5.2 决策树 -- 条件概率分布

如果有10个条件概率分布，对应特征空间的10个划分，相当于构建了10棵决策树。
特征空间由特征向量组成，特征向量表示输入的每一个实例。一般认为输入空间与特征空间相同

决策树可以看作是ifthen规则构成的集合

5.2 决策树 -- 决策树学习

目的：构造决策树，对实例正确分类

n=特征=3

构造决策树的问题：
哪个特征作为首选？第二第三个特征怎么确定？（特征选择）
什么时候构建好特征树？（生成）

5.3 决策树：信息增益（特征选择）

不同首要特征的选择构成的决策树不同。信息增益是由熵构成。熵起源于热力学，香农引入信息论中，如果随机变x量有n个取值，每个随机变量所对应的概率是pi，那么随机变量x的熵是H（x）如下。熵与x的随机分布有关，可以表现成H（p）的形式，p对应随机变量的分布。

那么随机变量如何取值的时候，熵最小和最大呢？
像掷骰子，每个点的概率都是1/6，相应熵是最大。如果有n个取值，pi=1/n的时候，相应熵最大。当点数确定的时候，熵最小。熵理解为不确定性
为什么等概率分布的时候熵最大？

当x只有1和0两个取值，分别是p和q（即1-p），那么H(x)如蓝笔书写，在坐标轴上当p取0.5，H(p)最大，H(p)=1就是n取2的时候（n是随机变量的取值数），log以2为底，log2=1。证实了左下角的不等式
如果函数是凹函数，可以用求导来求H(x)的最大值

如果取最小值，函数是凸函数才可以

因为概率p(x)的的取值是0到1，所以log2p(x)<0

所以为了保证信息熵是正，要加负号

如果已知x，怎么求y的熵？

条件熵就是负的pi乘以随机变量X取xi的时候y的熵，pi就是X=xi的概率（pi=P（X=xi），n对应X的n个取值）。
当熵和条件熵都是训练数据得到的，也就是都是估计值而不是真实值，称经验熵和经验条件熵。若对应真实分布时，那时是理想化的熵和条件熵，所谓真实熵和真实条件熵
信息增益：熵 - 条件熵 （都是训练数据得到的）
D对应训练数据集，H（D）是不知道任何特征信息时所得的熵，如果知道X的特征信息（A），训练数据集有了重新分类，此时的熵是根据特征信息A发生的变化，变化越小说明更加确定，哪个特征所带来的信息增益越大，哪个特征就是最优特征

算信息增益的步骤：（具体看后面例题）

例题：
样本D=15
类别K=2
Ck是不附加任何特征时属于的类别
H(D)是不加特征时所得的训练数据集的熵：

加上了特征后的熵：经验条件熵。
加上年龄这个特征，将数据划分为D1、2、3。经验条件熵就是在给定A之后得到的n个子集，每个子集计算熵，加权求和。权重是Di中的个数/数据集D中的个数，也就是pi的估计值。i=1，pi=5/15，经验熵的计算方式如蓝色书写。

经验条件熵：H(D|A1)的计算通过pi、p2、p3和H(D1)、H(D2)、H(D3)得到：

给定有工作这个特征，将数据划分为D1、2

由于D1这个子集不包含不同意贷款，所以不同意贷款是不可能事件，所以携带信息量为0，所有样本归属同意贷款这类，所以对应-5/5log2 5/5这部分是完全确定性事件，携带信息量为0，因此D1的经验熵为0。D2和之前的计算方式一样

给定有房子这个特征，将数据划分为D1、2

给定信贷情况这个特征，将数据划分为D1、2、3

信息增益g（D，A）：

那个特征的信息增益更大？它便是最优特征。可以放在根结点处，下面的每一个内部结点，也可以根据信息增益的方法，寻找最优特征

信息增益比

信息增益倾向于选择具有更多取值的的那个特征。比如刚才“有自己的房子”有3个取值，比其他的特征要多。怎么消除取值较多带来的影响呢，就需要信息增益比，在信息增益的基础上加一个惩罚项，是D关于特征A的熵的倒数，也就是信息增益比gR（D，A）/HA(D)，想计算特征A单位取值个数下的信息增益，就把特征取值个数这个因素所带来的影响消除了。是D关于A的熵。
怎么计算HA(D)？找到每个子集对应的样本个数
比如A1是年龄，D1、2、3个数分别是5、5、5，A2是有工作，D1、2、3个数分别是5、10、0，HA1(D)和HA2(D)计算方式如图

计算信息增益比：

确定性强（条件熵小），信息增益高。
只看信息增益比的话，选择信息增益比高的。但说不清信息增益和信息增益比孰优孰劣。信息增益比倾向于选择具有更少取值的的那个特征

5.4 决策树的生成 -- ID3算法

信息增益来进行特征选择

如果不需要特征选择，可以直接生成决策树。用于①所有实例同属一类的情况（单结点数）、②特征集A=∅（空集）的时候（20天中18天是晴天，2天不是，没有温度湿度的信息，分类时归一类，生成单结点树）
需要特征选择
选择信息增益最大的特征（记作Ag），作为根节点。决策树是否只包含一个结点？需要用阈值ε判断，若信息增益小于ε，说明Ag不会给分类带来更多确定性，既然信息增益最大的特征都没有给树确定性，可以认为是单结点树。怎么确定类别？找到包含实例点最多的类别Ck，这个类别作为结点的类标记得到决策树

若信息增益大于ε，
根据D的特征取值来划分，比如取值为a1，归为D1子集。划分为n个子集。若D1……Dn都是单结点树便可停止，若不认为是这样接着选信息增益最大的特征，继续做决策树，相当于D1回到D做循环处理，选择特征时减去已经用过的Ag。

当所有特征的信息增益都小于ε，便划分完毕

决策树的生成 -- C4.5算法

信息增益比来进行特征选择
好处：克服偏向取值较多的特征，可以处理连续型特征。
坏处：计算麻烦（低效）

决策树的生成 -- 例子：

有四个特征，A≠∅，计算信息增益
信息增益如上图，若ε=0.001，四个信息增益都大于ε，不可以认为是单节点决策树
选择信息增益最大的特征来作为根节点
A3将D划分为D1、2
D1中只有一类，是叶结点
D2中有两类，再进行特征选择，将D2作为新训练数据集，A1、2、4作为新特征集，计算各特征的信息增益
对于A1（年龄）的信息增益：

同理计算A2、4的信息增益。
已经得到D2的经验熵，以D2作为新训练数据，A1、2、4作为新特征集，分别计算出经验条件熵，经验熵 - 经验条件熵得到信息增益。

“有工作”的信息增益最大，接下来的内部结点对应这个特征

5.5 决策树 -- 剪枝

评判是不是好的决策树：
能力是不是强：对已知和未知数据的分类能力
结构是不是简单

深度：所有结点的最大层次数
根节点深度0，往下结点深度+1

剪枝的目的：减少过拟合

预剪枝：若结点不能提高泛化能力，则不划分，记为叶结点
后剪枝：自底而上，若变为叶可以提高泛化能力，则剪掉

预剪枝

①设定深度（决策树层数），多余的层数，数一下哪个类别最多，就直接分为哪个类。

②阈值设定大，决策树简单
③设置指标：基于测试集上的误差率
（测试集中错误分类的实例占比）
划分前后若测试集上误差率降低，则划分，若不变或升高，则剪枝。

后剪枝

自下而上

降低错误剪枝（REP）

降低测试集的错误率

悲观错误剪枝（PEP）

只需训练集，计算训练集的错误率时用了修正方法，从离散二项分布到连续正态分布，加0.5来处理

每个叶结点上的误差率：error（Leafi）：叶结点上犯错个数比上全部样本个数为误差率
目标子树总的修正误差Error（T）：每个叶结点上的误差率之和。表示目标子树上所有的误判样本+修正部分（0.5×叶子结点个数L），也就是剪枝前的修正误差率。这个误差率为犯错概率。
再得到误判个数期望值，对于二项分布，期望是N×T，N是样本数，×犯错率是Error（T）。
再算标准差，对于二项分布，方差是npq，p是错误率，q是1-p，标准差是根号下方差。
计算误判上限：期望值+一个标准差

计算剪枝后的误差，剪枝后目标子树变成叶结点，误差率是多少？同样做修正，先看犯错的样本个数是多少（error（Leaf）），+0.5，除以N。
求剪枝后误判个数期望值
剪枝后误判个数与剪枝前误判上限比较
如果剪枝后误判个数期望值小于剪枝前误判上限，则剪枝，用叶结点替换

例子：
①剪枝前修正误差Error（T）= 剪枝前误判个数（3+2+1=6）+0.5×3（3个叶结点）/ 30（目标子树所有样本N）

②根据修正后错误率计算期望和方差（误判个数的期望值和误判个数的标准差）
期望E（T）= N×T=30×Error（T）= 7.5
方差Var（T）= npq=30×7.5/30×（1-7.5/30）=5.625
标准差std（T）= 方差开根号 = 2.37

③剪枝前误判个数上限 = 期望 + 标准差 =7.5 + 2.37 = 9.87

④剪枝后误差Error（Leaf） = 13（剪枝后，因为17>13，所以此叶结点为正类，那么误判个数为13）+ 0.5/30 = 13.5/30 。因为是一个叶结点，加一个0.5就可以了

⑤剪枝后误判个数期望值E（Leaf）= 30 × 13.5/30 = 13.5

⑥比较
9.87<13.5 剪枝后误判个数期望值比剪枝前误判上限大，所以不剪枝

最小误差剪枝（MEP）

最小分类错误概率

m表示了先验概率对于后验概率的影响程度

Prk（T）：先验概率=1/K（样本属于每个类的概率相同），当m=K（此处指定）

计算T7和T8的预测错误率：
Error（T7）= 2（不属于正类的个数）+ 1（K-1） /11（样本总数）+ 2 （正负两个类别，K=2）= 3/13
Error（T8）= 1+1 / 9+2 = 2/11

加权的方式：
T7处权重：11 / 20（一共是20个样本）
T8处权重：9 / 20

剪枝前目标子树的预测错误率：Error（Leaf）= 11/20 × 3/13 +9 / 20 × 2/11 =0.2087

剪枝后（直接将T5划为叶结点，正负的个数相同，不妨就归正类）
Error（T5）=10（判错的样本）+1 /20 + 2 = 0.5

0.2087<0.5，所以剪枝后预测错误率增大

基于错误剪枝（EBP）

此处对应视频p51的内容，先不做学习要求。
【合集】十分钟 机器学习 系列视频 《统计学习方法》_哔哩哔哩_bilibili

p52 代价复杂度剪枝（CCP）
【合集】十分钟 机器学习 系列视频 《统计学习方法》_哔哩哔哩_bilibili