40563

Деревья решений. Принятие решений

Лабораторная работа

Информатика, кибернетика и программирование

Экспертные системы – класс близкий к системам поддержки принятия решений которые представляют собой компьютерные автоматизированные системы целью которых является помощь людям принимающим решение в каких-либо определенных условиях для полного и объективного анализа предметной деятельности. Теория принятия решений – область исследования включающая в себя понятия и методы математики статистики экономики менеджмента и психологии которая изучает закономерности выбора людьми путей решения разного рода задач а также исследует способы...

Русский

2015-04-22

500 KB

465 чел.

Деревья решений

Прежде чем переходить непосредственно к теории по деревьям решений и методу анализа иерархий, необходимо ввести базовые понятия и определения по экспертным системам.

Экспертные системы – класс, близкий к системам поддержки принятия решений, которые представляют собой компьютерные автоматизированные системы, целью которых является помощь людям, принимающим решение в каких-либо определенных условиях для полного и объективного анализа предметной деятельности.

Теория принятия решений – область исследования, включающая в себя понятия и методы математики, статистики, экономики, менеджмента и психологии, которая изучает закономерности выбора людьми путей решения разного рода задач, а также исследует способы поиска наиболее выгодных из возможных решений.

Принятие решения – это процесс рационального или иррационального выбора альтернатив, имеющий целью достижение осознаваемого результата. [1]

Наиболее популярные методы анализа данных и принятия решения – это деревья решений и метод анализа иерархий, которые будут рассмотрены далее.

1. Определения

Когда нужно принять несколько решений в условиях неопределенности, когда каждое решение зависит от исхода предыдущего решения или исходов испытаний, то применяют схему, называемую деревом решений.

Дерево решений – это графическое изображение процесса принятия решений, в котором отражены альтернативные решения, альтернативные состояния среды, соответствующие вероятности и выигрыши для любых комбинаций альтернатив и состояний среды.

Другое определение: деревья решений - это способ представления правил в иерархической, последовательной структуре, где каждому объекту соответствует единственный узел, дающий решение.

Деревья решений разбивают данные на группы на основе значений переменных, в результате чего возникает иерархия операторов "ЕСЛИ - ТО", которые классифицируют данные.

Под правилом понимается логическая конструкция вида «если - то».

Объект – некоторый пример, действие, шаблон, наблюдение.

Атрибут – признак, свойство.

Узел – внутренний узел дерева, узел проверки.

Лист – конечный узел дерева, узел решения.

2 Построение деревьев

Способ 1. Рисуют деревья слева направо. Места, где принимаются решения, обозначают квадратами, места появления исходов – кругами, возможные решения – пунктирными линиями, возможные исходы – сплошными линиями.

Для каждой альтернативы мы считаем ожидаемую стоимостную оценку (EMV) – максимальную из сумм оценок выигрышей, умноженных на вероятность реализации выигрышей, для всех возможных вариантов (см. пример 1).

Пример 1.

Компания рассматривает вопрос о строительстве завода. Возможны три варианта действий:

а). Построить большой завод стоимостью Ст1 = 500 тысяч у.е. При этом варианте возможны большой спрос (годовой доход в размере Д1 = 200 тысяч у.е. в течение следующих 5 лет) с вероятностью p1 = 0,7 и низкий спрос (ежегодные убытки Д2 = 90 тысяч у.е.) с вероятностью р2 = 0,3.

б). Построить маленький завод стоимостью Ст2 = 300 тысяч у.е. При этом варианте возможны большой спрос (годовой доход в размере Д3 = 100 тысяч у.е. в течение следующих 5 лет) с вероятностью p3 = 0,7 и низкий спрос (ежегодные убытки Д4 = 40 тысяч у.е.) с вероятностью р4 = 0,3.

в). Отложить строительство завода на один год для сбора дополнительной информации, которая может быть позитивной или негативной с вероятностью p5 = 0,4 и p6 = 0,6 соответственно. В случае позитивной информации можно построить заводы по указанным выше расценкам, а вероятности большого и низкого спроса меняются на p7 = 0,8 и р8 = 0,2 соответственно. Доходы на последующие четыре года остаются прежними. В случае негативной информации компания заводы строить не будет.

Нарисовав дерево решений, определим наиболее эффективную последовательность действий, основываясь на ожидаемых доходах.

Решение.

Строим дерево решений.

Строим узел 1, из которого исходят три заявленные в условии варианты. Обозначаем эти ветви пунктиром, поскольку это – возможные решения.

На концах ветвей ставим узлы-исходы, заключаем их в круг и обозначаем буквами А, В и т.д. Рисуем из этих узлов-исходов ветви с возможными исходами при выборе того или иного варианта из условия. Под каждой ветвью подписываем вероятности соответствующих исходов. На концах каждой ветви, не закрытой новым узлом, выставляем доходы и убытки, умноженные (исходя из условия) на время (годы из условия). На ветвях (возможные решения) ставим стоимость строительства со знаком «-», так как это расходы компании. Убытки на концах «открытых» ветвей также пишем со знаком «-».

Рис.1 – Дерево решений для примера 1. Первый этап построения

Далее считаем ожидаемые стоимостные оценки узлов.

Ожидаемая стоимостная оценка узла А равна:

ЕМV(А) = 0,8 х 1000 + 0,2 х (-450) -500 = 210.

EMV( B) = 0,8 х 500 + 0,2 х (-200) - 300 = 60.

EMV( D) = 0,9 x 800 + 0,1 x (-360) - 500 = 184.

EMV(E) = 0,9 x 400 + 0,1 х (-160) - 300 = 44.

Для узлов принятия решения 2 (второй уровень, условно) выбираем максимальную оценку:

EMV(2) = max {EMV( D), EMV( E)} = max {184, 44} = 184 = EMV(D).

Поэтому в узле 2 отбрасываем возможное решение «маленький завод».

EMV(C) = 0,7 x 184 + 0,3 x 0 = 128,8.

Для узла принятия решения 1 – узла принятия окончательного решения, аналогично выбираем максимальную оценку на других узлах.

EMV(1) = max {ЕМV(A), EMV(B), EMV(C)} = max {210; 60; 128,8} = 210 = EMV(А).

Поэтому в узле 1 выбираем решение «большой завод». Исследование проводить не нужно. Строим большой завод. Ожидаемая стоимостная оценка этого наилучшего решения равна 210 тысяч у.е.

Ответ: наиболее подходящее решение – решение строить большой завод.

Рис.2 – Дерево решений со стоимостными оценками

В рассмотренном примере мы произвели отсечение ветвей в узле 2. И далее в задаче мы отсекаем те ветви и узлы, стоимостные оценки которых не приемлемы для принятия наиболее выгодного решения.

Способ 2. Применяется в случаях, если необходимо провести исследование по каким-либо атрибутам. Чаще всего, здесь фигурируют понятия таблиц, как в базах данных. Проще говоря, деревья решений разбивают данные на группы на основе значений переменных, в результате чего возникает иерархия операторов "ЕСЛИ - ТО", которые классифицируют данные.

И такие деревья решений называются деревьями классификаций.

Цель построения деревьев классификации заключается в предсказании (или объяснении) значений категориальной зависимой переменной, и поэтому используемые методы тесно связаны с более традиционными методами, например, кластерного анализа1. Широкая сфера применимости деревьев классификации делает их весьма привлекательным инструментом анализа данных.

Что же такое деревья классификации? Рассмотрим простой пример.

Пример 2. Необходимо придумать устройство, которое отсортирует коллекцию монет по их достоинству (например, 1, 2, 3 и 5 копеек). Предположим, что какое-то из измерений монет, например - диаметр, известен и, поэтому, может быть использован для построения иерархического устройства сортировки монет. Заставим монеты катиться по узкому желобу, в котором прорезана щель размером с однокопеечную монету. Если монета провалилась в щель, то это 1 копейка; в противном случае она продолжает катиться дальше по желобу и натыкается на щель для двухкопеечной монеты; если она туда провалится, то это 2 копейки, если нет (значит это 3 или 5 копеек) - покатится дальше, и так далее. Таким образом, мы построили дерево классификации. Решающее правило, реализованное в этом дереве классификации, позволяет эффективно рассортировать горсть монет, а в общем случае применимо к широкому спектру задач классификации. [2]

Деревья классификации идеально приспособлены для графического представления, и поэтому сделанные на их основе выводы гораздо легче интерпретировать, чем если бы они были представлены только в числовой форме.

В печатных изданиях приводится ряд примеров применения деревьев классификации. Один из них посвящен диагностике больных, поступающих в стационар с сердечным приступом. В приемном отделении у них измеряют несколько десятков показателей (частоту пульса, кровяное давление и т.д.). Одновременно в базу данных заносится много другой информации о больном (возраст, перенесенные болезни и др.). Из последующей истории пациента можно, в частности, выделить такой показатель: прожил ли он 30 дней (или более) после приступа. Для разработки методов лечения больных с сердечной недостаточностью было бы весьма полезно научиться по данным первичного обследования выявлять пациентов с высокой степенью риска (тех, кто, вероятнее всего, не сможет прожить больше 30 дней, например). Одно из деревьев классификации, построенных авторами для этой задачи, представляло собой бинарное дерево классификации, и его можно описать следующей фразой: "Если нижнее давление у пациента в течение первых суток не опускается ниже 91, то, если его возраст превосходит 62.5 года, то, если у него наблюдается синусоидальная тахикардия, то в этом и только в этом случае следует ожидать, что пациент не сможет прожить 30 дней." Из этого предложения несложно представить себе соответствующее "дерево" решений. Как видим, в таком дереве вопросы задаются последовательно (иерархически), и окончательное решение зависит от ответов на все предыдущие вопросы. Иерархическое строение дерева классификации - одно из наиболее важных его свойств.

Пример 3.

Исследовать аудиторию пользователей ролевой образовательной онлайн игры на предмет выявления их потребности в вопросах для подготовки к ЭКЗАМЕН, а также провести исследование аудитории по возрасту, чтобы скорректировать игру под наиболее «активный» возраст участников.

Игра предназначена для всех учащихся и студентов (с 7го класса школы).

Решение.

Основные атрибуты, по которым проводится исследование: возраст (один из главных атрибутов), вид учебного заведения (важный атрибут, поскольку студенты ВУЗов уже не нуждаются в подготовке к ЭКЗАМЕН), предстоящий Экзамен.

На рисунке 3 представлено дерево классификаций для рассматриваемой задачи.

Это четырехуровневое дерево.

Уровень 1: проводим классификацию по возрасту. Из всех пользователей, зарегистрированных в игре, основная масса (73%) – пользователи до 18 лет. Лишь 27% пользователей старше 18 лет.

Уровень 2: исследуем каждую ветвь первого уровня. Разбиваем аудиторию пользователей старше 18 лет на 2 группы – до 22х лет после. Получаем лист А, который вместе со своей ветвью будет отсечен, поскольку процент людей старше 22х лет и играющих в игру очень маленький и разработчикам нет смысла ориентироваться на эту аудиторию.

Вторая ветвь переводит исследование на уровень 3, параллельный второму, который позволяет классифицировать аудиторию по учебному заведению (учащиеся ВУЗов, ССУЗов или школ). Согласно данным игры, только 10% пользователей в возрасте от 18 до 22 лет  - учащиеся ССУЗов, которые играют в игру. Остальные – учащиеся ВУЗов. Поэтому необходимо провести исследование на предмет принадлежности к курсу обучения в ВУЗе, поскольку уровни игры предполагают использование студентами младших курсов в частности. Как видно, 60%, что больше половины, учатся на 1-2 курсе (уровень 4). Значит, аудитория студентов 1-2 курсов обучения может быть довольно активной в игре. Отсюда следует, что мы не отсекаем ветви В и D. Ветвь С отсекаем, поскольку игра на вряд ли будет интересна студентам старших курсов, суд по статистике.

Рис. 3 – Дерево классификаций для примера 3

Исследуя аудиторию младше 18 лет, делим её на три ветви: учащиеся школы, ССУЗов и ВУЗов. Как видно из рисунка 3, аудитория учащихся ВУЗов составляет 7% от общего числа играющих в игру младше 18 лет. Но им не предстоит ЭКЗАМЕН. Лист Е не отсекаем, потому что это – аудитория студентов 1-2 курса, которая довольно активна, как мы выяснили на предыдущем шаге.

Остальные группы учащихся потенциально нуждаются в подготовке к ЭКЗАМЕН, поскольку выпускникам школы и ССУЗов для поступления в ВУЗ или ССУЗ необходимо пройти этот экзамен (уровень 3).

Как видно из схемы, мы получили четырехуровневое дерево решений, в котором исследование может проводиться на разных уровнях параллельно. Визуально уровни представлены на рисунке 4.

Рис. 4 – Уровни

Отсечение ветвей подробно представлено на рисунке 5.

Как правило, ветви отсекаются в том случае, когда найденное решение (лист, итог) не имеет значения и далее рассматривать задачу от этой ветви не имеет смысла.

Итак, по итогам составления дерева классификаций делаем вывод: рентабельно и наиболее выгодно игру продвигать среди школьников и студентов 1-2 курсов, но основной упор делать на школьников и на составление тестовых заданий в игре для подготовки к ЭКЗАМЕН.

Рис. 5 – Отсечение ветвей

3 Области применения деревьев

Деревья решений и деревья классификации широко используются в таких прикладных областях, как медицина (диагностика), программирование (анализ структуры данных), ботаника (классификация) и психология (теория принятия решений).

В основном, методы деревьев решений используют в экономической и банковской сферах. Например, для оценки кредитоспособности лиц или для выбора наиболее выгодной стратегии развития предприятия или сделки.

В сфере промышленности деревья решений применяются для определения качества продукции и для его контроля, выявления дефектов, в медицине – для диагностики заболеваний у пациентов, в биологии – для анализа строения аминокислот.

1 Термин кластерный анализ в действительности включает в себя набор различных алгоритмов классификации. Общий вопрос, задаваемый исследователями во многих областях, состоит в том, как организовать наблюдаемые данные в наглядные структуры. Например, биологи ставят цель разбить животных на различные виды, чтобы содержательно описать различия между ними. В соответствии с современной системой, принятой в биологии, человек принадлежит к приматам, млекопитающим, позвоночным и животным. В этой классификации, чем выше уровень агрегации, тем меньше сходства между членами в соответствующем классе. Т.е. человек имеет больше сходства с другими приматами (т.е. с обезьянами), чем с "отдаленными" членами семейства млекопитающих (например, собаками) и т.д.


 

А также другие работы, которые могут Вас заинтересовать

35197. Теория потребительского поведения. Равновесие потребителя в условиях бюджетных ограничений 163.5 KB
  Кривые безразличия. Кривые безразличия Кривая безразличия потребителя – кривая построенная в координатах количество товара А – количество товара Б точки которой отражают сочетание товаров выбираемое потребителем. Кривая отражает возможный набор вариантов комбинаций этих товаров благ обладающих одинаковой полезностью для потребителя вследствие чего ему безразлично какой выбрать набор из двух товаров находящихся в количественном сочетании соответствующем положению точек на кривой безразличия. Общественная кривая безразличия...
35198. ПРОГРАМНА СИСТЕМА ДЛЯ АВТОМАТИЗАЦІЇ БРОКЕРСЬКОГО ОБСЛУГОВУВАННЯ НА ВАЛЮТНІЙ БІРЖІ. КЛІЄНТСЬКА ЧАСТИНА 1.55 MB
  JSF JavaServer Faces – це каркас програмування технологія для вебзастосунків що написані на Java. AJAX Asynchronous JavaScript And XML – підхід до побудови користувацьких інтерфейсів вебзастосувань за яких вебсторінка не перезавантажуючись у фоновому режимі відправляє запити на сервер і сама звідти довантажує потрібні користувачу дані. – Інструменти для створення персональних вебсторінок – скриптова мова програмування загального призначення інтенсивно застосовується для розробки вебдодатків. PHP PHP – Інструменти для...
35199. Исторические и этимологические словари 48.71 KB
  Теорією і практикою укладання словників займається термінологічна лексикографія. Розроблення загальної класифікації документів є одним із провідних напрямків документознавства класифікація термінологічних словників розглядається в колі проблематики термінографії. Метою дослідження є встановлення видових і типологічних особливостей термінологічних словників розроблення класифікаційної схеми. Це створить передумови для розроблення методології та конкретних способів укладання спеціальних словників вироблення науково обґрунтованих принципів...
35200. Разработка стандарта организации «Планирование, разработка и подготовка производства литых деталей» системы менеджмента качества ООО «Литформ» в соответствии с требованиями стандарта ИСО 9001:2008» 738.95 KB
  На предприятии периодически производится обновление производственных участков. В 2007 году реконструирован стержневой участок. В настоящее время проводится реконструкция основного производства – монтаж конвейеров отработанной формовочной смеси и формовочных машин. При этом часть производственных площадей остается незадействованной.
35201. ВОЗРАСТНАЯ ПСИХОЛОГИЯ КАК ОТРАСЛЬ СОВРЕМЕННОЙ ПСИХОЛОГИЧЕСКОЙ НАУКИ 326 KB
  Предмет структура и актуальные задачи возрастной психологии Возрастная психология изучает возрастную динамику развития психики онтогенез психических процессов и психологических качеств личности качественно изменяющегося во времени человека. Возрастная психология будучи фундаментальной теоретической дисциплиной дает представление об уровне психического и личностного развития человека соотнося его со статистическими возрастными нормами развития; анализирует влияние разнообразных факторов на развитие психики и личности; прогнозирует ход...
35202. Возрастная психология 377 KB
  Новорожденность Ребенок рождается и своим первым криком оповещает этот мир о своем появлении. Рождаясь ребенок физически отделяется от матери. Поскольку ребенок полностью сосредоточен на сосании эта реакция была названа “пищевым сосредоточениемâ€. В дальнейшем когда ребенок научится схватывать предметы он уже будет лишен такой цепкости рук.
35203. ТЕОРИЯ ЯЭУ АЭС. ЦИКЛЫ 548 KB
  Влияние на КПД цикла Ренкина на перегретом паре: давления свежего пара. Сухость пара на выходе из турбины; Для цикла 2 у которого давление свежего пара выше значение Тср также выше следовательно и КПД выше ηtR=1T2 Tcp . Повышение давления свежего пара повышает КПД но увеличивается влажность пара на последней ступени турбины. температуры свежего пара.
35204. Що таке філософія 146.5 KB
  Світоглядце система поглядів людини на світ і місце в ньому людини. Ставлення людини до світуце безпосередній предмет ф. виконує такі функції: пізнавальна вона означає практичне і пізнавальне ставлення людини до світу і до самої себе як предмет філософського пізнання; світоглядна; методологічна. культурновиховна вона полягає в тому що сприяє культурному розвитку людини.
35205. Методические рекомендации по написанию рефератов по дисциплине «Концепции современного естествознания» 26.5 KB
  В результате выполнения реферативной работы студенты приобретают навыки самостоятельной работы с литературными источниками анализа научных текстов а также навыки подбора литературы по данной теме. В ходе написании реферата недопустимо использование готовых работ или их фрагментов а также написание работы с использованием только одного литературного источника. Тема для написания реферативной работы выбирается студентом из числа тем предложенных преподавателем. Допускается сдача рукописной работы однако в этом случае желательно чтобы она...