Univerzita Hradec Králové Fakulta informatiky a managementu Katedra informačních technologií
Aplikace strojového učení v oblasti e-komerce Diplomová práce
Autor: Pavel Vraný Studijní obor: aplikovaná informatika
Vedoucí práce: Ing. Filip Malý, Ph.D.
Hradec Králové
srpen 2013
Prohlášení: Prohlašuji, že jsem diplomovou práci zpracoval samostatně a s použitím uvedené literatury.
V Hradci Králové dne
Pavel Vraný
Poděkování Děkuji vedoucímu diplomové práce Ing. Filipovi Malému, Ph.D. za vstřícný přístup, věcné připomínky a čas, který mi věnoval.
Anotace Cílem diplomové práce je představit strojové učení jako účinný nástroj ke zvyšování efektivity v oblasti e-komerce a na praktických příkladech demonstrovat jeho nasazení. Nejdříve jsou popsány nezbytné teoretické základy strojového učení a některé často používané algoritmy. Další část práce je věnována aplikaci na vybrané problémové domény. Na závěr jsou provedeny ukázkové implementace některých z nich.
Annotation Title: Application of machine learning methodsin e-commerce The aim of the diploma thesis is to introduce the machine learning as an effective tool to increase the efficiency in the field of e-commerce and describe its application on practical examples. The theoretical part focuses on the description of basic concepts and describes some commonly used algorithms. Another part is devoted to the application to the selected problem domains and the final part is deal with a sample implementations of some of thems.
Obsah 1
Úvod......................................................................................................................................1
2
Cíl a metodika práce.............................................................................................................3
3
Popis použitých metod..........................................................................................................4 3.1
Učení s učitelem.......................................................................................................9 3.1.1
Lineární regrese..........................................................................................12 3.1.1.1
3.1.2
3.2
Gradient descent............................................................................14
Klasifikace..................................................................................................15 3.1.2.1
Naivní bayesovský model..............................................................17
3.1.2.2
Rozhodovací stromy......................................................................18
3.1.2.3
Logistická regrese..........................................................................19
3.1.2.4
Klasifikace podle nejbližších sousedů...........................................20
3.1.2.5
SVM...............................................................................................20
Učení bez učitele....................................................................................................22 3.2.1
3.2.2
Shluková analýza.......................................................................................23 3.2.1.1
Hierarchické shlukování................................................................23
3.2.1.2
Nehierarchické shlukování............................................................24
Identifikace témat.......................................................................................25
3.3
Učení posilováním..................................................................................................27
3.4
Map Reduce............................................................................................................27
4 Aplikace metod na konkrétní problémy..............................................................................29 4.1 Agregace zpráv.......................................................................................................30 4.2
Rozpoznávání jazyka..............................................................................................31
4.3
Rozpoznávání obsahu.............................................................................................32
4.4
Rozpoznávání emocí...............................................................................................32
4.5
Rozpoznávání zájmu o produktové vlastnosti........................................................33
4.6
Extrahování informací............................................................................................33
4.7 Analýza grafických dat...........................................................................................34 4.8 5
Předpověď chování návštěvníka webu...................................................................37
Popis implementace............................................................................................................39 5.1
Nástroje...................................................................................................................39
5.1.1 Apache Mahout..........................................................................................40 5.1.2 Weka...........................................................................................................40 5.1.3
Java-ML.....................................................................................................41
5.1.4
Mallet.........................................................................................................42
5.1.5
BoofCV......................................................................................................42
5.1.6 Apache Commons Math.............................................................................43 5.2
Demonstrační aplikace...........................................................................................44 5.2.1 Agregátor zpráv..........................................................................................44 5.2.2
Hledání vizuálně podobných produktů......................................................46
5.2.3
Klasifikace zákazníků pomocí Naive Bayes..............................................50
6
Shrnutí výsledků.................................................................................................................53
7
Závěry a doporučení............................................................................................................55
8
Seznam použité literatury....................................................................................................56
9
Seznam obrázků a tabulek...................................................................................................59
10
Přílohy...............................................................................................................................60
1
Úvod Pro začátek je vhodné uvést, co se skrývá pod pojmem „strojové učení”. Nápomocny
k tomu budou následující dva citáty: „Strojové učení je obor, který dává počítačům schopnost učit se, aniž by byly explicitně naprogramovány.” [Arthur Samuel 1959][1] „Strojové učení je programování počítačů pro optimalizaci výkonnostního kritéria za využití vzorku historických dat.”[2] Strojové učení tvoří samostatný obor umělé inteligence, který dokáže odvodit nové informace z analyzovaných vstupních dat. Namísto vytváření počítačového programu s konkrétním postupem odvozování je tento nahrazen aplikací univerzálních metod strojového učení. Při aplikacích strojového učení je běžné, že implementátor nezná exaktní algoritmus převodu vstupních dat na požadovaný výstup a přesto mu tento fakt nebrání pro takový případ vytvořit fungující model. Nakonec jsou případy, kdy exaktní algoritmus ani neexistuje. O sledované veličině je pouze známo, že nenabývá zcela náhodných hodnot. Výsledný model pak pouze aproximuje výstupní hodnoty a jeho kvalita je posuzována rozdíly mezi aproximací a skutečností. Tyto vlastnosti umožňují aplikace strojového učení pro řešení různorodých problémů. Podle [3] je vhodné použít strojové učení v případech, kdy: 1. je třeba analyzovat více dat, než zvládne člověk 2. je možné definovat a změřit cíl 3. v dané oblasti existuje velká konkurence Nasbírat množství dat není v prostředí Internetu nic složitého, jen logování aktivit návštěvníků generuje objemy, jež není možné smysluplně analyzovat bez pomoci počítačů. Stejné prostředí současně umožňuje relativně snadno získat externí data k analýze bez nutnosti je všechna speciálně pro tento účel zaznamenávat vlastními prostředky. Daty vhodnými k analýze disponují firmy i v rámci svých počítačových systémů. Je zřejmé, že čím větší část firemních procesů probíhá elektronicky, tím větší množství dat vhodných pro počítačové zpracování má firma k dispozici. Podnikání, ve kterém jsou stěžejní procesy realizovány elektronicky zejména pomocí internetu, se označuje pojmem elektronické podnikání (e-business). Jsou-li těmito procesy řešeny obchodní vztahy, používá se pojem
1
e-komerce[4]1. Protože společnosti pohybující se v těchto oblastech mívají k dispozici záznam jakékoliv komunikace se svými potenciálními či skutečnými zákazníky v elektronické formě, mají tím rovněž data použitelná pro další zpracování a analýzu bez dodatečných nákladů na jejich pořízení. Tato data lze pak vyhodnocovat například za účelem odhadu budoucího chování zákazníka a posouzení jeho hodnoty pro dosažení firemních cílů. Definice cílů je nezbytná pro samotný proces učení. Pokud nebude znám cíl snahy, nelze ani stanovit, jaká data jakým způsobem má učící algoritmus zpracovávat. Cílem může být prakticky cokoliv, ale obvykle souvisí se zlepšením ekonomických ukazatelů (chci více objednávek!), předvídání nějaké události (kdy bude třeba objednat nové zásoby?) nebo zlepšení nabídky služeb (čeho zákazník vyznačující se tímto chováním chce pravděpodobně dosáhnout?). Konečně závěrečný bod představuje racionální pohled business sféry, kde konkurenční prostředí je motivací pro získání konkurenční výhody. Společnosti využívající strojové učení mají spíše předpoklady objevit skryté souvislosti v historických datech, automatizovat své firemní procesy nebo lépe cílit své nabídky a zvýšit úspěšnosti prodeje.
1 Současně je třeba podotknout, že vymezení těchto pojmů nevychází z žádného standardu a jsou běžně vzájemně zaměňovány či oblasti jejich působnosti zpřesňovány jinými pojmy nebo vykládány odlišně (např. e-komerce úzce jen pro B2C v [4] nebo mnohem širší definice a to nejen hierarchicky v [5]). Protože pro popis metod není striktní vymezení oblasti důležité a ty naopak nachází své uplatnění napříč celým elektronickým podnikáním, bude dále upřednostněn volnější výklad termínu e-komerce.
2
2
Cíl a metodika práce Cílem práce je představit strojové učení a nastínit jeho potenciál pro oblast e-komerce
za pomoci popisu scénářů jeho nasazení. Pro tento účel bude nejdříve vysvětleno, co se pod pojmem strojové učení skrývá a kde se s ním lze běžně setkat. Dále budou vymezeny některé teoretické pojmy, které se v dalších kapitolách při výkladu použijí. Vždy při zavedení nového pojmu ho doplní i jeho anglický přepis pro snazší dohledání podrobnějších informací v cizojazyčné literatuře. Následovat bude popis vybraných metod a algoritmů v takové podobě, aby čtenář získal přehled o teoretických základech a při aplikaci strojového učení na jím řešené problémy věděl jak postupovat. Protože různých algoritmů se dnes používá řádově desítky, popsány budou jen ty nejznámější a jen v míře dostatečné pro intuitivní pochopení problematiky. Po seznámení s nezbytnou teorií přijdou na řadu scénáře popisující možné aplikace strojového učení ve vybrané oblasti e-komerce. Scénáře nemají za úkol pokrýt všechna možná potenciální využití. Jejich smyslem bude inspirovat k hledání dalších způsobů, jak zužitkovat nabyté znalosti. Některé scénáře budou dotaženy do podoby demonstrační aplikace s představením použitých nástrojů a návodným popisem, jak při takové implementaci postupovat.
3
3
Popis použitých metod Problémy řešitelné aplikací strojového učení se vyskytují prakticky ve všech oblastech
lidské činnosti. Formalizací popisu problémů se obvykle dá dojít k nějakému obecnému prototypu řešení, a tím předejít znovuobjevování kola při každé aplikaci.[6] Příklady takového zobecnění jsou klasifikace nebo regrese. V této práci bude obecný prototyp nazýván typovou úlohou. Aplikace strojového učení na velké databáze za účelem objevení skrytých vlastností je jednou z metod oblasti nazývané dolování dat.[7] Jejím úkolem je z velkého množství vstupních dat získat informace v pro člověka pochopitelné formě často s využitím statistických metod. Důležitou vlastností strojového učení je schopnost odvodit i zcela nové informace a vztahy, které by při použití explicitně definovaného algoritmu zůstaly skryty, protože nebyly při jeho tvorbě zvažovány. Strojové učení není pouze metodou pro zpracování dat, ale je i součástí umělé inteligence. Inteligentní systémy se schopností učit se a přizpůsobovat se změnám prostředí, se kterými autor původně nepočítal, nepotřebují obsahovat scénáře na všechny možné situace, jež mohou při jejich činnosti nastat. Díky tomu zvládají nejen zpracovávat data a zprostředkovávat informace, ale v omezené míře i získávat znalosti a zkušenosti2. Nejde však o schopnosti srovnatelné s lidskými, protože tyto znalosti nejsou dostatečně abstraktní a nejsou převoditelné na odlišné situace. Významným okruhem nasazení strojového učení je i rozpoznávání vzorů (pattern recognition). Oblíbeným příkladem používaným autory literatury zabývající se strojovým učením jsou obrazová data, na kterých se strojově rozpoznávají konkrétní objekty na fotografiích
(např. obličeje,
auta atd.),
párují
odlišné
záběry
na stejný
objekt
nebo vyhledávají vzhledově podobné snímky. Některé známé aplikace strojového učení jsou uvedeny v Tabulka 1. Protože strojové učení lze aplikovat na široké spektrum problémů, při výběru vhodné metody je prvotním úkolem z popisu zadání určit typovou úlohu, na níž lze problém převést. Teprve poté přichází na řadu výběr vhodného algoritmu pro tvorbu modelu, který bude použit pro splnění úkolu.
2 Data slouží k popisování reality, informace přidávají datům význam a strukturu a informují o změnách v datech. Znalosti vedou k vykonání nějaké cílevědomé činnosti na základě dostupných informací.[4]
4
Aplikace Ranking
příklad Tvorba index webových stránek pro vyhledávací služby. (Google)
Collaborative filtering
Nabídka položek, které by mohly uživatele zajímat, protože o ně projevil zájem jiný uživatel s podobným profilem. (Amazon, Netflix)
Automatic translation
Automatický překlad mezi různými jazyky. (Google Translate API)
Classification problem
Rozhodnutí, zda email je nebo není spam. (Google Mail, Spam Assasin)
Named entity recognition
Extrakce metadat z dokumentu, například adresy z emailu. (Apple Mail)
Speech recognition
Přepis mluveného slova do písemné podoby. (YouTube)
Similiarity learning
Automatické seskupení zpráv z různých webových magazínů podle společného tématu. (Google News)
Data mining
Objevování skrytých vztahů z provozních systémů podniku (aplikace pro ETL).
Pattern recognition
Rozpoznání obličeje na fotografii. (Facebook)
Tabulka 1: Příklady aplikací strojového učení (částečně podle [6])
Model je definován algoritmem a jeho parametry, jejichž hodnoty jsou při procesu učení optimalizovány. Pro každý typ úloh jsou k dispozici odlišné učící algoritmy lišící se výpočetní náročností, rychlostí zpracování dat, rychlostí a přesností vzniklého modelu. Dobře vytvořený model sestavený za účelem predikce nebo klasifikace by aplikací na nová data měl poskytovat obdobně přesné výsledky jako nad učícími historickými daty. Alternativně může být model vytvořen pro získávání znalostí z historických dat.
Ilustrace 1: Aplikace strojového učení
5
Typové úlohy se obvykle rozdělují podle toho, zda jsou pro historická data k dispozici jejich správná ohodnocení, případně podle schopnosti plánovat akce a posuzovat jejich dopady na prostředí a pravděpodobnost dosažení stanoveného cíle na: •
učení s učitelem (supervised learning) ◦ regrese (regression) ◦ klasifikace (classification) ◦ hledání podobností (similarity learning)
•
učení bez učitele (unsupervised learning) ◦ shluková analýza (clustering)
•
učení posilováním (reinforcement learning)
Často bývá problematická doména chápána jako samostatná oblast nasazení strojového učení a ve vývojových nástrojích pro ni existuje specifická podpora. I v těchto případech je ale každá oblast nasazení řešena za pomoci formulace jednoho či více typových úloh, přičemž v rámci typové úlohy mohou být použity odlišné učící algoritmy. Některé takové oblasti nasazení uvádí Tabulka 2. Tyto příklady vyplynou při tvorbě systému doporučení nabízejícího zákazníkovi seznam produktů, které jsou pro něj potenciálně zajímavé (recommendation systems). Vhodné produkty mohou být identifikovány podle podobnosti s těmi prohlíženými v minulosti (content-based filtering). Nebo mohou vycházet z profilu zákazníka a pro výběr vhodných nabídek využít podobnost s jiným profilem a předpokladu, že se těmto zákazníkům líbí obdobné věci (collaborative filtering). I takto jednoduše formulované zadání se tedy dotýká hned dvou oblastí nasazení strojového učení. Navíc se přibližuje oblasti třetí, kde by se seznam doporučení tvořil na základě historie nákupů (market basket analysis) a vycházelo z předpokladu, že když zákazníci v minulosti nakupovali tytéž položky v kombinaci s jinými, ten současný bude pravděpodobněji ochoten obdobné kombinace nakoupit také (cross selling). Analýzy poté nemusí sloužit k pouhému doporučení produktů ale i vytváření prodejních setů obsahujících často kombinované produkty
za zvýhodněných
podmínek
nebo inteligentnímu
aranžování
produktů
v marketingových materiálech. Všechny vyjmenované oblasti nasazení lze vnímat jako specifickou doménu. Přestože jde o typové úlohy hledání podobností a seskupování, existují specializované nástroje usnadňující na ně aplikaci strojového učení. 6
Oblast
Příklad
Content-based learning
Zákazník si po sobě prohlédl tři červené míče: má smysl mu nabídnout zrychlenou volbu na další vzhledově či jinými parametry podobné produkty.
Collaborative filtering
Zákazník ohodnotil několik produktů. Pokud v databázi existuje jiný zákazník, se kterým se v hodnocení silně shoduje, mají pravděpodobně stejný vkus. Má smysl jim tedy křížově nabízet to, co se druhému líbilo.
Market basket analysis
Zákazník vhodil do košíku jím vybrané produkty. Z historických
(frequent item set mining) objednávek vyplývá, že tyto produkty jsou velmi často kombinovány s jiným. Proto má smysl tento zákazníkovi dodatečně nabídnout. Tabulka 2: Příklady oblastí strojového učení dotýkající se problematiky doporučení zákazníkovi
Pokud je identifikována typová úloha pro řešení zadaného problému, přichází na řadu výběr učícího algoritmu pro model z těch, které jsou pro ni dostupné. Obecně lze prohlásit, že pro žádnou neexistuje univerzálně nejlepší učící algoritmus použitelný pro jakýkoliv problém. Vždy je nutné z dostupných algoritmů vybírat s ohledem na konkrétní data, která mají být zpracovávána. Na druhou stranu i nevhodně zvolený algoritmus bude při správné aplikaci vracet použitelné výsledky, jen mohou nastat výkonnostní problémy nebo se špatná volba projeví na menší přesnosti modelu. Některé algoritmy umožňují stanovit parametry modelu analyticky pomocí přímých výpočtů a ne jen nepřímými metodami, kterými jsou parametry aproximovány pomocí iterativních výpočtů. Analytický způsob je vhodný pouze pro malé objemy dat a vyžaduje je mít
všechna
k dispozici
před zahájením
výpočtu,
současně
je
více
náchylný
vůči nepřesnostem vzniklým zaokrouhlováním. V aproximačních úlohách se pro získání vektoru
parametrů často používá metoda nejmenších čtverců3, přičemž pro strojové
zpracování je upřednostňován postup založený na inverzní matici získané pomocí determinantu matice dat. Protože s počtem záznamů roste pravděpodobnost, že data budou tvořit singulární matici4, roste tím také pravděpodobnost, že nebude možné tento postup aplikovat. Ze všech těchto důvodů se v procesu učení více uplatňují iterativní metody.[8] 3 Aproximace parametrů při interpolaci polynomem
θ=( X T X)−1 X T y
4 Pokud jsou některé vektory tvořící matici lineárně závislé, její determinant je nulový (singulární matice) a nelze tedy s jeho pomocí získat inverzní matici.
7
Typová úloha Atributy X Výstup Y Predikce
Korelace
Doporučená technika
Numerické Numerické Stabilní/lineární
Lineární regrese
Kategorie
Lineární regrese,
Numerické
neuronové sítě Numerické Numerické Nestabilní/silně nelineární Neuronové sítě Klasifikace
Numerické Kategorie
Stabilní/lineární
Numerické Kategorie
Nestabilní/silně nelineární SVM
Kategorie
Kategorie
Logistická regrese SVM, Naive Bayes, jiné pravděpodobnostní grafické modely
Tabulka 3: Příklady doporučených algoritmů podle typu úloh a parametrů[9]
Data mají obvykle formát tabulky, skupiny položek nebo časových řad[10]. Atributy definující jednotlivé dokumenty mohou být typu[7]5: •
Numerické spojité
•
Numerické diskrétní
•
Kategorie (setříděné nebo nesetříděné) Dokumenty jsou pro zpracování převedeny do podoby vektoru, kdy dimenze vektoru
odpovídá počtu atributů, které tvoří popis zjistitelných vlastností dokumentu. Při výběru atributů zahrnutých do popisu dokumentu proti sobě stojí snaha o co nejkompletnější popis na jedné straně a výpočetní nároky při použití velkého množství atributů na straně druhé. S jejich počtem rostou nároky na zpracování zejména procesu optimalizace modelu. Proto existují metody, jak z identifikovatelných atributů vybrat pouze ty, jež jsou při dalším zpracování přínosné (features selection). Zpracování dat může být provedeno v několika režimech[7]: •
dávkově: všechny prvky jsou použity najednou pro vypočtení parametrů hypotézy h
•
iteračně: všechny prvky jsou použity pro iterativní optimalizaci parametrů hypotézy h
•
inkrementálně: prvky jsou zpracovávány po jednom a každé zpracování ovlivňuje parametry hypotézy h
5 Datový typ Boolean může být podle potřeby reprezentován buď jako diskrétní hodnota nebo kategorie.
8
3.1
Učení s učitelem Učení s učitelem zahrnuje případy, kdy pro historická data jsou známy „správné”
odpovědi, podle kterých se použitý algoritmus může učit. Správné odpovědi mohou být přiřazeny lidským expertem z daného oboru nebo pocházet ze zaznamenaných událostí, jež jsou s konkrétními daty spjaty. Například informací o provedení objednávky. Postup iterativního učení s učitelem se skládá z kroků: 1. získání historických dat a jejich případná transformace na vektory atributů (input vectors)6 2. rozdělení dat na trénovací (training set) a kontrolní množinu (validation set) 3. stanovení
obecné
hypotézy hθ (podle typu
úlohy
nazývá
function estimator
nebo classifier) nad vstupními atributy x (threshold) 4. fáze učení: optimalizace parametrů θi (weights) hypotézy nad testovacími daty a měřením přesnosti na kontrolní skupině (cross validation). 5. ověření přesnosti optimalizované hypotézy nad testovacími daty (test set) Z datového zdroje je vhodné načítat selektivně jen to, co má pro další zpracování svůj význam. Pokud nemají být zpracovány všechny záznamy v datech, výběr vzorků (sampling) musí být proveden tak, aby zachoval vlastnosti celé populace. Načtená data je poté vhodné transformovat. V závislosti na konkrétním případě mohou být například odstraněny neúplné záznamy, kde chybí hodnoty důležité pro následné zpracování. Údaje je často vhodné převést na čísla stejného řádu a stejné měřítko. Identifikované textové atributy je obvykle nutné převést na diskrétní číselné hodnoty. Například je-li atributem textové vyjádření s výčtem možností {„žádné“,„malé“,„velké“}, převedou se hodnoty atributu na prvky množiny {0,1,2}. Někdy se ukáže jako vhodné vytvořit nový atribut z kombinací více existujících a v následném procesu učení pracovat s ním. Příkladem může být převedení rozměrů balení expedovaného zboží na jeho objem nebo kategorizaci převzatou od přepravní služby. Data, která jsou k dispozici pro proces učení, se rozdělí do více částí. První vzorek (training set) slouží pro samotný proces učení, druhý (validation set) pak pro zjištění úspěšnosti testované hypotézy s učením získanými parametry. A nakonec pro ověření 6 Pro označení těchto vektorů se v anglické literatuře používají různé pojmy (input vector, pattern vector, feature vector, sample, example) a pro označení atributů představujících vlastnosti je situace obdobná (features, attributes, input variables, components).[7]
9
přesnosti získaného modelu se vyčleňuje ještě třetí od procesu učení zcela nezávislý vzorek dat (test set). Důležité je, aby rozdělení dat mezi vzorky bylo zcela náhodné. Pro měření přesnosti může být jako měřítko použita směrodatná odchylka (mean square error) nebo prostý počet chyb.[7] Při tvorbě modelu je třeba se vypořádat s potřebou určité generalizace a ohlídat riziko přeučení (overfitting). K němu dochází v případech, kdy se díky komplexnímu modelu (například kvůli polynomu vysokého řádu u funkce hypotézy nebo příliš atributy zahrnutými do modelu) nalezne řešení příliš přizpůsobené testovacímu vzorku a na jiných datech selhávající. Pro nalezení obecnějšího popisu dat je obvykle určitá míra chybovosti (bias) v testované hypotéze nezbytná[7] a vždy je vhodnější použít jednodušší model s ještě uspokojivými výsledky než komplikovaný model přespříliš přizpůsobený učícím datům. Nakonec i učící data nemusí být bezchybná a mohou obsahovat takzvaný šum (noise). Posoudit smysluplnost zobecnění (inductive bias) je jeden z hlavních úkolů tvůrce modelu. K přeučení může rovněž docházet při nepoměru složitosti modelu a množství učících dat. Pokud model nelze z odůvodnitelných důvodů zjednodušit, je třeba navýšit množství dat pro zreálnění výsledků. Pomoci může i takzvaná regularizace, která do procesu učení zanáší penalizaci za komplexnost modelu. Regularizace rovněž pomáhá řešit problém korelace vstupních atributů.[2] Opačný problém představuje podučení (underfitting), kdy je zvolený model příliš jednoduchý a nepřesnost aproximace měřená odchylkami od správných hodnot příliš vysoká. V těchto případech může být řešením zahrnout do modelu více atributů představujících nezávislé proměnné nebo hypotézu formulovat pomocí polynomu vyššího řádu. Př: Model
hθ (x )=θ0 +θ 1 x 1 trpí podučením, proto
1. přidá se další atribut
hθ (x )=θ0 +θ 1 x 1+ θ2 x 2
2. použije polynom vyššího řádu 3. nebo kombinace obojího
hθ (x )=θ0 +θ 1 x 1+ θ2 x 21
hθ (x )=θ0 +θ 1 x 1+ θ2 x 22
Na konci procesu je model v podobě hypotézy h převádějící vstupní data na predikci (mapuje x’ na y’). Typickými úlohami strojového učení s učitelem jsou předpovědi spojité hodnoty nebo třídy. Protože jednotlivé modely sami o sobě nemusí dosahovat požadované přesnosti, někdy se používají techniky pro seskupení více modelů v jeden silnější (ensemble learning). Tento krok vychází z úvahy, že každý jeden samostatný model má své slabiny, které lze eliminovat 10
kombinací výsledků s modely jinými. Konečným výsledkem by pak měla být nižší průměrná chybovost. Jednotlivé techniky se liší způsobem kombinace dílčích výsledků, přičemž některé zvyšují problém přeučení a jiné ho naopak eliminují. Příkladem technik pro seskupení modelů jsou boosting, bagging, stacking atd.[11] Boosting kombinuje modely pomocí váženého průměru, čímž dosahuje menší chyby, ale také je náchylnější k přeučení. Váha jednotlivých modelů je pevně určena autorem modelu (například empiricky). Technika stacking rovněž kombinuje modely a přikládá jim odlišnou váhu, ale její rozložení je navíc samo předmětem procesu strojového učení. [11] Další z často používaných technik je bagging7. Tou je obcházen potenciální problém, kdy malá změna v datech dokáže výrazně ovlivnit závěry nedokonalých modelů. Jednotlivé dílčí modely se mohou vzájemně lišit v použitém algoritmu, ale především se učí nad různými vzorky dat generovanými náhodným výběrem s navracením ze všech učících dat. Dílčí metody pak o výsledku hlasují rovným hlasem. Takto zprůměrované výsledky pak dávají mnohem stabilnější výstup s menší standardní odchylkou než výsledky získané kterýmkoliv jedním z nich. Technika bagging tak patří mezi ty, jež pomáhají řešit problém přeučení. Na Ilustrace 2 je vyobrazen princip, na kterém technika bagging pracuje. Šedivé křivky představují dílčí modely, červený potom výsledný. Dílčí modely mohou být silně ovlivněny extrémními hodnotami, ale při hlasování jsou jejich závěry korigovány většinou hlasů.
Ilustrace 2: Ukázka stabilizace výsledků technikou Bagging[12] 7 Někdy též nazývána jako bootstrap aggregation
11
3.1.1
Lineární regrese
Regresní analýza se zabývá odhadem spojité hodnoty. Pokud jsou data analyzována na základě časové dimenze, jde o oblast nasazení označovanou pojmem předpovídání (forecasting). Někdy se také používá pro její pojmenování pojem analýza časových řad.[4] Existující pozorování zahrnují vzorky představované dvojicí (x,f(x)), kde x je vstupní hodnota a f(x) je výstup získaný aplikací nějaké funkce na vstupní hodnotu. Protože funkce f je neznámá, úkolem učení je najít funkci h, která ji aproximuje. Této aproximační funkci pak říkáme hypotéza.[13]
Ilustrace 3: Model regresní analýzy[14]
Při regresní analýze jsou k dispozici historická data (learning set) ve formě hodnot atributů a k nim vztažené výstupní hodnoty. Hodnoty atributů mohou mít na vstupu různou podobu, pro další zpracování ale musí být převedeny na čísla. Pomocí zvolených atributů se sestaví hypotéza, což je aproximační funkce vyjádřená lineární kombinací vektorů. Pokud je pro hypotézu použit polynom vyššího řádu, opět musí být rozepsaný na lineární kombinaci vektorů. Při výběru atributů a hypotézy je vhodné usilovat o co nejjednodušší vyjádření, které ještě splňuje požadavky kladené na přesnost aproximace (tzv. Occamova břitva). Větší množství atributů nevede automaticky k lepším výsledkům, současně má negativní vliv na výpočetní náročnost procesu učení. Zvyšuje také riziko přeučení (overfitting), kdy hypotéza příliš věrně popisuje trénovací data[14]. Například u dat vyjadřujících přímou úměrnost zatíženou šumem s rozptylem podle normálního rozdělení není vhodné použít polynom vyššího řádu, ale upřednostnit prostou lineární funkci. Přestože polynom by mohl na testovacích datech dosahovat vyšší přesnosti aproximace. Naopak nedostatečné množství atributů má za následek větší nepřesnosti v predikci. Při stanovení optimálního počtu je vhodné eliminovat vzájemné závislosti mezi atributy[15]. 12
Zvolené atributy představují nezávislé proměnné a v matematickém vyjádření funkce hypotézy jsou obvykle značeny jako X. Naměřené nebo předpovídané hodnoty jsou potom závislé proměnné značené Y. Nejjednodušší formu zápisu hypotézy představuje funkce přímky hθ (x )=θ0 +θ 1 x , tedy funkce pracující s jediným rozměrem představovaným atributem X. Při více atributech a pouze jedné vysvětlované hodnotě má hypotéza lineární regrese podobu hθ (x )=θ0 +θ 1 x 1+ θ2 x 2 +... . Pro sestavení je znám vektor atributů x. Atributy je nutné převést na podobný rozsah (feature scaling), tedy zabránit aby například jeden byl v řádu desetitisíců a jiný jen v řádu jednotek. Převedení se provede prostým vydělením (případně vynásobením) skutečných hodnot atributu, přičemž jako dělitele lze použít maximální hodnotu, které atribut nabývá. Operace se provede identicky nad stejným atributem u všech dat. Z výkonnostních důvodů je vhodné před touto operací provést ještě normalizaci hodnot (mean normalization) spočívající v odečtení průměrné hodnoty atributu od jeho skutečné hodnoty. Tím je zajištěno rozptýlení pracovních hodnot atributu kolem čísla nula. Vhodný výsledný rozsah závisí vždy na konkrétních datech, ale typicky jím může být například interval <−1 , 1> .[14] Řešeným problémem je nalézt takové hodnoty θ, aby model představovaný hypotézou dával při predikci co nejlepší výsledky. Přesnost je odvozena od zvolené metriky, kterou je obvykle
metoda nejmenších čtverců počítající rozdíly mezi predikovanými a skutečnými
hodnotami.
Optimální
hodnoty
lze
vypočítat
řešením
rovnice: θ=( X T X)−1 X T y .
Asymptotická složitost takového výpočtu je ovšem O(n3 ) a je tedy při velkém objemu dat nepoužitelný[14]. Proto se pro optimalizaci hodnot atributů θ používají spíše iterativní metody, například algoritmus Gradient Descent nebo Newtonova metoda. Gradient Descent
Newtonova metoda
Směřuje vždy tam, kde je největší změna.
Směřuje vždy přímo k minimu.
Používá první derivace kvadrátu odchylek.
Používá první i druhé derivace kvadrátu odchylek => výpočetně náročnější.
Výkonná, pokud je počáteční bod vzdálen
Výkonná, pokud je počáteční bod blízko
od hledaného minima.
minimu.
Tabulka 4: Srovnání iterativních metod[8]
13
3.1.1.1
Gradient descent8
V každém kroku se hledají takové hodnoty, které vedou k největšímu zlepšení predikce. Slabinou algoritmu je nalezení takzvaného lokálního minima. Tedy hodnot, které sice dávají lepší výsledky než nejbližší alternativy, ale bez záruky, že někde jinde neexistuje lepší řešení. Použití algoritmu rovněž stěžuje nutnost zvolit velikost kroku α, který představuje rychlost učení (learning rate). Při malé α je algoritmus pomalý a k nalezení minima potřebuje provést více iterací. Naopak při velké hodnotě α hrozí riziko přestřelení, kdy algoritmus nemusí konvergovat k minimu. Velikostí kroku α se pak opakovaně pro každý atribut násobí jeho parciální derivace hodnotící funkce J (cost function) a o výsledek mění testovaná hodnota atributu. Iterace se provádí pro každý atribut do té doby, dokud výsledky hodnotící funkce J konvergují k minimu. Dosažení lokálního minima se pozná tak, že parciální derivace funkce J podle všech atributů se rovnají nule. Hodnotící funkce J pro množinu dat s prvky 1 až m a atributy θ0 až θn má podobu: m
J (θ0 , θ1 ,... , θn )=
1 (hθ ( x (i) )− y (i))2 ∑ 2m i=1
Hodnotící funkce vyjadřuje sumu kvadrátu všech odchylek (residuals, fitting errors) v predikci hypotézou h0
od správných hodnot. Pro zjednodušení práce s čísly menších řádů
se v tomto případě vše ještě zprůměruje a vydělí dvěma. Protože cílem je minimalizace hodnot, je algoritmem gradient descent opakovaně prováděna operace: opakovat dokud konverguje { simultánně pro j od 0 do n {
θ j :=θ j−α
∂ J (θ0, θ1, ... , θn ) ∂θj
} }
Algoritmus konverguje, dokud se zmenšuje odchylka vypočtená pomocí hodnotící funkce J(θ). Simultánností se rozumí, že v rámci jedné iterace jsou v hodnotící funkci J zachovány hodnoty z předchozí iterace neovlivněné právě počítanými změnami: změna θ0 pak ve stejné iteraci neovlivní výpočet hodnoty θ1 . Hodnotící funkce může navíc zahrnovat regularizační parametr, který má za cíl vyhladit její průběh a zabránit tak přeučení. Jednou z možných podob podle [14] je: 8 Kapitola zpracována podle [14]
14
m
J (θ0 , θ1 ,... , θn )=
n
1 ∑ (h ( x (i) )− y (i))2 + λ ∑ θ 2j 2m i=1 θ j=1
Velikost regularizačního parametru λ ovlivňuje míru vyhlazení a při velké hodnotě může vést až k opačnému problému, tedy podučení. V algoritmu gradient descent se regularizační parametr nepřidává při výpočtu parametru θ0 , ale až pro další hodnoty. 3.1.2
Klasifikace
Při klasifikaci jsou k dispozici učící ohodnocená data. Cílem učení je najít pravidlo, podle kterého jsou prvky rozřazeny. Výstupem procesu je vždy nějaká diskrétní hodnota. Může to být 1 nebo 0 ve významu ANO a NE, stejně tak to mohou být hodnoty z libovolné diskrétní množiny (např. {„červená”, „modrá”, „bílá”}). Podmnožinou klasifikace je pravděpodobnostní klasifikace, kdy na výstupu není definitivní přiřazení jedné třídě, ale jsou udány pravděpodobnosti pro všechny třídy. Proces klasifikace má dvě fáze: 1. fázi učení nad vzorkem, který má přiřazeny správné třídy a vytvoření modelu 2. klasifikace vstupních dat modelem Klasifikační test může vycházet z jediné hypotézy postavené nad pozitivními příklady, která vše ostatní považuje za příklady negativní. V některých případech mají obě skupiny svou rozpoznatelnou strukturu a je potom žádoucí formulovat pro negativní příklady vlastní hypotézu. Výhodou takového přístupu je, že pokud klasifikovaný prvek nevyhovuje ani jedné třídě, může být pro obě zamítnut.[2] Existuje více typů klasifikace: •
unární klasifikace (one-class classification)
•
binární klasifikace (binary classification)
•
klasifikace do více oddělených tříd (multi-class classification)
•
štítkování (multi-label classification) Při binární klasifikaci se klasifikátor rozhoduje mezi dvěma třídami. Učící data jsou
ohodnocením rozdělena na pozitivní a negativní příklady. Unární klasifikace se od binární odlišuje tím, že učící data zahrnují pouze data jedné třídy. Klasifikátor má za úkol v nových datech pouze rozhodnout, zda jsou nebo nejsou dané třídy. Rozhodnutí o náležitosti k třídě je pak redukováno na test, zda vstupní hodnoty dávají na výstup modelu jedničku nebo nulu. Taková klasifikace nachází své využití například v oblasti detekci anomálií. 15
Při složitější klasifikaci mezi více tříd jsou učící data hodnocením rozdělena mezi všechny tyto třídy. Rozlišují se dva případy: zda jde o rozdělení dat mezi nezávislé třídy nebo štítkování. V prvním případě je každý prvek označen právě jednou třídou, ve druhém jich může mít více. Při trénování rozřazení prvků do nezávislých množin se používají různé strategie: •
nejdříve získat binární klasifikátory a následně zkombinovat jejich výsledky
•
klasifikaci provést najednou na základě aposteriorní9 pravděpodobnosti Pro kombinaci binárních klasifikátorů je jednou z nejjednodušších metod metoda
One-vs-All[16]. Pro každou třídu se při ní učí samostatný binární klasifikátor tak, že prvky všech ostatních tříd se považují za druhou spojenou třídu. Při rozhodování o třídě nového prvku se potom zvolí ta, jejíž klasifikátor udává největší pravděpodobnost. Scénář
Klasifikace
Je příchozí email spam?
Úloha
binární
Je konkrétní komentář u produktu pozitivní, negativní více tříd
analýza sentimentu
nebo neutrální? Vytipovat podezřelou objednávku.
unární
detekce anomálií
Tabulka 5: Příklady klasifikačních úloh
V Tabulka 5 se pro některé scénáře vyskytují ještě upřesňující názvy úlohy, jakými jsou například analýza sentimentu nebo detekce anomálií. Ty tvoří v rámci klasifikační metody specifické úlohy. Analýzu sentimentu lze řešit běžnými klasifikačními algoritmy (naivní bayesovský klasifikátor atd.), ale protože předmětem analýzy jsou písemně vyjádřené lidské pocity, výsledky analýzy jsou obtížně uchopitelné. Sentiment a především způsob jeho vyjádření i vnímání je silně subjektivní pro každého lidského jedince. Při hodnocení nepanuje jednoznačná shoda ani pokud ho provádí skupina lidí[17], natož má-li se jednat o vyhodnocení strojové. Speciálně při analýze sentimentu se jako větší problémy
jeví mnohovýznamnost
větných spojení, neznalost kontextu nebo problém vztažení vyjádřeného sentimentu ke správnému předmětu. Některé metody založené čistě na slovníku negativních a pozitivních slov nebo slovních spojení dávají jednotné hodnocení celému textu, ačkoliv v něm může 9 Apriorní pravděpodobnost p(θ) je pravděpodobnost pro parametry, které jsou známy předem. Aposteriorní pravděpodobnost p(θ|x) pro parametry odvozené až z dat.
16
figurovat více potenciálních předmětů analýzy a vyjádřený sentiment bude odvozen pouze od jednoho z nich. Tyto problémy je potřeba zohlednit a pracovat s nimi. Například analýza sentimentu zaměřená na firemní značku bude dávat pravděpodobně přesnější výsledky na data pocházející ze zdroje zaměřeného čistě na tuto značku (např. Facebook profil) než napříč obecnými zdroji (např. obsah ze služby Twitter fulltextem dohledaný podle názvu značky). Přesnost odhadu také ovlivní délka analyzovaného textu, proto přesnější výsledky bude mít analýza zápisků na blogu nebo recenzí v magazínech než krátkých tweetů. Stejně tak je třeba zohlednit časovou nestálost sentimentu a v případě hodnocení v delším časovém úseku pracovat s časovou řadou a nikoliv sumarizovanými údaji. Jinou specifickou úlohou je detekce anomálií v datech. Anomálie je něco, co se vymyká běžným hodnotám, proto klasifikátor nelze na žádných historických datech naučit co je a co není anomálie. Příklad z Tabulka 5 se zaměřuje na hledání z podvodu podezřelých objednávek: pokud objednávající na internetovém obchodě nevyplnil na sebe platný telefonní kontakt, zaplatil kartou předem a chce zboží doručit s adresou převzetí mimo své bydliště (např. benzínová pumpa), kombinace všech těchto charakteristik se silně vymyká běžnému průměru a měla by být klasifikátorem označena za anomální. Pro klasifikaci obecně lze použít více algoritmů s odlišnými vlastnostmi: •
Naivní bayesovský klasifikátor (naive bayes)
•
Bayesovské sítě (Bayesian network)
•
Metoda nejbližších sousedů (nearest neighbour)
•
Logistická regrese (logistic regression)
•
Rozhodovací stromy (decision tree)
•
SVM (support vector machine)
•
Neuronové sítě (Neural network) a mnohé další...
3.1.2.1
Naivní bayesovský model10
Při použití tohoto algoritmu naive bayes se předpokládá, že jednotlivé atributy popisující dokument jsou na sobě zcela nezávislé - proto je v názvu slovo „naivní“. Takové zjednodušení je nezbytné především z výkonnostních důvodů, aby nebylo nutné zahrnout pravděpodobnosti pro všechny kombinace atributů (tedy pro n binárních atributů 2n hodnot 10 Kapitola zpracována podle [10]
17
pravděpodobností). Pro rozhodnutí, která hypotéza je nejpravděpodobnější, slouží bayesovský vztah: p(hypotéza | pozorování )=
p( pozorování | hypotéza)∗p (hypotéza) p( pozorování )
S jeho pomocí se postupně vypočítá pravděpodobnost všech hypotéz a vybere ta, která dopadla nejlépe. Jednotlivé hodnoty pravděpodobnosti potřebné pro dosazení jsou získány z analyzovaných dat. Protože se hledá pouze nejlepší hypotéza a není potřeba znát přesné výsledky, lze výpočet zjednodušit ignorováním jmenovatele ve zlomku, který je pro všechny případy stejný. Algoritmus nepotřebuje prohledávat prostor hypotéz, ale vystačí s výpočtem příslušné pravděpodobnosti na základě četnosti výskytů hodnot jednotlivých atributů a hodí se proto pro velké datové soubory. Přestože předpoklad podmíněné nezávislosti atributů bývá jen málokdy splněn, vykazuje naivní bayesovský klasifikátor dobré výsledky ve smyslu úspěšnosti klasifikace. 3.1.2.2
Rozhodovací stromy
Rozhodovací strom je hierarchická datová struktura implementující strategii „rozděl a panuj“.[2] Model rozhodovacího stromu je tvořen uzly a hranami, které rozdělují data na menší podmnožiny. Dělení probíhá výběrem pomocí takového atributu, aby v každé vzniklé podmnožině převládala jedna třída. Obecný algoritmus dělení je podle [10]: 1. zvolit atribut jako kořen dílčího stromu 2. rozdělit data v tomto uzlu na podmnožiny podle hodnot zvoleného atributu a přidat uzel pro každou podmnožinu 3. existuje-li uzel, pro který nepatří všechna data do stejné třídy, opakovat pro něj celý postup, jinak zpracování ukončit Algoritmus rozhodovacích stromů má podle [3] několik výhod: ▪ rychleji se učí ▪ není potřeba upravovat vstupní data ▪ model je pochopitelný pro člověka a lze převést na soubor srozumitelných pravidel
18
Ilustrace 4: Ukázka klasifikace rozhodovacím stromem[2]
3.1.2.3
Logistická regrese11
Logistická regrese vychází z lineární regrese, tedy zahrnuje formulaci hypotézy h za pomoci atributů představujících vektor nezávislé proměnné x a vektoru jejich vah θ. Odlišnost spočívá v použití výstupu modelu pro binární klasifikaci. Pro tento účel slouží sigmoida pro vpasování funkce hypotézy do intervalu <0;1>, potom se pro binární klasifikaci použije výsledku bližší hodnota. Sigmoida současně zajistí konvexní průběh hodnotící funkce a umožní tak efektivně využívat algoritmus gradient descent pro získání optimálních atributů bez hrozby nalezení lokálního minima. hypotéza: hθ ( x )=g(θ T x) při sigmoida: g( z )=
1 1+ e−z m
1 (i) (i) hodnotící funkce: J (θ)= ∑ Cost (hθ (x ), y ) (nebo s regularizací) m i=1 při Cost (hθ ( x), y)=
{
−log(hθ ( x)) pro y=1 −log (1−hθ ( x )) pro y=0
11 Kapitola zpracována podle [14]
19
}
3.1.2.4
Klasifikace podle nejbližších sousedů
Binární klasifikační algoritmus nearest neighbour spočívá v přiřazení klasifikovaného vzorku dat stejné třídě, jakou má přiřazen jemu nejbližší vzorek v učících datech. Algoritmus lze modifikovat tak, aby při rozhodování zohlednil více než jeden nejbližší vzorek. Potom je třída přiřazena podle nejčetnějšího zastoupení v porovnávané skupině. Při volbě množství vztažených vzorků je vhodné dodržet lichý počet tak, aby ve skupině vždy jedna třída převažovala12. Doprovodná Ilustrace 5 zobrazuje dva klasifikátory: vlevo při použití jednoho nejbližšího vzorku a vpravo při zohlednění sedmi nejbližších vzorků. Ze znázornění je zřejmé, že více vzorků vyhlazuje průběh funkce a snižuje riziko přeučení a vliv náhodného šumu. S rostoucím počtem vztažených vzorků ovšem hrozí, že ostrost poklesne pod nežádoucí mez a současně rostou i výpočetní a paměťové nároky aplikace algoritmu[6], který obecně patří mezi ty s velkými nároky na paměť[7].
Ilustrace 5: Ukázka aplikace algoritmu Nearest Neighbour[6]
3.1.2.5
SVM13
Technika SVM (Support vector machine) je zvláště vhodná pro případy, kdy jsou data popsána velkým množstvím atributů. Cílem učící fáze je vytvořit model založený na tréninkových datech, který uspokojivě předpovídá výstupní hodnoty v testovacích datech. Princip spočívá v nalezení nadroviny, kde jsou učící data lineární separací rozdělena tak, aby prázdné okraje mezi krajními pozorováními byly co největší.[19] Technika umožňuje použít klasifikaci na data, kde vztah mezi třídou a atributy je nelineární pomocí mapování vstupní hodnoty do vyšší dimenze, ve které jsou již lineárně separovatelné (kernel trick). 12 Pohybujeme se nadále v binární klasifikaci, čímž je tento předpoklad zajištěn. Strategie klasifikace mezi více tříd za pomoci binárních klasifikátorů byla popsána v úvodu kapitoly 3.1.2. 13 Kapitola zpracována podle [18]
20
Doporučený postup aplikace algoritmu podle [18]: 1. transformovat data do formátu nástroje, který bude použit 2. škálovat data 3. vybrat kernel funkci, jejíž obecný tvar je
T K ( x i , x j )=Φ ( x i )Φ ( x j ) kde Φ je
mapovací funkce do vyšší dimenze 4. pomocí křížové validace (cross validation) najít nejlepší parametry kernel funkce. 5. nalezené parametry použít pro učení nad všemi testovacími daty 6. otestovat kvalitu modelu Vstupní data musí mít podobu vektoru reálných čísel. Pokud čísla představují kategorický údaj, bývá někdy doporučováno namísto řady celých čísel představujících jednotlivé kategorie použít více čísel pro binární reprezentaci kategorií (například {červená,zelená,modrá} nekódovat jako {1,2,3} ale {(0,0,1), (0,1,0), (1,0,0)}). Škálováním vstupních dat do podobného rozsahu se zabrání tomu, aby některé atributy dominovaly nad jinými a způsobovaly numerické problémy. Doporučený rozsah je například v intervalu [-1,1] nebo [0,1]. Škálování musí být pro stejný atribut jednotné napříč učícími i testovacími daty. Při volbě kernel funkce se jako základní tvary doporučují: •
lineární
K (x i , x j )=x iT x j tedy bez mapování do vyšší dimenze, je vhodná například
pro velké množství atributů •
polynomická
•
RBF
•
sigmoida
T
d
K (x i , x j )=(γ x i x j +r ) pro γ >0 2
K (x , y )=e−γ ∥x− y∥ pro γ >0
vhodná pro většinu případů
K (x , y )=tanh( γ x Ti x j +r )
Uváděné γ, r a d jsou parametry kernel funkce. Kromě nich se při optimalizaci hledá ještě parametr C představující trestné ohodnocení za chybně klasifikovaný prvek. Počet parametrů kernel funkce ovlivňuje výkonnostní nároky procesu optimalizace, proto třeba užití RBF namísto polynomické funkce kernelu představuje z tohoto pohledu výhodu, protože hledá pouze dvojice (C,γ). Při optimalizaci je třeba se vyvarovat problému přeučení, který je vyobrazen na Ilustrace 6.
21
Ilustrace 6: Problém přeučení při SVM klasifikaci[18]
3.2
Učení bez učitele Zatímco při učení s učitelem byly k dispozici ohodnocená učící data, pro učení
bez učitele nic takového neexistuje a proces si musí vystačit jen s vlastní analýzou vstupních dat za účelem hledání datových vzorů a struktur. Nejběžnější úlohou typickou pro učení bez učitele je seskupování (clustering) někdy nazývaný též jako shlukování nebo shluková analýza. Kromě ní existují i další úlohy (například blind signal separation), ale ty nebudou v dalším textu využity a jejich popisu nebude věnován další prostor.
22
3.2.1
Shluková analýza
Shlukování (seskupování) je rozklad množiny prvků na základě jejich vzájemné podobnosti na jednotlivé komponenty – shluky. Shlukování se podobá klasifikaci v tom, že na výstupu jsou nějaké komponenty, které se zde nazývají shluky a u klasifikace třídy. Rozdíl spočívá v existenci učících ohodnocených dat u klasifikace a jejich neexistenci u shlukování. Klasifikace tedy spadá pod strojové učení s učitelem, zatímco shlukování je učením bez učitele. Model vysvětlující data může být založen na statistickém nebo deterministickém přístupu. Statistický přístup vychází z analýzy hustoty dat, deterministický hledá jiné míry podobnosti[20]. Shlukováním lze získat shluky hierarchické nebo nehierarchické. Nehierarchické shluky jsou od sebe zcela odděleny a neexistují mezi nimi žádné průniky. Hierarchické shluky tvoří strukturu, kdy některé shluky jsou podmnožinou jiných. Tematickým příkladem hierarchického shlukování by mohla být analýza produktů, jejímž výstupem je stromová skupina kategorií využitelná pro vygenerování rozbalovací navigace na webové stránce. 3.2.1.1
Hierarchické shlukování
Při hierarchickém shlukování proběhne sekvence vnořených rozkladů, která má na jedné straně jednoprvkové shluky a na druhé jeden shluk obsahující všechny prvky. Postup shlukování může proběhnout v obou směrech a shlukování se pak nazývá buď aglomerativní nebo divizivní. V každém kroku aglomerativního shlukování se vyberou ty dva shluky, které jsou si nejpodobnější s ohledem na cíle aplikace a zvolenou metriku. Tyto dva shluky jsou sloučeny, čímž vzniká nový shluk.[21] Metrikou pro porovnání podobnosti shluků může být euklidovská vzdálenost ve vektorovém prostoru mezi všemi páry, které lze nakombinovat z center shluků, nebo metrika může využívat hustotu pravděpodobnosti.[7] Postup
divizivního
shlukování
spočívá
v
postupném
rozdělování
každého
z existujících shluků na dva nové tak, aby výsledný rozklad tohoto shluku byl optimální vzhledem k nějakému kritériu. Nalezení absolutně optimálního rozkladu množiny objektů na dvě podmnožiny však vyžaduje prozkoumání 2(n−1) −1 možností. Tento postup je prakticky proveditelný jen pro malý počet objektů.[21]
23
3.2.1.2
Nehierarchické shlukování
U nehierarchického shlukování (někdy též nazývaného rozdělující[20]) je třeba vyřešit problém optimálního počtu shluků. Některé algoritmy umí počet shluků přizpůsobovat průběžným hodnotám, jiné pracují s konstantním počtem. Počet shluků výrazně ovlivňuje kvalitu výstupu, stanovení příliš malého nebo naopak příliš velkého počtu může zcela znehodnotit výsledky. Pro stanovení optimálního počtu existuje více metod[21]. Typickými algoritmy nehierarchického shlukování jsou K-Means a EM algoritmus (expectation-maximization algorithm). K-Means je založený na vzdálenosti bodů od centra shluku a EM algoritmus využívá hustotu rozložení pravděpodobnosti. EM algoritmus dává obvykle lepší výsledky (příklad na Ilustrace 7), ale je výpočetně náročnější.
Different cluster analysis results on "mouse" data set: Original Data
k-Means Clustering
EM Clustering
0.9
0.9
0.9
0.8
0.8
0.8
0.7
0.7
0.7
0.6
0.6
0.6
0.5
0.5
0.5
0.4
0.4
0.4
0.3
0.3
0.3
0.2
0.2
0.2
0.1
0
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
1
0.1
0
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
1
0.1
0
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
1
Ilustrace 7: Shlukování algoritmy K-Means a EM[22] K-Means
Algoritmus pro seskupování pomocí hledání podobností mezi dokumenty. Při aplikaci algoritmu se postupuje tak, že v prvním kroku se náhodně vybere tolik bodů, kolik chceme získat skupin a tyto body jsou prohlášeny za středy (centra) skupin. V druhém kroku jsou všechny dosud nepřiřazené body zařazeny do skupiny, k jejímuž středu se nachází nejblíže. V dalších krocích se z bodů tvořících skupiny vždy přepočtou nová centra skupin a body jsou přeřazeny tam, ke kterému centru se nachází nejblíže. Centra skupin skrze k nim vztažené oblasti dělí prostor do Voroného diagramu. Postup se opakuje do té doby, dokud dochází k přeřazování bodů. Pro způsob měření vzdálenosti mezi centrem a body lze využít různé způsoby: nejen euklidovskou, ale například i manhatanskou (pravoúhlou) či jinou metrikou. Algoritmus
24
K-Means je velmi citlivý na počáteční umístění center a jejich nevhodná volba může způsobit špatné výsledky zejména díky riziku nalezení lokálního minima[6][22]. Shlukování pomocí EM algoritmu
EM algoritmus reprezentuje jednotlivé shluky jako hustotu normálního rozložení N (µ , Σ) definovaného střední hodnotou µ, která je dána souřadnicemi shluku, a kovariační maticí Σ odvozené ze souřadnic známých bodů (pozorování). Při aplikaci EM algoritmu probíhají iterace s těmito kroky: 1. Expectation, ve kterém se počítají pravděpodobnosti příslušnosti bodů do shluků pro všechny kombinace bodů a shluků 2. Maximalization, ve kterém se metodou maximální věrohodnosti počítají nová centra shluků a kovariační matice pro další krok Protože maximalizace je založena na derivaci
∂P =0 , používají se logaritmované ∂µ
pravděpodobnosti (log likehood). Průběh jejich funkce je rostoucí a lze tedy snadněji pomocí derivací hledat jejich maximum. 3.2.2
Identifikace témat
Identifikace témat (topic modeling) se obvykle využívá při zpracování přirozeného jazyka, kde je cílem ze souboru vstupních dokumentů extrahovat témata, kterými se dokumenty zabývají. Jde o specifický způsob seskupování. Předem se nevyžaduje seznam témat ani ohodnocený testovací vzorek, vše se odvozuje ze statistiky výskytů slov v dokumentech. Témata jsou získávána v abstraktní formě jako unikátní kombinace slov a seznamu dokumentů, které jsou pro ně relevantní. Postup analýzy textů: 1. Nashromáždit nebo identifikovat text obsahující dokumenty 2. Připravit dokumenty pro zpracování analyzerem (stemming/lemmatisation, vyřadit stop slova, tokenizace) 3. Zvolit počet hledaných témat 4. Sestavit reprezentaci dokumentů ve vektorovém prostoru 5. Identifikovat podobné dokumenty, například na základě euklidovské vzdálenosti vrcholů vektorů témat nebo jimi svíraného úhlu
25
Jedním ze způsobů, jak reprezentovat dokument je vektor relevantnosti slov. Relevance může být vyjádřena binárně, početně (TF) nebo váhově (TF-IDF). Protože takto vyjádřený vektor bude mít velký počet dimenzí (různých slov), je nutné ho redukovat. Redukce probíhá buď výběrem příznaků (feature selection) nebo extrakcí příznaků (feature extraction). V prvním případě se vyřazují takové příznaky, které nejsou významné pro plánovanou aplikaci. Ve druhém jsou skupiny příznaků nahrazovány novými příznaky. V případě vektoru slov mohou například nové příznaky představovat základní tvary (lemmatisation) nebo kmen slova (stemming).[23] Reprezentace dokumentu pomocí vektoru slov i přes popsané techniky trpí obvykle problémem velkého množství dimenzí, které znesnadňují další zpracování. Proto existují i jiné techniky, jež místo s vektorem slov pracují spíše s vektorem tématických oblastí a dokument je charakterizován vztahem vůči těmto předem naučeným tématům
(metody
nebo témata
jsou
Latent Semantic Analyses, v průběhu
procesu
Propabilistics Latent Semantic Analyses)
učení
kompletně
odvozena
(metoda
Latent Dirichlet Allocation, dále jako LDA).[23] Zde je záhodno vysvětlit význam použitého termínu „téma”. Téma je vždy definováno seznamem slov a hodnot, nakolik jsou konkrétní slova pro toto téma specifická. Zda je takto definované téma nějak jednoznačně pojmenovatelné není pro proces učení vůbec relevantní. Proto tvrzením „metoda LDA sama odvozuje témata” není myšleno, že by dokument byl touto technikou přiřazen například do třídy „sport“ nebo „politika“. A ačkoliv u ostatních technik pracující s předpřipravenými tématy budou tyto pravděpodobně i autory pro jejich potřeby pojmenovány, do procesu učení název nijak nevstupuje a zpracovávány jsou pouze slova definující téma. Množství hledaných témat má zásadní vliv na použitelnost výstupu. Při volbě této hodnoty se bere v potaz především účel aplikace. Výstupem učení jsou vektory dokumentů, kde řádky představují slova a hodnoty na řádkách relevance těchto slov pro daný dokument. Dále pak vektor témat, kde jsou obdobným způsobem vyjádřeny vazby slov na témata. Při analýze podobnosti mezi různými dokumenty stačí porovnat jejich vektorové popisy. Dokumenty s podobným vektorem mají pak podobný obsah.[24] Nejpoužívanější technika LDA považuje vstupní data za pozorování generativního pravděpodobnostního procesu, který zahrnuje skryté proměnné. U dokumentů jsou skrytou proměnnou struktura pro ně relevantních témat.[25] Každé slovo má tedy různě silnou
26
relevanci k více dokumentům a totéž platí pro jeho vztah k tématům. Proto i každý dokument má různě silnou relevanci k více tématům. Relevance slov k jednotlivým tématům jsou určeny pomocí vydělení počtu slov mezi všechna témata. Následně je použit odvozovací algoritmus, který hledá skupiny spolu souvisejících slov. Přitom usiluje o co největší řídkost témat pro jednotlivé dokumenty a penalizuje případy, kdy má dokument příliš mnoho silných vazeb na různá témata. Na základě toho upravuje definice vztahů mezi slovy, čímž postupně dochází ke vzniku uskupení slov vzájemně více provázanými než se slovy mimo toto uskupení.[25] 3.3
Učení posilováním Třetí skupina algoritmů se zabývá tzv. učením posilováním (reinforcement learning),
v češtině někdy též nazývaném zpětnovazebním učením. Algoritmy usilují o dosažení nějakého cíle a vytváří sekvenci akcí, kterými se k cíli snaží dostat. Každá jedna samotná akce není sama o sobě důležitá, důležitá je stanovená politika (policy) a zda akce do této politiky zapadá nebo ne. Algoritmus posuzuje jednotlivé politiky a umí ohodnotit jejich přínos pro dosažení stanoveného cíle. Pokud má přístup k historii úspěšných sekvencí, je schopen se z ní poučit a zohlednit je při návrhu nových politik. Učení posilováním je vhodné především do prostředí, kde existuje komponenta chovající se jako agent, který je sám schopen provádět nějaké akce a posuzovat jejich dopady. Ačkoliv existují i scénáře, kdy aplikace učení posilováním v oblasti e-komerce bude představovat přínos, software používaný v praktické části tyto algoritmy nepoužívá a praktická část práce se jimi nezabývá. Proto nebude toto téma v práci podrobněji popisováno. 3.4
Map Reduce Jde o techniku spočívající v rozdělení zpracování dat do dvou odlišných úloh. První se
nazývá Map a provádí konverzi vstupních dat do podoby n-tic [klíč,hodnoty], které jsou výstupem mapovací funkce. Obsah n-tice je zvolen tak, aby zohledňoval zpracováním sledované cíle. Druhou úlohou je Reduce a jejím úkolem je převzít výstup z více Map úloh a zredukovat je do jediné sady n-tic, opět za pomoci nějaké stanovené funkce. Teprve nad redukovanými daty jsou nakonec prováděny požadované operace.[9] Algoritmus MapReduce lze shrnout slovy: seznam hodnot je transformován na jiný seznam hodnot, který
27
je posléze redukován na hodnotu jedinou. Tento princip se často používá při řešení úloh strojového učení. Na Ilustrace 8 je vyobrazen příklad zpracování došlých objednávek. Nejdříve jsou vstupní data mapována do požadované n-tice a ty jsou nakonec převedeny na výstupní hodnoty. Protože řešeným požadavkem je získat celkový obrat, pro fázi redukce je použita funkce součtu (SUM). Současně diagram zachycuje možnost aplikovat mapování na víceprvkovou množinu vstupních dat.
Ilustrace 8: Příklad získání obratu pro jednotlivá města metodou MapReduce
Z pohledu strojového učení je metoda MapReduce zajímavá i jako řešení potenciálních výkonnostních problémů, které mohou nastat při aplikacích na reálná data. Protože množství úloh strojového učení lze přeformulovat do úlohy pro MapReduce[26], může pak zpracování probíhat ve výpočetním clusteru. Škálovatelnosti v clusteru je dosaženo rozdělením zdrojových dat mezi více uzlů, které nad nimi na vyžádání provádí mapovací úlohy a vrací jejich výstup. V clusteru pak existuje jeden nebo více uzlů tvořících vstupní rozhraní pro klientské požadavky k vyřízení, uzly mající za úkol mapování a uzly provádějící redukci. Struktura clusteru se může lišit počtem uzlů vykonávajících určitou roli nebo některé uzly mohou zastávat více rolí, ale pro účely škálování bude zátěž z výpočetně nejnáročnější operace map rozložena na více uzlů.
28
4
Aplikace metod na konkrétní problémy Pro všechny dříve popsané úlohy strojového učení lze v oblasti e-komerce vymyslet
mnohé způsoby jejich uplatnění. Nejznámější klasifikační úlohou je detekce nevyžádané pošty (spam), kdy na základě ručního roztřídění došlé pošty uživatelem klasifikátor u nově příchozích emailů odhaduje, zda nemají být označeny jako spam a nějakou formou filtrovány (odmítnuty při SMTP spojení na poštovní server nebo přesunuty do vizuálně oddělené přihrádky v emailovém klientovi). Klasifikovány mohou být prakticky jakákoliv data. Jakmile je potřeba něco třídit nebo ohodnotit a jsou pro tento úkol k dispozici ohodnocená historická (učící) data, počítačem prováděná klasifikace umožňuje zpracovat masivní množství dat. Výstup může být chápán jako konečný stav nebo posloužit jako příprava podkladů pro konečné zpracování lidskou silou. Pro shlukování existuje rovněž široké uplatnění: seskupovat lze podobné dokumenty (produkty,
obrázky),
databáze
zákazníků
lze
rozdělit
do vyprofilovaných
skupin
(customer/market segmentation) nebo najde své uplatnění při analýze prodeje. Strojové učení je základem mnoha úspěšných služeb, které jsou běžně využívány na Internetu[3]: •
klasifikátor spamu (Spam Assasin, Gmail, atd.)
•
sémantická reklama (Google Adwords, Sklik, atd.)
•
klasifikace typu zpráv (Gmail a jeho tématické složky)
•
doporučení „zákazníci, kteří koupili tento produkt, rovněž zakoupili...“ (Amazon)
Další potenciální způsoby nasazení strojového učení podle [27]: •
doporučení produktů na základě známých údajů o zákazníkovi (např. z historie nákupů, bydliště, zájmů) nebo na základě doporučení jiných zákazníků s podobným profilem (collaborative filtering)
•
rozpoznávání podvodného nebo jinak nežádoucího jednání (detekce anomálií)
•
jako jedna z metod oblasti dolování dat, například analýza kombinace atributů u zákazníka, které ho předurčují k nákupu Zdrojovými daty nemusí být pouze data ve výhradním vlastnictví tvůrce analýzy,
existují i zdroje veřejně dostupné. Jedním z takových dostupných zdrojů dat vhodných pro analýzu jsou sociální sítě, protože obsahují dostatečně velké množství profilů
29
se zveřejněnými údaji využitelnými pro zacílení na určité demografické skupiny. Často zveřejňovanými údaji jsou: •
rok narození
•
pohlaví
•
dosažené vzdělání
•
přibližné bydliště atd. Další zpřesňující údaje lze získat například emočně časovou analýzou profilu.
Například proběhnou-li volby či jiná významná celospolečensky vnímaná událost, lze kombinací jejich výsledku a projevené emoce v čase po vyhlášení s velkou pravděpodobností přiřadit danému profilu politické nebo jiné preference a zpřesnit jeho demografické zařazení. Společně s dalšími údaji v profilu pak tyto odvozené údaje poslouží jako zdrojová data pro další analýzu. Předmětem analýzy může být nepřeberné množství otázek, pro která lze nějakým způsobem z dostupných dat najít indicie pro rozhodnutí. Vyjádřil se analyzovaný jedinec k nějakému analyzovanému tématu (klasifikace)? Jaké emoce projevil (rozpoznávání emocí)? Jaká témata preferuje (extrahování informací)? Jaké barvy má rád (analýza grafických dat)? V jakých časech bývá online (statistika)? A mnoha dalších. 4.1
Agregace zpráv Agregátory zpráv mají za úkol shromažďovat informace z různých zdrojů a usnadnit
uživateli získat rychlý přehled o všech aktuálních tématech. Jako zdroj obvykle slouží takzvané RSS feedy, tedy XML dokumenty určené pro syndikaci obsahu. Agregátory mohou být sofistikovanější a zpracovávat i obsah na odkazované webové adrese, případně nabízet jinou přidanou hodnotu. Tou může být: •
dohledání jiných podobných článků (oblast topic modeling)
•
profilování hlavních zpráv podle počtu zdrojů (topic modeling, clustering)
•
filtraci hlavních zpráv tak, aby se vedle sebe nezobrazovaly články z různých zdrojů na stejné téma (topic modeling)
•
štítkování zpráv podle předem připraveného seznamu štítků (classification, labeling)
•
výběr článků podle profilu uživatele (classification, collaborative filtering)
•
za pomoci jednoduché metriky založené na četnosti článků určit význam aktuálních událostí 30
Příkladem
služeb
fungujících
na principu
agregátoru
jsou
Google News
(news.google.cz) nebo Právě dnes (pravednes.cz). Agregování lze využít i pro potřeby marketingu. Například inzerent hledající reklamní prostory, může použít agregátor pro odhalení míst, kde se pro inzerci relevantními tématy dlouhodobě zabývají. Obdobně on-line reklamní systémy musí umět agregovat zapojené webové stránky do tematických celků tak, aby mohly rozhodovat o co nejlepším umístění inzerce. 4.2
Rozpoznávání jazyka Příklad: firma provozuje
multijazyčný web
a obsluhuje zákazníky
komunikující různými jazyky. Pokud strojově rozpozná, v jakém jazyce je příchozí komunikace, může ji nasměrovat na vhodnou osobu pro její vyřízení.14 Z pohledu strojového učení je rozpoznání jazyka klasifikační úlohou. Alternativou ke strojovému rozpoznávání jazyka mohou být pomůcky v podobě existence různých emailových adres, přiřazení jazyka na základě jazykové mutace podle jazykové verze použité pro zobrazení kontaktního formuláře nebo explicitní vyžádání volby jazyka od protistrany. Všechny tyto alternativy sebou nesou zásadní nevýhody. Existence pro zákazníky.
více
emailových
adres
zhoršuje
přehlednost
kontaktních
údajů
V rámci jedné webové prezentace lze toto skrýt pomocí filtrace
podle jazykové mutace, ale v případě inzerce, firemních zápisů v různých katalozích nebo materiálů tato možnost neexistuje. Zákazníci
mohou
z různých
důvodů
používat
odlišnou
jazykovou
mutaci
pro prohlížení webu a jazyk pro komunikaci. Například kvůli odlišné kvalitě prezentace a úplnosti doprovodných materiálů se jim často vyplatí upřednostnit anglickou variantu před ostatními. Ale to neznamená, že při kontaktu lokálního zastoupení nebudou chtít komunikovat svou rodnou řečí nebo nebudou klást dotazy určené lokálnímu zastoupení. Komunikující operátor tak může dostat k řešení obsah, kterému nebude rozumět. A nakonec třetí zmíněná alternativa je současně ukázkou odrazujícího obtěžování potenciálního zákazníka od kontaktu. Nejen při webovém prodeji platí, že cokoliv složitého odvádějícího pozornost od žádoucího směru znamená vysoké procento odchodů ze stránky a ztráty obchodní příležitosti.
14 Inspirováno příkladem uvedeným v dokumentaci k Google Prediction API[28].
31
údržba
2 3
zákazník
1
1 podle jazykové mutace 2 více emailových adres 3 volba jazyka ve formuláři
vyřízení Ilustrace 9: Složitost alternativ ke strojovému rozpoznání jazyka
Strojové učení není jediný způsob, jak se s takovým problémem vypořádat. Diagram na Ilustrace 9 mapuje negativní rysy alternativ ke strojovému rozpoznávání jazyka: zvýšenou složitost pro zákazníka, složitost pro údržbu obsahu a složitost pro vyřízení. Pokud je pro řešení využito strojové učení, vše se zjednoduší: jedna emailová adresa pro vnější komunikaci, jeden kontaktní formulář, žádné nadbytečné prvky odrazující od jeho použití. A přesto v naprosté většině případů komunikace poputuje k nejvhodnějšímu příjemci. 4.3
Rozpoznávání obsahu Za příklad poslouží stejný problém jako u rozpoznávání jazyka s malou obměnou:
hledá se nejvhodnější příjemce podle typu obsahu. Technický dotaz by měl být přeposlán na podporu prodeje, propagační materiály na sekretariát nebo do spamu, objednávky na prodejce, reklamace reklamačnímu oddělení atd. 4.4
Rozpoznávání emocí Příklad: firmu dovážející elektroniku zajímá, jaké jsou skutečné reakce cílové skupiny nově uvedeného produktu v zahraničí. Na základě nich se rozhodne, zda má zájem ucházet se o zastoupení pro ČR. Rozpoznávání emocí je v takovém případě mocným nástrojem pro zvyšování
úspěšnosti prodeje. Co bude prodejním hitem příštích vánoc? Jak zákazníci hodnotí zakoupené produkty? Má smysl jim k nim zpětně nabízet příslušenství nebo se raději nepřipomínat? Pokud bude prodejce schopen na takové otázky s předstihem a vysokou úspěšností umět odpovědět, nepochybně tím získá významnou konkurenční výhodu. Z pohledu strojového učení je rozpoznávání emocí klasifikační úlohou. Zdroji pro rozpoznání emocí mohou být sociální sítě, diskusní příspěvky pod články nebo produkty, ale třeba i vlastní emailová komunikace se zákazníkem.
32
4.5
Rozpoznávání zájmu o produktové vlastnosti Příklad: firma na základě analýzy zájmu cílové skupiny tipuje vlastnosti produktů, které jsou významné pro úspěšnost prodeje. Místo aby odpovědní pracovníci hádali potenciální sortiment či některé zákazníky požadované atributy na základě své intuice a zkušeností, mohou se rozhodovat až ve výběru zúženém pomocí strojové inteligence. Strojová inteligence na rozdíl od lidských pracovníků může analyzovat řádově větší
objem informací a přispět tak k lepší konečné volbě. Zdrojová data pro analýzu mohou pocházet z historie prodejů nebo průzkumu údajů na sociálních sítích. Cílem analýzy je identifikovat společné rysy prodejně úspěšných nebo naopak neúspěšných produktů. Z pohledu strojového učení se nabízí několik rovnocenných postupů. Pokud analýza probíhá nad historickými daty o prodeji, může být jako metoda zvoleno seskupování podle technických produktu a získané shluky dále analyzovány například z pohledu prodejnosti nebo marže. Takové nasazení je typické pro využití strojového učení jako techniky dolování dat. Protože tímto způsobem získané shluky budou pravděpodobně dále ručně analyzovány, je vhodné pro tyto účely použít nástroje s grafickým uživatelským rozhraním. Jiným přístupem by mohla být klasifikace, kdy produkty zvažované pro zařazení do sortimentu by klasifikátorem získaly hodnocení jejich potenciálu. Nebo by pro každý takový produkt byly algoritmem pro hledání podobnosti nalezeny jeho nejbližší ekvivalenty a potenciál by byl odhadnut z jejich historického výkonu. 4.6
Extrahování informací Extrahování informací (information extraction) se zabývá získáním strukturovaných
dat z dat nestrukturovaných a to především pomocí metod zpracování přirozeného jazyka (NLP). Nestrukturovaná zdrojová data ale nemusí být pouze ve formě textu, do této kategorie strojového učení se řadí i multimediální data a další formáty. Hlavní motivací taková data zpracovávat je velký informační potenciál, který skýtají. Nestrukturovaná data často obsahují informace zasazené do kontextu s jinými informacemi a umožňují odhalovat skryté souvislosti. Navíc nestrukturovaná data tvoří až 80% všech dat, kterými podniky disponují[4]. V oblasti e-komerce může být jedním ze scénářů využití pro tipování nového sortimentu na základě recenzí v oborových webových magazínech. Výstupem zpracování 33
jednotlivých článků pak může být vektor (výrobce, produkt, datum) určený pro další například statistické zpracování. Jinou aplikací může být automatické přiřazení štítků bitmapovým obrázkům na základě produktů, které se na nich vyskytují. Složitost takové klasifikační úlohy stoupá s počtem rozpoznávaných tvarů a jejich podobností, přičemž pro úspěšnost je především rozhodující zvolit správné příznaky, podle kterých budou tvary rozpoznávány. Zde by mohlo být
výstupem
přiřazení
jednoho
nebo více
vektorů
ve tvaru
(produkt,
pohled)
ke klasifikovanému obrázku. 4.7
Analýza grafických dat V jaké podobě je k dispozici nejvíce elektronicky uložených dat? Bez ohledu
na metodiku měření a její konečný výsledek, grafická data budou tvořit nezanedbatelný podíl. Údaje o struktuře dat přenášených po Internetu uvádí, že objemově většinu síťového provozu tvoří přenos video obsahu[29]. Nakolik koreluje údaj o podílu na síťovém provozu s podílem na celkově existujícím objemu dat? Bez zodpovězení této otázky nelze vyvozovat závěry o obecné dominanci objemu grafických dat nad jinými formáty, přesto jako indicie významu takový údaj posloužit může. Pro potřeby této práce je daleko důležitější otázkou, kolik údajů nebo dokonce informací z dat v této podobě dokážeme strojově získat. Ačkoliv grafická data mohou mít různou podobu (videosekvence, bitmapy, vektory), nejobvyklejším předmětem zpracování bude pravděpodobně bitmapový obrázek. Výsledky jeho zpracování mohou být zasazeny do komplexnější úlohy, kterou může být například analýza pohybu na videosekvenci nebo na ještě vyšší úrovni řízení dopravního prostředku umělou inteligencí. Někde na nejnižší úrovni zapouzdření bude nutné umět popsat obsah obrazových dat a využít tento popis pro potřeby zadané úlohy. Popis dat může tvořit nějaký vektor hodnot. Význam hodnot, tedy co konkrétní hodnoty představují, a dimenze vektorového prostoru jsou základní vlastnosti ovlivňující použitelnost popisu při dalším zpracování. Jedním takovým způsobem popisu bitmapového obrázku je rozdělit bitmapu na množství menších segmentů a pro ně získat popisný vektor atributů (image segmentation). Takto získaný vektor lze použít k dohledání podobného vektoru představujícího jiný obrázek.
34
Podle [30] postup řešení problematiky hledání vizuální podobnosti zahrnuje kroky: 1. Předzpracování obrázku: aplikace filtrů pro zvýšení kontrastu, odstranění šumu atd. 2. Segmentace
obrázku
(image
segmentation)
pomocí
rozdělení
na jednotlivé
rovnoměrné segmenty (například tvořící matici) nebo rozdělení na oblasti, ve kterých pixely uvnitř mají společné vlastnosti mimo oblast se nevyskytující. Zde se může uplatnit strojové učení (shluková analýza, klasifikace,...). 3. Vytvořit popisné vektory pro jednotlivé regiony. 4. Pokud je to potřeba, znovu provést segmentaci. Přitom rozhodnout, zda některé původně získané segmenty spojit do jednoho. Při tomto kroku mohou být nezbytné znalosti o konkrétní úloze (např. o hledaném objektu), jen zřídkakdy může být použit obecný automatický postup. 5. Odstranit segmenty, které se zdají nepotřebné pro další zpracování: jsou příliš malé nebo vyhodnoceny jako nerelevantní. 6. Uložit popisný vektor obrázku pro pozdější zpracování a opakovat kroky pro ostatní obrázky. 7. Použít popisné vektory pro porovnání obsahu obrázků za pomoci některého z algoritmů pro porovnávání vzorů, klasifikaci, shlukování nebo obecně z oblasti umělé inteligence a dolování dat. Způsob segmentace je odvislý od úlohy, pro kterou je popis připravován. Tam kde je segmentace provedena rozdělením bitmapy na pevný počet sloupců a řádků, mohou být popisnými informacemi barevné kanály nebo jas[31]. Například údaj o nejčastější nebo průměrné barvě atd. U nepravidelných segmentů potom navíc tvar segmentu, jeho obvod, plocha, počet děr a další vlastnosti, které lze objektivně naměřit[30]. Informace v obrazových datech jsou primárně
reprezentovány nějakými objekty
a objekt lze nejlépe detekovat podle jeho hran. Proto segmenty mohou být popsány podle uvnitř detekovaných tvarů pomocí detektorů hran. Ty mohou pracovat na principu derivací obrazu nebo analýze frekvenčního pásma[32], nejčastěji se používá histogram[33]. Hranu pak představují místa s velkou změnou jasových hodnot pixelů[32]. Zejména při prodeji v elektronických obchodech nastává situace, kde je dobré zákazníkovi
nabídnout
produkt
podobný
nějakému
jinému
(vyprodanému,
dříve
prohlíženému, atd.). Podobnost může být určena nejen podle technických parametrů produktu, 35
ale právě i vizuální. Samostatnou otázkou k zodpovězení je, co si představit pod pojmem „vizuální podobnost“ produktů. Při porovnání vzhledu není jednoznačně rozhodnutelné, zda jsou si více podobné vyobrazení s podobnými objekty (sémantická podobnost), s podobným barevným rozložením na fotografii nebo obsahující stejné vzory. Posouzení podobnosti je problematické, protože je velmi subjektivní a každý jedinec může vyhodnotit podobnost zcela odlišně.[34]
Tento problém dobře znázorňuje Ilustrace 10, kde vyhledávač Google vrací seznam vizuálně podobných obrázků pro zadaný obrázek obsahující dětské kolo. Ani jeden z nabídnutých obrázků neobsahuje vyhledávaný objekt, přesto všechny nesou vizuálně podobné znaky v podobě zeleného travnatého pozadí.15 Z těchto důvodů může být žádoucí za pomoci strojového učení vytvořit personalizovaný model uzpůsobený záměrům konkrétního návštěvníka. Upřednostňované znaky mohou být odhadnuty podle shodných vlastností několika posledních produktů, které si prohlížel.
15 Nutno dodat, že v Google lze dosáhnout lepšího výsledku kombinováním zdrojového obrázku a klíčového slova „dětské kolo“. Potom výsledky budou obsahovat dětská kola na zeleném travnatém pozadí.
36
Například u zákazníka vybírajícího míč v obchodě s hračkami může na základě historie prohlížených položek algoritmus strojového učení vyhodnotit jako pro něj rozhodující kritérium barevnost a nabídnout mu seznam pravděpodobně pro něj zajímavých položek. U jiného bude hlavním kritériem konkrétní vzor, kterým je třeba jeho oblíbená kreslená postavička. Zaznamenávat všechna potenciální kritéria ručně by představovalo tak velké nároky na administrativu, že to lze u velkého sortimentu považovat za prakticky neproveditelné. Navíc umělá inteligence je schopna odhalit i podobnosti, které nejsou na první pohled zřejmé nebo prostě jen lidskou obsluhu ve chvíli zadávání dat nenapadly. Sémantické porovnání obrázků je nelehlý úkol, při kterém je nutné se vypořádat s mnoha technickými problémy. I původně identické obrázky mohou být vinou dalšího zpracování pozměněny (změna rozlišení, komprese, barevnosti). Jakmile dva obrázky obsahují
fotografie
téhož
objektu
z jiného
úhlu,
zvětšení
nebo třeba
osvětlení,
přes sémantickou identičnost může obraz nést naprosto odlišné popisné znaky. A platí to i naopak: fotografie s odlišnými objekty nacházejícími se v podobném prostředí se budou v mnoha ohledech podobat[30], jak zachycuje Ilustrace 10. 4.8
Předpověď chování návštěvníka webu Na základě podobnosti pohybu na webových stránkách (sled, strávený čas,...)
aktuálního návštěvníka s historickými daty lze odhadovat jeho pravděpodobný cíl, případně pravděpodobný konečný stav návštěvy (nákup, kontakt, odchod). Při zapojení více vstupních údajů lze předpovídat další vlastnosti. Pro vyhodnocení pohybu na webu se zdají být vhodné absorpční (Markovovy) řetězce, kde stavy reprezentují jednotlivé stránky webu a přechody mezi nimi jsou ohodnocené pravděpodobností takového přechodu. Absorpční stavy pak představují sledované konverzní cíle (košík, kontaktní formulář) nebo pro analýzu jinak relevantní stránky. Stavy také mohou představovat seskupení více stránek, například detaily všech produktů mohou být jedním stavem a jiným výpisy produktů v libovolné kategorii, případně stránky produktů seskupené tématicky (stav tvořený detaily všech cestopisů a jiný stav tvořený detaily všech prodávaných knih o vaření). Takto vytvořený grafický model sám o sobě poslouží pro získání statisticky zajímavých údajů[35].
37
Příklady informací odvozených z charakteristik absorpčních řetězců: •
Střední doba přechodu procesu započatého příchodem z reklamní upoutávky měřená proti skupině stránek se seznamem produktů (představující transientní stavy) jako informace o tom, jak přesně daná kampaň směruje získané návštěvníky k cíli.
•
Střední doba strávená v transientních stavech vypovídá o tom, odkud návštěvníkům trvá nejdéle nebo naopak nejméně kroků, než zkonvertují nebo odejdou. Takový údaj může avizovat, kde je vhodné zkrátit proces objednání.
•
Pravděpodobnost přechodu do absorpčních stavů napoví, které vstupní stránky (seskupení) mají nejlepší nebo nejhorší konverzní poměr. Takový údaj může být použit pro volbu, kam směrovat odkazy při inzerci.
•
Pravděpodobnost přechodu z nějakého transientního stavu do absorpčního v zadaném čase je charakteristika, která srovnáním různých transientních stavů vypovídá o přehlednosti nebo přesvědčivosti jimi představovaných stránek. Zodpoví otázky, zda odněkud návštěvník nebloudí moc dlouho nebo o něj zbytečně provozovatel webu nepřichází. Pro proces strojového učení může vhodně sestavený absorpční řetězec představovat
zdroj dat. Například při úpravách webových stránek může klasifikátor využívající vektor charakteristik automaticky detekovat vznik případného problému. Pro tento účel musí být změny zaznamenávány včetně aktuálních charakteristik před jejich nasazením a pomocí nějakého kritéria ohodnoceny. Jiné scénáře se mohou zaměřovat na klasifikaci návštěvníka nebo identifikaci jeho cílů a na zjištěné výsledky vhodně reagovat. Pokud by v každém návštěvníkem prodělaném stavu bylo vyhodnoceno jeho vlastní chování, může posloužit pro hledání podobnosti mezi ním a jinými návštěvníky. Tento způsob je vhodný i pro detekci robotů, kdy vysoká míra odchylek od obvyklého chování poslouží pro klasifikátor jako alternativa k učení se chování charakteristického pro roboty.
38
5
Popis implementace V předchozích kapitolách byly popsány algoritmy strojového učení a scénáře jejich
aplikace na vybrané problémy z oblasti e-komerce. Tato kapitola si klade za cíl přetavit nabyté teoretické znalosti do schopnosti implementovat strojové učení jako řešení reálných problémů. Obdobně jako v jiných odvětvích vývoje software i pro strojové učení existují nástroje a knihovny usnadňující implementaci. Pro praktické využití není tedy nutná detailní znalost každého použitého algoritmu, spíše se upotřebí všeobecný teoretický přehled a znalost nástrojů, jež jsou pro konkrétní úlohu k dispozici. 5.1
Nástroje
Pro implementaci ukázkových příkladů byly zvažovány tyto nástroje: •
Java-ML
•
Weka
•
Apache Mahout
•
Mallet
•
BoofCV
•
Commons Math Při výběru byla posuzována náročnost nasazení v kombinaci s jazykem Java (autorem
subjektivně upřednostňovaným) a svobodná licence. Svobodné licence neznamenají automaticky bezproblémové použití, proto především před komerčním využitím je nutné ověřit, zda licence nástrojů neklade na jimi vytvořené dílo své vlastní požadavky16. K dispozici jsou i další nástroje a knihovny pro oblast strojového učení, které mohou být pro některé reálné úlohy vhodnější volbou. Příkladem stojícím za zmínku je framework českého původu Gensim (http://radimrehurek.com/gensim/) specializující se na zpracování přirozeného jazyka.
16 Například svobodná licence GPL je relativně invazivní a pro proprietární software určený k dalšímu šíření mohou být její požadavky na odvozená díla neakceptovatelné nebo dokonce nepřijatelné pro licenční konflikt s jinými částmi aplikace. Někdy je tento fakt součástí obchodní politiky autorů, kteří duálně k produktu nabízejí i komerční licence.
39
5.1.1
Apache Mahout
Framework
Apache Mahout
(http://mahout.apache.org/)
je
zaměřen
primárně
na aplikace strojového učení v prostředí výpočetních clusterů. Je postaven nad projektem Apache Hadoop
(http://hadoop.apache.org/),
který
poskytuje
spolehlivý
ekosystém
pro škálovatelné a distribuované výpočty. V současnosti podporuje čtyři základní případy použití: 1. Návrhy doporučení (recommendation mining): doporučení položek na základě předchozího chování uživatele. 2. Shlukování (clustering): vytváření skupin dokumentů, které jsou tematicky podobné. 3. Klasifikace
(classification):
automatické
přiřazení
dokumentu
do tematicky
odpovídající kategorie. 4. Hledání společného výskytu (frequent itemset mining): identifikace položek, které se vyskytují často společně. 5.1.2
Weka17
Framework Weka je zaměřen na dolování dat a pro tento účel má implementovánu podporu pro všechny obvyklé typové úlohy a běžně používané algoritmy. Disponuje grafickým uživatelským rozhraním, ze kterého umožňuje vizuálně měnit typ úlohy, použitý algoritmus
nebo parametry
úloh.
Obsahuje
generátory
dat
pro testování,
filtry
pro předzpracování dat z různých zdrojů a umí výsledky vizualizovat pomocí grafů. Tyto vlastnosti ho proto favorizují pro výukové potřeby a ručně prováděnou analýzu dat. Současně lze nástroj ovládat příkazy v terminálu nebo použít jako knihovnu umožňující algoritmy volat z vlastního zdrojového kódu. Framework nabízí několik samostatných grafických rozhraní: •
Weka KnowledgeExplorer
•
KnowledgeFlow
•
Weka Experimenter Weka KnowledgeExplorer slouží pro zkoumání dat a snadnou aplikaci všech nástrojů
dostupných ve frameworku. Rozhraní KnowledgeFlow má podobný účel, ale je inspirované
17 Kapitola zpracována za pomoci dokumentace projektu[36]
40
procesním modelováním a umožňuje vizuálně modelovat sekvenci kroků, které mají být vykonány. Poslední Weka Experimenter je určen pro testování algoritmů strojového učení. Umožňuje předvolit počet iterací, kolekce dat a učících algoritmů, které na ně mají být aplikovány. Získané modely pak testovat a porovnávat jejich úspěšnost napříč algoritmy a původními i novými daty. Při použití z jazyka Java jsou základními komponentami frameworku Weka: •
instance představující vzorky dat
•
filtry pro předzpracování dat
•
učící algoritmy (klasifikátory, shlukovače)
•
hodnotící algoritmy pro posouzení přesnosti výstupu učících algoritmů
•
algoritmy pro výběr atributů (feature selection) Za zmínku stojí, že autoři frameworku
Weka se podílí na vývoji jiného
frameworku MOA. Ten má podobné vlastnosti, ale je zaměřen na streamovaná data. Protože pro něj v současnosti neexistuje stabilní verze, nebude mu věnováno více prostoru. 5.1.3
Java-ML18
Knihovna obsahuje množství algoritmů pro strojové učení a navíc umí pracovat i s některými třídami nástroje Weka. V současnosti podporuje typové úlohy klasifikace a shlukové analýzy. Základním stavebním prvkem je datový vzorek reprezentovaný třídou Instance, jednotlivé vzorky jsou seskupovány do množin představovaných třídou Dataset. Instance může mít své atributy, které jsou představované reálnými čísly, a také může volitelně mít určenou třídu, do které náleží. Všechny algoritmy obsažené v knihovně požadují na vstupu data reprezentovaná v těchto formátech. Algoritmy jsou nejenom učící, ale pokrývají širší spektrum problémů a požadavků, se kterými se lze při aplikaci metod strojového učení setkat. Takovými požadavky jsou například manipulace s daty (vytváření, ukládání, načítání, vzorkování, normalizace, diskretizace, aproximace hodnot nebo smazání neúplných vzorků) a atributy (ohodnocení, výběr) nebo porovnání instancí (vzdálenost, podobnost, korelace) atd. Třídy s algoritmy jsou 18 Kapitola zpracována z dokumentace projektu[37]
41
v knihovně transparentně organizovány pomocí veřejných rozhraní. Dají se tedy s minimálním zásahem do zdrojového kódu zaměňovat za jiné implementující stejné rozhraní. 5.1.4
Mallet
Mallet je nástroj pro statistické zpracování přirozeného jazyka, klasifikaci dokumentů, shlukování, identifikaci témat, extrahování informací a další aplikace strojového učení pro zpracování textu.[15] Mallet lze ovládat z příkazové řádky nebo ho použít jako Java balík a programovat proti jeho Java API. Podporovány jsou tyto typy modelů[15]: •
generativní (pravděpodobnostní modely pro náhodná známá data) ◦ Naive Bayes ◦ Hidden Markov Models ◦ Latent Dirichlet Topic Models
•
diskriminativní (modelují závislost neznámé proměnné y na známé x) ◦ Logistická regrese ◦ Conditional random fields (CRFs)
5.1.5
BoofCV
Knihovna BoofCV je primárně určena pro aplikace počítačového vidění. Knihovna mimo jiné obsahuje části věnované zpracování obrazu (aplikace filtrů), detekce atributů pro popisné vektory a jejich vizualizaci. Některé její schopnosti jsou specifické pro práci s kamerou a videem, jiné jsou obecně využitelné pro analýzu obrazu. Takovou obecnou funkcionalitou je detekce takzvaných zájmových bodů, kdy detekované vzory mohou posloužit i pro hledání podobností mezi bitmapami. Zájmové body jsou místa, která lze matematicky definovat a algoritmicky detekovat (roh, křivka, atd.). Detekované zájmové body musí být nějakým způsobem přepsány do vektoru. Zatímco o proces detekce se stará takzvaný detektor, o přepis se stará deskriptor. Pro detekci
knihovna
obsahuje
povícero
algoritmů,
včetně
algoritmů
založených
na dvourozměrné nebo trojrozměrné geometrii. Stejně tak je na výběr z více typů deskriptorů. Detektory a deskriptory mají odlišné vlastnosti především s ohledem na rychlost a odolnost proti změně pozice kamery.19 19 Knihovna BoofCV se používá především pro počítačové vidění založené na zpracování sekvence snímků.
42
Například algoritmus FAST umí detekovat rohy tak, že kolem bodu zvažovaného za rohový vytvoří kruh a počítá na jeho obvodu délku souvislé řady, která je tvořena buď světlejšími
nebo tmavšími
pixely
než středový
bod[38].
Základními
parametry
pro rozhodování algoritmu jsou poloměr kruhu, požadovaná délka souvislé řady a minimální akceptovaný rozdíl světlosti (threshold). Princip je zobrazen na obrázku Ilustrace 11, kde kruh tvoří 16 pixelů a vyhovující souvislou řadu tvoří devět pixelů.
Knihovna disponuje funkcí sledování atributů (feature tracking), kterou dokáže sledovat detekované zájmové body mezi snímky s odlišnou polohou kamery (vzdálenost, změna úhlu). Pro tuto funkcionalitu využívá metody strojového učení. 5.1.6
Apache Commons Math
Jde o knihovnu pro matematické a statistické výpočty, jejíž součástí je i komponenta org.apache.commons.math3.ml pro strojové učení. V současné verzi (v3.2) obsahuje množství algoritmů využitelných pro strojové učení (genetické algoritmy, algoritmy pro regresní analýzu, shlukování). Současně ale nepodporuje iterativní metody řešení úloh, proto se nehodí na zpracování velkých objemů dat. Také se neumí sama vypořádat s případnými chybějícími daty.
43
5.2
Demonstrační aplikace
5.2.1
Agregátor zpráv
Aplikace nabízí přidanou hodnotou v podobě seskupování článků podle jejich vzájemné obsahové podobnosti tak, aby uživatel nemusel číst stejnou informaci z více zdrojů ale mohl si vybrat jím nejvíce preferovaný. Nebo naopak tuto možnost měl, pokud o ní stojí. Protože jde o úlohu z oblasti topic modeling, využívá aplikace pro implementaci java API pro topic modeling nástroje Mallet. Ten nepodporuje stemming pro český jazyk, proto je pro tuto operaci využita třída CzechAnalyzer z knihovny Apache Lucene. V nástroji
Mallet
slouží
pro oblast
topic modeling
několik
tříd
z balíku
cc.mallet.topics založených na technice LDA. Odlišují se podporou paralelního zpracování, schopností rozpoznávat témata napříč více jazyky nebo používanými algoritmy. Také tím, zda pracují pouze nad samotnými slovy nebo umí rozpoznávat i fráze, případně zda témata jsou modelem chápána hierarchicky nebo ne. Při implementaci testovacího příkladu byla využita třída
cc.mallet.topics.ParallelTopicModel,
která
je
dokumentací
doporučována
i pro neparalelní zpracování. Pro nastavení modelu bylo použito hned několik parametrů: •
počet rozpoznávaných témat: menší hodnota vede ke spojování různých témat do jednoho, vysoká zase k rozmělnění stejného tématu mezi několik podobných
•
počet zpracovávaných dokumentů: vyšší počet znamená pravděpodobně více témat, což vyžaduje odlišné nastavení ostatních parametrů
•
hranice shody pro přiřazení dokumentu k tématu: vysoký požadavek na shodu vede k zamítnutí shody tam, kde by byla žádoucí, nízký požadavek vede k seskupování dokumentů, které jsou si tématicky velmi vzdálené
•
způsob přiřazení dokumentu k tématu: přiřazovat dokument k tématu vždy při splnění hranice shody nebo ho přiřadit jen k nejvíce relevantnímu tématu? První vede paralelně k vzniku velkých obecných témat a vedle nich specifičtějších podtémat. Druhé k ignorování některých vazeb. Případně lze volit nějaký alternativní rozhodovací algoritmus.
•
parametr alfa algoritmu LDA: vysoká hodnota alfa zvyšuje počet témat, ke kterým jsou dokumenty relevantní, nízká hodnota předpokládá dokumenty s vazbou na menší počet témat případně jen na jedno jediné. 44
•
parametr beta algoritmu LDA: vysoká hodnota beta zvyšuje počet témat, ke kterým jsou jednotlivá slova relevantní, nízká hodnota předpokládá slova více specifická pro každé téma
•
počet učících iterací: při vyšších počtech jsou tématům přiřazovány odlišné váhy a dokumenty tak lépe rozdělovány mezi zvolený počet témat. Témata se vzájemně více vylučují a klesá procento shody u dokumentů zahrnujících více témat.
•
kvalita stemmingu/lemmatizeru Parametry se navzájem ovlivňují a změna každého z nich má vliv na kvalitu výstupu:
počty chybně propojených dokumentů nebo naopak nerozpoznaných vazeb. U jednotlivých voleb nelze o žádné hodnotě jednoznačně rozhodnout, zda bude vracet optimální výsledky. Známy jsou pouze trendové dopady na množství identifikovaných seskupení dokumentů. Demonstrační aplikace pracuje s externím textovým seznamem adres feedů českých zpravodajských portálů. Seznam lze volně upravovat, ale je třeba respektovat vlastnosti aplikace, která je uzpůsobena pro zpracování českého textu. Významná změna agregovaných dokumentů může ovlivnit výstup a vyžadovat nové odladění některých parametrů vyhodnocení (počet hledaných témat, požadovaná hladina shody, atd.). Feedy jsou načteny, poté nadpisy a popisy jimi odkazovaných dokumentů analyzérem převedeny na tokeny obsahující jednotlivá slova v základním tvaru. Dokumenty definované těmito tokeny jsou použity pro proces strojového učení, kde výstupem zpracování jsou pole vzájemně souvisejících dokumentů. Tato pole lze chápat jako identifikovaná témata a jejich obsah jako zdroje, která se tématem zabývají. Aplikace na standardní výstup vypisuje html kód stránky se souhrnem témat zahrnujících hlavní zprávy. Význam zprávy je posuzován podle počtu dokumentů, které se jí zabývají, takže nejvíce probíraná událost je v čele výpisu a neseskupené články se na výpisu vůbec neobjevují. Titulek a popis prvního článku slouží pro zobrazení informace ve výpisu, ostatní články jsou vypsány jako alternativní zdroje.
45
5.2.2
Hledání vizuálně podobných produktů
Aplikace demonstruje řešení problému hledání vzhledově podobného produktu k nějakému předvolenému. Praktické využití se nabízí například na internetovém obchodě, kde je návštěvníkovi zobrazena nabídka produktů, které by ho s ohledem na historii pohybu v katalogu mohly zajímat, případně jako zdroj pro navigační výpis produktů podobných aktuálně prohlíženému. Produkty jsou zastoupeny bitmapovým obrázkem, ze kterého je vytvářen popis v podobě vektoru stanovených atributů. Pro získání zdrojových dat je využita webová služba Google Image Search, která poskytuje API pro vyhledávání obrázků pomocí klíčových slov a ve formátu JSON vrací seznam odkazů na relevantní soubory. API podporuje v hledaném výrazu použití operátoru pro omezení vyhledávání na konkrétní webové stránky, což usnadňuje
praktické
testování
aplikace
nad reálnými
daty
(například
existujících
internetových obchodů). Příklad výrazu pro sémantické hledání obrázků na doméně www.example.com: hledaný pojem site:www.example.com
46
Způsob nafocení produktů výrazně ovlivňuje schopnosti dohledat podobný obrázek. Na Ilustrace 10 je znázorněno, jak detektor může vyhodnotit podobnost pozadí jako vlastnost dominující vlastnostem objektu v popředí. Protože aplikace má za úkol dohledávat podobné produkty, je v tomto případě informace o pozadí v obrázku objektivně nezajímavá a je vhodné ji nějakým způsobem potlačit. K potlačení by bylo možné využít detekci objektů a následně porovnávat pouze objekt vyhodnocený jako pravděpodobný produkt. Technologicky daleko snazší cestou je porovnávat pouze obrázky, kde jsou produkty nafoceny na jednotném jednobarevném pozadí. Potom se detektor nemusí vyrovnávat s potřebou odlišit hlavní objekt od rušících prvků na pozadí a celý proces se zjednoduší a zrychlí. Databáze složená z fotografií produktů na bílém pozadí poslouží tedy pro potřeby vyhledávání shodných prvků lépe, než databáze která obsahuje prvky na měnícím se pozadí (silnice, místnost, krajina). U smíšených dat stojí za zvážení, zda není výhodnější cestou obrázky s pozadím pro potřeby srovnání zcela ignorovat a vyměnit tak jednoduchost implementace za neúplnost výstupu. Tedy u produktů s oběma typy vyobrazení použít jen ty vyhovující a zcela ignorovat produkty, pro které není k dispozici vyobrazení s jednobarevným pozadím. Ačkoliv se může takové zjednodušení zdát omezujícím, právě v oblasti internetového prodeje je prezentace nabízeného sortimentu vyobrazením na bílém pozadí běžná. Aplikace využívá schopnost knihovny BoofCV detekovat v bitmapovém obrázku takzvané zájmové body. Protože knihovna nabízí více metod detekce a deskripce, je pro demonstrační potřeby využito více detekčních algoritmů a výstup dává možnost vizuálně vyhodnotit úspěšnost hledání podobností pro konkrétní vstupní data. Na Ilustrace 13 je ukázka vyhodnocení podobnosti obrázků nad daty, které služba Google Image Search vrací při hledání
termínů
„tenisové
rakety“,
„dětské
rakety“
a „rakety
pro badminton“
v internetovém obchodě sportobchod.cz. První produkt v pořadí je ten, pro který jsou hledány jemu podobné. Ty jsou setříděny podle podobnosti od nejvyšší shody k nižší. Popisek obrázků je tvořen identifikátorem algoritmu, počtem spárovaných bodů a jejich podílem na celkovém počtu detekovaném v daném obrázku.
Ilustrace 13: Ukázka výstupu aplikace pro hledání podobností pomocí zájmových bodů
47
Popis pomocí zájmových bodů má své přednosti i nedostatky. Zájmové body teoreticky umožňují vyhodnotit podobnost obrázku v případech, kdy se jimi tvořený vzor nachází v úplně jiné části obrazu nebo na zcela odlišném typu produktu. Současně se ale špatně vypořádají s odlišným typem vyobrazení (například fotografie vs renderovaný obrázek), kde pro člověka snadno rozpoznatelná podobnost nevytváří matematicky popsatelné podobné body. Dalším nedostatkem je relativně výpočetně náročný způsob detekce. Ovšem zde je třeba přihlédnout k faktu, že v reálném nasazení by byla detekce a deskripce prováděna pouze jednou při vytváření indexu. Výsledek ovlivňují parametry zvolené pro detekci (algoritmus, rádius oblasti pro detekci okolí, tolerance, počet hledaných bodů) a vyhodnocení porovnání (tolerance odchylky, váha při různých odchylkách). Nelze předem rozhodnout, který z algoritmů detekce bodů bude dávat nejlepší výsledky, ani o žádném obecném tvrzení týkajícím se nastavení jeho parametrů. Vždy konkrétní nastavení zlepší výsledky na konkrétních datech a zhorší na jiných. Protože při reálném nasazení není možné parametry měnit a musí být jednotné napříč porovnávaným sortimentem, vhodným řešením může být použít pro popis obrázku kombinaci více detekčních algoritmů. Výsledek ovlivní i zvolená metrika pro získání výsledků shody bodů detekovaných stejným algoritmem. I pokud je pro nízkou míru tolerance zanedbán rozdíl v přesnosti shody jednotlivých spárovaných bodů, odlišně zvolená metrika porovnání takto zjednodušených výsledků dává odlišné pořadí. Například pouhých osm shodných bodů ze 400 detekovaných na prvním a 340 na druhém obrázku automaticky neznamená nízkou míru shody, zejména ne při přísně zvolené toleranci pro detektor. Proto i pokud jsou vyhodnocovány výsledky pouze jednoho typu detekce a je pro zjednodušení ignorována odlišná přesnost spárování (score shody pro jednotlivé dvojice bodů), i tak se nabízí více způsobů řazení výsledků: •
podle prostého počtu spárovaných bodů (se shodou do stanoveného limitu)
•
podle poměru spárovaných bodů k počtu ve zdrojovém obrázku :
•
podle poměru spárovaných bodů k součtu bodů v obou obrázcích:
spárováno bodů A spárováno bodů A+ bodů B
Pokud je při procesu párování bodů zvolena volnější míra jejich minimální shody (score), získané páry se mohou výrazně lišit svou přesností. Míra shody by měla být zohledněna ve zvolené metrice, kde by se potom pracovalo se sumou score namísto prostého počtu. 48
Jakmile mají být kombinovány výsledky založené na odlišných detekčních algoritmech, je navíc nutné rozhodnout o kritériu, jakým budou dílčí výsledky jednotlivých algoritmů zahrnuty do celkového výsledku. Protože odlišné techniky detekce vrací na porovnávaných obrázcích i řádově se lišící počty nalezených zájmových bodů, je třeba rozhodnout,
zda
například
20 spárovaných
bodů
ze zdrojového
souboru
s celkem
200 detekovanými body a cílového s celkem 300 body je lepším výsledkem než odlišnou technikou detekovaných šest spárovaných bodů z deseti na zdrojovém a 25 na cílovém souboru. Příkladem možných metrik jsou: •
Prosté hlasování.
•
Sumarizace jedné z metrik použité pro řazení výsledků samotného algoritmu.
•
Sumarizace, ale navíc s normalizací. Prosté hlasování zahrnuje ztrátu informace o zjištěné kvalitě shody. Pokud jeden
z algoritmů jednoznačně vyhodnotí shodu u nějaké dvojice obrázků, ale jiné algoritmy mezi těmito obrázky nenajdou žádnou podobnost a kvůli slabší shodě často hlasují pro jinou dvojici, může být pro rovnost hlasů informace o silné shodě upozaděna. Sumarizace nenormalizovaných hodnot čelí faktu, že různé algoritmy mohou pracovat s řádově odlišnými počty detekovaných bodů, což se obvykle projeví na množství spárovaných bodů. Algoritmy detekující větší množství zájmových bodů pak s vyšší pravděpodobností pro své dílčí výsledky získávají větší váhu na výsledku celkovém. Při normalizaci je naopak posílen vliv případných extrémů, které se častěji vyskytují ve výsledcích algoritmů detekujících malé množství bodů. Na základě testování algoritmů a metrik za pomoci demonstrační aplikace lze pro reálné nasazení doporučit postup: 1. Otestovat různé kombinace detekčních a deskriptivních algoritmů a jejich parametrů. Podle statistiky výsledků nad pro nasazení typickými daty vytipovat několik málo z nich tak, aby vybrané vracely dostatečné množství zájmových bodů a výsledky jejich párování svým rozptylem umožňovaly seřadit produkty. 2. Algoritmy, jejichž výsledky vzájemně silně korelují, buď ze seznamu odstranit nebo u nich změnou parametrů docílit větší odlišnosti. 3. Zvolit jednu z metrik zvážením jejich výpočetní náročnosti a subjektivního posouzení výsledků. 49
5.2.3
Klasifikace zákazníků pomocí Naive Bayes
Funkce naivního bayesovského klasifikátoru bude demonstrována na příkladu s historickými daty (datový soubor je součástí přílohy 1) tvořenými sto fiktivními záznamy o objednávkách. Každý záznam se skládá ze dvou atributů (pohlaví, platební metoda) a přiděleného ohodnocení, zda jde o nákup zákazníka s dlouhodobým potenciálem (hodnota ANO) nebo jde o jednorázový nákup (hodnota NE). Cílem učení je vytvořit takový model, který bude schopen pomocí daných kritérií klasifikovat nové objednávky. Zadáním ukázkového příkladu je odhadnout do které klasifikované třídy patří objednávka učiněná mužem platícím platební kartou. Při klasifikaci nad reálnými daty by výběr rozhodujících atributů měl být proveden na základě jejich relevance pro model, ať již subjektivně nebo pomocí některé z metod k tomu určených. Aby aplikace mohla být demonstrována ručním výpočtem, vše je zjednodušeno a ukázková data obsahují pouze dva parametry, které současně budou jako jediné pro klasifikaci použity. Postup řešení při ručním výpočtu:
1. formulace dvou hypotéz: •
dlouhodobá perspektiva h0
•
jednorázový nákup h1
2. pozorování získaná ze souboru: P(muž )=57 /100=0.57
P(karta)=26 /100=0.26 P(úvěr )=14 /100=0.14
P(hotovost )=60/100=0.6 p(muž | h0 )=32/51=0,6275
(pro zjednodušení je výpočet bez použití korekce20)
p(karta | h0 )=17 /51=0,3333 Sloupec tvoří hodnoty získané prostým počtem vyhovujících údajů ze zadání po vydělení celkovým relevantním počtem. 3. atributy zákazníka ze zadání: muž, platební karta
20 Protože hrozí, že výskyt pozorované kombinace bude nulový, se ještě při práci s reálnými daty provádějí korekce, které takové případy ošetří. Například zde by se při použití Laplaceovy korekce počítalo:
p(muž | h0 )=(32+1)/(51+T ) Kdy T=2, protože v příkladu existují dvě třídy ANO a NE. 50
4. sestavení hypotéz podle Bayesova vztahu: p(hi | muž , karta)=
p(muž , karta | hi)∗p(hi ) p(muž , karta)
přičemž pravděpodobnost současného výskytu nezávislých jevů muž a karta vychází: p(muž , karta)= p(muž )∗p( karta)=0,57∗0,26=0,1482 a podmíněné pravděpodobnosti pro výpočty jsou:
p(muž , karta| h 0)=p (muž | h 0)∗p (karta | h0 )=0,2092 to po doplnění dává pravděpodobnost hypotézy: p(h 0 | muž , karta)=0,7197 a stejným způsobem se vypočítá pravděpodobnost druhé hypotézy21:
p(h1 | muž ,karta)=0,2664 Procesem získané hodnoty udávají s jakou pravděpodobností patří takový uživatel do třídy ANO a s jakou do třídy NE. Klasifikátor by tedy rozhodl o tom, že objednávce učiněné mužem a placené kartou bude přiřazena třída představující dlouhodobou perspektivu opakovaných nákupů. Postup řešení nástrojem Weka
Nástroj Weka Knowledge Flow umožňuje modelovat aplikaci vizuálně pomocí sekvence kroků, které mají být vykonány. Jednotlivé kroky jsou představovány uzly v podobě aplikovaných činností (algoritmů, filtrů, atd.), hrany mezi uzly představují zasílaná data. V libovolném uzlu se může tok rozvětvit a větve pak mohou běžet nezávisle na sobě.
Ilustrace 14: Ukázka klasifikace v nástroji Weka
21 Protože v příkladu je dopočítána pravděpodobnost (tedy včetně vlivu pro pouhé porovnání jinak nepodstatného jmenovatele zlomku), součet obou hypotéz musí být jedna. Zde s odchylkou způsobenou zaokrouhlováním.
51
Na Ilustrace 14 je zachycena tvorba klasifikačního modelu nad stejnými daty jako v předchozím příkladě ručního výpočtu. V prvním uzlu jsou data nahrána z CSV souboru. V dalších krocích uzel ClassAsssigner označí sloupec obsahující klasifikovanou třídu a AtrributeSelection
aplikuje
algoritmus
pro výběr
atributů.
Poté
jsou
data
v CrossValidationFoldMaker rozdělena na učící a testovací množiny a předána modelu k učení. Úspěšnost získaným modelem provedené klasifikace nad testovacími daty měří poslední uzel Classifier PerformanceEvaluator. Diagram obsahuje ještě několik uzlů typu TextViewer, které jsou jedním ze způsobů, jak zobrazit stavy uzlů v pro člověka čitelné podobě. Naučený model může být uložen v serializované podobě pro pozdější použití. Ukázka proti ručnímu řešení zahrnuje navíc aplikaci algoritmu pro výběr atributů, která by v tomto konkrétním případě nebyla nutná, protože oba obsažené atributy jsou pro proces učení nezbytné. Při klasifikaci reálných dat je ale běžné, že ta zahrnují velké množství atributů s nulovým přínosem pro proces učení. Bez jejich vytřídění by vznikl komplikovaný model náchylný na přeučení a mající zbytečně velké nároky na systémové zdroje. Rovněž ukázka pro zreálnění zahrnuje rozdělení dat na učící a testovací. Weka podporuje více způsobů vytváření učících a testovacích dat. Kromě označení celého příchozího data setu za učící nebo testovací, umí jej zvoleným poměrem na tyto skupiny rozdělit nebo připravit data pro křížovou validaci. V posledním uvedeném případě použitém i v demonstrační ukázce se vytvoří ze všech dat několik kopií. Ty jsou pak stejným poměrem a náhodným výběrem rozděleny na učící a testovací data, aby nakonec na každou kopii byl samostatně aplikován učící algoritmus. Získané dílčí výsledky jsou zprůměrovány. Stejný proces učení umožňuje framework Weka realizovat i přímo z jazyka Java pomocí API, které pro tento účel poskytuje. Odlišné přístupy lze plně kombinovat a serializovaný model načítat nebo ukládat bez ohledu na to, jakým způsobem vznikl. Tato schopnost otevírá možnost model vytvořit a otestovat nad historickými daty pomocí vizuálních nástrojů a do produkčního prostředí nasadit pouze jeho finální podobu.
52
6
Shrnutí výsledků V práci byly probrány teoretické základy potřebné pro pochopení principů strojového
učení a rozebrány některé algoritmy. Jejich výběr byl ovlivněn zejména pravděpodobností, že na ně začátečník v oblasti strojového učení při svých prvotních pokusech aplikovat nabyté znalosti narazí. Důraz byl kladen zejména na intuitivnost popisu tak, aby čtenář získal o jejich činnosti alespoň základní představu dostatečnou pro implementaci za pomoci nástrojů popisovaných v dalších kapitolách. Rozebrané scénáře nasazení by měly být dostatečné pro získání ucelené představy o tom, jak při aplikaci na doménové problémy postupovat. Při implementaci demonstračních příkladů byly prakticky vyzkoušeny některé z popisovaných nástrojů, což vedlo k získání dalších znalostí umožňujících jejich vzájemné srovnání. Framework Weka lze používat jako knihovnu jazyka Java, z příkazové řádky i z několika
grafických
uživatelských
rozhraní.
Při použití
jako
knihovny
volané
ze zdrojového kódu jazyka Java se programátor může setkat s konfiguraci objektů pomocí pole textových voleb ve formátu, který je zcela odvozen od zadávání parametrů v příkazové řádce. Takový způsob bude hodnocen příznivě někým, kdo tento nástroj používá i jinak než jako externí knihovnu a ocení tak jednotné rozhraní. Oproti běžným zvyklostem programování v jazyce Java jde ale o velmi nepřirozený způsob a pokud je v kódu využíván, zhorší jeho čitelnost a ztíží údržbu zejména ve vícečlenných týmech. Dostupnou alternativou jsou pro prostředí Java přirozené settery, takže nástroj umožňuje se tohoto nebezpečí vyvarovat. Mocnou zbraní hovořící pro tento framework je schopnost ukládat naučené modely v serializované podobě a přenášet je mezi všemi podporovanými rozhraními. Mnohé z tříd zpřístupňujících algoritmy strojového učení frameworkem Weka je možné využít i v kombinaci s výrazně štíhlejší knihovnou Java-ML. Ta disponuje API založeném na návrhu společných veřejných rozhraní, jež jsou implementovány třídami reprezentujícími jednotlivé algoritmy. Kromě vlastních implementací obsahuje i třídy zapouzdřující právě algoritmy z frameworku Weka. Knihovna je dobře zdokumentována a k dispozici je množství demonstračních příkladů pro její nasazení. Vše je uzpůsobeno pro intuitivní používání z jazyka Java. Také Mallet netvoří pouze knihovna jazyka Java, ale poskytuje i nástroje pro použití frameworku z příkazové řádky. Případné nasazení jako knihovny stěžuje nedostatečná dokumentace, kdy se na webových stránkách projektu nachází povrchní popis nezbytný 53
pro implementaci základní funkcionality. Současně autory zdrojových kódů nelze označit za fanoušky javadoc komentářů, proto ani generovaná dokumentace k API nenabízí informace v šíři, jež by mohla. Při více specifických požadavcích bude případný zájemce odkázán na studium zdrojového kódu, což pro reálné nasazení znamená velké mínus. Apache Commons Math je obecná matematická a statistická knihovna s vynikající dokumentací, která ovšem pro případné nasazení v oblasti strojového učení trpí vážnými nedodělky a je pro tyto účely v aktuální verzi spíše nepoužitelná. Naopak se zdá být dobrou volbou při úkolech, ve kterých jde primárně o statistiku a případné požadavky na metody strojového učení si vystačí s tím málem knihovnou podporovaným. Mezi její přednosti patří prakticky nulová míra závislostí na jiných knihovnách a relativně malá velikost. Pro účely rozpoznávání podobností mezi bitmapovými obrázky se jako plnohodnotná alternativa k běžně používaným způsobům osvědčila metoda využívající zájmové body detekované knihovnou BoofCV. Tam kde je výsledek analýzy použit pro nekritické účely, jakým je například doporučení podobných produktů na stránkách internetového obchodu, může být pro zjednodušení použit i jen jediný empiricky vyzkoušený detektor a výsledky budou stále uspokojivé. Na druhou stranu technika zájmových bodů představuje pouze jeden z možných přístupů a například nezohledňuje celkové barevné vyznění obrázků. To přitom může být hodnotitelem subjektivně vnímáno jako nejdůležitější kritérium. Proto je vhodné tento způsob analýzy použít paralelně s dalšími založenými na jiných technikách a získané dílčí výsledky vhodně kombinovat.
54
7
Závěry a doporučení Při implementaci demonstračních příkladů bylo prakticky ověřeno, že programátor
nepotřebuje znát do detailu veškeré teoretické pozadí použitých algoritmů. Při nasazení existujících knihoven a nástrojů si vystačí se základními teoretickými znalostmi a alespoň základní představou, jak jím používané algoritmy pracují. Pro přípravu dat je nutné dodržet některá pravidla, která jsou obecná a platí napříč všemi metodami. Rozhodnout, o jakou typovou úlohu se jedná, jaký algoritmus a nástroj bude použit. Připravit data do formátu podporovaného použitým nástrojem, při zpracovávání pouze části dat dodržet pravidla pro výběr vzorku, nekomplikovat model zbytečnými parametry a před procesem učení hodnoty atributů v datech normalizovat. Pro začátek je nejlepší použít jednodušší rychleji implementovatelný algoritmus a otestovat jeho výsledky pomocí křížové validace. Potom se rozhodnout, zda je nutné zvýšit množství dat nebo atributů, regularizovat nebo zvolit úplně jiný algoritmus. Při rozhodování může pomoci detailní analýza případů, kdy algoritmus na testovacích datech selhal. Pokud lze v těchto selháních vysledovat nějaký řád, měl by být zahrnut do nového modelu. Při testování demonstrační aplikace pro hledání podobných bitmapových obrázků s produkty vyplynulo, že zvolená metoda porovnání pomocí zájmových bodů řeší jen jeden typ podobnosti mezi obrázky a s některými obrázky si poradí velice špatně. Zejména těmi, kde produkt není vyfocen na jednobarevném pozadí. Pro nekritické aplikace, jakým je doporučení alternativního produktu zákazníkovi formou rychlé navigace, je ale vyhovující. Z výkonnostních důvodů je vhodné analýzu omezit jen na jeden vyzkoušený detektor a data by měla být pro detekci předpřipravena nebo vytříděna. Pro kritičtější aplikace by neměl být tento způsob používán samostatně, ale spíše jeho výsledky použity v kombinaci s popisem získaným jiným způsobem. Například vytvořit popisný vektor na základě barevnosti nebo tvarů segmentovaného obrázku a o popis podle detekovaných zájmových bodů ho pouze rozšířit. Současně použitá knihovna BoofCV disponuje i jinými způsoby popisu obrázku, které si zaslouží stát se předmětem dalšího zkoumání. Konkrétně popisné vektory založené na atributech získaných detekcí hran nebo kombinace detekce objektů se zohledněním pouze vnitřní části hlavního detekovaného objektu do popisného vektoru.
55
8
Seznam použité literatury
[1] Machine learning. In: Wikipedia: the free encyclopedia [online]. San Francisco (CA): Wikimedia Foundation, 2001- [cit. 2013-08-13]. Dostupné z: http://en.wikipedia.org/wiki/Machine_learning [2] ALPAYDIN, Ethem. Introduction to machine learning. 2nd ed. Massachusetts: MIT Press, c2010, xl, 537 s. ISBN 978-0-262-01243-0. [3] ILLICH, Michal. Strojové učení z rychlíku. Slideshare [online]. 2013 [cit. 2013-08-13]. Dostupné z: http://www.slideshare.net/michalillich/prez-develcz3 [4] ČECH, Pavel a Vladimír BUREŠ. Podniková informatika. Vyd. 1. Hradec Králové: Gaudeamus, 2009, 232 s. ISBN 978-807-0414-798. [5] E-commerce. In: Wikipedia: the free encyclopedia [online]. San Francisco (CA): Wikimedia Foundation, 2001- [cit. 2013-08-13]. Dostupné z: http://en.wikipedia.org/wiki/E-commerce [6] SMOLA, Alex. Introduction to Machine Learning. Cambridge: Cambridge University Press, 2008. ISBN 0-521-82583-0. Dostupné z: http://alex.smola.org/drafts/thebook.pdf [7] NILSSON, Nils J. Introduction to Machine Learning. Stanford Artificial Intelligence Laboratory [online]. 2008 [cit. 2013-08-13]. Dostupné z: http://ai.stanford.edu/~nilsson [8] PRINCIPE, José C, Neil R EULIANO a W LEFEBVRE. Neural and adaptive systems: fundamentals through simulations. New York: Wiley, c2000, xiii, 656 s. ISBN 04-713-5167-9. Dostupné z: http://www.nd.com/NSBook/ [9] SHROFF, Gautam. Web Intelligence and Big Data. Coursera [online]. 2012 [cit. 2013-08-13]. Dostupné z: https://www.coursera.org/course/bigdata [10] BERKA, Petr. 4IZ450 Dobývání znalostí z databází [online]. 2013 [cit. 2013-08-13]. Dostupné z: http://sorry.vse.cz/~berka/4IZ450/ hzuz [11] Ensemble learning. In: Wikipedia: the free encyclopedia [online]. San Francisco (CA): Wikimedia Foundation, 2001- [cit. 2013-08-13]. Dostupné z: http://en.wikipedia.org/wiki/Ensemble_learning [12] Bootstrap aggregating. In: Wikipedia: the free encyclopedia [online]. San Francisco (CA): Wikimedia Foundation, 2001- [cit. 2013-08-13]. Dostupné z: http://en.wikipedia.org/wiki/Bootstrap_aggregating [13] RUSSELL, Stuart J a Peter NORVIG. Artificial intelligence: a modern approach. Englewood Cliffs, N.J.: Prentice Hall, c1995, xxviii, 932 p. ISBN 01-310-3805-2. [14] NG, Andrew. Machine Learning. Coursera [online]. 2013 [cit. 2013-08-13]. Dostupné z: https://www.coursera.org/course/ml [15] MCCALLUM, Andrew Kachites. MALLET: A Machine Learning for Language Toolkit [online]. 2002 [cit. 2013-08-13]. Dostupné z: http://mallet.cs.umass.edu [16] RIFKIN, Ryan. Multiclass Classification. Statistical Learning Theory and Applications [online]. 2008 [cit. 2013-08-13]. Dostupné z: http://www.mit.edu/~9.520/spring09/Classes/multiclass.pdf [17] ŠLERKA, Josef. O sentiment analýze bez sentimentu aneb jeden malý experiment. Lupa.cz [online]. 2011 [cit. 2013-08-13]. Dostupné z: http://www.lupa.cz/clanky/o-sentiment-analyze-bez-sentimentu-aneb-jeden-maly-experiment/
56
[18] HSU, Chih-Wei, Chih-Chung CHANG a Chih-Jen LIN. A Practical Guide to Support Vector Classification. National Taiwan University [online]. April 15, 2010. 2003 [cit. 2013-08-13]. Dostupné z: http://www.csie.ntu.edu.tw/~cjlin/papers/guide/guide.pdf [19] TONG a Edward CHANG. Support vector machine active learning for image retrieval. In: CHANG, Edward. Proceedings ACM Multimedia 2001: Ottawa, Canada, September 30-October 5, 2001. New York: Association for Computing Machinery, c2001, s. 107-118. ISBN 1581133944. DOI: 10.1145/500141.500159. [20] HLAVÁČ, Václav. Učení bez učitele. Center for Machine Perception [online]. [2006] [cit. 2013-08-13]. Dostupné z: http://cmp.felk.cvut.cz/~hlavac/Public/TeachingLectures/UceniBezUcitele.pdf [21] Shluková analýza. KELBEL, Jan a David ŠILHÁN. Gerstner Laboratory [online]. [2005] [cit. 2013-08-13]. Dostupné z: http://gerstner.felk.cvut.cz/biolab/X33BMI/slides/KMeans.pdf [22] K-means clustering. In: Wikipedia: the free encyclopedia [online]. San Francisco (CA): Wikimedia Foundation, 2001- [cit. 2013-08-13]. Dostupné z: http://en.wikipedia.org/wiki/K-means_clustering [23] MATERNA, Jiří. Sémantická analýza textů. In: Blog fulltextového týmu [online]. 2011-2012 [cit. 2013-08-14]. Dostupné z: http://fulltext.sblog.cz/2012/02/14/semanticka-analyza-textu-7/ [24] ŘEHŮŘEK, Radim a Petr SOJKA. Software Framework for Topic Modelling with Large Corpora. In: Proceedings of the LREC 2010 Workshop on New Challenges for NLP Frameworks. Valletta, Malta: University of Malta, 2010, s. 46-50. ISBN 2-9517408-6-7. Dostupné z: http://is.muni.cz/publication/884893/en [25] Topic Models. In: BLEI, David. Videolectures [online]. 2009 [cit. 2013-08-13]. Dostupné z: http://videolectures.net/mlss09uk_blei_tm/ [26] GILLICK, Dan, Arlo FARIA a John DENERO. MapReduce: Distributed Computing for Machine Learning. International Computer Science Institute [online]. 2006 [cit. 2013-08-14]. Dostupné z: http://www1.icsi.berkeley.edu/~arlo/publications/gillick_cs262a_proj.pdf [27] INGERSOLL, Grant. Introduction to Apache Mahout. In: Slideshare [online]. [2010] [cit. 2013-08-14]. Dostupné z: http://www.slideshare.net/gsingers/intro-to-mahout-dc-hadoop [28] Google Prediction API [online]. 2010 [cit. 2013-08-14]. Dostupné z: https://developers.google.com/prediction/ [29] The Zettabyte Era—Trends and Analysis. CISCO SYSTEMS, Inc. Cisco [online]. 2013 [cit. 2013-08-14]. Dostupné z: http://www.cisco.com/en/US/solutions/collateral/ns341/ns525/ns537/ns705/ns827/VNI_Hyperconnectivity_WP. pdf [30] SANTOS, Rafael. Java Image Processing Cookbook [online]. [2003] [cit. 2013-08-14]. Dostupné z: http://www.lac.inpe.br/JIPCookbook/ [31] SIAGIAN, Christian. Gist/Context of a Scene. University of Southern California [online]. [2007] [cit. 2013-08-14]. Dostupné z: http://ilab.usc.edu/siagian/Research/Gist/Gist.html [32] Detektory hran a ekvalizace histogramu. DEPARTMENT OF IMAGE PROCESSING. Institute of Information Theory and Automation of the ASCR [online]. [2013] [cit. 2013-08-14]. Dostupné z: http://zoi.utia.cas.cz/files/roz1/ROZ1-04-8546975.pdf
57
[33] TATIRAJU, Suman a Avi MEHTA. Image Segmentation using k-means clustering, EM and Normalized Cuts. In: Donald Bren School of Information and Computer Sciences [online]. [2010] [cit. 2013-08-14]. Dostupné z: http://www.ics.uci.edu/~dramanan/teaching/ics273a_winter08/projects/avim_report.pdf [34] JOHANSSON, Björn. A Survey on: Contents Based Search in Image Databases. In: Linköpings universitet [online]. 2000 [cit. 2013-08-14]. Dostupné z: http://www.isy.liu.se/cvl/Projects/VISIT-bjojo/ [35] SKALSKÁ, Hana. Stochastické modelování. Hradec Králové: Gaudeamus, 1998, 132 s. ISBN 80-704-1039-6. [36] HALL, Mark, Eibe FRANK, Geoffrey HOLMES, Bernhard PFAHRINGER, REUTEMANN, a Ian H. WITTEN. The WEKA Data Mining Software: An Update. In: SIGKDD Explorations: Volume 11, Issue 1. 2009, s. 10-18. Dostupné z: http://www.kdd.org/sites/default/files/issues/11-1-2009-07/p2V11n1.pdf [37] ABEEL, Thomas, Yves VAN DE PEER a Yvan SAEYS. Java-ML: A Machine Learning Library. In: Journal of Machine Learning Research. Journal of Machine Learning Research, 2009, s. 931-934. Dostupné z: http://jmlr.org/papers/v10/abeel09a.html [38] ROSTEN, Edward, Reid PORTER a Tom DRUMMOND. FASTER and better: A machine learning approach to corner detection. In: IEEE Trans. Pattern Analysis and Machine Intelligence [online]. 2010, s. 105-119 [cit. 2013-08-14]. Dostupné z: http://www.edwardrosten.com/work/rosten_2008_faster_presentation.pdf
58
9
Seznam obrázků a tabulek Použité obrázky
Ilustrace 1: Aplikace strojového učení........................................................................................5 Ilustrace 2: Ukázka stabilizace výsledků technikou Bagging...................................................11 Ilustrace 3: Model regresní analýzy..........................................................................................12 Ilustrace 4: Ukázka klasifikace rozhodovacím stromem..........................................................19 Ilustrace 5: Ukázka aplikace algoritmu Nearest Neighbour.....................................................20 Ilustrace 6: Problém přeučení při SVM klasifikaci...................................................................22 Ilustrace 7: Shlukování algoritmy K-Means a EM...................................................................24 Ilustrace 8: Příklad získání obratu pro jednotlivá města metodou MapReduce........................28 Ilustrace 9: Složitost alternativ ke strojovému rozpoznání jazyka............................................32 Ilustrace 10: Screenshot vyhledávání vizuálně podobných obrázků vyhledávačem Google....36 Ilustrace 11: Princip algoritmu FAST pro detekci rohů v obrázku...........................................43 Ilustrace 12: Ukázka výstupu demonstrační aplikace Agregátor zpráv....................................46 Ilustrace 13: Ukázka výstupu aplikace pro hledání podobností pomocí zájmových bodů.......47 Ilustrace 14: Ukázka klasifikace v nástroji Weka.....................................................................51 Seznam tabulek Tabulka 1: Příklady aplikací strojového učení............................................................................5 Tabulka 2: Příklady oblastí strojového učení dotýkající se problematiky doporučení zákazníkovi.................................................................................................................................7 Tabulka 3: Příklady doporučených algoritmů podle typu úloh a parametrů...............................8 Tabulka 4: Srovnání iterativních metod....................................................................................13 Tabulka 5: Příklady klasifikačních úloh....................................................................................16
59
10
Přílohy 1. zdrojové kódy a datové soubory demonstračních aplikací ve formě archivu Eclipse workspace 2. archiv spustitelných souborů demonstračních aplikací 3. zadání diplomové práce
60
