学习目标
- 了解信息增益率的计算公式
- 知道ID3 和 C4.5决策树的优缺点
- 了解基尼指数的计算公式
- 了解基尼指数对于不同特征的计算方式
- 了解回归决策树的构建原理
1. 信息增益率计算公式¶
- Gain_Ratio 表示信息增益率
- IV 表示分裂信息、内在信息
- 特征的信息增益 ➗ 内在信息
- 如果某个特征的特征值种类较多，则其内在信息值就越大。即：特征值种类越多，除以的系数就越大。
- 如果某个特征的特征值种类较小，则其内在信息值就越小。即：特征值种类越小，除以的系数就越小。
信息增益比本质： 是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。惩罚参数：数据集D以特征A作为随机变量的熵的倒数。
1.1信息增益率计算举例
特征1的信息增益率：
- 信息增益：
0.5408520829727552 - 分裂信息：
-4/6*math.log(4/6, 2) -2/6*math.log(2/6, 2)=0.9182958340544896 - 信息增益率：
信息增益/分裂信息=0.5408520829727552/0.9182958340544896=0.5889736868180786
特征2的信息增益率：
- 信息增益：1
- 分裂信息：
-1/6*math.log(1/6, 2) * 6=2.584962500721156 - 信息增益率：
信息增益/信息熵=1/2.584962500721156=0.38685280723454163
由计算结果可见，特征1的信息增益率大于特征2的信息增益率，根据信息增益率，我们应该选择特征1作为分裂特征
1.2. ID3和C4.5对比
- ID3算法缺点
- ID3算法不能处理具有连续值的属性
- ID3算法不能处理属性具有缺失值的样本
- 算法会生成很深的树，容易产生过拟合现象
- 算法一般会优先选择有较多属性值的特征，因为属性值多的特征会有相对较大的信息增益，但这里的属性并不一定是最优的
- C4.5算法的核心思想是ID3算法，对ID3算法进行了相应的改进。
- C4.5使用的是信息增益比来选择特征，克服了ID3的不足。
- 可以处理离散型描述属性，也可以处理连续数值型属性
- 能处理不完整数据
- C4.5算法优缺点
- 优点：分类规则利于理解，准确率高
- 缺点
- 在构造过程中，需要对数据集进行多次的顺序扫描和排序，导致算法的低效
- C4.5只适合于能够驻留内存的数据集，当数据集非常大时，程序无法运行
- 无论是ID3还是C4.5最好在小数据集上使用，当特征取值很多时最好使用C4.5算法
4. Cart树简介
Cart模型是一种决策树模型，它即可以用于分类，也可以用于回归，其学习算法分为下面两步：
（1）决策树生成：用训练数据生成决策树，生成树尽可能大
（2）决策树剪枝：基于损失函数最小化的剪枝，用验证数据对生成的数据进行剪枝。
分类和回归树模型采用不同的最优化策略。Cart回归树使用平方误差最小化策略，Cart分类生成树采用的基尼指数最小化策略。
Scikit-learn中有两类决策树，他们均采用优化的Cart决策树算法。一个是DecisionTreeClassifier一个是DecisionTreeRegressor回归。
5. 基尼指数计算公式
- 信息增益（ID3）、信息增益率值越大（C4.5），则说明优先选择该特征。
- 基尼指数值越小（cart），则说明优先选择该特征。
6. Cart分类树原理¶
如果目标变量是离散变量，则是classfication Tree分类树。
分类树是使用树结构算法将数据分成离散类的方法。
（1）分类树两个关键点：
将训练样本进行递归地划分自变量空间进行建树‚用验证数据进行剪枝。
（2）对于离散变量X（x1…xn）处理：
分别取X变量各值的不同组合，将其分到树的左枝或右枝，并对不同组合而产生的树，进行评判，找出最佳组合。如果只有两个取值，直接根据这两个值就可以划分树。取值多于两个的情况就复杂一些了，如变量年纪，其值有“少年”、“中年”、“老年”，则分别生产{少年，中年}和{老年}，{少年、老年}和{中年}，{中年，老年}和{少年}，这三种组合，最后评判对目标区分最佳的组合。因为CART二分的特性，当训练数据具有两个以上的类别，CART需考虑将目标类别合并成两个超类别，这个过程称为双化。这里可以说一个公式,n个属性，可以分出(2^n-2)/2种情况。
