Daniel@0: function [centers,clusters,errors,ind] = kmeans_clusters(sD, n_max, c_max, verbose)
Daniel@0: 
Daniel@0: % KMEANS_CLUSTERS Clustering with k-means with different values for k.
Daniel@0: %
Daniel@0: % [c, p, err, ind] = kmeans_clusters(sD, [n_max], [c_max], [verbose])
Daniel@0: %
Daniel@0: %   [c, p, err, ind] = kmeans_clusters(sD);
Daniel@0: %  
Daniel@0: %  Input and output arguments ([]'s are optional):
Daniel@0: %   D         (struct) map or data struct
Daniel@0: %             (matrix) size dlen x dim, the data 
Daniel@0: %   [n_max]   (scalar) maximum number of clusters, default is sqrt(dlen)
Daniel@0: %   [c_max]   (scalar) maximum number of k-means runs, default is 5
Daniel@0: %   [verbose] (scalar) verbose level, 0 by default
Daniel@0: %
Daniel@0: %   c         (cell array) c{i} contains cluster centroids for k=i
Daniel@0: %   p         (cell array) p{i} contains cluster indeces for k=i
Daniel@0: %   err       (vector) squared sum of errors for each value of k
Daniel@0: %   ind       (vector) Davies-Bouldin index value for each clustering
Daniel@0: %
Daniel@0: % Makes a k-means to the given data set with different values of
Daniel@0: % k. The k-means is run multiple times for each k, and the best of
Daniel@0: % these is selected based on sum of squared errors. Finally, the
Daniel@0: % Davies-Bouldin index is calculated for each clustering. 
Daniel@0: %
Daniel@0: % For example to cluster a SOM: 
Daniel@0: %    [c, p, err, ind] = kmeans_clusters(sM); % find clusterings
Daniel@0: %    [dummy,i] = min(ind); % select the one with smallest index
Daniel@0: %    som_show(sM,'color',{p{i},sprintf('%d clusters',i)}); % visualize
Daniel@0: %    colormap(jet(i)), som_recolorbar % change colormap
Daniel@0: %  
Daniel@0: % See also SOM_KMEANS.
Daniel@0: 
Daniel@0: % References: 
Daniel@0: %   Jain, A.K., Dubes, R.C., "Algorithms for Clustering Data", 
Daniel@0: %   Prentice Hall, 1988, pp. 96-101.
Daniel@0: %
Daniel@0: %   Davies, D.L., Bouldin, D.W., "A Cluster Separation Measure", 
Daniel@0: %   IEEE Transactions on Pattern Analysis and Machine Intelligence, 
Daniel@0: %   vol. PAMI-1, no. 2, 1979, pp. 224-227.
Daniel@0: %
Daniel@0: %   Vesanto, J., Alhoniemi, E., "Clustering of the Self-Organizing
Daniel@0: %   Map", IEEE Transactions on Neural Networks, 2000.
Daniel@0: 
Daniel@0: % Contributed to SOM Toolbox vs2, February 2nd, 2000 by Esa Alhoniemi
Daniel@0: % Copyright (c) by Esa Alhoniemi
Daniel@0: % http://www.cis.hut.fi/projects/somtoolbox/
Daniel@0: 
Daniel@0: % ecco 301299 juuso 020200 211201
Daniel@0: 
Daniel@0: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Daniel@0: %% input arguments and initialization
Daniel@0: 
Daniel@0: if isstruct(sD), 
Daniel@0:   if isfield(sD,'data'), D = sD.data; 
Daniel@0:   else D = sD.codebook; 
Daniel@0:   end
Daniel@0: else D = sD; 
Daniel@0: end
Daniel@0: [dlen dim] = size(D);
Daniel@0: 
Daniel@0: if nargin < 2 | isempty(n_max) | isnan(n_max), n_max = ceil(sqrt(dlen)); end
Daniel@0: if nargin < 3 | isempty(c_max) | isnan(c_max), c_max = 5; end
Daniel@0: if nargin < 4 | isempty(verbose) | isnan(verbose), verbose = 0; end
Daniel@0: 
Daniel@0: centers   = cell(n_max,1); 
Daniel@0: clusters  = cell(n_max,1);
Daniel@0: ind       = zeros(1,n_max)+NaN;
Daniel@0: errors    = zeros(1,n_max)+NaN;
Daniel@0: 
Daniel@0: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Daniel@0: %% action
Daniel@0: 
Daniel@0: % the case k=1 is trivial, but Davies-Boulding index cannot be evaluated
Daniel@0: m = zeros(1,dim);
Daniel@0: for i=1:dim, m(i)=mean(D(isfinite(D(:,i)),i)); end
Daniel@0: centers{1} = m;
Daniel@0: clusters{1} = ones(dlen,1);
Daniel@0: [dummy qerr] = som_bmus(m,D);
Daniel@0: errors(1) = sum(qerr.^2);
Daniel@0: ind(1) = NaN; 
Daniel@0: 
Daniel@0: if verbose, fprintf(2,'Doing k-means for 2-%d clusters\n',n_max); end
Daniel@0: 
Daniel@0: for i = 2:n_max, % number of clusters
Daniel@0: 
Daniel@0:   % make k-means with k=i for c_max times and select the best based
Daniel@0:   % on sum-of-squared errors (SSE)
Daniel@0:   best = realmax;  
Daniel@0:   for j = 1:c_max     % run number j for cluster i      
Daniel@0:     if verbose,
Daniel@0:       fprintf('%d/%d clusters, k-means run %d/%d\r', i, n_max,j, c_max);
Daniel@0:     end      
Daniel@0:     [c, k, err] = som_kmeans('batch', D, i, 100, 0);
Daniel@0:     if err < best, k_best = k'; c_best = c; best = err; end
Daniel@0:     % ' added in k_best = k'; by kr 1.10.02
Daniel@0:   end
Daniel@0:   if verbose, fprintf(1, '\n');  end
Daniel@0: 
Daniel@0:   % store the results  
Daniel@0:   centers{i}  = c_best;
Daniel@0:   clusters{i} = k_best;
Daniel@0:   errors(i)   = best;
Daniel@0: %  ind(i)      = db_index(D, c_best, k_best, 2); wrong version in somtbx ??
Daniel@0:   ind(i)      = db_index(D, k_best, c_best, 2); % modified by kr 1.10.02
Daniel@0: 
Daniel@0:   % if verbose mode, plot the index & SSE
Daniel@0:   if verbose
Daniel@0:     subplot(2,1,1), plot(ind), grid
Daniel@0:     title('Davies-Bouldin''s index')
Daniel@0:     subplot(2,1,2), plot(errors), grid
Daniel@0:     title('SSE')
Daniel@0:     drawnow
Daniel@0:   end
Daniel@0: end
Daniel@0: 
Daniel@0: return; 
Daniel@0: 
Daniel@0: 
Daniel@0: