Hierarchical topic segmentation of websites

ABSTRACT

In this paper, we consider the problem of identifying and segmenting topically cohesive regions in the URL tree of a large website. Each page of the website is assumed to have a topic label or a distribution on topic labels generated using a standard classifier. We develop a set of cost measures characterizing the benefit accrued by introducing a segmentation of the site based on the topic labels. We propose a general framework to use these measures for describing the quality of a segmentation; we also provide an efficient algorithm to find the best segmentation in this framework. Extensive experiments on human-labeled data confirm the soundness of our framework and suggest that a judicious choice of cost measures allows the algorithm to perform surprisingly accurate topical segmentations.

REFERENCES

• 1: Rakesh Agrawal , Sridhar Rajagopalan , Ramakrishnan Srikant , Yirong Xu, Mining newsgroups using networks arising from social behavior, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775227]
• 2: D. J. Aumueller. A tool for gathering, analysing, exporting, and visualizing the structure of a website. Master's thesis, University of Leeds, Institute of Communications Studies, 2003.
• 3: Arindam Banerjee , Inderjit S. Dhillon , Joydeep Ghosh , Suvrit Sra, Clustering on the Unit Hypersphere using von Mises-Fisher Distributions, The Journal of Machine Learning Research, 6, p.1345-1382, 9/1/2005
• 4: Krishna Bharat , Andrei Broder , Jeffrey Dean , Monika R. Henzinger, A comparison of techniques to find mirrored hosts on the WWW, Journal of the American Society for Information Science, v.51 n.12, p.1114-1122, Oct. 2000 [doi>10.1002/1097-4571(2000)9999:9999<::AID-ASI1025>3.0.CO;2-0]
• 5: David M. Blei , Michael I. Jordan, Modeling annotated data, 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.860460]
• 6: 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
• 7: L. M. Collins and C. W. Dent. Omega: A general formulation of the rand index of cluster recovery suitable for non-disjoint solutions. Multivariate Behavioral Research, 23(2):231--242, 1988.
• 8: Nick Craswell , David Hawking , Stephen Robertson, Effective site finding using link anchor information, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.250-257, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383999]
• 9: Ludovic Denoyer , Patrick Gallinari, Bayesian network model for semi-structured document classification, Information Processing and Management: an International Journal, v.40 n.5, p.807-827, September 2004 [doi>10.1016/j.ipm.2004.04.009]
• 10: F. Scarselli, Classification of HTML Documents by Hidden Tree-Markov Models, Proceedings of the Sixth International Conference on Document Analysis and Recognition, p.849, September 10-13, 2001
• 11: Martin Ester , Hans-Peter Kriegel , Matthias Schubert, Web site mining: a new way to spot competitors, customers and suppliers in the world wide web, 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.775084]
• 12: Ronald Fagin , R. Guha , Ravi Kumar , Jasmine Novak , D. Sivakumar , Andrew Tomkins, Multi-structural databases, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065191]
• 13: R. Fagin , Ph. Kolaitis , R. Kumar , J. Novak , D. Sivakumar , A. Tomkins, Efficient implementation of large-scale multi-structural databases, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 14: Shai Fine , Yoram Singer , Naftali Tishby, The Hierarchical Hidden Markov Model: Analysis and Applications, Machine Learning, v.32 n.1, p.41-62, July 1998 [doi>10.1023/A:1007469218079 ]
• 15: David Gibson, Surfing the web by site, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA [doi>10.1145/1013367.1013543]
• 16: David Gibson , Kunal Punera , Andrew Tomkins, The volume and evolution of web page templates, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062763]
• 17: W. L. Hsu. The distance-domination numbers of trees. Operations Research Letters, 1:96--100, 1982.
• 18: Sepandar D. Kamvar , Mario T. Schlosser , Hector Garcia-Molina, The Eigentrust algorithm for reputation management in P2P networks, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775242]
• 19: O. Kariv and S. L. Haikim. An algorithmic approach to network location problems, part II: p-medians. SIAM J. on Applied Mathematics, 37:539--560, 1979.
• 20: Daphne Koller , Mehran Sahami, Hierarchically Classifying Documents Using Very Few Words, Proceedings of the Fourteenth International Conference on Machine Learning, p.170-178, July 08-12, 1997
• 21: H.-P. Kriegel and M. Schubert. Classification of websites as sets of feature vectors. In IASTED Intl. Conf. on Databases and Applications, pages 127--132, 2004.
• 22: J. Pierre. Practical issues for automated categorization of web sites. In ECDL 2000 Workshop on Semantic Web, 2000.
• 23: B. Piwowarski, L. Denoyer, and P. Gallinari. Un modèle pour la recherche d'information sur des documents structurés. In 6th Journées internationales d'Analyse statistique des Données Textuelles, 2002.
• 24: J. R. Quinlan. Induction of decision trees. In J. W. Shavlik and T. G. Dietterich, editors, Readings in Machine Learning. Morgan Kaufmann, 1990. Originally in Machine Learning 1:81--106, 1986.
• 25: Filippo Ricca , Paolo Tonella, Web Site Analysis: Structure and Evolution, Proceedings of the International Conference on Software Maintenance (ICSM'00), p.76, October 11-14, 2000
• 26: Uri Schonfeld , Ziv Bar-Yossef , Idit Keidar, Do not crawl in the DUST: different URLs with similar text, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135992]
• 27: Rahul Shah , Martin Farach-Colton, Undiscretized dynamic programming: faster algorithms for facility location and related problems on trees, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.108-115, January 06-08, 2002, San Francisco, California
• 28: Aixin Sun , Ee-Peng Lim, Web unit mining: finding and classifying subgraphs of web pages, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956885]
• 29: A. Tamir. An o(pn2) algorithm for the p-median and related problems on tree graphs. Operations Research Letters, 19:59--64, 1996.
• 30: Loren Terveen , Will Hill , Brian Amento, Constructing, organizing, and visualizing collections of topically related Web resources, ACM Transactions on Computer-Human Interaction (TOCHI), v.6 n.1, p.67-94, March 1999 [doi>10.1145/310641.310644]
• 31: Mike Thelwall , David Wilkinson, Finding similar academic web sites with links, bibliometric couplings and colinks, Information Processing and Management: an International Journal, v.40 n.3, p.515-526, January 2004 [doi>10.1016/S0306-4573(03)00042-6]
• 32: M. Theobald, R. Schenkel, and G. Weikum. Exploiting structure, annotation, and ontological knowledge for automatic classification of XML data. In 6th WebDB, pages 1--6, 2003.
• 33: YongHong Tian , TieJun Huang , Wen Gao , Jun Cheng , PingBo Kang, Two-Phase Web Site Classification Based on Hidden Markov Tree Models, Proceedings of the IEEE/WIC International Conference on Web Intelligence, p.227, October 13-17, 2003

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
KL-distance, classification, facility location, gain ratio, tree partitioning, website hierarchy, website segmentation