Вторая половина ХХ века была прорывной для многих сфер знаний: статистики, психологии, менеджмента, компьютеров и искусственного интеллекта. Предпринимались попытки описать опыт обучения и передать машинам. Основатель «Школы траблшутеров» Олег Брагинский и ученик Владислав Иванов изучают алгоритм принятия решений и предсказания в виде дерева.
Логика – упрямая наука. Настаивает на двойственности мира. Основа удачно легла в двоичную систему, что правит вычислительными машинами. Условные суждения типа «если…, то…» позволяют соотнести причины и следствия, критерии и условия, субъекты и объекты.
Такой подход получил название «дерево решений». Суть – постепенно пройти по предпосылкам, чтобы классифицировать данные, спрогнозировать или принять решение. Изображается графом. Может быть бинарным или произвольным. В первом случае каждая вершина содержит только два исхода.
В состав дерева входят:
- корень (корневой узел) – вершина, с которой начинается работа
- узлы – дополнительные критерии для конкретизации решения
- листья (терминальные вершины) – итоговые значения
- ветви – рёбра графа, соединяющие вершины.
Общий вид у дерева решений следующий:
Построим дерево на примере. Вопрос возьмём бытовой: куда отправиться в отпуск?
Поехать можно за границу или остаться в родной стране.
Затем определим: какой тип отдыха больше нравится?
И, конечно, куда без денег? Сузим этот вопрос до формулировок: бюджет большой ($+), бюджет малый ($-).
Теперь легко выбрать. Хотим поехать в другую страну, предпочитаем активный отдых и не имеем огромного запаса финансов – путь лежит в Египет (1-2-4-9). Отпуск внутри родного государства, желание погреться на солнышке и достаточное количество денег – Сочи (1-3-7-14).
Дерево решений для бытовой задачи построено. Для наглядности вопросы размещают слева или справа от графа на соответствующих уровнях вершин.
Обратимся ко второй сфере популярности алгоритма – машинному обучению (machine learning). Перемещение по дереву опирается не столько на вопросы, сколько на явные атрибуты, а цель – прогноз или классификация данных. Предсказательные деревья называются регрессионными.
На вход подаётся таблица с данными. Попробуем построить дерево для оценки вероятности выдачи кредита. Значения 0 и 1 в столбце «Одобрение» соответствуют ответам «отказ» и «одобрено».
С помощью языка программирования Python и библиотеки машинного обучения sklearn проанализируем таблицу. На выходе получаем дерево:
В вершине – критерий «Кредитная история». Значит, программа посчитала прирост индекса Джини (gini) для каждого признака и выбрала дающий оптимальное разбиение на классы. Индекс Джини демонстрирует «умение узла качественно разделять объекты на классы».
Значение 690 также возникло в ходе вариаций. Оказалось лучшим решением: отказы и одобрения расходятся без потерь. Заодно сводит к нулю неопределённость в листьях (gini = 0).
Показатель «samples» указывает на долю объектов в узле от общего числа. В корне дерева – 100%, в остальных 60% и 40%. В левом листе три объекта из таблицы, в правом – два.
Новые заявки на кредитование проверяются по единственному условию: балл кредитной истории. Превышает 690 – одобрение, ниже – отказ.
Дерево решений применяют широко: скрипты звонков и общения с технической поддержкой или клиентами, оценка кредитных заявок и страхования, предсказание стоимости б/у-автомобиля или иной техники, постановка диагноза, классификация покупателей и товаров.