Decision Trees

Question 1

Things that make decision trees unique

Answer 1

supervised learning
batch processing of training examples
uses a preference bias

Question 2

Decision tree non-leaf node

Answer 2

associated with an attribute/feature

Question 3

decision tree leaf node

Answer 3

associated with a classification

Question 4

decision tree arc

Answer 4

associated with one of the possible values of attribute of parent node

Question 5

How does decision tree work?

Answer 5

attribute at root is question; answer is determined by value of that attribute in the input example; answer determines movement of child; repeat until leaf (class label at leaf = classification give to input example)

Question 6

Ockham’s Razor

Answer 6

Preference bias; the smallest decision tree that correctly classifies all training examples is best

Question 7

Decision Tree Construction (greed) aka ID3, C5.0

Answer 7

1. select best attribute to use for new node at current level
2. partiton examples using the possible values of this attribute, assign subsets to appropriate child node; recursively generate child node until all examples at node have same label

Question 8

How to select best attribute to construct best tree?

Answer 8

random; least values; most values; max gain

Question 9

Information Value

Answer 9

Given a set S of size |S|, the expected work required to determine a specific element is log2|S|

Question 10

Entropy Interpretation

Answer 10

The number of yes/no questions (in bits) need on average to determine the value of Y in a random drawing

Question 11

Entropy H(Y)

Answer 11

H measures the information content (in bits) associated with a set of examples; 0

Question 12

bit

Answer 12

information needed to answer a yes/no question; real valued scalar

Question 13

Perfect balance (maximum inhomogeneity)

Answer 13

high entropy - from a nearly uniform distribution

Question 14

Perfect homogeneity

Answer 14

low entropy - Y is from a varied (peaks/valleys) distribution

Question 15

max value of H is

Answer 15

log2c (c is the number of classes)

Question 16

How is entropy related to tree size

Answer 16

small entropy = small tree size

Question 17

conditional entropy H(Y|X)

Answer 17

weighted sum of the entropy of each subset of the examples partitioned by the possible values of attribute x; weighted sum of entropy at each child node generated by x;

Question 18

What does conditional entropy measure

Answer 18

the total impurity, disorder, or inhomogeneity at all the children nodes

Question 19

Information gain

Answer 19

measures the difference in entropy of a node and entropy remaining after the node’s examples are “split” between the children using a chosen attribute; choose attribute that maximizes I(Y;X)

Question 20

Why is high information gain desirable?

Answer 20

Means more of the examples are the same class in each child node; the decision trees rooted at each child that are needed to differentiate between the classes are likely to be small

Question 21

The best attribute for a node is the attribute with

Answer 21

maximum information gain, minimum conditional entropy