Generalising Ward's Method for Use with Manhattan Distances

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 metho...

Full description

Saved in:
Bibliographic Details
Published in:PloS one 2017-01, Vol.12 (1), p.e0168288-e0168288
Main Authors: Strauss, Trudie, von Maltitz, Michael Johan
Format: Article
Language:English
Subjects:
Algorithms
Bioinformatics
Biology and Life Sciences
Cluster Analysis
Clustering
Clusters
Computer and Information Sciences
Engineering and Technology
Euclidean geometry
Europe
Humans
India
Language
Languages
Linguistics
Methods
Models, Theoretical
Phylogenetics
Physical Sciences
Research and Analysis Methods
Social Sciences
Statistical analysis
Statistics
Taxonomy
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1932-6203
1932-6203
DOI:10.1371/journal.pone.0168288