一种基于角相似性的k-最近邻搜索算法

减小字体 增大字体 作者:余小高 余小鹏  来源:www.zhonghualunwen.com  发布时间:2009-10-12 23:30:16

  0 引言
  
  KNNS在文本分类[1]、推荐系统[2]、时间序列分析[3]等应用中有很大的用途,该方法对密度估计和分类都很有效。最简单的k-最近邻搜索算法需要计算一个查询对象p(d维矢量)到所有其他训练样本之间的距离,其总的计算复杂度为O((dn)2)[4]。人们为了降低复杂度,进行了大量的研究。在众多的算法中,数据分割方法应用比较广泛[4~8]。该类方法的思路有共同之处,即先对数据进行索引组织,然后再将查询空间确定在一个以查询点p为中心、以r为半径的d-超球(或超立方体)内进行,查询代价为数据组织代价和查询代价之和,但是这些方法对r值的研究不深。虽然有效设定r是很不错的方法,但却很难并且是非自觉能决定的[9],r设置大了会导致搜索代价大,设置小了会导致很多空查询[10]。文献 [9]是在假设数据集统一服从已知分布的情况下进行研究的,很明显这不切实际。文献[10]也是假设在分布已知的情况下对超球半径进行估计,并允许半径以一个步长变量rinc逐步递增。由于分布未知,不能在假定的情况下对超球半径进行估计;同时,如果数据样本很复杂,稀疏很不均匀,半径递增由于缺乏指导要么导致不必要的搜索(包括空搜索)数量,要么导致包含过多的样本而增加计算复杂度,也即rinc是很难适合全部样本的。在文献[4]的研究中,rinc从0增加到1.1以上时效果才明显。文献[8]提出iDistance方法,但它也是预测确定一个最大半径超球和固定步长的迭代的方法。文献[11]是先采用SA-Tree组织数据集,然后再用MinMax剪枝和局部MinDist剪枝方法,其实质也是预测查询超球的半径。
  对于高效率的查询处理,索引支持是非常重要的。尽管目前的研究在一定程度上能有效提高k-最近邻搜索效率,但是其所采用的数据索引结构基本上都是以欧氏距离为相似性度量函数[12],不适合使用角相似性的应用。前者是在一个超球内进行搜索,而后者的搜索只能在一个超圆锥体内进行。角相似性度量函数(如cosine)并不满足度量函数的三角不等式。
  由于几何上的不匹配和特征空间的高维性,对于采用角相似性的文本分类、时间序列分析、推荐系统等应用来说,M-Trees存储方式也是不可取的[13]。当前的技术要么不适用,要么性能低劣,虽然可以将数据集规范化到欧氏空间,但那样会增大维数,导致检索更加困难[12]。虽然文献[12]也提出了基于角相似性的k-最近邻搜索的思路(CS_KNNS),但其计算复杂度偏大。因此,本文提出一种基于角相似性的k-最近邻搜索算法(BA-KNNS),它也属于数据分割方法。
  
  1 相关研究
  
  1.1 KNNS搜索算法简介
  KNNS也就是从数据集中找出查询对象的k个最近邻居,其定义如下:
  定义1 设数据集S={xi|1≤i≤n},xi=[xi1,xi2,…,xid]。其中:n为样本总数,d为数据元素的维数。给定任意样本xi和度量函数D,xi的k(k<  p∈S′|h∈S-S′:D(xi,y)≤D(xi,h)(1)
  最简单的KNNS需要计算一个查询点xi到所有其他训练样本之间的距离,然后对距离值进行排序得到其k个最近邻居。为了缩小查询范围,提高效率,常用的KNNS算法是从给定查询点xi为中心、半径相对比较小的一个超球体内开始搜索;然后采用一个迭代方法,逐步扩充半径,直到超球半径超过或等于最小半径rmin为止,此时该超球至少包含k个最近邻居。可以发现,对于比较小的r,该算法的复杂度会随d增长很慢。在很多的模式识别问题中,这个特性是充分的,当然r不可能假设为已知的[3]。
     定义2 最小半径rmin。xi的第k个最近邻居到xi的距离为D(xi,neighbork),也就是以xi为中心、包含k个最近邻居的最小超球半径。
  1.2 相似性度量
  在KNNS算法中,相似性度量是一个重要概念,其实质上是一个相似性度量函数。在度量空间S中,相似性度量函数D应满足S×S→非负实数,使得任意的x1,x2,x3∈S同时满足如下条件:
  a)非负性。D(x1,x2)≥0,并且D(x1,x2)=0,当且仅当x1=x2。
  b)对称性。D(x1,x2)=D(x2,x1)。
  c)三角不等式。D(x1,x2)+D(x1,x3)≥D(x2,x3)。
  狭义上讲,满足度量的三个条件的函数才能被称为相似性度量函数,如欧氏距离函数(Euclidean)。
  D(xi,xj)=∑dl=1(xil-xjl)2(2)
  但是广义上也将许多常用的、不满足三角不等式条件的度量函数作为相似性度量函数。角相似性度量函数就是其中之一。
  在高维空间中,角相似性度量就是用向量之间的夹角来衡量它们的相似性。在应用中往往使用夹角的余弦值来表示夹角,也可以说是通常所说的余弦相似性函数等,如式(3)所示。
  D(xi,xj)=(∑dl=1(xil×xjl))/(‖xi‖×‖xj‖)(3)
  
  2 BA-KNNS算法
  
  2.1 分析
  目前KNNS研究基本上都是使用欧氏距离函数对数据进行索引和查找的。而很多应用,如文本分类、时间序列分析和推荐系统等都是根据角相似性进行k-最近邻查找,这使得目前的研究基本上不适用。如果依然使用当前的方法,则会导致精确度或性能低下。如图1所示,如果采用欧氏距离,则在以查询对象p为中心的超球内就可以查询到其k(k=8)个最近邻居;如果采用角相似性函数,则不能在超球内进行查询了,只能在一个超圆锥体内进行查询,否则必然导致图中p的邻居p1、p2、p3等数据丢失。
  根据以上分析,在常用研究不适用的情况下,研究高效率的基于角相似性的k-最近邻搜索算法是非常必要的。
  2.2 关键思路
  对于高效率的查询处理,索引支持非常重要。BA-KNNS首先提出索引结构(BA-Index),将数据按照一定的索引结构进行组织,然后确定查询对象的存储位置以及查询范围,最后在该范围内进行搜索。
  2.2.1 索引结构
  定义3 查询超圆锥体HyperCone(p,θ),简称HC,也就是数据对象p的k-最近邻搜索空间,即以原点为顶点、从原点到数据对象p的直线为中心线,以2θ为圆锥角的一个超空间几何体,如图2(a)所示。

[1] [2] [3]  下一页

Tags:

作者:余小高 余小鹏
  • 好的评价 如果您觉得此文章好,就请您
      0%(0)
  • 差的评价 如果您觉得此文章差,就请您
      0%(0)

文章评论评论内容只代表网友观点,与本站立场无关!

   评论摘要(共 0 条,得分 0 分,平均 0 分) 查看完整评论