经典机器学习算法

概述

经典机器学习算法是人工智能领域的基础，涵盖了从线性模型到集成学习的多种方法。这些算法在实际应用中仍然广泛使用，是面试中考察基础知识的重点。本文整理了最常考的十大经典机器学习算法：线性回归、逻辑回归、SVM、决策树、随机森林、GBDT、XGBoost、LightGBM、K-Means和KNN。

核心原理

线性回归

线性回归是利用线性函数对自变量和因变量之间关系进行建模的一种回归分析方法。

• 原理：用线性函数拟合数据，通过最小化均方误差(MSE)寻找最优参数
• 损失函数：均方误差(MSE)
• 求解方法：
  • 梯度下降法（批量梯度下降BGD、小批量梯度下降MBGD、随机梯度下降SGD）
  • 最小二乘法（正规方程）
• 特点：对异常值非常敏感；简单易于理解；计算速度快

常见问题：

• 为什么线性回归使用均方误差作为损失函数？ 从概率角度，如果假设误差服从高斯分布，通过极大似然估计可以推导出均方误差。

• 梯度下降法和最小二乘法的比较：

逻辑回归 (LR)

逻辑回归虽然名字叫回归，实际上是经典的二分类算法。

• 本质：极大似然估计
• 激活函数：Sigmoid
• 损失函数：交叉熵损失
• 优点：
  • 速度快，适合二分类问题
  • 简单易于理解，直接看到各个特征的权重
  • 能容易地更新模型吸收新的数据
  • 输出可以表示为概率，方便后续处理
• 缺点：对数据和场景的适应能力有限，不如决策树算法适应性强

核心问题：

• 为什么LR使用sigmoid函数？

  1. 广义线性模型推导所得
  2. 满足统计的最大熵模型
  3. 性质优秀，任意阶可导，计算方便

• 为什么LR用交叉熵损失而不是均方误差？ 如果使用均方误差，梯度会受到sigmoid导数的影响，在饱和区梯度非常小，导致学习速度慢。而交叉熵损失的梯度不包含sigmoid导数，预测误差越大，参数更新越快，训练更高效。

• LR如何解决多分类问题？

  • OvR (One-vs-Rest)：对每个类别训练一个二分类器
  • OvO (One-vs-One)：每两个类别训练一个二分类器

支持向量机 (SVM)

支持向量机通过寻找最大间隔超平面来进行分类。

• 核心思想：间隔最大化，转化为凸二次优化问题

• 三种SVM：

  1. 线性可分SVM：硬间隔最大化
  2. 线性SVM：软间隔最大化，处理近似线性可分情况
  3. 非线性SVM：核技巧 + 软间隔最大化

• 核函数：将低维空间线性不可分数据映射到高维空间变得线性可分

  • 线性核：适合线性可分情况
  • 多项式核
  • 高斯核(RBF)：最常用，适合非线性情况
  • Sigmoid核

关键问题：

• 为什么SVM要引入对偶问题？

  1. 对偶问题更容易求解
  2. 自然引入核函数，方便推广到非线性情况

• SVM对缺失数据敏感吗？ 是的，SVM对缺失数据敏感，因为核函数计算依赖于特征空间的距离计算。

• LR vs SVM：

决策树

决策树是一种树结构的分类/回归模型，通过递归选择最优特征进行划分。

• 三种经典算法：

  • ID3：基于信息增益选择特征，偏向于取值多的特征
  • C4.5：使用信息增益率，解决ID3偏向问题，支持连续特征，能够剪枝
  • CART：使用基尼指数，二叉树，既可以分类也可以回归

• 纯度度量：

  • 信息熵：$H(T) = -\sum_i p_i \log_2 p_i$
  • 基尼指数：$Gini = \sum p_i(1-p_i) = 1 - \sum p_i^2$
  • 错误率

• 剪枝：

  • 预剪枝：在构建过程中提前停止，控制树的复杂度
  • 后剪枝：生成完全树后自下而上剪枝，泛化性能更好

• 优点：

  • 模型可读性好，具有可解释性
  • 效率高，只需要一次构建，预测快速

• 缺点：

  • 容易过拟合，泛化能力差
  • 对缺失值敏感
  • ID3偏向取值多的特征

K近邻 (KNN)

KNN是基于实例的学习，通过距离找到最近的K个样本投票预测。

• 原理：一个样本在特征空间中，如果与其最近的k个样本中的大多数属于某个类别，则该样本也属于这个类别。
• 距离度量：
  • 欧氏距离：最常用
  • 曼哈顿距离：L1距离
  • 闵可夫斯基距离：广义形式

关键问题：

• 为什么用欧氏距离而不是曼哈顿距离？ 曼哈顿距离只计算水平或垂直距离，有维度限制；欧氏距离可用于任何空间的距离计算，更适合高维空间中的距离计算。

• K值选择：

  • K太小：容易过拟合，对噪声敏感
  • K太大：容易欠拟合，边界模糊
  • 通过交叉验证选择最优K值

• 优缺点：

  • 优点：简单直观，对数据没有假设，精度高
  • 缺点：计算量大，每预测一个样本都要计算与所有训练样本的距离；样本不平衡时预测偏差大

K-Means聚类

K-Means是最经典的无监督聚类算法。

• 算法流程：

  1. 随机选择k个初始聚类中心
  2. 计算每个样本到各个中心的距离，分配到最近的簇
  3. 重新计算每个簇的中心（均值）
  4. 重复2-3直到收敛

• K-means++优化：初始聚类中心之间的相互距离要尽可能远：

  1. 随机选第一个中心
  2. 计算每个点到已选中心的最短距离D(x)，D(x)越大被选中为新中心的概率越大
  3. 重复直到选出k个中心
  4. 标准K-means迭代

• 时间复杂度：O(tKmn)，t迭代次数，K簇数，m样本数，n维数

• 优缺点：

  • 优点：算法简单，收敛快
  • 缺点：需要预先指定K值，对初始中心敏感，容易陷入局部最优，对离群点敏感

集成学习：Bagging vs Boosting

Bagging：并行训练多个基学习器，然后投票/平均

• 代表：随机森林(Random Forest)
• 特点：降低方差，减少过拟合

Boosting：串行训练，每一轮根据上一轮结果调整样本权重，最终加权组合

• 代表：AdaBoost、GBDT、XGBoost、LightGBM
• 特点：降低偏差，提升精度

随机森林 (RF)

随机森林是Bagging的扩展，在样本随机采样基础上，增加了特征随机选择。

• 特点：

  • 随机性：样本有放回采样，特征随机选择
  • 每棵树独立训练，最终投票

• 特征重要性评估：

  1. Decrease GINI：节点分裂时GINI指数减少量
  2. Decrease Accuracy：OOB打乱特征顺序后精度下降幅度

• 处理缺失值：

  • 简单方法：分类变量用众数填充，连续变量用中位数填充
  • 复杂方法：rfImpute迭代填充

• 优点：

  • 抗过拟合能力强，泛化性能好
  • 可以处理高维数据，不需要降维
  • 能够输出特征重要性
  • 训练速度快，支持并行

GBDT (梯度提升决策树)

梯度提升决策树通过迭代多棵树，每棵树学习之前所有树的残差。

• 核心思想：每次拟合负梯度（残差），逐步减少损失
• 与XGBoost的区别：

  对比项	GBDT	XGBoost
  损失函数	只用一阶导数	泰勒展开，使用一二阶导数
  正则化	无显式正则	加入L1/L2正则，控制模型复杂度
  分裂标准	基尼系数	基于二阶导数计算增益
  缺失值处理	需要手动处理	自动学习分裂方向

XGBoost

XGBoost是GBDT的高效实现，工程优化和正则化改进。

• 核心改进：

  1. 泰勒展开损失函数，使用一二阶导数，更精确
  2. 显式加入正则化项（L1/L2），控制模型复杂度，防止过拟合
  3. 支持并行处理（特征粒度并行）
  4. 自动处理缺失值
  5. 列抽样（类似随机森林），防止过拟合，减少计算

• 为什么用泰勒展开？ 去耦合了损失函数选择和优化算法，使得XGBoost可以支持自定义损失函数，只要能求出一二阶导数即可。

• 优点：精度高，正则化防止过拟合，速度快，支持并行

LightGBM

LightGBM是XGBoost的改进版，更快更省内存。

• 核心改进：

  1. 基于梯度的单边采样(GOSS)：保留大梯度样本，对小梯度样本采样，减少计算
  2. 互斥特征绑定(EFB)：将互斥的多个特征绑定为一个特征，降维
  3. 叶子生长策略：按叶子分裂而非按层分裂，减少误差，速度更快
  4. 支持类别特征，不需要One-hot编码

• XGBoost vs LightGBM：

面试常见问题

1. **LR和线性回归的区别与联系？

   • 联系：都属于广义线性模型，LR基于线性回归，用sigmoid映射到0-1概率
   • 区别：
     • 线性回归用于回归问题，LR用于分类问题
     • 线性回归用均方误差损失，LR用交叉熵损失
     • 线性回归输出是实数范围，LR输出在[0,1]表示概率
   • LR为什么比线性回归好？对于分类问题，LR将输出限定在[0,1]，鲁棒性更好。

2. **L1和L2正则化的区别？L1为什么能产生稀疏性？

   • L1是参数绝对值之和，L2是参数平方和
   • L1可以产生稀疏解，用于特征选择；L2防止过拟合，提升泛化能力
   • L1产生稀疏性原因：在最优解附近，L1在0点处不可导，最优解更容易落到0点，使很多参数变为0，得到稀疏解。

3. **决策树如何防止过拟合？

   • 预剪枝：限制树深度、限制叶子节点最少样本数、设置熵/基尼阈值提前停止
   • 后剪枝：生成完全树后自下而上剪枝
   • 交叉验证选择最优复杂度
   • 集成方法（随机森林）降低过拟合风险

4. **为什么XGBoost要用泰勒展开，优势在哪里？ XGBoost使用一阶和二阶偏导，二阶导数有利于梯度下降更快更准。使用泰勒展开可以在不选定损失函数具体形式的情况下进行优化分析，本质上把损失函数选取和模型优化参数选择分开，增加了XGBoost的适用性，支持自定义损失函数。

5. **XGBoost如何处理缺失值？ XGBoost在训练时，自动学习缺失值的分裂方向。对于每个树节点，算法会尝试把缺失值分到左子树和右子树，选择分裂增益更大的方向，这样在预测时遇到缺失值就按学习到的方向分裂。

6. **LightGBM的GOSS和EFB是什么？

   • GOSS（Gradient-based One-Side Sampling）：保留梯度大的样本，对梯度小的样本随机采样，通过权重调整保证数据分布不变，减少计算量
   • EFB（Exclusive Feature Bundling）：将互斥的多个特征捆绑成一个特征，减少特征数量，降维加速

7. **生成模型和判别模型的区别？举例说明

   • 生成模型：学习联合概率分布P(X,Y)，然后求后验概率P(Y|X)。例子：朴素贝叶斯、隐马尔可夫模型、高斯混合模型。
   • 判别模型：直接学习决策函数Y=f(X)或条件概率P(Y|X)。例子：KNN、SVM、决策树、LR、boosting、条件随机场。
   • 由生成模型可以得到判别模型，但由判别模型得不到生成模型。

8. **哪些机器学习算法不需要做归一化处理？为什么？

   • 不需要归一化：决策树、随机森林、GBDT、XGBoost、LightGBM
   • 原因：树形结构不关心变量的值，只关心变量分布和条件概率，样本数值缩放不影响分裂点位置，不影响树结构。且树模型是阶跃的，不需要梯度下降，不需要归一化。
   • 需要归一化：线性回归、LR、KNN、SVM、神经网络、KMeans
   • 原因：基于距离计算或梯度下降，特征量级差异大会影响目标函数优化，归一化后加速收敛。

9. **KMeans中，K的选择方法？

   • 肘部法则：画SSE（误差平方和）随K变化曲线，选择肘部位置
   • 轮廓系数：计算平均轮廓系数，选择较大值对应的K
   • 业务需求：根据实际应用场景人为指定K

10. **LR和SVM的联系与区别？

    • 联系：都处理分类问题，都可以加正则化，都是线性分类器
    • 区别：
      • LR是参数模型，SVM是非参数模型
      • 损失函数不同：LR用交叉熵，SVM用hinge损失
      • SVM只考虑支持向量，LR考虑所有样本
      • LR输出概率可解释，SVM输出不是天然概率
      • LR更简单，大规模数据训练更快；SVM用核函数可以处理非线性问题