Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Breiman, L., Friedman, J.H., Olshen, R.A., Sotne, C.J.: Classification and Regression Trees. Wadsworth, Belmont (1984)
NASA Ames Research Center. Introduction to IND Version 2.1. GA23-2475-02 edition (1992)
Chesseman, P., Kelly, J., Self, M., et al.: AutoClass: A Bayesian classification system. In: 5th Int’l Conf. on Machine Learning. Morgan Kaufman, San Francisco (1988)
Chou, P.A.: Optimal Partitioning for Classification and Resgression Trees. IEEE Transactions on Pattern Analysis and Machine Intelligence 13(4) (1991)
Fayyad, U.: On the Induction of Decision Trees for multiple Concept Learning. PhD thesis, The University of Michigan, Ann arbor (1991)
Fayyad, U., Irani, K.B.: Multi-interval discretization of continuous-valued attributes for classification learning. In: Proc. of the 13th International Joint Conference on Artificial Intelligence (1993)
Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning. Morgan Kaufmann, San Francisco (1989)
Han, J., Kamber, M.: Data Mining: Concepts and Techniques. Morgan Kaufmann Publishers, San Francisco (2000)
Mehta, M., Agrawal, R., Rissanen, J.: SLIQ: A fast scalable classifier for data mining. In: Apers, P.M.G., Bouzeghoub, M., Gardarin, G. (eds.) EDBT 1996. LNCS, vol. 1057. Springer, Heidelberg (1996)
Mehta, M., Rissanen, J., Agrawal, R.: MDL-based decision tree pruning. In: Int’l Conference on Knowledge Discovery in Databases and Data Mining (1995)
Michie, D., Spiegelhalter, D.J., Taylor, C.C.: Machine Learning, Neural and Statistical Classification. Ellis Horwood (1994)
Quinlan, J.R.: C4.5: Programs for Machine Learning. Morgan Kaufmann, San Francisco (1993)
Quinlan, J.R.: Induction of decision trees. Machine Learning (1986)
Quinlan, J.R., Rivest, R.L.: Inferring decision trees using minimum description length principle. Information and Computtation (1989)
Rastogi, R., Shim, K.: PUBLIC: A Decision Tree Classifier that Integrates Building and Pruning. In: Proceedings of 24rd International Conference on Very Large Data Bases, New York City, New York, USA, August 24-27 (1998)
Ripley, B.D.: Pattern Recognition and Neural Networks. Cambridge University Press, Cambridge (1996)
Shafer, J., Agrawal, R., Mehta, M.: SPRINT: A scalable parallel classifier for data mining. In: Proc. of the VLDB Conference, Bombay, India (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lo, SH., Ou, JC., Chen, MS. (2003). Inference Based Classifier: Efficient Construction of Decision Trees for Sparse Categorical Attributes. In: Kambayashi, Y., Mohania, M., Wöß, W. (eds) Data Warehousing and Knowledge Discovery. DaWaK 2003. Lecture Notes in Computer Science, vol 2737. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45228-7_19
Download citation
DOI: https://doi.org/10.1007/978-3-540-45228-7_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40807-9
Online ISBN: 978-3-540-45228-7
eBook Packages: Springer Book Archive