《人工智能与数据挖掘教学课件》lect.ppt

yes
>40 credit rating?
no
yes
excellent fair
no
yes
no
yes
2020/4/24
AI&DM
6
2 Algorithm for Decision Tree Building
• Basic algorithm (a greedy algorithm)
– Tree is constructed in a top-down recursive divide-and-conquer manner
2020/4/24
AI&DM
9
Attribute Selection by Information Gain
Computation
Class P: buys_computer = “yes”
Class N:
E(age) 5 I (2,3) 4 I (4,0)
14
14
5 I (3,2) 0.69 14
– There are no remaining attributes for further partitioning – majority voting is employed for classifying the leaf
– There are no samples left
– Reach the pre-set accuracy
predetermined classes
– Preparation: Each tuple/sample is assumed to belong to a predefined class, labeled by the output attribute or class label attribute
– Test attributes are selected on the basis of a heuristic or statistical measure (e.g., information gain)
• Conditions for stopping partitioning
– All samples for a given node belong to the same class
IF age = “31…40”
THEN buys_computer = “yes”
IF age = “>40” AND credit_rating = “excellent” THEN buys_computer = “yes”
IF age = “>40” AND credit_rating = “fair” THEN buys_computer = “no”
2020/4/24
AI&DM
12
3.2 Rules simplification and elimination
A Rule for the Tree in Figure 3.4
IF Age <=43 & Sex = Male & Credit Card Insurance = No THEN Life Insurance Promotion = No (accuracy = 75%, Figure 3.4)
A Simplified Rule Obtained by Removing Attribute Age
IF Sex = Male & Credit Card Insurance = No THEN Life Insurance Promotion = No (accuracy = 83.3% (5/6), Figure 3.5)
classify objects in all subsets Si is
E( A)
i1
pi p
ni n
I(
pi , ni )
• The encoding information that would be gained by branching on A Gain(A) I ( p, n) E(A)
buys_computer no no yes yes yes no yes no yes yes yes yes yes no 5
1 Example (2): Output: A Decision Tree for “buys_computer”
age?
<=30 ov30e.r.c4a0st
student?
Classification Process (2): Use the Model in Prediction
Classifier
Testing Data
Unseen Data
NAME RANK
YEARS TENURED
T om A ssistant P rof 2
no
M erlisa A ssociate P rof 7
Gain(income) 0.029 Gain(student) 0.151
30?0 4 0 0
Gain(credit _ rating) 0.048
2>02400/4/24
3 2 0.971
AI&DM
10
3. Decision Tree Rules
• Automate rule creation • Rules simplification and elimination • A default rule is chosen
– Estimate accuracy of the model
• The known label of test sample is compared with the classified result from the model
• Accuracy rate is the percentage of testing set samples that are correctly classified by the model
2020/4/24
AI&DM
2
Classification Process (1): Model Construction
Training Data
Classification Algorithms
NAME RANK
YEARS TENURED
M ike A ssistant P rof 3
no
M ary A ssistant P rof 7
2020/4/24
AI&DM
11
3.1 Extracting Classification Rules from Trees
• Represent the knowledge in the form of IF-THEN rules
• One rule is created for each path from the root to a leaf
2020/4/24
AI&DM
7
Information Gain （信息增益）(ID3/C4.5)
• Select the attribute with the highest information gain
• Assume there are two classes, P and N
– Let the set of examples S contain p elements of class P and n elements of class N
student credit_rating no fair no excellent no fair no fair yes fair yes excellent yes excellent no fair yes fair yes fair yes excellent no excellent yes fair nAIo&DM excellent
age <=30 <=30 30…40 >40 >40 >40 31…40 <=30 <=30 >40 <=30 31…40 31…40 >40
income high high high medium low low low medium low medium medium medium high medium
yes
B ill P rofessor
2
yes
Jim A ssociate P rof 7
yes
D ave A ssistant P rof 6
no
A nne A ssociate P rof 3
no
2020/4/24
AI&DM
Classifier (Model)
IF rank = ‘professor’ OR years > 6 THEN tenured = ‘y3 es’
– The amount of information, needed to decide if an arbitrary example in S belongs to P or N is defined as
I ( p, n)
p
ห้องสมุดไป่ตู้
p
n
log2
p pn
p
n
n
log2
n pn
2020/4/24
AI&DM
• Note: Test set is independent of training set, otherwise over-fitting will occur
• 2. Model usage: use the model to classify future or unknown