基于聚类的环形kNN算法

计算机工程与科学

基于聚类的环形kNN算法

匡振曦，武继刚，李嘉兴

（广东工业大学计算机学院,广东广州 510006）

收稿日期:2018-11-15 修回日期:2019-02-28 出版日期:2019-05-25 发布日期:2019-05-25
基金资助:
国家自然科学基金（61672171,61702115,61702114）；广东省自然科学基金重点项目(2018B030311007)

A clustering-based annular k-nearest neighbor algorithm

KUANG Zhenxi，WU Jigang，LI Jiaxing

（School of Computers,Guangdong University of Technology,Guangzhou 510006,China）

Received:2018-11-15 Revised:2019-02-28 Online:2019-05-25 Published:2019-05-25

摘要/Abstract

摘要：

传统k最近邻算法kNN在数据分类中具有广泛的应用，但该算法具有较多的冗余计算，致使处理高维数据时花费较多的计算时间。同时，基于地标点谱聚类的分类算法（LCkNN和RCkNN）中距离当前测试点的最近邻点存在部分缺失，导致其准确率降低。针对上述问题，提出一种基于聚类的环形k最近邻算法。提出的算法在聚类算法的基础上，首先将训练集中相似度较高的数据点聚成一个簇，然后以当前测试点为中心设置一个环形过滤器，最后通过kNN算法对过滤器中的点进行分类，其中聚类算法可以根据实际情况自由选择。算法性能已在UCI数据库中6组公开数据集上进行了实验测试，实验结果表明：AkNNE与AkNNH算法比kNN算法在计算量上平均减少51%，而在准确率上比LCkNN和RCkNN算法平均提高3%。此外，当数据在10 000维的情况下该算法仍然有效。

关键词: 环形过滤器, 聚类, 分类, 相邻簇心组, 三角不等式

Abstract:

The traditional knearest neighbor (kNN) algorithm has been widely used in data classification, but its redundant distance computation consumes much time for highdimensional data processing. Meanwhile, for the classification algorithms based on landmarkbased spectral clustering (LCkNN and RCkNN), the nearest neighbor points of the current testing point are partially missing, which results in low accuracy. Aiming at the above problems, we propose a clusteringbased annular knearest neighbor algorithm (AkNN). Based on the traditional clustering algorithm, the proposed algorithm collects data points with high similarity in the training set into a cluster. Then an annular filter centered on the testing point is set. Finally, the points in the filter are classified by the kNN algorithm. We can choose a clustering algorithm freely according to practical needs. The performance of the proposed algorithm is tested on 6 open data sets in the UCI database. Experimental results show that the AkNNE and AkNNH algorithms reduce calculation by 51% on average compared with the kNN algorithm, and enhance the accuracy by 3% on average compared with the LC-kNN and RC-kNN algorithms. In addition, the proposed algorithm is still valid in 10000 dimensional datasets.

Key words: annular filter, clustering, classification, neighboring centroid, triangle inequality

匡振曦，武继刚，李嘉兴. 基于聚类的环形kNN算法[J]. 计算机工程与科学.

KUANG Zhenxi，WU Jigang，LI Jiaxing. A clustering-based annular k-nearest neighbor algorithm[J]. Computer Engineering & Science.

[1]	柴燕涛，董德尊，张鹤颖，朱成阳，廖湘科. 基于SDN架构的高性能网络拥塞避免策略[J]. J4, 20160101, 38(01): 1-10.
[2]	柴旭清, 乔一航, 范黎林, . 一种基于随机森林分类器构建高性能应用程序性能分析模型的方法[J]. 计算机工程与科学, 2024, 46(07): 1218-1228.
[3]	黄智慧, 肖祥立, 张玉书, 薛明富. 基于隐形后门水印的开源数据集版权保护[J]. 计算机工程与科学, 2024, 46(06): 1013-1021.
[4]	肖新正, 黄瑞章, 陈艳平, 秦永彬, 宋玉梅, 周裕林, . Corrective-Net：面向多标签文本分类的标签关联学习模块[J]. 计算机工程与科学, 2024, 46(06): 1092-1100.
[5]	佟缘, 姚念民. 基于对span的预判断和多轮分类的实体关系抽取[J]. 计算机工程与科学, 2024, 46(05): 916-928.
[6]	刘盼, 郭延明, 雷军, 王昊冉, 老松杨, 李国辉. 结合上下文的细粒度实体分类特征表示方法[J]. 计算机工程与科学, 2024, 46(05): 929-936.
[7]	高珊, 李世杰, 蔡志平. 基于深度学习的中文文本分类综述[J]. 计算机工程与科学, 2024, 46(04): 684-692.
[8]	罗月童, 李超, 周波, 张延孔. 面向工业缺陷分类的交互式易混淆缺陷分离方法研究[J]. 计算机工程与科学, 2024, 46(03): 463-470.
[9]	吕伏, 韩晓天, 冯永安, 项梁. 基于自适应纹理特征融合的纹理图像分类方法[J]. 计算机工程与科学, 2024, 46(03): 488-498.
[10]	张远洋, 贡正仙, 孔芳. 增强依存结构表达的零样本跨语言事件论元角色分类[J]. 计算机工程与科学, 2024, 46(03): 508-517.
[11]	宋鑫海, 韩京宇, 郎杭, 毛毅. 滑动窗口投票策略的QRS波群形态识别[J]. 计算机工程与科学, 2024, 46(02): 272-281.
[12]	钟卓辉, 陈黎飞, . 基于模型的非凸聚类算法[J]. 计算机工程与科学, 2024, 46(02): 292-302.
[13]	庞诺言, 关东海, 袁伟伟. 基于早期时间序列分类的可解释实时机动识别算法[J]. 计算机工程与科学, 2024, 46(02): 353-362.
[14]	马雪, 何星星, 兰咏琪, 李莹芳. 一阶逻辑中基于treelet图神经网络的前提选择[J]. 计算机工程与科学, 2024, 46(02): 374-380.
[15]	肖振国, 陈林书, 孙少杰, 梅本霞, 柳媛慧, 赵磊. 基于代数粒的聚类方法[J]. 计算机工程与科学, 2024, 46(01): 150-158.