How to Find Boundaries in Data: A Simple Way to See Groups ✎

Original: "A New Spectral Clustering Algorithm"

arXiv:1710.02756 · 2017-10-07 · arXiv non-exclusive · independent analysis · 1 min

Machine Learning Computer Vision Geophysics

The SP-MGM algorithm finds groups in data by analyzing sharp changes in special waves that describe connections between objects.

Imagine a river that separates two banks. On one bank live some people, on the other, others. The boundary between them is visible where the river's current changes sharply. The SP-MGM algorithm looks for such abrupt changes in data to figure out where one group ends and another begins.

To find boundaries, the algorithm builds special waves that describe how objects are connected. If two groups are weakly linked, the wave changes sharply at the boundary between them. The algorithm finds the largest change and draws the boundary right there. This way, it decides on its own how many groups there should be, without needing that number to be specified in advance.

Instead of deciding in advance how many groups the data should have, the algorithm looks at the data itself and finds natural gaps in it. It's like cutting a cake along the lines that are already there, rather than along pre-marked ones.

The algorithm was tested on sea surface temperature data. It found seven distinct states of El Niño and La Niña. This helps better understand how different types of this phenomenon affect weather. Such a method could also be useful in other areas, for example, for finding communities in social networks.

Whole graph →

The SP-MGM algorithm almost always outputs exactly m+1 clusters for m eigenmodes, although theoretically there could be up to $2^m$. This points to a deep connection between gaps in eigenvectors and graph structure.

The idea of finding hidden structures by gaps in data recalls the analysis of 'patterns' in William Gibson's novel 'Pattern Recognition', where the protagonist intuitively finds anomalies in video streams. The algorithm formalizes such a search for graphs.

L = I - D^{-1/2} A D^{-1/2}

A matrix describing graph connectivity; its eigenvectors encode cluster structure.

A_{ij} = \exp(-d_{ij}^2 / (2\sigma))

Similarity matrix entries decrease as the distance between objects increases.

\max_{i \neq m} \frac{(n_i - 1) \rho_1}{\lambda_{i,2}} < \frac{1}{4 n_m^{1/2}}

If inter-cluster connections are weak relative to intra-cluster connectivity, the algorithm is guaranteed to find clusters.

Concepts

clustering nonlinear laplacian spectral analysis k means clustering climate network least squares ensemble forecast spectral pattern ENSO pattern recognition El Niño index cls method neural networks matched filtering Multivariate ENSO Index cross correlation El Niño-Southern Oscillation signal stacking classification least squares fitting neural network polarimetry

I am the author

How to Find Boundaries in Data: A Simple Way to See Groups ✎