模式识别-第4章概率密度函数的非参数估计

1、模式识别 概率密度函数的非参数估计第四章第四章 概率密度函数的概率密度函数的非参数估计非参数估计模式识别 概率密度函数的非参数估计4.1 基本思想基本思想模式识别 概率密度函数的非参数估计4.1 基本思想基本思想p令令R是包含样本点是包含样本点x的一个区域，其体积为的一个区域，其体积为V，设有设有n个训练样本，其中有个训练样本，其中有k个落在区域个落在区域R中，则中，则可对概率密度作出一个估计：可对概率密度作出一个估计： k npVxp相当于用相当于用R区域内的平均性质来作为一点区域内的平均性质来作为一点x的估的估计，是一种数据的平滑。计，是一种数据的平滑。模式识别 概率密度函数的非参数估计有

2、效性有效性p当当n固定时，固定时，V的大小对估计的效果影响很的大小对估计的效果影响很大，过大则平滑过多，不够精确；过小则大，过大则平滑过多，不够精确；过小则可能导致在此区域内无样本点，可能导致在此区域内无样本点，k=0。p此方法的有效性取决于样本数量的多少，此方法的有效性取决于样本数量的多少，以及区域体积选择的合适。以及区域体积选择的合适。模式识别 概率密度函数的非参数估计收敛性收敛性p 构造一系列包含构造一系列包含x的区域的区域R1, R2, ，对应，对应n=1,2,，则对，则对p(x)有一系列的估计：有一系列的估计： nnnknpVxp 当满足下列条件时，当满足下列条件时，pn(x)收敛于

3、收敛于p (x)：lim0nnVlimnnk lim0nnkn模式识别 概率密度函数的非参数估计区域选定的两个途径区域选定的两个途径pParzen窗法窗法：区域体积：区域体积V是样本数是样本数n的函数，如：的函数，如：1nVnpK-近邻法近邻法：落在区域内的样本数：落在区域内的样本数k是总样本数是总样本数n的的函数，如：函数，如：nkn模式识别 概率密度函数的非参数估计Parzen窗法和窗法和K-近邻法近邻法模式识别 概率密度函数的非参数估计4.2 Parzen窗方法窗方法p定义定义窗函数窗函数 1,1 20,juu其它1,20,jijnnxxhhix-x其它dnnVh1,jd模式识别 概率密

4、度函数的非参数估计1维数据的窗函数维数据的窗函数模式识别 概率密度函数的非参数估计概率密度函数的估计概率密度函数的估计p超立方体中的样本数：超立方体中的样本数：p概率密度估计：概率密度估计：1nninkhix-x 111nninnpnVhix-xx模式识别 概率密度函数的非参数估计窗函数的要求窗函数的要求p上述过程是一个内插过程，样本上述过程是一个内插过程，样本xi距离距离x越近，越近，对概率密度估计的贡献越大，越远贡献越小。对概率密度估计的贡献越大，越远贡献越小。p只要满足如下条件，就可以作为窗函数：只要满足如下条件，就可以作为窗函数： 0u 1duu模式识别 概率密度函数的非参数估计窗函数

5、的形式窗函数的形式模式识别 概率密度函数的非参数估计方形窗和高斯窗方形窗和高斯窗方形窗函数方形窗函数高斯窗函数高斯窗函数模式识别 概率密度函数的非参数估计窗函数的宽度对估计的影响窗函数的宽度对估计的影响p hn为窗的宽度为窗的宽度hn=5hn=1hn=2hn=0.5模式识别 概率密度函数的非参数估计识别方法识别方法1. 保存每个类别所有的训练样本；保存每个类别所有的训练样本；2. 选择窗函数的形式，根据训练样本数选择窗函数的形式，根据训练样本数n选择窗函选择窗函数的宽度数的宽度h；3. 识别时，利用每个类别的训练样本计算待识别识别时，利用每个类别的训练样本计算待识别样本样本x的类条件概率密度：

6、的类条件概率密度：4. 采用采用Bayes判别准则进行分类。判别准则进行分类。111iinjnijinpnVhx-xx模式识别 概率密度函数的非参数估计Parzen窗的神经网络实现窗的神经网络实现p神经元模型神经元模型1dtiiinetw xw xtyf netfw x模式识别 概率密度函数的非参数估计简化神经元模型简化神经元模型模式识别 概率密度函数的非参数估计Parzen窗函数的神经元表示窗函数的神经元表示p 窗函数取窗函数取Gauss函数，所有的样本归一化，令神经元的权函数，所有的样本归一化，令神经元的权值等于训练样本，即：值等于训练样本，即：,kkwx21,txx x21tkkkww

7、w 222exp2exp21exptkkknkhnettttkkkxwxwxwx x+w w -2w xp 则有：则有：模式识别 概率密度函数的非参数估计概率神经网络概率神经网络(PNN, Probabilistic Neural Network)模式识别 概率密度函数的非参数估计PNN的训练算法的训练算法1. begin initialize j = 0; n =训练样本数，训练样本数，aji=02. do j j + 13. normalize :4. train : wjxj5. if then aji16. until j = njjjxxxjix模式识别 概率密度函数的非参数估计PN

8、N分类算法分类算法1. begin initialize k = 0; x 待识模式待识模式2. do k k + 13. 4. if aki = 1 then 5. until k = n6. return 7. endTkknet w x2exp1iikyynet1argmaxii cclassy 模式识别 概率密度函数的非参数估计径向基函数网络径向基函数网络(RBF, Radial Basis Function)p RBF与与PNN的差异的差异1. 神经元数量神经元数量：PNN模式层神经元数等于训练样本数，模式层神经元数等于训练样本数，而而RBF小于等于训练样本数；小于等于训练样本数；2

9、. 权重权重：PNN模式层到类别层的连接权值恒为模式层到类别层的连接权值恒为1，而，而RBF的需要训练；的需要训练；3. 学习方法学习方法：PNN的训练过程简单，只需一步设置即的训练过程简单，只需一步设置即可，而可，而RBF一般需要反复迭代训练；一般需要反复迭代训练；模式识别 概率密度函数的非参数估计径向基函数网络的训练径向基函数网络的训练pRBF的训练的三种方法：的训练的三种方法：1.根据经验选择每个模式层神经元的权值根据经验选择每个模式层神经元的权值wi以及映射函以及映射函数的宽度数的宽度，用最小二乘法计算模式层到类别层的权，用最小二乘法计算模式层到类别层的权值值；2.用聚类的方法设置模式

10、层每个神经元的权值用聚类的方法设置模式层每个神经元的权值wi以及映以及映射函数的宽度射函数的宽度，用最小二乘法计算模式层到类别层，用最小二乘法计算模式层到类别层的权值的权值；3.通过训练样本用误差纠正算法迭代计算各层神经元的通过训练样本用误差纠正算法迭代计算各层神经元的权值，以及模式层神经元的宽度权值，以及模式层神经元的宽度；模式识别 概率密度函数的非参数估计4.3 近邻分类器近邻分类器p后验概率的估计后验概率的估计Parzen窗法窗法估计的是每个类别的类条件概率密度估计的是每个类别的类条件概率密度 ，而而k-近邻法近邻法是直接估计每个类别的后验概率是直接估计每个类别的后验概率 。将一个体积为

11、将一个体积为V的区域放到待识样本点的区域放到待识样本点x周围，包含周围，包含k个训个训练样本点，其中练样本点，其中ki个属于个属于i类，总的训练样本数为类，总的训练样本数为n，则，则有：有：ipxipx,inik npVx 1,niniiicnnjjppkppkpxxxxx模式识别 概率密度函数的非参数估计k-近邻分类器近邻分类器p k-近邻分类算法近邻分类算法1. 设置参数设置参数k，输入待识别样本，输入待识别样本x；2. 计算计算x与每个训练样本的与每个训练样本的距离距离；3. 选取距离最小的前选取距离最小的前k个样本，统计其中包含个样本，统计其中包含各个类别的样本数各个类别的样本数ki；

12、4. 1argmaxii cclassk 模式识别 概率密度函数的非参数估计k-近邻分类，近邻分类，k=13模式识别 概率密度函数的非参数估计最近邻规则最近邻规则p分类规则分类规则：在训练样本集中寻找与待识别样本：在训练样本集中寻找与待识别样本x距距离最近的样本离最近的样本x，将，将x分类到分类到x所属的类别。所属的类别。p最近邻规则最近邻规则相当于相当于k=1的的k-近邻分类，其分类界面近邻分类，其分类界面可以用可以用Voronoi网格表示。网格表示。模式识别 概率密度函数的非参数估计Voronoi网格网格模式识别 概率密度函数的非参数估计距离度量距离度量p 距离度量应满足如下四个性质：距离

13、度量应满足如下四个性质：1. 非负性非负性：2. 自反性自反性： 当且仅当当且仅当3. 对称性对称性：4. 三角不等式三角不等式：0Da,b0Da,babDDa,bb,aDDDa,bb,ca,c模式识别 概率密度函数的非参数估计常用的距离函数常用的距离函数 121221,dtiiiDxyx yx-yx-yp欧几里德距离欧几里德距离：(Eucidean Distance) 模式识别 概率密度函数的非参数估计常用的距离函数常用的距离函数p街市距离街市距离：(Manhattan Distance)1,diiiDxyx y模式识别 概率密度函数的非参数估计常用的距离函数常用的距离函数p明氏距离明氏距离

14、：(Minkowski Distance)11,mdmiiiDxyx y模式识别 概率密度函数的非参数估计常用的距离函数常用的距离函数 1,tDx yx-y x-yp马氏距离马氏距离：(Mahalanobis Distance) 模式识别 概率密度函数的非参数估计常用的距离函数常用的距离函数p角度相似函数角度相似函数：(Angle Distance),tDx yx yx y模式识别 概率密度函数的非参数估计常用的距离函数常用的距离函数1,tdxxx1,tdyyy,0,1iix y p海明距离海明距离：(Hamming Distance) x和和y为为2值特征矢量：值特征矢量： D(x,y)定义

15、为定义为x,y中使得不等式中使得不等式 成立的成立的i的个的个数。数。iixy模式识别 概率密度函数的非参数估计最近邻分类器的简化最近邻分类器的简化p 最近邻分类器计算的时间复杂度和空间复杂度都最近邻分类器计算的时间复杂度和空间复杂度都为为O(dn)，d为特征维数，通常只有当样本数为特征维数，通常只有当样本数n非非常大时，分类效果才会好。常大时，分类效果才会好。p 简化方法可以分为三种：简化方法可以分为三种：1. 部分距离法；部分距离法；2. 预分类法；预分类法；3. 剪辑近邻法。剪辑近邻法。模式识别 概率密度函数的非参数估计部分距离法部分距离法p 定义：定义：1221rriiiDxyx,yD

16、r(x,y)是是r的单调不减函数。令的单调不减函数。令Dmin为当前搜索到的最近邻为当前搜索到的最近邻距离，当待识别样本距离，当待识别样本x与某个训练样本与某个训练样本xi的部分距离的部分距离Dr(x,xi)大于大于 Dmin时，时， Dd(x,xi)一定要大于一定要大于Dmin ，所以，所以xi一定不是最一定不是最近邻，不需要继续计算近邻，不需要继续计算Dd(x,xi) 。模式识别 概率密度函数的非参数估计预分类（搜索树）预分类（搜索树）模式识别 概率密度函数的非参数估计预分类（搜索树）预分类（搜索树）p在特征空间中首先找到在特征空间中首先找到m个有代表性的样本点，个有代表性的样本点，用这些

17、点代表一部分训练样本；用这些点代表一部分训练样本；p待识别模式待识别模式x首先与这些代表点计算距离，找到一首先与这些代表点计算距离，找到一个最近邻，然后在这个最近邻代表的样本点中寻个最近邻，然后在这个最近邻代表的样本点中寻找实际的最近邻点。找实际的最近邻点。p这种方法是一个这种方法是一个次优次优的搜索算法。的搜索算法。模式识别 概率密度函数的非参数估计剪辑近邻法剪辑近邻法p 最近邻剪辑算法最近邻剪辑算法1. begin initialize j = 0;D = data set; n = number of training samples2. construct the full Voron

18、oi diagram of D3. do j j + 1; 4. Find the Voronoi neighbors of Xj5. if any neighbor is not from the same class as Xj then mark Xj6. until j = n7. Discard all points that are not marked8. Construct the Voronoi diagram of the remaining samples9. end模式识别 概率密度函数的非参数估计剪辑近邻法剪辑近邻法剪辑前剪辑前剪辑后剪辑后模式识别 概率密度函数的非参数估计RCE网络网络模式识别 概率密度函数的非参数估计RCE网络的训练算法网络的训练算法1. begin initialize j=0, n=#patterns, =small pattern, m=max radius，aij=02. do jj+13. train weight: wj=xj4. if then aji = 15. find nearest poin