1、模式识别 概率密度函数的非参数估计第四章第四章 概率密度函数的概率密度函数的非参数估计非参数估计4.1 基本思想基本思想4.1 基本思想基本思想p令令R是包含样本点是包含样本点x的一个区域，其体积为的一个区域，其体积为V，设有设有n个训练样本，其中有个训练样本，其中有k个落在区域个落在区域R中，则中，则可对概率密度作出一个估计：可对概率密度作出一个估计：k npVxp相当于用相当于用R区域内的平均性质来作为一点区域内的平均性质来作为一点x的估的估计，是一种数据的平滑。计，是一种数据的平滑。有效性有效性p当当n固定时，固定时，V的大小对估计的效果影响很的大小对估计的效果影响很大，过大则平滑过多，
2、不够精确；过小则大，过大则平滑过多，不够精确；过小则可能导致在此区域内无样本点，可能导致在此区域内无样本点，k=0。p此方法的有效性取决于样本数量的多少，此方法的有效性取决于样本数量的多少，以及区域体积选择的合适。以及区域体积选择的合适。收敛性收敛性p 构造一系列包含构造一系列包含x的区域的区域R1,R2,，对应，对应n=1,2,，则对，则对p(x)有一系列的估计：有一系列的估计：nnnk npVxp 当满足下列条件时，当满足下列条件时，pn(x)收敛于收敛于p(x)：lim0nnVlimnnk lim0nnkn区域选定的两个途径区域选定的两个途径pParzen窗法窗法：区域体积：区域体积V是
3、样本数是样本数n的函数，如：的函数，如：1nVnpK-近邻法近邻法：落在区域内的样本数：落在区域内的样本数k是总样本数是总样本数n的的函数，如：函数，如：nknParzen窗法和窗法和K-近邻法近邻法4.2 Parzen窗方法窗方法p定义定义窗函数窗函数 1,1 20,juu其它1,20,jijnnxxhhix-x其它dnnVh1,jd 1维数据的窗函数维数据的窗函数概率密度函数的估计概率密度函数的估计p超立方体中的样本数：超立方体中的样本数：p概率密度估计：概率密度估计：1nninkhix-x 111nninnpnVhix-xx窗函数的要求窗函数的要求p上述过程是一个内插过程，样本上述过程是
4、一个内插过程，样本xi距离距离x越近，越近，对概率密度估计的贡献越大，越远贡献越小。对概率密度估计的贡献越大，越远贡献越小。p只要满足如下条件，就可以作为窗函数：只要满足如下条件，就可以作为窗函数：0u 1duu窗函数的形式窗函数的形式窗函数的宽度对估计的影响窗函数的宽度对估计的影响phn称为窗的宽度称为窗的宽度窗函数的宽度对估计的影响窗函数的宽度对估计的影响识别方法识别方法p 保存每个类别所有的训练样本；保存每个类别所有的训练样本；p 选择窗函数的形式，根据训练样本数选择窗函数的形式，根据训练样本数n选择窗函选择窗函数的数的h宽度；宽度；p 识别时，利用每个类别的训练样本计算待识别识别时，利
5、用每个类别的训练样本计算待识别样本样本x的类条件概率密度：的类条件概率密度：p 采用采用Bayes判别准则进行分类。判别准则进行分类。111iinjnijinpnVhx-xxParzen窗的神经网络实现窗的神经网络实现p神经元模型神经元模型1dtiiinetw xw xtyf netfw x简化神经元模型简化神经元模型Parzen窗函数的神经元表示窗函数的神经元表示p 窗函数取窗函数取Gauss函数，所有的样本归一化，令神经元的权函数，所有的样本归一化，令神经元的权值等于训练样本，即：值等于训练样本，即：,kkwx21,txx x21tkkkww w 2exp2tkkknhxwxwxw221e
6、xpexp2knettttkkkx x+w w-2w xp 则有：则有：概率神经网络概率神经网络(PNN,Probabilistic Neural Network)PNN的训练算法的训练算法p begin initialize j=0;n=训练样本数，训练样本数，aji=0p do j j+1p normalize:p train:wjxjp if then aji1p until j=njjjxxxjixPNN分类算法分类算法p begin initialize k=0;x 待识模式待识模式p do k k+1p p if aki=1 then p until k=np return p e
7、ndTkknet w x2exp1iikyynet1argmaxii cclassy 径向基函数网络径向基函数网络(RBF,Radial Basis Function)p RBF与与PNN的差异的差异n 神经元数量神经元数量：PNN模式层神经元数等于训练样本数，模式层神经元数等于训练样本数，而而RBF小于等于训练样本数；小于等于训练样本数；n 权重权重：PNN模式层到类别层的连接权值恒为模式层到类别层的连接权值恒为1，而，而RBF的需要训练；的需要训练；1.学习方法学习方法：PNN的训练过程简单，只需一步设置即的训练过程简单，只需一步设置即可，而可，而RBF一般需要反复迭代训练；一般需要反复迭
8、代训练；径向基函数网络的训练径向基函数网络的训练pRBF的训练的三种方法：的训练的三种方法：n根据经验选择每个模式层神经元的权值根据经验选择每个模式层神经元的权值wi以及映射函以及映射函数的宽度数的宽度，用最小二乘法计算模式层到类别层的权，用最小二乘法计算模式层到类别层的权值；值；n用聚类的方法设置模式层每个神经元的权值用聚类的方法设置模式层每个神经元的权值wi以及映以及映射函数的宽度射函数的宽度，用最小二乘法计算模式层到类别层，用最小二乘法计算模式层到类别层的权值；的权值；n通过训练样本用误差纠正算法迭代计算各层神经元的通过训练样本用误差纠正算法迭代计算各层神经元的权值，以及模式层神经元的宽
9、度权值，以及模式层神经元的宽度；4.3 近邻分类器近邻分类器p后验概率的估计后验概率的估计Parzen窗法窗法估计的是每个类别的类条件概率密度估计的是每个类别的类条件概率密度 ，而而k-近邻法近邻法是直接估计每个类别的后验概率是直接估计每个类别的后验概率 。将一个体积为将一个体积为V的区域放到待识样本点的区域放到待识样本点x周围，包含周围，包含k个训个训练样本点，其中练样本点，其中ki个属于个属于i类，总的训练样本数为类，总的训练样本数为n，则，则有：有：ipxipx,inik npVx 1,niniiicnnjjppkppkpxxxxxk-近邻分类器近邻分类器p k-近邻分类算法近邻分类算法
10、n 设置参数设置参数k，输入待识别样本，输入待识别样本x；n 计算计算x与每个训练样本的与每个训练样本的距离距离；n 选取距离最小的前选取距离最小的前k个样本，统计其中包含个样本，统计其中包含各个类别的样本数各个类别的样本数ki；1.1argmaxii cclassk k-近邻分类，近邻分类，k=13最近邻规则最近邻规则p分类规则分类规则：在训练样本集中寻找与待识别样本：在训练样本集中寻找与待识别样本x距距离最近的样本离最近的样本x，将，将x分类到分类到x所属的类别。所属的类别。p最近邻规则最近邻规则相当于相当于k=1的的k-近邻分类，其分类界面近邻分类，其分类界面可以用可以用Voronoi网
11、格表示。网格表示。Voronoi网格网格距离度量距离度量p 距离度量应满足如下四个性质：距离度量应满足如下四个性质：n 非负性非负性：n 自反性自反性：当且仅当当且仅当n 对称性对称性：1.三角不等式三角不等式：0Da,b0Da,babDDa,bb,aDDDa,bb,ca,c常用的距离函数常用的距离函数 121221,dtiiiDxyx yx-yx-yp欧几里德距离欧几里德距离：(Eucidean Distance)常用的距离函数常用的距离函数p街市距离街市距离：(Manhattan Distance)1,diiiDxyx y常用的距离函数常用的距离函数p明氏距离明氏距离：(Minkowski
12、 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)定义为定义为x,y中使得不等式中使得不等式 成立的成立的i的个的个数。数。iixy最近邻分类器的简化最近邻分类器的简化p 最近邻分类器
13、计算的时间复杂度和空间复杂度都最近邻分类器计算的时间复杂度和空间复杂度都为为O(dn)，d为特征维数，通常只有当样本数为特征维数，通常只有当样本数n非非常大时，分类效果才会好。常大时，分类效果才会好。p 简化方法可以分为三种：简化方法可以分为三种：n 部分距离法；部分距离法；n 预分类法；预分类法；1.剪辑近邻法。剪辑近邻法。部分距离法部分距离法p 定义：定义：1221rriiiDxyx,yDr(x,y)是是r的单调不减函数。令的单调不减函数。令Dmin为当前搜索到的最近邻为当前搜索到的最近邻距离，当待识别样本距离，当待识别样本x与某个训练样本与某个训练样本xi的部分距离的部分距离Dr(x,x
14、i)大于大于 Dmin时，时，Dd(x,xi)一定要大于一定要大于Dmin，所以，所以xi一定不是最一定不是最近邻，不需要继续计算近邻，不需要继续计算Dd(x,xi)。预分类（搜索树）预分类（搜索树）预分类（搜索树）预分类（搜索树）p在特征空间中首先找到在特征空间中首先找到m个有代表性的样本点，个有代表性的样本点，用这些点代表一部分训练样本；用这些点代表一部分训练样本；p待识别模式待识别模式x首先与这些代表点计算距离，找到一首先与这些代表点计算距离，找到一个最近邻，然后在这个最近邻代表的样本点中寻个最近邻，然后在这个最近邻代表的样本点中寻找实际的最近邻点。找实际的最近邻点。p这种方法是一个这种
15、方法是一个次优次优的搜索算法。的搜索算法。剪辑近邻法剪辑近邻法p 最近邻剪辑算法最近邻剪辑算法n begin initialize j=0;D=data set;n=number of training samplesn construct the full Voronoi diagram of Dn do j j+1;n Find the Voronoi neighbors of Xjn if any neighbor is not from the same class as Xjn then mark Xjn until j=nn Discard all points that are
16、not markedn Construct the Voronoi diagram of the remaining samplesn end剪辑近邻法剪辑近邻法剪辑近邻法剪辑近邻法RCE网络网络RCE网络的训练算法网络的训练算法p begin initialize j=0,n=#patterns,=small pattern,m=max radius，aij=0p do jj+1p train weight:wj=xjp if then aji=1p find nearest point not in i:p set radius:p until j=nargminijDxxx,xmin,jjmD x,xjixRCE网络的分类算法网络的分类算法p begin initialize j=0,k=0,x,p do jj+1p if thenp until j=np if category of all is the same p then return the labelp else “ambiguous”labeltD ttjDDx,jjD x xjtD x
