Curs nr. 05 - Cautare.pdf

Modele de cautare Discutii Bibliografie

Regasirea Informatiilor pe WEBCurs 05: Modele de cautare

s.l. dr. ing. Alexandru [email protected]

Facultatea de Automatica si Calculatoare, Iasi

an universitar: 2014 2015

RIWeb 2014 2015/C05: Modele cautare. Web Mining 1/ 15


Cuprins

1 Modele de cautareNotiuni introductiveModelul booleanModelul bazat pe reprezentare vectoriala

2 Discutii



Notiuni introductive

Motor de cautare pe WEB

Figura 1: Arhitectura generala a motoarelor de catare pe WEB [2]





Sistem de regasire a informatiilor

Functia unui sistem de regasire a informatiilor este de a prelua interogarea unuiutilizator, de a prelucra aceasta interogare si de a ntoarce utilizatorului unsubset de documente ce satisfac interogarea n discutie [5].

In mod uzual rezultatele sunt sortate relativ la relevanta fata de interogareaintordusa de utilizator.

Etape implicate

1 utilizatorul introduce o interogare;

2 interogarea este procesata si modelata conform modelului de cautare aldocumentelor tinta;

3 documentele determinate ca fiind corespunzatoare interogarii sunt sortateconform cu functia de relevanta inclusa de sistemul de regasire a informatiilor;

4 rezultatele sunt prezentate utilizatorului.




Notiuni introductive (2)

Figura 2: Schema generala a unui sistem de regasire de informatii si etapele implicate [5]




Notiuni introductive (3)

Forme de interogare [5]

1 interogare de tip cuvinte cheie

2 interogare de tip boolean

3 interogari de tip expresie

4 interogari de tip distanta

5 interogari de documente

6 interogari n limbaj natural




Modele de cautare

Ce nseamna model de cautare?

Un model de cautare specifica [3,5]:

un mod de reprezentare/organizare al documentelor;un mod de reprezentare/organizare al interogarii;un mod de stabilire a relevantei unui document relativ la o interogare.




Modele de cautare (2)

Premise

Un sistem de regasire a informatiilor utilizeaza:

D multimea de documente (1)V = {t1, t2, ..., t|V |} colectia de termeni (2)

unde:

ti termen inclus n cel putin un document din multime|V | cardinalul multimii de termeni (sau de chei de cautare)

Pentru fiecare termen ti se asociaza o pondere wij 0 n cadruldocumentului dj D.Documentele sunt reprezentate sub forma vectoriala:

dj = (w1j , w2j , ..., w|V |j) (3)



Modelul boolean

Modelul boolean

Caracteristici

Reprezentarea documentului vector de ponderi (conform ecuatiei 3) pentrucare ponderea wij este definita conform ecuatiei de mai jos:

wij =

{1 daca ti dj0 altfel

(4)

Reprezentarea interogarii termenii interogarii (sau cheile de cautare suntcombinate logic utilizand operatorii booleeni AND, OR si/sauNOT.

Regasirea documentului se bazeaza pe criteriul deciziei binare si pearitmetica multimilor.



Modelul boolean

Modelul boolean (2)

Avantaje

Este un model de cautare simplu, cu un formalism bine pus la punct,neambiguu.

Poate fi implementat usor si poate raspunde rapid pentru interogarile uzualeale utilizatorilor.

Dezavantaje

Datorita simplitatii, este un model foarte rigid.

Interogarile complexe nu pot fi realizate direct.

Nu poate fi controlata cu exactitate dimensiunea exacta a raspunsului.

Nu ofera un mecanism direct de feedback din partea utilizatorilor.



Modelul bazat pe reprezentare vectoriala


Caracteristici

Reprezentarea documentului vector de ponderi (conform ecuatiei 3) pentrucare ponderea wij poate fi definita astfel ncat sa modeleze diferitescenarii

Reprezentarea interogarii vector de ponderi (conform ecuatiei 3) pentru careponderile termenilor sunt definite conform pasului anterior.

Regasirea documentului se bazeaza pe distanta dintre doua documentecalculata ca fiind unghiul dintre 2 vectori n-dimensionali.




Modelul bazat pe reprezentare vectoriala (2)

Model algoritmic [3]

Algoritm 1 cautareVectoriala(D, q)

1: (optional) transforma fiecare document dj D in dj = {key : tf (key , d) idf (key)}2: transforma interogarea q = {key : tf (key , d) idf (key)}3: for all

dj D do

4: calculeaza sj = similaritateCosinus(dj ,q )

5: end for6: sorteaza documentele descrescator din punct de vedere al scorului anterior sj7: return setul relevant de documente




Modelul bazat pe reprezentare vectoriala (3)

Avantaje [3]

Formalism relativ simplu, bazat pe un model matematic clar.

Furnizeaza si rezultate partiale (n sensul de potrivire partiala).

Dezavantaje

Nu nglobeaza informatiile legate de semantica si de structura sintactica.

Se presupune ca termenii sunt independenti.

Avand n vedere ca se furnizeaza si rezultate partiale, nu exista un controldirect al interogarii.



Discutii

1 Ce implica o implementare eficiena a algoritmului 1?

ce ar trebui sa reprezinte D? poate fi restrans domeniul de cautare?ce nseamna un calcul eficient al scorului sj al unui document?



Bibliografie

1 M. Craus et al., Regasirea Informatiilor pe WEB, Editura POLITEHNIUM,Iasi 2005, capitolul 4

2 Christopher D. Manning, Prabhakar Raghavan and Hinrich Schutze,Introduction to Information Retrieval, Cambridge University Press. 2008

3 Raymond J. Mooney Information Retrieval and Web Search (note de curs)

4 Wikipedia Index (search engine)

5 Ioan Agavriloaei, Modele si algoritmi de Web Mining, Teza de doctorat, UTI,2012


Modele de cautareNotiuni introductiveModelul booleanModelul bazat pe reprezentare vectoriala

Discutii

Curs nr. 05 - Cautare.pdf

Documents

Transcript of Curs nr. 05 - Cautare.pdf