K——均值法

一.算法学习：

1.前提：
模式特征矢量集为{x1,x2,…,xN}；类的数目K是事先取定的。
2.基本思想：
任意选取K个聚类中心，按最小距离原则将各模式分配到K类的某一类。不断计算聚类中心和调整各模式的类别，最终使各模式到其判属类别中心的距离平方之和最小。
Sj：第j个聚类集（域），Zj ；聚类中心，Nj： Sj中所含的样本个数

聚类中心的选择应使准则函数J极小，Sj类的聚类中心应选为该类样本的均值。
3.步骤：
(1)任选K个模式特征矢量作为初始聚类中心： z1(1) ,z2(1) ,…zK(1)。括号内的序号表示迭代次数。
(2)将待分类的模式特征矢量集{x}中的模式逐个按最小距离原则分划给K类中的某一类。
(3)计算重新分类后的各聚类中心zj(k+1)，即求各聚类域中所包含样本的均值向量：
，以均值向量作新的聚类中心。可得新的准则函数：

(4)如果zj(k+1)=zj(k)(j=1,2,…K),则结束；否则，k=k+1,转(2)。
注意：多次运行K均值算法，例如50~1000次，每次随机选取不同的初始聚类中心。聚类结束后计算准则函数值，选取准则函数值最小的聚类结果为最后的结果。该方法一般适用于聚类数目小于10的情况。

二．例题：

X1(0,0) X2(3,8) X3(2,2) X4(1,1) X5(5,3)
X6(4,8) X7(6,3) X8(5,4) X9(6,4) X10(7,5)
2.1算法分析：
1） 第一个问题应该是选取一个合适的K值，然后随机选取K个点作为初始的聚类中心。
2） 然后就是计算距离，进行聚类（即把点集中每个点分到对应的聚类中）。
3） 计算新的聚类中心，均值法计算。
4） 判断上一轮的聚类中心和本轮的聚类中心是否相等。否则返回第二步。

2.2 代码：（python代码经planet B高亮处理）

1.	import random  
2.	import numpy as np  
3.	#数据导入工作  
4.	data=[[0,0],[3,8],[2,2],[1,1],[5,3],[4,8],[6,3],[5,4],[6,4],[7,5]]  
5.	l=len(data)  
6.	print("数据长度：",l)  
7.	k=int(input("请输入k值："))  
8.	#随机选k个向量作为均值向量  
9.	sj=random.sample(range(l),k)  #  
10.	print("随机选取k个数:",sj)  
11.	jzxl=[data[i] for i in sj]  #均值向量  
12.	print("均值向量:",jzxl)  
13.	  
14.	t=0  
15.	  
16.	while True:  
17.	    t=t+1  
18.	    if t>100:  
19.	        print("循环超过100次")  
20.	        break  
21.	  
22.	    a=[[] for i in range(k)]  # k个空列表来存各个样本与均值的距离  
23.	    #计算距离  
24.	    for j in range(l):  
25.	        gds=1000 #固定数作为每轮比较值  
26.	        julei=0  
27.	        for q in range(k):  
28.	            d=np.hypot(data[j][0]-jzxl[q][0],data[j][1]-jzxl[q][1])  
29.	            if d<gds:  
30.	                gds=d  
31.	                julei=q  
32.	        a[julei].append(data[j])  
33.	      
34.	      
35.	  
36.	    #用均值法计算新的聚类中心  
37.	    newjzxl=[[] for i in range(k)]  
38.	    for i in range(k):  
39.	        s1=np.sum(a[i][j][0] for j in range(len(a[i])))  
40.	        z1=s1/len(a[i])  
41.	        newjzxl[i].append(z1)  
42.	          
43.	        s2=np.sum(a[i][j][1] for j in range(len(a[i])))  
44.	        z2=s2/len(a[i])  
45.	        newjzxl[i].append(z2)  
46.	    if jzxl==newjzxl:  #如果前后均值向量相等，则退出循环  
47.	          
48.	        break  
49.	    else:  
50.	        print("第",t,"次聚类结果为：")  
51.	        for i in range(k):  
52.	             print("聚类",i,": ",a[i])  
53.	        jzxl=newjzxl  
54.	      
55.	    #break  
56.	print("共循环了  ",t,"  次，最终聚类结果为")  
57.	for i in range(k):  
58.	    print("聚类",i,": ",a[i])  

一．K-均值聚类（K-means）概述

1.聚类

“类”指的是具有相似形得几何。聚类是值将数据集划分为若干类，是的类内之间得数据最为相似，各类之间的数据相似度差别尽可能大。聚类分析就是以相似性为基础，对数据集进行聚类划分，属于无监督学习。

2.无监督学习和监督学习

K-均值聚类属于无监督学习。监督学习知道从对象（数据）中学习什么，而无监督学习无需知道所要搜寻的目标，它根据算法得到数据的共同特征。比如用分类和聚类来说，分类事先就知道所要得到的类别，而聚类是以相似度为基础，将对象就分得不同的簇。

3.K-means

K-means算法是一种简单的迭代型聚类算法，采用距离作为相似性指标，从而发现给定数据集中的K个类，且每个类的中心是根据类中所有值的均值得到，每个类用聚类中心来描述。对于给定的一个包含n个d 维数据点的数据集X以及要分得的类别K，选取欧式距离作为相似度指标，聚类目标是使得各类的聚类平方和最小，即最小化：

结合最小二乘法和拉格朗日原理，聚类中心为对应类别中各数据点的平均值，同时为了使得算法收敛，在迭代过程中，应使最终聚类中心尽可能的不变。

二．K均值聚类算法实现

1.K均值聚类算法流程

K-means是一个反复迭代的过程，算法分为四个步骤：

1） 选取数据空间中的K个对象作为初始中心，每个对象代表一个聚类中心：

2） 对于样本中的数据对象，根据他们与这些聚类中心的欧氏距离，按距离最近的准则将它们分到距离它们最近的聚类中心（最相似）所对应的类；

3） 更新聚类中心：将每个类别中所有对象所对应的均值作为该类别的聚类中心，计算目标函数的值：

4） 判断聚类中心和目标函数的值是否发生改变，若不变，则输出结果，若改变，则返回2）。

2.K均值聚类Matlab实现

1）自主选择数据测试：利用mvnrnd（）函数在一定范围内创造随机数，并作图，生成的随机二维分布图形见图1：

2）分析类别数K的设定：K值的确定可以由以下方法确定：1、根据实际需要；2、肘部法则;3、轮廓系数;4、层次聚类;5、Canopy算法;6、间隔统计量 Gap Statistic;

本文采用层次聚类的方法确定K的取值。层次聚类是通过可视化然后认为去判断大致聚为积累，很明显在共同父节点的一颗子树可以被聚类为一类。分层聚类图见图2：

图2

从图中我们可以看到K可以取3。

3）初始质心的选取：选择适当的初始质心是基本K-means算法的关键步骤。

方法1：随机选取初始质心，但是这样簇的质量常常很差。处理选取初始质心问题的一种常用技术是“多次运行，每次使用一组不同的随机初始质心，然后选取具有最小SSE的簇集。

方法2：取一个样本，并使用层次聚类技术对它聚类。从层次聚类中提取K个簇，并用这些簇的质心作为初始质心。适用于小样本。

方法3：随机选择第一个点，或去所有点的质心作为第一个点。然后，对于每个后继初始质心，选择已经选取过的初始质心最远的点。使用这种方法，确保了选择的初始质心不仅是随机的，而且是散开的。但是，这种方法可能选中离群点。

方法4：canopy算法。

本文随机选取质心，见图3：

图3

5） 距离的度量：常用的距离度量方法包括：欧几里得距离和余弦相似度。欧氏距离是最常见的距离度量，二余弦相似度是最常见的相似度度量，借助图4三维坐标系来看下欧氏距离和余弦相似度的区别：

图4：三维坐标系

从图上可以看出距离度量衡量的是空间各点间的绝对距离，跟各个点所在的位置坐标(即个体特征维度的数值)直接相关；而余弦相似度衡量的是空间向量的夹角，更加的是体现在方向上的差异，而不是位置。本文选择欧式距离来对距离进行度量，欧氏距离公式见（2）：

6） 聚类效果展示如图5：

图5

7） 聚类效果评估：Kmeans是一种非监督学习，没有标签和其他信息来比较聚类结果。从图5的结果可以清晰的看到算法具有一定的聚类效果，本文采用MCR进行验证，结果见图6

图6

多次计算平均求得的MCR= 0.66,表明误分率还是蛮大的，聚类效果并不是很理想，究其原因：虽然算法收敛，但算法只是收敛到了局部最小值，而并非全局最小值。

三．模糊K均值算法

模糊K-均值算法由K-均值算法派生而来的。K-均值算法在聚类过程中，每次得到的结果虽然不一定是预期的效果，但类别之间的边界是明确的，聚类中心根据各类当前具有的样本进行修改。模糊K-均值算法在聚类过程中，每次得到的类别边界仍是模糊的，每类聚类中心的修改都需要用到所有样本，此外聚类准则也体现了模糊性。

四．模糊K-均值算法

1.模糊K-均值算法过程

模糊K-均值算法基本思想是首先设定一些类及每个样本对各类的隶属度；然后通过迭代，不断调整隶属度至收敛。收敛条件是隶属度的变化量小于规定的阈值。具体步骤如下：

（1）
确定模式类数K，1<K≤N，N是样本个数。

（2）
根据先验知识确定样本属于各类的隶属度，建立初始隶属度矩阵U（0）=[],其中i为类别编号、矩阵的行号，j为样本编号、矩阵的列号。表示第j个元素对第i个类的隶属度。对隶属度矩阵的第j列而言，它表示第j个元素分别对各模式类的隶属度，因此矩阵的每列元素之和为1。

（3）
求各类的聚类中心L是迭代次数。见公式（3）：

式中，参数m≥2，是一个控制聚类结果模糊程度的参数。可以看出各聚类中心的计算必须用到全部的N个样本，这是与一般（非模糊）K-均值算法的区别之一。在一般（非模糊）K-均值算法中，某一类的聚类中心仅由该类样本决定，不涉及其他类。

（4）
计算新的隶属度矩阵U（K+1），矩阵元素计算如下：

式中，是第L次迭代完成时，第j个样本到第i类聚类中心的距离。为避免分母为零，特别的

5) 回到(3)求聚类中心，重复至收敛。收敛条件：

，其中为规定的参数。 (6)

当算法收敛时，就得到了各类的聚类中心以及表示个样本对各类隶属程度的隶属度矩阵，模糊聚类到此结束。这时，准则函数

达到最小。

(6) 根据隶属度矩阵U(L+1)进行聚类，按照隶属原则进行划分，即

若

.模糊K均值matlab实现

1．沿用上面用K均值聚类的的数据随机创造一组数据，见图6；

图6

2.沿用上面K均值聚类确定K值的方法确定K值，取K=3。

3.根据先验知识确定初始隶属度矩阵，利用matlab的rand（）函数初始化隶属度矩阵U（0），并归一化，见图7：

图7

其中，cluster_n为聚类中心个数，即K值，data_n为样本点数，U为隶属度矩阵。

4．模糊K均值聚类时迭代的一步：计算新的隶属度矩阵，先求样本点到聚类中心的距离d，见图8：

图8

然后利用求得的距离d，带入公式求解新的隶属度矩阵，见图9：

图9

并求得目标函数值，见图10：

图10

将新得的聚类中心和隶属度值重新分配进行下一次迭代。

5.设置隶属度最小变化量，当变化量小于这个阈值时，迭代终止，见图11：

图11

变化量小于设定阈值，跳出迭代。

3.聚类效果展示，见图12：

图12

五．总结

通过实验，我们发现K均值聚类的优缺点：

优点：

1.算法快速、简单;

2.对大数据集有较高的效率并且是可伸缩性的;

3.时间复杂度近于线性，而且适合挖掘大规模数据集。

缺点：

1.在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。

2.在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果。

3.从 K-means 算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。

一K均值聚类程序：
clear all;close
all;clc;
%% 随机生成数据
% 第一组数据
mu1=[0 0 ]; %均值
S1=[.1 0 ;0.1]; %协方差
data1=mvnrnd(mu1,S1,100); %产生高斯分布数据
%第二组数据
mu2=[1.25 1.25 ];
S2=[.1 0 ;0 .1];
data2=mvnrnd(mu2,S2,100);
% 第三组数据
mu3=[-1.25 1.25 ];
S3=[.1 0 ;0 .1];
data3=mvnrnd(mu3,S3,100);
% 显示数据
plot(data1(:,1),data1(:,2),‘b+’);
hold on;
plot(data2(:,1),data2(:,2),‘r+’);
plot(data3(:,1),data3(:,2),‘g+’);
grid on;
% 三类数据合成一个不带标号的数据类
data=[data1;data2;data3];
%% 分层聚类确定K值
eucD =pdist(data,‘euclidean’);
clustTreeEuc =linkage(eucD,‘average’);
cophenet(clustTreeEuc,eucD);
P3 = figure;clf;
[h,nodes] = dendrogram(clustTreeEuc,20);
set(gca,‘TickDir’,‘out’,‘TickLength’,[.0020],‘XTickLabel’,[]);
%% 随机产生聚类中心
N=3;%设置聚类数目
[m,n]=size(data);
pattern=zeros(m,n+1);
center=zeros(N,n);%初始化聚类中心
pattern(:,1:n)=data(:😅;
for x=1:N
center(x,:)=data( randi(300,1)😅;%第一次随机产生聚类中心
end
%% 迭代过程
while 1
distence=zeros(1,N);
num=zeros(1,N);
new_center=zeros(N,n);
for x=1:m
for y=1:N
distence(y)=norm(data(x,:)-center(y,:));%计算到每个类的距离
end
[~, temp]=min(distence);%求最小的距离
pattern(x,n+1)=temp;
end
k=0;
for y=1:N
for x=1:m
if pattern(x,n+1)== y
new_center(y,:)=new_center(y,:)+pattern(x,1:n);
num(y)=num(y)+1;
end
end
new_center(y,:)=new_center(y,:)/num(y);
if norm(new_center(y,:)-center(y,:))<0.1
k=k+1;
end
end
if k==N
break;
else
center=new_center;
end
end
[m,
n]=size(pattern);
%% 最后显示聚类后的数据
figure;
hold on;
for i=1:m
if pattern(i,n)==1
plot(pattern(i,1),pattern(i,2),‘r*’);
plot(center(1,1),center(1,2),‘ko’);
elseif pattern(i,n)==2
plot(pattern(i,1),pattern(i,2),‘g*’);
plot(center(2,1),center(2,2),‘ko’);
elseif pattern(i,n)==3
plot(pattern(i,1),pattern(i,2),‘b*’);
plot(center(3,1),center(3,2),‘ko’);
elseif pattern(i,n)==4
plot(pattern(i,1),pattern(i,2),‘y*’);
plot(center(4,1),center(4,2),‘ko’);
else
plot(pattern(i,1),pattern(i,2),‘m*’);
plot(center(4,1),center(4,2),‘ko’);
end
end
grid on;
[cidx3,cmeans3,sumd3,D3]= kmeans(data,3,‘dist’,‘sqEuclidean’);
P4 = figure;clf;
[silh3,h3] =silhouette(data,cidx3,‘sqeuclidean’);
%% 采用MCR判定聚类效果
B = pattern(:,3);
B = reshape(B,1,m);
A = [ones(1,100),2 * ones(1,100),3ones(1,100),4 * ones(1,100)];
sum = 0;
for i = 1:m
if ( A(1,i) ~= B(1,i))
sum = sum + 1;
end
end
MCR = sum / m;
fprintf(‘MCR =%d\n’,MCR);
二模糊K均值程序
function [U,
V,objFcn] = myfcm(data, c, T, m, epsm)
% fuzzy c-means
algorithm
% 输入： data： 待聚类数据，n行s列，n为数据个数，s为每个数据的特征数
% c ： 聚类中心个数
% m : 模糊系数
% 输出： U : 隶属度矩阵，c行n列，元素uij表示第j个数据隶属于第i类的程度
% V ： 聚类中心向量，c行s列，有c个中心，每个中心有s维特征
% see also :
mydist.m myplot.m
if nargin < 3
T = 100;
%默认迭代次数为100
end
if nargin < 5
epsm = 1.0e-6; %默认收敛精度
end
if nargin < 4
m = 2;
%默认模糊系数值为2
end
[n, s] = size(data);
% 初始化隶属度矩阵U(0),并归一化
U0 = rand(c, n);
temp = sum(U0,1);
for i=1:n
U0(:,i) = U0(:,i)./temp(i);
end
iter = 0;
V(c,s) = 0; U(c,n) =
0; distance(c,n) = 0;
while( iter<T )
iter = iter + 1;
% U = U0;
% 更新V(t)
Um = U0.^m;
V = Umdata./(sum(Um,2)*ones(1,s)); % MATLAB矩阵相乘啊，好东西
% 更新U(t)
for i = 1:c
for j = 1:n
distance(i,j) =
mydist(data(j,:),V(i,:));
end
end
U=1/(distance.^{m.*(ones(c,1)*sum(distance.}(-m))));
objFcn(iter) = sum(sum(Um.*distance.^2));
% FCM算法停止条件
if norm(U-U0,Inf)<epsm
break
end
U0=U;
end
myplot(U,objFcn);
function d = mydist(X,Y)
% 计算向量Y到向量X的欧氏距离的开方
d =
sqrt(sum((X-Y).^2));
end