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

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

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

https://github.com/Eligijus112/градиентное повышение

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



Алгоритм дерева решений в Python с нуля
Написание популярного алгоритма с использованием только NumPy и Pandas в Python и объяснение того, что находится под капотомtowardsdatascience.com





Дерево регрессии в Python с нуля
Программирование популярного алгоритма дерева регрессии в Python и объяснение его сутиtowardsdatascience.com





Алгоритм случайного леса в Python с нуля
Написание мощного алгоритма на Python с использованием (в основном) массивов и цикловtowardsdatascience.com



Мы будем использовать модель дерева решений, чтобы создать связь между средней ценой на жилье (Y) в Калифорнии с использованием различных регрессоров (X). Набор данных¹ можно загрузить с помощью пакета scikit-learn:

# Dataset loading
from sklearn.datasets import fetch_california_housing
# Loading the data
_cali_data = fetch_california_housing(as_frame=True)
# Features and target
X, y = _cali_data.data, _cali_data.target
# Droping the geo coordinate featuress
X = X.drop(columns=['Latitude', 'Longitude'])
# Droping the population feature; In real life modeling, this could be used as weight.
# For educational and inference purposes, we drop it.
X = X.drop(columns=['Population'])
# Saving the feature names
features = X.columns
view raw california.py hosted with ❤ by GitHub

Функции X, которые мы будем использовать в моделях:

* MedInc — средний доход домохозяйства за последние 12 месяцев (сотни тысяч)

* HouseAge — возраст дома (годы)

* AveRooms – среднее количество комнат в жилом доме.

* AveBedrms — среднее количество спален на жилое помещение.

* AveOccup – среднее количество членов домохозяйства.

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

Форма данных следующая:

Быстрый взгляд на переменные функции:

Распределение переменной Y:

Чтобы анонимизировать данные, в данных есть предел дохода в 500 000 долларов: все, что выше этого, по-прежнему помечается как доход в 500 000 долларов. Это делается для того, чтобы никто не мог идентифицировать конкретное домашнее хозяйство, потому что еще в 1997 году было не так много домашних хозяйств, которые стоили так дорого.

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

# Train test spliting
from sklearn.model_selection import train_test_split
# Importing the sklearn implementation
from sklearn.tree import DecisionTreeRegressor
# Precision metrics
from sklearn.metrics import mean_absolute_error
# Spliting the data into training and testing sets
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.25, random_state=0)
# Defining the hyper parameters
hps = {
'max_depth': 3,
'min_samples_split': 4
}
# Loading the tree object
tree = DecisionTreeRegressor(**hps)
# Fitting on the training data
tree.fit(X_train, y_train)
# Predicting the test set
y_pred = tree.predict(X_test)
# Calculating the mean absolute error
mae_train = mean_absolute_error(y_train, tree.predict(X_train)).round(2)
mae_test = mean_absolute_error(y_test, y_pred).round(2)
print(f"Mean absolute error on training set: {mae_train}")
print(f"Mean absolute error on test set: {mae_test}")
view raw regression_tree_fit.py hosted with ❤ by GitHub

Распечатки:

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

Взрослое дерево на тренировочном наборе:

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

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

Каждый узел нумеруется от 1 до 15.

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

MedInc ≤ 5,029 — правило разделения узла. Если наблюдение имеет значение MedInc меньше или равное 5,029, то мы идем по дереву влево (переходим к узлу 2), в противном случае идем к правому узлу (узел номер 3).

squared_error — статистика, используемая в качестве критерия разделения. Squared_error рассчитывается по следующей формуле:

В первом узле статистика равна 1,335.

samples — количество наблюдений в узле. Поскольку это корневой узел, 15480 соответствует всему набору обучающих данных.

value — прогнозируемое значение узла. Другими словами, если путь наблюдения останавливается в этом узле, то прогнозируемое значение для этого узла будет равно 2,074.

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

n_entries = {
“node 1”: 15480,
“node 2”: 12163,
“node 3”: 3317,
“node 4”: 5869,
“node 5”: 6294,
“node 6”: 2317,
“node 7”: 1000,
“node 8”: 2454,
“node 9”: 3415,
“node 10”: 1372,
“node 11”: 4922,
“node 12”: 958,
“node 13”: 1359,
“node 14”: 423,
“node 15”: 577
}

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

Обозначим этот словарь как n_entries_weighted:

n_entries_weighted = {
'node 1': 1.0,  
'node 2': 0.786,  
'node 3': 0.214,  
'node 4': 0.379,  
'node 5': 0.407,  
'node 6': 0.15,  
'node 7': 0.065,  
'node 8': 0.159,  
'node 9': 0.221,  
'node 10': 0.089,  
'node 11': 0.318,  
'node 12': 0.062,  
'node 13': 0.088,  
'node 14': 0.027,  
'node 15': 0.037
}

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

Обозначим каждый узел как

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

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

Обозначим статистику среднеквадратичной ошибки (MSE) как:

Одним очень важным атрибутом узла, у которого есть дочерние элементы, является так называемая важность узла:

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

Давайте создадим словарь со статистикой MSE каждого узла:

i_sq = {
“node 1”: 1.335,
“node 2”: 0.832,
“node 3”: 1.214,
“node 4”: 0.546,
“node 5”: 0.834,
“node 6”: 0.893,
“node 7”: 0.776,
“node 8”: 0.648,
“node 9”: 0.385,
“node 10”: 1.287,
“node 11”: 0.516,
“node 12”: 0.989,
“node 13”: 0.536,
“node 14”: 0.773,
“node 15”: 0.432
}

Авторы Тревор Хасти, Роберт Тибширани и Джером Фридман в своей замечательной книге Элементы статистического обучения: интеллектуальный анализ данных, вывод и прогнозированиеопределяют вычисление важности признаков с помощью следующего уравнения²:

Где

T — все дерево решений

l — рассматриваемая функция

J — количество внутренних узлов в дереве решений

i² — уменьшение показателя, используемого для разделения

II — индикаторная функция

v(t) — функция, используемая при разделении узла t, используемая при разделении узла.

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

Scikit-learn использует предложенную ранее формулу важности узла. Основное отличие состоит в том, что в scikit-learn вводятся веса узлов, которые представляют собой вероятность попадания наблюдения в дерево.

Давайте немного увеличим масштаб и осмотрим узлы с 1 по 3 немного дальше.

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

Только узлы с правилом разделения участвуют в расчете важности функции.

2-й узел является левым дочерним элементом, а 3-й узел — правым дочерним элементом узла номер 1.

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

Если мы используем MedInc в корневом узле, 12163 наблюдения будут отправлены на второй узел и 3317 — на правый узел. Это означает, что вес левого узла равен 0,786 (12163/15480), а вес правого узла равен 0,214 (3317/15480). Среднеквадратическая ошибка в левом узле равна 0,892, а в правом узле — 1,214.

Нам нужно рассчитать важность узла:

Теперь мы можем сохранить важность узла в словаре. Ключи словаря — это функции, которые использовались в критериях разделения узла. Значения - это важность узла.

{
  "MedInc": 0.421252,
  "HouseAge": 0,
  "AveRooms": 0,
  "AveBedrms": 0,
  "AveOccup": 0
}

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

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

Квадрат ошибки, если мы используем функцию MedInc в узле 2:

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

{
  "MedInc": 0.421 + 0.10758
  "HouseAge": 0,
  "AveRooms": 0,
  "AveBedrms": 0,
  "AveOccup": 0
}

{
  "MedInc": 0.558,
  "HouseAge": 0,
  "AveRooms": 0.018817,
  "AveBedrms": 0,
  "AveOccup": 0
}

Мы не можем пойти дальше, потому что узлы 8 и 9 не имеют правила разделения и, следовательно, не уменьшают статистику среднеквадратичной ошибки.

Давайте закодируем реализацию, которая была представлена ​​в разделах выше.

# Entries in the nodes
n_entries = {
"node 1": 15480,
"node 2": 12163,
"node 3": 3317,
"node 4": 5869,
"node 5": 6294,
"node 6": 2317,
"node 7": 1000,
"node 8": 2454,
"node 9": 3415,
"node 10": 1372,
"node 11": 4922,
"node 12": 958,
"node 13": 1359,
"node 14": 423,
"node 15": 577
}
# Nodes squared errors
i_sq = {
"node 1": 1.335,
"node 2": 0.832,
"node 3": 1.214,
"node 4": 0.546,
"node 5": 0.834,
"node 6": 0.893,
"node 7": 0.776,
"node 8": 0.648,
"node 9": 0.385,
"node 10": 1.287,
"node 11": 0.516,
"node 12": 0.989,
"node 13": 0.536,
"node 14": 0.773,
"node 15": 0.432
}
# Defining the features used in the nodes that have a splitting rule
feature_in_node = {
"node 1": "MedInc",
"node 2": "MedInc",
"node 3": "MedInc",
"node 4": "AveRooms",
"node 5": "AveOccup",
"node 6": "AveOccup",
"node 7": "MedInc"
}
# The first node's count is the total number of entries in the tree
_n = n_entries["node 1"]
# Calculating the n entries probability
n_entries_weight = {}
for node in n_entries:
n_entries_weight[node] = n_entries[node] / _n
# Defining the relationship between nodes;
# The key is the parent node, and the value is a list of
# [left child node, right child node]
node_pairs = {
"node 1": ["node 2", "node 3"],
"node 2": ["node 4", "node 5"],
"node 3": ["node 6", "node 7"],
"node 4": ["node 8", "node 9"],
"node 5": ["node 10", "node 11"],
"node 6": ["node 12", "node 13"],
"node 7": ["node 14", "node 15"]
}
view raw tree_data.py hosted with ❤ by GitHub

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

def node_importance(
node_main: str,
node_left: str,
node_right: str,
n_entries_weight: dict,
i_sq: dict
) -> float:
"""
Calculated the importance of the node_main
Arguments
---------
node_main: str
The main parent node
node_left: str
The left child node
node_right: str
The right child node
n_entries_weight: dict
The weight of each node, calculated by the samples in node divided by the total number of samples
i_sq: dict
The squared error of each node
Returns
-------
float
The importance of the node_main
"""
# Calculating the main nodes part of the equation
_main_part = n_entries_weight[node_main] * i_sq[node_main]
# Calculating the left child nodes part of the equation
_left_part = n_entries_weight[node_left] * i_sq[node_left]
# Calculating the right child nodes part of the equation
_right_part = n_entries_weight[node_right] * i_sq[node_right]
# Returning the gain of the node_main; This gain is the importance of the node_main
return _main_part - _left_part - _right_part
view raw node_importance.py hosted with ❤ by GitHub

Собираем все вместе:

# Calculating the importance of each node
importance = {}
for node in node_pairs:
importance[node] = round(node_importance(node, *node_pairs[node], n_entries_weight, i_sq), 3)
print(f"Node importance: {importance}")
# Going from node importance to feature importance
feature_importance = {}
for node in node_pairs:
# Extracting the feature name
_ft_name = feature_in_node[node]
# Extracting the feature importance
_ft_imp = importance[node]
# Adding the feature importance to the feature importance dictionary
if _ft_name in feature_importance:
feature_importance[_ft_name] += _ft_imp
else:
feature_importance[_ft_name] = _ft_imp
# Adding any missing features
for feature in features:
if feature not in feature_importance:
feature_importance[feature] = 0
print(f"Feature importance before normalization: {feature_importance}")
# Dividing the feature importance by the sum of importances
_sum_importance = sum(feature_importance.values())
for feature in feature_importance:
feature_importance[feature] = round(feature_importance[feature]/_sum_importance, 3)
print(f"Feature importance after normalization: {feature_importance}")
view raw feature_importance_calculation.py hosted with ❤ by GitHub

Отпечатки в приведенном выше фрагменте кода:

Node importance: {
‘node 1’: 0.421, 
‘node 2’: 0.108, 
‘node 3’: 0.076, 
‘node 4’: 0.019, 
‘node 5’: 0.061, 
‘node 6’: 0.025, 
‘node 7’: 0.013
} 
Feature importance before normalization: {
‘MedInc’: 0.618, 
‘AveRooms’: 0.019, 
‘AveOccup’: 0.086, 
‘HouseAge’: 0, 
‘AveBedrms’: 0
} 
Feature importance after normalization: {
‘MedInc’: 0.855, 
‘AveRooms’: 0.026, 
‘AveOccup’: 0.119, 
‘HouseAge’: 0.0, 
‘AveBedrms’: 0.0
}

Окончательный словарь признаков после нормализации — это словарь с окончательной важностью признаков. Согласно словарю, наиболее важной функцией является MedInc, за которой следуют AveOccup и AveRooms.

Признаки HouseAge и AveBedrms не использовались ни в одном из правил разделения, поэтому их важность равна 0.

Давайте сравним наш расчет с реализацией расчета важности признаков в scikit-learn.

# Loading the data
_cali_data = fetch_california_housing(as_frame=True)
X, y = _cali_data.data, _cali_data.target
# Droping the geo coordinate featuress
X = X.drop(columns=['Latitude', 'Longitude'])
# Droping the population feature; In real life modeling, this could be used as weight.
# For educational and inference purposes, we drop it.
X = X.drop(columns=['Population'])
# Saving the feature names
features = X.columns.tolist()
# Train test split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.25, random_state=0)
# Defining the hyper parameters
hps = {
'max_depth': 3,
'min_samples_split': 4,
'random_state': 0
}
# Loading the tree object
tree = DecisionTreeRegressor(**hps)
# Fitting on the training data
tree.fit(X_train, y_train)
# Extracting the importances by sklearn
importances_sk = tree.feature_importances_
# Creating a dataframe with the feature importance by sklearn
feature_importance_sk = {}
for i, feature in enumerate(features):
feature_importance_sk[feature] = round(importances_sk[i], 3)
print(f"Feature importance by sklearn: {feature_importance_sk}")
view raw sklearn_ft_importance.py hosted with ❤ by GitHub

Печать гласит:

Feature importance by sklearn: 
{
‘MedInc’: 0.854, 
‘HouseAge’: 0.0, 
‘AveRooms’: 0.027, 
‘AveBedrms’: 0.0, 
‘AveOccup’: 0.12
}

Сравнивая с нашими расчетами:

Есть минимальные различия, но они связаны с ошибками округления.

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

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

Удачного кодирования!

[1] Автор:Пейс, Р. Келли и Рональд Барри
Год: 1997
Название: Разреженные пространственные авторегрессии
URL: https://archive.ics.uci.edu/ml
Журнал: Письма о статистике и вероятности

[2] Автор:Тревор Хасти, Роберт Тибширани и Джером Фридман
Год: 2017
Название: Элементы статистического обучения: данные Интеллектуальный анализ, логические выводы и прогнозирование
URL: https://archive.ics.uci.edu/ml
Страница: 368–370