KMeans聚类算法模式识别.docx
《KMeans聚类算法模式识别.docx》由会员分享，可在线阅读，更多相关《KMeans聚类算法模式识别.docx（12页珍藏版）》请在冰点文库上搜索。
KMeans聚类算法模式识别
K-Means聚类算法
1.算法原理
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）直到不再发生变化。
2.主要代码
主程序：
clc;
clear;
closeall;
%%聚类算法测试
nSample=[500,500,500];
%3维情况
dim=3;
coeff={
[-20.8;-10.9;20.7;],....
[10.9;-20.7;-20.8;],...
[-20.7;20.8;-10.9;],};
data=createSample（nSample,dim,coeff）;
%%得到训练数据
nClass=length（nSample）;
tlabel=[];
tdata=[];
fori=1:
nClass
tlabel=[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:
nClass
index=find（label（:
1）==i）;
result{i}=tdata（index,:
）;
end
figure;
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:
k
label（seq（i））=i;
end
dist=zeros（n,k）;
while（true）
%计算数据到每个簇的欧几里得距离
fori=1:
k
temp=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
%dist=data（i,:
）-nowMeans（j,:
）;
%dist=dot（dist,dist）;
%
%if（dist%%修改最近的距离，并记录测试的簇号
%minDist=dist;
%index=j;
%end
%end
%
%%判断是该元素是否重新划分了簇
%if（index~=label（i））
%editElem=editElem+1;
%label（i）=index;
%end
%
%end
ifeditElem==0
%表示本次没有修改，那么跳出循环
break;
end
%重新分簇后，重新计算均值
fori=1:
k
%计算第k簇的均值
[index]=find（label（:
1）==i）;
nowMeans（i,:
）=mean（data（index,:
））;
end
end
end
从n个元素中随机抽取K个元素的代码：
function[out]=stpRandN_K（n,k）
%%从1-n中随机选中k个不同的元素
data=1:
n;
fori=1:
k
index=floor（（n-i+1）*rand（））+i;
%交换i和index上的数据
temp=data（index）;
data（index）=data（i）;
data（i）=temp;
end
out=data（1:
k）;
end
图片聚类测试代码：
closeall;
clc;
clear;
rgbdata=imread（'data\\g-1.jpg'）;
labdata=stpRgb2Lab（rgbdata）;
[sm,sn,~]=size（labdata）;
sN=sm*sn;
nClass=4;
labdata=reshape（labdata,sN,3）;
[label]=stpKMeans（labdata,nClass）;
label=reshape（label,sm,sn）;
figure;
subplot（1,2,1）;imshow（rgbdata）;
holdon;
subplot（1,2,2）;
TX=1:
sn;
TY=1:
sm;
imagesc（TX,TY,label）;
3.结果分析
针对给定的参数
K-Means算法三类聚类结果：
图1初始数据和K-Means聚类结果
当初始数据给为如下时：
K-Means算法三类聚类结果：
图2初始数据和K-Means聚类结果
由此可以看到，K-Means算法会把一些偏离中心较远的点分到其它簇内。
4.用于图片的结果
以图片的在Lab颜色空间的三通道作为三个特征，每个像素为一个样本点，进行图片聚类，此时，如果类数为8，则得到：
图3a图片聚类（8类）结果
图3b图片聚类（8类）结果
聚类数量变为15时结果如下：
图4a图片聚类（15类）结果
图4b图片聚类（15类）结果
当聚类为4的时候，结果为：
图5a图片聚类（4类）结果
图5b图片聚类（4类）结果
升级会员 