A complete fuzzy decision tree technique

[en] In this paper, a new method of fuzzy decision trees called soft decision trees (SDT) is presented. This method combines tree growing and pruning, to determine the structure of the soft decision tree, with refitting and backfitting, to improve its generalization capabilities. The method is explained and motivated and its behavior is first analyzed empirically on 3 large databases in terms of classification error rate, model complexity and CPU time. A comparative study on 11 standard UCI Repository databases then shows that the soft decision trees produced by this method are significantly more accurate than standard decision trees. Moreover, a global model variance study shows a much lower variance for soft decision trees than for standard trees as a direct cause of the improved accuracy. (C) 2003 Elsevier B.V. All rights reserved.

Disciplines :

Computer science
Mathematics

Author, co-author :

Olaru, C.; Université de Liège - ULiège > Département d'Electricité, d'Electronique et d'Informatique > Systèmes et Modélisation

Wehenkel, Louis ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation

Language :

English

Title :

A complete fuzzy decision tree technique

Publication date :

01 September 2003

Journal title :

Fuzzy Sets and Systems

ISSN :

0165-0114

eISSN :

1872-6801

Publisher :

Elsevier Science Bv, Amsterdam, Netherlands

Volume :

138

Issue :

Pages :

221-254

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 22 March 2009

Statistics

Number of views

143 (10 by ULiège)

Number of downloads

3 (1 by ULiège)

More statistics

Scopus citations^®

350

Scopus citations^®
without self-citations

348

OpenCitations

272

Bibliography

Apolloni B., Zamponi G., Zanaboni A.M. Learning fuzzy decision trees. Neural Networks. 11:1998;885-895.
R. Araya, P. Gigon, Segmentation trees: a new help building expert systems and neural networks, Proceedings of Stats, 1992, pp. 119-124.
J.F. Baldwin, J. Lawry, T.P. Martin, Mass assignment based induction of decision trees on words, in: Proceedings of the Information Processing and Management of Uncertainty in Knowledge-Based Systems, Vol. 1, July 6-10, Paris, 1998, pp. 524-531.
X. Boyen, Design of fuzzy logic-based decision trees applied to power system transient stability assessment, Master's Thesis, University of Liège, 1995.
X. Boyen, L. Wehenkel, Fuzzy decision tree induction for power system security assessment, Proceedings of SIPOWER'95, IFAC Symposium on Control of Power Plants and Power Systems, Cancun, Mexico, December 1995, pp. 151-156.
X. Boyen, L. Wehenkel, On the Unfairness of Convex Discriminator Quality Measures for Fuzzy Partitioning in Machine Learning, Technical Report, University of Liege, 1995.
Boyen X., Wehenkel L. Automatic induction of fuzzy decision trees and its applications to power system security assessment. Fuzzy Sets and Systems. 1(102):1999;3-19.
Breiman L. Arcing classifiers. Ann. Statist. 26(3):1998;801-849.
Breiman L., Friedman J.H., Olshen R.A., Stone C.J. Classification and Regression Trees. 1984;Chapman & Hall, New-York.
Buntine W. Learning classification trees. Statist. Comput. 2:1992;63-73.
C. Carter, J. Catlett, Assessing Credit Card Applications Using Machine Learning, IEEE Expert, Fall 1987, pp. 71-79.
Chang R.L.P., Pavlidis Th. Fuzzy decision tree algorithms. IEEE Trans. Systems Man, Cybern. SMC-7(1):1977;28-35.
Chi Z., Yan H. ID3-Derived fuzzy rules and optimized defuzzification for handwritten numeral recognition. IEEE Trans. Fuzzy Systems. 4(1):1996;24-31.
Cios K.J., Liu N. A machine learning method for generation of a neural network architecture. a continuous ID3 algorithm IEEE Trans. Neural Networks. 3(2):1992;280-291.
K.J. Cios, L.M. Sztandera, Continuous ID3 algorithm with fuzzy entropy measures, Proceedings of The First IEEE Conference on Fuzzy Systems, San Diego, 1992, pp. 469-476.
Cios K.J., Sztandera L.M. Ontogenic neuro-fuzzy algorithm. F-CID3 Neurocomputing. 14:1997;383-402.
Dietterich T.G. Approximate statistical tests for comparing supervised classification learning algorithms. Neural Comput. 10(7):1998;1895-1924.
T.G. Dietterich, Ensemble methods in machine learning, in: J. Kittler, F. Roli (Eds.), First International Workshop on Multiple Classifier Systems, Cagliari, Italy, Lecture Notes in Computer Science, Vol. 1857, Springer, Berlin, 2000, pp. 1-15.
T.G. Dietterich, E.B. Kong, Machine Learning Bias, Statistical Bias, and Statistical Variance of Decision Tree Algorithms, Technical Report, Department of Computer Science, Oregon State University, 1995.
J.H. Friedman, Local Learning Based On Recursive Covering, Technical Report, Dept. of Statistics, Standford University, August 1996.
Geurts P., Olaru C., Wehenkel L. Improving the bias/variance tradeoff of decision trees. towards soft tree induction Eng. Intelligent Syst. 9(4):2001;195-204.
P. Geurts, L. Wehenkel, Investigation and reduction of discretization variance in decision tree induction, Proceedings of 11th European Conference on Machine Learning, ECML 2000, Barcelona, Spain, May/June 2000, pp. 162-170.
L.O. Hall, P. Lande, Generating fuzzy rules from decision trees, Proceedings of International Fuzzy Systems Association of World Congress, Vol. 2, Prague, 1997, pp. 418-423.
I. Hayashi, J. Ozawa, L.C. Jain, Generation of Fuzzy Decision Trees by Fuzzy ID3 with Adjusting Mechanism of AND/OR Operators, IEEE 1998.
A.P. Heinz, Learning and generalization in adaptive fuzzy logic networks, in: H.-J. Zimmermann (Ed.), EUFIT'94, Proceedings of the Second European Congress on Intelligent Techniques and Soft Computing, Aachen, Germany, 20-23 September 1994, pp. 1347-1351.
A.P. Heinz, Pipelined neural tree learning by error forward-propagation, ICNN'95, Proceedings of the IEEE International Conference on Neural Networks, Vol. I, Perth, Western Australia, 27 November-1 December, 1995, pp. 394-397.
Ichihashi H., Shirai T., Nagasaka K., Miyoshi T. Neuro-fuzzy ID3. a method of inducing fuzzy decision trees with linear programming for maximizing entropy and an algebraic method for incremental learning Fuzzy Sets and Systems. 81:1996;157-167.
A. Ittner, J. Zeidler, R. Rossius, W. Dilger, M. Schlosser, Feature space partitioning by non-linear and fuzzy decision trees, Proceedings of International Fuzzy Systems Association World Congress, Vol. 2, Prague, 1997, pp. 394-398.
Janikow C.Z. Fuzzy decision trees. issues and methods IEEE Trans. Systems Man, Cybernetics - Part B: Cybernetics. 28(1):1998;1-14.
Jeng B., Jeng Y.-M., Liang T.-P. FILM. a fuzzy inductive learning method for automated knowledge acquisition Decision Support Systems. 21:1997;61-73.
Jordan M.I. A statistical approach to decision tree modeling. Warmuth M. Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory. 1994;ACM Press, New York.
C. Marsala, Apprentissage inductif en présence de données imprécises: construction et utilisation d'arbres de décision flous, Thèse de doctorat, Université Paris 6, 1998.
C. Marsala, B. Bouchon-Meunier, Forests of fuzzy decision trees, Proceedings of the International Fuzzy Systems Association World Congress, Vol. 2, Prague, 1997, pp. 369-374.
C. Olaru, Fuzzy Decision Tree Induction using Square Error Type of Criterion, Internal Report, University of Liege, Department of Electrical and Computer Engineering, Belgium, October 1998.
Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical Recipes in C. The Art of Scientific Computing. 2nd Edition:1994;Cambridge University Press, Cambridge.
Quinlan J.R. Induction of decision trees. Machine Learn. 1:1986;81-106.
Quinlan J.R. C4.5: Programs for Machine Learning. 1993;Morgan Kaufmann Publishers, Inc. San-Mateo.
M. Ramdani, Système d'induction formelle à base de connaissances imprécises, Thèse de doctorat, Université Paris VI, Paris, France, February 1994.
J.-S. Roger Jang, Structure determination in fuzzy modeling: a fuzzy CART approach, Proceedings of the Third IEEE International Conference on Fuzzy Systems, Vol. 1, June 26-29, Orlando, Florida, 1994, pp. 480-485.
Sethi I.K. Entropy nets. from decision trees to neural networks Proc. IEEE. 78(10):1990;1605-1613.
Sethi I.K. Neural implementation of tree classifiers. IEEE Trans. Systems Man Cybernetics. 25(8):1995;1243-1249.
Shah Hamzei G.H., Mulvaney D.J. On-line learning of fuzzy decision trees for global path planning. Eng. Appl. Artificial Intelligence. 12:1999;93-109.
T. Shibata, T. Abe, K. Tanie, M. Nose, Motion planning of a redundant manipulator based on criteria of skilled operators using fuzzy-ID3 and GMDH, Proceedings of Sixth IFSA World Congress, Vol. 1, Sao Paulo, Brazil, July 21-28, 1995, pp. 613-616.
Suarez A., Lutsko F. Globally optimal fuzzy decision trees for classification and regression. IEEE Trans. Pattern Anal. Machine Intelligence. 21(12):1999;1297-1311.
T. Tani, M. Sakoda, K. Tanaka, Fuzzy modeling by ID3 algorithm and its application to prediction of heater outlet temperature, Proceedings of the First IEEE Conference on Fuzzy Systems, San Diego, 1992, pp. 923-930.
L. Torgo, Inductive Learning of Tree-based Regression Models, Ph.D. Thesis, Department of Computer Science, Faculty of Sciences, University of Porto, September 1999.
Tsang E.C.C., Wang X.Z., Yeung Y.S. Improving learning accuracy of fuzzy decision trees by hybrid neural networks. IEEE Trans. Fuzzy Systems. 8(5):2000;601-614.
Tsuchiya T., Maeda T., Matsubara Y., Nagamachi M. A fuzzy rule induction method using genetic algorithm. Internat. J. Industrial Ergonomics. 18:1996;135-145.
Turney P. Technical note. bias and quantification of stability Machine Learn. 20:1995;23-33.
M. Umano, H. Okamoto, I. Hatono, H. Tamura, Fuzzy Decision Trees by fuzzy ID3 algorithm and its application to diagnosis systems, Proceedings of The Third IEEE Conference on Fuzzy Systems, Vol. 3, June 26-29, Orlando, FL, 1994, pp. 2113-2118.
Utgoff P.E. Perceptron trees. a case study in hybrid concept representations Connect. Sci. 1(4):1989;377-391.
Wang X.Z., Chen B., Qian G., Ye F. On the optimization of fuzzy decision trees. Fuzzy Sets and Systems. 112(1):2000;117-125.
Wang Q.R., Suen C.Y. Large tree classifier with heuristic search and global training. IEEE Trans. Pattern Anal. Machine Intelligence. PAMI-9(1):1987;91-102.
R. Weber, Fuzzy ID3: a class of methods for automatic knowledge acquisition, Proceedings of the 2nd International Conference on Fuzzy Logic and Neural Networks, Iizuka, Japan, July 17-22, 1992, pp. 265-268.
L. Wehenkel, An information quality based decision tree pruning method, Proceedings of the IPMU'92 Conference, Palma de Mallorca, Spain, July 6-10, 1992.
L. Wehenkel, Discretization of continuous attributes for supervised learning. Variance evaluation and variance reduction, Proceedings of the Seventh IFSA World Congress (invited paper), Vol. 2, Prague, June 25-29, 1997, pp. 381-388.
Wehenkel L. Automatic Learning Techniques in Power Systems. 1998;Kluwer Academic, Boston.
Wehenkel L., Pavella M. Decision tree approach to power system security assessment. Electrical Power Energy Systems. 15(1):1993;13-36.
Yuan Y., Shaw M.J. Induction of fuzzy decision trees. Fuzzy Sets and Systems. 69:1995;125-139.
J. Zeidler, M. Schlosser, Continuous-valued attributes in fuzzy decision trees, Proceedings of Information Processing and Management of Uncertainty in Knowledge-Based Systems, Granada, 1996, pp. 395-400.