描述聚类算法概述、用例以及优缺点

目录（TOC）
简介

1. 机器学习
2. 聚类分析
3. 聚类类型

聚类算法

1. 基于质心的聚类

• k-means
• k-means++
• k-means|| 
• 模糊 C-means
• k-medoids, PAM
• k-Medians
• k-Modes
• k-prototypes
• CLARA
• CLARANS

1. 基于分布的聚类

• GMM 
• EM
• DMM

1. 基于密度的聚类

• DBSCAN      
• ADBSCAN      
• DENCLUE      
• OPTICS

1. 结论
2. 有用的资源

介绍

数据变得越来越重要，并且可供全球人使用，越来越多的数据科学和机器学习方法已经被设计出来。聚类分析模型看起来可能很简单，但要了解模型怎样处理海量数据。然而，在大量聚类算法之间难以做出合理的选择，并且需要对各种算法有相当多的了解。因此，本文汇总了 17 种聚类算法，以提供有关其中大部分算法的大量知识。

机器学习

机器学习是人工智能的一个子领域，最简单的定义是，机器如何通过发现统计方法来学习数据（例如，从传感器收集的数据、实验……）来做出决策并自行完成任务（自动化数据）驱动模型）。就是这么简单。然而，困难来自狭窄的细节和应用。这一切都是从分析数据并从中学习。此外，机器学习为其核心提供了数据科学的基础。

从历史上看，机器学习起源于人工智能中的连接主义，其中一群人想要复制具有相似特征的人脑机制。此外，它主要受益于融合了心理学和其他领域（例如统计学）的思想。此外，统计学和机器学习是根本不同的领域，前者旨在为人类提供正确的工具来分析和理解数据。后者侧重于自动化人类在分析数据时的干预（AI奇点）。

聚类分析

聚类分析、聚类或数据分割可以定义为一种无监督（未标记数据）机器学习方法，旨在收集数据样本的同时找到范例（例如，许多子组、每个组的大小、共同特征、数据凝聚力……）并使用预定义的距离度量（如欧几里得距离等）将它们分组到相似的记录中。共享相似特征的数据对象或观察被分组到一个集群中，该集群由保存这些数据样本的距离（例如，椭圆的长轴）描述。

聚类分析被图像处理、神经科学、经济学、网络通信、医学、推荐系统、客户细分等各种应用广泛采用。此外，在处理新数据集以提取见解和了解数据分布时，可以将聚类视为初始步骤。聚类分析也可用于执行降维（例如，PCA）。它还可以作为分类、预测和其他数据挖掘应用程序等其他算法的预处理或中间步骤。

聚类类型

有很多方法可以将聚类方法分类。例如，基于重叠区域，存在两种类型的聚类：

硬聚类：聚类不重叠：k​​-means、k-means++。一个数据点只属于一个集群。它要么属于某个集群，要么不属于某个集群。

软聚类：聚类可以重叠：Fuzzy c-means、EM。一个数据对象可以以一定的概率或隶属程度存在于多个集群中。

此外，聚类算法可以根据它们尝试达到的目的进行分类。因此，存在两种基于此标准的聚类技术：

Monothetic：集群成员之间存在一些共同属性（例如，25% 的患者因疫苗 A 出现副作用）：数据按单个特征生成的值进行划分。

Polythetic：集群成员之间存在某种程度的相似性，但没有共同的属性（例如，不相似性度量）：数据根据所有特征生成的值进行划分。

基于所使用的聚类分析技术，每个聚类呈现一个质心、一个代表数据样本中心的单个观测值和一个边界限制。下图代表了一些常见的聚类算法类别。

聚类算法的综合调查

聚类算法

基于质心的聚类
该方法的主要步骤之一是初始化集群的数量 k，这是一个在模型的训练阶段保持不变的超参数。
k-means或Lloyd 算法
最流行的分区算法之一（在谷歌学者上被引用超过一百万）用于对数据进行聚类。使用这种多元硬聚类方法，n 个数据被分成 k 个分区 (k << n)，其中每个分区代表一个簇。每个集群必须至少包含一个数据。此外，每个数据必须只属于一个组。此外，对同一集群的观察应该彼此相似或接近。相反，不同组的对象必须彼此相距甚远或不同。换句话说，k-means 算法的目标是最大化每对集群中心之间的距离，并最小化每个集群内的观测值之间的距离（例如，最小化集群内的平方误差和 SSE）。 .

如果满足以下条件，k-means 聚类效果很好：

1. 每个属性的分布方差是球形的。
2. 组是线性可分的。
3. 聚类具有相似数量的观察值（更接近大小。）。
4. 变量呈现相同的方差。

然而，如果这些假设之一被打破，这并不一定意味着 k-means 将无法对观察结果进行聚类分析，该算法的唯一指标是最小化平方误差之和 (SSE)。这里有一个很好的讨论说明，如果不满足前面的假设之一，k-means 会很好地工作。

为了更好地理解数据（例如，提取信息和查找聚类），经验法则是将数据绘制在二维空间中。例如，要找出 iris 数据集中有多少簇，一个基本的相关矩阵会说明很多问题。

如图所示，该数据集中有三个主要集群。因此，为了进一步的训练数据，k 应该等于 3。然而，这并不是选择 k 值的最佳方法。
在建模中，标准化是从目标函数开始，其中函数针对不同的 k 值运行（例如，k= 1、2、3、4……），并使用称为 WCSS（组内平方和）的稳健方法) 计算每个集群成员与其质心之间的距离总和，使组内平方和最小化以达到 k 的最佳值。

k 的最佳值为 3

还有另一种方法可以通过计算每个组的轮廓系数来选择正确的 k 值：同一簇的点之间的平均距离。它提供了一个指标，表明数据对象根据它们的集群有多相似。为了说明这一点，我们在 iris 数据集上绘制了一个轮廓图，其中每个集群都有一个轮廓系数。

k = [2, 3, ..., 7] 的轮廓系数得分

使用这种方法，系数越接近 1，k 值越适合模型。因此，k 的最佳值是 2 和 3，因为它们为每个集群画出比其他的轮廓系数更高。

K 值也可以使用方差进行初始化，该方法表示平方和百分比 (BSS/TSS) 与组数的关系图。

k 的最佳值为 3

如图所示，最佳集群数量是拐点形成的位置。因此，k 等于 3。

此外，还有许多其他方法可用于估计 k 的最佳值，例如R 平方度量。然而，轮廓系数得分已被证明是找到 k 的最佳方法。

解释

这一切都始于在特征样本中随机放 k 值，其中每个点代表一个集群的质心。使用某种差异性度量迭代计算数据集的每个样本值到每个聚类中心之间的距离。此外，将每个样本值分给距离最近质心的集群。之后，对于每个集群，计算每个集群点的平均值（数字属性）并将质心重新分给结果平均值。这个过程将不断循环，直到满足预定义的收敛条件（例如，达到最大迭代次数，误差不变，BSS 低于给定最小，SSE 最小，最小化目标函数，失真......）

k-means 的目标函数

算法

1、从数据集中挑选 k 个随机质心

2、使用适当的相异性度量（例如，欧几里得距离）计算每个样本点与簇的质心之间的距离。

3、根据计算出的距离将每个样本点分给最近的集群。

4、通过计算样本点的平均值来重新定位质心。因此 k-means 仅适用于数值数据！

5、重复 2 直到集群稳定或目标函数 J 达到最小值。

优势

1. 学习曲线比较陡峭
2. 由多种包广泛实现（ R 中的Stats包，python 中的 scikit-learn ......）
3. 快速收敛小数据集
4. 易于实施

20 次迭代对 iris 数据集进行聚类

缺点

1. 大型数据集的计算成本很高（k 变大）
2. 有时，很难为组数（k）选择一个初始值
3. 不保证收敛到全局最小值。它对质心的初始化很敏感。不同的设置可能会导致不同的结果
4. 对异常值有很强的敏感性
5. 仅适用于数值数据
6. 无法为一组具有非凸形状的点提供良好的聚类分析

k-means 无法分离月形样本点

但是，使用拐点初始化组数，使用k-means++克服参数初始化的敏感性，使用遗传算法等技术寻找全局最优解，可以解决一些缺点

应用场景

k-means 聚类被各种现实世界的业务所采用，例如搜索引擎（例如，文档聚类、聚类相似文章）、客户细分、垃圾邮件/火腿检测系统、学术表现、故障诊断系统、无线通信等等

目标函数最小化

k-means 的目标函数

为了找到 k 个集群的最优解，目标函数J wrt μ的导数必须等于 0

对于每个集群 J，前面的等式将导致：

每个簇质心与欧几里得距离的梯度

每次迭代后，每个集群的质心都会更新为集群内所有样本点的经验平均值。

请注意，最小化每个集群内的欧几里得距离的问题称为Weber 问题。而且，从几何上讲，均值并不是最优解。因此需要复杂的几何中心，如中值、中点，以最小化欧几里得距离。

k-means++

k-means++ 背后的想法是它试图分散中心，同时在每次迭代中分配一个新中心。因此，该算法首先从数据集中随机（均匀）选择一个初始中心，这意味着所有点都有相同的被选中概率。然后计算从每个样本点到先前选择的中心的距离平方。之后，它通过简单地将距离除以总距离来计算每个数据点的概率。此外，将新的质心分配给具有最高概率或最大距离的点。换句话说，数据成为新集群中心的可能性与距离的平方成正比。

k_means++ 采样 k 个质心

一旦分配了中心，k-means 算法将和这些集群的中心一起运行，并且它会更快地收敛，因为中心已经被仔细选择并且彼此远离

k_means 在采样质心上。~ 12 次迭代

算法

初始化步骤

以统一的方式独立地对每个质心进行采样，概率与每个样本点到每个质心的距离平方成正比。

聚类步骤

一旦 k 个质心被均匀采样，K-means 算法将使用这些质心运行

优势

1. 与 K-means 的优点相同
2. 在更少的迭代次数内收敛速度比 K-means 快

缺点

1. 与 K-means 相同的缺点
2. 初始化步骤（为 K 选择初始值）可以被认为是 kmeans++ 的主要缺点之一，就像其他风格的 K-means 算法一样。然而，它比单独运行 K-means 更有可能收敛和更快。此外，该算法仍然对可以使用LOF、RANSAC和其他方法解决的异常值敏感

K-means||，可扩展的 K- means ++

K-means 并行是一种勉强满意的算法，它在每次迭代后不太频繁地更新样本的分布。它在 k-means 算法中引入了一个过采样因子（L ~ k 阶，例如 k、k/2、...）。使用该因素，它将使算法在更大的数据集上收敛得更快。

算法

初始化步骤

k-均值|| 初始化步骤

1. 初始化过采样因子 L 的值
2. 对于一定次数的迭代（0 ≤ nb_iter ≤ k），随机均匀地采样 L 个质心，概率与每个数据点到每个质心的距离平方成正比（比 kmeans++ 算法中的概率大 L 倍）

nb_iter = 0 ---》 k 均值聚类

nb_iter = k，L = 1 ---》 k-means++ 聚类

聚类步骤

一旦 k 个质心被均匀采样，K-means 算法将使用这些质心运行

k_means 在 4 次迭代中收敛

优势

1. 适用于大型数据集。运行时〜日志（k）
2. 比 kmeans++ 快，因为它每次迭代对 L 个质心进行采样

缺点

1. 它可能导致基于 L 的值的过采样或欠采样

过采样（L = 20）~ 13 次迭代，使用 k-means

使用 k-means 进行欠采样 (L = 0) ~ 14 次迭代

模糊 C 均值：FCM

FCM算法

模糊一词用于强调这样一个事实，即允许在一个或多个集群中存在样本点的地方形成各种阴影的集群（例如，不相交的、非不相交的……）。例如，橙色是红色和黄色的混合颜色，这意味着它在某种程度上属于每个颜色组。

隶属度函数用于衡量一个数据点对每个聚类的归属程度。它描述了一个样本点属于某个集群的概率

该算法旨在最小化以下成本函数：

FCM的目标函数

算法

1、根据预定义的权重 aij^p 和 p 的初始值选择 k 个初始模糊伪质心

2、使用模糊分区更新聚类中心

3、使用以下公式更新权重

4、计算目标函数 J

5、重复2直到稳定质心或满足以下标准：新计算的目标函数与旧的目标函数之间的差异小于某个值

FCM 的收敛条件

Fuzzy k-means 展示了大型现实世界用例，例如图像分割、异常检测。与边缘和对象检测等其他图像处理技术相比，它的计算量较小

优势

1. 与 k-means 相比，重叠数据的结果更好
2. 时间复杂度低
3. 保证收敛

缺点

1. 对 k 和 p 的初始值敏感
2. 对异常值敏感

目标函数最小化

FCM 的目标函数

为了找到 k 个集群的最优解，成本函数J wrt μ的导数必须等于 0 

对于每个集群 J，前面的等式将导致：

成本函数 wrt 质心 j 的梯度

知道对于数据集中的每个观察，所有集群的成员之和等于 1；因此，每个集群的质心在每次迭代后都会更新为其经验平均值。

每次迭代后，每个簇的质心更新为簇内所有数据点的平均值

k-medoids，PAM（围绕 Medoids 分区）

k-means 算法的修改版本，其中中心点表示在集群内的所有点中具有最低平均相异性的数据点。目的是最小化每个集群的总成本。与 k-means 不同，它使用medoid作为度量来重新分配每个集群的质心。Medoids 对异常值不太敏感。这些中心点是来自数据集的实际观察结果，而不是像 k-means 那样的计算点（平均值）。最好使用曼哈顿距离作为度量，因为它对异常值不太敏感。

算法

1. 随机选择 k 个观测值作为初始中心点。
2. 计算观测值和中心点之间的距离。
3. 将每个点分配给最近的中心点。
4. 在每个集群中选择一个新的观察（非中心点）并将其与对应的中心点交换。
5. 计算每个中心点的交换成本和每个集群内的新数据点。
6. 选择成本最低的观测值（例如，最小相异之和）作为新的中心点。
7. 重复步骤2，直到满足收敛条件（例如，最小化成本函数，误差平方和（PAM 中的 SSE））。

k-medoids 成本函数

优势

1. 在存在异常值的情况下比 k-means 更稳健（受异常值影响较小。）
2. 易于实施。
3. 它在固定次数的迭代中收敛。
4. 它适用于小型数据集。

缺点

1. 它不适用于大型数据集。
2. 计算复杂度相当昂贵。
3. 参数k需要初始化为某个值。
4. 不保证收敛到全局最小值。它对质心的初始化很敏感。不同的设置会导致不同的结果。
5. 仅适用于数值数据。

为了提高 PAM 的效率，使用了 CLARA 算法。