Supervised Learning

Classification problems.

SCG, BIT Jaipur 1

Decision Tree Algorithm

SCG, BIT, JPR 2

Decision tree induction
Decision tree induction is the learning of decision trees from class-labeled training data or
tuples.
Below is a data set for AllElectronics and customers which are likely to purchase a computer.
age income student credit_rating buys_computer
youth high no fair no
youth high no excellent no Decision Tree
middle_age
high no fair yes
senior medium no fair yes age?
senior low yes fair yes
senior low yes excellent no youth middle_age senior
middle_age
low yes excellent yes
youth medium no fair no credit rating?
youth low yes fair yes
student? yes
senior medium yes fair yes excellent fair
no yes
youth medium yes excellent yes
middle_age
medium no excellent yes no yes no yes
middle_age
high yes fair yes
senior medium no excellent no
3
Decision tree induction
A decision tree is a flowchart-like tree structure (shown in fig), where
a) The topmost node in a tree is the root node
b) each internal node (nonleaf node) and root node denote a test on an attribute,
c) each branch represents an outcome of the test, and
d) each leaf node (or terminal node) holds a class label.
Buying_computer Decision Tree
It represents the concept buys_computer,
.
that is, it predicts whether a customer at
AllElectronics is likely to purchase a
computer.

4
Decision tree
age income student credit_rating buys_computer
youth high no fair no
youth high no excellent no
-Training data set: Buys_computer middle_age
high no fair yes
senior medium no fair yes
-Resulting tree: senior low yes fair yes
senior low yes excellent no
middle_age
low yes excellent yes
youth medium no fair no
youth low yes fair yes
senior medium yes fair yes
youth medium yes excellent yes
middle_age
medium no excellent yes
middle_age
high yes fair yes
senior medium no excellent no

5
Decision Tree Induction Algorithm
ID3 Algorithm: (Using information gain)
During early 1980s, J. Ross Quinlan, a researcher in machine learning, developed a decision tree
algorithm known as ID3 (Iterative Dichotomiser).

C4.5 Algorithm: (Using Gain_Ratio)

Quinlan later presented C4.5 (a successor of ID3), which became a benchmark to which newer
supervised learning algorithms are often compared.

CART Algorithm: (Using Gini Index)

In 1984, a group of statisticians (L. Breiman, J. Friedman, R. Olshen, and C. Stone) published the
book Classification and Regression Trees (CART), which described the generation of binary decision
trees.

SCG, BIT, JPR 6

Design of 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 considered at root node.
– Attributes are made categorical (if continuous-valued, they are discretized in advance)
– Test attributes are selected on the basis of a heuristic or statistical measure (e.g., information
gain, gain ratio or gini index)
– Datasets are partitioned recursively based on selected test attributes

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

SCG, BIT, JPR 7

Attribute Selection Measures

It is an information measure for the splitting criterion to select an attribute that “best” separates a
given partition D, of class-labeled training tuples into individual classes.

At split, ideally we need each partition should be pure. (i.e., all the tuples that fall into a given
partition would belong to the same class).

The attribute selection measure provides a score about each attribute.

The attribute having the best (high) score for the measure is chosen as the splitting attribute for
the given tuples.

Attribute selection measure can be given in one of the following popular Measures.
a) Information gain : used in ID3 Algorithm
b) Gain Ratio : used in C4.5 Algorithm
c) Gini Index : used in CART Algorithm
SCG, BIT, JPR 8
Amount of Information measure
We can calculate the amount of information of an event using the probability of the event. This is
called “Shannon information,” simply the “information”.

It is also called Entropy and denoted as H.

It can be calculated for a discrete event x as follows:

H(x) = -log2( p(x) ) ) #The negative sign results in positive or zero.

Log base-2 means that the units of the information measure is in bit
(binary digits). i.e. the number of bits required to represent the event.

Information will be zero when the probability of an event is 1.0 or 0 i.e.

complete certainty for true or complete certainty for false.

9
Amount of Information measure
For discrete event of random variable Y taking m distinct values {y1, y2…..ym}
The entropy is given as:
m
H ( y )   pi log 2 ( pi ) where p (Y  yi )
i 1

Higher entropy mean => higher uncertainty

Lower entropy mean => Lower uncertainty

SCG, BIT, JPR 10

Information Gain:
Based on pioneering work by Claude Shannon on information theory.

The attribute with the highest information gain is chosen as the splitting attribute for
node N.

Our purpose here is to minimize the information need in the resulting partitions so
that, they should reflect the least randomness or “impurity”.

Also minimizes the expected number of tests needed to classify a given tuple and
guarantees that a simple (but not necessarily the simplest or optimized) tree is
found.

11
Information Gain:
Let the dataset D be a training set of class-labeled tuples.

Suppose the class label attribute has m distinct values defining m distinct classes, Ci (for i = 1,….., m).

Let Ci,D be the set of tuples of class Ci in D.

Let |D| and |Ci,D| denote the number of tuples (Cardinality) in D and Ci,D respectively.

The expected information needed to classify a tuple in D is given by

m
Info( D)   pi log 2 ( pi ) where , pi  Ci , D D
i 1

Info(D) is just the average amount of information needed to identify the class label of a tuple in D.
Info(D) is also known as the entropy of D.
12
Information Gain:
Now, suppose we have to partition the tuples in D on some attribute A having v distinct values,
{a1, a2, ……. , av}, as observed from the training data.

If A is discrete-valued, these values correspond directly to the v outcomes of a test on A.

Attribute A can be used to split D into v partitions or subsets,

{D1, D2, ….. , Dv}, where Dj contains those tuples in D that have outcome aj of A.

These partitions would correspond to the branches grown from node N.

Ideally, we would like this partitioning to produce an exact classification of the tuples. i.e, we would
like
for each partition to be pure.

SCG, BIT, JPR 13

Information Gain:
So, information expected (after using A to split D into v partitions) to arrive at an exact classification is:
v | Dj |
Info A ( D )    Info( D j )
j 1 |D|

The term |Dj|/|D| acts as the weight (or proportion) of the jth partition.

The smaller the expected information required, the greater the purity of the partitions.

Now, Information gain is defined as the difference between the original information requirement (i.e.,
based on just the proportion of classes) and the new requirement (i.e., obtained after partitioning on
A).

Gain(A)  Info(D)  Info A(D)

Gain(A) tells the expected reduction in the information requirement caused by knowing the value of A.

SCG, BIT, JPR 14

 age income student credit_rating buys_computer
Example on Information gain youth
youth
high
high
no fair
no excellent
no
no
middle_age
high no fair yes
Computing the Info(D) for our buy_computer example: senior medium no fair yes
senior low yes fair yes
senior low yes excellent no
middle_age
low yes excellent yes
Nos. of tuples of class Yes in D : 9 youth medium no fair no
Nos. of tuples of class No in D : 5 youth low
senior medium
yes fair
yes fair
yes
yes
The expected information needed to classify a tuple in D: youth medium yes excellent yes
middle_age
medium no excellent yes
middle_age
high yes fair yes
senior medium no excellent no

m
Info( D )   pi log 2 ( pi ) where , pi  Ci , D D
i 1

SCG, BIT, JPR 15

Example on Information gain age
youth high
income student credit_rating buys_computer
no fair no
youth high no excellent no
Computing the InfoA(D): i.e. computing the info for each attribute of middle_age
high no fair yes
the example. senior medium no fair yes
a) Attribute Age: senior low yes fair yes
senior low yes excellent no
We need to look at the distribution of yes and no tuples for each category of middle_age
low yes excellent yes
age. youth medium no fair no
youth low yes fair yes
senior medium yes fair yes
-For the category “youth,” there are two yes tuples and three no tuples. youth medium yes excellent yes
middle_age
medium no excellent yes
-For the category “middle aged,” there are four yes tuples and zero no tuples. middle_age
high yes fair yes
senior medium no excellent no

-For the category “senior,” there are three yes tuples and two no tuples.
v | Dj |
Info Age ( D )    Info( D j )
j 1 |D|

16
Example on Information gain
Now the information gain for attribute age:
Gain(age) = Info(D) - Infoage(D) = 0.940 - 0.694 = 0.246 bits.

Similarly, we can compute

Gain(income) = ?
Gain(student) = ?
Gain(credit_rating) = ?

17
Example on Information gain
Now the information gain for attribute age:
Gain(age) = Info(D) - Infoage(D) = 0.940 - 0.694 = 0.246 bits.

Similarly, we can compute

Gain(income) = 0.029 bits
Gain(student) = 0.151 bits
Gain(credit_rating) = 0.048 bits.

. the maximum gain is in

Here
case of age, so the age can
be chosen for splitting the
Dataset D

SCG, BIT, JPR 18

Problems with Information gain (ID3)
• The information gain measure is biased toward tests with many outcomes.

• i.e. it prefers to select attributes having a large number of values.

• For example, consider an attribute that acts as a unique identifier such as product ID.

• A split on productID would result in a large number of partitions (as many as there are values),
each one containing just one tuple.

• Because each partition is pure, the information required to classify data set D based on this
partitioning would be InfoproductID(D) = 0.

• Therefore, the information gained by partitioning on this attribute is maximal.

• But clearly, such a partitioning is useless for classification.

SCG, BIT, JPR 19
 Gain Ratio for Attribute Selection
Gain ratio is used to overcome the problem of Information gain.
Gain Ratio applies a kind of normalization to information gain using a “split information” value defined
analogously with Info(D) as
v | Dj |  | Dj | 
SplitInfo A ( D)    log 2  
j 1 |D|  |D| 

Note that, for each outcome v , it considers the number of tuples having that outcome with respect to the total
number of tuples in D.

It differs from information gain, which measures the information with respect to classification that is acquired
based on the same partitioning (i.e. not the total i.e. Only Dj).

The gain ratio is now defined as:

Gain( A)
GainRatio( A) 
SplitInfo A ( D)
20
 age income student credit_rating buys_computer
Gain Ratio for Attribute Selection youth high
youth high
no fair
no excellent
no
no
middle_age
high no fair yes
The gain ratio in our example for income attribute is : senior medium no fair yes
1) Gain(income) = 0.029 senior low yes fair yes
senior low yes excellent no
middle_age
low yes excellent yes
2) SplitInfoincome(D) youth medium no fair no
youth low yes fair yes
senior medium yes fair yes
youth medium yes excellent yes
middle_age
medium no excellent yes
middle_age
high yes fair yes
senior medium no excellent no

SO, the gain-Ratio (income): 0.029/1.557 = 0.019

The attribute with the maximum gain ratio is selected as the splitting attribute. 21
Gini Index (CART)
Gini Index measures the impurity of D, a data partition or set of training tuples, as
m
Gini ( D )  1   pi2 where pi is the probability of class Ci and is
i 1 estimated by |Ci, D|/|D|
This is the measure of total impurities.

Now we select an attributes and find the Gini index on it, and the get the difference of it with total. Which
attribute shows the maximum reduction of impurity is selected.
The Gini index considers a binary split for each attribute.

Let’s first consider the case where A is a discrete-valued attribute having v distinct values, {a1, a2, : : : , av},
occurring in D.

To determine the best binary split on A, we examine all the possible subsets that can be formed using known
values of A.

Each subset, SA, can be considered as a binary test for attribute A of the form “A ϵ SA?”

22
Gini Index (CART)
For a given tuple, this test is satisfied if the value of A for the tuple is among the values listed
in SA.

If A has v possible values, then there are 2v possible subsets.

For example, if income has three possible values, namely

{low, medium, high}, then the possible subsets are {low, medium, high}, {low, medium}, {low,
high}, {medium, high}, {low}, {medium}, {high}, and {}.

We exclude the power set, {low, medium, high}, and the empty set from consideration since,
conceptually, they do not represent a split.

Therefore, there are 2v- 2 possible ways to form two partitions of the data, D, based on a
binary split on A.
23
Gini Index (CART)
For example, if a binary split on attribute A partitions D into D1 and D2.

Then Gini index of D with A is given as

|D1| |D |
gini A ( D)  gini( D1)  2 gini( D 2)
|D| |D|

Reduction in Impurity:

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

The attribute, which provides the smallest giniA(D) (or the maximum reduction in impurity) is chosen to
split the node.

24
Computation of Gini Index
age income student credit_rating buys_computer
youth high no fair no
youth high no excellent no
middle_age
high no fair yes
In our example: senior medium no fair yes
senior low yes fair yes
senior low yes excellent no
2 2 middle_age
low yes excellent yes
 9  5 youth medium no fair no
gini ( D )  1        0.459 youth low yes fair yes
 14   14  senior medium
youth medium
yes fair
yes excellent
yes
yes
middle_age
medium no excellent yes
middle_age
high yes fair yes
senior medium no excellent no

To find the splitting criterion for the tuples in D, we need to compute the Gini index for each attribute.

Let’s consider attribute income and each of the possible splitting subsets.

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.

25
Computation of Gini Index
The Gini index value computed based on this partitioning is:

SCG, BIT, JPR 26

Computation of Gini Index
Income Gini index values
0.443 (for (the subsets {low, medium} or {high})

Similarly, Income Gini index values for splits on the remaining subsets are :

0.458 (for the subsets {low, high} or {medium})

0.450 (for the subsets {medium, high} or {low} ).

Therefore, the best binary split for attribute income is on {low, medium} (or {high})
because it minimizes the Gini index.

SCG, BIT, JPR 27

Computation of Gini Index
Evaluating age, we obtain {youth, senior} (or {middle_ aged}) as the best split for age with a Gini
index
of 0.357;

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.

SCG, BIT, JPR 28

Decision Tree classifier for Iris flower dataset

SCG, BIT, JPR 29