第5期 李建元，等：谱图聚类算法研究进展 ·413· 1421568. [53]WU Z,LEAHY R.An optimal graph theoretic approach to [37]MOHAR B.The Laplacian spectrum of graphs M]// data clustering:theory and its application to image seg- ALAVI Y,CHARTRAND G,OELLERMANN O R,et al. mentation[J].IEEE Transactions on Pattern Analysis and Graph Theory,Combinatorics,and Applications.[S. Machine Intelligence,1993,15(11):1101-1113. 1.]:Wiey,1991,2:871-898. [54]CHAN P K,SCHLAG M D F,ZIEN J Y.Spectral k-way [38]MOHAR B.Some applications of Laplace eigenvalues of ratio-cut partitioning and clustering[J].IEEE Transactions graphs[J].Graph Symmetry:Algebraic Methods and Ap- on Computer-Aided Design of Integrated Circuits and Sys- plications,1997,497(22):227-275. tems,1994,13(9):1088-1096. [39]LUXBURG U.A tutorial on spectral clustering[J].Statis- [55]WEI Y C,CHENG C K.A two-level two-way partitioning tics and Computing,2007,17(4):395-416. algorithm[C]//IEEE International Conference on CAD. [40]WEI Y C,CHENG C K.Toward efficient hierarchical de- Santa Clara.USA,1990:516-519. signs by ratio cut partitioning [C]//IEEE International [56]HAGEN L,ANDREW B K.New spectral methods for ratio Conference on CAD.New York,USA,1989:298-301. cut partitioning and clustering[J].IEEE Transactions on [41]BARNARD S,POTHEN A,SIMON H.A spectral algo- Computer-Aided Design of Intergrated Circuits and Sys- rithm for envelope reduction of sparse matrices[J].Nu- tems,1992,11(9):1074-1085. merical Linear Algebra with Applications,1995,2(4): [57]YU S,SHI J B.Multiclass spectral clustering[C]//Pro- 317-334. ceedings of the Ninth IEEE International Conference on [42]GUATTERY S,MILLER G L.On the quality of spectral Computer Vision.Nice,France,2003,2:313-319. separators[J].SIAM Joumal on Matrix Analysis and Ap- [58]DING C,HE X,ZHA H,et al.A min-max cut algorithm plications,1998,19(3):701-719. for graph partitioning and data clustering[C]//Proceedings [43]WEISS Y.Segmentation using eigenvectors:a unifying of the 2001 IEEE International Conference on Data Min- view[C]//Proceedings of the Seventh IEEE International ing.Washington,DC,USA:IEEE Computer Society, Conference on Computer Vision.Washington,DC,USA: 2001:107-114. IEEE Computer Society,1999:975-982. [59]SARKAR S,SOUNDARARAJAN P.Supervised learning [44]HIGHAM D,KIBBLE M.A unified view of spectral clustering of large perceptual organization:graph spectral partitioning [EB/OL].[2010-10-05].http://meyer.math.ncsu.edu/Mey- and learning automata[J].IEEE Transactions on Pattern er/Courses/Selee591RPresentation.pdf,2007. Analysis and Machine Intelligence,2000,22 (5):504- 45]MEILA M,SHI J B.Learing segmentation by random 525. walks[C]//LEEN T K,DIETTERICH T G,TRESP V. [60]ZHA Hongyuan,HE Xiaofeng,DING C H Q,et al.Spec- Advances in Neural Information Processing Systems.Cam- tral relaxation for k-means clustering[C]//DIETTERICH bridge,USA:MIT Press,2001:873-879. T G,BECKER S,GHAHRAMANI Z.Advances in Neural [46]NEWMAN M E J.Finding community structure in net- Information Processing Systems.Cambridge,USA:MIT works using the eigenvectors of matrices[J].Physical Re- Pres8,2002,14:1057-1064. view E,2006,74(3):036104. [61]WU Z,LEAHY R.Tissue classification in MR images u- [47]NEWMAN M E J.Modularity and community structure in sing hierarchical segmentation [C]//1990 IEEE Nuclear networks[J].Proceedings of the National Academy of Sci- Science Symposium Conference Record,Including Sessions ences of the United States,2006,103(23):8577-8582. on Nuclear Power Systems and Medical Imaging Confer- [48 NEWMAN M E J.Analysis of weighted networks [J]. ence.Piscataway,USA:IEEE Service Center,1990: Physical Review E,2004,70(5):056131. 1410-1414. [49]LEICHT E A,NEWMAN M E J.Community structure in [62]FORD L R,FULKERSON D R.Flows in networks[M]. directed networks J].Physical Review Letters,2008, Princeton,USA:Princeton University Press,1962. 100(11):118703. [63]DHILLON I S,KULIS Y B.A unified view of kemel k- 50]ZAHN C T.Graph-theoretic methods for detecting and de- means,spectral clustering and graph partitioning,UTCS scribing gestalt clusters[J].IEEE Transactions on Com- Technical Report #TR-04-25[R].Austin,USA:Depart- puters,1971,20(1):68-86. ment of Computer Science,The University of Texas at Aus- [51]URQUHART R.Graph theoretical clustering based on lim- tin,2005. ited neighborhood sets[J].Pattern Recognition,1982,15 [64 DHILLON I S,GUAN Y,KULIS B.Kemel k-means: (3):173-187. spectral clustering and normalized cuts[C]//ACM SIGK- 52]WAGNER D,WAGNER F.Between mincut and graph bi- DD International Conference on Knowledge Discovery and section[J].Lecture Notes in Computer Science,1993, Data Mining.New York,USA:ACM Press,2004:551- 711:744-750 556