Measuring text similarity with dynamic time warping

ABSTRACT

In this work, we describe an approach which aims to make typed texts comparable with temporal data mining methods. This proposal was made in earlier work [11], but to our knowledge no significant research on this subject has been done yet. The basic idea is to derive artificial time series from texts by counting the occurrences of relevant keywords in a sliding window applied to them, and these time series can be compared with techniques of time series analysis. In this particular case the Dynamic Time Warping distance [3] was used. By extensive testing adequate parameters for time series calculation were derived, and we show that this approach might aid in the recognition of similar texts since the observed distances between similar documents are significantly lower than those between unrelated texts. Our idea might also be especially suitable for comparison in different languages since only the keyword translations must be known.

REFERENCES

• 1: Rakesh Agrawal , King-Ip Lin , Harpreet S. Sawhney , Kyuseok Shim, Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.490-501, September 11-15, 1995
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: D. J. Berndt and J. Clifford. Using dynamic time warping to find patterns in time series. In KDD Workshop, pages 359--370, 1994.
• 4: S. Chu, E. Keogh, D. Hart, and M. Pazzani. Iterative deepening dynamic time warping for time series. In In Proc 2 na SIAM International Conference on Data Mining, 2002.
• 5: P. Iyer and A. Singh. Document similarity analysis for a plagiarism detection system. In IICAI, pages 2534--2544, 2005.
• 6: Eamonn J. Keogh , Michael J. Pazzani, Scaling up dynamic time warping for datamining applications, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.285-289, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347153]
• 7: E. Keogh and M. Pazzani. Derivative dynamic time warping. In First SIAM International Conference on Data Mining, (Chicago, IL)., 2001.
• 8: Thomas Lancaster , Fintan Culwin, Towards an error free plagarism detection process, ACM SIGCSE Bulletin, v.33 n.3, p.57-60, Sept. 2001
• 9: Chi-Hong Leung , Yuen-Yan Chan, A natural language processing approach to automatic plagiarism detection, Proceedings of the 8th ACM SIGITE conference on Information technology education, October 18-20, 2007, Destin, Florida, USA [doi>10.1145/1324302.1324348]
• 10: M. Matuschek. Temporal Aspects in Data Mining (Master Thesis). Heinrich-Heine-Universität, Düsseldorf, 2008.
• 11: C. Ratanamahatana and E. Keogh. Everything you know about dynamic time warping is wrong. In Third Workshop on Mining Temporal and Sequential Data, in conjunction with the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2004), 2004.
• 12: T. Rath and R. Manmatha. Word image matching using dynamic time warping. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR '03), 2003.
• 13: Hiroaki Sakoe , Seibi Chiba, Dynamic programming algorithm optimization for spoken word recognition, Readings in speech recognition, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 14: G. Salton , A. Wong , C. S. Yang, A vector space model for automatic indexing, Communications of the ACM, v.18 n.11, p.613-620, Nov. 1975 [doi>10.1145/361219.361220]
• 15: Stan Salvador , Philip Chan, Toward accurate dynamic time warping in linear time and space, Intelligent Data Analysis, v.11 n.5, p.561-580, October 2007
• 16: Junji Tomita , Hidekazu Nakawatase , Megumi Ishii, Calculating similarity between texts using graph-based text representation model, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031226]
• 17: Daniel R. White , Mike S. Joy, Sentence-based natural language plagiarism detection, Journal on Educational Resources in Computing (JERIC), v.4 n.4, p.2-es, December 2004 [doi>10.1145/1086339.1086341]
• 18: X. Xi, E. Keogh, L. Wei, and A. Mafra-Neto. Finding motifs in a database of shapes. In SDM, 2007.
• 19: Manuel Zini , Marco Fabbri , Massimo Moneglia , Alessandro Panunzi, Plagiarism Detection through Multilevel Text Comparison, Proceedings of the Second International Conference on Automated Production of Cross Media Content for Multi-Channel Distribution, p.181-185, December 13-15, 2006 [doi>10.1109/AXMEDIS.2006.40]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing

Keywords:
data mining, databases and information retrieval, dynamic time warping, pseudo time series, text comparison, text databases and digital libraries