Ensemble clustering

Overview

Ensemble clustering builds several base clusterings and combines them into one. The diversity comes from randomness: each base clustering sees a different random slice of the data, and a consensus step merges the results 2203.11572 §3.2 2203.11572 §3.5.

One card on wikillm lists this slug so far: FastMICE, which targets multi-view data, where each sample is described by several feature sets called views 2203.11572 §1. Everything below is taken from that paper and its reported results. This page therefore describes one method, not the field.

The paper's pipeline has four stages 2203.11572 §3:

• Diversity source. Random view groups, random feature columns, random anchors, random neighbour sets and a random cluster count per base clustering 2203.11572 §3.2 2203.11572 §3.3 2203.11572 §3.4.
• Base clusterer. Each group builds one anchor-based bipartite graph over the samples, which is partitioned with the transfer cut 2203.11572 §3.3 2203.11572 §3.4.
• Consensus. All base labels are stacked into one binary membership matrix, with one 1 per base clustering per sample, and partitioned again 2203.11572 §3.5.

The paper presents early fusion (all views in one group) and late fusion (one view per group) as the two extremes of the grouping step 2203.11572 §3.2.

Variants

Random view groups with anchor graphs (FastMICE)

Card: Fast Multi-view Clustering via Ensembles.

• Ensemble size. M = 20 view groups, each giving one base clustering 2203.11572 §4.2. The authors report that a larger M helps 2203.11572 §4.4 fig. 3.
• Anchor budget. Each group shares a total of about p anchors (p = min{1000, N} in the experiments) and about K nearest anchors per sample (K = 5). Each view in a group gets an equal share, rounded up 2203.11572 §3.3 2203.11572 §4.2. The authors report that a moderate K, in the range [4, 8], works best on most datasets 2203.11572 §4.6 fig. 5.
• Base partition. The cluster count of each base clustering is drawn between k and 2k 2203.11572 §4.2. The transfer cut solves a small eigenproblem on the anchors, lifts the result to the samples, and then runs k-means 2203.11572 §3.4.
• Cost. The text gives a near-linear cost in N under the assumption that the anchor count is much smaller than N and the other sizes are smaller still. It drops the cubic terms in the anchor count and in the total number of base clusters 2203.11572 §3.6.1.
• Reported results. Average NMI rank 1.23 over 22 datasets, where the next best method scores 4.41. FastMICE has the highest NMI on 19 of 22 2203.11572 tab. 3 2203.11572 §4.3. On the YTF-200 dataset (286,006 samples) it runs in 263.81 s, against 3,184.79 s for the fastest other method that finished there 2203.11572 tab. 7. On YTF-400 (398,191 samples) it is the only method that completes 2203.11572 tab. 7.
• Tuning. The method uses the same M, p and K on every dataset. The user still supplies k, and picks the distance (Euclidean, or cosine for text) 2203.11572 §4.2. Baselines were tuned with a grid of 10⁻⁵ to 10⁵ per hyperparameter, on a random subset when N exceeds 10,000 2203.11572 §4.2.

When to use which

Sensitivity results are only described in the text, not given as numbers 2203.11572 §4.4 2203.11572 §4.5 2203.11572 §4.6. Do not read values from the sensitivity figures into your settings without checking the source.

Implementation sketch

Language-agnostic pseudocode of the FastMICE core. The paper has no algorithm box, so this is our summary of its text 2203.11572 §3.

# Ensemble clustering, FastMICE-style  [arxiv:2203.11572 §3]
# Input:  views (V matrices, N rows each), k; M, p, K
# Output: labels (N,) in 0..k-1

def ensemble_cluster(views, k, M=20, p=1000, K=5):
    base = []
    for m in range(M):
        # Random non-empty group of views  [arxiv:2203.11572 §3.2]
        group = random_subset(views)
        # The group shares p and K across its members  [arxiv:2203.11572 §3.3]
        p_bar = ceil(p / len(group))
        K_bar = ceil(K / len(group))
        blocks = []
        for v in group:
            # Keep a random share of the columns, here 20 to 80 percent  [§4.2]
            X = random_columns(views[v], random_ratio(0.2, 0.8))
            # p_bar representatives of X  [arxiv:2203.11572 §3.3]
            anchors = pick_representatives(X, p_bar)
            # Gaussian weights to the K_bar nearest anchors, zero elsewhere  [§3.3]
            blocks.append(sparse_gaussian_graph(X, anchors, K_bar))
        # Unit-norm rows, concatenated across the group  [arxiv:2203.11572 §3.3]
        B_m = concat_rows_normalised(blocks)
        # Random cluster count between k and 2k  [arxiv:2203.11572 §4.2]
        base.append(transfer_cut(B_m, random_int(k, 2 * k)))
    # Stack the base labels and partition the union graph  [arxiv:2203.11572 §3.5]
    return transfer_cut(one_hot_union(base), k)

Where transfer_cut(B, k) solves an eigenproblem on the anchor graph, lifts the eigenvectors back to the samples and runs k-means on them 2203.11572 §3.4. Where implementations differ: the scaling of the lifted embedding and the row normalisation before k-means are described under Contradictions.

Contradictions

No cross-paper disagreement: only one card lists this slug. Within the paper, the text and the official code differ, and some reported numbers are not explained.

• Embedding scale and normalisation. The text divides the lifted embedding by (1 − λ) 2203.11572 §3.4 2203.11572 eq. 11. The official code does not apply that division, and it normalises each row to unit length before k-means with cosine distance 2203.11572 §3.4. The paper does not mention row normalisation. Our card notes that the effect on partitions has not been measured.
• Gaussian bandwidth. The paper gives no bandwidth 2203.11572 §3.3. The code uses the mean distance to the K̄ nearest anchors for Euclidean data, and 1 − distance for cosine data 2203.11572 §3.3.
• Random draws. The text says "randomly chosen" for view members, feature ratios and cluster counts, and does not state the distributions 2203.11572 §3.2 2203.11572 §3.3 2203.11572 §3.4. The code draws them uniformly.
• Reproducibility. The paper states no seed. The official code reseeds from the clock before each random step, so reruns differ 2203.11572 §4.2.
• Baseline variance. The captions say each value is an average over 20 runs, yet many baseline cells show a standard deviation of exactly 0.00. The paper does not explain this 2203.11572 tab. 3.
• Dataset count. Parts of the text say 20 datasets, while the tables and dataset list give 22 2203.11572 §4.3 2203.11572 tab. 2.

Papers

• Fast Multi-view Clustering via Ensembles: Towards Scalability, Superiority, and Simplicity: FastMICE, which fuses random view groups, each turned into an anchor-based bipartite graph, through a consensus step. Author-reported results only.