K近邻算法

在进行图像搜索时，要求系统返回与查询图片相似的图像集，这里头涉及高维空间的数据查询问题。排序和寻找是计算机技术的基础算法，最基本的是对一维数组排序和在一维数组中寻找元素。在图像检索系统中面对的是大规模的高维数据，对查询算法的效率要求更高，这里介绍是一种基本的查询算法--最近邻（Nearest Neighbor ）或K近邻(KNN)。最近邻搜索（Nearest Neighbor Search）：最近邻查询是最重要的空间查询之一，也是文本着重考虑的类型。其定义是：给定一个查询点q和一个距离度量（有欧几里德距离、曼哈顿距离等），一个最近邻查询找出一个离查询点q最近的空间数据对象。它的一般化形式为k(k>=1)最近邻查询，定义为：给定一个查询点q，一个正整数k以及一个距离度量，则一个k最邻近查询找出k个离q最近的空间数据对象。如上图所示，查询对象q的k邻近1NN(q)={a},4NN(q)={a,b,c,d}。

最近邻规则也是一种分类方法，如上图中，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。

用原始的穷举法可实现最近邻查询，结果如上图（K=3），Matlab代码如下：

当数据点数目增大时，穷举法的计算量会以指数级别增长。1977年Friedman提出的k-d树快速搜索算法[Friedman & Bentley s.t. '77]可以快速找到最近邻，但当特征点描述符多于10维时其效率就很低，并不比穷举法效率高。1997年Beis和Lowe提出了一种近似算法称为Best-Bin-First(BBF)[Beis & Lowe'99] ，这种近似算法能够以很高的概率找到最近邻点。

k-d树（K-dimension tree）是二叉检索树的扩展，k-d tree的每一层将空间分成两个。树的顶层结点按一维进行划分，下一层结点按另一维进行划分，以此类推，各个维循环往复。划分要使得在每个结点，存储在子树中大约一半的点落入一侧，而另一半落入另一侧。

参照上图，用二维(K=2)数据的实例来说明K-D Tree的建立：

1. 根结点选择：将数据按x维排序，以中值所在数据点(5,8)作为根结点，然后以此结点为参考作第一次分裂；

注意，这里涉及两种基本操作：

（1）选择分裂(split)的维度，即在哪一维数据上将原数据分为两半，有两种做法：

一是取  当前层数n mod 数据维数K：如第一层时，n = 0，n mod K = 0，即在第一维数据上寻找分裂点。

二是取 方差最大的那维数据，即在各维数据上分别计算方差，方差最大者数据越分散，故在该维数据上寻找分裂点。

（2）在分裂维度上选择分裂点：通常是取该数据的中值点。

2. 分裂：（父）根结点p的分裂维split_dim = 0，即在x维上分裂，第split_dim分量小于p[split_dim]的放于左侧，否之放在右侧。对左右侧分别确定分裂维、分裂点，循环，直至最后。

照以上步骤，Matlab中递归实现如下：

其划分2-D平面的过程如下：

k-d树的数据结构决定了能够减少查询量，因为很多结点在查询时不参与比较。下面通过实例说明最近邻(K=1)的查询过程：

1. 以q(2,6)做为查询点，在KD Tree上自顶向下进行比较。

2. 在结点p处，如果q(split_dim)