非参数估计_KN近邻

1、2022-4-81非参数估计非参数估计-Kn近邻估计近邻估计报告人：马振磊报告人：马振磊2022-4-82统计决策法Bayes决策法参数估计法非参数估计法非参数估计法线性判别函数概率方法概率方法几何方法聚类分析非线性判别函数非参数估计2022-4-83 最大似然估计和贝叶斯估计都属于参数化估计。 要求待估计的类概率密度函数形式已知。 在实际应用中，类概率密度函数形式已知的条件并不一定成立，特别是多峰的概率分布，用普通函数难以拟合，这就需要用非参数估计技术。非参数估计2022-4-84 原理 不需获取类类概率密度的函数形式，而是直接利用学习样本估计特征空间任意点的类概率密度的值。 即直接由学习样

2、本来设计分类器。非参数估计2022-4-85概率密度估计概率密度估计 概率密度估计问题：概率密度估计问题：给定的样本集：给定的样本集：估计概率分布：估计概率分布：12,lX x xx p x2022-4-86概率密度估计概率密度估计 非参数概率密度估计的核心思路： RPpdx x一个向量一个向量x落在区域落在区域R中的概率中的概率P为：为：因此，可以通过统计概率因此，可以通过统计概率P来估计概率密度函数来估计概率密度函数p(x)2022-4-87概率密度估计概率密度估计 假设假设N个样本的集合个样本的集合是根据概率密度是根据概率密度函数为函数为p(x)的分布独立抽取得到的。的分布独立抽取得到的

3、。那么，有那么，有k个样本落在区域个样本落在区域R中的概率服从二项式中的概率服从二项式定理：定理：1N kkkNPPPkk 的期望值为的期望值为： E kNPkPN对对P的估计：的估计：当当 时，时， 估计是非估计是非常精确的常精确的N 2022-4-88概率密度估计概率密度估计 假设假设p(x)是连续的，且是连续的，且R足够小使得足够小使得p(x)在在R内几乎没内几乎没有变化。有变化。 令令R是包含样本点是包含样本点x的一个区域，其体积为的一个区域，其体积为V，设有，设有N个训练样本，其中有个训练样本，其中有k落在区域落在区域R中，则可对概率密度中，则可对概率密度作出一个估计：作出一个估计：

4、 RPpdpVxxx /k NpVxkPN对对p(x) 在小区域内的平均值的估计在小区域内的平均值的估计2022-4-89非参数估计 思路 用已知类别的学习样本在特征空间X处出现的频度 来近似 即： 其中：v为包含X点的区域 , k为n个样本中落入体积v的样本数。)/(jXPvnkxp/)(2022-4-810非参数估计故： 表示单位体积内落入x点邻域的样本在总样本中的比例，可以用此来近似样本在X点处的类概率密值。vnkxp/)(2022-4-811非参数估计 问题一 若v固定，则当n增大时， 只能表示平均概率，而不是点概率密度 因此，为保证 为点概率密度，必须有)( xp)( xp0 ,vn

5、时)()(xpxpnn2022-4-812非参数估计 问题二 若样本数n固定， 则当 时，则会出现x邻域内不包含任何样本，得出 的错误估计。0v0)(xp2022-4-813 解决方案 考虑让v和k都随n的变化进行调整，即： nnnvnkxPvnkxP/)(/)(非参数估计2022-4-814 如果要求如果要求 npx能够收敛到能够收敛到p(x)，那么必须满足：，那么必须满足：lim0nnVlimnnk lim/0nnkn选择选择Vn选择选择kn非参数估计2022-4-815非参数估计 基本方法 非参数估计法Parzen窗口法Kn近邻法2022-4-816 基本方法 Parzen窗口法：主动选

6、择vn与n的关系，kn被动确定，指n个样本中落入区域v的样本数 kn近邻法：主动选择kn与n的关系， vn被动确定，指包含kn个样本的x邻域非参数估计2022-4-817窗口宽度的影响窗口宽度的影响2022-4-818Kn近邻法近邻法 Parzen窗口法的估计效果取决于样本总数n及 当n较小时，对 较为敏感，即 ：1h1h 较大容易产生平均误差， 估计较平坦，反映 不出总体分布的变化。 较小容易产生噪声误差，大部分体积将是空的（即不包含样本），从而使 估计不稳定。1h1h)(xpn)(xpn2022-4-819Kn近邻法近邻法 其原因是由于 只与总样本数有关，即进行概率密度 估计时，任何x点处

7、的 都是相同的 一种合理的选择是对样本出现密度大的x处， 可较小，而对样本密度较小的x处， 则相对大一些，这就是近邻法。 nvnvnv)(xpnnhvn12022-4-820Kn近邻法近邻法2022-4-821Kn近邻法近邻法 基本原理 主动选择 与n的关系， 被动确定，即使得体积 为样本密度的函数，而不是样本总数的函数。 可选择 ，该条件可满足： a. b. c.nvnvnknnknnklim0/limnknn0)(limxPnkvnnnn2022-4-822Kn近邻法近邻法 近邻法，有效地解决了Parzen窗口法存在的问题，对平均误差和噪声性误差均有较好的改善 选择 后， 如何计算 ？ n

8、vnknnKnnnnvnvnkxP1/)(2022-4-823Kn近邻法近邻法 为与x点相邻的 个近邻样本中，与x距离最远的样本所构成的区域，即nvdnnhv nk2022-4-824Kn近邻法近邻法 用Kn近邻法设计分类器的过程： 获取n个学习样本 令 找到待识样本X处的Kn个近邻 计算Kn 个邻近到X的距离，找到最远距离的样本 计算邻域的直径 ，计算邻域的体积 nkndnnhv nhnXXX,.,212022-4-825Kn近邻法近邻法 则 对每一类样本重复上述过程，得各类的类概率密度 将样本X归类到 最大的类别中去dnnnnnhnvnvnkXP11/)()(Xpn)()(jnPXp202

9、2-4-826K KN N近邻法作后验概率的估计近邻法作后验概率的估计由KN近邻估计知N个已知类别样本落入VN内为KN个样本的概率密度估计为： N个样本落入VN内有KN个，KN个样本内有Ki个样本属于i类则联合概率密度： VNkxPNNN)()()|(),(iiNiiNPxPvNkxPKn近邻法近邻法2022-4-827根据Bayes公式可求出后验概率：MjjNiNNiiiiiiNxPxPPxPPxPxP11),(),()()|()()|()|(VNkxPxPNNMjjNN1),()(VNkxPNiiN),(kkxPNiiN)|(后验概率的估计： 类别为i的后验概率就是落在 内属于i的样本ki与 内总样本数 的比值。Kn近邻法近邻法VNVNkN2022-4-828K K近邻分类准则近邻分类准则：对于待分样本x，找出它的k个近邻，检查