Clustering
1. Introduction : Pourquoi le Clustering est Important dans le Data Mining
Le clustering est une pierre angulaire de l’apprentissage non supervisé (unsupervised
learning) dans le data mining. Il consiste à regrouper les données en clusters où les points
d’un même cluster sont plus similaires entre eux qu’avec ceux des autres clusters. Son
importance réside dans sa capacité à :
• Découvrir des Motifs (patterns) Cachés : Le clustering identifie des
regroupements naturels dans les données, cruciaux pour l’analyse exploratoire. Par
exemple, il peut révéler des comportements de consommateurs qui pourraient
passer inaperçus avec des méthodes traditionnelles.
• Améliorer la Prise de Décision : Par exemple, en segmentant les clients ou les
produits, le clustering permet aux entreprises de personnaliser leurs stratégies
marketing, concevoir des campagnes ciblées et optimiser l’allocation des
ressources.
• Prétraitement pour l’Apprentissage Supervisé (Supervised Learning): Le
clustering aide à identifier les valeurs aberrantes pour améliorer la qualité des
données, ce qui peut renforcer les performances des modèles supervisés.
2. Algorithmes de Clustering
Cette section explore les fondements de deux algorithmes populaires de clustering : K-
Means, Clustering Hiérarchique, et une comparaison des deux méthodes, accompagnés
de leurs implémentations en R.
2.1 Clustering K-Means
• Le K-Means partitionne les données en clusters en minimisant la somme des carrés
des distances intra-clusters (WCESS), aussi appelée somme des erreurs intra-
clusters :
𝑘
WCESS = ∑ ∑ ∥ 𝑥 − 𝜇𝑖 ∥2
𝑖=1 𝑥∈𝐶𝑖
où 𝐶𝑖 est un cluster et 𝜇𝑖 son centroïde.
• L’algorithme :
1. Initialisation des centroïdes : Commencez par sélectionner aléatoirement
𝑘 points comme centroïdes initiaux.
2. Affectation des points au centroïde le plus proche : Calculez la distance
de chaque point à tous les centroïdes et affectez chaque point au plus
proche.
3. Recalculez les centroïdes : Pour chaque cluster, calculez la moyenne de
tous les points et mettez à jour le centroïde.
4. Vérifiez la convergence : Répétez les étapes 2 et 3 jusqu’à ce que les
centroïdes se stabilisent (c.-à-d. que leurs positions ne changent plus
significativement) ou qu’un nombre maximal d’itérations soit atteint.
• Avantages et limitations :
o Simple à implémenter et efficace sur le plan computationnel.
o Sensible au placement initial des centroïdes, ce qui peut conduire à un
clustering sous-optimal.
• Implémentation en R :
# Exemple de données
data <- iris[, -5]
# Clustering K-Means
[Link](123)
kmeans_result <- kmeans(data, centers = 3)
# Visualisation des clusters
library(ggplot2)
data$Cluster <- [Link](kmeans_result$cluster)
ggplot(data, aes([Link], [Link], color = Cluster)) +
geom_point() +
labs(title = "Clustering K-Means")
2.2 Clustering Hiérarchique
Le clustering hiérarchique construit une hiérarchie de clusters et peut être mis en œuvre
selon deux approches :
• Agglomérative (Bottom-Up) : Commence avec chaque point comme un cluster
unique et fusionne les clusters les plus proches de manière itérative jusqu’à ce que
tous les points forment un seul cluster.
• Divisive (Top-Down) : Commence avec tous les points dans un seul cluster et les
divise en clusters plus petits de manière itérative jusqu’à ce que chaque point soit
un cluster unique.
Exemple de Clustering Agglomératif
• Étapes de l’algorithme :
1. Commencez avec chaque point comme son propre cluster.
2. Calculez les distances entre tous les clusters.
3. Fusionnez les deux clusters les plus proches selon les critères de liaison.
4. Répétez les étapes 2 et 3 jusqu’à ce qu’il ne reste qu’un seul cluster ou
qu’un critère d’arrêt soit atteint.
# Charger la bibliothèque nécessaire
library(cluster)
# Exemple de données
data <- mtcars
# Matrice de distance pour le clustering agglomératif
dist_matrix <- dist(data)
# Clustering agglomératif avec la méthode de Ward
hc <- hclust(dist_matrix, method = "ward.D2")
# Dendrogramme
plot(hc, main = "Dendrogramme de Clustering Hiérarchique Agglomératif", sub
= "", xlab = "")
Interprétation : Observez le dendrogramme et identifiez une hauteur pour couper l’arbre
afin de former le nombre de clusters souhaité. Chaque branche représente une fusion de
clusters, et la hauteur indique la distance entre les clusters fusionnés.
Exemple de Clustering Divisif
• Étapes de l’algorithme :
1. Commencez avec tous les points dans un seul cluster.
2. Évaluez les divisions potentielles et divisez le cluster en groupes plus petits
pour maximiser la séparation entre sous-clusters.
3. Répétez jusqu’à ce que chaque point soit un cluster unique ou qu’un critère
d’arrêt soit atteint.
# Charger la bibliothèque nécessaire
library(cluster)
# Exemple de données
data <- mtcars
# Clustering divisif
dc <- diana(data)
# Dendrogramme
plot(dc, main = "Dendrogramme de Clustering Hiérarchique Divisif", sub =
"", xlab = "")
Interprétation : Le dendrogramme divisif commence avec un cluster unique en haut et se
divise de manière itérative. Concentrez-vous sur les divisions significatives pour identifier
des clusters significatifs.
2.3 Comparaison entre K-Means et Clustering Hiérarchique
Caractéristique K-Means Clustering Hiérarchique
Type d’algorithme Basé sur des partitions Hiérarchique (agglomératif ou
divisif)
Forme des clusters Suppose des clusters Peut gérer des clusters de
sphériques de taille similaire formes arbitraires
Nombre de clusters Doit être spécifié à l’avance Pas nécessaire; le
(k) dendrogramme aide à décider
Évolutivité Efficace pour les grands Coûteux en calcul pour les
ensembles de données grands ensembles de données
Flexibilité Ne peut pas gérer des clusters Peut découvrir des clusters
imbriqués imbriqués
Résultats Affectations finales des clusters Dendrogramme et
affectations des clusters
Stabilité Dépend des centroïdes initiaux Plus déterministe
Quand Utiliser
• K-Means : Idéal pour les grands jeux de données avec des clusters bien séparés et
sphériques.
• Clustering Hiérarchique : Idéal pour les petits ensembles de données avec des
structures complexes.
3. Applications du Clustering dans les Problèmes Métier
• Segmentation de Clients : Personnaliser les stratégies marketing.
• Analyse de Panier d’Achat : Identifier les groupes de produits souvent achetés
ensemble.
• Détection d’Anomalies : Repérer les activités frauduleuses.
• Classification de Documents : Organiser de grands corpus textuels.
4. Exercice
Objectif : Appliquer les algorithmes de clustering sur un ensemble de données et
interpréter les résultats.
Tâches :
1. Effectuer un clustering K-Means avec les données de votre projet. Essayez plusieurs K,
et choisissez le K qui vous semble informatif.
2. Visualiser les regroupements avec un dendrogramme en utilisant le clustering
hiérarchique.
3. Comparer les résultats des différentes méthodes.
