Source-linked AI summary
Robust Ensemble Clustering Using Probability Trajectories
Dong Huang, Jian-Huang Lai, Chang-Dong Wang
TL;DR
The paper targets uncertain links and limited use of global information in ensemble clustering. It combines locally adaptive sparse-graph selection with random-walk probability trajectories, and reports significantly better clustering accuracy and efficiency than state-of-the-art approaches on real-world datasets.
Problem
Most existing ensemble clustering approaches overlook uncertain links and lack effective use of global structure to refine local links.
Method
The approach represents ensembles with microclusters, uses ENS to construct a sparse K-ENG graph, and derives PTS from random-walk trajectories for PTA and PTGP consensus functions.
Results
The approach significantly outperforms state-of-the-art approaches in clustering accuracy and efficiency across ten real-world datasets.
Takeaways & Limitations
Retaining a small number of probably reliable links and analyzing their global probability trajectories yields the paper's reported consensus-clustering gains.
Takeaways & Limitations
The formulation uses only the clustering ensemble as input and has no access to the dataset's original feature vectors.
Abstract
from arXiv · showhide
Although many successful ensemble clustering approaches have been developed in recent years, there are still two limitations to most of the existing approaches. First, they mostly overlook the issue of uncertain links, which may mislead the overall consensus process. Second, they generally lack the ability to incorporate global information to refine the local links. To address these two limitations, in this paper, we propose a novel ensemble clustering approach based on sparse graph representation and probability trajectory analysis. In particular, we present the elite neighbor selection strategy to identify the uncertain links by locally adaptive thresholds and build a sparse graph with a small number of probably reliable links. We argue that a small number of probably reliable links can lead to significantly better consensus results than using all graph links regardless of their reliability. The random walk process driven by a new transition probability matrix is utilized to explore the global information in the graph. We derive a novel and dense similarity measure from the sparse graph by analyzing the probability trajectories of the random walkers, based on which two consensus functions are further proposed. Experimental results on multiple real-world datasets demonstrate the effectiveness and efficiency of our approach.
1 INTRODUCTION
The paper addresses uncertain links and missing global structure in ensemble clustering with sparse graph representation and probability trajectory analysis. It selects probably reliable links, derives dense similarities from random walks, and proposes consensus functions evaluated on real-world datasets.
- Motivation: Existing ensemble clustering approaches often overlook uncertain links and lack mechanisms to incorporate global structure when refining local links.Unreliable links may mislead consensus, while co-association information primarily captures direct relationships.
- Approach: Microclusters provide a compact ensemble representation that reduces problem size and facilitates computation.The approach maps ensemble information to microclusters before constructing a microcluster similarity graph.
- Approach: Elite neighbor selection uses locally adaptive thresholds to retain a small number of probably reliable links in the K-ENG sparse graph.The authors report that preserving several percent or less than one percent of links can improve consensus results over using all links.
- Approach: Random walks on K-ENG use a transition matrix incorporating link weights and node sizes to derive dense probability trajectory based similarity.The resulting PTS similarity supports the PTA and PTGP consensus functions.
- Approach: The approach combines microcluster representation, ENS pruning, random-walk analysis, and consensus clustering in a single pipeline.The pipeline proceeds from base clusterings to MCA, MSG, K-ENG, PTS, and finally PTA or PTGP.
- Results: Experiments on real-world datasets report better clustering accuracy and efficiency than state-of-the-art approaches.The paper evaluates PTA and PTGP across multiple datasets and varying ensemble sizes.
2 RELATED WORK
Prior ensemble clustering work spans pair-wise similarity, median partition, and graph partitioning approaches, but commonly overlooks uncertain links and global structure. This paper addresses both limitations with sparse reliable-link graphs, random walks, and probability-trajectory similarity.
- Existing approaches: Ensemble clustering approaches are commonly categorized into pair-wise similarity, median partition, and graph partitioning methods.Pair-wise methods include EAC; graph-based methods include CSPA, HGPA, and MCLA.
- Existing approaches: Pair-wise similarity methods construct representations such as co-association matrices from object co-occurrence across base clusterings.EAC counts how often two objects occur in the same cluster.
- Existing approaches: Median partition methods seek a clustering maximizing similarity to all base clusterings, but the median partition problem is NP-complete.The large space of possible clusterings makes finding an optimal solution generally infeasible.
- Limitations: Most existing approaches overlook uncertain links and lack efficient use of global structure to refine local links.These limitations can affect consensus formation and the accuracy or efficiency of link refinement.
- Proposed approach: The proposed approach selects probably reliable neighbors using locally adaptive thresholds, then applies random walks and probability trajectories to derive PTS for PTA and PTGP.The method builds a sparse graph and uses a new transition probability matrix to explore global structure.
3 PROBLEM FORMULATION
The problem is defined over an ensemble of base partitions, with the goal of obtaining a consensus clustering that summarizes their information. This formulation uses only the clustering ensemble and excludes the original data features.
- Problem formulation: The dataset contains N objects, and the ensemble consists of M base partitions whose consensus clustering is sought.The consensus clustering π* is intended to summarize the information in the ensemble Π.
- Problem formulation: Each base clustering πk comprises nk clusters, and the collection of all base-clustering clusters contains Nc = Σk=1^M nk clusters.The notation defines the cluster containing each object within each base clustering.
- Problem formulation: This paper adopts the formulation in which the input is only the clustering ensemble, without access to the original feature vectors.A second formulation may use both the ensemble and data features, but it is not used here.
4 ENSEMBLE CLUSTERING USING PROBABILITY TRAJECTORIES
The approach compresses ensemble data into microclusters, prunes uncertain links with locally adaptive elite-neighbor selection, and uses random-walk probability trajectories to recover global structure. It derives a dense similarity measure and applies two consensus functions to obtain the final clustering.
- Elite Neighbor Selection: The method constructs a microcluster similarity graph and applies ENS to retain links selected by locally adaptive thresholds.ENS targets low-confidence connections while preserving a sparse graph of probably reliable links.
- Microcluster Based Representation: Microclusters compactly represent objects that share the same cluster assignments across all base clusterings.This reduces the graph problem size before similarity construction and random-walk analysis.
- Elite Neighbor Selection: K-ENG preserves only a small number of probably reliable links, with K values of 5–20 retaining several percent or less than one percent of MSG links.The paper reports that this sparse-link setting can produce better and more robust clustering results than retaining all links.
- From Sparse Graph to Dense Similarity: Random walks on K-ENG produce probability trajectories that represent nodes across multiple graph scales rather than at a single step.The transition design incorporates link weights and microcluster sizes, while trajectory comparison yields the PTS similarity measure.
- Consensus Functions: PTS supports two consensus functions, probability trajectory accumulation and probability trajectory based graph partitioning, for obtaining the final clustering.The resulting pairwise similarity can also be used by clustering algorithms based on pairwise similarity.
5 EXPERIMENTS
Experiments on ten real-world datasets evaluate NMI quality, parameter robustness, ensemble-size robustness, and execution time. PTA and PTGP generally outperform baseline ensemble clustering methods while remaining efficient as data size varies.
- Experimental setup: Experiments use ten real-world datasets and NMI, where higher NMI indicates better consensus clustering quality.Base clusterings are generated using repeatedly initialized k-means and RPCL algorithms.
- Parameter analysis: Moderate K and T values, typically in the interval [5, 20], produce consistently good and robust PTA and PTGP performance across benchmark datasets.The experiments vary K, which controls preserved neighbors, and T, which controls trajectory length.
- Parameter analysis: Using microclusters reduces graph size by about 80% to 90% for most datasets, while KDD99 variants use fewer than 1% as many nodes as original objects.Microcluster counts depend on dataset size and cluster-boundary shapes.
- Comparison with base clusterings: PTA and PTGP produce overall more accurate clusterings than base clusterings, with significant NMI improvements on ODR, LS, PD, KDD99-10P, and KDD99.The comparison uses average NMI scores and variances over 100 runs.
- Comparison with ensemble methods: PTA and PTGP achieve overall best clustering accuracy and robustness across benchmark datasets compared with ten ensemble clustering methods.PTA-AL is best or nearly best among pairwise similarity methods, while PTGP significantly outperforms five graph-partitioning methods.
- Robustness and efficiency: The proposed methods retain best or nearly best performance as ensemble size varies, with advantages increasing beyond ensemble size 20; execution times are evaluated up to 494,020 data points.PTA and PTGP show particularly strong robustness on MF, IS, PD, FC, KDD99-10P, and KDD99.
6 CONCLUSION
The paper combines sparse graph representation with probability trajectory analysis for ensemble clustering. Microclusters, elite-neighbor selection, and random walks support consensus functions that reportedly improve clustering accuracy and efficiency.
- Conclusion: Microclusters reduce computation, while elite neighbor selection identifies uncertain links locally and preserves a small set of probably reliable links.The approach reports better clustering than retaining all graph links regardless of reliability.
- Conclusion: A transition matrix incorporating link weights and node sizes drives random walks whose probability trajectories yield the dense PTS similarity measure.PTS is derived from the sparse K-ENG graph to capture global structure.
- Conclusion: Based on PTS, PTA and PTGP significantly outperform state-of-the-art approaches in clustering accuracy and efficiency across ten real-world datasets.The two methods are proposed as consensus functions using the derived similarity measure.