第三章概率密度函数估计及近邻法Estimation of Probability Density Function and The Nearest Neighbor Rule1 引言2 总体分布的参数估计 极大似然估计 贝叶斯估计参数3 总体分布的非参数估计 Parzen窗法 kN近邻法4 近邻法则 1 引言基于样本的两步贝叶斯决策： 估计类条件概率密度 和先验概率 ； 利用 和 完成分类器设计。(第二章)本章讨论从样本集推断总体概率分布p(x|wi) 。而样本的先验概率P(wi)的估计较易实现。概率密度函数含参数和形式两方面内容，分别称为参数估计和非参数估计。其估计方法：1. 监督参数估计 已知样本类别wi及其p(x|wi)形式，而参数未知，需从训练样本x估计参数q q，如一元正态分布的m、s 2等参数。2. 非监督参数估计 未知样本类别wi ，已知概率密度函数p(x|wi)的形式，但参数未知，需从样本x估计参数。 上述两种均可用极(最)大似然法和Bayes估计法来估计参数。3. 非参数估计即估计p(x|wi)形式 已知样本类别，但未知概率密度函数的形式，要从样本推断p(x|wi)属于哪种分布。 可用Parzen窗法和kN近邻法。4. 近邻法则不属于估计内容 直接利用样本设计分类器。非参数(即分类中不需要估计概率密度函数) 方法之一。5. 参数估计的几个基本术语统计量：每个训练样本都包含总体信息。根据从总体中抽取的样本集构造某种函数, 该函数统计学中称为统计量。参数空间：概率密度形式已知，参数q q 未知, q q 可取值的集合称为参数空间，记为。点估计、估计量和估计值：构造一个统计量f(x1,xn) 作为参数q 的估计量 。如果x1,xn属于某类，代入统计量f，就可得到该类具体的估计值。本章参数估计属于点估计。区间估计要求用区间(d1, d2)作为q 可能取值范围的一种估计。该区间称为置信区间。2 总体分布的参数估计1. 极(最)大似然估计 基本原理 把参数q q 看成确定的(非随机) 但取值未知，最好估计值是在样本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个样本的概率。极大似然估计值定义： 令l(q q) 为样本集x的似然函数，在的参数空间中能使l(q q) 极大化的那个 值。极大似然法的主要思想：如果在一次观察中一个事件出现了，则这个事件出现的可能性最大。事件xx1,x2,xN在一次观察中(即从总体中抽取N个样本)出现了，就可认为 p(x|q)达到极大值，即在参数空间中使似然函数极大化的 值。一个简单的例子：假设似然函数p(x|q q) 对未知参数q q 是连续可微的，则 可由典型的求极值的方法求得。求极大值的必要条件 单个q q 的情况下： 若q q 是向量，有s个分量q q =q1,qs T，则多变量的梯度算子对数似然函数H(q q)是单调的增函数，为计算方便，一般用对数似然函数。 正态分布的极大似然估计 从总体中抽取N个样本 xk，观察下列不同情况：已知，均值向量m m未知，即q q = =m m。 m的极大似然估计必须满足方程： 未知均值的极大似然估计正是样本的算术平均。 一维正态情况，两个参数均未知，设q1m，q2s 2 , q qq1,q2 T 。 多维正态密度的情况。 计算方法和形式完全类似，只是复杂些，计算结果： 均值向量的极大似然估计是样本的均值，而协方差的极大似然估计是N个矩阵 的算术平均。这是一致估计。 协方差矩阵的无偏估计为2. 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为随机变量, 已知其先验概密函数p(q) 。贝叶斯估计和最小风险贝叶斯决策可统一：Bayes估计：有一个样本集x，用来估计所属总体分布的某个参数，使带来的贝叶斯风险最小。Bayes估计最小风险 R为给定条件下某个估计量的期望损失，常称为条件风险。使条件风险最小的估计量q q，也就是贝叶斯估计。经推导(P.52定理3.1)使用平方误差损失函数时，得到估计量为条件期望：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)是的二次函数的指数函数，仍是正态密度, 写成 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), 据此作为下一步计算的先验概率密度； 读入样本x2，计算得到p(q|x1,x2) ； ； 这样得到一个概率密度序列： 这个过程称为参数估计的递归的Bayes方法。这个序列收敛于一个q q0为中心的d 函数，则这个性质称 Bayes 学习。大多数密度函数有此性质。从前例 Bayes学习得到条件概率密度函数非监督参数估计方法所采用的也是这两种方法，但计算较复杂。就极大似然估计来说，由于样本的类别未知，因此定义c类样本组成的混合密度建立似然函数。3 总体分布的非参数估计根据训练样本集x=x1, x2, xN , 估计总体分布概率密度函数p(x|x1, x2, xN)形式。基本思想： 每个样本对总体概率密度 分布都有贡献 (如矩形a)， N个样本的贡献叠加起来， 得到概率密度估计，如虚线。 也可认为每个样本在自己位 置上贡献增大，离得远贡献 小(如正态分布)，同样叠加 得到概率密度估计(下图)。直方图方法估计一维概率密度函数近似值：将x轴划分为长度为h的区间，样本x落在某个区间的概率就是这个区间的估计值。 样本总数为N，落在某个区间的点数为kN，相应的概率近似于频数： P kN /N 概率密度在同一个区间为常数，近似等于 估计值收敛于真实值的条件： hN 0； kN ； kN /N0。 这三个条件表示对N的依赖型。理论上讲，要使 ，就必须使体积V趋于零，同时N和k 趋于无穷大。 若体积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窗法： 把包含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为数轴(特征空间坐标轴)上的点。为了用函数描述落入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)的分布虚线所示。如果样本数很多，并选择适当的窗函数，估计的概率密度函数的性质有可能接近真实的概率密度函数p(x)。估计量 为密度函数的条件 为使 是一个估计合理的概率密度函数，必须满足对概率密度函数的基本要求，即它应该非负且在特征空间积分为1。为此窗函数须满足两个条件： 窗函数的选择： 方窗函数 正态窗函数 指数窗函数只要所选择的函数满足前述的两个条件式，都可作为窗函数。估计量的统计性质 产生随机变量的补充材料（共四页，三个问题）产生 0,1之间均匀分布的随机数ui方法 产生随机变量方法(非0,1均匀分布的随机数)基本方法反变换法 以概率积分变换定理为基础的一种常用的抽样方法。其基础是0,1之间均匀分布的随机数。若随机变量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)的估计值，在计算中要注意公式中变量和参数的意义。这种方法具有普遍性，即不管是规则或不规则、单峰或多峰分布都可用，但需要的样本数量很大。从图中可看出N256，h11时，接近真实分布，而h14时，噪声小。当样本数很多时， h1影响不大。均值为0方差为1的正态分布二个均匀分布的混合密度基本步骤：产生训练集样本，有两种方法： 在问题域中搜集样本； 根据题意按已知的概率密度产生随机样本。设x为d维的数轴，以体积 在数轴上向前推进，即N=1,2,3,，这样就可统计落入各体积的样本数KN。选择窗函数f(u)，利用概率密度函数公式进行统计 计算数轴上各点的密度。对所有的点求和，用图形表示概率密度曲面(一维为曲线)。如果自行按某种概率密度产生的随机数，则可将计算得到的曲面(线)与其进行比较，以验证Parzen窗法的正确性。3. kN近邻法Parzen 窗存在问题：体积V的选择 V1的选择很敏感，太小大部分是空的噪声大；太大估计值平坦，不能反映总体分布变化。kN近邻法：体积不是样本的函数，而是kN的函数。先确定kN，然后以x点为中心，让体积不断扩大，直到捕获到kN个样本为止，这些样本称为x的kN个近邻。如果点x附近密度愈高, 则体积愈小, 分辨率高，反之体积愈大。kN近邻估计公式： 估计的pN (x)收敛于真实概率密度p(x)的充分必要条件：kN 可取为N的某个函数，如 k1 0 选择k1，使kN 1。这种方法同样要求样本数量要大。一维要几百个样本；二维要几千个样本。例：条件同上例，用kN近邻法。 p(x)是均值为0方差为1的正态分布，生成样本xi p(x)是二个均匀分布的混合密度生成样本xi 设 N=1,16,256, ；kN =1,4,16, 估计结果为左图所示。计算步骤与Parzen窗法类似。 其他4 近邻法 kN近邻法是利用样本进行概率密度函数的估计。现在讨论的是直接利用样本，根据距离分类。近邻法： 在设计阶段已根据训练集样本在特征空间划分了边界。计算待识别样本点x到周围近邻的距离， 将x归入最近邻中样本所属的那个类。 最近邻法 k-近邻法此法属非参数法(无需估计概率密度)有近邻法，线性判别函数和聚类(非监督学习法)。 两种近邻法1.最近邻法 决策规则设有c个类别 ，每类有标明类别的Ni个样本，i =1, 2 , c。 wi类的判别函数和决策规则： 比较未知样本x与 个已知类别样本xik 间的欧氏距离，将 x 归入离它最近的那个样本类。最近邻法错误率的分析训练集样本数有限，有时多一个或少一个对分类结果影响较大。 例如图中有 A类和 B类， O 代表待分样本,用欧氏距离测量，O的近邻为A3，分在A类；若将A3拿开，O就分在B类。说明最近邻法错误率有偶然性。样本越多偶然性减少。因此用训练样本数增到 极大来评价性能，用到 渐近概念分析错误率。 设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个近邻中，按出现最多的样本类别来作为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-近邻法错误率 的上下界。k =1, 相当于最近邻法。 k 增加时, 上界靠近下界。 k , k-近邻法变成最优。实际使用时要折中考虑k的选取。3. 近邻法的优缺点优点： 实现简单；分类结果较好，错误率在一倍和两倍Bayes错误率P*之间。缺点： 需将全部训练样本存入计算机中, 每次决策都要计算x与全部样本的距离并进行比较。因此存贮量和计算量都很大。 没有考虑决策风险。 分析是建立在样本无限大的基础上，实际上是不可能的，对有限样本缺乏分析。4.改进算法目标是减小存储量和计算量，加速搜索待分类模式样本x的最近邻。两种原理： 分群分层，将计算压缩到接近x的小范围内。 在训练集中挑选对分类有效的样本，以减少样本数量。方法： 快速近邻算法，将样本分成不相交的子集，在此基础上搜索。分为：分量邻域法和列表法。 剪辑近邻法 压缩近邻法第三章习题1. 用贝叶斯学习的性质，说明当样本N趋于无穷时,极大似然估计等价于贝叶斯估计。2. 根据已知概率密度函数p(x) 产生N个随机数作为样本x， N=16, 256, 1000 。 p(x)是均值为0方差为1的正态分布，生成样本xN p(x)是二个均匀分布的混合密度生成样本xN 用指数窗函数和kN近邻法估计样本的密度函数。 给出程序框图，并编写程序，数据及图形与P44、48比较。其他3. 有七个二维向量： x1T =(1,0)、 x2T =(0,1)、 x3T =(0,-1)、 x4T =(0,0)、 x5T =(0,2)、 x6T =(0,-2)、 x7T =(-2,0), 假定前三个为w1类，后四个为w2 类要求： 画出最近邻法决策面； 求样本均值m1, m2。若按样本均值距离的大小进行分类，画出决策面。（清华教材6.5题）