标签：剪枝 ID3 算法 实验 增益 节点 决策树

实验一：决策树算法实验

【实验目的】

1. 理解决策树算法原理，掌握决策树算法框架；
2. 理解决策树学习算法的特征选择、树的生成和树的剪枝；
3. 能根据不同的数据类型，选择不同的决策树算法；
4. 针对特定应用场景及数据，能应用决策树算法解决实际问题。

【实验内容】

1. 设计算法实现熵、经验条件熵、信息增益等方法。
2. 针对给定的房贷数据集(数据集表格见附录1)实现ID3算法。
3. 熟悉sklearn库中的决策树算法；
4. 针对iris数据集，应用sklearn的决策树算法进行类别预测。

【实验报告要求】

1. 对照实验内容，撰写实验过程、算法及测试结果；
2. 代码规范化：命名规则、注释；
3. 查阅文献，讨论ID3、5算法的应用场景

实验过程

1.导包

 

2.设计算法实现熵、经验条件熵、信息增益等办法：

 

 

 输出结果

3.针对iris数据集，应用sklearn的决策树算法进行类别预测：

 

输出结果

 

 

 

 

 

 

 4.

 

 

 

输出结果

5.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

输出结果

 

6.

 

 

 

 

 

 

 输出结果

7.

 

 

 

输出结果

 

 

 

 

 

 8

 

 9.

 

 

 

 

 

 

 

【实验总结】

一、决策树的原理

1、 构造原理，如何构造出一个决策树，即选择哪些属性分别作为根节点、中间节点以及叶节点。

2、剪枝原理，即给决策树瘦身，把对分类效果促进不明显的节点取掉的过程，分为前剪枝和后剪枝两种。

前剪枝，是在构造决策树的过程中就进行剪枝。

后剪枝，是先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来泛化性能提升，则将该子树替换为叶结点。

二、ID3算法
1、 ID3算法是基于信息增益计算的，信息增益是指划分可以带来纯度的提高，信息熵的下降。

2、信息增益计算：是父亲节点和信息熵减去所以子结点的加权信息熵，这个权重系数为每个子结点在父节点出现的概率,即每个子结点的归一化信息熵。

3、计算每个属性的信息增益，选择信息增益最大的作为根节点即可，其他节点选择也类似。

三、C4.5算法
C4.5算法是ID3算法的改进，具体的，有以下四方面的改进：

采用信息增益率而非信息增益，解决了ID3倾向于选择取值多属性的问题。信息增益率=信息增益/属性熵。

采用悲观剪枝(属于后剪枝技术)，通过递归估算每个内部节点的分类错误率来判断是否对其进行剪枝，这种剪枝方法不再需要一个单独的测试数据集，解决了ID3构造决策树容易产生过拟合的情况，提升了决策树的泛化能力。

C4.5算法通过选择具有最高信息增益的划分所对应的阈值，可以离散化处理连续属性。

针对数据集不完整情况，即存在缺失值，C4.5可以进行处理，乘以加权系数即可。

 

标签：剪枝,ID3,算法,实验,增益,节点,决策树
From： https://www.cnblogs.com/yuanfangxingchen/p/16842826.html