机器学习经典算法优缺点总结

简介
机器学习大多数场景是搜索、广告、垃圾过滤、安全、推荐系统等等。本文是经典机器学习算法的优劣势比较,欢迎纠正。

朴素贝叶斯

生成模型贝叶斯定理特征条件独立后验概率最大化

原理

基于贝叶斯定理与特征条件独立假设的分类方法。对于给定的训练集首先基于特征条件独立假设学习输入/输出的联合概率分布,然后利用贝叶斯定理求出后验概率最大。

解决问题(适用场景)

分类问题
场景举例:文本主题分类、垃圾文本过滤

技术细节

概率估计方法:极大似然估计和贝叶斯估计(拉普拉斯平滑)

优点

实现简单;对小规模数据表现很好,适合多分类任务;适合增量式训练

缺点

对输入数据表达形式敏感(离散、连续、值极大极小等);需要条件独立假设,会牺牲准确率,分类性能不一定高

逻辑回归

对数线性模型似然函数为目标函数最优化问题

原理

主要计算在某个样本特征下事件发生的概率。用sigmoid函数将线性回归进行了归一化,输出值压缩到0-1之间,这个值代表的是发生的概率。

解决问题(适用场景)

分类问题(二分类推广到多分类)
场景举例:根据用户浏览情况预测是否购买商品

技术细节

  • LogReg中,输出Y=1的对数几率是输入x的线性函数;
  • 极大似然估计法估计模型参数;
  • softmax和k个LR的选择,类别之间互斥,softmax、类别之前有联系,K个LR
  • 优化:梯度下降、拟牛顿法、BFGS、改进的迭代尺度法
    梯度下降会陷入局部最优,改用随机梯度下降,收敛速度更快,且易并行。

优点

简单高效;概率值输出;多重共线性可以通过L2正则化应对

缺点

欠拟合,精度不高;
必须线性可分;
特征空间太大时表现不太好;
大量分类变量性能较差;

k-近邻

判别模型多分类与回归不具有显式学习过程

原理

利用训练数据集对特征向量空间进行划分,根据k个最近邻的训练样本的类别,通过多数表决进行预测。

解决问题(适用场景)

分类与回归

技术细节

三要素:K的选择、距离度量、决策规则

交叉验证,取最优k值
K小,模型变得复杂,过拟合;估计误差增大;
K大,模型变得简单,近似误差增大

kd 树

X的K个特征,一一个切分,使得每个数据最终都在切分点上(中位数),对输入的数据搜索kd树,找到K近邻。

优点

简单,分类与回归,可用于非线性,复杂度为O(n),对噪声不敏感

缺点

K需要人为设定,对大小不平衡数据易偏向大容量数据;计算量大,大量内存

决策树

判别模型多分类与回归正则化的极大似然估计

原理

决策树实际上是将空间用超平面进行划分的一种方法,每次分割的时候,都将当前的空间一分为二,这样使得每一个叶子节点都是在空间中的一个不相交的区域,在进行决策的时候,会根据输入样本每一维feature的值,一步一步往下,最后使得样本落入N个区域中的一个。

解决问题(适用场景)

适用于小数据集
场景举例:基于规则的信用评估

技术细节

特征选择准则:信息增益或信息增益比
决策树生成,ID3、C4.5、CART(Gini index,平方误差)
剪枝,减小模型复杂度,设定$ \alpha $ ,相当于正则化的极大似然估计;动态规划实现

CART
通过递归方式建立决策二叉树,基尼指数最小化的特征(分类),平方误差最小化(回归)作为划分特征

优点

训练时间复杂度低,预测过程快速;可读性好;适合处理有缺失属性值得样本,能够处理不相关特征

缺点

容易过拟合

解决过拟合:剪枝、交叉验证、随机森林

单棵树分类能力弱,对连续变量难以处理

随机森林

判别模型多分类与回归正则化的极大似然估计Random FutureBagging

原理

很多随机生成的决策树组成,预测时,每颗决策树进行判断,最后通过Bagging思想进行结果的输出。
RF被证明对大规模数据集和存在大量且有时不相关特征的项来说很有用。

解决问题(适用场景)

场景举例:用户流失分析、风险评估、检测离群点

技术细节

行(有放回)列(节点分裂时)采样,每个决策树使用相同参数
完全分裂,叶节点特征(样本特征相同、样本类别相同、样本数=1)
超参:树的数量、列采样特征数(通常取总特征的平方根)
泛化误差估计,oob(out-of-bag)

优点

  1. 适合多分类问题,训练和预测速度快
  2. 对训练数据容错能力强,有效的估计缺失数据的方法
  3. 可以处理高维数据且不用特征选择
  4. 训练过程中检测到特征间相互影响及特征重要性
  5. 数据集上表现良好,避免过拟合
  6. 实现简单且容易并行化
  7. 在创建随机森林的时候,对generlization error使用的是无偏估计,所以在随机森林算法中不需要再进行交叉验证或者单独的测试集来获取测试集误差的无偏估计

缺点

噪声较大的分类和回归问题上会过拟合。对于类别特征的属性值较多时,RF产生的属性权重不可信。

支持向量机

间隔最大凸二次规划核函数

原理

低维空间映射到高维空间,实现线性可分,求解正确划分训练集并(几何)间隔最大化的分离超平面。

技术细节

函数间隔,几何间隔
应用拉格朗日对偶性,求解对偶问题(更易求解、自然引用核函数)
正则化的合页损失函数最优化问题
核函数

表示将输入从输入空间映射到特征空间得到的特征向量之间的内积。

序列最小最优化算法(不断分解,对子问题求解,每个子问题中选择两个变量优化,其中一个变量是违反KKT条件的,直到所有变量都满足KKT条件为止)

优点

可以处理高维特征;使用核函数可以向高维空间进行映射,可以解决非线性分类;分类思想简单(间隔最大化);分类效果好

缺点

核函数及参数敏感;无法直接支持多分类;大量观测样本,效率低

集成学习

关键点

  1. 差异性基分类器:数据集(bagging、boosting)、数据特征、改变基分类器参数
  2. 基分类器整合,回归(简单平均、加权平均)、分类(简单/加权投票、概率投票)

Notes:分类问题,每个分类器的分类精度大于0.5

Boosting

三个臭皮匠顶个诸葛亮改变样本权重分而治之加法模型前向分布算法Shrinkage

原理

在分类问题中,通过改变训练样本的权重,学习多个基分类器,最终进行线性组合。

技术细节

概念强可学习充要条件概念弱可学习

  • AdaBoost,提高前一轮弱分类器错分的样本权重,降低分对的样本权重;组合时,加大分类错误率低的基分类器权值,减小分类错误率大的权重。
  • AdaBoost二分类学习时是加法模型、损失函数为指数函数、学习算法为前向分布算法

boosting tree
基分类器,分类树或回归树,不同的问题的提升树主要区别在于损失函数不同。

  • 梯度提升(gradient boosting),每一轮计算为了减少上一次的残差,加入新的model是在之前model损失函数梯度下降方向。
  • GBDT精髓,在于训练都以上一棵树的残差为目标去提升。

调参:树的个数、树深度、学习速率、叶子上最大节点树、训练采样比例、训练特征采样比例……

优点

精度高;能处理非线性数据;能处理多特征类型;适合低维稠密数据

缺点

并行麻烦;多分类时,复杂度大

EM

含隐变量的概率模型极大似然估计

原理

从不完全数据或有数据丢失的数据集(存在隐含变量)中求解概率模型参数的最大似然估计方法。

解决问题(适用场景)

含有隐变量、非监督学习
高斯混合模型学习中的应用

技术细节

E步,求期望,根据上一步迭代的模型参数计算隐变量的后验概率;M步,求极大,似然函数最大化获得新的参数值

优点

思想简单,普适

缺点

EM算法与初值的选择有关,不同初值,得到不同参数估计;

归一化使梯度下降收敛更好?

如果不归一化,各维特征的跨度差距很大,梯度下降时,目标函数梯度方向就会偏离最小值的方向,走很多弯路,如下方左图。
如果归一化了,每一步梯度的方向都指向最小值,收敛更快,如下方右图。

descend

算法横向比较

LR与Linear SVM

  • 都是线性分类器;
  • 都会受到异常点影响;
  • 本质不同——损失函数,一个hinge loss,一个logistical loss
  • Linear SVM只受支持向量影响(部分样本),LR则受所有数据点影响;
  • Linear SVM需要归一化数据,LR不受影响;
  • Linear SVM自带正则,而LR需另加;
  • 海量数据LR使用更广泛,Linear SVM内存消耗大

LR与朴素贝叶斯

  • 判别/生成model;
  • 朴素贝叶斯条件独立假设;
  • 当数据集小时,首选朴素贝叶斯,数据集大时,考虑LR

附两份cheat sheet

sk-learn
cheat sheet

分享