Topic 18

Question 1

How to best choose which features to have at the root of the decision tree?

Answer 1

Examine the probability distribution of the different outcomes and choose the features that split the probabilities most differently

Question 2

Entropy

Answer 2

A measure of the uncertainty associated with a random variable X, H(X) = -Σ n, i=1 P(xi)log2(Pxi) (Base 2 log)

Question 3

Expected Entropy (over a child node)

Answer 3

EH = Σ k, i=1 Hi *|ni| / |n| where |ni| / |n| is the proportion of parent training instances that went to the child note. Allows us to compare the entropy before and after splitting a parent node into child nodes

Question 4

Information Gain / Reduction in Entropy (from a split using some feature F)

Answer 4

Gain(Feat) = Hn - EH(Feat) or Entropy at Parent Node – (Expected) Entropy over the Child Nodes

Question 5

Gini Index

Answer 5

Gini(X) = Σ n, i=1 P(xi)(1-P(xi))

Question 6

Advantages of Decision Trees

Answer 6

*
Relatively computationally inexpensive.
*
Can deal both non-numeric features and numeric features (i.e. use a numeric cut-off boundary). See next set of topic notes.
*
Can learn complex, non-linear decision boundaries.
*
Give an easy-to-understand classification process.

Question 7

Disadvantages of Decision Trees

Answer 7

Disadvantages
*
Susceptible to overfitting
*
Lack robustness (small changes to training data can mean large changes to fitted model).
In particular, the order we assign feature decisions to nodes may change based on small changes in the data. See next set of topic notes.
*
Tend to be outperformed by other methods, and refinements to the basic decision tree idea. See next set of topic notes.