Book and Authors, an idea from Sergei Brin

Traduzione e Integrazione delle Lezioni a cura di Sandro Gallo

Home Web Mining e DICE Clustering

Sergei Brin propose per la ricerca un modello chiamato Books and Authors. Questo modello si basa sulla costruzione di pattern usando dati buoni e riusando i pattern per cercarne di nuovi.
Un pattern è fatto di cinque elementi:

  1. Ordinamento degli elementi della tupla.
  2. Presiffo URL.
  3. Prefisso del testo.
  4. Elemento di mezzo del testo.
  5. Suffisso del testo.
Prefisso e suffisso devono occupare meno di 10 caratteri.
Le regole di Brin perchè un pattern possa essere accettato sono:
  1. Devono esserci almeno due tuple buone conosciute.
  2. Il prodotto della specificità di un pattern per il numero di occorrenze delle tuple che esso definisce deve superare una certa soglia s.
La specificità è definita come il prodottto delle lunghezze del prefisso, del suffisso e dell'elemento di mezzo del testo, e il prefisso URL.
Una occorrenza di tupla è associata ad un pattern, perchè la stessa tupla può essere identificata da pattern diversi. Quindi ogni occorrenza di dati trovata è identificata da:
  1. I particolari valori.
  2. L'URL completo.
  3. L'ordine, il prefisso, l'elemento di mezzo e il suffisso del pattern dove i particolari valori trovati occorrono.
L'algoritmo di Sergei Brin procede nel seguente modo:
  1. Iniziamo con un insieme di tuple buone.
  2. Cerchiamole sul web e proviamo a trovare pattern sufficientemente specifici ma non troppo.
  3. Dato un insieme di pattern buoni trova i dati identificati da quei pattern e aggiungili all'insieme di dati buoni.
  4. Ripeti i passi 2. e 3. diverse volte.
Vediamo ogni singolo passo:
  1. Date le tuple buone usiamo una tecnica A-priori, cioè (supponendo che ci sia qualche modo per indicizzare le parole e le pagine che le contengono) cerchiamo l'autore, poi cerchiamo il titolo. Quindi intersechiamo i risultati delle due ricerche. Come prefisso e suffisso del test prendiamo non più di 10 caratteri a sinistra e a destra.
  2. Il passo due procede così:
    1. Raggruppo le occorrenze fissando l'elemento di mezzo e l'ordine.
    2. Per ogni gruppo troviamo il prefisso e il suffisso più lungo del testo e prefisso URL comune a tutti.
    3. Se il test di Specificità di Brin è Ok, accetta un pattern, altrimenti estendo il prefisso URL di un carattere spaccando in due il gruppo e ripeto dal passo 2. Se non si spacca vuol dire che non può essere prodotto un pattern per quei dati.
  3. Il terzo passo procede così:
    1. Trova tutti gli URL che contengono il prefisso URL di almeno un pattern.
    2. Per ogni pagina usa il pattern associato per cercare al suo interno
    3. Da ogni match estrai titolo e autore in accordo con l'ordine specificato nel pattern.

Home Web Mining e DICE Clustering