Original title: Finding Optimal Decision Trees
Authors: Máša, Petr ; Ivánek, Jiří (advisor) ; Berka, Petr (referee) ; Jiroušek, Radim (referee)
Document type: Doctoral theses
Year: 2006
Language: eng
Publisher: Vysoká škola ekonomická v Praze
Abstract: Rozhodovácí stromy jsou rozšířenou technikou pro popis dat. Používají se často teké pro predikace. Zajímavým problémemje, že konkrétní distribuce může být popsána jedním či více rozhodovacími stromy.Obvykle nás zajímá co nejjednodušší rozhodovací strom(který budeme nazývat též optimální rozhodovací strom).Tato práce navrhuje rozšíření prořezávácí fáze algoritmů pro rozhodovací stromytak, aby umožňovala více prořezávání. V práci byly zkoumány teoretické i praktické vlastnosti tohoto rozšířeného algoritmu. Jako hlavní teoretický výsledek bylo dokázano, že pro jistou třídu distribucí nalezne algoritmus optimální rozhodovací strom(tj.nejmenší rozhodovací strom, který reprezentuje danou distribuci). V praktických testech bylo zkoumáno, jak je schopen algoritmus rekonstruovat známý strom z dat. Zajímalo nás, zdali dosáhne naše rozšíření zlepšení v počtu správně rekonstruovaných stromů zejména v případě, že data jsou dodatečně velká ( z hlediska počtu záznamů). Tato doměnka byla potvrzena praktickými testy. Obdobný výsledek byl před několika lety prokázán pro Bayesovské sítě. Algoritmus navržený v této disertační práci je polynomiální v počtu listů stromu, který je výstupem hladového algoritmu pro růst stromů, což je vylepšení oproti jednoduchému algoritmu prohledávání všech možných stromů, který je exponenciální.
Keywords: algoritmus; nejmenší rozhodovací strom; optimalita; rozhodovací stromy; změna vnitřní struktury

Institution: University of Economics, Prague (web)
Document availability information: Available in the digital repository of the University of Economics, Prague.
Original record: http://www.vse.cz/vskp/eid/794

Permalink: http://www.nusl.cz/ntk/nusl-456


The record appears in these collections:
Universities and colleges > Public universities > University of Economics, Prague
Academic theses (ETDs) > Doctoral theses