VC' Blog
0%

常见机器学习算法的优缺点

Posted on Edited on In Valine:

想要寻找一个合适的算法不容易，实际应用中，我们一般采用启发式实验。

没有免费的午餐定理 (NFL)：核心在于，假设了所有问题出现的机会相同，或所有问题同等重要。当需求是解决一切问题时，“哪个算法更好”就毫无意义。HG2G 中“深思”面对“宇宙、生命以及一切的中继答案是什么？”这样一个问题，用最复杂的算法算出一个 42 和随便说一个 42 是一样的。

偏差与方差

  • 偏差：描述的是估计值的期望 E 与真实值 Y 之间的差距。偏差越大，越偏离真实数据。
  • 方差：描述的是预测值的离散程度，方差越大，数据分布约分散。
  • 模型的真实误差可以看成 bias2+var+σ2bias^2 + var + \sigma^2，其中 σ2\sigma^2 是噪音

偏差与方差窘境：

  • 学得不好，偏差大
  • 学得好，敏感性高，方差大。

通常情况下

  • 小训练集，高偏差/低方差的分类器（例如，朴素贝叶斯 NB）要比低偏差/高方差大分类的优势大（例如，KNN），因为后者会发生过拟合（overfitting）。
  • 随着训练集增长，此时低偏差/高方差的分类器在训练集上性能变好，偏差降低，就会渐渐的表现其优势（因为它们有较低的渐近误差），而高偏差分类器的偏差难以下降。

特征选择：最小冗余/最大相关（Minimum Redundancy Maximum Relevance， mRMR）

常见算法的优缺点

朴素贝叶斯 Naive Bayes classifier

朴素贝叶斯假设数据之间是无关的，严重简化了模型。对于这样一个简单没顶，大部分时候表现出高偏差，低方差。

属于生成式模型，收敛速度快于判别式模型

优点：

  • 有坚实的数学理论基础，易解释，分类效率稳定，计算速度快
  • 小规模数据表现好，能处理多分类任务，适合增量式训练
  • 对缺失数据不敏感，常用于文本分类

缺点：

  • 需要计算先验概率
  • 使用了“属性条件独立性假设”，当属性之间有关联时效果较差
  • 对输入数据的表达形式敏感

应用领域：

  • 欺诈检测
  • 文本分类
  • 人脸识别

逻辑回归 Logistic Regression

属于判别式模型，常和很多模型正则化方法（L0[1]，L1，L2）。能使用在线梯度下降法更新模型。

优点：

  • 实现简单，计算量小
  • 有概率解释
  • 能通过 L2 正则化解决多重共线性问题

缺点：

  • 特征空间很大时，性能不好
  • 容易欠拟合，一般准确性不高
  • 不能很好地处理大量分类特征
  • 只能处理线性二分类问题（多分类使用 softmax）

应用领域：

  • 适用于根据概率排名的应用，如搜索排名

线性回归

Normal Equation 优化结果：

ω^=(XTX)−1XTy\hat{\omega} = (X^TX)^{-1}X^Ty

局部加权线性回归（LWLR）优化结果：

ω^=(XTWX)−1XTWywij=exp((xi−xj)22k2)\begin{gathered} \hat{\omega} = (X^T W X)^{-1} X^T W y \\ w_{ij} = exp\left(\frac{(x_i - x_j)^2}{2k^2}\right) \end{gathered}

LWLR 是非参数模型，每次进行回归计算都需要遍历训练样本。

优点：实现简单，计算简单

缺点：不能拟合非线性关系

KNN

关键在于 K 值的选择，K 值较大能够减少噪声的影响，但会使类别之间的界限变模糊。噪声和非相关性特征向量的存在会使 K 近邻算法的准确性减小。数据密度很大时，KNN 的泛化错误率不会超过贝叶斯最优分类器错误率的两倍。

优点：

  • 思路简单，可分类，可回归
  • 可用于非线性分类
  • 对数据没有假设，对离群点不敏感
  • 惰性学习，新增数据无需重新训练

缺点：

  • 样本不平衡时效果差，bias 大
  • 需要大量内存
  • 预测时需要全局计算，计算量大

应用领域：

  • 文本分类
  • 模式识别
  • 多分类

决策树

优点：

  • 易于解释，可以可视化，容易提取规则
  • 可以同时处理连续变量和分类变量
  • 对属性缺失不敏感

缺点：

  • 容易过拟合（通过随机森林减轻）

  • 容易忽略数据集中属性的相互关联

  • 样本不平衡的情况下，进行属性划分时，不同的判定准则有不同的属性选择倾向；

    • 信息增益准则对可取数目较多的属性有所偏好（典型代表 ID3 算法）
    • 增益率准则（CART）则对可取数目较少的属性有所偏好，CART 进行属性划分时候不再简单地直接利用增益率进行划分，而是采用一种启发式规则
    • 只要是使用了信息增益，都有这个缺点，如 RF

应用领域：

  • 决策类

SVM

优点：

  • 可以解决高维问题，即特征空间很大的问题
  • 小样本下也有不错的表现
  • 能处理非线性特征的相互作用（利用核函数）
  • 无局部最小值问题（相对于神经网络）
  • 不依赖所有数据
  • 泛化能力强

缺点：

  • 当观测样本很多，效率不高
  • 对非线性问题没有通用解决方案，很难找到一个合适的核函数
  • 对核函数的高维映射解释力不强，尤其是高斯核
  • 对缺失数据敏感

核函数的选择：libsvm 中自带了四种核函数：线性核、多项式核、RBF 以及 sigmoid 核

  • 如果样本数量小于特征数，那么就没必要选择非线性核，简单的使用线性核就可以了；
  • 如果样本数量大于特征数目，这时可以使用非线性核，将样本映射到更高维度，一般可以得到更好的结果；
  • 如果样本数目和特征数目相等，该情况可以使用非线性核，原理和第二种一样

应用：

  • 文本分类
  • 图像分类

人工神经网络

优点：

  • 分类的准确度高；
  • 并行分布处理能力强，分布存储及学习能力强，
  • 对噪声神经有较强的鲁棒性和容错能力；
  • 具备联想记忆的功能，能充分逼近复杂的非线性关系

缺点：

  • 神经网络需要大量的参数，如网络拓扑结构、权值和阈值的初始值；
  • 黑盒过程，不能观察之间的学习过程，输出结果难以解释，会影响到结果的可信度和可接受程度；
  • 学习时间过长，有可能陷入局部极小值，甚至可能达不到学习的目的。

K-Means 聚类

优点

  • 算法简单，容易实现 ，算法速度很快；
  • 对处理大数据集，该算法是相对可伸缩的和高效率的，因为它的复杂度大约是 O(nkt)，其中 n 是所有对象的数目，k 是簇的数目，t 是迭代的次数。通常 k << n，这个算法通常局部收敛。
  • 算法尝试找出使平方误差函数值最小的 k 个划分。当簇是密集的、球状或团状的，且簇与簇之间区别明显时，聚类效果较好。

缺点

  • 对数据类型要求较高，适合数值型数据；
  • 可能收敛到局部最小值，在大规模数据上收敛较慢
  • 分组的数目 k 是一个输入参数，不合适的 k 可能返回较差的结果。
  • 对初始的簇心值敏感
  • 不适合于发现非凸面形状的簇，或者大小差别很大的簇
  • 对于”噪声”和孤立点数据敏感

EM 最大期望算法

EM 算法是基于模型的聚类方法，是在概率模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量。E 步估计隐含变量，M 步估计其他参数，交替将极值推向最大。

  • EM 算法比 K-means 算法计算复杂，收敛也较慢，不适于大规模数据集和高维数据，

  • 比 K-means 算法计算结果稳定、准确。

应用：

  • 机器学习和计算机视觉的数据集聚（Data Clustering）

AdaBoost

一种经典的 boosting 算法，每个模型都是基于上一次模型的错误率来建立的，增加错误分类样本的权重，而对正确分类的样本减少关注度，逐次迭代之后，可以得到一个相对较好的模型。

优点：

  • 精度高
  • 可以使用各种方法构建子分类器，Adaboost 提供的是框架
  • 当使用简单分类器时，计算结果可以理解
  • 不需要特征筛选，不易 overfitting
  • 相对于 bagging 算法和 RF，AdaBoost 充分考虑了每个分类器的权重

缺点：

  • 对 outlier 敏感，对样本平衡性敏感
  • 迭代次数不易确定

Adaboost, GBDT 及 XGBoost 比较

关联规则算法

Apriori 算法是一种挖掘关联规则的算法，用于挖掘其内含的、未知的却又实际存在的数据关系。

常用的频繁项集的评估标准有支持度，置信度和提升度三个。

支持度就是几个关联的数据在数据集中出现的次数占总数据集的比重。或者说几个数据关联出现的概率。如果我们有两个想分析关联性的数据 X 和 Y，则对应的支持度为：

Support(X,Y)=P(XY)=number(XY)num(AllSamples)Support(X,Y)=P(XY)=\frac{number(XY)}{num(AllSamples)}

置信度体现了一个数据出现后，另一个数据出现的概率，或者说数据的条件概率。如果我们有两个想分析关联性的数据 X 和 Y，X 对 Y 的置信度为

Confidence(X⇐Y)=P(X∣Y)=P(XY)/P(Y)Confidence(X \Leftarrow Y)=P(X|Y)=P(XY)/P(Y)

提升度表示含有 Y 的条件下，同时含有 X 的概率，与 X 总体发生的概率之比，即：

Lift(X⇐Y)=P(X∣Y)/P(X)=Confidence(X⇐Y)/P(X)Lift(X \Leftarrow Y) = P(X|Y)/P(X) = Confidence(X \Leftarrow Y)/P(X)

提升度体先了 X 和 Y 之间的关联关系，提升度大于 1 则X⇐YX \Leftarrow Y是有效的强关联规则， 提升度小于等于 1 则X⇐YX \Leftarrow Y是无效的强关联规则 。一个特殊的情况，如果 X 和 Y 独立，则有Lift(X⇐Y)=1Lift(X⇐Y)=1，因为此时P(X∣Y)=P(X)P(X|Y)=P(X)

learn more

算法选择参考

一个简单的算法选择技巧：

  1. x 先逻辑回归，如果它的效果不怎么样，那么可以将它的结果作为基准来参考，在基础上与其他算法进行比较；
  2. 然后试试决策树（随机森林）看看是否可以大幅度提升你的模型性能。即便最后你并没有把它当做为最终模型，你也可以使用随机森林来移除噪声变量，做特征选择；
  3. 如果特征的数量和观测样本特别多，那么当资源和时间充足时（这个前提很重要），使用 SVM 不失为一种选择。

通常情况下：GBDT >= SVM >= RF >= Adaboost >= Other

算法固然重要，但好的数据却要优于好的算法，设计优良特征是大有裨益的。假如你有一个超大数据集，那么无论你使用哪种算法可能对分类性能都没太大影响（此时就可以根据速度和易用性来进行抉择）。

  1. L0 正则化的值是模型参数中非零参数的个数 ↩︎