Analiza sistema za pretragu slika i teksta

UNIVERZITET SINGIDUNUM

DEPARTMAN ZA POSLEDIPLOMSKE STUDIJE

MASTER RAD

ANALIZA SISTEMA ZA PRETRAGU SLIKA I TEKSTA

Mentor:

Student:

Prof . dr Milan Milosavljević

Aleksandar Živković

Br. indeksa 410449/2014

Beograd,

2017

. godine

Sadržaj

Apstrakt ................................................................................................................. - 5 –

Uvod ........................................................................................................................ - 6 -

Pronalaženje informacija ............................................................................. - 10 –

Modeli sistema za pronalaženje informacija ............................................... - 10 -

2.1

Model vektorskog prostora .................................................................... - 11 –

2.2

Modeli verovatnoće ............................................................................... - 13 –

2.3

Model mreže zaključivanja .................................................................... - 15 –

Implementacija .............................................................................................. - 16 –

3.1

BM25 rankirajuća funkcija ..................................................................... - 17–

3.2

PageRank algoritam ............................................................................... - 18 –

3.3

HITS algoritam ...................................................................................... - 19 –

Ocenjivanje sistema ...................................................................................... - 20 –

Modifikacija upita .......................................................................................... - 21–

5.1

Upiti u obliku pitanja ............................................................................. - 22 –

Povratne informacije o relevantnosti ........................................................... - 37–

8.1

Metode razdaljine ................................................................................... - 38 –

8.1.1

Euklidova razdaljina .............................................................................. - 39 –

8.1.2

L1 ........................................................................................................... - 40 –

8.1.3

L∞ .......................................................................................................... - 40 –

8.1.4

Dzensen-Šanon ...................................................................................... - 41 –

8.1.5

Kulbak-Leibler ....................................................................................... - 41 –

8.1.6

Distorzija ................................................................................................ - 41 –

8.1.7

Razdaljina vizuelnih reči ........................................................................ - 42 –

8.2

Metode ocenjivanja ................................................................................ - 43 –

Zaključna razmatranja ................................................................................. - 46 -

Literatura ........................................................................................... - 47 -

Apstrakt

U današnjem svakodnevnom životu, važnost arhivisanja i pronalaženja informacija postaje sve

više bitnija. U ovom radu objasnićemo neke ključne metodologije i tehnike, kao i evoluciju oblasti
pretraživanja informacija. Zaključujemo da je istraživanje u ovoj oblasti od ključnog značaja za brzu i
efikasnu dostupnost informacijama što je značajno da skoro svaku ljudku delatnost u modernom svetu.

Ključne reči: veštačka inteligencija, sistem za pronalaženje informacija, pretraživač informacija,
pretraživač slika, upit

Čuvanje pisane informacije se može naći i 3000 godina pre Isusa Hrista, kada su Sumerci

odvajali specijalna mesta za čuvanje glinenih tabli sa zapisima na klinastom pismu. Čak i Sumerci su
shvatili da prava organizacija i pristup arhivama je kritična za efikasno korišćenje informacije. Pravili
su specijalne klasifikacije za indetifikaciju svake table i njene sadržine.

Potreba za skladištenje i pronalaženje informacija je postala sve važnija tokom vekova, naročito

sa izumima kao što su papir i presa za štampanje. Uskoro su i računari izumljeni i ljudi su shvatili da
mogu da se koriste za skladištenje i mehaničko pronalaženje velike količine informacija. 1965-te
godine Vannevar Bush je objavio revloucionarni članak “Kako možemo misliti” koji je rodio ideju
automatskog pristupa velikoj količini informacija.[2] 1950-ih godina ova ideja se materijalizovala u
konkretne opise kako bi arhive teksta mogle da se automatski pretražuju. Nekoliko radova iz sredine
1950-ih godina su razradili bazičnu ideju pretrage teksta pomoću računara.

Nekoliko glavnih razvitaka u oblasti su se desili 1960-ih godina. Najbitnije je bilo razviće

SMART sistema od Gerard Salton-a i njegovih studenta, prvo na Harvard Univerzitetu pa kasnije na
Cornell Univerzitetu,[3] i Cranfield procene rađene od Cyril Cleverdon-a i njegove grupe na Cranfield
Univerzitetu.[4] Cranfield testovi su razvili metodologiju ocenjivanja sistema za pronalaženje
informacija koja se koristi još danas. SMART sistem je dozvolio istraživačima da eksperimentišu sa
idejama da bi unapredili kvalitet pretrage. Sistem za eksperimentisanje zajedno da dobrom
metadologijom ocenjivanja je doprinelo brzom razvoju u oblasti i mnogim razvićima.

1970-tih i 1980-tih godina su se razvila mnoga unapređenja od ideja 1960-ih. Novi modeli i

tehnike su eksperimentalno dokazani da su efikasni na malim kolekcijama teksta (nekoliko hiljada
članaka) koji su bili dostupni istraživačima tada, ali pošto nisu imali pristup velikim kolekcijama
dokumenata nisu znali da li će biti isto toliko efikasne na većim kolekcijama dokumenata. Ovo se
promenilo 1992 godine sa kreiranjem konferencije za pretraživanje teksta (Text Retrieval Conference -
TREC).[5]

Sa velikim kolekcijama teksta dostupnim od TREC-a, dosta starih tehnika se modifikovalo i

dosta novih se razvilo za efektivnu pretragu velikih kolekcija. Algoritmi razvijeni u ovoj naučnoj
oblasti su se prvi koristili za pretragu World Wide Web-a od 1996 do 1998. Web pretraživači su se
kasnije razvili da koriste relacione veze dostupne na web-u.