Module 3
Classification
1
Classification vs. Prediction
■ Classification
■ A process of finding a model that describes and
distinguishes the data classes.
■ predicts categorical class labels (discrete or nominal)
■ Typical applications
■ Credit approval
■ Target marketing
■ Medical diagnosis
■ Fraud detection
2
Classification vs. Prediction
■ Classification
■ A process of finding a model that describes and
distinguishes the data classes.
■ Predicts categorical class labels (discrete or nominal)
3
Classification vs. Prediction
■ Prediction
■ Models continuous-valued functions, i.e., predicts
unknown or missing values
■ Regression analysis is a statistical methodology that is
most often used for numeric prediction.
■ Classification and numeric prediction are the two major
types of prediction problems.
4
Classification—A Two-Step Process
(Learning step+Classification step)
■ In the first step, we build a classification model by
learning from training dataset — Supervised Learning
■ In the second step, we determine if the model’s
accuracy is acceptable, and if so, we use the model to
classify new data.
5
Data classification Process
Step 1:Learning Step
Y = f(X)
Y: Class label
X=Given tuple
The data classification process: (a) Learning step:Training data are analyzed by a classification algorithm.
Here, the class label attribute is loan decision, and the learned model or classifier is represented in the form of
classification rules.
6
Data Classification Process
Step 2:Classification Step
(b) Classification step : 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.
● The accuracy of classifier on a given test set is % of test set tuples that are correctly classified by
classifier.
7
Decision Tree Induction
(Learning of a decision tree from class labeled training tuples)
8
Decision Tree Induction
■ ID3 (Iterative Dichotomiser), C4.5, CART(Classification And
Regression Trees) Algorithms.
■ These algorithms adopt a greedy (i.e., non backtracking) approach in
which decision trees are constructed in a top-down recursive
divide-and-conquer manner.
■ It starts with a training set of tuples and their associated class labels.
The training set is recursively partitioned into smaller subsets as the
tree is being built.
9
10
Let A be the splitting attribute. (a) If A is discrete-valued, then one branch is grown for each
known value of A. (b) If A is continuous-valued, then two branches are grown,
corresponding to A<= split point and A > split point.
(c) If A is discrete-valued and a binary tree must be produced, then the test is of the form
A ∈ SA?, where SA is the splitting subset for A. Partitioning Scenarios 11
Algorithm for Decision Tree Induction
1. The tree starts as a single node, N, representing the training tuples in D
2. If the tuples in D are all of the same class, then node N becomes a leaf and
is labeled with that class.
3. Otherwise, the algorithm calls Attribute selection method to determine the
splitting criterion.
▪ The splitting criterion tells us which attribute to test at node N by
determining the “best” way to separate or partition the tuples in D into
individual classes.
▪ The splitting criterion also tells us which branches to grow from node N
with respect to the outcomes of the chosen test.
▪ More specifically, the splitting criterion indicates the splitting attribute
and may also indicate either a split-point or a splitting subset.
▪ The splitting criterion is determined so that, ideally, the resulting partitions
at each branch are as “pure” as possible.
▪ A partition is pure if all the tuples in it belong to the same class.
12
Algorithm for Decision Tree Induction
4. The node N is labeled with the splitting criterion, which serves as a test at the
node. A branch is grown from node N for each of the outcomes of the splitting
criterion. The tuples in D are partitioned accordingly.
5. The algorithm uses the same process recursively to form a decision tree for the
tuples at each resulting partition, Dj , of D .
6. The recursive partitioning stops only when any one of the following terminating
conditions is true:
1. All the tuples in partition D (represented at node N) belong to the same
class.
2. There are no remaining attributes on which the tuples may be further
partitioned.
■ In this case, majority voting is employed. This involves converting node N into a leaf and
labeling it with the most common class in D. Alternatively, the class distribution of the node
tuples may be stored.
3. There are no tuples for a given branch, that is, a partition Dj is empty.
■ In this case, a leaf is created with the majority class in D.
7. The resulting decision tree is returned.
13
Attribute Selection Measures
(Also known as Splitting Rules)
■ An attribute selection measure is a heuristic for selecting the splitting
criterion that “best” separates a given data partition, D , of class-labeled
training tuples into individual classes.
■ The attribute selection measure provides a ranking for each attribute
describing the given training tuples.
■ The three popular attribute selection measures—
1. information gain
2. gain ratio, and
3. Gini index
14
Attribute Selection Measures:
Information Gain (ID3 algorithm)
■ This measure is based on pioneering work by Claude Shannon on
information theory, which studied the value or “information
content” of messages.
■ The attribute with the highest information gain is chosen as the
splitting attribute for node N.
■ This attribute minimizes the information needed to classify the tuples
in the resulting partitions and reflects the least randomness or
“impurity” in these partitions.
■ Such an approach minimizes the expected number of tests needed to
classify a given tuple and guarantees that a simple (but not
necessarily the simplest) tree is found.
15
Attribute Selection Measure:
Information Gain (ID3)
■ 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:
■ Information needed (after using A to split D into v partitions) to
classify D:
■ Information gained by branching on attribute A
Highest
Information
gain 16
Information Gain (ID3)
Let pi be the probability that an arbitrary tuple in D belongs to class C i , estimated by
pi =|Ci, D|/|D|
Expected information (entropy) needed to classify a tuple in D:
Information needed (after using A to split D into v partitions) to classify D:
Information gained by branching on attribute A
■ Select the attribute with the highest information gain.
Example: Information Gain
18
Example: Information Gain
19
■ The expected information needed to classify a tuple in D if the tuples are
partitioned according to age is:
■ Similarly, compute Gain(income) ,Gain(student) ,and Gain(credit rating)
20
Example: Information Gain(Cntd…)
■ we get Gain(income) = 0.029 bits, Gain(student) = 0.151 bits, and
Gain(credit rating) = 0.048 bits.
■ Because age has the highest information gain among the attributes, it is
selected as the splitting attribute.
■ Node N is labeled with age, and branches are grown for each of the
attribute’s values.
21
• Notice that the tuples falling into the partition for age = middle_aged all belong to the
same class.
• Because they all belong to class “yes,” a leaf should therefore be created at the end
of this branch and labeled “yes.” 22
The final decision tree returned by the algorithm
23
Using following training data set ,create decision tree classification model.
Income Age Own House?
1 Very High Young Yes
2 High Medium Yes
3 Low Young Rented
4 High Medium Yes
5 Very High Medium Yes
6 Medium Young Yes
7 High Old Yes
8 Medium Medium Rented
9 Low Medium Rented
10 Low Old Rented
11 High Young Yes
12 Medium Old Rented
24
Computing Information-Gain for
Continuous-Value Attributes
■ Let attribute A be a continuous-valued attribute
■ Must determine the best split point for A
■ Sort the values of A in increasing order.
■ Typically, the midpoint between each pair of adjacent values where
there is a change in classification 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
25
Example: Computing Information-Gain
for Continuous-Value Attributes
Step 1: Sort the values of A in increasing order.
Temp Play Step 2: Determine the split points by averaging
Tennis?
consecutive values where there is a change in
40 NO classification.
So split points here are :
48 NO
point 1= (48+60)/2=54 and
60 YES point 2 =( 80+90)/2= 85
72 YES
Step 3: Evaluate the information gain of the
80 YES candidate split points 54 and 85 and select the
split point.
90 NO
26
Example: Computing Information-Gain
for Continuous-Value Attributes
Entropy(D)=Info(D)=-(3/6) (log 3/6)- (3/6)(log (3/6) =1
Temp Play Tennis? Consider split point=54.
40 NO Temp <=54 : 2 tuples(Yes=0,No=2)
Temp>54 : 4 tuples(Yes=3,No=1)
48 NO
60 YES
72 YES
80 YES Info Temp(D) = 0.54
90 NO
Info Gain(Temp) = 1 - 0.54=0.46
Similarly for split point=85, calculate Info Gain(Temp) = 0.1908
As information gain for split point=54 is high, it will be selected.
27
Gain Ratio for Attribute Selection (C4.5)
■ ‘Information gain’ measure is biased towards attributes with a large
number of values(e.g. Unique ID attribute like Product_ID)
■ C4.5 uses an extension to information gain known as gain ratio, which
attempts to overcome this bias.
■ It applies a kind of normalization to information gain using a “split
information” value defined analogously with Info(D) as
■ This value represents the potential information generated by splitting the
training data set, D, into v partitions, corresponding to the v outcomes of a
test on attribute A.
■ The gain ratio is defined as
■ GainRatio(A) = Gain(A)/SplitInfoA(D)
■ The attribute with the maximum gain ratio is selected as the splitting
attribute 28
Example: Gain Ratio
Calculate Gain Ratio(Income) 29
Example: Gain Ratio for income attribute
■ From previous example, Gain(income) = 0.029.
■ A test on income attribute splits the data of Table into three partitions,
namely low, medium, and high, containing four, six, and four tuples,
respectively.
■ GainRatio(income) = Gain(income)/SplitInfoincome(D)
■ Therefore, GainRatio(income) = 0.029 /1.557 = 0.019.
■ The attribute with the maximum gain ratio is selected as the splitting
attribute
■ Drawback: tends to prefer unbalanced splits in which one partition is much
smaller than the others. 30
Gini index (CART)
■ Gini index measures the impurity of D, a data partition or set of training
tuples, as
■ The Gini index considers a binary split for each attribute.
■ Case 1: A is discrete-valued: To determine the best binary split on
discrete valued attribute A, we examine all the possible subsets of the
known values of A.
■ Each subset, SA, can be considered as a binary test for attribute A of the
form “A Є SA?”
■ If A has v possible values, then there are 2v possible subsets.
■ Out of these, there are 2v -2 possible ways to form two partitions of the
data, D, based on a binary split on A.
31
Gini index (CART)
■
■ For each attribute, each of the possible binary splits is considered.
■ For a discrete-valued attribute, the subset that gives the minimum Gini index
for that attribute is selected as its splitting subset.
■ The reduction in impurity that would be incurred by a binary split on a discrete- or
continuous-valued attribute A is
■ The attribute that maximizes the reduction in impurity (or, equivalently, has the
minimum Gini index) is selected as the splitting attribute. This attribute and its
splitting subset (for a discrete-valued splitting attribute) together form the splitting
criterion.
32
Gini index (Continuous-valued attribute)
■ For continuous-valued attributes, each possible split-point must be
considered.
■ The strategy is to take the midpoint between each pair of (sorted)
adjacent values as a possible split-point.
■ The point giving the minimum Gini index for a given (continuous-valued)
attribute is taken as the split-point of that attribute.
■ Recall that for a possible split-point of A, 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
■ The attribute that maximizes the reduction in impurity (or, equivalently,
has the minimum Gini index) is selected as the splitting attribute. This
attribute and its split-point (for a continuous-valued splitting attribute)
together form the splitting criterion.
33
Gini index (Continuous-valued attribute)
■ For continuous-valued attributes, each possible split-point must be
considered.
■ The strategy is to take the midpoint between each pair of (sorted)
adjacent values as a possible split-point.
■ The point giving the minimum Gini index for a given (continuous-valued)
attribute is taken as the split-point of that attribute.
■ Recall that for a possible split-point of A, 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
■ The attribute that maximizes the reduction in impurity (or, equivalently,
has the minimum Gini index) is selected as the splitting attribute. This
attribute and its split-point (for a continuous-valued splitting attribute)
together form the splitting criterion.
34
Example: Gini Index
35
Example: Gini index
■ Ex: Let D be the training data where there are nine tuples belonging to the class
buys computer = yes and the remaining five tuples belong to the class buys
computer = no.
■ A (root) node N is created for the tuples in D. We first compute the impurity of D
as:
■ To find the splitting criterion for the tuples in D, we need to compute the Gini index
for each attribute.
■ Let’s start with the attribute income and and Consider the subset {low, medium}.
This would result in 10 tuples in partition D1 satisfying the condition “income Є
{low, medium}.” The remaining four tuples of D would be assigned to partition D2.
■ The Gini index value computed based on this partitioning is
0.458
Giniincome Є (low,high}(D) =
Giniincome Є (medium,high}(D) 0.450
=
• Therefore, the best binary split for attribute income is on {low, medium} or {high}
because it minimizes the Gini index. 36
Example: Gini index (Cntd…)
■ Evaluating age, we obtain Giniage Є (youth,senior}(D)=0.357 = Giniage Є (middle aged}(D)
■ The attributes student and credit rating are both binary, with Gini index
values of 0.367 and 0.429, respectively.
■ The attribute age and splitting subset {youth, senior} therefore give the
minimum Gini index overall, with a reduction in impurity of 0.459 - 0.357 =
0.102. The binary split “age Є {youth, senior?}” results in the maximum
reduction in impurity of the tuples in D and is returned as the splitting
criterion.
■ Node N is labeled with the criterion, two branches are grown from it, and
the tuples are partitioned accordingly.
37
Comparing Attribute Selection Measures
■ 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
■ Although biased, these measures give reasonably good
results in practice.
38
Other Attribute selection measures
1. CHAID, a decision tree algorithm that is popular in marketing, uses an attribute
selection measure that is based on the statistical x2 test for independence.
2. C-SEP (which performs better than information gain and the Gini index in certain
cases) and G-statistic (an information theoretic measure that is a close
approximation to 2 distribution).
3. Attribute selection measures based on the Minimum Description Length (MDL)
principle have the least bias toward multivalued attributes.
4. Other attribute selection measures consider multivariate splits (i.e., where the
partitioning of tuples is based on a combination of attributes, rather than on a
single attribute)
“Which attribute selection measure is the best?”
■ It has been shown that the time complexity of decision tree induction generally
increases exponentially with tree height. Hence, measures that tend to produce
shallower trees (e.g., with multiway rather than binary splits, and that favor more
balanced splits) may be preferred.
■ However, some studies have found that shallow trees tend to have a large number
of leaves and higher error rates.
■ Despite several comparative studies, no one attribute selection measure has been
found to be significantly superior to others. Most measures give quite good results.
39
Overfitting and Tree Pruning
■ Overfitting:
■ When a decision tree is built, many of the branches will reflect anomalies in the
training data due to noise or outliers.
■ Tree pruning methods address this problem of overfitting the data.
■ Such methods typically use statistical measures to remove the least-reliable
branches.
40
Overfitting and Tree Pruning
■ Two approaches to avoid overfitting : Prepruning and Postpruning
■ Prepruning:
■ Halt tree construction early (e.g., by deciding not to further split or partition the
subset of training tuples at a given node).
■ Upon halting, the node becomes a leaf.
■ The leaf may hold the most frequent class among the subset tuples or the
probability distribution of those tuples.
■ Difficult to choose an appropriate threshold
■ Postpruning:
■ Remove branches from a “fully grown” tree—A subtree at a given node is pruned
removing its branches and replacing it with a leaf.
■ The leaf is labeled with the most frequent class among the subtree being
replaced.
41
42