A new efficient probabilistic model for mining labeled ordered trees

ABSTRACT

Mining frequent patterns is a general and important issue in data mining. Complex and unstructured (or semi-structured) datasets have appeared in major data mining applications, including text mining, web mining and bioinformatics. Mining patterns from these datasets is the focus of many of the current data mining approaches. We focus on labeled ordered trees, typical datasets of semi-structured data in data mining, and propose a new probabilistic model and its efficient learning scheme for mining labeled ordered trees. The proposed approach significantly improves the time and space complexity of an existing probabilistic modeling for labeled ordered trees, while maintaining its expressive power. We evaluated the performance of the proposed model, comparing it with that of the existing model, using synthetic as well as real datasets from the field of glycobiology. Experimental results showed that the proposed model drastically reduced the computation time of the competing model, keeping the predictive power and avoiding overfitting to the training data. Finally, we assessed our results using the proposed model on real data from a variety of biological viewpoints, verifying known facts in glycobiology.

REFERENCES

• 1: Serge Abiteboul , Peter Buneman , Dan Suciu, Data on the Web: from relations to semistructured data and XML, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 2: Kiyoko F. Aoki , Nobuhisa Ueda , Atsuko Yamaguchi , Tatsuya Akutsu , Minoru Kanehisa , Hiroshi Mamitsuka, Managing and analyzing carbohydrate data, ACM SIGMOD Record, v.33 n.2, June 2004 [doi>10.1145/1024694.1024700]
• 3: E. Baum and T. Petrie. Statistical inference for probabilistic functions of infinite state Markov chains. Ann. Math. Stat., 37:1554--1563, 1966.
• 4: S. Chakrabarti. Mining the Web: Analysis of Hypertext and Semi Structured Data. Morgan Kaufmann, 2002.
• 5: A. Dempster, N. Laird, and D. Rubin. Maximum likelihood from incomplete data via the EM algorithm. J. Royal Stat. Soc., B, 39:1--38, 1977.
• 6: Michelangelo Diligenti , Paolo Frasconi , Marco Gori, Hidden Tree Markov Models for Document Image Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.4, p.519-523, April 2003
• 7: David J. Hand , Robert J. Till, A Simple Generalisation of the Area Under the ROC Curve for Multiple Class Classification Problems, Machine Learning, v.45 n.2, p.171-186, November 2001 [doi>10.1023/A:1010920819831]
• 8: J. A. Hanley and B. J. McNeil. The meaning and use of the area under a receiver operating characteristic (ROC) curve. Radiology, 143:29--36, 1982.
• 9: K. Hashimoto, S. Goto, S. Kawano, K. Aoki-Kinoshita, N. Ueda, M. Hamajima, T. Kawasaki, and M. Kanehisa. KEGG as a glycome informatics resource. Glycobiology, 16(5):63R--70R, 2005.
• 10: M. Kanehisa, S. Goto, M. Hattori, K. F. Aoki-Kinoshita, M. Itoh, S. Kawashima, T. Katayama, M. Araki, and M. Hirakawa. From genomics to chemical genomics: New developments in KEGG. Nucl. Acids Res., 34:D354--D357, 2006.
• 11: Hisashi Kashima , Teruo Koyanagi, Kernels for Semi-Structured Data, Proceedings of the Nineteenth International Conference on Machine Learning, p.291-298, July 08-12, 2002
• 12: K. Lari and S. J. Young. The estimation of stochastic context-free grammars using the inside-outside algorithm. Computer Speech and Language, 4:35--56, 1990.
• 13: S. L. Lauritzen and D. J. Spiegelhalter. Local computations with probabilities on graphical structures and their application to expert systems (with discussion). J. Royal Stat. Soc. B, 50(2):157--224, 1988.
• 14: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 15: G. J. McLachlan and T. Krishnan. The EM Algorithm and Extensions. Wiley-Interscience, 1996.
• 16: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 17: L. R. Rabiner and B. H. Juang. An introduction to hidden Markov models. IEEE ASSP Magazine, 3(1):4--16, 1986.
• 18: N. Ueda, K. F. Aoki, and H. Mamitsuka. A general probabilistic framework for mining labeled ordered trees. In Proc. Fourth SDM, pages 357--368, 2004.
• 19: Nobuhisa Ueda , Kiyoko F. Aoki-Kinoshita , Atsuko Yamaguchi , Tatsuya Akutsu , Hiroshi Mamitsuka, A Probabilistic Model for Mining Labeled Ordered Trees: Capturing Patterns in Carbohydrate Sugar Chains, IEEE Transactions on Knowledge and Data Engineering, v.17 n.8, p.1051-1064, August 2005 [doi>10.1109/TKDE.2005.117]
• 20: A. Varki, R. Cummings, J. Esko, H. Freeze, G. Hart, and J. Marth, editors. Essentials of Glycobiology. Cold Spring Harbor Laboratory Press, New York, 1999.
• 21: Sholom Weiss , Nitin Indurkhya , Tong Zhang , Fred Damerau, Text Mining: Predictive Methods for Analyzing Unstructured Information, SpringerVerlag, 2004
• 22: Mohammed J. Zaki , Charu C. Aggarwal, XRules: an effective structural classifier for XML data, 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.956787]
• 23: Mohammed J. Zaki, Efficiently Mining Frequent Trees in a Forest: Algorithms and Applications, IEEE Transactions on Knowledge and Data Engineering, v.17 n.8, p.1021-1035, August 2005 [doi>10.1109/TKDE.2005.125]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Parameter learning
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

General Terms:
Algorithms, Experimentation

Keywords:
expectation - maximization, labeled ordered trees, maximum likelihood, probabilistic models