A Max-Flow-Based Similarity Measure for Spectral Clustering

ETRI Journal

关键词: similarity measure;    affinity graph;    maximum flow;    Spectral clustering;   

Others  :  1196751
DOI  :  10.4218/etrij.13.0112.0520

【 摘 要 】

In most spectral clustering approaches, the Gaussian kernel-based similarity measure is used to construct the affinity matrix. However, such a similarity measure does not work well on a dataset with a nonlinear and elongated structure. In this paper, we present a new similarity measure to deal with the nonlinearity issue. The maximum flow between data points is computed as the new similarity, which can satisfy the requirement for similarity in the clustering method. Additionally, the new similarity carries the global and local relations between data. We apply it to spectral clustering and compare the proposed similarity measure with other state-of-the-art methods on both synthetic and real-world data. The experiment results show the superiority of the new similarity: 1) The max-flow-based similarity measure can significantly improve the performance of spectral clustering; 2) It is robust and not sensitive to the parameters.

   

【 参考文献 】

• [1]C. Alzate and J.A.K Suykens, "Multiway Spectral Clustering with Out-of-Sample Extensions through Weighted Dernel PCA," IEEE Trans. Pattern Anal. Mach. Intell., vol. 32, no. 2, 2010, pp. 335-347.
• [2]T.H. Kim, K.M. Lee, and S.U. Lee, "Learning Full Pairwise Affinities for Spectral Segmentation," CVPR, 2010, pp. 2101-2108.
• [3]M. Li et al., "Time and Space Efficient Spectral Clustering via Column Sampling," CVPR, 2011, pp. 2297-2304.
• [4]K. Jain, "Data Clustering: 50 Years beyond K-Means," Pattern Recog. Lett., vol. 31, 2010, pp. 651-666.
• [5]J.B. Shi and J. Malik, "Normalized Cuts and Image Segmentation," IEEE Trans. Pattern Anal. Mach. Intell. vol. 22, no. 8, 2000, pp. 888-905.
• [6]K. Ersahin, I.G. Cumming, and R.K. Ward, "Segmentation and Classification of Polarimetric SAR Data Using Spectral Graph Partitioning," IEEE Trans. Geosci. Remote Sensing, vol. 48, no. 1, 2010, 164-174.
• [7]C.J. Alpert, A.B. Kahng, and S.Z. Yao, "Spectral Partitioning with Multiple Eigenvectors," Discrete Appl. Mathematics, vol. 90, no. 1-3, 1999, pp. 3-26.
• [8]F.R. Bach and M.I. Jordan, "Learning Spectral Clustering, with Application to Speech Separation," J. Mach. Learn. Res. vol. 7, 2006, pp. 1963-2001.
• [9]F.R. Bach and M.I. Jordan, "Spectral Clustering for Speech Separation," Automatic Speech and Speaker Recognition: Large Margin and Kernel Methods, J. Keshet and S. Bengio, Eds., New York: John Wiley & Sons, Inc., 2008, pp. 221-250.
• [10]T. Xia et al., "On Defining Affinity Graph for Spectral Clustering through Ranking on Manifolds," Neurocomputing, vol. 72, 2009, pp. 3203-3211.
• [11]A.Y. Ng, M.I. Jordan, and Y. Weiss, "On Spectral Clustering: Analysis and an Algorithm," NIPS, 2001, pp. 849-856.
• [12]L. Zelnik-Manor and P. Perona, "Self-Tuning Spectral Clustering," NIPS, 2004, pp. 1601-1608.
• [13]X. Zhang, J. Li, and H. Yu, "Local Density Adaptive Similarity Measurement for Spectral Clustering," Pattern Recog. Lett., vol. 32, no. 2, 2011, pp. 352-358.
• [14]H. Chang and D.Y. Yeung, "Robust Path-Based Spectral Clustering," Pattern Recog., vol. 41, no. 1, 2008, pp. 191-203.
• [15]U. Luxburg, "A Tutorial on Spectral Clustering, Statistics Computing," vol. 17, no. 4, 2007, pp. 395-416.
• [16]I. Fischer and J. Poland, "Amplifying the Block Matrix Structure for Spectral Clustering," Proc. 14th Annual Mach. Learning Conf. Belgium Netherlands, pp. 21-28.
• [17]B. Fischer and J.M. Buhmann, "Path-Based Clustering for Grouping of Smooth Curves and Texture Segmentation," IEEE Trans. Pattern Anal. Mach. Intell., vol. 25, no. 4, 2003, pp. 513-518.
• [18]B. Fischer, T. Zöller, and J.M. Buhmann, "Path Based Pairwise Data Clustering with Application to Texture Segmentation," Proc. 3rd Int. Workshop Energy Minimization Methods Computer Vision Pattern Recog., Sophia Antipolis, France, 2001, pp. 235-250.
• [19]L. Yen et al., "Clustering Using a Random Walk Based Distance Measure," ESANN, 2005.
• [20]U. Luxburg and A. Radl, "Getting Lost in Space: Large Sample Analysis of the Commute Distance," NIPS, 2010, pp. 153-160.
• [21]F. Fouss et al., "Random-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation," IEEE Trans. Knowl. Data Eng., vol. 19, no. 3, 2007, pp. 355-369.
• [22]M. Ester et al., "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise," KDD, 1996, pp. 226-231.
• [23]L.R. Ford, Sr., and E. Fulkerson, Flows in Networks, Princeton, NJ: Princeton University Press, 1962.
• [24]Y. Boykov and V. Kolmogorov, "An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision," IEEE Trans. Pattern Anal. Mach. Intell., vol. 26, no. 9, 2004, pp. 1124-1137.
• [25]Z. Li et al., "Noise Robust Spectral Clustering," ICCV, 2007, pp. 1-8.
• [26]D.B. Graham and N.M. Allinson, "Characterizing Virtual Eigensignatures for General Purpose Face Recognition," Face Recognition: From Theory to Applications, H. Wechsler et al., Eds., NATO ASI Series: Series F: Computer and Systems Sciences, vol. 163, 1998, pp. 446-456.
• [27]Yale Face Database. http://cvc.yale.edu/