Naivny Bayesovsky klasifikator

 Autori: Alžbeta Kováčová Lucia Brédová


1 Popis metódy- Naive Bayes

Bayesovské klasifikátory sú štatistické klasifikátory, ktoré predikujú pravdepodobnosti, s ktorými daný príklad patrí do tej – ktorej triedy. Vychádzajú pritom z určenia podmienených pravdepodobností jednotlivých hodnôt atribútov pre rôzne triedy. [1]

Naivný Bayesovský klasifikátor vychádza z predpokladu nezávislosti atribútov medzi sebou. To znamená, že efekt, ktorý má hodnota každého atribútu na danú triedu, nie je ovplyvnený hodnotami ostatných atribútov. Kvôli tomuto zjednodušeniu je tento klasifikátor nazývaný ako „naivný“.[2]


1.1 Bayesovská teoréma

Bayesová teoréma nesie meno po svojom autorovi, Thomasovi Bayesovi, anglickom duchovnom žijúcom v 18. storočí. Bayes nikdy nepublikoval svoju teorému. Vydaná a pomenovaná bola až po jeho smrti jeho priateľom Richardom Priceom. [3]

Nech X je príklad s neznámym zaradením do triedy C. Nech H je hypotéza, že X patrí do určitej triedy Ci. Cieľom klasifikácie je určenie podmienenej pravdepodobnosti P(X|H). Ide o posteriórnu pravdepodobnosť hypotézy H za podmienky X. V tomto prípade pravdepodobnosti toho, že X patrí do triedy Ci.

Predpokladajme, že máme súbor dát máme zákazníkov, ktorí sú popisovaní atribútmi vek a príjem, napr. že X má 35 rokov a jeho príjem je 40 000 EUR. Predpokladajme, že H je hypotéza tvrdiaca, že zákazník si kúpi počítač. Potom P(X|H) predstavuje pravdepodobnosť, že zákazník X si kúpi počítač na základe toho, že vieme zákazníkov vek a príjem.                

Naopak, P(H) je apriórna pravdepodobnosť H. V našom prípade ide o pravdepodobnosť, že zákazník si kúpi počítač bez uvažovania jeho veku, príjmu, alebo inej vlastnosti.

P(X|H) je posteriórna pravdepodobnosť X podmienenej H. Ide o pravdepodobnosť, že zákazník X, má 35 rokov a zarába 40 000 EUR, pričom vieme, že zákazník si kúpi počítač.

P(X) je apriórna pravdepodobnosť X. V našom príklade by išlo o pravdepodobnosť, že osoba z našho súboru zákazníkov má 35 rokov a zarába 40 000 EUR. [2]

Podľa Bayesovskej teorémy môžeme vypočítať žiadanú posteriórnu pravdepodobnosť P(H|X) na základe pravdepodobnosstí P(H), P(X|H) a P(X), a teda ako:

 

P(H|X)=\frac{P(X|H).P(H)}{P(X)}

 


1.2 Naivný Bayesovský klasifikátor

 

Naivný Bayesovský klasifikátor pracuje nasledovne [2]


  1. Nech D je trénovacia množina príkladovich zaradení do tried. Každý príklad je reprezentovaný n-rozmerným vektorom vlastností  X=(x1, x2, ..., xn), patriacim n-atribútom A1, A2,..,An.
  2. Majme m tried C1, C2, ..., Cm. Neznámy príklad X bude klasifikovaný do triedy s najväčšou posteriórnou pravdepodobnosťou P(X|Ci) > P(Ci|X)   pre 1 ≤ j ≤ m, j ≠ i.
  3. Vychádzame z Bayesovej teorémy: P(C_{i}|X)=\frac{P(X|C_{i}).P(C_{i})}{P(X)}Keďže P(X) je konštatna pre všetky triedy Ci, stačí maximalizovať výraz P(X|Ci).P(Ci).  P(Ci) vyjadruje pravdepodobnosť,akou ľubovoľne zvolený prvok patrí do triedy Ci. Používame pri tom vzťah: P(C_{i})=\frac{s_{i}}{S}kde si predstavuje počet príkladov triedy Ci a S je počet všetkých príkladov. Maximalizujeme teda len člen P(X|Ci).
  4. Vzhľadom na to, že pri veľkom počte atribútov by bolo výpočtovo náročné určovať P(X|Ci), vychádzamepredpokladu, že nezávislosti atribútov pri príslušnosti k danej cieľovej triede, teda P(X|C_{i})=\prod_{k=1}^{n}P(x_{k}|C_{i})=P(x_{1}|C_{i})xP(x_{2}|C_{i})x...xP(x_{n}|C_{i})Pravdepodobnosť P(x1|Ci)xP(x2|Ci)x...xP(xn|Ci vieme určiť z trénovacej množiny, pričom:  
    1. Ak Ak je kategorický atribút, potom P(x_{k}|C_{i})=\frac{s_{ik}}{S}kde sik je počet príkladovtrénovacej množiny patriacich triede Ci, pre ktoré Ak=xk. Si je počet vzoriek z trénovacej množiny patriacich triede Ci.
    2. Pre spojité atribúty Ak sa zvyčajne predpokladá Gaussovo normálne rozhodelenie hodnôt,potom P(x_{k}|C_{i})=g(x_{k},\mu_{C_{i}},\sigma _{C_{i}})=\frac{1}{\sqrt{2\pi \sigma _{C_{i}}}}.e^{-\frac{(x-\mu _{C_{i}})^{2}}{2\sigma _{C_{i}}^{2}}}kde μCi je stredná hodnota a σCi je rozptyl hodnôt atribútu Ak trénovacích príkladov z triedy Ci
  5. Pri klasifikácií neznámeho príkladu X je vypočítaný člen P(X|Ci)P(Ci) pre každú triedu Ci. Príkladu X je priradená trieda Ci, vtedylen vtedy ak P(X|Ci).P(Ci)>P(X|Cj)P(Cj)   pre 1 ≤ j ≤ m, j ≠ i. Inými slovami, príklad X je zaradený do tej triedy, pre ktorú je P(X|Ci)P(Ci) maximálne.

 

1.3 Laplacelova korekcia

 

Pri použití Bayesovho mode môže nastať problém, kedy podmienená pravdepodobnosť P(xk|Ci) je rovná 0 (v množine dát sa nenachádza žiaden príklad patriaci do danej triedy),  pretože kvôli násobeniu dôjde k P(X|Ci)=0, čo znehodnotí celú klasifikáciu.

Riešením je Laplacelova korekcia, čo znamená pridanie jedného prvku do všetkých množín. Vychádzame pri tom z toho, že naša množina príkladov je tak veľká, že pridanie ďalšieho príkladu ovplyvní pravdepodobnosť len zanedbateľne, pričom sa ale vyhneme nulovej hodnote pravdepodobnosti. [4]

Ako príklad, predpokladaje, že pre triedu kúpi=áno v trénovacej množine máme 1000 príkladov, pričom 0 z nich má príjem = nízky, 990 má príjem = stredný a 10 príkladov má príjem = vysoký. Pravdepodobnosti javov bez Laplacelovej korekcie sú pre príjem = stredný 0,990 (990/1000), a pre príjem=vysoký 0,010 (10/1000). Pri použití Laplacelovej korekcie predtrierame, že máme o jeden príklad viac pre každú hodnotu atribútu príjem. Tak získame pravdepodobnosti 1/1003=0,001, 991/1003=0,988 a 11/1003=0,011. Hodnoty modifikovaných pravdepodobností sú teraz blízke k tým pôvodným, avšak vyhli sme sa nulovej pravdepodobnosti pre hodnotu atribútu príjem = nízky. [6] 


 

1.4 Výhody a nevýhody algoritmu

Výhodou naivného Bayesovského klasifikátora je jeho jednoduchosť a zrozumiteľnosť. Ide o jeden z najstarších formálnych klasifikačných algoritmov, pričom aj jeho najjednoduchšia forma je často veľmi efektívna. Štúdie ukázali, že jeho účinnosť je porovnateľná s účinnosťou rozhodovacích stromov alebo niektorých neurónových sieti. [2]  Často sa využíva v oblastiach klasifikácie textu, filtrovanie spamu alebo na kategorizáciu dokumentov. Flexibilita algoritmu vyústila k jeho obmenám, ktoré fungujú vo sférach ako dolovanie v dátach, strojové učenie alebo štatistika. Dôsledkom modifikácií sa zvýšila jeho zložitosť, čo narušilo jeho základnu vlastnosť - jednoduchosť. Pozitívom je tiež to, že každá trieda je charakterizovaná pravdepodobnostným popisom. [5] Najväčším negatívom Bayesovskej klasifikácie je naivné predpokladanie nezávislosti atribútov.


1.5 Príklad výpočtu naivného bayesovského klasifikátora

Pre ilustráciu postupu naivného Bayesovského klasifikátora použijeme úlohu o poskytovaní úveru na základe výšky príjmu. [7]

Máme danú trénovaciu množinu príkladov. Objekty v nej sú popísané štyrmi atribútmi (príjem, konto, pohlavie, nezamestnaný). Každý objekt (klienti banky) je zaradený do jednej z dvoch tried, a to – dostal úver alebo nedostal úver. Úlohou je navrhnúť naivný Bayesovský klasifikátor a klasifikovať ním nového klienta, pričom má nasledujúce hodnoty X = (konto=“stredné“, nezamestnaný=“nie“).

Výhodou bayesovských metód je schopnosť klasifikovať príklady do tried s určitou pravdepodobnosťou. Túto pravdepodobnosť môžeme interpretovať ako spoľahlivosť rozhodnutia.

 

Klient

Príjem

Konto

Pohlavie

Nezamestnaný

Úver

K1

Vysoký

Vysoké

Žena

Nie

Áno

K2

Vysoký

Vysoké

Muž

Nie

Áno

K3

Nízky

Nízke

Muž

Nie

Nie

K4

Nízky

Vysoké

Žena

Áno

Áno

K5

Nízky

Vysoké

Muž

Áno

Áno

K6

Nízky

Nízke

Žena

Áno

Nie

K7

Vysoký

Nízke

Muž

Nie

Áno

K8

Vysoký

Nízke

Žena

Áno

Áno

K9

Nízky

Stredné

Muž

Áno

Nie

K10

Vysoký

Stredné

Žena

Nie

Áno

K11

Nízky

Stredné

Žena

Áno

Nie

K12

Nízky

Stredné

Muž

Nie

Áno

Tab. 1 Trénovacia množina príkladov z databázy klientov banky

 

Našou úlohou je zistiť, pre ktorú z dvoch tried je hodnota súčinu P(X|ci).P(ci) maximálna. V prvom kroku vypočítame apriórne pravdepodobnosti jednotilvých tried P(ci), ktoré možno jednoducho určiť z trénovacej množiny

 

P(úver(áno))=8/12=0,667

P(úver(nie))=4/12=0,333


Pre výpočet podmienených pravdepodobností P(X|Ci) je už potrebné pracovať s hodnotami atribútov vstupného objektu a pre každú z nich vypočítať čiastkovú podmienenú pravdepodobnosť. 

P(konto(stredné)|úver(áno))=2/8=0,25

P(konto(nízke)|úver(áno))=2/8=0,25

 

P(konto(vysoké)|úver(áno))=4/8=0,5

P(konto(stredné)|úver(nie))=2/4=0,5

P(konto(nízke)|úver(nie))=2/4=0,5

P(konto(vysoké)|úver(nie))=0/4=0

 

P(nezamestnaný(nie)|úver(áno))=5/8=0,625

P(nezamestnaný(áno)|úver(áno))=3/8=0,375

P(nezamestnaný(nie)|úver(nie))=1/4=0,25

P(nezamestnaný(áno)|úver(nie))=3/4=0,75

  

P(príjem(nízky)|úver(áno))=3/8=0,375

P(príjem(vysoký)|úver(áno))=5/8=0,625

P(príjem(nízky)|úver(nie))=4/4=1

P(príjem(vysoký)|úver(nie))=0/4=0

 

P(pohlavie(muž)|úver(áno))=4/8=0,5

P(pohlavie(žena)|úver(áno))=4/8=0,5

P(pohlavie(muž)|úver(nie))=2/4=0,5

P(pohlavie(žena)|úver(nie))=2/4=0,5

 

 Teraz, keď použijeme tieto čiastkové pravdepodobnosti, môžeme vypočítať celkovú podmienenú pravdepodobnosť. Pre uchádzača o úver, ktorá má stredné konto a nie je nezamestnaný spočítame:

 

P(X|úver(áno))=P(konto(stredné)|úver(áno))xP(nezamestnaný(nie)|úver(áno))=0,25*0,625=0,1563

P(X|úver(nie))=P(konto(stredné)|úver(nie))xP(nezamestnaný(nie)|úver(nie))=0,5*0,25=0,125

 

a teda hodnoty súčinu P(X|ci).P(ci)  pre každú triedu sú:

 

P(X|úver(áno)).P(úver(áno))=0,667*0,1563=0,1042

P(X|úver(nie)).P(úver(nie))=0,333*0,125=0,0416

 

To znamená, že naivný Bayesovský klasifikátor zatriedi daný vstupný objekt do triedy úver(áno). Inými slovami, podľa klasifikátora bude uchádzačovi žiadosť o úver schválená. 


2 Systémy a aplikácie

 „Klasický“ naivný bayesovský klasifikátor je implementovaný v systéme Bayda z univerzity v Helsinkách alebo v systéme RoC z univerzity vo Veľkej Británii. Oba tieto systémy sú voľne dostupné cez internet.

Bayda je softvérový balíček na flexibilné analýzy dát v prediktívnych dataminigových úlohách. Základný matematický model je založený na naivnom bayesovskom klasifikátore a algoritme feature selection. Bayda má niekoľko jedinečných vlastností, ktoré tento softvér odlišujú od štandardných štatistických programov pre klasifikáciu (ako prediktívna diskriminačná analýza alebo balíčky klasifikátorov strojového učenia). Po prvé, na klasifikáciu Bayda používa „úplný“ bayesovský naivný klasifikátor s marginálnou pravdepodobnosťou. Po druhé, Bayda kombinuje manuálny a automatický algoritmus feature selection. Po tretie, Bayda grafické rozhranie je postavené pomocou „inteligentného dokumentu“. Užívateľské rozhranie je vložené do HTML dokumentu a pre každú vykonanú klasifikačnú úlohu Bayda vytvára zodpovedajúcu HTML správu, ktorá vysvetľuje výsledky analýzy. [8]

RoC (Robust Bayesian Classifier) – robustný bayesovský klasifikátor je počítačový program schopný vykonávať kontrolovanú bayesovskú klasifikáciu z nekompletných databáz bez predpokladu o type chýbajúcich hodnôt. RoC je založený na novej metóde odhadu, nazývanej robustný bayesovský odhad. [10]

Zaujímavým systémom vychádzajúcim z naivného bayesovského klasifikátora je systém AutoClass. AutoClass umožňuje odvodiť maximálnu aposteriornú pravdepodobnosť zaradenia do tried pre klasifikované (učenie s učiteľom) i neklasifikované (učenie bez učiteľa) príklady. Pri učení bez učiteľa sa používa EM algoritmus, skrytou veličinou je v tomto prípade informácia o zaradení do triedy. Algoritmus EM umožňuje nájsť pre uvažovaný počet tried najlepšie rozdelenie príkladov do týchto tried. Triedy (zhluky) s malou pravdepodobnosťou sa môžu zanedbať. Priechod cez EM sa potom zopakuje pre menší počet tried. Tento postup umožňuje súčasne stanoviť optimálny počet tried i zaradenie príkladov k týmto triedam.


Iným príkladom systému používajúcom bayesovský prístup k zhlukovaniu príkladov je COBWEB. Tento systém inkrementálnym spôsobom vytvára hierarchiu konceptov metódou zhora-nadol. Nový vstupný príklad sa zaradí buď k existujúcemu konceptu (uzlu hierarchie) alebo sa pre neho vytvorí nový uzol (koncept). V prípade, že príklad bude zaradení do existujúceho uzla, zvažuje sa ešte možnosť tento uzol rozdeliť, respektíve zlúčiť s iným uzlom. Rozhodnutie, ktorá operácia sa pre daný príklad uskutoční (vytvorenie nového uzla, jednoduché pridanie do existujúceho uzla, pridanie a rozdelenie, pridanie a spojenie), závisí na hodnote

 vzorec

ktorá porovnáva podmienenú pravdepodobnosť, že atribút Aj má hodnotu vk , pokiaľ príklad patrí ku konceptu C(vk) s apriornou pravdepodobnosťou, že atribút Aj má hodnotu vk. Pre zaradenie príkladu sa zvolí tá operácia, ktorá maximalizuje uvedenú hodnotu. Pôvodná podoba algoritmu pracovala len s kategorickými dátami, ďalšie verzie umožňovali pracovať i s numerickými dátami. [9] 

 

3 Ukážka aplikácie v RapidMineri

3.1 Údaje

Na ilustráciu naivného bayesovkého klasifikátora v RapidMineri bola použitá databáza vín. Tieto údaje sú výsledkom chemického rozboru vín pestovaných v rovnakej oblasti v Taliansku, ale pochádzajúcich z troch rôznych kultivarov. Analýza určí množstvo 13 zložiek nájdených v každej z troch druhov vín.

Informácie o databáze:

Charakteristika údajov

viacrozmerné

Charakteristika atribútov

prirodzené, reálne

Súvisiace úlohy

klasifikácia

Počet príkladov

178

Počet atribútov

13

Chýbajúce hodnoty

žiadne

Oblasť

fyzikálna

Dátum zverejnenia

1.7.1991

Počet webových výskytov

164813

 

Informácie o atribútoch:

V tejto databáze vín sa nachádza 13 atribútov, z toho sú 2 typu integer, ostatné typu real. Ani jeden z atribútov neobsahuje chýbajúce hodnoty. Na základe týchto atribútov model klasifikuje nový príklad do jednej z troch druhov vín (1-3 (identifikátor triedy)).

 

1) Alkohol
2) Kyselina jablčná
3) Popol
4) Alkalinity popola
5) Horčík
6) Celkové fenoly
7) Flavonoidy
8) Nonflavanoid fenoly
9) Proantokyanidy
10) Intenzity farieb
11) Odtieň
12) OD280/OD315 zriedeného vína
13) Prolín


3.2 Proces

 

V prvom rade je potrebné načítať vstupnú vzorku údajov, ktorá je popísaná vyššie. Vstupná vzorka je súbor typu *.csv oddelený čiarkami.

r1

V konfiguračnom wizarde nastavíme kódovanie na UTF-8 a ako oddeľovač zaškrtneme čiarku.

r2

Ďalej nastavíme typ atribútu "Att1" (identifikátor triedy) na "nominal" a pridelíme rolu atribútu "Label". 

r3

Na obrázku môžeme vidieť metadáta, kde prvý atribút je identifikátor triedy, s pridelenou rolou label a typom nominal a ostatné atribúty majú rolu regular a typ integer alebo real. Vidíme taktiež, že vzorka údajov neobsahuje žiadne chýbajúce dáta.

r4

Na nasledujúcom obrázku už môžeme vidieť konkrétne údaje o jednotlivých zložkách vína.

r5

Na ďalšom obrázku vidíme celý proces. Operátory, ktoré sme po načítaní vstupných dát použili sú Naive Bayes a Apply Model. Takisto sme ešte načítali údaje, ktoré budeme predikovať, tiež typu *.csv.

r6

Po aplikovaní modelu, bayesovský naivný klasifikátor zatriedil 5 predikovaných vín nasledovne: dve do prvej triedy, dve do druhej a jedno do tretej triedy. Výsledky môžeme vidieť na nasledovnom obrázku.

r7

r8

3.3 Súbory

 subory RapidMiner

Zdroje

[1]   PARALIČ, Ján: Objavovanie znalostí v databázach. Košice: Elfa, 2003. ISBN 80-89066-60-7

[2]   HAN, Jiawei - KAMBER, Micheline: Data Mining: Concepts and Techniques. San Francisco: Morgan Kaufmann Publisher, 2003. ISBN 1-55860-901-6

[3]   Wikipedia. Thomas Bayes. [online][08. 12 2011] Dostupné na internete: <http://en.wikipedia.org/wiki/Thomas_Bayes>.

[4]   KAŠČÁK, Pavol: Metody pro klasifikaci dat: Bakalárska práca. [online] Brno: FIT VUT v Brne, 2010. [s.a.]. [cit. 2011-12-08] Dostupné na internete: <http://www.fit.vutbr.cz/study/DP/rpfile.php?id=10647>

[5]   HALAŠ, Marián: Analýza vybraných metód a algoritmov dolvania v dátach. Bratislava, 2009 [online][cit. 2011-12-12]. Dostupné na internete: <http://www2.fiit.stuba.sk/~kapustik/ZS/Clanky0910/halas/index.html>;.

[6]   LEUNG, Ming: Naive Bayesian Classifier. 2008. [online] [cit. 2011-12-12] Dostupné na internete: <http://cis.poly.edu/~mleung/FRE7851/f07/naiveBayesianClassifier.pdf>;.

[7]   BERKA, Peter: Dobývání znalostí z databází. Praha: Academia, 2003. ISBN 80-200-1062-9

  [8]   Petri Kontkanen, Petri Myllym¨aki, Tomi Silander, Henry Tirri: BAYDA: Software for Bayesian Classification and Feature Selection [online][05. 01. 2012] Dostupné na internete: <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.5278>. 

  [9]   BERKA, Peter, [online][05. 01. 2012] Dostupné na internete: <http://sorry.vse.cz/~berka/docs/izi456/kap_5.6.pdf>.

  [10]   M. Ramoni, P. Sebastiani, [online][05. 01. 2012] Dostupné na internete: < http://projects.kmi.open.ac.uk/bkd/>.

 


 


 


 

Principal Component Analysis

Autor: Ladislav Miženko


Popis metódy

Principal Component Analysis, čiže analýza hlavných komponentov patrí medzi metódy analýzy skrytých komponentov, medzi ktoré sa zaraďuje tiež napríklad Faktorová analýza. Takéto metódy používame, keď:

  • premenné nemožno logicky rozdeliť do dvoch skupín na závislé a nezávislé
  • cieľom je zistiť prečo a ako sú premenné vzájomne korelované, čiže ako sa navzájom ovplyvňujú
  • ak sú premenné navzájom korelované, možno rovnaký objem informácií vystihnúť menším počtom premenných – zníženie dimenzie
  • metóda analýzy hlavných komponentov vychádza  z an alýzy kovariačnej, resp. korelačnej matice pôvodných premenných a pokúša sa nájsť skryté – nemerateľné - latent prememnné. Tieto premenné sa nedajú merať, ale majú schopnosť vecnej interpretácie.

RandomForest

Úvod

Random forest je operátor, ktorý pozostáva z podmnožiny podoperátorov, ktorými sú rozhodovacie stromy. Využíva sa na klasifikáciu, alebo regresiu, presnosť. Tento algoritmus vyvinuli Leom Breiman a Adele Cutler. Názov pochádza z random decicion forest, ktoré boli najprv navrhnuté podľa pracovníka Tin Kam Ho v roku 1995. Táto metóda kombinuje Breiman-ov nápad baggingu a náhodný výber funkcií, ktorý bol zavedený nezávisle s cieľom vytvoriť súbor rozhodovacích stromov s riadenou zmenou.

Využitie

Klasifikácia

Úloha datamaingu využívajúca sa pri prediktívnom dolovaní v dátach. Modeluje a predpovedá nominálne atribúty – triedy.  Predikuje kategorické označenia tried (predikovaný atribút je nominálny). Klasifikuje dáta (konštruuje model) na základe trénovacej množiny a daných zaradení do tried v klasifikačnom atribúte.  Skonštruovaný model potom využíva pre klasifikáciu nových príkladov. 

Základný prístup 

 V  prvej fáze snaží vybudovať (naučiť sa) model správania dát na základe nejakej trénovacej množiny. Zostavený (naučený) model správania sa dát je potom v druhej fáze používaný na predpovedanie (predikciu).

 Bagging

Bagging a boosting sú techniky , ktoré sa využívajú na zvyšovanie presnosti klasifikátorov. Využitím  množiny T- klasifikátorov  C1,C2, … , CT v snahe vytvoriť lepší, zložený klasifikátor C*
Popis techniky:

V každej iterácii t (t = 1, 2, ..., T) sa najprv z množiny vytvorí vzorka Ot (existujú rôzne stratégie výberu), následne sa množina Ot použije ako trénovacia množina pre získanie klasifikátora Ct, pre klasifikáciu neznámeho príkladu X zložený klasifikátor C* najprv zistí klasifikácie všetkých čiastkových klasifikátorov Ct (t = 1, 2, ..., T), spočíta hlasy pre jednotlivé triedy. Príklad X nakoniec klasifikuje do tej triedy, ktorá získala najväčší počet hlasov.

Teoretická časť  

  História RF

 V roku 2001 urobil L. Breiman návrh Random forest, ktorý pridáva do techniky bagging ďalšie vrstvy náhodnosti. Do konštrukcie rozhodovacieho stromu pridáva vytvorením novej trénovacej množiny náhodných vzoriek (bootstrap sample) data, čiže pomocou Random forest zmení spôsob konštrukcie klasifikácie  alebo regresie stromu.

V klasických stromoch je každý uzol rozdelený pomocou  najlepšieho delenia vybraného spomedzi všetkých možností.

Použitím Random forest je každý uzol rozdelený prostredníctvom podmnožiny predikovaných hodnôt, vybraných z tohto uzla. Tento spôsob sa javí v porovnaní s inými spôsobmi klasifikácie ( neurónové siete, diskriminačná analýza...) ako najlepší a je odolný voči javu, ktorý nazývame preučenie ( skonštruovaný rozhodovací strom  príliš podrobne kopíruje  charakteristiky príkladov z trénovacej množiny, čo ale môže, znížiť jeho presnosť pre nové, neznáme príklady v budúcnosti.).

Algoritmus Random Forest

Každý strom  zostavovaný podľa tohto operátora má nasledujúci algorutmus: 
Nech počet tréningových procesov je N a počet premenných v klasifikátore je M
Nech je dané, že počet vstupných premenných použitých na určenie rozhodnutia v uzle stromu je m (m by malo byť menej ako M)

Vyberieme si tréningovú sadu pre tento strom výberom  n-krát s výmenou všetkých N dostupných  tréningových  procesov. Použitím zvyšných procesov odhadneme chybu stromu prostredníctvom predikcie ich tried.

Pre každý uzol stromu náhodne vyberieme m premenných, na základe ktorých rozhodujeme v tomto uzle. Vypočítame si najlepšie rozdelenie na základe vybraných m premenných z trénovacej množiny.  

Každý strom je plne dospelý a nie je vyčistený.

Pre predikciu je nová vzorka údajov tlačená smerom  nadol v strome. Je pridelené označenie tréningovej skupiny a končí v terminálovom  uzle. Táto procedúra sa zopakuje nad všetkými stromami v skupine a priemer všetkých stromov je označovaný ako predikcia random forest.   

  Vlastnosti Random forest

 

  • Beží efektívne vo veľkých databázach 
  • Nevyniká v presnosti súčasných algoritmov
  • Dokáže zvládnuť tisíce vstupných premenných bez vymazania premmených
  • Dokáže dať odhad, aké sú premenné dôležité v klasifikácii
  • Vytvára vnútorný odhad generalizácie chyby v postupe v budovaní stromu
  • Je to efektívna  metóda pre odhad chýbajúcich údajov a udržuje presnosť ak chýba veľká časť údajov
  • Obsahuje metódy pre vyrovnanie chyby v triede populácie nevyrovnaných dát
  • Generované foresty je možné uložiť pre budúce použitie v iných dátach
  • Ponúka experimentálnu metódu pre zisťovanie variabilnej interakcie 
  • Prototypy sú vypočítavané ako informácie medzi premennými a klasifikáciou

 

Ako pracuje operátor random forest

  Pre správne použitie operátora random forest potrebujeme informácie, ktoré závisia od dátových objektov generovaných operátorom random forest.

Trénovacia množina je vytvorená zo vzorky údajov a tieto dáta sa nazývajú OOB dáta a sú použité na odhad chyby klasifikácie.

Po tom ako je každý strom zostavený, všetky dáta sa rozvetvia v strome, a “proximieties“ sú počítané pre každý pár prípadov. Ak dva prípady zaberajú rovnaký uzol, ich „proximity“ je zvýšená o jedno. Na konci vetvenia proximities sú normalizované delením počtov stromov. Proximities sú používané v nahradení chýbajúcich dát, nájdením odľahlých hodnôt a produkciou objasnia nízkodimenzionálny pohľad na dáta.  

Odhad chyby

Pre odhad chyby v RF nie je potrebná X-validácia ani triedenie testovacej množiny pridaním odhadov chýb, ale chyba sa odhaduje počas behu použitím rozličných vzoriek bootstrapov z originálnych dát a približne tretina prípadov je vynechaná z bootstrap  vzoriek a nepoužíva sa na konštrukciu „k-tych“ stromov.

Každý vynechaný prípad je pridaný do klasifikácie „k-teho“ stromu. Takto sa klasifikácia testovacej množiny získa pre každý prípad z tretiny stromu a na konci behu ho klasifikuje do tej triedy, kde bol najväčší počet hlasov. 

Interakcie

Operačná definícia interakcií použitá pri premenných „m“ a „k“ interakciách spôsobí rozdelenie z jednej premennej „m“  na „k“ systematicky menších alebo väčších. Použitá implementácia je založená na „gini“ hodnotách pre každý strom v RF. Tie sú zoradené pre každý strom a pre každé dve premenné, absolútne rozdiely ich hodnôt sú priemerné cez všetky stromy .

Tento počet je teda vypočítaný podľa hypotézy, že oba premenné sú nezávislé na ostatných a nasledujúca je odčítaná od predchádzajúcej.  

Zle označené prípady

Tréningové množiny sú často tvorené tak, že „lable“ je priradená ľudským rozhodnutím. V niektorých oblastiach to vedie k vysokej frekvencii nesprávneho označenia. Mnoho zle označených prípadov môže byť odhalené použitím „outlier measure“.

Vzdialené hodnoty (Outliers)

Outliers sú zvyčajne definované ako prípady ktoré sú odobraté z hlavnej časti dát. Inak povedané, sú to prípady v ktorých „proximities“ všetkých ostatných prípadov v dátach sú všeobecne malé. Užitočnou kontrolou je zadefinovanie „outliers“ vo vzťahu k ich triede. Teda“ outliers“  v j-triede je prípad keď proximities  všetkých ostatných prípadoch j-triedy sú malé.

Proximities

 V RF sú „Proximities“ jedným z veľmi užitočných nástrojov. Pôvodne tvorili matice NxN. Potom ako sa strom (tree) vytvorí, potláča (put down) stromom všetky dáta aj z trénovania aj z OOB . Ak prípady „k“ a „n“ sú v rovnakom terminálovom uzle, zvýši sa ich „proximity“ o jedno.  Nakoniec sa normalizujú „proximities“ vydelením počtom stromov (trees) .

Bolo zistené, že s veľkými dátovými množinami, nemohli pridať NXN matice do rýchlej pamäti. Úpravou sa znižila veľkosť potrebnej pamäte pre NXT, kde T je počet stromov v lese. Pre urýchlenie náročne počítaného „SCALING“ (kritéria , meradlá) a opakujúce sa chýbajúca hodnota náhrady, je užívateľovi daná možnosť zachovať iba nrnn najväčšie „Proximities“  ku každému prípadu.

Keď je testovacia množina prezentovaná, bude počítaná „proximities“  každého prípadu  testovacej množiny s každým prípadom v trénovacej množine. Množstvo ďalších výpočtov je pomerne malé.

Scaling – kritéria, meradlá

 „Proximities“ medzi prípadmi „n“ a „k“ matice prox(n,k).Z ich definície je ľahko viditeľné, že táto matica je symetrická, kladne definovaná a zhora ohraničená číslom 1 aj jej diagonálne prvky sú rovné 1. Z toho vyplýva, že hodnoty 1-prox(n, k) sú umocnené vzdialenosti dimenzií Euklidovského priestoru nie sú väčšie ako počet prípadov. Pre podrobnejšie objasnenie metódy „scaling“ pozri "Multidimensional Scaling" by T.F. Cox and M.A. Cox.

Nech prox(-, k) je priemer prox(n, k) vyššej ako 1. Koordinácia,

Nech prox(n, -) je priemer prox(n, k) vyššej ako 2. Korelácia,

Nech prox(-, -) je priemer oboch koordinácii,

 

Potom matica:       cv(n,k)=.5*(prox(n,k)-prox(n,-)-prox(-,k)+prox(-,-))

 

je maticou vzdialeností a je teda kladne jednoznačne (definitívne) symetrická.

Ak vlastné hodnoty “cv“ označíme ako I(j) a vlastné hodnoty „nj(n)“ nj(n),

potom vektor         x(n) = (Öl(1) n1(n) , Öl(2) n2(n) , ...,)

 štorcová vzdialenosť medzi nimi je rovnaká ako v 1-prox(n,k). Hodnoty  Öl(j) nj(n) sú rovnaké ako  j-tá scaling koordinácia.

Myšlienkou v „metric scaling“ je aproximovať vektor x(n) vybratím niekoľkých prvých koordinácii. To urobí RF  získaním zopár najväčších vlastných hodnôt CV matice a im zodpovedajúcim vlastným vektorom.V dvojrozmernom grafe, kde porovnávame i-tu „scaling“ koordináciu s j-tou najčastejšie vyskytujúcou sa pridávanou užitočnou informáciou dát. Najužitočnejšou je zvyčajne graf  „2nd vs. the 1st“.

Vzhľadom k tomu, že výpočet vlastnej funkcie na zopár horných hodnôt NxN matice je zložitý, môže byť časovo náročný. Preto sa odporúča použiť podstatne nižšie nrnn, aby veľkosť vzorky bola vypočítaná rýchlejšie.

K dispozícii sú presnejšie spôsoby projektovania vzdialenosti do nižšich dimenzií,  napr. Roweis a Saul. Ale performácia „matric scaling“ udržuje z implementácie presnejšie projekcie algoritmov. Ďalším aspektom je rýchlosť. „Matric scaling“ je najrýchlejší súčasný algoritmus na projektovanie dole. Zvyčajne tri alebo štyri „scaling“ súradnice postačujú na dobré zosnímanie dát. Vykreslenie druhej „scaling“ kóordinacie oproti prvej dáva zvyčajne jasný pohľad.  

Prototypy  

Prototypy sú spôsoby zobrazenia vzťahu premenných na klasifikáciu. Pre j-tú triedu sa nájde prípad v ktorom má najväčší počet tried j-prípadov spomedzi jeho najbližších susedov stanovený na základe „proximities“. Z týchto prípadov nájdeme median (25 ‰ a 75 ‰). Mediany sú prototypom j-tej triedy a kvartily udávajú odhad stability. Pre druhý prototyp opakujeme postup pričom berieme do úvahy len prípady ktoré nepatria do pôvodnej k-triedy atď. Keď sú prototypy požiadane o zobrazenie alebo uloženie výstupu, prototypy spojitej premennej sú štandardizované odpočítaním 5‰ a vydelenie rozdielu medzi 95‰ a 5‰. Pri kategorizácii premenných je prototyp najčastejšia hodnota. Keď sú prototypy požiadane o zobrazenie alebo uloženie výstupu, všetky frekvencie sú uvedené pre kategorickú premennú.

Chýbajúce hodnoty dopĺňané do tréningových množín

RF má dva spôsoby na nahrádzanie hodnôt.

Prvý spôsob je rýchly. Ak nie je m-tá premenná jednoznačná (kategorická), použije sa metóda ktorá vypočíta  median zo všetkých hodnôt premennej v j-tej triede, a touto hodnotou nahradí vsetky chýbajúce hodnoty m-tej premennej  j-tej triade. Ak m-tá premenná je jednoznačná, náhrada ju najfrekventovanejšia nechýbajúca hodnota v triede j (non-missing). Nahradená hodnota sa nazyva výplň –(fill).

Druhý spôsob nahrádzania chýbajúcich hodnôt je výpočtovo náročnejší, ale je presnejší ako prvý a dokonca môže byť použité väčšie množstvo údajov. Nahrádza chýbajúce hodnoty len v trénovacej množine. Začína hrubým a nepresným vyplnením chýbajúcich hodnôt, potom spustí RF a počíta „proximities“.

Ak x(m,n) je chýbajúca trvalá hodnota, odhadom vyplnenia je priemer nechýbajúcich hodnôt m-tých premenných vážený „proximities“ medzi n-tým prípadom nechýbajúcej hodnoty.  Ak ide o chýbajúcu jednoznačnú premennú je nahradená najfrekventovanejšou nechýbajúcou hodnotou pričom frekvenciou je vážená „proximities“. Teraz znova vytvoríme iteráciou RF pričom použijeme novo vytvorené hodnoty(vyplnením chýbajúcich hodnôt), nájdeme nové výplne (fills) a iterácia prebehne znovu. Na to stačí približne 4-6 iterácií.  

Chýbajúce hodnoty dopĺňané do testovacích množín

Pri testovacej množine máme dva spôsoby nahradenia v závislosti na tom či existuje „lable“ v testovacej množine. Ak existuje, potom sa ako náhrada použije výplň (fill) získaná z tréningovej množiny. Ak „lable“ neexistuje potom každý prípad testovacej množiny je predložený(kopírovaný) „nclass“(nclass=počet tried). Prvý kopírovaný prípad predpokladá, že trieda 1 a trieda prvej výplne sa použije na nahradenie(kopírovanie) chýbajúcej hodnoty. Druhý kopírovaný prípad predpokladá, že sa použije trieda 2 a trieda druhej výplne. Tento rozšírený test prebehne dole stromom (tree). V každej množine opakovaní dostaneme prípad „vote“, ktorý dostane najviac hlasov a ten určuje triedu pôvodného prípadu.

Zle označené prípady

Tréningové množiny sú často tvorené tak, že „lable“ je priradená ľudským rozhodnutím. V niektorých oblastiach to vedie k vysokej frekvencii nesprávneho označenia. Mnoho zle označených prípadov môže byť odhalené použitím „outlier measure“ (v okrajových odľahlých opatreniach). Príklad je uvedený v štúdii DNA prípad.  

Outliers- vzdialené hodnoty

Outliers sú zvyčajne definované ako prípady ktoré sú odobraté-vymazané z hlavnej časti dát. Inak povedané, sú to prípady v ktorých „proximities“ všetkých ostatných prípadov v dátach sú všeobecne malé. Užitočnou kontrolou je zadefinovanie „outliers“ vo vzťahu k ich triede. Teda“ outliers“  v j-triede je prípad keď proximities  všetkých ostatných prípadoch j-triedy sú malé.  

Definícia priemernej poximity n-prípadu v j-triede na zvyšok j-triedy tréningových dát, je nasledovná:

vzorec1 

Čistý (neupravený) „outlier measure“ pre prípad n sú definované ako:

vzorec2 

Výsledok bude veľký ak je priemerná proximity malá. V každej triede nájdeme median týchto neupravených /surových/ measures (opatrení) a ich absolútnu odchýlku medianu. Odčítaním medianu každého neupraveného opatrenia a vyhľadaním absolutnej odchýlky je najdne konecné „outlier measure“.

Praktická časť

Popis operátora Random Forest v RapidMiner-i

Vstupy

Vstupom do operátora je tréningová množina. Čiže vzorka údajov, ktoré  chceme vyhodnotiť.

 Výstupy

Po spustení operátora, ktorému sme nastavili požadované parametre  dostávame  vyhodnotenie - model , ktorý popisuje stromy podľa  nastavených  parametrov.

Parametre

 počet stromov: Počet učiacich sa "random trees" (náhodných stromov)

 - default: 10

 kritérium: Určuje použité kritérium pre výber atribútov a numerickej rozdelí.

 Rozsah: gain_ratio, information_gain, gini_index, presnosť

 - default: gain_ratio

 minimálnu veľkosť pre rozdelenie: Minimálna veľkosť uzla potrebná na rozdelenie.

 - default: 4

 minimálna veľkosť listov: Minimálna veľkosť všetkých listov.

 - default: 2

 minimálny zisk:

 Minimálny zisk, ktorý je potrebné dosiahnuť za účelom vytvorenia rozdelenia.

 - default: 0.1

 maximálna hĺbka: Maximálna hĺbku stromu (-1: nie viazané)

 - default: 20

 istota: Úroveň spoľahlivosti použitá pre výpočet pesimistickej chyby

 pri "pruning-u" (prerezávanie).

 -default: 0.25

 Počet alternatív "prepruning": Počet alternatívnych uzlov, keď sa

 snažil prepruning zabránirozkolu.

 - default: 3

 No pre-pruning: Vypne pre pruning (pred prerezávanie) a dodáva strom

 bez prepruning.

 No-pruning: Vypne prerezávanie a poskytuje unpruned  (neperezaný) strom.

 Odhad pomeru pormnožiny: Ukazuje, že log (m) + 1 funkcií sú používané,

 inak pomer musí byť uvedený.

 Podmnožina koeficient: Pomer náhodne vybraných testovacích atribútov.

 Použitie lokálneho náhodného potomka: Určuje, či miesty náhodný

 potomok by mali byť použité.

 Lokálny náhodný potomok: Špecifikuje lokálneho náhodného potomka

Praktické využitie operátora Random Forest

Ako testovciu vzorku pri praktickom využití sme použili súbor zo vzorových dát programu RapidMiner s názvom „Golf“ . V tomto súbore sa na základe atribútov: Outlook, Temperature, Humidity a Wind rozhoduje o tom, či sa bude alebo nebude hrať ( Play – Yes or No).

datagolf 

Obrázok1: Dáta v trénovacej množine  

Na tomto súbore, ktorý sme vložili z repozitára, sme aplikovali operátor Random Forest, ktorý nájdeme  ako: Modeling/Classification and Regression/Tree Induction/Random Forest , alebo do filtra napíšeme: Random Forest (príp. Forest). Ako už bolo spomenuté v popise, parametre operátora je možné meniť na základe vlastných požiadaviek. My sme však nechali prednastavené (default) hodnoty.

 RF

  Obrázok2: Prostredie rapidmineru s operátorom random forest

 

Po spustení procesu sa vo výslednom modeli zobrazí základné nastavenie MetaModelu, kde si môžeme vybrať, ktorý strom nás zaujíma. Počet stromov sme nastavili v parametroch. Keďže u nás to bolo 10, v ľavom okne Random Forest Model vidíme Model 1 – Model 10. Tieto stromy môžeme jednotlivo prehliadať.

3

Obrázok3: Meta model - základné vyhodnotenie dát

Po kliknutí na vybraný model, sa nám daný model zobrazí a vidíme vyhodnotenie. Daný strom si môžeme zmenšiť alebo zväčšiť pomocou funkcie Zoom.  Funkcia Mode slúži na manuálne úpravy vizualizácie stromu alebo posun ceého stromu po zobrazovacej ploche.  V nasledujúcom Selecte si môžeme vybrať spôsob zobrazenia stromu z 9 možností: Tree, Tree(Tight), Radial, Balloon,  ISOM, KKLayout, FRLayout, Circle a Spring. Ako je vidno na obrázku sú checkboxy pri Node Labels a Edge Labels zaškrtnuté.

4

  Obrázok4:  Meta model – grafické vyhodnotenie prvého stomu

  Ak ich odšrtneme zmizne graficka úprava ako to vidno na obrázku 5:

5

  Obrázok5 Meta model – grafické vyhodnotenie prvého stomu - možnosti zobrazenia

  Pre textové vyhodnotenie stačí prekliknúť na Text view.

6

Obrázok6: Meta model – textové vyhodnotenie prvého stomu  

  Zobrazenie jednotlivých stromov:

strom1

Obrázok7: Strom č.1  

strom2

  Obrázok8: Strom č.2

strom3

Obrázok9: Strom č.3  

strom4

Obrázok10: Strom č.4  

strom5

Obrázok11: Strom č.5  

strom6

Obrázok12: Strom č.6  

strom7

Obrázok13: Strom č.7  

strom8

Obrázok14: Strom č.8 

strom9

Obrázok15: Strom č.9 

strom10 

Obrázok16: Strom č.10  

Záver

Operátor random forest je príkladom nástroja, ktorý je užitočný pri analýze vedeckých dát. Ale ani tie najlepšie algoritmy nedokážu nahradiť ľudskú inteligenciu a problematiku znalostí dát. Treba zoberať do úvahy výstup random forestov ako nie absolútnu pravdu, ale iba ako inteligentne počítačom generované odhady, ktoré môžu byť užitočné a môžu viesť k pochopeniu problému.

Zdroje 

http://www.stat.berkeley.edu/~breiman/RandomForests/cc_home.htm

http://en.wikipedia.org/wiki/Random_forest

http://rapid-i.com/wiki/index.php?title=Random_Forest#Description

J. Paralič: Objavovanie znalostí v databázach. Elfa, Košice 2003, ISBN 80-89066-60-7, 80 s.

 

Využitím  množiny T- klasifikátorov  C1,C2, … , CT v snahe vytvoriť lepší, zložený klasifikátor C*
Attachments:
Download this file (operator random forest.rar)random forest[random forest]470 Kb

Neural Net; Perceptron

Autori: Dušan Salaj

           Marián Kall

 

Obsah

 

1     Úvod. 3

2     Proces CRISP-DM... 3

3     Pochopenie problému. 3

3.1 Stanovenie cieľa a ohraničení pre úlohu. 3

3.2 Neurónové siete. 4

4     Pochopenie dát 4

5     Príprava dát 6

6     Modelovanie. 7

6.1 Clementine. 7

6.2 RapidMiner 9

7     Vyhodnotenie. 12

8     Nasadenie. 12

9     Zdroje

 

       1  Úvod

V tejto práci sa budeme zaoberať využitím neurónových sietí (ďalej iba ako NN) pri predikcii vývoja finančných časových radov. Práca je rozčlenená na šesť  častí podľa procesu zvaného CRISP-DM (Industry Standard Process for Data Mining), kde každá časť zodpovedá práve jednej fáze z tohto procesu. 

 

        2  Proces CRISP-DM

Na začiatok si povieme niečo o procese CRISP-DM, podľa ktorého bude celá práca písaná.

Proces CRISP – DM vznikol ako iniciatíva, ktorej hlavnou úlohou je štandardizácia KDD (objavovanie znalostí v databázach). Samotné KDD nemá štandardizovanú metodológiu, čím vzniká nebezpečenstvo, že každá organizácia si vytvorí svoj vlastný procesný model, čo má za následok, že nie je možné systematické porovnávanie týchto modelov pri objavovaní znalostí.

Samotný proces pozostáva zo 6 častí (fáz):

  • Fáza pochopenia problému (cieľa)
  • Fáza pochopenia dát
  • Fáza prípravy dát
  • Fáza modelovania
  • Fáza vyhodnotenia
  • Fáza nasadenia

    3  Pochopenie problému

    V tejto časti sa budeme zaoberať pochopením obchodných alebo iných cieľov a požiadaviek, a budeme sa snažiť ich pretransformovať na konkrétnu definíciu úlohy dolovania. Taktiež sa bližšie pozrieme na NN.

         3.1    Stanovenie cieľa a ohraničení pre úlohu

Najprv sa pozrieme na ohraničenia, ktoré nás navedú na stanovenie cieľa.

Úloha spočíva v obchodovaní menových párov na finančných trhoch. My sa budeme zaoberať iba jedným menovým párom – euro/dolárom, EUR/USD  (prvé ohraničenie), pričom nebude pre nás podstatné, či budeme daný pár nakupovať - BUY alebo predávať - SELL (pre naše potreby je postačujúce, ak si to definujeme takto). Taktiež zisk budeme vyčíslovať pri objeme obchodov 0,1 Lotu (= veľkosť obchodu, čo je vlastne 10000 jednotiek daného páru), čim si vlastne zabezpečíme to, že sa nám bude ľahšie vyjadrovať zisk – pohyb o päť desaťtisícin predstavuje jednu jednotku zisku (pre našu úlohu, bude opäť stačiť takto zadefinované). Ďalším ohraničením bude tzv. time-frame (v skratke TF, čo nám predstavuje pohyb kurzu za isté časové obdobie, napr. TF 5min nám bude ukazovať pohyb kurzu každých 5min.) – bližšie sa tomu budeme venovať v časti pochopenie dát .

Teraz môžeme prejsť k stanoveniu cieľa úlohy. Naším cieľom bude nájsť a optimalizovať takú stratégiu, ktorá nám bude prinášať najväčší zisk. Ak sa na to pozrieme z iného uhla pohľadu, tak naším cieľom nebude predikovať n+1,n+2...n+k hodnotu časového radu, ale budeme predpovedať, akú operáciu v danom momente máme vykonať, čiže aký typ obchodu máme otvoriť. Budeme vytvárať predikčný model v 2 programoch – SPSS Clementine a RapidMiner.

Na záver si zvolenú stratégiu vyhodnotíme vzhľadom na dosiahnutý zisk a porovnáme navzájom výsledné modely z oboch programov.

. 12

            

         3.2    Neurónové siete

 

Neurónové siete (Neural Networks - NN) sú inšpirované biologickými nervovými sieťami, najmä  ľudským mozgom. Tak, ako  ľudský mozog, aj NN je zložená z neurónov, ktoré fungujú paralelne. Samotný neurón pozostáva zo vstupu do neurónu, prahu,  čo je vlastne hodnota, ktorá prispieva ku vstupu z externého prostredia, aktivačnej funkcie a výstupnej  funkcii z neurónu.

Základnou vlastnosťou NN je ich schopnosť aproximácie funkcie, čiže vie napodobniť správanie každého systému. V našom prípade dokáže NN abstrahovať pravidlá zo vstupných dát a následne ich aplikovať na akékoľvek ďalšie dáta. Výhodou je, že NN nepotrebuje žiadne  predpoklady o modeli, vystačí si iba s dátami. Proces abstrakcie pravidiel sa nazýva učenie. Samotné učenie prebieha tak, že sa menia hodnoty synaptických váhových spojení. Po ukončení učenia je NN schopná produkovať výstupy podľa pravidiel, ktoré  aplikovala na vstupné dáta. Nevýhodou je, že znalostí, ktoré NN nadobudla počas učenia, nie je možné získať v explicitnom tvare, keďže jej znalostí sú obsiahnuté v synaptických váhach resp. ich hodnotách.

Existuje viacero typov NN, my v našom modeli (v oboch programoch) použijeme doprednú neurónovú sieť (feed-forward neural networks) známu tiež ako viacvrstvový perceptrón (Multilayer Perceptron). Neuróny v tejto sieti sú usporiadané vo vrstvách. Typicky je tam jedna vrstva na vstup – vstupná vrstva, jedna alebo viacero aplikačných vrstiev – skryté vrstvy a jedna vrstva pre výstup – výstupná  vrstva. Každá vrstva je prepojená s predchádzajúcou a nasledujúcou vrstvou. Pri učení sa používa metóda spätného šírenia chýb, kde každý záznam po predložení sieti počas učenia šíri informáciu dopredu celou sieťou a tak generuje predikciu  z výstupnej vrstvy. Táto predpoveď sa porovnáva s výslednou hodnotou učenia a rozdiel medzi predpovedaným a aktuálnym výsledkom sa šíri späť celou sieťou a upravuje synaptické váhy, aby dokázali lepšie predpovedať.

 

Vo všetkých neurónoch sa používa nelineárna aktivačná funkcia, pričom existujú dva typy týchto funkcií (obe funkcie sú sigmoidy) :

 rovnica

 

Pričom prvá je funkcia hyperbolického tangensu a je v rozmedzí -1 a 1, a druhá predstavuje logistickú funkciu v rozmedzí 0 a 1. Output i-teho neurónu predstavuje yi a vi je 

suma váh vstupných synapsií. 

Spätné šírenie chyby je vyjadrené ako j v n-tom bode dát : 

rovnica 5


kde d je cieľová hodnota a y je hodnota vypočítaná NN, takto spravíme korekciu na váhach, čím minimalizuje chybu celého výstupu, daného: 

rovnica2

 

Pričom každá zmena váh sa dá vyjadriť:

rovnica3

 

kde yi je výstup predchádzajúceho neurónu, n (pred deriváciou) je tzv. learning rate, čiže váha učenia – bežne sa nastavuje v rozmedzí 0.2 až 0.8. Samotná derivácia sa dá vyjadriť ako:

rovnica4

pričom derivované phi je derivácia aktivačnej funkcie.

 

Perceptron

Je najjednoduchšia dopredná neurónová sieť (single-layer perceptron), pričom je to vlastne binárny klasifikátor, ktorý vstup x do výstupu f(x), pričom :

rovnica6

kde w predstavuje vektor váh a b (tzv. bias), ktorý nezávisí na žiadnej vstupnej hodnote.

Učiaci algoritmus spočíva v počiatočnom iniciovaní váh a prahu, následne sa počíta output:

rovnica 7

 

kde j predstavuje každé dáta v trénovacej množine D, xj je vlastne vstup z týchto dát a dj predstavuje output. Potom sa adaptujú váhy:

rovnica 8

kde i je z interval <0,n>. Následne sa učiaci algoritmus opakuje, kym iteračná chyba nie je menšia ako ako užívateľom zadaný prah.

 

4 Pochopenie dát

 

V tejto časti sa budeme zaoberať najme predspracovaním dát, čiže pochopením z čoho sú dáta zložené a čo nám predstavujú. Odkiaľ a ako sme dáta získali nie je pre našu úlohu veľmi podstatné, takže sa tejto časti v pochopení dát nebudeme venovať.

Predspracovanie dát môžeme rozdeliť na 5 krokov:

1.Krok – spočívapochopení z čoho naše dáta budú pozostávať. Ak sa pozrieme na sviečky na obrázku 1, ktoré nám predstavujú vývoj kurzu za isté časové obdobie, tak vidíme, že jedna sviečka nám ukazuje hodnotu kurzu na začiatku a na konci tohto obdobia, taktiež vidíme aj maximum a minimum, a z farby sviečky vieme určiť, či kurz klesol (čierna) alebo vzrástol(biela). Pre nás bude podstatná otváracia a zatváracia hodnota a taktiež si budeme všímať pokles alebo rast kurzu. Ešte dodáme, že zatváracia hodnota sviečky, je otváracou hodnotou sviečky, ktorá nasleduje za ňou.

 

 sviecky v_grafe

2.Krok – ako sme už spomínaliprvom kroku, budeme sa zaujímať o otváraciu a zatváraciu hodnotu, čo pre nás budú predstavovať vstupné parametre, a o rast resp. pokles, ktorý pre nás bude predstavovať výstupný parameter. Výstupný parameter ovšem nebude priamo ukazovať či kurz vzrástol alebo klesol, ale bude rast resp. pokles bude priemetnutý do pozície akú mame otvoriť, čiže ak nám vyjde, že kurz za sledované obdobie klesol, tak dostaneme signál na otvorenie predajnej pozície (SELL), čiže -1, ak vzrástol , tak nákupnej pozície (BUY), čiže 1. Pridáme ešte jeden signál – 0, ktorý nám bude signalizovať „nerob nič“, čiže nemáme otvárať žiadnu pozíciu – čo presne znamená, že kurz vzrástol/klesol resp. o koľko v súvislosti so signálmi si definujeme v štvrtom kroku.

3.Krok - tretí krok priamo súvisíprvými dvoma a to už niekoľko krát spomínaným časovým obdobím (TF). Je nutné vybrať vhodný TF, aby sme mali vyvážene triedy pre všetky 3 signály, resp. aby si sme sa nedostali do situácie, že NN nám bude predikovať signály „nerob nič“ (keďže sme zameraný na dosiahnutie maximálneho zisku, tak najbezpečnejšia stratégia bude ak nebudeme otvárať žiadne pozície, bez ohľadu na to, že nič nezarobíme, hlavne, že nič neprerobíme) – tento krok je priamo nadviazaný na nasledujúci krok.

4.Krok – ako sme spomínalidruhom kroku, je potrebné určiť (vyjadriť), čo znamená či kurz vzrástol resp. klesol a taktiež čo znamená signál nerob nič. Ako už bolo spomenuté, chceme byť čo najziskovejší, čiže na jednej sviečke by sme chceli zarobiť čo najviac (či už na poklese alebo raste), na to potrebujeme vedieť otváraciu a zatváraciu hodnotu sviečky, taktiež nás bude zaujímať rozdiel medzi týmito dvoma hodnotami, a práve tento rozdiel bude kľúčový pre určenie našich signálov. Je samozrejme, že rozdiel týchto hodnôt bude pre každú sviečku iný, no my sa to pokúsime zovšeobecniť, čiže ak tento rozdiel je väčší ako X tak daj signál 1, ak bude menši tak -1, ak bude medzi týmito hodnotami tak 0. Matematicky:

Rozdiel > x => 1 (rast), rozdiel < -x => -1 (pokles), ak rozdiel bude patriť do množiny (-x, x) => 0 (nerob nič). Pre nás bude teda podstatné správne určiť to X aj vzhľadom na spomínané nebezpečenstvo v 3 kroku. Naše X teda predstavuje min. hranicu, ktorú by sme chceli zarobiť na každej sviečke.

Pre názornejšie pochopenie sa môžeme pozrieť na tabuľku č.1, kde je vybraný TF 5min a x=0.0005, čiže sa snažíme každých 5 minút zarobiť aspoň 5 jednotiek (dolárov).

 

Open

Close

Signál

1,43261

1,4323

0

1,4323

1,4329

1

1,4329

1,43292

0

1,43292

1,43285

0

1,43285

1,43302

0

1,43302

1,43235

-1

1,43235

1,43234

0

 

5.Krok – ak už budeme mať všetky predchádzajúce kroky, tak si určime časové okno, čiže budeme vedieť povedať, čo sa dialo v čase t, t-1, t-2 až t-5, čím vlastne pokryjeme 6 sviečok (využitie pri modelovaní resp. pri predikcii).

 

 5 Príprava dát

 

V tejto časti sa budeme venovať prediktívnemu dolovaniu v dátach, čo predstavuje kontrolované učenie, v rámci ktorého sa tvorí model pre predikciu, keďže náš cieľový atribút je numerický, hodnôt cieľového atribútu pre nové objekty.

V predchádzajúcej kapitole sme sa oboznámili so zložením dát, ako budeme s nimi pracovať a čo ma byť naším výsledkom. Je nutné ešte dodať, že dáta pre trénovaciu množinu budú z obdobia 5.4.2010 00:00 – 1.4.2011 22:00 a pre testovaciu 4.4.2011 00:00 – 30.9.2011 22:00, pričom sme sa snažili zvoliť obdobie tak, aby trénovacia množina bola k testovacej v pomere 2:1. Taktiež sme spomínali, že je nutné zvoliť správny TF a „naše X“, my sme si zvolili, že si budeme vyberať medzi 10,15,30, 60 a 240 minútovým TF, a za X sme si zvolili 5, 10, 15 a 20 (pohyb kurzu o 5,10... desaťtisícin) tak, aby sme dosiahli čo najvyváženejšie triedy vzhľadom na signály (výstupy). Výsledky si môžeme pozrieť v nasledujúcej tabuľke:

 

 

 

Granularita

10Min

15Min

30Min

1Hod

4Hod

Signály

Signály

Signály

Signály

Signály

Zisk

1

0

1

1

0

1

1

0

1

1

0

1

1

0

1

5

7257

22551

7471

5918

13144

5863

3725

5025

3722

2234

1844

2168

677

241

691

10

2818

31647

2914

2660

19496

2769

2190

8138

2144

1528

3219

1499

581

456

572

15

1141

35051

1187

1252

22344

1329

1274

9918

1280

1005

4207

1034

478

664

467

20

536

36305

538

596

23704

625

737

10977

758

695

4831

720

403

802

404

 

 

Po tomto vyhodnotení si musíme zvoliť vhodnú granularitu dát, čo pre nás znamená vybrať TF a zisk taký, aby počet nákupných signálov (1) a predajných signálov (-1) bol v súčte aspoň taký ako počet signálov pre „nerob nič“ (0). Pri pohľade na tabuľku je jasné, že TF 10min nepripadá v úvahu pre žiaden zisk, rovnako to bude aj pre 15min a 30min, aj keď tam by sme mohli relatívne uvažovať o dátach pri zisku 5 jednotiek resp. pre 30min by to bol vhodný výber, no keď sa pozrieme na 1hod dáta, tam si už môžeme vybrať z dvoch, pri 4 hodinových nám dokonca sedia všetky. Problém ovšem pri 4hodinových dátach je ten, že máme málo záznamov. Vzhľadom nato sme sa rozhodli zobrať hodinové dáta a zisk 10jednotiek. Tu nastáva otázka, že prečo sme nezobrali hodinové so ziskom 5, veď je tam viac dát a tiež počet signálov na otvorenie nejakej pozície krásne prevyšuje počet signálov nerob nič, nerozhodli sme sa pre nich jednak práve kvôli spomínanému faktu – vzniknutý predikčný model by mohol byť oveľa náchylnejší na riziko, resp. vzhľadom na vysoký počet signálov na otvorenie nejakej pozície, by sa mohol model naučiť predikovať najme tieto signály, čo by v konečnom dôsledku nemuselo byť vhodné – vzrástol by počet falošných (zlých) signálov a jednak – aj keď sme na začiatku spomínali, že nebudeme klásť dôraz na poplatky za otváranie pozíc brokerovi (v našom prípade sa poplatok za otvorenie jednej pozície pohybuje na úrovni 0,0002 x veľkosť pozície – v našom prípade je veľkosť pozície fixná, čiže zisk z jednej pozície by sa automaticky znížil o 2, strata by narástla o 2), v konečnom dôsledku sme brali ohľad aj na to.

Výsledkom prípravy dát je, že sme zvolili 60min resp. 1hod TF a očakávame zisk na jednej sviečke o veľkosti 10 jednotiek.

 

 

6 Modelovanie

Túto kapitolu rozdelíme na dve časti a to na model pre program Clementine a model pre program RapidMiner.

6.1 Clementine

Použité moduly:

  • Analysis - hodnotí schopnosť prediktívneho modelu generovať presné predpovede. Nastavili sme, že chceme presnosť vidieť v kontigenčnej tabuľke.
  • History - tento modul sa najčastejšie používa pre sekvenčné dáta, ako sú

časové rady. History node vytára nové pole obsahujúce dáta z predchádzajúcich

záznamov. Nastavili sme, že chceme mať posledných 6 sviečok v dátach, čiže pred našou sviečkou pokryjeme 5 hodinové časové okno.

  • Neural network – modul pre neurónovú sieť, v tomto module sme nič nenastavovali, nechali sme prednastavené nastavenia.
  • Type – je modul, v ktorom špecifikujeme vlastnosti premenných, ktoré sa

nachádzajú v dátach, napr. určujeme  či premenná je typu integer (celé  číslo)

alebo string (reťazec písmen).

  • Table - umožňuje zobraziť dáta v tabuľke alebo ich uložiť do súboru
  • V modeli sa ešte nachádza jeden modul, ktorý nám vlastne reprezentuje výsledok učenia NN (žltá farba).

 

 model tren

 

 

Ako vstup pre model slúžia dáta, v history module nastavíme okno na hodnotu šesť,  čím si zabezpečíme spomínaný tridsať minútový interval. V module type si dodefinujeme dáta, otváraciu  a zatváraciu hodnotu označíme ako typ range (rozsah hodnôt) a označíme ich ako vstupné dáta. Signály označíme ako výstupné dáta a typ im nastavíme na set (nadobúdajú hodnoty iba -1, 0, 1). Na type napojíme NN a spustíme modul. Tým vlastne prebieha učenie neurónovej siete. Po skončení dostaneme výsledok a ten napojíme na modul type a pridáme modul analyze, ktorý taktiež napojíme na výsledok učenia, viď. Obr. 2.

 vysledok tren2

 

Vidíme, že výsledok nie je veľmi dobrý, NN správne predikovala niečo viac ako polovicu prípadov, pričom skoro rovnaké množstvo predikovala aj nesprávne, čiže skoro 50:50, čo je vlastne pravdepodobnosť rovná akoby sme hádali. Z tohto výsledku môžeme usudzovať, že po aplikovaní učenia na testovaciu množinu náš výsledok nebude dobrý.

Aplikáciu učenia na testovaciu množinu si môžeme pozrieť na Obr. 4 :

 model test

 

 

6.2 RapidMiner

 

Použité moduly:

  • Retrieve – dáta sme získali pomocou načítania z excelovského súboru.
  • Set Role – nastavuje rolu atribútu. My sme to využili na nastavenie id pre dátum
  • Windowing – modul, ktorý nám poslúžil na vytvorenie časového okna.

Pre trénovaciu množinu:

  1. o– nechali sme nastavenie encode series examples
  2. o– určuje vzdialenosť medzi poslednou hodnotoučasovom okne a predikovanou hodnotou, my sme to nastavili na 1, čiže vytvoríme časové okno a ďalšia hodnota bude predikovaná hodnota
  3. o– veľkosť časového okna, nastavili sme na 6 (t,t-1, t-2, ..., t-5)
  4. o– tu sme vlastne nastavili ako sa bude tvoriť okno (t, t-1 ...) – znižovať o 1, čiže sme nastavili na 1
  5. o– nechali sme zaškrtnuté
  6. o– zaškrtli sme, keďže label je vlastne output, tak sme aj nastavili hodnotu label attribute na „Signal(buy:1,sell:-1,nic:0)“

Pre testovaciu množinu:

  1. o parametre ostali rovnaké ako pri trénovačke, nechali sme zaškrtnuté create labellabel attribute na „Signal(buy:1,sell:-1,nic:0)“, keďže chceme predpovedať práve tento atribút (bez toho by sme dostali nezrozumiteľnú predikciu, ktorá by sa pohybovala v intervale -1 a 1, koniec koncov vo výsledku aj tak bude figurovať, ale nás bude práve zaujímať predikovaná hodnota label atribútu).
  • Sliding Window Validation – modul pre finančné časové dáta
  1. o– model pre neurónovú sieť, nechali sme pôvodné nastavenia
  2. o– výsledok učenia NN (rovnako použitý aj pri testovacej množine)
  3. o– modul slúžiaci na vyhodnotenie predikcie

 

                  -Horizon – nastavený opäť na 1

                  -Main criterion – nastavený na first, je to kritérium slúžiace na porovnávanie      vektorov

                  - 

Ostatné položky sme nechali zaškrnuté


  • Write model – modul slúžiaci na uloženie modelu, model sa automaticky uloží na určené miesto, s určeným menom po zvalidovaní procesu
  • Read model – podobne ako write, akurát načítava model

Priebeh modelovania:

Načítali sme dáta pre trénovaciu množinu a nastavali dátum ako ID, vytvorili sme časové okno, aplikovali na to neurónovú sieť a následne vyhodnotili presnosť jej učenia. Výsledný model sme uložili, aby sa dal použiť pri testovaní viď. Obr. 5 a 6. 

Pri testovaní sme na načítali dáta na testovanie, opäť nastavili rolu dátumu ako ID, vytvorili časové okno a aplikovali výsledok učenia z trénovacieho modelu na nové dáta viď. Obr. 7.

 trenovacka

 

trenovacka2

 

 

Výsledná presnosť bola dostačujúca (lepšia ako v prípade modelu v Clementine) :

vysledok tren


 

Čo je vlastne 84,4% presnosť učenia NN.

Model pre testovaciu množinu:

testovacka

 

 

 

 

7 Vyhodnotenie

Vyhodnotenie rozdelíme opäť na dve časti – Clementine a RapidMiner.

Clementine:

Na ďalšom obrázku môžeme vidieť aplikáciu učenia na testovacie dáta:

vysledok test

 

Ako si môžeme všimnúť naša úspešnosť nebola veľmi vysoká, práve naopak, viac sme predikovali nesprávne ako správne. Paradoxne podarilo sa nám dosiahnuť práve to, čomu sme sa snažili vyhnúť – NN na predikovala najme také signály, ktoré nám oznamovali, že nemáme vykonať žiadnu akciu a aj to viac ako polovica tých signálov bola zlá. O nejakej ziskovosti je ťažké hovoriť, keďže reálne by sme podľa tejto predikcie otvorili iba 3 pozície, aj keď správne, ale v podstate na počet potencionálnych obchodov, je to strašne chabý výsledok.

     Ak sa spätne pozrieme na výsledok pri trénovacej množine, už tam si môžeme všimnúť, že naše učenie dopadlo zle (nebrať v úvahu % úspešnosti), keďže skoro všetky predikcie sa týkali signálu „nerob nič“ – 0. Ak by sme sa rozhodli tento model opraviť, práve tam by museli nastať zásadné zmeny.


 

RapidMiner

 

Na exportovanie výsledkov predikcie sme použili modul write csv, ktorý nám zabezpečil, že sme sa mohli dostať ku konkrétnym hodnotám predikcie. Tie sme potom porovnali so skutočnými hodnotami signálov a vypočítali presnosť predikcie.

Potencionálny zisk – označený ako zisk 1.0 predstavuje ušlý zisk, to znamená, že mali sme možnosť zarobiť, ale NN predpovedala zlý signál, napr. mali sme otvoriť pozíciu, no my sme dostali signál nerob nič, tak sme prišli o zisk (relatívne aj stratu), toto číslo je čisto teoretické a vykazali sme tam stratu. Podstatný je ďalší sledovaný ukazovateľ a to reálny zisk-označený ako zisk 2.0, ktorý bral v úvahu iba otvorené obchody, ktoré sme spravili. Tam sa nám podarilo dosiahnuť symbolický zisk resp. zhodnotenie o 1,94%, viď. priložený súbor.

 

8 Nasadenie

Zistené výsledky by sme mohli aplikovať do vytvorenia AOS (automatický obchodný systém) s NN, ktorý by bol schopný samostatne predpovedať vývoj trhu a na základe toho obchodovať. 

Ďalšou variantou by mohol byť obchodný systém, ktorý by síce samostatne neobchodoval, no poskytoval, by informácie obchodníkovi a ten by sa na základe nich rozhodoval. V našej práci sme sa nezaoberali mierou akceptácie jednotlivých signálov NN, keďže sme automaticky akceptovali signál, ktorý sme dostali. Práve táto informácia by mohla byť pre obchodníka užitočná.

 



9 Zdroje

 

 

KALL, Marián: Predikčné úlohy v obchodných stratégiách na finančných trhoch. Bakalárska práca. Košice: Technická univerzita v Košiciach, Fakulta elektrotechniky a informatiky, 2010. 52 s.

 

http://en.wikipedia.org/wiki/Multilayer_perceptron

 

 

http://en.wikipedia.org/wiki/Feedforward_neural_network

 

 

http://en.wikipedia.org/wiki/Perceptron

 

Attachments:
Download this file (clementine.rar)clementine.rar[ ]20 Kb
Download this file (data.rar)data.rar[ ]216 Kb
Download this file (dokumenty.rar)dokumenty.rar[ ]304 Kb
Download this file (RapidMiner.rar)RapidMiner.rar[ ]112 Kb

Random Forest

Úvod

Random forest je operátor, ktorý pozostáva z podmnožiny podoperátorov, ktorými sú rozhodovacie stromy. Využíva sa na klasifikáciu, alebo regresiu, presnosť. Tento algoritmus vyvinuli Leom Breiman a Adele Cutler. Názov pochádza z random decicion forest, ktoré boli najprv navrhnuté podľa pracovníka Tin Kam Ho v roku 1995. Táto metóda kombinuje Breiman-ov nápad baggingu a náhodný výber funkcií, ktorý bol zavedený nezávisle s cieľom vytvoriť súbor rozhodovacích stromov s riadenou zmenou.

Využitie

Klasifikácia