基于对象数量的宽度加权聚类kNN算法

摘要

传统k最近邻算法(k-Nearest Neighbor,kNN)作为一种非参数化分类技术在数据分析中具有广泛的应用,但该算法具有较多的冗余计算,致使处理数据时需要花费较多的计算时间.目前大量的研究都集中在数据的预处理阶段,通过为数据建立模型降低kNN查询的计算量.提出一种基于对象数量的宽度加权聚类kNN算法(NOWCkNN),该算法中数据集首先以全局宽度进行聚类,每个生成的子集群根据其对象数量递归计算其宽度的权值,然后算法根据其权值的大小和调和系数调节宽度值,最后生成不同宽度大小的集群用于kNN查询.这不仅减少了算法的聚类时间,还能平衡产生集群的大小,减少迭代次数,使三角不等式修剪率达到最大.实验结果表明,NOWCkNN算法与现有工作相比在各个维度的数据集中有较好的性能,尤其是在高维度、数据量较大的数据集中有更高的修剪效率.