|
wolffd@0
|
1 function [centres, options, post, errlog] = netlabkmeans(centres, data, options)
|
|
wolffd@0
|
2 %KMEANS Trains a k means cluster model.
|
|
wolffd@0
|
3 %(Renamed NETLABKMEANS in MIRtoolbox in order to avoid conflict with
|
|
wolffd@0
|
4 % statistics toolbox...)
|
|
wolffd@0
|
5 %
|
|
wolffd@0
|
6 % Description
|
|
wolffd@0
|
7 % CENTRES = KMEANS(CENTRES, DATA, OPTIONS) uses the batch K-means
|
|
wolffd@0
|
8 % algorithm to set the centres of a cluster model. The matrix DATA
|
|
wolffd@0
|
9 % represents the data which is being clustered, with each row
|
|
wolffd@0
|
10 % corresponding to a vector. The sum of squares error function is used.
|
|
wolffd@0
|
11 % The point at which a local minimum is achieved is returned as
|
|
wolffd@0
|
12 % CENTRES. The error value at that point is returned in OPTIONS(8).
|
|
wolffd@0
|
13 %
|
|
wolffd@0
|
14 % [CENTRES, OPTIONS, POST, ERRLOG] = KMEANS(CENTRES, DATA, OPTIONS)
|
|
wolffd@0
|
15 % also returns the cluster number (in a one-of-N encoding) for each
|
|
wolffd@0
|
16 % data point in POST and a log of the error values after each cycle in
|
|
wolffd@0
|
17 % ERRLOG. The optional parameters have the following
|
|
wolffd@0
|
18 % interpretations.
|
|
wolffd@0
|
19 %
|
|
wolffd@0
|
20 % OPTIONS(1) is set to 1 to display error values; also logs error
|
|
wolffd@0
|
21 % values in the return argument ERRLOG. If OPTIONS(1) is set to 0, then
|
|
wolffd@0
|
22 % only warning messages are displayed. If OPTIONS(1) is -1, then
|
|
wolffd@0
|
23 % nothing is displayed.
|
|
wolffd@0
|
24 %
|
|
wolffd@0
|
25 % OPTIONS(2) is a measure of the absolute precision required for the
|
|
wolffd@0
|
26 % value of CENTRES at the solution. If the absolute difference between
|
|
wolffd@0
|
27 % the values of CENTRES between two successive steps is less than
|
|
wolffd@0
|
28 % OPTIONS(2), then this condition is satisfied.
|
|
wolffd@0
|
29 %
|
|
wolffd@0
|
30 % OPTIONS(3) is a measure of the precision required of the error
|
|
wolffd@0
|
31 % function at the solution. If the absolute difference between the
|
|
wolffd@0
|
32 % error functions between two successive steps is less than OPTIONS(3),
|
|
wolffd@0
|
33 % then this condition is satisfied. Both this and the previous
|
|
wolffd@0
|
34 % condition must be satisfied for termination.
|
|
wolffd@0
|
35 %
|
|
wolffd@0
|
36 % OPTIONS(14) is the maximum number of iterations; default 100.
|
|
wolffd@0
|
37 %
|
|
wolffd@0
|
38 % See also
|
|
wolffd@0
|
39 % GMMINIT, GMMEM
|
|
wolffd@0
|
40 %
|
|
wolffd@0
|
41
|
|
wolffd@0
|
42 % Copyright (c) Ian T Nabney (1996-2001)
|
|
wolffd@0
|
43
|
|
wolffd@0
|
44 [ndata, data_dim] = size(data);
|
|
wolffd@0
|
45 [ncentres, dim] = size(centres);
|
|
wolffd@0
|
46
|
|
wolffd@0
|
47 if dim ~= data_dim
|
|
wolffd@0
|
48 error('Data dimension does not match dimension of centres')
|
|
wolffd@0
|
49 end
|
|
wolffd@0
|
50
|
|
wolffd@0
|
51 if (ncentres > ndata)
|
|
wolffd@0
|
52 error('More centres than data')
|
|
wolffd@0
|
53 end
|
|
wolffd@0
|
54
|
|
wolffd@0
|
55 % Sort out the options
|
|
wolffd@0
|
56 if (options(14))
|
|
wolffd@0
|
57 niters = options(14);
|
|
wolffd@0
|
58 else
|
|
wolffd@0
|
59 niters = 100;
|
|
wolffd@0
|
60 end
|
|
wolffd@0
|
61
|
|
wolffd@0
|
62 store = 0;
|
|
wolffd@0
|
63 if (nargout > 3)
|
|
wolffd@0
|
64 store = 1;
|
|
wolffd@0
|
65 errlog = zeros(1, niters);
|
|
wolffd@0
|
66 end
|
|
wolffd@0
|
67
|
|
wolffd@0
|
68 % Check if centres and posteriors need to be initialised from data
|
|
wolffd@0
|
69 if (options(5) == 1)
|
|
wolffd@0
|
70 % Do the initialisation
|
|
wolffd@0
|
71 perm = randperm(ndata);
|
|
wolffd@0
|
72 perm = perm(1:ncentres);
|
|
wolffd@0
|
73
|
|
wolffd@0
|
74 % Assign first ncentres (permuted) data points as centres
|
|
wolffd@0
|
75 centres = data(perm, :);
|
|
wolffd@0
|
76 end
|
|
wolffd@0
|
77 % Matrix to make unit vectors easy to construct
|
|
wolffd@0
|
78 id = eye(ncentres);
|
|
wolffd@0
|
79
|
|
wolffd@0
|
80 % Main loop of algorithm
|
|
wolffd@0
|
81 for n = 1:niters
|
|
wolffd@0
|
82
|
|
wolffd@0
|
83 % Save old centres to check for termination
|
|
wolffd@0
|
84 old_centres = centres;
|
|
wolffd@0
|
85
|
|
wolffd@0
|
86 % Calculate posteriors based on existing centres
|
|
wolffd@0
|
87 d2 = dist2(data, centres);
|
|
wolffd@0
|
88 % Assign each point to nearest centre
|
|
wolffd@0
|
89 [minvals, index] = min(d2', [], 1);
|
|
wolffd@0
|
90 post = id(index,:);
|
|
wolffd@0
|
91
|
|
wolffd@0
|
92 num_points = sum(post, 1);
|
|
wolffd@0
|
93 % Adjust the centres based on new posteriors
|
|
wolffd@0
|
94 for j = 1:ncentres
|
|
wolffd@0
|
95 if (num_points(j) > 0)
|
|
wolffd@0
|
96 centres(j,:) = sum(data(find(post(:,j)),:), 1)/num_points(j);
|
|
wolffd@0
|
97 end
|
|
wolffd@0
|
98 end
|
|
wolffd@0
|
99
|
|
wolffd@0
|
100 % Error value is total squared distance from cluster centres
|
|
wolffd@0
|
101 e = sum(minvals);
|
|
wolffd@0
|
102 if store
|
|
wolffd@0
|
103 errlog(n) = e;
|
|
wolffd@0
|
104 end
|
|
wolffd@0
|
105 if options(1) > 0
|
|
wolffd@0
|
106 fprintf(1, 'Cycle %4d Error %11.6f\n', n, e);
|
|
wolffd@0
|
107 end
|
|
wolffd@0
|
108
|
|
wolffd@0
|
109 if n > 1
|
|
wolffd@0
|
110 % Test for termination
|
|
wolffd@0
|
111 if max(max(abs(centres - old_centres))) < options(2) & ...
|
|
wolffd@0
|
112 abs(old_e - e) < options(3)
|
|
wolffd@0
|
113 options(8) = e;
|
|
wolffd@0
|
114 return;
|
|
wolffd@0
|
115 end
|
|
wolffd@0
|
116 end
|
|
wolffd@0
|
117 old_e = e;
|
|
wolffd@0
|
118 end
|
|
wolffd@0
|
119
|
|
wolffd@0
|
120 % If we get here, then we haven't terminated in the given number of
|
|
wolffd@0
|
121 % iterations.
|
|
wolffd@0
|
122 options(8) = e;
|
|
wolffd@0
|
123 if (options(1) >= 0)
|
|
wolffd@0
|
124 disp(maxitmess);
|
|
wolffd@0
|
125 end
|
|
wolffd@0
|
126
|
