Интеллектуальный информационные системы дерево решений

Дерево решений.

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

Для построения дерева решения следует определить:

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

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

множество вероятностей (вероятных оценок) появления объективных событий влияющих на исходы (результаты) альтернативных действий;

множество исходов (результатов, последствий) альтернативных действий в зависимости от того, какое из объективных событий осуществиться;

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

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

Все имеющиеся сведения представляются в виде дерева решений.

о

А о

о

альтернативы исходы и их исходы

Пусть вам нужно выбрать банк, в котором ваша фирма будет хранить свои денежные ресурсы. В одном банке вы будете держать деньги под 125% годовых, в другом – под 150%. Надежность хранения денег в первом банке оценивается в 0.9, а во втором – 0.7. В качестве характеристики полезности примем годовой прирост ваших денежных вкладов. Допустим, что вы можете вложить в банк 100 тыс. рублей. Тогда в первом случае с вероятностью 0.9 на вашем счете будет 125 тыс. руб., а во втором – 150 тыс. руб. Однако вероятность этого события значительно ниже.

Дерево решения принимает следующий вид.

0.9 — 125000

о

А 0.9 125000

о 0.7 150000

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

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

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

Какое дерево решений будет иметь место в рассматриваемом случае.

Девушка изучает последствия реализации следующих альтернатив:

А 1 – отказ от участия в нечестном пари без объяснения причин отказа;

А 2 – отказаться участвовать в пари и сказать почему, т.е. разоблачить ростовщика;

А 3 – принять участие в пари на предложенных условиях;

А 4 – принять участие в пари, но ответить своей хитростью на хитрость.

При выборе лучшей альтернативы следует предусмотреть возможность разоблачения ответной хитрости девушки. Далее. Чтобы построить дерево решений, надо оценить полезности возможных исходов. Примем, что полезности исходов выражаются так: и(С1)=и(С2)=и(С42)= — 100; и(С3)= — 50; и(С4)= — 100. Здесь С1, С2, С42 – отец в тюрьме, а девушка нищая, С3 – долг аннулируется и девушка становится женой ростовщика, С41-долг аннулируется и девушка остается свободной.

Обозначим вероятность разоблачения хитрости девушки через х, а вероятность ее неудачи (1-х).

Дерево решений принимает следующий вид.

А 1 — 100

А 2 — 100

А А 3 — 50

100

О

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

Данные примеры деревьев решений позволяют сделать следующий вывод.

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

Определение численных значений субъективных значений вроятностей и полезностей.

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

Рассмотрим некоторые способы определения численных значений субъективных значений вроятностей и полезностей.

Если дерево решения включает события, наступление которых не зависит от ЛПР, то ему желательно знать вероятности их появления. Можно, конечно, воспользоваться статистическими данными, если они имеются. Однако по ряду причин это не всегда удается. Как поступают в данном случае?

Наиболее распространенном методом вычисления искомых вероятностей является следующий.

Пусть О событие, вероятность которого требуется вычислить. Воспользуемся каким-либо датчиком случайных чисел и выберем игру в пари.

При вычислении полезностей исходов руководствуются следующими правилами.

Относительно двух исходов следует или признать их равноценными, или предпочесть один друглму.

Если один исход предпочитают другому, то его полезность должна быть больше полезности последнего.

Если имеются три таких исхода, что первый из них предпочитается второму, второй – третьему, то первый исход должен также предпочитаться третьему.

Если имеются три таких исхода, что первый из них предпочитается второму, второй – третьему, то существует некоторое значение вероятности x, такое что субъекту, принимающему решенте, безразлично, выбтрать второй исход тлт заключать пари на получение первого исхода с вероятностью (1-х).

Источник

Лаба_3_2

Далее используем таблицу deals для создания дерева решений.

Рисунок 4 – Процесс создания

Рисунок 5 – Результат работы Decision Tree для таблицы продуктов

Рисунок 6 – Описательный результат

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

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

Оставим в ней только нужные данные с помощью Select Attributes и отсортируем их

Рисунок 7 — Таблица со списком покупок

Рисунок 8 – Настройка процесса ID3

Рисунок 9 – Результат работы ID3

Из полученного графа можно сделать следующий вывод. Для города Naypyitaw. Для людей которые имеют членство в магазине ( карту магазина ), цена продуктовой корзины отличается во много раз в зависимости от типа оплаты. Например. Мужчина участник потратил 56 у.е в то время как другом мужчина обычный покупатель купил на 30 у.е за наличные. Для кредитной карты показатели очень похожее. Таким образом можно сделать вывод, что покупатели с членской картой тратят в магазине гораздо больше чем обычные покупатели.

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

1. Деревья решений – это способ представления правил в иерархической, последовательной структуре, где каждому объекту соответствует единственный узел, дающий решение
2. Задачи классификации(отнесения объектов к одному из заранее известных классов), задачи численного прогнозирования (предсказания значений целевой переменной) – решаются методом деревьев решений и хранение данных в сжатом виде
3. Существуют следующие алгоритмы для построения деревьев решений — разделения и захвата, обучением с учителем, CART, C4.5, NewId, ITrule, CHAID, CN2 и т.д.
4. Разбиение узлом может происходит по следующим критериям – теоретико-информационный и статический
5. Преимущества использования деревьев решений следующие – высокая точность прогноза, быстрый процесс обучения, генерация правил в областях, где эксперту трудно формализовать свои знания, извлечение правил на естественном языке, интуитивно понятная классификационная модель.

Источник

Интеллектуальный информационные системы дерево решений

должность, уч. степень, звание

ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ №5

Интеллектуальный анализ данных. Метод деревьев принятия решений.

по курсу: Интеллектуальные информационные системы

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

Интеллектуальный анализ данных. Метод деревьев принятия решений.

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

Рисунок 1 – Процесс встроенного примера

Рисунок 2 – Результат работы процесса

Выбран набор данных Iris. К данным применён метод дерева принятия решений, как показано на рисунках 3-6.

Рисунок 3 – Процесс метода дерева принятия решений

Рисунок 4 – Настройки блока DecisionTree

Рисунок 5 – Исходные данные Iris

Рисунок 6 – Дерево принятия решений

Дерево принятия решений – эффективный инструмент для обработки и анализа данных. Получены навыки построения дерева принятия решений в программном комплексе Rapid Miner Studio.

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

Задачи классификации, установления зависимости, численного прогнозирования.

Метод разделения и захвата (алгоритм Куинлена), CART, C4.5, NewId, ITrule, CHAID, CN2.

Теоретико-информационный критерий, Статистический критерий.

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

Источник