-
Notifications
You must be signed in to change notification settings - Fork 1
/
LBG.m
52 lines (45 loc) · 1.5 KB
/
LBG.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
function [codebook, clusterID, D] = LBG(X, K, distortion_eps)
% X = input matrix of size M*N where N is number of features and M is number
% of sampels
% K = number of clusters, must be a power of 2
% distortion_eps: (D'-D/D)<distortion_eps
%%
% Step 1: Initialize single-vector codebook : centroid of all training vectors
codebook = mean(X,1); %1*N vector
D_prime = 0;
% Compute D (distortion)
D = sum((X-codebook(1,:)).^2,'all');
D = D./size(X,1);
D_prime = D;
clusterID = ones(size(X,1), 1);
while size(codebook,1) < K
eps = 0.01;
% Step 2: double size of codebook by splitting
codebook = [codebook.*(1-eps);codebook.*(1+eps)];
while(1)
clusterID = zeros(size(X,1), 1);
euc_dist = zeros(size(X, 1), size(codebook,1));
% step 3: Nearest-Neighbor Search
for i=1:size(codebook,1)
euc_dist(:,i) = sum(((X-codebook(i,:)).^2),2);
end
[~,clusterID] = min(euc_dist, [], 2);
%Step 4: Centroid update
codebook = zeros(size(codebook,1), size(X, 2));
for i=1:size(codebook,1)
codebook(i,:) = mean(X(clusterID==i,:));
end
% Compute D (distortion)
D=0;
for i=1:size(codebook,1)
D = D + sum((X(clusterID==i,:)-codebook(i,:)).^2,'all');
end
D = D./size(X,1);
if(abs(D_prime-D)/D < distortion_eps)
break
end
D_prime = D;
end
end
%final size of codebook is K*N, K=number of clusters, N=number of features
end