决策树算法总结

精品文档 1欢迎下载 决策树决策树 研发二部 精品文档 I欢迎下载 文件标识 当前版本 1 0 作者 张宏超 文件状态 草稿 正式发布 正在修改 完成日期 2019 年 3 月 8 日 精品文档 II欢迎下载 目录目录 1 算法介绍 1 1 1 分支节点选取 1 1 2 构建树 3 1 3 剪枝 10 2 sk learn 中的使用 12 3 sk learn 中源码分析 13 精品文档 1欢迎下载 1 1 算法介绍算法介绍 决策树算法是机器学习中的经典算法之一 既可以作为分类算法 也可以作 为回归算法 决策树算法又被发展出很多不同的版本 按照时间上分 目前主要 包括 ID3 C4 5 和 CART 版本算法 其中 ID3 版本的决策树算法是最早出现的 可以用来做分类算法 C4 5 是针对 ID3 的不足出现的优化版本 也用来做分类 CART 也是针对 ID3 优化出现的 既可以做分类 可以做回归 决策树算法的本质其实很类似我们的 if elseif else 语句 通过条件作为 分支依据 最终的数学模型就是一颗树 不过在决策树算法中我们需要重点考虑 选取分支条件的理由 以及谁先判断谁后判断 包括最后对过拟合的处理 也就 是剪枝 这是我们之前写 if 语句时不会考虑的问题 决策树算法主要分为以下 3 个步骤 1 分支节点选取 2 构建树 3 剪枝 1 1 1 1 分支节点选取分支节点选取 分支节点选取 也就是寻找分支节点的最优解 既然要寻找最优 那么必须 要有一个衡量标准 也就是需要量化这个优劣性 常用的衡量指标有熵和基尼系 数 熵 熵用来表示信息的混乱程度 值越大表示越混乱 包含的信息量也就越 多 比如 A 班有 10 个男生 1 个女生 B 班有 5 个男生 5 个女生 那么 B 班的熵 值就比 A 班大 也就是 B 班信息越混乱 精品文档 2欢迎下载 基尼系数 同上 也可以作为信息混乱程度的衡量指标 有了量化指标后 就可以衡量使用某个分支条件前后 信息混乱 程度的收敛效果了 使用分支前的混乱程度 减去分支后的混乱程度 结果越大 表示效果越好 计算熵值 defdef entropy dataSet tNum len dataSet print tNum 用来保存标签对应的个数的 比如 男 6 女 5 labels forfor node inin dataSet curL node 1 获取标签 ifif curL notnot inin labels keys labels curL 0 如果没有记录过该种标签 就记录并初始化为 0 labels curL 1 将标签记录个数加 1 此时 labels 中保存了所有标签和对应的个数 res 0 计算公式为 p logp p 为标签出现概率 forfor node inin labels p float labels node tNum res p log p 2 returnreturn res 计算基尼系数 defdef gini dataSet 精品文档 3欢迎下载 tNum len dataSet print tNum 用来保存标签对应的个数的 比如 男 6 女 5 labels forfor node inin dataSet curL node 1 获取标签 ifif curL notnot inin labels keys labels curL 0 如果没有记录过该种标签 就记录并初始化为 0 labels curL 1 将标签记录个数加 1 此时 labels 中保存了所有标签和对应的个数 res 1 计算公式为 p logp p 为标签出现概率 forfor node inin labels p float labels node tNum res p p returnreturn res 1 2 1 2 构建树构建树 ID3ID3 算法 算法 利用信息熵增益 决定选取哪个特征作为分支节点 分支前的总样本 熵值 分支后的熵值总和 信息熵增益 T1 的信息熵增益 1 13 20 0 961 7 20 0 863 0 073 T2 的信息熵增益 1 12 20 0 812 8 20 0 544 0 295 所以使用 T2 作为分支特征更优 ID3ID3 算法建树 算法建树 依据前面的逻辑 递归寻找最优分支节点 直到下面情况结束 1 叶节点已经属于同一标签 精品文档 4欢迎下载 2 虽然叶节点不属于同一标签 但是特征已经用完了 3 熵小于预先设置的阈值 4 树的深度达到了预先设置的阈值 ID3ID3 算法的不足 算法的不足 1 取值多的特征比取值少的特征更容易被选取 2 不包含剪枝操作 过拟合严重 3 特征取值必须是离散的 或者有限的区间的 于是有了改进算法 C4 5 C4 5C4 5 算法 算法 基于 ID3 算法进行了改进 首先 针对 ID3 的不足 1 采用信息增益 率取代 ID3 中使用信息增益而造成的偏向于选取取值较多的特征作为分裂点的问 题 针对 ID3 的不足 2 采用剪枝操作 缓解过拟合问题 针对 ID3 的不足 3 采用将连续值先排列 然后逐个尝试分裂 找到连续值中的最佳分裂点 信息增益率的计算信息增益率的计算 先计算信息增益 然后除以 spliteInfo spliteInfo 为分 裂后的子集合的函数 假设分裂后的子集合个数为 sub1 和 sub2 total 为分裂 前的个数 spliteInfo sub1 total log sub1 total sub2 total log sub2 total index 特征序号 value 特征值 该方法表示将 index 对应特征的值为 value 的集合返回 返回集合中不包含 index 对 应的特征 defdef spliteDataSet dataSet index value newDataSet 精品文档 5欢迎下载 forfor node inin dataSet ifif node index value 0 index 列的数据 newData node index index 1 最后 列的数据 newData extend node index 1 newDataSet append newData returnreturn newDataSet 选择最优分裂项 defdef chooseBestFeature dataSet 特征个数 featureNum len dataSet 0 1 计算整体样本的熵值 baseEntropy entropy dataSet print baseEntropy baseEntropy f f baseEntropy 保存最大的信息增益率 maxInfoGainRatio 0 0 bestFeatureId 1 forfor i inin range featureNum 获取特征所有可能的值 featureValues forfor node inin dataSet featureValues append node i print featureValues 将特征值去除重复 uniqueFeatureValues set featureValues print uniqueFeatureValues 按照 i 特征分裂之后的熵值 newEntropy 0 0 分裂信息 spliteInfo 0 0 按照 i 所表示的特征 开始分裂数据集 forfor value inin uniqueFeatureValues 当 i 属性等于 value 时的分裂结果 subDataSet spliteDataSet dataSet i value print subDataSet 精品文档 6欢迎下载 计算占比 p float len subDataSet float len dataSet newEntropy p entropy subDataSet spliteInfo p log p 2 计算信息增益 infoGain baseEntropy newEntropy 计算信息增益率 ifif spliteInfo 0 continuecontinue infoGainRatio infoGain spliteInfo ifif infoGainRatio maxInfoGainRatio maxInfoGainRatio infoGainRatio bestFeatureId i returnreturn bestFeatureId C4 5C4 5 算法的不足 算法的不足 1 1 如果存在连续值的特征需要做排序等处理 计算比较耗时 2 只能用于分类使用 于是有了 CART 算法 CARTCART 算法 算法 也是基于 ID3 算法优化而来 支持分类和回归 使用基尼系数 分 类树 或者均方差 回归树 替代熵的作用 减少运算难度 使用二叉树代替多 叉树建模 降低复杂度 基尼系数的计算 基尼系数的计算 精品文档 7欢迎下载 均方差的计算 均方差的计算 计算举例 假设有如下数据源计算举例 假设有如下数据源 看电视 时间 婚姻情 况 职业年龄 3 未婚学生 12 4 未婚学生 18 2 已婚老师 26 5 已婚上班族 47 2 5 已婚上班族 36 3 5 未婚老师 29 4 已婚学生 21 如果将婚否作为标签 该问题是一个分类问题 所以使用基尼系数 假设使用职业作为特征分支 对于看电视和年龄 都是连续数据 需要按照 C4 5 的算法排序后处理 这里先分析简单的按照职业开始划分 精品文档 8欢迎下载 又因为 CART 算法的建模是二叉树 所以 针对职业来说 有以下组合 学生 非学生 老师 非老师 上班族 非上班族 到底怎么划分 就要通过基尼系数来 判断了 ginigini 3 3 7 7 1 1 2 2 3 3 2 2 3 3 1 1 3 3 1 1 3 3 4 4 7 7 1 1 3 3 4 4 3 3 4 4 1 1 4 4 1 1 4 4 0 40 4 ginigini 2 2 7 7 1 1 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 5 5 7 7 1 1 2 2 5 5 2 2 5 5 3 3 5 5 3 3 5 5 0 490 49 精品文档 9欢迎下载 ginigini 2 2 7 7 1 1 1 1 1 1 5 5 7 7 1 1 3 3 5 5 3 3 5 5 2 2 5 5 2 2 5 5 0 340 34 所以 如果选择职业来划分 那么首先应该按照上班族 非上班族划分 如果将年龄作为标签 该问题是一个回归问题 所以使用均方差 同样 先考虑使用职业来划分 mean 开方 12 12 18 18 21 21 3 17 17 开方 26 26 47 47 36 36 29 29 5 32 5 32 5 34 71 其他情况略 精品文档 10欢迎下载 可以看到选择分裂属性这一步骤会比较麻烦 首先要遍历所有特征 可以看到选择分裂属性这一步骤会比较麻烦 首先要遍历所有特征 找到每一个特征的最优分裂方法 然后在选择最优的分裂特征 找到每一个特征的最优分裂方法 然后在选择最优的分裂特征 功能功能树结构树结构特征选取特征选取连续值处连续值处 理理 缺失值处缺失值处 理理 剪枝剪枝 ID3ID3 分类多叉信息增益不支持不支持不支持 C4 5C4 5 分类多叉信息增益率支持支持支持 CARTCART 分类 回归二叉基尼系数 分类 均方差 回归 支持支持支持 精品文档 11欢迎下载 1 3 1 3 剪枝剪枝 CCP Cost Complexity Pruning 代价复杂性剪枝法 CART 常用 REP Reduced Error Pruning 错误降低剪枝法 PEP Pessimistic Error Pruning 悲观错误剪枝法 C4 5 使用 MEP Minimum Error Pruning 最小错误剪枝法 这里以 CCP 为例讲解其原理 CCP 选择节点表面误差率增益值最小的非叶子节点 删除该节点的子节点 若多 个非叶子节点的表面误差率增益值相同 则选择子节点最多的非叶子节点进行裁 剪 表面误差率增益值计算 表面误差率增益值计算 R t 表示非叶子节点的错误率 比如 总样本 20 在 A 节点上 a 类 5 个 b 类 2 个 所以可以认为 A 节点代表的是 a 类 那么错误率就是 2 7 7 20 R T 表示叶子节点的错误率累积和 N T 表示叶子节点的个数 剪枝步骤 剪枝步骤 1 构建子树序列 2 找到最优子树 作为我们的决策树 交叉验证等 精品文档 12欢迎下载 举例 举例 t1 是根节点 t2 t3 t4 t5 是非叶子节点 t6 t7 t8 t9 t10 t11 是叶子节点 首先我们计算所有非叶子节点误差率增益值 t4 4 50 50 80 1 45 45 80 2 5 5 80 2 1 0 0125 t5 4 10 10 80 0 0 2 1 0 05 t2 10 60 60 80 1 45 45 80 2 5 5 80 0 0 4 1 0 0292 精品文档 13欢迎下载 t3 0 0375 因此得到第 1 颗子树 T0 t4 0 0125 t5 0 05 t2 0 0292 t3 0 0375 比较发现可以将 t4 裁剪掉 得到第 2 颗子树 t5 0 05 t3 0 0375 t2 10 60 60 80 4 50 50 80 0 0 3 1 0 0375 此时 t2 与 t3 相同 那么裁剪叶子节点较多的 因此 t2 被裁剪 得到第 3 颗树 精品文档 14欢迎下载 然后对上面 3 颗子树进行验证 找到效果最后的作为剪枝之后的决策树 2 2 sk learnsk learn 中的使用中的使用 fromfrom sklearn datasets importimport load iris fromfrom sklearn importimport tree importimport pydotplus importimport graphviz iris load iris clf tree DecisionTreeClassifier clf fit iris data iris target dot data tree export graphviz clf out file NoneNone graph pydotplus graph from dot data dot data graph write pdf iris pdf iris pdf 精品文档 15欢迎下载 3 3 sk learnsk learn 中源码分析中源码分析 主要分析 tree 的相关函数代码 使用 pycharm 下载 sklearn 包中 tree 文件 引用了 tree pxd pxd 相当于头文件 其实现在 tree pyd 中 pyd 是加密文件 无法查看 从 github 上下载源码中有 tree pyx 相当于 c 文件 因此可以查看 pxd 相当于 h pyx 相当于 c pyd 相当于 dll tree DecisionTreeClassifier 创建分类决策树对象 DecisionTreeClassifier 继承 BaseDecisionTree clf fit iris data iris target 建树 DecisionTreeClassifier 直接使用了父类 BaseDecisionTree 的方法 super fit X y sample weight sample weight check input