Spectral Clustering

In order to perform spectral clustering, we should know graph Laplacian first
 
Once we convert any data into a transfered domain noted by eigenvectors, we can make them clustered
 
Thus we should know how to transfer feature domain using eigen vector.
 
Spectral clustering:
 
1. Generate graph Laplacian expression
 
2. Transfer data domain using eigen vector
 
3. Graph notation and graph cut
 
============================================================


 <Short Note>
In order to cluster given data which might be difficult to do in given domain,
we can transform given data into other domain described by eigenvector calculation.
Then we can easily perform k-means clustering that could have not been possible in the original domain.
This is called spectral clustering

In the field of machine learning, graph Laplacians are useful for many tasks such as semi-supervised learning, clustering, and manifold reconstruction.
Graph Laplacians has the assumption that data points that are close should have similar label, thereby having small f'Lf value.



 <Algorithm>

1. Form a Similarity graph.

There are several popular graph notation to transform given data points into a graph.
Primary goal of a graph notation is to model the local neighborhood relationship between data points.

(1) The ε-neighborhood graph
(2) k-nearest neighbor graph
(3) The fully connected graph

2. Define D to the diagonal matrix whose (i,i)-element is the sum of W’s i-th row, and construct the Laplacian matrix L

(1). Unnormalized graph Laplacian
L=D-W
(2). Normalized graph Laplacian

L=D^(-1/2) LD^(-1/2)

  =I - D^(-1/2) WD^(-1/2)

 

There are many properties of the unnormalized graph Laplacian L.The main thing is that the unnormalized graph Laplacian and its eigenvalues and eigenvectors can be used to describe many properties of graphs.

  3. Find k eigenvector of graph Laplacian L
and form the matrix X=[x_1,x_2, …,x_k ]∈R^(n×k) by stacking the eigenvectors in columns
(2). Form the matrix Y from X by renormalizing each of X^′ s rows to have unit length
– Ng, Jordan, and Weiss (2002)
Refer "On spectral clustering: Analysis and an algorithm - Andrew Ng, et al"

Note: When we talk about eigenvectors of a matrix, we do not necessarily assume that they are normalized to norm 1.
For example, the constant vector 1 and a multiple a1 for some a 6= 0 are considered as the same eigenvectors. Eigenvalues will always be ordered increasingly, respecting multiplicities. By “the first k eigenvectors” we refer to the eigenvectors corresponding to the k smallest eigenvalues.


4. K-means clustering


 < Graph cut point of view>

1. Graph notation and graph cut
In fact, the intuition of clustering is to separate points in different groups according to their similarities.
This problem can be restated; we want to find a partition of the graph that the edges between different groups have low weight and that the edges within a group have high weight.
So we can regard this problem as an approximation to such graph partitioning problems.

 In RatioCut, the size of a subset A of a graph is measured by its number of vertices.
So it restricts the number of vertices from having too large value nor too small value.
In particular, the minimum of this function(1) is achieved if all numbers of Ai are same.
So what the objective function try to achieve is that the clusters are “balanced”, and it is also true for Normalized Cut.
Unfortunately, introducing balancing conditions makes the simple-to-solve mincut problem becomes NP hard. That’s what spectral clustering try to solve.



 <Details and applications>