主动纠错式半监督聚类社区发现算法  

Active error-correcting community discovery algorithm based on semi-supervised clustering

作　　者：张贤坤[1] 刘渊博[1] 任静 张高祯 Zhang Xiankun;Liu Yuanbo;Ren Jing;Zhang Gaozhen(School of Computer Science & Information Engineering,Tianjin University of Science & Technology,Tianjin 300457,China)

机构地区：[1]天津科技大学计算机科学与信息工程学院

出　　处：《计算机应用研究》2019年第9期2631-2635,2660,共6页Application Research of Computers

基　　金：国家自然科学基金资助项目(61702367);天津市教委科研计划资助项目(2017KJ033)

摘　　要：经典的无监督聚类算法快速、简单且可以直接对大规模数据集进行划分,但是由于网络结构较为复杂,划分的准确度并不高。为此,提出一种基于主动学习的纠错式半监督社区发现算法ESCD(error correction semisupervised community detection algorithm),将传统的K-means算法进行分步计算,并且在聚类的过程中加入成对约束。根据先验信息保留正确的划分,纠正错误的划分来改变网络的连接关系,使网络具有更明显的块结构,当节点与聚类中心的距离不再变化时划分结束。实验结果表明,与现有的社区发现算法相比,ESCD算法具有更高的精度,且所需的监督信息远远小于其他半监督算法。The classical unsupervised clustering algorithm is fast, simple and suitable for mining large-scale datasets, and it can also directly divide communities. However, due to the complexity of communities, the classification accuracy of the algorithm is not ideal. Therefore, this paper proposed an error- correcting semi-supervised community detection algorithm (ESCD) based on active learning. It can calculate the traditional K-means algorithm step by step, and adding pairs of constraints in the clustering process. In order to preserve the correct partitioning according to the prior information, it corrected the wrong division to change the connection of the network. So that the network has a more obvious block structure in the process of changing the distance between nodes and cluster centers. The results of the experiment show that compared with the existing community discovery algorithms, the ESCD algorithm has higher accuracy with less supervisory information than other semi-supervised algorithms.

关 键 词：主动学习 纠错式半监督社区发现 K-MEANS算法 成对约束 

分 类 号：TP391[自动化与计算机技术—计算机应用技术] TP301.6[自动化与计算机技术—计算机科学与技术]