Data Mining

Imbalanced Class Problem

Class Imbalance Problem

Lots of classification problems where the classes

are skewed (more records from one class than
another)
– Credit card fraud
– Intrusion detection
– Defective products in manufacturing assembly
line

2
Challenges

Evaluation measures such as accuracy is not

well-suited for imbalanced class

Detecting the rare class is like finding needle in a

haystack

3
Confusion Matrix

Confusion Matrix:

PREDICTED CLASS

Class=Yes Class=No

Class=Yes a b
ACTUAL
CLASS Class=No c d

a: TP (true positive)
b: FN (false negative)
c: FP (false positive)
d: TN (true negative)

4
Accuracy

PREDICTED CLASS

Class=Yes Class=No

Class=Yes a b
ACTUAL (TP) (FN)
CLASS
Class=No c d
(FP) (TN)

Most widely-used metric:

a+d TP + TN
Accuracy = =
a + b + c + d TP + TN + FP + FN
5
Problem with Accuracy

Consider a 2-class problem

– Number of Class 0 examples = 9990
– Number of Class 1 examples = 10

6
Problem with Accuracy

Consider a 2-class problem

– Number of Class NO examples = 990
– Number of Class YES examples = 10

If a model predicts everything to be class NO,

accuracy is 990/1000 = 99 %
– This is misleading because the model does
not detect any class YES example
– Detecting the rare class is usually more
interesting (e.g., frauds, intrusions, defects,
etc)

7
Alternative Measures

PREDICTED CLASS
Class=Yes Class=No

Class=Yes a b
ACTUAL
CLASS Class=No c d

a
Precision (p) =
a+c
a
Recall (r) =
a+b
2rp 2a
F - measure (F) = =
r + p 2a + b + c
8
Alternative Measures
10
PREDICTED CLASS Precision (p) = = 0.5
10 + 10
10
Class=Yes Class=No Recall (r) = =1
10 + 0
Class=Yes 10 0 2 *1* 0.5
ACTUAL F - measure (F) = = 0.62
CLASS Class=No 10 980 1 + 0.5
990
Accuracy = = 0.99
1000

9
Alternative Measures
10
PREDICTED CLASS Precision (p) = = 0.5
10 + 10
10
Class=Yes Class=No Recall (r) = =1
10 + 0
Class=Yes 10 0 2 *1* 0.5
ACTUAL F - measure (F) = = 0.62
CLASS Class=No 10 980 1 + 0.5
990
Accuracy = = 0.99
1000

PREDICTED CLASS 1
Precision (p) = =1
1+ 0
Class=Yes Class=No
1
Recall (r) = = 0.1
Class=Yes 1 9 1+ 9
ACTUAL 2 * 0.1*1
CLASS Class=No 0 990 F - measure (F) = = 0.18
1 + 0.1
991
Accuracy = = 0.991
1000
10
Alternative Measures

PREDICTED CLASS
Precision (p) = 0.8
Class=Yes Class=No
Recall (r) = 0.8
Class=Yes 40 10 F - measure (F) = 0.8
ACTUAL
CLASS Class=No 10 40 Accuracy = 0.8

11
Alternative Measures

PREDICTED CLASS
Precision (p) = 0.8
Class=Yes Class=No
Recall (r) = 0.8
Class=Yes 40 10 F - measure (F) = 0.8
ACTUAL
CLASS Class=No 10 40 Accuracy = 0.8

PREDICTED CLASS
Class=Yes Class=No Precision (p) =~ 0.04
Class=Yes 40 10 Recall (r) = 0.8
ACTUAL F - measure (F) =~ 0.08
CLASS Class=No 1000 4000
Accuracy =~ 0.8

12
 Measures of Classification Performance

PREDICTED CLASS
Yes No
ACTUAL
Yes TP FN
CLASS
No FP TN

 is the probability that we reject

the null hypothesis when it is
true. This is a Type I error or a
false positive (FP).

 is the probability that we

accept the null hypothesis when
it is false. This is a Type II error
or a false negative (FN).

13
Alternative Measures

PREDICTED CLASS Precision (p) = 0.8

TPR = Recall (r) = 0.8
Class=Yes Class=No
FPR = 0.2
Class=Yes 40 10 F - measure (F) = 0.8
ACTUAL
CLASS Class=No 10 40 Accuracy = 0.8

PREDICTED CLASS
Precision (p) =~ 0.04
Class=Yes Class=No
TPR = Recall (r) = 0.8
ACTUAL
Class=Yes 40 10 FPR = 0.2
CLASS Class=No 1000 4000 F - measure (F) =~ 0.08
Accuracy =~ 0.8

14
Alternative Measures

PREDICTED CLASS
Class=Yes Class=No
Precision (p) = 0.5
Class=Yes 10 40
TPR = Recall (r) = 0.2
ACTUAL
Class=No 10 40
FPR = 0.2
CLASS

PREDICTED CLASS
Precision (p) = 0.5
Class=Yes Class=No
TPR = Recall (r) = 0.5
Class=Yes 25 25
ACTUAL FPR = 0.5
Class=No 25 25
CLASS

PREDICTED CLASS Precision (p) = 0.5

Class=Yes Class=No
TPR = Recall (r) = 0.8
Class=Yes 40 10
ACTUAL FPR = 0.8
CLASS Class=No 40 10

15
ROC (Receiver Operating Characteristic)

A graphical approach for displaying trade-off

between detection rate and false alarm rate
Developed in 1950s for signal detection theory to
analyze noisy signals
ROC curve plots TPR against FPR
– Performance of a model represented as a
point in an ROC curve
– Changing the threshold parameter of classifier
changes the location of the point

16
ROC Curve

(TPR,FPR):
(0,0): declare everything
to be negative class
(1,1): declare everything
to be positive class
(1,0): ideal

Diagonal line:
– Random guessing
– Below diagonal line:
◆ prediction is opposite
of the true class

17
ROC (Receiver Operating Characteristic)

To draw ROC curve, classifier must produce

continuous-valued output
– Outputs are used to rank test records, from the most
likely positive class record to the least likely positive
class record

Many classifiers produce only discrete outputs (i.e.,

predicted class)
– How to get continuous-valued outputs?
◆ Decision trees, rule-based classifiers, neural networks,
Bayesian classifiers, k-nearest neighbors, SVM

18
 Example: Decision Trees
Decision Tree
x2 < 12.63

x1 < 13.29 x2 < 17.35

Continuous-valued outputs
x1 < 6.56 x1 < 2.15

x2 < 12.63
x1 < 7.24
x2 < 8.64
x1 < 13.29 x2 < 17.35

x1 < 12.11
x2 < 1.38 x1 < 6.56 x1 < 2.15
0.059 0.220
x1 < 18.88
x1 < 7.24
x2 < 8.64 0.071
0.107

x1 < 12.11
x2 < 1.38 0.727
0.164

x1 < 18.88
0.143 0.669 0.271

0.654 0

19
 ROC Curve Example

x2 < 12.63

x1 < 13.29 x2 < 17.35

x1 < 6.56 x1 < 2.15

0.059 0.220

x1 < 7.24
x2 < 8.64 0.071
0.107

x1 < 12.11
x2 < 1.38 0.727
0.164

x1 < 18.88
0.143 0.669 0.271

0.654 0

20
 ROC Curve Example
- 1-dimensional data set containing 2 classes (positive and negative)
- Any points located at x > t is classified as positive

At threshold t:
TPR=0.5, FNR=0.5, FPR=0.12, TNR=0.88
21
Using ROC for Model Comparison

No model consistently
outperform the other
M1 is better for
small FPR
M2 is better for
large FPR

Area Under the ROC

curve
Ideal:
▪ Area =1
Random guess:
▪ Area = 0.5

22
How to Construct an ROC curve

• Use a classifier that produces a

Instance Score True Class
continuous-valued score for
1 0.95 +
each instance
2 0.93 +
• The more likely it is for the
3 0.87 - instance to be in the + class, the
4 0.85 - higher the score
5 0.85 - • Sort the instances in decreasing
6 0.85 + order according to the score
7 0.76 - • Apply a threshold at each unique
8 0.53 + value of the score
9 0.43 - • Count the number of TP, FP,
10 0.25 + TN, FN at each threshold
• TPR = TP/(TP+FN)
• FPR = FP/(FP + TN)

23
How to construct an ROC curve
Class + - + - - - + - + +
P
Threshold >= 0.25 0.43 0.53 0.76 0.85 0.85 0.85 0.87 0.93 0.95 1.00

TP 5 4 4 3 3 3 3 2 2 1 0

FP 5 5 4 4 3 2 1 1 0 0 0

TN 0 0 1 1 2 3 4 4 5 5 5

FN 0 1 1 2 2 2 2 3 3 4 5

TPR 1 0.8 0.8 0.6 0.6 0.6 0.6 0.4 0.4 0.2 0

FPR 1 1 0.8 0.8 0.6 0.4 0.2 0.2 0 0 0

ROC Curve:

24
Handling Class Imbalanced Problem

Class-based ordering (e.g. RIPPER)

– Rules for rare class have higher priority

Cost-sensitive classification
– Misclassifying rare class as majority class is
more expensive than misclassifying majority
as rare class

Sampling-based approaches

25
Cost Matrix

PREDICTED CLASS

Class=Yes Class=No
ACTUAL
CLASS Class=Yes f(Yes, Yes) f(Yes,No)

C(i,j): Cost of
Class=No f(No, Yes) f(No, No)
misclassifying class i
example as class j
Cost PREDICTED CLASS
Matrix
C(i, j) Class=Yes Class=No Cost =  C (i, j )  f (i, j )
Class=Yes C(Yes, Yes) C(Yes, No)
ACTUAL
CLASS
Class=No C(No, Yes) C(No, No)

26
Computing Cost of Classification

Cost PREDICTED CLASS

Matrix
C(i,j) + -
ACTUAL
+ -1 100
CLASS
- 1 0

Model PREDICTED CLASS Model PREDICTED CLASS

M1 M2
+ - + -
ACTUAL ACTUAL
+ 150 40 + 250 45
CLASS CLASS
- 60 250 - 5 200

Accuracy = 80% Accuracy = 90%

Cost = 3910 Cost = 4255
27
Cost Sensitive Classification

Example: Bayesian classifer

– Given a test record x:
◆ Compute p(i|x) for each class i
◆ Decision rule: classify node as class k if

k = arg max p(i | x)

i

– For 2-class, classify x as + if p(+|x) > p(-|x)

◆ This decision rule implicitly assumes that
C(+|+) = C(-|-) = 0 and C(+|-) = C(-|+)

28
Cost Sensitive Classification

General decision rule:

– Classify test record x as class k if
k = arg min  p(i | x )  C (i, j )
j i
2-class:
– Cost(+) = p(+|x) C(+,+) + p(-|x) C(-,+)
– Cost(-) = p(+|x) C(+,-) + p(-|x) C(-,-)
– Decision rule: classify x as + if Cost(+) < Cost(-)
◆ if C(+,+) = C(-,-) = 0:
C ( −, + )
p( + | x ) 
C ( −, + ) + C ( + , − )
29
Sampling-based Approaches

Modify the distribution of training data so that rare

class is well-represented in training set
– Undersample the majority class
– Oversample the rare class

Advantages and disadvantages

30