https://github.com/reproducibilitystamp/dataset-processing
Tip revision: 36fbb80f231a8a564a730b8ad7d2787491b2a696 authored by acarlier on 20 May 2016, 09:34:24 UTC
- comments added
- comments added
Tip revision: 36fbb80
spectralClustering.m
function [clust_maj,annot_clust,ind_annot_clust] = spectralClustering(shape_annot,areas_tri)
nbAnnot = length(shape_annot);
% Compute the affinity matrix of the annotations
aff = eye(nbAnnot);
for ind_ann = 1:length(shape_annot)
for ind_ann2 = ind_ann+1:length(shape_annot)
d = annotationDistance(shape_annot{ind_ann},shape_annot{ind_ann2},areas_tri);
aff(ind_ann,ind_ann2) = d;
aff(ind_ann2,ind_ann) = d;
end
end
% Compute the optimal number of clusters using the Calinski-Harabasz
% criteria (not defined
VRC(1) = 0;
for nbClust = 2:nbAnnot
clust = ngJordanWeissSpectralClustering(aff,nbClust);
VRC(nbClust) = computeCalinskiHarabasz(shape_annot,clust,areas_tri);
end
[aux,nbClust] = max(VRC);
% Cluster the annotations using the Jordan-Weiss method
clust = ngJordanWeissSpectralClustering(aff,nbClust);
ind_aux = 1;
for ind_clust = 1:nbClust
% Only keep the clusters that have at least 3 annotations
if (length(find(clust==ind_clust)) > 2)
% For each cluster, get the corresponding annotations
annot_clust{ind_aux} = shape_annot(clust==ind_clust);
ind_annot_clust{ind_aux} = find(clust==ind_clust);
% Compute the majority of the annotations from this cluster
clust_maj{ind_aux} = computeMajority(annot_clust{ind_aux});
ind_aux = ind_aux + 1;
end
end
end
function VRC = computeCalinskiHarabasz(annotations,idx,areas_tri)
% Nuber of annotations
N = length(idx);
% Number of clusters
nbClust = max(idx);
majority = computeMajority(annotations);
SSw = 0; % Within cluster variance
SSb = 0; % Between cluster variance
for ind_c = 1:nbClust
% For each cluster, get the corresponding annotations
annot_ind_c = annotations(idx==ind_c);
% Number of annotations in the cluster
N_ind_c = sum(idx==ind_c);
% Compute cluster Majority
if (length(annot_ind_c)>1)
majority_ind_c = computeMajority(annot_ind_c);
else
majority_ind_c = cell2mat(annot_ind_c);
end
% Updating SSb
SSb = SSb + N_ind_c*annotationDistance(majority,majority_ind_c,areas_tri);
% Updating SSw
for i = 1:N_ind_c
SSw = SSw + annotationDistance(annot_ind_c{i},majority_ind_c,areas_tri);
end
end
VRC = SSb/SSw;
% Using this criteria changes the results and usually provides less
% clusters (one or two)
% VRC = SSb*(N-nbClust)/(SSw * (nbClust));
end
% Implements the spectral clustering described in
% Ng, A., Jordan, M., and Weiss, Y. (2002). On spectral clustering:
% analysis and an algorithm
% Takes an affinity matrix as an input and the desired number of clusters k
function indices = ngJordanWeissSpectralClustering(A,k)
% Define D to be the diagonal matrix whose (i, i)-element is the
% sum of A's i-th row
for i=1:size(A,1)
D(i,i) = sum(A(i,:));
end
L = zeros(size(A));
% construct the matrix L = D^(-1/2) A D^(-1/2)
for i=1:size(A,1)
for j=1:size(A,2)
L(i,j) = A(i,j) / (sqrt(D(i,i)) * sqrt(D(j,j)));
end
end
% Find x1, x2, ..., xk, the k largest eigenvectors of L ...
[x,aux] = eig(L);
% ... and form the matrix X = [X1 X2 ... Xk] by stacking the eigenvectors
% in columns.
X = x(:,(size(x,1)-(k-1)): size(x,1));
% Form the matrix Y from X by renormalizing each of X's rows to have
% unit length
for i=1:size(X,1)
n = sqrt(sum(X(i,:).^2));
Y(i,:) = X(i,:) ./ n;
end
% Treating each row of Y as a point in Rk, cluster them into k
% clusters via K-means or any other algorithm
[indices,aux] = kmeans(Y,k);
end