1，kNN算法

试题描述：对于N个样本，每个样本为D维向量，采用欧式距离使用kNN做类预测。

1）给出预测时间复杂度。

2）当N很大时，有哪些方法可以降低复杂度？

3）k取值的大小对预测方差和偏差有何影响？

知识点：

kNN是通过测量不同特征值之间的距离进行分类。

思路是：如果一个样本在特征空间中的k个最邻近的样本中的大多数属于某一个类别，则该样本也划分为这个类别。kNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

算法的描述：

1）计算测试数据与各个训练数据之间的距离；

2）按照距离的递增关系进行排序；

3）选取距离最小的K个点；

4）确定前K个点所在类别的出现频率；

5）返回前K个点中出现频率最高的类别作为测试数据的预测分类

值选择：

当 的取值过小时，一旦有噪声得成分存在们将会对预测产生比较大影响，例如取 值为1时，一旦最近的一个点是噪声，那么就会出现偏差， 值的减小就意味着整体模型变得复杂，容易发生过拟合；

当的值取的过大时，就相当于用较大邻域中的训练实例进行预测，学习的近似误差会增大。这时与输入目标点较远实例也会对预测起作用，使预测发生错误。 值的增大就意味着整体的模型变得简单；

当 的时候，那么就是取全部的实例，即为取实例中某分类下最多的点，就对预测没有什么实际的意义了；

的取值尽量要取奇数，以保证在计算结果最后会产生一个较多的类别，如果取偶数可能会产生相等的情况，不利于预测。

关于距离：

常用的有：欧几里得距离、余弦值（cos）, 相关度 （correlation）, 曼哈顿距离 （Manhattan distance）。

kNN 很耗时，时间复杂度为 ，一般适用于样本数较少的数据集，当数据量大时，可以将数据以树的形式呈现，能提高速度，常用的有 kd-tree 和 ball-tree。

python代码：

#!/usr/bin/env python
#coding:utf-8

from numpy import *
import operator


def create_data_set():
    """
    创建训练集
    :return:
    """

    group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels


def classify(in_x, data_set, labels, k):
    """

    :param in_x:
    :param data_set:
    :param labels:
    :param k:
    :return:
    """

    data_set_size = data_set.shape[0]
    # 根据欧式距离计算训练集中每个样本到测试点的距离
    diff_mat = tile(in_x, (data_set_size, 1)) - data_set
    sq_diff_mat = diff_mat ** 2
    sq_distances = sq_diff_mat.sum(axis=1)
    distances = sq_distances ** 0.5

    # 计算完所有点的距离后，对数据按照从小到大的次序排序
    sorted_dist_indices = distances.argsort()

    # 确定前k个距离最小的元素所在的主要分类，最后返回发生频率最高的元素类别
    class_count = dict()
    for i in range(k):
        vote_label = labels[sorted_dist_indices[i]]
        class_count[vote_label] = class_count.get(vote_label, 0) + 1
    sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)
    return sorted_class_count[0][0]


if __name__ == '__main__':

    gr, labs = create_data_set()
    print("group：", gr)
    print("labels：", labs)

    print("classify: \n", classify([0.1, 2.9], gr, labs, 3))

2，关于Dropout

Dropout 背景：

在2012年，Hinton在其论文《Improving neural networks by preventing co-adaptation of feature detectors》中提出Dropout。当一个复杂的前馈神经网络被训练在小的数据集时，容易造成过拟合。为了防止过拟合，可以通过阻止特征检测器的共同作用来提高神经网络的性能。

Dropout可以作为训练深度神经网络的一种trick供选择。在每个训练批次中，通过忽略一半的特征检测器（让一半的隐层节点值为0），可以明显地减少过拟合现象。

当前Dropout被大量利用于全连接网络，而且一般认为设置为0.5或者0.3，而在卷积网络隐藏层中由于卷积自身的稀疏化以及稀疏化的ReLu函数的大量使用等原因，Dropout策略在卷积网络隐藏层中使用较少。

参考文献