Learning Decision Trees from Uncertain Data with an Evidential EM Approach

Abstract

In real world applications, data are often uncertain or imperfect. In most classification approaches, they are transformed into precise data. However, this uncertainty is an information in itself which should be part of the learning process. Data uncertainty can take several forms: probabilities, (fuzzy)sets of possible values, expert assessments, etc. We therefore need a flexible and generic enough model to represent and treat this uncertainty, such as belief functions. Decision trees are well known classifiers which are usually learned from precise datasets. In this paper we propose a methodology to learn decision trees from uncertain data in the belief function framework. In the proposed method, the tree parameters are estimated through the maximization of an evidential likelihood function computed from belief functions, using the recently proposed E2M algorithm that extends the classical EM. Some promising experiments compare the obtained trees with classical CART decision trees.