Se per esempio si vuole considerare come livello di astrazione l’host della Url, baster`a passare il numero 1 come parametro della funzione e tutte le pagine che hanno lo stesso host saranno considerate come una sola UCitation.
2.6
Pivot-based clustering
Oltre alle molte funzionalit`a di preprocessing, all’interno del WOS, posso- no essere integrati algoritmi di data mining. All’interno della libreria `e stato introdotto anche un algoritmo di clustering per analizzare dati web.
Volendo, anche in questo caso, seguire un approccio pi`u generico possibi- le, per proporre meccanismi sfruttabili ai vari livelli, l’algoritmo permette di effettuare il clustering su un qualsiasi insieme di oggetti, basandosi di volta in volta su una funzione di similarit`a o distanza differente implementata dal- l’utente.
Il metodo di clustering proposto si basa sul partizionamento degli elementi iniziali in un certo numero di cluster stabilito a priori, ognuno rappresentato da un elemento significativo (pivot ), scelto in modo opportuno tra tutti gli elementi dell’insieme.
La scelta di un tipo di cluster basato sul centro si rivela una soluzione semplice e adatta al caso in cui gli elementi del dataset tendano naturalmen- te a suddividersi in sottoinsiemi. Una volta scelto il pivot dei cluster, ogni elemento verr`a associato al cluster dal cui centro ha distanza minima.
Diventa chiaramente cruciale la scelta dei pivot ed `e noto come una scelta casuale sia assolutamente inadatta e possa invalidare il risultato anche nel caso di una corretta scelta del numero dei cluster.
Tale selezione viene quindi fatta in modo iterativo, seguendo l’approccio suggerito in [29, 25]. L’idea base sta nel fatto che ogni elemento del dataset, una volta assegnato ad un cluster, si trover`a molto distante dagli elementi degli altri cluster, quanto meno se compariamo tale distanza con quella dagli oggetti appartenenti allo stesso cluster. In questo modo dato un insieme di pivot, possiamo cercarne uno nuovo tra gli elementi che sono pi`u distanti da tutti i centri gi`a selezionati [29].
66 Web Object Store
viduato nell’elemento che ha la distanza maggiore dagli altri pivot. Contem- poraneamente alla scelta del pivot successivo si ricalcolano le distanze degli elementi da quello scelto al passo precedente in modo da assegnare ogni ele- mento al cluster pi`u appropriato.
Al termine dell’algoritmo conosciamo tutti i centri, il cluster in cui `e stato inserito ogni elemento e la distanza dal suo centro. Poich´e tutti gli elementi vengono assegnati ad un cluster, ce ne saranno sicuramente alcuni che rap- presentano del rumore e quindi dovrebbero venir isolati. Questo pu`o essere fatto a seconda della funzione utilizzata nella distanza. Se, per esempio, con- sideriamo una funzione che pu`o assumere valori compresi nell’intervallo [0,1], se un elemento ha 1 come valore della distanza dal centro del cluster a cui appartiene, pu`o essere considerato rumore. Vedremo nel capitolo 5 un esem- pio di applicazione di questo algoritmo di clustering in cui `e utilizzata una distanza che soddisfa questa condizione.
Seguendo lo pseudocodice proposto nell’algoritmo 2.2, come parametri di input dell’algoritmo abbiamo il dataset iniziale (Repository rep), passato alla funzione sotto forma di repository WOS, una funzione che permette di calcolare la distanza tra due oggetti contenuti in esso (function Dist) e il numero di cluster (k) che vogliamo avere in output. E’ stato inserito tra i parametri opzionali del metodo, non indicato nello pseudocodice per rendere l’algoritmo pi`u leggibile, anche un cursore che permetta di effettuare il clu- stering solo su un sottoinsieme dei dati contenuti nel repository.
L’output dell’algoritmo consiste di tre vettori: il primo (cluster), di di- mensione pari al numero di cluster, contiene gli id degli oggetti che sono stati scelti come pivots, il secondo (centre) ha dimensione uguale al numero di elementi del repository e, in posizione corrispondente all’id di ogni ele- mento contiene l’identificatore del cluster a cui `e stato assegnato (cio`e l’id dell’elemento che rappresenta il centro del cluster) e il terzo (distance, inizia- lizzato ad un valore massimo max dist), che memorizza la distanza di ogni elemento dal cluster che lo contiene (cio`e la distanza dal suo centro).
2.2.6 Pivot-based clustering 67
Il primo dei k centri `e scelto in modo casuale (passo 1), e tutti gli oggetti vengono assegnati al cluster identificato da questo pivot, mentre i successi- vi sono individuati sulla base della distanza degli elementi dell’insieme dai cluster gi`a individuati.
In particolare, per ogni elemento del repository si calcola la distanza dal- l’ultimo centro selezionato: se tale valore `e minore della distanza dal centro del cluster di appartenenza, l’oggetto viene assegnato al nuovo cluster e il valore del vettore distance modificato di conseguenza (passi 4-8). Infine si sceglie come pivot successivo l’elemento che ha distanza massima dal “suo” centro (passo 9).
Al raggiungimento del numero voluto di pivots si procede all’eliminazione del rumore eliminando dai cluster gli elementi che hanno ancora una distanza dal centro pari a max dist (passo 10).
Algorithm 2.2 P ivot − based clustering Input: Repository rep contenente N elementi
function Dist
int k, numero di cluster Output: Vector cluster (dim k)
Vector centre (dim N ) Vector distance (dim N )
1. selezione di p ∈ rep
2. for i = 1 to k do
3. cluster[i] = p.id
4. for all element ∈ rep do
5. d = Dist(element, p) 6. distance[element.id] = M IN (distance[element.id], d) 7. if distance[element.id] = d then 8. centre[element.id] = i 9. p = rep.get by id(argmax(distance)) 10. for i = 1 to N do
11. if distance[i] = max dist then
68 Web Object Store
Dal punto di vista del costo computazionale l’algoritmo risulta efficiente in quanto ha un costo di O(kN) dove k `e il numero di cluster risultanti e N `
e il numero di elementi del dataset. Poich´e generalmente il numero di cluster `
e molto minore rispetto al numero degli elementi, il costo `e sostanzialmente lineare.
L’implementazione dell’algoritmo ben si presta ad utilizzare diverse no- zioni di distanza, poich´e sempre con l’obiettivo di rendere il pi`u semplice possibile la personalizzazione di ogni parte del sistema, la funzione che cal- cola la distanza tra due elementi `e un parametro di input del metodo invece che essere inglobato in esso.