Pretraživanje informacija

Pretraživanje informacija (skraćeno PI; eng. information retrieval — IR) nauka je o potrazi za informacijama u dokumentima, koja pretražuje same dokumente, tražeći metapodatke (eng. metadata) koji opisuju te dokumente ili koja pretražuje unutar baza podataka, bilo relacionih samostalnih baza podataka (eng. relational stand-alone databases) ili hipertekstualnih baza podataka sa mreže (eng. hypertextually-networked databases) kao što je globalna računarska mreža (eng. world wide web).

Međutim, postoji opšta zabuna u vezi sa pretraživanjem podataka, pretraživanjem dokumenata, pretraživanjem informacija i pretraživanjem teksta, jer svako od ovih pretraživanja ima svoju zasebnu literaturu, teoriju, praksu i tehnologije. Pretraživanje informacija je interdisciplinarna oblast, poput većine oblasti koje su u razvoju, zasnovana na računarskoj nauci, matematici, bibliotekarstvu i nauci o informacijama, kognitivnoj psihologiji, lingvistici, statistici i fizici.

Automatizovani sistemi za pretraživanje informacija se koriste da bi se smanjila preopterećenost informacijama. Mnogi univerziteti i javne biblioteke koriste sisteme za pretraživanje informacija da bi obezbedile pristup knjigama, časopisima i drugim dokumentima. Sistemi za pretraživanje informacija se često odnose na objekat (eng. object) i upit (eng. query). Upiti su formalni zahtevi za potrebnim informacijama koje korisnik ubacuje u sistem za pretraživanje informacija. Objekat je entitet koji čuva ili skladišti informacije u bazi podataka. Upiti korisnika se uparuju sa objektima uskladištenim u bazi podataka. Dokument je, stoga, objektni podatak (eng. object data). Često se sami dokumenti ne čuvaju ili skladište direktno u sistemu pretraživanja informacija, već su, umesto toga, predstavljeni u tom sistemu njihovim surogatima.

Godine 1992, Ministarstvo odbrane Sjedinjenih Američkih Država, zajedno sa nacionalnim institutom za standarde i tehnologiju (eng. National Institute of Standards and Technology) kofinansiralo je konferenciju o pretraživanju informacija (eng. TREC-Text Retrieval Conference) kao deo tekstualnog programa TIPSTER. Cilj ovoga bio je da se zađe u grupu za pretraživanje informacija tako što bi se obezbedila infrastruktura koja je potrebna za tako široku procenu metodologija pretraživanja informacija. Pretraživači mreže, poput Gugla, live.com-a ili Jahua, predstavljaju najočiglednije aplikacije za pretragu informacija.

Mere rada уреди

Postoji nekoliko mera za rad sistema za pretraživanje informacija. Mere se zasnivaju na zbirci dokumenata i upitima kojima je poznata relevantnost datih dokumenata. Sve uobičajene mere koje su opisane ovde pretpostavljaju binarnu relevantnost: dokument je ili relevantan ili irelevantan. U praksi, upiti mogu biti loše postavljeni i mogu da postoje različite nijanse relevantnosti. Formule za preciznost, opoziv i ispad su prevedene iz članka nemačke vikipedije ‘recall und precision’. Obratite pažnju i na ovaj lep intuitivan grafički opis.

Preciznost уреди

Proporcija pretraženih i relevantnih dokumenata u odnosu na sva dokumenta u pretraživanju.

                             {RELEVANTNA  DOKUMENTA} ∩ {PRETRAŽENA DOKUMENTA}

Preciznost=

                                      {SVA DOKUMENTA U PRETRAZI}

U binarnoj klasifikaciji, preciznost je analogna pozitivnoj proceni verovatnoće. Preciznost uzima u obzir sva dokumenta u pretrazi. Takođe se može vršiti procena na osnovu datog zasebnog ranga, uzimajući u obzir samo prve rezultate koje je dao sistem. Ova mera se naziva preciznost na n ili P@n (eng. precision at n).

Treba obratiti pažnju da se značenje i upotreba reči preciznost u oblasti pretraživanja informacija razlikuje od definicije tačnosti i određenosti u okviru drugih grana nauke i tehnologije.

Primer pozitivne procene verovatnoće kod testova za otkrivanje bolesti — tu treba razlikovati one koji imaju dotičnu bolest i koji su pozitivni na testu (stvarno pozitivni). Zatim, one koji su zdravi, ali su pozitivni na testu (lažno pozitivni). Oni koji su zdravi, ali negativni na testu (stvarno negativni) i oni koji su bolesni, a negativni na testu (lažno negativni), pa stoga formula izgleda:

                                       BROJ PRAVO POZITIVNIH

PPV=

        BROJ STVARNO POZITIVNIH + BROJ LAŽNO POZITIVNIH

Opoziv уреди

Proporcija relevantnih dokumenata koja su pretražena u odnosu na sva relevantna dokumenta koja su na raspolaganju.

                            {RELEVANTNA DOKUMENTA} ∩ {PRETRAŽENA DOKUMENTA}

Opoziv=

                        {SVA RELEVANTNA DOKUMENTA KOJA SU NA RASPOLAGANJU}

U binarnoj klasifikaciji, opoziv se naziva senzitivnost.

Trivijalno je postići stopostotni opoziv tako što se daju sva dokumenta kao odgovor na bilo koji upit, stoga sam opoziv nije dovoljan već mora da se izmeri i broj irelevantnih dokumenata, na primer izračunavajući preciznost.

                                     BROJ STVARNO POZITIVNIH

Senzitivnost=

                               BROJ STVARNO POZITIVNIH + BROJ LAŽNO NEGATIVNIH

Ispad уреди

Proporcija irelevantnih dokumenata koji su pretraženi u odnosu na sva irelevantna dokumenta koja su na raspolaganju:

                        {IRELEVANTNA DOKUMENTA} ∩ {PRETRAŽENA DOKUMENTA}

Ispad=

                            {SVA IRELEVANTNA DOKUMENTA NA RASPOLAGANJU}

F-mera, ili usklađen F-rezultat, je ponderisana, harmonijska sredina preciznosti i opoziva i glasi:

 F = 2x(PRECIZNOST x OPOZIV)/(PRECIZNOST + OPOZIV)

Još se naziva i F1-mera, jer se preciznost i opoziv jednako vrednuju.

Opšta formula, za nenegativnu stvarnu α, je:

Fα = (1 + α ) x (PRECIZNOST x OPOZIV ) / (α x PRECIZNOST + OPOZIV )

Druge dve obično korišćene F-mere su: F2-mera, koja vrednuje opoziv dvostruko u odnosu na preciznost, i F0,5-mera koja vrednuje preciznost dvostruko u odnosu na opoziv.

Prosečna preciznost уреди

Preciznost i opoziv se zasnivaju na celokupnoj listi dokumenata koje sistem daje kao odgovor. Prosečna preciznost pridaje značaj prvenstveno davanju relevantnijih dokumenata kao odgovor. To je prosek preciznosti izračunatih posle skraćivanja liste koja se vrši posle svakog od relevantnih dokumenata naizmenično:

             ∑N (P(r ) x rel (r ))

Prop = r=1

            BROJ RELEVANTNIH DOKUMENATA

Gde je r - rang, N - broj pretraženih dokuimenata, rel (r ) - binarna funkcija relevantnosti datog ranga, a P (r ) – preciznost datog zasebnog ranga.

Ako postoji nekoliko upita sa poznatim relevantnostima na raspolaganju, srednja vrednost prosečne preciznosti je sredina prosečnih preciznosti izračunatih za svaki upit posebno.

Tipovi modela уреди

Kategorizacija modela za pretraživanje informacija

Osobine modela

Matematička osnova bez međuzavisnosti termina sa međuzavisnostima termina Imanentne međuzavisnosti termina transcedentne međuzavisnosti termina Skup-teoretski Modeli Algebarski modeli Probabilistički modeli

Za uspešno pretraživanje informacija neophodno je da se dokumenti predstave na neki način. Postoji više modela koji se koriste u ovu svrhu. Oni se mogu kategorizovati na osnovu dve dimenzije kao što je prikazano u tabeli: na osnovu matematičke osnove i na osnovu osobina modela.

PRVA DIMENZIJA:MATEMATIČKA OSNOVA уреди

Set-teoretski modeli predstavljaju dokumente u skupovima. Sličnosti se obično izvode iz set-teoretskih operacija na tim skupovima. Uobičajeni modeli su

Standardni Bulov (Boolean) model
Prosiren Bulov model
Nejasno pretraživanje

Algebarski modeli obično predstavljaju dokumenta i upite kao vektore, matrice ili zapise. Ti vektori, matrice ili zapisi se pretvaraju pomoću konačnog broja algebarskih operacija u jednodimenzionalnu meru sličnosti. To su:

Vektorsko-prostorni model
Univerzalni vektorsko-prostorni model
Tematski vektorsko-prostorni model
Prošireni Bulov model
Poboljšan tematski vektorsko-prostorni model
Latentno semantičko indeksiranje takođe poznato kao latentna semantička analiza

Probabilistički modeli tretiraju proces pretraživanja dokumenta kao nasumični eksperiment u više etapa. Sličnosti su prema tome predstavljene kao mogućnosti. Probabilističke teoreme poput Bajesove (Bayes) se često koriste u ovim modelima.

Binarno nezavisno pretraživanje
Probabilistički model relevantnosti (BM25)
Sporna interferencija
Jezički modeli
Modeli odstupanja od nasumičnosti

Druga dimenzija: osobine modela

Modeli bez međuzavisnosti termina tretiraju različite termine/reči kao da nisu međuzavisni. Ova činjenica je obično predstavljena u vektorsko-prostornim modelima pretpostavkom ortogonalnosti terminskih vektora ili u probabilističkim modelima pretpostavkom nezavisnosti terminskih varijabli.
Modeli sa imanentnim međuzavisnostima termina dozvoljavaju prikazivanje međuzavisnosti između termina. Međutim, stepen međuzavisnosti između dva termina je definisan samim modelom. Obično je direktno ili indirektno izveden iz učestalosti pojavljivanja tih termina jedan uz drugi u čitavom skupu dokumenata (npr. uz pomoć dimenzionalne redukcije).
Modeli sa transcedentnim međuzavisnostima termina dozvoljavaju prikazivanje međuzavisnosti između termina, ali ne iskazuju kako je ta međuzavisnost između 2 termina definisana. Oni zamenjuju otvoreni izvor sa stepenom međuzavisnosti između 2 termina (npr. ljudski ili sofisticirani algoritmi).

GLAVNI DOGAĐAJI U ISTORIJI PRETRAŽIVANJA INFORMACIJA U SAD-U уреди

1890.-Holeritove (Herman Hollerith) tabelarne mašine su se koristile za analizu cenzusa SAD-a

1945.- “ Kao što mislimo” Venevara Buša (Vannevar Bush) se pojavio u Atlantik mesečniku

Kasne 40-te.- Vojska SAD-a se susrela sa problemima indeksiranja i pretraživanja dokumenata ratnih naučnih istraživanja koja su zaplenili od Nemaca.

1947.- Hans Peter Lan (Hans Peter Luhn) (inženjer istražitelj u IBM-u od 1941.) je započeo rad na mehanizovanom sistemu za traženje hemijskog sastava zasnovanog na bušenim karticama.

1950.- Pretpostavlja se da je Kalvin Muers (Calvin Mooers) skovao termin „ pretraživanje informacija “.

1950-te- Rastuća briga u SAD-u zbog „naučnog jaza“ zajedno sa motivisućim, podsticajnim finansiranjem od strane Sovjeta, činilo je tle na kome su se razvili mehanizovani sistemi za traženje literature Alena Kenta (Allen Kent) i pronalazak indeksiranja službenih pohvala Judžina Garfilda (Eugene Garfield)

1955.- Alen Kent se pridružio Univerzitetu “Case Western Reserve”, i konačno postaje direktor saradnik centra za istraživanje dokumentacije i komunikacije (Center for Documentation and Communication Research).

1958.- Međunarodna konferencija o naučnim informacijama (International Conference on Scientific Information ) u Vašingtonu obuhvatala je i uzimanje u obzir sistema za pretraživanje informacija kao rešenje za prepoznate probleme. Pogledati: Izveštaji sa međunarodne konferencije o naučnim informacijama, 1958. (Nacionalna Akademija Nauka,Vašington, 1959.)

1959.- Hans Peter Lan je objavio „ auto-kodiranje dokumenata za pretraživanje informacija “.

1960.- Melvin Erl (Bil) Maron (Melvin Earl (Bill) Maron) I J. L. Kan (J.L. Kuhn ) su objavili „ O relevanciji, probabilističkim modelima i pretraživanju informacija “ u časopisu ACM-a (Računarsko društvo) 7 (3):216-244

Rane 1960-te- Džerard Salton (Gerard Salton) je započeo rad na pretraživanju informacija na Harvardu, a kasnije je prešao na Kornel.

1962.- Siril V. Kleverdon (Cyril W. Cleverdon) je objavio rana otkrića Krenfildovih (Cranfield) istraživanja, razvijajući model za procenu sistema za pretraživanje informacija.

1962.- Kent je objavio Analizu i Pretraživanje informacija.

1963.- Vejnbergov izvestaj „ nauka, vlada i informacije“ dao je potpuno razjašnjenje ideje o „krizi naučnih informacija „. Izvestaj je dobio naziv po Dr. Alvinu Vejnbergu (Dr. Alvin Weinberg).

1963.- Džozef Beker (Joseph Becker) i Robert Hejz (Robert Hayes) su objavili tekst o pretraživanju informacija „ Čuvanje i pretraživanje informacija: sredstva, elementi, teorije „ Njujork, Vajli (1963)

1964.- Karen Spark Džouns (Karen Sparck Jones) je završila svoju tezu na Kembridžu, Sinonimija i Semantička Klasifikacija, i nastavila sa radom na primeni računarske lingvistike u pretraživanju informacija.

1964.- Nacionalni Biro standarda (National Bureau of Standards) je sponzorisao simpozijum pod nazivom „ Statističke zajedničke metode za mehanizovanje dokumentaciju „. Nekoliko izuzetno značajnih radova, uključujući i prvi objavljeni izvestaj o „ SMART “ sistemu G. Saltona.

Sredina 1960-ih- Nacionalna biblioteka medicine je razvila Sistem za analizu i pretraživanje medicinske literature „ MEDLARS “- Prvu značajnu bazu podataka koju čita mašina i sistem za pretraživanje serijski grupisanih dokumenata..

Sredina 1960-ih- Intrex projekat na Tehnološkom institutu u Masačusetsu

1965.- J.C.R. Liklider (J.C.R. Licklider) je objavio Biblioteke Budućnosti

1966.- Don Svonson (Don Swanson) je bio uključen u istraživanja o Tehničkim zahtevima za buduće kataloge na čikaškom univerzitetu.

1968.- Džerard Salton je objavio Automatsku organizaciju i pretraživanje informacija

1968.- „ RADC Tech “ izvestaj J. V. Samona (J.W. Sammon) „ Malo matematike čuvanja i pretraživanja informacija „ koji je dao nacrt vektorskog modela.

1969.- „ Nelinearna podela memorije po sadržaju za analizu strukture podataka „ Samona (IEEE (Institut elekričnih i elektronskih inzinjera) Transakcije na računarima ) je bio prvi predlog vizuelizacije interfejsa za sistem pretraživanja informacija.

Kasne 1960-te- F. V. Lankaster (F. W. Lancaster) je završio istraživanja procene sistema MEDLARS i objavio prvo izdanje svog teksta o pretraživanju informacija.

Rane 1970-te- Prvi on-line sistemi- NLM, AIM-TWX, MEDLINE; Lokhidov (Lockheed) Dijalog; SDC-ov ORBIT

Rane 1970-te - Teodor Nelson (Theodor Nelson) zastupajući koncept hiperteksta, objavljuje računarske Lib/Drim (Lib/Dream) mašine

1971.- N. Zardin (N. Jardin) I C.J. Van Ridzsbergen (C. J. Van Rijsbergen) su objavili „Upotrebu Hijerarhijskog Grupisanja u Pretraživanju Informacija”, koja je razjasnila hipotezu o grupama.

1975.- Tri veoma uticajne Saltonove publikacije su u potpunosti razjasnile sistem vektorskog postupka i modela diskriminacije tremina:

Teorija Indeksiranja (Društvo za idustrijsku i primenjenu matematiku)
Teorija o značaju termina u automatskoj analizi teksta (JASIS v.26)
Vektorsko-prostorni model za automatsko indeksiranje (CACM)

1978.- Prva ACM SIGIR konferencija

1979.- C.J. Van Rijsbergen je objavio Pretraživanje informacija (Baterworts). Veliki akcenat na probabilističkim modelima.

1980.- Prva međunarodna ACM SIGIR konferencija, zajedno sa grupom britanskog računarskog društva za pretraživanje informacija u Kembridžu.

1982- Belkin (Belkin), Odi (Oddy) i Bruks (Brooks) su predložili ASZ (Anomalno Stanje Znanja) gledište za pretraživanje informacija. Ovo je bio bitan koncept, mada se njihovo sredstvo za automatsku analizu pokazalo potpuno razočaravajućim.

1983.- Salton (I M. Makgil (M. McGill)) su objavili Uvod u savremeno pretraživanje informacija (Mekgro-Hil (McGraw-Hill)) sa velikim akcentom na vektorske modele.

Sredina 1980-ih- Pokušaji da se razvije verzija krajnjeg korisnika komercijalnog sistema za pretraživanje informacija.

1985—1993.- Ključni radovi i eksperimentalni sistemi za vizuelizaciju interfejsa. Radovi D. B. Krauca (D.B. Crouch), R.R. Korfedza (R.R. Korfhage), M. Calmersa (M. Chalmers), A. Sperija (A. Spoerri) i drugih.

1989.- Prvi predlozi Tima Bernersa-Lija (Tim Berners-Lee) za globalnu računarsku mrežu u evropskoj organizaciji za nuklearna istraživanja (CERN)

1992.- Prva TREC konferencija

1997.-Korfedzova publikacija Pretraživanje informacija sa akcentom na poenti vizuelizacije i postojanju više referenci u sistemima.

Kasne 1990-te- Primena pretraživaca mreže sa brojnim karakteristikama koje su se ranije mogle naći samo u eksperimetalnim sistemima za pretraživanje.

SISTEMI ZA PRETRAŽIVANJE OTVORENOG IZVORA INFORMACIJA уреди

„ Datapark search“, pretraživač pisan u C-u, GPL-u
Egothor, pretraživač teksta sa svim karakteristikama, visokih preformansi pisan potpuno u Javi
Glimpse i Webglimpse- napredni softver za pretraživanje sajtova
Smart, prvi pretraživač informacija sa Kornel Univerziteta