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