HOVYSOKÉ UČENÍ TECHNICKÉ V BRNĚ BRNO UNIVERSITY OF TECHNOLOGY
FAKULTA INFORMAČNÍCH TECHNOLOGIÍ ÚSTAV INFORMAČNÍCH SYSTÉMŮ FACULTY OF INFORMATION TECHNOLOGY DEPARTMENT OF INFORMATION SYSTEMS
WEBOVÁ APLIKACE DOPORUČOVACÍHO SYSTÉMU
DIPLOMOVÁ PRÁCE MASTER’S THESIS
AUTOR PRÁCE AUTHOR
BRNO 2013
Bc. PAVEL HLAVÁČEK
VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ BRNO UNIVERSITY OF TECHNOLOGY
FAKULTA INFORMAČNÍCH TECHNOLOGIÍ ÚSTAV INFORMAČNÍCH SYSTÉMŮ FACULTY OF INFORMATION TECHNOLOGY DEPARTMENT OF INFORMATION SYSTEMS
WEBOVÁ APLIKACE DOPORUČOVACÍHO SYSTÉMU WEB APPLICATION OF RECOMMENDER SYSTÉM
DIPLOMOVÁ PRÁCE MASTER’S THESIS
AUTOR PRÁCE
Bc. PAVEL HLAVÁČEK
AUTHOR
VEDOUCÍ PRÁCE SUPERVISOR
BRNO 2013
Doc. Ing. Jaroslav Zendulka, CSc.
Abstrakt Práce se zabývá problematikou doporučovacích systémů a jejich využití ve webových aplikacích. Jsou zde shrnuty základní techniky data miningu a jednotlivé přístupy pro doporučování. Hlavní částí práce je návrh a implementace webové aplikace pro doporučování jídla z restaurací. Je zde navržen a implementován algoritmus pro doporučování jídel, který se snaží řešit problém s často měnicími položkami. Tento algoritmus vychází z hybridní techniky filtrování založené na obsahu a znalostech, která pro vlastní výpočet využívá kosinové podobnosti vektorů.
Abstract This thesis deals with problems of recommender systems and their usage in web applications. Basic data mining techniques and recommendation approaches are summarized in the theoretical part of the work. Main part of this thesis is a suggestion and an implementation of web applications for recommending dishes from restaurants. Algorithm for food recommendation has been designed and implemented in this paper. The algorithm deals with the problem of frequently changing items and it utilizes hybrid filtering technique that is based on content and knowledge. This filtering technique uses cosine vector similarity for computation.
Klíčová slova Dolování z dat, doporučovací systémy, kolaborativní filtrování, filtrování založené na obsahu, doporučování jídel, kosinová podobnost
Citace Hlaváček Pavel: Webová aplikace doporučovacího systému, diplomová práce, Brno, FIT VUT v Brně, 2013
Webová aplikace doporučovacího systému Prohlášení Prohlašuji, že jsem tuto diplomovou práci vypracoval samostatně pod vedením Doc. Ing. Jaroslava Zendulky, CSc. Další informace mi poskytl Ing. Martin Hlosta. Uvedl jsem všechny literární prameny a publikace, ze kterých jsem čerpal.
…………………… Bc. Pavel Hlaváček 15.5.2013
Poděkování Za pomoc, podněty, trpělivé konzultace a odborné rady děkuji Ing. Martinu Hlostovi a Doc. Ing. Jaroslavu Zendulkovi, CSc.
Obsah Obsah ...................................................................................................................................................... 1 1 Úvod ............................................................................................................................................... 2 2 Data mining.................................................................................................................................... 4 2.1 Dolovací úlohy........................................................................................................................ 5 2.1.1 Asociační analýza ........................................................................................................... 5 2.1.2 Klasifikace a predikce..................................................................................................... 5 2.1.3 Shluková analýza ............................................................................................................ 6 2.1.4 Analýza odlehlých hodnot a evoluční analýza................................................................ 6 2.2 Metodiky ................................................................................................................................. 7 2.2.1 Metodika SEMMA ......................................................................................................... 7 2.2.2 Metodika CRISP-DM ..................................................................................................... 8 2.3 Web mining ............................................................................................................................ 9 2.4 Potenciální nebezpečí a problémy ........................................................................................ 10 3 Doporučovací systémy ................................................................................................................. 11 3.1 Přístupy filtrování ................................................................................................................. 12 3.1.1 Kolaborativní filtrování (Collaborative filtering) ......................................................... 12 3.1.2 Filtrování založené na obsahu (Content-based) ............................................................ 15 3.1.3 Filtrování založené na znalostech (Knowledge-based)................................................. 16 3.1.4 Hybridní přístup (Hybrid approach) ............................................................................. 17 3.2 Nejznámější doporučovací systémy...................................................................................... 18 3.3 Testovací metriky ................................................................................................................. 19 3.4 Problémy ............................................................................................................................... 21 4 Návrh aplikace ............................................................................................................................. 23 4.1 Návrh sběru dat ..................................................................................................................... 23 4.1.1 Možnosti získání dat ..................................................................................................... 24 4.2 Návrh webové aplikace......................................................................................................... 24 4.3 Návrh parseru RSS kanálu .................................................................................................... 26 4.4 Návrh doporučování ............................................................................................................. 27 4.5 Neformální specifikace požadavků ....................................................................................... 29 5 Implementace ............................................................................................................................... 30 5.1 Použité technologie............................................................................................................... 30 5.1.1 Asp.Net ......................................................................................................................... 31 5.1.2 Entity Framework ......................................................................................................... 33 5.2 Webová aplikace................................................................................................................... 36 5.3 RSS Parser ............................................................................................................................ 41 5.4 Doporučování ....................................................................................................................... 43 5.5 Hosting.................................................................................................................................. 46 6 Testování a zhodnocení................................................................................................................ 47 6.1 Testování doporučování........................................................................................................ 47 6.2 Uživatelské testování ............................................................................................................ 49 6.3 Zhodnocení ........................................................................................................................... 50 7 Závěr ............................................................................................................................................ 51
1
1
Úvod
V současné době, kdy se celosvětová internetová síť rapidně rozšiřuje, rostou i objemy dat uchovávaných v jednotlivých systémech. Z pohledu byznysu jsou to velice užitečné informace, které mohou zvýšit zisk, ale musí se umět využít. K tomuto účelu slouží data mining (Dolování dat z databází). Data mining neboli „dolování z dat“ je proces získávání zajímavých, ale dosud neznámých znalostí z dat. Mnohdy je škoda, pokud ve firmě leží ladem zajímavá data, anebo jejich zpracování spočívá pouze ve vytvoření tabulek a grafů v Excelu nějakým zaměstnancem. Při správném přístupu k dolování z dat lze získat přehlednou segmentaci zákazníků, kterou lze využít k lepšímu cílenému marketingu. Dále se dolování z dat dá využít pro analýzu nákupního košíku, na základě které můžeme uživateli doporučit podobné zboží, nebo pro shlukovou analýzu, která nám umožní získat skupiny vysoce ziskových zákazníků a zaměřit se na ně s cílem vyššího obratu. Využití data miningu je opravdu veliké. K získání potřebných dat pro data mining slouží firemní CRM systémy, které pomáhají sledovat a vyhodnocovat veškeré obchodní aktivity v rámci celé společnosti. Cílem CRM systémů je především zlepšit cílení služeb, lépe porozumět zákazníkům a identifikovat jejich konkrétní potřeby. To umožňuje budovat dlouhodobě prospěšné vztahy se zákazníky a tím vytěžit z jednoho zákazníka větší zisk. Typickým příkladem těchto systémů jsou internetové obchody, kde se nachází mnoho produktů. Každý produkt bývá popsán pomocí několika atributů, na základě kterých je zařazen do kategorií. Od takovýchto systémů se však očekává, že budou plnit funkce, které usnadní práci zákazníkovi i majiteli. Cílem je tedy vytvořit funkce, které budou doporučovat jednotlivé produkty na základě informací získaných o zákaznících a produktech. Tím by internetové obchody mohly dosahovat vyšších obratů a zákazníci se mohli lépe orientovat v nabízených produktech. K tomuto účelu se používají doporučovací systémy, které se pomocí různých metod snaží hledat jednotlivé souvislosti v získaných znalostech. Tyto souvislosti jsou poté reprezentovány tabulkou podobností, na základě které je poté provedeno doporučení. V současné době tyto systémy nachází velké uplatnění a jsou čím dál častěji používány. I přesto stále existují oblasti, pro něž se často nevyskytují. Jednou z takovýchto oblastí je doporučování jídla. V této oblasti se systém snaží doporučit uživateli jídlo, které nejlépe vystihuje jeho návyky a preference. Dalo by se říci, že se jedná o oblast podobnou internetovým obchodům, ale jsou zde značné rozdíly. Především se jedná o časté přidávání nových položek. To je jeden z problému, kterým trpí některé metody doporučování. Na základně dohody s vedoucím práce a konzultantem práce byla zvolena tato oblast tématem práce. Výzvou je tedy najít optimální způsob, jakým doporučovat jednotlivá jídla. Teoretickou část práce tvoří kapitoly dvě a tři. V druhé kapitole je definován pojem data mining. Poté následuje část věnující se nejznámějším metodikám. Podrobně jsou popsány metodiky SEMMA a CRISP-DM. Dále je zmíněn pojem web mining. Třetí kapitola se věnuje samotnému doporučování. Nachází se zde jednotlivé přístupy filtrování a jejich možné problémy, kterými trpí. Nedílnou součástí jsou testovací metriky, které slouží pro ohodnocení kvality doporučovacích systémů. Praktickou část tvoří kapitoly čtyři, pět a šest. Je v nich postupně rozebrán návrh, realizace a testování celého projektu, který je rozdělen do několika částí. Skládá se z webové aplikace, webové služby (parser RSS) a doporučovacího systému. Ve čtvrté kapitole je tedy postupně rozebrán návrh
2
všech částí projektu. Za ní následuje kapitola pět, která se zabývá samotnou realizací. Jsou zde uvedeny nejdůležitější části implementace. Poslední kapitole šest je věnováno testování výsledné aplikace, zhodnocení kvality doporučení a celkové funkčnosti systému. Celá práce je pak shrnuta v závěru.
3
2
Data mining
Pojem „data mining“ neboli „dolování z dat“ různí autoři definují různě. Jednou z nejjednodušších a nejkratších může být následující definice. Definice 2.1: Data mining je netriviální proces získávání implicitních, dříve neznámých a potenciálně užitečných informací z dat. [11] Tak, jak je ukázáno v [1], data mining je analytická metodologie, kterou někdy chápeme jako analytickou součást dobývání znalostí z databází (Knowledge Discovery in Databases, KDD – viz Obrázek 1). Z počátku se pro tuto oblast razily nejrůznější názvy: harvesting, data archeology, data destilery. Nakonec ale převládla metafora: dobývání znalostí a dolování z dat. Po jisté době tápání se ustálilo i chápání KDD jako interaktivního a iterativního procesu tvořeného kroky selekce, předzpracování a transformace, vlastního „dolování“ a interpretace.
Obrázek 1: Proces dobývání znalostí z databází [11]
Na rozdíl od „prostého“ použití statistických metod a metod strojového učení se v procesu dobývání znalostí klade důraz již i na přípravu dat pro analýzu a na interpretaci výsledných znalostí. Při přípravě dat, obvykle uložených ve složité struktuře, se vytváří jedna tabulka obsahující relevantní údaje o sledovaných objektech. Při interpretaci se poté nalezené znalosti hodnotí z pohledu koncového uživatele. Dolování z dat lze rozdělit do dvou základních skupin dolovacích úloh: [16] •
Deskriptivní – Popisují data a snaží se v nich nalézt obecné vlastnosti, zajímavé charakteristiky a podobně. Využívají metody učení bez učitele a příkladem jsou asociační a shluková analýza.
•
Prediktivní – Cílem těchto úloh je na základě poznatků z analyzovaných dat něco předpovědět. Využívají především metody učení s učitelem a mezi příklady řadíme klasifikaci a predikci.
4
Dolování z dat je velice důležitým nástrojem v procesu rozhodování, zejména pro střední a vyšší management. Stává se nepostradatelným i v dalších odděleních firem, kam si postupně proráží cestu.[3]
2.1
Dolovací úlohy
Jedná se o úlohy, které řeší mnohdy zdánlivě nesouvisející problémy z nejrůznějších oborů. Je pozoruhodné, kolik praktických aplikací má několik obecných metod analýzy dat. Výběr metody, která bude použita pro řešení daného problému, je jen jedním z kroků procesu dolování z dat. Je třeba mít na zřeteli cíl, pro jehož splnění lze použít více metod. Pak je dobré znát jejich výhody a mít možnost porovnat jejich výsledky. Jelikož těchto typů úloh existuje více, uvedeme si jen ty nejznámější. Následující text byl převzat a upraven z [16][17].
2.1.1
Asociační analýza
Jedná se o deskriptivní úlohu, která se snaží v datech hledat frekventované vzory, tzn. takové, které se vyskytují dostatečně často. Takovým vzorem může být asociační pravidlo ve tvaru Nákup(‘lyžáky‘) => Nákup(‘lyže‘). Toto pravidlo říká, že pokud si někdo koupil lyžáky, koupil si i lyže. Tyto pravidla mají dvě důležité míry, které charakterizují jejich kvalitu. Jedná se o podporu a spolehlivost. •
Podpora – pro výše uvedené pravidlo by značila, v kolika procentech ze všech nákupů byly lyžáky a lyže.
•
Spolehlivost – pro výše uvedené pravidlo by udávala, v kolika procentech nákupů z těch, ve kterých byly lyžáky, byly zároveň i lyže.
2.1.2
Klasifikace a predikce
Klasifikace se snaží nalézt ze vstupních dat model, který bude nová data zařazovat do předem známých tříd. Samotný proces klasifikace se skládá ze dvou kroků: •
Učení – spočívá v tvorbě klasifikačního modelu schopného klasifikovat data pomocí trénovacích dat.
•
Vlastní klasifikace – využití modelu pro klasifikaci dat (zařazení do tříd).
Pro klasifikace existuje mnoho modelů, kde každý je v hodný pro jiný typ dat. Patří sem především Bayesovská klasifikace, rozhodovací stromy a neuronové sítě. Na rozdíl od klasifikace predikce nezařazuje data do předem známých tříd, ale je označována jako proces určení dodatečných, případně chybějících, hodnot atributů analyzovaného záznamu. Nejznámějším druhem predikce je regrese.
5
2.1.3
Shluková analýza
Shluková analýza je založená na seskupování dat, která si jsou podobná a mají blízko k sobě do shluků (skupin). Na rozdíl od klasifikace, kde se snažíme data zařazovat do tříd, zde tyto třídy nemáme a snažíme se je hledat na základě podobnosti a rozdílnosti mezi daty. Tyto třídy pak nazýváme shluky. Shluky pak obsahují data, jejichž podobnost je maximální, zatímco podobnost s daty mimo tento shluk je minimální. Shlukováním je možné najít vztahy mezi daty bez jejich dalšího vysvětlení nebo interpretace. Jinými slovy, shluková analýza nachází strukturu mezi daty bez vysvětlení, proč existuje. Algoritmy shlukové analýzy můžeme rozdělit na hierarchické a nehierarchické. •
Hierarchické shlukování – je systém podmnožin, kde průnikem dvou podmnožin (shluků) je buď prázdná množina, nebo jeden z nich. Pokud nastane aspoň jednou druhý případ, tak se jedná o hierarchický systém.
•
Nehierarchické shlukování – je takový systém, kde průnik shluků je prázdný. Jedná se tedy o disjunktní množiny.
Existuje mnoho způsobů, jak shlukovat jednotlivé objekty na základě jejich vzdálenosti či podobnosti. Patří sem především metoda nejbližšího (nejvzdálenějšího) souseda, centroidní a další.
2.1.4
Analýza odlehlých hodnot a evoluční analýza
Tato analýza je prakticky opakem shlukové analýzy. Ve shlukové analýze hledáme často se vyskytující vzory, kdežto zde nás zajímají hodnoty, které se výrazně liší od ostatních a mohly by být v jiných úlohách odstraněny. Proto je nutné, při fázi předzpracování dat neprovádět filtraci odlehlých hodnot. Typickým využitím této úlohy je hledání podezřelých finančních transakcí označující možný podvod. Evoluční analýza se zaměřuje na objekty, které se v čase mění. Snaží se v nich nalézt různé pravidelnosti a trendy. Typickým příkladem použití může být sledování akcií, které nám pak napomáhá k odhadnutí budoucího vývoje.
6
2.2
Metodiky
Jelikož data mining zahrnuje velkou šíři metod a způsobu práce, je obtížné podat jednoznačný návod k postupu. Podle [1] se v data miningu vyskytují 2 druhy metodik, které popisují proces dobývání znalostí z databází. Jedná se zaprvé o metodiky založené na technologickém pohledu, kde se většinou postupuje podle [11] po následujících krocích: selekce dat, předzpracování dat, transformace dat, dolování dat a interpretace dat. Druhá sada metodik je založena na manažerském pohledu. V těchto metodikách se obvykle postupuje po krocích: porozumění problematice, porozumění datům, příprava dat, modelování, vyhodnocení výsledků a využití výsledků. Přesto se během 90. let vykrystalizovaly dvě obecné metodologie, které alespoň v hrubých rysech popisují jednotlivé kroky: metodologie SEMMA a metodologie CRISP-DM. Tak, jak je ukázáno v [1], společnou podstatnou všech metodologií jsou posloupnosti těchto kroků: • • •
• •
2.2.1
Obchodní/praktický – nutnost formulace úlohy, nelze něco provádět naslepo. Datový – předpřipravení dat pro analýzu. Analytický – hledání informace v datech, vytváření statistických modelů s využitím nejrůznějších metod od jednoduchých tabelací a vizualizací až po sofistikované přístupy jako je genetické programování (rozhodovací stromy, neuronové sítě). Výstupem bývají obecnější znalosti (svobodní klienti nejčastěji nakupují pozdě večer, zatímco ženatí po obědě) a matematické modely (např. postup, jak vytipovat potenciálního klienta pro daný produkt). Aplikační – zjištěné poznatky a model je třeba uvést do praxe, prezentovat výsledek. Kontrolní – ověření zpětné vazby, v případě dlouhodobě nasazovaných modelů zkontrolovat jeho efektivitu, zda nezestárl.
Metodika SEMMA
Softwarový produkt firmy SAS vychází z vlastní metodiky pro dobývání znalostí z databází. Název SEMMA charakterizuje jednotlivé prováděné kroky:[1] •
Prvním krokem je Sample – výběr, který umožňuje rozpoznávat vstupní datové soubory (rozpoznává vstupní data, provádí výběr z rozsáhlejších dat, rozděluje datový soubor na trénovací, validační a testovací množinu).
•
Druhý krok, Explore – průzkum, prozkoumává datový soubor pomocí statistických a grafických metod.
•
Třetí krok, Modify – úprava, obsahuje přípravu dat pro analýzu (vytváří doplňkové proměnné, identifikuje odlehlá či extrémní pozorování, provádí shlukovou analýzu, analyzuje data pomocí sítí).
•
Čtvrtý krok, Model – modelování, kvalifikuje prediktivní model (modeluje cílovou proměnnou použitím regresních modelů, rozhodovacích stromů, neuronových sítí nebo uživatelem definovaných modelů). 7
•
V pátém kroku, Assess – vyhodnocení, se porovnávají vytvořené prediktivní modely (vytvořené grafy, které vyznačují procenta vysvětlení, procenta odpovědí, růstové grafy a grafy užitku). SAMPLE
Výběr vzorku dat
EXPLORE
Vizualizace dat
Shlukování
MODIFY
Selekce a vytváření veličin
Transformace dat
MODEL
Neuronové sítě
Modely založené na stromech
ASSESS
Logistické modely
Zhodnocení
Obrázek 2: Metodika SEMMA převzato a upraveno z [3]
2.2.2
Metodika CRISP-DM
Metodika vznikla v rámci Evropského výzkumného projektu. Její celý název zní CRoss-Industry Standard Process for Data Mining. Cílem projektu bylo navrhnout univerzální přístup pro dobývání znalostí, který bude použitelný v nejrůznějších komerčních aplikacích. Navíc má kromě standardního postupu nabízet „průvodce“ potenciálními problémy a řešeními, které se mohou vyskytnout v reálných aplikacích.
Porozumění datům
Porozumění problematice
Využití výsledků
Data
Vyhodnocení výsledků
Příprava dat
Modelování
Obrázek 3: Metodika CRISP-DM převzato a upraveno z [3]
8
Životní cyklus projektu dobývání znalostí je podle této metodiky tvořen šesti fázemi (porozumění problematice, porozumění datům, příprava dat, modelování, vyhodnocení výsledků, využití výsledků) – viz obrázek 3. Přičemž pořadí jednotlivých fází není přesně dáno a výsledek dosažený v jedné fázi ovlivňuje volbu následujících kroků. Často se stává, že se k jednotlivým krokům vracíme. [1]
2.3
Web mining
Při dobývání znalostí se v poslední době objevují i nové oblasti aplikací. Mezi dnes velmi populární oblasti patří dobývání znalostí z textu tzv. text mining a dobývání znalostí z webu, tzv. web mining. Do budoucna se dá očekávat i rozvoj oboru multimédia mining, tedy dobývání znalostí z multimediálních dat, kombinující texty, obrázky, zvuky a videosekvence. Webmining, nebo-li proces získávání znalostí z webového prostředí, směřuje svoji pozornost na nejdynamičtěji se rozvíjející zdroj informací současnosti. V některých případech web slouží jako zdroj dat pro „klasické“ dobývání znalostí z databází i pro dobývání znalostí z textů, v jiných případech jde o nové typy úloh, vyplívající ze zvláštností internetu. Podle analýzy cílů můžeme web mining rozdělit do tří různých typů, které jsou: •
Web usage mining – dobývání znalostí na základě obsahu webu je proces extrakce užitečné informace z logů serverů a uživatelů, tj. z historie. Je to proces hledání, co uživatelé vyhledávají na internetu.
•
Web content mining – dobývání znalostí na základě obsahu webu je analogický cíli dobývání znalostí z textů. Chceme tedy získat znalosti z webovských stránek chápaných jako dokumenty. V kontextu internetu jde o vyhledávání, metavyhledávání či dobývání znalostí „skrytých“ ve stránkách.
•
Web structure mining – dobývání znalostí na základě struktury webu je proces používání teorie grafů pro analýzu prohlížení webu jako graf, kde uzly jsou dokumenty (stránky) a hrany jsou vazby (odkazy) mezi stránkami.
Cílem dobývání znalostí na základě používání webu je analýza chování uživatelů při procházení jednotlivých stránek. Zdrojem dat jsou serverové logy zachycující údaje o IP adrese uživatelova počítače, datu a čase přístupu, navštíveném URL a typu požadavku. Z hlediska získávání znalostí jde tedy o časová data, která můžeme chápat jako sekvence stránek navštívených jedním uživatelem. V těchto sekvencích můžeme hledat často opakující se sekvence metodami vyvinutými v souvislosti s asociačními pravidly, můžeme rovněž hledat skupiny uživatelů vyznačujících se podobným chováním různými metodami shlukování. Takto získané znalosti o chování jednotlivých návštěvníků na daném webovém serveru můžeme využít pro vylepšení samotného serveru, anebo pro potřeby reklamy. Z experimentálních systémů pro tuto oblast je velice významný WebLogMiner, který lze využít pro dobývání znalostí z logů, systém WebSIFT1 (Web Site Information Filter System) nabízející pro analýzu přístupu k webu asociační pravidla, shlukování a i statické metody. V současné době však nesmíme zapomenout na analýzu nákupního košíku v internetových obchodech, kde získané informace lze využít pro doporučování dalšího zboží.[1] 1
Při využití data miningu nad komerčními daty, kde dochází často k masivnímu a inteligentnímu zpracování osobních údajů, vznikají často obavy ze zneužití informací. Může dojít k záměrnému nebo i nezáměrnému úniku dat a jejich využití pro nečestné aktivity, ať už se jedná o spam či vydírání. V současné době se ale zdá, že toto nebezpečí je nepatrné. Za větší potenciální nebezpečí lze považovat technologie, které se využívají k data miningu v akademické sféře. Například dekódování genomu může být použito k nehumánním selekcím osob postavených na vědeckém základě. Případně pokročilé metody identifikace osob a jejich následné sledování pomocí kamerového systému. Za předpokladu, že máme správná data a použijeme-li správný způsob dobývání, dostaneme správné výsledky. Proto by dobývání dat mělo být založeno na správných datech. Nicméně protože se používají statistické metody, tak výsledky jsou tzv. statisticky správně, to znamená, že jsme schopni s malou pravděpodobností odvodit chybné výsledky (falešně pozitivní). Při dobývání typicky neodhalíme všechny souvislosti schované v datech.
10
3
Doporučovací systémy
Doporučovací systémy (Recommender Systems) jsou softwarové nástroje a techniky poskytující návrh položek, které budou uživateli užitečné. Jsou podtřídou informačního filtračního systému, který se snaží předvídat hodnocení nebo preference jednotlivých položek (např. hudba, knihy, jídlo, filmy,…) nebo sociálních elementů (osoby, skupiny lidí) za pomoci stavění modelů. Doporučovací systémy jsou tedy primárně orientované na uživatele, kteří nemají s položkami dostatečné zkušenosti nebo nemají dostatečnou kompetenci, aby dokázali vyhodnotit všechny možnosti alternativních položek, které mohou například naleznout na webové stránce. Doporučovací systémy se v současné době používají v mnoha aplikacích. Příkladem jsou webové obchody, on-line komunity a hudební přehrávače. Lidé mají většinou tendenci si spojovat doporučovací systémy s komerčními weby, kde doporučující systém navrhuje produkty a informace, které mu pomohou se rozhodnout o případné koupi. Produkty mohou být doporučovány na základě demografie uživatelů nebo na základě analýzy minulého nakupování uživatelů jako predikce budoucího nákupního chování.[4][6]
Obrázek 4: Filtrování v doporučovacím systému převzato z [4]
Kolaborativní filtrování (Collaborative filtering) a filtrování založené na obsahu (Contentbased filtering) jsou dvě základní algoritmické techniky používané pro počítačové doporučení. Filtrování obsahu vybírá položky na základě korelace mezi obsahem a preferencemi uživatele, kdežto kolaborativní filtrování vybírá položky na základě korelace mezi lidmi s podobnými preferencemi. Systémy používající druhou techniku se také nazývají jako „automatické doporučovací systémy“. Kromě toho byl dále vyvinut hybridní přístup, aby se zabránilo určitým omezením, týkajících se doporučování na základě filtrování obsahu. Návrhy jsou obvykle individualizované, takže každý uživatel dostane jiné. Existují však i techniky, které poskytují neindividualizované návrhy, které jsou mnohem jednoduší na vytvoření. Tyto techniky jsou obvyklé v novinách, časopisech a fotogaleriích. Typickým reprezentantem této kategorie doporučování je nejlepší desítka „TOP 10“ podle prodeje nebo hodnocení zákazníků. Tyto návrhy jsou kolikrát velice užitečné, ale z pohledu doporučovacích systému nezajímavé.[4]
11
Vlastní doporučování se skládá ze tří krokového procesu: 1. Na začátku proces vyžaduje nějaká vstupní data. Tato vstupní data pomáhají systému porozumět, zda se daný produkt uživateli líbí nebo nelíbí. 2. Cílem procesu je najít podmnožinu položek, o kterých se ví, že nejvíce vyhovují zájmu aktivního uživatele. 3. Po nalezení této podmnožiny položek je předložena uživateli jako množina, která nejvíce vyhovuje jeho chování.
3.1
Přístupy filtrování
Dle [2] můžeme techniky doporučovácích systémů rozdělit následovně: • • • •
3.1.1
Kolaborativní filtrování (Collaborative filtering) Filtrování založené na obsahu (Content-based filtering Filtrování založené na znalostech (Knowledge-based filtering) Hybridní přístup (Hybrid approach)
Myšlenkou tohoto přístupu je fakt, že uživatelé, kteří v minulosti sdíleli stejné zájmy o položku, budou mít i v budoucnu podobný vkus. Například, pokud uživatelé A a B mají velmi podobnou nákupní historii a uživatel A si koupí novou položku, tak logickým výstupem na základě koupi bude doporučení položky uživateli B. Kolaborativní filtrování je metoda tvorby automatických tipů (filtrování) položek pro uživatele na základě sbírání informací o chování ostatních uživatelů. Její nespornou výhodou je, že nepotřebuje žádná data o položkách. Základní princip kolaborativního filtrování zachycuje Obrázek 5. Dle [2] lze kolaborativní filtrování rozdělit na dva přístupy, a to na filtrování založeném na podobnosti uživatelů a na filtrování založeném na podobnosti položek. Tyto přístupy se od sebe liší především v hledání podobnosti. Jeden využívá podobnost uživatelů a druhý podobnost položek. Oba tyto přístupy jsou podrobněji rozebrány níže. Nadále tyto dva přístupy ještě můžeme klasifikovat jako paměťové nebo modelové. V modelovém přístupu jsou data předzpracována offline a je vytvořen model pro uživatele. Poté v režimu online je potřeba pouze tento předpřipravený model k vytvoření doporučení. V případě doporučování na základě podobnosti historie nákupu uživatelů, kdy je k vygenerování doporučení použita přímo originální databáze, se jedná o paměťový přístup. Tento přístup má mnohem přesnější návrhy, protože využívá všechna dostupná data k vygenerování doporučení. Nastává však problém s výpočty pro velké databáze.
12
Obrázek 5: Kolaborativní filtrování převzato z [4]
Doporučování založené na podobnosti uživatelů (User-based) Na základě podobnosti aktivního uživatele s ostatními je v tomto přístupu vybrána podmnožina uživatelů. Pomocí této podmnožiny se dále vypočítá hodnocení pro položky, které aktivní uživatel ještě neviděl, a nejlépe hodnocené položky se mu doporučí. Základní myšlenkou metody je fakt, že pokud měli uživatelé podobný vkus v minulosti, budou ho mít i v budoucnosti, jelikož uživatelské preference zůstávají stabilní a v průběhu času konzistentní.
Obrázek 6: Hodnotící matice pro doporučování [12]
Prvním krokem je tedy přiřazení váhy podobnosti ostatním uživatelům podle aktivního uživatele. Podobnost mezi dvěma uživateli se nejčastěji počítá pomocí Pearsonova korelačního koeficientu: ∑
,
∑
,
,
∑
,
,
Kde , je váha podobnosti, u označuje uživatele a a značí aktivního uživatele. I je množina položek ohodnocena oběma uživateli, , je hodnocení položky i uživatelem a a je průměrné hodnocení uživatele a, , je hodnocení položky i uživatelem u a je průměrné hodnocení uživatele u. Druhým krokem je selekce uživatelů s největší podobností s aktivním uživatelem. Jde tedy o hledání nejbližšího souseda. Třetím krokem je předpověď hodnocení z kombinace vybraných uživatelských hodnocení. Tuto předpověď můžeme spočítat pomocí následujícího vzorce: ,
∑
,
∑
∗ ,
,
13
Kde , je předpověď hodnocení aktivního uživatele a pro položku i, kde K je množina nejbližších sousedů. Tento přístup však nelze použít na aplikace, kde se nachází velké množství uživatelů a položek (řádově miliony), protože je nemožné touto metodou vypočítat hodnotící matici v reálném čase.[2][7][13]
Doporučování založené na podobnosti položek (Item-based) Tento přístup je vhodný pro velké komerční weby, které obsahují velké množství položek a uživatelů, jelikož řeší problém skenování velkého počtu sousedů, což je v reálném čase nemožné. Je vhodný tedy pro offline zpracování hodnotící matice a tím pak umožní doporučení v reálném čase i pro velké hodnotící matice.
Hlavní myšlenkou je výpočet předpovědi pomocí podobnosti položek a ne podobnosti mezi uživateli. Podobnosti mezi dvěma položkami i a j můžeme opět vypočítat pomocí Pearsonovy korelace v režimu offline takto: ,
∑
,
∑
,
∑
,
,
Kde U je množina všech uživatelů, kteří ohodnotili obě položky i a j, položky i a je průměrné hodnocení položky i všemi uživateli.
,
je hodnocení uživatele u
Poté hodnocení položky i pro uživatele a může být určeno pomocí následujícího vztahu váženého průměru: ,
∑ ∑
|
,
,
,
|
Kde K je množina sousedících položek hodnocených uživatelem a, které jsou nejvíce podobné položce i.[2][7][13]
14
3.1.2
Filtrování založené na obsahu (Content-based)
Jak uvádí [2], filtrování obsahu je založené na informacích a vlastnostech položky, které mají být doporučeny. Jinými slovy se tyto algoritmy snaží doporučit předměty podobné těm, které uživatel v minulosti ohodnotil (nebo zkoumá v přítomnosti). Zejména různé kandidátské položky jsou porovnávány s položkami dříve hodnocenými uživateli a ty nejlépe odpovídající položky jsou následně doporučeny. Základní princip zachycuje Obrázek 8. V podstatě tyto metody používají profil jednotlivých položek, který specifikuje jednotlivé atributy a charakterizuje položku v rámci systému. Systém z těchto informací vytvoří modely uživatelů, založených na váhovém vektoru položek. Jednotlivé váhy označují důležitost jednotlivých vlastností a můžou být vypočítány samostatně užitím různých technik. Jednoduché metody používají průměrné hodnoty hodnotících vektorů, zatímco jiné sofistikované metody používají metody strojového učení. Například jako Bayesovská klasifikace, shluková analýza, rozhodovací stromy a neuronové sítě s cílem odhadnout pravděpodobnost, že se uživateli daná položka bude líbit.
Obrázek 8: Content based filtering, převzato z [15]
Přímá zpětná vazba od uživatelů, obvykle řešená tlačítkem líbí – nelíbí (like - dislike) může být využita k ovlivnění váhy některých atributů položky. I když tento přístup závisí na dalších informacích o položkách a uživatelích, nepotřebuje velkou uživatelskou základnu k tomu, aby vygeneroval doporučení. List doporučení může být vytvořen, i když existuje jen jeden uživatel. Samotný systém doporučení prozatím neviděné položky spočívá v tom, že systém vyhodnotí jak moc je daná položka podobná těm, které se uživateli v minulosti líbily. Tato podobnost se dá vypočítat několika způsoby. Například stačí, aby obě položky byly zařazeny ve stejné skupině, případně se zaměřit na jednotlivé atributy položek, v kterých se shodují. Výhodou tohoto přístupu je nezávislost na ostatních uživatelích. Stačí nám pouze hodnocení od aktivního uživatele. Další nespornou výhodou je průhlednost celé této metody, kdy jsme schopni přesně určit, na jakém základě byla položka doporučena. Dále systém nemá problémy s nově zařazenými položkami, které ještě nikdo předtím nehodnotil. Mezi nevýhody tohoto přístupu patří přílišná specializace doporučení. Vždy bude doporučen jen ten produkt, který má podobné vlastnosti s uživatelovým nastavením. Dále nastává problém pro nově příchozí uživatele, kteří musí ohodnotit dostatečné množství položek, než bude generované kvalitní doporučení. Případně musí specifikovat svoje zájmy.
15
3.1.3
Filtrování založené na znalostech (Knowledge-based)
Tento přístup je zcela odlišný od předchozích. Pro doporučování využívá znalostí o položkách a uživatelích. Předchozí přístupy se hodí spíše na doporučování knih a filmů, kdežto tento přístup je vhodný tehdy, pokud není možné získat dostatek hodnocení o doporučované položce (např. prodej bytů). Filtrování založené na znalostech netrpí žádným z problémů předchozích přístupů, jelikož pro doporučení nepotřebuje žádná hodnocení. Samotný proces filtrování probíhá individuálně pro každého uživatele zvlášť (nezávisle na ostatních) na základě jeho specifikace. Jak uvádí zdroje [2] a [14], pro filtrování (doporučování) existují dva základní přístupy. Prvním přístupem je doporučování na základě omezení a druhým na základě požadavků. Oba přístupy si jsou podobné s tím, že uživatel musí specifikovat svoje požadavky. Hlavním rozdílem metod je styl doporučení. Doporučení na základě omezení využívá předem stanovených pravidel, která definují, jak se chovat vzhledem k danému zákazníkovi, kdežto doporučení na základě požadavků hledá co nejpodobnější položky k uživatelovým požadavkům. •
Doporučení na základě požadavků – doporučování probíhá na základě podobnosti položek. V praxi existují proměnné, které chce uživatel maximalizovat (např. velikost pevného disku), a naproti tomu proměnné, které chce minimalizovat (např. cena). Tyto proměnné musíme brát v potaz a pro výpočet podobnosti , mezi atributem položky p a požadavky uživatele r, kdy uživatel chce danou položku maximalizovat, vypadá výpočet následovně: ,
=
!" max
− min − min
max max
− !" − min
kde !" vyjadřuje pro každý atribut položky jeho vzdálenost od požadavků zákazníka. Poté pro minimalizaci: ,
=
V některých případech je však vhodné založit podobnost na vzdálenosti argumentů od sebe, například pokud chce uživatel určitou velikost disku. Podobnost pak spočítáme podle tohoto vzorce: ,
•
=
|!" − | max − min
Doporučení na základě omezení – tento doporučovací systém bývá definován pěti množinami proměnných, které popisují zákazníkovy požadavky, vlastnosti produktu a omezení, které definuje, jaké položky by měly být doporučeny s ohledem na situaci. Jedná se tedy o množinu () , (*+,- , .+ , ./ , .*+,- ). Pro příklad si uvedeme případ koupě fotoaparátu.
16
o
Uživatelovi požadavky () – obsahuje požadavky zadané uživatelem, tedy požadavky na daný produkt (fotoaparát: maximální rozlišení, cena,…).
o
Vlastnosti produktu (*+,- – popisuje konkrétní vlastnosti produktu (fotoaparát: velikost displeje, rozlišení,…).
o
Omezení .+ – definuje jednotlivá pravidla omezení pro uživatelovy vlastnosti (fotoaparát: pokud zoom > 20x, potom cena musí být vyšší než 10 000Kč).
o
o
Filtrovací podmínky ./ – definuje podmínky, za jakých by měly být vybrané produkty – definuje vztah mezi uživatelovými požadavky a vlastnostmi produktu (fotoaparát: velkoplošné snímky vyžadují rozlišení větší než 5Mpis). Omezení produktu .*+,- – definuje současně dostupné produkty.
V případě, že známe všechny tyto proměnné, samotné doporučení je už velice jednoduché. Systém buď daný produkt najde, anebo ne.
3.1.4
Hybridní přístup (Hybrid approach)
Žádná technika přístupu doporučování není bezchybná a pro různé stavy má různé slabiny. Tyto slabiny ji pak znevýhodňují vůči ostatním přístupům. Hybridní přístup se snaží kombinovat dvě nebo více doporučovacích technik. Chce tím vylepšit výkonnost jednotlivých přístupů uvedených výše. Většinou se jedná o techniku zkombinování kolaborativního filtrování s nějakou další technikou a předejití problémům s novými položkami nebo uživateli.[2] Některé kombinace metod hybridního přístupu zpracované dle [5] jsou: •
Weighted – skóre z několika doporučovacích technik je spojeno do jednoho. Nejjednodušší možností je použít lineární kombinaci všech výsledků, ale občas je vhodnější dát některým výsledkům rozdílnou váhu. Výhodou tohoto systému je jeho jednoduchost nasazení a jeho potenciál využití všech technik k vygenerování doporučení. Problémem může být, že ne všechny techniky doporučování jsou si ve všech situacích rovny, neboť kolaborativní filtrování bude mít slabší váhu při doporučování položek s malým počtem hodnocení, ale v tomto přístupu se často vyhodnotí ekvivalentně.
•
Switching - systém přepíná mezi technikami doporučování v závislosti na aktuální situaci. Například v případě, že první přístup nedokáže udělat dostatečně věrohodné doporučení, použije se druhý. Často se používá kolaborativní filtrování a filtrování podle obsahu, i když neřeší problém s novými uživateli. Výsledkem kolaborativního filtrování může být nečekaný výsledek, který by se podle podobnosti položek určitě neobjevil. Nevýhodou je, že druhá technika se použije jen tehdy, když první selže. Navíc je tento přístup složitější, protože musíme definovat přepínací kritéria.
•
Mixed – doporučení od více doporučovacích technik je prezentováno dohromady. V případě, že použijeme současně kolaborativní filtrování a filtrování podle obsahu, vyhneme se problému nové položky, protože druhá technika se o to postará. Ale 17
s problémem nového uživatele se ani toto spojní nevypořádá, protože obě techniky potřebují informace o chování uživatele. •
Feature combination - doporučení z více technik je vloženo do jedné, jedná se tedy o etapový proces. Při použití kolobarativního filtrování a využití jeho výsledků v technice filtrování podle obsahu se nám významně zvýší kvalita doporučení. Tato modifikace je velice atraktivní, jelikož umožňuje zlepšení výkonu systému bez potřeby velké modifikace.
•
Cascade - postupné zpřesňování výsledků předáváním výsledků po kaskádě. Jde o etapový proces. Jedna technika se používá na hledání množiny kandidátů a druhá z této množiny vybírá konečné doporučení. Rozdílem oproti předchozí technice je způsob zpracování výsledků od předchozího stupně. V této technice se nevyužívá hodnocení předchozího stupně (techniky), ale všechny položky vybrané ve množině bere jako ekvivalentní.
•
3.2
Featurea ugmentation – jedna technika se použije k hodnocení nebo klasifikaci položek a její výstup se použije jako vstupní prvek do jiné doporučovací techniky.
Nejznámější doporučovací systémy
V současné době existuje mnoho odvětví, kde se vyskytují doporučovací systémy. Za jeden z nejznámějších a nejstarších doporučovacích systému můžeme považovat internetový obchod Amazon2. Tento obchod začal vznikat v roce 1994 a za rok byl uveden na trh. Jeho zakladatelem byl Jeff Bezos, který se již při jeho zakládání věnoval především požadavkům zákazníků. Sám Bezos pronesl na téma úspěšnosti Amazonu několik citátu, nejznámějším je níže uvedený. „Máme 6.2 miliónů uživatelů; měli bychom mít 6.2 miliónů obchodů. Měli bychom tedy mít optimální obchod pro každého uživatele.“ – Jeff Bezos, CEO of Amazon.com.[4] Na základě tohoto citátu lze říci, že snahou bylo vytvořit pro každého zákazníka specifický obchod, který by mu nabízel produkty, o které by mohl mít zájem. Dá se říci, že toto se mu povedlo, díky doporučování založeném na podobnosti položek (Item-based collaborative filtering), kdy algoritmus na této stránce nejdříve přiřadí uživatelovým nákupům a hodnocením podobné položky a poté zkombinuje tyto podobné položky do listu doporučení. Aby autoři dosáhli vysokého výkonu, rozdělili doporučování do dvou komponent. V režimu offline se vytvoří matice podobností položek, která je velmi časově náročná na zpracování, a potom se už v režimu online jen prohledává a produkují se doporučení. Dalším známým doporučovacím systémem je služba Netflix, která doporučuje filmy. Bohužel v naší zemi není momentálně dostupná. Mezi důležité odvětví doporučovacích systémů patří sociální sítě Facebook, MySpace a další, které využívají především kolaborativní filtrování pro doporučování nových přátel, skupin a dalších sociálních spojení. V současnosti je však doporučovací systém 2
http://www.amazon.com
18
zaměřen spíše na cílené doporučování reklam, čehož využívají reklamní společnosti a sbírají data o uživatelích. Posledními, asi všeobecně známými doporučovacími systémy, jsou webové aplikace Youtube3 a Last.fm4. Ty od počátku svojí existence doporučují jednotlivé video klipy nebo písničky na základě kolaborativního filtrování.
3.3
Testovací metriky
Následující odstavec je zpracován podle [8][23]. Testovací metriky slouží k ohodnocení kvality doporučujícího systému. Můžeme je především rozdělit do dvou tříd: • Prediktivní metriky (Predictive accuracy metrics) – vyhodnocení přesnosti probíhá na základě porovnání doporučujícího skóre s uživatelovým hodnocením v testovací množině dat. Do této kategorie patří metody MAE (Mean Absolute Error), RMSE (Root Mean Squared Error). •
Klasifikační metriky (Clasificationt accuracy metrics) – vyhodnotí efektivnost predikce pro výběr vysoce hodnocených položek uživatelem ze všech dostupných položek. Tyto metriky berou proces jako binární operace – buď jsou položky předpokládané (dobré), anebo ne (špatné). Z tohoto hlediska zcela ignorují hodnocení položky nebo její pozici. Pouze vyhodnotí, zda je položka klasifikována jako dobrá nebo špatná. Do této kategorie mezi nejčastěji používané metriky patří přesnost a úplnost (Precision and recall), obrácená míra (Reversal rate), vážené chyby (Weighted errors) a ROC citlivost (ROC sensitivity).
MAE (Mean Absolute Error) Tato metrika je definována [8] jako průměr absolutního rozdílu mezi očekávaným hodnocením a aktuálním hodnocení, která má následující tvar: 012
∑3 , 4|5 , − 6
Kde 5 , je odhad hodnocení pro uživatele u položky i a hodnocení v testovací sadě.
,
|
,
je aktuální hodnocení. N je celkový počet
RMSE (Root Mean Squared Error) Obdobně jako MAE [8], ale s kladením většího důrazu na velikost absolutní chyby, je dána vztahem: ∑3 , 4 5 , − 012 = 7 6
Kde 5 , je odhad hodnocení pro uživatele u položky i a hodnocení v testovací sadě.
3 4
,
,
je aktuální hodnocení. N je celkový počet
http://www.youtube.com http://www.last.fm
19
Přesnost a úplnost Přesnost a úplnost (precision and recall) jsou pojmy používané v oblasti vyhledávání informací a doporučování. Hledáme-li například na webu nějaké dokumenty týkající se určitého tématu, pak podle [1] nastávají dvě situace: • •
Ne všechny nalezené dokumenty se týkají tématu, které jsme hledali. Určitě jsme nenalezli vše, co je o tématu k dispozici.
To samé platí o doporučování, kdy se snažíme doporučit nějaké produkty, které by se uživateli mohli líbit. Zde nastávají situace obdobné: • •
Ne všechny doporučené produkty jsou správné. Určitě v množině doporučených produktů nejsou všechny, které lze doporučit.
Pro definici samotné přesnosti a úplnosti si musíme ještě říci, co je to matice záměn. Matice záměn slouží pro zobrazení počtu správně a špatně klasifikovaných objektů. V jednotlivých sloupcích jsou uvedeny informace o tom, jak postupoval při klasifikaci systém využívající dostupná data. V řádcích jsou pak informace o tom, jak by to mělo správně být. Níže uvedená tabulka, která zachycuje klasifikaci do dvou tříd, do kladné (+) a záporné (-) zobrazuje, jaké mohou nastat situace při klasifikaci. Klasifikace systému Správné zařazení + -
Konkrétně při klasifikaci mohou nastat čtyři situace: • • • •
TP (true positive) – udává počet případů, kdy systém správně zařadil objekt do třídy +. TN (true negative) – udává počet případů, kdy systém správně zařadil objekty do třídy -. FP (flase positive) – udává počet případů, kdy systém chybně zařadil objekty do třídy +. FN (false negative) – udává počet případů, kdy systém nesprávně zařadil objekty do třidy -.
Jednotlivé tyto situace jsou reprezentovány počtem odpovídajících objektů, které byly do příslušných kategorii zařazeny. V řadě případů může být důležitý i typ chyby, kterého se systém dopustil. Jedná se tedy o falešně pozitivní chybu a falešně negativní chybu. Falešně pozitivní chyba bývá označována jako chyba prvního druha a její míru můžeme vyjádřit pomocí vztahu 859
/*
:;
negativní chyba bývá označována jako chyba druhého druhu a její míra je 859
/;
:*
je však velice důležité rozlišovat, jelikož každé může mít jiné následky. Například, pokud by systém hodnotil bonitu klientů banky za účelem rozhodnutí o úvěru, dopustil by se chyby, tak nastane situace, že doporučí půjčku klientovi, který jí nesplatí, nebo situace, že zamítne půjčku klientovi, 20
který by ji splatil. Pro banku to jsou dvě zcela odlišené situaci, kdy v prvním případě by banka prodělala a ve druhém by nevydělala. Z hlediska banky je první chyba o hodně závažnější.[1] Na základě výše popsaných situací si již můžeme definovat samotou přesnost a úplnost, které vychází z matice záměn. S ohledem na uvedení příkladu o vyhledávání dokumentů na webu nám přesnost říká, kolik nalezených dokumentů se skutečně týká daného tématu a úplnost, kolik dokumentů týkajících se tématu jsme nalezli. Přesnost a úplnost jsou definovány podle [1] následovně: 5ř >? @ Ú C>? @
A5 A5 85
A5 A5 86
Na základě přesnosti a úplnosti pak můžeme definovat F-míru (F-measure), která zobrazuje tzv. harmonický průběh přesnosti a úplnosti. Zapsat ji lze podle [1] pomocí následujícího vzorce: 8
Jednotlivé techniky doporučování trpí na různé problémy, které mohou nastat. Většinou jde o problémy vycházející ze specifikace konkrétní techniky, ale i o úmyslné ovlivnění. Největším problémem je však tzv. „studený start“(Cold start)[2]. Jde o potenciální problém počítačových informačních systémů, které zahrnují určitou míru automatizace modelování dat. Konkrétně se jedná o problém, kdy systém nemůže čerpat žádné důsledky pro položky nebo uživatele, o kterých doposud neshromáždil dostatečné informace. Nejvíce na tento problém trpí kolaborativní filtrování. Řešením problému je nasazení hybridních technik přístupu. Dále mezi nejznámější problémy patří:
Problém nových uživatelů a položek Problém nových položek je obdoba „studeného startu“, který se objevuje v kolaborativním přístupu, kde položka nemůže být doporučena, dokud ji nějaký uživatel neohodnotí. Tento problém se však vyskytuje i u položek, které nejsou příliš hodnocené a tím jsou neznámé. Řešením je využití filtrování podle obsahu, které dokáže takovéto objekty zpracovat. S problémem nových uživatelů je to však složitější, jelikož bez předchozích akcí uživatele je nemožné nalézt podobné uživatele anebo položky, které by se uživateli líbily. Řešením je donucení uživatele zvolit svoje preference, na základě kterých ho můžeme ohodnotit.[8]
Problém řídkosti V praxi je mnoho komerčních doporučovacích systémů založených na velkých datových souborech. V důsledku toho, může být hodnotící matice příliš velká a řídká, protože je těžké najít množinu uživatelů s podobným hodnocením. Tento problém se nejčastěji vyskytuje u nových systémů, kde jde o tzv. studený start (Cold start). Řešením tohoto problému je nasazení hybridních technik, kde se využívají i jiné metody.[8]
21
Podvody Kolaborativní filtrování je velice citlivé na informace od uživatelů a z tohoto důvodu velice náchylné na podvodné útoky. Ve virtuálním světě by tato technika fungovala velice dobře, kdežto v reálném musíme vzít v potaz, že zainteresovaný uživatel může doporučovací systém ovlivnit a tím ovlivnit celé doporučování. Nejčastějším útokem bývá tzv. profilová injekce, která se skládá z množiny podvodných profilů a cílových položek, u kterých útočník sníží nebo zvýší hodnocení. Tímto způsobem je schopen útočník aktivně ovlivnit celý systém doporučování.
Grey/Black Sheep Za „šedé ovce“ (Gray Sheep) jsou považováni uživatelé, jejichž názor není konzistentní s žádnou jinou skupinou uživatelů, tedy pro ně kolaborativní filtrování není efektivní. Za „černé ovce“ (Black Sheep) jsou považováni uživatelé, jejichž výstřední vkus znemožňuje generování kvalitních doporučení. Jelikož jsou tyto extrémní případy problémem i pro běžné doporučovací způsoby, jsou považovány za akceptovatelnou chybu.[9]
22
4
Návrh aplikace
Webových stránek restaurací, které nabízejí svoje denní menu, je v současnosti mnoho. Důvodů, proč se jejich počet stále zvyšuje, je hned několik. Náklady na pořízení takovéto stránky nejsou příliš vysoké a potenciální zisk je při minimálních nákladech velice slušný. Pro uživatele, který navštěvuje více stravovacích podniků, nastává však problém, že si musí pročítat jednotlivé jídelní lístky na konkrétních webových stránkách a tím přichází o drahocenný čas. Na základě tohoto faktu a dohody s vedoucím práce, byla vybrána jako aplikační oblast doporučování jídel. Jde o oblast poměrně podobnou internetovým obchodům, jen s tím rozdílem, že u doporučování jídel se jednotlivé položky každý den mění, což mění celý základní přístup k doporučování, neboť máme neustále nové položky. V této kapitole se budeme věnovat návrhu jednotlivých částí aplikace. Jak plyne z níže uvedeného obrázku 9, zobrazujícího abstraktní pohled na projekt, bude třeba rozebrat návrh několika různých částí, z nichž každá je v něčem specifická.
Internet
Doporučovací systém
Parser
DB Webová aplikace Feedback Sběr dat
Obrázek 9: Abstraktní pohled na jednotlivé části aplikace
Zdrojem dat, která budou použita pro doporučování, jsou jednotlivé jídelní lístky restaurací, které poskytují RSS kanál, který bude pomocí webové služby parserem zpracováván. Jednotlivé položky pak budou uloženy do databáze, z které bude čerpat doporučovací systém.
4.1
Návrh sběru dat
Důležitou podmínkou při sběru dat je, aby ho mohl uživatel ovlivnit. To znamená, že uživatel by měl mít možnost jednotlivé restaurace a jídla hodnotit, aby ovlivnil doporučování. Hodnocení se dá řešit pomocí známého tlačítka „like“ a „dislike“ nebo pomocí hvězdiček (5 je více než 1). Na základě hodnocení pomocí hvězdiček lze však dosáhnou přesnější zpětné vazby (feedback). Tato tlačítka a hvězdičky musí být vhodně umístěny, aby se zajistilo, že uživatel projeví zpětnou vazbu. To je pro nás velmi důležité, protože to má vliv na kvalitu doporučování.
23
4.1.1
Možnosti získání dat
Jednou z možností získání dat je dát uživateli možnost hodnotit jednotlivé restaurace a jednotlivá jídla. Při hodnocení konkrétního jídla se hodnocení promítne do kategorií, do kterých spadá. Tím pádem dojde k ovlivnění při výběru kategorií. Další možností je donutit uživatele vyplnit preference, které preferuje, a systém pak na základě analýzy těchto preferencí doporučí konkrétní jídlo. Je tedy mnoho způsobů, jak sbírat data od uživatele. Druhou možností je strojové učení na základě chování uživatele neboli implicitní feedback. V tomto případě není potřeba žádná interakce s uživatelem. Lze shromažďovat informace o vyhledávaných položkách a jednotlivých akcích uživatele. Na základě těchto informací můžeme nalézt nejbližší sousedy s podobným chováním a předpovědět správné doporučení.
4.2
Návrh webové aplikace
Důležitou částí návrhu webové aplikace je návrh uživatelského rozhraní. Cílem je vytvořit uživatelsky příjemný a přehledný vzhled, který uživatele zaujme, nebude se v něm ztrácet a rád se na stránky vrátí. Této části však předchází analýza všech možných interakcí systému s uživatelem. Co by tedy měl systém umět: • Měl by zajistit přehledné zobrazení. • Zajistit kvalitní doporučení. • Poskytovat hodnocení nabídek a restaurací. • Umožnit vyhledávání v nabídkách. • Zobrazit dané kategorie. • Umožnit nastavení oblíbené restaurace. • Zobrazovat informace o restauracích. • Zobrazovat top restaurace a nabídky. • Poskytovat nápovědu. Z výše uvedených uživatelských interakcí se systémem vytvoříme pokud možno atomické požadavky. Tedy: • Zobraz domovskou stránku. • Vyhledej nabídku. • Zobraz detaily o nabídce. • Filtruj nabídky podle kategorií. • Zobraz nejlépe hodnocené restaurace. • Zobraz nejlépe hodnocené nabídky. • Zobraz nastavení. • Ohodnoť nabídku, restauraci. • Zobraz nápovědu. Po specifikaci požadavků na uživatelské rozhraní se nyní budeme věnovat vytvoření prototypu uživatelského rozhraní. Tento prototyp nazývaný Lo-Fi prototyp je velice důležitý. Je to úplně základní představa o tom, jaké budou vztahy mezi jednotlivými stránkami. Slouží jako podklad, který definuje strukturu každé stránky, její obsah i funkčnost. Tyto prototypy předcházejí grafickým
24
návrhům, přičemž jsou většinou kresleny pouze tužkou na papír jako černobílé kresby. Výhodou těchto prototypů je možnost cokoliv změnit s vynaložením minimálního úsilí. Prototypy je možné vytvářet buď „odshora“, nejdříve se zaměřit na rozmístění komponent a až poté na jejich detail. Nebo „odzdola“, nejprve navrhnout detail komponent a poté se zaměřit na jejich rozmístění. Nejlepší je kombinace obou těchto přístupů, lehce si rozmyslet vzhled komponent i jejich rozmístění, poté navrhnout samotné rozmístění a případně komponenty upravit.[9] Při kreslení těchto prototypů došlo k několika iteracím, které postupně upravovaly rozmístění jednotlivých částí. Mezi nejzajímavější patří prototyp domovské stránky – viz Obrázek 10.
Obrázek 10: Lo-Fi prototyp domovské stránky
Samotná stránka byla rozdělena na několik části, kde každá je v něčem specifická. První částí je hlavička, kde bude zobrazené logo a základní menu poskytující přístup do nastavení a odhlášení ze systému. Další část se nachází pod hlavičkou, jsou v ní umístěny dvě komponenty. Jedná se o formulář pro vyhledávání a menu složené z jednotlivých kategorií. Tuto část bylo nutné umístit na střed, aby byla uživateli vždy na očích. Největší částí je samotný obsah, který je rozdělen do dvou sloupců. V pravém sloupci se bude nacházet mapa s uživatelovými restauracemi a dále jednotlivé restaurace, které by ho mohli zaujmout. Levý sloupec bude zobrazovat již jednotlivá jídla a poskytovat základní informace. Celý tento koncept rozmístění komponent je založen na současném trendu vývoje webových aplikací, aby koncový uživatel nebyl zmaten, při hledání typických ovládacích prvků. Na základě tohoto prototypu byl vytvořen grafický návrh, ze kterého budou dále vycházet jednotlivé podsekce webu. Tento návrh se bude ještě dále v průběhu vývoje aplikace optimalizovat za účelem lepší prezentace a intuitivnosti pro uživatele. Samotný grafický návrh je zobrazen na Obrázek 11.
25
Obrázek 11: Grafický návrh
Jak již bylo řečeno, grafický návrh na obrázku 11 vychází z Lo-FI prototypu zobrazeném na obrázku 10. Snaží se ho plně implementovat a dodržet původní rozvržení komponent a obohacuje ho o grafickou část. Takto připravený návrh můžeme již využít pro vlastní vytvoření webové stránky s tím, že ho nařežeme a nastylujeme.
4.3
Návrh parseru RSS kanálu
Primárním účelem parseru bude získávání dat pro potřeby webové aplikace. Tyto data bude získávat z RSS kanálů jednotlivých restaurací, které zpracuje a následně je uloží do databáze. Jelikož všechny restaurace nemají RSS kanál a navíc každá by mohla mít jiný formát, bude jako zdroj RSS kanálu využita webová stránka lunchtime,5 která poskytuje pro každou restauraci RSS kanál. Díky tomuto zdroji dat lze předpokládat, že rozhraní jednotlivých kanálů bude jednotné, a tak i samotné přidávání dalších restaurací bude jednoduché. Bude stačit pouze přidat potřebný záznam do databáze. Samotný proces zpracování každého kanálu bude spočívat v jeho načtení, analyzování, zda obsahuje položky, které hledáme a pak teprve zpracování. Zpracování znamená, že vyčte jednotlivá menu s cenou pro 5
http://www.lunchtime.cz
26
požadovaný den, zařadí je do kategorií a vše uloží do databáze. Tento proces se bude opakovat pro všechny uložené restaurace. V případě, že se nepodaří něco správně načíst, nastaví se příznak, aby se operace opakovala. Do funkčních požadavků na parser lze zařadit automatickou kontrolu RSS kanálu. Jelikož parser bude implementován jako webová služba, která se bude automaticky spouštět v předem definovaných intervalech za účelem získání aktuálních dat. Tyto intervaly se upřesní na základě analýzy frekvence změny RSS kanálů. Dalším požadavkem je automatické zařazování jídel do předem definovaných kategorií. Jednotlivá data získaná z RSS kanálů totiž kategorie neobsahují, a tak je nutné provést jejich mapování. V případě, že se nepovede jídlo nikam zařadit, zařadíme ho do neznámé kategorie, aby se dalo později ručně namapovat. Možné problémy Mezi možné problémy lze zařadit mnoho nečekaných událostí, které mohou nastat: • • • •
Nedostupnost RSS kanálu, výpadek webové služby, nevalidní data v RSS kanálu, nové elementy.
Je však důležité, aby se z kterékoliv z těchto událostí dokázal parser zotavit a pokračovat dál ve zpracovávání zbývajících dat. Pokud zpracování dat nebude možné, tak alespoň ve zpracování zbývajících RSS kanálů. Další problém může nastat v případě, že se objeví nové jídlo, které nelze zařadit do žádné z předem definovaných kategorii. Takovéto jídlo bude zařazeno do neznámé kategorie a administrátor bude informován o nových datech. Ten pak bude muset ručně upravit mapovací funkci, zařazující jednotlivá menu do kategorií, aby problém znovu nenastal.
4.4
Návrh doporučování
Cílem bylo navrhnout inteligentní algoritmus doporučování, který bude doporučovat v jakékoliv situaci, bez ohledu na to, zda už máme dostatek dat od uživatelů, kteří navštívili systém. S ohledem na zvolenou aplikační oblast, týkající se doporučování jídel, lze předpokládat, že těchto dat mnoho nebude, protože je těžké uživatele donutit o explicitní feedback. Po podrobnější analýze cílové aplikační oblasti bylo zjištěno, že nelze využít klasické doporučovací metody používané v internetových obchodech. Z důvodu, že tento doporučující systém bude zobrazovat všechny dostupné nabídky menu pro daného uživatele, seřazené v určitém pořadí. Ne tedy, jak tomu bývá v internetových obchodech, kdy se snažíme doporučit uživateli určité zboží na základě analýzy jeho chování. Navíc zde nastává problém s každodenní obměnou položek, které se budou doporučovat. To znamená, že se v systému nachází každý den mnoho nových položek, které nikdo nehodnotil. S tímto problémem souvisí již zmiňovaný problém s hodnocením, protože málokterý uživatel se podívá na menu, dojde se najíst a projeví zpětnou vazbu formou hodnocení. Proto se nelze spolehnout pouze na tyto znalosti, ale je nutné problém řešit jinak.
27
Řešením je změna pohledu na jednotlivá data, která budou doporučována. Z pohledu doporučujícího systému nás nebude zajímat konkrétní položka, ale budou nás zajímat kategorie a restaurace, do které spadá. To znamená, že v případě ohodnocení dané položky se toto hodnocení promítne do jednotlivých kategorií a restaurace. Nastává zde však ještě problém s novými uživateli. Tento problém je nazýván také jako Cold start. Jde o to, že může nastat situace, kdy o uživateli nebudeme mít žádný záznam o jeho chování, přestože nějaký potřebujeme. K tomuto účelu bude uživateli poskytnuta možnost specifikovat jednotlivé preference kategorií, na základě kterých bude vytvořen počáteční model doporučování. To přinese uživatelovi možnost aktivně ovlivňovat výsledky doporučování. Samotný výpočet podobnosti mezi jednotlivými položkami a uživatelovým modelem bude založen na kosinově podobnosti vektorů, přičemž jednotlivé složky vektorů budou odpovídat jednotlivým kategoriím a restauraci, do které spadají. Poté výpočet kosinové podobnosti mezi vektorem A a vektorem B, kdy každý vektor reprezentuje jednu položku, lze realizovat pomocí následujícího vzorce: cos I
1 . K ‖1‖‖K‖
∑MNO 1 ∗ K
∑MNO 1
∗ ∑MNO K
Výhodou tohoto přístupu k výpočtu je možnost jednotlivé vektory násobit váhovým vektorem, kterým lze ovlivnit výslednou podobnost. Tento váhový vektor bude odpovídat uživatelovým preferencím, díky kterým bude možno spočítat doporučení i pro nově příchozí uživatele. Výsledná podobnost položky, s uživatelovým modelem, který bude reprezentován pomocí hodnocených položek a preferencí, bude získána jako průměr jednotlivých podobností položky s každou hodnocenou položkou. V případě neexistence hodnocených položek pouze jako podobnost s preferencemi. Výsledkem tohoto výpočtu pro všechny položky a uživatele bude tabulka podobností, která bude vypočítána v režimu offline z důvodu časové náročnosti. Poté již samotný výběr položek pro doporučení bude velice rychlý, protože bude stačit seřadit jednotlivé položky podle dosažené podobnosti a zobrazit je. Výsledný návrh doporučovacího systému, na jisté úrovni abstrakce pak zobrazuje obrázek 12, kde vidíme jednotlivé vztahy mezi uživatelem a doporučovacím systémem.
Preference Hodnocení Doporučení
Doporučovací systém
Obrázek 12: Doporučovací systém na vyšší abstraktní úrovni.
28
4.5
Neformální specifikace požadavků
V této části se zaměříme na neformální specifikaci databáze, na základě které bude možné vytvořit výsledné schéma databáze. Webová aplikace bude zobrazovat jednotlivé položky menu restaurací, které má aktuálně přihlášený uživatel přidané mezi oblíbenými. U každé položky bude zobrazen její název, restaurace, do které patří, cena, hodnocení a čas, kdy má restaurace otevřeno. Dále bude možno zobrazit detail o restauraci, který poskytne informace o kontaktu. Jednotlivé položky budou seřazeny na základě výsledku doporučovací funkce, která bude specifická pro každého uživatele. Tato funkce předpočítá data a uloží si k jednotlivým položkám menu informace o získaném skóre. Pro potřeby výpočtu této funkce bude nutné uchovávat historii jednotlivých hodnocení daného uživatele. Každé menu je zařazeno do jedné či více kategorii, přičemž každý uživatel si může ke každé kategorii nastavit jednotlivé preference. V případě hodnocení konkrétního menu se hodnota hodnocení promítne i do restaurace, ke které patří. Současně se ovlivní i hodnocení jednotlivých kategorii daného uživatele. Dále bude nutné zajistit, aby uživatel mohl hodnotit dané menu pouze jednou. Pro potřeby zobrazení restaurací na mapě bude nutné nadále uchovávat informace o jejích souřadnicích.
29
5
Implementace
Cílem této kapitoly je popsat implementaci aplikace a jejích součástí podle návrhu uvedeného v kapitole 4. V první části si popíšeme jednotlivé technologie použité pro implementaci a poté se zaměříme na samotnou strukturu aplikace. Jen pro připomenutí, úkolem této práce bylo vytvořit webovou aplikaci a v ní implementovat navržený doporučovací systém.
5.1
Použité technologie
Pro implementaci webové aplikace a samotného systému doporučování byly zvoleny technologie od firmy Microsoft. Konkrétně celá aplikace byla napsána v programovacím jazyku C# s využitím technologie ASP.NET 4.0. Dále byl využit MS SQL server 2008 R2, který se staral o data. Samotný vývoj aplikace probíhal ve vývojovém prostředí Microsoft Visual Studio 2012, které je poskytováno studentům FIT VUT zdarma v rámci programu MSDN AA6. Jedná se o vývojové prostředí, které může být použito pro vývoj nejrůznějších typů aplikací. Od aplikací určených pro mikro čipy, přes konzolové a desktopové aplikace až po nejrůznější webové. Visual Studio obsahuje editor kódu podporující IntelliSense a refaktorování. Integrovaný debugger pracující na úrovni kódu, tak i na úrovni stroje. Dále obsahuje spoustu vestavěných nástrojů pomáhajících při tvorbě aplikace (návrhář formulářů, databázových schémat,…). Samotné Visual Studio je založené na službách, kde každé rozšíření funkčnosti je zabaleno do balíčku VSPackage, a poté nainstalováno a dostupné jako služba. To umožňuje podporu jakéhokoliv programovacího jazyka, kdy stačí nainstalovat potřebnou jazykovou službu. Mezi základní vestavěné jazykové služby patří především C/C++, VB.NET a C#. Ostatní lze tedy jednoduše doinstalovat.
Obrázek 13: Architektura Visual Studio 2012 převzato z [18]
Architektruva Visual Studia zobrazená na Obrázku 13 poskytuje v základu tři služby, které se starají o jeho běh. Jedná se o SVsSolution, která umožňuje číslovat projekty a sestavy. SVsUIShell, který poskytuje rozdělování na okna a UI funkce. Poslední je SVsShell, který se stará o registraci 6
MSDN AA – jedná se o program zaměřený na podporu vývoje na a pro produkty společnosti Microsoft
30
balíčků VSPackage. Z toho tedy vyplývá, že všechny součásti Visual Studia jsou implementované jako balíčky. Pro přístup k jednotlivým balíčkům je používán Component Object Model (COM – jedná se o platformově nezávislý, distribuovaný, objektově orientovaný systém pro vytváření binárních softwarových komponent, které jsou schopny spolupracovat), který umožňuje, že jednotlivé balíčky mohou být psány v jazycích .NET. [18]
5.1.1
Asp.Net
Proč jsem zvolil pro vývoj technologii ASP.NET? Na začátku jsem přemýšlel mezi dvěma technologiemi. Mezi ASP.NET od Microsoftu a JavaServerFaces (JSF) od Sunu. Po uvážení všech pro a proti po předešlých zkušenost s vývojem na jednotlivých platformách padla volba na ASP.NET. Bylo tomu proto, že Java poskytuje pro objektově relační mapování framework Hibernate, který nemám rád a nemám s ním takové zkušenosti jako s konkurencí Microsoft a jeho Entity Frameworkem. Nadále upřednostňuji vyvíjení aplikací ve Visual Studiu a tak volba byla jasná. Technologie ASP.NET vychází ze starší technologie ASP, ale je postavená nad .NET Frameworkem a tím se odlišuje. Díky .NET Frameworku jsou ve všech aplikacích ASP.NET dostupné jeho funkce a navíc cílové aplikace můžeme psát v libovolném jazyce, který je kompatibilní s modulem CLR (Common Language Runtime).To je pro programátory velice přínosné. Strukturu architektury zachycuje obrázek 14, kde jsou zobrazeny jednotlivé vazby mezi komponentami.
Obrázek 14: ASP.NET architektura, převzato z [20]
Samotná technologie ASP.NET je založená na architektuře klient-server. Výstupem je tedy aplikace, jejíž výstup je HTML stránka. Jedná se tedy o dynamický web, který na základě požadavků vygeneruje webovou stránku a pošle ji klientovi. Tyto aplikace jsou velice rychlé, jelikož jsou předkompilované do jednoho či několika málo DLL souborů, na rozdíl od ryze skriptovacích jazyků, kde jsou stránky při každém přístupu znovu a znovu pársovány. Samotný proces kompilace je zobrazen na Obrázku 15. Proces je prováděn v několika krocích. Nejprve dojde ke kompilaci do mezi jazyka MSIL (Microsoft Intermediate Language), který je uznáván v rámci CLR a poté při první žádosti na požadovanou stránku dojde k převedení do nativního kódu JIT (Just in Time) kompilátorem. Ten se poté uloží do mezipaměti a tím jsou další požadavky na tutéž stránku velmi efektivní. Toto si již řeší sám IIS (Internet Information Service), kde ASP.NET aplikace běží. V současné době existuje několik verzí IIS serverů a .NET frameworků a ne všechny vlastnosti jsou
31
kompatibilní. Proto v případě, kdy nemáme vlastní server, je vhodné si ověřit, jestli firmy poskytující jednotlivé hostingy podporují námi zvolenou verzi, a tím pak předejít různým problémům.
Obrázek 15: Kompilace ASP.NET stránky do MSIL kódu a poté do nativního, převzato z [19]
ASP.NET podporuje dvě koncepce tvorby aplikaci. Jednou je MVC a druhou WebForms. Zde si přiblížíme pouze WebForms z toho důvodu, že byly využity při tvorbě aplikace. WebForms je pokus přenést WinForms (standardní formulářové aplikace z desktopu) na web. Pointa spočívá v tom, že navenek se aplikace tváří a chová stejně jako desktopová, ale na pozadí je složitá logika. Problém nastává v tom, že událostmi řízené programování potřebuje zachování stavu, což přes bezestavový protokol HTTP je problém. ASP.NET tento problém řeší pomocí kombinace HTML a JavaScriptu. Prakticky se dá říci, že ASP.NET stránka je jeden velký formulář, který obsahuje skryté pole nazývané ViewState. Toto pole uchovává stav aplikace a v případě dotazu na server se odešle s ním. Server ho pak zpracuje a obnoví data. Tento proces obnovení se také nazývá životní cyklus stránky, který má přesně definované kroky. Jednotlivé kroky jsou zobrazeny na Obrázku 16.
Obrázek 16: Životní cyklus ASP.NET stránky, převzato z [20]
32
Výhodou tohoto přístupu je, že se aplikace navenek tváří jako desktopová, ale nevýhodou je větší velikost přenášených dat. Proto se s touto vlastností musí zacházet uváženě, aby její velikost nebyla natolik velká, až by aplikace byla prakticky nepoužitelná.
5.1.2
Entity Framework
Microsoft ADO.NET Entity Framework, dále jen EF, je objektově – relační mapovací Framework (ORM), který umožňuje vývojářům pracovat s jednotlivými relačními daty jako s objekty a eliminuje nutnost psaní kódu pro přístup k datům. Architektura tohoto systému je zobrazena na obrázku 17, kde vidíme přímou vazbu EF na ADO.NET. EF je objektově relační implementace, která poskytuje sadu technologií obsažené v ADO.NET sloužící pro tvorbu aplikací, které pracují s daty. Na rozdíl od ADO.NET, kde vývojář trávil mnoho času na úpravách kódu v případě změn databáze, EF poskytuje mapování z relačního schématu databáze na objekty a nabízí abstrakci ADO.NET na vyšší úrovni. V EF můžeme tedy definovat entity tříd, které jsou nezávislé na datové struktuře databáze, a poté je namapovat do tabulek v databázi. Protože nyní pracujeme s entitami, které mají své vlastní schéma, jsme zcela odstíněni od změn v databázi. EF vyplňuje mezeru mezi aplikací a databází. Na pozadí používá ADO.NET a nabízí přechod z databázově orientovaného na modelově orientovaný vývoj aplikace. To umožňuje vývojářům aplikace se zaměřit především na bussines logiku a nevěnovat čas řešením přístupu k datům. Jedná se o velice efektivní nástroj, který usnadňuje vývoj a budoucí správu aplikace.[21]
Obrázek 17: Entity Framework architektura, převzato z [21]
V EF můžeme realizovat také tři typy relací jako v relační databázi. Máme zde vazby typu 1:1, 1:N a M:N. Vazby 1:1 a 1:N jsou v EF realizovány stejně jako v běžné databázi, ale pokud se jedná o vazbu M:N neboli many-to-many jsou tu nepatrné rozdíly. Na Obrázku 18 vidíme relační schéma databáze s vyznačenými jednotlivými vazbami. Zaměříme-li se na tabulku Student a tabulku Course tak vidíme, že jsou ve vztahu M:N a tedy potřebují vazební tabulku StudentCourse. Pokud tuto databázi namapujeme pomocí EF a vytvoříme Entity Data Model (EDM), získáme model uvedený na Obrázku 19. Z modelu je patrné, že zde není uvedena vazební tabulka StudentCourse, přestože vazba 33
mezi Student a Course je označena jako M:N. EDM nereprezentuje vazební tabulky, které obsahují pouze primární klíče. To přináší výhodu automatická správa vazby. Pokud tedy přidáme studenta do kurzu a změnu uložíme, dojde k automatickému přidání záznamu do StudentCourse. Tento přístup je velice efektivní a přináší další výhody spojené s vyhledáváním, aktualizováním a mazáním záznamů. V případě, že by vazební tabulka měla jakýkoliv další sloupec, tak se již zobrazí a o všechny operace pramenící ze vztahu M:N se musíme postarat samy.
Obrázek 18: SQL schéma databáze – vazby, převzato z [22]
Obrázek 19: Entity Data Model–vazby, převzato z [22]
34
Pro přístup a změnu dat v databázi nabízí EF několik způsobů, kdy pomocí dotazování vrací objekty. Samotnou architekturu a způsoby přístupu zachycuje obrázek 20, kde jsou uvedeny tři způsoby:[20] •
LINQ to Entities – nejnovější součást technologie LINQ, která vytváří dotazy nad entitním modelem vytvořeným pomocí EF.
•
Entity SQL - jedná se o jazyk umožňující dotazy do konceptuálního modelu pomocí EF
•
Querybuildermethods – tyto metody umožňují vytvořit Entity SQL dotazy s využitím stylu LINQ dotazů.
Obrázek 20:Architektura pro přístup k datům, převzato z [21]
Za pozornost stojí přístup LINQ to Entities. Tento přístup využívá technologii LINQ (Language Integrated Query), která je integrovaným jazykem pro dotazování nad různými typy dat, usnadňuje jejich tvorbu, třídění, vyhledávání a jednotlivé propojování. Samotná klíčová slova dotazů jsou téměř totožná s těmi, které jsou používané v klasických SQL dotazech. Ať už se jedná o slova select, where nebo další. Rozdílem je však jejich umístění. Typickým rozdílem je umístění select na samotný konec dotazu. Dotaz pro získání všech jmen zákazníků, kteří utratili více než 500Kč by mohl vypadat následovně: var names = from z in ZakaznikEntities.zakaznik where z.utratil > 500 select z.jmeno Po provedení tohoto dotazu získáme kolekci všech jmen zákazníků, kteří utratili víc než 500Kč. Za slovem from se vyskytuje proměnná z, která reprezentuje jednotlivé objekty z tabulky zakaznik. Dále slovo in určuje, kde se tyto objekty nachází. Do takto zapsaného dotazu lze doplnit spousta dalších slov ovlivňujících výsledný select. Nespornou výhodou LINQ je podpora lambda výrazů (lambda expressions), který dokážou velice zpřehlednit a usnadnit samotný dotaz. Víše uvedený dotaz zapsaný s pomocí lambda výrazu by vypadal následovně:
35
var names = ZakaznikEntities.zakaznik.where(x=>x.utralil> 500).select(y=>y.jmeno) Pro vytvoření lambda výrazu musíme specifikovat vstupní parametry, které se uvádějí na levé straně operátoru => a umístit blok příkazu na druhou stranu.
5.2
Webová aplikace
Jak již bylo uvedeno, celá webová aplikace byla implementována pomocí technologie ASP.NET 4.0. Samotný vývoj aplikace byl rozdělen do několika fází, kdy se postupně vyvíjeli jednotlivé součásti potřebné pro správný chod aplikace. První fází vývoje bylo vytvoření návrhu schématu databáze. Samotný návrh databáze vycházel z předem definovaných požadavků na aplikaci rozebraných v kapitole 4. K tomuto účelu byla využita aplikace MS SQL Management Studio, která poskytuje příjemné interaktivní rozhraní. Výhodou tohoto studia je, že přímo při návrhu schématu a jeho následném uložení vytvoří konkrétní objekty v databázi, čímž nám odpadá starost o případné generování databáze z ER diagramu vytvořeného v jiném programu. Na začátku vývoje byl používán jako databázový server SQL 2008 Express. Jenže v průběhu vývoje s ním nastali problémy. Problémy byly spojeny s realizací fulltextového vyhledávání. Základní verze SLQ Express totiž nepodporuje fulltextové indexy potřebné pro vyhledávání. Proto bylo přistoupeno k přechodu na plnohodnotný server SQL Server 2008 R2, který již fulltextové indexy podporuje. Výsledné schéma databáze je z důvodu velikosti uvedeno v příloze 1. Další fází vývoje bylo založení webového projektu ASP.NET Web Forms Application, který slouží pro vývoj webových aplikací. Po vytvoření tohoto projektu se vytvoří základní adresářová struktura, jejíž součástí je soubor web.config. Tento soubor slouží pro konfigurační nastavení platná pro složku, ve které se nachází. V tomto případě pro celou aplikaci, jelikož se nachází v hlavním adresáři. Jedná se o XML dokument, který definuje chování aplikace. Do tohoto souboru budeme tedy přidávat jednotlivá nastavení potřebná pro správný chod aplikace. Prvním potřebným nastavením bylo připojení do databáze. Jedná se o přidání nového záznamu mezi párový element s potřebnými informacemi. Tento záznam je vždy nutné změnit s ohledem na to, kde výslednou aplikaci budeme spouštět, neboť připojení je vždy různé.
Na výše uvedeném příkladu vidíme použité nastavení pro připojení k databázi. Toto připojení využívá k autentizaci do databáze aktuálně přihlášeného uživatele pod Windows. V případě potřeby autentizace pomocí uživatelského jména a hesla je nutno přidat do atributu connectionString dva záznamy a to „user ID“ a „password“.
36
Za pomoci tohoto připojení k databázi byl s využitím Entity Frameworku vytvořen objektový model databáze. Došlo k vygenerování objektového modelu, který je mapován na relační uložený v databázi. K tomuto účelu byl využit nástroj Entity Designer, který umožňuje grafickou úpravu mapování. Tento model je v ASP.NET reprezentován XML souborem DBModel.edmx, který nadále obsahuje další soubory. Výsledný model mapování je uveden v příloze 2. Poté následovala fáze stylování a tvorby jednotlivých stránek. Aby se dosáhlo jednotného vzhledu pro více stránek s několika stejnými částmi bez nutnosti kopírování kódu, byly využity master page stránky, v kterých se definují společné části a proměnné bloky, do kterých lze vkládat obsah. Jednotlivé master page můžou být do sebe vnořené a tím vytvářet složité struktury pro rozsáhlé webové aplikace. Kód pro definici proměnného bloku lze napsat následovně:
V aplikaci byla definována jedna hlavní Base. Master stránka, která obsahuje základní definici vzhledů. Do této stránky jsou vnořené další tři, které jsou již konkrétnější specializací pro dané určení. Jedná se o stránku sloužící pro nastavení (Setting.Master), pro autentizaci a operace s ní spojené (Autentization.Master) a pro hlavní stránku (Home.Master). Z takto definovaných master stránek, již můžeme vytvořit jednotlivé Contentpage (aspx stránky). Tyto stránky pak obsahují jednotlivé Contenty vygenerované na základě Master page. Takováto stránka s návazností na předchozí příklad může vypadat následovně: <%@Page Title="" Language="C#" MasterPageFile="~/App_Core/Home.Master" CodeBehind="Default.aspx.cs"%>
Na příkladu vidíme ještě direktivu Page, která pomocí atributu MasterPagerFile definuje, do které master page stránky bude doplněn obsah. Dále pro lepší přehlednost a efektivitu podporují aspx stránky tzv. kód na pozadí, který je realizován klasickou třídou ve zvoleném programovacím jazyce. Přiřazení této třídy definuje atribut CodeBehid a zvolený implementační jazyk atribut Language. Tímto způsobem byly vytvořeny jednotlivé stránky pro interakci s uživatelem. Za pozornost stojí domovská stránka Default.aspx a stránka s nastavením Settings.aspx, které budou níže podrobněji rozebrány. Nedílnou součástí implementace bylo řešení autentizaci a autorizaci uživatele. K tomuto účelu ASP.NET poskytuje model pro správu uživatelských účtů a oprávnění. Já jsem z tohoto modelu využil dvě části a to Membership a Roles. První část se stará o autentizaci a identifikaci uživatele. Druhá část rozhoduje o tom, co uživatel může a nemůže dělat. Tedy každého uživatele z Membership můžeme přiřazovat do několika rolí. Dále zde můžeme rozhodovat o tom, jestli je uživatel přihlášený, nepřihlášený nebo zařazen do nějaké role. Aby tento model fungoval, je nutná tzv. sada providerů. Jedná se o třídy, které poskytují patřičné operace spojené s danou částí modelu. ASP.NET poskytuje vestavěné providery, které však nejsou příliš flexibilní s ohledem na jejich úpravu. Další možností je definování vlastních, což však nebylo potřeba, jelikož spousta kvalitních providerů je dostupná formou NuGet7 balíčků. Já jsem využil Altaris Web Security Toolkit8 balíček, který obsahuje 7
www.nuget.org
37
jednotlivé providery. Po nainstalování balíčků a potřebné konfigurace ve web.config, lze již využívat jednotlivé komponenty pracující s providery. Pro nastavení Membership providera byl použit následující kód: <membership defaultProvider="MyMembershipProvider" userIsOnlineTimeWindow="15"> <providers>
Dále jsem využil SimpleSqlRoleProvider, jehož nastavení je obdobné. Díky využití těchto providerů vznikla možnost efektivního nastavení pravidel přístupu do jednotlivých složek a stránek. Samotná pravidla se zapisují do web.config, ať už do kořenového adresáře nebo do konkrétního, v kterém chceme upravit pravidla. Nejvyšší váhu má pravidlo uvedené ve web.config umístěném v kořenovém adresáři. U definice pravidel je nutno brát v potaz souvislosti a návaznosti. Tedy pokud povolíme nepřihlášenému uživateli přístup na stránku s formulářem pro přihlášení, pak nesmíme zapomenout také povolit přístup k css souborům, které mohou být umístěny v jiném adresáři. Ukázka použitého pravidla, které povoluje dodatečný přístup nepřihlášeným uživatelům ke stylům umístěných v adresáři App_themes, byla implementována následovně: <system.web>
V celé aplikaci byla nastavena práva tak, aby se nepřihlášený uživatel dostal pouze na stránky spojené s autentizací. Tato varianta byla zvolena díky nutnosti uchovávat uživatelovo nastavení potřebné pro správnou funkčnost doporučovacího systému. Dále byla řešena implementace routování url adres, které slouží jednak pro hezčí url adresy, ale také pro jednoduchou správu cest, k jednotlivým stránkám v případě jejich změny. K tomuto účelu byl využit soubor Global.asax, který je také označován jako aplikační soubor technologie ASP.NET. V tomto souboru byla vytvořena metoda RegisterRoutes, která je volána při startu aplikace. V této metodě jsou pak definována jednotlivá pravidla. Přidání takového pravidla může vypadat následovně: RouteTable.Routes.MapPageRoute("DefaultRoute", "kategorie/{category}", "~/Default.aspx", true, newRouteValueDictionary { { "category", "" } });
kde první parametr je název pravidla, druhý specifikuje, jak bude vypadat výsledná url adresa. Třetím parametrem je fyzická cesta ke stránce a posledním defaultní nastavení parametru category. V případě, že chceme někde ve stránce navigovat na jinou stránku, využijeme právě název definovaného pravidla. 8
http://altairiswebsecurity.codeplex.com/
38
Jednotlivé ukázky výsledného uživatelského rozhraní jsou uvedeny v příloze 3. Default.aspx Při implementaci stránky Default.aspx bylo plně vycházeno z grafického návrhu uvedeného na Obrázku 11 v kapitole 4. Jak již bylo řečeno, snahou bylo vytvořit jednoduché a intuitivní grafické rozložení komponent, pro jednoduché ovládání. Pro realizaci vkládání dynamických dat do stránky, byly využity ASP.NET komponenty. Jedná se o komponenty, ke kterým lze na pozadí v kódu přistupovat a měnit různé vlastnosti. Každá taková komponenta musí mít atribut runnat=“server“ a tím je definováno, že k ní lze přistupovat programově. Nejvíce využívanou komponentou byl asp:Repeater, který slouží jako „opakovač“. V této komponentě si můžeme nadefinovat vzhled nějaké položky, kterou bude chtít opakovat. V případě, kdy komponentě nastavíme vstupní data (kolekci objektů) a provedeme DataBind nad danou komponentou, dojde k jejímu naplnění a provedení patřičné operace. Pomocí této komponenty byl například implementován výpis jednotlivých menu. Ukázkou použití asp:Repeater je následující kód:
Důležitými prvky jsou atributy ID a runat, bez kterých by žádná komponenta nepracovala správně. Z důvodu, aby kód obsluhující jednotlivé komponenty zůstal přehledný a jednoduše modifikovatelný, byla zcela odloučena datová vrstva do jednotlivých tříd, které připravují data a poskytují příslušené metody. Samotná stránka Default.aspx zobrazuje jednotlivá menu (Obrázek 21) z restaurací, které má uživatel vybrané. Tyto menu jsou seřazené podle hodnocení spočítané hodnotícím algoritmem. Tento algoritmus je podrobněji rozebrán v kapitole 5.2.3. U každé položky menu si může uživatel zobrazit detail o restauraci, ohodnotit menu a případně přejít na celý jídelní lístek.
Obrázek 21: Položka menu na hlavní stránce
Další informací, kterou poskytuje hlavní stránka je přehled jednotlivých uživatelových restaurací a to v podobě mapy nebo seznamu. V samotných menu lze vyhledávat pomocí realizovaného fulltextového vyhledávání, které je postaveno na fulltextovém indexu v databázi. Pro realizaci tohoto vyhledávání bylo nutno přidat metodu realizující fulltextový dotaz do objektu reprezentující menu. Tento objekt je generován EF při mapování databáze a je vytvořen jako částečná třída (partial class). Partial class umožňuje rozdělit definici třídy do více zdrojových souborů, pro snazší přidávání metod do generovaného kódu. Proto byla vytvořena nová partial class tblMenu, která obsahuje definici metody FullTextSearch. Díky této úpravě lze využívat fulltextové vyhledávání i pomocí dotazovacího jazyka LINQ, který ho standardně nepodporuje. Samotný fulltextový dotaz vypadá následovně: SELECT * FROM
tabulka WHERE freetext(sloupec, hledaná fráze)
39
Výhodou slova freetext je, že nehledá pouze celé fráze, ale jednotlivá slova zpracovává jako výrazy a poté vrátí výsledek. Další možnost filtrování pomocí jednotlivých kategorií je zobrazena na obrázku 22, kdy velikost textu dané kategorie odpovídá její popularitě. Čím větší text, tím populárnější kategorie.
Obrázek 22: Kategorie
Settings.aspx Stránka Settings.aspx opět vychází ze stejného grafického návrhu, jen má jiný obsah a účel. Tato stránka slouží pro uživatelovo nastavení týkající se jednotlivých restaurací a jeho preferencí kategorii. Samotná stránka je jakoby rozdělena na dvě části, které spolu souvisí. V horní polovině se nachází mapa a tabulka obsahující uživatelovi restaurace a v dolní nastavení preferencí. Mapa byla implementována s využitím Google Maps API v3. Já jsem nepoužíval přímo oficiální API dostupné v JavaScriptu, ale využil jsem opět formou NuGet balíčku dostupné rozšíření pro ASP.NET, které poskytuje jakousi nástavbu nad tímto API, převedenou do jazyku C#. Samotný balíček je dostupný pod jménem GoogleMap Control 6.1 NuGet Package ve správci balíčků nebo na domovské adrese9. Na níže uvedeném obrázku 23 vidíme výslednou mapu s jednotlivými záložkami označující restaurace. Zelené označují přidané restaurace a červené nepřidané. Po kliku na danou záložku se zobrazí nabídka s detailem a možností přidat nebo odebrat. V mapě bylo nadále implementováno vyhledávání, které pracuje stejně jako na oficiálních stránkách Google Maps10. Akorát v případě, že nalezne více výsledků, zobrazí pouze první. Proto je nutné v případě špatného nalezení adresy lépe specifikovat požadavek.
Obrázek 23: Mapa s restauracemi
Nastavování preferencí spočívá v ovlivnění, jaká kategorie jídel je daným uživatelem preferovaná. U každé kategorie lze nastavit preferenci v procentech od jednoho do sta. Díky tomuto 9
nastavení může uživatel ovlivnit výsledky doporučovaní. Samotné nastavování bylo realizováno zpracováváním na pozadí a díky tomu není uživatel při každé změně preference nucen čekat na obnovení stránky. Tohoto bylo dosaženo díky asynchronní komunikaci dvou komponenty asp:UpdatePanel a ajaxToolkit:SliderExtender. V případě změny hodnoty preference vyvolá komponenta SliderExtender událost a pomocí asynchronního postbacku dojde k zpracování vyvolané události se současnou aktualizací nadřazeného UpdatePanelu, s kterým je svázaná. Pro komunikaci s uživatelem se po takto provedené operaci na pozadí zobrazí informativní panel s informací o tom, jestli byla operace úspěšná nebo ne. Nedílnou součástí nastavování jsou preference sloužící pro úpravu uživatelského rozhraní, které jsou realizovány obdobně. V případě provedení jakýchkoliv změn v nastavení ovlivňující model pro doporučovací systém, dojde při odchodu z této stránky k jeho přepočítání, aby uživateli byly zobrazeny aktuální data.
5.3
RSS Parser
Na základě funkčních požadavků na RSS parser bylo rozhodnuto, že bude implementován jako samostatná aplikace s využitím technologie WCF (Windows Communication Foundation). Jedná se o programový model používaný pro servisově orientované aplikace. Využil jsem konkrétně WCF service application, která se používá pro tvorbu webových služeb. Výsledkem této aplikace je webová služba, kterou lze umístit na IIS server. Tato služba poté může poskytovat jednotlivé metody, které lze volat pomocí klienta, anebo tyto metody může zpřístupnit pomocí HTTP/S protokolu. Pro účely RSS parseru byla zvolena druhá varianta z důvodu její flexibility. Prvním krokem implementace služby bylo vytvoření interface pro definici rozhraní, pomocí kterého bude služba komunikovat. Jedná se o klasické rozhraní, kde jednotlivé metody mají navíc patřičné atributy sloužící pro nastavení. Takto byla definována metoda sloužící pro spuštění RSS parseru. Její definice je následující: [OperationContract] [WebInvoke(Method = "GET", ResponseFormat = WebMessageFormat.Json, UriTemplate = "LoadData")] string LoadData();
Vidíme zde dva atributy, první OperationContract říká, že metoda bude vystavena klientovi a druhý WebInvoke definuje přístup pomocí URL adresy a návratový typ dat typu JSON. Zde této metodě byla přidělena adresa LoadData. Pro správnou funkčnost této adresy je ještě nutné ve web.configu definovat adresu samotné služby. Adresa byla definována následovně: <serviceActivations>
Kde atribut relativeAddress definuje výslednou adresu. Poté výše uvedenou metodu LoadData bychom zavolali pomocí následující URL: <doména>/service/CheckData.svc/LoadData
41
Metoda LoadData předává třídě RssParser jako parametr seznam restaurací, které má zpracovat. Samotný proces zpracování probíhá po jednotlivých restauracích. Každý záznam o restauraci obsahuje adresu RSS kanálu. Vzhledem k předem známé struktuře každého RSS kanálu bylo využito standardních nástrojů pro parsování XML dokumentu. K parsování byly využity metody dostupné v knihovně System.Xml.Linq, poskytující možnost definovat typ dokumentu pro zpracování. V mém případě se jednalo o typ dokumentu specifikovaného na adrese http://purl.org/rss/1.0/. Z adresy lze určit, že se jedná o dokument typu RSS verze 1.0. Po načtení dokumentu do paměti je dokument rozdělen na jednotlivé uzly item, z kterých jsou nadále vybrány tři vnořené elementy title, link a description. Obsahem těchto elementů je naplněná nová třída RSS, reprezentující jeden záznam. Po zpracování všech uzlů získáme kolekci objektů RSS, reprezentující jednotlivé záznamy. Každý záznam odpovídá nějakému dni v týdnu. Samotný formát dokumentu je demonstrován následující ukázkou, v které je z důvodu velikosti uvedena pouze jedna položka a byly v ní odstraněny jednotlivé styly. 14.5.2013 Denní menu Krčma u svatého Václava http://www.lunchtime.cz/krcmausvatehovaclava/?rssDay=2013-05-14 <description>
<span style="..." />Denní menu <span style="COLOR: #999999;">/ Brno <span style="...">/ Královo Pole <span style="...">/ Palackého třída <span style="...">- Úterý 14.5.2013
Po takto předzpracovaném vstupu přecházíme k fázi zpracování jednotlivých záznamů. Jak z ukázky plyne, pro zpracování lze využít výhod spojených s jazykem html. K tomuto účelu byla využita knihovna HtmlAgilityPack11, která podporuje parosvání HTML dokumentů. Navíc je velice tolerantní k případným chybám, které se mohou v syntaxi vyskytnout. Pomocí této knihovny je z daného záznamu získán datum a je vyhodnoceno, zda se jedná o aktuální den. Pokud ne, záznam je zahozen a zpracovává se další. V opačném případě je záznam dále zpracováván. Je z něho nutno získat jednotlivé položky menu, které jsou umístěny v elementu table. Položka menu je brána jako jeden řádek obsahující dva sloupce. V jednom se nachází název a v druhém cena. Takto získá všechny hodnoty a předá je další metodě ke zpracování. Ta se již snaží o zařazení daného menu do konkrétních kategorií, do kterých by mohlo patřit. Samotné zařazování je realizováno pomocí regulárních výrazů. V případě, že se menu nepodaří zařadit do žádné kategorie, je implicitně zařazené do defaultní nezařazeno. Jednotlivé záznamy jsou poté ukládány do databáze. V případě, že při zpracovávání nastane chyba nebo daná restaurace ještě neposkytla jídelní lístek na daný den, je k restauraci nastaven příznak o tom, že načtení nebylo korektní. Z toho důvodu byla do služby přidána další metoda LoadDataCheck sloužící pro zpracování těchto chyb. Zpracováním je myšlen opětovný pokus načtení dat restaurací s tímto příznakem. Díky tomu, že služba poskytuje přístup k jednotlivým metodám přes URL adresu, byl pro plánování jednotlivých událostí využit plánovač SetCronJob12. Výhodou tohoto plánovače je, že poměrně jednoduchou úpravou lze měnit plány provádění jednotlivých operací. Toho bylo využito především pro naplánování opakovaného načítání z důvodu nedostupnosti dat.
5.4
Doporučování
Implementace algoritmu pro doporučování proběhla přesně podle návrhu uvedeného v kapitole 4.4. Součástí návrhu bylo i získání dat potřebných pro vytvoření uživatelova modelu. Pro tyto účely byla vytvořena třída RatingController, která se stará o operace spojené s hodnocením jednotlivých položek. Položkou je myšlené konkrétní vypsané jídlo. Jak již bylo zmíněno v návrhu, systém nehodnotí konkrétní položky, ale jednotlivé kategorie a restauraci, do které spadá. Tyto informace poté archivuje v databázi. Při implementaci algoritmu pro výpočet podobnosti jednotlivých položek menu s uživatelovým modelem bylo nutno rozlišovat tři různé stavy, ve kterých se model nachází. •
• •
Uživatel nemá žádnou historii hodnocení a současně nelze nalézt žádného uživatele, který by měl nějaké hodnocení pro stejné restaurace. Díky tomu lze pro výpočet použít pouze známé preference uživatele, které poslouží jako model. Uživatel má nějakou historii hodnocení, která ale není postačující pro výpočet podobnosti. Proto je k ní připojena historie hodnocení ostatních uživatelů pro stejné restaurace. Uživatel má postačující historii hodnocení, na základě které lze provést výpočet.
Všechny výpočty pro jednotlivé stavy jsou založené na kosinusově podobnosti vektorů. Každý vektor reprezentuje jednu položku a jeho počet složek odpovídá celkovému počtu dostupných kategorií v systému plus s jednou pro restauraci. Tyto složky pak mají hodnotu 1 nebo 0 v závislosti, zda daná 11 12
Dostupná na http://htmlagilitypack.codeplex.com/ nebo formou NuGet balíčku Dostupný na adrese https://www.setcronjob.com
43
položka do konkrétní kategorie patří nebo nepatří, či zda jsou obě položky ze stejné restaurace. Díky takto zvolenému výpočtu lze každé kategorii (složce) dávat určitou váhu, na základě které můžeme ještě ovlivnit výpočet. Tato váha odpovídá hodnotě preference dané kategorie, kterou si uživatel nastavil. Jelikož jednotlivé preference jsou reprezentovány pomocí procent, je nutné tyto hodnoty převést do intervalu P0,5S, aby odpovídaly hodnotám získaných při hodnocení. Druhý a třetí stav, ač mají rozdílné vstupy, mají stejný výpočet. V tomto výpočtu dochází navíc k násobení váhového vektoru s hodnotou hodnocení, kdežto první stav počítá pouze s položkami a jednotlivými váhovými vektory. Pro lepší pochopení problému si uvedeme příklad výpočtu pro dvě položky A a B, uvedené v následující tabulce, kde jedna bude reprezentovat novou a druhá již ohodnocenou. Nová položka A Již ohodnocená položka B Kategorie k1,k2,k5 k1,k3,k5 Restaurace r1 r2 Tabulka 1: Smyšlené položky pro potřeby výpočtu
Prvním krokem je sestavení odpovídajících vektorů reprezentující dané položky. Tento krok zobrazuje následující tabulka, kde již vidíme jednotlivé vektory. Sestavení těchto vektorů proběhlo přesně podle výše popisovaného postupu, kdy 1 značí, že položka do dané kategorie patří a 0, že ne. Položka A Položka B
1 1
1 0
0 1
0 0
1 1
0 1
k1
k2
k3 Kategorie
k4
k5
r2 Restaurace
Tabulka 2: Výsledné vektory pro položky A a B
Dalším krokem výpočtu je roznásobení jednotlivých složek vektorů odpovídajícím váhovým vektorem modifikovaným o hodnotu hodnocení. Tedy, pokud by měl uživatel nastavenou preferenci u kategorie k1 na 80% a položka B by byla hodnocena hodnotou 4, výsledná složka váhového vektoru TO odpovídající kategorii k1 by se spočítala jako: TO = preference k1 * 5 * hodnocení B = 0,8 *5 * 4 = 16
S využitím tohoto postupu dojde k postupnému výpočtu jednotlivých podobností mezi novou položkou a všemi položkami hodnocenými daným uživatelem. Výsledná podobnost nové položky s celým modelem se poté spočítá jako aritmetický průměr jednotlivých dílčích podobností. Pokud se jedná o případ jedna, kdy nemáme žádné uživatelovo hodnocení, je výpočet proveden jen pomocí váhových vektorů.
44
Výsledný pseudokód implementovaného algoritmu pro případ dva a tři vypadá následovně: Vstup: seznam uživatelů U Výstup: tabulka podobností mezi jednotlivými položkami a hodnocením Metoda: For( všechny uživatele u v U) Načti položky menu M daného uživatele u Načti hodnocení všech položek R daného uživatele u If( počet(R) < limit) Přidej k hodnocení R hodnocení sousedů For(každou položku m v M) Nastav P na 0 //reprezentuje podobnost mezi m a R For(každou položku r v R) Spočítej podobnost(m,r)a přičti ji k P Výsledná podobnost mezi m a R je V = P / počet(R)
Algoritmus 1: výpočet podobnosti
Z algoritmu je patrné, že samotný výpočet lze ovlivňovat hned několika parametry. Jedná se především o jednotlivou úpravu váhových vektorů, ale také o specifikaci požadovaného počtu vstupních dat. Je tedy nutné nastavit limit, kdy budeme brát počet hodnocených záznamu uživatelem jako dostatečný a kdy ne. Dalším nutným omezením je maximální počet načítaných záznamů R, jelikož po delší době provozu, by se mohlo stát, že čas potřebný pro výpočet bude již neúnosný. Navíc při načítání veškeré historie hodnocení by mohl model po delší době provozu stagnovat. Jednotlivé parametry a jejich vliv na výsledek výpočtu jsou rozebrány v kapitole 6, kde pomoci testování bylo zvoleno optimální nastavení. Pro implementaci tohoto algoritmu byla vytvořena třída RecommItemController, v které byly implementovány všechny metody potřebné pro jednotlivé operace výpočtu. Samotný proces výpočtu je prováděn v režimu offline v případě, že dojde k načtení nových dat do systému. K tomuto účelu byla do služby, v které je implementován RSS parser přidána metoda, zajišťující volání potřebných funkcí pro výpočet. Definice rozhraní metody je následující: [OperationContract] [WebInvoke(Method = "GET", ResponseFormat = WebMessageFormat.Json, UriTemplate = "ComputeData")] string ComputeData();
Pokud však uživatel provede nějaké změny svých preferencí, je proveden nový výpočet pouze pro daného uživatele. Tím je zaručeno, že uživatel dostane vždy aktuální data. Výstupem výše uvedeného algoritmu 1 je tabulka obsahující pro každou položku menu konkrétního uživatele záznam o její podobnosti s uživatelovým modelem. Poté při zobrazování jednotlivých nabídek jsou tyto záznamy seřazené podle dosažené podobnosti a zobrazeny, což je již velice rychlá operace.
45
5.5
Hosting
Při hledání hostingu pro výslednou aplikaci jsem se zaměřil především na jednotlivé parametry, které daný hosting podporuje. Jedná se o tyto parametry: • • •
IIS 7 a vyšší ASP.NET 4.0 a vyšší SQL SERVER 2008 a vyšší
Z dostupných řešení na internetu jsem vybral hosting asp2.cz13. Jedná se o free hosting podporující nejnovější technologie společnosti Microsoft. Je především určen pro testování při vývoji, ale i pro případné nasazení s určitými omezeními. Jedním z omezení je dostupnost pouze domény třetího řádu. Za ním následuje limit pro velikost databáze a celkové omezení diskového prostoru. Přesto pro moji aplikaci byly dostačující. Při prvním nasazování aplikace na web nastaly různé problémy. Bylo nutno vyexportovat a obnovit databázi, kde byly problémy spojené s kódováním, které bylo nutno odstranit. Poté nastal problém s virtuálním adresářem pro WCF službu, který se stále choval jako běžný adresář. Tento problém byl nakonec vyřešen společným web.config souborem pro webovou aplikaci a službu. Po vyřešení těchto problému je výsledná aplikace již dostupná na adrese http://www.cosidas.asp2.cz
13
http://www.asp2.cz
46
6
Testování a zhodnocení
Pro ověření funkčnosti výsledné aplikace bylo zapotřebí ji otestovat. Samotné testování bylo rozděleno do dvou skupin, kdy každá je zaměřená na něco jiného. Jedná se o: •
Testování funkčnosti aplikace: cílem toho testování bylo ověřit, zda doporučovací algoritmus funguje tak, jak má a určit, jaké vlivy na doporučování mají jednotlivé jeho parametry.
•
Uživatelské testování aplikace: tato část testování se zaměřuje na testování uživatelského rozhraní na vybrané skupině uživatelů.
6.1
Testování doporučování
Jak již bylo zmíněno, výsledný algoritmus doporučování bylo nutné podrobit testování vlivu jednotlivých parametrů, ovlivňujících kvalitu doporučování, za účelem jejich správného nastavení a ověření funkčnosti. Pro testování byly využity různé datové sady odpovídající jednotlivým menu různých restaurací získaných ze stánky LunchTime14. Pro tyto účely bylo do systému přidáno 100 záznamů o jednotlivých restauracích především z oblasti Brno Královo pole a Brno Střed. Dále byly využity modely pro doporučování, které byly průběžně upravovány s ohledem na testovanou vlastnost. Samotná úprava spočívala v přidávání nebo odebírání historie hodnocení jednotlivých položek. Proces testování bylo nadále nutné rozdělit do několika fází, kdy se pokaždé testovala specifická vlastnost. Jedná se o: 1. Testování vlivu změny uživatelových preferencí Tento test se bude snažit ověřit správnou funkčnost vlivu změny jednotlivých preferencí na výsledné doporučení. Cílem tohoto testu je dosáhnout viditelné změny pořadí jednotlivých položek ve výsledném doporučení. Předpokladem pro tento test jsou datové sady obsahující jednotlivá menu, která budeme chtít doporučit. Pro potřeby tohoto testu byly vytvořeny tři datové sady, kdy každá sada obsahovala řádově 25 položek menu z různých restaurací. Proces tohoto testování spočíval ve změnách preferencí jednotlivých kategorií, kdy po každé změně byly sledovány změny pozice jednotlivých položek, patřících do právě modifikované preference. Tento proces byl prováděn opakovaně na jednotlivých sadách a ze sledování jednotlivých změn lze říci, že v tomto ohledu pracuje algoritmus správně. Dále bylo nutno otestovat vliv této změny preferencí v případě, že již existuje uživatelova historie hodnocení různých položek menu. K tomuto testu byly opět využity výše uvedené datové sady, které byly doplněny o uživatelovu historii hodnocení. Proces tohoto testu spočíval v ohodnocení skupiny položek menu spadající do stejné kategorie, aby se docílilo k jejímu upřednostnění. Poté pomocí změny preferencí jednotlivých kategorií bylo zkoumáno, zda lze původní doporučení ovlivnit. V průběhu tohoto testu je však nutné si uvědomit, aby nedocházelo ke špatným závěrům, že ne vždy kategorie s větší preferencí musí být na lepší pozici. Je tomu proto, že výpočet ovlivňují již hodnocené položky. Po provedení obou výše uvedených procesů testování pro jednotlivé datové sady a analýze výsledného chování systému lze říci, že v tomto ohledu algoritmus pracuje správně. 14
Dostupná na http://www.lunchtime.cz
47
2. Test pro určení minimálního počtu hodnocených položek Cílem tohoto testu bylo nalezení hodnoty odpovídající minimálnímu počtu potřebných hodnocení položek, aby bylo zajištěno kvalitní doporučení i v případě, kdy jsou jednotlivé preference nastaveny na stejnou hodnotu. Algoritmus poté vyhodnotí všechny (většinu v případě malého počtu hodnocení) položky datové sady rovnocenně, což má za následek, že výsledné pořadí položek odpovídá jejich pořadí ukládání do datové sady. Tento stav je nežádoucí a proto je nutné stanovení onoho minima, aby se dal problém vyřešit. Předpokladem pro tento test jsou opět datové sady obsahující jednotlivá menu, dále již zmíněné nastavení preferencí a možnost přidávat hodnocené položky (ohodnotit dané menu). Proces testování spočíval v postupném přidávání hodnocených položek do modelu, kdy při každé změně došlo k přepočítání doporučení. Poté byly porovnávány jednotlivé pozice doporučení a použité datové sady. V případě, že tyto pozice byly beze změny, byl do systému přidán další údaj o hodnocení a celý postup se opakoval. U tohoto testování hrálo velkou roli, do jakých kategorií hodnocená položka spadala. Čím více kategorií obsahovala, tím rychleji se podařilo nalézt požadované minimum. Výsledné minimum bylo poté určeno jako průměr jednotlivých získaných hodnot pro použité datové sady. Lze tedy říci, že již při 4 ohodnocených položkách, s ohledem na výše uvedené nastavení, můžeme zajistit kvalitní doporučení. 3. Test celkového doporučování Tento test se snažil ověřit celkovou funkčnost doporučovacího systému. Předpokladem k jeho provedení bylo využití výsledků z předchozích testů, stanovení pomyslné hranice mezi doporučovanými položkami a využití datových sad s průměrným počtem položek menu 25. Tato hodnota byla zvolena na základě analýzy počtu nabízených menu jednotlivých restaurací, která v průměru činí 5 menu na den. Dále pak podle úvahy, že každý uživatel navštěvuje v průměru 5 restaurací ve svém okolí. Samotný proces testování spočíval ve zkoumání, zda se námi preferované položky dostanou nad nebo pod definovanou pomyslnou hranici. Dá se říci, že tento test vychází z metriky Precision and Recall. Průběh tohoto testování měl několik kroků. I.
Prvním krokem bylo zobrazení jednotlivých položek menu obsažených v první datové sadě, ze kterých byly vybrány mnou preferované položky a ty ohodnoceny.
II.
V druhém kroku došlo k upřesnění preferencí pro jednotlivé kategorie a tím byl definován základní model pro doporučování.
III.
V třetím kroku došlo k zobrazení jiné datové sady, kde již bylo zkoumáno, na jakých pozicích se nacházejí mnou preferované položky.
Zkoumání uvedené v kroku III bylo opakováno na několika datových sadách a bylo zjištěno, že mnou preferované položky se vyskytovaly nejčastěji v TOP 12. Tento výsledek se však může obecně lišit, jelikož na něho má vliv jak zvolená datová sada, tak i model pro doporučování. Na základě tohoto testování bylo ještě přistoupeno k specifikování maximálního počtu hodnocených položek ovlivňujících výpočet. Bylo k tomu přistoupeno proto, aby model odpovídal více současnému vývoji chování uživatele a reagoval více na změny. Tato hodnota byla stanovena experimentálně na hodnotu 30, která odpovídá zhruba jednomu měsíci historie při hodnocení jedné položky za den.
48
Z dosažených výsledků výskytu preferovaných položek v TOP 12 hodnotím celkové doporučování jako dobré.
6.2
Uživatelské testování
Z důvodu, aby nebyl testován jen samotný algoritmus doporučování, ale aplikace jako celek, bylo přistoupeno k jednoduchému uživatelskému testování. Od tohoto testování bylo očekáváno získání postřehů z provozu aplikace. Samotný proces testování lze provádět několika způsoby, například předložením scénáře s úkoly danému uživateli a sledovat jeho činnost, nebo poskytnutím dvou různým skupinám rozdílné verze stránek a vyhodnotit, které jsou lepší. Způsobů je opravdu mnoho. Pro otestování výsledné aplikace byla nakonec zvolena metodika založená na scénáři. Pro realizaci a vyhodnocení této metodiky byl vytvořen jednoduchý dotazník, kde byly uvedeny otázky, na které testovaný uživatelé odpovídali. Před samotným testováním bylo vždy uživateli vysvětleno, k čemu aplikace slouží, avšak bez uvedení jednotlivých kroků potřebných pro nastavení. Cílem bylo totiž dosáhnout intuitivnosti celé aplikace. Výsledný dotazník obsahoval následující otázky: 1. Měli jste nějaký problém s aplikací? 2. Co byste v aplikaci udělali jinak? 3. Jak jste byly spokojeni s doporučováním? Takovýto dotazník byl předložen celkem 5 uživatelům, kterým byla současně zobrazena výsledná aplikace a bylo očekáváno jeho vyplnění. Je nutno podotknout, že při odpovídání na otázku 3, byla testovaným uživatelům poskytnuta asistence v podobě zajištění změny jednotlivých datových sad využívaných při testování v kapitole 6.1. Cílová skupina testovacích uživatelů se skládala především z technicky vzdělaných lidí, a proto byly očekávány věrohodné odpovědi. Samotný proces testování probíhal na lokálním IIS serveru, s využitím prohlížeče Chrome. Při vyhodnocování uživatelského testování bylo zjištěno, že většina odpovědí uživatelů se shoduje a navíc byly objeveny i nějaké nedostatky. U první otázky se uživatelé shodli na tom, že při prvním přihlášení do aplikace nevěděli, co mají nastavit, aby aplikace správně fungovala. To byl docela zásadní problém, a proto byl do aplikace přidán průvodce nastavením, který tento problém řeší. U druhé otázky, kdy byly tázáni na to, co by udělali jinak, byly odpovědi různé. Někdo uváděl, že řešení nastavení preferencí je příliš složité a někomu se zase nelíbil způsob implementace fulltextového vyhledávače, který má omezené možnosti vyhledávání. Vyhodnocování třetí otázky bylo rozdílné, jelikož při jejím vyplňování byli uživatelé požádáni, aby svoji spokojenost vyjádřili pomocí 10 úrovňové stupnice. Hodnota této stupnice odpovídá kvalitě doporučení. Tedy čím vyšší hodnota, tím lepší doporučení. Vyhodnocením bylo zjištěno, že většina hodnocení je v rozmezí 4 až 8 bodů. To odpovídá průměrné hodnotě. Proto lze říci, že z pohledu uživatelského testování bylo doporučení hodnocené jako dobré. Díky tomuto testování se podařilo identifikovat některé nedostatky aplikace, které byly opraveny a upozornit na slabé části, na které by bylo nutné se zaměřit při budoucím vývoji.
49
6.3
Zhodnocení
Cílem této kapitoly bylo podrobit aplikaci některým testům za účelem dosažení lepší kvality výsledné aplikace a samotného doporučování. Doporučovací algoritmus byl testován pomocí výše uvedených testů, na základě kterých, byly specifikovány jednotlivé parametry ovlivňující jeho výpočet. Snahou bylo dosažení co nejlepšího výsledku pro širokou skupinu uživatelů. Velký vliv na kvalitu doporučování z pohledu uživatele má datová sada, nad kterou je doporučování počítáno. V případě, že datová sada obsahuje položky, o které má uživatel zájem, lze pak předpokládat, že i výsledné doporučení bude hodnoceno jako dobré. Naopak, v případě kdy datová sada obsahuje pro uživatele nezajímavá data, lze zcela jistě předpokládat, že výsledné doporučení bude hodnocené špatně. Tuto vlastnost však již nelze ovlivnit.
50
7
Závěr
Hlavním cílem této diplomové práce bylo navrhnout a implementovat doporučovací systém webové aplikace. Po dohodě s vedoucím práce byla zvolena jako aplikační oblast doporučování jídel z restaurací. Na první pohled se může zdát, že se jedná o oblast velice podobou internetovým obchodům, ale opak je pravdou, jelikož zde nastává několik zásadních odlišností, které bylo nutné vyřešit. Součástí této práce je i teoretický rozbor, týkající se doporučovacích systému, který byl zpracován již v rámci semestrálního projektu, na který tato práce navazuje. Jsou zde uvedeny jednotlivé metody používané pro doporučování a problémy kterými trpí. Dále je zde uveden přehled jednotlivých testovacích metrik používaných pro ohodnocení kvality doporučování. Poté následuje část věnovaná návrhu aplikace, kde je proveden rozbor a návrh jednotlivých částí. Za zmínku stojí část věnovaná návrhu doporučovacího algoritmu, která se snaží řešit problémy plynoucí z dané aplikační oblasti. Jedná se především o problém plynoucí z často se měnících položek. Na tuto část navazuje samotná implementace, kde jsou rozebrány jednotlivé implementační detaily. Výsledná funkčnost implementovaného algoritmu byla ověřena na různých datových sadách a modelech, což ve fázi optimalizace, přispělo k dosažení lepších výsledků pro různé uživatele. Pro budoucí vývoj a rozšíření této aplikace, by bylo nutné do systému zařadit více restaurací, aby došlo k postupnému pokrytí všech měst. V současnosti totiž aplikace disponuje pouze pokrytím části Brna. Dále by bylo nutné se zaměřit na přepracování fulltextového vyhledávače a dát tak uživateli větší volnost ve vyhledávání. Také by stálo za úvahu, zda nepřepracovat systém zařazování jednotlivých položek do kategorií, tím způsobem, že by existovalo méně kategorii na vyšší abstraktní úrovni.
51
Literatura [1]
BERKA, Petr. Dobývání znalostí z databází. Praha: Academia, 2003. ISBN 80-200-1062-9.
[2]
JANNACH, Dietmar, ZANKER, Markus, FELFERNIG, Alexander, FRIEDRICH, Gerhard. Recommender Systems: An Introduction. Cambridge University Press, 2010. ISBN 978-0521493369.
[3]
BÍNOVÁ, Dagmar. Využití vybraných statistických metod při zpracování dat technikami Data mining. Disertační práce, Praha, 2006.
[4]
MORTENSEN, Magnus. Design and Evaluation of a Recommender Systém, Masters´s Thesis, University ofTroms, 2007.
[5]
BURKE, Robin. Hybrid Recommender Systems: Survey and Experiments [online]. In User Modeling and User-Adapted Interaction Volume 12 Issue 4, 2002. s. 331–370. [cit. 2012-12-30]. Dostupné z: http://dl.acm.org/citation.cfm?id=586352.
[6]
RICCI, Francesco, ROKACH, Lior, SHAPIRA, Bracha. Introduction to Recommender Systems Handbook.In RICCI, F., ROKACH, L., SHAPIRA, B., KANTOR, P., B., Recommender Systems Handbook, Springer, 2010. s. 1–35. ISBN 978-0387858197.
[7]
SEGARAN, Toby. Programming collective intelligence: building smart web 2.0 applictions. Sebastopol: O´Reilly, 2007, xxi, 334 s. ISBN 978-0-596-52932-1.
[8]
MELVILLE, Prem, SINDHWANI, Vikas. Recommender Systems [online]. In Encyclopedia of Machine Learning, 2010. [cit. 2012-12-30]. Dostupné z: http://www.prem-melville.com/publications/recommender-systems-eml2010.pdf.
[9]
VEHLOVSKÝ, Martin. Agregátor slevových nabídek s doporucovacím systémem. Magisterská práce, ČVUT v Praze, Fakulta informačních technologií, 2012.
[10]
EKSTRAND, Michael, RIEDL, John, KONSTAN, Joseph. Collaborative filtering recommender systems. Hanover, Mass: now Publishers. ISBN 978-160-1984-425.
[11]
FAYYAD, Usama, PIATETSKY-SHAPIRO, Gregory, SMYTH, Padhraic. From Data Mining to Knowledge Discovery in Databases [online]. In AI Magazine Volume 17 Number 3, 1996. s. 37–45. [cit. 2012-12-30]. Dostupné z: http://www.aaai.org/ojs/index.php/aimagazine/article/viewArticle/1230.
ALMAZRO, Dhoha, SHAHATAH, Ghadeer, ALBDULKARIM, Lamia, KHEREES, Mona, MARTINEZ, Romy, NZOUKOU, William. A Survey Paper on Recommender Systems [online]. 2010 [cit. 2012-12-30]. Dostupné z: http://arxiv.org/pdf/1006.5278v4.pdf.
[14]
BURKE, Robin. Knowledge-based recommender systems [online]. In Encyclopedia of Library and Information Science 69, 2000. [cit. 2012-12-29]. Dostupné z: http://www.cs.odu.edu/~mukka/cs795sum10dm/Lecturenotes/Day6/burke-elis00.pdf.
[15]
METEREN, Robin, SOMEREN, Maarten. Recommendation. University of Amsterdam.
[16]
HLOSTA, Martin. Modul pro shlukovou analýzu systému pro dolování z dat. Diplomová práce, Brno, FIT VUT v Brně, 2010.
MICROSOFT CORPORATION. Visual Studio 2012. In: MSDN Library [online]. [cit. 2013-03-04]. Dostupné z: http://msdn.microsoft.com/enus/library/bb165114.aspx.
[19]
C# corner. Migrating from ASP to ASP.NET [online]. 2004 [cit. 2013-03-04]. Dostupné z: http://www.csharpcorner.com/UploadFile/Dada%20Kalander/MigratingASPtoASP.NET11262005 035157AM/MigratingASPtoASP.NET.aspx.
SCHRÖDER Gunnar. Setting Goals and Choosing Metrics for Recommender system Evaluations [online]. In: CEUR Workshop Proceedings [cit. 2013-03-04]. Dostupné z: http://ucersti.ieis.tue.nl/files/papers/4.pdf.
Using Content-Based Filtering for
53
Seznam příloh Příloha 1. Schéma databáze Příloha 2. Model databáze EF Příloha 3. Uživatelské rozhraní Příloha 4. CD se zdrojovými soubory implementační části
54
Příloha 1 – schéma databáze
Obrázek 24: Schéma databáze
55
Příloha 2 – model databáze EF
Obrázek 25: Model databáze EF
56
Příloha 3 – ukázky uživatelského rozhraní
Obrázek 26: Hlavní stránka
Obrázek 27: Stránka s nastavením
57
Příloha 4 – obsah přiloženého CD docs/
- text diplomové práce v PDF a zdrojové texty v DOCX
src/
- zdrojové soubory ASP.NET aplikace včetně projektu
