Bregman

In the Documents section are available the slides entitled: “Novel Clustering Techniques: Support Vector Methods and Minimum Bregman Information principle”

SVC has been explained with more care because it still is a very experimental technique.

In the previous posts, we have presented the results of some experiments about missing values robustness of SVC and Co-clustering.

A note about Co-clustering is dutiful: the Scheme number two of the Bregman Co-clustering without feature clustering and with Euclidean distance, is equal to the K-means algorithm.

This is the continuation of the experiments started few days ago.

Two other datasets have been involved in this type of experiments. Both of them are Astrophysics datasets, more precisely two dataset containing Stars and Galaxies.

Star/Galaxies separation is a problem usually tackled with supervised learning methodologies. In our work several clustering testes are conducted on such type of data.

These two datasets was chosen to be quite simple to separate, because we are interested in the robustness with respect missing values.

Starting from the original datasets, I have created eight variants for each of them, in this way

• 4 variants affecting only 3 features out of 15, with 5, 10, 20, 30 percent of objects reporting missing values for all of the 3 features, respectively
• 4 variants affecting 6 features out of 15, with 5, 10, 20, 30 percent of objects reporting missing values for all of the 6 features, respectively

The experiments was done with Euclidean Co-clustering (Information-theoretic cannot work with negative values) and SVC.

An archive with all results is available for download (it contains also the results of the previous stage).

In the files above:

- “MV� stands for “Missing Values�
- “FC� stands for “Feature Clusters�
- FC1 means no feature clustering
- FC2 means two clusters of feature requested
- FC3 means three clusters of feature requested
- CC stands for Co-clustering

Data la complessità nell’eseguire gli esperimenti con il Co-clustering e al fine di eseguire dei test ben ponderati, ho oggi deciso di eseguire dei test su dataset di dimensioni ridotte per capire la linea da seguire su dataset più complicati.

In riferimento agli esperimenti preliminari già eseguiti, ancora una volta oggetto dei test è l’IRIS data set.

Il test in questione è stato eseguito con lo Squared Euclidean Co-clustering. Nei test preliminari, con tale istanza di Co-clustering si era raggiunta un’accuratezza che oscillava tra l’88% e l’89%.

Nel test di oggi sono stati introdotti missing values nell’IRIS dataset, secondo una politica casuale.

Data la matrice di dati rappresentate il dataset (150 oggetti x 4 attributi), sono stati introdotti, nell’ordine, prima il 5, poi il 10 e poi il 20 per cento di missing values.

Nel primo caso l’accuratezza è stata del 88.667%, praticamente immutata.
Nel secondo caso l’accuratezza è stata del 84%.
Nel terzo caso l’accuratezza è stata del 81%.

Considerando la perdita di informazione introdotta, il Co-clustering ha fornito ugualmente risultati rispettabili, con una perdita di accuratezza non lineare rispetto al numero di missing values introdotti.

In giornata eseguirò altri test simili, per poi ritornare sul Pandora Dataset del prof. Longo e infine passare su un dataset di documenti testuali, come Reuters.

Ottime slide che riassiumono le caratteristiche e le applicazioni del Bregman Framework per il Co-clustering e il Missing-values Prediction.

N.B. nelle slide il termine matrice sparsa è usato secondo l’accezione geometrica classica.

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}
}

In the Documents section are available the slides entitled: “Data Clustering: High dimensionality, missing values and noise. Support Vector Methods and Minimum Bregman Information Principle“