Homec4science
Diffusion Research Scripts (Thomas Bolton) (master) Browse

Scripts_Sharing/Motion/MatlabScripts/GlobalUtilities/01_Graph_Construction/construct_knn_graph.m
3e192de56f2emaster

Last Change
Raw File

construct_knn_graph.m
View Options

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Author:
% Xavier Bresson, xavier.bresson@epfl.ch
%
% Course:
% A Network Tour of Data Science
% a.k.a. Graph Algorithms in Data Science
% EPFL, Fall 2015
%
% Version:
% November 25, 2015
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% % Pre-process data (if needed)
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% n = nb_data
% d = data_dimensionality
%
% % Center the data, i.e. x_i <- x_i - mean({x_i}), size(X) = n x d
% X = bsxfun(@minus, X, mean(X,1));
%
% % Normalize the variance of the data, i.e. x_i <- x_i / var({x_i}), size(X) = n x d
% X = bsxfun(@rdivide, X, sqrt(sum(X.^2,1))+eps);
%
% % Projection onto the sphere, i.e. ||x_i||_2=1, size(X) = n x d
% X = bsxfun(@rdivide, X, sqrt(sum(X.^2,2))+eps);
%
% % Normalize the data value between [0,1]:
% X = (X - min(X(:)))/ (max(X(:)) - min(X(:)));
% % or between [-1,1]:
% X = 2* ( (X - min(X(:)))/ (max(X(:)) - min(X(:))) - 0.5 );
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Usages:
% (i) W = construct_knn_graph(X,k,'euclidean');
% (ii) W = construct_knn_graph(X,k,'euclidean','zelnik-perona');
% (iii) W = construct_knn_graph(X,k,'cosine');
% (iv) W = construct_knn_graph(X,k,'cosine','binary');
% (v) W = construct_knn_graph(X,k,'cosine_binary');
%
% Notations:
% n = nb_data
% d = data_dimensionality
%
% Input variables:
% X = Data matrix. Size = n x d.
% k = Number of nearest neaighbors.
% dist = Type of distances: 'euclidean' or 'cosine'
% (Optional) zelnik_perona = 'zelnik-perona'.
% It activate the zelnik_perona technique: "Self-Tuning Spectral Clustering", 2005
%
% Output variables:
% W = Adjacency matrix. Size = n x n.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function W = construct_knn_graph(X,k,dist,parameter)
tstart = tic;
% Parameters
n = size(X,1);
% Additional parameters
if nargin==3
parameter = '';
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% k-NN Graph with Euclidean distance
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
if strcmp(dist,'euclidean') && ~strcmp(parameter,'zelnik-perona')
% Display
fprintf('Construct k-NN Graph with Euclidean distance\n')
% D = L2/Euclidean distances between all pairwise data points size(D) = n x n
fprintf('Computational time to compute all pairwise Euclidean distances:\n')
tic
D = distance(X',X');
toc
% Sort from smallest distances
[Dist,idx_sort] = sort(D,2,'ascend');
% Display
if 2==1
figure(100);
subplot(121);
imagesc(D); colorbar;
title('Euclidean distances for all pairwise data points')
subplot(122);
imagesc(Dist); colorbar;
title('Sorted Euclidean distances')
end
% Select k nearest neighbors (in k-NN)
Dk = Dist(:,1:k);
Idxk = idx_sort(:,1:k);
% Compute scale parameter of graph weigth function
sigma = Dk(:,k)';
sigma = mean(sigma);
% Compute graph
idxi = zeros(k*n,1);
idxj = zeros(k*n,1);
entries = zeros(k*n,1);
cpt = 1;
for i = 1:n
idxi(cpt:cpt+k-1) = Idxk(i,1);
idxj(cpt:cpt+k-1) = Idxk(i,:);
entries(cpt:cpt+k-1) = exp(-(Dk(i,:).^2)./ sigma^2); % Gaussian weight function
cpt = cpt+k;
end
W = sparse(idxi,idxj,entries,n,n);
W = max(W,W');
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% k-NN Graph with Euclidean distance and Zelnik-Perona's scale
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
if strcmp(dist,'euclidean') && strcmp(parameter,'zelnik-perona')
% Display
fprintf('Construct k-NN Graph with Euclidean distance and Zelnik-Perona''s scale\n')
% D = L2/Euclidean distances between all pairwise data points size(D) = n x n
fprintf('Computational time to compute all pairwise Euclidean distances:\n')
tic
D = distance(X',X');
toc
% Sort from smallest distances
[Dist,idx_sort] = sort(D,2,'ascend');
% Display
if 2==1
figure(100);
subplot(121);
imagesc(D); colorbar;
title('Euclidean distances for all pairwise data points')
subplot(122);
imagesc(Dist); colorbar;
title('Sorted Euclidean distances')
end
% Select k nearest neighbors (in k-NN)
Dk = Dist(:,1:k);
Idxk = idx_sort(:,1:k);
% Compute scale parameter of graph weigth function
sigma = Dk(:,k)';
% Compute graph
idxi = zeros(k*n,1);
idxj = zeros(k*n,1);
entries = zeros(k*n,1);
cpt = 1;
for i = 1:n
idxi(cpt:cpt+k-1) = Idxk(i,1);
idxj(cpt:cpt+k-1) = Idxk(i,:);
entries(cpt:cpt+k-1) = exp(-(Dk(i,:).^2)./ ( sigma(i).* sigma(Idxk(i,:)) ) ); % Zelnik-Perona
cpt = cpt+k;
end
W = sparse(idxi,idxj,entries,n,n);
W = max(W,W');
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% k-NN Graph with Cosine distance
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
if strcmp(dist,'cosine') && ~strcmp(parameter,'binary')
% Display
fprintf('Construct k-NN Graph with Cosine distance\n')
% Make X full for speedup
X = full(X);
% Center the data
X = bsxfun(@minus, X, mean(X,1));
% Projection onto the sphere, i.e. ||x_i||_2=1, size(X) = n x d
X = bsxfun(@rdivide, X, sqrt(sum(X.^2,2))+eps);
% Compute D = <Xi,Xj> for all pairwise data points size(D) = n x n
fprintf('Computational time to compute all pairwise dot products:\n')
tic
D = X * X';
toc
% Sort D according to largest values
[D_sort,idx_sort] = sort(D,2,'descend');
% Cosine distance
Dcos = abs(acos(D_sort));
Dist = Dcos;
% Display
if 2==1
figure(100);
subplot(121);
imagesc(D); colorbar;
title('Inner products <Xi,Xj> for all pairwise data points');
subplot(122);
imagesc(Dcos); colorbar;
title('Sorted cosine distances');
end
% Select k nearest neighbors (in k-NN)
Dk = Dist(:,1:k);
Idxk = idx_sort(:,1:k);
% Compute scale parameter of graph weigth function
sigma = Dk(:,k)';
sigma = mean(sigma);
% Compute graph
idxi = zeros(k*n,1);
idxj = zeros(k*n,1);
entries = zeros(k*n,1);
cpt = 1;
for i = 1:n
idxi(cpt:cpt+k-1) = Idxk(i,1);
idxj(cpt:cpt+k-1) = Idxk(i,:);
entries(cpt:cpt+k-1) = exp(-(Dk(i,:).^2)./ sigma^2); % Gaussian weight function
cpt = cpt+k;
end
W = sparse(idxi,idxj,entries,n,n);
W = max(W,W');
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% k-NN Graph with Cosine distance and Binary weight
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
if strcmp(dist,'cosine') && strcmp(parameter,'binary')
% Display
fprintf('Construct k-NN Graph with Cosine distance and Binary weight\n')
% Make X full for speedup
X = full(X);
% Center the data
X = bsxfun(@minus, X, mean(X,1));
% Projection onto the sphere, i.e. ||x_i||_2=1, size(X) = n x d
X = bsxfun(@rdivide, X, sqrt(sum(X.^2,2))+eps);
% Compute D = <Xi,Xj> for all pairwise data points size(D) = n x n
fprintf('Computational time to compute all pairwise dot products:\n')
tic
D = X * X';
toc
% Sort D according to largest values
[D_sort,idx_sort] = sort(D,2,'descend');
% Cosine distance
Dcos = abs(acos(D_sort));
Dist = Dcos;
% Display
if 2==1
figure(100);
subplot(121);
imagesc(D); colorbar;
title('Inner products <Xi,Xj> for all pairwise data points');
subplot(122);
imagesc(Dcos); colorbar;
title('Sorted cosine distances');
end
% Select k nearest neighbors (in k-NN)
Dk = Dist(:,1:k);
Idxk = idx_sort(:,1:k);
% Compute graph
idxi = zeros(k*n,1);
idxj = zeros(k*n,1);
entries = zeros(k*n,1);
cpt = 1;
for i = 1:n
idxi(cpt:cpt+k-1) = Idxk(i,1);
idxj(cpt:cpt+k-1) = Idxk(i,:);
entries(cpt:cpt+k-1) = 1; % Binary weight
cpt = cpt+k;
end
W = sparse(idxi,idxj,entries,n,n);
W = max(W,W');
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% k-NN Graph with Cosine distance and Binary weight
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
if strcmp(dist,'cosine_binary')
% Display
fprintf('Construct k-NN Graph with Cosine distance and Binary weight\n')
% Make X full for speedup
X = full(X);
% Center the data
X = bsxfun(@minus, X, mean(X,1));
% Projection onto the sphere, i.e. ||x_i||_2=1, size(X) = n x d
X = bsxfun(@rdivide, X, sqrt(sum(X.^2,2))+eps);
% Compute D = <Xi,Xj> for all pairwise data points size(D) = n x n
fprintf('Computational time to compute all pairwise dot products:\n')
tic
D = X * X';
toc
% Sort D according to largest values
[D_sort,idx_sort] = sort(D,2,'descend');
% Cosine distance
Dcos = abs(acos(D_sort));
Dist = Dcos;
% Display
if 2==1
figure(100);
subplot(121);
imagesc(D); colorbar;
title('Inner products <Xi,Xj> for all pairwise data points');
subplot(122);
imagesc(Dcos); colorbar;
title('Sorted cosine distances');
end
% Select k nearest neighbors (in k-NN)
Dk = Dist(:,1:k);
Idxk = idx_sort(:,1:k);
% Compute graph
idxi = zeros(k*n,1);
idxj = zeros(k*n,1);
entries = zeros(k*n,1);
cpt = 1;
for i = 1:n
idxi(cpt:cpt+k-1) = Idxk(i,1);
idxj(cpt:cpt+k-1) = Idxk(i,:);
entries(cpt:cpt+k-1) = 1; % Binary weight
cpt = cpt+k;
end
W = sparse(idxi,idxj,entries,n,n);
W = max(W,W');
end
fprintf('\nComputational time for K-NN graph construction (sec) = %.3f\n\n',toc(tstart));
end
function d = distance(a,b)
% DISTANCE - computes Euclidean distance matrix
%
% E = distance(A,B)
%
% A - (DxM) matrix
% B - (DxN) matrix
%
% Returns:
% E - (MxN) Euclidean distances between vectors in A and B
%
%
% Description :
% This fully vectorized (VERY FAST!) m-file computes the
% Euclidean distance between two vectors by:
%
% ||A-B|| = sqrt ( ||A||^2 + ||B||^2 - 2*A.B )
%
% Example :
% A = rand(400,100); B = rand(400,200);
% d = distance(A,B);
% Author : Roland Bunschoten
% University of Amsterdam
% Intelligent Autonomous Systems (IAS) group
% Kruislaan 403 1098 SJ Amsterdam
% tel.(+31)20-5257524
% bunschot@wins.uva.nl
% Last Rev : Oct 29 16:35:48 MET DST 1999
% Tested : PC Matlab v5.2 and Solaris Matlab v5.3
% Thanx : Nikos Vlassis
% Copyright notice: You are free to modify, extend and distribute
% this code granted that the author of the original code is
% mentioned as the original author of the code.
if (nargin ~= 2)
error('Not enough input arguments');
end
if (size(a,1) ~= size(b,1))
error('A and B should be of same dimensionality');
end
aa=sum(a.*a,1); bb=sum(b.*b,1); ab=a'*b;
d = sqrt(abs(repmat(aa',[1 size(bb,2)]) + repmat(bb,[size(aa,2) 1]) - 2*ab));
end
c4science · Help