k-NN(k Nearest Neighbor)

直观理解

  k-NN是一种基于“物以类聚人以群分”思路的分类方法。

  

  以下图为例,小明为刚加入这个班级不久的新同学,在挑选兴趣小组时稍微犯了点难,因为他好像对什么都不太感兴趣,但是经过一周和班上同学的接触,小明和同学们的亲疏程度已经有了自己的判断,在图中以距离的形式表现了出来,距离越近的关系越好。

  那么,在如何给小明划分群体的这个问题上,我们就可以使用k-NN来进行判断。我们取k = 6,即认为小明的群体划分是以和他关系最好的6个人来判断的,明显,图中和小明最亲近的6个人中,5个是活泼调皮类型的,1个是文静类型的,因此我们可以大致判断,小明有比较大的可能也是属于活泼调皮类型的。

小明

但是如果考虑k > 10的情况,例如k = 11,那么我们可以发现,11个人中,5个活泼好动,另外6个文静,则按照k-NN的思想,我们认为小明是属于文静类型的人。

言归正传

k-NN是一种基本的分类、回归方法,对特征向量空间进行划分。决定这种方法最终效果的因素主要有3个:

  1. k值的选择(一般都不大,可以采用交叉验证的方式来确定)

  2. 距离的度量方式(这里的距离也可以是相似度,空间的距离/相似度并不只有欧氏距离一种)

  3. 分类决策规则(通常采用多数决)

其中的

(1)交叉验证(cross-validation) 一般又被称作是k折交叉验证(k-fold cross-validation),其实就只是把测试集分成k份,然后用k-1份训练模型,用1份来验证准确度,循环k次求得最终的算法准确度。详情可以参看这里(交叉验证)

(2)有关距离/相似度的度量方式,除了欧式距离之外,还可以使用曼哈顿距离、或者向量余弦相似度等其他方法。

(3)所谓多数决就是少数服从多数。当然还可以选择少数决或者随机决,以实际需求为准。

如何快速判断分类?显然,每一次判断一个新样本的分类都要和所有的模型样本进行一次比对才能找到最近的k个元素,这每一次的计算代价就是n^2,那么有没有更快的做法呢?答案是肯定的,这个方法就是使用kd树(kd tree)

Kd Tree(k-dimensional tree)

是一种对空间中的实例点进行划分的一种二叉树数据结构。

通过这种数据结构,我们可以快速找到某个实例的最近邻居。

KD Tree

首先,图上的这些方格划分出来的区域就是kd tree的直观表示,借助于此我们可以看到,面对新来的蓝色点,要找它的邻居就可以从离他最近的几个区域内开始找起,而不用拿他和其他所有的实例点一一对比。效率就在这里体现了出来。具体如何构建kd tree以及如何寻找目标实例的n个近邻就是现在要说的。

I.如何构建kd tree

1.选择一个坐标轴(通常依次轮流选择),并在其上找到选定一个切分点(一般是中位数),此切分点作为kd tree的当前节点,并以它将剩下的节点划分为两个子空间。

2.在子空间中重复步骤1,直到无法划分出新的子空间为止。

举例如下:

实例点集:{(2,3), (4,7), (5,4), (7,2), (8,1), (9,6)}

Kd Tree Build

如何对kd-tree进行快速查找

//TODO: to be continued.