machine learning study notes interview

Machine Learning: 知识点汇总

面试各类问题知识点整理

Posted by Yingfan on May 4, 2022

1 基本概念

1.1 理解局部最优和全局最优

优化问题一般分为局部最优和全局最优。

（1）局部最优，就是在函数值空间的一个有限区域内寻找最小值；而全局最优，是在函数值空间整个区域寻找最小值问题

（2）函数局部最小点是它的函数值小于或等于附近点的点，但是有可能大于较远距离的点

（3）全局最小点是那种它的函数值小于或等于所有的可行点

1.2 各种常见算法

日常使用机器学习的任务中，我们经常会遇见各种算法：

  • 回归算法
  • 聚类算法
  • 正则化方法
  • 决策树学习
  • 贝叶斯方法
  • 基于核的算法
  • 降维算法
  • 集成算法
  • 关联规则学习
  • 人工神经网络，深度学习

2 机器学习学习方式

根据数据类型的不同，对一个问题的建模有不同的方式。依据不同的学习方式和输入数据，机器学习主要分为以下四种学习方式

2.1 监督学习

  • 定义
    • 监督学习是使用已知正确答案的示例来训练模型。已知数据和其一一对应的标签，训练一个预测模型，将输入数据映射到标签的过程
  • 应用场景
    • 分类问题
    • 回归问题
  • 算法举例
    • SVM, NB, LR, KNN, DT, RF, AdaBoost, LDA
    • 深度学习(Deep Learning)也是大多数以监督学习的方式呈现

2.2 非监督式学习

  • 定义
    • 在非监督式学习中，数据并不被特别标识，适用于具有数据集但无标签的情况。训练模型是为了推断出数据的一些内在结构。
  • 应用场景
    • 关联规则学习，聚类
  • 算法举例
    • Apriori, K-Means, DBSCAN

2.3 半监督式学习

  • 定义
    • 在此学习方式下，输入数据部分被标记，部分没有被标记，这种学习模型可以用来进行预测。
  • 应用场景
    • 应用场景包括分类和回归，算法包括一些对常用监督式学习算法的延伸，通过对已标记数据建模，在此基础上，对未标记数据进行预测
  • 算法举例
    • 图论推理算法（Graph Inference）
    • 拉普拉斯支持向量机（Laplacian SVM）

2.4 弱监督学习

  • 定义
    • 弱监督学习可以看做是有多个标记的数据集合，次集合可以是空集，单个元素，或包含多种情况（没有标记，有一个标记，和有多个标记）的多个元素。
    • 数据集的标签是不可靠的，这里的不可靠可以是标记不正确，多种标记，标记不充分，局部标记等。已知数据和其一一对应的弱标签，训练一个智能算法，将输入数据映射到一组更强的标签的过程。标签的强弱指的是标签蕴含的信息量的多少，比如相对于分割的标签来说，分类的标签就是弱标签。
  • 算法举例
    • 给出一张包含气球的图片，需要得出气球在图片中的位置及气球和背景的分割线， 这就是已知弱标签学习强标签的问题。

3 分类算法

3.1 常用分类算法的优缺点

算法 优点 缺点
Bayes贝叶斯分类    
Decision Tree    
SVM    
KNN    
NN    
AdaBoost    
     

3.2 分类算法的评估方法

分类评估方法主要功能是用来评估分类算法的好坏，而评估一个分类器算法的好坏又包括许多项指 标。了解各种评估方法，在实际应用中选择正确的评估方法是十分重要的。

  • 混淆矩阵

  • 评价指标

    1. 正确率（accuracy）

      $accuracy = (TP+TN)/(P+N)$，正确率是被分对的样本数在所有样本数中的占比，通常来说，正确率越高，分类器越好

    2. 错误率（error rate)

      描述被分类器错分的比例，对某一个实例来说，分对与分错是互斥事件，所以accuracy = 1 - error rate

    3. 召回率（recall）/ 灵敏度（sensitivity）

      sensitivity = TP/P，表示的是所有正例中被分对的比例，衡量了分类器对正例的识别能力

    4. 特异性（specificity)

      specificity = TN/N，表示的是所有负例中被分对的比例，衡量了分类器对负例的识别能力。

    5. 精度（precision）

      precision=TP/(TP+FP)，精度是精确性的度量，表示被分为正例的示例中实际为正例的比例。

    6. F1-score

      • $F1=\frac{2precision\times recall}{precision+recall}$
      • 为了综合多个类别的分类情况，经常采用的还有微平均F1（micro-averaging）和宏平均F1（macro-averaging ）两种指标
        • 宏平均F1与微平均F1是以两种不同的平均方式求的全局F1指标。
        • 宏平均F1的计算方法先对每个类别单独计算F1值，再取这些F1值的算术平均值作为全局指标。
        • 微平均F1的计算方法是先累加计算各个类别的a、b、c、d的值，再由这些值求出F1值。
        • 宏平均F1平等对待每一个类别，所以它的值主要受到稀有类别的影响
        • 而微平均F1平等考虑文档集中的每一个文档，所以它的值受到常见类别 的影响比较大。

    7. 其他评价指标

      • 计算速度：分类器训练和预测需要的时间；

      • 鲁棒性：处理缺失值和异常值的能力；

      • 可扩展性：处理大数据集的能力；

      • 可解释性：分类器的预测标准的可理解性，像决策树产生的规则就是很容易理解的，而神经网络的一堆参数就不好理解，我们只好把它看成一个黑盒子

  • ROC曲线和PR曲线

    • ROC曲线
      • 灵敏度（TPR）为纵坐标，以1减去特异性（FPR）为横坐标
      • ROC曲线越靠近左 上角，说明其对应模型越可靠
      • 当两个模型的ROC很接近，可以使用AUC来判断模型优劣
    • PR曲线
      • 描述的是precision和recall之间的关系，以recall为横坐 标，precision为纵坐标绘制的曲线
      • 该曲线的所对应的面积AUC实际上是目标检测中常用的评价指标平均精度（Average Precision, AP）。AP越高，说明模型性能越好

3 逻辑回归

3.1 什么是逻辑回归

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

  • 逻辑回归的基本假设是

    • 数据服从伯努利分布
    • 假设样本为正的概率是sigmoid function

  • 损失函数是

    • 极大似然函数 $L(\beta, x)=\prod_{i=1}^mh(x^i;\beta)^{y^i}\cdot (1-h(x^i;\beta))^{1-y^i}$
    • 其中$h(x^i;\beta)$是sigmoid function

    不使用最小二乘法是因为残差不符合正态分布，并且方差不同

  • 求解方法使用梯度下降

    • 批量梯度下降法BGD
      • 会获得全局最优解
      • 更新每个参数的时候需要遍历所有的数据，计算量会很大
    • 随机梯度下降法SGD
      • 每次迭代随机选择一个样本计算梯度
      • 可以处理更大量的数据
      • 有可能无法找到最优解
    • 小批量梯度下降法MBGD
      • 结合了sgd和batch gd的优点，每次更新的时候使用n个样本
      • 减少了参数更新的次数，可以达到更加稳定收敛结果

3.2 逻辑回归适用性

逻辑回归可用于以下几个方面：

（1）用于概率预测。用于可能性预测时，得到的结果有可比性。比如根据模型进而预测在不同的自变量 情况下，发生某病或某种情况的概率有多大。

（2）用于分类。实际上跟预测有些类似，也是根据模型，判断某人属于某病或属于某种情况的概率有多 大，也就是看一下这个人有多大的可能性是属于某病。进行分类时，仅需要设定一个阈值即可，可能性 高于阈值是一类，低于阈值是另一类。

（3）仅能用于线性问题。只有当目标和特征是线性关系时，才能用逻辑回归。

3.3 逻辑回归的优缺点

  • 优点
    • 可解释性：形式简单，模型的可解释性非常好
    • 模型效果不错。在工程上是可以接受的（作为baseline)
    • 速度：训练速度较快。分类的时候，计算量仅仅只和特征的数目相关。
    • 方便调整输出结果，设置不同的阈值进行分类
  • 缺点
    • 只能进行划分线性问题
    • 很难处理数据不平衡的问题
    • 逻辑回归本身无法筛选特征。有时候，我们会用gbdt来筛选特征，然后进行逻辑回归

3.4 逻辑回归与朴素贝叶斯的区别

逻辑回归与朴素贝叶斯区别有以下几个方面：

（1）逻辑回归是判别模型， 朴素贝叶斯是生成模型

（2）朴素贝叶斯属于贝叶斯，逻辑回归是最大似然，分属于两种概率哲学

（3）朴素贝叶斯需要条件独立假设。

（4）逻辑回归需要求特征参数间是线性的

4 决策树

4.1 决策树的基本原理

  • 决策树（Decision Tree）是一种分而治之的决策过程
  • 它将一个困难的预测问题，通过树的分支节点划分为两个或多个较为简单的子问题
  • 将依规则分割数据集的过程不断递归下去，随着树的深度不断增加，分支节点的子集越来越小，所需要提的问题也逐渐简化
  • 当分支节点的深度或者问题的简单程度满足一定的停止规则，该分支节点会停止分裂

4.2 决策树的三要素是什么

一棵决策树的生成过程主要分为下3个部分：

  1. 特征选择：从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着 很多不同量化评估标准，从而衍生出不同的决策树算法。
  2. 决策树生成：根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则决策树停止生长。
  3. 剪枝：决策树容易过拟合，一般来需要剪枝，缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。

4.3 选择最优划分属性的办法

一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”（purity）越来越高。下面列出了几种衡量纯度的指标。

  • 信息增益（information gain）
    • 特征A对训练数据集D的信息增益定义为D的信息熵与A条件下的条件熵之差
    • 当D只含有一种类型时信息熵为0
    • ID3算法使用此指标作为选择特征的标准
    • 信息增益准则偏向于选择取值较多的特征
  • 信息增益比（gain ratio）
    • 特征A对训练数据集D的信息增益率定义为其信息增益与数据集D关于特征A的取值的熵之比
    • 增益率准则对取值较少的属性有所偏好
    • C4.5算法使用信息增益比，首先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的特征进行划分
  • 基尼系数（Gini index）
    • $G_i=1-\sum_k^np_{i,k}^2$是节点$i$的基尼系数, 其中$p_{i,k}$是节点$i$中第$k$类样本的比例
    • 基尼系数越小，则纯度越高
    • 在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性
    • CART做分类问题时使用基尼系数作为划分标准

4.4 决策树优缺点

  • 优点
    • 易理解，机理解释起来简单
    • 可以用于小数据集。
    • 不需要特征标准化
    • 对缺失值不敏感
  • 缺点
    • 容易过拟合
    • 不稳定性：对于数据集旋转，小的变动非常敏感（因为决策边界都是正交的）
      • RF可以通过平均多棵树的结果来解决不稳定性
    • 对于各类别样本数量不一致的数据，在决策树当中，信息增益的结果偏向于那些具有更多数值的特征

4.5 CART算法的训练过程

  1. 首先寻找阈值$t_k$和特征$k$将训练集划分为两个子集，组合$(k,t_k)$需要最小化损失函数$J(k,t_k)=\frac{m_{left}}{m}G_{left}+\frac{m_{right}}{m}G_{right}$
  2. 然后迭代这个分裂过程，直到数据集不可分或当分支节点的深度或者问题的简单程度满足一定的停止规则，该分支节点会停止分裂

当使用CART解决回归问题时，将$G_{left}$替换为$MSE_{left}$

4.6 决策树剪枝

剪枝处理是决策树学习算法用来解决过拟合问题的一种办法。在决策树算法中，为了尽可能正确分类训练样本， 节点划分过程不断重复， 有时候会造成决策树分支过多，因此可以采用剪枝处理来去掉一些分支来降低过拟合的风险。

剪枝的基本策略有预剪枝（pre-pruning）和后剪枝（post-pruning）

  • 预剪枝
    • 在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。
    • 优点
      • 降低了过拟合的风险。
      • 减少了决策树的训练时间开销和测试时间开销
    • 缺点
      • 有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高。因此预剪枝会有欠拟合的风险。
  • 后剪枝
    • 先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
    • 优点
      • 欠拟合风险很小。
      • 泛化性能往往优于预剪枝决策树。
    • 缺点
      • 后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

5 支持向量机

5.1 什么是支持向量机

  • 支持向量机是一种二分类模型，目的是寻找一个超平面对样本进行分割，分割的原则是边界最大化。
    • 通俗解释：通过模型在两个类别之间拟合一条尽可能宽的街道将样本分割
  • 支持向量
    • 位于分割边界边缘的样本
    • 这些样本完全决定了SVM的边界
  • 支持向量机的种类
    • 当训练样本线性可分时，通过硬边界（hard margin）最大化，学习一个线性支持向量机；
    • 当训练样本近似线性可分时，通过软边界（soft margin）最大化，学习一个线性支持向量机；
    • 当训练样本线性不可分时，通过核技巧和软边界最大化，学习一个非线性支持向量机；

5.2 支持向量机能解决哪些问题

  • 线性分类
    • 在训练数据中，每个数据都有n个属性和一个二分类类别标志，我们可以认为这些数据在一个n维空 间里。我们的目标是找到一个n-1维的超平面，这个超平面可以将数据分成两部分，每部分数据都属于同 一个类别。
  • 非线性分类
    • SVM的一个优势是支持非线性分类。它结合使用拉格朗日乘子法（Lagrange Multiplier）和KKT（Karush Kuhn Tucker）条件，以及核函数可以生成非线性分类器。

5.3 核函数特点及其作用

引入核函数目的：把原坐标系里线性不可分的数据用核函数投影到另一个空间，尽量使得数据在新的空间里线性可分

核函数的特点：

  • 核函数的引入避免了“维数灾难”，大大减小了计算量。
    • 输入空间的维数n对核函数矩阵无影响。因此，核函数方法可以有效处理高维输入
  • 核函数方法可以和不同的算法相结合，形成多种不同的基于核函数技术的方法，且这两部分的设计可 以单独进行，并可以为不同的应用选择不同的核函数和算法

5.4 核函数的种类

  • 线性核
  • 多项式核

  • 指数核

  • 高斯核
    • 首先定义相似函数为Gaussian Radial Basis Function (RBF)
    • 其次选取一些样本点作为基准
    • 计算每个样本点和基准点的相似度（内积）作为新的特征
  • 拉普拉斯核
  • ANOVA核
  • sigmoid核

5.5 SVM的主要特点

  1. SVM的最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了“维数灾难“
  2. 少数支持向量决定了最终结果，这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本,而且注定 了该方法不但算法简单，而且具有较好的“鲁棒性”。这种鲁棒性主要体现在
    • 增、删非支持向量样本对模型没有影响
    • 支持向量样本集具有一定的鲁棒性;
    • 有些成功的应用中，SVM方法对核的选取不敏感
  3. 适用于小样本
  4. SVM学习问题可以表示为凸优化问题，因此可以利用已知的有效算法发现目标函数的全局最小值

5.6 SVM主要缺点

  1. SVM算法对大规模训练样本难以实施
  2. 用SVM解决多分类问题存在困难
    • 可以使用多个二类支持向量机的组合解决，如OvO, OvR
  3. 对缺失数据敏感，对参数和核函数的选择敏感

5.7 逻辑回归与SVM的比较

相同点

  • 分类，有监督学习
  • 线性分类算法（当SVM使用线性核）

不同点

  • 逻辑回归使用log loss，SVM使用hinge loss

  • LR对异常值敏感，SVM对异常值不敏感

    • 在支持向量机中改变非支持向量样本并不会引起决策面的变化
    • 逻辑回归中改变任何样本都会引起决策面的变化

  • 计算复杂度不同。对于海量数据，SVM的效率较低，LR效率比较高

6 贝叶斯分类器

6.1 贝叶斯分类器基本原理

贝叶斯决策论通过相关概率已知的情况下利用误判损失来选择最优的类别分类。 假设有N种可能的分类标记，记为$Y={c_1,c_2,…,c_N}$，计算步骤如下：

  1. 算出样本$x$属于第$i$个类的概率，即$P(c_i x)$
  2. 比较所有的$P(c_i x)$, 得到样本$x$所属的最佳类别，注意，这里只需要比较最大的P$(x c_i)$即可
    \[P(c_i|x)=\frac{P(x|c_i)P(c_i)}{P(x)}\]

6.2 朴素贝叶斯分类器

假设样本$x$包含$d$个特征，即$x={x_1,x_2,…,x_d}$，目标为求解$P(c_i x)=P(c_i x1,x2,…x_d)$. 而$x_1,x_2,…,x_d$的联合概率难以计算

朴素贝叶斯采用“属性条件独立性假设”：对已知类别，假设所有属性相互独立，则有

$P(c_i x)=\frac{\prod_{j=1}^d P(x_j c_i)P(c_i)}{\prod_{j=1}^d P(x_j c_i)}$

只需要比较分子部分，概率最大的$c_i$就是所属类别

7 降维和聚类

7.1 维数灾祸问题

当增加特征数量且样本量一定时，高维样本空间的样本密度会越来越稀疏，这种分布的稀疏性会带来以下问题：

  1. 模型参数难以正确估计。样本不够时，得出的决策边界往往是过拟合的，尤其是对于那些具有非线性决策边界的分类器（如：神经网络，决策树，KNN）来说，如果样本不够多时，往往很容易过拟合。
  2. 样本分布位于中心附近的概率，随着维度的增加，越来越低；而样本处在边缘的概率，则越来越高。这种情况下，一些度量相异性的距离指标（如：欧式距离）效果会大大折扣，从而导致一些基于这些指标的分类器在高维度的时候表现不好。

7.2 降维的方法有哪些

  • PCA, kernel PCA, Randomized PCA, Incremental PCA
  • Locally Linear Embedding
  • Multidimensional Scaling (MDS)
  • Isomap
  • t-Distributed Stochastic Neighbor Embedding (t-SNE)
  • Linear Discriminant Analysis (LDA)

7.3 聚类算法衡量标准

不同聚类算法有不同的优劣和不同的适用条件。可从以下方面进行衡量判断：

1、算法的处理能力：处理大的数据集的能力，即算法复杂度；处理数据噪声的能力；处理任意形状， 包括有间隙的嵌套的数据的能力；

2、算法是否需要预设条件：是否需要预先知道聚类个数，是否需要用户给出领域知识；

3、算法的数据输入属性：算法处理的结果与数据输入的顺序是否相关，也就是说算法是否独立于数据输入顺序；算法处理有很多属性数据的能力，也就是对数据维数是否敏感，对数据的类型有无要求。

7.4 常见聚类算法

K-means及其变种讲解、DBSCAN

层次聚类法

根据层次分解的顺序是自底向上的还是自上向下的，层次聚类算法分为凝聚的层次聚类算法和分裂的层次聚类算法。

凝聚型层次聚类的策略是先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有 对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类，它们只是在簇 间相似度的定义上有所不同

算法流程

SOM(Self-organizing map)聚类算法

8 模型评估

9 线性判别分析(Linear Discriminant Analysis)

9.1 LDA思想总结

LDA是一种有监督学习的降维技术，数据集的每个样本有类别 输出。分类思想总结如下：

  1. 多维空间中，数据处理分类问题较为复杂，LDA算法将多维空间中的数据投影到一条直线上，将d 维数据转化成1维数据进行处理。
  2. 对于训练数据，设法将多维数据投影到一条直线上，同类数据的投影点尽可能接近，异类数据点尽 可能远离
  3. 对数据进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定样本的类别。

LDA的主要思想可以总结为：投影后类内方差最小，类间方差最大

10 损失函数

CATALOG
    FEATURED TAGS
    sql lecture notes machine learning model interview study notes neural network data analysis
    FRIENDS