NTA

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

0
12 комментариев
Популярные
По порядку
Написать комментарий...
Oleg Kyl

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

Ответить
3
Развернуть ветку
Полный блик

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

:)

Ответить
4
Развернуть ветку
Алексей Кутузов

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

Ответить
2
Развернуть ветку
Viacheslav Egorenkov

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

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

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

Ответить
1
Развернуть ветку
NTA

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

Ответить
1
Развернуть ветку
Viacheslav Egorenkov

И действительно:

Ответить
1
Развернуть ветку
Andrey Shevtsov

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

Ответить
1
Развернуть ветку
NTA

Спасибо за отзыв, рады, что смогли помочь )

Ответить
0
Развернуть ветку
Алексей Кутузов

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

Ответить
1
Развернуть ветку
Vladimir Kindyuk

спасибо, очень интересно.
попробую реализовать для своих примеров

Ответить
1
Развернуть ветку
NTA

Вам спасибо )
Удачи в реализации!

Ответить
0
Развернуть ветку
Дмитрий Крюков

я вообще не шарю в этом, по этому для меня это просто набор символов.

Ответить
0
Развернуть ветку
Читать все 12 комментариев
Пять путешествий до Луны — столько километров ленты в TikTok могли просмотреть пользователи Yota за 2021 год
Специфика поиска работы на сайте hh

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

Как пандемия изменила рынок онлайн-страхования

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

Как я ходила на собеседование в ВТБ и оказалась в начале 2000-х

Итак, быстро ввожу в курс дела. Мне чуть более 40 лет, 16 из которых я продаю разные банковские продукты... На сайте давно, но как читательница. Теперь решила написать про личный опыт и впечатление от свежего собеседования в госбанке.

Это нужно знать иностранцам, желающим получить гражданство Турции, на основании покупки недвижимости
Как я адаптировал популярную игру и за неделю привлёк 100 тысяч пользователей без бюджета

За 6 часов сделал первую версию игры и ворвался в тренды Твиттера с одного твита. Привлек 100 000 пользователей за неделю, а также попал в более 50 СМИ страны. Как это было и что я для этого сделал можно узнать в статье.

«Холакратия, любимые мемчики и прозрачность»: программист о работе в Точке, моделинге и запуске треков на Spotify

Точка — это про людей. Про сотрудников, которые создают удобный банк для бизнеса. Мы запускаем серию интервью с нашей командой, чтобы рассказать, как у нас всё устроено.

Чтобы я посоветовал себе как предприниматель, если бы встретил себя 10 лет назад

До стартапа Event Link у меня уже был опыт, в том числе в качестве предпринимателя. Были как успешные бизнесы и стартапы, так и с факапами на 45 млн. руб.. Вот такие советы я бы дал себе, если бы встретил себя 10 лет назад

Банкомат «Тинькофф» внёс не все деньги на мой счёт

28.12.2021 пополнял карту в банкомате Тинькофф, положить нужно было 60 тысяч. Выбрал на банкомате "Пополнить", положил в лоток 12 купюр по 5 тысяч, банкомат начал шуршать, через какое-то время на экране появилось сообщение типа "Заберите нераспознанные купюры", открылся лоток, в нем 5 купюр(25 тысяч), деньги забрал, на экране появилась сумма…

«Инновации — это поле для сражений»

Как фуд-ритейл внедряет новые технологии.

Статус бота Veles
null