Способы построения деревьев решений

Дерево решений (Decision Tree)

Дерево решений – это инструмент прогнозного моделирования, применяемого в ряде различных областей. Как правило, они строятся с помощью алгоритмического подхода, который определяет способы разделения набора данных на основе различных условий. Это один из наиболее широко используемых и практичных методов Контролируемого обучения (Supervised Learning). Деревья решений – это непараметрический метод обучения с учителем, используемый как для Классификации (Classification), так и для задач Регрессии (Regression). Цель состоит в том, чтобы создать модель, которая предсказывает значение Целевой переменной (Target Feature), изучая простые правила принятия решений, выведенные из характеристик данных.

Правила принятия решений обычно имеют форму операторов if-then-else. Чем глубже дерево, тем сложнее правила и точнее модель.

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

  • Экземпляры – векторы Признаков (Feature), атрибутов, которые определяют пространство ввода
  • Атрибут – количество, описывающее экземпляр
  • Концепция – функция, которая сопоставляет ввод с выводом
  • Целевая концепция – функция, которую мы пытаемся найти, то есть фактический ответ
  • Класс гипотез – набор всех возможных функций.
  • Выборка (Sample) – набор входных данных в паре с меткой, которая является правильным выходом. Также известна как Тренировочные данные (Train Data)
  • Концепция кандидата – концепция, которая, по нашему мнению, является целевой
  • Тестовые данные (Test Data) – аналогичен набору для обучения и используется для тестирования концепции кандидата и определения его производительности
Читайте также:  Способы расчета заработной платы при различных формах оплаты труда

Вступление

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

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

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

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

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

Дерево решений для концепции «Игра в бадминтон»

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

Общий алгоритм для дерева решений можно описать следующим образом:

  • Выберите лучший атрибут, который разделяет наблюдения на группы
  • Задайте соответствующий вопрос
  • Следуйте по путям ответов
  • Вернитесь к шагу 1

Хороший сплит – это разделение двух разных этикеток на два варианта.

Выразительность деревьев решений

Деревья решений могут иметь в качестве узлов булевую пару значений «Да / Нет». Давайте воспользуемся ими для изучения трех логических концепций ‘AND, OR и XOR’. Посмотрим, как строится дерево для первого оператора «И» (AND). Согласно логике оператора, любое значение False в столбцах A и B генерирует результат False, и только пара True генерирует положительный результат. Конвертируя таблицу в деревья, мы рассматриваем два варианта развития событий: то A первично, то B, ибо такова иерархическая природа дерева решений. Посвятите одну-две минуты, чтобы проникнуться простой логикой дерева, дублирующей таблицу.

Дерево решений для оператора И (AND)

Есть две кандидат-концепции для создания дерева решений, которые подчиняются логике «И». Точно так же создается дерево решений, которое подчиняется логике «ИЛИ» (OR).

Дерево решений для оператора ИЛИ (OR)

Давайте создадим дерево решений, выполняющее функцию XOR, используя 3 атрибута:

Дерево решений для оператора «Исключительное ИЛИ» (XOR)

Границы дерева

Деревья решений делят пространство признаков на параллельные оси прямоугольники или гиперплоскости. Продемонстрируем это на примере. Давайте рассмотрим простую операцию «И» над двумя переменными. Предположим, что X и Y являются координатами по осям x и y соответственно, и нанесем возможные значения X и Y. На анимации изображено формирование границы принятия решения по мере принятия каждого решения:

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

Дерево решений и Scikit-learn

Дерево решений можно построить с помощью модуля SkLearn. Для начала импортируем необходимые библиотеки:

Мы будем использовать классический набор данных о подвидах цветка Ириса.

Датасет (Dataset) содержит информацию растениях в виде следующих признаков:

  • Длина чашелистика
  • Ширина чашелистика
  • Длина лепестка
  • Ширина лепестка

Выделяют три класса растений:

  • Ирис щетинистый (Iris Setosa)
  • Ирис разноцветный (Iris Versicolour)
  • Ирис виргинский (Iris Virginica)

Задача – предсказать класс растения ириса по признакам. Извлечем данные так, чтобы наполнить столбцы данными и назвать их определенным образом:

Датасет совсем крошечный:

Всегда полезно взглянуть на данные в исходном состоянии:

В ячейке ниже показаны 4 атрибута первых четырех растений ириса:

Теперь, когда мы извлекли атрибуты данных и соответствующие метки, мы разделим их, чтобы сформировать наборы данных для обучения и тестирования. Для этой цели мы будем использовать функцию train_test_split() , которая принимает атрибуты и метки в качестве входных данных и создает наборы Тренировочных (Train Data) и Тестовых данных (Test Data):

Мы установим критерий «энтропия», который параметризует способ разделения данных на тренировочную и учебную части:

Система отображает настройки классификатора по умолчанию:

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

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

Чем больше значение min_sample_split , тем сглаженнее границы решения и маловероятнее Переобучение (Overfitting). Посмотрим, как Модель (Model) представляет себе дерево решений:

Чтобы создать первое разветвление, система предположила пограничное значение X[3] ≤ 0.8 (ширина лепестка меньше 0,8 сантиметра). SkLearn, вероятно, указывает, как выглядит типичный представитель своего подвида в строках value . Число наблюдений в каждом из двух разветвлений, как вы уже наверняка заметили, равно числу наблюдений родительской ветки.

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

Источник

1.10. Деревья решений ¶

Деревья решений (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 .

Использование деревьев с несколькими выходами для регрессии продемонстрировано в разделе «Регрессия дерева решений с несколькими выходами» . В этом примере вход X — это одно действительное значение, а выходы Y — синус и косинус X.

Использование деревьев с несколькими выходами для классификации демонстрируется в разделе «Завершение лица с оценками с несколькими выходами» . В этом примере входы X — это пиксели верхней половины граней, а выходы Y — пиксели нижней половины этих граней.

1.10.4. Сложность

В общем, время выполнения для построения сбалансированного двоичного дерева составляет $O(n_n_\log(n_))$ и время запроса $O(\log(n_))$. Хотя алгоритм построения дерева пытается генерировать сбалансированные деревья, они не всегда будут сбалансированными. Предполагая, что поддеревья остаются примерно сбалансированными, стоимость на каждом узле состоит из перебора $O(n_)$ найти функцию, обеспечивающую наибольшее снижение энтропии. Это стоит $O(n_n_\log(n_))$ на каждом узле, что приводит к общей стоимости по всем деревьям (суммируя стоимость на каждом узле) $O(n_n_^<2>\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 это часто лучший выбор.

Обратите внимание, что min_samples_split выборки рассматриваются напрямую и независимо от них sample_weight , если они предусмотрены (например, узел с m взвешенными выборками по-прежнему обрабатывается как имеющий ровно m выборок). Рассмотрим min_weight_fraction_leaf или min_impurity_decrease если учет образцов весов требуются при расколах.

  • Перед обучением сбалансируйте набор данных, чтобы дерево не смещалось в сторону доминирующих классов. Балансировка классов может быть выполнена путем выборки равного количества выборок из каждого класса или, предпочтительно, путем нормализации суммы весов выборок ( sample_weight ) для каждого класса к одному и тому же значению. Также обратите внимание, что критерии предварительного отсечения на основе веса, такие как min_weight_fraction_leaf , будут менее смещены в сторону доминирующих классов, чем критерии, которые не знают весов выборки, например min_samples_leaf .
  • Если выборки взвешены, будет проще оптимизировать древовидную структуру, используя основанный на весе критерий предварительной отсечения, например min_weight_fraction_leaf , который гарантирует, что конечные узлы содержат по крайней мере часть общей суммы весов выборки.
  • Все деревья решений np.float32 внутренне используют массивы. Если данные обучения не в этом формате, будет сделана копия набора данных.
  • Если входная матрица X очень разреженная, рекомендуется преобразовать ее в разреженную csc_matrix перед вызовом соответствия и разреженную csr_matrix перед вызовом предсказания. Время обучения может быть на порядки меньше для входной разреженной матрицы по сравнению с плотной матрицей, когда функции имеют нулевые значения в большинстве выборок.
  • 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 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<1> \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 параметра.

    Источник

    Оцените статью
    Разные способы