非参数估计(完整).ppt

非参数估计,刘芳，戚玉涛 qi_yutao,引言,参数化估计：ML方法和Bayesian估计。假设概率密度形式已知。 实际中概率密度形式往往未知。 实际中概率密度往往是多模的，即有多个局部极大值 。 实际中样本维数较高，且关于高维密度函数可以表示成一些低维密度函数乘积的假设通常也不成立。 本章介绍非参数密度估计方法：能处理任意的概率分布，而不必假设密度函数的形式已知。,主要内容,概率密度估计 Parzen窗估计 k-NN估计 最近邻分类器（NN） k-近邻分类器（k-NN）,概率密度估计,概率密度估计问题：,给定i.i.d.样本集： 估计概率分布：,概率密度估计,直方图方法：非参数概率密度估计的最简单方法 1. 把x的每个分量分成k 个等间隔小窗， （ xEd ，则形成kd 个小舱） 2. 统计落入各个小舱内的样本数qi 3. 相应小舱的概率密度为： qi /(NV ) （ N ：样本 总数，V ：小舱体积）,概率密度估计,直方图的例子,概率密度估计,非参数概率密度估计的核心思路：,一个向量x落在区域R中的概率P为：,因此，可以通过统计概率P来估计概率密度函数p(x),概率密度估计,假设N个样本的集合,是根据概率密度,函数为p(x)的分布独立抽取得到的。,那么，有k个样本落在区域R中的概率服从二项式定理：,k 的期望值为：,对P的估计：,当 时， 估计是非常精确的,概率密度估计,假设p(x)是连续的，且R足够小使得p(x)在R内几乎没有变化。 令R是包含样本点x的一个区域，其体积为V，设有N个训练样本，其中有k落在区域R中，则可对概率密度作出一个估计：,对p(x) 在小区域内的平均值的估计,概率密度估计,当样本数量N固定时，体积V的大小对估计的效果影响很大。 过大则平滑过多，不够精确； 过小则可能导致在此区域内无样本点，k=0。 此方法的有效性取决于样本数量的多少，以及区域体积选择的合适。,概率密度估计,收敛性问题：样本数量N无穷大是，估计的概率函数是否收敛到真实值？,概率密度估计,理论结果：,设有一系列包含x 的区域R1，R2，,Rn,，对R1采用1个样本进行估计，对R2用2 个， Rn包含kn个样本。Vn为Rn的体积。,为p(x)的第n次估计,概率密度估计,如果要求,能够收敛到p(x)，那么必须满足：,选择Vn,选择kn,概率密度估计,两种选择方法：,主要内容,概率密度估计 Parzen窗估计 k-NN估计 最近邻分类器（NN） k-近邻分类器（k-NN）,Parzen窗估计,定义窗函数：假设Rn是一个d维的超立方体。令hn为超立方体一条边的长度，则体积：,立方体窗函数为：,中心在原点的单位超立方体,Parzen窗估计,X处的密度估计为：,落入以X为中心的立方体区域的样本数为：,可以验证：,窗函数的要求,Parzen窗估计过程是一个内插过程，样本xi距离x越近，对概率密度估计的贡献越大，越远贡献越小。 只要满足如下条件，就可以作为窗函数：,窗函数的形式,方窗函数,指数窗函数,正态窗函数,其中：,窗口宽度的影响,Parzen估计的性能与窗宽参数hn紧密相关 当hn较大时，x和中心xi距离大小的影响程度变弱，估计的p(x)较为平滑，分辨率较差。 当hn较小时，x和中心xi距离大小的影响程度变强，估计的p(x)较为尖锐，分辨率较好。,窗口宽度的影响,窗函数,密度估计值,5个样本的Parzen窗估计：,渐近收敛性,Parzen窗密度估计的渐近收敛性： 无偏性： 一致性：,当 时，, x是一维的,上式用图形表示是6个分别以3.2，3.6，3，6，2.5，1.1为中心的正态曲线，而PN(x)则是这些曲线之和。,代入：,由图看出，每个样本对估计的贡献与样本间的距离有关，样本越多，PN(x)越准确。,例：设待估计的P(x)是个均值为0，方差为1的正态密度 函数。若随机地抽取X样本中的1个、 16个、 256个作为 学习样本xi,试用窗口法估计PN(x)。 解：设窗口函数为正态的， 1，0 hN:窗长度，N为样本数，h1为选定可调节的参数。,由图看出, PN(x)随N, h1的变化情况 当N1时， PN(x)是一个以第一个样本为中心的正态曲线，与窗函数差不多。 当N16及N=256时 h10.25 曲线起伏很大，噪声大 h11 起伏减小 h14 曲线平坦 当N时， PN(x)收敛于一平滑的正态曲线， 估计曲线较好。,例：待估的密度函数为二项分布 解：此为多峰情况的估计 设窗函数为正态 解：此为多峰情况的估计 设窗函数为正态,x,-2.5,-2,1,0.25,0,2,P(x),-2.5x-2,0x2,x为其它,当N=1、16、256、 时的PN(x)估计如图所示 当N1时， PN(x) 实际是窗函数。 当N16及N=256时 h10.25 曲线起伏大 h11 曲线起伏减小 h14 曲线平坦 当N时，曲线较好。,Parzen窗估计,优点 由前面的例子可以看出， Parzen窗估计的优点是应用的普遍性。对规则分布，非规则分布，单锋或多峰分布都可用此法进行密度估计。 可以获得较为光滑且分辨率较高的密度估计，实现了光滑性和分辨率之间的一个较好平衡。 缺点 要求样本足够多，才能有较好的估计。因此使计算量，存储量增大。 窗宽在整个样本空间固定不变，难以获得区域自适应的密度估计。,识别方法,保存每个类别所有的训练样本； 选择窗函数的形式，根据训练样本数n选择窗函数的h宽度； 识别时，利用每个类别的训练样本计算待识别样本x的类条件概率密度： 采用Bayes判别准则进行分类。,例子： 基于Parzen估计的Bayesian分类器,较小,较大,主要内容,概率密度估计 Parzen窗估计 Kn近邻估计 最近邻分类器（NN） k-近邻分类器（k-NN）,Kn近邻估计,在Parzen窗估计中，存在一个问题：对hn的选择。 若hn选太小，则大部分体积将是空的（即不包含样本），从而使Pn(x)估计不稳定。 若hn选太大，则Pn(x)估计较平坦，反映不出总体分布的变化 Kn近邻法的思想：固定样本数量Kn ，调整区域体积大小Vn，直至有Kn个样本落入区域中,Kn近邻估计,Kn近邻密度估计：,在X处的概率密度估计值为：,渐近收敛的条件,渐近收敛的充要条件为：,通常选择：,Kn近邻估计,例子：,例子：,Parzen windows,kn-nearest-neighbor,斜率不连续,当n值为有限值时Kn近邻估计十分粗糙,例子：,Parzen windows,kn-nearest-neighbor,Kn近邻估计,Kn近邻后验概率估计： 给定i.i.d.样本集 ，共 类。把一个体积V放在x周围，能够包含进k个样本，其中有 ki个样本属于第i类。那么联合概率密度的估计为： 后验概率：,Kn近邻估计,例子,X属于第i类的后验概率就是体积中标记为第i类的样本个数与体积中全部样本点个数的比值。 为了达到最小误差率，选择比值最大的那个类别作为判决结果。 如果样本足够多、体积足够小，这样的方法得到的结果是比较准确的！,主要内容,概率密度估计 Parzen窗估计 k-NN估计 最近邻分类器（NN） k-近邻分类器（k-NN）,最近邻分类器(NN),假设i.i.d.样本集 对于样本 ，NN采用如下的决策： 相当于采用 近邻方法估计后验概率，然后采用最大后验概率决策。 分类一个样本的计算复杂度： （采用欧氏距离）,最近邻分类器,样本 x = (0.10, 0.25) 的类别？,最近邻分类器,决策边界： Voronoi网格,NN分类规则将特征空间分成许多Voronoi网格 （ Voronoi网格：由一组由连接两邻点直线的垂直平分线组成的连续多边形组成 ）,最近邻分类器,决策边界 在一个Voronoi网格中，每一个点到该 Voronoi网格原型的距离小于到其它所有训练样本点的距离。 NN分类器将该Voronoi网格中的点标识为与该原型同类。,最近邻分类器,决策边界： 在NN分类器中，分类边界对于分类新样本是足够的。 但是计算或者存储分类边界是非常困难的 目前已经提出许多算法来存储简化后的样本集，而不是整个样本集，使得分类边界不变。,NN分类器的渐近误差界,NN分类器的渐近误差界,假设能够得到无限多的训练样本和使用任意复杂的分量规则，我们至多只能使误差率降低一半。 也就是说，分类信息中的一半信息是由最邻近点提供的！,最近邻分类器,当样本有限的情况下，最近邻分类器的分类效果如何？ 不理想！ 随着样本数量的增加，分类器收敛到渐近值的速度如何？ 可能会任意慢，而且误差未必会随着n的增加单调递减！,k-近邻分类器（k-NN）,假设i.i.d.样本集 对于样本 ，k-NN采用如下的决策： 搜索与 最近的 个近邻，如果 个近邻中属于 类的样本最多，则判决 属于 原理：相当于采用 近邻方法估计后验概率，然后采用最大后验概率决策。 分类一个样本的计算复杂度： （采用欧氏距离）,k-近邻分类器,从测试样本x开始生长，不断扩大区域，直至包含进k个训练样本； 把测试样本x的类别归为与之最近的k个训练样本中出现频率最大的类别。,例： k = 3 (odd value) and x = (0.10, 0.25)t 选择 k-NN to x (0.10, 0.28, 2); (0.12, 0.20, 2); (0.09, 0.30,5) X属于 2。,k-近邻分类器,决策面： 分段线性超平面 每一个超平面对应着最近两点的中垂面。,k-近邻分类器,k-NN分类器的误差率在样本数无穷大时趋向于Bayesian最小错误率！,k-NN分类器,近邻分类器 假设i.i.d.样本集 对于样本 ， -NN采用如下的决策： 搜索与 最近的 个近邻，如果 个近邻中属于 类的样本最多，为 个，则判决 属于 ，否则拒识。,k-NN分类器,k-NN分类器的优点： 原理和实现简单，特别适用于大类别问题。 当训练样本数较多时，误差界小于2倍的Bayesian最小错误率。,k-NN分类器,k-NN分类器的缺点： 由于训练样本数有限，k-NN估计的后验概率往往并不精确，从而导致分类错误率远远大于Bayesian最小错误率。 搜索近邻需要遍历每一个样本，计算复杂度较大。 需要存储所有样本。 受噪声和距离测度的选择影响较大。,距离度量,距离度量应满足如下三个性质： 非负性： 自反性： 当且仅当 对称性： 三角不等式：,距离测度的选取原则：需要精心选择类内变化平缓，类间变化剧烈的距离测度！,常用的距离函数,欧几里德距离：(Eucidean Distance),曼哈顿距离：(Manhattan Distance),常用的距离函数,明氏距离：(Minkowski Distance),马氏距离：(Mahalanobis Distance),常用的距离函数,角度相似函数：(Angle Distance),海明距离：(Hamming Distance),x和y为2值特征矢量：,D(x,y)定义为x,y中使得不等式 成立的i的个数。,最近邻分类器的简化,最近邻分类器的简化方法可以分为三种： 部分距离法； 预分类法； 需要存储所有样本问题：浓缩、剪枝。,部分距离法,定义：,Dr(x,y)是r的单调不减函数。令Dmin为当前搜索到的最近邻距离，当待识别样本x与某个训练样本xi的部分距离Dr(x,xi)大于 Dmin时， Dd(x,xi)一定要大于Dmin ，所以xi一定不是最近邻，不需要继续计算Dd(x,xi) 。,预分类（搜索树）,预分类（搜索树）,在特征空间中首先找到m个有代表性的样本点，用这些点代表一部分训练样本； 待识别模式x首先与这些代表点计算距离，找到一个最近邻，然后在这个最近邻代表的样本点中寻找实际的最近邻点。 这种方法是一个次优的搜索算法。,浓缩、剪枝,浓缩(Condensing)：仅保留对决策边界有贡献的样本，删除没有贡献的样本。,Original data,Consistent data,浓缩、剪枝,浓缩(Condensing) 最近邻剪辑算法：删除周围网格全为同类的Voronoi 原型。,浓缩、剪枝,剪枝(Pruning)：删除噪声样本点，使决策边界变得更加光滑。 Wilson pruning算法: 删除那些类别与周围k-NN多数不一致的样本。,Original data,Wilson editing with k=7,浓缩、剪枝,通常先进行剪枝然后进行浓缩,