非参数估计完整.pptx

《非参数估计完整.pptx》由会员分享，可在线阅读，更多相关《非参数估计完整.pptx（72页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、引言参数化估计：ML方法和Bayesian估计。假设概率密度形式已知。实际中概率密度形式往往未知。实际中概率密度往往是多模的，即有多个局部极大值。实际中样本维数较高，且关于高维密度函数可以表示成一些低维密度函数乘积的假设通常也不成立。本章介绍非参数密度估计方法：能处理任意的概率分布，而不必假设密度函数的形式已知。第1页/共72页主要内容概率密度估计Parzen窗估计k-NN估计最近邻分类器（NN）k-近邻分类器（k-NN）第2页/共72页概率密度估计概率密度估计问题：给定样本集：估计概率分布：第3页/共72页概率密度估计直方图方法：非参数概率密度估计的最简单方法 1.把x的每个分量分成k 个等

2、间隔小窗，（xEd，则形成kd 个小舱）2.统计落入各个小舱内的样本数qi 3.相应小舱的概率密度为：qi/(NV)（N：样本 总数，V：小舱体积）第4页/共72页概率密度估计直方图的例子第5页/共72页概率密度估计非参数概率密度估计的核心思路：一个向量x落在区域R中的概率P为：因此，可以通过统计概率P来估计概率密度函数p(x)第6页/共72页概率密度估计假设N个样本的集合是根据概率密度函数为p(x)的分布独立抽取得到的。那么，有k个样本落在区域R中的概率服从二项式定理：k 的期望值为：对P的估计：当 时，估计是非常精确的第7页/共72页概率密度估计假设p(x)是连续的，且R足够小使得p(x)

3、在R内几乎没有变化。令R是包含样本点x的一个区域，其体积为V，设有N个训练样本，其中有k落在区域R中，则可对概率密度作出一个估计：对p(x)在小区域内的平均值的估计第8页/共72页概率密度估计当样本数量N固定时，体积V的大小对估计的效果影响很大。过大则平滑过多，不够精确；过小则可能导致在此区域内无样本点，k=0。此方法的有效性取决于样本数量的多少，以及区域体积选择的合适。第9页/共72页概率密度估计收敛性问题：样本数量N无穷大是，估计的概率函数是否收敛到真实值？实际中，越精确，要求：实际中，N是有限的：当时，绝大部分区间没有样本：如果侥幸存在一个样本，则：第10页/共72页概率密度估计理论结果

4、：设有一系列包含x 的区域R1，R2，,Rn,，对R1采用1个样本进行估计，对R2用2 个，Rn包含kn个样本。Vn为Rn的体积。为p(x)的第n次估计第11页/共72页概率密度估计如果要求能够收敛到p(x)，那么必须满足：选择Vn选择kn第12页/共72页概率密度估计两种选择方法：第13页/共72页主要内容概率密度估计Parzen窗估计k-NN估计最近邻分类器（NN）k-近邻分类器（k-NN）第14页/共72页Parzen窗估计定义窗函数：假设Rn是一个d维的超立方体。令hn为超立方体一条边的长度，则体积：立方体窗函数为：中心在原点的单位超立方体第15页/共72页Parzen窗估计X处的密度

5、估计为：落入以X为中心的立方体区域的样本数为：可以验证：第16页/共72页窗函数的要求Parzen窗估计过程是一个内插过程，样本xi距离x越近，对概率密度估计的贡献越大，越远贡献越小。只要满足如下条件，就可以作为窗函数：第17页/共72页窗函数的形式 方窗函数指数窗函数正态窗函数其中：第18页/共72页窗口宽度的影响Parzen估计的性能与窗宽参数hn紧密相关当hn较大时，x和中心xi距离大小的影响程度变弱，估计的p(x)较为平滑，分辨率较差。当hn较小时，x和中心xi距离大小的影响程度变强，估计的p(x)较为尖锐，分辨率较好。第19页/共72页窗口宽度的影响第20页/共72页窗函数密度估计值

6、5个样本的Parzen窗估计：第21页/共72页渐近收敛性Parzen窗密度估计的渐近收敛性：无偏性：一致性：当 时，第22页/共72页0123456x6x5x3x1x2x4x 例：对于一个二类（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)解：选正态窗函数第23页/共72页 x是一维的上式用图形表示是6个分别以3.2，3.6，3，6，2.5，1.1为中心的正态曲线，而PN(x)则是这些曲线之和。代入：由图看出，每个样本对估计的贡献与样本间的

7、距离有关，样本越多，PN(x)越准确。第24页/共72页例：设待估计的P(x)是个均值为0，方差为1的正态密度函数。若随机地抽取X样本中的1个、16个、256个作为学习样本xi,试用窗口法估计PN(x)。解：设窗口函数为正态的，1，0hN:窗长度，N为样本数，h1为选定可调节的参数。第25页/共72页v用 窗法估计单一正态分布的实验N=N=256N=16N=1第26页/共72页由图看出,PN(x)随N,h1的变化情况 当N1时，PN(x)是一个以第一个样本为中心的正态曲线，与窗函数差不多。当N16及N=256时 h10.25 曲线起伏很大，噪声大 h11 起伏减小 h14 曲线平坦 当N时，P

8、N(x)收敛于一平滑的正态曲线，估计曲线较好。第27页/共72页例：待估的密度函数为二项分布解：此为多峰情况的估计设窗函数为正态解：此为多峰情况的估计设窗函数为正态x-2.5-210.2502P(x)-2.5x-20 x2x为其它第28页/共72页N=N=256N=16N=1v用 窗法估计两个均匀分布的实验第29页/共72页当N=1、16、256、时的PN(x)估计如图所示 当N1时，PN(x)实际是窗函数。当N16及N=256时 h10.25 曲线起伏大 h11 曲线起伏减小 h14 曲线平坦 当N时，曲线较好。第30页/共72页Parzen窗估计优点由前面的例子可以看出，Parzen窗估计

9、的优点是应用的普遍性。对规则分布，非规则分布，单锋或多峰分布都可用此法进行密度估计。可以获得较为光滑且分辨率较高的密度估计，实现了光滑性和分辨率之间的一个较好平衡。缺点要求样本足够多，才能有较好的估计。因此使计算量，存储量增大。窗宽在整个样本空间固定不变，难以获得区域自适应的密度估计。第31页/共72页识别方法1.保存每个类别所有的训练样本；2.选择窗函数的形式，根据训练样本数n选择窗函数的h宽度；3.识别时，利用每个类别的训练样本计算待识别样本x的类条件概率密度：4.采用Bayes判别准则进行分类。第32页/共72页例子：基于Parzen估计的Bayesian分类器较小较大第33页/共72页

10、主要内容概率密度估计Parzen窗估计Kn近邻估计最近邻分类器（NN）k-近邻分类器（k-NN）第34页/共72页Kn近邻估计在Parzen窗估计中，存在一个问题：对hn的选择。若hn选太小，则大部分体积将是空的（即不包含样本），从而使Pn(x)估计不稳定。若hn选太大，则Pn(x)估计较平坦，反映不出总体分布的变化Kn近邻法的思想：固定样本数量Kn，调整区域体积大小Vn，直至有Kn个样本落入区域中第35页/共72页Kn近邻估计Kn近邻密度估计：固定样本数为，在附近选取与之最近的个样本，计算该个样本分布的最小体积在X处的概率密度估计值为：第36页/共72页渐近收敛的条件渐近收敛的充要条件为：通

11、常选择：第37页/共72页Kn近邻估计例子：第38页/共72页例子：Parzen windowsParzen windowskn-nearest-neighbor斜率不连续当n值为有限值时Kn近邻估计十分粗糙第39页/共72页例子：Parzen windowsParzen windowskn-nearest-neighbor第40页/共72页Kn近邻估计Kn近邻后验概率估计：给定样本集 ，共 类。把一个体积V放在x周围，能够包含进k个样本，其中有 ki个样本属于第i类。那么联合概率密度的估计为：后验概率：第41页/共72页Kn近邻估计例子X属于第i类的后验概率就是体积中标记为第i类的样本个数与

12、体积中全部样本点个数的比值。为了达到最小误差率，选择比值最大的那个类别作为判决结果。如果样本足够多、体积足够小，这样的方法得到的结果是比较准确的！第42页/共72页主要内容概率密度估计Parzen窗估计k-NN估计最近邻分类器（NN）k-近邻分类器（k-NN）第43页/共72页最近邻分类器(NN)v假设样本集v对于样本 ，NN采用如下的决策：v相当于采用 近邻方法估计后验概率，然后采用最大后验概率决策。v分类一个样本的计算复杂度：（采用欧氏距离）第44页/共72页最近邻分类器样本 x=(0.10,0.25)的类别？Training ExamplesLabelsDistance(0.15,0.3

13、5)(0.10,0.28)(0.09,0.30)(0.12,0.20)1 2520.1180.0300.0510.054第45页/共72页最近邻分类器决策边界：Voronoi网格NN分类规则将特征空间分成许多Voronoi网格（Voronoi网格：由一组由连接两邻点直线的垂直平分线组成的连续多边形组成）第46页/共72页最近邻分类器决策边界 在一个Voronoi网格中，每一个点到该 Voronoi网格原型的距离小于到其它所有训练样本点的距离。NN分类器将该Voronoi网格中的点标识为与该原型同类。第47页/共72页最近邻分类器决策边界：在NN分类器中，分类边界对于分类新样本是足够的。但是计算

14、或者存储分类边界是非常困难的目前已经提出许多算法来存储简化后的样本集，而不是整个样本集，使得分类边界不变。第48页/共72页NN分类器的渐近误差界若是n个样本时的误差率，并且：为最小Bayesian错误率，c为类别数。可以证明：第49页/共72页NN分类器的渐近误差界假设能够得到无限多的训练样本和使用任意复杂的分量规则，我们至多只能使误差率降低一半。也就是说，分类信息中的一半信息是由最邻近点提供的！第50页/共72页最近邻分类器当样本有限的情况下，最近邻分类器的分类效果如何？不理想！随着样本数量的增加，分类器收敛到渐近值的速度如何？可能会任意慢，而且误差未必会随着n的增加单调递减！第51页/共

15、72页k-近邻分类器（k-NN）假设样本集对于样本 ，k-NN采用如下的决策：搜索与 最近的 个近邻，如果 个近邻中属于 类的样本最多，则判决 属于 原理：相当于采用 近邻方法估计后验概率，然后采用最大后验概率决策。分类一个样本的计算复杂度：（采用欧氏距离）第52页/共72页k-近邻分类器从测试样本x开始生长，不断扩大区域，直至包含进k个训练样本；把测试样本x的类别归为与之最近的k个训练样本中出现频率最大的类别。第53页/共72页例：k=3(odd value)and x=(0.10,0.25)tv选择 k-NN to x (0.10,0.28,2);(0.12,0.20,2);(0.09,0

16、.30,5)vX属于 2。PrototypesLabels(0.15,0.35)(0.10,0.28)(0.09,0.30)(0.12,0.20)1252第54页/共72页k-近邻分类器决策面：分段线性超平面 每一个超平面对应着最近两点的中垂面。第55页/共72页k-近邻分类器k-NN分类器的误差率在样本数无穷大时趋向于Bayesian最小错误率！第56页/共72页k-NN分类器 近邻分类器 假设样本集 对于样本 ，-NN采用如下的决策：搜索与 最近的 个近邻，如果 个近邻中属于 类的样本最多，为 个，则判决 属于 ，否则拒识。第57页/共72页k-NN分类器k-NN分类器的优点：原理和实现简

17、单，特别适用于大类别问题。当训练样本数较多时，误差界小于2倍的Bayesian最小错误率。第58页/共72页k-NN分类器k-NN分类器的缺点：由于训练样本数有限，k-NN估计的后验概率往往并不精确，从而导致分类错误率远远大于Bayesian最小错误率。搜索近邻需要遍历每一个样本，计算复杂度较大。需要存储所有样本。受噪声和距离测度的选择影响较大。第59页/共72页距离度量距离度量应满足如下三个性质：1.非负性：2.自反性：当且仅当3.对称性：4.三角不等式：距离测度的选取原则：需要精心选择类内变化平缓，类间变化剧烈的距离测度！第60页/共72页常用的距离函数欧几里德距离：(Eucidean D

18、istance)v曼哈顿距离：(Manhattan Distance)第61页/共72页常用的距离函数明氏距离：(Minkowski Distance)v马氏距离：(Mahalanobis Distance)第62页/共72页常用的距离函数角度相似函数：(Angle Distance)v 海明距离：(Hamming Distance)x和y为2值特征矢量：D(x,y)定义为x,y中使得不等式 成立的i的个数。第63页/共72页最近邻分类器的简化最近邻分类器的简化方法可以分为三种：1.部分距离法；2.预分类法；3.需要存储所有样本问题：浓缩、剪枝。第64页/共72页部分距离法定义：Dr(x,y)

19、是r的单调不减函数。令Dmin为当前搜索到的最近邻距离，当待识别样本x与某个训练样本xi的部分距离Dr(x,xi)大于 Dmin时，Dd(x,xi)一定要大于Dmin，所以xi一定不是最近邻，不需要继续计算Dd(x,xi)。第65页/共72页预分类（搜索树）第66页/共72页预分类（搜索树）在特征空间中首先找到m个有代表性的样本点，用这些点代表一部分训练样本；待识别模式x首先与这些代表点计算距离，找到一个最近邻，然后在这个最近邻代表的样本点中寻找实际的最近邻点。这种方法是一个次优的搜索算法。第67页/共72页浓缩、剪枝浓缩(Condensing)：仅保留对决策边界有贡献的样本，删除没有贡献的样

20、本。Original dataConsistent data第68页/共72页浓缩、剪枝浓缩(Condensing)最近邻剪辑算法：删除周围网格全为同类的Voronoi 原型。第69页/共72页浓缩、剪枝剪枝(Pruning)：删除噪声样本点，使决策边界变得更加光滑。Wilson pruning算法:删除那些类别与周围k-NN多数不一致的样本。Original dataWilson editing with k=7第70页/共72页浓缩、剪枝通常先进行剪枝然后进行浓缩第71页/共72页Institute of Intelligent Information Processing,IIIP School of Electronic EngineeringKey Lab.of Intelligent Perception and Image Understanding Xidian University感谢您的观看！第72页/共72页