切空间距离具有任意变换不变性.PPT

集合之间的距离度量 Hausdorff距离 练习计算集合 与 之间的Hausdorff距离 切空间距离 很多实际问题中，任意选择距离度量（如最常用的欧几里德距离）会带来糟糕的结果 切空间距离 不变量（invariance）问题 平移 旋转 尺度变换 线条粗细 …… 解决方案 预处理 使用更加一般化（具有**不变性）的距离度量 切空间距离 切空间距离具有任意变换不变性 假设问题可能会涉及r种变换 对每一个训练样本x’进行所有可能的变换，表示为 ，i=1,2,…,r，其中 为第i个变换的参数，如平移距离，旋转角度等 对每一种变换，可以构造一个切向量（tangent vector）： 所有变换的切向量张成x’的一个切空间（tangent space），该切空间是对x’可能发生的所有变换的一个线性逼近，其中每个点对应一种可能的变换 测试点x到x’的切空间距离即x到x’的切空间的最小距离，因此可认为具有任意变换不变性 切空间距离 例：旋转与细化的切空间 切空间距离 求x到x’的切空间距离 切空间距离 基于切空间距离的最近邻分类器通常具有很高的准确率 但是，切空间距离的计算要求设计者预先知道所有可能的变换，并且能够在每个原型点（训练样本点）上应用这些变换，这一要求在实践中有时无法满足 切空间距离的计算复杂度较高，在数据量较大时计算量可能无法忍受 小结 kn-近邻估计 小结 最近邻规则 直接估计后验概率 误差率 误差界 如果xk属于类别 ，则判断x的类别为 小结 k-近邻规则 误差界 降低k-近邻计算复杂度的方法 计算部分距离 预建立结构 对训练样本加以剪辑 如果 是在S中出现频率最高的类，则判断x的类别为 小结 距离度量的性质 非负性 自反性 对称性 三角不等式 常用距离度量 欧几里德距离 Minkowski距离 Mahalanobis距离 小结 集合之间的距离度量 Tanimoto距离 Hausdorff距离 切空间距离 任意变换不变性 * 黑板作图 尖锐的变化源自体积V的突然变化 * 把一维空间切分成若干小区间，数一数每个区间中有多少样本，落入某个区间中的个数k除以总数就是其对应格子的概率 * * * * 平方和的最小值当所有值相等时发生 板书推导 * * * * * 黑板画图说明L_1和L_2的区别 黑板作图 最近邻规则 k=1时的k-近邻决策 把x判断为与其距离最近的训练样本x’所属的类别 给定训练集 ，其中包括n个来自c个不同类别的样本 对测试样本x，如果 是距离x最近（根据某种距离度量）的训练样本，则最近邻（1-NN）规则为 最近邻规则是次优的方法，通常的误差率比最小可能的误差率（即贝叶斯误差率）要大 如果xk属于类别 ，则判断x的类别为 最近邻规则 直观理解 当样本个数非常大时，可认为x’距离x足够近，以使得即最近邻规则是对真实后验概率的一个有效近似 Voronoi网格 最近邻规则把特征空间分成一个个网格单元结构，称为Voronoi网格 每一个单元包含一个训练样本点x’ 该单元中任意一点x，到x’的距离均小于到其他训练样本点的距离 该单元中所有样本点均判别为x’所属的类别 最近邻规则的误差率 给定训练集 ，其中包括n个来自c个不同类别的样本 对测试样本x，设 是距离x最近的训练样本 x和xk的类别标记分别为 和 条件误差概率 最近邻规则的误差率 条件误差概率（cont’） 当 时，假设D包含的样本足够多，使得则当 时，有 平均误差率（ 时） 最近邻规则的误差界 平均误差率 的下界 平均误差率 的上界 当 对每个x取最小值时， 最大 设x的真实类别为 ，则贝叶斯误差率表示为 最近邻规则的误差界 平均误差率 的上界（cont’） 给定 （即给定 ）此式当第二项最小时最小，而第二项当 对所有除m以外的i取值相同时最小，即 最近邻规则的误差界 平均误差率 的上界（cont’） 所以或 所以 当P*较小时，最近邻规则的平均误差率上界： 最近邻规则的误差界 k-近邻规则 k-近邻（k-NN）规则是对最近邻（1-NN）规则的扩展，即考虑多个最近的邻居 给定训练集 ，其中包括n个来自c个不同类别的样本 对测