信息与编码课程设计

题    目：k均值聚类算法及其matlab实现

姓    名：王超

学    号：2008052223

班    级：信息与计算科学082

指导教师：刘力军

完成日期：2011年9月26日

                       目录

1．算法介绍································2

二Matlab语言的介绍·······················2

3．算法的实现······························3

4．结论····································6

5．参考文献································6

摘要：本文主要介绍了K均值聚类算法并完成了k均值聚类算法的matlab实现

正文：

1．算法介绍

    k-means算法是输入聚类个数k，以及包含 n个数据对象的数据库，输出满足方差最小标准的k个聚类　　

k-means算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 

k-means算法是一种基于样本间相似性度量的间接聚类方法，属于非监督学习方法。此算法以k为参数，把n 个对象分为k个簇，以使簇内具有较高的相似度，而且簇间的相似度较低。相似度的计算根据一个簇中对象的平均值（被看作簇的重心）来进行。此算法首先随机选择k个对象，每个对象代表一个聚类的质心。对于其余的每一个对象，根据该对象与各聚类质心之间的距离，把它分配到与之最相似的聚类中。然后，计算每个聚类的新质心。重复上述过程，直到准则函数会聚。k-means算法是一种较典型的逐点修改迭代的动态聚类算法，其要点是以误差平方和为准则函数。逐点修改类中心：一个象元样本按某一原则，归属于某一组类后，就要重新计算这个组类的均值，并且以新的均值作为凝聚中心点进行下一次象元素聚类；逐批修改类中心：在全部象元样本按某一组的类中心分类之后，再计算修改各类的均值，作为下一次分类的凝聚中心点。

处理流程：

（1） 从 n个数据对象任意选择 k 个对象作为初始聚类中心；　　

（2） 循环（3）到（4）直到每个聚类不再发生变化为止　　

（3） 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；　　

（4） 重新计算每个（有变化）聚类的均值（中心对象）

2．Matlab语言的介绍

matlab是由美国mathworks公司发布的主要面对科学计算、可视化以及交互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使用的视窗环境中，为科学研究、工程设计以及必须进行有效数值计算的众多科学领域提供了一种全面的解决方案，并在很大程度上摆脱了传统非交互式程序设计语言（如C、Fortran）的编辑模式，代表了当今国际科学计算软件的先进水平。　 　　

matlab和mathematics、maple并称为三大数学软件。它在数学类科技应用软件中在数值计算方面首屈一指。MATLAB可以进行矩阵运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语言的程序等，主要应用于工程计算、控制设计、信号处理与通讯、图像处理、信号检测、金融建模设计与分析等领域。

3．算法的实现

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

4．结论：

    k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。本算法确定的K 个划分到达平方误差最小。当聚类是密集的，且类与类之间区别明显时，效果较好。

五．参考文献：

[1] David J.C.Mackay, 信息论、推理与学习算法,北京，高等教育出版社