Rozhodovací tabulky a stromy

Příklad rozhodovacího stromu

Rozhodovací strom je nástroj, jehož cílem je nalézání skrytých závislostí v datech.

Konstrukce rozhodovacích stromů je jednou ze základních a nejčastěji využívaných metod dataminingu (dobývání znalostí z dat). Slouží jako jakási podpora pro rozhodování, která je znázorněna v podobě modelu rozhodnutí a jejich možných důsledků. Používají se k analýze rozhodování a nalezení strategie, která s největší pravděpodobností dosáhne požadovaného cíle. Fungují na tom principu, že se k existujícím datovým záznamů přiřadí cílový atribut (z pravidla v binární podobě 1/0) a jsou dále kombinovány příslušné otázky tak, aby každá cesta vedla k jasnému výsledku. K jejich sestavování se využívají tzv. rozhodovací tabulky, které jsou tvořeny souborem rozhodovacích pravidel, otázkami ve formě booleovských atributů a samozřejmě výslednými rozhodnutími.

Důvodů pro využívání této techniky může být hned několik, mimo jiné například to, že je velmi přehledná a snadno interpretovatelná a výsledky je možné jednoduše vyhodnotit. Výsledek lze snadno interpretovat například v prezentaci a jednoduše vysvětlit případným zájemcům. Zároveň je výhodou, že rozhodovací strom si v podstatě sám určí, které atributy jsou pro získání výsledku relevantní a lze pak snadno poznat, které otázky je možné úplně vynechat.

Cílem rozhodovacího stromu je rozhodnutí se na základě několika faktorů – uzlů. Každý z uzlů stromu představuje jednu vlastnost, jednu otázku, kde je potřeba vybrat z několika variant. Na základě kombinací rozhodnutí v jednotlivých uzlech daná větev stromu dovede uživatele k příslušnému výsledku. Může se zdát, že rozhodovací stromy často vedou k rozhodnutím, která by bylo možné intuitivně odhadnout. Proti tomu však stojí fakt, že výsledky vzniklé z rozhodovacích stromů jsou podloženy konkrétními daty a navíc je díky nim možné odhalit spojení, která až tak intuitivní nejsou. Příklad konkrétního využití rozhodovacích stromů můžeme ukázat na příkladu z bankovnictví . Banka v tomto případě využije rozhodovací strom jako nástroj, který porovná různé faktory, které ovlivňují, zda klient získá půjčku, či nikoliv.

Rozhodovací tabulky

Rozhodovací tabulka je tvořena otázkami, rozhodovacími pravidly a rozhodnutími. Příklad takové rozhodovací tabulky můžete vidět v tabulce níže, kde A, B, C, D představují jednotlivé otázky, a1 až a5 představují rozhodnutí a R1 až R7 rozhodovací pravidla. Účelem rozhodovací tabulky je odvození odpovědi na základě odpovědí na jednotlivé otázky.

Rozhodovací tabulky se využívají tam, kde je potřeba vyhodnocovat neměnným konzistentní počet podmínek.

Příklad rozhodovací tabulky

	R1	R2	R3	R4	R5	R6	R7
A	1	1	–	1	0	0	0
B	1	0	0	0	1	0	0
C	–	1	1	0	–	1	0
D	–	1	0	–	–	1	–
	a1	a2	a5	a3	a2	a1	a4

Vlastnosti rozhodovacích tabulek

Jak již bylo řečeno, rozhodovacími tabulkami lze odvozovat odpovědi na dané otázky. Může se však stát, že se pravidla v rozhodovací tabulce navzájem překrývají. Překrytí pravidel. nastává, když předpoklady více pravidel splňuje více rozhodnutí. Překrytí pravidel navíc může být buď redundantní, kdy výsledná rozhodnutí těchto pravidel jsou stejná, nebo sporné, kdy bývají výsledná rozhodnutí různá. Pro zjištění překrytí pravidel v tabulce je potřeba porovnat všechny dvojice pravidel a zjistit, zda se v některé otázce předpoklady pravidel výrazně liší (např. když je u jednoho z překrývajících se pravidel 0 a u druhého 1). To pak znamená, že taková dvojice pravidel je protichůdná, nelze je splnit žádným pravdivostním ohodnocením, v tabulce je sporné překrytí pravidel a rozhodovací tabulka tak není konzistentní.

Další vlastností rozhodovací tabulky je její úplnost. Tabulka je úplná, pokud dokáže určit rozhodnutí v každém případě, tj. pokud v každém pravdivostním ohodnocení splňuje předpoklad některého z pravidel. Pokud máme tabulku bez překrytí pravidel, lze její úplnost posoudit velice snadno rozborem počtu pravdivostních ohodnocení určených jednotlivými pravidly. (Rozhodovací pravidla v příkladu níže znázorňují pravidla úplné tabulky.)

R1: A^ B => a1

R2: A ^¬B ^ C ^ D => a2

R3: ¬B ^ C ^¬D => a5

R4: A^¬B^¬C => a3

R5: ¬A^ B => a2

R6: ¬A^¬B^ C^ D => a1

R7: ¬A ^¬B ^¬C => a4

Následně lze v rozhodovací tabulce vyčíst frekvenci výskytu jednotlivých rozhodovacích pravidel. Toto lze vyjádřit tak, že ke každé kombinaci odpovědí na jednotlivé otázky přiřadíme hodnotu pravděpodobnosti. Pokud se jedná o úplnou tabulku, musí být součet věech pravděpodobností roven 1. Pokud se jedná o neuplnou tabulku bez překrytí, lze předpokládat, že nepokryté kombinace nemohou nastat, mají proto pravděpodobnost 0, a součet všech pravděpodobností musí být i v tomto případě rovem 1.

Příklad tabulky s pravděpodobnostní distribucí

P	0.2	0.1	0.4	0.3	0
Q1	–	0	0	1	1
Q2	0	0	1	–	1
Q3	0	1	–	1	0
A	a1	a2	a2	a3

Příklad rozvinuté rozhodovací tabulky

P	0.1	0.1	0.1	0.2	0.2	0.15	0.15	0
Q1	0	1	0	0	0	1	1	1
Q2	0	0	0	1	1	0	1	1
Q3	0	0	1	0	1	1	1	0
A	a1	a1	a2	a2	a2	a3	a3

Rozhodovací stromy

Rozhodovací strom je obecně definován jako souvislý graf neobsahující cykly s orientovanými hranami, který se skláda z kořene, větví (hran), terminálních a neterminálních uzlů. Kořen je ten vrchol, do nějž nevstupují žádné větve a z nějž vstupuje do ostatních uzů vždy jedna větev. Každá větev, která z kořene vystupuje je označena příslušnou odpovědí na otázku, kterou označoval kořen. Větve s odpovědí vedou buď do neterminálního nebo terminálního uzlu. Pokud je uzel neterminální, je označen další otázkou a vedou z něj další větve. Pokud je uzel terminální, je to konečný bod rozhodovacího stromu a je mu tedy přiřazeno příslušné rozhodnutí.

Aby byl rozhodovací strom konzistentní s rozhodovací tabulkou, musí určovat rozhodovací funkci konzistentní s rozhodovací tabulkou. To platí, pokud kombinace odpovědí na dané otázky splňuje předpoklad rozhodovací tabulky. Tehdy určuje rozhodovací funkce stejné rozhodnutí, které určuje pravidlo v tabulce.

Cílem je sestavení co nejlepšího rozhodovacího stromu, který je konzistentní s příslušnou rozhodovací tabulkou. A zároveň, by k rozhodnutí měl vést co nejnižší počet otázek, měla by tedy být minimalizována maximální délka cesty z kořene do terminálních uzlů. Pokud se jedná o tabulku s pravděpodobnostní distribucí, jedná se o minimalizaci střední délky stromu. Z toho vyplývá, že za optimální rozhodovací strom je považován ten, jehož minimální střední délka je nejnižší mezi všemi ostatnímy stromy, které jsou také konzistentní s danou rozhodovací tabulkou.

Pokud máme strom konzistentní k rozhodovací tabulce s pravděpodobnostní distribucí, lze určit pravděpodobnost dosažení jednotlivých uzlů. A to tak, že se sečtou pravděpodobnosti těch pravidel, jejichž předpoklad je konzistentní s odpověďmi na cestě z kořene k příslušnému terminálnímu uzlu. Z této hodnoty je pak možné jednoduše určit střední délku rozhodovacího stromu, jelikož ta je váženým průměrem všech cest daného stromu k jednotlivým terminálním uzlům. Taktéž je možné z pravděpodobnstí dosažení terminálních uzlů určit entropii rozhodovacího stromu.

Odkazy

Použitá literatura

IVÁNEK, Jiří. Stručně o rozhodovacích tabulkách a konstrukci rozhodovacích stromů. Praha: Ústav informačních studií a knihovnictví FF UK v Praze, 2014.

JAHODA, Miroslav. Rozhodovací stromy. Praha, 2009. Diplomová práce. Univerzita Karlova. Vedoucí práce Doc. RNDr. Iveta Mrázová, CSc

TREJBAL, Pavel. Jak na rozhodovací stromy. Optimics [online]. Praha: Optimics s.r.o, 3. 11. 2014 [cit. 2018-05-30]. Dostupné z: https://www.optimics.cz/jak-na-rozhodovaci-stromy/

Doporučená literatura

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

GUPTA, Prashant. Decision Trees in Machine Learning. Towards data science [online]. 2017 [cit. 2018-05-30]. Dostupné z: https://towardsdatascience.com/decision-trees-in-machine-learning-641b9c4e8052

IVÁNEK, Jiří. Stručně o rozhodovacích tabulkách a konstrukci rozhodovacích stromů. Praha: Ústav informačních studií a knihovnictví FF UK v Praze, 2014.

SKLENÁK, Vilém. Data, informace, znalosti a Internet. Praha: C.H. Beck, 2001. C.H. Beck pro praxi. ISBN 80-717-9409-0.

SOWA, John F. Knowledge representation: logical, philosophical, and computational foundations. Pacific Grove: Brooks/Cole, c2000. ISBN 978-0534949655.

TREJBAL, Pavel. Jak na rozhodovací stromy. Optimics [online]. Praha: Optimics s.r.o, 3. 11. 2014 [cit. 2018-05-30]. Dostupné z: https://www.optimics.cz/jak-na-rozhodovaci-stromy/

Klíčová slova

rozhodovací strom, rozhodovací tabulka, datamining, dobývání znalostí, rozhodování

Související články

Metody dobývání znalostí z databází (data mining)