Parameter-Free Hierarchical Co-clustering by n-Ary Splits

Dino Ienco, Ruggero G. Pensa, Rosa MeoECML/PKDD 2009 · DOI

TL;DR

This paper introduces HiCC, a novel hierarchical co-clustering algorithm that simultaneously builds coupled hierarchies for both data objects and features. Unlike existing methods, HiCC is parameter-free, automatically determines the number of clusters, and uses n-ary splits for more compact and interpretable hierarchies, outperforming state-of-the-art methods on several high-dimensional datasets.

What Problem Does This Paper Address?

Clustering high-dimensional data presents a significant challenge. Traditional clustering methods often struggle to identify meaningful similarities due to the "curse of dimensionality." While co-clustering approaches, which simultaneously cluster objects and features, offer a promising solution, existing methods typically produce flat, non-hierarchical clusterings and require the user to pre-specify the number of clusters. This lack of hierarchy limits interpretability, as the relationships between clusters are not explicitly represented. Furthermore, the need to manually set the number of clusters adds a cumbersome pre-processing step. This paper aims to address these limitations by proposing a hierarchical co-clustering method that is parameter-free and provides interpretable cluster structures.

Methods

The core of the proposed method, HiCC (Hierarchical Co-Clustering by n-ary split), is built upon the TCoClust algorithm, which optimizes the Goodman-Kruskal $\tau$ coefficient to find optimal flat co-clusterings. HiCC extends this by iteratively building hierarchical structures.

The algorithm operates in a divisive manner:

  1. Initialization: It starts by computing the first level of both object and feature hierarchies using TCoClust.
  2. Hierarchical Growth: For each existing cluster at a given level, HiCC performs an "n-ary split" (where 'n' is automatically determined) to create new clusters for the next level. This splitting process is applied alternately to row (object) clusters and column (feature) clusters.
  3. Optimization: During the splitting process, the algorithm uses a local search strategy (similar to TCoClust's optimizeRowCluster and optimizeColumnCluster functions) to optimize the Goodman-Kruskal $\tau$ coefficient, ensuring that the newly formed clusters maintain or improve the co-clustering quality.
  4. Termination: The hierarchical construction continues until a termination condition is met, typically when all leaf clusters contain only a single element.

A key novelty is the use of "n-ary splits" instead of binary splits, which leads to more compact and potentially more interpretable hierarchies. The algorithm is also parameter-free, meaning it doesn't require the user to specify the number of clusters beforehand.

Datasets

The paper evaluates HiCC on several real-world, high-dimensional, multi-class datasets commonly used in text categorization research:

  • OHSUMED: Two samples, oh0 and oh15, derived from a MEDLINE subset.
  • TREC: Two samples, tr11 and tr21, from the Text Retrieval Conference archive.
  • Reuters-21578: Two samples, re0 and re1, a widely used benchmark for text categorization.

These datasets are characterized by a large number of features and classes, making them suitable for testing the robustness of co-clustering algorithms. No new benchmarks were introduced; instead, existing, well-established datasets were used.

Key Insights and Ideas

  • Hierarchical Co-clustering is Inherently More Informative: The paper strongly advocates for hierarchical structures in co-clustering, arguing that they provide deeper insights into the relationships between objects and features than flat clusterings. The hierarchy itself becomes a valuable tool for understanding data organization.
  • Parameter-Free is a Game-Changer: The absence of user-defined parameters (like the number of clusters) significantly simplifies the application of co-clustering, making it more accessible and less prone to suboptimal choices during pre-processing.
  • N-ary Splits Enhance Compactness and Interpretability: Moving beyond binary splits allows for more direct representation of data structure, leading to "compact hierarchies" that are easier for humans to grasp and analyze.
  • Goodman-Kruskal $\tau$ as a Robust Association Measure: The paper leverages the Goodman-Kruskal $\tau$ coefficient as a key objective function, highlighting its desirable properties for measuring association between clusterings, including invariance to permutations and an intuitive interpretation as a proportional reduction in prediction error.

Key Results

  • Superior Performance: HiCC consistently outperforms the state-of-the-art Information-Theoretic Co-Clustering (ITCC) algorithm across multiple datasets and evaluation metrics (NMI, Purity, Adjusted Rand Index).
  • High-Quality Hierarchies: The generated hierarchies were validated using external measures, showing competitive or superior results compared to ITCC, especially at higher levels of the hierarchy.
  • Stability: The algorithm demonstrated good stability, with low standard deviations in performance metrics across multiple runs.
  • Efficiency: While not the primary focus, the paper notes that HiCC's constrained optimization approach can be faster than ITCC's global optimization, which restarts from scratch for each desired number of co-clusters.
  • Compact Hierarchies: The n-ary splits resulted in shorter hierarchies compared to what might be achieved with binary splits, aiding in data exploration.

Limitations and Future Work

  • Computational Cost: While HiCC is efficient, the paper acknowledges that for very large datasets, the computational cost can still be significant (e.g., ~4 hours for the largest dataset rel).
  • Local Search Limitations: The paper mentions that local search strategies can sometimes lead to temporary degradation of one objective function while improving another, though it asserts that compensation effects stabilize the results over iterations.
  • Future Work: The authors suggest exploring more sophisticated splitting strategies beyond random splitting and investigating adaptive iteration counts for optimization. They also imply that the framework could be extended to other objective functions beyond Goodman-Kruskal $\tau$.

Summary updated

BibTeX
@inproceedings{ienco2009parameter,
  author = {Dino Ienco and Ruggero G. Pensa and Rosa Meo},
  title = {{Parameter-Free Hierarchical Co-clustering by n-Ary Splits}},
  booktitle = {ECML/PKDD},
  year = {2009},
  doi = {10.1007/978-3-642-04180-8\_55},
}
Figure