概率密度估计及近邻法课件.ppt

1、第三章第三章概率密度函数估计及近邻法概率密度函数估计及近邻法Estimation of Probability Density Function and The Nearest Neighbor Rule1 引言引言2 总体分布的参数估计总体分布的参数估计 极大似然估计极大似然估计 贝叶斯估计参数贝叶斯估计参数3 总体分布的非参数估计总体分布的非参数估计 Parzen窗法窗法 kN近邻法近邻法4 近邻法则近邻法则 1 1 引言引言 基于样本的两步贝叶斯决策：基于样本的两步贝叶斯决策：估计类条件概率密度估计类条件概率密度 和先验概率和先验概率 ；利用利用 和和 完成分类器设计。完成分类器设计。(

2、第二章第二章)本章讨论从本章讨论从样本集推断样本集推断总体概率分布总体概率分布p(x|w wi)。而。而样本的先验概率样本的先验概率P(w wi)的估计较易实现。的估计较易实现。概率密度函数含概率密度函数含参数参数和和形式形式两方面内容，分别称两方面内容，分别称为参数估计和非参数估计。其估计方法：为参数估计和非参数估计。其估计方法：1.监督监督参数估计参数估计 已知样本类别已知样本类别w wi及其及其p(x|w wi)形式，而参数未知，形式，而参数未知，需从训练样本需从训练样本x估计参数估计参数q q，如一元正态分布的，如一元正态分布的m m、s s 2等参数。等参数。)(ixpw)(iPw)

3、(ixpw)(iPw2.非监督参数估计非监督参数估计 未知样本类别未知样本类别w wi，已知概率密度函数，已知概率密度函数p(x|w wi)的形的形式，但参数未知，需从样本式，但参数未知，需从样本x估计参数。估计参数。上述两种均可用上述两种均可用极极(最最)大似然法大似然法和和Bayes估计法估计法来来估计参数。估计参数。3.非参数估计即估计非参数估计即估计p(x|w wi)形式形式 已知样本类别，但未知概率密度函数的形式，要已知样本类别，但未知概率密度函数的形式，要从样本推断从样本推断p(x|w wi)属于哪种属于哪种分布分布。可用可用Parzen窗法窗法和和kN近邻法近邻法。4.近邻法则不

4、属于估计内容近邻法则不属于估计内容 直接利用样本设计分类器。非参数直接利用样本设计分类器。非参数(即分类中不即分类中不需要估计概率密度函数需要估计概率密度函数)方法之一。方法之一。5.参数估计的几个基本术语参数估计的几个基本术语统计量：每个训练样本都包含总体信息。根据统计量：每个训练样本都包含总体信息。根据从总体中抽取的样本集构造某种函数从总体中抽取的样本集构造某种函数,该函数统该函数统计学中称为统计量。计学中称为统计量。参数空间：概率密度形式已知，参数参数空间：概率密度形式已知，参数q q 未知未知,q q 可取值的集合称为参数空间，记为可取值的集合称为参数空间，记为。点估计、估计量和估计值

5、：构造一个统计量点估计、估计量和估计值：构造一个统计量f(x1,xn)作为参数作为参数q q 的估计量的估计量 。如果。如果x1,xn属于某类，代入统计量属于某类，代入统计量f，就可，就可得到该类具体的得到该类具体的估计值。本章参数估计属于点估计。估计值。本章参数估计属于点估计。区间估计要求用区间区间估计要求用区间(d1,d2)作为作为q q 可能取值范可能取值范围的一种估计。该区间称为置信区间。围的一种估计。该区间称为置信区间。q2 总体分布的参数估计总体分布的参数估计1.极极(最最)大似然估计大似然估计 基本原理基本原理 把参数把参数q q 看成确定的看成确定的(非随机非随机)但取值未知，

6、最但取值未知，最好估计值是在样本好估计值是在样本x概率为最大条件下得到的概率为最大条件下得到的。假设：假设：按类别把样本集分成按类别把样本集分成c个子集个子集 x1,x2,xc，其，其中中xj中的样本是从概率密度为中的样本是从概率密度为p(x|w wj)的总体中的总体中独立抽取的。独立抽取的。p(x|w wj)形式已知形式已知,参数参数q qj未知未知,可写成可写成p(x|w wj,q qj)。不同类的参数独立，即不同类的参数独立，即xi不包含不包含q qj信息信息(ij)这这样每一类可样每一类可单独处理单独处理，共处理，共处理c个独立问题。个独立问题。设某类有设某类有N个样本组成了样本集个样

7、本组成了样本集 xx1,x2,xN 样本是独立从该类抽取的，因此样本是独立从该类抽取的，因此N个随机变量个随机变量的联合概率密度的联合概率密度 统计学中称统计学中称p(x|q q)为相对于样本集为相对于样本集x的的q q 的的似然似然函数函数l(q q)似然函数似然函数l(q q)给出了从总体中抽取的给出了从总体中抽取的x1,x2,xN这这N个样本的概率。个样本的概率。极大似然估计值定义：极大似然估计值定义：令令l(q q)为样本集为样本集x的似然函数，在的似然函数，在的参数空间的参数空间中能使中能使l(q q)极大化的那个极大化的那个 值。值。)()()(),()(2121qqqqqNNxp

8、xpxpxxxplNkkNxpxxxpxp121)(),()(qqqq 极大似然法的主要思想：如果在一次观察中一个极大似然法的主要思想：如果在一次观察中一个事件出现了，则这个事件出现的可能性最大。事事件出现了，则这个事件出现的可能性最大。事件件xx1,x2,xN在一次观察中在一次观察中(即从总体中抽取即从总体中抽取N个样本个样本)出现了，就可认为出现了，就可认为 p(x|q q)达到极大值，达到极大值，即在参数空间中使似然函数极大化的即在参数空间中使似然函数极大化的 值。值。一个简单的例子：一个简单的例子：q为均值。对应达极大点时在点时较小点和有不同值的概密计算自左向右取不同值时，当。此时似然

9、法估计用极大集已知，通过抽出的样本，现方差布设一维样本服从正态分qqqqqmqmsmq,)|(,)|()|(,),()|(616212xpCBAxpxpxxxxxNxpkk 假设似然函数假设似然函数p(x|q q)对未知参数对未知参数q q 是连续可微的是连续可微的，则，则 可由典型的求极值的方法求得。可由典型的求极值的方法求得。求极大值的求极大值的必要条件必要条件 单个单个q q 的情况下：的情况下：若若q q 是向量，有是向量，有s个分量个分量q q=q q1,q qs T，则多变量，则多变量的梯度算子的梯度算子 对数似然函数对数似然函数H(q q)是单调的增函数，为计算方是单调的增函数，

10、为计算方便，一般用对数似然函数。便，一般用对数似然函数。sqqq10)(qqddlq 使似然函数最大。只有个解，解，如图中有有时上式可能没有唯一。，就是极大似然估计值得到的解个方程的从而下个样本独立抽取的条件在对数似然函数qqqqqqqqqqqqqqqqq50)()|(ln)()|(ln)|(ln)(),|,(ln)|(ln)(ln)()(11111sHxpHxpxpHNxxpxplHHNkkkNkNkksN 正态分布的极大似然估计正态分布的极大似然估计 从总体中抽取从总体中抽取N个样本个样本 xk，观察下列不同情况：，观察下列不同情况：已知，均值向量已知，均值向量m m未知，即未知，即q q

11、 m m。m m的极大似然估计必须满足方程：的极大似然估计必须满足方程：未知均值的极大似然估计正是样本的算术平均。未知均值的极大似然估计正是样本的算术平均。)()(21exp21)|(1212mmqxxxpTdNkkNkkxNx1111,0)(mm)()|(ln)()(21|)2ln(21)|(ln11mqmmqmkkkTkdkxxpxxxp 一维正态情况，两个参数均未知，设一维正态情况，两个参数均未知，设q q1 1m m，q q2s s 2,q q q q1,1,q q2 T。2122)(212ln21)(lnqqqqkkxxp似然函数22212122)(21)(1)(lnqqqqqqqk

12、kkxxxp两个变量的梯度2)(21exp21)(smsqxxp分布形式NkNkkNkkxx1122212112210)(10)(1qqqqqqq需满足下列条件、求极大似然估计2122112)(11msqmqsmNkkNkkxNxN和方差值解方程，得到一维的均多维正态密度的情况。多维正态密度的情况。计算方法和形式完全类似，只是复杂些，计算结计算方法和形式完全类似，只是复杂些，计算结果：果：均值向量的极大似然估计是样本的均值，而协方均值向量的极大似然估计是样本的均值，而协方差的极大似然估计是差的极大似然估计是N个矩阵个矩阵 的的算术平均。这是一致估计。算术平均。这是一致估计。协方差矩阵的无偏估计

13、为协方差矩阵的无偏估计为Tkkxx)(mmNkTkkxxN1)(11mm维向量。个抽样，是为第其中dkxxxNxNkNkTkkNkk11)(11mmm2.Bayes估计和估计和Bayes学习学习 Bayes估计：根据样本集估计：根据样本集 x 确定总体某个参数确定总体某个参数q q Bayes学习：利用样本集学习：利用样本集 x 确定概率密度函数确定概率密度函数p(x)Bayes估计估计 基本原理：把参数基本原理：把参数q q当作具有某种先验分布当作具有某种先验分布p(q q)的随机变量的随机变量,对样本对样本x观察使先验分布转化为后验观察使先验分布转化为后验分布分布p(q q|x)，据此再修

14、正原先的估计，据此再修正原先的估计 。假设：假设：把所有的样本按类别分成把所有的样本按类别分成c个子集。每个子集有个子集。每个子集有N个样本个样本 x=x1,x2,xN。每类可。每类可单独单独处理。处理。已知样本的分布形式已知样本的分布形式p(x|q q)，而参数，而参数q q 未知。未知。q q为随机变量为随机变量,已知其先验概密函数已知其先验概密函数p(q q)。q贝叶斯估计和最小风险贝叶斯决策可统一：贝叶斯估计和最小风险贝叶斯决策可统一：Bayes估计：有一个样本集估计：有一个样本集x，用来估计所属总，用来估计所属总体分布的某个参数，使带来的贝叶斯风险最小体分布的某个参数，使带来的贝叶斯

15、风险最小。Bayes估计最小风险估计最小风险 R为给定条件下某个估计量的期望损失，常称为给定条件下某个估计量的期望损失，常称为条件风险。使条件风险最小的估计量为条件风险。使条件风险最小的估计量q q，也，也就是贝叶斯估计。就是贝叶斯估计。经推导经推导(P.52定理定理3.1)使用平方误差损失函数时使用平方误差损失函数时，得到估计量为条件期望：，得到估计量为条件期望：2)(),()(),()(qqqqqqqqq损失函数dxpxRdxpxEqqqqq)|()|(Bayes参数估计步骤：参数估计步骤：确定确定q q 的的先验概率密度函数先验概率密度函数p(q q)；由样本集由样本集 x=x1,x2,

16、xN计算样本的联合分计算样本的联合分布布 ，它是，它是 q q 的函数的函数；用用Bayes公式求后验分布公式求后验分布p(q q|x)求样本的估计量求样本的估计量q qNkkxpxp1)|()|(qqqqqqqqdxpxEx)|(|条件下的条件期望：给定是在，贝叶斯估计量损失函数为二次函数时qqqqqqdxpxpxpxpxp)|()|()|()|()|(正态分布情况的正态分布情况的Bayes估计举例估计举例 样本为一维正态分布样本为一维正态分布 p(x|m m)N(m m,s s 2)，m m未知未知 m m是随机是随机的，其先验概密的，其先验概密 p(m m)N(m m0,s s02)N个

17、样本构成样本集个样本构成样本集 x=x1,x2,xN 求求m m的估计量的估计量 解：解：用用Bayes公式求公式求m m的后验分布：的后验分布：mmmmmmmmmmmdpxpapxpadpxppxpxpNkk)()|(/1)()|()()|()()|()|(1a比例因子与无关mmmmqqqqdxpdxp)|()|(根据上述假设：根据上述假设：代入计算代入计算后验概密后验概密 p(|x)p(|x)是是的二次函数的指数函数，仍是正态密度的二次函数的指数函数，仍是正态密度,写成写成),()(),()|(2002smmsmmNpNxpk)1(2)1(21exp)()(21exp)(21exp21)(

18、21exp21)|(200122202,20012,20200122axnaxaxaxpNkkNkkNkk无关项并入与mmsmsmsssmmsmsmmssmsm)(21exp21)|(),()|(22NNNNNxpNxpsmmsmsmm02202220202222022020220222020120022202221exp21)|(),()|(1,11mssssssmmmsmmsmmmmmsmmmsssssmssssssmsmssmsssNmNNddxpNxpNNmNNxNmmNNNNNNNNNNNNNkkNNNNN。为的后验概密由样本集得到解得样本的均值比较后得到 Bayes学习求概率密度函

19、数学习求概率密度函数p(x|X)从联合密度求条件概密函数从联合密度求条件概密函数 X由由N个样本组成，个样本组成，X=x1,xN 用用Bayes公式计算公式计算q q 的的后验分布后验分布 p(q q|X)，根据独立性根据独立性 其中其中 XN=x1,xN1,xN，XN1=x1,xN1 qqqqqqqqqqqqqqqdXpxpXpxpXpXpxpXpdpXppXpXpNNNNNNNN)()()()()()()()()()|()()|()(111qqqqqdXpxpdXxpXxp)|()|()|,()|(已知已知q q 的先验概密的先验概密 p(q q|X0)=p(q q)，根据样本，根据样本序

20、序列列x1,xN按下式反复计算，得到概率密度的按下式反复计算，得到概率密度的序列序列p(q q),p(q q|x1),p(q q|x1,x2 2),，同时修改，同时修改q q，如，如果这个密度序列在估计值果这个密度序列在估计值 附近产生一个陡峰附近产生一个陡峰,即即d d 函数函数,这种性质称为这种性质称为Bayes学习。学习。q)()|()|(),()|(,xpxpxxpxpxpNNqqqqq即也就是真实总体分布而，就是真实参数时当qqqqqqdXpxpXpxpXpNNNNN)()()()()(11 Bayes学习步骤：学习步骤：前三步同前三步同Bayes估计。下面的步骤估计。下面的步骤 读

21、入第一个样本读入第一个样本x1，计算得到得到后验概密，计算得到得到后验概密p(q q|x1),据此作为下一步计算的先验概率密度；据此作为下一步计算的先验概率密度；读入样本读入样本x2，计算得到，计算得到p(q q|x1,x2)；这样得到一个概率密度序列：这样得到一个概率密度序列：这个过程称为参数估计的递归的这个过程称为参数估计的递归的Bayes方法。方法。这个序列收敛于一个这个序列收敛于一个q q0为中心的为中心的d d 函数，则这个函数，则这个性质称性质称 Bayes 学习。大多数密度函数有此性质学习。大多数密度函数有此性质。为已知的先验密度函数第一列)(),|(,),|(),|(),(12

22、11qqqqqpxxpxxpxppN从前例从前例 Bayes学习得到条件概率密度函数学习得到条件概率密度函数 非监督参数估计方法所采用的也是这两种方法非监督参数估计方法所采用的也是这两种方法，但计算较复杂。就极大似然估计来说，由于，但计算较复杂。就极大似然估计来说，由于样本的类别未知，因此定义样本的类别未知，因此定义c类样本组成的混类样本组成的混合密度建立似然函数。合密度建立似然函数。方差修正为通过样本估计均值为方差为为也是正态分布，其均值为，为其中2222122122222121211,),(),|(,),|()(21exp21),|(),(),|(),()|(),|()|(),|(NNNN

23、NNNNNNNNNNNNNNxxxpxxxpxxxxpNxxpNxpdxxpxpxxxpssmssmssmssmsssmmsmmmmm3 总体分布的非参数估计总体分布的非参数估计 根据训练根据训练样本集样本集x=x1,x2,xN ,估计总体分布估计总体分布概率密度函数概率密度函数p(x|x1,x2,xN)形式。形式。基本思想：基本思想：每个样本对总体概率密度每个样本对总体概率密度 分布都有贡献分布都有贡献(如矩形如矩形a)，N个样本的贡献叠加起来，个样本的贡献叠加起来，得到概率密度估计，如虚线。得到概率密度估计，如虚线。也可认为每个样本在自己位也可认为每个样本在自己位 置上贡献增大，离得远贡献

24、置上贡献增大，离得远贡献 小小(如正态分布如正态分布)，同样叠加，同样叠加 得到概率密度估计得到概率密度估计(下图下图)。直方图方法估计一维概率密度函数近似值：直方图方法估计一维概率密度函数近似值：将将x轴划分为长度为轴划分为长度为h的区间，样本的区间，样本x落在某个落在某个区间的概率就是这个区间的估计值。区间的概率就是这个区间的估计值。样本总数为样本总数为N，落在某个区间的点数为，落在某个区间的点数为kN，相，相应的概率近似于频数：应的概率近似于频数：P kN/N 概率密度在同一个区间为常数，近似等于概率密度在同一个区间为常数，近似等于 估计值收敛于真实值的条件：估计值收敛于真实值的条件：h

25、N 0；kN；kN/N0。这三个条件表示对这三个条件表示对N的依赖型。的依赖型。为区间中点。00,2,1)(xhxxNkhxpNNkPPNPNmkRmkNPPPNmmkPkNkNCRxPPPCPPRkNxxxNxpxxpdxxpPRxkmkkNkNkkNkkNR)1(max)1(,)!(!,)1(,)()()(.121的概率最大个落入个样本中根据众数定义，。即称为众数取最大值的知，根据二项分布的性质可的概率落入为服从离散二项分布的概率个样本落入区域个中有，则个样本中独立抽取的从的总体概率密度函数为的概率落入区域基本方法：设样本有关。以及落入其中的样本数的区域体积包含、的估计值。与样本数点概率密

26、度上式就是因此中的点，则是的体积，是区域式中，中近似不变，得到在使足够小，连续，并且区域设为了估计kVxNxpxVNkxpVxpdxxpPNkRxRVVxpdxxpPRxpRxpxpRR)(/)()()()()()()(),(上的一个很好估计。在这是总体密度，RxpNkP)(理论上讲，要使理论上讲，要使 ，就必须使体积，就必须使体积V趋于零，同时趋于零，同时N和和k 趋于无穷大。趋于无穷大。若体积若体积V固定固定,样本取得越来越多样本取得越来越多,则则k/N收敛，收敛，只能得到只能得到p(x)的空间平均估计的空间平均估计 若样本数若样本数N固定，使固定，使R不断缩小，不断缩小，V趋于零，会发趋

27、于零，会发生两种无意义情况：一是区域内不包含任何样本生两种无意义情况：一是区域内不包含任何样本，p(x)=0；二是碰巧有一个样本，；二是碰巧有一个样本，p(x)=。实际上样本是有限的，实际上样本是有限的，V也不能任意缩小。若用也不能任意缩小。若用这种方法估计，频数这种方法估计，频数k/N和估计的和估计的p(x)将存在随将存在随机性，都有一定的方差。机性，都有一定的方差。RRdxdxxpVP)()()(xpxpN收敛于 假设有无限多的样本可利用，在特征空间构造包假设有无限多的样本可利用，在特征空间构造包含含x点的区域序列点的区域序列R1,R2,RN,对对R1用一个样用一个样本进行估计，对本进行估

28、计，对R2用二个样本，用二个样本，。设落在。设落在RN的的 x点数为点数为kN，则第，则第N次估计的概率密度函数为次估计的概率密度函数为 要使要使 NNNVNkxp/)(收敛，这是必要条件。忽略不计。要使比仍可，但与内落入大量样本尽管。收敛于可使频数比的点对。收敛于可使空间平均区域平滑缩小)(,0lim,0)(,lim)(,0limxpNkRNkPNkxpkxpVPVNNNNNNNNNN的三个条件：收敛于)()(xpxpN 满足这三个条件的区域序列通常有两种方法：满足这三个条件的区域序列通常有两种方法：Parzen窗法窗法：把包含把包含x点的区域序列点的区域序列VN选为样本数目选为样本数目N的

29、函数的函数，并使其空间体积，并使其空间体积VN随随N的增大而减小，例如的增大而减小，例如 VN=N-1/2。但对但对kN和和kN/N都要加些限制条件以使估都要加些限制条件以使估计值收敛于计值收敛于p(x)。kN近邻法近邻法：把把KN选为样本数目的函数。选为样本数目的函数。让让kN为为N的某个函数的某个函数(例如例如kN=N1/2)，并调整体积，并调整体积VN大小，使区域正好包含大小，使区域正好包含x的的kN个个近邻，则该区近邻，则该区域体积可用作域体积可用作x点的密度估计点的密度估计。2.Parzen窗法窗法 窗估计的概念窗估计的概念 多维情况下，围绕多维情况下，围绕x点的区域点的区域RN为一

30、个超立方体为一个超立方体，边长为，边长为hN,d为特征空间维数。为特征空间维数。训练样本训练样本xi是否落入这个超立方体内，检查是否落入这个超立方体内，检查x-xi的每个分量值，若小于的每个分量值，若小于hN/2，则在，则在RN内，其中内，其中x为数轴为数轴(特征空间坐标轴特征空间坐标轴)上的点。上的点。为了用函数描述落入为了用函数描述落入VN 中训练样本的数目中训练样本的数目kN，定义窗函数定义窗函数 对对u的特征空间来说，的特征空间来说，f f(u)是围绕原点的是围绕原点的1个单个单位位超立方体超立方体。dNNhV其他，当，,0,2,12/1|1)(djuujf 若若u=(x-xi)/hN

31、，则窗函数则窗函数 当某个样本当某个样本xi落入以落入以x为中心、体积为为中心、体积为VN的立方体的立方体内时计为内时计为1，否则为，否则为0。落入落入VN内的样本数：内的样本数：x点的密度估计点的密度估计 Parzen窗的密度估计窗的密度估计 NiNiNNhxxVNxp111)(f其他当，,0,121|)(|1djhxxhxxNjiNifNNNVNkxp/)(NiNiNhxxk1f在以x为中心的立方体内的样本应相加 用用方窗方窗的直观解释一维概率密度函数的估计：的直观解释一维概率密度函数的估计：样本集样本集xx1,x2,x5有五个样本。有五个样本。每个每个样本样本xi在以在以 xxi为中心，

32、宽为为中心，宽为h的范围内对的范围内对概率密度函数贡献为概率密度函数贡献为1，数轴数轴x上任一点的概密函上任一点的概密函数是样本集中全部样本对概密函数之和。数是样本集中全部样本对概密函数之和。对所有的点求和，得到对所有的点求和，得到p(x)的分布虚线所示。的分布虚线所示。如果样本数很多，并选择适当的窗函数，估计的如果样本数很多，并选择适当的窗函数，估计的概率密度函数的性质有可能接近真实的概率密度概率密度函数的性质有可能接近真实的概率密度函数函数p(x)。估计量估计量 为密度函数的条件为密度函数的条件 为使为使 是一个估计合理的概率密度函数，必是一个估计合理的概率密度函数，必须满足对概率密度函数

33、的基本要求，即它应该非须满足对概率密度函数的基本要求，即它应该非负且在特征空间积分为负且在特征空间积分为1。为此窗函数须满足两个条件：为此窗函数须满足两个条件：)(xpN。概率的估计的密度函数利用第二个条件可证明非负。限制条件下，保证在第一个数的形式窗函数本身具有密度函即积分为非负1)()()(11)(0)(xpPxpxpduuuNNff)(xpN 窗函数的选择：窗函数的选择：方窗函数方窗函数 正态窗函数正态窗函数 指数窗函数指数窗函数 只要所选择的函数满足前述的两个条件式，都只要所选择的函数满足前述的两个条件式，都可作为窗函数。可作为窗函数。221exp21)(uuf|)|exp(21)(u

34、uf02/1|,1)(uuf估计量的统计性质估计量的统计性质NVNVVuuuduuuxxpxpNNNNNdiiuuN/1,lim0lim0)(lim)(sup1)(0)()()(1缩减的速率要低于窗宽受下列条件约束；窗函数满足下列条件点连续；在限制条件：和平方误差一致性。是渐近无偏性计量在一些限制条件下，估ffff 产生随机变量的补充材料（共四页，三个问题）产生随机变量的补充材料（共四页，三个问题）产生产生 0,1之间均匀分布的随机数之间均匀分布的随机数ui方法方法为正整数为计算机字长的位数，参数选择：例：。之间均匀分布的随机数量之间均匀分布的随机变为种子。为模数为增量为乘子其中：个随机数是第

35、kzkacpmuzuzuzzcammzummzzmcaizmcazzpiiiiii,14,122438.016/7,716mod)345(063.016/1,116mod)365(375.016/6,616mod)375(7,3,5,16 1,0/1,010,)(mod(016162211001mm 产生产生随机变量随机变量方法方法(非非0,1均匀分布的随机数均匀分布的随机数)基本方法反变换法基本方法反变换法 以概率积分变换定理为基础的一种常用的抽样方以概率积分变换定理为基础的一种常用的抽样方法。法。其基础是其基础是0,1之间均匀分布的随机数。之间均匀分布的随机数。若若随机变量随机变量x的的分

36、布函数为分布函数为F(x)，其反函数，其反函数F-1。可用可用0,1之间均匀分布的随机数来产生要求分布之间均匀分布的随机数来产生要求分布的随机变量。的随机变量。具体方法具体方法 U为为0,1均匀分布随机数均匀分布随机数 令令 U=F(x)x=F-1(U)x即为所要求分布的随机变量。即为所要求分布的随机变量。变量区间上均匀分布的随机即为则有，令随机数使用的分布函数可得到由其他其概率密度函数为变量区间上均匀分布的随机例：产生,)()()()1,0()(1)()(,0,1)(,0baxuabaxbxabxaxxFuuUbxabxaxdtabxFxxfbxaabxfbaxx产生一维正态分布随机变量的近

37、似方法产生一维正态分布随机变量的近似方法xyNuxnnunnnuUxxNNuuunnnxxxniiniiniixxnxxnxxsmsmsmsmsmsm则分布，若要若取的随机变量分布，可得到服从标准正态当。其均匀分布的随机数个的近似正态分布。和方差为之和，服从均值为量的独立同分布的随机变，方差为个均值为概率中心极限定理：),(612212122)1,0(12/1,2/1,1,0,121112212212举例举例 根据已知概率密度函数根据已知概率密度函数p(x)产生一系列随机变量，产生一系列随机变量，作为样本。用作为样本。用正态窗函数正态窗函数估计样本的总体分布，估计样本的总体分布，并与真实的概率

38、密度函数作比较。并与真实的概率密度函数作比较。采用下列两种样本：采用下列两种样本：p(x)是均值为是均值为0方差为方差为1的正态分布，生成样本的正态分布，生成样本xi p(x)是两个均匀分布的是两个均匀分布的混合密度生成样本混合密度生成样本xi02025.025.21)(xxxp其他 统计落入正态窗的随机样本数，计算统计落入正态窗的随机样本数，计算p(x)的估计的估计值，在计算中要注意公式中值，在计算中要注意公式中变量和参数的意义变量和参数的意义。这种方法具有普遍性，即不管是规则或不规则、这种方法具有普遍性，即不管是规则或不规则、单峰或多峰分布都可用，但需要的样本数量很大单峰或多峰分布都可用，

39、但需要的样本数量很大。需要一定的经验。很敏感的选择对估计量对有限时，选择问题。在窗估计中有个体积系列为可调整的参数，概率密度函数使用正态窗,)(4,1,4111)(21exp21)(111112xphNhhNhhhxxhNxpuuNNiNiNNff从图中从图中可看出可看出N256，h11时，时，接近真实接近真实分布，而分布，而h14时，时，噪声小。噪声小。当样本数当样本数很多时，很多时，h1影响不影响不大。大。均值为0方差为1的正态分布二个均匀分布的混合密度 基本步骤：基本步骤：产生训练集样本，有两种方法：产生训练集样本，有两种方法：在问题域中搜集样在问题域中搜集样本；本；根据题意按已知的概率

40、密度产生随机样本。根据题意按已知的概率密度产生随机样本。设设x为为d维的数轴，以体积维的数轴，以体积 在数轴上向前推进，在数轴上向前推进，即即N=1,2,3,，这样就可统计落入各体积的样本数，这样就可统计落入各体积的样本数KN。选择窗函数选择窗函数f f(u)，利用概率密度函数公式进行统计，利用概率密度函数公式进行统计 计算数轴上各点的密度。计算数轴上各点的密度。对所有的点求和，用图形表示概率密度曲面对所有的点求和，用图形表示概率密度曲面(一维为曲一维为曲线线)。如果自行按某种概率密度产生的随机数，则可将计算如果自行按某种概率密度产生的随机数，则可将计算得到的曲面得到的曲面(线线)与其进行比较

41、，以验证与其进行比较，以验证Parzen窗法的窗法的正确性。正确性。dNNhVNiNiNNhxxVNxp111)(f3.kN近邻法近邻法 Parzen 窗存在问题：体积窗存在问题：体积V的选择的选择 V1的选择很敏感，太小大部分是空的噪声大；的选择很敏感，太小大部分是空的噪声大；太大估计值平坦，不能反映总体分布变化。太大估计值平坦，不能反映总体分布变化。kN近邻法：体积不是样本的函数，而是近邻法：体积不是样本的函数，而是kN的函的函数。先确定数。先确定kN，然后以，然后以x点为中心，让体积不断点为中心，让体积不断扩大，直到捕获到扩大，直到捕获到kN个样本为止，这些样本称个样本为止，这些样本称为

42、为x的的kN个近邻。如果点个近邻。如果点x附近密度愈高附近密度愈高,则体积则体积愈小愈小,分辨率高，反之体积愈大。分辨率高，反之体积愈大。kN近邻估计公式：近邻估计公式：NNNVNkxp/)(NVVN/1估计的估计的pN(x)收敛于真实概率密度收敛于真实概率密度p(x)的充分必的充分必要条件：要条件：kN 可取为可取为N的某个函数，如的某个函数，如 k1 0 选择选择k1，使，使kN 1。这种方法同样要求样本数量要大。一维要几百这种方法同样要求样本数量要大。一维要几百个样本；二维要几千个样本。个样本；二维要几千个样本。不为样本的体积获的增长不要太快，使捕可限制的概率。估计落入这样可较好地用00

43、/lim/lim0limNNNNNNNNNNkkNkVNkkV，NkkN1例：条件同上例，用例：条件同上例，用kN近邻法。近邻法。p(x)是均值为是均值为0方差为方差为1的正态的正态分布，生成样本分布，生成样本xi p(x)是二个均匀分布的混合密是二个均匀分布的混合密度生成样本度生成样本xi 设设 N=1,16,256,；kN=1,4,16,估计结果为左图所示。估计结果为左图所示。计算步骤与计算步骤与Parzen窗法类似。窗法类似。02025.025.21)(xxxp其他NNNVNkxp/)(估计公式4 近邻法近邻法 kN近邻法是利用样本进行概率密度函数的估计。近邻法是利用样本进行概率密度函数

44、的估计。现在讨论的是现在讨论的是直接利用样本，直接利用样本，根据根据距离距离分类。分类。近邻法：近邻法：在设计阶段已根据训练集样本在特征空间划分了在设计阶段已根据训练集样本在特征空间划分了边界。计算待识别样本点边界。计算待识别样本点x到周围近邻的距离，到周围近邻的距离，将将x归入最近邻中样本所属的那个类。归入最近邻中样本所属的那个类。最近邻法最近邻法 k-近邻法近邻法 此法属非参数法此法属非参数法(无需估计概率密度无需估计概率密度)有近邻法有近邻法，线性判别函数和聚类，线性判别函数和聚类(非监督学习法非监督学习法)。两种近邻法1.最近邻法最近邻法 决策规则决策规则 设有设有c个类别个类别 ，每

45、类有标明类别的，每类有标明类别的Ni个样本，个样本，i=1,2,c。w wi类的判别函数和决策规则：类的判别函数和决策规则：比较未知样本比较未知样本x与与 个已知类别样本个已知类别样本xik 间间的的欧氏距离欧氏距离，将，将 x 归入离它最近的那个样本类归入离它最近的那个样本类。()cixxxxxxxxijdjjiTii,2,1)()()(|212121欧氏距离：jiijxcixgxgw则决策若决策规则：,2,1),(min)(为待分类的样本是样本的类别，其中判别函数：xiNkxxxgikiki,2,1,|min)(ciiNN1cwww,21最近邻法错误率的分析最近邻法错误率的分析 训练集样本

46、数有限，有时多一个或少一个对分训练集样本数有限，有时多一个或少一个对分类结果影响较大。类结果影响较大。例如图中有例如图中有 A类和类和 B类，类，O 代表待分样本代表待分样本,用欧氏距离测量，用欧氏距离测量，O的近邻为的近邻为A3，分在，分在A类；类；若将若将A3拿开，拿开，O就分在就分在B类。类。说明最近邻法错误率有偶然性。样本越多偶然说明最近邻法错误率有偶然性。样本越多偶然性减少。性减少。因此用训练样本数增到因此用训练样本数增到 极大来评价性能，用到极大来评价性能，用到 渐近概念分析渐近概念分析错误率。错误率。设设N个样本下的平均错误概率为个样本下的平均错误概率为PN(e)，且样本，且样本

47、x的最近邻为的最近邻为x，则，则 可证明下述关系可证明下述关系 根据第二章，贝叶斯错误率根据第二章，贝叶斯错误率P*)(lim)()()|(),|()(ePPePNPdxxpdxxxpxxePePNNNNN的极限时为当定义渐近平均错误率为类数。为贝叶斯错误率，其中cPPccPPP12dxxpxPdxxpxePPm)()|(1)()|(w 最近邻法渐近平均错误率最近邻法渐近平均错误率P的范围的范围(上下界上下界)：PccPPPPccPdxxpxPPPPcccPcicxPPPPxPPPdxxpxPdxxpxePePPciiimciiNNNN1212)()|(1,111),2,1(/1)|(,01)

48、|()()|(1)()|(lim)(lim1212所以上界可以证明息情况。密度函数相等，即无信相当于各类的条件概率，时，各类后验概率相等，当时，当特定情况下，存在下界wwww 根据最近邻法错误率的公式根据最近邻法错误率的公式 图中标明最近邻法错误率的上下界。图中标明最近邻法错误率的上下界。Bayes错误率在错误率在0和和(c-1)/c 之间。之间。当当Bayes错误率较小时，错误率较小时，最近邻法的错误率最大为最近邻法的错误率最大为Bayes两倍。两倍。一般情况下，近邻法错误率在阴影区域中。一般情况下，近邻法错误率在阴影区域中。近邻法是一种次优法，它的错误率比近邻法是一种次优法，它的错误率比B

49、ayes决决策大。当样本数目无限大时，它的错误率策大。当样本数目无限大时，它的错误率P不不会超过会超过Bayes错误率错误率P*的的2倍。倍。)12(PccPPPP=2P*P=P*2.k-近邻法，最近邻法的改进近邻法，最近邻法的改进 在待分样本在待分样本x的的k个近邻中，按个近邻中，按出现最多的样本出现最多的样本类别来作为类别来作为x的类别的类别，即在，即在x的近邻中一一找出的近邻中一一找出它们的类别进行判别。它们的类别进行判别。方法：首先规定方法：首先规定k的大小，找出待分样本的大小，找出待分样本x的的k个个近邻，看这近邻，看这k个近邻中多数属于哪一类，就将个近邻中多数属于哪一类，就将x归为

50、这一类。归为这一类。x附近的附近的n个样本中来自个样本中来自w w1类的有类的有n1个，设近邻个，设近邻 有有k1；来自；来自w w2类的有类的有n2个个,近邻有近邻有k2个；个；来自来自w wc 类的有类的有nc个个,近邻有近邻有kc个。个。判别函数：判别函数：gi(x)ki,i=1,2,c 决策规则：决策规则：jicijxkxgw则决策若,.,2,1max)(例图中设定例图中设定k=5,用欧氏距离度量用欧氏距离度量X到这三类的到这三类的距离得到：距离得到：k1=4,k2=1,k3=0。根据判别规则根据判别规则X为为w w1 1类。类。最近邻法是最近邻法是k近邻法的特例，近邻法的特例，k=1