Teema 6 - Information Retrieval

1. Ülesandepüstitus ja sissejuhatus
2. Dokumentide rankimine
3. Veebi otsimootorid
4. Tekstide kaevandamine
5. ...

Kirjandust

• Ian H. Witten, Alistair Moffat, and Timothy C. Bell:
  Managing Gigabytes. Compressing and Indexing Documents and Images
  Second Edition, 1999 Morgan Kaufmann Publishing, San Francisco, ISBN 1-55860-570-3.
  web site.

• C. J. van RIJSBERGEN B.Sc., Dip. NAAC, Ph.D., M.B.C.S., F.I.E.E., C.Eng., F.R.S.E. INFORMATION RETRIEVAL (2nd ed. London: Butterworths, 1979) (kohalik)
• Generic Information Retrieval System (TREP/Tipster) (kohalik)
  Seal on ka muid dokuemente teema kohta...
• Text REtrieval Conference (TREC)
• Google - webi otsimine

Ülesandepüstitus

• Vajadused

• Dokumentide andmebaasid

  • Sõnastikud

  • Teaduslikud artiklid

  • Seaduste baasid

• Kogu WWW-d hõlmavad otsimootorid

• Teadmusbaasid

• Probleem

• Olgu antud dokumentide kogum

• Eesmärk on leida teatud teemat puudutavad dokumendid

• Kasutaja formuleerib päringu

• Päringule vastavad dokumendid tagastatakse

• Küsimusi

  • Kas saadud dokumendid on relevantsed teema suhtes?

  • Kui vaadata esimest ütleme sadat vastust, siis kui palju nendest on relevantsed teema suhtes ja kui suur osa relevantseid artikleid mahub 100 hulka?

  • Kui üks dokument on oluline/huvitav, siis kuidas leida teised sarnased dokumendid?

  • Millised dokumentide/teemade grupid on esindatud kogu andmebaasis ja millised võtmesõnad iseloomustavad iga sellist gruppi?

  • Kuidas esitada kogu andmebaas visuaalselt kasutajale?
    • Teemade hierarhiad
    • Iseorganiseeruv kaart (näiteks WebSom)
    • Teemade hierarhiad

Rankimine

• Olgu antud dokumentide kogu D mis koosneb |D| dokumendist

• Vaatame päringut: Otsi kõik dokumendid d ∈ D mis sisaldavad sõna A

• A AND B; A OR B; A AND NOT B

• Saab täpselt öelda mitu dokumenti vastab antud kriteeriumile.

• Kuid kas saab öelda, mitu dokumenti vastab tegelikult sellele soovile mille pärast päring esitati?

• Kuidas me teame millised dokumendid vastavad meie ootustele kõige "paremini"

• Tuleb sorteerida vastused relevantsuse järjekorda

• Kuidas hinnata relevantsust matemaatiliselt, et saaks sorteerida?

• Esita dokumendid bitivektoritena üle kõikide sõnade.

• 1 - järelikult sõna esineb dokumendis, 0 - ei esine

• Päring Q võib vaadelda kui dokumenti (kus on näiteks üks sõna)

• Ristkorrutis: hinda arvuliselt kui palju sõnu päringust langeb kokku päringuga

• Päringu ja dokumendi sarnasus M(Q, D_i) = Q · D_i

• X · Y = ∑_i x_iy_i

  ---

• Sõnade sagedus - rohkem korratud sama sõna, siis tuleks anda lisaväärtust

• Bitivektori asemel hoiame vektoreid sõnade sagedustega igas dokumendis

• M(X , Y ) = ∑_i w_q,i w_d,i

• w on iga sõna jaoks igas dokumendis erinev

• Lisaks saab hinnata rohkem neid sõnade esinemisi mis sisalduvad olulistes kohtades

  ---

• Väga pikk dokument kus palju sõnu oleks relevantne alati - tuleb kompenseerida dokumendi pikkuse järgi.

• Kui mõni sõna otsitutest on harvaesinev siis tuleks selle esinemist "premeerida"

• St, anda rohkem kaalu keskmiselt vähestes dokumentides esinevatele sõnadele

• Sõnadele rankimise järjekorras alanev kaal.

  ---

• Korrelatsioon/koosinus

• X · Y = |X| |Y| cos Θ

• |X| = sqrt( ∑_i x_i² )

• cos Θ = ( X · Y ) / |X| |Y|

• Kui ortogonaalsed, siis cos on 0, kui sama vektor, cos=1.

• Mida suurem cos, seda sarnasemad

Täpsus ja täielikkus

• Kõige sagedamini kasutatavd päringu kvaliteedi mõõdud on täpsus (precision) ja täielikkus (recall)

• Me suudame läbi vaadata vaid mingi maksimum r dokumenti.

• Seega peaks r esimest dokumenti rankimise järjekorras sisaldama enamvähem kõiki relevantseid dokumente.

• Täpsus (precision) mõõdab, kui mitu esimesest r dokumendist vastab tegelikult meie soovile.

• 
         relevantsete dokumentide arv esimeses r vastuses 
  Pr = --------------------------------------------------
    		        r
  
  

• Täielikkus (recall) mõõdab kui suure osa kõikidest relevantsetest oleme kätte saanud

• 
  	 relevantsete dokumentide arv esimeses r vastuses 
  Rr = --------------------------------------------------
  	    kõikide relevantsete dokumentide arv
  
  

• Mida suurem on r seda parem on R

• Väikese r puhul võib olla väga hea P

• Võib joonistada graafiku kuidas muutuvad P ja R sõltuvalt r-ist

Google ja veebi otsimootorid

• Webis semantika kirjeldamine märksõnade abil (meta tag)

• Dublin core jt.; Semantic Web jne.

• Google - kõik tahavad eesotsas olla. Kuidas vältida pürgureid/võltsijaid?

• Dokumendi rank ei sõltu mitte enam ainult sellest mis dokumendis kirjas...

• Usaldusväärsel materjalil on tõenäoliselt palju ja usaldusväärsed viitajad

• Rankimine arvestab seda kui palju ja mis kontekstis sulle viidatakse

• Veebis linkide jaotumise statistika - "power law" - kohtab ka väga paljudes teistes "loomulikes" võrkudes/graafides.

Tekstide kaevandamine

• Dokumentide klasterdamine

• Sarnaste dokumentide otsimine

• Kõikide dokumentides esinevate seoste otsimine

• Näiteks kõikide potentsiaalselt seotud geenide paaride (ja võrkude) otsimine

• Teatud haigusi kirjeldavate artiklite sees mainitud geenide ja nende geenidega seonduvate geenide otsimine...

• Lingvistiline analüüs ja täpsete suhete tuvastamine...