非参数估计.ppt

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