概述
KNN
K Nearest Neighbor: 一个样本最相似的 K 个样本中大多数都属于某一个类别，则该样本也属于这个类别
流程
分类流程：
- 计算未知样本到每个训练样本距离
- 训练样本根据距离排序
- 取距离最近的 K 个训练样本
- 进行多数表决，统计 K 个样本中哪个类别样本更多
- 未知样本归属到出现次数最多的类别中
回归流程：
第 1-3 步同分类流程
- 把这 K 个样本目标值计算求平均值即为未知样本的值
- K 值过小：过拟合，会受到异常点影响
- K 值过大：欠拟合，模型简单，极端例子，K=样本数量
距离
欧式(L2)距离：$d_{12} = \sqrt{\sum_{k=1}^{n}{(x_{1k} - x_{2k})^{2}}}$
曼哈顿(L1)距离：$d_{12} = \sum_{k=1}^{n}{|x_{1k} - x_{2k}|}$
切比雪夫距离：$d_{12} = \max_{k}{|x_{1k} - x_{2k}|}$（相较于曼哈顿可以斜着走）
闽可夫斯基距离 Minkowski：$d_{12} = \sqrt[p]{\sum_{k=1}^{n}{|x_{1k} - x_{2k}|^{p}}}$，上述距离的总结，p=1 时，为曼哈顿距离；p=2 时，为欧式距离；p=∞ 时，为切比雪夫距离。
数据预处理
归一化：对原始数据变换把数据映射到$[mi, mx]$之间。$x’ = \frac{x - min}{max - min}, x’’ = x’ * (mx - mi) + mi$，$max, min$为数据集的最大最小值。（小数据集处理，容易受最大最小值影响）
标准化：对原始数据进行标准化，转换为均为 0，标准差为 1 的标准正态分布的数据。$x’ = \frac{x - mean}{\sigma}$, $mean$为特征平均值，$\sigma$为特征的标准差。（大数据集处理）
超参数选择方法
交叉验证：一种数据集的分割方法，将训练集划分为 n 份，一份做验证集，其他 n-1 份做训练集
如下例子，分成 4 份，每份做验证集做四次训练测试，取四次测试结果平均值
网格搜索：模型有很多超参数，能力也有差异，每种超参数都采用交叉验证评估，最后选择最优参数组合。
线性回归
利用回归方程（函数）对一个或多个自变量（特征值）和因变量（目标值）关系进行建模的一种分析方式
$$ h_{(w)} = w_1x_1 + w_2x_2 + \cdots + b = w^{T}x + b, w^{T} = [b, w_1, w_2, \cdots], x = \begin{pmatrix} 1 \ x_1 \ x_2 \ \vdots \end{pmatrix} $$
损失函数
均方误差（MSE）：$J(w) = \frac{1}{m}\sum_{i=1}^{m}{(h_{(w)}^{(i)} - y^{(i)})^{2}}$
平均绝对误差（MAE）：$J(w) = \frac{1}{m}\sum_{i=1}^{m}{|h_{(w)}^{(i)} - y^{(i)}|}$，反应真实的平均误差。
均方根误差（RMSE）：$J(w) = \sqrt{\frac{1}{m}\sum_{i=1}^{m}{(h_{(w)}^{(i)} - y^{(i)})^{2}}}$，放大误差的数据对指标影响，对异常数据敏感。
正规方程
$$ w = (X^{T}X)^{-1}X^{T}y $$
梯度下降(GD)
$$ w = w - \alpha \frac{\partial J(w)}{\partial w} $$
$\alpha$ 通常在 0.001~0.01 之间，$\alpha$ 越小，收敛越慢，$\alpha$ 越大，收敛越快，但可能错过最优点。
全梯度下降 (FGD)：每次迭代都使用整个训练集，计算量大，收敛慢。例如：
$$ w = w - \alpha \frac{1}{m}\sum_{i=1}^{m}{(h_{(w)}^{(i)} - y^{(i)})x^{(i)}} $$
随机梯度下降 (SDG)：每次迭代只使用一个样本，计算量小，收敛快，但结果不稳定。例如：
$$ w = w - \alpha (h_{(w)}^{(i)} - y^{(i)})x^{(i)} $$
小批量梯度下降：每次迭代使用一部分样本，计算量适中，收敛速度适中，结果稳定。例如：
$$ w = w - \alpha \frac{1}{b}\sum_{i=1}^{b}{(h_{(w)}^{(i)} - y^{(i)})x^{(i)}}, 1 < b < m $$
梯度下降和正规方程的对比：
| 对比维度 | 梯度下降 | 正规方程 |
|---|---|---|
| 是否需要学习率 | 需要选择学习率 | 不需要学习率 |
| 求解方式 | 需要迭代求解 | 一次运算得出，一蹴而就 |
| 应用场景 | 普适性强，迭代计算方式，适合嘈杂、大数据场景 | 小数据量场景、精准的数据场景 |
| 缺点 | - | 计算量大；易受噪声、特征强相关性的影响 |
| 注意事项 | 在各类损失函数（目标函数）求解中大量使用；深度学习中参数常达上亿规模，仅能通过迭代求最优解 | 1. $X^TX$的逆矩阵不存在时，无法求解 2. 计算$X^TX$的逆矩阵非常耗时 3. 数据规律非线性时，无法使用或效果差 |
正则化
- L1 正则化：$J(w) = MSE(w) + \lambda \sum |w_i|$，使权重趋向于 0，甚至为 0，使某些特征失效
- L2 正则化：$J(w) = MSE(w) + \lambda \sum w_i^2$，岭回归，使权重趋向于 0，但不会为 0
$\lambda$为惩罚系数，值越大，权重调整服务越大
逻辑回归
解决分类问题，通过激活函数将预测值映射到[0,1]区间，得到概率值，结合阈值进行分类
Sigmoid 函数：$f(x) = \frac{1}{1 + e^{-x}}$
逻辑回归：$h(x) = sigmoid(w^Tx + b)$，将线性回归输出当作 Sigmoid 函数的输入
损失函数：$Loss(L) = -\sum^{m}{i=1}(y{i}\log(p_i) + (1 - y_i)\log(1 - p_i)), p_i = sigmoid(w^Tx_i + b)$。
性能评价标准
| 预测正例 | 预测反例 | |
|---|---|---|
| 真实正例 | TP | FN |
| 真实反例 | FP | TN |
准确率 – Accuracy
预测正确的结果占总样本的百分比 $$准确率 =(TP+TN)/(TP+TN+FP+FN)$$
精确率（差准率）- Precision
所有被预测为正的样本中实际为正的样本的概率 $$精准率 =TP/(TP+FP)$$
召回率（查全率）- Recall
实际为正的样本中被预测为正样本的概率 $$召回率=TP/(TP+FN)$$
F1-score
为了综合精确率和召回率的表现，在两者之间找一个平衡点，就出现了一个 F1 分数。
$$F1-score = \frac{2 \times Precision \times Recall}{Precision+Recall}$$
ROC 和 AUC
在利用精确率和召回率两个指标时，这两个指标是随着我们设定的分类的阈值变化的，具有一定的主观性，但是我们希望有更好的指标克服这个缺点，能够客观描述一个模型的质量，这就是 ROC 曲线。
$$灵敏度（Sensitivity） = TP/(TP+FN)$$ $$特异度（Specificity） = TN/(FP+TN)$$ $$真正率（TPR） = 灵敏度 = TP/(TP+FN)$$ $$假正率（FPR） = 1- 特异度 = FP/(FP+TN)$$
ROC 曲线以真正率 TPR 为纵轴，以假正率 FPR 为横轴，在不同的阈值下获得坐标点，并连接各个坐标点，得到 ROC 曲线。
AUC 被定义为 ROC 曲线下的面积，使用 AUC 值作为评价标准是因为很多时候 ROC 曲线并不能清晰的说明哪个分类器的效果更好，分类器对应的 AUC 越大说明其效果越好。
决策树
树每个内部节点表示一个特征上的判断，每个分支代表一个判断结果的输出，每个叶节点代表一种分类结果。
熵：信息论中代表随机变量不确定度的度量（越大信息越多），$H(X) = -\sum_{i=1}^{n}p_i \log_2p_i$，$p_i$ 是数据中随机变量出现的概率
条件熵：$H(D \mid A) = \sum_{v=1}^{n} \frac{D^v}{D} H(D^v) = \sum_{v=1}^{n} \frac{D^v}{D} \sum_{k=1}^K \frac{C^{kv}}{D^v} \log \frac{C^{kv}}{D^{v}}$
信息增益：特征 $A$ 对数据集 $D$ 的信息增益 $g(D,A)$，定义为集合 $D$ 的信息熵 $H(D)$ 与特征 $A$ 在数据集 $D$ 中划分后的条件熵 $H(D|A)$ 的差值，$g(D,A) = H(D) - H(D|A)$。
ID3
构建流程：
- 计算每个特征的信息增益
- 使用信息增益最大的特征将数据集拆分成子集
- 使用该特征作为决策树的一个节点
- 使用剩余特征重复上述操作
C4.5
将 ID3 中的信息增益替换为信息增益率
信息增益率 = 信息增益/特征熵
$$Gain_Ratio(D, a) = \frac{Gain(D, a)}{IV(a)}, IV(a) = -\sum_{v=1}^{n} \frac{D^v}{D} Ent(\frac{D^v}{D})$$
CART
分类
采用基尼指数最小化策略
基尼值：从数据集中随机抽取两个样本，其类别标记不一样的概率。越小说明数据集纯度越高。
$$ Gini(D) = \sum_{k=1}^{|y|} \sum_{k’ \neq k} p_k p_{k’} = 1 - \sum_{k=1}^{|y|} p_k^2 $$
基尼指数：选择使划分后基尼系数最小的属性作为最优划分属性。
$$ Gini_index(D, a) = \sum_{v=1}^V \frac{D^v}{D} Gini(D^v) $$
| 名称 | 提出时间 | 分支方式 | 特点 |
|---|---|---|---|
| ID3 | 1975 | 信息增益 | 1. ID3 只能对离散属性的数据集构成决策树 2. 倾向于选择取值较多的属性 |
| C4.5 | 1993 | 信息增益率 | 1. 缓解了 ID3 分支过程中总喜欢偏向选择值较多的属性 2. 可处理连续数值型属性，也增加了对缺失值的处理方法 3. 只适合于能够驻留于内存的数据集，大数据集无能为力 |
| CART | 1984 | 基尼指数 | 1. 可以进行分类和回归，可处理离散属性，也可以处理连续属性 2. 采用基尼指数，计算量减小 3. 一定是二叉树 |
回归
使用平方损失（$Loss(y, f(x)) = (f(x) - y)^2$）作为划分建树依据，采用叶子节点里均值作为预测值
剪枝
把子树节点全部删掉，使用叶子节点替换
- 预剪枝：指在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能提升，则停止划分并将当前节点标记为叶节点；
- 后剪枝：是先从训练集生成一棵完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点。
| 算法 | 优点 | 缺点 |
|---|---|---|
| 预剪枝 | 使决策树的很多分支没有展开，不仅降低了过拟合风险，还显著减少了决策树的训练、测试时间开销。 | 有些分支的当前划分虽不能提升泛化性能，但后续划分却有可能导致性能的显著提高；预剪枝决策树也带来了欠拟合的风险。 |
| 后剪枝 | 比预剪枝保留了更多的分支。一般情况下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝。 | 后剪枝先生成完整决策树再剪枝，自底向上地对树中所有非叶子节点进行逐一考察，训练时间开销比未剪枝的决策树和预剪枝的决策树都要大得多。 |
集成学习
一种思想，通过将多个模型的组合形成一个精度更高的模型，参与组合的模型成为弱学习器（基学习器）。训练时，使用训练集依次训练出这些弱学习器，对未知的样本进行预测时，使用这些弱学习器联合进行预测。
Bagging
- 有放回抽样（bootstrap sampling）产生不同的训练集，训练不同的弱学习器
- 平权投票，多数表决方式决定预测结果
- 弱学习器可以并行训练
Boosting
- 每个训练器重点关注前一个训练器不足的地方进行训练
- 通过加权投票的方式得出预测结果
- 串行训练
随机森林
- 随机选取 m 条数据
- 随机选取 k 个数据特征
- 训练决策树
- 重复 1-3 步 n 次，得到 n 棵决策树
- 预测时，每棵树给出预测结果，最终结果为这 n 棵树投票的结果
AdaBoost
Adaptive Boosting，基于 Boosting 思想实现，核心思想是逐步提高那些被前一步分类错误的样本的权重来训练一个强分类器。算法流程如下：
-
初始化训练数据权重相等，训练第 1 个学习器
- 如果有 100 个样本，则每个样本的初始权重为：$1/100$
- 根据预测结果找一个错误率最小的分裂点，计算、更新：样本权重、模型权重
-
根据新权重的样本集 训练第 2 个学习器
- 根据预测结果找一个错误率最小的分裂点，计算、更新：样本权重、模型权重
-
迭代训练，在前一个学习器的基础上，根据新的样本权重训练当前学习器
- 直到训练出 $m$ 个弱学习器
-
$m$ 个弱学习器集成预测公式
$$ H(x) = sign(\sum_{i=1}^m \alpha_i h_i(x)) $$
- $\alpha$ 为模型的权重，输出结果大于 0 则归为正类，小于 0 则归为负类。
-
模型权重计算公式
$$ \alpha_t = \frac{1}{2} \ln\left(\frac{1-\varepsilon_t}{\varepsilon_t}\right) $$
- $\alpha_t$ 为模型权重
- $\varepsilon_t$ 表示第 $t$ 个弱学习器的错误率
-
样本权重计算公式
- $Z_t$ 为归一化值（所有样本权重总和）
- $D_t(x)$ 为样本权重
- $\alpha_t$ 为模型权重
GBDT
BDT(Boosting Decision Tree)，残差提升树，通过拟合残差的思想来提升，残差=真实值-预测值。
GBDT(Gradient Boosting Decision Tree)，梯度提升树，通过拟合负梯度（等价于残差）的思想来提升。算法流程如下：
- 前一轮迭代得到强学习器：$f_{t-1}(x)$
- 损失函数为平方损失：$L(y, f_{t-1}(x))$
- 本轮迭代目标是找到一个弱学习器：$h_t(x)$
- 使得本轮损失最小：$L(y, f_{t}(x)) = L(y, f_{t-1}(x) + h_t(x)) = (y - f_{t-1}(x) - h_{t}(x))^2$
- 则要拟合的负梯度为：$\frac{\partial L(y, f(x_i))}{\partial f(x_i)} = -(y_i - f(x_i))$
XGBoost
XGBoost(eXtreme Gradient Boosting)，极端梯度提升树，对 GBDT 的改进，在损失函数中增加正则化项，构建思想：
- 最小化训练数据的损失函数：$\min_{f \in F} \frac{1}{N} \sum_{i=1}^{N}L(y_i, f(x_i))$，训练的模型复杂度过高，容易过拟合；
- 在损失函数中加入正则化项：$\min \frac{1}{N} \sum_{i=1}^{N}L(y_i, f(x_i)) + \Omega(f)$，降低模型复杂度，提高对位置的测试数据的泛化能力。
正则化项 $\Omega(f)$ 的构建：
$$ \Omega(f) = \gamma T + \frac{1}{2} \lambda \parallel w \parallel^2 $$
- $\gamma T$ 中 $T$ 表示叶子节点个数
- $\lambda \parallel w \parallel^2$ 中 $w$ 表示叶子节点输出值组成的向量
整体目标函数：
$$ \sum_{i}L(y_i, f(x_i)) + \sum_{k} \Omega(f_k) $$
- $i$ 表示第 $i$ 个样本
- $k$ 表示第 $k$ 颗树
通过
- 二阶泰勒展开，去除常数项
- 正则化项展开，去除常数项
- 合并一次项系数、二次项系数
得到最终目标函数：
$$ L = \sum_{j=1}^{T} (G_j W_j + \frac{1}{2} (H_j + \lambda) W_j^2) + \gamma T $$
- $G_j = \sum_{i \in I_j} g_i$，表示叶子节点 $j$ 所包含样本的一阶偏导数累加之和，是一个常数
- $H_j = \sum_{i \in I_j} h_i$，表示叶子节点 $j$ 所包含样本的二阶偏导数累加之和，是一个常数
所以上述目标函数中的变量只剩下第 $t$ 颗树的权重向量 $w$，对每个叶子节点目标函数求最优解 $w^*$，由此得到目标函数最优解 $Obj$：
$$ w^* = -\frac{G_j}{H_j + \lambda} $$
$$ Obj = -\frac{1}{2} \sum_{j=1}^{T} \frac{G_j^2}{H_j + \lambda} + \gamma T $$
上述内容参考自：XGBoost 的原理、公式推导、Python 实现和应用
朴素贝叶斯
贝叶斯公式：
$$ P(C|W) = \frac{P(W|C)P(C)}{P(W)} $$
- $P(C)$ 表示 $C$ 出现的概率，一般是目标值
- $P(W|C)$ 表示 $C$ 条件下出现 $W$ 的概率
- $P(W)$ 表示 $W$ 出现的概率
拉普拉斯平滑系数：为了避免概率值为 0，在分子分母上分别加上一个数值。
$$ P(F_1|C) = \frac{N_i + \alpha}{N + \alpha m} $$
- $\alpha$：拉普拉斯系数，一般指定为 1
- $N_i$：$F_1$ 中符合条件 $C$ 的样本数量
- $N$：在条件 $C$ 下所有样本的总数
- $m$: 所有独立样本的总数
K-means
- 确定常数 $K$ 为聚类类别数，随机选取 $K$ 个样本作为初始聚类中心
- 计算每个样本到各个聚类中心的距离，将样本划分到距离最近的聚类中心
- 根据每个类别中的样本点，重新计算出新的聚类中心点（平均值）
- 新中心点与原中心点一致则停止，否则回到第 2 步
评估方法
误差平方和 SSE（Sum of Squared Errors）：表示簇的内聚程度，越小越好，极限值为 0（每个点自己是一个簇）。
$$ SSE = \sum_{i=1}^{k} \sum_{p \in C_i} (p - \mu_i)^2 $$
- $k$：聚类类别数
- $C_i$：第 $i$ 个簇
- $p$：簇 $C_i$ 中的样本
- $\mu_i$：簇 $C_i$ 的中心点
SC 轮廓系数法（Silhouette Coefficient）：考虑簇内的内聚程度，簇外的分离程度，取值范围为 [-1, 1]，值越大越好。计算过程如下：
- 计算每个样本 $x_i$ 到同簇其他样本的平均距离 $a_i$，该值越小越好，说明簇内相似程度越大
- 计算每个样本 $x_i$ 到其他簇的所有样本的平均距离 $b_i$，该值越大越好，说明簇间相似程度越小
- 根据公式计算该样本轮廓系数：$\frac{b_i - a_i}{max(a_i, b_i)}$
- 计算所有样本平均轮廓系数
- 轮廓系数范围为 [-1, 1]，值越大聚类效果越好
CH 系数法（Calinski-Harabasz Index）：考虑簇内的内聚程度（类别内部数据距离平方和越小越好）、簇外的离散程度（类别间距离平方和越大越好）、中心点个数（聚类种类数越少越好）。整体值越大表示聚类效果越好，计算公式如下：
$$ CH(k) = \frac{SSB}{SSW} \frac{m - k}{k - 1} $$
$$ SSW = \sum_{i=1}^{m} \parallel x_i - C_{pi} \parallel^2 $$
$$ SSB = \sum_{j=1}^{k} n_j \parallel C_j - \overline{X} \parallel ^2 $$
- $SSW$：相当于 $SSE$，簇内距离，越小越好
- $C_{pi}$：样本 $x_i$ 所属的簇中心
- $x_i$：样本
- $m$：样本总数
- $SSB$：簇间距离，越大越好
- $C_j$：第 $j$ 个簇的中心
- $\overline{X}$：所有中心点的均值
- $n_j$：第 $j$ 个簇的样本数
- $k$：聚类类别数
