Spectral clustering
One of the most common problems of K-means and other similar algorithms is the assumption we have only hyperspherical clusters. This condition can be acceptable when the dataset is split into blobs that can be easily embedded into a regular geometric structure. However, it fails whenever the sets are not separable using regular shapes. Let's consider, for example, the following bidimensional dataset:
Sinusoidal dataset
As we are going to see in the example, any attempt to separate the upper sinusoid from the lower one using K-means will fail. The reason is quite obvious: a circle that contains the upper set will also contain part of the (or the whole) lower set. Considering the criterion adopted by K-means and imposing two clusters, the inertia will be minimized by a vertical separation corresponding to about x0 = 0. Therefore, the resulting clusters are completely mixed and only a dimension is contributing to the final configuration. However, the two sinusoidal sets are...
