特征工程

标准化和归一化

数据的标准化是将数据按比例缩放，使之落入一个小的特定的区间，从而去除数据的单位限制，将其转换为无量纲的纯数值，便于不同单位或量级的指标能够进行比较和加权。
归一化：将数据映射到[0,1]区间。因此归一化是标准化的一种特例。

min-max标准化/0-1标准化

机器学习 - 图1

z-score标准化

机器学习 - 图2
相比于min-max标准化，z-score标准化适用于有超出取值范围的离群数据的情况。
z-score要求原始数据的分布近似高斯分布，否则效果会变得很糟糕。

优点

  1. 提升模型的收敛速度

归一化之前的在狭长的空间梯度下降呈之字形路径，特别是在短的方向上收敛慢
归一化后的圆形区域可以更快更稳定地进行梯度下降

  1. 提升模型的精度

涉及到距离计算的算法时效果更显著

适用场景

一般进行梯度下降求解的都需要归一化
使用距离计算的模型中也需要归一化，比如KNN，SVM
树模型一般不用归一化。因为树模型是通过分裂最优属性寻找最优点的，因此树模型是阶跃的，阶跃是不可导的，求导也没有意义，所以树模型不需要归一化。

数据样本不平衡问题

一个准确率高达90%以上的模型在真实数据上可能完全无法使用，一个可能的原因是：训练数据样本不平衡。

混淆矩阵、精度、召回率、F1

屏幕快照 2020-06-24 下午3.44.45.png
机器学习 - 图4
机器学习 - 图5
机器学习 - 图6
机器学习 - 图7

ROC曲线

假设对于给定点 x，我们的模型输出该点属于类别 C 的概率为：P(C | x)。基于这个概率，我们定义一个决策规则，即当且仅当 P(C | x) ≥ T 时，x 属于类别 C，其中 T 是定义决策规则的给定阈值。如果 T = 1，则仅当模型 100％可信时，才将该点标注为类别 C。如果 T = 0，则每个点都标注为类别 C。
阈值 T 从 0 到 1 之间的每个值都会生成一个点 (false positive, true positive)，ROC 曲线就是当 T 从 1 变化到 0 所产生点的集合所描述的曲线。该曲线从点 (0,0) 开始，在点 (1,1) 处结束，且单调增加。好模型的 ROC 曲线会快速从 0 增加到 1（这意味着必须牺牲一点精度才能获得高召回率）。
AUC是 ROC 曲线下面积。可以看出，AUC在最佳情况下将趋近于 1.0，而在最坏情况下降趋向于 0.5。

解决数据不平衡的方法

  1. 下采样：随机删除观测量足够多的类（被删除的数据中可能包含预测的重要信息）
  2. 过采样：复制少数类中的一些点（可能会导致过拟合）

  3. 合成采样(SMOTE)：从少数类中创建新的合成点，以增加其基数

    PCA

    主成分分析即PCA，可以将数据从原来的坐标转换到新的坐标系，新坐标系的选择由数据本身决定的，第一个新坐标系的选择是原始数据中方差最大的方向（第一主成分），数据的最大方差给出了最重要的信息，第二个坐标系的选择和第一个坐标系正交且具有最大方差的方向。
    具体的步骤包括：

  4. 去平均值

  5. 计算协方差矩阵
  6. 计算协方差矩阵的特征值和特征向量
  7. 将特征值从大到小排序
  8. 保留最上面的N个特征向量
  9. 将数据转换到这N个特征向量构建的空间中

    正则化

    正则化是通过修正损失函数，加入模型复杂度评估，从而防止过拟合的一种方法。

    L1正则化

    损失函数+向量中各元素绝对值之和。有叫做稀疏规则算子，L1趋于产生少量的特征，而其他特征都是0，能够实现特征选择，参数稀疏性可以避免非必要的特征引入的噪声。

    L2正则化

    损失函数+向量中各元素的平方和。L2会使得每个参数都尽可能小，但都不为0。L2也叫岭回归或者权重衰减。

    Logistic Regression

    定义

    logistc regression假设数据服从伯努利分布，通过极大似然估计，运用梯度下降来求解参数，达到将数据而二分类的目的。
    logistic regression的模型可以表示为：
    屏幕快照 2020-06-20 下午10.05.30.png

    似然函数和损失函数

    用极大似然估计表示：
    屏幕快照 2020-06-20 下午10.13.57.png
    取负对数构造损失函数：
    屏幕快照 2020-06-20 下午10.15.06.png

    梯度下降

    由于该极大似然函数无法直接求解，需要对该函数进行梯度下降来不断逼急最优解。
    求导：

屏幕快照 2020-06-20 下午10.18.07.png
参数更新：
屏幕快照 2020-06-20 下午10.19.31.png

决策树

定义

决策树就是用一棵树表示整个决策过程，其中根节点包含整个样本集，每个叶子结点对一个决策结果，从根节点到叶节点的路径对应一条测试判定序列。
决策树的生成是一个递归的过程，停止的条件有：

  1. 当前节点包含的样本数据同一类别，无需划分

  2. 当前节点对应的属性集为空，已无可用的划分属性 机器学习 - 图13

    特征选择

    信息增益

    信息增益=划分前熵-划分后熵
    数据集D中的熵：
    屏幕快照 2020-06-22 下午4.09.48.png
    熵表示数据包含的信息量的大小。熵越小，数据的纯度越高，数据越趋于一致，这是我们希望划分之后每个节点的样子。
    用属性A划分数据集D为v个子集后的熵：
    屏幕快照 2020-06-22 下午4.10.35.png
    信息增益：
    屏幕快照 2020-06-22 下午4.11.09.png
    信息增益越大，意味着通过属性A来划分所获得的“纯度提升”越大，也就是说使用A划分数据集，得到的结果中纯度比较高。

    信息增益比

    由于信息增益总是倾向于选择取值较多的属性，信息增益比在此基础上增加了一个罚项：
    屏幕快照 2020-06-22 下午4.12.03.png
    where：
    屏幕快照 2020-06-22 下午4.12.41.png

    Gini指数

    Gini指数和熵都可以表示数据的不确定性、不纯度，但Gini指数的计算不需要运用对数运算，效率更高。
    假设数据集D包含了n类样本，数据集D的Gini指数可以表示为：
    屏幕快照 2020-06-22 下午4.13.33.png
    如果数据集D通过属性A划分为两个数据集D1和D2，此时的Gini指数可以表示为：
    屏幕快照 2020-06-22 下午4.16.10.png
    Gini指数越大，集合的不确定性越高，不纯度也越大，因此需要选择Gini指数最小的特征进行划分。

    树的生成

    ID3

    ID3使用信息增益作为特征选择的准则，ID3仅仅能够处理离散数据。

    C4.5

    对于分类问题：C4.5使用信息增益比作为特征选择的准则，解决了信息增益偏向选择取值较多特征的问题。
    对于回归问题：C4.5将连续特征的特征值排序，以连续两个值的中间值作为划分标准，尝试每一种划分，选择信息增益比最大的分裂点作为该属性的分裂点。

    CART

    CART与ID3和C4.5不同的是，CART必须是二叉树，无论是分类问题还是回归问题，无论特征是离散的还是连续的，内部节点都只能根据属性值进行二分。
    对于分类问题：CART使用Gini指数最小化的准则来选择特征并划分。
    对于回归问题：CART使用平方误差最小化的准则来选择特征并划分，所以又叫最小二乘回归树。每个叶子结点给出的预测值，是划分到该叶子结点的所有样本目标值的均值。要确定最优划分，需要遍历所有特征，以及遍历其所有的取值来尝试划分，并计算在这种划分下的平方误差，选择最小的情况作为划分依据。

    树的剪枝

    决策树算法很容易过拟合，剪枝是用来降低过拟合风险、提高泛化能力的方法。

    预剪枝

    预剪枝是只在决策树的生成过程中，对每个节点在划分前进行评估，如果当前的划分不能够带来泛化能力的提升，则停止划分，并将当前节点标记为叶子结点。

    后剪枝

    后剪枝是指先从训练集中生成一棵完整的决策树，然后自底向上对非叶节点进行考察，若将该节点对应的子树替换为叶节点能够带来泛化性能的提升，则将该子树替换为叶节点。

    集成学习

    概念

    集成学习通过构建并组合多个学习器来完成学习任务，通常获得比单一学习器更优越的泛化性能。
    分类：

  3. Bagging：个体学习器之间不存在强依赖关系，可以同时生产的并行化方法

  4. Boosting：个体学习器之间存在强依赖关系，必须串行生成的序列化方法

    Bagging

    原理

  5. 通过有放回的随机采样生成子训练集

基学习器之间的多样性和独立性可以提升集成学习的泛化能力。
Bagging对训练集进行有放回的随机采样，生成若干个不同的子集，再从每个子集中训练一个基学习器。由于训练数据不同，我们期望基学习器之间有较大的差异。

  1. 并行训练基学习器
  2. 集成所有集学习器的结果：

分类：简单投票法
回归：简单平均法
屏幕快照 2020-06-23 上午10.00.24.png

随机森林原理

随机森林是Bagging的一个变体，在Bagging的基础上，引入了随机属性选择。即在每棵树的每个节点分裂前，先从该节点的属性集中随机选择K个属性构成属性子集，然后从这个属性子集中选择最优的属性进行划分。

随机森林优缺点

优点：

  1. 由于每次不需要考虑全部的属性，而是一个属性子集，因此相比于Bagging计算开销更小，训练效率更高。
  2. 增加了属性的扰动，随机森林基学习器性能降低，使得随机森林在初始阶段性能较差，但随着基学习器数量的增多，随机森林通常会收敛于一个更低的泛化误差。
  3. 对数据的适应能力强，可以处理连续型和离散型的数据。

缺点：
在噪声较大的时候容易更拟合。

Boosting

原理

  1. 先从初始训练集中学习一个基学习器
  2. 根据基学习器的表现调整训练样本的分布，增加分类错误的样本的权重，降低分类正确的样本的权重，使得分类错误的样本在后续得到更多的关注。

  3. 如此反复，直到基学习器的数量达到T，最终将这T个基学习器进行加权结合。

    Adaboost优缺点

    优点：

  4. 不改变训练数据，只改变训练数据的权值分布，使得训练数据在基学习器的学习中起到不同的作用。

  5. 利用基学习器的加权线性组合构建最终的分类器。
  6. 能够很好地防止过拟合。

缺点：
只能用于二分类问题

梯度提升决策树

GBDT

模型介绍

GBDT通过采用加法模型，不断减小训练过程产生的残差来达到将数据分类或回归的目的。
残差本质上就是平方损失函数下的负梯度。

训练过程

通过多轮迭代，每次迭代产生一个弱分类器，每个分类器学习的之前所有树结论和的残差。对于弱分类器的要求一般是足够简单，并且是低方差高偏差，训练过程中通过不断降低偏差来不断提高分类器的精度。
gbdt的迭代公式为：
屏幕快照 2020-06-21 下午9.43.20.png
gbdt的核心是沿着损失函数梯度的方向下降，利用损失函数的负梯度作为残差去拟合提升树的回归值：
屏幕快照 2020-06-21 下午9.44.14.png

特征选择

在特征选择时，首先遍历每个特征，然后对每个特征选择它所有可能的切分点，找到最优特征和最优切分点，使用最有特征和最优切分点划分的数据集，每条数据到均值的平方误差的和最小：

  1. def findLossAndSplit(x,y):
  2.     # 我们用 x 来表示训练数据
  3.     # 我们用 y 来表示训练数据的label
  4.     # x[i]表示训练数据的第i个特征
  5.     # x_i 表示第i个训练样本
  7.     # minLoss 表示最小的损失
  8.     minLoss = Integet.max_value
  9.     # feature 表示是训练的数据第几纬度的特征
  10.     feature = 0
  11.     # split 表示切分点的个数
  12.     split = 0
  14.     # M 表示 样本x的特征个数
  15.     for j in range(0,M):
  16.         # 该维特征下，特征值的每个切分点，这里具体的切分方式可以自己定义
  17.         for c in range(0,x[j]):
  18.             L = 0
  19.             # 第一类
  20.             R1 = {x|x[j] <= c}
  21.             # 第二类
  22.             R2 = {x|x[j] > c}
  23.             # 属于第一类样本的y值的平均值
  24.             y1 = ave{y|x 属于 R1}
  25.             # 属于第二类样本的y值的平均值
  26.             y2 = ave{y| x 属于 R2}
  27.             # 遍历所有的样本，找到 loss funtion 的值
  28.             for x_1 in all x
  29.                 if x_1 属于 R1：
  30.                     L += (y_1 - y1)^2
  31.                 else:
  32.                     L += (y_1 - y2)^2
  33.             if L < minLoss:
  34.                minLoss = L
  35.                feature  = i
  36.                split = c
  37.     return minLoss,feature ,split

特征组合

GBDT是一种非线性模型，其思想使其可以发现多种有区分性的特征以及特征组合，决策树的路径可以直接作为LR输入特征使用，提升模型最终的结果。
屏幕快照 2020-06-21 上午11.24.49.png

用于分类问题

GBDT中的树全部都是回归树，核心是累加所有树的结果作为最终结果。只有回归树的结果累加是有意义的，分类结果的累加是没有意义的。
GBDT用于分类问题时，需要对每个类别分别训练M个分类器。假设有K个类别，那么训练完之后会有M*K棵树。最后K棵树的结果经过softmax获得分类概率。

优缺点

优点：

  1. 可以灵活处理各种数据，离散值和连续值
  2. 泛化性能更好，每一步的残差计算其实变相增大了分错样本的权重，而已分对样本的权重趋近于0，这样后面会更专注于分错的样本。
  3. 对异常值的鲁棒性非常强

缺点：
由于弱分类器之间存在依赖关系，难以并行训练

GBDT和随机森林对比

相同点：

  1. 都是由多棵树构成
  2. 最终的结果由多棵树共同决定

不同点：

  1. 组成随机森林的既可以是分类树也可以是回归树；组成GBDT只能是回归树
  2. 组成随机森林的树可以并行生成(Bagging)，组成GBDT的树只能串行生成(Boosting)
  3. 对于最终的结果，随机森林采用多数投票或者简单平均；GBDT则是将所有的结果累加起来

  4. 随机森林通过减小模型的方差提高模型性能，GBDT通过减小模型的偏差提高模型性能

    XGBoost和GBDT的区别

  5. 损失函数的二阶泰勒展开

传统GBDT只用到了一阶导数信息，XGBoost对损失函数进行了二阶泰勒展开，同时用到了一阶和二阶导数

  1. 正则项

XGBoost在损失函数中增加了正则项来控制模型的复杂度。惩罚项包含叶子结点的个数（T）、叶节点分数（w）的L2正则项：
屏幕快照 2020-06-21 下午9.45.33.png

  1. 缩减系数

在迭代时引入缩减系数，每走一小步来逼近结果要比走一大步很快逼近结果的方式更容易防止过拟合：
屏幕快照 2020-06-21 下午9.44.56.png
认为每棵树只学习到了真理的一小部分，累加的时候也只累加一小部分，通过多学习几棵树来弥补不足。

  1. 缺失值处理

对于特征值有缺失的样本，XGBoost可以自动学习它的分裂方向。

  1. 列抽样

XGBoost和Random Forest一样，在每棵树的每个分裂节点分裂前，先从该节点的属性集中随机选取k个属性的子集，然后从这个属性子集中选择最优属性进行划分。

  1. 支持并行

XGBoost遍历一次数据可以同时分裂同一层的叶子。XGBoost将数据每列按特征值排序存储在内存单元（Block）中，在进行节点分裂时，需要计算每个特征值的增益，最终选择增益最大的特征进行分裂，各个特征的增益可以多进程并行。

LightGBM

直方图算法

把浮点特征值离散化成k个整数，构造一个宽度为k的直方图，其中离散后的数值是直方图的索引。在遍历一次数据时，在直方图中累计统计量。最后根据直方图的离散值和累计的统计量，寻找最优分割点。
直方图算法优点：

  1. 占用更少内存

直方图算法不需要额外存储预排序的结果，可以只保留特征离散化后的值，内存消耗降为原来的1/8。

  1. 计算时间复杂度降低

XGBoost每遍历一个特征值就需要计算一次信息增益，LightGBM只需要计算k次，时间复杂度从O(datafeature)降低到O(kfeature)，data>>k

  1. 直方图做差加速

在二叉树中，一个叶节点的直方图可以通过其父节点的直方图和兄弟节点的直方图做差得到。

带有深度限制的Leaf-wise算法

XGBoost采用的Level-wise生长策略，不加区别地对待同一层的叶子，但实际上很多叶子的分裂增益很低，没有必要进行搜索和分裂，因此带来了很多不必要的开销。
屏幕快照 2020-06-22 上午10.11.16.png
LightGBM采用Leaf-wise的生长策略，每次从当前所有的叶子结点中，找到信息增益最大的叶子结点进行分裂。与Level-wise相比，Leaf-wise在相同的分裂次数下，可以降低更多的误差。此外，LightGBM在Leaf-wise增加了最大深度的限制，在保证高精确率的同时防止过拟合。
屏幕快照 2020-06-22 上午10.15.10.png

单边梯度采样算法

单边梯度采样算法（GOSS）从减少样本的角度出发，排除大部分小梯度的样本，用剩余的样本计算信息增益，它是一种在减少数据量和保证精度上平衡的算法。
GOSS目的是丢弃对信息增益没有帮助的样本，留下有帮助的。梯度大的样本对信息增益有更大的影响，因此GOSS在数据采样的时候只保留了梯度较大的数据。
为了尽量不影响数据的分布，GOSS首先将要分裂的特征的所有取值按照绝对值大小降序排序，选取绝对值最大的a100%个数据，在剩下的梯度较小的数据中随机选择b100%个数据，将这b*100%个数据乘以一个常数(1-a)/b，这样算法就会更多地关注训练不足的样本，而不会过多改变原数据集的分布。

互斥特征捆绑算法

互斥特征捆绑算法（EFB）从减少特征数的角度出发，被捆绑的特征都是互斥的，这样两个特征捆绑起来才不会丢失信息。如果两个特征不完全互斥，可以用一个指标（冲突比率）来衡量互斥程度，当这个值较小的时候，我们可以将两个特征捆绑起来而不会影响最后的精度。
算法步骤

  1. 构造一个无向带权图，权值对应于特征之间的冲突
  2. 按照特征在图中的度数降序排列特征
  3. 检查排序后的每个特征，对它进行特征绑定或建立新的绑定，使得绑定之后的总冲突最小