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

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

那么,knn具体是怎么算的呢?首先我们要定义下距离这个概念。

假定有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_ix_j的差别有多大,何解?

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

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

其中 p 大于等于1.

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

比如有数据集 x1=(1,2) 和 x2=(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"的边界大致如下图所示。

L_p

然而,到目前为止,所谓的距离都是两者之间的距离。按照这个推法,如果有个数据集,有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 : 第三步本应当按照第三个向量排序,但本数据集只有两个向量,所以继续按照以第一个向量来排序。 这样最后就得到了如下的一棵树:

Tree

还可以如下这样理解

kd_tree

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

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

Reference:

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


Yu

Ideals are like the stars: we never reach them, but like the mariners of the sea, we chart our course by them.

2 Comments

Sonullx Liu · May 20, 2014 at 12:13

Google Chrome 34.0.1847.137 Google Chrome 34.0.1847.137 Windows 7 Windows 7

学习了。
KDTree就是多层BSTree吧?这个东西要是玩平衡似乎不是很容易。

    yu · May 20, 2014 at 16:46

    Google Chrome 34.0.1847.137 Google Chrome 34.0.1847.137 GNU/Linux x64 GNU/Linux x64

    @Sonullx Liu 和BSTree的确很像,而且岂止”玩平衡不容易”,我根本没有见到哪个天才写过调平方面的paper。如果要插入个新的数据,我会的唯一方法就是rebuild一个tree。

    但和BSTree还是有点区别的。BS期望的是”找到个相同的数据”,否则返回空,而KD期望是”找到一组全数据集的子集,该子集中包含全数据集中和目标数据最相似的那组数据”。然后逐个对比找最相似。
    而至于”完全一样的数据集”基本完全没这个期望嘛。

Leave a Reply to yu Cancel reply

Your email address will not be published. Required fields are marked *