决策树研发二部目录1. 算法介绍 (1)1.1.分支节点选取 (1)1.2.构建树 (3)1.3.剪枝 (10)2. sk-learn中的使用 (12)3. sk-learn中源码分析 (13)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班信息越混乱。
基尼系数：同上，也可以作为信息混乱程度的衡量指标。
有了量化指标后，就可以衡量使用某个分支条件前后，信息混乱程度的收敛效果了。
使用分支前的混乱程度，减去分支后的混乱程度，结果越大，表示效果越好。
#计算熵值def entropy(dataSet):tNum = len(dataSet)print(tNum)#用来保存标签对应的个数的，比如,男：6，女：5labels = {}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]) / tNumres -= p * log(p, 2)return res#计算基尼系数def gini(dataSet):tNum = len(dataSet)print(tNum)# 用来保存标签对应的个数的，比如,男：6，女：5labels = {}for node in dataSet:curL = node[-1] # 获取标签if curL not in labels.keys():labels[curL] = 0 # 如果没有记录过该种标签，就记录并初始化为0 labels[curL] += 1 # 将标签记录个数加1# 此时labels中保存了所有标签和对应的个数res = 1# 计算公式为-p*logp ，p 为标签出现概率 for node in labels:p = float (labels[node]) / tNum res -= p * p return res1.2. 构建树ID3算法：利用信息熵增益，决定选取哪个特征作为分支节点。
分支前的总样本熵值-分支后的熵值总和=信息熵增益。
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作为分支特征更优。
ID3算法建树：依据前面的逻辑，递归寻找最优分支节点，直到下面情况结束 1. 叶节点已经属于同一标签2. 虽然叶节点不属于同一标签，但是特征已经用完了3. 熵小于预先设置的阈值4. 树的深度达到了预先设置的阈值ID3算法的不足：1.取值多的特征比取值少的特征更容易被选取。
2.不包含剪枝操作，过拟合严重3.特征取值必须是离散的，或者有限的区间的。
于是有了改进算法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对应的特征def spliteDataSet(dataSet, index, value):newDataSet = []for node in dataSet:if node[index] == value:#[0,index)列的数据newData = node[:index]#[index+1,最后]列的数据newData.extend(node[index + 1:])newDataSet.append(newData)return newDataSet;#选择最优分裂项def chooseBestFeature(dataSet):#特征个数featureNum = len(dataSet[0]) - 1#计算整体样本的熵值baseEntropy = entropy(dataSet)print("baseEntropy = %f"%(baseEntropy))#保存最大的信息增益率maxInfoGainRatio = 0.0bestFeatureId = -1for i in range(featureNum):#获取特征所有可能的值featureValues = []for node in dataSet:featureValues.append(node[i])print(featureValues)#将特征值去除重复uniqueFeatureValues = set(featureValues)print(uniqueFeatureValues)#按照i特征分裂之后的熵值newEntropy = 0.0#分裂信息spliteInfo = 0.0#按照i所表示的特征，开始分裂数据集for value in uniqueFeatureValues:#当i属性等于value时的分裂结果subDataSet = spliteDataSet(dataSet, i, value)print(subDataSet)#计算占比p = float(len(subDataSet)) / float(len(dataSet)) newEntropy += p * entropy(subDataSet)spliteInfo += -p * log(p, 2)#计算信息增益infoGain = baseEntropy - newEntropy#计算信息增益率if spliteInfo == 0:continueinfoGainRatio = infoGain / spliteInfoif infoGainRatio > maxInfoGainRatio:maxInfoGainRatio = infoGainRatiobestFeatureId = ireturn bestFeatureIdC4.5算法的不足：1.如果存在连续值的特征需要做排序等处理，计算比较耗时2. 只能用于分类使用于是有了CART算法CART算法：也是基于ID3算法优化而来，支持分类和回归，使用基尼系数（分类树）或者均方差（回归树）替代熵的作用，减少运算难度。
使用二叉树代替多叉树建模，降低复杂度。
基尼系数的计算：均方差的计算：计算举例，假设有如下数据源看电视时间婚姻情况职业年龄3 未婚学生124 未婚学生18 2 已婚老师265 已婚上班族472.5 已婚上班族363.5 未婚老师294 已婚学生21如果将婚否作为标签，该问题是一个分类问题，所以使用基尼系数假设使用职业作为特征分支，对于看电视和年龄，都是连续数据，需要按照C4.5的算法排序后处理，这里先分析简单的按照职业开始划分。
又因为，CART算法的建模是二叉树，所以，针对职业来说，有以下组合，学生|非学生，老师|非老师，上班族|非上班族，到底怎么划分，就要通过基尼系数来判断了。
gini = 3 / 7 * (1 – 2 / 3 * 2 /3 – 1 / 3 * 1 / 3) + 4 / 7 * (1 – 3 / 4 * 3 / 4 – 1 / 4 * 1 / 4) = 0.4gini = 2 / 7 * (1 – 1 / 2 * 1 / 2 – 1 / 2 * 1 / 2) + 5 / 7 * (1 – 2 / 5 * 2 / 5 – 3 / 5 * 3 / 5) = 0.49gini = 2 / 7 * (1 – 1 * 1) + 5 / 7 * (1 – 3 / 5 * 3 / 5 – 2 / 5 * 2 / 5) = 0.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其他情况略。
可以看到选择分裂属性这一步骤会比较麻烦，首先要遍历所有特征，找到每一个特征的最优分裂方法，然后在选择最优的分裂特征。
功能树结构特征选取连续值处理缺失值处理剪枝ID3 分类多叉信息增益不支持不支持不支持C4.5 分类多叉信息增益率支持支持支持CART 分类/回归二叉基尼系数（分类），均方差（回归）支持支持支持1.3.剪枝CCP（Cost Complexity Pruning）代价复杂性剪枝法（CART常用）REP（Reduced Error Pruning）错误降低剪枝法PEP（Pessimistic Error Pruning）悲观错误剪枝法（C4.5使用）MEP（Minimum Error Pruning）最小错误剪枝法这里以CCP为例讲解其原理CCP选择节点表面误差率增益值最小的非叶子节点，删除该节点的子节点。