Полное практическое руководство по построению, визуализации и точной настройке дерева решений с использованием сокращения вычислений затрат в Python.

Введение

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

Дерево решений обычно состоит из:

  • Корневой узел - представляет выборку или совокупность, которая делится на дополнительные однородные группы.
  • Разделение - процесс разделения узлов на два подузла.
  • Узел принятия решения - когда подузел разделяется на дополнительные подузлы в зависимости от определенного условия, он называется узлом принятия решения.
  • Конечный или конечный узел - подчиненные узлы, которые не разделяются дальше
  • Получение информации - чтобы разделить узлы с помощью условия (скажем, наиболее информативной функции), нам нужно определить целевую функцию, которую можно оптимизировать. В алгоритме дерева решений мы стремимся максимизировать получение информации при каждом разбиении. Обычно для измерения прироста информации используются три меры примеси. Это примесь Джини, энтропия и ошибка классификации.



Достаточно ли ваши навыки программирования для работы в области науки о данных?
5 примеров кода, которые вы должны знать, если вы работаете в отрасли науки о данных в сторонуdatascience.com



Понимание математики

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

  1. Всего студентов - 20
  2. Всего студентов, отнесенных к категории гурманов - 10
  3. Всего учащихся, не отнесенных к категории гурманов - 10
  4. P (Foodie), вероятность того, что студент будет гурманом = (10/20) = 0,5
  5. Q (Not Foodie или 1-P), вероятность того, что студент не будет гурманом = (10/20) = 0,5

Давайте разделим учащихся по полу на два узла и пересчитаем вышеуказанные показатели.

Студенты мужского пола (узел A)

  1. Всего студентов - 10
  2. Всего студентов, отнесенных к категории гурманов - 8
  3. Всего учащихся, не отнесенных к категории гурманов - 2
  4. P (Foodie), вероятность того, что студент будет гурманом = (8/10) = 0,8
  5. Q (Not Foodie или 1-P), вероятность того, что студент не будет гурманом = (2/10) = 0,2

Студентки (узел B)

  1. Всего студентов - 10
  2. Всего студентов, отнесенных к категории гурманов - 4
  3. Всего учащихся, не отнесенных к категории гурманов - 6
  4. P (Foodie), вероятность того, что студент будет гурманом = (4/10) = 0,4
  5. Q (Not Foodie, или 1-P), вероятность того, что студент не будет гурманом = (6/10) = 0,6

Индекс Джини (GIn) для узла A или студентов мужского пола = P² + Q², где P и Q - вероятность того, что студент будет гурманом или не гурманом. GIn (узел A) = 0,8² + 0,2² = 0,68

примесь Джини (GIp) для узла A = 1 - индекс Джини = 1–0,68 = 0,32

Индекс Джини (GIn) для узла B или студенток = P² + Q², где P и Q - вероятность того, что студент будет гурманом или не гурманом. GIn (узел B) = 0,4² + 0,6² = 0,52

примесь Джини (GIp) для узла B = 1 - индекс Джини = 1–0,52 = 0,48

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

Взвешенная примесь Джини = (Общее количество образцов в узле A / Общее количество образцов в наборе данных) * Примесь Джини (узел A) + (Общее количество образцов в узле B / Общее количество образцов в наборе данных) * Примесь Джини (узел B)

Используя эту формулировку для расчета взвешенного показателя примеси Джини в приведенном выше примере, взвешенного показателя примеси Джини, когда учащиеся разделены по полу = (10/20) * 0,32 + (10/20) * 0,48 = 0,4

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

В приведенном выше примере взвешенное усиление примесей с использованием «пола» в качестве переменной решения составляет 0,4, однако, скажем, используя «степень» в качестве переменной решения, нам удается достичь взвешенного прироста примесей 0,56, алгоритм будет использовать «степень» в качестве переменная решения для создания первого разделения. Аналогичная методика применяется для всех последующих шагов, пока каждый узел не станет однородным.

Краткие сведения об алгоритме дерева решений

  1. Деревья решений склонны к переобучению, поскольку алгоритм продолжает разбивать узлы на подузлы, пока каждый узел не станет однородным.
  2. Точность обучающих данных намного выше по сравнению с тестовым набором, поэтому деревья решений следует обрезать, чтобы модель не переобучалась. Сокращение может быть достигнуто путем управления глубиной дерева, максимальным / минимальным количеством выборок в каждом узле, минимальным усилением примесей для узла, который нужно разделить, и максимальным количеством листовых узлов.
  3. Python позволяет пользователям разрабатывать дерево решений, используя примесь Джини или энтропию в качестве критерия получения информации.
  4. Дерево решений можно настроить с помощью поиска по сетке или рандомизированного поиска. CV означает перекрестную проверку

Визуальное сравнение трех различных критериев примеси

Приведенный ниже фрагмент кода обеспечивает визуальное сравнение различных критериев примесей и того, как они меняются с разными значениями вероятности. Обратите внимание, что приведенный ниже код адаптирован из Python: более глубокое понимание машинного обучения С.Рашки, Д. Джулиана и Дж. Херти, 2016.

import matplotlib.pyplot as plt
import numpy as np
#-----Calculating Gini Index
def gini(p):
    return (p)*(1 - (p)) + (1 - p)*(1 - (1-p))
#-----Calculating Entropy
def entropy(p):
    return - p*np.log2(p) - (1 - p)*np.log2((1 - p))
#-----Calculating Classification Error
def classification_error(p):
    return 1 - np.max([p, 1 - p])
#----Creating a Numpy Array of probability values from 0 to 1, with an increment of 0.01
x = np.arange(0.0, 1.0, 0.01)
#---Obtaining Entropy for different values of p
ent = [entropy(p) if p != 0 else None for p in x]
#---Obtaining scaled entropy
sc_ent = [e*0.5 if e else None for e in ent]
#--Classification Error
err = [classification_error(i) for i in x]
#--Plotting
fig = plt.figure();
plt.figure(figsize=(10,8));
ax = plt.subplot(111);
for i, lab, ls, c, in zip([ent, sc_ent, gini(x), err], ['Entropy', 'Entropy (scaled)','Gini Impurity',
                                                        'Misclassification Error'],['-', '-', '--', '-.'],
                          ['black', 'darkgray','blue', 'brown', 'cyan']):
    line = ax.plot(x, i, label=lab,
    linestyle=ls, lw=2, color=c)
    
ax.legend(loc='upper center', bbox_to_anchor=(0.5, 1.15), ncol=3, fancybox=True, shadow=False)
ax.axhline(y=0.5, linewidth=1, color='k', linestyle='--')
ax.axhline(y=1.0, linewidth=1, color='k', linestyle='--')
plt.ylim([0, 1.1])
plt.xlabel('p(i=1)')
plt.ylabel('Impurity Index')
plt.show()

Руки на упражнении

Постановка задачи направлена ​​на разработку модели классификации для прогнозирования качества красного вина. Подробнее о постановке задачи можно прочитать здесь. Это классический пример задачи классификации на несколько классов. Обратите внимание, что все модели машинного обучения чувствительны к выбросам, поэтому особенности / независимые переменные, состоящие из выбросов, следует обрабатывать перед построением дерева.

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

#---------------------------------------------Importing Required Libraries-----------------------------------
%matplotlib inline
import numpy as np
import pandas as pd
from sklearn.tree import DecisionTreeClassifier
import numpy as np
import pandas as pd
import seaborn as sns
sns.set(color_codes=True)
from matplotlib import pyplot as plt
from sklearn.model_selection import train_test_split #--------------splitting data into test and train
from sklearn.tree import DecisionTreeClassifier #-----------Building decision tree model
from sklearn import metrics
from sklearn.metrics import accuracy_score,f1_score,recall_score,precision_score, confusion_matrix #-----model validation scores
%matplotlib inline
from IPython.display import display #---------------------for displaying multiple data frames in one output
from sklearn.feature_extraction.text import CountVectorizer  #DT does not take strings as input for the model fit step
import missingno as msno_plot #--------------plotting missing values
wine_df = pd.read_csv('winequality-red.csv',sep=';')

Быстрая описательная статистика данных

wine_df.describe().transpose().round(2)

Проверка отсутствующих значений

#-------------------------------------------Barplot of non-missing values--------------------------------
plt.title('#Non-missing Values by Columns')
msno_plot.bar(wine_df);

Проверка выбросов и лечение

#--Checking Outliers
plt.figure(figsize=(15,15))
pos = 1
for i in wine_df.columns:
    plt.subplot(3, 4, pos)
    sns.boxplot(wine_df[i])
    pos += 1

col_names=['fixed acidity', 'volatile acidity', 'citric acid', 'residual sugar',
       'chlorides', 'free sulfur dioxide', 'total sulfur dioxide', 'density',
       'pH', 'sulphates', 'alcohol']
display(col_names)
for i in col_names:
    q1, q2, q3 = wine_df[i].quantile([0.25,0.5,0.75])
    IQR = q3 - q1
    lower_cap=q1-1.5*IQR
    upper_cap=q3+1.5*IQR
    wine_df[i]=wine_df[i].apply(lambda x: upper_cap if x>(upper_cap) else (lower_cap if x<(lower_cap) else x))

Вышеуказанные выбросы оцениваются с использованием значений Q1–1,5 * IQR и Q3 + 1,5 * IQR. Q1, Q3 и IQR обозначают квартиль 1, квартиль 3 и межквартильный диапазон соответственно.

sns.pairplot(wine_df);

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

plt.figure(figsize=(10,8))
sns.heatmap(wine_df.corr(),
            annot=True,
            linewidths=.5,
            center=0,
            cbar=False,
            cmap="YlGnBu")
plt.show()

Проблемы классификации чувствительны к классовой диспропорции. Дисбаланс классов - это сценарий, когда в зависимом атрибуте доля единиц больше, чем нулей, или наоборот. В мультиклассовой задаче дисбаланс классов возникает, когда доля одного из значений класса намного выше. Баланс классов достигается путем комбинирования значений атрибута «качество», который является зависимой переменной в этой постановке задачи.

plt.figure(figsize=(10,8))
sns.countplot(wine_df['quality']);

wine_df['quality'] = wine_df['quality'].replace(8,7)
wine_df['quality'] = wine_df['quality'].replace(3,5)
wine_df['quality'] = wine_df['quality'].replace(4,5)
wine_df['quality'].value_counts(normalize=True)

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

# splitting data into training and test set for independent attributes
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test =train_test_split(wine_df.drop('quality',axis=1), wine_df['quality'], test_size=.3,
                                                   random_state=22)
X_train.shape,X_test.shape

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

clf_pruned = DecisionTreeClassifier(criterion = "gini", random_state = 100,
                               max_depth=3, min_samples_leaf=5)
clf_pruned.fit(X_train, y_train)

Обратите внимание, что следующие параметры можно настроить для улучшения вывода модели (Scikit Learn, 2019).

  1. критерий - примесь Джини используется для определения переменных, на основе которых следует разделить корневой узел и следующие узлы решения.
  2. вес_класса - нет; Всем классам присваивается вес 1
  3. max_depth - 3; Обрезка сделана. Когда «Нет», это означает, что узлы будут расширяться до тех пор, пока все листья не станут однородными.
  4. max_features - нет; При принятии решения о разделении узла учитываются все функции или независимые переменные.
  5. max_leaf_nodes - нет;
  6. min_impurity_decrease - 0,0; Узел разделяется только тогда, когда разделение обеспечивает уменьшение примеси больше или равное нулю.
  7. min_impurity_split - нет;
  8. min_samples_leaf - 1; Минимальное количество образцов, необходимых для существования листа
  9. min_samples_split - 2; Если min_samples_leaf = 1, это означает, что правый и левый узел должны иметь по 1 выборке каждый, то есть родительский узел или корневой узел должны иметь не менее двух выборок.
  10. сплиттер - «лучший»; Стратегия, используемая для выбора разделения на каждом узле. Лучше всего убедиться, что все особенности учтены при принятии решения о разделении
from sklearn.tree import export_graphviz
from sklearn.externals.six import StringIO  
from IPython.display import Image  
import pydotplus
import graphviz
xvar = wine_df.drop('quality', axis=1)
feature_cols = xvar.columns
dot_data = StringIO()
export_graphviz(clf_pruned, out_file=dot_data,  
                filled=True, rounded=True,
                special_characters=True,feature_names = feature_cols,class_names=['0','1','2'])
from pydot import graph_from_dot_data
(graph, ) = graph_from_dot_data(dot_data.getvalue())
Image(graph.create_png())

preds_pruned = clf_pruned.predict(X_test)
preds_pruned_train = clf_pruned.predict(X_train)
print(accuracy_score(y_test,preds_pruned))
print(accuracy_score(y_train,preds_pruned_train))

Оценка точности модели на обучающих и тестовых данных оказалась равной 0,60 и 0,62 соответственно.

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

## Calculating feature importance
feat_importance = clf_pruned.tree_.compute_feature_importances(normalize=False)
feat_imp_dict = dict(zip(feature_cols, clf_pruned.feature_importances_))
feat_imp = pd.DataFrame.from_dict(feat_imp_dict, orient='index')
feat_imp.rename(columns = {0:'FeatureImportance'}, inplace = True)
feat_imp.sort_values(by=['FeatureImportance'], ascending=False).head()

DecisionTreeClassifier () предоставляет такие параметры, как min_samples_leaf и max_depth, чтобы предотвратить переоснащение дерева. Думайте об этом как о сценарии, в котором мы явно определяем глубину и максимальное количество листьев в дереве. Однако самая большая проблема - определить оптимальную глубину и листья, которые должно содержать дерево. В приведенном выше примере мы использовали max_depth = 3, min_samples_leaf = 5. Эти числа являются лишь примерами фигур, чтобы увидеть, как ведет себя дерево. Но если на самом деле нас попросили поработать над этой моделью и найти оптимальное значение для параметров модели, это будет сложно, но не невозможно (модели дерева решений можно настроить с помощью алгоритма GridSearchCV).

Другой способ сделать это - использовать сокращение сложности затрат (CCP).

Обрезка сложности с затратами дает еще один вариант управления размером дерева. В DecisionTreeClassifier этот метод отсечения параметризуется параметром сложности затрат ccp_alpha. Большие значения ccp_alpha увеличивают количество удаляемых узлов (Scikit Learn, n.d.).

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

Чем ниже КПК, тем ниже примеси. Как?

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

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

В приведенном ниже коде (Scikit Learn, n.d.) показано, как можно настроить альфа-канал для получения модели с улучшенным показателем точности.

path = model_gini.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas, impurities = path.ccp_alphas, path.impurities
fig, ax = plt.subplots(figsize=(16,8));
ax.plot(ccp_alphas[:-1], impurities[:-1], marker='o', drawstyle="steps-post");
ax.set_xlabel("effective alpha");
ax.set_ylabel("total impurity of leaves");
ax.set_title("Total Impurity vs effective alpha for training set");

Давайте разберемся с изменением глубины и количества узлов при изменении альфа.

clfs = clfs[:-1]
ccp_alphas = ccp_alphas[:-1]
node_counts = [clf.tree_.node_count for clf in clfs]
depth = [clf.tree_.max_depth for clf in clfs]
fig, ax = plt.subplots(2, 1,figsize=(16,8))
ax[0].plot(ccp_alphas, node_counts, marker='o', drawstyle="steps-post")
ax[0].set_xlabel("alpha")
ax[0].set_ylabel("number of nodes")
ax[0].set_title("Number of nodes vs alpha")
ax[1].plot(ccp_alphas, depth, marker='o', drawstyle="steps-post")
ax[1].set_xlabel("alpha")
ax[1].set_ylabel("depth of tree")
ax[1].set_title("Depth vs alpha")
fig.tight_layout()

Понимание изменения точности при увеличении альфа.

fig, ax = plt.subplots(figsize=(16,8)); #-----------------Setting size of the canvas
train_scores = [clf.score(X_train, y_train) for clf in clfs]
test_scores = [clf.score(X_test, y_test) for clf in clfs]
ax.set_xlabel("alpha")
ax.set_ylabel("accuracy")
ax.set_title("Accuracy vs alpha for training and testing sets")
ax.plot(ccp_alphas, train_scores, marker='o', label="train",
        drawstyle="steps-post")
ax.plot(ccp_alphas, test_scores, marker='o', label="test",
        drawstyle="steps-post")
ax.legend()
plt.show()

i = np.arange(len(ccp_alphas))
ccp = pd.DataFrame({'Depth': pd.Series(depth,index=i),'Node' : pd.Series(node_counts, index=i),\
                    'ccp' : pd.Series(ccp_alphas, index = i),'train_scores' : pd.Series(train_scores, index = i),
                   'test_scores' : pd.Series(test_scores, index = i)})
ccp.tail()
ccp[ccp['test_scores']==ccp['test_scores'].max()]

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

Ссылка

  1. Рашка, С., Джулиан, Д. и Харти, Дж. (2016). Python: более глубокое понимание машинного обучения: использование преимуществ методов машинного обучения с использованием Python: курс из трех модулей. Бирмингем, Великобритания: Packt Publishing, стр. 83, 88, 89.
  2. ‌ Scikit-learn: машинное обучение в Python, Педрегоса и др., JMLR 12, стр. 2825–2830, 2011.
  3. Scikit Learn (2019). sklearn.tree.DecisionTreeClassifier - документация scikit-learn 0.22.1. [онлайн] Scikit-learn.org. Доступно по адресу: https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html.
  4. Scikit Learn (нет данных). Публикация деревьев решений по сокращению с сокращением сложности затрат. [онлайн] Доступно по адресу: https://scikit-learn.org/stable/auto_examples/tree/plot_cost_complexity_pruning.html#sphx-glr-auto-examples-tree-plot-cost-complexity-pruning-py.

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