Capitolo 1 Clustering Algorithm

(1)

Capitolo 1

Clustering Algorithm

Con il termine clustering sono indicate un insieme di tecniche per raggrup-pare oggetti omogenei di un insieme di dati in base alla loro similarità. Per ottenere risultati soddisfacenti è necessario individuare una buona metrica cioè una buon metodo per calcolare la distanza fra gli elementi. Gli algorit-mi di clustering raggruppano gli elementi rispetto alla distanza reciproca fra gli elementi stessi quindi l'appartenenza di un elemento ad un certo insieme dipende da quanto l'elemento preso in considerazione sia distante dall'insie-me stesso. Un algoritmo di clustering è ottimale se i cluster che esso genera hanno la caratteristica di avere gli elementi all'interno di uno stesso cluster molto coesi e nello stesso tempo separando bene un cluster dagli altri. La Cluster Analysis consiste nel raggruppare gli oggetti solamente sulla base delle informazioni contenute nei dati che descrivono gli oggetti e delle relazio-ni fra questi. L'obiettivo consiste nel partizionare gli oggetti in modo che gli oggetti dentro un gruppo siano simili (o in relazione) fra di essi e dierenti (o non in relazione) rispetto agli oggetti di altri gruppi. Maggiore è la similarità (o l'omogeneità) all'interno del gruppo e maggiore è la dierenza fra i gruppi, ossia migliore o più distinto è il clustering.

In molte applicazioni, la nozione di cluster non è ben denita. Per meglio capire le dicoltà per decidere quali elementi costituiscono un cluster, consi-deriamo la Figura 1.1, che mostra venti punti e tre diversi modi di suddividerli in clusters. La diversa forma del punto indica l'appartenenza ad un cluster. La Figura 1.1(b) e 1.1(d) divide i dati rispettivamente in due e sei parti, tut-tavia l'apparente divisione di ognuno dei due grossi cluster in tre sottocluster potrebbe essere semplicemente un artefatto del sistema visivo umano; inoltre potrebbe anche essere irragionevole dire che i punti formano quattro cluster, come mostrato in Figura 1.1(c). Questa gura illustra come la denizione di

(2)

CAPITOLO 1. CLUSTERING ALGORITHM 2 un cluster sia imprecisa per cui la denominazione più corretta dipende dalla natura dei dati e dai risultati che si vuole ottenere.

La Cluster Analysis è relativa ad altre tecniche che sono utilizzate per divi-dere un insieme di oggetti in gruppi. Per esempio, il clustering può essere considerato come una forma di classicazione nel quale si crea una etichet-tatura degli oggetti con etichette di classi (o cluster), tuttavia tali etichette sono derivate solo dai dati; diversamente, nella classicazione supervisionata, agli oggetti nuovi non etichettati è assegnata un'etichetta di classe usando un modello sviluppato a partire dagli oggetti di cui conosciamo l'appartenenza a quella determinata classe. Per questa ragione, la cluster analysis è spesso riferita nella letteratura come classicazione non supervisionata. Quando il termine classicazione è usato nel contesto del Data Mining senza specicare ulteriormente il tipo, solitamente si intende la classicazione supervisionata. Sebbene, a volte, si utilizzino anche i termini segmentazione e partizionamen-to come sinonimi di clustering, questi termini sono utilizzati frequentemente al di fuori del contesto della cluster analysis. Per esempio, il termine parti-zionamento è spesso usato con riferimento a tecniche per suddividere i gra in sottogra e che non sono strettamente legate al clustering. Segmentazione spesso riferisce la divisione di dati in gruppi usando semplici tecniche, ad esempio, un'immagine può essere suddivisa in segmenti basandosi solamente sull'intensità e su colore dei pixel, oppure le persone possono essere divise in gruppi in base al loro reddito. Tuttavia, alcuni graph partitioning e market segmentation sono relativi alla cluster analysis.

(3)

Figura 1.1: Dierenti modi di clusterizzare lo stesso insieme di punti

1.1 Dierenti tipi di Clustering

Un'intera collezione di clusters è comunemente riferita come clustering, in questa sezione, classichiamo il clustering in vari tipi: agglomerativo o divisivo, esclusivo o non esclusivo, partitivo o gerarchico, completo o parziale. Gli algoritmi di clustering possono essere classicati nel seguente modo:

Agglomerativo (Bottom-Up) o Divisivo (Top-Down)

• Bottom-Up dove inizialmente tutti gli elementi sono considerati singoli cluster e l'algoritmo iterativamente unisce i cluster più vicini no ad ot-tenere un numero pressato di cluster oppure nché la distanza minima tra i cluster non supera una certa soglia.

• Top-Down dove, al contrario, inizialmente tutti gli elementi fanno par-te di un unico cluspar-ter e successivamenpar-te l'algoritmo inizia a dividere l'insieme di partenza in tanti cluster di dimensioni inferiori. La suddi-visione è fatta in modo da ottenere elementi omogenei e si continua a suddividere no a che non si raggiunge una certo numero pressato di cluster.

(4)

CAPITOLO 1. CLUSTERING ALGORITHM 4

Esclusivo (Hard Clustering) o non esclusivo (Soft/Fuzzy

Clustering)

• Esclusivo dove ogni elemento può essere assegnato ad uno ed un so-lo gruppo (partizione), i cluster risultanti quindi non possono avere elementi in comune.

• Non esclusivo dove un elemento può appartenere ad uno o più cluster dierenti.

Partitivo (K-Clustering/Unnested) o Gerarchico (Nested)

• Partitivo in cui per denire l'appartenenza di un elemento al cluster viene utilizzata una distanza a partire da un punto rappresentativo per l'insieme (centroide, medioide, ...) avendo ssato a priori il numero di cluster da ottenere.

• Gerarchico in cui viene costruita una gerarchia di partizioni caratte-rizzata da un numero decrescente (crescente in caso di approccio Top-Down) di cluster la cui visualizzazione ad albero è detta dendrogramma e mostra i passi di accorpamento (o suddivisione) dei cluster.

Completo o Parziale

• Completo se ogni oggetto è necessariamente assegnato ad un cluster. • Parziale se un oggetto può non essere assegnato ad alcun cluster.

(5)

1.2 Dissimilarità fra cluster e Metriche

Per individuare i cluster che devono essere combinati (approccio Bottom-Up) o divisi (approccio Top-Down) è necessario denire una misura di dissimila-rità tra cluster. Una misura di dissimiladissimila-rità è tale che più alta è la distanza fra due oggetti, meno questi sono simili. Solitamente si utilizzano metriche speciche per valutare la distanza tra coppie di elementi (es. distanza Eucli-dea, Manhattan distance, distanza di Hamming, edit distance, ecc.) oppure è possibile denirne una personalizzata ad hoc per il nostro dataset.

(6)

1.3 Dierenti tipi di Clusters

Lo scopo del Clustering consiste nel trovare una suddivisione degli oggetti in gruppi (detti clusters), adeguata rispetto agli obbiettivi pressati dall'analisi. Per questo motivo, esistono diverse denizioni di cluster e altrettanti algorit-mi sono stati sviluppati per deteralgorit-minarli. La Figura 1.2 illustra le dierenze fra i vari tipi di clusters.

Well-Separated

Un cluster è un insieme di oggetti nel quale ogni oggetto è più vicino (o più simile) ad ogni altro oggetto nel cluster rispetto ad un oggetto non appar-tenente al cluster. Qualche volta viene utilizzata una soglia per specicare che tutti gli oggetti del cluster devono essere sucientemente vicini (o simili) agli altri. Queste idealistica denizione di cluster è soddisfatta solo quando i dati contengono clusters naturali che sono abbastanza distanti gli uni dagli altri. La Figura 1.2(a) è un esempio di cluster ben separati formati da due gruppi di punti. La distanza fra due punti qualsiasi appartenenti a dierenti gruppi è più grande della distanza fra due punti qualsiasi dentro un gruppo.

Prototype-Based

Un cluster è un insieme di oggetti nel quale ogni oggetto è più vicino (o più simile) al prototipo che denisce il cluster rispetto al prototipo di ogni altro cluster. Per dati con attributi continui, il prototipo di un cluster è spesso il centroide, cioè la media di tutti i punti nel cluster. Quando un centroide non è signicativo, come quando i dati hanno attributi categorici, il prototipo è spesso un medioide, cioè il punto più rappresentativo di un cluster. Per molti tipi di dati, il prototipo può essere visto come il punto più centrale, e in tal caso, ci riferiamo ai cluster basati su prototipo con center-based clusters. Non sorprendentemente, tali cluster tendono ad essere globulari, cioè di forma sferica, la Figura 1.2(b) mostra un esempio di center-based clusters.

Graph-Based

Se il dato è rappresentato come un grafo, dove i nodi sono oggetti e i links rappresentano connessioni fra gli oggetti, allora il cluster può essere denito come una componente connessa, cioè un gruppo di oggetti che sono connessi

(7)

con altri, ma che non hanno connessioni con oggetti al di fuori del gruppo. Un importante esempio di cluster basati su gra sono i contiguity-based clu-sters, dove due oggetti sono connessi solo se cadono entro una certa distanza l'uno dall'altro. Questo implica che ogni oggetto in un contiguity-based clu-ster è più vicino ad alcuni degli altri oggetti del cluclu-ster rispetto a qualsiasi altro punto in un dierente cluster. La Figura 1.2(c) mostra un esempio di tali clusters. Questa denizione di un cluster è utile quando i cluster sono irregolari o sovrapposti, ma può dare problemi quando è presente del rumore (noise), come illustrato nei due cluster sferici in Figura 1.2(c), un piccolo insieme di punti allineati può unire due clusters.

Possono esistere altri tipi di cluster basati su gra, uno di tali approcci de-nisce un cluster come una clique, cioè un insieme di nodi di un grafo che sono completamente connessi fra di loro; in particolare, se aggiungiamo con-nessioni fra gli oggetti nell'ordine delle loro reciproche distanze, si ottiene un cluster quando un insieme di oggetti forma una clique. Come i cluster basati su prototipo, tali cluster tendono ad essere globulari.

Density-Based

Un cluster è una regione densa di oggetti che è circondata da una regione con bassa densità. La Figura 1.2(d) mostra alcuni cluster basati su densi-tà ottenuti aggiungendo del rumore ai dati di Figura 1.2(c). I due cluster circolari non sono uniti, come in Figura 1.2(c), poiché i punti allineati svani-scono nel rumore. Similmente, anche la curva che è presente in Figura 1.2(c) svanisce nel rumore e non forma alcun cluster in 1.2(d). La denizione di cluster basato su densità è spesso utilizzata quando i cluster sono irregolari o sovrapposti, oppure quando è presente rumore e outliers; al contrario, una denizione di cluster basato sulla contiguità non si adatterebbe bene ai dati di Figura 1.2(d) in quanto il rumore tenderebbe a formare punti allineati fra cluster con il risultato di unire i due cluster in uno solo.

Shared-Property (Conceptual Clusters)

Più generalmente, possiamo denire un cluster come un insieme di ogget-ti che condividono alcune proprietà. Questa denizione comprende tutte le precedenti denizioni di cluster, cioè gli oggetti in un center-based cluster condividono la proprietà di essere tutti vicini allo stesso centroide o medioi-de. Tuttavia, l'approccio shared-property cluster include anche nuovi tipi di cluster. Consideriamo il cluster mostrato in Figura 1.2(e), è presente un'area

(8)

Figura 1.2: Dierenti tipi di clusters

triangolare (cluster) adiacente ad un'area rettangolare (cluster) e due cerchi sovrapposti (clusters). In entrambi i casi, un algoritmo di clustering neces-sita di un concetto di cluster molto specico per individuare correttamente questi cluster. Il processo di individuare tali cluster è chiamato clustering concettuale, tuttavia la nozione troppo specica di cluster fa rientrare questo caso nell'area del pattern recognition.

(9)

1.4 Hierarchical Clustering

Le tecniche di clustering gerarchico sono un'importante categoria di metodi di clustering. Questi approcci sono relativamente datati rispetto a molti altri algoritmi di clustering, ma sono ancora largamente utilizzati. Ci sono due approcci base per generare un clustering gerarchico:

Agglomerativo: Inizialmente i cluster sono costituiti dai singoli oggetti e ad ogni passo, si unisce la coppia di cluster più vicina (simile); per fare questo è necessario denire la nozione di prossimità fra cluster.

Divisivo: Inizialmente tutti gli oggetti appartengono ad un unico cluster che li contiene e ad ogni passo, si divide il cluster in sottocluster no ad ottenere cluster costituiti da singoli oggetti (singleton). In questo approccio è necessario decidere ad ogni passo quale cluster dividere e come eettuare la divisione.

I cluster agglomerativi sono i più comuni e nel seguito ci riferiremo a questa tipologia di clustering.

Un clustering gerarchico è spesso visualizzato gracamente usando un dia-gramma simile a quello ad albero, detto dendrodia-gramma, che mostra la relazio-ne cluster/sottocluster e l'ordirelazio-ne con il quale i cluster sono stati uniti (vista agglomerativa) o divisi (vista divisiva). Per insiemi di punti bidimensionali, un cluster gerarchico può essere rappresentato anche usando un diagramma nidicato di cluster. La Figura 1.3 mostra questi due tipi di rappresentazio-ni per un insieme di quattro punti bidimensionali. Questi punti sono stati clusterizzati usando la tecnica single-link descritta successivamente.

1.4.1 Algoritmo base di un cluster gerarchico

agglome-rativo

Molte tecniche di clustering gerarchico agglomerativo sono varianti di un comune approccio: si parte da cluster formati da punti individuali e succes-sivamente si uniscono i cluster più vicini (simili) nché non otteniamo un singolo cluster. Questo approccio è espresso più formalmente nell'Algoritmo 1.1

(10)

Figura 1.3: Un clustering gerarchico di quattro punti mostrato come un Dendrogramma e un Nested cluster diagram

Algorithm 1.1 Algoritmo base di un cluster gerarchico agglomerativo 1 : Calcola l a matrice di prossimità , se n e c e s s a r i o . 2 : repeat

3 : Unisci i due c l u s t e r più v i c i n i .

4 : Aggiorna l a matrice di p r o s s i m i t à per r i f l e t t e r e l a p r o s s i m i t à f r a i nuovi c l u s t e r e q u e l l i

o r i g i n a l i .

5 : until Rimane s o l o un c l u s t e r .

Questo approccio al clustering fa riferimento ad una collezione di tecniche strettamente collegate che produce un clustering gerarchico partendo con ogni oggetto in un proprio cluster e poi raggruppando ripetutamente i due cluster più vicini in modo da ottenere un nuovo cluster ed iterando il procedimento nché si ottiene il numero di cluster desiderati (k-partitioning) oppure si è raggiunta una ssata soglia di distanza fra elementi del cluster (distance-partitioning). Alcune di queste tecniche hanno una naturale interpretazione in termini di graph-based clustering mentre altre hanno un'interpretazione in termini di prototype-based clustering.

(11)

Denizione di Prossimità fra Clusters

L'operazione chiave dell'Algoritmo 1.1 è il calcolo della prossimità fra due clusters; la denizione della prossimità tra cluster dierenzia le varie tecni-che di clustering gerarchico. La prossimità fra cluster è tipicamente denita avendo in mente un determinato tipo di cluster - vedi Sezione 1.3. Per esem-pio, molte tecniche di clustering gerarchico agglomerativo, come MIN, MAX e AVG, derivano dalla vista basata su grafo dei clusters. MIN denisce la prossimità fra cluster come la prossimità fra i due punti più vicini apparte-nenti a due cluster dierenti, o utilizzando la terminologia dei gra, il più corto arco fra due nodi in dierenti sottoinsiemi di nodi; questo produce un clusters basato su contiguità come quello mostrato in Figura 1.2(c). Alter-nativamente, MAX considera la prossimità fra i due punti più distanti in dierenti clusters come prossimità, o usando la terminologia dei gra, il più lungo arco fra due nodi in dierenti sottoinsiemi di nodi. (Se i valori per il calcolo della prossimità sono distanze, allora i nomi, MIN e MAX, sono brevi e suggestivi. Per similarità, tuttavia, dove i valori alti indicano punti più vicini, il nome sembra essere invertito. Per queste ragioni, è preferibile utilizzare i nomi alternativi, single link e complete link, rispettivamente.) Un altro approccio basato sui gra, la tecnica group average, denisce la prossimità fra cluster come la prossimità media (lunghezza media degli ar-chi) fra tutte le coppie di punti appartenenti a cluster diversi. La Figura 1.4 mostra questi tre approcci.

Figura 1.4: Denizione di prossimità basata su gra

Se, invece, prendiamo in considerazione una vista basata su prototipo, nella quale ogni cluster è rappresentato da un centroide, dierenti denizioni di prossimità fra cluster sono più naturali. Quando usiamo i centroidi, la prossi-mità fra cluster è comunemente denita come la prossiprossi-mità fra i centroidi del cluster. Una tecnica alternativa, il metodo di Ward, assume che un cluster è rappresentato da un centroide ma misura la prossimità fra due clusters in termini di incremento nella scarto quadratico risultante dall'unione dei due cluster. Il metodo di Ward tenta di minimizzare la somma del quadrato delle distanze di punti dei centroidi dei cluster.

(12)

CAPITOLO 1. CLUSTERING ALGORITHM 12 Complessità spaziale e temporale

L'algoritmo base di clustering gerarchico agglomerativo (Algoritmo 1.1) uti-lizza una matrice di prossimità. La matrice richiede la memorizzazione di

1 2m

2 prossimità (assumendo che la matrice di prossimità sia simmetrica)

do-ve m indica il numero di punti. Lo spazio necessario per tenere traccia dei clusters è proporzionale al numero di clusters, che è m − 1, escludendo i clu-ster composti da un solo elemento (singleton). Quindi la complessità spaziale totale è O(m2₎_.

L'analisi dell'algoritmo base di clustering gerarchico agglomerativo è sem-plice rispetto alla complessità computazionale. O(m2₎ di tempo è richiesto

per calcolare la matrice di prossimità. Dopo questo passo, ci sono m − 1 iterazioni che coinvolgono i passi 3 e 4 poiché inizialmente ci sono m cluster e due cluster sono uniti ad ogni iterazione. Se eseguiamo una ricerca lineare della matrice di prossimità, allora per la iesima _{iterazione, il passo 3 richiede}

un tempo di O((m − i + 1)2₎_{, che è proporzionale al quadrato del numero}

corrente di clusters. Il passo 4 richiede solamente un tempo di O(m − i + 1) per aggiornare la matrice di prossimità dopo l'unione dei due clusters. (L'u-nione di due clusters coinvolge solo O(m − i + 1) prossimità per la tecnica che abbiamo considerato). Senza ulteriori modiche, queste valutazioni per-mettono di ottenere una complessità temporale di O(m3)_{. Se le distanze fra}

ogni cluster e tutti gli altri sono memorizzati in una lista ordinata (o heap) è possibile ridurre il costo di trovare i due clusters più vicini a O(m − i + 1). Tuttavia, poiché è necessaria una complessità aggiuntiva per le operazioni sulla lista ordinata o sull'heap, il tempo totale richiesto per l'algoritmo base di clustering gerarchico (Algoritmo 1.1) è O(m2_{log m)}. La complessità in

termini di spazio e tempo del clustering gerarchico limita pesantemente la dimensione dei dataset che possono essere processati.

1.4.2 Tecniche speciche

1.4.2.1 Dataset di esempio

Per illustrare il comportamento dei vari algoritmi di clustering gerarchico, utilizziamo un semplice dataset composto da 6 punti bidimensionali, mostrati in Figura 1.5 a). Le coordinate x e y dei punti e le distanze euclidee fra di loro sono mostrate rispettivamente in Figura 1.5 b) e in Figura 1.5 c).

(13)

Figura 1.5: Dataset di esempio 1.4.2.2 Single Link o MIN

Per la versione Single Link o MIN del clustering gerarchico, la prossimità fra clusters è denita come il minimo della distanza (massimo della similarità) fra ogni coppia di punti appartenenti a due dierenti clusters. Usando la terminologia dei gra, se partiamo da una situazione in cui tutti i punti costituiscono cluster di singoli elementi (singleton) e aggiungendo un link fra due punti alla volta, a partire da quelli più corti, allora questi link singoli aggregano i punti in cluster. Il metodo del single link funziona bene con forme non ellittiche ma è sensibile al rumore e agli outliers.

La Figura 1.6 mostra il risultato di applicare la tecnica del single link al dataset di esempio. La Figura 1.6 (a) mostra i cluster come una sequenza di ellissi annidiate, dove i numeri associati con le ellissi indica l'ordine del clustering. La Figura 1.6 (b) mostra le stesse informazioni ma come den-drogramma. L'altezza alla quale due clusters sono uniti nel dendrogramma

(14)

CAPITOLO 1. CLUSTERING ALGORITHM 14 riette la distanza dei due clusters. Per esempio, dalla Figura 1.5, possiamo notare che la distanza tra i punti 3 e 6 è 0.11, che è anche l'altezza alla quale i due cluster vengono uniti nel dendrogramma; per fare un altro esempio la distanza fra i cluster {3, 6} e {2, 5} è data da:

Figura 1.6: Single Link clustering del dataset di esempio di Figura 1.5 dist({3, 6}, {2, 5}) = min(dist(3, 2), dist(6, 2), dist(3, 5), dist(6, 5))

= min(0.15, 0.25, 0.28, 0.39) = 0.15

1.4.2.3 Complete Link o MAX o CLIQUE

Per la versione Complete Link o MAX del clustering gerarchico, la prossimità fra due cluster è denita come il massimo della distanza (minimo della similarità) fra ogni coppia di punti appartenenti a due dierenti clusters. Usando la terminologia dei gra, se partiamo da una situazione in cui tutti i punti costituiscono cluster di singoli elementi (singleton) e aggiungendo un link fra due punti alla volta, a partire da quelli più corti, allora un gruppo di punti non diventa un cluster nché tutti i punti in esso non sono linkati, ossia formano una clique. Il metodo del complete link è meno sensibile al rumore e agli outliers ma potrebbe dividere grandi cluster e favorisce la formazione di cluster di forma globulare.

La Figura 1.7 mostra il risultato di applicare la tecnica del complete link al dataset di esempio. Come nel single link, i punti 3 e 6 sono uniti per primi, tuttavia successivamente {3, 6} è unito a {4} invece di {2, 5} o {1}, poiché:

(15)

Figura 1.7: Complete Link clustering del dataset di esempio di Figura 1.5 dist({3, 6}, {4}) = max(dist(3, 4), dist(6, 4))

= max(0.15, 0.22) = 0.22

dist({3, 6}, {2, 5}) = max(dist(3, 2), dist(6, 2), dist(3, 5), dist(6, 5)) = max(0.15, 0.25, 0.28, 0.39)

= 0.39

dist({3, 6}, {1}) = max(dist(3, 1), dist(6, 1)) = max(0.22, 0.23)

= 0.23

1.4.2.4 Group Average

Per la versione Group Average del clustering gerarchico, la prossimità fra due cluster è denita come la prossimità media fra tutte le coppie di punti appartenenti a due dierenti clusters. Questo è un approccio intermedio fra la tecnica del single e del complete link clustering. Per il group average, quindi, la prossimità fra due cluster è espressa dalla seguente equazione:

proximity(Ci, Cj) = P xCi xCjproximity(x,y) mi∗ mj dove:

(16)

La Figura 1.8 mostra il risultato di applicare la tecnica del group average al dataset di esempio. Per illustrare il funzionamento del group average, calcoliamo la distanza tra alcuni cluster:

Figura 1.8: Group Average clustering del dataset di esempio di Figura 1.5 dist({3, 6, 4}, {1}) = (0.22 + 0.37 + 0.23)/(3 ∗ 1) = 0.28 dist({2, 5}, {1}) = (0.2357 + 0.3421)/(2 ∗ 1) = 0.2889 dist({3, 6, 4}, {2, 5}) = (0.15 + 0.28 + 0.25 + 0.39 + 0.20 + 0.29)/(6 ∗ 2) = 0.26

Poiché dist({3, 6, 4}, {2, 5}) è più piccola di dist({3, 6, 4}, {1}) e dist({2, 5}, {1}), i cluster {3, 6, 4} e {2, 5} sono uniti al quarto passo.

1.4.2.5 Metodo di Ward e Metodo dei Centroidi

Per il metodo di Ward, la prossimità fra due clusters è denita come l'in-cremento nello scarto quadratico che risulta dall'unione di due clusters. Questo metodo utilizza la stessa funzione obiettivo del K-means clustering. Potrebbe sembrare che questa caratteristica renda il metodo di Ward alquan-to dierente rispetalquan-to alle altre tecniche di clustering gerarchico ma invece, può essere dimostrato matematicamente che il metodo di Ward è molto si-mile al metodo del group average quando come prossimità fra due punti si considera il quadrato della distanza che li separa.

(17)

La Figura 1.9 mostra il risultato di applicare il metodo di Ward al dataset di esempio. Il clustering risultante è dierente da quello prodotto dal single link, complete link e group average. I metodi dei Centroidi determinano la prossimità fra due clusters calcolando la distanza fra i centroidi dei clusters. Queste tecniche potrebbero sembrare simili al K-means, ma come abbiamo sottolineato, il metodo di Ward è l'esatto analogo del gerarchico. I metodi dei Centroidi hanno anche una caratteristica - spesso considerata negativa - che non ha nessun'altra tecnica di clustering gerarchico fra quelle che abbiamo discusso: la possibilità di inversione. Più precisamente, gli elementi di due cluster che sono stati uniti potrebbero essere più simili (meno distanti) agli elementi presenti in altri cluster piuttosto che a quelli che hanno portato all'unione al passo precedente. Per gli altri metodi, la distanza fra i cluster uniti, incrementa monotonicamente (o nel caso peggiore, non incrementa) passando dai singleton ad un cluster che raggruppa tutti i punti.

Figura 1.9: Ward's clustering del dataset di esempio di Figura 1.5

1.4.3 La formula di Lance-Williams per la prossimità

fra cluster

Ciascuna delle misure di prossimità fra cluster che abbiamo discusso in que-sta sezione può essere vique-sta come una scelta di dierenti parametri (nella formula di Lance-Williams mostrata sotto nell'equazione 1.1) per la prossi-mità fra i clusters Q e R, dove R è ottenuto unendo i cluster A e B. In questa equazione, p è la funzione di prossimità, mentre mA, mB e mQrappresentano

rispettivamente il numero di punti dei cluster A, B e Q. In altre parole, dopo aver messo insieme i cluster A e B per formare il cluster R, la prossimità fra il nuovo cluster R e un generico cluster Q, è una funzione lineare della

(18)

Tabella 1.1: Tabella dei coecienti di Lance-Williams per comuni approcci di clustering gerarchico

prossimità di Q rispetto ai cluster originali A e B. La Tabella 1.1 mostra il valore dei coecienti per le tecniche che abbiamo discusso.

p(R, Q) = αAp(A, Q) + αBp(B, Q) + βp(A, B) + γ|p(A, B) − p(B, Q)| (1.1)

Ogni tecnica di clustering gerarchico può essere espressa usando la formula di Lance-Williams, non è necessario avere i punti originali. Invece, la matrice di prossimità è aggiornata ogni volta che si determina un nuovo cluster. Mentre la formula generale è utile, specialmente per l'implementazione, osservando direttamente la denizione di prossimità fra cluster utilizzata da ogni metodo, è facile comprendere i dierenti metodi di clustering.

1.4.4 Punti chiave del Clustering Gerarchico

Mancanza di una Funzione Obiettivo globale Il clustering gerarchi-co agglomerativo non può essere visto gerarchi-come l'ottimizzazione di una funzione obiettivo globale, invece, le varie tecniche utilizzano diversi criteri per deci-dere localmente, ad ogni passo, che cluster deve essere unito (o diviso per l'approccio divisivo). Questo approccio permette agli algoritmi di clustering di evitare di risolvere un dicile problema di ottimizzazione combinatoria. E' possibile mostrare come il problema generale di clustering per una funzio-ne obiettivo come "minimizzare lo scarto quadratico" è computazionalmente non fattibile. Inoltre, tale approccio non ha problemi di minimi locali o dif-coltà nella scelta dei punti iniziali. Certamente la complessità temporale di O(m2log m)e la complessità spaziale di O(m2)in molti casi sono proibitive. Capacità di trattare Cluster di dierenti dimensioni Un aspetto del clustering gerarchico agglomerativo che non è stato ancora trattato è quello

(19)

relativo alla dimensione dei cluster ottenuti in seguito ad un'unione. Questa discussione riguarda solo gli schemi di prossimità fra cluster che coinvolgono somme, come il metodo dei Centroidi, il metodo di Ward e il Group Average). Ci sono due approcci: pesato, che tratta ugualmente tutti i cluster indipen-dentemente dal numero di punti che contengono e non pesato che considera il numero di punti di ogni cluster (si noti che la terminologia pesato e non pesato è riferita ai punti, non ai clusters). In altre parole, trattare i cluster di diverse dimensioni nello stesso modo dà dierenti pesi ai punti nel cluster, mentre se consideriamo la dimensione dei cluster si dà ai punti di dierenti cluster lo stesso peso.

Illustreremo quanto sopra usando la tecnica discussa nella Sezione 1.4.2.4, ossia la versione non pesata della tecnica di group average. Nella letteratura del clustering, il nome esteso di questo approccio è Unweighted Pair Group Method using Arithmetic averages (UPGMA). Nella Tabella 1.1, che dà la formula per aggiornare la similarità fra cluster, il coeciente per UPGMA è relativo alla dimensione di ogni cluster che sono stati uniti: αA = _mmA

A+mB,

αB = _mmB

A+mB, β = 0, γ = 0. Per la versione pesata del group average

-conosciuta come Weighted Pair Group Method using Arithmetic averages (WPGMA) - i coecienti sono costanti: αA = 1/2, αB = 1/2, β = 0, γ = 0.

In generale, l'approccio non pesato è preferibile a meno che non ci siano ragioni per credere che i punti individuali debbano avere pesi dierenti, ad esempio magari le classi di oggetti sono state campionate in maniera non uniforme.

Come unire i cluster: una scelta denitiva Gli algoritmi di cluste-ring gerarchico agglomerativo tendono a prendere buone decisioni locali su quali cluster è meglio unire in quanto usano informazioni sulla similarità fra coppie di punti; tuttavia, una volta presa la decisione di unire due cluster, successivamente non può più essere disfatta. Questo approccio permette di non far diventare il criterio locale di ottimizzazione un criterio globale. Per esempio, sebbene il criterio della "minimizzazione degli scarti quadratici" del K-means sia usato per decidere quale cluster unire nel metodo di Ward, i clu-sters ad ogni livello non rappresentano un minimo locale rispetto alla scarto quadratico totale. I cluster, invece, non sono sempre stabili, nel senso che un punto nel cluster potrebbe essere più vicino al centroide di uno degli altri cluster rispetto al centroide del cluster corrente. Comunque, il metodo di Ward è spesso usato come un metodo robusto per inizializzare un K-means clustering, questo sta ad indicare che la minimizzazione degli scarti quadra-tici locali della funzione obiettivo non è connessa con la minimizzazione degli scarti quadratici globali della funzione obiettivo.

(20)

CAPITOLO 1. CLUSTERING ALGORITHM 20 Ci sono delle tecniche che tentano di superare le limitazioni della scelta de-nitiva dell'unione. Un approccio tenta di aggiustare il clustering gerarchico muovendo rami degli alberi da una parte all'altra così da aumentare la fun-zione obiettivo globale. Un altro approccio usa una tecnica di clustering partitiva come K-means per creare un numero elevato di piccoli cluster a partire dai quali poi eseguire il clustering gerarchico.

1.4.5 Punti di forza e di debolezza

I punti di forza e di debolezza specici per ogni algoritmo di clustering ge-rarchico agglomerativo sono già stati descritti precedentemente. In generale, questi algoritmi sono usati tipicamente perché c'è un'applicazione sottostan-te, infatti la creazione di una tassonomia richiede una gerarchia. Ci sono stati, inoltre, degli studi che indicano che questi algoritmi producono clusters di qualità migliore rispetto agli altri algoritmi. Tuttavia, gli algoritmi di clu-stering gerarchici agglomerativi sono costosi in termini di requisiti di tempo e di spazio. Il fatto che l'unione fra cluster sia denitiva può creare problemi con il rumore in dati con un'elevata dimensionalità, come nei documenti. A sua volta, questi due problemi possono essere arontati clusterizzando prima parzialmente i dati utilizzando altre tecniche, come il K-means.

1.4.6 Libreria LingPipe

Come implementazione dell'algoritmo di Clustering Gerarchico abbiamo uti-lizzato la libreria lingpipe-4.0.1 [?]. La libreria consente di utilizzare due al-goritmi di agglomerative clustering: Single-Linkage e Complete-Linkage. A partire dal dendrogramma, generato dal clustering gerarchico tramite uno dei due algoritmi sopra citati, si applica il metodo partitionDistance(maxDistance) che permette di suddividere le partizioni tagliando il dendrogramma ad una determinata altezza. Il parametro maxDistance indica la soglia utilizzata per eettuare il taglio. E' stata eseguita un'analisi statistica, a partire dal graco ottenuto ordinando le distanze in ordine crescente, che ci ha permes-so di determinare l'altezza (permes-soglia) adeguata per eettuare il taglio. Tale soglia è stata quindi a sua volta utilizzata tramite il metodo partitionDistan-ce(maxDistance) per l'esecuzione degli algoritmi di Single e Complete-Link Clustering.

(21)

1.5 OPTICS: Ordering Points To Identify

Clu-stering Structure

OPTICS[?] è un algoritmo per individuare cluster in dataset spaziali ba-sandosi sulla densità. E' stato presentato da Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel and Jörg Sander. L'idea è simile a DBSCAN [?], ma aronta uno dei principali svantaggi di DBSCAN: il problema di individuare clusters signicativi in dataset di dierenti densità. A tal ne gli elementi del dataset vengono linearmente ordinati in modo che gli ele-menti che sono spazialmente i più vicini risulteranno a poca distanza anche nell'ordinamento. Inoltre per ogni elemento viene memorizzata una speciale distanza (core-distance) che rappresenta la densità necessaria per un cluster per avere entrambi gli elementi nello stesso cluster.

OPTICS non produce esplicitamente un clustering del dataset ma invece crea un ordinamento incrementale del dataset in modo da rappresentare la strut-tura del clustering sulla base della densità. Molte ricerche sul clustering sono volte ad incrementare l'ecienza degli algoritmi, ma un problema più serio, invece, è migliorare l'ecacia, ossia la qualità e l'utilità dei risultati. Ci sono tre ragioni connesse fra di loro per cui l'ecacia nel clustering è un pro-blema: Primo, sebbene tutti gli algoritmi di clustering richiedano valori da utilizzare come parametri d'ingresso, questi risultano dicili da determinare, specialmente per dataset reali contenenti oggetti con un'alta dimensionali-tà. Secondo, gli algoritmi sono molto sensibili al valore di questi parametri, spesso producendo partizioni totalmente dierenti cambiando leggermente il valore di tali parametri. Terzo, i dataset reali spesso hanno una distribuzione veramente complessa che non può essere ottenuta dagli algoritmi di clustering semplicemente variando globalmente il valore dei parametri di input.

(22)

1.5.1 Verso il Clustering basato su densità

Una importante proprietà di molti dataset reali è che la loro intrinseca strut-tura di cluster non può essere caratterizzata da un parametro di densità globale. Valori di densità locale molto diversi potrebbero essere necessari per individuare i cluster in dierenti regioni dello spazio dei dati. Per esempio nel dataset mostrato in Figura 1.10 non è possibile rilevare i cluster A, B, C1, C2

e C3 simultaneamente usando un parametro di densità globale. Una

decom-posizione globale basata sulla densità sarebbe dovuta essere composta dai cluster A, B, C oppure da C1, C2, C3; in quest'ultimo caso gli oggetti di A e

B sarebbero considerati rumore.

Il primo modo per individuare ed analizzare tale struttura di clustering è usando un clustering gerarchico, per esempio usando il metodo single-link. In questo caso ho però due svantaggi: primo il clustering subisce considera-bilmente l'eetto del single-link, ossia il fatto che i clusters connessi da una linea formata da pochi punti hanno una bassa inter-object distance e quindi non sono separati; secondo il risultato prodotto dagli algoritmi di clustering gerarchico, cioè il dendrogramma, sono dicili da capire ed analizzare per più di poche centinaia di elementi. Ora il primo problema potrebbe esse-re risolto adottando un altro metodo di linking come il complete-linking o l'average-linking; mentre il secondo è un problema intrinseco degli algoritmi di clustering gerarchico che forniscono come output un dendrogramma. Un secondo metodo per eettuare il clustering è quello di usare un algoritmo di partizionamento basato su densità con dierenti settaggi dei parametri. Tuttavia, c'è un innito numero di possibili setting dei valori dei parametri. Anche se usassimo un grande numero di valori dierenti, che richiederebbe altresì un sacco di memoria per memorizzare l'appartenenza dei vari elementi ai cluster individuati, non è ovvio come poter analizzare i risultati ottenuti e con il rischio di non individuare alcuni livelli interessanti per il clustering. L'idea di fondo per superare questi problemi è utilizzare un algoritmo che produce uno speciale ordine (da qui Ordering) degli elementi rispetto alla struttura, basata sulla densità, del clustering. Questo ordinamento ci per-mette di avere delle informazioni per ogni livello di clustering del dataset no ad una certa distanza di generazione e nello stesso tempo risultando facile da analizzare.

(23)

Figura 1.10: Clusters rispetto a dierenti parametri di densità

1.5.2 Clustering basato su densità

L'idea principale su cui si fonda il clustering basato su densità è che per ogni elemento di un cluster, il proprio vicinato a distanza , deve contenere alme-no MinPts elementi, ossia la cardinalità dell'insieme costituito dal vicinato (a distanza dal cluster) deve superare una certa soglia MinPts. Adesso in-troduco brevemente la notazione per caratterizzare formalmente questa idea (per una presentazione più dettagliata vedere [?]).

Denizione 1: (direttamente raggiungibile per densità)

Un oggetto p è direttamente raggiungibile per densità da un oggetto q ri-spetto a ed a MinPts in un insieme di oggetti D se

1. p ∈ N∈(q) (N∈(q)è il sottoinsieme di D contenuto nel -vicinato di

q)

2. Card(N∈(q) ≥ M inP ts (Card(N ) denota la cardinalità

dell'insie-me N )

La condizione Card(N∈(q) ≥ M inP ts è chiamata "core object condition".

Se questa condizione è vericata per un oggetto p, allora noi chiamiamo p "core object". Solo a partire da core object, altri oggetti possono essere direttamente raggiungibili per densità.

Denizione 2: (raggiungibile per densità)

Un oggetto p è raggiungibile per densità da un oggetto q rispetto a e MinPts in un insieme di oggetti D se c'è una catena di oggetti p1, ..., pn, p1 = q, pn = p

tale che pi∈D e pi+1 è direttamente raggiungibile per densità da pi rispetto

a e MinPts. La raggiungibilità per densità è la chiusura transitiva del-la raggiungibilità diretta per densità. Questa redel-lazione in generale non è

(24)

Figura 1.11: Density-reachability e density-connectivity

simmetrica. Solo i core-object possono essere mutuamente raggiungibili per densità.

Denizione 3: (connesso per densità)

Un oggetto p è connesso per densità da un oggetto q rispetto a e MinPts in un insieme di oggetti D se c'è un oggetto o∈D tale che sia p che q sono raggiungibili per densità da o rispetto a e MinPts in D. La connessione per densità è una relazione simmetrica. La Figura 1.11 illustra la denizione su un semplice database di punti bidimensionali di uno spazio vettoriale. Da notare che la denizione sopra richieda solamente una misura di distanza e può essere applicata a dati di uno spazio metrico. Un cluster basato su densità è adesso denito come un insieme di oggetti connessi per densità che è massimo rispetto alla raggiungibilità per densità e il rumore (noise) è l'insieme di oggetti che non sono contenuti in alcun cluster.

Denizione 4: (cluster and noise)

Sia D un insieme di oggetti. Un cluster C rispetto ae MinPts per D è un sottoinsieme non vuoto di D che soddisfa le seguenti condizioni:

1. Massimalità: ∀p, q ∈ D : se p ∈ C e q è raggiungibile per densità da p rispetto a e MinPts, allora anche q ∈ C.

2. Connettività: ∀p, q ∈ C : p è connesso per densità a q rispetto a e MinPts in D.

Ogni oggetto non contenuto in alcun cluster è detto rumore (noise).

Da notare che un cluster non contiene solo core object ma anche oggetti che non soddisfano la "core object condition". Tali oggetti, sono chiamati "border objects" del cluster e sono, tuttavia, direttamente raggiungibili per

(25)

densità da almeno un core object (contrariamente ai noise object (rumore)). L'algoritmo [?], che individua i cluster e il rumore in un database secondo le denizioni sopra, è basato sul fatto che un cluster è equivalente all'insieme di tutti gli oggetti in D che sono raggiungibili per densità a partire da un arbitrario core object nel cluster (cfr. lemma 1 e 2 in [?]). L'individuazione di oggetti raggiungibili per densità è eettuata iterativamente collezionando gli oggetti raggiungibili direttamente per densità. DBSCAN controlla i -vicinato di ogni punto del database. Se il --vicinato N(p) di un punto p

ha più di di MinPts punti, viene creato un nuovo cluster C contenente gli oggetti in N(p). Poi, si controlla il -vicinato di tutti i punti q in C che non

sono stati ancora processati; se N(q) contiene più di MinPts punti, i vicini

di q che non sono già contenuti in C sono aggiunti al cluster e nel passo successivo si controlla il loro -vicinato. Questa procedura è ripetuta nché nessun nuovo punto può essere aggiunto al cluster corrente C.

(26)

1.5.3 Ordinamento dei cluster basato sulla densità

Prima di introdurre la nozione di ordinamento dei cluster basato sulla den-sità, facciamo la seguente osservazione: per un valore costante di MinPts, i cluster con un alto valore di densità (corrispondenti a bassi valori di ) sono completamente contenuti in insiemi connessi per densità rispetto a quelli con bassi valori di densità (relativi ad alti valori di ). Quanto detto è illustrato in Figura 1.12, dove C1e C2 sono cluster basati su densità rispetto a 2 < 1

e C è un cluster basato su densità rispetto a 1 che contiene completamente

gli insiemi C1 e C2.

Figura 1.12: Cluster "nidicati" basati su densità

Conseguentemente, è possibile estendere l'algoritmo DBSCAN in modo da costruire simultaneamente i cluster per diversi valori di densità. Per produrre un risultato consistente, tuttavia, vogliamo considerare un determinato or-dine nel quale processare gli oggetti quando espandiamo il cluster.Vogliamo selezionare sempre un oggetto che è raggiungibile per densità rispetto al più basso valore di per garantire che i cluster con più alta densità (cioè con valore di più bassi) siano generati per primi.

OPTICS lavora in principio come un'estensione dell'algoritmo DBSCAN per un innito numero di valori di distanza i che sono più bassi di un "distanza

di generazione" (cioè 0 ≤ i ≤ ). La sola dierenza è che non vengono

assegnati gli oggetti ai cluster; invece, viene memorizzato l'ordine con il quale gli oggetti vengono processati e le informazioni che potrebbero essere usate da un estensione dell'algoritmo di DBSCAN per assegnare gli oggetti ai cluster (se tutto questo fosse possibile per un innito numero di parametri). Questa informazione è costituita da solo due valori per ogni oggetto: la core-distance e la reachability-distance, introdotte nelle seguenti denizioni.

(27)

Sia p un oggetto di un database D, sia un valore di distanza, sia N(p) il

- vicinato di p, sia MinPts un numero naturale e sia MinPts-distance(p) la distanza fra p e i suoi MinPts vicini. Allora, la core-distance(p) è denita come la core − distance,M inP ts(p) =

(

IN DEF IN IT A se Card(N(p)) < M inP ts

M inP ts − distance(p) altrimenti

La core-distance di un oggetto p è semplicemente la più piccola distanza 0

fra p e un oggetto del suo - vicinato tale che p sia un core-object rispetto a 0 _{se i suoi vicini sono contenuti in N}

(p); altrimenti la core-distance non è

denita.

Denizione 6: (reachability-distance di un oggetto p rispetto ad un oggetto o)

Siano p e o oggetti di un database D, sia N(o)il - vicinato di o, e sia MinPts

un numero naturale; allora la reachability-distance di p rispetto a o è denita come la reachability − distance,M inP ts(p, o) =

(

IN DEF IN IT A se Card(N(o)) < M inP ts

max(core − distance(o), distance(o, p)) altrimenti

Intuitivamente, la reachability-distance di un oggetto p rispetto ad un altro oggetto o è la più piccola distanza tale che p è direttamente raggiungibile per densità da o se o è un core object. In questo caso, la reachability-distance non può essere più piccola della core-distance di o poiché per piccole distanze nessun oggetto è direttamente raggiungibile per densità da o. Altrimenti, se o non è un core object, sempre considerando la distanza di generazione , la reachability-distance di p rispetto a o è indenita. La reachability-distance di un oggetto p dipende dal core object rispetto alla quale viene calcolata. La Figura 1.13 mostra la nozione di core-distance e di reachability-distance. L'algoritmo OPTICS crea un ordinamento del database, memorizzando inol-tre la core-distance e la reachability-distance per ogni oggetto; queste infor-mazioni sono sucienti per individuare tutti i cluster basati sulla distanza rispetto ad ogni distanza 0 _{che è inferiore alla distanza di generazione di}

quel dato ordinamento.

(28)

Figura 1.13: Core-distance(o), reachability-distances r(p1, o), r(p2, o) for

MinPts=4

Sia DB una database contenente n punti. L'algoritmo OPTICS genera un ordinamento dei punti o : 1..n → DB e il corrispondente valore di reachability-distance r : {1..n} → R≥0.