A Method for Comparing Two Hierarchical Clusterings

Abstract

This article concerns the derivation and use of a measure of similarity between two hierarchical clusterings. The measure, B_k , is derived from the matching matrix, [m_ij ], formed by cutting the two hierarchical trees and counting the number of matching entries in the k clusters in each tree. The mean and variance of B_k are determined under the assumption that the margins of [m_ij ] are fixed. Thus, B_k represents a collection of measures for k = 2, …, n – 1. (k, B_k ) plots are found to be useful in portraying the similarity of two clusterings. B_k is compared to other measures of similarity proposed respectively by Baker (1974) and Rand (1971). The use of (k, B_k ) plots for studying clustering methods is explored by a series of Monte Carlo sampling experiments. An example of the use of (k, B_k ) on real data is given.

Key Words:

• Clustering
• Measures of similarity
• Statistical graphics