模式识别课件

3.5总体分布的非参数估计非参数估计优势：能处理任意的概率分布，不必假设概密的形式。

参数估计要求密度函数的形式已知，但有时并不成立。常见的一些函数形式很难拟合实际的概率密度，且许多都是单峰的，而在许多实际情况中却是多峰的，因此用非参数估计。①

用训练样本直接去估计类概率密度p(x/ωi)以此来设计分类器,如窗口估计

当样本数目N足够大时，则p(x/X)非常接近真实分布密度p(x)，即方法有：任务:直接用已知类别样本去估计总体密度分布。②

用训练样本直接估计后验概率p(ωi/x)作为分类准则来设计分类器如k近邻法.基本思想：

每个训练样本xk(k=1,2,…,N)对总体概率密度p(x)都有一定贡献，把N个训练样本的贡献叠加起来，就得到总体

密度估计如图3.3、3.4所示。密度估计:∴概率P是概密p(x)的一种平滑或取平均的形式，p(x)为P在R内的变化值。对于某区域R，当一向量x落入某区域R的概率为可通过估计概率P来估计概率密度p(x)其中

假设有N个样本x=(x1,x2,…xN)T都是按照概率密度p(x)从总体分布中独立抽取，则N个样本中有k个落入区域R的概率是服从二项式分布：P是样本x落入R内的概率

Pk是k个样本落入R内的概率∵样本x是随机抽取的，∴落入区域R的数目k是随机的，则k的数学期望为：Pk是k个样本落入区域R的概率P是样本x落入区域R的概率众数的概念：

使Pk最大的k值，称为众数，记为m，即这个概率发生在k的众数m上∴对概率P的估计:根据二项式分布，k的众数为：

m＝[(N+1)P]的整数部分意义:抽N个样本中,有k=m个样本落入区域R的概率最大。可取:来对P进行估计是P的一个较好的估计，尤其N非常大时，估计将非常准确。∵目的是估计概率密度p(x)

设p(x)在R内连续变化,当R逐渐减小的时候,小到使p(x)在其上几乎没有变化时，则其中是R包围的体积∴概率密度的估计为：(V足够小)∴与N、V、k有关，显然与p(x)存在差异讨论:①若区域R的体积V固定，随着N增加,k也增加,

当

时②若N固定,体积变小

.当

时，k=0时

只能反映p(x)的空间平均估计，而反映不出空间的变化。则需让

无意义该方法的局限性：

实际估计时，N有限，V也不能任意小，估计的p(x)总是存在一定误差，密度函数是一定范围内的平均值，存在一定的平滑效果。

如果样本数目N固定，让V→0，则会出现无意义的情况，p(x)=0,p(x)→∞。p(x)值起伏比较大,噪声比较大.∴为了提高x处概率p(x)的估计精度，需要对V进行改进，设计适当限制条件

为了估计x点处的概率密度函数,我们构造一串包括x的区域序列R1，R2，…，RN。对体积V进行改进：

对R1采用一个样本进行估计，对R2采用二个样本进行估计…。

设VN是RN的体积，KN是N个样本中落入VN的样本数，则概率密度的第N次估计：是p(x)的第N次估计

为使

收敛于p(x)，提高p(x)估计精度，序列必须满足三个条件：

当N↑时，VN↓，N→∞，VN→0

这时虽然样本数多，但由于VN↓，落入VN内的样本KN也减小，所以空间变化才反映出来

保证了在区域均匀收缩及p(x)在x处连续情况下，可使平均密度收敛于真实分布p(x)，即

只对p(x)≠0的点有意义，可使频率数

收敛于真实概率PN↑，kN↑，N与KN同相变化

KN的变化远小于N的变化。尽管在RN

内落入了大量样本，但与样本总数N比较,仍然很少。避免了

的可能性。第3个条件是必要条件

满足上述条件的区域序列(VN)有两种选择方法，

形成两种非参数估计方法：1）Parzen窗法；两者如何选择VN？2）KN近邻估计选择VN满足上述条件，可使

收敛于p(x)1）Parzen窗法：2．KN近邻估计使体积VN以N的某个函数减小，例（满足第1条）使KN作为N的某个函数，例VN的选择使RN正好包含KN个近邻（满足第2条）V1→K1，V2→K2，..VR→KR——近邻法

这两种方法最终都能够收敛，但却很难预测在有限样本情况下的估计效果。3.5.2Parzen窗法——一种非参数估计方法1．Parzen窗估计法的基本概念由出发，

可假设围绕x点的区域RN为一个d维超立方体，边长为hN，其中d=1，窗口为一线段；d=2，窗口为一平面d=3，窗口为一立方体；d>3，窗口为一超立方体窗口的选择：有多种选择

方窗函数指数窗函数正态窗函数Φ(u)Φ(u)Φ(u)hN

正态窗函数若选ф(u)是以原点x为中心的超立方体。在xi落入方窗时，则有在VN内为1不在VN内为0落入VN的样本数等于所有为1者之和即则概率密度估计：∴落入窗口中的样本为——Parzen窗法估计的基本公式

该式是一个迭加函数，使用KN个以xi为中心的窗函数迭加，对x处的概密进行估计。每一样本xi对概率密度函数的贡献只在一个窗口范围，离x远近不同，贡献不同，是一种内插过程。①每个样本对估计所起的作用依赖于它到x的距离，即

|x-xi|≤hN/2时，xi在VN内为1，否则为0。讨论：②

称为窗函数，取0，1两种值，

但有时可取0,0.1,0.2……多种数值，例如随xi离x接近的程度，

取值可由0,0.1,0.2……到1。为满足这两个条件，要求窗函数满足：（保证

非负）④窗函数的选择例：矩形窗、正态窗、指数窗、三角窗等等（只要满足上述两条件，都可作为窗函数使用）③要求估计的

应满足：④窗长度hN对

的影响

hN又称为平滑因子，N有限时，hN影响大，既影响幅度，又影响宽度若定义则

hN太大,是p(x)的一个平滑估计,不能跟上p(x)变化，分辨力太低，有平均误差。

若hN太大，

N(x)幅度小，而宽度拓宽，

变得平缓，是由N个宽的低幅缓变函数迭加。

若hN太小，

N(x)幅度很大，宽度很小，是N个以xi为中心的尖脉冲在x处的叠加。

hN太小,是p(x)的一个起伏大的估计,分辨力高，但不稳定，波动太大，有噪声误差。

图3.6、图3.7，说明hN及N的影响为使这些误差不严重，hN应折衷选择，即VN选择很关键

看出要得到与真实分布相近的估计，需要非常大量的训练样本。（5）的统计特性

对p(x)，

(u)，hN作必要的约束，即满足3.115~3.123式，就能保证收敛。应用示例∴在一定限制条件下，是渐近无偏估计，平方误差一致，即N

，0123456x6x5x3x1x2x4x例1：对于一个二类（ω1

，ω2

）识别问题，随机抽取ω1类的6个样本X=(x1，x2，….x6)ω1=(x1，x2，….x6)=(x1=3.2，x2=3.6，x3=3，x4=6，x5=2.5，x6=1.1)估计p(x|ω1)，即解：选正态窗函数∵x是一维的

上式用图表示，则是6个分别以3.2，3.6，3，6，2.5，1.1为中心的正态曲线，而

则是这些曲线之和。

由图看出：每个样本对估计的贡献与样本间的距离有关，样本越多，PN(x)越准确。例2：设待估计的p(x)是均值为0，方差为1的正态密度函数。若随机抽取X样本中的1个、16个、256个作为学习样本xi,试用窗口法估计pN(x)。解：设窗口函数为正态的，σ＝1，μ＝0hN:窗长度，N为样本数，h1为选定可调节的参数。用窗法估计单一正态分布的实验N=∞N=256N=16N=1①当N＝1时，是一个以第一个样本为中心的正态形状的小丘，与窗函数差不多。

讨论：由图看出，随N,h1的变化情况②当N＝16及N=256时

h1＝0.25曲线起伏很大，噪声大

h1＝1起伏减小

h1＝4曲线平坦，平均误差

③当N→∞时，pN(x)收敛于一平滑的正态曲线，估计曲线较好。例3.待估的密度函数为二项分布解：此为多峰情况的估计设窗函数为正态-0.25<x<-20<x<2x为其它x-2.5-210.2502p(x)N=∞N=256N=16N=1用窗法估计两个均匀分布的实验①当N＝1时，实际是窗函数。

②当N＝16及N=256时

h1＝0.25曲线起伏大

h1＝1曲线起伏减小

h1＝4曲线平坦③当N→∞时，曲线较好上图是N=1、16、256、∞时的

估计结果

图3.6、图3.7说明了该方法的功能和限制，其结果依赖N和h1。尤其要得到精确的估计，所需的样本个数非常多。N=1时，得到的更多是关于窗函数的信息，而不是概密函数;当N=16时，估计结果不令人满意;当N=256，h1=1时，结果开始趋于精确。图3.7更明显:①窗口法具有应用的普遍性。对规则、非规则分布，单锋或多峰分布都可用此法估计概率密度。

图3.6、图3.7说明了如下结论：

只要样本足够多，总可保证收敛于任何复杂的概密函数。Parzen窗的优点：Parzen窗的缺点：

尤其特征空间维数大于1后，更加突出，对样本的需求相对于维数按指数

，所以易出现“维数灾难”。②要求样本足够多，才能有较好的估计。比参数估计法所需样本数大得多，∴需大量的存储单元和计算时间，计算效率不高。

利用训练样本类别属性已知，对每一类独立估计概率密度，并根据最大后验概率（MAP）的原则进行分类。

为提高处理效率，模式识别可用并行处理方式实现，以空间复杂度来换取时间复杂度——具有人工网络的结构。Parzer窗法＋神经网络结构

概率神经网络（ProbabilisticneuralnetworkPNN）分类器设计：3.5.3KN近邻估计Parzen窗法存在的问题：

例，对V1敏感(图3.6，图3.7)对VN

（hN）的选择，对估计结果影响很大若hN选太小，则大部分体积将是空的（不包含样本），使PN(x)估计不稳定;若hN选太大，则PN(x)估计较平坦，反映不出总体分布的变化.KN近邻估计是克服该问题的一个较有效方法

以x为中心建立区域V，使V增大（V1，V2，…，VN

），直到捕捉到KN个样本为止。∴称KN-近邻估计KN近邻法的思想:VN

受控于KN，而不是直接作为N的函数，可避免出现空的区域RN，消除了不稳定性。

VN适应于KN的变化即：样本密度大，VN↓;

样本密度小，VN↑;KN近邻方法：

1）预先确定KN是N的函数，例：2）然后围绕x点建立一个体积（邻域）RN，并让它

不断增大，直到包含KN个样本为止，这KN个样本就称为x的KN个近邻。3）计算该领域的体积VN显然：如果x点附近样本密度高，概密p(x)较大，则区域体积就小，分辨力较高。如果x点附近样本密度低，p(x)较小，则区域体积自然就大，

当区域为包含KN个邻近样本而扩展到高密度区时，扩展过程必然很快停止。4）概密函数估计为N个已知类别样本落入VN内为KN个样本的概率密度估计为：

当N个样本落入VN内有KN个，KN个样本内有Ki个样本属于ωi类则联合概率密度：用KN近邻法进行后验概率的估计：根据Bayes公式可求出后验概率：∵则

∴类别为ωi的后验概率就是落在VN内属于ωi的样本ki与VN内总样本数KN的比值Parzen窗估计法：需调整hN(VN)因子∴与Parzen窗法比较，KN近邻估计法是一种较好的非参数估计方法。KN近邻估计法：需调查KN因子1）（使平均密度收敛于真实密度，

即）2）N与KN同相变化。3）KN的变化远小于N的变化。即KN

的慢一点，以使捕获KN个样本的体积VN可逐步减小，使，避免

要使

收敛于p(x)，仍应满足下列条件:即N

时，KN

，可保证样本落在VN中的概率估值

有一定的值(充分必要条件)上述条件满足，则

收敛于真实概密p(x)缺点：

计算量太大（一维需数百个样本，二维需数千个样本）。∴出现了直接用该方法进行样本分类例：最近邻法分类K—近邻法分类（第六章内容）K近邻分类准则：K近邻分类的错误率，随K↑，其错误率P↓,最低的错误率为Bayes分类对于待分样本x，找出它的k个近邻，检查它的类别，把x归于样本最多的那个类别。P(e)P最近邻分类准则：

待分样本x，找一个离它最近的样本，把x归于最近的样本一类。错误率：其中：c为类别数;P(e)为Bayes估计的错误率

最近邻分类法的错误率P比K近邻错误率还大，但最大不会超过贝叶斯分类器错误率的二倍。P(e)BayesK近邻最近邻P剪辑法：

目标去掉训练集中那些不太可信的样本，减少需计算的距离数方法：

1）用另一训练集合中的KN个近邻，对现有训练集合中的每个样本用KN近邻法分类2）若分类结果与这个样本原始类别不一样就去掉该样本，就得到一个更小的新的训练集

为提高近邻估计法效率，应获取一个更新、更小、更有效的训练样本。注意样本选择：3.7小结（主要讨论存在的问题及局限性）

应用统计决策理论设计分类器（最优分类器设计）的前提条件是：1）对先验概率或类条件概密有充分的先验知识（已知则更好）2）有足够多的训练样本

虽理论完善，但需大量样本，有时难以实现。否则，设计分类器效果差即：无偏性，有效性，一致性1）无偏性

若称为渐近无偏2）有效性比较两种估计的方差大小3）一致性

评判获得的估计量的好坏，有其评判标准（需足够多样本）

实际中，样本数目有限时，不能保证估计的概密能较好反映真实情况，设计的分类器性能没有充分信心。∴当样本有限时，对概密函数估计比样本分类本身是更难的问题。

通过解决一个更难的问题作为媒介，去解决分类问题是不合理的，所以实际工作中，常采用直接分类器设计方法。（后面章节的内容）1.一种基于Parzen窗法和Renyi熵的图像分割阈值选取新方法《计算机应用研究》2006年文献介绍：

正态函数作为窗口函数，用Parzen窗法估计图像灰度值的空间概率密度估计函数:用Renyi熵构造目标函数，来对图像进行阈值分割搜索使目标函数最小的灰度值t为最佳全局阈值。利用灰度值t，将各灰度级的空间累积概率分布分为背景(A类)和前景(B类)两类可见：阈值t=33时分割效果非常好,t=90时有点欠分割。实验结果与分析在用Parzen窗带来的问题：要想得到满意的结果，需要大量的样本数。因此需要大量的运行时间和存储量。

结果表明,图像分割精度高,适应性强。对目标和背景整体分布不均匀,不满足双峰性质的图像,也可得到令人满意的分割结果。“基于Parzen窗函数的SAR图像人造目标检测算法”《华中科技大学学报》2008年8月方法：

以基于数据驱动的Parzen窗核函数逼近实际SAR图像的直方图，完成SAR图像的精确建模;在此基础上，推导了全局CFAR检测算法的阈值，设计了阈值求解的数值算法。实例结论：速度较快、精度较高的人造目标检测算法。2.多种分类器在华北地区土地覆盖遥感分类中的性能评价

《中国科学院研究生院学报》2005

应用遥感影像对中国华北地区土地覆盖进行分类。最大似然法（MLC）Parzen窗CART决策树BP神经网络Fuzzy神经网络。采用方法：不同训练样本下各种分类方法的总体分类精度样本大小对分类器影响不同分类器下，各类别的分类精度

(%)(1)Parzen窗法分类性能最优，CART决策树和BP神经网络分类性能次之，Fuzzy神经网络较差结果表明:(2)Parzen窗能真实逼近类概率密度，对复杂分布数据有良好分类能力；CART决策树鲁棒性较好,缺点是样本代价较大；BP神经网络分类器精度较高，缺点是需样本质量较高，且网络结构参数难确定，稳健性较差；(3)训练样本数量的影响：对最大似然法分类精度影响最小，差异低于5%；对Parzen和FuzzyARTMAP影响居中，分类精度差异为5%～10%；对CART和BP的分类精度影响较大,均在10%以上。“基于C均值K近邻算法的面部表情识别”

《智能系统学报》2008年年2月方法：使用C均值聚类、K近邻算法进行人脸识别以及表情分类。实例处理流程：结论：考虑了每种表情表现形式的多样性,识别率得到一定的提高。“一种基于相似度判据的K近邻分类器的车牌字符识别方法”

《四川大学学报（自然科学版）》2006年5月方法：基于相似度判据的K近邻分类器车牌字符识别方法。实例结论：该分类方法性能优良，较好的解决了车牌字符的识别问题。第4章线性判别函数确定分类的关键技术之一是确定判别函数例：贝叶斯决策，实际是用后验概率密度P(wi/x)作为判别函数。但P(wi/x)估计有困难（p(x/wi)难确定)。另一种方法:直接用样本集设计分类器。采用Parzen窗等估计方法，又需大量样本。用样本集设计分类器的两个步骤：1）确定判别函数类型gi(x)

2）利用样本集确定判别函数的未知参数

4.1.1线性判别函数

——最简单的判别函数线性判别函数：当g(x)只是样本x的一次函数时，称为线性判别函数，对应的分界面为超平面。或：对于c个类别，各给出一个由d个特征组成的单值函数，叫做线性判别函数。记为g1(x),…,gc(x)，分别对应w1,…,wc

若

gi(x)>gj(x)，i

j，j=1,…,c，则x

wi；在wi与wj的分界面上，则gi(x)=gj(x)数学表达式：—d维权向量—d维特征向量—阈值权

其中：两类问题：若，则决策x

w1，则决策x

w2，则拒判或决策为任何一类两类别的分界面：判别函数可采用——d维线性平面，称为超平面，也称决策面Hg(x)=0当d=2时，判别边界为一直线当d=1时，判别边界为分界点当d=3时，判别边界为一平面当d>3时，判别边界为一超平面。1)决策面H与权向量W的关系：W与H正交设两个向量

都在决策面上，即

∵为决策面上任意两点，∴是H面上的任意向量则有：决策界面H的性质：∴上式表明w和超平面H上任一向量正交，即

∴

w是H面的法向量，方向指向类别

1对应的区域R12)g(x)可看成是

到H面的距离的度量图中，可表示为其中

是

在H面上的投影向量，使

垂直H面，r是

到H的垂直距离，是

方向的单位向量。∴∵xp在H上∴∴

即，∵r是

到H的垂直距离，∴g(x)反映了

到H的距离，即与距离成正比当r>0时，在H正面；当r<0时，在H反面3）原点到H面的距离为，∵见图中所示w0>0原点在H的正侧（H在原点负侧）w0<0原为在H的负侧（H在原点正侧）w0=0，，决策面H通过坐标原点

结论：（a）超平面H与w正交，方向由w决定（b）超平面H的位置由w0来决定（c）g(x)正比于x到H的代数距离

x在H的正侧，g(x)>0,否则，反之

总之，利用线性判别函数进行决策，就是用超平面把特征空间分割成两个决策区域。即：到坐标原点的距离∴设计过程就是寻找w,w0的过程超平面的方向由权向量w确定超平面的位置由阈值权w0确定∴超平面由两个参数确定指向正方向的单位法向量

4.1.2推广：广义线性判别函数

在样本分类中，不只限于使用线性决策函数，只要各类别之间没有重叠，总能在d维空间中找到一个广义决策函数，可将类w1从c个类别中分离出来。例图4.2

用线性函数不能解决划分问题，但高次判别函数可解决。可找一个广义线性判别函数，如二次判别函数即：若做非线性变换，将令

则：称为广义线性判别函数

可利用线性函数的简单性解决复杂问题。但这种变换，使维数大大增加。如图4.2,一维x空间映射成二维y的空间（y2，y3）其中：称为增广样本向量称为增广权向量

这种映射将寻找w和w0的问题简化为寻找一个权向量a线性判别函数可表示为更一般形式：

总之，在特征向量空间，可线性表示一个非常复杂的决策函数。举例4.1.3设计线性分类器的主要步骤

设计线性分类器就是利用训练样本集建立线性判别函数或广义线性判别函数。∵仅有w、w0或a是未知的，∴设计线性分类器的过程就是找最好的w、w0或a的过程。1.选取一组具有类别标志的样本集X={x1,…,xN}

（1）确定性样本集；（2）随机性样本集2.确定一个准则函数J（1）应是X，w,w0（或a）的函数；（2）反映分类器的性质主要步骤：3.用最优化技术求出准则函数的极值解：w*,w0*或

a*，由此得g(x)。常用准则函数有：Fisher准则；感知准则；最小错分样本准则；最小平方误差准则等。4.2Fisher线性判别1.Fisher线性判别的思路：(1)在监督学习的情况下，利用训练样本的分类信息，设计一从高维空间到一维空间的映射。

即将d维空间的所有样本投影到一条过原点的直线上（把维数压缩到1）——降低特征空间维数的一种方法，实际是多维空间向一维空间的一种映射(2)转动直线，找一条最佳的投影方向（使样本容易分开），再在一维空间上进行分类。2.Fisher线性判别的优点：

简化分类器设计，且对类别的分离性有更直观的认识

从高维压缩一维，数学上容易实现，但投影到一条直线上是否可分，如何找到最好的方向，使样本易分开，是关键问题。3.Fisher法要解决的问题如何找到最好的投影方向例：如图示wy1y2x2x1ω1ω2如何向最好方向投影正是Fisher要解决的问题wy1y2x2x1ω1ω2BA两类二维模式分布：

在x1,x2轴上投影都不好分类，有可能找到一条直线AB，使样本很易分开。投影后，得到N个一维样本yn

w为该直线正方向的单位向量，则投影有：正是寻找的解向量关键点：确定w*的方向

w值大小无关紧要，仅使yn乘上一个比例因子，重要的是寻找w*的方向，直接影响分离程度。

如何确定最佳w*方向两个基本原则：（1）各类间的期望均值之差愈大愈好；（2）各类样本内部越紧密越好。定义几个基本参量：1．d维X空间（1）各类样本均值向量：（第i类d维样本的均值）（2）样本类内离散度矩阵：（3）总类内离散度矩阵：（4）样本类间离散度矩阵：

（讨论两类问题）2．在一维Y空间（1）各类样本均值：（即投影后的样本均值）（2）样本类内离散度（4）类间离散度基于Fisher准则函数的原则：1）各类均值之差越大越好2）同类样本内部尽量紧密（3）总类内离散度3．定义Fisher准则函数要求：JF(w)最大化求JF(w)的极大值w*，上式不是w的显函数，表达成w的显形式，则类间离散度总类内离散度即对应的w*就是最佳解向量经推导可得：是广义Rayleigh商Rayleigh商性质：利用Lagrange乘子法求极值：构造Lagrange函数令，即w*是矩阵相应于特征值

的特征矢量左乘（N>dSw通常非奇异）即sbw*总是在m1-m2方向上∵标量，令为R代入下式：则有：实际就是多维空间向一维空间的一种映射。

忽略比例因子，得是d维X空间到一维Y空间的最佳投影方向即类间最分散，类内最集中的解分类器设计方便；一些参数和非参数估计方法在低维空间可能得到很好运用；降维后每一类独立估计参数的可能增大；降为前无法满足多元正态分布，而降维后有可能正态分布的假设成立降维后的优势：4.分类器设计：一维空间设计Fisher分类器：

只要确定分界点y0即可先求解阈值问题方法：(1)N、d都很大时，可采用贝叶斯决策规则，获得在一维空间上的“最优”分类器。2）若样本数很少时，可根据训练样本，直接确定分界阈值y0

，就可决策(利用样本估计参数及P(wi))例：

取两类中心在w上投影连线的中心作为阈值或取均值加权平均作为阈值对于给定的某样本x，计算x在w*的投影点y即：再决策：得到分类结果4.3感知准则函数

——一种设计线性分类器的方法前面已知，分类器设计过程：感知器（perception）算法由神经网络演变来。样本集确定判别函数形式

再确定权向量

分类器设计完成。介绍一种设计线性分类器的算法：感知器算法4.3.1几个基本概念：1.线性可分性设有N个样本y1,y2,…,yN为增广样本分量，即分别来自w1,w2类，希望用它们确定判别函数，并寻找能使所有样本正确分类的权向量a*（y是d+1维）关键：是否存在一个线性分类器，即：是否存在一个权向量a，使

若存在这样的权向量a，则称为线性可分实际中，完全线性可分的条件很难满足，允许一定分类误差存在

线性可分的概率例两类问题：设有4个二维样本，有2N=24=16种可能方法，二种不可分∴

样本的规范化则两类样本模式均应满足∴规范化后，只要寻找一个权向量，使全部样本都满足

即可为分析方便，把来自w2的样本模式均乘以(-1)，即：——称为规范化增广样本向量。3.解向量和解区

满足

的权向量称为解向量，记为a*。每个样本都对解向量a*的位置给出限制。解区：

方程

确定了权空间的一个过原点的超平面，yn为法向量，指向正侧。解向量

在

的正侧（∵正侧才有）。有N个超平面，这N个正半空间共同确定的区域是顶点为原点的多面锥体，锥体内每一点都满足

∴N个样本产生N个超平面，每个超平面将权空间分为两个半空间。

若存在解向量，必在N个超平面的正半空间的交叠区，该区中任意向量都是解向量a*，∴有无穷多个解向量组成，∴称为解区图说明解区例：有4个训练样本,w1={y3,y4},w2={y1,y2}×

y3×

y4o

y1o

y2－＋－＋＋－＋－－＋解区4.对解区的限制

为使解向量更可靠，引入余量（希望能对新的样本正确分类），越靠近解区中心，分类错误越小。

每个样本对解区提供一个限制，训练样本越多，对解区限制越严，解向量越可靠，越靠近解区中心，则a*越可靠，分类错误会越小。求的解向量a*，提高可靠性。(解区见图4.6)4.3.2感知准则函数

为了解线性不等式组需构造准则函数——感知准则函数（常用）。定义：定义感知准则函数：只考虑错分样本

其中YK是被权向量a错分类的样本集合。称Jp(a)为感知准则函数∵只有当分类发生错误时，即y被错分类时，才有当a是解向量时，Jp(a)为最小

Jp(a)总大于等于0。错误分类愈少，Jp(a)就愈小。理想情况下，当a为解向量或a在解区边界时，Jp(a)为0，即即：仅当YK为空集时，几何上，Jp(a)正比于被错分样本到决策面的距离之和。（作业）

若不存在错分样本，这时a就是寻找的解向量a*，即某向量a能使Jp(a)达极小值时，a为解向量。

是求最小值的问题。

有了准则函数，利用最优化方法，求解使Jp(a)达极小值的解向量a*。可采用梯度下降法求解。求最小值，对a求梯度

Jp(a)在某点ak的梯度

Jp(ak)是一个向量，正梯度方向是Jp(a)增长最大的方向，负梯度方向是Jp(a)减小最快的方向，∴在求Jp(a)极小值时，沿负梯度方向搜索有可能最快找到极小值，这就是梯度下降法。梯度下降法基本思想：方法：

先任选初始权向量a1，计算a1的

Jp(a1)。从a1出发，沿下降最陡的方向，即负梯度方向移动一个距离，得下一个权向量a2，以此类推，采用迭代法从ak

ak+1，即：——梯度下降法的迭代公式由此建立起迭代算法，可得序列a(1),a(2),…,a(k),…在一定限制条件下，将收敛于使J(a)极小的解a*

图中，由Jp(a)经第K+1次迭代的时候，Jp(a)趋于0，收敛于所求的a*值

k：步长或增量

YK：被a(k)错误分类的样本集感知训练过程：根据梯度下降法的迭代公式：

k太小收敛太慢，

k太大，修正过分，甚至引起发散，a不稳定。问题：

k的选择及a(1)的选择

理论上可计算出最佳步长，但计算量太大，通常人为选定步长

k。两者决定收敛速度的快慢找a*的迭代过程，可采用：单样本修正法非单样修正法单样本修正法：把样本看成一个序列，逐个加以考虑非单样修正法：缺点：每次迭代必须遍历全部样本集，才能得到a(k)下的错分样本集YK设a1=0,

k=1（不失一般性，设为1）则a2=a1+y1图4.7说明了找a*的迭代过程，采用单样本修正法用权向量a2分类时，有：a*的训练过程：继续：a3又使y1错分，即则

a4使

则

a5使则

a6使，此时对所有yi都有∴权向量a*=a6例如:x1,x2,x3∈ω1作

x1,x3的垂直线可得解区(如图)

x1x2x32H3H14H25a区间3）依上法得矢量4,垂直于矢量4做超平面,H2将x3错分

假设起始权向量a1=0ρk=11）x1,x2,x3三个矢量相加得矢量2,垂直于矢量2的超平面H将x3错分.2）x3与矢量2相加得矢量3,垂直于矢量3的超平面H1,将x1错分4）x3与矢量4相加得矢量5,矢量5在解区内,垂直于矢量5的超平面，可以把x1,x2,x3分成一类。总结步骤：1.初始权向量a1，

k，门限

2.迭代法：3.直到Jp(a)达极小的解a*，或只要二类样本是线性可分的，该算法总可以收敛。为止，得a*例：X1(0,0)及X2(0,1)∈ω1、X3(1,0)及X4(1,1)∈ω2

设模式线性可分，写成增广形式y1=(001)Ty2=(011)Ty3=(101)Ty4=(111)T将属于w2的训练样本乘以（-1）（样本规范化），则

设

k=1，a(1)=0第一轮迭代a(2)=a(1)+y1=(001)Ta(2)y2=(001)(011)T=1>0∴a(3)=a(2)=(001)a(3)Ty’3=(001)(-10–1)T=-1∴a(4)=a(3)+y’3=(-100)Ta(4)Ty’4=(-100)(-1-1-1)T=1>0∴a(5)=a(4)=(-100)T出现错分，应使a(k)加上一个正比于y3的分量第二轮迭代aT(5)y1=0∴a(6)=a(5)+y1=(-101)TaT(6)y2=1>0∴a(7)=a(6)a7(6)y’3＝0∴

a(8)=a(7)+y’3=(-200)Ta7(8)y4=2>0a(9)=a(8)=(-200)T第三轮迭代aT(9)y1=0a(10)=a(9)+y1=(-2,0,1)aT(10)y2=1,>0

a(11)=a(10)aT(11)y’3=1,>0

a(12)=a(11)aT(12)y’4=1,>0

a(13)=a(12)=(-2,0,1)∴解向量a*=(-2,0,1)aTy1=1>0,都大于0第四轮迭代则判别函数为：即：w0＝1，w＝(－2，0)T决策面g(x)=0例：有两类样本

ω1=（x1,x2）={(1,0,1),(0,1,1)}ω2=（x3,x4）={(1,1,0),(0,1,0)}解：先求四个样本的增值模式

y1=(1,0,1,1)y2=(0,1,1,1)y3=(1,1,0,1)y4=(0,1,0,1)假设初始权向量a1=(1,1,1,1)ρk=1第一次迭代：

a1Ty1=(1,1,1,1)(1,0,1,1)T=3>0

不修正

a1Ty2=(1,1,1,1)(0,1,1,1)T=3>0

不修正

a1Ty3=(1,1,1,1)(1,1,0,1)T=3>0

修正a1a2=a1-y3=(0,0,1,0)a2Ty4=(0,0,1,0)T(0,1,0,1)=0

修正a2a3=a2－y4=(0,-1,1,-1)第一次迭代后,权向量a3=(0,-1,1,-1),再进行第2,3,…次迭代,如下表

直到在一个迭代过程中权向量相同，训练结束。a6=a=(0,1,3,0)判别函数g(y)=-y2+3y3感知器算法只对线性可分样本有收敛的解,对非线性可分样本集会造成训练过程的振荡,这是它的缺点.

训练样本akTy修正式修正后的权值ak＋1迭代次数y11011y20111y31101y40101+++0a1a1a1-y3a2-y41111111100100–11-1

1y11011y20111y31101y401010+0-a3+y1a4a4-y3a51–1201–1200–22–10–22-1

2y11011y20111y31101y40101+---a5a5+y2a6a60–22–10–1300–1300–130

3y11011y20111y31101y40101++--a6a6a6a60–1300–1300–1300–130

4线性不可分样本集的分类解(取近似解)

对于线性可分样本集，可用上述方法得到正确分类的权向量。当样本集线性不可分时，上述方法不收敛。

如果把循环的权向量取平均值作为待求的权向量，或取其中之一为权向量，一般可得较满意的近似结果。例：在样本ω1:

X1=（0,2）X3=（2,0）

X5=（-1,-1）ω2:

X2=（1,1）X4=（0,-2）

X6=（-2,0）求权向量的近似解特征1x6x1x3－2x5－2x4x211H特征2则判别函数为：g(x)=2x1+2x2解：此为线性不可分问题利用感知器法求权向量，权向量产生循环(-1,2,0),(0,2,2),(-1,1,1),(-1,1,1)(-1,1,1),(0,0,0),(-1,2,0)因此算法不收敛，可取循环中任一权值，例如取a=(0,2,2)T判别面方程为：g(x)=2x1+2x2＝0所以x1+x2＝0

由图看出决策面H把二类分开，但其中x2错分到ω1类，而x1错分到ω2类，但大部分分类还是正确的。x6x1x3－2x5－2x4x211H特征1特征2作业：已知四个训练样本

w1={(0,0),(0,1)}w2={(1,0),(1,1)}

使用感知器固定增量法求判别函数设a1=(1,1,1,1)ρk=1

要求编写程序上机运行，写出判别函数。作业：有两类样本

ω1=（x1,x2）={(1,0,1),(0,1,1)}ω2=（x3,x4）={(1,1,0),(0,1,0)}假设初始权向量a1=(1,1,1,1)ρk=1求解向量a*一种迭代算法感知算法的特点：当样本可分时，算法收敛，否则会来回摆动，始终不收敛。即使可分，因不知迭代次数，造成迟迟不见收敛，易误会是不可分造成。

希望找一算法，既适用于可分情况，又适用于不可分情况，

找错分数最少的解向量a*.最小错分样本数准则：针对线性不可情况，找出使错分数目最少的a*引入余量要求：矩阵形式：定义准则函数：使Jq(a)最小值的a为最优解a*2.最小平方误差准则(MSE法)---非迭代法现在不等式组变成如下形式：方程组形式：定义误差形式：

最小化一般N>d，

解方程可用最小二乘法

前面研究的都是线性不等式方程组g(x)=aTy>0的解法。共同点是找一个权向量a*，使错分样本最小。把平方误差作为目标函数，定义平均误差准则函数：使

最小化的解为最优a*。有两个变量a、b，选择自由度更多，可改善算法收敛速度。求

的梯度并为0——MSE准则函数

解上方程得：YTYa=YTb

这样把求解Ya=b的问题，转化为对YTYa*=YTb求解

这一方程最大好处是因YTY是方阵且通常是非奇异的，所以可得a*的唯一解。即称为Y的伪逆（规范矩阵）只要计算出Y+

就可以得到a*（MSE解）有N1个

则最小平方误差法同Fisher法是一致的，即MSE解a*等价于Fisher解(作业)。有N2个b如何选取，若取：3.随机最小错误率线性判别准则定义随机函数为准则函数4.7多类问题

前面主要讨论两类问题，对多类问题可化为二类问题，也可直接按多类问题求解。1．按二类问题解

通过一判别函数把一类别从其它所有类别中区分开来，即将c类问题转化为c-1个二类问题方法1：——序贯分类

第i个二类问题就是用线性函数把属于wi的样本点与不属于wi类的点分开。仍需要有c个线性判别函数gi(x)i=1,…,c称为

二分法

需在wi与其它所有类型之间确定超平面。图4.14中，阴影部分为不确定区域，可属于w1也可属于w2例：设三类问题，已知：有一样本x=(65)T判断其属于哪一类

如果大于0的条件超过一个，分类失效，若全

部，分类也失效。代入上式有：方法2：

两两分类，即将c类中任两类wi,wj，建立判别函数

c类中任取两类型的组合数为，∴需建立

个两类线性判别函数每个线性函数只对其中相应的两类别分类，即∴将多类问题转化为

次二类线性分类问题就可将wi,wj分开由wi,wj建立

对其它类型不提供任何信息，只在wi与

wj之间确定超平面，∴方法二比方法一容易。图4.14(b)中，阴影区的点无法确定类别，拒绝分类。

方法2与方法1比，两类问题是，而不是

然而两种方法都会产生阴影区。2．按多类问题解对每一类均建立判决函数定义c类判别函数：

——可避免拒绝分类的现象设有c个判别函数，其决策规则为：对一切，若存在，则

若，则拒判这样的分类器称为线性机器（linearmachine）

实质上，线性机器把特征空间分为c个决策区域R1，…，Rc

，当x

Ri时，gi(x)具有最大值。

若Ri与Rj相邻，决策面是超平面Hij的一部分，在决策面上有：即：则

是Hij的法向量若x不在决策面上，则从x到Hij的代数距离为：∴对于线性机器，重要的是权向量的差，而不是权向量本身。特点：的推导过程：(与p85类似推导过程)设xp在决策面上，则∵是Hij面的法向量，r为x到Hij面的代数距离∴x可表示为等于0∴

图4-15(a)、(b)是线性机器产生的三类、五类问题，可看出不存在阴影问题图4-15(b)，决策面由8块超平面组成，而不是

个，区域R2与R4、R5不相邻

相邻区域最多有

对，即最多有

都个决策面。但区域不一定相邻，实际上，决策面往往少于

个。线性机器决策区域的特点：（1）所有决策区域是凸的（2）每个决策区域是连通的

（3）不存在拒绝分类的死区二类问题的准则算法，可推广到多类例如感知器算法可推广到多类样本的分类

∵多类线性机器的分界面是分段线性，也可利用分段线性分类器设计方法解决多类问题，分段线性是解决多类问题的有效算法。分段线性判别函数求解及分类器的设计，见第5章总之，线性机器分析简单，是一个很好的分类器。举例：利用感知器算法求多类问题的判别函数

设有w1，…，w2类，若第k次迭代时，一个属于wi

类的样本y送入分类器，计算c个判别函数：若则权向量不变，

若其中第l个权向量使，则权向量作调整，即，

为正常数，常选为1

可证明，只要线性可分，经有限次迭代后收敛。初始值ai(0)视情况任意选择，例例：给出三类样本（c=3），各类训练样本为

w1:{(00)T},w2:{(11)T},w3:{(-11)T}

，求ai

，i=1,2,3取

=1，a1(1)=a2(1)=a3(1)=(000)T样本写成增广形式：y1=(001)T,y2=(111)T,y3=(-111)T第一次迭代用y1作训练：∴a作调整第二次迭代，用y2作训练样本，则∵，，故a作调整

第三次迭代

为训练样本，则∵，，故a作调整。第四次迭代y1作训练样本，则∵，，故a作调整。第五次迭代，以y2为训练样本，则∵，，故a不作调整。第六次迭代，以y3为训练样本，则a仍不作调整，样本已正确分类第七次迭代，以y1为训练样本，则a仍不作调整，也正确分类∴权向量的解为：得三个判别函数：作业：用多类感知器算法求下列模式的判别函数决策树：（也称多级分类器，或多层分类器）

不是企图用一种算法、一个决策规则把多类一次分开，而是利用分级形式，逐步解决。类似于查询问答，来决策分类

决策树针对多类、多峰尤其方便。将特征空间分为与类对应的唯一区域。

对于某未知样本，是通过一系列决策函数，最终判为某一类别。组成：由根节点n1、中间节点ni和叶节点tj组成tj对应一定的类别，也可能对应相同类别二叉树：决策树的一种简单形式

除了叶节点外，每个节点只有两个分支，是“二中选一”的决策，称为二叉树

二叉树的每个节点上对应单个特征，得到一个线性判别，该判别平行于特征轴

可将多类问题化为多级两类问题。因各节点选择不同的特征和采用不同的决策规则，所以设计方法灵活多样，便于利用先验知识。图4.17每个节点选择一个特征及相应的决策阈值举例:用简单例子说明决策树分类情况2）在每个非终止节点上选择合理的特征3）在每个非终止节点上选择合适的决策准则，包括选择最佳分支决策树需考虑的设计要点:1）选择合适的树结构，即合理的树节点、分支。

每个节点与特定子集Xt相关，对节点拆分等价于将子集Xt拆分。

多类两类的形式多种多样，∴二叉树结构多种多样，目的是找最优决策树

决策树和神经网络分类器极为相似，都是在特征空间中形成复杂决策界限，两者区别是决策方式不同。一种改进的线性判别分析法在人脸识别中的应用计算机工程2006年文献介绍：特点：

重新定义样本的类间离散度矩阵，增加一种径向基函数（RBF）调节类间距离，使选择的投影方向能更好地分开各类样本；在类间离散矩阵与类内离散矩阵的特征分解的基础上，通过变换求出符合Fisher准则的最优投影方向，该投影方向同时具有正交性与统计不相关性。

在解决两类问题时，Fisher准则就是找到样本类间的离散度与样本类内的离散度的比值达到最大的投影方向。

但对于多类问题时，Fisher准则函数定义的样本类间离散度，却有可能得不到最优投影方向。另外，由于样本维数有可能大于样本数量(即小样本问题)，样本类内离散矩阵通常是奇异的。改进的线性判别分析：原因：距离大的类别主导特征向量方向，导致算法在降维中过分强调已经能较好分开的类别，而引起其它小间距类别分类性能显著的降低。传统算法不足：当类别数多于两类时，定义的类间离散度矩阵过分地强调了类间距离大的类别，而忽视了类间距离小的类别，导致算法投影方向能很好地分开类间距较大的类别，却造成小间距类别的大量重叠。

重新定义样本类间离散度矩阵，减少距离大的类别的影响。w(di)是一个单调减函数，设计的函数形式为：式中α是调节函数单调下降速度的一个参数加权类间散度矩阵

这样可给相距较近的类较大的权值，而给远离总体类中心的类别较小的权值。即将相距远的类中心拉近总体类中心，而将可能有重叠的类中心拉开远离总体类中心。有5类数据，每类有100个样本。图1是改进的线性分类设计（ILDA）与传统线性分类设计（LDA）方法的区别

传统的LDA投影方向对于密集处的类有很大的重叠，而改进的LDA的投影方向优于传统投影方向，特别对于类密集地方,有更好的分类能力。对于高维，改进的LDA性能会更好。基本步骤；1.求出类内散离散度矩阵与类间离散度矩阵2.对角化Sb：可获得Sb的特征值，从大到小排序3.找前m列非零特征值对应的特征向量，将Sb变换为一个m×m单位阵，可得矩阵Z4.通过矩阵Z，将Sw向Sb投影并对角化该矩阵,其元素按从小到大排序5.求最终的投影方向实验结果与分析ORL人脸数据库：每个人都有不同表情、不同姿态与不同光照条件的人脸图像。分辨率是92×112像素，每个像素为256个灰度级。图中是数据库中的部分实例。每个人随机取5张照片用于训练集首先实验分析参数α对人脸识别性能的影响

可看出参数α对算法性能影响较大。当α接近于0时，ILDA算法相当于传统LDA算法，随着α增加，算法的性能变好，但到某个临界值后再增加α，算法性能又开始变差，这是由于将距离大的类惩罚太厉害的缘故。可看出当α值在0.5×10−5

左右时，算法性能最好。分析比较改进算法（ILDA）与传统算法传统算法有：PCA（KL变换）、LDA及PCA+LDA

可看出ILDA算法在各种特征维数下的识别率都优于传统算法。例：fisher测量了150种鸢尾花（iris）花萼（Sepal）长度和宽度，采用fisher分类方法研究鸢尾花的分类问题采用fisher线性判决函数分类结果，在150种鸢尾花中，20％出现了错误的分类。采用fisher线性判决函数划分的类区域。采用二次判决函数划分的类区域。采用决策树划分的类区域采用决策树分类，在150种鸢尾花中，13.3％出现了错误的分类。第5章非线性判别函数——(重点是分段线性分类器，适应力很强)5.1.1基于距离的分段线性判别函数最小距离分类器：将样本归入离均值最近的一类。（2.3.2节讲过）如图5.2，g(x)=0是过均值连线中心的一条直线。

多峰分布时，应取多个代表点，如图5.3，w1取两个代表点，w2取三个代表点，将x归入离代表点最近的类别，即为分段线性距离分类器。5.1.2分段线性判别函数例：对于图5.4，最小距离分类不合适，即只考虑各代表点信息是不够的用贝叶斯决策规则：用最小距离分类

只考虑各代表点信息是不够的将每一类分为若干个子类，wi类的线性判别函数定义为：每个子类定义线性判别函数：同理，算出其它类的线性判别函数得到的决策面也是分段线性的决策规则：即：将样本x归入最大值判别函数所对应的类别。关键问题：如何利用样本集确定子类数目；如何求各子类的权向量和阈值权，或a*

。1．多类线性判别函数算法当已知子类划分情况时，利用第4章讨论的多类线性判别函数算法，分开各子类2．已知子类数目时的分段线性函数类似于多类感知算法（固定增量算法）3．未知子类数目时的分段线判方法很多，其中可采用树状分段线性分类器。1.

已知子类划分时的设计方法先求子类的权向量ail，再求总的权向量ai

把每一个子类作为独立类，利用每个子类的训练样本，求每个子类的线性判别函数，总的判别函数就可获得。子类的划分可用以下方法：①

用先验知识直接划分②

用聚类分析，聚成多个子类（第10章讲）2.

已知子类数目的设计方法①设各个子类的初始权向量：ai1,ai2…aili

i=1,2,…cai中有li个子类②若第k步迭代时，ωj

类样本yj同ωj类某个子类的权向量ajm(k)的内积值最大，即：ajm(k)Tyj=

max{ajl(k)Tyj}l=1,2,…lj并且满足条件：ajm(k)Tyj>ail(k)Tyji=1,2,…c类l=1,2,…li子类i≠j

则权向量ai1(k)，ai2(k)，…,aili

(k)不影响yj分类，所以权向量不需要修正。

若有某个或某几个子类不满足条件，即：

存在aim(k)，使ajm(k)Tyj≤ain(k)Tyji≠j所以yj错分类，要修改权向量。

③

重复以上迭代,直到收敛,此法类似于固定增量法.设ail’(k)