完整word版,决策树算法总结

决策树

决策树

研发二部

武汉中原电子信息有限公司

决策树

文件状态： [ ] 草稿 [ ] 正式发布 [ ] 正在修改 文件标识： 当前版本： 作者： 完成日期： 1.0 张宏超 2024年3月8日

I

决策树

目录

1.

算法介绍 .................................................................................................................................... 1

1.1. 1.2. 1.3.

2. 3.

分支节点选取 .............................................................................................................. 1 构建树 .......................................................................................................................... 3 剪枝 ............................................................................................................................ 10

sk-learn中的使用 .................................................................................................................... 12 sk-learn中源码分析 ................................................................................................................ 13

II

决策树

1. 算法介绍

决策树算法是机器学习中的经典算法之一，既可以作为分类算法，也可以作为回归算法。决策树算法又被发展出很多不同的版本，按照时间上分，目前主要包括，ID3、C4.5和CART版本算法。其中ID3版本的决策树算法是最早出现的，可以用来做分类算法。C4.5是针对ID3的不足出现的优化版本，也用来做分类。CART也是针对ID3优化出现的，既可以做分类，可以做回归。

决策树算法的本质其实很类似我们的if-elseif-else语句，通过条件作为分支依

据，最终的数学模型就是一颗树。不过在决策树算法中我们需要重点考虑选取分支条件的理由，以及谁先判断谁后判断，包括最后对过拟合的处理，也就是剪枝。这是我们之前写if语句时不会考虑的问题。

决策树算法主要分为以下3个步骤： 1. 分支节点选取 2. 构建树 3. 剪枝

1.1. 分支节点选取

分支节点选取，也就是寻找分支节点的最优解。既然要寻找最优，那么必须

要有一个衡量标准，也就是需要量化这个优劣性。常用的衡量指标有熵和基尼系数。

熵：熵用来表示信息的混乱程度，值越大表示越混乱，包含的信息量也就越

多。比如，A班有10个男生1个女生，B班有5个男生5个女生，那么B班的熵值就比A班大，也就是B班信息越混乱。

基尼系数：同上，也可以作为信息混乱程度的衡量指标。

武汉中原电子信息有限公司

1

决策树

有了量化指标后，就可以衡量使用某个分支条件前后，信息混乱程度的收敛效果了。使用分支前的混乱程度，减去分支后的混乱程度，结果越大，表示效果越好。

#计算熵值 def entropy(dataSet): tNum = len(dataSet) print(tNum)

#用来保存标签对应的个数的，比如,男：6，女：5 labels = {}

for node in dataSet:

curL = node[-1] #获取标签 if curL not in labels.keys():

labels[curL] = 0 #如果没有记录过该种标签，就记录并初始化为0 labels[curL] += 1 #将标签记录个数加1 #此时labels中保存了所有标签和对应的个数 res = 0

#计算公式为-p*logp，p为标签出现概率 for node in labels:

p = float(labels[node]) / tNum res -= p * log(p, 2) return res

#计算基尼系数 def gini(dataSet):

tNum = len(dataSet) print(tNum)

# 用来保存标签对应的个数的，比如,男：6，女：5 labels = {}

for node in dataSet:

curL = node[-1] # 获取标签 if curL not in labels.keys():

labels[curL] = 0 # 如果没有记录过该种标签，就记录并初始化为0 labels[curL] += 1 # 将标签记录个数加1 # 此时labels中保存了所有标签和对应的个数 res = 1

武汉中原电子信息有限公司

2