Decision trees as possibilistic classifiers

This paper addresses the classification problem with imperfect data. More precisely, it extends standard decision trees to handle uncertainty in both building and classification procedures. Uncertainty here is represented by means of possibility distributions. The first part investigates the issue of building decision trees from data with uncertain class values by developing a non-specificity based gain ratio as the attribute selection measure which, in our case, is more appropriate than the standard gain ratio based on Shannon entropy. The proposed non-specificity based possibilistic decision tree (NS-PDT) approach is then extended by considering another kind of uncertainty inherent in the building procedure. The extended approach so-called non-specificity based possibilistic option decision tree (NS-PODT) offers a more flexible building procedure by allowing the selection of more than one attribute in each node. The second part addresses the classification phase. More specifically, it investigates the issue of predicting the class value of new instances presented with certain and/or uncertain attribute values. Finally, we have developed a possibilistic decision tree toolbox (PD2T) in order to show the feasibility of the proposed approach. (C) 2008 Elsevier Inc. All rights reserved.