1. Bibliographic Information

• Title: M3W: Multistep Three-Way Clustering
• Authors: Mingjing Du (Member, IEEE), Jingqi Zhao, Jiarui Sun, and Yongquan Dong. Their affiliations are with Jiangsu Normal University, Xuzhou, China, and Shandong University, Jinan, China.
• Journal/Conference: The paper mentions "Member, IEEE" and uses a standard IEEE transaction format, suggesting publication in a reputable IEEE journal, likely related to data mining, cybernetics, or knowledge systems.
• Publication Year: The specific publication date is not provided in the text, but the references include papers up to 2021, suggesting the work was likely published in or after 2021.
• Abstract: The paper addresses key limitations in existing three-way clustering algorithms, namely their difficulty in leveraging sufficient information for ambiguous data points and their reliance on fixed, global thresholds that are hard to determine. To solve this, the authors propose a novel algorithm called Multistep Three-Way Clustering (M3W), inspired by sequential three-way decisions. M3W first employs a progressive erosion strategy to create a multilevel data structure, separating high-density core regions from lower-density boundary regions. It then uses a multistep allocation strategy that considers neighborhood information to gradually assign data points, starting from the core and moving outwards. This allows the algorithm to adaptively capture the inherent clustering structure of the data. The paper demonstrates through experiments on 18 benchmark datasets that M3W outperforms eight competing algorithms.
• Original Source Link: /files/papers/68ef675cc4954f31b6b55d82/paper.pdf (Formally published paper).

2. Executive Summary

• Background & Motivation (Why):

  • Core Problem: Traditional clustering methods, often called "two-way clustering," force each data point to belong to exactly one cluster. This is problematic for data with overlapping regions or ambiguous boundaries. Three-way clustering addresses this by introducing a "boundary region" for points that might belong to multiple clusters.
  • Identified Gaps: Existing three-way clustering algorithms suffer from two main weaknesses:
    1. They use a one-step allocation process with fixed, global thresholds. This approach is not adaptive to clusters with different shapes, densities, or distributions and struggles to handle complex boundaries. Determining these global thresholds is also a significant challenge.
    2. They often fail to gather sufficient information for points in the boundary regions, leading to potential misclassifications and limiting their fault tolerance.
  • Innovation: The paper introduces a novel approach inspired by sequential three-way decisions. Instead of making an immediate, final decision for every data point, this paradigm allows for deferring judgment on uncertain points until more information becomes available. The M3W algorithm applies this concept by processing data in stages, from the most certain (cluster cores) to the least certain (cluster boundaries).

• Main Contributions / Findings (What):

  1. A Novel Algorithm (M3W): The paper proposes M3W, a multistep three-way clustering algorithm that combines a progressive erosion strategy with the principles of sequential three-way decision-making. This iterative process is better suited for handling clusters with complex distributions and unclear boundaries.
  2. Multilevel Structure via Progressive Erosion: M3W uses a progressive erosion technique to peel away the outer, lower-density layers of data points, effectively creating a multilevel structure. This process clearly separates the high-density core regions of different clusters, which are easier to identify correctly.
  3. Multistep Allocation Strategy: Leveraging the multilevel structure, M3W employs a multistep clustering process. It first clusters the high-confidence core data and then iteratively assigns the eroded (boundary) data points level by level. This allows boundary points to gather information from their already-classified neighbors, increasing the probability of correct assignment.
  4. Superior Performance: Experimental results on 18 synthetic and real-world datasets show that M3W consistently outperforms eight state-of-the-art and benchmark clustering algorithms, demonstrating its effectiveness and robustness.

3. Prerequisite Knowledge & Related Work

Foundational Concepts

• Clustering: An unsupervised machine learning task that involves grouping a set of objects (data points) in such a way that objects in the same group (called a cluster) are more similar to each other than to those in other groups.

• Two-Way Clustering: The most common form of clustering, where every data point is assigned to at most one cluster. The relationship is binary: a point either "belongs to" or "does not belong to" a cluster.

• Three-Way Decision Theory: A framework for problem-solving that mimics human triadic thinking. Instead of making a binary decision (e.g., accept/reject), it divides a set into three regions: a positive region (accept), a negative region (reject), and a boundary region (defer judgment and seek more information). This theory originated from the interpretation of rough sets.

• Three-Way Clustering: An extension of clustering based on three-way decision theory. For any given cluster, a data point can:

  1. Belong-to certainly (Positive Region / Core Region): The point is definitively part of the cluster.

  2. Belong-to partially (Boundary Region): The point lies in an overlapping or ambiguous area and may belong to this cluster and potentially others.

  3. Not belong-to certainly (Negative Region): The point is definitively not part of the cluster. As shown in Image 2, this allows for a more nuanced representation of clusters, especially where they overlap. A cluster $C_i$ is represented by an interval set $(\underline{\mathbf{C}_i}, \overline{\mathbf{C}_i})$, where $\underline{\mathbf{C}_i}$ is the core region and $\overline{\mathbf{C}_i}$ is the core plus the boundary region.

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

• Sequential Three-Way Decisions: An extension of the three-way decision theory where decisions are not made in a single step. Instead, it uses a multilevel or iterative process. At each step, confident decisions (accept/reject) are made, while uncertain cases are passed to the next level for re-evaluation with more information or at a finer granularity. M3W is directly inspired by this concept.

• Density-Based Clustering: A family of algorithms (like DBSCAN) that identify clusters as dense regions of data points separated by sparser regions. M3W uses density estimation as a core component.

• Progressive Erosion: A technique, borrowed from mathematical morphology, where the outer layers of a data distribution are iteratively "eroded" or removed. In this paper, low-density points are considered the outer layers and are peeled away to reveal the high-density cores of clusters.

Previous Works and Differentiation

The paper positions M3W against several categories of existing work:

• Extensions of Classic Algorithms:

  • CE3: A three-way clustering framework based on K-means that uses contraction and expansion.
  • 3W-DBSCAN: A three-way extension of DBSCAN that uses a pair of density thresholds.
  • TWKM and TCM: Other variations of three-way K-means.
  • 3WDPET: A three-way version of density peak clustering.
  • Limitation: The performance of these methods is heavily tied to the underlying algorithms (K-means, DBSCAN). Furthermore, CE3, TWKM, TCM, and 3WDPET require the number of clusters to be specified in advance.

• Threshold-Based Methods: Most existing three-way clustering algorithms rely on a pair of fixed, global thresholds to partition data into core and boundary regions.

  • Limitation: A single pair of global thresholds cannot adapt to clusters with varying densities and distributions. The paper argues this is a fundamental flaw.

• Automatic Threshold Selection Methods: Some algorithms like 3WC-OR (using genetic algorithms) and another by Yu et al. (using universal gravitation) attempt to automatically determine the thresholds.

  • Differentiation: While these methods automate threshold selection, they still rely on a one-step allocation process driven by these estimated thresholds. In contrast, M3W uses a multistep, adaptive allocation scheme where decisions are made progressively, level by level, without relying on a single pair of global thresholds.

4. Methodology (Core Technology & Implementation)

The M3W algorithm is structured into three main phases, as illustrated in Image 1.

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

A. Dynamic Density Estimation

Instead of using a static density measure, M3W re-estimates the density of the remaining data points at each level of the erosion process. This dynamic approach allows the density estimation to adapt as the outer, sparser points are removed. The density $\rho_i^{(l)}$ of a data point $\mathbf{x}_i$ at level $l$ is calculated using an adaptive Gaussian kernel:

$$\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)}$: Density of point $\mathbf{x}_i$ at level $l$.
• $RkNN^{(l)}(\mathbf{x}_i)$: The set of reverse k-nearest neighbors of $\mathbf{x}_i$ at level $l$. A point $\mathbf{x}_j$ is a reverse neighbor of $\mathbf{x}_i$ if $\mathbf{x}_i$ is one of the k-nearest neighbors of $\mathbf{x}_j$. This measure helps identify the local density structure.
• $\| \mathbf{x}_j - \mathbf{x}_i \|$: Euclidean distance between points $\mathbf{x}_j$ and $\mathbf{x}_i$.
• $N_k^{(l)}(\mathbf{x}_j)$: The $k$-th nearest neighbor of $\mathbf{x}_j$ at level $l$. The denominator term $\| \mathbf{x}_j - N_k^{(l)}(\mathbf{x}_j) \|^2$ acts as an adaptive bandwidth, which varies based on the local data density around $\mathbf{x}_j$.

B. Progressive Erosion Strategy

This phase constructs the multilevel structure of the data. It's an iterative process over $L$ levels.

1. Density Calculation: At each level $l$, the density of all remaining points $\mathbf{X}^{(l)}$ is calculated using the dynamic density estimation formula above.
2. Erosion: Points with the lowest densities are identified as boundary points and are "eroded." Specifically, points whose density is below a cutoff value $\rho_c^{(l)}$ are removed. $$\mathbf { X } _ { E } ^ { ( l ) } = \Big \{ { \mathbf { x } _ { i } } \mid \rho _ { i } ^ { ( l ) } \leqslant \rho _ { c } ^ { ( l ) } \Big \} .$$ The paper sets $\rho_c^{(l)}$ such that the $10\%$ of points with the lowest densities are eroded at each level.
3. Update: The set of remaining points for the next level is updated: $$\mathbf { X } ^ { ( l + 1 ) } = \mathbf { X } ^ { ( l ) } \setminus \mathbf { X } _ { E } ^ { ( l ) }$$ After $L$ levels, the remaining data, $\mathbf{X}^{(L+1)}$, represents the high-confidence "initial" cores of the clusters. The eroded sets $\mathbf{X}_E^{(1)}, \dots, \mathbf{X}_E^{(L)}$ form the different layers of the boundary regions.

C. Multistep Clustering Process

This phase reconstructs the clusters in reverse order of erosion, from the inside out.

1) Connectivity-Based Approach for Core Clustering

The initial cores, $\mathbf{X}^{(L+1)}$, are clustered first. This is done using a connectivity-based method inspired by DBSCAN and HDBSCAN.

• Core Distance ($d_{\mathrm{core}}$): The distance from a point $\mathbf{x}_i$ to its $k$-th nearest neighbor.
• Adaptive Distance Threshold ($\varepsilon_{\mathrm{core}}^{(l)}(\mathbf{x}_i)$): A dynamic threshold that adapts based on neighborhood information from previously eroded layers. For the initial level ($l=1$), it's based on the mean and standard deviation of core distances. For subsequent levels, it's the minimum of the previous level's threshold and a value derived from the distances to its nearest eroded neighbors. This allows the threshold to shrink in dense areas.
• Mutual Reachability: Two core points $\mathbf{x}_i$ and $\mathbf{x}_j$ are considered mutually reachable if there's a path of core points between them, where the distance between any two adjacent points on the path is less than or equal to their mutual reachability distance threshold. All mutually reachable points in $\mathbf{X}^{(L+1)}$ are merged to form the initial core regions of the clusters, denoted as $\{\underline{\mathbf{C}_1^{(L+1)}}, \dots, \underline{\mathbf{C}_K^{(L+1)}}\}$.

2) Three-Way Approach for Boundary Assignment

Next, the eroded points are assigned back in reverse order: $\mathbf{X}_E^{(L)}, \dots, \mathbf{X}_E^{(1)}$. For each level $l$ (from $L$ down to 1), the points in $\mathbf{X}_E^{(l)}$ are assigned using a "two-stage" allocation scheme based on their neighbors in the already-clustered, higher-level data ($\mathbf{X}^{(l+1)}$).

• Probability Calculation: For an unassigned point $\mathbf{x}_i \in \mathbf{X}_E^{(l)}$, the probability of it belonging to an existing cluster core $\underline{\mathbf{C}_r^{(l)}}$ is calculated based on the labels of its $k$ nearest neighbors that are already in a core region (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| }$$ This is essentially the fraction of its core neighbors that belong to cluster $r$.

• Rule 1 (First Stage):

  • If $P(\mathbf{C}_r^{(l)} | \mathbf{x}_i) = 1$ (all core neighbors belong to a single cluster $r$), $\mathbf{x}_i$ is assigned to the core region of $\mathbf{C}_r$.
  • If $0 < P(\mathbf{C}_r^{(l)} | \mathbf{x}_i) < 1$ but it's the maximum probability, $\mathbf{x}_i$ is temporarily assigned to a "candidate" boundary region of $\mathbf{C}_r$ for further processing.

• Rule 2 (Second Stage): For a point $\mathbf{x}_i$ in a "candidate" boundary region of cluster $\mathbf{C}_r$:

  • If there exists another cluster $\mathbf{C}_s$ such that the probability gap is small ($P(\mathbf{C}_r^{(l)} | \mathbf{x}_i) - P(\mathbf{C}_s^{(l)} | \mathbf{x}_i) < 1/K$), the point is considered truly ambiguous. It is assigned to the boundary region of $\mathbf{C}_r$ and all other clusters $\mathbf{C}_s$ that satisfy this condition.

  • Otherwise, the point is considered confident enough and is assigned to the core region of $\mathbf{C}_r$.

    This process repeats until all points in $\mathbf{X}_E^{(1)}$ are assigned, completing the clustering.

D. Algorithm and Complexity Analysis

The full procedure is summarized in Algorithm 1.

The computational complexity is dominated by the $k$-NN searches during the erosion phase. With efficient data structures like k-d trees, the complexity is approximately $O(L k \bar{N}_C \log \bar{N}_C)$, where $L$ is the number of levels, $k$ is the number of neighbors, and $\bar{N}_C$ is the average number of points per level. Since $L$ and $k$ are much smaller than the total number of points $N$, the overall complexity is roughly $O(N \log N)$, making it efficient for large datasets.

5. Experimental Setup

• Datasets: The evaluation uses 18 benchmark datasets:

  • 8 Synthetic Datasets: Triangle1, Triangle2, S1, S2, T2, Pathbased, Ds2c2sc13, and T4. These are 2D datasets designed to test clustering algorithms on various challenges like different densities, shapes, and overlapping regions.
  • 10 Real-World Datasets: Glass, Dermatology, Digits, MSRA, Segmentation, Optdigits, Statlog, Pendigits, Htru, and Shuttle from repositories like UCI. The details are transcribed in the table below, as per the paper's Table II. Table II: Datasets Used in Experiments (Manual Transcription)

  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:

  1. Normalized Mutual Information (NMI):

     • Conceptual Definition: Measures the "mutual information" (statistical dependency) between the predicted clustering and the true ground-truth labels, normalized to a value between 0 and 1. A score of 1 means a perfect match, while 0 means the clustering is independent of the true labels.
     • Mathematical Formula: $$\mathrm{NMI}(Y, C) = \frac{I(Y, C)}{\sqrt{H(Y)H(C)}}$$
     • Symbol Explanation:
       • $Y$: The ground-truth class labels.
       • $C$: The predicted cluster labels.
       • I(Y, C): The mutual information between $Y$ and $C$.
       • H(Y) and H(C): The entropy of the ground-truth labels and cluster labels, respectively.

  2. Adjusted Rand Index (ARI):

     • Conceptual Definition: Measures the similarity between two data clusterings by considering all pairs of samples and counting pairs that are assigned in the same or different clusters in both the predicted and true clusterings. It is "adjusted for chance," so a random clustering will have an ARI close to 0. The range is -1 to 1, with 1 indicating a perfect match.
     • Mathematical Formula: $$\mathrm{ARI} = \frac{\text{Index} - \text{Expected Index}}{\text{Max Index} - \text{Expected Index}} = \frac{\sum_{ij}\binom{n_{ij}}{2} - [\sum_i\binom{a_i}{2}\sum_j\binom{b_j}{2}]/\binom{n}{2}}{\frac{1}{2}[\sum_i\binom{a_i}{2}+\sum_j\binom{b_j}{2}] - [\sum_i\binom{a_i}{2}\sum_j\binom{b_j}{2}]/\binom{n}{2}}$$
     • Symbol Explanation:
       • $n_{ij}$: Number of objects in true class $i$ and predicted cluster $j$.
       • $a_i$: Sum of $n_{ij}$ over $j$.
       • $b_j$: Sum of $n_{ij}$ over $i$.
       • $\binom{n}{2}$: Total number of pairs of objects.

  3. Pairwise F1 Score:

     • Conceptual Definition: Views clustering as a series of pairwise decisions. For each pair of points, it checks if they are correctly placed together or correctly separated. The F1 score is the harmonic mean of pairwise precision and recall.
     • Mathematical Formula: $$F1 = \frac{2 \cdot \text{Precision} \cdot \text{Recall}}{\text{Precision} + \text{Recall}}, \quad \text{where} \quad \text{Precision} = \frac{\text{TP}}{\text{TP} + \text{FP}}, \quad \text{Recall} = \frac{\text{TP}}{\text{TP} + \text{FN}}$$
     • Symbol Explanation:
       • TP (True Positives): Number of pairs of points that are in the same cluster in both ground truth and prediction.
       • FP (False Positives): Number of pairs that are in the same cluster in the prediction but not in the ground truth.
       • FN (False Negatives): Number of pairs that are not in the same cluster in the prediction but are in the ground truth.

• Baselines: M3W is compared against eight algorithms:

  • Three-Way: 3W-DBSCAN, 3W-DPET, CE3.
  • Overlapping/Soft: NEO-K-Means, Fuzzy C-means (FCM), Rough K-Means (RKM).
  • Two-Way: Kernel K-means (KnK-Means), Spectral Clustering (SC).

6. Results & Analysis

Core Results on Synthetic Datasets

The visual results on synthetic datasets demonstrate M3W's ability to handle complex structures.

• On Triangle1 and Triangle2 (Gaussian clusters), M3W perfectly or near-perfectly identifies the clusters, even when the margins are small (Image 8 and 9).

• On S1 and S2 (many overlapping clusters), M3W shows strong performance, whereas 3W-DBSCAN fails on S2 by merging adjacent clusters. M3W's erosion strategy effectively prevents this incorrect linking.

• On Pathbased (a challenging dataset with non-convex shapes), M3W is the only algorithm that gives a satisfactory result, correctly separating the half-circle from the two inner clusters.

• On T4 (complex shapes), M3W is again the only one to find the optimal structure (Image 3).

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

The quantitative results are transcribed from Table III below. M3W achieves the highest scores on nearly all synthetic datasets across all three metrics.

Table III: Performance Comparison of M3W on Synthetic Datasets (Manual Transcription)

Core Results on Real-World Datasets

The results on real-world datasets, transcribed from Table IV, confirm M3W's strong performance.

Table IV: Performance Comparison of M3W on Real-World Datasets (Manual Transcription)

• Key Findings: M3W achieves the highest NMI scores on all 10 real-world datasets. It also achieves the best ARI and F1 scores on at least 8 of them. The performance gap is particularly large on datasets like Pendigits, Htru, and Shuttle, where M3W outperforms the second-best algorithm by a significant margin. This confirms that the benefits of its multistep approach are not limited to synthetic data but translate to complex, high-dimensional real-world problems.

Running Time

Figure 11 compares the running time of M3W with other three-way clustering algorithms.

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

• 3WDPET is significantly slower than the others.
• On a log scale, M3W is shown to be faster than 3W-DBSCAN and CE3 in most cases.
• The performance advantage of M3W becomes more pronounced as the number of data instances increases, indicating better scalability. This aligns with its $O(N log N)$ complexity.

7. Conclusion & Reflections

• Conclusion Summary: The paper successfully introduces M3W, a novel three-way clustering algorithm that addresses fundamental limitations of existing methods. By incorporating a progressive erosion strategy to create a multilevel data structure and a multistep allocation scheme inspired by sequential three-way decisions, M3W can adaptively and accurately identify clusters, especially those with complex shapes and ambiguous boundaries. Extensive experiments validate its superior performance and efficiency compared to a wide range of competitors.

• Limitations & Future Work: The authors identify several directions for future research:

  1. Online Learning: Extending M3W to handle streaming data.
  2. Automatic Parameter Determination: Developing methods to automatically select the optimal values for the number of neighbors ($k$) and the number of levels ($L$).
  3. General Framework: Building a more general framework for sequential three-way clustering that could be applied to different types of algorithms.

• Personal Insights & Critique:

  • Novelty and Strength: The main strength of M3W is its elegant fusion of ideas from sequential decision theory and density-based clustering. The multistep, inside-out clustering process is intuitive and powerful. It provides a robust way to handle boundary points by allowing them to "wait" for more information (i.e., for their neighbors to be classified first). This is a significant conceptual advance over methods that rely on a single, global thresholding step.
  • Potential Limitations:
    • Parameter Sensitivity: While effective, the algorithm still has two key parameters, $k$ and $L$, that require tuning. The paper provides a range for them but doesn't offer a principled way to set them, a common challenge in clustering.
    • Density Assumption: Like other density-based methods, M3W may struggle with datasets containing clusters of vastly different densities, although the dynamic density estimation and adaptive thresholds are designed to mitigate this.
  • Overall Impact: M3W presents a strong and well-motivated contribution to the field of three-way clustering. Its core idea of sequential, information-gathering allocation could inspire new approaches in other areas of unsupervised learning where uncertainty and ambiguity are prevalent. The work is a prime example of how concepts from decision theory can enrich machine learning models.