Current Slide

Small screen detected. You are viewing the mobile version of SlideWiki. If you wish to edit slides you will need to use a larger device.

Spectral Clustering: The Ng-Jordan-Weiss (NJW) Algorithm

  • 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

Speaker notes:

Content Tools

Sources

There are currently no sources for this slide.