Decision tree learning

From Infogalactic: the planetary knowledge core
Jump to: navigation, search


In decision analysis, a decision tree can be used to visually and explicitly represent decisions and decision making. In data mining, a decision tree describes data but not decisions; rather the resulting classification tree can be an input for decision making. This page deals with decision trees in data mining.







Data comes in records of the form:

(\textbf{x},Y) = (x_1, x_2, x_3, ..., x_k, Y)



Decision trees used in data mining are of two main types:




  • A Random Forest classifier uses a number of decision trees, in order to improve the classification rate.



  • ID3 (Iterative Dichotomiser 3)
  • C4.5 (successor of ID3)
  • CART (Classification And Regression Tree)
  • MARS: extends decision trees to handle numerical data better.




Gini impurity

Not to be confused with Gini coefficient.

Used by the CART (classification and regression tree) algorithm, Gini impurity is a measure of how often a randomly chosen element from the set would be incorrectly labeled if it were randomly labeled according to the distribution of labels in the subset. Gini impurity can be computed by summing the probability f_i of each item being chosen times the probability 1-f_i of a mistake in categorizing that item. It reaches its minimum (zero) when all cases in the node fall into a single target category.

To compute Gini impurity for a set of items, suppose i \in \{1, 2, ..., m\}, and let f_i be the fraction of items labeled with value i in the set.

I_{G}(f) = \sum_{i=1}^{m} f_i (1-f_i) = \sum_{i=1}^{m} (f_i - {f_i}^2) = \sum_{i=1}^m f_i - \sum_{i=1}^{m} {f_i}^2
 = 1 - \sum^{m}_{i=1} {f_i}^{2} = \sum_{i\neq k}f_i f_k

Information gain


I_{E}(f) = - \sum^{m}_{i=1} f_i \log^{}_2 f_i

Variance reduction


I_{V}(N) = \frac{1}{|S|^2}\sum_{i\in S} \sum_{j\in S} \frac{1}{2}(x_i - x_j)^2 - \left(\frac{1}{|S_t|^2}\sum_{i\in S_t} \sum_{j\in S_t} \frac{1}{2}(x_i - x_j)^2 + \frac{1}{|S_f|^2}\sum_{i\in S_f} \sum_{j\in S_f} \frac{1}{2}(x_i - x_j)^2\right)


Decision tree advantages

Amongst other data mining methods, decision trees have various advantages:



  • The problem of learning an optimal decision tree is known to be NP-complete under several aspects of optimality and even for simple concepts.[12][13] Consequently, practical decision-tree learning algorithms are based on heuristics such as the greedy algorithm where locally-optimal decisions are made at each node. Such algorithms cannot guarantee to return the globally-optimal decision tree. To reduce the greedy effect of local-optimality some methods such as the dual information distance (DID) tree were proposed.[14] [1]
  • Decision-tree learners can create over-complex trees that do not generalise well from the training data. (This is known as overfitting.[15]) Mechanisms such as pruning are necessary to avoid this problem (with the exception of some algorithms such as the Conditional Inference approach, that does not require pruning [9][10]).
  • For data including categorical variables with different numbers of levels, information gain in decision trees is biased in favor of those attributes with more levels.[17] However, the issue of biased predictor selection is avoided by the Conditional Inference approach.[9]


Decision graphs

In a decision tree, all paths from the root node to the leaf node proceed by way of conjunction, or AND. In a decision graph, it is possible to use disjunctions (ORs) to join two more paths together using Minimum message length (MML).[18] Decision graphs have been further extended to allow for previously unstated new attributes to be learnt dynamically and used at different places within the graph.[19] The more general coding scheme results in better predictive accuracy and log-loss probabilistic scoring.[citation needed] In general, decision graphs infer models with fewer leaves than decision trees.

Alternative search methods

Evolutionary algorithms have been used to avoid local optimal decisions and search the decision tree space with little a priori bias.[20][21]

It is also possible for a tree to be sampled using MCMC.[22]

The tree can be searched for in a bottom-up fashion.[23]

See also




  5. Friedman, J. H. (1999). Stochastic gradient boosting. Stanford University.
  8. Kass, G. V. (1980). "An exploratory technique for investigating large quantities of categorical data". Applied Statistics. 29 (2): 119–127. JSTOR 2986296. doi:10.2307/2986296. 
  9. 9.0 9.1 9.2 Hothorn, T.; Hornik, K.; Zeileis, A. (2006). "Unbiased Recursive Partitioning: A Conditional Inference Framework". Journal of Computational and Graphical Statistics. 15 (3): 651–674. JSTOR 27594202. doi:10.1198/106186006X133933. 
  15. "Principles of Data Mining". 2007. ISBN 978-1-84628-765-7. doi:10.1007/978-1-84628-766-4. 
  16. Horváth, Tamás; Yamamoto, Akihiro, eds. (2003). "Inductive Logic Programming". Lecture Notes in Computer Science. 2835. ISBN 978-3-540-20144-1. doi:10.1007/b13700. 
  19. Tan & Dowe (2003)

External links