1 笨笨的孩子慢慢学stay hungry stay foolish 2 学习，思考，实践，改变

0%

20191231面试2

发表于 更新于 Valine：

1，项目介绍

首先自我介绍。再介绍异常检测项目。在介绍广告CTR项目。

1，对每个项目的细节梳理清楚：

如lightGBM如何对类别特征进行节点分裂的？（lightGBM论文）

2，然后就是要仔细思考进一步的优化的地方在哪。

如何进一步提高点云的识别率呢？当时做了实验加多卷积层并没有明显的提升效果了，物体结构的特征点已经提取充分，所以并没用更深的网络。另一方面继续优化的点可以考虑点与点之间的领域结构，就像图像主要是考虑了相对位置关系，才可以用一些高反差核之类的卷积核提取图像的局部信息。

2 基础知识

中间问了机器学习的一些算法。

1，随机森林的采样体现在哪些地方？

（1）随机森林主要是Bagging和特征采用。Bagging是有放回的抽样，每次约63.2%的数据样本作为训练集。

随机森林每次没有用的样本数据有用吗？做包外预测$H^{oob}(x)$：

Bagging的泛化误差包外估计是：

包外估计可以辅助剪枝。

Bagging可以降低方差。

（2）另外RF引入了随机特征选择。就是每个结点都会随机选择一些特征来构建树。如下图的算法流程。第5行，先选取了部分特征用来构建树（森林中每棵树都只随机的选择特征集中的一部分特征进行训练，因而森林中的每棵树都不会全都关注某些有很强预测性的特征上面），然后每个结点都有选择特征子集（line 5）来计算Gini impurity或均方误差，以此挑选最优划分特征（line 6），计算最优划分点（line7）。

（额额额，后面我居然给直接忘了，还有后面算法题短路得不行，捂脸）

每个结点的特征子集的好处：如果特征A1,A2彼此相关。树根据信息增益选择了A1后，A2的信息增益一定会变得很小，因为A1和A2所引起的不确定度是同一个不确定度，确定了A1后那么这个不确定度就没有了，确定A2后数据集的不确定性不会再减小了，因而造成的结果就是虽然说A1和A2同等重要，但是所有的树每次选择A1后就不会选择A2了。

20200102RandomForest

（3）结合策略

随机森林的结合策略有：平均法（简单平均、加权平均），投票法，stacking（先从初始数据集训练出初始学习器，然后生成一个新数据集用于训练次级学习器，交叉验证）

20200102Stacking

（4）优点

在数据集上表现良好，两个随机性的引入，使得随机森林不容易陷入过拟合，抗噪声能力强。

它能够处理很高维度（feature很多）的数据，并且不用做特征选择，对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化。

训练速度快，可以得到变量重要性排序（两种：基于OOB误分率的增加量和基于分裂时的GINI下降量）

2，梯度下降算法在GBDT有吗？动量法可以用到里面吗？

GBDT本身就是梯度提升法。在构建树的时候，是根据上一次的预测值和真实值的预测残差来构建的，其实就是拟合的损失函数的负梯度。

3 算法题

海量数据，找出最大的k个数。紧张得面红耳赤，下来了总结学习下咯。

思路1，将数据qsort从大道小排序，取前k-1个数。回顾下qsort，复杂度O(nlogn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

void swap(int A[], int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

int partition(int A[],int l, int r, int& pivot){
    do{
        while(A[++l] > pivot);
        while((l<r) && (A[--r] < pivot));
        swap(A,l,r);
    }while(l<r);
    return l;
}

void myqsort(int A[],int i,int j){
    if (j <= i) return;
    int pivotIndex = (i+j)/2;
    swap(A,pivotIndex,j);
    int k = partition(A,i-1,j,A[j]);
    swap(A,k,j);
    myqsort(A,i,k-1);
    myqsort(A,k+1,j);
}
// function call: myqsort(num, 0, N-1);
int main(){
  	int k;
    int num[3] = {1,-2,0};
    myqsort(num, 0, N-1);
    for (int i=0; i<k; i++) {
        cout<<num[i]<<endl;
    }
}

思路2，用partition函数每次划分，两边排好序来做。当中间pivot下标正好是k-1则左边部分就是前k大个数。左边大的数的个数大于k，则最大的k个数在左边。否则在右边，个数为k-count个，复杂度是O(nlog2K)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int KthBig(int A[],int i,int j,int kBig){
    int count = 0;
    if (j <= i || A == NULL) return -1;
    int pivotIndex = (i+j)/2;
    swap(A,pivotIndex,j);
    int index = partition0(A,i-1,j,A[j]); // k is index
    swap(A,index,j);
    count = index - i + 1; // count the k big data
    if (kBig == count) {
        return index;
    }
    else if(count > kBig){
        return KthBig(A, i, index, kBig);
    }
    else{
        return KthBig(A, index, j, kBig-count);
    }
}

思路3，k个的最大堆。然后后面的数一遍遍历过去，每次有比堆当前最小值小的即替换，调整堆结构。

首先堆的思想：完全二叉树，局部有序，O(logn)。简单基于数组的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <queue>
using namespace std;

const int MAX_N = 100;
int heap[MAX_N],sz=0; //sz is global variable, meaning the lengh of heap

void heap_push(int x){
    //own node's num.
    int node_index = sz++;
    while (node_index > 0) {
        int p = (node_index-1)/2; //i's parent
        if (heap[p] >= x) {
            break; // sequence is ok
        }
        // parent's value put down, node value go up
        heap[node_index] = heap[p];
        node_index = p;
    }
    heap[node_index] = x;
}

int heap_pop(){
    // max (root)
    int rec = heap[0];
    // The value to put in the root
    int x = heap[--sz];
    //Swap from root
    int i = 0;
    while (i*2+1 < sz) {
        //compare the children value
        int a = i*2+1; // left child
        int b = i*2+2; // right child
        if (b < sz && heap[b] > heap[a]) {
            a = b;
        }
        // sequence is right
        if (heap[a] <= x) {
            break;
        }
        // child's value go up
        heap[i] = heap[a];
        i=a;
    }
    heap[i] = x;
    return rec;
}

int main(){
    //push(3);
    heap_push(9);
    heap_push(2);
    heap_push(6);
    for (int i=0; i<sz; i++) {
        cout<<heap[i]<<endl;
    }
    cout<<"pop:"<<heap_pop()<<endl;
  	
  	// also we can use library
    priority_queue<int> qqueue;
    qqueue.push(9);
    qqueue.push(2);
    qqueue.push(6);
    //loop until it is empty
    while (!qqueue.empty()) {
        cout<<qqueue.top()<<endl;
        qqueue.pop();
    }
    return 0;
}

最近面了三次，也见识了，知道哪该查漏补缺了。

1，项目的总结博客（启发式算法、三维点云、异常检测部分）

2，深度模型CTR（DeepCTR入手）

3，leecode刷题系列

4，其他（印象笔记搬迁到博客，kaggle比赛开源代码读读）

Reference

https://blog.csdn.net/weixin_37688445/article/details/79272319