Древо решений

1 Основные понятия

количество информации

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

Информационная энтропия

Он измеряет степень неопределенности набора событий, то есть ожидание неопределенности всех событий в наборе событий.

Относительная энтропия (расхождение KL)

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

перекрестная энтропия

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

совместная энтропия

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

Условная энтропия

Условная энтропия множества событий Y = совместная энтропия - информационная энтропия множества событий X, которая используется для измерения степени снижения неопределенности множества событий Y на основе известного множества событий X

2 Принцип дерева решений

2.1 Принцип

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

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

2.2 Процесс

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

2.3 Как определить оптимальную точку разделения

• ID3 - получение информации

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

  Для выборки D количество категорий равно K, а эмпирическая энтропия набора данных D выражается как

  $$H(D)=-\sum_{k=1}^{K} \frac{\left|C_{k}\right|}{|D|} \log _{2} \frac{\left|C_{k}\right|}{|D|}$$

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

из которых$C_k$— подмножество выборок, принадлежащих k-му классу в выборке D,$|C_k|$представляет количество элементов в подмножестве,$|D|$Представляет количество элементов в выборке.

Затем рассчитайте эмпирическую условную энтропию признака A для набора данных D.$H(D|A)$за

Среди них,$D_i$Представляет подмножество выборок, которые принимают i-е значение признака A в D,$D_{ik}$выражать$D_i$Подмножество выборок, принадлежащих k-му классу в .

Таким образом, получение информации$g(D,A)$можно выразить как разницу между ними, мы можем получить

​总结：ID3对特征值数目较多的特征有所偏好，且只能处理离散型数据；对缺失值敏感

• C4.5 - Скорость получения информации

  Коэффициент получения информации от функции A к набору данных D определяется как

  $$g_{R}(D, A)=\frac{g(D, A)}{H_{A}(D)}$$

  в

  $$H_{A}(D)=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \log _{2} \frac{\left|D_{i}\right|}{|D|}$$

​总结：C4.5使用信息增益率克服信息增益偏好特征数目多的特征，实际上是引入了特征的信息熵作为分母，来对高基数类别进行惩罚。所以C4.5对特征值数目较少的特征有所偏好，既可以处理离散型数据，也可以处理连续型数据，可以是多叉树。

• КОРЗИНА – Индекс Джини

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

  $$\operatorname{Gini}(D)=1-\sum_{k=1}^{n}\left(\frac{\left|C_{k}\right|}{|D|}\right)^{2}$$

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

  $$\operatorname{Gini}(D \mid A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \operatorname{Gini}\left(D_{i}\right)$$

​总结：CART既可以分类，也可以回归；既可以处理离散型数据也可以处理连续型数据；但只能是二叉树，分裂过的特征还可以再次分裂。

2.4 При каких обстоятельствах разделение прекращается?

1. Прирост информации до и после разделения меньше заданного порога
2. Количество выборок текущего узла меньше заданного порога
3. Образцы текущего узла принадлежат к той же категории
4. Когда дерево достигает определенной глубины

2.5 Как обрезать?

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

2.6 Преимущества и недостатки дерева решений

преимущество

• Простота расчета и интерпретация
• Нет необходимости нормализовать данные

недостаток

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

3 Случай дерева решений

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

3.1 Дерево классификации

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

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

В задаче классификации предположим, что у нас есть$K$класс, точки выборки принадлежат$k$Вероятность класса$p_k$, то индекс Джини распределения вероятностей определяется как

Если задача бинарной классификации, если точка выборки принадлежит к первому классу, вероятность$p$, то индекс Джини распределения вероятностей равен

для образца$D$, номер$|D|$, предполагая$K$категория,$k$Количество категорий$C_k$, то образец$D$Выражение индекса Джини

для образца$D$, номер$|D|$, согласно собственному значению признака A,$D$разделен на$D_l$и$D_r$, то при условии признака А выборка$D$Коэффициент Джини выражается как

Возьмем в качестве примера набор кредитных данных.

Данные заявки на получение кредита, указанные в таблице выше, с$А_1, А_2, А_3, А_4$Обозначает возраст, наличие работы, наличие собственного дома и кредитной ситуации с четырьмя характеристиками и использует 1, 2, 3 для представления значений молодости, среднего возраста и старости; используя 1, 2 для представления работы и своего собственный дом Да и Нет, значение 1, 2, 3 для очень хорошие, хорошие и справедливые условия кредита.

Найдите функции$A_1$Индекс Джини

так как$Gini(D,A_1=1)$и$Gini(D,A_1=3)$равное и наименьшее, поэтому$A_1=1$и$A_1=3$все как$A_1$лучшая точка разделения.

Найдите функции$А_2, А_3$Индекс Джини:

из-за$А_2, А_3$Существует только одна точка разделения, поэтому они являются лучшими точками разделения.

Найдите функции$A_4$Индекс Джини:

из-за$Gini(D,A_4=3)$минимум, так$A_4=3$все как$A_4$лучшая точка разделения.

в$А_1, А_2, А_3, А_4$Среди четырех характеристик$Джини (D, A_3 = 1) = 0,27$минимум, поэтому выберите функции$A_3$это лучшая функция,$A_3=1$для лучшей точки разделения. в соответствии с$A_3=1$Разделите набор данных на две части, чтобы корневой узел генерировал два дочерних узла. Затем продолжайте использовать описанный выше метод в двух дочерних узлах.$А_1, А_2, А_4$Выберите оптимальную функцию и ее оптимальную точку разделения.

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

3.2 Дерево регрессии

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

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

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

Чем больше дисперсия, тем более изменчивы данные; чем меньше дисперсия, тем менее изменчивы данные.

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

Набор обучающих данных показан в таблице выше.$x$Диапазон значений: [0,5, 10,5],$y$Диапазон значений составляет [5.0, 10.0], и обучается модель дерева регрессии.

Во-первых, оптимизация задачи

Решение для точек разделения обучающих данных$s$;

в

легко найти$R_1,R_2$в пределах которого минимизируется ошибка квадрата потерь$с_1, с_2$за

здесь$Н_1, Н_2$да$R_1,R_2$количество образцов.

Найдите точки среза тренировочных данных.По заданным данным рассмотрим следующие точки среза: 1,5, 2,5, 3,5, 4,5, 5,5, 6,5, 7,5, 8,5, 9,5

Для каждой точки сегментации нетрудно найти соответствующую$Р_1, Р_2, с_1, с_2$и

Например, когда$s = 1.5$час,$R_{1}=\{1\}, R_{2}=\{2,3, \cdots, 10\}, c_{1}=5.56, c_{2}=7.50$,

Получите все значения s и соответствующие m(s), результаты следующие:

Как показано в приведенной выше таблице, когда s=6,5, m(s) достигает минимального значения, поэтому s=6,5 является наилучшей точкой разделения.

4 python реализует дерево решений

4.1 Построить дерево решений

шаг

1. Создать экземпляр, построить объект модели оценки
2. Обучите модель через интерфейс модели
3. Получите необходимую информацию через интерфейс модели

Дерево решений в sklearn

1. Восемь параметров: критерий, два параметра, относящиеся к случайности (random_state, splitter), Пять параметров обрезки (max_depth, min_samples_split, min_samples_leaf, max_feature, min_impurity_decrease)
2. Атрибут: feature_importances_
3. Четыре интерфейса: подгонка, оценка, применение, прогнозирование

код

def buildTree():
    # 加载红酒数据集
    wine = load_wine()
    print(wine.data.shape)

    print(wine.target)

    # 将wine整理成一张表
    pd.concat([pd.DataFrame(wine.data), pd.DataFrame(wine.target)], axis=1)
    print(wine.feature_names)
    print(wine.target_names)

    # 划分训练集和测试集
    Xtrain, Xtest, Ytrain, Ytest = train_test_split(wine.data, wine.target, test_size=0.3)
    print(Xtrain.shape)
    print(Xtest.shape)

    # 建立模型
    # random_state 用来设置分支中的随机模式的参数； splitter用来控制决策树中的随机选项
    # max_depth 限制树的最大深度；min_samples_leaf & min_samples_split 一个节点在分之后的每个子节点最少包含多少个训练样本
    clf = tree.DecisionTreeClassifier(criterion="entropy", random_state=30)
    clf.fit(Xtrain, Ytrain)
    score = clf.score(Xtest, Ytest)
    print(score)

    # 画出一棵树
    import graphviz
    feature_name = wine.feature_names
    dot_data = tree.export_graphviz(clf, feature_names=feature_name, class_names=['class_0', 'class_1', 'class_2'],
                                    filled=True, rounded=True)
    graph = graphviz.Source(dot_data)
    print(graph)

    # 探索决策树的特征重要性
    print(clf.feature_importances_)
    feature_importance = [*zip(feature_name, clf.feature_importances_)]
    print(feature_importance)

    # apply（）返回每个测试样本所在的叶子节点的索引
    print(clf.apply(Xtest))
    # predict（）返回每个测试样本的分类结果:返回的是一个大小为n的一维数组，一维数组中的第i个值为模型预测第i个预测样本的标签
    print(clf.predict(Xtest))
    # predict_proba返回的是一个n行k列的数组，第i行第j列上的数值是模型预测第i个预测样本的标签为j的概率。此时每一行的和应该等于1
    print(clf.predict_proba(Xtest))

4.2 Определение оптимальных параметров обрезки с помощью поиска по сетке

def max_parameter(Xtrain, Ytrain, Xtest, Ytest):
    test = list()
    for i in range(10):
        clf = tree.DecisionTreeClassifier(max_depth=i + 1, criterion="entropy", random_state=30, splitter="random")
        clf = clf.fit(Xtrain, Ytrain)
        score = clf.score(Xtest, Ytest)
        test.append(score)

    plt.plot(range(1, 11), test, color="red", label="max_depth")
    plt.legend()
    plt.show()

4.3 K-кратная перекрестная проверка

def cross_val():
    """
    K折交叉验证
    :return:
    """
    from sklearn.datasets import load_boston
    from sklearn.model_selection import cross_val_score
    from sklearn.tree import DecisionTreeRegressor
    boston = load_boston()
    regressor = DecisionTreeRegressor(random_state=0)
    val_score = cross_val_score(regressor, boston.data, boston.target, cv=10, scoring="neg_mean_squared_error")
    print(val_score)

4.4 Прогноз выживших на Титанике

def titanic_example():
    import pandas as pd
    from sklearn.tree import DecisionTreeClassifier
    from sklearn.model_selection import train_test_split
    from sklearn.model_selection import GridSearchCV
    from sklearn.model_selection import cross_val_score
    import matplotlib.pyplot as plt
    import numpy as np

    data = pd.read_csv(r"data.csv", index_col=0)
    print(data.head())
    print(data.info())

    # 删除缺失值过多的列，和观察判断来说和预测的y没有关系的列
    data.drop(["Cabin", "Name", "Ticket"], inplace=True, axis=1)

    # 处理缺失值，对缺失值较多的列进行填补，有一些特征只确实一两个值，可以采取直接删除记录的方法
    data["Age"] = data["Age"].fillna(data["Age"].mean())
    data = data.dropna()

    # 将二分类变量转换为数值型变量
    # astype能够将一个pandas对象转换为某种类型，和apply(int(x))不同，astype可以将文本类转换为数字，用这个方式可以很便捷地将二分类特征转换为0~1
    data["Sex"] = (data["Sex"] == "male").astype("int")

    # 将三分类变量转换为数值型变量
    labels = data["Embarked"].unique().tolist()
    data["Embarked"] = data["Embarked"].apply(lambda x: labels.index(x))

    # 查看处理后的数据集
    print(data.head())

    # 提取标签和特征矩阵， 分测试集和训练集
    X = data.iloc[:, data.columns != "Survived"]
    y = data.iloc[:, data.columns == "Survived"]

    Xtrain, Xtest, Ytrain, Ytest = train_test_split(X, y, test_size=0.3)

    # 修正测试集和训练集的索引
    for i in [Xtrain, Xtest, Ytrain, Ytest]:
        i.index = range(i.shape[0])

    # 查看分好的训练集和测试集
    print(Xtrain.head())

    # 建立模型
    clf = DecisionTreeClassifier(random_state=25)
    clf = clf.fit(Xtrain, Ytrain)
    score_ = clf.score(Xtest, Ytest)
    print(score_)
    score = cross_val_score(clf, X, y, cv=10).mean()
    print(score)

    # 在不同max_depth下观察模型的拟合状况
    tr = []
    te = []
    for i in range(10):
        clf = DecisionTreeClassifier(random_state=25
                                     , max_depth=i + 1
                                     , criterion="entropy"
                                     )
        clf = clf.fit(Xtrain, Ytrain)
        score_tr = clf.score(Xtrain, Ytrain)
        score_te = cross_val_score(clf, X, y, cv=10).mean()
        tr.append(score_tr)
        te.append(score_te)
    print(max(te))
    plt.plot(range(1, 11), tr, color="red", label="train")
    plt.plot(range(1, 11), te, color="blue", label="test")
    plt.xticks(range(1, 11))
    plt.legend()
    plt.show()

    # 用网格搜索调整参数
    gini_thresholds = np.linspace(0, 0.5, 20)

    parameters = {'splitter': ('best', 'random')
        , 'criterion': ("gini", "entropy")
        , "max_depth": [*range(1, 10)]
        , 'min_samples_leaf': [*range(1, 50, 5)]
        , 'min_impurity_decrease': [*np.linspace(0, 0.5, 20)]}

    clf = DecisionTreeClassifier(random_state=25)
    GS = GridSearchCV(clf, parameters, cv=10)
    GS.fit(Xtrain, Ytrain)

    print(GS.best_params_)
    print(GS.best_score_)

использованная литература

1. Статистические методы обучения, Ли Ханг. 2012.03 Издательство Университета Цинхуа