Efficient Consensus Functions

In this section, we introduce three efficient heuristics to solve the cluster ensemble problem. All algorithms approach the problem by first transforming the set of clusterings into a hypergraph representation.

Cluster-based Similarity Partitioning Algorithm (CSPA).

A clustering signifies a relationship between objects in the same cluster and can thus be used to establish a measure of pairwise similarity. This induced similarity measure is then used to recluster the objects, yielding a combined clustering.

HyperGraph Partitioning Algorithm (HGPA).

In this algorithm, we approximate the maximum mutual information objective with a constrained minimum cut objective. Essentially, the cluster ensemble problem is posed as a partitioning problem of a suitably defined hypergraph where hyperedges represent clusters.

Meta-CLustering Algorithm (MCLA).

Here, the objective of integration is viewed as a cluster correspondence problem. Essentially, groups of clusters (meta-clusters) have to be identified and consolidated.

The following four subsections describe the common hypergraph representation, CSPA, HGPA, and MCLA. Section 5.3.5 discusses differences in the algorithms and evaluates their performance in a controlled experiment.