Decision Tree
What is a Decision Tree?
A decision tree is a flowchart-like structure used to make decisions or predictions. It consists
of nodes representing decisions or tests on attributes, branches representing the outcome of
these decisions, and leaf nodes representing final outcomes or predictions. Each internal node
corresponds to a test on an attribute, each branch corresponds to the result of the test, and each
leaf node corresponds to a class label or a continuous value.
Structure of a Decision Tree
1. Root Node: Represents the entire dataset and the initial decision to be made.
2. Internal Nodes: Represent decisions or tests on attributes. Each internal node has one or
more branches.
3. Branches: Represent the outcome of a decision or test, leading to another node.
4. Leaf Nodes: Represent the final decision or prediction. No further splits occur at these
nodes.
How Decision Trees Work?
The process of creating a decision tree involves:
1. Selecting the Best Attribute: Using a metric like Gini impurity, entropy, or information
gain, the best attribute to split the data is selected.
2. Splitting the Dataset: The dataset is split into subsets based on the selected attribute.
3. Repeating the Process: The process is repeated recursively for each subset, creating a new
internal node or leaf node until a stopping criterion is met (e.g., all instances in a node
belong to the same class or a predefined depth is reached).
Metrics for Splitting
Gini Impurity: Measures the likelihood of an incorrect classification of a new instance if it
was randomly classified according to the distribution of classes in the dataset.
o Gini=1–∑i=1n(pi)2Gini=1–∑i=1n(pi)2, where pi is the probability of an instance being
classified into a particular class.
Entropy: Measures the amount of uncertainty or impurity in the dataset.
o Entropy=−∑i=1npilog2(pi)Entropy=−∑i=1npilog2(pi), where pi is the probability of an
instance being classified into a particular class.
Information Gain: Measures the reduction in entropy or Gini impurity after a dataset is
split on an attribute.
o InformationGain=Entropyparent–∑i=1n(∣Di∣∣D∣∗Entropy(Di))InformationGain=Entropyparent
–∑i=1n(∣D∣∣Di∣∗Entropy(Di)), where Di is the subset of D after splitting by an attribute.
Advantages of Decision Trees
Simplicity and Interpretability: Decision trees are easy to understand and interpret. The
visual representation closely mirrors human decision-making processes.
Versatility: Can be used for both classification and regression tasks.
No Need for Feature Scaling: Decision trees do not require normalization or scaling of the
data.
Handles Non-linear Relationships: Capable of capturing non-linear relationships between
features and target variables.
Disadvantages of Decision Trees
Overfitting: Decision trees can easily overfit the training data, especially if they are deep
with many nodes.
Instability: Small variations in the data can result in a completely different tree being
generated.
Bias towards Features with More Levels: Features with more levels can dominate the tree
structure.
Applications of Decision Trees
Business Decision Making: Used in strategic planning and resource allocation.
Healthcare: Assists in diagnosing diseases and suggesting treatment plans.
Finance: Helps in credit scoring and risk assessment.
Marketing: Used to segment customers and predict customer behavior.
K-Nearest Neighbor(KNN) Algorithm
The K-Nearest Neighbors (KNN) algorithm is a supervised machine learning
method employed to tackle classification and regression problems.
What is the K-Nearest Neighbors Algorithm?
KNN is one of the most basic yet essential classification algorithms in machine
learning. It belongs to the supervised learning domain and finds intense application
in pattern recognition, data mining, and intrusion detection.
We are given some prior data (also called training data), which classifies coordinates
into groups identified by an attribute.
As an example, consider the following table of data points containing two features:
KNN Algorithm working visualization
Now, given another set of data points (also called testing data), allocate these points
to a group by analyzing the training set. Note that the unclassified points are marked
as ‘White’.
Intuition Behind KNN Algorithm
If we plot these points on a graph, we may be able to locate some clusters or groups.
Now, given an unclassified point, we can assign it to a group by observing what
group its nearest neighbours belong to. This means a point close to a cluster of
points classified as ‘Red’ has a higher probability of getting classified as ‘Red’.
Intuitively, we can see that the first point (2.5, 7) should be classified as ‘Green’, and
the second point (5.5, 4.5) should be classified as ‘Red’.
Why do we need a KNN algorithm?
(K-NN) algorithm is a versatile and widely used machine learning algorithm that is
primarily used for its simplicity and ease of implementation. It does not require any
assumptions about the underlying data distribution. It can also handle both numerical
and categorical data, making it a flexible choice for various types of datasets in
classification and regression tasks. It is a non-parametric method that makes
predictions based on the similarity of data points in a given dataset. K-NN is less
sensitive to outliers compared to other algorithms.
The K-NN algorithm works by finding the K nearest neighbors to a given data point
based on a distance metric, such as Euclidean distance.
How to choose the value of k for KNN Algorithm?
The value of k is very crucial in the KNN algorithm to define the number of neighbors
in the algorithm. The value of k in the k-nearest neighbors (k-NN) algorithm should
be chosen based on the input data. If the input data has more outliers or noise, a
higher value of k would be better. It is recommended to choose an odd value for k to
avoid ties in classification.
Workings of KNN algorithm
Thе K-Nearest Neighbors (KNN) algorithm operates on the principle of similarity,
where it predicts the label or value of a new data point by considering the labels or
values of its K nearest neighbors in the training dataset.
Step-by-Step explanation of how KNN works is discussed below:
Step 1: Selecting the optimal value of K
K represents the number of nearest neighbors that needs to be considered while
making prediction.
Step 2: Calculating distance
To measure the similarity between target and training data points, Euclidean
distance is used. Distance is calculated between each of the data points in the
dataset and target point.
Step 3: Finding Nearest Neighbors
The k data points with the smallest distances to the target point are the nearest
neighbors.
Step 4: Voting for Classification or Taking Average for Regression
In the classification problem, the class labels of K-nearest neighbors are
determined by performing majority voting. The class with the most occurrences
among the neighbors becomes the predicted class for the target data point.
In the regression problem, the class label is calculated by taking average of the
target values of K nearest neighbors. The calculated average value becomes the
predicted output for the target data point.
Advantages of the KNN Algorithm
Easy to implement as the complexity of the algorithm is not that high.
Adapts Easily – As per the working of the KNN algorithm it stores all the data in
memory storage and hence whenever a new example or data point is added then
the algorithm adjusts itself as per that new example and has its contribution to the
future predictions as well.
Few Hyperparameters – The only parameters which are required in the training
of a KNN algorithm are the value of k and the choice of the distance metric which
we would like to choose from our evaluation metric.
Disadvantages of the KNN Algorithm
Does not scale – As we have heard about this that the KNN algorithm is also
considered a Lazy Algorithm. The main significance of this term is that this takes
lots of computing power as well as data storage. This makes this algorithm both
time-consuming and resource exhausting.
Curse of Dimensionality – There is a term known as the peaking phenomenon
according to this the KNN algorithm is affected by the curse of
dimensionality which implies the algorithm faces a hard time classifying the data
points properly when the dimensionality is too high.
Prone to Overfitting – As the algorithm is affected due to the curse of
dimensionality it is prone to the problem of overfitting as well. Hence
generally feature selection as well as dimensionality reduction techniques are
applied to deal with this problem.
Applications of the KNN Algorithm
Data Preprocessing – While dealing with any Machine Learning problem we first
perform the EDA part in which if we find that the data contains missing values
then there are multiple imputation methods are available as well. One of such
method is KNN Imputer which is quite effective ad generally used for
sophisticated imputation methodologies.
Pattern Recognition – KNN algorithms work very well if you have trained a KNN
algorithm using the MNIST dataset and then performed the evaluation process
then you must have come across the fact that the accuracy is too high.
Recommendation Engines – The main task which is performed by a KNN
algorithm is to assign a new query point to a pre-existed group that has been
created using a huge corpus of datasets. This is exactly what is required in
the recommender systems to assign each user to a particular group and then
provide them recommendations based on that group’s preferences.
Linear Regression in Machine learning
Machine Learning is a branch of Artificial intelligence that focuses on the development of
algorithms and statistical models that can learn from and make predictions on data. Linear
regression is also a type of machine-learning algorithm more specifically a supervised
machine-learning algorithm that learns from the labelled datasets and maps the data points to
the most optimized linear functions, which can be used for prediction on new datasets.
First off we should know what supervised machine learning algorithms is. It is a type of
machine learning where the algorithm learns from labelled data. Labeled data means the
dataset whose respective target value is already known. Supervised learning has two types:
Classification: It predicts the class of the dataset based on the independent input
variable. Class is the categorical or discrete values. like the image of an animal is a cat
or dog?
Regression: It predicts the continuous output variables based on the independent input
variable. like the prediction of house prices based on different parameters like house age,
distance from the main road, location, area, etc.
What is Linear Regression?
Linear regression is a type of supervised machine learning algorithm that computes
the linear relationship between the dependent variable and one or more independent
features by fitting a linear equation to observed data.
When there is only one independent feature, it is known as Simple Linear
Regression, and when there are more than one feature, it is known as Multiple Linear
Regression.
Similarly, when there is only one dependent variable, it is considered Univariate
Linear Regression, while when there are more than one dependent variables, it is
known as Multivariate Regression.
Why Linear Regression is Important?
The interpretability of linear regression is a notable strength. The model’s equation
provides clear coefficients that elucidate the impact of each independent variable on
the dependent variable, facilitating a deeper understanding of the underlying
dynamics. Its simplicity is a virtue, as linear regression is transparent, easy to
implement, and serves as a foundational concept for more complex algorithms.
Linear regression is not merely a predictive tool; it forms the basis for various
advanced models. Techniques like regularization and support vector machines draw
inspiration from linear regression, expanding its utility. Additionally, linear regression
is a cornerstone in assumption testing, enabling researchers to validate key
assumptions about the data.
Types of Linear Regression
There are two main types of linear regression:
Simple Linear Regression
This is the simplest form of linear regression, and it involves only one independent
variable and one dependent variable. The equation for simple linear regression is:
y=β0+β1Xy=β0+β1X
where:
Y is the dependent variable
X is the independent variable
β0 is the intercept
β1 is the slope
Multiple Linear Regression
This involves more than one independent variable and one dependent variable. The
equation for multiple linear regression is:
y=β0+β1X1+β2X2+………βnXny=β0+β1X1+β2X2+………βnXn
where:
Y is the dependent variable
X1, X2, …, Xn are the independent variables
β0 is the intercept
β1, β2, …, βn are the slopes
The goal of the algorithm is to find the best Fit Line equation that can predict the values based on the
independent variables.
In regression set of records are present with X and Y values and these values are
used to learn a function so if you want to predict Y from an unknown X. In regression
we have to find the value of Y, So, a function is required that predicts continuous Y in
the case of regression given X as independent features.
What is the best Fit Line?
Our primary objective while using linear regression is to locate the best-fit line, which
implies that the error between the predicted and actual values should be kept to a
minimum. There will be the least error in the best-fit line.
The best Fit Line equation provides a straight line that represents the relationship
between the dependent and independent variables. The slope of the line indicates
how much the dependent variable changes for a unit change in the independent
variable(s).
Linear Regression
Here Y is called a dependent or target variable and X is called an independent
variable also known as the predictor of Y. There are many types of functions or
modules that can be used for regression. A linear function is the simplest type of
function. Here, X may be a single feature or multiple features representing the
problem.
Linear regression performs the task to predict a dependent variable value (y) based
on a given independent variable (x)). Hence, the name is Linear Regression. In the
figure above, X (input) is the work experience and Y (output) is the salary of a
person. The regression line is the best-fit line for our model.
Evaluation Metrics for Linear Regression
A variety of evaluation measures can be used to determine the strength of any linear
regression model. These assessment metrics often give an indication of how well the
model is producing the observed outputs.
The most common measurements are:
Mean Square Error (MSE)
Mean Squared Error (MSE) is an evaluation metric that calculates the average of the
squared differences between the actual and predicted values for all the data points.
The difference is squared to ensure that negative and positive differences don’t
cancel each other out.
MSE=1n∑i=1n(yi–yi^)2MSE=n1∑i=1n(yi–yi)2
Here,
n is the number of data points.
yi is the actual or observed value for the ith data point.
yi^yi is the predicted value for the ith data point.
MSE is a way to quantify the accuracy of a model’s predictions. MSE is sensitive to
outliers as large errors contribute significantly to the overall score.
Mean Absolute Error (MAE)
Mean Absolute Error is an evaluation metric used to calculate the accuracy of a
regression model. MAE measures the average absolute difference between the
predicted values and actual values.
Lower MAE value indicates better model performance. It is not sensitive to the
outliers as we consider absolute differences.
Root Mean Squared Error (RMSE)
The square root of the residuals’ variance is the Root Mean Squared Error. It
describes how well the observed data points match the expected values, or the
model’s absolute fit to the data.
RSME is not as good of a metric as R-squared. Root Mean Squared Error can
fluctuate when the units of the variables vary since its value is dependent on the
variables’ units (it is not a normalized measure).
Coefficient of Determination (R-squared)
R-Squared is a statistic that indicates how much variation the developed model can
explain or capture. It is always in the range of 0 to 1. In general, the better the model
matches the data, the greater the R-squared number.
In mathematical notation, it can be expressed as:
R2=1−(RSSTSS)R2=1−(TSSRSS)
Residual sum of Squares (RSS): The sum of squares of the residual for each
data point in the plot or data is known as the residual sum of squares, or RSS. It is
a measurement of the difference between the output that was observed and what
was anticipated.
RSS=∑i=2n(yi−b0−b1xi)2RSS=∑i=2n(yi−b0−b1xi)2
Total Sum of Squares (TSS): The sum of the data points’ errors from the answer
variable’s mean is known as the total sum of squares, or TSS.
TSS=∑(y−yi‾)2TSS=∑(y−yi)2
R squared metric is a measure of the proportion of variance in the dependent
variable that is explained the independent variables in the model.