聚类算法的种类介绍-白红宇的个人博客

聚类算法的种类介绍

发布日期：2021-06-29 11:41:52 浏览次数：3 分类：技术文章

本文共 4658 字，大约阅读时间需要 15 分钟。

一、原型聚类：基于原型的聚类（prototype-based clustering），假设聚类结构能通过一组原型刻画。通常情况下，算法先对原型进行初始化，然后原型进行迭代更新求解。

1、k均值聚类算法（k-mean）

给定样本集D= $\{x_{1},x_{2},x_{3},...,x_{m}\}$ ，“k-mean”算法针对聚类所得簇划分C= $\{C_{1},C_{2},C_{3},...,C_{k}\}$ 的最小化平方误差：

$E=\sum_{i=1}^{k}\sum_{x\in C_{i}}||x-\mu _{i}||_{2}^{2}$ ，其中 $\mu_{i}$ 是簇 $C_{i}$ 的均值向量，定义为 $\mu_{i} = \frac{1}{|C_{i}|}\sum _{x\in{C_{i}}}x$ .

直观上看，上式在一定程度上刻画了簇内样本围绕均值向量的紧密程度，E越小则簇内样本相似度越高。

最小化上式，找到它的最优解需要考察样本集D中多有可能的簇划分，这是一个NP难问题。因此，k-mean算法采用了贪心策略，通过迭代优化来近似求解上式。

算法流程：

（1）2个输入：样本集D= $\{x_{1},x_{2},x_{3},...,x_{m}\}$ ，聚类簇数k

（2）从D中随机选择k个样本作为初始均值向量 $\{\mu_{1},\mu_{2},\mu_{3},...,\mu_{k}\}$ ，令 $C_{i}=\varnothing$ ，i=1,2,...k初始化簇内没有元素

（3）for j =1，2，3，...，m，

计算样本 $x_{j}$ 与各均值向量 $\mu_{i}(1\leqslant i\leqslant k)$ 的距离： $d_{ji}$ 采用欧氏距离；

根据距离最近的均值向量确定 $x_{j}$ 的簇标记： $\lambda _{j}=argmin_{i\in{\{1,2,...,k\}}}d_{ji}$ ；

将样本 $x_{j}$ 划入相应的簇： $C_{\lambda_{j}} = C_{\lambda_{j}}\cup \{x_{j}\}$

（4）for i = 1，2，...，k

计算新的均值向量 $\mu_{i}^` = \frac{1}{|C_{i}|}\sum _{x\in{C_{i}}}x$ ；

如果新的均值向量不等于当前的均值向量 $\mu_{i}^`\neq \mu_{i}$ ，那么就将当前均值向量 $\mu_{i}$ 更新为 $\mu_{i}^`$ ，否则就保持当前均值向量不变

（5）重复步骤（3）和（4）直到当前均值均为更新

（6）输出：簇划分C= $\{C_{1},C_{2},C_{3},...,C_{k}\}$

性能分析：

优点：

（1）k-mean算法是解决聚类问题的一种经典算法，算法简单、快速。

（2）对处理大数据集，该算法是相对可伸缩的和高效率的，算法复杂度低，因为它的复杂度大约是O（nkt），其中n是所有对象的数目，k是簇的数目,t是迭代的次数。通常k<<n（2<k<sqrt(n)）。这个算法经常以局部最优结束。

（3）算法尝试找出使平方误差函数值最小的k个划分。当簇是密集的、球状或团状的，而簇与簇之间区别明显时，它的聚类效果很好。

缺点：

（1）k-mean方法只有在簇的平均值被定义的情况下才能使用，只能处理数值属性的数据、聚类结构可能不平衡，不适用于某些应用，如涉及有分类属性的数据不适用，如果处理符号属性的数据并不适用。

（2）要求用户必须事先给出要生成的簇的数目k，不合适的k可能返回较差的结果，对K值的选择没有准则可依循。

（3）对初值敏感，对于不同的初始值，可能会导致不同的聚类结果，由于采用迭代更新的方法，所以当初始聚类中心落在局部值最小附近时，算法容易生成局部最优解。

（4）对离群点敏感，对于"噪声"和孤立点数据敏感，少量的该类数据能够对平均值产生极大影响，一些过大的异常值会带来很大影响。

（5）不适合于发现非凸面形状的簇，或者大小差别很大的簇。

算法改进：

数据预处理

初始聚类中心选择

迭代过程中聚类种子的选择

首先，对样本数据进行归一化处理，这样就能防止某些大值属性的数据左右样本间的距离。给定一组含有n个数据的数据集，每个数据含有m个属性，分别计算每一个属性的均值、标准差对每条数据进行标准化。

其次，初始聚类中心的选择对最后的聚类效果有很大的影响，原K-means算法是随机选取k个数据作为聚类中心，而聚类的结果要是同类间尽可能相似，不同类间尽可能相异，所以初始聚类中心的选取要尽可能做到这一点。采用基于距离和的孤立点定义来进行孤立点的预先筛选，并利用两两数据之间的最大距离在剩余数据集合（去除孤立点）中寻找初始的k个聚类中心。但对于实际数据，孤立点个数往往不可预知。在选择初始聚类中心时，先将孤立点纳入统计范围（不剔除），在样本中计算对象两两之间的距离，选出距离最大的两个点作为两个不同类的聚类中心，接着从其余的样本对象中找出已经选出来的所有聚类中心的距离和最大的点为另一个聚类中心，直到选出k个聚类中心。这样做就降低了样本输入顺序对初始聚类中心选择的影响。

最后，聚类中心选好以后，就要进行不断的迭代计算，在K-means算法中，是将聚类均值点(类中所有数据的几何中心点)作为新的聚类种子进行新一轮的聚类计算，在这种情况下，新的聚类种子可能偏离真正的数据密集区，从而导致偏差，特别是在有孤立点存在的情况下，有很大的局限性。在选择初始中心点时，由于将孤立点计算在内，所以在迭代过程中要避免孤立点的影响。这里根据聚类种子的计算时，采用簇中那些与第k-1轮聚类种子相似度较大的数据，计算他们的均值点作为第k轮聚类的种子，相当于将孤立点排除在外，孤立点不参与聚类中心的计算，这样聚类中心就不会因为孤立点的原因而明显偏离数据集中的地方。在计算聚类中心的时候，要运用一定的算法将孤立点排除在计算均值点那些数据之外，这里主要采用类中与聚类种子相似度大于某一阈值的数据组成每个类的一个子集，计算子集中的均值点作为下一轮聚类的聚类种子。为了能让更多的数据参与到聚类中心的计算种去，阈值范围要包含大多数的数据。在第k-1轮聚类获得的类，计算该类中所有数据与该类聚类中心的平均距离S（平均距离即为相似度）,选择类中与聚类种子相似度大于2S的数据组成每个类的一个子集，以此子集的均值点作为第k轮聚类的聚类种子。在数据集中无论是否有明显的孤立点存在，两倍的平均距离都能包含大多数的数据。

近似的k平均算法已经被设计用于原始数据子集的计算。从算法的表现上来说，它并不保证一定得到全局最优解，最终解的质量很大程度上取决于初始化的分组。由于该算法的速度很快，因此常用的一种方法是多次运行k平均算法，选择最优解。

对孤立点的改进：

经典k均值算法中没有考虑孤立点。所谓孤立点都是基于距离的, 是数据集U中到U中最近邻居的距离最大的对象, 换言之, 数据集中与其最近邻居的平均距离最大的对象。针对经典k均值算法易受孤立点的影响这一问题, 基于距离法移除孤立点, 具体过程如下：

首先扫描一次数据集, 计算每一个数据对象与其临近对象的距离（最近邻的k个）, 累加求其距离和, 并计算出距离和均值。如果某个数据对象的距离和大于距离和均值, 则视该点为孤立点。把这个对象从数据集中移除到孤立点集合中, 重复直到所有孤立点都找到。最后得到新的数据集就是聚类的初始集合。

对随机选取初始聚类中心的改进：

经典k均值算法随机选取k个点作为初始聚类中心进行操作。由于是随机选取, 则变化较大, 初始点选取不同, 获得聚类的结果也不同，并且聚类分析得到的聚类的准确率也不一样。对k均值算法的初始聚类中心选择方法—随机法进行改进, 其依据是聚类过程中相同聚类中的对象是相似的, 相异聚类中的对象是不相似的。因此提出了一种基于数据对象两两间的距离来动态寻找并确定初始聚类中心的思路, 具体过程如下：

首先，整理孤立点集合为 $A_{0}$ ，在对剔除孤立点后的数据集U操作。令m=1，比较数据集中所有数据对象两两之间的距离。找出距离最近的2个数据对象形成集合 $A_{m}$ ；比较 $A_{m}$ 中每一个数据对象与数据对象集合U中每一个对象的距离，在U中找出与 $A_{m}$ 中最近的数据对象,优先吸收到 $A_{m}$ 中，直到 $A_{m}$ 中的数据对象个数到达一定数值，然后令m=m+1。

然后，从剩下的U中找到对象两两间距离最近的2个数据对象构成 $A_{m}$ ，重复上面的过程,直到形成k个对象集合（最后m=k）。这些集合内部的数据是相似的，而集合间是相异的。可以看出，这种聚类方法同时满足以下2个条件:①每个组至少包含一个数据对象; ②每个数据对象必须属于且仅属于一个组。即数据对象 $x_{i}\in {A_{i}}$ ，且U= $\{\{A_{1}\cup {A_{2}}\cup ...\cup {A_{k-1}}\cup {A_{k}}\}\cup {A_{0}}\}$ ,且 $A_{i}\cap{A_{j}}$ =Φ。最后对k个对象集合分别进行算术平均,形成k个初始聚类中心。

解析：A选项笔者不太清楚还没有确切理解，有理解的请留言指教！，查询网上有两种说法，“估计说的是用了online-learning策略的变异kmeans算法。原始的静态kmeans对输入顺序不敏感，静态指训练数据固定。对正常的K-means，或者说batch K-means，样本的顺序肯定是不会对结果有影响的，甚至中间步骤的结果也是没有影响的”，和另一种说法“K-Means算法选取前K个点为中心,数据输入顺序不同,选取的K个中心点就不同,因此聚类结果不同.这个的根源还是K-Means算法对初始聚类中心的敏感性”。B选项模式相似性测度我认为是表达簇内相似性高，簇间相异性越大的意思或者是表达数据是密集的、球状或团状的。C选项的聚类准则，思想只讲到最小化平方误差，但是算法里面并未具体说到，不是主要因素。D选项是主要因素，初始中心点的选取非常重要。

2、LVQ算法（学习向量量化Learning Vector Quantization）

LVQ假设数据样本带有类别标记，学习过程利用样本的这些监督信息来辅助聚类。

给定样本集D= $\{(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{m},y_{m})\}$ ，每个样本 $x_{j}$ 是由n个属性描述的特征向量 $(x_{j1},x_{j2},x_{j3},...,x_{jn})$ ， $y_{j}\in{\Upsilon }$ 是样本 $x_{j}$ 的类别标记。LVQ算法的目标是学习一组n维原型向量 $\{p_{1},p_{2},...,p_{q}\}$ ，每个原型向量代表一个聚类簇，簇标记 $t_{i}\in\Upsilon$ .

算法流程：

（1）4个输入：样本集D= $\{(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{m},y_{m})\}$ ；原型向量个数q；各原型向量预设的类别标记 $\{t_{1},t_{2},...,t_{q}\}$ ；学习率 $\eta \in{(0,1)}$

（2）对原型向量随机初始化 $\{p_{1},p_{2},...,p_{q}\}$ ，通常初始化为数据集中的样本，例如对第q个簇可以从类别标记为 $t_{q}$ 的样本中随机抽取一个作为原型向量。

（3）对原型向量进行迭代优化。从样本数据集D中随机抽取一个有标记的训练样本，找出与其距离最近的原型向量。

（4）根据两者的类别标记对当前的原型向量进行相应的更新：对样本 $(x_{j},y_{j})$ ，若最近的原型向量 $p_{i^*}$ (因为所有原型向量 $p_{i}$ 中距离最近的原型向量，加星号表示)与 $x_{j}$ 的类别标记相同即 $t_{i^*}=y_{j}$ ，则令 $p_{i^*}$ 向 $x_{j}$ 的方向靠拢，更新当前的原型向量为 $p^`=p_{i^*}+\eta (x_{j}-p_{i^*})$ ；

若类别标记不相同，则令 $p_{i^*}$ 向 $x_{j}$ 的方向远离，更新当前的原型向量为：

$p^`=p_{i^*}-\eta (x_{j}-p_{i^*})$

（5）若算法的停止条件已满足则停止对原型向量迭代更新，例如已经达到最大迭代步数，或原型向量更新很小甚至不再更新。

（6）输出：原型向量 $\{p_{1},p_{2},...,p_{q}\}$

3、高斯混合聚类（Mixture-of-Gaussian）

和k-mean、LVQ用原型向量来刻画聚类结构不同，高斯混合聚类采用概率模型（高斯分布）来表达聚类原型，簇划分则由圆形对应后验概率确定。

高斯分布完全由均值向量和协方差矩阵这两个参数确定。高斯混合分布共由k个混合成分组成，每个混合成分对应一个高斯分布，其中 $\mu _{i}$ 和 $\Sigma _{i}$ 是第i个高斯混合成分的参数，而 $\alpha _{i}>0$ 为相应的“混合系数”， $\sum_{i=1}^{k}\alpha _{i}=1$ 。