计算机科学 ›› 2017, Vol. 44 ›› Issue (Z6): 424-427.doi: 10.11896/j.issn.1002-137X.2017.6A.095

• 大数据与数据挖掘 • 上一篇    下一篇

改进的自适应谱聚类NJW算法

李金泽,徐喜荣,潘子琦,李晓杰   

  1. 大连理工大学计算机科学与技术学院 大连116024,大连理工大学计算机科学与技术学院 大连116024,大连理工大学计算机科学与技术学院 大连116024,大连理工大学计算机科学与技术学院 大连116024
  • 出版日期:2017-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受国家大学生创新创业训练项目(2016101410168)资助

Improved Adaptive Spectral Clustering NJW Algorithm

LI Jin-ze, XU Xi-rong, PAN Zi-qi and LI Xiao-jie   

  • Online:2017-12-01 Published:2018-12-01

摘要: 聚类算法是近年来国际上机器学习领域的一个新的研究热点。为了能在任意形状的样本空间上聚类,学者们提出了谱聚类和图论聚类等优秀的算法。首先介绍了图论聚类算法中的谱聚类经典NJW算法和NeiMu图论聚类算法的基本思路,提出了改进的自适应谱聚类NJW算法。提出的自适应NJW算法的优点在于无需调试参数,即可自动求出聚类个数,克服了经典NJW算法需要事先设置聚类个数且需反复调试参数δ才能得出数据分类结果的缺点。在UCI标准数据集及实测数据集上对自适应NJW算法与经典NJW算法、自适应NJW算法与NeiMu图论聚类算法进行了比较。实验结果表明,自适应NJW算法方便快捷,且具有较好的实用性。

关键词: 谱聚类,图论聚类,本征间隙

Abstract: Clustering algorithm is a new research hotspot in the field of machine learning in recent years.In order to cluster in the sample space of any shape,the scholars have put forward excellent algorithms such as spectral clustering and graph theory clustering.In this paper,we first introduced the basic idea of the classical NJW algorithm of graph theo-ry clustering algorithm and NeiMu algorithm,and then we gave a new algorithm named Improved adaptive spectral clustering NJW algorithm.This approach overcomes the shortcomings of the classical NJW algorithm,which needs to adjust the number of clusters in advance and needs to be repeated to obtain the data classification results.We compared the adaptive NJW algorithm with the classical NJW algorithm,the adaptive NJW algorithm and the NeiMu graph theory clustering algorithm on the UCI standard data set and the measured data set.The experimental results show that the adaptive NJW algorithm is convenient and well practicable.

Key words: Spectral clustering,Graph theory clustering,Intrinsic gap

[1] JAIN A,MURTY M,FLYNN P.Data clustering:A Review [J].ACM Computing Surveys,1999,31(3):264-323.
[2] 张亚平,杨明.一种基于密度敏感的自适应谱聚类算法[J].数学的实践与认识,2013,3(20):150-156.
[3] 王娜,李霞.基于监督信息特性的主动半监督谱聚类算法[J].电子学报,2010,38(1):172-176.
[4] 孔万增,孙志海,杨灿,等.基于本征间隙与正交特征向量的自动谱聚类[J].电子学报,2010,8(8):1880-1891.
[5] 应德全,应晓敏,叶继华.一种基于图论的聚类算法NeiMu[J].计算机工程与应用,2009,45(3):47-50.
[6] 钱云涛,赵荣椿,谢维信.鲁棒聚类—基于图论和目标函数的方法[J].电子学报,1998,26(2):91-94.
[7] 刘锁兰,王江涛,王建国,等.一种新的基于图论聚类的分割算法[J].计算机科学,2008,5(9):245-247.
[8] SHI J,MALIK J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):888-905.
[9] 蔡晓妍,戴冠中,杨黎斌.谱聚类算法综述[J].计算机科学,2008,35(7):14-18.
[10] FILIPPONEA M,CAMASTRAB F,MASULLIA F,et al.A sur-vey of kernel and spectral methods for clustering[J].Pattern Recognition,2008,41(1):176-190.
[11] LUXBURG U.A tutorial on spectral clustering[J].Statistics and Computing,2007,17(4):395-416.
[12] VERMA D,MEILA M.A comparison of spectral clustering algorithms:2003.UW CSE Tech nical report 03-05-01[R].2003.
[13] 卜德云,张道强.自适应谱聚类算法研究[J].山东大学学报,2009,39(5):22-39.
[14] ZHAO F,JIAO L C,LIU H Q,et al.Spectral Clustering with Eigenvector Selection Based on Entropy anking[J].Neurocomputing,2010,73(10-12):1704-1717.
[15] 赵凤,焦李成,刘汉强,等.半监督谱聚类特征向量选择算法[J].模式识别与人工智能,2011,24(1):48-56.
[16] ZELNIK-MANOR L,PERONA P.Self-Tuning Spectral Clustering[C]∥Proc of Advances in Neural Information Processing Systems 17.Vancouver,Canada,2004:1601-1608.
[17] NGA Y,JORDAN M I,WEISS Y.On spectral clustering:Ana-lysis and an algorithm[C]∥Proceedings of the 14th Advances in Neural Information Processing Systems (NIPS 2002).Cambri-dge,MIT Press, 2002:849-856.
[18] ZELNIK M L,PERONA P.Self-tuning spectral clustering[C]∥Advances in Neural Information Processing Systems(NIPS).Cambridge,MA:MIT Press,2004.
[19] 孙继广.矩阵扰动分析[M].北京:科学出版社,2001:146-160.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!