Rozhodovací tabulky a stromy

(rozpracováno)

Příklad rozhodovacího stromu

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. 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.

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.

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.

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

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.