常用的分类算法

参考链接：
https://www.sohu.com/a/225585188_556060
http://www.360doc.com/content/16/0330/01/31750011_546416731.shtml
https://zhuanlan.zhihu.com/p/34154663
https://baijiahao.baidu.com/s?id=1591109035165038806&wfr=spider&for=pc

机器学习本质上就是一种对问题真实模型的逼近。其中有监督的分类算法在众多的业务场景得到了非常广泛的应用，如：根据个人的学历、性别、年龄等信息判断用户是否会违约等。分类问题属于预测任务，就是通过已有数据集（训练集）的学习，得到一个目标函数f（模型），把每个属性集x映射到目标属性y（类），且y必须是离散的（若y为连续的，则属于回归算法）。

解决分类问题的方法很多，基本的分类方法主要包括：决策树、朴素贝叶斯、人工神经网络、K-近邻、支持向量机等；另外还有用于组合基本分类器的集成学习算法，集成学习的代表算法有随机森林，adaboost，xgboost等。本篇文章主要总结了各基本分类器的基本原理和优缺点。

一、K近邻法(K-Nearest Neighbor，KNN)：

KNN法即K近邻法，最初由Cover和Hart于1968年提出的，是一个理论上比较成熟的方法。人常说“物以类聚，人以群分”，要判断一个人的好坏就看看他周围的朋友，如果朋友都是好人，当然此君也极有可能是好人。反之亦然。KNN算法就是基于这种思想。

它的思路非常简单：找到训练集样本空间中的K个距离预测样本x最近的点，统计K个距离最近的点的类别，找出个数最多的类别，将x归入该类别。从下图的示例中可以清晰看出，当K=5时，未知样本xu应该属于类别w1。

KNN法的三要素

KNN法有三个基本要素：K值的选择、距离度量及分类决策规则。

（1）Ｋ值选择

K太小，分类结果易受噪声点影响；K太大，近邻中又可能包含太多的其它类别的点。（对距离加权，可以降低k值设定的影响）。K值通常是采用交叉检验来确定。经验规则：K一般低于训练样本数的平方根。

（2）距离度量选择

一般采用马氏距离或者欧式距离。需要注意的是，高维度和变量值域对距离衡量存在显著影响：当变量数越多，欧式距离的区分能力就越差；值域越大的变量常常会在距离计算中占据主导作用，因此应先对变量进行标准化。

（3）决策规则

投票法没有考虑近邻的距离的远近，距离更近的近邻也许对最终的分类有更大的影响，所以加权投票法更恰当一些。加权投票法中的权重随着样本间距离增大而减小。

KNN算法步骤

3. KNN算法的优缺点

优点：

（1）简单有效，容易理解和实现。

（2）重新训练的代价较低（类别体系的变化和训练集的变化）。

（3）由于KNN方法主要依赖周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

(4) 适合处理多模分类和多标签分类问题。

缺点：

（1）是lazy learning方法（决策在测试时生成），比一些积极学习的算法要慢；

（2）计算量比较大（需要计算到所有样本点的距离），需对样本点进行剪辑；

（3）样本不平衡会导致预测偏差较大，可采用加权投票法改进；

（4）容易对维度灾难敏感；

（5）类别评分不是规格化的（不像概率评分）。

二、SVM法：

SVM法即支持向量机(Support Vector Machine)法，是一个二分类的分类模型。由Vapnik等人于1995年提出。SVM的主要思想可以概括为两点（源自百度百科）：

（1）它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能。

（2）它基于结构风险最小化理论之上在特征空间中构建最优超平面，使得学习器得到全局最优解，并且在整个样本空间的期望以某个概率满足一定上界。

1、线性可分

支持向量机把分类问题转化为寻找分类平面的问题，并通过最大化分类边界点距离分类平面的距离来实现分类。故SVM法亦被称为最大边缘(maximum margin)算法。

举例说明SVM的思想

源自：https://www.zhihu.com/question/21094489

（1）对两类样本进行分类

（2）想要找到可以将两类样本分隔开的直线（高维时则是找到超平面）

（3）发现：增加样本数量后，很容易出现分类错误的样本

（4）SVM就是试图找到最佳的直线，能让直线两边有尽可能大的间隙。

（5）这种情况下，即使增加了样本数量，仍然可以将不同类别的样本区分开。

将训练集中的数据区分开的超平面可以线性方程表示：

假设两种样本的标签分别是{+1，-1}，那么对于一个分类器来说，f(x)>0和个f(x)<0就可以分别代表两个不同的类别，+1和-1。但光是分开是不够的，SVM的核心思想是尽最大努力使分开的两个类别有最大间隔，这样才使得分隔具有更高的可信度。而且对于未知的新样本才有很好的分类预测能力（即泛化能力）。

为了描述这个间隔，并且让它最大，SVM的办法是：让离分隔面最近的数据点距离分隔面具有最大的距离。

将距离分离超平面最近的两个不同类别的样本点称为支持向量（support vector），两个类别中的支持向量构成了两条平行于分离超平面的长带，二者之间的距离称之为margin。

从上图中可观察到：margin以外的样本点对于确定分离超平面没有贡献，换句话说，SVM是由训练样本中很重要的支持向量所确定的。待分样本集中的大部分样本不是支持向量，移去或者减少这些样本对分类结果没有影响。因此，SVM具有较好的适应能力和较高的分准率。

SVM分类问题可描述为在全部分类正确的情况下，最大化间隔

，等价于最小化

。因此，SVM的约束最优化问题可以表示为：

2、线性不可分

线性可分是理想情况，通常情况下，由于噪声或特异点等各种原因，训练样本是线性不可分的。线性不可分意味着公式（2.2）中的约束条件不再满足，为解决这个问题，可以对每个样本引入一个松弛变量

。此时，约束最优化问题变为：

目标函数有两层含义：（1）margin尽量大，（2）误分类的样本点计量少。其中，C为惩罚函数，调节（1）和（2）的权重占比。

其等价的对偶优化问题：

3、非线性

对于非线性问题，线性SVM不再适用了，需要非线性SVM来解决了。解决非线性分类问题的思路，通过空间变换ϕ，一般是低维空间映射到高维空间x→ϕ(x)后实现线性可分，在下图所示的例子中，通过空间变换，将左图中的曲线分离变换成了右图中平面可分。

在SVM的等价对偶问题中的目标函数中有样本点的内积xi⋅xj，在空间变换后则是ϕ(xi)⋅ϕ(xj)，由于维数增加导致内积计算成本增加，这时核函数（kernel function）便发挥作用了，将映射后的高维空间内积转换成低维空间的函数：K(x,z)=ϕ(x)⋅ϕ(z)，将其代入一般化的SVM学习算法的目标函数(2.4)中，可得非线性SVM的最优化问题：

4、SVM的优缺点

优点：

（1）适合小样本情况下的机器学习问题；

（2）可以提高泛化性能；

（3）可以解决高维问题；

（4）可以解决非线性问题；

（5）可以避免神经网络结构选择和局部极小点问题。

缺点：

（1）对缺失数据敏感；

（2）对非线性问题没有通用解决方案，必须谨慎选择Kernel function来处理；

（3）计算复杂度高。主流的算法是O(n^2)的，大规模数据计算耗时。

三、决策树分类算法

决策树（decision tree）归纳是经典的分类算法。它采用自顶向下递归的方式构造决策树。可以从生成的决策树中提取规则。

上图给出了（二叉）决策树的示例。决策树具有以下特点：

（1）对于二叉决策树而言，可以看作是if-then规则集合，由决策树的根节点到叶子节点对应于一条分类规则;

（2）分类规则是互斥并且完备的，所谓互斥即每一条样本记录不会同时匹配上两条分类规则，所谓完备即每条样本记录都在决策树中都能匹配上一条规则；

（3）分类的本质是对特征空间的划分，如下图所示。

决策树思想，实际上就是寻找最纯净的划分方法，这个最纯净在数学上叫纯度，纯度通俗点理解就是目标变量要分得足够开（y=1的和y=0的混到一起就会不纯）。另一种理解是分类误差率的一种衡量。实际决策树算法往往用到的是纯度的另一面，即不纯度。不纯度的选取有多种方法，如信息熵，基尼指数，分类误差等。

决策树要达到寻找最纯净划分的目标要干两件事，建树和剪枝。

1、决策树建树

决策树建树，首先需要解决三个问题：

（1）如何选择较优的特征属性进行分裂？

每一次特征属性的分裂，相当于对训练数据集进行再划分，对应于一次决策树的生长。选择较优的特征属性，首先需要对特征的重要性进行排序比较。也就是从树根节点到叶子节点上的特征变量是从最重要到次重要依次排序的，那怎么衡量这些变量的重要性呢？ID3算法用的是信息增益，C4.5算法用信息增益率；CART算法使用基尼系数。

为了判断分裂前后节点不纯度的变化情况，目标函数定义为信息增益（informationgain）：

I(⋅)对应于决策树节点的不纯度，parent表示分裂前的父节点，N表示父节点所包含的样本记录数，ai表示父节点分裂后的某子节点，N(ai)为其计数，n为分裂后的子节点数。特别地，ID3算法选取熵值作为不纯度I(⋅)的度量，则

c指父节点对应所有样本记录的类别；A表示选择的特征属性，即ai的集合。那么，决策树学习中的信息增益Δ等价于训练数据集中类与特征的互信息，表示由于得知特征A的信息训练数据集c不确定性减少的程度。

在特征分裂后，有些子节点的记录数可能偏少，以至于影响分类结果。为了解决这个问题，CART算法提出了只进行特征的二元分裂，即决策树是一棵二叉树；C4.5算法改进分裂目标函数，用信息增益比（information gain ratio）来选择特征：

因而，特征选择的过程等同于计算每个特征的信息增益，选择最大信息增益的特征进行分裂。

决策树方法是会把每个特征都试一遍，然后选取那个，能够使分类分的最好的特征，也就是说将A属性作为父节点，产生的纯度增益（GainA）要大于B属性作为父节点产生的纯度增益（GainB），则A作为优先选取的属性。

（2）如何分裂训练数据（对每个属性选择最优的分割点）

分裂准则依然是通过不纯度来分裂数据的，通过比较划分前后的不纯度值，来确定当前属性的最优分割点。

（3）什么时候应该停止分裂？

有两种自然情况应该停止分裂：

- 该节点对应的所有样本记录均属于同一类别，

- 该节点对应的所有样本的特征属性值均相等。

但除此之外，还可以手动设定分裂停止条件：

- 树的深度达到设定的阈值，

- 该节点所含观测值的数量少于预设的父节点应含观测值数量的阈值，

- 该节点所含观测值的数量少于预设的阈值等。

2、决策树剪枝

生成的决策树对训练数据会有很好的分类效果，却可能对未知数据的预测不准确，即决策树模型发生过拟合（overfitting）——训练误差（training error）很小、泛化误差（generalization error，亦可看作为test error）较大。发生过拟合的根本原因是分类模型过于复杂，可能的原因如下：

(1) 训练数据集中有噪音样本点，对训练数据拟合的同时也对噪音进行拟合，从而影响了分类的效果；

(2) 决策树的叶子节点中缺乏有分类价值的样本记录，也就是说此叶子节点应被剪掉。

为了避免决策树过拟合，需要对树进行剪枝。《统计学习方法》（李航）中提出一种简单剪枝策略，通过极小化决策树的整体损失函数（loss function）或代价函数（cost function）来实现，决策树T的损失函数为：

Lα(T)=C(T)+α|T| (3.4)

其中，C(T)表示决策树的训练误差，α为调节参数，|T|为模型的复杂度。当模型越复杂时，训练的误差就越小。上述定义的损失正好做了两者之间的权衡。如果剪枝后损失函数减少了，即说明这是有效剪枝。具体剪枝算法可以由动态规划等来实现。

3、决策树的优缺点

优点：

(1) 计算复杂度不高，易于理解和解释；

(2) 数据预处理阶段比较简单，且可以处理缺失数据；

(3**) 能够同时处理数据型和分类型属性，**且可对有许多属性的数据集构造决策树，其他技术往往需要数据属性的单一；

(4) 是一个白盒模型，若给定一个观察模型，则根据所产生的决策树很容易推断出相应的逻辑表达式；

(5) 在相对短的时间内能够对大数据集合做出可行且效果良好的分类结果。

缺点：

（1）对于各类别样本数量不一致数据，信息增益偏向于那些具有更多数值的特征。因此建议用平衡的数据训练决策树；

（2）决策树的结果可能是不稳定的，因为在数据中一个很小的变化可能导致生成一个完全不同的树，这个问题可以通过使用集成决策树来解决；

（3）实际决策树学习算法是基于启发式算法，如贪婪算法，寻求在每个节点上的局部最优决策。这样的算法不能保证返回全局最优决策树；

（4）忽略属性之间的相关性；

（5）易于过拟合；

（6）对噪声数据较为敏感。

四、朴素贝叶斯(Naïve Bayes)法

**朴素贝叶斯法是基于贝叶斯定理与特征条件独立假设的分类方法。**朴素贝叶斯分类器的主要思路：通过联合概率P(x,y)=P(x|y)P(y)建模，运用贝叶斯定理求解后验概率P(y|x)；将后验概率最大者对应的的类别作为预测类别，因为后验概率最大化，可以使得期望风险最小化（期望风险是全局的，是基于所有样本点的损失函数最小化的）。

朴素贝叶斯分类器

首先定义训练样本集，其类别

，则训练样本中有N个样本，类别数为K，输入待测样本x，通过最大化后验概率的原则预测x类别的公式如下：

由贝叶斯定理可知：

对于类别ck而言，P(x)是恒等的，因此公式（4.1）可以等价为：

从上式可以发现，朴素贝叶斯分类问题转化成了求条件概率和先验概率乘积的最大值问题。其中先验概率可以通过统计不同类别样本出现频次得到，而条件概率却无法直接获得。朴素贝叶斯法对条件概率做了条件独立的假设，即特征条件独立。样本x有n维特征向量()，第j维特征x(j)的取值有Sj个。根据条件独立假设，可知