Chapter 8.

Classification: Basic
Concepts
Meng Jiang
CS412 Summer 2017:
Introduction to Data Mining
 Classification: Basic
Concepts
• Classification: Basic Concepts
• Decision Tree Induction
• Bayes Classification Methods
• Model Evaluation and Selection
• Techniques to Improve Classification
Accuracy: Ensemble Methods

2
 Supervised vs. Unsupervised
Learning
• 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 3
 Prediction Problems: Classification
vs. Numeric Prediction
• Classification
– Predicts categorical class labels (discrete or nominal)
– Classifies data (constructs a model) based on the
training set (tuples/samples/objects and their
attributes/features; attributes: measurements,
observations, etc.) and the class labels
• Numeric Prediction
– Models continuous-valued functions, i.e., predicts
unknown or missing values
• Typical applications
– Credit/loan approval
– Medical diagnosis: if a tumor is cancerous or benign
– Fraud detection: if a transaction is fraudulent
– Web page categorization: which category it is 4
Classification: A Two-Step Process
• 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 attributes
– The set of tuples used for model construction is training set
– Model: represented as classification rules, decision trees, or
mathematical formulae
• 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: % of test set samples that are correctly classified
by the model
• Test set is independent of training set (otherwise overfitting)
– If the accuracy is acceptable, use the model to classify new data
• Note: If the test set is used to select/refine models, it is called
validation (test) set or development test set
5
(1) Model Construction
Classification
Algorithms
Training
Data

Classifier
(Model)

IF rank = ‘professor’
OR years > 6
THEN tenured = ‘yes’
6
(2) Using the Model in
Prediction
Classifier

Testing
Data Unseen Data

(Jeff, Professor, 4)

Tenured?

7
 Classification: Basic
Concepts
• Classification: Basic Concepts
• Decision Tree Induction
• Bayes Classification Methods
• Model Evaluation and Selection
• Techniques to Improve Classification
Accuracy: Ensemble Methods

8
 Decision Tree Induction: An
Example
• Training data set: Buys_computer
• The data set follows an example of Quinlan’s ID3
(Playing Tennis)
• Resulting tree:
age?

<=30 31..40 >40

student? yes credit rating?

no yes excellent fair

no yes no yes

9
Quinlan’s Example – Playing
Tennis?

outlook

sunny rain
overcast

humidity P windy

high normal true false

N P N P
10
 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

11
 Brief Review of Entropy
• Entropy (Information Theory)
– A measure of uncertainty associated with a
random number
– Calculation: For a discrete random variable Y
taking m distinct values {y1, y2, …, ym}

– Interpretation
• Higher entropy → higher uncertainty
• Lower entropy → lower uncertainty
• Conditional entropy
m=
2 12
 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|
• Expected information (entropy)
m needed to classify a
tuple in D: Info ( D )  pi log 2 ( pi )
i 1

• Information needed (after using A to split D into v

partitions) to classify D:
v |D |
Info A ( D ) 
j
Info ( D j )
j 1 |D|
• Information gained by branching on attribute A
Gain(A) Info(D)  Info A(D)
13
 Attribute Selection: Information
Gain
#total (#positive, #negative)

14 (9,5)
Gain(age), Gain(income),
age?Gain(student), Gain(credit rating)

5 (2,3) 4 (4,0) 5 (3,2)

<=30 >40 Gain(income),
31..40
Gain(student),
Gain(income), Gain(credit rating)
Gain(student), student? yes credit rating?
Gain(credit rating)

no yes excellent fair

3 (0,3) 2 (2,0) 3 (3, 0)
2 (0,2)
no yes no yes

14
 Attribute Selection: Information
•
Gain
Class P: buys_computer =
“yes” 5 4
Info age ( D )  I (2,3)  I (4,0)
• Class N: buys_computer = 14 14
9 9 5 5
Info ( D )“no”
I (9,5)  log 2 ( )  log 2 ( ) 0.940 
5
I (3,2) 0.694
14 14 14 14 14
5
I ( 2,3) means “age <=30” has 5 out
14
of 14 samples, with 2 yes’es
and 3 no’s. Hence
Gain(age) Info ( D )  Info age ( D ) 0.246
Similarly,
Gain(income) 0.029
Gain( student ) 0.151
Gain(credit _ rating ) 0.048

15
 Computing Information-Gain for
Continuous-Valued Attributes
• Let attribute A be a continuous-valued attribute
• Must determine the best split point for A
– Sort the value A in increasing order
Why?
– Typically, the midpoint between each pair of adjacent
values is considered as a possible split point
• (ai+ai+1)/2 is the midpoint between the values of ai and
ai+1
– The point with the minimum expected information
minpoint Infopoint(A)
requirement for A is selected as the split-point for A
• Split:
– D1 is the set of tuples in D satisfying A ≤ split-point, and D2
is the set of tuples in D satisfying A > split-point
16
 Gain Ratio for Attribute Selection
(C4.5)
• Information gain measure is biased towards attributes
with a large number of values
• C4.5 (a successor of ID3) uses gain ratio to overcome
the problem (normalization to information gain)
v|D | |D |
SplitInfo ( D )  
j j
A log (
2 )
|D|
j 1 |D|
5 4
Info age ( D )  I (2,3)  I (4,0)
14 14
– GainRatio(A) = Gain(A)/SplitInfo(A) 5
 I (3,2) 0.694
• Ex. 14
Gain(age) Info ( D )  Info age ( D ) 0.246
Gain(income) 0.029
– gain_ratio(income) = 0.029/1.557 = 0.019
Gain ( student ) 0.151
Gain(income) = Info(root) –
• The attribute with the maximum gain ratio is selected
Gain
Info (credit _ rating ) 0.048
income(root)
as the splitting attribute
= I(9,5) – { 4/14 I(2,2) + 6/14 I(4, 2)
+ 4/14 I(3, 1) }
17
= 0.940 – 0.911 = 0.029
 Gain Ratio for Attribute Selection
(C4.5)
• Information gain measure is biased towards attributes
with a large number of values
• C4.5 (a successor of ID3) uses gain ratio to overcome
the problem (normalization to information gain)
v|D | |D |
SplitInfo ( D )  
j j
A log (
2 )
|D|
j 1 |D|
5 4
Info age ( D )  I (2,3)  I (4,0)
14 14
– GainRatio(A) = Gain(A)/SplitInfo(A) 5
 I (3,2) 0.694
• Ex. 14
Gain(age) Info ( D )  Info age ( D ) 0.246
Gain(income) 0.029
– gain_ratio(income) = 0.029/1.557 = 0.019
Gain( student ) 0.151
• The attribute with the maximum gain ratio is selected
Gain(credit _ rating ) 0.048
as the splitting attribute
If we have many income values:
1000-2000, 2000-3000, … 9000-10000, …
18
 Gain Ratio for Attribute Selection
(C4.5)
• Information gain measure is biased towards attributes
with a large number of values
• C4.5 (a successor of ID3) uses gain ratio to overcome
the problem (normalization to information gain)
v |D | |D |
SplitInfo ( D )  
j j
A 2log ( )
j 1 |D| |D|

– GainRatio(A) = Gain(A)/SplitInfo(A)
• Ex.

– gain_ratio(income) = 0.029/1.557 = 0.019

• The attribute with the maximum gain ratio is selected
as the splitting attribute

19
 Gini Index (CART, IBM
IntelligentMiner)
• If a data set D contains examples from n classes, gini index,
n 2
gini(D) is defined as
gini( D) 1  p j
j 1
where pj is the relative frequency of class j in D
• If a data set D is split on A into two subsets D1 and D2, the
gini index gini(D) is defined |D | |D |
gini Aas
( D)  1 gini( D1)  2 gini( D 2)
|D| |D|

• Reduction in Impurity: gini( A) gini( D)  giniA ( D)

• The attribute provides the smallest ginisplit(D) (or the largest

reduction in impurity) is chosen to split the node (need to
enumerate all the possible splitting points for each
attribute)
20
 IG vs Gini

m n 2
Info ( D)   pi log 2 ( pi ) gini( D) 1  p j
i 1 j 1

v | Dj |
Info A ( D ) 
|D | |D |
Info ( D j ) gini A ( D)  1 gini( D1)  2 gini( D 2)
|D| |D|
j 1 |D|

Gain(A) Info(D)  Info A(D) gini( A) gini( D)  giniA ( D)

21
 Computation of Gini Index
• Ex. D has 9 tuples in buys_computer = “yes” and 5 in “no”
2 2
 9  5
gini ( D) 1       0.459
 14   14 
• Suppose the attribute income partitions D into 10 in D 1:
{low, medium} and 4 in D2: {high}
 10   4
giniincome{low,medium} ( D)   Gini ( D1 )    Gini ( D2 )
 14   14 

Gini{low,high} is 0.458; Gini{medium,high} is 0.450. Thus, split on the

{low,medium} (and {high}) since it has the lowest Gini index
• All attributes are assumed continuous-valued
• May need other tools, e.g., clustering, to get the possible
split values
• Can be modified for categorical attributes
22
 Comparing Attribute Selection
Measures
• The three measures, in general, return good results
but
– Information gain:
• biased towards multivalued attributes
– Gain ratio:
• tends to prefer unbalanced splits in which one
partition is much smaller than the others
– Gini index:
• biased to multivalued attributes
• has difficulty when # of classes is large
• tends to favor tests that result in equal-sized
partitions and purity in both partitions 23
Other Attribute Selection Measures
• CHAID: a popular decision tree algorithm, measure based on χ2
test for independence
• C-SEP: performs better than info. gain and gini index in certain
cases
• G-statistic: has a close approximation to χ2 distribution
• MDL (Minimal Description Length) principle (i.e., the simplest
solution is preferred):
– The best tree as the one that requires the fewest # of bits to
both (1) encode the tree, and (2) encode the exceptions to the
tree
• Multivariate splits (partition based on multiple variable
combinations)
– CART: finds multivariate splits based on a linear comb. of attrs.
• Which attribute selection measure is the best?
– Most give good results, none is significantly superior than 24
others
Overfitting and Tree Pruning
• Overfitting: An induced tree may overfit the training data
– Too many branches, some may reflect anomalies due
to noise or outliers
– Poor accuracy for unseen samples
• Two approaches to avoid overfitting
– Prepruning: Halt tree construction early ̵ do not split a
node if this would result in the goodness measure
falling below a threshold
• Difficult to choose an appropriate threshold
– Postpruning: Remove branches from a “fully grown”
tree—get a sequence of progressively pruned trees
• Use a set of data different from the training data to
decide which is the “best pruned tree” 25
 Classification in Large
Databases
• Classification—a classical problem extensively studied by
statisticians and machine learning researchers
• Scalability: Classifying data sets with millions of examples
and hundreds of attributes with reasonable speed
• Why is decision tree induction popular?
– relatively faster learning speed (than other
classification methods)
– convertible to simple and easy to understand
classification rules
– can use SQL queries for accessing databases
– comparable classification accuracy with other methods
• RainForest (VLDB’98 — Gehrke, Ramakrishnan & Ganti)
– Builds an AVC-list (attribute, value, class label) 26
 RainForest: A Scalable Classification
Framework
• The criteria that determine the quality of the tree can be
computed separately
– Builds an AVC-list: AVC (Attribute, Value, Class_label)
• AVC-set (of an attribute X )
– Projection of training dataset onto the attribute X and class
label where counts of individual class label are aggregated
• AVC-group (of a node n )
AVC-set on Age AVC-set on Income
– Set of AVC-sets of all
Age Buy_Computer income Buy_Computer
predictor attributes at
yes no yes no
the node n
<=30 2 3 high 2 2
31..40 4 0 medium 4 2
>40 3 2 low 3 1

AVC-set on StudentAVC-set on Credit_Rating

student Buy_Computer Buy_Computer
yes no Credit
rating yes no
yes 6 1
fair 6 2
no 3 4
excellent 3 3 27
The Training Data Its AVC Sets
 Classification: Basic
Concepts
• Classification: Basic Concepts
• Decision Tree Induction
• Bayes Classification Methods
• Model Evaluation and Selection
• Techniques to Improve Classification
Accuracy: Ensemble Methods

28
 Bayesian Classification:
Why?
• A statistical classifier: performs probabilistic prediction,
i.e., predicts class membership probabilities
• Foundation: Based on Bayes’ Theorem.
• Performance: A simple Bayesian classifier, naïve
Bayesian classifier, has comparable performance with
decision tree and selected neural network classifiers
• Incremental: Each training example can incrementally
increase/decrease the probability that a hypothesis is
correct — prior knowledge can be combined with
observed data
• Standard: Even when Bayesian methods are
computationally intractable, they can provide a
standard of optimal decision making against which
other methods can be measured 29
Bayes’ Theorem: Basics

30
 Bayes’ Theorem: Basics
P(H | X) P(X | H ) P(H ) P(X | H )P(H ) / P(X)
• Bayes’ Theorem: P(X)
– 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), (i.e., posteriori
probability): 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) (likelihood): the probability of observing the
sample X, given that the hypothesis holds
• E.g., Given that X will buy computer, the prob. that X
31
is 31..40, medium income
 Prediction Based on 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 | H )P(H ) / P(X)

P(X)

• Informally, this can be viewed as

posteriori = likelihood x prior/evidence
• Predicts X belongs to Ci iff the probability P(Ci|X) is the
highest among all the P(Ck|X) for all the k classes
• Practical difficulty: It requires initial knowledge of
many probabilities, involving significant computational
cost
32
 Classification is to Derive the
Maximum Posteriori
• 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

P(C | X) P(X | C )P(C )
i i i
33
needs to be maximized
 Naïve Bayes Classifier
• A simplified assumption: attributes are conditionally
independent (i.e., no dependence relation between
attributes): n
P( X | C i )   P( x | C i ) P( x | C i ) P( x | C i ) ... P( x | C i )
k 1 2 n
k 1
• This greatly reduces the computation cost: Only counts
the class distribution
• If Ak is categorical, P(xk|Ci) is the # of tuples in C i having
value xk for Ak divided by |Ci, D| (# of tuples of Ci in D)
• If Ak is continous-valued, P(x k|Ci) is usually computed
based on Gaussian distribution ( x  )
with a mean μ and
2
1 
standard deviation
g ( x,  ,  )σ e 2
2

2 

P ( X | C i )  g ( xk ,  Ci ,  C i )
and P(xk|Ci) is 34
 Naïve Bayes Classifier: Training
Dataset
• Class:
– C1: buys_computer =
‘yes’
– C2: buys_computer =
‘no’

• Data to be classified:
– X = (age <=30,
Income = medium,
Student = yes,
Credit_rating = Fair)

35
 Naïve Bayes Classifier: 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 = 36
 Avoiding the Zero-Probability
Problem
• Naïve Bayesian prediction requires each conditional
prob. be non-zero. Otherwise, the predicted prob.
will be zero n
P( X | C i)   P( x k | C i)
k 1

• Ex. Suppose a dataset with 1000 tuples, income=low

(0), income= medium (990), and income = high (10)
• Use Laplacian correction (or Laplacian estimator)
– Adding 1 to each case
Prob(income = low) = 1/1003
Prob(income = medium) = 991/1003
Prob(income = high) = 11/1003
– The “corrected” prob. estimates are close to their
“uncorrected” counterparts 37
 Naïve Bayes Classifier:
Comments
• Advantages
– Easy to implement
– Good results obtained in most of the cases
• Disadvantages
– Assumption: class conditional independence,
therefore loss of accuracy
– Practically, dependencies exist among variables
• E.g., hospitals: patients: Profile: age, family
history, etc.
Symptoms: fever, cough etc., Disease: lung
cancer, diabetes, etc.
• Dependencies among these cannot be modeled
by Naïve Bayes Classifier
• How to deal with these dependencies? Bayesian
Belief Networks (Chapter 9) 38
 Classification: Basic
Concepts
• Classification: Basic Concepts
• Decision Tree Induction
• Bayes Classification Methods
• Model Evaluation and Selection
• Techniques to Improve Classification
Accuracy: Ensemble Methods

39
 Model Evaluation and
Selection
• Evaluation metrics: How can we measure accuracy?
Other metrics to consider?
• Use validation test set of class-labeled tuples
instead of training set when assessing accuracy
• Methods for estimating a classifier’s accuracy:
– Holdout method, random subsampling
– Cross-validation
– Bootstrap
• Comparing classifiers:
– Confidence intervals
– Cost-benefit analysis and ROC Curves
40
 Classifier Evaluation Metrics:
Confusion Matrix
Confusion
Matrix:
Actual class\Predicted C1 ¬ C1
class
C1 True Positives False Negatives
(TP) (FN)
xample of¬Confusion
C1 Matrix:
False Positives True Negatives
Actual class\Predicted class (FP)
buy_computer = (TN) = no
buy_computer Total
yes
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 totals41
 Classifier Evaluation Metrics:
Accuracy, Error Rate, Sensitivity
and Specificity
• Class Imbalance
A\P C ¬C
Problem:
C TP FN P – One class may be rare,
¬C FP TN N e.g. fraud, or HIV-
positive
P’ N’ All
– Significant majority of
• Classifier Accuracy, the negative class and
minority of the positive
or recognition rate: class
percentage of test set – Sensitivity: True
tuples that are correctly Positive recognition rate
classified • Sensitivity = TP/P
Accuracy = (TP + TN)/All – Specificity: True
• Error rate: 1 – Negative recognition
accuracy, or rate
42
Error rate = (FP + FN)/All • Specificity = TN/N
 Classifier Evaluation Metrics:
Precision and Recall, and F-measures
• Precision: exactness: what % of tuples that the classifier
labeled as positive are actually positive

• Recall: completeness – what % of positive tuples did the

classifier label as positive?
• Comment:
– Perfect score is 1.0
– Inverse relationship between precision & recall
• F measure (or F-score): harmonic mean of precision
and recall
– In general, it is the weighted measure of β
Assigning precision &
times as much
recall weight to recall as to
precision)

• F1-measure (balanced F-measure)

43
» That is, when β = 1,
 Classifier Evaluation Metrics:
Example
Actual Class\Predicted cancer = cancer = Total Recognition(%
class yes no )
cancer = yes 90 210 300 30.00
(sensitivity)
cancer = no 140 9560 9700 98.56
(specificity)
PrecisionTotal
= 90/230 = 39.13%
230
Recall
9770
= 90/300
10000
= 30.00%
96.40
(accuracy)

44
 Evaluating Classifier Accuracy:
Holdout & Cross-Validation Methods
• Holdout method
– Given data is randomly partitioned into two independent sets
• Training set (e.g., 2/3) for model construction
• Test set (e.g., 1/3) for accuracy estimation
– Random sampling: a variation of holdout
• Repeat holdout k times, accuracy = avg. of the accuracies
obtained
• Cross-validation (k-fold, where k = 10 is most popular)
– Randomly partition the data into k mutually exclusive subsets,
each approximately equal size
– At i-th iteration, use Di as test set and others as training set
– Leave-one-out: k folds where k = # of tuples, for small sized
data
– *Stratified cross-validation*: folds are stratified so that
class dist. in each fold is approx. the same as that in the initial
data 45
 Evaluating Classifier Accuracy:
Bootstrap
• Bootstrap
– Works well with small data sets
– Samples the given training tuples uniformly with replacement
• Each time a tuple is selected, it is equally likely to be
selected again and re-added to the training set
• Several bootstrap methods, and a common one is .632
bootstrap
– A data set with d tuples is sampled d times, with replacement,
resulting in a training set of d samples. The data tuples that did
not make it into the training set end up forming the test set.
About 63.2% of the original data end up in the bootstrap, and the
remaining 36.8% form the test set (since (1 – 1/d) d ≈ e-1 = 0.368)
– Repeat the sampling procedure k times, overall accuracy of the
model:

46
 Model Selection: ROC
Curves
• ROC (Receiver Operating
Characteristics) curves: for visual
comparison of classification models
• Originated from signal detection
theory
• Shows the trade-off between the
true positive rate and the false
positive rate
• The area under the ROC curve is a
measure of the accuracy of the
model
• Rank the test tuples in decreasing • Vertical axis represents the
order: the one that is most likely to true positive rate
belong to the positive class appears • Horizontal axis rep. the false
at the top of the list positive rate
• The closer to the diagonal line • The plot also shows a diagonal line
(i.e., the closer the area is to • A model with perfect accuracy
0.5), the less accurate is the will have an area of 1.0
model 47
 Issues Affecting Model
Selection
• Accuracy
– classifier accuracy: predicting class label
• 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

48
 Classification: Basic
Concepts
• Classification: Basic Concepts
• Decision Tree Induction
• Bayes Classification Methods
• Model Evaluation and Selection
• Techniques to Improve
Classification Accuracy:
Ensemble Methods

49
 Ensemble Methods: Increasing the
Accuracy
• Ensemble methods
– Use a combination of models to increase accuracy
– Combine a series of k learned models, M1, M2, …, Mk,
with the aim of creating an improved model M*
• Popular ensemble methods
– Bagging: averaging the prediction over a collection of
classifiers
– Boosting: weighted vote with a collection of classifiers
– Ensemble: combining a set of heterogeneous
classifiers

50
 Bagging: Boostrap
Aggregation
• Analogy: Diagnosis based on multiple doctors’ majority vote
• Training
– Given a set D of d tuples, at each iteration i, a training set Di
of d tuples is sampled with replacement from D (i.e.,
bootstrap)
– A classifier model Mi is learned for each training set Di
• Classification: classify an unknown sample X
– Each classifier Mi returns its class prediction
– The bagged classifier M* counts the votes and assigns the
class with the most votes to X
• Prediction: can be applied to the prediction of continuous values
by taking the average value of each prediction for a given test
tuple
• Accuracy: Proved improved accuracy in prediction
– Often significantly better than a single classifier derived from
D 51
– For noise data: not considerably worse, more robust
 Boosting
• Analogy: Consult several doctors, based on a combination of
weighted diagnoses—weight assigned based on the previous
diagnosis accuracy
• How boosting works?
– Weights are assigned to each training tuple
– A series of k classifiers is iteratively learned
– After a classifier Mi is learned, the weights are updated to
allow the subsequent classifier, Mi+1, to pay more attention
to the training tuples that were misclassified by Mi
– The final M* combines the votes of each individual
classifier, where the weight of each classifier's vote is a
function of its accuracy
• Boosting algorithm can be extended for numeric prediction
• Comparing with bagging: Boosting tends to have greater
accuracy, but it also risks overfitting the model to
misclassified data 52
 Adaboost (Freund and Schapire,
1997)
• Given a set of d class-labeled tuples, (X1, y1), …, (Xd, yd)
• Initially, all the weights of tuples are set the same (1/d)
• Generate k classifiers in k rounds. At round i,
– Tuples from D are sampled (with replacement) to form a
training set Di of the same size
– Each tuple’s chance of being selected is based on its weight
– A classification model Mi is derived from Di
– Its error rate is calculated using Di as a test set
– If a tuple is misclassified, its weight is increased, o.w. it is
decreased
• Error rate: err(Xj) is the misclassification error of tuple
d
Xj. Classifier Mi error rate
error ( M i ) sum
is the of( Xthe
w j err weights of
j)
the misclassified tuples: j

1  error ( M i )
log
• The weight of classifier Mi’s vote is error ( M i )
53
Random Forest (Breiman 2001)
• Random Forest:
– Each classifier in the ensemble is a decision tree classifier
and is generated using a random selection of attributes at
each node to determine the split
– During classification, each tree votes and the most popular
class is returned
• Two Methods to construct Random Forest:
– Forest-RI (random input selection): Randomly select, at each
node, F attributes as candidates for the split at the node. The
CART methodology is used to grow the trees to maximum size
– Forest-RC (random linear combinations): Creates new
attributes (or features) that are a linear combination of the
existing attributes (reduces the correlation between individual
classifiers)
• Comparable in accuracy to Adaboost, but more robust to errors
and outliers
• Insensitive to the number of attributes selected for consideration 54
at each split, and faster than bagging or boosting
 Classification of Class-Imbalanced
Data Sets
• Class-imbalance problem: Rare positive example but
numerous negative ones, e.g., medical diagnosis, fraud,
oil-spill, fault, etc.
• Traditional methods assume a balanced distribution of x x x
classes and equal error costs: not suitable for class- x x x x x
imbalanced data x x xx x
x
x
x
x
xo o
• Typical methods in two-class classification: x x
x
o x x
o x
x x
x
– Oversampling: re-sampling of data from positive class
– Under-sampling: randomly eliminate tuples from negative class
– Threshold-moving: move the decision threshold, t, so that the
rare class tuples are easier to classify, and hence, less chance of
costly false negative errors
– Ensemble techniques: Ensemble multiple classifiers introduced
above
• Still difficult for class imbalance problem on multiclass
tasks 55
 Summary
• Classification: Extracting models describing important data classes
• Effective and scalable methods
– Decision tree induction, Naive Bayesian classification, rule-based
classification, and many other classification methods
• Evaluation metrics:
– Accuracy, sensitivity, specificity, precision, recall, F measure, and Fß
measure
– Stratified k-fold cross-validation is recommended for accuracy
estimation
• Ensemble: Bagging and boosting can be used to increase overall accuracy
by learning and combining a series of individual models
– Adaboost
• No single method has been found to be superior over all others
for all data sets
56
 References
• C. Apte and S. Weiss. Data mining with decision trees and decision rules. Future
Generation Computer Systems, 13, 1997
• P. K. Chan and S. J. Stolfo. Learning arbiter and combiner trees from partitioned
data for scaling machine learning. KDD'95
• A. J. Dobson. An Introduction to Generalized Linear Models. Chapman & Hall,
1990.
• R. O. Duda, P. E. Hart, and D. G. Stork. Pattern Classification, 2ed. John Wiley,
2001
• U. M. Fayyad. Branching on attribute values in decision tree generation. AAAI’94.
• Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line
learning and an application to boosting. J. Computer and System Sciences,
1997.
• J. Gehrke, R. Ramakrishnan, and V. Ganti. Rainforest: A framework for fast
decision tree construction of large datasets. VLDB’98.
• J. Gehrke, V. Gant, R. Ramakrishnan, and W.-Y. Loh, BOAT -- Optimistic Decision
Tree Construction. SIGMOD'99.
• T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning:
Data Mining, Inference, and Prediction. Springer-Verlag, 2001.
• T.-S. Lim, W.-Y. Loh, and Y.-S. Shih. A comparison of prediction accuracy,
complexity, and training time of thirty-three old and new classification 57
algorithms. Machine Learning, 2000
 References (cont.)
• J. Magidson. The Chaid approach to segmentation modeling: Chi-squared automatic
interaction detection. In R. P. Bagozzi, editor, Advanced Methods of Marketing Research,
Blackwell Business, 1994
• M. Mehta, R. Agrawal, and J. Rissanen. SLIQ : A fast scalable classifier for data mining.
EDBT'96
• T. M. Mitchell. Machine Learning. McGraw Hill, 1997
• S. K. Murthy, Automatic Construction of Decision Trees from Data: A Multi-Disciplinary
Survey, Data Mining and Knowledge Discovery 2(4): 345-389, 1998
• J. R. Quinlan. Induction of decision trees. Machine Learning, 1:81-106, 1986.
• J. R. Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann, 1993.
• J. R. Quinlan. Bagging, boosting, and c4.5. AAAI‘96.
• R. Rastogi and K. Shim. Public: A decision tree classifier that integrates building and
pruning. VLDB’98
• J. Shafer, R. Agrawal, and M. Mehta. SPRINT : A scalable parallel classifier for data
mining. VLDB’96
• J. W. Shavlik and T. G. Dietterich. Readings in Machine Learning. Morgan Kaufmann,
1990
• P. Tan, M. Steinbach, and V. Kumar. Introduction to Data Mining. Addison Wesley, 2005
• S. M. Weiss and C. A. Kulikowski. Computer Systems that Learn: Classification and
Prediction Methods from Statistics, Neural Nets, Machine Learning, and Expert
Systems. Morgan Kaufman, 1991
• S. M. Weiss and N. Indurkhya. Predictive Data Mining. Morgan Kaufmann, 1997
• I. H. Witten and E. Frank. Data Mining: Practical Machine Learning Tools and 58
Techniques, 2ed. Morgan Kaufmann, 2005