Module 1

Introduction to Machine Learning

Syllabus

Introduction to Machine Learning Preface of Machine Learning, Types of

Learning : Supervised - Unsupervised Learning- Reinforcement- theory of
learning – feasibility of learning – error and noise – training versus testing –
theory of generalization – generalization bound –
approximation-generalization tradeoff – bias and variance – learning curve -
Finite and Infinite Hypothesis Spaces, Probably Approximately Correct (PAC)
Learning-Bayes theorem ,MDL principle.
SYLLABUS

Introduction to Machine Learning Preface of Machine Learning, - ppt

Types of Learning :
Supervised -
Unsupervised Learning- 1.2.4 page 35 - TB 1
Reinforcement- 1.2.5 page 37 - TB 1
theory of learning – feasibility of learning – error and noise – training versus testing – theory of
generalization – generalization bound – approximation-generalization tradeoff – bias and
variance – learning curve - Finite and Infinite Hypothesis Spaces,
Probably Approximately Correct (PAC) Learning- 2.3 page 53 - TB 1
Bayes theorem ,MDL principle.
Assessing the success of learning
Bias is a necessary evil associated with the abstraction and generalization
process inherent in any machine learning task.

The final step in the generalization process is to determine the model's

success in spite of its biases.

It's worth noting that it is exceedingly rare for a model to perfectly generalize
to every unforeseen case
In part, the failure for models to perfectly generalize is due to the problem of
noise, or unexplained variations in data. Noisy data is caused by seemingly
random events,
● Measurement error due to imprecise sensors
● Issues with reporting data - respondents reporting random answers to
survey questions in order to finish more quickly.
● Errors caused when data is recorded incorrectly, including missing, null,
truncated, incorrectly coded, or corrupted values

Trying to model the noise in data is the basis of a problem called overfitting
Steps to apply ML to your Data
Collecting data: Whether the data is written on paper, recorded in text files
and spreadsheets, or stored in an SQL database, you will need to gather it in
an electronic format suitable for analysis.
Exploring and preparing the data: The quality of any machine learning project
is based largely on the quality of data it uses. This step in the machine
learning process require a great deal of human intervention.
Training a model on the data: a. The specific machine learning task will inform
the selection of an appropriate algorithm, and the algorithm will represent the
data in the form of a model
Evaluating model performance:
Improving model performance:
Choosing a machine learning algorithm
Choosing a machine learning algorithm involves matching the characteristics
of the data to be learned to the biases of the available approaches

Choice of a machine learning algorithm is largely dependent upon

● the type of data you are analyzing and

● the proposed task at hand,
Input Data
All machine learning algorithms require input training data.

Input data takes the form of examples and features.

What is an Example:

● If you were building a learning algorithm to identify spam e-mail, the

examples would be data from many individual electronic messages.
● To detect cancerous tumors, the examples might comprise biopsies from
a number of patients
A feature is a characteristic or attribute of an example, which might be useful
for learning the desired concept.

What is a feature:
● attributes in the spam detection dataset might consist of the words used
in the e-mail messages.
● the cancer dataset, the attributes might be genomic data from the
biopsied cells, or measured characteristics of the patient such as weight,
height, or blood pressure.
The following spreadsheet
shows a dataset in matrix
format, which means that
each example has the same
number of features

Each row in the spreadsheet

is an example and each Here, the rows indicate examples of automobiles while
column is a feature. the columns record various features of the cars such as
the price, mileage, color, and transmission.
If a feature represents a characteristic measured in numbers, it is unsurprisingly called numeric.

If it measures an attribute that is represented by a set of categories, the feature is called categorical
or nominal.

A special case of categorical variables is called ordinal, which designates a nominal variable with
categories falling in an ordered list.

Examples of ordinal variables include clothing sizes such as small, medium, and large, or a
measurement of customer satisfaction on a scale from 1 to 5.
LEARNING
MODELS
GEOMETRIC MODEL
 kNN Algorithm
K-Nearest Neighbour Classification
Algorithm
LAZY LEARNING - Classification Using K-Nearest
Neighbour (KNN)
LAZY LEARNERS:

Learning from Neighbours

- Simply stores training data and waits until it gets a test tuple.
- Works only if gets a new example
- Less training time
- More prediction time

Eg: KNN Algorithm

Similar types of food tend to be
grouped closely together.

As illustrated in figure, vegetables

tend to be crunchy but not sweet,
fruits tend to be sweet and either
crunchy or not crunchy, while
proteins tend to be neither
crunchy nor sweet
We decide to use it to settle the
age-old question: is a tomato a
fruit or a vegetable? We can use
a nearest neighbor approach to
determine which class is a
better fit as shown in the
following figure
Calculating the distance
Locating the tomato's nearest neighbors requires a distance function, or a formula that
measures the similarity between two instances

Traditionally, the kNN algorithm uses Euclidean distance, which is the distance one would
measure if you could use a ruler to connect two points

where p and q are the examples to be compared, each having n features. The term p1 refers
to the value of the first feature of example p, while q1 refers to the value of the first feature
of example q:
For example, to calculate the distance between the tomato (sweetness = 6, crunchiness = 4),
and the green bean (sweetness = 3, crunchiness = 7), we can use the formula as follows:
Choosing an appropriate k value
Deciding how many neighbors to use for kNN determines how well the model
will generalize to future data.

The balance between overfitting and underfitting the training data is a

problem known as the bias-variance tradeoff.

Choosing a large k reduces the impact or variance caused by noisy data,

but can bias the learner such that it runs the risk of ignoring small, but
important patterns.
Choosing a large k value:

Suppose we choose a very large k,

equal to the total number of
observations in the training data. As
every training instance is
represented in the final vote, the
most common training class always
has a majority of the voters.
Choosing a smaller k value:
Choosing a single nearest neighbor allows
noisy data or outliers, to unduly influence
the classification of examples.
suppose that some of the training
examples were accidentally mislabeled.
Any unlabeled example that happens to
be nearest to the incorrectly labeled
neighbor will be predicted to have the
incorrect class, even if the other nine
nearest neighbors would have voted
differently
The best k value is somewhere between these two extremes.
The following figure illustrates more generally how the decision boundary (depicted by a
dashed line) is affected by larger or smaller k values.
Smaller values allow more complex decision boundaries that more carefully fit the
training data. The problem is that we do not know whether the straight boundary or the
curved boundary better represents the true underlying concept to be learned.
Usual practice of choosing a k value
Choosing k depends on the difficulty of the concept to be learned and the number of
records in the training data.
Typically, k is set somewhere between 3 and 10.
● A common practice is:
Set k equal to the square root of the number of training examples.
In the food classifier we developed previously, we might set k = 4, because there were 15
example ingredients in the training data and the square root of 15 is 3.87.
● An alternative approach:
To test several k values on a variety of test datasets and choose the one that delivers the
best classification performance.
Unless the data is very noisy, larger and more representative training datasets
can make the choice of k less important. This is because even subtle concepts
will have a sufficiently large pool of examples to vote as nearest neighbors.
 Preparing Data for use with kNN
If certain features have much larger values than
others, the distance measurements will be strongly
dominated by the larger values.

Suppose we added an additional feature indicating

spiciness, which we measured using the Scoville scale.
The Scoville scale is a standardized measure of spice
heat, ranging from zero (not spicy) to over a million
(for the hottest chili peppers).

While the difference between sweet and non-sweet is

at most ten, we might find that our distance
measures only differentiate foods by their spiciness;
the impact of crunchiness and sweetness would be
dwarfed by the contribution of spiciness
Rescaling the features
We need a way of "shrinking" or rescaling the various features such that each
one contributes relatively equally to the distance formula.

For example, if sweetness and crunchiness are both measured on a scale from
1 to 10, we would also like spiciness to be measured on a scale from 1 to 10
Min-Max re-scaling
The traditional method of rescaling features
for kNN is min-max normalization.
This process transforms a feature such that
all of its values fall in a range between 0 and
1. The formula for normalizing a feature is
as follows.

the formula subtracts the minimum of

feature X from each value and divides by
the range of X:
Z-score standardization
Another common transformation is called z-score standardization. The
following formula subtracts the mean value of feature X and divides by the
standard deviation of X
For Nominal Data
The Euclidean distance formula is
not defined for nominal data.

Therefore, to calculate the

distance between nominal
features, we need to convert them
into a numeric format.
A typical solution utilizes dummy coding, where a value of 1 indicates one
category, and 0 indicates the other. For instance, dummy coding for a gender
variable could be constructed as

dummy coding of the two-category (binary) gender variable results in a single

new feature named male. There is no need to construct a separate feature for
female; as the two genders are mutually exclusive,
An n-category nominal feature can be dummy coded by creating binary
indicator variables for (n - 1) levels of the feature.
For example, dummy coding for a three-category temperature variable (for
example, hot, medium, or cold) could be set up as (3 - 1) = 2 features, as
shown:

knowing that hot and medium are both 0 is enough to know that the
temperature is cold. We, therefore, do not need a third feature for the cold
attribute
 LEARNING
MODELS
PROBABILISTIC MODEL
Naive Bayes
Algorithm
A machine learning algorithm called naive Bayes, which
also uses principles of probability for classification
as meteorologists forecast weather, naive Bayes uses data about prior events
to estimate the probability of future events

An application:

naive Bayes uses the frequency of words in past junk email messages to
identify new junk mail.
Understanding Naive Bayes
-The technique descended from the work of the 18th century mathematician Thomas Bayes

The probability of an event is a number between 0 percent and 100 percent

that captures the chance that the event will occur given the available evidence.

The lower the probability, the less likely the event is to occur.

A probability of 0 percent indicates that the event definitely will not occur,
while a probability of 100 percent indicates that the event certainly will occur.
Classifiers based on Bayesian methods utilize
training data to calculate an observed
probability of each class based on feature
values.

When the classifier is used later on unlabeled

data, it uses the observed probabilities to
predict the most likely class for the new
features.

It's a simple idea, but it results in a method

that often has results on par with more
sophisticated algorithms.
Applications
● Text classification, such as junk email
(spam) filtering, author identification, or
topic categorization

● Intrusion detection or anomaly detection

in computer networks

● Diagnosing medical conditions, when

given a set of observed symptoms
Bayesian classifiers are best applied to problems in which the information
from numerous attributes should be considered simultaneously in order to
estimate the probability of an outcome.

While many algorithms ignore features that have weak effects, Bayesian methods
utilize all available evidence to subtly change the predictions.

If a large number of features have relatively minor effects, taken

together their combined impact could be quite large.
Bayesian Method
Bayesian probability theory is rooted in the idea that the estimated likelihood
of an event should be based on the evidence at hand.

Events are possible outcomes, such as sunny and rainy weather, a heads or
tails result in a coin flip, or spam and not spam email messages.

A trial is a single opportunity for the event to occur, such as a day's weather, a
coin flip, or an email message
Probability
If it rained 3 out of 10 days,
the probability of rain can be estimated as 30 percent.

Similarly, if 10 out of 50 email messages are spam, then

the probability of spam can be estimated as 10/50 = 20 percent.

The notation P(A) is used to denote the

probability of event A, as in P(spam) = 0.20.
Mutually exclusive or exhaustive
The total probability of all possible outcomes of a trial must always be 100 percent.

If the trial only has two outcomes that cannot occur simultaneously, such as heads or tails,
or spam and ham (non-spam), then knowing the probability of either outcome reveals the
probability of the other.

For example, given the value

P(spam) = 0.20,

we are able to calculate

P(ham) = 1 – 0.20 = 0.80.

This works because the events spam and ham are mutually exclusive and exhaustive.
Joint Probability
Consider an event based on the outcome that the email message contains the
word Virus.

For most people, this word is only likely to appear in a spam message; its
presence in a message is therefore a very strong piece of evidence that the
email is spam.
the Virus circle does not completely fill the spam circle, nor is it completely
contained by the spam circle.

This implies that not all spam messages contain the word Virus, and not every
email with the word Virus is spam.
We know that 20 percent of all
messages were spam (the left
circle),
and 5 percent of all messages
contained spam (the right circle).
Our job is to quantify the degree
of overlap between these two
proportions.
To estimate the probability of
both P(spam) and P(Virus)
occurring,
which can be written as P(spam
∩ Virus).
Calculating P(spam ∩ Virus) depends on the joint probability of the two events

If the two events are totally unrelated, they are called independent events.

For instance, the outcome of a coin flip is independent from whether the weather is rainy or sunny.

Dependent events are the basis of predictive modeling.

For instance, the presence of clouds is likely to be predictive of a rainy day.

The appearance of the word Viagra is predictive of a spam email.

With the knowledge that P(spam) and P(Virus) were independent,

we could then easily calculate P(spam ∩ Virus);

Because 20 percent of all messages are spam = P(spam)

and 5 percent of all emails contain the word Virus =

we could assume that 5 percent of 20 percent (0.05 * 0.20 = 0.01)

or 1 percent of all messages are spam containing the word Virus

More generally, for independent events A and B, the probability of

both happening is P(A ∩ B) = P(A) * P(B)
Conditional probability with Bayes' theorem
The relationships between dependent events can be described using Bayes'
theorem

The notation P(A|B) can be read as the probability of event A given that event
B occurred.

This is known as conditional probability, since the probability of A is

dependent (that is, conditional) on what happened with event B.
Task:

guessing the probability that an incoming email was spam = the probability
that any prior message was spam (that is, 20 percent in the preceding
example).

This is known as the prior probability

You were told that the incoming message used the term Virus.

The probability that the word Virus was used in previous spam messages is
called the likelihood
The probability that Virus appeared in any message at all is known as the
marginal likelihood.
By applying Bayes' theorem to this evidence, we can compute

a posterior probability that measures how likely the message is to be

spam.

If the posterior probability is greater than 50 percent, the message is more likely to
be spam than ham, and it should be filtered.
To calculate the components of Bayes' theorem
Construct a frequency table that
records the number of times Virus
appeared in spam and ham messages.

The frequency table can then be used

to construct a likelihood table
since the theorem says that
P(B|A) * P(A) = P(A ∩ B), or P(A ∩ B) = P(B|A) * P(A)
we can calculate
P(spam ∩ Virus) = P(Virus|spam) * P(spam) = (4/20) * (20/100) = 0.04.
This is four times greater than the previous estimate under the faulty
independence assumption illustrating the importance of Bayes' theorem when
calculating joint probability
To compute the posterior probability, P(spam|Virus), we simply take

P(spma|Virus) = (4/20) * (20/100) / (5/100)

= 0.80.
The naive Bayes algorithm
The naive Bayes (NB) algorithm describes a simple application using Bayes'
theorem for classification

Although it is not the only machine learning method utilizing Bayesian

methods, it is the most common, particularly for text classification.

The naive Bayes algorithm is named as such because it makes a couple of

"naive" assumptions about the data - that all of the features in the dataset are
equally important and independent. These are rarely true in most of the
real-world applications
Let's extend our spam filter by adding a few additional terms to be monitored:

money, groceries, and unsubscribe.

The naive Bayes learner is trained by constructing a likelihood table for the
appearance of these four words (W1, W2, W3, and W4), as shown in the
following diagram for 100 emails:
As new messages are received, the posterior probability must be calculated
to determine whether they are more likely spam or ham.
Given the likelihood of the words found in the message text.
For example, suppose that a message contains the terms Virus and
Unsubscribe, but does not contain either Money or Groceries.
Virus = Yes, Money = No, Groceries = No, and Unsubscribe = Yes
Virus = Yes, Money = No, Groceries = No, and Unsubscribe = Yes
The result of this formula should be compared to the probability that the
message is ham:
Using the values in the likelihood table, we can start filling numbers in these
equations. Because the denominator is the same in both cases, it can be
ignored for now. The overall likelihood of spam is then:
While the likelihood of ham given this pattern of words is

Because 0.012 / 0.002 = 6, we can say that this message is six times more likely
to be spam than ham.
The probability of spam is equal to the likelihood that the message is spam divided
by the likelihood that the message is either spam or ham
0.012 / (0.012 + 0.002) = 0.857

the probability of ham is equal to the likelihood that the message is ham divided by
the likelihood that the message is either spam or ham
0.002 / (0.012 + 0.002) = 0.143

Given the pattern of words in the message, we expect that the message is spam
with 85.7 percent probability, and ham with 14.3 percent probability.
Because these are mutually exclusive and exhaustive events, the probabilities sum
up to one.
Laplace Estimator
Let us consider one more example. Suppose we received another message,
this time containing the terms: Virus, Groceries, Money, and Unsubscribe.

Using the naive Bayes algorithm as before, we can compute the likelihood of
spam
And the likelihood of ham is:
the probability of spam is:

And the probability of ham is:

These results suggest that the message is spam with 0 percent probability
and ham with 100 percent probability.

The message contains several words usually associated with spam, including
Virus, which is very rarely used in legitimate messages. It is therefore very
likely that the message has been incorrectly classified.
Issue with Naive Bayes
This problem might arise if an event never occurs for one or more levels of the
class. For instance, the term Groceries had never previously appeared in a
spam message. Consequently, P(spam|groceries) = 0%.

Because probabilities in naive Bayes are multiplied, this 0 percent value

causes the posterior probability of spam to be zero, giving the word Groceries
the ability to effectively nullify and overrule all of the other evidence.

Even if the email was otherwise overwhelmingly expected to be spam, the

absence of the word Groceries will always result in a probability of spam
being zero.
Solution to Naive Bayes - Laplace Estimator
A solution to this problem involves using something called the Laplace
estimator, which is named after the French mathematician Pierre-Simon
Laplace.

The Laplace estimator essentially adds a small number to each of the counts
in the frequency table, which ensures that each feature has a nonzero
probability of occurring with each class.

The Laplace estimator is set to 1, which ensures that each class-feature

combination is found in the data at least once.
Using a Laplace value of 1, we add one to each numerator in the likelihood
function. The total number of 1s must also be added to each denominator.
The likelihood of spam is therefore:
And the likelihood of ham is:
This means that the probability of spam is 80 percent and the probability of
ham is 20 percent; a more plausible result than the one obtained when
Groceries alone determined the result.
Using numeric features with naive Bayes
Naive Bayes uses frequency tables for learning the data, each feature must be
categorical in order to create the combinations of class and feature values
comprising the matrix.

Since numeric features do not have categories of values, this algorithm does
not work directly with numeric data.
An easy and effective solution is to discretize numeric features.

-which simply means that the numbers are put into categories known as bins.

Discretization is also sometimes called binning.

This method is ideal when there are large amounts of training data, a
common condition when working with naive Bayes.
One thing to keep in mind is that discretizing a numeric feature always
results in a reduction of information, as the feature's original granularity is
reduced to a smaller number of categories.

It is important to strike a balance, since;

too few bins can result in important trends being obscured,

while too many bins can result in small counts in the naive Bayes
frequency table.
LEARNING
MODELS
LOGICAL MODEL
Divide and Conquer
Classification Using Decision
Trees and Rules
To make a difficult decision, some people weigh their options by making lists
of pros and cons for each possibility.

Example:
A job seeker was deciding between several offers, some closer or further from
home, with various levels of pay and benefits. He or she might create a list
with the features of each position. Based on these features, rules can be
created to eliminate some options.

Dividing data into smaller and smaller portions to identify patterns that can be
used for prediction.
Will discuss

decision trees and

rule learners

—two machine learning methods that apply a similar strategy of dividing data
into smaller and smaller portions to identify patterns that can be used for
prediction.
Decision Trees
A decision tree classifier in machine
learning is a supervised learning
algorithm that classifies data based on a
tree-like structure. It can also be used to
predict what will happen next.
This dataset contains two
features, X0 and X1

We have plotted X0 along the

Horizontal Axis (X-axis)

And X1 along the Vertical Axis

(Y-Axis)

The exist 2 classes GREEN and

RED

The classes are not linearly

separable - means you can’t draw
a line and split them into classes.
Decision tree learners build a model in the form of a tree structure.

The model itself comprises a series of logical decisions, similar to a flowchart,

with decision nodes that indicate a decision to be made on an attribute.

These split into branches that indicate the decision's choices.

The tree is terminated by leaf nodes (also known as terminal nodes) that
denote the result of following a combination of decisions.

Data that is to be classified begin at the root node where it is passed through
the various decisions in the tree according to the values of its features.
Scenarios where trees may not be an ideal fit. One such case might be a task
where

● the data has a large number of nominal features with many levels or
● if the data has a large number of numeric features.

These cases may result in a very large number of decisions and an overly
complex tree.
Example Questions
5 questions to work out in the next few slides
Divide and Conquer
Decision trees are built using a heuristic called recursive partitioning.

This approach is generally known as divide and conquer because it uses the
feature values to split the data into smaller and smaller subsets of similar
classes.

Beginning at the root node, which represents the entire dataset, the
algorithm chooses a feature that is the most predictive of the target class.
To build a simple decision tree
using this data, we can apply a
divide-and-conquer strategy.

Let's first split the feature

indicating the number of
celebrities, partitioning the movies
into groups with and without a low
number of A-list stars
Next, among the group of movies
with a larger number of celebrities,
we can make another split
between movies with and without
a high budget:
 If we wanted, we could continue to divide the data by splitting it based on
increasingly specific ranges of budget and celebrity counts until each of the
incorrectly classified values resides in its own, perhaps tiny partition.

Since the data can continue to be split until there are no distinguishing
features within a partition, a decision tree can be prone to be overfitting
for the training data with overly-specific decisions.

We'll avoid this by stopping the algorithm here since more than 80 percent of
the examples in each group are from a single class
Stopping criteria for Divide and Conquer algorithm:

This might occur at a node if:

• All (or nearly all) of the examples at the node have the same class

• There are no remaining features to distinguish among examples

• The tree has grown to a predefined size limit

C5.0 Decision Tree Algorithm
Choosing the best split
The first challenge that a decision tree will face is to identify which feature to
split upon.

If the segments of data contain only a single class, they are considered pure.

C5.0 uses entropy for measuring purity. The entropy of a sample of data
indicates how mixed the class values are; the minimum value of 0 indicates
that the sample is completely homogenous, while 1 indicates the maximum
amount of disorder. The definition of entropy is specified by
for a given segment of data (S),

the term c refers to the number of different class levels,

and pi refers to the proportion of values falling into class level i.

For example, suppose we have a partition of data with two classes:

red (60 percent), and white (40 percent). We can calculate the entropy as:
We can examine the entropy for all possible two-class arrangements.

If we know the proportion of examples in one class is x, then the proportion

in the other class is 1 - x.

Using the curve() function, we can then plot the entropy for all possible values
of x

the peak in entropy at x = 0.50, a 50-50 split results in

the maximum entropy. As one class increasingly
dominates the other, the entropy reduces to zero
According to Information Theory, The model will choose the split that maximises
the Information Gain.

In machine learning, information gain (IG) measures how much a feature reduces
uncertainty, or entropy, when used to split a dataset.
Pruning the Decision Tree
A decision tree can continue to grow indefinitely, choosing splitting features
and dividing into smaller and smaller partitions until each example is perfectly
classified or the algorithm runs out of features to split on.
However, if the tree grows overly large, many of the decisions it makes will
be overly specific and the model will have been overfitted to the training data.
The process of pruning a decision tree involves reducing its size such that it
generalizes better to unseen data.

Pre-Pruning
Post-Pruning
Classification Rules Learning
Separate and Conquer
1R algorithm
Understanding Classification Rules
Classification rules represent knowledge in the form of logical if-else
statements that assign a class to unlabeled examples.
They are specified in terms of an antecedent and a consequent; these form
a hypothesis stating that "if this happens, then that happens."
A simple rule might state that "if the hard drive is making a clicking sound,
then it is about to fail."
The antecedent comprises certain combinations of feature values, while
the consequent specifies the class value to assign if the rule's conditions
are met
Rule learners are often used in a manner similar to decision tree learners.

Unlike a tree, which must be applied from top-to-bottom, rules are facts that
stand alone.

The result of a rule learner is often more parsimonious, direct, and easier
to understand than a decision tree built on the same data

Rule learners are generally applied to problems where the features are
primarily or entirely nominal.
Separate and Conquer
Classification rule learning algorithms utilize a heuristic known as separate
and conquer.
The process involves:
● identifying a rule that covers a subset of examples in the training data,
and
● then separating this partition from the remaining data.
● As rules are added, additional subsets of data are separated until the
entire dataset has been covered and no more examples remain.
 Suppose you were tasked with creating
rules for identifying whether or not an
animal is a mammal. Can be depicted as a
large space, as in the diagram

A rule learner begins by using the available

features to find homogeneous groups.

For example, using a feature that measured

whether the species travels via land, sea, or
air, the first rule might suggest that any
land-based animals are mammals
If you look carefully, you might note that
frogs are amphibians, not mammals.
Therefore, our rule needs to be a bit more
specific.
Let's drill down further by suggesting that
mammals walk on land and have a tail:

One way to imagine the rule learning

process is to think about drilling down into
data by creating increasingly specific rules
for identifying class values,
Our more specific rule results in a subset
of animals that are entirely mammals
A potential feature distinguishing bats
from the other remaining animals
would be the presence of fur.

We learned a total of three rules:

● Animals that walk on land and
have tails are mammals
● If the animal has fur, it is a
mammal
● Otherwise, the animal is not a
mammal
Rules gradually consume larger and larger segments of data to eventually
classify all instances.
Divide-and-conquer and separate-and-conquer algorithms are known as
greedy learners because data is used on a first-come, first-served basis.

As the rules seem to cover portions of the data, separate-and-conquer

algorithms are also known as covering algorithms, and the rules are called
covering rules.
The One Rule Algorithm
The One Rule algorithm (1R or OneR), improves over ZeroR by selecting a
single rule. Although this may seem overly simplistic, it tends to perform
better than you might expect.

The accuracy of this algorithm can approach that of much more sophisticated
algorithms for many real-world tasks.
 For each feature, 1R divides the data into groups based on similar values of
the feature.

Then, for each segment, the algorithm predicts the majority class.

The error rate for the rule based on each feature is calculated, and the
rule with the fewest errors is chosen as the one rule.
As the Travels By feature resulted in fewer errors, the 1R algorithm would
return the following "one rule" based on Travels By:

● If the animal travels by air, it is not a mammal

● If the animal travels by land, it is a mammal
● If the animal travels by sea, it is not a mammal

The algorithm stops here, having found the single most important rule

Would you want a medical diagnosis system to consider only a single

symptom, or an automated driving system to stop or accelerate your car
based on only a single factor?
Rules for Decision Trees
Classification rules can also be
obtained directly from
decision trees.

Beginning at a leaf node and

following the branches back to
the root, you will have
obtained a series of
decisions.

These can be combined into a

single rule.
Following the paths from the root to
each leaf, the rules would be:
1. If the number of celebrities is low,
then the movie will be a Box Office
Bust.

2. If the number of celebrities is high

and the budget is high, then the
movie will be a Mainstream Hit.

3. If the number of celebrities is high

and the budget is low, then the
movie will be a Critical Success.