机器学习非参数方法

非参数方法第一页，共七十三页。单击此处添加标题

前面的章节中，我们介绍了参数和半参数方法，这两种方法在实际训练前都需要对数据遵从的模型进行一个假定，这个假定可以是一个已知的概率分布或混合分布。参数方法的优点是把估计概率密度、判别式或回归函数问题归结为估计少量参数值，缺点则是模型假定并非总成立，当不成立时就会出现很大的误差。这时我们就需要使用非参数方法，其中我们只需要假定一个事实：即相似的输入具有相似的输出。因为我们一般都认为世界的变化时平稳、量变到质变的，因此无论是密度、判别式还是回归函数都应当缓慢地变化。在这样的非参数估计（nonparamitricestimation）中，局部实例对于密度的影响就显得颇为重要，而较远的实例影响则较小。本节要点如下：

k-近邻估计 Pazen窗第二页，共七十三页。K近邻第三页，共七十三页。最简单的分段线性分类器：把各类划分为若干子类，以子类中心作为类别代表点，考查新样本到各代表点的距离并将它分到最近的代表点所代表的类。极端情况，将所有样本都作为代表点－－－－近邻法第四页，共七十三页。问题描述:

特征向量类别X=(0.1,0.1)?特征向量类别(0.1,0.2)W1(0.2,0.1)W1(0.4,0.5)W2(0.5,0.4)W2第五页，共七十三页。最小距离分类器：将各类训练样本划分成若干子类，并在每个子类中确定代表点，一般用子类的质心或邻近质心的某一样本为代表点。测试样本的类别则以其与这些代表点距离最近作决策。该法的缺点是所选择的代表点并不一定能很好地代表各类，其后果将使错误率增加。最近邻法的基本思想：以全部训练样本作为“代表点”，计算测试样本与这些“代表点”，即所有样本的距离，并以最近邻者的类别作为决策。近邻法是由Cover和Hart于1968年提出的，随后得到理论上深入的分析与研究，是非参数法中最重要的方法之一。第六页，共七十三页。第七页，共七十三页。第八页，共七十三页。在二维情况下，最近邻规则算法使得二维空间被分割成了许多Voronoi网格，每一个网格代表的类别就是它所包含的训练样本点所属的类别。第九页，共七十三页。

最近邻法的错误率是比较难计算的，这是因为训练样本集的数量总是有限的，有时多一个少一个训练样本对测试样本分类的结果影响很大。红点表示A类训练样本，蓝点表示B类训练样本，而绿点O表示待测样本。假设以欧氏距离来衡量，O的最近邻是A3，其次是B1，因此O应该属于A类；但若A3被拿开，O就会被判为B类。第十页，共七十三页。这说明计算最近邻法的错误率会有偶然性，也就是指与具体的训练样本集有关。同时还可看到，计算错误率的偶然性会因训练样本数量的增大而减小。因此我们就利用训练样本数量增至极大，来对其性能进行评价。这要使用渐近概念，以下都是在渐近概念下来分析错误率的。

第十一页，共七十三页。当最近邻法所使用的训练样本数量N不是很大时，其错误率是带有偶然性的。

下图所示为一个在一维特征空间的两类别情况：

X表示一待测试样本，而X'是所用训练样本集中X的最邻近者，则错误是由X与X'分属不同的类别所引起的。第十二页，共七十三页。由于X‘与所用训练样本集有关，因此错误率有较大偶然性。但是如果所用训练样本集的样本数量N极大，即N→∞时，可以想像X‘将趋向于X，或者说处于以X为中心的极小邻域内，此时分析错误率问题就简化为在X样本条件下X与一个X(X’的极限条件)分属不同类别的问题。如果样本X的两类别后验概率分别为P(ω1|X)与P(ω2|X)，那么对X值，在N→∞条件下，发生错误决策的概率为：第十三页，共七十三页。而在这条件下的平均错误率

P称为渐近平均错误率，是PN(e)在N→∞的极限。为了与基于最小错误率的贝叶斯决策方法对比，下面写出贝叶斯错误率的计算式：

其中第十四页，共七十三页。

若是两类问题，则

贝叶斯错误率：最近邻法错误率：可见在一般情况下△P是大于零的值，只要P(ω1|X)＞P(ω2|X)＞0。第十五页，共七十三页。有以下两种例外情况△P＝0：P(ω1|X)＝1P(ω1|X)＝P(ω2|X)＝1/2。第十六页，共七十三页。请想一下，什么情况下P(ω1|X)＝1或P(ω2|X)=1?P(ω1|X)=P(ω2|X)会出现什么什么情况？

一般来说，在某一类样本分布密集区，某一类的后验概率接近或等于1。此时，基于最小错误率贝叶斯决策基本没错，而近邻法出错可能也很小。而后验概率近似相等一般出现在两类分布的交界处，此时分类没有依据，因此基于最小错误率的贝叶斯决策也无能为力了，近邻法也就与贝叶斯决策平起平坐了。从以上讨论可以看出，当N→∞时，最近邻法的渐近平均错误率的下界是贝叶斯错误率，这发生在样本对某类别后验概率处处为1的情况或各类后验概率相等的情况。

第十七页，共七十三页。第十八页，共七十三页。最近邻法的错误率高于贝叶斯错误率，可以证明以下关系式成立：由于一般情况下P*很小，因此又可粗略表示成：可粗略说最近邻法的渐近平均错误率在贝叶斯错误率的两倍之内。

第十九页，共七十三页。小结

模式识别（机器自动分类）的基本方法有两大类：一类是将特征空间划分成决策域，这就要确定判别函数或确定分界面方程。另一种方法则称为模板匹配，即将待分类样本与标准模板进行比较，看跟哪个模板匹配度更好些，从而确定待测试样本的分类。前面讨论的方法可以说都是将特征空间划分为决策域，并用判别函数或决策面方程表示决策域的方法。近邻法则在原理上属于模板匹配。它将训练样本集中的每个样本都作为模板，用测试样本与每个模板做比较，看与哪个模板最相似(即为近邻)，就按最近似的模板的类别作为自己的类别。第二十页，共七十三页。6k-近邻法:

最近邻法的扩展，其基本规则是，在所有N个样本中找到与测试样本的k个最近邻者，其中各类别所占个数表示成ki,i＝1，…，c。定义判别函数为：

gi(x)=ki,i=1,2,…,c。

决策规则为：

k-近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。第二十一页，共七十三页。

从样本点x开始生长，不断扩大区域，直到包含进k个训练样本点为止，并且把测试样本点x的类别归为这最近的k个训练样本点中出现频率最大的类别。第二十二页，共七十三页。对于两类问题，有以下两种例外情况△P＝0：PN(e|x,x’)＝P(ω1|x)P(ω2|x’)+P(ω2|x)P(ω1|x’)当N->∞时，P(ωi|x’)近似等于P(ωi|x)PN->∞(e|x,x’)＝P(ω1|x)P(ω2|x)+P(ω2|x)P(ω1|x)对于K近邻法

第二十三页，共七十三页。对所有的x，有：

PN->∞(e|x)≤Ck[P*(e|x)]根据Jensen不等式,P=E[PNk(e|x)≤E{Ck[P*(e|x)]}≤CkE{[P*(e|x)]}=Ck(P*)不等式关系P*≤P≤Ck(P*)≤Ck-1(P*)≤…≤C1(P*)≤2P*(1-P*)

第二十四页，共七十三页。最近邻法和k-近邻法的错误率上下界都是在一倍到两倍贝叶斯决策方法的错误率范围内。在k→∞的条件下，k-近邻法的错误率要低于最近邻法。在k→∞的条件下，k-近邻法的错误率等于贝叶斯误差率。第二十五页，共七十三页。§6.3改进的近邻法

尽管近邻法有其优良品质，但是它的一个严重弱点与问题是需要存储全部训练样本，以及繁重的距离计算量。

但以简单的方式降低样本数量，只能使其性能降低，这也是不希望的。为此要研究既能减少近邻法计算量与存储量，同时又不明显降低其性能的一些改进算法。改进的方法大致分为两种原理。一种是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算。

另一种原理则是在原有样本集中挑选出对分类计算有效的样本，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。第二十六页，共七十三页。快速搜索近邻法

这种方法着眼于只解决减少计算量，但没有达到减少存储量的要求。

基本思想：将样本集按邻近关系分解成组，给出每组的质心所在，以及组内样本至该质心的最大距离。这些组又可形成层次结构，即组又分子组。因而待识别样本可将搜索近邻的范围从某一大组，逐渐深入到其中的子组，直至树的叶结点所代表的组，确定其相邻关系。第二十七页，共七十三页。（1）样本集的分级分解首先将整个样本分成l个子集，每个子集又分为它的l个子集，如此进行若干次就能建立起一个样本集的树形结构。分成子集的原则是该子集内的样本尽可能聚成堆，这可用聚类方法实现。

结点参数：树形结构，每个结点表示一样本子集，描述该子集的参数是：

第二十八页，共七十三页。用树结构表示样本分级:p:树中的一个结点，对应一个样本子集KpNp:Kp中的样本数Mp:Kp中的样本均值rp:从Kp中任一样本到Mp的最大距离第二十九页，共七十三页。（2）快速搜索算法

要实现快速搜索近邻，需要有方法快速判断某个样本子集是否是该待识样本的可能近邻样本集，从而可将无关的样本子集尽快排除。另一方面在某样本子集内寻找哪个样本是近邻时，需快速排除不可能为近邻的样本。

这两个快速判别算法可用以下两个规则表示。第三十页，共七十三页。

规则1：如果存在则不可能是X的近邻。其中B是待识别样本在搜索近邻过程中的当前近邻距离，B在搜索过程中不断改变与缩小。算法开始可将B设为无穷大。表示待识样本X到结点的均值点距离。

第三十一页，共七十三页。

规则2：如果其中Xi∈，则Xi不可能是X的近邻。由此可见，只要将每个样本子集中的每个样本Xi到其均值Mp的距离D(Xi,Mp)存入存储器中，就可利用上式将许多不可能成为测试样本近邻的训练样本排除。

第三十二页，共七十三页。（3）搜索算法

搜索算法的大体过程是这样的：当搜索树形样本集结构由高层次向低层次深入时，对同一层次的所有结点，可以利用规则1排除掉一些不可能包含待识别样本的近邻的结点(样本子集)。但是这往往不能做到只留下唯一的待搜索结点，因此必须选择其中某一结点先深入搜索，以类似于深度优先的方法确定搜索路径直至叶结点。然而在该叶结点中找到的近邻并不能保证确实是全样本集中的最近邻者，所找到的该近邻样本需要在那些有可能包含最近邻的样本子集中核对与修正，直至找到真正的最近邻样本为止。第三十三页，共七十三页。置B=∞，L=0，p=0将当前结点的所有直接后继结点放入一个目录表中，并对这些结点计算D(x,Mp)根据规则1从目录表中去掉step2中的某些结点如果目录表已无结点则置L=L-1，如果L=0则停止，否则转Step3。如果目录表有一个以上的结点，则转step5在目录表中选出最近结点p’为当前执行结点。如果当前的水平L是最终水平，则转Step6，否则置L=L+1，转Step2对当前执行结点p’中的每个xi，根据规则2决定是否计算D(x,xi)。若D(x,xi)<B，则置NN=i和B=D(x,xi)，处理完当前执行结点中的每个xi后转Step3当算法结束时，输出x的最近邻xNN和x与xNN的距离B第三十四页，共七十三页。剪辑近邻法目的：去掉靠近两类中心的样本？基本思想：当不同类别的样本在分布上有交迭部分的，分类的错误率主要来自处于交迭区中的样本。当我们得到一个作为识别用的参考样本集时，由于不同类别交迭区域中不同类别的样本彼此穿插，导致用近邻法分类出错。因此如果能将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。为此可以利用现有样本集对其自身进行剪辑。第三十五页，共七十三页。剪辑的过程是：将样本集KN分成两个互相独立的子集：考试（test）集KT和参考（reference）集KR。首先对KT中每一个Xi在参考集KR中找到其最近邻的样本Yi(Xi)

。如果Yi与Xi不属于同一类别，则将Xi从考试集KT中删除，最后得到一个剪辑的样本集KTE（剪辑样本集），以取代原样本集，对待识别样本进行分类。剪辑的结果是去掉两类边界附近的样本。第三十六页，共七十三页。压缩近邻法：利用现有样本集，逐渐生成一个新的样本集，使该样本集在保留最少量样本的条件下，仍能对原有样本的全部用最近邻法正确分类，那末该样本集也就能对待识别样本进行分类，并保持正常识别率。第三十七页，共七十三页。定义两个存储器，一个用来存放即将生成的样本集，称为Store；另一存储器则存放原样本集，称为Grabbag。其算法是：初始化。Store是空集，原样本集存入Grabbag；从Grabbag中任意选择一样本放入Store中作为新样本集的第一个样本。样本集生成。在Grabbag中取出第i个样本用Store中的当前样本集按最近邻法分类。若分类错误，则将该样本从Grabbag转入Store中，若分类正确，则将该样本放回Grabbag中。结束过程。若Grabbag中所有样本在执行第二步时没有发生转入Store的现象，或Grabbag已成空集，则算法终止，否则转入第二步。第三十八页，共七十三页。最佳距离度量近邻法定义新的距离函数

其中xl为x的局部邻域中的样本,则必有

按照上面定义的新距离，在x的局部邻域中选择x的最近邻x’,则可使有限样本与无限样本的错误率之差在均方意义下达到最小。

需要说明：上述距离度量使通过对P(wi|x)在x的局部邻域区域中做线性近似得到的，因此，它只适合于XN中与x较为接近的那些样本。第三十九页，共七十三页。根据

寻找x最近邻的程序步骤

（1）计算||x-x1||,…,||x-xN||(2)找出与x距离是最短的NA个近邻xl，l=1,2,…,lNa

（3）利用xl计算M1-M0(4)计算|(M1-M0)T(x-xl1)|,…,|(M1-M0)T(x-xlNA)选出其中最小者，若为xlk,则xlk为x的按照距离度量的最近邻，即xlk

＝x’

第四十页，共七十三页。Pazen窗第四十一页，共七十三页。1、Parzen窗方法综述、发展历史及现状模式识别领域的非参数估计方法大致可以分为两类。第一种类型是先估计出概率密度函数的具体形式，然后再利用这个估计出来的概率密度函数对样本进行分类。第二种类型是，不估计具体的概率密度函数，而直接根据样本进行分类。Parzen窗方法就是属于第一种类型的非参数估计方法，概率神经网络（PNN）是它的一种实现方式。Parzen窗方法的基本思想是利用一定范围内的各点密度的平均值对总体密度函数进行估计。

第四十二页，共七十三页。Parzen窗（Parzenwindow）又称为核密度估计（kerneldensityestimation），是概率论中用来估计未知概率密度函数的非参数方法之一。该方法由EmanuelParzen于1962年在TheAnnalsofMathematicalStatistics杂志上发表的论文“OnEstimationofaProbabilityDensityFunctionandMode”中首次提出。Nadaraya和Watson最早把这一方法用于回归法中。Specht把这一方法用于解决模式分类的问题，并且在1990年发表的论文“Probabilisticneuralnetworks”中提出了PNN网络的硬件结构。Ruppert和Cline基于数据集密度函数聚类算法提出了修订的核密度估计方法，对Parzen窗做了一些改进。Parzen窗方法虽然是在上个世纪60年代提出来的，已经过去了45年的时间，看上去是一种很“古老”的技术，但是现在依然有很多基于Parzen窗方法的论文发表。这说明Parzen窗方法的确有很强的生命力和实用价值，虽然它也存在很多缺点。第四十三页，共七十三页。2、Parzen窗方法和概率神经网络

Parzen窗方法就是基于当样本个数n非常大的时候，有公式成立这样的一个事实而提出的。通过计算在一个区域R内的频数k/n，用这个频数来估计这一点的频率，从而得到这一点的概率。当n趋于无穷大的时候，p(x)等于该点的实际概率。这种方法就是模式识别领域中的非参数估计方法。Parzen窗方法就是通过构造一系列的区域：，在这些区域内计算k/n。记Vn为区域Rn的体积，kn为落在区域Rn中的样本个数，表示对的第n次估计，于是有：为了保证能够收敛到，必须满足以下3个条件：第四十四页，共七十三页。

Parzen窗方法的实质就是通过对上面的区域Rn，每次按照来构造区域序列，使区域逐渐收缩到一个给定的初始区间。它不断收缩区域，按照公式把区域不断缩小，而不关心该区域实际上包含多少个样本点。另外一种与它相对应的非参数估计方法是Kn-近邻法。假设区间Rn是一个d维的超立方体，hn表示超立方体的一条边的长度，那么该超立方体的体积就是。通过定义如下的窗函数，我们能够解析地得到落在窗中的样本个数kn的表达式：第四十五页，共七十三页。第四十六页，共七十三页。

该方程表明一种更加一般的估计概率密度函数的方法——不必规定区间必须是超立方体，可以是某种更加一般化的形式。这个公式表示我们对p(x)的估计是对一系列关于x和xi的函数求平均。这个就是Parzen窗方法估计得到的概率密度函数。关于是否合理的问题，也就是判断它是否保证函数值非负，而且积分的结果为1。这一点可以通过增加条件来保证：

增加这些条件就可以保证是一个合理的概率密度函数，函数值是非负的，积分的结果为1。第四十七页，共七十三页。

Parzen窗方法可以使用神经网络的方法来实现，也就是通常所说的概率神经网络（Probabilisticneuralnetwork,PNN）。现在假设有n个d维的样本，它们都是从c个类别中选取的。在这种情况下，输入层由d个输入单元组成，每一个输入单元都与模式层中的n个模式单元相连。而每一个模式单元只与类别层中的c个类别单元中的其中之一相连。第四十八页，共七十三页。

从输入层到模式层的连线表示可修改的权系数，这些权系数可以通过训练得到。每一个类别单元都计算与之相连的各模式单元的输出结果的和。每一个模式层单元能够对它的权重向量和归一化的样本向量x作内积，得到Z=WtX，然后映射为。每一个类别单元把与它相连的模式层单元的输出结果相加。这样的结果就保证了类别单元处得到的就是使用协方差为的圆周对称高斯窗函数的Parzen窗的估计结果（I表示d×d的单位矩阵）。第四十九页，共七十三页。

PNN网络是用下面的方式训练的。首先，把训练样本中的每一个样本x都归一化为单位长度，即。第一个经过归一化的样本被置于输入层单元上。同时，连接输入单元和第一个模式层单元的那些连接被初始化为W1=X1。然后，从模式层的第一个单元到类别层中代表x1所属类别的那个单元之间就建立了一个连接。同样的过程对剩下的各个模式单元都重复进行，即Wk=Xk，其中k=1,2,…,n。这样就得到了一个网络：输入层单元与模式层单元之间是完全连通的，而模式层单元到类别单元之间是稀疏连接的。如果把第j个样本的第k个分量记为Xjk，把这个分量到第j个模式层单元的连接权重系数记为wjk，其中j=1,2,…,n,k=1,2,…,d。得到算法描述如下：第五十页，共七十三页。第五十一页，共七十三页。

然后，经过训练完成的网络就可以用这样的方式实现分类：首先把一个归一化了的测试样本x提供给输入节点，每一个模式层单元都计算内积，得到“净激活”（netactivation）：并产生netk的一个非线性函数，其中,是由用户设置的一个参数，表示有效的高斯窗的宽度。每一个类别层单元则把与它相连接的模式层单元的结果进行相加。为了实现Parzen窗算法，这里的激活函数必须是一个指数函数。对于一个中心在某一个训练样本Wk处的未经过归一化的高斯窗函数。从期望得到的高斯窗函数倒推出模式层应采用的非线性活化函数的形式，即如果令有效宽度hn为常数，则窗函数为第五十二页，共七十三页。

其中使用了归一化条件：这样一个模式层单元向与它相连接的那个类别层单元贡献了一个信号，这个信号的强度等于以当前训练样本为中心的高斯函数产生这个测试样本点的概率。对这些局部估计值求和就得到判别函数gi(X)——也就是概率密度函数的Parzen窗估计结果。通过

运算得到测试点的期望的类别：第五十三页，共七十三页。第五十四页，共七十三页。3、Parzen窗方法的优点和缺点

Parzen窗方法的好处是不需事先知道概率密度函数的参数形式，比较通用，可以应对不同的概率密度分布形式。在处理有监督学习过程的时候，现实世界的情况往往是我们不知道概率密度函数形式。就算能够给出概率密度函数的形式，这些经典的函数也很少与实际情况符合。所有经典的概率密度函数的形式都是单模的（只有单个局部极大值），而实际情况往往是多模的。非参数方法正好能够解决这个问题，所以从这个意义上来讲，Parzen窗方法能够更好地对应现实世界的概率密度函数，而不必实现假设概率密度函数的形式是已知的。Parzen窗方法能处理任意的概率分布，不必假设概率密度函数的形式已知，这是非参数化方法的基本优点。第五十五页，共七十三页。

Parzen窗方法的一个缺点是它需要大量的样本。在样本有限的情况下，很难预测它的收敛性效果如何。为了得到较精确的结果，实际需要的训练样本的个数是非常惊人的。这时要求的训练样本的个数比在知道分布的参数形式下进行估计所需要的训练样本的个数要多得多。而且，直到今天人们还没有找到能够有效的降低训练样本个数的方法。这也导致了Parzen窗方法对时间和存储空间的消耗特别大。更糟糕的是，它对训练样本个数的需求，相对特征空间的维数呈指数增长。这种现象被称为“维数灾难（curseofdimensionality）”，严重制约了这种方法的实际应用。Parzen窗方法的另外一个缺点是，它在估计边界区域的时候会出现边界效应。第五十六页，共七十三页。

Parzen窗方法的一个问题是，窗宽度的选择难以把握。下图是一个二维Parzen窗的两类分类器的判决边界。其中窗宽度h不相同。左边的图中的窗宽度h较小，右边的图中的窗宽度h较大。所以左侧的Parzen窗分类器的分类界面比右边复杂。这里给出的训练样本的特点是，上半部分适合用较小的窗宽度h，而下半部分适合用较大的窗宽度h。所以，这个例子说明没有一个理想的固定的h值能够适应全部区域的情况。这算是Parzen窗方法的一个不足之处。第五十七页，共七十三页。第五十八页，共七十三页。

PNN是Parzen窗方法的实现。PNN的好处之一是学习速度很快，因为学习规则非常简单（Wk=Xk），并且每一个样本点只需要提供一遍。这个算法的空间复杂度也很容易计算：只要查看PNN图中的连接个数即可。而空间复杂度是O((n+1)d)。可见，PNN算法的缺点就是在硬件实现的时候，对存储空间的要求比较高，特别是当n和d都比较大的时候。PNN算法的时间复杂度是O(1)，因为公式中的内积都可以用并行的方式来完成计算。所以，PNN算法适合于对计算速度要求高而存储器资源比较容易满足的场合。PNN算法的另外一个优点是新的训练样本很容易被加入以前训练好的分类器中，这一特性对于“在线”应用特别有意义。第五十九页，共七十三页。4、对Parzen窗法的改进

Parzen窗/PNN算法中的一个关键问题就是如何选取体积序列V1,V2,…,Vn。例如，当我们选取那么对于有限的n，估计结果将对初始体积V1非常敏感。如果V1非常小，那么大多数的体积内都是空的，估计得到的Pn(x)将包含很大的误差。但是如果V1非常大的话，那么平滑效应就会非常剧烈，以至于概率密度的空间变化被掩盖了。而且很有可能对于某一个区域适合的体积对于另一个区域就非常不适合。所以，可以考虑更加一般化的方法，例如使用交叉验证方法来辅助Parzen窗方法，提高算法的性能。第六十页，共七十三页。

简单地说，“交叉验证方法”使用数据集中的一小部分来形成一个“验证集”，而窗的宽度就是通过使验证集上的误差率最小来调节得到的。我们可以通过使用“m-重交叉验证”（m-foldcrossvalidation）来估计Parzen窗方法得到的分类器的推广性能。首先讲训练样本集D，样本点的总数为n。然后把训练样本随机地划分为m个集合，每个集合包含n/m个样本点，这m个训练样本子集互不相交。用这m个训练样本集去训练Parzen窗分类器，训练完成之后，再选择一个与训练样本集不同的样本集作为“验证集”（validationset），在验证的时候可以计算出这一次的推广误差（generalizationerror），把这个值作为Parzen分类器推广能力的度量。上述过程重复m次，将获得的推广误差取平均值，就可以估计Parzen分类器的推广能力，从而评价它的性能如何。第六十一页，共七十三页。

利用交叉验证技术，我们可以对Parzen窗技术中的高斯窗函数的宽度进行调整。通过不断调整窗宽度h的值，使得交叉验证方法得到的推广误差最小。从而达到优化Parzen窗方法的目的。下面的例子中，将数据集D分为2部分，第一部分占样本点总数的90%，用作训练集；第二部分占样本总数的10%，用作验证集以测试推广性能。对Parzen窗分类器以及大多数的问题而言，训练误差会随着训练的进行而单调下降。而在验证集上误差典型的情况是首先单调下降，然后上升。这是因为后面出现了对训练集“过拟合”（overfitting）的现象。所以，在调整窗宽度h的时候，在验证集误差达到第一个局部极小值时就停止。如图所示：第六十二页，共七十三页。

前面提到了Parzen窗方法存在着“维数灾难”的问题，这严重限制了Parzen窗方法的实际应用。产生“维数灾难”的最核心的问题是，高维函数事实上远比低维函数复杂，人们对其复杂度几乎无法进行有效的分析和掌握。现在对付“维数灾难”的惟一有效的方法就是尽可能多的在处理问题时嵌入关于模式数据本身的可靠的先验知识。第六十三页，共七十三页。Parzen窗方法的实质就是通过对上面的区域Rn，每次按照来构造区域序列，使区域逐渐收缩到一个给定的初始区间。它不断收缩区域，按照公式把区域不断缩小，而不关心该区域实际上包含多少个样本点。另外一种与它相对应的非参数估计方法是Kn-近邻法。假设区间Rn是一个d维的超立方体，hn表示超立方体的一条边的长度，那么该超立方体的体积就是。通过定义如下的窗函数，我们能够解析地得到落在窗中的样本个数kn的表达式：这样，就表示一个中心在原点的单位超立方体。如果xi落在超立方体Vn中，那么，否则便为0。因此，超立方体中的样本个数就是带入公式，就得到该方程表明一种更加一般的估计概率密度函数的方法——不必规定区间必须是超立方体，可以是某种更加一般化的形式。这个公式表示我们对p(x)的估计是对一系列关于x和xi的函数求平均。这个就是Parzen窗方法估计得到的概率密度函数。第六十四页，共七十三页。模式分类方法总结一、参数判别分类方法与非参数判别分类方法的区别

从参数判别方法看，它的前提是对特征空间中的各类样本的分布清楚，因此一旦要测试分类样本的特征向量值X已知，就可以确定X对各类的后验概率，也就可按相应的准则计算与分类。如果这种分布可以用正态分布等描述，那么决策域的判别函数与分界面方程就可用函数的形式确定下来。所以判别函数等的确定取决于样本统计分布的有关知识。因此参数分类判别方法一般只能用在有统计知识的场合，或能利用训练样本估计出参数的场合。第六十五页，共七十三页。模式分类方法总结一、参数判别分类方法与非参数判别分类方法的区别非参数分类判别方法则着眼于直接利