A comparative evaluation of different link types on enhancing document clustering

ABSTRACT

With a growing number of works utilizing link information in enhancing document clustering, it becomes necessary to make a comparative evaluation of the impacts of different link types on document clustering. Various types of links between text documents, including explicit links such as citation links and hyperlinks, implicit links such as co-authorship links, and pseudo links such as content similarity links, convey topic similarity or topic transferring patterns, which is very useful for document clustering. In this study, we adopt a Relaxation Labeling (RL)-based clustering algorithm, which employs both content and linkage information, to evaluate the effectiveness of the aforementioned types of links for document clustering on eight datasets. The experimental results show that linkage is quite effective in improving content-based document clustering. Furthermore, a series of interesting findings regarding the impacts of different link types on document clustering are discovered through our experiments.

REFERENCES

• 1: Ralitsa Angelova , Gerhard Weikum, Graph-based text classification: learn from your neighbors, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148254]
• 2: Ralitsa Angelova , Stefan Siersdorfer, A neighborhood-based approach for clustering of linked document collections, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183726]
• 3: Soumen Chakrabarti , Byron Dom , Piotr Indyk, Enhanced hypertext categorization using hyperlinks, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.307-318, June 01-04, 1998, Seattle, Washington, United States
• 4: Cohn, D. and Hofmann,T. The missing link - a probabilistic model of document content and hypertext connectivity. In NIPS 13, 2001.
• 5: D. Eppstein, Finding the k shortest paths, Proceedings of the Proceedings 35th Annual Symposium on Foundations of Computer Science, p.154-165, November 20-22, 1994 [doi>10.1109/SFCS.1994.365697]
• 6: Erkan, G., Radev, D.R.: LexRank: Graph-based Lexical Centrality as Salience in Text Summarization. J. Artif. Intell. Res. (JAIR) 22: 457--479 (2004)
• 7: Rayid Ghani , Seán Slattery , Yiming Yang, Hypertext Categorization using Hyperlink Patterns and Meta Data, Proceedings of the Eighteenth International Conference on Machine Learning, p.178-185, June 28-July 01, 2001
• 8: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 9: Maria Halkidi , Benjamin Nguyen , Iraklis Varlamis , Michalis Vazirgiannis, THESUS: Organizing Web document collections based on link semantics, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.4, p.320-332, November 2003 [doi>10.1007/s00778-003-0100-6]
• 10: He, X., Zha, H, Ding, C. and Simon, H. Web document clustering using hyperlink structures, Tech. Rep. CSE-01-006, Dept. of CS and Eng., Pennsylvania State University, 2001.
• 11: John D. Lafferty , Andrew McCallum , Fernando C. N. Pereira, Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, Proceedings of the Eighteenth International Conference on Machine Learning, p.282-289, June 28-July 01, 2001
• 12: Pelkowitz, L. A continuous relaxation labeling algorithm for markov random fields. IEEE transactions on Systems, Man and Cybernetics, Vol 20 No.3:709--715, 1990.
• 13: Lu,Q. and Getoor, L. Link-based classification. ICML, 2003.
• 14: Andrew McCallum , Kamal Nigam , Jason Rennie , Kristie Seymore, A Machine Learning Approach to Building Domain-Specific Search Engines, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.662-667, July 31-August 06, 1999
• 15: Filippo Menczer, Lexical and semantic clustering by web links, Journal of the American Society for Information Science and Technology, v.55 n.14, p.1261-1269, December 2004 [doi>10.1002/asi.20081]
• 16: Dharmendra S. Modha , W. Scott Spangler, Clustering hypertext with applications to web searching, Proceedings of the eleventh ACM on Hypertext and hypermedia, p.143-152, May 30-June 03, 2000, San Antonio, Texas, United States [doi>10.1145/336296.336351]
• 17: Hyo-Jung Oh , Sung Hyon Myaeng , Mann-Ho Lee, A practical hypertext catergorization method using links and incrementally available class information, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.264-271, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345594]
• 18: Page, L., Brin,S., Motwani, R., and Winograd,T. The PageRank citation ranking: Bringing order to the Web. Technical report, 1998.
• 19: Seán Slattery , Tom M. Mitchell, Discovering Test Set Regularities in Relational Domains, Proceedings of the Seventeenth International Conference on Machine Learning, p.895-902, June 29-July 02, 2000
• 20: Strehl, A., Ghosh, J. andMooney, R. J. Impact of similarity measures on web-page clustering. In AAAI Workshop, 2000.
• 21: Yitong Wang , Masaru Kitsuregawa, Evaluating contents-link coupled web page clustering for web search results, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584875]
• 22: Ron Weiss , Bienvenido Vélez , Mark A. Sheldon, HyPursuit: a hierarchical network search engine that exploits content-link hypertext clustering, Proceedings of the the seventh ACM conference on Hypertext, p.180-193, March 16-20, 1996, Bethesda, Maryland, United States [doi>10.1145/234828.234846]
• 23: Xiaodan Zhang , Xiaohua Zhou , Xiaohua Hu, Semantic Smoothing for Model-based Document Clustering, Proceedings of the Sixth International Conference on Data Mining, p.1193-1198, December 18-22, 2006 [doi>10.1109/ICDM.2006.142]
• 24: Zhao, Y. and Karypis, G. Criterion functions for document clustering: experiments and analysis, Technical Report, Department of Computer Science, Univ. of Minnesota, 2001
• 25: Zhou X., Zhang X. and Hu X., Semantic Smoothing of Document Models for Agglomerative Clustering, IJCAI 2007, 2922--2927.
• 26: Xiaohua Zhou , Xiaodan Zhang , Xiaohua Hu, Dragon Toolkit: Incorporating Auto-Learned Semantic Knowledge into Large-Scale Text Retrieval and Mining, Proceedings of the 19th IEEE International Conference on Tools with Artificial Intelligence - Vol.2 (ICTAI 2007), p.197-201, October 29-31, 2007 [doi>10.1109/ICTAI.2007.90]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
link-based clustering, markov random field, relaxation labeling