《哈工大模式识别概率密度函数的非参数估计课件》由会员分享,可在线阅读,更多相关《哈工大模式识别概率密度函数的非参数估计课件(46页珍藏版)》请在金锄头文库上搜索。
1、模式识别 概率密度函数的非参数估计第四章第四章 概率密度函数的概率密度函数的非参数估计非参数估计哈工大模式识别概率密度函数的非参数估计模式识别 概率密度函数的非参数估计4.1 基本思想基本思想模式识别 概率密度函数的非参数估计4.1 基本思想基本思想p令令R是包含样本点是包含样本点x的一个区域,其体积为的一个区域,其体积为V,设,设有有n个训练样本,其中有个训练样本,其中有k个落在区域个落在区域R中,则可中,则可对概率密度作出一个估计:对概率密度作出一个估计:p相当于用相当于用R区域内的平均性质来作为一点区域内的平均性质来作为一点x的估的估计,是一种数据的平滑。计,是一种数据的平滑。模式识别
2、概率密度函数的非参数估计有效性有效性p当当n固定时,固定时,V的大小对估计的效果影响很的大小对估计的效果影响很大,过大则平滑过多,不够精确;过小则大,过大则平滑过多,不够精确;过小则可能导致在此区域内无样本点,可能导致在此区域内无样本点,k=0。p此方法的有效性取决于样本数量的多少,此方法的有效性取决于样本数量的多少,以及区域体积选择的合适。以及区域体积选择的合适。模式识别 概率密度函数的非参数估计收敛性收敛性p构造一系列包含构造一系列包含x的区域的区域R1, R2, ,对应,对应n=1,2,,则对,则对p(x)有一系列的估计:有一系列的估计:p当满足下列条件时,当满足下列条件时,pn(x)收
3、敛于收敛于p (x):模式识别 概率密度函数的非参数估计区域选定的两个途径区域选定的两个途径pParzen窗法:区域体积窗法:区域体积V是样本数是样本数n的函数,如:的函数,如:pK-近邻法:落在区域内的样本数近邻法:落在区域内的样本数k是总样本数是总样本数n的的函数,如:函数,如:模式识别 概率密度函数的非参数估计Parzen窗法和窗法和K-近邻法近邻法模式识别 概率密度函数的非参数估计4.2 Parzen窗方法窗方法p定义窗函数定义窗函数模式识别 概率密度函数的非参数估计1维数据的窗函数维数据的窗函数模式识别 概率密度函数的非参数估计概率密度函数的估计概率密度函数的估计p超立方体中的样本数
4、:超立方体中的样本数:p概率密度估计:概率密度估计:模式识别 概率密度函数的非参数估计窗函数的要求窗函数的要求p上述过程是一个内插过程,样本上述过程是一个内插过程,样本xi距离距离x越近,对越近,对概率密度估计的贡献越大,越远贡献越小。概率密度估计的贡献越大,越远贡献越小。p只要满足如下条件,就可以作为窗函数:只要满足如下条件,就可以作为窗函数:模式识别 概率密度函数的非参数估计窗函数的形式窗函数的形式模式识别 概率密度函数的非参数估计窗函数的宽度对估计的影响窗函数的宽度对估计的影响phn称为窗的宽度称为窗的宽度模式识别 概率密度函数的非参数估计窗函数的宽度对估计的影响窗函数的宽度对估计的影响
5、模式识别 概率密度函数的非参数估计识别方法识别方法1.保存每个类别所有的训练样本;保存每个类别所有的训练样本;2.选择窗函数的形式,根据训练样本数选择窗函数的形式,根据训练样本数n选择窗函选择窗函数的数的h宽度;宽度;3.识别时,利用每个类别的训练样本计算待识别识别时,利用每个类别的训练样本计算待识别样本样本x的类条件概率密度:的类条件概率密度:4.采用采用Bayes判别准则进行分类。判别准则进行分类。模式识别 概率密度函数的非参数估计Parzen窗的神经网络实现窗的神经网络实现p神经元模型神经元模型模式识别 概率密度函数的非参数估计简化神经元模型简化神经元模型模式识别 概率密度函数的非参数估
6、计Parzen窗函数的神经元表示窗函数的神经元表示p窗函数取窗函数取Gauss函数,所有的样本归一化,令神经元的权函数,所有的样本归一化,令神经元的权值等于训练样本,即:值等于训练样本,即:p则有:则有:模式识别 概率密度函数的非参数估计概率神经网络概率神经网络(PNN, Probabilistic Neural Network)模式识别 概率密度函数的非参数估计PNN的训练算法的训练算法1.begin initialize j = 0; n =训练样本数,训练样本数,aij=02.do j j + 13. normalize :4. train : wjxj5. if then aji16.
7、until j = n模式识别 概率密度函数的非参数估计PNN分类算法分类算法1.begin initialize k = 0; x 待识模式待识模式2. do k k + 13. 4. if aki = 1 then 5. until k = n6. return 7.end模式识别 概率密度函数的非参数估计径向基函数网络径向基函数网络(RBF, Radial Basis Function)pRBF与与PNN的差异的差异1.PNN模式层神经元数等于训练样本数,而模式层神经元数等于训练样本数,而RBF小于小于等于训练样本数;等于训练样本数;2.PNN模式层到类别层的连接权值恒为模式层到类别层的
8、连接权值恒为1,而,而RBF的需的需要训练;要训练;3.PNN的训练过程简单,只需一步设置即可,而的训练过程简单,只需一步设置即可,而RBF一般需要反复迭代训练;一般需要反复迭代训练;模式识别 概率密度函数的非参数估计径向基函数网络的训练径向基函数网络的训练pRBF的训练的三种方法:的训练的三种方法:1.根据经验选择每个模式层神经元的权值根据经验选择每个模式层神经元的权值wi以及映射函以及映射函数的宽度数的宽度,用最小二乘法计算模式层到类别层的权,用最小二乘法计算模式层到类别层的权值值;2.用聚类的方法设置模式层每个神经元的权值用聚类的方法设置模式层每个神经元的权值wi以及映以及映射函数的宽度
9、射函数的宽度,用最小二乘法计算模式层到类别层,用最小二乘法计算模式层到类别层的权值的权值;3.通过训练样本用误差纠正算法迭代计算各层神经元的通过训练样本用误差纠正算法迭代计算各层神经元的权值,以及模式层神经元的宽度权值,以及模式层神经元的宽度;模式识别 概率密度函数的非参数估计4.3 近邻分类器近邻分类器p后验概率的估计后验概率的估计Parzen窗法估计的是每个类别的类条件概率密度窗法估计的是每个类别的类条件概率密度 ,而而k-近邻法是直接估计每个类别的后验概率近邻法是直接估计每个类别的后验概率 。将一个体积为将一个体积为V的区域放到待识样本点的区域放到待识样本点x周围,包含周围,包含k个训个
10、训练样本点,其中练样本点,其中ki个属于个属于i类,总的训练样本数为类,总的训练样本数为n,则,则有:有:模式识别 概率密度函数的非参数估计k-近邻分类器近邻分类器pk-近邻分类算法近邻分类算法1.设置参数设置参数k,输入待识别样本,输入待识别样本x;2.计算计算x与每个训练样本的与每个训练样本的距离距离;3.选取距离最小的前选取距离最小的前k个样本,统计其中包含个样本,统计其中包含各个类别的样本数各个类别的样本数ki;4. 模式识别 概率密度函数的非参数估计k-近邻分类,近邻分类,k=13模式识别 概率密度函数的非参数估计最近邻规则最近邻规则p分类规则:在训练样本集中寻找与待识别样本分类规则
11、:在训练样本集中寻找与待识别样本x距距离最近的样本离最近的样本x,将,将x分分类到到x所属的所属的类别。p最近最近邻规则相当于相当于k=1的的k-近近邻分分类,其分,其分类界面界面可以用可以用Voronoi网格表示。网格表示。模式识别 概率密度函数的非参数估计Voronoi网格网格模式识别 概率密度函数的非参数估计距离度量距离度量p距离度量应满足如下四个性质:距离度量应满足如下四个性质:1.非负性:非负性:2.自反性:自反性: 当且仅当当且仅当3.对称性:对称性:4.三角不等式:三角不等式:模式识别 概率密度函数的非参数估计常用的距离函数常用的距离函数p欧几里德距离:欧几里德距离:(Eucid
12、ean Distance) 模式识别 概率密度函数的非参数估计常用的距离函数常用的距离函数p街市距离:街市距离:(Manhattan Distance)模式识别 概率密度函数的非参数估计常用的距离函数常用的距离函数p明氏距离:明氏距离:(Minkowski Distance)模式识别 概率密度函数的非参数估计常用的距离函数常用的距离函数p马氏距离:马氏距离:(Mahalanobis Distance) 模式识别 概率密度函数的非参数估计常用的距离函数常用的距离函数p角度相似函数:角度相似函数:(Angle Distance)模式识别 概率密度函数的非参数估计常用的距离函数常用的距离函数p海明距
13、离:海明距离:(Hamming Distance) x和和y为为2值特征矢量:值特征矢量: D(x,y)定义为定义为x,y中使得不等式中使得不等式 成立的成立的i的个的个数。数。模式识别 概率密度函数的非参数估计最近邻分类器的简化最近邻分类器的简化p最近邻分类器计算的时间复杂度和空间复杂度都最近邻分类器计算的时间复杂度和空间复杂度都为为O(dn),d为特征维数,通常只有当样本数为特征维数,通常只有当样本数n非非常大时,分类效果才会好。常大时,分类效果才会好。p简化方法可以分为三种:简化方法可以分为三种:1.部分距离法;部分距离法;2.预分类法;预分类法;3.剪辑近邻法。剪辑近邻法。模式识别 概
14、率密度函数的非参数估计部分距离法部分距离法p定义:定义:Dr(x,y)是是r的单调不减函数。令的单调不减函数。令Dmin为当前搜索到的最近邻为当前搜索到的最近邻距离,当待识别样本距离,当待识别样本x与某个训练样本与某个训练样本xi的部分距离的部分距离Dr(x,xi)大于大于 Dmin时,时, Dd(x,xi)一定要大于一定要大于Dmin ,所以,所以xi一定不是最一定不是最近邻,不需要继续计算近邻,不需要继续计算Dd(x,xi) 。模式识别 概率密度函数的非参数估计预分类(搜索树)预分类(搜索树)模式识别 概率密度函数的非参数估计预分类(搜索树)预分类(搜索树)p在特征空间中首先找到在特征空间
15、中首先找到m个有代表性的样本点,个有代表性的样本点,用这些点代表一部分训练样本;用这些点代表一部分训练样本;p待识别模式待识别模式x首先与这些代表点计算距离,找到一首先与这些代表点计算距离,找到一个最近邻,然后在这个最近邻代表的样本点中寻个最近邻,然后在这个最近邻代表的样本点中寻找实际的最近邻点。找实际的最近邻点。p这种方法是一个次优的搜索算法。这种方法是一个次优的搜索算法。模式识别 概率密度函数的非参数估计剪辑近邻法剪辑近邻法p最近邻剪辑算法最近邻剪辑算法1.begin initialize j = 0;D = data set; n = number of training samples
16、2.construct the full Voronoi 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模式识别 概率密度函数的非参数估计剪辑近邻法剪辑近邻法模式识别
17、概率密度函数的非参数估计剪辑近邻法剪辑近邻法模式识别 概率密度函数的非参数估计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 point not in i:6. set radius: 7.until j = n模式识别 概率密度函数的非参数估计模式识别 概率密度函数的非参数估计RCE网络的分类算法网络的分类算法1.begin initialize j=0, k=0, x, 2. do jj+13. if then4. until j = n5. if category of all is the same 6. then return the label7. else “ambiguous” label