最近邻搜索NearestNeighborSearch.doc

最近邻 搜索 Nearest Neighbor Search
最近邻 搜索 Nearest Neighbor
Search
在进行图像搜索时，要求系统返回与查询图片相似的图像集，这里头涉及高维空间的数据查询问题。排序和寻找是计算机技术的基础算法，最基本的是对一维数组排序和在一维数组中寻找元素。在图像检索系统中面对的是大规模的高维数据，对查询算法的效率要求更高，这里介绍是一种基本的查询算法--最近邻(NearestNeighbor)或K近邻(KNN)。最近邻搜索
(NearestNeighborSearch):最近邻查询是最重要的空间查询之一，也是文本着
给定一个查询点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代码如下:
12
34
56
78
911222324252627282930functionknn_2d_demo()
%KNN2DDemodim=2;
num=40;
X=randi(100,num,dim); Q=randi(100,1,dim);
K=3;
[indexsdistances]=KNNS(X,Q,K); figureholdonplot(X(:,1),X(:,2),
'b.'
)
plot(X(indexs,1),X(indexs,2), 'ro'
)
plot(Q(1),Q(2),
'g*'
)
plot(Q(1),Q(2),
'co'
,
'MarkerSize'
,ceil(distances(K))*6)
holdofffunction
[indexsdistances]=KNNS(X,Q,K) %X--数据点集N×D
--查询数据N×D %Q
%K--查询近邻数
%indexs--KNN点集索引
%distances--查询点同KNN点的距离
[n,dim]=size(X);
query_mat=repmat(Q,n,1); dist_list=sqrt(
sum
((X-query_mat).^2,2));
[value,index]=
sort
(dist_list);
indexs=index(1:K);
distances=value(1:K);
当数据点数目增大时，穷举法的计算量会以指数级别增长。1977年
Friedman提出的k-d树快速搜索算法[.'77]可以快速找到
最近邻，但当特征点描述符多于10维时其效率就很低，并不比穷举法效率高。
1997年Beis和Lowe提出了一种近似算法称为Best-Bin-First(BBF)[BeisLowe'99]，这种近似算法能够以很高的概率找到最近邻点。
k-d树(K-dimensiontree)是二叉检索树的扩展，k-dtree的每一层将空间分成两个。树的顶层结点按一维进行划分，下一层结点按另一维进行划分，以此类推，各个维循环往复。划分要使得在每个结点，存储在子树中大约一半的点落入一侧，而另一半落入另一侧。
参照上图，用二维(K=2)数据的实例来说明K-DTree的建立:
:将数据按x维排序，以中值所在数据点(5,8)作为根结点，然后以此结点为参考作第一次分裂;
注意，这里涉及两种基本操作:
(1)选择分裂(split)的维度，即在哪一维数据上将原数据分为两半，有两种做法:
一是取当前层数nmod数据维数K:如第一层时，n=0，nmodK=0，即在第一维数据上寻找分裂点。
二是取方差最大的那维数据，即在各维数据上分别计算方差，方差最大者数据越分散，故在该维数据上寻找分裂点。
(2)在分裂维度上选择分裂点:通常是取该数据的中值点。
:(父)根结点p的分裂维split_dim=0，即在x维上分裂，第split_dim分量小于p[split_di