Pretraživanje informacija

Из Википедије, слободне енциклопедије

Pretraživanje informacija (PI) je nauka o potrazi za informacijama u dokumentima, koja pretražuje same dokumente, tražeći metapodatke (metadata) koji opisuju te dokumente ili koja pretražuje unutar baza podataka, bilo relacionih samostalnih baza podataka (relational stand-alone databases) ili hipertekstualnih baza podataka sa mreže (hypertextually-networked databases) kao što je globalna računarska mreža (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, 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 (object) i upit (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 (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.

1992. godine ministarstvo odbrane Sjedinjenih Američkih Država, zajedno sa nacionalnim institutom za standarde i tehnologiju (National Institute of Standards and Technology) je kofinansiralo konferenciju o pretraživanju informacija (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živaci mreže poput google-a, live.com-a, ili yahoo-a 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 (precision at n). Obratite 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 sto 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 LAZNO 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

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

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

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

Opsta formula za ne-negativnu 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
  1. Standardni Bulov (Boolean) model
  2. Prosiren Bulov model
  3. 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:
  1. Vektorsko-prostorni model
  2. Univerzalni vektorsko-prostorni model
  3. Tematski vektorsko-prostorni model
  4. Prošireni Bulov model
  5. Poboljšan tematski vektorsko-prostorni model
  6. 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.

  1. Binarno nezavisno pretraživanje
  2. Probabilistički model relevantnosti (BM25)
  3. Sporna interferencija
  4. Jezički modeli
  5. 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 se preselio u Kornel (Cornell)

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. Mekgil (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