Как разобраться в дереве принятия решений и сделать его на Python
Совсем скоро, 20 ноября, у нас стартует новый поток «Математика и Machine Learning для Data Science», и в преддверии этого мы делимся с вами полезным переводом с подробным, иллюстрированным объяснением дерева решений, разъяснением энтропии дерева решений с формулами и простыми примерами, вводом понятия «информационный выигрыш», которое игнорируется большинством умозрительно-простых туториалов. Статья рассчитана на любящих математику новичков, которые хотят больше разобраться в работе дерева принятия решений. Для полной ясности взят совсем маленький набор данных. В конце статьи — ссылка на код на Github.
Дерево решений — тип контролируемого машинного обучения, который в основном используется в задачах классификации. Дерево решений само по себе — это в основном жадное, нисходящее, рекурсивное разбиение. «Жадное», потому что на каждом шагу выбирается лучшее разбиение. «Сверху вниз» — потому что мы начинаем с корневого узла, который содержит все записи, а затем делается разбиение.
Корневой узел — самый верхний узел в дереве решений называется корневой узел.
Узел принятия решения — подузел, который разделяется на дополнительные подузлы, известен как узел принятия решения.
Лист/терминальный узел — узел, который не разделяется на другие узлы, называется терминальный узел, или лист.
Набор данных
Я взяла совсем маленький набор данных, содержащий индекс массы тела (BMI), возраст (Age) и целевую переменную Diabetes (диабет). Давайте спрогнозируем, будет у человека данного возраста и индекса массы тела диабет или нет.
Представление набора данных
На графике невозможно провести какую-то прямую, чтобы определить границу принятия решения. Снова и снова мы разделяем данные, чтобы получить границу решения. Так работает алгоритм дерева решений.
Вот так в дереве решений происходит разбиение.
Важные теоретические определения
Энтропия
Энтропия — это мера случайности или неопределенности. Уровень энтропии колеблется от 0 до 1 . Когда энтропия равна 0, это означает, что подмножество чистое, то есть в нем нет случайных элементов. Когда энтропия равна 1, это означает высокую степень случайности. Энтропия обозначается символами H(S).
Формула энтропии
Энтропия вычисляется так: -(p(0) * log(P(0)) + p(1) * log(P(1)))
P(0) → Вероятность принадлежности к класу 0
P(1) → Вероятность принадлежности к классу 1
Связь между энтропией и вероятностью
Когда энтропия равна 0, это означает, что подмножество «чистое», то есть в нем нет энтропии: либо все «да», либо все голоса «нет». Когда она равна 1, то это означает высокую степень случайности. Построим график вероятности P(1) вероятности принадлежности к классу 1 в зависимости от энтропии. Из объяснения выше мы знаем, что:
Если P(1) равно 0, то энтропия равна 0
Если P(1) равно 1, то энтропия равна 0
Если P(1) равно 0,5, то энтропия равна 1
Уровень энтропии всегда находится в диапазоне от 0 до 1.
Информационный выигрыш
Информационный выигрыш для разбиения рассчитывается путем вычитания взвешенных энтропий каждой ветви из исходной энтропии. Используем его для принятия решения о порядке расположения атрибутов в узлах дерева решений.
H(S) → Энтропия
A → Атрибут
S → Множество примеров
V → Возможные значения A
Sv → Подмножество
Как работает дерево решений
В нашем наборе данных два атрибута, BMI и Age. В базе данных семь записей. Построим дерево решений для нашего набора данных.
1. Корневой узел
В дереве решений начнем с корневого узла. Возьмем все записи (в нашем наборе данных их семь) в качестве обучающих выборок.
В корневом узле наблюдаем три голоса за и четыре против.
Вероятность принадлежности к классу 0 равна 4/7. Четыре из семи записей принадлежат к классу 0.
P(0) = 4/7
Вероятность принадлежности к классу 1 равна 3/7. То есть три из семи записей принадлежат классу 1.
P(1) = 3/7.
Вычисляем энтропию корневого узла:
2. Как происходит разбиение?
У нас есть два атрибута — BMI и Age. Как на основе этих атрибутов происходит разбиение? Как проверить эффективность разбиения?
1. При выборе атрибута BMI в качестве переменной разделения и ≤30 в качестве точки разделения мы получим одно чистое подмножество.
Точки разбиения рассматриваются для каждой точки набора данных. Таким образом, если точки данных уникальны, то для n точек данных будет n-1 точек разбиения. То есть в зависимости от выбранных точки и переменной разбиения мы получаем высокий информационный выигрыш и выбираем разделение с этим выигрышем. В большом наборе данных принято считать только точки разделения при определенных процентах распределения значений: 10, 20, 30%. У нас набор данных небольшой, поэтому, видя все точки разделения данных, я выбрала в качестве точки разделения значения ≤30.
Энтропия чистого подмножества равна нулю. Теперь рассчитаем энтропию другого подмножества. Здесь у нас три голоса за и один против.
P(0)=1/4 [одна из четырех записей)
P(1)=3/4 [три из четырех записей)
Чтобы решить, какой атрибут выбрать для разбиения, нужно вычислить информационный выигрыш.
2. Выберем атрибут Age в качестве переменной разбиения и ≤45 в качестве точки разбиения.
Давайте сначала вычислим энтропию подмножества True. У него есть одно да и одно нет. Это высокий уровень неопределенности. Энтропия равна 1. Теперь рассчитаем энтропию подмножества False. В нем два голоса за и три против.
3. Рассчитаем информационный выигрыш.
Мы должны выбрать атрибут, имеющий высокий информационный выигрыш. В нашем примере такую ценность имеет только атрибут BMI. Таким образом, атрибут BMI выбирается в качестве переменной разбиения. После разбиения по атрибуту BMI мы получаем одно чистое подмножество (листовой узел) и одно нечистое подмножество. Снова разделим это нечистое подмножество на основе атрибута Age. Теперь у нас есть два чистых подмножества (листовой узел).
Итак, мы создали дерево решений с чистыми подмножествами.
Напишем это на Python с помощью sklearn
1. Импортируем библиотеки.
import numpy as np import pandas as pd import matplotlib.pyplot as plt import seaborn as sns
2. Загрузим данные.
df=pd.read_csv("Diabetes1.csv") df.head()
3. Разделим переменные на x и y.
Атрибуты BMI и Age принимаются за x.
Атрибут Diabetes (целевая переменная) принимается за y.
x=df.iloc[. 2] y=df.iloc[:,2:] x.head(3)
y.head(3)
4. Построим модель с помощью sklearn
from sklearn import tree model=tree.DecisionTreeClassifier(criterion="entropy") model.fit(x,y)
Вывод: DecisionTreeClassifier (criterion=«entropy»)
5. Оценка модели
model.score(x,y)
Вывод: 1.0 . Мы взяли очень маленький набор данных, поэтому оценка равна 1.
6. Прогнозирование с помощью модели
Давайте предскажем, будет ли диабет у человека 47 лет с ИМТ 29. Напомню, что эти данные есть в нашем наборе данных.
model.predict([[29,47]])
Вывод: array([‘no’], dtype=object)
Прогноз — нет, такой же, как и в наборе данных. Теперь спрогнозируем, будет ли диабет у человека 47 лет с индексом массы тела 45. Отмечу, что этих данных в нашем наборе нет.
model.predict([[45,47]])
Вывод: array([‘yes’], dtype=object)
7. Визуализация модели:
tree.plot_tree(model)
Код и набор данных из этой статьи доступны на GitHub.
Приходите изучать математику к нам на курс «Математика и Machine Learning для Data Science» а промокод HABR, добавит 10 % к скидке на баннере.
- «Математика и Machine Learning для Data Science»
- Продвинутый курс «Machine Learning Pro + Deep Learning»
- Курс «Python для веб-разработки»
- Обучение профессии Data Science
- Обучение профессии Data Analyst
- Онлайн-буткемп по Data Analytics
Eще курсы
- Курс по Machine Learning
- Курс по JavaScript
- Профессия Веб-разработчик
- Профессия Java-разработчик
- C++ разработчик
- Курс по аналитике данных
- Курс по DevOps
- Разработчик игр на Unity
- Профессия iOS-разработчик с нуля
- Профессия Android-разработчик с нуля
Рекомендуемые статьи
- Как стать Data Scientist без онлайн-курсов
- 450 бесплатных курсов от Лиги Плюща
- Как изучать Machine Learning 5 дней в неделю 9 месяцев подряд
- Сколько зарабатывает аналитик данных: обзор зарплат и вакансий в России и за рубежом в 2020
- Machine Learning и Computer Vision в добывающей промышленности
Анализ решений и деревья в Python
Использование деревьев решений в Python для получения информации о решении A переехать в Лас-Вегас.
Совсем недавно владелец бейсбольной команды Oakland Athletics Джон Фишер объявил, что команда приобрела около 50 акров земли в Лас-Вегасе, штат Невада.[1] Это ставит под угрозу будущее последней оставшейся профессиональной спортивной команды Окленда. За последние 5 лет в Окленде «Голден Стэйт Уорриорз» (НБА) и «Лас-Вегас Рейдерс» (НФЛ) отправились на более новые, более блестящие стадионы в других городах (хотя «Голден Стэйт» только что пересек мост через залив в Сан-Франциско). Хотя процесс принятия решений во фронт-офисе Oakland A остается для меня загадкой, наука о данных и анализ решений в тандеме могут многое рассказать о мотивах Джона Фишера переехать в Лас-Вегас.
Анализ решений важен для понимания всеми учеными, занимающимися данными, потому что он является мостом между высокотехнологичной работой вероятностных и статистических моделей и бизнес-решениями. Понимание того, как принимаются бизнес-решения, может помочь сформулировать нашу работу и представить наши выводы нетехнической аудитории, поскольку мы предоставляем действенные рекомендации и выводы. В Институте исследования операций и управления (INFORMS) даже есть целое общество, занимающееся анализом решений.
Кроме того, машинное обучение может помочь обобщить результаты анализа решений, открывая возможности вероятностного анализа чувствительности. После первоначального построения модели, анализирующей сценарии Окленда и Лас-Вегаса с использованием анализа решений, мы будем использовать машинное обучение для поиска шаблонов, которые могут помочь выявить действенные рекомендации для А, если обстоятельства принятия решения изменятся.
Что такое анализ решений?
Анализ решений — это область исследования, посвященная «систематическому, количественному и визуальному подходу к рассмотрению и оценке важных вариантов».[2] Это может быть мощным инструментом в среде с низким объемом данных и помочь людям использовать сочетание экспертных знаний в предметной области и предварительных знаний для повышения ожидаемой ценности сложных решений. Он используется в самых разных областях, таких как экономика, управление и анализ политики.
Как правило, в мире анализа решений мы принимаем байесовскую точку зрения на мир. Основная теорема Байеса заключается в следующем:
Где: P(A) — вероятность возникновения события A, P(B) — вероятность возникновения события B, P(A|B) — вероятность возникновения события A при условии, что событие B произошло, а P(B|A) — вероятность наступления события B при условии, что произошло событие A. Как правило, P(A) представляет собой априорное мнение о вероятности наступления события A, а B представляет некоторые новые данные. P(A|B) — это обновленное апостериорное убеждение о вероятности наступления события A после того, как вы наблюдали событие B.
Например, предположим, что мы идем в Колизей округа Окленд-Аламеда, чтобы посмотреть игру в мяч, но мы не отслеживаем статистику игроков. Мы начинаем со знания, что аутфилдеры попадают на базу с вероятностью 0,35, инфилдеры попадают на базу с вероятностью 0,25, а назначенные нападающие попадают на базу с вероятностью 0,4. Пусть A будет событием, что следующий отбивающий будет аутфилдером, B будет событием, что следующий отбивающий станет инфилдером, а C будет событием, что следующий отбивающий станет назначенным нападающим. Поскольку нам известен состав бейсбольной команды, мы уже знаем, что P(A) = 0,33, P(B) = 0,56 и P(C) = 0,11. Теперь следующий отбивающий подходит к тарелке и, к нашей радости, попадает на базу (событие D)! Из наших предыдущих знаний о бейсболе мы знаем, что P(D|A) = 0,35, P(D|B) = 0,25 и P(D|C) = 0,4. Используя закон полной вероятности, мы можем вычислить P(D) = P(D|A)P(A) + P(D|B)P(D) + P(D|C)P(C) = 0,3. Теперь мы можем обновить наши представления о том, каким игроком был отбивающий: P(A|D) = 0,39, P(B|D) = 0,47 и P(C|D) = 0,15. Увидев, как игрок попадает на базу, мы теперь с большей вероятностью поверим, что игрок не был инфилдером. Теперь, когда вы находитесь в правильном настроении, давайте продолжим.
Ключевым инструментом анализа решений является дерево решений (не путать с одноименным алгоритмом машинного обучения).[3] Дерево решений состоит из двух основных компонентов: узла решения и узла выбора.[3] В этом блоге я собираюсь показать вам, как построить дерево решений, оценить его в Python и понять решение Окленда А переехать в Лас-Вегас.
Какое решение?
Ховард и Аббас определяют решение как «выбор между двумя или более альтернативами, который предполагает безвозвратное распределение ресурсов».[3] Это широкое определение, но в нашем примере с командой «А» из Окленда решение таково: должна ли бейсбольная команда «Атлетикс» остаться в Окленде или переехать в Лас-Вегас? В этом случае решение бесповоротно, потому что новый стадион будут строить вне зависимости от выбранного города.
Какие неопределенности?
Неопределенность окружает каждое решение, которое мы принимаем. Принимая решение о том, оставаться ли в Окленде или переезжать в Лас-Вегас, члены А не уверены в стоимости нового стадиона и последующих операционных доходах: 1) сколько государственных денег они получат для финансирования своего нового стадиона, 2) какой доход они получат. приносят от продажи билетов, и 3) какой доход они принесут от сделок с местным телевидением.
В настоящее время «А» надеются построить в Лас-Вегасе стадион стоимостью 1,5 миллиарда долларов. [1] Еще в 2021 году организация запросила 855 миллионов долларов из государственных денег, чтобы помочь построить их новый стадион в Окленде, несмотря на то, что ранее было согласовано с городом и округом, что новый стадион в Окленде будет финансироваться из частных источников. [1] Таким образом, можно обоснованно предположить, что стоимость строительства стадиона примерно одинакова в обоих населенных пунктах. Единственная неопределенность здесь заключается в том, сколько денег налогоплательщиков пойдет на финансирование стадиона.
Предполагаемый доход от продажи билетов сильно различается между командами: от 27 до 131 миллиона долларов при медиане около 75 миллионов долларов. [4] По оценкам, доход Окленда от продажи билетов составил около 55 миллионов долларов. [4]
Доходы от телевидения в MLB равномерно распределяются по сделкам с национальным телевидением, заключаемым MLB. Однако важная составляющая доходов от телетрансляций отдельных команд поступает через региональные спортивные сети (RSN). Команды получают большую часть доходов от сделок с местным телевидением, хотя по-прежнему существует значительная часть доходов. После распределения доходов доходы от телевизионных контрактов с RSN варьировались от 36 до 131 миллиона долларов, при этом все команды, кроме самых ценных, зарабатывали менее 60 миллионов долларов. [4]
Благодаря переезду Raiders (NFL) в Лас-Вегас из Окленда несколько лет назад, мы знаем, что город Лас-Вегас был готов выделить 750 миллионов долларов из государственных средств на строительство совершенно нового футбольного стадиона. [5] Мы также знаем, что и местные жители, и туристы готовы присоединиться и поддержать новую профессиональную команду, поскольку «Рейдеры» возглавили НФЛ по доходам от билетов в 2021 году, составив 119 миллионов долларов за год. [6]
Существуют методы, которые выходят за рамки этого блога, чтобы запросить у лица, принимающего решения, предварительные убеждения о вероятных последствиях этих неопределенностей и вероятностях каждого из них. Кроме того, я сомневаюсь, что Джон Фишер готов комментировать мой блог. Итак, тем временем я буду использовать информацию, которую я собрал из этих веб-источников, чтобы представить несколько возможных сценариев для каждой неопределенности.
Каков наш временной горизонт принятия решения?
Конечно, доходы — это годовые цифры, и стадион должен прослужить гораздо дольше года. Временные горизонты могут различаться в зависимости от контекста решения и того, как лицо, принимающее решение, рассматривает вероятность изменения ландшафта. В терминах науки о данных это соответствует дрейфу данных, когда данные, используемые для обучения модели, отличаются от текущих данных. А пока давайте предположим, что эти оценки останутся довольно стабильными в течение десятилетия, и используем 10-летний временной горизонт с 3%-ной ставкой дисконтирования наших годовых затрат.
Как выглядит дерево решений?
Для лучшего понимания дерева решений предлагаем вам изучить статьи о том, как внедрять их с нуля и как их реализовать.
Теперь, когда мы определили все компоненты нашего дерева решений, пришло время построить дерево. Концептуально вот как это выглядит:
Квадратный узел — это узел принятия решения, круглые узлы — это случайные узлы, а треугольные узлы — конечные узлы. Из-за нехватки места все дерево не видно на изображении, но каждый узел также имеет связанную вероятность и значение.
Как построить модель на Python?
При анализе решений после построения нашего дерева решений мы можем определить наилучшее решение, «откатив» дерево. В этом примере мы предполагаем, что лицо, принимающее решение, принимает рациональное решение (также известное как ожидаемая ценность). Итак, мы начинаем с табулирования значения, связанного с терминальным состоянием, если оно применимо. Это станет нашим промежуточным итогом или ожидаемым значением. В данном случае это неприменимо, поэтому мы начинаем с суммы 0 долларов. Затем мы итеративно вычисляем ожидаемое значение каждого набора узлов слева от конечных узлов и добавляем его к промежуточному итогу или ожидаемому значению. В итоге мы получим одно ожидаемое значение решения остаться в Окленде и одно ожидаемое значение решения переехать в Лас-Вегас.
Давайте начнем с простой настройки нашего базового сценария. Мы собираемся использовать подход создания фрейма данных для всех возможных комбинаций сценариев решений, государственных денег, продажи билетов и доходов RSN.
import numpy as np import pandas as pd # Create data frame of all possible outcomes decision_list = ['Oakland', 'Las Vegas'] # First Node chance_node_stadium_money_scenarios = ['Optimistic', 'Neutral', 'Pessimistic'] chance_node_stadium_money_probabilities_oakland = [0.1, 0.3, 0.6] chance_node_stadium_money_probabilities_vegas = [0.5, 0.4, 0.1] chance_node_stadium_money_values = [855, 500, 0] #Second Node chance_node_ticket_sales_scenarios = ['Optimistic', 'Neutral', 'Pessimistic'] chance_node_ticket_sales_probabilities_oakland = [0.2, 0.2, 0.6] chance_node_ticket_sales_probabilities_vegas = [0.3, 0.4, 0.3] chance_node_ticket_sales_values_per_year = [80, 55, 27] # Third Node chance_node_rsn_revenue_scenarios = ['Optimistic', 'Neutral', 'Pessimistic'] chance_node_rsn_revenue_probabilities_oakland = [0.15, 0.5, 0.35] chance_node_rsn_revenue_probabilities_vegas = [0.1, 0.3, 0.6] chance_node_rsn_revenue_values_per_year = [60, 45, 36] # Convert annual values to NPV of 10 year time horizon time_horizon = 10 # years discount_rate = 0.03 # per year chance_node_ticket_sales_values = [val * (1 - (1/((1 + discount_rate)**time_horizon)))/discount_rate for val in chance_node_ticket_sales_values_per_year] chance_node_rsn_revenue_values = [val * (1 - (1/((1 + discount_rate)**time_horizon)))/discount_rate for val in chance_node_rsn_revenue_values_per_year] # Create data frame of all possible scenarios decision_list_list_for_df = [] chance_node_stadium_money_list_for_df = [] chance_node_stadium_money_probability_list_for_df = [] chance_node_stadium_money_value_list_for_df = [] chance_node_ticket_sales_list_for_df = [] chance_node_ticket_sales_probability_list_for_df = [] chance_node_ticket_sales_value_list_for_df = [] chance_node_rsn_revenue_list_for_df = [] chance_node_rsn_revenue_probability_list_for_df = [] chance_node_rsn_revenue_value_list_for_df = [] for i in decision_list: for j in range(len(chance_node_stadium_money_scenarios)): for k in range(len(chance_node_rsn_revenue_scenarios)): for m in range(len(chance_node_rsn_revenue_scenarios)): decision_list_list_for_df.append(i) chance_node_stadium_money_list_for_df.append(chance_node_stadium_money_scenarios[j]) chance_node_stadium_money_value_list_for_df.append(chance_node_stadium_money_values[j]) chance_node_ticket_sales_list_for_df.append(chance_node_ticket_sales_scenarios[k]) chance_node_ticket_sales_value_list_for_df.append(chance_node_ticket_sales_values[k]) chance_node_rsn_revenue_list_for_df.append(chance_node_rsn_revenue_scenarios[m]) chance_node_rsn_revenue_value_list_for_df.append(chance_node_rsn_revenue_values[m]) if i == 'Oakland': chance_node_stadium_money_probability_list_for_df.append(chance_node_stadium_money_probabilities_oakland[j]) chance_node_ticket_sales_probability_list_for_df.append(chance_node_ticket_sales_probabilities_oakland[k]) chance_node_rsn_revenue_probability_list_for_df.append(chance_node_rsn_revenue_probabilities_oakland[m]) elif i == 'Las Vegas': chance_node_stadium_money_probability_list_for_df.append(chance_node_stadium_money_probabilities_vegas[j]) chance_node_ticket_sales_probability_list_for_df.append(chance_node_ticket_sales_probabilities_vegas[k]) chance_node_rsn_revenue_probability_list_for_df.append(chance_node_rsn_revenue_probabilities_vegas[m]) decision_tree_df = pd.DataFrame(list(zip(decision_list_list_for_df, chance_node_stadium_money_list_for_df, chance_node_stadium_money_probability_list_for_df, chance_node_stadium_money_value_list_for_df, chance_node_ticket_sales_list_for_df, chance_node_ticket_sales_probability_list_for_df, chance_node_ticket_sales_value_list_for_df, chance_node_rsn_revenue_list_for_df, chance_node_rsn_revenue_probability_list_for_df, chance_node_rsn_revenue_value_list_for_df)), columns = ['Decision', 'Stadium_Money_Result', 'Stadium_Money_Prob', 'Stadium_Money_Value', 'Ticket_Sales_Result', 'Ticket_Sales_Prob', 'Ticket_Sales_Value', 'RSN_Revenue_Result', 'RSN_Revenue_Prob', 'RSN_Revenue_Value'])
Теперь, если вы напечатаете свое дерево решений, вы получите фрейм данных pandas из 54 строк и 10 столбцов. Мы можем легко откатить дерево решений, творчески используя функции группировки и слияния. Давайте начнем с подсчета ожидаемого значения доходов RSN для каждой комбинации решений, денег стадиона и продаж билетов:
decision_tree_df['RSN_EV'] = decision_tree_df['RSN_Revenue_Prob'] * decision_tree_df['RSN_Revenue_Value'] # Consolidate the RSN_EV values RSN_rollback_df = decision_tree_df.groupby(['Decision', 'Stadium_Money_Result', 'Stadium_Money_Prob', 'Ticket_Sales_Result', 'Ticket_Sales_Prob'])['RSN_EV'].sum().reset_index() # Keep the rest of the columns decision_tree_df = decision_tree_df.groupby(['Decision', 'Stadium_Money_Result', 'Stadium_Money_Prob', 'Ticket_Sales_Result', 'Ticket_Sales_Prob'])['Stadium_Money_Value', 'Ticket_Sales_Value'].mean().reset_index() # merge two dataframes decision_tree_df = pd.merge(decision_tree_df, RSN_rollback_df, on = ['Decision', 'Stadium_Money_Result', 'Stadium_Money_Prob', 'Ticket_Sales_Result', 'Ticket_Sales_Prob'])
Результирующая таблица уменьшилась, и теперь вы можете визуально увидеть ожидаемое значение отката узлов дохода RSN.
Повторение процесса с продажей билетов. У нас есть следующий код:
decision_tree_df['Ticket_Sales_RSN_EV'] = decision_tree_df['Ticket_Sales_Prob'] * decision_tree_df['Ticket_Sales_Value'] + decision_tree_df['RSN_EV'] # Consolidate the Ticket Sales and RSN_EV values ticket_sales_rollback_df = decision_tree_df.groupby(['Decision', 'Stadium_Money_Result', 'Stadium_Money_Prob'])['Ticket_Sales_RSN_EV'].sum().reset_index() # Keep the rest of the columns decision_tree_df = decision_tree_df.groupby(['Decision', 'Stadium_Money_Result', 'Stadium_Money_Prob'])['Stadium_Money_Value'].mean().reset_index() # merge two dataframes decision_tree_df = pd.merge(decision_tree_df, ticket_sales_rollback_df, on = ['Decision', 'Stadium_Money_Result', 'Stadium_Money_Prob'])
Наконец, повторяя для стадиона вклад государственных денег:
decision_tree_df['Stadium_Money_Ticket_Sales_RSN_EV'] = decision_tree_df['Stadium_Money_Prob'] * decision_tree_df['Stadium_Money_Value'] + decision_tree_df['Ticket_Sales_RSN_EV'] # Consolidate the Stadium Money, Ticket Sales, and RSN_EV values decision_tree_df = decision_tree_df.groupby(['Decision'])['Stadium_Money_Ticket_Sales_RSN_EV'].sum().reset_index()
Здесь мы видим, что модель рассчитывает, что в течение 10 лет ожидаемая стоимость пребывания в Окленде составляет 4,7 миллиарда долларов, а ожидаемая стоимость переезда в Лас-Вегас — 5,2 миллиарда долларов.
Как мы можем обобщить модель?
Конечно, и в наших данных, и в нашей модели есть неопределенность, и есть много разных сценариев, которые мы могли бы протестировать. Естественно, мы можем попытаться определить некоторые пороговые значения или сценарии, при которых решение меняется с пребывания в Окленде на переезд в Лас-Вегас (или наоборот). Эти точки принятия решений могут служить полезным набором «бизнес-правил» для лиц, принимающих решения, и могут помочь нам, специалистам по данным, извлекать действенные рекомендации из нашего анализа.
Есть много способов достичь этой цели, но в этом блоге мы будем использовать метамоделирование машинного обучения. Мета-моделирование включает в себя разработку более быстрой (а иногда и более простой) модели исходной математической или имитационной модели, которая принимает те же входные данные и дает очень похожие выходные данные [7]. В этом случае мы будем использовать вероятностный анализ чувствительности для проверки большого пространства параметров дерева решений анализа решений и отметить результирующее решение для каждого набора параметров. Затем мы обучим модель классификации дерева решений машинного обучения, используя набор параметров в качестве признаков и полученное решение в качестве меток для нашей модели машинного обучения. Преимущество модели машинного обучения заключается в том, что она раскрывает для нас сложные взаимосвязи, которые было бы трудно расшифровать только с помощью многомерного анализа чувствительности. Мы надеемся, что мы сможем получить достаточно точности от неглубокого дерева, чтобы описать сценарии, в которых пятерки должны остаться в Окленде, а не переехать в Лас-Вегас.
Во-первых, мы начинаем с разработки вероятностного анализа чувствительности. Для этого примера мы предположим, что долларовые значения узлов шансов останутся прежними, но вероятности различных результатов будут различаться. Поскольку мы знаем, что вероятности будут варьироваться между значениями 0 и 1, мы предположим, что вероятности всех сценариев равновероятны, и смоделируем их, используя равномерное распределение с минимальным значением 0 и максимальным значением 1. После трехкратной выборки из равномерного распределения (один для каждого оптимистического, нейтрального и пессимистического сценария) мы нормализуем результаты таким образом, чтобы сумма трех вероятностей составляла 1.
# Number of simulations n_sim = 5000 # Track scenarios oakland_stadium_money_probabilities_optimistic_list = [] oakland_stadium_money_probabilities_neutral_list = [] oakland_stadium_money_probabilities_pessimistic_list = [] oakland_ticket_sales_probabilities_optimistic_list = [] oakland_ticket_sales_probabilities_neutral_list = [] oakland_ticket_sales_probabilities_pessimistic_list = [] oakland_rsn_revenue_probabilities_optimistic_list = [] oakland_rsn_revenue_probabilities_neutral_list = [] oakland_rsn_revenue_probabilities_pessimistic_list = [] vegas_stadium_money_probabilities_optimistic_list = [] vegas_stadium_money_probabilities_neutral_list = [] vegas_stadium_money_probabilities_pessimistic_list = [] vegas_ticket_sales_probabilities_optimistic_list = [] vegas_ticket_sales_probabilities_neutral_list = [] vegas_ticket_sales_probabilities_pessimistic_list = [] vegas_rsn_revenue_probabilities_optimistic_list = [] vegas_rsn_revenue_probabilities_neutral_list = [] vegas_rsn_revenue_probabilities_pessimistic_list = [] oakland_EV_list = [] vegas_EV_list = [] decision_list = [] # Create data frame of all possible outcomes decision_list = ['Oakland', 'Las Vegas'] # First Node chance_node_stadium_money_scenarios = ['Optimistic', 'Neutral', 'Pessimistic'] chance_node_stadium_money_values = [855, 500, 0] #Second Node chance_node_ticket_sales_scenarios = ['Optimistic', 'Neutral', 'Pessimistic'] chance_node_ticket_sales_values_per_year = [80, 55, 27] # Third Node chance_node_rsn_revenue_scenarios = ['Optimistic', 'Neutral', 'Pessimistic'] chance_node_rsn_revenue_values_per_year = [60, 45, 36] # Convert annual values to NPV of 10 year time horizon time_horizon = 10 # years discount_rate = 0.03 # per year chance_node_ticket_sales_values = [val * (1 - (1/((1 + discount_rate)**time_horizon)))/discount_rate for val in chance_node_ticket_sales_values_per_year] chance_node_rsn_revenue_values = [val * (1 - (1/((1 + discount_rate)**time_horizon)))/discount_rate for val in chance_node_rsn_revenue_values_per_year] # Run the probabilistic sensitivity analysis n_sim times for n in range(n_sim): ## Set up tree #First node chance_node_stadium_money_probabilities_oakland = np.random.uniform(0,1,3) chance_node_stadium_money_probabilities_oakland = chance_node_stadium_money_probabilities_oakland / np.sum(chance_node_stadium_money_probabilities_oakland) chance_node_stadium_money_probabilities_vegas = np.random.uniform(0,1,3) chance_node_stadium_money_probabilities_vegas = chance_node_stadium_money_probabilities_vegas / np.sum(chance_node_stadium_money_probabilities_vegas) #Second Node chance_node_ticket_sales_probabilities_oakland = np.random.uniform(0,1,3) chance_node_ticket_sales_probabilities_oakland = chance_node_ticket_sales_probabilities_oakland / np.sum(chance_node_ticket_sales_probabilities_oakland) chance_node_ticket_sales_probabilities_vegas = np.random.uniform(0,1,3) chance_node_ticket_sales_probabilities_vegas = chance_node_ticket_sales_probabilities_vegas / np.sum(chance_node_ticket_sales_probabilities_vegas) # Third Node chance_node_rsn_revenue_probabilities_oakland = np.random.uniform(0,1,3) chance_node_rsn_revenue_probabilities_oakland = chance_node_rsn_revenue_probabilities_oakland / np.sum(chance_node_rsn_revenue_probabilities_oakland) chance_node_rsn_revenue_probabilities_vegas = np.random.uniform(0,1,3) chance_node_rsn_revenue_probabilities_vegas = chance_node_rsn_revenue_probabilities_vegas / np.sum(chance_node_rsn_revenue_probabilities_vegas) # Evaluate Tree # Create data frame of all possible scenarios decision_list_list_for_df = [] chance_node_stadium_money_list_for_df = [] chance_node_stadium_money_probability_list_for_df = [] chance_node_stadium_money_value_list_for_df = [] chance_node_ticket_sales_list_for_df = [] chance_node_ticket_sales_probability_list_for_df = [] chance_node_ticket_sales_value_list_for_df = [] chance_node_rsn_revenue_list_for_df = [] chance_node_rsn_revenue_probability_list_for_df = [] chance_node_rsn_revenue_value_list_for_df = [] for i in decision_list: for j in range(len(chance_node_stadium_money_scenarios)): for k in range(len(chance_node_rsn_revenue_scenarios)): for m in range(len(chance_node_rsn_revenue_scenarios)): decision_list_list_for_df.append(i) chance_node_stadium_money_list_for_df.append(chance_node_stadium_money_scenarios[j]) chance_node_stadium_money_value_list_for_df.append(chance_node_stadium_money_values[j]) chance_node_ticket_sales_list_for_df.append(chance_node_ticket_sales_scenarios[k]) chance_node_ticket_sales_value_list_for_df.append(chance_node_ticket_sales_values[k]) chance_node_rsn_revenue_list_for_df.append(chance_node_rsn_revenue_scenarios[m]) chance_node_rsn_revenue_value_list_for_df.append(chance_node_rsn_revenue_values[m]) if i == 'Oakland': chance_node_stadium_money_probability_list_for_df.append(chance_node_stadium_money_probabilities_oakland[j]) chance_node_ticket_sales_probability_list_for_df.append(chance_node_ticket_sales_probabilities_oakland[k]) chance_node_rsn_revenue_probability_list_for_df.append(chance_node_rsn_revenue_probabilities_oakland[m]) elif i == 'Las Vegas': chance_node_stadium_money_probability_list_for_df.append(chance_node_stadium_money_probabilities_vegas[j]) chance_node_ticket_sales_probability_list_for_df.append(chance_node_ticket_sales_probabilities_vegas[k]) chance_node_rsn_revenue_probability_list_for_df.append(chance_node_rsn_revenue_probabilities_vegas[m]) decision_tree_df = pd.DataFrame(list(zip(decision_list_list_for_df, chance_node_stadium_money_list_for_df, chance_node_stadium_money_probability_list_for_df, chance_node_stadium_money_value_list_for_df, chance_node_ticket_sales_list_for_df, chance_node_ticket_sales_probability_list_for_df, chance_node_ticket_sales_value_list_for_df, chance_node_rsn_revenue_list_for_df, chance_node_rsn_revenue_probability_list_for_df, chance_node_rsn_revenue_value_list_for_df)), columns = ['Decision', 'Stadium_Money_Result', 'Stadium_Money_Prob', 'Stadium_Money_Value', 'Ticket_Sales_Result', 'Ticket_Sales_Prob', 'Ticket_Sales_Value', 'RSN_Revenue_Result', 'RSN_Revenue_Prob', 'RSN_Revenue_Value']) decision_tree_df['RSN_EV'] = decision_tree_df['RSN_Revenue_Prob'] * decision_tree_df['RSN_Revenue_Value'] # Consolidate the RSN_EV values RSN_rollback_df = decision_tree_df.groupby(['Decision', 'Stadium_Money_Result', 'Stadium_Money_Prob', 'Ticket_Sales_Result', 'Ticket_Sales_Prob'])['RSN_EV'].sum().reset_index() # Keep the rest of the columns decision_tree_df = decision_tree_df.groupby(['Decision', 'Stadium_Money_Result', 'Stadium_Money_Prob', 'Ticket_Sales_Result', 'Ticket_Sales_Prob'])['Stadium_Money_Value', 'Ticket_Sales_Value'].mean().reset_index() # merge two dataframes decision_tree_df = pd.merge(decision_tree_df, RSN_rollback_df, on = ['Decision', 'Stadium_Money_Result', 'Stadium_Money_Prob', 'Ticket_Sales_Result', 'Ticket_Sales_Prob']) decision_tree_df['Ticket_Sales_RSN_EV'] = decision_tree_df['Ticket_Sales_Prob'] * decision_tree_df['Ticket_Sales_Value'] + decision_tree_df['RSN_EV'] # Consolidate the Ticket Sales and RSN_EV values ticket_sales_rollback_df = decision_tree_df.groupby(['Decision', 'Stadium_Money_Result', 'Stadium_Money_Prob'])['Ticket_Sales_RSN_EV'].sum().reset_index() # Keep the rest of the columns decision_tree_df = decision_tree_df.groupby(['Decision', 'Stadium_Money_Result', 'Stadium_Money_Prob'])['Stadium_Money_Value'].mean().reset_index() # merge two dataframes decision_tree_df = pd.merge(decision_tree_df, ticket_sales_rollback_df, on = ['Decision', 'Stadium_Money_Result', 'Stadium_Money_Prob']) decision_tree_df['Stadium_Money_Ticket_Sales_RSN_EV'] = decision_tree_df['Stadium_Money_Prob'] * decision_tree_df['Stadium_Money_Value'] + decision_tree_df['Ticket_Sales_RSN_EV'] # Consolidate the Stadium Money, Ticket Sales, and RSN_EV values decision_tree_df = decision_tree_df.groupby(['Decision'])['Stadium_Money_Ticket_Sales_RSN_EV'].sum().reset_index() # Fill out lists for meta-model inputs oakland_stadium_money_probabilities_optimistic_list.append(chance_node_stadium_money_probabilities_oakland[0]) oakland_stadium_money_probabilities_neutral_list.append(chance_node_stadium_money_probabilities_oakland[1]) oakland_stadium_money_probabilities_pessimistic_list.append(chance_node_stadium_money_probabilities_oakland[2]) oakland_ticket_sales_probabilities_optimistic_list.append(chance_node_ticket_sales_probabilities_oakland[0]) oakland_ticket_sales_probabilities_neutral_list.append(chance_node_ticket_sales_probabilities_oakland[1]) oakland_ticket_sales_probabilities_pessimistic_list.append(chance_node_ticket_sales_probabilities_oakland[2]) oakland_rsn_revenue_probabilities_optimistic_list.append(chance_node_rsn_revenue_probabilities_oakland[0]) oakland_rsn_revenue_probabilities_neutral_list.append(chance_node_rsn_revenue_probabilities_oakland[1]) oakland_rsn_revenue_probabilities_pessimistic_list.append(chance_node_rsn_revenue_probabilities_oakland[2]) vegas_stadium_money_probabilities_optimistic_list.append(chance_node_stadium_money_probabilities_vegas[0]) vegas_stadium_money_probabilities_neutral_list.append(chance_node_stadium_money_probabilities_vegas[1]) vegas_stadium_money_probabilities_pessimistic_list.append(chance_node_stadium_money_probabilities_vegas[2]) vegas_ticket_sales_probabilities_optimistic_list.append(chance_node_ticket_sales_probabilities_vegas[0]) vegas_ticket_sales_probabilities_neutral_list.append(chance_node_ticket_sales_probabilities_vegas[1]) vegas_ticket_sales_probabilities_pessimistic_list.append(chance_node_ticket_sales_probabilities_vegas[2]) vegas_rsn_revenue_probabilities_optimistic_list.append(chance_node_rsn_revenue_probabilities_vegas[0]) vegas_rsn_revenue_probabilities_neutral_list.append(chance_node_rsn_revenue_probabilities_vegas[1]) vegas_rsn_revenue_probabilities_pessimistic_list.append(chance_node_rsn_revenue_probabilities_vegas[2]) oakland_EV_list.append(decision_tree_df['Stadium_Money_Ticket_Sales_RSN_EV'][0]) vegas_EV_list.append(decision_tree_df['Stadium_Money_Ticket_Sales_RSN_EV'][1]) print(n)
Теперь мы можем поместить результаты в новый фрейм данных, который мы можем использовать для обучения нашей модели машинного обучения:
decision_tree_psa_data_df = pd.DataFrame(list(zip(oakland_stadium_money_probabilities_optimistic_list, oakland_stadium_money_probabilities_neutral_list, oakland_stadium_money_probabilities_pessimistic_list, oakland_ticket_sales_probabilities_optimistic_list, oakland_ticket_sales_probabilities_neutral_list, oakland_ticket_sales_probabilities_pessimistic_list, oakland_rsn_revenue_probabilities_optimistic_list, oakland_rsn_revenue_probabilities_neutral_list, oakland_rsn_revenue_probabilities_pessimistic_list, vegas_stadium_money_probabilities_optimistic_list, vegas_stadium_money_probabilities_neutral_list, vegas_stadium_money_probabilities_pessimistic_list, vegas_ticket_sales_probabilities_optimistic_list, vegas_ticket_sales_probabilities_neutral_list, vegas_ticket_sales_probabilities_pessimistic_list, vegas_rsn_revenue_probabilities_optimistic_list, vegas_rsn_revenue_probabilities_neutral_list, vegas_rsn_revenue_probabilities_pessimistic_list, oakland_EV_list, vegas_EV_list)), columns = ['oakland_stad_mon_prob_optimistic', 'oakland_stad_mon_prob_neutral', 'oakland_stad_mon_prob_pessimistic', 'oakland_ticket_sales_prob_optimistic', 'oakland_ticket_sales_prob_neutral', 'oakland_ticket_sales_prob_pessimistic', 'oakland_rsn_rev_prob_optimistic', 'oakland_rsn_rev_prob_neutral', 'oakland_rsn_rev_prob_pessimistic', 'vegas_stad_mon_prob_optimistic', 'vegas_stad_mon_prob_neutral', 'vegas_stad_mon_prob_pessimistic', 'vegas_ticket_sales_prob_optimistic', 'vegas_ticket_sales_prob_neutral', 'vegas_ticket_sales_prob_pessimistic', 'vegas_rsn_rev_prob_optimistic', 'vegas_rsn_rev_prob_neutral', 'vegas_rsn_rev_prob_pessimistic', 'oakland_EV', 'vegas_EV']) # Add decision based on EV decision_tree_psa_data_df['decision'] = 'Oakland' decision_tree_psa_data_df.loc[decision_tree_psa_data_df['vegas_EV'] > decision_tree_psa_data_df['oakland_EV'],'decision'] = 'Las Vegas'
Теперь мы обучим базовое дерево решений машинного обучения, используя учебный пакет sci-kit. Поскольку входные данные представляют собой вероятности от 0 до 1, и мы используем древовидную модель, нам не нужно будет выполнять масштабирование или разработку каких-либо функций. В целях визуализации для блога я ограничил глубину дерева до 3. Однако чем больше глубина дерева, тем выше вероятность достижения большей точности.
from sklearn.datasets import load_iris from sklearn.model_selection import cross_val_score from sklearn.model_selection import train_test_split from sklearn import tree #Features X = decision_tree_psa_data_df.drop(['oakland_EV', 'vegas_EV', 'decision'], axis = 1) #labels y = decision_tree_psa_data_df['decision'] # split into train (70%) and test set (30%) X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=32) # Create decision tree model with maximum depth of 3 to keep recommendation managable dec_tree_model = tree.DecisionTreeClassifier(random_state=32, max_depth = 3, class_weight = 'balanced') dec_tree_model = dec_tree_model.fit(X_train, y_train)
Наша модель получила приличную, но не идеальную AUC почти 0,8. (AUC — это способ измерения точности модели на основе показателей истинных и ложноположительных результатов. Чтобы узнать больше о показателях точности модели, ознакомьтесь с моим предыдущим блогом об оценке точности предсказанных результатов ESPN в фэнтези-футболе здесь.) Это достаточно респектабельно, чтобы мы могли продолжить упражнение. Конечно, существует несколько способов сделать классификатор дерева решений более точным, включая увеличение максимальной глубины, настройку гиперпараметров или запуск большего количества симуляций для увеличения количества данных.
from sklearn.metrics import roc_auc_score roc_auc_score(y_test, dec_tree_model.predict_proba(X_test)[:, 1])
Теперь, когда мы удовлетворены производительностью, мы можем визуально изучить дерево решений поезда. Каждое разделение в дереве представляет другое измерение набора бизнес-правил. В каждом блоке (или листе) напечатанного дерева первая строка будет представлять правило, используемое моделью для разделения данных, вторая строка — это индекс Джини, который описывает распределение классов в листе (где 0,5 представляет собой равное количество каждого класса, а 0 или 1 представляет только один класс), третья строка показывает количество образцов каждого класса, а четвертая строка показывает метку, которую модель присваивает всем образцам в этом листе. Мы можем распечатать полученное дерево ниже:
# Plot decision tree results to see how decisions were made import matplotlib.pyplot as plt fig = plt.figure(figsize = (14,14)) tree.plot_tree(dec_tree_model, filled = True, feature_names = X.columns, fontsize = 8, class_names = ['Las Vegas', 'Oakland']) plt.show()
Из нашего дерева решений, основанного на машинном обучении, мы видим, что классификация того, должны ли пятерки остаться в Окленде или переехать в Лас-Вегас, основывалась сначала на вероятности оптимистического дохода RSN, а затем на вероятностях, связанных с продажей билетов в Окленде.
Лас-Вегас, вероятно, предпочтительнее, если:
- Вероятность оптимистичной выручки RSN в Лас-Вегасе больше 0,4 (за исключением случаев, когда вероятность оптимистичной выручки RSN в Окленде больше 0,341 И вероятность оптимистичной продажи билетов в Окленде больше 0,355)
- ИЛИ вероятность оптимистичной выручки RSN в Окленде меньше или равна 0,468 И вероятность оптимистичной продажи билетов в Лас-Вегасе больше 0,438.
Интересно, что, несмотря на всю болтовню в СМИ о государственном или частном финансировании нового стадиона, наша модель указывает на доходы RSN и продажи билетов. Разница может быть связана с нашим 10-летним горизонтом или может быть связана с тем, что организация ищет одобренный MLB повод покинуть Окленд. В любом случае, этот подход выдвигает на первый план важную информацию, которую команда специалистов по данным может донести до лиц, принимающих решения, для информирования бизнес-стратегии. Подобные методы могут превратить вашу модель из интересного теоретического упражнения в изменение взглядов топ-менеджеров.
Как мы проверяем модель машинного обучения?
Учитывая, что мы пытаемся сообщить об очень важном решении, важно убедиться, что наша модель устойчива к различиям во входных данных или несбалансированному набору меток классов. Как вы заметите, для учета последнего мы включили class_weight = ‘balanced’ при создании нашей модели машинного обучения. Чтобы учесть первое и для проверки модели, мы можем использовать оценку перекрестной проверки, чтобы увидеть, какими будут другие показатели производительности разделения обучения/тестирования:
# 10-fold cross-validation scores cross_val_score(dec_tree_model, X, y, cv=10)
Вывод следующий: массив ([0,724, 0,722, 0,718, 0,72, 0,722, 0,708, 0,732, 0,726, 0,76, 0,702]), который говорит нам, что в 10 различных возможных разделениях обучения/тестирования наша модель имела одинаковую производительность.
Что мы узнали?
Таким образом, мы перешли от бизнес-вопроса о перемещении бейсбольной команды «А» к откатыванию модели дерева решений для анализа решений, чтобы выяснить, почему «А» могут отправиться в Лас-Вегас, к использованию дерева решений с машинным обучением для обобщения наших результатов в легко усваиваемые бизнес-правила, которые руководство может использовать, чтобы решить, следует ли перемещать компанию или нет. Надеюсь, вы сможете использовать подобную методологию или подход для информирования лиц, принимающих решения, в вашей организации или в повседневной жизни.
Рекомендации
[3] Ховард Р. и Аббас А. Основы анализа решений (2014 г.)
Считаете ли вы, что пятёрки должны остаться в Окленде? Переехать в Вегас? Может, попробовать другой город? Каков ваш опыт использования машинного обучения для метамоделирования.
Rukovodstvo
статьи и идеи для разработчиков программного обеспечения и веб-разработчиков.
Деревья принятия решений в Python с помощью Scikit-Learn
Введение. Дерево решений — один из наиболее часто и широко используемых алгоритмов контролируемого машинного обучения, который может выполнять задачи как регрессии, так и классификации. Интуиция, лежащая в основе алгоритма дерева решений, проста, но при этом очень эффективна. Для каждого атрибута в наборе данных алгоритм дерева решений [https://en.wikipedia.org/wiki/Decision_tree_learning] формирует узел, в котором наиболее важный атрибут помещается в корневой узел. Для оценки мы начинаем с корневого узла и работаем
Время чтения: 9 мин.
Вступление
Дерево решений — один из наиболее часто и широко используемых алгоритмов контролируемого машинного обучения, который может выполнять задачи как регрессии, так и классификации. Интуиция, лежащая в основе алгоритма дерева решений, проста, но при этом очень эффективна.
Для каждого атрибута в наборе данных алгоритм дерева решений формирует узел, в котором наиболее важный атрибут помещается в корневой узел. Для оценки мы начинаем с корневого узла и продвигаемся вниз по дереву, следуя за соответствующим узлом, который соответствует нашему условию или «решению». Этот процесс продолжается до тех пор, пока не будет достигнут конечный узел, содержащий прогноз или результат дерева решений.
Сначала это может показаться немного сложным, но вы, вероятно, не понимаете, что вы использовали деревья решений для принятия решений всю свою жизнь, даже не подозревая об этом. Рассмотрим сценарий, в котором человек просит вас одолжить ему машину на день, и вы должны решить, одолжить ли ему машину. Есть несколько факторов, которые помогают определить ваше решение, некоторые из них перечислены ниже:
- Этот человек — близкий друг или просто знакомый? Если человек просто знакомый, то отклоните запрос; если человек друг, переходите к следующему шагу.
- Человек впервые просит машину? Если да, одолжите им машину, в противном случае переходите к следующему шагу.
- Была ли машина повреждена при последнем возврате машины? Если да, отклоните запрос; если нет, одолжите им машину.
Дерево решений для вышеупомянутого сценария выглядит так:
Преимущества деревьев решений
Использование дерева решений для прогнозного анализа дает несколько преимуществ:
- Деревья решений могут использоваться для прогнозирования как непрерывных, так и дискретных значений, т.е. они хорошо работают как для задач регрессии, так и для классификации.
- Для их обучения требуется относительно меньше усилий.
- Их можно использовать для классификации нелинейно разделимых данных.
- Они очень быстрые и эффективные по сравнению с KNN и другими алгоритмами классификации.
Реализация деревьев решений с помощью Python Scikit Learn
В этом разделе мы реализуем алгоритм дерева решений с использованием библиотеки Python Scikit-Learn . В следующих примерах мы решим как классификационные, так и регрессионные задачи с помощью дерева решений.
Примечание . Задачи классификации и регрессии выполнялись в Jupyter iPython Notebook.
1. Схема принятия решений для классификации
В этом разделе мы предскажем, является ли банкнота подлинной или поддельной, в зависимости от четырех различных атрибутов изображения банкноты. Атрибуты — это дисперсия изображения, преобразованного вейвлетом, кратность изображения, энтропия и асимметрия изображения.
Набор данных
Набор данных для этой задачи можно скачать по этой ссылке:
Для получения более подробной информации об этом наборе данных ознакомьтесь с репозиторием UCI ML для этого набора данных.
Остальные шаги по реализации этого алгоритма в Scikit-Learn идентичны любой типичной задаче машинного обучения: мы импортируем библиотеки и наборы данных, проведем некоторый анализ данных, разделим данные на наборы для обучения и тестирования, обучим алгоритм, сделаем прогнозы, и, наконец, мы оценим производительность алгоритма на нашем наборе данных.
Импорт библиотек
Следующий скрипт импортирует необходимые библиотеки:
import pandas as pd import numpy as np import matplotlib.pyplot as plt %matplotlib inline
Импорт набора данных
Поскольку наш файл находится в формате CSV, мы будем использовать read_csv для чтения нашего файла данных CSV. Для этого выполните следующий сценарий:
dataset = pd.read_csv("D:/Datasets/bill_authentication.csv")
В этом случае файл bill_authentication.csv находится в папке «Datasets» на диске «D». Вы должны изменить этот путь в соответствии с настройками вашей собственной системы.
Анализ данных
Выполните следующую команду, чтобы увидеть количество строк и столбцов в нашем наборе данных:
dataset.shape
В выходных данных будет отображаться «(1372,5)», что означает, что в нашем наборе данных 1372 записи и 5 атрибутов.
Выполните следующую команду, чтобы проверить первые пять записей набора данных:
dataset.head()
Результат будет выглядеть так:
Дисперсия Асимметрия Куртоз Энтропия Класс
0 3,62160 8,6661 -2.8073 -0,44699 0 1 4,54590 8,1674 -2,4586 -1,46210 0 2 3,86600 -2,6383 1,9242 0,10645 0 3 3,45660 9,5228 -4,0112 -3,59440 0 4 0,32924 -4,4552 4,5718 -0,98880 0
Подготовка данных
В этом разделе мы разделим наши данные на атрибуты и метки, а затем разделим полученные данные на обучающие и тестовые наборы. Делая это, мы можем обучить наш алгоритм на одном наборе данных, а затем протестировать его на совершенно другом наборе данных, который алгоритм еще не видел. Это дает вам более точное представление о том, как на самом деле будет работать ваш обученный алгоритм.
Чтобы разделить данные на атрибуты и метки, выполните следующий код:
X = dataset.drop('Class', axis=1) y = dataset['Class']
Здесь X содержит все столбцы из набора данных, кроме столбца «Класс», который является меткой. y содержит значения из столбца «Класс». X — это наш набор атрибутов, а y содержит соответствующие метки.
Последний шаг предварительной обработки — разделить наши данные на обучающие и тестовые наборы. Библиотека model_selection Scikit-Learn содержит train_test_split , который мы будем использовать для случайного разделения данных на наборы для обучения и тестирования. Для этого выполните следующий код:
from sklearn.model_selection import train_test_split X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.20)
В приведенном выше test_size параметр test_size указывает соотношение набора тестов, которое мы используем для разделения 20% данных на набор тестов и 80% для обучения.
Обучение и прогнозирование
После того, как данные были разделены на наборы для обучения и тестирования, последний шаг — обучить алгоритм дерева решений на этих данных и сделать прогнозы. Scikit-Learn содержит tree библиотеку, которая содержит встроенные классы / методы для различных алгоритмов дерева решений. Поскольку здесь мы собираемся выполнить задачу классификации, мы будем использовать DecisionTreeClassifier для этого примера. Метод fit этого класса вызывается для обучения алгоритма на обучающих данных, которые передаются в качестве параметра методу fit Выполните следующий скрипт для обучения алгоритма:
from sklearn.tree import DecisionTreeClassifier classifier = DecisionTreeClassifier() classifier.fit(X_train, y_train)
Теперь, когда наш классификатор обучен, давайте сделаем прогнозы на основе тестовых данных. Для прогнозирования используется метод predict класса DecisionTreeClassifier Взгляните на следующий код для использования:
y_pred = classifier.predict(X_test)
Оценка алгоритма
На этом этапе мы обучили наш алгоритм и сделали некоторые прогнозы. Теперь посмотрим, насколько точен наш алгоритм. Для задач классификации часто используются такие показатели, как матрица неточностей , точность, отзыв и оценка F1 . К счастью для нас, библиотека metrics classification_report и confusion_matrix которые можно использовать для расчета этих показателей для нас:
from sklearn.metrics import classification_report, confusion_matrix print(confusion_matrix(y_test, y_pred)) print(classification_report(y_test, y_pred))
Это даст следующую оценку:
[[142 2] 2 129]] precision recall f1-score support 0 0.99 0.99 0.99 144 1 0.98 0.98 0.98 131 avg / total 0.99 0.99 0.99 275
Из матрицы неточностей видно, что из 275 тестовых примеров наш алгоритм неправильно классифицировал только 4. Это точность 98,5%. Не плохо!
2. Дерево решений для регрессии
Процесс решения проблемы регрессии с помощью дерева решений с использованием Scikit Learn очень похож на процесс классификации. Однако для регрессии мы используем класс DecisionTreeRegressor древовидной библиотеки. Матрицы оценки регрессии также отличаются от матриц классификации. В остальном процесс почти такой же.
Набор данных
Набор данных, который мы будем использовать в этом разделе, тот же, что мы использовали в статье о линейной регрессии. Мы будем использовать этот набор данных, чтобы попытаться спрогнозировать потребление газа (в миллионах галлонов) в 48 штатах США на основе налога на газ (в центах), дохода на душу населения (в долларах), асфальтированных дорог (в милях) и доли населения с водительское удостоверение.
Набор данных доступен по этой ссылке:
Подробную информацию о наборе данных можно найти в первоисточнике .
Первые два столбца в приведенном выше наборе данных не предоставляют никакой полезной информации, поэтому они были удалены из файла набора данных.
Теперь давайте применим наш алгоритм дерева решений к этим данным, чтобы попытаться предсказать потребление газа на основе этих данных.
Импорт библиотек
import pandas as pd import numpy as np import matplotlib.pyplot as plt %matplotlib inline
Импорт набора данных
dataset = pd.read_csv('D:\Datasets\petrol_consumption.csv')
Анализ данных
Мы снова будем использовать head фрейма данных, чтобы увидеть, как на самом деле выглядят наши данные:
dataset.head()
Результат выглядит так:
Бензин_налог Средний заработок Асфальтированные, шоссе Population_Driver_license (%) Бензин_Потребление
0 9.0 3571 1976 г. 0,525 541 1 9.0 4092 1250 0,572 524 2 9.0 3865 1586 0,580 561 3 7,5 4870 2351 0,529 414 4 8.0 4399 431 0,544 410
Чтобы просмотреть статистические данные набора данных, выполните следующую команду:
dataset.describe() Бензин_налог Средний заработок Асфальтированные, шоссе Population_Driver_license (%) Бензин_Потребление
считать 48,000000 48,000000 48,000000 48,000000 48,000000 иметь в виду 7,668333 4241.833333 5565.416667 0,570333 576.770833 стандартное 0,950770 573,623768 3491.507166 0,055470 111,885816 мин 5,000000 3063.000000 431,000000 0,451000 344,000000 25% 7,000000 3739.000000 3110.250000 0,529750 509 500 000 50% 7,500000 4298.000000 4735.500000 0,564500 568 500 000 75% 8,125 000 4578.750000 7156.000000 0,595250 632,750000 Максимум 10,00000 5342.000000 17782,000000 0,724000 986,000000
Подготовка данных
Как и в случае с задачей классификации, в этом разделе мы разделим наши данные на атрибуты и метки и, следовательно, на обучающие и тестовые наборы.
Выполните следующие команды, чтобы разделить данные на метки и атрибуты:
X = dataset.drop('Petrol_Consumption', axis=1) y = dataset['Petrol_Consumption']
Здесь X содержит все столбцы из набора данных, кроме столбца Petrol_Consuming, который является меткой. y содержит значения из столбца «Расход бензина», что означает, что X содержит набор атрибутов, а y содержит соответствующие метки.
Выполните следующий код, чтобы разделить наши данные на обучающий и тестовый наборы:
from sklearn.model_selection import train_test_split X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=0)
Обучение и прогнозирование
Как упоминалось ранее, для задачи регрессии мы будем использовать другой класс sklearn, чем для задачи классификации. Класс, который мы будем здесь использовать, — это DecisionTreeRegressor , в отличие от DecisionTreeClassifier ранее.
Чтобы обучить дерево, мы создадим экземпляр DecisionTreeRegressor и вызовем метод fit
from sklearn.tree import DecisionTreeRegressor regressor = DecisionTreeRegressor() regressor.fit(X_train, y_train)
Чтобы делать прогнозы на тестовом наборе, используется метод predict
y_pred = regressor.predict(X_test)
Теперь давайте сравним некоторые из наших предсказанных значений с фактическими значениями и посмотрим, насколько мы точны:
df=pd.DataFrame() df
Результат выглядит так:
Действительный Прогнозируемый
41 год 699 631,0 2 561 524,0 12 525 510,0 36 640 704,0 38 648 524,0 9 498 510,0 24 460 510,0 13 508 603,0 35 год 644 631,0
Помните, что в вашем случае сравниваемые записи могут отличаться в зависимости от разделения на обучение и тестирование. Поскольку train_test_split случайным образом разбивает данные, у нас, скорее всего, не будет одинаковых наборов для обучения и тестирования.
Оценка алгоритма
Для оценки производительности алгоритма регрессии обычно используются метрики: средняя абсолютная ошибка , среднеквадратичная ошибка и среднеквадратичная ошибка . Библиотека Scikit-Learn содержит функции, которые могут помочь нам вычислить эти значения. Для этого используйте этот код из пакета metrics
from sklearn import metrics print('Mean Absolute Error:', metrics.mean_absolute_error(y_test, y_pred)) print('Mean Squared Error:', metrics.mean_squared_error(y_test, y_pred)) print('Root Mean Squared Error:', np.sqrt(metrics.mean_squared_error(y_test, y_pred)))
Результат должен выглядеть примерно так:
Mean Absolute Error: 54.7 Mean Squared Error: 4228.9 Root Mean Squared Error: 65.0299930801
Средняя абсолютная ошибка для нашего алгоритма составляет 54,7, что составляет менее 10 процентов от среднего значения всех значений в столбце «Расход бензина». Это означает, что наш алгоритм отлично справился с прогнозированием.
Ресурсы
Хотите узнать больше о Scikit-Learn и других полезных алгоритмах машинного обучения? Я бы порекомендовал изучить более подробные ресурсы, например онлайн-курс:
- Учебный курс по Python для науки о данных и машинного обучения
- Машинное обучение, AZ: практический опыт Python и R в науке о данных
- Наука о данных в Python, Pandas, Scikit-learn, Numpy, Matplotlib
Заключение
В этой статье мы показали, как можно использовать популярную библиотеку Python Scikit-Learn для использования деревьев решений как для задач классификации, так и для задач регрессии. Хотя сам по себе алгоритм является довольно простым, реализация деревьев решений с помощью Scikit-Learn еще проще.
Licensed under CC BY-NC-SA 4.0
1.10. Деревья решений ¶
Деревья решений (DT) — это непараметрический контролируемый метод обучения, используемый для классификации и регрессии . Цель состоит в том, чтобы создать модель, которая предсказывает значение целевой переменной, изучая простые правила принятия решений, выведенные из характеристик данных. Дерево можно рассматривать как кусочно-постоянное приближение.
Например, в приведенном ниже примере деревья решений обучаются на основе данных, чтобы аппроксимировать синусоидальную кривую с набором правил принятия решений «если-то-еще». Чем глубже дерево, тем сложнее правила принятия решений и тем лучше модель.
Некоторые преимущества деревьев решений:
- Просто понять и интерпретировать. Деревья можно визуализировать.
- Требуется небольшая подготовка данных. Другие методы часто требуют нормализации данных, создания фиктивных переменных и удаления пустых значений. Однако обратите внимание, что этот модуль не поддерживает отсутствующие значения.
- Стоимость использования дерева (т. Е. Прогнозирования данных) является логарифмической по количеству точек данных, используемых для обучения дерева.
- Может обрабатывать как числовые, так и категориальные данные. Однако реализация scikit-learn пока не поддерживает категориальные переменные. Другие методы обычно специализируются на анализе наборов данных, содержащих только один тип переменных. См. Алгоритмы для получения дополнительной информации.
- Способен обрабатывать проблемы с несколькими выходами.
- Использует модель белого ящика. Если данная ситуация наблюдаема в модели, объяснение условия легко объяснить с помощью булевой логики. Напротив, в модели черного ящика (например, в искусственной нейронной сети) результаты могут быть труднее интерпретировать.
- Возможна проверка модели с помощью статистических тестов. Это позволяет учитывать надежность модели.
- Работает хорошо, даже если его предположения несколько нарушаются истинной моделью, на основе которой были сгенерированы данные.
К недостаткам деревьев решений можно отнести:
- Обучающиеся дереву решений могут создавать слишком сложные деревья, которые плохо обобщают данные. Это называется переобучением. Чтобы избежать этой проблемы, необходимы такие механизмы, как обрезка, установка минимального количества выборок, необходимых для конечного узла, или установка максимальной глубины дерева.
- Деревья решений могут быть нестабильными, поскольку небольшие изменения в данных могут привести к созданию совершенно другого дерева. Эта проблема смягчается за счет использования деревьев решений в ансамбле.
- Как видно из рисунка выше, предсказания деревьев решений не являются ни гладкими, ни непрерывными, а являются кусочно-постоянными приближениями. Следовательно, они не годятся для экстраполяции.
- Известно, что проблема обучения оптимальному дереву решений является NP-полной с точки зрения нескольких аспектов оптимальности и даже для простых концепций. Следовательно, практические алгоритмы обучения дереву решений основаны на эвристических алгоритмах, таких как жадный алгоритм, в котором локально оптимальные решения принимаются в каждом узле. Такие алгоритмы не могут гарантировать возврат глобального оптимального дерева решений. Это можно смягчить путем обучения нескольких деревьев в учащемся ансамбля, где функции и образцы выбираются случайным образом с заменой.
- Существуют концепции, которые трудно изучить, поскольку деревья решений не выражают их легко, например проблемы XOR, четности или мультиплексора.
- Ученики дерева решений создают предвзятые деревья, если некоторые классы доминируют. Поэтому рекомендуется сбалансировать набор данных перед подгонкой к дереву решений.
1.10.1. Классификация
DecisionTreeClassifier — это класс, способный выполнять мультиклассовую классификацию набора данных.
Как и в случае с другими классификаторами, DecisionTreeClassifier принимает в качестве входных данных два массива: массив X, разреженный или плотный, формы (n_samples, n_features), содержащий обучающие образцы, и массив Y целочисленных значений, формы (n_samples,), содержащий метки классов для обучающих образцов:
>>> from sklearn import tree >>> X = [[0, 0], [1, 1]] >>> Y = [0, 1] >>> clf = tree.DecisionTreeClassifier() >>> clf = clf.fit(X, Y)
После подбора модель можно использовать для прогнозирования класса образцов:
>>> clf.predict([[2., 2.]]) array([1])
В случае, если существует несколько классов с одинаковой и самой высокой вероятностью, классификатор предскажет класс с самым низким индексом среди этих классов.
В качестве альтернативы выводу определенного класса можно предсказать вероятность каждого класса, которая представляет собой долю обучающих выборок класса в листе:
>>> clf.predict_proba([[2., 2.]]) array([[0., 1.]])
DecisionTreeClassifier поддерживает как двоичную (где метки — [-1, 1]), так и мультиклассовую (где метки — [0,…, K-1]) классификацию.
Используя набор данных Iris, мы можем построить дерево следующим образом:
>>> from sklearn.datasets import load_iris >>> from sklearn import tree >>> iris = load_iris() >>> X, y = iris.data, iris.target >>> clf = tree.DecisionTreeClassifier() >>> clf = clf.fit(X, y)
После обучения вы можете построить дерево с помощью plot_tree функции:
>>> tree.plot_tree(clf)
Мы также можем экспортировать дерево в формат Graphviz с помощью export_graphviz экспортера. Если вы используете Conda менеджер пакетов, то Graphviz бинарные файлы и пакет питон может быть установлен conda install python-graphviz .
В качестве альтернативы двоичные файлы для graphviz можно загрузить с домашней страницы проекта graphviz, а оболочку Python установить из pypi с помощью pip install graphviz .
Ниже приведен пример экспорта graphviz вышеуказанного дерева, обученного на всем наборе данных радужной оболочки глаза; результаты сохраняются в выходном файле iris.pdf :
>>> import graphviz >>> dot_data = tree.export_graphviz(clf, out_file=None) >>> graph = graphviz.Source(dot_data) >>> graph.render("iris")
Экспортер export_graphviz также поддерживает множество эстетических вариантов, в том числе окраски узлов их класс (или значение регрессии) и используя явные имена переменных и классов , если это необходимо. Блокноты Jupyter также автоматически отображают эти графики встроенными:
>>> dot_data = tree.export_graphviz(clf, out_file=None, . feature_names=iris.feature_names, . class_names=iris.target_names, . filled=True, rounded=True, . special_characters=True) >>> graph = graphviz.Source(dot_data) >>> graph
В качестве альтернативы дерево можно также экспортировать в текстовый формат с помощью функции export_text . Этот метод не требует установки внешних библиотек и более компактен:
>>> from sklearn.datasets import load_iris >>> from sklearn.tree import DecisionTreeClassifier >>> from sklearn.tree import export_text >>> iris = load_iris() >>> decision_tree = DecisionTreeClassifier(random_state=0, max_depth=2) >>> decision_tree = decision_tree.fit(iris.data, iris.target) >>> r = export_text(decision_tree, feature_names=iris['feature_names']) >>> print(r) |--- petal width (cm) 0.80 | |--- petal width (cm) 1.75 | | |--- class: 2
- Постройте поверхность принятия решений дерева решений на наборе данных радужной оболочки глаза
- Понимание структуры дерева решений
1.10.2. Регрессия
Деревья решений также могут применяться к задачам регрессии с помощью класса DecisionTreeRegressor .
Как и в настройке классификации, метод fit будет принимать в качестве аргументов массивы X и y, только в этом случае ожидается, что y будет иметь значения с плавающей запятой вместо целочисленных значений:
>>> from sklearn import tree >>> X = [[0, 0], [2, 2]] >>> y = [0.5, 2.5] >>> clf = tree.DecisionTreeRegressor() >>> clf = clf.fit(X, y) >>> clf.predict([[1, 1]]) array([0.5])
1.10.3. Проблемы с несколькими выходами
Задача с несколькими выходами — это проблема контролируемого обучения с несколькими выходами для прогнозирования, то есть когда Y — это 2-й массив формы (n_samples, n_outputs) .
Когда нет корреляции между выходами, очень простой способ решить эту проблему — построить n независимых моделей, то есть по одной для каждого выхода, а затем использовать эти модели для независимого прогнозирования каждого из n выходов. Однако, поскольку вполне вероятно, что выходные значения, относящиеся к одному и тому же входу, сами коррелированы, часто лучшим способом является построение единой модели, способной прогнозировать одновременно все n выходов. Во-первых, это требует меньшего времени на обучение, поскольку строится только один оценщик. Во-вторых, часто можно повысить точность обобщения итоговой оценки.
Что касается деревьев решений, эту стратегию можно легко использовать для поддержки задач с несколькими выходами. Для этого требуются следующие изменения:
- Сохранять n выходных значений в листьях вместо 1;
- Используйте критерии разделения, которые вычисляют среднее сокращение для всех n выходов.
Этот модуль предлагает поддержку для задач с несколькими выходами, реализуя эту стратегию как в, так DecisionTreeClassifier и в DecisionTreeRegressor . Если дерево решений соответствует выходному массиву Y формы (n_samples, n_outputs), то итоговая оценка будет:
- Вывести значения n_output при predict ;
- Выведите список массивов n_output вероятностей классов на predict_proba .
Использование деревьев с несколькими выходами для регрессии продемонстрировано в разделе «Регрессия дерева решений с несколькими выходами» . В этом примере вход X — это одно действительное значение, а выходы Y — синус и косинус X.
Использование деревьев с несколькими выходами для классификации демонстрируется в разделе «Завершение лица с оценками с несколькими выходами» . В этом примере входы X — это пиксели верхней половины граней, а выходы Y — пиксели нижней половины этих граней.
- Регрессия дерева решений с несколькими выходами
- Завершение лица с помощью многовыходных оценщиков
- М. Дюмон и др., Быстрая мультиклассовая аннотация изображений со случайными подокнами и множественными выходными рандомизированными деревьями , Международная конференция по теории и приложениям компьютерного зрения, 2009 г.
1.10.4. Сложность
В общем, время выполнения для построения сбалансированного двоичного дерева составляет $O(n_n_\log(n_))$ и время запроса $O(\log(n_))$. Хотя алгоритм построения дерева пытается генерировать сбалансированные деревья, они не всегда будут сбалансированными. Предполагая, что поддеревья остаются примерно сбалансированными, стоимость на каждом узле состоит из перебора $O(n_)$ найти функцию, обеспечивающую наибольшее снижение энтропии. Это стоит $O(n_n_\log(n_))$ на каждом узле, что приводит к общей стоимости по всем деревьям (суммируя стоимость на каждом узле) $O(n_n_^\log(n_))$
1.10.5. Советы по практическому использованию
- Деревья решений имеют тенденцию чрезмерно соответствовать данным с большим количеством функций. Получение правильного соотношения образцов к количеству функций важно, поскольку дерево с небольшим количеством образцов в многомерном пространстве, скорее всего, переоборудуется.
- Предварительно рассмотрите возможность уменьшения размерности (PCA, ICA, или Feature selection), чтобы дать вашему дереву больше шансов найти отличительные признаки.
- Понимание структуры дерева решений поможет лучше понять, как дерево решений делает прогнозы, что важно для понимания важных функций данных.
- Визуализируйте свое дерево во время тренировки с помощью export функции. Используйте max_depth=3 в качестве начальной глубины дерева, чтобы понять, насколько дерево соответствует вашим данным, а затем увеличьте глубину.
- Помните, что количество образцов, необходимых для заполнения дерева, удваивается для каждого дополнительного уровня, до которого дерево растет. Используйте max_depth для управления размером дерева во избежание переобучения.
- Используйте min_samples_split или, min_samples_leaf чтобы гарантировать, что несколько выборок информируют каждое решение в дереве, контролируя, какие разделения будут учитываться. Очень маленькое число обычно означает, что дерево переоборудуется, тогда как большое число не позволяет дереву изучать данные. Попробуйте min_samples_leaf=5 в качестве начального значения. Если размер выборки сильно различается, в этих двух параметрах можно использовать число с плавающей запятой в процентах. В то время как min_samples_split может создавать произвольно маленькие листья, min_samples_leaf гарантирует, что каждый лист имеет минимальный размер, избегая малодисперсных, чрезмерно подходящих листовых узлов в задачах регрессии. Для классификации с несколькими классами min_samples_leaf=1 это часто лучший выбор.
1.10.6. Алгоритмы дерева: ID3, C4.5, C5.0 и CART
Что представляют собой различные алгоритмы дерева решений и чем они отличаются друг от друга? Какой из них реализован в scikit-learn?
ID3 (Iterative Dichotomiser 3) был разработан Россом Куинланом в 1986 году. Алгоритм создает многостороннее дерево, находя для каждого узла (т. Е. Жадным образом) категориальный признак, который даст наибольший информационный выигрыш для категориальных целей. Деревья вырастают до максимального размера, а затем обычно применяется этап обрезки, чтобы улучшить способность дерева обобщать невидимые данные.
C4.5 является преемником ID3 и снял ограничение, что функции должны быть категориальными, путем динамического определения дискретного атрибута (на основе числовых переменных), который разбивает непрерывное значение атрибута на дискретный набор интервалов. C4.5 преобразует обученные деревья (т. Е. Результат алгоритма ID3) в наборы правил «если-то». Затем оценивается точность каждого правила, чтобы определить порядок, в котором они должны применяться. Удаление выполняется путем удаления предусловия правила, если без него точность правила улучшается.
C5.0 — это последняя версия Quinlan под частной лицензией. Он использует меньше памяти и создает меньшие наборы правил, чем C4.5, но при этом является более точным.
CART (Classification and Regression Trees — деревья классификации и регрессии) очень похож на C4.5, но отличается тем, что поддерживает числовые целевые переменные (регрессию) и не вычисляет наборы правил. CART строит двоичные деревья, используя функцию и порог, которые дают наибольший прирост информации в каждом узле.
scikit-learn использует оптимизированную версию алгоритма CART; однако реализация scikit-learn пока не поддерживает категориальные переменные.
1.10.7. Математическая постановка
Данные обучающие векторы $x_i \in R^n$, i = 1,…, l и вектор-метка $y \in R^l$ дерево решений рекурсивно разбивает пространство признаков таким образом, что образцы с одинаковыми метками или аналогичными целевыми значениями группируются вместе.
Пусть данные в узле m быть представлен $Q_m$ с участием $N_m$ образцы. Для каждого раскола кандидатов $\theta = (j, t_m)$ состоящий из функции $j$ и порог $t_m$, разделите данные на $Q_m^(\theta)$ а также $Q_m^(\theta)$ подмножества
$$Q_m^(\theta) = <(x, y) | x_j <= t_m>$$
$$Q_m^(\theta) = Q_m \setminus Q_m^(\theta)$$
Качество кандидата разделения узла $m$ затем вычисляется с использованием функции примеси или функции потерь $H()$, выбор которых зависит от решаемой задачи (классификация или регрессия)
$$G(Q_m, \theta) = \frac> H(Q_m^(\theta)) + \frac> H(Q_m^(\theta))$$
Выберите параметры, которые минимизируют примеси
$$\theta^* = \operatorname_\theta G(Q_m, \theta)$$
Рекурсия для подмножеств $Q_m^(\theta^*)$ а также $Q_m^(\theta^*)$ пока не будет достигнута максимально допустимая глубина, $N_m < \min_$ или же $N_m = 1$.
1.10.7.1. Критерии классификации
Если целью является результат классификации, принимающий значения 0,1,…, K-1, для узла m, позволять
$$p_ = 1/ N_m \sum_ I(y = k)$$
быть пропорцией наблюдений класса k в узле m. Еслиmявляется конечным узлом, predict_proba для этого региона установлено значение $p_$. Общие меры примеси следующие.
Энтропия:
$$H(Q_m) = — \sum_k p_ \log(p_)$$
Неверная классификация:
$$H(Q_m) = 1 — \max(p_)$$
1.10.7.2. Критерии регрессии
Если целью является непрерывное значение, то для узла m, общими критериями, которые необходимо минимизировать для определения местоположений будущих разделений, являются среднеквадратичная ошибка (ошибка MSE или L2), отклонение Пуассона, а также средняя абсолютная ошибка (ошибка MAE или L1). MSE и отклонение Пуассона устанавливают прогнозируемое значение терминальных узлов равным изученному среднему значению $\bar_m$ узла, тогда как MAE устанавливает прогнозируемое значение терминальных узлов равным медиане $median(y)_m$.
Половинное отклонение Пуассона:
$$H(Q_m) = \frac \sum_ (y \log\frac<\bar_m> — y + \bar_m)$$
Настройка criterion=»poisson» может быть хорошим выбором, если ваша цель — счетчик или частота (количество на какую-то единицу). В любом случае, y>=0 является необходимым условием для использования этого критерия. Обратите внимание, что он подходит намного медленнее, чем критерий MSE.
Обратите внимание, что он подходит намного медленнее, чем критерий MSE.
1.10.8. Обрезка с минимальными затратами и сложностью
Сокращение с минимальными затратами и сложностью — это алгоритм, используемый для сокращения дерева во избежание чрезмерной подгонки, описанный в главе 3 [BRE] . Этот алгоритм параметризован $\alpha\ge0$ известный как параметр сложности. Параметр сложности используется для определения меры затрат и сложности, $R_\alpha(T)$ данного дерева $T$:
$$R_\alpha(T) = R(T) + \alpha|\widetilde|$$
где $|\widetilde|$ количество конечных узлов в $T$ а также $R(T)$ традиционно определяется как общий коэффициент ошибочной классификации конечных узлов. В качестве альтернативы scikit-learn использует взвешенную общую примесь конечных узлов для $R(T)$. Как показано выше, примесь узла зависит от критерия. Обрезка с минимальными затратами и сложностью находит поддеревоT что сводит к минимуму $R_\alpha(T)$.
Оценка сложности стоимости одного узла составляет $R_\alpha(t)=R(t)+\alpha$. Ответвление $T_t$, определяется как дерево, в котором узел $t$ это его корень. В общем, примесь узла больше, чем сумма примесей его конечных узлов, $R(T_t)(t)=\frac<|T|-1>$. Нетерминальный узел с наименьшим значением $\alpha_$ является самым слабым звеном и будет удалено. Этот процесс останавливается, когда обрезанное дерево минимально $\alpha_$ больше ccp_alpha параметра.
- BRE Л. Брейман, Дж. Фридман, Р. Олшен и К. Стоун. Деревья классификации и регрессии. Уодсворт, Белмонт, Калифорния, 1984.
- https://en.wikipedia.org/wiki/Decision_tree_learning
- https://en.wikipedia.org/wiki/Predictive_analytics
- JR Quinlan. C4. 5: программы для машинного обучения. Морган Кауфманн, 1993.
- Т. Хасти, Р. Тибширани и Дж. Фридман. Элементы статистического обучения, Springer, 2009.
Если вы хотите помочь проекту с переводом, то можно обращаться по следующему адресу support@scikit-learn.ru
© 2007 — 2020, scikit-learn developers (BSD License).