4.9 Analisi comparativa delle prestazioni
5.1.1 Inconvenienti degli algoritmi di clustering tradizionali
Gli algoritmi di clustering esistenti possono essere in prima approssimazione suddivisi in due gruppi:
1. Algoritmi Partizionali
2. Algoritmi Gerarchici
Nei paragrafi5.1.1.1e5.1.1.2descriviamo brevemente in cosa consistano tali metodi e in cosa si distinguano tra loro.
Figura 5.1: Suddivisione indesiderata di un grande cluster, dovuta agli algoritmi partizionali
5.1.1.1 Algoritmi di clustering Partizionali
Gli algoritmi di clustering partizionali si prefiggono lo scopo di determinare k partizioni in modo tale da ottimizzare un determinato criterio funzionale. Ad esempio, uno dei criteri più usati è quello della minimizzazione dell’errore quadratico medio, definito come segue:
E = k X i=1 X p ∈Ci ||p − mi||2
ove Ci è l’i-esimo cluster e mi è il suo punto medio, detto anche centroide. L’errore quadratico medio costituisce una buona valutazione delle variazioni intra-cluster su tutte le partizioni. L’obiettivo è dunque quello di trovare k partizioni che minimizzino l’errore quadratico: ne deduciamo che il clustering basato sul criterio dell’errore quadratico cerca di generare k cluster il più possibile compatti e separati. Il problema risiede nel fatto che tale metodo funziona bene solo se i cluster sono “nuvole” di iperpunti ben definite e ben distanziate le une dalle altre.
Qualora tuttavia vi siano notevoli differenze nelle dimensioni e nella geo- metria dei vari gruppi, come illustrato in figura5.1, pag. 65, il metodo dell’er- rore quadratico medio fornisce molto probabilmente risultati non accurati. Esso tende infatti a spezzare i cluster di dimensioni maggiori, comporta- mento che porta a una riduzione apprezzabile dell’errore quadratico: la lieve riduzione dell’errore dovuta alla divisione dei cluster più grandi è pesata dai molti punti in essi contenuti.
5.1.1.2 Algoritmi di Clustering Gerarchico
Il clustering gerarchico (vedi capitolo 3, pag. 25) è una sequenza di parti- zioni consecutive, nella quale ogni partizione è annidata in quella successiva. Un algoritmo di clustering gerarchico agglomerativo parte da un insieme di cluster disgiunti, ognuno dei quali contiene inizialmente un solo individuo. I gruppi vengono poi fusi (merged) tra loro, finché il numero totale di cluster non si riduce ad un numero k1; a ogni passo, la coppia dei cluster fusi è quella
per cui si ha la distanza minima. Avendo indicato con:
• Ci il cluster i-esimo
• mi il punto medio di Ci
• ni il numero di punti contenuti in Ci
introduciamo di seguito le misure di distanza tra cluster più diffusamente utilizzate: dmean(Ci, Cj) = ||mi− mj|| dave(Ci, Cj) = X p ∈Ci X q ∈Cj ||p − q|| ni nj dmax(Ci, Cj) = max p ∈Ci, q∈Cj ||p − q|| dmin(Ci, Cj) = min p ∈Ci, q ∈Cj ||p − q|| (5.1)
Tali misure di distanza inter-cluster sono abbastanza intuitive: ad esempio, se scegliamo dmeancome misura di distanza, a ogni passo vengono fusi i cluster i cui centroidi sono più vicini; se invece scegliamo dmin vengono fusi i cluster che contengono la coppia di punti più vicini. Le misure di distanza5.1hanno tutte lo scopo di minimizzare la varianza e forniscono gli stessi risultati se i cluster sono compatti e ben separati. Tuttavia se si verifica anche una sola delle seguenti condizioni:
• I cluster sono molto vicini tra loro (magari solo perché collegati da stream di punti singolari o outlier )
• La loro forma non è ipersferica
1k può essere un dato di input dell’algoritmo oppure può essere determinato
Figura 5.2: Suddivisione indesiderata dei cluster, dovuta alla loro forma allungata
• Le loro dimensioni non sono uniformi
allora i risultati del clustering possono variare notevolmente. Infatti, se la forma dei gruppi è allungata, come mostrato in figura5.2, pag. 67, l’utilizzo della misura di distanza dmean causa la divisione dei cluster in questione e la fusione dei sotto-cluster risultanti con porzioni di eventuali classi allungate confinanti.
D’altro canto, se si utilizza la misura di distanza dmean, può accadere che
cluster congiunti da una stretta fila di punti vengano fusi insieme: questo effetto di concatenazione (chaining), per il quale pochi punti si pongono a formare una sorta di ponte tra due cluster causandone l’indesiderato rag- gruppamento in un singolo gruppo, è il principale inconveniente dell’utilizzo della misura di distanza dmin.
Da quanto detto risulta che sia l’approccio centroid-based, basato sull’u- tilizzo di dmean, sia l’approccio a tutti punti, basato sull’utilizzo di dmin, fal- liscono nel caso in cui siano presenti cluster di forma arbitraria e comunque lontana dalla idealità ipersferica. Il punto debole dell’approccio centroid- based risiede nel fatto che esso considera un solo punto rappresentativo per ogni classe; tuttavia per cluster di grandi dimensioni e forma arbitraria è plausibile che i centroidi dei suoi sotto-cluster siano anche molto lontani tra di loro: questo può causare la divisione del cluster.
L’approccio a tutti punti d’altro canto considera tutti i punti all’interno di un cluster come rappresentativi: quest’altro “estremo” presenta l’incon- veniente di rendere l’algoritmo di classificazione estremamente sensibile alla presenza di punti singolari e alle variazioni, se pur minime, nella posizione dei punti rappresentativi dei dati.
5.1.1.3 Algoritmo BIRCH
Quando il numero N di dati in ingresso diventa cospicuo, gli algoritmi di clustering gerarchico cominciano a essere inefficienti, a causa della loro com- plessità computazionale non lineare (tipicamente O(N2)) e degli enormi costi di I/O. E’ per ovviare a questo problema che gli autori di [ZRL96] hanno proposto l’algoritmo di clustering BIRCH, che ha rappresentato fino a poco tempo fa lo strumento “di punta” per il raggruppamento di insiemi di dati di grandi dimensioni.
BIRCH, come abbiamo visto nel capitolo 4, pag. 45, effettua una pre- liminare fase di pre-clustering, durante la quale dense regioni di punti sono rappresentate da compendî (summaries) succinti; al pre-clustering fa segui- to un algoritmo di classificazione centroid-based, che opera sull’insieme dei summaries, molto più ridotto dell’insieme di dati originario. L’algoritmo di pre-clustering, usato da BIRCH per ridurre la dimensione dei dati di input, è incrementale e approssimato. Durante la fase di pre-clustering, l’intero data- base viene scandito e i sommarî dei cluster sono immagazzinati in memoria in una struttura dati denominata CF Tree (albero delle Clustering Feature). Per ogni nuovo punto, il CF Tree viene attraversato, alla ricerca del cluster a esso più vicino. Se la distanza del punto dal gruppo più vicino è inferiore ad una certa soglia, il punto viene assorbito dal cluster, altrimenti esso diventa il generatore di una nuova classe nel CF Tree.
Terminata la fase di clustering, si effettua una fase finale di labeling2,
durante la quale si stabilisce l’appartenenza dei varî punti ai cluster eviden- ziati dall’analisi. Il criterio di assegnamento consiste nell’inserire il punto nel cluster il cui centroide è il più vicino al punto stesso. L’utilizzo di un solo punto rappresentativo (centroide) per i gruppi costituisce il problema di questa fase, nel caso in cui i cluster abbiano dimensioni e forme non omo- genee, come mostrato in figura 5.3, pag. 69. In questa situazione infatti si può manifestare l’assegnamento errato di un certo numero di punti: può accadere che i punti di un grosso cluster vengano erroneamente assegnati ad una classe molto più piccola perché il suo centroide è più vicino.
Figura 5.3: Etichettatura problematica