Математика деревьев решений, случайный лес и важность функций в Scikit-learn и Spark

Введение

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

В Интернете есть много замечательных ресурсов, в которых обсуждается, как создаются деревья решений и случайные леса, и этот пост не предназначен для этого. Хотя он включает короткие определения контекста, предполагается, что читатель понимает эти концепции и желает знать, как алгоритмы реализованы в Scikit-learn и Spark.

Итак, начнем с…

Деревья решений

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

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

Существует несколько алгоритмов, и документация scikit-learn предоставляет обзор некоторых из них (ссылка)

Так что же используют Scikit-learn и Spark?

В документации Scikit-learn говорится, что он использует «оптимизированную версию алгоритма CART». Хотя это явно не упоминается в документации, было сделано предположение, что Spark использует ID3 с CART.

Итак, давайте сосредоточимся на этих двух - ID3 и CART.

Преимущества и недостатки взяты из статьи Сравнительное исследование ID3, CART и C4.5 алгоритм дерева принятия решений: обзор. Там же можно найти более подробные определения.

ID3

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

Преимущества

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

Недостатки

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

КОРЗИНА

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

Преимущества

• CART может легко обрабатывать как числовые, так и категориальные переменные
• Алгоритм CART сам определит наиболее значимые переменные и исключит незначимые.
• CART легко справляется с выбросами

Недостатки

• У КОРЗИНЫ может быть нестабильное дерево решений
• CART разделяется по одной переменной

Примесь узла / критерий примеси

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

Ссылки на документацию по древовидным алгоритмам

• Научный комплект учить
• "Искра"

Получение информации

Еще один термин, на который стоит обратить внимание, - это «получение информации», который используется для разделения данных с использованием энтропии. Он рассчитывается как уменьшение энтропии после разделения набора данных по атрибуту:

Прирост (T, X) = энтропия (T) - энтропия (T, X)

• T = целевая переменная
• X = функция, которую нужно разделить
• Энтропия (T, X) = энтропия, вычисленная после разделения данных по признаку X

Случайные леса

Случайные леса (RF) создают множество индивидуальных деревьев решений во время обучения. Прогнозы по всем деревьям объединяются, чтобы сделать окончательный прогноз; режим классов для классификации или прогноз среднего для регрессии. Поскольку они используют набор результатов для принятия окончательного решения, они называются методами ансамбля.

Важность функции

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

Реализация в Scikit-learn

Для каждого дерева решений Scikit-learn вычисляет важность узлов с использованием значения Gini Importance, предполагая только два дочерних узла (двоичное дерево):

• ni sub (j) = важность узла j
• w sub (j) = взвешенное количество выборок, достигающих узла j
• C sub (j) = значение примеси узла j
• left (j) = дочерний узел из левого разделения на узле j
• right (j) = дочерний узел из правого разделения на узле j

sub () используется, поскольку индекс недоступен в Medium

См. Метод compute_feature_importances в _tree.pyx

Затем важность каждой функции в дереве решений рассчитывается как:

• fi sub (i) = важность функции i
• ni sub (j) = важность узла j

Затем их можно нормализовать до значения от 0 до 1, разделив на сумму всех значений важности функций:

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

• RFfi sub (i) = важность признака i, рассчитанная по всем деревьям в модели случайного леса
• normfi sub (ij) = нормализованная важность функции для i в дереве j
• T = общее количество деревьев

См. Метод feature_importances_ в forest.py

Нотация была навеяна этой веткой StackExchange, которую я нашел невероятно полезной для этого сообщения.

Реализация в Spark

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

• fi sub (i) = важность функции i
• s sub (j) = количество выборок, достигающих узла j
• C sub (j) = значение примеси узла j

См. Метод computeFeatureImportance в treeModels.scala

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

• normfi sub (i) = нормализованная важность функции i
• fi sub (i) = важность функции i

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

• RFfi sub (i) = важность признака i, рассчитанная по всем деревьям в модели случайного леса
• normfi sub (ij) = нормализованная важность функции для i в дереве j

См. Метод featureImportances в treeModels.scala

Заключение

Целью этой модели было объяснить, как Scikit-Learn и Spark реализуют деревья решений и вычисляют значения важности функций.

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