K-MEANS算法

K-MEANS算法是輸入聚類個數k,以及包含 n個數據對象的資料庫,輸出滿足方差最小標準的k個聚類。

實現方法

補充一個Matlab實現方法:

function [cid,nr,centers] = cskmeans(x,k,nc)

% CSKMEANS K-Means clustering - general method.

%

% This implements the more general k-means algorithm, where

% HMEANS is used to find the initial partition and then each

% observation is examined for further improvements in minimizing

% the within-group sum of squares.

%

% [CID,NR,CENTERS] = CSKMEANS(X,K,NC) Performs K-means

% clustering using the data given in X.

%

% INPUTS: X is the n x d matrix of data,

% where each row indicates an observation. K indicates

% the number of desired clusters. NC is a k x d matrix for the

% initial cluster centers. If NC is not specified, then the

% centers will be randomly chosen from the observations.

%

% OUTPUTS: CID provides a set of n indexes indicating cluster

% membership for each point. NR is the number of observations

% in each cluster. CENTERS is a matrix, where each row

% corresponds to a cluster center.

%

% See also CSHMEANS

% W. L. and A. R. Martinez, 9/15/01

% Computational Statistics Toolbox

warning off

[n,d] = size(x);

if nargin < 3

% Then pick some observations to be the cluster centers.

ind = ceil(n*rand(1,k));

% We will add some noise to make it interesting.

nc = x(ind,:) + randn(k,d);

end

% set up storage

% integer 1,...,k indicating cluster membership

cid = zeros(1,n);

% Make this different to get the loop started.

oldcid = ones(1,n);

% The number in each cluster.

nr = zeros(1,k);

% Set up maximum number of iterations.

maxiter = 100;

iter = 1;

while ~isequal(cid,oldcid) & iter < maxiter

% Implement the hmeans algorithm

% For each point, find the distance to all cluster centers

for i = 1:n

dist = sum((repmat(x(i,:),k,1)-nc).^2,2);

[m,ind] = min(dist); % assign it to this cluster center

cid(i) = ind;

end

% Find the new cluster centers

for i = 1:k

% find all points in this cluster

ind = find(cid==i);

% find the centroid

nc(i,:) = mean(x(ind,:));

% Find the number in each cluster;

nr(i) = length(ind);

end

iter = iter + 1;

end

% Now check each observation to see if the error can be minimized some more.

% Loop through all points.

maxiter = 2;

iter = 1;

move = 1;

while iter < maxiter & move ~= 0

move = 0;

% Loop through all points.

for i = 1:n

% find the distance to all cluster centers

dist = sum((repmat(x(i,:),k,1)-nc).^2,2);

r = cid(i); % This is the cluster id for x

%%nr,nr+1;

dadj = nr./(nr+1).*dist'; % All adjusted distances

[m,ind] = min(dadj); % minimum should be the cluster it belongs to

if ind ~= r % if not, then move x

cid(i) = ind;

ic = find(cid == ind);

nc(ind,:) = mean(x(ic,:));

move = 1;

end

end

iter = iter+1;

end

centers = nc;

if move == 0

disp('No points were moved after the initial clustering procedure.')

else

disp('Some points were moved after the initial clustering procedure.')

end

warning on

相關詞條

相關搜尋

熱門詞條

聯絡我們