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

Algorithm of KNNS based on angular similarity

作　　者：余小高[1] 余小鹏[2,3] 

机构地区：[1]湖北经济学院,武汉430205 [2]武汉工程大学,武汉430073 [3]武汉大学信息资源研究中心,武汉430072

出　　处：《计算机应用研究》2009年第9期3296-3299,共4页Application Research of Computers

基　　金：湖北省教育厅资助项目(2008d095;D20081902)

摘　　要：k-最近邻搜索(KNNS)在高维空间中应用非常广泛,但目前很多KNNS算法是基于欧氏距离对数据进行索引和搜索,不适合采用角相似性的应用。提出一种基于角相似性的k-最近邻搜索算法(BA-KNNS)。该算法先提出基于角相似性的数据索引结构(BA-Index),参照一条中心线和一条参照线,将数据以系列壳—超圆锥体方式进行组织并分别线性存储;然后确定查询对象的空间位置,有效确定一个以从原点到查询对象的直线为中心线的超圆锥体并在其中进行搜索。实验结果表明,BA-KNNS算法较其他k-最近邻搜索算法有更好的性能。The KNNS is widely used in the high dimension space. However, the current KNNS uses Euclidean distance to index dataset and retrieve the target object, which is not suitable for those applications based on angular similarity. This paper proposed the angular similarity based on KNNS （BA-KNNS）. BA-KNNS firstly proposed that the indexing structure should be based on angular similarity, refered to a center line and a referenced line to organize dataset with the method of the shell- hy- percone, and stored them linearly. Then it determined the space place for the target object, making a hypercone which took the line connecting the origin point and the target object as center, and searched the hypercone for the target. The experiment shows that the performance of BA-KNNS is superior to those other KNNS.

关 键 词：k-最近邻搜索 数据分割 角相似性 壳-超圆锥体 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]