相关算法实现_集成算法是什么?

1 决策树

1.1 分类树

1.1.1 信息熵1.1.2 案例1.1.3 基尼Gini指数1.1.4 案例 1.2 回归树

1.2.1 回归树分支标准1.2.2 案例

信息熵是用来衡量信息不确定性的指标，不确定性是一个事件出现不同结果的可能性，计算方法如下所示：
H ( X ) = − ∑ i = 1 n P ( X = i ) l o g 2 P ( X = i ) H(X)=-sum_{i=1}^{n}P(X=i)log_2P(X=i) H(X)=−i=1∑n​P(X=i)log2​P(X=i)

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

E n t r o p y = − 0.5 ∗ l o g 0.5 − 0.5 ∗ l o g 0.5 = 1 Entropy=-0.5*log{0.5}-0.5*log{0.5}=1 Entropy=−0.5∗log0.5−0.5∗log0.5=1

E n t r o p y = − 0.99 ∗ l o g 0.99 − 0.01 ∗ l o g 0.01 = 0.08 Entropy=-0.99*log{0.99}-0.01*log{0.01}=0.08 Entropy=−0.99∗log0.99−0.01∗log0.01=0.08

条件熵
在给定随机变量Y的条件下，随机变量X的不确定性
H ( X ∣ Y = v ) = − ∑ i = 1 n P ( X = i ∣ Y = v ) l o g 2 P ( X = i ∣ Y = v ) H(X|Y=v)=-sum_{i=1}^{n}P(X=i|Y=v)log_2P(X=i|Y=v) H(X∣Y=v)=−i=1∑n​P(X=i∣Y=v)log2​P(X=i∣Y=v)

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

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

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

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

具体流程：

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

H ( X ) = − 0.36 ∗ l o g 2 0.36 − 0.64 ∗ l o g 2 0.64 = 0.940 H(X)=-0.36*log_{2}0.36-0.64*log_{2}0.64=0.940 H(X)=−0.36∗log2​0.36−0.64∗log2​0.64=0.940

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

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

学历

X=是否接受
Y=学历
其中i为：是和否接受
H ( Y = 学 历 ) = − H ( X ∣ Y = 专 科 ) − H ( X ∣ Y = 本 科 ) − H ( X ∣ Y = 硕 士 ) H(Y=学历)=-H(X|Y=专科)-H(X|Y=本科)-H(X|Y=硕士) H(Y=学历)=−H(X∣Y=专科)−H(X∣Y=本科)−H(X∣Y=硕士)
H ( X ∣ Y = 专 科 ) = − ∑ i = 1 n P ( X = i ∣ Y = 专 科 ) l o g 2 P ( X = i ∣ Y = 专 科 ) H(X|Y=专科)=-sum_{i=1}^{n}P(X=i|Y=专科)log_2P(X=i|Y=专科) H(X∣Y=专科)=−i=1∑n​P(X=i∣Y=专科)log2​P(X=i∣Y=专科)

H ( X ∣ Y = 专 科 ) = H ( Y = 专 科 ) ∗ P ( Y = 专 科 ) H(X|Y=专科)=H(Y=专科)*P(Y=专科) H(X∣Y=专科)=H(Y=专科)∗P(Y=专科)

H ( Y = 专 科 ) = 0.40 ∗ l o g 2 0.40 + 0.60 ∗ l o g 2 0.60 = 0.971 H(Y=专科)=0.40*log_{2}0.40+0.60*log_{2}0.60=0.971 H(Y=专科)=0.40∗log2​0.40+0.60∗log2​0.60=0.971
P ( Y = 专 科 ) = 5 5 + 4 + 5 = 0.36 P(Y=专科)=frac{5}{5+4+5}=0.36 P(Y=专科)=5+4+55​=0.36
H ( X ∣ Y = 专 科 ) = H ( Y = 专 科 ) ∗ P ( Y = 专 科 ) = 0.36 ∗ 0.971 H(X|Y=专科)=H(Y=专科)*P(Y=专科)=0.36*0.971 H(X∣Y=专科)=H(Y=专科)∗P(Y=专科)=0.36∗0.971

学历的信息熵为： 0.36 ∗ 0.971 + 0.36 ∗ 0.971 + 0.29 ∗ 0 = 0.69 0.36*0.971+0.36*0.971+0.29*0=0.69 0.36∗0.971+0.36∗0.971+0.29∗0=0.69

婚史

婚史的信息熵为： 0.43 ∗ 0.918 + 0.29 ∗ 1.000 + 0.29 ∗ 0.811 = 0.92 0.43*0.918+0.29*1.000+0.29*0.811=0.92 0.43∗0.918+0.29∗1.000+0.29∗0.811=0.92

房

房的信息熵为： 0.50 ∗ 0.985 + 0.50 ∗ 0.592 = 0.79 0.50*0.985+0.50*0.592=0.79 0.50∗0.985+0.50∗0.592=0.79

车

车的信息熵为： 0.43 ∗ 1.000 + 0.57 ∗ 0.811 = 0.89 0.43*1.000+0.57*0.811=0.89 0.43∗1.000+0.57∗0.811=0.89

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

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

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

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

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

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

G i n i ( p ) = ∑ k = 1 k p k ( 1 − p k ) = 1 − ∑ k = 1 k p k 2 Gini(p)=sum_{k=1}^{k}p_k(1-p_k)=1-sum_{k=1}^{k}p_k^2 Gini(p)=k=1∑k​pk​(1−pk​)=1−k=1∑k​pk2​

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

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

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

G i n i = 1 − ∑ i = 1 2 p 2 = 1 − ( 5 14 ) 2 − ( 9 14 ) 2 = 0.459 Gini=1-sum_{i=1}^{2}p^2=1-(frac{5}{14})^2-(frac{9}{14})^2=0.459 Gini=1−∑i=12​p2=1−(145​)2−(149​)2=0.459

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

学历

加权的基尼：
0.36 ∗ G i n i ( 专 科 ) + 0.36 ∗ G i n i ( 本 科 ) + 0.29 ∗ G i n i ( 硕 士 ) 0.36*Gini(专科)+0.36*Gini(本科)+0.29*Gini(硕士) 0.36∗Gini(专科)+0.36∗Gini(本科)+0.29∗Gini(硕士)
= 0.36 ∗ ( 1 − ( 3 5 ) 2 − ( 2 5 ) 2 ) + 0.36 ∗ ( 1 − ( 2 5 ) 2 − ( 3 5 ) 2 ) + 0.29 ∗ ( 1 − ( 4 4 ) 2 − ( 0 4 ) 2 ) = 0.342 =0.36*(1-(frac{3}{5})^2-(frac{2}{5})^2)+0.36*(1-(frac{2}{5})^2-(frac{3}{5})^2)+0.29*(1-(frac{4}{4})^2-(frac{0}{4})^2)=0.342 =0.36∗(1−(53​)2−(52​)2)+0.36∗(1−(52​)2−(53​)2)+0.29∗(1−(44​)2−(40​)2)=0.342

婚史

加权的基尼：
0.43 ∗ G i n i ( 无 婚 ) + 0.29 ∗ G i n i ( 有 婚 ) + 0.29 ∗ G i n i ( 无 婚 ) 0.43*Gini(无婚)+0.29*Gini(有婚)+0.29*Gini(无婚) 0.43∗Gini(无婚)+0.29∗Gini(有婚)+0.29∗Gini(无婚)
= 0.43 ∗ ( 1 − ( 4 6 ) 2 − ( 2 6 ) 2 ) + 0.29 ∗ ( 1 − ( 2 4 ) 2 − ( 2 4 ) 2 ) + 0.29 ∗ ( 1 − ( 3 4 ) 2 − ( 1 4 ) 2 ) = 0.4405 =0.43*(1-(frac{4}{6})^2-(frac{2}{6})^2)+0.29*(1-(frac{2}{4})^2-(frac{2}{4})^2)+0.29*(1-(frac{3}{4})^2-(frac{1}{4})^2)=0.4405 =0.43∗(1−(64​)2−(62​)2)+0.29∗(1−(42​)2−(42​)2)+0.29∗(1−(43​)2−(41​)2)=0.4405

房

加权的基尼：
0.50 ∗ G i n i ( 有 房 ) + 0.50 ∗ G i n i ( 无 房 ) 0.50*Gini(有房)+0.50*Gini(无房) 0.50∗Gini(有房)+0.50∗Gini(无房)
= 0.5 ∗ ( 1 − ( 3 7 ) 2 − ( 4 7 ) 2 ) + 0.50 ∗ ( 1 − ( 6 7 ) 2 − ( 1 7 ) 2 ) = 0.3674 =0.5*(1-(frac{3}{7})^2-(frac{4}{7})^2)+0.50*(1-(frac{6}{7})^2-(frac{1}{7})^2)=0.3674 =0.5∗(1−(73​)2−(74​)2)+0.50∗(1−(76​)2−(71​)2)=0.3674

车

加权的基尼：
0.43 ∗ G i n i ( 有 车 ) + 0.57 ∗ G i n i ( 无 车 ) 0.43*Gini(有车)+0.57*Gini(无车) 0.43∗Gini(有车)+0.57∗Gini(无车)
= 0.43 ∗ ( 1 − ( 3 6 ) 2 − ( 3 6 ) 2 ) + 0.57 ∗ ( 1 − ( 6 8 ) 2 − ( 2 8 ) 2 ) = 0.4286 =0.43*(1-(frac{3}{6})^2-(frac{3}{6})^2)+0.57*(1-(frac{6}{8})^2-(frac{2}{8})^2)=0.4286 =0.43∗(1−(63​)2−(63​)2)+0.57∗(1−(86​)2−(82​)2)=0.4286

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

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

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

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

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

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

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

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

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

1.计算年龄的标准方差：
S = ∑ ( x − x ^ ) 2 n = 9.32 S=sqrt{frac{sum(x-hat x)^2}{n}}=9.32 S=n∑(x−x^)2​ ​=9.32

2.计算不同单一的条件下，每一个特征的标准方差，最后并进行加权求和，

学历、婚史、房、车分别去年龄做数据透视图

学历

加权的标准差：
0.36 ∗ S ( 专 科 ) + 0.36 ∗ S ( 本 科 ) + 0.29 ∗ S ( 硕 士 ) 0.36*S(专科)+0.36*S(本科)+0.29*S(硕士) 0.36∗S(专科)+0.36∗S(本科)+0.29∗S(硕士)
= 0.36 ∗ 7.78 + 0.36 ∗ 10.87 + 0.29 ∗ 3.49 = 7.66 =0.36*7.78+0.36*10.87+0.29*3.49=7.66 =0.36∗7.78+0.36∗10.87+0.29∗3.49=7.66

婚史

加权的标准差：
0.43 ∗ S ( 无 婚 ) + 0.29 ∗ S ( 有 婚 ) + 0.29 ∗ S ( 二 婚 ) 0.43*S(无婚)+0.29*S(有婚)+0.29*S(二婚) 0.43∗S(无婚)+0.29∗S(有婚)+0.29∗S(二婚)
= 0.43 ∗ 7.65 + 0.36 ∗ 8.95 + 0.29 ∗ 10.51 = 9.15 =0.43*7.65+0.36*8.95+0.29*10.51=9.15 =0.43∗7.65+0.36∗8.95+0.29∗10.51=9.15

房

加权的标准差：
0.50 ∗ S ( 有 房 ) + 0.50 ∗ S ( 无 房 ) 0.50*S(有房)+0.50*S(无房) 0.50∗S(有房)+0.50∗S(无房)
= 0.50 ∗ 9.36 + 0.50 ∗ 8.37 = 9.04 =0.50*9.36+0.50*8.37=9.04 =0.50∗9.36+0.50∗8.37=9.04

车

加权的标准差：
0.43 ∗ S ( 有 车 ) + 0.57 ∗ S ( 无 车 ) 0.43*S(有车)+0.57*S(无车) 0.43∗S(有车)+0.57∗S(无车)
= 0.43 ∗ 10.59 + 0.57 ∗ 7.87 = 9.03 =0.43*10.59+0.57*7.87=9.03 =0.43∗10.59+0.57∗7.87=9.03

3.计算不同条件下标准差增益

选择哪个条件跟熵、基尼一样的，如果是看标准差就看最小的，如果是看标准差增益看最大的。