18.3 Decision Trees
1 18.3 Decision Trees
DECISIONTREE「Quinlan93]An internal node represents a test on an attribute.A branch represents an outcome of the test, e.g.,Color=red.A leaf node represents a class label or class labeldistribution.At each node, one attribute is chosen to split trainingexamples into distinct classes as much as possibleA new case is classified by following a matching pathto a leaf node.2
2 DECISION TREE [Quinlan93] ◼ An internal node represents a test on an attribute. ◼ A branch represents an outcome of the test, e.g., Color=red. ◼ A leaf node represents a class label or class label distribution. ◼ At each node, one attribute is chosen to split training examples into distinct classes as much as possible ◼ A new case is classified by following a matching path to a leaf node
Training SetOutlookTempreature Humidity WindyClassNhothighfalsesunnyNhothightruesunnyPhothighfalseovercastPmildhighfalserainPraincoolfalsenormalNcoolrainnormaltruePcoolnormaltrueovercastNmildhighfalsesunnyPcoolnormalfalsesunnyPmildrainfalsenormalPmildtruenormalsunnyPhighovercast mildtruePfalseovercast hotnormalNhighrainmildtrue
Outlook Tempreature Humidity Windy Class sunny hot high false N sunny hot high true N overcast hot high false P rain mild high false P rain cool normal false P rain cool normal true N overcast cool normal true P sunny mild high false N sunny cool normal false P rain mild normal false P sunny mild normal true P overcast mild high true P overcast hot normal false P rain mild high true N Training Set
ExampleOutlooksunnyovercastrainPhumiditywindyhighnormalfalsetruePPNN
Outlook overcast humidity windy high normal true false sunny rain N P N P P overcast Example
Building Decision Tree [Q93]Top-down tree constructionAtstart,alltrainingexamplesareattheroot.Partition the examples recursively by choosing one attributeeach time. Bottom-up tree pruningRemove subtrees or branches,in a bottom-up manner, toimprovethe estimated accuracy on new cases.5
5 Building Decision Tree [Q93] ◼ Top-down tree construction ◼ At start, all training examples are at the root. ◼ Partition the examples recursively by choosing one attribute each time. ◼ Bottom-up tree pruning ◼ Remove subtrees or branches, in a bottom-up manner, to improve the estimated accuracy on new cases