模式识别非参数估计

非参数估计

--模式识别课程

Non-ParametricClassification提纲概率密度估计Parzen窗估计Kn-近邻估计最近邻规则

Non-ParametricClassification模式分类的途径途径1：估计类条件概率密度p(x|ωi)

•通过p(x|ωi)和p(ωi)，利用贝叶斯规则计算后验概率p(ωi|x)，然后通过最大后验概率做出决策•方法1a：概率密度参数估计,基于对p(x|ωi)的含参数的描述•方法1b：概率密度非参数估计,基于对p(x|ωi)的非参数的描述途径2：直接估计后验概率p(ωi|x)

•不需要先估计p(x|ωi)途径3：直接计算判别函数不需要估计p(x|ωi)或者p(ωi|x)

Non-ParametricClassification为什么？对复杂的问题，我们常常得不到解析化的描述是，比如对于概率密度的多高斯描述。Bayesian学派的核心就是概率密度，而现实世界中的概率分布是复杂的。在一些部分上可能符合了人脑的推理规则。

Non-ParametricClassification非参数估计方法的分类非参数估计:直接用已知类别样本去估计总体密度分布，方法有：①

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

用学习样本直接估计后验概率p(ωi|x)作为分类准则来设计分类器,如k近邻法.概率密度估计-核心思想投硬币实验-当独立进行的实验次数足够多的时候，统计数据接近实际的概率密度。但是，问题本身是离散的，简单的（服从伯努利分布），采样实验是容易的。对实际的问题呢？概率密度估计一个随机变量X落在区域R的概率为PRp(x)p1是样本x落入R内的概率pk是k个样本落入R内的概率概率密度估计数学期望:E(k)=k=NP∴对概率P的估计:。是P的一个比较好的估计.

设p(x’)在R内连续变化,当R逐渐减小的时候,小到使p(x)在其上几乎没有变化时，则其中是R包围的体积概率密度估计

概率密度的估计：(V足够小)(1)当V固定的时候N增加,k也增加,当时(2)当N固定,体积V变小

当时,

时当时,时

p(x)起伏比较大,噪声比较大,需要对V进行改进.概率密度估计对体积V进行改进：为了估计X点的密度,我们构造一串包括X的区域序列R1,R2,..RN.对R1采用一个样本进行估计，对R2采用二个样本进行估计.。设VN是RN的体积，KN是N个样本落入RN的样本数则密度的第N次估计：

其中,VN是RN的体积,

KN是N个样本落入RN的样本数∴pN(x)是p(x)的第N次估计非参数概率密度估计的关键-VV很大：估计的概率密度过于平滑，失去准确性V很小：需要的样本很多,且估计结果起伏不定pN(x)收敛于p(x)的三个条件：Parzen窗和Kn-近邻区别：选择V的策略不同。首先给定一个初始V值，然后使区域序列的体积Vn按照某个函数随N的增大不断地缩小，如Parzen窗方法确定kn为n的某个函数，随N的增大而变大，如kn-近邻方法132023/1/17概率密度的估计方法直方图方法用直方图逼近概率密度函数•用直方图来模拟p(x)•假设k个样本落入以x为中点的小条（宽度为h）中，如果n足够大，则有•根据以上两种近似，得到高维空间由于数据稀疏，很难应用142023/1/17概率密度的估计方法核方法定义窗函数（核函数、势函数）•落入宽度为h，中点为x的小条中的样本个数•对p(x)的非参数化模拟xj的某个函数的均值Parzen窗口估计假设RN为一个d维的超立方体，hN为超立方体的长度超立方体体积为：，

d=1，窗口为一线段d=2，窗口为一平面

d=3，窗口为一立方体d>3，窗口为一超立方体窗口的选择：

方窗函数指数窗函数Φ(u)Φ(u)Φ(u)正态窗函数Parzen窗口估计φ(u)是以原点x为中心的超立方体。在xi落入方窗时，则有在VN内为1

不在VN内为0落入VN的样本数为所有为1者之和概率密度估计Parzen窗口估计讨论：①每个样本对估计所起的作用依赖于它到x的距离，即

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

②称为的窗函数，取0，1两种值，但有

时可以取0,0.1,0.2……多种数值，例如随xi离x接近的程度，取值由0,0.1,0.2……到1。Parzen窗口估计③要求估计的pN(x)应满足：为满足这两个条件，要求窗函数满足：④窗长度hN对pN(x)的影响若hN太大,pN(x)是p(x)的一个平坦,分辨率低的估计,有平均误差若hN太小,pN(x)是p(x)的一个不稳定的起伏大的估计,有噪声误差为了使这些误差不严重，hN应仔细选择下面进一步讨论窗宽对估计的影响:定义:于是估计式表示成:影响的幅度和宽度。注意到:可看出Parzen窗口估计若Nh较大，则)(jNxxrr-d幅度将较小，而宽度增大是N个低幅缓变的尺度较宽的函数迭加,较平滑，不能跟上的变化，分辨率较低。Parzen窗口估计当hN很小时，δN（X-Xj）幅度很大，宽度很小，近似于以X为中心的δ-函数，此时pN（x）是N个以学习样本xj为中心的尖脉冲在X点处叠加，这会使pN（x）波动，不稳定，可能失去连续性，所以hN的选取对概率密度估计值pN（x）的影响很大。估计量是一随机变量，它依赖于随机的训练样本，所以估计量的性能只能用统计性质表示。在满足下列条件下是渐近无偏估计、均方收敛、均方逼近、且是渐近正态分布。⑴

概密)(xp在x处连续⑵

窗函数满足下列条件①0)(³ju②

ò=j1)(udu③

¥<j)(supuu④

0)(lim1=jÕ=¥®diiuuuParzen窗口估计证明pN(x)是p(x)的渐近无偏估计：Parzen窗口估计例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)即pN(x)?0123456x6x5x3x1x2x4X轴Parzen窗口估计Parzen窗口估计选正态窗函数∵x是一维的上式用图形表示是6个分别以3.2，3.6，3，6，2.5，1.1为中心的正态曲线，而PN(x)则是这些曲线之和。Parzen窗口估计Parzen窗口估计例2：设待估计的概率密度p(x)是个均值为0，方差为1的正态分布。若随机地抽取X样本中的1个、16个、256个作为学习样本xi,试用窗口法估计PN(x)。解：设窗口函数为正态的，σ＝1，μ＝0hN:窗长度，N为样本数，h1为选定可调节的参数。用窗法估计单一正态分布的实验N=∞N=256N=16N=1例3,待估的密度函数为采用正态窗函数x-2.5-210.2502p(x)-2.5<x<-20<x<2x为其它Parzen窗口估计N=∞N=256N=16N=1用窗法估计两个均匀分布的实验Parzen窗分类直接估计后验概率密度进行判决Parzen窗分类器判决边界的划分与窗宽相关Parzen窗分类直接估计后验概率密度存在维数灾难-非参数方法的致命弱点322023/1/17Parzen窗分类332023/1/17Parzen窗分类概率神经网络（PNN）-一种Parzen窗的实现a1a2ad...p1p2pn...InputunitPatternsunits....WdnWd2W111c.Categoryunits...2....Xi训练PNN1.规范化训练数据Xi={a1i,a2i,…,adi|c(类别)}使||Xi||=1;2.修改Xi和模式层单元Pi个之间的权值(w1i,w2i,…,wdi)为(a1i,a2i,…,adi);3.在pi和类别单元c之间增加连接4.直到所有训练数据用完并每个数据只用一次，宣告训练完成。用PNN分类1.归一化待分类实例x;2.对每个模式计算内积3.在有连接的输出层上累加最大的响应类别做为最后分类结果结论：

由上例知窗口法的优点是应用的普遍性。对规则分布，非规则分布，单锋或多峰分布都可用此法进行密度估计。要求样本足够多，才能有较好的估计。因此使计算量，存储量增大。窗函数选取得当有利于提高估计的精度和减少样本的数量。Parzen窗口估计KN近邻估计

在窗口法中存在一个问题是对hN的选择问题。若hN选太小，则大部分体积将是空的（即不包含样本），从而使pN(x)估计不稳定。若hN选太大，则pN(x)估计较平坦，反映不出总体分布的变化，而KN近邻法的思想是以x为中心建立空胞，使v↑，直到捕捉到KN个样本为止。∴称KN-近邻估计。

v的改进，样本密度大，VN↓;

样本密度小，VN↑;

∴p(x)的估计为：KN近邻估计

使PN(x)收敛于P(x)的充分必要条件：①，N与KN同相变化②，KN的变化远小于N的变化

③V1为N=1时的VN值KN近邻估计KN近邻法作后验概率的估计由KN近邻估计知N个已知类别样本落入VN内为KN个样本的概率密度估计为：

N个样本落入VN内有KN个，KN个样本内有ki个样本属于ωi类则联合概率密度：

KN近邻估计根据Bayes公式可求出后验概率：类别为ωi的后验概率就是落在VN内属于ωi的样本ki与VN内总样本数KN的比值∴

∵K近邻准则K近邻分类准则：对于待分样本x，找出它的k个近邻，检查它的类别，把x归于样本最多的那个类别。K近邻分类的错误率随K↑，Pk↓,最低的错误率为Bayes分类。P*PK

最近邻分类准则：待分样本x，找一个离它最近的样本，把x归于最近的样本一类。错误率：

M为类别数P(e)为Bayes估计的错误率最近邻分类法则的错误率P比K近邻错误率还大，但最大不会超过贝叶斯分类器错误率的二倍。PP(e)BayesK近邻最近邻最近邻法将与测试样本最近邻样本的类别作为决策的方法称为最近邻法。

最近邻法的错误率是比较难计算的，这是因为训练样本集的数量总是有限的，有时多一个少一个训练样本对测试样本分类的结果影响很大。红点表示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→∞的极限。为了与基于最小错误率的贝叶斯决策方法对比，下面写出贝叶斯错误率的计算式：

其中最近邻法的错误率

若是两类问题，则

贝叶斯错误率：