Algorithmes de Clustering Non Supervisé : k-Means, DBSCAN et Analyse Mathématique Comparative

Résumé

Le clustering est un problème fondamental de l'apprentissage non supervisé, pourtant les garanties formelles des algorithmes largement déployés sont rarement examinées dans des traitements unifiés. Cet article présente une analyse comparative rigoureuse de trois paradigmes majeurs de clustering : les méthodes à base de centroïdes ($k$-means), à base de densité (DBSCAN), et hiérarchiques (agglomératives). Nous formalisons l'objectif du $k$-means comme un problème d'optimisation non convexe, prouvons que l'algorithme de Lloyd converge en un nombre fini d'itérations via un argument de descente de coordonnées, et établissons que le problème $k$-means optimal est NP-difficile même pour $k=2$ en dimension générale. Nous dérivons ensuite la garantie d'approximation compétitive en $O(\log k)$ de l'initialisation $k$-means++. Pour DBSCAN, nous fournissons un cadre formel d'accessibilité par densité, prouvons la correction vis-à-vis des composantes connexes par densité, et analysons sa complexité dans le pire cas en $\Theta(n^2)$ et en $O(n \log n)$ avec index. Nous évaluons toutes les méthodes selon des indices de validité interne formels — le coefficient de silhouette et l'indice de Davies–Bouldin — dont nous dérivons les propriétés mathématiques. L'analyse comparative identifie les conditions géométriques et distributionnelles précises sous lesquelles chaque paradigme est supérieur, allant au-delà de l'heuristique informelle selon laquelle « cela dépend des données ».

1. Introduction

1.1 Motivation

Le clustering — la tâche de partitionner un ensemble de données en groupes d'objets similaires sans supervision étiquetée — occupe une position centrale en science des données, en reconnaissance de formes et en analyse exploratoire. Malgré son omniprésence, le clustering n'est pas un problème bien défini unique, mais une famille de problèmes d'optimisation, chacun encodant des hypothèses géométriques ou statistiques différentes sur ce qui constitue une « bonne » partition. La conséquence pratique est que les praticiens sélectionnent régulièrement des algorithmes par commodité ou par réglage empirique, sans comprendre formellement quand une méthode choisie est optimale, approximativement optimale, ou manifestement inadaptée.

Cela est important théoriquement parce que les objectifs de clustering encodent une structure combinatoire profonde. Le problème du $k$-means, par exemple, est NP-difficile (Aloise et al., 2009 ; Dasgupta, 2008), pourtant l'heuristique de Lloyd (Lloyd, 1982) reste largement utilisée. Comprendre pourquoi elle fonctionne — et quand elle échoue — nécessite une analyse formelle que les traitements habituels omettent.

1.2 Énoncé du Problème

Nous considérons le problème général suivant. Étant donné un ensemble de données fini $X = \{x_1, \dots, x_n\} \subset \mathbb{R}^d$ et une fonction de dissimilarité $\delta: \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}_{\ge 0}$, produire une partition $\mathcal{C} = \{C_1, \dots, C_k\}$ de $X$ qui optimise un critère de qualité. La nature du critère — et si $k$ est donné ou inféré — distingue fondamentalement les paradigmes de clustering que nous analysons.

1.3 Travaux Antérieurs et Résultats Existants

Lloyd (1982) a introduit l'algorithme itératif de raffinement des centroïdes universellement appelé « $k$-means ». Sa complexité dans le pire cas en nombre d'itérations a été montrée superpolynomiale par Vattani (2011), qui a construit des instances nécessitant $2^{\Omega(\sqrt{n})}$ itérations dans le plan. Arthur et Vassilvitskii (2007) ont introduit $k$-means++ avec une garantie d'approximation prouvable en $O(\log k)$. La NP-difficulté du problème $k$-means plan a été établie par Mahajan, Nimbhorkar et Varadarajan (2012) et pour la dimension générale par Aloise et al. (2009). Ester et al. (1996) ont introduit DBSCAN, dont les propriétés formelles ont été analysées par Sander et al. (1998). Les indices de validation interne ont été formalisés par Rousseeuw (1987) pour le coefficient de silhouette et Davies et Bouldin (1979) pour leur indice éponyme.

1.4 Contributions

Cet article apporte les contributions spécifiques suivantes :

1. Nous prouvons la convergence du $k$-means comme descente de coordonnées sur l'objectif WCSS (somme intra-cluster des carrés) et analysons l'écart entre cette garantie et la NP-difficulté de l'optimum global.
2. Nous dérivons le ratio d'approximation $O(\log k)$ du $k$-means++.
3. Nous formalisons DBSCAN via l'accessibilité par densité, prouvons que sa sortie est égale à l'ensemble des composantes connexes par densité maximales, et établissons des bornes de complexité précises.
4. Nous comparons toutes les méthodes selon un cadre multi-critères rigoureux incluant la complexité, les hypothèses géométriques et les indices de qualité formels.

1.5 Organisation

La section 2 établit les notations, définitions et résultats préliminaires. La section 3 présente l'analyse centrale : $k$-means (§3.1), DBSCAN (§3.2), clustering hiérarchique (§3.3), et le cadre comparatif formel (§3.4). La section 4 explique comment préparer une comparaison reproductible. La section 5 offre la discussion, les limitations et les problèmes ouverts. La section 6 conclut.

---

2. Préliminaires et Définitions

2.1 Notations

Tout au long de cet article, $X = \{x_1, \dots, x_n\} \subset \mathbb{R}^d$ désigne l'ensemble de données en entrée. Nous écrivons $\|x - y\|$ pour la norme euclidienne ($\ell_2$) sauf indication contraire. Une $k$-partition de $X$ est une collection $\mathcal{C} = \{C_1, \dots, C_k\}$ de sous-ensembles non vides, disjoints deux à deux et dont l'union est $X$. Pour un ensemble fini $S \subset \mathbb{R}^d$, son centroïde est $\mu(S) = \frac{1}{|S|} \sum_{x \in S} x$. Nous utilisons $[k]$ pour désigner $\{1, 2, \dots, k\}$. Toute l'analyse de complexité est dans le modèle RAM avec des opérations arithmétiques de coût $\Theta(d)$ sur des vecteurs de dimension $d$.

2.2 Définitions Fondamentales

Définition 1 (Somme Intra-Cluster des Carrés — WCSS). Étant donné une $k$-partition $\mathcal{C} = \{C_1, \dots, C_k\}$ de $X$, l'objectif WCSS est :

On peut également écrire $W(\mathcal{C}) = \sum_{j=1}^k |C_j| \cdot \text{Var}(C_j)$, où $\text{Var}(C_j) = \frac{1}{|C_j|} \sum_{x \in C_j} \|x - \mu(C_j)\|^2$.

Exemple. Pour $X = \{1, 2, 10, 11\} \subset \mathbb{R}$ avec $k = 2$, la partition $\{\{1, 2\}, \{10, 11\}\}$ donne $W = (0{,}25 + 0{,}25) + (0{,}25 + 0{,}25) = 1$, tandis que $\{\{1, 10\}, \{2, 11\}\}$ donne $W = 40{,}5$.

Définition 2 ($\epsilon$-voisinage). Pour $\epsilon > 0$ et $x \in X$, le $\epsilon$-voisinage de $x$ est $N_\epsilon(x) = \{y \in X : \|x - y\| \le \epsilon\}$.

Définition 3 (Point noyau, point frontière, bruit). Étant donnés les paramètres $\epsilon > 0$ et $\text{minPts} \in \mathbb{N}$, un point $x \in X$ est un point noyau si $|N_\epsilon(x)| \ge \text{minPts}$. Un point est un point frontière s'il n'est pas un point noyau mais appartient à $N_\epsilon(y)$ pour un certain point noyau $y$. Tous les points restants sont du bruit.

Définition 4 (Accessibilité directe par densité). Un point $y$ est directement accessible par densité depuis $x$ si $x$ est un point noyau et $y \in N_\epsilon(x)$.

Définition 5 (Accessibilité par densité). Un point $y$ est accessible par densité depuis $x$ s'il existe une chaîne $x = p_1, p_2, \dots, p_m = y$ telle que $p_{i+1}$ est directement accessible par densité depuis $p_i$ pour tout $i \in [m-1]$.

Définition 6 (Connexité par densité). Deux points $x, y \in X$ sont connexes par densité s'il existe un point $z \in X$ tel que $x$ et $y$ sont tous deux accessibles par densité depuis $z$.

Exemple. Dans un ensemble de données avec trois blobs gaussiens de rayon approximativement $r$ séparés par une distance $\gg r$, fixer $\epsilon \approx 2r$ et $\text{minPts}$ à un petit entier produit trois ensembles de points mutuellement connexes par densité, un par blob.

2.3 Résultats Préliminaires

Nous utiliserons les résultats suivants sans démonstration.

Théorème 0 (Borne inférieure basée sur les comparaisons, Knuth 1973). Tout algorithme de tri basé sur les comparaisons nécessite $\Omega(n \log n)$ comparaisons dans le pire des cas. Nous invoquons ce résultat lors de l'analyse des coûts de construction d'index.

Proposition 0 (Identité de la médiane). Pour tout ensemble fini $S \subset \mathbb{R}^d$, le minimiseur unique de $f(\mu) = \sum_{x \in S} \|x - \mu\|^2$ est le centroïde $\mu(S)$. Cela découle de $\nabla_\mu f = 0$.

---

3. Analyse Centrale

3.1 Le Problème $k$-Means

3.1.1 Formulation comme Optimisation

Le problème de clustering $k$-means est :

où la minimisation porte sur toutes les $k$-partitions de $X$. De manière équivalente, en introduisant des centres explicites $\mu_1, \dots, \mu_k \in \mathbb{R}^d$ et une fonction d'affectation $\sigma: X \to [k]$, on peut écrire :

Cette reformulation révèle que le problème se décompose en deux sous-problèmes imbriqués : optimiser les affectations étant donnés les centres, et optimiser les centres étant données les affectations. L'algorithme de Lloyd exploite précisément cette structure.

Hypothèse 1. L'entrée se situe dans $\mathbb{R}^d$ selon la métrique euclidienne. Tous les résultats du $k$-means dans cet article supposent la distance $\ell_2$ sauf indication contraire.

Hypothèse 2. Le nombre de clusters $k$ est donné en entrée. Le problème du choix de $k$ est hors du champ de cette analyse, bien que nous notions sa connexion aux critères de sélection de modèles (BIC, statistique du gap) dans la discussion.

3.1.2 L'Algorithme de Lloyd

L'algorithme de Lloyd alterne entre les deux sous-problèmes identifiés dans l'équation (2).

Algorithme 1 : Algorithme de Lloyd ($k$-Means)

Entrée : $X = \{x_1, \dots, x_n\} \subset \mathbb{R}^d$, nombre de clusters $k$, centres initiaux $\mu_1^{(0)}, \dots, \mu_k^{(0)}$.

Répéter jusqu'à convergence :

1. Étape d'affectation : Pour chaque $i \in [n]$, fixer $\sigma^{(t)}(i) = \text{argmin}_{j \in [k]} \|x_i - \mu_j^{(t)}\|^2$ (en brisant les égalités arbitrairement mais de manière cohérente).

2. Étape de mise à jour : Pour chaque $j \in [k]$, fixer $\mu_j^{(t+1)} = \frac{1}{|C_j^{(t)}|} \sum_{x \in C_j^{(t)}} x$, où $C_j^{(t)} = \{x_i : \sigma^{(t)}(i) = j\}$.

Sortie : Partition $\mathcal{C}^{(T)} = \{C_1^{(T)}, \dots, C_k^{(T)}\}$.

---

Théorème 1 (Convergence de l'Algorithme de Lloyd). Sous les hypothèses 1 et 2, l'algorithme de Lloyd se termine en un nombre fini d'itérations. De plus, l'objectif WCSS est monotoniquement non croissant : $W(\mathcal{C}^{(t+1)}) \le W(\mathcal{C}^{(t)})$ pour tout $t \ge 0$.

Démonstration. Nous montrons que chaque étape de l'algorithme n'augmente pas l'objectif, et qu'il existe un nombre fini de partitions possibles.

Considérons l'objectif joint de l'équation (2) :

Étape d'affectation. En fixant $\mu_1^{(t)}, \dots, \mu_k^{(t)}$, l'affectation $\sigma^{(t)}(i) = \text{argmin}_j \|x_i - \mu_j^{(t)}\|^2$ minimise $F$ sur $\sigma$ point par point (chaque terme de la somme est minimisé indépendamment). Ainsi :

Étape de mise à jour. L'étape de mise à jour calcule $\mu_j^{(t)} = \mu(C_j^{(t-1)})$. Par la proposition 0, pour chaque cluster $C_j^{(t-1)}$, le centroïde minimise de manière unique $\sum_{x \in C_j^{(t-1)}} \|x - \mu\|^2$. Par conséquent :

En combinant les inégalités (3) et (4) :

Puisque l'objectif est non croissant et que le nombre de $k$-partitions distinctes de $n$ points est fini (au plus $k^n$, le nombre de fonctions $\sigma: X \to [k]$), l'algorithme doit se terminer. □

La démonstration révèle que l'algorithme de Lloyd est une méthode de descente de coordonnées par blocs sur l'objectif joint $F(\sigma, \mu)$, alternant la minimisation sur la variable discrète $\sigma$ et les variables continues $\mu_1, \dots, \mu_k$. Ce lien avec la descente de coordonnées est la raison précise pour laquelle la convergence est garantie : chaque minimisation par bloc est exacte, et le nombre de valeurs possibles du bloc discret est fini.

Remarque. La convergence vers un minimum local est garantie, mais pas la convergence vers le minimum global. La non-convexité de l'objectif (qui est convexe en $\mu$ pour $\sigma$ fixé et vice versa, mais pas conjointement) signifie que différentes initialisations peuvent produire des minima locaux différents avec des valeurs d'objectif arbitrairement différentes.

3.1.3 Complexité par Itération

Proposition 1. Chaque itération de l'algorithme de Lloyd s'exécute en temps $\Theta(nkd)$ et en espace $\Theta(nd + kd)$.

Démonstration. L'étape d'affectation calcule $\|x_i - \mu_j\|^2$ pour tout $i \in [n], j \in [k]$, chacun nécessitant $\Theta(d)$ opérations, soit un total de $\Theta(nkd)$. L'étape de mise à jour calcule $k$ centroïdes, chacun comme moyenne d'au plus $n$ vecteurs dans $\mathbb{R}^d$, soit un total de $\Theta(nd)$. Le terme dominant est $\Theta(nkd)$. L'espace est $\Theta(nd)$ pour l'ensemble de données et $\Theta(kd)$ pour les centres. □

3.1.4 Complexité en Nombre d'Itérations : L'Écart entre Pratique et Pire Cas

La complexité totale de l'algorithme de Lloyd est $O(T \cdot nkd)$ où $T$ est le nombre d'itérations jusqu'à la convergence. La question critique est la magnitude de $T$.

Théorème 2 (Vattani, 2011). Il existe des ensembles de points dans $\mathbb{R}^2$ pour lesquels l'algorithme de Lloyd (avec une initialisation spécifique) nécessite $2^{\Omega(\sqrt{n})}$ itérations.

Ce résultat, que nous énonçons sans démonstration, montre que le nombre d'itérations dans le pire cas est superpolynomial. Arthur et Vassilvitskii (2006) ont donné la première borne inférieure superpolynomiale ; la construction de Vattani l'a affinée.

En contraste saisissant, l'observation empirique montre systématiquement que $T$ est petit — typiquement $O(1)$ à $O(\log n)$ — sur des données du monde réel. Cet écart a été partiellement expliqué par l'analyse lissée :

Théorème 3 (Arthur et Vassilvitskii, 2009 — énoncé informel). Sous l'analyse lissée (chaque point d'entrée perturbé par un bruit gaussien de variance $\sigma^2$), le nombre attendu d'itérations de l'algorithme de Lloyd est polynomial en $n$ et $1/\sigma$.

Il s'agit d'un résultat profond reliant l'efficacité pratique du $k$-means au fait que les constructions pathologiques du théorème 2 sont des phénomènes de mesure nulle sous perturbation.

3.1.5 NP-Difficulté du $k$-Means Optimal

Théorème 4 (Aloise et al., 2009 ; Dasgupta, 2008 ; Mahajan et al., 2012). Le problème de trouver une $k$-partition minimisant le WCSS (équation 1) est NP-difficile. Plus précisément :

• Il est NP-difficile pour $d$ général même pour $k = 2$ (Aloise et al., 2009).
• Il est NP-difficile dans le plan ($d = 2$) pour $k$ général (Mahajan et al., 2012).

Intuitivement, cela signifie que, sauf si P = NP, il n'existe pas d'algorithme en temps polynomial qui trouve la solution $k$-means globalement optimale. Ce résultat de dureté est ce qui rend théoriquement significatives les garanties d'approximation — comme celles du $k$-means++.

3.1.6 L'Initialisation $k$-Means++

Arthur et Vassilvitskii (2007) ont proposé une procédure d'initialisation randomisée ($k$-means++) qui fournit une garantie d'approximation prouvable avant toute itération de Lloyd.

Algorithme 2 : Initialisation $k$-Means++

Entrée : $X = \{x_1, \dots, x_n\} \subset \mathbb{R}^d, k$.

1. Choisir $\mu_1$ uniformément au hasard dans $X$.
2. Pour $j = 2, \dots, k$ :
   • Pour chaque $x_i \in X$, calculer $D(x_i) = \min_{l < j} \|x_i - \mu_l\|^2$.
   • Choisir $\mu_j = x_i$ avec probabilité $D(x_i) / \sum_{m=1}^n D(x_m)$.

Sortie : Centres initiaux $\mu_1, \dots, \mu_k$.

L'idée clé est la pondération $D^2$ : les points éloignés de tous les centres actuellement sélectionnés sont plus susceptibles d'être choisis comme nouveaux centres. Cela répartit les centres initiaux dans les données.

Théorème 5 (Arthur et Vassilvitskii, 2007). Soit $W^*$ la valeur WCSS optimale et $W_{\text{init}}$ le WCSS après l'initialisation $k$-means++ (avant toute itération de Lloyd). Alors :

Lemme 1 (Lemme de Réduction du Coût). Soit $S = \{\mu_1, \dots, \mu_j\}$ l'ensemble actuel de $j$ centres. Considérons un cluster optimal $C^*_l$ avec centre optimal $\mu^*_l$ et coût optimal $W^*_l = \sum_{x \in C^*_l} \|x - \mu^*_l\|^2$. Si l'on sélectionne un nouveau centre $\mu_{j+1}$ depuis $C^*_l$ avec probabilité proportionnelle à $D^2(x) = \min_{\mu \in S} \|x - \mu\|^2$, alors le nouveau coût attendu des points dans $C^*_l$ est borné par $2W^*_l$.

Démonstration du Lemme 1. Pour tout point $x' \in C^*_l$ sélectionné comme nouveau centre, la contribution au coût depuis $C^*_l$ devient :

En utilisant l'identité (qui découle du développement de la norme au carré) :

La probabilité de sélectionner $x'$ est proportionnelle à $D^2(x')$. En prenant l'espérance sur le tirage pondéré par $D^2$ :

Le premier terme, par la définition de la pondération $D^2$ dans $C^*_l$, contribue au plus $W^*_l$. Par conséquent :

Démonstration du Théorème 5. On procède par récurrence sur le nombre de centres choisis.

Cas de base : Le premier centre $\mu_1$ est choisi uniformément au hasard. Pour chaque cluster optimal $C^*_l$, si $\mu_1 \in C^*_l$, le coût attendu depuis $C^*_l$ est au plus $2W^*_l$ par le Lemme 1.

Étape d'induction : Supposons que nous ayons $j$ centres. Soit $U$ l'ensemble des clusters optimaux « non couverts ». La probabilité que le $(j+1)$-ème centre couvre un cluster non couvert spécifique $C^*_l$ est au moins :

Le nombre attendu de clusters non couverts après $k$ itérations suit un processus de collecte de coupons. En combinant avec le facteur 2 du Lemme 1, on obtient :

Corollaire 1. $k$-means++ réalise une $O(\log k)$-approximation du WCSS optimal en espérance, en temps $\Theta(nkd)$.

---

3.2 DBSCAN

3.2.1 Cadre Formel

Contrairement au $k$-means, DBSCAN (Density-Based Spatial Clustering of Applications with Noise) n'optimise pas une fonction objectif explicite. À la place, il définit géométriquement les clusters comme des ensembles maximaux de points connexes par densité.

Hypothèse 3. Les paramètres $\epsilon > 0$ et $\text{minPts} \in \mathbb{N}$ sont donnés. L'entrée est un ensemble fini $X \subset \mathbb{R}^d$ selon la métrique euclidienne.

Définition 7 (Cluster DBSCAN). Un ensemble $C \subseteq X$ est un cluster DBSCAN (par rapport à $\epsilon$ et $\text{minPts}$) s'il satisfait deux conditions : (i) Connexité : pour tout $x, y \in C$, $x$ et $y$ sont connexes par densité ; et (ii) Maximalité : si $x \in C$ et $y$ est accessible par densité depuis $x$, alors $y \in C$.

Lemme 2 (Symétrie de l'Accessibilité par Densité sur les Points Noyaux). Soit $\text{Core}(X) = \{x \in X : |N_\epsilon(x)| \ge \text{minPts}\}$ l'ensemble des points noyaux. Pour tout $p, q \in \text{Core}(X)$, si $q$ est accessible par densité depuis $p$, alors $p$ est accessible par densité depuis $q$.

Démonstration. Soit $p = p_1, p_2, \dots, p_m = q$ une chaîne témoignant que $q$ est accessible par densité depuis $p$. Puisque $q$ est un point noyau, $|N_\epsilon(q)| \ge \text{minPts}$. Considérons la chaîne inversée $q = p_m, p_{m-1}, \dots, p_1 = p$.

Pour chaque paire consécutive $(p_{i+1}, p_i)$ dans la chaîne originale, on a $p_{i+1} \in N_\epsilon(p_i)$ où $p_i$ est un point noyau. Par symétrie de la métrique euclidienne : $\|p_{i+1} - p_i\| = \|p_i - p_{i+1}\| \le \epsilon$.

Puisque tous les points intermédiaires $p_2, \dots, p_{m-1}$ doivent être des points noyaux, on a $|N_\epsilon(p_i)| \ge \text{minPts}$ pour tout $i \in \{1, \dots, m\}$. Par conséquent, la chaîne inversée témoigne que $p$ est accessible par densité depuis $q$. □

Théorème 6 (Correction de DBSCAN, Ester et al. 1996). Soient $X, \epsilon, \text{minPts}$ donnés. Alors :

(a) La connexité par densité est une relation d'équivalence sur l'ensemble des points noyaux. (b) Chaque cluster DBSCAN contient au moins un point noyau. (c) Les clusters DBSCAN sont précisément les composantes connexes par densité maximales.

Démonstration de (a). Nous vérifions les trois propriétés d'une relation d'équivalence sur $\text{Core}(X)$.

Réflexivité : Tout point noyau $x$ est accessible par densité depuis lui-même (chaîne triviale de longueur 1). Donc $x$ est connexe par densité à lui-même via $z = x$.

Symétrie : Supposons que $x, y \in \text{Core}(X)$ soient connexes par densité via $z$. Puisque $x$ est accessible par densité depuis $z$ et que les deux sont des points noyaux, par le Lemme 2, $z$ est accessible par densité depuis $x$. Par conséquent, $y$ est connexe par densité à $x$ via le même témoin $z$.

Transitivité : Supposons que $x, y$ soient connexes par densité via $z_1$, et que $y, w$ soient connexes par densité via $z_2$. Par le Lemme 2 et la concaténation de chaînes, $x$ et $w$ sont tous deux accessibles par densité depuis $z_1$, ce qui les rend connexes par densité. □

Remarque. L'accessibilité par densité n'est pas symétrique en général (un point frontière est accessible par densité depuis un point noyau, mais pas l'inverse). Cette asymétrie est précisément la raison pour laquelle DBSCAN définit la connexité par densité via un ancêtre commun $z$.

3.2.2 L'Algorithme DBSCAN

Algorithme 3 : DBSCAN

Entrée : $X = \{x_1, \dots, x_n\}$, paramètres $\epsilon, \text{minPts}$.

1. Marquer tous les points comme non visités.
2. Pour chaque point non visité $x \in X$ :
   • Marquer $x$ comme visité. Calculer $N_\epsilon(x)$.
   • Si $|N_\epsilon(x)| < \text{minPts}$ : marquer $x$ comme bruit (provisoirement).
   • Sinon : Créer un nouveau cluster $C$. Ajouter $x$ à $C$. Initialiser l'ensemble de graines $S \leftarrow N_\epsilon(x) \setminus \{x\}$.
   • Tant que $S \neq \emptyset$ :
     • Prendre $y \in S$, le retirer de $S$.
     • Si $y$ est non visité : marquer $y$ comme visité, calculer $N_\epsilon(y)$. Si $|N_\epsilon(y)| \ge \text{minPts}$ : $S \leftarrow S \cup (N_\epsilon(y) \setminus \text{déjà assignés})$.
     • Si $y$ n'est pas encore membre d'un cluster : ajouter $y$ à $C$.

Sortie : Ensemble de clusters et points de bruit.

L'algorithme est essentiellement un parcours de graphe (similaire au BFS) sur le graphe d'accessibilité par densité.

3.2.3 Analyse de la Complexité

Théorème 7 (Complexité de DBSCAN). La complexité temporelle dans le pire cas de DBSCAN est $\Theta(n^2)$ sans indexation spatiale. Avec un index spatial supportant des requêtes de voisinage en $O(\log n + |N_\epsilon(x)|)$, la complexité est $O(n \log n)$ lorsque le nombre total de relations voisins est $O(n)$.

Démonstration. Le coût dominant est le calcul de $N_\epsilon(x)$ pour chaque point. Sans index, chaque requête de voisinage nécessite de parcourir tous les $n$ points : $\Theta(n)$ par requête, donnant $\Theta(n^2)$ au total.

Avec un index spatial tel qu'un $k$-d tree, chaque requête de plage coûte $O(\log n + |N_\epsilon(x)|)$. Le coût total est :

où $M = \sum_{i=1}^n |N_\epsilon(x_i)|$ est le nombre total de relations de voisinage. Dans le pire des cas, $M = \Theta(n^2)$. Cependant, pour des clusters bien séparés ou $\epsilon$ petit, $M = O(n)$ et la complexité devient $O(n \log n)$. □

Hypothèse 4. Le bénéfice de l'indexation spatiale suppose une faible dimensionnalité effective. En haute dimension, les $k$-d trees dégénèrent en balayage linéaire en raison de la malédiction de la dimensionnalité.

---

3.3 Clustering Hiérarchique Agglomératif

3.3.1 Cadre

Le clustering hiérarchique agglomératif (HAC) construit une séquence de partitions en fusionnant itérativement les deux clusters les plus proches, produisant un dendrogramme qui encode simultanément tous les nombres possibles de clusters.

Définition 8 (Fonction de liaison). Une fonction de liaison $\Lambda: 2^X \times 2^X \to \mathbb{R}_{\ge 0}$ assigne une distance entre sous-ensembles. Les choix standards incluent :

• Liaison simple : $\Lambda_{\text{simple}}(A, B) = \min_{a \in A, b \in B} \|a - b\|$
• Liaison complète : $\Lambda_{\text{complète}}(A, B) = \max_{a \in A, b \in B} \|a - b\|$
• Liaison moyenne : $\Lambda_{\text{moyenne}}(A, B) = \frac{1}{|A||B|} \sum_{a \in A} \sum_{b \in B} \|a - b\|$
• Liaison de Ward : $\Lambda_{\text{Ward}}(A, B) = \frac{|A| \cdot |B|}{|A| + |B|} \| \mu(A) - \mu(B) \|^2$

Théorème 8 (Connexion Ward-WCSS). La fusion des clusters $A$ et $B$ augmente le WCSS total exactement de $\Lambda_{\text{Ward}}(A, B)$. Par conséquent, la méthode de Ward est un algorithme glouton qui minimise l'augmentation du WCSS à chaque étape.

Démonstration. Soient $A$ et $B$ deux clusters disjoints avec centroïdes $\mu(A), \mu(B)$, tailles $|A| = n_a, |B| = n_b$.

Après fusion, le nouveau cluster $C = A \cup B$ a pour centroïde :

En appliquant la formule de décomposition de la variance (théorème de Huygens) :

En calculant les termes de décalage et en simplifiant :

Proposition 3 (Complexité du HAC naïf). Le clustering agglomératif naïf s'exécute en temps $\Theta(n^3)$. Avec des files de priorité, la liaison simple peut être calculée en $O(n^2)$ via l'algorithme MST de Prim, et la liaison générale en $O(n^2 \log n)$.

---

3.4 Analyse Comparative

3.4.1 Complexité Computationnelle

Le coût pratique par itération du $k$-means est $\Theta(nkd)$, le rendant linéaire en $n$ par itération pour $k$ et $d$ fixés. Pour $n$ grand ($n > 10^5$), le $k$-means est généralement la seule option réalisable.

3.4.2 Hypothèses Géométriques et Forme des Clusters

Proposition 4 (Structure de Voronoï du $k$-Means). La partition produite par l'algorithme de Lloyd est constituée des intersections de $X$ avec les cellules de Voronoï des centroïdes finaux. Les cellules de Voronoï sont des polytopes convexes, donc le $k$-means ne peut produire que des frontières de clusters convexes.

Contre-exemple 1. Considérons deux cercles concentriques dans $\mathbb{R}^2$ : $C_1 = \{x : \|x\| = 1\}$ et $C_2 = \{x : \|x\| = 3\}$. Toute solution $k$-means avec $k = 2$ partitionne le plan en deux régions convexes, ce qui ne peut pas séparer des cercles concentriques. DBSCAN avec des paramètres $\epsilon$ et $\text{minPts}$ appropriés identifie correctement les deux clusters circulaires.

3.4.3 Indices Formels de Qualité des Clusters

Définition 9 (Coefficient de Silhouette). Pour un point $x_i$ affecté au cluster $C_j$ :

Proposition 5. $s(x_i) \in [-1, 1]$. Les valeurs proches de $+1$ indiquent un bon clustering ; les valeurs proches de $-1$ indiquent une mauvaise affectation.

Définition 10 (Indice de Davies–Bouldin). Pour les clusters $C_1, \dots, C_k$ avec dispersions $\sigma_j$ :

Des valeurs plus faibles indiquent une meilleure séparation.

3.4.4 Conditions de Supériorité des Paradigmes

Condition A (le $k$-Means est approprié) : Les clusters sont approximativement convexes, $k$ est connu, la dimensionnalité est gérable, et la scalabilité à $n$ grand est requise.

Condition B (DBSCAN est approprié) : Les clusters ont des formes arbitraires, les données contiennent du bruit/des valeurs aberrantes, $k$ est inconnu, et la dimensionnalité effective est faible.

Condition C (HAC est approprié) : L'ensemble de données est petit ($n \lesssim 10^4$), la structure hiérarchique est d'intérêt, ou plusieurs niveaux de granularité sont nécessaires.

Théorème 9 (Pas de Repas Gratuit pour le Clustering). Il n'existe pas d'algorithme de clustering simultanément optimal pour toutes les distributions. Ceci peut être formalisé via le théorème d'impossibilité de Kleinberg (2003).

---

4. Comparaison et reproductibilité

Cette section décrit un protocole de comparaison à mettre en œuvre. Elle ne présente pas des expériences exécutées ou des résultats validés. Les anciennes valeurs sans protocole publié ont été retirées.

4.1 Scénarios

Deux scénarios synthétiques permettent d’étudier des hypothèses différentes : des groupes gaussiens bien séparés pour la structure centroïde, et deux demi-cercles imbriqués pour des frontières non convexes. La géométrie exacte, le bruit et les graines doivent être publiés avant toute comparaison chiffrée.

4.2 Critères de comparaison

• Silhouette : comparer la compacité et la séparation, avec une convention explicite pour le bruit et les partitions dégénérées.
• Indice de Rand ajusté (ARI) : comparer la partition aux étiquettes synthétiques connues.
• Coût de calcul : mesurer les durées sur un environnement fixé, en séparant la préparation des données, la construction des index et l’exécution.

4.3 Éléments à publier

Une évaluation reproductible doit fournir le code, les données ou leur générateur, les graines, les paramètres complets des algorithmes, les versions logicielles, le matériel et les sorties brutes. Une comparaison de durées doit préciser les répétitions et leur dispersion. Aucun classement mesuré n’est revendiqué ici.

4.4 Limites d’interprétation

Une observation sur deux jeux synthétiques ne démontre pas une garantie universelle. Les garanties formelles des sections précédentes restent conditionnelles à leurs hypothèses. La figure des deux lunes est une illustration calculée de la géométrie, pas un rapport de benchmark.

---

5. Discussion

5.1 Interprétation

L'analyse révèle une tension fondamentale dans le clustering : entre les approches basées sur l'optimisation ($k$-means) avec des objectifs clairs mais des hypothèses géométriques fortes, et les approches géométriques/topologiques (DBSCAN) avec des formes de clusters flexibles mais sans objectif global. Cette tension reflète l'ambiguïté inhérente au problème de clustering. Le théorème d'impossibilité de Kleinberg (2003) rend cela précis.

Le résultat du $k$-means++ (Théorème 5) est particulièrement significatif car il fournit un algorithme en temps polynomial avec une garantie d'approximation prouvable pour un problème NP-difficile.

5.2 Limitations

Plusieurs hypothèses de notre analyse sont restrictives :

• L'Hypothèse 1 (métrique euclidienne) exclut des cadres importants tels que le clustering avec des divergences de Bregman, les distances d'édition ou les distances de graphe.
• L'Hypothèse 4 (indexation en faible dimension pour DBSCAN) est limitante pour les données modernes en haute dimension.
• Nous n'avons pas analysé le problème de la sélection de $k$ (pour le $k$-means) ou de $\epsilon$ et $\text{minPts}$ (pour DBSCAN).

5.3 Connexions

L'objectif du $k$-means est intimement lié à l'analyse en composantes principales (ACP). La relaxation continue des variables indicatrices du $k$-means récupère une relaxation spectrale résoluble via les premiers vecteurs propres — c'est la base du clustering spectral (von Luxburg, 2007).

DBSCAN se connecte à l'analyse topologique des données : à mesure que $\epsilon$ augmente, le complexe de Vietoris–Rips croît, et les clusters DBSCAN correspondent approximativement aux composantes connexes à une échelle fixée.

5.4 Questions Ouvertes

1. La garantie d'approximation $O(\log k)$ du $k$-means++ peut-elle être améliorée à $O(1)$ ?
2. Existe-t-il un algorithme de clustering basé sur la densité avec des garanties d'optimalité formelles ?
3. Quelle est la dépendance polynomiale précise de la complexité lissée en $n$, $k$ et $1/\sigma$ ?

---

6. Conclusion

Cet article présente une analyse comparative de trois paradigmes de clustering et un protocole d’évaluation reproductible.

Contributions clés :

1. L'algorithme de Lloyd converge comme une procédure de descente de coordonnées par blocs sur l'objectif WCSS (Théorème 1), malgré une complexité en nombre d'itérations superpolynomiale dans le pire cas (Théorème 2).

2. $k$-means++ réalise une $O(\log k)$-approximation du WCSS optimal via un lemme de réduction du coût (Théorème 5).

3. La correction de DBSCAN a été prouvée via un lemme de symétrie rigoureux (Lemme 2, Théorème 6) avec une complexité dans le pire cas en $\Theta(n^2)$.

4. La connexion Ward-WCSS (Théorème 8) établit le clustering hiérarchique comme un minimiseur glouton du WCSS.

Le protocole de comparaison ne constitue pas une validation expérimentale. Le choix des algorithmes dépend des hypothèses géométriques et des critères d’évaluation. Le théorème d'impossibilité de Kleinberg offre l'explication la plus profonde : aucun paradigme de clustering unique ne peut satisfaire simultanément tous les critères naturels.

---