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

Nahoře 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, do nˇejˇz nevstupuj´ı ˇz´adn´e hrany, do

ostatn´ıch uzl˚u vstupuje pr´avˇe jedna hrana, • termin´aln´ı uzly (listy stromu) jsou ty vrcholy, z nichˇz ˇz´adn´a 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´ı.