Frequent term-based text clustering

ABSTRACT

Text clustering methods can be used to structure large sets of text or hypertext documents. The well-known methods of text clustering, however, do not really address the special problems of text clustering: very high dimensionality of the data, very large size of the databases and understandability of the cluster description. In this paper, we introduce a novel approach which uses frequent item (term) sets for text clustering. Such frequent sets can be efficiently discovered using algorithms for association rule mining. To cluster based on frequent term sets, we measure the mutual overlap of frequent sets with respect to the sets of supporting documents. We present two algorithms for frequent term-based text clustering, FTC which creates flat clusterings and HFTC for hierarchical clustering. An experimental evaluation on classical text documents as well as on web documents demonstrates that the proposed algorithms obtain clusterings of comparable quality significantly more efficiently than state-of-the- art text clustering algorithms. Furthermore, our methods provide an understandable description of the discovered clusters by their frequent term sets.

REFERENCES

• 1: Soumen Chakrabarti, Data mining for hypertext: a tutorial survey, ACM SIGKDD Explorations Newsletter, v.1 n.2, January 2000 [doi>10.1145/846183.846187]
• 2: Douglass R. Cutting , David R. Karger , Jan O. Pedersen , John W. Tukey, Scatter/Gather: a cluster-based approach to browsing large document collections, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.318-329, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133214]
• 3: 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]
• 4: Steinbach M., Karypis G., Kumar V.: A Comparison of Document Clustering Techniques, Proc. TextMining Workshop, KDD 2000, 2000.
• 5: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 6: Kaufman L., Rousseeuw P.J.: Finding Groups in Data: An Introduction to Cluster Analysis, John Wiley & Sons, 1990.
• 7: 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]
• 8: Jochen Hipp , Ulrich Güntzer , Gholamreza Nakhaeizadeh, Algorithms for association rule mining — a general survey and comparison, ACM SIGKDD Explorations Newsletter, v.2 n.1, p.58-64, June, 2000 [doi>10.1145/360402.360421]
• 9: Liu B., Hsu W., Ma Y.: Integrating Classification and Association Rule Mining, Proc. KDD 98, pp. 80--86.
• 10: Osmar R. Zaïane , Maria-Luiza Antonie, Classifying text documents by associating terms with text categories, Proceedings of the thirteenth Australasian database conference, p.215-222, January 01, 2002, Melbourne, Victoria, Australia
• 11: Yibin S.: An implementation of the Apriori algorithm, <u>http://www.cs.uregina.ca/~dbd/cs831/notes/itemsets/dic.java</u>, 2000.
• 12: Eui-Hong Han , Daniel Boley , Maria Gini , Robert Gross , Kyle Hastings , George Karypis , Vipin Kumar , Bamshad Mobasher , Jerome Moore, WebACE: a Web agent for document categorization and exploration, Proceedings of the second international conference on Autonomous agents, p.408-415, May 10-13, 1998, Minneapolis, Minnesota, United States [doi>10.1145/280765.280872]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Textual databases

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
clustering, frequent item sets, text documents