Normalized Information Distance

The Normalized Information Distance is a universal distance measurement for many different objects. Since the Normalized Information Distance is based on Kolmogorov complexity, the actual distance value cannot be computer, nevertheless, there are still many ways to take advantage of the concept. First of all, compression algorithms can be used to approximate Kolmogorov complexity, as long as the objects being compressed can have a string representation.

Second, page count statistics obtained from the World Wide Web can be used for names and even abstract concepts. These practical applications of the normalized information distance are then applied to machine learning tasks to assist in tasks such as data mining. We will explore both the theoretical and practical implications of Normalized Information Distance. Real world applications include music clustering, bioinformatics and machine translation.

Kolmogorov complexity measures the absolute information content of individual objects. In the tasks of clustering and data mining, it is also necessary to measure the absolute information distance between individual objects. Measuring absolute information distance is a universal requirement for determining a distance between two objects x and y. The distance between two string is defined as the minimum quantity of information required to translate x into y or vice versa. Unfortunately, because of the universal requirement that this information be based on Kolmogorov complexity, the distance is uncomputable. To get around this dilemma, several formulas and approaches have been developed that come close to approximating Kolmogorov complexity.

Continuing along the line that Kolmogorov Complexity is the length of the shortest program that outputs x on input y, has some interesting implications. One of the implications is that if x and y are concatenated, we still have two distinct objects, just concatenated. When we concatenate these programs, then, run them through a compressor, and compare the output of the concatenated result with the individual components, we now have a metric for the similarity between x and y. As x and y become more similary, the output of the concatenation of x and y, will tend to be the same as x and y compressed and unconcatenated.

Normalized Compression Distance

The Normalized Information Distance is impractical since it cannot be computed. To overcome this limitation, a practical form of the Normalized Information Distance was developed. This practical form is known as the Normalized Compression Distance. The Normalized Compression Distance utilizes the properties of data compressors (gzip, bzip, & PPMZ) to replace Kolmogorov complexity with a practical value. Making the proper substitutions gives us the following formula:

NCD =	C(xy) - min(C(x), C(y))
	-----------------------------------------------
	max(C(x), C(y))

where:

C(x) = Size of compressed file: X.
C(y) = Size of compressed file: Y.
C(xy) = Size of compressed file: concatenated files x & y.
min(C(x), C(y)) = min compressed file size of x & y.
max(C(x), C(y)) = max compressed file size of x & y.