树模型-ID3决策树-撸清算法逻辑
树模型-ID3决策树-撸清算法逻辑
ID3决策树
下图是判断是否外出打高尔夫球的决策树：
算法流程：
- 从集合D中选择最优切分属性A，衡量是否为最优的切分属性，ID3采用的是信息增益准则。
- 按照属性A将集合切分，判断切分后的集合：如果当前节点包含的样本属于同一类别，则无需划分，并将此叶子节点的类别定为此类；当前属性为空，或者所有样本属性集上取值相同，此叶子节点类别为大多数样本类别；当前集合为包含样本为空则直接返回。
- 若2)中的返回条件都不满足，则递归的继续切分集合，直到满足相应的阈值，递归结束。
从上述流程上看，决策树在建立过程中，树的深度不断增加，比较容易过拟合，所以要采用剪枝操作，避免形成过于复杂的决策树。
剪枝操作：
分为两种：预剪枝、后剪枝
预剪枝是指在决策树的生成过程中，对每个节点在划分前先进行评估，若当前的划分不能带来泛化性能的提升，则停止划分，并将当前节点标记为叶节点。
后剪枝是指先从训练集生成一颗完整的决策树，然后自底向上对非叶节点进行考察，若将该节点对应的子树替换为叶节点，能带来泛化性能的提升，则将该子树替换为叶节点。
决策树的后剪枝，一般来讲可以采用通过极小化决策树整体的损失函数(loss funtion)或代价函数(cost funtion)来实现。
我们将决策树学习的损失函数可以定义为：
公式第一项，衡量的是决策树对样本的拟合程度，拟合程度越好，其数值越小。公式第二项，衡量的是决策树的结构复杂程度，其结构越简单，第二项数值越小，也即是说：损失函数旨在找寻在结构不太复杂而准确率还较高的一棵决策树（奥卡姆剃刀原理）
后剪枝算法：
- 计算每个节点的经验熵
- 递归的从每个叶节点向上会缩。若会缩到父节点之后整体决策树的C(T)变小，则将其父节点变为新的叶子结点，否则不进行回缩。
- 重复步骤2)直到找到损失函数最下的T。