Why spectral clustering results in disjointed cluster?

Question

I'm working on a project where I have to dynamically cluster the position of objects with respect to one coordinate. So I'm essentially dealing with subsequent frames and each frame represents a one-dimensional dataset. The intuition behind clustering is to form clusters out of points that are in similar distance to other points within the cluster and can be naturally connected. I use spectral clustering due to its ability to cluster points by their connectedness and not the absolute location and I set rbf kernel due to its non-linear transofrmation of distance. However, in some frames the algorithm results in unnatural assignments. One example is

import numpy as np
from sklearn.cluster import SpectralClustering

X = np.array([[51.08354988], [57.10594997], [70.51259995], [76.74425011], 
[61.24844971], [89.00615082], [98.55859985], [61.26575031], [88.35105019], 
[87.40859985]])

clustering = SpectralClustering(n_clusters = 4, random_state  = 42,
                                gamma = 5 / (X.max() - X.min()))
clustering.fit(X)

and the result of clustering is presented in a form of swarm plot below, so only x coordinate matters here (each color represents a cluster and labels are array indices):

What I cannot understand is why points marked as red are clustered together as the similarity between points {4, 7} and {5, 8, 9} should be really low. My first thought was that maybe this is caused by unlucky, random initialisation, but I tried with many different random states and the resulting clusters seems to be persistant. So I guess this is connected to the chosen affinity measure (rbf_kernel) and its gamma parameter. As points move with each frame, and distances between them are kind of dependent on their overall range, I tried to set gamma to 5 / (X.max() - X.min()). The intuition behind this was that if the range is bigger, then the distances between points are usually bigger and we should penalise them more to obtain similar values of exp(-gamma * ||x-y||^2) to those obtained within smaller range. But it doesn't seem to work as expected and results in faulty clustering where red cluster is formed out of points divided by green cluster). My expectation would be rather clusters formed as follows: {0, 1, 4, 7}, {2, 3}, {9, 8, 5} and {6} or {0}, {1, 4, 7}, {2, 3}, {5, 6, 8, 9}.

So my question are:

1. Is affinity choice and its gamma parameter really the problem here?

2. If so, how can I choose gamma better?

3. Otherwise, what approach should I consider to deal with faulty assignments with separated points within the same clusters as presented here?

4. (Side question) Is there any measure/index that would be suitable to automatically compare clusterings with different number of clusters?

@Edit: As it can be observed under this link, those separated clusters occurs for a short period of time, but still, the problem seems to be recurrent.

Answer 1

First, please note that spectral clustering is very sensitive to the affinity kernel. With the standard RBF kernel, my experience is that spectral clustering often isolates outliers (in the spectral space), leaving clusters with numerous observations which can be separated by great distances. This is a major difference with direct k-means: there is no notion of distance anymore, it's just about connectivity.

In the case shown in your example, the results are "strange" because of the low dimensionality: 1D is typically a case where spectral clustering does not provide "logical" results. In addition, you are quite unlucky on several aspects:

• The numbers of clusters (4): try it out with different numbers of clusters, and you will find more trivial results
• The positions of observations: move #0 to the left and you may find results that make more sense
• The low number of observations: #6 is not considered as an outlier, due to its vicinity to the #5, #8, #9 triplet. Indeed, the more points there are in an area, the largest its influence is. This is also how #4 and #7 can be considered part of the (#5, #6, #8, #9) cluster, rather than the (#2, #3) cluster. Try removing #9 and see how the results suddenly make sense.
• The chosen kernel (not tried on my side, but it is likely that the results may vary a lot if you increase the gamma value or change the kernel shape)

TL;DR: your case is an example of how spectral clustering can go wrong with low number of observations and dimensions.

Answer 2

Spectral clustering does not make sense on low dimensional data.

In fact, it will first project your data in a 4 dimensional embedding and then run k-means there. That is likely where this is behavior comes from.

I'd rather use the actual positions and a distance tolerance threshold.

Answer 3

I like your approach, but

you said I use spectral clustering due to its ability to cluster points by their affinities and not the exact position which is cool. (checkout Affinityprop also) BUT then you try to cluster with distance/position. If you wanted to make it reproducible try gamma=0 that should only measure distance.

One more note, these affinity based approaches are extremely expensive as data grows (Spectral time complexity is qubic+) I would advise against it unless you are playing with it on small(ish) datasets or you dont have some special approach in mind. For example spectral is designed for graph based problems originally.