Self-tuning Spectral Clustering

The choice of the kernel size $\sigma$ in (3) has a high impact on the clustering quality. It is a measure of when two points are considered similar, and should be of the same order of the distance between similar points. Some rules of thumb have been proposed to set a value for $\sigma$ , whereas in other cases this value is set manually.

When the data contains clusters with different local statistics, there may not be a single value of $\sigma$ that works well for all the data. In [12] a ``local'' scaling parameter $\sigma_i$ is proposed instead of this global parameter. It allows self-tuning of the point-to-point distances by studying the local statistics of the neightboring points of every point $\textbf{x}_i$ . This leads to the following extension of (3):

$$\tilde{\kappa}(\textbf{x}[i],\textbf{x}[j]) = \exp\left(-\frac{d^2(\textbf{x}[i],\textbf{x}[j])}{\sigma_i \sigma_j}\right).$$ (4)

If $\sigma_i$ is chosen as

$$\sigma_i = d(\textbf{x}_i,\textbf{x}_L)$$ (5)

where $\textbf{x}_L$ is the L'th nearest neighbor of point $\textbf{x}_i$ , then spectral clustering will group together all points with their closest neighbors that have similar $\sigma_i$ . The selection of $L$ only depends on the data dimension of the embedding space.