数据挖掘——决策树分类

决策树分类

树状结构，可以很好的对数据进行分类；

• 决策树的根节点到叶节点的每一条路径构建一条规则；
• 具有互斥且完备的特点，即每一个样本均被且只能被一条路径所覆盖；
• 只要提供的数据量足够庞大真实，通过数据挖掘模式，就可以构造决策树。
  

Hunt算法

设$D_t$是与节点相关联的训练记录集
算法步骤:

1. 如果$D_t$中所有记录都属于同一个类$y_t$,则t是叶节点，用$y_t$标记。
2. 如果$D_t$中包含属于多个类的记录,则选择一个属性测试条件，将记录划分成较小的子集
3. 对于测试条件的每个输出，创建一个子结点，并根据测试结果将$D_t$中的记录分布到子结点中。然后，对于每个子结点，递归地调用该算法。

Hunt算法采用贪心策略构建决策树

• 在选择划分数据的属性时，采取一系列局部最优决策来构造决策树。

决策树归纳的设计问题

• 如何分裂训练记录？
  • 怎样为不同类型的属性指定测试条件？
  • 怎样评估每种测试条件？
• 如何停止分裂过程？

怎样为不同类型的属性指定测试条件？

• 依赖于属性的类型

  • 标称
  • 序数
  • 连续

• 依赖于划分的路数

  • 多路划分
  • 二元划分

怎样选择最佳划分？
选择最佳划分的度量通常是根据划分后子节点纯性的程度。
纯性的程度越高，类分布就越倾斜，划分结果越好。

信息增益

熵的定义如下：
$$\mathrm{Entropy}(S)=-\sum _{i=1}^c{p}_i\log \left(p_i\right)$$
信息增益定义如下：
$$\mathrm{Gain}(S,A)=\mathrm{Entropy}(S)-\sum _{v\in A}\frac{\left|S_v\right|}{|S|}\mathrm{Entropy}\left(S_v\right)$$

信息增益表示的是：得知特征X的信息而使得分类Y的信息的不确定性减少的程度，如果某个特征的信息增益比较大，就表示该特征对结果的影响较大。

举例说明:

增益比率

信息增益问题：取值比较多的特征比取值少的特征信息增益大
解决方案：使用增益率，K越大，SplitINFO越大，增益率被平衡
$$GainRATI{O}_{split}=\frac{{\text{ GAIN }}_{\text{split }}}{\text{ SplitINFO}}$$
$$SplitINFO=-\sum _{n=1}^k\frac{n_i}{n}\log \frac{n_i}{n}$$

增益率准则对可取值数目较少的属性有偏好，因此C4.5算法并不是直接选择增益率最大的属性作为分支标准，而是先从侯选属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的属性。

基尼指数

连续数据

• 二元划分：$（A<v）or（A\ge v）$
  • 考虑所有的划分点，选择一个最优划分点v
• 多路划分：$v_i\le A<v_{i+1}（i=1,\dots ,k）$
  

总结

1. 决策树是一种构建分类（回归）模型的非参数方法
2. 不需要昂贵的的计算代价
3. 决策树相对容易解释
4. 决策树是学习离散值函数的典型代表
5. 决策数对于噪声的干扰具有相当好的鲁棒性
6. 冗余属性不会对决策树的准确率造成不利影响
7. 数据碎片问题：随着树的生长，可能导致叶结点记录数太少，对于叶结点代表的类，不能做出具有统计意义的判决
8. 子树可能在决策树中重复多次，使决策树过于复杂
9. 决策树无法学习特征之间的线性关系，难以完成特征构造