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

от Администрация и управление
Направо към: навигация, търсене

При разработването на Дърво на решенията се използва определен алгоритъм.

Същност

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

  • решения в условията на определеност;
  • решения в условия на неопределеност;
  • решения в условията на конфликт.

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

Алгоритъм ID3

Алгоритъм ID3 е познат още като итеративен алгоритъм. Избира по случаен начин подмножество от обучаващите примери (наречено прозорец) и построява по него дърво на решенията, което класифицира правилно всеки пример от прозореца. Ако има неразгледани примери, които се класифицират неправилно, те се прибавят към прозореца и дървото се построява отново.

Durvo na resheniqta6.jpg

Експериментите са показали, че такъв итеративен метод е по-ефективен от опита да се построи дървото направо от всички данни. Евристиката, използвана от 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.

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