0. 线性回归（LR）
0.1 回归拟合方程
线性方程的拟合式通常为：，
拟合的过程中，我们希望误差项 最小，对它取平方：
使用最大似然估计法，求解当 对 的偏导为 0 的情况下， 的估计解：
（手动验证）
扩展：
矩阵手动求逆的方法有：
1. 右边扩展单位阵，初等变换左边的矩阵为单位阵后得到矩阵的逆；
2. 通过解方程组，矩阵与逆矩阵相乘等于单位阵（和上一个方式几乎相同）；
0.2 向量矩阵介绍
从B站李沐老师的《动手学深度学习》课程中导出，对于常用的矩阵求导进行了介绍。
首先介绍线性代数，矩阵之间的加减相比不用多说，矩阵与标量的乘除法也无需过多介绍。标量之间的操作很简单：
向量之间的操作（长度显然是数学的范数）：
注：范数是一种将向量映射为非零的正长度或者大小，半范数可以为非零的适量赋予零长度；存在三个性质：① 非负性；② 齐次性；③ 三角不等式；最后的三个等式分别代表了非负性、三角不等式以及齐次性。
向量乘法：
矩阵简单操作：
注1：正交矩阵与正交向量不同，正交向量的乘积为零，正交矩阵的成绩为单位向量；正交矩阵有几个特征，所有行都相互正交，所有行都有单位长度，并且；
注2：置换矩阵是一个方阵，仅由0或者1组成，每一行每一列恰好只有一个1，其余元素为0。因为其他矩阵乘以置换矩阵，得到的是原有矩阵的行（置换矩阵左乘）或者列（右乘置换矩阵）发生置换得到的矩阵；
0.3 矩阵求导
首先回忆一下，标量导数，标量的导数是切线的斜率，常用的函数导数形式有：
将导数扩展到不可微的函数中，被称为亚导数，比如：
将导数拓展到向量，可以得到：
注：原来当时我只是被问懵了，写出来还没有讲解我就知道维度应该是怎么样的，向量对向量的求导不就类似于Hessian矩阵么。
对于梯度的理解就是，它总是向着值最大的方向去走，比如图中的圆圈是等高线，变量域是一个平面，因此梯度是等高线的切线，总是指着值变化最大的地方，这也是机器学习求解的核心思想。
拓展到矩阵之后是这样的：
0.4 自动求导
1. 逻辑回归（LR）
1.1 回归拟合方程
使用线性函数进行分类时，通过线性函数 值大小来判断类别，通常是：
但是这个判断函数本身不可微，取对数之后得到替代函数：
原先是：
这里的 为正例发生的概率， 为反例发生的概率，分式代表的是正例相比反例的概率，取对数之后并重新求解得到原有的式子；
极大似然估计法求解模型参数，如下：
因为机器学习中使用平均对数似然损失：
最小化损失函数等价于最大化似然函数。
1.2 正则化方式
随机梯度下降法：
随机梯度下降时，通过损失函数对 的一阶导数来找下降方向，以迭代的方式更新参数，其更新方式为：
显然，是学习率，表示学习速率，通常是机器学习中的超参数。
牛顿法：
牛顿法的基本思想就是，在原有的参数估计值附近，对损失函数进行二阶泰勒展开，进而找到极小点的下一个估计值。假设 为当前极小值估计值，那么会有：
令 =0，得到了 。
正则化：
正则化是一个通用的算法和思想，所有会产生过拟合现象的算法都可以使用正则化来避免过拟合，正则化为模型增加了“模型参数服从零均值拉普拉斯分布”这一先验知识，正则化相当于为模型增加了“服从零均值正态分布”这一先验知识。
2. 支持向量机（SVM）
2.1 原理
支持向量机是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器。
设存在一条直线可以划分所有样本为两类，该直线为 ，可以简单得到：
进一步定义样本点 (x_i, y_i) 与分割线的几何间隔为：
可以得到最优化问题为：
简化得到：
构造拉格朗日目标函数得到：
转换之后可以得到：
需要满足两个条件，优化问题是凸优化问题（损失函数取平方损失时满足该条件），且满足KKT条件，KKT条件为：
最终求解得到：
训练完成之后，大部分的训练样本都不需要保留，最终的模型仅与支持向量有关，这里的 是支持向量。
注意上面的小于号其实是等号，因为没有办法打出小于等于，大于号同理；
关于KKT条件的原理，即拉格朗日化简，可参考文章：https://www.zhihu.com/question/38586401
2.2 优化
核函数
上述 的介绍中，用以划分类别的函数为线性函数。然而很多样本无法被线性可分，于是可以通过增加维度来使得样本变得线性可分。核函数可以将低维样本数据映射到高维，再利用 进行分类。
核函数的定义是对于任意 属于 ，均有 。其中 是一个由低维向高维特征空间的映射，将所有的特征映射到一个更高的维度，使线性可分。
勘误，这里应该是将样本从源维度空间映射到一个可分的维度空间；
常用的核函数有线性核函数，多项式核函数，高斯核函数， 核函数，分别为：
其中高斯核函数中的 ，该参数需要调节。
SVM求解过程
1）构造服从约束的目标函数：
2）用 算法求出上式最小时对应的 向量的值 向量；
3）计算 ；
4）找出所有的 S 个支持向量，即满足 对应的样本 ，通过 计算出每个支持向量 对应的 对应的平均值即为最终的 ，最终的分类超平面与决策函数为：
3. 树模型
3.1 分叉
信息增益 - ID3
信息增益是信息熵与条件熵的插值，信息熵的计算方法为：
条件熵相比信息熵，其计算方式为：
所以计算得到的信息增益，就是根据某个特征划分数据集之后，混乱程度的减少。
计算所有可供挑选的特征划分之后，选择可以使得信息增益最大的特征作为分叉特征。
基尼指数 - CART
决策树通过计算 指数，基于最小的 Gini 指数选择特征，生成二叉树。Gini 指数的计算方式为：
在选择特征 X 之后，可以得到选定特征 X 之后的 Gini 指数：
信息增益率（信息增益比）- C4.5
信息增益率，适用于解决信息增益使得属性的选择取值较多的问题，信息增益率为信息增益与该特征的信息熵之比，如下：
式中的表示计算方式相同，但以为标签转换为了以为标签来划分数据集。
3.2 决策树
见下图：
其核心就是根据每一列特征，依据一定的原则，如信息增益与 Gini 指数，选择最优分割点，实现分叉；一棵树完成之后，再对数进行剪枝，避免过拟合。
3.3 随机森林
随机森林是一种集成学习，也就是对于训练数据集，通过训练一系列个体学习器，通过一定的结合策略将它们组合起来，形成一个强有力的学习器，将强学习器作为预测模型。
集成学习需要考虑的两个问题是，如何产生一系列个体学习器，以及选择怎样的结合策略，将个体学习器组合成一个强学习器。弱学习器的问题是，它既不能太弱，也需要在相互之间保证一定的差异性。
集成学习分为两类，一类是 Bagging，一类是 Boosting。这两类的区别在于，Bagging为并行训练，随机有放回地采样一定比例的样本给弱分类器学习，训练之后通过简单的平均组合获得强学习器结果。Boosting是通过训练一个基学习器，然后通过训练结果，提升分错的样本权重，降低分对的样本权重，然后输入到下一个基学习器中，重复直到数量达到指定值，将所有基学习器进行加权结合。
组合策略主要有三种，首先为平均法。平均法包含简单平均与加权平均，当个体学习器性能相差较大时，宜采用加权平均法，在个体学习器性能相近时宜用简单平均法。其次是投票法，分为绝对多数投票、相对多数投票、加权投票法，第一个方法要求票数过半（或者自己设定的阈值），第二份方法则选择票数最多的类别，第三个方法则是加权。最后是学习法，通过另一个学习器来学习这些弱学习器的预测情况。
随机森林的特点主要是，个体学习器为决策树，对训练样本进行采样，对属性进行随机采样。也就是，在选定划分结点的时候，从候选的属性中随机选择一个作为划分，然后选择最优的属性值。
4. XGBoost
XGBoost 是 GBDT 的改进版，GBDT即梯度提升决策树。先了解GBDT做了哪些工作，再看XGBoost做了哪些改进。
4.1 GBDT - 梯度提升决策树
梯度提升决策树的框架如下所示：
步骤一：初始化 ，表示第 棵树的预测值，按照框架所示，初始预测值取决于损失函数的选择，一般来说，常用的损失函数有：
MSE：
MAE：
Logisit Loss：，取 或者
并且，将与的差作为新的传入下一棵树的创建中。
步骤二：的预测值拟合的是目标值与上一棵树预测值的负梯度（残差）；
步骤三：表示树的输出区域（叶子节点），需要拟合负梯度来得到，即计算所有的来计算最合适的，表示输出预测值的函数，表示树的样本加权；（存疑）
拟合负梯度是指，
步骤四：表示树的学习率，通过与累加到树的预测值求解最小的损失函数；
步骤五：更新预测值。
4.2 XGBoost
的目标函数由损失函数和正则化项两部分组成，其基本结构与类似，相比，做了三个步骤优化目标函数。
1）首先为损失函数在上一棵树的预测值附近二阶泰勒展开，去除常数项：
有：
损失函数为：
2）其次为正则化项展开，去除常数项，优化正则化项；
原损失函数去除常数项：
展开正则项并移除常数项：
3）最后为合并一次项系数、二次项系数，得到最终目标函数：
，是叶子节点的权重（就是叶子节点的输出值），是叶子节点的数量，是一个划分的阈值超参数，正则化由叶子节点数量与叶子节点权重向量的范数。
将代入目标函数得：
，
将所有的训练样本按叶子节点进行分组得到：
定义：
其中：
：叶子节点所包含样本的一阶偏导数累加之和，是常数；
：叶子节点所包含样本的二阶偏导数累加之和，是常数；
代入目标函数可以得到：，此时变量只剩下第棵树的权重向量，即的最终目标函数。
4）目标函数求解，单个叶子节点的目标函数为：，当，则取得最小值时，。
5）节点分裂准则
贪心准则，基本思路与CART一样，对特征值排序后遍历划分点，将其中最优的分裂收益作为该特征的分裂收益，选取具有最有分裂收益的特征作为当前节点的划分特征，按其最优划分点进行二叉划分，得到左右子树。
近似算法，简单来说，是将特征的分位数作为划分的候选点，这样的候选点集合由全样本的遍历变为了几个分位数之间的遍历。Global与Local两种是指，Global是指在全体样本上的特征值中选取，Local是指在待分裂节点包含的样本特征值上选取，每个节点分裂前都要进行重新确定样本集。
加权分位数，目标函数令偏导等于零，可以很容易得到，该函数可以理解为为权重，为标签的二次损失函数：
6）列采样与学习率
学习率已经在GBDT上感受到了，即，列采样即样本并不采用全部特征。
7）稀疏感知
缺失值应对策略是算法需要考虑的，特征稀疏问题也同样需要考虑，部分特征可能出现大量的0，需要将部分特征中的0作为缺失值处理，分裂节点的遍历会跳过缺失值的整体，增加运算效率。
8）工程优化 - 并行列块设计
将每一列特征提前进行排序，以块（Block）的形式储存在缓存中，并以索引将特征值和梯度统计量 对应起来，每次节点分裂时会重复调用排好序的块。而且不同特征会分布在独立的块中，因此可以进行分布式或多线程的计算。
9）工程优化 - 缓存访问
特征值排序后通过索引来取梯度 会导致访问的内存空间不一致，进而降低缓存的命中率，影响算法效率。为解决这个问题，为每个线程分配一个单独的连续缓存区，用来存放梯度信息。
10）工程优化 - 核外块计算
数据量过大时，不能同时全部载入内存。XGBoost 将数据分为多个blocks并储存在硬盘中，使用一个独立的线程专门从磁盘中读取数据到内存中，实现计算和读取数据的同时进行。为了进一步提高磁盘读取数据性能，XGBoost还使用了两种方法：一是通过压缩block，用解压缩的开销换取磁盘读取的开销；二是将block分散储存在多个磁盘中，有助于提高磁盘吞吐量。
5. LightGBM
5.1 简介
GBDT前面已经介绍过，其核心思想就是通过弱模型不停地Boosting，拟合前一个模型剩余的残差。该模型具有训练效果好、不易过拟合等优点。但另一方面，相比神经网络算法，该算法在每一次迭代时，都需要遍历整个训练数据多次，如果将整个训练数据装进内存则会限制训练数据的大小；如果不装进内存，反复地读写训练数据又会消耗非常大的时间。尤其面对工业级海量的数据，普通的GBDT算法是不能满足其需求的。
LightGBM提出的主要原因就是为了解决GBDT在海量数据遇到的问题，让GBDT可以更好更快地运用于工业实践。
5.2 对比XGBoost
XGBoost对GBDT的改进就是将数据进行了预排序，将数据分块实现了并行化，并且对目标函数进行了展开。相比于GBDT，性能提升了不少。
这样的预排序算法的优点是能精确地找到分割点。但是缺点也很明显：首先，空间消耗大。这样的算法需要保存数据的特征值，还保存了特征排序的结果（例如，为了后续快速的计算分割点，保存了排序后的索引），这就需要消耗训练数据两倍的内存。其次，时间上也有较大的开销，在遍历每一个分割点的时候，都需要进行分裂增益的计算，消耗的代价大。最后，对cache优化不友好。在预排序后，特征对梯度的访问是一种随机访问，并且不同的特征访问的顺序不一样，无法对cache进行优化。同时，在每一层长树的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问的顺序也不一样，也会造成较大的cache miss。
LightGBM的优化主要有：1）基于Histogram的决策树算法；2）单边梯度采样（GOSS）：使用GOSS可以减少大量只具有小梯度的数据实例，这样在计算信息增益的时候只利用剩下的具有高梯度的数据就可以了；3）互斥特征捆绑 Exclusive Feature Bundling（EFB）：使用EFB可以将许多互斥的特征绑定为一个特征，实现降维；4）带深度限制的Leaf-Wise的叶子生长策略：大多数GBDT工具使用按层生长的决策树生长策略，多余了不少计算开销，LightGBM按叶子生长，可以减少很多节点的分裂；5）使用Histogram，支持类别特征的处理；6）支持高效并行；Cache命中率优化；
5.3 LightGBM的基本原理
1）直方图算法
直方图算法：先把连续的浮点特征值离散化成 个整数，同时构造一个宽度为的直方图。在遍历数据的时候，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。
简单理解：首先确定对于每一个特征需要多少个箱子（bin）并为每一个箱子分配一个整数；然后将浮点数的范围均分成若干区间，区间个数与箱子个数相等，将属于该箱子的样本数据更新为箱子的值；最后用直方图（#bins）表示。
其优点有：
2）带深度限制的 按叶子生长(Leaf-wise) 算法
3）单边梯度采样算法
4）互斥特征捆绑算法
高维度的数据往往都是稀疏的，这种稀疏性启发我们设计一种无损的方法来减少特征的维度。通常被捆绑的特征都是互斥的（即特征不会同时为非零值，像one-hot），这样两个特征捆绑起来才不会丢失信息。如果两个特征并不是完全互斥（部分情况下两个特征都是非零值），可以用一个指标对特征不互斥程度进行衡量，称之为冲突比率，当这个值较小时，我们可以选择把不完全互斥的两个特征捆绑，而不影响最后的精度。互斥特征捆绑算法（Exclusive Feature Bundling, EFB）指出如果将一些特征进行融合绑定，则可以降低特征数量。这样在构建直方图时的时间复杂度从变为，这里 指特征融合绑定后特征包的个数，且 远小于。
此时，如何解决两个问题呢？
① 如何判定哪些特征应当绑定在一起？
将相互独立的特征进行绑定是一个 问题，的算法将这个问题转化为图着色的问题来求解，将所有的特征视为图的各个顶点，将不是相互独立的特征用一条边连接起来，边的权重就是两个相连接的特征的总冲突值，这样需要绑定的特征就是在图着色问题中要涂上同一种颜色的那些点（特征）。此外，我们注意到通常有很多特征，尽管不是100％相互排斥，但也很少同时取非零值。 如果我们的算法可以允许一小部分的冲突，我们可以得到更少的特征包，进一步提高计算效率。经过简单的计算，随机污染小部分特征值将影响精度最多，是每个绑定中的最大冲突比率，当其相对较小时，能够完成精度和效率之间的平衡。具体步骤可以总结如下：
② 怎么将特征绑定为一个呢？
5）工程优化
① 类别特征的直接支持
② 高效并行 - 特征并行
③ 高效并行 - 数据并行
④ 高效并行 - 投票并行
⑤ Cache命中优化（）
5.4 优缺点总结
优点：
缺点：
6. Scikit-Learn实现
常用机器学习算法的包导入与实现：
# Logistics
linear_model.LogisticRegressionCV()
model = linear_model.LogisticRegression(
C=1.0, # 惩罚项
class_weight=None, # 类别权重
dual=False, # 对偶问题
fit_intercept=True, # 拟合常数项
intercept_scaling=1, #
max_iter=1000, # 最大迭代次数
multi_class='ovr', # 多类
n_jobs=1, # 最大使用线程
penalty='l2', # 正则化
random_state=None, # 随机种子或者随机种子生成器
solver='liblinear', # 求解器
tol=0.0001, # 迭代停止阈值
verbose=0, # 日志输出
warm_start=False # 热启动？
)
# SVM
model = sklearn.svm.LinearSVC(
C=1.0, # 浮点数，惩罚参数
loss='hinge', # 损失函数，hinge表示合页算是函数，'squared_hinge'表示合页损失函数的平方
penalty='l1', # 正则化
dual=True, # 是否求解对偶问题
tol=0.5, # 终止迭代的阈值
multi_class='over', # one-vs-rest 多分类策略
fit_intercept=True, # 计算决策函数中的截距
intercept_scaling=, # 常数人工特征
class_weight=, # 字典或字符串，类别权重
verbose=, # 表示是否开启日志输出
random_state=, # 制定随机数种子或者随机数生成器
max_iter=100
)
model = sklearn.svm.LinearSVR()
model = sklearn.svm.NuSVC()
model = sklearn.svm.NuSVR()
model = sklearn.svm.SVC(
C=1.0, # 惩罚系数
coef0=, #和函数中的独立项，对RBF与Poly有效
kernel='RBF', # 默认RGF，还有Linea，Sigmoid，Poly
gamma=, # 核函数的系数，默认gamma = 1 / n_features
degree=2, # 多项式最高次幂
)
model = sklearn.svm.SVR()
# XGBoost
model = xgboost.sklearn.XGBoostRegression()
other_params = {
'learning_rate': 0.05, # 学习率
'n_estimators': 145, # 评估器的数量
'max_depth': 5, # 树的最大深度
'min_child_weight':2, # 最小叶子节点权重
'seed': 0, # 随机数种子
'subsample': 0.8, # 每棵树的采样比例
'colsample_bytree': 0.7, # 每棵树采样的列比例
'gamma': 0.5, # 叶子节点分裂时所需要的最小损失减小量，该值越大，叶子节点越难分裂
'reg_alpha':0 , # 后悔参数
'reg_lambda': 1, #
'eval_metric': 'auc', # 评估方法，有rmse，mae，auc，aucpr（pr曲线下面积）
'use_label_encoder': False
}
model = xgboost.sklearn.XGBoostClassifier(**other_params)
# 集成学习 RF
sklearn.ensemble.RandomForestClassifier()
sklearn.ensemble.RandomForestRegressor()
sklearn.ensemble.RandomTreesEmbedding()
对模型训练拟合效果的评估：
from sklearn.metrics import accuracy_score
from sklearn.metrics import recall_score
from sklearn.metrics import f1_score
from sklearn.metrics import confusion_matrix
from sklearn.metrics import classification_report
from sklearn.metrics import roc_auc_score
from sklearn.model_selection import GridSearchCV