ModelCube（modelcube.cn）是博雅数智自主研发的一站式人工智能科研平台。为全国高校和科研机构的大数据和人工智能科研团队提供一站式科研服务。基于MLOps的实践和企业核心技术，实现了科研场景中全类型数据管理与标注，实验环境快速获取与灵活定制，模型的全生命周期管理，科研成果的管理与发布，以及 AI驱动的论文检索和学习等功能。
1 聚类的定义
聚类（Clustering）是指将物理或抽象对象的集合分组为由类似的对象组成的多个类的分析过程。聚类是搜索簇的无监督学习的过程，对于所要求划分的类是未知的，不必事先给出分类标准，而是可以从样本数据出发自动进行分类。
聚类的实现过程是按照某个特定标准(如距离)把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大，也即聚类后同一类的数据尽可能聚集到一起，不同类数据尽量分离。
1.1 数据对象之间相似度度量
1.2 类别之间相似度度量
单连接（Single-link）: 定义两个类之间距离为两个类之间距离最近的两个点之间的距离，这种方法会在聚类的过程中产生链式效应，即有可能会出现非常大的类。
全连接（Complete-link）：定义两个类之间的距离为两个类之间距离最远的两个点之间的距离，这种方法可以避免链式效应，但对异常样本点（不符合数据集的整体分布的噪声点）却非常敏感，容易产生不合理的聚类。
UPGMA：Single-link和Complete-link的折中，定义两个类之间的距离为两个类之间所有点距离的平均值。 WPGMA：计算两个类之间两个对象之间的距离的加权平均值，加权的目的是为了使两个类对距离的计算的影响在同一层次上，而不受类大小的影响，具体公式和采用的权重方案有关。
2 聚类方法总结
2.1 K均值（K-Means）
2.1.1 模型概述
K-Means 聚类是一种常见的无监督学习算法，是一种自上而下的聚类方法，需要预先确定样本中的聚类数目。K-Means 聚类的目标是将数据点分成K个簇，每个簇内的数据点彼此相似，而不同簇之间的数据点相似度较低。其核心思想是通过最小化每个数据点与其所属簇中心点之间的距离来划分数据。
聚类K的均值或者中心位置定义为：
其中， 是簇 的中心位置， 是簇 的数据点数量， 是簇 中的第 个数据点.
K-Means 的目标是最小化平方误差函数（SSE，Sum of Squared Errors），调整簇的分配和中心点位置，以最小化所有数据点到其所属簇中心的距离之和的平方。SSE公式如下：
K-means通过迭代算法近似求解，包括分配和更新两个过程，将两个过程重复迭代，即可找到最优化问题的局部最小解。
分配过程：如果知道聚类中心位置 ，可计算聚类的分布，即每个观测值归入最近的类别。 更新过程：一旦知道聚类的分布，则可以更新聚类的中心位置 。
K-Means聚类的关键问题是如何选择聚类数目K，有如下几种常用方法：
肘部法则（Elbow Method）：计算不同K值下各类的离差平方和，随着K值增加，类中的点会变少，离差平方和会逐渐变小。当K值达到一定点后，SSE的下降幅度急剧减小，形成一个肘部形状的曲线。肘部所对应的K值通常被选择为最佳的K值，因为它表示了一个自然的聚类分割点。
轮廓分析（Silhouette Analysis）：考虑了数据点的分配到簇的均匀性和分离度。对于每个K值，轮廓系数可以用来衡量簇内数据点的相似度和簇间数据点的不相似度。较高的轮廓系数表示更好的聚类质量，所以选择具有最高轮廓系数的K值。
2.1.2 加速精确的K-Means（Accelerating exact K-Means）
在1999年的论文《Accelerating exact k-means algorithms with geometric reasoning》中，利用数据点之间的几何信息，考虑数据点的空间分布，找到一些可加速的划分策略。该方法将数据用“KD树”这种结构存储，利用树的性质，一般能比传统的K-Means更快找到每个点最近的聚类中心。同时，提出了剪枝策略，帮助确定哪些数据点不需要参与更新簇中心的计算，可以减少迭代的次数，从而提高效率。
KD树每个节点代表一个矩形，存储着这个矩形中数据点的信息： 和 ，这两个向量用于描述这个矩形的边界和矩形中数据点的数量。 树的叶子节点存储矩形中每个数据点的值。树的每个非叶子节点还额外存储关于分裂成子树的信息：划分子树的值和此数值所在的维度。 树的深度是提前设定好的，并不一定要分裂到不可再分。
2.1.3 优点
K-Means 算法是一种简单而高效的聚类算法，易于实现和理解，适用于大型数据集和高维数据； 聚类结果相对容易解释，因为每个数据点被分配到最接近的簇中，簇的中心点代表了该簇的特征； 通用性强，可以应用于多种领域，包括数据挖掘、图像处理、文本分析等。
2.1.4 缺点
对初始中心点的选择非常敏感，不同的初始中心点可能导致不同的聚类结果； 确定K值通常需要使用不同的方法，选择不合适的K值可能会导致不良的聚类结果； 对噪声和异常值敏感； K-Means 假定簇是凸形的，因此不适用于发现不规则形状的簇。
Accelerating exact k-means Algorithms with Geometric Reasoning[1]. Dan Pelleg, Andrew Moore. KDD 1999.
2.2 分层聚类（Hierarchical clustering）
2.2.1 模型概述
分层聚类方法最早在《Hierarchical clustering schemes》一文中被提出，是一种逐次聚类方法。其无须预先设定聚类数目，通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树，最后可在任意层次横切一刀选择聚类数目。层次聚类是一种贪心算法，因为其每次合并或者划分都是基于某种局部最优的选择。
按照层次分解是自下而上，还是自顶向下，层次的聚类方法可以进一步分为凝聚方法和分裂方法。
自下而上的凝聚方法（agglomerative）：先将所有样本的每个点都看成一个簇，然后找出距离最小的两个簇进行合并，不断重复到预期簇或者其他终止条件。代表算法为Agglomerative Nesting（AGNES）。 自顶向下的分裂方法（divisive）：先将所有样本当作一整个簇，然后找出簇中距离最远的两个簇进行分裂，不断重复到预期簇或者其他终止条件。代表算法为Divisive Analysis（DIANA）。
2.2.2 优点
层次结构提供了对数据更细致和全面的理解，允许用户根据需要选择合适的聚类层次； 不需要预先设定聚类数，可解释性好； 不受初始点的选择影响，逐渐构建聚类层次，而不需要初始簇的估计。
2.2.3 缺点
计算复杂度高，效率低； 分层聚类需要选择合适的距离度量和聚类算法； 异常值会产生很大影响； 聚类终止条件具有不精确性，算法可能聚类成链状。
Hierarchical Clustering Schemes*[2]. Stephen C. Johnson. PSYCHOMETRIK 1967.
2.3 谱聚类（Spectral clustering）
2.3.1 模型概述
谱聚类（spectral clustering）是从图论中演化出来的算法，将无向权重图划分为两个或两个以上的最优子图(sub-graph)，使子图内部尽量相似，而子图间距离尽量距离较远，以达到常见的聚类的目的。算法将聚类问题转化成图的划分问题，最优划分原则是切图后不同的子图间边权重和最小，而子图内的边权重和最大，常见的划分准则有最小割集准则 (Minimum cut，Mcut)、比例割集准则 (Ratio cut，Rcut)、规范割集准则 (Normalized cut，Ncut) 等。
其能够在高维数据空间中发现低维结构，并在处理非凸形状的数据聚类问题中表现出色。对数据分布的适应性更强，聚类效果很优秀，同时聚类的计算量也小很多，实现起来不复杂。
2.3.2 模型实现
首先，构建相似度矩阵（W）和度矩阵（D），通常采用K-近邻（KNN）、-近邻法或者全连接策略从而获得样本之间的相似度或距离信息，并根据相似度或距离信息构建系数矩阵。
相似度矩阵计算
K-近邻法
ϵ-近邻法
全连接
度矩阵计算：
其次，计算拉普拉斯矩阵（L），并得到标准化后的拉普拉斯矩阵。它包含了样本之间的相似度或距离信息，并且对于每个节点有一个额外的自环权重。通过计算增广拉普拉斯矩阵的特征向量和特征值，可以将样本映射到低维嵌入空间中。
最后，将特征向量嵌入聚类，通常选择前 k 个特征向量，并将它们视为聚类时使用的新特征。用这些特征作为坐标轴可以得到新的低维表示。然后使用 K-Means 或模糊聚类等传统的聚类算法来将数据分成 k 个类别。
2.3.3 优点
不受簇的几何形状的限制，可以有效地处理不同形状和大小的簇； 由于使用了降维，因此在处理高维数据聚类时的复杂度比传统聚类算法好； 依赖于数据点之间的相似度矩阵，这允许它捕捉数据的光滑性和连通性，特别适用于图像分割等应用； 谱聚类产生一个谱嵌入（spectral embedding），这是一种将数据映射到一个低维空间中的表示，可以在可视化和降维方面非常有用。
2.3.4 缺点
需要用户指定一些参数，如簇的数量或相似度阈值，选择适当的参数值可能具有挑战性； 谱聚类的计算复杂度较高，特别是在数据集非常大时，需要进行特征值分解和矩阵操作，这可能使它不适合处理大规模数据集； 谱聚类通常难以提供可解释性的结果，因为它产生的簇是在低维嵌入空间中定义的，不容易直观理解。
Lower Bounds for the Partitioning of Graphs[3]. W. E. Donath, A. J. Hoffman. IBM Journal of Research and Development 1973.
2.4 基于密度的噪声应用空间聚类（DBSCAN）
2.4.1 模型概述
基于密度的噪声应用空间聚类（DBSCAN）适用于处理包含噪声和非凸形状簇的数据，主要思想是通过找到核心点和它们的连接性来形成聚类簇，同时识别噪声点。
其创新性表现在如下几点：
引入了密度的概念，以区分核心点、边界点和噪声点。核心点是指在给定半径 （领域半径）内至少有 （最小邻域点数）个邻居点的点，对应图中红色点；边界点是半径 内少于 个邻居点的点，对应图中黄色点；噪声点是既不是核心点也不是边界点的点，没有足够的密度来被归为某个簇，对应图中蓝色点。
用一种特殊的邻域查询技术，即通过半径 内的邻域来判断点的密度，而不是事先指定簇的数量，这使得它能够自动发现不同形状和大小的簇。 DBSCAN 具有高效的性能，通过核心点和它们相邻点的连接避免对数据集中的所有点进行显式比较。其中点的关系分为四种：
密度直达：如果 为核心点， 在 的 邻域内，那么称 到 密度直达。密度直达不具有对称性。 密度可达：如果存在核心点 ，且 到 密度直达， 到 密度直达，…， 到 密度直达， 到 密度直达，则 到 密度可达。密度可达也不具有对称性。 密度相连：如果存在核心点 ，使得 到 和 都密度可达，则 和 密度相连。密度相连的两个点属于同一个聚类簇。 非密度相连：如果两个点不属于密度相连关系，则两个点非密度相连。非密度相连的两个点属于不同的聚类簇，或者其中存在噪声点。
2.4.2 优点
不需要事先指定要寻找的簇的数量； 能够有效地发现具有不同形状和密度的簇，因为它基于点之间的密度来定义簇，而不依赖于簇的几何形状； DBSCAN对噪声点具有鲁棒性，因为它将噪声点视为孤立的点，而不将它们与簇相关联； 使用邻域查询技术，避免了对整个数据集进行显式比较，因此通常在处理大型数据集时非常高效。
2.4.3 缺点
需要用户指定两个参数： 和 。选择适当的参数值可能有些挑战，尤其是当数据的密度分布不均匀时； 在高维空间中，密度估计和距离度量变得更为复杂，可能需要调整参数以适应高维数据； 非凸簇时可能遇到困难，因为非凸簇内的点密度分布可能不均匀； 对初始点的选择敏感，可能会导致不同初始点产生不同的聚类结果。
A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[4]. Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu. KDD 1996.
2.5 均值漂移（Mean Shift）
2.5.1 模型概述
均值漂移（Mean Shift）是一种密度估计方法，通过在特征空间中对数据点进行迭代移动，以找到数据点的局部密度最大值。这是一种非参数化方法，无需预先指定簇的数量。其具体实现过程如下：
初始化：选择一个或多个数据点作为初始种子点。
计算均值漂移向量： 对于每个种子点，计算均值漂移向量。均值漂移向量是一个指向数据点密度梯度的向量，它用于引导数据点向局部密度最大值漂移。
其中， 是数据点之间的距离； 是核函数的带宽参数，控制核函数的宽度，影响漂移的速度； 是核函数，用于衡量数据点之间的相似性； 是要计算漂移的数据点； 表示数据集中的其他数据点； 为均值漂移向量。
移动数据点：根据均值漂移向量，移动数据点。通常数据点在特征空间中按照均值漂移向量的方向进行移动，并且移动的距离取决于数据点与局部密度的关系。移动的距离通常是自适应的，可以根据数据点与局部密度的距离来调整。
迭代： 重复上述步骤直到数据点不再移动或达到收敛条件。收敛条件可以是移动距离小于某个阈值或达到最大迭代次数。
形成聚类： 最终数据点会根据它们的漂移轨迹形成聚类。漂移轨迹表示数据点是如何从初始位置移动到局部密度最大值的路径。数据点将被分配到最接近的局部密度最大值处形成的聚类中。
2.5.2 优点
不需要事先指定簇的数量，能够自动识别数据中的聚类结构； 均值漂移对于噪声和异常值具有较强的鲁棒性，因其根据数据点密度进行漂移，而不受孤立的离群点的干扰； 对于不规则形状和尺度变化的聚类具有良好的适应性，因为它基于局部密度最大值进行漂移； 在计算机视觉、图像处理、目标跟踪、特征空间分析等领域有广泛的应用。
2.5.3 缺点
计算复杂度较高，特别是在处理大规模数据集时，需要进行大量的距离计算；
均值漂移的性能受到带宽参数的影响，带宽参数的选择需要谨慎；
均值漂移算法的收敛速度可能相对较慢，特别是对于大规模数据集，需要进行多次迭代。
Mean shift: a robust approach toward feature space analysis[5]. D. Comaniciu, P. Meer. TPAMI 2002.
2.6 近邻传播聚类（Affinity Propagation）
2.6.1 模型概述
AP聚类提出于2007年的论文《Clustering by Passing Messages Between Data Points》，将数据点之间的相似性度量作为消息传递的基础，不需要预先指定聚类的数量，自动确定聚类的数量和簇的中心点。AP算法中使用的相似性度量，通常是数据点之间的距离度量，例如欧氏距离或相关性度量。
AP算法的核心是数据点之间通过消息传递来通信：每个数据点根据接收到的消息，向其他数据点发送两种消息：责任消息和可用性消息。
责任消息（Responsibility）表示一个数据点希望成为另一个数据点的聚类中心，用 表示。 可用性消息（Availability）表示一个数据点愿意选择另一个数据点作为其聚类中心， 表示。
在消息传递过程中，每个数据点的相似性度量将会与"preference" 参数相加，会影响数据点选择自己作为聚类中心的倾向程度，较高的"preference" 值将增加数据点选择自己作为聚类中心的概率，而较低的"preference" 值将减少这一概率。
根据接收到的消息来更新其责任和可用性值，反映了数据点对其它数据点的倾向性和可用性。根据更新后的消息，每个数据点决定是否成为聚类中心。聚类形成后，每个数据点被分配到最接近的聚类中心。然后通过迭代消息传递、消息更新和聚类形成来逐渐收敛。
2.6.2 优点
不需要事先指定簇的数量，能够自动确定聚类中心的数量； 对于噪声和异常值具有一定的鲁棒性，因为它利用数据点之间的相似性来确定聚类中心，而不容易受到离群值的干扰； 不受初始中心点的选择影响，因为每个数据点都会自动选择自己作为聚类中心或选择其他数据点作为中心； 在处理不规则形状的聚类时表现出色，因为不依赖于簇的形状或尺寸。
2.6.3 缺点
计算复杂度较高，特别是在处理大规模数据集时，需要进行大量的距离计算； 如果选择的相似性度量不当或设置了较高的"preference" 值，AP 可能会生成过多的簇； 参数"preference" 的选择对聚类结果有较大影响； 对于大规模数据集，AP 可能需要较多的内存来存储相似性矩阵。
Clustering by Passing Messages Between Data Points[6]. Brendan J. Frey. Science 2007.
Accelerating exact k-means Algorithms with Geometric Reasoning: http://modelcube.cn/paper/detail/22
[2]Hierarchical Clustering Schemes*: http://modelcube.cn/paper/detail/25
[3]Lower Bounds for the Partitioning of Graphs: https://ieeexplore.ieee.org/document/5391366
[4]A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise: http://modelcube.cn/paper/detail/2416949
[5]Mean shift: a robust approach toward feature space analysis: https://ieeexplore.ieee.org/document/1000236
[6]Clustering by Passing Messages Between Data Points: http://modelcube.cn/paper/detail/24
阅读原文，了解更多信息：ModelCube一站式人工智能科研平台
http://modelcube.cn/paper/reading-list-detail/39
