-
Notifications
You must be signed in to change notification settings - Fork 0
/
specclust.m
60 lines (49 loc) · 1.72 KB
/
specclust.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
function [C, L, U] = SpectralClustering(W, k)
% Executes the spectral clustering algorithm defined by
% Type on the adjacency matrix W and returns the k cluster
% indicator vectors as columns in C.
% If L and U are also called, the (normalized) Laplacian and
% eigenvectors will also be returned.
%
% 'W' - Adjacency matrix, needs to be square
% 'k' - Number of clusters to look for
% 'Type' - Defines the type of spectral clustering algorithm
% that should be used. Choices are:
% 1 - Unnormalized
% 2 - Normalized according to Shi and Malik (2000)
% 3 - Normalized according to Jordan and Weiss (2002)
%
% References:
% - Ulrike von Luxburg, "A Tutorial on Spectral Clustering",
% Statistics and Computing 17 (4), 2007
%
% Author: Ingo Buerk
% Year : 2011/2012
% Bachelor Thesis
% calculate degree matrix
degs = sum(W, 2);
D = sparse(1:size(W, 1), 1:size(W, 2), degs);
% compute unnormalized Laplacian
L = D - W;
% avoid dividing by zero
degs(degs == 0) = eps;
%calculate D^(-1/2)
D = spdiags(1./(degs.^0.5), 0, size(D, 1), size(D, 2));
% calculate normalized Laplacian
L = D * L * D;
% compute the eigenvectors corresponding to the k smallest
% eigenvalues
diff = eps;
[U, ~] = eigs(L, k, diff);
% for the the Jordan-Weiss algorithm, we need to normalize
% the eigenvectors row-wise
U = bsxfun(@rdivide, U, sqrt(sum(U.^2, 2)));
% now use the k-means algorithm to cluster U row-wise
% C will be a n-by-1 matrix containing the cluster number for
% each data point
C = kmeans(U, k, 'start', 'cluster', ...
'EmptyAction', 'singleton');
% now convert C to a n-by-k matrix containing the k indicator
% vectors as columns
C = sparse(1:size(D, 1), C, 1);
end