Current Slide

• Given a set of objects o1, …, on, and the distance between each pair of objects, dist(oi, oj), find the desired number k of clusters
• Calculate an affinity matrix W, where σ is a scaling parameter that controls how fast the affinity Wij decreases as dist(oi, oj) increases. In NJW, set Wij = 0

\[D_{ii}=\sum_{j=1}^{n}W_{ij}\]

• Derive a matrix A = f(W). NJW defines a matrix D to be a diagonal matrix s.t. Dii is the sum of the i-th row of W, i.e.,

\[W_{ij}=e^{-\frac{dist(o_{i},o_{j})}{\sigma^{2}}}\]

• Then, A is set to

\[A=D^{-\frac{1}{2}}WD^{-\frac{1}{2}}\]

• A spectral clustering method finds the k leading eigenvectors of A
• A vector v is an eigenvector of matrix A if Av = λv, where λ is the corresponding eigen-value
• Using the k leading eigenvectors, project the original data into the new space defined by the k leading eigenvectors, and run a clustering algorithm, such as k-means, to find k clusters
• Assign the original data points to clusters according to how the transformed points are assigned in the clusters obtained