Как вырастить дерево при помощи Python

Бывает так, что IT-сотрудник для анализа данных подключает библиотеку и бездумно использует все представленные в ней методы, совершенно не понимая, какие алгоритмы и механизмы находятся «под капотом». Поэтому в рамках этой статьи мы разберём простейший алгоритм «Дерево решений» из библиотеки sklearn, а точнее, как он работает с точки зрения математики и теории вероятностей, как алгоритм «учится», и что происходит, когда мы передаём ему данные для обучения.

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

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

Как вырастить дерево при помощи Python

Для простоты понимания работы дерева решений будем рассматривать эту задачу на основе всего двух параметров: «Год выпуска» и «Пробег». Расположим наши данные на точечном графике.

Как вырастить дерево при помощи Python

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

Как вырастить дерево при помощи Python

Целью разбиения было получение чистого множества. В данном случае все автомобили с пробегом менее 165 тысяч целы. Таким образом, мы получили чистое множество.

Чистым множеством называется множество, энтропия которого равна 0.

Энтропия – это мера неопределённости некоторой системы, которая колеблется от 0 до 1. Другими словами, чем ближе энтропия к 0, тем большая часть данных принадлежит к одной и той же группе. Энтропия вычисляется по формуле:

Как вырастить дерево при помощи Python

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

Как вырастить дерево при помощи Python

Как мы видим, у исходного множества довольно высокая энтропия. Это говорит о том, что оно достаточно хаотичное.

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

Как вырастить дерево при помощи Python

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

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

Как вырастить дерево при помощи Python

Рассчитаем информационный выигрыш для нашего разбиения:

Как вырастить дерево при помощи Python

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

Как вырастить дерево при помощи Python

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

Как вырастить дерево при помощи Python

Разбиение левой таблицы производилось по году выпуска автомобиля на группы «до 2016 года» и «после 2016 года»

Как вырастить дерево при помощи Python

В данном случае разбиение снова произошло по году выпуска.

После всех разбиений дерево выглядит так:

Как вырастить дерево при помощи Python

Необходимо так же упомянуть об ещё одном важном параметре – индексе Джини. Он позволяет оценить, насколько правильно, на основе текущих данных, будет определена принадлежность элемента к той или иной группе. Индекс Джини рассчитывается по формуле:

Как вырастить дерево при помощи Python

Ради примера рассчитаем индекс Джини для левого узла первого разбиения:

Как вырастить дерево при помощи Python

Теперь перейдём к практике.

Реализуем то же самое через популярную библиотеку для Python – Scikit-learn (sklearn). Эта библиотека является одной из самых популярных для Data Science и Machine Learning. Она предоставляет различные алгоритмы для решения задач классификации, регрессии и кластеризации. Это простой и эффективный инструмент для предиктивного анализа данных.

Подключаем все необходимые библиотеки

Как вырастить дерево при помощи Python

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

Как вырастить дерево при помощи Python

Теперь заведём переменную model, которая будет являться объектом дерева решений, и сразу передадим дереву данные, по которым оно будет строиться.

Как вырастить дерево при помощи Python

Теперь попробуем предсказать, будет ли поломана машина 2013 года с пробегом 600 тысяч.

Как вырастить дерево при помощи Python

Дерево выдало ответ «0», что соответствует поломанной машине. Теперь для наглядности давайте выведем полное дерево.

Как вырастить дерево при помощи Python

Получилось такое дерево условий:

Как вырастить дерево при помощи Python

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

Как вырастить дерево при помощи Python

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

Теперь попробуем на примере, больше приближённом к реальности. Будем предсказывать, будет ли одобрена кредитная карта по двум параметрам: возраст и среднемесячный доход. Наша выборка будет составлять 1320 элементов.

Как вырастить дерево при помощи Python

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

Заключение

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

88
12 комментариев

Следующая статья будет называться "Как родить сына при помощи Python"

3
Ответить

Как вырастить дерево при помощи Python - думал тут будет Arduino запрограммированный на полив и удобрение растений в зависимости от показателей почвы. А не вот это вот все!

:)

5
Ответить

Вот вам без питонов за 10 секунд расчёт

2
Ответить

Хотя нет, учитывая, что после 10го года хлам производят - вот такой

2
Ответить

Спасибо! Очень интересно! :)

Энтропия – это мера неопределённости некоторой системы, которая колеблется от 0 до 1.

Небольшая поправка: область значений энтропии лежит не от 0 до 1, а от 0 до +∞, по идее. Но я не уверен, будет здорово, если вы развеете это сомнение.

1
Ответить
Автор

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

1
Ответить

Очень актуально: как раз решал задачу оценки абсолютного спроса на группы товаров, и хорошо сработал именно этот алгоритм. И статья - топ, прям для меня, все на пальцах)))

1
Ответить