第05章 线性判别函数 模式识别课程 哈工大.pptVIP

第五章 线性判别函数 5.1 线性判别函数和判别界面 线性不可分情况 线性判别函数 x=(x1, x2,…, xd)t: 特征矢量； w=(w1, w2, …, wd)t: 权矢量； w0：偏置(bias)。 线性判别函数的增广形式 x=(1, x1, x2,…, xd)t: 增广的特征矢量； a=(w0, w1, w2, …, wd)t: 增广的权矢量； 两类问题线性判别准则 线性分类器的分类界面 分类界面的几何解释 线性分类界面H是d维空间中的一个超平面； 分类界面将d维空间分成两部分，R1，R2分别属于两个类别； 判别函数的权矢量w是一个垂直于分类界面H的矢量，其方向指向区域R1 ； 偏置w0与原点到分类界面H的距离有关： 多类问题（情况一） 每一类模式可以用一个超平面与其它类别分开； 这种情况可以把c个类别的多类问题分解为c个两类问题解决，需要c个线性分类界面； 第i类与其它类别之间的判别函数： 多类问题（情况一）分类界面 多类问题（情况一）判别规则 若存在i，使得gi(x)0， gj(x)0，j≠i，则判别x属于ωi类； 其它情况，拒识。 多类问题（情况二） 每两个类别之间可以用一个超平面分开； c个类别的问题需要c(c-1)/2个线性分类界面； 第i类与第j类之间的判别函数为： 多类问题（情况二）分类界面 多类问题（情况二）判别准则 如果对任意j≠i ，有gij(x)≥0 ，则决策x属于ωi。 其它情况，则拒识。 多类问题（情况三） 情况三是情况二的特例，不存在拒识区域。 多类问题（情况三）判别函数 c个类别需要c个线性函数： 5.2 线性判别函数的学习 问题的提出：假设有一个包含n个样本的集合y1, y2, …, yn, 一些标记为ω1,另一些标记为ω2，用这些样本来确定一个判别函数g(x)=atx的权矢量a。 在线性可分的情况下，希望得到的判别函数能够将所有的训练样本正确分类； 线性不可分的情况下，判别函数产生错误的概率最小。 训练样本的规范化 解区域的几何解释(特征空间中） 特征空间中：矢量a是垂直于分类界面的矢量： 解区域的几何解释(权空间中） 权空间中，atyi=0是一个通过原点的超平面，yi是法向量，而a是空间中一个点。 一般求解方法—梯度下降法 求解不等式组采用的最优化的方法： 定义一个准则函数J(a)，当a是解向量时，J(a)为最小； 采用最优化方法求解标量函数J(a)的极小值。 最优化方法采用最多的是梯度下降法，设定初始权值矢量a(1)，然后沿梯度的负方向迭代计算： 5.3 感知器算法(Perceptron) 最直观的准则函数定义是最少错分样本数准则： JN(a) = 样本集合中被错误分类的样本数； 感知器准则 以错分样本到判别界面距离之和作为准则： 感知器算法(批量调整版本) begin initialize , ,θ, k?0 do k?k+1 until return a end 感知器算法(单样本调整版本) begin initialize , k?0 do k?(k+1)mod n if yk is misclassified by a then until all patterns properly classified return a end 例5.1 有两类模式的训练样本： ω1：{ (0,0), (0,1) } ω2：{ (1,0), (1,1) } 用感知器算法求取判别函数，将两类样本分开。 感知器算法的特点 当样本线性可分情况下，学习率 合适时，算法具有收敛性； 收敛速度较慢； 当样本线性不可分情况下，算法不收敛，且无法判断样本是否线性可分。 5.4 最小平方误差算法(LMSE) LMSE方法的基本思想是将求解线性不等式组的问题转化为求解线性方程组： 最小平方误差的准则函数 定义误差矢量e，用e长度的平方作为准则函数： 权值矢量的求解(伪逆求解法) 例5.2 有两类模式的训练样本： ω1：{ (0,0), (0,1) } ω2：{ (1,0), (1,1) } 用LMSE算法求取判别函数，将两类样本分开。 权值矢量的求解(迭代求解法) begin initialize a(0), b, θ, η(?), k?0； do k?k+1； until return a end LMSE算法的特点 算法的收敛依靠η(k)的衰减，一般取η(k)=η(1)/k； 算法对于线性不可分的训练样本也能够收敛于一个均方误差最小解； 取b=1时，当样