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

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

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

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

Что такое дерево принятия решений? Это метод, показывающий все возможные варианты решения задачи.

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

Данный метод принятия решений назвали именно деревом решений по причине его сходства со стволом и ветвями, расположенными вверх ногами. Схема имеет:

• Корень. Именно с него начинается дерево. Его размещают вверху и пишут в нем вопрос.

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

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

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

Источник: shutterstock.com

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

• Корень дерева – это вопрос: «На какой доставке остановить выбор?».

• Ветви – возможные варианты: быстрая и более дорогая / медленная, но дешевая.

• Листья – выводы.

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

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

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

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

В сфере продаж скрипты строятся следующим образом: менеджер задает клиенту вопрос, на основании которого корректирует следующие вопросы.

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

Источник: shutterstock.com

Самая популярная и простая задача – бинарная классификация или разделение множества различных элементов на две группы. Например:

• вариант 1 – да (клиент успешно погасил кредит);

• вариант 0 – нет (клиент не оплатил задолженность по кредиту).

Еще один пример – прогноз погоды и предположение, будет ли завтра дождь, на основании метеорологических наблюдений за 100 дней. Ответа может быть два:

• вариант 1 – дождь завтра будет;

• вариант 0 – завтра не будет дождя.

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

Какие задачи решает дерево принятия решений

Дерево принятия решений используется также в машинном обучении, чтобы:

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

2. Определить условия, которые являются наиболее значимыми в конкретной ситуации. Алгоритм дерева принятия решений дает возможность оценить значимость признаков (англ. Feature Importance), найти именно те условия, которые в конкретном исследовании наиболее важны. Эти условия расположены ближе всего к месту разветвления основной выборки. Можно создать 100 деревьев принятия решений для решения одной задачи. И в основании этих деревьев будут лежать, скорее всего, одни и те же условия.

3. Увеличить точность результатов. Метод помогает выстроить выборку, которая максимально подходит под все условия, и на основании имеющихся данных сделать точный прогноз.

2 способа построения дерева принятия решений

Алгоритмы по выстраиванию деревьев на практике отличаются друг от друга по ряду признаков:

• Максимально допустимое количество потомков, то есть вариантов ответа в одном узле.

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

• Тип переменной, с которой вы ведете работу (дискретная или непрерывная). Если переменная имеет ответ на вопрос «Выдать кредит клиенту или нет?», то она будет дискретной, так как ответы выглядят, как «да» или «нет». А если переменная показывает стоимость квартиры, то она может иметь абсолютно разные значения, к примеру, от 2 до 10 млн. Такая переменная является непрерывной.

Дерево принятия решений можно сформировать как сверху вниз, так и снизу вверх.

Прямой метод

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

Однако такой метод не всегда может привести к верному решению. Возьмем для примера задачу по размену монет. Нам нужно собрать шесть центов из монет номиналом 1, 3 и 4 цента. На первом шаге алгоритм выберет 4, таким образом итоговая комбинация будет выглядеть: 4 + 1 + 1. А более оптимальным решением будет: 3 + 3.

Если строить деревья прямым способом, очень важно представить в обучающей выборке все классы данных. От этого будет напрямую зависеть точность полученных данных. К примеру, решая задачу про монеты, в обучающей выборке нужно представить все варианты: 1, 3, 4 цента. При построении деревьев они будут разбиваться на отдельные варианты монет – неповторяющиеся подмножества.

Источник: shutterstock.com

Очень удобно отражать разбивку по классам графическим способом. Например, при классификации ирисов разделить обучающее множество на классы по двум признакам – ширине чашелистиков и лепестков. На плоскости каждая точка обозначает один набор признаков и, соответственно, один вид цветов. То есть если рассмотреть n количество признаков, то и пространство получится n-мерным.

Примеры «жадных» алгоритмов, имеющих прямое построение: ID3, С4.5, CART.

Обратный метод

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

• Инвестиции составляют 250 млн, возможная прибыль – 150 млн, а вероятность финансовых потерь – 10 %.

• Инвестиции составляют 350 млн, возможная прибыль – 250 млн, а вероятность финансовых потерь – 5 %.

• Инвестиции – 550 млн, возможная прибыль – 350 млн, вероятность финансовых потерь – 20 %.

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

Получается:

• А) -250 * 0,1 + 150 * 0,9 = 110;

• В) -350 * 0,05 + 250 * 0,95 = 207,5;

• С) -550 * 0,2 + 350 * 0,8 = 170.

Самым выгодным является вариант В, равный 207,5. Значит, для инвестирования следует выбирать второй проект.

Другой пример. Из 100 дней дождь шел 50. Из них в 40 случаях на следующий день после дождя снова были осадки. Значит, если сегодня был дождь, завтра он тоже будет с вероятностью 80 %.

Подготовка данных для построения дерева принятия решений

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

Рассмотрим основные этапы по подготовке данных:

1. Работа с пропущенными значениями. Они либо заменяются медианой, средним или прогнозируемым значением, либо создается категория «пропущено».

2. Преобразование (кодирование) категориальных признаков – применение метода One-Hot Encoding для номинальных переменных и Label Encoding – для порядковых.

3. Достижение баланса между классами – использование техник Oversampling/Undersampling при существенном дисбалансе.

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

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

Источник: shutterstock.com

Немаловажно правильно делить данные на обучающую выборку и тестовую. Обычно соотношение выглядит следующим образом: 70-80 % – обучение, 20-30 % – тестирование. Также при достаточном объеме данных рекомендуют выделять валидационную выборку, чтобы подобрать гиперпараметры.

Базовый алгоритм ID3 формирования дерева принятия решений

В 1936 году Р. Куинланом был разработан алгоритм ID3 (Iterative Dichotomiser 3), послуживший основой современных методов выстраивания деревьев решений. Главная идея алгоритма заключается в следующем: производится последовательное деление данных по признаку, который дает самый большой информационный выигрыш.

Как выглядит процесс построения дерева по алгоритму Iterative Dichotomiser 3:

1. Производится расчет энтропии исходного множества данных S.

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

3. Выбирается признак, имеющий максимальный выигрыш.

4. С выбранным признаком создается узел.

5. К каждому подмножеству, которое было образовано при разбиении по выбранному признаку, рекурсивно применяются шаги от 1 до 4.

6. Рекурсия прекращается во время выполнения одного из условий остановки: все примеры подмножества относятся к одному классу, подмножество пустое, или отсутствуют доступные признаки.

Рассмотрим ключевые формулы, характерные для алгоритма ID3.

Энтропия множества S:

H(S) = -Σ(p_i * log2(p_i))

Информационный выигрыш для признака A:

Gain(S, A) = H(S) – Σ((|S_v| / |S|) * H(S_v))

где S_v – это подмножество S, для которого признак A имеет значение v.

Такой алгоритм имеет ряд ограничений. Например, может работать только с категориальными признаками, не работает с пропущенными значениями, склонен переобучаться. В поздних версиях алгоритмов (C4.5, CART) данные ограничения были устранены.

Продвинутые алгоритмы построения дерева принятия решений

C4.5 и CART – это улучшения основного алгоритма ID3, в которых отсутствуют прежние ограничения, появляются новые функции:

Алгоритм CART (Classification and Regression Trees)

Он разработан в 1984 году Л. Брайманом с соавторами. CART совершил прорыв, открыв универсальный подход для решения задач по классификации и регрессии. В чем заключаются отличия алгоритма CART от базового ID3?

• Вместо энтропии использует индекс Джини в качестве меры неоднородности.

• Для всех, в том числе числовых, типов признаков создает бинарные разбиения.

• Имеет механизмы постпрунинга, используемые для борьбы с переобучением.

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

В работе с числовыми признаками Classification and Regression Trees подбирает оптимальный порог разделения, который максимизирует снижение индекса Джини. А при работе с категориальными признаками используется бинарное разбиение, которое группирует имеющиеся категории самым оптимальным образом.

Алгоритм C4.5

Этот алгоритм был разработан в 1993 году Р. Куинланом как эволюционное развитие ID3. Он имеет следующие улучшения:

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

• Работает с пропущенными значениями.

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

• Для контроля сложности модели использует механизмы пре- и постпрунинга.

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

Оба эти алгоритма, CART и C4.5, стали основой для реализации современных деревьев принятия решений в популярных библиотеках машинного обучения, например, XGBoost, LightGBM и scikit-learn.

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

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

Пример 1. Нужно ли запускать новое приложение?

Предположим, вы предприниматель-новичок. Вы решили запустить новое мобильное приложение. Для его разработки вы готовы нанять программистов. Но, прежде чем это сделать, задаетесь вопросом: «Нужно ли вообще запускать новый продукт или нет?». Для принятия решения можно нарисовать дерево:

Первый шаг. Для начала определитесь с вопросом, от которого будут идти ветви. В данном случае он будет выглядеть так: «Нужно ли создавать приложение?».

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

Источник: shutterstock.com

Ветка № 1: «Высок ли спрос на рынке?». Если ответ «да», скорее всего, продукт будет пользоваться успехом, в противном случае – приложение будет непопулярным.

Ветка № 2: «Какова себестоимость продукта?». Если его создание требует больших финансовых затрат, он должен иметь высокий спрос, иначе велик риск понести серьезные финансовые потери.

Ветка № 3: «Есть ли конкуренты на рынке и сколько их?». Даже если спрос на продукт высок, а стоимость его мала, не нужно забывать о конкурентах. Крупные известные бренды уже завоевали доверие клиентов, поэтому привлечь внимание пользователей к новому продукту может быть сложно. Для этого нужно потратить много средств на рекламу.

Рассмотрим категории, охватывающие возможные сценарии:

• Конкурентов мало – конкуренция средняя, шансы на успех имеются.

• Конкурентов много – конкуренция высокая, шансов на успех крайне мало.

Третий шаг. Распишите листья подробно. Подобрав комбинацию условий, принимайте решение:

• Отказаться от запуска продукта – риски слишком большие: высокая себестоимость продукта, низкий спрос и наличие конкурентов.

• Отложить запуск на более подходящее время – в настоящее время условия сложны в исполнении, но есть потенциал.

• Запустить продукт – условия подходящие: низкая себестоимость продукта, большой спрос и отсутствие или маленькое количество конкурентов.

Как заполнять дерево, основываясь на комбинации из имеющихся условий:

• Низкий спрос – Не запускать продукт.

• Высокий спрос + Много конкурентов + Высокая себестоимость – Отложить запуск продукта.

• Высокий спрос + Низкая стоимость – Создать продукт.

• Средний спрос + Средняя стоимость + Мало или нет конкурентов – Создать продукт.

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

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

ТОП-7 кейсов
из разных ниш с ростом
от 89% до 1732%

Узнать подробнее

Пример 2. Как чат-бот может забронировать места в ресторане?

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

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

Шаг 1. Первым делом нужно определиться с корнем. Это главный вопрос, с которого будет начинаться разговор, например: «Вы хотите забронировать столик?». Пользователь может выбрать ответ «да» и уточнить детали или выбрать «нет» и закрыть чат.

Шаг 2. Далее выстраиваются ветки разговора. Открывается узел: «На какое количество человек нужен столик?». В вариантах ответа должны быть представлены наиболее популярные запросы. Например:

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

• Столик на 3-6 человек. Здесь у клиента могут возникнуть дополнительные требования, например, VIP-комната. Также нужно уточнить детали заказа.

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

Источник: shutterstock.com

Для двух первых сценариев за первым узлом следует вопрос: «На какой день забронировать столик?». В зависимости от ответа бот предложит доступные варианты:

• Будний день.

• Выходной день.

Для второго сценария (столик на 3-6 человек) добавляется вопрос: «Нужна VIP-комната?», где предусмотрено два варианта ответа: «да» и «нет».

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

• Забронировать столик.

• Перевести на оператора.

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

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

Критерий остановки алгоритма

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

Чтобы сформировать наиболее оптимальное дерево решений по точности и сложности, используются разные критерии, например:

• максимально возможное количество узлов (глубина дерева);

• минимальное количество примеров в каждом узле;

• процент правильно распознанных примеров;

• процент примеров в узле, который допустимо отнести к одному классу;

• степень увеличения или уменьшения информации при последующем разделении.

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

Отсечение ветвей дерева принятия решений

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

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

Для ускорения процесса используется метод по отсечению веток, называемый «стрижкой» дерева. Отсекаются ветки в обратном направлении. Рассмотрим алгоритм отсечения:

• Шаг 1. Сформировать дерево, в каждом листе которого останется по одному элементу.

• Шаг 2. Высчитать долю верно и неверно распознанных примеров.

• Шаг 3. Отсечь узлы, отсутствие которых не изменит показателей второго шага. Отсечение означает превращение их в листья.

Данный метод требует достаточного количества времени на обучение: построение дерева, расчет точности, отсечение ветвей. Но он более точен в отличие от метода преждевременной остановки.

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

Преимущества дерева принятия решений:

• Формирование понятных, четких правил классификации. Например, если возраст клиента менее 40 лет и отсутствует имущество для залога, он получает отказ в выдаче кредита.

• Способность генерирования правил в тех областях, в которых специалисту сложно свои знания формализовать.

• Хорошо визуализируется, то есть «интерпретируется», не только в качестве модели, но и в качестве прогноза для конкретного тестового субъекта (путь).

• Способно быстро обучаться и прогнозировать.

• Не нуждается в большом количестве параметров модели.

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

Источник: shutterstock.com

Недостатки дерева принятия решений:

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

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

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

• Трудности с поиском оптимального метода и необходимость использования эвристики типа «жадного» поиска признака с максимальным приростом данных. В итоге это не гарантирует нахождения оптимального дерева решений.

• Из-за подхода дерева решений могут охватываться не все объекты из обучающей выборки.

Скачайте полезный документ по теме:

Чек-лист: Как добиваться своих целей в переговорах с клиентами

Часто задаваемые вопросы о дереве принятия решений

Почему при построении дерева решений у людей возникают ошибки?

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

С помощью каких инструментов создаются сложные модели деревьев?

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

В Python есть бесплатная библиотека Scikit-learn с классом Decision Tree и предподготовленным кодом.

Как дерево помогает снижать риски?

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

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

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

Определяем точку баланса:

• Если цель – накопить деньги с минимальным риском, выбираем консервативный путь.

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

Не нужно идти до конца, если понимаете, что пошли не по тому пути. Добавляйте в дерево «красные флаги» – сигналы, которые предупредят, когда нужно изменить траекторию движения. Предположим, криптовалюта падает в цене более чем на 20 % в течение трех месяцев. В такой ситуации нужно срочно продавать активы.

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

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

Источник изображения на шапке: shutterstock.com

Автор статьи

Дмитрий Свистунов

Руководитель SEO-отдела и разработки

Последние статьи этого автора:

• Адаптивная верстка сайта: гайд для начинающих
• Анкор ссылки: виды, правила составления, влияние на продвижение
• Белая раскрутка сайта без перехода на темную сторону

Забрать ценные бизнес-подарки бесплатно

Полезные
материалы
для руководителей

Скачать 3,2 MB