Pattern Recognition
Lez.12: Unsupervised
classification: fuzzy C-mean
clustering
Classi “sfumate” (fuzzy)
• Una soluzione ai problemi posti dalla
classificazione “dura” (hard) utilizza il
concetto di “insieme fuzzy”.
• In questo corso non ci occuperemo di
logica fuzzy ma introduciamo solo i
concetti necessari al problema della
classificazione.
Insiemi “classici”, funzione caratteristica
Dato un universo Ω ed un sottoinsieme A di esso
la funzione caratteristica dell’insieme A su Ω è
definita per ogni x in Ω come segue:
χA(x) = 1 se x in A, 0 altrimenti
Un modo per interpretare tale funzione è
osservare che essa definisce il “grado” con cui
un elemento x appartiene all’insieme A.
Nella classificazione “hard” o “crisp” questo grado
può essere o minimo (zero) o massimo (uno).
Insiemi “fuzzy”, funzione caratteristica fuzzy
Dato un universo Ω un sottoinsieme “fuzzy” A può
essere definito da una funzione caratteristica
dell’insieme A, su Ω è definita per ogni x in Ω come
segue:
χA(x) = α con α in [0,1]
Anche in questo caso tale funzione definisce il
“grado” con cui un elemento x appartiene
all’insieme A.
Nel caso di insiemi “fuzzy” questo grado può essere
un numero qualunque tra un minimo (zero) o
massimo (uno).
Esempi di insiemi hard e fuzzy a confronto
• Tra tutte le possibili misure di statura di un uomo quando
siamo in presenza di una statura “alta”?
• Nel caso “hard” possiamo dire che se una statura è
superiore ai 180 cm siamo in presenza di statura alta.
• Ma se un uomo è alto 179 non può essere definito alto in
nessun grado?
• Una funzione caratteristica fuzzy “cattura” e esprime meglio
un concetto “vago” e “qualitativo” e fornisce uno strumento
matematico per lavorare con esso.
χA(x) : fuzzy
χA(x) : hard
0 cm
160 cm
180 cm
230 cm
Classificazione “hard”: nuova formulazione
matematica
• Nel caso “hard” abbiamo definito il problema della
classificazione in termini di “labeling”. Riformuliamolo in
modo da generalizzarlo al caso fuzzy.
• Una classificazione “hard” è una partizione
dell’universo Ω in k sottoinsiemi A1, A2, …, Ak a due a
due disgiunti tali che la loro unione restituisce tutto Ω.
• Usando il linguaggio delle funzioni caratteristiche possiamo
dire che classificare equivale a definire k funzioni
caratteristiche χ1(x), χ2(x), …, χk(x), su Ω soggette al
vincolo che per ciascun elemento x di Ω una ed una sola di
tali funzioni assume il valore 1.
• Un altro modo per esprimere tale vincolo è che per ogni x
in Ω deve risultare:
∑j=1…k χj(x) = 1
Classificazione “fuzzy”: definizione
Una classificazione “fuzzy” è un insieme di
k funzioni caratteristiche fuzzy χ1(x),
χ2(x), …, χk(x), su Ω soggette al vincolo
che per ogni x in Ω deve risultare:
∑j=1…k χj(x) = 1
In pratica un elemento x si distribuisce tra molti sottoinsiemi,
“appartenendo” a ciascuno di essi in grado differente.
Questo formalismo consente una maggiore flessibilità e imita meglio il
ragionamento umano soprattutto quando esso viene condotto
relativamente a concetti vaghi e non definiti in maniera rigida.
(ESISTONO ANCHE ALTRE FORMULAZIONI NON EQUIVALENTI MA
UTILI PER TALUNE APPLICAZIONI)
Partizione “hard” e “fuzzy”
Dividiamo le stature in due classi “alti” e “bassi”.
Nella classificazione “hard” dobbiamo definire due funzioni caratteristiche “complementari”
(in ogni punto la somma deve essere 1)
Appartenenza ai “bassi”
Appartenenza agli “alti”
0 cm
180 cm
230 cm
Dividiamo le stature in due classi fuzzy “alti” e “bassi”.
Nella classificazione “fuzzy” dobbiamo definire due funzioni caratteristiche “complementari”
(in ogni punto la somma deve essere 1)
Appartenenza ai “bassi”
Appartenenza agli “alti”
0 cm
180 cm
230 cm
Come classificare in maniera fuzzy?
• Si può generalizzare al caso fuzzy l’approccio
“hard” che sta alla base dell’algoritmo c-means.
IDEA (non nuova in questo corso!): introdurre una funzione “costo” di una
partizione fuzzy.
Ciascuna classe può essere “rappresentata” dal valore medio delle features
degli oggetti che ne fanno parte (le means). Le medie però dovranno essere
calcolate tenendo conto del “grado” di appartenenza di ciascun elemento
della classe alla classe stessa.
Per ciascuna classe ciascun elemento paga una tassa proporzionale alla
distanza dal centro della classe e proporzionale al grado con cui appartiene
a tale classe.
Il costo complessivo di una partizione fuzzy è dato dall’insieme di tutte le tasse
pagate dai record.
• Una buona partizione fuzzy è una partizione che
minimizza il costo complessivo.
• Anche in questo caso tale ottimizzazione viene
realizzata mediante un algoritmo iterativo.
Fuzzy c-mean algorithm
• Passo 0: (inizializzazione) si assegnano casualmente (o
in base ad una eusristica) dei gradi di appartenenza a
ciascuna classe per ciascun elemento.
• Passo 1: Si calcolano i centroidi delle classi mediante le
medie pesate di tutti gli elementi dell’universo da
classificare.
• Passo 2: Si “aggiornano” le appartenenze di ciascun
elemento a ciascuna classe tenendo conto della
distanza dai centroidi calcolati al passo precedente.
• Passo 3: Si ricalcolano i centroidi. Se essi non si sono
spostati dal passo precedente (o si sono spostati solo di
una quantità minore ad una soglia fissata) terminare.
Altrimenti andare al passo 2.
Dettagli nelle slide seguenti
La matrice delle appartenenze fuzzy
Se gli elementi da classificare sono N e le classi in
cui classificarli sono k la partizione fuzzy sarà
rappresentata da una matrice di k righe e N
colonne U.
Il numero reale ui,j di posto (i,j) in tale matrice è il
grado con cui l’elemento j-esimo appartiene alla
classe i-esima.
Si ha inoltre il vincolo che la somma degli elementi
in ciascuna colonna deve essere pari ad 1.
L’algoritmo di ottimizzazione, in pratica fa evolvere
ad ogni fase la matrice U.
I centroidi fuzzy
Se gli elementi da classificare sono record con m
campi numerici ciascuno il centroide della classe
h-esima si otterrà calcolando la media pesata
per ciascuna delle h componenti usando come
pesi i valori della riga h-esima della matrice U.
Xmedio_h = (Xmedio_h,1 … Xmedio_h,m)
con
Xmedio_h,g = ∑j in Ω uhjxjg
La matrice delle distanze D
La matrice U viene aggiornata tenendo conto della
“distanza” di ciascun elemento da ciascun
centroide.
Tale informazione può a sua volta essere
conservata in una matrice D di k righe e N
colonne. L’elemento dij di posto (i,j) indica la
distanza dell’elemento j-esimo dal centroide iesimo.
Anche nel caso fuzzy i risultati finali dipendono dal
tipo di metrica adottata per valutare queste
distanze.
Aggiornamento della matrice U:
la matematica
• L’aggiornamento della matrice U è il vero passo
critico dell’algoritmo. Omettiamo i dettagli della
derivazione matematica della legge con cui
svolgere tale aggiornamento.
• Tale derivazione si svolge essenzialmente
scrivendo il funzionale del costo e calcolando
mediante il calcolo differenziale in quale
“direzione” devono variare i parametri del nostro
problema per fare decrescere tale funzionale.
Aggiornamento della matrice U:
la formula
Data la matrice U e la matrice D alla fase t-esima la matrice U
nella fase (t+1)-esima si ottiene aggiornando ciascun elemento della matrice
come segue:
1
uij=
(dij2/d1j2)(2/(m-1))+ … + (dij2/dkj2)(2/(m-1))
Il parametro m deve essere maggiore di 1 e si chiama parametro di
fuzzificazione. Maggiore è il suo valore più “sfumata” sarà la partizione fuzzy
alla quale si perverrà al termine dell’algoritmo. La scelta più comune è m=2.
De-fuzzificazione
Sebbene il ragionamento “sfumato” sia utile nella fase di costruzione di una
classificazione in alcune applicazioni esso non è utile.
Se un botanico deve classificare i suoi iris alla fine dovrà comunque scegliere
la classe nella quale inserire i prorpi campioni.
Si deve in questi casi “estrarre” una classificazione “Hard” da una fuzzy. Si
parla di de-fuzzificazione.
Esistono diverse metodologie con la quale tale “assegnamento hard” può
essere fatto.
Un metodo semplice è assegnare ciascun elemento alla classe per la quale
ha il massimo grado di appartenenza.
Un metodo appena più sofisticato è assegnare ciascun elemento alla classe
per la quale ha il massimo grado di appartenenza purchè tale grado sia
superiore ad un certo valore limite e lasciarlo non classificato altrimenti.
Si tenga presente che, in ogni caso, la de-fuzzificazione è un passo opzionale
non legato all’algoritmo di fuzzy c-means.
Esperimento sugli iris di Fisher
Inizializzo:
ogni fiore con grado
di appartenenza
superiore a .33 è
marcato con la tag
corrispondente alla
classe presa in
considerazione
Secondo passo:
la terza classe
comincia ad
emergere
Primo passo:
le prime due
classi cominciano
ad emergere e a
delinearsi
Terzo passo:
la terza classe
occupa il posto
che manterrà fino
alla finale
convergenza
Dopo altri 15 passi…
Iris su cui la
classificazione
rimane incerta
Il perdurare
dell’incertezza
potrebbe
essere usato
come criterio di
rejection per
migliorare la
qualità del
classificatore.
Applichiamo il fuzzy-C-mean ad
una immagine RGB
• Le features sono i tre canali di colore.
• Assegneremo 3 classi in maniera fuzzy.
• Per la visualizzazione coloriamo di rosso,
blu o verde ciascun pixel a seconda della
classe per la quale il pixel ha “grado di
appartenenza” massimo. Se però nessuna
delle classi supera grado di apparteneza
0.5 il pixel resta nero.
Risultati
originale
Animazione dei cluster (un
frame ogni due passi)
Commenti
• Al passo iniziale le classi sono casuali.
• Ri-assegnando con le regole fuzzy le
appartenenze si “omegeinizzano” (frame
nero).
• Successivamente le classi “emergono”
dalla immagine di partenza.
• Restano ampie zone “non classificate”
Ripetiamo l’esperimento ma
usando le PCA dell’immagine
Non tratteremo della “induzione
fuzzy”
• Il potere dell’approccio fuzzy è più
evidente nel momeno in cui si vuole
formalizzare (ed automatizzare) il
ragionamento approssimato.
• Questi temi non possono essere coperti in
questa sede (vedi corso di Intelligenza
Artificiale)
Clustering per “prototipo”
• Sia nel caso “classico” che nel caso “fuzzy” il
clustering è un approccio “filosofico” preciso alla
classificazione.
• Si tratta di raffinare via via, in una interazione tra
le due fasi classi e prototipi.
• Si tratta di una classificazione “positiva”: un
elemento viene assegnato ad una classe se
“somiglia” al prototipo di tale classe.
• Dipende dalla “metrica di similarità” adottata.
Alternativa alla similarità… la
dissimilarità
• Se un prototipo non può essere definito con precisione
un approccio spesso utile è quello di classificare una
popolazione graduando la sua “dissimilarità” rispetto a
certi esempi.
• Per esempio si scelgono alcuni pixel che caratterizzano
in una immagine landsat un bosco. Un approccio alla
classificazione è decidere in che grado tutti gli altri pixel
sono “non-bosco”.
• Quando la definizione in termini positivi delle classi che
si intende creare è difficoltosa questo approccio è più
sensato di quanto sembri a prima vista…
Prossimamente
• Clustering gerarchico
• Miscuglio di Gaussiane