机器学习算法中的模型

感知机

感知机是一个二分类线性分类模型,目的是为了找到可以将实例划分为两类的分离超平面，通过基于误分类的损失函数，利用梯度下降法对损失函数进行最优化。是神经网络和支持向量机的基础。
感
知机是一个二分类线性分类模型，它的目的是求得一个能将训练集正实例点和负实例点完全分开的分离超平面。通过极小化基于误分类的损失函数，运用梯度下降来求解参数。 主要关注的是误分类点距离超平面的距离，误分类点越少，误分类点距离超平面越近，损失函数值就越小。

K-近邻：

KNN，一种分类和回归方法
根据最接近预测的那个点的k个点的最大特征结果来表示预测的点的类别。可以分类也可以回归。

k值的选取：一般取一个比较小的值，采用交叉验证法来选取最优的k值。（k太小，模型复杂，容易过拟合；k太大，近似误差会增大，输入实例较远的训练实例也会对预测起作用，使预测发生错误）
距离度量：一般使用欧式距离(欧式距离可适用于不同空间，表示不同空间点之间的距离)
分类决策规则：一般为多数表决
回归决策规则：选择平均法，k个样本输出的平均值作为预测输出

朴素贝叶斯

朴素贝叶斯是基于贝叶斯定理与特征条件独立假设的分类方法。对于给定的待分类项x，通过学习到的模型计算后验概率分布。即：在此项出现的条件下各个目标类别出现的概率，将后验概率最大的类作为x所属的类别。

引入条件独立假设、
假定所有的特征在数据集中的作用是独立同分布的，但这个假设在现实生活中很不真实，因此很“朴素”。

决策树

决策树是一种树结构，一种分类和回归方法。

决策树目的是为了让模型的不确定性降低的越快越好，基于评价指标的不同，主要分为ID3、C4.5和CART算法。 ID3选择信息增益大的属性来对样本进行划分，但是容易产生过拟合；所以C4.5选择信息增益比来对样本进行划分；不过这两种算法都没有完全解决过拟合的问题，因为对决策树的生长没有进行合理的限制，所以引入CART树，使用基尼系数作为节点的分类依据。CART树中有剪枝操作。

剪枝是防止决策树过拟合的方法
剪枝分为预剪枝和后剪枝两种，预剪枝是在构建决策树时抑制它的生长，后剪枝是决策树生长完全后再对叶子节点进行修剪。

逻辑回归

逻辑回归假设数据服从伯努利分布，通过极大化似然函数的方法，运用梯度下降来求解参数，来达到将数据二分类的目的。

SVM

SVM 支持向量机是一种二类分类模型，基本模型是在特征空间中寻找间隔最大化的分离超平面的线性分类器。
主要分为线性支持向量机、非线性支持向量机
硬间隔、软间隔

当样本量线性可分时，使用硬间隔最大化学习一个线性分类器，即线性可分支持向量机
当训练数据近似线性可分时，引入松弛变量，通过软间隔最大化，学习一个线性分类器，即线性支持向量机
当训练数据线性不可分时，使用核技巧即软间隔最大化，学习非线性支持向量机。

比较关键的知识点：几何间隔、原始问题和对偶问题、硬间隔和软间隔、核技巧和核函数

最大熵模型

最大熵模型是对数线性分类模型。
学习概率模型的时候，在所有可能的概率模型(分布)中，熵最大的模型就是最好的模型。

逻辑回归和最大熵模型没有本质区别；逻辑回归是最大熵对应为二分类时的特殊情况，也就是说，当逻辑回归扩展为多类别的时候，就是最大熵模型。

聚类

主要会的聚类算法是k-means和DBSCAN。

k-means：从数据集中随机选择k个聚类样本作为初始的聚类中心,然后计算数据集中每个样本到这k个聚类中心的距离,并将此样本分到距离最小的聚类中心所对应的类中。将所有样本归类后,对于每个类别重新计算每个类别的聚类中心即每个类中所有样本的质心,重复以上操作直到聚类中心不变为止。

dbscan:一种基于密度的空间聚类算法.将具有足够高密度的区域划分为簇,并在有噪声的数据中发现任意形状的簇

LR和softmax区别

聚类算法

主要有的聚类算法是k-means和DBSCAN。

DBSCAN

DBSCAN：基于密度的聚类算法：DBSCAN是一种基于密度的空间聚类算法,它不需要定义簇的个数,而是将具有足够高密度的区域划分为簇,并在有噪声的数据中发现任意形状的簇,在此算法中将簇定义为密度相连的点的最大集合。
优点：
速度快，计算简便
缺点：
我们必须提前知道数据有多少类/组。
具体步骤：

首先确定半径r和minPoints. 从一个没有被访问过的任意数据点开始，以这个点为中心，r为半径的圆内包含的点的数量是否大于或等于minPoints，如果大于或等于minPoints则改点被标记为central point,反之则会被标记为noise point。
重复1的步骤，如果一个noise point存在于某个central point为半径的圆内，则这个点被标记为边缘点，反之仍为noise point。重复步骤1，知道所有的点都被访问过。

优点：不需要知道簇的数量
缺点：需要确定距离r和minPoints

k-means

基于划分的聚类算法：给定一个有N个元祖或者记录的数据集，分裂法将构造k个分组，每一个分组就代表一个聚类。
从数据集中随机选择k个聚类样本作为初始的聚类中心,然后计算数据集中每个样本到这k个聚类中心的距离,并将此样本分到距离最小的聚类中心所对应的类中。将所有样本归类后,对于每个类别重新计算每个类别的聚类中心即每个类中所有样本的质心,重复以上操作直到聚类中心不变为止。

k-means存在 缺点：

1）k-means是局部最优的，容易受到初始质心的影响
2）同时，k值的选取也会直接影响聚类结果，最优聚类的k值应与样本数据本身的结构信息相吻合，而这种结构信息是很难去掌握，因此选取最优k值是非常困难的。

算法步骤：
(1) 首先我们选择一些类/组，并随机初始化它们各自的中心点。中心点是与每个数据点向量长度相同的位置。这需要我们提前预知类的数量(即中心点的数量)。
(2) 计算每个数据点到中心点的距离，数据点距离哪个中心点最近就划分到哪一类中。
(3) 计算每一类中中心点作为新的中心点。
(4) 重复以上步骤，直到每一类中心在每次迭代后变化不大为止。也可以多次随机初始化中心点，然后选择运行结果最好的一个。

k值的选择：

  1. 拍脑袋法：将样本量除以2再开方出来的值作为K值
  2. 手肘法 使用指标SSE（误差平方和）：当k小于真实聚类数的时候，随着k的增大，SSE会大幅下降；而当k到达真实聚类数的时候，再增加k,SSE的下降幅度骤减，并且越增大，越趋于平缓。关系图是一个手肘的形状。
  3. 间隔统计量（Gap Statistic）
  4. 轮廓系数法：用Xi到某个簇所有样本平均距离作为衡量该点到该簇的距离后，选择离Xi最近的一个簇作为最近簇。求出所有样本的轮廓系数后再求平均值就得到了平均轮廓系数。平均轮廓系数的取值范围为[-1,1]，且簇内样本的距离越近，簇间样本距离越远，平均轮廓系数越大，聚类效果越好。那么，很自然地，平均轮廓系数最大的k便是最佳聚类数。
  5. Calinski-Harabasz准则

区别

  • K均值和DBSCAN都是将每个对象指派到单个簇的划分聚类算法，但是K均值一般聚类所有对象，而DBSCAN丢弃被它识别为噪声的对象。
  • K均值使用簇的基于原型的概念，而DBSCAN使用基于密度的概念。
  • K均值很难处理非球形的簇和不同大小的簇。DBSCAN可以处理不同大小或形状的簇，并且不太受噪声和离群点的影响。当簇具有很不相同的密度时，两种算法的性能都很差。
  • K均值只能用于具有明确定义的质心（比如均值或中位数）的数据。DBSCAN要求密度定义（基于传统的欧几里得密度概念）对于数据是有意义的。
  • K均值可以用于稀疏的高维数据，如文档数据。DBSCAN通常在这类数据上的性能很差，因为对于高维数据，传统的欧几里得密度定义不能很好处理它们。
  • 基本K均值算法等价于一种统计聚类方法（混合模型），假定所有的簇都来自球形高斯分布，具有不同的均值，但具有相同的协方差矩阵。DBSCAN不对数据的分布做任何假定。
  • K均值和DBSCAN的最初版本都是针对欧几里得数据设计的，但是它们都被扩展，以便处理其他类型的数据。
  • K均值DBSCAN和都寻找使用所有属性的簇，即它们都不寻找可能只涉及某个属性子集的簇。
  • K均值可以发现不是明显分离的簇，即便簇有重叠也可以发现，但是DBSCAN会合并有重叠的簇。
  • K均值算法的时间复杂度是O(m)，而DBSCAN的时间复杂度是O(m^2)，除非用于诸如低维欧几里得数据这样的特殊情况。
  • DBSCAN多次运行产生相同的结果，而K均值通常使用随机初始化质心，不会产生相同的结果。
  • K均值聚类可以看作优化问题，即最小化每个点到最近质心的误差平方和，并且可以看作一种统计聚类（混合模型）的特例。DBSCAN不基于任何形式化模型。

LR 逻辑回归(手动推导)

公式推导 Sigmod函数 似然估计法 求对数 求最大值 梯度上升的方法 损失函数

如何进行多分类？ 如果类别之间有明显的互斥就选用softmax，若不互斥有交叉则使用2

  1. 修改损失函数，使用softmax函数构造模型解决多分类问题
  2. 构建相应类别个数的二分类逻辑回归分类器

LR和SVM的区别：

  • LR是参数模型,SVM为非参数模型
  • 使用的损失函数不同。LR采用的损失函数为logisticalloss,而SVM采用的是hingeloss(合页损失函数)。这两个损失函数的目的都是增加对分类影响较大的数据点的权重，减少与分类关系较小的数据点的权重。
  • 在学习分类器的时候,SVM只考虑与分类最相关的少数支持向量点。而LR通过非线性映射，大大减小了离分类平面较远的点的权重，相对提升了与分类最相关的数据点的权重。
  • LR的模型相对简单,在进行大规模线性分类时比较方便。SVM的理解和优化相对来说复杂一些，SVM转化为对偶问题后,分类只需要计算与少数几个支持向量的距离,这个在进行复杂核函数计算时优势很明显,能够大大简化模型和计算。
  • LR 能做的 svm能做，但可能在准确率上有问题，svm能做的LR有的做不了。

LR和线性回归的区别：

  • LR分类；线性回归 预测
  • LR 预测函数；线性回归 拟合函数
  • LR 用最大似然估计来计算参数；线性回归用最小二乘法来计算参数
  • LR 对异常值有较好的稳定性； 线性回归 更容易受到异常值的影响

SVM(手动推导)

什么是支持向量机：二分类模型，模型为特征空间上的间隔最大的线性分类器，策略是最大化分类间隔，它只关注支持向量到超平面的距离。
SVM的目标是寻找一个最优化超平面可以在空间中分割两类数据。距离超平面最近的那些点，也就是支持向量，需要最大化支持向量距离超平面的距离。

作用：可以解决二分类或者多分类问题
物理意义：构造一个最优化的超平面在空间中分割数据

原问题、对偶问题、拉格朗日乘子法、

硬间隔、软间隔： 区别在于是否引入松弛变量 公式

SVM的对偶问题推导

使用对偶计算的目的： 方便核函数的引入、原问题的求解复杂度与特征的维数有关，而转成对偶问题以后只与问题的变量个数有关，这个变量个数也就是支持向量的个数，相较于特征数来说较少。并且对偶问题是一个凸优化问题，通过拉格朗日算子使带约束的优化目标转为不带约束的优化函数。

损失函数

SVM只和分类界限上的支持向量点有关,换而言之 只和局部数据有关。

核函数和核方法

核函数：线性核、多项式核、高斯核
核函数的作用：核函数隐含着一个从低维空间到高维空间的映射,这个映射可以把低维空间中线性不可分的两类点变成线性可分的。
本质： 因为实际应用中会遇到线性不可分的情况，所以通常的做法就是将样例特征映射到高维空间中，转换成线性可分问题，但是会遇到维度过高的问题，所以引入核函数，将特征从低位转换到高维，但是避免了直接进行高维空间的复杂计算，可以在低维上进行计算，实质上分类效果表现在高维上。

线性核和高斯核的选用：当数据和问题是线性可分的，并且数据的特征提取较好，所包含的信息量足够大，则选用线性核；若特征数较少，样本量适中，对于时间不敏感，且问题线性不可分的时候，则使用高斯核的效果更好。

应用场景：
线性核： 特征维数高、样本数量非常多(避免造成庞大的计算量)
多项式核
高斯核： 样本数量可观、特征少(非线性核)

核函数的选择：当样本的特征很多且维数很高时可考虑用SVM的线性核函数。当样本的数量较多,特征较少时,一般手动进行特征的组合再使用SVM的线性核函数。当样本维度不高且数量较少时,且不知道该用什么核函数时一般优先使用高斯核函数,因为高斯核函数为一种局部性较强的核函数,无论对于大样本还是小样本均有较好的性能且相对于多项式核函数有较少的参数。

为什么高斯核能够拟合无穷维度：因为将泰勒展开式代入高斯核,将会得到一个无穷维度的映射。

朴素贝叶斯

要求：贝叶斯定理、特征条件独立假设、
朴素贝叶斯属于生成式模型，学习输入和输出的连和分布概率，给定输入x，利用贝叶斯概率定理求出最大的后验概率作为输出y

机器学习中的距离计算方法

  1. 欧式距离：两点之间相减平方和
  2. 曼哈顿距离：绝对值之和
  3. 余弦距离
  4. 切比雪夫距离

分类算法

单一的分类方法： LR、SVM、决策树、朴素贝叶斯、人工神经网络、KNN、
集成学习方法：基于Bagging和Boosting算法、随机森林、GBDT、Adaboost、XGboost

一个问题：有一个数据集，如何进行分类

（分类模型的优缺点，以及分类模型的构造步骤）
根据数据类型选择不同的模型，如Lr或者SVM，决策树。
假如特征维数较多，可以选择SVM模型，
如果样本数量较大可以选择LR模型，但是LR模型需要进行数据预处理；
假如缺失值较多可以选择决策树。
选定完模型后，相应的目标函数就确定了。
还可以在考虑正负样例比比，通过上下集采样平衡正负样例比。

数据存在问题怎么处理

上下采样平衡正负样例比(类不平衡)
考虑缺失值，需要进行缺失值的填充(比如使用KNN)
数据需要进行归一化

训练集中类别不均衡，哪个参数最不准确?

准确度。（可以举个二分类的极度不平衡的例子来说明）

分层采样

适用范围：考虑保持样本结构和总体结构的一致性，当总体有明显差异的几部分组成的时候，适用于分层抽样。

生成式模型和判别式模型

生成式模型：朴素贝叶斯、KNN、贝叶斯网络、HMM、马尔科夫随机场
判别式模型：线性回归、逻辑回归、SVM、CART、神经网络、CRF、Boosting

区别：

  • 判别式模型是针对 条件分布建模，而生成式模型则针对 联合分布进行建模。
  • 不管是生成式模型还是判别式模型，它们最终的判断依据都是 条件概率，但是生成式模型先计算了 联合概率，再由贝叶斯公式计算得到 条件概率。因此，生成式模型可以体现更多数据本身的分布信息，其普适性更广。

决策树

决策树最常用的三个算法是：

  1. ID3
  2. C4.5
  3. CART

区别：

  • ID3是选择 信息增益大的属性来对样本进行划分，由于存在缺点(多属性的取值会使得模型的泛化能力变差，决策树容易产生过拟合)
  • C4.5进行改进，选用了 信息增益比来对样本进行划分
  • 但是问题还是存在。所以引入CART树，使用 基尼系数作为节点的分类依据。

熵

联合熵：两个随机变量X，Y的联合分布，可以形成联合熵Joint Entropy，用H(X,Y)表示。
条件熵：在随机变量X发生的前提下，随机变量Y发生所新带来的熵定义为Y的条件熵，用H(Y|X)表示，用来衡量在已知随机变量X的条件下随机变量Y的不确定性。
H(Y|X)=H(X,Y)-H(X)，整个式子表示(X,Y)发生所包含的熵减去X单独发生包含的熵。
相对熵：又称互熵，交叉熵，鉴别信息，Kullback熵，Kullback-Leible散度等。在一定程度上，相对熵可以度量两个随机变量的“距离”，且有D(p||q) ≠D(q||p)
互信息：两个随机变量X，Y的互信息定义为X，Y的联合分布和各自独立分布乘积的相对熵，用I(X,Y)表示。I(X,Y)=D(P(X,Y)||P(X)P(Y))

H(Y)-I(X,Y)=H(Y|X)
H(Y|X)=H(X,Y)-H(X)【条件熵的定义】
H(Y|X)=H(Y)-I(X,Y)【互信息】
则
I(X,Y)= H(X)+H(Y)-H(X,Y)

正则化

L1正则化和L2正则化的区别：

  • L1是模型各个参数的绝对值之和,L2为各个参数平方和的开方值。
  • L1更趋向于产生少量的特征,其它特征为0,最优的参数值很大概率出现在坐标轴上,从而导致产生稀疏的权重矩阵,而L2会选择更多的矩阵,但是这些矩阵趋向于0。

损失函数

  • 平方损失（预测问题）
  • 交叉熵（分类问题）
  • hinge损失（SVM支持向量机）
  • CART回归树的残差损失

0-1损失、平方损失、绝对损失以及对数损失

知道哪些损失函数？为什么分类问题不能用均方差？（这也是经典的题目，求导后发现预测值越接近label时返回的梯度越小，越难训练）

线性回归

表达式、损失函数、反向求导推导
线性回归y=wx+b，w和x可能是多维。线性回归的损失函数为平方损失函数。

降维

LDA是一种基于有监督学习的降维方式,将数据集在低维度的空间进行投影,要使得投影后的同类别的数据点间的距离尽可能的靠近,而不同类别间的数据点的距离尽可能的远。

A/B test如何进行流量分流

集成算法

XGBOOST和GDBT的区别

  • GDBT在函数空间中利用梯度下降法进行优化而XGB在函数空间中使用了牛顿法进行优化。即GDBT在优化中使用了一阶导数信息,而XGB对损失函数进行了二阶泰勒展开,用到了一阶和二阶倒数信息。
  • XGB在损失函数中加入了正则项(树叶子节点个数,每个叶子节点上输出score的L2模平方和。
  • 对于缺失的样本,XGB可以自动学习出它的分裂方向。GDBT的节点分裂方式使用的是gini系数,XGB通过优化推导出分裂前后的增益来选择分裂节点。
  • XGB在处理每个特征列时可以做到并行。

AdaBoost和GBDT的区别

  • AdaBoost通过调整错分的数据点的权重来改进模型,而GBDT是从负梯度的方向去拟合改进模型。
  • AdaBoost改变了训练数据的权值,即样本的概率分布,减少上一轮被正确分类的样本权值,提高被错误分类的样本权值,而随机森林在训练每棵树的时候,随机挑选部分训练集进行训练。在对新数据进行预测时,AdaBoost中所有树加权投票进行预测,每棵树的权重和错误率有关,而随机森林对所有树的结果按照少数服从多数的原则进行预测。

如何防止过拟合

模型权重减小，模型简单

  • 增加数据集，数据清洗，防止噪声干扰
  • 早停法
  • L1和L2正则化
  • 神经网络的dropout【在神经网络的训练过程中,对于神经单元按一定的概率将其随机从网络中丢弃,从而达到对于每个mini-batch都是在训练不同网络的效果,防止过拟合。】
  • BN
  • 决策树剪枝
  • SVM的松弛变量
  • 集成学习
  • 网络bagging

时间序列的数据集如何进行交叉验证

  • 预测后一半
  • 日向前链技术

嵌套交叉验证，有两种方式，分别是预测后一半、日前向链。
预测后一半嵌套交叉验证方法的一个缺陷是 hold-out 测试集的任意选择会导致在独立测试集上预测误差的有偏估计。（有系统误差）
日前向链技术：一种基于前向链（Forward-Chaining）的方法。
将最后几天的数据当做测试集，并将以前的所有数据分配到训练集中，然后训练计算误差，最后将误差求平均。

正负样本不平衡的解决方法，评价指标的参考意义

上下采样法
上采样就是以数据量多的一方的样本数量为标准，把样本数量较少的类的样本数量生成和样本数量多的一方相同，称为上采样。下采样与之相反。

好的指标：ROC和AUC、F值、G-Mean；不好的指标：Precision、Recall ？

数据不平衡的解决方法：

  • 使用正确的评估标准,当数据不平衡时可以采用精度,调用度,F1得分,MCC,AUC等评估指标。
  • 重新采样数据集,如欠采样和过采样。欠采样通过减少冗余类的大小来平衡数据集。当数据量不足时采用过采样,尝试通过增加稀有样本的数量来平衡数据集,通过使用重复,自举,SMOTE等方法生成新的样本。
  • 以正确的方式使用K-fold交叉验证,组合不同的重采样数据集,对多数类进行聚类。

softmax 公式

SGD,Momentum,Adagard,Adam原理

  1. SGD为随机梯度下降,每一次迭代计算数据集的mini-batch的梯度,然后对参数进行更新。
  2. Momentum参考了物理中动量的概念,前几次的梯度也会参与到当前的计算中,但是前几轮的梯度叠加在当前计算中会有一定的衰减。
  3. Adagard在训练的过程中可以自动变更学习的速率,设置一个全局的学习率,而实际的学习率与以往的参数模和的开方成反比。
  4. Adam利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率,在经过偏置的校正后,每一次迭代后的学习率都有个确定的范围,使得参数较为平稳。

L1不可导的时候该怎么办

当损失函数不可导,梯度下降不再有效,可以使用 坐标轴下降法,梯度下降是沿着当前点的负梯度方向进行参数更新,而坐标轴下降法是 沿着坐标轴的方向,假设有m个特征个数,坐标轴下降法进参数更新的时候,先固定m-1个值,然后再求另外一个的局部最优解,从而避免损失函数不可导问题。使用Proximal Algorithm对L1进行求解,此方法是去优化损失函数上界结果。

最大似然估计和最大后验概率的区别

  1. 最大似然估计提供了一种给定观察数据来评估模型参数的方法,而最大似然估计中的采样满足所有采样都是独立同分布的假设。
  2. 最大后验概率是根据经验数据获难以观察量的点估计,与最大似然估计最大的不同是最大后验概率融入了要估计量的先验分布在其中,所以最大后验概率可以看做规则化的最大似然估计。

评价指标

项目如何验证有效性，在业务中怎么用

F1-score :精准率和召回率的调和平均数

统计学中用来衡量二分类模型精确度的一种指标，兼顾了分类模型的精确率和召回率，
可以看做是模型精确率和召回率的一种调和平均。

F1 = 2 * precision* recall/ (precision + recall)

TP:实际为正，预测为正的样本数量
FP:实际为负，预测为正的样本数量
FN:实际为负，预测为负的样本数量
TN:实际为正，预测为负的样本数量

准确率： TP+FN/ TP+FP+FN+TN
精确度： 针对预测样本，计算我们预测出来的某类样本中，有多少是被正确预测的。
TP/TP+FP 预测为正的样本中实际上也是正的样本占被预测为正的样本的比例
召回率： 针对原先实际样本而言，有多少样本被正确的预测出来了。
TP/TP+FN 实际为正的样本中，预测也为正的样本占实际为正的样本的比例

Micro-F1和Macro-F1

微平均：第一种计算出所有类别总的Precision和Recall，然后计算F1。
宏平均：第二种方式是计算出每一个类的Precison和Recall后计算F1，最后将F1平均。

随机梯度下降