Scholion.ai

Representation of Similarity Matrices by Trees

J. A. Hartigan

Journal of the American Statistical Association · 1967 · Volume 62 · Issue 320

DOI: 10.1080/01621459.1967.10500922

Abstract

Suppose given a set of similarities (or dissimilarities) between pairs of of objects from some set of objects, such as animal species, books, colours. We wish to construct from this similarity matrix a tree, or nested set of clusterings of the objects; graphs of trees provide a striking visual display of similarity groupings of the objects. The construction requires (1) a definition specifying when a similarity matrix has exact tree structure, (2) a measure of distance between any two similarity matrices, which yields (when combined with (1)) a measure of distance between any similarity matrix and any tree, (3) a family of local operations on a tree, which can be used to search out trees which best fit a given similarity matrix. The construction technique is applied to voting behaviour of the 50 United States in the last 13 presidential elections, giving a tree clustering of the states.

Enable JavaScript for citation tools and additional paper interactions.