Prepared by :

KKB Vali Basha

Associate Professor (CSE)
MACHINE LEARNING VITW

UNIT-II
1. Distance based Methods
Distanced based algorithms are machine learning algorithms that classify queries
by computing distances between these queries and a number of internally stored
exemplars. Exemplars that are closets to the query have the largest influence on the
classification assigned to the query.

Euclidean Distance
It is the most common use of distance. In most cases when people said about
distance, they will refer to Euclidean distance. Euclidean distance is also known as
simply distance. When data is dense or continuous, this is the best proximity
measure. The Euclidean distance between two points is the length of the path
connecting them. The Pythagorean theory gives distance between two points.

Manhattan Distance
 If you want to find Manhattan distance between two different points (x1, y1) and
(x2, y2) such as the following, it would look like the following:
 Manhattan distance = (x2 – x1) + (y2 – y1)
 Diagrammatically, it would look like traversing the path from point A to point B
while walking on the pink straight line.
Minkowski Distance
The generalized form of the Euclidean and Manhattan Distances is the Minkowski
Distance. You can express the Minkowski distance as

he order of the norm is represented by p. When an order(p) is 1, Manhattan

Distance is represented, and when order(p) is 2 in the above formula,
Euclidean Distance is represented.

2. Nearest Neighbours
The abbreviation KNN stands for “K-Nearest Neighbour”. It is a supervised
machine learning algorithm. The algorithm can be used to solve both classification
and regression problem statements.

The number of nearest neighbours to a new unknown variable that has to be

predicted or classified is denoted by the symbol ‘K’.

KNN calculates the distance from all points in the proximity of the unknown data
and filters out the ones with the shortest distances to it. As a result, it’s often
referred to as a distance-based algorithm.
In order to correctly classify the results, we must first determine the value of K
(Number of Nearest Neighbours).

It is recommended to always select an odd value of K ~

When the value of K is set to even, a situation may arise in which the elements
from both groups are equal.
In the diagram below, elements from both groups are equal in the internal “Red”
circle (k == 4).
In this condition, the model would be unable to do the correct classification for
you. Here the model will
randomly assign any of the two classes to this new unknown data.
Choosing an odd value for K is preferred because such a state of equality between
the two classes would
never occur here. Due to the fact that one of the two groups would still be in the
majority, the value of K is selected as odd.

The impact of selecting a smaller or larger K value on the model

• Larger K value: The case of underfitting occurs when the value of k is increased.
In this case, the model would be unable to correctly learn on the training data.
• Smaller k value: The condition of overfitting occurs when the value of k is
smaller. The model will capture all of the training data, including noise. The model
will perform poorly for the test data in this scenario.
How does KNN work for ‘Classification’ and ‘Regression’ problem statements?
 Classification When the problem statement is of ‘classification’ type, KNN
tends to use the concept of “Majority Voting”.
Within the given range of K values, the class with the most votes is chosen.
Consider the following diagram, in which a circle is drawn within the radius of the
five closest neighbours.
Four of the five neighbours in this neighbourhood voted for ‘RED,’ while one
voted for ‘WHITE.’ It will be classified as a ‘RED’ wine based on the majority
votes.
Real-world example:
Several parties compete in an election in a democratic country like India. Parties
compete for voter support during election campaigns.

The public votes for the candidate with whom they feel more connected.
When the votes for all of the candidates have been recorded, the candidate with the
most votes is declared as the election’s winner.

Decision Trees

A decision tree is a flowchart-like structure in which each internal node

represents a test on a feature (e.g. whether a coin flip comes up heads or tails) ,
each leaf node represents a class label (decision taken after computing all
features) and branches represent conjunctions of features that lead to those class
labels. The paths from root to leaf represent classification rules. Below diagram
illustrate the basic flow of decision tree for decision making with labels
(Rain(Yes), No Rain(No)).

Decision Tree for Rain Forecasting

Decision tree is one of the predictive modelling approaches used in statistics, data
mining and machine learning.
Decision trees are constructed via an algorithmic approach that identifies ways to
split a data set based on different conditions. It is one of the most widely used
and practical methods for supervised learning. Decision Trees are a non-
parametric supervised learning method used for both classification and
regression tasks.

Tree models where the target variable can take a discrete set of values are called
classification trees. Decision trees where the target variable can take continuous
values (typically real numbers) are called regression trees. Classification And
Regression Tree (CART) is general term for this.
Approach to make decision tree

While making decision tree, at each node of tree we ask different type of
questions. Based on the asked question we will calculate the information gain
corresponding to it.

Information Gain

Information gain is used to decide which feature to split on at each step in

building the tree. Simplicity is best, so we want to keep our tree small. To do so,
at each step we should choose the split that results in the purest daughter nodes.
A commonly used measure of purity is called information. For each node of the
tree, the information value measures how much information a feature gives us
about the class. The split with the highest information gain will be taken as the
first split and the process will continue until all children nodes are pure, or until
the information gain is 0.

First let’s understand the meaning of Pure and Impure.

Pure
Pure means, in a selected sample of dataset all data belongs to same class (PURE).

Impure
Impure means, data is mixture of different classes.
Definition of Gini Impurity
Gini Impurity is a measurement of the likelihood of an incorrect classification of
a new instance of a random variable, if that new instance were randomly
classified according to the distribution of class labels from the data set.

If our dataset is Pure then likelihood of incorrect classification is 0. If our sample

is mixture of different classes then likelihood of incorrect classification will be
high.
Steps for Making decision tree

 Get list of rows (dataset) which are taken into consideration for making
decision tree (recursively at each nodes).
 Calculate uncertanity of our dataset or Gini impurity or how much our data
is mixed up
 Generate list of all question which needs to be asked at that node.
 Partition rows into True rows and False rows based on each question asked.
 Calculate information gain based on gini impurity and partition of data from
previous step.
 Update highest information gain based on each question asked.
 Update best question based on information gain (higher information gain).
 Divide the node on best question. Repeat again from step 1 again until
we get pure node (leaf nodes).
Advantage of Decision Tree

 Easy to use and understand.

 Can handle both categorical and numerical data.
 Resistant to outliers, hence require little data preprocessing.

Disadvantage of Decision Tree

 Prone to overfitting.
 Require some kind of measurement as to how well they are doing.
 Need to be careful with parameter tuning.
 Can create biased learned trees if some classes dominate.

How to avoid overfitting the Decision tree model

Overfitting is one of the major problem for every model in machine learning. If
model is overfitted it will poorly generalized to new samples. To avoid decision
tree from overfitting we remove the branches that make use of features having
low importance. This method is called as Pruning or post-pruning. This way we
will reduce the complexity of tree, and hence imroves predictive accuracy by the
reduction of overfitting.

Pruning should reduce the size of a learning tree without reducing predictive
accuracy as measured by a cross-validation set. There are 2 major Pruning
techniques.

 Minimum Error: The tree is pruned back to the point where the cross-
validated error is a minimum.
 Smallest Tree: The tree is pruned back slightly further than the minimum
error. Technically the pruning creates a decision tree with cross-
validation error within 1 standard error of the minimum error.

Naive Bayes Algorithm

 Naive Bayes method is predictive modeling.

 It is an algorithm for supervised learning.
 This method, which is based on the Bayes theorem, is used to
solve sorting difficulties.
 It is mostly employed in text classification using a high-
dimensional training dataset.
 The Naive Bayes algorithm is one of the most basic and effective
operational Classification algorithms for building fast machine-
learning models that can make quick predictions.
 It is a probabilistic classifier, which means it predicts on the basis
of the probability of an object.
 It indicates that it forecasts based on an object's likelihood.
 The following are more or less common examples of the Naive
Bayes Algorithm:

The Naïve Bayes algorithm is comprised of two words" Naïve" and "Bayes",
Which can be described as:

 Naïve: It is called Naïve because it assumes that the occurrence of a certain

feature is independent of the occurrence of other features. Such as if the fruit
is identified on the bases of color, shape, and taste, then red, spherical, and
sweet fruit is recognized as an apple. Hence each feature individually
contributes to identify that it is an apple without depending on each other.
 Bayes: It is called Bayes because it depends on the principle of Bayes'
Theorem.
Bayes' Theorem:

 Bayes' theorem is also known as Bayes' Rule or Bayes' law, which is used
to determine the probability of a hypothesis with prior knowledge. It
depends on the conditional probability.
 The formula for Bayes' theorem is given as:

Where,

P(A|B) is Posterior probability: Probability of hypothesis A on the observed

event B.

P(B|A) is Likelihood probability: Probability of the evidence given that the

probability of a hypothesis is true.

 Spam Detection
 Emotional Analysis
 Article Categorization

Linear Models

Linear regression is one of the easiest and most popular Machine Learning
algorithms. It is a statistical method that is used for predictive analysis. Linear
regression makes predictions for continuous/real or numeric variables
such as sales, salary, age, product price, etc.
Linear regression algorithm shows a linear relationship between a dependent (y)
and one or more independent (y) variables, hence called as linear regression. Since
linear regression shows the linear relationship, which means it finds how the value
of the dependent variable is changing according to the value of the independent
variable.

The linear regression model provides a sloped straight line representing the
relationship between the variables.
Consider the below image:
Mathematically, we can represent a linear regression as:
y= a0+a1x+ ε
Here,
Y= Dependent Variable (Target Variable)
X= Independent Variable (predictor Variable)
a0= intercept of the line (Gives an additional degree of freedom)
a1 = Linear regression coefficient (scale factor to each input value).
ε = random error
The values for x and y variables are training datasets for Linear Regression model
representation.

Types of Linear Regression

Linear regression can be further divided into two types of the algorithm:
Simple Linear Regression:
If a single independent variable is used to predict the value of a numerical
dependent variable, then such a Linear Regression algorithm is called Simple
Linear Regression.

Multiple Linear regression:

If more than one independent variable is used to predict the value of a numerical
dependent variable, then such a Linear Regression algorithm is called Multiple
Linear Regression.

Simple linear regression :

Simple Linear Regression is a type of Regression algorithms that models the
relationship between a dependent variable and a single independent variable. The
relationship shown by a Simple Linear Regression model is linear or a sloped
straight line, hence it is called Simple Linear Regression.

The key point in Simple Linear Regression is that the dependent variable
must be a continuous/real value.
However, the independent variable can be measured on continuous or categorical
values.
Simple Linear regression algorithm has mainly two objectives:
• Model the relationship between the two variables. Such as the relationship
between Income and expenditure, experience and Salary, etc.
• Forecasting new observations. Such as Weather forecasting according to
temperature, Revenue of a company according to the investments in a year, etc.

Simple Linear Regression Model:

The Simple Linear Regression model can be represented using the below equation:
y= a0+a1x+ ε
Where,
a0= It is the intercept of the Regression line (can be obtained putting x=0)
a1= It is the slope of the regression line, which tells whether the line is increasing
or decreasing.
ε = The error term. (For a good model it will be negligible)

Multiple linear regression

Multiple Linear Regression is one of the important regression algorithms which

models the linear relationship between a single dependent continuous variable and
more than one independent variable.
Example:
Prediction of CO2 emission based on engine size and number of cylinders in a car.
Some key points about MLR:
• For MLR, the dependent or target variable(Y) must be the continuous/real, but
the predictor or independent variable may be of continuous or categorical form.
• Each feature variable must model the linear relationship with the dependent
variable.
• MLR tries to fit a regression line through a multidimensional space of data-
points.
The multiple regression equation explained above takes the following form:
y = b1x1 + b2x2 + … + bnxn + c.
Where,
Y= Output/Response variable
b0, b1, b2, b3 , bn....= Coefficients of the model.
x1, x2, x3, x4,...= Various Independent/feature variable
Assumptions for Multiple Linear Regression:
• A linear relationship should exist between the Target and predictor variables.
• The regression residuals must be normally distributed.
• MLR assumes little or no multicollinearity (correlation between the independent
variable) in data.

Binary Classification

It is a process or task of classification, in which a given data is being classified into

two classes. It’s basically a kind of prediction about which of two groups the thing
belongs to.
Let us suppose, two emails are sent to you, one is sent by an insurance
company that keeps sending their ads, and the other is from your bank regarding
your credit card bill. The email service provider will classify the two emails, the
first one will be sent to the spam folder and the second one will be kept in the
primary one.
This process is known as binary classification, as there are two discrete
classes, one is spam and the other is primary. So, this is a problem of binary
classification.
Binary classification uses some algorithms to do the task, some of the most
common algorithms used by binary classification are .
 Logistic Regression
 k-Nearest Neighbors
 Decision Trees
 Support Vector Machine
 Naive Bayes

Multiclass Classification

Multi-class classification is the task of classifying elements into different classes.

Unlike binary, it doesn’t restrict itself to any number of classes.
Examples of multi-class classification are
 classification of news in different categories,
 classifying books according to the subject,
 classifying students according to their streams etc.
In these, there are different classes for the response variable to be classified in and
thus according to the name, it is a Multi-class classification.
Can a classification possess both binary or multi-class?
Let us suppose we have to do sentiment analysis of a person, if the classes are just
“positive” and “negative”, then it will be a problem of binary class. But if the
classes are “sadness”, happiness”, “disgusting”, “depressed”, then it will be called
a problem of Multi-class classification.

Parameters Binary classification Multi-class classification

No. of It is a classification of There can be any number of classes in

classes two groups, i.e. it, i.e.,
classifies objects in at classifies the object into more than
most two classes. two classes.
Algorithms
The most popular
used
algorithms used by the
Popular algorithms that can be used
binary classification are-
for multi-class
Logistic Regression classification include:
• k-Nearest Neighbors
. k-Nearest Neighbors
• Decision Trees
• Decision Trees
• Support Vector
• Naive Bayes
Machine
Examples • Random Forest.
Examples of binary • Gradient Boosting
classification include-
 • Email spam detection Examples of multi-class classification
(spam or include:
not). • Face classification.
• Churn prediction • Plant species classification.
(churn or not). • Optical character recognition.
• Conversion prediction
(buy or
not).

MNIST

The MNIST database (Modified National Institute of Standards and Technology

database) is a large database of handwritten digits that is commonly used for
training various image processing systems.

The database is also widely used for training and testing in the field of machine
learning.
It was created by "re-mixing" the samples from NIST's original datasets.
The creators felt that since NIST's training dataset was taken from American
Census Bureau employees, while the testing dataset was taken from American high
school students, it was not well-suited for machine learning experiments.
Furthermore, the black and white images from NIST were normalized to fit into a
28x28 pixel bounding box and anti-aliased, which introduced grayscale levels.
The MNIST database contains 60,000 training images and 10,000 testing images.
Half of the training set and half of the test set were taken from NIST's training
dataset, while the other half of the training set and the other half of the test set were
taken from NIST's testing dataset. The original creators of the database keep a list
of some of the methods tested on it. In their original paper, they use a support-
vector machine to get an error rate of 0.8%.

Extended MNIST (EMNIST) is a newer dataset developed and released by NIST

to be the (final) successor to MNIST.[11][12] MNIST included images only of
handwritten digits. EMNIST includes all the images from NIST Special Database
19, which is a large database of handwritten uppercase and lower case letters as
well as digits. The images in EMNIST were converted into the same 28x28 pixel
format, by the same process, as were the MNIST images. Accordingly, tools which
work with the older, smaller, MNIST dataset will likely work unmodified with
EMNIST