A machine learning based approach for table detection on the web

ABSTRACT

Table is a commonly used presentation scheme, especially for describing relational information. However, table understanding remains an open problem. In this paper, we consider the problem of table detection in web documents. Its potential applications include web mining, knowledge management, and web content summarization and delivery to narrow-bandwidth devices. We describe a machine learning based approach to classify each given table entity as either genuine or non-genuine. Various features reflecting the layout as well as content characteristics of tables are studied.In order to facilitate the training and evaluation of our table classifier, we designed a novel web document table ground truthing protocol and used it to build a large table ground truth database. The database consists of 1,393 HTML files collected from hundreds of different web sites and contains 11,477 leaf TABLE elements, out of which 1,740 are genuine tables. Experiments were conducted using the cross validation method and an F-measure of 95.89% was achieved.

REFERENCES

• 1: Mary Campione , Kathy Walrath , Alison Huml, The Java Tutorial: A Short Course on the Basics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 2: Hsin-Hsi Chen , Shih-Chung Tsai , Jin-He Tsai, Mining tables from large scale HTML texts, Proceedings of the 18th conference on Computational linguistics, p.166-172, July 31-August 04, 2000, Saarbrücken, Germany [doi>10.3115/990820.990845]
• 3: Corinna Cortes , Vladimir Vapnik, Support-Vector Networks, Machine Learning, v.20 n.3, p.273-297, Sept. 1995 [doi>10.1023/A:1022627411411]
• 4: Robert M. Haralick , Linda G. Shapiro, Computer and Robot Vision, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992
• 5: Why Table Ground-Truthing is Hard, Proceedings of the Sixth International Conference on Document Analysis and Recognition, p.129, September 10-13, 2001
• 6: M. Hurst. Layout and language: Challenges for table understanding on the web. In Proc. 1st International Workshop on Web Document Analysis, pages 27--30, Seattle, WA, USA, September 2001.
• 7: Thorsten Joachims, A Probabilistic Analysis of the Rocchio Algorithm with TFIDF for Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.143-151, July 08-12, 1997
• 8: Andrew Kachites McCallum , Kamal Nigam , Jason Rennie , Kristie Seymore, Automating the Construction of Internet Portals with Machine Learning, Information Retrieval, v.3 n.2, p.127-163, July 2000 [doi>10.1023/A:1009953814988]
• 9: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 10: Flexible Web Document Analysis for Delivery to Narrow-Bandwidth Devices, Proceedings of the Sixth International Conference on Document Analysis and Recognition, p.1074, September 10-13, 2001
• 11: M. F. Porter. An algorithm for suffix stripping. Program, 14(3):130--137, 1980.
• 12: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 13: Yiming Yang , Xin Liu, A re-examination of text categorization methods, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.42-49, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312647]
• 14: M. Yoshida, K. Torisawa, and J. Tsujii. A method to integrate tables of the world wide web. In Proc. 1st International Workshop on Web Document Analysis, pages 31--34, Seattle, WA, USA, September 2001.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.3 Communications Applications
          Subjects: Information browsers

General Terms:
Algorithms

Keywords:
decision tree, information retrieval, layout analysis, machine learning, support vector machine, table detection