聚类之K均值聚类和EM算法,聚类之高斯夹杂模子与EM算法

2019年7月2日11:04:18聚类之K均值聚类和EM算法,聚类之高斯夹杂模子与EM算法已关闭评论 271

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

1、K均值聚类的道理;

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

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

 

一、K均值聚类的道理

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

1、界说丧失函数

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

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

聚类之K均值聚类和EM算法,聚类之高斯夹杂模子与EM算法

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

聚类之K均值聚类和EM算法,聚类之高斯夹杂模子与EM算法

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

因而我们须要找到{rnk}和{μk}的值,使得间隔平方之和J最小化。

2、举行迭代

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

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

详细来说:

E步:在类中间μk已肯定的状况下,最优化rnk

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

聚类之K均值聚类和EM算法,聚类之高斯夹杂模子与EM算法

M步:肯定了数据集的一种离别,也就是{rnk}肯定后,最优化μk

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

聚类之K均值聚类和EM算法,聚类之高斯夹杂模子与EM算法

解出μk的效果为:

聚类之K均值聚类和EM算法,聚类之高斯夹杂模子与EM算法

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

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

须要注重以下几点:

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

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

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

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

 

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

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

(一)初始类中间的挑选

1、第一种要领

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

2、第二种要领

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

(二)种别数K的肯定

1、表面系数

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

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

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

②盘算样本xi到其他类Cj一切样本的均匀间隔bij,j=1, 2 ,..., K,j≠k,称为样本xi与种别Cj的不类似度。界说样本xi簇间不类似度:bi =min{bi1, bi2, ...,bij,..., biK},j≠k,bi越大,申明样本xi越不属于其他簇。

据样本xi的簇内不类似度ai和簇间不类似度bi,界说样本xi的表面系数si,作为样本xi分类效果的公道性的器量。

聚类之K均值聚类和EM算法,聚类之高斯夹杂模子与EM算法

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

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

聚类之K均值聚类和EM算法,聚类之高斯夹杂模子与EM算法

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

2、肘部轨则

K均值聚类的丧失函数是一切样本到种别中间的间隔平方和J,也就是偏差平方和SSE:
聚类之K均值聚类和EM算法,聚类之高斯夹杂模子与EM算法
从种别数K=1最先,一最先跟着种别数的增大,且种别数K小于实在的种别数时,SSE会疾速地下落。而当种别数抵达实在种别数的临界点后,SSE最先迟缓下落,也就是说SSE和K的干系是一个肘部外形,这个肘部所对应的K值能够认为是适宜的种别数。  
那末我们挑选分歧的K值,用K均值聚类练习多个模子,然后盘算模子的SSE,挑选SSE最先迟缓下落时的K值作为聚类的种别数。以下图,能够挑选4或5作为聚类的种别数。
聚类之K均值聚类和EM算法,聚类之高斯夹杂模子与EM算法

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

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

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

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

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

(一)从图形来明白

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

聚类之K均值聚类和EM算法,聚类之高斯夹杂模子与EM算法

 聚类之K均值聚类和EM算法,聚类之高斯夹杂模子与EM算法

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

聚类之K均值聚类和EM算法,聚类之高斯夹杂模子与EM算法

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

聚类之K均值聚类和EM算法,聚类之高斯夹杂模子与EM算法

(二)从公式来明白

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

聚类之K均值聚类和EM算法,聚类之高斯夹杂模子与EM算法

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

聚类之K均值聚类和EM算法,聚类之高斯夹杂模子与EM算法

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

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

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

 

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

import matplotlib.pyplot as plt
import math
import numpy as np

# 均值
u1 = 0   
u2 = 2
u3 = 4
u4 = 6

# 标准差
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)

# 几率密度
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》

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

avatar