Istanziazione dell’algoritmo

dei risultati mostrati all’utente eseguendo nuovamente le query estratte dal log file e basando il cluster su questi documenti.

La ricostruzione del comportamento dell’utente sarebbe stata possibile se le query fossero state sottomesse allo stesso motore di ricerca, in un istante temporale vicino a quello effettivo delle richieste memorizzate nel log. Chia- ramente questo non `e stato possibile, sia per evidenti ritardi temporali, sia perch´e todobr non ha a disposizione dei meccanismi per effettuare in modo automatico numerose query e memorizzarne opportunamente i risultati.

Il procedimento sviluppato si basa sulla considerazione che sottomettendo le interrogazioni in un momento diverso e a un diverso motore di ricerca, i risultati siano ragionevolmente simili, quantomeno per le query pi`u diffuse.

5.1.1

Istanziazione dell’algoritmo

Il metodo di clustering realizzato si basa sull’uso combinato del repository per dati web fornito dal Wos e dell’insieme dei dati raccolti attraverso l’ac- cesso ad un motore di ricerca che fornisce un gran numero di query effettuate.

A seconda del tipo di conoscenza che vogliamo estrarre `e possibile esegui- re il clustering sia su un insieme di sessioni, sia su un insieme di PageView. Nel primo caso si possono, per esempio, ottenere informazioni su quali query vengono eseguite pi`u spesso da pi`u utenti in una stessa sessione di navigazio- ne, nel secondo si pu`o essere interessati ad un pi`u classico raggruppamento testuale per capire quali stringhe sintatticamente diverse producono in realt`a risultati simili e utilizzare dati reali, di interrogazioni effettivamente richieste pu`o servire per limitare il numero di stringhe su cui effettuare l’analisi (cio`e limitarsi solo a quelle che in un certo periodo di tempo sono state cercate almeno un numero minimo volte).

Nel caso si voglia effettuare un clustering sulle sessioni `e bene osservare come, in questo specifico caso, non abbia senso utilizzare delle Q-Session, che non darebbero le stesse informazioni estraibili nel caso di sessioni inter-site, in quanto identificando le Q-Session di un motore di ricerca otterremo sempre l’aggregazione di una o al massimo due PageView: la pagina principale, in cui l’utente immette la query, e se presente, la pagina con i risultati.

106 Casi d’uso

ritmo di data mining fornito, ma sono necessarie delle operazioni preliminari che preparino l’ambiente e i dati aggiuntivi su cui eseguire il clustering. Per poter applicare l’algoritmo infatti `e necessario recuperare l’insieme delle que- ry e quello dei risultati.

Possiamo isolare i seguenti passi:

1. Estrazione delle query: permette di isolare tutte le stringhe rappre- sentanti le interrogazioni al motore di ricerca

2. Esecuzione delle query: a partire dalle stringhe ottenute al passo precedente vengono rieseguite le stesse query a Google per raccogliere i risultati

3. Memorizzazione dei risultati: i documenti risultanti dalle query eseguite vengono memorizzati in modo opportuno per poter essere utilizzati durante l’algoritmo di clustering

4. Esecuzione algoritmo di clustering: otteniamo una suddivisione dell’insieme iniziale in un certo numero di cluster.

Estrazione delle query

Il primo passo di quella che possiamo considerare come un’ulteriore fase di preprocessing, specifica per il clustering di sessioni, consiste nel recupe- rare tutte le query delle richieste HTTP costituenti l’insieme di oggetti da analizzare. Parliamo di insieme di oggetti poich´e, come detto, il clustering `e abbastanza generico da poter essere eseguito su diversi tipi di collezioni.

L’estrazione delle query dalle PageView (in ogni caso si va a lavorare sul- le PageView, siano esse prese come componenti di sessioni, o come oggetti autonomi) `e molto semplice, come possiamo osservare nell’algortimo 5.1, in quanto il contenuto di un eventuale query era gi`a stato isolato dai parametri della Url durante la fase di parsing e memorizzato nel campo query dell’og- getto HttpRequest. L’unica ulteriore elaborazione che viene fatta in questo passaggio `e evitare di copiare due volte la stessa query, in modo da evitare al passo successivo l’esecuzione di due query identiche che produrranno neces- sariamente lo stesso insieme di risultati, se eseguite in uno stesso momento. Per questo mano a mano che si legge il campo query degli oggetti, prima di

5.5.1.1 Istanziazione dell’algoritmo 107

copiare la stringa sul file in output si controlla se non sia gi`a presente in una struttura dati ausiliaria atta a questo scopo. Se la stringa non `e presente, viene aggiunta sia al file che alla struttura dati.

Algorithm 5.1 Estrazione query Input: Repository rep

1. while rep.next() do

2. query = rep.get().query

3. if (query != 0−0_{) and (query /∈ querySet) then}

4. querySet.insert(query)

5. stampa query su file

Esecuzione delle query – Google API

Poich´e si vuole realizzare un algoritmo di clustering che basa la nozione di similarit`a sul numero di risultati comuni, `e necessario ottenere questi risultati che non sono presenti nel log file in quanto riguardano pagine ospitate su altri host. A questo scopo `e stata utilizzata la funzionalit`a messa a disposizione da Google, che permette di eseguire delle query attraverso delle interfacce per alcuni linguaggi di programmazione. Poich´e per C++ non sono fornite delle interfacce, per semplicit`a `e stato utilizzato uno script Perl, che con poche righe di codice permette di eseguire una o pi`u query. Per questo motivo le query non possono essere eseguite immediatamente al momento dell’estra- zione dalle richieste HTTP. E’ stata fatta questa scelta poich´e `e stata data maggiore importanza alla fase di clustering, che comunque `e indipendente dal modo in cui vengono ottenuti i risultati delle query. Sar`a sempre possibile in seguito ottimizzare anche questa fase implementando delle interfacce C++ attraverso il Web Service fornito da Google.

Attraverso un semplice script Perl `e possibile eseguire una query spe- cificando tutti i parametri necessari, in modo da simulare correttamente il comportamento di un utente che esegue l’interrogazione accedendo al motore di ricerca dal web.

L’utilizzo dello script si `e rivelato ottimale anche per elaborare le query estrat- te dalle richieste HTTP, poich´e la stringa estratta dalla Url non `e identica

108 Casi d’uso

a quella digitata dall’utente al momento della ricerca poich´e vengono sosti- tuiti i caratteri speciali come per esempio le virgolette. E’ stato necessario affrontare questo problema in quanto la presenza di virgolette richiede che i termini racchiusi al loro interno siano ricercati nell’esatto ordine, mentre se non sono presenti un documento `e restituito come risultato se contiene tutte le parole in una qualsiasi combinazione.

Una volta trascritto l’elenco delle query da eseguire su un file, viene eseguito il seguente script per ogni riga del file:

#sostituzione %XX con i corrispondenti caratteri $r=~s/%([0-9a-zA-Z]{2})/chr(hex($1))/eg;

print OUTPUT "#".$r;

my $googleSearch = SOAP::Lite -> service("file:GoogleSearch.wsdl"); my $results = $googleSearch -> doGoogleSearch($key, $r, 0, 5,

"false", "", "false", "", "latin1", "latin1"); @{$results->{resultElements}} or exit;

# Loop through the results

foreach my $result (@{$results->{resultElements}}) print OUTPUT $result->{URL}."\n";

La prima riga sostituisce ogni occorrenza di %XX con i corrispondenti caratteri e la query cos`ı modificata viene copiata nel file che conterr`a i do- cumenti trovati, aggiungendo un simbolo iniziale per identificare che quella stringa `e la query e non una delle Url restituite come risultato.

Con i successivi comandi si avvia l’esecuzione vera e propria che memoriz- za nel vettore results->resultElements le Url corrispondenti alla query, in

numero pari al massimo specificato nel quarto parametro della richiesta (nel- l’esempio si restituiscono al massimo 5 link). Come ultima azione si scrivono sul file di output le Url delle pagine risultanti.

Tale file verr`a processato da un metodo C++, descritto nel prossimo paragrafo.

5.5.1.1 Istanziazione dell’algoritmo 109

Memorizzazione dei risultati

Dopo aver eseguito il passo precedente abbiamo a disposizione un file di testo organizzato nel modo seguente:

#query1 urlA urlB ... #query2 urlB urlC ... ...

Occorre adesso memorizzare i risultati ottenuti in un modo strutturato, che ne permetta un efficiente e comodo recupero durante l’esecuzione dell’algorit- mo di clustering. Per questo possiamo utilizzare il metodo di archiviazione del Wos, creando un oggetto QueryResult e un repository che render`a persistenti le istanze di tali oggetti.

L’oggetto QueryResult contiene due campi:

char* query che registra la stringa rappresentante la query

(int dbArray results) che contiene degli interi che rappresentano ognuno un risultato dell’esecuzione della query.

Per popolare il repository ed associare ad ogni oggetto l’elenco dei docu- menti proposti da Google, si utilizza un repository temporaneo contenente oggetti di tipo Uri. Leggendo dal file di testo prodotto al passo precedente, per ogni query string si crea un’istanza della classe QueryResult, se non `e gi`a presente un oggetto con identico valore del campo query. Successivamente, per ogni Url risultato, si cerca di inserire la Url nel database temporaneo creato e, con un procedimento simile a quello seguito nella fase di parsing, si recupera l’id dell’oggetto.

In questo modo `e anche possibile all’occorrenza recuperare le Url corri- spondenti ai risultati ottenuti per ogni query eseguita.

110 Casi d’uso

Tale id viene aggiunto al vettore dell’oggetto QueryResult, in modo da mantenere il vettore ordinato in modo crescente. Il vettore contenente i ri- sultati delle query `e memorizzato in modo ordinato per ottimizzare il calcolo della distanza, rendendo lineare il costo del confronto tra due vettori.

Il procedimento seguito `e mostrato nell’algoritmo 5.2 . Algorithm 5.2 Memorizzazione risultati query

Input: File result

1. for all riga in f ile do

2. if riga[0] = 0#0 then

3. if queryResult != null then

4. queryResult.results.sort()

5. resultRepository.insert(queryResult)

6. else

7. queryResult = new QueryResult(riga)

8. else

9. qU ri = uriRepository.get by uri(riga)

10. if qU ri = null then

11. qU ri = new U ri(qU ri)

12. uriRepository.insert(qU ri)

13. queryResult.results.insert(qU ri.id)

Esecuzione del clustering

L’esecuzione del passo di clustering vero e proprio `e eseguita utilizzando l’algoritmo proposto all’interno del WOS, che pu`o venir applicato a partire da un insieme di page view o da un insieme di sessioni.

Per adattare il clustering a questo specifico contesto `e fondamentale la scelta della distanza da utilizzare. Per calcolare la distanza tra due query session ci si basa sui risultati delle query contenute nella sessione. Ci`o che abbiamo a disposizione `e, per ogni query, l’elenco dei risultati, codificati ognuno con un id che identifica univocamente ogni Url.