Выберите корневой атрибут дерева

Добавил пользователь Владимир З.
Обновлено: 19.09.2024

Аннотация: Описывается метод деревьев решений. Рассматриваются элементы дерева решения, процесс его построения. Приведены примеры деревьев, решающих задачу классификации. Даны алгоритмы конструирования деревьев решений CART и C4.5.

Метод деревьев решений ( decision trees ) является одним из наиболее популярных методов решения задач классификации и прогнозирования. Иногда этот метод Data Mining также называют деревьями решающих правил , деревьями классификации и регрессии.

Как видно из последнего названия, при помощи данного метода решаются задачи классификации и прогнозирования.

Если зависимая, т.е. целевая переменная принимает дискретные значения, при помощи метода дерева решений решается задача классификации.

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

Впервые деревья решений были предложены Ховилендом и Хантом (Hoveland, Hunt) в конце 50-х годов прошлого века. Самая ранняя и известная работа Ханта и др., в которой излагается суть деревьев решений - "Эксперименты в индукции" ("Experiments in Induction ") - была опубликована в 1966 году.

В наиболее простом виде дерево решений - это способ представления правил в иерархической, последовательной структуре. Основа такой структуры - ответы "Да" или "Нет" на ряд вопросов.

На рис. 9.1 приведен пример дерева решений, задача которого - ответить на вопрос: "Играть ли в гольф?" Чтобы решить задачу, т.е. принять решение, играть ли в гольф, следует отнести текущую ситуацию к одному из известных классов (в данном случае - "играть" или "не играть"). Для этого требуется ответить на ряд вопросов, которые находятся в узлах этого дерева, начиная с его корня.

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

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

Целью построения дерева решения в нашем случае является определение значения категориальной зависимой переменной.

Итак, для нашей задачи основными элементами дерева решений являются:

Корень дерева: "Солнечно?"

Внутренний узел дерева или узел проверки : "Температура воздуха высокая?", "Идет ли дождь?"

Лист , конечный узел дерева, узел решения или вершина : "Играть", "Не играть"

Ветвь дерева (случаи ответа): "Да", "Нет".

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

Рассмотрим более сложный пример. База данных , на основе которой должно осуществляться прогнозирование, содержит следующие ретроспективные данные о клиентах банка, являющиеся ее атрибутами: возраст, наличие недвижимости, образование, среднемесячный доход, вернул ли клиент вовремя кредит . Задача состоит в том, чтобы на основании перечисленных выше данных (кроме последнего атрибута) определить, стоит ли выдавать кредит новому клиенту.

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

На этапе построения модели, собственно, и строится дерево классификации или создается набор неких правил . На этапе использования модели построенное дерево , или путь от его корня к одной из вершин, являющийся набором правил для конкретного клиента, используется для ответа на поставленный вопрос "Выдавать ли кредит ?"

Правилом является логическая конструкция, представленная в виде "если : то :".

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

Как мы видим, внутренние узлы дерева (возраст, наличие недвижимости, доход и образование) являются атрибутами описанной выше базы данных . Эти атрибуты называют прогнозирующими, или атрибутами расщепления (splitting attribute ). Конечные узлы дерева, или листы, именуются метками класса, являющимися значениями зависимой категориальной переменной "выдавать" или "не выдавать" кредит .

Каждая ветвь дерева, идущая от внутреннего узла , отмечена предикатом расщепления . Последний может относиться лишь к одному атрибуту расщепления данного узла. Характерная особенность предикатов расщепления : каждая запись использует уникальный путь от корня дерева только к одному узлу-решению. Объединенная информация об атрибутах расщепления и предикатах расщепления в узле называется критерием расщепления (splitting criterion ) [33].

На рис. 9.2. изображено одно из возможных деревьев решений для рассматриваемой базы данных . Например, критерий расщепления "Какое образование?", мог бы иметь два предиката расщепления и выглядеть иначе: образование "высшее" и "не высшее". Тогда дерево решений имело бы другой вид.

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

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

Метод деревьев решений часто называют "наивным" подходом [34]. Но благодаря целому ряду преимуществ, данный метод является одним из наиболее популярных для решения задач классификации.

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

Некоторые преимущества деревьев решений:

Просто понять и интерпретировать. Деревья можно визуализировать.
Требуется небольшая подготовка данных. Другие методы часто требуют нормализации данных, создания фиктивных переменных и удаления пустых значений. Однако обратите внимание, что этот модуль не поддерживает отсутствующие значения.
Стоимость использования дерева (т. Е. Прогнозирования данных) является логарифмической по количеству точек данных, используемых для обучения дерева.
Может обрабатывать как числовые, так и категориальные данные. Однако реализация scikit-learn пока не поддерживает категориальные переменные. Другие методы обычно специализируются на анализе наборов данных, содержащих только один тип переменных. См. Алгоритмы для получения дополнительной информации.
Способен обрабатывать проблемы с несколькими выходами.
Использует модель белого ящика. Если данная ситуация наблюдаема в модели, объяснение условия легко объяснить с помощью булевой логики. Напротив, в модели черного ящика (например, в искусственной нейронной сети) результаты могут быть труднее интерпретировать.
Возможна проверка модели с помощью статистических тестов. Это позволяет учитывать надежность модели.
Работает хорошо, даже если его предположения несколько нарушаются истинной моделью, на основе которой были сгенерированы данные.

К недостаткам деревьев решений можно отнести:

Обучающиеся дереву решений могут создавать слишком сложные деревья, которые плохо обобщают данные. Это называется переобучением. Чтобы избежать этой проблемы, необходимы такие механизмы, как обрезка, установка минимального количества выборок, необходимых для конечного узла, или установка максимальной глубины дерева.
Деревья решений могут быть нестабильными, поскольку небольшие изменения в данных могут привести к созданию совершенно другого дерева. Эта проблема смягчается за счет использования деревьев решений в ансамбле.
Как видно из рисунка выше, предсказания деревьев решений не являются ни гладкими, ни непрерывными, а являются кусочно-постоянными приближениями. Следовательно, они не годятся для экстраполяции.
Известно, что проблема обучения оптимальному дереву решений является NP-полной с точки зрения нескольких аспектов оптимальности и даже для простых концепций. Следовательно, практические алгоритмы обучения дереву решений основаны на эвристических алгоритмах, таких как жадный алгоритм, в котором локально оптимальные решения принимаются в каждом узле. Такие алгоритмы не могут гарантировать возврат глобального оптимального дерева решений. Это можно смягчить путем обучения нескольких деревьев в учащемся ансамбля, где функции и образцы выбираются случайным образом с заменой.
Существуют концепции, которые трудно изучить, поскольку деревья решений не выражают их легко, например проблемы XOR, четности или мультиплексора.
Ученики дерева решений создают предвзятые деревья, если некоторые классы доминируют. Поэтому рекомендуется сбалансировать набор данных перед подгонкой к дереву решений.

1.10.1. Классификация

DecisionTreeClassifier — это класс, способный выполнять мультиклассовую классификацию набора данных.

Как и в случае с другими классификаторами, DecisionTreeClassifier принимает в качестве входных данных два массива: массив X, разреженный или плотный, формы (n_samples, n_features), содержащий обучающие образцы, и массив Y целочисленных значений, формы (n_samples,), содержащий метки классов для обучающих образцов:

После подбора модель можно использовать для прогнозирования класса образцов:

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

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

DecisionTreeClassifier поддерживает как двоичную (где метки — [-1, 1]), так и мультиклассовую (где метки — [0,…, K-1]) классификацию.

Используя набор данных Iris, мы можем построить дерево следующим образом:

После обучения вы можете построить дерево с помощью plot_tree функции:

Мы также можем экспортировать дерево в формат Graphviz с помощью export_graphviz экспортера. Если вы используете Conda менеджер пакетов, то Graphviz бинарные файлы и пакет питон может быть установлен conda install python-graphviz .

В качестве альтернативы двоичные файлы для graphviz можно загрузить с домашней страницы проекта graphviz, а оболочку Python установить из pypi с помощью pip install graphviz .

Ниже приведен пример экспорта graphviz вышеуказанного дерева, обученного на всем наборе данных радужной оболочки глаза; результаты сохраняются в выходном файле iris.pdf :

Экспортер export_graphviz также поддерживает множество эстетических вариантов, в том числе окраски узлов их класс (или значение регрессии) и используя явные имена переменных и классов , если это необходимо. Блокноты Jupyter также автоматически отображают эти графики встроенными:

В качестве альтернативы дерево можно также экспортировать в текстовый формат с помощью функции export_text . Этот метод не требует установки внешних библиотек и более компактен:

1.10.2. Регрессия

Деревья решений также могут применяться к задачам регрессии с помощью класса DecisionTreeRegressor .

Как и в настройке классификации, метод fit будет принимать в качестве аргументов массивы X и y, только в этом случае ожидается, что y будет иметь значения с плавающей запятой вместо целочисленных значений:

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 .

М. Дюмон и др., Быстрая мультиклассовая аннотация изображений со случайными подокнами и множественными выходными рандомизированными деревьями , Международная конференция по теории и приложениям компьютерного зрения, 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 году. Алгоритм создает многостороннее дерево, находя для каждого узла (т. Е. Жадным образом) категориальный признак, который даст наибольший информационный выигрыш для категориальных целей. Деревья вырастают до максимального размера, а затем обычно применяется этап обрезки, чтобы улучшить способность дерева обобщать невидимые данные.

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 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) ccp_alpha параметра.

Общий принцип построения деревьев решений был дан в статье "Деревья решений – основные принципы работы".

В этой статье речь пойдет об алгоритме CART. CART, сокращение от Classification And Regression Tree, переводится как "Дерево Классификации и регрессии" – алгоритм бинарного дерева решений, впервые опубликованный Бриманом и др. в 1984 году [1]. Алгоритм предназначен для решения задач классификации и регрессии. Существует также несколько модифицированных версий – алгоритмы IndCART и DB-CART. Алгоритм IndCART, является частью пакета Ind и отличается от CART использованием иного способа обработки пропущенных значений, не осуществляет регрессионную часть алгоритма CART и имеет иные параметры отсечения. Алгоритм DB-CART базируется на следующей идее: вместо того чтобы использовать обучающий набор данных для определения разбиений, используем его для оценки распределения входных и выходных значений и затем используем эту оценку, чтобы определить разбиения. DB, соответственно означает – "distribution based". Утверждается, что эта идея дает значительное уменьшение ошибки классификации, по сравнению со стандартными методами построения дерева. Основными отличиями алгоритма CART от алгоритмов семейства ID3 являются:

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

Бинарное представление дерева решений

В алгоритме CART каждый узел дерева решений имеет двух потомков. На каждом шаге построения дерева правило, формируемое в узле, делит заданное множество примеров (обучающую выборку) на две части – часть, в которой выполняется правило (потомок – right) и часть, в которой правило не выполняется (потомок – left). Для выбора оптимального правила используется функция оценки качества разбиения.

Предлагаемое алгоритмическое решение.

Оно вполне очевидно. Каждый узел (структура или класс) должен иметь ссылки на двух потомков Left и Right – аналогичные структуры. Также узел должен содержать идентификатор правила (подробнее о правилах см. ниже), каким либо образом описывать правую часть правила, содержать информацию о количестве или отношении примеров каждого класса обучающей выборки "прошедшей" через узел и иметь признак терминального узла – листа. Таковы минимальные требования к структуре (классу) узла дерева.

Функция оценки качества разбиения

Обучение дерева решений относится к классу обучения с учителем, то есть обучающая и тестовая выборки содержат классифицированный набор примеров. Оценочная функция, используемая алгоритмом CART, базируется на интуитивной идее уменьшения нечистоты (неопределённости) в узле. Рассмотрим задачу с двумя классами и узлом, имеющим по 50 примеров одного класса. Узел имеет максимальную "нечистоту". Если будет найдено разбиение, которое разбивает данные на две подгруппы 40:5 примеров в одной и 10:45 в другой, то интуитивно "нечистота" уменьшится. Она полностью исчезнет, когда будет найдено разбиение, которое создаст подгруппы 50:0 и 0:50. В алгоритме CART идея "нечистоты" формализована в индексе Gini. Если набор данных Т содержит данные n классов, тогда индекс Gini определяется как:

$Gini\,(T) = 1 - \sum\limits_^\ p_i^2$ ,

где p_i – вероятность (относительная частота) класса i в T.

Если набор Т разбивается на две части Т₁ и Т₂ с числом примеров в каждом N₁ и N₂ соответственно, тогда показатель качества разбиения будет равен:

Наилучшим считается то разбиение, для которого Gini_split(T) минимально.

Обозначим N – число примеров в узле – предке, L, R – число примеров соответственно в левом и правом потомке, l_i и r_i – число экземпляров i-го класса в левом/правом потомке. Тогда качество разбиения оценивается по следующей формуле:

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

Так как умножение на константу не играет роли при минимизации:

В итоге, лучшим будет то разбиение, для которого величина максимальна. Реже в алгоритме CART используются другие критерии разбиения Twoing, Symmetric Gini и др., подробнее см. [1].

Правила разбиения

Вектор предикторных переменных, подаваемый на вход дерева может содержать как числовые (порядковые) так и категориальные переменные. В любом случае в каждом узле разбиение идет только по одной переменной. Если переменная числового типа, то в узле формируется правило вида x_i n-1 – 1). На каждом шаге построения дерева алгоритм последовательно сравнивает все возможные разбиения для всех атрибутов и выбирает наилучший атрибут и наилучшее разбиение для него.

Предлагаемое алгоритмическое решение.

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

Каждый шаг построения дерева фактически состоит из совокупности трех трудоемких операций.

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

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

Обе этих операции связаны (если действовать напрямую) с перемещением значительных объемов памяти. Здесь намеренно источник данных не называется таблицей, так как можно существенно снизить временные затраты на построение дерева, если использовать индексированный источник данных. Обращение к данным в таком источнике происходит не напрямую, а посредством логических индексов строк данных. Сортировать и разделять такой источник можно с минимальной потерей производительности.

Третья операция, занимающая 60–80% времени выполнения программы – вычисление индексов для всех возможных разбиений. Если у Вас n – числовых атрибутов и m – примеров в выборке, то получается таблица n*(m-1) – индексов, которая занимает большой объем памяти. Этого можно избежать, если использовать один столбец для текущего атрибута и одну строку для лучших (максимальных) индексов для всех атрибутов. Можно и вовсе использовать только несколько числовых значений, получив быстрый, однако плохо читаемый код. Значительно увеличить производительность можно, если использовать, что L = N – R, l_i – r_i , а l_i и r_i изменяются всегда и только на единицу при переходе на следующую строку для текущего атрибута. То есть подсчет числа классов, а это основная операция, будет выполняться быстро, если знать число экземпляров каждого класса всего в таблице и при переходе на новую строку таблицы изменять на единицу только число экземпляров одного класса – класса текущего примера.

Все возможные разбиения для категориальных атрибутов удобно представлять по аналогии с двоичным представлением числа. Если атрибут имеет n – уникальных значений. 2 n – разбиений. Первое (где все нули) и последнее (все единицы) нас не интересуют, получаем 2 n – 2. И так как порядок множеств здесь тоже неважен, получаем (2 n – 2)/2 или (2 n-1 – 1) первых (с единицы) двоичных представлений. Если – все возможные значения некоторого атрибута X, то для текущего разбиения, которое имеет представление, скажем получаем правило X in для правой ветви и [ not = = X in ] для левой ветви.

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

Механизм отсечения дерева

Механизм отсечения дерева, оригинальное название minimal cost-complexity tree pruning, – наиболее серьезное отличие алгоритма CART от других алгоритмов построения дерева. CART рассматривает отсечение как получение компромисса между двумя проблемами: получение дерева оптимального размера и получение точной оценки вероятности ошибочной классификации.

Основная проблема отсечения – большое количество всех возможных отсеченных поддеревьев для одного дерева. Более точно, если бинарное дерево имеет |T| – листов, тогда существует ~[1.5028369 |T| ] отсечённых поддеревьев. И если дерево имеет хотя бы 1000 листов, тогда число отсечённых поддеревьев становится просто огромным.

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

Обозначим |T| – число листов дерева, R(T) – ошибка классификации дерева, равная отношению числа неправильно классифицированных примеров к числу примеров в обучающей выборке. Определим $C_\,(T)$ – полную стоимость (оценку/показатель затраты-сложность) дерева Т как:

$C_\,(T) = R\,(T)\,+\,\alpha\,*\,|T|$, где |T| – число листов (терминальных узлов) дерева, – некоторый параметр, изменяющийся от 0 до + $\infty$. Полная стоимость дерева состоит из двух компонент – ошибки классификации дерева и штрафа за его сложность. Если ошибка классификации дерева неизменна, тогда с увеличением полная стоимость дерева будет увеличиваться. Тогда в зависимости от менее ветвистое дерево, дающее бОльшую ошибку классификации может стоить меньше, чем дающее меньшую ошибку, но более ветвистое.

Определим T_max – максимальное по размеру дерево, которое предстоит обрезать. Если мы зафиксируем значение $\alpha$, тогда существует наименьшее минимизируемое поддерево $\alpha$, которое выполняет следующие условия:

$C_\Bigl(T\,(\alpha)\Bigr) = min_>\,C_(T)$
$if\,\,C_\,(T) = C_\Bigl(T\,(\alpha)\Bigr)\,then\,\,T\,(\alpha)\leq\,T$

Первое условие говорит, что не существует такого поддерева дерева T_max , которое имело бы меньшую стоимость, чем $T\,(\alpha)$ при этом значении $\alpha$. Второе условие говорит, что если существует более одного поддерева, имеющего данную полную стоимость, тогда мы выбираем наименьшее дерево.

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

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

(где t₁ – корневой узел дерева) такую, что T_k – наименьшее минимизируемое поддерево для $[\alpha_k,\,\alpha_)$. Это важный результат, так как это означает, что мы можем получить следующее дерево в последовательности, применив отсечение к текущему дереву. Это позволяет разработать эффективный алгоритм поиска наименьшего минимизируемого поддерева при различных значениях $\alpha$. Первое дерево в этой последовательности – наименьшее поддерево дерева T_max имеющее такую же ошибку классификации, как и T_max, т.е. $T_1 = T(\alpha=0)$. Пояснение: если разбиение идет до тех пор, пока в каждом узле останется только один класс, то T₁ = T_max, но так как часто применяются методы ранней остановки (prepruning), тогда может существовать поддерево дерева T_max имеющее такую же ошибку классификации.

Предлагаемое алгоритмическое решение.

Алгоритм вычисления T₁ из T_max прост. Найти любую пару листов с общим предком, которые могут быть объединены, т.е. отсечены в родительский узел без увеличения ошибки классификации. R(t) = R(l) + R(r), где r и l – листы узла t. Продолжать пока таких пар больше не останется. Так мы получим дерево, имеющее такую же стоимость как T_max при = 0, но менее ветвистое, чем T_max.

Как мы получаем следующее дерево в последовательности и соответствующее значение $\alpha$? Обозначим T_t – ветвь дерева Т с корневым узлом t. При каких значениях дерево T – T_t будет лучше, чем Т? Если мы отсечём в узле t, тогда его вклад в полную стоимость дерева T – T_t станет $C_(\) = R\,(t)\,+\,\alpha$, где R(t) = r(t)* p(t), r(t) – это ошибка классификации узла t и p(t) – пропорция случаев, которые "прошли" через узел t. Альтернативный вариант: R(t)= m/n, где m – число примеров классифицированных некорректно, а n – общее число классифицируемых примеров для всего дерева.

Вклад T_t в полную стоимость дерева Т составит $C_(T_t) = R\,(T_t)\,+\,\alpha\,|T_t|$, где

Дерево T – T_t будет лучше, чем Т, когда $C_\<(t\>) = C_\,(T_t)$, потому что при этой величине они имеют одинаковую стоимость, но T – T_t наименьшее из двух. Когда $C_\<(t\>) = C_\,(T_t)$ мы получаем:

решая для $\alpha$, получаем:

Так для любого узла t в Т₁ ,если мы увеличиваем $\alpha$, тогда когда

дерево, полученное отсечением в узле t, будет лучше, чем Т₁.

Основная идея состоит в следующем: вычислим это значение для каждого узла в дереве Т₁, и затем выберем "слабые связи" (их может быть больше чем одна), т.е. узлы для которых величина

является наименьшей. Мы отсекаем Т₁ в этих узлах, чтобы получить Т₂ – следующее дерево в последовательности. Затем мы продолжаем этот процесс для полученного дерева и так пока мы не получим корневой узел (дерево в котором только один узел).

Алгоритм вычисления последовательности деревьев.

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

Рассмотрим метод подробнее на примере.

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

Очевидно, что Т₁ = Т_max , так как все листы содержат примеры одного класса и отсечение любого узла (t₃ или t₅) приведёт к возрастанию ошибки классификации.
Затем мы вычисляем g₁(t) для всех узлов t в Т₁.

R(t₁) – ошибка классификации. Если превратить t₁ в лист, то следует сопоставить ему какой либо класс; так как число примеров обоих классов одинаково (равно 100), то класс выбираем наугад, в любом случае он неправильно классифицирует 100 примеров. Всего дерево обучалось на 200 примеров (100+100=200 для корневого узла). R(t₁) = m/n. m=100, n=200. R(t₁) = 1/2.

$R\,(T_1,\,t_1)$– сумма ошибок всех листов поддерева. Считается как сумма по всем листам отношений количества неправильно классифицированных примеров в листе к общему числу примеров для дерева. В примере все делим на 200. Так как для поддерева с корнем в t₁ оно же дерево Т₁ все листы не имеют неправильно классифицированных примеров, поэтому

$|T_1,\,t_1|$ количество листов поддерева с корнем в узле t₁. Итого их – 5.

Узлы t₃ и t₅ оба хранят минимальное значение g₁, мы получаем новое дерево Т₂, обрезая Т₁ в обоих этих узлах. Мы получили дерево изображенное на рис.2.

Далее мы продолжаем вычислять g-значение для Т₂.

g₂(t₁) = (100/200 – (0/200 + 10/200 + 10/200)) / (3 – 1) = 2/10.

Минимум хранится в узле t₁, поэтому мы обрезаемы в t₁ и получаем корень дерева (T₃ = 1>). На этом процесс отсечения заканчивается.

Последовательность значений получается: $\alpha$₁ = 0, $\alpha$₂ = 1/20, $\alpha$₃ = 2/10. Итак, Т₁ является лучшим деревом для [0, 1/20), T₂ – для [1/20, 2/10) и Т₃ = 1> для [2/10, $\infty$).

Выбор финального дерева

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

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

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

Каковы различные узлы дерева решений?

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

Анализ Пример дерева решений

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

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

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

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

Понимание алгоритма дерева решений

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

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

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

Сколько видов деревьев решений?

Типы деревьев решений зависят от целевых переменных. Существует два типа деревьев решений:

Дерево решений с непрерывными переменными
Категорическое дерево принятия решений с переменными параметрами

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

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

Каковы “плюсы” и “минусы” дерева решений?

Сильные стороны

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

Слабые стороны

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

Терминологии основных деревьев принятия решений

Детский и родительский узлы

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

Под-дерево/отделение

Подраздел дерева решений – это его поддерево или ветвь.

Обрезка

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

Узел/лист терминала

Листовые или терминальные узлы не имеют детей и не проходят через дополнительные расщепления.

Узел принятия решений

Когда один подузел делится на несколько узлов, он становится узлом принятия решений.

Разделение

Разделение – это процесс, при котором один узел делится на несколько подузлов.

Корневой узел

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

Заключительные Мысли

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

Читайте также: