UNIT-3

Classification
General Approach to Solving a Classification Problem
A classification technique (or classifier) is a systematic approach to building
classification models from an input data set. Examples include decision tree
classifiers, rule-based classifiers, neural networks, support vector machines, and
na¨ıve Bayes classifiers.
Each technique employs a learning algorithm to identify a model that best fits the
relationship between the attribute set and class label of the input data. The model
generated by a learning algorithm should both fit the input data well and correctly
predict the class labels of records it has never seen before.
Figure 4.3 shows a general approach for solving classification problems. First, a
training set consisting of records whose class labels are known must be
provided. The training set is used to build a classification model, which is
subsequently applied to the test set, which consists of records with unknown
class labels.
 Predicted Class
Class Class
=1 =0
Actu Class f11 f10
al =1
Clas Class f01 f00
s =0
Confusion matrix for a 2-class problem.
Evaluation of the performance of a classification model is based on the counts
of test records correctly and incorrectly predicted by the model. These counts are
tabulated in a table known as a confusion matrix. Table 4.2 depicts the
confusion matrix for a binary classification problem. Each entry fij in this table
denotes the number of records from class i predicted to be of class j. For
instance, f01 is the number of records from class 0 incorrectly predicted as
class 1. Based on the entries in the confusion matrix, the total number of
correct predictions made by the model is (f11 + f00) and the total number of
incorrect predictions is (f10 + f01).
Although a confusion matrix provides the information needed to determine how
well a classification model performs, summarizing this information with a single
number would make it more convenient to compare the performance of different
models. This can be done using a performance metric such as accuracy, which
is defined as follows:

𝑁𝑜 𝑜𝑓 𝐶𝑜𝑟𝑟𝑒𝑐𝑡 𝑃𝑟𝑒𝑑𝑖𝑐𝑡𝑖𝑜𝑛𝑠 𝑓11 + 𝑓00

𝐴𝑐𝑐𝑢𝑟𝑎𝑐𝑦 = = +
Total No of Predictions 𝑓11 𝑓10 + 𝑓01 + 𝑓00
Equivalently, the performance of a model can be expressed in terms of its
error rate, which is given by the following equation:

𝑁𝑜 𝑜𝑓 𝑊𝑟𝑜𝑛𝑔 𝑃𝑟𝑒𝑑𝑖𝑐𝑡𝑖𝑜𝑛𝑠 𝑓10 + 𝑓01

𝐸𝑟𝑟𝑜𝑟 𝑅𝑎𝑡𝑒 = = +
Total No of Predictions 𝑓11 𝑓10 + 𝑓01 + 𝑓00
1. Decision Tree induction:
A decision tree is a structure that includes a root node, branches, and leaf nodes.
Each internal node denotes a test on an attribute, each branch denotes the outcome
of a test, and each leaf node holds a class label. The topmost node in the tree is the
root node.
The following decision tree is for the concept buy_computer that indicates whether a
customer at a company is likely to buy a computer or not. Each internal node
represents a test on an attribute. Each leaf node represents a class.

The benefits of having a decision tree are as follows −

• It does not require any domain knowledge.
• It is easy to comprehend.
• The learning and classification steps of a decision tree are simple and fast.
Decision Tree Induction Algorithm
A decision tree algorithm known as ID3 (Iterative Dichotomiser). Later C4.5, which
was the successor of ID3. ID3 and C4.5 adopt a greedy approach. In this algorithm,
there is no backtracking; the trees are constructed in a top-down recursive divide-and-
conquer manner. Generating a decision tree form training tuples of data partition D
Algorithm : Generate_decision_tree
Input:
Data partition, D, which is a set of training tuples and their associated class labels.
attribute_list, the set of candidate attributes. Attribute selection method, a procedure
to determine the splitting criterion that best partitions that the data tuples into
individual classes. This criterion includes a splitting_attribute and either a splitting
point or splitting subset.
Output:
A Decision Tree

Method
create a node N;

if tuples in D are all of the same class, C then

return N as leaf node labeled with class C;

if attribute_list is empty then

return N as leaf node with labeled
with majority class in D;|| majority voting

apply attribute_selection_method(D, attribute_list)

to find the best splitting_criterion;
label node N with splitting_criterion;

if splitting_attribute is discrete-valued and

multiway splits allowed then // no restricted to binary trees

attribute_list = splitting attribute; // remove splitting attribute

for each outcome j of splitting criterion
// partition the tuples and grow subtrees for each partition
let Dj be the set of data tuples in D satisfying outcome j; // a partition

if Dj is empty then
attach a leaf labeled with the majority
class in D to node N;
else
attach the node returned by Generate
decision tree(Dj, attribute list) to node N;
end for
return N;
Methods for selecting best test conditions
Decision tree induction algorithms must provide a method for expressing an attribute
test condition and its corresponding outcomes for different attribute types.

Binary Attributes: The test condition for a binary attribute generates two potential

outcomes.

Nominal Attributes: These can have many values. These can be represented in two
ways.

Ordinal attributes: These can produce binary or multiway splits. The values can be
grouped as long as the grouping does not violate the order property of attribute values.
2. Attribute Selection Measures
➢ 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.
➢ If we were to split D into smaller partitions according to the outcomes of the
splitting criterion, ideally each partition would be pure (i.e., all the tuples that fall into
a given partition would belong to the same class).
➢ Conceptually, the “best” splitting criterion is the one that most closely results in
such a scenario. Attribute selection measures are also known as splitting rules
because they determine how the tuples at a given node are to be split.
➢ The attribute selection measure provides a ranking for each attribute describing
the given training tuples. The attribute having the best score for the measure4 is
chosen as the splitting attribute for the given tuples.
➢ If the splitting attribute is continuous-valued or if we are restricted to binary trees,
then, respectively, either a split point or a splitting subset must also be determined as
part of the splitting criterion.
➢ The tree node created for partition D is labeled with the splitting criterion, branches
are grown for each outcome of the criterion, and the tuples are partitioned accordingly.
➢ There are three popular attribute selection measures—information gain, gain
ratio, and Gini index.

INFORMATION GAIN
This measure is based on pioneering work by Claude Shannon on information theory,
which studied the value or “information content” of message. Let node N represents
or hold the tuple of partition D. The attribute with the highest information gain is chosen
as the splitting attribute for the node N. The expected information needed to classify
a tuple in D is given by,

i.e in our example Entropy(D)=info(D)=-py log2(py)-pn log2(pn)

Where Pi is the probability that an arbitrary tuple in D belongs to class Ci and is
estimated by |Ci,D|/ |D|. Info(D) is the average amount of information needed to identify
the class label of a tuple in [Link](D) is also known as the entropy of [Link] expected
information required to classify a tuple from D, based on the partitioning by attribute
A is calculated by,

Information gain is defined as the difference between the original information

requirement (i.e. based on the classes) and the new requirement (i.e. obtained after
partitioning on A)

The following table presents training set, D, of class labeled tuples randomly selected
from the AllElectronics Customer database.
Example

• Each attribute is discrete value.

• Continues valued attribute have been generated
• The class label attribute, buys_computer have 2 distinct values {yes, no};
therefore, there are 2 distinct class (i.e. m=2)
• Let class C1 corresponds to YES and class C2 corresponds to NO
• There are nine tuples of class yes and five tuples of class no.
• A (root) node N is created for the tuples in D.
• To find the splitting criterion for these tuples, we must compute the information
gain of each attribute.
• Let us consider classes: buys_computer as decision criteria D

• Now Calculate Entropy of age.

• Age Can be
➢ Youth
➢ Middle_aged
➢ Senior
• Youth

• Middle aged

• Senior

Hence, the gain in information from such a partitioning would be

Similarly, we can compute 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.
Gain Ratio:
• The information gain measure is biased toward tests with many outcomes.
• 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 product ID 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 Infoproduct ID(D)= D0.
• Therefore, the information gained by partitioning on this attribute is maximal.
Clearly, such a partitioning is useless for classification.
• C4.5, a successor of ID3, uses an extension to information gain known as gain
ratio, which attempts to overcome this bias.

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

The attribute with the maximum gain ratio is selected as the splitting attribute.
Computation of gain ratio for the attribute income. A test on income splits the data
into three partitions, namely low, medium, and high, containing four, six, and four
tuples, respectively. To compute the gain ratio of income.
Gini Index:
• Gini index measures the impurity of D, a data partition or set of training tuples, as

i.e. Gini(D)=1-py2-pn2
• where pi is the probability that a tuple in D belongs to class Ci and is estimated
by |Ci,D|/|D|.
• The sum is computed over m classes.
• The Gini index considers a binary split for each attribute.
• When considering a binary split, we compute a weighted sum of the impurity of
each resulting partition.

• 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.
• For continuous-valued attributes, each possible split-point must be considered.
• The strategy is similar to that described earlier for information gain, where the
midpoint between each pair of (sorted) adjacent values is taken as a possible split-
point.
• 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 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 either its
splitting subset (for a discrete-valued splitting attribute) or split-point (for a continuous-
valued splitting attribute) together form the splitting criterion.

Induction of a decision tree using the Gini index. Let D be the training data shown
earlier in Table, where there are nine tuples belonging to the class buys computer D
yes and the remaining five tuples belong to the class buys computer D no. A (root)
node N is created for the tuples in D. The Gini index to compute the
impurity of D:

Let A=income: {low, medium, high}

Let D1 satisfies the condition income ε {low, medium} and D2 satisfies income ε {high}
Therefore, no of tuples in D1=10 and in D2=4.

Similarly, the Gini index values for {low, high} and {medium} = 0.458
and for {medium, high} and {low}=0.450.
Evaluating age, we obtain {youth, senior} and {middle_aged} as the best split for age
with a Gini index = 0.375; the attributes student and credit rating are both binary, with
Gini index values of 0.367 and 0.429, respectively.
Gini index overall, with a reduction in impurity of 0.459-0.357=0.102.

4.1 Model Overfitting

The errors committed by a classification model are generally divided into two types:
training errors and generalization errors. Training error, also known as resubstitution
error or apparent error, is the number of misclas- sification errors committed on training
records, whereas generalization error is the expected error of the model on previously
unseen records.
4.1.1 Overfitting Due to Presence of Noise
Consider the training and test sets shown in Tables 4.3 and 4.4 for the mammal
classification problem. Two of the ten training records are mislabeled: bats and whales
are classified as non-mammals instead of mammals.
A decision tree that perfectly fits the training data is shown in Figure 4.25(a). Although
the training error for the tree is zero, its error rate on

Table 4.3. An example training set for classifying mammals. Class labels with asterisk symbols repre- sent mislabeled
records.

Name Body Gives Four- Hibernates Class

Temperature Birth legged Label
porcupine warm-blooded yes yes yes yes
Cat warm-blooded yes yes no yes
bat warm-blooded yes no yes no∗
whale warm-blooded yes no no no∗
salamander cold-blooded no yes yes no
komodo dragon cold-blooded no yes no no
python cold-blooded no no yes no
salmon cold-blooded no no no no
eagle warm-blooded no no no no
guppy cold-blooded yes no no no

Table 4.4. An example test set for classifying mammals.

Name Body Gives Four- Hibernates Class

Temperature Birth legged Label
human warm-blooded yes no no yes
pigeon warm-blooded no no no no
elephant warm-blooded yes yes no yes
leopard shark cold-blooded yes no no no
turtle cold-blooded no yes no no
penguin cold-blooded no no no no
eel cold-blooded no no no no
dolphin warm-blooded yes no no yes
spiny anteater warm-blooded no yes yes yes
gila monster cold-blooded no yes yes no
 the test set is 30%. Both humans and dolphins were misclassified as non- mammals
because their attribute values for Body Temperature, Gives Birth, and Four-legged are
identical to the mislabeled records in the training set. Spiny anteaters, on the other hand,
represent an exceptional case in which the class label of a test record contradicts the class
labels of other similar records in the training set. Errors due to exceptional cases are often
unavoidable and establish the minimum error rate achievable by any classifier.
In contrast, the decision tree M 2 shown in Figure 4.25(b) has a lower test error rate (10%)
even though its training error rate is somewhat higher (20%). It is evident that the first
decision tree, M 1, has overfitted the training data because there is a simpler model with
lower error rate on the test set. The Four-legged attribute test condition in model M 1 is
spurious because it fits the mislabeled training records, which leads to the
misclassification of records in the test set.
4.1.1 Overfitting Due to Lack of Representative Samples
Models that make their classification decisions based on a small number of training
records are also susceptible to overfitting. Such models can be gener- ated because of lack
of representative samples in the training data and learning algorithms that continue to refine
their models even when few training records are available. We illustrate these effects in
the example below.
Consider the five training records shown in Table 4.5. All of these training records are
labeled correctly and the corresponding decision tree is depicted in Figure 4.26. Although
its training error is zero, its error rate on the test set is 30%.

3. Bayesian Classification:
➢ Bayesian classifiers are statistical classifiers.
➢ They can predict class membership probabilities, such as the probability
that a given tuple belongs to a particular class.
➢ Bayesian classification is based on Bayes’ theorem.
Bayes’ Theorem:
➢ Let X be a data tuple. In Bayesian terms, X is considered ― “evidence”
and it is described by measurements made on a set of n attributes.
➢ Let H be some hypothesis, such as that the data tuple X belongs to a
specified class C.
➢ For classification problems, we want to determine P(H|X), the probability
that the hypothesis H holds given the ―evidence‖ or observed data tuple X.
➢ P(H|X) is the posterior probability, or a posteriori probability, of H
conditioned on X.
➢ Bayes’ theorem is useful in that it provides a way of calculating the
posterior probability, P(H|X), from P(H), P(X|H), and P(X).

Naïve Bayesian Classification:

The naïve Bayesian classifier, or simple Bayesian classifier, works as follows:
1. Let=be a training set of tuples and their associated class labels. As usual,
each tuple is represented by an n-dimensional attribute vector, X = (x1, x2, …,xn),
depicting n measurements made on the tuple from n attributes, respectively, A1, A2,
…, An.
2. Suppose that there are m classes, C1, C2, …, Cm. Given a tuple, X, the
classifier will predict that X belongs to the class having the highest posterior
probability, conditioned on X. That is, the naïve Bayesian classifier predicts that tuple
X belongs to the class Ci if and only if

Thus we maximize(𝐶𝑗 |𝑋). The class Ci for which (𝐶𝑗 |𝑋). is maximized is called
the maximum posteriori hypothesis. By Bayes’ theorem

3. As P(X) is constant for all classes, only P(X|Ci)P(Ci) need be maximized.

If the class prior probabilities are not known, then it is commonly assumed that the
classes are equally likely, that is, P(C1) = P(C2) = …= P(Cm), and we would therefore
maximize P(X|Ci). Otherwise, we maximize P(X|Ci)P(Ci).
4. Given data sets with many attributes, it would be extremely computationally
expensive to compute P(X|Ci). In order to reduce computation in evaluating P(X|Ci),
the naive assumption of class conditional independence is made. This presumes that
the values of the attributes are conditionally independent of one another, given the
class label of the tuple. Thus,

5. We can easily estimate the probabilities P(x1|Ci), P(x2|Ci), : : : , P(xn|Ci) from

the training tuples.
6. For each attribute, we look at whether the attribute is categorical or
continuous- valued. For instance, to compute P(X|Ci), we consider the following:
➢ If Ak is categorical, then P(xk|Ci) is the number of tuples of class Ci
in=having the value xk for Ak, divided by |Ci ,D| the number of tuples of class Ci in D.
➢ If Ak is continuous-valued, then we need to do a bit more work, but the
calculation is pretty straightforward.
Example:
age income student credit_rating buys_computer

youth high no Fair No

youth high no Excellent No
middle_aged high no Fair Yes
senior medium no Fair Yes
senior low yes Fair Yes
senior low yes Excellent No
middle_aged 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_aged medium no Excellent Yes
middle_aged high yes Fair Yes
 senior medium no Excellent No

We wish to predict the class label of a tuple using naïve Bayesian classification, given
the same training data above. The training data were shown above in Table. The data
tuples are described by the attributes age, income, student, and credit rating. The
class label attribute, buys computer, has two distinct values (namely, {yes, no}). Let
C1 correspond to the class buys computer=yes and C2 correspond to buys
computer=no. The tuple we wish to classify is
X={age= “youth”, income= “medium”, student= “yes”, credit_rating= “fair”}

We need to maximize P(X|Ci)P(Ci), for i=1,2. P(Ci), the prior probability of each class,
can be computed based on the training tuples:

P(buys computer = yes) = 9/14 = 0.643

P(buys computer = no) = 5/14 = 0.357

To compute P(X|Ci), for i = 1, 2, we compute the following conditional probabilities:

P(age = youth | buys computer = yes) = 2/9 = 0.222

P(income=medium | buys computer=yes) = 4/9 = 0.444
P(student=yes | buys computer=yes) = 6/9 = 0.667
P(credit rating=fair | buys computer=yes) = 6/9 = 0.667

P(age=youth | buys computer=no) = 3/5 = 0.600

P(income=medium | buys computer=no) = 2/5 = 0.400
P(student=yes | buys computer=no) = 1/5 = 0.200
P(credit rating=fair | buys computer=no) = 2/5 = 0.400

Using these probabilities, we obtain

P(X | buys computer=yes) = P(age=youth | buys computer=yes)
× P(income=medium | buys computer=yes)
× P(student=yes | buys computer=yes)
× P(credit rating=fair | buys computer=yes)
= 0.222 × 0.444 × 0.667 × 0.667 = 0.044.
Similarly,
P(X | buys computer=no) = 0.600 × 0.400 × 0.200 × 0.400 = 0.019.
To find the class, Ci, that P(X|Ci)P(Ci), we compute
P(X | buys computer=yes) P(buys computer=yes) = 0.044 × 0.643 = 0.028
P(X | buys computer=no) P(buys computer=no) = 0.019 × 0.357 = 0.007
Therefore, the naïve Bayesian classifier predicts buys computer = yes for tuple X.
4. Rule-Based Classification
Using IF-THEN Rules for Classification
Rules are a good way of representing information or bits of knowledge. A rule-based
classifier uses a set of IF-THEN rules for classification. An IF-THEN rule is an
expression of the form
IF condition THEN conclusion.
An example is rule R1,
R1: IF age = youth AND student = yes THEN buys computer = yes.
• The “IF” part (or left side) of a rule is known as the rule antecedent or
precondition.
• The “THEN” part (or right side) is the rule consequent.
R1 can also be written as
R1: (age = youth) ^ (student = yes)=>(buys_computer = yes).
A rule R can be assessed by its coverage and accuracy. Given a tuple, X, from a class
labelled data set, D, let ncovers be the number of tuples covered by R; ncorrects be the
number of tuples correctly classified by R; and |D| be the number of tuples in D. We
can define the coverage and accuracy of R as

Rule Extraction from a Decision Tree

To extract rules from a decision tree, one rule is created for each path from the root
to a leaf node. Each splitting criterion along a given path is logically ANDed to form
the rule antecedent (“IF” part). The leaf node holds the class prediction, forming the
rule consequent (“THEN” part).
Example:

Rule Induction Using a Sequential Covering Algorithm

IF-THEN rules can be extracted directly from the training data (i.e., without having to
generate a decision tree first) using a sequential covering algorithm.