A new suffix tree similarity measure for document clustering

ABSTRACT

In this paper, we propose a new similarity measure to compute the pairwise similarity of text-based documents based on suffix tree document model. By applying the new suffix tree similarity measure in Group-average Agglomerative Hierarchical Clustering (GAHC) algorithm, we developed a new suffix tree document clustering algorithm (NSTC). Experimental results on two standard document clustering benchmark corpus OHSUMED and RCV1 indicate that the new clustering algorithm is a very effective document clustering algorithm. Comparing with the results of traditional word term weight tf-idf similarity measure in the same GAHC algorithm, NSTC achieved an improvement of 51% on the average of F-measure score. Furthermore, we apply the new clustering algorithm in analyzing the Web documents in online forum communities. A topic oriented clustering algorithm is developed to help people in assessing, classifying and searching the the Web documents in a large forum community.

REFERENCES

• 1: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 2: Eugene Charniak, Statistical Language Learning, MIT Press, Cambridge, MA, 1994
• 3: W. B. Croft. Organizing and searching large files of documents. PhD thesis, University of Cambridge, 1978.
• 4: David D. Lewis , Yiming Yang , Tony G. Rose , Fan Li, RCV1: A New Benchmark Collection for Text Categorization Research, The Journal of Machine Learning Research, 5, p.361-397, 12/1/2004
• 5: A. Ehrenfeucht , D. Haussler, A new distance metric on strings computable in linear time, Discrete Applied Mathematics, v.20 n.3, p.191-203, July, 1988 [doi>10.1016/0166-218X(88)90076-5]
• 6: R. Giegerich and S. Kurtz. From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction. Algorithmica, 19(3):331--353, 1997.
• 7: Khaled M. Hammouda , Mohamed S. Kamel, Efficient Phrase-Based Document Indexing for Web Document Clustering, IEEE Transactions on Knowledge and Data Engineering, v.16 n.10, p.1279-1296, October 2004 [doi>10.1109/TKDE.2004.58]
• 8: X. D. Hung Chim, Min Jiang. A semantics based information distribution framework for large web-based course forum system. Lecture Notes in Computer Science: Advances in Web Based Learning ICWL 2006, 4181/2006:93--104, 2006.
• 9: Frederick Jelinek, Statistical methods for speech recognition, MIT Press, Cambridge, MA, 1998
• 10: Bjornar Larsen , Chinatsu Aone, Fast and effective text mining using linear-time document clustering, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.16-22, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312186]
• 11: Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, SIAM Journal on Computing, v.22 n.5, p.935-948, Oct. 1993 [doi>10.1137/0222058]
• 12: D. K. O'Neill and L. M. Gomez. The collaboratory notebook: A distributed knowledge-building environment for project-enhanced learning. In Proceedings of Ed-Meida'94, Vancouver, BC, 1994.
• 13: O. M. Oren Zamir, Oren Etzioni and R. M. Karp. Fast and intuitive clustering of web documents. In Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining, 1997.
• 14: J. R. Paul Bieganski and J. V. Carlis. Generalized suffix trees for biological sequence data: Application and implentation. In Proceedings of 27th Annual Hawaii International Conference on System Sciences, pages 35--44, 1994.
• 15: M. Porter. New models in probabilistic information retrieval. British Library Research and Development Report, no. 5587, 1980.
• 16: Robert B. Allen , Pascal Obry , Michael Littman, An interface for navigating clustered document sets returned by queries, Proceedings of the conference on Organizational computing systems, p.166-171, November 01-04, 1993, Milpitas, California, United States [doi>10.1145/168555.168572]
• 17: Rajesh Pampapathi , Boris Mirkin , Mark Levene, A suffix tree approach to anti-spam email filtering, Machine Learning, v.65 n.1, p.309-338, October 2006 [doi>10.1007/s10994-006-9505-y]
• 18: G. Salton , C. Buckley, On the use of spreading activation methods in automatic information, Proceedings of the 11th annual international ACM SIGIR conference on Research and development in information retrieval, p.147-160, May 1988, Grenoble, France [doi>10.1145/62437.62447]
• 19: 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]
• 20: D. S. Sven Meyer zu Eissen and M. Potthast. The suffix tree document model revisited. In Proceedings of the 5th International Conference on Knowledge Management, pages 596--603, 2005.
• 21: E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249--260, 1995.
• 22: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 23: Peter Willett, Recent trends in hierarchic document clustering: a critical review, Information Processing and Management: an International Journal, v.24 n.5, p.577-597, 1988 [doi>10.1016/0306-4573(88)90027-1]
• 24: William Hersh , Chris Buckley , T. J. Leone , David Hickam, OHSUMED: an interactive retrieval evaluation and new large test collection for research, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.192-201, July 03-06, 1994, Dublin, Ireland
• 25: Mikio Yamamoto , Kenneth W. Church, Using suffix arrays to compute term frequency and document frequency for all substrings in a corpus, Computational Linguistics, v.27 n.1, p.1-30, March 2001 [doi>10.1162/089120101300346787]
• 26: Oren Zamir , Oren Etzioni, Web document clustering: a feasibility demonstration, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.46-54, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290956]
• 27: Oren Zamir , Oren Etzioni, Grouper: a dynamic clustering interface to Web search results, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1361-1374, May 17, 1999

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Linguistic processing

General Terms:
Algorithms, Experimentation

Keywords:
document model, similarity measure, suffix tree