使用环形过滤器的[K]值自适应KNN算法

来源：计算机工程与应用杂志2019年第23期北京时间：

作者：张万桢，刘同来，邬满，匡振曦

单位：1.桂林航天工业学院 实践教学部，广西 桂林 541004；2.广西密码学与信息安全重点实验室，广西 桂林 541004；3.广东工业大学 计算机学院，广州 510006；4.南宁师范大学 北部湾环境演变与资源利用教育部重点实验室，南宁 530001

摘要：针对传统KNN算法[K]值固定问题，提出基于环形过滤器的[K]值自适应KNN算法（K-value Adaptive KNN Algorithm Based on Annular Filter，AAKNN），其核心思想是利用稀疏向量能够较好地表达数据之间的相似度信息来动态选择每个测试点的[K]个最近邻点，从而提高算法的准确率。该算法不仅能够根据不同测试点的实际情况来选择不同的[K]值，而且利用环形过滤器避免了内存占用过大的问题。最后通过6组公开数据集对所提出的AAKNN算法进行了实验验证。实验结果表明，AAKNN与CM-KNN算法相比较于其余四种算法在准确率上平均提高2%，其中AAKNN算法相比较CM-KNN算法可以平均减少79%的内存消耗。

关键词：环形过滤器,聚类,分类,三角不等式,稀疏向量