A practical web-based approach to generating topic hierarchy for text segments

ABSTRACT

It is crucial in many information systems to organize short text segments, such as keywords in documents and queries from users, into a well-formed topic hierarchy. In this paper, we address the problem of generating topic hierarchies for diverse text segments with a general and practical approach that uses the Web as an additional knowledge source. Unlike long documents, short text segments typically do not contain enough information to extract reliable features. This work investigates the possibilities of using highly ranked search-result snippets to enrich the representation of text segments. A hierarchical clustering algorithm is then applied to create the hierarchical topic structure of text segments. Different from traditional clustering algorithms, which tend to produce cluster hierarchies with a very unnatural shape, the approach tries to produce a more natural and comprehensive hierarchy. Extensive experiments were conducted on different domains of text segments. The obtained results have shown the potential of the proposed approach, which is believed able to benefit many information systems.

REFERENCES

• 1: L. Douglas Baker , Andrew Kachites McCallum, Distributional clustering of words for text classification, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.96-103, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290970]
• 2: Doug Beeferman , Adam Berger, Agglomerative clustering of a search engine query log, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.407-416, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347176]
• 3: Peter F. Brown , Stephen A. Della Pietra , Vincent J. Della Pietra , Robert L. Mercer, Word-sense disambiguation using statistical methods, Proceedings of the 29th annual meeting on Association for Computational Linguistics, p.264-270, June 18-21, 1991, Berkeley, California [doi>10.3115/981344.981378]
• 4: C. Buckley, G. Salton, and J. Allan. Automatic retrieval with locality information using smart. In Proceedings of the First Text REtrieval Conference (TREC-1), pages 59--72, 1992.
• 5: Shui-Lung Chuang , Lee-Feng Chien, Towards Automatic Generation of Query Taxonomy: A Hierarchical Query Clustering Approach, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.75, December 09-12, 2002
• 6: Hang Cui , Min-Yen Kan , Tat-Seng Chua, Unsupervised learning of soft patterns for generating definitions from online news, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988686]
• 7: Inderjit S. Dhillon , Subramanyam Mallela , Rahul Kumar, Enhanced word clustering for hierarchical text classification, 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.775076]
• 8: Chris H. Q. Ding , Xiaofeng He , Hongyuan Zha , Ming Gu , Horst D. Simon, A Min-max Cut Algorithm for Graph Partitioning and Data Clustering, Proceedings of the 2001 IEEE International Conference on Data Mining, p.107-114, November 29-December 02, 2001
• 9: Eric Glover , David M. Pennock , Steve Lawrence , Robert Krovetz, Inferring hierarchical descriptions, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584876]
• 10: Marti A. Hearst , Jan O. Pedersen, Reexamining the cluster hypothesis: scatter/gather on retrieval results, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.76-84, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243216]
• 11: S. Johansson, E. Atwell, R. Garside, and G. Leech. THE TAGGED LOB CORPUS: Users' Manual, 1986.
• 12: 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]
• 13: Dawn Lawrie , W. Bruce Croft , Arnold Rosenberg, Finding topic words for hierarchical summarization, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.349-357, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384022]
• 14: Tao Li , Shenghuo Zhu , Mitsunori Ogihara, Topic hierarchy generation via linear discriminant projection, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860531]
• 15: Bing Liu , Chee Wee Chin , Hwee Tou Ng, Mining topic-specific concepts and definitions on the web, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775188]
• 16: G. W. Milligan and M. C. Cooper. An examination of procedures for detecting the number of clusters in a data set. Psychometrika, 50:159--179, 1985.
• 17: B. Mirkin. Mathematical Classification and Clustering. Kluwer, 1996.
• 18: Adrian Miiller , Jochen Dorre, The TaxGen Framework: Automating the Generation of a Taxonomy for a Large Document Collection, Proceedings of the Thirty-Second Annual Hawaii International Conference on System Sciences-Volume 2, p.2034, January 05-08, 1999
• 19: Fernando Pereira , Naftali Tishby , Lillian Lee, Distributional clustering of English words, Proceedings of the 31st annual meeting on Association for Computational Linguistics, p.183-190, June 22-26, 1993, Columbus, Ohio [doi>10.3115/981574.981598]
• 20: Gerard Salton , Christopher Buckley, Term-weighting approaches in automatic text retrieval, Information Processing and Management: an International Journal, v.24 n.5, p.513-523, 1988 [doi>10.1016/0306-4573(88)90021-0 ]
• 21: Mark Sanderson , Bruce Croft, Deriving concept hierarchies from text, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.206-213, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312679]
• 22: Noam Slonim , Naftali Tishby, Document clustering using word clusters via the information bottleneck method, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.208-215, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345578]
• 23: M. Suan N. M. Semi-automatic taxonomy for efficient information searching. In Proceedings of the 2nd International Conference on Information Technology for Application, 2004.
• 24: D. Sullivan. Document warehousing & content management: Poor search quality in your enterprise information portal? DM Review, January 2002.
• 25: Shivakumar Vaithyanathan , Byron Dom, Model-Based Hierarchical Clustering, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.599-608, June 30-July 03, 2000
• 26: Query clustering using user logs, ACM Transactions on Information Systems (TOIS), v.20 n.1, p.59-81, January 2002 [doi>10.1145/503104.503108]
• 27: 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 ]
• 28: 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]
• 29: Oren Zamir , Oren Etzioni, Grouper: a dynamic clustering interface to Web search results, Proceeding of the eighth international conference on World Wide Web, p.1361-1374, May 1999, Toronto, Canada
• 30: Hua-Jun Zeng , Qi-Cai He , Zheng Chen , Wei-Ying Ma , Jinwen Ma, Learning to cluster web search results, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009030]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.m Miscellaneous

General Terms:
Algorithms, Experimentation, Performance

Keywords:
clustering, partitioning, search-result snippet, text segment, topic hierarchy generation, web data mining