1. 论文基本信息 (Bibliographic Information)

• 标题 (Title): M3W: 多步三向聚类 (Multistep Three-Way Clustering)
• 作者 (Authors): Mingjing Du (杜明晶), Jingqi Zhao (赵静琦), Jiarui Sun (孙嘉瑞), and Yongquan Dong (董永权)。
  • 作者隶属机构：江苏师范大学计算机科学与技术学院、美术学院。第一作者 Mingjing Du 为该校副教授。
• 发表期刊/会议 (Journal/Conference): 论文摘要中提到了 Member, IEEE 和 Index Terms，这通常是 IEEE Transactions 系列期刊的格式。虽然未明确写出期刊全称，但从内容和格式推断，它发表在一个高质量的 IEEE 期刊上。
• 发表年份 (Publication Year): 摘要中提到 Experimental results show that M3W achieves superior performance, verifying its advantages and effectiveness.，并且在参考文献中引用了 2021 和 2022 年的论文，可以推断本文发表于 2021 年之后。
• 摘要 (Abstract): 三向聚类是近年来聚类分析领域的研究热点。然而，现有算法在获取更多信息方面存在困难，且容错性受限。此外，基于一对固定的全局阈值进行一步式分配虽然直接，但难以揭示数据集内在的聚类结构，且阈值难以预先确定。受序贯三向决策的启发，本文提出了一种名为多步三向聚类 (M3W) 的算法。该算法首先使用渐进式侵蚀策略构建数据的多层级结构，使得外层可以从内层获取更多信息。然后，提出一种多步三向分配策略，充分考虑每个被侵蚀实例的邻域信息。通过将该分配策略与多层级结构相结合，算法能逐步获取更多信息以提高正确分配的概率，从而自适应地捕获数据集的内在聚类结构。实验在 18 个基准数据集上将 M3W 与 8 个竞争算法进行比较，结果表明 M3W 性能优越，验证了其有效性。
• 原文链接 (Source Link): /files/papers/68ef675cc4954f31b6b55d82/paper.pdf (已发表)

2. 整体概括 (Executive Summary)

• 研究背景与动机 (Background & Motivation - Why):
  • 核心问题： 现有的三向聚类 (three-way clustering) 算法在处理复杂数据，尤其是簇边界模糊或重叠时，存在显著的局限性。
  • 重要性与挑战 (Gap)：
    1. 信息获取不足与容错性差： 现有算法大多采用一步式决策，未能充分利用邻域信息来辅助决策，导致容错能力差。一个错误的分配可能引发连锁错误，影响最终聚类效果。
    2. 全局阈值的局限性： 大多数方法依赖一对固定的、全局的阈值来划分核心区域和边界区域。这种“一刀切”的方式无法适应不同簇的密度、形状和分布差异，难以准确揭示数据的内在结构，并且这些阈值通常需要用户手动设置，非常困难。
  • 创新思路： 论文的核心创新在于引入了序贯三向决策 (sequential three-way decisions) 的思想。其本质是将一个复杂的、一步到位的决策过程，分解为一系列从易到难、信息逐步丰富的多步决策过程。这使得算法能够首先处理最有把握的数据（簇核心），然后利用已确定的信息，逐步处理更模糊、更困难的数据（簇边界）。
• 核心贡献/主要发现 (Main Contribution/Findings - What):
  • 提出了 M3W 算法： 提出了一种新颖的多步三向聚类 (M3W) 算法，该算法将渐进式侵蚀策略与序贯三向决策思想相结合，能更好地处理具有复杂分布和不清晰边界的簇。
  • 设计了多层级结构构建方法： 采用渐进式侵蚀策略 (progressive erosion strategy) 来生成数据的多层级结构。该策略能有效分离相邻簇的初始核心区域，为后续的聚类过程打下良好基础。
  • 创建了多步聚类与分配流程： 在多层级结构的基础上，设计了一个多步聚类过程 (multistep clustering process)。该过程首先使用基于连接性的方法识别最高层级的核心簇，然后逐层向下，利用已有的聚类信息和邻域信息，通过一个“两阶段”分配方案来处理边界数据，自适应地捕获数据的内在结构。

3. 预备知识与相关工作 (Prerequisite Knowledge & Related Work)

• 基础概念 (Foundational Concepts):

  • 聚类 (Clustering): 一种无监督学习技术，旨在将数据集中的样本划分为若干个簇 (cluster)，使得同一簇内的样本彼此相似，而不同簇间的样本相异。
  • 双向聚类 (Two-way Clustering): 传统的聚类方法，一个样本与一个簇之间的关系只有两种：属于或不属于。这种方法难以处理簇之间存在重叠区域的现实情况。
  • 三向决策 (Three-way Decision): 一种源于粗糙集理论的决策模型，模仿人类的“三支思维”(triadic thinking)。它将一个论域划分为三个不相交的区域：正域 (positive region)、负域 (negative region) 和边界域 (boundary region)，并据此作出接受、拒绝或延迟决策三种不同类型的决策。
  • 三向聚类 (Three-way Clustering): 将三向决策理论应用于聚类分析。它定义了样本与簇之间的三种隶属关系：确定属于、可能属于和确定不属于。

    • 一个簇 $C$ 因此被划分为三个区域：

      • 正域/核心区 (Positive/Core Region, $\widehat{C}$): 包含那些确定无疑属于该簇的样本。
      • 边界区 (Boundary Region, $\ddot{C}$): 包含那些可能属于该簇，也可能属于其他簇的样本，通常位于簇的重叠或模糊地带。
      • 负域 (Negative Region, $\widetilde{C}$): 包含那些确定不属于该簇的样本。

    • 在表示上，一个三向簇 $C_i$ 通常用一个区间集 (interval set) $(\underline{C_i}, \overline{C_i})$ 来描述，其中 $\underline{C_i} = \widehat{C_i}$ 称为下界 (lower bound)，$\overline{C_i} = \widehat{C_i} \cup \ddot{C_i}$ 称为上界 (upper bound)。

    • 下图直观展示了双向聚类和三向聚类的区别：

      该图像是示意图，展示了两种不同的数据聚类场景。(a) 部分显示了两个相邻的聚类C1和C2，其中一些数据点位于两者之间，难以明确归属。 (b) 部分则描绘了多步三向聚类（M3W）策略下的聚类结果，通过内层核心聚类（如$\widehat{C}_1, \widehat{C}_2$）和外层区域（如$\ddot{C}_1, \ddot{C}_2$）的划分，更精细地揭示了数据的多层结构，并有助于更准确地处理边界点。

      图 (a) 中，边界点被强制分配给某个簇。图 (b) 中，三向聚类通过核心区 $\widehat{C}$ 和边界区 $\ddot{C}$ 的划分，更合理地处理了重叠区域。

  • 序贯三向决策 (Sequential Three-way Decision): 也称为多步三向决策，是一种处理成本敏感、信息不完备问题的决策理论。它通过构建一个多层级的粒度结构，在高层级（信息粗糙但明确）对部分数据做出接受或拒绝决策，而将信息不充分的数据推迟到更低的、粒度更细的层级去处理。随着层级下降，信息越来越丰富，从而可以做出更准确的决策。这是 M3W 算法的核心思想来源。

• 前人工作 (Previous Works):

  • 基于 K-Means 的扩展：
    • CE3: 引入数学形态学中的侵蚀和膨胀思想，提出一个“收缩-扩张”框架。
    • TWKM: 采用扰动分析来分离核心区域。
    • TCM: 集成了三向权重和三向分配。
    • 局限性： 这些方法都依赖于 K-Means，需要预先指定簇的数量 $K$，且对初始中心点敏感。
  • 基于密度聚类的扩展：
    • 3W-DBSCAN: 将 DBSCAN 的结果通过一个类型函数和一对密度阈值转化为三向簇。
    • 3WDPET: 结合了证据理论和密度峰值聚类。
    • 局限性： 结果严重依赖于原始算法（DBSCAN 或密度峰值）的性能，且同样面临阈值设定的问题。
  • 自动阈值选择方法：
    • 3WC-OR: 使用遗传算法自动确定划分阈值。
    • 其他工作：利用万有引力思想或样本相似性来自动调整阈值。
    • 局限性： 虽然解决了手动调参问题，但其聚类结果仍然是由最终估计出的（全局）阈值驱动的，本质上还是一步式决策，未能充分利用数据的局部和多层结构信息。

• 差异化分析 (Differentiation):

  • 与上述所有方法的核心区别在于，M3W 不是一个一步式的决策过程。它借鉴了 序贯三向决策 的思想，设计了一个多步、迭代的聚类流程。
  • 它不依赖于一对固定的全局阈值来划分核心和边界。相反，它通过 渐进式侵蚀 动态地构建出一个数据的多层结构，然后从最可靠的核心层开始，逐层向外扩展，利用已有的信息自适应地、局部地决策每个数据点的归属。这种从内到外、从确定到不确定的处理方式是其最根本的创新点。

4. 方法论 (Methodology - Core Technology & Implementation Details)

M3W 算法的整体架构如下图所示，主要包含两个核心阶段：侵蚀阶段（构建多层级结构）和聚类阶段（多步聚类过程）。

该图像是M3W算法的架构示意图（图2），展示了从输入到输出的聚类流程。它首先通过渐进式“侵蚀过程”构建数据的多层级结构。接着，在聚类阶段，结合基于连接的聚类和三支聚类策略，逐步对数据点进行识别和分配，以增加正确分配的概率。最终，原始输入数据被清晰地划分为两个不同的聚类输出，有效揭示了数据集的内在结构。

• 方法原理 (Methodology Principles):

  • 核心思想： 簇的核心区域比边界区域更容易被正确聚类。因此，可以先通过一种“剥洋葱”的方式（即 侵蚀）将边界数据层层剥离，直到剩下高度分离的簇核心。然后，再反向地、逐层地将剥离的数据分配回去，在这个过程中，后分配的数据可以利用先分配数据提供的丰富信息，从而提高分配的准确性。

• 方法步骤与流程 (Steps & Procedures):

  阶段一：渐进式侵蚀策略 (Progressive Erosion Strategy)

  此阶段的目标是构建数据的多层级结构。

  1. 动态密度估计 (Dynamic Density Estimation):

     • 在每个侵蚀层级 $l$，对所有尚未被侵蚀的数据 $\mathbf{X}^{(l)}$ 中的每个点 $\mathbf{x}_i$ 重新计算其密度。密度计算采用一种自适应的高斯核密度估计，其公式为： $$\rho _ { i } ^ { ( l ) } = \sum _ { \mathbf { x } _ { j } \in R \mathbf { k } \mathbf { N } \mathbf { N } ^ { ( l ) } ( \mathbf { x } _ { i } ) } \exp \biggl ( - \frac { \| \mathbf { x } _ { j } - \mathbf { x } _ { i } \| ^ { 2 } } { \| \mathbf { x } _ { j } - N _ { k } ^ { ( l ) } \bigl ( \mathbf { x } _ { j } \bigr ) \| ^ { 2 } } \biggr ) .$$
     • 符号解释：
       • $\rho_i^{(l)}$: 实例 $\mathbf{x}_i$ 在第 $l$ 层的密度。
       • $RkNN^{(l)}(\mathbf{x}_i)$: 实例 $\mathbf{x}_i$ 在第 $l$ 层的反向 k 近邻 (reverse k-nearest neighbors) 集合，即所有将 $\mathbf{x}_i$ 视为其 k 近邻之一的点的集合。使用 RkNN 可以更好地反映数据的局部密度分布。
       • $N_k^{(l)}(\mathbf{x}_j)$: 实例 $\mathbf{x}_j$ 在第 $l$ 层的第 $k$ 个最近邻。分母 $\| \mathbf { x } _ { j } - N _ { k } ^ { ( l ) } \bigl ( \mathbf { x } _ { j } \bigr ) \| ^ { 2 }$ 是一个自适应的带宽，使得密度估计对不同密度的区域更鲁棒。
       • 动态性体现在每一层都会基于当前剩余的点重新计算 kNN、RkNN 和密度，而非使用全局固定的密度值。

  2. 侵蚀过程 (Erosion):

     • 计算完当前层所有点的密度后，将密度值最低的一部分点视为边界点并“侵蚀”掉。
     • 被侵蚀的点集 $\mathbf{X}_E^{(l)}$ 定义为： $$\mathbf { X } _ { E } ^ { ( l ) } = \Big \{ { \mathbf { x } _ { i } } \mid \rho _ { i } ^ { ( l ) } \leqslant \rho _ { c } ^ { ( l ) } \Big \} .$$ 其中 $\rho_c^{(l)}$ 是当前层的密度截断阈值。论文中，该阈值通过百分位设置，例如每层侵蚀掉密度最低的 10% 的数据。
     • 更新剩余点集，进入下一层：$\mathbf{X}^{(l+1)} = \mathbf{X}^{(l)} \setminus \mathbf{X}_E^{(l)}$。
     • 重复该过程 $L$ 次（$L$ 为总层数，是一个超参数），最终得到一个多层级结构：最高层的核心数据 $\mathbf{X}^{(L+1)}$ 和每一层被侵蚀的数据集 $\{\mathbf{X}_E^{(L)}, \dots, \mathbf{X}_E^{(1)}\}$。

  阶段二：多步聚类过程 (Multistep Clustering Process)

  此阶段的目标是自顶向下地重建簇，形成三向聚类结果。

  1. 基于连接性的核心聚类 (Connectivity-Based Approach):

     • 首先处理最高层、最稀疏、最易于分离的核心数据 $\mathbf{X}^{(L+1)}$。
     • 采用一种受 DBSCAN 启发的基于连接性的方法。两个点 $\mathbf{x}_i, \mathbf{x}_j \in \mathbf{X}^{(L+1)}$ 如果满足 $\| \mathbf{x}_i - \mathbf{x}_j \| \le \varepsilon_{mr}(\mathbf{x}_i, \mathbf{x}_j)$，则认为它们是可达的。其中 $\varepsilon_{mr}$ 是一个自适应的相互可达距离阈值，它考虑了每个点的局部密度。
     • 通过合并所有相互可达的点，形成初始的核心簇 $\{\underline{C_1}^{(L+1)}, \dots, \underline{C_K}^{(L+1)}\}$。在这一步，所有点都被视为核心点，因此它们的下界和上界是相同的。

  2. 三向分配 (Three-Way Approach):

     • 接下来，逆序处理被侵蚀的数据，从 $\mathbf{X}_E^{(L)}$ 开始，逐层向下到 $\mathbf{X}_E^{(1)}$。
     • 在处理第 $l$ 层的 $\mathbf{X}_E^{(l)}$ 时，对其中每个未标记的点 $\mathbf{x}_i$，采用一个“两阶段”分配方案：
       • 计算隶属概率： 首先计算 $\mathbf{x}_i$ 属于每个现有簇 $C_r$ 的概率。该概率基于其在已标记的核心区域中的 k 近邻（称为 core k nearest neighbors）来定义： $$P \left( \mathbf { C } _ { r } ^ { ( l ) } | \mathbf { x } _ { i } \right) = \frac { \left| \left\{ \mathbf { x } _ { j } | \mathbf { x } _ { j } \in C N ^ { ( l ) } ( \mathbf { x } _ { i } ) \right\} \cap \left\{ \mathbf { x } _ { p } | \mathbf { x } _ { p } \in \underline { { \mathbf { C } _ { r } ^ { ( l ) } } } \right\} \right| } { \left| C N ^ { ( l ) } ( \mathbf { x } _ { i } ) \right| }$$ 符号解释：
         • $CN^{(l)}(\mathbf{x}_i)$: $\mathbf{x}_i$ 在已标记的核心点中的 k 近邻集合。
         • $\underline{C_r^{(l)}}$: 第 $r$ 个簇在当前步骤的核心区域。
         • 这个公式本质上是计算 $\mathbf{x}_i$ 的核心邻居中，有多大比例属于簇 $C_r$。
       • 第一阶段决策 (Rule 1):
         • 如果 $\mathbf{x}_i$ 的所有核心邻居都只属于一个簇 $C_r$（即 $P(\mathbf{C}_r^{(l)}|\mathbf{x}_i) = 1$），则将 $\mathbf{x}_i$ 确定地分配到 $C_r$ 的核心区域 $\underline{C_r}$。
         • 如果 $\mathbf{x}_i$ 的核心邻居分属不同簇，但属于 $C_r$ 的概率最高（即 $0 < P(\mathbf{C}_r^{(l)}|\mathbf{x}_i) < 1$ 且为最大值），则暂时将 $\mathbf{x}_i$ 放入 $C_r$ 的**“候选”边界区域**，等待第二阶段决策。
       • 第二阶段决策 (Rule 2):
         • 对于每个在“候选”边界区域的点 $\mathbf{x}_i$，检查其属于第二大概率簇 $C_s$ 的情况。
         • 如果概率差距很小，即 $P(\mathbf{C}_r^{(l)}|\mathbf{x}_i) - P(\mathbf{C}_s^{(l)}|\mathbf{x}_i) < 1/K$（$K$ 是当前簇数量），说明 $\mathbf{x}_i$ 确实位于模糊的边界上。此时，将 $\mathbf{x}_i$ 分配到 $C_r$ 的边界区域 $\ddot{C_r}$，并同时将其加入所有满足此条件的簇 $C_s$ 的边界区域。这意味着 $\mathbf{x}_i$ 将属于多个簇的上界。
         • 否则，如果概率差距较大，说明 $\mathbf{x}_i$ 还是更倾向于属于 $C_r$。此时，将其从“候选”边界区域移出，分配到 $C_r$ 的核心区域 $\underline{C_r}$。

  3. 迭代更新： 处理完一层的所有数据后，簇的核心区域和边界区域都得到了扩展。然后继续处理下一更外层的数据，重复上述过程，直到所有数据点都被分配。

• 算法复杂度分析 (Complexity Analysis):

  • 算法的主要开销在于 k-NN 搜索。使用优化的数据结构（如 k-d 树），k-NN 搜索的复杂度约为 $O(N \log N)$。
  • 整个算法涉及 $L$ 次侵蚀和分配，每次处理的数据量递减。论文分析得出，M3W 的整体时间复杂度约为 $O(L k \bar{N}_C \log \bar{N}_C)$，其中 $L$ 和 $k$ 远小于 $N$，$\bar{N}_C$ 约等于 $N$。因此，总体复杂度近似为 $O(N \log N)$，具有良好的可扩展性。

5. 实验设置 (Experimental Setup)

• 数据集 (Datasets):

  • 实验共使用了 18 个基准数据集，分为两类：

    • 8 个合成数据集： Triangle1, Triangle2, S1, S2, T2, Pathbased, Ds2c2sc13, T4。这些数据集具有多样的形状、密度和重叠程度，用于直观验证算法处理复杂结构的能力。
    • 10 个真实世界数据集： Glass, Dermatology, Digits, MSRA, Segmentation, Optdigits, Statlog, Pendigits, Htru, Shuttle。这些数据集来自 UCI 等公开数据源，用于评估算法在实际应用中的性能。

  • 下表是转录自原文 Table II 的数据集详细信息：

    Data sets	#Instances	#Features	#Classes
    Triangle1	1000	2	4
    Triangle2	1000	2	4
    S1	5000	2	15
    S2	5000	2	15
    T2	4000	2	6
    Pathbased	300	2	3
    Ds2c2sc13	588	2	13
    T4	7236	2	6
    Glass	214	10	6
    Dermatology	366	34	6
    Digits	1797	64	10
    MSRA	1799	256	12
    Segmentation	2310	19	7
    Optdigits	5620	64	10
    Statlog	6435	36	6
    Pendigits	10992	16	10
    Htru	17898	8	2
    Shuttle	22170	9	3

• 评估指标 (Evaluation Metrics):

  • 归一化互信息 (Normalized Mutual Information, NMI):
    1. 概念定义: NMI 是一个源于信息论的指标，用于衡量两个聚类结果之间的一致性程度。它度量的是一个聚类结果中包含的关于另一个聚类结果的信息量，并进行了归一化处理，使其值范围在 0 到 1 之间。NMI 为 1 表示两个聚类结果完全匹配，为 0 表示两个聚类结果完全独立（随机）。它对簇的数量不敏感。
    2. 数学公式: $$\mathrm{NMI}(Y, C) = \frac{I(Y, C)}{\sqrt{H(Y)H(C)}}$$
    3. 符号解释:
       • $Y$: 真实标签的集合。
       • $C$: 聚类算法输出的簇标签集合。
       • I(Y, C): $Y$ 和 $C$ 之间的互信息 (Mutual Information)。
       • H(Y) 和 H(C): $Y$ 和 $C$ 的熵 (Entropy)。
  • 调整兰德指数 (Adjusted Rand Index, ARI):
    1. 概念定义: ARI 通过计算数据点对在真实标签和聚类结果中的分配一致性来衡量聚类质量。它考虑了所有点对，并根据它们是“同类同簇”、“异类异簇”、“同类异簇”还是“异类同簇”进行计数。ARI 经过调整以消除随机分配的影响，其值范围通常在 -1 到 1 之间。值为 1 表示完美匹配，接近 0 表示随机分配。
    2. 数学公式: $$\mathrm{ARI} = \frac{\sum_{ij}\binom{n_{ij}}{2} - [\sum_i\binom{a_i}{2}\sum_j\binom{b_j}{2}] / \binom{n}{2}}{[\sum_i\binom{a_i}{2} + \sum_j\binom{b_j}{2}]/2 - [\sum_i\binom{a_i}{2}\sum_j\binom{b_j}{2}] / \binom{n}{2}}$$
    3. 符号解释:
       • $n_{ij}$: 同时在真实类别 $i$ 和预测簇 $j$ 中的样本数。
       • $a_i$: 真实类别 $i$ 中的样本数。
       • $b_j$: 预测簇 $j$ 中的样本数。
       • $n$: 总样本数。
  • 成对 F1 分数 (Pairwise F1 Score):
    1. 概念定义: 该指标同样从数据点对的角度来评估聚类。它将聚类任务视为一个二分类问题：对于任意一对点，预测它们是否属于同一个簇。F1 分数是成对精确率 (Precision) 和成对召回率 (Recall) 的调和平均值，综合了这两方面的表现。值域为 [0, 1]，越高越好。
    2. 数学公式: $$F1 = \frac{2 \times \mathrm{Precision} \times \mathrm{Recall}}{\mathrm{Precision} + \mathrm{Recall}}$$ 其中，Precision = TP / (TP + FP)，Recall = TP / (TP + FN)。
    3. 符号解释:
       • TP (True Positive): 真实同类且被分到同簇的点对数。
       • FP (False Positive): 真实异类但被分到同簇的点对数。
       • FN (False Negative): 真实同类但被分到异簇的点对-数。

• 对比基线 (Baselines):

  • 论文选择了 8 个有代表性的算法进行比较，涵盖了三向聚类、软聚类和传统（双向）聚类：
    • 三向聚类算法： 3W-DBSCAN, 3W-DPET, CE3。
    • 可处理重叠的算法： NEO-K-Means。
    • 软聚类算法： Fuzzy C-means (FCM), Rough K-Means (RKM)。
    • 传统双向聚类算法： Kernel K-means (KnK-Means), Spectral Clustering (SC)。
  • 这些基线的选择覆盖了不同的聚类思想（基于密度、划分、谱方法）和边界处理方式，使得比较非常全面。

6. 实验结果与分析 (Results & Analysis)

• 核心结果分析 (Core Results Analysis):

  • 合成数据集上的表现：

    • 在 Triangle1 和 Triangle2 数据集上（下图为 Triangle1 的结果），M3W、3W-DBSCAN 和 3W-DPET 表现出色，能够完美区分高斯簇。

      该图像是图3，展示了M3W与其他八种算法在Triangle1数据集上的聚类结果。M3W（a）清晰地识别出数据集中的四个独立聚类，相较于其他算法，其聚类效果更准确、边界更清晰，验证了其优势和有效性。

    • 在 S1 和 S2 数据集上，簇之间存在不同程度的重叠。M3W 表现鲁棒，而 3W-DBSCAN 在 S2 上因簇间距过小而错误地将多个簇合并。这凸显了 M3W 的侵蚀策略在分离相邻簇方面的优势。

    • 在 Pathbased 和 T4（下图）等具有复杂非凸形状和模糊边界的数据集上，M3W 是唯一能够准确识别所有簇结构的算法，展现了其处理任意形状簇的强大能力。其他算法或无法处理非凸形状，或在边界处产生大量错误划分。

      该图像是图10，展示了T4数据集上的聚类结果。它比较了M3W算法与3W-DBSCAN、3W-DPET等八种竞争算法的性能。M3W（a）清晰地识别出四种聚类结构，其结果比其他算法更准确地反映了数据的内在分布，验证了其优势。

    • 量化结果 (Table III)： 转录的表格数据显示，M3W 在所有合成数据集上的 NMI, ARI, F1 指标几乎都取得了最高分，显著优于所有对比算法。

  • 真实世界数据集上的表现：

    • 量化结果 (Table IV)： 转录自原文 Table IV 的数据显示，M3W 的性能同样出色。在 10 个真实数据集上，M3W 在 所有 NMI 指标上均获得第一，并且在 ARI 和 F1 指标上的表现也绝大多数是最好的。例如，在 Pendigits, Htru, Shuttle 等数据集上，M3W 的性能比第二名高出超过 10%，优势巨大。这充分证明了 M3W 的有效性和泛化能力。
    • 综合分析： M3W 的优越性归功于其两个核心机制：1) 渐进式侵蚀 揭示了簇的自然结构，有效分离了核心；2) 多步分配策略 充分利用了邻域信息，逐步求精，准确地划分了边界。

  • 运行时间分析：

    • 下图比较了 M3W 与其他三向聚类算法在不同数据量下的运行时间。

      该图像是图11，展示了不同算法的运行时间比较。图(a)采用线性Y轴，图(b)采用对数Y轴。随着数据量的增加，M3W、3W-DBSCAN、CE3和3WDPET四种算法的运行时间均呈上升趋势。在绝大多数数据点上，M3W的运行时间优于其他三种算法，尤其在对数尺度下M3W（红色线）的效率优势更明显，验证了其在效率方面的优势。

    • 从图 (a) 和图 (b) (对数坐标) 可以看出，3WDPET 效率最低。M3W 在大多数情况下比 3W-DBSCAN 和 CE3 更快。随着数据量的增加，M3W 的效率优势更加明显，表明其具有更好的可扩展性 (scalability)，这与 $O(N \log N)$ 的理论复杂度分析相符。

• 消融实验/参数分析 (Ablation Studies / Parameter Analysis):

  • 论文中没有明确设立一个名为“消融研究”的章节。但是，其方法的整个设计思想本身就隐含着对各组件重要性的论证。例如，如果没有 渐进式侵蚀，算法就无法构建多层结构，也就无法实现 多步分配。如果没有 多步分配，仅靠核心聚类是无法处理边界点的。
  • 论文对两个关键超参数 $k$ (邻居数) 和 $L$ (层数) 进行了分析。实验部分展示了在不同数据集上取得最优结果时所用的参数值（见 Table III 和 Table IV 中的 Params 列），表明这些参数确实需要根据数据集特性进行调整。

7. 总结与思考 (Conclusion & Personal Thoughts)

• 结论总结 (Conclusion Summary):

  • 本文成功提出了一种新颖的三向聚类算法 M3W。该算法通过创新的多步决策过程，有效解决了现有三向聚类算法依赖全局阈值、信息利用不充分的问题。
  • M3W 结合了渐进式侵蚀和序贯三向决策思想，能够自适应地捕获具有复杂形状、不同密度和模糊边界的数据集的内在结构。
  • 在 18 个基准数据集上的大量实验表明，M3W 在聚类效果和运行效率上均显著优于多种先进的对比算法。

• 局限性与未来工作 (Limitations & Future Work):

  • 参数依赖： 算法的性能依赖于两个关键参数 $k$ (邻居数) 和 $L$ (侵蚀层数)。作者承认，自动确定这些参数是一个有待解决的重要问题。
  • 未来方向：
    1. 将 M3W 扩展到在线学习 (online learning) 场景，以处理流数据。
    2. 研究参数自动选择机制。
    3. 开发一个更通用的序贯三向聚类框架。

• 个人启发与批判 (Personal Insights & Critique):

  • 启发：
    • 这篇论文最大的启发是将“分而治之”和“由易到难”的思想引入了聚类问题。序贯三向决策 提供了一个非常优雅的理论框架来解决不确定性问题，即将复杂问题分解为一系列信息逐步递增的子问题。这种思想不仅适用于聚类，也可以迁移到半监督学习、主动学习等领域，即先处理置信度高的样本，再利用它们的信息去处理模糊样本。
    • 渐进式侵蚀 是一种非常巧妙的、非参数化的方式来识别簇的核心。相比于依赖全局密度阈值的方法，这种逐层剥离的方式更加鲁棒和自适应。
  • 批判性思考：
    • 参数敏感性： 尽管 M3W 性能优越，但其对 $k$ 和 $L$ 的依赖可能是其在实际应用中的一个障碍。$L$ 的选择直接决定了核心区域的大小和边界区域的层数，设置不当可能会导致核心过小或侵蚀不足。虽然作者提到了这是未来工作，但在当前版本中，这无疑是一个局限。
    • 对噪声的鲁棒性： 论文虽然提到了 DBSCAN 的思想，但没有明确讨论 M3W 对噪声点的处理机制。在侵蚀过程中，噪声点（密度极低）可能会在第一层就被剥离，但后续如何处理它们（是标记为噪声还是分配到某个边界）并未详细说明。
    • 高维数据下的性能： 实验中的真实数据集最高维度为 256 (MSRA)。在更高维度的空间中，“距离”和“密度”的定义可能会变得不那么可靠（维度灾难）。M3W 在非常高维的数据集上的表现有待进一步验证。