6.1基本概念

6.1.1 kNN的基本思路

kNN：k-Nearest Neighbor算法是一种分类算法，其核心想法是根据给定的训练集，对于需要判别的测试集中的样本，在训练集中找到与之最接近的k个样本，并统计这k个样本的分类情况，将出现次数最多的类别作为测试集中的样本的分类结果。
如果将k个最近的样本用 $六、k近邻分类 kNN - 图1$ #card=math&code=N_k%28x%29)来表示，那么kNN的分类决策用公式表示就是：

$六、k近邻分类 kNN - 图2$ %7DI(yi%3Dc_i)%0A#card=math&code=y%3D%5Carg%5Cmax%5Csum%7Bx_i%5Cin%20N_k%28x%29%7DI%28y_i%3Dc_i%29%0A)

kNN的基本思路其实就是：如果一个东西看起来像鸭子，走路像鸭子，吃饭也像鸭子，那么它很可能就是一只鸭子。而“最接近”这个概念是有待商榷的，因为我们没有统一的距离度量法则，因此需要确定一种度量距离的方法。此外k也需要自己选择，k=1的时候这个算法被称为最近邻算法

6.1.2距离度量的选择

我们需要在n维的特征空间中度量两个点之间的距离，对于n维空间中的两个向量 $六、k近邻分类 kNN - 图3$ ，我们定义距离：

$六、k近邻分类 kNN - 图4$ %3D(%5Csum%7Bl%3D1%7D%5En%7Cx_i%5E%7B(l)%7D-x_j%5E%7B(l)%7D%7C)%5E%7B%5Cfrac%7B1%7D%7Bp%7D%7D%0A#card=math&code=L_p%28x_i%2Cx_j%29%3D%28%5Csum%7Bl%3D1%7D%5En%7Cx_i%5E%7B%28l%29%7D-x_j%5E%7B%28l%29%7D%7C%29%5E%7B%5Cfrac%7B1%7D%7Bp%7D%7D%0A)

上面的公式中：

p=2的时候称为欧几里得距离，
p=1的时候称为曼哈顿距离
当p为无穷大的时候，L就是每个坐标中距离最大值.

6.1.3 k的选择

k的选择也对最终的结果有比较大的影响，k选择太小的话学习时的误差会减小，但是估计误差会增大，预测结果会对样本的位置关系非常敏感。
如果k选的太大，则估计误差会降低，但是学习时的误差会增大，二者各有利弊，当然如果k=N那么就是按照出现次数最多的作为结果，完全忽略了模型中的大量有用信息。

6.2 kd树：kNN求解

kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构，是一种二叉树，用来表示对k维空间的一个划分，使得每个k维空间中数据集的点对应到一个k维空间超矩形上面去。

6.2.1 kd树的构造

一般来说构造kd树的方法是
- 先选择根节点
- 然后每次选定一个坐标轴，并用该方向的样本点坐标的中位数作为划分的依据，并沿着垂直于坐标轴的方向作超矩形
- 然后将k维空间分出了新的两个区域，之后就在两个新的区域里面换一个坐标轴重复上面的操作，直到每个样本点都进行了划分，每个子区域中没有样本点的时候停止。
用这种方法构造出来的kd树是平衡的

6.2.2 kd树的搜索

对于一棵构造好的kd树进行k近邻搜索可以省去对大部分数据点的搜索，从而减少搜索的计算量，以最近邻为例，对于给定的目标点，搜索其最邻近的点需要首先找到包含目标点的叶节点(注意，kd树里的节点代表的是超平面里的一块超矩形，不是样本点)，然后从该叶节点出发，回退到
父节点，并不断查找与目标点最邻近的节点，当确定不可能存在更近的节点的时候终止。

6.3 kNN代码实现

尝试了蔡老师机器学习课程中的kNN作业，目标是用kNN实现一个简单的验证码数字识别，主要任务其实就是用最原始的方法实现kNN，然后对数据集进行一定的标注之后用kNN来识别数字，可能是因为场景比较简单，最后实现的验证准确率非常高。

def knn(x, x_train, y_train, k):
    """
    KNN k-Nearest Neighbors Algorithm.
        INPUT:  x:         testing sample features, (N_test, P) matrix.
                x_train:   training sample features, (N, P) matrix.
                y_train:   training sample labels, (N, ) column vector.
                k:         the k in k-Nearest Neighbors
        OUTPUT: y    : predicted labels, (N_test, ) column vector.
    """
    # Warning: uint8 matrix multiply uint8 matrix may cause overflow, take care
    # Hint: You may find numpy.argsort & scipy.stats.mode helpful
    # Hint: distance = (x - x_train)^2. How to vectorize this?
    # YOUR CODE HERE
    # begin answer
    N_test, P = x.shape
    y = np.zeros((N_test, 1))
    for i in range(N_test):
        test_vector = x[i]
        # 这里采用传统方法实现kNN，即采用最naive的方法计算测试数据和训练数据每个点的距离
        # 并从中选出最大的K个
        distance = np.linalg.norm(x_train - test_vector, axis=1)
        top_k_index = np.argsort(distance)[0: k]
        max_mode, count = scipy.stats.mode(y_train[top_k_index])
        y[i] = max_mode
    # end answer
    return y