Miroslav Fabián - Vyhľadávanie webových stránok s využitím analógie sociálneho správania sa včiel

    Miroslav Fabián - Vyhľadávanie webových stránok s využitím analógie sociálneho správania sa včiel

     

    Popis problému

     

                Cieľom môjho projektu je vytvoriť systém na on-line vyhľadávanie podobných stránok s použitím analógie správania sa včiel.

     

     

                Včely majú vyvinutý zaujímavý spôsob hľadania a zbierania potravy. Cieľom včiel je získať čo najväčšie množstvo nektáru. Zdroje nektáru sú kvety, ktoré sa nachádzajú v okolí hniezda. Tieto zdroje v prírode nie sú rozložené rovnomerne, ale ich štruktúra má skôr zhlukový charakter. Zdroje sa líšia svojou polohou a výdatnosťou, časom sa menia, menia svoju výdatnosť a objavujú sa nové zdroje. Kolónia včiel sa musí priebežne prispôsobovať týmto zmenám ak chce maximalizovať svoj zisk nektáru. Najdôležitejšia úloha, ktorú musia včely v tejto súvislosti riešiť je rozdelenie pracovnej sily medzi hľadanie nových zdrojov a ťaženie už nájdených zdrojov.

     

     

                Existuje analógia medzi zháňaním potravy u včiel a vyhľadávaním informácií u človeka. Teória zháňania informácií (Information foraging) používa biologické modely ako metaforu správania sa ľudí pri vyhľadávaní informácií. Podľa tejto teórie sa ľudia pri vyhľadávaní informácií správajú rovnako ako naši predkovia pri zháňaní potravy. Informácie, takisto ako potrava, majú zhlukový charakter a ľudia pri ich vyhľadávaní riešia podobné otázky ako včely a to či ostať na aktuálnej stránke, alebo ísť hľadať inde a ktorú cestu nasledovať pri hľadaní. Analógia správania sa včiel sa ukazuje ako vhodný prístup pri vyhľadávaní, preto sa tomuto problému venujem aj mojej diplomovej práci.

     

     

    Súčasné riešenia

     

               Možnosťou využitia správania sa včiel sa už zaoberalo niekoľko prác. Tieto práce sa zaoberajú možnosťami vyžitia včiel na Internete, alebo ich použitím v systéme na odporúčanie prípadov. Zoznam vedeckých prác zaoberajúcich sa touto problematikou je uvedení v kapitole Použitá literatúra. 

     

     

     

     

     

     

     

               V týchto prácach boli vypracované viaceré modely správania sa včiel. Niektoré sa smažia čo najvernejšie popísať fungovanie kolónie včiel. Takýmto je aj model v práci [2]. Je pomerne komplikovaný a priamo nepoužiteľný pri praktickom riešení. V práci [5], vytvorili autori jednoduchý matematický model. Na základe toho modelu vznikol navrhli v [1] multi-agentový systém CASIS. Cieľom bolo vytvoriť čo najjednoduchší a najpoužiteľnejší model na použitie v oblasti získavania informácií. V niektorých dlhších prácach sa používajú modely podobné tomuto, z rôznymi ďalšími úpravami.

     

     

     

    Popis riešenia

     

                Moje riešenie sa skladá z grafického rozhrania, modelu správania sa včiel a systému na vyhodnotenie výsledkov.

     

     

                Grafické rozhranie slúži na zadanie stránky, ku ktorej chceme vyhľadávať podobné stánky a na zobrazene výsledkov vyhľadávania aj z vyhodnotením presnosti a pokrytia.

     

     

                Pri návrhu modelu správania sa včiel som vychádzal z modelu z práce [1], ktorý je zobrazený na Obr. 1.

     

     

     

    vcely.bmp

    Obrázok 1. Model systému CASIS [1]

     

     

     

      

    Po zadaní vstupnej stránky sa táto načíta a z jej obsahu sa vytiahnu odkazy na ďalšie stránky, tieto odkazy sa umiestia medzi zdroje, s ktorými včely pracujú. Včely sa najprv náhodne rozletia na tieto zdroje. Zdroje spracujú a následne ak je zdroj dobrí môžu naň lákať ďalšie včely. Nalákané včely budú následne posielané na zdroje, ktoré boli vytiahnuté zo stránky, na ktorú boli nalákané. Stránky pri ktorých bola zaznamenaná podobnosť zo stránkou, na ktorej sme začali sa zobrazia ako výsledok.

     

     

                Určovať podobnosť stránok je komplikovaná záležitosť. Jednoduché nie je ani samotné definovanie toho čo za podobné pokladáme. Pre účely tohto projektu som použil len veľmi jednoduchú funkciu, ktorá určuje podobnosť len na základe výskytu slov v  nadpisoch článkov.

     

     

                Výsledky sú nakoniec spracované. Ak používateľ zadá očakávané výsledky z testovacej množiny, program nakoniec z výsledkov vypočíta presnosť a pokrytie.

     

     

                Program som implementoval v jazyku Java. Na spracovanie web stránok som použil knižnicu z názvom WebSPHINX. Táto knižnica sa jednoducho používa, ja som ju využil na sťahovanie stránok, vyťahovanie odkazov zo stránok a určenie slov, ktoré sa na stránke nachádzajú v určitých tagoch.  

     

     

     

     

     

    Popis algoritmu na rozhodnutie na propagovanie zdroja 

     Ak má včela priradený zdroj, môže sa rozhodnúť ísť ho propagovať. Jej rozhodnutie záleží od kvality zdroja. Kvalita je vyjadrená jedným číslom v rozsahu <0,1>, pričom 1 je najlepšie. Včela môže v každom cykle s pravdepodobnosťou kvalita neopustí zdroj. Ak zdroj neopusti tak z pravdepodobnosťou 1 – kvalita pôjde zdroj propagovať do tančiarne. Účinnosť propagácie záleží od toho koľko včiel ho naraz propaguje. Čas propagácie je závislý od kvality zdroja a vypočíta sa ako MaximálnyČasTancovania x kvalita.

     

    Testovanie

     

                Na testovanie softvéru som použil asi 100 stránok. Jedná sa o herné recenzie z portálu www.sector.sk. Program má nastavené obmedzenia aby vyhľadával len na tejto stránke v sekcii recenzie PC hier. Program som testoval najprv on-line s obmedzením počtu prejdených stránok na 100, kvôli rýchlosti. Použitý model správania sa včiel je ešte vo fáze vývoja a nie je optimalizovaný a väčšie množstvo stránok by už vyžadovalo aj niekoľko minú spracovávania.

     

               

     

                Program môže pracovať aj off-line pokiaľ, má používateľ stiahnutú aspoň danú časť stránky. Na vyhodnotenie presnosti som siahol asi 100 stránok z recenziami. Program je nastavený tak, že neplatné stránky, ktoré nie sú stiahnuté alebo dostupné ignoruje. V testovacej sade som určil 5 stránok a k nim prislúchajúce výsledky, ktoré by som očakával.

     

     

                Je ťažké objektívne určiť čo by sa malo pokladať ako podobné stránky. Tento program slúži ako základ pre experimentovanie z modelom správania sa včiel a funkciou na porovnávanie stránok a tejto problematike sa venujem ďalej v mojej diplomovej práci. V tomto prípade som považoval za podobné stránky, ktoré sa venujú hrám z podobným názvom. Pri tomto experimente program vráti vždy zoznam stránok, ktoré sa venujú hrám z názvom podobným názvu hry na vstupnej stránke. Keďže včely v tomto testovacom prípade prejdú všetky stránky, výsledkom pri všetkých pokusoch bolo pokrytie aj presnosť 1. Napríklad pri vyhľadávaní podobných stránok ku stránke z recenziou na hru Fifa 09, sú výsledkom stránky o hrách Fifa street, NHL 09 a NBA LIVE 09. Výsledky som skúšal porovnávať s funkciou vyhľadávania podobných stránok Google. Pri obmedzení takéhoto vyhľadávania na sekciu ktorú používam na testovanie, nevráti žiadne výsledky, takže porovnanie nie je možné

     

     

     

     

    Použitie softvéru

     

                Na spustenie programu je potrene mať nainštalované Java Runtime Environment. Samotný program nie je potrebné inštalovať. Stačí spustiť súbor vyhladavanie.jar. Na spustenie vyhľadávania treba zadať URL stránky, ku ktorej hľadáme podobné stránky. 

    Použitá literatúra

     

    [1]       Lorenzi, F., Scherer dos Santos, D., Bazzan, A.L.C.: Case-Based RecommenderSystem Inspired by Social Insects. In: Proc. XXV Congresso da Sociedade Braseilera de Computacao, Sao Leopoldo, 2005, s. 752-760.

     

     

    [2]       De Vries H. and Biesmeijer J.C.: Modelling collective foraging by means of individual behaviour rules in honey-bees. Behav. Ecol. Sociobiol 44, 1998, s. 109-124

     

     

    [3]       The honey bee dance language, NC State University, NORTH CAROLINA COOPERATIVE EXTENSION SERVICE

     

     

    [4]       Stephen J. Schultze: A collaborative foraging approach to web browsing enrichment. CHI Extended Abstracts, 2002, s. 860-861

     

     

    [5]       Camazine, S. and Sneyd, J.: A model of collective nectar source selection by honey bees: Self-organization through simple rules. Journal of Theoretical Biology, 149(4),  1991, s. 547-571

     

    [6]       Pavol Návrat, Martin Kováčik, Anna Bou Ezzeddine, Viera Rozinajová: Metafora včelieho úľa – model vyhľadávania a odporúčania informácií, Ústav informatiky a softvérového inžinierstva FIIT STU

     

    [7]       Pavol Návrat, Martin Kováčik, Anna Bou Ezzeddine, Viera Rozinajová: Vyhľadávanie informácií pomocou včiel, Ústav informatiky a softvérového inžinierstva FIIT STU

     

     

     

     

     

     

     

    Tag page (Edit tags)
    • No tags
    You must login to post a comment.
    Powered by MindTouch Core