监督学习——决策树
1.1. 决策树
度量方法：
信息增益（ID3）
信息增益率（C4.5）
基尼指数（CART）
对一个给定样本分类所需要的信息熵：
S：是s个数据样本的集合
m：类别标签具有m个
：定义m个不同类
：是类
中样本数
：任意样本属于
的概率，
信息期望：
信息增益：
例如：
1.1.1. 迭代Dichotomiser3（ID3）
（1）给定样本分类的信息熵
类别标签S被分为两类：买或不买。S1(买)=640；S2(不买)=384。S=S1+S2=1024。S1的概率p1=640/1024=0.625；S2的概率p2=384/1024=0.375。
则信息熵：
（2）计算每个特征的信息熵
年龄：青年(0)、中年(1)、老年(2)。
P(0)=384/1024=0.375;青年中买的S1(买)=128，p1=128/384；S2(不买)=256，p2=256/384;
P(1)=256/1024=0.25;中年中买的S1(买)=256，p1=1；S2(不买)=0，p2=0;
P(2)=384/1024=0.375;老年中买的S1(买)=257，p1=257/384；S2(不买)=127，p2=127/384;
年龄的平均信息期望：
学生：学生分为两组：是(0)、否(1)
收入：高(0)、中(1)、低(2)
信誉：优(0)、良(1)
（3）从所有特征列中选出信息增益最大的那个作为根节点或内部节点（划分节点），首次递归选择年龄列G(年龄)=0.2667来划分。
（4）计算剩余特征列的信息熵，如果有信息增益则重复以上
（5）结束标志：子集中只有一个类别标签，停止划分。
1.1.2. C4.5算法
ID3算法改进为C4.5算法。C4.5用信息增益率（GainRatio）来代替信息增益（Gain），克服了信息增益选择特征时偏向于特征个数较多的不足。
Gain(S,A)就是ID3算法中的信息增益，
1.1.3. 分类树和回归树（CART）
CART算法是决策树算法中最成熟的算法，既可以用来分类，也可以用来预测。是一种通过决策树的方法实现回归的算法。
CART既是分类树又是回归树
当CART 是分类树时采用GINI（基尼指数）作为分裂节点的一句，当CART作为回归树时，使用样本的最小方差作为分裂节点的依据。
CART使用最小剩余方差来判定回归树的最优划分，这个准则期望划分后子树与样本点的误差方差最小。这样决策树将数据集切分成很多子模型数据，然后利用线性回归来建模，每个叶子节点都是一个线性回归模型，被称为模型树。
分类树
基尼指数：
分类问题中，假设有K个类，样本点属于第K类的概率为pk，则概率分布的基尼指数定义为
对于二分类问题来说，若样本点属于第一类的·概率为p，则概率分布的基尼指数为
对于给定的样本集合D，其基尼指数为
其中，Ck是D中属于第k类的样本子集，K是类的个数。|Ck|和D分别表示子集的个数和样本的个数。如果样本集合D根据特征A是否取某一可能的值α被分割成D1和D2，即
所以在特征A的条件下集合D的基尼指数为
其中基尼指数Gini(D)表示集合的不确定性，基尼指数G(D,A)表示A=a分解后集合的不决定性。基尼指数越大，样本集合的不确定性越大。
回归树
最小二乘法回归树生成算法：
1）依次遍历每个特征j，以及该特征的每个取值s，计算每个切分点（j,s）的损失函数，选择损失函数最小的切分点。
2）使用上步得到的切分点将当前的输入空间划分为两个部分
3）然后将被划分后的两个部分再次计算切分点，依次类推，直到不能继续划分。
4）最后将输入空间划分为M个区域R1,R2,…,RM,生成的决策树为：
其中cm为所在区域的输出值的平均。
例如：
利用上面的数据对年龄进行预测：
首先将j的属性宣威职业，则有三种划分情况：
{“老师”，“学生”}、{“上班族”}
{“老师”，“上班族”}、{“学生”}
{“学生”，“上班族”}、{“老师”}
第一种情况R1={“学生”}，R2={“老师”，”上班族”}：
c1=(12+18+21)/3=17
c2=(26+47+36+29)/4=34.5
yi∈(年龄)=({12,18,21},{26,47,36,29})
最小平方误差计算得：
m = 42+261 = 303
第二种情况R1={“上班族”}，R2={“学生”，”老师”} ：
c1=27.5,c2=26.5
m=4.5+738.16=742.66
(3)第三种情况R1={“上班族”}，R2={“学生”，”老师”}
c1=41.5,c2=21.2
m=60.5+178.8=238.8
根据上面计算得到第三种划分方式误差最小，因此此时的决策树为：
这只是一个特征情况下的分类，按照同样的方法对其他特征情况进行划分计算，找到最合适的最初划分点。经过计算如果按照是否已婚划分得到m=545.67，如果按照看电视时间大于3.4h或者小于3.4h得到m=420，所以初始划分按照。这样数据集就划分为两类，然后再按照以上方法划分，直到满足设置的误差最小化阈值。
当然，处理具体问题时，单一的回归树肯定是不够用的。可以利用集成学习中的boosting框架，对回归树进行改良升级，得到的新模型就是提升树（Boosting Decision Tree），在进一步，可以得到梯度提升树（Gradient Boosting Decision Tree，GBDT），再进一步可以升级到XGBoost。
为了后续章节的提升树介绍，我们再举个例子：
训练数据见下表，得到一颗回归树：
X |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
Y |
5.56 |
5.7 |
5.91 |
6.4 |
6.8 |
7.05 |
8.9 |
8.7 |
9 |
9.05 |
1. 选择最优切分变量j与最优切分点s
接下来我们考虑9个切分点[1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5,9.5]
取s=1.5，此时 R1={1},R2={2,3,4,5,6,7,8,9,10}，这两个区域的输出值分别为：c1=5.56，c2=19(5.7+5.91+6.4+6.8+7.05+8.9+8.7+9+9.05)=7.50。
取s=2.5，c1=5.63，s2=7.73，等等，
得到下表：
s |
1.5 |
2.5 |
3.5 |
4.5 |
5.5 |
6.5 |
7.5 |
8.5 |
9.5 |
c1 |
5.56 |
5.63 |
5.72 |
5.89 |
6.07 |
6.24 |
6.62 |
6.88 |
7.11 |
c2 |
7.5 |
7.73 |
7.99 |
8.25 |
8.54 |
8.91 |
8.92 |
9.03 |
9.05 |
计算m(1.5)=0+15.72=15.72等等，得到下表：
s |
1.5 |
2.5 |
3.5 |
4.5 |
5.5 |
6.5 |
7.5 |
8.5 |
9.5 |
m(s) |
15.72 |
12.07 |
8.36 |
5.78 |
3.91 |
1.93 |
8.01 |
11.73 |
15.74 |
显然s=6.5时，m(s)最小。因此，第一个划分变量s=6.5
对这个选定划分后的两个区域为R1={1,2,3,4,5,6},R2={7,8,9,10}输出值c1=6.24,c2=8.91。
2. 对这两个子区域继续调用步骤1（提升树就是在这里做了优化，见后续章节）
对R1继续进行划分：
X |
1 |
2 |
3 |
4 |
5 |
6 |
Y |
5.56 |
5.7 |
5.91 |
6.4 |
6.8 |
7.05 |
取切分点[1.5,2.5,3.5,4.5,5.5]，则各区域的输出值c如下表
s |
1.5 |
2.5 |
3.5 |
4.5 |
5.5 |
c1 |
5.56 |
5.63 |
5.72 |
5.89 |
6.07 |
c2 |
6.37 |
6.54 |
6.75 |
6.93 |
7.05 |
计算m(s)：
s |
1.5 |
2.5 |
3.5 |
4.5 |
5.5 |
m(s) |
1.3078 |
0.754 |
0.2771 |
0.4368 |
1.0644 |
S=3.5时m(s)最小。之后过程同上，
3. 生成回归树
假设在生成3个区域后停止划分了，那么最终的回归树如下：