On the optimization of fuzzy decision trees

The induction of fuzzy decision trees is an important way of acquiring imprecise knowledge automatically. Fuzzy ID3 and its variants are popular and efficient methods of making fuzzy decision trees from a group of training examples. This paper points out the inherent defect of the likes of Fuzzy ID3, presents two optimization principles of fuzzy decision trees, proves that the algorithm complexity of constructing a kind of minimum fuzzy decision tree is NP-hard, and gives a new algorithm which is applied to three practical problems. The experimental results show that, with regard to the size of trees and the classification accuracy for unknown cases, the new algorithm is superior to the likes of Fuzzy ID3. (C) 2000 Elsevier Science B.V. All rights reserved.