Automatic segmentation of text into structured records

ABSTRACT

In this paper we present a method for automatically segmenting unformatted text records into structured elements. Several useful data sources today are human-generated as continuous text whereas convenient usage requires the data to be organized as structured records. A prime motivation is the warehouse address cleaning problem of transforming dirty addresses stored in large corporate databases as a single text field into subfields like “City” and “Street”. Existing tools rely on hand-tuned, domain-specific rule-based systems.

We describe a tool DATAMOLD that learns to automatically extract structure when seeded with a small number of training examples. The tool enhances on Hidden Markov Models (HMM) to build a powerful probabilistic model that corroborates multiple sources of information including, the sequence of elements, their length distribution, distinguishing words from the vocabulary and an optional external data dictionary. Experiments on real-life datasets yielded accuracy of 90% on Asian addresses and 99% on US addresses. In contrast, existing information extraction methods based on rule-learning techniques yielded considerably lower accuracy.

REFERENCES

• 1: Brad Adelberg, NoDoSE—a tool for semi-automatically extracting structured and semistructured data from text documents, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.283-294, June 01-04, 1998, Seattle, Washington, United States
• 2: Arnaud Sahuguet , Fabien Azavant, Building Light-Weight Wrappers for Legacy Web Data-Sources Using W4F, Proceedings of the 25th International Conference on Very Large Data Bases, p.738-741, September 07-10, 1999
• 3: TheaterLoc: Using Information Integration Technology to Rapidly Build Virtual Applications, Proceedings of the 16th International Conference on Data Engineering, p.681, February 28-March 03, 2000
• 4: Daniel M. Bikel , Scott Miller , Richard Schwartz , Ralph Weischedel, Nymble: a high-performance learning name-finder, Proceedings of the fifth conference on Applied natural language processing, p.194-201, March 31-April 03, 1997, Washington, DC [doi>10.3115/974557.974586]
• 5: Mary Elaine Califf , Raymond J. Mooney, Relational learning of pattern-match rules for information extraction, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.328-334, July 18-22, 1999, Orlando, Florida, United States
• 6: A. Crespo, J. Jannink, E. Neuhold, M. Rys, and R. Studer. A survey of semi-automatic extraction and transformation. http://www-db.stanford.edu/ crespo/publications/.
• 7: D. W. Embley , Y. Jiang , Y.-K. Ng, Record-boundary discovery in Web documents, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.467-478, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 8: D. Freitag and A. McCallum. Information extraction using HMMs and shrinkage. In Papers from the AAAI-99 Workshop on Machine Learning for Information Extraction, pages 31-36, 1999.
• 9: Dayne Freitag , Andrew McCallum, Information Extraction with HMM Structures Learned by Stochastic Optimization, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.584-589, July 30-August 03, 2000
• 10: H. Galhardas. http://caravel.inria.fr/ galharda/cleaning.html.
• 11: J. Hammer, H. Garcia-Molina, J. Cho, R. Aranha, and A. Crespo. Extracting semistructure information from the web. In Workshop on mangement of semistructured data, 1997.
• 12: Mauricio A. Hernández , Salvatore J. Stolfo, The merge/purge problem for large databases, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.127-138, May 22-25, 1995, San Jose, California, United States
• 13: Chun-Nan Hsu , Ming-Tzung Dung, Generating finite-state transducers for semi-structured data extraction from the Web, Information Systems, v.23 n.9, p.521-538, Dec. 1998
• 14: S. Huffman. Learning information extraction patterns from examples. In S. Wermter, G. Scheler, and E. Riloff, editors, Proceedings of the 1995 IJCAI Workshop on New Approaches to Learning for Natural Language Processing., 1995.
• 15: Ralph Kimball, Dealing with dirty data, DBMS, v.9 n.10, p.55-60, Sept. 1996
• 16: J. Kupiec. Robust part of speech tagging using a hidden Markov model. Computer Speech and Language, 6:225-242, 1992.
• 17: N. Kushmerick, D. Weld, and R. Doorenbos. Wrapper induction for information extraction. In Proceedings of IJCAI, 1997.
• 18: P.-S. Laplace. Philosophical Essays on Probabilities. Springer-Verlag, New York, 1995. Translated by A. I. Dale from the 5th French edition of 1825.
• 19: Steve Lawrence , C. Lee Giles , Kurt Bollacker, Digital Libraries and Autonomous Citation Indexing, Computer, v.32 n.6, p.67-71, June 1999 [doi>10.1109/2.769447]
• 20: XWRAP: An XML-Enabled Wrapper Construction System for Web Information Sources, Proceedings of the 16th International Conference on Data Engineering, p.611, February 28-March 03, 2000
• 21: Andrew McCallum , Dayne Freitag , Fernando C. N. Pereira, Maximum Entropy Markov Models for Information Extraction and Segmentation, Proceedings of the Seventeenth International Conference on Machine Learning, p.591-598, June 29-July 02, 2000
• 22: G. Mecca, P. Merialdo, and P. Atzeni. Araneus in the era of xml. In IEEE Data Engineering Bullettin, Special Issue on XML. IEEE, September 1999.
• 23: A. E. Monge and C. P. Elkan. The field matching problem: Algorithms and applications. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96), 1996.
• 24: I. Muslea. Extraction patterns for information extraction tasks: A survey. In The AAAI-99 Workshop on Machine Learning for Information Extraction, 1999.
• 25: Ion Muslea , Steve Minton , Craig Knoblock, A hierarchical approach to wrapper induction, Proceedings of the third annual conference on Autonomous Agents, p.190-197, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301191]
• 26: L. Rabiner. A tutorial on Hidden Markov Models and selected applications in speech recognition. In Proceedings of the IEEE, 77(2), 1989.
• 27: Lawrence Rabiner , Biing-Hwang Juang, Fundamentals of speech recognition, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 28: K. Seymore, A. McCallum, and R. Rosenfeld. Learning Hidden Markov Model structure for information extraction. In Papers from the AAAI-99 Workshop on Machine Learning for Information Extraction, pages 37-42, 1999.
• 29: Stephen Soderland, Learning Information Extraction Rules for Semi-Structured and Free Text, Machine Learning, v.34 n.1-3, p.233-272, Feb. 1999 [doi>10.1023/A:1007562322031]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Abstracting methods

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION

General Terms:
Design, Documentation, Experimentation, Management, Measurement, Performance, Theory