聚类分析学习笔记(一)

此笔记参考了数据挖掘导论、周志华的机器学习以及机器学习实战三本书

1.概要

聚类分析的作用是根据在数据中发现的描述对象及其关系的信息，将数据分组（簇）。组内的对象相互之间是相似的（相关的），而不同组中的对象是不同的（不相关的）。组内的相似性越大，组间的差别越大，则聚类就越好。

因为聚类分析是无标记学习，所以是一种非监督学习。聚类分好几种类型，本文中主要涉及基于原型的聚类，基于层次的聚类以及基于密度的聚类。

2.基于原型的聚类

假设聚类结构能通过一组原型刻画。其中簇是对象的集合，其中每个对象到定义该簇的原型的距离比到其他簇的原型的距离更近（或者更加相似）。我们通常把基于原型的簇看做基于中心的簇。基于原型的聚类通常步骤是：算法先对原型进行初始化，然后对原型进行迭代更新求解。不同的原型聚类算法会采用不同的原型表达方式或不同的求解方式等等。

2.1 K-means算法

K-means是一种基于距离的迭代式算法。它将n个观察实例分类到k个聚类中，以使得每个观察实例距离它所在的聚类的中心点比其他的聚类中心点的距离更小。

给定样本D={x1,x2,x3,…,xm}，K-means算法针对聚类所得划分簇C={C1,C2,…,Ck}最小化平方误差：

E=∑i=1k∑xεCi||x−μi||2

其中 μi=1/|Ci|∑xεCix 是簇 Ci 的均值向量。为了得到最小化平方误差，K-means算法采用了迭代优化来近似求解目标式。

伪代码如下：

input: 样本集：D={x1,x2,x3,...,xm}； 聚类簇数：k 过程： 从D中随机选择k个样本作为初始均值向量{u1，u2,...,uk} repeat: 令Ci=空集(1<=i<=k) for j=1,2,...,m do 计算xj与各均值向量ui(1<=i<=k)的距离：d_ji 将样本xj划入距离最近的均值向量相应的簇 end for for i=1,2,...,k do 计算新的均值向量ui' if ui不等于ui' 将当前的均值向量ui更新为ui' else 保持当前均值不变 end if end for until 当前均值向量均未更新 output: 簇划分C={C1,C2,...,Ck}

2.2 学习向量量化(LVQ)

学习向量量化是也是试图找到一组原型来刻画聚类结构，但LVQ是假设数据样本带有类别标记，学习过程利用样本的这些监督信息来辅助聚类，可看作通过聚类来形成类别的子类结构，每个子类对应一个聚类簇。

LVQ的目标是学习到一组原型向量{p1,p2,…,pk}，每个原型向量代表一个聚类簇，簇标记{t1,t2,…,tk}

给定样本集D={(x1,y1),(x2,y2),…,(xm,ym)}；原型向量个数，各原型向量的类别标记，学习率η。

算法首先初始化一组原型向量，可以从该类别中随机选取一个向量作为原型向量。初始化完成之后，开始迭代过程，每次从样本集中选取一个样本（xi,yi），将这个样本划分到距离它最近的原型向量p所在的簇中。

如果这两个向量的类别标记相同那么更新p为:p=p+η∗(x−p), 若类别标记不相同，更新p为:p=p−η∗(x−p)

直观上来看，若类别标记相同，原型向量向x的方向靠拢，否则远离。算法的停止条件是达到最大迭代轮数或者原型向量更新很小。

2.3 高斯混合聚类

高斯混合聚类是采用概率模型来表达聚类原型。高斯混合聚类具体步骤可以用EM方法来表示。

高斯模型的概率密度函数记为 p(x|μi,∑i)

高斯混合分布定义为： pm(x)=∑ki=1ϕi⋅p(x|μi,∑i)

E-step:

对于第i个样本xi 来说，它由第j个高斯模型生成的概率为：

M-step:

重复上述两步骤直到算法收敛。