Spectral clustering: embed by the bottom eigenvectors, then k-means

The eigenvectors are the SMALLEST ones. Signs are fixed on the largest-magnitude entry and the k-means is initialised at the FIRST k embedded rows with a fixed sweep budget, so both arms agree. Under a repeated eigenvalue the eigenvectors are not unique; that is a property of the problem, not of the code.

Usage

Specclus(W, k = 2, normalized = TRUE, max_iter = 50)

Arguments

W

Symmetric non-negative similarity matrix.

k

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

normalized

Use the symmetric normalized Laplacian and row-normalize the embedding.

max_iter

k-means sweep budget.

Value

List with cluster, embedding, values, centers, tot_withinss, iterations, n, k.

Details

Formula: L = T - W (or L_sym = T^-1/2 L T^-1/2); U = the k eigenvectors of smallest eigenvalue; normalized: rows of U scaled to unit norm; cluster the rows of U by k-means

References

von Luxburg (2007), A Tutorial on Spectral Clustering, Statistics and Computing 17(4), 395-416. Lloyd (1982), IEEE Transactions on Information Theory 28(2), 129-137, for the k-means step.

Examples

set.seed(1)
W <- matrix(runif(36), 6, 6)
W <- (W + t(W)) / 2
diag(W) <- 0
Specclus(W, k = 2)
#> $cluster
#> [1] 2 2 2 2 1 1
#> 
#> $embedding
#>           [,1]        [,2]
#> [1,] 0.7867353 -0.61729050
#> [2,] 0.7278044 -0.68578475
#> [3,] 0.9978241 -0.06593254
#> [4,] 0.7713662 -0.63639151
#> [5,] 0.5288739  0.84870042
#> [6,] 0.6022556  0.79830331
#> 
#> $values
#> [1] 1.332268e-15 1.043595e+00
#> 
#> $centers
#>           [,1]       [,2]
#> [1,] 0.5655647  0.8235019
#> [2,] 0.8209325 -0.5013498
#> 
#> $tot_withinss
#> [1] 0.3028351
#> 
#> $iterations
#> [1] 4
#> 
#> $n
#> [1] 6
#> 
#> $k
#> [1] 2
#> 
#> $method
#> [1] "Spectral clustering, von Luxburg (2007)"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"