doc. Ing. Jan Janoušek, Ph.D.
vedoucí katedry
prof. Ing. Pavel Tvrdík, CSc.
děkan
Č
ESKÉ VYSOKÉ UČENÍ TECHNICKÉ VP
RAZEF
AKULTA INFORMAČNÍCH TECHNOLOGIÍZADÁNÍ DIPLOMOVÉ PRÁCE
Název: Analýza a predikce chování uživatelů na aukčních webech Student: Bc. Lukáš Kratochvíl
Vedoucí: doc. RNDr. Ing. Marcel Jiřina, Ph.D.
Studijní program: Informatika Studijní obor: Znalostní inženýrství
Katedra: Katedra teoretické informatiky Platnost zadání: Do konce zimního semestru 2018/19
Pokyny pro vypracování
Cílem práce je analyzovat chování uživatelů, kteří se účastní aukcí (dražeb) na aukčních webech a následně predikovat budoucí vývoj aukce (odhad finálního stavu, tj. jaké ceny bude dosaženo).
1) Prozkoumejte nejznámější aukční weby (Aukro, eBay), způsob jejich fungování (systém přihazování) a pořiďte sadu dat vzorových případů ukončených aukcí.
2) Analyzujte chování uživatele a navrhněte prediktivní model pro predikci cílové dosažené ceny.
3) Model implementujte ve vhodném programovacím jazyku.
4) Vyhodnoťte dosažené výsledky, porovnejte dosaženou přesnost modelu (správnost odhadu cílové ceny) a diskutujte další možné směry zlepšení modelu.
Seznam odborné literatury
Dodá vedoucí práce.
České vysoké učení technické v Praze Fakulta informačních technologií Katedra teoretické informatiky
Diplomová práce
Analýza a predikce chování uživatelů na aukčních webech
Bc. Lukáš Kratochvíl
Vedoucí práce: doc. RNDr. Ing. Marcel Jiřina, Ph.D.
8. května 2017
Poděkování
Děkuji za poskytnuté rady od pana doc. RNDr. Ing. Marcel Jiřina, Ph.D., jehož cenné zkušenosti mi pomáhaly při tvorbě této práce. Děkuji mu za tr- pělivost, kterou věnoval odpovědím na mé otázky týkjaící se problematiky analýzy a predikce. Dále bych chtěl vyjádřit své díky rodině a blízkým, kteří mě podporovali po celou dobu studií.
Prohlášení
Prohlašuji, že jsem předloženou práci vypracoval(a) samostatně a že jsem uvedl(a) veškeré použité informační zdroje v souladu s Metodickým pokynem o etické přípravě vysokoškolských závěrečných prací.
Beru na vědomí, že se na moji práci vztahují práva a povinnosti vyplývající ze zákona č. 121/2000 Sb., autorského zákona, ve znění pozdějších předpisů.
V souladu s ust. § 46 odst. 6 tohoto zákona tímto uděluji nevýhradní oprávnění (licenci) k užití této mojí práce, a to včetně všech počítačových programů, jež jsou její součástí či přílohou, a veškeré jejich dokumentace (dále souhrnně jen
„Dílo“), a to všem osobám, které si přejí Dílo užít. Tyto osoby jsou oprávněny Dílo užít jakýmkoli způsobem, který nesnižuje hodnotu Díla, a za jakýmkoli účelem (včetně užití k výdělečným účelům). Toto oprávnění je časově, teri- toriálně i množstevně neomezené. Každá osoba, která využije výše uvedenou licenci, se však zavazuje udělit ke každému dílu, které vznikne (byť jen zčásti) na základě Díla, úpravou Díla, spojením Díla s jiným dílem, zařazením Díla do díla souborného či zpracováním Díla (včetně překladu), licenci alespoň ve výše uvedeném rozsahu a zároveň zpřístupnit zdrojový kód takového díla ale- spoň srovnatelným způsobem a ve srovnatelném rozsahu, jako je zpřístupněn zdrojový kód Díla.
V Praze dne 8. května 2017 . . . .
České vysoké učení technické v Praze Fakulta informačních technologií
c 2017 Lukáš Kratochvíl. Všechna práva vyhrazena.
Tato práce vznikla jako školní dílo na Českém vysokém učení technickém v Praze, Fakultě informačních technologií. Práce je chráněna právními před- pisy a mezinárodními úmluvami o právu autorském a právech souvisejících s právem autorským. K jejímu užití, s výjimkou bezúplatných zákonných li- cencí, je nezbytný souhlas autora.
Odkaz na tuto práci
Kratochvíl, Lukáš. Analýza a predikce chování uživatelů na aukčních webech.
Diplomová práce. Praha: České vysoké učení technické v Praze, Fakulta infor- mačních technologií, 2017.
Abstrakt
Cílem této práce bylo analyzovat chování uživatelů na aukčních webech a pre- dikovat konečnou cenu aukcí. Použitá data byla stažena ze stránek Aukro.cz pomocí nástroje TextMiningSuite. Návrh předzpracování dat, množin atri- butů (při kterých koncová cena dosahuje požadované hranice závislosti) a učí- cích algoritmů byl následován implementační částí realizující zmíněný postup.
Na konci práce byla určena množina atributů nejvíce ovliňující uživatele při příhozech. Dále byl nalezen nejlepší algoritmus (a jeho nastavení) prediku- jící koncovou cenu aukce. Následovalo navržení možných kroků vedoucích ke zlepšení výsledků predikce.
Klíčová slova strojové učení, Python, selekce atributů, regrese, klasifikace, predikce koncových cen online aukcí, analýza uživatelů na aukčních webech
Abstract
The goal of this thesis was to analyze behavior of users on auction websi- tes and to predict final prices of auctions. Used data was downloaded from Aukro.cz website by using TextMiningSuite util. Design of preprocessing, sets of atributes (which meet required level of dependency according to final price) and learning algorithms was followed by implementation realizing mentioned
procedure. At the end of the thesis a set of the most user influential atributes was defined. Then the best auction final price predicting algorithm (and its settings) was found. This section was followed by suggestion of steps that may lead to improve results of predictions.
Keywords machine learning, Python, feature selection, regression, classifi- cation, predicting final prices of online auctions, analysis of users on auction websites
x
Obsah
Úvod 1
1 Aukční servery a jejich principy 5
1.1 Aukro . . . 5
1.2 eBay . . . 7
2 Současná řešení 11 3 Použité metody při analýze dat a predikci 15 3.1 Metody analýzy dat . . . 15
3.2 Predikovací modely . . . 17
4 Formát dat a jejich získání 25 4.1 Formát dat . . . 25
4.2 Získání dat . . . 26
5 Analýza 29 5.1 Selekce atributů . . . 29
6 Návrh možných řešení 45 6.1 Předzpracování dat . . . 45
6.2 Výběr atributů . . . 47
6.3 Použité predikovací modely . . . 47
6.4 Učení predikovacích modelů . . . 47
6.5 Zpracování výsledků . . . 48
7 Technologie 49 8 Výsledky experimentů 51 8.1 Výběr parametrů modelů . . . 51
8.2 Zobrazení a vyhodnocení výsledků . . . 52
8.3 Nalezení nejlepšího řešení . . . 68
9 Diskuse 73
Závěr 75
Literatura 77
A Seznam použitých zkratek 81
B Obsah přiloženého CD 83
xii
Seznam obrázků
1.1 Ukázka úvodní stránky webu Aukro.cz . . . 5
1.2 Ukázka úvodní stránky webu eBay . . . 8
3.1 Příklady Pearsonových korelačních koeficientů s ukázkami dat v gra- fech . . . 16
3.2 Studentovo rozdělení . . . 17
3.3 Příklad klasifikačního rozhodovacího stromu . . . 18
3.4 Příklad regresního rozhodovacího stromu . . . 19
3.5 Příklad lomené lineární funkce vytvořené pomocí MARS metody . 19 3.6 Příklad modelu SVR a trénovacích dat . . . 20
3.7 Příklad modelu KNN při klasifikaci dat . . . 21
3.8 Příklad prediktorů modelu SVM a trénovacích dat . . . 22
4.1 Příklad aukce při vyhledávání . . . 25
4.2 Příklad detailního zobrazení aukce . . . 26
4.3 Příklad historie příhozů aukce . . . 26
5.1 Graf pravděpodobnosti (ne)využití služby Aukrobot na normalizo- vané ceně . . . 32
5.2 Graf závislosti koncových cen skončených aukcí na normalizova- ných koncových cenách . . . 33
5.3 Graf znázorňující růst ceny v čase . . . 36
5.4 Graf Paersonových korelačních koeficientů jednotlivých atributů extrahovaných z aukcí . . . 37
5.5 Graf Pearsonových korelačních koeficinetů atributů se znázorněním jejich selekce . . . 38
5.6 Graf Pearsonových korelačních koeficinetů atributů neobsahující informace o denních příhozech se znázorněním jejich selekce . . . . 40
5.7 Graf Pearsonových korelačních koeficinetů atributů obsahující in- formace o denních příhozech se znázorněním jejich selekce . . . 41
Seznam tabulek
4.1 Ukázka seznamu aukcí vytvořeného programem TextMiningSuite ze stažených dat z Aukra . . . 27 4.2 Ukázka historie příhozů aukce vytvořené programem TextMining-
Suite ze stažených dat z Aukra . . . 27 5.1 Pearsonovy korelační koeficienty a testy hladin významnosti pro
atributy extrahované ze seznamu vyhledávaných aukcí . . . 33 5.2 Pearsonovy korelační koeficienty a testy hladin významnosti pro
atributy extrahované z detailů aukcí . . . 35 5.3 Výsledky rekurzivní eliminační metody pro výběr atributů využí-
vající SVR model (všechny atributy) . . . 42 5.4 Výsledky rekurzivní eliminační metody pro výběr atributů využí-
vající SVR model (denní atributy) . . . 42 5.5 Výsledky rekurzivní eliminační metody pro výběr atributů využí-
vající SVR model (nedenní atributy) . . . 43 8.1 Výsledky predikce pro rozhodovací strom (CART) při využití všech
atributů . . . 53 8.2 Výsledky predikce pro rozhodovací les při využití všech atributů . 54 8.3 Výsledky predikce pro SVR algoritmus při využití všech atributů . 55 8.4 Výsledky predikce pro k-nejbližsích sousedů algoritmus při využití
všech atributů . . . 56 8.5 Výsledky predikce pro SVM algoritmus při využití všech atributů . 57 8.6 Výsledky predikce pro rozhodovací strom (CART) při využití ne-
denních atributů . . . 58 8.7 Výsledky predikce pro rozhodovací les při využití nedenních atributů 58 8.8 Výsledky predikce pro SVR algoritmus při využití nedenních atributů 60 8.9 Výsledky predikce pro k-nejbližsích sousedů algoritmus při využití
nedenních atributů . . . 61 8.10 Výsledky predikce pro SVM algoritmus při využití nedenních atributů 62
Seznam tabulek
8.11 Výsledky predikce pro rozhodovací strom (CART) při využití den- ních atributů . . . 62 8.12 Výsledky predikce pro rozhodovací les při využití denních atributů 63 8.13 Výsledky predikce pro SVR algoritmus při využití denních atributů 64 8.14 Výsledky predikce pro k-nejbližsích sousedů algoritmus při využití
denních atributů . . . 65 8.15 Výsledky predikce pro SVM algoritmus při využití denních atributů 66 8.16 Výsledky predikce pro rozhodovací strom (CART) při využití tře-
tiny všech, denních a nedenních atributů získaných pomocí RFE . 67 8.17 Výsledky predikce pro rozhodovací les při využití třetiny všech,
denních a nedenních atributů získaných pomocí RFE . . . 67 8.18 Výsledky predikce pro SVR algoritmus při využití třetiny všech,
denních a nedenních atributů získaných pomocí RFE . . . 69 8.19 Výsledky predikce pro k-nejbližsích sousedů algoritmus při využití
třetiny všech, denních a nedenních atributů získaných pomocí RFE 70 8.20 Výsledky predikce pro SVM algoritmus při využití třetiny všech,
denních a nedenních atributů získaných pomocí RFE . . . 71
xvi
Úvod
Snad každý rozumný člověk se snaží ušetřit za nákupy co nejvíce peněz (v zá- silosti na kvalitě) a zbytečně neplatit víc, než je třeba. Samozřejmě je možné procházet nákupní centra nebo obchody a hledat nejnižší ceny zboží třeba (na- příklad v akcích). To je však časově neefektivní.
V dnešní době lze časovou náročnost snížit pomocí internetu. Téměř každá domácnost vlastní zařízení, pomocí kterého se může k síti připojit. Člověk si pak objedná požadované zboží až domů.
Pokud k tomu ještě nakupující připustí, že není potřeba kupovat naprosto nový předmět za plnou cenu, je zde možnost pořídit zboží za cenu, kterou je kupující ochoten zaplatit v závislosti na kvalitě, a to pomocí aukčních ser- verů nebo bazarů. Většinou jde o předměty od ostatních uživatelů, které už nepotřebují, vyměnili za novější nebo je vyhráli v soutěži a chtějí je zpeněžit.
Výhodou i nevýhodou aukcí je, že jsou založeny na principu přihazování:
kdo nabídne nejvíce peněz, tomu je za tuto částku předmět prodán. Pokud by byla momentální cena po příhozu kupujícího menší, než cena, kterou je ochotný zaplatit (nebo jakou stojí stejný předmět v bazaru), lze aukci pova- žovat za výhodnou a má smysl přihodit.
Opačně tomu je, pokud se cena předmětu vyšplhala do takové výše, která už není pro uživatele zajímavá. V tom případě již nákupčí přestane přiha- zovat a raději se podívá po stejném nebo obdobném výrobku za příznivější cenu. Naopak bazarové zboží má cenu fixní, tudíž se jedná o obdobu nákupu v elektronickém obchodě, a proto se jím práce nebude dále zabývat.
Zde se lze setkat s odlišným problémem, než je jen prohledávání aukčních serverů, a to s predikcí koncové ceny. Každý uživatel by si přál vědět reálnou koncovou cenu, podle které by se rozhodoval, jestli se aukce účastnit a sledovat její průběh, nebo si říct, že bude cena příliš vysoká, nezabývat se touto aukcí a raději se podívat po jiné.
Odahdnout koncovou cenu předmětu na základě jeho informací by bylo jistou výhodou i pro prodávající. Ti by pak mohli aukci nastavit taková data,
Úvod
která by přesvědčila více lidí přihodit a tím by cena vzrostla. Samozřejmě by data byla zároveň pravdivá.
Aukce nejsou záležitostí posledních let. Za autora první historicky zmíněné aukce je obvykle považován Herodotos, jenž zaznamenal babylonský zvyk, kdy muži dražili ženy, se kterými se následně oženili. Další zmínky o aukcích provází celý antický svět od Říma až k Japonsku. Při takových aukcích se prodávaly běžné komodyty jako je dobytek nebo i vzácné předměty – jako jsou diamanty a umělecká díla [1].
Dražba může mít také důležitou roli při získávání hodnoty prodávaného zboží. Například u starožitností a uměleckých děl, která nejsou přesně ohod- nocena, lze využít nejvyššího příhozu k určení ceny předmětu.
Při prodeji je více či méně potřeba vynaložit úsilí a peníze na hledání kupců a vyjednávání s nimi. S nástupem online aukcí se obě zmíněné vlastnosti výrazně změnily. Cena na najití kupců výrazně klesla a díky většímu počtu zúčastněných lze lépe najít hodnotu předmětu aukce. Proto není divu, že se internetové aukce staly tak populárními [2].
Existují 4 základní druhy aukcí [3]: anglická, holandská, obálková a Vic- kreyova.
Anglická aukce je nejběžněji využívaná metoda, kdy cena zboží roste po- mocí jednotlivých příhozů od nakupujících. Ti vidí, jaká ja nejvyšší hodnota, proto je vhodná právě pro případy zjišťování cen.
Další je holandská, kde se cena oproti předchozímu snižuje. Vyvolávající nejdříve navrhne první vyšší nabídku a postupně ji snižuje, dokud se někdo o předmět za danou hodnotu nepřihlásí. Běžné využití této metody je právě v Holadnsku (proto tento název) při prodeji řezaných květin, dále při prodeji rychle se kazícího zboží jako jsou ryby.
Obálková metoda se od prvních dvou zásadně liší – všichni účastníci aukce se rozhodnou, za jakou nejvyšší cenu jsou ochotni koupit komoditu, a tato nabídka se poté současně porovná s ostatními, aniž by kdokoli věděl, jakou částku nabídli ostatní. Podobně jako v anglické aukci vyhrává nabídka s nej- vyšší cenou. Využítí této metody lze najít při vypisování veřejných soutěží.
Poslední základní metodou je Vickreyova aukce, kdy stejně jako v před- chozím případě nakupující nevědí o ostatních nabídkách a nemají možnost případně změnit své rozhodnutí. Rozdíl nastává na konci aukce, kdy nejvyšší přihazující vyhrává předmět, zaplatí za něj ale druhou nejvyšší nabídnutou částku. Tato metoda má spíše teoretický význam, v praxi se objevuje jen zřídka.
Používání aukčních serverů k nákupům a prodejům lze doložit čísly. Na konci posledního kvartálu 2016 eBay oznámil zvýšení počtu aktivních uživatelů na 167 milionů a prodané zboží v hodnotě 22.3 miliardy dollarů [4].
Cílem práce je analyzovat a predikovat chování uživatelů na aukčních webech. Toto chování, které závisí na informacích u jednotlivých aukcích, se odrazí ve výši koncové ceny. Proto bude potřeba nalézt takovou množinu atri- 2
butů aukcí, která bude mít největší vliv na koncovou cenu. Tím se splní první část práce – analýza chování uživatelů.
Druhá část, která se zabývá predikcí, vychází z té první – na základě vybra- ných množin atributů se budou provádět experimenty s různými predikčními modely a zvolí se ten s největší úspěšností odhadu koncové ceny. Tak by se splnila i druhá část práce.
Jako výchozí a jediný aukční server bylo použito české Aukro.cz [5].
Základem všeho jsou data, ze kterých bude čerpáno. Ta budou získána přímo ze stránek pomocí nástroje, který na základě stažených zdrojových kódů získá potřebné atributy jako jsou datum konce aukce nebo historie příhozů.
Ty budou předzpracovány do formy vhodné pro následující experimenty – informace o aukcích budou převedeny do jedné tabulky, kde každý záznam bude představovat jednu aukci. U popisu samotné aukce nebude třeba nikterak měnit atributy.
Horší to bude v případě historie příhozů, kde aukce mohou mít různý počet příhozů. Převod celé historie do jediného záznamu tabulky bude proveden rozčleněním příhozů do dní v týdnu, ve kterých se udály (například počet příhozů, které se udály v pondělí).
Pro analýzu chování budou tyto atributy ohodnoceny pomocí Pearsonova korelačního koeficientu a rekurzivní eliminační metody (RFE). Oba přístupy naleznou vhodné množiny atributů, které budou popisovat, na co uživatel nejvíce reaguje a podle čeho se rozhoduje, zda přihodí nebo ne.
Dále různé množiny atributů naučí vybrané modely predikovat a následně budou jejich predikční vlastnosti porovnány. Kvůli větší důvěryhodnosti vý- sledků bude využito křížové validace [6].
Práce bude završena stanovením takové množiny atributů, jež nejvíce ovliv- ňuje koncovou cenu předmětu, a nalezením nejvhodnějšího predikčního algo- ritmu a jeho nastavení. Závěrem budou též navrženy kroky, které mohou vy- lepšit výsledky predikce.
Práce bude brána jako „proof of concept“ a skládá se ze dvou částí: z te- oretické a realizace.
V první teoretické budou rozebrány aukční servery (Aukro a eBay), jak s nimi pracovat a co umožňují. Následně budou rozebrány práce zabývající se obdodbnou tematikou, tedy predikcí koncové ceny aukce. V další kapitole bu- dou zmíněny algoritmy a metody, pomocí kterých bude atributům přiřazena důležitost (vliv na koncovou cenu aukce) a které budou predikovat hodnotu draženého předmětu za využití tětchto atributů. Dále bude popsáno, jak data vypadají na stránkách, jak se stahují a v jaké formě se s nimi bude zachá- zet. Selekce atributů nejvíce ovlivňujíví chování uživatelů (a s tím související finální cenu předmětů) bude rozebrána v kapitole Analýza. Předešlé kapitoly mi poslouží k navržení řešení, která budou implementována.
Tím se práce posune do druhé části, tj. realizace. V té budou provedeny experimenty vzniklé na základě návrhů. Jejich výsledky budou diskutovány v následující kapitole.
Kapitola 1
Aukční servery a jejich principy
V této kapitole budou rozebrány dva aukční servery. Prvním bude server Aukro, určený především pro české uživatele, a druhým bude eBay, který je využíván celosvětově. U obou dvou serverů bude popsáno, jak se na nich regis- trovat a jak obchodovat (prodávat a nakupovat). Také budou zmíněny základní funkcionality, které servery poskytují.
1.1 Aukro
Aukro je největším českým online tržištěm založené roku 2003 Václavem Liš- kou, kde mohou registrované osoby prodávat i kupovat zboží. V roce 2016 bylo v systému registrováno 3.8 milionů uživatelů a každou minutu se zde prodá průměrně 23 položek 1.1.
Obrázek 1.1: Ukázka úvodní stránky webu Aukro.cz zabývajícího se aukcemi zejména na českém trhu.
1. Aukční servery a jejich principy
1.1.1 Registrace
Pokud se člověk rozhodne na Aukru nakupovat, obejde se bez registrace. Avšak pokud se zaregistruje (bezplatně), umožní mu to využívat veškeré funkce ser- veru, jako je například seznam koupeného zboží. V případě prodeje zboží je registrace nutná.
Nejdříve je potřeba vybrat, zda se bude jednat o soukromý nebo podni- katelský účet. V tomto bodu se na základě výběru jedince registrace větví.
Jelikož se tato práce zabývá chováním jednotlivých uživatelů a ne firem, bude uvedena jen možnost registrace soukromého účtu.
Po vyplnění emailu, hesla, data narození a potvrzení, že se nejedná o ro- bota, se odešle požadavek na vytvoření účtu. Aby byla registrace dokončena, uživatel obdrží zprávu s potvrzovacím odkazem, na který musí přejít. Tím se ověří, že je emailová adresa skutečná. Na konci registrace systém uživateli přidělí jméno, které si může v nastavení změnit. Na stejném místě může také doplnit další kontaktní údaje.
1.1.2 Prodej
Aby mohl vůbec prodávající nabídnout svoje zboží na stránkách, musí nejdříve z důvodu bezpečnosti účet aktivovat. To probíhá buď ověřovací platbou nebo dopisem s aktivačním kódem. Pokud uživatel chce, může si nastavit i PayU (umožnění online plateb). Dále je možné upravit nastavení prodeje, jako na- příklad „Zpráva pro Kupujícího“, „Omezení pro Kupující“ nebo si vytvořit
„Šablonu přepravy“ – předejde se opakovanému ručnímu zadávání poštovného.
Při vystavování nabídek je nutné ještě vybrat napojení: ruční, poloauto- matické, plně automatické a externí. Stejně jako v registraci se budu zabývat jen jednou možností, a to manuálním vystavováním. Dále už stačí vytvořit nabídku, přidat o ní údaje, nastavit metody platby a přepravu a přidat další informace jako třeba fotografie. Před prvním příhozem je možné nabídku li- bovolně pozměnit, po příhozu jsou možnosti úprav omezené.
Společnost si účtuje poplatky za vystavení nabídky, provizi z úspěšného prodeje nebo propagace nabídky. Poplatky jsou tedy zaměřeny pouze na pro- dávající.
1.1.3 Nákup pomocí aukce
Při nákupech na Aukru si uživatel musí najít předmět, o který by měl zájem.
To provede buď procházením kategorií (s případným tříděním podle různých parametrů) nebo pomocí vyhledávače, kde se mohou využít operátory „*“
pro nahrazení koncové části výrazu nebo „()“ obsahující množinu vyhledá- vaných slov. Při najití vhodné aukce si uživatel zobrazí nabídku s detailními informacemi o ní.
Jestli se uživateli aukce zalíbí, může k probíhající aukci přihodit. Samotné přihazování má své náležitosti: pokud je aktuální cena (v Kč) 1.00-4.99, pak je 6
1.2. eBay minimální hodnota příhozu 1.00 Kč, pro 5.00-19.99 je 2.00 Kč, pro 20.00-49.99 je 3.00 Kč, atd. Je zde i možnost automatického přihazování. Při této volbě si uživatel nastaví maximální cenu, kterou je ochoten zaplatit, systém si ji zapamatuje, ale aktuální cenu aukce to nepoznamená. Pokud cenu někdo jiný navýší, systém automaticky za původního uživatele přihodí minimální možnou částku, aby byl stále potencionálním výhercem. Takto bude pokračovat, dokud aukce neskončí, nebo cena nepřevýší zvolené maximum.
V průběhu aukce nakupující nevidí celá jména dalších přihazujících. Účel tohoto bezpečnostního opatření je zabránění zasílání nevyžádanách emailů nebo neoprávněných žádostí o platby.
1.1.4 Typy nabídek a aukcí
Na serveru je možné provést nákup pomocí „Kup teď“ nebo aukce. Pro práci je první možnost ne příliš zajímavá, protože chceme zjišťovat koncovou cenu, která se mění jen v případě aukcí.
Aukro se řídí anglickým typem aukce, tedy nejvyšší příhoz vyhrává a vítěz platí tuto částku. Každý příhoz je závazný, tudíž nelze jednoduše vzít zpět. Po- kud však přihazující nechtěně přihodil, může poslat požadavek prodávajícímu o zrušení příhozu, který ho musí akceptovat, aby byl fakticky zrušen.
Existují předměty, které uživatel nebude moci na tomto aukčním serveru koupit, protože jsou proti pravidlům provozovatele. Mezi ně patří alkohol, akcie, neoriginální předměty. Dále existují předměty, které jsou jistým způso- bem omezené, například elektronické publikace, kde uživatel musí být autorem nebo dílo musí spadat pod veřejnou licenci.
Pokud uživatel má více věcí, kterých by se rád prodal, ale nechce trávit čas přidáváním a nastavováním jednotlivých aukcí, může využít službu Aukrobot.
Ta funguje tak, že si prodávající objedná odvoz věcí určených k aukci a předá je kurýrovi. To je poslední krok, který leží na uživateli. Dále jsou tyto předměty Aukrem samy vystaveny na stránkách a o vydělané peníze za prodej se Aukro s uživatelem rozdělí.
1.2 eBay
Firma eBay byla založena roku 1995 Pierrem Omidyarem. Již v úvodu bylo zmíněno, že ve 4. čtvrtletí roku 2016 zde aktivně obchodovalo 167 milionů uživatelů po celém světě, počet stažení mobilní aplikace byl 348 milionů a za toto období byl obrat vypočítán na 22.3 miliardy dolarů 1.2.
1.2.1 Registrace
Obdobně jako v případě Aukra i eBay umožňuje zdarma vytvořit jak sou- kromý, tak podnikatelský účet. Pro vytvoření soukromého účtu oproti před- chozímu příkladu není potřeba zadat datum narození, zato je nutné vyplnit
1. Aukční servery a jejich principy
Obrázek 1.2: Ukázka úvodní stránky webu eBay zabývajícího se aukcemi po celém světě.
číslo mobilního telefonu a jméno uživatele. Stejně tak přijde ověřovací email, kterým se potvrdí pravost uživatele. Po ověření pravosti se umožní úpravy dalších informací účtu jako třeba adresy, kam má být zboží doručováno.
1.2.2 Prodej
Pro možnost prodeje si musí po registraci uživatel nastavit účet k prodávání.
K tomu je nutné zadat formu plateb poplatků, účet (kreditní, debetní karta nebo PayPal), na který mu budou peníze z aukcí docházet, a provede se kon- trola jména, adresy a telefonního čísla.
Dále je doporučené, aby si uživatel prošel ukončené i právě běžící aukce ostatních a tím lépe určil kategorii svého prodávaného předmětu a další nasta- vení aukce (např. počáteční cena). Za stejným účelem systém nabízí průvodce, tipy pro úspěšné prodávání a pravidla pro prodávající. Dále už jen vyplní po- žadované informace a vystaví předmět, stejně jako u Aukra. Zajímavou po- ložkou je skrytá minimální cena, která musí být překročena, aby se předmět mohl prodat.
Poplatky z prodeje nebo vystavení aukce zde platí také.
1.2.3 Nákup
Na rozdíl od Aukra má eBay nákup bez registrace jistá omezení, jako na- přiklad cenový limit. Oproti tomu registrovaní uživatelé mají otevřeno více 8
1.2. eBay možností (přístup k úplnému detailu objednávky, přístup k eBay komunitě, . . . ) a je opět zdarma.
K hledání aukcí lze využít rozšířeného vyhledávání, kde lze předvyplnit různé filtry pro přesnější nalezení požadované aukce. Toto vyhledávání lze kombinovat s pomocnými symboly jako závorky (stejný význam jako v Aukru), uvozovky pro zadání přesného pořadí slov nebo minus, které označuje slova, která se nemají v názvu aukce vyskytovat.
Při přihazování stačí zadat maximální hodnotu, kterou je schopný kupu- jící nabídnout. Systém potom automaticky přihazuje minimální částky, dokud jsou příhozy menší než maximum. Jestliže příhozy ostatních přesáhnou ma- ximum, eBay na to kupujícího upozorní. Jinak je možné přihazovat ručně po menších částkách, to je ale méně pohodlné.
Může se stát, že uživatel bude chtít nabídnout větší částku peněz, avšak příhoz nebude proveden. Pravděpodobně to bude tím, že dosáhl svého limitu.
Tyto limity jsou zavedeny z důvodu zabezpečení. Získáváním kladných ohod- nocení od ostatních účastníků nebo přidáním čísla debetní karty se může limit navýšit (možnost vyšších příhozů).
1.2.4 Typy nabídek a aukcí
Oba dva typy i průběhy obchodování jsou stejné jako v případě Aukra (aukce i „Kup teď“). Obdobně tomu platí s předměty, se kterými je zakázano obcho- dovat nebo musí splňovat podmínky určené společností eBay.
Kapitola 2
Současná řešení
Stále více se využívá nákupu a prodeje zboží pomocí aukcí, existují práce zabývající se predikcí jak koncové ceny, tak i samotným problémem, zda se předmět vůbec prodá nebo neprodá. Proto tato problematika nebude těžiš- těm mé práce. Zmíním se ale alespoň stručně o již existujících pracích (jejich přístupech a výsledcích). Z těch pak může být čerpáno při návrhu možného řešení.
David Nicholson a Rohan Paranjpe [7] skloubili obě varianty. Jejich práce je založena na aukcích ze serveru eBay. Data z důvodu velikosti omezili na kategorii zahrnující hudební nahrávky „Music – Records“. Součástí jejich předzpracování bylo odstranění aukcí (čímž opět snížili počet dat), které v po- pisku obsahovaly klíčová slova jako „skip“ nebo „damage“. Následovně spo- jitý prostor koncových cen aukcí převedli na diskrétní a to tak, že vytvořili kategorie odpovídající cenovým rozmezím o stejné velikosti a k nim přiřadili reálné koncové ceny aukcí: 0−(p−0.01), p−(2p−0.01), . . .. Proto mohli využít k predikci klasifikátory jako je naivní Bayesův klasifikátor (NB), po- mocí kterého predikovali, zda se předmět aukce vydraží nebo ne. Dále využili Multinomial Logistic Regression (softmax regrese, MLR), Multi-class Naive Bayes (MCNB) aUniform Prior Naive Bayes (UPNB). K učení NB a UPNB klasifikátoru využili pouze text názvu aukce – slova indikující prodej:concerto, tchaikovsky, organ; opak: digital, tulip, great. Autorům textu na základě ex- perimentů vyšlo, že s rostoucí velikostí rozmezí kategorií (p) se snižuje chyba klasifikátoru. Přibližné chybovosti (průměrná absolutní chyba) klasifikátorů jim vyšly: NB 25 %, softmax regrese 66 %, MCNB 44 %, UPNB 30 %.
Systém [8] pánů Manali Rajendra Khadge a Milind V Kulkarni se snaží o zlepšení přesnosti odhadu koncové ceny produktu na serveru eBay, přičemž využívají NB pro zjištění, zda se prodá, a Support Vector Machine (SVM) pro zjištění ceny. K experimentům využili dataset o velikosti 1000 záznamů – 700 na trénovaní systému a 300 na testování. Pro další zpracování dat bylo potřeba extrahovat z aukcí příznaky, jako je jméno předmětu nebo počáteční cena. Mimo jiné byly v práci ještě využity komentáře od uživatelů k před-
2. Současná řešení
mětu, které byly zpracovány metodou Term Frequency - Inverse Document Frequency(TF-IDF) [9], kdy se nejdříve zjistí počet výskytů slov v dokumen- tech a dále je vypočtena jejich váha napříč všemi dokumenty – čím častěji se slovo v dokumentech vyskytuje, tím menší má váhu. Poté bylo využito NB k rozhodnutí, zda mají komentáře pozitivní nebo negativní vliv na aukci. Při použití NB pro predikci prodeje bylo dosaženo přesnosti 99.3 % (s použitými atributy: ID předmětu, počtu zhlédnutí, počtu příhozů a komentáři) a při od- hadu ceny SVM s využitím nelineární jádrové funkce byla průměrná absoultní chyba 5.91 %.
Jedna část další práce [10] od Li Xuefeng, Liu Lu, Wu Lihua a Zhang Zhao se zabývala opět predikcí. Zde byly ceny zařazovány do kategorií o „šířce“
500 jednotek (jenů) pomocí logistické regrese a neuronové sítě, která k učení využívala zpětné propagace chyby a jako aktivační funkci používala sigmo- idu. Síť obsahovala 3 vrstvy, kde vstupní obsahovala 16 neuronů, což odpoví- dalo počtu extrahovaných atributů jednotlivých aukcí, ve skryté se nacházelo 30 neuronů a ve výstupní 1. Počet neuronů ve skryté vrstvě byl vybrán ex- perimentálně. V druhé části autoři experimentovali i s regresní metodou a to s MLR. Při využití regresní metody byla změřena průměrná kvadratická chyba 79.44 % s průměrnou standardní odchylkou 36.44 %. Logistická regrese dosáhla přesnosti 76.46 % a neuronová síť dokonce 91.29 %. Nakonec ještě vytvořili dva shluky dat pomocí metodyK-means na základě standardního skóre finálních cen aukcí. Pak na těchto datech zvlášť pustili lineární regresi a neuronovou síť.
U první metody se přesnost zmenšila na 68.4 a 63.4 % a u druhé se zvětšila na 94 a 95 %.
Další práce s názvem A final price prediction model for english auctions:
a neuro-fuzzy approach [11] využívá fuzzy logiky a fuzzy množin k určení pa- rametrů jako je například počáteční cena (nízká, střední, vysoká) nebo trvání aukce (krátká, střední, dlouhá). Nejdříve byla nastavena „KDYŽ-PAK“ pra- vidla, která se skládala z nezávislých a závislých proměnných (příklad: KDYŽ počáteční cena je nízká a běžná cena předmětu je střední, PAK finální cena je střední). Jednotlivé hodnoty atributů byly popsány jako procentuální pří- slušnosti do fuzzy množin (například pro počáteční cenu o hodnotě 500 Kč:
nízká 0.6, střední 0.35, vysoká 0.05). Jelikož byl tento přístup zkombinován s neuoronovou sítí, bylo potřeba z příslušností do jednotlivých fuzzy množin získat číslo, které by bylo sítí zpracováno. Toho bylo dosaženo defuzzifikací – jednotlivé příslušnosti byly vynásobeny reprezentativními hodnotami množin.
Porovnáním reálných a odhadnutých finálních cen pomocí fuzzy množin s neu- ronovou sítí a samotné neuronové sítě vyšly výsledky ve prospěch řešení s vy- užitím fuzzy množin (s průměrnou kvadratickou chybou kolem hodnoty 0.01).
Odhadováním koncové ceny aukcí pomocí algoritmu K-nejbližších sou- sedů (KNN) vážených atributů, se zabývá další práce [12] autorů Ilya Ra- ykhela a Dana Ventura, kteří se snažili pomocí vyvinutého systému hledat aukční předměty za „dobrou“ cenu. Ty pak přeprodávali za vyšší ceny a zjiš- ťovali výnosnost při využití systému. Jeho chybovost při odhadu koncové ceny 12
naměřili průměrnou relativní chybu na 16 %, což nelze považovat za špatný výsledek. Po nabídnutí aukcí systémem bylo ještě potřeba ručně projít a vyřa- dit některé aukce. Aby aukcí, které bylo potřeba ručně vytřídit, nebylo tolik, využili několika selekcí, jako například vyloučení aukcí, jejichž název obsaho- val slova jako „broken“ nebo „cracked“. Na závěr autoři porovnávali vydělané částky za hodinu strávenou hledáním vhodných aukcí s nevyužitím a využi- tím systému při 2 týdenních experimentech – v prvním případě vyšla sazba na 17.41 $ za hodinu, v druhém 98.04 $ za hodinu.
Použitím „boostingu“ [13] (souboru více modelů) chtěli autoři dosáhnout lepších výsledků než použitím samostatně postavených modelů. Touto meto- dou by mělo být dosaženo lepších výsledků – menší chyby. Základní ideou
„boostingu“ je zřetězení několika slabších modelů s cílem získání přesnějšího modelu [14]. V tomto případě se jako slabé modely použily rozhodovací stromy.
Tímto způsobem zlepšily hodnoty průměrné relativní chyby (v nejlepším pří- padě z 1.2 na 0.585 při vyhledávání digitálních kamer značky Canon). Pro učení bylo staženo přibližně 22000 aukcí, které byly rozděleny na trénovací a testovací množiny poměrem 4:1. Mimo jiné k učení bylo využito textového pole (konkrétně popisu aukce), obdobně jako v [7] nebo [8].
Vztahem mezi koncovou cenou aukce a možnými aktivitami, které mají uživatele přimět ke zvýšení ceny, se zabývali Fei Dong, Sol M. Shatz a Haiping Xu [15]. K tomu využili neuronové sítě (stejně jako v [10] a [11]). Síť se učila pomocí atributů jako je stav předmětu nabo počet příhozů. Cílem práce bylo prozkoumat dvě hypotézy: pokud je predikovaná finální cena menší, než reálná finální cena, pak je výskyt aktivity spojených s „umělým“ navyšováním ceny pravděpodobnější, a naopak. Autorům se povedlo obě hypotézy potvrdit.
PráceA Study on Different Methods and Algorithms to Predict End Prices in Online Auctions[16] od autorů Selva Mary. G, Likhesh N. Kolhe a Rucha D.
Pathari zjišťovala pomocí metod NB, UPNB, MLR a rozhodovacích stromů, zda se aukce vydraží, nebo ne, a na odhadování finální ceny aukce. Stejnou problematikou se zabývala práce [7] .
Kapitola 3
Použité metody při analýze dat a predikci
KapitolaPoužité metody při analýze dat a predikci obsahuje popisy metod po- užitých při vybírání atributů vhodných pro učící modely. Principy, na kterých tyto modely pracují, jsou vysvětleny ve druhé části kapitoly.
3.1 Metody analýzy dat
Samotné učení algoritmů je založeno na datech. Mohlo by se zdát, že čím větší počet atributů se při učení použije, tím lepší budou výsledky predikce.
To však není vždy pravda. Proto je nutné vybrat jen ty atributy, které zmenší výslednou chybu modelu. K tomu byl využit Pearsonův korelační koeficient, rekurzivní eliminační metoda na výběr atributů a testování hypotéz.
3.1.1 Pearsonův korelační koeficient
Obecně může být korelace popsána jako vztah mezi dvěma veličinami. Pear- sonův korelační koeficient popisuje korelaci hodnotami od -1 do 1 a vyja- dřuje tím míru lineárního vztahu mezi veličinami X = (x1, x2, x3, ..., xn) a Y = (y1, y2, y3, ..., yn), kde nje počet vzorků. Vzorec vypadá následovně:
r =
Pn
i=1(Xi−µX)(Yi−µY) pPn
i=1(Xi−µX)2pPni=1(Yi−µY)2, kdeµX = 1nPni=1Xi a obdobněµY = 1nPni=1Yi.
Čím je koeficient blíže k 0, tím jeY méně závislé na hodnotě X, a čím je hodnota vyšší, respektive menší (blíží se k 1, respektive k -1), tím jsou více závislé 3.1.
3. Použité metody při analýze dat a predikci
Obrázek 3.1: Příklad Pearsonových korelačních koeficientů datových souborů znázorněných v grafech. V ukázkách je vidět, že koeficient popisuje pouze lineární závislosti – data ve třetí řadě od shora a prvním sloupci zleva vypa- dají, jako by opisovaly funkci sinus, a i přes to je hodnota koeficientu 0. Zdroj:
https://upload.wikimedia.org/wikipedia/commons/thumb/d/d4/Correlation _examples2.svg/506px-Correlation_examples2.svg.png
3.1.2 Rekurzivní eliminační metoda výběru atributů
Existují i způsoby, ve kterých se nepracuje se samostatnými atributy, nýbrž s podmnožinami všech atributů a hledá se ta nejlepší. Takovou podmnožinu je možné najít pomocí rekurzivní eliminační metody [17]. Té je předán model, který se nejprve učí na trénovací množině dat se všemi atributy. Jednotlivým atributům se nastaví váhy a atribut s nejmenší vahou je pak odříznut. Tímto způsobem se bude podmnožina atributů zmenšovat.
Dále je potřeba nastavit výsledný počet atributů, po jehož dosáhnutí se rekurzivní metoda zastaví.
V práciGene Selection for Cancer Classification using Support Vector Ma- chines [18] se pracuje s rekurzivní eliminační metodou za využití SVM (po- psáno níže). S menší obměnou bude to samé využito i zde, jen se bude místo SVM pracovat s algoritmemsupport vector regression(SVR - popsáno níže) [19]
s lineární jádrovou funkcí.
3.1.3 Testování hypotéz
Tvrzení, které nelze jednoduše rozhodnout, jestli platí, nebo neplatí, se nazývá hypotéza [20].
Při statistických testech se využívá nulové (H0) a alternativní (HA) hy- potézy. Nejčastěji se pracuje s nulovou hypotézu, která se buď zamítá, nebo nezamítá.
Dosazením vypočtené hodnoty r a počtu záznamů n do následujícího vzorce pro výpočet testovacího kritéria je možné otestovat, zda lze, nebo nelze zamítnout nulovou hypotézu na hladině významnostiα, tedy zda jsou soubory na sobě nezávislé (respektive závislé):
16
3.2. Predikovací modely
Obrázek 3.2: Graf ukazující Studentovo rozdělení se stupněm volnosti 1508 a 5 % oboustranným intervalem spolehlivosti.
t= |r|√ n−2
√
1−r2 .
Hladina významnosti vyjadřuje pravděpodobnost, se kterou se zamítá nu- lová hypotéza, i když platí (jedná se o tzv. chybu 1. druhu). Nejčastěji se využívá hodnot α= 1% neboα= 5%.
Existuje ještě chybu 2. druhu, kde se naopak přijímá hypotéza, která ne- platí.
Nyní se z tabulky pro Studentovo rozdělení 3.2 nalezne kritická meztα,n−1. Na zadání pak záleží, jestli se bude jednat o jednostranný interval, kdy je zadaná nulová hypotéza jakoH0:θ > θ0neboH0 :θ < θ0, nebo o oboustranný interval, kde H0 : θ 6= θ0. Pokud se jedná o oboustranný interval, dělí se α dvěma, takže se kritická mez získá jako tα/2,n−1.
Posledním krokem je porovnání hodnot t a tα,n−1, respektive tα/2,n−1, na jejímž základě se rozhodne, zda se H0 zamítá, nebo nezamítá. Jestliže t < tα,n−1, nulová hypotéza nelze zamítnout na hladině významnosti 1−α (alternativní hypotéza je považována za neprokázanou). V opačném případě seH0 zamítá (HAje prokázána). Obdobně to platí pro oboustranné intervaly – pokud platí |t|<tα/2,n−1, pak se nezamítne.
3.2 Predikovací modely
Cíl práce obsahuje predikci koncové ceny aukce, tudíž bude potřeba využít modelů, které se naučí pomocí předložených trénovacích dat určovat tuto cenu.
Za tímto účelem jsou pro představu, jak fungují, jednotlivé modely popsány v této kapitole.
3. Použité metody při analýze dat a predikci
Obrázek 3.3: Příklad stromové struktury klasifikující vozidlo na základě jeho vlastností.
3.2.1 Rozhodovací strom
Obecně se rozhodovací strom [21] skládá ze sady hiearchicky uspořádaných rozhodovacích pravidel. Každý strom se tvoří z kořene, který obsahuje množinu všech závislých proměnných Y. V každé úrovni se větví podle Y do dalších uzlů (tím se jeho struktura zvětšuje).
Příklad větvení může být dělení zvířat, kdy nejdříve máme všechna zví- řata (závislé proměnné) a v každém uzlu se množina rozdělí (třeba při dělení na ty, která mají křídla a na ty, která je nemají). Větvení se dělí na binární a nebinární podle toho, kolik větví vystupuje z uzlů.
Rozhodovací stromy se také dělí na klasifikační a regresní.
V kořenu klasifikačního stromu s N uzly se nachází všechny cílové pro- měnné Y, které lze zařadit do J kategorií. Při každém větvení se proměnné dělí podle kategorií (například ANO a NE) atributů vstupních proměnných X (například má motor).
Jednoduchý příklad klasifikačního rozhodovacího stromu je ukázán na ob- rázku 3.3 zachycující klasifikaci vozidel. V prvním kroku výstupní proměnná Y obashuje všechna vozidla. Při větvení v kořenovém uzlu se Y rozdělí do dvou skupin podle atributu má motor, který obsahuje proměnná X. Pokud klasifikujeme předmět do 3 kategorií (automobil, motocykl, kolo), první uzel ji rozdělí naautomobil, motocykl, pokud vozidlo má motor, a kolo, pokud ho nemá. Takto se postupuje stromem až k listům, kde již nelze Y dělit podle žádného atributuX.
Nevýhodou stromů je, že jsou velice náchylné na trénovací množinu dat.
Stačí malá změna a vytvoří se odlišná hiearchie rozhodovacích pravidel, což má dopad na výslednou predikci.
Regresní rozhodovací stromy jsou založeny na stejném principu, jako kla- 18
3.2. Predikovací modely
Obrázek 3.4: Příklad stromové struktury určující pravděpodobnost, zda vstupní proměnná je muž (respektive žena).
Obrázek 3.5: Graf ukazuje lomenou lineární funkci vytvořenou metodou MARS.
sifikační, jenom je závislá proměnnáY spojitá. Jako příklad může pousloužit dělení na muže a ženy 3.4. Z jednoho úhlu pohledu může být tento příklad brán jako klasifikace – buď se jedná o muže, nebo ženu. Z druhého se však může měřit míra příslušnosti k jednotlivým pohlavím. V grafu je vidět, jak listy stromu neobsahují jasnou klasifikaci do tříd, ale pravděpodobnost zařazení.
Nejznámějším a nejpoužívanějším algoritmem pro tvorbu stromů je CART (Classification and Regression Trees). Tyto stromy jsou pak vhodné pro kate- goriální a regresní úlohy, kde se soubor v uzlech dělí binárně.
3. Použité metody při analýze dat a predikci
Obrázek 3.6: Graf ukazuje SVR model s lineární jádrovou funkcí a trénovacími daty, kde je odchylka aξ a ξ∗ je tolerance při překročení odchylky .
Dalším typem algrotimu pro tvorbu stromu je Multivariate Adaptive Re- gression Splines(MARS). Jedná se o metodu vhodnou pro regresní problémy řešící nedostatky binárních stromů, kde počet predikovaných hodnot je roven počtu listů stromu. Rozdělení souborů probíhá pomocí „splajn“, které jsou definované jako lineární funkce lomené v jednom bodě 3.5.
Tento model (tyu CART) byl vybrán z toho důvodu, že se jedná o zá- stupce neparametrického učení [22] – model nemá žádné předdefinované zá- kladní vztahy mezi cílovou a vstupní proměnnou.
3.2.2 Rozhodovací les
Základem rozhodovacích lesů [21] je soubor samostatných rozhodovacích stromů.
V případě klasifikace je výsledek rozhodovacího stromu dán největším zastou- pením výsledků jednotlivých stromů. U regrese se pak počítá průměr výsledků všech rozhodovacích stromů v lese.
U rozhodovacích lesů se využívá tzv. „bootstrapového výběru“. Jeho prin- cip spočívá v náhodném výběru podmnožiny všech trénovacích dat o kon- stantní velikosti. Výběr podmnožin se provádí vícekrát, vždy z původní mno- žiny dat. Jedná se o náhodný výběr s opakováním.
Rozhodovací les jsem se rozhodl použít z důvodu rozšíření rozhodovacího stromu. Zajímalo mě, zde je lepší použít jediný strom, nebo použít průměr více stromů.
20
3.2. Predikovací modely
Obrázek 3.7: Graf ukazuje, jak vypadá klasifikace vstupní proměnné (křížek).
Umístění trojúhelníků a čtverců znázorňuje vzorová dat a jejich tvar značí kategorii, do které podle klasifikace spadají. Podle zadaného počtu nejbližších sousedů se vstupní proměnná ohodnotí. Záleží tedy naK. Jeho volba je velice obtížná – při nízkých nebo vysokých hodnotách může být zařazení nepřesné.
3.2.3 Support vector regression
Cílem učícího algoritmu SVR [23] je získání funkce f(x), která má nanejvýš odchylkuod závislých proměnnýchyi z celé trénovací množiny dat a zároveň je co nejvíce plochá. Jinými slovy – pokud je odchylkayi od funkce menší než , počítáme s ní, jako kdyby byla chyba nulová 3.6.
Jestliže by se všechny chyby hodnot yi měly vejít do pásu o velikosti a při tom by měla funkce být maximálně plochá, mohl by vzniknout buď široký pás okolo funkce, nebo by funkce mohla ztratit plochost. K vyřešení tohoto problému se využívá proměnnýchξ,ξ∗ ≥0 a konstanty C >0.
ξ a ξ∗ určují toleranci při překročení odchylky . Konstanta C je pak kompromis mezi plochostí funkce a mírou, do které je překročení odchylky tolerováno. Správným výběrem konstanty se zabrání přeučení, nebo nedoučení modelu (pro velkéCje funkce sice méně plochá, ale chyby jsou malé; pro malé C je funkce více plochá, ale chyby jsou větší).
Jelikož se jedná o regresní obdobu velmi používaného a oblíbeného algo- ritmu SVM, rozhodl jsem se ji využít při získání modelu predikující koncovou cenu aukce.
3.2.4 K-nejbližších sousedů – regresní model
Stejně jako v předešlém případě u SVR jsem se rozhodl využít regresní model KNN [24] z toho důvodu, že je odvozen od známého klasifikačního modelu.
Idea algoritmu spočívá v lokalizaci dat – vstupní proměnné, které ve společném prostoru sousedí, mají podobné výstupní hodnoty 3.7.
3. Použité metody při analýze dat a predikci
Obrázek 3.8: Graf ukazuje rozdíl dvou SVM modelů se stejnými trénovacími daty a různými hodnotami C. ξ a ξ∗ jsou tolerance při vytváření klasifikační funkce. Funkce f má menší pás a nepřipouští žádnou chybu na trénovacích datech, hodnota konstantyC je tedy velká. Funkceg naopak připouští chybu a lépe rozděluje třídy (C je menší.)
Algoritmus regresní verze KNN je založen na funkci f, která přiřazuje vstupním proměnnýmxvýstupní hodnotyy. Funkcefpracuje tak, že k zadané vstupní proměnné vybereK nejbližších sousedů z množiny trénovacích dat, ty spáruje s jejich výslednými hodnotami, následně provede aritmetický průměr těchto hodnot a přiřadí ho vstupní proměnné.
U výpočtu vzdáleností lze využít různých metrik, třeba Minkowského.
Algoritmus také může přiřazovat sousedům váhy na základě vzdáleností od vstupní proměnné – váhy jsou nastaveny na převrácenou hodnotu vzdálenosti.
Protože model využívá prohledávání lokálního prostoru (předešlé nikoli), rozhodl jsem se ho vyzkoušet v experimentech při predikci.
3.2.5 Support vector machine
Regresní alternativu (SVR) tohoto modelu jsem již popsal, nyní je na řadě klasický klasifikační SVM [25].
Principem této metody je rozdělení trénovacích dat do dvou tříd pomocí optimální nadroviny, která obě třídy rozdělí tak, že minimum vzdáleností dat od nadroviny bude maximální 3.8.
Rozdíl oproti SVR je v hledání funkce – regresní model se snaží najít co nejmenší vzdálenost od funkce, aby se do ní vešla všechna data. Kdežto SVM se snaží najít co nejširší pás kolem lineárního prediktoru tak, aby byla klasifikace co nejjednoznačnější.
22
3.2. Predikovací modely Společnou vlastností obou metod je použití proměnných ξ,ξ∗, značící to- leranci, a konstanty C, která ovlivňuje chybu, se kterou je možné při učení SVM modelu skloubit jak nejširší pás kolem funkce, tak přijetí chyby při učení (pro velké C je šířka pásu sice menší, ale chyby na tréninkových datech jsou malé; pro malé C je šířka pásu větší, ale chyby na tréninkových datech jsou větší).
Pro využití SVM modelu při klasifikaci do více tříd se může využít dvou přístupů: klasifikovat pro všechny dvojice tříd (1 třída ku 1 třídě), nebo klasifi- kovat pro jednotlivé třídy proti všem zbylým třídám (1 třída kuK−1 třídám).
Kapitola 4
Formát dat a jejich získání
Kapitola pojednává o formě aukčních dat, ve které se na stránkách Aukro.cz vyskytují a kterou uživatel vidí. Informace z webu bylo potřeba vzhledem k dalšímu využití (konkrétně k učení modelů) nějakým způsobem získat. I to je součástí této kapitoly.
4.1 Formát dat
Pro analýzu chování uživatelů bylo potřeba získat atributy aukcí, ke kterým má uživatel přístup a které může vidět. Po vyhledávání nebo filtrování podle parametrů uvidí nejdříve obecné informace k předmětu (jak je vidět na ob- rázku 4.1). Zde si člověk může prohlédnout první náhled předmětu, jeho aktu- ální cenu (případně cenu dopravy a možnosti „Kup teď“), kolik lidí přihazuje, jak dlouho ještě aukce potrvá, kolik předmětů zbývá a další parametry zadané prodávajícím.
Pokud uživatele obecné informace o vyhledávaném předmětu zaujmou, může si otevřít jeho detail, kde se dozví více informací jako je popis před- mětu, prodejce a jeho ohodnocení od ostatních uživatelů a všechny přidané obrázky předmětu 4.2. Ve spodní části si ještě může zobrazit historii přihazo- vání a podívat se, kdo, kdy a jakou částku přihodil 4.3.
Obrázek 4.1: Příklad aukce zobrazené při vyhledávání nebo filtrování podle parametrů.
4. Formát dat a jejich získání
Obrázek 4.2: Příklad detailu vybrané aukce.
Obrázek 4.3: Příklad historie příhozů kupujících zobrazený v detailu aukce.
4.2 Získání dat
Základem byla data o aukcích telefonů ze serveru Aukro.cz, která jsem stáhl pomocí TextMiningSuite (interní program). Celkem bylo 1509 záznamů vhod- ných k následujícím úkonům - měly alespoň jeden příhoz (jinak nemá smysl odhadovat koncovou cenu aukce) a musely být už skončené.
Před samotným stažením dat pomocí nástroje TextMiningSuite bylo po- třeba nastavit paramtery, podle kterých se data budou stahovat.
Prvním krokem bylo zadání klíčového slova, které by uživatel v případě internetových stránek Aukro.cz zadal do vyhledávače. Další parametry byly použity jako filtry, například výběr pouze skončených aukcí, počet záznamů zobrazených na jedné stránce. Tím byly specifikovány atributy, pomocí kterých byly jednotlivé aukce nalezeny.
Následovalo vytěžení dat z jednotlivých aukcí. Program získává informace o aukcích tím způsobem, že stáhne zdrojový kód stránky ve formě HTML (Hy- 26
4.2. Získání dat
/spickovy-telefon- samsung-s7-edge- za-super-cenu- i6567140317.html
21 osob přihazo- valo
Skončeno 27 října 2016 v 21:30
13 633,00 Kč s dopravou 13 733,00 Kč
**ŠPIČKOVÝ TELE- FON SAMSUNG S7
EDGE ZA SUPER
CENU**
/mobilni-telefon-lg-g4c- h525n-titan-5-uhlopr- i6553977627.html
17 osob přihazo- valo
Skončeno 17 října 2016 v 22:05
1 666,00 Kč s dopravou 1 751,00 Kč
Mobilní telefon LG G4c (H525n)Titan,5"Úhlopř /mobilni-telefon-
lg-v10-h960a- 32gb-cerna-prislus- i6568609348.html
15 osob přihazo- valo
Skončeno 21 října 2016 v 18:49
8 600,00 Kč Přeprava ZDARMA s dopravou –
Mobilní telefon LG V10 H960A 32GB, černá, přísluš.
Tabulka 4.1: Tabulka ukazuje seznam obsahující informace o aukcích, které je možné získat z internetových stránek při vyhledávání pomocí klíčového slova (telefon) a filtrů (skončená aukce).
v...4 (757) 105,00 Kč Čt 20 říj 2016 17:46:34 m...8 (334) 100,00 Kč Čt 20 říj 2016 09:45:47
Tabulka 4.2: Tabulka obsahuje záznamy příhozů uživatelů k aukčnímu před- mětu, které je možné získat z internetových stránek při zobrazení detailu aukce.
perText Markup Language) – obsahující značky s identifikátory. Uživatel na- staví příslušnému nástroji tyto dva elementy a tím mu řekne, jaké atributy ohledně aukcí má program uložit (místo si uživatel sám zvolí). Všechny sou- bory jsou ukládány ve formátu *.xlsx.
TextMiningSuite ukládal data do 3 složek – první obsahovala seznam všech aukcí v jednom souboru 4.1, druhá historii příhozů jednotlivých aukcí, kde každá aukce má vlastní soubor 4.2 a ve třetí byly uloženy pouze popisy aukcí (také má každá vlastní soubor). K výběru atributů ke stažení ze stránek bylo přistupováno stylem „čím více, tím lépe“, proto byla získána všechna data, která obsahuje každá aukce.
Celkem bylo staženo 12 souborů obsahující obecné informace ohledně jed- notlivých aukčních předmětů. Počet vytvořených souborů odpovídá počtu stránek nalezených na webu Aukro a každý obsahuje tolik záznamů, kolik je nabídek na stránce.
Kapitola 5
Analýza
Cílem této kapitoly je roztřídit atributy na vhodné, které nesou informace, jež napomohou k dobrému naučení algoritmu, a na nevhodné. Nejdříve bude vybrána vhodná kategorie předmětů. Pak se analyzuje využití textů (názvů a popisů) aukcí a pomocí Pearsonova korelačního koeficientu a následně i re- kurzivní eliminační metody se vyberou množiny atributů, které budou mít za cíl zjistit, jaké atributy uživatele při výběru předmětu nejvíce ovlivňují.
Většina prací, která se zabývala stejnou problematikou, zjišťovala (pomocí NB), jestli se vůbec předmět prodá. Tato práce se tímto problémem přímo zabývat nebude, zato se zaměří na předměty, které budou prodány – tedy mají jednoho nebo více zájemců, přihazujících.
Stejně jako v případě panů Nicholsona a Paranjpe [7] byla vybrána jedna dostatečně zastoupená kategorie, a to telefony. Je důležité se zaměřit na jeden úsek a ten prozkoumat. Telefony byly vybrán z toho důvodu, že množství aukcí s nimi je dostatečně velké (třeba oproti golfovým holím).
Práce byla pojata ve stylu analýzy aukcí na serveru Aukro, které dopadnou úspěšně. Z neúspěšných předmětů lze získat pouze informace, které uživatele od koupě odrazují. U úspěšných obchodů lze však predikovat i konečnou cenu.
Ze skončených aukcí je také možné analyzovat, jak a které faktory (atri- buty) týkající se aukcí (např. počet příhozů v jednom dni) uživatele ovlivňují (a tím ovlivňují i koncovou cenu). Tyto faktory by mohly být v budoucnu dobrým rádcem při hledání vhodných kandidátů ke koupi – předmět příliš nezvýší svou aktuální cenu.
Dalším důvodem bylo, že výše zmíněné výzkumy predikci prodejnosti ob- sahovaly, tudíž by práce v tomto směru nic nového nepřinesla.
5.1 Selekce atributů
Opakujícím se rysem již existujících prací je predikce na základě textu, kon- krétně názvu a popisu aukce. Tento přístup byl použit na binární klasifikci
5. Analýza
prodejnosti (nejčastěji pomocí NB). Jak už bylo na začátku kapitoly řečeno, rozhodování o úspěchu či neúspěchu prodeje nebude součástí této práce.
Podstatnou odlišností od ostatních prací je, že se zabývaly anglickými auk- cemi, tudíž byly texty psány v anglickém jazyce. Aukro je český server, takže obsahuje české titulky a popisky. Protože se čeština od angličtiny liší mimo jiné v možnosti skloňování, je náročnější strojově předzpracovat text tak, aby význam jednotlivých slov v něm nebyl pozměněn, jako je například u slova
„čtvrtky“. Zde záleží na kontextu, ve kterém se slovo nachází. Rozdílně bude chápán v případě „čtvrtka – papír“ a „čtvrtek – den“.
K tomuto účelu se využívá program zvaný lemmatizátor [26]. Jak název napovídá, lemmatizátor vytváří ze slov lemma. Za lemma se považují základní tvary slov, jako je právě zmíněné jednotné číslo podstatného jména v 1. pádu, nebo infinitiv u sloves. Tím získáme jednotné tvary slov a i jejich význam.
Jak už bylo nastíněno, pro program je obtížné nalézt lemma, které by pasovalo do kontextu. Samotná analýza zabývající se vytěžováním slov z textu by vydala na novou práci.
Existují lemmatizátory, které tuto situaci řeší – některé lépe, některé hůře.
Lemmatizace lze dosáhnout dvěma způsoby, buď algoritmicky nebo pomocí slovníku. Algoritmický přístup má výhodu v nenáročnosti, kdy se určí pra- vidla, kterých se má program při vytváření lemmat držet. Avšak má to své stinné stránky. Pravidla nedokáží úplně obsáhnout veškeré výjimky a zvlášt- nosti jazyka, jako je třeba nepravidelné skloňování.
To by měl dokázat lemmatizátor pomocí slovníku. Tento přístup je však kvůli přípravě hodně časově náročný. Navíc se český jazyk neustále vyvíjí, slova vznikají a zanikají, a proto nelze říct, jaká slova ani kolik jich v současné době přesně existuje. Například v práciFrekvence slov, slovních druhů a tvarů [27]
autoři pracují s 1 623 527 slovy ze 75 literárních děl a novin a zárověň zmiňují, že počet využitých slov nebyl dostatečný na to, aby se vyhnuli komplikacím.
Další nepříjemnost se vyskytne při automatickém zpracovávání slov po- mocí slovníku – lemmatizátor vrátí seznam vhodných slov (většinou seřazený podle frakvence výskytu v textech, ze kterých je slovník sestaven). Kvůli tomu nastává problém při hledání správného významu vyhovujícímu kontextu.
Dále může být slovo špatně vyhodnoceno kvůli překlepům, nespisovné češ- tině a cizím výrazům.
Neméně významnou komplikací u popisů jsou i aukce nabízené přes službu Aukrobot, které obsahují zvláštní elementy, tudíž je nelze zpracovat stejně jako běžné aukce.
Jedinou možností by bylo procházet jednotlivá slova textů, jedno po dru- hém vkládat do lemmatizátoru a vybírat ty tvary slov, které významově za- padají. To by ale bylo časově neefektivní a jelikož je tato práce brána ve stylu
„proof of concept“, nepovažoval jsem za nutné se tímto směrem vydávat.
Kvůli všem výše zmíněným důvodům jsem se rozhodl nezprácovávat texty aukcí ani je nepoužít při učení modelů.
30
5.1. Selekce atributů 5.1.1 Využití Pearsonova korelačního koeficientu
Nyní se práce bude zabývat zbylými atributy, které existující práce buď ne- zmínily nebo zmínily, ale nezabývaly se jimi podrobně.
Z celkového počtu 1509 aukcí bylo 88 prodáno pomocí služby Aukrobot.
Jak bylo již zmíněno, Aukrobot spadá pod společnost Aukro. Je dost možné, že pokud uživatel uvidí, že je aukce vystavena společností spravující celý systém, mohl by získat pocit o vyšší důvěryhodnosti a jistotě při přihazování. A to by mohlo ovlivnit konečnou cenu aukce.
Pro výpočet vztahu mezi využitím a nevyužitím služby Aukrobot byl po- užit Pearsonův korelační koeficient. Ten vyšel přibližně -0.0234, tzn. existuje nepatrná souvislost mezi využitím služeb Aukra a normalizovanou cílovou hod- notou (poměr posledního a prvního příhozu skončené aukce).
Tato hodnota koeficientu byla otestována pomocí testu hypotéz, kde nulová hypotéza tvrdila, že jsou proměnné nezávislé (H0 : r = 0), a alternativní hypotéza, že jsou závislé (HA:r 6= 0).
Po dosazení vyšla hodnotat= 0.9096. Pro rozhodnutí bylo potřeba nasta- vit hodnotu předem známéα, kterou jsem zvolil 5 %.
Nyní se z tabulky Studentova rozdělení nalezla kritická meztα/2,n−1 (pro- tože se jedná o oboustranný interval). Pro t0.025,1508 vyšla hodnota 1.960.
Protože platilo, že t < t0.025,1508 (a tím pádem náleží do konfidenčního inter- valu), pak nešlo zamítnout nulovou hypotézu na hladině významnosti 95 %.
Což také znamená, že hypotéza HA:r6= 0 byla neprokázaná.
Podobný závěr (nezávislost vektorů X a Y) bylo možné vyčíst i z grafu pravděpodobnostních rozdělení 5.1, kde hustoty v obou případech byly téměř stejné až na zanedbatelné výkyvy, které byly způsobeny nízkým množstvím dat u aukcí s využitou službou Aukrobot.
Na základě porovnání pravděpodobnostních rozdělení z grafu a hodnoty Pearsonova korelačního koeficientu se vyvodil závěr, že neexistují souvislosti mezi využitím a nevyužitím služeb Aukrobot a konečné ceny. Začlenění tohoto atributu k jednotlivým záznamům tudíž by nepřineslo žádné zlepšení.
Již bylo na vyhledávání aukce ukázáno, co může uživatel při rozhodování, jestli se o akci dále zajímat či nikoli, vidět. Na rozdíl od skončené aukce uži- vatel může vidět, kolik předmětů zbývá. A protože se jedná o analýzu chování uživatelů založenou právě na ukončených aukcích, není možné počet nabíze- ných předmětů při ní získat, takže bude rovnou zanedbán.
Dalším atributem, zobrazovaným jen u probíhajících aukcí, je „předvypl- nitelný“ popis předmětu. Jedná se o jeho stav (nový nebo použitý), operační systém, úhlopříčka displeje, konstrukce (dotykový, s klavesnicí), značka, . . . . Tato data je možné najít také v detailu aukce v sekci „Popis předmětu“.
Zmíněné vlastnosti uživatel nemusí vylňovat, jsou volitelné. Z toho důvodu nebudou zkoumány.
Zbytek informací u seznamu vyhledaných skončených aukcí je stejný jako u neskončených, obsahuje tedy název aukce, konec aukce, cenu a počet přiha-
