Antoine PALISSON

Machine Learning
Unsupervised Methods
 TABLE OF CONTENTS

Dimensionality
01 Introduction
Reduction 02

03 Clustering Anomaly Detection 04

Association Rules Doorway to Deep
05 Learning Learning methods 06
2
 01
Introduction
3
 Antoine PALISSON

Introduction
Most of the available data is not labelled : we only have the features.
Unfortunately, supervised machine learning algorithms need labels to
estimate the error made by the prediction and ultimately improve its
performances by updating its parameters.
There are two solutions:
● To label the unlabelled data before using any supervised algorithm
but it is generally very expensive and time consuming as experts may
be needed to do the task
● To replace supervised algorithm by algorithms that do not need any
labels and thus avoiding the costly labelling step
4
 Antoine PALISSON

Definition
Unsupervised learning are methods to learn when the data does not have
any label. In short, unsupervised algorithms work on their own, i.e. without a
supervisor, to detect new patterns and useful information in data that have or
have not any internal relationship.
Imagine a set of cat and dog pictures without any label on it.
An adult could easily spot the difference even without any label because he already learned
to make the difference. However, a newborn does not know the difference (they both are
four legs living being with fur).
The baby might be able to differentiate the two animals by comparing a lot of dogs and
cats and remembering their features → it is the unsupervised method.
Or the baby can be helped by an adult → it is the supervised method.
5
 Antoine PALISSON

Definition (2)
Unsupervised learning methods are not restricted to unlabelled data.
Indeed, unsupervised algorithms can be used on labelled data, the labels are
simply ignored or seen as features.

X1 … Xn Y X1 … Xn

Instance1 Instance1

… …

Instancen Instancen

Labelled data Unlabelled data

6
 Antoine PALISSON

Usages
Unsupervised methods have many applications thanks to its ability to analyze
the data in order to discover new patterns and useful information:
● Customer analysis and recommender systems
● Data categorization, also known as clustering
○ News, articles, products …
● Abnormal instances (outliers …) detection
○ Frauds, defects …
● Object recognition in computer vision
○ Medical analysis …

7
 Types
At least four main types of Unsupervised Learning methods exist:
● Anomaly Detection
● Association Rules
● Clustering
● Dimensionality Reduction

Antoine PALISSON 8
 Anomaly Detection
Anomaly detection, also known as Novelty detection, methods are trying to
find outliers in the data. An outlier can be seen as a rare or isolated instance
that differs significantly from the remainder of the data.
This type of unsupervised algorithms it widely used in fraud detection (credit
card frauds …), defect detection (defect on a production line …), medical
diagnosis (radiology image analysis …), cyber security (intrusion detection …)
and so on.

Antoine PALISSON 9
 Antoine PALISSON

Anomaly Detection (2)

The anomaly detection method field is broad as it can be done using statistical
methods, density-based unsupervised methods, probabilistic methods, data
encodings with neural networks …

anomaly

data

10
 Association Rules
Association Rules methods are trying to find relations between the features.
These relations can be seen as a set of interesting rules that determine how
and why certain features are linked.
Such methods are generally used in sale and customer analyses in order to find
associations between the products. For example, it allows retailers to identify
relationships between the items that their customer buy together frequently.

Antoine PALISSON 11
 Antoine PALISSON

Association Rules (2)

Many algorithms for generating association rules have been proposed. They
generally use the most frequent sets (ex: the most frequent set of products
purchased together) to find the next most promising frequent sets.
Association rules are well described by Venn diagrams:

Sets
Set X Set Y
X&Y

12
 Clustering
Cluster methods are trying to create groups of similar instances based of the
features. Each instance of a dataset is assigned to a group without knowing its
label (its “True” group).
This type of unsupervised algorithms it widely used to segment customer
databases, medicine, web search and as a tool for other machine/deep learning
algorithms.

Antoine PALISSON 13
 Antoine PALISSON

Clustering (2)
Clustering algorithms are generally divided into four main categories based on:
● Connectivity - it groups the data points that are close from each other
● Centroid - it groups the data points around a center point
● Distribution - it groups the data points that appear to belong to the
same probabilistic distribution
● Density - it groups the data points that belong to a high density area
and treats the other points as outliers

14
 Antoine PALISSON

Clustering (3)

15
 Dimensionality Reduction
Dimensionality Reduction methods are transforming data from a high
dimensional space to a lower one while keeping as much information as
possible. In short, it reduces the number of features.
This method is mostly used to visualize data or as a tool for other
machine/deep learning model because it reduces the curse of dimensionality
effect and thus helps to improve the model performances.

Antoine PALISSON 16
 Antoine PALISSON

Dimensionality Reduction (2)

Dimensionality reduction algorithm are either using a feature selection or a
feature projection method.
The feature selection method involves metrics that measures the impact of
addition or deletion of a feature. It keeps the other features untouched.
On the contrary, the feature extraction method is generally replacing the entire
set of feature with a smaller one obtained by projection on a lower dimensional
space.

3D 2D 17
 02
Dimensionality
Reduction
18
 Antoine PALISSON

Usage
Dimensionality reduction is useful when the goal is to make the data more
manageable, improve the performance of machine learning algorithms, or gain
a better understanding of the underlying structure of the data.
In particular, when:
● The data has a lot of correlated or redundant features
● The data is hard to visualize because of its high dimensionality
● The number feature is slowing down the algorithm

19
 Antoine PALISSON

Curse of Dimensionality
Many machine learning project involves thousands or even millions of features.
This amount of features causes two problems:
● It slows down the training ;
● It may harm the performances because the dimensionality is too
large. This problem is also known as the curse of dimensionality.
The curse of dimensionality is not the only motive to use a dimensionality
reduction algorithm. It also used to visualize data to a 2D or a 3D space as we
will see in this chapter.

20
 Antoine PALISSON

Curse of Dimensionality (2)

The Curse of Dimensionality refers to the following problem:
When the dimensionality increases, the volume of the space increases so
fast that the available data become sparse.
Imagine you have a feature with two possible values: 0 or 1. Thus, two instances can cover
the range of possible values.
Letʼs add another feature with also two possible values: 0 or 1. Now, we need 4 instances to
cover the range of possible values: (0,0), (0,1), (1,0), (1,1).
With a 3rd one, there are 8 possible combinations, 16 with a 4th, 32 with a 5th and so on. With
30 features, there are more than a billion possible combinations and more than a million of
billion combinations with 50 features.
21
 Antoine PALISSON

Curse of Dimensionality (3)

A randomly selected point in a very high dimensional unit cube (hypercube)
has a probability of being very close to one of the border of this hypercube
close to 1 i.e. to be an outlier.

1D 2D 3D

Increasing distance between points 22

 Antoine PALISSON

Feature Projection
Feature projection is the most common type of method used by the
dimensionality reduction algorithms. It reduces the dimensionality of the
dataset by projecting the data into a lower dimensional space of the high
dimensional space.
This dimensionality reduction process comes with a cost: the loss of
information. Indeed, the lower is the subspace compared to the original
space, the higher is the loss of information.
For example, 3D data may not be homogeneously spread and thus lie close to a 2D plan. In
this case, the 3D data can be projected to this plan without losing too much information.

23
 Antoine PALISSON

Feature Projection (2)

24
 Antoine PALISSON

Feature Projection (3)

Two main type of feature projection exists:
● Linear Projections
○ PCA (Principal Component Analysis)
○ NMF (Non-negative Matrix Factorization)
● Non-Linear Projections, also known as Manifold Learning
○ MDS (Multidimensional Scaling)
○ Isometric Mapping
○ LLE (Locally Linear Embedding)
○ TSNE (t-distributed Stochastic Neighbor Embedding)
○ UMAP (Uniform Manifold Approximation and Projection)
25
Linear projection
techniques

26
 Antoine PALISSON

PCA
The Principal Component Analysis is the most popular dimensionality
reduction algorithm. It is two steps algorithm:
1. First, it finds the hyperplane that lies closest to the data
2. Then, it projects the data on this hyperplane
In order to find that hyperplane, we search for the axis that accounts for the
largest amount of variance: it is the 1st principal component.
Then, the 2nd principal component is the axis that is orthogonal to the 1st
principal component. The 3rd is the axis that is orthogonal to the plane formed
by the two first principal components. The 4th is orthogonal to the hyperplane
formed by the three first and so on.
27
 Antoine PALISSON

PCA (2)
PC1

PC2

PC1 PC2
Here is a GIF example: link. 28
 Antoine PALISSON

PCA & SVD

SVD

In order to find the principal components a matrix factorization technique can

be used, namely: the Singular Value Decomposition.
The SVD decomposes a matrix X into three matrices:
● a matrix, noted U, that contains the singular vectors of X that forms
an orthonormal basis for the columns of X
● a singular values matrix named 𝚺
● another singular vector matrix named V that forms an orthonormal
basis for the rows of X

29
 Antoine PALISSON

PCA & SVD (2)

SVD

Theses submatrices can then be used for a lot of tasks including data
compression, matrix completion, dimensionality reduction and, of course,
principal component analysis.

The VT is the transposed form of the

V matrix.

Source : Wikipedia

30
 Antoine PALISSON

PCA & SVD (3)

Truncated SVD

One of the main benefits of the SVD method is that it can be used to find a
low-rank estimation of a matrix.
By keeping only the first k singular values in the 𝚺 matrix and multiplying it to
the singular vector matrix U, we can obtain a rank k approximation of the initial
matrix. This process is called the Truncated SVD (TSVD) method.

𝚺k Removed
X Xsvd U singular
values

mxn mxk mxm mxk

31
 Antoine PALISSON

PCA & SVD (4)

PCA

From a PCA perspective, the V matrix contains principal directions/axes and the
U𝚺 matrix product contains the principal components.
PCA is very similar to the truncated SVD, there is one major difference: the data
must be centered before applying the SVD algorithm.

The mean
of the data
features
SVD method
Top-k
singular
values
32
 Antoine PALISSON

PCA & SVD (5)

Randomized SVD

There are two major problems with the SVD algorithm: it is very slow, with a
time complexity of O(n3), and is using a lot of memory for large data.
The speed problem can be solved using a randomized SVD. The basic idea is to
use random projections to reduce the dimensionality of the matrix before
applying the decomposition.
Randomized SVD is particularly useful when:
● The data is large and sparse
● The data has a lot of redundant and/or useless features

33
 Antoine PALISSON

PCA & SVD (6)

Incremental SVD

The memory problem can be solved using an incremental SVD, also known as
online SVD or dynamic SVD. It is an algorithm for updating the SVD of a matrix
as new data is added.
The key insight behind incremental SVD is that the SVD of a matrix can be
updated efficiently by adding or removing a single row or column from the
matrix, without having to recalculate the entire SVD.
It is particularly useful when:
● The data is large
● The data is updated frequently (e.g. recommender systems)

34
 Antoine PALISSON

PCA & SVD (7)

SVD variants

Both randomized and incremental SVD methods are approximation of the

SVD. There are pros and cons to their implementation.
Randomized SVD is faster than SVD, with a time complexity of O(n2k + nk2), but
the quality of the approximate SVD depends on the number of random
projection used and degrades as the number of retained singular values
decreases.
Incremental SVD makes better usage of the memory but the quality of the
approximate SVD degrades over time as the number of updates increases.

35
 Antoine PALISSON

Kernel PCA
Kernel PCA is a non-linear extension of PCA that allows for the computation
of principal components in a higher dimensional feature space without actually
having to perform the computations in that space.
A kernel function is a mathematical function that is used to compute the dot
product between two data points in a higher-dimensional feature space,
even though the data points are not explicitly represented in that space.
Different kernels can be used: linear, polynomial, gaussian radial basis (RBF) or
sigmoid. The choice of the kernel type has a big impact on the results.
Additionally, the Kernel PCA is computationally more expensive than PCA.

36
 Antoine PALISSON

PCA & SVD (8)

Pros & Cons

Pros Cons
● Does not always find patterns and trends
Truncated SVD ● Robust to noise and outliers ● Restricted to linear data
● Not scalable
● Can be sensible to noise and outliers
PCA (with SVD) ● Finds patterns and trends ● Restricted to linear data
● Not scalable
● Not as accurate as PCA
Randomized PCA ● Faster than PCA on large datasets ● Can be sensible to noise and outliers
● Restricted to linear data
● Faster than PCA on datasets that are ● Not as accurate as PCA
Incremental PCA updated frequently ● Can be sensible to noise and outliers
● Better memory usage ● Restricted to linear data
● Slower than PCA
● Can be sensible to noise and outliers
Kernel PCA ● Works with nonlinear data
● Very sensitive to the choice of the width
parameter
37
 Antoine PALISSON

NMF
NMF (Non-Negative Matrix Factorization) is a group of algorithms that
decompose a given matrix into two non-negative matrices.
The basic idea behind NMF is to approximate the original matrix X as a product
of two non-negative matrices, W and H, such that X ≈ WH. The matrix W is often
referred to as the "dictionary" or "basis" matrix and contains the basis vectors
that make up the lower-dimensional representation of the data.

Source : GeeksforGeeks
38
 Antoine PALISSON

NMF (2)
NMF can be used for dimensionality reduction by choosing a smaller number
of columns in the basis matrix W.
NMF is not restricted to dimensionality reduction and is particularly useful for
cases where the input data has non-negative values, such as :
● text data (topic modeling …)
● image data (image compression …)
● audio data (feature extraction …)

39
 Antoine PALISSON

PCA or NMF ?
Pros Cons Usages
● Faster and more scalable than
● Assumes that the data follows
NMF PCA is widely used for data
a Gaussian distribution.
PCA ● Good for visualization, data
● Sensitive to outliers
compression, feature extraction,
compression, and feature and visualization in various fields.
● Data need to be centered
extraction
● Good to discover the ● May not be suitable for data
underlying patterns or with negative values or
NMF is widely used in text mining
structures in the data, even if extreme outliers.
and image processing to extract
they are non-linear or highly ● Requires careful tuning of the
NMF correlated. regularization parameters to
informative and interpretable
features from high-dimensional
● Can be regularized to reduce avoid overfitting or underfitting.
data.
overfitting and improve ● NMF is slower and less
generalization. scalable than PCA.

40
Nonlinear projection
techniques

41
 Antoine PALISSON

Manifold Learning
Nonlinear projection techniques, also known as manifold learning, is a
technique used to explore and analyze complex, high-dimensional data by
identifying a low-dimensional structure that the data lies on.
The idea behind manifold learning is that many high-dimensional datasets
have a lower-dimensional structure that is hidden or "folded" within the
data.
By identifying this structure, we can reduce the dimensionality of the data
while retaining important information and structure.

42
 Antoine PALISSON

MDS
Multidimensional scaling (MDS) is a technique for dimensionality reduction
that creates a low-dimensional representation of a dataset that preserves the
pairwise distances or dissimilarities between the instances.
There are two main types of MDS:
● Metric MDS - It is used when the dissimilarities are based on actual
distances.
● Non-metric MDS - It is used when the dissimilarities are based on
non-metric information. It keeps the order of the distances.
MDS is commonly used in combination with other dimensionality reduction
techniques, such as Isomap.
43
 Antoine PALISSON

Isometric Mapping
One of the earliest approaches to manifold learning is the Isomap algorithm.
It is used for dimensionality reduction by creating a low-dimensional representation
of the data that preserves the geodesic distances (curvy distances) between the
instances. These geodesic distances are then used to create a weighted graph of
the data instances, also known as a neighborhood graph, where the weights on the
edges represent the distances between the instances.
Once the graph is constructed, Isomap applies the MDS technique to find a
lower-dimensional representation of the data that preserves the pairwise distances
as much as possible.
Isomap is a computationally expensive method compared to other dimensionality
reduction methods.
44
 Antoine PALISSON

LLE
Locally Linear Embedding (LLE) finds a lower-dimensional representation of
the data such that each instance in the low-dimensional space is a linear
combination of its closest neighbors in the high-dimensional space.
This ensures that the local structure of the data is preserved while reducing the
dimensionality of the data.
LLE is sensitive to the choice of the number of nearest neighbors and may
produce a poor result if that number is too low or too high.

45
 Antoine PALISSON

t-SNE
t-Distributed Stochastic Neighbor Embedding (t-SNE) is a technique that is
particularly effective at visualizing high-dimensional data.
The basic idea behind t-SNE is to construct a probability distribution over pairs
of high-dimensional data instances so that similar instances have a high
probability of being chosen.
The technique constructs a probability distribution over the high-dimensional
data using a Gaussian kernel, and then constructs a similar probability
distribution over the low-dimensional data using a Student t-distribution.

46
 Antoine PALISSON

t-SNE (2)
Although extremely useful for visualizing high-dimensional data, t-SNE plots
can sometimes be mysterious or misleading. Here are some guidelines:
● Hyperparameters are very important
● Cluster sizes in a t-SNE plot mean nothing
● Distances between clusters might not mean anything
● Random noise doesnʼt always look random
● Shapes are not always meaningful
● Topological information can be misleading
● Different runs can lead to different results 47
 Antoine PALISSON

UMAP
Uniform Manifold Approximation and Projection (UMAP) is a dimensionality
reduction algorithm that is commonly used for visualizing high-dimensional
datasets.
UMAP uses a mathematical framework called Riemannian geometry to
preserve both global and local structure in the high-dimensional dataset. The
algorithm first constructs a fuzzy topological representation of the data, which
captures the relationships between data points in the high-dimensional space.
This representation is then optimized using a stochastic gradient descent
process, which seeks to minimize the discrepancy between the
high-dimensional relationships and their corresponding low-dimensional
relationships.
48
 Antoine PALISSON

Pros & Cons

Pros Cons

● Powerful technique for visualizing ● Computationally Expensive for large datasets

t-SNE high-dimensional data ● Difficult to interpret

● Good technique for visualizing high-dimensional

● Sensitive to the choice of parameters
UMAP data
● Does not perform well on noisy data
● Fast & scalable
● Sensitive to the choice of neighborhood size
● Does not perform well on noisy or high
LLE ● Fast
dimensional data
● Not suited for global structures
● Preserves global distances between instances ● Computationally Expensive for large datasets
MDS which is useful to analyze similarity or ● Does not perform well on noisy data
dissimilarity between instances ● Not suited for global structures
● Computationally Expensive for large datasets
● Can produce results that are interpretable and
IsoMap meaningful
● Does not perform well on noisy data
● Not suited for global structures

49
 03
Clustering

50
 Introduction
Clustering is a technique used to group similar data points together. The
goal of clustering is to partition a set of data points into distinct groups, called
clusters, such that data points within a cluster are more similar to each other
than to data points in other clusters.
Many algorithms have been developed since the mid 90ʼs involving the use of
some methods such as connectivity, centroid, distribution and density
clustering.

Antoine PALISSON 51
 Antoine PALISSON

Usages
Some of the main usages of clustering include:
● Market Segmentation - Clustering can be used to group customers
with similar characteristics
● Recommender systems - Clustering can be used to group similar
items, which can then be used to recommend items to users based on
their previous preferences.
● Image and speech recognition - Clustering can be used to group
similar patterns
● Natural Language Processing - Clustering can be used to group
similar documents or text segment
52
Centroid-based
Clustering

53
 Antoine PALISSON

Introduction
Centroid-based clustering is a method of clustering objects in which the
cluster is represented by the mean (centroid) of all the points in the cluster.
There are several centroid-based clustering methods, some of the most
commonly used ones include:
● K-means
● K-medians - a variant that uses the median instead of the mean
● K-medoids - a variant that uses an instance as a centroid instead of
the mean
● Fuzzy c-means - a variant where instances can belong to
multiple clusters
54
 Antoine PALISSON

K-Means
K-means is a widely used centroid-based clustering algorithm that partitions a
dataset into k clusters, where each cluster is represented by its centroid,
which is the mean of all the points in the cluster. The algorithm proceeds in
two steps:
● Initialization: K cluster centroids are chosen from the data points.
● Iteration: Each instance is reassigned to the cluster whose centroid is
closest to it, and then recomputes the centroids as the mean of all the
points in the cluster. This process is repeated until the assignment of
points to clusters no longer changes or a maximum number of
iterations is reached.
55
 Antoine PALISSON

K-Means (2)
Initialization

The k-means algorithm is sensitive to the initial placement of centroids.

There are two main methods to initialize the centroids :
● In the traditional k-means algorithm, the initial cluster centroids are
chosen randomly from the instances.
● In the improved method called k-means++, the first cluster centroid is
chosen randomly and then for each iteration, the next centroid is
chosen to be the instance that is furthest away from the centroids
that have already been chosen.

56
 Antoine PALISSON

K-Means (3)
Iteration

The iteration step of the k-means algorithm is done in two steps:

● Assignment step - each instance is assigned to the cluster whose
centroid is closest to it. This assignment is typically done using Euclidean
distance, which is a measure of the distance between two points in a
multidimensional space.
● Update step - once all the instances have been assigned to a cluster, the
centroid of each cluster is recomputed as the mean of all the points in
the cluster. The mean is calculated for each dimension separately.
The algorithm converges when the assignment of points to clusters no longer
changes, which means that the centroids are not moving anymore.

57
 Antoine PALISSON

K-Means (4)
Random initialization of
Assignment step n°1 Update step n°1 Assignment step n°2
3 clusters

58
 Antoine PALISSON

K-Means (5)
Pros and cons

Pros Cons
Ease of implementation
It is a good starting point for many clustering Sensitivity to initial centroids
problems.
Efficiency
Assume spherical clusters
The linkage criterion can produce different
Not all real-world data can be clusterized in
clustering results depending on the
spherical and equally sized clusters.
characteristics of the data.
Number of cluster is a parameter
Scalability & Efficiency
The number of cluster must be specified as a
It is computationally efficient and it can handle
parameter. The perfect number of cluster is
large datasets and high-dimensional spaces.
generally not known is advance.
Interpretability
Each cluster is represented by its centroid, Not good with categorical data
which is the mean of all the points in the The mean of categorical data is not relevant.
cluster.
Not good with outliers
these can skew the centroid and affect the
clusters 59
 Antoine PALISSON

K-Means (6)
Non-Spherical Clusters

To address the issue of non-spherical clusters, other centroid-based clustering

methods such as k-medoids and especially fuzzy c-means can be used.
The fuzzy c-means algorithm proceeds in two steps:
● Membership assignment - The membership value of each instance to
each cluster is calculated using a membership function such as a
Gaussian function. The membership value of an instance to a cluster
represents the degree of similarity between that instance and the
cluster centroid.
● Centroid update: The cluster centroids are updated as the
weighted mean of all the data points, where the weight of each
data point is its membership value to the cluster. 60
 Antoine PALISSON

K-Means (7)
Number of clusters

To address the issue of not knowing the number of clusters, a few techniques
can be used:
● Elbow method - a simple graphical method
● Silhouette analysis - a similarity measure
● Calinski-Harabasz index - an inter-cluster/intra-cluster variance ratio
Ultimately, other clustering methods such as hierarchical clustering or
density-based clustering can be used to solve this issue.

61
 Antoine PALISSON

Elbow Method
The elbow method involves fitting the k-means algorithm for different values of
k and plotting the sum of squared distances between the instances and their
respective cluster centroid against k.
The number of clusters that corresponds to the "elbow" point on the plot,
where the within-cluster sum of squares begins to decrease at a slower rate, is
considered the correct number of clusters.

62
 Antoine PALISSON

Elbow Method (2)

Sum of squared
distances of samples
to their closest cluster
center
K=3

Values of K
63
 Antoine PALISSON

Silhouette Score
The silhouette analysis involves calculating the silhouette score for each
instance, which measures the similarity of an instance to its own cluster
compared to other clusters. It is composed of two elements :
● The average distance between an instance i and all other instances in
the same cluster, denoted as a(i)
● The minimum of the average distance between an instance i and all
other instances in the nearest different cluster, denoted as b(i)

with I the cluster of instance i and J a different cluster, CI and CJ the number of
instances in clusters I and J and d(i,j) the distance between instances i and j. 64
 Antoine PALISSON

Silhouette Score (2)

The silhouette score for each instance i can be computed as follows:

The silhouette score for each cluster is the average of all its instance
silhouette scores s(i):

65
 Antoine PALISSON

Silhouette Score (3)

The silhouette score ranges from -1 to 1:
● a high score (close to 1) indicates that the data point is well-matched
to its own cluster
● a score close to 0 indicates overlapping clusters.
● a low score (close to -1) indicates that the data point is poorly
matched to its own cluster
The correct number of clusters is typically chosen as the number of clusters
that results in the highest average silhouette score.
Additionally, it is a good idea to search for even clusters when two
silhouette scores are close. 66
 Antoine PALISSON

Calinski Harabasz
The Calinski-Harabasz index, also known as the Variance Ratio Criterion, is a
method for evaluating the quality of clustering solutions and estimating the
correct number of clusters in a k-means algorithm.
It compares the ratio of the between-cluster variance to the within-cluster
variance for different values of k. The correct number of clusters is chosen as
the number of clusters that maximizes this ratio.
Inter-cluster variance

Number of instances

Number of clusters Intra-cluster variance 67

 Antoine PALISSON

K-Means (8)
Categorical data and Outliers

To address the issue of categorical data, other clustering methods such as

k-modes or k-prototypes can be used. k-modes uses mode instead of mean for
categorical data and k-prototypes uses a combination of mode and mean for
mixed data.
Finally, to address the issue of outliers, robust versions of the k-means
algorithm such as k-medians or k-MAD can be used. k-medians uses the
median instead of the mean, which is more robust to outliers, and k-MAD uses
the median absolute deviation.

The median 68
 Antoine PALISSON

Elkan
The Elkan algorithm is a variation of the traditional algorithm (Llyod) that
improves the efficiency of the k-means method.
It uses a more sophisticated method for computing the distance between a
data point and a centroid. It is based on the triangle inequality, which states
that the distance between two points is always shorter or equal to the sum of
the distances between these points and a third point.
While the Lloyd algorithm uses the standard Euclidean distance, the Elkan
algorithm uses a lower bound on the Euclidean distance, which allows it to skip
certain distance calculations and reduce the overall computational cost.

69
Connectivity-based
Clustering

70
 Antoine PALISSON

Introduction
Connectivity-based clustering, also known as hierarchical clustering, is based
on the core idea of objects being more related to nearby objects than to objects
farther away.
There are two main approaches:
● Bottom-up - In this method, all instances start with their own cluster
which are gradually merged during the next steps.
● Top-down - In this method, all instances are inside one big cluster
which is gradually divided during the next steps.
The top-down approach works best when there are fewer, but larger clusters.
The bottom-up approach works best when there are many smaller clusters.
71
 Antoine PALISSON

Method
In order to determine the similarity between data instances and the distance
between the clusters a linkage criteria is used as well as a distance metric.
Most of the time, the euclidean distance is used but others such as the
Manhattan, Minkowski or the Hamming distances can be used.
There are four main linkage criterion:
● Single linkage
● Complete linkage
● Average linkage
● Ward linkage
72
 Antoine PALISSON

Method (2)
Single Linkage

The single linkage criteria is searching for the closest pair of points to merge
or split two clusters.

of points
Closest pair

73
 Antoine PALISSON

Method (3)
Complete Linkage

The complete linkage criteria is searching for the farthest pair of points to
merge or split two clusters.

ts
f p oin
ro
pai
est
Farth

74
 Antoine PALISSON

Method (4)
Average/median Linkage

The average or median linkage criteria is searching to minimize the average

or median distance of all the pair of points to merge or split two clusters.

Average or median distance

between points

75
 Antoine PALISSON

Method (5)
Ward Linkage

The ward linkage criteria is considering the union of every possible cluster pair
and is trying to minimize the variance of the distances between the new
clusters and their centroids.
Let's say you have two clusters of data points, A and B. The Ward distance
between A and B is obtained by adding the variances of A and B and
subtracting the variance of AB (AB is the merger of A and B).
Variance of AB

Variance of A

Variance
of B
76
 Antoine PALISSON

Dendrograms
During the process, a dendrogram is built, which is a tree-like diagram that
shows the hierarchical structure of the clusters. Each leaf of the dendrogram
represents an instance, and each node represents a cluster.
The linkage criterion used is represented by the height of the node; the higher
the node, the more dissimilar the two clusters are.

A node / cluster

Linkage criterion
An instance

77
 Antoine PALISSON

Dendrograms (2)
It is possible to cut the dendrogram to create a flat clustering based on the
desired number of clusters or a threshold of similarity.

Three clusters
(yellow, green and red)

78
 Antoine PALISSON

Pros and cons

Pros Cons
Interpretability Computational complexity
The dendrogram makes it easy to visualize It is computationally expensive for large
and interpret the clustering results. datasets.

Flexibility
Scale sensitivity
The linkage criterion can produce different
Some linkage criteria such as ward linkage are
clustering results depending on the
sensitive to the scale of the data.
characteristics of the data.

Difficulty to determine the clusters

Outlier handling One way to determine the number of clusters
The ward linkage is not sensitive to the is to cut the dendrogram at a certain height,
outliers. but this can be subjective and may not always
produce the desired results.

Robustness
The results of hierarchical clustering depend on the initial ordering of the data points and linkage
criterion used, which may lead to different results in different runs. However, performing multiple runs
of the algorithm with different initial orderings or linkage criteria can produce a more robust
clustering.
79
 Antoine PALISSON

BIRCH
BIRCH stands for Balanced Iterative Reducing and Clustering using Hierarchies. It
uses a Cluster Feature tree (CF) to incrementally build a hierarchical clustering
structure.
In BIRCH, a CF Tree is constructed incrementally as the data is processed. The
instances are added to the tree one at a time, and each time a new instance is
added, the tree is updated to reflect the new information.
This allows BIRCH to efficiently handle large and dynamic data sets, without
having to store all the data in memory.

80
 Antoine PALISSON

BIRCH (2)
Cluster Feature Tree

A Cluster Feature Tree is a tree-based data structure used in the process of Cluster
Feature extraction. It provides a compact representation of the cluster's
characteristics, and can be thought of as a summary or an aggregate of the
features of the instances in the cluster. In practice, the feature vector is often
computed as the mean or the sum of the features of the instances in the cluster.

Root cluster

Intermediate
clusters

Final clusters

81
 Antoine PALISSON

BIRCH (3)
Algorithm

The algorithm initializes the CF Trees with a threshold T that determines the
maximum size of a cluster, and is used to control the granularity of the clustering.
Then, it finds the leaf node in the CF Tree that is closest to each instance:
● If the size of that leaf node is less than T, the instance is added
● Else, two new leaves are created by splitting the old one
Generally, the CF tree also has a certain maximum size that cannot be exceeded. If
reached, the closest leaves of the tree will be merged.

When the CF tree is completed, the final clustering step occurs. It generally
uses other clustering technique such as k-means or hierarchical clustering to
group the clusters of the CF tree until a final number of cluster is reached.
82
 Antoine PALISSON

BIRCH (4)
Final Clustering

Without final clustering With final clustering 83

 Antoine PALISSON

BIRCH (5)
Pros & cons

Pros Cons
Scalability Parameter sensitivity
It is designed to handle large datasets It relies on the choice of the threshold
efficiently and can process millions of data parameter to control the granularity of the
points in a reasonable amount of time. clusters. An ill-defined threshold parameter
may result in over-clusterization.

Robustness Spherical clusters

It is robust to the presence of noise and It can only produce spherical clusters.
outliers.

Dynamic Clustering High-Dimensional Data

It can adjust the granularity of the clustering It may perform poorly for high-dimensional
results. data.

Incremental and Online Memory usage

It can easily update its state with the new It may require more computational resources
instances. than simpler clustering algorithms, especially
for large data sets.
84
Distribution-based
Clustering

85
 Introduction
Distribution-based clustering methods are a class of clustering techniques
that attempt to model the underlying probability distributions of the data
points in a dataset.
These methods are based on the assumption that data points in a cluster are
generated by a specific probability distribution, such as a Gaussian
distribution. These methods are particularly useful for datasets that have a
complex structure.
One prominent method is the Gaussian Mixture.

Antoine PALISSON 86
 Antoine PALISSON

Gaussian Mixture
Gaussian Mixture Models (GMM) is a probabilistic model that assumes that the
instances in a cluster are generated by a Gaussian distribution.
The GMM method estimates the parameters of the Gaussian distributions,
such as the mean and covariance matrix, and uses these parameters to assign
instances to clusters.
The probability density function (PDF) of a Gaussian distribution is defined by
its mean and covariance matrix. The mean is a vector that gives the location of
the distribution, and the covariance matrix describes the shape of the
distribution.

87
 Antoine PALISSON

Gaussian Mixture (2)

Different shape & density
Spherical covariance Diagonal covariance Full covariance

𝜎2 0 0 𝜎 x2 0 0 𝜎 x2 cov xy cov xz

0 𝜎2 0 0 𝜎 y2 0 cov yx 𝜎 y2 cov yz

0 0 𝜎2 0 0 𝜎 z2 cov zx cov zy 𝜎 z2 88
 Antoine PALISSON

Gaussian Mixture (3)

Algorithm

The GMM algorithm works by iteratively finding the maximum likelihood

estimates of the parameters of the Gaussian distributions and the mixing
coefficients.
The mixing coefficients represent the proportion of instances that belong to
each cluster, and are also known as the cluster weights.
The Expectation-Maximization algorithm is often used to estimate the
parameters of the Gaussian distributions and the mixing coefficients. The
Expectation-Maximization algorithm consists of two steps:
● Expectation step
● Maximization step
89
 Gaussian Mixture (3)
Expectation-Maximization

In the Expectation step, the algorithm computes the probability of each

instance belonging to each cluster, given the current estimates of the
parameters: the expected value of the log-likelihood.
In the Maximization step, the algorithm updates the estimates of the
parameters based on these probabilities and the current estimates of the
parameters using numerical optimization techniques such as gradient ascent
or the Newton-Raphson method.

Antoine PALISSON 90
 Antoine PALISSON

Likelihood
The parameters of the model (mean and covariance) can be estimated using
maximum likelihood estimation (MLE), which involves finding the parameters
that maximize the likelihood function.
In a Gaussian distribution model, the likelihood is a mathematical function that
calculates the probability of obtaining the observed data given the
parameters of the model. The likelihood function for a Gaussian model is
given by: Number of instances

Mean of the gaussian

distribution

Variance of the
gaussian distribution An instance 91
 Antoine PALISSON

Gaussian Mixture (4)

Pros & Cons

Pros Cons
Flexibility
Initial Conditions
It can model clusters with different shapes and
It is sensitive to initial conditions.
densities

Soft Clustering Normality

It can assign a probability of each data point to Not all real-world data follow gaussian
each cluster distributions.

Number of cluster
Handling Missing Data
The number of cluster must be specified as a
It can handle missing data by computing the
parameter. The perfect number of cluster is
likelihood of the data given the missing values.
generally not known is advance.

Speed High Dimensionality

It is relatively fast compared to other methods The covariance matrix becomes difficult to
for large datasets. estimate in high dimensionality.

92
 Antoine PALISSON

Gaussian Mixture (5)

Initial Conditions

To mitigate the issue of sensitivity to initial conditions, multiple runs of the

algorithm with different initial conditions can be performed.
Additionally, different initialization methods can be used such as the traditional
k-means or the k-means++. It applies a K-mean algorithm to find clusters
before starting the Expectation Maximization algorithm.
However, this can be computationally expensive compared to other
initialization methods.

93
 Antoine PALISSON

Gaussian Mixture (6)

Number of clusters

To determine the number of clusters, the elbow, silhouette and

calinski-harabasz methods can be used. Additionally, statistics using the log
likelihood can be used such as the Akaike and the Bayesian Information
Criteria (AIC & BIC) or the GAP statistics.
AIC compares the likelihood of the data under the k-means model for different
values of k with the number of parameters (k) in the model.
BIC is similar to AIC but it's more conservative than AIC, it penalizes models
that have more parameters, in this case the number of clusters.

n is the number of instances / k is the number of clusters / L is the likelihood 94

 Antoine PALISSON

Gaussian Mixture (7)

Other solutions

If the data does not follow a Gaussian distribution, one solution is to use a
different probability density function or to transform the data such as the
logarithm transformation.
To handle high-dimensional data, one solution is to use dimensionality
reduction techniques such as principal component analysis.

95
Density-based
Clustering

96
 Introduction
Density-based clustering methods are a class of unsupervised machine
learning techniques that group similar data points together based on the
density of points in a given area.
The main idea behind density-based clustering is that a cluster is a dense
region of points that is separated from other dense regions by areas of lower
point density.
These methods are typically used to identify clusters of arbitrary shapes, as
opposed to the spherical clusters produced by other methods such as k-means.

Antoine PALISSON 97
 Methods
The most widely used density-based clustering methods are:

● DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

● OPTICS (Ordering Points To Identify the Clustering Structure)
● Mean Shift

Antoine PALISSON 98
 DBSCAN
DBSCAN, or Density-Based Spatial Clustering of Applications with Noise, is a
density-based clustering algorithm that groups together instances that are closely
packed together i.e. instances with many nearby neighbors. It marks as outliers the
instances that are alone in low-density regions.
DBSCAN requires two parameters:

● the radius is used to define the neighborhood around each point.

● the number of points is used to define the minimum number of points
required to form a dense region.

Antoine PALISSON 99
 Antoine PALISSON

DBSCAN (2)
1. Select an instance 2. Add its neighbors
A cluster is created if there to the cluster
are enough neighbors

3. Repeat

100
 Antoine PALISSON

DBSCAN (3)

Clusters

Isolated instance
too far from the
other instances

101
 Antoine PALISSON

DBSCAN (4)
Pros & Cons

Pros Cons
Parameters
The perfect number of cluster is found by DBSCAN given the radius and the min number of
instances. However, the radius and the minimum number of points must be chosen.

Flexibility Variability in density

It can model clusters with different shapes and It may not be suitable for datasets with high
densities variance in densities.

Efficient
It can handle large datasets.
Metric Sensitivity
The metric used may affect the performances.
Initial points
It is not sensitive to initialization.

102
 Antoine PALISSON

DBSCAN (5)
Parameters sensitivity

17 clusters
~50% of noise

Tuned parameters “Default” parameters 103

 Antoine PALISSON

DBSCAN (6)
Solutions

To overcome the difficulty in choosing the parameters, grid search or other

parameter tuning techniques can be used to select the best parameters for a specific
dataset.
To handle datasets with highly varying densities, algorithms like HDBSCAN
(Hierarchical DBSCAN) can be used, which do not require the user to specify a fixed
density threshold.
To overcome the sensitivity to the distance metric, different distance metrics or
distance-based similarity measures can be tried out.

104
 Antoine PALISSON

HDBSCAN
Hierarchical DBSCAN (HDBSCAN) is a variation of the DBSCAN algorithm that can
handle datasets with varying densities. HDBSCAN is a density-based clustering
algorithm that uses a hierarchical approach to form clusters. HDBSCAN works as
followed:
1. It starts by using a modified version of DBSCAN to form clusters at a low
density threshold.
2. Then, it increases the density threshold and forms new clusters by
merging the existing clusters.
3. This process continues until all the clusters have been merged into a
single cluster.
The result is a hierarchical tree of clusters, where each level of the tree corresponds
to a different density threshold. 105
 OPTICS
OPTICS (Ordering Points To Identify the Clustering Structure) is a density-based
clustering algorithm that extends DBSCAN by building a density-based
hierarchical clustering ordering.
The main difference between OPTICS and DBSCAN is that OPTICS maintains a list of
ordered instances, called the reachability-distance ordering, which captures the
clustering structure of the data.
The reachability distance measures the distance between an instance and its
nearest neighbor that has a higher density. Instances with high density will have a
smaller reachability distance than instances with low density.

Antoine PALISSON 106

 Antoine PALISSON

OPTICS (2)
The algorithm works as follow:
1. Initialization of the reachability distances
2. Find core instances: Check if the current point is a core point i.e. it has at least
MinPts neighbors within a radius of ε.
3. Update reachability distances:
a. Update the reachability distance of each neighboring instances of the core
instances based on the maximum of the core distance (the smallest
distance with its neighboring instances) of the current instance and the
distance between the current instance and the neighboring instance.
b. Check if the new reachability distance is smaller than its current
reachability distance. If there was no previous reachability distance, the
neighboring instance is added to the core instances list.
107
 Antoine PALISSON

OPTICS (3)
Then the cluster can be extracted from from the ordered list by finding regions of
instances with low reachability distances. These regions indicate the core of a
cluster, and points with high reachability distances are on the edges of the cluster.

Source : Wikipedia 108

 Antoine PALISSON

OPTICS (4)
Pros & Cons

Pros Cons
Flexibility Density sensitivity
It can model clusters with different shapes and It may not be suitable for datasets with highly
densities varying densities.

Parameters
Metric Sensitivity
Number of cluster and density thresholds are
The distance metric used to compute the
not parameters. The minimum number of
reachability distances will affect the result.
instances per cluster still need to be tuned.

Initialization Number of cluster

It is not sensitive to the initial points. It may produce a large number of clusters.

Efficiency
It can handle large datasets but it is generally less efficient than DBSCAN.

109
 OPTICS vs DBSCAN
DBSCAN is considered to be more efficient in terms of computational time and
memory because it only needs to calculate the distances between the points and
their neighbors once, and only needs to store the clusters and the noise points.
Indeed, OPTICS is less efficient in terms of computational time because it builds a
hierarchical clustering ordering of the data points.
However, OPTICS is more flexible than DBSCAN in terms of clustering and can
handle datasets with varying densities.

Antoine PALISSON 110

 Antoine PALISSON

Mean Shift
Mean Shift is a non-parametric density-based (and centroid-based) clustering
algorithm. It aims to find the peak of a probability density function by iteratively
shifting points towards areas of higher density until convergence.
It is used in computer vision and image processing for object tracking,
segmentation, and feature detection.
Unlike traditional clustering algorithms, Mean Shift does not require prior
knowledge of the number of clusters and it can handle data of any shape.

111
 Antoine PALISSON

Mean Shift (2)

Algorithm

1. Select a kernel function such as the Gaussian kernel (RBF) and a bandwidth parameter.
2. For each instance:
2.1. Define a region around the instance thanks to the bandwidth parameter. The window is a
region around the point, within which the density will be estimated.
2.2. Calculate the mean of the density within the window.
2.3. Shift the instance towards the mean. This shift is performed iteratively until convergence.
3. For each instance:
3.1. Assign the instance to a cluster based on its final location. Instances that converge to the
same location are assigned to the same cluster.
4. Repeat the process for all instances until no further changes are made.

112
 Antoine PALISSON

Mean Shift (3)

Pros & Cons

Pros Cons

Complexity
It may not be suitable for large datasets.
Flexibility
It can model clusters with different shapes and Bandwidth
densities Choosing the appropriate bandwidth parameter
can be challenging and may require some
experimentation.

Local Optimum
It may get stuck at a local optimum when the
Non-parametric dataset has outliers and/or noise.
Number of cluster and shape of the clusters
are not parameters.
Initial Conditions
It is sensitive to initial conditions especially if the
data is noisy.

113
Side notes

114
 Antoine PALISSON

Clustering Guide
High feature High instance Cluster Number of Cluster
Interpretability
dimension dimension shape cluster density

Moderate
K-means Low sensitivity Spherical Medium Uneven High
sensitivity
Hierarchical Moderate
Low sensitivity Any High Uneven High
Clustering sensitivity

Birch Low sensitivity Low sensitivity Spherical High Even Low

Gaussian Memory
Low sensitivity Elliptical Few Uneven High
Mixture inefficiency *
Performances
DBSCAN Low sensitivity Any Medium Even Low
inefficiency
Performances Moderate
OPTICS Any High Even Low
inefficiency sensitivity
Time Time
Mean Shift Any High Even Low
inefficiency inefficiency
* when the covariance matrix type is full. If spherical or diagonal, the GM is moderately sensitive to the number of features.
115
 Antoine PALISSON

High Dimensionality
Due to the memory and time constraints, clustering large datasets can be
challenging. Some strategies can be used to solve this problem:
● Sampling - randomly sample a smaller subset of the data to work with,
then use the results to infer information about the larger dataset.
● Dimensionality Reduction - reduce the number of features in the dataset
to make it smaller and easier to process.
● Incremental Learning - use algorithms that can incrementally learn from
the data and update the clustering results in an online fashion such as
Birch or mini-batch k-means.
● Parallel Processing
116
 Antoine PALISSON

Mini-Batch K-means
Mini-batch K-means is a variant of the traditional K-means algorithm that is
designed to handle large datasets. Instead of processing all the instances at once, it
updates the cluster centroids after processing a randomly chosen subset of the
dataset.
In each iteration, it computes the mean of the instances assigned to each centroid,
which serves as a new estimate of the centroids. The updated centroids are a
weighted average of the previous centroids and the new instances, where the
weight depends on the number of instances in the current mini-batch and the
number of iterations already performed.
However, it may not always converge to the global optimum solution, since it
only considers a subset of the data at each iteration.
117
 Antoine PALISSON

Mini-Batch K-means (2)

First batch Second batch Third batch

118
 Antoine PALISSON

Other methods
Other clustering algorithms exist such as:
● Spectral Clustering - a graph-based clustering algorithm that uses a
similarity matrix to group the instances. It works well on datasets with
non-linearly separable clusters and is particularly useful when the number
of clusters is not known. It does not scale well with the number of instances.
● Affinity Propagation - it uses a “message passing” approach to cluster
instances based on the similarity between them. It does not scale well with
the number of instances.
● CURE (Clustering Using REpresentatives) - a Birch-like algorithm
that uses representative points to condense the data and reduce the
dimensionality of the problem. It handles non-linearly separable
clusters. 119
 04
Anomaly
Detection
120
 Antoine PALISSON

Introduction
Anomaly and novelty detection are techniques used to identify unusual patterns
or instances in data that do not conform to the expected behavior.
Anomaly detection is used in a wide range of applications, such as fraud detection,
network intrusion detection, and fault detection in industrial systems.
Anomalies and Novelties are both outliers:

● Anomaly detection assumes that there is a normal behavior and any

deviation from that is considered as an anomaly

● Novelty detection assumes that there is no prior knowledge of normal

behavior and the goal is to identify new and unknown patterns in the
data.
121
 Antoine PALISSON

Anomaly vs Novelty
Anomaly detection is used when we have a
clear idea of what is normal behavior,
while novelty detection is used when we
don't have a clear idea of what is normal
behavior and we want to find something
new and unusual in the data.

Novelties
These type of outliers
were not present in the
training instances

122
 Antoine PALISSON

Methods
There are several methods used to detect anomalies and novelties in data:
● Statistical methods - Interquartile Range, Z-score, PCA …
● Probabilistic methods - Gaussian mixture model, Kernel density estimator,
Elliptic Envelope …
● Distance-based methods - Mahalanobis …
● Neighbor-based methods - Local outlier factor, k-Nearest Neighbors,
Angle-Based Outlier Detection, Subspace outlier detection …
● Isolation methods - Isolation Forest …
● Domain-based methods - One-class SVM …

123
 Antoine PALISSON

Statistical methods
Statistical methods rely on the assumption that the normal data follows a
particular statistical distribution, and anomalies or novelties can be identified
based on deviations from this distribution.
Some of the most common statistical methods are:
● Z-Score
● Interquartile Range
● Dimensionality Reduction such as PCA

124
 Antoine PALISSON

Statistical methods (2)

Z-Score

The Z-score works as follows:

1. Calculate the mean (𝜇) and the standard deviation (𝜎) of the features.
2. For each instance x, calculate the Z-score : z = (x - 𝜇) / 𝜎
3. Anomalies are the values with a z-score greater than a threshold. For
“soft” anomalies, the threshold is 3 for the upper bound and -3 for the
lower bound. For “hard” anomalies, the threshold is -4/4.

0.1% of the values

of a unit normal
0.1% of the values of a unit distribution have a
normal distribution have a z-score higher than
z-score lower than 3 3

125
 Antoine PALISSON

Statistical methods (3)

IQR

The interquartile range (IQR) is the difference between the third (Q3) and the
first (Q1) quartiles: IQR = Q3 - Q1. The anomalies are the values that are more
than 1.5 times the IQR away from the first quartile and the third quartile.

Lower bound Upper bound

outliers outliers
126
 Antoine PALISSON

Statistical methods (4)

Dimensionality Reduction

Dimensionality reduction techniques can be used to detect anomalies and novelties

by projecting high-dimensional data onto a lower-dimensional space in order to
identify patterns and structures in the data that may not be easily visible in the
original high-dimensional space.
Any linear or nonlinear projection techniques that have a method to compute the
inverse transformation such as PCA can be used to find outliers in the data by
computing the reconstruction error.
Reconstruction error is the difference between the original data and its
reconstruction from a compressed representation. In anomaly detection,
instances with high reconstruction errors are considered anomalies, as
they deviate significantly from the learned patterns in the data.
127
 Antoine PALISSON

Statistical methods (5)

Reconstruction Error
Original data Error = |Original data - Reconstructed data|

Dimensionality
Reduction

Low feature
space
Reconstruction
Outliers with high
Error Histogram reconstruction error
Reconstruction

…
Reconstructed data

128
 Antoine PALISSON

Probabilistic methods
Probabilistic methods rely on the assumption that the normal data follows a
particular probability distribution, and anomalies or novelties can be identified
based on their low probability under the model.
Some of the most common statistical methods are:
● Gaussian mixture model (GMM) method
● Kernel density estimator (KDE) method
● Elliptic Envelope method

Probabilistic methods are well-suited for novelty detection because they

can model the probability distribution of the normal data and identify
novelties based on their low probability under the model. 129
 Antoine PALISSON

Probabilistic methods (2)

Clustering - Gaussian Mixture Model

This figure shows the Gaussian

Mixture Log Likelihood boundaries
obtained after clustering the data.

Log- Likelihood
Regions with very high log-likelihood
can be considered as inliers, whereas
regions with very low log-likelihood
can be considered as outliers.

GMM is not the only clustering algorithm that

can be used to find anomalies. Density based
algorithm such as DBSCAN can also be used
to find anomalies.
130
 Antoine PALISSON

Elliptic Envelope
The Elliptic Envelope algorithm is a density-based algorithm that models the
distribution of the data, and any point that falls outside of this distribution is
considered an anomaly.
The main idea behind the Elliptic Envelope algorithm is that anomalies are more
likely to be located in regions of the data that have a low density.
The algorithm is based on the assumption that the data is Gaussian distributed,
and thus, it models the distribution of the data using an ellipse.

131
 Antoine PALISSON

Elliptic Envelope (2)

Outliers
(outside of
the ellipse) Ellipse of a
Gaussian
Distribution

132
 Antoine PALISSON

Elliptic Envelope (3)

Algorithm

The algorithm works by fitting an ellipse to the data, where the ellipse is defined
by the mean and the covariance of the data. Once the ellipse is defined, any point
that falls outside of the ellipse is considered an anomaly.

1. Find the Gaussian Distribution parameters of the data:

1.1. Compute the mean vector
1.2. Compute the covariance matrix
2. Compute the inverse of the covariance matrix
3. For each instance compute the Mahalanobis distance, defined as:
distance = (x - mean) T * covariance -1 * (x - mean)
4. Identify instances with a Mahalanobis distance greater than a threshold as outliers
133
 Antoine PALISSON

Elliptic Envelope (4)

Confidence Intervals

134
 Antoine PALISSON

Distance methods
Distance-based methods rely rely on the assumption that anomalies or novelties
can be identified based on their distance to the normal data.
The most commonly used distance is the Mahalanobis distance. It is a distance
metric that takes into account the covariance structure of the data. In this approach,
the Mahalanobis distance between each instance and the mean of the normal data
is calculated, and instances with a high Mahalanobis distance are identified as
anomalies or novelties.

An instance

The location of the Gaussian The covariance of the

Distribution i.e. the mean Gaussian Distribution 135
 Antoine PALISSON

Neighbor methods
Neighbor-based methods rely on the assumption that anomalies or novelties are
instances that do not fit well with the remainder of the data, and thus, have a lower
similarity to their neighbors.
Some of the most common Neighbor-based methods are:
● k-Nearest Neighbors (k-NN) method
● Local Outlier Factor (LOF) method
● Angle-Based Outlier Detection (ABOD) method
● Subspace outlier detection (SOD) method

136
 Antoine PALISSON

k-Nearest Neighbors
k-Nearest Neighbors (k-NN) is a non-parametric machine learning algorithm that
works by finding the k-nearest neighbors to a given instance. The distance to the
k-nearest neighbors is then used as a measure of the instance's normality.
The k-NN algorithm works as follow:
1. Calculate the distance between the current instance and all the other
instances in the dataset.
2. Sort the distances in ascending order and select the k-nearest neighbors to
the current instance.
3. Calculate a score (the inverse of the average distance to the k-nearest
neighbors or the simply distance to the kth nearest neighbor) that
reflects the degree of abnormality of the instance.
4. Use a threshold to find the anomalies. 137
 Antoine PALISSON

k-Nearest Neighbors (2)

3-Nearest Neighbors

This instance has

very close neighbors
This instance has
compare to the blue
very far neighbors
ones : it is an normal
compare to the blue
instance.
ones : it is an
anomaly.

138
 Antoine PALISSON

Local Outlier Factor

Local Outlier Factor (LOF) is a density-based algorithm that calculates the density
of a point compared to its neighbors, and any point that has a significantly lower
density than its neighbors is considered an anomaly.
The main idea behind the LOF algorithm is that anomalies are more likely to have a
lower density than their neighbors. The algorithm is based on the assumption that
anomalies are located in low-density regions of the data, while normal
observations tend to be located in high-density regions.

139
 Antoine PALISSON

Local Outlier Factor (2)

Instances in area
of low density
Areas of high
density

140
 Antoine PALISSON

Local Outlier Factor (3)

Simplified algorithm

The algorithm works by first identifying the k-nearest neighbors for each instance in
the data, where k is a user-specified parameter. The k-nearest neighbors are the k
instances that are closest to the current instance.
Then, for each instance, the algorithm calculates a local density score, which is
similar to the ratio of the instanceʼs k-distance (the distance to its kth nearest
neighbor) to the average k-distance of its k-nearest neighbors. Points with a low
local density score are considered to be anomalies.

141
 Antoine PALISSON

Local Outlier Factor (4)

Algorithm

1. for each instance P:

1.1. Find the k-nearest neighbors of P
1.2. for each k-nearest neighbors N of P:
1.2.1. Calculate the distance of P with respect to N, dist(P, N)
1.3. Set k_dist(P) to the maximum dist(P, N)
1.4. for each k-nearest neighbors N of P:
1.4.1. Calculate the reachability distance of P with respect to N, reach_dist(P, N)
reach_dist(P, N) = max(k_dist(P), dist(P, N))
1.5. Calculate the local reachability density of P:
lrd(P) = k / sum of the k reach_dist(P, N)
2. for each instance P:
2.1. Calculate the local outlier factor of P relative to its k-nearest neighbors denoted as N
LOF(P) = sum of the k lrd(N) / (k * lrd(P))
3. Return the set of points with a local outlier factor above a certain threshold
142
 Antoine PALISSON

Local Outlier Factor (5)

High density regions

“Density” score

Low density regions

143
 Antoine PALISSON

ABOD
The Angle-Based Outlier Detection (ABOD) model uses the notion of the angle
between an instance and its neighbors to identify outliers. After calculating the
angles between all the other instances, the ABOD model makes some assumptions:
● For an instance within a cluster, the angles between difference vectors
to pairs of other instances differ widely because most of the other
instances are close.
● For an instance at the border of a cluster, the variance of the angles will
become smaller. However, even here the variance is still relatively high
compared to the variance of angles for real outliers.
● For an instance far from the cluster i.e. an outlier, the angles to
most pairs of instances will be small since most points are clustered
in some directions. 144
 Antoine PALISSON

ABOD (2)
Outliers have a Normal instances
small angle have a large angle
variance because it variance because it is
is always small. can be small or large.

The ABOD model has some advantages over other outlier detection algorithms. It
can handle datasets with high dimensions and it is robust to noise.
However, it has some limitations:
● It can be computationally expensive for large datasets
● It may not perform well if the dataset has a high degree of overlap
between the normal and outlier points. 145
 Antoine PALISSON

Isolation methods
Isolation methods, such as Isolation Forest, rely on the assumption that anomalies
are instances that are rare and different from the rest of the data, especially it
assumes that anomalies are isolated from the majority of the instances, either in
terms of their values or their relationships to other instances.
Isolation Forest is an ensemble method that uses random decision trees to identify
observations that are different from the majority of the data. It works by randomly
selecting a feature and a split value, and then isolating the observation that has
the highest path length. The path length is the number of splits it takes to isolate
the observation.
The more isolated the observation, the higher the path length and the more
likely it is to be an anomaly.
146
 Antoine PALISSON

Isolation methods (2)

Isolation Forest

At least one split is At least two splits are At least four splits
needed to isolate the needed to isolate the are needed to isolate
instance instance the instance
Outlier Border instance Inlier

147
 Antoine PALISSON

Isolation methods (3)

Isolation Forest - Algorithm

1. Initialize the forest with a number of trees

2. For each tree:
2.1. Select a random sample of the data
2.2. Select a random feature and a random split value
2.3. Split the sample into two subsets based on the feature and split value
2.4. Repeat the process recursively until reaching a stopping criterion
3. For each instance:
3.1. For each tree, calculate the path length from the root to the leaf that the instance falls in
3.2. Calculate the average path length across all the trees
4. Identify the instances with the shortest average path length as the anomalies

148
 Antoine PALISSON

Isolation methods (4)

Isolation Forest - Path Length regions

Normal instance regions

Average Path Length

(normalized)

Outlier regions
149
 Antoine PALISSON

Domain-based methods
Domain-based methods rely on the assumption that anomalies are instances that
do not meet some predefined rules or are located in regions of low density. It relies
either on:
● Prior knowledge about the data
● The problem domain in order to define rules
● On density thresholds that separate normal instances from anomalies.

Rule-based methods assume that anomalies can be identified based on a set

of rules that define the expected behavior of the data whereas density-based
methods such as One Class SVM assume that anomalies are instances that
are located in regions of low density.
150
 Antoine PALISSON

One-class SVM
The One-class Support Vector Machine algorithm is based on the supervised
algorithm of the name. However, it is a one-class classification algorithm, which
means that it is trained on a dataset that only contains examples of the normal
class.
The goal is to learn a decision boundary that separates the normal class from the
other classes. It is based on the idea that the normal class is well separated from the
other classes, and that any new examples that fall on the opposite side of the
decision boundary are considered to be anomalies or novelties.
There are two types of One-Class SVM:

● Soft-Margin that has a diffuse boundary

● Hard-Margin that has a strict boundary 151
 Antoine PALISSON

One-class SVM (2)

Outliers

Hyperplane
(Decision Surface)

Support Vector
Soft Margin Hard Margin

152
 Antoine PALISSON

One-class SVM (3)

The One-class SVM algorithm works by finding a hyperplane that maximizes the
distance between itself and the closest examples of the normal class, while still
correctly classifying all examples of the normal class. The algorithm uses a kernel
function to transform the input data into a higher dimensional space where the
data can be linearly separated.

Kernel

Not linearly separable Linearly separable 153

 Antoine PALISSON

One-class SVM (4)

The main idea is to minimize the objective function :

with the weight vector w, the bias b, a regularization parameter 𝜌, a parameter that
controls the proportion of outliers 𝜈 and the hyperplane function f(x):

with K a kernel function and xi and xj two instances.

154
 Antoine PALISSON
Soft-Margin One Class SVM - Pseudocode algorithm

1. Initialization
1.1. Select a kernel function, a value for the 𝜈 parameter a value for the regularization parameter C
1.1. Create an empty set of support vectors
1.2. Initialize the weight vector w, the bias b and 𝜌 to 0

2. Transform the input data into a higher dimensional feature space using the selected kernel function

3. Minimize the objective function L(w, b) = 1/2 * ||w||2 - 𝜌𝜈 + 1/2 * SUM(max(0, 1 - f(x)))
over all negative class instances x using the set of support vectors as constraints
3.1. For each instance x in the training set:
3.1.1. Calculate the value of the decision function f(x) = wT * x + b
3.1.2. If f(x) >= 1, the instance is in the positive class and is added to the set of support vectors
3.1.3. Else if f(x) < 1, the instance is considered to be in the negative class
3.2. Update w and b using an optimization algorithm (Gradient descent, Quasi-Newton Methods …)

4. For each instance x in the test set:

4.1. Calculate the value of the decision function f(x) = wT * x + b
4.2. If f(x) >= 0, the instance is considered to be in the positive class
4.3. Else if f(x) < 0, the instance is in the negative class and is considered as an anomaly

155
 Antoine PALISSON

Pros & Cons

Pros Cons
● Good for isolated anomalies ● Not good at identifying global/local anomalies
Isolation Forest ● Fast and efficient ● Dataset must be representative
● Robust to variations in the data distributions ● Sensitive to the presence of outliers & noise

● Not good with not evenly distributed data

Local Outlier ● Good for local anomalies
● Sensitive to the choice of the parameter k
Factor ● Good for data with varying densities
● Sensitive to the density of the data

● Not good with non Gaussian distributed data

Elliptic ● Good with Gaussian distributed data
● Sensitive to the choice of the parameters (model
Envelope ● Robust to the presence of noise and outliers
used, contamination rate …)

● Not good with non linearly separable data

One Class ● Good for local anomalies ● Sensitive to the choice of the kernel function and the
nu-SVM ● Good for novelty detection regularization parameter
● Dataset must be representative

156
 05
Association
Rules Learning
157
 Antoine PALISSON

Introduction
Association Rules Learning is a statistical technique used to uncover hidden
relationships between items in large datasets. It aims to identify frequent patterns
and relationships (association rules) among the items, which can then be used to
make informed decisions such as providing valuable insights for market basket
analysis, recommendation systems, fraud detection and other applications.

Lettuce

Beers
Tomato Buns

Mozzarella Oignons Burger Ribs

158
 Antoine PALISSON

Methods
The most known algorithms for Association Rules Learning are:
● Apriori - proposed by Agrawal and Srikant in 1994, it is designed to operate
on databases containing transactions.
● Eclat (Equivalence Class Clustering and bottom-up Lattice Traversal) -
proposed by Zaki et al. in 1997, it is a more efficient and scalable version of
the Apriori algorithm.
● FP-Growth - proposed by Han et al. in 2000, it is faster than the Apriori and
Eclat algorithms.

Some other algorithms were designed to address different challenges in the

Association Rules learning problem such as CMAR (2001), EASE (2003) or
Charm (2004) to name a few. 159
 Antoine PALISSON

Apriori
The Apriori algorithm operates on the principle that if an item is frequent, then all
its subsets must also be frequent.
The algorithm starts with single items and successively adds items to generate all
possible combinations, pruning any infrequent itemsets along the way. The final
result is a set of frequent itemsets that can be used to generate association rules,
which describe relationships between items in the database.
Apriori is a 4-steps algorithm:
● Candidate Generation
● Support Counting
● Pruning
● Generating Association Rules
160
 Antoine PALISSON

Apriori (2)
Candidate Generation

The purpose of the candidate generation step is to generate multiple candidate

itemsets from the database that can be used in the next steps to determine which
of them are frequent:
1. It starts with multiple item sets of size 1, where each item set consists of a
single item.
2. Then, candidate itemsets of size 2 are generated by combining every pair
of candidate item sets.
3. This process continues for each size n, candidate itemsets of size n+1 are
generated by combining every pair of item sets of size n.

161
 Antoine PALISSON

Apriori (3)
Support Counting & pruning

The purpose of the support counting step is to calculate the support of each
candidate item set, which is a measure of how frequently the item set appears in
the transactions of the database.

Then, based on the support count, the pruning step removes the item sets with a
support count below a specified minimum support threshold.

162
 Antoine PALISSON

Apriori (4)
Generating Association Rules

The purpose of the generating association rules step is to extract meaningful

relationships or associations between items in the frequent item sets generated
in the previous steps.
An association rule is an implication of the form X → Y, where X is an item set that is
referred to as the antecedent and Y is an item set that is referred to as the
consequent.
The {A,B} item set is linked
{A,B} → {C} to the {C} item set.
{A,C} → {B}
{B,C} → {A}
{A,B,C} {A} → {B,C}
The {B} item set is linked
{B} → {A,C}
to the {A, C} item set.
A frequent itemset {C} → {A,B}

Association Rules 163

 Antoine PALISSON

Apriori (5)
Confidence

Each association rule is associated to a confidence score such as:

A high confidence score in association rule mining means that the presence of an
antecedent item set (X) in a transaction is strongly correlated with the presence of
the consequent item set (Y).
A confidence score of 1 means that every transaction containing the antecedent
item set also contains the consequent item set, while a score of 0 means that the
antecedent and consequent items never appear together.
A threshold is generally used to remove the low confidence association rules.
164
 Antoine PALISSON

Apriori (6)
Lift

The lift is a measure of the strength of the relationship between the antecedent
and consequent item sets in an association rule. It can be seen as a normalization.

This score can be interpreted as follows:

● lift ~ 1 indicates that the X and Y set items are independent.
● lift > 1 indicates a positive association between the item sets.
● lift < 1 indicates a negative association between the item sets.

165
 Antoine PALISSON

Apriori (7)
Pros & cons

Pros Cons

Interpretability Parametric
It is a very simple model that can be easily It is sensible to the choice of parameters such
understood by the end-users. as the support threshold.

Sparse Data Limited

It efficiently deals with sparse datasets. 1. It is limited to the frequent itemset
association rules. It may not be suited for
other type of association rule such as
Exhaustive sequence or subgroup rule mining.
It finds all the association rules between the 2. It may generate redundant and/or trivial
items. rules.

Scalable
It works well with large datasets but it can be very slow.

166
 Antoine PALISSON

Eclat
Definition

Equivalence Class Clustering and Bottom-Up Lattice Traversal (Eclat) is an

association rule mining algorithm that is used to find frequent itemsets in
transaction databases. It is a depth-first search algorithm that uses a vertical data
representation format, where each column in the dataset corresponds to an item,
and each row represents a transaction.
Eclat is often considered as an improvement over Apriori as it can be faster and
more memory-efficient. The main difference between the two algorithms is in the
candidate generation step.
The Eclat algorithm uses a vertical data format where each item is
represented as a set of transactions that contain it. It then recursively
computes the intersection of the transaction sets of each item to generate
frequent itemsets. 167
 Antoine PALISSON

Support
Eclat (2)
(the number of occurrences)

Transactions Items
Item
1 ADE
A:7 B:3 C:6 D:6 E:7
B 2 BCD
3 ACE
A C:2 D:2 E:1 C D
4 ACDE
5 AE
B:0 C:4 D:5 E:6 D:4 E:4 E:4
6 ACD
D D
7 BD
C E:4 E:2
8 ACDE
9 BCE
D:3 E:3
10 ADE
D
E:2 min_support = 3
168
 Antoine PALISSON

Eclat (3)
Transactions Items Items Transactions Items Transactions

1 ADE A 1, 3, 4, 5, 6, 8, 10 AC 3, 4, 6, 8
2 BCD B 2, 7, 9 AE 1, 3, 4, 5, 8, 10
3 ACE C 2, 3, 4, 6, 8, 9 CD 2, 4, 6, 8
4 ACDE D 1, 2, 4, 6, 7, 8, 10 CE 3, 4, 8, 9
5 AE E 1, 3, 4, 5, 8, 9, 10 DE 1, 4, 8, 10
6 ACD
7 BD
8 ACDE Items Transactions
9 BCE ACE 3, 4, 8
10 ADE ACD 4, 6, 8
ADE 4, 8, 10
min_support = 3 169
 Antoine PALISSON

FP-Growth
Definition

The Frequent Pattern(FP) growth algorithm is a data mining technique used to

discover frequent itemsets from a transactional database. It uses a compact data
structure called a frequent pattern tree to efficiently store and process the
database, enabling the generation of all frequent itemsets that meet a minimum
support threshold.
The FP-growth algorithm is a two step algorithm:
1. Compress the database into a frequent-pattern tree
2. Divide the compressed database into a set of conditional databases and
extract the rules separately

170
 Antoine PALISSON

FP-Growth (2)
Frequent pattern tree

The frequent pattern tree is built using the following steps:

1. Find the support count of each item and remove the infrequent items.
2. Sort the items in descending order of their support count.
3. Traverse the dataset again, and for each transaction, order the items in
the transaction according to the descending order of their support
count. Then, add a branch to the tree that represents the first ordered
transaction.
5. For each item in the next ordered transaction, create a node in the
tree or update the count of an existing node if the item already
exists in the tree.
171
 Antoine PALISSON

FP-Growth (3)
Frequent pattern tree

Step 1 Step 2
Step 3
Support Support
Items Items
Transactions Items Count Count Transactions Items

1 ABCD A 2 B 4 1 BCAD
2 BCE B 4 C 3 2 BCE
3 ABCE C 3 E 3 3 BCEA
4 BE D 1 A 2 4 BE
E 3 D 1

172
 Antoine PALISSON
Transactions Items

1
2
3
BCAD
BCE
BCEA
FP-Growth (4)
Frequent pattern tree
4 BE

Step 3
Step 3 Step 4-1 Step 4-2 Step 4-2

Null Null Null Null

B (1) B (2) B (3) B (3)

C (1) C (2) C (3) C (3) E (1)

A (1) A (1) E (1) A (1) E (2) A (1) E (2)

D (1) D (1) D (1) A (1) D (1) A (1)

173
 Antoine PALISSON

FP-Growth (5)
Conditional Database

The conditional database is built by recursively mining the tree by starting from
the leaf nodes and working upwards. At each node, combine the frequent pattern
represented by the node with the frequent patterns from its parent node, until the
root node is reached.
Null min_support = 2

Conditional Conditional
B (7) A (2) Item Frequent Patterns
Patterns FP-Tree

E {B,A:1} {B,A,C:1} {B:2,A:2} {B,E:2} {A,E:2} {B,A,E:2}

A (4)
D (1) C (2) D {B,A:1} {B:1} {B:2} {B,D:2}
C (2)
C {B,A:2} {B:2} {A:2} {B:4,A:2} {A:2} {B,C:4} {A,C:4}* {B,A,C:4}
E (1) D (1) A {B:4} {B:4} {B,A:4}
C (2)
* combination of the two {A:2} 174
E (1)
 06
Doorway to
Deep Learning
175
 Antoine PALISSON

Autoencoder
Autoencoders are a type of neural network that can be used for unsupervised
learning of high-dimensional data.
The main idea behind Autoencoders is to learn a compressed representation of the
input data by training a neural network to encode the input data into a
lower-dimensional space and then decode it back into the original
high-dimensional space.
Autoencoders can be used for dimensionality reduction but also for anomaly
detection, where the reconstruction error between the original data and the
reconstructed data is used as a measure of how anomalous the input data is.
The lower-dimensional space produced by the autoencoders can also be used
along with traditional clustering algorithms such as k-Means and DBSCAN.
176
 Antoine PALISSON

Autoencoder (2)
Autoencoders have several advantages : Inputs
● They can capture nonlinear
relationships in the input features
Encoder
● They can be used for
unsupervised feature learning
i.e. discovering patterns or Bottleneck
features in data without the need
for explicit supervision or labels Decoder
such as edge detectors, texture
detectors or object detectors.
Outputs
Antoine PALISSON 177
 Antoine PALISSON

VAEs
Variational Autoencoders (VAEs) are a type of Autoencoder that can learn a
compressed representation of the input data, while also learning a probability
distribution over the input data.
Unlike traditional Autoencoders, VAEs use a probabilistic approach that enables
the generation of new instances by sampling from the learned distribution. It
consists of an encoder network that maps the input data to a probability
distribution in the latent space, and a decoder network that maps the latent space
to the output space.

178
 Antoine PALISSON

VAEs (2)
VAEs have several advantages : Inputs
● They can be used to generate
new instances by sampling Encoder
from the learned distribution
in the latent space.
Probabilistic Layer N(𝜎,𝜇)
● They can also be used for
unsupervised feature
learning Decoder

Outputs
179
 Antoine PALISSON

SOMs
Self-Organizing Maps (SOMs) are a type of artificial neural network developed in
the 1980s that are used for unsupervised learning of high-dimensional data.
The main idea behind SOMs is to map high-dimensional input data onto a
low-dimensional grid of neurons, while preserving the topological structure of the
input space. This means that similar inputs should be mapped to nearby neurons,
while dissimilar inputs should be mapped to neurons that are further apart.
The training of SOMs involves two main processes:
● Competition : each neuron in the grid competes with its neighbors to be
the most similar to the input.
● Cooperation : the weights of the winning neuron and its neighbors
are updated to make them even more similar to the input.
180
 Antoine PALISSON

SOMs (2)
Source : [Link]

SOMs have several advantages over

Machine Learning clustering techniques
such as k-means:
● They capture the underlying
structure of the input space, and
can be used for data
visualization, as the
low-dimensional grid of neurons
can be easily visualized.
● They are much more robust to
noise and outliers in the input
data. 181
 Antoine PALISSON

GANs
Generative Adversarial Networks (GANs) are a type of generative model that can
learn to generate new instances that are similar to the input data.
The main idea behind GANs is to train two neural networks :
● A generator network that learns to generate new instances that are
similar to the input data,
● A discriminator network that learns to distinguish between the
generated instances and the real data samples.

182
 Antoine PALISSON

GANs (2)
OC-GANs

One Class Generative Adversarial Network (OC-GAN) is a variation of the standard

Generative Adversarial Network designed specifically for anomaly detection.
OC-GAN is trained on a dataset of normal instances, and its objective is to generate
realistic instances that resemble the normal data distribution i.e. that seem to
belong to the normal instances.
Once the OC-GAN model is trained, it can be used for anomaly detection. New
instances are compared to the learned normal data distribution: If the discriminator
classifies the new instance as fake i.e., it deviates significantly from the normal
distribution, it is considered as an anomaly.

183