PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Hierarchical Clustering

Maria-Florina Balcan, Yingyu Liang, Pramod Gupta

arXiv:1401.0247v2cs.LGcs.DS

TL;DR

Classic agglomerative clustering is widely used but lacks robustness to noise, motivating a more reliable linkage-based approach. The paper proposes and analyzes a robust bottom-up algorithm that succeeds under natural clustering properties, extends to small-sample inductive settings, and performs better than other hierarchical methods in noisy experiments.

  • Problem

    Classic agglomerative methods are widely used but can fail when similarity deviates slightly from strict separation, motivating robust linkage-based clustering under natural conditions.

  • Method

    The paper proposes a robust bottom-up agglomerative algorithm and extends it to construct a hierarchy from a small random sample of the full data set.

  • Results

    The algorithm achieves accurate hierarchical clustering under good neighborhood properties and consistently performs better than other hierarchical algorithms while being more robust to noise.

  • Takeaways & Limitations

    The method provides formal robustness guarantees and a potentially faster inductive alternative when evaluating the complete data is resource intensive.

  • Takeaways & Limitations

    Ward’s minimum variance method might fail under strict separation when clusters are unbalanced, motivating care in comparing linkage procedures.

Abstract

from arXiv · show

One of the most widely used techniques for data clustering is agglomerative clustering. Such algorithms have been long used across many different fields ranging from computational biology to social sciences to computer vision in part because their output is easy to interpret. Unfortunately, it is well known, however, that many of the classic agglomerative clustering algorithms are not robust to noise. In this paper we propose and analyze a new robust algorithm for bottom-up agglomerative clustering. We show that our algorithm can be used to cluster accurately in cases where the data satisfies a number of natural properties and where the traditional agglomerative algorithms fail. We also show how to adapt our algorithm to the inductive setting where our given data is only a small random sample of the entire data set. Experimental evaluations on synthetic and real world data sets show that our algorithm achieves better performance than other hierarchical algorithms in the presence of noise.

1 Introduction

Hierarchical clustering is widely used because its tree-structured output is interpretable, but classic agglomerative methods are vulnerable to noise. The paper develops a robust bottom-up algorithm with guarantees under natural neighborhood conditions, an inductive extension, and favorable empirical results.

  • 1 Introduction: Classic agglomerative clustering is widely used for interpretable output but is not robust to noise.Hierarchical clustering represents partitions at multiple granularities, while agglomerative methods progressively merge clusters.
  • 1.1 Our Results: The proposed algorithm produces hierarchies whose prunings recover target clusterings under good neighborhood properties, including settings with bad and boundary points.After removing a small number of potentially malicious bad points, most neighbors of good points come from their target cluster; a generalized property permits a good fraction of boundary points.
  • 1.1 Our Results: The paper notes that Ward’s minimum variance method might fail under strict separation when clusters are unbalanced.A concrete example is provided in Appendix C.
  • 1.1 Our Results: The algorithm extends to the inductive setting, using a small random sample whose required size is independent of the full data-set size.The sample-generated hierarchy implicitly represents a hierarchy over the entire data set.
  • 1.1 Our Results: Experiments on synthetic and real-world data show consistently better performance than other hierarchical algorithms and greater robustness to noise.The inductive version is also presented as a faster alternative when evaluating the complete data is resource intensive.

2 Definitions. A Formal Setup

The paper formalizes hierarchical clustering as finding a tree with a near-target pruning, then develops robust linkage methods for noisy similarity structures where standard linkages can fail.

  • 2 Definitions. A Formal Setup: The similarity function is assumed symmetric and accessed only through pairwise values K(x, x′) in [−1, 1].
  • 2 Definitions. A Formal Setup: The goal is a hierarchy containing a pruning whose clustering error is at most ϵ relative to the unknown target.The hierarchy is a tree over subsets, with each node’s children partitioning that node.
  • 2 Definitions. A Formal Setup: Strict separation may admit multiple substantially different valid clusterings, motivating success defined by whether the target appears as a pruning rather than a fixed partition.The paper’s Figure 1 gives two distinct clusterings satisfying strict separation.
  • 2.2 Standard Linkage Based Algorithms Are Not Robust: Standard single, average, and complete linkage work under strict separation but can fail after slight similarity deviations, motivating more robust linkage algorithms.
  • 2.1 Properties of the Similarity Function: The α-good neighborhood property requires that, for every point, all but αn of its n_C(x) nearest neighbors belong to its target cluster.
  • 2.1 Properties of the Similarity Function: The (α, ν)-good neighborhood property applies this local-neighborhood condition after removing up to a ν fraction of points and generalizes both strict separation and α-good neighborhoods.The ν-strict separation and α-good neighborhood properties correspond to the special cases (0, ν) and (α, 0).
  • 2.1 Properties of the Similarity Function: The new robust linkage algorithm offers a simpler, faster route than an earlier expensive method under ν-strict separation and the more general (α, ν)-good neighborhood property.The earlier method generates Ω(n^2) candidate clusters and repeatedly performs pairwise tests, with a large unspecified polynomial running time.
  • 2.1 Properties of the Similarity Function: The algorithm also succeeds under weak good neighborhood, where only local neighborhoods of a good fraction of points need favorable structure.

3 Robust Median Neighborhood Linkage

Robust Median Neighborhood Linkage builds graphs from shared nearest-neighbor structure and median tests, then merges connected blobs as the threshold increases. Under the good neighborhood property, it produces a near-correct hierarchical clustering with formal robustness and runtime guarantees.

  • The algorithm repeatedly builds shared-neighbor graph F_t, blob graph H_t, merges sufficiently supported connected components, and increases t until one blob remains.F_t uses common t-nearest-neighbor counts; H_t uses common-neighbor thresholds for singleton blobs and a median test otherwise.
  • A pruning of the output hierarchy is ν-close to the target clustering when the smallest target cluster exceeds 6(ν+α)n.The guarantee holds for symmetric similarity functions satisfying the (α, ν)-good neighborhood property, with runtime O(n^ω+1).
  • At thresholds below a target cluster size, good points avoid cross-cluster edges, while points within a cluster become connected when the threshold reaches that cluster’s size.This separation-and-connectivity pattern lets the procedure recover clusters of unequal sizes without knowing their sizes in advance.
  • For non-singleton blobs, the median test uses pairwise common-neighbor counts to outvote noise when most blob points are good.The proof uses the fact that more than half of relevant cross-blob pairs are good-point pairs.
  • Algorithm 1 runs in O(n^ω+1) time because it recomputes O(n^ω) data structures across O(n) merges and O(n) thresholds.

4 A More General Property: Weak Good Neighborhood

The weak good neighborhood property extends robustness beyond strict separation by allowing boundary points and requiring reliable structure mainly in local neighborhoods. Under this generalized property, the algorithm succeeds where standard linkage methods can fail, producing a hierarchy with a near-correct pruning.

  • 4 A More General Property: Weak Good Neighborhood: Boundary points can look impure at the target-cluster scale while retaining mostly target-cluster neighbors in a smaller local neighborhood.This local structure motivates calling them boundary points and supports the weaker property.
  • 4 A More General Property: Weak Good Neighborhood: The algorithm succeeds on the Figure 7 example, producing a hierarchy whose prunings include all four desired clusterings despite standard linkage failure.The desired clusterings are {AI, Statistics}, {Learning, Planning, ParameterEstimation, HypothesisTesting}, {Learning, Planning, Statistics}, and {AI, ParameterEstimation, HypothesisTesting}.
  • 4 A More General Property: Weak Good Neighborhood: The weak (α, β, ν)-good neighborhood property permits up to νn bad points and requires each remaining point to have a sufficiently large local subset with mostly in-subset neighbors.Each such subset must exceed 6(α + ν)n points, and at least a β fraction of its points must have mostly same-cluster nearest neighbors.
  • 4 A More General Property: Weak Good Neighborhood: In Figure 7, {AI, Statistics} satisfies the weak property with α = 1/32, β = 7/8, and ν equal to the fraction of adversarial bad points.With sufficiently many points, the property holds with probability at least 1−δ; the example uses areas containing more than n/32 points.
  • 4.2 Correctness under the Weak Good Neighborhood Property: Theorem 2 guarantees a ν-close pruning in time O(n^ω+1) when β ≥ 7/8, extending the earlier good-neighborhood result.The proof forms local blobs, shows most blob points are good, and uses a median test to merge blobs from the same target cluster.

5 The Inductive Setting

The inductive algorithm learns a hierarchy from a small random sample while implicitly representing the hierarchy over the full data set. Under good neighborhood properties, it provides formal accuracy guarantees with sample size independent of the full data-set size.

  • 5 The Inductive Setting: A small random sample can define a hierarchy over the entire data set, avoiding dependence on the full instance-space size.The sample is drawn uniformly from a larger finite space, and each sample node induces a cluster indicator over that space.
  • 5.2 Inductive Robust Median Neighborhood Linkage: Algorithm 2 runs Robust Median Neighborhood Linkage on the sample, then assigns each full-data point by recursively following the child containing most sampled nearest neighbors.It uses 6(α + ν)n sampled nearest neighbors and outputs both the sample hierarchy and induced functions over the full space.
  • 5.2 Inductive Robust Median Neighborhood Linkage: With sufficiently large samples, good neighborhood structure transfers to the sample with parameters (2α, 2ν) and probability at least 1 −δ.The transfer is established through sampling lemmas controlling bad points and sampled nearest-neighbor errors.
  • 5.2 Inductive Robust Median Neighborhood Linkage: If the smallest target cluster exceeds 12(ν + α)N, the induced hierarchy has a pruning (ν + δ)-close to the target with probability 1 −δ.The proof combines the sample-level guarantee with concentration bounds ensuring sufficiently many sampled good points in every target cluster.
  • 5.2 Inductive Robust Median Neighborhood Linkage: The same inductive strategy also succeeds under the weak good neighborhood property, yielding an analogous final guarantee.The corresponding sampling lemma and theorem are stated as extensions of the arguments used for the good neighborhood property.

6 Experiments

Experiments compare RMNL with established hierarchical methods on synthetic and real-world data under transductive and noisy settings. RMNL generally achieves the lowest or near-lowest errors and remains robust as several noise types increase.

  • 6.1 Synthetic Data: In synthetic experiments, RMNL has error at most ν when α + ν < 1/24 and still reports lower error than alternatives beyond that regime.Other algorithms have higher error and fail rapidly as α + ν increases, matching the proposed property-based analysis.
  • 6.2 Experiments: RMNL consistently achieves the lowest or nearly lowest errors across the real-world data sets, while Ward’s method is the strongest competing method but remains worse.The transductive comparison uses all data points and evaluates the best k-cluster pruning by classification error.
  • 6.2.2 Robustness to Noise: Under attribute corruption, RMNL remains best or near-best through noise level 0.2 across all data sets.The figure averages results over 30 runs; EigenCluster and Ward’s method also show some robustness.
  • 6.2.2 Robustness to Noise: With similarity corruption, RMNL errors remain nearly unchanged through noise level 0.2, whereas competing methods generally worsen rapidly as noise increases.Some methods are comparable without noise but degrade substantially under increasing similarity corruption.
  • 6.2.2 Robustness to Noise: With Gaussian attribute noise, all methods degrade as noise rises, but RMNL remains best or near-best through level 0.2.The paper also reports that robustness to high-variance Gaussian similarity noise is limited because neighbor rankings can change considerably.
  • Robustness to Parameter Tuning: RMNL performs well over a continuous range of α + ν values, although the usable range is relatively small for the low-noise Iris data set.The algorithm requires α and ν as additional inputs, but exact tuning is not necessary on most evaluated data sets.

7 Discussion

The paper presents RMNL as a robust bottom-up agglomerative method with guarantees under good neighborhood properties and an inductive extension for sampled data. Experiments support better performance under noise, while the discussion identifies open questions about broader similarity properties.

  • 7 Discussion: RMNL generates a hierarchy containing a pruning close to the target clustering when good neighborhood properties hold.This is the paper’s central theoretical guarantee for robust bottom-up agglomerative clustering.
  • 7 Discussion: The inductive extension uses a sample whose required size is independent of the full data-set size while retaining similar correctness guarantees.This is intended for settings where evaluating the complete data set is resource intensive.
  • 7 Discussion: With appropriate noise-parameter tuning, RMNL consistently outperforms other hierarchical algorithms and is more robust to noisy data.The inductive version is also presented as a faster alternative when full-data evaluation is expensive.
  • 7 Discussion: The authors identify extending the analysis to noisy max stability or average stability properties as an open direction.These properties are linked in the discussion to conditions previously associated with single-linkage and average-linkage success.

A Implementation Details of Algorithm 1

The implementation builds neighborhood and blob graphs from nearest-neighbor relations, merges sufficiently supported blobs, then handles singleton blobs and outputs a merge tree. Practical shortcuts accelerate late-stage merging.

  • A Implementation Details of Algorithm 1: For each scale t, the implementation constructs point graph F_t from shared nearest-neighbor relationships and blob graph H_t from inter-blob connectivity.Thresholds use α, ν, and the sample size to determine graph edges and median-neighborhood support.
  • A Implementation Details of Algorithm 1: Large connected components of H_t may be merged in arbitrary order, while the implementation chooses high-confidence connected pairs before merging singleton clusters.The selected pair maximizes median similarity divided by the combined blob size.
  • A Implementation Details of Algorithm 1: Connected non-singleton blobs are merged when their combined size exceeds 4(α + ν)n, prioritizing pairs with maximum normalized median similarity.The implementation then recomputes the relevant graph structures after merges.
  • A Implementation Details of Algorithm 1: When few singleton blobs remain, each is merged with the non-singleton blob having the highest median similarity to speed practical execution.This shortcut is described as correctly assigning all but bad points under the good neighborhood properties.
  • A Implementation Details of Algorithm 1: The final output is a tree whose leaves are individual points and whose internal nodes represent performed merges.Algorithm 3 supplies the implementation details for Robust Median Neighborhood Linkage.

B Additional Proofs for Section 5

The appendix proves that a sufficiently large random sample preserves the weak good neighborhood conditions with adjusted parameters, enabling Algorithm 2 to produce an approximately correct hierarchy with high probability.

  • The sample preserves the weak good neighborhood property after accounting for sampled bad points and adjusted neighborhood parameters.The proof establishes both neighborhood conditions using concentration bounds, sampling lemmas, and union bounds.
  • The proof combines Lemmas 8–10 with Theorem 1 to transfer correctness from the sampled hierarchy to the target clustering.
  • For sufficiently large samples, each sampled point has at most 2αn neighbors outside its relevant target neighborhood among the selected nearest neighbors.This bound is established for both the first and second weak good neighborhood conditions.
  • Algorithm 2 produces a hierarchy with a pruning that is (ν + δ)-close to the target clustering with probability 1 −δ.

C Strict Separation and Ward’s Method

Ward’s minimum variance method can fail even when strict separation holds, particularly for unbalanced clusters, producing a hierarchy that excludes the correct clustering as a pruning.

  • The failure demonstrates that strict separation alone does not guarantee successful clustering by Ward’s method when cluster sizes are unbalanced.
  • The example contains three line-separated groups A, B, and C with within-group distance 0 and between-group distances 5, 6, and 11.
  • Although {A ∪B, C} satisfies strict separation, Ward’s tree does not contain this clustering as a pruning.
  • Ward’s criterion merges clusters minimizing the increase in total within-cluster variance at each agglomerative step.
  • Ward’s method incurs 1/6 ≈16.7% error on a strictly separated instance with unbalanced clusters.The instance has groups of sizes 4n, n, and n; Ward merges the two smaller groups because that yields the lower variance increase.
Loading 1401.0247v2…