Machine Learning Algorithms

This is my personal notes for Machine Learning Algorithms.

Introduction

本文介绍经典的机器学习算法，包括Decision Tree, 随机森林, GBDT, XGBoost

Decision Tree

• 生成原理:

  如果当前的label还没有分出来, 遍历所有可分的label， 分别计算加上每个label之后的Info Gain = 加之前的信息熵(H) - 加之后的信息熵(H), 每次分裂用Info Gain最大的那个选项, 即信息熵下降最多

  如果当前的path已经对应了确定的label, 那么停止分裂

  H = sum(-p(d)*log2p(d)), 其中d是对于每个category对应的decision的比例分布

  比如sunny下有4个decision, 分别是1，1，2， 那么H(Decision | sunny) = -1/4log2(1/4) - 1/4log2(1/4) - 2/4*log2(2/4) = 1.5

• 如何防止过拟合

  剪枝：

  • a 先剪枝 - 提前停止树的增长 (限制决策树的高度和叶子结点处样本的数目)

    • 1 定义一个高度，当决策树达到该高度时就可以停止决策树的生长，这是一种最为简单的方法；

    • 2 达到某个结点的实例具有相同的特征向量，即使这些实例不属于同一类，也可以停止决策树的生长。这种方法对于处理数据中的数据冲突问题非常有效；

    • 3 定义一个阈值，当达到某个结点的实例个数小于该阈值时就可以停止决策树的生长；

    • 4 定义一个阈值，通过计算每次扩张对系统性能的增益，并比较增益值与该阈值的大小来决定是否停止决策树的生长。

  • b 后剪枝 - 对已经生成的树按照一定的规则进行剪枝

    它首先构造完整的决策树，允许树过度拟合训练数据，然后对那些置信度不够的结点子树用叶子结点来代替，该叶子的类标号用该结点子树中最频繁的类标记。后剪枝的剪枝过程是删除一些子树，然后用其叶子节点代替，这个叶子节点所标识的类别通过大多数原则(majority class criterion)确定。所谓大多数原则，是指剪枝过程中, 将一些子树删除而用叶节点代替,这个叶节点所标识的类别用这棵子树中大多数训练样本所属的类别来标识,所标识的类称为majority class .相比于先剪枝，这种方法更常用，正是因为在先剪枝方法中精确地估计何时停止树增长很困难。

• 决策树的分类

  • ID3：以信息增益为准则来选择最优划分属性

  • C4.5：基于信息增益率准则选择最优分割属性的算法

  • CART：以基尼系数为准则选择最优划分属性，可以应用于分类和回归

• 分类树和回归树

  提到决策树算法，容易想到上面提到的ID3、C4.5、CART分类决策树。其实决策树分为分类树和回归树，前者用于分类，如晴天/阴天/雨天、用户性别、邮件是否是垃圾邮件，后者用于预测实数值，如明天的温度、用户的年龄等。

  分类树: 我们知道ID3、C4.5分类树在每次分枝时，是穷举每一个特征属性的每一个阈值，找到使得按照feature<=阈值，和feature>阈值分成的两个分枝的信息增益最大的feature和阈值。按照该标准分枝得到两个新节点，用同样方法继续分枝直到所有人都被分入性别唯一的叶子节点，或达到预设的终止条件，若最终叶子节点中的性别不唯一，则以多数人的性别作为该叶子节点的性别。

  回归树: 总体流程类似，不过在每个节点（不一定是叶子节点）都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化均方差–即（每个人的年龄-预测年龄）^2 的总和 / N，或者说是每个人的预测误差平方和 除以 N。这很好理解，被预测出错的人数越多，错的越离谱，均方差就越大，通过最小化均方差能够找到最靠谱的分枝依据。分枝直到每个叶子节点上人的年龄都唯一（这太难了）或者达到预设的终止条件（如叶子个数上限），若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。

Random Forest

Random Forest是经典的的bagging算法(减少variance)，由多棵决策树(Cart)并行组成，每颗决策树既可以是分类树也可以是回归树。

• 生成过程:
  • (1) 每颗决策树用有放回抽样的方法从原始样本(m个)中抽取m个样本–所以每个决策树使用的样本基本都有重复
  • (2) 每颗决策树从m个总特征中随机抽取k个，用决策树的方法每次选择最优的特征进行分裂
  • (3) 循环生成若干个决策树，每次预测时每个决策树给出一个结果，所有决策树投票产生预测结果

Sample:

RF=RandomForestRegressor(n_estimators=10,max_features=4,min_samples_split=30)
RF.fit(train_x,train_y)
Prediction3=RF.predict(test_x)
Prediction3=np.expm1(Prediction3)
print(r2_score(test_y,Prediction3))

• 参数说明
  • n_estimators: 决策树数量
  • max_features: 每棵决策树抽取的feature数量上限
  • min_samples_split: 内部节点再划分所需最小样本数，如果某节点样本量小于这个数，不再分裂
• 模型优点:
  • (1) 实现简单，训练速度快，可以并行实现，因为训练时树与树之间是相互独立的；
  • (2) 相比单一决策树，能学习到特征之间的相互影响，且不容易过拟合；
  • (3) 能处理高维数据（即特征很多），并且不用做特征选择，因为特征子集是随机选取的；
  • (4) 对于不平衡的数据集，可以平衡误差，对异常值不敏感；
  • (5) 训练完成后可以给出哪些特征比较重要。

GBDT

GBDT是经典的的boosting算法(减少bias)，由多棵决策树(Cart)串行组成，决策树只能是回归树。

GBDT的核心就在于：每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。

• 生成过程:
  • (1) 算法每次迭代生成一颗新的决策树;
  • (2) 在每次迭代开始之前，计算损失函数在每个训练样本点的一阶导数和二阶导数;
  • (3) 通过贪心策略生成新的决策树，并计算每个叶节点对应的预测值;
  • (4) 把新生成的决策树添加到模型中，通常这个时候会加入一个步长(学习率)。

Sample:

GBDT=GradientBoostingRegressor(n_estimators=30,learning_rate=0.1,loss='ls',subsample=1.0)
GBDT.fit(train_x,train_y)
Prediction1=GBDT.predict(test_x)
Prediction1=np.expm1(Prediction1)
print(r2_score(test_y,Prediction1))

• 参数说明
  • n_estimators: 串行树的个数，即迭代次数，树越多，准确率变高，但效率变差
  • learning_rate: GBDT在每增加一颗新树进来的时候，系统并不完全相信这颗树的拟合程度，而是只采纳了其中一部分(学习率), 步长(学习率)越长，准确率越高，但泛化能力越弱
  • loss: 损失函数，ls为均方差，回归时用，用来做分类是loss改为对数似然函数
  • subsample: 采样比例，选择一定比例的样本放入GBDT进行拟合(无放回)

和RF不同的是，GBDT从第二颗树开始，导入的就是残差，而不是样本，这就带来了一个问题。RF模型因为是导入样本，因此它可以轻松的建立最优的树结构，而GBDT导入的是残差，因此建立最优树结构比RF难多了。为解决这个问题，梯度下降出现了。大神Freidman提出了用损失函数的负梯度来拟合本轮损失的近似值，进而拟合一个CART回归树。之前提到的问题迎刃而解了。GBDT算法推导

• 模型优点:
  • 适用面广，离散或连续的数据都可以处理，几乎可用于所有回归问题（线性/非线性），亦可用于二分类问题。
• 模型缺点:
  • 由于弱分类器的串行依赖，难以并行训练数据。但预测时是并行的，预测结果是所有树的预测值之和。

• Random Forest 和 GBDT 的对比

  • 随机森林采用的bagging思想，而GBDT采用的boosting思想。这两种方法都是Bootstrap思想的应用，Bootstrap是一种有放回的抽样方法思想。虽然都是有放回的抽样，但二者的区别在于：Bagging采用有放回的均匀取样，而Boosting根据错误率来取样（Boosting初始化时对每一个训练样例赋相等的权重1／n，然后用该算法对训练集训练t轮，每次训练后，对训练失败的样例赋以较大的权重），因此Boosting的分类精度要优于Bagging。Bagging的训练集的选择是随机的，各训练集之间相互独立，弱分类器可并行，而Boosting的训练集的选择与前一轮的学习结果有关，是串行的。
  • 组成随机森林的树可以是分类树，也可以是回归树；而GBDT只能由回归树组成。
  • 组成随机森林的树可以并行生成；而GBDT只能是串行生成。
  • 对于最终的输出结果而言，随机森林采用多数投票等；而GBDT则是将所有结果累加起来，或者加权累加起来。
  • 随机森林对异常值不敏感；GBDT对异常值非常敏感。
  • 随机森林对训练集一视同仁；GBDT是基于权值的弱分类器的集成。
  • 随机森林是通过减少模型方差(variance)提高性能；GBDT是通过减少模型偏差(bias)提高性能。

XGBoost

首先xgboost是Gradient Boosting的一种高效系统实现，并不是一种单一算法。xgboost里面的基学习器除了用tree(gbtree)，也可用线性分类器(gblinear)。而GBDT则特指梯度提升决策树算法。XGBoost在寻找splitpoint的时候，不会枚举所有的特征值，而会对特征值进行聚合统计，按照特征值的密度分布，构造直方图计算特征值分布的面积，然后划分分布形成若干个bucket(桶)，每个bucket的面积相同，将bucket边界上的特征值作为splitpoint的候选，遍历所有的候选分裂点来找到最佳分裂点。

• 1 传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。

• 2 传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。

• 3 XGBoost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。 Shr

• 4 Shrinkage（缩减），相当于学习速率（xgboost中的eta）。每次迭代，增加新的模型，在前面成上一个小于1的系数，降低优化的速度，每次走一小步逐步逼近最优模型比每次走一大步逼近更加容易避免过拟合现象；

• 5 列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样（即每次的输入特征不是全部特征），不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。

• 6 忽略缺失值：在寻找splitpoint的时候，不会对该特征为missing的样本进行遍历统计，只对该列特征值为non-missing的样本上对应的特征值进行遍历，通过这个工程技巧来减少了为稀疏离散特征寻找splitpoint的时间开销

• 7 指定缺失值的分隔方向：可以为缺失值或者指定的值指定分支的默认方向，为了保证完备性，会分别处理将missing该特征值的样本分配到左叶子结点和右叶子结点的两种情形，分到那个子节点带来的增益大，默认的方向就是哪个子节点，这能大大提升算法的效率。

• 8 并行化处理：在训练之前，预先对每个特征内部进行了排序找出候选切割点，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行，即在不同的特征属性上采用多线程并行方式寻找最佳分割点。