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
Tools
Sources (0)
Tags (0)
Comments (0)
History
Usage
Questions (0)
Playlists (0)
Quality
Sources
There are currently no sources for this slide.