• B
    User •

    Metamotori e calcolo del ranking

    Ciao a tutti!

    Sto facendo un lavoro di tesi su un'integrazione di un motore di ricerca all'interno di un sistema documentale.

    La mia esigenza è questa:

    • Ho un oggetto
    • A partire da questo oggetto genero delle query di ricerca
    • Eseguo queste query di ricerca su uno (o più?) motori
    • Ottengo dei risultati
    • Devo effettuare il merge dei risultati.

    Qui mi trovo un attimo in difficoltà: supponiamo che io abbia come risultati elenchi di questo tipo

    ELENCO 1)
    Pagina1 Rank: X1
    Pagina2 Rank: X2
    Pagina3 Rank: X3

    ELENCO 2)
    Pagina2 Rank: Y2
    Pagina4 Rank: Y4
    Pagina3 Rank: Y3

    ELENCO 3)
    Pagina3 Rank: Z3
    Pagina4 Rank: Z4
    Pagina1 Rank: Z1

    (per semplicità, tutti i rank sono compresi nello stesso intervallo, ad esempio tra 0 e 100)

    Devo quindi ottenere un elenco del tipo:

    Pagina1 Rank: rankFinale(X1,Z1)
    Pagina2 Rank: rankFinale(X2,Y2)
    Pagina3 Rank: rankFinale(X3,Y3,Z3)
    Pagina4 Rank: rankFinale(Y4,Z4)

    Dove posso trovare un algoritmo per definire la funzione rankFinale(), che a partire dai rank di ogni motore mi restiuisca un rank per l'inserimento nel mio elenco finale?

    La rimozione dei duplicati non la vedo difficile, è proprio sul calcolo del rank finale che mi vedo spaesato...

    Vedo bene un discorso relativo ai metamotori di ricerca, ma dove posso trovare degli esempi di algoritmo di aggregazione di risultati?

    0
  • paocavo
    Moderatore •

    Ciao Bondo,
    che bel quesito interessante! 😉 .
    Una risposta abbastanza banale potrebbe essere quella di effettuare una semplice media aritmetica dei rank posti in ingresso alla funzione. Questo sotto l'ipotesi che i rank siano omogenei nel senso che appartengano allo stesso dominio (range di variabilità).
    Dall'esempio che hai fatto osservo che il numero di input in ingresso della funzione rankFinale è variabile da 1 a N dove è il numero di MDR scelti.
    In questo caso che fai nei parametri mancanti? ci passi zero?
    Volendo complicare un pò le cose si potrebbe pensare ad una media pesata dei rank dove i pesi, fissati da te, potrebbero essere ad esempio legati alla "attendibilità" dei motori di ricerca utilizzati per generare i set iniziali di risultati o legati ad altri fattori, per esempio alla "vicinanza" dei risultati con l'Oggetto di studio iniziale. Per "vicinanza" potresti, inizialmente, considerare il numero di componenti elementari (parole?) in comune tra L'oogetto di Studio e l'i-mo risultato restituito dal motore.
    Se poi vuoi fare le cose in grande allora devi passare ad adottare algoritmi di clustering k-means e/o Vector space Model
    In passato abbiamo ampiamente discusso di questi algoritmi. Cerca nel Forum ed, ovviamente, su Google!

    PS: Ecco il codice Java che implementa l'algoritmo K-means nel caso bidimensionale (ma è (abbastanza) facilmente estendibile al caso N-dimensionale)

    :ciauz:

    0
  • B
    User •

    Osservo un'altra cosa: un conto è ragionare a livello di ranking, un conto è ragionare a livello di rating/confidence.

    Ora ho fatto dei ragionamenti a livello di rating: la media aritmetica sarbebe assurda.
    Il ragionamento che ci sta dietro è: sul motore M1 trovo il link L1 con rating R1M1 e il link L2 con rating R2M1.
    Sul motore M2 trovo il link L3 con ranting R3M2 e il link L2 con rating R2M2.
    A questo punto mi viene da dire che il rating di L1 e di L3 rimangono invariati, mentre invece il calcolo è da fare sul rating di L2.
    E qui nulla è facile: il fatto che sia presente in due SERP implica che potrebbe essere piu' "importante" degli altri due link.
    Pertanto il nuovo rating non dovrebbe essere inferiore del valore massimo tra R2M1 e R2M2.
    L'incremento deve quidni essere proporzionale ai due valori, onde evitare incrementi troppo elevati che generino dei falsi positivi.

    Ragionando e facendo due conti ho trovato questa formuletta che può andar bene in quando prende in considerazione due valori alla volta e rispetta un po' di requisiti (commutatività, non decrescenza, associatività, nessun problema di risommazione, ideale in processi iterativi di ricerca di duplicati e compagnia bella): RadQ(1-(1-R2M1R2M1)(1-R2M2*R2M2))
    (ovviamente i valori di rating sono compresi tra 0 e 1)

    Ovviamente prima posso comunque pesare i due valori in base all'"attendibilità" dei motori di ricerca.

    Non è un granché, ma come punto di partenza per iniziare a fare due esperimenti non mi sembra niente male...

    Passando ad un discorso Ranking, questo sitema pero' non sta piu' in piedi.

    Poi si possono valutare sistemi diversi: ad esempio, Mamma.com utilizza una semplificazione di un algoritmo utilizzato nei calcoli relativi ai sistemi di voto (sul ranking però).
    In effetti combinare sistemi di voto rating con sistemi proporzionali qualcosa se ne tirerebbe fuori, ma probabilmetne questo sarebbe un lavoro di tesi a parte.

    Su una cosa sono certo: non voglio mettermi a fare considerazioni sul contenuto, ma esclusivamente calcoli matematici in base al ranking o al rating restituito.

    Tra l'altro, la conversione da sistema di rating a sistema di ranking è relativamente semplice, diverso è l'incontrario (a meno di non voler assegnare rating predefiniti alle prime n posizioni).

    0
  • lowlevel
    Super User •

    @Bondo said:

    Dove posso trovare un algoritmo per definire la funzione rankFinale(), che a partire dai rank di ogni motore mi restiuisca un rank per l'inserimento nel mio elenco finale?

    Eh... dipende davvero da tantissime cose. Da che tipo di meta search engine vuoi creare, dagli elementi a cui vuoi attribuire più peso...

    Purtroppo non ho molto tempo, ma dai un'occhiata a come gli algoritmi che gestiscono il data fusion (tipico di scenari diversi da quello sul quale stai lavorando tu) possono venirti comunque in aiuto: [url=http://www.ischool.utexas.edu/~i385df04/readings/Meng(2002)-mewtasearch_engines.pdf]ecco qua.

    (in particolare fai qualche ricerca su Google Scholar sulle funzioni CombMNX e CombSUM)

    0
  • B
    User •

    Magico! Questo articolo è proprio quello che mi serve per iniziare!

    In realtà il mio sistema interagirà non tanto con piu' motori di ricerca, ma con piu' query simili sullo stesso motore di ricerca (esempio del cavolo, ad esempio se voglio trovare casa a Milano eseguirà le query "Cerco casa Milano", "Annunci Immobiliari Milano", "Appartamenti in affitto a Milano", "Case in vendita a Milano" e così via) e alla fine farà il merge dei risultati.
    Sbaglio a dire che il ragionamento comunque alla fine della fiera è simile al discorso dei metamotori?

    Poi il discorso teorico/sperimentale abbracciato al discorso di tesi è che un un insieme di query da eseguire, un insieme di motori di ricerca su cui eseguire la mia query, con un subset di query che viene eseguita su un subset di motori di ricerca (eg. Query=A,B,C Motori=1,2,3: esegui la query A sui motori 1 e 2, la query B solo sul motore 3, la query C su tutti i motori) e alla fine ottengo un risultato.

    Ah puntualizzo questo: nel mio caso le query non sono generate in automatico ma sono configurate dall'utente (se no sì che si incasinava il tutto.. ma questa è un'altra storia e ci vorrebbe un discorso di tesi solo qui).
    Poi, sempre a livello teorico di architettura, si può pensare al modulo di "conversione" di query per i vari motori (tra l'altro, ho visto una cosa del genere nella gesione degli ECIS Adapter in Documentum - che credo essere l'unico documentale in cui viene gestita una cosa del genere), ma direi che non posso sviluppare un sistema completo di questo tipo per una tesi... altrimenti mi danno la laurea Honoris Causa se lo faccio tutto solo soletto 🙂

    0
  • lowlevel
    Super User •

    @Bondo said:

    In realtà il mio sistema interagirà non tanto con piu' motori di ricerca, ma con piu' query simili sullo stesso motore di ricerca

    Questo cambia molto le cose, ad esempio...

    Sbaglio a dire che il ragionamento comunque alla fine della fiera è simile al discorso dei metamotori?

    Non sbagli. Tecnicamente si tratta anche in questo caso di meta-ricerca, anche se ci si avvicina di molto agli algoritmi di query expansion tipici dei normali motori di ricerca (non meta).

    Nel documento che ti ho segnalato dovresti trovare anche delle distinzioni tra le varie tipologie di meta-motori. Dico "dovresti" perché vado un po' a memoria e non ricordo perfettamente quali distinzioni e classificazioni dei meta-motori venivano fatte.

    La prima domanda che mi viene in mente è: "Tu possiedi solo i risultati delle singole ricerche (le SERP) o anche le informazioni che hanno prodotto quei risultati?

    Nel secondo caso la soluzione potrebbe essere piuttosto semplice.

    0
  • B
    User •

    Io ho le query e le SERP.

    Fondamentalmente ora inizio a lavorare con un Google Server Appliance, a cui passo le query e ottengo il risultato in XML.

    0
Effettua l'accesso per rispondere