文章目录1主题2理论与算法原理2.1决策树模型的构成2.2决策树的数据结构2.3决策树的功能2.4实现决策树模型的算法2.5决策树生成算法原理3算法比较分析3.1算法摘要3.2算法的基础3.3算法细节3.5例3.5 缩放3.5.2 C4.5算法3.5.3 CART算法3.5.4例题所示各算法的差异4
1主题决策树模型是树模型，可以分类和回归。 决策树的训练是决策树的构建过程。 为了实现最佳决策树，需要在实际情况中选择不同的算法，在此对决策树的三种算法进行分析比较。 2理论与算法原理2.1构成决策树模型的决策树模型由节点和有向边组成，其中节点表示特征空间的子集，有向边表示一个划分规则，根节点到叶节点的有向边表示一个决策路径。 2.2决策树的数据结构决策树可以是二叉树，也可以是二叉树。 2.3决策树功能决策树实现的分类和预测功能，在分类能力方面非常强大，很多算法都是让机器在分类过程中找到最佳分类特征并进行分类，从而达到最佳决策树。 2.4实现决策树模型的算法常见决策树算法有ID3、C4.5和分类回归树(CART )三种模型。 2.5决策树生成算法原理
决策树学习的算法通常是递归选择最佳特征，根据该特征分割训练数据，并对各子数据集给出最佳分类的过程。 这个过程对应特征空间的划分，也对应决策树的构建。
(1) .开始)构建根节点，将所有训练数据放置在根节点上，选择一个最佳特征。 根据这一特点，将训练数据集划分为子集，使每个子集在当前条件下有最佳分类。 )2) .这些子集基本正确分类后，构建叶节点，并将这些子集分配给对应的叶节点。 )3) .如果还有不能正确分类的子集，则为这些子集选择新的最佳特征，然后将其分割构建对应的节点。 递归进行，直到所有训练数据的子集大致正确分类或没有适当的特征。 )4) .各子集被分类为叶节点，即有明确的类，由此生成决策树。 3算法比较分析3.1算法归纳历史流行的决策树模型有ID3、C4.5、分类回归树(CART ) 3种。 C4.5是ID3的高级版，建树过程相似，计算不纯度的方式不同。 可以是二叉树，也可以是二叉树，但CART只能是二叉树，可以分类也可以回归。
3.2算法的基础信息熵：熵表示不确定度。 信息熵越大，信息量就越大。
公式：
其中，n是数据集合中的样本数目，且Ni是第I类别数据的子集的样本数目。 显而易见，p(Xi )表示此类别在总样本中出现的频率。 计算结果计算出信息熵，即样本分类分布的散布程度。 熵越大，表示数据集中不同类别的样本分布越均衡，数据集越不纯。
经验熵：在现有条件下再次进行，得到新的熵值，即x后y的不确定度
公式：
经验性熵表示每个子集内样本的类分布的平均散布程度，也可以认为是数据集分成多个子集后的平均不纯度。
信息增益：信息增益相对于特征。 因此，特征a的训练数据集d的信息增益g(d，a )被定义为集合d的经验熵h ) d )和特征a的给定条件下的d的经验条件熵h ) d|a )之间的差。
(g ) d，a )=h ) d ) h ) d ) a )的公式
信息增益表示在基于特征a的值将数据集d划分成m个子集之后每个子集的平均不确定减少量。
信息增益比：训练集d中的特征a的信息增益比g_r(d，a )被定义为熵h_a ) d )与信息增益g ) d，a )的特征之比
公式：
ha(d )表示特征a对训练集d的分割能力。 信息增益比本质上是与信息增益相乘的加权系数，希望即使增加信息也不要使分割变得过细。 当特征a的取值集合小时，权重系数大意味着鼓励该特征。
基尼指数(Gini Index )基尼系数最先应用于经济学，主要用于衡量分配公平程度的指标。 决策树CART算法通过基尼指数测定数据的不纯度或不确定性。
公式：
Gini(d，a )表示特征a分割的集合d的不确定性，基尼指数越大，不确定性越大。 因此，基尼指数越小，就越有必要将特征作为节点来寻找。
剪枝：剪枝是指删除一个子树的所有子节点，将根节点作为叶节点。 修剪分裂前后分类误差不大的子树，可以降低决策树的复杂度，降低发生拟合的概率。 3.3算法细节ID3算法： ID3算法是决策树的典型结构方法，在内部用信息熵和信息增益构建； 在每次反复中选择信息增益最大特征属性作为分割属性
优点：决策树构建速度快，实现简单
缺点()1) .计算依存特征数多的特征，属性数最多的特征不一定是最佳的
)2).ID3算法不是增量算法，不能重复选择属性
)3).ID3算法是单变量决策树，不考虑特征属性之间的关系
)4) .抗干扰能力差，对缺失值极为敏感
)5) .只适合小规模数据集，需要将数据放入内存
(6) .仅适用于离散数据集C4.5算法)基于ID3算法，使用信息增益比代替提出的算法ID3算法中的信息增益来进行算法优化，并在树的构建过程中进行剪枝操作能够自动进行连续属性离散化处理； 当选择分割属性时，C4.5算法选择信息增益比最大的属性
优点： (1) .发生
规则易于理解(2).准确率比较高
(3).实现简单
缺点：(1).对数据集需要进行多次顺序扫描和排序，效率较低
(2).只适合小规模数据集，需要将数据放入内存 CART算法：使用基尼系数作为数据纯度量化指标来构建的决策树算法就叫做CART（分类回归树）算法。CART算法使用基尼增益作为分隔属性选择的标准，选择基尼增益最小的作为当前数据集的分隔属性；可用于分类和回归两类问题；CART构建的树是二叉树。
3.4算法对比
3.5例
已知以社会调查，调查人们对工作好与不好的评判，评判因素主要有工资、压力、平台。工资1为高工资，0为低工资；压力1为压力大，压力0为压力小；平台分别为0、1、2，代表着平台降低。接下来会对此表用三种算法进行决策分类，表如下表所示
ID3算法选择信息增益最大的特征属性为分割属性
计算整个集合的信息熵：H(D)=-(3/8 log_2〖3/8+5/8 log_2〖5/8〗 〗)=0.95
计算工资的经验条件熵：H(D|工资)= 3/8*(-3/3 log_2〖3/3-0/3 log_2〖0/3〗 〗 )+5/8*(-3/5 log_2〖3/5-2/5 log_2〖2/5〗 〗 )=0.63
得到工资的信息增益为：g(D,工资)=H(D)-H(D|工资)=0.95-1.63=0.34
同理可得：g(D,压力)=H(D)-H(D|压力)=0.16
g(D,平台)=H(D)-H(D|平台)=0.36
因为平台的的信息增益最大，所以选择平台优先选择平台作为特征属性分割。进行迭代该过程，此时数据集被分为三个模块，以三个模块为总数据集进行上述迭代操作，算出其他特征的信息增益，选出信息增益最大的特征作为特征属性再次进行分割。经过计算得出工资的信息增益大于压力的信息增益，所以以工资作为特征属性再次分割，得到多叉树如下图所示
C4.5算法选择信息增益比最大的特征属性为分割属性
上述内容已算出信息熵与信息增益
计算工资特征的熵：H(工资)=-( 3/8 log_2〖3/8+5/8 log_2〖5/8〗 〗)=0.95
同理计算出：H(压力)=0.95
H(平台)=1.56
计算信息增益比：g_R (D,工资)=(g(D,工资))/(H(工资))=0.34/0.95=0.36
同理计算出：g_R (D,压力)=0.17
g_R (D,压力)=0.23
因为工资的的信息增益比最大，所以选择平台优先选择工资作为特征属性分割。进行迭代该过程，此时数据集被分为两个模块，以两个模块为总数据集进行上述迭代操作，算出其他特征的信息增益比，选出信息增益比最大的特征作为特征属性再次进行分割。经过计算得出平台的信息增益大于压力的信息增益，所以以平台作为特征属性再次分割，得到多叉树如下图所示
CART算法选择基尼系数最小的特征属性为分割属性
计算基尼系数并计算出基尼增益：
Gini(D,工资)=3/8*(1-(3/3)2-(0/3)2 )+5/8*(1-(3/5)2-(2/5)2 )=0.3
同理可计算出：
Gini(D,平台)=0.37
因为平台有3的属性，CART只能形成二叉树，所以需要对三个条件都进行基尼增益运算：
Gini(D,平台=0)=0.3
Gini(D,平台=1)=0.37
Gini(D,平台=2)=0.46
因为工资和平台=0的的基尼增益最小，所以选择平台优先选择工资或平台=0作为特征属性分割，在此可随意选择，此处选择工资。进行迭代该过程，此时数据集被分为两个模块，以两个模块为总数据集进行上述迭代操作，算出其他特征的基尼增益，选出基尼增益最小的特征作为特征属性再次进行分割。经过计算得出平台=0的信息增益最小，所以以平台=0作为特征属性再次分割，得到多叉树如下图所示
学习机器学习，了解人工智能，让我们了解到了计算机科研的前瞻。决策树是机器学习的一小部分较为简单的模块，学习该模块让我也回顾了不少的数学理论知识，也学习了算法的精妙。很佩服发明该算法的人，很感叹知识的奇妙，感叹到自己所掌握知识的贫乏。在之后应加强学习，好了解很多知识才能突破自己，升华人生。
5参考文献[1]卿来云, 过时的保温杯. 机器学习从原理到应用[M]. 第1版. 北京:人民邮电出版社, 2020年10月 :105-118.
[2]Jonny的ICU. 决策树的剪枝操作[EB/OL]. 2017年7月[2021年12月1日]. https://blog.csdn.net/m0_37338590/article/details/75266989.
[3]呆呆的猫. 机器学习实战（三）——决策树[EB/OL]. 2018年3月[2021年12月1日]. https://blog.csdn.net/jiaoyangwm/article/details/79525237?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163871318916780255211529%2522%252C%2522scm%2522%253A%252220140713.130102334…%2522%257D&request_id=163871318916780255211529&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2alltop_positive~default-1-79525237.pc_search_es_clickV2&utm_term=%E5%86%B3%E7%AD%96%E6%A0%91&spm=1018.2226.3001.4187.