一种高维向量空间K近邻快速搜索方法

作者：徐国天

来源：小型微型计算机系统, 2020, 41(11): 2274-2281.

• Ball-tree
• 双树
• KNN
• 高维空间
• 搜索

针对基于Ball-tree结构的KNN算法初始K个近邻点位置固定,导致剪枝半径过大,剪枝效果差,查询效率低的问题,本文提出一种基于"双树"结构的高维向量空间K近邻快速搜索方法.在训练阶段,将原始数据集按照8∶2比例划分为训练集和测试集,利用随机选择方法共生成10组训练和测试集合,通过统计分析,得到最优"双树"构造参数.利用最优参数从原始数据点集合中过滤出极少量数据点构成剪枝树,过滤剩余数据点构成被删树,剪枝树需要最大限度地保留原始数据点集合在高维空间的分布形态.在查询阶段,由于剪枝树内数据点个数很少,可以快速定位最近邻点,再利用这个近邻点作为被删树的初始近邻点,在被删树内搜索K近邻.实验结果表明,由于初始近邻点位置不再固定,而是位于待查点附近,有效缩小了剪枝半径,改善了剪枝效果,提升了K近邻查询效率.

• 单位
  中国刑事警察学院