PaperlayerView exact revision on arXiv

Source-linked AI summary

A Simple and Efficient Method to Compute a Single Linkage Dendrogram

Huanbiao Zhu, Werner Stuetzle

arXiv:1911.00223v1cs.DScs.LGstat.COstat.ML

TL;DR

The paper addresses efficient computation of a single-linkage dendrogram without storing all interpoint distances. It uses MST recursive partitioning and Prim’s algorithm information to identify subtree vertices and edges without additional computational cost. The method also addresses tied edge weights by relating Prim’s orders of the graph and its minimum spanning tree.

  • Problem

    Computing a single-linkage dendrogram by iterative merging requires storing the interpoint distance matrix.

    Source: §1.4 · p. 3

  • Method

    The method forms an MST, recursively breaks its longest edges, and uses Prim’s algorithm information to identify the resulting subtree vertices and edges.

    Source: §1.4 · p. 4

  • Results

    The subtree vertices and edges can be identified easily and efficiently without additional computational cost, while distances need not be stored.

    Source: §5 · p. 11

  • Takeaways & Limitations

    Prim’s MST construction supports single-linkage dendrogram computation while calculating distances as needed rather than storing the interpoint distance matrix.

    Source: §5 · p. 11

    With tied edge weights, multiple minimum spanning trees and Prim’s orders may exist, so the unique-tree restriction must be removed.

    Source: §4 · pp. 8, 10

Abstract

from arXiv · show

We address the problem of computing a single linkage dendrogram. A possible approach is to: (i) Form an edge weighted graph $G$ over the data, with edge weights reflecting dissimilarities. (ii) Calculate the MST $T$ of $G$. (iii) Break the longest edge of $T$ thereby splitting it into subtrees $T_L$, $T_R$. (iv) Apply the splitting process recursively to the subtrees. This approach has the attractive feature that Prim's algorithm for MST construction calculates distances as needed, and hence there is no need to ever store the inter-point distance matrix. The recursive partitioning algorithm requires us to determine the vertices (and edges) of $T_L$ and $T_R$. We show how this can be done easily and efficiently using information generated by Prim's algorithm without any additional computational cost.

1 Introduction

The paper introduces hierarchical single-linkage clustering and a dendrogram representation, then develops an MST-based method that identifies recursive subtrees using Prim’s algorithm without storing the interpoint distance matrix.

1.1 Hierarchical Clustering

  • Hierarchical clustering produces a sequence of nested partitions by repeatedly merging clusters, whereas flat methods require a target number of clusters.Source: §1.1 · p. 2
  • Single linkage defines the distance between two clusters using the minimum dissimilarity between an object in each cluster.Source: §1.1 · p. 2

1.2 Dendrogram

  • A dendrogram lays out the binary merge tree with leaves for observations and vertical positions of internal nodes representing merge distances.Source: §1.2 · p. 2

1.3 Extracting Partitions

  • Dendrogram cutting selects a distance threshold and eliminates nodes below it to obtain a partition, as illustrated by Figure 1.Source: §1.3 · pp. 2–3, Figure 1 · p. 3

1.4 Computing the Single Linkage Dendrogram

  • Prim’s-based MST construction calculates distances as needed, avoiding storage of the interpoint distance matrix while determining recursive subtree structure.Source: §1.4 · pp. 3–4
  • The proposed method computes an MST, recursively removes its longest edge to form subtrees, and identifies their vertices and edges from Prim’s algorithm information.Source: §1.4 · p. 4

2 Prim’s Algorithm and Prim’s Order

Prim’s algorithm grows a minimum spanning tree from an arbitrary seed by repeatedly adding the lightest connecting edge. The resulting vertex order also orders MST edges, with uniqueness depending on tied edge weights.

2.1 Prim’s algorithm

  • In single-linkage applications, the graph is typically complete over Euclidean points, with edge weights equal to Euclidean distances.Source: §2.1 · p. 4
  • Prim’s algorithm initializes a tree with an arbitrary seed and repeatedly adds the minimum-weight edge connecting the tree to an unconnected vertex.Source: §2.1 · p. 4

2.2 Prim’s order

  • Distinct edge weights make the MST and Prim’s order unique, whereas tied weights can produce multiple MSTs and multiple orders for one seed.Source: §2.1 · p. 4, §2.2 · p. 5
  • Each vertex’s addition defines Prim’s order, whose positions depend on the arbitrary seed vertex.Source: §2.2 · pp. 4–5
  • For an MST edge, its Prim’s-order position is the larger Prim’s-order position of its two endpoints.Source: §2.2 · p. 5

Edge

The method uses Prim’s order on an MST to identify the two components created by cutting the longest edge, then applies this rule recursively to construct the single linkage dendrogram.

Edge

  • The key proposition states that vertices with orders below P(emax) form one subtree, while those with orders at least P(emax) form the other.Source: Edge · pp. 5–6
  • Prim’s orders partition the vertices and edges of the two subtrees formed by breaking the longest MST edge.For emax=(vi,vj), P(emax)=max(P(vi),P(vj)); vertices and edges are assigned by their order relative to this value.Source: Edge · p. 6
  • Prim’s order is preserved between a graph and its MST when both runs use the same seed vertex, enabling the proposition to be proved on the tree alone.Source: Edge · pp. 5, 7
  • Within the MST, all edges in the seeded subtree are selected before the longest connecting edge, so its vertices are connected before those in the other subtree.Source: Edge · p. 7
  • The Prim’s-order rule remains valid recursively because each resulting subtree is itself an MST and its local order is equivalent to the corresponding segment of the original order.Source: Edge · p. 8
  • After computing one MST, the algorithm identifies every split from Prim’s order and stores node-member order ranges instead of all members.Source: Edge · p. 8

4 The Case of Tied Edge Weights

Tied longest edges make Prim’s growth order ambiguous, so the paper generalizes the splitting rule by breaking the tied edge with the largest Prim’s order.

4 The Case of Tied Edge Weights

  • The original distinct-edge-weight assumption is removed, while Proposition 1 remains valid with the stated alteration to edge selection.Source: §4 · pp. 8, 10, 11
  • When longest edge weights are tied, different choices between tied edges can produce different Prim’s orders and incompatible first splits.With two longest edges e1 and e2, breaking e1 first yields different components from breaking e2 first.Source: Figure 5 · p. 9, §4 · p. 9
  • The generalized proposition breaks the tied longest edge having the largest Prim’s order, then applies the same order-based vertex and edge partition.The resulting sets use P(emax)=max(P(vi),P(vj)) for the selected edge.Source: §4 · pp. 9–10
  • The generalized lemma allows every Prim’s order of the graph to serve as a Prim’s order of the MST, and conversely, under the same seed vertex.Source: §4 · p. 10
  • Selecting the tied edge with the largest Prim’s order ensures other tied longest edges lie in the already reached subtree rather than the later subtree.Source: §4 · p. 10

5 Summary

The paper presents a recursive MST-based procedure for computing a single linkage dendrogram while avoiding storage of the inter-point distance matrix. Its contribution is an efficient way to identify the vertices and edges of the recursively formed subtrees using information generated by Prim’s algorithm.

  • The method computes a single linkage dendrogram by recursively splitting an MST at its longest edge.It forms a dissimilarity-weighted graph, computes its MST, breaks the longest edge into subtrees, and repeats the process.Source: §5 · p. 11
  • Prim’s algorithm calculates distances as needed, eliminating the need to store the inter-point distance matrix.Source: §5 · p. 11
  • The recursive partitioning procedure determines the vertices and edges of the resulting subtrees.Source: §5 · p. 11
  • The paper shows that Prim’s generated information supports this subtree determination easily and efficiently without additional computational cost.Source: §5 · p. 11
Loading 1911.00223v1…