Le clustering est une technique d'apprentissage non supervisé visant à regrouper des données similaires sans étiquettes préalables. Deux approches fondamentales dominent ce domaine : K-means, basé sur les centroïdes, et DBSCAN, basé sur la densité.

Comparaison des approches

1. L'algorithme K-means

K-means cherche à partitionner n observations en k clusters où chaque observation appartient au cluster dont le centre (moyenne) est le plus proche.

Implémentation personnalisée

Voici une structure simplifiée pour comprendre le mécanisme itératif de mise à jour des centroïdes :

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs

class AnalyseurKMeans:
   def __init__(self, n_groupes=4, iterations=100):
       self.k = n_groupes
       self.max_iter = iterations
       self.centres = None

   def entrainer(self, donnees):
       # Initialisation aléatoire des points centraux
       indices_depart = np.random.permutation(donnees.shape[0])[:self.k]
       self.centres = donnees[indices_depart]

       for _ in range(self.max_iter):
           # Calcul des distances euclidiennes
           distances = np.sqrt(((donnees - self.centres[:, np.newaxis])**2).sum(axis=2))
           # Assignation au centre le plus proche
           labels = np.argmin(distances, axis=0)
           
           nouveaux_centres = np.array([donnees[labels == i].mean(axis=0) for i in range(self.k)])
           
           # Convergence si les centres ne bougent plus
           if np.all(self.centres == nouveaux_centres):
               break
           self.centres = nouveaux_centres
       
       return labels

# Test sur données synthétiques
X, _ = make_blobs(n_samples=400, centers=4, cluster_std=0.7, random_state=42)
modele = AnalyseurKMeans(n_groupes=4)
predictions = modele.entrainer(X)

plt.scatter(X[:, 0], X[:, 1], c=predictions, cmap='plasma', alpha=0.6)
plt.scatter(modele.centres[:, 0], modele.centres[:, 1], c='black', marker='x', s=100)
plt.title("Visualisation K-means (Manuel)")
plt.show()

Sélection du 'k' optimal : Méthode du coude

Pour déterminer le nombre idéal de clusters, on observe l'évolution de l'inertie (somme des carrés des distances intra-cluster).

from sklearn.cluster import KMeans

inerties = []
plage_k = range(1, 11)
for k in plage_k:
   km = KMeans(n_clusters=k, n_init='auto').fit(X)
   inerties.append(km.inertia_)

plt.plot(plage_k, inerties, 'bx-')
plt.xlabel('Nombre de clusters (k)')
plt.ylabel('Inertie')
plt.title('Méthode du coude (Elbow Method)')
plt.show()

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

Contrairement à K-means, DBSCAN ne nécessite pas de spécifier le nombre de clusters. Il définit un cluster comme une zone de haute densité entourée de zones de basse densité.

• Points cœurs : Points ayant au moins MinPts dans leur voisinage de rayon ε.
• Points frontières : Points dans le voisinage d'un point cœur mais n'étant pas eux-mêmes des points cœurs.
• Bruit : Points n'appartanant à aucune des catégories précédentes (marqués -1).

from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons

# Création de données en forme de croissants (difficiles pour K-means)
X_moons, _ = make_moons(n_samples=250, noise=0.08, random_state=42)

# Configuration de DBSCAN
detecteur_densite = DBSCAN(eps=0.2, min_samples=5)
clusters_db = detecteur_densite.fit_predict(X_moons)

plt.scatter(X_moons[:, 0], X_moons[:, 1], c=clusters_db, cmap='viridis')
plt.title("DBSCAN : Clustering basé sur la densité")
plt.show()

3. Estimation du paramètre Epsilon (ε)

Une technique courante consiste à utiliser le graphe des distances aux k-plus proches voisins. Le point d'inflexion (le "genou") indique souvent une valeur d'ε appropriée.

from sklearn.neighbors import NearestNeighbors

voisins = NearestNeighbors(n_neighbors=5)
voisins.fit(X_moons)
distances, indices = voisins.kneighbors(X_moons)

# Trier les distances au 5ème voisin
dist_triees = np.sort(distances[:, 4])
plt.plot(dist_triees)
plt.axhline(y=0.2, color='r', linestyle='--')
plt.title("Graphique des distances K-NN pour Epsilon")
plt.show()

4. Application concrète : Quantification de couleurs

K-means est fréquemment utilisé en traitement d'image pour réduire le nombre de couleurs dominantes.

from PIL import Image

def reduire_couleurs(chemin_image, k_couleurs=8):
   img = Image.open(chemin_image)
   img_array = np.array(img) / 255.0
   h, w, c = img_array.shape
   donnees_pixels = img_array.reshape(-1, c)

   algo = KMeans(n_clusters=k_couleurs, n_init='auto').fit(donnees_pixels)
   nouveaux_pixels = algo.cluster_centers_[algo.labels_]
   
   img_compressee = nouveaux_pixels.reshape(h, w, c)
   return img_compressee

# Note: Remplacez par un chemin d'image valide pour tester
# plt.imshow(reduire_couleurs("image.jpg"))

5. Métriques d'évaluation

L'évaluation en clustering est complexe en l'absence de vérité terrain. On utilise souvent des indices de validation interne.

• Coefficient de Silhouette : Mesure la similitude d'un objet avec son propre cluster par rapport aux autres. Range de -1 (mauvais) à +1 (excellent).
• Indice de Davies-Bouldin : Mesure la séparation et la compacité. Une valeur plus faible indique un meilleur clustering.

from sklearn.metrics import silhouette_score, davies_bouldin_score

score_s = silhouette_score(X, predictions)
score_db = davies_bouldin_score(X, predictions)

print(f"Silhouette Score: {score_s:.2f}")
print(f"Davies-Bouldin Index: {score_db:.2f}")

Synthèse des cas d'usage

Privilégiez K-means pour des données dont les clusters sont globulaires et de tailles similaires, notamment lorsque la rapidité sur de grands volumes est cruciale. Optez pour DBSCAN si vos données contiennent du bruit ou si les regroupements présentent des formes géométriques complexes (anneaux, croissants, etc.).