Clustering e Probabilistic Rand Index

Uno dei punti deboli dell’attuale tecnologia dei motori di ricerca è costituito dalla modalità di presentazione dei risultati, offerti come una lista di elementi spesso ridondanti e senza nessuna organizzazione logica. I motori di ricerca a categorie (clustering engines) offrono uno schema di visualizzazione complementare, in cui i risultati recuperati da un motore di ricerca tradizionale vengono successivamente raggruppati in categorie omogenee, alle quali l’utente può accedere in modo indipendente. La diversificazione è la seconda strategia più diffusa per migliorare l’output dei motori di ricerca, e si basa sul principio che la collocazione di un risultato ai primi posti dipenda non soltanto dal valore intrinseco di quel risultato, ma anche dalla ridondanza rispetto agli elementi che lo precedono.

KeySRC (Keyphrase-based Search Results Clustering) è un esempio di clustering engine innovativo, sviluppato in FUB e accessibile su Web (http://keysrc.fub.it/Keysrc/), che si caratterizza per l’elevata espressività delle descrizioni delle categorie. Nel 2010, KeySRC è stato esteso per farne anche uno strumento di diversificazione dei risultati. Le prestazioni di KeySRC, utilizzato nelle due modalità, sono state confrontate con sistemi alternativi, ottenendo risultati generalmente positivi e ascrivibili alla precisione con la quale l’utente riesce a discriminare il contenuto dei cluster creati da KeySRC. L’analisi delle prestazioni di KeySRC si è successivamente evoluta in una valutazione complessiva dell’efficacia dei sistemi per subtopic retrieval, mettendo direttamente a confronto le due strategie principali (clustering e diversificazione). Ne è emerso che le due strategie sono essenzialmente complementari: il clustering funziona meglio quando siamo interessati a recuperare documenti multipli che afferiscono a ciascuna subtopic, mentre la diversificazione è preferibile quando l’obiettivo è di coprire il maggior numero possibile di subtopic con almeno un documento. Nel corso del 2011, le prestazioni del clustering engine KeySRC sono state analizzate con tecniche più robuste e confrontate con altri sistemi di questo tipo. Le nuove valutazioni hanno confermato che l'utilizzazione di KeySRC consente di ottenere prestazioni migliori in termini  del numero di documenti recuperati afferenti a singole “subtopic”, in virtù della maggiore precisione con la quale le etichette create dal sistema identificano il contenuto dei cluster alle quali esse sono associate. I risultati di questi esperimenti sono stati pubblicati sulla rivista Web Intelligence and Agent Systems.

Così come i risultati prodotti da motori di ricerca distinti possono essere fusi in un meta motore di ricerca, con l’obiettivo di valorizzare gli elementi presenti in più ranking, anche per i clustering engine è pensabile combinare gli output in un unico clustering di risultati più robusto e preciso. Quest’analogia ha condotto alla definizione, implementazione e validazione di un metodo per fondere i clustering (partizioni) prodotti da un insieme di clustering engine di input in un meta clustering engine. È un approccio nuovo, proposto da FUB per la prima volta.
È stato definito un indice di somiglianza fra due partizioni, basato sulla concordanza probabilistica delle decisioni assunte dalle due partizioni rispetto alle possibili coppie di risultati da partizionare. Successivamente, il problema di meta-clustering è stato formulato come un problema di ottimizzazione della concordanza fra la meta partizione e le partizioni di input, ed è stato dimostrato che metodi di calcolo euristici molto efficienti producono soluzioni con un buon grado di approssimazione. La validazione è consistita nell’esaminare le proprietà della meta partizione rispetto alle partizioni individuali, ed ha evidenziato un miglioramento di prestazioni sia rispetto alla riconoscibilità dei cluster nello spazio delle caratteristiche, sia rispetto all’utilizzazione delle partizioni come sistema interattivo per browsing retrieval, sia infine per quanto riguarda la capacità di ricreare classificazioni naturali note a priori.

Il lavoro sulla fusione di clustering multipli iniziato nel 2010 ha condotto alla definizione di una nuova versione probabilistica del ben noto Rand Index, per stabilire la similarità fra due partizioni di un insieme di oggetti. L’indice di Rand è basato sul conteggio del numero di volte in cui ciascuna coppia di oggetti da partizionare è stata classificata nello stesso gruppo o in gruppi distinti dalle due partizioni. Il suo limite principale è che non tiene conto del fatto che il numero di cluster presenti in una partizione influenza la possibilità che due oggetti siano raggruppati insieme o meno. Partendo da questa osservazione abbiamo definito un nuovo indice, denominato Probabilistic Rand Index, nel quale alle concordanze e discordanze presenti nella classificazione di ciascuna coppia di oggetti nelle due partizioni vengono assegnati dei pesi basati sulle loro probabilità casuali di occorrenza. Successivamente, questo nuovo indice è stato utilizzato come criterio da ottimizzare nella combinazione di clustering multipli (consensus clustering), realizzata mediante un metodo stocastico semplice ma molto efficiente. Ai fini della valutazione delle prestazioni dello schema complessivo, sono stati analizzati sia classici problemi di riconoscimento di cluster non convessi o rumorosi, sia l’applicazione del consensus clustering al problema di riconoscere ed etichettare i temi presenti nell’elenco dei risultati restituiti da un motore di ricerca (subtopic retrieval). Questo lavoro sarà pubblicato sulla prestigiosa rivista IEEE Pattern Analysis and Machine Intelligence.