下面,介绍了各个算法的概念及特点。
- KNN
- 决策树
- 朴素贝叶斯
- 逻辑回归
- 支持向量机
- 随机森林
- AdaBoost
- GBDT
- XGBoost
一、K 近邻(KNN)
k-近邻算法(K-Nearest neighbors,KNN),它采用测量不同特征值之间的距离方法进行分类,即是给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的K个实例(也就是上面所说的K个邻居), 这K个实例的多数属于某个类,就把该输入实例分类到这个类中。
KNN 是一种基本分类与回归方法,其基本做法是:给定测试实例,基于某种距离度量找出训练集中与其最靠近的k个实例点,然后基于这k个最近邻的信息来进行预测。
通常,在分类任务中可使用“投票法”,即选择这k个实例中出现最多的标记类别作为预测结果;在回归任务中可使用“平均法”,即将这k个实例的实值输出标记的平均值作为预测结果;还可基于距离远近进行加权平均或加权投票,距离越近的实例权重越大。
k近邻法不具有显式的学习过程,事实上,它是懒惰学习(lazy learning)的著名代表,此类学习技术在训练阶段仅仅是把样本保存起来,训练时间开销为零,待收到测试样本后再进行处理。
k近邻法的三要素:距离度量、k值的选择及分类决策规则是k近邻法的三个基本要素。
kNN 算法特点:
优点:精度高、对异常值不敏感、无数据输入假定
缺点:计算复杂度高、空间复杂度高
适用数据范围:数值型和标称型
二、决策树
决策树(Decision Trees)是一种非参监督学习方法,即没有固定的参数,对数据进行分类或回归学习。决策树的目标是从已知数据中学习得到一套规则,能够通过简单的规则判断,对未知数据进行预测。
决策树是一种基本的分类与回归方法。在分类问题中,表示基于特征对实例进行分类的过程,可以认为是 if-then 的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。
决策树通常有三个步骤:特征选择、决策树的生成、决策树的修剪。
用决策树分类:从根节点开始,对实例的某一特征进行测试,根据测试结果将实例分配到其子节点,此时每个子节点对应着该特征的一个取值,如此递归的对实例进行测试并分配,直到到达叶节点,最后将实例分到叶节点的类中。
决策树模型
决策树学习的目标:根据给定的训练数据集构建一个决策树模型,使它能够对实例进行正确的分类。
决策树学习的本质:从训练集中归纳出一组分类规则,或者说是由训练数据集估计条件概率模型。
决策树学习的损失函数:正则化的极大似然函数。
决策树学习的测试:最小化损失函数。
决策树原理和问答猜测结果游戏相似,根据一系列数据,然后给出游戏的答案。
决策树算法特点:
优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据。
缺点:可能会产生过度匹配问题。
适用数据类型:数值型和标称型
三、朴素贝叶斯
朴素贝叶斯(Naive Bayesian)是基于贝叶斯定理和特征条件独立假设的分类方法,它通过特征计算分类的概率,选取概率大的情况进行分类。
朴素贝叶斯是经典的机器学习算法之一,也是为数不多的基于概率论的分类算法。对于大多数的分类算法,在所有的机器学习分类算法中,朴素贝叶斯和其他绝大多数的分类算法都不同。比如决策树,KNN,逻辑回归,支持向量机等,他们都是判别方法,也就是直接学习出特征输出Y和特征X之间的关系,要么是决策函数,要么是条件分布。但是朴素贝叶斯却是生成方法,该算法原理简单,也易于实现。
朴素贝叶斯
在scikit-learn中,一共有3个朴素贝叶斯的分类算法类。分别是GaussianNB,MultinomialNB和BernoulliNB。其中GaussianNB就是先验为高斯分布的朴素贝叶斯,MultinomialNB就是先验为多项式分布的朴素贝叶斯,而BernoulliNB就是先验为伯努利分布的朴素贝叶斯。
朴素贝叶斯算法特点:
优点:在数据较少的情况下依然有效,可以处理多类别问题。
缺点:对于输入数据的准备方式较为敏感。
适用数据类型:标称型数据
四、逻辑回归
逻辑(Logistic) 回归是一种统计方法,用于根据先前的观察结果预测因变量的结果。它是一种回归分析,是解决二分类问题的常用算法。
逻辑回归算法特点:
优点:计算代价不高,易于理解和实现
缺点:容易欠拟合,分类精度可能不高(这里是使用构造数据,效果较佳,并且运行多次,结果可能不一样)
五、支持向量机(SVM)
支持向量机(简称SVM)英文为Support Vector Machine。它是一 种监督式学习的方法,它广泛的应用于统计分类以及回归分析中。支持向量机(Support Vector Machine)是一种十分常见的分类器,核心思路是通过构造分割面将数据进行分离。
SVM 是一类按监督学习方式对数据进行二元分类的广义线性分类器,其决策边界是对学习样本求解的最大边距超平面,可以将问题化为一个求解凸二次规划的问题。与逻辑回归和神经网络相比,支持向量机,在学习复杂的非线性方程时提供了一种更为清晰,更加强大的方式。
具体来说就是在线性可分时,在原空间寻找两类样本的最优分类超平面。在线性不可分时,加入松弛变量并通过使用非线性映射将低维度输入空间的样本映射到高维度空间使其变为线性可分,这样就可以在该特征空间中寻找最优分类超平面。
SVM使用准则:n 为特征数, m 为训练样本数。
- 如果相较于m而言,n要大许多,即训练集数据量不够支持我们训练一个复杂的非线性模型,我们选用逻辑回归模型或者不带核函数的支持向量机。
- 如果n较小,而且m大小中等,例如n在 1-1000 之间,而m在10-10000之间,使用高斯核函数的支持向量机。
- 如果n较小,而m较大,例如n在1-1000之间,而𝑚大于50000,则使用支持向量机会非常慢,解决方案是创造、增加更多的特征,然后使用逻辑回归或不带核函数的支持向量机。
SVM 算法特点:
优点:计算代价不高,易于理解和实现
缺点:容易欠拟合,分类精度可能不高
适用数据类型:数值型和标称型数据
六、随机森林
随机森林是一个包含多个决策树的分类器, 并且其输出的类别是由个别树输出的类别的众数而定。随机森林解决决策树泛化能力弱的特点。
随机森林算法的具体流程
随机森林算法特点:
优点:
- 对于很多种资料,可以产生高准确度的分类器
- 可以处理大量的输入变量
- 可以在决定类别时,评估变量的重要性
- 在建造森林时,可以在内部对于一般化后的误差产生不偏差的估计
- 包含一个好方法可以估计丢失的资料,并且如果有很大一部分的资料丢失,仍可以维持准确度
- 对于不平衡的分类资料集来说,可以平衡误差
- 可被延伸应用在未标记的资料上,这类资料通常是使用非监督式聚类,也可侦测偏离者和观看资料
- 学习过程很快速
缺点:
- 牺牲了决策树的可解释性
- 在某些噪音较大的分类或回归问题上会过拟合
- 在多个分类变量的问题中,随机森林可能无法提高基学习器的准确性
七、AdaBoost算法
提升方法是从弱学习算法出发,反复学习,得到一系列的弱分类器(即基本分类器),然后组合这些弱分类器,构成一个强分类器,大多数的提升方法都是改变训练数据集的概率分布(训练数据的权值分布),针对不同的训练数据分布调用弱学习算法学习一系列的弱分类器。
AdaBoost算法特点:
优点:
1. 分类精度高;
2. 可以使用各种方法构建子分类器,Adaboost算法提供的是框架;
3. 简单,且不用做特征筛选;
4. 不会造成overfitting。
缺点:
1. 对分类错误的样本多次被分错而多次加权后,导致权重过大,影响分类器的选择,造成退化问题;(需改进权值更新方式)
2. 数据不平衡问题导致分类精度的急剧下降;
3. 算法训练耗时,拓展困难;
4. 存在过拟合,稳健性不强等问题。
八、GBDT
GBDT的基本结构是决策树组成的森林,学习方式是梯度提升。
具体讲,GBDT作为集成模型,预测的方式是把所有子树的结果加起来。GBDT通过逐一生成决策子树的方式生成整个森林,生成新子树的过程是利用样本标签值与当前树林预测值之间的残差,构建新的子树。
GBDT 算法特点:
优点:
1) 可以灵活处理各种类型的数据,包括连续值和离散值。
2) 在相对少的调参时间情况下,预测的准确率也可以比较高。这个是相对SVM来说的。
3)使用一些健壮的损失函数,对异常值的稳健性非常强。比如 Huber损失函数和Quantile损失函数。
缺点:
1) 由于弱学习器之间存在依赖关系,难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。
九、XGBoost算法
极端梯度提升(eXtreme Gradient Boosting,XGBoost)。XGBoost是陈天奇等人开发的一个开源机器学习项目,高效地实现了GBDT算法并进行了算法和工程上的许多改进,被广泛应用在Kaggle竞赛及其他许多机器学习竞赛中并取得了不错的成绩。
它是大规模并行boosted tree的工具,它是目前最快最好的开源boosted tree工具包。XGBoost 所应用的算法就是 GBDT(gradient boosting decision tree)的改进,既可以用于分类也可以用于回归问题中。与GBDT最大的区别是xgboost通过对目标函数做二阶泰勒展开,从而求出下一步要拟合的树的叶子节点权重(需要先确定树的结构),从而根据损失函数求出每一次分裂节点的损失减小的大小,从而根据分裂损失选择合适的属性进行分裂。
1.XGBoost与GBDT相比,其优势:
将树模型的复杂度加入到正则项中,来避免过拟合,因此泛化性能会优于GBDT。
损失函数用泰勒展开式展开,同时用到了一阶和二阶导数,可以加快优化速度。
GBDT只支持CART作为基学习器,XGBoost还支持线性分类器作为基学习器。
引进了特征子采样,像随机森林那样,既能避免过拟合,又能减少计算。
在寻找最优分割点时,考虑到传统的贪心算法效率较低,实现了一种近似贪心算法,用来加速和减少内存小号,除此之外,还考虑了稀疏数据集合缺失值的处理。
XGBoost支持并行处理。XGBoost的并行不是模型生成的并行,而是在特征上的并行,将特征排序后以block的形式存储在内存中,在后面迭代重复使用这个结构。这个block也使得并行化成为了可能,其次在节点分裂时,计算每个特征的增益,最终选择增益最大的那个特征去做分割,那么各个特征的增益计算就可以开多线程进行。
2.与lightGBM相比的不足点:
XGBoosting采用预排序,在迭代之前,对结点的特征做预排序,遍历选择最优分割点,数据量大时,贪心法耗时,LightGBM方法采用histogram算法,占用的内存低,数据分割的复杂度更低。
XGBoosting采用level-wise生成决策树,同时分裂同一层的叶子,从而进行多线程优化,不容易过拟合,但很多叶子节点的分裂增益较低,没必要进行更进一步的分裂,这就带来了不必要的开销;LightGBM采用深度优化,leaf-wise生长策略,每次从当前叶子中选择增益最大的结点进行分裂,循环迭代,但会生长出更深的决策树,产生过拟合,因此引入了一个阈值进行限制,防止过拟合。
如何决定选择哪种分类算法
下面有一个列表,可以帮助您了解应该使用哪些分类算法来解决业务问题。
- 问题识别:首先要做的是彻底了解手头的任务。如果是有监督的分类案例,可以使用逻辑回归、随机森林、决策树等算法。
- 数据集的大小:数据集的大小也是您在选择算法时应该考虑的一个参数。由于很少有算法相对较快,因此最好切换到那些算法。如果数据集的大小很小,您可以坚持使用像朴素贝叶斯这样的低偏差/高方差算法。相反,如果数据集很大,特征数量很多,那么你应该使用高偏差/低方差算法,如 KNN、决策树和 SVM。
- 预测准确度:模型的准确度是测试分类器好坏的参数。它反映了预测输出值与正确输出值的匹配程度。当然,更高的精度是可取的,但还应检查模型是否过拟合。
- 训练时间:有时,像 SVM 和随机森林这样的复杂算法可能会占用大量计算时间。此外,更高的准确性和大数据集无论如何需要更多时间来学习模式。像逻辑回归这样的简单算法更容易实现并节省时间。
- 数据集的线性:输入变量和目标变量之间并不总是存在线性关系。因此,必须分析这种关系并仔细选择算法,因为其中一些仅限于线性数据集。检查线性的最佳方法是拟合线性线或运行逻辑回归或 SVM 并查找残差。较高的误差表明数据是非线性的,需要实施复杂的算法。
- 特征数量:有时,数据集可能包含不必要的许多特征,并且并非所有特征都相关。然后可以使用最适合这种情况的 SVM 等算法,或者使用主成分分析来确定哪些特征是重要的。