1、第3章线性判别分析第三章第三章 线性判别分析线性判别分析 非参数判别分类方法非参数判别分类方法第3章线性判别分析本章内容本章内容3.1线性判别函数线性判别函数3.2线性分类器线性分类器 Fisher线性判决线性判决 感知准则函数感知准则函数 3.3分段线性分类器分段线性分类器3.4近邻分类器近邻分类器总结总结习题习题第3章线性判别分析3.2.2Fisher线性判决线性判决u Fisher线性判决的基本思想线性判决的基本思想是寻找一个最好的投影方向是寻找一个最好的投影方向, 当特征向量当特征向量x从从d维空间映射到维空间映射到这个方向上时这个方向上时, 两类能最好地两类能最好地分开。分开。u 这
2、个方法实际上涉及这个方法实际上涉及特征维特征维数的压缩数的压缩问题。问题。3.2线线 性性 分分 类类 器器第3章线性判别分析分析分析w1方向之所以比方向之所以比w2方向优方向优越越, 可以归纳出这样一个准则：可以归纳出这样一个准则：即向即向量量w的方向选择应能使两类样本投的方向选择应能使两类样本投影的均值之差尽可能大些影的均值之差尽可能大些, 而使类内而使类内样本的离散程度尽可能小样本的离散程度尽可能小。这就是。这就是Fisher准则函数的基本思路。准则函数的基本思路。第3章线性判别分析第一步：计算参量。第一步：计算参量。(1) 各类样本的均值向量各类样本的均值向量i: 1 (1,2)iii
3、iNxx(2) 样本类内离散度矩阵样本类内离散度矩阵Si：()() (1,2)iTiiiixSxx12wSSS总类内离散度矩阵总类内离散度矩阵Sw: *112()wwS第二步：计算最优投影方向，第二步：计算最优投影方向，并将样本往该方向上投影并将样本往该方向上投影。 xwTy)(*第三步：决策。第三步：决策。在投影空间内的决策准则为在投影空间内的决策准则为: 若若yy0, 则则x1, 否则否则x2。Fisher线性判决步骤线性判决步骤第3章线性判别分析n采用类似于人认知错误、纠正错误、通过自学习改善自采用类似于人认知错误、纠正错误、通过自学习改善自己认识事物本领的过程，己认识事物本领的过程，随
4、意确定判别函数初始值，该随意确定判别函数初始值，该值在对样本分类训练过程中逐步修正直至最终确定。值在对样本分类训练过程中逐步修正直至最终确定。n 基本思想基本思想：寻找一个权向量，使规范化增广样本向量集：寻找一个权向量，使规范化增广样本向量集的错分类样本数最少。的错分类样本数最少。 3.2.3 感知准则函数感知准则函数 第3章线性判别分析一、基本概念一、基本概念1.1.线性可分性线性可分性 已知来自已知来自1和和2两类的样本集两类的样本集x1, x2, , xN, 两类的两类的线线性性判决函数为判决函数为yi为增广样本向量为增广样本向量, v为增广权向量为增广权向量。()Tiig yv y线性
5、可分：线性可分：如果存在一个线性分类器能把每个样本正确分类如果存在一个线性分类器能把每个样本正确分类, 即若即若存在一个权向量存在一个权向量v, 使得对于任何使得对于任何yi1, 都有都有vTyi0, 而对而对于任何于任何yi2, 都有都有vTyi0。规范化规范化增广样本向量增广样本向量21iiiiiyyyyz 经过这样的变换后经过这样的变换后, 我们可以不考虑样本原来的类别标我们可以不考虑样本原来的类别标志志, 只要找到一个对全部样本只要找到一个对全部样本zi都满足都满足vTzi0(i=1, 2, , N)的的权向量即可。权向量即可。 样本的规范化样本的规范化第3章线性判别分析3. 解向量和
6、解区解向量和解区满足满足vTzi0(i=1, 2, , N)的的权向量称为解向量权向量称为解向量。 若把若把v看成是权向量空间中看成是权向量空间中的一点的一点, 对于任一对于任一zi, vTzi=0在权向在权向量空间确定了一个超平面量空间确定了一个超平面, 这个这个超平面把权空间分为两个半空间超平面把权空间分为两个半空间, 该超平面的法向量为该超平面的法向量为zi , 超平面超平面正侧的向量满足正侧的向量满足vTzi0。第3章线性判别分析 相应地相应地, N个样本确定了个样本确定了N个超平面个超平面, 每个超平面把每个超平面把权空间分为两个半空间。所以权空间分为两个半空间。所以, 满足满足vT
7、zi0(i=1, 2, , N)的的权向量必在这权向量必在这N个超平面正侧的交叠区个超平面正侧的交叠区, 称这一交叠区为称这一交叠区为解区解区, 解区中的任意向量都是解区中的任意向量都是解向量解向量v*。第3章线性判别分析二、感知准则函数二、感知准则函数感知准则函数方法感知准则函数方法利用错分类对现决策权向量进行修正直至收利用错分类对现决策权向量进行修正直至收敛敛。这种方法只对。这种方法只对线性可分情况适用线性可分情况适用，并且只适用于，并且只适用于两类判决两类判决。感知准则函数方法的思路感知准则函数方法的思路是：先随意找一个初始向量是：先随意找一个初始向量v，写作，写作v(0)，然后用训练样
8、本集中的每个样本来计算。一旦发现有的，然后用训练样本集中的每个样本来计算。一旦发现有的zi，使，使vTzi0, 则引入余量后的解区在原解区之内。则引入余量后的解区在原解区之内。 将上式写将上式写成矩阵形式即为成矩阵形式即为 0 ( 1,2,)Tiiz vbiNZ vb 12TTTNzzZz12Nbbbb第3章线性判别分析定义误差向量定义误差向量: eZ vb 定义定义平方误差准则函数平方误差准则函数: 221( )()NTsiiiJvev zbJs(v)是一个是一个非负函数非负函数, 当当 有解时有解时, Js(v)达到最小值达到最小值0, 此时的矢量此时的矢量v*满足满足: Z vb * (
9、)0 (1,2,)TiivzbiNv*能将所有样本正确分类。能将所有样本正确分类。 若若v*不能使某个样本不能使某个样本zj正确分类正确分类, 即即(v*)Tzjbj, 则则e2j=(vTzjbj)2。 错分样本的结果是使错分样本的结果是使Js(v)增大增大, 因此因此, Js(v)越小越好越小越好, 其其最小值最小值0为理想分类结果为理想分类结果, 实现所有样本的正确分类。实现所有样本的正确分类。 求使求使Js(v)最小的最小的v*有两种方法有两种方法: 梯度下降法和解析法。梯度下降法和解析法。 第3章线性判别分析1. 1. 梯度下降法梯度下降法对对Js( (v) )求梯度求梯度( )2()
10、TsJvZZvb(3-78)(3-78)相应地相应地, ,梯度下降算法为梯度下降算法为 (1)( )( )Tkv kv kZZv kb其中，其中，k为为学习速率学习速率; ; 初值初值v(0)(0)可任意选取。可任意选取。 第3章线性判别分析2. 解析法解析法解析法得到的是伪逆解。解析法得到的是伪逆解。 令令Js(v)=0得得*TTZ ZvZ b(3-79)其中其中*1()TTvZ ZZ bZ b(3-80)ZTZ为为(d+1)(d+1)方阵方阵, 一般是满秩的一般是满秩的, 因此有唯一解因此有唯一解: -1()TTZZ ZZ(3-81)是是Z的左逆矩阵的左逆矩阵, Z的右逆矩阵定义为的右逆矩
11、阵定义为 1()TZZ Z Z(3-82)b的典型值为的典型值为 (1,1,1)Tb 第3章线性判别分析3.3 分段线性分类器分段线性分类器 线性分类器的分界面是一个超平面线性分类器的分界面是一个超平面。当类与类之间。当类与类之间不能用任何一个超平面实现划分时不能用任何一个超平面实现划分时, 类间的分界面应是类间的分界面应是一个超曲面。曲线可以由多个线段近似表达一个超曲面。曲线可以由多个线段近似表达, 曲面可以曲面可以由多个平面逼近由多个平面逼近, 因此因此, 可以可以用多个超平面近似表达超用多个超平面近似表达超曲面曲面, 分段线性分类器正是基于这种思路而设计的一种分段线性分类器正是基于这种思
12、路而设计的一种分类器。分类器。 第3章线性判别分析u线性判决函数只能解决线线性判决函数只能解决线性可分问题。性可分问题。u在线性不可分的情况下，在线性不可分的情况下，可以采用可以采用分段线性判别分段线性判别或或二次函数判别二次函数判别等方法等方法。u分段线性判决函数确定的分段线性判决函数确定的决策面是由决策面是由若干段超平面若干段超平面组成的。组成的。3.3.1 分段线性分类器的定义分段线性分类器的定义第3章线性判别分析 与线性判别函数相比，分段线性判别函数设计中与线性判别函数相比，分段线性判别函数设计中首先首先要解决的问题是分段线性判别函数的要解决的问题是分段线性判别函数的分段段数分段段数问
13、题。问题。u分段段数过少，其分类效果必然要差；但段数又要尽分段段数过少，其分类效果必然要差；但段数又要尽可能少，以免分类判别函数过于复杂，增加分类决策可能少，以免分类判别函数过于复杂，增加分类决策的计算量。的计算量。u在有些实际的分类问题中，同一类样本可以用若干个在有些实际的分类问题中，同一类样本可以用若干个子类来描述，这些子类来描述，这些子类的数目子类的数目就可作为确定分段段数就可作为确定分段段数的依据。的依据。u在有些情况下样本分布及合适子类划分并不知道，往在有些情况下样本分布及合适子类划分并不知道，往往需要采用一种往需要采用一种聚类的方法聚类的方法，设法将样本划分成相对，设法将样本划分成
14、相对密集的子类，然后用各种方法设计各段判别函数。密集的子类，然后用各种方法设计各段判别函数。第3章线性判别分析把属于类把属于类i的样本区域的样本区域Ri分为分为li个两两不相交的子区个两两不相交的子区, 对每对每个子类定义一个线性判决函数个子类定义一个线性判决函数: 0( )() (1,2, 1,2,)llTliiiigxxwllimw定义类定义类i的的判别函数判别函数: 1,2, ,( )max( ) (1,2, )iliillg xg xim判决准则为判决准则为 若若 ，则，则xj ( )max( )jiigxg x称称gi(x)(i=1, 2, , m)为分段线性判决函数为分段线性判决函
15、数, 相应的分类器称为相应的分类器称为分段线性分类器。分段线性分类器。第3章线性判别分析当类由多个子类构成时当类由多个子类构成时, 其决策面方程是由各子其决策面方程是由各子类的判决函数确定的类的判决函数确定的, 若第若第i类的第类的第n个子类和第个子类和第j类的类的第第k个子类相邻个子类相邻, 则该段决策面方程为则该段决策面方程为 ( )( )nkijgxgx其中其中, n1, 2, , li, k1, 2, , lj, li和和lj分别表示分别表示第第i类和第类和第j类的子类数目。类的子类数目。 第3章线性判别分析3.3.2 分段线性距离分类器分段线性距离分类器 正态分布条件下，两类别问题在
16、各特征统计独立、同方差、正态分布条件下，两类别问题在各特征统计独立、同方差、且先验概率相等情况下，最小错误率决策可按最小距离决策，且先验概率相等情况下，最小错误率决策可按最小距离决策，最小距离分类器的最小距离分类器的判决函数判决函数为为即即这时这时类间的决策面类间的决策面为为 2212-xx它是它是两类均值点连线的垂直平分面两类均值点连线的垂直平分面。 221122xxx 2211220 xxx 第3章线性判别分析 显然最小距离判别方法只有在显然最小距离判别方法只有在各类别密集地分布在其均各类别密集地分布在其均值附近值附近时才有效。时才有效。最小距离分类器最小距离分类器两类物体在特征空间的分布
17、两类物体在特征空间的分布n 对右图所示的情况按最小距离计算，就会将原来对右图所示的情况按最小距离计算，就会将原来类的类的x决策成决策成2类，如不对类，如不对类进行子类划分，或采用别的决策就类进行子类划分，或采用别的决策就不会取得好的效果。不会取得好的效果。第3章线性判别分析u右图所示情况，若企图再用右图所示情况，若企图再用每类一个均值代表点产生最每类一个均值代表点产生最小距离分类器，就会产生很小距离分类器，就会产生很明显的错误率。明显的错误率。u在这种情况下，可以将各类在这种情况下，可以将各类别划分成相对密集的子类，别划分成相对密集的子类，每个子类以它们的均值作为每个子类以它们的均值作为代表点
18、，代表点，然后按最小距离分然后按最小距离分类，可以有比较满意的效果。类，可以有比较满意的效果。u 对样本进行对样本进行子类的合适划子类的合适划分分是分段线性距离分类器性是分段线性距离分类器性能好坏的一个关键问题。能好坏的一个关键问题。分段线性距离分类器示意图分段线性距离分类器示意图第3章线性判别分析归纳起来，如果对于归纳起来，如果对于i有有li个子类，则有个子类，则有li个代表点，或者个代表点，或者说将类说将类i的样本区域的样本区域Ri分为分为li个子区个子区: 12iliiiiRRRR其中其中, 1212, jjiiRRjj。用用mli表示表示Rli中的均值向量中的均值向量, 并以此作为该子
19、区的代表并以此作为该子区的代表点点, 确定确定判别函数判别函数: 1,2,( )miniliillg xxm则则判决准则判决准则为为 若若1,2,( )min( )jiimgxgx， 则则xj 称这种分类器为称这种分类器为分段线性距离分类器分段线性距离分类器。 第3章线性判别分析注意：注意： 线性距离分类器使用的是马氏距离线性距离分类器使用的是马氏距离, 分段分段线性距离分类器使用的则是欧几里德距离线性距离分类器使用的则是欧几里德距离, 由最小距由最小距离分类器的导出过程可知离分类器的导出过程可知, 仅当所有子区的协方差阵仅当所有子区的协方差阵相同且等于相同且等于2I时时, 才具有较好的分类效
20、果。才具有较好的分类效果。 第3章线性判别分析 设计分段线性分类器的前提条件是有一组已知类别的设计分段线性分类器的前提条件是有一组已知类别的样本集样本集, 其关键在于解决以下两个问题其关键在于解决以下两个问题: (1) 根据样本集根据样本集确定子类数目及各子类的划分确定子类数目及各子类的划分; (2) 利用样本集利用样本集计算各子类判别函数的权向量和阈值权。计算各子类判别函数的权向量和阈值权。 根据已知条件的不同根据已知条件的不同, 可以分别采取不同的方法。可以分别采取不同的方法。3.3.3 分段线性分类器设计的一般考虑分段线性分类器设计的一般考虑 (1)子类数目及各子类划分已知；子类数目及各
21、子类划分已知；(2)子类数目已知子类数目已知, 各子类划分不知；各子类划分不知；(3)子类数目未知。子类数目未知。第3章线性判别分析u最初的近邻法是由最初的近邻法是由Cover和和Hart于于1968年提出的，是非参年提出的，是非参数法中最重要的方法之一。数法中最重要的方法之一。 u最小距离分类器将各类训练样本划分成若干子类，并在每最小距离分类器将各类训练样本划分成若干子类，并在每个子类中确定代表点，一般用子类的均值或邻近均值的某个子类中确定代表点，一般用子类的均值或邻近均值的某一样本为代表点。一样本为代表点。实质就是将样本判属于与代表点距离最实质就是将样本判属于与代表点距离最近的类。近的类。
22、u该法的该法的缺点缺点是所选择的代表点并不一定能很好地代表各类，是所选择的代表点并不一定能很好地代表各类，其后果将使错误率增加。其后果将使错误率增加。3.4 近邻分类器近邻分类器第3章线性判别分析3.5.1 最近邻法最近邻法一、最近邻法的原理及判决准则一、最近邻法的原理及判决准则u近邻法的基本思想近邻法的基本思想：以全部训练样本作为：以全部训练样本作为“代表代表点点”，计算测试样本与这些，计算测试样本与这些“代表点代表点”，即所有，即所有样本的距离，并以最近邻者的类别作为决策。样本的距离，并以最近邻者的类别作为决策。u其主要特点就是将样本判属它的最近邻（和它距其主要特点就是将样本判属它的最近邻
23、（和它距离最近的代表点）所在的类。离最近的代表点）所在的类。第3章线性判别分析 假定有假定有m个类别个类别1, 2, , m的模式识别问的模式识别问题题, 每类有每类有Ni(i=1, 2, , m)个样本个样本, 规定类规定类i的的判判别函数别函数为为( )min 1,2,kiiiig xxxkN其中其中, 表示第表示第i类的第类的第k个元素。个元素。 kix判决准则判决准则: 若若1,2,( )min( )jiimgxg x，则，则xj 第3章线性判别分析第3章线性判别分析二、错误率分析二、错误率分析u最近邻法的错误概率最近邻法的错误概率比最小错误概率判决准则的错误概比最小错误概率判决准则的
24、错误概率要大，但是当样本数目无限时，它的错误概率率要大，但是当样本数目无限时，它的错误概率不会超不会超过后者的错误概率的一倍过后者的错误概率的一倍。u假设近邻分类器的渐近平均错误概率为假设近邻分类器的渐近平均错误概率为P, , 最小错误概最小错误概率判决准则的错误概率为率判决准则的错误概率为P*e , , 那么它们之间存在如下关那么它们之间存在如下关系系: : )12(*eeePmmPPP其中其中m为类别数为类别数, )(limePPNNPN(e)是当样本数为是当样本数为N 时近邻分类器的平均错误概率。时近邻分类器的平均错误概率。第3章线性判别分析图中曲线与直线分别图中曲线与直线分别是近邻法分
25、类器当是近邻法分类器当N时渐近平均错误时渐近平均错误概率的上、下界概率的上、下界, 具体具体的的P落在图中阴影区落在图中阴影区内。内。 )12(*eeePmmPPPP的上、的上、 下界下界 第3章线性判别分析3.5.2 k近邻法近邻法一、一、k近邻法的原理及判决准则近邻法的原理及判决准则u最近邻分类器最近邻分类器的判决思想是将样本判属与它距离的判决思想是将样本判属与它距离最小的样本所属的类。最小的样本所属的类。u这种方法的特点是概念容易理解，最近邻样本和这种方法的特点是概念容易理解，最近邻样本和待分类样本在距离意义下是最相似的。待分类样本在距离意义下是最相似的。u其缺点在于其缺点在于受随机噪声
26、影响较大，尤其是在两类受随机噪声影响较大，尤其是在两类的交叠区内。的交叠区内。第3章线性判别分析u例如下图有例如下图有两类样本点。图中有两个待识别样本，其中点两类样本点。图中有两个待识别样本，其中点1落在第一类落在第一类较密集的区域内，它属于第一类的可能性较大，但点较密集的区域内，它属于第一类的可能性较大，但点1的最近邻为第二的最近邻为第二类的样本，而该样本对于第二类的区域而言属于因较大的随机误差引类的样本，而该样本对于第二类的区域而言属于因较大的随机误差引起的样本；点起的样本；点2落在第二类较密集的区域内，属于第二类的可能性较大，落在第二类较密集的区域内，属于第二类的可能性较大，但点但点2的
27、最近邻为第一类的样本，而该样本对于第一类的区域而言属于的最近邻为第一类的样本，而该样本对于第一类的区域而言属于因较大的随机误差引起的样本。因较大的随机误差引起的样本。随机噪声对最近邻分类结果的影响随机噪声对最近邻分类结果的影响第3章线性判别分析对于待分类样本对于待分类样本x, 在在N个样本集中找出它的个样本集中找出它的k个近个近邻邻, 设设k个样本中属于第个样本中属于第i类的为类的为ki个个(i=1, 2, , m), 即即mkkkk21定义定义判别函数判别函数: ( ) , 1,2,iig xkim判决准则判决准则为为 若若( )maxjiigxk，则，则 xj称这种方法为称这种方法为k近邻
28、法近邻法, 相应的分类器称为相应的分类器称为k近邻分类器近邻分类器。 第3章线性判别分析8近邻示意图近邻示意图 对于下图中的样本点对于下图中的样本点, 若按若按8近邻方法判决近邻方法判决, 则点则点1的的8近邻中近邻中, k1=6, k2=2, 所以应判属第一类；点所以应判属第一类；点2的的8近邻中近邻中, k1=2, k2=6, 所以应判属第二类。所以应判属第二类。第3章线性判别分析二、错误率分析二、错误率分析 k近邻一般采用近邻一般采用k为奇数为奇数，跟投票表决一样，避免，跟投票表决一样，避免因两种票数相等而难以决策。因两种票数相等而难以决策。k近邻分类器的渐近平均错误概率也满足近邻分类器
29、的渐近平均错误概率也满足: *(2)1eeemPPPPm其中其中, P*e为最小错误概率的贝叶斯分类器的错误概率。为最小错误概率的贝叶斯分类器的错误概率。 第3章线性判别分析近邻法近邻法优点：优点：在模板数量很大时其错误率指标还是相当不错的。在模板数量很大时其错误率指标还是相当不错的。缺点：缺点：需要存储全部训练样本，另外有繁重的距离计算量，即需要存储全部训练样本，另外有繁重的距离计算量，即计算量大，存储量大。计算量大，存储量大。剪辑近邻法与压缩近邻法剪辑近邻法与压缩近邻法就是两种有代表性的改进方法。就是两种有代表性的改进方法。 3.5.3 近邻法的改进方法近邻法的改进方法第3章线性判别分析
30、剪辑近邻法剪辑近邻法，其，其基本原理基本原理是在原有样本集中挑是在原有样本集中挑选出对分类计算有效的样本，将不同类别交界选出对分类计算有效的样本，将不同类别交界处的样本以适当方式进行筛选处的样本以适当方式进行筛选，把处于交界处把处于交界处的训练样本给剪辑掉的训练样本给剪辑掉，使，使样本总数合理地减少，样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双以同时达到既减少计算量，又减少存储量的双重效果。重效果。 压缩近邻法压缩近邻法，其，其基本原理基本原理是对样本集进行组织是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范
31、围内，避免盲目地与训近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算。练样本集中每个样本进行距离计算。第3章线性判别分析一、剪辑近邻法一、剪辑近邻法剪辑近邻法着眼于如何剪辑近邻法着眼于如何减少模板样本数目减少模板样本数目，从而可同时，从而可同时减少减少分分类时的类时的计算量计算量及模板样本的及模板样本的存储量存储量，同时还能进一步改进，同时还能进一步改进分类器的性能，如分类器的性能，如降低错误率降低错误率等要求。等要求。剪辑近邻法的剪辑近邻法的基本思想基本思想是从这样一个现象出发的，即当不同类是从这样一个现象出发的，即当不同类别的样本在分布上有交迭部分，分类的错误率主要来
32、自处别的样本在分布上有交迭部分，分类的错误率主要来自处于交迭区中的样本。当我们得到一个作为识别用的参考样于交迭区中的样本。当我们得到一个作为识别用的参考样本集时，由于不同类别交迭区域中不同类别的样本彼此穿本集时，由于不同类别交迭区域中不同类别的样本彼此穿插，导致用近邻法分类出错。因此如果插，导致用近邻法分类出错。因此如果能将不同类别交界能将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。为此可以利用现有样本集对其自正确识别率的双重目的。为此可以利用现有样本集对其自身进行剪辑。身进行剪辑。 第3章线性判别分析
33、用近邻法容易出错的区域是在两类的交界处，这时用近邻法容易出错的区域是在两类的交界处，这时某个训练样本存在与否就会影响到某些测试分类的结果。某个训练样本存在与否就会影响到某些测试分类的结果。因此剪辑的效果往往把这些处于交界的训练样本给剪辑因此剪辑的效果往往把这些处于交界的训练样本给剪辑掉了。掉了。 第3章线性判别分析二、压缩近邻法二、压缩近邻法剪辑近邻法所得到的剪辑样本集在样本数量的压缩方面并不十剪辑近邻法所得到的剪辑样本集在样本数量的压缩方面并不十分明显，它的作用在于将原样本集中处于边界处的样本删除分明显，它的作用在于将原样本集中处于边界处的样本删除掉，但靠近两类中心的大部分样本仍被保留下来。
34、然而按近掉，但靠近两类中心的大部分样本仍被保留下来。然而按近邻规则来看，这些样本中的大多数对分类决策没什么用处，邻规则来看，这些样本中的大多数对分类决策没什么用处，如能在剪辑的基础上再去掉一部分这样的样本，将有助于进如能在剪辑的基础上再去掉一部分这样的样本，将有助于进一步缩短计算时间与压缩存储量。一步缩短计算时间与压缩存储量。其实处于同一类样本密集区的测试样本并不一定要全部保留，其实处于同一类样本密集区的测试样本并不一定要全部保留，几乎绝大部分都可去掉，只要保留若干个训练样本即可。问几乎绝大部分都可去掉，只要保留若干个训练样本即可。问题是保留哪些好。压缩近邻法采用了用测试集测试的办法，题是保留
35、哪些好。压缩近邻法采用了用测试集测试的办法，采用采用只要分类有错，在出错处添加一个训练样本的做法。只要分类有错，在出错处添加一个训练样本的做法。第3章线性判别分析压缩近邻压缩近邻法压缩样本的思想很简单，它利用现有样本集，逐法压缩样本的思想很简单，它利用现有样本集，逐渐生成一个新的样本集。使该样本集在保留最少量样本的渐生成一个新的样本集。使该样本集在保留最少量样本的条件下条件下, 仍能对原有样本的全部用最近邻法正确分类，那仍能对原有样本的全部用最近邻法正确分类，那末该样本集也就能对待识别样本进行分类末该样本集也就能对待识别样本进行分类, 并保持正常识并保持正常识别率。该算法的作法也十分简单，它别
36、率。该算法的作法也十分简单，它定义两个存储器定义两个存储器，一，一个用来存放即将生成的样本集，称为个用来存放即将生成的样本集，称为Store；另一存储器则；另一存储器则存放原样本集，称为存放原样本集，称为Grabbag。第3章线性判别分析 1.初始化初始化Store是空集，原样本集存入是空集，原样本集存入Grabbag；从；从Grabbag中任意选择一样本放入中任意选择一样本放入Store中作为新样本集的第一个样本。中作为新样本集的第一个样本。 2.样本集生成在样本集生成在Grabbag中取出第中取出第i个样本用个样本用Store中的当前中的当前样本集按最近邻法分类。若分类错误，则将该样本从样
37、本集按最近邻法分类。若分类错误，则将该样本从Grabbag转入转入Store中，若分类正确，则将该样本放回中，若分类正确，则将该样本放回Grabbag中，对中，对Grabbag中所有样本重复上述过程。中所有样本重复上述过程。 3.结束过程若结束过程若Grabbag中所有样本在执行第二步时没有发生中所有样本在执行第二步时没有发生转入转入Store的现象，或的现象，或Grabbag已成空集，则算法终止，否则转已成空集，则算法终止，否则转入第二步。入第二步。 在算法终止后，在算法终止后，Store中的样本集作为压缩样本集，可用来中的样本集作为压缩样本集，可用来对待识别样本按最近邻法分类。对待识别样本
38、按最近邻法分类。压缩近邻法算法步骤：压缩近邻法算法步骤：第3章线性判别分析本章小结本章小结 u参数判别分类方法与非参数判别分类方法参数判别分类方法与非参数判别分类方法u线性判别函数和决策面方程线性判别函数和决策面方程uFisher线性判决准则线性判决准则u感知准则函数感知准则函数u最小平方误差准则函数最小平方误差准则函数u分段线性分类器分段线性分类器u近邻分类器近邻分类器第3章线性判别分析参数判别分类方法与非参数判别分类方法参数判别分类方法与非参数判别分类方法参数判别方法：参数判别方法： 适用条件：前提是清楚特征空间中的各类样本的分布，一旦适用条件：前提是清楚特征空间中的各类样本的分布，一旦待
39、分类样本的特征向量值待分类样本的特征向量值x已知，就可以确定已知，就可以确定x对各类的后验概对各类的后验概率，也就可按相应的准则计算与分类。参数分类判别方法一般率，也就可按相应的准则计算与分类。参数分类判别方法一般只能用在有统计知识的场合，或能利用训练样本估计出参数的只能用在有统计知识的场合，或能利用训练样本估计出参数的场合。场合。 判别函数类型如何确定？判别函数类型如何确定？ 判别函数及决策面方程的类别确定是由样本分布规律决定判别函数及决策面方程的类别确定是由样本分布规律决定的，例如，符合某种条件就可使用线性分类器，正态分布条件的，例如，符合某种条件就可使用线性分类器，正态分布条件下一般适合
40、用二次函数决策面。下一般适合用二次函数决策面。第3章线性判别分析参数判别分类方法与非参数判别分类方法参数判别分类方法与非参数判别分类方法非参数分类判别方法：非参数分类判别方法：直接利用训练样本集，省去参数估计这一环节直接利用训练样本集，省去参数估计这一环节，根据，根据一些准则一些准则(如如Fisher准则、感知准则函数准则、感知准则函数)来设计分类器。来设计分类器。 判别函数类型如何确定？判别函数类型如何确定？ 在非参数判别方法的设计中，在非参数判别方法的设计中，使用什么典型的分使用什么典型的分类决策方法预先由设计者确定，然后利用训练样本集类决策方法预先由设计者确定，然后利用训练样本集提供的信
41、息确定这些函数中的参数。提供的信息确定这些函数中的参数。这是参数与非参这是参数与非参数判别方法的一个重要不同点。数判别方法的一个重要不同点。第3章线性判别分析非参数分类判别方法的基本做法：非参数分类判别方法的基本做法： 使用非参数分类判别方法进行分类器设计主使用非参数分类判别方法进行分类器设计主要包含两个步骤：选择函数类型与确定参数。要包含两个步骤：选择函数类型与确定参数。 确定使用的判别函数类型或决策面方程类型，确定使用的判别函数类型或决策面方程类型，如线性分类器、非线性分类器、分段线性分类如线性分类器、非线性分类器、分段线性分类器或近邻法等。器或近邻法等。 在选定的函数类型条件下，在选定的
42、函数类型条件下，确定相应的参数确定相应的参数，从而完成整个分类器设计。从而完成整个分类器设计。第3章线性判别分析其中其中wi是权向量是权向量,wi0是一个常数，称为阈值权。是一个常数，称为阈值权。设样本在设样本在d维特征空间中描述，两类问题维特征空间中描述，两类问题线性判别线性判别函数的一般形式函数的一般形式可表示成可表示成Ti0( )wiig xxw判决准则的可以表示为判决准则的可以表示为 线性判别函数和决策面方程线性判别函数和决策面方程第3章线性判别分析在线性判别函数条件下，它是在线性判别函数条件下，它是d维空间的一个超维空间的一个超平面。平面。相应的决策面方程为相应的决策面方程为T01
43、1220( )w0ddg xxww xw xw xw12w(,)Tdw ww12(,)Tdxx xx其中其中,第3章线性判别分析n基本思想基本思想：寻找一个最好的投影方向，当特征：寻找一个最好的投影方向，当特征向量从向量从d 维空间映射到这个方向时，两类能最维空间映射到这个方向时，两类能最好地分开。好地分开。nFisher准则函数的基本思路：准则函数的基本思路：向量向量w的方向选的方向选择应能使两类样本在该向量上投影的交迭部分择应能使两类样本在该向量上投影的交迭部分最少最少,投影的均值之差尽可能大些，而使类内样投影的均值之差尽可能大些，而使类内样本的离散程度尽可能小。本的离散程度尽可能小。Fi
44、sher线性判决准则线性判决准则 第3章线性判别分析第一步：计算参量。第一步：计算参量。(1) 各类样本的均值向量各类样本的均值向量i: 1 (1,2)iixixiN(2) 样本类内离散度矩阵样本类内离散度矩阵Si()() (1,2)iTiiixSxxi12wSSS总类内离散度矩阵总类内离散度矩阵Sw: *112()wSw第二步：计算最优投影方向，第二步：计算最优投影方向，并并 将样本往该方向上投影将样本往该方向上投影。 *()Tyx w第三步：决策。第三步：决策。在投影空间内的决策准则为在投影空间内的决策准则为: 若若yy0, 则则x1, 否则否则x2。步骤步骤第3章线性判别分析感知准则函数
45、感知准则函数n这种方法只对线性可分情况适用。适用于两类判决这种方法只对线性可分情况适用。适用于两类判决。n基本思想基本思想：寻找一个增广权向量：寻找一个增广权向量v，使规范化增广样，使规范化增广样本向量集的错分类样本数最少。本向量集的错分类样本数最少。第3章线性判别分析感知准则函数方法的思路感知准则函数方法的思路是：先随意找一个初始向量是：先随意找一个初始向量v，写作，写作v(0)，然后用训练样本集中的每个样本来计算。，然后用训练样本集中的每个样本来计算。一旦发现有的一旦发现有的zi，使，使vTzi0，则说明当前的广义权向量，则说明当前的广义权向量v(0)不适合还需要进一步修正。不适合还需要进
46、一步修正。 感知准则函数感知准则函数n基本思想基本思想：寻找一个增广权向量：寻找一个增广权向量v，使规范化增广样，使规范化增广样本向量集的错分类样本数最少。本向量集的错分类样本数最少。n这种方法只对线性可分情况适用，并且适用于两类这种方法只对线性可分情况适用，并且适用于两类判决。判决。第3章线性判别分析 设设Z=z1, z2, , zN是经过规范化的一组样本集是经过规范化的一组样本集, 定义感知准则函数定义感知准则函数: ( )()kTpzZJvv z其中其中, Zk是被权向量是被权向量v错分类的样本集合错分类的样本集合, 当当zZk时时, 有有 0Tv z显然显然, Jp(v)0。 梯度下降
47、算法梯度下降算法求求Jp(v)准则函数的极小值。准则函数的极小值。迭代公式迭代公式为为 (1)( )kkz Zv kv kz其中其中( )0kTZz v kz即即Zk为第为第k步被错分的样本集步被错分的样本集。 k为正，是为正，是步长系数步长系数。第3章线性判别分析最小平方误差准则函数最小平方误差准则函数 Js(v)越小越好越小越好, 其最小值其最小值0为理想分类结果为理想分类结果, 实实现所有样本的正确分类。现所有样本的正确分类。 221( )()NTsiiiJvev zbn平方误差准则函数平方误差准则函数Js(v)为为第3章线性判别分析分段线性距离分类器分段线性距离分类器 正态分布条件下，
48、两类别问题在各特征统计独立、同方差、正态分布条件下，两类别问题在各特征统计独立、同方差、且先验概率相等情况下，最小错误率决策可按最小距离决策，且先验概率相等情况下，最小错误率决策可按最小距离决策，最小距离分类器的判决函数最小距离分类器的判决函数为为即即这时这时类间的决策面类间的决策面为为 2212-xx它是它是两类均值点连线的垂直平分面两类均值点连线的垂直平分面。 221122xxx 2211220 xxx 第3章线性判别分析近邻法近邻法 基本特点：将样本集中的任何一个样本都作为代表点。基本特点：将样本集中的任何一个样本都作为代表点。实质：将样本判属于与代表点距离最近的类。实质：将样本判属于与
49、代表点距离最近的类。第3章线性判别分析对于待分类样本对于待分类样本x, 在在N个样本集中找出它的个样本集中找出它的k个近个近邻邻, 设设k个样本中属于第个样本中属于第i类的为类的为ki个个(i=1, 2, , m), 即即mkkkk21定义定义判别函数判别函数: ( ) , 1,2,iig xkim判决准则判决准则为为 若若( )maxjiigxk，则，则 xjk近邻法近邻法第3章线性判别分析习习 题题1. 对于线性判决函数对于线性判决函数: 22)(21xxg x(1) 将判别函数写成将判别函数写成g(x)=wTx+w0的形式的形式, 画出画出 H: g(x)=0的几何图形的几何图形, 标出权向量并确定决策区域标出权向量并确定决策区域R1和和R2。 (2) 化成增广权向量和增广向量的形式化成增广权向量和增广向量的形式: g(x)=vTy。第3章线性判别分析 2.有七个二维向量有七个二维向量: 12341000,0110 xxxx 5600,22xx 720 x，假定前三个为假定前三个为1类类, 后四个为后四个为2类。类。(1) 画出最近邻法决策区域画出最近邻法决策区域; (2) 求样本均值求样本均值1、2; 若按离样本均值距离的大若按离样本均值距离的大小进行分类小进行分类, 试画出决策区域。试画出决策区域。 第3章线性判别分析
