Belief decision trees: Theoretical foundations.

*(English)*Zbl 0991.68088Summary: This paper extends the decision tree technique to an uncertain environment where the uncertainty is represented by belief functions as interpreted in the transferable belief model. This so-called belief decision tree is a new classification method adapted to uncertain data. We will be concerned with the construction of the belief decision tree from a training set where the knowledge about the instances’ classes is represented by belief functions, and its use for the classification of new instances where the knowledge about the attributes’ values is represented by belief functions.

##### MSC:

68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |

68T35 | Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence |

##### Keywords:

transferable belief model##### Software:

C4.5
PDF
BibTeX
Cite

\textit{Z. Elouedi} et al., Int. J. Approx. Reasoning 28, No. 2--3, 91--124 (2001; Zbl 0991.68088)

Full Text:
DOI

##### References:

[1] | J.A. Barnett, Combining opinions about the order of rule execution, in: The Ninth National Conference on Artificial Intelligence, AAAI, vol. 91, 1991, pp. 477-481 |

[2] | M.S. Bjanger, Induction of decision trees from partially classified data using belief functions, Master, University of Compiegne, 2000 |

[3] | Breiman, L.; Friedman, J.H.; Olshen, R.A.; Stone, C.J., Classification and regression trees, (1984), Wadsworth & Brooks Monterey, CA · Zbl 0541.62042 |

[4] | J. Cheng, U.M. Fayyad, K.B. Irani, Z. Qian, Improved decision trees: a generalized version of ID3, in: Proceedings of the fifth International Conference on Machine Learning, June 12-14, 1988, pp. 100-106 |

[5] | Denoeux, T., A k-nearest neighbor classification rule based on dempster – shafer theory, IEEE transactions on systems, man, and cybernetics, 25, 5, 804-813, (1995) |

[6] | T. Denoeux, M.S. Bjanger, Induction of decision trees from partially classified data using belief functions, in: IEEE Int. Conf. on Systems, Man and Cybernetics, 2000 |

[7] | Z. Elouedi, K. Mellouli, P. Smets, Decision trees using the belief function theory, in: The Proceedings of the International Conference on Information Processing and Management of Uncertainty in Knowledge-based Systems, IPMU’2000, 2000, pp. 141-148 · Zbl 0973.68538 |

[8] | Z. Elouedi, K. Mellouli, P. Smets, Classification with belief decision trees, in: The Proceedings of the Ninth International Conference on Artificial Intelligence: Methodology, Systems, Applications, AIMSA’2000, 2000, pp. 80-90 · Zbl 0973.68538 |

[9] | Z. Elouedi, K. Mellouli, P. Smets, Induction of belief decision trees: a conjunctive approach, in: The Proceedings of the 10th Conference of the Applied Stochastic Models and Data Analysis, ASMDA2001, 2001, pp. 404-409 · Zbl 0991.68088 |

[10] | U.M. Fayyad, K.B. Irani, The attribute selection problem in decision tree generation, in: The Tenth National Conference on Artificial Intelligence, AAAI, vol. 92, 1992, pp. 104-110 |

[11] | Janikow, G.Z., Fuzzy decision trees: issues and methods, IEEE transactions on systems, man, and cybernetics, B, 28, 1, 1-14, (1998) |

[12] | J. Kholas, P.A. Monney, A Mathematical Theory of Hints. An Approach to Dempster-Shafer Theory of Evidence, Lecture Notes on Economics and Mathematical Systems, vol. 425, Springer, Berlin, 1995 · Zbl 0833.62005 |

[13] | Liu, W.Z.; White, A.P., The importance of attribute selection measures in decision tree induction, Machine learning, 15, 24-41, (1994) |

[14] | 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 de l’Université Paris6, LIP6, 1998 |

[15] | K. Mellouli, On the propagation of beliefs in networks using the Dempster-Shafer theory of evidence, Ph.D. Dissertation, School of business, University of Kansas, Lawrence, KS, 1987 |

[16] | Quinlan, J.R., Induction of decision trees, Machine learning, 1, 81-106, (1986) |

[17] | J.R. Quinlan, Decision trees as probabilistic classifiers, in: Proceedings of the Fourth International Workshop on Machine Learning, June 22-25, 1987, pp. 31-37 |

[18] | Quinlan, J.R., Decision trees and decision making, IEEE transactions on systems, man, and cybernatics, 20, 2, 339-346, (1990) |

[19] | J.R. Quinlan, Probabilistic decision trees, in: R.S. Michalski, J.G. Carbonell, T.M. Michell (Eds.), Machnie Learning, vol. 3, Morgan Kaufmann, Los Altos, CA, 1990, pp. 140-152 (Chapter 5) |

[20] | Quinlan, J.R., C4.5: programs for machine learning, (1993), Morgan Kaufmann San Mateo, CA |

[21] | Safavian, S.R.; Landgrebe, D., A survey of decision tree classifier methodology, IEEE transactions on systems, man, and cybernetics, 21, 3, 660-674, (1991) |

[22] | Shafer, G., A mathematical theory of evidence, (1976), Princeton University Press Princeton, NJ · Zbl 0359.62002 |

[23] | Shafer, G., Perspectives on the theory and practice of belief functions, International journal of approximate reasoning, 4, 323-362, (1990) · Zbl 0714.62001 |

[24] | Shafer, G., Rejoinders to comments on perspectives on the theory and practice of belief functions, International journal of approximate reasoning, 6, 445-480, (1992) · Zbl 0749.68081 |

[25] | Shannon, C.E., A mathematical theory of communication, The Bell system technical journal, 7, 3, 379-423, (1948) · Zbl 1154.94303 |

[26] | P.P. Shenoy, G. Shafer, Axioms for probability and belief-function propagation, in: G. Shafer, J. Pearl (Eds.), The Morgan Kauffmann series in Representation and Reasoning, 1990, pp. 574-610 |

[27] | P. Smets, Decisions and belief functions, Technical Report No. TR/IRIDIA/90-10, Université Libre de Bruxelles, 1990 |

[28] | Smets, P., The combination of evidence in the transferable belief model, IEEE transactions on pattern analysis and machine intelligence, 12, 321-344, (1990) |

[29] | P. Smets, in: Ph. Smets, A. Mamdani, D. Dubois, H. Prade (Eds.), Belief Functions, Non Standard Logics for Automated Reasoning, Academic Press, London, 1990, pp. 253-286 |

[30] | Smets, P., Belief functions: the disjunctive rule of combination and the generalized Bayesian theorem, International journal of approximate reasoning, 9, 1-35, (1993) · Zbl 0796.68177 |

[31] | Smets, P.; Kennes, R., The transferable belief model, Artificial intelligence, 66, 191-234, (1994) · Zbl 0807.68087 |

[32] | P. Smets, Numerical representation of uncertainty, in: D.M. Gabbay, Ph. Smets (Eds.), Handbook of Defeasible Reasoning and Uncertainty Management Systems, vol. 3, Kluwer Academic Publishers, Dordrecht, 1998, pp. 265-309 · Zbl 0944.91014 |

[33] | P. Smets, The transferable belief model for quantified belief representation, in: D.M. Gabbay, Ph. Smets (Eds.), Handbook of Defeasible Reasoning and Uncertainty Management Systems, vol. 1, Kluwer Academic Publishers, Doordrecht, 1998, pp. 267-301 · Zbl 0939.68112 |

[34] | Smets, P., The application of the transferable belief model to diagnostic problems, International journal of intelligent systems, 13, 127-158, (1998) · Zbl 0900.68393 |

[35] | P. Smets, Practical uses of belief functions, in: K.B. Laskey, H. Prade (Eds.), Uncertainty in Artificial Intelligence, UAI99, vol. 15, 1999, pp. 612-621 |

[36] | M. Umano, H. Okamoto, I.H.H. Tamura, F. Kawachi, S. Umedzu, J. Kinoshita, Fuzzy decision trees by fuzzy ID3 algorithm and its application to diagnosis systems, in: Proceedings of third IEEE International Conference on Fuzzy Systems, FUZZ-IEEE’94, June 26-29, 1994, pp. 2113-2118 |

[37] | Yuan, Y.; Shaw, M.J., Induction of fuzzy decision trees, Fuzzy sets and systems, 69, 125-139, (1995) |

[38] | Zeidler, J.; Schlosser, M., Continuous valued attributes in fuzzy decision trees, Ipmu, 96, 395-400, (1996) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.