Spectral clustering result interpretation

Question

I cluster a toy data set into three groups with spectral clustering. Please see the code below. affinity='rbf' by default.

from sklearn.cluster import SpectralClustering 
import numpy as np

points = np.array([[5,6], [3,3], [2,2], [7,3], [8,3], [5,4], [5,5], [9,3], [7,1]]) 

spectral = SpectralClustering(n_clusters=3) 
labels = spectral.fit(points).labels_

The output is three clusters with labels [1 2 2 0 0 1 1 0 2] shown on the image. Why point 8 happens to be in the same cluster with 1 and 2, not with points 3,4, and 7?

UPDATE:

Affinity matrix:

Spectral embedding result:

Answer 1

Supposedly because of the weighting / normalization.

Point 8 is fairly far from all it's neighbors, so it's edges have a similar weight; and the normalization increases the edge weight to give every point the same influence. It's two other cluster members are (except they have one neighbor) similar. So I wouldn't be surprised if the two strongest edges after normalization of 8 are to 1 and 2.

To understand this better, I suggest that you compute the affinity matrix and visualize the affinities as edge strengths. The spectral embedding may also be worth looking at.

But this is an interesting example about the drawbacks of spectral clustering: normalization may give too much weight on "outliers".