Leren Samenvatting 2
Decision Trees
Decision tree representation:
Each internal node tests an attribute
Each branch corresponds to an attribute value
Each leaf node assigns a classification
Top-Down Induction of Decision trees, main loop:
1. A the “best” decision attribute for the next node
2. Assign A as decision attribute for a node
3. For each value of A, create a new descendant of the node
4. Sort training examples to leaf nodes
5. If the training examples are perfectly classified, then STOP, else iterate over new leaf
nodes
Entropy
Entropy(S) is the expected number of bits needed to encode a class (+ or -) of a randomly
drawn member of S (under the optimal, shortest-length code). Entropy is the degree of
uncertainty. Binary variance = p(1-p)
, Information Gain
Gain(S,A) is the expected reduction in entropy due to sorting on A.
The information gain is higher for the classifier Humidity, so that is the best classifier.
ID3 Algorithm
There is noise in the data, so we need to make sure that that isn’t used in the model, because
it couldn’t generalize if that were the case.
Preference for short trees, and for those trees with high information gain attributes
near the root.
Bias is a preference for some hypotheses, rather than a restriction of hypothesis space
H.
Occam’s razor: prefer the shortest hypothesis that fits the data:
o Arguments in favor:
Fewer short hypotheses, than long hypotheses
A short hypothesis that fits data is unlikely to be a coincidence
A long hypothesis that fits data might be a coincidence
o Arguments opposed:
There are many ways to define small sets of hypotheses
E.g. all trees with a prime number of nodes that use attributes
beginning “Z”
Decision Trees
Decision tree representation:
Each internal node tests an attribute
Each branch corresponds to an attribute value
Each leaf node assigns a classification
Top-Down Induction of Decision trees, main loop:
1. A the “best” decision attribute for the next node
2. Assign A as decision attribute for a node
3. For each value of A, create a new descendant of the node
4. Sort training examples to leaf nodes
5. If the training examples are perfectly classified, then STOP, else iterate over new leaf
nodes
Entropy
Entropy(S) is the expected number of bits needed to encode a class (+ or -) of a randomly
drawn member of S (under the optimal, shortest-length code). Entropy is the degree of
uncertainty. Binary variance = p(1-p)
, Information Gain
Gain(S,A) is the expected reduction in entropy due to sorting on A.
The information gain is higher for the classifier Humidity, so that is the best classifier.
ID3 Algorithm
There is noise in the data, so we need to make sure that that isn’t used in the model, because
it couldn’t generalize if that were the case.
Preference for short trees, and for those trees with high information gain attributes
near the root.
Bias is a preference for some hypotheses, rather than a restriction of hypothesis space
H.
Occam’s razor: prefer the shortest hypothesis that fits the data:
o Arguments in favor:
Fewer short hypotheses, than long hypotheses
A short hypothesis that fits data is unlikely to be a coincidence
A long hypothesis that fits data might be a coincidence
o Arguments opposed:
There are many ways to define small sets of hypotheses
E.g. all trees with a prime number of nodes that use attributes
beginning “Z”
