概率密度函数的非参数估计课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 概率密度函数的非参数估计,第四章 概率密度函数的非参数估计,1,4.1 基本思想,4.1 基本思想,2,4.1 基本思想,令R是包含样本点,x,的一个区域，其体积为V，设有n个训练样本，其中有k落在区域R中，则可对概率密度作出一个估计：,相当于用R区域内的平均性质来作为一点,x,估计，是一种数据的平滑。,4.1 基本思想令R是包含样本点x的一个区域，其体积为V，设,3,有效性,当n固定时，V的大小对估计的效果影响很大，过大则平滑过多，不够精确；过小则可能导致在此区域内无样本点，k=0。,此方法的有效性取决于样本数量的多少，以及区域体积选择的合适。,有效性,4,收敛性,构造一系列包含,x,的区域R,1,R,2,，对应n=1,2,，则对p(,x,)有一系列的估计：,当满足下列条件时，p,n,(,x,)收敛于p,(,x,)：,收敛性构造一系列包含x的区域R1,R2,，对应n=1,5,区域选定的两个途径,Parzen窗法：区域体积V是样本数n的函数，如：,K-近邻法：落在区域内的样本数k是总样本数n的函数，如：,区域选定的两个途径Parzen窗法：区域体积V是样本数n的函,6,Parzen窗法和K-近邻法,Parzen窗法和K-近邻法,7,4.2 Parzen窗方法,定义窗函数,4.2 Parzen窗方法定义窗函数,8,1维数据的窗函数,1维数据的窗函数,9,概率密度函数的估计,超立方体中的样本数：,概率密度估计：,概率密度函数的估计超立方体中的样本数：,10,窗函数的要求,上述过程是一个内插过程，样本,x,i,距离,x,越近，对概率密度估计的贡献越大，越远贡献越小。,只要满足如下条件，就可以作为窗函数：,窗函数的要求上述过程是一个内插过程，样本xi距离x越近，对概,11,窗函数的形式,窗函数的形式,12,窗函数的宽度对估计的影响,h,n,称为窗的宽度,窗函数的宽度对估计的影响hn称为窗的宽度,13,窗函数的宽度对估计的影响,窗函数的宽度对估计的影响,14,识别方法,保存每个类别所有的训练样本；,选择窗函数的形式，根据训练样本数n选择窗函数的h宽度；,识别时，利用每个类别的训练样本计算待识别样本,x,的类条件概率密度：,采用Bayes判别准则进行分类。,识别方法保存每个类别所有的训练样本；,15,Parzen窗的神经网络实现,神经元模型,Parzen窗的神经网络实现神经元模型,16,简化神经元模型,简化神经元模型,17,Parzen窗函数的神经元表示,窗函数取Gauss函数，所有的样本归一化，令神经元的权值等于训练样本，即：,则有：,Parzen窗函数的神经元表示窗函数取Gauss函数，所有的,18,概率神经网络,(PNN,Probabilistic Neural Network),概率神经网络(PNN,Probabilistic Neur,19,PNN的训练算法,begin initialize,j,=0,;n,=训练样本数，,a,ij,=0,do,j,j,+1,normalize:,train,:,w,j,x,j,if,then,a,ji,1,until,j,=,n,PNN的训练算法begin initialize j=0,20,PNN分类算法,begin initialize,k,=0,;,x,待识模式,do,k,k,+1,if,a,ki,=1,then,until,k,=,n,return,end,PNN分类算法begin initialize k=0;,21,径向基函数网络,(RBF,Radial Basis Function),RBF与PNN的差异,PNN模式层神经元数等于训练样本数，而RBF小于等于；,PNN模式层到类别层的连接权值恒为1，而RBF的需要训练；,PNN的训练过程简单，只需一步设置即可，而RBF一般需要反复迭代训练；,径向基函数网络(RBF,Radial Basis Func,22,径向基函数网络的训练,RBF的训练的三种方法：,根据经验选择每个模式层神经元的权值w,i,以及映射函数的宽度,，用最小二乘法计算模式层到类别层的权值；,用聚类的方法设置模式层每个神经元的权值w,i,以及映射函数的宽度,，用最小二乘法计算模式层到类别层的权值；,通过训练样本用误差纠正算法迭代计算各层神经元的权值，以及模式层神经元的宽度,；,径向基函数网络的训练RBF的训练的三种方法：,23,4.3 近邻分类器,后验概率的估计,Parzen窗法估计的是每个类别的类条件概率密度 ，而k-近邻法是直接估计每个类别的后验概率 。,将一个体积为V的区域放到待识样本点,x,周围，包含k个训练样本点，其中k,i,个属于,i,类，总的训练样本数为n，则有：,4.3 近邻分类器后验概率的估计,24,k-近邻分类器,k-近邻分类算法,设置参数k，输入待识别样本,x,；,计算,x,与每个训练样本的,距离,；,选取距离最小的前k个样本，统计其中包含各个类别的样本数k,i,；,k-近邻分类器k-近邻分类算法,25,k-近邻分类，k=13,k-近邻分类，k=13,26,最近邻规则,分类规则：在训练样本集中寻找与待识别样本,x,距离最近的样本,x,，将,x,分类到,x,所属的类别。,最近邻规则相当于k=1的k-近邻分类，其分类界面可以用Voronoi网格表示。,最近邻规则分类规则：在训练样本集中寻找与待识别样本x距离最近,27,Voronoi网格,Voronoi网格,28,距离度量,距离度量应满足如下三个性质：,非负性：,自反性：当且仅当,对称性：,三角不等式：,距离度量距离度量应满足如下三个性质：,29,常用的距离函数,欧几里德距离：(Eucidean Distance),常用的距离函数欧几里德距离：(Eucidean Distan,30,常用的距离函数,街市距离：(Manhattan Distance),常用的距离函数街市距离：(Manhattan Distanc,31,常用的距离函数,明氏距离：(Minkowski Distance),常用的距离函数明氏距离：(Minkowski Distanc,32,常用的距离函数,马氏距离：(Mahalanobis Distance),常用的距离函数马氏距离：(Mahalanobis Dista,33,常用的距离函数,角度相似函数：(Angle Distance),常用的距离函数角度相似函数：(Angle Distance),34,常用的距离函数,海明距离：(Hamming Distance),x,和,y,为2值特征矢量：,D(,x,y,)定义为,x,y,中使得不等式 成立的i的个数。,常用的距离函数海明距离：(Hamming Distance),35,最近邻分类器的简化,最近邻分类器计算的时间复杂度和空间复杂度都为O(dn)，d为特征维数，通常只有当样本数n非常大时，分类效果才会好。,简化方法可以分为三种：,部分距离法；,预分类法；,剪辑近邻法。,最近邻分类器的简化最近邻分类器计算的时间复杂度和空间复杂度都,36,部分距离法,定义：,D,r,(,x,y,)是r的单调不减函数。令D,min,为当前搜索到的最近邻距离，当待识别样本,x,与某个训练样本,x,i,的部分距离D,r,(,x,x,i,)大于 D,min,时，D,d,(,x,x,i,)一定要大于D,min,，所以,x,i,一定不是最近邻，不需要继续计算D,d,(,x,x,i,)。,部分距离法定义：Dr(x,y)是r的单调不减函数。令Dmi,37,预分类（搜索树）,预分类（搜索树）,38,预分类（搜索树）,在特征空间中首先找到m个有代表性的样本点，用这些点代表一部分训练样本；,待识别模式,x,首先与这些代表点计算距离，找到一个最近邻，然后在这个最近邻代表的样本点中寻找实际的最近邻点。,这种方法是一个次优的搜索算法。,预分类（搜索树）在特征空间中首先找到m个有代表性的样本点，用,39,剪辑近邻法,最近邻剪辑算法,begin initialize,j,=0,;D,=data set,;n,=number of training samples,construct the full Voronoi diagram of,D,do,j,j,+1;,Find the Voronoi neighbors of,X,j,if,any neighbor is not from the same class as,X,j,then,mark,X,j,until,j,=,n,Discard all points that are not marked,Construct the Voronoi diagram of the remaining samples,end,剪辑近邻法最近邻剪辑算法,40,剪辑近邻法,剪辑近邻法,41,剪辑近邻法,剪辑近邻法,42,RCE网络,RCE网络,43,RCE网络的训练算法,begin initialize,j=0,n=#patterns,=small pattern,m,=max radius，a,ij,=0,do,j,j+1,train weight,:,w,j,=,x,j,if,then,a,ji,=1,find nearest point not in,i,:,set radius,:,until,j=n,RCE网络的训练算法begin initialize j=0,44,概率密度函数的非参数估计课件,45,RCE网络的分类算法,begin initialize,j=0,k=0,x,do,j,j+1,if,then,until,j=n,if,category of all is the same,then,return the label,else,“ambiguous”label,RCE网络的分类算法begin initialize j=0,46,