Spectral Clustering

Definition

Spectral clustering technique make use of spectrum of the similarity matrix of the data to perform dimensionality reduction before clustering.

Algorithms

Apply Laplacian Eigenmap to the given data ${\mathbf{x}}_1,{\mathbf{x}}_2,\dots ,{\mathbf{x}}_n\in {\mathbb{R}}^l$. ${\mathbf{x}}_i\in {\mathbb{R}}^l\to [{\mathbf{z}}_2,{\mathbf{z}}_3,\dots ,{\mathbf{z}}_m{]}_i\in {\mathbb{R}}^m$

Form an $n\times k$ sub matrix $\mathbf{T}$ using the first $k$-columns of the embedded matrix $\mathbf{Z}$, and normalize each row to norm $1$. $\mathbf{T}=[{\mathbf{z}}_1,{\mathbf{z}}_2,\dots ,{\mathbf{z}}_k]$

Apply clustering algorithm (e.g. K-Means Clustering) to ${\mathbf{t}}_1,{\mathbf{t}}_2,\dots ,{\mathbf{t}}_n$, where ${\mathbf{t}}_i$ is the $i$-th row of $\mathbf{T}$.

Mathematical Background

Consider a cluster assignment vector ${\mathbf{z}}_i$ for each data point. Then, clustering $n$ observations is corresponding to estimating ${\mathbf{z}}_i$‘s The entries $a_{ij}$ of the Adjacency Matrix represents the similarity between points $i$ and $j$.

Under the assumption that the close data points (large $a_{ij}$) have a similar label (${\mathbf{z}}_i\approx {\mathbf{z}}_j$), the optimization problem is set up that minimizing the difference between assignments for similar points. $\underset{\mathbf{Z}}{\mathrm{argmin}}\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{a}_{ij}({\mathbf{z}}_i-{\mathbf{z}}_j{)}^2\text{subject to}{\mathbf{Z}}^{⊺}\mathbf{Z}=I$ where the constraint is imposed to avoid the trivial solution ${\mathbf{z}}_i=0$.

In a matrix notation, the problem is $\underset{\mathbf{Z}}{\mathrm{argmin}}\mathrm{tr}({\mathbf{Z}}^{⊺}\mathbf{LZ})\text{subject to}{\mathbf{Z}}^{⊺}\mathbf{Z}=I$

When ${\mathbf{z}}_i\approx {\mathbf{z}}_j$, $a_{ij}$ is large and when ${\mathbf{z}}_i\ne {\mathbf{z}}_j$, $a_{ij}$ is small. So, $a_{ij}$ works as the weight for each pair in the optimization.

The Lagrangian function is defined as $L_P={\mathbf{Z}}^{⊺}\mathbf{LZ}-\Lambda ({\mathbf{Z}}^{⊺}\mathbf{Z}-1)$ And the solution of the problem is given by an Eigenvalue problem. $\frac{\partial L_p}{\partial \mathbf{Z}}=2\mathbf{LZ}-2\Lambda \mathbf{Z}=0\Rightarrow \mathbf{LZ}=\Lambda \mathbf{Z}\Rightarrow {\mathbf{Z}}^{⊺}\mathbf{LZ}=\Lambda$ The solution $\mathbf{Z}$ is an $n\times n$ matrix of eigenvectors sorted in ascending by their corresponding eigenvalues.