1. 决策树算法思路
根据一些 feature 进行分类，每个节点提一个问题，通过判断，将数据分为两类，再继续提问。这些问题是根据已有数据学习出来的，再投入新数据的时候，就可以根据这棵树上的问题，将数据划分到合适的叶子上。
来源：机器学习实战-p34
2. 特征选择 - 信息熵、信息增益、基尼指数
这里需要考虑一个问题，当前数据集上哪个特征在划分数据分类 时起决定性作用，每次我们选择哪个特征作为划分的参考属性呢？为了找到决定性的特征，划分出最好的结果，我们必须评估每个特征，使得随着划分过程不断进行，分支节点包含的样本尽量属于同一类别，即节点的“纯度”越来越高。
信息熵 (Information Entropy)： 度量样本集合纯度最常用的一种指标。假定当前样本集合 D 中第 k 类样本所占的比例 pk ，D 的信息熵为：
信息增益 (Information Gain)：记离散属性 a 有 V 个可能的取值{a1,a2,...aV}，使用a对样本集D进行划分，则会产生V个分支节点，其中第v个分支节点包含了D中在a属性取值为av的样本，记为Dv。于是使用属性a对D进行划分所获得的信息增益为:
信息增益越大，则意味着使用属性a来进行划分所获得的 “纯度” 提升越大
基尼指数 (Gini index)：
CART决策树使用基尼指数来选择划分属性，数据集D的纯度可以用基尼值来度量：
Gini(D)反映了从数据集中随机抽取两个样本，其类别标记不一致的的概率。因此Gini(D)越小，数据集D的纯度越高。
所以，应选Gini_index(D,a)最小的属性作为最优划分属性。
案例：ID3决策树算法
第一轮划分：
第二轮划分：
信息增益准则对可取值数目较多的属性有所偏好，因此C4.5决策树算法采用增益率：
3. 剪枝处理
在决策树学习中，有时决策树分支过多，以至于把训练集自身的一些特点当成是一般性而导致过拟合，因此通过主动剪枝来降低过拟合风险。
将上文中的西瓜数据集分为训练集和验证集两部分。根据信息增益将从训练集生成如图4.5的决策树：
预剪枝：
预剪枝是在决策树形成之前对每一个属性根据划分前后集精度（测试集的预测准确率）的提升来判断是否要对该属性进行划分。
用表4.2的验证集计算划分前后的集精度，评估是否按照该属性继续进行划分，那么最后形成的决策树如图4.6所示。
对比图4.5和4.6，预剪枝使得决策树的很多分支都没有展开，减少了时间开销，但另一方面，有些属性的当前划分虽不能提升泛化性能，但在其基础上的后续划分却有可能使得泛化性能提高，预剪枝禁止这些分支展开会带来欠拟合风险。
后剪枝：
后剪枝先从训练集中生成一棵完整决策树，从图4.5易知验证集精度=3/7≈42.9%。
首先考察图4.5中的节点⑥，如果把该节点替换成叶节点，该叶节点包含{7,15}，应标记成好瓜（好瓜1：1坏瓜，此处有疑问，不过不管标记成好瓜还是坏瓜，此例中没有影响到之后的结果），此时，验证集精度=4/7≈57.1%，于是后剪枝策略决定剪枝。
考察节点⑤，将其子树替换成叶节点，该叶节点包含{6,7,15}，应标记成好瓜，验证集精度=4/7≈57.1%不变，后剪枝策略可以不剪枝。
考察节点②，将其子树替换成叶节点，该叶节点包含{1,2,3,14}，应标记成好瓜，验证集精度=5/7≈71.4%不变，后剪枝策略决定剪枝。
考察节点③和①，若将其子树替换成叶节点，集精度分别为：5/7≈71.4%，3/7≈42.9%。
来源：机器学习-p83
网友评论