Archive for June, 2007

Co-clustering Preliminary Experiments

29 Jun, 2007  No Comment

In the section Documents is available for download the PDF with the configurations used for tests and related results; is also available the ZIP archive containing the data-sets used for the experiments.

Co-clustering - Synthetic Dataset Test #1

22 Jun, 2007  2 Comments

Macchina usata:
PowerPC G4, 1.5GHz, 768MB RAM, Mac OS X

Software usato:

  • H. Cho, Y. Guan, and S. Sra, Co-cluster (v 1.1), 2004.
    @misc{coclus-software,
      author = {Hyuk Cho and Yuqiang Guan and Suvrit Sra},
      Date-Added = {2007-04-29 15:15:55 +0200},
      Date-Modified = {2007-06-25 17:10:33 +0200},
      Howpublished = {Bregman co-clustering software},
      Keywords = {co-clustering, relative entropy, euclidean distance, software},
      Title = {Co-cluster (v 1.1)},
      Url = {http://www.cs.utexas.edu/users/dml/Software/cocluster.html},
      Year = {2004},
      Bdsk-Url-1 = {http://www.cs.utexas.edu/users/dml/Software/cocluster.html}
    }

Dataset usato:
Il dataset usato in questo test è un dataset sintetico, generato grazie a

  • J. R. Vennam and S. Vadapalli, "SynDECA: A Tool to Generate Synthetic Datasets for Evaluation of Clustering Algorithms," in 11th International Conference on Management of Data (COMAD 2005), Goa, India, 2005.
    @conference{syndeca2005, Address = {Goa, India},
      Author = {Jhansi Rani Vennam and Soujanya Vadapalli},
      Booktitle = {11th International Conference on Management of Data (COMAD 2005)},
      Date-Added = {2007-06-18 16:18:49 +0200},
      Date-Modified = {2007-07-03 18:34:02 +0200},
      Keywords = {clustering, tool, synthetic, dataset, generator},
      Month = {January},
      Organization = {http://cde.iiit.ac.in/syndeca},
      Title = {SynDECA: A Tool to Generate Synthetic Datasets for Evaluation of Clustering Algorithms},
      Url = {http://comad2005.persistent.co.in/COMAD2005Proc/pages027-036.pdf},
      Year = {2005},
      Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGBwpZJGFyY2hpdmVyWCR2ZXJzaW9uVCR0b3BYJG9iamVjdHNfEA9OU0tleWVkQXJjaGl2ZXISAAGGoNEICVRyb290gAGoCwwXGBkaHiVVJG51bGzTDQ4PEBMWWk5TLm9iamVjdHNXTlMua2V5c1YkY2xhc3OiERKABIAFohQVgAKAA4AHXHJlbGF0aXZlUGF0aFlhbGlhc0RhdGFfEHAuLi8uLi8uLi9QYXBlcnMvVmVubmFtL1N5bkRFQ0EgQSBUb29sIHRvIEdlbmVyYXRlIFN5bnRoZXRpYyBEYXRhc2V0cyBmb3IgRXZhbHVhdGlvbiBvZiBDbHVzdGVyaW5nIEFsZ29yaXRobXMucGRm0hsPHB1XTlMuZGF0YU8RApwAAAAAApwAAgAACURvY3VtZW50cwAAAAAAAAAAAAAAAAAAAAAAAL7OeK5IKwAAADk5AR9TeW5ERUNBIEEgVG9vbCB0byBHZSMzOTM4RjcucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAOTj3wrBG9QAAAAAAAAAAAAMAAwAACQAAAAAAAAAAAAAAAAAAAAAGVmVubmFtABAACAAAvs5cjgAAABEACAAAwrAq1QAAAAEAFAA5OQEANxuAAACy8gAAEsYAABKtAAIAUURvY3VtZW50czpuZW1vOkRvY3VtZW50czpVbml2ZXJzaXRhOlBhcGVyczpWZW5uYW06U3luREVDQSBBIFRvb2wgdG8gR2UjMzkzOEY3LnBkZgAADgC0AFkAUwB5AG4ARABFAEMAQQAgAEEAIABUAG8AbwBsACAAdABvACAARwBlAG4AZQByAGEAdABlACAAUwB5AG4AdABoAGUAdABpAGMAIABEAGEAdABhAHMAZQB0AHMAIABmAG8AcgAgAEUAdgBhAGwAdQBhAHQAaQBvAG4AIABvAGYAIABDAGwAdQBzAHQAZQByAGkAbgBnACAAQQBsAGcAbwByAGkAdABoAG0AcwAuAHAAZABmAA8AFAAJAEQAbwBjAHUAbQBlAG4AdABzABIAgi9uZW1vL0RvY3VtZW50cy9Vbml2ZXJzaXRhL1BhcGVycy9WZW5uYW0vU3luREVDQSBBIFRvb2wgdG8gR2VuZXJhdGUgU3ludGhldGljIERhdGFzZXRzIGZvciBFdmFsdWF0aW9uIG9mIENsdXN0ZXJpbmcgQWxnb3JpdGhtcy5wZGYAEwASL1ZvbHVtZXMvRG9jdW1lbnRzABUAAgAX//8AAIAG0h8gISJYJGNsYXNzZXNaJGNsYXNzbmFtZaMiIyRdTlNNdXRhYmxlRGF0YVZOU0RhdGFYTlNPYmplY3TSHyAmJ6InJFxOU0RpY3Rpb25hcnkACAARABsAJAApADIARABJAEwAUQBTAFwAYgBpAHQAfACDAIYAiACKAI0AjwCRAJMAoACqAR0BIgEqA8oDzAPRA9oD5QPpA/cD/gQHBAwEDwAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAAQc},
      Bdsk-Url-1 = {http://comad2005.persistent.co.in/COMAD2005Proc/pages027-036.pdf}
    }

Il dataset è così composto:
Oggetti: 1000
Attributi: 10
Classi: 5, per un totale di 888 punti (Cluster 0: 327, Cluster 1: 134, Cluster 2: 162, Cluster 3: 132, Cluster 4: 133)
Punti di disturbo: 112 (punti non classificabili)

Algoritmo di co-clustering usato: Euclidean Distance Based, Minimum Sum Squared, Information Theoretic

Problemi: Da questo primo test condotto su un dataset disturbato, lo schema di co-clustering sembra non essere pensato per identificare il rumore e separarlo dal resto della classificazione, col risultato che tutte le istanze di co-clustering tendono a classificare il rumore in una delle cinque classi richieste, sfalsando i risultati.

Eliminazione punti di rumore: Eliminando i punti di rumore, abbiamo ottenuto un dataset di 888 punti e l’algoritmo (Euclidean Distance Based, con 5 co-cluster richiesti) ha separato perfettamente le 5 classi senza alcun errore in un tempo così espresso:
User = 0 second(s) 138552 ms
System = 0 second(s) 6630 ms
Time/Run = 0.138552 second(s)

Co-clustering - Real World Dataset Test #2

22 Jun, 2007  No Comment

Macchina usata:
PowerPC G4, 1.5GHz, 768MB RAM, Mac OS X

Software usato:

  • H. Cho, Y. Guan, and S. Sra, Co-cluster (v 1.1), 2004.
    @misc{coclus-software,
      author = {Hyuk Cho and Yuqiang Guan and Suvrit Sra},
      Date-Added = {2007-04-29 15:15:55 +0200},
      Date-Modified = {2007-06-25 17:10:33 +0200},
      Howpublished = {Bregman co-clustering software},
      Keywords = {co-clustering, relative entropy, euclidean distance, software},
      Title = {Co-cluster (v 1.1)},
      Url = {http://www.cs.utexas.edu/users/dml/Software/cocluster.html},
      Year = {2004},
      Bdsk-Url-1 = {http://www.cs.utexas.edu/users/dml/Software/cocluster.html}
    }

Dataset Usato:
Mushrooms Database
Number of instances: 8124
Number of Attributes: 22
2480 missing values for attribute #12
Original Class Distribution: edible: 4208 (51.8%), poisonous: 3916 (48.2%)
Mushroom records drawn from The Audubon Society Field Guide to North
American Mushrooms (1981). G. H. Lincoff (Pres.), New York: Alfred A. Knopf
Donor: Jeff Schlimmer (Jeffrey.Schlimmer@a.gp.cs.cmu.edu)
Date: 27 April 1987

Algoritmo di co-clustering usato: Minimum Sum Squared Residue

Prova #1
Richiesti 2 cluster di riga e 1 di colonna. Totale: 2 co-cluster

Tempo impiegato: User = 2 second(s) 127370 ms, System = 0 second(s) 40949 ms, Time/Run = 2.12737 second(s)

Risultato: 3670 elementi nella classe “poisonous”, 4454 elementi nella classe “edible”.

Percentuale d’errore (elementi non classificati correttamente): ~3%

Prova #2
Richiesti 2 cluster di riga e 2 di colonna. Totale: 4 co-cluster

Tempo impiegato: User = 2 second(s) 158490 ms, System = 0 second(s) 40654 ms, Time/Run = 2.15849 second(s)

Risultato: 3915 elementi nella classe “poisonous”, 4209 elementi nella classe “edible”.

Percentuale d’errore: ~1.23 x 10^-4 (1 solo elemento è stato classificato erroneamente)

Co-clustering - Real World Dataset Test #1

22 Jun, 2007  No Comment

Macchina usata:
PowerPC G4, 1.5GHz, 768MB RAM, Mac OS X

Software usato:

  • H. Cho, Y. Guan, and S. Sra, Co-cluster (v 1.1), 2004.
    @misc{coclus-software,
      author = {Hyuk Cho and Yuqiang Guan and Suvrit Sra},
      Date-Added = {2007-04-29 15:15:55 +0200},
      Date-Modified = {2007-06-25 17:10:33 +0200},
      Howpublished = {Bregman co-clustering software},
      Keywords = {co-clustering, relative entropy, euclidean distance, software},
      Title = {Co-cluster (v 1.1)},
      Url = {http://www.cs.utexas.edu/users/dml/Software/cocluster.html},
      Year = {2004},
      Bdsk-Url-1 = {http://www.cs.utexas.edu/users/dml/Software/cocluster.html}
    }

Dataset usato:
Iris Plant Database
From Fisher, 1936
3 classes, 4 numeric attributes, 150 instances
1 class is linearly separable from the other 2, but the other 2 are not linearly separable from each other

Algoritmo di co-clustering usato: Euclidean Distance Based.

Prova #1:
Richiesti 3 cluster di riga (sulle righe abbiamo gli oggeti, sulle colonne gli attributi) e 1 solo cluster di colonna. In tal modo non viene effettuato alcun feature clustering (che ricordiamo è contestuale al data clustering).

Tempo impiegato: User = 0 second(s) 9193 ms, System = 0 second(s) 2709 ms, Time/Run = 0.009193 second(s)

Risultato: Co-Cluster 1: 54 elementi di riga, Co-Cluster 2: 40 elementi di riga, Co-Cluster 3: 56 elementi di riga. Avendo specificato 1 solo cluster per le colonne, tutti i co-cluster hanno gli stessi elementi di colonna.

Conclusioni: L’algoritmo è riuscito a separare i cluster sovrapposti (classi 2 e 3 del dataset), ma ha commesso svariati errori di classificazioni. Al cluster 2 mancano 10 elementi, 4 dei quali sono nel primo cluster e i restanti 6 nel terzo cluster.

Prova #2:
Richiesti 3 cluster di riga e 2 cluster di colonna.

Tempo impiegato: User = 0 second(s) 8397 ms, System = 0 second(s) 3042 ms, Time/Run = 0.008397 second(s)

Risultato: Le tre classi sono state perfettamente separate. Nello specifico, sono stati prodotti 6 co-cluster, poiché, detto C il numero di cluster di colonna, e R il numero di cluster di riga, si ottengono sempre C*R co-cluster. Per ogni cluster di riga chiesto, si ottengono in pratica C co-cluster.

Conclusioni: Separare 2 cluster (classi 2 e 3 del dataset in esame) non linearmente separabili è notevole per un algoritmo non kernel-based.

Dataset sintetici per Clustering Benchmark

19 Jun, 2007  No Comment

Molto spesso, nell’eseguire i test di algoritmi di clustering, è molto utile avere a disposizione degli insiemi di dati campione sintetici, ovvero creati artificialmente e che non rispecchiano dei dati reali.

A tale scopo molto utile si rivela il lavoro fatto dal Center for Data Engineering, International Institute of Information Technology, Hyderabad, INDIA

  • J. R. Vennam and S. Vadapalli, "SynDECA: A Tool to Generate Synthetic Datasets for Evaluation of Clustering Algorithms," in 11th International Conference on Management of Data (COMAD 2005), Goa, India, 2005.
    @conference{syndeca2005, Address = {Goa, India},
      Author = {Jhansi Rani Vennam and Soujanya Vadapalli},
      Booktitle = {11th International Conference on Management of Data (COMAD 2005)},
      Date-Added = {2007-06-18 16:18:49 +0200},
      Date-Modified = {2007-07-03 18:34:02 +0200},
      Keywords = {clustering, tool, synthetic, dataset, generator},
      Month = {January},
      Organization = {http://cde.iiit.ac.in/syndeca},
      Title = {SynDECA: A Tool to Generate Synthetic Datasets for Evaluation of Clustering Algorithms},
      Url = {http://comad2005.persistent.co.in/COMAD2005Proc/pages027-036.pdf},
      Year = {2005},
      Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGBwpZJGFyY2hpdmVyWCR2ZXJzaW9uVCR0b3BYJG9iamVjdHNfEA9OU0tleWVkQXJjaGl2ZXISAAGGoNEICVRyb290gAGoCwwXGBkaHiVVJG51bGzTDQ4PEBMWWk5TLm9iamVjdHNXTlMua2V5c1YkY2xhc3OiERKABIAFohQVgAKAA4AHXHJlbGF0aXZlUGF0aFlhbGlhc0RhdGFfEHAuLi8uLi8uLi9QYXBlcnMvVmVubmFtL1N5bkRFQ0EgQSBUb29sIHRvIEdlbmVyYXRlIFN5bnRoZXRpYyBEYXRhc2V0cyBmb3IgRXZhbHVhdGlvbiBvZiBDbHVzdGVyaW5nIEFsZ29yaXRobXMucGRm0hsPHB1XTlMuZGF0YU8RApwAAAAAApwAAgAACURvY3VtZW50cwAAAAAAAAAAAAAAAAAAAAAAAL7OeK5IKwAAADk5AR9TeW5ERUNBIEEgVG9vbCB0byBHZSMzOTM4RjcucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAOTj3wrBG9QAAAAAAAAAAAAMAAwAACQAAAAAAAAAAAAAAAAAAAAAGVmVubmFtABAACAAAvs5cjgAAABEACAAAwrAq1QAAAAEAFAA5OQEANxuAAACy8gAAEsYAABKtAAIAUURvY3VtZW50czpuZW1vOkRvY3VtZW50czpVbml2ZXJzaXRhOlBhcGVyczpWZW5uYW06U3luREVDQSBBIFRvb2wgdG8gR2UjMzkzOEY3LnBkZgAADgC0AFkAUwB5AG4ARABFAEMAQQAgAEEAIABUAG8AbwBsACAAdABvACAARwBlAG4AZQByAGEAdABlACAAUwB5AG4AdABoAGUAdABpAGMAIABEAGEAdABhAHMAZQB0AHMAIABmAG8AcgAgAEUAdgBhAGwAdQBhAHQAaQBvAG4AIABvAGYAIABDAGwAdQBzAHQAZQByAGkAbgBnACAAQQBsAGcAbwByAGkAdABoAG0AcwAuAHAAZABmAA8AFAAJAEQAbwBjAHUAbQBlAG4AdABzABIAgi9uZW1vL0RvY3VtZW50cy9Vbml2ZXJzaXRhL1BhcGVycy9WZW5uYW0vU3luREVDQSBBIFRvb2wgdG8gR2VuZXJhdGUgU3ludGhldGljIERhdGFzZXRzIGZvciBFdmFsdWF0aW9uIG9mIENsdXN0ZXJpbmcgQWxnb3JpdGhtcy5wZGYAEwASL1ZvbHVtZXMvRG9jdW1lbnRzABUAAgAX//8AAIAG0h8gISJYJGNsYXNzZXNaJGNsYXNzbmFtZaMiIyRdTlNNdXRhYmxlRGF0YVZOU0RhdGFYTlNPYmplY3TSHyAmJ6InJFxOU0RpY3Rpb25hcnkACAARABsAJAApADIARABJAEwAUQBTAFwAYgBpAHQAfACDAIYAiACKAI0AjwCRAJMAoACqAR0BIgEqA8oDzAPRA9oD5QPpA/cD/gQHBAwEDwAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAAQc},
      Bdsk-Url-1 = {http://comad2005.persistent.co.in/COMAD2005Proc/pages027-036.pdf}
    }

Lo strumento riesce a produrre dataset sintetici molto rapidamente; in genere un insieme con spazio delle feature 2D, con un milione di punti e centinaia di cluster, viene prodotto in pochi secondi.

Per ogni insieme prodotto, viene fornito dettagli sul clustering, come:

- quali punti appartengono a quali cluster
- quanti cluster
- quanti punti per cluster
- forma dei cluster
- etc.