朴素贝叶斯(分类)
- (C): Class, 类别
- (F): Feature，特征
- (P(C)): 先验概率
- (P(F|C))：似然值
- (sum_iF_i)：归一化用的，对所有类别都相同，可忽略
- 假设“所有特征彼此独立”，问题转化为：
egin{aligned}
P(C|F)proptoprod_iP(F_i|C)P(C)
end{aligned}
其中(P(F_i|C))和(P(C))可从统计资料中得到，由此可计算出每个类别对应的概率，从而找出最大概率的类。 - “所有特征彼此独立”是很强的假设，现实中不太可能成立，但是可以大大简化计算，且有研究表明对分类结果准确性影响不大。
决策树(分类)
算法核心
选择最优的划分特征。每次划分后的分支节点所包含的样本尽可能的属于同一类别，也就是节点中所包含的样本纯度越来越高。
如何评判纯度？
信息熵
信息量化
如何衡量(H(x))的大小
- 事件的信息量和事件发生的概率有关。(H(x)Leftrightarrow frac{1}{P(x)})
- 多个事件的信息总量是信息量的加和。(H(x_1,x_2)Leftrightarrow H(x_1)+H(x_2))
- (H(x)ge0)
需要构造一个关于(H(x))的函数满足上述关系：(H(x)=log frac{1}{P(x)}=-logP(x))
熵
熵求的是(H(x))在(P(x))分布下的数学期望，代表一个系统的不确定性，信息熵越大，不确定性越大。
egin{aligned}
Entropy(x) = E_x[H(x)]=-sum_xP(x)logP(x)
end{aligned}
- 全为一种元素，熵最小，(Entropy(x)=0)
- 系统内元素均匀分布，熵最大，(Entropy(x)=1)
- 想在系统内对元素划分，使得同一类元素在一起，每次划分就希望 minimize 系统的信息熵
信息增益
Information Gain(IG)
egin{aligned}
IG=OriginalEntropy - sum_i frac{A_i}{|A|}Entropy(A_i)
end{aligned}
信息熵是系统的不确定度，信息增益代表划分后系统的不确定度减少的程度。
每次划分希望信息增益越大越好。
ID3算法
采用 Information Gain 作为纯度的度量，算每一个特征的信息增益，选择使得信息增益最大的特征进行划分。
决策树划分
特征类型：
- ordinal 离散而有序
- numerical (discrete nominal) 离散而无序
- continuous 连续
贝叶斯分类模型适用离散无序类型(discrete)的特征
划分方法：
- 多路划分
- 独立值
- 二分法
- 组合
Discretization 连续数据离散化：
- 有序离散化
- 静态划分 一开始就离散化
- 动态划分 均匀间隔、均匀频次、聚类
- 二分法
- 类似IG3算法划分，找IG最大的划分
- 计算更密集
Gini Index
除了熵，还有其他方式来指导决策树划分。
egin{aligned}
GINI(t)=1-sum_jP(j|t)^2
end{aligned}
(P(j|t))：每个状态(t)里每个class(j)的频率
- 若均匀分布(对应熵 = 1的情况)，GINI Index = 0.5 最大
- 若某一类元素占比为1 (对应熵 = 0的情况)，GINI Index = 0 最小
比较容易算，不用计算log。
Gini Split
划分(k)个分区，计算各个分区的加权 GINI 指数
对应信息增益
egin{aligned}
GINI_{split}=sum_{i=1}^kfrac{n_i}{n}GINI(i)
end{aligned}
- (n_i)：当前分区内元素个数
- (n): 系统内总的元素个数
GINI划分越小越好
Misclassification Error
错分率
egin{aligned}
Error(t)=1-max_iP(i|t)
end{aligned}
- (P(i|t))：每个状态(t)里每个class(i)的频率
- 若某一类元素占比为1 (对应熵 = 0，GINI Index = 0的情况)，Error = 0 最小
- 若均匀分布(对应熵 = 1，GINI Index = 0.5的情况)，Error = 0.5 最大
Traning and Test Errors
训练决策树时什么时候该停止，停止过早，没有很好学习数据性能，停止过晚，过拟合现象。
Tree Ensemble 集成学习
numbers of nodes： complexity of model
CART回归树(预测)
决策树做预测和做分类有相同的地方，都是将数据分成很多块，如果是做预测，将数据在某维度 (x^i) 分成几块，取块中 (y) 值的均值或加权均值作为这块区域数据的估计值；如果是分类，估计的值是 {0,1}
给定训练数据 (D={(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),...,(x^{(N)},y^{(N)})})，希望学习一个CART树来最小化损失函数
- (x^i) 是高维向量，(y^i) 是连续变量
- 如果 (y^i) 是离散的 ({0,1})，那是分类问题
- 如果 (y^i) 是连续的，就是回归预测问题
- (Loss) : 每一个区间的均值和真实数据 (y) 之间的距离
- (R_m)：被划分的输入区间
- (C_m)：区间(R_m)对应的输出值，区域的均值
- (j)：第几个特征维度
- (s): 分割点，cut point
- (L): (y) 和 (C) 之间的距离，计算距离一般常用(L_2)欧式距离
- 具体计算公式：$$Loss = min_{j,s}[min_{C_1}sum_{x in R_1(j,s)} (y{(i)}-C_1)2+min_{C_2} sum_{x in R_2(j,s)} (y{(i)}-C_2)2]wherequad R_1(j,s)={x|x_j le s},quad R_2(j,s)={x|x_j > s}\quad quad quad quad C_m=frac{1}{N_m}sum_{xin R_m(j,s)}y^{(i)},m={1,2}$$
- 遍历特征变量(j)，在每一个特征变量上选择合适分割点，使得距离相加和最小，最后选择最好的结果对应的(j)和(s)
- CART树一般就分2块区域，(R_1)和(R_2)，因为是递归分割的
集成学习
Bagging (Bootstrap Aggregating，引导聚集算法，装袋算法)
Bootstrap 是统计学里一种采样方法。自身有放回式采样。给定大小为(n)的训练集(D)，从中均匀、有放回地选出(m)个大小为(n')的子集(D_i)作为新的训练集。在这(m)个训练集上使用分类、回归等算法，则得到(m)个模型，再通过取平均值、取多数票等方法，即可得到 Bagging 结果。
- 采好后每一个定形处理
- 很好做并行，每一个采样都可以放到不同机器上处理
- Bagging 算法可与其他分类、回归算法结合，提高准确率、稳定性的同时，通过降低结果的方差，避免过拟合的发生。
- Random Forest：对CART树使用 Bagging 算法，生成的许多树组成随机森林。
Boosting(增强算法)：给采样增加权重
AdaBoost (Adapting Boosting，自适应的boosting算法)
给出训练数据(D={(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),...,(x^{(N)},y^{(N)})})，(x^{(i)}in R^n)，(y in left{ +1,-1 ight})。对每一个(x^{(i)})，有一个相应的权重(w^{(i)} in R)(标量)
1. 初始化
-
初始化时每一个数据 (x^{(i)}) 的权重相等
-
机器学习第一步基本上都是初始化
2. for (k=1,2,...,K)迭代( Boosting 和 Bagging 不一样的地方。Boosting 每采样一次就要学习出一个弱分类器，每一次学习出的结果会对数据权重产生影响，必须顺序处理)
a. 计算第 (k) 个弱分类器的错分率
- (I(condition))：Indicator 指示函数，逻辑变量，括号内等式成立等于1，不成立等于0。这里表示被分类错误的样本数量。
- (G_k(x))是一个弱分类器(朴素贝叶斯、决策树)
- (e_k)：第 (k) 个分类器的误差
b. 计算第 (k) 个弱分类器的权重
- 如果一个分类器的误差比较大， 不希望该分类器的权重较大、
- 分类器的权重决定最后结果中这个分类器的话语权有多重
- 集成分类是各个分类器结果累加的形式
c. 更新训练数据权重 (w_k)
-
(exp(f(x)))：表示 (e) 的 (f(x)) 次方
[ifquad y^{(i)}=G_k(x^{(i)}),则y^{(i)}G_k(x^{(i)})=1\exp(-alpha_ky^{(i)}G_k(x^{(i)})=exp(-alpha_k)=frac{1}{e^{alpha_k}} quad uparrow ][ifquad y^{(i)} e G_k(x^{(i)}),则y^{(i)}G_k(x^{(i)})=-1\exp(-alpha_ky^{(i)}G_k(x^{(i)})=exp(alpha_k)=e^{alpha_k} quad downarrow ] -
分错的数据赋予更大权重，更好的学习
-
({z_k})：归一化系数，使得(w_k^{(i)})加和为1。
[{z_k}=sum_{i=1}^N w_k^{(i)}exp(-alpha_kG_k(x^{(i)}) ]
3.得到结果
- 对所有 (k) 个分类器赋予权重，计算得最后的强分类器
- sign()函数，大于0输出1，小于0输出-1
Boosting需要逐个训练弱分类器，1）数据权重初始化 。2）根据每一个弱分类器的误差来计算弱分类器的权重，并更新数据的权重，分错了权重增加，分对了权重减少。3）将要分类的数据输入到每一个弱分类器，由每一个弱分类器的加权结果得出最终结果。
Gradient Boosting( 梯度的boosting算法)
boosting的思想：分类器对分对了的保留，分错了的在下一个分类器加强学习。每次都在调整残差 (实际值与拟合值之间的差)。
Gradient Boosting： 每一次建立分类器都是在减少上一轮分类器产生的残差，每一次建立模型是在之前建立模型损失函数的梯度下降方向.
a. 模型要求
给定训练数据 (D={(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),...,(x^{(N)},y^{(N)})})，我们要让残差适应之前的弱分类器
-
上一轮训练中有误差(h(x))
-
我们的目标是学习一个(h(x^{(i)}))，让(h(x^{(i)}))尽量小， 使得这一轮的分类结果尽可能与真实结果 (y^{(i)}) 逼近：
b. 训练目的
目的是通过优化 (loss function)，找到一个对于$ F(x) $ 的逼近函数 $ widehat F(x) $
-
(argmin): 求最优化的写法，使后面的式子达到最小值时的变量的取值
-
(F(x)) 是对以往的 (h(x)) 的一个加权和
[F(x)=sum_{i=1}^M alpha_ih_i(x) ] -
(F_0(x))：以CART树举例，来说就是初始情况，没有学习任何分类器，学习一个常数 (C) 即可，大概在均值的地方
[F_0(x)=argmin_Csum_{i=1}^NL(y^{(i)},C) ] -
有了(F_0(x))，下一个分类器就是上一个分类器加上误差函数，再加上调整误差的函数 (h(x))
[F_m(x)=F_{m-1}(x)+argminsum_{i=1}^N[L(y^{(i)},F_{m-1}(x^{(i)})+h_m(x^{(i)})) ]
c. 学习残差
- 损失函数对于 (F(x)) 求导，负导数就是改进梯度方向
- 类比变量空间的梯度下降求极值方法，只不过自变量 (x) 对应函数 (F(x)) ，因变量 (f(x)) 对应损失函数 (L(y,F(x)))
d. （例）GDBT拟合残差
如何求损失函数 (L(y,F(x)))对函数 (F(x)) 的导数，针对决策树模型，可以学习一个CART树来拟合残差。
- 就好像根据训练数据 (D={(x^{(1)},r_m^{(1)}),(x^{(2)},r_m^{(2)}),...,(x^{(N)},r_m^{(N)})}) ，学习CART树：
-
新的分类器变为：
[F_m(x)=F_{m-1}(x)+sum_{j=1}^JC_{m,j}I(xin R(m,j)) ][Rightarrow F_m(x)=sum_{m=1}^Msum_{j=1}^JC_{m,j}I(xin R(m,j)) ]
e. （补）Shrinkage 收缩
增加学习速率 ( heta( heta>0))
一般地，( heta in [0.001,0.01]) 来减慢拟合速度，更好地逼近结果。
决策树与GDBT对比
决策树分类
GDBT分类
- 先用一个弱分类器分类
- 根据残差，对残差再用一个弱分类器分类。例子中残差为0
- 最终分类结果=第一次弱分类器的结果+第二次残差分类器的结果
