Classification in Data Mining
2,037 views
79 slides
Jul 31, 2022
Slide 1 of 79
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
About This Presentation
Process of Classification in Data Mining
Slide Content
Classification and Prediction
2
What is Classification?
•In Classification, a modelor classifieris constructed to predict categorical labels
•Data classification is a two-step process
1. Learning 2. Classification
Training
Data
Classification
algorithm
Classification
rules
Test Data
New Data
(unknown
class label)
Class Label
Data Mining: Classification and Prediction 3
•In Classification, a modelor classifieris constructed to predict categorical labels
•Data classification is a two-step process
1. Learning 2. Classification
Training
Data
Classification
algorithm
Classification
rules
Test Data
New Data
(unknown
class label)
Class Label
Data Mining: Classification and Prediction 3
What is Classification?
•Learning step:
•A classification algorithm builds the classifierby analyzing or “learning from” a training
set made up of database tuples and their associated class labels.
•The individual tuples making up the training set are referred to as training tuples.
•Data tuples can be referred to as samples, examples, instances, data points, or objects
•This is supervised learning step
•The class label of each training tuple is provided
•This process can be viewed as the learning of a mapping or function y=�(�)
•Predicts the associated class label �of a given tuple �
•This mapping is represented in the form of classification rules, decision trees, or
mathematical formulae
Data Mining: Classification and Prediction 4
•Learning step:
•A classification algorithm builds the classifierby analyzing or “learning from” a training
set made up of database tuples and their associated class labels.
•The individual tuples making up the training set are referred to as training tuples.
•Data tuples can be referred to as samples, examples, instances, data points, or objects
•This is supervised learning step
•The class label of each training tuple is provided
•This process can be viewed as the learning of a mapping or function y=�(�)
•Predicts the associated class label �of a given tuple �
•This mapping is represented in the form of classification rules, decision trees, or
mathematical formulae
Data Mining: Classification and Prediction 4
What is Classification?
•Classification Step
•The model is used for classification.
•A test set is used, made up of test tuples and their associated class labels.
•Randomly selected tuples from the general data set
•The accuracy of a classifier on a given test set is the percentage of test set tuples that
are correctly classifiedby the classifier.
•The associated class label of each test tuple is compared with the learned classifier’s class
prediction for that tuple.
•If the accuracy of the classifier is considered acceptable, the classifier can be used to
classify future data tuples for which the class label is not known.
Data Mining: Classification and Prediction 5
•Classification Step
•The model is used for classification.
•A test set is used, made up of test tuples and their associated class labels.
•Randomly selected tuples from the general data set
•The accuracy of a classifier on a given test set is the percentage of test set tuples that
are correctly classifiedby the classifier.
•The associated class label of each test tuple is compared with the learned classifier’s class
prediction for that tuple.
•If the accuracy of the classifier is considered acceptable, the classifier can be used to
classify future data tuples for which the class label is not known.
Data Mining: Classification and Prediction 5
Data Mining: Classification and Prediction 6
What is Prediction?
•Data prediction is a two step process similar to data classification
•There is no class attribute
•Because attribute values to be predicted are continuous-valued (ordered) rather than
categorical (discrete-valued)
•Predicted attribute
•Prediction can also be viewed as a mapping or functiony=�(�)
Data Mining: Classification and Prediction 7
•Data prediction is a two step process similar to data classification
•There is no class attribute
•Because attribute values to be predicted are continuous-valued (ordered) rather than
categorical (discrete-valued)
•Predicted attribute
•Prediction can also be viewed as a mapping or functiony=�(�)
Data Mining: Classification and Prediction 7
How classification and prediction are
different?
•Data classification classifies categoricalattribute values
•Data prediction predicts continuous-valuedattribute value
•Testing data is used to assess accuracy of a classifier
•The accuracy of a predictor is estimated by computing an error based on the
difference between the predicted value and the actual known value of y for each
of the test tuples, X
Data Mining: Classification and Prediction 8
different?
•Data classification classifies categoricalattribute values
•Data prediction predicts continuous-valuedattribute value
•Testing data is used to assess accuracy of a classifier
•The accuracy of a predictor is estimated by computing an error based on the
difference between the predicted value and the actual known value of y for each
of the test tuples, X
Data Mining: Classification and Prediction 8
Decision Tree Induction
•It is the learning of decision trees from class-labeled training tuples.
•A decision tree is a flowchart-like tree structure, where
•Each internal node (non-leaf node) denotes a test on an attribute,
•Each branchrepresents an outcome of the test, and
•Each leaf node (or terminal node) holds a class label.
•The topmost node in a tree is the rootnode
•Is a person fit?????
•Binary decision tree
•Non-binary decision tree
Data Mining: Classification and Prediction 9
Age <30?
Eats lots of
pizza?
Exercises
daily?
Fit Fit Unfit! Unfit!
Yes No
Yes Yes No No
Fig. Decision Tree for the concept being fit
•It is the learning of decision trees from class-labeled training tuples.
•A decision tree is a flowchart-like tree structure, where
•Each internal node (non-leaf node) denotes a test on an attribute,
•Each branchrepresents an outcome of the test, and
•Each leaf node (or terminal node) holds a class label.
•The topmost node in a tree is the rootnode
•Is a person fit?????
•Binary decision tree
•Non-binary decision tree
Data Mining: Classification and Prediction 9
Age <30?
Eats lots of
pizza?
Exercises
daily?
Fit Fit Unfit! Unfit!
Yes No
Yes Yes No No
Fig. Decision Tree for the concept being fit
Decision Tree Induction
•How are decision trees used for classification?
•Given a tuple, X, for which the associated class label is unknown, the attribute values of
the tuple are tested against the decision tree.
•A path is traced from the root to a leaf node, which holds the class prediction for that
tuple.
•Advantages of decision trees:
•Does not require any domain knowledge or parameter setting
•Can handle high dimensional data.
•The learning and classification steps of decision tree induction are simple and fast
•Have good accuracy
Data Mining: Classification and Prediction 10
•How are decision trees used for classification?
•Given a tuple, X, for which the associated class label is unknown, the attribute values of
the tuple are tested against the decision tree.
•A path is traced from the root to a leaf node, which holds the class prediction for that
tuple.
•Advantages of decision trees:
•Does not require any domain knowledge or parameter setting
•Can handle high dimensional data.
•The learning and classification steps of decision tree induction are simple and fast
•Have good accuracy
Data Mining: Classification and Prediction 10
Decision Tree Induction
•Attribute selection measures
•Used to select the attribute that best partitions the tuples into distinct
classes.
•Information gain, Gain Ratio, Gini Index
•A decision tree algorithm is known as ID3(Iterative Dichotomiser).
•C4.5algorithm (successor of ID3) benchmark to newer supervised
learning algorithms
•Classification and Regression Trees (CART)
•Adopt a greedy (i.e., nonbacktracking) approach in which decision trees
are constructed in a top-downrecursive divide-and-conquermanner
Data Mining: Classification and Prediction 11
Info Gain
Gain Ratio
Gini Index
•Attribute selection measures
•Used to select the attribute that best partitions the tuples into distinct
classes.
•Information gain, Gain Ratio, Gini Index
•A decision tree algorithm is known as ID3(Iterative Dichotomiser).
•C4.5algorithm (successor of ID3) benchmark to newer supervised
learning algorithms
•Classification and Regression Trees (CART)
•Adopt a greedy (i.e., nonbacktracking) approach in which decision trees
are constructed in a top-downrecursive divide-and-conquermanner
Data Mining: Classification and Prediction 11
Info Gain
Gain Ratio
Gini Index
Decision Tree Induction
•Information Gain
•ID3 uses information gain as its attribute selection measure
•The expected information needed to classify a tuple in �is given by
�����=−
�=�
�
�
�??????????????????
�(�
�)
•where �
�is the probability that an arbitrary tuple in �belongs to class �
�,estimated as ൗ
�
??????,??????
�
•Info(D) is also known as the entropyof D.
•The expected information required to classify a tuple from �based on the partitioning by
attribute �.
����
��=
�=�
�
�
�
�
����(�
�)
Data Mining: Classification and Prediction 12
•Information Gain
•ID3 uses information gain as its attribute selection measure
•The expected information needed to classify a tuple in �is given by
�����=−
�=�
�
�
�??????????????????
�(�
�)
•where �
�is the probability that an arbitrary tuple in �belongs to class �
�,estimated as ൗ
�
??????,??????
�
•Info(D) is also known as the entropyof D.
•The expected information required to classify a tuple from �based on the partitioning by
attribute �.
����
��=
�=�
�
�
�
�
����(�
�)
Data Mining: Classification and Prediction 12
Decision Tree Induction
•Information Gain
•Information gain is defined as the difference between the original information
requirement and the new requirement
�����=�����−����
��
•The attribute �with the highest information gain, ����(�), is chosen as the splitting
attribute at node �.
Data Mining: Classification and Prediction 13
•Information Gain
•Information gain is defined as the difference between the original information
requirement and the new requirement
�����=�����−����
��
•The attribute �with the highest information gain, ����(�), is chosen as the splitting
attribute at node �.
Data Mining: Classification and Prediction 13
Decision Tree Induction
•Decision Tree Generation Algorithm
•Input:
•Data partition, D,
which is a set of training tuples and their associated class labels;
•Attribute_list,
the set of candidate attributes;
•Attribute_selection_method,
a procedure to determine the splitting criterion that “best” partitions the data tuples into
individual classes. This criterion consists of a splitting attribute and, possibly, either a split point
or splitting subset.
Data Mining: Classification and Prediction 14
•Decision Tree Generation Algorithm
•Input:
•Data partition, D,
which is a set of training tuples and their associated class labels;
•Attribute_list,
the set of candidate attributes;
•Attribute_selection_method,
a procedure to determine the splitting criterion that “best” partitions the data tuples into
individual classes. This criterion consists of a splitting attribute and, possibly, either a split point
or splitting subset.
Data Mining: Classification and Prediction 14
Decision Tree Induction
•Generate_decision_treeAlgorithm
•Method
1.create a node N;
2.if tuples in Dare all of the same class, Cthen
3. return Nas a leaf node labeled with the class C;
4.if Attribute_listis empty then
5. return Nas a leaf node labeled with the majority class in D;
6.apply Attribute_selection_method(D, Attribute_list) to find the “best” splitting
criterion;
7.label node Nwith splitting criterion;
Data Mining: Classification and Prediction 15
•Generate_decision_treeAlgorithm
•Method
1.create a node N;
2.if tuples in Dare all of the same class, Cthen
3. return Nas a leaf node labeled with the class C;
4.if Attribute_listis empty then
5. return Nas a leaf node labeled with the majority class in D;
6.apply Attribute_selection_method(D, Attribute_list) to find the “best” splitting
criterion;
7.label node Nwith splitting criterion;
Data Mining: Classification and Prediction 15
Decision Tree Induction
•Decision Tree Generation Algorithm
•Method
8.if splitting_attributeis discrete-valued and multiway splits allowed then
9. Attribute_list←Attribute_list −Splitting_attribute; // remove splitting attribute
10.for each outcome jof splitting criterion
11.let D
jbe the set of data tuples in Dsatisfying outcome j; // a partition
12.if D
jis empty then
13. attach a leaf labeled with the majority class in D to node N;
14.else attach the node returned by Generate_decision_tree(D
j, attribute_list) to node N;
15.End for
16.return N;
Data Mining: Classification and Prediction 16
•Decision Tree Generation Algorithm
•Method
8.if splitting_attributeis discrete-valued and multiway splits allowed then
9. Attribute_list←Attribute_list −Splitting_attribute; // remove splitting attribute
10.for each outcome jof splitting criterion
11.let D
jbe the set of data tuples in Dsatisfying outcome j; // a partition
12.if D
jis empty then
13. attach a leaf labeled with the majority class in D to node N;
14.else attach the node returned by Generate_decision_tree(D
j, attribute_list) to node N;
15.End for
16.return N;
Data Mining: Classification and Prediction 16
Example
Data Mining: Classification and Prediction 17
Patient IDAge Sex BP CholesterolClass: Drug
P1 <=30 F High Normal Drug A
P2 <=30 F High High Drug A
P3 31…50 F High Normal Drug B
P4 >50 F Normal Normal Drug B
P5 >50 M Low Normal Drug B
P6 >50 M Low High Drug A
P7 31…50 M Low High Drug B
P8 <=30 F Normal Normal Drug A
P9 <=30 M Low Normal Drug B
P10 >50 M Normal Normal Drug B
P11 <=30 M Normal High Drug B
P12 31…50 F Normal High Drug B
P13 31…50 M High Normal Drug B
P14 >50 F Normal High Drug A
P15 31…50 F Low Normal ?
Data Mining: Classification and Prediction 17
Patient IDAge Sex BP CholesterolClass: Drug
P1 <=30 F High Normal Drug A
P2 <=30 F High High Drug A
P3 31…50 F High Normal Drug B
P4 >50 F Normal Normal Drug B
P5 >50 M Low Normal Drug B
P6 >50 M Low High Drug A
P7 31…50 M Low High Drug B
P8 <=30 F Normal Normal Drug A
P9 <=30 M Low Normal Drug B
P10 >50 M Normal Normal Drug B
P11 <=30 M Normal High Drug B
P12 31…50 F Normal High Drug B
P13 31…50 M High Normal Drug B
P14 >50 F Normal High Drug A
P15 31…50 F Low Normal ?
Example
•Reduced Training Data
•Establish the target classification
Which Drug to advice???
•5/14 →Drug A
•9/14 →Drug B
Data Mining: Classification and Prediction 18
Age Gender BP CholesterolClass: Drug
<=30 F High Normal Drug A
<=30 F High High Drug A
31…50 F High Normal Drug B
>50 F Normal Normal Drug B
>50 M Low Normal Drug B
>50 M Low High Drug A
31…50 M Low High Drug B
<=30 F Normal Normal Drug A
<=30 M Low Normal Drug B
>50 M Normal Normal Drug B
<=30 M Normal High Drug B
31…50 F Normal High Drug B
31…50 M High Normal Drug B
>50 F Normal High Drug A
•Reduced Training Data
•Establish the target classification
Which Drug to advice???
•5/14 →Drug A
•9/14 →Drug B
Data Mining: Classification and Prediction 18
Age Gender BP CholesterolClass: Drug
<=30 F High Normal Drug A
<=30 F High High Drug A
31…50 F High Normal Drug B
>50 F Normal Normal Drug B
>50 M Low Normal Drug B
>50 M Low High Drug A
31…50 M Low High Drug B
<=30 F Normal Normal Drug A
<=30 M Low Normal Drug B
>50 M Normal Normal Drug B
<=30 M Normal High Drug B
31…50 F Normal High Drug B
31…50 M High Normal Drug B
>50 F Normal High Drug A
Example
•Calculate Information gain of class attribute: Drug
�����=−
5
14
log
2
5
14
−
9
14
log
2
9
14
�����=0.9403
•Calculate information gain of remaining attributes to determine the root node
Data Mining: Classification and Prediction 19
•Calculate Information gain of class attribute: Drug
�����=−
5
14
log
2
5
14
−
9
14
log
2
9
14
�����=0.9403
•Calculate information gain of remaining attributes to determine the root node
Data Mining: Classification and Prediction 19
Example
•Attribute: Age
•<=30 →5, 31-50 →4, >50 →5
•3 distinct values for attribute Age, so we need to calculate 3 entropy calculations
����
�??????��=�����−ൗ
5
14
����
(≤30)+ൗ
4
14
����
(31−50)+ൗ
5
14
����
(>50)
����
�??????��=�.����
Data Mining: Classification and Prediction 21
<=30: 3-Drug A , 2-Drug B����
(≤30)=−Τ
3
5log
2Τ
3
5−Τ
2
5log
2Τ
2
5 ≈0.9710
31-50: 0-Drug A , 4-Drug B����
(31−50)=−Τ
0
4log
2Τ
0
4−Τ
4
4log
2Τ
4
4 =0
>50 : 2-Drug A , 3-Drug B ����
(>50)=−Τ
2
5log
2Τ
2
5−Τ
3
5log
2Τ
3
5 ≈0.9710
•Attribute: Age
•<=30 →5, 31-50 →4, >50 →5
•3 distinct values for attribute Age, so we need to calculate 3 entropy calculations
����
�??????��=�����−ൗ
5
14
����
(≤30)+ൗ
4
14
����
(31−50)+ൗ
5
14
����
(>50)
����
�??????��=�.����
Data Mining: Classification and Prediction 21
<=30: 3-Drug A , 2-Drug B����
(≤30)=−Τ
3
5log
2Τ
3
5−Τ
2
5log
2Τ
2
5 ≈0.9710
31-50: 0-Drug A , 4-Drug B����
(31−50)=−Τ
0
4log
2Τ
0
4−Τ
4
4log
2Τ
4
4 =0
>50 : 2-Drug A , 3-Drug B ����
(>50)=−Τ
2
5log
2Τ
2
5−Τ
3
5log
2Τ
3
5 ≈0.9710
Example
•Attribute: Gender
•M→7, F→7
•2 distinct values for attribute Gender, so we need to calculate 2 entropy calculations
����
�������=�����−ൗ
7
14
����
�+ൗ
17
14
����
�
����
�������=0.9403−0.7885=�.����
Data Mining: Classification and Prediction 23
F: 4 Drug A, 3 drug B����
��=−Τ
4
7log
2Τ
4
7−Τ
3
7log
2
Τ
3
7 ≈0.9852
M: 1 Drug A, 6 drug B����
��=−Τ
1
7log
2Τ
1
7−Τ
6
7log
2
Τ
6
7 ≈0.5917
•Attribute: Gender
•M→7, F→7
•2 distinct values for attribute Gender, so we need to calculate 2 entropy calculations
����
�������=�����−ൗ
7
14
����
�+ൗ
17
14
����
�
����
�������=0.9403−0.7885=�.����
Data Mining: Classification and Prediction 23
F: 4 Drug A, 3 drug B����
��=−Τ
4
7log
2Τ
4
7−Τ
3
7log
2
Τ
3
7 ≈0.9852
M: 1 Drug A, 6 drug B����
��=−Τ
1
7log
2Τ
1
7−Τ
6
7log
2
Τ
6
7 ≈0.5917
Example
•Attribute: BP
•High→4 , Normal→6 , Low→4
•3 distinct values for attribute BP, so we need to calculate 3 entropy calculations
����
�??????�=�����−ൗ
4
14
����
��??????ℎ+ൗ
6
14
����
����??????�+ൗ
4
14
����
���
����
�??????�=0.9403−0.9111=�.����
Data Mining: Classification and Prediction 25
High: 2-Drug A , 2-Drug B ����
(��??????ℎ)=−Τ
2
4log
2Τ
2
4−Τ
2
4log
2Τ
2
4 ≈1.00
Normal: 2-Drug A , 4-Drug B����
(����??????�)=−Τ
2
6log
2Τ
2
6−Τ
4
6log
2Τ
4
6 =0.9183
Low: 1-Drug A , 3-Drug B ����
(���)=−Τ
1
4log
2Τ
1
4−Τ
3
4log
2Τ
3
4 ≈0.8113
•Attribute: BP
•High→4 , Normal→6 , Low→4
•3 distinct values for attribute BP, so we need to calculate 3 entropy calculations
����
�??????�=�����−ൗ
4
14
����
��??????ℎ+ൗ
6
14
����
����??????�+ൗ
4
14
����
���
����
�??????�=0.9403−0.9111=�.����
Data Mining: Classification and Prediction 25
High: 2-Drug A , 2-Drug B ����
(��??????ℎ)=−Τ
2
4log
2Τ
2
4−Τ
2
4log
2Τ
2
4 ≈1.00
Normal: 2-Drug A , 4-Drug B����
(����??????�)=−Τ
2
6log
2Τ
2
6−Τ
4
6log
2Τ
4
6 =0.9183
Low: 1-Drug A , 3-Drug B ����
(���)=−Τ
1
4log
2Τ
1
4−Τ
3
4log
2Τ
3
4 ≈0.8113
Data Mining: Classification and Prediction 26
CholesterolClass: Drug
High Drug A
High Drug A
High Drug B
High Drug B
High Drug B
High Drug A
CholesterolClass: Drug
Normal Drug A
Normal Drug B
Normal Drug B
Normal Drug B
Normal Drug A
Normal Drug B
Normal Drug B
Normal Drug B
CholesterolClass: Drug
High Drug A
High Drug A
High Drug B
High Drug B
High Drug B
High Drug A
CholesterolClass: Drug
Normal Drug A
Normal Drug B
Normal Drug B
Normal Drug B
Normal Drug A
Normal Drug B
Normal Drug B
Normal Drug B
Example
•Attribute: Cholesterol
•High→6 , Normal →8
•2 distinct values for attribute Cholesterol, so we need to calculate 2 entropy calculations
����
�ℎ����������=�����−ൗ
6
14
����
(��??????ℎ)+ൗ
8
14
����
(����??????�)
����
�ℎ����������=0.9403−0.8922=�.����
Data Mining: Classification and Prediction 27
High: 3-Drug A , 3-Drug B ����
(��??????ℎ)=−Τ
3
6log
2Τ
3
6−Τ
3
6log
2Τ
3
6 =1.00
Normal: 2-Drug A , 6-Drug B����
(����??????�)=−Τ
2
8log
2Τ
2
8−Τ
6
8log
2Τ
6
8 ≈0.8113
•Attribute: Cholesterol
•High→6 , Normal →8
•2 distinct values for attribute Cholesterol, so we need to calculate 2 entropy calculations
����
�ℎ����������=�����−ൗ
6
14
����
(��??????ℎ)+ൗ
8
14
����
(����??????�)
����
�ℎ����������=0.9403−0.8922=�.����
Data Mining: Classification and Prediction 27
High: 3-Drug A , 3-Drug B ����
(��??????ℎ)=−Τ
3
6log
2Τ
3
6−Τ
3
6log
2Τ
3
6 =1.00
Normal: 2-Drug A , 6-Drug B����
(����??????�)=−Τ
2
8log
2Τ
2
8−Τ
6
8log
2Τ
6
8 ≈0.8113
Example
•Recap
•We choose Age being a rootnode.
Data Mining: Classification and Prediction 29
����
�??????��0.2467
����
�������0.1519
����
�??????�0.0292
����
�ℎ����������0.0481
����
����0.2467
����
�������0.1519
����
�??????�0.0292
����
�ℎ����������0.0481
Age
<=30 31-50 >50
Drug B? ?
Repeat the steps
•Recap
•We choose Age being a rootnode.
Data Mining: Classification and Prediction 29
����
�??????��0.2467
����
�������0.1519
����
�??????�0.0292
����
�ℎ����������0.0481
����
����0.2467
����
�������0.1519
����
�??????�0.0292
����
�ℎ����������0.0481
Age
<=30 31-50 >50
Drug B? ?
Repeat the steps
Example
Data Mining: Classification and Prediction 30
Age
<=30 31-50 >50
Drug B? ?
Gender
Male Female
Drug B Drug A
Cholesterol
Male
Normal High
Drug B
Drug A
Data Mining: Classification and Prediction 30
Age
<=30 31-50 >50
Drug B? ?
Gender
Male Female
Drug B Drug A
Cholesterol
Male
Normal High
Drug B
Drug A
Decision Tree Induction
•What if the splitting attribute �is continuous-valued?
•The test at node N has two possible outcomes, corresponding to the conditions �≤
�����_�����and �>�����_�����, respectively
•where �����_�����is the split-point returned by Attribute selection method as part of the
splitting criterion.
•When A is discrete-valued and a binary tree must be produced
•The test at node N is of the form “�∈�
�”,
•where �
�is the splitting subset for �returned by Attribute selection method as part of the
splitting criterion.
Data Mining: Classification and Prediction 31
•What if the splitting attribute �is continuous-valued?
•The test at node N has two possible outcomes, corresponding to the conditions �≤
�����_�����and �>�����_�����, respectively
•where �����_�����is the split-point returned by Attribute selection method as part of the
splitting criterion.
•When A is discrete-valued and a binary tree must be produced
•The test at node N is of the form “�∈�
�”,
•where �
�is the splitting subset for �returned by Attribute selection method as part of the
splitting criterion.
Data Mining: Classification and Prediction 31
Decision Tree Induction
Data Mining: Classification and Prediction 32
1
2 3
Data Mining: Classification and Prediction 32
1
2 3
Attribute Selection Measures
•Gain Ratio
•The information gain measure is biased toward tests with many outcomes.
•C4.5, a successor of ID3, uses an extension to information gain known as gain ratio
•Applies a kind of normalization to information gain using a “split information” value defined
analogously with Info(D) as
���������
�=−
�=1
�
|�
�|
|�|
×log
2
|�
�|
|�|
•This represents the potential information generated by splitting the training data set, �, into �
partitions, corresponding to the �outcomes of a test on attribute �.
•The gain ratio is defined as
����������=
����(�)
���������(�)
•The attribute with the maximum gain ratio is selected as the splitting attribute.
Data Mining: Classification and Prediction 33
•Gain Ratio
•The information gain measure is biased toward tests with many outcomes.
•C4.5, a successor of ID3, uses an extension to information gain known as gain ratio
•Applies a kind of normalization to information gain using a “split information” value defined
analogously with Info(D) as
���������
�=−
�=1
�
|�
�|
|�|
×log
2
|�
�|
|�|
•This represents the potential information generated by splitting the training data set, �, into �
partitions, corresponding to the �outcomes of a test on attribute �.
•The gain ratio is defined as
����������=
����(�)
���������(�)
•The attribute with the maximum gain ratio is selected as the splitting attribute.
Data Mining: Classification and Prediction 33
Attribute Selection Measures
•Gain Ratio
•Computation of gain ratio for the attribute weight.
•Attribute: Weight has three values as Heavy, Average and Light containing 5, 6 and 4 tuples
respectively.
���������
�=−
5
15
×log
2
5
15
−
6
15
×log
2
6
15
−
4
15
×log
2
4
15
=1.5655
��������ℎ�=0.0622
�������������ℎ�=
0.0622
1.5655
=0.040
Data Mining: Classification and Prediction 34
•Gain Ratio
•Computation of gain ratio for the attribute weight.
•Attribute: Weight has three values as Heavy, Average and Light containing 5, 6 and 4 tuples
respectively.
���������
�=−
5
15
×log
2
5
15
−
6
15
×log
2
6
15
−
4
15
×log
2
4
15
=1.5655
��������ℎ�=0.0622
�������������ℎ�=
0.0622
1.5655
=0.040
Data Mining: Classification and Prediction 34
Attribute Selection Measures
•Gini Index
•The Gini index is used in CART
•The Gini index measures the impurity of �, a data partition or set of training tuples, as
�����=1−
�=1
�
�
�
2
•where �
�is the probability that a tuple in �belongs to class �
�and is estimated by ൗ
|�
??????,??????|
|�|
.
•The sum is computed over �classes.
•The Gini index considers a binary split for each attribute
•If a binary split on A partitions D into D1 and D2, the Gini index of D given that partitioning
is
����
��=
|�
1|
|�|
����(�
1)+
�
2
�
����(�
2)
Data Mining: Classification and Prediction 35
•Gini Index
•The Gini index is used in CART
•The Gini index measures the impurity of �, a data partition or set of training tuples, as
�����=1−
�=1
�
�
�
2
•where �
�is the probability that a tuple in �belongs to class �
�and is estimated by ൗ
|�
??????,??????|
|�|
.
•The sum is computed over �classes.
•The Gini index considers a binary split for each attribute
•If a binary split on A partitions D into D1 and D2, the Gini index of D given that partitioning
is
����
��=
|�
1|
|�|
����(�
1)+
�
2
�
����(�
2)
Data Mining: Classification and Prediction 35
Attribute Selection Measures
•Gini Index
•For a discrete-valued attribute, the subset that gives the minimum giniindex for
that attribute is selected as its splitting subset.
•For continuous-valued attributes, each possible split-point must be considered.
•The reduction in impurity that would be incurred by a binary split on a discrete-
or continuous-valued attribute A is
Δ�����=�����−����
��
•The attribute that maximizes the reduction in impurity is selected as the splitting attribute.
Data Mining: Classification and Prediction 36
•Gini Index
•For a discrete-valued attribute, the subset that gives the minimum giniindex for
that attribute is selected as its splitting subset.
•For continuous-valued attributes, each possible split-point must be considered.
•The reduction in impurity that would be incurred by a binary split on a discrete-
or continuous-valued attribute A is
Δ�����=�����−����
��
•The attribute that maximizes the reduction in impurity is selected as the splitting attribute.
Data Mining: Classification and Prediction 36
Data Mining: Classification and Prediction 37
Data Mining: Classification and Prediction 38
Bayesian Classification
•Bayesian classifiers are statistical classifiers
•Predicts class membership probabilities.
•based on Bayes’ theorem.
•Exhibits high accuracy and speed when applied to large databases.
•A simple Bayesian classifier is known as the naïve Bayesian classifier
•Assumes that the effect of an attribute value on a given class is independent of the values of
the other attributes: class conditional independence.
•Bayesian belief networks are graphical models, allow the representation of
dependencies among subsets of attributes
Data Mining: Classification and Prediction 39
•Bayesian classifiers are statistical classifiers
•Predicts class membership probabilities.
•based on Bayes’ theorem.
•Exhibits high accuracy and speed when applied to large databases.
•A simple Bayesian classifier is known as the naïve Bayesian classifier
•Assumes that the effect of an attribute value on a given class is independent of the values of
the other attributes: class conditional independence.
•Bayesian belief networks are graphical models, allow the representation of
dependencies among subsets of attributes
Data Mining: Classification and Prediction 39
Bayesian Classification
•Bayes’ Theorem
•Let ??????be a data tuple (X is considered “evidence”).
•Let �be some hypothesis, such as that the data tuple ??????belongs to a specified class �.
•Determine ??????�|??????, the probability that the hypothesis �holds given the “evidence” or
observed data tuple X.
•??????�|??????is the posteriorprobability of �conditioned on X.
•??????�is the priorprobability of �.
•????????????|�is the posteriorprobability of ??????conditioned on H.
•????????????is the priorprobability of ??????.
•“How are these probabilities estimated?”
Data Mining: Classification and Prediction 40
??????�|??????=
????????????|�??????�
????????????
…Bayes’ Theorem
•Bayes’ Theorem
•Let ??????be a data tuple (X is considered “evidence”).
•Let �be some hypothesis, such as that the data tuple ??????belongs to a specified class �.
•Determine ??????�|??????, the probability that the hypothesis �holds given the “evidence” or
observed data tuple X.
•??????�|??????is the posteriorprobability of �conditioned on X.
•??????�is the priorprobability of �.
•????????????|�is the posteriorprobability of ??????conditioned on H.
•????????????is the priorprobability of ??????.
•“How are these probabilities estimated?”
Data Mining: Classification and Prediction 40
??????�|??????=
????????????|�??????�
????????????
…Bayes’ Theorem
Naïve Bayesian Classification
•A simple Bayesian classifier is known as the naïve Bayesian classifier
•Assumes that the effect of an attribute value on a given class is independent of
the values of the other attributes: class conditional independence.
•It is made to simplify the computations involved and, in this sense, is
considered “naïve.”
Data Mining: Classification and Prediction 41
•A simple Bayesian classifier is known as the naïve Bayesian classifier
•Assumes that the effect of an attribute value on a given class is independent of
the values of the other attributes: class conditional independence.
•It is made to simplify the computations involved and, in this sense, is
considered “naïve.”
Data Mining: Classification and Prediction 41
Naïve Bayesian Classification
•Let �be a training set of tuples and their associated class labels.
•Suppose that there are m classes, �
1,�
2,…�
�.
•Given a tuple, �=(�
1,�
2,…,�
�)depicting �measurements made on the tuple from �
attributes, the classifier will predict that �belongs to the class having the highest
posterior probability, conditioned on �.
•The naïve Bayesian classifier predicts that tuple X belongs to the class �
�if and only if
??????�
�|�>??????�
�|����1≤�≤�,�≠�
•We maximize ??????�
�|�
•The class �
�for which ??????�
�|�is maximized is called the maximum posteriori
hypothesis.
Data Mining: Classification and Prediction 42
•Let �be a training set of tuples and their associated class labels.
•Suppose that there are m classes, �
1,�
2,…�
�.
•Given a tuple, �=(�
1,�
2,…,�
�)depicting �measurements made on the tuple from �
attributes, the classifier will predict that �belongs to the class having the highest
posterior probability, conditioned on �.
•The naïve Bayesian classifier predicts that tuple X belongs to the class �
�if and only if
??????�
�|�>??????�
�|����1≤�≤�,�≠�
•We maximize ??????�
�|�
•The class �
�for which ??????�
�|�is maximized is called the maximum posteriori
hypothesis.
Data Mining: Classification and Prediction 42
Naïve Bayesian Classification
•By Bayes’ theorem
??????�
�|??????=
????????????|�
�??????�
�
????????????
•As ??????�is constant for all classes, only ??????�|�
�??????�
�need be maximized.
•The naïve Bayesian classifier predicts that tuple X belongs to the class Ci if and only if
??????�
�|�>??????�
�|����1≤�≤�,�≠�
•The class �
�for which ??????�
�|�is maximized is called the maximum posteriori
hypothesis.
•The class prior probabilities may be estimated by
??????�
�=
�
�,�
�
……�ℎ����
�,����ℎ�������������������������������
����
Data Mining: Classification and Prediction 43
•By Bayes’ theorem
??????�
�|??????=
????????????|�
�??????�
�
????????????
•As ??????�is constant for all classes, only ??????�|�
�??????�
�need be maximized.
•The naïve Bayesian classifier predicts that tuple X belongs to the class Ci if and only if
??????�
�|�>??????�
�|����1≤�≤�,�≠�
•The class �
�for which ??????�
�|�is maximized is called the maximum posteriori
hypothesis.
•The class prior probabilities may be estimated by
??????�
�=
�
�,�
�
……�ℎ����
�,����ℎ�������������������������������
����
Data Mining: Classification and Prediction 43
Naïve Bayesian Classification
•In order to reduce computation in evaluating ??????�|�
�, the naive assumption of class
conditional independence is made.
????????????|�
�=ෑ
�=�
�
??????�
�|�
�=??????�
�|�
�×??????�
�|�
�×⋯×??????�
�|�
�
•Bayesian classifiers have the minimum error rate in comparison to all other classifiers.
Data Mining: Classification and Prediction 44
•In order to reduce computation in evaluating ??????�|�
�, the naive assumption of class
conditional independence is made.
????????????|�
�=ෑ
�=�
�
??????�
�|�
�=??????�
�|�
�×??????�
�|�
�×⋯×??????�
�|�
�
•Bayesian classifiers have the minimum error rate in comparison to all other classifiers.
Data Mining: Classification and Prediction 44
Naïve Bayesian Classification: Example
RID age incomestudentcredit_ratingclass: Buys_computer
1 youth high no fair no
2 youth high no excellent no
3middle_agedhigh no fair yes
4 seniormedium no fair yes
5 senior low yes fair yes
6 senior low yes excellent no
7middle_agedlow yes excellent yes
8 youth medium no fair no
9 youth low yes fair yes
10 seniormedium yes fair yes
11 youth medium yes excellent yes
12middle_agedmedium no excellent yes
13middle_agedhigh yes fair yes
14 seniormedium no excellent no
Data Mining: Classification and Prediction 45
RID age incomestudentcredit_ratingclass: Buys_computer
1 youth high no fair no
2 youth high no excellent no
3middle_agedhigh no fair yes
4 seniormedium no fair yes
5 senior low yes fair yes
6 senior low yes excellent no
7middle_agedlow yes excellent yes
8 youth medium no fair no
9 youth low yes fair yes
10 seniormedium yes fair yes
11 youth medium yes excellent yes
12middle_agedmedium no excellent yes
13middle_agedhigh yes fair yes
14 seniormedium no excellent no
Data Mining: Classification and Prediction 45
Naïve Bayesian Classification: Example
Data Mining: Classification and Prediction 46
•Let �
1be the �����:����_�������r=���and �
2be the �����:����_�������r=��
•The tuple we wish to classify is
�=(���=����ℎ,������=������,�������=���,������������=����)
•We need to maximize ??????�|�
�??????�
�, for �=1,2
•Calculate ??????�
�, for �=1,2
•??????����_��������=���=
•??????����_��������=��=
•Calculate ??????�|�
�, for �=1,2
9/14 = 0.643
5/14 = 0.357
Data Mining: Classification and Prediction 46
•Let �
1be the �����:����_�������r=���and �
2be the �����:����_�������r=��
•The tuple we wish to classify is
�=(���=����ℎ,������=������,�������=���,������������=����)
•We need to maximize ??????�|�
�??????�
�, for �=1,2
•Calculate ??????�
�, for �=1,2
•??????����_��������=���=
•??????����_��������=��=
•Calculate ??????�|�
�, for �=1,2
9/14 = 0.643
5/14 = 0.357
Naïve Bayesian Classification: Example
RID age incomestudentcredit_ratingclass: Buys_computer
1 youth high no fair no
2 youth high no excellent no
3middle_agedhigh no fair yes
4 seniormedium no fair yes
5 senior low yes fair yes
6 senior low yes excellent no
7middle_agedlow yes excellent yes
8 youth medium no fair no
9 youth low yes fair yes
10 seniormedium yes fair yes
11 youth medium yes excellent yes
12middle_agedmedium no excellent yes
13middle_agedhigh yes fair yes
14 seniormedium no excellent no
Data Mining: Classification and Prediction 47
RID age incomestudentcredit_ratingclass: Buys_computer
1 youth high no fair no
2 youth high no excellent no
3middle_agedhigh no fair yes
4 seniormedium no fair yes
5 senior low yes fair yes
6 senior low yes excellent no
7middle_agedlow yes excellent yes
8 youth medium no fair no
9 youth low yes fair yes
10 seniormedium yes fair yes
11 youth medium yes excellent yes
12middle_agedmedium no excellent yes
13middle_agedhigh yes fair yes
14 seniormedium no excellent no
Data Mining: Classification and Prediction 47
Naïve Bayesian Classification: Example
Data Mining: Classification and Prediction 48
•Calculate ??????�|�
�, for �=1,2
•??????�
1|�
1=??????(���=����ℎ|����_��������=���)
•??????�
1|�
2=??????(���=����ℎ|����_��������=��)
•??????�
2|�
1=??????(������=������|����_��������=���)
•??????�
2|�
2=??????(������=������|����_��������=��)
•??????�
3|�
1=??????(�������=���|����_��������=���)
•??????�
3|�
2=??????(�������=���|����_��������=��)
•??????�
4|�
1=??????(������������=����|����_��������=���)
•??????�
4|�
2=??????(������������=����|����_��������=��)
= 2/9 = 0.222
= 3/5 = 0.600
= 4/9 = 0.444
= 2/5 = 0.400
= 6/9 = 0.667
= 1/5 = 0.200
= 6/9= 0.667
= 2/5 = 0.400
�=(���=����ℎ,������=������,�������=���,������������=����)
Data Mining: Classification and Prediction 48
•Calculate ??????�|�
�, for �=1,2
•??????�
1|�
1=??????(���=����ℎ|����_��������=���)
•??????�
1|�
2=??????(���=����ℎ|����_��������=��)
•??????�
2|�
1=??????(������=������|����_��������=���)
•??????�
2|�
2=??????(������=������|����_��������=��)
•??????�
3|�
1=??????(�������=���|����_��������=���)
•??????�
3|�
2=??????(�������=���|����_��������=��)
•??????�
4|�
1=??????(������������=����|����_��������=���)
•??????�
4|�
2=??????(������������=����|����_��������=��)
= 2/9 = 0.222
= 3/5 = 0.600
= 4/9 = 0.444
= 2/5 = 0.400
= 6/9 = 0.667
= 1/5 = 0.200
= 6/9= 0.667
= 2/5 = 0.400
�=(���=����ℎ,������=������,�������=���,������������=����)
Naïve Bayesian Classification: Example
Data Mining: Classification and Prediction 49
•Now we calculate from above probabilities
??????(�|����_��������=���)=0.222×0.444×0.667×0.667
Similarly
??????(�|����_��������=��)=0.600×0.400×0.200×0.400
•To find the class, �
�, that maximizes ??????�|�
�??????�
�, we compute
??????(�|����_��������=���)??????����_��������=���=
??????(�|����_��������=��)??????����_��������=��=
•Therefore, the naïve Bayesian classifier predicts, ����_��������=���for
tuple �.
=0.044
=0.019
0.028
0.007
Data Mining: Classification and Prediction 49
•Now we calculate from above probabilities
??????(�|����_��������=���)=0.222×0.444×0.667×0.667
Similarly
??????(�|����_��������=��)=0.600×0.400×0.200×0.400
•To find the class, �
�, that maximizes ??????�|�
�??????�
�, we compute
??????(�|����_��������=���)??????����_��������=���=
??????(�|����_��������=��)??????����_��������=��=
•Therefore, the naïve Bayesian classifier predicts, ����_��������=���for
tuple �.
=0.044
=0.019
0.028
0.007
Naïve Bayesian Classification: Example
RID age incomestudentcredit_ratingclass: Buys_computer
1 youth high no fair no
2 youth high no excellent no
3middle_agedhigh no fair yes
4 seniormedium no fair yes
5 senior low yes fair yes
6 senior low yes excellent yes
7middle_agedlow yes excellent yes
8 youthmedium no fair no
9 youth low yes fair yes
10 seniormediumyes fair yes
11 youthmediumyes excellent yes
12middle_agedmedium no excellent yes
13middle_agedhigh yes fair yes
14 seniormedium no excellent no
Data Mining: Classification and Prediction 50
Calculate ??????�
�, for �=1,2
??????����_��������=���=
10/14 = 0.714
??????����_��������=��=
4/14 = 0.286
RID age incomestudentcredit_ratingclass: Buys_computer
1 youth high no fair no
2 youth high no excellent no
3middle_agedhigh no fair yes
4 seniormedium no fair yes
5 senior low yes fair yes
6 senior low yes excellent yes
7middle_agedlow yes excellent yes
8 youthmedium no fair no
9 youth low yes fair yes
10 seniormediumyes fair yes
11 youthmediumyes excellent yes
12middle_agedmedium no excellent yes
13middle_agedhigh yes fair yes
14 seniormedium no excellent no
Data Mining: Classification and Prediction 50
Calculate ??????�
�, for �=1,2
??????����_��������=���=
10/14 = 0.714
??????����_��������=��=
4/14 = 0.286
Naïve Bayesian Classification: Example
Data Mining: Classification and Prediction 51
•Calculate ??????�|�
�, for �=1,2
•??????�
1|�
1=??????(���=����ℎ|����_��������=���)
•??????�
1|�
2=??????(���=����ℎ|����_��������=��)
•??????�
2|�
1=??????(������=������|����_��������=���)
•??????�
2|�
2=??????(������=������|����_��������=���)
•??????�
3|�
1=??????(�������=���|����_��������=���)
•??????�
3|�
2=??????(�������=���|����_��������=��)
•??????�
4|�
1=??????(������������=����|����_��������=���)
•??????�
4|�
2=??????(������������=����|����_��������=��)
= 2/10 = 0.200
= 3/4 = 0.750
= 4/10 = 0.400
= 2/4 = 0.500
= 7/10= 0.700
= 0/5 = 0
= 6/10 = 0.600
= 2/4 = 0.500
Data Mining: Classification and Prediction 51
•Calculate ??????�|�
�, for �=1,2
•??????�
1|�
1=??????(���=����ℎ|����_��������=���)
•??????�
1|�
2=??????(���=����ℎ|����_��������=��)
•??????�
2|�
1=??????(������=������|����_��������=���)
•??????�
2|�
2=??????(������=������|����_��������=���)
•??????�
3|�
1=??????(�������=���|����_��������=���)
•??????�
3|�
2=??????(�������=���|����_��������=��)
•??????�
4|�
1=??????(������������=����|����_��������=���)
•??????�
4|�
2=??????(������������=����|����_��������=��)
= 2/10 = 0.200
= 3/4 = 0.750
= 4/10 = 0.400
= 2/4 = 0.500
= 7/10= 0.700
= 0/5 = 0
= 6/10 = 0.600
= 2/4 = 0.500
Naïve Bayesian Classification: Example
Data Mining: Classification and Prediction 52
•Now we calculate from above probabilities
??????(�|����_��������=���)=0.200×0.400×0.700×0.600
Similarly
??????(�|����_��������=��)=0.750×0.500×0×0.500
•To find the class, �
�, that maximizes ??????�|�
�??????�
�, we compute
??????(�|����_��������=���)??????����_��������=���=
??????(�|����_��������=��)??????����_��������=��=
•Therefore, the naïve Bayesian classifier predicts, ����_��������=���for
tuple �.
=0.034
=0
0.024
0
IS IT CORRECT CLASSIFICATION ??????????
Data Mining: Classification and Prediction 52
•Now we calculate from above probabilities
??????(�|����_��������=���)=0.200×0.400×0.700×0.600
Similarly
??????(�|����_��������=��)=0.750×0.500×0×0.500
•To find the class, �
�, that maximizes ??????�|�
�??????�
�, we compute
??????(�|����_��������=���)??????����_��������=���=
??????(�|����_��������=��)??????����_��������=��=
•Therefore, the naïve Bayesian classifier predicts, ����_��������=���for
tuple �.
=0.034
=0
0.024
0
IS IT CORRECT CLASSIFICATION ??????????
Naïve Bayesian Classification
Data Mining: Classification and Prediction 53
•A zero probability cancels the effects of all of the other (posteriori) probabilities
(on �
�) involved in the product.
•To avoid the effect of zero probability value, Laplacian correction or Laplace
estimatoris used.
•We add one to each count.
Data Mining: Classification and Prediction 53
•A zero probability cancels the effects of all of the other (posteriori) probabilities
(on �
�) involved in the product.
•To avoid the effect of zero probability value, Laplacian correction or Laplace
estimatoris used.
•We add one to each count.
Naïve Bayesian Classification
Data Mining: Classification and Prediction 54
•E.g. If we have a training database D having 1500 tuples.
•Out of which, 1000 tuples are of class Buys_computer= yes.
•For income attribute we have
•0 tuples for income = low,
•960 tuple for income = medium,
•40 tuples for income = high.
•Using the Laplacian correction for the three quantities, we pretend that we have 1 extra tuple for
each income-valuepair.
1
1003
=0.001,
961
1003
=0.958,
41
1003
=0.040
•The “corrected” probability estimates are close to their “uncorrected” counterparts, yet the zero
probability value is avoided.
Data Mining: Classification and Prediction 54
•E.g. If we have a training database D having 1500 tuples.
•Out of which, 1000 tuples are of class Buys_computer= yes.
•For income attribute we have
•0 tuples for income = low,
•960 tuple for income = medium,
•40 tuples for income = high.
•Using the Laplacian correction for the three quantities, we pretend that we have 1 extra tuple for
each income-valuepair.
1
1003
=0.001,
961
1003
=0.958,
41
1003
=0.040
•The “corrected” probability estimates are close to their “uncorrected” counterparts, yet the zero
probability value is avoided.
Rule-Based Classification
•The learned model is represented as a set of IF-THEN rules.
•An IF-THEN rule is an expression of the form
�����������??????�������������
•Example: �1:�����=����ℎ����������=�����������
��������=���
•R1 can also be written as
�1:(���=����ℎ)∧(�������=���)⇒(����_��������=���)
Data Mining: Classification and Prediction 55
Rule antecedent
or precondition
Rule consequent
Attribute sets Class Prediction
•The learned model is represented as a set of IF-THEN rules.
•An IF-THEN rule is an expression of the form
�����������??????�������������
•Example: �1:�����=����ℎ����������=�����������
��������=���
•R1 can also be written as
�1:(���=����ℎ)∧(�������=���)⇒(����_��������=���)
Data Mining: Classification and Prediction 55
Rule antecedent
or precondition
Rule consequent
Attribute sets Class Prediction
Rule-Based Classification
•If the condition in a rule antecedent holds true for a given tuple, the rule antecedent is
satisfiedand that the rule coversthe tuple.
•Evaluation of Rule R:
���������=
�
������
|�|
���������=
�
�������
�
������
•Let �
������be the number of tuples covered by R
•�
�������be the number of tuples correctly classified by R
•|�|be the number of tuples in D.
Data Mining: Classification and Prediction 56
•If the condition in a rule antecedent holds true for a given tuple, the rule antecedent is
satisfiedand that the rule coversthe tuple.
•Evaluation of Rule R:
���������=
�
������
|�|
���������=
�
�������
�
������
•Let �
������be the number of tuples covered by R
•�
�������be the number of tuples correctly classified by R
•|�|be the number of tuples in D.
Data Mining: Classification and Prediction 56
Naïve Bayesian Classification: Example
RID age incomestudentcredit_ratingclass: Buys_computer
1 youth high no fair no
2 youth high no excellent no
8 youthmedium no fair no
9 youth low yes fair yes
11 youthmediumyes excellent yes
12middle_agedmedium no excellent yes
13middle_agedhigh yes fair yes
14 seniormedium no excellent no
Data Mining: Classification and Prediction 57
RID age incomestudentcredit_ratingclass: Buys_computer
1 youth high no fair no
2 youth high no excellent no
8 youthmedium no fair no
9 youth low yes fair yes
11 youthmediumyes excellent yes
12middle_agedmedium no excellent yes
13middle_agedhigh yes fair yes
14 seniormedium no excellent no
Data Mining: Classification and Prediction 57
Rule-Based Classification
•If a rule is satisfiedby X, the rule is said to be triggered.
X=(age=youth,income=medium,student=yes,creditrating=fair)
•Xsatisfies the rule R1, which triggers the rule.
•If R1 is the only rule satisfied, then the rule firesby returning the class prediction for X.
•If more than one rule is triggered, we need a conflict resolution strategy.
•Size ordering: assigns the highest priority to the triggering rule that has the “toughest”
requirements
•Rule ordering: prioritizes the rules beforehand. The ordering may be class-based or rule-
based.
•Class-based ordering: the classes are sorted in order of decreasing “importance”
•Rule-based ordering, the rules are organized into one long priority list
Data Mining: Classification and Prediction 58
•If a rule is satisfiedby X, the rule is said to be triggered.
X=(age=youth,income=medium,student=yes,creditrating=fair)
•Xsatisfies the rule R1, which triggers the rule.
•If R1 is the only rule satisfied, then the rule firesby returning the class prediction for X.
•If more than one rule is triggered, we need a conflict resolution strategy.
•Size ordering: assigns the highest priority to the triggering rule that has the “toughest”
requirements
•Rule ordering: prioritizes the rules beforehand. The ordering may be class-based or rule-
based.
•Class-based ordering: the classes are sorted in order of decreasing “importance”
•Rule-based ordering, the rules are organized into one long priority list
Data Mining: Classification and Prediction 58
Rule-Based Classification
•Extracting rules from a decision tree
•One rule is created for each path from the root to a leaf node.
•Each splitting criterion along a given path is logically ANDed to form the rule
antecedent (“IF” part).
•The leaf node holds the class prediction, forming the rule consequent (“THEN”
part).
Data Mining: Classification and Prediction 59
•Extracting rules from a decision tree
•One rule is created for each path from the root to a leaf node.
•Each splitting criterion along a given path is logically ANDed to form the rule
antecedent (“IF” part).
•The leaf node holds the class prediction, forming the rule consequent (“THEN”
part).
Data Mining: Classification and Prediction 59
Rule-Based Classification
•Extracting rules from a decision tree
Data Mining: Classification and Prediction 60
age?
student? credit_rating?yes
middle_aged
youth
senior
no yes no yes
no yes fair excellent
•Extracting rules from a decision tree
Data Mining: Classification and Prediction 60
age?
student? credit_rating?yes
middle_aged
youth
senior
no yes no yes
no yes fair excellent
Rule-Based Classification
•Extracted rules from a decision tree are
�1:�����=���������������_������=�����������������_��������=���
�2:�����=���������������_������=������������_��������=no
�3:�����=������_������������_��������=���
�4:�����=����ℎ���student=yes ��������_��������=���
�5:�����=����ℎ���student=����������_��������=no
Data Mining: Classification and Prediction 61
•Extracted rules from a decision tree are
�1:�����=���������������_������=�����������������_��������=���
�2:�����=���������������_������=������������_��������=no
�3:�����=������_������������_��������=���
�4:�����=����ℎ���student=yes ��������_��������=���
�5:�����=����ℎ���student=����������_��������=no
Data Mining: Classification and Prediction 61
Data Mining: Classification and Prediction 62
Extract the classification rule from given decision tree
Extract the classification rule from given decision tree
Data Mining: Classification and Prediction 63
X=(Color=Yellow, Type = SUV, Origin = Imported)
X=(Color=Yellow, Type = SUV, Origin = Imported)
Prediction
•Numeric prediction is the task of predicting continuous (or ordered) values for
given input.
•Widely used approach for numeric prediction is regression.
•Regression is used to model the relationship between one or more independent
or predictorvariables and a dependentor responsevariable.
•The predictor variables are the attributes of interest describing the tuple.
•The response variable is what we want to predict.
Data Mining: Classification and Prediction 64
Predictor Variables Response Variable
�={age=youth,"income=medium,student=yes,creditrating=fair",Buys_computer=?}
•Numeric prediction is the task of predicting continuous (or ordered) values for
given input.
•Widely used approach for numeric prediction is regression.
•Regression is used to model the relationship between one or more independent
or predictorvariables and a dependentor responsevariable.
•The predictor variables are the attributes of interest describing the tuple.
•The response variable is what we want to predict.
Data Mining: Classification and Prediction 64
Predictor Variables Response Variable
�={age=youth,"income=medium,student=yes,creditrating=fair",Buys_computer=?}
Prediction: Linear Regression
•Straight-line regression analysis involves a response variable,�, and a single
predictor variable, �.
•Simplest regression technique which models �as a linear function of �.
�=�+��
•�and �are regression coefficients specifying the Y-intercept and slope of the line.
•Coefficients can also be thought as weights
�=�
0+�
1�
•These coefficients can be solved for by the method of least squares, which estimates
the best-fitting straight line as the one that minimizes the error between the actual
data and the estimate of the line.
Data Mining: Classification and Prediction 65
•Straight-line regression analysis involves a response variable,�, and a single
predictor variable, �.
•Simplest regression technique which models �as a linear function of �.
�=�+��
•�and �are regression coefficients specifying the Y-intercept and slope of the line.
•Coefficients can also be thought as weights
�=�
0+�
1�
•These coefficients can be solved for by the method of least squares, which estimates
the best-fitting straight line as the one that minimizes the error between the actual
data and the estimate of the line.
Data Mining: Classification and Prediction 65
Prediction: Linear Regression
•The regression coefficients can be estimated
�
1=
σ
�=1
|�|
�
�−ҧ��
�−ത�
σ
�=1
|�|
�
�−ҧ�
2
�
0=ത�−�
1ҧ�
Data Mining: Classification and Prediction 66
•The regression coefficients can be estimated
�
1=
σ
�=1
|�|
�
�−ҧ��
�−ത�
σ
�=1
|�|
�
�−ҧ�
2
�
0=ത�−�
1ҧ�
Data Mining: Classification and Prediction 66
Prediction: Linear Regression
Age
(x)
Avg. amount spent on
medical expenses
(per month in Rs.) (y)
15 100
20 135
25 135
37 150
40 250
45 270
48 290
50 360
55 375
61 400
64 500
67 1000
70 1500
Data Mining: Classification and Prediction 67
ҧ�=45.92
ത�=412.69
The regression coefficients are
�
1=16.89
�
0=−355.32
The equation of the least square (best fitting) line is
�=−355.32+16.89�
Age
(x)
Avg. amount spent on
medical expenses
(per month in Rs.) (y)
15 100
20 135
25 135
37 150
40 250
45 270
48 290
50 360
55 375
61 400
64 500
67 1000
70 1500
Data Mining: Classification and Prediction 67
ҧ�=45.92
ത�=412.69
The regression coefficients are
�
1=16.89
�
0=−355.32
The equation of the least square (best fitting) line is
�=−355.32+16.89�
Prediction: Linear Regression
Age
(x)
Avg. amount spent on
medical expenses
(per month in Rs.) (y)
15 100
20 135
25 135
37 150
40 250
45 270
48 290
50 360
55 375
61 400
64 500
67 1000
70 1500
Data Mining: Classification and Prediction 68
y = 16.891x -355.32
-200
0
200
400
600
800
1000
1200
1400
1600
0 10 20 30 40 50 60 70 80
Avg. amount spent on medical expenses (per month in Rs.) (y)
Age
(x)
Avg. amount spent on
medical expenses
(per month in Rs.) (y)
15 100
20 135
25 135
37 150
40 250
45 270
48 290
50 360
55 375
61 400
64 500
67 1000
70 1500
Data Mining: Classification and Prediction 68
y = 16.891x -355.32
-200
0
200
400
600
800
1000
1200
1400
1600
0 10 20 30 40 50 60 70 80
Avg. amount spent on medical expenses (per month in Rs.) (y)
Classifier Accuracy Measures
Data Mining: Classification and Prediction 69
•Confusion Matrix:
•Given �classes, a confusion matrix is a table of at least size �by �
•where an entry is row �and column �shows the number of tuples of class �that were
labeled by the classifier as class �.
Data Mining: Classification and Prediction 69
•Confusion Matrix:
•Given �classes, a confusion matrix is a table of at least size �by �
•where an entry is row �and column �shows the number of tuples of class �that were
labeled by the classifier as class �.
Class –Low Class –Medium Class -High
Class –Low 250 10 0
Class –Medium 10 440 10
Class -High 0 10 270
Data Mining: Classification and Prediction 70
1000 tuples
Class –Low 250 10 0
Class –Medium 10 440 10
Class -High 0 10 270
Data Mining: Classification and Prediction 70
1000 tuples
Classifier Accuracy Measures
Data Mining: Classification and Prediction 71
•Classifier Accuracy
•The percentage of test set tuples that are correctly classified by the classifier.
•Also referred to as the overall recognition rate of the classifier.
•Error Measure
•An error rate or misclassification rate of a classifier M, which is simply
1−����
where ���(�)is the accuracy of M.
Data Mining: Classification and Prediction 71
•Classifier Accuracy
•The percentage of test set tuples that are correctly classified by the classifier.
•Also referred to as the overall recognition rate of the classifier.
•Error Measure
•An error rate or misclassification rate of a classifier M, which is simply
1−����
where ���(�)is the accuracy of M.
Classifier Accuracy Measures
Data Mining: Classification and Prediction 72
•Confusion Matrix: Given 2 classes
•Positive tuples:
•tuples of the main class of interest
•Negative tuples:
•True Positive:
•The positive tuples that were correctly labeled by the classifier
•True negatives
•The negative tuples that were correctly labeled by the classifier
•False positives
•The negative tuples that were incorrectly labeled
•False negatives
•The positive tuples that were incorrectly labeled
Data Mining: Classification and Prediction 72
•Confusion Matrix: Given 2 classes
•Positive tuples:
•tuples of the main class of interest
•Negative tuples:
•True Positive:
•The positive tuples that were correctly labeled by the classifier
•True negatives
•The negative tuples that were correctly labeled by the classifier
•False positives
•The negative tuples that were incorrectly labeled
•False negatives
•The positive tuples that were incorrectly labeled
Classifier Accuracy Measures
Data Mining: Classification and Prediction 73
•We would like to be able to access how well the classifier can recognize the
positive tuples and how well it can recognize the negative tuples.
•Sensitivity(true positive (recognition) rate)
•The proportion of positive tuples that are correctly identified.
�����������=
�_���
���
•Specificity(true negative rate)
•The proportion of negative tuples that are correctly identified.
�����������=
�_���
���
•Precision
??????��������=
�_���
(�_���+�_���)
Data Mining: Classification and Prediction 73
•We would like to be able to access how well the classifier can recognize the
positive tuples and how well it can recognize the negative tuples.
•Sensitivity(true positive (recognition) rate)
•The proportion of positive tuples that are correctly identified.
�����������=
�_���
���
•Specificity(true negative rate)
•The proportion of negative tuples that are correctly identified.
�����������=
�_���
���
•Precision
??????��������=
�_���
(�_���+�_���)
Classifier Accuracy Measures
Data Mining: Classification and Prediction 74
•It can be shown that accuracy is a function of sensitivity and specificity.
��������=�����������×
���
���+���
+�����������×
���
���+���
��������=
�
���+�
��??????
�������.��������
Data Mining: Classification and Prediction 74
•It can be shown that accuracy is a function of sensitivity and specificity.
��������=�����������×
���
���+���
+�����������×
���
���+���
��������=
�
���+�
��??????
�������.��������
Predictor Accuracy Measures
Data Mining: Classification and Prediction 75
•Instead of focusing on whether the predicted value �′
�is an “exact” match with actual
value �
�, we check how far off the predicted value is from the actual known value.
•Loss functions measures the error between the actual value �
�and the predicted value
�′
�.
�������������:�
�−�′
�
������������:(�
�−�′
�)
�
•The test error (rate), or generalization error, is the average loss over the test set.
�����������������=
σ
�=�
�
�
�−�′
�
�
����������������=
σ
�=�
�
(�
�−�′
�)
�
�
•If we were to take the square root of the mean squared error, the resulting error measure
is called the root mean squared error.
Data Mining: Classification and Prediction 75
•Instead of focusing on whether the predicted value �′
�is an “exact” match with actual
value �
�, we check how far off the predicted value is from the actual known value.
•Loss functions measures the error between the actual value �
�and the predicted value
�′
�.
�������������:�
�−�′
�
������������:(�
�−�′
�)
�
•The test error (rate), or generalization error, is the average loss over the test set.
�����������������=
σ
�=�
�
�
�−�′
�
�
����������������=
σ
�=�
�
(�
�−�′
�)
�
�
•If we were to take the square root of the mean squared error, the resulting error measure
is called the root mean squared error.
Predictor Accuracy Measures
Data Mining: Classification and Prediction 76
•Relative measures of error include
??????��������������������=
σ
�=�
�
�
�−�′
�
σ
�=�
�
�
�−ഥ�
??????�������������������=
σ
�=�
�
(�
�−�′
�)
�
σ
�=�
�
(�
�−ഥ�)
�
•We can take the root of the relative squared error to obtain the root relative squared
error so that the resulting error is of the same magnitude as the quantity predicted.
Data Mining: Classification and Prediction 76
•Relative measures of error include
??????��������������������=
σ
�=�
�
�
�−�′
�
σ
�=�
�
�
�−ഥ�
??????�������������������=
σ
�=�
�
(�
�−�′
�)
�
σ
�=�
�
(�
�−ഥ�)
�
•We can take the root of the relative squared error to obtain the root relative squared
error so that the resulting error is of the same magnitude as the quantity predicted.
Accuracy Measures
Data Mining: Classification and Prediction 77
•Evaluating the Accuracy of a Classifier or Predictor
Holdout
Random Subsampling
Cross Validation
Bootstrap
Data Mining: Classification and Prediction 77
•Evaluating the Accuracy of a Classifier or Predictor
Holdout
Random Subsampling
Cross Validation
Bootstrap
Accuracy Measures
Data Mining: Classification and Prediction 78
•Holdout
•The given data are randomly partitioned into two independent sets, a training set and a
test set.
•Two-thirds of the data are allocated to the training set, and the remaining one-third is
allocated to the test set.
Data
Training
set
Test set
Derive model
Estimate
Accuracy
Data Mining: Classification and Prediction 78
•Holdout
•The given data are randomly partitioned into two independent sets, a training set and a
test set.
•Two-thirds of the data are allocated to the training set, and the remaining one-third is
allocated to the test set.
Data
Training
set
Test set
Derive model
Estimate
Accuracy
Accuracy Measures
Data Mining: Classification and Prediction 79
•Random Subsampling
•A variation of the holdout method in which the holdout method is repeated �times.
•The overall accuracy estimate is taken as the average of the accuracies obtained from
each iteration
Data
Training
set 1
Test set
1
Derive model
Estimate
Accuracy
Data
Training
set 2
Test set
2
Derive model
Estimate
Accuracy
Data
Training
set k
Test set
k
Derive model
Estimate
Accuracy
Iteration 1
Iteration 2 Iteration k. . .
Data Mining: Classification and Prediction 79
•Random Subsampling
•A variation of the holdout method in which the holdout method is repeated �times.
•The overall accuracy estimate is taken as the average of the accuracies obtained from
each iteration
Data
Training
set 1
Test set
1
Derive model
Estimate
Accuracy
Data
Training
set 2
Test set
2
Derive model
Estimate
Accuracy
Data
Training
set k
Test set
k
Derive model
Estimate
Accuracy
Iteration 1
Iteration 2 Iteration k. . .
Accuracy Measures
Data Mining: Classification and Prediction 80
•Cross Validation
Data
�
2 �
3�
1 �
�
�
2
�
3
�
1
�
�
…
�
2
�
3
�
1
�
�
…
�
2
�
3
�
1
�
�
…
Iteration 1Iteration 2Iteration3 Iteration �
�mutually exclusive folds
i.e.�data partitions
. . .
�
2
�
3
�
1
�
�
…
Training Set Test Set
Data Mining: Classification and Prediction 80
•Cross Validation
Data
�
2 �
3�
1 �
�
�
2
�
3
�
1
�
�
…
�
2
�
3
�
1
�
�
…
�
2
�
3
�
1
�
�
…
Iteration 1Iteration 2Iteration3 Iteration �
�mutually exclusive folds
i.e.�data partitions
. . .
�
2
�
3
�
1
�
�
…
Training Set Test Set
Accuracy Measures
Data Mining: Classification and Prediction 81
•Cross Validation
•Each sample is used the same number of times for training and once for testing.
•For Classification, the accuracy estimate is the overall number of correct classifications
from the k iterations, divided by the total number of tuples in the initial data.
•For Prediction, the error estimate can be computed as the total loss from the k iterations,
divided by the total number of initial tuples.
•Leave-one-out
•�is set to the number of initial tuples. So, only one sample is “left out” at a time for the test set.
•Stratified cross-validation
•The folds are stratified so that the class distribution of the tuples in each fold is approximately
the same as that in the initial data
Data Mining: Classification and Prediction 81
•Cross Validation
•Each sample is used the same number of times for training and once for testing.
•For Classification, the accuracy estimate is the overall number of correct classifications
from the k iterations, divided by the total number of tuples in the initial data.
•For Prediction, the error estimate can be computed as the total loss from the k iterations,
divided by the total number of initial tuples.
•Leave-one-out
•�is set to the number of initial tuples. So, only one sample is “left out” at a time for the test set.
•Stratified cross-validation
•The folds are stratified so that the class distribution of the tuples in each fold is approximately
the same as that in the initial data
Accuracy Measures
Data Mining: Classification and Prediction 82
•Bootstrap
•The bootstrap method samples the given training tuples uniformly with replacement.
•i.e. each time a tuple is selected, it is equally likely to be selected again and readded to the
training set.
•.632 Bootstrap
•On an average, 63.2% of the original data tuples will end up in the bootstrap, and the remaining
36.8% will form the test set
•Each tuple has a probability of Τ
1
�of being selected, so the probability of not being chosen is (1−
Τ
1
�).
•We have to select �times, so the probability that a tuple will not be chosen during this whole time is
(1−Τ
1
�)
�
.
•If �is large, the probability approaches e
−1
=0.368.
•Thus, 36.8% of tuples will not be selected for training and thereby end up in the test set, and the
remaining 63.2% will form the training set.
Data Mining: Classification and Prediction 82
•Bootstrap
•The bootstrap method samples the given training tuples uniformly with replacement.
•i.e. each time a tuple is selected, it is equally likely to be selected again and readded to the
training set.
•.632 Bootstrap
•On an average, 63.2% of the original data tuples will end up in the bootstrap, and the remaining
36.8% will form the test set
•Each tuple has a probability of Τ
1
�of being selected, so the probability of not being chosen is (1−
Τ
1
�).
•We have to select �times, so the probability that a tuple will not be chosen during this whole time is
(1−Τ
1
�)
�
.
•If �is large, the probability approaches e
−1
=0.368.
•Thus, 36.8% of tuples will not be selected for training and thereby end up in the test set, and the
remaining 63.2% will form the training set.
Accuracy Measures
Data Mining: Classification and Prediction 83
•Bootstrap
•.632 Bootstrap
•Repeat the sampling procedure �times, where in each iteration, we use the current test set to
obtain an accuracy estimate of the model obtained from the current bootstrap sample.
•The overall accuracy of the model is
����=
�=1
�
0.632���(�
�)
����_���+0.368���(�
�)
��??????��_���
Data Mining: Classification and Prediction 83
•Bootstrap
•.632 Bootstrap
•Repeat the sampling procedure �times, where in each iteration, we use the current test set to
obtain an accuracy estimate of the model obtained from the current bootstrap sample.
•The overall accuracy of the model is
����=
�=1
�
0.632���(�
�)
����_���+0.368���(�
�)
��??????��_���
Download
Download Slideshow Get the original presentation fileQuick Actions
Statistics
- Views 2,037
- Slides 79
- Age 1219 days
Related Slideshows
11
TLE-9-Prepare-Salad-and-Dressing.pptxkkk
MaAngelicaCanceran
31 views
12
LESSON 1 ABOUT MEDIA AND INFORMATION.pptx
JojitGueta
24 views
60
GRADE-8-AQUACULTURE-WEEKQ1.pdfdfawgwyrsewru
MaAngelicaCanceran
39 views
26
Feelings PP Game FOR CHILDREN IN ELEMENTARY SCHOOL.pptx
KaistaGlow
39 views
![Jeopardy_Figures_of_Speech_Template.pptx [Autosaved].pptx](https://slidepub.com/thumb/5828/284015828.jpg)
54
Jeopardy_Figures_of_Speech_Template.pptx [Autosaved].pptx
acecamero20
23 views
7
Jeopardy_Figures_of_Speech.pptxvdsvdsvsdvsd
acecamero20
24 views