线性分类器 (Linear Classifiers).docVIP

线性分类器 (Linear Classifiers) 我们看到，在一定条件下，基于概率或概率密度的分类器设计问题，即基于后验概率或类条件概率密度的分类器设计问题，或用Bayes决策理论设计的分类器可转化为线性分类器。 线性分类器的特点是结构简单，计算工作量小，缺点是在很多情况下分类正确率不够高。 线性判别函数和决策超平面(Linear Discriminant Functions and Decision Hyperplanes) 我们先考虑两类问题和线性判别函数。设特征空间维数为m，即x(Rm，一个超平面决策方程可写为 这里，w=(w1,w2,(,wm)T为权值向量，w0为阈值(bias)。如果x1、x2两个点均在超平面(上，则有 或 显然，w与x1-x2垂直。有时，人们称w为超平面(的法矢量。将(3.1)展开得 这里，x0=1。平面(在坐标轴上的截距为 图3.1给出了线性分类器决策超平面示意图。根据该图，坐标原点到决策平面(的Euclid距离为 特征空间任意一点x=(x1,x2,(,xm)T到决策平面(的Euclid距离为 特别需要注意的是，(1: l(x)=w1x1+w2x2+(+wmxm+w0=0与(2: l(x)= -w1x1-w2x2-(-wmxm-w0=0所决定的平面完全相同，但它们的决策区域却是完全相反的。因此，在判断决策区域时，重要的是法矢量的方向。 更一般地，有 称之为代数（有向）距离，它是Euclid距离的倍。 另外，两点xi、xk在特征空间的距离为(0=(xi-xk(，但 是原来距离的倍。从这个意义讲，人们常称一个线性分类器就是执行一个线性变换。事实上，（3-9）表示的就是两点之差xi-xk在权值向量或决策平面法矢量方向上的投影，与阈值w0无关，如图3.2所示。 推广以一下，若两点xi、xk经两个线性变换l1(x)和l1(x)，则如图3.3所示。 必须指出的是，多少次线性变换等价于一次线性变换。 我们称(: l(x)=0为决策超平面。若分类对象只有两类(1、(2，决策规则为 若分类对象有多类，决策函数形式上仍为 但决策过程中会出现图3.4所示的几种情况。类别数越多，情况月越复杂。因此，线性分类器只对处理不同类别的样本分布在特殊区域的情况才是有效的。例如，各个类别均位于超维立方体的顶端。 3.2超维分界平面的确定—感知器算法（Perceptron Algorithm） ，这是过坐标原点的超维平面。对一般方程，只需令、即可。设(为错分样本的集合，则误差函数为 其中，与样本是否被错分有关。判别规则为 设样本的类别为已知（当然来自于训练集），但 为了确定一组最佳的，对（3-12）求偏导，则有 根据梯度下降算法，有 式中，(为学习率，或称之为步长，(为迭代次数。 特别地，设(=1，只有来自(1的样本和来自(2的样本被错分，（3.16）变为 图3.3为感知器算法的一次学习过程。 感知器算法在具体实现时，初始权值分量可为(0, 1)之间的随即数。一般地，步长因子0(1。步长太大，可能造成一次调整量过多（调整过头）；反之，(太小，则需要更多的学习次数，即学习时间长。 可以证明，只要两个类别是线性可分的，感知器学习算法是收敛的，反之则该算法不收敛。对线性可分的样本集，学习结束时，线性分类器对训练集的错分样本数为0。 例3.1，证明，对线性可分的样本集，感知器学习算法收敛。 是一个解，则 由于为错分的样本， ，所以 又由于是一个解，且被错分，于是 但 令，，则有 写成递推公式，就是 当(足够大时，有 但，由此推出矛盾，故 当(足够大时，有。 又为一有限值，所以，当没有样本被错分时，有，或，于是 也是有限值。 这说明，若两个类别是线性可分的，则在有限步内，感知器学习算法收敛。 方法2： 设是一个解，当迭代次数(足够多时，逼近于，于是，两者之间的夹角余弦为 由于 这里，。 又 这里，。 类推下去，有 所以 特别地，取，取（元素均为零的向量），为单位向量，则有 ( 或 由于(、(均为有限值，故(也为有限值。 例3.2，设第次学习后，超平面方程为。这时，被错分为；被错分为。令学习步长，试用感知器算法确定分类器参数，并画图表示分类器超平面的变化过程。迭代一次即可，假设学习结束后没有样本被错分。 解：分类器在第次学习结束后的权值向量为，由式（3.16）得 画出图形如例2图所示。 3.3 超维分界平面的确定—最小法（） 目标（期望、理想）输出为 设所求超维决策平面的参数为，我们将输入数据阵X增加元素全为‘1’的列向量，记为 令线性分类器的实际输出向量为 则有 对第p个样本，分类器的实际输出为 它与理想输出之间的误差为 对整个训练集而言，分类器的误差平方和为 对E求关于的一阶偏导数 这是一个列向量。令，得 在可逆的条件下，有 该方法也被称