Classification: Basic Concepts

• Classification is a form of data analysis that extracts models describing important

data classes.
• Such models, called classifiers, predict categorical (discrete, unordered) class labels.
• For example, we can build a classification model to categorize bank loan
applications as either safe or risky.
• Such analysis can help provide us with a better understanding of the data at large.
• Many classification methods have been proposed by researchers in machine
learning, pattern recognition, and statistics.
 6.1 Basic Concepts

• In the first step, we build a classification model based on previous data.

• In the second step, we determine if the model’s accuracy is acceptable, and if so, we use the
model to classify new data.
• 6.1.1 What Is Classification?
• A bank loans officer needs analysis of her data to learn which loan applicants are “safe” and
which are “risky” for the bank.
• A marketing manager at AllElectronics needs data analysis to help guess whether a
customer with a given profile will buy a new computer. A medical researcher wants to
analyze breast cancer data to predict which one of three specific treatments a patient
should receive.
 6.1 Basic Concepts

• In each of these examples, the data analysis task is classification, where a model or
classifier is constructed to predict class (categorical) labels, such as “safe” or “risky” for
the loan application data; “yes” or “no” for the marketing data; or “treatment A,”
“treatment B,” or “treatment C” for the medical data.
• These categories can be represented by discrete values, where the ordering among
values has no meaning.
• For example, the values 1, 2, and 3 may be used to represent treatments A, B, and C,
where there is no ordering implied among this group of treatment regimes.
 6.1 Basic Concepts

• Suppose that the marketing manager wants to predict how much a given customer will
spend during a sale at AllElectronics.
• This data analysis task is an example of numeric prediction, where the model constructed
predicts a continuous-valued function, or ordered value, as opposed to a class label.
• This model is a predictor.
• Regression analysis is a statistical methodology that is most often used for numeric
prediction; hence the two terms tend to be used synonymously, although other methods
for numeric prediction exist. Classification and numeric prediction are the two major types
of prediction problems.
 6.1 Basic Concepts

• Ranking is another type of numerical prediction where the model predicts the
ordered values (i.e., ranks), for example, a web search engine (e.g., Google) ranks
the relevant webpages with respect to a given query, with the higher-ranked
webpages being more relevant to the query.
• Classification and numeric prediction are the two major types of prediction
problems.
• It is worth pointing out that classification and numerical prediction (e.g.,
regression) are closely related to each other.
6.1.2 General Approach to Classification
6.1.2 General Approach to Classification
Supervised vs. Unsupervised Learning
 6.1.2 General Approach to Classification

• “How does classification work?”

• Data classification is a two-step process, consisting of a learning step (where a
classification model is constructed) and a classification step (where the model is
used to predict class labels for given data).
• The process is shown for the loan application data of Figure 6.1.
• (The data are simplified for illustrative purposes.
• In reality, we may expect many more attributes to be considered.
6.1.2 General Approach to Classification
 6.1.2 General Approach to Classification

• In the first step, a classifier is built describing a predetermined set of data

classes or concepts.
• This is the learning step (or training phase), where a classification algorithm
builds the classifier by analyzing or “learning from” a training set made up of
database tuples and their associated class labels.
• A tuple, X, is represented by an n-dimensional attribute vector, X = (x1, x2,..., xn),
depicting n measurements made on the tuple from n database attributes,
respectively, A1, A2,..., An.
 6.1.2 General Approach to Classification

• Each tuple, X, is assumed to belong to a predefined class as determined by another

database attribute called the class label attribute.
• The class label attribute is discrete-valued and unordered. {hair_color, smoker,
medical_test, and drink_size}
• It is categorical (or nominal) in that each value serves as a category or class.
• The individual tuples making up the training set are referred to as training tuples and
are randomly sampled from the database under analysis.
• In the context of classification, data tuples can be referred to as samples, examples,
instances, data points, or objects.
 6.1.2 General Approach to Classification

• Because the class label of each training tuple is provided, this step is also known as
supervised learning (i.e., the learning of the classifier is “supervised” in that it is told
to which class each training tuple belongs).
• It contrasts with unsupervised learning (or clustering), in which the class label of
each training tuple is not known, and the number or set of classes to be learned may
not be known in advance.
• For example, if we did not have the loan decision data available for the training set,
we could use clustering to try to determine “groups of like tuples,” which may
correspond to risk groups within the loan application data.
 6.1.2 General Approach to Classification

• Likewise, we could use clustering techniques to find social media posts sharing similar topics without
knowing their actual class labels.
• The landscape of the prediction problem (e.g., classification, regression, ranking) has gone beyond
supervised vs. unsupervised learning.
• To name a few, in semisupervised classification, it builds a classifier based on a limited number of
labeled training tuples (whose true class labels are given during training) and a large number of
unlabeled training tuples (whose class labels are unknown during training); in zero-shot learning, some
class label might appear after the classification model has been built.
• In other words, during the training phase, there are no (i.e., zero) labeled training tuples for such a class
label.
 6.1.2 General Approach to Classification

• Both semi supervised learning and zero-shot learning belong to weakly supervised learning in that the
supervision information for training the model is weaker than the standard supervised learning.
• For the classification task, this means that the supervision (i.e., the true class labels of training tuples) is
known only for a small fraction of the entire training set in semisupervised learning; or is absent for
certain class label(s) in zero-shot learning.
 6.1.2 General Approach to Classification

• “What about classification accuracy?”

• First, the predictive accuracy of the classifier is estimated.
• If we were to use the training set to measure the classifier’s accuracy, this estimate would likely be too
optimistic, because the classifier tends to overfit the data (i.e., during learning it may incorporate some
particular anomalies of the training data that do not represent the general data set).
• Therefore a test set is used, made up of test tuples and their associated class labels.
• They are independent of the training tuples, meaning that they were not used to construct the
classifier.
 6.1.2 General Approach to Classification

• The accuracy of a classifier on a given test set is the percentage of test tuples that are correctly
classified by the classifier.
• The associated class label of each test tuple is compared with the learned classifier’s class prediction
for that tuple.
• If the accuracy of the classifier is considered acceptable, the classifier can be used to classify future
data tuples for which the class label is not known.
• Such data are also referred to in the machine learning literature as “unknown” or “previously unseen”
data.
• For example, the classification rules learned in Fig. 6.1(a) from the analysis of data from previous loan
applications can be used to approve or reject new or future loan applicants.
6.1.2 General Approach to Classification
 6.2 Decision Tree Induction

• Decision tree induction is the learning of decision trees from class-labeled training
tuples.
• A decision tree is a flowchart-like tree structure, where each internal node (nonleaf
node) denotes a test on an attribute, each branch represents an outcome of the test, and
each leaf node (or terminal node) holds a class label.
• The topmost node in a tree is the root node. Figure 6.2

• A typical decision tree is shown in Figure 6.2. It

represents the concept buys computer, that is, it
predicts whether a customer at AllElectronics is likely
to purchase a computer. Internal nodes are denoted by
rectangles, and leaf nodes are denoted by ovals.
 6.2 Decision Tree Induction

• Some decision tree algorithms produce only binary trees (where each internal
node branches to exactly two other nodes), whereas others can produce
nonbinary trees.
• “How are decision trees used for classification?”
• Given a tuple, X, for which the associated class label is unknown, the attribute
values of the tuple are tested against the decision tree.
• A path is traced from the root to a leaf node, which holds the class prediction for
that tuple.
• Decision trees can easily be converted to classification rules.
 6.2 Decision Tree Induction

“Why are decision tree classifiers so popular?”

• The construction of decision tree classifiers does not require any domain knowledge or
parameter setting, and therefore is appropriate for exploratory knowledge discovery.
• Decision trees can handle multidimensional data.
• Their representation of acquired knowledge in tree form is intuitive and generally easy
to assimilate by humans.
• The learning and classification steps of decision tree induction are simple and fast.
• In general, decision tree classifiers have good accuracy.
• However, successful use may depend on the data at hand.
 6.2 Decision Tree Induction

• Decision tree induction algorithms have been used for classification in many application
areas such as medicine, manufacturing and production, financial analysis, astronomy,
and molecular biology.
• Decision trees are the basis of several commercial rule induction systems.
 6.2.1 Decision Tree Induction

• During the late 1970s and early 1980s, J. Ross Quinlan, a researcher in machine learning, developed a
decision tree algorithm known as ID3 (Iterative Dichotomiser).
• This work expanded on earlier work on concept learning systems, described by E. B. Hunt, J. Marin, and P.
T. Stone.
• Quinlan later presented C4.5 (a successor of ID3), which became a benchmark to which newer supervised
learning algorithms are often compared.
• 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.
• ID3 and CART were invented independently of one another at around the same time, yet follow a similar
approach for learning decision trees from training tuples.
• These two cornerstone algorithms spawned a flurry of work on decision tree induction.
 6.2.1 Decision Tree Induction

• The strategy is as follows.

• The algorithm is called with three parameters:
• D, attribute list, and Attribute selection method.
• We refer to D as a data partition.
• Initially, it is the complete set of training tuples and their associated class labels.
• The parameter attribute list is a list of attributes describing the tuples.
• Attribute selection method specifies a heuristic procedure for selecting the attribute that
“best” discriminates the given tuples according to class.
 6.2.1 Decision Tree Induction

• This procedure employs an attribute selection measure such as information

gain or the Gini index.
• Whether the tree is strictly binary is generally driven by the attribute selection
measure.
• Some attribute selection measures, such as the Gini index, enforce the resulting
tree to be binary.
• Others, like information gain, do not, therein allowing multiway splits (i.e., two
or more branches to be grown from a node).
6.2.1 Decision Tree Induction
8.2.1 Decision Tree Induction
 6.2.1 Decision Tree Induction

The tree starts as a single node, N, representing the

training tuples in D (step 1).

If the tuples in D are all of the same class, then node N becomes a leaf and
is labeled with that class (steps 2 and 3). Note that steps 4 and 5 are
terminating conditions.
 6.2.1 Decision Tree Induction

• 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 (step 6).
• 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.
 6.2.1 Decision Tree Induction

The node N is labeled with the splitting criterion, which serves as a test at the node (step 7). A branch is grown
from node N for each of the outcomes of the splitting criterion. The tuples in D are partitioned accordingly (steps
10 to 11).
8.2.1 Decision Tree Induction
 6.2.1 Decision Tree Induction

• There are three possible scenarios, as illustrated in Figure 6.4.

• Let A be the splitting attribute.
• A has v distinct values, {a1, a2,..., av }, based on the training data.

1. A is discrete-valued: In this case, the

outcomes of the test at node N
correspond directly to the known values
of A.
A branch is created for each known
value, aj , of A and labeled with that
A need not be considered in any future partitioning of the
value (Figure 8.4a). Partition Dj is the tuples. Therefore, it is removed from attribute list (steps 8 and
9)
subset of class-labeled tuples in D having
value aj of A.
 6.2.1 Decision Tree Induction

• 2. A is continuous-valued: In this case, the test

at node N has two possible outcomes,
corresponding to the conditions A ≤ split_point
and A > split_point, respectively, where
split_point is the splitpoint returned by
Attribute_selection_method as part of the
splitting criterion.
• (In practice, the split-point, a, is often taken as
the midpoint of two known adjacent values of A
and therefore may not actually be a preexisting
value of A from the training data.)
• Two branches are grown from N and labeled
according to the previous outcomes (Fig. 6.4(b)).
• The tuples are partitioned such that D1 holds
the subset of class-labeled tuples in D for which
A ≤ split_point, while D2 holds the rest.
 6.2.1 Decision Tree Induction

• 3. A is discrete-valued and a binary tree must be

produced (as dictated by the attribute selection
measure or algorithm being used):
• The test at node N is of the form “A ∈ SA?,” where SA
is the splitting subset for A, returned by
Attribute_selection_method as part of the splitting
criterion.
• It is a subset of the known values of A. If a given tuple
has value aj of A, and if aj ∈ SA, then the test at node N
is satisfied.
• Two branches are grown from N (Fig. 6.4(c)).
• By convention, the left branch out of N is labeled yes
so that D1 corresponds to the subset of class-labeled
tuples in D that satisfy the test.
• The right branch out of N is labeled no so that D2
corresponds to the subset of class-labeled tuples from
D that do not satisfy the test
6.2.1 Decision Tree Induction
6.2.1 Decision Tree Induction

FIGURE 6.4 This figure shows three

possibilities for partitioning tuples
based on the splitting criterion, each
with examples. 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.
 6.2.1 Decision Tree Induction

• The algorithm uses the same process recursively to form a decision tree for the tuples at each resulting
partition, Dj , of D (step 14).
• 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 (steps 2 and 3).
2. There are no remaining attributes on which the tuples may be further partitioned (step 4).
In this case, majority voting is employed (step 5). 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 (step 12).
In this case, a leaf is created with the majority class in D (step 13).
• The resulting decision tree is returned (step 15).
 6.2.1 Decision Tree Induction

• The computational complexity of the algorithm given training set D is O(n × |D| × log(|D|)), where n is the
number of attributes describing the tuples in D and |D| is the number of training tuples in D.
• This means that the computational cost of growing a tree grows at most n × |D| × log(|D|) with |D| tuples.
• Incremental versions of decision tree induction have also been proposed.
• When given new training data, it restructures the decision tree acquired from learning on previous training
data rather than relearning a new tree from scratch.
• Differences in decision tree algorithms include how the attributes are selected in creating the tree and the
mechanisms used for pruning .
 6.2.1 Decision Tree Induction

• Decision tree is closely related to another type of tree, called regression tree, which is used to predict the
continuous output value.
• A regression tree is very similar to a decision tree in that it also partitions the entire attribute space into multiple
subregions, each corresponding to a leaf node.
• The main difference is as follows.
• In a regression tree, a leaf node holds a continuous value instead of a categorical value (i.e., class label) in a
decision tree.
• The continuous value of a leaf node is learned during the training phase, which is set as the average output value
of all training tuples fallen in the corresponding subregions.
• CART uses residual sum of squares (RSS) as the objective function, which is the sum of the squared difference
between the actual and predicted output values of training tuples
 6.2.1 Decision Tree Induction

• where yi is the actual output value of the ith training tuple, and is the predicted output by the regression tree.
• Choosing the average output of all training tuples in the corresponding subregion is optimal in that it minimizes
the RSS in Eq. (6.1).
• Each leaf node value is then used to predict the output of a test tuple which falls into it.
• Fig. 6.5 presents an example of a regression tree for predicting the average yearly income based on an
individual’s education (e.g., whether or not the individual attended the college, the average GPA at college, etc.).

FIGURE 6.5
 6.2.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.
 Attribute selection measures

• The attribute selection measure provides a ranking for each attribute describing the given training tuples.
• The attribute having the best score for the measure 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.
• This section describes three popular attribute selection measures—
• The notation used herein is as follows.
• information gain, • Let D, the data partition, be a training set of class-labeled tuples.
• Suppose the class label attribute has m distinct values defining m distinct classes,
• gain ratio, and Ci (for i =1,...,m).
• Gini impurity. • Let Ci,D be the set of tuples of class Ci in D.
• Let |D| and |Ci,D| denote the number of tuples in D and Ci,D, respectively.
 Attribute selection measures

Information Gain
• Information gain ID3 uses information gain as its attribute selection measure.
• This measure is based on pioneering work by Claude Shannon on information theory, which studied the
value or “information content” of messages. Let node N represent or hold the tuples of partition D.
• 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.
• The expected information needed to classify a tuple in D is given by
 Attribute selection measures

• where pi is the nonzero probability that an arbitrary tuple in D belongs to class Ci and is
estimated by |Ci,D|/|D|.
• A log function to the base 2 is used, because the information is encoded in bits.
• Info(D) is just the average amount of information needed to identify the class label of a tuple in
D.
• Note that, at this point, the information we have is based solely on the proportions of tuples of
each class.
• Info(D) is also known as the entropy of D.
 Attribute selection measures

• Now, suppose we were 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.
• That is, we would like for each partition to be pure. However, it is quite likely that the partitions will be
impure (e.g., where a partition may contain a collection of tuples from different classes rather than
from a single class).
 Attribute selection measures

• How much more information would we still need (after the partitioning) to arrive at an exact
classification? This amount is measured by

• The term acts as the weight of the j th partition.

• InfoA(D) is the expected information required to classify a tuple from D based on the partitioning by A.
• The smaller the expected information (still) required, the greater the purity of the partitions.
• InfoA(D) is also known as the conditional entropy of D (conditioned on the attribute A).
• 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).
• That is,
 Attribute selection measures

• In other words, Gain(A) tells us how much would be gained by branching on A.

• It is the expected reduction in the information requirement caused by knowing the value of A.
• The attribute A with the highest information gain, Gain(A), is chosen as the splitting attribute at
node N.
• This is equivalent to saying that we want to partition on the attribute A that would do the “best
classification,” so that the amount of information still required to finish classifying the tuples is
minimal (i.e., minimum InfoA(D)).
 Attribute selection measures

• Example 6.1. Induction of a decision tree

using information gain.
• Table 6.1 presents a training set, D, of
class-labeled tuples randomly selected from
the customer database of an electronics store.
• In this example, each attribute is
discrete-valued.
• Continuous valued attributes have been
generalized.)
• The class label attribute, buys_computer, has
two distinct values (namely, {yes, no});
therefore, there are two distinct classes (i.e.,
m = 2).
• Let class C1 correspond to yes and class C2
correspond to no.
 Attribute selection measures

• 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.
• We first use Eq. (6.2) to compute the expected information needed to classify a tuple in D:

• Next, we need to compute the expected information requirement for each attribute.
• Let’s start with the attribute age.
• We need to look at the distribution of yes and no tuples for each category of age.
For the age category “youth” there are two yes tuples and three no tuples.
For the category “middle_aged,” there are four yes tuples and zero no tuples.
For the category “senior,” there are three yes tuples and two no tuples.
• Using Eq. (6.3), the expected information needed to classify a tuple in D if the tuples are partitioned
according to age is
 Attribute selection measures

• 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
Hence, the gain in information from such partitioning would be splitting attribute.
• Node N is labeled with age, and
branches are grown for each of
the attribute’s values.
 Attribute selection measures

• The tuples are then partitioned

accordingly, as shown in Fig. 6.6.
• 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.”
 Attribute selection measures

• “But how can we compute the information gain of an attribute that is continuous-valued, unlike in the
example?”
• Suppose, instead, that we have an attribute A that is continuous-valued rather than discrete-valued.
• (For example, suppose that instead of the discretized version of age from the example, we have the raw
values for this attribute.) For such a scenario, we must determine the “best” split-point for A, where the
split-point is a threshold on A.
• We first sort the values of A in the increasing order. Typically, the midpoint between each pair of
adjacent values is considered as a possible split-point. Therefore, given v values of A, (v − 1) possible
splits are evaluated. For example, the midpoint between the values ai and ai+1 of A is
 Attribute selection measures

• If the values of A are sorted in advance, then determining the best split for A requires only one
pass through the values. For each possible split-point for A,
• we evaluate InfoA(D), where the number of partitions is two, that is, v = 2 (or j = 1, 2) in Eq.
(6.3). The point with the minimum expected information requirement for A is selected as the
split_point for 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
 Attribute selection measures

Gain Ratio
• The information gain measure is biased toward tests with many outcomes.
• That is, 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) = 0. Therefore the information gained by partitioning on this attribute is
maximal. Clearly, such a partitioning is useless for classification.
 Attribute selection measures

Gain Ratio

• C4.5, a successor of ID3, 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
 Attribute selection measures

Gain Ratio
• 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.
• Note that, for each outcome, it considers the number of tuples having that outcome with
respect to the total number of tuples in D.
• The gain ratio is defined as

• The attribute with the maximum gain ratio is selected as the splitting attribute.
• Note, however, that as the split information approaches 0, the ratio becomes unstable.
 Attribute selection measures

Example 8.2 Computation of gain ratio for the attribute income.

• A test on income splits the data of Table 8.1 into three partitions, namely low,
medium, and high, containing four, six, and four tuples, respectively.
• To compute the gain ratio of income, we first use Eq. (8.5) to obtain

• From Example 6.1, we have Gain(income) = 0.029.

• Therefore, GainRatio(income) = 0.029/1.557 = 0.019.
 Attribute selection measures : Gini Impurity

• The Gini impurity is used in CART.

• Using the notation previously described, the Gini index measures the impurity
of D, a data partition or set of training tuples, as

• where pi is the probability that a tuple in D belongs to class Ci and is estimated

by
• The sum is computed over m classes.
 Gini Impurity

• The Gini impurity 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?”
• Given a tuple, this test is satisfied if the value of A for the tuple is among the values
listed in SA.
 Gini Impurity

• 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 {}.
 Gini Impurity

• 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.
• When considering a binary split, we compute a weighted sum of the impurity of
each resulting partition.
• For example, if a binary split on A partitions D into D 1 and D2, the Gini index of D
given that partitioning is
 Gini Impurity

• For each attribute, each of the possible binary splits is considered.

• For a discrete-valued attribute, the subset that gives the minimum Gini impurity 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.
• The point giving the minimum Gini impurity 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
 Gini Impurity

• 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.
 Gini Impurity

• Ex: Induction of a decision tree using the Gini impurity.

• Let D be the training data shown earlier in Table 6.1, 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 use for the Gini index to compute the impurity of D:
 Gini Impurity

• To find the splitting criterion for the tuples in D, we need to compute the Gini impurity for each
attribute.
• Let’s start with the attribute income and consider 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.
• The Gini impurity value computed
based on this partitioning is
 Gini Impurity

• Similarly, the Gini impurity values for splits on the remaining subsets are 0.458 (for the subsets {low,
high} and {medium}) and 0.450 (for the subsets {medium, high} and {low}).
• Therefore, the best binary split for attribute income is on {low, medium} (or {high}) because it
minimizes the Gini index.
• Evaluating age, we obtain {youth, senior} (or {middle_aged}) as the best split for age with a Gini
impurity of 0.375; the attributes student and credit_rating are both binary, with Gini impurity
values of 0.367 and 0.429, respectively.
• The attribute age and splitting subset {youth, senior} therefore give the minimum Gini impurity
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.
 Gini Impurity

• “So, what is the relationship between Gini impurity and information gain?”
• ” Intuitively, both measures aim to quantify to what extent the impurity will be reduced if we split the
current node based on the given attribute.
• Information gain, rooted in information theory, measures the impurity based on (the change of) the
average amount of information needed to identify the class label of a tuple.
• Gini impurity is related to mis-classification in the following way. Based on the class label distribution in
the current node, it tells how likely a randomly chosen tuple will be mis-classified if it is assigned to a
random class label.
• Gini impurity is always used for binary split, whereas information gain allows multiway split. In terms of
computation, Gini impurity is slightly more efficient than information gain, since the latter involves the
logarithm computation. In practice, however, both measures often lead to very similar decision trees.
 Other attribute selection measures

• We have shown three measures that are commonly used for building decision trees.
• These measures are not without their biases.
• Information gain, as we saw, is biased toward multivalued attributes.
• Although the gain ratio adjusts for this bias, it tends to prefer unbalanced splits in which one partition is
much smaller than the others.
• The Gini impurity is biased toward multivalued attributes and has difficulty when the number of classes
is large.
• It also tends to favor tests that result in equal-size partitions and purity in both partitions.
• Although biased, these measures give reasonably good results in practice.
 Other attribute selection measures

• Many other attribute selection measures have been proposed.

• CHAID, a decision tree algorithm that is popular in marketing, uses an attribute selection measure that is
based on the statistical χ2 test for independence.
• Other measures include C-SEP (which performs better than information gain and Gini impurity in certain
cases) and G-statistic (an information theoretic measure that is a close approximation to χ2 distribution).
• For regression tree, it is natural to use RSS (Eq. (6.1)) as the splitting criteria.
• That is, the best split point for a given attribute is the one that leads the smallest RSS.
• We choose the attribute with the minimum RSS to split the tree node into two nodes, including left leaf
node and right leaf node.
Eq. (6.1)
 Other attribute selection measures

Example 6.4.
• Let us look at an example in Table 6.2 on how to use RSS to find the best split point.
• Suppose there are five training tuples at a regression tree node, and each training tuple has a true
output value yi and a continuous attribute xi(i = 1,..., 5).
• We want to find the best split point for attribute xi to split the tree node into two leaf nodes.
• More specifically, all the tuples whose xi is less than or equal to the split point will go to the left leaf
node, and the remaining training tuples will go to the right leaf node.
 Other attribute selection measures

• Since xi is a continuous attribute with five possible values, there are four candidate split points, including x i = 1.5, xi
= 2.5, xi = 3.5 and xi = 4.5.
• For each candidate split point, we partition the current tree node into two leaf nodes.
• The average output value yl of the training tuples in the left leaf node is used to predict the output of all tuples
residing in the left leaf node.
• Likewise, the average output value yr of the training tuples in the right leaf node is used to predict the output of all
tuples residing in the right leaf node.
 Other attribute selection measures

• For example, if the split point xi = 1.5, only the first training tuple goes to the left leaf node, and we have that y l = y1
= 10; and yr = (y2 + y3 + y4 + y5)/4 = (12 + 8 + 20 + 22)/4 = 15.5.
• Using the predicted output values for all five training tuples (yl or yr), we can use Eq. (6.1) to calculate RSS. Again, if
the split point xi = 1.5, we have that RSS = 5 i=1(yi − ˆyi)2 = (y1 − yl)2 + (y2 − yr)2 + (y3 − yr)2 + (y4 − yr)2 + (y5 − yr)2 =
122.25.
• The computation results for all four possible split points are summarized in Table 6.3. Since xi = 3.5 has the smallest
RSS, it is chosen as the split point.
 Other attribute selection measures

• Attribute selection measures based on the Minimum Description Length (MDL) principle have the least bias
toward multivalued attributes.
• MDL-based measures use encoding techniques to define the “best” decision tree as the one that requires the
fewest number of bits to both
• encode the tree and
• encode the exceptions to the tree (i.e., cases that are not correctly classified by the tree). Its main idea is that the
simplest solution is preferred.
• The philosophy underlying the MLD principle is Occam’s razor, also known as law of parsimony.
• In data mining and machine learning, Occam’s razor is often translated into a design principle that one should
favor a model with a shorter description (hence minimum description length) for the data over a lengthier model,
provided that everything else is equal (e.g., both shorter and lengthier models share the same training set errors)
 Other attribute selection measures

• “Which attribute selection measure is the best?”

• All measures have some bias.
• 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 single attribute selection measure has been found to be significantly superior
to others. Most measures give quite good results.
• A shallow decision tree has fewer levels (low depth), meaning it does not split the data enough to separate
different classes properly. This can lead to more leaves and a higher error rate.
 6.2.3 Tree pruning

• 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.
• An unpruned tree and a pruned version of it are shown in Fig. 6.7.
• Pruned trees tend to be smaller and less complex and, thus, easier to
comprehend.
• They are usually faster and better at correctly classifying independent
test data (i.e., of previously unseen tuples) than unpruned trees.
 6.2.3 Tree pruning

• “How does tree pruning work?”

• There are two common approaches to tree pruning: prepruning and postpruning.
• In the prepruning approach, a tree is “pruned” by halting its 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 label among the subset tuples or the probability distribution of
the class labels of those tuples.
• When constructing a tree, measures such as statistical significance, information gain, Gini impurity, and
so on, can be used to assess the goodness of a split.
• If partitioning the tuples at a node would result in a split that falls below a prespecified threshold, then
further partitioning of the given subset is halted.
 6.2.3 Tree pruning

• There are difficulties, however, in choosing an appropriate threshold.

• High thresholds could result in oversimplified trees, whereas low thresholds could result in very little
simplification.
• The second and more common approach is postpruning, which removes subtrees from a “fully grown”
tree. A subtree at a given node is pruned by removing its branches and replacing it with a leaf.
• The leaf is labeled with the most frequent class label among the subtree being replaced. For example,
notice the subtree at node “A3?” in the unpruned tree of Fig. 6.7.
• Suppose that the most common class within this subtree is “class B.”
• In the pruned version of the tree, the subtree in question is pruned by replacing it with the leaf “class
B.”
6.2.3 Tree pruning
 6.2.3 Tree pruning

• The cost complexity pruning algorithm used in CART is an example of the postpruning
approach.
• This approach considers the cost complexity of a tree to be a function of the number of leaves in
the tree and the error rate of the tree (where the error rate is the percentage of tuples
misclassified by the tree). It starts from the bottom of the tree.
• For each internal node, N, it computes the cost complexity of the subtree at N, and the cost
complexity of the subtree at N if it were to be pruned (i.e., replaced by a leaf node). The two
values are compared.
• If pruning the subtree at node N would result in a smaller cost complexity, then the subtree is
pruned; otherwise, it is kept.
 6.2.3 Tree pruning

• A pruning set of class-labeled tuples is used to estimate the cost complexity.

• This set is independent
• (1) of the training set used to build the unpruned tree and
• (2) of any test set used for accuracy estimation. The algorithm generates a set of progressively
pruned trees.
• In general, the smallest decision tree that minimizes the cost complexity is preferred.
• C4.5 uses a method called pessimistic pruning, which is similar to the cost complexity method in that it
also uses error rate estimates to make decisions regarding subtree pruning.
• Pessimistic pruning, however, does not require the use of a pruning set.
• Instead, it uses the training set to estimate error rates.
• Recall that an estimate of accuracy or error based on the training set is overly optimistic and therefore
strongly biased.
• The pessimistic pruning method, therefore, adjusts the error rates obtained from the training set by
adding a penalty, so as to counter the bias incurred.
 6.2.3 Tree pruning

• Rather than pruning trees based on estimated error rates, we can prune trees based on the number
of bits required to encode them.
• The “best” pruned tree is the one that minimizes the number of encoding bits.
• This method adopts the MDL [Link] basic idea is that the simplest solution is preferred.
• Unlike cost complexity pruning, it does not require an independent set of tuples (i.e., the pruning
set).
• Alternatively, prepruning and postpruning may be interleaved for a combined approach.
• Postpruning requires more computation than prepruning, yet generally leads to a more reliable tree.
• No single pruning method has been found to be superior over all others.
• Although some pruning methods do depend on the availability of additional data for pruning, this is
usually not a concern when dealing with large databases.
 6.2.3 Tree pruning

• Although pruned trees tend to be more compact than their unpruned counterparts, they may still be rather large
and complex.
• Decision trees can suffer from repetition and replication (Fig. 6.8), making them overwhelming to interpret.
• Repetition occurs when an attribute is repeatedly tested along a given branch of the tree (e.g., “age < 60?,”
followed by “age < 45?,” and so on).
• In replication, duplicate subtrees exist within the tree.
• These situations can impede the accuracy and comprehensibility of a decision tree.
• The use of multivariate splits (splits based on a combination of attributes) can prevent these problems.
• Another approach is to use a different form of knowledge representation, such as rules, instead of decision trees.
which shows how a rule-based classifier can be constructed by extracting IF-THEN rules from a decision tree.
6.2.3 Tree pruning
 6.2.3 Tree pruning

Prepruning stops the tree from

growing too deep by halting its
construction before it fully expands.
•It prevents further splits if they do not
improve classification significantly.
•The node where splitting is halted
becomes a leaf.

Postpruning removes branches

(subtrees) from a fully grown decision
tree to prevent overfitting.
It simplifies the tree by replacing a
subtree with a single leaf node.
The new leaf is labeled with the most
frequent class from the pruned subtree.
 6.3 Bayes Classification Methods

• “What are Bayesian classifiers?” 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.
• Studies comparing classification algorithms have found a simple Bayesian classifier
known as the naive Bayesian classifier to be comparable in performance with decision
tree and selected neural network classifiers.
• Bayesian classifiers have also exhibited high accuracy and speed when applied to large
databases.
 6.3 Bayes Classification Methods

• Naive Bayesian classifiers assume that the effect of an attribute value on a given class is
independent of the values of the other attributes.
• This assumption is called class conditional independence.
• It is made to simplify the computations involved and, in this sense, is considered
“naive.”
 6.3.1 Bayes’ Theorem

• Bayes’ theorem is named after Thomas Bayes, a nonconformist English clergyman who
did early work in probability and decision theory during the 18th century.
• Let X be a data tuple.
• In Bayesian terms, X is considered “evidence.”
• 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.
• In other words, we are looking for the probability that tuple X belongs to class C, given
that we know the attribute description of X.
 6.3.1 Bayes’ Theorem

• P(H|X) is the posterior probability, or a posteriori probability, of H conditioned

on X.
• For example, suppose our world of data tuples is confined to customers
described by the attributes age and income, respectively, and that X is a
35-year-old customer with an income of $40,000.
• Suppose that H is the hypothesis that our customer will buy a computer.
• Then P(H|X) reflects the probability that customer X will buy a computer given
that we know the customer’s age and income.
 6.3.1 Bayes’ Theorem

• In contrast, P(H) is the prior probability, or a priori probability, of H.

• For our example, this is the probability that any given customer will buy a computer,
regardless of age, income, or any other information, for that matter.
• The posterior probability, P(H|X), is based on more information (e.g., customer
information) than the prior probability, P(H), which is independent of X.
• Similarly, P(X|H) is the conditional probability of X conditioned on H.
• That is, it is the probability that a customer, X, is 35 years old and earns $40,000,
given that we know the customer will buy a computer. In classification, P(X|H) is also
often referred to as likelihood.
 6.3.1 Bayes’ Theorem

• P(X) is the prior probability of X.

• Using our example, it is the probability that a person from our set of customers is 35
years old and earns $40,000. In classification, P(X) is also often referred to as marginal
probability.
• “How are these probabilities estimated?”
• P(H), P(X|H), and P(X) may be estimated from the given data.
• 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).
• Bayes’ theorem is
 6.3.1 Bayes’ Theorem

• “What does Bayes classifier look like?”

• Suppose that there are m classes, C1,C2,...,Cm.
• Given a tuple, X, we want to predict which class it belongs to.
• In Bayes classifier, it first calculates the posterior probabilities for each of the m classes, P(Ci|X) (i = 1,...,m),
and then predicts that tuple X belongs to the class with the highest posterior probability.
• In the above example, given a customer, X, of 35 years old and earning $40,000, we want to predict if the
customer will buy a computer.
• So, in this task, there are two possible classes (buy computer vs. not buy computer).
• Suppose P(buy computer|X) = 0.8 and P(not buy computer|X) = 0.2.
• Bayes classifier will predict that the customer X will buy a computer.
 6.3.1 Bayes’ Theorem

• “So, how good is Bayes classifier?”

• In theory, Bayes classifier is optimal in the sense that it has the smallest classification error rate compared to all other
classifiers.
• Since Bayes classifier is a probabilistic method, it could make a wrong prediction for any given tuple. In the above
example, Bayes classifier predicts the customer will buy a computer.
• Since P(not buy computer|X) = 0.2, there is 20% chance that the prediction the Bayes classifier makes is incorrect.
• However, since Bayes classifier always predicts the class with the maximum posterior probability, the probability that
its prediction is wrong for a given tuple X (which is often called risk) is the lowest in comparison to all other
classifiers.
• In our example, the risk for the given customer is 0.2. In other words, there is 20% probability that the prediction by
Bayes classifier is wrong.
 6.3.1 Bayes’ Theorem

• Therefore, the overall classification error of Bayes classifier, which is the expectation (i.e., the weighted
average) of the risk of all possible tuples, is the lowest in all possible classifiers.
• Given its theoretic optimality, Bayes classifier plays a foundational role in the statistical machine
learning community.
• For example, many classifiers (e.g., naïve Bayesian classifier, k-Nearest-Neighbor classifier, logistic
regression, Bayesian network, etc.) can be viewed as approximated Bayes classifiers.
• Bayes classifier is also useful in that it provides a theoretical justification for other classifiers that do
not explicitly use Bayes’ theorem.
• For example, under certain assumptions, it can be shown that many neural network and curve-fitting
algorithms output the maximum posteriori hypothesis, as does the Bayes classifier.
 6.3.1 Bayes’ Theorem

• “Then, why do not we just use Bayes classifier?”

• According to Bayes’ theorem (Eq. (6.11)), in order to calculate the posterior probabilities P(C i|X) (i = 1,...,m), we
need to know the conditional probabilities P(X|Ci) (i = 1,...,m), the priors P(Ci) (i = 1,...,m) and the marginal
probability P(X).
• In Bayes classifier, we only need to know which class has the highest posterior probability and for a given tuple X,
its marginal probability is independent of different classes.
• In other words, different posterior probabilities P(Ci|X) (i = 1,...,m) share the same marginal probability P(X).
• Therefore for the purpose of predicting which class a given tuple belongs to, we only need to estimate the
conditional probabilities P(X|Ci) (i = 1,...,m), and the priors P(Ci) (i = 1,...,m).
 6.3.1
Bayes’
Theore
It is relatively easy to estimate the priors P(Cm
i
) (i = 1,...,m) from the training data set.
On the other hand, it is usually very challenging to directly estimate the conditional probabilities
P(X|Ci) (i = 1,...,m).
To see this, let us assume there are n binary attributes A1,A2,...,An.
Then, the n-dimensional attribute vector X has 2n possible values and we need to estimate the
conditional probability of each possible value of the attribute vector with respect to each class
label.
In other words, the attribute value space is exponential!
It is very difficult to estimate such a large number of parameters for the conditional probabilities.
 6.3.1
Bayes’
Theore
Therefore the main difficulty for Bayes classifier lies
m in how to efficiently estimate the conditional
probabilities, often with some approximation. Many solutions have been developed. One of such efforts,
probably the simplest yet quite effective solution, is the naïve Bayesian classifier, which we introduce next.
6.3.1 Bayes’ Theorem
 6.3.2 Naïve Bayesian classification

The naïve Bayesian classifier, or simple Bayesian classifier, follows the same procedure as Bayes classifier,
except the way it estimates the conditional probabilities.
1. Let D be a training set of tuples and their associated class labels.
2. 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.
3. Suppose that there are m classes, C1,C2,...,Cm.
4. Given a tuple, X, the classifier will predict that X belongs to the class having the highest posterior
probability, conditioned on X.
5. That is, the naïve Bayesian classifier predicts that tuple X belongs to the class Ci if and only if
 6.3.2 Naïve Bayesian classification

• Thus we maximize P(Ci|X).

• The class Ci for which P(Ci|X) is maximized is called the maximum posteriori hypothesis.
• By Bayes’ theorem

• As P(X) is constant for all classes, we only need to find out which class maximizes P(X|Ci)P(Ci).
• 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).
• Note that the class prior probabilities may be estimated by P(Ci) = |Ci,D|/|D|, where |Ci,D| is the number of
training tuples of class Ci in D.
 6.3.2 Naïve Bayesian classification

• Given a data set with many attributes, it would be extremely computationally expensive to compute
P(X|Ci) for the aforementioned reasons.
• To reduce computation in evaluating P(X|Ci), the naïve assumption of class-conditional independence
is made.
• This presumes that the attributes’ values are conditionally independent of one another, given the class
label of the tuple (i.e., there are no dependence relationships among the attributes, if we know which
class the tuple belongs to.).
• Thus
 6.3.2 Naïve Bayesian classification

• We can easily estimate the probabilities P(x1|Ci),P(x2|Ci),...,P(xn|Ci) from the training tuples.
• Recall that here xk refers to the value of attribute Ak for tuple X.
• 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:

a. If Ak is categorical, then P(xk|Ci) is the number of tuples of class Ci in D having

the value xk for Ak, divided by |Ci,D|, the number of tuples of class Ci in D.
 6.3.2 Naïve Bayesian classification

b. If Ak is continuous-valued, then we need to do a bit more work, but the calculation is pretty
straightforward.
A continuous-valued attribute is typically assumed to have a Gaussian distribution with a mean μ and
standard deviation σ, defined by

so that

We need to compute μCi and σCi , which are the mean (i.e., average) and standard deviation, respectively, of
the values of attribute Ak for training tuples of class Ci. We then plug these two quantities into Eq. (6.14),
together with xk, to estimate P(xk|Ci).
6.3.2 Naïve Bayesian classification
 6.3.2 Naïve Bayesian classification

• To predict the class label of X, P(X|Ci)P(Ci) is evaluated for each class Ci.
• The classifier predicts that the class label of tuple X is the class Ci if and only if

In other words, the predicted class label is the class Ci for which P(X|Ci)P(Ci) is the maximum.
 6.3.2 Naïve Bayesian classification

• “How effective is naïve Bayesian classifier?”

• Notice that the only difference between naïve Bayesian classifier and Bayes classifier is the
class-conditional independence assumption.
• Therefore if such an assumption indeed holds, naïve Bayesian classifier would be optimal with the
smallest possible classification error.
• However, in practice this is not always the case, owing to inaccuracies in the assumptions made for its use,
such as class-conditional independence, and the lack of available probability data.
• Nonetheless, various empirical studies of this classifier in comparison to decision trees and selected
neural network classifiers have found it to be comparable in some domains.
• Another advantage of naïve Bayesian classifier is that it can naturally handle the missing attribute(s).
6.3.2 Naïve Bayesian classification
6.3.2 Naïve Bayesian classification
6.3.2 Naïve Bayesian classification
6.3.2 Naïve Bayesian classification
6.3.2 Naïve Bayesian classification
6.3.2 Naïve Bayesian classification
 6.3.2 Naïve Bayesian classification

• “What if I encounter probability values of zero?”

• There is a simple trick to avoid this problem.
• We can assume that our training database, D, is so large that adding one to each count that we
need would only make a negligible difference in the estimated probability value yet would
conveniently avoid the case of probability values of zero.
• This technique for probability estimation is known as the Laplacian correction or Laplace
estimator, named after Pierre Laplace, a French mathematician who lived from 1749 to 1827.
• If we have, say, q counts to which we each add one, then we must remember to add q to the
corresponding denominator used in the probability calculation.
 6.3.2 Naïve Bayesian classification

• Example 8.5
• Using the Laplacian correction to avoid computing probability values of zero.
• Suppose that for the class buys computer = yes in some training database, D, containing
1000 tuples, we have 0 tuples with income = low, 990 tuples with income = medium,
and 10 tuples with income = high.
• The probabilities of these events, without the Laplacian correction, are 0, 0.990 (from
990/1000), and 0.010 (from 10/1000), respectively.
 6.3.2 Naïve Bayesian classification

Using the Laplacian correction for the three quantities, we pretend that we have 1 more
tuple for each income-value pair. In this way, we instead obtain the following probabilities
(rounded up to three decimal places):

respectively.
The “corrected” probability estimates are close to their “uncorrected” counterparts, yet the
zero probability value is avoided.