| Title | On affinity matrix normalization for graph cuts and spectral clustering |
| |
| Author | Beauchemin, M |
| Source | Pattern Recognition Letters vol. 68, pt. 1, 2015 p. 90-96, https://doi.org/10.1016/j.patrec.2015.08.020 |
| Year | 2015 |
| Alt Series | Earth Sciences Sector, Contribution Series 20120406 |
| Publisher | Elsevier BV |
| Document | serial |
| Lang. | English |
| Media | paper; on-line; digital |
| File format | pdf |
| Program | Remote Sensing Science |
| Released | 2015 09 03 |
| Abstract | Graph-based spectral clustering algorithms involve the analysis of an affinity matrix. The latter defines the pairwise similarity relations among data points. Popular graph partitioning algorithms
typically involve a normalization step that reflects itself onto an affinity matrix normalization step in spectral clustering algorithms. In this paper, we show that affinity matrix normalization with constant row/column sum guarantees the invariance
of the size-weighted sum of the between- and within-cluster graph association; a property conceptually equivalent to the data variance decomposition exploited by the standard k-means algorithm. From this observation, we demonstrate that the solution
of numerous spectral clustering methods can be obtained using the standard graph ratio cut objective function. We have identified in the literature 7 such affinity matrix normalization schemes relevant to spectral clustering. Clustering experiments
performed with these 7 normalization schemes on 17 benchmark datasets are presented. As a general rule, it is observed that the appropriate normalization method depends on the dataset. A geometric interpretation in the feature space (FS) of such a
normalization scheme for k-way spectral clustering is also presented. |
| GEOSCAN ID | 292235 |
|
|