Learning using Decision Trees

2
Decision Trees
 A Decision Tree (DT) defines a hierarchy of rules to make a
prediction Root Node
Body
Warm temp. Cold

An Internal Node Non-mammal

A Leaf Node

Gives No
Yes
birth

Mammal Non-mammal

 Root and internal nodes test rules. Leaf nodes make

predictions
 3
A decision tree friendly problem
Loan approval prediction
 4
Learning Decision Trees with Supervision
 The basic idea is very simple

 Recursively partition the training data into homogeneous

regions
What do you Even though the rule
mean by within each group is
“homogeneou simple, we are able to
s” regions? learn a fairly
A homogeneous sophisticated model
overall (note in this
region will have all
example, each rule is
(or a majority of) a simple
training inputs with horizontal/vertical
the same/similar classifier but the
outputs overall decision
boundary is rather
sophisticated)

 Within each group, fit a simple supervised learner (e.g., predict

 5
Decision Trees for Classification
5
NO YES
𝑥1 >3.5 ?
4 Test input

NO 𝑥 2> 2?
YES NO 𝑥 2> 3 ?
YES
3

2
Predict Predict Predict Predict
1 Red Green Green Red

1 2 3 4 5 6
Remember: Root node
Feature 1 ( contains all training
DT is very efficient at test time: To inputs
predict the label of a test point, Each leaf node receives
nearest neighbors will require a subset of training
computing distances from 48 training inputs
inputs. DT predicts the label by doing
just 2 feature-value comparisons! Way
 6
Decision Trees for Classification: Another Example
 Deciding whether to play or not to play Tennis on a Saturday
 Each input (Saturday) has 4 categorical features: Outlook,
Temp., Humidity, Wind
 A binary classification problem (play vs no-play)
 Below Left: Training data, Below Right: A decision tree
constructed using this data

Example credit: Tom Mitchell

 Usually, cross-
7
Decision Trees: Some Considerations validation can be
used to decide
size/shape
 What should be the size/shape of the DT?
 Number of internal and leaf nodes
 Branching factor of internal nodes
 Depth of the tree

 Split criterion at internal nodes

 Use another classifier?
 Or maybe by doing a simpler test?
Usually, constant
 What to do at the leaf node? Some options: prediction at leaf
 Make a constant prediction for each test input reaching
nodes usedthere
since it
will be very
 Use a nearest neighbor based prediction using training fast at that
inputs
leaf node
 Train and predict using some other sophisticated supervised learner
on that node
 8
How to Split at Internal Nodes?
 Recall that each internal node receives a subset of all the
training inputs
 Regardless of the criterion, the split should result in as “pure”
groups as possible
 A pure group means that the majority of the inputs have the same
label/output

 For classification problems (discrete outputs), entropy is a

 9
Techniques to Split at Internal Nodes
 Each internal node decides which outgoing branch an input
should be sent to
 This decision/split can be done using various ways, e.g.,
 Testing
With this approach, the
all value of a single feature at a time (such internal node
DT methods
featurescalled based on
“Decision Stump”)
and all possible
testing a single
values of each feature
need to See here infor more details
be evaluated feature at each
selecting the feature to be internal node
tested at each internal are faster and
node more popular
(can be slow but can be (e.g., ID3, C4.5
made faster using some algos)
tricks)
DT methods based on
learning and using a
separate classifier at each
 Learning a classifier (e.g., LwP or some more sophisticated
internal node are lessclassifier)
common. But this approach
can be very powerful and
are sometimes used in
 Given some training
10
Constructing Decision Trees data, what’s the
“optimal” DT?
How to decide which
5 NO
𝑥1 >3.5 ?
YES
rules to test for and in
4 what order?
NO
𝑥 2> 2?
YES NO
𝑥 2> 3 ?
YES How to assess informativeness of
3 a rule?
Feature 2 (

2
Predict
Red
Predict
Green
Predict
Green
Predict
Red In general, constructing
1
DT is an intractable
1 2 3 4 5 6 The rules are organized problem (NP-hard)
Feature 1 (
Often we can use some
Hmm.. So DTs are in the DT such that “greedy” heuristics to
like the “20 most informative rules construct a “good” DT
questions” game are tested first To do so, we use the training data to
(ask the most Informativeness of a rule is of figure out which rules should be
useful questions related to the extent of the tested at each node
first) purity of the split arising due The same rules will be applied on the
to that rule. More informative test inputs to route them along the
rules yield more pure splits tree until they reach some leaf node
where the prediction is made
 11
Decision Tree Construction: An Example
 Let’s consider the playing Tennis example
 Assume each internal node will test the value of one of the
features

 Question: Why does it make more sense to test the feature

“outlook” first?
 Answer: Of all the 4 features, it’s the most informative
 12
Entropy and Information Gain
 Assume a set of labelled inputs from C classes, as fraction
Uniform sets (all
of class c inputs classes roughly
 Entropy of the set is defined as equally present) have
high entropy; skewed
 Suppose a rule splits into two smaller disjoint setssetsand
low

 Reduction in entropy after the split is called information gain

This split has a low IG

This split has
(in fact zero IG)
higher IG
 13
Entropy and Information Gain
 Let’s use IG based criterion to construct a DT for the Tennis example
 At root node, let’s compute IG of each of the 4 features
 Consider feature “wind”. Root contains all examples S = [9+,5-]
H ( S ) = −(9/14) log 2(9/14) − (5/14) log 2(5/14) = 0.94
Sweak = [6+, 2−] ⇒ H(Sweak ) = 0.811
Sstrong = [3+, 3−] ⇒ H(Sstrong) = 1
= 0.94 − 8/14 ∗ 0.811 − 6/14 ∗ 1 = 0.048

 Likewise, at root: IG(S, outlook) = 0.246, IG(S, humidity) = 0.151,

IG(S,temp) = 0.029
 Thus we choose “outlook” feature to be tested at the root node
 Now how to grow the DT, i.e., what to do at the next level? Which feature
to test next?
 14
Growing the tree

 Proceeding as before, for level 2, left node, we can verify that

 IG(S,temp) = 0.570, IG(S, humidity) = 0.970, IG(S, wind) = 0.019
 Thus humidity chosen as the feature to be tested at level 2, left node
 No need to expand the middle node (already “pure” - all “yes” training
examples )
 Can also verify that wind has the largest IG for the right node
 Note: If a feature has already been tested along a path earlier, we don’t
 15
When to stop growing the tree?

 Stop expanding a node further (i.e., make it a leaf node) when

 It consist of all training examples having the same label (the node
becomes “pure”)
 We run out of features to test along the path to that node
 The DT starts to overfit (canTobehelp prevent the
checked by monitoring
tree from growing
the validation set accuracy)too much!
 Important: No need to obsess too much for purity OR
 It is okay to have a leaf node that is not fully pure, e.g., this
 At test inputs that reach an impure leaf, can predict probability of
belonging to each class (in above example, p(red) = 3/8, p(green) =
 16
Avoiding Overfitting in DTs
 Desired: a DT that is not too big in size, yet fits the training data
reasonably
 Note: An example of a very simple DT is “decision-stump”
 A decision-stump only tests the value of a single feature (or a simple
rule)
 Not very powerful in itself but often used Either
in large
canensembles
be of
decision stumps done using a
 Mainly two approaches to prune a complex DT validation set
 Prune while building the tree (stopping early)
 Prune after building the tree (post-pruning)
 Criteria for judging which nodes could potentially be pruned
 Use a validation set (separate from the training set)
 Prune each possible node that doesn’t hurt the accuracy on the
validation set

 17
Decision Trees: Some Comments
 Gini-index defined as can be an alternative to IG

 For DT regression1, variance in the outputs can be used to assess purity

 When features are real-valued (no finite possible values to try), things are
a bit more tricky
 Can use tests based on thresholding feature values (recall our
synthetic data examples)
 Need to be careful w.r.t. number of threshold points, how fine each
range is, etc.
 More sophisticated decision rules at the internal nodes can also be used
 Basically, need some rule that splits inputs at an internal node into
homogeneous groups
 The rule can even be a machine learning classification algo (e.g., LwP
or aJ. H.;
, Leo; Friedman, deep
Olshen,learner)
R. A.; Stone, C. J. (1984). Classification and regression trees
 18
An Illustration: DT with Real-Valued Features
Test example
“Best” (purest “Best”(purest
possible) possible) Vertical
Horizontal Split Split

Up Down Left Right

Between the best
horizontal vs best vertical
split, the vertical split is
better (purer), hence we
use this rule for the
internal node

s illustration’s credit: Purushottam Kar

 19
Decision Trees for RegressionCan use any Another simple
regression model option can be to
but would like a predict the
simple one, so let’s average output
use a constant of the training
prediction based inputs in this
regression model region
4 NO YES
𝑥> 4 ?

3
y YES
NO Predict
2 𝑥 2> 3 ?

1
Predict Predict
1 2 3 4 5
𝐱

To predict the output for a test point,

nearest neighbors will require computing
distances from 15 training inputs. DT
predicts the label by doing just at most
feature-value comparisons! Way faster!
 20
Decision Trees: ..AthusSummary
helping us learn
complex rule as a combination
Some key strengths: of several simpler rules
 Simple and easy to interpret
5
 Nice example of “divide and conquer” NO
𝑥1 >3.5 ?
YES

paradigm in machine learning 4

NO YES NO YES
 Easily handle different types of3
𝑥 2> 2? 𝑥 2> 3 ?

Feature 2 (
features (real, categorical, etc.)
2
 Very fast at test time Predict
Red
Predict
Green
Predict
Green
Predict
Red
1
 Multiple DTs can be combined
1 2 3 4 5 6 Human-body
via ensemble methods: more powerful Feature 1 ( pose
(e.g., Decision Forests; will see later) estimation
 Used in several real-world ML applications, e.g., recommender
systems, gaming (Kinect)
Some key weaknesses:
 Learning optimal DT is (NP-hard) intractable. Existing algos mostly
 Key Hyperparameters
1. criterion
•What it does: Chooses the function to measure the quality of a split.
•Options:
• "gini" (default) — Uses Gini Impurity.
• "entropy" — Uses Entropy (from Information Gain).
•Impact: Affects how the tree decides where to split.
2. max_depth
•What it does: Sets the maximum depth of the tree.
•Impact: Controls overfitting (deep trees may overfit) and underfitting (shallow trees
may underfit).
3. min_samples_split
•What it does: Minimum number of samples required to split an internal node.
•Default: 2
•Impact: Higher values = less splits = simpler tree.
4. min_samples_leaf
from sklearn.tree import DecisionTreeClassifier clf = •What it does: Minimum number of samples that must be in a leaf node.
DecisionTreeClassifier •Default: 1
•Impact: Bigger values = more pruning = prevents very small leaves.
( criterion="gini", 5. max_features
max_depth=5, •What it does: Number of features to consider when looking for the best split.
•Options:
min_samples_split=4, • Integer (exact count)
• Float (proportion of total features)
min_samples_leaf=2, • "sqrt" (square root of total features — common in Random Forests)
max_features="sqrt" ) •
•
"log2"
None (use all features)
6. max_leaf_nodes
•What it does: Maximum number of leaf nodes.
•Impact: Limits tree growth and simplifies model.
7. splitter
•What it does: Chooses strategy to split nodes.
•Options:
• "best" — Chooses the best split.
• "random" — Chooses a random split among the best candidates.
8. class_weight
•What it does: Weights assigned to each class (for handling imbalance).
•Options:
• None — All classes treated equally.
• balanced — Weights are inversely proportional to class frequencies.