机器学习之聚类常用方法_机器学习 聚类

基于划分的聚类

通过将对象划分为互斥的簇进行聚类， 每个对象属于且仅属于一个簇，划分结果旨在使簇之间的相似性低，簇内部的相似度高，基于划分的方法常用算法有k均值、k-medoids、k-prototype等。

K均值算法

k-均值聚类是基于划分的聚类算法，计算样本点与类簇质心的距离，与类簇质心相近的样本点划分为同一类簇。k-均值通过样本间的距离来衡量它们之间的相似度，两个样本距离越远，则相似度越低，否则相似度越高
k-均值算法聚类步骤如下：

1. 首先选取?个类簇（?需要用户进行指定）的质心，通常是随机选取。
2. 对剩余的每个样本点，计算它们到各个质心的欧式距离，并将其归入到相互间距离最小的质心所在的簇，计算各个新簇的质心。
3. 在所有样本点都划分完毕后，根据划分情况重新计算各个簇的质心所在位置，然后迭代计算各个样本点到各簇质心的距离，对所有样本点重新进行划分。
4. 重复第（2）步和第（3）步, 直到迭代计算后，所有样本点的划分情况保持不变，此时说明k-均值算法已经得到了最优解，将运行结果返回。

优缺点：

1. k-均值算法原理简单，容易实现，且运行效率比较高。
2. k-均值算法聚类结果容易解释，适用于高维数据的聚类。
3. k-均值算法采用贪心策略，导致容易局部收敛，在大规模数据集上求解较慢。
4. k-均值算法对离群点和噪声点非常敏感，少量的离群点和噪声点可能对算法求平均值产生极大影响，从而影响聚类结果。
5. k-均值算法中初始聚类中心的选取也对算法结果影响很大，不同的初始中心可能会导致不同的聚类结果。对此，研究人员提出k-均值++算法，其思想是使初始的聚类中心之间的相互距离尽可能远。

---

k均值++算法

1. 从样本集?中随机选择一个样本点?_1作为第1个聚类中心；
2. 计算其它样本点?到最近的聚类中心的距离?(?)；
3. 以概率T选择一个新样本点?_?加入聚类中心点集合中，其中距离值?(?)越大，被选中的可能性越高；
   
4. 重复步骤(2)和(3)选定k个聚类中心；
5. 基于这k个聚类中心进行k均值运算

注意

k均值算法不适用于非凸面形状（非球形）的数据集，例如图中例子，k均值算法的聚类结果就与初始目标有非常大的差别。

使k-均值聚类时，需要注意如下问题：

1. 模型的输入数据为数值型数据（如果是离散变量，需要作哑变量处理，需要将原始数据作标准化处理，防止不同量纲对聚类产生影响）
2. 对k值的选取，主要有以下几种：（1）与层次聚类算法结合，先通过层次聚类算法得出大致的聚类数目，并且获得一个初始聚类结果，然后再通过k均值算法改进聚类结果。（2）基于系统演化的方法，将数据集视为伪热力学系统，在分裂和合并过程中，将系统演化到稳定平衡状态从而确定k值

---

k-medoids算法

k-均值算法簇的聚类中心选取受到噪声点的影响很大，因为噪声点与其他样本点的距离远，在计算距离时会严重影响簇的中心。

k-medoids 算法克服了k-均值算法的这一缺点， k -medoids算法不通过计算簇中所有样本的平均值得到簇的中心，而是通过选取原有样本中的样本点作为代表对象代表这个簇（就像平均数和中位数的差异，k-mdeoids就好比取中位数），计算剩下的样本点与代表对象的距离，将样本点划分到与其距离最近的代表对象所在的簇中。

距离计算过程与k均值算法的计算过程类似，只是将距离度量中的中心替换为代表对象。：

---

k-prototype算法

k-prototype算法的聚类过程与k-均值算法相同，只是在聚类过程中引入参数?来控制数值属性和分类属性的权重。对于?维样本：

其中标号为1至?下标的属性为数值型，?+1到?下标的属性为分类型。

定义样本与簇的距离为:

其中，??? ^r 和??? ^c 分别是?_?第?个属性的数值属性取值和分类属性取值，?_?? ^ ?和?_?? ^ ? 分别是聚类?的原型?_?的数值属性取值和分类属性取值，?为符号函数。

---

基于层次的聚类

层次聚类的应用广泛程度仅次于基于划分的聚类，核心思想就是通过对数据集按照层次，把数据划分到不同层的簇，从而形成一个树形的聚类结构。

层次聚类算法可以揭示数据的分层结构，在树形结构上不同层次进行划分，可以得到不同粒度的聚类结果。按照层次聚类的过程分为自底向上的聚合聚类和自顶向下的分裂聚类。聚合聚类以AGNES、BIRCH、ROCK等算法为代表，分裂聚类以DIANA算法为代表。

自底向上的聚合聚类将每个样本看作一个簇，初始状态下簇的数目等于样本的数目，然后根据算法的规则对样本进行合并，直到满足算法的终止条件。

自顶向下的分裂聚类先将所有样本看作属于同一个簇，然后逐渐分裂成更小的簇，直到满足算法终止条件为止。

---

BIRCH算法

BIRCH（Balanced Iterative Reducing and Clustering using Hierarchies）算法的全称是：利用层次方法的平衡迭代规约和聚类。

BIRCH算法克服了?-均值算法需要人工确定?值，且?值的选取对于聚类结果影响较大的缺点。BIRCH算法的?值设定是可选择的，默认情况下不需要选取。BIRCH算法只需要对数据集扫描一次就可以得出聚类结果，因此在大规模数据集情况下速度快。

BIRCH算法的核心就是构建一个聚类特征树（Clustering Feature Tree，CF-Tree），聚类特征树的每一个节点都是由若干个聚类特征（??）组成的

CF-Tree中包含三个重要的变量：枝平衡因子?，叶平衡因子?，空间阈值?。

• 其中，平衡因子?表示每个非叶节点包含最大的??数为?

• 叶平衡因子?表示每个叶节点包含最大的??数为?

• 空间阈值?表示叶节点每个??的最大样本空间阈值，也就是说在叶节点??对应子簇中的所有样本点，一定要在半径小于?的一个超球体内。
  构建CF-Tree的过程为：

• 选择第一个样本点作为根节点

• 从根节点开始，依次选择最近的子节点，到达叶节点后

• if 查该数据点是否能够直接插入最近的元组??

• 更新??值

• else if可以直接在当前节点添加一个新的元组

• 添加一个新的元组

• else分裂最远的元组，按最近距离重新分配其它元组

• 更新每个非叶节点的??信息，如果分裂节点，在父节点中插入新的元组，检查分裂，直到根节点

如图所示：
在最开始的时候，CF Tree是空的，没有任何样本，我们从训练集读入第一个样本点，将它放入一个新的CF三元组A，这个三元组的N=1，将这个新的CF放入根节点，此时的CF Tree如下图

现在我们继续读入第二个样本点，我们发现这个样本点和第一个样本点A，在半径为T的超球体范围内，也就是说，他们属于一个CF，我们将第二个点也加入CF A,此时需要更新A的三元组的值。此时A的三元组中N=2。此时的CF Tree如下图：

此时来了第三个节点，结果我们发现这个节点不能融入刚才前面的节点形成的超球体内，也就是说，我们需要一个新的CF三元组B，来容纳这个新的值。此时根节点有两个CF三元组A和B，此时的CF Tree如下图：

来到第四个样本点的时候，我们发现和B在半径小于T的超球体，这样更新后的CF Tree如下图：

叶子节点LN1有三个CF， LN2和LN3各有两个CF。我们的叶子节点的最大CF数L=3。此时一个新的样本点来了，我们发现它离LN1节点最近，因此开始判断它是否在sc1,sc2,sc3这3个CF对应的超球体之内，但是很不幸，它不在，因此它需要建立一个新的CF，即sc8来容纳它。

我们将LN1里所有CF元组中，找到两个最远的CF做这两个新叶子节点的种子CF，然后将LN1节点里所有CF sc1, sc2, sc3，以及新样本点的新元组sc8划分到两个新的叶子节点上。将LN1节点划分后的CF Tree如下图：

如果我们的内部节点的最大CF数B=3，则此时叶子节点一分为二会导致根节点的最大CF数超了，也就是说，我们的根节点现在也要分裂，分裂的方法和叶子节点分裂一样，分裂后的CF Tree如下图：

---

CURE算法

CURE算法属于层次聚类中的凝聚聚类，但是与传统的聚类算法选择一个样本点或者中心来代表一个簇的方法不同。

CURE算法采用多个点代表一个簇的方法，选择数据空间中固定数目且具有代表性的点，在处理大数据量的时候采用了随机取样，分区的方法，来提高其效率，使其可以高效地处理大量数据。

每个簇的代表点产生过程中，首先选择簇中分散的对象，然后根据收缩因子对这些分散的对象进行收缩，使之距离更紧密，更能代表一个簇的中心。

CURE算法采用了随机抽样和分割的方法，将样本分割后对每个部分进行聚类，最终将子类聚类结果合并得到最终聚类结果，通过随机抽样和分割可以降低数据量，提高算法运行效率。

CURE算法的基本步骤如下：

1. 对原始数据集进行抽样，得到一个用于聚类的样本。
2. 将得到的样本进行分割处理，得到?个分区，每个分区的大小为?/?。
3. 对?个分区中的每一个分区，进行局部的凝聚聚类。
4. 去除异常值。主要有以下两种方式：（a）在聚类过程中，由于异常值与其他对象的距离大，因此其所在簇的对象数量增长缓慢，将此类对象去除。（b）在聚类过程完成后，对于簇中对象数目异常小的簇，将其视作异常去除。
5. 将步骤（3）中发现各分区的代表点作为输入，由固定个数的代表点经过收缩后表示各个簇，对整个原始数据集进行聚类。其中，代表点收缩是通过收缩因子α实现，0<α<1, α越大得到的簇更紧密。反之，簇之间更稀松，可以区分异形（如拉长）的簇。

CURE算法采用多个代表点来表示一个簇，使得在非球状的数据集中，簇的外延同样能够扩展，因此CURE算法可以用于非球状数据集的聚类。

在选取代表点的过程中，使用收缩因子减小了异常点对聚类结果的影响，因此CURE算法对噪声不敏感。CURE 算法采用随机抽样与分割相结合的办法来提高算法的空间和时间效率。

但是CURE 算法得到的聚类结果受参数的影响比较大，包括采样的大小、聚类的个数、收缩的比例等参数。

---

基于密度聚类

基于划分聚类和基于层次聚类的方法在聚类过程中根据距离来划分类簇，因此只能够用于挖掘球状簇。

为了解决这一缺陷，基于密度聚类算法利用密度思想，将样本中的高密度区域(即样本点分布稠密的区域)划分为簇，将簇看作是样本空间中被稀疏区域(噪声)分隔开的稠密区域。这一算法的主要目的是过滤样本空间中的稀疏区域，获取稠密区域作为簇。

基于密度的聚类算法是根据密度而不是距离来计算样本相似度，所以基于密度的聚类算法能够用于挖掘任意形状的簇，并且能够有效过滤掉噪声样本对于聚类结果的影响。

常见的基于密度的聚类算法有DBSCAN、OPTICS和DENCLUE等。其中，OPTICS 对DBSCAN算法进行了改进，降低了对输入参数的敏感程度。DENCLUE算法综合了基于划分、基于层次的方法。

---

DBSCAN算法[参考百度百科]

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）采用基于中心的密度定义，样本的密度通过核心对象在?半径内的样本点个数（包括自身）来估计。

DBSCAN算法基于领域来描述样本的密度，输入样本集?={?_1,?_2,…,?_? }和参数(?,??????)刻画邻域的样本分布密度。

其中，?表示样本的邻域距离阈值，??????表示对于某一样本?，其?-邻域中样本个数的阈值。下面给出DBSCAN中的几个重要概念。

?-邻域：给定对象?_?，在半径?内的区域称为?_?的?-邻域。在该区域中，?的子样本集：

（1）核心对象（core object）：如果对象?_?∈?，其?-邻域对应的子样本集?_? (?_? )至少包含??????个样本，|?_? (?_? )|≥??????,那么?_?为核心对象。

（2）直接密度可达（directly density-reachable）：对于对象?_?和?_?，如果?_?是一个核心对象，且?_?在?_?的?-邻域内，那么对象?_?是从?_?直接密度可达的。

（3）密度可达（density-reachable）：对于对象?_?和?_?，若存在一个对象链?_1,?_2,…,?_?，使得?_1=?_?,?_?=?_?，并且对于?_?∈?(1≤?≤?), ?_(?+1)从?_?关于(?,??????)直接密度可达，那么?_?是从?_?密度可达的。

（4）密度相连（density-connected）：对于对象?_?和?_?，若存在?_?使得?_?和?_?是从?_?关于(?,??????)密度可达，那么?_?和?_?是密度相连的。

在下图中，若??????=3（某个圈内除了核心对象之外，对象的最大个数），则?、?、?和?、?、?都是核心对象，因为在各自的ε-邻域中，都至少包含3个对象。对象?是从对象?直接密度可达的，对象?是从对象?直接密度可达的，则对象?是从对象?密度可达的。对象?是从对象?密度可达的，对象?是从对象?密度可达的，则对象?和?是密度相连的。

DBSCAN可以用于对任意形状的稠密数据集进行聚类，DBSCAN算法对输入顺序不敏感。DBSCAN能够在聚类的过程中发现数据集中的噪声点，且算法本身对噪声不敏感。当数据集分布为非球型时，使用DBSCAN算法效果较好。

DBSCAN算法要对数据集中的每个对象进行邻域检查，当数据集较大时， 聚类收敛时间长，需要较大的内存支持，I/O 消耗也很大，此时可以采用KD树或球树对算法进行改进，快速搜索最近邻，帮助算法快速收敛。此外，当空间聚类的密度不均匀，聚类间距离相差很大时，聚类的质量较差。

DBSCAN算法的聚类结果受到邻域参数(?, ??????)的影响较大，不同的输入参数对聚类结果有很大的影响，邻域参数也需要人工输入，调参时需要对两个参数联合调参，比较复杂。

# 流程
（1）检测数据库中尚未检查过的对象p，如果p未被处理(归为某个簇或者标记为噪声)，则检查其邻域，
     若包含的对象数不小于minPts，建立新簇C，将其中的所有点加入候选集N。
     
（2）对候选集N 中所有尚未被处理的对象q，检查其邻域，若至少包含minPts个对象，则将这些对象加入N；
	 如果q 未归入任何一个簇，则将q 加入C。
	 
（3）重复步骤2)，继续检查N 中未处理的对象，当前候选集N为空。

（4）重复步骤1)~3)，直到所有对象都归入了某个簇或标记为噪声。
1
2
3
4
5
6
7
8
9
10

DENCLUE算法

DENCLUE算法是一种基于密度的聚类算法，采用了基于网格单元的方法提高聚类性能。算法的核心思想是采用核密度估计来度量数据集中每一个对象对于其他对象的影响。

用一个对享受到所有其他对象影响之和来衡量数据集中每一个对象的核密度估计值。通过影响值的叠加形成空间曲面，曲面的局部极大值成为一个簇的密度吸引点。

DENCLUE算法采用影响函数来对邻域中的样本建模，定义影响函数为：

其中，?(?,?)为样本?,?之间的距离（通常采用欧式距离），?表示该点的数据影响量，?为光滑参数的带宽，反映该点对周围的影响能力。通常，采用的核函数是采用欧式距离的标准高斯函数（正太分布函数）。

给定包含?个样本的数据集?，对于任意样本点的密度函数为：

定义梯度为：

密度吸引点可以通过希尔爬山过程确定，只要核函数在每个数据对象处连续可导，则爬山过程就可以被核函数梯度引导。对象?的密度吸引点计算过程如下：

其中，?是控制算法收敛速度的参数。

为了避免聚类过程收敛于局部最大点，DENCLUE算法引入噪声阈值?，若对象?被局部极大值点?^∗ 吸引，如果? ̂(?^∗ )<?，则?为噪声点，将其排除。

当爬山过程中步骤?满足? ̂(?^(?+1) )<? ̂(?^? )，则爬山过程停止，把对象?分配给密度吸引点?^∗。

DENCLUE算法融合了基于划分的、基于层次的和基于网格的聚类方法，对于含有大量噪声的数据集，也能够得到良好的聚类结果。

由于算法使用了网格单元，且使用基于树的存取结构管理这些网格单元，因此算法的运行速度快。但是DENCLUE算法要求对光滑参数的带宽?和噪声阈值?的选取敏感，参数选择的不同可能会对聚类结果产生较大的影响。

---

基于网格的聚类（STING、CLIQUE ）

基于网格的聚类算法的基本思想是将每个属性的可能性分割成许多相邻的区间（例如将属性的值域离散化处理）。

创建网格单元的集合，将数据空间划分为许多网格单元，然后以网格单元为单位计算每个单元中的对象数目。删除密度小于阈值的单元之后，将邻接的高密度单元组合成簇。

基于网格的聚类与基于密度的聚类算法相比，基于网格的聚类运行速度更快，算法的时间复杂度更低。

---

基于模型的聚类

基于概率模型的聚类

基于概率模型的方法利用属性的概率分布来描述聚类，假定样本集是通过某种统计过程生成的，用样本的最佳拟合统计模型来描述数据。

最典型的例子是高斯混合模型(GMM)，它采用EM算法求解，EM算法是在概率模型中寻找参数的最大似然估计的算法，其中概率模型是依赖于无法观测的隐藏变量。

高斯混合模型处理聚类问题时，以数据遵循若干不同的高斯分布为前提。这一前提的合理性可以由中心极限定理推知，在样本容量很大时，总体参数的抽样分布趋向于高斯分布，高斯混合模型的概率分布模型如下：

其中：

高斯分布的概率密度函数为：

GMM的聚类，和K-means（k均值）聚类有点相似，具体算法流程如下：

1. 随机生成k个高斯分布作为初始的k个类别
2. 对每个样本数据点，计算其在各个高斯分布的概率；
3. 对每个高斯分布，样本数据点得到的不同概率值作为权重，加权计算并更新其均值和方差；
4. 重复以上步骤2和3，直到每一个高斯分布的均值和方差不再发生变化或已满足迭代次数。

基于神经网络模型的聚类

自组织映射网络(Self-organizing Map. SOM)是种竞争式学习网络， 能在学习过程中无监督地进行自组织学习。 SOM 是由芬兰教授Teuvo Kohonen提出的，因此也叫Kohonen 神经网络。

SOM模拟大脑神经系统自组织特征映射的方式，将高维空间中相似的样本点映射到网络输出层中的邻近神经元，这种方法可以将任意维度的输入离散化到一维或二维的空间上。

SOM包含输入层和竞争层（输出层）两个层。输入层对应一个高维的输入向量，有?个样本?_?=(?_1^?,?_2?,…,?_?^? ),输出层由二维网络上的有序节点构成，节点个数为?=?^2,输入节点与输出节点之间通过权向量实行全互连接,输出层各节点之间实行侧抑制连接，构成一个二维平面阵列

SOM中有两种连接权值：（1）节点对外部输入的连接权值。（2）节点之间控制着相互的交互作用大小的连接权值

SOM能将任意维的输入在输出层映射成低维(维成二维)的离散映射，通过对输入模式反复学习，保持其拓扑结构不变，从而反映输入模式的统计特征。

SOM基本的拓扑结构:通过细胞空间位置的不同来表示特征和分配任务，用竞争学习来实现，表示一个特征有多个范畴，如形状，大小，色彩等，组特征用一组细胞来表示，获胜的神经元把周围的神经单元训练成与之相似的，范围大小是由网络设计者决定，随着训练增加，范围逐渐减少。在应用中可增加遗忘机制，权值随时间逐渐变小，从而防止权值无限放大

SOM的基本思想是基于赢者通吃法则(也称为竞争学习)，使获胜神经元对其邻近神经元的影响是由近及远，对附近神经元产生兴奋影响逐渐变为抑制。通过自动寻找样本中的内在规律和本质属性，自组织、自适应地改变网络参数与结构。

Kohonen神经网络步骤如下：
网络初始化。对输入层到输出层所有神经元的连接权值?_??赋予随机的小数作为初始值。

计算连接向量。对网络的输入样本?_?=(?_1^?,?_2?,…,?_?^? )，计算?_?与所有输出神经网络节点连接向量的距离。

定义获胜单元。根据第（2）步距离计算结果，找到与输入向量距离最小的输出节点?^∗，即：

在获胜单元的邻近区域，调整权重使其向输入向量靠拢。调整输出节点?^∗ 连接的权值以及邻域NE(?^∗)内输出节点的连接权值。

其中?是学习因子，随着学习的进行，利用?逐渐减少权值调整的幅度。提供新样本进行训练，收缩邻域半径，减小学习率。重复上述步骤，直到小于阈值，输出聚类结果。