Appunti di Data Mining

5.1.6 Edit Distance

L'Edit Distance tra la stringa X e la stringa Y di differenti dimensioni è definita come il numero minimo di operazioni di base che convertono X in Y. Tali operazioni base sono l'inserimento di un carattere, la rimozione di un carattere, la sostituzione di un carattere e altre operazioni simili.

In particolare, dato il costo c[i, j] di convertire il carattere X[i] nel carattere Y[j], allora possiamo definire la seguente formulazione ricorsiva:

• c[i, j] = c[i-1, j-1] + cost(copy) se X[i] = Y[j]
• c[i, j] = c[i-1, j-1] + cost(replace) se X[i] ≠ Y[j]
• c[i, j] = min(c[i-2, j-2] + 2, c[i-1, j-1] + 1, c[i, j-1] + cost(insert), c[i-1, j] + cost(delete)]) sempre

CLUSTERING 485.2 Algoritmi di Clustering

5.2.1 Hierarchical Clustering

Gli algoritmi di Clustering gerarchici producono un insieme di cluster annidati organizzati in un dendrogramma, ovvero un albero che registra le sequenze di fusioni o scissioni. Il vantaggio del Clustering gerarchico è che non deve essere definito un numero di cluster a priori. In particolare possiamo ottenere un qualsiasi numero desiderato di cluster tagliando il dendrogramma al livello opportuno.

Distinguiamo due diverse classi di algoritmi di Clustering gerarchici a seconda della tecnica utilizzata per costruire le gerarchie:

• Agglomerativi: (metodo bottom-up) inizialmente si considera ogni punto del dataset come un cluster. Ad ogni passo si aggregano i due punti più vicini.
• Divisivi: (metodo top-down) inizialmente si considera un unico cluster rappresentato dall'intero dataset. Ad ogni passo si divide il cluster per i punti più distanti.

Particolare concentriamoci sugli algoritmi di Clustering gerarchici agglomerativi. L'idea è quella di unire successivamente i cluster più vicini (perciò dobbiamo definire una misura di vicinanza tra i cluster). Possiamo definire l'algoritmo nel seguente modo:

Algorithm 3 Clustering k-Means

1. Compute the proximity matrix.
2. Let each data point be a cluster.
3. repeat
4. Merge the two closest clusters.
5. Update the proximity matrix.
6. until only a single cluster remains.

CAPITOLO 5. CLUSTERING 49

Per calcolare la distanza tra due cluster possiamo utilizzare diverse misure:

• MIN (Single Link): rappresenta la distanza minima tra due punti appartenenti a due diversi cluster. Perciò, la vicinanza di due cluster si basa sui due punti più vicini nei diversi cluster. Questa soluzione permette di gestire forme non ellittiche ma è sensibile al rumore.
• MAX (Complete Link): rappresenta la distanza massima tra due punti appartenenti a due

CAPITOLO 5. CLUSTERING 50

Consideriamo il seguente dataset costituito da punti rappresentati nello spazio Euclideo e con la corrispondente matrice di prossimità:

Vediamo come viene costruita la gerarchia secondo le diverse tecniche di misura di prossimità tra i cluster:

• MIN:
• MAX:
• Group Average:

CAPITOLO 5. CLUSTERING 51

La complessità degli algoritmi di Clustering gerarchici è (spaziale) O(n^2) per creare la matrice di prossimità, dove n è il numero di punti nel dataset, ed (temporale) O(n^3) poiché ci sono passi e ad ogni passo la matrice di prossimità di dimensione 2n deve essere aggiornata. Perciò il costo è elevato, quindi questi algoritmi sono inefficienti per dataset di grandi dimensioni.

Nel caso in cui i punti dati siano definiti su uno spazio Euclideo, allora il

è detto (cioè i punti vengono rappresentati dal punto del cluster piùvicino a tutti i punti). Per determinare la vicinanza tra i cluster, possiamo trattare ilclusteroide come un centroide.

Il concetto di clusteroide, ovvero di punto più vicino agli altri punti, può essere rappre-sentato in modi diversi:

• Minima distanza massima dagli altri punti.
• Minima distanza media dagli altri punti.
• Minima somma dei quadrati delle distanze dagli altri punti. Ovvero, la metrica didistanza per il clustroide del cluster sarà .2Pmind c C d(x, c)c x∈X

Perciò, il centroide è la media di tutti i punti dati del cluster (ovvero il centroide è unpunto artificiale), mentre il clustroide è un punto dati esistente che è più vicino a tuttigli altri punti del cluster.

CAPITOLO 5. CLUSTERING 52ES:

Consideriamo un dataset costituito dalle seguenti stringhe: abecb, aecdb, ecdab}{abcd,

Allora calcoliamo la distanza

tra i termini attraverso l'Edit Distance (la se-guente matrice è simmetrica):

ecdab abecb aecdbabcd 4 2 2

aecdb 2 2

abecb 4

Allora vediamo come possiamo valutare il clusteroide secondo le diverse tec-niche rappresentate:

Point Max Sum Sum-Square

abcd 4 8 24

aecdb 2 6 16

abecb 4 8 24

ecdab 4 10 36

In ogni caso otteniamo che il migliore clusteroide è la stringa "aecdb" (ovve-ro rappresenta la stringa più vicina a tutte le altre stringhe del cluster).

Durante un algoritmo di Clustering gerarchico, possiamo decidere di interrompere l'unione dei cluster (merge) attraverso diverse tecniche:

• Dopo aver individuato cluster, con valore preimpostato.
• Quando il diametro del cluster supera una certa soglia preimpostata.
• Quando la densità del cluster è inferiore ad una certa soglia.
• Quando la prossima combinazione comporta un peggioramento (ad esempio, quando ad un'iterazione il diametro medio è

significativamente più alto rispetto allaprecedente iterazione).

CAPITOLO 5. CLUSTERING

53ES:Consideriamo un dataset di punti in una{1,= 4, 9, 16, 25, 36, 49, 64, 81}Ddimensione. Eseguiamo l’algoritmo di Clustering gerarchico agglomerativoseguendo differenti approcci:

• Single Link, ovvero la distanza minima tra due cluster. Consideriamoinizialmente i cluster formati dai singoli punti. Quindi calcoliamo lamatrice di prossimità tra i punti (tale matrice è simmetrica, perciò icampi vuoti corrispondono ai valori simmetrici):

Perciò osserviamo che la distanza minima è data dai cluster contenentii punti e Perciò uniamo questi due cluster in un unico cluster1 4.Quindi aggiorniamo la matrice di prossimità, valutando la{1, 4}.distanza minima tra i punti dei cluster (in blu

Sono evidenziati i valori aggiornati). Ad esempio, la distanza tra il cluster ed il cluster{9} sarà che rappresenta la distanza minima tra i due{1, -4} = 9 4 = 5dcluster (rispetto a - = 9 1 = 8):

d1,4 9 16 25 36 49 64 81

1,4 0 5 12 21 32 45 60 77

9 0 7 16 27 40 55 72

16 0 9 20 33 48 65

25 0 11 24 39 56

36 0 13 28 45

49 0 15 32

64 0 17

81 0

Di conseguenza possiamo unire il cluster con il cluster{1, {9},4} ottenendo il cluster poiché è quello con distanza minima.

{1, 4, 9}

CAPITOLO 5. CLUSTERING 54

Quindi otteniamo la seguente matrice di prossimità aggiornata:

1,4,9 16 25 36 49 64 81

1,4,9 0 7 16 27 40 55 72

16 0 9 20 33 48 65

25 0 11 24 39 56

36 0 13 28 45

49 0 15 32

64 0 17

81 0

Perciò il successivo cluster è ottenuto unendo il cluster con il{1, 4, 9} cluster (ovvero{16} {1, 4, 9, 16}).

Proseguendo fino ad ottenere un unico cluster che rappresenta l'intero dataset otteniamo il seguente dendogramma:

• Distance Between Centroid, ovvero i cluster sono