PaperlayerView exact revision on arXiv

Source-linked AI summary

Enhanced Ensemble Clustering via Fast Propagation of Cluster-wise Similarities

Dong Huang, Chang-Dong Wang, Hongxing Peng, Jianhuang Lai, Chee-Keong Kwoh

arXiv:1810.12544v1cs.LGstat.ML

TL;DR

Existing ensemble-clustering methods often remain object-level and focus on direct relationships, leaving higher-level and multi-scale indirect information underused. The paper propagates cluster-wise similarities through random walks, maps them into an enhanced co-association matrix, and reports superior clustering quality and efficiency over state-of-the-art methods across multiple datasets.

  • Problem

    Existing ensemble-clustering algorithms often overlook higher-level ensemble information and multi-scale indirect relationships beyond direct object co-occurrence.

  • Method

    The method builds a Jaccard-weighted graph of base clusters, propagates similarities through random walks, maps them to an enhanced co-association matrix, and applies two consensus functions.

  • Results

    Experiments on multiple datasets report advantages over state-of-the-art ensemble-clustering methods in clustering quality and efficiency.

  • Takeaways & Limitations

    The approach combines object-wise co-occurrence with multi-scale cluster-wise structural information for consensus clustering.

Abstract

from arXiv · show

Ensemble clustering has been a popular research topic in data mining and machine learning. Despite its significant progress in recent years, there are still two challenging issues in the current ensemble clustering research. First, most of the existing algorithms tend to investigate the ensemble information at the object-level, yet often lack the ability to explore the rich information at higher levels of granularity. Second, they mostly focus on the direct connections (e.g., direct intersection or pair-wise co-occurrence) in the multiple base clusterings, but generally neglect the multi-scale indirect relationship hidden in them. To address these two issues, this paper presents a novel ensemble clustering approach based on fast propagation of cluster-wise similarities via random walks. We first construct a cluster similarity graph with the base clusters treated as graph nodes and the cluster-wise Jaccard coefficient exploited to compute the initial edge weights. Upon the constructed graph, a transition probability matrix is defined, based on which the random walk process is conducted to propagate the graph structural information. Specifically, by investigating the propagating trajectories starting from different nodes, a new cluster-wise similarity matrix can be derived by considering the trajectory relationship. Then, the newly obtained cluster-wise similarity matrix is mapped from the cluster-level to the object-level to achieve an enhanced co-association (ECA) matrix, which is able to simultaneously capture the object-wise co-occurrence relationship as well as the multi-scale cluster-wise relationship in ensembles. Finally, two novel consensus functions are proposed to obtain the consensus clustering result. Extensive experiments on a variety of real-world datasets have demonstrated the effectiveness and efficiency of our approach.

I. INTRODUCTION

The paper targets ensemble-clustering methods that remain largely object-level and direct-connection based, proposing cluster-level random-walk propagation to integrate multi-scale relationships into consensus clustering.

  • Research challenges: Existing ensemble-clustering algorithms often investigate information only at the object level and overlook higher-level ensemble structure.
  • Research challenges: Conventional co-association matrices capture direct object co-occurrence but lack indirect connections between objects whose clusters are related through other clusters.
  • Research challenges: As ensemble size grows, intersection-fragment methods can generate dramatically more fragments and increase computational burden.
  • Research challenges: Over 80 percent of LR intersection fragments have size 1 or 2, while 1.72 percent exceed size 20 but contain 36.45 percent of all objects.
  • Proposed approach: The proposed approach builds a Jaccard-weighted graph of base clusters and uses random walks to derive multi-scale cluster-wise similarities.
  • Proposed approach: The resulting cluster-wise similarities are mapped to an enhanced co-association matrix, followed by object-level and cluster-level consensus functions named ECPCS-HC and ECPCS-MC.
  • Reported outcome: Experiments on multiple datasets report superiority over existing ensemble-clustering approaches.

II. RELATED WORK

Existing ensemble clustering methods combine multiple base clusterings using pair-wise co-occurrence, graph partitioning, or median-partition formulations. However, most methods remain at the object level and primarily model direct connections, leaving higher-level and multi-scale indirect information insufficiently explored.

  • Pair-wise co-occurrence: Pair-wise co-occurrence methods construct co-association matrices from the frequency with which objects share clusters across base clusterings.These methods can then apply hierarchical agglomerative clustering to obtain a consensus result.
  • Graph partitioning: Graph partitioning methods represent clusters, objects, or their similarities as graphs and derive consensus clusters by partitioning those graphs.Examples include hyper-edge representations, bipartite graphs, and object-similarity graphs.
  • Median partition: Median-partition methods formulate ensemble clustering as an optimization problem that seeks a partition maximizing similarity to the base clusterings.Because the median partition problem is NP-hard, approximate methods such as EM have been used.
  • Open challenges: Most existing algorithms investigate ensemble information at the object level rather than exploiting higher-level cluster information.This limits their ability to explore richer structure at different granularities.
  • Open challenges: Many methods model direct connections but neglect multi-scale indirect relationships; one-step neighborhood refinement is insufficient, while SimRank incurs very high computational cost.The cited SimRank-based approach is described as infeasible for large data.
  • Problem formulation: The ensemble objective is to integrate multiple base clusterings into a better consensus clustering result.The ensemble contains base clusterings, each composed of multiple base clusters, with all clusters collectively forming the cluster set.

IV. PROPAGATION OF CLUSTER-WISE SIMILARITIES

The method builds a cluster-level similarity graph from base clusters using Jaccard similarity, then propagates structural information through random walks. Similarities between random-walk trajectories provide a multi-scale cluster-wise representation.

  • Graph construction: The conventional mapping captures base-cluster information at the object or fragment level through co-association matrices.The proposed propagation instead operates on base clusters as graph nodes.
  • Graph construction: Jaccard similarity measures the initial relationship between two clusters using their intersection and union sizes.These similarities define weighted edges in an initial graph whose node set is the ensemble’s cluster set.
  • Random-walk propagation: Random walks transition between neighboring cluster nodes with probabilities determined by edge weights.The resulting transition matrix encodes one-step movement and can be recursively extended to multiple steps.
  • Random-walk propagation: The t-step transition probability p(t)_ij represents the probability of moving from cluster Ci to cluster Cj in t steps.Different step lengths expose graph structure at different scales.
  • Trajectory similarity: Each node’s trajectory records transition distributions across multiple steps, forming a multi-scale neighborhood representation.A new cluster similarity is obtained by comparing the trajectories of two nodes; cosine similarity is used in the paper.

V. ENHANCED CO-ASSOCIATION MATRIX BASED ON SIMILARITY MAPPING

The enhanced co-association matrix maps propagated cluster-wise similarities back to objects. It retains direct co-occurrence while incorporating multi-scale relationships between different clusters.

  • ECA construction: The ECA matrix maps the new cluster-wise similarity matrix from the cluster level to the object level.Its entries lie in [0, 1], and it can be used with co-association-based consensus functions.
  • Conventional representation: Conventional co-association matrices record how often two objects occur in the same cluster across the base clusterings.They treat each cluster as independent and therefore omit relationships between different clusters.
  • ECA construction: The ECA representation is designed to capture object-wise co-occurrence and multi-scale cluster-wise similarity simultaneously.It first uses the propagated cluster-wise matrix to construct an enhanced connectivity matrix for each base clustering.
  • ECA construction: Enhanced connectivity agrees with conventional connectivity when two objects share a cluster, but differs when they belong to different clusters.In the latter case, it incorporates further cluster-wise connections that conventional connectivity omits.
  • ECA construction: The enhanced connectivity matrices are aggregated across the base clusterings to form the ensemble-level ECA matrix.The resulting representation is intended for subsequent consensus functions.

VI. TWO TYPES OF CONSENSUS FUNCTIONS

The framework proposes two consensus functions for producing the final clustering after cluster-wise similarity propagation. One partitions at the object level using hierarchical clustering, while the other uses meta-clustering at the cluster level.

  • Consensus functions: The first consensus function uses hierarchical clustering and performs partitioning at the object level.
  • Consensus functions: The second consensus function uses meta-clustering and performs partitioning at the cluster level.

A. ECPCS-HC

ECPCS-HC treats the ECA matrix as object-wise similarity and applies hierarchical agglomerative clustering through iterative region merging to produce a consensus hierarchy.

  • A. ECPCS-HC: ECPCS-HC uses the ECA matrix as the object-wise similarity matrix for hierarchical agglomerative consensus clustering.The original objects serve as initial regions.
  • A. ECPCS-HC: Each initial region contains exactly one object, and the initial-region similarity matrix is defined before merging begins.
  • A. ECPCS-HC: At each iteration, the two most similar regions are merged and the region set and similarity matrix are updated.
  • A. ECPCS-HC: The updated similarity matrix uses average-link similarity after each region-merging iteration.
  • A. ECPCS-HC: After N −1 iterations, all objects merge into a root region, yielding a dendrogram whose levels represent different clusterings.

B. ECPCS-MC

ECPCS-MC partitions ensemble clusters into meta-clusters using enhanced cluster-wise similarities, then assigns objects by their within-meta-cluster voting scores.

  • B. ECPCS-MC: ECPCS-MC partitions at the cluster level by grouping ensemble clusters into subsets called meta-clusters.It uses the enhanced cluster-wise similarity matrix Z during this partitioning process.
  • B. ECPCS-MC: A cluster similarity graph treats ensemble clusters as nodes and uses Z to define edge weights.
  • B. ECPCS-MC: The normalized cut algorithm partitions the new cluster graph into k meta-clusters.
  • B. ECPCS-MC: An object’s voting score for a meta-cluster is the proportion of clusters in that meta-cluster containing the object.
  • B. ECPCS-MC: Majority voting assigns each object to the meta-cluster where it appears most frequently, producing the consensus clustering.

VII. EXPERIMENTS

The experiments evaluate ECPCS-HC and ECPCS-MC on benchmark datasets against several state-of-the-art ensemble clustering algorithms.

  • VII. EXPERIMENTS: The study conducts experiments on a variety of benchmark datasets.
  • VII. EXPERIMENTS: The evaluated methods are the proposed ECPCS-HC and ECPCS-MC algorithms.
  • VII. EXPERIMENTS: Performance is assessed against several state-of-the-art ensemble clustering algorithms.

A. Datasets and Evaluation Measures

The evaluation uses ten benchmark datasets and measures clustering quality with NMI and ARI, where larger values indicate better results.

  • A. Datasets and Evaluation Measures: The benchmark suite contains ten datasets, including MNIST and nine datasets from the UCI machine learning repository.The listed datasets are BC, CTG, Ecoli, Gisette, LR, LS, MNIST, PD, Wine, and Yeast.
  • A. Datasets and Evaluation Measures: Clustering quality is evaluated with normalized mutual information (NMI) and adjusted Rand index (ARI).
  • A. Datasets and Evaluation Measures: Higher NMI and ARI values indicate better clustering results.

B. Baseline Methods and Experimental Settings

The study compares ECPCS-HC and ECPCS-MC with eight baseline ensemble clustering methods across ten datasets using repeated NMI and ARI evaluations under true-k and best-k criteria. The proposed methods achieve the strongest overall clustering performance across these comparisons.

  • Experimental settings: Eight baseline methods are compared with ECPCS-HC and ECPCS-MC on ten benchmark datasets using average NMI and ARI over 20 runs.The evaluation uses true-k and best-k criteria for the number of clusters.
  • NMI results: ECPCS-HC and ECPCS-MC together achieve the highest NMI in 19 of 20 dataset-and-criterion comparisons, while PTGP leads in only two comparisons.ECPCS-HC ranks first in ten comparisons and ECPCS-MC in nine; the top-three counts are 17 and 20, respectively.
  • ARI results: ECPCS-HC or ECPCS-MC achieves the highest ARI in 16 of 20 comparisons, with each method ranked in the top three in 17 comparisons.The third-best method is ranked in the top three in only nine comparisons.
  • Aggregate results: For true-k, ECPCS-MC and ECPCS-HC obtain average ranks of 1.90 and 2.30, compared with 3.90 for WCT.The proposed methods are also the two best methods by average rank under best-k and show similar advantages for ARI.
  • Aggregate results: ECPCS-HC improves true-k average NMI and ARI over EAC from 53.18 to 57.23 and from 46.13 to 52.60, respectively.The comparison isolates the contribution of the enhanced co-association matrix relative to the conventional co-association matrix.

D. Robustness to Ensemble Size M

The experiments assess performance as ensemble size M varies and examine execution time on the LR dataset. The proposed methods maintain strong clustering quality, while ECPCS-MC is the fastest method in the reported timing experiment.

  • Robustness to ensemble size M: As M increases from 10 to 50, ECPCS-HC achieves the best NMI on BC, Ecoli, LR, Wine, and Yeast, while ECPCS-MC leads on CTG and PD.ARI results similarly favor ECPCS-HC on BC, Ecoli, PD, and Wine and ECPCS-MC on CTG and MNIST.
  • Sensitivity of parameter t: The parameter t controls random-walker propagation steps, and the proposed methods show consistently good NMI across varying t values.Larger t values, such as values above 10, generally produce better clustering results.
  • Robustness to ensemble size M: The figures report average NMI or ARI percentages over 20 runs across ten named datasets as ensemble size M varies.The panels cover BC, CTG, Ecoli, Gisette, LR, LS, MNIST, PD, Wine, and Yeast.
  • Execution time: ECPCS-MC processes the 20,000-object LR dataset in 1.28s, faster than SEC at 1.56s and MCLA at 2.00s.ECPCS-HC has time efficiency comparable to ECC and better than PTGP, WCT, and SRS.

VIII. CONCLUSION

The paper proposes ensemble clustering through random-walk propagation of cluster-wise similarities, mapping the propagated information into an enhanced co-association matrix. Experiments on ten real-world datasets report advantages over state-of-the-art methods in clustering quality and efficiency.

  • Conclusion: The method constructs a weighted graph of base clusters using Jaccard similarity and propagates cluster-wise structural information through random walks.Propagating trajectories yield a new cluster-wise similarity matrix.
  • Conclusion: The propagated cluster similarity is mapped to objects to form an enhanced co-association matrix, followed by ECPCS-HC and ECPCS-MC consensus functions.This combines cluster-level propagation with object-level consensus construction.
  • Conclusion: Experiments on ten real-world datasets show advantages over state-of-the-art methods in both clustering quality and efficiency.The conclusion reports the outcome at the paper level without specifying a single dataset or metric.
Loading 1810.12544v1…