决策树(1)——ID3算法与C4.5算法的理论基础与python实现

A2​作为此结点的特征 可以发现 C4.5算法与ID3算法对于此贷款申请数据集生成的决策树是一样的 但是通过比较特征的信息增益比和信息增益可以发现 特征取值多的特征 比如年龄和信贷情况 的信息增益比相较于其信息增益有了一定程度的下降 而特征取值少的特征 比如是否有工作和是否有房子 的信息增益比相较于其信息增益有了一定程度的上升 这就展示了信息增益比确实对信息增益所存在的偏向于选择取值较多的特征的问题进行了改进。

C4.5算法与ID3算法只有特征选择的准则不同 其特征选择的代码如下

 # 计算数据集D关于特征A的值的熵
 def calc_HAD(self,dataset,A 0):
 dataset np.array(dataset)
 data_length len(dataset)
 feature dataset[:,A] 
 feature_values Counter(feature) #得到一个字典 key为类别 value为对应的类的数量
 HD -sum([(p/data_length)*log(p/data_length,2) for p in feature_values.values()]) 
 return HAD
 #找出信息增益比最大的特征
 def calcBestFeature(self,dataset):
 feature_count len(dataset[0]) - 1 #特征的个数
 GRDA [0]*feature_count
 for i in range(feature_count):
 #计算信息增益 课本式 5.9 
 GDA[i] self.calc_HD(dataset) - self.calc_HDA(dataset,A i)
 #计算信息增益比 课本式 5.10 
 GRDA[i] GDA[i] / self.calc_HAD(dataset, A i)
 max_GRDA max(GRDA) #最大的信息增益比
 best_feature GRDA.index(max_GRDA) #最大的信息增益比对应的特征索引
 return best_feature,max_GRDA

4.决策树的剪枝

  为了提高决策树模型的泛化能力 避免过拟合 往往需要对生成的决策树进行剪枝。
决策树的剪枝通常有两种方法 分别为预剪枝(pre-pruning)和后剪枝(post-pruning)。
  预剪枝的核心思想是在树中结点进行扩展之前 先计算当前的划分是否能够带来模型泛化能力的提升 如果不能则不在继续生长子树。此时可能存在不同类别的样本同时存在与结点中 按照多数投票的原则判断该结点所属类别。预剪枝对于何时停止树的生长有以下几种方法

当树到达一定深度的时候 停止树的生长 当到达当前结点的样本数量小于某个阈值的时候 停止树的生长 计算每次分裂对测试集的准确度提升 当小于某个阈值的时候 不再继续扩展。

  后剪枝的核心思想是让算法生成一颗完全生长的决策树 然后自下而上计算是否剪枝。剪枝的过程是将子树删除 用一个叶结点替代 该结点的类别同样按照多数投票的原则进行判断。相比于预剪枝 后剪枝通常可以得到泛化能力更强的决策树 但时间开销会更大。
  常见的后剪枝方法有错误率降低剪枝、悲观剪枝、代价复杂度剪枝和最小误差剪枝等等。下面我们主要讨论代价复杂度剪枝(Cost Complexity Pruning,CCP)的实现过程。如果想了解其他剪枝方法可以去B站https://space.bilibili.com/406882224/search/video?keyword %E5%89%AA%E6%9E%9D观看 我感觉这个UP主讲的很好。
  决策树的剪枝通常通过极小化决策树整体的损失函数或代价函数来实现。设完全生长的决策树为