ˇ ´ vysoke ´ uc ˇen´ı technicke ´ v Praze Cesk e ˇn´ıch technologi´ı Fakulta informac ´ho inˇ ´ rstv´ı Katedra softwarove zeny
Reranking zaloˇzen´y na metadatech MI-VMW Projekt IV - 1
Pavel Homolka Ladislav Kubeˇs 6. 12. 2011
1
1
Popis projektu
C´ılem projektu je vytvoˇren´ı aplikace umoˇzn ˇuj´ıc´ı vylepˇsen´e vyhled´av´an´ı ve fotografi´ıch uloˇzen´ ych na serveru Flickr. Flickr poskytuje aplikaˇcn´ı rozhran´ı umoˇzn ˇuj´ıc´ı z´ıskat prakticky libovoln´a data o fotografi´ıch, kter´a jsou pˇr´ıstupn´a i z ofici´aln´ıho webov´eho rozhran´ı. C´ılem projektu je tedy aplikace, kter´a umoˇzn´ı vyhled´av´an´ı na flickru zaloˇzen´e na kl´ıˇcov´ ych slovech, stejnˇe jako je tomu na Flickru nyn´ı, ale nav´ıc bude moˇzn´e zadat sekund´arn´ı vyhled´av´an´ı na libovoln´a metadata.
1.1
Vstupy
Vstupn´ı data se zad´avaj´ı ve dvou f´az´ıch. V prvn´ı f´azi si aplikace vyˇza´d´a kl´ıˇcov´e slovo a poˇcet v´ ysledk˚ u jako povinn´e parametry a GPS souˇradnice jako nepovinn´ y parametr. V druh´e f´azi je pak moˇzn´e zad´avat metadata pro reranking. Aplikace implementuje reranking pro autora, n´azev, tag, GPS souˇradnice, datum uloˇzen´ı na Flickr a datum poˇr´ızen´ı fotografie.
1.2
V´ ystupy
Po prvn´ı f´azi jsou zobrazeny nesetˇr´ıdˇen´e fotky tak, jak je vr´atil Flickr. Uˇzivatel zad´a metadata pro reranking a aplikace fotografie setˇr´ıd´ı.
2
Zp˚ usob ˇ reˇ sen´ı
Pro implementaci rerankingu byly vyuˇzity r˚ uzn´e typy vzd´alenost´ı. Pro porovn´an´ı podobnosti dvou ˇretˇezc˚ u je vyuˇzita editaˇcn´ı vzd´alenost (Levenshteinova vzd´alenost). Pro vzd´alenosti dvou bod˚ u na zemˇekouli je vyuˇzita ortodroma (great circle distance). Pro porovn´an´ı dvou dat je vyuˇzit algoritmus vyuˇz´ıvaj´ıc´ı Unixov´e ˇcasov´e raz´ıtko.
2.1
Editaˇ cn´ı vzd´ alenost
Levenshteinova vzd´alenost (Levenshtein distance, editaˇcn´ı vzd´alenost) je vzd´alenost dvou ˇretˇezc˚ u definovan´a jako minim´aln´ı poˇcet operac´ı vkl´ad´an´ı, maz´an´ı a substituce takov´ ych, aby po jejich proveden´ı byly zadan´e ˇretˇezce totoˇzn´e. Levenshteinovu vzd´alenost zavedl v roce 1965 Vladimir Levenshtein.
2.2
Ortodroma
2.3
Algoritmus vyuˇ z´ıvaj´ıc´ı Unixov´ eˇ casov´ e raz´ıtko
Porovn´avan´a data jsou pˇrevedena na Unix time stamp. Vzd´alenost je vypoˇctena podle n´asleduj´ıc´ıho vzorce. distance = |
date 1 − date 2 | 86400 2
(1)
3
Implementace
Aplikace je implementov´ana v PHP 5.3. Je postavena na n´avrhov´em vzoru MVP (model, view, presenter) a vyuˇz´ıv´a framework Nette. Komunikace s API Flickrem je ˇreˇsena za pomoci vol´an´ı REST zdroj˚ u.
3.1
Model aplikace
Model aplikace se skl´ad´a ze tˇr´ı ˇca´st´ı. Jak si mezi sebou tyto ˇca´sti vymˇenuj´ı data, bude pops´ano v ˇca´sti aplikaˇcn´ı logika. 3.1.1
Komunikace s API Flickru
Komunikaci s API zajiˇst’uje tˇr´ıda Flickr, kter´a obsahuje jednu veˇrejnou metodu search a dvˇe konstanty - API KEY slouˇz´ıc´ı k autorizaci na Flickru a FORMAT urˇcuj´ıc´ı form´at n´avratov´ ych dat. Tˇr´ıda Flickr nen´ı v aplikaci vol´ana pˇr´ımo, ale prostˇrednictv´ım syst´emov´eho kontejneru. 3.1.2
Session
Komunikace s Flickrem je ˇcasovˇe n´aroˇcn´a, proto nen´ı vhodn´e pˇri kaˇzd´em tˇr´ıdˇen´ı fotografi´ı tuto komunikaci opakovat. Protoˇze HTTP komunikace je bezestavov´a, aplikace si nen´ı schopna pamatovat sv´e pˇredchoz´ı stavy. Proto aplikace vyuˇz´ıv´a session, kterou reprezentuje tˇr´ıda PhotosSession. 3.1.3
Reranking
O samotn´ y reranking se star´a tˇr´ıda Reranking obsahuj´ıc´ı tˇri veˇrejn´e metody: levenshteinDistance - pro tˇr´ıdˇen´ı ˇretˇezc˚ u, greatCircleDistance - pro tˇr´ıdˇen´ı podle GPS souˇradnic a dateDistance pro tˇr´ıdˇen´ı pomoc´ı dat. Ke sv´e pr´aci potˇrebuje tˇr´ıdu PhotosSession a o to, ˇze ji bude m´ıt k dispozici, se star´a syst´emov´ y kontejner. Tˇrida nen´ı v aplikaci vol´ana pˇr´ımo, ale opˇet pˇres syst´emov´ y kontejner.
3.2
Aplikaˇ cn´ı logika
Cel´a aplikaˇcn´ı logika je zaloˇzena na MVP. Pˇri pˇr´ıchodu na web aplikace zavol´a Nette framework SearchPresenter. Ten zajist´ı rendrov´an´ı formul´aˇre pro zad´an´ı prvn´ı f´aze vstupn´ıch metadat od uˇzivatele, viz kapitola 1.1. Vstupy. Pot´e co uˇzivatel zad´a vstupn´ı data, poˇz´ad´a SearchPresenter pˇres syst´emov´ y kontejner tˇr´ıdu Flickr, aby odeslala REST poˇzadavek na server Flickru. Flickr vr´at´ı mnoˇzinu fotografi´ı odpov´ıdaj´ıc´ı zadan´ ym metadat˚ um. Tato mnoˇzina je uloˇzena do session prostˇrednictv´ım tˇr´ıdy PhotosSession. N´aslednˇe SearchPresenter pˇresmˇeruje uˇzivatele na RerankingPresenter. Ten se v prvn´ı ˇradˇe postar´a o zobrazen´ı mnoˇziny fotografi´ı uloˇzen´ ych v session. D´ale rendruje formul´aˇr pro zad´an´ı druh´e f´aze metadat a ˇcasu komunikace s Flickrem. Nyn´ı m˚ uˇze uˇzivatel zad´avat metadata pro reranking. Kaˇzd´a fotografie v session se m˚ uˇze nach´azet v nˇekolika stavech. Algoritmus v´ ybˇeru ukazuje obr´azek 1. Ve chv´ıli, kdy nedoˇslo jeˇstˇe k ˇza´dn´emu tˇr´ıdˇen´ı, nen´ı ˇza´dn´ y stav definov´an. 3
Po odesl´an´ı poˇzadavku na reranking zavol´a RerankingPresenter opˇet pˇres syst´emov´ y kontejner pˇr´ısluˇsnou metodu tˇr´ıdy Reranking. Napˇr. pro ˇretˇezce je to levenshteinDistance, kter´a projde celou mnoˇzinu fotografi´ı a podle stavu, ve kter´em se fotografie nach´az´ı, vypoˇc´ıt´a vzd´alenost a aktualizuje stav. Tento proces popisuje obr´azek 1. Pokud fotografie nem´a jeˇstˇe ˇz´adn´ y stav definovan´ y nebo m´a stav true, je spoˇctena vzd´alenost od ˇretˇezce zadan´eho uˇzivatelem. Tato vzd´alenost je porovn´ana s r´adiem. Pokud je zadan´ y r´adius menˇs´ı neˇz vypoˇcten´a vzd´alenost fotografie, je nastaven stav false. V opaˇcn´em pˇr´ıpadˇe je nastaven stav true. Stav false znamen´a, ˇze fotografie nesplˇ nuje zad´an´ı a v dalˇs´ım porovn´av´an´ı s n´ı jiˇz nen´ı poˇc´ıt´ano. Ve v´ ysledn´em zobrazen´ı skonˇc´ı na posledn´ıch m´ıstech. Stav true znamen´a, ˇze fotografie vyhovuje vstupn´ım parametr˚ um.
Obr´azek 1: V´ ybˇer stavu fotografie. Pot´e co t´ımto procesem projdou vˇsechny fotografie mnoˇziny, jsou fotografie se stavem true seˇrazeny podle jejich vzd´alenosti od nejmenˇs´ı po nejvˇetˇs´ı. Takto setˇr´ıdˇen´ y seznam je uloˇzen do session. D´ale RerankingPresenter naˇcte seznam ze session a pˇred´a ho view, kter´ y vytvoˇr´ı HTML k´od, kter´ y je odesl´an na klienta. Cel´ y tento proces jiˇz prob´ıh´a bez komunikace se serverem Flickru. Pokud uˇzivatel zad´a v´ıce metadat pro tˇr´ıdˇen´ı, je mnoˇzina tˇr´ıdˇena v nˇekolika f´az´ıch. F´aze jsou vykon´avan´e v poˇrad´ı Autor → N´azev → Tag → GPS → Datum. Do dalˇs´ı f´aze vstupuj´ı jen fotografie se stavem true. Uˇzivatel m´a moˇznost kdykoliv se vr´atit k zad´an´ı prvn´ı f´aze vstupn´ıch metadat t´ım, ˇze vypln´ı formul´aˇr Nov´ y dotaz. V tom pˇr´ıpadˇe je v mnoˇzina v session smaz´ana a nahrazena novou.
4
4
Pˇ r´ıklad v´ ystupu
Jako pˇr´ıklad v´ ystupu bude uveden obdobn´ y pˇr´ıpad jako v zad´an´ı. Dejme tomu, ˇze chceme vyhledat auta podl´ıˇz prvn´ıho n´advoˇr´ı Praˇzsk´eho hradu.
Obr´azek 2: Prvn´ı f´aze zad´an´ı metadat. Obr´azek 2 ukazeje vyplnˇen´ı formul´aˇr pro zad´an´ı prvn´ı f´aze dat. Chceme vyhledat kl´ıˇcov´e slovo car, poˇcet v´ ysledk˚ u maxim´alnˇe 100 a pro upˇresnˇen´ı zad´ame GPS souˇradnici prvn´ıho n´advoˇr´ı Praˇzsk´eho hradu s radiusem 5km. Kdybychom tuto posledn´ı informaci nezadali prvdˇepodobnˇe by mezi v´ ysledky nebylo ˇzadn´e auto v Praze.
Obr´azek 3: V´ ysledn´a mnoˇzina vr´acen´a Flickrem. Obr´azek 3 ukazuje statistika v´ ysledku - dotaz vr´atil 100 fotografi´ı, ˇcas komunikace 3,01 s a prvn´ı fotografii. Je vidˇet ˇze jeˇstˇe nem´a definovan´ y stav.
5
Obr´azek 4: V´ ysledek rerankingu pro GPS. Reranking podle GPS a pˇresnost´ı na 0,5 km ukazuje obr´azek 4, jde o prvn´ı fotografii. Od poˇzadovan´ ych souˇradnic je vzd´alen´a 44,5 m. Stav fotografie je true.
Obr´azek 5: V´ ysledek rerankingu pro autora. Pokud nin´ı zad´ame tˇr´ıdit podle autora Monika & Marek a s pˇresnost´ı 0 tj. ber v u ´vahu 6
pouze shodn´e ˇretˇezce. Dostaneme v´ ysledek podle obr´azku 5. Zde vid´ıme ˇze forografie z obr´azku 4 pˇreˇsla do stavu false a na prvn´ı m´ısto se dostala fotografie atora Monika& Marek(forografie v levo).
5
Experiment´ aln´ı sekce
6
Diskuze
Reference [1] Havlena, V. (1999). Modern´ı teorie ˇr´ızen´ı – Doplˇ nkov´e skriptum. Vydavatelstv´ı ˇ CVUT, Praha. ˇ, J. Modern´ı teorie ˇr´ızen´ı [online]. Posledn´ı revize 2003-07-01 [2] Roubal, J.; Pekar [cit. 2003-07-01], hhttp://dce.felk.cvut.cz/mtr/i.
7
