Clustering pair-wise dissimilarity data into partially ordered sets

Jinze Liu, Qi Zhang, Wei Wang, Leonard McMillan, Jan F. PrinsKDD 2006 · DOI

TL;DR

This paper introduces "PoCluster," a novel clustering algorithm that generates partially ordered sets (posets) from pairwise dissimilarity data. Unlike traditional methods that produce disjoint hierarchies, PoCluster allows for overlapping clusters and multiple parent relationships, better reflecting complex real-world ontologies like the Gene Ontology.

What Problem Does This Paper Address?

Many real-world classification systems, such as biological ontologies (e.g., Gene Ontology), are not simple trees but rather directed acyclic graphs (DAGs) where categories can overlap and have multiple parent categories. Traditional clustering algorithms, which typically produce disjoint partitions or strict hierarchies, struggle to accurately represent these complex structures. This paper addresses the challenge of automatically constructing these more flexible, ontology-like categorizations from pairwise dissimilarity matrices, which are common inputs for clustering. The core problem is that existing methods often lose information from the dissimilarity matrix, failing to capture the nuanced relationships present in complex ontologies.

Methods

The paper proposes PoCluster, an algorithm that models ontologies as partially ordered sets (posets) where the ordering is based on the subset relation. Instead of generating disjoint clusters, PoCluster aims to create a collection of "clique clusters." A clique cluster is defined as a maximal clique in a graph derived from the dissimilarity matrix, with its "diameter" representing the maximum dissimilarity within that cluster.

The construction process involves:

  1. Graph Representation: Mapping the dissimilarity matrix to a weighted undirected graph where nodes are objects and edge weights are dissimilarities.
  2. Varying Thresholds: Iteratively considering subgraphs formed by edges with dissimilarities less than or equal to a specific threshold.
  3. Clique Detection: Identifying maximal cliques within these subgraphs. These cliques represent potential categories.
  4. PoCluster Formation: Collecting all such clique clusters across all possible diameter thresholds. This collection forms the PoCluster, which is a poset where a cluster is a subset of another if its diameter is strictly smaller.

The paper also introduces an Optimized Incremental Algorithm to efficiently construct PoClusters, leveraging previously found cliques to speed up the process when new edges are added to the graph.

Datasets

The primary dataset used for evaluation is a subset of gene function categories from the Gene Ontology (GO). Specifically, they used data for 799 genes related to the yeast cell cycle. They considered three GO files: Biological Process (BP), Cellular Component (CC), and Molecular Function (MF). They also generated dissimilarity matrices from these GO categories using two similarity measures: Resnik and Leacock & Chodorow (LC).

Key Insights and Ideas

  • Ontologies are more than trees: The paper highlights that real-world classification systems often exhibit complex relationships (overlaps, multiple parents) that simple hierarchical or pyramidal clustering cannot capture.
  • Dissimilarity matrices hold rich information: Traditional clustering methods often discard information from dissimilarity matrices. PoCluster aims to preserve this information by considering all possible clique clusters across varying dissimilarity thresholds.
  • Clique clusters as building blocks: The concept of a "clique cluster" with a defined diameter provides a natural way to define categories that are internally cohesive.
  • PoCluster as a generalization: PoCluster generalizes hierarchical and pyramidal clustering by allowing for non-disjoint clusters and multiple parent relationships, making it more suitable for representing complex ontologies.
  • Resnik similarity is effective for GO: The experiments suggest that the Resnik similarity measure is more effective than the Leacock & Chodorow measure for deriving dissimilarity matrices that lead to better reconstruction of GO structures.

Key Results

  • Superior Reconstruction of GO: PoCluster significantly outperformed hierarchical and pyramidal clustering in reconstructing the structure of Gene Ontology files, achieving higher "match scores" (indicating better approximation of the original poset).
  • High Accuracy and Recovery: PoCluster demonstrated a high recovery rate (percentage of GO categories recovered) and accuracy (percentage of discovered clusters that are actual matches in GO), with over 96% of discovered clusters being actual matches.
  • Efficiency: The optimized incremental algorithm for PoCluster construction is presented as an efficient approach for handling large datasets.
  • Comparison of Similarity Measures: The Resnik similarity measure yielded better results than the LC measure when used to generate dissimilarity matrices for GO data.

Limitations and Future Work

  • Computational Complexity: The paper acknowledges that finding cliques is an NP-hard problem, suggesting that exact PoCluster reconstruction might be intractable for very large datasets.
  • Approximation Algorithms: The authors suggest investigating approximation algorithms to make PoCluster scalable to larger datasets.
  • Valid PoCluster Identification: A theoretical question raised is how to identify whether an arbitrary poset can be a valid PoCluster, as not all posets are valid PoClusters (illustrated by an example in Figure 5).
  • Theoretical Properties: Further theoretical investigation into the relationship between PoClusters, dissimilarity matrices, and existing matrix types (like Robinson or ultrametric) is proposed.

Summary updated

BibTeX
@inproceedings{liu2006clustering,
  author = {Jinze Liu and Qi Zhang and Wei Wang and Leonard McMillan and Jan F. Prins},
  title = {{Clustering pair-wise dissimilarity data into partially ordered sets}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2006},
  doi = {10.1145/1150402.1150480},
}
Figure