A Max-Flow-Based Similarity Measure for Spectral Clustering

作者：Cao, Jiangzhong^*; Chen, Pei; Zheng, Yun; Dai, Qingyun

来源：ETRI Journal, 2013, 35(2): 311-320.

DOI：10.4218/etrij.13.0112.0520

• Spectral clustering
• maximum flow
• affinity graph
• similarity measure

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.

• 出版日期2013-4
• 单位中山大学; 广东工业大学