非参数估计(完整)

非参数估计刘芳，戚玉涛[e-mail]引言参数化估计：ML方法和Bayesian估计。假设概率密度形式已知。实际中概率密度形式往往未知。实际中概率密度往往是多模的，即有多个局部极大值。实际中样本维数较高，且关于高维密度函数可以表示成一些低维密度函数乘积的假设通常也不成立。本章介绍非参数密度估计方法：能处理任意的概率分布，而不必假设密度函数的形式已知。主要内容概率密度估计Parzen窗估计k-NN估计最近邻分类器（NN）k-近邻分类器（k-NN）概率密度估计概率密度估计问题：给定i.i.d.样本集：估计概率分布：12,,,lXxxxpx概率密度估计直方图方法：非参数概率密度估计的最简单方法1.把x的每个分量分成k个等间隔小窗，（x∈Ed，则形成kd个小舱）2.统计落入各个小舱内的样本数qi3.相应小舱的概率密度为：qi/(NV)（N：样本总数，V：小舱体积）概率密度估计直方图的例子概率密度估计非参数概率密度估计的核心思路：RPpdxx一个向量x落在区域R中的概率P为：因此，可以通过统计概率P来估计概率密度函数p(x)概率密度估计假设N个样本的集合是根据概率密度函数为p(x)的分布独立抽取得到的。那么，有k个样本落在区域R中的概率服从二项式定理：1NkkkNPPPkk的期望值为：EkNPˆkPN对P的估计：当时，估计是非常精确的N概率密度估计假设p(x)是连续的，且R足够小使得p(x)在R内几乎没有变化。令R是包含样本点x的一个区域，其体积为V，设有N个训练样本，其中有k落在区域R中，则可对概率密度作出一个估计：RPpdpVxxx/ˆkNpVxˆkPN对p(x)在小区域内的平均值的估计概率密度估计当样本数量N固定时，体积V的大小对估计的效果影响很大。过大则平滑过多，不够精确；过小则可能导致在此区域内无样本点，k=0。此方法的有效性取决于样本数量的多少，以及区域体积选择的合适。概率密度估计收敛性问题：样本数量N无穷大是，估计的概率函数是否收敛到真实值？ˆlimNNppxx0R实际中，ˆpx越精确，要求：实际中，N是有限的：0Rˆ0px当时，绝大部分区间没有样本：ˆpx如果侥幸存在一个样本，则：概率密度估计理论结果：设有一系列包含x的区域R1，R2，…,Rn,…，对R1采用1个样本进行估计，对R2用2个，…，Rn包含kn个样本。Vn为Rn的体积。/nnnkNpVx为p(x)的第n次估计概率密度估计如果要求npx能够收敛到p(x)，那么必须满足：lim0nnVlimnnklim/0nnkn选择Vn选择kn概率密度估计两种选择方法：主要内容概率密度估计Parzen窗估计k-NN估计最近邻分类器（NN）k-近邻分类器（k-NN）Parzen窗估计定义窗函数：假设Rn是一个d维的超立方体。令hn为超立方体一条边的长度，则体积：dnnVh立方体窗函数为：中心在原点的单位超立方体11,1,,20jujdotherwiseuParzen窗估计X处的密度估计为：落入以X为中心的立方体区域的样本数为：1nininkhxx1/11ˆnnininnknpVnnVhxxxˆ0npxˆ1npdxx可以验证：窗函数的要求Parzen窗估计过程是一个内插过程，样本xi距离x越近，对概率密度估计的贡献越大，越远贡献越小。只要满足如下条件，就可以作为窗函数：0u1duu窗函数的形式其他.021||,1)(uu|}|exp{)(uu}21exp{21)(2uu方窗函数指数窗函数正态窗函数xxinuh其中：窗口宽度的影响Parzen估计的性能与窗宽参数hn紧密相关当hn较大时，x和中心xi距离大小的影响程度变弱，估计的p(x)较为平滑，分辨率较差。当hn较小时，x和中心xi距离大小的影响程度变强，估计的p(x)较为尖锐，分辨率较好。窗口宽度的影响窗函数密度估计值5个样本的Parzen窗估计：渐近收敛性Parzen窗密度估计的渐近收敛性：无偏性：一致性：当时，0nVˆlEppxx2ˆlim0nnpx0123456x6x5x3x1x2x4x例：对于一个二类（ω1，ω2）识别问题，随机抽取ω1类的6个样本X=(x1，x2，….x6)ω1=(x1，x2，….x6)=(x1=3.2，x2=3.6，x3=3，x4=6，x5=2.5，x6=1.1)估计P(x|ω1)即PN(x)解：选正态窗函数)21exp(21)(2uu])||(21exp[21)||()(2hxxhxxuNiNi∵x是一维的1NN1hVh,0.566hNN其中选，0.560.56NNhV上式用图形表示是6个分别以3.2，3.6，3，6，2.5，1.1为中心的正态曲线，而PN(x)则是这些曲线之和。111ˆNiNinnpNVhxxx代入：由图看出，每个样本对估计的贡献与样本间的距离有关，样本越多，PN(x)越准确。例：设待估计的P(x)是个均值为0，方差为1的正态密度函数。若随机地抽取X样本中的1个、16个、256个作为学习样本xi,试用窗口法估计PN(x)。解：设窗口函数为正态的，σ＝1，μ＝0hN:窗长度，N为样本数，h1为选定可调节的参数。])||(21exp[21)||(2hxxhxxNiNi1NhhN2111111||111||()()exp[]22NNiiNiiNNxxNxxPxNNVhhhNNhV用窗法估计单一正态分布的实验Parzen001.001.01.00.10.10001.001.01.00.10.10001.001.01.00.10.1025.01h202202202001.001.01.00.10.1011h41h由图看出,PN(x)随N,h1的变化情况①当N＝1时，PN(x)是一个以第一个样本为中心的正态曲线，与窗函数差不多。②当N＝16及N=256时h1＝0.25曲线起伏很大，噪声大h1＝1起伏减小h1＝4曲线平坦③当N→∞时，PN(x)收敛于一平滑的正态曲线，估计曲线较好。例：待估的密度函数为二项分布解：此为多峰情况的估计设窗函数为正态解：此为多峰情况的估计设窗函数为正态x-2.5-210.2502P(x)025.01)(xP-2.5x-20x2x为其它NhhuuN12],21exp[21)(001.001.01.00.10.10001.001.01.00.10.10001.001.01.00.10.1025.01h202202202001.001.01.00.10.1011h41h用窗法估计两个均匀分布的实验Parzen当N=1、16、256、∞时的PN(x)估计如图所示①当N＝1时，PN(x)实际是窗函数。②当N＝16及N=256时h1＝0.25曲线起伏大h1＝1曲线起伏减小h1＝4曲线平坦③当N→∞时，曲线较好。Parzen窗估计优点由前面的例子可以看出，Parzen窗估计的优点是应用的普遍性。对规则分布，非规则分布，单锋或多峰分布都可用此法进行密度估计。可以获得较为光滑且分辨率较高的密度估计，实现了光滑性和分辨率之间的一个较好平衡。缺点要求样本足够多，才能有较好的估计。因此使计算量，存储量增大。窗宽在整个样本空间固定不变，难以获得区域自适应的密度估计。识别方法1.保存每个类别所有的训练样本；2.选择窗函数的形式，根据训练样本数n选择窗函数的h宽度；3.识别时，利用每个类别的训练样本计算待识别样本x的类条件概率密度：4.采用Bayes判别准则进行分类。111iinjnijinpnVhx-xx例子：基于Parzen估计的Bayesian分类器lhnhnh较小较大主要内容概率密度估计Parzen窗估计Kn近邻估计最近邻分类器（NN）k-近邻分类器（k-NN）Kn近邻估计在Parzen窗估计中，存在一个问题：对hn的选择。若hn选太小，则大部分体积将是空的（即不包含样本），从而使Pn(x)估计不稳定。若hn选太大，则Pn(x)估计较平坦，反映不出总体分布的变化Kn近邻法的思想：固定样本数量Kn，调整区域体积大小Vn，直至有Kn个样本落入区域中Kn近邻估计Kn近邻密度估计：/ˆnnnknpVx固定样本数为nk，在nkxnVnk附近选取与之最近的个样本，计算该个样本分布的最小体积在X处的概率密度估计值为：渐近收敛的条件ˆnpxlimnnklim/0nnkn渐近收敛的充要条件为：通常选择：nknKn近邻估计例子：例子：Parzenwindowskn-nearest-neighbornkn斜率不连续当n值为有限值时Kn近邻估计十分粗糙例子：Parzenwindowskn-nearest-neighbornknKn近邻估计Kn近邻后验概率估计：给定i.i.d.样本集，共类。把一个体积V放在x周围，能够包含进k个样本，其中有ki个样本属于第i类。那么联合概率密度的估计为：后验概率：/ˆ,iiknpVxc12,,,nXxxx1ˆ,ˆˆ,iiiciipkpkpxxxKn近邻估计例子X属于第i类的后验概率就是体积中标记为第i类的样本个数与体积中全部样本点个数的比值。为了达到最小误差率，选择比值最大的那个类别作为判决结果。如果样本足够多、体积足够小，这样的方法得到的结果是比较准确的！主要内容概率密度估计Parzen窗估计k-NN估计最近邻分类器（NN）k-近邻分类器（k-NN）最近邻分类器(NN)假设i.i.d.样本集对于样本，NN采用如下的决策：相当于采用近邻方法估计后验概率，然后采用最大后验概率决策。分类一个样本的计算复杂度：（采用欧氏距离）1122,,,,,,llXyyyxxxargmin,iiXiifidthenyyxxxxOld1k最近邻分类器样本x=(0.10,0.25)的类别？TrainingExamplesLabelsDistance(0.15,0.35)(0.10,0.28)(0.09,0.30)(0.12,0.20)12520.1180.0300.0510.054最近邻分类器决策边界：Voronoi网格NN分类规则将特征空间分成许多Voronoi网格（Voronoi网格：由一组由连接两邻点直线的垂直平分线组成的连续多边形组成）最近邻分类器决策边界在一个Voronoi网格中，每一个点到该Voronoi网格原型的距离小于到其它所有训练样本点的距离。NN分类器将该Voronoi网格中的点标识为与该原型同类。最近邻分类器决策边界：在NN分类器中，分类边界对于分类新样本是足够的。但是计算或者存储分类边界是非常困难的目前已经提出许多算法来存储简化后的样本集，而不是整个样本集，使得分类边界不变。NN分类器的渐近误差界limlimnnnnPPerrorPerrorpdxxx*P****(2)21cPPPPPc*1,,*1,argmaxjjjcPerrorPjPPperrorpdxxxxxxnPerror若是n个样本时的误差率，并且：为最小Bayesian错误率，c为类别数。可以证明：NN分类器的渐近误差界****(2)21cPPPPPc假设能够得到无限多的训练样本和使用任意复杂的分量规则，我们至多只能使误差