4
producono direttamente la struttura “dendritica” (vedi paragrafo 1.7.1) che
successivamente viene utilizzata nella fase di ricerca.
Per scendere lungo la struttura ad albero, durante il processo di ricerca, vengono
effettuati confronti tra “centroidi”, gli elementi prototipici dei cluster, elementi che
devono essere aggiunti alla base di dati.
L’applicazione di metodi partitivi o non gerarchici per la realizzazione di una
struttura ad albero si è rivelata maggiormente efficace rispetto ai metodi gerarchici; tali
procedure permettono di limitare il numero di centroidi da aggiungere all’insieme
originale degli elementi, inoltre questo tipo di algoritmi molto più rapido rispetto ai
metodi gerarchici, consentendo di riaggiornare periodicamente tutta la struttura qualora
la base di dati venisse modificata in misura rilevante.
Con la pianificazione del progetto “Key Reader 2000S” Silca S.p.A. intende fornire
uno strumento utile per evitare il problema dell’incompletezza delle transazioni; in
questo particolare mercato infatti non tutte le transazioni si traducono con un incontro
tra domanda ed offerta, molto spesso le difficoltà nella fase di riconoscimento delle
chiavi determinano una volontaria restrizione dell’offerta, che a livello pratico si
traduce nell’impossibilità di effettuare il servizio richiesto per mancanza del materiale
necessario (chiavi grezze e macchina duplicatrice) o delle necessarie competenze per
effettuare il riconoscimento delle chiavi.
La tesi è strutturata in due parti distinte, nella prima vengono esposti i metodi di
cluster analysis mentre nella seconda viene presentato il caso pratico ed il metodo
impiegato per risolvere il problema proposto, documentando i test ed i confronti che
hanno portato alla scelta dei metodi partitivi per la realizzazione della struttura
gerarchica.
Nel corso della trattazione non verranno volutamente tradotti alcuni termini inglesi
tra cui cluster analysis, pattern recognition e fuzzy logic. Questa decisione è maturata
durante la stesura del presente lavoro, tenendo conto che la maldestra traduzione dei
termini inglesi, oramai universalmente accettati, non comporta alcun vantaggio.
5
CAPITOLO 1
CLASSIFICAZIONE E CLUSTERING
1.1 Introduzione: la classificazione
L’acquisizione delle informazioni, nelle scienze come nei processi cognitivi, deve
necessariamente essere seguita da una fase di analisi che consenta la comprensione dei
fenomeni che hanno generato i dati. A tale scopo si rivelano indispensabili strumenti in
grado di organizzare opportunamente le informazioni, come la classificazione, che tra le
diverse metodologie disponibili è sicuramente una delle più efficienti.
Classificare significa distinguere e separare ciò che appare diverso ed unire in gruppi
omogenei di ciò che invece si presenta simile; queste semplici operazioni consentono di
organizzare collezioni anche molto vaste di informazioni.
La classificazione è uno dei processi fondamentali della scienza e costituisce parte
integrante di ogni processo di apprendimento, mediante la classificazione è possibile
individuare la struttura intrinseca delle informazioni analizzate e le relazioni che legano
le stesse; ottenendo una migliore e più completa comprensione del problema analizzato.
Oltre ad agevolare la conoscenza, la classificazione consente un’adeguata
organizzazione delle informazioni; uno schema di classificazione infatti può
rappresentare un metodo estremamente conveniente per organizzare un vasto insieme di
dati in modo che il recupero delle informazioni possa essere effettuato in maniera
efficiente.
La memorizzazione ed il successivo reperimento delle informazioni risultano molto
semplici e rapidi, poiché la classificazione permette di ridurre la mole di informazioni
da gestire, rendendo sufficiente analizzare le sole classi od un loro elemento
rappresentativo piuttosto che l’intero insieme dei dati, inoltre la migliore conoscenza
della struttura intrinseca contribuisce ad una più efficace procedura di ricerca.
6
La reale importanza della classificazione appare evidente se si considera il fatto che
la comprensione della struttura intrinseca dell’informazione, la sua organizzazione ed il
suo recupero efficiente rappresentano aspetti di fondamentale importanza in svariate
discipline scientifiche. Ad esempio la segmentazione del mercato rispetto alle diverse
esigenze e preferenze dei potenziali consumatori rappresenta solo uno dei motivi per cui
la classificazione sia divenuta elemento imprescindibile della scienza, in particolare di
quelle economiche.
Aristotele (384 - 322 a.C.) fu il primo a dare un significato scientifico al concetto di
classificazione introducendo la logica “classificatoria”, ma ancora oggi dopo più di
duemila anni non esiste una vera e propria “scienza della classificazione”, nonostante
tale attività sia così importante e così largamente utilizzata.
La sempre più rapida crescita del volume di informazioni a disposizione dell’uomo e
della scienza, ha condotto alla ricerca ed allo sviluppo di strumenti nuovi e più efficienti
per organizzare ed analizzare le informazioni. Partendo dalle medesime basi della
classificazione tradizionale, la cluster analysis fornisce alcune rapide ed efficaci
metodologie per affrontare tali problemi.
In questo capitolo verrà introdotta la cluster analysis e saranno evidenziate similarità
e differenze con il problema della classificazione, al fine di chiarire il motivo che da
qualche decennio spinge molti ricercatori allo studio ed al perfezionamento di questo
potente strumento di investigazione.
1.2 Clustering
La parola inglese cluster è difficilmente traducibile, letteralmente significa
“grappolo”, ma anche “ammasso”, “sciame”, “agglomerato”, parole che visivamente
richiamano alla mente una o più entità costituite da elementi più piccoli, omogenei tra
loro ma allo stesso tempo distinti da altri elementi esterni al cluster stesso.
Una definizione di cluster è peraltro difficile da trovare anche in letteratura,
normalmente si parla di coesione interna ed isolamento esterno [Everitt, 1980], oppure
di elevato grado di associazione naturale tra gli elementi di un cluster e di relativa
distinzione tra cluster differenti [Anderberg, 1973], in modo più generale si può definire
cluster una parte dei dati (un sottoinsieme della popolazione in analisi) che consiste di
7
elementi molto simili rispetto alla rimanente parte dei dati [Mirkin, 1996]. La generalità
delle definizioni di cui sopra è determinata principalmente dalla assoluta impossibilità
di formalizzare matematicamente il concetto di cluster in maniera univoca, del resto
empiricamente si possono osservare molti tipi differenti di cluster: sferici, ellissoidali,
lineari.
Le tecniche che permettono di ottenere i cluster dai dati osservati sono molteplici ed
utilizzano procedure differenti, comunemente vengono denominati algoritmi di
clustering per sottolineare il carattere automatico di tale procedura.
E’ possibile far risalire la nascita di tale disciplina all’inizio di questo secolo, quando
si cominciò ad avvertire la necessità di sostituire l’occhio ed il cervello umano
nell’attività classificatoria con strumenti maggiormente precisi, in grado di gestire
enormi quantità di informazioni e non limitati a spazi tridimensionali.
Solamente con lo sviluppo e la diffusione dei moderni computer le procedure di
clustering cominciarono ad essere impiegate con successo in numerose discipline: nelle
scienze naturali, nell’ambito della tassonomia numerica [Sneath & Sokal, 1973], allo
scopo di rendere più veloce e precisa l’opera di classificazione delle specie viventi;
nelle scienze sociali per individuare gruppi socio-economici e segmenti di mercato; nel
campo dell’intelligenza artificiale ed in particolare nella pattern recognition, per
l’analisi, il confronto ed il riconoscimento dei dati. Seguendo questo percorso, pur in
assenza di un rigoroso fondamento teorico, ha avuto origine la disciplina oggi nota
come cluster analysis.
Generalmente gli algoritmi di clustering cercano di separare un insieme di dati nei
suoi cluster costituenti, evidenziando i gruppi naturali, ossia la struttura classificatoria
relativa ai dati stessi, si suppone che i dati analizzati possiedano una propria
classificazione e compito degli algoritmi di clustering è proprio trovare la struttura
classificatoria che meglio si adatta alle osservazioni.
Mentre nella classificazione la struttura dei dati è nota, quindi si suppone che per
classificare un insieme di dati non ordinati ci si riferisca comunque ad una struttura
classificatoria conosciuta, nella cluster analysis poco o nulla è noto circa la struttura dei
dati, tutto ciò che è disponibile è una collezione di osservazioni le cui relative classi si
appartenenza sono ignote.
8
Questa, che è la principale differenza tra clustering e classificazione, ci permette di
definire la cluster analysis come strumento classificatorio empirico basato sulle
osservazioni, le eventuali informazioni note a priori possono essere utilizzate per
verificare la bontà dello schema classificatorio ottenuto. E’ quindi errato definire gli
algoritmi di clustering “metodi di classificazione automatica” visto che la struttura
classificatoria viene individuata contestualmente all’assegnazione di ogni elemento al
suo gruppo di appartenenza.
Il compito degli algoritmi di clustering è quindi duplice, da un lato trovare la
struttura classificatoria intrinseca dei dati, i cosiddetti gruppi naturali, dall’altro
assegnare ogni elemento alla rispettiva classe di appartenenza, per fare questo
generalmente gli algoritmi cercano di classificare le osservazioni in gruppi tali che il
grado di associazione naturale sia alto tra i membri dello stesso gruppo e basso tra i
membri di gruppi differenti. Si può quindi affermare che l’essenza della cluster analysis
può anche essere vista come l’assegnazione di appropriati significati ai termini “gruppi
naturali” ed “associazione naturale”.
1.3 Classificazione degli algoritmi di clustering
Data la varietà dei metodi e degli algoritmi di clustering disponibili è opportuno
presentarne una classificazione
1
[Sneath & Sokal, 1973], che permetta di comprendere
quali siano le principali caratteristiche delle diverse procedure.
1
Quella presentata non è l’unica classificazione degli algoritmi di clustering, vedi [Bezdek, 1981]. Inoltre
è opportuno precisare che sono stati esclusi dalla presente trattazione i metodi di clustering che utilizzano
la teoria dei grafi.
Clustering
Gerarchici Non gerarchici
Agglomerativi Divisivi
Cluster
sovrapposti
Cluster non
sovrapposti
Figura 1.1 Classificazione degli algoritmi di clustering
9
1. Metodi gerarchici e non gerarchici: costituisce la distinzione principale, si riferisce
sia al metodo usato per ottenere i cluster che alla struttura del risultato dell’algoritmo
stesso. I metodi gerarchici producono delle tipiche strutture ad albero, di tipo
ricorsivo o annidato; i cluster dei livelli più alti sono aggregazioni di cluster dei
livelli più bassi dell’albero. I metodi non gerarchici vengono anche definiti partitivi
poiché dividono l’insieme dei dati in partizioni, le quali sono costituite solamente dai
singoli elementi oggetto della classificazione, l’insieme dei dati da classificare viene
quindi diviso in più sottoinsiemi o cluster senza ulteriori suddivisioni all’interno di
ogni cluster.
2. Metodi agglomerativi e divisivi: si riferisce al metodo con il quale operano gli
algoritmi gerarchici ed anche alla direzione seguita per costruire lo schema
classificatorio (albero gerarchico). I metodi agglomerativi procedono dal basso verso
l’alto unendo i singoli elementi mentre i metodi divisivi procedono dall’alto verso il
basso scindendo i cluster in altri più piccoli.
3. Metodi con sovrapposizione e senza sovrapposizione (dei cluster): riguarda i
cluster prodotti con i metodi non gerarchici o partitivi e si riferisce ai cluster ottenuti
per mezzo dell’algoritmo. I cluster si definiscono non sovrapposti quando ogni
elemento appartiene ad uno e ad un solo cluster; i cluster sovrapposti vengono anche
denominati fuzzy cluster poiché ogni elemento può appartenere a più cluster
differenti per mezzo di un grado di appartenenza definito come segue:
> ≅ Π
Ci
i
x 01,
L’elemento x
i
appartiene al cluster C
i
con un grado di appartenenza compreso
nell’intervallo > ≅01, .
Questa estensione della cluster analysis classica deriva dalla considerazione che
nella realtà molti fenomeni non si presentano con contorni ben definiti, ed un
elemento può appartenere contemporaneamente a più cluster differenti. Ad esempio
nel caso si vogliano classificare diverse specie di frutta, gli ibridi si troveranno in
una posizione intermedia tra i cluster dei frutti dal cui incrocio sono stati generati, ed
inserirli forzatamente in uno solo dei due cluster rappresenta una errata
interpretazione della realtà [Bezdek, 1981].
10
1.4 Struttura generale degli algoritmi di clustering
La necessità di elaborare un metodo algoritmico per la classificazione dei dati viene
di solito spiegata in letteratura con un esempio alquanto convincente: se si pensasse di
enumerare tutte le possibili strutture classificatorie di un insieme di n dati per
confrontarle e quindi scegliere la migliore con un procedimento di tipo esaustivo, ci si
troverebbe di fronte ad numero finito ma enorme di possibili schemi di classificazione
tale da rendere computazionalmente intrattabile il problema; tale numero corrisponde
alla seguente espressione:
1
1
1
c
c
j
j
cj
n
j
c
!
♣
♥
♦
•
≠
÷
♠
←
↔
≡
…
≈
ƒ
Volendo quindi classificare venticinque osservazioni in dieci classi distinte (n=25,
c=10) si dovrebbero esaminare 10
18
strutture differenti, una mole di dati troppo grande
da trattare persino per i più potenti computer.
Il metodo su cui si fondano gli algoritmi gerarchici agglomerativi si basa su una
procedura iterativa di unione degli elementi più simili due alla volta, il processo si
ripete quindi nc volte (15 volte per l’esempio considerato sopra).
I metodi partitivi invece utilizzano una procedura iterativa nota con il nome di ciclo
di Picard [Bezdek, 1981], che comprende una fase iniziale in cui viene definita,
generalmente in modo casuale, una struttura iniziale, che viene successivamente
“aggiornata” ad ogni iterazione fino alla convergenza ad una struttura stabile. Questo
metodo non permette di conoscere il numero esatto di iterazioni che dovranno essere
effettuate; per cautelarsi da tale inconveniente molti algoritmi, oltre al criterio di
convergenza appena illustrato, utilizzano un criterio aggiuntivo, ossia terminano in ogni
caso dopo un numero predeterminato di iterazioni.
In ogni caso tutti i metodi partitivi convergono in un numero solitamente non molto
elevato di iterazioni, in generale, tanto più velocemente quanto più la struttura iniziale si
avvicina alla reale struttura classificatoria. La fase di inizializzazione costituisce quindi
un aspetto molto importante dell’algoritmo.
Nonostante la varietà degli algoritmi di clustering e la diversa metodologia utilizzata
per trovare i gruppi naturali dei dati, è possibile individuare alcuni punti comuni a tutti
gli algoritmi. Ovviamente esistono numerose differenze tra i diversi metodi, in special
modo confrontando metodi gerarchici e non gerarchici; tuttavia entrambe le
11
metodologie partono dalla medesima premessa: raggruppare gli elementi simili e
separare quelli diversi, è quindi opportuno illustrare sommariamente gli aspetti che
caratterizzano questi gli algoritmi.
In primo luogo per trovare la classificazione ottimale dei dati è necessario poter
misurare la diversità o la somiglianza tra i diversi elementi, serve quindi uno strumento
che traduca numericamente tali concetti. La letteratura presenta due differenti soluzioni
relativamente alle misure di similarità o dissimilarità: un primo approccio che utilizza le
misure di distanza ed un secondo che utilizza i coefficienti di correlazione quali misure
di similarità tra elementi.
L’utilizzo di tali funzioni si differenzia fortemente tra metodi gerarchici e non
gerarchici; i primi (nel caso di algoritmi agglomerativi) utilizzano la matrice delle
distanze, che risulta quadrata, simmetrica ed in cui ogni elemento rappresenta la
distanza tra due osservazioni.
Ad ogni iterazione la matrice delle distanze viene aggiornata, tenendo conto che gli
elementi da analizzare sono diminuiti di un’unità, per effetto della fusione nel caso dei
metodi agglomerativi; oppure sono aumentati di un’unità nel caso di algoritmi divisivi.
I metodi non gerarchici invece non si servono della matrice delle distanze, ma ad
ogni iterazione la struttura viene aggiornata calcolando la distanza degli n elementi
rispetto ai c centroidi dei cluster, vengono quindi calcolate nc distanze ad ogni passo
2
.
Oltre ad una misura di distanza è necessaria una struttura che consenta di
rappresentare la classificazione dei dati: gli algoritmi gerarchici utilizzano i
dendrogrammi, strutture gerarchiche che rappresentano le unioni (o le scissioni) che
l’algoritmo esegue ad ogni iterazione; quelli partitivi utilizzano un vettore di indici o
più comunemente la matrice di partizione, una matrice c υn dove ogni elemento indica
l’appartenenza di ogni osservazione rispetto ad ogni cluster.
Alcuni metodi gerarchici e quasi tutti i metodi partitivi si servono di elementi
prototipici nell’elaborazione della struttura classificatoria, in queste procedure il tipo di
centroide (solitamente elemento medio o mediano del cluster) ed il loro calcolo nella
procedura iterativa incidono negativamente sulla complessità computazionale
dell’algoritmo, anche se questo accorgimento rende più semplice ed intuitiva la
procedura per determinare la corretta partizione dei dati.
12
Non esiste un metodo di clustering universalmente applicabile, i risultati forniti
dall’algoritmo dipendono fortemente da tutti gli elementi considerati; utilizzare un
metodo gerarchico od uno partitivo, una funzione di distanza piuttosto che un’altra o un
particolare tipo di centroide conducono all’identificazione di strutture differenti per il
medesimo campione di osservazioni, tale “debolezza” ha generato dubbi e perplessità.
Alcuni ricercatori hanno effettuato studi comparativi tra le numerose metodologie
disponibili, cercando di agevolare la scelta tra i diversi metodi da parte dell’utente, i
confronti si basano sia sulla tipologia di dati da analizzare che sulle caratteristiche della
struttura classificatoria [Anderberg, 1973] e soprattutto [Dubes & Jain, 1976].
Per poter confrontare i diversi algoritmi, verificare la bontà dei risultati e stabilire se
quella ottenuta è una struttura classificatoria plausibile, la procedura di clustering viene
arricchita da una fase finale di validazione dei risultati, nella quale si ricorre a strumenti
come le funzioni di validazione per misurare alcune caratteristiche proprie della
struttura ritenute desiderabili, ad esempio, si richiede che la varianza all’interno dei
cluster sia minima mentre tra cluster differenti deve essere elevata (vedi paragrafo 1.8).
1.5 Misure di Distanza e Spazi Metrici
Parte fondamentale di ogni algoritmo di clustering è un’appropriata misura di
distanza o dissimilarità che permetta di tradurre numericamente i concetti, in
precedenza esposti, di associazione tra elementi simili e distinzione tra elementi
appartenenti a cluster diversi; tale necessità si presenta sia per i metodi gerarchici che
per quelli partitivi.
E’ opportuno ricordare che alcuni autori traducendo letteralmente il significato del
termine associazione naturale tra elementi utilizzano nei loro algoritmi delle misure di
similarità piuttosto che misure di dissimilarità, ma data la ovvia relazione di
complementarità esistente tra le due misure è opportuno soffermarsi solo sulle seconde.
L’utilizzo delle misure di distanza negli algoritmi di clustering appare più chiaro se
si immagina ogni elemento da classificare come un punto in uno spazio
iperdimensionale, per semplicità è possibile riferirsi ad uno spazio bidimensionale come
in figura 1.2, dove sono esemplificati due cluster ben distinti, la loro forma
2
L’algoritmo “fuzzy c-means” ne calcola nc
2
ad ogni iterazione.
13
approssimativa ed i loro “centroidi” (le croci poste al centro delle linee tratteggiate che
rappresentano il perimetro dei cluster).
In questa rappresentazione la struttura classificatoria dei dati è facilmente
individuabile, la distanza tra i punti (elementi) appartenenti al medesimo cluster è
inferiore a quella tra punti appartenenti a cluster differenti; si può ancora notare che i
centroidi, che rappresentano i centri dei cluster, hanno delle distanze minime rispetto
agli altri elementi del cluster; infatti la minimizzazione della distanza dei punti attorno
al centroide del cluster è uno dei criteri più utilizzati negli algoritmi di clustering.
Questo ovviamente rappresenta un semplice esempio, utilizzato allo scopo di chiarire
il motivo dell’utilizzo delle misure di distanza nella cluster analysis; generalmente,
anche nei problemi più comuni, ogni elemento viene descritto da un vettore con più di
tre elementi, anche in questo caso l’approccio rimane valido nonostante non sia
effettuabile una verifica ex post basata su informazioni di tipo grafico.
A questo punto è necessario definire formalmente i concetti di misura di dissimilarità
e di misura di distanza: sia S la rappresentazione simbolica di uno spazio di misura e
siano x y z, e S tre punti qualsiasi in S. Si definisce una misura di dissimilarità o
“semimetrica” una funzione d,:xy SS υ
che soddisfa le seguenti condizioni:
1. d,xy 0 se e solo se x y ,
2. d,xy τ0 x y, S ,
3. d, d,xy yx x y, S .
Figura 1.2 Clustering in uno spazio bidimensionale
14
La prima condizione indica la riflessività della relazione, la seconda richiede che la
distanza, sia comunque non negativa, la terza indica infine la simmetria. Se oltre alle
sopra elencate condizioni la funzione soddisfa anche la seguente, la funzione di distanza
può essere definita una metrica:
4a. d, d, d,xy xz yzδ x y z,, S
Questa condizione, comunemente definita disuguaglianza triangolare, richiede che la
distanza tra i punti x ed y sia minore od al più uguale alla somma delle distanze tra i due
punti ed un terzo punto z distinto dai precedenti (vedi figura 1.3).
Se la funzione soddisfa la seguente, più forte versione della disuguaglianza
triangolare la misura di distanza costituisce una ultrametrica:
4b. ⊥ d, maxd,,d,xy xz yzδ x y z,, S
1.5.1 La metrica euclidea
Quella euclidea è probabilmente la metrica più nota, lo spazio di misura S in cui viene
definita tale metrica è
n
dove n indica la dimensione dello spazio, ossia il numero di
coordinate che possiede ogni punto.
E’ possibile derivare la definizione di distanza euclidea partendo dal prodotto
scalare, definito come segue:
Prodotto scalare: xy,
n
, il loro prodotto scalare xy, è definito come:
xy,
ƒxy
ii
i
n
1
.
x
y
z
d(x,y)
d(x,z)
d(y,z)
Figura 1.3 Disuguaglianza triangolare
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
