Open AccessA Max‐Flow‐Based Similarity Measure for Spectral Clustering
Author(s) -
Cao Jiangzhong,
Chen Pei,
Zheng Yun,
Dai Qingyun
Publication year - 2013
Publication title -
etri journal
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.295
H-Index - 46
eISSN - 2233-7326
pISSN - 1225-6463
DOI - 10.4218/etrij.13.0112.0520
Subject(s) - spectral clustering , similarity measure , similarity (geometry) , cluster analysis , pattern recognition (psychology) , mathematics , measure (data warehouse) , kernel (algebra) , artificial intelligence , data mining , computer science , combinatorics , image (mathematics)
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.