Chapter 6.

Classification: Basic Concepts

 Classification: Basic Concepts
 Decision Tree Induction
 Bayes Classification Methods
 Lazy Learners (or learning from your neighbors)
 Linear Classifiers
 Model Evaluation and Selection
 Techniques to Improve Classification Accuracy
 Summary

1
 Supervised vs. Unsupervised Learning (1)
 Supervised(‫ )ُموّج ه‬learning (classification)
 Supervision: The training data such as observations or measurements are
accompanied by labels indicating the classes which they belong to
 New data is classified based on the models built from the training set
Training Data with class label:
Outlook Temp Humidity Windy Play Golf
Training Model
Rainy Hot High False No
Instances Learning
Rainy Hot High True No

Overcast Hot High False Yes

Sunny Mild High False Yes

Sunny Cool Normal False Yes

Positive
Sunny Cool Normal True No

Overcast Cool Normal True Yes Test Prediction

Rainy Mild High False No Instances Model
Negative
2
 Supervised vs. Unsupervised Learning (2)
 Unsupervised learning (clustering)
 The class labels of training data are unknown
 Given a set of observations or measurements, establish the possible existence of
classes or clusters in the data

3
 Prediction Problems: Classification vs. Numeric
Prediction
 Classification
 Predict categorical class labels (discrete or nominal)
 Construct a model based on the training set and the class labels (the values in a
classifying attribute) and use it in classifying new data
 Numeric prediction
 Model continuous-valued functions (i.e., predict unknown or missing values)

4
 Classification Tasks
 In bank:
 Which loan applicants are “safe” and which are “risky” for the bank.
 At risk management department wishes to detect fraudulent transactions.
 A marketing manager:
 Guess whether a customer with a given profile will buy a new computer
 Understand the sentiment of social media posts regarding a newly released product.
 Detect fake reviews about a new product from an online review site.
 Identify a subscribed customer who is likely to switch to a competitive electronics store (i.e., churn
prediction).
 An IT security analyst:
 wants to know if the network system is under attack (intrusion detection)
 or if a given application is contaminated with malware (malware detection).

5
 Classification—Model Construction, Validation and
Testing
 Model Construction and Training
 Model: Represented as decision trees, rules, mathematical formulas, or other forms
Rules Example: Rule-based classification for approving loans.

 Rule 1: IF income > 50,000 AND credit rating = excellent THEN loan = approved.
 Rule 2: IF income ≤ 50,000 AND debt > 20,000 THEN loan = rejected.
 Output: Approves or rejects loan applications based on these rules.
 Other forms:
 Neural Networks and Support Vector Machines (SVM)
 Assumption: Each sample belongs to a predefined class /class label

 Training Set: The set of samples used for model construction

6
 Classification—Model Construction, Validation and
Testing
 Model Validation and Testing:
 Test: Estimate accuracy of the model
 The known label of test sample VS. 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
 Validation: If the test set is used to select or refine models, it is called validation (or
development) (test) set
 Model Deployment: If the accuracy is acceptable, use the model to classify new data

7
 Chapter 6. Classification: Basic Concepts
 Classification: Basic Concepts
 Decision Tree Induction
 Bayes Classification Methods
 Lazy Learners (or learning from your neighbors)
 Linear Classifiers
 Model Evaluation and Selection
 Techniques to Improve Classification Accuracy
 Summary

8
 Decision Tree Induction: An Example
 Decision tree construction: Training data set: Play Golf?
 A top-down, recursive, divide-and- Outlook Temp Humidity Windy Play Golf
Rainy Hot High False No
conquer process Rainy Hot High True No
 Resulting tree: Overcast Hot High False Yes
outlook Sunny Mild High False Yes
? Sunny Cool Normal False Yes
Sunny Rainy
Sunny Cool Normal True No
Overcast
Overcast Cool Normal True Yes

windy Yes Humidity Rainy Mild High False No

Rainy Cool Normal False Yes
? ?
Sunny Mild Normal False Yes
False True Normal High Rainy Mild Normal True Yes
Overcast Mild High True Yes

Yes No Yes No Overcast Hot Normal False Yes

Sunny Mild High True No
9 [Link]
 Decision Tree Induction: Algorithm
Basic algorithm
 Tree is constructed in a top-down, recursive, divide-and-conquer manner
 At start, all the training examples are at the root
 Examples are partitioned recursively based on selected attributes
 On each node, attributes are selected based on the training examples on that
node, and a heuristic or statistical measure (e.g., information gain, Gini index)

10
 Example: Attribute Selection with Information
Gain
Play
Play Outlook Temp Humidity Windy Golf
Outlook Temp Humidity Windy Golf
Rainy Hot High False No
Sunny Mild High False Yes
Rainy Hot High True No
Sunny Cool Normal False Yes
Rainy Mild High False No
Sunny Cool Normal True No
Rainy Cool Normal False Yes
Sunny Mild Normal False Yes
Rainy Mild Normal True Yes
Sunny Mild High True No

Play
Outlook Temp Humidity Windy Golf
Overcast Hot High False Yes
Overcast Cool Normal True Yes
Overcast Mild High True Yes
Overcast Hot Normal False Yes

11
 Decision Tree Induction: Algorithm
 Conditions for stopping partitioning
 All samples for a given node belong to the same class
 There are no remaining attributes for further partitioning
 There are no samples left
 Prediction
 Majority voting is employed for classifying the leaf

12
 How to Handle Continuous-Valued
Attributes?
 Method 1: Discretize continuous values and treat them as categorical values
 E.g., age: < 20, 20..30, 30..40, 40..50, > 50
 Method 2: Determine the best split point for continuous-valued attribute A
 Sort:, e.g. 15, 18, 21, 22, 24, 25, 29, 31, …
 Possible split point: (ai+ai+1)/2
 e.g., (15+18)/2 = 16.5, 19.5, 21.5, 23, 24.5, 27, 30, …
 The point with the maximum information gain for A is selected as the split-
point for A
 Split: Based on split point P
 The set of tuples in D satisfying A ≤ P vs. those with A > P

13
 Pro’s and Con’s
Pro’s
 Easy to explain (even for non-expert)
 Easy to implement (many software)
 Efficient
 Can tolerant missing data
 White box
 No need to normalize data
 Non-parametric: No assumption on data distribution, no assumption on
attribute independency
 Can work on various attribute types

14
 Con’s
Con’s
 Unstable. Sensitive to noise:
 A minor modification in the dataset (e.g., adding or removing a few data points) can result in a
completely different tree structure.
 Accuracy may be not good enough (depending on your data)
 The optimal splitting is NP. Greedy algorithms are used
 Overfitting

15
 Splitting Measures: Information Gain
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

16
 Information Gain: An Attribute Selection
Measure
 Select the attribute with the highest information gain (used in typical
decision tree induction algorithm: ID3/C4.5)
 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)
17
 Example: Attribute Selection with Information
Gain
Outlook Temp Humidity Windy
Play outlook yes no I(yes, no)
Golf
rainy 2 3 0.971
outlook
Rainy Hot High False No overcast 4 0 0 ?
sunny 3 2 0.971
Sunny Rainy
Rainy Hot High True No
Overcast
Overcast Hot High False Yes
Sunny Mild High False Yes
9 9 5 5
Sunny Cool Normal False Yes Info ( D ) I (9,5)  log 2 ( )  log 2 ( ) 0.940
14 14 14 14
Sunny Cool Normal True No 5 4 5
Overcast Cool Normal True Yes 𝐼𝑛𝑓 𝑜𝑜𝑢𝑡𝑙𝑜𝑜𝑘 ( 𝐷 )= 𝐼 ( 3 , 2) + 𝐼 ( 4 , 0) + 𝐼 ( 2 , 3 ) =0.694
14 14 14
Rainy Mild High False No
Rainy Cool Normal False Yes
means “outlook=rainy” has 5 out of 14 samples, with 2 yes’es
Sunny Mild Normal False Yes
Rainy Mild Normal True Yes and 3 no’s.
Overcast Mild High True Yes Hence
Overcast Hot Normal False Yes
Sunny Mild High True No
𝐺𝑎𝑖𝑛(𝑜𝑢𝑡𝑙𝑜𝑜𝑘)=𝐼𝑛𝑓𝑜 (𝐷)− 𝐼𝑛𝑓 𝑜𝑜𝑢𝑡𝑙𝑜𝑜𝑘 (𝐷)=0.246

18
 Example: Attribute Selection with Information
Gain
Play
Play Outlook Temp Humidity Windy Golf
Outlook Temp Humidity Windy Golf
Rainy Hot High False No
Sunny Mild High False Yes
Rainy Hot High True No
Sunny Cool Normal False Yes
Rainy Mild High False No
Sunny Cool Normal True No
Rainy Cool Normal False Yes
Sunny Mild Normal False Yes
Rainy Mild Normal True Yes
Sunny Mild High True No

= 0.971
Outlook Temp Humidity Windy Play
Golf
Overcast Hot High False Yes 4 4 0 0
𝐼 ( 4 , 0 )=− log 2 − log 2 = 0
Overcast Cool Normal True Yes 4 4 4 4
Overcast Mild High True Yes
Overcast Hot Normal False Yes = 0.971

19
 Example: Attribute Selection with Information
Gain
Outlook Temp Humidity Windy Play Temp Yes No I(Yes, No)
Golf Hot 2 2 ? Similarly, we can get
Rainy Hot High False No Mild 4 2 ?
Rainy Hot High True No Cool 3 1 ?
Overcast Hot High False Yes
Sunny Mild High False Yes Windy Yes No I(Yes, No)
Sunny Cool Normal False Yes True ? ? ?
Sunny Cool Normal True No False ? ? ?
Overcast Cool Normal True Yes
Rainy Mild High False No Humidity Yes No I(Yes, No)
Rainy Cool Normal False Yes Normal 6 1 ?
Sunny Mild Normal False Yes High 3 4 ?
Rainy Mild Normal True Yes
Overcast Mild High True Yes
Overcast Hot Normal False Yes
Sunny Mild High True No

20
 Example: Attribute Selection with Information
Gain
Play Play
Outlook Temp Humidity Windy Windy Yes No I(Yes, No) Outlook Temp Humidity Windy Golf
Golf
Rainy Hot High False No True 3 3 ? Rainy Hot High True No
Overcast Hot High False Yes False 6 2 ? Sunny Cool Normal True No
Sunny Mild High False Yes Overcast Cool Normal True Yes
Sunny Cool Normal False Yes Rainy Mild Normal True Yes
Rainy Mild High False No Overcast Mild High True Yes
Rainy Cool Normal False Yes Sunny Mild High True No
Sunny Mild Normal False Yes
Overcast Hot Normal False Yes
6 8
𝐼𝑛𝑓 𝑜𝑊𝑖𝑛𝑑𝑦 ( 𝐷 )= 𝐼 ( 3 , 3 )+ 𝐼 ( 6 , 2 )=0.43∗ 1+0.57 ∗ 0.811=0.892
14 14

=1 𝐺𝑎𝑖𝑛(𝑊𝑖𝑛𝑑𝑦 )=𝐼𝑛𝑓𝑜( 𝐷)− 𝐼𝑛𝑓 𝑜𝑜𝑢𝑡𝑙𝑜𝑜𝑘 ( 𝐷)=¿

0.048
= 0.811

21
 Gain Ratio: A Refined Measure for Attribute Selection
 Information gain measure is biased towards attributes with a large number of
values (e.g. ID)
 Such attributes often have high Information Gain but may not provide meaningful splits.
 Gain ratio: Overcomes the problem (as a normalization to information gain)
v | Dj | | Dj |
SplitInfo A ( D )   log 2 ( )
j 1 |D| |D|
 GainRatio(A) = Gain(A)/SplitInfo(A)
 The attribute with the maximum gain ratio is selected as the splitting attribute
 Gain ratio is used in a popular algorithm C4.5 (a successor of ID3) by R. Quinlan
 Example

 GainRatio(temp) = 0.029/1.557 = 0.019

22