唯品会2018校招数据挖掘、机器学习笔试题（A卷）

题目

1.（数据结构与算法）列举至少2种排序算法（如快排），并写出实现代码。

2.（数据结构与算法）现有N个数，找出其中第M大的数，这里的N远大于M。请说明算法思路、复杂度。

3.（机器学习理论）请列举生成模型与判别模型的区别。

4.（机器学习理论）请列举分类模型和回归模型的区别。

5.（机器学习理论）什么是欠拟合、过拟合？避免过拟合有哪些途径？

6.（机器学习理论）请列举Random Forest和GBDT的区别。

7.（机器学习理论）梯度下降法求解最优化问题的原理与步骤。

参考答案

1.

冒泡排序

//冒泡排序
    public void bubbleSort(int[] a)
    {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n-1; j++) {
                if (a[j] > a[j + 1]) {
                    int t = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = t;
                }
            }
        }
    }

快速排序

//一趟快速排序
    public int PartSort(int i, int j ,int[] a)
    {
        int r = a[i];
        while (i < j) {
            while (a[j] >= r &&i<j)
                j--;
            //加了if 其实是 降低了效率的，这里加if其实是为了i++这个语句
            //可做如下优化
            /*
             * 因为a[j]=r是，也会--，避免了if的判断。
            if (i<j)
            {
                a[i]=a[j];
                i++;
            }
            */
            a[i]=a[j];
            System.out.println("hi:"+i+",j:"+j);
            //这里不用判断的原因是因为就算a[i]=r了，i也会++.
            while(a[i] <= r &&i<j)
                i++;
            /*
             * 优化同上
            if(i<j)
            {
                a[j]=a[i];
                j--;
            }
            */
            a[j]=a[i];
            System.out.println("li:"+i+",j:"+j);
        }
//      System.out.println("i:"+i+",j:"+j);
        a[i]=r;
        return i;
    }

    //快速排序主体
    public void quickSort(int i, int j ,int[] a)
    {
//      int n = a.length-1;
        if(i>=j)
            return;
        System.out.println("qi:"+i+",j:"+j);
        int r = PartSort(i,j,a);
        System.out.println("r:"+r);
        for(int k=0;k<a.length;k++)
            System.out.print(a[k]);
        System.out.println();
        quickSort(i,r-1,a);
        quickSort(r+1,j,a);
    }

采用快速排序算法思想，一次快速排序,返回值若为k，其实a[k]对应的位置是第k大的数，则若k>m, 则在左半部分继续寻找第m大的数，否则在右半部分寻找第（m-k）大的数。 
复杂度为O(N)。 
代码如下：

public int findMaxK(int i, int j, int[] a,int k)
    {
        System.out.println("findi:"+i+",j:"+j+"k:"+k);
        if(i>j)
            return -1000000; 
        int r = PartSort(i,j,a);
        System.out.println("findR:"+r);
        if (r<k)
            return findMaxK(r+1,j,a,k-r);
        else if (r>k)
            return findMaxK(i,r-1,a,k);
        else
            return a[r];
    }

生成模型是通过数据学习联合概率分布P(x,y)，然后求出条件概率分布P(Y|X)，作为预测的模型，即生成模型为：P(Y|X)=P(X,Y)/P(X)

生成模型的特点：生成模型可以还原联合概率分布，而判别模型不行；生成模型的收敛速度更快，即当样本容量增大时，生成模型能更快的收敛到真实模型；当存在隐变量时，只能用生成模型。 
常见的生成模型有朴素贝叶斯，隐马尔科夫链。

判别模型是通过数据直接学习判别函数Y=f(X)或者条件概率作为预测模型。

判别模型的特点：判别模型直接学习的还是判别函数或者条件概率分布，直接面对预测，往往学习的准确率要高；判别模型由于直接学习条件概率或决策函数，可以对数据进行各种程度上的抽象/定义特征并使用特征，因此可以简化学习问题。 
常见的判别模型有SVM，逻辑回归等。

4.

分类和回归的区别在于输出变量的类型。

定量输出称为回归，或者说是连续变量预测；

定性输出称为分类，或者说是离散变量预测。

5.

欠拟合：对训练数据拟合不够，偏差较大，根本的原因是特征维度过少，导致拟合的函数无法满足训练集，训练误差较大。

过拟合：对训练数据过度拟合，方差较大，根本的原因则是特征维度过多，导致拟合的函数完美的经过训练集，但是对新数据的预测结果则较差。

解决过拟合问题，则有3个途径：

a.特征选择：减少特征维度; 包括前向算法，后向算法以及Filter Method.

b.模型选择：一般通过交叉验证方法来避免过拟合。

c.正则化：里面涉及到概率学派和贝叶斯学派的区别，但是其本质是类似与特征选择的，通过先验概率，限制参数的取值，使得某些参数接近于0，则对应的特征基本不起作用，起到降低模型复杂度的作用。

6.

随机森林：bagging算法，对训练数据进行抽样，每次取不同的训练数据进行决策树的训练，最终分类采用多数表决的方法。不同树之间的训练是并行的。

GBDT：boosting算法，所有训练数据都会一起放入模型中，而不会抽样。通过调整样本权重对模型进行修正得到下一个模型，即串行方法，得到最终输出。在GBDT中，下一个模型拟合的不再是原始数据，而是梯度，以梯度去代替残差值。

假设目标函数为min L(x;a)

梯度下降的求解步骤就是不断更新a，使得L下降，a的更新方法为：

a:=a-η*L对a的梯度。

其原理是，因为在数学中，一个函数变化最快的方向便是其梯度方向，因为是最小化问题，所以我们使得a降低。