Normalized compression distance

From HandWiki

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 [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] as the length of the shortest program [math]\displaystyle{ p }[/math] that computes [math]\displaystyle{ x }[/math] from [math]\displaystyle{ y }[/math] 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 [math]\displaystyle{ p }[/math] one uses the notion of Kolmogorov complexity. Then, it has been shown [1]

[math]\displaystyle{ |p| = \max \{K(x\mid y),K(y\mid x)\} }[/math]

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).[1]

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),

[math]\displaystyle{ NID(x,y) = \frac{ \max\{K{(x\mid y)},K{(y\mid x)}\} }{ \max \{K(x),K(y)\}}, }[/math]

where [math]\displaystyle{ K(x\mid y) }[/math] is algorithmic information of [math]\displaystyle{ x }[/math] given [math]\displaystyle{ y }[/math] as input. The NID is called `the similarity metric.' since the function [math]\displaystyle{ NID(x,y) }[/math] has been shown to satisfy the basic requirements for a metric distance measure.[2][3] However, it is not computable or even semicomputable.[4]

Normalized compression distance

While the NID metric is not computable, it has an abundance of applications. Simply approximating [math]\displaystyle{ K }[/math] by real-world compressors, with [math]\displaystyle{ Z(x) }[/math] is the binary length of the file [math]\displaystyle{ x }[/math] compressed with compressor Z (for example "gzip", "bzip2", "PPMZ") in order to make NID easy to apply.[2] Vitanyi and Cilibrasi rewrote the NID to obtain the Normalized Compression Distance (NCD)

[math]\displaystyle{ NCD_Z(x,y) = \frac{Z(xy) - \min \{Z(x),Z(y)\}}{\max \{Z(x),Z(y)\}}. }[/math][3]

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.[3]

Applications

The normalized compression distance has been used to fully automatically reconstruct language and phylogenetic trees.[2][3] It can also be used for new applications of general clustering and classification of natural data in arbitrary domains,[3] for clustering of heterogeneous data,[3] and for anomaly detection across domains.[5] The NID and NCD have been applied to numerous subjects, including music classification,[3] to analyze network traffic and cluster computer worms and viruses,[6] authorship attribution,[7] gene expression dynamics,[8] predicting useful versus useless stem cells,[9] critical networks,[10] image registration,[11] question-answer systems.[12]

Performance

Researchers from the datamining community use NCD and variants as "parameter-free, feature-free" data-mining tools.[5] One group have experimentally tested a closely related metric on a large variety of sequence benchmarks. Comparing their compression method with 51 major methods found in 7 major data-mining conferences over the past decade, they established superiority of the compression method for clustering heterogeneous data, and for anomaly detection, and competitiveness in clustering domain data.

NCD has an advantage of being robust to noise.[13] However, although NCD appears "parameter-free", practical questions include which compressor to use in computing the NCD and other possible problems.[14]

Comparison with the Normalized Relative Compression (NRC)

In order to measure the information of a string relative to another there is the need to rely on relative semi-distances (NRC).[15] These are measures that do not need to respect symmetry and triangle inequality distance properties. Although the NCD and the NRC seem very similar, they address different questions. The NCD measures how similar both strings are, mostly using the information content, while the NRC indicates the fraction of a target string that cannot be constructed using information from another string. For a comparison, with application to the evolution of primate genomes, see.[16]

Normalized Google distance

Main page: Normalized Google distance

Objects can be given literally, like the literal four-letter genome of a mouse, or the literal text of War and Peace by Tolstoy. For simplicity we take it that all meaning of the object is represented by the literal object itself. Objects can also be given by name, like "the four-letter genome of a mouse," or "the text of `War and Peace' by Tolstoy." There are also objects that cannot be given literally, but only by name, and that acquire their meaning from their contexts in background common knowledge in humankind, like "home" or "red." We are interested in semantic similarity. Using code-word lengths obtained from the page-hit counts returned by Google from the web, we obtain a semantic distance using the NCD formula and viewing Google as a compressor useful for data mining, text comprehension, classification, and translation. The associated NCD, called the normalized Google distance (NGD) can be rewritten as

[math]\displaystyle{ NGD(x,y)= \frac{ \max \{\log f(x), \log f(y)\} - \log f(x,y) }{ \log N - \min\{\log f(x), \log f(y) \}}, }[/math]

where [math]\displaystyle{ f(x) }[/math] denotes the number of pages containing the search term [math]\displaystyle{ x }[/math], and [math]\displaystyle{ f(x,y) }[/math] denotes the number of pages containing both [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math],) as returned by Google or any search engine capable of returning an aggregate page count. The number [math]\displaystyle{ N }[/math] can be set to the number of pages indexed although it is more proper to count each page according to the number of search terms or phrases it contains. As rule of the thumb one can multiply the number of pages by, say, a thousand...[17]

See also

References

  1. ↑ 1.0 1.1 C.H. Bennett, P. Gacs, M. Li, P.M.B. Vitányi, and W. Zurek, Information Distance, IEEE Trans. Inform. Theory, IT-44:4(1998) 1407–1423
  2. ↑ 2.0 2.1 2.2 Li, Ming; Chen, Xin; Li, Xin; Ma, Bin; Vitanyi, P. M. B. (2011-09-27). "M. Li, X. Chen, X. Li, B. Ma, P.M.B. Vitanyi, The similarity metric, IEEE Trans. Inform. Th., 50:12(2004), 3250–3264". IEEE Transactions on Information Theory 50 (12): 3250–3264. doi:10.1109/TIT.2004.838101. 
  3. ↑ 3.0 3.1 3.2 3.3 3.4 3.5 3.6 Cilibrasi, R.; Vitanyi, P. M. B. (2011-09-27). "R. Cilibrasi, P.M.B. Vitanyi, Clustering by compression". IEEE Transactions on Information Theory 51 (4): 1523–1545. doi:10.1109/TIT.2005.844059. 
  4. ↑ Terwijn, Sebastiaan A.; Torenvliet, Leen; Vitányi, Paul M.B. (2011). "Nonapproximability of the normalized information distance". Journal of Computer and System Sciences 77 (4): 738–742. doi:10.1016/j.jcss.2010.06.018. https://ir.cwi.nl/pub/19043. 
  5. ↑ 5.0 5.1 Keogh, Eamonn; Lonardi, Stefano; Ratanamahatana, Chotirat Ann (2004-08-22). "Towards parameter-free data mining". E. Keogh, S. Lonardi, and C.A. Ratanamahatana. "Towards parameter-free data mining." In Conference on Knowledge Discovery in Data: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, vol. 22, no. 25, pp. 206–215. 2004. Dl.acm.org. pp. 206. doi:10.1145/1014052.1014077. ISBN 978-1581138887. 
  6. ↑ S. Wehner, Analyzing worms and network traffic using compression, Journal of Computer Security, 15:3(2007), 303–320. Iospress.metapress.com. http://iospress.metapress.com/content/y3q582341n5l8ux2/. Retrieved 2012-11-03. 
  7. ↑ Stamatatos, Efstathios (2009). "A survey of modern authorship attribution methods". Journal of the American Society for Information Science and Technology 60 (3): 538–556. doi:10.1002/asi.21001. 
  8. ↑ Nykter, M. (2008). "Gene expression dynamics in the macrophage exhibit criticality". Proceedings of the National Academy of Sciences 105 (6): 1897–1900. doi:10.1073/pnas.0711525105. PMID 18250330. Bibcode: 2008PNAS..105.1897N. 
  9. ↑ Cohen, Andrew R (2010). "Computational prediction of neural progenitor cell fates". Nature Methods 7 (3): 213–218. doi:10.1038/nmeth.1424. PMID 20139969. 
  10. ↑ Nykter, Matti; Price, Nathan D.; Larjo, Antti; Aho, Tommi; Kauffman, Stuart A.; Yli-Harja, Olli; Shmulevich, Ilya (2008). "M. Nykter, N.D. Price, A. Larjo, T. Aho, S.A. Kauffman, O. Yli-Harja1, and I. Shmulevich, Critical networks exhibit maximal information diversity in structure-dynamics relationships, Phys. Rev. Lett. 100, 058702 (2008)". Physical Review Letters 100 (5): 058702. doi:10.1103/PhysRevLett.100.058702. PMID 18352443. 
  11. ↑ Bardera, Anton; Feixas, Miquel; Boada, Imma; Sbert, Mateu (July 2006). "Compression-based Image Registration". M. Feixas, I. Boada, M. Sbert, Compression-based Image Registration. Proc. IEEE International Symposium on Information Theory, 2006. 436–440. Ieeexplore.ieee.org. pp. 436–440. doi:10.1109/ISIT.2006.261706. ISBN 978-1-4244-0505-3. 
  12. ↑ Zhang, Xian; Hao, Yu; Zhu, Xiaoyan; Li, Ming; Cheriton, David R. (2007). "Information distance from a question to an answer". X Zhang, Y Hao, X Zhu, M Li, Information distance from a question to an answer, Proc. 13th ACM SIGKDD international conference on Knowledge discovery and data mining, 2007, 874–883. Dl.acm.org. pp. 874. doi:10.1145/1281192.1281285. ISBN 9781595936097. 
  13. ↑ Cebrian, M.; Alfonseca, M.; Ortega, A. (2011-09-27). "The normalized compression distance is resistant to noise". IEEE Transactions on Information Theory 53 (5): 1895–1900. doi:10.1109/TIT.2007.894669. 
  14. ↑ "M. Cebrián, M. Alfonseca, and A. Ortega, Common pitfalls using the normalized compression distance: what to watch out for in a compressor, Commun. Inf. Syst. 5:4(2005), 367–384". Projecteuclid.org. http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.cis/1175791028. 
  15. ↑ Ziv, J.; Merhav, N. (1993). "A measure of relative entropy between individual sequences with application to universal classification". IEEE Transactions on Information Theory 39 (4): 1270–1279. doi:10.1109/18.243444. 
  16. ↑ Pratas, Diogo; Silva, Raquel M.; Pinho, Armando J. (2018). "Comparison of Compression-Based Measures with Application to the Evolution of Primate Genomes". Entropy 20 (6): 393. doi:10.3390/e20060393. PMID 33265483. Bibcode: 2018Entrp..20..393P.  CC-BY icon.svg Material was copied from this source, which is available under a Creative Commons Attribution 4.0 International License.
  17. ↑ Cilibrasi, R. L.; Vitanyi, P. M. B. (2011-09-27). "R.L. Cilibrasi, P.M.B. Vitanyi, The Google Similarity Distance, IEEE Trans. Knowledge and Data Engineering, 19:3(2007), 370-383". IEEE Transactions on Knowledge and Data Engineering 19 (3): 370–383. doi:10.1109/TKDE.2007.48. 

External links

  • Efficient Estimation of Word Representations in Vector Space
  • M. Li and P. Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, Springer-Verlag, New York, 4th Edition 2019



Retrieved from "https://handwiki.org/wiki/index.php?title=Normalized_compression_distance&oldid=3431564"