一种近似的K最近邻图算法

Approximate algorithm based on k-nearest neighbor graph

针对K最近邻(KNN)图方法在数据挖掘和机器学习方面的问题,文中提出一种高效的基于K最近邻图的近似算法.首先随机生成一个KNN图近似值;对空间进行随意层次划分,构建一个近似近邻图,然后与KNN图近似值合并生成一个更准确的图;最后对生成的更准确的图进行近邻传播,进一步提高准确度.通过采用各种真实数据集和高维度合成数据进行实验研究,证实文中提出的算法性能优于先进的KNN图构造方法.

In view of the k-nearest neighbor（ KNN） graph problems in data mining and machine learning,an efficient approximate algorithm is proposed based on the k-nearest neighbor graph. First,a random graph KNN approximation is generated; the space is divided at random level to construct an approximate nearest neighbor graph,and then approximate KNN value map they are combined to build a more accurate map; finally,neighbor propagation of the more accurate nearest neighbor graph further improves the accuracy. Experiments are performed by using real data sets and high-dimensional synthetic data,and the result shows that the proposed algorithm has better performance than the advanced KNN method.