[1]LI Jianyuan,ZHOU Jiaogen,GUAN Jihong,et al.A survey of clustering algorithms based on spectra of graphs[J].CAAI Transactions on Intelligent Systems,2011,6(5):405-414.
Copy

A survey of clustering algorithms based on spectra of graphs

References:
[1]LLOYD S P. Least squares quantization in PCM[J]. IEEE Transactions on Information Theory, 1982, 28(2): 129137. 
[2]DEMPSTER A P, LAIRD N M, RUBIN D B. Maximum likelihood from incomplete data via the EM algorithm[J]. Journal of the Royal Statistical Society—Series B: Statistical Methodology, 1977, 39(1): 138.
[3]NG A Y, JORDAN M I, WEISS Y. On spectral clustering: analysis and an algorithm[C]//PIETTERICH T G, BECKER S, GHAHRAMANI Z. Advances in Neural Information Processing Systems. Cambridge, USA: MIT Press, 2001: 849856.
[4]RAHIMI A, RECHT B. Clustering with normalized cuts is clustering with a hyperplane[C]//Statistical Learning in Computer Vision Workshop in ECCV 2004. Prague, Czech Republic, 2004: 112.
[5]SHI J B, MALIK J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888905.
[6]MALIK J, BELONGIE S, LEUNG T, et al. Contour and texture analysis for image segmentation[J]. International Journal of Computer Vision, 2001, 43(1): 727.
[7]ZHANG X R, JIAO L C, LIU F. Spectral clustering ensemble applied to SAR image segmentation[J]. IEEE Transactions on Geoscience and Remote Sensing, 2008, 46(7): 21262136.
[8]陶文兵,金海.一种新的基于图谱理论的图像阈值分割方法[J].计算机学报, 2007, 30(1): 110119.
?TAO Wenbing, JIN Hai. A new image thresholding method based on graph spectral theory[J]. Journal of Computers, 2007, 30(1): 110119.
[9]ALPERT C J, KAHNG A B. Multiway partitioning via geometric embeddings, orderings and dynamic programming[J]. IEEE Transactions on ComputerAaided Design of Integrated Circuits and Systems, 1995, 14(11): 13421358.
[10]DRIESSCHE R V, ROOSE D. An improved spectral bisection algorithm and its application to dynamic load balancing[J]. Parallel Computing, 1995, 21(1): 2948.
[11]HENDRICKSON B, LELAND R. An improved spectral graph partitioning algorithm for mapping parallel computations[J]. SIAM Journal on Scientific Computing, 1995, 16(2): 452459.
[12]CRISTIANINI N, SHAWETAYLOR J, KANDOLA J. Spectral kernel methods for clustering[C]//Proceedings of the Neural Information Processing Systems. Vancouver, Canada, 2001: 649655.
[13]KLUGER Y, BASRI R, CHANG J T, et al. Spectral biclustering of microarray data: coclustering genes and conditions[J]. Genome Research, 2003, 13(4): 703716.
[14]KULIS B, BASU S, DHILLON I S, et al. Semisupervised graph clustering: a kernel approach[C]//International Conference on Machine Learning. New York, USA: ACM Press, 2005: 457464.
[15]PACCANARO A, CHENNUBHOTLA C, CASBON J A. Spectral clustering of protein sequences[J]. Nucleic Acids Research, 2006, 34(5): 15711580.
[16]DHILLON I S. Coclustering documents and words using bipartite spectral graph partitioning[C]//Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM Press, 2001: 269274.
[17]谢永康,周雅倩,黄萱菁.一种基于谱聚类的共指消解方法[J].中文信息学报, 2009, 23(3): 1016.
XIE Yongkang, ZHOU Yaqian, HUANG Xuanjing. A spectral clustering based coreference resolution method[J]. Journal of Chinese Information Processing, 2009, 23(3): 1016.
[18]ALPERT C J, YAO S Z. Spectral partitioning: the more eigenvectors, the better[C]//Proceedings of the 32nd Annual ACM/IEEE Design Automation Conference. New York, USA: ACM, 1995: 195200.
[19]ZELNIKMANOR L, PERONA P. Selftuning spectral clustering[C]//Neural Information Processing Systems. Vancouver, Canada, 2004, 2: 16011608.
[20]NING Huazhong, XU Wei, CHI Yun, et al. Incremental spectral clustering with application to monitoring of evolving blog communities[C]//Proceedings of the SIAM International Conference on Data Mining. Minneapolis, USA, 2007: 261272.
[21]ALZATE C, SUYKENS J A K. Multiway spectral clustering with outofsample extensions through weighted kernel PCA[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(2): 335347.
[22]YU S X, SHI J B. Grouping with bias[C]//The Fifteenth Annual Conference on Neural Information Processing Systems. Vancouver, Canada, 2001: 13271334.
[23]KANNAN R, VEMPALA S, VETTA A. On clusterings: good, bad, and spectral[J]. Journal of the ACM, 2004, 51(3): 497515.
[24]SONG Yangqiu, CHEN Wenyen, BAI Hongjie, et al. Parallel spectral clustering[C]//European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases. Antwerp, Belgium, 2008: 374389.
[25]VERMA D, MEILA M. A comparison of spectral clustering algorithms, Technical Report UWCSE030501[R]. Seattle, USA: Department of CSE, University of Washington, 2003.
[26]LUXBURG U, BELKIN M, BOUSQUET O. Consistency of spectral clustering[J]. Annals of Statistics, 2008, 36(2): 555586.
[27]FILIPPONE M, CAMASTRA F, MASULLI F, et al. A survey of kernel and spectral methods for clustering[J]. Pattern Recognition, 2008, 41(1): 176190.
[28]蔡晓妍,戴冠中,杨黎斌.谱聚类算法综述[J].计算机科学, 2008, 35(7): 1417.
CAI Xiaoyan, DAI Guanzhong, YANG Libin. Survey on spectral clustering algorithms[J]. Computer Science, 2008, 35(7): 1417.
[29]DIESTEL R. Graph theory[M]. 4th ed. Heidelberg, Germany: SpringerVerlag, 2010.
[30]FIEDLER M. Algebraic connectivity of graphs[J]. Czechoslovak Mathematical Journal, 1973, 23(98): 298305.
[31]DONATH W E, HOFFMAN A J. Lower bounds for the partitioning of graphs[J]. IBM Journal of Research and Development, 1973, 17(5): 420425.
[32]BAMES E R. An algorithm for partitioning the nodes of a graph[J]. SIAM Journal on Algebraic and Discrete Methods, 1982, 17(5): 541550.
[33]DONATH W E. Logic partitioning[M]//PREAS B T, LORENZETTI M J. Physical Design Automation of VLSI Systems. [S.l.]: Benjamin/Cummings Pub Co, 1988: 6586.
[34]BIGGS N L. Algebraic graph theory[M]. Cambridge, USA: Cambridge University Press, 1974.
[35]BROUWER A E, HAEMERS W H. Spectra of graphs[EB/OL]. [20101005]. http://homepages.cwi.nl/~aeb/math/ipm.pdf.
[36]CHUNG F. Spectral graph theory[EB/OL]. [2010-10-05]. http://www.ams.org/mathscinetgetitem?mr=1421568.
[37]MOHAR B. The Laplacian spectrum of graphs[M]//ALAVI Y, CHARTRAND G, OELLERMANN O R, et al. Graph Theory, Combinatorics, and Applications. [S.l.]: Wiley, 1991, 2: 871898.
[38]MOHAR B. Some applications of Laplace eigenvalues of graphs[J]. Graph Symmetry: Algebraic Methods and Applications, 1997, 497(22): 227275.
[39]LUXBURG U. A tutorial on spectral clustering[J]. Statistics and Computing, 2007, 17(4): 395416.
[40]WEI Y C, CHENG C K. Toward efficient hierarchical designs by ratio cut partitioning[C]//IEEE International Conference on CAD. New York, USA, 1989: 298301.
[41]BARNARD S, POTHEN A, SIMON H.A spectral algorithm for envelope reduction of sparse matrices[J]. Numerical Linear Algebra with Applications, 1995, 2(4): 317334.
[42]GUATTERY S, MILLER G L. On the quality of spectral separators[J]. SIAM Journal on Matrix Analysis and Applications, 1998, 19(3): 701719.
[43]WEISS Y. Segmentation using eigenvectors: a unifying view[C]//Proceedings of the Seventh IEEE International Conference on Computer Vision. Washington, DC, USA: IEEE Computer Society, 1999: 975982.
[44]HIGHAM D, KIBBLE M. A unified view of spectral clustering[EB/OL]. [2010-10-05]. http://meyer.math.ncsu.edu/Meyer/Courses/Selee591RPresentation.pdf, 2007.
[45]MEILA M, SHI J B. Learning segmentation by random walks[C]//LEEN T K, DIETTERICH T G, TRESP V. Advances in Neural Information Processing Systems. Cambridge, USA: MIT Press, 2001: 873879.
[46]NEWMAN M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E, 2006, 74(3): 036104.
[47]NEWMAN M E J. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences of the United States, 2006, 103(23): 85778582.
[48]NEWMAN M E J. Analysis of weighted networks[J]. Physical Review E, 2004, 70(5): 056131.
[49]LEICHT E A, NEWMAN M E J. Community structure in directed networks[J]. Physical Review Letters, 2008, 100(11): 118703.
[50]ZAHN C T. Graphtheoretic methods for detecting and describing gestalt clusters[J]. IEEE Transactions on Computers, 1971, 20(1): 6886.
[51]URQUHART R. Graph theoretical clustering based on limited neighborhood sets[J]. Pattern Recognition, 1982, 15(3): 173187.
[52]WAGNER D, WAGNER F. Between mincut and graph bisection[J]. Lecture Notes in Computer Science, 1993, 711: 744750.
[53]WU Z, LEAHY R. An optimal graph theoretic approach to data clustering: theory and its application to image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993, 15(11): 11011113.
[54]CHAN P K, SCHLAG M D F, ZIEN J Y. Spectral kway ratiocut partitioning and clustering[J]. IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, 1994, 13(9): 10881096.
[55]WEI Y C, CHENG C K. A twolevel twoway partitioning algorithm[C]//IEEE International Conference on CAD. Santa Clara, USA, 1990: 516519.
[56]HAGEN L, ANDREW B K. New spectral methods for ratio cut partitioning and clustering[J]. IEEE Transactions on ComputerAided Design of Intergrated Circuits and Systems, 1992, 11(9): 10741085.
[57]YU S, SHI J B. Multiclass spectral clustering[C]//Proceedings of the Ninth IEEE International Conference on Computer Vision. Nice, France, 2003, 2: 313319.
[58]DING C, HE X, ZHA H, et al. A minmax cut algorithm for graph partitioning and data clustering[C]//Proceedings of the 2001 IEEE International Conference on Data Mining. Washington, DC, USA: IEEE Computer Society, 2001: 107114.
[59]SARKAR S, SOUNDARARAJAN P. Supervised learning of large perceptual organization: graph spectral partitioning and learning automata[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(5): 504525.
[60]ZHA Hongyuan, HE Xiaofeng, DING C H Q, et al. Spectral relaxation for kmeans clustering[C]//DIETTERICH T G, BECKER S, GHAHRAMANI Z. Advances in Neural Information Processing Systems. Cambridge, USA: MIT Press, 2002, 14: 10571064.
[61]WU Z, LEAHY R. Tissue classification in MR images using hierarchical segmentation[C]//1990 IEEE Nuclear Science Symposium Conference Record, Including Sessions on Nuclear Power Systems and Medical Imaging Conference. Piscataway, USA: IEEE Service Center, 1990: 14101414.
[62]FORD L R, FULKERSON D R. Flows in networks[M]. Princeton, USA: Princeton University Press, 1962.
[63]DHILLON I S, KULIS Y B. A unified view of kernel kmeans, spectral clustering and graph partitioning, UTCS Technical Report #TR0425[R]. Austin, USA: Department of Computer Science, The University of Texas at Austin, 2005.
[64]DHILLON I S, GUAN Y, KULIS B. Kernel kmeans: spectral clustering and normalized cuts[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM Press, 2004: 551556.
[65]JEBARA T, WANG J, CHANG S. Graph construction and bmatching for semisupervised learning[C]//Proceedings of the 26th Annual International Conference on Machine Learning. New York, USA: ACM, 2009: 441448.
[66]DAITCH S I, KELNER J A, SPIELMAN D A. Fitting a graph to vector data[C]// Proceedings of the 26th Annual International Conference on Machine Learning. New York, USA: ACM, 2009: 201208.
[67]XUE F, KUMAR P R. The number of neighbors needed for connectivity of wireless networks[J]. Wireless Networks, 2004, 10(2): 169181.
[68]BALISTER P, BOLLOBAS B, SARKAR A, et al. Connectivity of random knearestneighbour graphs[J]. Advances in Applied Probability, 2005, 37(1): 124. 
[69]BRITO M R, CHFIVEZ E L, QUIROZ A J, et al. Connectivity of the mutual knearestneighbor graph in clustering and outlier detection[J]. Statistics & Probability Letters, 1997, 35(1): 3342. 
[70]POLITO M, PERONA P. Grouping and dimensionality reduction by locally linear embedding[C]// DIETTERICH T G, BECKER S, GHAHRAMANI Z. Advances in Neural Information Processing Systems. Cambridge, USA: MIT Press, 2001: 12551262.
[71]田铮,李小斌,句彦伟.谱聚类的扰动分析[J].中国科学E辑:信息科学, 2007, 37(4): 527543.
?TIAN Zheng, LI Xiaobin, JU Yanwei. Perturbation analysis of spectral clustering[J]. Science in China Series E: Technological Sciences, 2007, 37(4): 527543.
[72]HERNANDEZ V, ROMAN J, TOMAS A, et al. A survey of software for sparse eigenvalue problems[EB/OL]. [20101005]. http://www.grycap.upv.es/slepc/documentation/reports/str6.pdf.
[73]FOWLKES C, BELONGIE S, CHUNG F, et al. Spectral grouping using the Nystrom method[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(2): 214225. 
[74]DHILLON I S, GUAN Y, KULIS B. Weighted graph cuts without eigenvectors: a multilevel approach[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(11): 19441957.
[75]YAN D H, HUANG L, JORDAN M I. Fast approximate spectral clustering[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM Press, 2009: 907915.
[76]MASCHHOFF K J, SORENSEN D C. A portable implementation of ARPACK for distributed memory parallel architectures[EB/OL]. [20101005]. http://www.caam.rice.edu/_kristyn/parpack home.html.
[77]BACH F R, JORDAN M I. Learning spectral clustering, Technical Report No.UCB/CSD031249[R]. Berkeley, USA: Computer Science Division, University of California, 2003.
[78]王玲,薄列峰,焦李成.密度敏感的半监督谱聚类[J].软件学报, 2007, 18 (10): 24122422.
WANG Ling, BO Liefeng, JIAO Licheng. Densitysensitive semisupervised spectral clustering[J]. Journal of Software, 2007, 18(10): 24122422. 
[79]KAMVAR S D, KLEIN D, MANNING C D. Spectral learning[C]//Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Acapulco, Mexico, 2003: 561566.
[80]FISCHER I, POLAND I. New methods for spectral clustering, Technical Report No.IDSIA1204[R]. Manno, Switzerland: Dalle Molle Institute for Artificial Intelligence, 2004.
[81]ROWEIS S, SAUL L. Nonlinear dimensionality reduction by locally linear embedding[J]. Science, 2000, 290(5550): 23232326.
[82] CHENG B, YANG J, YAN S, et al. Learning with L1graph for image analysis[J]. IEEE Transactions on Image Processing, 2010, 19(4): 858866.
Similar References:

Memo

-

Last Update: 2011-11-16

Copyright © CAAI Transactions on Intelligent Systems