这篇博客整顿K均值聚类的内容，包罗：

1、K均值聚类的道理；

2、初始类中间的挑选和种别数K的肯定；

3、K均值聚类和EM算法、高斯夹杂模子的干系。

一、K均值聚类的道理

K均值聚类（K-means）是一种基于中间的聚类算法，经由历程迭代，将样本分到K个类中，使得每一个样本与其所属类的中间或均值的间隔之和最小。

1、界说丧失函数

假定我们有一个数据集｛x₁, x₂,..., x_N｝，每一个样本的特性维度是m维，我们的目的是将数据集离别为K个种别。假定K的值已给定，那末第k个种别的中间界说为μ_k，k=1,2,..., K，μ_k是一个m维的特性向量。我们须要找到每一个样本所属的种别，以及一组向量｛μ_k｝，使得每一个样本与它所属的种别的中间μ_k的间隔平方和最小。

起首，这个间隔是甚么间隔呢？聚类须要依据样本之间的类似度，对样本鸠合举行离别，将类似度较高的样本归为一类。器量样本之间类似度的要领包罗盘算样本之间的欧氏间隔、马氏间隔、余弦间隔或相干系数，而K均值聚类是用欧氏间隔的平方来器量样本之间的类似度。欧式间隔的平方公式以下：

把一切样本与所属类的中间之间间隔的平方之和界说为丧失函数：

个中r_nk∈{0,1}，n=1,2,...,N，k=1,2,...,K，若是r_nk=1，那末透露表现样本x_n属于第k类，且关于j≠k，有r_nj=0，也就是样本x_n只能属于一个种别。

因而我们须要找到｛r_nk｝和｛μ_k｝的值，使得间隔平方之和J最小化。

2、举行迭代

K均值聚类的算法是一种迭代算法，每次迭代涉及到两个一连的步调，离别对应r_nk的最优化和μ_k的最优化，也对应着EM算法的E步（求希冀）和M步（求极大）两步。

起首，为μ_k挑选一些初始值，也就是挑选K个类中间。然后第一步：连结μ_k流动，挑选r_nk来最小化J，也就是把样本指派到与其近来的中间所属的类中，获得一个聚类效果；第二步：连结r_nk流动，盘算μ_k来最小化J，也就是更新每一个种别的中间。赓续反复这两个步调直到收敛。

详细来说：

E步：在类中间μ_k已肯定的状况下，最优化r_nk

这一步对照简单，我们能够对每一个样本x_n独登时举行最优化。将某个样本分派到第k个种别，若是这个样本和第k个种别的间隔最小，那末令r_nk=1。对N个样本都如许举行分派，天然就获得了使一切样本与类中间的间隔平方和最小的｛r_nk｝，从而获得了一个聚类效果。

M步：肯定了数据集的一种离别，也就是｛r_nk｝肯定后，最优化μ_k

目的函数J是μ_k的一个二次函数，令它关于μ_k的导数为零，便能够使目的函数抵达最小值，即

解出μ_k的效果为：

这个μ_k就是种别k中一切样本的均值，以是把这个算法称为K均值聚类。

从新为样本分派种别，再从新盘算每一个种别的均值，赓续反复这两个步调，直到聚类的效果不再转变。

须要注重以下几点：

①K均值聚类算法能够收敛到目的函数J的局部极小值，不克不及包管收敛到全局最小值；

②在聚类之前，须要对数据集举行标准化，使得每一个样本的均值为0，标准差为1；

③初始类中间的挑选会直接影响聚类效果，挑选分歧的初始类中间，能够会获得分歧的聚类效果。

④K均值聚类算法的复杂度是O(mnk)，m是样本的特性维度，n是样本个数，k是种别个数。

二、初始类中间的挑选和种别数K的肯定

K均值聚类算法的头脑对照简单，不涉及到甚么数学知识，症结点在于初始类中间的挑选和种别数K的肯定，这对聚类的效果有对照大的影响。

（一）初始类中间的挑选

1、第一种要领

用条理聚类算法举行初始聚类，然后用这些种别的中间作为K均值聚类的初始类中间。条理聚类的复杂度为O(mn³)，m是样本的特性维度，n是样本个数，复杂度也是蛮高的，那为甚么用条理聚类的效果作为初始类呢？我想是因为条理聚类的效果完整是由算法肯定的，完整没有人工的干涉干与，是一个客观的效果，如许就把K均值聚类的初始类挑选题目，由主观肯定变成了客观决议。

2、第二种要领

起首随机挑选一个点作为第一个初始类中间点，然后盘算该点与其他一切样本点的间隔，挑选间隔最远的点作为第二个初始类的中间点，以此类推，直到选出K个初始类中间点。

（二）种别数K的肯定

1、表面系数

表面系数（Silhouette Coefficient）能够用来判定聚类效果的优劣，也能够用来肯定种别数K。好的聚类要包管种别内部样本之间的间隔尽量小（麋集度），而类与类之间样本的间隔尽量大（离散度），表面系数就是一个用来器量类的麋集度和离散度的综合目标。

表面系数的盘算历程和运用以下：

①盘算样本x_i到同类C_k其他样本的均匀间隔a_i，将a_i称为样本x_i的簇内不类似度，a_i越小，申明样本x_i越应该被分派到该类。

②盘算样本x_i到其他类C_j一切样本的均匀间隔b_ij，j=1, 2 ,..., K，j≠k，称为样本x_i与种别C_j的不类似度。界说样本x_i的簇间不类似度：b_i =min{b_i1, b_i2, ...,b_ij,..., b_iK}，j≠k，b_i越大，申明样本x_i越不属于其他簇。

③根据样本x_i的簇内不类似度a_i和簇间不类似度b_i，界说样本x_i的表面系数s_i，作为样本x_i分类效果的公道性的器量。

④表面系数范围在[-1,1]之间，该值越大，聚类效果越好。s_i靠近1，则样本x_i被分派到种别C_k的效果对照公道；s_i靠近0，申明样本x_i在两个类的界限上；s_i靠近-1，申明样本x_i更应该被分派到其他种别。

⑤盘算一切样本的表面系数s_i的均值，获得聚类效果的表面系数S，作为聚类效果公道性的器量。表面系数越大，聚类效果越好。

⑥运用分歧的K值举行K均值聚类，盘算各自聚类效果的表面系数S，挑选较大的表面系数所对应的K值。

2、肘部轨则

K均值聚类的丧失函数是一切样本到种别中间的间隔平方和J，也就是偏差平方和SSE：

从种别数K=1最先，一最先跟着种别数的增大，且种别数K小于实在的种别数时，SSE会疾速地下落。而当种别数抵达实在种别数的临界点后，SSE最先迟缓下落，也就是说SSE和K的干系是一个肘部外形，这个肘部所对应的K值能够认为是适宜的种别数。  
那末我们挑选分歧的K值，用K均值聚类练习多个模子，然后盘算模子的SSE，挑选SSE最先迟缓下落时的K值作为聚类的种别数。以下图，能够挑选4或5作为聚类的种别数。

三、K均值聚类与高斯夹杂模子的干系

关于K均值聚类与EM算法、高斯夹杂模子的干系，主要有以下三点：

1、K均值聚类是一种非几率的聚类算法，属于硬聚类要领，也就是一个样本只能属于一个类（类与类之间的交集为空）。相比之下，高斯夹杂模子（GMM）是一种基于几率的聚类算法，属于软聚类要领，每一个样本依照一个几率散布，属于多个类。

2、K均值聚类在一次迭代中的两个步调，能够看作是EM算法的E步和M步，并且K均值聚类能够看作是用EM算法对⾼斯夹杂模子举行参数预计的⼀个惯例，也就是高斯夹杂模子平分模子的方差σ²相称，为常数，且σ²→0时的极限状况。

3、K均值聚类和基于EM算法的高斯夹杂模子，对参数的初始化值对照敏感，因为K均值聚类的盘算量远小于基于EM算法的高斯夹杂模子，以是一般运⾏K均值算法找到⾼斯夹杂模子的⼀个初始化值，再运用EM算法举行调治。详细而言，用K均值聚类离别的K个种别中，各种别中样本所占的比例，来初始化K个分模子的权重；用各种别中样本的均值来初始化K个高斯散布的希冀；用各种别中样本的方差来初始化K个高斯散布的方差。

（一）从图形来明白

为了明白以上这几点，尤其是第2点，我们能够先从图形来看。假定高斯夹杂模子由4个高斯散布夹杂而成，高斯散布的密度函数以下。这里和《聚类之高斯夹杂模子与EM算法》的符号透露表现一致，y为样本。

令均值μ=[0,2,4,6]，方差σ²=[1,2,3,1]，则4个高斯散布的几率密度函数的图形以下。我们能够看到，4个图形之间有堆叠的局部，也就申明每一个样本能够依照一个几率散布α_k，属于多个类，只是属于某类的几率大些，属于其他类的几率小些。这表明高斯夹杂模子是一种软聚类要领。

然后令均值μ稳定，方差σ²=[0.01, 0.01, 0.01, 0.01]，也就是4个分模子的方差σ_k²相称，并且σ_k²→0，那末4个高斯散布的图形以下。每一个高斯散布的图形之间没有交集，那末每一个样本只能属于一个类，变成了硬聚类。这也就是高斯夹杂模子的惯例：K均值聚类。

（二）从公式来明白

用EM算法对高斯夹杂模子举行极大似然预计，在E步，我们须要基于第i轮迭代的参数θ⁽ⁱ⁾=(α_k, μ_k, σ_k)来盘算γ_jk，γ_jk是第j个样本y_j来自于第k个高斯散布分模子的几率，k=1,2,...,K。在高斯夹杂模子中，γ_j是一个K维的向量，也就是第j个样本属于K个类的几率。假定分模子的方差σ_k²都相称，且是一个常数，不须要再预计，那末在EM算法的E步我们盘算γ_jk

斟酌σ²→0时的极限状况，若是样本y_j属于第k类的几率最大，那末该样本与第k类的中间点的间隔异常近，(y_j - μ_k)²将会趋于0，因而有：

也就是样本y_j属于第k类的几率近似为1，属于其他种别的几率近似为0，也就成为了一种硬聚类，也就是K均值聚类。

其实在σ²→0时的极限状况下，最大化高斯夹杂模子的完整数据的对数似然函数的希冀，等价于最小化K均值聚类的目的函数J。

好比有4个高斯散布，样本y_j的γ_j为[0.55, 0.15, 0.2, 0.1]，那末属于第1类的几率γ_j1最大。而当分模子的方差σ²→0时，样本y_j的γ_j能够为[0.98, 0.01, 0.005, 0.005]，也就是该样本直接被分派到了第1类，成为了硬聚类。

附：4个高斯散布的几率密度函数的图形代码

importmatplotlib.pyplot as pltimportmathimportnumpy as np#均值
u1 =0   

u2= 2u3= 4u4= 6

#标准差
sig1 = math.sqrt(1)  

sig2= math.sqrt(2)

sig3= math.sqrt(3)

sig4= math.sqrt(1)defx(u,sig):return np.linspace(u - 5*sig, u + 5*sig, 100)



x1=x(u1,sig1)

x2=x(u2,sig2)

x3=x(u3,sig3)

x4=x(u4,sig4)#几率密度
defy(x,u,sig):return np.exp(-(x - u) ** 2 /(2* sig**2))/(math.sqrt(2*math.pi)*sig)



y1=y(x1,u1,sig1)

y2=y(x2,u2,sig2)

y3=y(x3,u3,sig3)

y4=y(x4,u4,sig4)



plt.plot(x1,y1,"r-")

plt.plot(x2, y2,"g-")

plt.plot(x3, y3,"b-")

plt.plot(x4, y4,"m-")

plt.xticks(range(-6,16,2))



plt.show()

参考资料：

1、李航：《统计学习要领》（第二版）

2、《Pattern Recognition and Machine Learning》

3、https://www.jianshu.com/p/335b376174d4