Whatsup 0.1: tipologia dei dati e algoritmo di clustering

L’algoritmo di clustering che ho sviluppato è estremamente semplice ma riesce ad ottenere discreti risultati nonostante l’esiguità di dati.

Il “nonostante” si applica perché in Information Retrieval la bontà di molte soluzioni non si fonda principalmente sulla qualità degli algoritmi bensì sulla qualità delle informazioni sulle quali gli algoritmi devono lavorare.

Uno stesso algoritmo può produrre risultati scadenti se applicato a pochi dati e risultati ottimi se applicato a basi di dati molto grandi. Google non è il leader nell’IR solo perché sviluppa buoni algoritmi ma anche perché disponde di una gigantesca quantità di informazioni sulla quale farli macinare.

Le informazioni prese in esame da Whatsup sono le keyphrase cercate dagli utenti su Google e, trattandosi nello specifico delle sole keyphrase che in un dato istante mostrano un picco di ricerche, la loro quantità è limitata. Attraverso i metodi che sto sfruttando al momento, la quantità delle keyphrase “hot” che è possibile estrarre da Google varia da 100 a 200 elementi.

Fortunatamente, nonostante la quantità non sia alta, i dati possiedono caratteristiche che vengono facilmente incontro anche all’algoritmo di clustering più semplice. In particolare, gli utenti sul Web cercano informazioni su uno specifico soggetto digitando ricerche molto diverse, varianti che fanno uso di sinonimi e altre che ripropongono le stesse parole in ordine differente.

A seguito di un’estrazione di keyphrase “di picco” da Google capita quindi che diverse di esse facciano riferimento allo stesso tema, usando parole e variazioni leggermente diverse, ma facilmente accomunabili da una o più parole in comune.

Di fronte a questi elementi di similarità, ho pensato che buoni risultati potessero essere ottenuti anche con un semplice algoritmo di clustering che cercasse nelle keyphrase la presenza di parole “importanti”. Ma cosa si intende per “importante”?

Il concetto di importanza va definito. Nel contesto in cui sto operando, ovvero un elenco di keyphrase “hot”, una parola che posso considerare importante potrebbe essere una parola che si ripete in più keyphrase. Più sono le keyphrase in cui la parola è presente e più essa può essere considerata importante per questo specifico contesto.

Tradotto in numeri, significa che il mio concetto di importanza si può limitare per il momento a calcolare la frequenza di ciascuna parola all’interno del corpus (in questo caso l’elenco delle keyphrase) e considerare importanti i termini che sono più frequenti.

Il metodo funziona bene solo se tiene conto del fatto che esistono particelle linguistiche che possono apparire frequentemente nelle keyphrase (articoli, preposizioni, ecc.) ma che non dovrebbero essere considerate importanti.

Le soluzioni per evitare che le particelle del discorso frequenti in lingua italiana inficino i risultati, sono sostanzialmente due: usare una lista di stop words oppure riuscire ad assegnare un peso inferiore o nullo a tali termini sfruttando statistiche su un corpus più grande.

Nonostante io possieda un grande storico delle ricerche su Google (in particolare su Google News), nella versione 0.1 di Whatsup mi sono limitato a usare una semplice lista di stop words. E’ stato veloce, indolore ed i risultati non sono niente male. Ovviamente le versioni successive di Whatsup preferiranno implementare soluzioni basate sull’analisi di dati storici.

Ho preso una lista di stop words italiane da qua, ne ho aggiunta qualcuna che mancava all’appello (es: “quando”) e ho prodotto una seconda lista di termini molto generici, come “news”, “notizie”, “video” o “ansa”. Ho infatti deciso di gestire normalmente questi termini tranne che durante la scelta dei nomi da attribuire ai cluster, che desidero incentrare su parole più specifiche.

Ecco dunque di seguito l’algoritmo finale di Whatsup 0.1, già obsoleto nel momento in cui scrivo ma che vi riporto perché nei post successivi sarà più facile spiegare il motivo di alcuni cambiamenti fatti nelle versioni successive del software, via via che ho acquisito visibilità sulla qualità della classificazione.

Primo clustering fatto a mano con XMind

1. Estraggo la parola più frequente nelle keyphrase (escludendo le stop words)
2. Creo un cluster e lo chiamo come la parola trovata
3. Assegno al cluster tutte le keyphrase che contengono la parola
4. Una volta che una keyphrase viene assegnata ad un cluster, viene tolta dal bacino di keyphrase dalle quali estrarre, al prossimo giro, la nuova parola più frequente
5. Prossimo giro: si torna al punto 1 fino a quando ci saranno parole ripetute in almeno due keyphrase diverse
6. A questo punto rimarranno solo keyphrase che non contengono alcuna delle parole usate per dare nome ai cluster. Per ciascuna keyphrase non assegnata, l’assegno al cluster che condivide con essa la quantità maggiore di parole.
7. Tutto ciò che rimane termina in un cluster speciale che chiamo “UNCATEGORIZED”

Pubblico nuovamente l’immagine con il risultato del clustering dell’algoritmo appena descritto.

Nei prossimi post vedremo i limiti del presente approccio e che cosa ho deciso di cambiare nelle versioni successive di Whatsup.