Module 4

This is a single, concatenated file, suitable for printing or saving as a PDF for offline viewing. Please
note that some animations or images may not work.

Module 4
April 1 - April 7

Topics: Lecture 7: Prediction and Classification Methods — The Naïve Bayes Classifier
Lecture 8: Prediction and Classification Methods — Classification and Regression
Trees

Readings: Lecture 17
Lecture Notes
Shmueli et al., Chapter 8

Lecture 8:
Lecture Notes
Shmueli et al., Chapter 9

Tutorials: Lecture 7:
Naïve Bayes Calculation (Spam vs. Ham)

Lecture 8:
Classification and Regression Trees

Discussions: Discussion 4

Initial post due Thursday, April 3 at 11:59 PM ET

Respond to at least two of your classmates' posts by Monday, April 7 at
11:59 PM ET

Assignments: Assignment 2 due Monday, April 7 at 11:59 PM ET

Assessments: Quiz 2, available from Saturday, April 5 at 9:00 AM ET to Monday, April 7 at 11:59
PM ET

Live Classroom: Module 4 Live Classroom Session: Monday, April 7 at 8:00pm ET

Lecture 7: Prediction and Classification Methods - The Naïve Bayes

 Classifier

Learning Objectives

After successfully completing the lesson, students will be able to:

1. Explain why naïve Bayes is used for classification.

2. Compare the difference between full (exact) conditional probability and naïve Bayes probability.
3. Identify real-world applications of naïve Bayes.
4. Identify the general pros and cons of using naïve Bayes for classification tasks.

Naïve Bayes: Overview

A British statistician from the 18th century, Thomas Bayes is best known for formulating a theory about conditional
probability. The exact derivation and use of this theory is outside the scope of AD699, but it is important for data
mining students to be able to perform conditional probability calculations, as the concept comes up in several
types of data mining operations. For a set of four practice problems, please view the Conditional Probability
Warm-Up video in the AD699 Video Library.

To perform a full conditional probability calculation, one must have all the available data. In other words, if we
were given data about a sample of people (including the total number in the sample), the number who take the
train to class, the number who use Uber, the number who use neither, and the overlap set (sometimes Uber,
sometimes train), we could perform any related conditional calculation — we could find, for example, the
probability that an Uber rider also takes the train, that a train rider also uses Uber, that a random person in the
sample does both, etc.

There are, however some real-world situations in which we want to be able to estimate the probability of
something belonging to a particular category (spam vs. ham, default vs. good credit risk, on-time vs. delayed
flight, etc.) and don’t have prior data involving the exact set of circumstances that we want to predict. In these
instances, we can use a naïve Bayes calculation to estimate probability.

A Naïve Bayes Calculation

To perform a naïve Bayes calculation, we first need to start with something called the prior (this is also sometimes
known as the posterior). We find the prior by looking at the training data set, and finding the proportion of records
that belong to a particular group. Then, we multiply that by the probability that each predictor would appear in a
particular group. For instance, let’s say we have an email message that simply says “International prince lottery
Viagra” and we need to determine whether it’s spam (junk) or ham (not junk). The following probabilities are
fictional — they are used only to illustrate how to perform the calculation:

From our training data, we know that 60% of all emails are spam and that 40% are ham.

From our training data, we also know the probabilities that the following words would appear in either type of
email:

SPAM HAM

International 0.10 0.020

prince 0.12 0.010

lottery 0.16 0.015

Viagra 0.09 0.001

To answer the “Is it spam” question we need to first find what I’ll call the “spam score.” That will be the prior (.60)
times the probability that each of the predictors would appear in a spam message. We then need to find the “ham
score” by taking that prior, and multiplying it by the ham probabilities.

(0.60)(0.10)(0.12)0(.16)(0.09) = 0.00010368.
(0.40)(0.02)0(.01)(0.015)(0.001) = 0.0000000012.

If we were simply trying to answer the question of which outcome is more likely, we could stop here and say that
this email is more likely to be spam, since its score is higher.

However, if we wish to know the Bayesian probability outcomes, we need to divide each of the scores by the sum
of the two scores:

Naïve Bayes spam probability: 0.00010368 / (0.00010368 + 0.0000000012) = 0.999988426.

Naïve Bayes ham probability: 0.0000000012 / (0.00010368 + 0.0000000012) = 0.0000115739.

Clearly, this email is a great candidate for a spam folder!

Probability calculations done this way (as opposed to the full, or “exact” conditional method) may not be as
accurate, but for the purposes of classification, that doesn’t necessarily matter. Think of it this way — when we
use this process to classify, we can measure our success by the percentage of times we make the correct
classification. Whether the above email is really 99%+ likely to be spam, or perhaps merely 97% likely, is
irrelevant, assuming we’re using a cutoff threshold that properly identifies this message.

Practical Uses of Naïve Bayes

The most famous real-world use case for naïve Bayes is spam filtration. It can actually be used with any
classification task for which there are categorical predictors. In theory, naïve Bayes could also work with
numerical predictors, but they would first have to be converted to factors and then binned into particular groups.
For more info about that process, please see the video in the AD699 Video Library Preparing numerical
predictors for use in a naïve Bayes model.

Naïve Bayes Pros and Cons

Naïve Bayes is remarkably efficient. It actually gets the “naïve” part of its name from the fact that it assumes
independence among all the predictor variables — that is to say, it treats the words “international”, “lottery”,
“prince” and “Viagra” as completely separate entities, with no separate weight given to the fact that they are all
lumped together in a single message. While that may seem intuitively to be a bad practice, it actually works quite
well — its accuracy rate stays relatively high without adding the tremendous additional computational burden that
would have to come with the treatment of predictors in some other, non-independent way.

To work effectively, naïve Bayes does require a large set of training data. To think about that in a real-world
context, look at the spam vs. ham example. 10 emails, or 100 emails, or even 1,000 emails, would not be enough
to effectively train a model to make that type of classification. The bigger the corpus of material given to the
training set, the more accurately naïve Bayes will work.

One potential issue with naïve Bayes is the way it handles predictors that are unknown to the training set. For
instance, let’s say the training set contained 100,000 emails, but not a single one included the word “fortnight.” If
a naïve Bayesian algorithm were to then assign a value of “0” to that word, it would become unable to properly
classify an email containing that word at all. In some naïve Bayesian algorithms, unknown words are thrown out
completely (which heightens the risk of overfitting to the training data), and in other cases, a smoothing constant
is used to ensure that non-zero values are emplaced in the calculations when the model encounters an unknown
predictor.

Lecture 8: Prediction and Classification Methods - Classification and

Regression Trees

Learning Objectives

After successfully completing the lesson, students will be able to:

1. Interpret the visual results of a tree and understand the way it can help with classification or regression.
2. Explain the conceptual goal of the algorithm that builds trees, and why homogeneity matters at the points
where the tree splits.
3. Explain why pruning is an important step in the process of avoiding overfitting.
4. Interpret the results of a regression tree.
5. Identify the pros and cons of using trees for data modeling.
Classification and Regression Trees: Overview

Trees, which can be used for either classification or prediction, are the most transparent and easiest to interpret
among the data-driven methods that we will study in AD699.

Conceptually, trees are built by splitting portions of a data set into homogeneous (or nearly homogeneous)
groups at points where the data naturally splits into such groups (i.e. income > 60, property size < 2 acres, etc.).

Tree models require large amounts of data at the outset, but are computationally cheap to deploy, even on large
samples. Trees are also robust to outliers and can easily handle missing values.

Classification Trees

One of the major concepts that drives the process of classification tree creation is called recursive partitioning.
Recursive partitioning is all about repeatedly dividing a data set into smaller and smaller non-overlapping
multidimensional records. To see a narrated code demo of this process, please view the code narrations for
Figures 9.7 and 9.8 in the textbook, which can be found in the AD699 Video Library.

A tree contains two types of nodes — decision nodes and terminal nodes. At a decision node, the data is split.
At a terminal node (also called a leaf), a record cannot be dropped any further — at this point, the algorithm is
making a prediction about which class a particular record belongs to.

Evaluating Classification Trees

The algorithm that decides where the splits in the tree should occur will do its best to create homogeneity among
the groups created by the splits. Two of the methods used to determine the level of homogeneity are the Gini
Index and entropy. The exact calculation of these values is outside the scope of AD699, but you should know that
a higher Gini index is associated with more heterogeneity (impurity), whereas a lower Gini index indicates greater
homogeneity.

Pruning to Avoid Overfitting

Overfitting is an important risk to consider when looking at tree-based models. Especially when a tree has many
nodes, the last few splits can sometimes be dividing a very tiny number of records, relative to the overall size of
the training data set. The problem with this is that those last few splits can be very subject to the idiosyncrasies of
the training set, and this won’t be useful for evaluating new data.
The pruning process involves determining the appropriate complexity parameter (CP). The CP helps to inform
the depth level of the tree. For an in-depth coded narration of the process of tabulating tree error as a function of
the complexity parameter, see the Table 9.4 code narration in the AD699 video library.

The big-picture idea behind pruning is to recognize that a very large tree is likely to overfit the training data, and
that the weakest branches, which hardly reduce the error rate, should be removed. Looking at an unpruned tree,
you can see that the very last few splits only change the classification of a small number of items.

A tree’s cost complexity is equal to its misclassification error, plus a penalty for the size of the tree.

Classification trees can be used with an outcome variable that has more than two classes. In such cases, the tree
itself would have the same structure, but its terminal nodes would take one of the m-class labels.

Regression Trees

The tree method can also be used for regression. The process is in many ways the same, but with the value
displayed in a terminal node representing the average outcome value of the training records in that particular
node.

The predictive power of regression trees can be measured in the same way that other predictive measures are
evaluated (e.g. linear regression), using summary measures such as RMSE.

Tree Pros and Cons

Our textbook notes that “tree methods are good off-the-shelf classifiers and predictors.” A major part of their
appeal is that they’re visually intuitive and relatively easy to understand. (In other words, you can show them to
your boss, who knows nothing about data mining!)

Trees are particular good at handling outliers and missing values. Since the key with trees is that they split at
particular points, large values on either side (or missing ones) won’t impact those splits.

One considerable weakness with trees is that they can’t be used to identify relationships among predictors. Since
trees split on one predictor at a time, they won’t be able to identify the interactions among multiple predictors that
can impact a classification.