Ch 05. 非参数方法
Part 2 kn-近邻估计
Parzen窗估计的问题
• 如果p(x)的分布不均匀，在整个特征空间中采用同 样的窗宽度可能无法总是得到令人满意的结果
同样尺寸的窗口
kn-近邻估计
• 一种解决Parzen窗估计单一窗宽问题方法
• 不固定窗宽度，而固定包括在x周围的某个区域中的样本个数k • 通常k取决于样本总数n，所以表示为kn • 当x周围数据密度大时，窗口变小（分辨率高） • 当x周围数据密度小时，窗口变大（分辨率低） • 包括进来的kn个样本称为x的kn个最近邻
• 对测试样本x，设
• 条件误差概率
是距离x最近的训练样本
• x和xk的类别标记分别为 和
最近邻规则的误差率
• 条件误差概率（cont’）
• 当 时，假设D包含的样本足够多，使得
则当
时，有
• 平均误差率（
时）
最近邻规则的误差界
• 平均误差率 的下界
• 平均误差率
• 当
的上界
对每个x取最小值时， 最大 ，则贝叶斯误差率表示为
• 逐步加进更多的维数时，部分距离的值严格非递减 • 计算测试样本x的最近邻时如何节省计算量？
• 计算x的最近邻时，每考察一个训练样本，可以更新当前的x的最 近邻。
• 如果x到某个训练样本的在子集r上的部分距离已经大于其到当前最 近邻的距离，则计算可以立即停止，舍弃该训练样本，继续考察 下一个。 • 当计算距离时，如果方差大的维度先计算，此技术尤其有用
• 平均误差率
贝叶斯误差率
的下界
• 平均误差率
• 当
的上界
时，
，并且
• 当k足够大，但是相对于n又足够小时，在大样本数上应 用k-NN规则近似于最优决策
k-近邻规则的误差界
k的选择
• k-近邻规则可被看作直接从样本中估计后验概率 的方法
• 为了得到可靠的估计（误差率低），k越大越好
• 为了使 尽可能逼近 越近越好，即k越小越好 • 根据实际问题，折中选取k的值 • 当n趋向于无穷大，并且k以较慢的速度同样趋向 于无穷大时，k-近邻规则是最优分类规则 ，x的近邻x’距离x
窗口包含同样多的样本
kn-近邻估计
• 令 则 ， 收敛到真实分布p(x)的充要条件为
• 满足此条件的一个常用选择
举例
• 一维分布，
• n=1时，
• n 1时，
1 pn ( x) 2 n max x xi
ikn 近邻
ห้องสมุดไป่ตู้

举例
n=8, k=3或5
举例
K=5
举例
更多非参数估计的例子
例子
k = 3 (奇数)， x = (0.10, 0.25)
训练样本 (0.15, 0.35)
类别
1
(0.10, 0.28)
(0.09, 0.30) (0.12, 0.20)
x的k个近邻:
2
5 2
{(0.10, 0.28, 2); (0.09, 0.30, 5); (0.12, 0.20,2)} 根据k-近邻规则，判断x的类别为2
计算复杂度
• 直接方法
• 假设训练集D包括n个d维样本
• 给定一个测试样本x，它与训练集中所有的样本xi之间 都要计算距离，计算复杂度为O(dn)
• 当n很大时，时间和空间复杂度都将很高！
• 降低计算复杂度的方法
• 计算部分距离 • 预建立结构 • 对训练样本加以剪辑
计算部分距离
• 在计算距离时，只使用d个维度中的一个子集r
预建立结构
• 预先建立某种形式的搜索树，根据训练样本点之 间的相对距离将它们组织起来 • 搜索树建立好之后，寻找x的最近邻只需访问整个 树的一部分，因此可以节省计算量 • 例子
• 最近邻规则把特征空间分成 一个个网格单元结构，称为 Voronoi网格
• 每一个单元包含一个训练样本 点x’ • 该单元中任意一点x，到x’的 距离均小于到其他训练样本点 的距离 • 该单元中所有样本点均判别为 x’所属的类别
最近邻规则的误差率
• 给定训练集 同类别的样本 ，其中包括n个来自c个不
• 设x的真实类别为
最近邻规则的误差界
• 平均误差率
• 给定
的上界（cont’）
）
（即给定
此式当第二项最小时最小，而第二项当 除m以外的i取值相同时最小，即
对所有
最近邻规则的误差界
• 平均误差率
• 所以
的上界（cont’）
或
• 所以 • 当P*较小时，最近邻规则的平均误差率上界：
最近邻规则的误差界
如果xk属于类别 ，则判断x的类别为
• 最近邻规则是次优的方法，通常的误差率比最小 可能的误差率（即贝叶斯误差率）要大
最近邻规则
• 直观理解
• 当样本个数非常大时，可认为x’距离x足够近，以使得
P(i | x ') P(i | x)
即最近邻规则是对真实后验概率的一个有效近似
Voronoi网格
k-近邻规则
• k-近邻（k-NN）规则是对最近邻（1-NN）规则的 扩展，即考虑多个最近的邻居
• 给定训练集 同类别的样本
• 对测试样本x，设集合 练样本 • k-近邻规则
如果
，其中包括n个来自c个不
包含距离x最近的k个训
是在S中出现频率最高的类，则判断x的类别为
k-近邻规则
k-近邻规则的误差界
• 后验概率
• 决策
• Parzen窗估计：选择 ki / k 最大的类别 i
• kn-近邻估计：选择 ki 最大的类别 i
k-近邻分类器
最近邻规则
• k=1时的k-近邻决策
• 把x判断为与其距离最近的训练样本x’所属的类别
• 给定训练集 同类别的样本
，其中包括n个来自c个不
• 对测试样本x，如果 是距离x最近（根据某种距 离度量）的训练样本，则最近邻（1-NN）规则为
• 直方图估计
更多非参数估计的例子
• Parzen窗估计
更多非参数估计的例子
• kn-近邻估计
更多非参数估计的例子
更多非参数估计的例子
Ch 05. 非参数方法
Part 3 k-近邻规则
模式分类的途径
• 途径1：估计类条件概率密度
• 通过 和 ，利用贝叶斯规则计算后验概率 通过最大后验概率做出决策 ，然后
• 两种方法
• 方法1a：概率密度参数估计
基于对 的含参数的描述
• 方法1b：概率密度非参数估计
基于对 的非参数的描述
• 途径2：直接估计后验概率
• 不需要先估计
• 途径3：直接计算判别函数
• 不需要估计 或者
后验概率的非参数估计
• 假设一个x附近的区域R，能够包括进k个样本，其中ki个属 于类别i ，则