Spectral clustering: Difference between revisions

Revision as of 19:57, 8 March 2022

Revision as of 22:11, 8 March 2022

Line 34:

===[[Cluster analysis]] via Spectral Embedding===

Knowing the eigenvectors, partitioning may be done in various ways, such as <math>n</math>-by computing the median -<math>mk</math> of the components of the second smallest eigenvectormatrix <math>vV</math> of selected eigenvectors, andmapping placing— allcalled pointsspectral whoseembedding component— inof the original <math>vn</math> data points is greaterperformed to thana <math>mk</math>-dimensional invector <math>B_1</math>,space andusing the restrows inof <math>B_2V</math>. TheNow algorithmthe cananalysis beis usedreduced for [[hierarchicalto clustering]] byvectors repeatedlywith partitioning<math>k</math> thecomponents, subsetswhich may be done in thisvarious fashionways.

In the simplest case <math>k=1</math>, the selected single eigenvector <math>v</math>, called the [[Fiedler vector]], corresponds to the second smallest eigenvalue. Using the components of <math>v,</math> one can place all points whose component in <math>v</math> is positive in the set <math>B_+</math> and the rest in <math>B_-</math>, thus bi-partitioning the graph and labeling the data points with two labels. This sign-based approach follows the intuitive explanation of spectral clustering via the mass-spring model — in the low frequency vibration mode that the [[Fiedler vector]] <math>v</math> represents, one cluster data points identified with mutually strongly connected masses would move together in one direction, while in the complement cluster data points identified with remaining masses would move together in the opposite direction. The algorithm can be used for [[hierarchical clustering]] by repeatedly partitioning the subsets in the same fashion.

In the general case <math>k>1</math>, any vector clustering technique can be used, e.g., [[DBSCAN]].

== Algorithms ==