Clustering flou : l’algorithme fuzzy c-means et les points entre les clusters

K-means et son affectation nette, fuzzy c-means avec des appartenances à tous les clusters, le fuzzificateur m, le coefficient de partition et l’indice de Xie–Beni pour choisir le nombre de clusters — et pourquoi les points aberrants reçoivent des appartenances élevées.

13 minutes Matěj Žalmánek 2026-10-15

Série Bases de l’IA Partie 36 sur 52

1. Carte de l’intelligence artificielle : qu’est-ce qui est quoi et comment tout s’emboîte
2. Brève histoire de l’intelligence artificielle : de Turing aux modèles de langage
3. Données, modèle, entraînement, inférence : les notions de base sur un seul exemple
4. Lire la notation mathématique : symboles, indices, sommes et quantificateurs
5. Ensembles et relations : les briques dont sont faites les définitions en IA
6. Fonctions et applications : pourquoi tout modèle d’IA est une fonction
7. Logique et démonstrations : les règles selon lesquelles on raisonne en IA
8. Graphes et arbres : la structure sur laquelle reposent la recherche et les réseaux de neurones
9. Algèbre linéaire pour l’apprentissage automatique : vecteurs, matrices et pourquoi l’IA multiplie surtout
10. Dérivées, gradient et règle de dérivation en chaîne : comment un modèle sait dans quelle direction apprendre
11. Descente de gradient : comment un modèle apprend
12. Qu’est-ce que la probabilité : du lancer de dé aux axiomes de Kolmogorov
13. Probabilité conditionnelle et théorème de Bayes : comment réviser une estimation quand on apprend du nouveau
14. Variable aléatoire et fonction de répartition : une seule fonction qui dit tout de la loi
15. Fonction de densité et fonction de masse : pourquoi une variable continue a une probabilité nulle en chaque point
16. Espérance, variance et covariance : où se situe une loi, quelle est sa largeur et ce qui varie avec quoi
17. Panorama des lois de probabilité : Bernoulli, binomiale, Poisson, uniforme, normale et exponentielle
18. Loi des grands nombres et théorème central limite : pourquoi les moyennes sont si prévisibles
19. Statistique et estimation de paramètres : maximum de vraisemblance, MAP et intervalles de confiance
20. Théorie de l’information : entropie, entropie croisée et divergence KL — d’où viennent les fonctions de perte
21. Recherche dans l’espace d’états : BFS, DFS, UCS et A* en animations
22. Jeux et adversaires : minimax, élagage alpha-bêta et Monte Carlo tree search
23. Satisfaction de contraintes : backtracking, propagation de contraintes et AC-3 sur un sudoku et une carte des régions tchèques
24. Logique et systèmes à base de connaissances : chaînage avant et arrière, résolution et systèmes experts
25. Planification : STRIPS, monde des blocs, heuristiques par relaxation et planification dans les agents IA
26. Recherche locale et recuit simulé : un voyageur de commerce à travers les chefs-lieux de région tchèques
27. Algorithmes génétiques : population, croisement, mutation et sélection sur un sac à dos de randonnée
28. Stratégies d’évolution et programmation génétique : de la règle du cinquième à la loi de Kepler
29. Optimisation par colonies de fourmis : comment une piste de phéromone trouve un chemin court
30. Optimisation par essaim de particules : inertie, expérience propre et expérience de l’essaim
31. Neuroévolution : faire évoluer les poids et la forme des réseaux de neurones, et l’algorithme NEAT
32. Ensembles flous et fonctions d’appartenance : comment écrire « un peu chaud »
33. Logique floue et probabilité : pourquoi « un peu chaud » ne veut pas dire « probablement chaud »
34. Logique floue : t-normes, implications et règles SI–ALORS
35. Commande floue : Mamdani et Sugeno, du ventilateur au pendule inversé sur un chariot
36. Clustering flou : l’algorithme fuzzy c-means et les points entre les clusters
37. Systèmes neuro-flous (ANFIS) : des règles floues qui apprennent à partir des données
38. Chaînes de Markov : matrice de transition, distribution stationnaire et PageRank
39. Modèles de Markov cachés : l’algorithme de Viterbi et le casino malhonnête
40. Réseaux bayésiens : pourquoi l’herbe est mouillée et ce que cela implique pour l’arroseur
41. Le filtre de Kalman : comment estimer, à partir de mesures imprécises, où se trouve une voiture et à quelle vitesse elle roule
42. Types d’apprentissage automatique : supervisé, non supervisé, semi-supervisé et plus
43. Prompts, contexte et RAG : comment donner au modèle les bonnes informations
44. Autoencodeurs variationnels (VAE) : de nouvelles images à partir d’un espace latent continu
45. Réseaux antagonistes génératifs (GAN) : le faussaire contre le détective
46. Modèles de diffusion : comment une image naît du bruit pur
47. Processus de décision markoviens : états, actions, récompenses et équations de Bellman
48. Q-learning et DQN : apprendre la valeur des actions, du tableau au réseau de neurones
49. Policy gradient et PPO : apprendre directement la politique
50. Comment fonctionne un agent IA : un modèle de langage en boucle avec des outils
51. Programmer avec des agents IA : consigne, tests et vérification
52. Évaluation et sécurité des systèmes d’IA : comment mesurer et comment surveiller

Programme complet de la série 52 sur 83 sujets publiés

Le clustering cherche dans les données des groupes dont on ne sait rien à l’avance : des clients au comportement d’achat similaire, des zones d’un même tissu sur une image d’IRM, des documents sur des thèmes proches. L’algorithme classique k-means affecte chaque point à un seul et unique groupe. Mais les données réelles comportent souvent des points à la frontière — un client qui achète un peu comme un étudiant et un peu comme un parent, un pixel où se rencontrent la substance grise et la substance blanche du cerveau. Le clustering flou permet à un point d’appartenir à plusieurs groupes à la fois, un peu à chacun.

Il fait suite aux épisodes Ensembles flous et fonctions d’appartenance et Types d’apprentissage automatique, où le clustering est apparu comme une tâche typique de l’apprentissage non supervisé.

1. Clustering net : k-means

Définition — problème des k-means

Pour des points x₁, …, x_n ∈ ℝ^d et un nombre de clusters c, on cherche des centres v₁, …, v_c et une affectation des points aux clusters qui minimisent

J = ∑_i=1ⁿ ‖x_i − v_shluk(i)‖².

L’algorithme de Lloyd alterne deux étapes : affecte chaque point au centre le plus proche ; recalcule chaque centre comme la moyenne de ses points. Répète tant que l’affectation change.

Définition — distance euclidienne

Pour des points x, v ∈ ℝ^d, ‖x − v‖ = √( ∑_r=1^d (x_r − v_r)² ). Dans le plan, c’est la longueur ordinaire d’un segment, par exemple du point M1 = (4,5 ; 2,5) au centre du cluster A (1,73 ; 2,31) tel que le trouve plus bas fuzzy c-means : √(2,77² + 0,19²) ≈ 2,78. Le clustering travaille avec le carré ‖·‖² — la racine disparaît et les points éloignés sont davantage pénalisés.

def kmeans(X, c):
    V = c points de X choisis au hasard           # centres initiaux
    while True:
        shluk = [argmin_j ‖x − V[j]‖² for x in X]  # étape d’affectation
        if shluk n’a pas changé: return V, shluk
        for j in range(c):                         # étape des centres
            V[j] = moyenne des points x tels que shluk(x) = j

Théorème — l’algorithme de Lloyd s’arrête

Aucune étape n’augmente J, et l’algorithme s’arrête donc après un nombre fini d’étapes.

Démonstration : Affectation : chaque terme ‖x_i − v_shluk(i)‖² est remplacé par le plus petit de tous les ‖x_i − v_j‖², il n’augmente donc pas. Centres : pour les points S d’un cluster de moyenne x̄, on a la décomposition

∑_i∈S ‖x_i − v‖² = ∑_i∈S ‖x_i − x̄‖² + |S| · ‖x̄ − v‖²

(le terme croisé 2 ∑ (x_i − x̄) · (x̄ − v) est nul, car ∑ (x_i − x̄) = 0). La somme est donc minimale pour v = x̄. Il n’existe qu’un nombre fini de partitions de n points en c clusters et J diminue strictement à chaque changement d’affectation (à distance égale, on laisse le point dans son cluster), donc aucune partition ne se répète. ∎

Le théorème ne dit rien sur le fait que la partition trouvée soit celle de plus petit J — seulement que l’algorithme ne bouclera pas.

Nos données : trois groupes de 40 points — A en bas à gauche, B à droite et C en haut —, quatre points à la frontière (M1–M4) et deux points aberrants loin de tout (O1, O2). K-means s’est stabilisé après quatre itérations :

Il a bien trouvé les clusters, mais il a dû trancher pour les points à la frontière : il a mis M1, M3 et M4 dans B, M2 dans A. Or le point M3 se trouve presque exactement entre B et C — k-means n’en dit rien. Et les deux points aberrants sont tombés dans le cluster C, comme s’ils lui appartenaient autant que son noyau.

2. Fuzzy c-means

Définition — fuzzy c-means (Dunn 1973, Bezdek 1981)

Au lieu d’une affectation, on cherche une matrice d’appartenance U = (u_ij), u_ij ∈ [0, 1], où pour chaque point ∑_j u_ij = 1, et des centres v_j qui minimisent

J_m = ∑_i ∑_j u_ij^m ‖x_i − v_j‖²,

où m > 1 est le fuzzificateur. L’algorithme alterne deux étapes qui découlent des conditions d’optimalité :

v_j = ∑_i u_ij^m x_i / ∑_i u_ij^m,    u_ij = 1 / ∑_k (d_ij / d_ik)^2/(m−1),

où d_ij = ‖x_i − v_j‖.

J_m = ∑_i=1ⁿ ∑_j=1^c u_ij^m ‖x_i − v_j‖²,    ∑_j u_ij = 1

J_m

le « coût » total de la partition — l’algorithme le minimise ; il est faible quand les points appartiennent surtout aux centres qui sont proches d’eux

∑_i ∑_j

chaque point est compté pour chaque cluster — contrairement à k-means, où l’on ne prenait qu’un cluster par point

u_ij

appartenance du point i au cluster j — le poids avec lequel la distance entre dans le coût

^m

fuzzificateur — sans puissance (m = 1), il serait avantageux de donner tout le « un » au centre le plus proche et l’on retomberait sur k-means ; avec m > 1, partager devient avantageux : un point à égale distance de deux centres ne paie, pour m = 2 et un partage moitié-moitié, que (½² + ½²) · d² = ½d² au lieu de d²

‖x_i − v_j‖²

carré de la distance — ce que coûte d’avoir le point « chez » ce centre ; un centre éloigné revient cher

∑_j u_ij = 1

contrainte — sans elle, le minimum serait trivial : tous les u_ij = 0 et un coût nul

u_ij = 1 / ∑_k=1^c ( d_ij / d_ik )^2/(m−1)

u_ij

nouvelle appartenance du point i au cluster j à centres fixés

d_ij / d_ik

rapport des distances — combien de fois le centre j est plus loin que le centre k ; le rapport (et non la différence) rend le résultat indépendant de l’échelle des données

^2/(m−1)

avec quelle netteté le rapport tranche — pour m = 2 il vaut 2, donc un centre deux fois plus proche reçoit quatre fois plus ; pour m → 1 l’exposant croît sans limite et tout revient au centre le plus proche

∑_k

comparaison avec tous les centres, y compris j lui-même (le terme k = j vaut 1) — grâce à cela, les appartenances d’un point ont pour somme exactement 1

Théorème — d’où viennent les deux étapes

Appartenances à centres fixés. Pour un point i, on minimise ∑_j u_ij^m d_ij² sous la contrainte ∑_j u_ij = 1. Le lagrangien est L = ∑_j u_ij^m d_ij² − λ (∑_j u_ij − 1). De ∂L/∂u_ij = m u_ij^m−1 d_ij² − λ = 0 découle u_ij = (λ/m)^1/(m−1) · d_ij^−2/(m−1). En substituant dans la contrainte de somme, l’inconnue λ se simplifie et il reste

u_ij = d_ij^−2/(m−1) / ∑_k d_ik^−2/(m−1) = 1 / ∑_k (d_ij / d_ik)^2/(m−1).

On obtient des nombres positifs, il n’est donc pas nécessaire de surveiller séparément la contrainte u_ij ≥ 0. (Si un point se trouve exactement sur un centre, d_ij = 0, il reçoit une appartenance 1 à ce cluster ; notre implémentation le gère en ne laissant jamais la distance descendre sous 10⁻¹².)

Centres à appartenances fixées. J_m est une fonction quadratique convexe en v_j et ∂J_m/∂v_j = −2 ∑_i u_ij^m (x_i − v_j) = 0 donne v_j = ∑_i u_ij^m x_i / ∑_i u_ij^m.

Chaque étape minimise donc J_m à l’autre groupe de variables fixé et ne peut pas l’augmenter — le même argument que pour k-means. Bezdek et al. (1987, correction du théorème original de Bezdek de 1980) ont montré que la suite a ses points d’accumulation en des points stationnaires de J_m (pas nécessairement au minimum global).

import numpy as np

def fcm(X, c, m=2.0, iteraci=100, eps=1e-5):
    U = np.random.dirichlet(np.ones(c), size=len(X))        # appartenances aléatoires, ligne = 1
    for _ in range(iteraci):
        W = U ** m
        V = (W.T @ X) / W.sum(axis=0)[:, None]             # centres comme moyennes pondérées
        D = np.linalg.norm(X[:, None, :] - V[None, :, :], axis=2) + 1e-12
        nove = 1 / ((D[:, :, None] / D[:, None, :]) ** (2 / (m - 1))).sum(axis=2)
        if np.abs(nove - U).max() < eps:
            return V, nove
        U = nove
    return V, U

3. Fuzzy c-means sur nos données

La couleur d’un point est maintenant un mélange des couleurs des clusters selon les appartenances : un point vert pur n’appartient qu’à A, un point « entre » le vert et l’orange est en partie dans A et en partie dans B. Les lignes pointillées montrent comment les centres se sont déplacés — l’algorithme s’est stabilisé après neuf itérations :

On voit maintenant ce que k-means a passé sous silence. M1 est presque à mi-chemin entre A et B ; M3 est en fait un cheveu plus dans C que dans B, bien que k-means l’ait mis dans B ; et M4, au milieu du triangle, appartient un peu aux trois. Les points des noyaux des clusters ont une appartenance à leur cluster proche de un. Les centres sont pratiquement les mêmes qu’avec k-means — fuzzy c-means ne change pas où sont les clusters, mais ajoute l’information de avec quelle certitude chaque point leur appartient.

Exemple — appartenances du point M1 = (4,5 ; 2,5)

Centres après neuf itérations : A ≈ (1,73 ; 2,31), B ≈ (7,12 ; 2,87), C ≈ (4,51 ; 7,11). Pour m = 2, les inverses des carrés des distances suffisent :

Cluster	d2	1/d2	u = (1/d2) / 0,3190
A	2,772 + 0,192 ≈ 7,72	0,1296	0,41
B	2,622 + 0,372 ≈ 7,03	0,1423	0,45
C	0,012 + 4,612 ≈ 21,25	0,0471	0,15
somme		0,3190	1,00

M1 est presque aussi loin des centres A et B (7,72 contre 7,03), et se partage donc presque à moitié entre eux ; C est trois fois plus loin (au carré), et ne reçoit donc que le reste.

4. Le fuzzificateur m

Définition — coefficient de partition

Le coefficient de partition (partition coefficient) est PC = (1/n) ∑_i ∑_j u_ij². Il vaut 1 pour une partition nette et 1/c quand chaque point appartient également à tous les clusters.

PC = (1/n) ∑_i ∑_j u_ij²

PC

netteté de toute la partition, un nombre de [1/c ; 1]

(1/n) ∑_i

moyenne sur les points — pour pouvoir comparer des jeux de données de tailles différentes

∑_j u_ij²

netteté d’un seul point — le carré « récompense » une appartenance concentrée : (1, 0, 0) donne 1, (⅓, ⅓, ⅓) seulement ⅓ ; à somme fixée égale à 1, la somme des carrés est minimale quand toutes les parts sont égales

Pour m proche de 1, fuzzy c-means se rapproche de k-means : le coefficient de partition vaut 0,98 et le point M4 appartient à B à 0,79. Pour m = 2, le coefficient vaut 0,84 et pour m = 5 seulement 0,42 — les couleurs se fondent et même un point du noyau du cluster A n’a qu’une appartenance de 0,45 à A. Pour m → ∞, toutes les appartenances tendraient vers 1/3. On utilise le plus souvent m = 2 : assez souple pour que les points à la frontière soient visibles, et assez net pour que les clusters restent distincts.

Exemple — un point deux fois plus proche de l’un des deux centres

Un point est à distance 1 du centre 1 et à distance 2 du centre 2. D’après la formule, u₁ = 1 / (1 + (1/2)^2/(m−1)) :

• m = 1,2 : exposant 10, u₁ = 1 / (1 + 1/1 024) ≈ 0,999 — affectation pratiquement nette,
• m = 2 : exposant 2, u₁ = 1 / (1 + 1/4) = 0,8,
• m = 5 : exposant 0,5, u₁ = 1 / (1 + 0,707) ≈ 0,586,
• m → ∞ : exposant → 0, (1/2)⁰ = 1 et u₁ → 1/2.

En général : pour m → 1⁺, l’exposant 2/(m − 1) tend vers l’infini, les rapports d_ij/d_ik < 1 tendent vers zéro et ceux > 1 vers l’infini, donc le centre le plus proche reçoit 1 et les autres 0 (k-means). Pour m → ∞, l’exposant tend vers zéro, les c termes de la somme tendent tous vers 1 et u_ij → 1/c.

5. Combien de clusters ?

Le nombre de clusters doit être fourni à l’algorithme. Si on ne le connaît pas, on le lance pour différentes valeurs de c et on compare la qualité des partitions. Le coefficient de partition et l’indice de Xie–Beni s’y prêtent bien.

Définition — indice de Xie–Beni

XB = ∑_i ∑_j u_ij^m ‖x_i − v_j‖² / (n · min_{j ≠ k} ‖v_j − v_k‖²) — plus il est petit, mieux c’est.

XB = ∑_i ∑_j u_ij^m ‖x_i − v_j‖² / ( n · min_{j ≠ k} ‖v_j − v_k‖² )

XB

rapport « dispersion à l’intérieur des clusters / distance entre eux » — plus petit est meilleur

∑ ∑ u_ij^m ‖x_i − v_j‖²

compacité — exactement la valeur de J_m que l’algorithme a minimisée

n

nombre de points — fait du numérateur une moyenne par point, pour que l’indice ne croisse pas avec la taille des données

min_{j ≠ k} ‖v_j − v_k‖²

séparation — c’est la paire de centres la plus proche qui décide ; J_m seul ne fait que diminuer quand on ajoute des clusters, et ce terme pénalise une partition qui scinde un vrai cluster en deux clusters proches

Exemple — indice de Xie–Beni pour c = 3

À la fin de l’algorithme, J₂ ≈ 166,73. Carrés des distances entre centres : A–B ≈ 29,4, A–C ≈ 30,8, B–C ≈ 24,79 (les plus proches sont B et C). Pour n = 126 points :

XB = 166,73 / (126 · 24,79) = 166,73 / 3 124 ≈ 0,053.

Les deux indicateurs s’accordent sur les trois clusters que nous avons placés dans les données. Sur des données réelles, un tel accord ne va pas de soi et les indicateurs sont davantage un repère qu’un verdict.

6. Où fuzzy c-means échoue

Regardez les points aberrants : O1 en haut à droite a une appartenance de 0,45 à C et de 0,39 à B ; O2 en haut à gauche, même 0,58 à C. Pourtant, ils n’appartiennent à aucun cluster. La faute en revient à la contrainte ∑_j u_ij = 1 : le point doit distribuer son « un » à quelqu’un, même s’il est loin de tous. L’appartenance signifie ici plutôt « de qui il est le plus proche » que « à quel point il a sa place ici ».

Exemple — pourquoi O2 = (0,2 ; 9,5) « appartient » à C

Carrés des distances aux centres : A ≈ 54,07, B ≈ 91,88, C ≈ 24,29. Même du centre le plus proche, C, il est donc à 4,9 — plus de six fois l’écart-type de 0,8 avec lequel les points des clusters sont dispersés autour des centres. Les inverses 0,0185, 0,0109 et 0,0412 donnent une somme de 0,0706 et des appartenances de 0,26, 0,15 et 0,58. La formule ne voit que les rapports des distances, pas leur grandeur : plus le point serait loin, plus les rapports se rapprocheraient de 1 et les appartenances de ⅓ — mais elles ne tendraient jamais vers zéro.

Définition — possibilistic c-means (Krishnapuram et Keller, 1993)

On supprime la contrainte de somme et on ajoute au coût un terme qui empêche la solution triviale u = 0 :

J = ∑_i ∑_j u_ij^m d_ij² + ∑_j η_j ∑_i (1 − u_ij)^m,    d’où u_ij = 1 / (1 + (d_ij² / η_j)^1/(m−1)).

η_j est le « rayon » du cluster j : un point à la distance d² = η_j a une appartenance de ½, et pour m = 2 un point avec d² = 9η_j seulement 0,1. L’appartenance dépend maintenant de la distance à un seul centre, et non du rapport aux autres — un point aberrant reçoit de petites valeurs partout.

• Possibilistic c-means (Krishnapuram et Keller, 1993) supprime la contrainte de somme — un point aberrant reçoit alors de petites appartenances à tous les clusters.
• Forme des clusters. La distance euclidienne produit des clusters ronds. L’algorithme de Gustafson et Kessel (1979) donne à chaque cluster sa propre matrice de distance et trouve aussi des ellipses allongées.
• Position initiale. Comme k-means, il peut finir dans un moins bon minimum local — en pratique, on le lance plusieurs fois depuis différents départs.

7. Le clustering flou en pratique

• Imagerie médicale. La segmentation d’images IRM du cerveau en substance grise, substance blanche et liquide cérébrospinal est une application classique : un pixel à la frontière des tissus contient réellement les deux.
• Segmentation de la clientèle. Un client peut appartenir en partie à plusieurs groupes, et le marketing peut en tenir compte.
• Un cousin probabiliste. Les mélanges gaussiens appris par l’algorithme EM affectent eux aussi les points aux clusters de manière « souple » — mais avec des probabilités, pas des appartenances. Les résultats sont souvent semblables, l’interprétation diffère exactement comme l’a décrit l’épisode sur la logique floue et les probabilités.
• Embeddings. Des textes transformés en vecteurs par un modèle de langage peuvent être regroupés de la même manière ; l’affectation souple révèle alors les documents qui se trouvent entre plusieurs thèmes.

8. Résumé

• K-means affecte chaque point à un seul cluster et ne dit rien des points à la frontière.
• Fuzzy c-means cherche des appartenances u_ij de somme 1 et des centres comme moyennes pondérées ; il alterne deux étapes simples.
• Sur nos données, il a trouvé les mêmes centres que k-means et a montré en plus que les points M1–M4 appartiennent à deux ou trois clusters à la fois.
• Le fuzzificateur m règle la souplesse de la partition ; le coefficient de partition et l’indice de Xie–Beni aident à choisir le nombre de clusters.
• La contrainte de somme égale à 1 donne aux points aberrants des appartenances élevées ; les variantes possibilistes y remédient.

Envie d’essayer par vous-même ? Demandez à un agent IA de lancer fuzzy c-means sur les couleurs des pixels d’une de vos photos et de la recolorer selon les clusters — et regardez quels pixels se trouvent « entre » les couleurs.

Vous voyez les choses autrement ? Écrivez à support@coden-app.com.