从K近邻算法、距离度量谈到KD树、SIFT+BBF算法

前言

一个人坚持自己的兴趣是比较难的，因为太多的人太容易为外界所动了，而尤其当你无法从中得到多少实际性的回报时，所幸，我能一直坚持下来。毕达哥拉斯学派有句名言：“万物皆数”，最近读完「微积分概念发展史」后也感受到了这一点。同时，从算法到数据挖掘、机器学习，再到数学，其中每一个领域任何一个细节都值得探索终生，或许，这就是“终生为学”的意思。

本文各部分内容分布如下：

第一部分讲K近邻算法，其中重点阐述了相关的距离度量表示法，

第二部分着重讲K近邻算法的实现--KD树，和KD树的插入，删除，最近邻查找等操作，及KD树的一系列相关改进(包括BBF，M树等);

第三部分讲KD树的应用：SIFT+kd_BBF搜索算法。

同时，你将看到，K近邻算法同本系列的前两篇文章所讲的决策树分类贝叶斯分类，及支持向量机SVM一样，也是用于解决分类问题的算法，

而本数据挖掘十大算法系列也会按照分类，聚类，关联分析，预测回归等问题依次展开阐述。

第一部分、K近邻算法 1.1、什么是K近邻算法

何谓K近邻算法，即K-Nearest Neighbor algorithm，简称KNN算法，单从名字来猜想，可以简单粗暴的认为是：K个最近的邻居，当K=1时，算法便成了最近邻算法，即寻找最近的那个邻居。为何要找邻居?打个比方来说，假设你来到一个陌生的村庄，现在你要找到与你有着相似特征的人群融入他们，所谓入伙。

用官方的话来说，所谓K近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例(也就是上面所说的K个邻居)，这K个实例的多数属于某个类，就把该输入实例分类到这个类中。根据这个说法，咱们来看下引自维基百科上的一幅图：

如上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。也就是说，现在，我们不知道中间那个绿色的数据是从属于哪一类(蓝色小正方形or红色小三角形)，下面，我们就要解决这个问题：给这个绿色的圆分类。

我们常说，物以类聚，人以群分，判别一个人是一个什么样品质特征的人，常常可以从他/她身边的朋友入手，所谓观其友，而识其人。我们不是要判别上图中那个绿色的圆是属于哪一类数据么，好说，从它的邻居下手。但一次性看多少个邻居呢?从上图中，你还能看到：

如果K=3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。

如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。

于此我们看到，当无法判定当前待分类点是从属于已知分类中的哪一类时，我们可以依据统计学的理论看它所处的位置特征，衡量它周围邻居的权重，而把它归为(或分配)到权重更大的那一类。这就是K近邻算法的核心思想。

1.2、近邻的距离度量表示法

上文第一节，我们看到，K近邻算法的核心在于找到实例点的邻居，这个时候，问题就接踵而至了，如何找到邻居，邻居的判定标准是什么，用什么来度量。这一系列问题便是下面要讲的距离度量表示法。但有的读者可能就有疑问了，我是要找邻居，找相似性，怎么又跟距离扯上关系了?

这是因为特征空间中两个实例点的距离可以反应出两个实例点之间的相似性程度。K近邻模型的特征空间一般是n维实数向量空间，使用的距离可以使欧式距离，也是可以是其它距离，既然扯到了距离，下面就来具体阐述下都有哪些距离度量的表示法，权当扩展。

1. 欧氏距离，最常见的两点之间或多点之间的距离表示法，又称之为欧几里得度量，它定义于欧几里得空间中，如点 x = (x1,...,xn) 和 y = (y1,...,yn) 之间的距离为：

(1)二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离：

(2)三维空间两点a(x1,y1,z1)与b(x2,y2,z2)间的欧氏距离：

(3)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的欧氏距离：

也可以用表示成向量运算的形式：

其上，二维平面上两点欧式距离，代码可以如下编写：

 

 

//unixfy：计算欧氏距离 double euclideanDistance(const vector<double>& v1, const vector<double>& v2)

//把未搜索数分支入口,差值存储在min_pq, if( minpq_insert( min_pq, unexpl, ABS( kv - feat->descr[ki] ) ) ) { fprintf( stderr, "Warning: unable to insert into PQ, %s, line %d ", __FILE__, target="_blank">http://weibo.com/1580904460/yDmzAEwcV#1348475194313

“编译的过程中，直接用的VS2010 + opencv(并没下gsl)。2012.09.24”。....

本文完整源码有pudn帐号的朋友可以前去这里下载：http://www.pudn.com/downloads340/sourcecode/graph/texture_mapping/detail1486667.html(没有pudn账号的同学请加群：169056165，至群共享下载，验证信息：sift)。感谢诸位。

参考文献及推荐阅读 维基百科，http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm; 机器学习中的相似性度量，http://www.cnblogs.com/heaad/archive/2011/03/08/1977733.html; 杰卡德相似系数及距离，http://www.cnblogs.com/heaad/archive/2011/03/08/1977733.html; 统计学习方法，李航; 概率论与数理统计 第四版 盛骤等编，高教版; 《图像局部不变特性特征与描述》王永明 王贵锦 编著; 数据挖掘：实用机器学习技术，[新西兰]Ian H.Witten 著，第4章4.7节; 模式分类，第4章 非参数技术，[美] IRichard O. Duda / Peter E. Hart / David G. Stork 著; http://underthehood.blog.51cto.com/2531780/687160; http://grunt1223.iteye.com/blog/921371; http://www.cnblogs.com/eyeszjwang/articles/2429382.html; http://blog.csdn.net/ijuliet/article/details/4471311; Rob Hess维护的sift库，http://blogs.oregonstate.edu/hess/code/sift/; 酷壳，http://coolshell.cn/articles/8052.html; rubyist，http://segmentfault.com/q/1010000000094674; 皮尔逊相关系数维基百科页面，http://t.cn/zjy6Gpg; 皮尔逊相关系数的一个应用：http://www.sobuhu.com/archives/567; http://blog.csdn.net/wsywl/article/details/5727327; 标准差，http://zh.wikipedia.org/wiki/%E6%A0%87%E5%87%86%E5%B7%AE; 协方差与相关性，http://t.cn/zjyXFRB ; 电子科大kd树电子课件：http://t.cn/zjbpXna; 编程艺术之寻找最小的k个数：http://blog.csdn.net/v_JULY_v/article/details/6403777; 机器学习那些事儿，http://vdisk.weibo.com/s/ix_9F; 大嘴巴漫谈数据挖掘，http://vdisk.weibo.com/s/bUbzJ; http://www.codeproject.com/Articles/18113/KD-Tree-Searching-in-N-dimensions-Part-I; 一个库：http://docs.pointclouds.org/trunk/group__kdtree.html; 3D上使用kd树：http://pointclouds.org/; 编辑数学公式：http://webdemo.visionobjects.com/equation.html?locale=zh_CN; 基于R树的最近邻查找：http://blog.sina.com.cn/s/blog_72e1c7550101dsc3.html; 包含一个demo：http://www.leexiang.com/kd-tree; 机器学习相关降维算法，http://www.cnblogs.com/xbinworld/category/337861.html; Machine Learning相关topic，http://www.cnblogs.com/jerrylead/tag/Machine%20Learning/; 机器学习中的数学，http://www.cnblogs.com/LeftNotEasy/category/273623.html; 一堆概念性wikipedia页面; 基于度量空间高维索引结构VP-tree及MVP-tree的图像检索，王志强，甘国辉，程起敏; Spill-Trees，An investigation of practical approximate nearest neighbor algorithms; DIST ANCE-BASED INDEXING FOR HIGH-DIMENSIONAL METRIC SP ACES，作者：Tolga Bozkaya & Meral Ozsoyoglu; “Multidimensional Binary Search Trees Used for Associative Searching”，Jon Louis Bentley。

来源：v_JULY_v博客

链接：http://m.blog.csdn.net/article/details?id=8203674#0-tsina-1-32915-397232819ff9a47a7b7e80a40613cfe1