Generalising Ward's Method for Use with Manhattan Distances

PLoS One. 2017 Jan 13;12(1):e0168288. doi: 10.1371/journal.pone.0168288. eCollection 2017.

Abstract

The claim that Ward's linkage algorithm in hierarchical clustering is limited to use with Euclidean distances is investigated. In this paper, Ward's clustering algorithm is generalised to use with l1 norm or Manhattan distances. We argue that the generalisation of Ward's linkage method to incorporate Manhattan distances is theoretically sound and provide an example of where this method outperforms the method using Euclidean distances. As an application, we perform statistical analyses on languages using methods normally applied to biology and genetic classification. We aim to quantify differences in character traits between languages and use a statistical language signature based on relative bi-gram (sequence of two letters) frequencies to calculate a distance matrix between 32 Indo-European languages. We then use Ward's method of hierarchical clustering to classify the languages, using the Euclidean distance and the Manhattan distance. Results obtained from using the different distance metrics are compared to show that the Ward's algorithm characteristic of minimising intra-cluster variation and maximising inter-cluster variation is not violated when using the Manhattan metric.

MeSH terms

  • Algorithms*
  • Cluster Analysis*
  • Europe
  • Humans
  • India
  • Language*
  • Linguistics*
  • Models, Theoretical*

Grants and funding

The authors received no specific funding for this work.