Efficient Rule Based Structural Algorithms For Classification Of Tree Structured Data

摘要

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.