决策树之C4.5算法

概要

• 关于决策树
  决策树其实是一种分类算法，目标是将具有P个维度特征的样本n划分到c个类别中： c = f(n); 通过这种分类的过程表示为一棵树，每次通过选择一个特征pi来进行分叉。
  每个叶节点对应着一个分类，非叶节点对应着在每个属性上的划分，根据样本在该属性上的不同取值将其划分成若干个子集。对于非纯的叶节点，多数类的标号给出到达这个节点的样本所属的类。

构建决策树的核心问题： 在每一步如何选择适当的属性对样本进行拆分。

• 不同的决策树算法有着不同的特征选择方案
  1、ID3： 信息增益
  2、C4.5： 信息增益率
  3、CART: gini系数（基尼系数）

算法	描述	适用
ID3	在决策树的各级节点上，使用信息增益方法作为属性选择标准，来确定生成每个节点时所采用的合适属性	适用于离散的描述属性
C4.5	使用信息增益率来选择节点属性，并克服ID3算法的不足	即适用离散的描述属性呦适用连续的描述属性
CART	是一种有效的非参数分类和回归方法，通过构建树、修建树、评估树来构建二叉树	当终结点为连续属性时该树为回归树；当终节点为分类变量时，即为分类树

实例

决策树-分类.png

数据总结： 属性数据4个 = {天气，温度，湿度，风速}
类别2个 = {进行，取消}
1、类型信息熵
定义：所有样本中各种类别出现的不确定性之和，根据熵的概念，熵越大，不确定性就越大。需要研究清楚信息就越多。

2、每个属性的信息熵
每个属性信息熵相当于一种条件熵。表示在某种属性的条件下，各种类别出现的不确定性之和。属性的信息熵越大，该属性拥有的样本类型越不“纯”。

3、信息增益
信息增益 = 熵 - 条件熵（信息类别熵 - 属性信息熵）；表示信息不确定性减少的程度。若是一个属性的信息增益越大，就表示用这个属性进行样本划分可以更好的减少划分后样本的不确定性。当然，选择该属性就可以更快更好的完成分类目标。
信息增益的ID3算法的特征选择指标

4.属性分裂信息度量
通过分裂信息度量来考虑某种属性进行分裂时分支的数量信息和尺寸信息，而这些信息称之为属性的内在信息。

信息增益率 = 信息增益 / 内存信息，导致属性的重要性随内在信息的增大而减小（换句话说：若是某个属性本身的不确定性很大，那就不倾向选取它）。是对单纯使用信息增益有所补偿

5、信息增益率
IGR(天气) = Gain(天气) / H(天气) = 0.246 / 1.577 = 0.155
IGR(温度) = Gain(温度) / H(温度) = 0.029 / 1.556 = 0.0186
IGR(湿度) = Gain(湿度) / H(湿度) = 0.151 / 1.0 = 0.151
IGR(风速) = Gain(风速) / H(风速) = 0.048 / 0.985 = 0.048 信息增益率

结论

后续

信息熵：体现的是在整个样本数据集中，结果类型或条件属性在对应的结果集中单一事件出现不确定性的概率；而这个不确定性的结果和对应的结果类型或条件属性存在log的联系；信息的不确定性越大，熵的值也就越大; 针对的是一元模型的概率
-(同一结果类型记录的个数) / (整个样本数据结果类型记录的总数) * log2((同一结果类型记录的个数) / (整个样本数据结果类型记录的总数))
条件熵： 通过多元模型的方式来减少一元模型中不确定性，或者说降低对应的熵，越低意味着信息的不确定性就越小。
条件熵 = -某个条件属性某个类型/总结果记录数 * 该条件属性某个类型的不同细分类的信息熵 之和
该条件属性某个类型的不同细分类的信息熵 = 同个属性不同内容类型相对结果类型的信息熵的之和