PaperlayerView exact revision on arXiv

Source-linked AI summary

Locally Weighted Ensemble Clustering

Dong Huang, Chang-Dong Wang, Jian-Huang Lai

arXiv:1605.05011v3cs.LG

TL;DR

Existing ensemble clustering methods often treat base clusterings equally or assign global weights, neglecting differing cluster reliability and local diversity. The paper estimates cluster uncertainty from ensemble labels using entropy, derives an ensemble-driven validity index and locally weighted co-association matrix, and proposes two consensus functions. Experiments on real-world datasets report superiority over state-of-the-art methods in clustering quality and efficiency.

  • Problem

    Existing methods often ignore differing cluster reliability and local diversity, while some cluster-reliability methods require data features or distributional assumptions.

  • Method

    The approach estimates cluster uncertainty from ensemble labels using entropy, evaluates reliability with ECI, constructs a locally weighted co-association matrix, and uses LWEA and LWGP.

  • Results

    Experiments on real-world datasets report superiority over state-of-the-art approaches in clustering quality and efficiency.

  • Takeaways & Limitations

    Local cluster reliability and ensemble diversity are incorporated into consensus clustering without requiring original data features or distributional assumptions.

Abstract

from arXiv · show

Due to its ability to combine multiple base clusterings into a probably better and more robust clustering, the ensemble clustering technique has been attracting increasing attention in recent years. Despite the significant success, one limitation to most of the existing ensemble clustering methods is that they generally treat all base clusterings equally regardless of their reliability, which makes them vulnerable to low-quality base clusterings. Although some efforts have been made to (globally) evaluate and weight the base clusterings, yet these methods tend to view each base clustering as an individual and neglect the local diversity of clusters inside the same base clustering. It remains an open problem how to evaluate the reliability of clusters and exploit the local diversity in the ensemble to enhance the consensus performance, especially in the case when there is no access to data features or specific assumptions on data distribution. To address this, in this paper, we propose a novel ensemble clustering approach based on ensemble-driven cluster uncertainty estimation and local weighting strategy. In particular, the uncertainty of each cluster is estimated by considering the cluster labels in the entire ensemble via an entropic criterion. A novel ensemble-driven cluster validity measure is introduced, and a locally weighted co-association matrix is presented to serve as a summary for the ensemble of diverse clusters. With the local diversity in ensembles exploited, two novel consensus functions are further proposed. Extensive experiments on a variety of real-world datasets demonstrate the superiority of the proposed approach over the state-of-the-art.

I. INTRODUCTION

Ensemble clustering combines diverse base clusterings, but existing methods often ignore differences in cluster reliability and local diversity. This paper proposes ensemble-driven cluster uncertainty estimation and local weighting, yielding two consensus functions evaluated favorably on real-world datasets.

  • Motivation: Different algorithms, initializations, and parameters can produce different clusterings, making method and parameter selection difficult without prior knowledge.
  • Limitations of Existing Methods: Existing weighted methods assign global weights to base clusterings, assuming all clusters within one clustering have equal reliability despite local diversity.
  • Proposed Approach: The proposed approach estimates cluster uncertainty from cluster-label distributions across the ensemble using entropy, without data features or distributional assumptions.
  • Proposed Approach: An ensemble-driven cluster validity measure evaluates and weights individual clusters, providing cluster-level reliability for local weighting.
  • Proposed Approach: Two consensus functions, locally weighted evidence accumulation and locally weighted graph partitioning, incorporate cluster diversity and local weighting.
  • Results: Extensive experiments on real-world datasets report superiority over state-of-the-art approaches in clustering quality and efficiency.

III. PRELIMINARIES

The preliminaries define entropy and joint entropy as uncertainty measures for discrete random variables. They also state the additivity of joint entropy for independent variables.

  • Entropy: Entropy measures the uncertainty associated with a discrete random variable.
  • Joint Entropy: Joint entropy measures the uncertainty associated with a set of random variables, with p(x, y) denoting the joint probability.
  • Entropy Properties: If X and Y are independent, their joint entropy equals H(X)+H(Y).
  • Entropy Properties: For n independent variables, joint entropy equals the sum H(X1) + ··· + H(Xn).

B. Formulation of the Ensemble Clustering Problem

The paper formulates ensemble clustering as combining multiple base partitions into a consensus clustering without access to original data features. Each base clustering partitions the dataset into nonoverlapping clusters, and the ensemble contains all such clusters.

  • B. Formulation of the Ensemble Clustering Problem: The ensemble Π consists of M partitions of dataset O, with each partition treated as a base clustering.Each base clustering contains a certain number of clusters.
  • B. Formulation of the Ensemble Clustering Problem: Each cluster is a set of data objects, and clusters within a base clustering jointly cover the entire dataset without overlap.
  • B. Formulation of the Ensemble Clustering Problem: The ensemble’s clusters can be represented collectively as C, containing nc clusters across all M base clusterings.The total is nc = n1+· · ·+nM.
  • B. Formulation of the Ensemble Clustering Problem: The goal is to combine multiple base clusterings to obtain a probably better and more robust clustering.
  • B. Formulation of the Ensemble Clustering Problem: The feature-free formulation takes only the clustering ensemble Π as input and produces a consensus clustering π∗.A separate formulation can also use original data features, but this paper adopts the feature-free setting.
  • B. Formulation of the Ensemble Clustering Problem: The proposed approach is based on ensemble-driven cluster uncertainty estimation and a local weighting strategy.

A. Measuring Cluster Uncertainty in Ensembles

Cluster uncertainty is estimated from how the objects in each cluster are distributed across the ensemble’s base clusterings. Agreement yields low uncertainty, while dispersion across clusters yields higher uncertainty.

  • A. Measuring Cluster Uncertainty in Ensembles: Cluster uncertainty with respect to a base clustering is computed from how the objects in a cluster are distributed among that base clustering’s clusters.
  • A. Measuring Cluster Uncertainty in Ensembles: The entropy-based uncertainty uses intersection proportions between cluster Ci and clusters Cm_j, normalized by |Ci|.
  • A. Measuring Cluster Uncertainty in Ensembles: Uncertainty is zero when all objects in Ci belong to the same cluster, and typically increases as they occupy more different clusters.
  • A. Measuring Cluster Uncertainty in Ensembles: Under the stated independence assumption for base clusterings, ensemble-level uncertainty sums uncertainty across the M base clusterings.
  • A. Measuring Cluster Uncertainty in Ensembles: For the 16-object example with three three-cluster base clusterings, C1_1 has uncertainty 2.56 because its objects are distributed across other clusterings.
  • A. Measuring Cluster Uncertainty in Ensembles: C1_2 has zero uncertainty because all three base clusterings place its objects together, while C1_1 is the most uncertain cluster and C1_2 and C3_3 are the most stable.

B. Ensemble-Driven Cluster Validity

The ensemble-driven cluster index ECI converts ensemble-level uncertainty into a cluster reliability measure. Lower uncertainty produces higher ECI, while θ controls how strongly uncertainty affects the index.

  • B. Ensemble-Driven Cluster Validity: The ensemble-driven cluster index ECI measures each cluster’s reliability using its uncertainty with respect to the entire ensemble.
  • B. Ensemble-Driven Cluster Validity: The parameter θ adjusts the influence of cluster uncertainty on ECI.
  • B. Ensemble-Driven Cluster Validity: ECI values lie in (0, 1], and smaller cluster uncertainty produces a greater ECI value.
  • B. Ensemble-Driven Cluster Validity: When uncertainty is zero, ECI reaches 1; as uncertainty approaches infinity, ECI approaches zero.
  • B. Ensemble-Driven Cluster Validity: For θ < 0.1, ECI decreases dramatically as uncertainty increases, whereas larger θ values narrow differences between high- and low-uncertainty clusters.The paper empirically suggests setting θ in [0.2, 1].

C. Refining Co-association Matrix by Local Weighting

The paper refines the classical co-association matrix with local cluster weighting, preserving cluster-level reliability and diversity rather than treating all clusters equally.

  • The classical co-association matrix counts how often object pairs co-occur in the same cluster across base clusterings.It does not evaluate or weight the reliability of individual ensemble members or clusters.
  • Unlike the classical matrix, LWCA reflects both object co-occurrence frequency and the reliability of the clusters containing those objects.
  • Existing weighted co-association methods weight base clusterings globally but neglect cluster-wise diversity within each base clustering.
  • The locally weighted co-association matrix applies local weighting based on an ensemble-driven cluster validity measure.
  • Higher-ECI clusters receive greater influence because objects co-occurring in more reliable clusters are considered more likely to share a true cluster.

D. Consensus Functions

The proposed consensus functions use the locally weighted co-association matrix as the basis for two complementary clustering procedures: hierarchical evidence accumulation and graph partitioning.

  • The paper proposes two consensus functions, locally weighted evidence accumulation (LWEA) and locally weighted graph partitioning (LWGP).
  • Locally Weighted Evidence Accumulation (LWEA): LWEA uses hierarchical agglomerative clustering, which takes the LWCA matrix as its initial similarity matrix.
  • Locally Weighted Evidence Accumulation (LWEA): LWEA initializes each data object as a separate region before iterative similarity-based merging.
  • Locally Weighted Evidence Accumulation (LWEA): At each iteration, the two most similar regions merge into a larger region, updating the region set and similarity matrix.
  • Locally Weighted Evidence Accumulation (LWEA): The iterative merging process constructs a dendrogram, from which the final clustering is obtained by specifying the desired number of clusters.

2) Locally Weighted Graph Partitioning (LWGP):

LWGP constructs a locally weighted bipartite graph linking objects to their containing clusters, then partitions the graph to produce the consensus clustering.

  • LWGP is a consensus function based on bipartite graph formulation and partitioning.
  • The locally weighted bipartite graph represents both data objects and clusters as graph nodes.
  • A link connects an object to its containing cluster, and its weight is determined by the cluster’s ECI reliability value.
  • The LWBG therefore captures object–cluster membership together with local cluster reliability in the ensemble.
  • Tcut partitions the graph into disjoint node sets, and objects in the same segment form a final cluster.

V. EXPERIMENTS

Experiments evaluate LWEA and LWGP on diverse real-world datasets using NMI and ARI, with repeated random ensemble construction to compare consensus quality.

  • Datasets and Evaluation Methods: Experiments compare the proposed methods with state-of-the-art ensemble clustering methods on fifteen real-world datasets.
  • Datasets and Evaluation Methods: NMI and ARI are used to evaluate clustering quality, with larger values indicating better results.
  • Datasets and Evaluation Methods: Candidate clusterings are generated by k-means with k randomly selected from [2, N], and ensembles typically contain M = 10 randomly chosen base clusterings.
  • Parameter Evaluation: Tables III and IV report average NMI scores for LWEA and LWGP across varying θ values, supporting consistent performance and an empirical setting of θ = 0.4.
  • Consensus Performance: Figure 5 reports average NMI performances and variances over 100 runs for the proposed methods and base clusterings.
  • Statistical Evaluation: Table V reports average NMI performances over 100 runs, while Table VI summarizes statistical comparisons using t-tests with p < 0.05.

B. Choices of Parameter θ

The proposed methods remain consistent across parameter θ values, with moderate settings recommended and θ = 0.4 used thereafter.

  • Parameter influence: Smaller θ increases the influence of cluster uncertainty on the LWEA and LWGP consensus process through ECI.The parameter controls uncertainty’s influence in both methods.
  • Empirical evaluation: Twenty-run evaluations across benchmark datasets found consistent LWEA and LWGP clustering performance across different θ values.Average NMI scores were reported for varying θ values in Tables III and IV.
  • Parameter selection: Moderate θ values, such as the interval [0.2, 1], are empirically recommended for LWEA and LWGP.The authors use θ = 0.4 in all subsequent benchmark experiments.
  • Parameter selection: The subsequent benchmark experiments use θ = 0.4 for both LWEA and LWGP.This setting follows the empirical recommendation of moderate parameter values.

C. Comparison against Base Clusterings

Across benchmark comparisons, LWEA and LWGP generally outperform base clusterings and competing ensemble methods in NMI and ARI, with statistical testing used to assess differences.

  • Against base clusterings: LWEA and LWGP significantly improve over base clusterings, with especially large advantages on IS, LS, MF, MNIST, ODR, PD, Semeion, texture, and USPS.The comparison averages results and variances over 100 randomly constructed ensembles.
  • Against ensemble methods: LWEA and LWGP achieve the best NMI scores on seven datasets and nearly the best scores on four others under both best-k and true-k settings.The results are reported against eleven ensemble clustering methods.
  • Against ensemble methods: LWEA and LWGP achieve the best ARI scores on six datasets under both best-k and true-k settings and nearly the best scores on six additional datasets.Table VII reports average ARI performances over 100 runs.
  • Statistical testing: A t-test with p < 0.05 classifies each comparison as significantly better, comparable, or significantly worse.The analysis covers 30 comparisons across fifteen datasets and two k settings.

E. Robustness to Ensemble Sizes M

LWEA and LWGP maintain consistent consensus performance as ensemble size varies, while providing competitive execution efficiency across data sizes.

  • Experimental design: The ensemble-size experiments randomly select M base clusterings and average results over 20 runs for each M.Both NMI and ARI are evaluated in Figures 6 and 7.
  • Performance robustness: Across thirteen datasets, LWEA and LWGP significantly outperform TOME in NMI as ensemble size varies, except on MF and PD.The methods show overall the most consistent and robust performance in the NMI analysis.
  • Execution efficiency: LWEA requires 75.20 seconds on the full LR dataset, comparable to GP-MGLA and faster than CSPA, WCT, SRS, and TOME.The full dataset contains 20,000 objects.
  • Execution efficiency: LWGP takes 8.74 seconds on the full LR dataset, making it the second-fastest method behind MCLA at 5.31 seconds.LWGP is slower than MCLA but faster than the other eleven tested methods.
  • Overall finding: The authors summarize LWEA and LWGP as delivering better, more consistent consensus performance with competitive efficiency than baseline methods.The conclusion draws on Tables V–VIII and Figures 6–8.
Loading 1605.05011v3…