5. L’ALGORITMO ORCLUS APPLICATO AI BASKET DATASET
5.1 Osservazioni
preliminari
Per basket dataset si intende qui un database di punti n -dimensionali, ciascuno dei quali ha un elevato numero di coordinate nulle. Un caso particolare di basket dataset, per il quale si parla di basket dataset binario, si ha quando tutte le coordinate non nulle valgono 1.
Tipicamente si incontrano basket dataset nel contesto di sistemi che coinvolgono transazioni, come ad esempio nel caso dell’e-commerce, oppure nel contesto dell’analisi delle sequenze di visita a siti web.
I dataset di questo tipo, che si presentano come matrici sparse, rendono difficile il clustering soprattutto a causa delle covarianze nulle. Nell’analisi che segue si cercherà di valutare come reagisce l’algoritmo ORCLUS di fronte a questo problema.
5.1.1 Un esempio teorico
Si consideri il semplice caso illustrato in Figura 25. Si tratta di un dataset costituito da punti a tre dimensioni, ciascuno dei quali avente una sola coordinata nulla. I punti formano tre cluster compatti, evidenziati in figura dalla diversa colorazione. In effetti il caso in esame è particolare, sia perché tutti i punti hanno esattamente lo stesso numero di coordinate nulle, cioè una sola, sia perché la separazione tra i cluster è fortemente marcata, infine perché punti appartenenti a cluster diversi hanno diversa coordinata nulla. Tuttavia la situazione è tale da mettere in gioco tutti gli ostacoli rispetto ai quali si desidera analizzare il comportamento dell’algoritmo.
Si supponga di eseguire ORCLUS su questo dataset richiedendo tre cluster, proiettati in sottospazi a due dimensioni. Si supponga inoltre che i cluster illustrati formino proprio il miglior clustering per il dataset. L’algoritmo fisserà i centroidi dei cluster e orienterà i rispettivi sottospazi di proiezione scartando la dimensione a maggior dispersione. Per il cluster di punti color celeste, giacente sul piano X-Y, le due dimensioni individuate saranno probabilmente quelle i cui versori sono indicati in Figura 25(d) con u1 e u2 .
Figura 25
Si nota immediatamente che il versore u1 è parallelo all’asse Z: questo è ragionevole, perché lungo quella direzione i punti del cluster hanno tutti stessa coordinata e di conseguenza la dispersione risulta nulla. Il versore u2 invece è combinazione lineare delle direzioni X e Y, dipendente dalla forma del cluster.
5.1.2 Interpretazione dei risultati
Si supponga che il dataset dell’esempio sia relativo alle visite degli utenti a un sito web. Si supponga inoltre che i tre assi dello spazio rappresentino le tre categorie di servizi disponibili e che i record del dataset indichino quante volte un certo utente si è avvalso di ciascun servizio.
Utilizzando ORCLUS l’informazione associata alla coppia centroide-sottospazio di ogni cluster è la seguente:
1. il legame tra i dati del cluster è rappresentato dalle direzioni del sottospazio; le componenti dei versori del sottospazio sono i coefficienti (normalizzati) delle combinazioni lineari delle direzioni dello spazio-origine;
2. il prototipo dei dati del cluster è rappresentato dal centroide;
3. l’importanza di una certa caratteristica in uno dei legami scoperti è proporzionale alla componente corrispondente a quella caratteristica nel versore rappresentativo del legame.
Nel contesto dell’esempio, le affermazioni ai punti 1 e 2 si traducono nell’interpretazione seguente: per gli utenti classificati nel cluster esaminato precedentemente, avere coordinata Z nulla significa che essi non si avvalgono mai della corrispondente categoria di servizi; questo comportamento è riassunto dal centroide, la cui coordinata Z è nulla essendo proprio la media aritmetica delle coordinate dei punti del cluster.
L’affermazione al punto 3 è invece meno immediata da spiegare. Un versore orientato come la bisettrice di uno dei semipiani, con coordinate
[
0.5 0.5 0]
per esempio, indicherebbe che la compattezza del cluster è dovuta in eguale misura ad entrambe le caratteristiche rappresentate dalle direzioni X e Y. Si consideri a tal proposito il versore u2: se la dispersione del cluster celeste lungo X fosse maggiore, l’algoritmo produrrebbe al suo posto un versore u3 che minimizza la dispersione e la cui componente lungo X è minore, in valore assoluto, della stessa componente di u2. Il versore u3 sarebbe in un certo senso “più simile” all’asse Y. Quindi, più un versore di un sottospazio-proiezione risulta parallelo a una delle direzioni dello spazio-origine, tanto più la caratteristica originale corrispondente ha peso nel legame rappresentato dal versore associato al cluster.In base a tutto questo si deduce che la situazione rappresentata dal versore u1 è un caso limite, in cui la caratteristica rappresentata dall’asse Z non è legata alle altre, da sola è sufficiente a fornire parte dell’informazione.
Si osservi infine il cluster rosso dell’esempio: la dispersione dei punti lungo X è nulla e quella lungo Z è ridottissima. I versori del sottospazio bi-dimensionale associato saranno probabilmente paralleli uno all’asse X e l’altro all’asse Z. Il centroide avrà coordinate
[
0 z~]
. Quindi l’informazione fornita dalla coppia centroide-sottospazio è che il gruppo di utenti rappresentati dal centroide del cluster rosso non si avvale mai dei servizi della categoria “X” e si è avvalsa di quelli della categoria “Y” un numero quasi costante z~ di volte.5.1.3 Riduzione delle caratteristiche
Nell’ottica della riduzione delle caratteristiche, spesso necessaria per l’usabilità dei risultati ai fini del data mining, si potrebbe richiedere all’algoritmo di restituire cluster proiettati su sottospazi aventi un numero molto ridotto di dimensioni rispetto allo spazio-origine.
Per capire come si comporta l’algoritmo in questa situazione, si supponga di eseguire ORCLUS sul dataset dell’esempio di Figura 25 e di imporre dimensionalità pari a 1.
L’algoritmo selezionerà la dimensione dello spazio-origine lungo la quale le coordinate dei punti sono tutte nulle, fornendo una risposta dal contenuto informativo banale, raggiungibile, al limite, anche per semplice ispezione del dataset. Ciò nonostante, l’algoritmo produce un risultato corretto.
Se però uno dei piani dello spazio-origine contenesse più di un cluster, situazione certamente più generale di quella restrittiva appena esaminata, non sarebbe più garantita la correttezza della soluzione restituita da ORCLUS. Per fissare le idee si può considerare il caso di Figura 26. Il dataset è analogo a quello del caso precedente, ma i dati sono in numero maggiore e si ha un cluster in più, i cui punti giacciono sul piano X-Y e sono evidenziati con il colore arancio.
Si supponga di applicare l’algoritmo richiedendo esattamente quattro cluster proiettati in sottospazi mono-dimensionali: dove si troveranno i centroidi dei due cluster giacenti sul piano X-Y?
Probabilmente non nel centro dei cluster raffigurati, dato che nel sottospazio mono-dimensionale tutti i punti sul piano possono appartenere indifferentemente all’uno o all’altro cluster e di conseguenza l’assegnamento dei punti sarà quasi casuale.
Figura 26
Per avere una risposta più completa, si consideri la struttura dell’algoritmo. Ogni operazione Assign determina l’attribuzione dei punti ai cluster, sulla base della distanza proiettata dal punto al centroide. Quando, a causa delle molte coordinate nulle, la distanza proiettata è zero per diversi cluster, il punto viene assegnato al primo di essi in ordine di valutazione. Da qui la casualità della soluzione restituita.
Il fenomeno illustrato, che rende ORCLUS inadatto ai basket dataset, può essere considerato dipendente dalla mancanza della quantità di informazione necessaria per assegnare correttamente i punti ai cluster.
Con l’obiettivo di risolvere questo problema, si è provveduto a realizzare una versione modificata di ORCLUS, aggiungendo una procedura di assegnamento specializzata per i basket dataset. La nuova procedura sostanzialmente usa, durante la fase Assign, la distanza
Euclidea calcolata nello spazio origine anziché la distanza proiettata. In questo modo risultano coinvolte nell’assegnamento tutte le coordinate e quindi cresce la quantità di informazione disponibile per la scelta del cluster in cui inserire ogni punto.
Il prossimi paragrafi illustrano i risultati delle prove effettuate su dati artificiali e dati reali, che da un lato hanno confermato il verificarsi del problema presentato e dall’altro hanno mostrato l’efficacia della modifica proposta come soluzione.
5.2 Prove su dati artificiali
5.2.1 Generazione di un dataset del tipo “basket data”
Per prima cosa è stato necessario realizzare un opportuno generatore di dati artificiali, chiamato Basketgen. Il programma è una variante del software Datagen e ne eredita il principio di funzionamento e le caratteristiche. Produce dataset d-dimensionali i cui punti hanno m coordinate nulle e formano cluster compatti.
Uno dei dataset utilizzati per testare orclus32 è quello descritto e illustrato qui di seguito: Numero di punti: 1000
Dimensionalità dello spazio-origine: 3 Numero di cluster: 5
Dimensionalità dei sottospazi-proiezione: 2
Proiezione X-Y -7900 -7890 -7880 -7870 -7860 -7850 -7840 -7830 -7820 -7810 -7800 4100 4120 4140 4160 4180 4200 4220 4240 4260 4280 4300 X Y cluster 0 Figura 27
Proiezione X-Z 550 1050 1550 2050 2550 3050 2500 3000 3500 4000 4500 5000 5500 X Z cluster 1 cluster 3 Figura 28 Proiezione Y-Z -6750 -6550 -6350 -6150 -5950 -5750 -5550 -9000 -7000 -5000 -3000 -1000 1000 3000 Y Z cluster 2 cluster 4 Figura 29
Le caratteristiche di questo dataset sono tali da provocare i problemi discussi nel capitolo precedente. Inoltre, la dimensione e la dimensionalità sono state scelte onde permettere una comoda visualizzazione grafica. Nel paragrafo seguente si analizzerà il comportamento della versione standard di ORCLUS.
5.2.2 Applicazione di ORCLUS
1. Inizialmente l’algoritmo è stato utilizzato per cercare cluster proiettati in una sola dimensione. Al programma è stata imposta la seguente configurazione:
Dimensionalità dello spazio-origine: 3 Numero desiderato di cluster: 5
Dimensionalità dei sottospazi-proiezione: 1 Numero iniziale di semi: 75
Fattore di riduzione: 0.5
Metodo di calcolo degli autovalori: J Progressive Random Sampling: OFF
Si noti che il numero di cluster richiesto è quello “esatto”: questa impostazione è stata scelta per poter effettuare eventuali regolazioni successive di altri parametri nel caso di restituzione di risultati sbagliati.
Una delle segmentazioni ottenute è riassunta dai seguenti valori:
cluster X Y Z punti 0 4193.918975 -7856.541623 0 76 1 3332.830246 0 2561.04036 383 2 0 -5200.86161 -6314.280516 541 3 0 -8383.981702 -6548.258826 0 4 0 -8396.541804 -6539.285592 0
Cluster Sparsity Coefficient: 0
Il CSC uguale a zero indicherebbe che il risultato è ottimo, però ci sono due cluster vuoti. Quindi l’algoritmo non ha trovato tutti i cluster, ma non è possibile accorgersene solo in base alla valutazione del CSC.
2. La responsabilità dell’errore è stata attribuita alla configurazione impostata. Tenendo conto che, durante i test precedenti, si era manifestato un calo della precisione quando il numero iniziale di semi superava il 5% della dimensione del dataset, al parametro k è stato assegnato il valore 40. 0
Una delle nuove segmentazioni ottenute è riassunta dai seguenti valori: cluster X Y Z punti 0 0 -5200.86161 -6314.280516 541 1 3332.830246 0 2561.04036 383 2 0 -8341.405952 -6583.237281 0 3 4193.918975 -7856.541623 0 76 4 0 -8404.250581 -6584.616137 0
Cluster Sparsity Coefficient: 0
Le caratteristiche del risultato sono identiche a quelle del precedente. Si noti che il numero di punti nei cluster individuati è rimasto lo stesso.
3. Prove ulteriori, eseguite con diverse configurazioni, hanno dato risultati del tutto analoghi. Un elemento di interesse può essere l’assoluta uguaglianza di certi valori per le diverse esecuzioni: la ripartizione del numero di punti nei cluster di output, le coordinate dei tre cluster non vuoti. Le figure seguenti mostrano il posizionamento dei centroidi: Proiezione X-Y -7900 -7890 -7880 -7870 -7860 -7850 -7840 -7830 -7820 -7810 -7800 4100 4120 4140 4160 4180 4200 4220 4240 4260 4280 4300 X Y cluster 0 centroide 2 Figura 30
Proiezione X-Z 550 1050 1550 2050 2550 3050 2500 3000 3500 4000 4500 5000 5500 X Z cluster 1 cluster 3 centroide 1 Figura 31 Proiezione Y-Z -6750 -6550 -6350 -6150 -5950 -5750 -5550 -9000 -7000 -5000 -3000 -1000 1000 3000 Y Z cluster 2 cluster 4 centroide 0 centroide 3 centroide 4 Figura 32
In base ai grafici e tenendo conto del fatto che tutte le prove eseguite hanno prodotto risultati simili, si deduce che il comportamento dell’algoritmo è attinente alle ipotesi precedentemente esposte a proposito dei basket dataset. Si fa notare inoltre che questo problema di indistinguibilità, provocato dalla presenza di più cluster contenenti punti con le stesse coordinate nulle, si è ripresentato anche per dimensionalità dei cluster più elevata.
4. Per completezza, si riporta infine una delle prove eseguite imponendo un numero di cluster diverso da quello “esatto”. I risultati seguenti riguardano una configurazione che impone k =7, k0 =45, α =0.75: cluster X Y Z punti 0 4193.918975 -7856.541623 0 76 1 0 2872.826129 -5640.58499 80 2 0 -5541.054391 -6344.10532 292 3 2772.11639 0 2965.65347 246 4 2750.297071 0 2966.543075 61 5 5616.767469 0 925.8437973 76 6 0 -8385.863945 -6577.474998 169
Cluster Sparsity Coefficient: 2.84686462e-006
Proiezione X-Y -7890 -7870 -7850 -7830 -7810 4160 4180 4200 4220 4240 4260 X Y cluster 0 centroide 0 Figura 33
Proiezione X-Z 500 1500 2500 3500 2500 3500 4500 5500 X Z cluster 1 cluster 3 centroide 3 centroide 4 centroide 5 Figura 34 Proiezione Y-Z -6800 -6550 -6300 -6050 -5800 -5550 -9000 -7000 -5000 -3000 -1000 1000 3000 Y Z cluster 2 cluster 4 centroide 1 centroide 2 centroide 6 Figura 35
Matrice di Confusione: cluster out 0 1 2 3 4 5 6 0 76 0 0 0 0 0 0 76 1 0 0 0 0 0 76 0 76 cluster in 2 0 80 73 0 0 0 0 153 3 0 0 0 246 61 0 0 307 4 0 0 219 0 0 0 169 388 76 80 292 246 61 76 169 Dominant Ratio: 0.964285714
In questo caso si può notare che nemmeno imponendo all’algoritmo di trovare un numero di cluster elevato si riesce ad aggirare il problema di indistinguibilità. Infatti, anche con due cluster più del necessario, si è ottenuto un centroide (il numero 2) che rappresenta punti vicini ad altri centroidi.
5.2.3 Applicazione di ORCLUS “modificato”
1. Come nell’esempio applicativo precedente, inizialmente l’algoritmo è stato utilizzato per cercare cluster proiettati in una sola dimensione. Al programma è stata imposta la seguente configurazione:
Dimensionalità dello spazio-origine: 3 Numero desiderato di cluster: 5
Dimensionalità dei sottospazi-proiezione: 1 Numero iniziale di semi: 75
Fattore di riduzione: 0.5
Metodo di calcolo degli autovalori: J Progressive Random Sampling: OFF Basket Dataset flag: ON
Una delle segmentazioni ottenute è riassunta dai seguenti valori:
cluster X Y Z punti 0 4193.918975 -7856.541623 0 76 1 0 2870.591332 -5641.811396 153 2 4412.273839 0 1785.720567 76 3 2765.154732 0 2968.778259 307 4 0 -8383.676816 -6579.455194 388 outlier -- -- -- 0
Il CSC uguale a zero indicherebbe ancora una volta che il risultato è ottimo e inoltre non compaiono cluster vuoti. Tuttavia, un esame del posizionamento dei centroidi ha mostrato che uno dei cluster di output giace nel centro di massa di due dei cluster di input. La responsabilità di questo comportamento è stata nuovamente attribuita al valore troppo alto del parametro k . 0
2. I test successivi sono stati eseguiti imponendo una configurazione con k0 =40. Uno dei risultati ottenuti è riassunto dai seguenti valori:
cluster X Y Z punti 0 4193.918975 -7856.541623 0 76 1 0 2870.591332 -5641.811396 153 2 5616.767469 0 925.8437973 76 3 2767.425592 0 2965.844721 307 4 0 -8383.676816 -6579.455194 388 outlier -- -- -- 0
Cluster Sparsity Coefficient: 0
La segmentazione è risultata molto accurata. In particolare, i centroidi dei cluster di output sono ben posizionati al centro dei cluster di input e il numero di punti in ciascuno di essi corrisponde esattamente. Tutti i punti sono stati assegnati correttamente.
Esiti analoghi sono stati ottenuti per tutte le altre prove, confermando l’efficacia della modifica effettuata all’algoritmo, almeno in questo semplice caso.
Le figure seguenti mostrano il posizionamento dei centroidi. Si è omesso di raffigurare la proiezione X-Y, irrilevante poiché contiene un solo cluster, per il quale neppure in precedenza si erano verificati problemi.
Proiezione X-Z 550 1050 1550 2050 2550 3050 2500 3000 3500 4000 4500 5000 5500 X Z cluster 1 cluster 3 centroide 2 centroide 3 Figura 36 Proiezione Y-Z -6750 -6550 -6350 -6150 -5950 -5750 -5550 -9000 -7000 -5000 -3000 -1000 1000 3000 Y Z cluster 2 cluster 4 centroide 1 centroide 4 Figura 37
3. Si è poi richiesto un output con cluster bidimensionali: Dimensionalità dello spazio-origine: 3
Numero desiderato di cluster: 5
Dimensionalità dei sottospazi-proiezione: 2 Numero iniziale di semi: 40
Fattore di riduzione: 0.5
Metodo di calcolo degli autovalori: J Progressive Random Sampling: OFF Basket Dataset flag: ON
Alcune esecuzioni del programma hanno restituito risultati interessanti, uno dei quali è riassunto dai seguenti valori:
cluster X Y Z punti 0 4193.918975 -7856.541623 0 76 1 5616.767469 0 925.8437973 76 2 2767.425592 0 2965.844721 307 3 0 2870.591332 -5641.811396 153 4 0 -8383.676816 -6579.455194 388 outlier -- -- -- 0
Cluster Sparsity Coefficient: 4.7526278e-006
I cluster prodotti in questo caso sono identici ai cluster generati con il dataset. Si riportano anche la Matrice di Confusione e la Dominant Ratio:
cluster out 0 1 2 3 4 0 76 0 0 0 0 76 1 0 76 0 0 0 76 cluster in 2 0 0 0 153 0 153 3 0 0 307 0 0 307 4 0 0 0 0 388 388 76 76 307 153 388 Dominant Ratio: 1
4. Ulteriori test sono stati effettuati richiedendo la produzione di un numero di cluster diverso da quello “giusto”. I risultati ottenuti sono stati complessivamente positivi. Quando il numero di cluster restituiti è stato posto maggiore del numero di cluster del dataset, l’algoritmo ha prodotto segmentazioni contenenti cluster sovrapposti, per i quali cioè coppie di centroidi hanno coordinate molto vicine. In pratica si sono presentate situazioni analoghe a quella descritta in Figura 34, che però non sono dovute al fenomeno dell’indistinguibilità, ma solo al numero eccessivo di cluster richiesti rispetto a quello ottimale. In questo caso non si tratta di un problema di prestazioni, perché l’algoritmo non trova automaticamente il numero ottimale di cluster, che è un parametro di input.
Quando il numero di cluster restituiti è stato posto minore del numero di cluster del dataset, l’algoritmo ha combinato alcuni cluster della segmentazione ottimale, producendo quindi risultati validi, anche se ovviamente meno precisi.
5.3 Esperienza su dati reali
5.3.1 Caratteristiche del dataset utilizzato
Per le prove su dati reali è stato utilizzato un dataset di 42.956 record a 61 dimensioni. Si tratta di informazioni relative ai comportamenti di visita degli utenti a un sito web, opportunamente filtrate e normalizzate.
La dimensione del dataset è piuttosto contenuta rispetto ai valori normalmente incontrati nel trattamento dei database estesi, per i quali si raggiungono facilmente milioni di record; tuttavia la dimensionalità è sufficientemente elevata da creare problemi per ottenere una segmentazione di qualità.
I record hanno molte coordinate nulle e i valori delle coordinate rimanenti sono
( )
0,1ℜ
∈ , quindi si può dire di essere in presenza di un basket dataset generale.
Alcune informazioni relative al dominio del problema, insieme a risultati ottenuti dall’applicazione di altri algoritmi, sono state prese come riferimento per la valutazione del clustering prodotto da orclus32.
5.3.2 Applicazione della versione standard dell’algoritmo
Le prove sono state effettuate applicando ripetutamente l’algoritmo con differenti combinazioni dei parametri di input. In particolare sono state eseguite prove con numero di cluster richiesti crescente e dimensionalità dei sottospazi decrescente, a partire da valori di 5 cluster e 30 dimensioni.
Le segmentazioni ottenute sono state quasi sempre inaccettabili e solo talvolta, nei casi migliori, di qualità bassa o scadente. Questa affermazione deriva principalmente dalla combinazione di due osservazioni:
1. i coefficienti di qualità restituiti sono stati mediamente O
( )
10−5 , talmente bassidunque da poter indicare o segmentazioni eccellenti o indistinguibilità;
2. in tutti i casi un alto numero di record (fra il 78% il 95%) è stato classificato appartenente a un unico grande cluster e spesso alcuni cluster sono risultati vuoti o formati da un numero non significativo di punti (1% o meno).
In seguito a queste osservazioni e tenendo presente il tipo del dataset in esame, si ha che il comportamento dell’algoritmo è risultato coerente con quello sperimentato nella fase di test su dati artificiali. Pertanto si può confermare che la versione standard dell’algoritmo ORCLUS è in generale inefficiente per i basket dataset.
5.3.3 Applicazione della versione modificata dell’algoritmo
Le prove sono state eseguite con le stesse modalità di quelle fatte per valutare la versione standard. Le segmentazioni ottenute sono state mediamente di buona qualità e sporadicamente di qualità più alta. Per giustificare queste affermazioni si riporta qui di seguito una breve analisi grafica dei risultati prodotti.
Dati reali (filtrati, 42956, 61)
0.0E+00 1.0E-02 2.0E-02 3.0E-02 4.0E-02 5.0E-02 6.0E-02 7.0E-02 8.0E-02 9.0E-02 1.0E-01 7 6 5 4 3 subspace dimensionality CS C clusters: 5 Figura 38
In Figura 38 è mostrato il grafico dell’andamento del Cluster Sparsity Coefficient rilevato al variare della dimensionalità dei sottospazi di proiezione, per esecuzioni con 5 cluster di output. La variazione del CSC è massima in corrispondenza del passaggio da 6 a 5 dimensioni, il che indica un probabile miglioramento della dispersione dei punti nei cluster quando la dimensionalità dei sottospazi è pari a 5.
Si sottolinea che il motivo per cui è necessario investigare sulle variazioni del CSC, piuttosto che sul suo valore minimo, è che al diminuire della dimensionalità dei sottospazi il
CSC decresce, dunque è evidente che il minimo del CSC non è necessariamente correlato al miglior clustering possibile.
Le figure seguenti mostrano grafici analoghi a quello appena esaminato, per dimensionalità diverse.
Dati reali (filtrati, 42956, 61)
0.0E+00 2.0E-02 4.0E-02 6.0E-02 8.0E-02 1.0E-01 1.2E-01 7 6 5 4 3 subspace dimensionality CS C clusters: 7 Figura 39
Dati reali (filtrati, 42956, 61)
0.0E+00 1.0E-02 2.0E-02 3.0E-02 4.0E-02 5.0E-02 6.0E-02 7 6 5 4 3 subspace dimensionality CS C clusters: 10 Figura 40
Si può notare che per dimensionalità pari a 4 e a 5 le curve hanno pendenze maggiori. Questo si è verificato per la maggioranza delle prove al variare del numero di cluster richiesti, inducendo quindi a concentrare l’attenzione su un intervallo di dimensionalità limitato.
Nel grafico di Figura 41, che mostra un confronto diretto, si può notare che le curve relative a segmentazioni con 10 e 15 cluster sono mediamente più schiacciate. In corrispondenza delle stesse curve sono stati ottenuti valori del CSC inferiori, fenomeno dovuto soprattutto al fatto che la dispersione dei punti tende a diminuire con l’aumento del numero di cluster della segmentazione.
Dati reali (filtrati, 42956, 61)
confronto diretto 0.0E+00 2.0E-02 4.0E-02 6.0E-02 8.0E-02 1.0E-01 1.2E-01 7 6 5 4 3 subspace dimensionality CS C clusters: 5 clusters: 7 clusters: 10 clusters: 15 Figura 41
In corrispondenza del valore 4 per la dimensionalità, il CSC ottenuto per 7 cluster è risultato generalmente prossimo a quelli ottenuti imponendo un numero maggiore di cluster. Questa osservazione, unitamente alle precedenti, ha portato l’indagine verso configurazioni dei parametri con 7 e 10 cluster e dimensionalità pari a 3, 4 e 5. Le segmentazioni ottenute utilizzando tali configurazioni sono state poi valutate rispetto alla dimensione dei cluster prodotti, con l’obiettivo di definire quella ottima.
Ripa rtiz ione de i punti
(c lusters: 7; dim ens ionality: 4)
3% 8% 55% 4% 19% 3% 8% 0 1 2 3 4 5 6
Ripa rtizione de i punti
(clus ters : 7; dim en s ion ality: 5)
58 % 5% 13 % 4%4% 1% 15 % 0 1 2 3 4 5 6
Ripa rtiz ione de i punti
(c lusters: 5; dim ens ionality: 3)
58% 27% 10% 1% 4% 0 1 2 3 4
Ripa rtizione de i punti
(clus ters : 10; d im e ns io nality: 4)
56 % 8% 4% 5% 2% 6% 9% 4% 3% 3% 0 1 2 3 4 5 6 7 8 9 Figura 42
Due segmentazioni considerate particolarmente interessanti sono quelle con 7 e 10 cluster rispettivamente, proiettati in sottospazi a 4 dimensioni. In corrispondenza di questi valori la massima percentuale di record classificati nello stesso cluster è risultata prossima al 55%, mentre i cluster più piccoli sono risultati contenere almeno il 2% dei record. Questi risultati sono stati valutati come ragionevoli sulla base delle conoscenze, pur minime, del dominio del problema. Per quanto detto precedentemente, tra le due segmentazioni indicate si individua come ottima quella con 7 cluster.
In definitiva, l’applicazione della versione modificata di ORCLUS ha prodotto un clustering con CSC dell’ordine di 10−2, valore al limite delle prestazioni definibili come
“buone”, per cui si può dire che l’esperienza su dati reali ha confermato che l’applicazione della modifica ha potenziato l’algoritmo base, rendendolo efficace anche in presenza di basket dataset.
