集成学习：算法理论 （超详细）

1 决策树

1.1 分类树

1.1.1 信息熵

信息熵是用来衡量信息不确定性的指标，不确定性是一个事件出现不同结果的可能性，计算方法如下所示：
$$H(X)=-\sum _{i=1}^{n}P(X=i)lo{g}_{2}P(X=i)$$

其中：$P(X=i)$为随机变量x取值为i的概率

$$Entropy=-0.5\ast log0.5-0.5\ast log0.5=1$$

$$Entropy=-0.99\ast log0.99-0.01\ast log0.01=0.08$$

条件熵
在给定随机变量Y的条件下，随机变量X的不确定性
$$H(X|Y=v)=-\sum _{i=1}^{n}P(X=i|Y=v)lo{g}_{2}P(X=i|Y=v)$$

信息增益
熵-条件熵，代表了在一个条件下，信息不确定性减少的程度
$$I(X,Y)=H(X)-H(X|Y)$$

总结一下，信息熵，条件熵，信息增益
以相亲为例来说，相亲要跟居然对方外貌、身高，经济等条件，做出是否结果对方继续相处的选择。是或者否

• 信息熵：直接对选择是或否的数量做相关的公式计算。
• 条件熵：在一定条件下选择是或否的数量做相关公式计算，比如我们看在有房条件里，看对方是否继续相处的数量，做相关公式计算
• 信息增益：类似于对每一个相亲条件给出优先级，数值，有人最在意外貌，其次是身高，对方有没有钱无所谓。与之不同的地方，是需要选择条件，每一轮选择一个优先级最高的条件后，要对剩下的条件，基于上一个条件下重新计算，选出最高的优先级

1.1.2 案例

假设有下图这样一群相亲对象的人选，以及他们被对方是否接受的历史记录，现在我们需要通过这个数据来判断下一位相亲对象是否被接受，因此我们需要计算信息增益

具体流程：

1.计算是否接受相亲对象的信息熵

$$H(X)=-0.36\ast lo{g}_{2}0.36-0.64\ast lo{g}_{2}0.64=0.940$$

2.下一步，我们计算不同单一的条件下，每一个特征的条件熵，最后并进行求和，得出单一条件的信息熵

单一条件，比如说学历，特征就是：专科、本科、硕士。

学历

X=是否接受
Y=学历
其中i为：是和否接受
$$H(Y=学历)=-H(X|Y=专科)-H(X|Y=本科)-H(X|Y=硕士)$$
$$H(X|Y=专科)=-\sum _{i=1}^{n}P(X=i|Y=专科)lo{g}_{2}P(X=i|Y=专科)$$

$$H(X|Y=专科)=H(Y=专科)\ast P(Y=专科)$$

$$H(Y=专科)=0.40\ast lo{g}_{2}0.40+0.60\ast lo{g}_{2}0.60=0.971$$
$$P(Y=专科)=\frac{5}{5+4+5}=0.36$$
$$H(X|Y=专科)=H(Y=专科)\ast P(Y=专科)=0.36\ast 0.971$$

学历的信息熵为：$0.36\ast 0.971+0.36\ast 0.971+0.29\ast 0=0.69$

婚史

婚史的信息熵为：$0.43\ast 0.918+0.29\ast 1.000+0.29\ast 0.811=0.92$

房

房的信息熵为：$0.50\ast 0.985+0.50\ast 0.592=0.79$

车

车的信息熵为：$0.43\ast 1.000+0.57\ast 0.811=0.89$

3.计算不同条件下的信息增益

选择学历信息增益最大的值，做为节点。

4.对新的节点，循环1、2、3的操作，直到条件分类完

基于上面的学历，我们分出的新的三个节点，专科、本科、硕士。在这些条件下，对应着不同的数据集。

1.1.3 基尼Gini指数

基尼指数(Gini不纯度)表示在样本集合中一个随机选中的样本被分错的概率。

Gini指数越小表示集合中被选中的样本被分错的概率越小。也就是集合的纯度越高。
计算公式如下：

$$Gini(p)=\sum _{k=1}^k{p}_k(1-p_k)=1-\sum _{k=1}^k{p}_k^2$$

其中，$p_k$表示选中的样本属于第k个类别的概率。

1.1.4 案例

回到刚才的案例，流程上与计算熵流程一致，只是说现在不是计算熵了，是计算基尼了

1.计算是否接受相亲对象的基尼

$Gini=1-{\sum }_{i=1}^2{p}^2=1-(\frac{5}{14}{)}^2-(\frac{9}{14}{)}^2=0.459$

2.计算不同单一的条件下，每一个特征的基尼，最后并进行加权求和，得出单一条件的基尼

学历

加权的基尼：
$0.36\ast Gini(专科)+0.36\ast Gini(本科)+0.29\ast Gini(硕士)$
$=0.36\ast (1-(\frac{3}{5}{)}^2-(\frac{2}{5}{)}^2)+0.36\ast (1-(\frac{2}{5}{)}^2-(\frac{3}{5}{)}^2)+0.29\ast (1-(\frac{4}{4}{)}^2-(\frac{0}{4}{)}^2)=0.342$

婚史

加权的基尼：
$0.43\ast Gini(无婚)+0.29\ast Gini(有婚)+0.29\ast Gini(无婚)$
$=0.43\ast (1-(\frac{4}{6}{)}^2-(\frac{2}{6}{)}^2)+0.29\ast (1-(\frac{2}{4}{)}^2-(\frac{2}{4}{)}^2)+0.29\ast (1-(\frac{3}{4}{)}^2-(\frac{1}{4}{)}^2)=0.4405$

房

加权的基尼：
$0.50\ast Gini(有房)+0.50\ast Gini(无房)$
$=0.5\ast (1-(\frac{3}{7}{)}^2-(\frac{4}{7}{)}^2)+0.50\ast (1-(\frac{6}{7}{)}^2-(\frac{1}{7}{)}^2)=0.3674$

车

加权的基尼：
$0.43\ast Gini(有车)+0.57\ast Gini(无车)$
$=0.43\ast (1-(\frac{3}{6}{)}^2-(\frac{3}{6}{)}^2)+0.57\ast (1-(\frac{6}{8}{)}^2-(\frac{2}{8}{)}^2)=0.4286$

3.计算不同条件下的Gini增益

选择学历基尼增益最大的值，做为节点，

其实我们可以不用考虑增益这个计算，只需要记住，求熵还是求基尼就看谁小，就增益就看谁大就行了。

1.2 回归树

回归树，用决策树的模型来实现回归模型，每一个一个树的叶子为最后多个下特征的预测值，只不过这个预测值是当下特征下，预测出的所有情况的均值。

还是回到原来的案例，在原来数据集上我们增加一列年龄，现在年龄才是我们的预测Y值。

假设我们训练集三条这样的特征(专科、无婚、无房、无车)，其中年龄的值如下图，

这里就需要对三个值，求平均值，用平均值的值作为三条数据的年龄，加入到模型训练。

1.2.1 回归树分支标准

标准方差是回归树的分支标准，回归树将某一特征分成多个子集，用标准方差来衡量子集之间的元素是否相近，方差越小，证明这二个子集元素越相近，就不能划分成二个子集，需要合并，方差越大，就说明二个子集是不同的。

1.2.2 案例

流程其实跟前面求熵，求基尼都差不多