蔟类问题与之前我们学过的回归和分类问题不同，起点是对数据内在秩序的理解与发现，而不是所谓的预测。因此，我们不再依赖先验标签，而是试图在数据空间中寻找自然的规律和结构来对数据进行划分。
首先是理解。蔟类分析会通过数据的特征来寻找数据点之间的相似性和差异性，然后再用这些相似性和差异性来划分数据。然而，蔟的边界并不总是清晰绝对的，同一份数据可以被划分成不同的蔟，这取决于我们选择的特征和算法。因此，蔟类分析更像是一种探索性的工具，而不是一个确定性的模型。
蔟的种类
首先我们要知道什么是蔟。蔟（Cluster）是指在数据空间中具有相似特征的数据点的集合。也就是数据团。
而之所以来探讨蔟的种类，是因为不同的蔟类型适用于不同的数据结构和分析目的。常见的蔟类型包括
完全分离蔟
Well-Separated Clusters 就像是海洋上分布着的几座孤岛。你可以很容易的发现他们之间能够很明显的分割开来。因此，这种定义的蔟在几何上最为直观，看起来就像是：
1 |
|
而判断一个点是否属于某座岛的方法也很直观。如果岛上的任意一个点，到岛上其他所有点的距离，都严格小于它到其他岛上任意一个点的距离，那么这个点就属于这座岛。这意味着，这种蔟的定义依赖一种全局性的亲密关系，蔟与蔟之间必须有明显的真空地带将它们隔开。
中心蔟
Center-Based Clusters 不再要求点与点之间彼此亲密，反而我们要求每个点与一个特定的中心点亲密。每一个蔟就像是一个拥有市中心的城市，判断一个人属于哪个城市，直接看它与哪个城市的市中心更近就行了。这样的蔟定义更为宽松，因为它允许蔟之间有重叠区域，甚至是完全重叠的蔟。
这个中心，在数学上通常表现为 质心（Centroid），质心是蔟内所有点的均值坐标；或者是 Medoid：卒中最具代表性的实际数据点。因此中心粗将复杂的群体归属问题简化成了点到中心的距离比较。
但是它的思路也导致了一些问题，例如它假设蔟一定是围绕一个中心点均匀辐射的。因此，如果数据的分布是非球形的，或者蔟之间存在复杂的边界，那么中心蔟可能无法准确地捕捉到数据的结构。
我们之前在第一节课有聊到过K-means。如果你还记得，那么K-means就是一个典型的中心蔟算法。
连续型蔟
连续型蔟 (Contiguity-Based Clusters)引入了所谓“连通性”的思想，比较接近我们日常生活中每个人的社交网络的形成。它认为一个蔟是由一系列相互连接的数据点组成的，如果你认识A，并且A又认识下一个人B，那么你和B就属于同一个蔟。换句话说：一个点只要与蔟内的至少一个点的距离足够近，那么它就能够被吸纳进来。
由于传递性一传十，十传百，它天然具备捕捉非凸形状能力：例如想象一个U形的蔟，中心蔟可能会把它分成两个部分，但连续型蔟可以把它当成一个整体来处理。但是正因为它依赖局部以来传递，它也非常容易被噪声点搭桥，导致两个本应分开的蔟被错误的连在一起。
密度型蔟
密度型蔟 Density-Based Clusters 这个类型的蔟在几何上也非常直观：算法会将人群密度高的地方划分为一个蔟，而将人群密度低的地方划分为另一个蔟。就像是演唱会现场，舞台前面人群密集的地方就是一个蔟，而周围稀疏的地方则是另一个蔟。
因此，这种算法不仅允许蔟呈现出复杂的几何形态，而且抗噪声能力也是非常的强，因为它会将那些孤立的点视为噪声，而不是错误地将它们划分到某个蔟中去。
目标函数与蔟
但由于现实世界的数据充满噪声，同时由于各种因素，我们很难找到一个完美的蔟划分。因此，与其说是依靠肉眼来观察点之间的关系来划分蔟，我们不如可以设定一个 目标函数 (Objective Function)来量化任何一种划分方案的好坏。
算法的任务，就是遍历或搜索所有可能的划分方式，找到能让这个目标函数达到最大值或最小值的哪一种组合。但是你想象一下，如果要枚举所有将 $n$ 个数据点划分为 $k$ 个蔟的可能性，那么它的计算复杂度一定是爆炸级别的，甚至数据NP Hard。因此在实际应用中，我们通常不会进行全局穷举，而是依赖优化算法寻找局部或全部最优解。
这里衍生出来两个重要的分支：Partitional Algorithms 划分式聚类 和 Hierarchical Algorithms 层次化聚类。
Partitional 通常致力于优化一个全局目标，来试图让整个数据集上找到整体误差最小的划分，而 Hierarchical 则往往只关注每一步合并或分裂时的局部目标，贪心地追求当前最优，且一旦做出决策，就不再回头。
（实际上还有一种更高级的视角，叫做 Parameterized Models。它不直接优化一个目标函数，而是假设我们的数据是由几个潜在的统计分布混合采样生成的。这样一来，聚类的过程就像FFT一样，试图反向推断出这些潜在分布的参数。不过在这里我们不会深入。）
那么，我们在这里具体如何使用目标函数来帮助我们划分蔟呢？我们如何指定一个数学标准来判断一个聚类结果是好是坏？
假如说我们要将全班同学分到几个学习小组中，我们的目标可能是让每个小组内的同学成绩尽可能相似，同时又要让不同小组之间的成绩差异尽可能大，这样才能够最大程度地促进小组内的合作和小组间的竞争。如果翻译成数学，那么就是：最小化每个小组内成员的成绩方差。这个就是所谓的一个目标函数。
找到目标函数之后，算法就会去寻找一种分组方案，让这个函数的值达到最优，最小或者最大。
K-Means
那么K-means根据上面的信息，你觉得它属于什么类型的分蔟算法呢？
K-means使用了中心蔟的定义是不假，并且它是一个典型的Partitional Algorithm。这意味着它会将数据集一次性切分成若干个互不重叠的子集，并且强制规定每个数据点必须且只能归属于一个蔟。为了让这种划分具备可操作性，K-means为每一个蔟定义了一个中心点，并通过迭代的方式来优化这个中心点的位置。
假如说我们想使用K-means算法来讲 $n$ 个数据点划分成 $k$ 个蔟，流程如下：
- 在图中随机选择 $k$ 个数据点作为初始的中心点
- 遍历每个数据点，找到与他距离最近的中心点，并将这个数据点划分到这个中心点所在的蔟中去
- 根据蔟内所有数据点的位置，计算出所有点距离中心的距离，并将这些距离平方后求和，得到这个蔟的SSE。随后我们根据SSE的值来调整中心点的位置。
- 重复步骤2和3，直到中心点的位置不再发生变化，或者达到预设的迭代次数为止。
K-means到最后必然会发生收敛，因为我们每一次迭代都在试图降低SSE，而SSE的值是有下界的（至少是0），因此它不可能无限制地下降下去，最终必然会在某个点上停下来。
K-means简单的流程看起来非常直观，但它也存在一些明显的缺点。最主要的缺点是，由于我们往往无法预知数据中真实的蔟中心在哪里，因此我们那 $k$ 个中心点的位置只能随机选取。因此每次运行算法，种子导致这些中心点落点位置不同，导致不同种子最终生长出来的蔟形态也会千差万别。
就比如上面这个图，在同样的数据集上，我们仅仅是因为初始中心落点不同，最终演变出了完全不同的蔟划分结果。在次优划分中，你看见本应独立存在的两个蔟被划分在一起，同时一个大蔟被划分成了两个小蔟。由于K-means本质上是一种贪心算法，它只盯着眼前的局部SSE下降，所以一旦初始点落在了糟糕的位置，算法就会划入一个局部最优陷阱，并且永远无法靠自身的迭代机制跳脱出来。
所以，如何选定合理的初始点，是决定K-means最后分类结果好坏的关键因素之一。
初始点优化
为了克服K-means对初始点敏感的问题，我们也有相应的对策。
最朴素的方法是 Multiple Runs，我们使用不同的随机种子重复运行算法多次，最终挑选出全局SSE最小的那次结果。这种算法本质上还是一种暴力枚举，如果你试的多了，确实能够显著提升结果的稳定性和质量，但是它的计算成本也会成倍增加。如果数据规模足够庞大，使用这个策略很明显是不现实的。
Select more than k initial centroids
讲义上写的是 "Select more than k initial centroids and then select among these initial centroids"，与其说我们盲目随机挑选k个点，不如说我们先随机撒下一张大网，然后刻意挑选那些彼此距离最远的点。
具体流程大概是:
从数据集中随机抽取远大于 $k$ 个数据点作为初始中心点的候选集合。一般是 $2k$ 或者 $3k$ 个。
在这些候选点中随机选定第一个初始中心点
遍历剩余的候选点，计算每一个后选定到这个“已选中心点”的最短距离，然后挑选出那个与已选中心点距离最远的点作为下一个初始中心点。
重复步骤3，直到选定了 $k$ 个初始中心点为止。
这样我们通过强制最大化初始中心之间的空间间隔，从根本上杜绝了多个中心扎堆挤进同一个蔟的情况。
Sample / Hierarchical Clustering
但是我们可以使用一个策略，课件上写的是 "Sample and use Hierarchical Clustering to determine initial centroids"。
既然说Hierarchical Clustering虽然对初始化不敏感，且能够自动发现数据骨架，但是它的复杂度是 $O(n^3)$，还是不适合直接在全量数据上使用。
在这里我们遵循这样的步骤：
在全量数据中进行随机抽样，提取出一个规模相当可控的子集，比如说原数据的10%或者20%。
在自己上运行 Agglomerative Hierarchical Clustering 来对这个子集进行聚类分析，得到一个层次化的聚类树（Dendrogram）。
直接在树状图的合适高度进行切割，切出 $k$ 个蔟。
找到这 $k$ 哥样本蔟的中心点，并将它们作为初始中心点来喂给 K-means。
但实际上我们刚才对于Hierarchical Clustering只讲了一句，你看到这里应该不会很明白具体来说，Agglomerative Hierarchical Clustering 是如何工作的。简单来说，Agglomerative Hierarchical Clustering 是一种自底向上的聚类方法。它的基本思想是：首先将每个数据点看作一个独立的蔟，然后逐步合并最相似的蔟，直到所有数据点都被合并成一个单一的蔟为止。
至于为什么要在合适的树高度切割来得到 $k$ 个蔟，是因为在层次化的聚类树中，在每一个树节点，由于节点都是依靠关系系来合并的，因此这个树节点下方的内容能够保证在某种程度上是相似的。我们只需要找到一个合适的树高度来切割，就能够得到 $k$ 个相对合理的蔟。
更多有关Hierarchical Clustering的内容，会在一会进行深入讲解。在这里先知道是什么就行。
处理空蔟
假设我们选定的某个中心点在一开始不幸落在了一篇数据稀疏的无人区，随着迭代的进行，所有数据点都会被其他更有吸引力的中心点吸引走，最终导致这个中心点所在的蔟变成一个空蔟。此时，算法将无法计算均值，中心点在数学上也就陷入了一个无定义状态。
为了修复这个问题，我们可以选择这样的策略：
扫描现有的所有蔟，并找到那个SSE最高的蔟。这个蔟通常是最不紧凑的蔟，或者说是最糟糕的蔟。
算法从这个高误差蔟中，挑选出当前距离中心点最远的那个数据点，并将其提拔为一个新的中心点。
这意味着我们并没有凭空捏造出一个点，而是强行将算法拟合最差的区域剥离出一个边缘点，并用它来探索之前未被充分利用的空间。
但是这个策略为什么会有效呢？因为在K-means的迭代过程中，SSE最高的蔟通常是那个被过度拉伸或者过度分散的蔟，这个蔟内的数据点之间的距离较大，导致了高误差。通过从这个蔟中挑选出一个距离中心点最远的数据点，我们实际上是在尝试将这个过于分散的蔟进行重新划分，从而有可能发现一个新的、更紧凑的蔟结构。
预处理与后处理
假设我们想要用K-means来对一组包含身高和年薪的数据进行聚类分析。身高的单位是米，但年薪的单位是万元。如果直接运行算法，会发生什么？
由于年薪的取值范围远大于身高的取值范围，在计算欧氏距离的时候，年薪的差异会完全主导距离的大小，导致身高的数值贡献几乎可以忽略不计。这样，算法会盲目的认为年薪相近的人就是相似的，而完全忽略了身高这个重要的特征。
因此，我们要把所有的特征缩放到同一个量纲尺度上，这就叫做预处理中的 Feature Scaling，数据标准化，来让不同维度在距离计算上拥有平等的话语权。常用的方法包括Min-Max缩放：将值映射到0和1之间；或者Z-score标准化：将值转换为均值为0，标准差为1的分布。
但是仅仅标准化还不够，现实生活中收集的数据往往混杂着一些极端的离群点，我们叫 Outliers。这些离群点可能是由于数据录入错误、测量误差或者是一些特殊情况导致的异常值。如果我们直接将这些离群点纳入K-means的计算中，它们可能会对中心点的位置产生极大的影响，导致整个聚类结果被扭曲。
因此预处理的第二部就是消除离群值。例如我们可以使用 $3\sigma$ 原则或者可视化手段来剔除这些离群点。
在K-means完成聚类之后，我们还可以进行一些后处理来进一步优化结果。
例如，Eliminate Small Clusters 可以用来剔除那些包含非常少量数据点的蔟。如果一个簇只包含极少数点，那么它很大概率不是一个真正的蔟，而更可能是一些噪声点或者是数据中的异常值。因此我们可以将这些微小的蔟标记成噪声，并将它们从最终的聚类结果中剔除掉，以提升结果的可解释性。
另一个后处理项目是 Split loose clusters，这代指那些SSE特别高的蔟，蔟内的哪些点相距甚元，抱团不够紧凑，很有可能一个簇内部隐藏着多个子簇。通过设定SSE的阈值，我们可以选择在这些松散的蔟上再次运行K-means，尝试将它们进一步细分成更紧凑的子簇。
最后我们也可以选择 Merge Clusters。如果两个蔟的中心彼此非常接近，且各自内部都很紧凑，那么它们很有可能本应属于同一个更大的自然蔟，只是被算法偶然切开。因此我们可以设定一个距离阈值，当两个蔟的中心点之间的距离小于这个阈值时，我们就将它们合并成一个更大的蔟，以更好地反映数据的内在结构。
而这些步骤也并非一定在K-means之后进行，实际上我们也可以在其他类型的聚类算法之后进行类似的预处理和后处理，以提升整体的聚类质量和结果的可解释性。
比如说，ISODATA算法是一种基于密度的聚类算法，它通过定义一个密度阈值来识别数据空间中的高密度区域，从而形成蔟。ISODATA算法的核心思想是：如果一个数据点周围的邻域内包含足够多的其他数据点，那么这个数据点就被认为是一个核心点，属于一个蔟；如果一个数据点周围的邻域内没有足够多的其他数据点，那么这个数据点就被认为是噪声或者边界点，不属于任何蔟。
二分K-means
既然我们知道K-means对于起始点极度敏感，以及在全量运行时带来的计算成本问题，那么我们有没有一种方法，能够在不牺牲太多性能的前提下，提升K-means的稳定性和效率呢？
二分K-means (Bisecting K-means) 就是这样一种方法，我们采用分治的策略，巧妙地在划分式聚类算法和层次化聚类算法之间找到了一个平衡点。整个过程一开始保留一整个数据集，随后在当前的所有蔟中挑选出内部最分散的那个蔟，并对它进行二分，使用K-means将它划分成两个子蔟。然后我们继续在所有的蔟中挑选出最分散的那个蔟，再次进行二分，直到我们最终得到了 $k$ 个蔟为止。
具体过程如下：
- 将整个数据集作为一个单一的蔟。并运行一次 $k=2$ 的K-means，将这个大蔟划分成两个子蔟。
- 挑选出当前所有蔟中，内部最松散，误差最大的那个蔟。执行 $k=2$ 的K-means，将这个蔟再次划分成两个子蔟。
- 重复步骤2，直到我们最终得到了 $k$ 个蔟为止。
由于我们每一次二分操作都记录了一个簇是如何被拆分成两个子蔟的，如果我们把这些拆分历史连接起来，就会自然生长出一棵二叉树。这意味着你既可以在中途停止，得到指定数量的划分结果，也可以保留完整的分裂树，用于后续任意粒度的切割。
K-means的限制与对策
我们之前说到K-means的一个主要缺点是它对初始中心点的位置非常敏感，容易陷入局部最优解。为了克服这个问题，我们采用了一些策略来优化初始中心点的选择。
但是除此之外，K-means由于建立在中心蔟的定义之上，它本质上在假设“蔟是围绕中心均匀辐射的球体”这一级和直觉之上。但问题就在于现实数据往往不服从这种完美的对称性，如果数据集中包含规模差异巨大的蔟时，K-means会出现明显的偏袒。
如果一个大蔟和小蔟相邻，由于大蔟包含更多的数据点，计算的中心点会被牢牢锚定在大蔟的之心附近。这样小蔟中的数据点就会被错误地划分到大蔟中去，导致小蔟被吞噬掉了。
更棘手的是K-means很难处理非球形结构的蔟。例如一个U形的蔟，K-means会试图将它划分成两个半圆形的蔟，而不是一个完整的U形。这是因为K-means在计算距离时，默认使用欧氏距离，这种距离度量方式更适合于球形的蔟结构。
但是方法总比困难多，既然K-means适合处理球形的蔟，那么我们就可以通过一些预处理手段来将非球形的数据转换成更适合K-means处理的形式。
例如上图，我们索性使用很多球形小蔟来拟合这个S形的结构。通过人为增加k值，将其设定的远大于真实的蔟数量，我们迫使算法将那些巨大的，非球形的复杂结构，来强行打散成这些小碎片。然而，切割只是第一步，真正的挑战在于如何合并它们。在得到大量碎片后，我们需要引入后处理逻辑，根据空间邻近性或连通性，将这些碎片重新缝合。
虽然这种方法在计算上略显冗余，且合并规则需要精心设计，但它巧妙地绕过了 K-means 对单一全局中心的依赖，为后续更高级的算法埋下了伏笔。
层次化聚类
这就是之前没详细展开讲的 Hierarchical Clustering。
如果K-means等这种划分式聚类算法是一次性地将数据切成若干个互不重叠的子集，那么层次聚类构建的是一个不断生长的决策树。数据点之间的相似性本身就是一个多层次的概念，就像生物分类学一样包含界门纲目科属种层层递进，层次聚类通过嵌套蔟的方式来组织数据，最后组成一个树状图（Dendrogram）。这个树状图不仅展示了数据点之间的相似性关系，还揭示了数据的内在层次结构。
在这个树状图中，每一个叶子节点都代表一个原始数据点，而每一次分支的汇合（或分叉）都记录了一次簇的合并（或分裂）事件。纵轴的高度通常代表了合并时的距离或相似度阈值。
层次聚类最迷人的特性在于它解耦了“聚类过程”与“簇的数量选择”。你不需要在算法开始前猜测 K 是多少，只需要在树状图生成后，用一把虚拟的剪刀在任意高度水平切断，就能瞬间得到对应粒度的划分结果。这意味着，同一个模型可以服务于从宏观概览到微观细分的多尺度分析需求，这在需要探索性数据理解或对应真实世界分类体系的场景中，具有不可替代的价值。
层次化聚类拥有两种基本的构造方式，由下到上和由上到下，讲的专业一些的话，这叫 Agglomerative 和 Divisive，分别是凝聚式和分列式。
凝聚式的操作自下而上，给定一系列数据点，它会将每一个数据点都视为一个独立的微蔟，然后在每一部迭代中，寻找空间距离最近的两个蔟，来将它们缝合成一个更大的蔟。如此往复，直到所有点最终汇聚成一个包含全集的超级蔟。
而分列式完全相反，采用自顶向下的策略。一开始我们将所有数据点强行纳入一个巨大的蔟中，然后在每一部寻找最该被分离开的蔟，一分为二，直到所有点都独立成蔟位置。这跟我们刚才说的二分K-means的思路非常类似，只不过二分K-means是基于K-means算法来进行二分，而这里的分列式层次聚类则是基于层次化的思想来进行二分。
这两种算法都高度依赖一个核心的数据结构，叫做 距离矩阵 (Distance Matrix)。这个矩阵记录了数据点之间的两两距离关系，是算法决策的基础。每一次合并或分裂操作，都会更新这个距离矩阵，以反映新的蔟结构和数据点之间的相似性关系。因此，距离矩阵的计算和更新效率直接影响了算法的性能。对于大规模数据集，距离矩阵的存储和计算可能成为瓶颈。
凝聚式算法
凝聚式算法在计算效率和工程实践中更为流行，整个过程可以被拆散为5个连贯的步骤：
计算所有点对之间的初始距离，构建出完整的距离矩阵。将每个数据点视为一个独立的蔟，初始时共有 $n$ 个蔟。
算法扫描矩阵，按照一个预设的距离度量标准，找到距离最近的两个蔟，并将它们合并成一个新的蔟。
合并之后，更新距离矩阵，重新计算新蔟与其他所有蔟之间的距离。
不断重复这个过程，直到矩阵中只剩下一个包含所有点的蔟，或者达到预设的停止条件。
这就是大致的流程了，但是其中有一个关键：我们该如何定义两个蔟之间的距离呢？这就是所谓的 Linkage Criteria，也就是我们在每一步合并时，如何衡量两个蔟之间的相似性或距离。
链接准则
我们目前会使用到四种主流的链接准则，分别是 MIN, MAX，Group Average 和基于目标函数的 Ward's Method。
MIN Linkage
MIN Linkage认为两个蔟之间的距离，完全由他们内部 最接近的那一对点 决定。无论岛屿A和B之间相距多远，只要它们之间存在一对点距离足够近，那么这两个蔟就会被认为是相似的，最终被合并在一起。
因此在更新距离矩阵的时候，我们不需要计算所有点对的平均或最远距离，只需要追踪并比较跨粗的最近邻距离即可。这意味着MIN本质上还是在执行一种局部贪婪策略，他只关心当前时刻哪两个点爱的最近，而不是关心蔟内其他点的分布态势。
虽然MIN能够顺着数据的局部股价捕捉任意复杂的非凸形状，但是对这种“最近邻”的极端依赖，也赋予了它一个及其脆弱的软肋：噪声点。
只要有一个离群点恰好落在了两个蔟之间的空地上，那么这个离群点就会成为这两个蔟的最近邻，导致它们被错误地合并在一起。算法会像串珠子一样，通过一系列局部最近的邻接关系，把本不属于同一结构的数据点连成一条长长的链，最终导致整个数据集被合并成一个巨大的、失去语义的簇。这意味着，在噪声密集或簇间边界模糊的场景下，MIN 的局部贪婪策略会引发全局性的结构误判，树状图也会因此失去层次分明的切割价值。
MAX Linkage
MAX Linkage则完全相反，它认为两个蔟之间的距离，完全由他们内部 最远的那一对点 决定。理论是，如果两个蔟之间最疏远的那一对点也足够亲密，那么剩下的点就更不成问题了。因此，在更新距离矩阵时，我们需要追踪并比较所有跨簇点对的距离，取其中的最大值作为簇间相似度。这意味着 MAX 本质上是在执行一种全局保守策略，它要求簇内的所有点都必须彼此靠近，任何一对点的疏远都会阻碍合并的发生。
由于 MAX 要求簇内所有点对都必须满足距离约束，它天然倾向于生成直径较小、形状接近球形的簇。由于噪声点通常位于蔟的边缘，且与蔟内核心点的距离往往很大，因此在MAX的评判体系下，这些边缘点会极大的拉高簇间距离，从而阻止噪声被轻易吸纳进簇内。
但是MAX相对于MIN来说，过于保守的合并条件也会导致它在处理具有复杂形状或密度变化的数据时，过早地将一些本应属于同一簇的点分割开来，从而产生过多的碎片化簇结构。如下图：
本身两个一大一小的圈圈，在MAX的评判体系下，你可以看见大圈的一部分被错误的拆到了小圈里去，导致了大簇都被过度切割。这是因为MAX在评判簇间距离时，过于关注那些最远的点对，而忽略了簇内其他点之间的紧密关系，从而导致了过度分割的问题。
Group Average Linkage
这个链接方式与我们对社交网络的判断很像。当你评估两个圈子是否相似的时，你不会只看它们之间关系最好的那两个人（MIN），也不会只看它们之间关系最差的那两个人（MAX），而是会综合考虑这两个圈子里所有人的关系，来判断这两个圈子整体上是否亲密。
算法会将两个蔟内所有点对之间的跨蔟距离全部计算出来，然后取算术平均值，来作为它们的亲疏标尺。Group Average 本质上是在执行一种“全局稀释”策略：单个噪声点或极端边缘点的距离，会被簇内大量正常点的距离所平均，从而无法轻易扭曲整体的合并决策。
它在抗噪声和抗异常值方面明显优于MIN，但与此同时也继承了MAX的某些集合偏好，也就是稍微偏向于生成更为紧凑、形状接近球形的簇结构。
Ward's Method
Ward's Method 则是基于目标函数的链接准则。
当我们准备将两个蔟合并时，我们会考虑这次合并会让整个系统的“内部混乱程度”增加多少？具体来说，它计算的是合并前后平方误差(SSE)的增量。算法会遍历所有可能的簇对组合，优先合并那个导致 SSE 增幅最小的蔟对。
Ward's Method 本质上是在贪婪地维护簇内的同质性，它只允许那些合并后依然能保持紧密抱团状态的簇走到一起。正因为这种基于误差增量的设计，Ward's Method 展现出了与 K-means 惊人的家族相似性，同样具备对噪声和异常值的强大抵抗力，同时也倾向于生成形状接近球形的簇结构。
而由于它天然地在优化SSE，因此其生成的层次结构末端往往能够直接作为K-means的优质初始点，来提升K-means的稳定性和最终结果的质量。
使用不同的链接准则，我们会得到完全不同的树状图结构，甚至是完全不同的聚类结果。但是有一点是共同的，那就是计算代价。层次聚类之所以无法直接应用于百万级的大规模数据集，根源在于它邻接矩阵的计算和更新机制。每一次合并或分裂操作都需要重新计算距离矩阵，尤其是在使用MAX或Group Average等链接准则时，需要对所有跨簇点对进行距离计算，这导致了算法的时间复杂度通常在 $O(n^3)$ 级别，空间复杂度也在 $O(n^2)$ 级别。
而计算开销还是表层限制，更深层的困境来源于算法的决策机制。凝聚是聚类本质上是一种贪心不可逆过程。一旦有两个蔟在早期某一步被错误合并，那么这个决策就会永久固化在树状图的底层，后续的所有合并操作都只能在这个被污染的拓扑结构上继续生长，永远无法回溯修正。这意味着算法缺乏全局视野，它只关注当前步的局部最优，而不评估这次合并对未来整体结构的长期影响。
分列式算法
我们刚才看过了自底而上，现在来看看自上而下有什么算法吧。
想象你不再是把散落的珍珠一颗颗串起来，而是手持一把剪刀，准备从一根完整的链条上剪出几段独立的珍珠串。由于直接在全局空间中暴力寻找最佳切割平面计算量太大，因此算法借用了最小生成树MST的结构作为底层骨架。
MST的构建过程遵循一种贪心的生长逻辑，首先算法会随机选择一个起始点作为树的根节点，然后在每一步中，它都会在所有“已在树中的点”与“尚在树外的点”的组合里，寻找距离最近的那一对 $(p, q)$。找到后，算法将 $q$ 正式拉入树中，并用一条边将 $p$ 和 $q$ 紧密连接。因此，MST 的生长过程就像藤蔓在空间中不断寻找最短路径向外蔓延，直到所有数据点都被这张无环连通图完整覆盖。
构建完成MST之后，分列式聚类不再需要复杂的距离矩阵迭代，而是只需要做一个简单的剪枝操作就可以了。由于MST恰好使用了 $N - 1$ 条边连接了所有 $N$ 个点，且每条边的权重严格对应了两点之间的原始距离，那么如果我们希望将数据划分为 $K$ 个蔟，算法只需要定位 MST 中权重最大的 $K-1$ 条边，切断它们即可。这样原本联通的图就会自然碎裂成 $K$ 个独立的子图，每个子图对应一个簇。
通过不断记录这些操作以及相对应的边权，我们就能够自顶而下地构建出一颗完整的层次树状图了。