Konstrukce rozhodovacích stromů (princip snižování entropie)

Rozhodovací stromy

Nejčastěji se koncept rozhodovacích stromů používá v oblasti výpočetní techniky. Tato metoda spadá mezi metody dobývání znalostí, jejichž cílem je dojít informacím za pomoci předem získaných dat a nalézt v datech vzájemné závislosti. Rozhodovací stromy vizuálně znázorňují celý proces rozhodování a cestu ke správnému výsledku. Všechny možnosti, dotazy a odpovědi jsou vidět zároveň.

Struktura

Základem (počátek dotazu) je výchozí uzel, tzv. kořen stromu. Obsahuje první otázku. Podle získané odpovědi pokračujeme po odpovídající hraně do příslušného podstromu a tak dál, až dojdeme ke konečné odpovědi. Ta je zapsaná v tzv. listu, tedy uzlu, ze kterého nevedou další hrany (protože neklade další otázky). Počet úrovní stromu od kořene k nejzazšímu listu nazýváme výškou stromu.

• Kořen stromu, je uzel do nějž nevstupují žádné hrany, do

ostatních uzlů vstupuje právě jedna hrana.

• Terminální uzly (listy stromu) jsou ty vrcholy, z nichž žádná hrana

nevystupuje. • netermin´aln´ım uzl˚um jsou pˇriˇrazeny ot´azky Q1,...,Qn tak, ˇze na ˇz´adn´e cestˇe z koˇrene se nesm´ı ˇz´adn´a ot´azka opakovat • z kaˇzd´eho netermin´aln´ıho uzlu vych´azej´ı orientovan´e hrany (vˇetve) oznaˇcen´e jednotliv´ymi moˇzn´ymi odpovˇed’mi na pˇriˇrazenou ot´azku, • termin´aln´ım uzl˚um jsou pˇriˇrazena rozhodnut´ı.