唯品会2018校招机器学习、算法笔试题（B卷）

题目

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

2.（数据结构与算法）已知一随机发生器，产生0的概率是P，产生1的概率是1-P。现在需要构造一个发生器，使得它构造0和1的概率均为1/2，请写出思路或伪代码 。

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

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

5.（机器学习理论）请描述决策树的原理、过程、终止条件，以及如何防止过拟合。

6.（机器学习理论）请描述K-means的原理，说明选择聚类中心的方法。

7.（机器学习理论）请描述推荐系统中协同过滤算法的原理。

参考答案

冒泡排序

//冒泡排序
    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);
    }

这道题想等概率产生0、1，就需要找到两个独立事件，这个两个独立事件发生的概率相同，已知随机数生成器可以以p产生0，以1-p产生1，所以有下面4个独立事件，用随机数生成器产生00，01，10，11，各自的概率分别为p*p，p*(1-p)，(1-p)*p，(1-p)*(1-p)可以发现生成01，10的概率相同，因此只保留这两种情况敏感词舍弃，然后将01映射为0，10映射为1，则等概率0，1随机数生成器可得到。

3.

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

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

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

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

4.

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

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

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

5.

决策树原理：

从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配其子节点；每个子节点对应着特征的一个取值，如此递归的对实例进行测试并分配，直到达到叶节点，最后将实例分到叶节点的类中。

过程：

特征选择、树的生成和树的剪枝

终止条件：

节点中的样本个数小于预定阈值，或样本集的基尼指数小于（信息增益或信息增益比大于）预定值，或者没有更多特征

如何防止过拟合：

剪枝

K-Means算法的思想很简单，对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大

输入：样本集D={x1, x2, x3,…,xm}，聚类簇数k 

输出：簇划分C={C1,C2,…,Ck} 

从D中随机选取k个样本作为初始向量； 

repeat: 

初始化所有Ci为空集； 

对于样本集里每个样本x: 

计算x与k个初始向量的距离，选择距离最小的初始向量的簇标记j作为x的簇标记，将x加入Cj中； 

对于每个簇： 

计算新的均值向量，如果新的均值向量与上一步的不同，则更新；否则保持当前均值向量 不变； 

until 当前均值向量均未更新

协同过滤推荐算法是诞生最早，并且较为著名的推荐算法。主要的功能是预测和推荐。算法通过对用户历史行为数据的挖掘发现用户的偏好，基于不同的偏好对用户进行群组划分并推荐品味相似的商品。协同过滤推荐算法分为两类，分别是基于用户的协同过滤算法(user-based collaboratIve filtering)，和基于物品的协同过滤算法(item-based collaborative filtering)。简单的说就是：人以类聚，物以群分。下面我们将分别说明这两类推荐算法的原理和实现方法。