Алгоритъм за избор на решение по метода "Дърво на решенията"

Алгоритъм за построяване на дърво на решенията

Метод

Метод за построяване на “дърво на решенията”. Допълва ситуационния анализ, като в провеждания анализ се включват и възможните изходни и съответни решения. Така се получава верига от възможни ситуации и решения със съответен изход /ефект, печалба, полза и т.н. При разработването на дърво на решенията трябва да се имат предвид три основни ситуации: - решения в условията на определеност; - решения в условия на неопределеност; - решения в условията на конфликт. Първата ситуация е обикновено рядко срещана. Втората ситуация е най-често срещана, тъй като в икономиката не съществуват безрискови ситуации и операции. В условията на неопределеност е невъзможно да се определи точна количествена оценка на вероятните изходи. В условията на конфликт вземането на решение се усложнява от отчитането на осъзнатото и актив ното противодействие на участниците в “конфлик тната” ситуация. Съществуват ефективни алгоритми за построяване на дървета на решенията от наблюдаваните данни. Построеното в резултат от работа на даден алгоритъм дърво се използва директно за решаване на класификационни задачи.

Алгоритъм ID3

Итеративен алгоритъм. Избира по случаен начин подмножество от обучаващите примери (наречено прозорец) и построява по него дърво на решенията, което класифицира правилно всеки пример от прозореца. Ако има неразгледани примери, които се класифицират неправилно, те се прибавят към прозореца и дървото се построява отново. Експериментите са показали, че такъв итеративен метод е по-ефективен от опита да се построи дървото направо от всички данни. Евристиката, използвана от ID3 за избор по кой атрибут да се разклонява дървото, е да се избере проверката, от която ще се спечели най-много информация. Тази евристика почива на аналогии с математическата теория на информацията (Клод Шенън) и се определя като търсене на минимална информационна ентропия, тъй като да се увеличи спечелената информация означава да се намали неопределеността или безпорядъка. ID3 е бил прилаган успещно към големи обучаващи множества, както и (адаптиран) към зашумени и непълни данни. Неговата простота и ефективност го правят добра алтернатива на методите за придобиване на знания, ако разполагаме с достатъчно количество подходящи данни. За разлика от метода на пространството на версиите той не е инкрементален - прибавянето на нови примери води до построяване на нова класификация с участие и на по-рано разгледаните примери. Не е гарантирано намиране на най-просто дърво на решенията, тъй като използуването на оценяваща функция от теорията на информацията всъщност е евристика. Практическите приложения са показали сравн. прости дървета на решенията и добра класификация на нови обекти. В последните години са разработени и инкрементални алгоритми за самообучение, работещи върху класификационни дървета (дървета на решенията).

Вижте още

Източници

Introduction to Data Mining and its Applications, S. Sumathi, S. N. Sivanandam, In series: "Studies in Computational Intelligence" No. 29, Springer-Verlag Berlin Heidelberg 2006
A Guide to the Project Management Body of Knowledge, Project Management Institute, North Carolina, 1996.
Chapman, Ch., St. Ward, Project Risk Management – Processes, Techniques and Insights, John Wiley & Sons, 1997.
Godeth, Michael, Scenarios and Strategic Management, Butterworth Scientific, London, 1987.
Pollack-Johnson, Bruce, Matthew J. Liberatore, Project Planning Under Uncertainty Using Scenario Analysis, Project Management Journal, March 2005.
Saaty T., K. Kearns, Analytical Planning. The Organization of Systems, Pergamon Press, 1985).
Schnaars, Steven, Paschalina Ziamou, The Essentials of Scenario Writing, Business Horizons, July-August 2001.
Smith, Pr., Managing Risk as Product Development Schedule Shrink, Research-Technology Management Sep/Oct, 1999.
Top Eleven Ways to Manage Technical Risk, Department of the Navy, USA, 1998
Vertzberger, Yaacov., Y., Making and Taking Risky Decisions, Nordic Journal of International Studies, v. 33, 1998.
Manning, Ñ., P. Raghavan, H. Schultze. Introduction to Information Retrieval, Web Information Systems and Technologies. Springer Berlin Heidelberg, 2009.
Chen, L. and Ê. Sycara WebMate: A Personal Agent for Browsing and Searching, 1998, Carnegie Mellon University.
Claire Cardie, Nicholas Nowe. Improving Minority Class Prediction Using Case Specific Feature Weights. Proceedings of the Fourteenth International Conference on Machine Learning, July 08-12, 1997
Daniel Jurafsky and James H. Martin. Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition, Prentice Hall series in artificial intelligence, 2000.

Външни препратки