Ng-Jordan-Weiss k-way spectral clustering

Take the k eigenvectors of L_sym with the smallest eigenvalues, normalise each ROW of that n-by-k matrix to unit length, and run k-means on the rows. The row normalisation projects nodes onto the unit sphere, where well-separated blocks become mutually orthogonal directions rather than clusters of different radius.

Usage

Sgtsck(A, k = 2)

Arguments

A

Symmetric non-negative weight matrix, positive degrees.

k

Number of clusters, 1 <= k <= n.

Value

List with labels (0-based), eigvecs, eigvals, k, n.

Details

Formula: L_sym = I - D^-1/2 A D^-1/2; U = its k lowest eigenvectors; T_ij = U_ij / ||U_i||; k-means on rows of T.

References

Ng, A. Y., Jordan, M. I. & Weiss, Y. (2002). On spectral clustering: analysis and an algorithm. Advances in Neural Information Processing Systems 14, pages 849-856, MIT Press.

Examples

A <- matrix(c(4, 1, 0.5, 1, 3, 0.8, 0.5, 0.8, 2), nrow = 3)
res <- Sgtsck(A = A)
res
#> $labels
#> [1] 0 1 1
#> 
#> $eigvecs
#>           [,1]       [,2]
#> [1,] 0.6536833  0.7567682
#> [2,] 0.9071509 -0.4208055
#> [3,] 0.6232441 -0.7820273
#> 
#> $eigvals
#> [1] -2.787716e-17  4.441113e-01
#> 
#> $k
#> [1] 2
#> 
#> $n
#> [1] 3
#> 
#> $method
#> [1] "Ng-Jordan-Weiss k-way spectral clustering"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"