This work concerns two important issues in machine learning and reasoning under uncertainty: how to evaluate a similarity relation between two uncertain pieces of information and how to perform classification from uncertain data. A first main contribution is to propose a so-called possibilistic decision tree which allows to induce decision trees from training data characterized by uncertain class labels where uncertainty is modeled within the quantitative possibility theory framework. Three possibilistic decision tree approaches have been developed. For each approach, we were faced and solved typical questions for inducing possibilistic decision trees such as how to define an attribute selection measure, how to find the stopping criteria and how leaves should be labeled in such uncertain context. Two of the proposed approaches are mainly based on the concept of similarity between possibility distributions. This issue constitutes the second main contribution of this work. After showing the important role that inconsistency could play in assessing possibilistic similarity, a new inconsistency based possibilistic similarity measure, so-called information affinity has been proposed.