机器学习--分类算法--决策树算法理论
2 决策树构建过程是一种递归过程，所以必须给定停止条件，否则过程不会停止
2 方式二 叶子节点的不纯度总和（决策树损失函数），数值越小，不纯度越小（损失越小），分类效果越好
2 回归树的评价标准一般采用R^2、MSE、RMSE、MAE
一 信息量
1 信息量是指一个事件所蕴含的信息量大小
- 一个事件发生的概率越大，所蕴含的信息量越小
- 一个事件发生的概率越小，所蕴含的信息量越大
注意：对于必然事件和不可能事件而言，信息量为0
2 信息量的度量
1）熵
相关公式
- X的熵：
- (X,Y)的联合熵：
- (X|Y)的条件熵：
- 熵的增益
- 熵的增益率
熵的性质
熵越大，信息越不纯
熵增益（熵增益率）越大，信息纯度损失越大
2）基尼系数
基尼系数的相关公式
- 基尼系数
- 联合基尼系数
- 条件基尼系数
- 基尼增益
- 基尼增益率
基尼系数的性质
基尼系数越大，信息越不纯
基尼增益越大，信息纯度损失越大
3）错误率
二 算法原理
1 决策树构造关键是选择特征属性以及分裂特征属性（树结构）
- 选择特征属性，采用信息量度量公式（增益度或者增益率）
- 分裂特征属性，采用信息量度量公式（增益度或者增益率）
2 决策树构建过程是一种递归过程，所以必须给定停止条件，否则过程不会停止
- 子结点只有一种类型的样本的时候，停止分裂该子结点（常会使树节点过多，极易过拟合，一般不采用）
- 子结点的样本个数小于阈值的时候，停止分裂该子结点
- 树的最大深度等等
注意：
- 决策树算法是一种贪心算法，即仅考虑当前数据特征下最好的分割方式，无法进行回溯操作
- 决策树算法常用ID3、C4.5 、CART
ID3：内部使用熵增益作为纯度损失度量方式，但是会产生多叉树，依赖特征属性较多的特征作为最优特征
C4.5：内部使用熵增益率作为纯度损失度量方式，但是会产生多叉树，多次对数据集进行扫描和排序，效率低
CART：内部使用基尼增益率作为纯度损失度量方式，产生二叉树，可以处理分类与回归问题
- 决策树中内部节点表示特征属性，叶子节点表示一种类别
三 算法评价标准
1 方式一 分类算法常用的混淆矩阵
准确率 精确率 召回率 F1值 ROC曲线的AUC面积等等
2 方式二 叶子节点的不纯度总和（决策树损失函数），数值越小，不纯度越小（损失越小），分类效果越好
四 回归树与分类树的区别
1 回归树一般采用叶子节点内样本的均值作为预测值
2 回归树的评价标准一般采用R^2、MSE、RMSE、MAE
注意：回归树选择特征属性以及分裂特征属性需要将连续数值离散化
五 决策树优化策略
1 随机森林（关注下一篇博客，推荐使用）
2 剪枝优化
1）前置剪枝/预先剪枝（优化效果差）
构建决策树的过程中，提前停止构建，例设定叶子节点样本个数阈值、树的最大深度等等
2）后置剪枝（效率低）
第一种：使用单一叶子节点替代整棵子树
算法流程：给定决策树
第一步：计算该决策树所有非叶子节点的剪枝系数
第二步：选择最小剪枝系数，将其子节点删除，存在多个最小剪枝系数，选择包含样本最多的节点，将其子 结点删除，得到
第三步：重复上述步骤，直到剪枝决策树仅剩一个节点，得到
第四步：使用验证集，得到最优子树
如何计算剪枝系数（对于内部节点而言（仅仅计算该子树））：
剪枝之前：
剪枝之后：
我们希望剪枝前后的损失相等，从而：
第二点：将一棵子树完全替代另一棵子树（不推荐使用）