I classificatori neuraliweb.tiscali.it/patrizio_antici/tesi/08_cap3.pdfCapitolo 3: I due...

Capitolo 3: I due classificatori

90

CAPITOLO 3

I classificatori neurali

3.1 Il cervello, il sistema nervoso ed il loro modello

L’apprendimento umano è un processo psichico mediante il quale l’esperienza modifica il

comportamento umano. Alla base si trova una struttura interna molto complessa, il cervello, che

riceve i parametri in ingresso. Molte cose sono ancora sconosciute sul funzionamento del

cervello. Comunque la ricerca medica ha potuto stabilire alcuni dei processi che avvengono in

esso.

Il cervello è costituito da moltissimi neuroni (di solito nell’ambito di alcuni miliardi) collegati

tutti fra di loro. Ogni neurone riceve segnali dagli altri neuroni attraverso una struttura chiamata

dendrite. Il neurone manda impulsi di attività elettrica attraverso l’assone (axon), che si dirama

in migliaia di collegamenti che collegano il neurone con gli altri. Alla fine di ogni ramo vi è una

struttura chiamata sinapse che converte l’attività dell’assone in effetti elettrici. Questi impulsi

elettrici hanno la capacità di convertire il neurone in attivo o inattivo, a seconda di come sia

predisposto il neurone di destinazione. Quando un neurone riceve un ingresso eccitante (che è

quindi sufficientemente grande per superare la soglia di attività) manda un impulso di attività

elettrica lungo il suo assone.

Fig.3.1a: Collegamento del neurone tramite il suo assone.


91

Fig.3.1b: Collegamento della sinapse con il suo assone.

L’apprendimento avviene cambiando l’efficacia delle sinapse e cambiando così anche

l’influenza di un neurone sull’altro.

Di fatto gli psicologi suppongono che l’apprendimento nel bambino avvenga per confronto

associativo. Un esempio può chiarire quanto esposto.

Si supponga di voler insegnare al bambino cosa è un tavolo e farglielo distinguere da una sedia.

Il bambino, in fase di apprendimento, vedrà alcuni esempi di tavoli nonché alcuni esempi di

sedie e gli verrà sempre specificato quale degli esempi è una sedia e quale è un tavolo. A forza

di mostrare esempi di tavoli ed esempi di sedie, il bambino cercherà di trovare i criteri che

distinguono i tavoli dalle sedie ed associerà quindi tutti i tavoli e le sedie viste ad una “classe” di

tavoli ed una “classe” di sedie. Una volta definite mentalmente queste classi, il bambino,

allorché gli verrà mostrato un esempio di tavolo o sedia non visto in precedenza, riuscirà ad

associare il nuovo elemento ad una delle due classi, eventualmente con più o meno dubbi.

Similmente avviene nella rete neurale. Si mostrano alla rete vari esempi di elementi appartenenti

ad una classe (fase di training – l’insieme dei dati di ingresso invece viene chiamato training

set), specificando a che classe appartengono. La rete calcola il giusto assetto dei suoi “neuroni”

artificiali in base agli esempi dati in ingresso. Una volta svolto “l’apprendimento” della rete si

passa alla seconda fase. Si dà alla rete in ingresso un elemento che non aveva mai visto,

appartenente però ad una delle classi utilizzate per l’apprendimento, e si vede se la rete riesce a

classificare correttamente l’elemento nella classe corrispondente (fase di validazione o

generalizzazione – l’insieme di dati utilizzato per questa fase viene chiamato validation set).

Ecco perché le reti di neuroni vengono talvolta anche chiamate “classificatori”.

Soprattutto per il riconoscimento si vede che il nostro cervello è molto più veloce ed efficiente

di tutti gli strumenti tecnici messi a disposizione al giorno di oggi. Ma non è la capacità di

elaborazione a nostra disposizione che rende le moderne macchine di calcolo inferiori al sistema

neurale umano. Infatti un semplice calcolo confronta le capacità di elaborazione di un animale

di piccola taglia con un personal computer:


92

Animale di piccolataglia

Personal computer

Elementi di base 109 neuroni 107 transistori

Ritmo di elaborazione 10Hz4*108 Hz (Pentium

400MHz)Numero medio di collegamenti 103 (sinapsi) per neurone 2 per transistore

Informazione transitante nelcollegamento

4 bit 0.5 bit

Capacità di elaborazione 4*1013 4* 1015

Tab.3.1: Confronto fra la capacità di elaborazione di un cervello di animale e uno artificiale(calcolatore elettronico)

Dalla tabella si vede che la capacità di elaborazione del personal computer è superiore rispetto a

quella dell’animale, ma comunque nel mondo reale non è così. Infatti l’animale, per esempio un

cane, riesce a riconoscere bene il suo padrone, mentre il computer non è capace di effettuare

alcun riconoscimento in tal senso.

Ecco perché diventa naturale cercare di imitare anche sui mezzi di calcolo a nostra disposizione

il sistema nervoso. Cosa precisamente sia da imitare non è stato ancora stabilito a fondo.

Comunque l’idea principale è quella di acquisire esperienza da esempi ed è questo che si cerca

di imitare. Ecco perché si sono create le reti neurali artificiali.

L’implementazione e la costruzione di tecnologie che usano le reti neurali sono tuttavia limitate

da barriere fisiche come mostra un semplice calcolo di energia e potenza:

Animale di piccolataglia

Personal computer

Energia necessaria per cambiamento distato

10-16 Joule 10-7 Joule (per transistor)

Numero operazioni 1016 operazioni/secondo 1014 operazioni/secondo1

(per elementi WSI)Potenza richiesta 1 Watt 1000 MWatt (caso

peggiore)

Tab.3.2: Confronto fra la potenza del cervello umano e quella del cervello elettronico.

1 Questo valore è il valore che si può ottenere con la tecnologia corrente (dati aggiornati al 1996). Unlimite fisico prevedibile ottenibile tramite tecnologia “neuromorfica” quale usata nella retina artificialedovrebbe aggirarsi intorno ai 10-15 J/s. Nella tecnologia elettronica corrente il limite fisico prevedibile èdi circa 10-9 J/op.


93

Si vede quindi come nel caso più sfavorevole la potenza richiesta per implementare le capacità

di elaborazione del cervello umano ammonterebbero ad una quantità di potenza assai

considerevole.

Oggigiorno le reti neurali sono entrate sempre di più nel mondo applicativo e vi sono veri e

propri progetti ingegneristici che, passo per passo, cercano di riprodurre reti neurali.

yi =∑ 1µnk

µnk− +1 1

µn2

µn 1 1+

µn 1

µ1

wnk− +1 1

wnk

wn2

wn1 1+

wn1

w1

y1

y2

yk

y1

y2

yk

e x( )

x1

x2

xn

fuzzy

out

crisp

out


94

Fig.3.2:

Schema di passaggio dal cervello umano alla realizzazione di un microchip neurale, passando per il suomodello matematico ed il progetto ingegneristico. Il chip è stato progettato presso l’Universtà di Roma

“Tor Vergata” – dipartimento di elettronica.


95

3.2 La struttura dei classificatori

3.2.1 Introduzione

Nel presente capitolo verranno esposti i due classificatori utilizzati per il riconoscimento degli

strumenti musicali. Verranno mostrate prima le caratteristiche comuni dei due tipi di

classificatori. Successivamente verranno illustrate le caratteristiche peculiari del primo e del

secondo classificatore. Sono state introdotte alcune nozioni matematiche e si prega il lettore di

perdonare il linguaggio più complesso.

3.2.2 Il processo di classificazione

Il processo di classificazione è essenzialmente un processo di individuazione, dato un insieme di

oggetti, di particolari caratteristiche di questi oggetti e/o di relazioni mutue intercorrenti tra di

loro. Queste mutue relazioni sottendono alla organizzazione dell’insieme stesso e permettono di

individuare all’interno di questo insieme dei sottoinsiemi. Ciascuno di tali sottoinsiemi

(chiamati anche classi) contengono oggetti accomunati dall’avere, per così dire, uno stesso

“valore” di queste caratteristiche.

L’individuazione di una struttura di questo genere è espletata da un meccanismo di astrazione

che porta alla costruzione, per ogni classe, di un modello rappresentante tutti gli oggetti

appartenenti ad essa, e che riflette tutte e sole le informazioni rilevanti ai fini della partizione

(divisione) dell’insieme in varie classi. Il modello in questione dovrà necessariamente

prescindere, invece, da quelli che possono essere dettagli inessenziali. Quanto più la costruzione

di tali modelli è accurata e idonea a riflettere la struttura fisica degli oggetti che descrivono,

tanto più questi modelli saranno in grado di permettere l’identificazione di un nuovo esemplare

di oggetto (chiamato anche pattern) della classe che rappresentano, qualora il modello venga

confrontato con un nuovo esemplare per la prima volta.

Guardando a come il cervello umano costruisce le sue categorie mentali è immediatamente

chiara la soluzione al problema: il sistema deve essere in grado di apprendere e di costruirsi in

maniera autonoma (cioè non supervisionata) i modelli astratti sulla base degli esempi concreti

che ha avuto la possibilità di vedere (apprendimento o training) ed inoltre deve essere dotato di

una qualche capacità di ragionamento che gli permetta di gestire anche situazioni che non gli

siano mai capitate prima (generalizzazione o validazione).


96

L’uso delle reti neurali nei problemi di classificazione e clusterizzazione è particolarmente

indicato proprio in virtù della capacità di generalizzare che hanno sistemi di calcolo basati su

questo tipo di architetture. In effetti, e per quanto detto prima, la risoluzione di un problema di

classificazione non può prescindere da tale capacità; il classificatore, anzi, sarà tanto migliore

quanto più riesce a generalizzare in merito al problema che è stato chiamato a risolvere.

Per quanto riguarda invece la scelta dell’utilizzo della logica fuzzy (aggettivo anglosassone di

cui la traduzione letterale è “sfumata”), un motivo che ne è alla base è l’elevata robustezza che

essa conferisce in termini di reiezione di errori; infatti i “confini logici” tra i modelli astratti di

classi diverse prodotti da un sistema fuzzy non sono mai netti bensì graduali. Non esistono

quindi frontiere nette e quindi gli oggetti situati in corrispondenza di queste frontiere hanno, per

così dire, caratteristiche proprie dell’una e dell’altra classe in egual misura, riducendo così la

possibilità di grossolani errori. Inoltre molte volte non è necessaria, anzi sarebbe da evitare, una

tassonomia rigida e una divisione in categorie rigorosa. La classificazione, quindi, avviene in

modo non esclusivo. Si pensi, per esempio, alla scelta di un aggettivo che indichi la temperatura

di una certa quantità d’acqua (situazione comunissima nella vita quotidiana, quando l’acqua è,

per esempio, quella che viene fuori dalla doccia di casa); non avrebbe senso, in questo caso,

tentare di classificare necessariamente in “calda” o “fredda” una qualsiasi quantità d’acqua (cioè

porre un confine rigoroso, lungo l’asse delle temperature, tra temperature “fredde” e “calde”).

Sarebbe invece più semplice, nonché sensato, fornire indicazioni di “freddezza” e “calore” di

una stessa quantità d’acqua, intese come valori di appartenenza di quella quantità di acqua alle

classi delle acque “fredde” e delle “calde”. In questo caso, la necessità di sfumare la decisione è

dettata dalla struttura stessa del problema e la variazione fuzzy delle indicazioni di “freddezza”

e “calore” ricalca il graduale e continuo variare da acqua “fredda” ad acqua “calda” che si ha

all’aumentare della temperatura.

3.2.3 La struttura di un classificatore reale

Verrà ora svolta una serie di utili considerazioni in merito alle problematiche concernenti la

realizzazione di un classificatore, nonché riguardanti lo svolgimento di una procedura di

classificazione nella sua interezza, vale a dire a partire dai dati reali, per così dire “grezzi”, sino

ad arrivare alla presentazione dei risultati in uscita, in aderenza al tipo di codifica delle uscite

scelta.

Un algoritmo classificatore è solo una parte (per quanto la più importante) del complesso

meccanismo che, dato un set di dati reali in ingresso, risolve il problema delle loro

classificazioni. La maggior parte di tali algoritmi, infatti, accetta i dati di ingresso solo se


97

compresi all’interno di un dominio prefissato dello spazio n-dimensionale2 (n è la dimensione di

tale spazio) che può essere fissato a piacere ma deve essere stabilito prima. È necessario quindi,

nel caso in cui si parta da dati reali, una preventiva normalizzazione di questi in modo tale da

adattarli a poter essere presentati all’algoritmo in questione. Inoltre, questi stessi dati

provengono, nella maggior parte dei casi, da misure effettuate su grandezze fisiche e, proprio a

causa di questa loro origine, non potranno mai essere esenti da errori. È frequente inoltre anche

il caso in cui tali dati sono incompleti, nel senso che alcuni patterns del set di addestramento

possono mancare del valore di una o più componenti. In questi casi, a monte della procedura di

classificazione vera e propria, non basta più una normalizzazione (per quanto complessa questa

possa essere), ma è necessaria una vera e propria elaborazione dei dati (preprocessing),

utilizzando anche tecniche di tipo statistico.

Fig. 3.3. Struttura del generico classificatore

Un discorso analogo vale per le uscite, in particolar modo nel caso in cui queste ultime debbano

essere usate (ad esempio, nel caso di un controllo automatico) come comando di uno o più

controllori di un sistema. In altre parole, volendo usare un classificatore in impieghi reali è

necessario dotarlo quantomeno di una parte che svolga le funzionalità di interfaccia di ingresso

(preprocessing) e di un’altra parte che faccia le veci di interfaccia di uscita (postprocessing); la

sua struttura di principio sarà quindi del tipo della figura 3.3.

Di seguito, vengono riportate alcune considerazioni in merito alla realizzazione dei singoli

blocchi. È necessario precisare che, dal punto di vista dell’utilizzo reale, il classificatore vero e

proprio è formato da tutti e tre i sopra menzionati stadi, nel senso che, volendolo proporre come

strumento di lavoro a chiunque ne abbia bisogno o, come si dice, volendolo “ingegnerizzare”

(ad esempio, sotto forma di pacchetto software che implementa automaticamente l’intera

procedura di classificazione dei dati), tutti gli eventuali preprocessamenti e postprocessamenti

debbono essere svolti in maniera del tutto trasparente agli utenti; questi ultimi, cioè, devono

2 Si vedrà in seguito che, per esempio, per il riconoscimento degli strumenti musicali lo spazio n-dimensionale consisteva nei primi armonici della nota.


98

vederli svolti in maniera (quasi) automatica. Assodato questo punto, è chiaro quindi che, per un

utilizzatore, il classificatore apparirà come una black box (scatola nera) che prende in ingresso i

dati “grezzi” e fornisce in uscita dei valori “adattati” all’applicazione corrente. Per questo

motivo, anche se l’algoritmo di classificazione funziona correttamente e fornisce prestazioni

ottimali, un errore o un mal funzionamento di uno dei due stadi, rispettivamente a monte e a

valle di esso, risulta complessivamente in un decadimento, forse critico, delle prestazioni

dell’intero sistema. È essenziale, quindi, focalizzare l’attenzione in maniera rilevante anche su

tali due stadi.

In conclusione di questa sezione si vuol evidenziare un ultimo punto che sino ad ora è stato

considerato come tacitamente valido, ma che vale la pena di precisare: il problema che si

sottopone al classificatore deve essere “consistente e ben posto”. Ciò vuol dire che è necessaria

un’accurata analisi del problema, dal punto di vista della sua struttura in astratto, che porterà poi

alla costruzione degli insiemi di dati (specificatamente training set e validation set) sui quali il

classificatore sarà chiamato a lavorare. In primo luogo occorrerà stabilire se ha effettivamente

senso intentare una classificazione in quanto il problema ha, per esempio, statisticamente

parlando, dei modi significativi e non una distribuzione totalmente casuale. In secondo luogo

dovranno essere individuate quelle grandezze che, riunite a formare un pattern, descrivano in

maniera soddisfacente tutte le informazioni relative alla distinzione delle classi stesse.

Successivamente sarà necessario scegliere una popolazione di esempi significativa dal punto di

vista statistico e contenente un adeguato livello di informazione circa la struttura “astratta” delle

classi. In ultimo, la divisione di tale popolazione in training set e validation set dovrà essere

fatta in maniera tale che questi ultimi siano in misura marcata equivalenti dal punto di vista

statistico.

3.2.4 La clusterizzazione parallela

Una particolarità dei due classificatori – delle due reti neurali – è che possono creare dei modelli

di classi che funzionano in parallelo e possono adattare la propria struttura alle caratteristiche

statistiche della classe che gli compete. Questo è una innovazione rispetto a molti algoritmi di

classificazione usati in altre reti neurali. Nel caso dell’algoritmo Min-Max di Simpson3, per

esempio, il valore del parametro θ (parametro che identifica il modello associato ad una classe

in base a quanto si distinguono i singoli patterns appartenenti ad essa) è uguale per tutte le

classi, indipendentemente dalla probabilità con la quale si distribuiscono i patterns di ciascuna

3 L’algoritmo Min-Max di Simpson è un algoritmo molto usato che verrà spiegato in seguito


99

classe. Infatti il parametro in questione viene calcolato una volta che si sono create le classi di

appartenenza dei singoli patterns e questi ultimi sono stati raggruppati in dei clusters (grappoli)

di appartenenza. Si supponga ora di avere un training set formato da due classi di cui una ha i

patterns molto concentrati e riuniti in due o più clusters compatti, mentre l’altra è formata da

patterns più radi e riuniti in regioni di più vaste dimensioni. Un qualsiasi valore “ottimo” di θ

dovrebbe essere un compromesso tra il valore che meglio clusterizza la prima classe e quello

più adatto alla seconda. Di questi due valori, il primo dovrebbe essere piccolo, magari prossimo

allo zero, mentre il secondo dovrebbe essere più grande, forse quasi pari ad uno, al fine di

ottenere clusters di dimensioni più estese e capaci di contenere i patterns della seconda classe,

più “rada”. È evidente che un valore “mediato” e uguale per tutte e due le classi, proprio in

quanto scelta di compromesso, potrebbe non essere adatto ad una, o addirittura a nessuna, di

tutte e due le classi in questione. Nel caso di clusterizzazione parallela, invece, ciascun

clusterizzatore userà il valore di θ adeguato alla distribuzione dei patterns della classe ad esso

relativa, ottenendo così una più accurata partizione dello spazio di ingresso.

In sostanza, sembra ragionevole pensare che chi riuscisse a “recintare” in maniera soddisfacente

le zone di spazio di “proprietà” di una singola classe, si troverebbe anche necessariamente in

grado di “spartire” altrettanto bene tali zone tra le diverse classi. In altre parole, cioè, una

classificazione “esatta” è necessariamente decomponibile in un insieme di clusterizzazioni

“esatte”.

In realtà, non si può spingere oltre una certa misura il parallelismo e l’indipendenza dei singoli

problemi di clustering. È necessario infatti coordinare in qualche modo in uscita i risultati forniti

dai singoli clusterizzatori, in modo da “recuperare” le informazioni di natura trasversale, cioè

quelle informazioni, presenti nella struttura del training set, che riguardano le relazioni mutue

tra le diverse classi. Per esempio, nel caso particolare di due classi A e B aventi distribuzione dei

patterns in due regioni di spazio concentriche e aventi “baricentri” (cioè medie algebriche dei

patterns) pressoché coincidenti (fig. 3.4), ciascuno dei clusterizzatori individuerebbe

ragionevolmente un unico cluster (Figg. 3.4b e 3.4c).

Fig. 3.4: Due clusters concentrici


100

Al momento della sovrapposizione delle due clusterizzazioni (Fig. 3.4d), per come sono

costruite le funzioni di appartenenza (vedi più avanti), il cluster più interno, della classe B,

risulta completamente assorbito da quello esterno e relativo alla classe A, fino a scomparire.

Accade cioè, che nella regione di decisione, tutti i punti della zona interna al cluster più grande,

eccetto il centroide del cluster più piccolo, vengono etichettati come appartenenti alla classe A e

la regione di spazio relativa alla classe B è costituita da un unico punto: il centroide del cluster

più interno. Questo accade perché, durante la clusterizzazione relativa alla classe A, il “buco” al

centro del cluster non viene in alcun modo preso in considerazione; il clusterizzatore in

questione, cioè, non possiede alcuna informazione su di esso e quindi non sa se quella è

realmente una regione di spazio vuota, oppure se (come è questo il caso) è occupata da patterns

di altre classi. In poche parole, l’architettura in questione non è in grado, almeno così com’è

stata presentata sino ad ora, di risolvere problemi in cui esistano classi concentriche (problemi

di tipo “bersaglio”).

È stato per questo necessario arricchire la procedura di addestramento di un’ulteriore fase in cui

si riorganizzano le uscite dei singoli clusterizzatori alla luce delle relazioni mutue tra le diverse

classi: queste uscite vengono pesate con dei coefficienti, determinati nella seconda fase di

training, che vengono aggiornati tenendo conto di eventuali misclassificazioni e mirando alla

correzione di queste .

Un altro aspetto importante riguarda il problema della ottimizzazione dei parametri che

governano l’addestramento della rete. Nel caso del min-max di Simpson è il parametro θ a

variare in maniera sostanziale la struttura della rete. Bisogna costruire una “funzione obbiettivo”

che sia in grado di esprimere quantitativamente la “bontà” della classificazione e, con l’ausilio

di questa, determinare il valore del parametro che garantisca che la partizione sia ottimale.

Nel caso di algoritmo di una classificazione non parallela, per esempio utilizzando l’algoritmo

di Simpson supervisionato, è stata proposta come funzione obiettivo una espressione del tipo:

F E EC S( ) ( ) ( ) ( )θ λ θ λ θ= ⋅ + − ⋅1 (3.1)

Questa funzione è somma di due contributi, di cui il primo tiene conto della complessità della

rete ( EC ( )θ è pari al numero di clusters creati diviso per la cardinalità del training set), mentre

il secondo, ES ( )θ , esprime la percentuale di errori in classificazione compiuti sul training set.

In generale tali contributi, presi singolarmente, hanno andamenti opposti al variare di θ; valori

piccoli di questo danno luogo ad un elevato numero di clusters, risultando in un basso numero di

errori, mentre valori elevati creano pochi clusters dando luogo a reti semplici che commettono

un numero di errori generalmente elevato. L’espressione precedente, quindi, ha un andamento di


101

tipo pseudo-parabolico (fig. 3.5), nel senso che non è monotona e presenta l’ottimo (il minimo)

in corrispondenza di uno dei punti in cui inverte la tendenza.

Fig. 3.5: Andamenti qualitativi delle funzioni obiettivo

Al variare del parametro λ nell’intervallo [0;1] si ottengono dalla diverse funzioni: bassi valori

di λ tendono a privilegiare l’aspetto legato agli errori, mentre alti valori di questo enfatizzano

l’importanza dell’aspetto legato alla complessità. Il valore del parametro λ va quindi scelto a

seconda di quale delle due esigenze debba essere soddisfatta maggiormente oppure, volendo

tener conto di ambedue nella stessa misura, conviene scegliere per esso un valore prossimo, o

addirittura uguale, a 0.5.

Nel caso del classificatore a clusterizzatori paralleli, invece, non è assolutamente praticabile una

strada che tenga conto degli errori di classificazione. Ciascun clusterizzatore, infatti, deve

fornire un clustering ottimizzato prima ancora che una funzione obiettivo possa essere calcolata.

Solo quando tutti i clusterizzatori avranno assolto al loro compito, e le informazioni da essi

fornite saranno state integrate, avrà senso considerare l’intera classificazione e si potrà

procedere ad una valutazione degli errori commessi. In sostanza, cioè, la partizione relativa alla

singola classe è essenzialmente di tipo non supervisionato. Il problema affrontato in merito,

quindi, è stato quello di ottimizzare i singoli clustering, adottando criteri di bontà che curassero

particolarmente caratteristiche quali compattezza e separabilità dei clusters.


102

3.2.5 La struttura della Rete

Le particolarità dei singoli clusterizzatori verranno illustrate nei paragrafi seguenti, comunque si

vuole qui illustrare brevemente la topologia della rete che viene creata durante l’addestramento.

La rete in questione è formata da tre strati di neuroni (vengono chiamati così per analogia con i

neuroni del cervello umano)(fig. 3.6). Nel primo strato, quello di ingresso, sono presenti n

neuroni, uno per ogni componente dei patterns, ognuno dei quali è collegato con tutti i neuroni

dello strato successivo. Tutte le connessioni tra il primo e il secondo strato hanno pesi unitari.

Il secondo strato è formato da tanti neuroni quanti sono i clusters complessivamente individuati

durante la fase di addestramento. L’insieme di questi neuroni è partizionabile in k sottoinsiemi,

ciascuno dei quali contiene tutti e soli i neuroni associati ai clusters di ogni singola classe. Ogni

sottoinsieme di questi costituisce, in sostanza, lo strato di uscita del singolo clusterizzatore.

Posto un pattern all’ingresso della rete, l’uscita di ciascuno di questi neuroni fornisce il valore di

appartenenza al cluster (ad esso associato) di tale pattern. L’ultimo strato, quello di uscita, è

costituito da k neuroni, uno per ogni classe da discriminare; ognuno di questi neuroni riceve in

ingresso le uscite del clusterizzatore della classe che gli compete ed ognuno di essi (supponiamo

quello j-esimo )fornisce in uscita il valore dell’appartenenza (appartenenza fuzzy) del pattern,

presente all’ingresso della rete, alla classe j-esima del training set. Ogni classe è pari all’unione

fuzzy dei clusters ad essa relativi, per cui il valore di appartenenza di un pattern ad essa è pari al

massimo delle appartenenze ai singoli clusters relativi alla classe in questione; ciascun neurone

dello strato di uscita realizza quindi sostanzialmente la funzione del rilevamento del massimo

(max(·) ), restituendo in uscita il massimo tra i valori al suo ingresso. Tutti questi valori, prima

di essere disponibili all’uscita della rete, vengono normalizzati in modo da dare in somma,

coerentemente col loro significato fuzzy, il valore unitario.

Le connessioni tra i neuroni del secondo e terzo strato sono caratterizzate da pesi, in un insieme

W, determinati, come detto sopra, col criterio di minimizzare il numero di errori globali

commessi sul training set a clusterizzazioni avvenute.

In figura 3.6 è illustrata la struttura della rete; si notano i tre strati di neuroni, le connessioni e i

singoli clusterizzatori (ciascuno racchiuso in un rettangolo tratteggiato). Il blocco etichettato ∑

prende in ingresso le k uscite dei neuroni del terzo strato e le normalizza in modo che in somma

diano il valore unitario, mentre l’ultimo realizza la politica di WTA, fornendo in uscita

l’etichetta stimata di un pattern x all’ingresso della rete come etichetta della classe a cui

corrisponde il massimo valore di appartenenza fuzzy di x stesso. Quest’ultimo blocco, come

qualsiasi defuzzyficatore, è necessario ogni qualvolta si voglia in uscita dalla rete un valore

“giusto” (nel senso, cioè, di non fuzzy).


103

Fig. 3.6: Struttura della rete

Si vuole effettuare qui qualche considerazione anche in merito a come è stato risolto il problema

dell’ordinamento. Come è già stato delineato, il problema di determinare quale sia l’ordine

migliore con cui debbano essere presentati alla rete i patterns in fase di addestramento non è di

facile risoluzione. Un espediente adottato nel caso del classificatore presentato è quello di

presentare ai singoli clusterizzatori i patterns delle relative classi disposti secondo un

ordinamento “sferico”.

L’ordinamento in questione consta di tre fasi:

• calcolo, per ciascuna classe, del centroide di tutti i patterns ad essa relativi;

• calcolo della distanza di ciascun pattern dal baricentro della classe a cui appartiene;

• ordinamento di tutti i patterns di ciascuna classe per valori crescenti di tali distanze

Questa procedura di ordinamento ha complessità minima (pari a O(N), essendo N il numero di

patterns presenti nel training set) e risulta svincolata dalla dimensione n dello spazio di ingresso.

Nel simulatore realizzato, comunque, oltre a questo tipo di ordinamento “sferico”, è stata

implementata anche la possibilità di ordinare i patterns lungo una qualsiasi dimensione dello

spazio di ingresso. Questo perché in alcuni casi è possibile che siano presenti nel training set

particolari disposizioni dei patterns che potrebbero palesemente essere evidenziate da

ordinamenti di questo tipo (ad esempio nel caso di training set formato da bande alterne di

patterns di classi diverse, parallele ad una data dimensione, sarà opportuno effettuare

l’ordinamento di questi lungo tale dimensione).


104

3.2.6 Ottimizzazione delle singole partizioni

Per quanto detto nei paragrafi precedenti, è necessario avere un qualche tipo di criterio che

permetta di trovare un valore dei parametri che governano l’algoritmo di addestramento, tale da

garantire una partizione accettabile dei patterns relativi ad una data classe. Si è già anticipato in

precedenza che una strategia che tenda a minimizzare il numero di errori commessi sul training

set è inapplicabile per il procedimento del singolo clustering, proprio per il fatto che i

clusterizzatori, in quanto tali, lavorano in modo essenzialmente non supervisionato.

È stata evidenziata in precedenza l’elevata modularità funzionale che caratterizza l’architettura

realizzata, quando è stato detto che il classificatore si avvale di k moduli (i clusterizzatori), uno

per classe, che, almeno in linea di principio, possono essere scelti di natura qualsiasi. Un

discorso analogo si può fare anche relativamente alla scelta del tipo di criterio da adottare per

l’individuazione della partizione ottima fornita da ciascuno di questi clusterizzatori. Qualsiasi

criterio, purché di tipo non supervisionato, può essere usato per decidere quali debbano essere le

caratteristiche che individuano una tale partizione. Va tuttavia sottolineato il fatto che un modo

per scegliere il “miglior” criterio tra i diversi possibili appare difficilmente individuabile a

priori. Purtroppo l’unica via per dire quale tra questi criteri sia più adatto e in quali situazioni

sembra essere la sola evidenza sperimentale.

Data comunque la distribuzione dei patterns relativi ad una classe, la possibilità di individuare

all’interno di essa una qualche struttura di organizzazione in clusters dipende strettamente dalla

disposizione spaziale dei patterns e dalle distanze relative che intercorrono tra essi. Un criterio

di valutazione che appare ragionevole alla luce di ciò, quello di fatto adottato nel presente

lavoro, potrebbe quindi essere uno che tenda a privilegiare caratteristiche dei clusters quali

compattezza (e cioè quanto sono compatti i clusters) e separabilità (quanto sono distanti i singoli

clusters tra di loro).

In generale, comunque, il corredare ciascun clusterizzatore di un criterio di ottimizzazione

(qualunque esso sia) contribuisce a rendere lo stesso clusterizzatore in qualche maniera più

“intelligente” e consente di automatizzare la procedura di clustering svincolandola dalla scelta,

peraltro abbastanza critica, del parametro che deve governare l’addestramento. L’effetto di un

tale arricchimento di struttura è schematizzato in figura 3.7.

Come si vede dalla figura, il blocco di ottimizzazione dovrebbe, sulla base dell’esame congiunto

delle partizioni fornite dal clusterizzatore e degli ingressi che le hanno prodotte, fornire il valore

del parametro che individua la partizione ottima in corrispondenza di quel dato set di ingressi.


105

Fig. 3.7: Ottimizzazione di un Clusterizzatore

3.2.7 Gli indici di bontà

I passi da seguire nella ricerca di un criterio di valutazione che tenga conto delle caratteristiche

sopra accennate sono i seguenti:

• individuazione di qualità (quali densità di patterns contenuti, compattezza, etc.) in base alle

quali giudicare individualmente la validità del singolo cluster ottenuto;

• individuazione di caratteristiche che permettano di esprimere le relazioni che intercorrono

tra due o più clusters comunque disposti nello spazio (separazione, distanza tra i centroidi,

etc.);

• ricerca di un modo per dare una valutazione quantitativa delle caratteristiche di cui ai due

precedenti punti;

• formulazione di un’adeguata funzione obiettivo, che sfrutti le informazioni numeriche

codificate al punto precedente, il cui valore ottimo sia ottenuto in corrispondenza di una

partizione, per così dire, il più possibile “ottimale”.

Esistono a tale scopo degli indici relativi di bontà di un clustering. Il termine relativi sta ad

indicare il fatto che il valore numerico ottenuto dal calcolo di uno di tali indici, in

corrispondenza alla partizione di un dato insieme di dati, non ha alcun significato preso come

entità a sé stante, assoluta. D’altra parte, invece, valori ottenuti relativamente a due diverse

partizioni di uno stesso data set possono essere tra loro confrontati e da tale confronto si può

desumere quale delle due partizioni sia migliore dell’altra.


106

Di solito gli indici relativi possono essere suddivisi in quattro tipi:

• indici crisp (dall’anglosassone: secchi – il contrario di fuzzy);

• indici fuzzy;

• indici probabilistici;

• indici di stabilità.

Per calcolarli vengono usati due tipi di misure: misure dirette e misure indirette.

Le misure dirette sono possibili quando la partizione dello spazio è stata fatta in modo netto,

non sfumato. E’ evidente che non è possibile misurare una spazio quando non è stato

esattamente delimitato (si immagini di misurare il diametro di un cerchio “sfumato”).

Nel caso in cui lo spazio non è ben definito si utilizzano misure indirette. In questo caso lo

spazio deve essere prima ricondotto ad uno spazio partizionato nettamente (e quindi non fuzzy).

A questo scopo vengono introdotti procedimenti di “defuzzyficazione” e “deprobabilizzazione”.

Nel primo indice, l’attributo crisp è praticamente sinonimo di misura diretta, nel senso che per

questi indici è necessario sapere soltanto a quale cluster appartiene il generico pattern. Questi

indici si applicano quindi nel caso di algoritmi di clustering crisp oppure dopo defuzzificazione,

o deprobabilizzazione, nel postprocessing di algoritmi fuzzy o probabilistici.

Nel caso degli indici fuzzy si può esprimere anche il grado di appartenenza di un pattern ad un

cluster, essi possono essere suddivisi in due ulteriori categorie:

§ semplicemente fuzzy: sono quelli in cui per ogni pattern è necessario conoscere il cluster ed

il grado di appartenenza. Poiché bisogna conoscere il cluster di appartenenza, questi sono

indici diretti che possono applicarsi soltanto dopo defuzzificazione di un algoritmo fuzzy o

dopo fuzzificazione di un algoritmo crisp.

§ puramente fuzzy: sono quelli in cui per ogni pattern è necessario conoscere solo il grado di

appartenenza a ciascun cluster. Sono indici indiretti in cui non è necessaria alcuna

defuzzificazione di un algoritmo fuzzy ma rimane necessaria la fuzzificazione per un

algoritmo crisp o probabilistico.

Gli indici di stabilità, infine, stabiliscono per quanto tempo una determinata partizione non

subisce mutamenti. Questi indici possono essere sia diretti che indiretti, a seconda del criterio

stabilito per determinare quando una partizione è cambiata. Nella fattispecie si introdurranno gli

indici Lifetime, Jaccard, e Rand Adjusted in cui gli ultimi due, che si basano su partizioni crisp,

richiederanno procedure di defuzzificazione quando necessario.


107

Prima di elencare gli indici più importanti si vuole sottolineare che, data una distribuzione di

patterns, la possibilità di riuscire ad individuare raggruppamenti degli stessi dipende

chiaramente dalla loro distribuzione spaziale e dalle loro reciproche distanze. Prendendo in

considerazione una delle definizioni date di cluster [Everitt 1974] si potrebbe affermare che:

‘una suddivisione in clusters è buona se la distanza tra due generici punti interni ad un cluster è

piccola mentre la distanza tra due generici punti appartenenti a clusters differenti è grande’.

L’attenzione dovrebbe a questo punto spostarsi su quanto piccola o quanto grande debba essere

la distanza tra due patterns, tornando così al problema di dover determinare in modo assoluto il

valore di una funzione. In generale si può dire che una buona partizione dà origine a clusters

ciascuno dei quali ha punti interni molto più vicini tra loro di quanto non lo siano i patterns

appartenenti a clusters diversi. Questo criterio non è sempre valido, si pensi a insiemi di data

che presentano strutture filiformi: è intuitivo associare a ciascuna struttura filiforme un cluster

nonostante che la distanza tra i punti estremi di una struttura possa essere maggiore di quella tra

due punti appartenenti a strutture filiformi diverse. Tenendo presenti questi concetti, la

partizione ottima sarà quella che tende a privilegiare le caratteristiche di compattezza e di

separabilità di un cluster rispetto agli altri individuati.


108

3.3 La rete neuro-fuzzy basata su hyperboxes (CLS2)

In questo paragrafo si descriverà la struttura di uno dei due classificatori utilizzati, basato su una

struttura a hyperbox4, sia dal punto di vista della topologia della rete, sia da quello

dell’algoritmo di addestramento. Inizialmente verrà descritto l’algoritmo Min-Max di Simpson

[Simpson 1992, Simpson 1993] in quanto diverse idee alla base del presente lavoro traggono

spunto proprio da questo algoritmo, soprattutto per quanto riguarda la rappresentazione dei

clusters, almeno nella fase iniziale.

3.3.1 L’algoritmo Min-Max

Presentato da Simpson nel 1992, questo algoritmo si distingue per la semplicità e il basso costo

computazionale delle strutture geometriche usate per partizionare lo spazio di ingresso. Le

regioni corrispondenti alle diverse classi vengono ricoperte con degli hyperboxes, rettangoloidi

aventi le facce parallele ai piani coordinati del sistema di riferimento fissato nello spazio di

ingresso. Ciascuno di questi hyperboxes è individuato in maniera univoca mediante due

particolari punti, il punto Min v e il punto Max w , che rappresentano, rispettivamente, il vertice

più vicino e quello più lontano dall’origine del sistema di riferimento in questione (vedi figura

3.8a e 3.8b) e che danno il nome all’algoritmo stesso. Il basso costo computazionale e

l’economicità di rappresentazione di queste strutture sono dovuti principalmente a due motivi:

1. questi hyperboxes, proprio in virtù della loro particolare disposizione spaziale, vengono

descritti mediante un numero relativamente basso di parametri (le 2n coordinate di tali

punti, essendo n la dimensione dello spazio)

2. l’operazione di verifica dell’appartenenza di un punto ad essi si riconduce all’esecuzione di

semplici confronti tra grandezze.

L’algoritmo, di tipo costruttivo, consta essenzialmente di tre fasi in successione. Nonostante ciò

in un’unica epoca di addestramento (cioè esaminando i punti del training set ciascuno una sola

volta) ottiene la ricopertura dello spazio e la costruzione della corrispondente rete neurale. La

struttura di quest’ultima consiste di tre strati di neuroni: oltre lo strato di ingresso (n neuroni,

ciascuno connesso con tutti i neuroni dello strato successivo), esiste uno strato nascosto che

conta tanti neuroni quanti sono gli hyperboxes formatisi durante l’addestramento. Inoltre vi è

4 Si fa riferimento ad un classificatore implementato all’università di Roma “La Sapienza” denominatoCLS2 [Risi 1997].


109

uno strato di uscita, formato da tanti neuroni quante sono le classi da discriminare. È evidente

che la complessità della rete dipende essenzialmente dal numero di hyperboxes formatisi ed in

generale è maggiore in corrispondenza di insiemi di dati particolarmente difficili da ricoprire.

Una volta fissato il problema, tale complessità dipende inoltre da un parametro θ che regola lo

svolgimento dell’addestramento stesso. Rimandando i dettagli in seguito, per il momento va

sottolineato che tale parametro, che varia nell’intervallo [0;1], limita l’estensione degli

hyperboxes, rivestendo il significato di massima estensione media (lungo tutte le dimensioni)

raggiungibile da ciascuno di essi. Addestramenti con valori di θ piccoli danno luogo ad un

numero elevato di hyperboxes, mentre valori più alti di questo parametro creano pochi

hyperboxes, ciascuno di dimensioni più estese rispetto al caso precedente.

Fig. 3.8a: Un hyperbox nello spazio tridimensionale

Fig.3.8b: Generazione di vari hyperboxes per clusterizzare alcuni patterns con il metodo Min-Max


110

Per ogni nuovo pattern del training set presentato alla rete in fase di addestramento, il processo

di costruzione della rete compie le sue tre fasi:

• Espansione: in questa fase uno degli hyperboxes già presenti, relativo alla classe di

appartenenza del pattern in questione, viene fatto espandere fino a contenere il pattern

stesso, compatibilmente col valore di θ correntemente impostato; se tale espansione non è

possibile, allora viene creato un nuovo hyperbox avente i punti di Min e di Max coincidenti

col pattern stesso (hyperbox degenere);

• Test di Overlap: non è ammissibile che hyperboxes di diverse classi si sovrappongano,

quindi viene effettuato questo test verificando l’eventuale occorrenza di tali

sovrapposizioni;

• Contrazione: nell’eventualità in cui si siano verificate una (o più) sovrapposizioni, si

procede a contrarre gli hyperboxes interessati, in maniera tale da eliminarle.

Ad ogni hyperbox è associata un’opportuna funzione di appartenenza di tipo fuzzy, per cui, alla

fine della procedura di training, tutti i punti del training set interni ai vari hyperboxes

apparterranno per un valore unitario agli stessi, mentre punti esterni (che risultano esterni a

causa delle contrazioni effettuate) avranno appartenenza tanto meno marcata quanto più

risulteranno lontani dalla frontiera di questi, secondo il valore di un ulteriore parametro γ, che

regola la fuzzyness delle funzioni di appartenenza stesse.

Fig. 3.9a: Schema dell’andamento della funzione di appartenenza nel caso bidimensionale

Fig.3.9b: Esempi di reali funzioni di appartenenza utilizzate


111

Nella fig. 3.9a è evidenziato un hyperbox nello spazio bidimensionale (n=2) con i suoi due punti

v e w , e uno spaccato dell’andamento della funzione di appartenenza (o membership function,

nel seguito per brevità funzione di appartenenza). Come si vede, tale funzione di appartenenza

dà valore costantemente pari ad uno in corrispondenza di punti interni all’hyperbox e valori

degradanti in dipendenza dal parametro γ all’esterno di esso.

Più formalmente, detta µ tale funzione di appartenenza, la sua espressione analitica, che esprime

l’appartenenza del generico pattern (dell’elemento i-mo) al hyperbox h-mo, è la seguente:

µh i ij hj hj ijj

n

xn

f x w f v x( ) [ ( ) ( )]= − − − −=

∑11

1

(3.2)

in cui, con le notazioni già accennate:

n è la dimensione dello spazio d’ingresso;

x in∈ℜ è l’i-mo pattern;

v hn∈ℜ è il punto Min dell’h-mo hyperbox;

whn∈ℜ è il punto Max dell’h-mo hyperbox;

f : [ ]ℜ → 0 1, è una funzione così definita:

f y

y

y y

y

( )

,

=⋅ >

⋅ ≤ ⋅ ≤⋅ <

1 1

0 1

0 0

se

, se

, se

γγ γ

γ

Fig. 3.10: Andamento della f (y)


112

Il parametro γ definisce la velocità di decadenza a zero della funzione di appartenenza

allontanandosi dall’hyperbox, cioè la caratteristica fuzzy della funzione di appartenenza stessa:

valori bassi di γ accentuano tale caratteristica, mentre valori alti la attenuano; al limite, per

γ → ∞ l'appartenenza diviene di tipo aristotelico: µ è uguale ad 1 se il pattern è interno

all’hyperbox, ed è uguale a 0 altrimenti.

Si capisce, da quanto appena detto, perché non è possibile che punti dello spazio siano interni a

due diversi hyperboxes. Tali punti, infatti, avrebbero appartenenza unitaria a ciascuno dei due

hyperboxes, mentre dal punto di vista della logica fuzzy non ha senso il fatto che un elemento

appartenga per un valore pari ad uno a due insiemi diversi.

Dei due parametri che governano il comportamento dell’algoritmo, γ ha influenza solo sulla

creazione della regione di decisione, ma non sulla creazione degli hyperboxes, né tantomeno sul

numero e l’estensione degli stessi. Di fatto la cosa può essere vista così: durante

l’addestramento si opera una partizione dello spazio ricoprendo quest’ultimo con degli

hyperboxes secondo quanto descritto sopra, effettuando una operazione prettamente geometrica

che nulla ha a che vedere con le caratteristiche fuzzy del classificatore e che dipende, fissato il

training set, solo dal valore del parametro θ. Successivamente, ciascuno di tali hyperboxes viene

“coperto” da una funzione di appartenenza che, alla stregua di una tovaglia (l’analogia è

evidente, in Fig. 3.9, nel caso n=2), si appoggerà a ciascun hyperbox ad altezza 1 da questo e

degraderà, esternamente ad esso, in dipendenza dal valore del parametro γ fino a raggiungere il

valore zero. Di fatto, a partizione avvenuta, una variazione di γ influisce solo sull’influenza che

gli hyperboxes hanno sulle regioni di spazio esterne ad essi, mentre gli hyperboxes stessi

restano uguali, sia nel numero che nelle dimensioni. Una volta definita una funzione obiettivo

che giudichi le partizioni effettuate dall’algoritmo in relazione al training set corrente, si può

fissare γ ad un valore ragionevole predefinito (di default) e cercare la partizione ottima, secondo

tale funzione obiettivo, al variare di θ nell’intervallo [0;1].

3.3.2 Il singolo clusterizzatore

Il compito di effettuare la partizione dello spazio di ingresso relativamente alla k-ma classe del

training set è espletato da un singolo clusterizzatore. La procedura di addestramento, di tipo

costruttivo, che dà luogo alla parte di rete contenente tutti e soli i clusters relativi alla classe k, si

ispira, come appena visto, a quella originariamente proposta da Simpson.


113

In generale, la risoluzione del problema di clustering di un insieme di dati può essere

schematicamente decomposta in due fasi distinte. La prima di queste consiste nell’associare ad

ogni pattern dell’insieme un’indicazione del cluster di appartenenza, cioè in sostanza,

“l’indirizzo” del pattern stesso (tale indicazione potrebbe essere, ad esempio, il centroide del

cluster). Alla fine di questa fase il risultato è una “tabella” in cui ad ogni pattern è associato il

suo indirizzo. Questa sorta di tabella non contiene alcuna informazione circa i punti dello spazio

che non appartengono all’insieme di dati di partenza, né circa la struttura geometrica dei clusters

stessi. Lo spazio di ingresso, cioè, è generalmente “sconosciuto” e solo localmente “noto”

(l’informazione posseduta su di esso è cioè di tipo discreto). Nella seconda fase l’assegnazione

di una struttura fisica ai clusters permette di giudicare la loro influenza su tutti i punti dello

spazio rendendo così l’informazione sullo spazio di natura continua. Nel caso di un sistema

fuzzy, questa 7seconda fase corrisponde all’assegnazione di una forma geometrica ai clusters e,

successivamente, alla “ricopertura” di questi con una funzione di appartenenza. Questa

suddivisione del problema in due fasi è solo di carattere concettuale; di fatto queste ultime non

vengono necessariamente svolte in sequenza, potendo essere, a seconda dell’algoritmo, svolte in

parallelo e simultaneamente.

Come già descritto, l’algoritmo originale di Simpson partiziona lo spazio di ingresso mediante

l’uso di hyperboxes ciascuno dei quali è univocamente individuato nello spazio n-dimensionale

mediante le coordinate dei due suoi punti min v e max w. Il singolo clusterizzatore di questo

lavoro svolge una procedura analoga al fine di desumere informazioni di tipo geometrico su

quelli che saranno successivamente i clusters. L’algoritmo di apprendimento del clusterizzatore

che lavora sulla k-ma classe è caratterizzato da una successione di processi di

creazione/espansione di hyperbox in seguito alla presentazione alla rete dei

patterns x i appartenenti alla classe k.

Data la natura “on line” dell’algoritmo, i patterns vengono elaborati nell’ordine in cui sono

presentati alla rete. Inizialmente, lo strato nascosto della rete non contiene alcun neurone

relativo alla classe k. Quando viene presentato il primo pattern x1 di quella classe, l’algoritmo

crea un hyperbox avente i punti di minimo e massimo coincidenti con il pattern stesso

(hyperbox degenere).

Successivamente, per ogni nuovo pattern x i , viene valutata la possibilità di annettere tale

pattern ad un hyperbox già esistente in base ad una certa regola di annessione e, se è il caso, si

espande tale hyperbox in modo da includerlo, altrimenti si crea un nuovo hyperbox degenere.


114

L’espansione dell’hyperbox h-mo dovuta all’annessione del pattern x i viene effettuata usando

le seguenti espressioni:

v v x j n

w w x j n

hjnew

hjold

ij

hjnew

hjold

ij

= ∀ =

= ∀ =

min( , ) ,...,

max( , ) ,...,

1

1

Nelle formule precedenti, gli apici new stanno ad indicare i nuovi valori, mentre quelli old

indicano gli stessi valori prima dell’aggiornamento.

La valutazione della possibilità di annessione di un pattern ad un dato hyperbox può essere

effettuata secondo tre diverse regole, ciascuna delle quali prende il nome dal parametro che ne

caratterizza il comportamento. In seguito viene fornita una descrizione di ciascuna di esse.

Regola Theta

Dato l’i-mo pattern e l’h-mo hyperbox, quest’ultimo verrà espanso fino a contenere il pattern se

e solo se accade che:

(max( , ) min( , ))w x v x nhjj

n

ij hj ij=

∑ − ≤ ⋅1

θ

in altre parole se e solo se la media delle lunghezze degli spigoli dell’ hyperbox h lungo tutte le

dimensioni, ad espansione effettuata, rimane minore o uguale di un certo valore θ ∈[ , ]0 1 che è

un parametro dell’algoritmo da fissarsi prima dell’inizio dell’addestramento e che resta uguale

per tutti gli hyperbox di quella classe. Questa regola di annessione è la stessa proposta da

Simpson nel Min-Max.

Regola Delta

Dato l’i-mo pattern e l’h-mo hyperbox, e detto ch il centroide di questo (cioè la media dei

patterns già contenuti al suo interno), l’espansione avviene se e solo se accade che:

c xh i− ≤ δ

cioè se e solo se il pattern i è compreso in un’ipersfera di raggioδ con centro in ch . Il

parametroδ , come nel caso precedente, deve essere fissato prima dell’inizio dell’addestramento

e governa il comportamento di quest’ultimo relativamente alla classe k. L’intervallo di valori

ammissibili di δ, nel caso di un problema n-dimensionale, è l’intervallo [ ; ]0 n . Nell’ipercubo


115

unitario n-dimensionale, infatti, n è la più grossa distanza possibile tra due punti interni ad

esso.

Il comportamento dell’algoritmo varia in maniera analoga al crescere dei due parametri: alti

valori, sia di θ che di δ, permettono grandi espansioni dando luogo a pochi hyperboxes ciascuno

con un elevato numero di patterns all’interno, mentre valori bassi portano alla formazione di un

numero di hyperboxes in generale più elevato, essendo ciascuno di essi meno densamente

popolato. In ambedue i casi, se la lista dei possibili candidati all’espansione contiene più di un

hyperbox, tra questi si sceglie quello che ha il centroide a minore distanza dal pattern.

Le due regole, di tipo prettamente geometrico, sono tra loro molto simili. Una delle principali

differenze che intercorrono tra esse è legata al significato dei parametri che le governano, in

relazione alla espansione degli hyperboxes. Mentre θ riveste il ruolo di grandezza mediata su

tutte le dimensioni, δ influenza l’espansione lungo ciascuna dimensione in modo del tutto

indipendente dalle altre.

Questi criteri di annessione sono entrambi di tipo prettamente geometrico. È possibile, però,

tentare anche un approccio di tipo più legato alla logica fuzzy. Un ulteriore criterio di

annessione di questo tipo, peraltro già adottato in [Jain 1988], è descritto di seguito.

Regola Beta

Dato l’i-mo pattern e l’h-mo hyperbox, l’espansione avviene se e solo se accade che:

µ βh ix( ) ≥

cioè se e solo se l’appartenenza fuzzy del pattern i all’hyperbox h, calcolata secondo

l’espressione adottata da Simpson, è maggiore di un certo valore β ∈[ ; ]0 1 . Il parametro β ,

come nei casi precedenti, deve essere fissato prima dell’inizio della procedura di addestramento

relativa alla k-ma classe.

Mentre nel caso della regole precedenti l’annessione è legata a fattori essenzialmente di tipo

geometrico (estensione degli hyperboxes), nel caso della regola Beta la stessa annessione è

subordinata alla vicinanza in senso fuzzy del pattern all’hyperbox. Quest’ultima regola ha il

pregio di avere un significato intuitivo più immediato; è infatti più facile fissare a priori un

valore di appartenenza fuzzy piuttosto che un valore di massima espansione media di un

hyperbox.

Lo svantaggio principale di questa regola si evidenzia particolarmente di fronte a distribuzioni

di patterns uniformi, tali cioè che la distanza tra ciascun pattern e quelli immediatamente vicini

è più o meno costante per tutti i patterns. In questo caso, durante la fase di addestramento, in


116

corrispondenza di ciascun nuovo pattern la situazione è sempre la stessa, indipendentemente

dalle dimensioni correnti di un hyperbox: o il pattern appartiene per più di β all’ hyperbox, e

quindi quest’ultimo viene espanso, oppure non vi appartiene e allora viene creato un nuovo

hyperbox degenere. Accade, cioè, che eseguendo un certo numero di addestramenti con valori di

β via via crescenti non si nota una crescita graduale della complessità della rete. Si ottengono

configurazioni che passano da un numero di neuroni basso (una o poche unità) a un numero

pari, o poco più basso, del numero di patterns complessivamente presenti. In tal caso non è detto

che esista un valore del parametro che produca una configurazione della rete accettabile. Questo

succede perché la velocità di decadimento della funzione di appartenenza, decisa dal solo valore

di γ, è indipendente dalle dimensioni dell’hyperbox e quindi, nel caso di distribuzioni uniformi,

l’esame del primo pattern dà luogo agli stessi risultati dell’esame di qualsiasi altro.

Nelle regole geometriche, invece, esiste una sorta di “memoria”, per cui l’annessione di un

pattern ad un hyperbox non dipende solo dalla posizione del pattern rispetto ai punti di min e

max dell’hyperbox stesso, ma anche dallo “stato” dell’hyperbox al momento dell’annessione. Se

l’hyperbox ha già raggiunto dimensioni vicine alle massime consentite dalla regola di

annessione, anche se il pattern è vicinissimo a uno dei punti v e w, potrà darsi che l’espansione

non avverrà comunque. Usando quindi una delle regole geometriche, e eseguendo un certo

numero di iterazioni con valori del parametro (θ o δ) via via decrescenti, la crescita della

complessità della rete aumenta in maniera più regolare; in questi casi, quindi, la scelta di regole

di annessione di tipo geometrico dà luogo ad una più ampia rosa di configurazioni.

Arrivati a questo punto è già disponibile una partizione dello spazio di ingresso relativamente

alla classe k (ogni pattern del training set possiede un indirizzo assegnato); inoltre le lunghezze

degli hyperboxes lungo ciascuna dimensione forniscono informazioni quantitative sulla

estensione spaziale dei diversi clusters. Il passo successivo verso il completamento della parte di

rete relativa alla classe k consiste nella sostituzione degli hyperboxes con entità geometriche

chiamate a individuare meglio i vari clusters nello spazio e nella conseguente ricopertura di tali

strutture con delle funzioni di appartenenza associate ai singoli clusters della classe.

Le strutture geometriche in questione sono degli hyperellissoidi, la scelta dei quali scaturisce

contestualmente alla decisione sul tipo di funzione di appartenenza da adottare. Quest’ultima è

la “Generalized Bell”, suggerita da Jang e Sun, la cui espressione, nel caso di appartenenza del

pattern x i all’h-mo cluster, è la seguente:


117

µh i

ij hj

hj

b

j

nx

x c

a

hj( )

( )=

+−

=∑

1

1

2

1

(3.3)

Come si vede dalla sua espressione, questa funzione assume valore unitario in un unico punto

dello spazio, il centroide ch del cluster h; inoltre, dato un valore di appartenenza β’ in (0,1], il

luogo dei punti dello spazio che hanno un’appartenenza fuzzy a quel cluster pari a β’ è un

hyperellissoide avente centro in ch e semiassi paralleli agli assi coordinati del sistema di

riferimento fissato nello spazio di ingresso. Il parametro ahj rappresenta la lunghezza del

semiasse, lungo la j-ma dimensione, dell’hyperellissoide isoappartenenza a valore β’=0.5,

mentre il parametro bhj regola la velocità di smorzamento della funzione di appartenenza

all’aumentare della distanza dal centroide lungo la dimensione j. Nella successiva figura 3.11 è

rappresentato l’andamento della funzione di appartenenza nel caso monodimensionale, caso in

cui la funzione di appartenenza assume la forma:

µh bxx c

a

( )( )

=+

−

1

12 (3.4)

L’espressione della funzione di appartenenza adottata, che ha un costo computazionale

leggermente più elevato di quella della funzione di appartenenza a “tovaglia” di Simpson e che

descrive il cluster con un numero leggermente maggiore di parametri (3n invece dei 2n di

Simpson), ha il vantaggio principale di evitare la gestione di sovrapposizioni di a clusters

relativi a classi diverse. Tali sovrapposizioni venivano risolte, nel caso del Min-Max originale,

contraendo gli hyperboxes per evitare che zone dello spazio avessero appartenenza unitaria in

corrispondenza di due o più classi diverse. Nel caso attuale, invece, dato che tale gestione

sarebbe stata comunque impossibile a causa del modo di operare “parallelo” dei diversi

clusterizzatori, si trae vantaggio dal fatto che le regioni di spazio con appartenenza unitaria ad

una data classe sono costituite da insiemi a misura nulla (ciascuno di tali insiemi contiene i

centroidi ch di ogni cluster, tutti isolati tra loro e in numero pari al numero di clusters della

classe in questione). Un altro vantaggio della funzione di appartenenza in oggetto è quello di

eliminare regioni di indecisione dovute al fatto che un punto possa avere un’appartenenza pari a

0 per tutte le classi e quindi non possa essere etichettato in alcun modo; la campana


118

generalizzata, infatti, assume valori sempre diversi da zero per distanze da ch comunque grandi,

purché finite.

Fig. 3.11: Andamento della campana generalizzata

Il legame tra le informazioni geometriche acquisite relativamente ai patterns della classe e le

dimensioni degli hyperellissoidi risiede nel modo in cui vengono fissati i valori dei 2n parametri

a e b di questi ultimi in funzione dei valori, determinati durante l’addestramento, di v e w di

ciascun hyperbox. La sostituzione degli hyperboxes con gli hyperellissoidi viene effettuata

imponendo, lungo ciascuna dimensione, il valore che la funzione di appartenenza deve assumere

in due punti a due diverse distanze dal centroide lungo il semiasse parallelo a quella

dimensione; più precisamente si ha che, detti β1 e β2 (β β2 < 1) due valori assegnati di

funzione di appartenenza e date due distanze dal centroide rhj1 ed rhj

2 ( rhj1 > rhj

2 ), i parametri ahj

e bhj dell’h-mo cluster lungo la j-ma dimensione si determinano risolvendo il sistema:

=

=

22

11

)(

)(

βµ

βµ

hjh

hjh

x

x(3.5)

dove xhjm (m=1,2) è un vettore avente la componente j-ma pari a c rhj hj

m+ e tutte le altre pari a

zero.

1


119

Il sistema precedente è un sistema di due equazioni nelle due incognite ahj e bhj che, una volta

risolto, permette di determinare questi due parametri. Esplicitando si ha:

br

r

ar

hjhj

hj

hj

hj

bhj

=− − −

=

−

ln( ) ln( )

ln( )

( )

11

11

2

11

1 21

2

2

2

1

2

β β

β

(3.6)

Il legame con l’h-mo hyperbox risiede nel modo di fissare i valori delle distanze rhj1 ed rhj

2 in

funzione delle dimensioni dell’hyperbox stesso. Nell’implementazione realizzata è possibile

scegliere a tempo di esecuzione se gli hyperellissoidi debbano essere inscritti o circoscritti agli

hyperboxes. A seconda di quale dei due sia il caso, viene scelto il valore di rhj1 :

r

w v

nw vhj

hj hj

hj hj

12

2

=

−

−

, ellissoide inscritto

, ellissoide circoscritto

il valore di rhj1 , cioè, è strettamente legato alle informazioni sul cluster scaturite

dall’addestramento effettuato con la tecnica tipo Min-Max.

Anche per quanto riguarda la disposizione del centroide ch rispetto all’hyperbox originale, è

possibile scegliere, prima dell’inizio della classificazione, se farlo coincidere con il centro

geometrico dell’hyperbox, cioè:

cw v

hj

hj hj=

+∀

2 , j = 1,.., n

oppure se farlo coincidere con il “baricentro” di tutti i patterns contenuti nell’hyperbox stesso:


120

cn

xhh

ii

nh

==∑1

1

essendo nh il numero di patterns contenuti nell’hyperbox h.

Per quanto riguarda il valore di rhj2 , si è rivelato opportuno di porre rhj

2 = rhj1 +λ, essendo λ un

valore positivo uguale per tutti i clusters e per tutte le dimensioni. Anche il valore di λ può

essere scelto, a tempo di esecuzione, prima dell’inizio della procedura di addestramento;

peraltro, il valore di default, scelto pari a 0.4, si è rivelato appropriato nella maggior parte dei

casi.

Per quanto riguarda i due valori di funzione di appartenenza, mentre per β1 è stato fissato un

valore, uguale per tutti e lungo tutte le dimensioni, pari a 0.9, per β2 il discorso è leggermente

diverso. L’utente infatti può scegliere se usare un approccio di tipo puramente geometrico,

ovvero un approccio di tipo “gravitazionale”. Nel primo caso β2 segue la stessa sorte di β1 , e

viene fissato ad un valore di 0.1 per tutti i clusters, mentre nel caso “gravitazionale” (si ricorda

che in questo caso l’influenza di un cluster cresce col numero di patterns in esso contenuti) si

adotta per esso l’espressione:

β β ε2 1= ⋅ −( )nN

h

in cui nh è il numero di patterns contenuti nel cluster h, N è il numero di patterns

complessivamente presenti nel training set e ε è un numero positivo piccolo (posto pari a 10 6− )

introdotto per poter gestire il caso di clustering, caso in cui nel training set è presente un’unica

classe, in cui viene prodotto un unico cluster. In tal caso, infatti, se fosse ε = 0 , si avrebbe

n N1 1= e quindi β β2 1= , con la conseguente impossibilità di risolvere il sistema.

Con queste scelte dei valori, quindi, allontanandosi dal centroide ch del cluster, parallelamente

alla dimensione j-ma, la µ h passa dal valore unitario al valore β1 (=0.9) in corrispondenza di

uno spostamento di entità pari a metà della lunghezza dello spigolo dell’hyperbox originale

lungo tale dimensione (nel caso di hyperellissoide inscritto all’hyperbox), e al valore di β2 in

corrispondenza di un ulteriore spostamento di entità pari a λ .

In conclusione, e per quanto fino ad ora detto, una volta impostato il valore di un parametro (θ,

β o δ, a seconda del tipo di regola di annessione scelta), il singolo clusterizzatore è in grado di

effettuare la partizione della classe che gli compete, per cui, fissati k di questi valori, ciascuno

per ogni clusterizzatore, alla fine delle procedure di clustering delle singole classi si otterrà la


121

regione di decisione determinata dal training set in questione. È evidente come la bontà delle

singole clusterizzazioni dipenda in maniera determinante dai valori, assegnati classe per classe,

dei suddetti parametri, e come tali valori debbano essere scelti accuratamente in base alle

caratteristiche di distribuzione della popolazione di patterns relativi a ciascuna classe.

Ciò era già stato messo in evidenza alla fine del paragrafo precedente.

3.3.3 Gli indici

Nel paragrafo precedente erano stati elencati i vari tipi di indici di bontà che vengono usati per

la classificazione. Di seguito si riportano alcuni dei più noti indici, implementati anche nella rete

basata su hyperboxes. Si tratta di indici di qualità e vengono presi prima in considerazione gli

indici relativi crisp e successivamente gli indici relativi fuzzy.

3.3.3.1 Indici relativi crisp

Indice di Davies-Bouldin

L’indice di Davies-Bouldin (DI) si calcola, data una partizione, a partire dalla conoscenza della

sola “tabella” degli indirizzi dei patterns ed è quindi indipendente dalla forma geometrica

assegnata ai clusters. Le informazioni di tipo geometrico, inerenti alla partizione, rientrano nel

calcolo dell’indice tramite i valori delle distanze tra i vari patterns e tra questi e i centroidi dei

clusters. Le grandezze usate nel calcolo del DI sono le seguenti:

compattezza del cluster k: e x ck j kj

nk

= −=

∑2

1

separazione dei clusters j e k: Re e

c cjk

j k

j k

=+

−

indice per il cluster k: Rk = maxj≠k{Rjk}

e l’espressione dell’indice in funzione di queste caratteristiche è:

∑=

=cN

kk

cc R

NNDI

1

1)(


122

Nelle precedenti equazioni, nk e ck rappresentano, rispettivamente, il numero di patterns

contenuti nel cluster k e il centroide dello stesso, mentre N c è il numero di clusters ottenuti

globalmente nella partizione.

Questo indice è tanto più piccolo quanto più i clusters sono compatti (bassi valori degli ek ) e

quanto più sono lontani tra loro (elevati valori di c ck j− ), per cui la partizione ottima si

ottiene in corrispondenza del suo minimo assoluto. Un problema dell’indice DI è dovuto al fatto

che clusters contenenti un unico pattern hanno valore di compattezza ek = 0 , per cui, in

corrispondenza alla clusterizzazione “degenere” (quella con tanti clusters quanti sono i patterns

nel data set), l’indice, che è sempre di norma non negativo, assume valore pari a 0 e quindi,

senza un criterio di arresto nella ricerca (esplorando cioè tutto l’intervallo di ammissibilità dei

parametri), il DI fornirebbe come ottima la partizione a complessità del 100%, dando luogo in

tal modo ad una rete con capacità di generalizzazione nulla. Alla luce di questo problema sono

nate delle modifiche al calcolo della espressione che hanno dato luogo a diverse varianti del DI.

Indice di Davies-Bouldin a pesatura singola

Questo indice (SWDI, Single-Weighted Davies Index) cerca di risolvere il problema evidenziato

nella sezione precedente. L’indice DI, infatti, tende a decrescere al crescere del numero di

clusters nella partizione, per cui fornisce in generale reti ad elevata complessità. Nel caso di

SWDI, è stato introdotto un termine moltiplicativo che penalizza questo tipo di partizioni. La

struttura e le modalità di calcolo sono del tutto analoghe a quelle del caso precedente:


nk

= −=

∑2

1


c cNN

jk

j k

j kc

=+

− ⋅ −( )1 2



∑=

=cN

kk

cc R

NNSWDI

1

1)(

espressione, peraltro, identica a quella nel caso di DI.


123

Le notazioni usate sono le stesse del caso precedente e, in aggiunta a queste, N rappresenta il

numero di patterns complessivamente presenti nella classe in questione:

N nkk

Nc

==

∑1

Come si vede dall’espressione della separabilità, il termine moltiplicativo a denominatore tende

a zero al tendere di Nc a N, facendo crescere in tal modo il valore dell’indice al crescere della

complessità della rete.

Indice basato sulla distanza euclidea

L’indice Euclidean Distance Based (EDB) possiede una struttura analoga a quella del SWDI ; le

differenze rispetto a questo risiedono nel calcolo della compattezza del singolo cluster, nonché

nell’espressione dell’indice per il singolo cluster. Si riportano, come per gli altri casi, le

espressioni che sono d’aiuto nel calcolo dell’indice:

compattezza del cluster k: en

x ckk

j kj

nk

= −=

∑1

1


c cNN

jk

j k

j kc

=+

− ⋅ −( )1 2

indice per il cluster k: R Rk jkjj k

Nc

==≠

∑1

Come si vede, in questo caso la compattezza del singolo cluster coincide con la media delle

distanze di ciascun pattern dal centroide del cluster, mentre l’indice per il singolo cluster è pari

alla somma dei valori R jk e non al massimo di essi, come nei casi precedenti. L’espressione

dell’indice in funzione delle precedenti quantità è:

∑=

=cN

kk

cc R

NNEDB

1

1)(

identica a quella relativa ai due casi precedenti.

Indice di Davies-Bouldin doppiamente pesato

In questo caso (DWDI, Double Weighted Davies Index), oltre al coefficiente moltiplicativo che

penalizza reti ad elevata complessità, introdotto nel SWDI, esiste un ulteriore termine che tende


124

a far crescere l’indice relativo al singolo cluster nel caso in cui quest’ultimo contenga un

numero troppo elevato di patterns. I passi necessari al calcolo sono i seguenti:


nk

= −=

∑2

1


c cN

N

n

N

jk

j k

j kc k

=+

− ⋅ − −( )( )1 1



∑=

=cN

kkc RNDWDI

1

)( .

Da notare, in questo caso, la mancanza di simmetria nell’espressione dell’indice; accade, cioè,

che R jk è diverso da Rkj in quanto il nuovo termine correttivo introdotto compare solo

relativamente al cluster k nel calcolo di Rk .

Nel programma di simulazione, è stata implementata anche la variante simmetrica (DWDI2)

uguale in tutto e per tutto al DWDI, con l’unica differenza che l’espressione della separazione è

rimpiazzata dalla seguente:

Re e

c cN

N

n

N

n

N

jk

j k

j kc k j

=+

− ⋅ − − −( )( )( )1 1 1

Nonostante la maggiore correttezza formale di questa seconda espressione, l’evidenza

sperimentale mostra che l’espressione DWDI fornisce risultati migliori nella quasi totalità dei

casi esaminati.

Ci sarebbe da fare un’ulteriore considerazione in merito alla valutazione della bontà di un

clustering: nonostante la natura fuzzy delle singole partizioni ottenute, ciascuno degli indici

relativi sopra presentati considera le stesse, in fase di valutazione, come rigidamente

aristoteliche. Ciascun pattern, cioè, nel calcolo degli indici, viene considerato come

appartenente interamente ad uno e un unico cluster. Si potrebbe tentare un’altra via, che dia

un’indicazione fuzzy della bontà delle singole partizioni, sfruttando i valori di appartenenza

fuzzy di tali patterns a ciascun cluster prodotto nella partizione. Seguendo questa linea di


125

ragionamento, si è provato ad ideare degli indici che “traducessero” in termini fuzzy le

caratteristiche di compattezza e separabilità dei clusters.

Si è adottata, come misura della non compattezza fuzzy del cluster k, la seguente espressione:

L’espressione fornisce il valore della non appartenenza totale dei patterns inclusi nel cluster k al

cluster stesso. Quanto più il valore di ck è alto, tanto più i patterns contenuti nel cluster sono

“sparpagliati” in senso fuzzy. Il valore zero si ottiene nel caso in cui tutti i patterns hanno

appartenenza unitaria al cluster (i casi in cui ciò si verifica sono quelli di clusters contenenti un

solo pattern, ovvero i casi in cui tutti i patterns sono sovrapposti e coincidono con il centroide

del cluster), mentre il valore limite, pari a nk , non si ottiene mai (si ricorda che la campana

generalizzata dà un valore sempre diverso da zero per distanze finite dal centroide del cluster).

3.3.3.2 Indici relativi fuzzy

Indice fuzzy comp/comp

Nel caso di questo indice (FCC), indicata con {C1,, C2, …, CNc} la partizione da valutare, il

termine relativo al singolo cluster è definito come segue:

R

x

Nx

k

k ix C

cj i

x Cjj k

Ni k

i j

c=

−

+−

−

∈

∈=≠

∑

∑∑

( ( ))

( ( ))

1

11

11

1

µ

µ

e l’espressione dell’indice in funzione di questa è:

FCC NN

Rcc

kk

Nc

( ) ==

∑1

1

del tutto analoga alle precedenti.

Il termine Rk, in funzione della non compattezza fuzzy prima introdotta, può essere espressa

nella forma:

∑=

−=kn

iikk xc

1

))(1( µ


126

∑≠=−

+=

cN

kjj

jc

kk

cN

cR

111

1

da cui si vede come il termine relativo al k-mo cluster, Rk , confronta essenzialmente una

caratteristica del cluster stesso col valore medio della stessa caratteristica relativa agli altri

clusters. La minimizzazione dell’indice corrisponde quindi a separare il più possibile la non

compattezza di ciascun cluster dal valore medio della stessa relativa a tutti gli altri clusters.

Indice fuzzy comp/sep

L’altro indice fuzzy proposto (FCS) è del tutto analogo al precedente, con la differenza che al

denominatore dell’indice relativo al singolo cluster k, si valuta la media delle appartenenze dei

patterns del cluster k a tutti gli altri clusters:

R

x

Nx

k

k ix C

cj i

x Cjj k

Ni k

i k

c=

−

+−

−

∈

∈=≠

∑

∑∑

( ( ))

( ( ))

1

11

11

1

µ

µ

Come si vede, la differenza tra questa espressione e quella dell’indice Fuzzy CompComp risiede

nel fatto che la sommatoria più interna nel denominatore è estesa, qualunque sia il valore di j, ai

patterns appartenenti al cluster k, mentre nella Fuzzy CompComp, la stessa è calcolata in

corrispondenza ai patterns di tutti i clusters di indice j diverso da k.

3.3.3.3 La procedura di ricerca dell’ottimo

In generale, l’andamento degli indici considerati non è regolare, ma piuttosto presenta,

localmente, oscillazioni anche di entità piuttosto significativa. Per evitare, quindi, di incappare

in un minimo relativo, è necessario campionare uniformemente tutto l’intervallo di variabilità

del parametro di addestramento. Al fine di ridurre il più possibile il tempo di elaborazione, si è

adottata una strategia di ricerca del parametro che, pur assicurando la convergenza verso una

soluzione ottima, riduce il più possibile i tempi di elaborazione. La procedura di clustering

ottimizzato di una data classe, alla generica iterazione, prende l’intervallo di ricerca del

parametro, lo divide in s sottointervalli uguali (s=10), ciascuno di ampiezza ∆, individuando s+1

punti (i due estremi dell’intervallo e tutti i punti interni di separazione di sottointervalli


127

contigui), ed effettua s+1 iterazioni della procedura di clustering calcolando, alla fine di ogni

iterazione, il valore del corrispondente indice ottenuto. Alla fine di questo procedimento è

disponibile il valore del parametro (tra gli s+1 valori esaminati) che dà luogo al minimo valore

dell’indice. A questo punto si effettua uno zoom attorno a tale valore ottimo procedendo in

questo modo: si divide l’intervallo di ampiezza 2∆, centrato attorno all’ottimo, in s+2

sottointervalli uguali individuando così s+3 punti. Il nuovo intervallo di ricerca sarà pari

all’unione dei sottointervalli, dal secondo all’(s+1)-mo. In altre parole, cioè, degli s+3 punti

individuati nello zoom, ne verranno esaminati un numero pari a s+1, cioè tutti meno il primo e

l’ultimo (Fig. 3.12), come nella precedente iterazione.

Fig. 3.12: Lo zoom nella procedura di ricerca dell'ottimo


128

3.4 Il classificatore basato sulla PCA (Principal Component

Analysis) (Classlab)

3.4.1 Introduzione

Esistono altri classificatori neuro-fuzzy che non usano l’algoritmo basato sui hyperboxes. Un

classificatore recente basato su un modello di clustering diverso verrà spiegato qui di seguito.

Prima di inoltrarsi nei dettagli tecnici del classificatore5 è utile esporre brevemente le sue

caratteristiche innovative.

Il classificatore è dotato di un approccio di scala. Ciò vuol dire che il classificatore ha la

possibilità di “osservare” lo spazio dei patterns da varie “distanze”. Similmente a come avviene

con la percezione visiva dell’uomo, (vedendo piccoli puntini raggruppati da lontano appariranno

come un unico punto, mentre ravvicinandosi si riesce sempre meglio a distinguere i singoli

punti fino a poter eventualmente riconoscere i dettagli più particolari) il classificatore in

questione ha la possibilità di “vedere” lo spazio dei patterns da diverse “distanze” valutando,

attraverso un parametro, se questa distanza è quella più opportuna. Ottimizzando un parametro,

il parametro di scala, si riesce a stabilire la risoluzione ideale per procedere con il clustering.

Il modello del clustering è diverso da quello proposto per l’altro classificatore. Infatti in questo

caso il clustering avviene per via probabilistica. Il classificatore stabilisce per ogni cluster una

funzione di probabilità. Questa funzione di probabilità viene generata dai parametri che a loro

volta vengono influenzati dai patterns. Viceversa, una volta ipotizzata la funzione di probabilità,

essa viene migliorata man mano con un processo iterativo che stabilisce la funzione di massima

verosimiglianza del singolo pattern al rispettivo cluster. Il clustering viene fatto con la PCA

(Principal component analysis6) ciò vuol dire che il classificatore ha la capacità di associare ad

un cluster un asse principale e viceversa di collegare i centri dei singoli clusters attraverso altri

assi. Se vede che dentro al cluster i patterns sono troppo distanti gli uni dagli altri (i calcoli

vengono fatti in base all’asse principale), il processo di clusterizzazione divide il cluster

(splitting) lungo l’ortogonale all’asse principale e genera così due nuovi clusters. Questo

processo è iterativo e gestito da un indice che cerca di ottimizzare lo splitting fino ad arrivare

all’assetto ottimale dei cluster. La figura evidenzia il processo di splitting:

5 Si fa riferimento ad un classificatore implementato all’Università di Roma “La Sapienza” denominatoClasslab [Baldelli 1999].6 Per una trattazione matematica della PCA si veda in appendice.


129

Fig.3.12: Descrizione dello splitting legato al parametro di scala

Grazie a questo procedimento è anche possibile proiettare l’intero spazio dei patterns (che è di

dimensione uguale al numero di campi in ingresso alla rete neurale) in uno sottospazio (con

dimensione inferiore) considerando per la classificazione solo le dimensioni che contengono

maggiore energia e trascurando le altre. Se la proiezione avviene in modo corretto, si riesce a

non perdere l’informazione e quindi la classificazione avviene come se la rete utilizzasse tutti i

campi (e quindi lavorasse in uno spazio di dimensione del campo in ingresso). Ridurre lo spazio

dei patterns ha il vantaggio che in fase di validazione la rete neurale deve eseguire i calcoli su

uno spazio più piccolo e quindi è più veloce. La figura seguente illustra il procedimento per un

caso bidimensionale:

Fig.3.13: Descrizione del processo di riduzione della dimensione di spazio (in sottospazio) senza perditadi informazione(proiezione sull’asse x) e con perdita (proiezione sull’asse y).

Vengono ora illustrate in dettaglio le particolarità di questo classificatore.

y

x


130

3.4.2 L’approccio di scala

La prima particolarità del classificatore è l’approccio di scala con il quale il classificatore

calcola i parametri da ottimizzare.

E’ stato mostrato in precedenza come viene ottenuta una ottimizzazione delle partizioni in base

al variare di un unico parametro (approccio parametrico al clustering). Naturalmente questo tipo

di procedura è sempre possibile quando l’algoritmo dipenda da un parametro al variare del quale

si ottengono differenti partizioni. Esiste però un particolare approccio parametrico, l’approccio

di scala (scale-based), in cui il parametro assume un significato particolare: questo rappresenta

il grado di risoluzione, ossia la scala, con cui è analizzata la struttura del data set.

Ad un livello di alta risoluzione, scala fine, ciascun pattern del data set è visto come un cluster,

mentre ad un livello di bassa risoluzione, scala grossolana, tutti i patterns possono essere visti

appartenenti ad un unico cluster. Nasce in maniera spontanea l’idea di paragonare una

situazione di alta risoluzione ad un osservatore che guarda da vicino gli oggetti di interesse

riuscendo a coglierne ogni minima differenza; al contrario, una situazione di bassa risoluzione

fa pensare ad una distanza, tra l’osservatore e gli oggetti di interesse, sufficientemente grande da

impedirne l’individuazione dei sottogruppi. Se in questo paragone si considera che

l’osservazione avviene tramite la vista, e quindi tramite l’occhio umano, la perdita del dettaglio

a grande distanza può pensarsi in analogia con l’effetto di filtraggio passa-basso che l’occhio

produce all’aumentare della distanza [Mandarini 1989].

Naturalmente l’approccio di scala è solo un particolare tipo di approccio parametrico:

riferendoci all’osservatore che guarda da diversa distanza una collezione di oggetti, il parametro

deve in qualche modo sempre essere legato alla distanza dagli oggetti dall’osservatore, o

perlomeno dal dettaglio con cui osserva loro.

In letteratura sembra che l’utilizzo di un nuovo indice, l’indice di stabilità di tipo Lifetime, sia il

più affermato per la scelta della partizione ottima. Ghosh e Chakravarthy affermano che

“nell’approccio al clustering in uno spazio di scala, i clusters sono determinati analizzando i dati

su un range di valori assunti dal parametro durante il processo di formazione dell’intera struttura

gerarchica, e la partizione stabile su un intervallo maggiore è quella da ritenere ottima”

[Chakravarthy 1996]. Anche Wong sostiene corretto ritenere particolarmente significativa la

struttura che rimane più stabile nella variazione della scala, considerando come criterio di

stabilità la permanenza di uno stesso numero di clusters [Wong 1993]. In questo classificatore

si utilizzeranno quindi questi indici di stabilità, magari con l’apporto di indici come Jaccard,

Rand Adjusted o il Lifetime Locale. Riprendendo il discorso sul clustering generalizzato, si può

dire che l’approccio di scala è sempre un’ottimizzazione che fa uso di indici relativi

classificabile nelle seguenti tre situazioni:


131

• approccio partizionale: si verifica in generale quando si usano algoritmi partizionali al

variare della scala e si ottengono diverse partizioni. L’ottimizzazione in questo caso è

senz’altro statica.

• approccio pseudo-gerarchico: è un caso particolare di approccio partizionale in cui l’insieme

delle partizioni ottenute costituisce una struttura gerarchica, nel senso che potrebbe

formalmente essere generata da un algoritmo gerarchico. Questo approccio non sfrutta a

priori i vantaggi dell’approccio gerarchico pur conservandone tutte le proprietà essenziali: è

quindi un’ottimizzazione, 'sorprendentemente' ed 'all’insaputa', dinamica.

• approccio gerarchico: è la solita scelta della partizione ottima dalla struttura di un algoritmo

gerarchico. Questa ottimizzazione è invece 'coscientemente' dinamica.

Le ragioni del nome “approccio di scala” nascono da tutta una serie di contributi esistenti in

letteratura, i quali costituiscono una vera e propria teoria su cosa si intenda per spazio di scala,

(scale space theory). In essa si fa riferimento alla rappresentazione di un qualsiasi segnale in

uno spazio di scala: sia ℜ→ℜNf : un qualsiasi segnale scalare reale, la rappresentazione

fS di f nello spazio di scala è data da:

)();();( xxx fkS f ∗= αα

dove ∗ denota l’operazione di convoluzione; il parametro di scala è +ℜ∈α con

fS f =→

);(lim0

αα

x ; e ℜ→ℜ×ℜ +Nk : è il kernel dello spazio di scala.

Il legame esistente col clustering risiede nel fatto che uno dei modi, certamente non l’unico e

probabilmente neanche il più corretto, di rappresentare la reale struttura dei dati può essere la

funzione densità di probabilità p(x) nello spazio dei patterns N-dimensionale Nℜ : i centri (o

centroidi) dei clusters potranno essere definiti come i punti a più alta densità in questo spazio ed

essere quindi in relazione con i picchi della funzione densità di probabilità p(x). Con l’approccio

di scala si cerca allora di dare una rappresentazione di scala pS della p(x) cercando di

determinare a diversi livelli risolutivi quali siano gli estremi dei clusters, e quindi i clusters

stessi, presenti nei dati.

Ghosh e Chakravarthy utilizzano in luogo del generico kernel );( αxk , un kernel gaussiano

definito da:

−=

απαα

2exp

)2(

1);(

T xxx

Ng (3.7)


132

Senza entrare nei dettagli su come venga utilizzato questo kernel nel compito di clustering,

Ghosh e Chakravarthy giungono ad un risultato che qui dimostreremo fortemente approssimato

evidenziando la necessità di utilizzare il concetto di scala al livello molto più astratto che al

livello di rappresentazione di scala della p(x).

Per chi volesse seguire la dimostrazione, essi dimostrano che i punti x per i quali risulta

statisticamente che 0][E =∆x , cioè i punti di convergenza per i quali il valore atteso delle loro

variazioni alla presentazione di nuovi patterns o alla iterazione della procedura di clustering è

nullo, sono gli estremi della rappresentazione di scala pS della p(x) mediante kernel gaussiano;

per cui tali punti identificano i centri di eventuali clusters presenti alla determinata scala α

utilizzata.

Generalizziamo innanzitutto questo risultato nel caso di kernel k(x) qualsiasi e poi, in base a

questo, discuteremo sui limiti di questo approccio. Definiamo il gradiente di pS come il vettore

[ ]

[ ]

[ ]

[ ]

∗∂

∂

∗∂∂

∗∂∂

=

∇

∇∇

=∗∇=∇

)();(

.....

)();(

)();(

);(

.....

);(

);(

)();();(2

1

2

1

xx

xx

xx

x

x

x

xxx

pkx

pkx

pkx

S

S

S

pkS

N

pN

p

p

p

α

α

α

α

αα

αα ;

in cui, tralasciando l’indicazione di α, risulta

∫∫∫ℜ∈ℜ∈ℜ∈

⋅−′=⋅

−

∂∂

=⋅−∂∂

=∇NNN

pkpkx

pkx

S iii

pi

ttt

dtttxdtttxdtttxx )()()()()()()(

Ni ≤≤1con ;

e quindi, con le dovute sostituzioni, sarà

NipkSNx

ipi ≤≤⋅−′=∇ ∫ℜ∈

1,)()()( dxxxxx .

Essendo ∫ℜ∈

⋅∆=∆Nx

p dxxxxx )()(][E , ove si è supposto )(xxx ∆=∆ dipendente dal generico

pattern x presentato al sistema, il punto x sarà di convergenza quando

⇔=∆ 0][E x Nixi ≤≤=∆ 1,0][E . Se si pone nelle regole di aggiornamento

dell’algoritmo

Nikx ii ≤≤−′∝∆ 1),()( xxx (3.8)


133

risulterà in definitiva

)(][E1),(][E xxx ppii SNiSx ∇∝∆⇔≤≤∇∝∆ ;

e quindi nei punti di convergenza

0)(0][E =∇⇔=∆ xx pS (c.v.d.). (3.9)

Si noti che quando si usa un kernel qualsiasi, anche gaussiano (3.7) come usato da Ghosh e

Chakravarthy, bisogna comunque definire in modo opportuno le regole di aggiornamento degli

x (in pratica il segno della costante di proporzionalità nella (3.8)) in modo da rendere instabili

dal punto di vista della convergenza i punti di minimo della pS , in quanto anche per essi vale la

(3.9). Inoltre non tutti i kernels sono adatti ad una rappresentazione di scala; senza entrare nei

dettagli, si può dimostrare che una funzione );( αxk è un kernel in uno spazio di scala se, per

ogni segnale f di ingresso, il numero di estremi nel segnale convoluto fS è minore o uguale a

quello degli estremi locali nel segnale originario f. Si può anche dimostrare che questo accade se

e solo se k possiede la Trasformata Bilatera di Laplace-Steltjes fattorizzabile in una forma

particolare che qui non sarà specificata (per dettagli si veda [Chakravarthy 1996]; tali funzioni

sono anche positive ed unimodali sia nel dominio spaziale che in quello della frequenza e la

gaussiana è una di queste. Non ci preoccuperemo di verificare ulteriormente queste ipotesi in

quanto dimostreremo che sarà necessario superare questo tipo di approccio legato alla

rappresentazione di scala dei segnali (p(x)) ed ai loro kernels.

Dimostriamo ora che i punti di convergenza x , con le proprietà sopra descritte, derivano dalla

soluzione di un sistema omogeneo di N equazioni, in generale non lineari, in N incognite (le

componenti del vettore x ) del tipo:

NikNset

ppi ≤≤=−′∑

=

1,0)(1

xx , (3.10)

essendo px uno degli N patterns che compongono il data set. Infatti, nel caso in cui le stime

data driven tendono alle stime probability driven ossia che N sia sufficientemente grande e

valga la legge dei grandi numeri, risulta essere

∑=

∆=∆Nset

ppii x

Nsetx

1

)(1

][E x

e quindi, dalla (3.8), è

∑=

−′∝∆Nset

ppii kx

1

)(][E xx ,


134

la quale porta alla (3.10) tramite la (3.9).

Un sistema non lineare di questo tipo può essere risolto in modo analitico ed approssimato

seguendo diverse strade:

Si possono utilizzare tecniche di soluzione iterativa di sistemi di equazioni non lineari mediante

approssimazione alle differenze finite del relativo Jacobiano.

Nel caso di Ghosh e Chakravarthy in cui )()( xx gk = , risulta

Nikxxk iii ≤≤−⋅−∝−′ 1),()()( xxxx

per cui la (4.16) porta ad una soluzione del tipo

Nik

kx

xkxxNset

pp

Nset

pppi

i

Nset

ppipi ≤≤

−

−⋅=⇒=−⋅−

∑

∑∑

=

=

=

1,)(

)(

0)()(

1

1

1 xx

xx

xx

che può essere utilizzata in modo iterativo se a secondo membro si utilizza )(tx calcolato

all’iterazione t-esima per calcolare i nuovi )1( +txi dell’iterazione t+1-esima a primo membro.

Si vedrà che una soluzione di questo tipo è simile all’algoritmo EM, spiegato più avanti ed

utilizzato per il classificatore in questione, per modellare le densità di probabilità in campo

statistico.

In entrambi gli esempi proposti i problemi da affrontare sono sostanzialmente due: il primo è

che la soluzione viene a dipendere in modo cruciale dal punto iniziale )0(x scelto per iniziare

le iterazioni; il secondo è che, per una certa scala α fissata nel kernel, si può trovare uno ed un

solo cluster alla volta identificato da x . Bisognerebbe allora scegliere le condizioni iniziali in

modo opportuno da far convergere le soluzioni volta per volta nei diversi massimi relativi della

pS , e questa è una cosa praticamente impossibile senza una quasi completa conoscenza a priori

delle caratteristiche del problema e/o del data set in esame (nella fattispecie la p(x)).

Si può invece cercare di risolvere il problema in modo diverso come fanno Ghosh e

Chakravarthy, cercando cioè di definire una certa struttura del sistema di clustering (le reti

neurali RBF), ed un algoritmo di addestramento per essa, in modo da garantire con un approccio

di scala gerarchico la convergenza del sistema durante la ricerca dei punti x aventi 0][E =∆x .

Il problema è che il loro algoritmo non mostra alcuna proprietà analitica che permetta di

garantire tale convergenza: esso si basa su un discorso euristico che alla prova dei fatti, sui test

effettuati, non fornisce prestazioni superiori, o quantomeno analoghe, né a quelle degli algoritmi

di clustering già presenti in letteratura, né a quelle degli algoritmi sviluppati presso il

dipartimento di informatica e sistemistica dell’università “La Sapienza”. Tuttavia questo non


135

deve sorprendere in quanto si è visto in precedenza che anche una soluzione analitica del

problema risulta essere abbastanza complicata e piena di limitazioni.

Tale analisi critica ha costituito il punto di partenza di tutto questo lavoro ed ha portato alla

conclusione che i vantaggi dell’approccio scala al clustering devono essere sfruttati senza

limitarsi alle pur affascinanti teorie statistiche della rappresentazione di scala delle densità di

probabilità del data set, ma utilizzando il concetto di scala come livello di risoluzione

nell’analisi strutturale dei dati.

3.4.3 L’algoritmo HMPPCA (Hierarchical Mixture of Probabilistic Principal

Component Analysis)

Come già detto esistono numerosi algoritmi di clustering, tutti dalle prestazioni soddisfacenti,

tuttavia un’attenta analisi sperimentale ha messo in evidenza la possibilità di sfruttare le idee

guida di questi algoritmi per migliorarne ulteriormente le prestazioni, cercando di superare i

limiti che pur sempre permangono in essi, in particolare quello dell’ordinamento.

Il contesto in cui è progettato l’algoritmo di misture (mixtures) gerarchiche di PCA

probabilistica (HMPPCA) è, in tal senso, leggermente differente: l’algoritmo utilizzato da

questo classificatore usa un modello probabilistico piuttosto che fuzzy, pur senza escludere le

caratteristiche di flessibilità e robustezza del clustering non esclusivo rispetto a quello crisp.

Si fa utilizzo dell’approccio di scala gerarchico e costruttivo illustrato precedentemente. In

effetti si vedrà che il concetto di gerarchia è usato in modo, per così dire, ibrido: se tale è infatti

la costruzione dei modelli, ciascuno dei quali identificherà un cluster, nel passaggio da

un’iterazione alla successiva si segue un approccio partizionale che ottimizza un’opportuna

funzione costo, la funzione log-likelihood7, al fine di definire i parametri di questi modelli. Si

tratta di un approccio di scala partizionale ma la costruzione gerarchica dei modelli ed il modo

in cui è variato il parametro di scala lo rendono sicuramente differente dalle ottimizzazioni

tipiche di un algoritmo partizionale. A differenza delle varie partizioni ottenute da un generico

algoritmo al variare del suo parametro (come per esempio è il caso per il classificatore illustrato

nel paragrafo precedente e basato sull’algoritmo Min-Max), ora esiste un legame ben definito

tra un’iterazione e la successiva. L’estremo grado di gerarchizzazione delle partizioni ottenute

può far parlare tranquillamente di approccio pseudo gerarchico in cui l’ottimizzazione dinamica

del clustering è ora operata in modo esplicito e consapevole.

7 La funzione log-likelihood verrà spiegata nel paragrafo successivo.


136

Inoltre è anche fortemente limitata la propagazione di eventuali errori che possono presentarsi

ad una certa iterazione, per esempio a causa dell’ordinamento locale dei patterns, in cui alcuni

patterns che dovrebbero lecitamente appartenere al cluster A sono invece contenuti nel cluster

B. Una rigida struttura gerarchica dell’algoritmo vincolerà questi patterns ad appartenere

necessariamente ai figli di B, per cui non c’è nessuna possibilità che essi vengano

successivamente assegnati ad A; il cluster naturale risulterà dunque scomposto in modo

anomalo per la scala corrente e questo porterà gli indici di ottimizzazione ad un risultato errato.

Se accadesse un errore analogo nell’HMPPCA, questo influirebbe solo nell’inizializzazione per

l’iterazione successiva, la convergenza dell’algoritmo verso il massimo della funzione costo

potrebbe comunque portare ad assegnare di nuovo questi patterns ad A.

Si tornerà in seguito su questo esempio e su come l’HMPPCA si comporti meglio di altri

algoritmi.

L’altra caratteristica essenziale di questo algoritmo è la possibilità di effettuare l’analisi locale

dei dati mediante la PCA. La peculiarità ora introdotta consiste nel generalizzare la dimensione

del sottospazio definito dalle direzioni principali:

se d è la dimensione dello spazio dei patterns, è possibile considerare il sottospazio a

dimensione dq ≤ costituito dalle prime q componenti principali di ciascun cluster. In pratica,

oltre all’analisi locale della struttura dei dati, ora si può anche cercare di effettuare una riduzione

o compressione locale eliminando la ridondanza degli stessi.

3.4.4 Clustering mediante decomposizione di mixtures

L’approccio classico utilizzato nel clustering probabilistico è quello di modellare i clusters

naturali del data set attraverso una mixture di sorgenti aleatorie dei dati: il data o training set

X = {x1, x2, … , xN} a disposizione sarà costituito da un insieme di N patterns, ciascuno dei

quali è una variabile aleatoria (random value, RV) estratta da una ed una sola delle K sorgenti

che costituiscono la mixture. Ciascuna i-esima sorgente, con Ki ,...,1= , rappresenta un cluster

il cui modello è descritto dalla relativa densità di probabilità );|( iip θθx , dove iθθ è il vettore

di parametri incogniti che la definisce, e dalla probabilità a priori iπ del cluster i, dove 0≥iπ

e 11

=∑=

K

iiπ . Il modello complessivo della mixture è la densità di probabilità costituita dalla

somma, pesata dalle iπ , di tutte queste componenti:


137

∑=

=K

iii ipp

1

);|();( θθθθ xx π (3.11)

Il problema di clustering sarebbe quindi quello di assegnare in modo netto (crisp) ogni pattern al

suo corretto cluster, dato che ciascuno di essi è generato da uno ed un solo cluster. Se, attraverso

i patterns a disposizione, è possibile stimare l’insieme complessivo

θ = {θ1,θ2,…, θK ; π1, π2,…, πK}

dei parametri del modello, l’assegnazione può essere fatta in base alle densità di probabilità che

diverrebbero note.

Tale problema di clustering è identico a quello di apprendimento non supervisionato: infatti,

usando la regola di Bayes [Papoulis 1991], si può ottenere la probabilità a posteriori niR che,

dato un pattern nx , esso sia generato dalla sorgente aleatoria del cluster i:

)(

)|()|(

n

ninni p

ipiR

xx

xππ ==

(3.12)

ed è evidente che si può assegnare il pattern nx al cluster h per cui questa probabilità a

posteriori risulti massima, ossia tale che

niKi

n Rh,...,1

max)|(=

=xπ (3.13)

In questo modo è perfettamente formalizzato un problema di crisp clustering mediante

l’approccio statistico di stima dei parametri θ.

Tuttavia, se si considera la matrice R={Rni}∈MN,K )(ℜ delle probabilità a posteriori di un

insieme X = {x1, x2, … , xN} di RV indipendenti e identicamente distribuite (i.i.d.) estratte

dalla mixture generate attraverso la formula (3.11), si osserva che R appartiene al sottospazio

delle partizioni probabilistiche contenuto nello spazio delle partizioni fuzzy. In questo modo si è

formalizzato un problema di clustering probabilistico in cui ad ogni pattern è associato un valore

di appartenenza (label) omonima la cui somma degli elementi è pari ad 1; il procedimento di

decisione espresso nella(3.13) ne diventa quindi la fase di deprobabilizzazione. Il clustering

risulta formalmente non esclusivo pur appartenendo i patterns in modo crisp ai vari clusters. In

effetti, dal punto di vista formale, le analogie col clustering fuzzy sono evidenti: pur essendo

differente la logica informativa contenuta nelle labels, le probabilità giocano lo stesso ruolo

delle funzioni di appartenenza nel fuzzy clustering. Guardando alla (3.11) si può dire che,


138

rispetto al caso fuzzy, le )|( ip x sono equivalenti alle )(xiµ , mentre le iπ sono in

quest’ultimo poste tutte pari ad 1. In tal caso si può dire che si agisce in totale assenza di

conoscenze a priori e tutti i clusters, seppur identificati in maniera fuzzy, sono considerati

equiprobabili.

Esistono diversi schemi di soluzione che permettono di stimare i parametri

θ = {θ1,θ2,…, θK ; π1, π2,…, πK} al fine di risolvere in modo univoco questo tipo di problemi di

clustering. Fra i tanti ne utilizzeremo uno dei più affermati in letteratura: il Metodo della

Massima Verosimiglianza (Maximum Likelihood Estimation, MLE), proposto da Duda ed Hart

[Duda 1973]. Esso si basa sulla massimizzazione della funzione di massima verosimiglianza

(log-likelihood):

( ) [ ] ∑ ∑∑∏= ===

==

==

N

n

K

iini

N

nn

N

nn ipppXpL

1 111

);|(ln);(ln);(ln);(ln)( θθθθθθθθθθ xxx π (3.14)

Più esplicitamente, lo spazio dei patterns è caratterizzato da una ben precisa ed incognita

mixture di cui bisogna determinare i parametri fissi ed incogniti θ attraverso l’osservazione di

alcune sue determinazioni nel data set i.i.d. X = {x1, x2, … , xN}. Si stabilisce che i parametri

reali MLθθ siano quelli per cui la mixture da essi determinata abbia massima probabilità di

generare X. Quale che sia il procedimento utilizzato, si tratta sempre di costruire uno stimatore

)(⋅g che, date le osservazioni in X, fornisca una stima )(~

XgML =θθ dei veri parametri MLθθ .

Data la natura aleatoria dei dati, il risultato dello stimatore è una RV che dipende dalla

determinazione di X che si ha a disposizione; i parametri MLθθ e la mixture sono invece

deterministici anche se incogniti. Definire la procedura di stima significa fissare la struttura

di )(⋅g dopodiché, al variare di X, si otterranno le diverse stime )()(~

XgXML =θθ dei parametri

reali MLθθ . Determinare il miglior stimatore di MLθθ , e dimostrare che esso esiste, non è un

problema semplice; si vuole solo menzionare il fatto che, nel caso sia uno stimatore non

polarizzato per cui [ ] MLMLML dXXpXgXE θθθθθθ == ∫ ),()()(~

, la sua covarianza non sarà

nulla ma si può dimostrare che possiede un limite inferiore, il limite di Rao-Cramér, che quindi

determina il migliore stimatore possibile di MLθθ [Papoulis 1991].

Nel seguito utilizzeremo come modello dell’i-esima sorgente aleatoria, ossia della densità di

probabilità dell’i-esimo cluster, la distribuzione gaussiana

−−−= − )()(

2

1exp

)2(

1);|( 1

iiT

i

idiip µµµµθθ xCx

Cx

π


139

dove iµµ è il vettore del suo valor medio e iC la matrice di covarianza. Il vettore di parametri di

ciascun cluster sarà dunque del tipo ),,( iiii Cµµθθ π= in cui sono state comprese, senza

perdita di generalità, anche le iπ . In questo particolare caso è possibile definire delle condizioni

necessarie per la MLE di θ nella (3.11) che conducono a due differenti casi a seconda che si

tratti di un problema di classificazione o di clustering.

Nel primo caso è nota la matrice R delle probabilità a posteriori, cioè sono note le labels, quindi

le equazioni per la MLE di ogni iθθ sono disaccoppiate fra le diverse classi e i diversi vettori di

parametri; ne segue che è possibile risolverle in maniera esplicita e non iterativa. Basterà

utilizzare il training set X per ogni classe, sostituirlo nelle equazioni, calcolare i parametri del

modello di ciascuna classe ed usare le funzioni risultanti come stimatori del secondo membro

della (3.12).

Nel caso di interesse, riguardante il clustering, la matrice R è ignota e quindi le equazioni per la

MLE di ogni iθθ sono accoppiate fra i diversi clusters e i diversi vettori di parametri. Un modo

per determinare le condizioni necessarie per trovare i massimi della log-likelihood è quello di

utilizzare la tecnica dei Moltiplicatori. In questo modo, anche utilizzando semplici modelli

gaussiani, si perviene ad un insieme di equazioni non lineari fortemente accoppiate fra loro nelle

incognite R e θ. Questi sistemi di equazioni trascendentali presentano diverse soluzioni, la cui

ambiguità è dovuta alla mancanza di conoscenza su quale componente della mixture abbia

generato lo specifico pattern e, inoltre, su quale vettore di parametri iθθ sia da esso influenzato.

Bisognerà allora utilizzare metodi di ottimizzazione iterativi per trovare delle soluzioni

approssimate alle condizioni necessarie; si incontreranno i soliti problemi di inizializzazione,

minimi locali, convergenza numerica, ecc., tuttavia è di solito possibile ottenere i risultati

necessari per stimare il secondo membro della (3.12).

A questo scopo, nel seguito sarà utilizzato l’algoritmo EM (Expectation Maximization) proposto

da Dempster [Dempster]. Esso consiste di due passi essenziali i cui dettagli saranno chiariti

quando si introdurranno i modelli specifici utilizzati, in generale essi sono:

• Passo-E: è calcolato il valore di ‘aspettazione’ della log-likelihood dell’intero data set,

condizionato ai dati osservati X ed ai parametri stimati θθ~

. Questo porta alla nuova stima

delle probabilità a priori iπ~ .

• Passo-M: sono calcolate le nuove stime dei parametri della mixture, in particolare il valor

medio e la covarianza delle gaussiane.


140

La convergenza dell’algoritmo è garantita dall’incremento monotonico della log-likelihood fino

ad un massimo locale che non è garantito essere anche globale. Si noti la totale indipendenza

dell’algoritmo, e quindi dei risultati, dall’ordine di presentazione dei patterns. Si ribadisce

ancora una volta che la sequenza dei suoi passi costituisce una procedura, approssimata ed

iterativa, che definisce la struttura dello stimatore )(⋅g .

Una volta definite le caratteristiche essenziali del clustering probabilistico, nel prossimo

paragrafo si passerà ad inquadrare, all’interno di questo contesto, le menzionate tecniche di

analisi locale tramite PCA.

3.4.5 Mixtures di PCA probalistiche

Sebbene la PCA sia una delle tecniche più affermate nell’analisi ed il processamento dei dati,

essa possiede un limite fatale che è dovuto alla sua linearità globale. Cercando di catturare la

complessità dei dati utilizzando una combinazione di PCA locali ci si scontra con il fatto che la

PCA convenzionale non corrisponde a delle densità di probabilità, quindi non esiste un modo

unico per combinare i vari modelli di PCA locali. Un simile utilizzo rientra in tutta quella classe

di esempi in cui la costruzione di mixtures di PCA avviene mediante generalizzazioni ad hoc,

limitate a delle specifiche applicazioni. In questi casi il problema fondamentale è dovuto

all’assenza di una funzione costo differenziabile in generale, la quale può essere minimizzata, o

massimizzata, per determinare i parametri del modello. Il problema è di solito decomposto in

due distinte procedure: la partizione dello spazio dei dati, seguito dalla stima del sottospazio

principale all’interno di ogni componente, cioè i clusters. Con la definizione standard di PCA, la

metodologia per combinare le due procedure rimane inevitabilmente arbitraria, soprattutto non è

unico il criterio con cui effettuare la partizione dei dati.

Il punto di svolta è però rappresentato dai risultati ottenuti da Bishop e Tipping [Bishop &

Tipping 1997] che derivano un modello probabilistico per la PCA, da cui la mixture di PCA

locali segue come naturale estensione. In questo caso, tutti i parametri del modello possono

essere stimati attraverso la massimizzazione di una singola funzione di log-likelihood con le

modalità viste al paragrafo precedente. Non solo questo conduce ad un esplicito ed unico

algoritmo, ma si possono anche applicare le tecniche di clustering probabilistico che sono di

interesse in questo lavoro.

Il punto di partenza è l’utilizzo dei modelli a variabile (aleatoria) latente. Essi cercano di mettere

in relazione un insieme di vettori osservati {xn} d-dimensionali, con un corrispondente insieme

di variabili latenti {tn} q-dimensionali:


141

εε+= );( Wtyx (3.15)

dove y è funzione della variabile latente t con dei parametri W, mentre ε è un processo

rappresentante rumore additivo indipendente da x. In generale dq < in modo che la variabile

latente offra una descrizione più parsimoniosa dei dati. Definendo a priori una distribuzione su x

e su ε, senza limitare la generalità del problema, la (3.15) induce una corrispondente

distribuzione nello spazio dei dati, quindi i parametri W possono essere stimati mediante

tecniche MLE.

Il classico esempio di modello a variabile latente è la Factor Analysis (FA) in cui le variabili

latenti sono anche dette fattori e la y è una funzione lineare:

εεµµ ++⋅= tWx (3.16)

dove t ha distribuzione gaussiana a valor medio nullo e covarianza I (matrice identità); ε ha

distribuzione gaussiana a valor medio nullo e covarianza diagonale Ψ; i qxd parametri W

contengono i fattori di carico; ed infine µ permette al modello di avere media non nulla. Con

queste posizioni, vista l’indipendenza di ε da t, anche x avrà un modello gaussiano con valor

medio µ e covarianza ΨΨ+= TWWC . Si noti che il modello, cioè la C, è invariante rispetto a

post-moltiplicazioni di W mediante una matrice ortogonale Q che rappresenta una rotazione del

sistema di coordinate in x.

Con le solite notazioni, su un data set di N patterns, si definiscono rispettivamente:

∑=

=N

nnN 1

1xµµ ∑

=

−−=N

n

TnnN 1

))((1

µµµµ xxS (3.17)

le stime del valor medio e della matrice di covarianza dell’insieme di dati. Risulta evidente che

quando questo µ è utilizzato nella (3.16) e la determinazione dei parametri porta a SC = , il

modello di covarianza si dirà esatto, altrimenti si dirà approssimato. In generale, a causa

dell’uso di un rumore con modello di covarianza diagonale Ψ, le colonne dei fattori di carico W

differiranno dagli assi principali definiti nella PCA, anche se si utilizzasse una rotazione

arbitraria Q; quindi non è immediato trovare un legame tra FA e PCA. Si può tuttavia

dimostrare che, se per il rumore si usa un modello isotropico I2σ=ΨΨ ed il modello è esatto, i

parametri W possono essere ricavati in modo diretto, cioè senza procedimenti iterativi,

attraverso decomposizione in valori singolari (abbreviazione: SVD) della S, per cui essi

rappresentano la PCA del data set. Nel caso di modello approssimato, ciò che avviene sempre

nella pratica, e con l’ipotesi di rumore isotropico, si raggiunge il risultato di Tipping e Bishop


142

per cui, utilizzando il metodo iterativo basato sulla MLE, le colonne di W sono i primi q

autovettori principali di S scalati ed arbitrariamente ruotati.

La conseguenza fondamentale di tutto ciò è che si può sempre riformulare la teoria della PCA

all’interno della FA e del contesto probabilistico, nella fattispecie essa prende il nome di PCA

Probabilistica (PPCA Probabilistic Principal Component Analysis). Con le ipotesi fatte di

rumore isotropico e di distribuzione gaussiana di t del tipo

−= xxt T

qp

2

1exp

)2(

1)(

π

la (5.6) implica evidentemente che x abbia nel suo spazio una distribuzione, condizionata al dato

valore di t, del tipo

−−−= 2

22 2

1exp

)2(

1)|( µµWxttx

σπσ dp

La distribuzione marginale di x, è pura questione di calcoli, avrà la forma:

−−−== −∫ )()(

2

1exp

)2(

1)()|()( 1 µµµµ xCx

Cdtttxx T

dppp

π(3.18)

con modello di covarianza

TWWIC += 2σ (3.19)

Ricapitolando, si vuole effettuare il clustering dei dati mediante decomposizione di una mixture.

Il modello della mixture è definito dalla (3.11), mentre la (3.12) permette di assegnare le

etichette probabilistiche ai patterns dove le densità di probabilità dei singoli clusters sono date

dalla (3.18).

Il problema diventa quello di stimare il vettore di parametri θ = {θ1,θ2,…, θK ; π1, π2,…, πK},

con ),,( 2iiii σWµµθθ = , mediante tecnica MLE e relativo algoritmo EM. In questo modo

ciascun cluster è rappresentato da un modello di PPCA che ne effettua l’analisi PCA locale con

un’ulteriore possibile riduzione locale della dimensione dei dati se dq < .


143

0,1

1

1,9

2,8

3,7

4,6

0,3 0,

6 0,9 1,

2 1,5 1,

8 2,1 2,

4 2,7

3 3,3 3,

6 3,9 4,

2 4,5 4,

8

0

0,2

0,4

0,6

0,8

1

x1

x2

0,8-1

0,6-0,8

0,4-0,6

0,2-0,4

0-0,2

Fig.3.14: Funzione di appartenenza basata su una guassiana

Tale algoritmo EM è stato ricavato nel loro lavoro da Tipping e Bishop [Tipping 1997] Le

condizioni necessarie per la MLE assumono ora una forma particolare. Al variare di W nel

singolo modello PPCA, gli unici punti stazionari non nulli 0≠MLW della log-likelihood tali

che 0=∂∂WL

devono avere una struttura del tipo:

( ) QIUW2/12σ−= qqML ΛΛ (3.20)

in cui le q colonne della matrice qxd qU sono q autovettori della S del modello; i

corrispondenti q autovalori λ sono nella matrice diagonale qxq qΛΛ ; e Q è la solita matrice

ortogonale di rotazione qxq arbitraria. Si dimostra anche che se si usano i primi q autovettori

principali si ottiene il massimo globale della log-likelihood, avendo posto

∑+=−

=d

qjjqd 1

2 1 λσ (3.21)

essendo chiaro che alla potenza del rumore si dà quindi il significato di varianza persa nella

proiezione, mediata sul numero di dimensioni scartate. Qualsiasi altra combinazione di

ΛΛ

0=W è un punto di minimo della stessa. Si fa notare che la matrice arbitraria ed

ortogonale Q, come già accennato in precedenza, non influisce sulla covarianza del modello in

quanto ora

( ) ( ) ( ) Tqqq

Tqq

Tqq

TMLML UIUUIQQIUWW 22/122/12 σσσ −=−−= ΛΛΛΛΛΛ (3.19’)

In effetti si nota anche che ( ) IQIQWW ≠−= 2σqT

MLTML ΛΛ , per cui MLW non è in generale

ortogonale e non è possibile estrarre con essa il vero sottospazio principale. Tuttavia vedremo

che, con l’uso del modello PPCA, la proiezione di x in t e la successiva ricostruzione di t in x̂

portano ad una relazione tra x e x̂ , cioè all’errore di ricostruzione, che non dipende da Q,

quindi è possibile porla pari ad I senza perdere di generalità.

Con ciò, tralasciando la fase di inizializzazione che sarà vista nello specifico algoritmo

HMPPCA, l’algoritmo EM assume la seguente particolare struttura che non necessita di ulteriori

commenti:

Passo-E: data la stima al passo precedente delle probabilità a priori iπ e dei parametri

),,( 2iiii σWµµθθ = , per ogni modello di cluster i, con Ki ,...,1= , sono calcolati:

il valore di ‘aspettazione’ della log-likelihood dell’intero data set tramite la (3.14), condizionato

dai dati osservati X ed ai parametri stimati;

le probabilità a posteriori niR tramite la (3.12);

Inoltre, se la log-likelihood si discosta da quella del passo precedente di un valore al di sotto di

una soglia prefissata, l’algoritmo è giudicato aver converso: la partizione del clustering è

costituita dalla matrice R = {Rni}, ed il modello di clustering è costituito dalla mixture (3.11)

con i parametri iπ e ),,( 2iiii σWµµθθ = noti. Altrimenti si procede calcolando le nuove

probabilità a priori

∑=

=N

nnii R

N 1

1~π

Passo-M: sono calcolate le nuove stime dei parametri della mixture per ogni cluster, in

particolare:

∑

∑

=

==N

nni

N

nnin

i

R

R

1

1~x

µµ


145

mentre iW~

e 2~iσ si ottengono tramite le (3.20) e (3.21) dopo decomposizione in autovettori ed

autovalori della matrice di covarianza locale pesata

Tin

N

ninni

ii R

N)~()~(~

1

1

µµµµ −−= ∑=

xxSπ

(3.22)

La figura 3.15 mostra il tipico andamento monotonico della log-likelihood nella successione di

questi passi EM quando sono utilizzati in ognuna delle iterazioni dell’algoritmo gerarchico

HMPPCA.

Figura 3.15: Convergenza della log-likelihood nella successione di 18 passi EM

3.4.6 Mixture gerarchiche di PPCA

C’è un’importante questione che ancora non è stata affrontata: come determinare il corretto

numero k di clusters nel training set? Infatti, l’algoritmo EM appena proposto è un tipico

esempio di k-clustering partizionale in cui k è noto a priori. In letteratura sono presenti degli

approcci analitici al problema che sono in stretto legame con quelli utilizzati per le reti neurali:


146

essi studiano la capacità di generalizzazione della rete ottimizzando una funzione costo secondo

il principio del Rasoio di Occam.

Avendo visto l’approccio di scala costruttivo e gerarchico, l’algoritmo per clusterizzare che

utilizza queste proprietà prende il nome dal modello di clustering che genera: una mixture

gerarchica di PPCA o, con l’acronimo inglese, HMPPCA. I problemi da risolvere sono

essenzialmente tre: primo, bisogna definire come inglobare nell’algoritmo il meccanismo di

esplorazione di scala; secondo, bisogna trovare la maniera di generare in modo gerarchico i

clusters di una successiva iterazione a partire da quella presente; terzo, è necessario stabilire la

procedura di inizializzazione dell’algoritmo EM utilizzato in ogni iterazione dell’algoritmo

gerarchico.

Riguardo al primo problema, vedremo che si utilizza il concetto primitivo di scala già introdotto

precedentemente: al suo variare i dati saranno semplicemente scalati, e quindi compressi o

dilatati, simulando l’osservazione a differenti distanze e con dettagli maggiori o minori. La

soluzione del secondo problema, sulla generazione gerarchica dei clusters, sarà chiarita durante

la definizione dell’algoritmo: essa si basa su una tecnica euristica legata alla PCA che riteniamo

abbastanza plausibile e che comunque ha fornito risultati ampiamente soddisfacenti in fase di

test dell’algoritmo. L’ultimo problema si vedrà limitato solo all’inizializzazione dell’unico

cluster della prima iterazione; infatti, nelle successive, saranno sfruttati come inizializzazione i

modelli della mixture stimati alle iterazioni precedenti, più quelli che derivano dalle eventuali

scissioni di clusters. In questo sta il legame già enunciato che rende i risultati dei singoli

algoritmi partizionali EM, utilizzati nelle iterazioni dell’HMPPCA, estremamente correlati fra

loro, dando un carattere complessivamente gerarchico all’algoritmo. Si vuole comunque

sottolineare che l’influenza delle inizializzazioni è più marcata sul costo computazionale che sui

risultati finali. Infatti l’algoritmo EM dovrebbe garantire la convergenza iterativa verso il

massimo globale della log-likelihood indipendentemente dalle condizioni iniziali, anche se

problemi di precisione numerica e di approssimazione nei modelli possono portare a

convergenze in massimi locali. Il vantaggio risiede comunque nel fatto che il numero di passi

effettuati da ogni EM si riduce drasticamente, anche ad un solo aggiornamento, laddove sia

presente un’inizializzazione molto vicina al modello finale: si pensi ad un cluster che non è

scisso da un’iterazione all’altra e che, verosimilmente, non subirà grandi alterazioni nel suo

modello.

La struttura di base dell’algoritmo è la seguente:

• Inizializzazione: si pone la scala 1=α e si considera un unico cluster, 1=K , sull’intero

training set X = {x1, x2, … , xN}. Mediante PCA convenzionale si stimano i parametri


147

),,( 21111 σWµµθθ = e si pone 11 =π . Si determina la soglia di scissione ξ nel modo che

sarà definito in seguito.

• Algoritmo EM: si pone αα =0 e, dati K clusters presenti con i parametri iπ e

),,( 2iiii σWµµθθ = ed Ki ,...,1= , si effettua l’algoritmo EM fino alla sua convergenza.

Si ottiene quindi la stima ottima dei suddetti parametri e la partizione R mediante le

probabilità a posteriori (3.12).

• Determinazione dei fattori di scissione: si effettua, mediante la (3.13), un processo di

deprobabilizzazione e si determina per ogni cluster Ki ,...,1= , con il procedimento

analizzato in seguito, il fattore di scissione iδ dipendente dai patterns di X assegnati al

cluster i.

• Determinazione della scala successiva: per ogni cluster Ki ,...,1= , questo subirà scissione

se si verifica che

ξαδ

>2i (3.25)

Se esiste almeno un cluster con queste caratteristiche allora si va al passo 4; altrimenti:

♦ se 0>α , si decrementa α di un valore 0),( >= Kαεε e la risoluzione

dell’approccio di scala, successivamente si torna all’inizio del passo 3;

♦ se 0=α , si va al passo 4.

• Test di fine algoritmo: se K è superiore ad un numero limite di clusters fissato a priori

oppure 0=α , si va al passo 6 con i risultati del passo 1 validi da 0α ad α; altrimenti si va

al passo 5.

• Procedura di scissione: per ogni cluster Ki ,...,1= : se al passo 3 si è deciso di scinderlo, si

effettua tale procedura con le modalità viste successivamente, si pone 1+= KK e tale

cluster scinderà nell’i-esimo e nel (K+1)-esimo. Tramite queste procedure, si determinano

anche i parametri iπ , ),,( 2iiii σWµµθθ = , 1+Kπ , ),,( 2

1111 ++++ = KKKK σWµµθθ da usare

come inizializzazione nel successivo passo 1; se il cluster non scinde, i parametri calcolati al

passo 1 sono usati come inizializzazione nella successiva iterazione. Si torna quindi al passo

1, decrementando α della risoluzione 0),( >= Kαεε .

• Ottimizzazione: si calcola la partizione ottima dalla gerarchia


148

Prima di descrivere le fasi che ancora mancano, si vogliono notare due caratteristiche:

innanzitutto il costo computazionale principale, legato dagli algoritmi EM, è sostenuto soltanto

dopo le eventuali procedure di scissione e non per ogni valore della scala α. Infatti, pur

effettuando una scansione lineare della stessa, se le scissioni non avvengono i modelli sono

inalterati e non c’è bisogno di rifare le stime; inoltre, è presente anche qui un possibile discorso

di perturbazione quando si decide di effettuare una scansione non lineare, rendendo ε variabile

con il numero di clusters e con la scala corrente. Ad esempio, si possono effettuare decrementi

maggiori per una scala grossolana vicino ad uno, e decrementi sempre più piccoli quando la

scala si raffina vicino allo zero.

La soglia di scissione ξ può essere impostata in modo esplicito e manuale a seconda del tipo di

problema in esame; è stata stabilita una formula euristica che sarà sempre utilizzata in fase di

analisi dell’HMPPCA in modo da renderla indipendente dai dati in esame. Si è posto ξδ=

d1 ,

dove d è la dimensione dello spazio dei patterns e 1δ è il fattore di scissione del cluster definito

in fase di inizializzazione.

Questo algoritmo, pur essendo probabilistico e non esclusivo, utilizza al suo interno dei processi

decisionali che si basano su logica crisp. Per determinare il fattore di scissione iδ di ogni

cluster, così come per effettuare la procedura di scissione, si deve infatti determinare con la

(3.13) l’insieme di patterns iA che appartengono al cluster i-esimo più che ad ogni altro cluster

presente. Definito questo insieme, si simula la procedura di scissione di iA presentata nel

seguito e si pone iδ pari alla distanza euclidea tra i centri (valori medi nella (3.18)) dei due

clusters generati. A questo punto è chiaro come agisce il concetto di scala: al suo diminuire, e

quindi all’avvicinarsi dell’osservatore ai dati, le distanze fra i patterns aumenteranno; se si

scalano i patterns per un fattore α, le distanze euclidee quadratiche saranno scalate per un

fattore 2

1

α come nella (3.25). Più un cluster è compatto, più il suo fattore di scissione sarà

piccolo, più la scala dovrà essere piccola affinché sia soddisfatta la (3.25), e quindi maggiore

sarà il tempo di vita (Lifetime locale) del cluster stesso.

Manca soltanto la definizione della procedura di scissione che è alla base di tutto l’algoritmo.

Ebbene, per il cluster i-esimo che deve essere scisso, continua ad essere utilizzata la PCA e

l’insieme iA prima definito. L’idea è quella di proiettare i patterns di iA , ed il loro valor


149

medio, sulla relativa direzione principale in modo da partizionare iA in due sottoinsiemi

disgiunti LiA e R

iA tali che Li

Rii AAA ∪= e ∅=∩ L

iRi AA . Gli insiemi L

iA e RiA sono

ottenuti discriminando i patterns che in questa proiezione cadono, rispettivamente, a sinistra o a

destra del valor medio. Dopodiché, si effettua la PCA convenzionale sui due insiemi e si

stimano i rispettivi parametri, ),,( 2iiii σWµµθθ = e ),,( 2

1111 ++++ = KKKK σWµµθθ , come

definito al passo 5 dell’algoritmo. Le nuove iπ e 1+Kπ sono invece definite così:

oldi

i

Li

i NN

ππ = e oldi

i

Ri

K N

Nππ =+1

dove oldiπ è la probabilità a priori del cluster che sta scindendo, iN è la cardinalità di iA ,

mentre LiN ed R

iN sono le cardinalità di LiA e R

iA rispettivamente.

3.4.7 Compressione PCA e PPCA dei Dati

L’obiettivo della compressione dei dati è quello di rappresentare gli stessi con una quantità di

informazione minore e con una perdita minima rispetto all’informazione originaria. Si supponga

di voler effettuare una trasmissione con dati compressi, vediamo due esempi tipici.

Nel caso della Quantizzazione Vettoriale (vectorial quantifier, VQ), ad ogni pattern nx è

associata un’etichetta numerica che viene trasmessa al posto di nx . Ciascuna etichetta

permetterà di ricostruire nx in nx̂ grazie ad una codeword del codebook, che deve essere

trasmesso prima dei dati, avente la stessa dimensione di nx .

Un altro possibile modo per comprimere nx è quello di effettuarne una proiezione lineare

nn Qxt = in cui nt avrà una dimensione dq < di quella di nx e può essere trasmesso al suo

posto assieme all’etichetta che stabilisce quale, fra le possibili matrici di proiezione, è stata

utilizzata. Anche in questo caso le matrici di proiezione devono essere trasmesse off-line o,

comunque, prima dei dati. In fase di ricostruzione, si ottiene il vettore ricostruito nn Stx =ˆ , con

S matrice di dimensioni opportune. A questo punto nasce il problema della scelta ottima,

rispetto ad un determinato criterio, delle matrici Q e S. Usando il criterio dei Minimi Quadrati

(Least Squares, LS) esse devono minimizzare l’errore quadratico


150

∑=

−=N

nnnREC N

E1

22 ˆ1

xx (3.26)

Ebbene, la proiezione PCA è quella che, fra tutte le possibili proiezioni ortogonali con

TWQ = , WS = e ( )ℜ∈= qq MIQS , minimizza tale errore ponendo nelle colonne di W i

vettori che generano il sottospazio principale degli N dati. Nel caso di modelli PPCA, ogni

pattern può essere rappresentato nello spazio latente grazie alla distribuzione a posteriori

)|( xtp che è una gaussiana.. Il dato sarà rappresentato dal suo valor medio condizionato che

assume la forma

[ ] nTMLnn pE xWMxtt 1)|( −== (3.27)

dove MLW è definita dalla (3.20) ed M è una matrice opportuna che non serve definire. Con

queste posizioni, si può dimostrare che la minimizzazione della (3.26) porta come risultato ad

avere

=nx̂ WTML {WML WML } M ⟨tn⟩ (3.27’)

Si noti che questa proiezione differisce dalla PCA in quanto, in generale, MLW non genera il

sottospazio principale dei dati.

3.4.8 Indici di stabilità

Sono stati mostrati nel paragrafo dedicato al classificatore basato su hyperboxes alcuni indici

che ottimizzano la partizione dello spazio dei patterns. Di seguito vengono illustrati altri indici

che sono stati implementati nel classificatore basato su PCA e che si sono rivelati essere molto

efficenti.

Con gli indici di stabilità si introduce un modo del tutto nuovo di ottimizzare un processo di

clustering: allontanandosi dai concetti di compattezza e separabilità, i quali sottintendono

un’idea di assolutezza dei loro valori e quindi devono subire una certa forzatura quando

utilizzati per gli indici relativi, la stabilità è riferita piuttosto alle differenze che intervengono fra

le varie partizioni e quindi sottintende un puro concetto relativo.


151

L’ipotesi di base consiste nel considerare le partizioni, fra cui scegliere la migliore, generate al

variare di un unico parametro da ottimizzare: nel caso di algoritmi partizionali la variazione del

parametro determinerà diverse soluzioni per lo stesso algoritmo; nel caso gerarchico ogni valore

del parametro sarà in corrispondenza biunivoca con l’iterazione legata all’algoritmo, sarà questo

il nostro caso.

Fra queste partizioni ve ne sarà una che permarrà inalterata per un intervallo dei valori assunti

dal parametro maggiore degli altri. L’indice di stabilità, funzione di questo unico parametro,

dovrà allora avere la proprietà di essere costante per tutti gli intervalli, detti di stabilità, per cui

la partizione rimane inalterata; il problema è quindi quello di definire un concetto di stabilità, o

equivalentemente di alterazione, della partizione e determinare un strumento matematico,

l'indice appunto, che la quantifichi in modo tale che esso sia minimo, o massimo, in

corrispondenza dell’intervallo di lunghezza maggiore. L’idea è infatti quella di ritenere la

partizione più stabile come quella più robusta rispetto alle variazioni del parametro ed alla

struttura dei dati, per cui essa dovrebbe essere quella che meglio identifica la reale struttura dei

dati in esame.

In realtà il vero problema è quello di determinare una funzione +ℜ→ℜ:f , al variare del

parametro t, che indichi quantitativamente quando e quanto la partizione è cambiata, il calcolo

dell’indice di stabilità è poi immediato; per questo motivo spesso per indice di stabilità si

intende proprio la particolare funzione f(t). Una volta che la si è stabilita, i passi da effettuare

saranno sempre i seguenti:

Determinare un insieme di partizioni P = {Ui : 1 ≤ i ≤ N} , ciascuna legata, con le modalità

prima viste, ad uno ed uno solo degli N valori di t utilizzati. Questi valori sono ordinati in modo

crescente, o decrescente, in un vettore finito ]...,,,[ 21 Nttt=T .

Determinare gli M valori di t in T, con )1(0 −≤≤ NM , indicanti quando la partizione è

cambiata. Se M=0, si può assegnare un unico valore convenzionale all’indice di stabilità e

scegliere arbitrariamente una partizione nell’intervallo tra tutte quelle generate,

matematicamente tutte uguali. Se M>0 si deve continuare: questi valori sono calcolati grazie ad

f(t) ed organizzati in un vettore TS ⊆′′′= ]...,,,[ 21 Mttt . I corrispondenti M valori di f(t)

indicanti quanto la partizione è cambiata sono organizzati nel vettore

)](...,),(),([ 21 Mtftftf ′′′=D , dove con )( itf ′ si intende la differenza tra la partizione di it′

e quella del parametro immediatamente precedente a it′ in T. I valori it′ che indicano il cambio

di partizione sono quelli per cui risulta ε>′)( itf , dove la costante non negativa ε, scelta a

piacere, determina la sensibilità della f(t) rispetto alle variazioni della partizione. La figura 3.16


152

mostra un esempio dei valori di t nel caso N=8 ed M=3: le partizioni distinte sono quelle

denominate A, B, C e D.

B

1t 12 tt ′= 7t36 tt ′=25 tt ′= 8t4t3tt

D

CA

Fig.3.16: Una possibile situazione dei valori del parametro

Con ovvio significato dei simboli, ed essendo M>0, si possono calcolare gli M+1 valori

dell’indice di stabilità collocati nel vettore I come segue:

11,)}({max2

)()(

diffmax_)1()( 11 −≤≤

′⋅′+′

⋅+′−′

⋅−= ++ Mhtf

tftfs

ttsh

i

hhhh

D

I ;

)}({max

)(

diffmax_)1()0( 111

itftf

stt

s′

′⋅+

−′⋅−=

D

I ;

)}({max

)(

diffmax_)1()(

i

MMN

tftf

stt

sM′

′⋅+

′−⋅−=

D

I ;

dove max_diff = max { MNii tttttt ′−′−′−′ + ,max, 111S

}.

Si potrà quindi scegliere la partizione legata a quello, fra questi intervalli, che rende massimo I.

I valori di I sono evidentemente compresi tra 0 ed 1, mentre il parametro s tende a pesare

nell’indice i contributi provenienti dalla lunghezza dell’intervallo di stabilità e dalle differenze

tra le partizioni che lo delimitano. A parità di lunghezza, e quindi di valore del primo addendo,

si può pensare che la partizione più stabile sia anche quella che più si differenzia dalla

precedente e dalla successiva, quindi che dia contributo maggiore al secondo addendo. I valori

di s, compresi tra 0 ed 1, possono essere scelti in relazione al problema in esame: s=0 significa

indice di stabilità puro, mentre s=1 significa scegliere la partizione più particolare fra le altre.

Si noti che all’interno di un qualsiasi intervallo non è detto che le partizioni siano tutte uguali,

ma soltanto che non si sono ritenute matematicamente significative le loro differenze, ad es. per

una certa scelta di ε, per cui si deve anche stabilire un modo per scegliere in quale punto

dell’intervallo più stabile scegliere la partizione ottima. Sono ora presentati alcuni criteri,

impropriamente chiamati indici, con cui determinare la f(t) e quindi stabilire le variazioni della


153

partizione: l’indice Lifetime già noto in letteratura e gli indici Jaccard e Rand Adjusted che sono

qui proposti, i quali sfruttano il concetto di metrica partizionale.

Fig.3.17a: Data set con 4 clusters ben separati e compatti

Intervallo di Stabilità per 4 Clusters

Fig.3.17b: Andamento del numero di clusters nel caso di Fig.3.17a

3.4.8.1 Indice Lifetime

Ghosh e Chakravarthy suggeriscono [Chakravarthy 1996] di considerare come criterio di

stabilità il numero di clusters della partizione: essa si riterrà variata se il suo numero di clusters

è differente da quello della partizione precedente. La )( itf ′ potrà quindi pensarsi come


154

differenza tra il numero di clusters in it′ e quello in 1−′it , la variazione avviene se essa risulta

maggiore di zero quando 0=ε .

La figura 3.17a mostra un data set clusterizzato mediante ottimizzazione dell’algoritmo

HMPPCA, in cui la scelta della partizione ottima viene effettuata mediante l’indice di stabilità

Lifetime: il data set presenta quattro zone in cui i punti risultano più addensati, ed infatti queste

regioni vengono individuate dall’algoritmo mediante quattro clusters. Osservando l’andamento

del numero di clusters in figura 3.17b e dell’indice di figura 3.18, si osserva quando la

partizione più stabile nasce, fino a quando esiste, e quanto è durata e con che intervallo di

lunghezza.

Quando sono presenti più intervalli ottimi di uguale lunghezza, il criterio utilizzato per la scelta

può essere quello della loro nascita (birthtime): a seconda del tipo di approccio, ad es.

costruttivo, e del verso di ordinamento del parametro, potrà scegliersi la partizione che nasce per

prima o quella che nasce per ultima. Questo criterio può valere in generale per qualsiasi altro

indice di stabilità.

Indice Lifetime nell’intervallo di 4 Clusters

Fig.3.18: Andamento dell’indice Lifetime, con s=0, nel caso di figura 3.17

L’indice Lifetime non richiede alcuna conoscenza della logica dei risultati, l’unica informazione

necessaria è quella del numero di clusters. A questo proposito, bisogna però osservare che

l’indice Lifetime non riesce a distinguere due partizioni consecutive U e U’ nel caso in cui esse

presentino lo stesso numero di clusters: è abbastanza raro, ma non improbabile, che due

partizioni ottenute per valori consecutivi del parametro presentino lo stesso numero di clusters e

differiscano nella loro struttura. Una situazione del genere, invisibile per l’indice Lifetime,

verrebbe invece ben individuata se si considerasse una misura diretta della differenza, e quindi

della distanza, che c’è tra due partizioni. Questo ha stimolato lo sviluppo degli indici successivi.


155

3.4.8.2 Indici di Jaccard e Rand Adjusted

Precedentemente si è mostrata la possibilità dell’uso delle contingency tables per valutare

l’affinità tra due patterns descritti da un serie di features con scala nominale. Ebbene, è

immediata l’estensione di questa procedura nel caso della valutazione dell’affinità, e quindi

della distanza, tra due partizioni. Le definizioni degli indici omonimi sono immediate una volta

ridefiniti i coefficienti ija date due partizioni A e B:

11a è il numero delle coppie di patterns che sono nello stesso cluster sia in A che in B;

10a è il numero delle coppie di patterns che sono nello stesso cluster in A ma in clusters diversi

in B;

01a è il numero delle coppie di patterns che sono nello stesso cluster in B ma in clusters

diversi in A;

00a è il numero delle coppie di patterns che sono in clusters diversi sia in A che in B.

Se i patterns sono N, allora sarà 2

)1(01101100

−⋅=+++

NNaaaa che è il numero di coppie

che si possono formare con N patterns.

La )( itf ′ sarà allora pari ad una di queste distanze tra la partizione in it′ e quella in 1−′it , la

variazione avviene se essa risulta maggiore di ε. Un valore dell’indice pari a 0 significherà

partizioni esattamente uguali, mentre un valore pari ad 1 indicherà la massima differenza

possibile fra esse. Si noti che questi sono indici diretti in quanto richiedono la conoscenza di una

partizione crisp.

Distanza fra partizioni con 3 e 4 Clusters

Distanza fra partizioni con 4 e 5 Clusters

Fig.3.19: Distanze Jaccard fra le partizioni nel caso di figura. 3.17a


156

Indice Jaccard nell’intervallo con 4 Clusters

Fig.3.20: Indice di stabilità nel caso di figura 3.19

Nella figura 3.19 sono mostrati i valori dell’indice Jaccard, cioè delle distanze delle partizioni in

corrispondenza dei valori assunti dal parametro, per il data set di figura 3.17a; in figura 3.20 è

mostrato l’andamento del relativo indice di stabilità.

3.4.8.3 Indici di bontà fuzzy

Una ultima particolarità del classificatore preso in esame è quello di poter determinare, al

termine di una operazione di classificazione, la bontà dei risultati. Infatti, alla fine del processo

di training si avrà a disposizione una rete o modello in grado di trattare situazioni ed esempi mai

visti prima, test set, fornendo i risultati di classificazione nel formato descritto. Su tali risultati

verrà effettuato un controllo confrontando le uscite fornite dal classificatore con le classi vere di

appartenenza di ciascun pattern del set presentato. Dal numero degli errori commessi, così come

dalla loro percentuale, si potranno trarre le conclusioni sulla bontà del processo eseguito. E’

proprio in questa ottica di valutazione delle prestazioni che sono stati introdotti degli indici di

bontà con lo scopo di valutare la validità, o meglio l’affidabilità, dell’intero processo di

classificazione; infatti ciò che interessa maggiormente è riscontrare la capacità di

generalizzazione della struttura implementata.

Più che enumerare semplicemente gli errori commessi, risulta più significativo misurare, nel

caso in cui un pattern venga classificato in maniera errata, l’entità dell’errore commesso dal

classificatore e, nel caso in cui esso sia contraddistinto dall’etichetta giusta, in che misura il

classificatore abbia eseguito il suo compito in maniera corretta. E’ necessario, infatti, tenere in


157

considerazione come l’obiettivo che si prefigge l’algoritmo presentato sia quello di studiare

approfonditamente un insieme di dati caratterizzato dalla presenza di classi non mutuamente

esclusive con patterns appartenenti contemporaneamente a più di una classe. In questo caso si

rivela estremamente utile la logica fuzzy, la quale consente di proporre degli opportuni indici in

grado di misurare adeguatamente le caratteristiche del classificatore realizzato, valutando non

solo il numero di errori commessi o di dati classificati correttamente, ma anche il grado di

appartenenza alle varie classi secondo una logica appunto sfumata. In particolare si procederà

introducendo un indice fondamentale ed altri due, i quali rappresentano delle quantità

intermedie, utilizzate per arrivare alla sua determinazione, ma che assumono un interesse

fondamentale nell’analisi delle prestazioni dell’algoritmo implementato.

Si indichi con N la cardinalità dell’insieme dei dati e sia E il sottoinsieme dei patterns

classificati in maniera errata, la cui cardinalità sia pari ad errn . Siano inoltre:

)()1()()( iDaai

Caaia xpxpx µµµ −+=

)()1()()( iDrri

Crrir xpxpx µµµ −+=

rispettivamente i valori di appartenenza del generico pattern ix del data set alla classe sbagliata,

cui esso viene assegnato dal classificatore, ed alla classe corretta, la cui etichetta viene fornita

dal data set. Questi sono ottenuti pesando, secondo il valore del peso corrispondente alla classe

in questione, il livello di appartenenza corrispondente alla sola parte continua e quello relativo

alla parte discreta. Ovviamente, nel caso in cui si faccia riferimento ad un data set costituito

esclusivamente da dati continui oppure da dati discreti, le espressioni precedenti si semplificano

notevolmente, dovendosi in esse prendere in considerazione esclusivamente il livello di

appartenenza relativo ad uno dei due contesti.

Si definisce Overall Fuzzy Error (FE) la seguente quantità:

∑∑∈∈

=−=Ex

ieEx

iria

ii

xfxxFE )())()(( µµ

Essa corrisponde a valutare, in corrispondenza di tutti i patterns del data set classificati in

maniera errata, l’entità dell’errore commesso come differenza tra il valore di appartenenza alla

classe errata e quello alla classe giusta. Il valore assunto dall’indice FE deve, evidentemente,

risultare il più piccolo possibile, dal momento che esso fornisce notizia dell’errore

effettivamente commesso nel classificare erroneamente i dati. Nel caso crisp, il valore di questo

indice corrisponde al numero di patterns erroneamente classificati, cioè errn .

Si definisce Overall Fuzzy Reliability (FR) la quantità seguente:


158

{ } ∑∑∉∉

≠=⋅−=

Exir

Exij

rjir

ii

xfxxFR )())(max)(( µµ

Essa corrisponde a valutare, relativamente a tutti i patterns del data set classificati in maniera

corretta dalla rete prodotta, in che misura essi siano stati classificati nel modo giusto, calcolando

la differenza fra il grado di appartenenza alla classe giusta ed il massimo grado di appartenenza

fra tutte le classi errate. Il valore di questo indice deve essere, evidentemente, il più elevato

possibile, in quanto esso corrisponde al margine di valutazione corretta dei dati. Nel caso crisp,

tale quantità si riduce alla differenza fra il numero di patterns componenti il data set ed il

numero di patterns classificati in modo non corretto, cioè N - errn .

Sulla base dei valori assunti dalla coppia di indici appena proposti, è possibile valutare il valore

dell’indice fuzzy proposto per la bontà della classificazione, definito Fuzzy Classification

Quality (FCQ), la cui espressione è:

N

xfxf

FCQEx

irEx

ie

ii

))(1()( ∑∑∉∈

−+

=

che in termini degli indici FE ed FR, risulta pari a:

NFRnNFE

FCQ err −−+=

)(

Il valore assunto dall’indice FCQ è ovviamente compreso tra zero ed uno, risultando

tipicamente prossimo a 0,5. Più piccolo risulta il valore di questo indice, migliore sarà il

risultato della classificazione dal punto di vista fuzzy.

I classificatori neuraliweb.tiscali.it/patrizio_antici/tesi/08_cap3.pdfCapitolo 3: I due...

Documents

Transcript of I classificatori neuraliweb.tiscali.it/patrizio_antici/tesi/08_cap3.pdfCapitolo 3: I due...