重庆理工大学学报（自然科学）

重庆理工大学学报（自然科学） ›› 2021, Vol. 35 ›› Issue (6): 147-155.doi: 10.3969/j.issn.1674-8425(z).2021.06.019

• 信息·计算机 • 上一篇    

一种基于数据空间自适应规则网格划分的 Ｓｋｄｔｒｅｅ最近邻算法

王荣秀１，王 波２   

  1. １．重庆工商大学 人工智能学院，重庆 ４０００６７； ２．重庆理工大学 理学院，重庆 ４０００５４
  • 收稿日期:2020-07-22 发布日期:2021-07-20
  • 作者简介:王荣秀，女，硕士，讲师，主要从事光电检测、机器学习研究，Ｅｍａｉｌ：ｗｒｘ＿００７＠ｃｔｂｕ．ｅｄｕ．ｃｎ。
  • 基金资助:
    重庆工商大学科研项目（１９５２０３６）

  • Received:2020-07-22 Published:2021-07-20

PDF (PC)

144

赞

摘要： 针对现有 ｋｄｔｒｅｅＫＮＮ算法的不足，提出了一种基于规则数据空间网格划分的 Ｓｋｄ ｔｒｅｅＫＮＮ算法。该树形结构把数据置于空间网格内部，能更好地利用数据的空间分布特性，可 以在更小的范围内对被查询数据定位，有效避免对部分无关数据的计算或回溯；同时，为了适应 网格空间的规则性，算法中采用了超方体而非超球体来查询局域空间中的最优结果，避免了空 间异构带来的缺点。数字实验的结果证明：ＳｋｄｔｒｅｅＫＮＮ比 ｋｄｔｒｅｅＫＮＮ具备更好的索引定位 精度、更少的无关数据回溯和计算、更短的查询时间，尤其适用于数据样本较大或高维度数据的 最近邻查询。

关键词: 最近邻算法, 数据索引, ＳｋｄｔｒｅｅＫＮＮ, 查询超体

中图分类号: 

  • TP311