KNN 和 KD 树

机器学习中，knn(k-nearest neighbor , 又称k近邻法)是一种比较简单的模型。就是通过计算两个数据集之间的距离远近，然后把一堆数据分为k类。它是一种典型的判别模型(discriminative model).

老板教导曰，这个方法简单到爆了，为什么要介绍这个方法呢，因为解决具体问题的时候，用这个方法试试，调调参数，效果往往很赞，为什么不介绍？管你方法简单还是复杂，f1-measure最高、计算量最小的方法就是最好的方法。某些拿着各种复杂的计算，看起来各种高深莫测却无法说明什么让人信服的道理，也无法用f1-measure说话的，只能用来发paper。

距离

首先我们要定义下距离这个概念。

假定有x_i = (x_i^{(1)},x_i^{(2)},x_i^{(3)},...,x_i^{(n)})和x_j = (x_j^{(1)},x_j^{(2)},x_j^{(3)},...,x_j^{(n)}),要知道x_i和x_j的差别有多大，何解?

有定义L_p, 即所谓 L_p distance 或 Minkowski distance. 其定义是这样的:

L_p(x_i,x_j) = (\Sigma_{l=1}^{n}|x_i^{(l)} - x_j^{(l)}|^p)^{\frac{1}{p}}

其意义是对每个向量求差的绝对值的p次方之和，然后开\frac{1}{p}次方。

比如有数据集 x_1=(1,2) 和 x_2=(3,4), 假定 p 为 3, 现在求 L_3(x_1,x_2)的值, 推导如下

L_3(x_1,x_2) = (\Sigma_{l=1}^{n}|x_1^{(l)} - x_2^{(l)}|^3)^{\frac{1}{3}} \\ = (|x_1^{(1)} - x_2^{(1)}| ^ 3 + |x_1^{(2)} - x_2^{(2)}| ^ 3 )^{\frac{1}{3}} \\ = (|1-3| ^ 3 + | 2 - 4 | ^ 3) ^{\frac{1}{3}} \\ = ( 2 ^ 3 + 2 ^ 3) ^{\frac{1}{3}} \\ = (16) ^{\frac{1}{3}} \\ = \sqrt[3]{16} \\

其实还是蛮简单的，若不是我这样的学渣，看到这样的数据集估计直接结果就出来了。

• 当 p = 1 的时候，有个特别的名字，叫曼哈顿距离(Manhattan distance);
• p = 2 的时候，称为欧氏距离(Euclidean distance);
• p = 3 的时候，称为阿格肯维距离(Joke distance);
• p = \infty 的时候，它是各个坐标距离的最大值, 也就是 L_\infty (x_i,x_j) = \max_i | x_i^{(l)} - x_j^{(l)}|

从图上说，p为上述几个值, 对于一个二维的数组，距离为"1"的边界大致如下图所示。

在纯数学计算上说，我们可以把这个公式推广到大于 0 有限任意长度的 N 维数组中。这样对于任意两个 N 维的数组，我们总是可以计算得出一个值，这个值越小，那么我们可以说这两个点在一个 N 维的空间中它们的“距离”越接近，也就是说，两个点“相似度”更高。

由点到树

然而，到目前为止，所谓的距离都是两者之间的距离。按照这个推法，如果有个数据集，有1000条数据，当我们拿出第1001条数据，期望能找到前面1000条数据中距离最近的数据，那么我们似乎要比较1000次，这显然是不可接受的，聪明的前辈们想出了一种特殊的技巧，能让我们尽可能少的比较，获得距离最近的数据集。那就是KD树。

使用KD树的方法其实也很简单。

我们首先要构造个KD树。

以一个数据集{T1(2,3),T2(5,4),T3(9,6),T4(4,7),T5(8,1),T6(7,2)}为例，构造方法如下：

• S1 : 首先，我们将数据集按照每个数据第一个向量排序，取中位数，本例中为{2,5,9,4,8,7}中，找到中间那个，也就是T6(7,2),它左边有{T1(2,3),T2(5,4),T4(4,7)},右边有{T3(9,6),T5(8,1)}
• S2 : 然后对分开的数据集分别按照第二个向量排序，取中位数，左边数据集中为{3,4,7},则根节点为T2(5,4)这个,右边数据集为{6,1},如之前惯例,若数据集为偶数个，则取右边的,所以根节点为T3(9,6).
• S3 : 第三步本应当按照第三个向量排序，但本数据集只有两个向量，所以继续按照以第一个向量来排序。 这样最后就得到了如下的一棵树：

还可以如下这样理解

然后一个新的数据集来后，我们只要按照同样的方法从根节点开始，一路查询下去，如果没有一个完全相同的，则将路上的各个根节点与之分别对比，复杂度为O(log_2n)，比之前的O(n)好多了

最后，我写了个demo，可以戳这里去看看，简单说就是随机生成一些数据集，组成个KD tree，然后再随机个新的数据，找之前数据中最接近的那个。

Reference:

[1] 李航. 统计学习方法[M]. 北京:清华大学出版社,2012.