线性分类器 VS 非线性分类器

在这一小节，我展示了Naive Bayes和Rocchio这两个学习方法，它们都属于线性分类器，大概也是文本分类器中最重要的一组，接着我把它们和非线性分类器做了一个比较。为了简化讨论部分，我在这一节将只考虑二类分类器，并将不同特征的线性组合和阈值做比较从而定义一个线性分类器为一个二类分类器。

图 14.8：有无数个可划分这两个线性可分类的超平面

在二维空间里面，一个线性分类器是一条线。图14.8展示了五个分类例子。这些线有一个函数形式w1x1­+w2­x2=b。线性分类器的分类规则是：如果w1x1­+w2­x2>b，就把一个文档归类为，如果w1x1­+w2­x2<=b,就把它归类为。在这里，(x1,x2)T是文档的二维向量表示，(w1,w2)是参数向量，和b一起决定决策边界。此外，在图 15.7中给出了线性分类器的另一种几何解释。

正如我们之前在公式 140中处理的那样，我们可以通过定义一个超平面将一个二维线性分类器映射到更高维空间，这里我重复一下之前的公式，即公式 144：

然后，分类标准更改为：如果，就归类为，如果，就归类为。我们把使用的超平面作为一个线性分类器的决策超平面。

图14.9 线性分类算法

图 14.9展示的是在M维空间中对应的线性分类算法。首先，从给出的这个简化算法表述来看，线性分类似乎是很简单的。然而，困难的是线性分类器的训练，也就是基于数据集来确定参数和b。我们用于评估学习算法性能的标准是通过比较经过学习得到的线性分类器在新数据上的表现效果来确定的，通常会有一些学习算法最后会计算出优于其它算法的参数。

现在，我们来证实下Rocchio和Naive Bayes这两个线性分类器。让我们先来看看Rocchio，可以看出如果一个向量到两个类质心的距离相等，那么它就位于决策边界上。

我们可以从它的决策规则中推导出Naïve bayes的线性，它选择有最大的作为类别(如图 13.2 , 页码 13.2 )，其中：

表示的是词表中包含的词在文档中出现的个数。对立类别用表示，我们可以得到log概率：

如果概率大于1，或是log概率大于0，我们就归类为。很容易看出，公式 147 是公式 144 的一个实例，其中，xi=d中ti的出现次数，。这里，下标i， 指的是词表中的词（并不是和k一样，指词在文档d中的位置；参见variantmultinomial），x和w是M维向量。因此，在log空间中，朴素贝叶斯是一个线性分类器。

一个线性分类器。在Reuters-21578中用于分类interest（如interest rate）的线性分类器的维数

和参数

，阈值

。像dlr和world这样的术语有负权重，因为它们是用于另一个类别“货币”的标志。

工作例子。表14.4定义了一个用于在Reuters-21578（见 13.6节，页 13.6）中分类interest的线性分类器。我们把文档`

`rate discount dlrs world''分为interest，因为

。我们把`

`prime dlrs''分为对立类（不在interest中），因为

。为了简化，我们在这个例子中假设一个简单的二类向量可以表示为如下形式：1表示出现的术语，0表示没有出现的术语。工作例子到此为止。

一个有噪声数据的线性问题。在这个假设的web页面分类场景中，全是中文的网页用实心圆标记，中英混合的网页用正方形表示。这两类被一个线性分类边界（虚线、短虚线）区分开，除了三个噪声文档（使用箭头标记）

图 14.10是线性问题的图例，我们的定义表明两个类的潜在分布

和

中有一条分隔线。我们把这条分割线称作类边界。这是两类的“true”边界并且我们把它从决策边界（学习方法计算类边界的近似值）中识别出来。

在典型的文本分类中，如图 14.10 （使用箭头标记的部分）有一些噪声文档，没有很好的拟合类别的整体分布。在 13.5 小节（页码 13.5 ），我们把噪声特征定义为误导特征，当文档中包含有噪声特征时，分类误差会均匀地增加。类似的，当训练集中包含噪声文档时，那么它将会误导学习方法并且增加分类错误率。直觉上，将代表空间划分为不同的区域，区域内的大部分样本类别都相同。一个文档如果不属于它所在区域的主要类别，那么它就是噪声文档。

噪声文档是使训练线性分类器变得困难的一个原因。在选择分类器决策超平面时，如果我们过于关注噪声文档，那么分类器在新的数据上就会表现得的不精确。最根本的是，通常很难决定哪一个文档属于噪声文档并因此潜在的误导我们。

如果存在一个超平面能够完美的的划分两个类别，那么我们称这两个类别为线性可分。事实上，如果具有线性可分性，那么会有无数条线性分割线（练习 14.4 ），如图 14.8 所示，可分割超平面是无限的。

图 14.8表明了在训练线性分类器中的另一挑战。如果我们处理的是一个线性可分问题，那么我们需要一条标准从所有的决策超平面中来进行选择，让其能够完美的划分训练数据。通常这些超平面，有些可以在新数据上表现的很好，而另一些则表现的不尽人意。

图14.11 非线性问题

非线性分类器的一个典型例子就是kNN。从图 14.6这个例子可以看出，kNN的非线性是直观清晰的。kNN的决策边界（如14.6的 两条线 ）是局部线性划分，但通常有一个复杂的形状，并不等同于二维空间中的一条线或是更高维空间中的一条超平面。

图 14.11是另一个非线性问题的例子：在

分布和

分布中没有一条很好的线性分割线，因为在图的左上角还有一个环形包围的“区域”。

线性分类器会误分圆形内部的部分，所以在处理这种类型的问题时，如果训练集足够大的话，像kNN这样的非线性分类器反而会表现得更加精确。

如果一个问题是非线性问题并且它的类边界不能够用线性超平面估计得很好，那么非线性分类器通常会比线性分类器表现得更精准。如果一个问题是线性的，那么最好使用简单的线性分类器来处理。

练习：

证明二分类中线性分割线的个数要么是无穷个，要么是零。

原文链接： Linear versus nonlinear classifiers（译者/刘帝伟 审校/赵屹华、朱正贵、李子健 责编/仲浩）

译者简介: 刘帝伟,中南大学软件学院在读研究生，关注机器学习、数据挖掘及生物信息领域。