第3章线性分类器
上一章介绍了基于概率的分类
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
,所有类具有相同协方差矩阵的正态分布问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
等价于一组线性判别函数。实际问题类条件概率密度估计比较困难,可以直接根据训练样本设计分类器。本章中假设问题是线性可分的。
3.2线性判别函数和决策超平面
考虑两类问题,在
维空间决策面是一个超平面
(3.1)
其中
是权向量,设
是决策面上两点,
(3.2)
即
与决策面。
3.3感知算法
决策面有
确定,对于给定问题关键是如何确定
。即确定
,满足
感知器代价函数定义为:
Y是错误分类的向量集合,
显然
当Y是空集时
,此时所有向量都正确分类。
采用梯度下降法迭代求最优
:
是正实数(学习系数、学习率)。
图3.2给出了感知器算法的几何解释。可以证明量
满足一定条件时算法收敛。
另一种感知器算法
前面算法是所有训练样本计算完成统一调一次权值
,可以采用一个样本一调的方法
即正确分类不改变权向量,错误改变权向量。可以证明算法是收敛的。
感知器
当设计好
后可以用来分类:
见图(3.3),模拟神经元的模型,称为感知器。
例3.1,设感知器算法得到x1+x2-0.5=0(图3.4)虚拟
除了(0.4 0.05)T和(-0.2 0.75)T外都已正确分类。
两样本都正确分类,实线
袋式算法
前面算法收敛条件是线性可分性。不满足将不收敛,而袋式算法可以收敛到理想解:
Pocket Algeriehm
1.随机初始化权向量
定义存储向量
,设
的
记数器hs=0。
2.在t次迭代中,由感知器规则更新
,用
检测正确分类的训练向量个数h。若h>hs,用
代替
,用h代替hs该算法得到的
是正确分类样本最多的权向量。
Kesler结构
前面讨论的两类问题分类方法可以直接推广到M类问题,每类定义一个线性判别函数
,
若
则
对
中的每一个向量构造M-1个
维向量
构造向量
,若
则
即
通过扩展将分类问题变为不等式约束问题。可以用线性判别函数分类:
例:在二维空间中考虑三类的问题。训练向量如下:
坐标轴可以将样本正确分类,是线性可分的
Keslex结构:
同理可以得到另12个向量,权向量为
显然要求这18个9组向量满足
,使用感知器算法确定
初始化为[0,1]随机数,学习率
=0.5,算法四次迭代收敛
正确分类
不准,只要正确分类(所有样本)算法结束。
3.4最小二乘法
前面介绍的方法适用于线性可分问题,对于非线性可分问题,用线性分类前面的算法可能不收敛。采用优化算法,定义代价函数,最小值的权向量确定分类。
3.4.1均方误差估计
对两类问题,给定特征向量
,分类器输入
,期望输出
。确定
使期望值和真实值的均方误差最小。
Rx是自相关矩阵。
(3.27)
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
明误差
与
正交,
是y在子空间上的正交投影。
多类情况
用均方准则设计M个线性判别函数
,定义期望输出
定义
,
,则最小均方误差
等价于M个独立的均方误差最小化问题(?)√
不同类无关
3.4.2随机逼近和LMS算法
前面最小二乘法需要知道自相关和互相关矩阵等统计信息,而实际问题一般未知。随机逼近法可以不适用这些信息确定
,考虑方程
xk是同一个随机向量,F(0,0)是一个函数,采用迭代法解
即用随机变量样本代替均值,若
收敛。
例:方程E[xk-w]=0,取
则
迭代解与是方程解得估计——样本均值
将之用于(3.27)
称为最小均方算法,实际中广泛应用(自适应滤波)
3.4.3误差平方和估计
误差平方和是与均方差相关的准则:
要求X的秩是
(向量xi维数),X+=(XTX)-1XT是x伪逆,当N=
时X+=x-1,但实际一般N>>
。 (3.31)
可以证明,多类问题的均方准则得到的判别函数gi(x)满足:
即
是
的均方估计(MSE)。
3.6支持向量机
前面的感知机算法得到的分类超平面不唯一,且对未知样本的分类不合适。支持向量机(SVM,Support Vector Machine)可以很好地解决此问题。