Sensibilità rispetto al numero di partizioni p

Gli autori di [GRS01] elaborano il data set 1 facendo variare il numero di partizioni p da 1 a 100. Per p < 50 la qualità del clustering rimane pres- soché inalterata, ma per p = 100, ad esempio, la qualità dell’analisi risulta notevolmente degradata.

C’è una correlazione tra il numero di partizioni p ed il parametro q, che stabilisce fino a quando effettuare il clustering della singola partizione (ricor- diamo che la partizione è sottoposta ad analisi finché il numero delle classi rimanenti non è1

q del numero dei cluster originarî della partizione stessa). Per preservare l’integrità del clustering, all’aumentare di q anche la dimensione della partizione deve aumentare e di conseguenza p deve diminuire.

Questo è il motivo per cui, se le dimensioni delle partizioni sono piccole, effettuare un clustering più profondo di ogni partizione può causare la fusione di punti appartenenti a cluster diversi (in quanto ogni partizione contiene un numero più piccolo di punti).

In generale conviene scegliere il numero di partizioni p in modo tale che: s

p q > 2 o 3 volte k.

5.4.4.4 Sensibilità rispetto alla dimensione del campione casuale s

Il data set 1 è stato elaborato dall’algoritmo CURE, utilizzando una dimen- sione del campione casuale variabile da 500 a 5.000 punti. Il risultato è stato che, con un campione casuale di 2.000 punti, si sono ottenuti cluster di qua- lità scadente, ma, già ricorrendo a campioni di dimensione > 2.500 punti (2.5% della dimensione del data set), i cluster sono stati rilevati in modo soddisfacente.

5.4.5

Confronto dei tempi di esecuzione di BIRCH e

CURE

Per confrontare gli algoritmi BIRCH e CURE è stato necessario tenere in considerazione il fatto che BIRCH è un algoritmo di clustering gerarchico centroid-based. Per questo gli autori di [GRS01] hanno eseguito il test sul data set 4, in quanto esso contiene cluster compatti e di dimensioni omoge- nee e viene pertanto analizzato correttamente anche da algoritmi centroid- based quali BIRCH. CURE d’altra parte doveva essere eseguito in modalità centroid-based ed è stato pertanto utilizzato con le seguenti impostazioni:

• Dimensione del campione casuale pari a 2.500

• α = 1 (modalità centroid-based)

• 1 punto rappresentativo per cluster (ovvero il centroide)

• 4 partizioni

La figura 5.10, pag. 99, mostra le performance a confronto di BIRCH e CURE quando il numero di punti varia dal valore iniziale di 100.000 fino al valore finale di 500.000. In figura sono riportati gli andamenti relativi a due diversi valori del numero di partizioni (P = 1, P = 2), in modo da mostrare l’effetto positivo del partizionamento sui tempi di esecuzione. Nel computo

































                   ! " # B i r c h $ % &'( )* + ,-./ 01

Figura 5.10: Tempi di esecuzione di BIRCH e CURE a confronto non è stato considerato il costo della fase di labeling, in quanto essa richiede approssimativamente lo stesso tempo sia per BIRCH che per CURE : infatti entrambi gli algoritmi stanno utilizzando in questo caso solo il centroide del cluster nella fase di etichettatura dei dati. Osservando la figura 5.10, pag.

99, si nota che i tempi di esecuzione di CURE sono sempre inferiori a quelli di BIRCH. Se poi si attiva anche il partizionamento con due partizioni, i tempi di esecuzione di CURE scendono di un ulteriore 50%. Inoltre i tempi di esecu- zione di CURE crescono di poco al crescere del numero di punti, al contrario di quello che accade a BIRCH, il quale deve scansionare l’intero database e utilizza tutti i punti del data set per eseguire il pre-clustering. Concluden- do possiamo affermare che i risultati sperimentali proposti dagli autori di

[GRS01] confermano la loro tesi, ovvero che CURE presenta effettivamente

[Ben75] Jon Louis Bentley. Multidimensional binary search trees used for associated searching. Communications of the ACM, 18(9):509– 517, September 1975.

[CLRS01] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press and McGraw-Hill Book Company, second edition, 2001.

[Cox64] H. S. M. Coxeter. An upper bound for the number of equal nonoverlaping spheres that can touch another of the same size. Symposia in Pure Mathematics, 7:53–71, 1964.

[DECM98] Duch, Estivill-Castro, and Martinez. Randomized K-dimensional binary search trees. In ISAAC: 9th International Symposium on Algorithms and Computation (formerly SIGAL International Symposium on Algorithms), Organized by Special Interest Group on Algorithms (SIGAL) of the Information Processing Society of Japan (IPSJ) and the Technical Group on Theoretical Foundation of Computing of the Institute of Electronics, Information and Communication Engineers (IEICE)), September 1998.

[EKSX96] Martin Ester, Hans-Peter Kriegel, Jorg Sander, and Xiaowei Xu. A density-based algorithm for discovering clusters in large spa- tial databases with noise. In Evangelos Simoudis, Jiawei Han, and Usama Fayyad, editors, Second International Conference on Knowledge Discovery and Data Mining, pages 226–231, Portland, Oregon, 1996. AAAI Press.

[FBF77] Jerome H. Friedman, Jon Louis Bentley, and Raphael Ari Finkel. An Algorithm for Finding Best Matches in Logarithmic Expected Time. ACM Transactions on Mathematical Software, 3(3):209– 226, September 1977.

[GRS01] Sudipto Guha, Rajeev Rastogi, and Kyuseok Shim. CURE: an efficient clustering algorithm for large databases. May 2001.

[MR97a] Conrado Martínez and Salvador Roura. Randomized binary search trees. January 1997.

[MR97b] Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1997.

[NH94] R. T. Ng and J. Han. Efficient and effective clustering methods for spatial data mining. In Jorgeesh Bocca, Matthias Jarke, and Carlo Zaniolo, editors, 20th International Conference on Ve- ry Large Data Bases, September 12–15, 1994, Santiago, Chile proceedings, pages 144–155, Los Altos, CA 94022, USA, 1994. Morgan Kaufmann Publishers.

[Ols95] C. F. Olson. Parallel algorithms for hierarchical clustering. Parallel Computing, 21(8):1313–1325, August 1995.

[Sam89] H. J. Samet. Design and analysis of Spatial Data Structures: Quadtrees, Octrees, and other Hierarchical Methods. Addison– Wesley, Redding, MA, 1989.

[Vit85] J. Vitter. Random sampling with a reservoir. ACM Transactions on Mathematical Software, 11(1):37–57, March 1985.

[ZRL96] Tian Zhang, Raghu Ramakrishnan, and Miron Livny. BIRCH: an efficient data clustering method for very large databases. pages 103–114, 1996.

Struttura dati KD-tree

“Tutto cio’ che esiste nell’universo e’ frutto del caso e della necessita”.

Democrito (460 - 370 a.C.)