CS 412 Intro.
to Data Mining
Chapter 8. Classification: Basic Concepts (1/2)
Jiawei Han, Computer Science, Univ. Illinois at Urbana -Champaign, 2106
This lecture note is taken from “[Link]
and then edited by Chun-Hee Lee.
1
Chapter 8. Classification: Basic Concepts
❑ Classification: Basic Concepts
❑ Decision Tree Induction
❑ Bayes Classification Methods
❑ Model Evaluation and Selection
❑ Techniques to Improve Classification Accuracy: Ensemble Methods
❑ Summary
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 and the values
(class labels) in a classifying attribute and uses it in classifying new data
❑ 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 attribute
❑ 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
Process (1): Model Construction
Classification
Algorithms
Training
Data
NAME RANK YEARS TENURED Classifier
M ike A ssistant P rof 3 no (Model)
M ary A ssistant P rof 7 yes
B ill P rofessor 2 yes
Jim A ssociate P rof 7 yes
IF rank = ‘professor’
D ave A ssistant P rof 6 no
OR years > 6
A nne A ssociate P rof 3 no
THEN tenured = ‘yes’
6
Process (2): Using the Model in Prediction
Classifier
Testing
Data Unseen Data
(Jeff, Professor, 4)
NAME RANK YEARS TENURED
T om A ssistant P rof 2 no Tenured?
M erlisa A ssociate P rof 7 no
G eorge P rofessor 5 yes
Joseph A ssistant P rof 7 yes
7
Chapter 8. Classification: Basic Concepts
❑ Classification: Basic Concepts
❑ Decision Tree Induction
❑ Bayes Classification Methods
❑ Model Evaluation and Selection
❑ Techniques to Improve Classification Accuracy: Ensemble Methods
❑ Summary
8
Decision Tree Induction: An Example
age income student credit_rating buys_computer
❑ Training data set: Buys_computer <=30 high no fair no
❑ The data set follows an example of <=30 high no excellent no
31…40 high no fair yes
Quinlan’s ID3 (Playing Tennis) >40 medium no fair yes
❑ Resulting tree: >40 low yes fair yes
age? >40 low yes excellent no
31…40 low yes excellent yes
<=30 medium no fair no
<=30 low yes fair yes
<=30 overcast
31..40 >40 >40 medium yes fair yes
<=30 medium yes excellent yes
31…40 medium no excellent yes
student? yes credit rating? 31…40 high yes fair yes
>40 medium no excellent no
no yes excellent fair
no yes yes
9
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
10
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
11
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) needed to classify a tuple in D:
m
Info( D) = − pi log 2 ( pi )
= H(D) i =1
❑ Expected Information needed for the tree with A as root: A1 Av
A2
(Conditional Entropy) v | D |
Info A ( D) = Info( D j )
j
…
= H(D|A) j =1 | D |
D1 D2 Dv
❑ Information gained by branching on attribute A
Gain(A) = Info(D) − InfoA(D)
12
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(pi, ni)
5
<=30 2 3 0.971 I (2,3) means “age <=30” has 5 out of 14
31…40 4 0 0 14
>40 3 2 0.971 samples, with 2 yes’es and 3 no’s.
age income student credit_rating buys_computer
<=30 high no fair no Hence
<=30
31…40
high
high
no
no
excellent
fair
no
yes
Gain(age) = Info( D) − Infoage ( D) = 0.246
>40 medium no fair yes
>40 low yes fair yes Similarly,
>40 low yes excellent no
31…40
<=30
low
medium
yes excellent
no fair
yes
no Gain(income) = 0.029
<=30
>40
low
medium
yes fair
yes fair
yes
yes Gain( student) = 0.151
Gain(credit _ rating ) = 0.048
<=30 medium yes excellent yes
31…40 medium no excellent yes
31…40 high yes fair yes
13 >40 medium no excellent no
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
❑ 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 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
14
Gini Index (CART, IBM IntelligentMiner)
❑ If a data set D contains examples from n classes, gini index, gini(D) is defined as
n
gini( D) = 1− p 2j
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 as
|D1| |D |
giniA ( D) = 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)
15
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 D1: {low, medium} and 4 in D2
10 4
giniincom e{low,m edium} ( 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
16
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”
17