国赛备赛——k-means聚类算法(含代码)
k-means聚类
概念:
将物理或抽象对象的集合分成由类似的对象组成的多个类的过程即为聚类,通俗的讲,就是“物以类聚,人以群分”
聚类是一种数据探索的分析方法,可以在大量的数据中找到某一种结构。
由聚类生成的簇是一组数据对象的集合,这些对象与同一个簇的对象彼此相似,与其他簇的对象相异。
聚类分析又称群分析,它是研究分类问题的一种统计方法,主要分为以下几种:
划分方法、层次方法、基于密度的方法、基于网格的方法、基于模型的方法
以下总结了划分法K-means的算法原理及步骤:
K-means算法原理
随机从数据集中选取K个点,每个点初始代表每个簇的聚类中心。计算剩余各个样本到聚类中心的的距离,并将它赋给距离最近的簇,然后重新计算每一簇的平均值,整个过程不断重复(算法迭代),直到相邻两次调整没有明显变化,此时数据聚类形成的簇已经收敛。迭代终止条件也可以是以下任意一个:
a.没有对象被重新分配给不同的聚类
b.聚类中心不再发生变化
c.误差平方和局部最小
2.K—means算法步骤
处理流程:
a.从N个数据对象任意选择K个对象作为初始聚类中心
b.循环c,d步骤
c.根据聚类对象的均值,计算每个对象与这些中心对象的距离。并根据最小距离重新对相应的对象进行划分。
d.重新计算每个聚类的均值,直到聚类中心不再变化。使得E式最小
已知20个样本,每个样本两个特征,对此数据进行分析为例,以下基于MATLAB实现聚类:
%% 数据准备和初始化
clc
clear
x=[0 0;1 0; 0 1; 1 1;2 1;1 2; 2 2;3 2; 6 6;7 6; 8 6; 6 7; 7 7; 8 7; 9 7 ; 7 8; 8 8; 9 8; 8 9 ; 9 9];
z=zeros(2,2);
z1=zeros(2,2);
z=x(1:2, 1:2);
%% 寻找聚类中心
while 1
count=zeros(2,1);
allsum=zeros(2,2);
for i=1:20 % 对每一个样本i,计算到2个聚类中心的距离
temp1=sqrt((z(1,1)-x(i,1)).^2+(z(1,2)-x(i,2)).^2);
temp2=sqrt((z(2,1)-x(i,1)).^2+(z(2,2)-x(i,2)).^2);
if(temp1<temp2)
count(1)=count(1)+1;
allsum(1,1)=allsum(1,1)+x(i,1);
allsum(1,2)=allsum(1,2)+x(i,2);
else
count(2)=count(2)+1;
allsum(2,1)=allsum(2,1)+x(i,1);
allsum(2,2)=allsum(2,2)+x(i,2);
end
end
z1(1,1)=allsum(1,1)/count(1);
z1(1,2)=allsum(1,2)/count(1);
z1(2,1)=allsum(2,1)/count(2);
z1(2,2)=allsum(2,2)/count(2);
if(z==z1)
break;
else
z=z1;
end
end
%% 结果显示
disp(z1);% 输出聚类中心
plot( x(:,1), x(:,2),'k*',...
'LineWidth',2,...
'MarkerSize',10,...
'MarkerEdgeColor','k',...
'MarkerFaceColor',[0.5,0.5,0.5])
hold on
plot(z1(:,1),z1(:,2),'ko',...
'LineWidth',2,...
'MarkerSize',10,...
'MarkerEdgeColor','k',...
'MarkerFaceColor',[0.5,0.5,0.5])
set(gca,'linewidth',2) ;
xlabel('特征x1','fontsize',12);
ylabel('特征x2','fontsize',12);
title('K-means分类图','fontsize',12);
输出结果及图形分析如下:
由上图结果,聚类效果显著
3.聚类模型评估:
优点
(1)原理易懂、易于实现;
(2)当簇间的区别较明显时,聚类效果较好;
缺点
(1)当样本集规模大时,收敛速度会变慢;
(2)对孤立点数据敏感,少量噪声就会对平均值造成较大影响;
(3)k的取值十分关键,对不同数据集,k选择没有参考性,需要大量实验
参加国赛的小伙伴可以加群一起讨论学习呀(最好别用报名的QQ加群)