TOPICS
Decision tree, ID3 algorithm, Entropy, Gain, Associative rules, Rule support,
Confidence, Rule induction, rule deduction ,rule coverage , Rule mining,
Apriori algorithm, Confusion matrix, Precision, Recall, F1- factor, Accuracy
error rate
Decision tree:
A decision tree is a model that uses a tree-like structure to visualize decisions by splitting data
into subsets. It's a popular tool in data mining, machine learning, and operations research.
What about ID3 algorithm?
The ID3 (Iterative Dichotomiser 3) algorithm is a decision tree learning algorithm that is used to
generate decision trees for classification tasks. It builds the tree top-down by selecting the best feature
to split the data at each node. ID3 is particularly sensitive to noisy data, and it does not handle
continuous features or missing data very well, but it is simple and effective for basic decision tree
construction.
Steps are:
1. Start with the Entire Dataset
Begin with the entire dataset as the root node of the decision tree.
2. Check for Stopping Criteria
At each node, the algorithm checks for the following conditions:
All examples in the dataset belong to the same class
There are no more features to split on
The dataset is empty
3. Calculate Entropy (Measure of Impurity)
For each feature in the dataset, calculate its entropy to measure the impurity of the data. Entropy
is calculated as follows:
Where:
pi is the proportion of the elements in class i in the set S,
k is the number of distinct classes in S.
4. Calculate Information Gain
For each feature, calculate the information gain. Information gain measures how much
uncertainty (entropy) is reduced when the dataset is split based on that feature. It is calculated as:
Where:
Entropy(S) is the entropy of the current set S,
Values(A) are the possible values for the feature A,
∣Sv∣ is the number of instances in subset Sv,
∣S∣ is the total number of instances in S,
Entropy(Sv) is the entropy of the subset Sv corresponding to each value v of feature A.
5. Select the Feature with the Highest Information Gain
Once the information gain has been computed for each feature, choose the feature that provides
the highest information gain (i.e., the feature that reduces the entropy the most).
6. Split the Dataset
Split the dataset based on the selected feature. For each possible value of the feature, create a
new branch. This will form the child nodes of the current node in the decision tree.
7. Repeat Recursively
For each child node, repeat steps 2 through 6, treating the subset of data that reaches each node
as a new dataset. Continue the process until a stopping condition is met (e.g., the dataset is pure,
or there are no more features to split on).
8. Final Tree Structure
Once the tree is built, each leaf node will contain the class label, and the path from the root to a
leaf node will represent a decision rule based on the feature splits.
Explain entropy with example:
In data mining, entropy is a measure of the randomness and uncertainty in a dataset. It's a
fundamental concept in data science that helps us understand the structure and patterns in data.
Entropy is used to build decision trees by selecting the best splits. High entropy implies a
higher level of disorder or uncertainty in the data. Hence, low entropy shall always be preferred
over high entropy. Mathematically entropy is defined as,
Entropy (attribute->values) =-E1 *log2(E1)- E2*log2(E2)
If there are 10 instances with 6 Yes and 4 No class instances.
Entropy=-6/10 *log2(6/10)- 4/10*log2(4/10); where E1=6/10 and E2=4/10
Problem1:
Appealing Temperature Taste Size
No Hot Salty Small
No Cold Sweet Large
No Cold Sweet Large
Yes Cold Sour Small
Yes Hot Sour Small
No Hot Salty Large
Yes Hot Sour Large
Yes Cold Sweet Small
Yes Cold Sweet Small
No Hot Salty Large
a) What is the initial entropy of appealing class?
b) Consider taste is chosen as the root of the decision tree. What is the information gain
associated this attributes.
c) Draw the full decision tree learned from the data (Using ID3 algorithm).
Solution:
(a)
Total instance are 10
Instances of Yes class=5
Instances of No class=5
Initial entropy =- 5/10*log2(5/10)- 5/10*log2(5/10)=0.5+.05=1.0
(b)
Entropy (taste-salty)=- 0/3*log2(0/3)- 3/3*log2(3/3)=0
Entropy (taste-sour)=-3/3*log2(3/3)- 0/3*log2(0/3)=0
Entropy (taste-sweet)=- 2/4*log2(2/4)- 2/4*log2(2/4)=1.0
Gain(taste)=1-3/10*0-3/10*0-4/10*1=0.6
(c)
Gain(taste)=0.6
Entropy (temp.-Hot)=- 2/5*log2(2/5)-3/5*log2(3/5)=0.53+0.44=0.97
Entropy (temp.-Cold)=-3/5*log2(3/5)-2/5*log2(2/5)= 0.44+0.53=0.97
Gain(temp.)=1-5/10*0.97 - 5/10*0.97=1-0.485-0.485=0.03
Entropy (size-small)=-4/5*log2(4/5)-1/5*log2(1/5)= 0.722
Entropy (size-large)=-1/5*log2(1/5)-4/5*log2(4/5)= 0.722
Gain (size)=1-5/10*0.722-5/10*0.722= 0.278
Root->taste
salty sweet sour
Best class: size Best class:
N0 Yes
Small large
Best class:
Best class:
N0
Yes
Problem2: Construct a decision tree using following dataset through ID3 algorithm.
Day Outlook Temp. Humidity Wind Class
1. Sunny Hot High weak no play tennis
2. Sunny Hot High strong no play tennis
3. Overcast Hot High weak play tennis
4. Rain Mild High weak play tennis
5. Rain cool normal weak play tennis
6. Rain cool normal strong no play tennis
7. Overcast cool normal strong play tennis
8. Sunny Mild High weak no play tennis
9. Sunny cool normal weak play tennis
10. Rain Mild normal weak play tennis
11. Sunny Mild normal strong play tennis
12. Overcast Mild High strong play tennis
13. Overcast Hot normal weak play tennis
14. Rain Mild High strong no play tennis
Solution:
The dataset has 4 attributes:
Outlook= (sunny, overcast, rain)
Temp. = (Hot, mild cold)
Humidity= (High, normal)
Wind= (Strong, weak)
There are possible 2 classes:
Class-I: play tennis =9
Class-II: no play tennis=5
Class entropy=-9/14*log2(9/14)-5/14*log2(5/14)=0.94
Entropy(outlook->sunny)= =-2/5*log2(2/5)-3/5*log2(3/5)=0.97
Entropy(outlook->overcast)= =-4/4*log2(4/4)-0/4*log2(0/4)=0
Entropy(outlook->rain)= =-3/5*log2(3/5)-2/5*log2(2/5)=0.97
Gain(outlook)=0.94-5/14*0.97-4/14*0-5/14*0.97=0.24
Entropy(Humidity->High)= =-3/7*log2(3/7)-4/7*log2(4/7)=0.98
Entropy(Humidity->normal)= =-6/7*log2(6/7)-1/7*log2(1/7)=0.59
Gain(Humidity)=0.94-7/14*0.98-7/14*0.59=0.155
Entropy(wind->weak)= =-6/8*log2(6/8)-2/8*log2(2/8)=0.81
Entropy(wind->strong)= =-3/6*log2(3/6)-3/6*log2(3/6)=1.0
Gain(wind)=0.94-8/14*0.81-6/14*1=0.048
Entropy(temp.->Hot)= =-2/4*log2(2/4)-2/4*log2(2/4)=1.0
Entropy(temp.->cool)= =-3/4*log2(3/4)-1/4*log2(1/4)=0.811
Entropy(temp.->mild)= =-4/6*log2(4/6)-2/6*log2(2/6)=0.92
Gain(temp.)=0.94-4/14*1-4/14*0.811-6/14*0.92=0.0283
The completed decision tree is as follows:
Root->outlook
overcast rain sunny
Best class: wind humidity
play(4)
weak strong normal high
Best class: Best class: Best class: Best class:
play(3) play(2) no play(3)
no play(2)
Limitation of ID3:
Bushy tree: Noise makes the trees bushy. Overfit the data.
Contradiction: ID3 does not handle contradiction well.
Association rules:
Association rules tell us something about the association between two attributes. Mathematically an
association rule is defined as X=>Y.
For examples: the rule {onions, potatoes} => {burger}
(item=milk) ^ (item=sugar) => (item=bread); means when a customer buys mil and sugar, it is most likely
that he also buys bread. The association rule is measured by some values such as support and confidence.
Explain confident and rule support:
Support: Rule support is the frequency of a rule over a dataset. The support Rs(r) of a general
rule R(D) is defined as,
Rs(r)=|R(D)|/|D|
where |D|= Total number of instances in the dataset
|R(D)|= Number of instances validated by the rule R(D)
In the word, support for rule (A->B) =frequency of (A, B)/N ; where N is the total instances.
Rule confidence:
Rule confidence denotes the accuracy of a rule over a dataset. Confidence for rule (A->B)=(support count of
(A,B))/ support count of (A)
Rule induction: Rule induction refers to generation/invention of rules from data. If it is 8 a.m. on a weekday, then
highway traffic will be heavy” and “if it is 8 p.m. on a Sunday, then the traffic will be light.”
Rule deduction: Deduction is a inference technique. In deduction, the rule is given and cases are applied to the
rule to get the conclusion.
Scenario:
Imagine you have the following rules and observations:
1. Rule 1: If it is raining, then the ground will be wet.
o Symbolically: Raining → Wet Ground.
2. Rule 2: If the ground is wet, then the plants will grow.
o Symbolically: Wet Ground → Plants Grow.
3. Observation: It is raining.
o Symbolically: Raining.
Conclusion:
Since it’s raining, the ground will be wet, and as a result, the plants will grow.
Rule coverage: Rule coverage is the number of instances that is supported by the antecedent part of the rule.
Test Cases for Rule Coverage:
Test Case 1:
Age: 20
Income: $3,000
Evaluation:
o Rule 1: Age ≥ 18 → True (Person is an adult).
o Rule 2: Income ≥ $2,000 → True (Person has sufficient income).
o Rule 3: Age ≥ 18 and Income ≥ $2,000 → True (Person is eligible for a loan).
Test Case 2:
Age: 16
Income: $3,000
Evaluation:
o Rule 1: Age ≥ 18 → False (Person is not an adult).
o Rule 2: Income ≥ $2,000 → True (Person has sufficient income).
o Rule 3: Age ≥ 18 and Income ≥ $2,000 → False (Person is not eligible for a loan due to
age).
Test Case 3:
Age: 25
Income: $1,500
Evaluation:
o Rule 1: Age ≥ 18 → True (Person is an adult).
o Rule 2: Income ≥ $2,000 → False (Person does not have sufficient income).
o Rule 3: Age ≥ 18 and Income ≥ $2,000 → False (Person is not eligible for a loan due to
income).
Test Case 4:
Age: 25
Income: $2,500
Evaluation:
o Rule 1: Age ≥ 18 → True (Person is an adult).
o Rule 2: Income ≥ $2,000 → True (Person has sufficient income).
o Rule 3: Age ≥ 18 and Income ≥ $2,000 → True (Person is eligible for a loan).
Rule Coverage Analysis:
Rule 1 (Age ≥ 18) was covered in Test Case 1, Test Case 2, Test Case 3, and Test Case 4.
Rule 2 (Income ≥ $2,000) was covered in Test Case 1, Test Case 2, Test Case 3, and Test Case
4.
Rule 3 (Eligibility based on both conditions) was covered in Test Case 1, Test Case 2, Test
Case 3, and Test Case 4.
Each rule has been tested in various combinations, ensuring that all rules have been evaluated at least
once for both true and false outcomes. This satisfies Rule Coverage, ensuring that every rule in the
decision system is properly tested.
Rule mining: Rule mining is a process of induction reasoning from cases or databases. Associative rule
mining is a type of rule mining that’s used to find patterns in large datasets. It's a popular method in data
mining and machine
Problem: Given the dataset in table 1. Find the rule support and rule confidence for rule
(cyl(6)LT(4))
Table 1
items cyl LT SEC Price $
falcon 6 4 10 28
fairlane 6 4 8 35
commodore 6 3.8 9 28
monaro 6 5 7 40
ltd 8 5.2 6 42
laser 4 1.8 13 17
hsv 8 5.2 5.7 44
vectra 4 2.2 11.7 20
kia 4 1.2 13.7 16
toyota 4 1.2 13.7 18
Solution:
Total instance N=10
No. of instance for rule cyl(6)LT(4)= 2
Support for rule ( cyl(6)LT(4)) = frequency of (cyl(6), LT(4))/N=2/10*100%=20%
Support count of (cyl(6), LT(4))=2
Support count of (cyl(6))=4
Confidence for rule ( cyl(6)LT(4)) = support count of (cyl(6), LT(4))/ support count of
(cyl(6))=2/4*100%=50%
Apriori algorithm: Apriori is an algorithm for frequent item set mining and association rule
learning over relational databases. It is an unsupervised algorithm that helps in creating
association rules from a given dataset.
Problem1: Given the transaction dataset as shown in the table. Apply apriori algorithm to find
associative rules. Let us consider the minimum support 50% and confident 80%.
TID Items
1 bread, cola, milk
2 juice, bread
3 juice, cola, diaper , milk
4 juice, bread, diaper , milk
5 cola, diaper , milk
Let us consider, cola=C, diaper=D , milk=M, bread=B, juice =J
Items Support Items Support
{B} 3/5*100%=60% {B,C} 1/5*100%=20%
{C} 3/5*100%=60% {B,M} 2/5*100%=40%
{M} 4/5*100%=80% SCAN=> {B,J} 2/5*100%=40%
{J} 3/5*100%=60% {B,D} 1/5*100%=20%
{D} 3/5*100%=60% {C,M} 3/5*100%=60%
{C,J} 1/5*100%=20%
{C,D} 2/5*100%=40%
{M,J} 2/5*100%=40%
{M,D} 3/5*100%=60%
{J,D} 2/5*100%=40%
Items Support Items Support
{C,M} 3/5*100%=60% SCAN=> {C,M,D} 2/5*100%=40%
{M,D} 3/5*100%=60%
Confidence:
Rules Support(A,B) Support( A) Confidence
{C,M} 3/5*100%=60% 3/5*100%=60% {CuM}/{C}*100%=3/3*100%=100%
{M,C} 3/5*100%=60% 4/5*100%=80% 3/4*100%=75%
{M,D} 3/5*100%=60% 4/5*100%=80% 3/4*100%=75%
{D,M} 3/5*100%=60% 3/5*100%=60% 3/3*100%=100%
Note: Confidence (A->B)=(support count of (A u B))/ support count of (A)
Final generated rules:
Rules Support (A,B) Confidence
{C,M} 60% 100%
{D,M} 60% 100%
Problem2:
Given the database D with minimum support 2. Explain the Apriori algorithm.
Database D
TID Items
100 1,3,4
200 2,3,5
300 1,2,3,5
400 2,5
Solution:
TID Items Item support Item Support Item set Support
set set
100 1,3,4 {1} 2 {1,2} 1 SCAN {1,2,3} 1
200 2,3,5 SCAN {2} 3 SCAN {1,3} 2 {1,2,5} 1
300 1,2,3,5 {3} 3 {1,5} 1 {1,3,5} 1
400 2,5 {4} 1 {2,3} 2 {2,3,5} 2
{5} 3 {2,5} 3
{3,5} 2
Item set Support
{2,3,5} 2
Confusion matrix: A confusion matrix is a table that compares predicted values to actual
values for a dataset. It's a tool used in machine learning to evaluate the performance of a
classification model.
Precision and recall are measures of how well a model can identify relevant data points. They are used in
classification models, information retrieval, and machine learning. If you want to minimize false positive
errors. In this case, precision is a good metric to evaluate and optimize for. A higher precision score
indicates that the model makes fewer false positive predictions. It is more likely to be correct whenever
it predicts a positive outcome. The higher the recall, the better. You can achieve a perfect recall of 1.0
when the model can find all instances of the target class in the dataset. High Recall Value: It means that the
model is good at identifying the correct data (positives). Low Recall Value: It means that the model is not
good at identifying the correct data points.
F1 factor: F1-score is a metric which takes into account both precision and recall and is
defined as follows: