Clustering by compression

By Rudi Cilibrasi, Paul M. B. Vitányi. 2003

1,184 citations recorded by the source corpus.

We present a new method for clustering based on compression. The method does not use subject-specific features or background knowledge, and works as follows: First, we determine a parameter-free, universal, similarity distance, the normalized compression distance or NCD, computed from the lengths of compressed data files (singly and in pairwise concatenation). Second, we apply a hierarchical clustering method. The NCD is not restricted to a specific application area, and works across application area boundaries. A theoretical precursor, the normalized information distance, co-developed by one of the authors, is provably optimal. However, the optimality comes at the price of using the noncomputable notion of Kolmogorov complexity. We propose axioms to capture the real-world setting, and show that the NCD approximates optimality. To extract a hierarchy of clusters from the distance matrix, we determine a dendrogram (ternary tree) by a new quartet method and a fast heuristic to implement it. The method is implemented and available as public software, and is robust under choice of different compressors. To substantiate our claims of universality and robustness, we report evidence of successful application in areas as diverse as genomics, virology, languages, literature, music, handwritten digits, astronomy, and combinations of objects from completely different domains, using statistical, dictionary, and block sorting compressors. In genomics, we presented new evidence for major questions in Mammalian evolution, based on whole-mitochondrial genomic analysis: the Eutherian orders and the Marsupionta hypothesis against the Theria hypothesis.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Molecular Biology

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Molecular Biology

Citations in the corpus

Least Square Projection: A Fast High-Precision Multidimensional Projection Technique and Its Application to Document Mapping (2008, methodology): “For the precision tests, we have used distances based on vector representations and also a new stream-based similarity measure based on the approximation by compression of the Kolmogorov Complexity [ 38 ] slightly modified to accommodate problems related with compressor accuracy [39], called Scaled ”
A survey of modern authorship attribution methods (2009, background): “…authorship, including American and English literature (Argamon et al., 2007; Koppel et al., 2007; McCarthy et al., 2006; Uzuner & Katz, 2005; Zhao & Zobel, 2007), Russian literature (Cilibrasi & Vitanyi, 2005; Kukushkina et al., 2001), Italian literature (Benedetto et al., 2002), and so on.”
A Field Guide to Genetic Programming (2008, background): “However, many interesting cases remain (Cilibrasi and Vitanyi, 2005) such as Arabic (Klassen and Heywood, 2002) and oriental languages, handwriting (De Stefano, Cioppa, and Marcelli, 2002; Gagne and Parizeau, 2006; Krawiec, 2004; Teredesai and Govindaraju, 2005) (such as the MNIST examples), other t”
The similarity metric (2001, methodology): “As a next step, using theapproachin[ 15 ],wehaveappliedthismethodtomuch larger nuclear genomes of fungi and yeasts.”
Author ' s personal copy A Fast Quartet tree heuristic for hierarchical clustering (2010, methodology): “Using the CompLearn package, in [12] we studied hypotheses concerning mammalian evolution, by reconstructing the phylogeny from the mitochondrial genomes of 24 species.”
An Anti-Phishing System Employing Diffused Information (2014, methodology): “Given a compression algorithm C, Normalized Compression Distance (NCD) is given by [Cilibrasi and Vitanyi 2005]: C(xy) - min{C(x), C(y)} NCD(x, y) = , (2) max{C(x), C(y)} where C(xy) refers to the compressed concatenation of the strings representing x and y,and C(x) is the compressed string…”
A Comparison of Personal Name Matching: Techniques and Practical Issues (2006, background): “Compression based similarity calculations have recently been investigated [6] for use in clustering of biological sequences, optical character recognition, and music.”
The Google Similarity Distance (2004, background): “This seems to be a new direction altogether.”