Inference Based Classifier: Efficient Construction of Decision Trees for Sparse Categorical Attributes

摘要

Classification is an important problem in data mining and machine learning, and the decision tree approach has been identified as an efficient means for classification. According to our observation on real data, the distribution of attributes with respect to information gain is very sparse because only a few attributes are major discriminating attributes where a discriminating attribute is an attribute, by whose value we are likely to distinguish one tuple from another. In this paper, we propose an efficient decision tree classifier for categorical attribute of sparse distribution. In essence, the proposed Inference Based Classifier (abbreviated as IBC) can alleviate the "overfitting" problem of conventional decision tree classifiers. Also, IBC has the advantage of deciding the splitting number automatically based on the generated partitions. IBC is empirically compared to C4.5, SLIQ and K-means based classifiers. The experimental results show that IBC significantly outperforms the companion methods in execution efficiency for dataset with categorical attributes of sparse distribution while attaining approximately the same classification accuracies. Consequently, IBC is considered as an accurate and efficient classifier for sparse categorical attributes.