Mercurial > hg > machine-learning-hw7

annotate runkMeans.m @ 6:6d94b2bafcd1 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Replace complicated memory-intensive operation with a faster loop
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Tue, 06 Dec 2011 11:49:32 -0500
parents ded78d0b4987
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
1 function [centroids, idx] = runkMeans(X, initial_centroids, ...
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
2 max_iters, plot_progress)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
3 %RUNKMEANS runs the K-Means algorithm on data matrix X, where each row of X
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
4 %is a single example
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
5 % [centroids, idx] = RUNKMEANS(X, initial_centroids, max_iters, ...
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
6 % plot_progress) runs the K-Means algorithm on data matrix X, where each
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
7 % row of X is a single example. It uses initial_centroids used as the
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
8 % initial centroids. max_iters specifies the total number of interactions
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
9 % of K-Means to execute. plot_progress is a true/false flag that
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
10 % indicates if the function should also plot its progress as the
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
11 % learning happens. This is set to false by default. runkMeans returns
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
12 % centroids, a Kxn matrix of the computed centroids and idx, a m x 1
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
13 % vector of centroid assignments (i.e. each entry in range [1..K])
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
14 %
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
15
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
16 % Set default value for plot progress
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
17 if ~exist('plot_progress', 'var') || isempty(plot_progress)
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
18 plot_progress = false;
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
19 end
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
20
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
21 % Plot the data if we are plotting progress
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
22 if plot_progress
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
23 figure;
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
24 hold on;
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
25 end
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
26
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
27 % Initialize values
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
28 [m n] = size(X);
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
29 K = size(initial_centroids, 1);
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
30 centroids = initial_centroids;
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
31 previous_centroids = centroids;
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
32 idx = zeros(m, 1);
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
33
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
34 % Run K-Means
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
35 for i=1:max_iters
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
36
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
37 % Output progress
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
38 fprintf('K-Means iteration %d/%d...\n', i, max_iters);
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
39 if exist('OCTAVE_VERSION')
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
40 fflush(stdout);
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
41 end
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
42
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
43 % For each example in X, assign it to the closest centroid
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
44 idx = findClosestCentroids(X, centroids);
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
45
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
46 % Optionally, plot progress here
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
47 if plot_progress
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
48 plotProgresskMeans(X, centroids, previous_centroids, idx, K, i);
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
49 previous_centroids = centroids;
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
50 fprintf('Press enter to continue.\n');
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
51 pause;
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
52 end
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
53
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
54 % Given the memberships, compute new centroids
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
55 centroids = computeCentroids(X, idx, K);
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
56 end
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
57
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
58 % Hold off if we are plotting progress
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
59 if plot_progress
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
60 hold off;
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
61 end
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
62
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
63 end
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
64