XRules: an effective structural classifier for XML data

ABSTRACT

XML documents have recently become ubiquitous because of their varied applicability in a number of applications. Classification is an important problem in the data mining domain, but current classification methods for XML documents use IR-based methods in which each document is treated as a bag of words. Such techniques ignore a significant amount of information hidden inside the documents. In this paper we discuss the problem of rule based classification of XML data by using frequent discriminatory substructures within XML documents. Such a technique is more capable of finding the classification characteristics of documents. In addition, the technique can also be extended to cost sensitive classification. We show the effectiveness of the method with respect to other classifiers. We note that the methodology discussed in this paper is applicable to any kind of semi-structured data.

REFERENCES

• 1: Charu C. Aggarwal, On effective classification of strings with wavelets, 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.775071]
• 2: C. Aggarwal, S. Gates, P. Yu. On the merits of using supervised clustering to build categorization systems. SIGKDD, 1999.
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 4: K. Alsabti, S. Ranka, V. Singh. CLOUDS: A Decision Tree Classifier for Large Datasets. SIGKDD, 1998.
• 5: R. Andersen et al. Professional XML. Wrox Press Ltd, 2002.
• 6: T. Asai, et al. Efficient substructure discovery from large semi-structured data. 2nd SIAM Int'l Conference on Data Mining, 2002.
• 7: W. W. Cohen. Fast Effective Rule Induction. Int'l Conf. Machine Learning, 1995.
• 8: Pedro Domingos, MetaCost: a general method for making classifiers cost-sensitive, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.155-164, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312220]
• 9: Guozhu Dong , Xiuzhen Zhang , Limsoon Wong , Jinyan Li, CAEP: Classification by Aggregating Emerging Patterns, Proceedings of the Second International Conference on Discovery Science, p.30-42, December 01, 1999
• 10: R. Duda, P. Hart. Pattern Classification and Scene Analysis, Wiley, New York, 1973.
• 11: Johannes Gehrke , Venkatesh Ganti , Raghu Ramakrishnan , Wei-Yin Loh, BOAT—optimistic decision tree construction, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.169-180, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 12: Mike James, Classification algorithms, Wiley-Interscience, New York, NY, 1985
• 13: Wenmin Li , Jiawei Han , Jian Pei, CMAR: Accurate and Efficient Classification Based on Multiple Class-Association Rules, Proceedings of the 2001 IEEE International Conference on Data Mining, p.369-376, November 29-December 02, 2001
• 14: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 15: Rajeev Rastogi , Kyuseok Shim, PUBLIC: A Decision Tree Classifier that Integrates Building and Pruning, Proceedings of the 24rd International Conference on Very Large Data Bases, p.404-415, August 24-27, 1998
• 16: B. Liu, W. Hsu, Y. Ma. Integrating Classification and Association Rule Mining. SIGKDD, 1998.
• 17: Kamal Nigam , Andrew Kachites McCallum , Sebastian Thrun , Tom Mitchell, Text Classification from Labeled and Unlabeled Documents using EM, Machine Learning, v.39 n.2-3, p.103-134, May-June 2000 [doi>10.1023/A:1007692713085]
• 18: John R. Punin , Mukkai S. Krishnamoorthy , Mohammed Javeed Zaki, LOGML: Log Markup Language for Web Usage Mining, Revised Papers from the Third International Workshop on Mining Web Log Data Across All Customers Touch Points, p.88-112, August 26, 2001
• 19: Alexandre Termier , Marie-Christine Rousset , Michèl Sebag, TreeFinder: a First Step towards XML Data Mining, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.450, December 09-12, 2002
• 20: Ke Wang , Huiqing Liu, Discovering typical structures of documents: a road map approach, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.146-154, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290982]
• 21: Mohammed J. Zaki, Efficiently mining frequent trees in a forest, 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.775058]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

Keywords:
XML/Semi-structured data, classification, tree mining