文档介绍：: .
Decisi 智能技术课程• Basic algorithm (a greedy algorithm)
– Tree is constructed in a top-down recursive divide-and-conquer
manner
– At start, all the training examples are at the root
– Attributes are categorical (if continuous-valued, they are discretized in
advance)
– Examples are partitioned recursively based on selected attributes
– Test attributes are selected on the basis of a heuristic or statistical
measure(to be explained later)
• Conditions for stopping partitioning
– All samples for a given node belong to the same class
– There are no remaining attributes for further partitioning – majority
voting is employed for classifying the leaf
– There are no samples left
2014-12-29 智能技术课程A Decision tree for the “Grouping”
problem,with attribute Size as the root
{1,4,-2,-5} size {2,3,-1,-3,-4}
Low high
hair hair
Gold={1,4,-5} B={-2) Gold={-1,3} B={-3,-4)
2 Red={2}
eyes eyes 2
Blue={1} B={-5) Blue={3) 1
G={4) B={-1)
2
1 1 1 2
2014-12-29 智能技术课程Rule set generated by tracing back from a leaf to the root:
8 rules, in total;
1. If [size=low] ∧[hair=Gold]∧[eyes=Blue], then Group=1；
2. If [size=low] ∧[hair=Gold]∧[eyes=Gray], then Group=1;
3. If [size=low] ∧[hair=Gold]∧[eyes=Black], then
Group=2;
4. If …..to be finished by students!
5. If…..
6. If
7. If
8. If
2014-12-29 智能技术课程A smaller Decision tree for the “Grouping”
problem,with attribute Hair as the root
hair
Gold={1,3,4,-1,-5} B={-2,-3,-4)
Red={2}