Adama Science & Technology

University
SoEEC:CS
Data Mining
Classification
Chapter 4

1
1
 Lecture Outlines
• Classification Methods

1. General Introduction
2. Decision Trees
3. Rule based classifiers
4. Bayesian Classification

2
 General Introduction

• Classification Definition

• Supervised vs Unsupervised

• What is classification? What is prediction?

• Typical Applications

• Classification Tasks

• Data Preparation

• Performance Evaluation
3
 General Introduction
• Given a collection of records (training set )
– Each record contains a set of attributes, one of the attributes is the class.
• Find a model for class attribute as a function of the values of other attributes.

• Definition: Given a database D={t1,t2,..,tn} and a set of classes C= {c1, c2, …, cm},
Classification problems is to define a mapping f : D→C, where each ti is
assigned to one class. That is, Classification is the task of learning a target
function f (-also known as classification model ) that maps each attribute set ti
to one of the predefined class ci .

• Goal: previously unseen records should be assigned a class as accurately as

possible.
– A test set is used to determine the accuracy of the model. Usually, the
given data set is divided into training and test sets, with training set used
to build the model and test set used to validate it.

4
 Classification vs. Prediction
• Classification
– predicts categorical class labels (discrete or nominal)
– classifies data (constructs a model) based on the training set and
the values (class labels) in a classifying attribute and uses it in
classifying new data
• Descriptive Modeling: A classification model
can serve as an explanatory tool to distinguish
between objects of different classes. e.g.
vertebrate data set.
• Prediction
– models continuous-valued functions, i.e., predicts unknown or
missing values
• Predictive Modeling: A classification model can
also be used to predict the class label of
unknown records.
5
PART 1: General Introduction

6
General Introduction

7
 General Introduction

• Supervised learning (classification)

– Supervision: The training data (observations,
measurements, etc.) are accompanied by labels indicating
the class of the observations
– New data is classified based on the training set

• Unsupervised learning (clustering)

– The class labels of training data is unknown
– Given a set of measurements, observations, etc. with the
aim of establishing the existence of classes or clusters in the
data
8
 General Introduction -Applications

• Medical Diagnosis: Predicting tumor cells as

benign or malignant

• Fraud Detection: Market Classifying credit

card transactions as legitimate or fraudulent

• Credit Approval: Bank Loans

• Classifying secondary structures of protein as

alpha-helix, beta-sheet, or random coil

• Categorizing news stories as finance, weather,

entertainment, sports, etc

9
 PART 1: General Introduction- Classification Task

• Classification Task —A Two-Step Process:

– Model Construction
– Model Usage

• Model construction: describing a set of predetermined

classes
– Each tuple/sample is assumed to belong to a predefined
class, as determined by the class label attribute.
– The set of tuples used for model construction is training
set
– The model is represented as classification rules, decision
trees, or mathematical formulae
10
 PART 1: General Introduction- Classification Task

Model Construction:
Classification
Algorithms
Training
Data

NAME RANK YEARS TENURED Classifier

Genet Assistant Prof 3 no (Model)
Mary Assistant Prof 7 yes
Wake Professor 12 yes
Kedir Associate Prof 7 yes IF rank = ‘professor’
Awel Assistant Prof 6 no OR years > 6
Ayele Associate Prof 3 no
THEN tenured = ‘yes’
11
 General Introduction- Classification Task

• Model usage: for classifying future or unknown objects

– 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 test set samples that are
correctly classified by the model
• Test set is independent of training set, otherwise over-fitting
will occur
– If the accuracy is acceptable, use the model to classify data
tuples whose class labels are not known

12
 General Introduction- Classification Task

Model Usage in Prediction:

Classifier

Testing
Data Unseen Data

(Dereje, Assi, Professor,8)

NAME RANK YEARS TENURED
Tesfaye Assistant Prof 2 no Tenured?
Eden Associate Prof 7 yes
Ferew Professor 9 yes
Feleke Assistant Prof 7 yes 13
 General Introduction- Classification Task

Figure : The data classification process: (a) Learning : Training data are analyzed by a
classification algorithm. Her the class label attribute is credit_rating, and the learned model or
classifier is represented in the form of classification rules.
14
 General Introduction- Classification Task

b) Classification: Test data are used to estimate the accuracy of the classification rules. If
the accuracy is considered acceptable, the rules can be applied to the classification of new
data tuples.
15
 General Introduction- Classification Task
Another Illustration of Classification Model:

Tid Attrib1 Attrib2 Attrib3 Class Learning

No
1 Yes Large 125K
algorithm
2 No Medium 100K No
3 No Small 70K No
4 Yes Medium 120K No
Induction
5 No Large 95K Yes
6 No Medium 60K No
7 Yes Large 220K No Learn
8 No Small 85K Yes Model
9 No Medium 75K No
10 No Small 90K Yes
Model
10

Training Set
Apply
Tid Attrib1 Attrib2 Attrib3 Class Model
11 No Small 55K ?
12 Yes Medium 80K ?
13 Yes Large 110K ? Deduction
14 No Small 95K ?

15 No Large 67K ?
10

Test Set

16
 General Introduction - Data Preparation

• Data cleaning
– Preprocess data in order to reduce noise and handle
missing values

• Relevance analysis (feature selection)

– Remove the irrelevant or redundant attributes

• Data transformation
– Generalize and/or normalize data

17
 General Introduction - Performance Evaluation

Predicted Class

Table-2; Confusion Matrix

Class = 1 Class =0
for a 2-class problem Actual Class =1 F11 F10
Class
Class = 0 F01 F00

Number of correct predictions F00 + F11

Accuracy = ---------------------------------- = -------------------
Total Number of predictions F 00 + F01 + F10 + F11

Number of wrong predictions F01 + F10

Error Rate = ----------------------------------- = -------------------------
Total Number of predictions F00 + F01 + F10 + F11

18
 General Introduction- Performance Evaluation
• Accuracy
– classifier accuracy: predicting class label
– predictor accuracy: guessing value of predicted attributes

• Speed
– time to construct the model (training time)
– time to use the model (classification/prediction time)

• Robustness: handling noise and missing values

• Scalability: efficiency in disk-resident databases

• Interpretability
– understanding and insight provided by the model
• Other measures, e.g., goodness of rules, such as decision tree size or
compactness of classification rules.
19
 Part 2: Decision Trees
• What is a Decision Tree?
• Decision Tree Induction Algorithms
• Building of a Decision Tree
• Choosing Splitting Attribute
• Evaluation of DT
– Information Gain
– Gini Index
– Gain Ratio
– Misclassification Error
• Overfitting & Underfitting
• Pruning

20
 What is a Decision Tree?
A decision tree is a flow-chart-like tree structure, where each
internal node denotes a test on an attribute, each branch
represents an outcome of the test, and leaf nodes
represent classes or class distribution.

• Definition: Given a database D = {t1,…,tn} where ti=(ti1,…,tih},

a set of classes C = { C1,…,Cm}, and attributes {A1,A2,…,Ah}, a
decision tree (DT) or classification tree is a tree associated
with D that has the following properties:

– Each internal node is a labeled with an attribute Ai

– Each arc (or edge) is labeled with a predicate that can be applied to the attribute
associated with the parent

– Each leaf node is labeled with a class Cj

21
 What is a Decision Tree?

A decision tree has three types of nodes:

o A root node that has no incoming edges and zero or more outgoing
edges.
o Internal nodes, each of which has exactly one incoming edge and two
or more outgoing edges.
o Leaf or terminal node, each of which has exactly one incoming and no
outgoing edges.

• Solving the classification problem using DT is a

two-step process:
1) Decision Tree Induction- Construct a DT using training data
2) For each ti є D, apply the DT to determine its class
22
 Table-3: The vertebrate data set.
Name Body Skin Gives Aquatic Aerial Has Hiber- Class
Temperature Cover Birth Creature Creature Legs nates label
human warm-blooded hair yes no no yes no mammal
python cold-blooded scales no no no no yes reptile
salmon cold-blooded scales no yes no no no fish
whale warm-blooded hair yes yes no no no mammal
frog cold-blooded none no semi no yes yes amphibian
komodo cold-blooded scales no no no yes no reptile
dragon
bat warm-blooded hair yes no yes yes yes mammal
pigeon warm-blooded feathers no no yes yes no bird
cat warm-blooded fur yes no no yes no mammal
leopard cold-blooded scales yes yes no no no fish
shark
turtle cold-blooded scales no semi no yes no reptile
penguin warm-blooded feathers no semi no yes no bird
porcupine warm-blooded quills yes no no yes yes mammal
eel cold-blooded scales no yes no no no fish
salamander cold-blooded none no semi no yes yes amphibian

23
 What is a Decision Tree?
Body
Root node
Temperature

Gives Non-
Internal
Birth Mammals
node

Mammals Non-
Mammals Figure :
A decision tree for the
Mammal classification
problem
Leaf Nodes
24
 What is a Decision Tree?
Name Body Gives Birth ….. Class
Unlabeled data temperature
Flamingo Warm NO …. ?

Body
Temperature
Warm Cold

Gives Non-
Birth Mammals
No
Yes

Non-
Mammals Mammals

Figure : Classifying an unlabeled vertebrate. The dashed lines represent the outcomes of applying various attribute test conditions on the
unlabeled vertebrate. The vertebrate is eventually assigned to the Non-mammal class.

25
 Decision Tree- An Example
Tid Attrib1 Attrib2 Attrib3 Class
Tree
1 Yes Large 125K No Induction
2 No Medium 100K No algorithm
3 No Small 70K No

4 Yes Medium 120K No

Induction
5 No Large 95K Yes

6 No Medium 60K No

7 Yes Large 220K No Learn

8 No Small 85K Yes Model
9 No Medium 75K No

10 No Small 90K Yes

Model
10

Training Set
Apply
Model Decision
Tid Attrib1 Attrib2 Attrib3 Class
?
Tree
11 No Small 55K
12 Yes Medium 80K ?

13 Yes Large 110K ?

Deduction
14 No Small 95K ?

15 No Large 67K ?
10

Test Set

26
 Decision Tree –An Example(contd..)
l l us
ri ca ri ca uo
o o in
teg teg n t a ss
c a c a co c l
Tid Refund Marital Taxable
Splitting Attributes
Status Income Cheat

1 Yes Single 125K No

2 No Married 100K No Refund
3 No Single 70K No
Yes No
4 Yes Married 120K No NO MarSt
5 No Divorced 95K Yes Married
Single, Divorced
6 No Married 60K No
7 Yes Divorced 220K No TaxInc NO
8 No Single 85K Yes < 80K > 80K
9 No Married 75K No
NO YES
10 No Single 90K Yes
10

Training Data Model: Decision Tree

27
Decision Tree –An Example (contd..)
a l a l us
o ric o ric uo
eg eg tin ss
t t n la Single,
c a c a co c MarSt
Married Divorced
Tid Refund Marital Taxable
Status Income Cheat
NO Refund
1 Yes Single 125K No
Yes No
2 No Married 100K No
3 No Single 70K No NO TaxInc
4 Yes Married 120K No < 80K > 80K
5 No Divorced 95K Yes
NO YES
6 No Married 60K No
7 Yes Divorced 220K No
8 No Single 85K Yes
9 No Married 75K No There could be more than one tree that fits
10 No Single 90K Yes the same data!
10

28
Decision Tree –An Example (contd..)
Tid Attrib1 Attrib2 Attrib3 Class
Tree
1 Yes Large 125K No Induction
2 No Medium 100K No algorithm
3 No Small 70K No

4 Yes Medium 120K No

Induction
5 No Large 95K Yes

6 No Medium 60K No

7 Yes Large 220K No Learn

8 No Small 85K Yes Model
9 No Medium 75K No

10 No Small 90K Yes

Model
10

Training Set
Apply
Model Decision
Tid Attrib1 Attrib2 Attrib3 Class
Tree
11 No Small 55K ?

12 Yes Medium 80K ?

13 Yes Large 110K ?

Deduction
14 No Small 95K ?

15 No Large 67K ?
10

Test Set

29
 Decision Tree –An Example (contd..)
Apply Model to Test Data
Test Data
Start from the root of tree. Refund Marital Taxable
Status Income Cheat

No Married 80K ?
Refund 10

Yes No

NO MarSt
Single, Divorced Married

TaxInc NO
< 80K > 80K

NO YES

30
 Decision Tree –An Example (contd..)
Apply Model to Test Data Test Data
Refund Marital Taxable
Status Income Cheat

No Married 80K ?
Refund 10

Yes No

NO MarSt
Single, Divorced Married

TaxInc NO
< 80K > 80K

NO YES

31
 Decision Tree –An Example (contd..)
Apply Model to Test Data Test Data
Refund Marital Taxable
Status Income Cheat

No Married 80K ?
Refund 10

Yes No

NO MarSt
Single, Divorced Married

TaxInc NO
< 80K > 80K

NO YES

32
 Decision Tree –An Example (contd..)
Apply Model to Test Data Test Data
Refund Marital Taxable
Status Income Cheat

No Married 80K ?
Refund 10

Yes No

NO MarSt
Single, Divorced Married

TaxInc NO
< 80K > 80K

NO YES

33
 Decision Tree –An Example (contd..)
Apply Model to Test Data Test Data
Refund Marital Taxable
Status Income Cheat

No Married 80K ?
Refund 10

Yes No

NO MarSt
Single, Divorced Married

TaxInc NO
< 80K > 80K

NO YES

34
 Decision Tree –An Example (contd..)
Test Data
Apply Model to Test Data Refund Marital Taxable
Status Income Cheat

No Married 80K ?
Refund 10

Yes No

NO MarSt
Single, Divorced Married Assign Cheat to
“No”
TaxInc NO
< 80K > 80K

NO YES

35
 Decision Tree -Another Illustration
Table-4: Training dataset for ‘buys_computer’ example

age income student credit_rating buys_computer

<=30 high no fair no
<=30 high no excellent no
31…40 high no fair yes
>40 medium no fair yes
>40 low yes fair yes
>40 low yes excellent no
31…40 low yes excellent yes
<=30 medium no fair no
<=30 low yes fair yes
>40 medium yes fair yes
<=30 medium yes excellent yes
31…40 medium no excellent yes
31…40 high yes fair yes
>40 medium no excellent no

36
 Decision Tree -Another Illustration
Output: A Decision Tree for “buys_computer”

age?

<=30 overcast
31..40 >40

student? yes credit rating?

no yes excellent fair

no yes no yes

37
Decision Tree -Another Illustration

38
 Decision Tree Induction
• Many Algorithms:
– Hunt’s Algorithm (one of the earliest)

– ID3(Induction Decision Tree ver. 3),

– C4.5, C5.0 by Ross Quinlan [Link].

– CART (Classification And Regression Tree)

– CHAID (Chi-square Automatic Interaction Detection)

39
 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
40
Decision Tree Induction Algorithm

41
 Choosing the Splitting Attribute
• At each node, available attributes are evaluated on the basis of
separating the classes of the training examples. An evaluation
(goodness) function is used for this purpose.

• Typical evaluation functions:

– information gain (ID3/C4.5)

– information gain ratio

– gini index (CART)

42
 Computing information
• Information is measured in bits
– Given a probability distribution, the info required to predict an
event is the distribution’s entropy
– Entropy gives the information required in bits (this can involve
fractions of bits!)
• Formula for computing the entropy:
entropy( p1 , p2 , , pn )  p1logp1  p2 logp2   pn logpn

43
 Attribute Selection Measure:
Information Gain (ID3/C4.5)
 Select the attribute with the highest information
gain
 Let pi be the probability that an arbitrary tuple in D
belongs to class Ci, estimated by |Ci, D|/|D|
m
 Expected information (entropy) needed
Info( D )  to (classify
  pi log 2 pi )
a tuple in D: i 1

 Information after split (afterInfo

using A to |D
v
j |
split D into v
partitions) to classify D: A ( D )  j 1 | D | I ( D j )

 Information gained by branching on attribute A

Gain(A) Info(D)  Info A(D)
44
 Attribute Selection: Information Gain
 Class P: buys_computer = “yes” 5 4
Infoage ( D )  I (2,3)  I (4,0)
 Class N: buys_computer = “no” 14 14
9 9 5 5 5
Info( D) I (9,5)  log 2 ( )  log 2 ( ) 0.940  I (3,2) 0.694
14 14 14 14 14
age pi ni I(p i, n i)
5
<=30 2 3 0.971 I (2,3) means “age <=30” has 5 out of 14
14
31…40 4 0 0 samples, with 2 yes’es and 3 no’s.
>40 3 2 0.971 Hence
age income student credit_rating buys_computer Gain(age) Info( D)  Infoage ( D) 0.246
<=30 high no fair no
<=30 high no excellent no
31…40
>40
high
medium
no
no
fair
fair
yes
yes Similarly,
>40 low yes fair yes
>40 low yes excellent no Gain(income) 0.029
31…40 low yes excellent yes
<=30
<=30
medium
low
no
yes
fair
fair
no
yes
Gain( student ) 0.151
>40
<=30
medium
medium
yes
yes
fair
excellent
yes
yes Gain(credit _ rating ) 0.048
31…40 medium no excellent yes
31…40 high yes fair yes
>40 medium no excellent no
45
 A criterion for attribute selection
• Which is the best attribute?
– The one which will result in the smallest tree
– Heuristic: choose the attribute that produces the “purest”
nodes
• Popular impurity criterion: information gain
– Information gain increases with the average purity of the
subsets that an attribute produces
• Strategy: choose attribute that results in greatest information
gain
• DT example

46
 Rule Extraction from a Decision Tree age?
 Rules are easier to understand than large trees
<=30 31..40
 One rule is created for each path from the root >40

to a leaf student? credit rating?

yes
 Each attribute-value pair along a path forms a no yes excellent fair

conjunction: the leaf holds the class prediction no yes no yes

 Rules are mutually exclusive and exhaustive

• Example: Rule extraction from our buys computer decision-tree

IF age = young AND student = no THEN buys computer = no
IF age = young AND student = yes THEN buys computer = yes
IF age = mid-age THEN buys computer = yes
IF age = old AND credit rating = fair THEN buys computer = yes
IF age = young AND credit rating = Excellent THEN buys computer = no
 Rule-based Classifier (Example)
Name Blood Type Give Birth Can Fly Live in Water Class
human warm yes no no mammals
python cold no no no reptiles
salmon cold no no yes fishes
whale warm yes no yes mammals
frog cold no no sometimes amphibians
komodo cold no no no reptiles
bat warm yes yes no mammals
pigeon warm no yes no birds
cat warm yes no no mammals
leopard shark cold yes no yes fishes
turtle cold no no sometimes reptiles
penguin warm no no sometimes birds
porcupine warm yes no no mammals
eel cold no no yes fishes
salamander cold no no sometimes amphibians
gila monster cold no no no reptiles
platypus warm no no no mammals
owl warm no yes no birds
dolphin warm yes no yes mammals
eagle warm no yes no birds

R1: (Give Birth = no)  (Can Fly = yes)  Birds

R2: (Give Birth = no)  (Live in Water = yes)  Fishes
R3: (Give Birth = yes)  (Blood Type = warm)  Mammals
R4: (Give Birth = no)  (Can Fly = no)  Reptiles
R5: (Live in Water = sometimes)  Amphibians
 Application of Rule-Based Classifier
• A rule r covers an instance x if the attributes of the instance
satisfy the condition of the rule
R1: (Give Birth = no)  (Can Fly = yes)  Birds
R2: (Give Birth = no)  (Live in Water = yes)  Fishes
R3: (Give Birth = yes)  (Blood Type = warm)  Mammals
R4: (Give Birth = no)  (Can Fly = no)  Reptiles
R5: (Live in Water = sometimes)  Amphibians

Name Blood Type Give Birth Can Fly Live in Water Class
hawk warm no yes no ?
grizzly bear warm yes no no ?

The rule R1 covers a hawk => Bird

The rule R3 covers the grizzly bear => Mammal
 What is Bayesian Classification?

• Bayesian classifiers are statistical classifiers

• For each new sample they provide a
probability that the sample belongs to a
class (for all classes)
 Bayes’ Theorem: Basics
• Let X be a data sample (“evidence”): class label is unknown
• Let H be a hypothesis that X belongs to class C
• Classification is to determine P(H|X), the probability that the hypothesis holds
given the observed data sample X
• P(H) (prior probability), the initial probability
– E.g., X will buy computer, regardless of age, income, …
• P(X): probability that sample data is observed

• P(X|H) (posteriori probability), the probability of observing the sample X,

given that the hypothesis holds
– E.g., Given that X will buy computer, the prob. that X is 31..40, medium income
 Classification Part II:
Bayes’ Theorem
• Given training data X, posteriori probability of a hypothesis H,
P(H|X), follows the Bayes theorem

P( H | X) P(X | H ) P( H )
P(X)
 Towards Naïve Bayesian Classifiers
• Let D be a training set of tuples and their associated class labels,
and each tuple is represented by an n-D attribute vector X = (x1, x2,
…, xn)
• Suppose there are m classes C1, C2, …, Cm.
• Classification is to derive the maximum posteriori, i.e., the
maximal P(Ci|X)
• This can be derived from Bayes’ theorem

P(X | C )P(C )
P(C | X)  i i
i P(X)
• Since P(X) is constant for all classes, only

needs to be maximized P(C | X) P(X | C )P(C )

i i i
 NBC: Training Dataset
age income studentcredit_rating
buys_compu
<=30 high no fair no
<=30 high no excellent no
Class: 31…40 high no fair yes
C1:buys_computer = >40 medium no fair yes
‘yes’ >40 low yes fair yes
C2:buys_computer = >40 low yes excellent no
31…40 low yes excellent yes
‘no’
<=30 medium no fair no
<=30 low yes fair yes
Data sample >40 medium yes fair yes
X = (age <=30, <=30 medium yes excellent yes
Income = medium, 31…40 medium no excellent yes
Student = yes 31…40 high yes fair yes
Credit_rating = Fair) >40 medium no excellent no
 NBC: An Example
• P(Ci): P(buys_computer = “yes”) = 9/14 = 0.643
P(buys_computer = “no”) = 5/14= 0.357

• Compute P(X|Ci) for each class

P(age = “<=30” | buys_computer = “yes”) = 2/9 = 0.222
P(age = “<= 30” | buys_computer = “no”) = 3/5 = 0.6
P(income = “medium” | buys_computer = “yes”) = 4/9 = 0.444
P(income = “medium” | buys_computer = “no”) = 2/5 = 0.4
P(student = “yes” | buys_computer = “yes) = 6/9 = 0.667
P(student = “yes” | buys_computer = “no”) = 1/5 = 0.2
P(credit_rating = “fair” | buys_computer = “yes”) = 6/9 = 0.667
P(credit_rating = “fair” | buys_computer = “no”) = 2/5 = 0.4

• X = (age <= 30 , income = medium, student = yes, credit_rating = fair)

P(X|Ci) : P(X|buys_computer = “yes”) = 0.222 x 0.444 x 0.667 x 0.667 = 0.044

P(X|buys_computer = “no”) = 0.6 x 0.4 x 0.2 x 0.4 = 0.019
P(X|Ci)*P(Ci) : P(X|buys_computer = “yes”) * P(buys_computer = “yes”) = 0.028
P(X|buys_computer = “no”) * P(buys_computer = “no”) = 0.007

Therefore, X belongs to class (“buys_computer = yes”)

 play tennis?
Naive Bayesian Classifier Example 2
Outlook Temperature Humidity W indy Class
sunny hot high false N
sunny hot high true N
overcast hot high false P
rain mild high false P
rain cool normal false P
rain cool normal true N
overcast cool normal true P
sunny mild high false N
sunny cool normal false P
rain mild normal false P
sunny mild normal true P
overcast mild high true P
overcast hot normal false P
rain mild high true N
Naive Bayesian Classifier Example
Outlook Temperature Humidity Windy Class
overcast hot high false P
rain mild high false P
rain cool normal false P
overcast cool normal true P
sunny cool normal false P 9
rain mild normal false P
sunny mild normal true P
overcast mild high true P
overcast hot normal false P

Outlook Temperature Humidity Windy Class

sunny hot high false N
sunny hot high true N
rain cool normal true N 5
sunny mild high false N
rain mild high true N
 Naive Bayesian Classifier Example
• Given the training set, we compute the probabilities:

Outlook P N Humidity P N
sunny 2/9 3/5 high 3/9 4/5
overcast 4/9 0 normal 6/9 1/5
rain 3/9 2/5
Tempreature Windy
hot 2/9 2/5 true 3/9 3/5
mild 4/9 2/5 false 6/9 2/5
cool 3/9 1/5
• We also have the probabilities
– P = 9/14
– N = 5/14
 Naive Bayesian Classifier Example
• To classify a new sample X:
– outlook = sunny
– temperature = cool
– humidity = high
– windy = false
• Prob(P|X) = Prob(P)*Prob(sunny|P)*Prob(cool|P)*
Prob(high|P)*Prob(false|P) = 9/14*2/9*3/9*3/9*6/9 = 0.01
• Prob(N|X) = Prob(N)*Prob(sunny|N)*Prob(cool|N)*
Prob(high|N)*Prob(false|N) = 5/14*3/5*1/5*4/5*2/5 =
0.013
• Therefore X takes class label N
 Naive Bayesian Classifier Example
• Second example X = <rain, hot, high, false>

• P(X|p)·P(p) =
P(rain|p)·P(hot|p)·P(high|p)·P(false|p)·P(p) =
3/9·2/9·3/9·6/9·9/14 = 0.010582
• P(X|n)·P(n) =
P(rain|n)·P(hot|n)·P(high|n)·P(false|n)·P(n) =
2/5·2/5·4/5·2/5·5/14 = 0.018286

• Sample X is classified in class N (don’t play)

 Classifier Evaluation Metrics:
Accuracy, Error Rate, Sensitivity and
A\P C ¬C
C TP FN P
Specificity  Class Imbalance Problem:
¬C FP TN N 
One class may be rare, e.g.
P’ N’ All
fraud, or HIV-positive
• Classifier Accuracy, or 
Significant majority of the
recognition rate: percentage of negative class and minority of
test set tuples that are correctly the positive class
classified 
Sensitivity: True Positive
Accuracy = (TP + TN)/All recognition rate
• Error rate: 1 – accuracy, or

Sensitivity = TP/P
Error rate = (FP + FN)/All

Specificity: True Negative
recognition rate

Specificity = TN/N
61
Classifier Evaluation Metrics: Confusion
Matrix
Confusion Matrix:
Actual class\Predicted class C1 ¬ C1
C1 True Positives (TP) False Negatives (FN)
¬ C1 False Positives (FP) True Negatives (TN)

ample of Confusion Matrix:

Actual class\Predicted buy computer buy_computer Total
class = yes = no
buy_computer = yes 6954 46 7000
buy_computer = no 412 2588 3000
Total 7366 2634 10000

• Given m classes, an entry, CMi,j in a confusion matrix indicates

# of tuples in class i that were labeled by the classifier as class j
• May have extra rows/columns to provide totals
62
Classifier Evaluation Metrics: Example

Actual Class\Predicted class cancer = yes cancer = no Total Recognition(%)

cancer = yes 90 210 300 30.00 (sensitivity
cancer = no 140 9560 9700 98.56 (specificity)
Total 230 9770 10000 96.50 (accuracy)
– Precision = 90/230 = 39.13% Recall = 90/300 = 30.00%

63