Summary Decision Tree Learning

3 Decision Tree Learning

I Decision tree representation

I ID3 learning algorithm

I Entropy, Information gain

I Overfitting




ICCL
International Center for Computational Logic 1
Algebra, Logic and Formal Methods in Computer Science

,Decision Tree for P layT ennis

Outlook



Sunny Overcast Rain


Humidity Yes Wind



High Normal Strong Weak

No Yes No Yes



ICCL
International Center for Computational Logic 2
Algebra, Logic and Formal Methods in Computer Science

, Decision Trees

I Decision tree representation:

. Each internal node tests an attribute.
. Each branch corresponds to an attribute value.
. Each leaf node assigns a classification.

I How would we represent:
. ∧, ∨, XOR
. (A ∧ B ) ∨ (C ∧ ¬D ∧ E )
. M of N




ICCL
International Center for Computational Logic 3

Algebra, Logic and Formal Methods in Computer Science