Classification Algorithms
An overview of Decision Trees, Random Forests,
Support Vector Machines, and k-Nearest Neighbors
[Link]
• Decision Trees and Random Forests
Agenda • Support Vector Machines
• k-Nearest Neighbors (k-NN)
9/3/20XX Classification Algorithms 2
Classification is a fundamental concept in the realm of
machine learning where the primary goal is to categorize
Introduction to data into predefined classes or labels. It's akin to sorting
Classification objects into different boxes based on specific features.
For instance, in email filtering, the classification algorithm
Algorithms determines whether an incoming email is spam or not
based on various characteristics of the email.
9/3/20XX Classification Algorithms 3
In machine learning, classification refers to the task of
predicting the category or class of a given data point or
Definition of sample based on its features. This supervised learning
approach requires a labeled dataset, where each data
classification in point is associated with a predefined class. The
Machine Learning algorithm learns from this data and then applies its
knowledge to classify new, unseen data.
9/3/20XX Classification Algorithms 4
Classification algorithms hold immense significance in
real-world applications. From detecting fraudulent
Importance transactions in banking, diagnosing diseases in
and healthcare, to recommending products in e-commerce,
these algorithms play a pivotal role. Their ability to swiftly
applications of and accurately categorize data allows businesses and
classification industries to make informed decisions, enhance user
experience, and ensure safety and efficiency in various
algorithms: operations.
9/3/20XX Classification Algorithms 5
Decision Trees
9/3/20XX Classification Algorithms 6
Definition
A decision tree is a flowchart-like tree structure where
each internal node represents a feature(or attribute), each
branch represents a decision rule, and each leaf node
represents an outcome or class. The topmost node in a
decision tree is known as the root node, and it learns to
partition data based on the value of an attribute, thus
leading to more granular and specific decisions as one
traverses down the tree.
9/3/20XX Classification Algorithms 7
A simple decision
tree diagram.
Imagine a tree diagram, starting with a single root node at the
top. This node represents a decision based on a specific feature.
From this root node, branches extend, leading to additional
nodes, each signifying another decision based on different feature
values. As you follow these branches downwards, they split
further, reflecting more detailed decisions. Finally, these branches
end at leaf nodes, which don't split any further and represent the
final classification outcomes or categories. This visual structure
encapsulates the decision-making process, translating data
features into a clear path from root to outcome.
9/3/20XX Classification Algorithms 8
Pros and cons
Pros:
• Easy to understand and interpret, even for non-experts.
• Requires little data preprocessing, such as normalization.
• Can handle both numerical and categorical data.
Cons:
• Prone to overfitting, especially with deep trees.
• Can be sensitive to small variations in data.
• Might not be as accurate as some other, more complex
algorithms.
Classification Algorithms
9/3/20XX 9
How Decision Trees
Work
9/3/20XX Classification Algorithms 10
splitting criteria like entropy
and gini impurity
Splitting criteria determine the "questions" a decision tree asks, and they're
pivotal in constructing an effective tree. Two commonly used criteria are
entropy and gini impurity:
Entropy measures the disorder or randomness in a set. A set with all identical
items has entropy of 0 (completely ordered), while a set split evenly between
two classes has the highest entropy (most disordered). The tree aims to
reduce entropy with each split, striving for clearer, more ordered subsets.
Gini Impurity measures the frequency a randomly chosen element would be
incorrectly classified. A gini impurity of 0 means all elements in the set
belong to a single class. The tree tries to minimize the gini impurity, aiming
for subsets where data points are of a single class.
Both criteria are means to the same end: creating the most homogeneous
subsets possible with each split.
9/3/20XX 11
Classification Algorithms
Example of a decision-
making process using a
decision tree
Consider a simple scenario where a bank wants to decide if they
should offer a loan to an individual. The decision tree might start at
the root with the question: "Is the applicant's income above
$50,000?" If yes, the next question might be about the credit score:
"Is the credit score above 700?" Branching out further, the tree
might query about employment history or outstanding debts. Each
question helps navigate closer to the decision: approve or decline
the loan. By the time we reach the leaf nodes (the ends of our
branches), we have a clear, data-driven decision based on the
cascading questions the applicant met along the way.
9/3/20XX Classification Algorithms 12
Random Forests
9/3/20XX Classification Algorithms 13
Definition
A Random Forest is aptly named because it's truly a "forest"
of decision trees. Instead of training a single tree on all the
data, Random Forests train multiple trees on different
subsets of the data. When making a prediction, all the trees
in this ensemble "vote", and the majority class (in
classification problems) or average prediction (in regression
problems) is chosen as the final output.
9/3/20XX Classification Algorithms 14
Importance of bagging
and feature randomness.
Two crucial mechanisms make Random Forests effective: bagging
and feature randomness.
Bagging (Bootstrap Aggregating): For each tree in the forest, a
random sample of the data is chosen with replacement (some data
points might be chosen multiple times, while others might not be
chosen at all). This ensures that each tree is slightly different, trained
on different data.
Feature Randomness: Instead of considering all features for a split
at a node, only a random subset of features is considered. This
introduces further variability among the trees, ensuring they aren't
identical and don't make the same decisions.
Together, these mechanisms reduce the variance of the model and
make it more resilient against overfitting.
9/3/20XX Classification Algorithms 15
Several decision
trees forming a
forest.
An expansive landscape filled with a variety of trees, each
representing an individual decision tree. Differences in tree
sizes and structures symbolize the unique training and
decisions of each tree. The collective ensemble of trees,
dense and interconnected, embodies the collaborative
strength of the Random Forest algorithm, where the
combined wisdom of all trees determines the final output.
9/3/20XX Classification Algorithms 16
Pros and cons.
Pros:
• Highly accurate due to multiple trees contributing to the final
decision.
• Effective in handling large datasets with higher dimensionality.
• Reduces overfitting compared to a single decision tree.
• Can estimate feature importances, providing insight into the
dataset.
Cons:
• More computationally intensive because of the need to train
multiple trees.
• Can be slower in prediction than a single decision tree.
• Requires more memory/storage due to the multitude of trees.
• Can be harder to interpret compared to a singular decision tree.
9/3/20XX Classification Algorithms 17
Support Vector
Machines (SVM)
9/3/20XX Classification Algorithms 18
Definition
SVM operates by finding a hyperplane that best separates
data into distinct classes. In simpler terms, imagine drawing a
line (in 2D) or a plane (in 3D) that best divides data points
from two different categories. The primary objective of SVM is
to maximize the margin between this boundary and the
nearest data points from both classes. These particular points
are known as "support vectors", and they essentially define
the optimal positioning of the separating hyperplane.
Classification Algorithms
9/3/20XX 19
Hyperplanes separating
data in a 2D space.
A 2D graph displaying data points from two distinct
categories. A prominent line, representing the
hyperplane, strategically bisects the space, ensuring
maximum distance from the closest points of both
categories. Key data points, known as 'support vectors',
are accentuated on the graph, underlining their role in
determining the optimal position of this dividing line.
9/3/20XX Classification Algorithms 20
Pros and cons
Pros:
Effective in high-dimensional spaces or when there are many
features.
Works well even when the number of dimensions exceeds the
number of samples.
Versatile: Different Kernel functions can be used to adapt to various
data structures.
Cons:
Not suitable for very large datasets due to its computational intensity.
Requires a good choice of Kernel function, which isn't always
straightforward.
Can be challenging to interpret and visualize, especially in higher
9/3/20XX dimensions. 21
Classification Algorithms
How SVM Works
9/3/20XX Classification Algorithms 22
Explanation of
maximizing margin.
At the heart of SVM is the goal to find the "best" boundary or
hyperplane that separates data points of different classes.
The "best" here refers to a boundary that has the largest
distance (or margin) from the nearest data points of each
class. Maximizing this margin ensures that new data points
are classified with higher confidence, as they would need to
fall significantly on one side of the boundary to belong to a
particular class.
9/3/20XX Classification Algorithms 23
Introducing the concept
of support vectors.
Support vectors are the data points that lie closest to the
separating hyperplane and effectively "support" or
determine its position. These vectors are pivotal because
even if all other data points were removed, the
hyperplane's position would remain unchanged as long
as these support vectors are intact. In essence, they are
the critical elements that the SVM algorithm revolves
around.
9/3/20XX Classification Algorithms 24
Kernel trick for non-linear
data separation.
While SVM can linearly separate data with a straight
hyperplane in simpler scenarios, real-world data is often not
linearly separable. This is where the kernel trick comes into
play. Instead of trying to draw complex boundaries in the
original space, SVM uses kernel functions to transform data
into a higher-dimensional space where it becomes linearly
separable. Common kernels include polynomial, radial basis
function (RBF), and sigmoid. Once the data is separated in
this transformed space, the inverse transformation maps the
linear boundary back to the original space, resulting in a
complex, non-linear decision boundary.
9/3/20XX Classification Algorithms 25
k-Nearest Neighbors (k-
NN)
9/3/20XX Classification Algorithms 26
Definition
k-Nearest Neighbors operates on a straightforward principle: similar
data points lie close to each other. When making a prediction for a
new data point, k-NN looks at the 'k' training samples that are closest
to the point and returns the most common output value among them
as the prediction. For instance, if 'k' is 3, and two out of the three
closest points belong to class A and one to class B, the new data point
would be classified as A.
9/3/20XX Classification Algorithms 27
Plot showing data points and
how neighbors are
determined.
A scatter plot displays data points from various classes. A distinct,
highlighted point represents a new data sample we want to classify.
Surrounding this point, lines or circles connect it to its 'k' nearest
neighbors, visually emphasizing the role of closeness in its potential
classification. The slide dynamically varies the value of 'k', illustrating
how the selection of different neighboring points directly impacts the
classification outcome.
9/3/20XX 28
Classification Algorithms
Pros and cons.
Pros:
• Simple and intuitive, making it easy to understand and
implement.
• Effective for datasets with irregular decision boundaries.
• Doesn't assume any underlying data distribution.
Cons:
• Computationally intensive for large datasets as it requires
measuring distances to all training samples for each prediction.
• Sensitivity to irrelevant features and the scale of the data.
• Choosing the right value for 'k' and the type of distance can be
tricky, impacting the model's performance.
9/3/20XX Classification Algorithms 29
How k-NN Works
9/3/20XX Classification Algorithms 30
Explanation of the
distance metric
To determine which points are "nearest" in k-NN, we need a way to
measure the distance between points. Different metrics can be
employed:
Euclidean Distance: Often referred to as the L2 norm, this is the
straight-line distance between two points. It's akin to the distance
measure we're intuitively familiar with in two or three dimensions.
Manhattan Distance (L1 norm): Instead of a straight line, this metric
calculates the distance based on paths that are parallel to the axes.
Picture navigating a grid-like city, moving block by block, rather than
cutting diagonally through buildings.
Other distance metrics can also be used, and the choice often
depends on the nature and dimensionality of the data.
9/3/20XX Classification Algorithms 31
Importance of choosing
the right 'k'
The 'k' in k-NN stands for the number of neighbors we consider
when making a prediction. Choosing the right 'k' is crucial:
A smaller 'k' (like 1 or 3) can be noisy and sensitive to outliers.
A larger 'k' smoothens the decision boundary but might include
points from other classes, diluting the local structure of the data.
Often, a validation set or cross-validation techniques are used to
fine-tune the value of 'k'.
9/3/20XX 32
Classification Algorithms
Use cases and when it's
beneficial to use k-NN
k-NN shines in scenarios where the decision boundary is
irregular or where the data lacks a clear parametric form.
Common use cases include:
Image or handwriting recognition, where pixel similarities can
determine classifications.
Recommendation systems, as users with similar behaviors or
preferences (neighbors) can suggest items to a new user.
However, its simplicity and non-parametric nature also make it
ideal for preliminary data analysis and as a benchmark against
more complex models.
9/3/20XX Classification Algorithms 33
[Link]
Thank you Ghayoumi@[Link]
9/3/20XX Classification Algorithms 34