1: 决策树定义
决策树是一类常见的机器学习方法, 它是基于树的结构进行决策的, 例如下图判断一个西瓜是否是好瓜, 决策过程通常会进行一系列的判断或是子决策, 例如, 先判断色泽如何, 如果色泽青绿再判断根蒂如何, 就这样每次判断一个因素, 一直进行下去, 知道判断出是好瓜还是坏瓜.
2: 划分选择
每次做决策时根据哪一个属性呢, 即如何选择最优划分属性, 一般而言, 随着划分过程不断进行, 我们希望决策树的分支节点所包含的样本尽可能属于同一个类别, 即节点的 "纯度"(purity)越来越高.
2.1: 信息熵
假设当前样本集合 D 中有 n 类样本{x1,x2,......,xn}, 第 i 类样本在样本集合 D 中所占的比例为 p(xi), 则熵定义为信息的期望值, xi 的信息定义为:
l(xi)=-log2p(xi)
而样本集合 D 的信息熵则定义为:
Ent(D)=-ni=1p(xi)log2p(xi)
Ent(D)的值越小, 则 D 的纯度越高.
2.2: 信息增益
假定离散属性 a 有 k 个可能的取值{a1,a2,......,ak}, 若使用 a 来对样本集 D 进行划分, 则会产生 k 个分支节点, 其中第 i 个分支节点包含了 D 中所有在属性 a 上取值为 ai 的样本, 记为 Di, 我们可根据公式求得第 i 个分支节点的信息熵记为 Ent(Di), 第 i 个分支节点样本集 Di 占样本集合 D 总的样本比例记为 p(Di)=Di/D, 父节点的信息熵记为 Ent(D), 则用属性 a 对样本 D 进行划分所获得的 "信息增益" 为:
Gain(D,a)=Ent(D)-ki=1p(Di)Ent(Di)
一般而言, 信息增益越大, 表明使用属性 a 来进行划分所获得的 "纯度提升" 越大, 因此我们可以用信息增益来进行决策树的划分属性选择, 著名的 ID3 决策树学习算法就是以信息增益为准则来选择划分属性的.
编号 | 是否在水下 | 是否有脚蹼 | 是否属于鱼类 |
1 | 是 | 是 | 是 |
2 | 是 | 是 | 是 |
3 | 是 | 否 | 否 |
4 | 否 | 是 | 否 |
5 | 否 | 是 | 否 |
表一: 海洋生物数据
以表一中的海洋生物数据集为例, 该数据集包含 5 个人样例, 用以学习得到一棵能预测一个不明海洋生物是否是鱼类的决策树, 在决策树开始之前, 根节点包含 D 中所有的样例, 其中正例占 p1=2/5, 反例占 p2=3/5, 于是, 根据公式可以计算出根节点信息熵为:
Ent(D)=-ni=1p(xi)log2p(xi)=-(2/5*log2(2/5)+3/5*log2(3/5))=0.971
然后我们计算出当前属性集合 {是否在水下, 是否有脚蹼} 中每个属性的信息增益, 假设以 "是否在水下" 进行划分, D1={1,2,3},2 个正例 1 个反例, D2={4,5},0 个正例 2 个反例, 计算可得信息增益为:
- Ent(D1)=-(2/3*log2(2/3)+1/3*log2(1/3))=0.918
- Ent(D2)=-(0*log2(0)+2/2*log2(2/2))=0.0
- Gain(D, 是否在水下)=Ent(D)-ki=1p(Di)Ent(Di)=0.971-(3/5*0.918+2/5*0.0)=0.4202
类似的, 我们也可以用 "是否有脚蹼" 进行划分, D1={1,2,4,5},2 个正例 2 个反例, D2={3},0 个正例 1 个反例, 计算可得信息增益为:
- Ent(D1)=-(2/4*log2(2/4)+2/4*log2(2/4))=1.0
- Ent(D2)=-(0*log2(0)+1/1*log2(1/1))=0.0
- Gain(D, 是否在水下)=Ent(D)-ki=1p(Di)Ent(Di)=0.971-(4/5*1.0+1/5*0.0)=0.171
由于按是否在水下进行划分的信息增益比 "是否有脚蹼" 的信息增益大, 所以选择按 "是否在水下" 进行划分, 如下图所示:
2.3: 信息增益率
在上面的计算中, 我们没有考虑第一列的编号, 如果把编号页作为一个属性考虑进去, 那么可计算出它的信息增益为:
Gain(D, 编号)=Ent(D)-ki=1p(Di)Ent(Di)=0.971-1/5*(-1/1*log2(1/1)-1/1*log2(1/1)-1/1*log2(1/1)-1/1*log2(1/1)-1/1*log2(1/1))=0.971
远大于其他候选划分属性, 因为根据编号划分可以产生 5 个分支, 每个分支节点只包含一个样本, 这些分支节点的纯度已经达到最大, 但是, 这样的决策树显然不具备泛化能力, 无法对新样本进行有效的预测.
实际上, 信息增益准则对可取值数目较多的属性有所偏好, 为减少这种偏好可能带来的不利影响, 著名的 C4.5 决策树算法不直接使用信息增益, 而是使用 "信息增益率" 来选择最优划分属性, 信息增益率定义为:
Gain_ration(D,a)=Gain(D,a)/IV(a)
其中
IV(a)=-ki=1p(Di)log2(Di)
称为属性 a 的 "固有值", 属性 a 的可能取值数目越多, 则 IV(a)的值通常会越大, 例如, 对表一中的海洋生物数据有:
- IV(编号)=-(1/5*log2(1/5)+1/5*log2(1/5)+1/5*log2(1/5)+1/5*log2(1/5)+1/5*log2(1/5)+1/5*log2(1/5))
- =2.322
- IV(是否在水下)=-(3/5*log2(3/5)+2/5*log2(2/5))=0.971
- IV(是否有脚蹼)=-(4/5*log2(4/5)+1/5*log2(1/5))=0.722
需要注意的是, 信息增益率准则对可取值数目较少的属性有所偏好, 因此 C4.5 算法并不是直接选择信息增益率最大的候选划分属性, 而是使用了一个启发式: 先从候选划分属性中找出信息增益高于平均水平的属性, 再从中选择增益率最高的.
2.4: 基尼指数
CART 决策树采用 "基尼指数" 来选择划分属性, 数据集 D 的纯度可用基尼值来度量:
Gini(D)=ni=1k'!=kpk*pk'=1-ki=1pk*pk
直观来说, Gini(D)反映了从数据集 D 中随机抽取两个样本, 其类别标记不一致的概率, 因此 Gini(D)越小, 则数据集 D 的纯度越高, 属性 a 的基尼指数定义为:
Gini_index(D,a)=ki=1p(Di)Gini(Di)
于是, 我们在候选集合 A 中, 选择那个使得划分后基尼指数最小的属性作为最优划分属性.
3: 决策树构建算法
决策树的构建算法主要有三种:
ID3: 以信息增益为准则来选择划分属性.
C4.5: 先从候选划分属性中找出信息增益高于平均水平的属性, 再从中选择信息增益率最高的.
CART: 使用基尼指数来选择划分属性.
ID3 是最基本的决策树构建算法, C4.5 和 CART 是在 ID3 的基础上进行优化的算法.
4: 决策树生成终止条件
决策树的生成是一个递归过程, 在决策树基本算法中, 有三种情形会导致递归返回:
(1): 当前节点包含的样本都属于同一类别, 无需再进行划分.
(2): 当前属性集为空, 或是所有样本在所有属性上的取值相同, 无法划分.
(3): 当前节点包含的样本集合为空, 不能划分.
在第 (2) 中情形下, 我们把当前节点标记为叶节点, 并将其类别设定为该节点所含样本最多的类别, 在第 (3) 种情形下, 同样把当前节点标记为叶节点, 但将其类别设定为其父节点所含样本最多的类别.
来源: https://www.cnblogs.com/earthhouge/p/9466277.html