概率密度估计及近邻法

1、第三章概率密度函数估计及近邻法estimation of probability density function and the nearest neighbor rule,1 引言 2 总体分布的参数估计 极大似然估计 贝叶斯估计参数 3 总体分布的非参数估计 parzen窗法 kn近邻法 4 近邻法则,1 引言,基于样本的两步贝叶斯决策： 估计类条件概率密度 和先验概率 ； 利用 和 完成分类器设计。(第二章) 本章讨论从样本集推断总体概率分布p(x|wi) 。而样本的先验概率p(wi)的估计较易实现。 概率密度函数含参数和形式两方面内容，分别称为参数估计和非参数估计。其估计方法： 1.

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

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

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

5、使l(q) 极大化的那个 值。,极大似然法的主要思想：如果在一次观察中一个事件出现了，则这个事件出现的可能性最大。事件xx1,x2,xn在一次观察中(即从总体中抽取n个样本)出现了，就可认为 p(x|q)达到极大值，即在参数空间中使似然函数极大化的 值。 一个简单的例子：,假设似然函数p(x|q) 对未知参数q 是连续可微的，则 可由典型的求极值的方法求得。 求极大值的必要条件 单个q 的情况下： 若q 是向量，有s个分量q =q1,qs t，则多变量的梯度算子 对数似然函数h(q)是单调的增函数，为计算方便，一般用对数似然函数。, 正态分布的极大似然估计,从总体中抽取n个样本 xk，观察下列

6、不同情况： 已知，均值向量m未知，即q =m。 m的极大似然估计必须满足方程： 未知均值的极大似然估计正是样本的算术平均。, 一维正态情况，两个参数均未知，设q1m，q2s 2 , qq1,q2 t 。,多维正态密度的情况。 计算方法和形式完全类似，只是复杂些，计算结果： 均值向量的极大似然估计是样本的均值，而协方差的极大似然估计是n个矩阵 的算术平均。这是一致估计。 协方差矩阵的无偏估计为,2. bayes估计和bayes学习,bayes估计：根据样本集 x 确定总体某个参数q bayes学习：利用样本集 x 确定概率密度函数p(x) bayes估计 基本原理：把参数q当作具有某种先验分布p

7、(q) 的随机变量, 对样本x观察使先验分布转化为后验分布p(q|x)，据此再修正原先的估计 。 假设： 把所有的样本按类别分成c个子集。每个子集有n个样本 x = x1,x2,xn。每类可单独处理。 已知样本的分布形式p(x|q) ，而参数q 未知。 q为随机变量, 已知其先验概密函数p(q) 。,贝叶斯估计和最小风险贝叶斯决策可统一： bayes估计：有一个样本集x，用来估计所属总体分布的某个参数，使带来的贝叶斯风险最小。 bayes估计最小风险 r为给定条件下某个估计量的期望损失，常称为条件风险。使条件风险最小的估计量q，也就是贝叶斯估计。 经推导(p.52定理3.1)使用平方误差损失函

8、数时，得到估计量为条件期望：,bayes参数估计步骤： 确定q 的先验概率密度函数p(q)； 由样本集 x = x1,x2,xn计算样本的联合分布 ，它是 q 的函数 ； 用bayes公式求后验分布p(q | x) 求样本的估计量q,正态分布情况的bayes估计举例 样本为一维正态分布 p(x|m)n(m,s 2)，m未知 m是随机的，其先验概密 p(m)n(m0,s02) n个样本构成样本集 x=x1, x2, xn 求m的估计量 解： 用bayes公式求m的后验分布：,a比例因子与无关,根据上述假设： 代入计算后验概密 p(|x) p(|x)是的二次函数的指数函数，仍是正态密度, 写成,

9、bayes学习求概率密度函数p(x| x) 从联合密度求条件概密函数 x由n个样本组成，x=x1,xn 用bayes公式计算q 的后验分布 p(q|x)， 根据独立性 其中 xn=x1, xn1,xn， xn1=x1,xn1,已知q 的先验概密 p(q|x0) = p(q)，根据样本序列x1, xn按下式反复计算，得到概率密度的序列p(q), p(q|x1), p(q|x1,x2),，同时修改q，如果这个密度序列在估计值 附近产生一个陡峰, 即d 函数, 这种性质称为bayes学习。,bayes学习步骤： 前三步同bayes估计。下面的步骤 读入第一个样本x1，计算得到得到后验概密p(q|x1

10、), 据此作为下一步计算的先验概率密度； 读入样本x2，计算得到p(q|x1,x2) ； ； 这样得到一个概率密度序列： 这个过程称为参数估计的递归的bayes方法。 这个序列收敛于一个q0为中心的d 函数，则这个性质称 bayes 学习。大多数密度函数有此性质。,从前例 bayes学习得到条件概率密度函数 非监督参数估计方法所采用的也是这两种方法，但计算较复杂。就极大似然估计来说，由于样本的类别未知，因此定义c类样本组成的混合密度建立似然函数。,3 总体分布的非参数估计,根据训练样本集x=x1, x2, xn , 估计总体分布概率密度函数p(x|x1, x2, xn)形式。 基本思想： 每个

11、样本对总体概率密度 分布都有贡献 (如矩形a)， n个样本的贡献叠加起来， 得到概率密度估计，如虚线。 也可认为每个样本在自己位 置上贡献增大，离得远贡献 小(如正态分布)，同样叠加 得到概率密度估计(下图)。,直方图方法估计一维概率密度函数近似值： 将x轴划分为长度为h的区间，样本x落在某个区间的概率就是这个区间的估计值。 样本总数为n，落在某个区间的点数为kn，相应的概率近似于频数： p kn /n 概率密度在同一个区间为常数，近似等于 估计值收敛于真实值的条件： hn 0； kn ； kn /n0。 这三个条件表示对n的依赖型。,理论上讲，要使 ，就必须使体积v趋于零，同时n和k 趋于无

12、穷大。 若体积v固定, 样本取得越来越多, 则k/n收敛，只能得到p(x)的空间平均估计 若样本数n固定，使r不断缩小，v趋于零，会发生两种无意义情况：一是区域内不包含任何样本，p(x)=0；二是碰巧有一个样本，p(x) = 。 实际上样本是有限的，v也不能任意缩小。若用这种方法估计，频数k/n和估计的p(x)将存在随机性，都有一定的方差。,假设有无限多的样本可利用，在特征空间构造包含x点的区域序列r1, r2, rn, 对r1用一个样本进行估计，对r2用二个样本，。设落在rn的 x点数为kn，则第n次估计的概率密度函数为 要使,满足这三个条件的区域序列通常有两种方法： parzen窗法： 把

13、包含x点的区域序列vn选为样本数目n的函数，并使其空间体积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为一个超立方体， ，边长为hn, d为特征空间维数。 训练样本xi是否落入这个超立方体内，检查x-xi的每个分量值，若小于hn/2，则在rn内，其中x为数轴(特征空间坐标轴)上的

14、点。 为了用函数描述落入vn 中训练样本的数目kn，定义窗函数 对u的特征空间来说，f(u)是围绕原点的1个单位超立方体。,若u=(x-xi)/hn，则窗函数 当某个样本xi落入以x为中心、体积为vn的立方体内时计为1，否则为0。 落入vn内的样本数： x点的密度估计 parzen窗的密度估计,在以x为中心的立方 体内的样本应相加,用方窗的直观解释一维概率密度函数的估计： 样本集xx1,x2,x5有五个样本。 每个样本xi在以 xxi为中心，宽为h的范围内对概率密度函数贡献为1，数轴x上任一点的概密函数是样本集中全部样本对概密函数之和。 对所有的点求和，得到p(x)的分布虚线所示。 如果样本数

15、很多，并选择适当的窗函数，估计的概率密度函数的性质有可能接近真实的概率密度函数p(x)。,估计量 为密度函数的条件 为使 是一个估计合理的概率密度函数，必须满足对概率密度函数的基本要求，即它应该非负且在特征空间积分为1。 为此窗函数须满足两个条件：,窗函数的选择： 方窗函数 正态窗函数 指数窗函数 只要所选择的函数满足前述的两个条件式，都可作为窗函数。,估计量的统计性质,产生随机变量的补充材料（共四页，三个问题） 产生 0,1之间均匀分布的随机数ui方法,产生随机变量方法(非0,1均匀分布的随机数) 基本方法反变换法 以概率积分变换定理为基础的一种常用的抽样方法。其基础是0,1之间均匀分布的随

16、机数。 若随机变量x的分布函数为f(x)，其反函数f -1。可用0,1之间均匀分布的随机数来产生要求分布的随机变量。 具体方法 u为0,1均匀分布随机数 令 u=f(x) x = f-1(u) x即为所要求分布的随机变量。,x,产生一维正态分布随机变量的近似方法,举例 根据已知概率密度函数p(x)产生一系列随机变量，作为样本。用正态窗函数估计样本的总体分布，并与真实的概率密度函数作比较。 采用下列两种样本： p(x)是均值为0方差为1的正态分布，生成样本xi p(x)是两个均匀分布的混合密度生成样本xi,其他,统计落入正态窗的随机样本数，计算p(x)的估计值，在计算中要注意公式中变量和参数的意

17、义。 这种方法具有普遍性，即不管是规则或不规则、单峰或多峰分布都可用，但需要的样本数量很大。,从图中 可看出 n256， h11时， 接近真实 分布，而 h14时， 噪声小。 当样本数 很多时， h1影响不 大。,均值为0方差为1的正态分布,二个均匀分布的混合密度,基本步骤： 产生训练集样本，有两种方法： 在问题域中搜集样本； 根据题意按已知的概率密度产生随机样本。 设x为d维的数轴，以体积 在数轴上向前推进，即n=1,2,3,，这样就可统计落入各体积的样本数kn。 选择窗函数f(u)，利用概率密度函数公式进行统计 计算数轴上各点的密度。 对所有的点求和，用图形表示概率密度曲面(一维为曲线)。

18、 如果自行按某种概率密度产生的随机数，则可将计算得到的曲面(线)与其进行比较，以验证parzen窗法的正确性。,3. kn近邻法 parzen 窗存在问题：体积v的选择 v1的选择很敏感，太小大部分是空的噪声大；太大估计值平坦，不能反映总体分布变化。 kn近邻法：体积不是样本的函数，而是kn的函数。先确定kn，然后以x点为中心，让体积不断扩大，直到捕获到kn个样本为止，这些样本称为x的kn个近邻。如果点x附近密度愈高, 则体积愈小, 分辨率高，反之体积愈大。 kn近邻估计公式：,估计的pn (x)收敛于真实概率密度p(x)的充分必要条件： kn 可取为n的某个函数，如 k1 0 选择k1，使k

19、n 1。 这种方法同样要求样本数量要大。一维要几百个样本；二维要几千个样本。,例：条件同上例，用kn近邻法。 p(x)是均值为0方差为1的正态分布，生成样本xi p(x)是二个均匀分布的混合密度生成样本xi 设 n=1,16,256, ；kn =1,4,16, 估计结果为左图所示。 计算步骤与parzen窗法类似。,其他,4 近邻法,kn近邻法是利用样本进行概率密度函数的估计。 现在讨论的是直接利用样本，根据距离分类。 近邻法： 在设计阶段已根据训练集样本在特征空间划分了边界。计算待识别样本点x到周围近邻的距离， 将x归入最近邻中样本所属的那个类。 最近邻法 k-近邻法 此法属非参数法(无需估

20、计概率密度)有近邻法，线性判别函数和聚类(非监督学习法)。,两种近邻法,1.最近邻法 决策规则 设有c个类别 ，每类有标明类别的ni个样本，i =1, 2 , c。 wi类的判别函数和决策规则： 比较未知样本x与 个已知类别样本xik 间的欧氏距离，将 x 归入离它最近的那个样本类。,最近邻法错误率的分析,训练集样本数有限，有时多一个或少一个对分类结果影响较大。 例如图中有 a类和 b类， o 代表待分样本,用欧氏距离测量，o的近邻为a3，分在a类；若将a3拿开，o就分在b类。 说明最近邻法错误率有偶然性。样本越多偶然性减少。 因此用训练样本数增到 极大来评价性能，用到 渐近概念分析错误率。,

21、设n个样本下的平均错误概率为pn(e)，且样本x的最近邻为x ，则 可证明下述关系 根据第二章，贝叶斯错误率p*,最近邻法渐近平均错误率p的范围(上下界) ：,根据最近邻法错误率的公式 图中标明最近邻法错误率的上下界。 bayes错误率在0和(c-1)/c 之间。 当bayes错误率较小时， 最近邻法的错误率最大为bayes两倍。 一般情况下，近邻法错误率在阴影区域中。 近邻法是一种次优法，它的错误率比bayes决策大。当样本数目无限大时，它的错误率p不会超过bayes错误率p*的2倍。,p=2p*,p=p*,2. k-近邻法，最近邻法的改进 在待分样本x的k个近邻中，按出现最多的样本类别来作

22、为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 决策规则：,例图中设定k=5, 用欧氏距离度量x到这三类的距离得到：k1 =4, k2 =1, k3 = 0。 根据判别规则x为w1类。 最近邻法是k近邻法的特例，k=1。 k近邻法克服了最近邻法的偶然 性，增加了可靠性。 两种近邻法的比较 图例，用欧氏距离度量 最近邻法：待分类样本x属于a。 k近邻法： k=8, a类k1 =3, b类k2 =5, x属于b。 直观上x划分到b合理。,k-近邻法错误率 在两类情况下，k为奇数时(避免出现k1=k2的情况)，两类问题的k-近邻法的错误率，下界为p*, 上界为ck(p*)，其中ck是大于 的关于的p*函数，并随着k增加而减小，可得 图中为具有不同k值时k