18. 线性判别分析
线性判别分析(linear discriminant analysis，LDA)是对fisher的线性鉴别方法的归纳，这种方法使用统计学，模式识别和机器学习方法，试图找到两类物体或事件的特征的一个线性组合，以能够特征化或区分它们。所得的组合可用来作为一个线性分类器，或者，更常见的是，为后续的分类做降维处理。
线性判别分析是特征抽取的一种方法。
特征抽取又可以分为监督和无监督的方法。监督的特征学习的目标是抽取对一个特定的预测任务最有用的特征，比如线性判别分析（Linear Discriminant Analysis， LDA）。而无监督的特征学习和具体任务无关，其目标通常是减少冗余信息和噪声，比如主成分分析（Principle Components Analysis， PCA）、独立成分分析、流形学习、自编码器。
线性判别分析可以用于降维。
在实际应用中，数据是多个类别的，我们的原始数据一般也是超过二维的，投影后的也一般不是直线，而是一个低维的超平面。
LDA与PCA 异同点：
某些某些数据分布下PCA比LDA降维较优，如下图所示：
LDA优缺点：
LDA算法既可以用来降维，又可以用来分类，但是目前来说，主要还是用于降维。在进行图像识别相关的数据分析时，LDA是一个有力的工具。下面总结下LDA算法的优缺点。
参考：
https://zhuanlan.zhihu.com/p/27899927
https://www.cnblogs.com/jiangkejie/p/11153555.html
https://www.cnblogs.com/jerrylead/archive/2011/04/21/2024384.html
19.朴素贝叶斯
为什么“朴素”：条件独立性假设：
推导：
在计算条件概率P(x|y)时出现概率为0的情况怎么办：拉普拉斯平滑
优缺点：
优点：
1. 对小规模的数据表现很好
2. 面对孤立的噪声点，朴素贝叶斯分类器是健壮的
3. 可解释性高
缺点：
输入变量必须都是条件独立的
20.梯度提升决策树GBDT/MART (Gradient Boosting Decision Tree)
Decision Tree：GBDT中使用的决策树一般为CART
Gradient Boosting：每次沿着损失函数的梯度下降(负梯度)的方向训练基分类器,
最后将所有基分类器结果加和作为预测结果.
梯度提升与梯度下降关系:
两者都是沿着梯度下降的方向对模型进行优化.
1. 梯度下降是LR或神经网络中使用,梯度优化是针对模型参数的,每次迭代过程都是对参数的更新.
2. 梯度提升是直接对函数的更新,这样和使用什么模型无关,扩展了使用模型的种类
优点:
预测的时候基分类器可以并行计算,预测速度快
对于分布稠密的数据,泛化能力和表达能力都很好
采用决策树作为基分类器,可解释性高,能自动发现特征之间的高阶关系,
也不需要对数据进行归一化等预处理
缺点:
高维稀疏数据,不如svm和神经网络
处理文本分类的时候,没有像处理数值特征的时候那么有优势
串行训练,训练过程慢
21.KMeans
优点：相对是高效的，它的计算复杂度是O(NKt)接近于线性，其中N是数据对象的数目，K是聚类的簇数，t是迭代的轮数
缺点：
（1）受初始点、初始K值的影响每次的结果不稳定；
（2）结果通常不是全局最优而是局部最优解
K值的选择：一般基于经验和多次实验结果。例如采用手肘法，我们可以尝试不同的K值：
由图可见，K值越大，距离和越小；并且，当K=3时，存在一个拐点，就像人
的肘部一样；当K (1,3)时，曲线急速下降；当K>3时，曲线趋于平稳。手肘法认
为拐点就是K的最佳值
K-means++算法：优化K-means“初始点”缺点
二分K-Means算法：
1、将所有样本数据作为一个簇放到一个队列中。
2、从队列中选择一个簇进行K-means算法划分，划分为两个子簇，并将子簇添加到队列中。
3、循环迭代第二步操作，直到中止条件达到(聚簇数量、最小平方误差、迭代次数等)。
4、队列中的簇就是最终的分类簇集合。
从队列中选择划分聚簇的规则一般有两种方式，分别如下：
1、对所有簇计算误差和SSE(SSE也可以认为是距离函数的一种变种)，选择SSE最大的聚簇进行划分操作(优选这种策略)。2、选择样本数据量最多的簇进行划分操作
22. 牛顿法
xwn:牛顿法解决的问题：a,求解函数的根 b,求解函数极值
eg,求函数的根， 图像理解
首先得明确，牛顿法是为了求解函数值为零的时候变量的取值问题的，具体地，当要求解 f(x)=0时，如果 f可导，那么将 f(x)展开：
求局部最优点（极值点）
通过比较牛顿法和梯度下降法的迭代公式，可以发现两者极其相似。海森矩阵的逆就好比梯度下降法的学习率参数alpha。牛顿法收敛速度相比梯度下降法很快，而且由于海森矩阵的的逆在迭代中不断减小，起到逐渐缩小步长的效果。
海森矩阵：
牛顿法的优缺点总结：
优点：二阶收敛，收敛速度快；
缺点：牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂，尤其是在高维情况下。(拟牛顿法就是以较低的计算代价求海森矩阵的近似逆矩阵)
参考 https://www.youtube.com/watch?v=FQN0-KHAgRw
https://zhuanlan.zhihu.com/p/37588590
http://sofasofa.io/forum_main_post.php?postid=1000966
23. 缺失值的处理
缺失值的原因：
- 信息暂时无法获取。如商品售后评价、双十一的退货商品数量和价格等具有滞后效应。
- 信息被遗漏。可能是因为输入时认为不重要、忘记填写了或对数据理解错误而遗漏，也可能是由于数据采集设备的故障
- 获取这些信息的代价太大。如统计某校所有学生每个月的生活费，家庭实际收入等等。
- 有些对象的某个或某些属性是不可用的。如一个未婚者的配偶姓名、一个儿童的固定收入状况等
_缺失值较多：_直接舍弃该特征
缺失值较少（<10%）：填充处理
- 异常值填充：将缺失值作为一种情况处理0
- 均值/条件均值填充：
- 均值：对于数值类型属性，可采用所有样本的该属性均值，
非数值类型，可采用所有样本的众数
其条件均值指的是与缺失值所属标签相同的所有数据的均值
- 最近距离法K-means：先根据欧式距离或相关分析来确定距离具有缺失数据样本最近的K个样本，将这K个值加权平均来估计该样本的缺失数据
- 插值
- 算法拟合填充：对有值的数据采用随机森林等方法拟合，然后对有缺失值的数据进行预测，用预测的值来填充
具体算法的缺失值处理：
- LR：如上所述
- 决策树：详见第15点
- XGBoost：将样本分别分配到左孩子和右孩子，选择增益大的方向分裂即可；如果在训练中没有缺失值而在预测中出现缺失，那么会自动将缺失值的划分方向放到右子树
参考链接
https://zhuanlan.zhihu.com/p/33996846
24. 模型评估中常用的验证方法
在机器学习中，我们通常把样本分为训练集和测试集，训练集用于训练模型，测试集用于评估模型。在样本划分和模型验证的过程中，存在着不同的抽样方法和验证方法。
1）Holdout检验
Holdout 检验是最简单也是最直接的验证方法，它将原始的样本集合随机划分成训练集和验证集两部分。比方说，对于一个点击率预测模型，我们把样本按照70%～30% 的比例分成两部分，70% 的样本用于模型训练；30% 的样本用于模型验证，包括绘制ROC曲线、计算精确率和召回率等指标来评估模型性能。
缺点：在验证集上计算出来的最后评估指标与原始分组有很大关系。
2）交叉检验
k-fold交叉验证：首先将全部样本划分成k个大小相等的样本子集；依次遍历这k个子集，每次把当前子集作为验证集，其余所有子集作为训练集，进行模型的训练和评估；最后把k次评估指标的平均值作为最终的评估指标。在实际实验中，k经常取10。
留一验证：每次留下1个样本作为验证集，其余所有样本作为测试集。样本总数为n，依次对n个样本进行遍历，进行n次验证，再将评估指标求平均值得到最终的评估指标。在样本总数较多的情况下，留一验证法的时间开销极大。事实上，留一验证是留p验证的特例。
留p验证:每次留下p个样本作为验证集，而从n个元素中选择p个元素有C(p,n)种可能，因此它的时间开销更是远远高于留一验证，故而很少在实际工程中被应用。
3) 自助法：
不管是Holdout检验还是交叉检验，都是基于划分训练集和测试集的方法进行模型评估的。然而，当样本规模比较小时，将样本集进行划分会让训练集进一步减小，这可能会影响模型训练效果。有没有能维持训练集样本规模的验证方法呢？自助法可以比较好地解决这个问题。
自助法是基于自助采样法的检验方法。对于总数为n的样本集合，进行n次有放回的随机抽样，得到大小为n的训练集。n次采样过程中，有的样本会被重复采样，有的样本没有被抽出过，将这些没有被抽出的样本作为验证集，进行模型验证，这就是自助法的验证过程。
当样本无穷大时，使用自助法有多少样本未被选择：
一个样本一次抽中概率为1-1/n，n次未抽中的概率为（1-1/n)^n，
25. 主成分分析
主成分分析是一种降维的方法，目的是找到一个超平面，将原有样本投射在该超平面上，原则则是样本经过投射后损失的信息尽量的少。
PCA 对该超平面有两种解释：
1. 最近重构性：样本点到该超平面的距离都足够近。
2. 最大可分性：样本点到该超平面的投影都尽量可分。
用最大可分性来推导，就是使得投影后的样本的方差尽可能大，两种方式都可以得到下式：(tr表示矩阵的迹，即矩阵主对角线元素的和，也等于矩阵所有特征值的和)
对其使用拉格朗日乘子法得到：
对XXT做特征值分解，取最大的d’(d’为降维后的维数)个特征值对应的特征向量作为W，即得到PCA的解。
d’的选取：
1. 用户事先指定。
2. 用其它开销较小的学习器先进行交叉验证选取。
3. 从重构的角度出发，设定一个重构阈值，如t=95%:
降维的作用：
1. 增大样本采样密度。
2. 去除噪声。
26.Softmax函数的特点和作用是什么
我们知道max，假如说我有两个数，a和b，并且a>b，如果取max，那么就直接取a，没有第二种可能
但有的时候我们不想这样，因为这样会造成分值小的那个饥饿。所以我希望分值大的那一项经常取到，分值小的那一项也偶尔可以取到，那么我用softmax就可以了
现在还是a和b，a>b，如果我们取按照softmax来计算取a和b的概率，那a的softmax值大于b的，所以a会经常取到，而b也会偶尔取到，概率跟它们本来的大小有关。所以说不是max，而是Softmax那各自的概率究竟是多少呢，我们下面就来具体看一下
定义：
1、计算与标注样本的差距
在神经网络的计算当中，我们经常需要计算按照神经网络的正向传播计算的分数S1，和按照正确标注计算的分数S2，之间的差距，计算Loss，才能应用反向传播。Loss定义为交叉熵
样本中正确的那个分类的对数值。
取log里面的值就是这组数据正确分类的Softmax值，它占的比重越大，这个样本的Loss也就越小，这种定义符合我们的要求。
2、计算上非常方便
当我们对分类的Loss进行改进的时候，我们要通过梯度下降，每次优化一个step大小的梯度。我们定义选到yi的概率是
然后我们求Loss对每个权重矩阵的偏导，应用链式法则
27.样本不均衡
导致模型性能降低的本质原因
模型训练时优化的目标函数和人们在测试时的评价标准不同：
1. 分布：在训练时优化的是整个训练集（正负样本比例可能是1∶99）的正确率 而测试时可能想要模型在正样本和负样本上的平均正确率尽可能大（实际上是期望正负样本比例为 1∶1）
2. 权重（重要性）：训练时认为所有样本的贡献是相等的，而测试时假阳性样本（False Positive） 和伪阴性样本（False Negative）有着不同的代价
解决办法
基于数据
a）随机采样：欠采样(有放回)+过采样（放不放回都可以）
欠采样对少数样本进行多次复制，扩大了数据规模，但容易造成过拟合
欠采样丢弃部分样本，有可能会丢失部分有用信息，导致模型只学到了整体模式的部分
b)SMOTE算法(针对过采样）不再简单的复制样本，而是生成新样本，降低过拟合
对少数类的数据集的每一个样本x,从其k近邻中随机选取一个样本y,在其连线上随机选取一点，作为新合成的样本
根据采样倍率重复操作
每个少数类样本合成相同数量的新样本，这可能会增大类间重叠度，并且会生成一些不能提供有益信息的样本
i）Borderline-SMOTE:只给那些处在分类边界上的少数类样本 合成新样本
ii)ADASYN: 给不同的少数类样本合成不同个数的新样本
iii）数据清理方法:进一步降低合成样本带来 的类间重叠
数据扩充方法也是一种过采样，对少数类样 本进行一些噪声扰动或变换（如图像数据集中对图片进行裁剪、翻转、旋转、加光照等）以构造出新的样本
c)Informed Undersampling(欠采样):解决数据丢失问题
i)easy ensemble
从多数类中随机抽取子集E,与所有少数类训练基分类器。
重复操作后，基分类器融合
ii)Balance Cascade
从多数类中随机抽取子集E,与所有少数类训练基分类器
从多数类中剔除被分类正确的样本，继续重复操作
融合基分类器
基于算法
1. 改变损失函数，不同类别不同权重 ------不平衡
2. 转化为单类学习（one-class learning)—极度不平衡
3. 异常检测（anormaly detection)
28.损失函数
回归
MSE loss／均方误差－－Ｌ２损失
MAE loss／平均绝对误差－－L１损失
MSE VS MAE
MSE易求解，但对异常值敏感，得到观测值的均值
MAE对于异常值更加稳健， 得到观测值的中值
对于误差较大的异常样本，MSE损失远大于MAE，使用MSE的话，模型会给予异常值更大的权重，全力减小异常值造成的误差，导致模型整体表现下降
因此，训练数据中异常值较多时，MAE较好
但MAE在极值点梯度会发生跃迁，即使很小的损失也会造成较大的误差，为解决这一问题，可以在极值附近动态减小学习率
总结：
1. MAE对异常值更加鲁棒，但导数的不连续导致找最优解过程中低效
2. MSE对异常值敏感，但优化过程更加稳定和准确
问题：例如某个任务中90%的数据都符合目标值——150，而其余的10%数据取值则在0-30之间
那么利用MAE优化的模型将会得到150的预测值而忽略的剩下的10%（倾向于中值）；
而对于MSE来说由于异常值会带来很大的损失，将使得模型倾向于在0-30的方向取值。
Huber loss/平滑平均绝对误差
对异常值不敏感，且可微
使用超参数δ来调节这一误差的阈值。当δ趋向于0时它就退化成了MAE，而当δ趋向于无穷时则退化为了MSE
Log-Cosh loss
拥有Huber的所有优点，并且在每一个点都是二次可导的。二次可导在很多机器学习模型中是十分必要的
Quantile loss/分位数损失
_参考：_https://www.jianshu.com/p/b715888f079b
- 分类
- 0-1 loss（很少使用）
对每个错分类点都施以相同的惩罚
不连续、非凸、不可导，难以使用梯度优化算法
Cross Entropy Loss/交叉熵损失
Hinge Loss
一般多用于支持向量机（SVM）
ys > 1 的样本损失皆为 0，由此带来了稀疏解，使得 SVM 仅通过少量的支持向量就能确定最终超平面
- Exponential loss/指数损失
一般多用于AdaBoost 中。因为使用 Exponential Loss 能比较方便地利用加法模型推导出 AdaBoost算法。该损失函数对异常点较为敏感，相对于其他损失函数robust性较差
Modified Huber loss
结合了 Hinge Loss 和 交叉熵 Loss 的优点。一方面能在 ys > 1 时产生稀疏解提高训练效率；另一方面对于 ys < −1 样本的惩罚以线性增加，这意味着受异常点的干扰较少
Softmax loss
当 s << 0 时，Softmax 近似线性；当 s>>0 时，Softmax 趋向于零。Softmax 同样受异常点的干扰较小，多用于神经网络多分类问题中
注：相比 Exponential Loss，其它四个 Loss，包括 Softmax Loss，都对离群点有较好的“容忍性”，受异常点的干扰较小，模型较为健壮
_参考：_https://blog.csdn.net/weixin_41065383/article/details/89413819
Focal loss
背景：
one-stage网络因为正负样本严重不均衡，且负样本中还有很多易区分的原因，精度一般低于two-stage 网络(two-stage 利用RPN网络，将正负样本控制在1：3左右）
原理：
1，解决正负样本不均衡问题：添加权重控制，增大少数类样本权重
2，解决难易样本问题：Pt越大说明该样本易区分，应当降低容易区分样本的权重。也就是说希望增加一个系数，概率越大的样本，权重系数越小。
另，为提高可控性，引入系数γ
综合：两个参数α和γ协调来控制，本文作者采用α=0.25，γ=2效果最好
29.贝叶斯决策论
概率框架下实施决策的基本方法
以多分类举例：
共 N 种类别，λij 为将 j 类样本误分类为 i 类样本所产生的损失。
那么，给定样本 x，将其分类为 i 类样本所产生的期望损失为：
任务目标为找到分类器 h:X→Y ，使总体损失最小：
最好的 h 显然是对每个样本 x，都选择期望损失最小的类别：
h* 就叫贝叶斯最优分类器，R(h*)叫贝叶斯风险，1-R(h*) 是分类器所能达到的最优性能，即通过机器学习所能产生的模型精度的理论上限。
比如，目标是最小化误分类率，那么：
判别式 vs 生成式
两者的本质区别在于建模对象不同。
判别式
直接对 P(c|x) 建模：给定 x，使用模型预测其类别 c，通过各种方法来选择最好的模型。
生成式
对 P(c,x) 建模，再计算 P(c|x)：
P©好得，P(x)无所谓，重点在如何获取 P(x|c).
极大似然估计
假设 P(x|c) 满足某种分布(分布参数为 θ)，再用极大似然估计找出 θ.
朴素贝叶斯
假设 x 中所有属性相互独立：
生成式模型理解 LR：
1. 常见的判别式与生成式模型：
判别式：线性回归、逻辑回归、线性判别分析、SVM、神经网络
生成式：隐马尔科夫模型HMM、朴素贝叶斯、高斯混合模型GMM、LDA、KNN
优缺点
1. 生成式模型最终得到的错误率会比判别式模型高，但是收敛所需的训练样本数会比较少。
2. 生成式模型更容易拟合，比如在朴素贝叶斯中只需要计数即可，而判别式模型通常都需要解决凸优化问题。
3. 生成式模型可以更好地利用无标签数据。
4. 生成式模型可以用来生成样本 x.
5. 生成式模型可以用来检测异常值。
30.采样
实现均匀分布的随机数生成器
计算机程序都是确定性的，因此并不能产生真正意义上的完全均匀分布随机数，只能产生伪随机数。
计算机 的存储和计算单元只能处理离散状态值，因此也不能产生连续均匀分布随机数，只能通过离散分布来逼近连续分布（用很大的离散空间来提供足够的精度）
线性同余法：根据当前生成的随机数xt来进行适当变换，进而产生下一次的随机数xt+1 。初始值x0称为随机种子
得到的是区间[0,m−1]上的随机整数，如果想要得到区间[0,1]上的连续均匀分布随机数，用xt除以m即可。
实际上对于特定的种子，很多数无法取到，循环周期基本达不到m。进行多次操作，得到的随机数序列会进入循环周期gcc中的设置
种子seed应该是随机选取的，可以将时间戳作为种子。
