Computer Science ›› 2018, Vol. 45 ›› Issue (5): 196-200.doi: 10.11896/j.issn.1002-137X.2018.05.033

Previous Articles     Next Articles

KNN Similarity Graph Algorithm Based on Heap and Neighborhood Coexistence

WANG Ying and YANG Yu-wang   

  • Online:2018-05-15 Published:2018-07-25

Abstract: In the spectral clustering algorithm,the construction of similarity graph is very important,which has a great impact on the clustering results and operation efficiency of algorithm.In order to speed up the operation of spectral clustering and improve the performance by nearest neighbor truncation,K nearest neighbor(KNN) method is usually used to construct the sparse similarity graph.But the K nearest neighbor graph is very sensitive to outliers in the data,and the noise will seriously affect the clustering performance.This paper presented a new efficient sparse affinity graph construction method HCKNN.In this method,the K nearest neighbor search based on heap is more efficient than the nearest neighbor selection process based on sort by log(n),and the sparse similarity matrix reduction based on the neighborhood coexistence cumulative threshold can not only remove the noise to enhance the performance of clustering,but also accelerate the eigenvector decomposition in spectral clustering.This paper proposed a new efficient method HCKNN for constructing sparse affinity graph based on heap and the information of two points in the same neighborhood,which can not only choose the neighbors more efficiently,but also can accelerate the spectral clustering because of the sparse matrix.

Key words: Spectral clustering,Similarity graph,Heap,Sparse k nearest neighborhood

[1] SBALZARINI I F,MLLER S,KOUMOUTSAKOS P.Mul-tiobjective optimization using evolutionary algorithms[C]∥Summer Program.CiteSeer,2001:63-74.
[2] HUGHES E J.Evolutionary many-objective optimisation:many once or one many?[C]∥The 2005 IEEE Congress on Evo-lutionary Computation,2005.IEEE,2005:222-227.
[3] ZHANG Q,LI H.MOEA/D:A Multiobjective Evolutionary Algorithm Based on Decomposition[J].IEEE Transactions on Evolutionary Computation,2008,11(6):712-731.
[4] LI Y L,ZHOU Y R,ZHAN Z H,et al.A Primary Theoretical Study on Decomposition-Based Multiobjective Evolutionary Algorithms[J].IEEE Transactions on Evolutionary Computation,2016,20(4):563-576.
[5] ZHAO S Z,SUGANTHAN P N,ZHANG Q.Decomposition-Based Multiobjective Evolutionary Algorithm With an Ensemble of Neighborhood Sizes[J].IEEE Transactions on Evolutionary Computation,2012,16(3):442-446.
[6] LI H,DING M,DENG J,et al.On the use of random weights in MOEA/D[C]∥Evolutionary Computation.IEEE,2015:978-985.
[7] CHENG R,JIN Y,OLHOFER M,et al.A Reference Vector Guided Evolutionary Algorithm for Many-Objective Optimization[J].IEEE Transactions on Evolutionary Computation,2016,20(5):773-791.
[8] XIE C W,DING L X.Study on Selection Strategies of Multiobjective Evolutionary Algorithms [J].Computer Science,2009,36(9):167-172.(in Chinese) 谢承旺,丁立新.多目标进化算法中选择策略的研究[J].计算机科学,2009,36(9):167-172.
[9] ZHENG J H,ZHANG Z F,ZOU J.An adaptive multi-objective evolutionary algorithm directed by objective space decomposition[J].Chinese High Technology Letters,2013,23(7):671-678.(in Chinese) 郑金华,张作峰,邹娟.基于目标空间分解的自适应多目标进化算法[J].高技术通讯,2013,23(7):671-678.
[10] WANG Z,ZHANG Q,GONG M,et al.A replacement strategy for balancing convergence and diversity in MOEA/D[C]∥IEEE Congress on Evolutionary Computation.IEEE,2014:2132-2139.
[11] LI K,ZHANG Q,KWONG S,et al.Stable Matching-Based Selection in Evolutionary Multiobjective Optimization[J].IEEE Transactions on Evolutionary Computation,2014,18(6):909-923.
[12] WANG Z,ZHANG Q,ZHOU A,et al.Adaptive ReplacementStrategies for MOEA/D[J].IEEE Transactions on Cybernetics,2015,46(2):474-486.
[13] MUNKRES J.Algorithms for the Assignment and Transportation Problems[J].Journal of the Society for Industrial & Applied Mathematics,1957,5(1):32-38.
[14] ZHANG Q,ZHOU A,ZHAO S,et al.Multiobjective optimization Test Instances for the CEC 2009 Special Session and Competition[J/OL].
[15] LI H,ZHANG Q.Multiobjective Optimization Problems WithComplicated Pareto Sets,MOEA/D and NSGA-II[J].IEEE Transactions on Evolutionary Computation,2009,13(2):284-302.
[16] HUBAND S,BARONE L,WHILE L,et al.A Scalable Multi-objective Test Problem Toolkit[C]∥ EMO.2005:280-295.
[17] DEB K,THIELE L,LAUMANNS M,et al.Scalable Test Problems for Evolutionary Multiobjective Optimization[M]∥Evolutionary Multiobjective Optimizatio.2005:105-145.
[18] ZHANG Q,LIU W,LI H.The performance of a new version of moea/d on cec09 unconstrained mop test instances[C]∥ Evolutionary Multiobjective,2009.IEEE,2009:203-208.
[19] GENG H T,ZHAO Y G,CHEN Z,et al.Multi-objective Particle Swarm Optimization Algorithm with Balancing Each Speed Coefficient[J].Computer Science,2016,43(12):248-254.(in Chinese) 耿焕同,赵亚光,陈哲,等.一种均衡各速度项系数的多目标粒子群优化算法[J].计算机科学,2016,43(12):248-254.
[20] DEB K,PRATAP A,AGARWAL S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.

No related articles found!
Full text



[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[3] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[4] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[5] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[6] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[7] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[8] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[9] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[10] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .