Normalized compression distance (NCD) is a way of measuring the similarity between two objects, be it two documents, two letters, two emails, two music scores, two languages, two programs, two pictures, two systems, two genomes, to name a few. Such a measurement should not be application dependent or arbitrary. A reasonable definition for the similarity between two objects is how difficult it is to transform them into each other. It can be used in information retrieval and data mining for cluster analysis.
Information distance We assume that the objects one talks about are finite strings of 0s and 1s. Thus we mean string similarity. Every computer file is of this form, that is, if an object is a file in a computer it is of this form. One can define the information distance between strings x {\displaystyle x} and y {\displaystyle y} as the length of the shortest program p {\displaystyle p} that computes x {\displaystyle x} from y {\displaystyle y} and vice versa. This shortest program is in a fixed programming language. For technical reasons one uses the theoretical notion of Turing machines. Moreover, to express the length of p {\displaystyle p} one uses the notion of Kolmogorov complexity. Then, it has been shown
| p | = max { K ( x ∣ y ) , K ( y ∣ x ) } {\displaystyle |p|=\max\{K(x\mid y),K(y\mid x)\}}
up to logarithmic additive terms which can be ignored. This information distance is shown to be a metric (it satisfies the metric inequalities up to a logarithmic additive term), is universal (it minorizes every computable distance as computed for example from features up to a constant additive term).
Normalized information distance (similarity metric) The information distance is absolute, but if we want to express similarity, then we are more interested in relative ones. For example, if two strings of length 1,000,000 differ by 1000 bits, then we consider that those strings are relatively more similar than two strings of 1000 bits that differ by 1000 bits. Hence we need to normalize to obtain a similarity metric. This way one obtains the normalized information distance (NID),
N I D ( x , y ) = max { K ( x ∣ y ) , K ( y ∣ x ) } max { K ( x ) , K ( y ) } , {\displaystyle NID(x,y)={\frac {\max\{K{(x\mid y)},K{(y\mid x)}\}}{\max\{K(x),K(y)\}}},}
where K ( x ∣ y ) {\displaystyle K(x\mid y)} is algorithmic information of x {\displaystyle x} given y {\displaystyle y} as input. The NID is called the similarity metric. Since the function N I D ( x , y ) {\displaystyle NID(x,y)} has been shown to satisfy the basic requirements for a metric distance measure. However, it is not computable or even semicomputable.
Normalized compression distance While the NID metric is not computable, it has an abundance of applications. Simply approximating K {\displaystyle K} by real-world compressors, Vitanyi and Cilibrasi rewrote the NID to obtain the Normalized Compression Distance (NCD). If Z ( x ) {\displaystyle Z(x)} is the binary length of file x {\displaystyle x} compressed with compressor Z {\displaystyle Z} (for example "gzip", "bzip2", "PPMZ") and Z ( x y ) {\displaystyle Z(xy)} denotes compressing the concatenation of x {\displaystyle x} and y {\displaystyle y} :
N C D Z ( x , y ) = Z ( x y ) − min { Z ( x ) , Z ( y ) } max { Z ( x ) , Z ( y ) } {\displaystyle NCD_{Z}(x,y)={\frac {Z(xy)-\min\{Z(x),Z(y)\}}{\max\{Z(x),Z(y)\}}}} The NCD is actually a family of distances parametrized with the compressor Z. The better Z is, the closer the NCD approaches the NID, and the better the results are.
… excerpt ends here. Continue reading the full article.
