Дерево решений: что это и где его используют🌲🧐

Не можете принять решение или просчитать риски в бизнесе? Invme расскажет, как это сделать. Читайте нашу статью о дереве решений и узнайте, как его создать и как с ним работать.

Что такое дерево решений

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

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

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

Дерево решений обычно состоит из трёх типов узлов:

- Узлы решения — обычно представлены квадратами

- Вероятностные узлы — представляются в виде круга

- Замыкающие узлы — представляются в виде треугольника

Кто придумал дерево решений

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

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

Почему такое название

Метод получил такое название из-за своей структуры, включающей в себя элементы двух типов — узлов (node) и листьев (leaf). Лист определяет решение для каждого попавшего в него примера, в нем содержится не правило, а подмножество объектов, удовлетворяющих всем правилам ветви, которая заканчивается этим листом. К каждому листу есть только один путь, поэтому пример или утверждение могут попасть только в один лист, что обеспечивает единственность решения.

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

Где используют дерево решений

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

- банковское дело – оценка кредитоспособности клиентов банка при выдаче кредитов;

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

- медицина – диагностика различных заболеваний;

- маркетинг – предсказание выбора покупателя, сегментация клиентской базы;

- молекулярная биология – анализ строения аминокислот и другие области.

Как создать дерево решений

Начните с основной цели — корня дерева (его обычно располагают наверху)

Главная цель или решение, которое вы пытаетесь принять, должны быть определены в самом начале вашего дерева решений. Это "корень" всей диаграммы.

Нарисуйте стрелки

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

Прикрепите узлы листьев на концах ваших ветвей.

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

Определите шансы на успех каждой точки принятия решения

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

Оцените соотношение риска и вознаграждения

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

Дерево решений: пример

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

Итак, главный вопрос разветвляется на две части: Доходы и Расходы. Доходы нужно повышать, расходы понижать. Как это сделать? От доходов идут разветвления: случайный выигрыш и работа. Выигрыш может быть легальным и нелегальным. Это может быть, скажем, выигрыш в лотерею или наследство.

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

Расходы разветвляются на стоимость и количество покупок, но все их можно отнести к одному классу. Стоимость можно понижать за счет, например, распродаж. А количество покупок понижать в каждой из сфер: еда, одежда, развлечения, путешествия, другое.

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

Обыкновенное дерево состоит из корня, ветвей, узлов (мест разветвления), листьев. Точно также дерево решений состоит из узлов (называемых также вершинами), обозначаемых окружностями; ветвей, обозначаемых отрезками, соединяющими узлы. Для удобства дерево решений изображают обычно слева направо или сверху вниз. Самая первая (левая или верхняя) вершина называется корнем. Цепочка "корень - ветвь - вершина - ... - вершина" заканчивается вершиной, которую называют "листом". Из каждой внутренней вершины (т.е. не листа) может выходить две или более ветвей. Каждому такому узлу сопоставлена некоторая характеристика, а ветвям - области значения этой характеристики, причем эти области дают разбиение множества значений данной характеристики.

Почему сложно построить идеальное дерево решений

В структуре дерева решений выделяют следующие компоненты:

Root Node, или корневой узел — тот, с которого начинается дерево, в нашем примере в качестве корня рассматривается фактор «температура».

Internal Node, или внутренний узел — узлы с одним входящим и двумя или более исходящими соединениями.

Leaf Node, или листовой узел — это заключительный элемент без исходящих соединений.

Когда создается дерево решений, мы начинаем от корневого узла, проверяем условия тестирования и присваиваем элемент управления одному из исходящих соединений. Затем снова тестируем условия и назначаем следующий узел. Чтобы считать дерево законченным, нужно все условия привести к листовому узлу (Leaf Node). Листовой узел будет содержать все метки класса, которые влияют на «за» и «против» в принятии решения.

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

Как использовать жадный алгоритм для построения дерева решений

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

Упрощенно алгоритм можно объяснить так:

На каждом узле выбирайте оптимальный способ проверки.

После разбейте узел на все возможные результаты (внутренние узлы).

Повторите шаги, пока все условия не приведут к конечным узлам.

Главный вопрос: «Как выбрать начальные условия для проверки?». Ответ заключается в значениях энтропии и прироста информации (информационном усилении). Рассказываем, что это и как они влияют на создание нашего дерева:

Энтропия — в дереве решений это означает однородность. Если данные полностью однородны, она равна 0; в противном случае, если данные разделены (50-50%), энтропия равна 1. Проще этот термин можно объяснить так — это то, как много информации, значимой для принятия решения, мы не знаем.

Прирост информации — величина обратная энтропии, чем выше прирост информации, тем меньше энтропия, меньше неучтенных данных и лучше решение.

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

Смотрите на примере. У нас есть большое количество таких данных:

Номер Возраст (Age) Уровень дохода (Income) Студент (Student) Кредитный рейтинг (CR) Покупка компьютера (Buys Computer)

1 <30 низкий (Low) да средний (Fair) да

2 30-40 высокий (High) нет прекрасный (Excellent) да

3 40 высокий (High) нет прекрасный (Excellent) нет

4 <30 средний (Medium) нет средний (Fair) нет

Здесь может быть n деревьев решений, которые формируются из этого набора атрибутов.

Дерево №1: здесь мы принимаем атрибут «Студент» в качестве начального условия теста

Дерево №2: здесь используем в качестве начального условия атрибут «Доход»

Ищем оптимальное решение с жадным алгоритмом

Первый шаг: создать два условных класса:

«Да», человек может купить компьютер.

«Нет», возможность отсутствует.

Второй шаг — вычислить значение вероятности для каждого из них.

Для результата «Да», «buys_computer=yes», формула выглядит так:

Для результата «Нет», «buys_computer=no», вот так:

Третий шаг: вычисляем значение энтропии, поместив значения вероятности в формулу.

Это довольно высокий показатель энтропии.

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

Здесь нужно пояснение. Например, что будет означать показатель прироста информации, если за основу взять атрибут «Возраст»? Эти данные показывают, сколько людей, попадающих в определенную возрастную группу, покупают и не покупают продукт.

Допустим, среди людей в возрасте 30 лет и младше покупают (Да) два человека, не покупают (Нет) три человека. Info(D) рассчитывается для последних трех категорий людей — соответственно, Info(D) будем считать по сумме этих трех диапазонов значений возраста.

В итоге разница между общей энтропией Info(D) и энтропией для возраста Info(D) age (пусть она равна 0,694) будет нужным значением прироста информации. Вот формула:

Сравним показатели прироста информации для всех атрибутов:

Возраст = 0,246.

Доход = 0.029.

Студент = 0,151.

Кредитный рейтинг = 0,048.

Получается, что прирост информации для атрибута возраста является самым значимым — значит, стоит использовать его. Аналогично мы сравниваем прирост в информации при каждом разделении, чтобы выяснить, брать этот атрибут или нет.

Таким образом, оптимальное дерево выглядит так:

Правила классификации для этого дерева можно записать следующим образом:

Если возраст человека меньше 30 лет и он не студент, то не будет покупать компьютер.

Если возраст человека меньше 30 лет, и он студент, то купит компьютер.

Если возраст человека составляет от 31 до 40 лет, он, скорее всего, купит компьютер.

Если человек старше 40 лет и имеет отличный кредитный рейтинг, то не будет покупать компьютер.

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

Вот мы и достигли оптимального дерева решений. Готово.

Лайфхаки для работы с деревом решений

Будьте проще

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

Используйте конкретные данные для прогнозирования результатов

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

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

Плюсы и минусы дерева решений

Плюсы:

- Формирует четкие и понятные правила классификации. То есть деревья решений хорошо и быстро интерпретируются

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

- Они легко визуализируются, то есть могут «интерпретироваться» не только как модель в целом, но и как прогноз для отдельного тестового субъекта (путь в дереве)

- Быстро обучаются и прогнозируют

- Не требуется много параметров модели

- Поддерживают как числовые, так и категориальные признаки

- Быстро приводят к результату и решению проблемы

Минусы:

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

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

- Возможно переобучение дерева решений, из-за чего приходится прибегать к методу «отсечения ветвей», установке минимального числа элементов в листьях дерева или максимальной глубины дерева (то есть ограниченность модели)

- Сложный поиск оптимального дерева решений

- Нет 100-процентной гарантии нахождения оптимального дерева

Читайте и другие статьи из раздела Лайфхаки на invme:

- Как создать интеллект-карту

- Лучший способ принять решение

- Как создать карту желаний