描述聚类算法概述、用例以及优缺点题库
目录（TOC）

简介

• 机器学习
• 聚类分析
• 聚类类型
• 聚类算法
  

1、基于质心的聚类

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

2、基于分布的聚类
  11.GMM
  12.EM
  13.DMM
3、基于密度的聚类
  14.DBSCAN      
  15.ADBSCAN      
  16.DENCLUE      
  17.OPTICS
4、结论




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

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

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

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



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

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

• 硬聚类：聚类不重叠：k​​-means、k-means++。一个数据点只属于一个集群。它要么属于某个集群，要么不属于某个集群。
• 软聚类：聚类可以重叠：Fuzzy c-means、EM。一个数据对象可以以一定的概率或隶属程度存在于多个集群中。
• 此外，聚类算法可以根据它们尝试达到的目的进行分类。因此，存在两种基于此标准的聚类技术：
• Monothetic：集群成员之间存在一些共同属性（例如，25% 的患者因疫苗 A 出现副作用）：数据按单个特征生成的值进行划分。
• Polythetic：集群成员之间存在某种程度的相似性，但没有共同的属性（例如，不相似性度量）：数据根据所有特征生成的值进行划分。
  

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



聚类算法的综合调查

聚类算法

基于质心的聚类
该方法的主要步骤之一是初始化集群的数量 k，这是一个在模型的训练阶段保持不变的超参数。

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



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

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

然而，如果这些假设之一被打破，这并不一定意味着 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 达到最小值。

优势

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

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

缺点

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

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

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

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

目标函数最小化

k-means 的目标函数

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



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



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

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

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