Machine Learning Lectujjjjjjjjjjjjjjjre 9.pdf

hhhhhhhhhhh

1. Machine Learning
Module 2
Induction Trees
Semester 2
Fall 2023-2024
Dr. Ahmed Ezz

2. 2
Decision Tree Induction: An Example
age?
overcast
student? credit rating?
<=30
>40
no yes
yes
yes
31..40
fairexcellent
yesnoageincomestudentcredit_ratingbuys_computer
<=30high nofair no
<=30high noexcellent no
31…40high nofair yes
>40 medium nofair yes
>40 low yesfair yes
>40 low yesexcellent no
31…40low yesexcellent yes
<=30medium nofair no
<=30low yesfair yes
>40 medium yesfair yes
<=30medium yesexcellent yes
31…40medium noexcellent yes
31…40high yesfair yes
>40 medium noexcellent no
❑Training data set: Buys_computer
❑Resulting tree:

3. Algorithm for Decision Tree Induction
•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 (e.g., information gain)
•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

4. Brief Review of Entropy
m = 2

5. Attribute Selection Measure: Information Gain

6. Example Attribute Selection: Information Gainageincomestudentcredit_ratingbuys_computer
<=30high nofair no
<=30high noexcellent no
31…40high nofair yes
>40 medium nofair yes
>40 low yesfair yes
>40 low yesexcellent no
31…40low yesexcellent yes
<=30medium nofair no
<=30low yesfair yes
>40 medium yesfair yes
<=30medium yesexcellent yes
31…40medium noexcellent yes
31…40high yesfair yes
>40 medium noexcellent no
Construct a Tree based on information gain
that classify “Buys_computer” as target.
The dataset has four inputs:
•age
•Income
•Student
•credit_rating

7. Expected information
(entropy) needed to classify a tuple in D:
ageincomestudentcredit_ratingbuys_computer
<=30 high no excellent no
<=30 high no fair no
<=30medium no fair no
>40medium no excellent no
>40 low yes excellent no
<=30medium yes excellent yes
<=30 high yes fair yes
>40medium no fair yes
>40 low yes fair yes
>40medium yes fair yes
31..40medium no excellent yes
31..40low yes excellent yes
31..40high no fair yes
31..40low yes fair yes
Class P: buys_computer = “yes” 9 cases
Class N: buys_computer = “no” 5 Cases940.0)
14
5
(log
14
5
)
14
9
(log
14
9
)5,9()(
22 =−−==IDInfo )(log)(
2
1
i
m
i
i ppDInfo
=
−=

8. info D(age)= 5/14 * I(2,3) + 5/14 *i(3,2) + 4/14 * i(4,0)
info D(age) = 0.693536139
gain D(Age) = info D - info(age)= 0.940 - 0.693536139
gain D(Age) = 0.24674982
Age <=30
Class P: buys_computer = “yes” 2 cases
Class N: buys_computer = “no” 3 Cases
Age 31..40
Class P: buys_computer = “yes” 4 cases
Class N: buys_computer = “no” 0 Cases
Age >40
Class P: buys_computer = “yes” 3 cases
Class N: buys_computer = “no” 2 Cases694.0)2,3(
14
5
)0,4(
14
4
)3,2(
14
5
)(
=+
+=
I
IIDInfo
age
Information Gain of attribute age

9. Income =high
Class P: buys_computer = “yes” 2 cases
Class N: buys_computer = “no” 2 Cases
Income =low
Class P: buys_computer = “yes” 3 cases
Class N: buys_computer = “no” 1 Cases
Income =medium
Class P: buys_computer = “yes” 4 cases
Class N: buys_computer = “no” 2 Cases
info D(income) =4/14 * i(2,2) + 4/14 * i(1,3) + 6/14 * i(2,4)
info D(income) = 0.911063393
gain D(income) =info D - info D(income) = 0.940 -0.911063393
gain D(income) = 0.029222566
Info
income (D) =
&#3627409362;
&#3627409359;&#3627409362;
??????&#3627409360;,&#3627409360;+
&#3627409362;
&#3627409359;&#3627409362;
??????&#3627409361;,&#3627409359; +
&#3627409364;
&#3627409359;&#3627409362;
??????&#3627409362;,&#3627409360;
Information Gain of attribute Income

10. Student=no
Class P: buys_computer = “yes” 3 cases
Class N: buys_computer = “no” 4 Cases
Student=yes
Class P: buys_computer = “yes” 6 cases
Class N: buys_computer = “no” 1 Cases
info D(student) = 7/14 * i(4,3) + 7/14 * i(1,6)
info D(student) = 0.788450457
gain D(student) =info D - info D(student) = 0.940 -0.788450457
gain D(student) = 0.151835501
Info
student(D) =
&#3627409365;
&#3627409359;&#3627409362;
??????&#3627409361;,&#3627409362;+
&#3627409365;
&#3627409359;&#3627409362;
??????&#3627409364;,&#3627409359;
Information Gain of attribute Student940.0)
14
5
(log
14
5
)
14
9
(log
14
9
)5,9()(
22 =−−==IDInfo

11. credit_rating = excellent
Class P: buys_computer = “yes” 3 cases
Class N: buys_computer = “no” 3 Cases
credit_rating = fair
Class P: buys_computer = “yes” 6 cases
Class N: buys_computer = “no” 2 Cases
info D(credit_rating) = 6/14 * i(3,3) + 8/14 * i(2,6)
info D(credit_rating) = 0.892158928
gain D(credit_rating) =info D - info D(credit_rating) = 0.940 - 0.892158928
gain D(credit_rating) = 0.04812703
Info
credit_rating(D) =
&#3627409364;
&#3627409359;&#3627409362;
??????&#3627409361;,&#3627409361;+
&#3627409366;
&#3627409359;&#3627409362;
??????&#3627409360;,&#3627409364;
Information Gain of attribute credit_rating

12. Which One?
gain D(Age) = 0.24674982
gain D(income) = 0.029222566
gain D(student) = 0.151835501
gain D(credit_rating) = 0.04812703
We will use the field with highest gain_D
Age

13. Draw Tree
Age

14. Work with Age <= 30
Class P: buys_computer = “yes” 3 cases
Class N: buys_computer = “no” 2 Cases
??????&#3627408475;&#3627408467;&#3627408476;??????= −
3
5
??????&#3627408476;&#3627408468;
2
3
5
−
2
5
??????&#3627408476;&#3627408468;
2
2
5
=0.970950594
info D(income) =3/5 * i(1,2) + 2/5 * i(1,1)
info D(income) = 0.9509775
gain D(income) =info D - info D(income)
gain D(income) = 0.019973094
info D(student) =3/5 * i(0,3) + 2/5 * i(2,0)
info D(student) = 0
gain D(student) =info D - info D(student
gain D(student) =0.970950594
info D(credit_rating) =2/5 * i(1,1) + 3/5 * i(1,2)
info D(credit_rating) = 0.9509775
gain D(credit_rating) =info D - info D(credit_rating)
gain D(credit_rating) = 0.019973094

15. Which One?
gain D(income) = 0.019973094
gain D(student) = 0.970950594
gain D(credit_rating) = 0.019973094
We will use the field with highest gain_D
student

16. NoYes Yes
Student
Draw Tree
Age

17. Work with Age > 40
Class P: buys_computer = “yes” 3 cases
Class N: buys_computer = “no” 2 Cases
??????&#3627408475;&#3627408467;&#3627408476;??????= −
3
5
??????&#3627408476;&#3627408468;
2
3
5
−
2
5
??????&#3627408476;&#3627408468;
2
2
5
=0.970950594

18. Constructed Tree
age?
overcast
student? credit rating?
<=30
>40
no yes yes
yes
31..40
fairexcellent
yesno
We Have Five leaves.
We Write Rule For each leaf using AND operator

19. Rules Extraction
age?
student?
<=30
no
no
buys_computer = “no” IF
age = “<=30” AND
student = “no”
buys_computer = “yes” IF
age = “<=30” AND
student = “yes”
age?
yes
31..40
age?
student?
<=30
yes
yes
buys_computer = “yes” IF
age = “31..40”
age?
credit rating?
>40
excellent
buys_computer = “no” IF
age = “>40” AND
credit_rating= “no”
age?
credit rating?
>40
excellent
yes
buys_computer = “no” IF
age = “>40” AND
credit_rating= “no”