Information shared by many objects

ABSTRACT

If Kolmogorov complexity [25] measures information in one object and Information Distance measures information shared by two objects, how do we measure information shared by many objects? This paper provides an initial pragmatic study of this fundamental data mining question. Firstly, E_m(x₁,x₂,...,x_n) is defined to be the minimum amount of thermodynamic energy needed to convert from any x_i to any x_j. With this definition several theoretical problems have been solved. Second, our newly proposed theory is applied to select a comprehensive review and a specialized review from many reviews: (1) Core feature words, expanded words and dependent words are extracted respectively. (2) Comprehensive and specialized reviews are selected according to the information among them. This method of selecting a single review can be extended to select multiple reviews as well. Finally, experiments show that this comprehensive and specialized review mining method based on our new theory can do the job efficiently.

REFERENCES

• 1: C. Ané and M. Sanderson. Missing the forest for the trees: Phylogenetic compression and its implications for inferring complex evolutionary histories. Systematic Biology, 54(1):146--157, 2005.
• 2: T. Arbuchle, A. Balaban, D. Peters, and M. Lawford. Software documents: Comparison and measurement. In The Nineteenth International Conference on Software Engineering and Knowledge Engineering, July 2007.
• 3: D. Benedetto, E. Caglioti, and V. Loreto. Language trees and zipping. Physical Review Letters, 88(4):048702, 2002.
• 4: C. Bennett, P. Gacs, M. Li, P. Vitányi, and W. Zurek. Information distance. IEEE Transactions on Information Theory, 44(4):1407--1423, July 1998.
• 5: C. Bennett, M. Li, and B. Ma. Chain letters and evolutionary histories. Scientific American, 288(6):76--81, June 2003.
• 6: Jaime Carbonell , Jade Goldstein, The use of MMR, diversity-based reranking for reordering documents and producing summaries, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.335-336, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291025]
• 7: Pimwadee Chaovalit , Lina Zhou, Movie Review Mining: a Comparison between Supervised and Unsupervised Classification Approaches, Proceedings of the Proceedings of the 38th Annual Hawaii International Conference on System Sciences (HICSS'05) - Track 4, p.112.3, January 03-06, 2005 [doi>10.1109/HICSS.2005.445]
• 8: X. Chen, B. Francia, M. Li, B. Mckinnon, and A. Seker. Shared information and program plagiarism detection. IEEE Transactions on Information Theory, 50(7):1545--1550, July 2004.
• 9: Alexei Chernov , Andrej Muchnik , Andrei Romashchenko , Alexander Shen , Nikolai Vereshchagin, Upper semi-lattice of binary strings with the relation "x is simple conditional to y", Theoretical Computer Science, v.271 n.1-2, p.69-95, January 28, 2002 [doi>10.1016/S0304-3975(01)00032-9]
• 10: R. Cilibrasi and P. Vitányi. Clustering by compression. IEEE Transactions on Information Theory, 51(4):1523--1545, 2005.
• 11: Rudi Cilibrasi , Paul Vitányi , Ronald De Wolf, Algorithmic Clustering of Music Based on String Compression, Computer Music Journal, v.28 n.4, p.49-67, December 2004 [doi>10.1162/0148926042728449]
• 12: Rudi L. Cilibrasi , Paul M. B. Vitanyi, The Google Similarity Distance, IEEE Transactions on Knowledge and Data Engineering, v.19 n.3, p.370-383, March 2007 [doi>10.1109/TKDE.2007.48]
• 13: M. C. de Marneffe, B. MacCartney, and C. D. Manning. Generating typed dependency parses from phrase structure parses. In The fifth international conference on Language Resources and Evaluation (LREC), May 2006.
• 14: K. Emanuel, S. Ravela, E. Vivant, and C. Risi. A combined statistical-deterministic approach of hurricane risk assessment. manuscript, Program in Atmospheres, Oceans, and Climate, MIT, 2005.
• 15: M. Gamon, A. Aue, S. C. Oliver, and E. Ringger. Pulse: Mining customer opinions from free text. In International Symposium on Intelligent Data Analysis (IDA), pages 121--132, October 2005.
• 16: M. Hayashida and T. Akutsu. Image compression-based approach to measuring the similarity of protein structures. In The 6th Asia-Pacific Bioinformatics Conference, pages 221--230, 2008.
• 17: Minqing Hu , Bing Liu, Mining and summarizing customer reviews, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014073]
• 18: Eamonn Keogh , Stefano Lonardi , Chotirat Ann Ratanamahatana, Towards parameter-free data mining, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014077]
• 19: S. Kirk and S. Jenkins. Information theory-based software metrics and obfuscation. Journal of Systems and Software, 72:179--186, 2004.
• 20: András Kocsor , Attila Kertész-Farkas , László Kaján , Sándor Pongor, Application of compression-based distance measures to protein sequence classification: a methodological study, Bioinformatics, v.22 n.4, p.407-412, February 2006 [doi>10.1093/bioinformatics/bti806]
• 21: A. Kraskov, H. Stogbauer, R. Andrzejak, and P. Grassberger. Hierarchical clustering using mutual information. Europhys. Lett, 70(2):278--284, 2005.
• 22: N. Krasnogor , D. A. Pelta, Measuring the similarity of protein structures by means of the universal similarity metric, Bioinformatics, v.20 n.7, p.1015-1021, May 2004 [doi>10.1093/bioinformatics/bth031]
• 23: M. Li, J. Badger, X. Chen, S. Kwong, P. Kearney, and H. Zhang. An information-based sequence distance and its application to whole mitochondrial genome phylogeny. Bioinformatics, 17(2):149--154, 2001.
• 24: M. Li, X. Chen, X. Li, B. Ma, and P. Vitányi. The similarity metric. IEEE Transactions on Information Theory, 50(12):3250--3264, 2004.
• 25: Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 26: Andrej A. Muchnik, Conditional complexity and codes, Theoretical Computer Science, v.271 n.1-2, p.97-109, January 28, 2002 [doi>10.1016/S0304-3975(01)00033-0]
• 27: Andrei A. Muchnik , Nikolai K. Vereshchagin, Logical Operations and Kolmogorov Complexity II, Proceedings of the 16th Annual Conference on Computational Complexity, p.256, June 18-21, 2001
• 28: M. Nykter, N. Price, M. Aldana, S. Ramsey, S. Kauffman, L. Hood, O. Yli-Harja, and I. Shmulevich. Gene expression dynamic in the macrophage exhibit criticality. PNAS, 105(6):1897--1900, 2008.
• 29: M. Nykter, N. Price, A. Larjo, T. Aho, S. Kauffman, O. Yli-Harja, and I. Shmulevich. Critical networks exhibit maximal information diversity in structure-dynamics relationships. Physical Review Letters, 100:058702 (1-4), 2008.
• 30: H. Otu and K. Sayood. A new sequence distance measure for phylogenetic tree construction. Bioinformatics, 19(6):2122--2130, 2003.
• 31: H. Pao and J. Case. Computing entropy for ortholog detection. In International Conference on Computational Intelligence, December 2004.
• 32: D. Parry. Use of Kolmogorov distance identification of web page authorship, topic and domain. In Workshop on Open Source Web Inf. Retrieval, 2005.
• 33: Ana-Maria Popescu , Oren Etzioni, Extracting product features and opinions from reviews, Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, p.339-346, October 06-08, 2005, Vancouver, British Columbia, Canada [doi>10.3115/1220575.1220618]
• 34: S. Rahmati and J. Glasgow. Noise tolerance of universal similarity metric applied to protein contact maps comparison in two dimensions. manuscript, Queen Univ, 2008.
• 35: C. Costa Santos , J. Bernardes , P. M. B. Vitanyi , L. Antunes, Clustering Fetal Heart Rate Tracings by Compression, Proceedings of the 19th IEEE Symposium on Computer-Based Medical Systems, p.685-690, June 22-23, 2006 [doi>10.1109/CBMS.2006.68]
• 36: Alexander Shen , Nikolai Vereshchagin, Logical operations and Kolmogorov complexity, Theoretical Computer Science, v.271 n.1-2, p.125-129, January 28, 2002 [doi>10.1016/S0304-3975(01)00035-4]
• 37: Arno Siebes , Zbigniew R. Struzik, Complex Data: Mining Using Patterns, Proceedings of the ESF Exploratory Workshop on Pattern Detection and Discovery, p.24-35, September 16-19, 2002
• 38: W. Taha, S. Crosby, and K. Swadi. A new approach to data mining for software design. manuscript, Rice Univ, 2006.
• 39: Pang-Ning Tan , Vipin Kumar , Jaideep Srivastava, Selecting the right interestingness measure for association patterns, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775053]
• 40: Nikolai K. Vereshchagin , Michael V. Vyugin, Independent minimum length programs to translate between given strings, Theoretical Computer Science, v.271 n.1-2, p.131-143, January 28, 2002 [doi>10.1016/S0304-3975(01)00036-6]
• 41: Mikhail V. Vyugin, Information distance and conditional complexities, Theoretical Computer Science, v.271 n.1-2, p.145-150, January 28, 2002 [doi>10.1016/S0304-3975(01)00037-8]
• 42: Xian Zhang , Yu Hao , Xiaoyan Zhu , Ming Li , David R. Cheriton, Information distance from a question to an answer, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281285]
• 43: Li Zhuang , Feng Jing , Xiao-Yan Zhu, Movie review mining and summarization, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183625]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing
          Subjects: Text analysis

General Terms:
Theory

Keywords:
data mining, information distance, kolmogorov complexity, text mining