Common Pitfalls Using the Normalized Compression Distance: What to Watch Out for in a Compressor
Manuel Alfonseca, Manuel Cebrián, Alfonso Ortega · Communications in Information and Systems · 2005
Using the mathematical background for algorithmic complexity developed by Kolmogorov in the sixties, Cilibrasi and Vitanyi have designed a similarity distance named normalized compression distance applicable to the clustering of objects of any kind, such as music, texts or gene sequences.The normalized compression distance is a quasi-universal normalized admissible distance under certain conditions.This paper shows that the compressors used to compute the normalized compression distance are not idempotent in some cases, being strongly skewed with the size of the objects and window size, and therefore causing a deviation in the identity property of the distance if we don't take care that the objects to be compressed fit the windows.The relationship underlying the precision of the distance and the size of the objects has been analyzed for several well-known compressors, and specially in depth for three cases, bzip2, gzip and PPMZ which are examples of the three main types of compressors: block-sorting, Lempel-Ziv, and statistic. Introduction.A natural measure of similarity assumes that two objects x and y are similar if the basic blocks of x are in y and vice versa.If this happens we can describe object x by making reference to the blocks belonging to y, thus the description of x will be very simple using the description of y.This is partially what a compressor does to code the catenated xy sequence: a search for information shared by both sequences in order to reduce the redundancy of the whole sequence.If the result is small, it means that a lot of information contained in x can be used to code y, following the similarity conditions described in the previous paragraph.This was formalized by Rudi Cilibrasi and Paul Vitányi [2], giving rise to the concept of normalized compression distance (NCD), which is based on the use of compressors to provide a measure of the similarity between the objects.This distance may then be used to cluster those objects.This idea is very powerful, because it can be applied in the same way to all kind of objects, such as music, texts or gene sequences.There is no need to use specific features of the objects to cluster.The only thing needed to compute the distance from one object x to another object y, is to measure the ability of x to turn the description of y simple and vice versa.Cilibrasi and Vitányi have perfected this idea in two ways, by stating the conditions that a compressor must hold to be useful in the computation of the NCD, and by giving formal expression to the quality of the distance in comparison with an ideal distance proposed by Vitányi and others in [3].In this paper we show that the