Clustering fuzzy: l’algoritmo fuzzy c-means e i punti tra i cluster

Il k-means e la sua assegnazione netta, il fuzzy c-means con appartenenze a tutti i cluster, il fuzzificatore m, il coefficiente di partizione e l’indice di Xie–Beni per scegliere il numero di cluster — e perché i punti anomali ricevono appartenenze alte.

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

Serie Basi di IA Parte 36 di 52

1. Mappa dell’intelligenza artificiale: che cos’è ciascuna cosa e come si incastra tutto
2. Breve storia dell’intelligenza artificiale: da Turing ai modelli linguistici
3. Dati, modello, addestramento, inferenza: i concetti di base su un unico esempio
4. Come leggere la notazione matematica: simboli, indici, sommatorie e quantificatori
5. Insiemi e relazioni: i mattoncini con cui si costruiscono le definizioni nell’IA
6. Funzioni e applicazioni: perché ogni modello di IA è una funzione
7. Logica e dimostrazioni: le regole con cui si ragiona nell’IA
8. Grafi e alberi: la struttura su cui poggiano la ricerca e le reti neurali
9. Algebra lineare per l’apprendimento automatico: vettori, matrici e perché l’IA soprattutto moltiplica
10. Derivate, gradiente e regola della catena: come un modello capisce in quale direzione imparare
11. Discesa del gradiente: come impara un modello
12. Che cos’è la probabilità: dal lancio di un dado agli assiomi di Kolmogorov
13. Probabilità condizionata e teorema di Bayes: come cambiare una stima quando scopri qualcosa di nuovo
14. Variabile aleatoria e funzione di ripartizione: una sola funzione che dice tutto sulla distribuzione
15. Funzione di densità e funzione di massa: perché una variabile continua ha probabilità zero in un punto
16. Valore atteso, varianza e covarianza: dove si trova una distribuzione, quanto è larga e che cosa è legato a che cosa
17. Panoramica delle distribuzioni di probabilità: Bernoulli, binomiale, Poisson, uniforme, normale ed esponenziale
18. Legge dei grandi numeri e teorema del limite centrale: perché le medie si comportano in modo così prevedibile
19. Statistica e stima dei parametri: massima verosimiglianza, MAP e intervalli di confidenza
20. Teoria dell’informazione: entropia, entropia incrociata e divergenza KL — da dove vengono le funzioni di perdita
21. Ricerca nello spazio degli stati: BFS, DFS, UCS e A* con animazioni
22. Giochi e avversari: minimax, potatura alfa-beta e Monte Carlo tree search
23. Soddisfacimento di vincoli: backtracking, propagazione dei vincoli e AC-3 su un sudoku e una mappa delle regioni ceche
24. Logica e sistemi basati sulla conoscenza: concatenazione in avanti e all’indietro, risoluzione e sistemi esperti
25. Pianificazione: STRIPS, il mondo dei blocchi, euristiche dal rilassamento e pianificazione negli agenti IA
26. Ricerca locale e ricottura simulata: un commesso viaggiatore tra i capoluoghi di regione cechi
27. Algoritmi genetici: popolazione, incrocio, mutazione e selezione su uno zaino per l’escursione
28. Strategie evolutive e programmazione genetica: dalla regola di un quinto alla legge di Keplero
29. Ottimizzazione con colonie di formiche: come una traccia di feromone trova un percorso breve
30. Ottimizzazione a sciame di particelle: inerzia, esperienza propria ed esperienza dello sciame
31. Neuroevoluzione: evoluzione dei pesi e della forma delle reti neurali e l’algoritmo NEAT
32. Insiemi fuzzy e funzioni di appartenenza: come scrivere «un po’ caldo»
33. Logica fuzzy e probabilità: perché «un po’ caldo» non significa «probabilmente caldo»
34. Logica fuzzy: t-norme, implicazioni e regole SE–ALLORA
35. Controllo fuzzy: Mamdani e Sugeno, dal ventilatore al pendolo inverso su un carrello
36. Clustering fuzzy: l’algoritmo fuzzy c-means e i punti tra i cluster
37. Sistemi neuro-fuzzy (ANFIS): regole fuzzy che imparano dai dati
38. Catene di Markov: matrice di transizione, distribuzione stazionaria e PageRank
39. Modelli di Markov nascosti: l’algoritmo di Viterbi e il casinò disonesto
40. Reti bayesiane: perché l’erba è bagnata e che cosa significa per l’irrigatore
41. Filtro di Kalman: come stimare da misure imprecise dove si trova un’auto e a che velocità va
42. Tipi di apprendimento automatico: supervisionato, non supervisionato, semi-supervisionato e altri
43. Prompt, contesto e RAG: come dare a un modello le informazioni giuste
44. Autoencoder variazionali (VAE): immagini nuove da uno spazio latente continuo
45. Reti generative avversarie (GAN): il falsario contro il detective
46. Modelli di diffusione: come il rumore puro diventa un’immagine
47. Processi decisionali di Markov: stati, azioni, ricompense ed equazioni di Bellman
48. Q-learning e DQN: imparare il valore delle azioni, dalla tabella alla rete neurale
49. Policy gradient e PPO: imparare direttamente la politica
50. Come funziona un agente IA: un modello linguistico in un ciclo con strumenti
51. Programmare con agenti IA: incarico, test e controllo
52. Valutazione e sicurezza dei sistemi di IA: come misurare e come sorvegliare

Programma completo della serie 52 di 83 argomenti pubblicati

Il clustering cerca nei dati gruppi di cui in anticipo non sappiamo nulla: clienti con abitudini d’acquisto simili, zone dello stesso tessuto in un’immagine di risonanza magnetica, documenti su temi affini. Il classico algoritmo k-means assegna ogni punto a esattamente un gruppo. Ma i dati reali hanno spesso punti di confine — un cliente che compra un po’ come uno studente e un po’ come un genitore, un pixel in cui si incontrano la sostanza grigia e quella bianca del cervello. Il clustering fuzzy permette a un punto di appartenere a più gruppi contemporaneamente, a ciascuno un po’.

Si collega alle parti Insiemi fuzzy e funzioni di appartenenza e Tipi di apprendimento automatico, dove il clustering è comparso come compito tipico dell’apprendimento non supervisionato.

1. Clustering netto: k-means

Definizione — il problema del k-means

Dati i punti x₁, …, x_n ∈ ℝ^d e il numero di cluster c, cerchiamo i centri v₁, …, v_c e un’assegnazione dei punti ai cluster che minimizzino

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

L’algoritmo di Lloyd alterna due passi: assegna ogni punto al centro più vicino; ricalcola ogni centro come media dei suoi punti. Ripeti finché l’assegnazione cambia.

Definizione — distanza euclidea

Per i punti x, v ∈ ℝ^d si ha ‖x − v‖ = √( ∑_r=1^d (x_r − v_r)² ). Nel piano è la comune lunghezza di un segmento, per esempio dal punto M1 = (4,5; 2,5) al centro del cluster A (1,73; 2,31), come lo troverà più avanti il fuzzy c-means: √(2,77² + 0,19²) ≈ 2,78. Il clustering lavora con il quadrato ‖·‖² — sparisce la radice e i punti lontani vengono penalizzati di più.

def kmeans(X, c):
    V = c punti scelti a caso da X                # centri iniziali
    while True:
        shluk = [argmin_j ‖x − V[j]‖² for x in X]  # passo di assegnazione
        if shluk non è cambiato: return V, shluk
        for j in range(c):                         # passo dei centri
            V[j] = media dei punti x per cui shluk(x) = j

Teorema — l’algoritmo di Lloyd termina

Nessun passo aumenta J, e l’algoritmo quindi termina dopo un numero finito di passi.

Dimostrazione: Assegnazione: ogni termine ‖x_i − v_shluk(i)‖² viene sostituito dal più piccolo di tutti i ‖x_i − v_j‖², quindi non aumenta. Centri: per i punti S di un cluster con media x̄ vale la scomposizione

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

(il termine misto 2 ∑ (x_i − x̄) · (x̄ − v) è nullo, perché ∑ (x_i − x̄) = 0). La somma è quindi minima per v = x̄. Le partizioni di n punti in c cluster sono in numero finito e J a ogni cambio di assegnazione diminuisce strettamente (a parità di distanza lasciamo il punto nel suo cluster), quindi nessuna partizione si ripete. ∎

Il teorema non dice nulla sul fatto che la partizione trovata sia quella con il J più piccolo — solo che l’algoritmo non entrerà in un ciclo.

I nostri dati: tre gruppi da 40 punti — A in basso a sinistra, B a destra e C in alto —, quattro punti di confine (M1–M4) e due punti anomali lontani da tutto (O1, O2). Il k-means si è stabilizzato dopo quattro iterazioni:

Ha trovato bene i cluster, ma sui punti di confine ha dovuto decidere: M1, M3 e M4 li ha messi in B, M2 in A. Eppure il punto M3 sta quasi esattamente tra B e C — il k-means non lo dice. Ed entrambi i punti anomali sono finiti nel cluster C, come se gli appartenessero quanto il suo nucleo.

2. Fuzzy c-means

Definizione — fuzzy c-means (Dunn 1973, Bezdek 1981)

Invece di un’assegnazione cerchiamo una matrice delle appartenenze U = (u_ij), u_ij ∈ [0, 1], in cui per ogni punto ∑_j u_ij = 1, e i centri v_j che minimizzano

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

dove m > 1 è il fuzzificatore. L’algoritmo alterna due passi che discendono dalle condizioni di ottimalità:

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

dove 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

il «costo» complessivo della partizione — l’algoritmo lo minimizza; è piccolo quando i punti appartengono soprattutto ai centri a cui sono vicini

∑_i ∑_j

ogni punto viene contato per ogni cluster — a differenza del k-means, dove si prendeva un solo cluster per punto

u_ij

appartenenza del punto i al cluster j — il peso con cui la distanza entra nel costo

^m

fuzzificatore — senza potenza (m = 1) converrebbe dare tutto l’«uno» al centro più vicino e si tornerebbe al k-means; con m > 1 conviene dividere: un punto ugualmente lontano da due centri paga, con m = 2 e una divisione a metà, solo (½² + ½²) · d² = ½d² invece di d²

‖x_i − v_j‖²

quadrato della distanza — quanto costa avere il punto «presso» questo centro; un centro lontano risulta caro

∑_j u_ij = 1

vincolo — senza di esso il minimo sarebbe banale: tutti gli u_ij = 0 e costo zero

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

u_ij

nuova appartenenza del punto i al cluster j a centri fissati

d_ij / d_ik

rapporto delle distanze — quante volte il centro j è più lontano del centro k; il rapporto (non la differenza) rende il risultato indipendente dalla scala dei dati

^2/(m−1)

quanto nettamente decide il rapporto — per m = 2 vale 2, quindi un centro due volte più vicino riceve quattro volte di più; per m → 1 l’esponente cresce oltre ogni limite e tutto va al centro più vicino

∑_k

confronto con tutti i centri, compreso j stesso (il termine k = j vale 1) — grazie a questo le appartenenze di un punto sommano esattamente a 1

Teorema — da dove vengono i due passi

Appartenenze a centri fissati. Per un punto i minimizziamo ∑_j u_ij^m d_ij² con il vincolo ∑_j u_ij = 1. La lagrangiana è L = ∑_j u_ij^m d_ij² − λ (∑_j u_ij − 1). Da ∂L/∂u_ij = m u_ij^m−1 d_ij² − λ = 0 segue u_ij = (λ/m)^1/(m−1) · d_ij^−2/(m−1). Sostituendo nel vincolo sulla somma l’incognita λ si semplifica e resta

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

Sono risultati numeri positivi, quindi il vincolo u_ij ≥ 0 non va controllato a parte. (Se un punto sta esattamente in un centro, d_ij = 0, riceve appartenenza 1 a quel cluster; la nostra implementazione lo gestisce facendo sì che la distanza non scenda mai sotto 10⁻¹².)

Centri ad appartenenze fissate. J_m è in v_j una funzione quadratica convessa e ∂J_m/∂v_j = −2 ∑_i u_ij^m (x_i − v_j) = 0 dà v_j = ∑_i u_ij^m x_i / ∑_i u_ij^m.

Ogni passo quindi minimizza J_m rispetto a un gruppo di variabili tenendo fisso l’altro e non può aumentarlo — lo stesso argomento del k-means. Bezdek e coautori (1987, correzione del teorema originale di Bezdek del 1980) hanno mostrato che la successione ha punti di accumulazione nei punti stazionari di J_m (non necessariamente nel minimo globale).

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))        # appartenenze casuali, riga = 1
    for _ in range(iteraci):
        W = U ** m
        V = (W.T @ X) / W.sum(axis=0)[:, None]             # centri come medie pesate
        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 sui nostri dati

Il colore di un punto è ora una miscela dei colori dei cluster secondo le appartenenze: un punto verde puro appartiene solo ad A, un punto «a metà» tra verde e arancione sta in parte in A e in parte in B. Le linee tratteggiate mostrano come si sono spostati i centri — l’algoritmo si è stabilizzato dopo nove iterazioni:

Ora si vede che cosa il k-means ha taciuto. M1 sta quasi a metà tra A e B; M3 in realtà è un pelo più in C che in B, anche se il k-means l’ha messo in B; e M4, al centro del triangolo, appartiene un po’ a tutti e tre. I punti nei nuclei dei cluster hanno un’appartenenza al proprio cluster vicina a uno. I centri sono risultati praticamente uguali a quelli del k-means — il fuzzy c-means non cambia dove sono i cluster, ma aggiunge l’informazione su quanto sicuramente ciascun punto vi appartiene.

Esempio — appartenenze del punto M1 = (4,5; 2,5)

Centri dopo nove iterazioni: A ≈ (1,73; 2,31), B ≈ (7,12; 2,87), C ≈ (4,51; 7,11). Per m = 2 bastano gli inversi dei quadrati delle distanze:

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
somma		0,3190	1,00

M1 è quasi ugualmente lontano dai centri A e B (7,72 contro 7,03), e perciò si divide fra loro quasi a metà; C è tre volte più lontano (al quadrato), e così riceve solo il resto.

4. Il fuzzificatore m

Definizione — coefficiente di partizione

Il coefficiente di partizione (partition coefficient) è PC = (1/n) ∑_i ∑_j u_ij². Vale 1 per una partizione netta e 1/c quando ogni punto appartiene a tutti i cluster in egual misura.

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

PC

nettezza dell’intera partizione, un numero in [1/c; 1]

(1/n) ∑_i

media sui punti — per poter confrontare insiemi di dati di dimensioni diverse

∑_j u_ij²

nettezza di un singolo punto — il quadrato «premia» un’appartenenza concentrata: (1, 0, 0) dà 1, (⅓, ⅓, ⅓) solo ⅓; a somma fissata pari a 1 la somma dei quadrati è minima quando tutte le parti sono uguali

Per m vicino a 1 il fuzzy c-means si avvicina al k-means: il coefficiente di partizione è 0,98 e il punto M4 appartiene a B per 0,79. Per m = 2 il coefficiente è 0,84 e per m = 5 solo 0,42 — i colori si fondono e perfino un punto del nucleo del cluster A ha verso A un’appartenenza di appena 0,45. Per m → ∞ tutte le appartenenze tenderebbero a 1/3. Il valore più usato è m = 2: abbastanza morbido da rendere visibili i punti di confine e abbastanza netto da lasciare i cluster ben distinti.

Esempio — un punto due volte più vicino a uno di due centri

Il punto ha distanza 1 dal centro 1 e distanza 2 dal centro 2. Secondo la formula u₁ = 1 / (1 + (1/2)^2/(m−1)):

• m = 1,2: esponente 10, u₁ = 1 / (1 + 1/1 024) ≈ 0,999 — un’assegnazione praticamente netta,
• m = 2: esponente 2, u₁ = 1 / (1 + 1/4) = 0,8,
• m = 5: esponente 0,5, u₁ = 1 / (1 + 0,707) ≈ 0,586,
• m → ∞: esponente → 0, (1/2)⁰ = 1 e u₁ → 1/2.

In generale: per m → 1⁺ l’esponente 2/(m − 1) tende all’infinito, i rapporti d_ij/d_ik < 1 tendono a zero e quelli > 1 all’infinito, quindi il centro più vicino riceve 1 e gli altri 0 (k-means). Per m → ∞ l’esponente tende a zero, tutti i c termini della somma tendono a 1 e u_ij → 1/c.

5. Quanti cluster?

Il numero di cluster va fornito all’algoritmo. Se non lo conosciamo, lo eseguiamo per vari c e confrontiamo la qualità delle partizioni. A questo scopo servono il coefficiente di partizione e l’indice di Xie–Beni.

Definizione — indice di Xie–Beni

XB = ∑_i ∑_j u_ij^m ‖x_i − v_j‖² / (n · min_{j ≠ k} ‖v_j − v_k‖²) — più è piccolo, meglio è.

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

XB

il rapporto «dispersione dentro i cluster / distanza fra di essi» — più piccolo è meglio

∑ ∑ u_ij^m ‖x_i − v_j‖²

compattezza — esattamente il valore di J_m che l’algoritmo ha minimizzato

n

numero di punti — trasforma il numeratore in una media per punto, perché l’indice non cresca con la dimensione dei dati

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

separazione — decide la coppia di centri più vicina; J_m da solo con l’aumentare dei cluster non fa che diminuire, e questo termine penalizza una partizione che spezza un vero cluster in due vicini

Esempio — indice di Xie–Beni per c = 3

Al termine dell’algoritmo J₂ ≈ 166,73. Quadrati delle distanze fra i centri: A–B ≈ 29,4, A–C ≈ 30,8, B–C ≈ 24,79 (i più vicini sono B e C). Per n = 126 punti:

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

Entrambi gli indicatori concordano sui tre cluster che abbiamo messo nei dati. Con dati reali un simile accordo non è scontato e gli indicatori sono più una guida che un verdetto.

6. Dove il fuzzy c-means fallisce

Guarda i punti anomali: O1 in alto a destra ha verso C un’appartenenza di 0,45 e verso B di 0,39; O2 in alto a sinistra addirittura 0,58 verso C. Eppure non appartengono a nessun cluster. La colpa è del vincolo ∑_j u_ij = 1: il punto deve dare il suo «uno» a qualcuno, anche se è lontano da tutti. Qui l’appartenenza significa più «a chi è più vicino» che «quanto bene appartiene a questo cluster».

Esempio — perché O2 = (0,2; 9,5) «appartiene» a C

Quadrati delle distanze dai centri: A ≈ 54,07, B ≈ 91,88, C ≈ 24,29. Anche dal centro più vicino, C, dista quindi 4,9 — più di sei volte la deviazione standard 0,8 con cui i punti dei cluster sono sparsi attorno ai centri. Gli inversi 0,0185, 0,0109 e 0,0412 danno la somma 0,0706 e le appartenenze 0,26, 0,15 e 0,58. La formula vede solo i rapporti delle distanze, non la loro grandezza: più il punto fosse lontano, più i rapporti si avvicinerebbero a 1 e le appartenenze a ⅓ — ma a zero non arriverebbero mai.

Definizione — c-means possibilistico (Krishnapuram e Keller, 1993)

Si elimina il vincolo sulla somma e al costo si aggiunge un termine che impedisce la soluzione banale u = 0:

J = ∑_i ∑_j u_ij^m d_ij² + ∑_j η_j ∑_i (1 − u_ij)^m,    da cui u_ij = 1 / (1 + (d_ij² / η_j)^1/(m−1)).

η_j è il «raggio» del cluster j: un punto a distanza d² = η_j ha appartenenza ½, e per m = 2 un punto con d² = 9η_j solo 0,1. L’appartenenza ora dipende dalla distanza da un solo centro, non dal rapporto con gli altri — un punto anomalo riceve valori piccoli ovunque.

• C-means possibilistico (Krishnapuram e Keller, 1993) elimina il vincolo sulla somma — un punto anomalo riceve allora appartenenze piccole verso tutti i cluster.
• Forma dei cluster. La distanza euclidea produce cluster rotondi. L’algoritmo di Gustafson e Kessel (1979) dà a ogni cluster una propria matrice di distanza e trova anche ellissi allungate.
• Posizione iniziale. Proprio come il k-means, può finire in un minimo locale peggiore — in pratica lo si esegue più volte da partenze diverse.

7. Il clustering fuzzy nella pratica

• Immagini mediche. La segmentazione delle immagini cerebrali di risonanza magnetica in sostanza grigia, sostanza bianca e liquido cerebrospinale è un impiego classico: un pixel al confine tra tessuti contiene davvero entrambi.
• Segmentazione dei clienti. Un cliente può appartenere in parte a più gruppi e il marketing può tenerne conto.
• Un parente probabilistico. Le misture gaussiane apprese con l’algoritmo EM assegnano anch’esse i punti ai cluster in modo «morbido» — ma con probabilità, non con appartenenze. I risultati sono spesso simili, l’interpretazione differisce esattamente come ha descritto la parte sulla logica fuzzy e la probabilità.
• Embedding. I testi trasformati in vettori da un modello linguistico si possono raggruppare allo stesso modo; l’assegnazione morbida mostra poi i documenti che stanno tra un tema e l’altro.

8. Riepilogo

• Il k-means assegna ogni punto a esattamente un cluster e sui punti di confine non dice nulla.
• Il fuzzy c-means cerca appartenenze u_ij con somma 1 e centri come medie pesate; alterna due passi semplici.
• Sui nostri dati ha trovato gli stessi centri del k-means e in più ha mostrato che i punti M1–M4 appartengono a due o tre cluster contemporaneamente.
• Il fuzzificatore m regola quanto è morbida la partizione; il coefficiente di partizione e l’indice di Xie–Beni aiutano a scegliere il numero di cluster.
• Il vincolo di somma 1 dà ai punti anomali appartenenze alte; le varianti possibilistiche risolvono il problema.

Vuoi toccarlo con mano? Fai eseguire a un agente IA il fuzzy c-means sui colori dei pixel di una tua foto e falla colorare secondo i cluster — e guarda quali pixel stanno «tra» i colori.

La vedi diversamente? Scrivi a support@coden-app.com.