K-Means聚类算法-模式识别.doc

K--means是划分方法中较经典的聚类算法之一。由于该算法的效率高,所以在对大规模数据进行聚类时被广泛应用。目前,许多算法均围绕着该算法进行扩展和改进。k-means算法以k为参数,把n个对象分成k个簇,使簇内具有较高的相似度,而簇间的相似度较低。k-means算法的处理过程如下:首先,随机地选择k个对象,每个对象初始地代表了一个簇的平均值或中心;对剩余的每个对象,根据其与各簇中心的距离,将它赋给最近的簇;然后重新计算每个簇的平均值。这个过程不断重复,直到准则函数收敛。通常,采用平方误差准则,其定义如下:这里E是数据库中所有对象的平方误差的总和,p是空间中的点,mi是簇Ci的平均值。该目标函数使生成的簇尽可能紧凑独立,使用的距离度量是欧几里得距离,当然也可以用其他距离度量。k-means聚类算法的算法流程如下:输入:包含n个对象的数据库和簇的数目k;输出:k个簇,使平方误差准则最小。步骤:(1)任意选择k个对象作为初始的簇中心;(2)repeat;(3)根据簇中对象的平均值,将每个对象(重新)赋予最类似的簇;(4)更新簇的平均值,即计算每个簇中对象的平均值;(5)直到不再发生变化。:clc;clear;closeall;%%聚类算法测试nSample=[500,500,500]; %3维情况dim=3;coeff={[-; -;;],....[;-;-;],...[-;;-;],};data=createSample(nSample,dim,coeff);%%得到训练数据nClass=length(nSample);tlabel=[];tdata=[];fori=1:nClasstlabel=[tlabel;i*ones(nSample(i),1)];tdata=[tdata;data{i}];end%%调用k-means聚类算法[label]=stpKMeans(tdata,nClass);%%绘图result=cell(1,nClass);index=0;fori=1:nClassindex=find(label(:,1)==i);result{i}=tdata(index,:);endfigure;subplot(1,2,1);plot3(data{1}(:,1),data{1}(:,2),data{1}(:,3),'*',...data{2}(:,1),data{2}(:,2),data{2}(:,3),'o',...data{3}(:,1),data{3}(:,2),data{3}(:,3),'x');title('初始数据');subplot(1,2,2);plot3(result{1}(:,1),result{1}(:,2),result{1}(:,3),'*',...result{2}(:,1),result{2}(:,2),result{2}(:,3),'o',...result{3}(:,1),result{3}(:,2),result{3}(:,3),'x');title('K-Means聚类结果');K-Means核心算法:function[label]=stpKMeans(data,k)%%KMeans聚类算法,参考%%%%输入%data   原始数据%k    聚多少个簇%%%输出%label  按照data数据的顺序,每个样本的簇号的列表[n,dim]=size(data);label=zeros(n,1);%任选k个对象作为初始的簇中心seq=stpRandN_K(n,k);nowMeans=data(seq,:);fori=1:klabel(seq(i))=i;enddist=zeros(n,k);while(true)%计算数据到每个簇的欧几里得距离fori=1:ktemp=data;forj=1:dim%先让数据减去第j个特征temp(:,j)=data(:,j)-nowMeans(i,j);end%点乘后再相加球的距离的平方temp=temp.*temp;dist(:,i)=sum(temp,2);end%从k种距离中找出最小的,并计算修改次数(label跟上一次不一样)[~,label2]=min(dist,[],2);editElem=sum(label(:,1)~=label2(:,1));label=label2;%    fori=1:n%    %根据均值将当前的每个元素重新分簇%      minDist=inf;%      index=-1;%      %从当前的k个均值中找到离元素i最近的一个,将其划分到该簇%      forj=1:k%