Press "Enter" to skip to content

K-means聚类与EM算法

一:内容预告

 

今天是三月的最后一天,邓邓就不吐槽了。

 

发一篇K-means的文章,完美结束这三月。

 

四月又是新的开始,愿大家每天都有最新鲜的空气,处处都有最美丽的风景。

 

本文关注以下内容:

 

K-means的原理

 

初始类中心的选择和类别数K的确定

 

K-means和EM算法、高斯混合模型的关系

 

二:K-means的原理

 

频率学派和贝叶斯学派的区别

 

频率学派和贝叶斯学派的区别

 

频率学派和贝叶斯学派的

 

K-means(K均值聚类)是一种基于中心的聚类算法,通过迭代,将样本分到K个类中,使每个样本与其所属类中心的距离之和最小 。

 

01

 

定义损失函数

 

假设我们有一个数据集

{x 1
, x 2
,…, x N
},每个样本的特征维度是m维,我们的目标是将数据集划分为K个类别。

 

假定K值已经给定,第k个类别的中心定义为μ
k,k=1,2,…, K,μ
k是一个m维的特征向量。

 

我们需要找到每个样本所属的类别,以及一组向量{μ
k},使每个样本与其所属类别的中心μ
k的距离之和最小。

 

聚类需要根据样本之间的相似度,对样本集合进行划分,将相似度较高的样本归为一类。

 

可以通过计算样本之间的欧氏距离、马氏距离、余弦距离或相关系数,来衡量样本之间的相似度。

 

而K-means是用欧氏距离的平方来度量样本之间的相似度。欧式距离的平方公式如下:

 

 

接着, 把所有样本与所属类中心的距离平方和,定义为损失函数:

 

 

其中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最小化。

 

02

 

进行迭代

 

K-means是一种迭代算法,每次迭代涉及到两个连续的步骤,分别对应r
nk的最优化和μ
k的最优化,也对应着EM算法的E步(求期望)和M步(求极大)两步。

 

首先,为μ k
选择一些初始值,也就是初始化K个类中心。

 

然后,执行以下两个步骤,直至收敛。

 

第一步:保持μ k
固定,选择r nk
来最小化J,也就是把样本指派到与其最近的中心所属的类中,得到一个聚类结果。

 

第二步:保持r nk
固定,计算μ k
来最小化J,也就是更新每个类别的中心。

 

具体来说,也就是E步和M步:

 

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均值聚类。

 

重新为样本分配类别,再重新计算每个类别的均值,不断重复这两个步骤,直到聚类的结果不再改变。

 

需要注意以下几点:

 

K-means可能收敛到目标函数J的局部极小值,不能保证收敛到全局最小值。

 

聚类之前,需要对数据集进行标准化,使样本的均值为0,标准差为1。

 

初始类中心的选择会直接影响聚类结果,选择不同的初始类中心,可能会得到不同的聚类结果。

 

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

 

四:初始化类中心和确定类别数

 

频率学派和贝叶斯学派的区别

 

频率学派和贝叶斯学派的区别

 

K-means的思想比较简单,关键在于初始类中心的选择和类别数K的确定,这对聚类的结果有比较大的影响。

 

01

 

初始化类中心

 

(一)第一种方法

 

用层次聚类法进行初始聚类,然后把这些类中心作为K均值聚类的初始类中心。

 

层次聚类的复杂度为O(mn 3
),m是样本的特征维度,n是样本个数,复杂度也是蛮高的,那为什幺用层次聚类的结果来初始化类中心呢?

 

我想是因为层次聚类的结果,完全是由算法确定的,是一个客观的结果。这样就把K-means的初始类中心的选择问题,由主观决定变成了客观决定。

 

(二)第二种方法

 

首先随机选择一个点,作为第一个初始类中心点,然后计算该点与其他所有样本点的距离,选择距离最远的点,作为第二个初始类的中心点,以此类推,直到选出K个初始类中心点。

 

02

 

类别数K的确定

 

(一)轮廓系数

 

轮廓系数(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值。

 

(二)肘部法则

 

K-means的损失函数,是所有样本到类别中心的距离平方和J,也就是误差平方和SSE:

 

 

从类别数K=1开始,当类别数K小于真实的类别数时,随着类别数的增大,SSE会快速地下降。

 

而当类别数到达真实类别数的临界点后,SSE开始缓慢下降,也就是说SSE和K的关系曲线一个肘部形状,这个肘部所对应的K值可以认为是合适的类别数。

 

那幺我们选择不同的K值,训练多个模型,然后计算模型的SSE,选择SSE开始缓慢下降时的K值,作为聚类的类别数。

 

如下图,可以选择4或5作为聚类的类别数。

 

 

五:与EM、GMM的关系

 

频率学派和贝叶斯学派的区别

 

这一部分,需要EM算法和高斯混合模型的前置知识。

 

这篇是我在博客园上总结的:

 

《聚类之高斯混合模型与EM算法》

 

https://www.cnblogs.com/Luv-GEM/p/10851395.html

 

01

 

要点总结

 

关于K-means与EM算法、高斯混合模型的关系,
主要有以下三点:

 

1:K-means是一种非概率的聚类算法,属于硬聚类方法,即一个样本只能属于一个类(类与类之间的交集为空)。

 

相比之下,高斯混合模型(GMM)是一种基于概率的聚类算法,属于软聚类方法,每个样本按照一个概率分布,属于多个类。

 

2:K-means在一次迭代中的两个步骤,可以看做是EM算法的E步和M步。

 

而且K-means可以看做,用EM算法对⾼斯混合模型进行参数估计的⼀个特例,也就是高斯混合模型中分模型的方差σ 2
相等,为常数,且σ 2
→0时的极限情况。

 

3:K-means和基于EM算法的高斯混合模型,对参数的初始化值比较敏感。

 

由于K-means的计算量远小于基于EM算法的高斯混合模型,所以通常运⾏K-means,来找到⾼斯混合模型的⼀个初始值,再用EM算法进行调节。

 

具体而言,用K-means划分K个类别,再用各类别样本所占的比例,来初始化K个分模型的权重;用各类别中样本的均值,来初始化K个高斯分布的期望;用各类别中样本的方差,来初始化K个高斯分布的方差。

 

02

 

从图形来理解

 

为了理解以上几点,尤其是第2点,我们可以先从图形来看。

 

假设高斯混合模型由4个高斯分布混合而成,高斯分布的密度函数如下。

 

Ø(y|θ
k)是第k个高斯分布的概率密度,被称为第k个分模型,参数为θ
k=(μ
k, α
k2)。

 

令均值μ=[0,2,4,6],方差σ 2
=[1,2,3,1],则4个高斯分布的概率密度函数的图形如下。

我们可以看到,4个图形之间有重叠的部分,也就说明每个样本可以按照一个概率分布α
k,属于多个类,只是属于某类的概率大些,属于其他类的概率小些。

 

这表明高斯混合模型是一种软聚类方法。

 

然后令均值μ不变,方差σ 2
=[0.01, 0.01, 0.01, 0.01],也就是4个分模型的方差σ k2
相等,而且σ k2
→0,那幺4个高斯分布的图形如下。

 

 

每个高斯分布的图形之间没有交集,那幺每个样本只属于一个类,变成了硬聚类。

 

这也就是高斯混合模型的特例:
K-means。

 

03

 

从公式来理解

 

用EM算法对高斯混合模型进行极大似然估计,在E步,我们需要基于第i轮迭代的参数θ (i)
=(α k
, μ k
, σ k
)来计算γ jk
,γ jk
是第j个样本y j
来自于第k个高斯分布分模型的概率,k=1,2,…,K。

 

在高斯混合模型中,γ j
是一个K维的向量,也就是第j个样本属于K个类的概率。假设分模型的方差σ k2
都相等,且是一个常数,不需要再估计,那幺在EM算法的E步我们计算γ jk

 

 

考虑σ 2
→0时的极限情况,如果样本y j
属于第k类的概率最大,那幺该样本与第k类的中心点的距离非常近,(y j
– μ k
) 2
将会趋于0
,于是有:

 

 

也就是样本y j
属于第k类的概率近似为1,属于其他类别的概率近似为0,也就成为了一种硬聚类,也就是K-means。

 

其实在σ 2
→0的极限情况下,最大化高斯混合模型的完全数据的对数似然函数的期望,等价于最小化K均值聚类的目标函数J。

 

比如有4个高斯分布,样本y j
的γ j
为[0.55, 0.15, 0.2, 0.1],那幺属于第1类的概率γ j1
最大。

 

而当分模型的方差σ 2
→0时,样本y j
的γ j
可能为[0.98, 0.01, 0.005, 0.005],也就是该样本直接被分配到了第1类,成为了硬聚类。

 

附:绘图代码

 

import matplotlib.pyplot as plt
import math
import numpy as np
""" 1: 4个高斯分布的均值 """ 
u1 = 0   
u2 = 2
u3 = 4
u4 = 6
""" 2: 4个高斯分布的标准差 """
sig1 = math.sqrt(1)  
sig2 = math.sqrt(2)
sig3 = math.sqrt(3)
sig4 = math.sqrt(1)
def x(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)
""" 3: 概率密度 """ 
def y(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》

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注