Page-level template detection via isotonic smoothing

ABSTRACT

We develop a novel framework for the page-level template detection problem. Our framework is built on two main ideas. The first is theautomatic generation of training data for a classifier that, given apage, assigns a templateness score to every DOM node of the page. The second is the global smoothing of these per-node classifier scores bysolving a regularized isotonic regression problem; the latter follows from a simple yet powerful abstraction of templateness on a page. Our extensive experiments on human-labeled test data show that our approachdetects templates effectively.

REFERENCES

• 1: Stanislav Angelov , Boulos Harb , Sampath Kannan , Li-San Wang, Weighted isotonic regression under the L₁ norm, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.783-791, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109643]
• 2: Shumeet Baluja, Browsing on small screens: recasting web-page segmentation into an efficient machine learning framework, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135788]
• 3: Ziv Bar-Yossef , Sridhar Rajagopalan, Template detection via data mining and its applications, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511522]
• 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: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Computer Networks and ISDN Systems, v.29 n.8-13, p.1157-1166, Sep. 1997
• 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: Yu Chen , Xing Xie , Wei-Ying Ma , Hong-Jiang Zhang, Adapting Web Pages for Small-Screen Devices, IEEE Internet Computing, v.9 n.1, p.50-56, January 2005 [doi>10.1109/MIC.2005.5]
• 8: Junghoo Cho , Narayanan Shivakumar , Hector Garcia-Molina, Finding replicated Web collections, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.355-366, May 15-18, 2000, Dallas, Texas, United States
• 9: B. Davison. Recognizing nepotistic links on the web. In AAAI-2000 Workshop on Artificial Intelligence for Web Search, pages 23--28, 2000.
• 10: Sandip Debnath , Prasenjit Mitra , Nirmal Pal , C. Lee Giles, Automatic Identification of Informative Sections of Web Pages, IEEE Transactions on Knowledge and Data Engineering, v.17 n.9, p.1233-1246, September 2005 [doi>10.1109/TKDE.2005.138]
• 11: 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]
• 12: L. Hubert and P. Arabie. Comparing partitions. J. Classification, 2:193--218, 1985.
• 13: Hung-Yu Kao , Ming-Syan Chen , Shian-Hua Lin , Jan-Ming Ho, Entropy-based link analysis for mining web informative structures, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584886]
• 14: Hung-Yu Kao , Jan-Ming Ho , Ming-Syan Chen, WISDOM: Web Intrapage Informative Structure Mining Based on Document Object Model, IEEE Transactions on Knowledge and Data Engineering, v.17 n.5, p.614-627, May 2005 [doi>10.1109/TKDE.2005.84]
• 15: Ravi Kumar , Kunal Punera , Andrew Tomkins, Hierarchical topic segmentation of websites, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150433]
• 16: Nicholas Kushmerick, Learning to remove Internet advertisements, Proceedings of the third annual conference on Autonomous Agents, p.175-181, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301186]
• 17: G. Milligan and M. Cooper. A study of the comparability of external criteria for hierarchical cluster analysis. Multivariate Behavioral Research, 21(4):441--458, 1986.
• 18: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 19: T. Morton-Jones, P. Diggle, L. Parker, H.O. Dickinson, and K. Blinks. Additive isotonic regression models in epidemiology. Statistics in Medicine, 19(6):849--859, 2000.
• 20: P.M. Pardalos and G. Xue. Algorithms for a class of isotonic regression problems. Algorithmica, 23(3):211--222, 1999.
• 21: T. Robertson, F.T. Wright, and R.L. Dykstra. Order-Restrictied Statistical Inference. Wiley, 1988.
• 22: Ruihua Song , Haifeng Liu , Ji-Rong Wen , Wei-Ying Ma, Learning block importance models for web pages, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988700]
• 23: Q. Stout. Optimal algorithms for unimodal regression. Computing Science and Statistics, 32:348--355, 2000.
• 24: Karane Vieira , Altigran S. da Silva , Nick Pinto , Edleno S. de Moura , João M. B. Cavalcanti , Juliana Freire, A fast and robust method for web page template detection and removal, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183654]
• 25: L. Yi and B. Liu. Web page cleaning for web mining through feature weighting. In Proc. 18th IJCAI, pages 43--50, 2003.
• 26: Lan Yi , Bing Liu , Xiaoli Li, Eliminating noisy information in Web pages for data mining, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956785]
• 27: Xinyi Yin , Wee Sun Lee, Using link analysis to improve layout on mobile devices, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988718]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
isotonic regression, template detection, webpage sectioning, webpage segmentation