Thesis Neminis

Prima bozza della stesura della tesi. Comprende

• Chapter 1: Introduction to Clustering

Download.

Impegni di lavoro non mi hanno permesso di lavorare al 100% sul test del Pandora Dataset, che data la mole di dati che produce a ogni test, ha necessitato, tra l’altro, la scrittura di strumenti di analisi, seppur abbastanza grezzi, per il momento.

Ad ogni modo, ciò che è possibile fornire allo stato attuale delle cose è il numero di oggetti per cluster, sia nel caso di “Pandora depurato” sia nel caso di “Pandora originale”. Il numero di cluster richiesti in entrambi i casi è stato 21, numero che dovrebbe essere un’ottima stima della realtà, in seguito ai ripetuti test effettuati per stimare appunto tale numero. Ad ogni modo, ripeto ancora una volta, l’obiettivo primario di questi test è assicurare un comportamento stabile del Co-clustering in presenza di oggetti con missing values. Un raffinamento della stima dei cluster potrà essere ottenuto, ad esempio, applicando relative criteria per la valutazione dei risultati (vedere prima bozza tesi)

Di seguito si fa riferimento all’ Information-Theoretic Co-clustering.

Co-clustering di “Pandora depurato” - Richiesti 21 Cluster

2724
5840
8064
8365
11825
12340
15119
15591
18449
19838
20086
22064
23863
25575
26577
26650
28016
30956
33215
40045
40746
435948 tot

Co-clustering di “Pandora originale” - Richiesti 21 Cluster

666
5176
5999
9961
13076
13336
14091
16104
17879
18135
19523
20632
23703
25933
30699
31505
32621
33934
35085
38781
42432
449271 tot (i 13304 oggetti in più sono quelli riportanti missing values)

Di seguito si fa riferimento al Minimum Sum Squared Co-clustering (v. II)

Co-clustering di “Pandora depurato” - Richiesti 21 Cluster

2427
3375
8471
10682
11176
11521
11702
12682
13262
15596
16760
19127
20744
20886
24549
28716
29123
30408
38123
41477
65141
435948 tot

Co-clustering di “Pandora originale” - Richiesti 21 Cluster

1106
1441
2288
3350
3597
5492
8232
8329
13267
16174
19508
19696
21329
23955
24489
26848
29635
41147
55983
56935
66470
449271 tot

Si sta sviluppando un ulteriore strumento di analisi, per l’analisi incrociata dei cluster.
Dato che il Co-clustering non produce i cluster sempre nello stesso ordine, è necessario un’analisi più complessa degli stessi per calcolare una misura di quanto il co-clustering sia rimasto stabile.

Inoltre si stanno riconducendo i test richiedendo 20 cluster, perché dagli ultimi test con 21 cluster, pur non essendoci cluster vuoti, è risultato in media, su 20 iterazioni, 1 cluster singleton.

Innanzitutto, le prime operazioni sul dataset Pandora sono state quelle di “preparazione” all’esperimento:

1. Eliminazione di alcune “feature” (quindi alcune colonne delle matrice dati)
2. Eliminazione degli oggetti aventi missing values (13304 su 449271) in corrispondenza delle restanti feature (i missing value erano riportati come -9999.0)

Partendo da un numero sovrastimato di cluster che si voleva ottenere, 50, si è iniziato a far girare il Co-clustering. Una serie di esecuzioni successive hanno rilevato che 50 era effettivamente sovrastimato, riportando il numero di cluster che restavano vuoti. Questo numero è stato sottratto a 50 ed è stato poi ripetuta l’esecuzione del co-clustering.

Questa operazione è stata ripetuta finché non si è avuta una media di cluster vuoti su 20 iterazioni di al più 1 cluster. Il numero di cluster stimato sembra così essere 20-21.
Già con input di 24 cluster richiesti, su 20 iterazioni si otteneva cmq una media di cluster vuoti di 1.5 cluster.

Ad ogni modo, questa prima fase non si è concentrata sulla stima esatta del numero di cluster, ma sul paragonare il comportamento dei test eseguiti sul dataset Pandora “depurato” dai missing values e quello originale.

Gli stessi test sono stati dunque ripetuti sul dataset originale, dove però al valore -9999.0 è stato sostituito 0, così come indicato dalla letteratura (una serie di test di prova direttamente col valore -9999.0 è stato effettuato e portava all’individuazione di soli 2-3 cluster). Il comportamento è stato praticamente simile, ottenendo la stessa stima di numero di cluster e un valore simile di funzione obiettivo alla fine del processo.

Tra l’altro, un controllo veloce dei cluster in entrambi i testi rivela che il contenuto dei cluster è molto simile, comunicandoci che la qualità del clustering non è stata gravemente inficiata dalla presenza di oggetti con missing values.

I successivi passi saranno questi:

1. Eseguire i test nuovamente stavolta aumentando il numero di step per l’algoritmo di local search, al fine di ottenere un migliore valore per i minimo locali e pertanto avere una maggiore affidabilità della stima di cluster finale.
2. Elaborazione approfondita dell’output del co-clustering, al fine di paragonare accuratamente i cluster ottenuti dal dataset depurato con quelli ottenuti dal dataset impuro

Inizio i lavori sul dataset Pandora fornitomi dal prof. Longo, basandomi sulle sue direttive.

Maggiori dettagli sul dataset saranno disponibili al più presto.

Il clustering verrà affrontato con Bregman Co-clustering, per affrontare il problema dei missing values.
Il metodo di aggiornamento dei mediodi/centroidi sarà il Local Search, che evita minimi locali e ci permette, partendo da un numero iniziale sovrastimato di cluter, di “scovare” il numero effettivo di cluster (o nei casi difficili una buona approssimazione di esso), lavorando per raffinamenti successivi.
In questo esperimento l’inizializzazione del co-clustering sarà lasciata casuale.

In successive prove proveremo ad utilizzare l’inizializzazione spettrale proposta in

• bibtex | link
  H. Cho, I. Dhillon, Y. Guan, and S. Sra, "Minimum sum squared residue co-clustering of gene expression data," in Proceedings of the Fourth SIAM International Conference on Data Mining, 2004, pp. 114-125.
  @inproceedings{cho04minimum,
  author = {H. Cho and I. Dhillon and Y. Guan and S. Sra},
  Booktitle = {Proceedings of the Fourth SIAM International Conference on Data Mining},
  Date-Added = {2007-04-12 11:30:35 +0200},
  Date-Modified = {2007-06-19 15:14:55 +0200},
  Keywords = {clustering, co-clustering, bioinformatics},
  Month = {April},
  Pages = {114–125},
  Title = {Minimum sum squared residue co-clustering of gene expression data},
  Url = {http://www.cs.utexas.edu/users/inderjit/public_papers/mssrcc_siam.pdf},
  Year = {2004},
  Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGBwpZJGFyY2hpdmVyWCR2ZXJzaW9uVCR0b3BYJG9iamVjdHNfEA9OU0tleWVkQXJjaGl2ZXISAAGGoNEICVRyb290gAGoCwwXGBkaHiVVJG51bGzTDQ4PEBMWWk5TLm9iamVjdHNXTlMua2V5c1YkY2xhc3OiERKABIAFohQVgAKAA4AHXHJlbGF0aXZlUGF0aFlhbGlhc0RhdGFfEFkuLi8uLi8uLi9QYXBlcnMvQ2hvL01pbmltdW0gc3VtIHNxdWFyZWQgcmVzaWR1ZSBjby1jbHVzdGVyaW5nIG9mIGdlbmUgZXhwcmVzc2lvbiBkYXRhLnBkZtIbDxwdV05TLmRhdGFPEQJYAAAAAAJYAAIAAAlEb2N1bWVudHMAAAAAAAAAAAAAAAAAAAAAAAC+zniuSCsAAAA3JQAfTWluaW11bSBzdW0gc3F1YXJlZCAjMkEzOTY0LnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACo5ZMI6vZZQREYgAAAAAAADAAMAAAkAAAAAAAAAAAAAAAAAAAAAA0NobwAAEAAIAAC+zlyOAAAAEQAIAADCOqF2AAAAAQAUADclAAA3G4AAALLyAAASxgAAEq0AAgBORG9jdW1lbnRzOm5lbW86RG9jdW1lbnRzOlVuaXZlcnNpdGE6UGFwZXJzOkNobzpNaW5pbXVtIHN1bSBzcXVhcmVkICMyQTM5NjQucGRmAA4AjABFAE0AaQBuAGkAbQB1AG0AIABzAHUAbQAgAHMAcQB1AGEAcgBlAGQAIAByAGUAcwBpAGQAdQBlACAAYwBvAC0AYwBsAHUAcwB0AGUAcgBpAG4AZwAgAG8AZgAgAGcAZQBuAGUAIABlAHgAcAByAGUAcwBzAGkAbwBuACAAZABhAHQAYQAuAHAAZABmAA8AFAAJAEQAbwBjAHUAbQBlAG4AdABzABIAay9uZW1vL0RvY3VtZW50cy9Vbml2ZXJzaXRhL1BhcGVycy9DaG8vTWluaW11bSBzdW0gc3F1YXJlZCByZXNpZHVlIGNvLWNsdXN0ZXJpbmcgb2YgZ2VuZSBleHByZXNzaW9uIGRhdGEucGRmAAATABIvVm9sdW1lcy9Eb2N1bWVudHMAFQACABf//wAAgAbSHyAhIlgkY2xhc3Nlc1okY2xhc3NuYW1loyIjJF1OU011dGFibGVEYXRhVk5TRGF0YVhOU09iamVjdNIfICYnoickXE5TRGljdGlvbmFyeQAIABEAGwAkACkAMgBEAEkATABRAFMAXABiAGkAdAB8AIMAhgCIAIoAjQCPAJEAkwCgAKoBBgELARMDbwNxA3YDfwOKA44DnAOjA6wDsQO0AAAAAAAAAgEAAAAAAAAAKAAAAAAAAAAAAAAAAAAAA8E=},
  Bdsk-Url-1 = {http://www.cs.utexas.edu/users/inderjit/public_papers/mssrcc_siam.pdf}
}

per migliorare la qualità del risultato finale.

Infine, essendo presenti valori negativi nella matrice, l’istanza di Co-clustering basata su di divergenza KL e Mutua Informazione non potrà essere utilizzata

• bibtex | link
  I. S. Dhillon, S. Mallela, and D. S. Modha, "Information-Theoretic Co-Clustering," in Proceedings of The Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2003), 2003, pp. 89-98.
  @inproceedings{dhillon:mallela:modha:03,
  author = {I. S. Dhillon and S. Mallela and D. S. Modha},
  Booktitle = {Proceedings of The Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining ({KDD}-2003)},
  Date-Modified = {2007-07-14 15:32:35 +0200},
  Keywords = {clustering, co-clustering, relative entropy},
  Pages = {89–98},
  Title = {Information-Theoretic Co-Clustering},
  Url = {http://www.cs.utexas.edu/users/inderjit/public_papers/kdd_cocluster.pdf},
  Year = {2003},
  Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGBwpZJGFyY2hpdmVyWCR2ZXJzaW9uVCR0b3BYJG9iamVjdHNfEA9OU0tleWVkQXJjaGl2ZXISAAGGoNEICVRyb290gAGoCwwXGBkaHiVVJG51bGzTDQ4PEBMWWk5TLm9iamVjdHNXTlMua2V5c1YkY2xhc3OiERKABIAFohQVgAKAA4AHXHJlbGF0aXZlUGF0aFlhbGlhc0RhdGFfED8uLi8uLi8uLi9QYXBlcnMvRGhpbGxvbi9JbmZvcm1hdGlvbi1UaGVvcmV0aWMgQ28tQ2×1c3RlcmluZy5wZGbSGw8cHVdOUy5kYXRhTxECCgAAAAACCgACAAAJRG9jdW1lbnRzAAAAAAAAAAAAAAAAAAAAAAAAvs54rkgrAAAANyNdH0luZm9ybWF0aW9uLVRoZW9yZXRpIzIzQThBNi5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAjqKbCBy5VAAAAAAAAAAAAAwADAAAJAAAAAAAAAAAAAAAAAAAAAAdEaGlsbG9uAAAQAAgAAL7OXI4AAAARAAgAAMIHIEUAAAABABQANyNdADcbgAAAsvIAABLGAAASrQACAFJEb2N1bWVudHM6bmVtbzpEb2N1bWVudHM6VW5pdmVyc2l0YTpQYXBlcnM6RGhpbGxvbjpJbmZvcm1hdGlvbi1UaGVvcmV0aSMyM0E4QTYucGRmAA4AUAAnAEkAbgBmAG8AcgBtAGEAdABpAG8AbgAtAFQAaABlAG8AcgBlAHQAaQBjACAAQwBvAC0AQwBsAHUAcwB0AGUAcgBpAG4AZwAuAHAAZABmAA8AFAAJAEQAbwBjAHUAbQBlAG4AdABzABIAUS9uZW1vL0RvY3VtZW50cy9Vbml2ZXJzaXRhL1BhcGVycy9EaGlsbG9uL0luZm9ybWF0aW9uLVRoZW9yZXRpYyBDby1DbHVzdGVyaW5nLnBkZgAAEwASL1ZvbHVtZXMvRG9jdW1lbnRzABUAAgAX//8AAIAG0h8gISJYJGNsYXNzZXNaJGNsYXNzbmFtZaMiIyRdTlNNdXRhYmxlRGF0YVZOU0RhdGFYTlNPYmplY3TSHyAmJ6InJFxOU0RpY3Rpb25hcnkACAARABsAJAApADIARABJAEwAUQBTAFwAYgBpAHQAfACDAIYAiACKAI0AjwCRAJMAoACqAOwA8QD5AwcDCQMOAxcDIgMmAzQDOwNEA0kDTAAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAANZ},
  Bdsk-Url-1 = {http://www.cs.utexas.edu/users/inderjit/public_papers/kdd_cocluster.pdf}
}

L’algoritmo di Cluster Assignment usato

• bibtex | link
  S. Lee and K. M. Daniels, "Cone Cluster Labeling for Support Vector Clustering," in Proceedings of 6th SIAM Conference on Data Mining, 2006, pp. 484-488.
  @inproceedings{cone2006,
  author = {Sei-Hyung Lee and Karen M. Daniels},
  Booktitle = {Proceedings of 6th SIAM Conference on Data Mining},
  Date-Added = {2007-04-29 16:58:13 +0200},
  Date-Modified = {2007-06-19 18:52:22 +0200},
  Keywords = {SVM, clustering},
  Month = {May},
  Pages = {484–488},
  Title = {Cone Cluster Labeling for Support Vector Clustering},
  Url = {http://www.siam.org/meetings/sdm06/proceedings/046lees.pdf},
  Year = {2006},
  Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGBwpZJGFyY2hpdmVyWCR2ZXJzaW9uVCR0b3BYJG9iamVjdHNfEA9OU0tleWVkQXJjaGl2ZXISAAGGoNEICVRyb290gAGoCwwXGBkaHiVVJG51bGzTDQ4PEBMWWk5TLm9iamVjdHNXTlMua2V5c1YkY2xhc3OiERKABIAFohQVgAKAA4AHXHJlbGF0aXZlUGF0aFlhbGlhc0RhdGFfEEsuLi8uLi8uLi9QYXBlcnMvTGVlL0NvbmUgQ2×1c3RlciBMYWJlbGluZyBmb3IgU3VwcG9ydCBWZWN0b3IgQ2×1c3RlcmluZy5wZGbSGw8cHVdOUy5kYXRhTxECLgAAAAACLgACAAAJRG9jdW1lbnRzAAAAAAAAAAAAAAAAAAAAAAAAvs54rkgrAAAANyVBH0NvbmUgQ2×1c3RlciBMYWJlbGluIzJGMDk0My5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAvCUPCWn72AAAAAAAAAAAAAwADAAAJAAAAAAAAAAAAAAAAAAAAAANMZWUAABAACAAAvs5cjgAAABEACAAAwlpi1gAAAAEAFAA3JUEANxuAAACy8gAAEsYAABKtAAIATkRvY3VtZW50czpuZW1vOkRvY3VtZW50czpVbml2ZXJzaXRhOlBhcGVyczpMZWU6Q29uZSBDbHVzdGVyIExhYmVsaW4jMkYwOTQzLnBkZgAOAHAANwBDAG8AbgBlACAAQwBsAHUAcwB0AGUAcgAgAEwAYQBiAGUAbABpAG4AZwAgAGYAbwByACAAUwB1AHAAcABvAHIAdAAgAFYAZQBjAHQAbwByACAAQwBsAHUAcwB0AGUAcgBpAG4AZwAuAHAAZABmAA8AFAAJAEQAbwBjAHUAbQBlAG4AdABzABIAXS9uZW1vL0RvY3VtZW50cy9Vbml2ZXJzaXRhL1BhcGVycy9MZWUvQ29uZSBDbHVzdGVyIExhYmVsaW5nIGZvciBTdXBwb3J0IFZlY3RvciBDbHVzdGVyaW5nLnBkZgAAEwASL1ZvbHVtZXMvRG9jdW1lbnRzABUAAgAX//8AAIAG0h8gISJYJGNsYXNzZXNaJGNsYXNzbmFtZaMiIyRdTlNNdXRhYmxlRGF0YVZOU0RhdGFYTlNPYmplY3TSHyAmJ6InJFxOU0RpY3Rpb25hcnkACAARABsAJAApADIARABJAEwAUQBTAFwAYgBpAHQAfACDAIYAiACKAI0AjwCRAJMAoACqAPgA/QEFAzcDOQM+A0cDUgNWA2QDawN0A3kDfAAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAAOJ},
  Bdsk-Url-1 = {http://www.siam.org/meetings/sdm06/proceedings/046lees.pdf}
}

come tutti gli altri proposti in letteratura non tratta esplicitamente la classificaizione dei Bounded Support Vector, ovvero di quei punti che, per effetto del valore della costante di margine morbido, finiscono fuori dalla sfera di descrizione del dominio anche se in realtà fanno parte di una delle classi del problema.

Il Cone Cluster Labeling prevede due passi:

• classificazione dei SV
• classificazione di tutti gli altri punti in relazione ai SV

che di fatto comprende anche i BSV in “tutti gli altri punti”.

Si è scelto di modificare in questo modo l’algoritmo:

• classificazione dei SV
• classificazione di tutti gli altri punti (tranne i BSV) in relazione ai SV
• classificazione dei BSV in relazione a tutti gli altri punti già classificati

Nel caso dell’IRIS data set, questa modifica ha portato l’accuratezza da un valore di 89,333% a un valore del 90%.

I limiti principali del Multi-Layer Perceptron (MLP) sono:

• la necessità di fissare a priori la struttura della rete, in termini di hidden layers e di numero di neuroni da porre in ognuno di essi
• l’eccessiva ampiezza delle maggiorazioni ottenute per la VC-dimension dei modelli impiegati praticamente
• difficoltà di addestramento nel caso di dataset non linearmente separabili:
• a causa dell’alto numero di dimensioni dello spazio dei pesi
• poiché le tecniche più diffuse, come la back-propagation, permettono di ottenere i pesi della rete risolvendo un problema di ottimizzazione non convesso e non vincolato che, di conseguenza, presenta un numero indeterminato di minimi locali.

Le SVM superano questi problemi.
Innanzitutto non c’è la necessità di costruire esplicitamente la funzione non lineare per mappare gli ingressi nello spazio degli attributi. Tramite il kernel trick si opera implicitamente nello spazio degli attributi (equivalente allo spazio degli hidden layers). In questo modo ci si svincola dall’obbligo di fissare a priori la struttura della rete neurale. Allo stesso tempo si rende le SVM scalabili rispetto a dati di alta dimensionalità.
Inoltre le SVM assicurano una soluzione unica e globale nel caso si scelta un kernel definito positivamente.