概率密度估计及近邻法

1、第三章概率密度函数估计及近邻法Estimation of Probability Density Function and The Nearest Neighbor Rule1 引言2 总体分布的参数估计 极大似然估计 贝叶斯估计参数3 总体分布的非参数估计 Parzen窗法 kN近邻法4 近邻法则 1 引言 基于样本的两步贝叶斯决策： 估计类条件概率密度 和先验概率 ； 利用 和 完成分类器设计。(第二章) 本章讨论从样本集推断总体概率分布p(x|wi) 。而样本的先验概率P(wi)的估计较易实现。 概率密度函数含参数和形式两方面内容，分别称为参数估计和非参数估计。其估计方法：1. 监督参数

2、估计 已知样本类别wi及其p(x|wi)形式，而参数未知，需从训练样本x估计参数q q，如一元正态分布的m、s 2等参数。)( ixpw)(iPw)( ixpw)(iPw2. 非监督参数估计 未知样本类别wi ，已知概率密度函数p(x|wi)的形式，但参数未知，需从样本x估计参数。 上述两种均可用极(最)大似然法和Bayes估计法来估计参数。3. 非参数估计即估计p(x|wi)形式 已知样本类别，但未知概率密度函数的形式，要从样本推断p(x|wi)属于哪种分布。 可用Parzen窗法和kN近邻法。4. 近邻法则不属于估计内容 直接利用样本设计分类器。非参数(即分类中不需要估计概率密度函数) 方

3、法之一。5. 参数估计的几个基本术语统计量：每个训练样本都包含总体信息。根据从总体中抽取的样本集构造某种函数, 该函数统计学中称为统计量。参数空间：概率密度形式已知，参数q q 未知, q q 可取值的集合称为参数空间，记为。点估计、估计量和估计值：构造一个统计量f(x1,xn) 作为参数q 的估计量 。如果x1,xn属于某类，代入统计量f，就可得到该类具体的估计值。本章参数估计属于点估计。区间估计要求用区间(d1, d2)作为q 可能取值范围的一种估计。该区间称为置信区间。q2 总体分布的参数估计1. 极(最)大似然估计 基本原理 把参数q q 看成确定的(非随机) 但取值未知，最好估计值是

4、在样本x概率为最大条件下得到的。 假设： 按类别把样本集分成c个子集 x1, x2,xc，其中xj中的样本是从概率密度为p(x|wj)的总体中独立抽取的。 p(x|wj)形式已知, 参数q qj未知, 可写成p(x|wj,q qj)。 不同类的参数独立，即xi不包含q qj信息(ij)这样每一类可单独处理，共处理c个独立问题。 设某类有N个样本组成了样本集 xx1,x2,xN 样本是独立从该类抽取的，因此N个随机变量的联合概率密度 统计学中称p(x|q)为相对于样本集x的q 的似然函数l(q q ) 似然函数l(q q) 给出了从总体中抽取的x1,x2,xN这N个样本的概率。 极大似然估计值定

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

6、正态分qqqqqmqmsmq,)|(,)|()|(,),()|(616212xpCBAxpxpxxxxxNxpkk 假设似然函数p(x|q q) 对未知参数q q 是连续可微的，则 可由典型的求极值的方法求得。 求极大值的必要条件 单个q q 的情况下： 若q q 是向量，有s个分量q q =q1,qs T，则多变量的梯度算子 对数似然函数H(q q)是单调的增函数，为计算方便，一般用对数似然函数。sqqq10)(qqddlq 使似然函数最大。只有个解，解，如图中有有时上式可能没有唯一。，就是极大似然估计值得到的解个方程的从而下个样本独立抽取的条件在对数似然函数qqqqqqqqqqqqqqqq

7、q50)()|(ln)()|(ln)|(ln)(),|,(ln)|(ln)(ln)()(11111sHxpHxpxpHNxxpxplHHNkkkNkNkksN 正态分布的极大似然估计 从总体中抽取N个样本 xk，观察下列不同情况：已知，均值向量m m未知，即q q m m。 m的极大似然估计必须满足方程： 未知均值的极大似然估计正是样本的算术平均。)()(21exp21)|(1212mmqxxxpTdNkkNkkxNx1111, 0) (mm)()|(ln)()(21|)2ln(21)|(ln11mqmmqmkkkTkdkxxpxxxp 一维正态情况，两个参数均未知，设q1m，q2s 2 ,

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

9、x) )(mmNkTkkxxN1) )(11mm维向量。个抽样，是为第其中dkxxxNxNkNkTkkNkk11)(11mmm2. Bayes估计和Bayes学习 Bayes估计：根据样本集 x 确定总体某个参数q Bayes学习：利用样本集 x 确定概率密度函数p(x)Bayes估计 基本原理：把参数q当作具有某种先验分布p(q) 的随机变量, 对样本x观察使先验分布转化为后验分布p(q|x)，据此再修正原先的估计 。假设： 把所有的样本按类别分成c个子集。每个子集有N个样本 x = x1,x2,xN。每类可单独处理。 已知样本的分布形式p(x|q q) ，而参数q q 未知。 q为随机变量

10、, 已知其先验概密函数p(q) 。q贝叶斯估计和最小风险贝叶斯决策可统一： Bayes估计：有一个样本集x，用来估计所属总体分布的某个参数，使带来的贝叶斯风险最小。 Bayes估计最小风险 R为给定条件下某个估计量的期望损失，常称为条件风险。使条件风险最小的估计量q q，也就是贝叶斯估计。 经推导(P.52定理3.1)使用平方误差损失函数时，得到估计量为条件期望：2)(),()(),()(qqqqqqqqq损失函数dxpxRdxpxEqqqqq)|()|( Bayes参数估计步骤： 确定q 的先验概率密度函数p(q)； 由样本集 x = x1,x2,xN计算样本的联合分布 ，它是 q 的函数

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

12、()|(1a比例因子与无关mmmmqqqqdxpdxp)|()|( 根据上述假设： 代入计算后验概密 p(|x) p(|x)是的二次函数的指数函数，仍是正态密度, 写成),()(),()|(2002smmsmmNpNxpk)1(2)1(21exp)()(21exp)(21exp21)(21exp21)|(200122202, ,20012,20200122axnaxaxaxpNkkNkkNkk无关项并入与mmsmsmsssmmsmsmmssmsm)(21exp21)|(),()|(22NNNNNxpNxpsmmsmsmm0220222020222202202022022202012002220

13、2221exp21)|(),()|(1,11mssssssmmmsmmsmmmmmsmmmsssssmssssssmsmssmsssNmNNddxpNxpNNmNNxNmmNNNNNNNNNNNNNkkNNNNN。为的后验概密由样本集得到解得样本的均值比较后得到 Bayes学习求概率密度函数p(x| X) 从联合密度求条件概密函数 X由N个样本组成，X=x1,xN 用Bayes公式计算q 的后验分布 p(q|X)， 根据独立性 其中 XN=x1, xN1,xN， XN1=x1,xN1 qqqqqqqqqqqqqqqdXpxpXpxpXpXpxpXpdpXppXpXpNNNNNNNN)()()(

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

15、面的步骤 读入第一个样本x1，计算得到得到后验概密p(q|x1), 据此作为下一步计算的先验概率密度； 读入样本x2，计算得到p(q|x1,x2) ； ； 这样得到一个概率密度序列： 这个过程称为参数估计的递归的Bayes方法。 这个序列收敛于一个q q0为中心的d 函数，则这个性质称 Bayes 学习。大多数密度函数有此性质。为已知的先验密度函数第一列)(),|(,),|(),|(),(1211qqqqqpxxpxxpxppN从前例 Bayes学习得到条件概率密度函数 非监督参数估计方法所采用的也是这两种方法，但计算较复杂。就极大似然估计来说，由于样本的类别未知，因此定义c类样本组成的混合密

16、度建立似然函数。方差修正为通过样本估计均值为方差为为也是正态分布，其均值为，为其中2222122122222121211,),(),|(,),|()(21exp21),|(),(),|(),()|(),|()|(),|(NNNNNNNNNNNNNNNNNNxxxpxxxpxxxxpNxxpNxpdxxpxpxxxpssmssmssmssmsssmmsmmmmm3 总体分布的非参数估计 根据训练样本集x=x1, x2, xN , 估计总体分布概率密度函数p(x|x1, x2, xN)形式。 基本思想： 每个样本对总体概率密度 分布都有贡献 (如矩形a)， N个样本的贡献叠加起来， 得到概率密度估

17、计，如虚线。 也可认为每个样本在自己位 置上贡献增大，离得远贡献 小(如正态分布)，同样叠加 得到概率密度估计(下图)。直方图方法估计一维概率密度函数近似值： 将x轴划分为长度为h的区间，样本x落在某个区间的概率就是这个区间的估计值。 样本总数为N，落在某个区间的点数为kN，相应的概率近似于频数： P kN /N 概率密度在同一个区间为常数，近似等于 估计值收敛于真实值的条件： hN 0； kN ； kN /N0。 这三个条件表示对N的依赖型。为区间中点。00,2,1)( xhxxNkhxpNNkPPNPNmkRmkNPPPNmmkPkNkNCRxPPPCPPRkNxxxNxpxxpdxxpP

18、RxkmkkNkNkkNkkNR) 1(max) 1(,)!( !,)1 (,)()()(. 121的概率最大个落入个样本中根据众数定义，。即称为众数取最大值的知，根据二项分布的性质可的概率落入为服从离散二项分布的概率个样本落入区域个中有，则个样本中独立抽取的从的总体概率密度函数为的概率落入区域基本方法：设样本有关。以及落入其中的样本数的区域体积包含、的估计值。与样本数点概率密度上式就是因此中的点，则是的体积，是区域式中，中近似不变，得到在使足够小，连续，并且区域设为了估计kVxNxpxVNkxpVxpdxxpPNkRxRVVxpdxxpPRxpRxpxpRR)(/)( )( )( )()()

19、()(),( 上的一个很好估计。在这是总体密度，RxpNkP)( 理论上讲，要使 ，就必须使体积V趋于零，同时N和k 趋于无穷大。 若体积V固定, 样本取得越来越多, 则k/N收敛，只能得到p(x)的空间平均估计 若样本数N固定，使R不断缩小，V趋于零，会发生两种无意义情况：一是区域内不包含任何样本，p(x)=0；二是碰巧有一个样本，p(x) = 。 实际上样本是有限的，V也不能任意缩小。若用这种方法估计，频数k/N和估计的p(x)将存在随机性，都有一定的方差。RRdxdxxpVP)( )()(xpxpN收敛于 假设有无限多的样本可利用，在特征空间构造包含x点的区域序列R1, R2, RN,

20、对R1用一个样本进行估计，对R2用二个样本，。设落在RN的 x点数为kN，则第N次估计的概率密度函数为 要使 NNNVNkxp/)(收敛，这是必要条件。忽略不计。要使比仍可，但与内落入大量样本尽管。收敛于可使频数比的点对。收敛于可使空间平均区域平滑缩小)(, 0lim,0)(,lim)(, 0limxpNkRNkPNkxpkxpVPVNNNNNNNNNN的三个条件：收敛于)()(xpxpN 满足这三个条件的区域序列通常有两种方法： Parzen窗法： 把包含x点的区域序列VN选为样本数目N的函数，并使其空间体积VN随N的增大而减小，例如 VN =N-1/2 。 但对kN和kN /N都要加些限制

21、条件以使估计值收敛于p(x) 。 kN近邻法： 把KN选为样本数目的函数。 让kN为N的某个函数 (例如kN =N1/2) ，并调整体积VN大小，使区域正好包含x的kN个近邻，则该区域体积可用作x点的密度估计。2. Parzen窗法 窗估计的概念 多维情况下，围绕x点的区域RN为一个超立方体， ，边长为hN, d为特征空间维数。 训练样本xi是否落入这个超立方体内，检查x-xi的每个分量值，若小于hN/2，则在RN内，其中x为数轴(特征空间坐标轴)上的点。 为了用函数描述落入VN 中训练样本的数目kN，定义窗函数 对u的特征空间来说，f(u)是围绕原点的1个单位超立方体。dNNhV其他，当，,

22、 0,2 , 12/1|1)(djuujf 若u=(x-xi)/hN，则窗函数 当某个样本xi落入以x为中心、体积为VN的立方体内时计为1，否则为0。 落入VN内的样本数： x点的密度估计 Parzen窗的密度估计 NiNiNNhxxVNxp111)(f其他当，, 0, 121| )( |1djhxxhxxNjiNifNNNVNkxp/)(NiNiNhxxk1f在以x为中心的立方体内的样本应相加 用方窗的直观解释一维概率密度函数的估计： 样本集xx1,x2,x5有五个样本。 每个样本xi在以 xxi为中心，宽为h的范围内对概率密度函数贡献为1，数轴x上任一点的概密函数是样本集中全部样本对概密函

23、数之和。 对所有的点求和，得到p(x)的分布虚线所示。 如果样本数很多，并选择适当的窗函数，估计的概率密度函数的性质有可能接近真实的概率密度函数p(x)。估计量 为密度函数的条件 为使 是一个估计合理的概率密度函数，必须满足对概率密度函数的基本要求，即它应该非负且在特征空间积分为1。 为此窗函数须满足两个条件： )(xpN。概率的估计的密度函数利用第二个条件可证明非负。限制条件下，保证在第一个数的形式窗函数本身具有密度函即积分为非负1)()()( 11)(0)(xpPxpxpduuuNNff)(xpN 窗函数的选择： 方窗函数 正态窗函数 指数窗函数 只要所选择的函数满足前述的两个条件式，都可

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

25、zuzzcammzummzzmcaizmcazzpiiiiii, 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的分布函数为F(x)，其反函数F -1。可用0,1之间均匀分布的随机数来产生要求分布的随机变量。 具体方法 U为0,1均匀分布随机

26、数 令 U=F(x) x = F-1(U) x即为所要求分布的随机变量。变量区间上均匀分布的随机即为则有，令随机数使用的分布函数可得到由其他其概率密度函数为变量区间上均匀分布的随机例：产生,)()()() 1 , 0()(1)()(,0,1)(,0baxuabaxbxabxaxxFuuUbxabxaxdtabxFxxfbxaabxfbaxx产生一维正态分布随机变量的近似方法xyNuxnnunnnuUxxNNuuunnnxxxniiniiniixxnxxnxxsmsmsmsmsmsm则分布，若要若取的随机变量分布，可得到服从标准正态当。其均匀分布的随机数个的近似正态分布。和方差为之和，服从均值为

27、量的独立同分布的随机变，方差为个均值为概率中心极限定理：),(612212122) 1 , 0(12/1, 2/1, 1 , 0,121112212212举例 根据已知概率密度函数p(x)产生一系列随机变量，作为样本。用正态窗函数估计样本的总体分布，并与真实的概率密度函数作比较。 采用下列两种样本： p(x)是均值为0方差为1的正态分布，生成样本xi p(x)是两个均匀分布的混合密度生成样本xi02025. 025 . 21)(xxxp其他 统计落入正态窗的随机样本数，计算p(x)的估计值，在计算中要注意公式中变量和参数的意义。 这种方法具有普遍性，即不管是规则或不规则、单峰或多峰分布都可用，

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

29、选择窗函数f(u)，利用概率密度函数公式进行统计 计算数轴上各点的密度。对所有的点求和，用图形表示概率密度曲面(一维为曲线)。 如果自行按某种概率密度产生的随机数，则可将计算得到的曲面(线)与其进行比较，以验证Parzen窗法的正确性。dNNhVNiNiNNhxxVNxp111)(f3. kN近邻法 Parzen 窗存在问题：体积V的选择 V1的选择很敏感，太小大部分是空的噪声大；太大估计值平坦，不能反映总体分布变化。kN近邻法：体积不是样本的函数，而是kN的函数。先确定kN，然后以x点为中心，让体积不断扩大，直到捕获到kN个样本为止，这些样本称为x的kN个近邻。如果点x附近密度愈高, 则体积

30、愈小, 分辨率高，反之体积愈大。 kN近邻估计公式： NNNVNkxp/)(NVVN/1估计的pN (x)收敛于真实概率密度p(x)的充分必要条件： kN 可取为N的某个函数，如 k1 0 选择k1，使kN 1。 这种方法同样要求样本数量要大。一维要几百个样本；二维要几千个样本。不为样本的体积获的增长不要太快，使捕可限制的概率。估计落入这样可较好地用00/lim/lim0limNNNNNNNNNNkkNkVNkkV，NkkN1例：条件同上例，用kN近邻法。 p(x)是均值为0方差为1的正态分布，生成样本xi p(x)是二个均匀分布的混合密度生成样本xi 设 N=1,16,256, ；kN =1

31、,4,16, 估计结果为左图所示。 计算步骤与Parzen窗法类似。 02025. 025 . 21)(xxxp其他NNNVNkxp/)(估计公式4 近邻法 kN近邻法是利用样本进行概率密度函数的估计。 现在讨论的是直接利用样本，根据距离分类。 近邻法： 在设计阶段已根据训练集样本在特征空间划分了边界。计算待识别样本点x到周围近邻的距离， 将x归入最近邻中样本所属的那个类。 最近邻法 k-近邻法 此法属非参数法(无需估计概率密度)有近邻法，线性判别函数和聚类(非监督学习法)。 两种近邻法1.最近邻法 决策规则 设有c个类别 ，每类有标明类别的Ni个样本，i =1, 2 , c。 wi类的判别函

32、数和决策规则： 比较未知样本x与 个已知类别样本xik 间的欧氏距离，将 x 归入离它最近的那个样本类。()cixxxxxxxxijdjjiTii, 2 , 1)()()(|212121欧氏距离：jiijxcixgxgw则决策若决策规则：, 2 , 1),(min)(为待分类的样本是样本的类别，其中判别函数：xiNkxxxgikiki, 2 , 1,|min)(ciiNN1cwww,21最近邻法错误率的分析 训练集样本数有限，有时多一个或少一个对分类结果影响较大。 例如图中有 A类和 B类， O 代表待分样本,用欧氏距离测量，O的近邻为A3，分在A类；若将A3拿开，O就分在B类。 说明最近邻法

33、错误率有偶然性。样本越多偶然性减少。 因此用训练样本数增到 极大来评价性能，用到 渐近概念分析错误率。 设N个样本下的平均错误概率为PN(e)，且样本x的最近邻为x ，则 可证明下述关系 根据第二章，贝叶斯错误率P*)(lim)()()| () ,|()(ePPePNPdxxpdxxxpxxePePNNNNN的极限时为当定义渐近平均错误率为类数。为贝叶斯错误率，其中cPPccPPP12dxxpxPdxxpxePPm)()|(1 )()|(w 最近邻法渐近平均错误率P的范围(上下界) ：PccPPPPccPdxxpxPPPPcccPcicxPPPPxPPPdxxpxPdxxpxePePPciii

34、mciiNNNN1212)( )|(1 ,111), 2 , 1(/1)|(, 01)|()( )|(1 )()|(lim)(lim1212所以上界可以证明息情况。密度函数相等，即无信相当于各类的条件概率，时，各类后验概率相等，当时，当特定情况下，存在下界wwww 根据最近邻法错误率的公式 图中标明最近邻法错误率的上下界。 Bayes错误率在0和(c-1)/c 之间。 当Bayes错误率较小时， 最近邻法的错误率最大为Bayes两倍。 一般情况下，近邻法错误率在阴影区域中。 近邻法是一种次优法，它的错误率比Bayes决策大。当样本数目无限大时，它的错误率P不会超过Bayes错误率P*的2倍。)12(PccPPPP=2P*P=P*2. k-近邻法，最近邻法的改进 在待分样本x的k个近邻中，按出现最多的样本类别来作为x的类别，即在x的近邻中一一找出它们的类别进行判别。方法：首先规定k的大小，找出待分样本x的k个近邻，看这k个近邻中多数属于哪一类，就将x归为这一类。 x附近的n个样本中来自w1类的有n1个，设近邻 有k1 ；来自w2类的有n2个, 近邻有k2个； ；来自wc 类的有nc个, 近邻有kc个。 判别函数： gi(x) ki, i = 1,2,c 决策规则：jicijxkxgw则决策若,