News correlate: migliorare l'algoritmo

Uno degli script di cui sono davvero orgoglioso è quello delle news correlate. Certo non è perfetto, ma per un algoritmo a cui ho lavorato un paio di settimane questo sta producendo risultati davvero eccellenti. Adesso che è online da qualche mese sento il bisogno di tornare a metterci mano per migliorarlo.

La prima cosa da fare è velocizzare l'algoritmo stesso. Per pura pigrizia, quando lo scrissi, optai per del codice più semplice anche dove del codice più complesso sarebbe stato più veloce. Ovviamente ho guadagnato tempo quando ho scritto il codice e ne ho perso il doppio quando ho dovuto riscriverlo.

Qui però ci vogliono un paio di parole di spiegazione.

L'algoritmo che decide se due news sono correlate è diviso in due parti.
Nella prima viene letta una news e si cerca di capire quali sono le parole chiave in questa news: ovvero si crea una mappa. Questa mappa - e qui viene dimostrata la mia pigrizia - viene salvata come una semplice stringa.
Nella seconda parte l'algoritmo paragona le mappe e decide se due news parlano dello stesso argomento.

Il problema è che salvando la mappa di una news come una stringa - invece di creare una tabella SQL in cui ogni parola della mappa riceve un codice ID unico e un'altra tabella in cui ogni ID di una parola viene associato all'ID di una news - i paragoni tra le stringhe diventano un'operazione lentissima.

Indicizzando le parole all'interno delle mappe ho quindi velocizzato l'algoritmo, ma la qualità dei risultati è sempre la stessa. Ho dunque sentito il mio amico zello e gli ho parlato della mia idea di migliorare l'algoritmo.

Allo stato attuale, l'algoritmo è composto da un numero di formule e da 10 variabili che vanno definite arbitrariamente. Ora, se queste variabili potessero assumere anche solo valori che vanno da 1 a 10, vorrebbe dire che le possibili combinazioni di queste variabili sono 10.000.000.000 (10 miliardi). In modo da migliorare lo script bisognerebbe testare tutte queste possibili combinazioni e vedere quale dia il risultato migliore.

Il problema è che con Apache, PHP e MySql montati su Windows al massimo si arriva al calcolo di qualche combinazione al secondo (se tutto va bene). Questo significa che ci vorrebbero diversi anni per arrivare a provarle tutte. Certo, se si escludono le combinazioni impossibili il tempo di calcolo scende - ad esempio io assegno un punteggio alle parole che appaiono nel titolo e un punteggio a quelle che appaiono nel corpo del testo: è avvio che il primo punteggio non potrà mai essere inferiore al secondo -, ma non scende abbastanza da fare la differenza.

Per fortuna, però, che zello è un grande programmatore di C/C++ e che ha molta pazienza quando parla con me e che ha deciso di aiutarmi scrivendo un programma che testi tutte le combinazioni. Abbiamo fatto qualche test con una prima bozza del suo programma e ci siamo accorti che neanche in C++ raggiungeremmo una velocità tale da poter calcolare tutte queste combinazioni (purtroppo funzioni come la distanza Levenshtein e lo stemming delle parole richiedono molta potenza di calcolo).

Abbiamo cercato il modo di ridurre la complessità, ma ci siamo resi conto che tutte le nostre idee sono in realtà delle ottimizzazioni, non qualcosa che ci permette di passare da 10 miliardi di combinazioni a centomila. L'unico sistema, ci siamo detti, è quello di usare solo un campione di news. Un conto è calcolare i 10 miliardi di combinazioni su 28.000 news e un conto è fare la stessa cosa su un campione scelto di qualche centinaia.

L'idea che stiamo seguendo ora e quindi quella di scegliere qualche centinaio di coppie news e specificare se queste sono correlate o meno. La combinazione di variabili che più di queste coppie troverà sarà usata per calcolare le correlazioni tra tutte 28.000 le news.

Adesso stiamo quindi a vedere quanto riusciamo a migliorare l'algoritmo.