Affiliations: [a] Database Research Group, Faculty of ECE, School of Engineering, University of Tehran, Tehran, Iran | [b] Department of CE, Sharif University of Technology, Tehran, Iran | [c] Control and Intelligent Processing Center of Excellence, Faculty of ECE, School of Engineering, University of Tehran, Tehran, Iran | [d] Database Research Group, Control and Intelligent Processing Center of Excellence, Faculty of ECE, School of Engineering, University of Tehran, Tehran, Iran | [e] Faculty of ECE, School of Engineering, University of Tehran, Tehran, Iran
Abstract: Recently, tree structures have become a popular way for storing and manipulating huge amount of data. Classification of these data can facilitate storage, retrieval, indexing, query answering and different processing operations. In this paper, we present C-Classifier and M-Classifier algorithms for rule based classification of tree structured data. These algorithms are based on extracting especial tree patterns from training dataset. These tree patterns, i.e. closed tree patterns and maximal tree patterns are capable of extracting characteristics of training trees completely and non-redundantly. Our experiments show that M-Classifier significantly reduces running time and complexity. As experimental results show, accuracies of M-Classifier and C-Classifier depend on whether or not we want to classify all of the data points (even uncovered data). In the case of complete classification, C-Classifier shows the best classification quality. On the other hand and in the case of partial classification, M-Classifier improves classification quality measures.
Keywords: Tree-structured data, XML documents, structural classification, rule based classification, induced closed tree pattern, induced maximal tree pattern