| This dissertation studies learning decision trees effectively and efficiently, from a probabilistic perspective.;The scalability problem in tree learning is addressed by applying the independence assumption in naive Bayes to the tree growing process. The new algorithm has a linear learning time complexity in the number of attributes, while achieving accuracies at the level of more expensive tree learners.;To show the impact of our results to the other probabilistic approaches, we extend the above results to Bayesian networks. A set of probabilistic trees are used to efficiently learn the structure and represent the local probability distribution in Bayesian networks Empirical studies show that learning and representing Bayesian networks by probabilistic trees have various advantages over state-of-the-art Bayesian network learners and standard tree learners.;We point out that the traditional prediction method in decision tree learning is not suitable for achieving both accurate ranking and classification in a tree. We propose to tackle this problem by using Laplace smoothing and the probability product rule to exploit the tree path information. Furthermore, by representing probability independence among attributes in tree paths, a large decision tree can be represented by many small decision trees, and these small trees can be combined by Bayes theory to make predictions. A new probabilistic decision tree model, called the Conditional Independence Tree (CITree), and the corresponding learning algorithm are proposed. In terms of prediction power, an extensive empirical study using benchmark datasets shows that CITree significantly outperforms the standard decision tree learners, and is competitive with ensemble tree learners. |
