Файл: Эвристические методы принятия управленческих решений Методы принятия управленческих решений.pptx

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

---

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

Задают общее множество S, содержащее:

n примеров, для каждого из которых задана метка класса Ci(i = 1..k);

m атрибутов Aj(j = 1..m), которые определяют принадлежность объекта к тому или иному классу.

Тогда возможно три случая:

1)Примеры множества S имеют одинаковую метку Ci, следовательно, все обучающие примеры относятся к одному классу. В таком случае обучение не имеет смысла, потому что все примеры в модели будут одного класса, который и «научится» распознавать модель. Само дерево будет похоже на один большой лист, ассоциированный с классом Ci. Тогда его использование не будет иметь смысла, потому что все новые объекты будут относиться к одному классу.

2)Множество S — пустое множество без примеров. Для него сформируется лист, класс которого выберется из другого множества. Например, самый распространенный из родительского множества класс.

3)Множество S состоит из обучающих примеров всех классов Ck. В таком случае множество разбивается на подмножества в соответствии с классами. Для этого выбирают один из атрибутов Aj множества S, состоящий из двух и более уникальных значений: a1, a2, …, ap), где p — число уникальных значений признака. Множество S разбивают на p подмножеств (S1, S2, …, Sp), состоящих из примеров с соответствующим значением атрибута. Процесс разбиения продолжается, но уже со следующим атрибутом. Он будет повторяться, пока все примеры в результирующих подмножества не окажутся одного класса.

Алгоритмы обучения

Сегодня существует много алгоритмов обучения: ID3, CART, C4.5, C5.0, NewId, ITrule, CHAID, CN2 и другие. Самыми популярными считаются:

ID3 (Iterative Dichotomizer 3). Алгоритм позволяет работать только с дискретной целевой переменной. Деревья решений, построенные на основе ID3, получаются квалифицирующими. Число потомков в узле неограниченно. Алгоритм не работает с пропущенными данными.

C4.5. «Продвинутая» версия ID3, дополненная возможностью работы с пропущенными значениями атрибутов. В 2008 году издание Spring Science провело исследование и выявило, что C4.5 — самый популярный алгоритм Data Mining.

---

CART (Classification and Regression Tree). Алгоритм решает задачи классификации и регрессии, так как позволяет использовать дискретную и непрерывную целевые переменные. CART строит деревья, в каждом узле которых только два потомка.

Основные этапы построения дерева решений

Построение осуществляется в 4 этапа:

Выбрать атрибут для осуществления разбиения в данном узле.

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

Выбрать метод отсечения ветвей.

Оценить точность построенного дерева

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

Специалисты решили принудительно останавливать строительство дерева, чтобы оно не становилось «переобученным».

Подходы от перегруженного дерева

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

Ограничение глубины дерева. Алгоритм останавливается после достижения установленного числа разбиений в ветвях. Этот подход также негативно сказывается на точности дерева.

Задание минимально допустимого числа примеров в узле. Устанавливается ограничение на создание узлов с числом примером меньше заданного (например, 7). В таком случае не будут создаваться тривиальные разбиения и малозначимые правила.

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

Где применяется Дерево решений

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

---

Успешнее всего деревья применяют в следующих областях:

Банковское дело. Оценка кредитоспособности клиентов банка при выдаче кредитов.

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

Медицина. Диагностика заболеваний разной сложности.

Молекулярная биология. Анализ строения аминокислот.

Торговля. Классификация клиентов и товар.

---

Зарубежный опыт

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

Зарубежный опыт

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

Преимущества метода дерева решений

Формируют четкие и понятные правила классификации. Например, «если возраст < 40 и нет имущества для залога, то отказать в кредите». То есть деревья решений хорошо и быстро интерпретируются.

---