**熵：**衡量不确定程度。熵越大，随机变量不确定性越大。熵只依赖于随机变量X的分布，与X的取值无关。
H
(
p
)
=
−
∑
i
n
p
i
l
o
g
(
p
i
)
H(p) = -sum_i^n p_i log(p_i)
H(p)=−i∑npilog(pi)
当随机变量只有两个值0，1的时候，
P
(
X
=
1
)
=
p
;
P
(
X
=
0
)
=
1
−
p
;
0
≤
p
≤
1
P(X=1)=p; P(X=0)=1-p; 0 leq p leq 1
P(X=1)=p;P(X=0)=1−p;0≤p≤1
H
(
0
)
=
−
[
p
l
o
g
(
p
)
+
(
1
−
p
)
l
o
g
(
1
−
p
)
]
H(0) = -[ plog(p)+(1-p)log(1-p) ]
H(0)=−[plog(p)+(1−p)log(1−p)]
熵随概率
p
p
p变化的曲线如下图，当p=0或p=1的时，H§=0，随机变量完全没有不确定性; 当p=0.5时，H§=1，随机变量不确定性最大（p=0.5相当于随机抽）
条件熵： H(Y|X)，给定条件X之后随机变量Y的不确定性
H
(
Y
∣
X
)
=
∑
i
n
p
i
H
(
Y
∣
X
=
x
i
)
=
∑
i
n
P
(
X
=
x
i
)
H
(
Y
∣
X
=
x
i
)
H(Y|X) = sum_i^n p_i H(Y|X=x_i) = sum_i^n P(X=x_i) H(Y|X=x_i)
H(Y∣X)=i∑npiH(Y∣X=xi)=i∑nP(X=xi)H(Y∣X=xi)
信息增益：已知特征X的信息对Y的不确定性减少的程度； 表示为
H
(
Y
)
−
H
(
Y
∣
X
)
H(Y) - H(Y|X)
H(Y)−H(Y∣X)。
例子：
- 样本量N=15，9个正样本，6个负样本；
熵 ： H ( Y ) = − 9 15 ∗ l o g ( 9 15 ) − 6 15 ∗ l o g ( 6 15 ) 熵：H(Y) = - frac{9}{15}*log(frac{9}{15})-frac{6}{15}*log(frac{6}{15}) 熵：H(Y)=−159∗log(159)−156∗log(156) - 特征X1：年龄{‘青年’：{正：2，负：3}；‘中年’：{正：3，负：2}；‘老年’：{正：4，负：1}}
条 件 熵 ： H ( Y ∣ X ) = ∑ 5 15 ∗ H ( Y ∣ X = X 青 年 ) + 5 15 ∗ H ( Y ∣ X = X 中 年 ) + 5 15 ∗ H ( Y ∣ X = X 老 年 ) 其 中 ： H ( Y ∣ X = X 青 年 ) = − 2 5 ∗ l o g ( 2 5 ) − 3 5 ∗ l o g ( 3 5 ) H ( Y ∣ X = X 中 年 ) = − 3 5 ∗ l o g ( 3 5 ) − 2 5 ∗ l o g ( 2 5 ) H ( Y ∣ X = X 老 年 ) = − 4 5 ∗ l o g ( 1 5 ) − 1 5 ∗ l o g ( 1 5 ) 条件熵：H(Y|X) = sum frac{5}{15}*H(Y|X=X_{青年})+frac{5}{15}*H(Y|X=X_{中年}) \ +frac{5}{15}*H(Y|X=X_{老年}) \ 其中：H(Y|X=X_{青年}) = - frac{2}{5}*log(frac{2}{5})-frac{3}{5}*log(frac{3}{5}) \ H(Y|X=X_{中年}) = - frac{3}{5}*log(frac{3}{5})-frac{2}{5}*log(frac{2}{5}) \ H(Y|X=X_{老年}) = - frac{4}{5}*log(frac{1}{5})-frac{1}{5}*log(frac{1}{5}) 条件熵：H(Y∣X)=∑155∗H(Y∣X=X青年)+155∗H(Y∣X=X中年)+155∗H(Y∣X=X老年)其中：H(Y∣X=X青年)=−52∗log(52)−53∗log(53)H(Y∣X=X中年)=−53∗log(53)−52∗log(52)H(Y∣X=X老年)=−54∗log(51)−51∗log(51)
信息增益：已知特征X的信息对Y的不确定性减少的程度； 表示为 H ( Y ) − H ( Y ∣ X ) H(Y) - H(Y|X) H(Y)−H(Y∣X)。
**信息增益比：**以信息增益作为准则划分特征时，偏向于类别较多的特征，增益比可校正这一问题
从数据集D中随机抽取2个样本，类别标记不一致的概率。基尼指数越小，数据集的纯度越高
G
i
n
i
(
D
)
=
∑
k
K
p
k
(
1
−
p
k
)
=
1
−
∑
k
K
p
k
2
，
K
为
类
别
数
量
Gini(D) = sum_k^K p_k(1-p_k)=1-sum_k^K {p_k}^2，K为类别数量
Gini(D)=k∑Kpk(1−pk)=1−k∑Kpk2，K为类别数量
对于二分类问题：
G
i
n
i
(
D
)
=
p
1
(
1
−
p
1
)
+
p
0
(
1
−
p
0
)
=
2
p
1
(
1
−
p
1
)
Gini(D) = p_1(1-p_1) + p_0(1-p_0) = 2p_1(1-p_1)
Gini(D)=p1(1−p1)+p0(1−p0)=2p1(1−p1)
C4.5决策树采用的方法：二分法，特征所有取值的中位数作为划分点。
例子：
假设特征X1为学生的成绩，
X
1
=
{
34
,
43
,
23
,
45
,
55
,
70
}
X1={34,43,23,45,55,70}
X1={34,43,23,45,55,70}，排序后变成
X
1
=
{
23
,
34
,
43
,
45
,
55
,
70
}
X1={23,34,43,45,55,70}
X1={23,34,43,45,55,70}，取中位数作为划分点
T
1
=
{
23
+
34
2
,
34
+
43
2
,
43
+
45
2
,
45
+
55
2
,
55
+
70
2
}
T1={frac{23+34}{2},frac{34+43}{2},frac{43+45}{2},frac{45+55}{2},frac{55+70}{2} }
T1={223+34,234+43,243+45,245+55,255+70}，然后分别计算这些划分点对应的信息增益，选择其中信息增益最大的划分点。
建立回归树的过程大致可以分为两步：
- 将特征空间 ( X 1 , X 2 , X 3 , ⋯ , X p ) (X_1 , X_2 , X_3 , ⋯ , X_p) (X1,X2,X3,⋯ ,Xp)的可能取值构成的集合分割成J 个互不重叠的区域 R 1 , R 2 , R 3 , ⋯ , R j { R_1 , R_2 , R_3 , ⋯ , R_j } R1,R2,R3,⋯ ,Rj
- 对落入区域
R
j
R_j
Rj的每个观测值作同样的预测，预测值等于
R
j
R_j
Rj上训练集的各个样本取值的算术平均数。
比如，在第一步中得到两个区域 R 1 R_1 R1和 R 2 R_2 R2， R 1 R_1 R1中训练集的各个样本取值的算术平均数为10， R 2 R_2 R2中训练集的各个样本取值的算术平均数为20。则对给定的观测值 X = x X = x X=x，若 x ∈ R 1 x in R_1 x∈R1，则给出的预测值为10；若 x ∈ R 2 x in R_2 x∈R2，则给出的预测值为20。
所以，决策树分类算法的关键在于如何构建区域划分
R
1
,
R
2
,
R
3
,
⋯
,
R
j
{ R_1 , R_2 , R_3 , ⋯ , R_j }
R1,R2,R3,⋯ ,Rj。事实上，区域的形状是可以为任意形状的，但出于模型简化和增强可解释性的考虑，这里将预测变量空间划分成高维矩形，我们称这些区域为称盒子。划分区域的目标是找到使模型的残差平方和RSS最小的矩形区域
R
1
,
R
2
,
R
3
,
⋯
,
R
j
{ R_1 , R_2 , R_3 , ⋯ , R_j }
R1,R2,R3,⋯ ,Rj。RSS的定义为：
R
S
S
=
∑
j
=
1
J
∑
i
∈
R
j
(
y
i
−
y
^
R
j
)
2
RSS = sum_{j=1}^J sum_{i in R_j} (y_i - hat y_{R_j})^2
RSS=j=1∑Ji∈Rj∑(yi−y^Rj)2
在执行递归二又分裂时，先选择预测变量
X
j
X_j
Xj和分割点s，将预测变量空间分为两个区域
{
X
∣
X
j
<
s
}
{ X ∣ X_j < s }
{X∣Xj
R
1
(
j
,
s
)
=
{
X
∣
X
j
<
s
}
和
R
2
(
j
,
s
)
=
{
X
∣
X
j
≥
s
}
R_1(j,s) = { X ∣ X_j < s } 和 R_2(j,s) = { X ∣ X_j geq s }
R1(j,s)={X∣Xj
寻找
j
j
j和
s
s
s，使得下式最小：
∑
x
i
∈
R
1
(
j
,
s
)
(
y
i
−
y
‾
R
1
)
2
+
∑
x
i
∈
R
2
(
j
,
s
)
(
y
i
−
y
‾
R
2
)
2
sum_{x_i in R_1(j,s)} (y_i - overline y_{R_1})^2 + sum_{x_i in R_2(j,s)} (y_i - overline y_{R_2})^2
xi∈R1(j,s)∑(yi−yR1)2+xi∈R2(j,s)∑(yi−yR2)2
区域
R
1
,
R
2
,
R
3
,
⋯
,
R
j
{ R_1 , R_2 , R_3 , ⋯ , R_j }
R1,R2,R3,⋯ ,Rj产生后，就可以确定某一给定的测试数据所属的区域，并用这一区域训练集的各个样本取值的算术平均数作为与测试进行预测。
集成学习是将弱学习器组合成强学习器的方法，有两个好处，一是发现弱学习器比强学习器容易的多，二是组合学习器可以提升模型的泛化性能。
考虑二分类问题，假定分类器的错误率是
ϵ
epsilon
ϵ，真实函数是
f
f
f，对每个基分类器
h
i
h_i
hi有
P
(
h
i
(
x
)
≠
f
(
x
)
)
=
ϵ
P(h_i(x) neq f(x)) = epsilon
P(hi(x)=f(x))=ϵ
如果T个基分类器中超过半数投票正确，则认为集成分类正确，假设T个基分类器的错误率相互独立.则有Hoeffding不等式可知，集成分类器的错误率如下，公式中
k
k
k个表示基分类器正确的个数，
1
−
ϵ
1-epsilon
1−ϵ表示基分类器正确率。
P
(
H
(
x
)
≠
f
(
x
)
)
=
∑
k
=
0
[
T
/
2
]
(
T
k
)
(
1
−
ϵ
)
k
ϵ
T
−
k
≤
e
x
p
(
−
1
2
T
(
1
−
2
ϵ
)
2
)
P(H(x) neq f(x)) = sum_{k=0}^{[T/2]} {T choose k} (1-epsilon)^k epsilon^{T-k} \ leq exp(- frac{1}{2} T(1-2epsilon)^2)
P(H(x)=f(x))=k=0∑[T/2](kT)(1−ϵ)kϵT−k≤exp(−21T(1−2ϵ)2)
上式显示，随着分类器数目T的增大，集成错误率指数下降。
通常选取个体学习器的准则是：
- 个体学习器要有一定的准确性，预测能力不能太差。 个体学习器之间要
- 有多样性，即学习器之间要有差异。
**如何将弱分类器组合成强分类器
- 提高错分样本的权重；
- 错误率的基分类器权重高；**
AdaBoost 算法可以认为是：模型为加法模型、损失函数为指数函数
L
(
y
,
f
(
x
)
)
=
e
x
p
[
−
y
f
(
x
)
]
L(y,f(x))=exp[-yf(x)]
L(y,f(x))=exp[−yf(x)]、学习算法为前向分步算法的二类分类学习方法。
前向分步算法求解这一优化问题的思想是：因为学习的是加法模型，如果能够从前向后，每一步学习上一步的残差，逐步逼近优化目标函数，则可以简化优化的复杂度。
梯度提升树流程：])
为得到泛化性能强的集成模型，基学习器应该尽可能相互独立，独立无法在现实中做到，但可以设法让基学习器间尽可能有较大的差异。Bagging方法通过对样本有放回的抽样实现，采样出T个包含m个训练样本的数据集，并训练得到基学习器，再将这写学习器组合。T个基学习器对分类任务通常使用简单投票法，对回归任务使用平均法。
2.1.1 随机森林RF不仅通过样本扰动，还通过属性扰动（随机抽取特征），来实现基学习器的多样性。
2.3 Stacking 待补充 2.4 Boosting和Bagging比较- 样本选择上：
Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。
Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。 - 样例权重：
Bagging：使用均匀取样，每个样例的权重相等
Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。 - 预测函数：
Bagging：所有预测函数的权重相等。
Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。
从偏差-方差分解的角度来看： - 方差-偏差：
Bagging主要关注降低方差，它能平滑强学习器的方差。因此它在非剪枝决策树、神经网络等容易受到样本扰动的学习器上效果更为明显。
Boosting 主要关注降低偏差，它能将一些弱学习器提升为强学习器。因此它在SVM 、knn 等不容易受到样本扰动的学习器上效果更为明显。
树的深入讲解
集成学习
