DBSCAN Clustering in Machine Learning
DBSCAN Clustering in ML
Objectifs de la présentation
• Comprendre les principes fondamentaux de l'algorithme
DBSCAN en termes mathématiques et algorithmiques.
• Illustrer concrètement le fonctionnement de DBSCAN à travers
des exemples détaillés et des études de cas dans divers
domaines d'application.
DBSCAN Clustering in ML
Plan du présentation
1. Introduction au clustering et à DBSCAN.
2. Fonctionnement de DBSCAN et paramètres associés.
3. Mise en œuvre pratique de DBSCAN.
DBSCAN Clustering in ML.
1. Introduction au clustering et à
DBSCAN.
1. Introduction au clustering et à DBSCAN
a. Notion de clustering.
• Le clustering, également appelé regroupement en français, est une
technique d'apprentissage non supervisée utilisée en analyse de données et
en apprentissage automatique.
• Son objectif est de regrouper un ensemble de données en sous-groupes,
appelés clusters, de sorte que les données au sein d'un même cluster
partagent des caractéristiques similaires tandis que les données entre
clusters sont différentes.
1. Introduction au clustering et à DBSCAN
b. DBSCAN
• Les clusters sont des régions denses dans l'espace des données, séparées par
des régions où la densité de points est plus faible. L'algorithme DBSCAN
repose sur cette notion intuitive de "clusters" et de "bruit".
• L'idée clé de DBSCAN est que pour chaque point d'un cluster, le voisinage
d'un rayon donné doit contenir au moins un nombre minimum de points.
DBSCAN Clustering in ML.
2. Fonctionnement de DBSCAN et
paramètres associés.
2. Fonctionnement de DBSCAN et paramètres associés.
a. Paramètres requis pour l'algorithme DBSCAN.
DBSCAN fonctionne en définissant deux paramètres clés:
1. Epsilon (ε): Le rayon maximal autour d'un point à considérer pour déterminer
sa densité.
2. MinPts: Le nombre minimum de points requis dans le voisinage d'un point
pour le considérer comme un point centrale.
Ces paramètres déterminent la façon dont les différents types de points de
données sont identifiés dans l'algorithme.
2. Fonctionnement de DBSCAN et paramètres associés.
b. Types de points de données.
Voici comment ces paramètres sont liés aux types de points de données dans
DBSCAN :
• Points centraux : Un point est considéré comme central s'il possède plus de
MinPts points à l'intérieur de eps.
• Points frontières : Un point qui a moins de MinPts points à l'intérieur de eps
mais qui se trouve dans le voisinage d'un point central.
• Points aberrants : Un point qui n'est ni central ni frontal.
2. Fonctionnement de DBSCAN et paramètres associés.
c. Concepts mathématiques sous-jacent.
Soit (𝐷, ∥. ∥) Un espace vectoriel normé
Définitions :
On appelle distance entre 2 points a et b , L’application :
d:𝐷×𝐷 ℝ+
(𝑎, 𝑏) 𝑑 𝑎, 𝑏 = ∥ 𝑎 − 𝑏 ∥
On appelle Boule ouvert de centre C et rayon R, L’ensemble :
𝐵 𝐶, 𝑅 = 𝑀 ∈ 𝐷 / 𝑑(𝑀, 𝐶) < 𝑅
On appelle 𝝐 − 𝒗𝒐𝒊𝒔𝒊𝒏𝒂𝒈𝒆 d’un point 𝑝, L’ensemble :
𝑉𝜖 𝑝 = 𝐵 𝑝, 𝜖 = 𝑀 ∈ 𝐷 / 𝑑(𝑀, 𝑝) < 𝜖
2. Fonctionnement de DBSCAN et paramètres associés.
c. Concepts mathématiques sous-jacent.
Soit 𝑁 l’ensemble des Points centraux définit par :
𝑁 = 𝑀 ∈ 𝐷 / 𝑐𝑎𝑟𝑑(𝑉𝜖 𝑀 ) ≥ 𝑀𝑖𝑛𝑝𝑡𝑠
Où 𝑀𝑖𝑛𝑝𝑡𝑠 ∈ ℕ∗
Construction des clusters :
Soit 𝑅1 la relation Directement accessible définit par :
∀ 𝑝, 𝑞 ∈ 𝐷 2 ∶ 𝑝 𝑅1 𝑞 ⇔ 𝑞 ∈ 𝑉𝜖 (𝑝)
Soit 𝑅2 la relation accessible définit par :
∀ 𝑝, 𝑞 ∈ 𝐷 2 : 𝑝 𝑅2 𝑞 ⇔ ∃ 𝑝1 , 𝑝2 , … … . . , 𝑝𝑛 ∈ 𝐷𝑛 𝑡𝑞 ∶
𝑝1 = 𝑝
ቐ𝑝𝑖 𝑅1 𝑝𝑖+1 , ∀𝑖 ∈ ۤ1, 𝑛 − 1ۥ
𝑝𝑛 = 𝑞
2. Fonctionnement de DBSCAN et paramètres associés.
c. Concepts mathématiques sous-jacent.
Soit 𝐶0 = ∅ , 𝐾 ∈ ℕ∗ , 𝑒𝑡 𝑗 ∈ (𝑁 \ 𝑘ڂ−1
𝑖=0 𝐶𝑖 )
On définit le cluster primaire 𝐶𝑘′ par :
𝐶𝑘′ = 𝑗 𝑁 ∈ 𝑀 ڂ/ 𝑗 𝑅2 𝑀
D’où le cluster 𝐶𝑘 est :
𝐶𝑘 = 𝐶𝑘′ 𝑘ڂ \ 𝐷 ∈ 𝑀 ڂ−1 𝐶
𝑖=1 𝑖 / 𝑀 𝑅1 𝑝, 𝑎𝑣𝑒𝑐 𝑝 ∈ 𝐶𝑘
′
On définit l’ensemble des points aberrants par :
𝑛
𝑇= 𝐷\ ራ 𝐶𝑖
𝑖=0
où n est le nombre des clusters
2. Fonctionnement de DBSCAN et paramètres associés.
c. Concepts mathématiques sous-jacent.
Choix de 𝜖 𝑒𝑡 𝑀𝑖𝑛𝑝𝑡𝑠 :
𝑴𝒊𝒏𝒑𝒕𝒔 ∶
le choix selon la règle de base : 𝑀𝑖𝑛𝑝𝑡𝑠 ≥ dim 𝐷 + 1
Souvent : 𝑀𝑖𝑛𝑝𝑡𝑠 = 2 × dim 𝐷
𝝐:
Soit 𝑓𝑖 ∶ 𝐷 𝐷
𝑀 𝑓𝑖 𝑀 ∶ le 𝑖 è𝑚𝑒 plus proche point de M
Soit Σ, L’ensemble définit par :
Σ = 𝑑 𝑀, 𝑓𝑀𝑖𝑛𝑝𝑡𝑠 𝑀 / 𝑀 ∈ 𝐷
Soit Σ′ est l’ensemble Σ trié en ordre croissante
2. Fonctionnement de DBSCAN et paramètres associés.
c. Concepts mathématiques sous-jacent.
On trace les éléments de Σ′ :
𝝐 est la valeur du ’’point seuil ’’
2. Fonctionnement de DBSCAN et paramètres associés.
d. Étapes de l'algorithme.
1. Initialisation : Choisir un point non visité.
2. Voisinage : Trouver tous les points dans un rayon ε du point choisi.
3. Densité : Si le nombre de points dans le voisinage est supérieur ou égal
à MinPts, marquer le point actuel comme un noyau.
4. Expansion du cluster : Étendre le cluster en ajoutant des points accessibles
à partir du noyau.
5. Terminaison : Répéter les étapes précédentes pour tous les points non
visités jusqu'à ce que tous les points aient été attribués à un cluster ou
soient marqués comme du bruit.
2. Fonctionnement de DBSCAN et paramètres associés.
e. L'algorithme DBSCAN.
DBSCAN(dataset, eps, MinPts){
# cluster index
C=1
for each unvisited point p in dataset {
mark p as visited
# find neighbors
Neighbors N = find the neighboring points of p
if |N|>=MinPts:
N = N U N'
if p' is not a member of any cluster:
add p' to cluster C
}
DBSCAN Clustering in ML.
3. Mise en œuvre pratique de DBSCAN
Poids Taille
Personne 56 150
1
Personne 62 170
2
Personne 71 168
3
... ... ...
DBSCAN Clustering in ML.
Bonus : DBSCAN VS K-Means.
DBSCAN K-Means
Pas besoin de spécifier le nombre de Sensible au nombre de clusters.
clusters.
Les clusters peuvent être de toute Les clusters sont sphériques ou
forme. convexes.
Fonctionne bien avec des données Ne fonctionne pas bien avec des
bruitées et des valeurs aberrantes. valeurs aberrantes.
Deux paramètres sont nécessaires Un seul paramètre est nécessaire
pour l'entraînement. pour l'entraînement.
DBSCAN Clustering in ML.
ANNEXE.