（每日一题）运算决策树的构建策略

决策树由节点和分支组成：（详细参考数据结构书籍）

节点分为三种类型：根节点、内部节点和叶节点。 分支：用于连接各个节点。

决策树分为以下几种结构：

决策树学习的目的是产生具有强泛化能力的决策树。 决策树如下

也就是说，使用多个判断语句进行判断，可以方便地转化为if-then语句：

决策树的生成必须遵循互斥和完备的规则（互斥和完备：每个实例都被一条且只有一条路径或规则覆盖）

决策树的构建

策略：自上而下、分而治之

特征选择是指从众多特征中选择一个特征作为当前节点的分裂标准。

如何选择特征有不同的定量评估方法，从而产生不同的决策树。

==算法改进（C4.5算法）： ==基于信息增益进行分类的决策树算法存在缺陷，具体表现在：偏好可能取值数量较多的属性，因此增益率为介绍了。 一个概念，可以在信息增益的基础上消除数量对属性的影响，使结果更加合理。

基尼指数（CART算法）：该算法放弃信息熵，使用基尼指数进行运算。

决策树的一般构建步骤（根据信息熵）：

首先我们需要根据这个公式计算根节点的信息熵（根节点的分类实际上是根据最终判别结果进行分类）

以鸢尾花的分类为例（鸢尾花有四个特征，即萼片长、萼片宽、花瓣长、花瓣宽）：

为了便于理解，这里假设鸢尾花的每个特征只有三个值，即长、中、短。

==|y|：==表示划分的类别数。 识别鸢尾花时只有三个标签（iris-或iris-或iris-），所以|y| = 3 虹膜分类

==Pk：==这个变量的k也是按照iris的类别来分类的，即每个类别在总集合中所占的比例。 例如，设虹膜-的比重为P1，虹膜-的比重为P2，虹膜-的比重为P3，则P1+P2+P3 = 1

因此，我们可以计算根节点的信息熵ENT(D)（ENT(D)的值越小，D的纯度越高），判断根节点是否纯净。 如果不纯，则需要进行以下划分。

然后选择根节点，即使用哪个特征作为第一类分类的根节点。 仍然得到信息熵，但是此时得到的信息熵是根据每个特征来划分的。 假设首先求虹膜花萼长度的信息熵。 步骤如下：

花萼长度包括长花萼（D1）、中花萼（D2）和短花萼（D3）。

先求Pk，找出长花萼中每种类型（iris-或iris-或iris-）占长花萼总数的比例，即为每种类型对应的P，P（长花萼iris-） + P(长萼鸢尾-) + P(长萼鸢尾-) = 1，但是此时y仍然是根据标签确定的，也就是说要代入的数据Pk是每个标签在每个类别，而不是该类别占总数的比例

中花萼和短花萼的信息熵以同样的方式计算。

由此，可以获得每个花萼长度的信息熵D1、D2和D3。

也就是说，必须计算每个特征的每个属性的信息熵。

然后用这个公式求这个特征的信息增益：

公式前半部分：Ent(D)是根节点的信息熵，也就是上面第一步得到的。

公式后半部分：V代表特征中属性的个数。 在上面的例子中，V=3，且|D| 分母中表示特征中参与运算的数据数量。 |DV| 表示Dv属性的数量。 ，Ent(Dv)表示Dv的信息熵。 上述步骤已经得到，可以直接计算。

然后对每个特征进行上述操作，就可以得到每个特征的信息增益。 假设获得的信息增益为（信息增益越大，分类越纯）：

Gain(D, 花萼长度), Gain(D, 花萼宽度), Gain(D, 花瓣长度), Gain(D, 花瓣宽度)，假设花瓣长度的信息增益最大，那么花瓣长度将取代前面提到的根节点作为新的根节点，第一次划分得到的分支为：

注意：当下面继续除法时，就进入了递归。 这时要小心排除花瓣长度的特征，因为决策树在计算时必须保持互斥的特征，并且需要特别注意假设在花瓣长的分支继续分类时，只有D1 {1,4,7,10...}数据行参与分类，其他行不参与本次计算。

参与计算的特征集是花萼长度、花萼宽度、花瓣宽度三个特征。 这时就必须根据D1按照上面介绍的方法计算出各个特征的信息增益。 如果有多个具有相同信息增益的特征，则选择其中之一。 分类特征

最终就可以得到一棵完整的决策树

值得一提的是，假设分类时的特征数据不是长、中、短等简单条件，而是都是数字，则决策树中的中间节点可以按照临界值进行划分，即a 该值为阈值。 如果特征中的值大于它，则它属于某个类别。 如果小于它，则属于另一类。 可以制定多个阈值来划分多次。

决策树剪枝

从对决策树泛化性能的影响来看，与采用不同方法构建决策树相比，剪枝方法和剪枝程度对决策树泛化性能的影响更为显着。

剪枝是防止决策树过拟合的一种手段（过拟合：测试集结果完全拟合训练集，即测试集和训练集完全一样）

决策树剪枝极大地提高了决策树的性能，尤其是当数据有噪声时。

修剪的基本策略是：

剪枝的判断是基于剪枝前的准确率和剪枝后的准确率的比较。 如果准确率下降，则不会对该分支进行剪枝； 否则，如果移除分支，则需要对中间节点进行一一比较。

剪枝前与剪枝后对比：

时间成本：过拟合和欠拟合风险泛化性能连续值和缺失值处理

连续值处理：

在许多情况下，处理连续数据。 由于连续属性的可能取值数量不再受到限制，因此无法直接根据连续属性的可能取值来划分节点。 处理这类数据的方法是：连续属性离散化：基本思想是在这个连续值上区分出几个区间，根据不同的区间来划分数据。 常用的方法是二分法

缺失值处理：

很多情况下，都会遇到有缺失值的数据。 但如果丢弃有缺失值的数据，就会给数据带来很大的浪费。 因此，需要对数据进行划分。 怎么处理呢？ 选择划分属性，如果样本属性值缺失，如何划分数据。求解的基本思路是：样本加权，权重划分

划分计算时，就用非缺失样本来计算，比如计算信息熵，但注意计算信息增益率时是有权重的。假设计算时总共有19条样本数据，但只有15条由于样本数据较为完整，因此在计算信息增益率时需要赋予15/19的权重。

决策树的本质

如何使用决策树

可以直接使用.tree中的模型进行计算。 使用方法与将模型应用到支持向量机的方法类似。 在测试鸢尾花数据集时，错误率高于支持向量机的错误率。

"""
-*- coding: utf-8 -*-
@Time    : 2021/8/5 8:57
@Author  : wcc
@FileName: DecisionTree.py
@Software: PyCharm
@Blog    ：https://blog.csdn.net/qq_41575517?spm=1000.2115.3001.5343
"""
from sklearn.tree import DecisionTreeClassifier
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
class Iris:
    def __init__(self, file_name, data_set, labels_set, normal_data_set,  data_division):
        self.fileName = file_name
        self.dataMat = data_set
        self.labelsMat = labels_set
        self.normalDataSet = normal_data_set
        self.dataDivision = data_division
    # 数据预处理
    def iris_processData(self):
        fr = open(self.fileName)
        numOfLines = len(fr.readlines())
        # 此处一定记得要把标签排除在外
        dataMat = np.zeros((numOfLines, 4))
        # 标签单独成一列
        labelsMat = []
        fr.seek(0, 0)
        index = 0
        for line in fr.readlines():
            line = line.strip()
            listLine = line.split(',')
            dataMat[index, :] = listLine[0:4]
            if listLine[-1] == 'Iris-setosa':
                labelsMat.append(1)
            if listLine[-1] == 'Iris-versicolor':
                labelsMat.append(2)
            if listLine[-1] == 'Iris-virginica':
                labelsMat.append(3)
            index += 1
        labelsMat = np.array(labelsMat)
        self.dataMat = dataMat
        self.labelsMat = labelsMat
    # 数据归一化(0-1归一化)
    def iris_normal(self):
        colDataMax = self.dataMat.max(0)
        colDatamin = self.dataMat.min(0)
        normalDataSet = np.zeros(self.dataMat.shape)
        normalDataSet = (self.dataMat - colDatamin)/(colDataMax - colDatamin)
        self.normalDataSet = normalDataSet
    # 决策树对测试集进行测试
    def iris_decision(self):
        totSize = int(self.normalDataSet.shape[0])
        trainSize = int(self.normalDataSet.shape[0]*self.dataDivision)
        testSize = int(self.normalDataSet.shape[0]*(1-self.dataDivision))
        result = []
        errorCount = 0
        errorRecords = {}
        correctRecords = {}
        index = 0
        # 模型定义
        model = DecisionTreeClassifier()
        # 模型函数,参数为样本数据和数据标签
        model.fit(self.normalDataSet[0:trainSize, :], self.labelsMat[0:trainSize])
        # 模型测试,predict()方法为预测方法，参数为测试集数据
        result = model.predict(self.normalDataSet[trainSize:totSize, :])
        for i in range(int(testSize)):
            if self.labelsMat[trainSize + i] != result[i]:
                errorCount += 1
                errorRecords[i] = result[i]
                correctRecords[i] = self.labelsMat[trainSize + i]
        print('错误个数：')
        print(errorCount)
        print('错误位置及错误值：')
        print(errorRecords)
        print('相应位置的正确值：')
        print(correctRecords)
        print('正确率：%f%%' % ((1-errorCount/testSize)*100))
if __name__ == '__main__':
    fileName = 'iris.txt' # 'datingTestSet.txt'# 文件路径
    dataMat = [] # 数据集（自己读取）
    labelsMat = [] # 标签集（自己读取）
    normalDataSet = [] #归一化后的数据集
    dataDivision = 0.8 # 数据集中训练集和测试集的划分比例
    iris = Iris(file_name=fileName, data_set=dataMat, labels_set=labelsMat, normal_data_set=normalDataSet, data_division=dataDivision)
    iris.iris_processData()
    iris.iris_normal()
    iris.iris_decision()

你可以编写自己的决策树算法，并根据算法思想进行优化。