1、Ch 05. 非参数方法,Part 2 kn-近邻估计,Parzen窗估计的问题,如果p(x)的分布不均匀，在整个特征空间中采用同样的窗宽度可能无法总是得到令人满意的结果,同样尺寸的窗口,kn-近邻估计,一种解决Parzen窗估计单一窗宽问题方法不固定窗宽度，而固定包括在x周围的某个区域中的样本个数k通常k取决于样本总数n，所以表示为kn当x周围数据密度大时，窗口变小（分辨率高）当x周围数据密度小时，窗口变大（分辨率低）包括进来的kn个样本称为x的kn个最近邻,窗口包含同样多的样本,kn-近邻估计,令 ，则 收敛到真实分布p(x)的充要条件为满足此条件的一个常用选择,举例,一维分布，n=1时，
2、 时，,举例,n=8, k=3或5,举例,K=5,举例,更多非参数估计的例子,直方图估计,更多非参数估计的例子,Parzen窗估计,更多非参数估计的例子,kn-近邻估计,更多非参数估计的例子,更多非参数估计的例子,Ch 05. 非参数方法,Part 3 k-近邻规则,模式分类的途径,途径1：估计类条件概率密度通过 和 ，利用贝叶斯规则计算后验概率 ，然后通过最大后验概率做出决策两种方法方法1a：概率密度参数估计基于对 的含参数的描述方法1b：概率密度非参数估计基于对 的非参数的描述途径2：直接估计后验概率不需要先估计途径3：直接计算判别函数不需要估计 或者,后验概率的非参数估计,假设一个x附近
3、的区域R，能够包括进k个样本，其中ki个属于类别 ，则后验概率决策Parzen窗估计：选择 最大的类别kn-近邻估计：选择 最大的类别,最近邻规则,k=1时的k-近邻决策把x判断为与其距离最近的训练样本x所属的类别给定训练集 ，其中包括n个来自c个不同类别的样本对测试样本x，如果 是距离x最近（根据某种距离度量）的训练样本，则最近邻（1-NN）规则为最近邻规则是次优的方法，通常的误差率比最小可能的误差率（即贝叶斯误差率）要大,最近邻规则,直观理解当样本个数非常大时，可认为x距离x足够近，以使得即最近邻规则是对真实后验概率的一个有效近似,Voronoi网格,最近邻规则把特征空间分成一个个网格单元
4、结构，称为Voronoi网格每一个单元包含一个训练样本点x该单元中任意一点x，到x的距离均小于到其他训练样本点的距离该单元中所有样本点均判别为x所属的类别,最近邻规则的误差率,给定训练集 ，其中包括n个来自c个不同类别的样本对测试样本x，设 是距离x最近的训练样本x和xk的类别标记分别为 和条件误差概率,最近邻规则的误差率,条件误差概率（cont）当 时，假设D包含的样本足够多，使得则当 时，有平均误差率（ 时）,最近邻规则的误差界,平均误差率 的下界平均误差率 的上界当 对每个x取最小值时， 最大设x的真实类别为 ，则贝叶斯误差率表示为,最近邻规则的误差界,平均误差率 的上界（cont）给定
5、 （即给定 ）此式当第二项最小时最小，而第二项当 对所有除m以外的i取值相同时最小，即,最近邻规则的误差界,平均误差率 的上界（cont）所以或所以当P*较小时，最近邻规则的平均误差率上界：,最近邻规则的误差界,k-近邻规则,k-近邻（k-NN）规则是对最近邻（1-NN）规则的扩展，即考虑多个最近的邻居给定训练集 ，其中包括n个来自c个不同类别的样本对测试样本x，设集合 包含距离x最近的k个训练样本k-近邻规则,如果 是在S中出现频率最高的类，则判断x的类别为,k-近邻规则,k-近邻规则的误差界,平均误差率 的下界贝叶斯误差率平均误差率 的上界当 ，并且 时，当k足够大，但是相对于n又足够小时
6、，在大样本数上应用k-NN规则近似于最优决策,k-近邻规则的误差界,k的选择,k-近邻规则可被看作直接从样本中估计后验概率 的方法为了得到可靠的估计（误差率低），k越大越好为了使 尽可能逼近 ，x的近邻x距离x越近越好，即k越小越好根据实际问题，折中选取k的值当n趋向于无穷大，并且k以较慢的速度同样趋向于无穷大时，k-近邻规则是最优分类规则,例子,k = 3 (奇数)， x = (0.10, 0.25)x的k个近邻:(0.10, 0.28, 2); (0.09, 0.30, 5); (0.12, 0.20,2)根据k-近邻规则，判断x的类别为2,计算复杂度,直接方法假设训练集D包括n个d维样本
7、给定一个测试样本x，它与训练集中所有的样本xi之间都要计算距离，计算复杂度为O(dn)当n很大时，时间和空间复杂度都将很高！降低计算复杂度的方法计算部分距离预建立结构对训练样本加以剪辑,计算部分距离,在计算距离时，只使用d个维度中的一个子集r逐步加进更多的维数时，部分距离的值严格非递减计算测试样本x的最近邻时如何节省计算量？计算x的最近邻时，每考察一个训练样本，可以更新当前的x的最近邻。如果x到某个训练样本的在子集r上的部分距离已经大于其到当前最近邻的距离，则计算可以立即停止，舍弃该训练样本，继续考察下一个。当计算距离时，如果方差大的维度先计算，此技术尤其有用,预建立结构,预先建立某种形式的搜
8、索树，根据训练样本点之间的相对距离将它们组织起来搜索树建立好之后，寻找x的最近邻只需访问整个树的一部分，因此可以节省计算量例子假设样本服从单位正方形内的均匀分布选择4个根节点 和对测试点x，首先计算其到4个根节点的距离，选择最近的一个，接下来的搜索就仅局限于这个根节点所代表的象限了，而剩下的3/4训练样本没有必要访问。不能保证找到x的真正最近邻,训练样本剪辑,消去那些“无用”的训练样本哪些样本“无用”？被同类别样本包围的样本！,无用的样本,训练样本剪辑,最近邻剪辑算法,Ch 05. 非参数方法,Part 4 距离度量,距离度量,最近邻规则或k-近邻规则以衡量模式（样本）之间的距离的度量为基础距
9、离度量是模式识别领域的核心问题之一度量（metric）的一般化表示度量必须满足的性质非负性：自反性：对称性：三角不等式：,欧几里德距离,d维空间中的欧几里德距离特征尺度的变换会严重影响以欧几里德距离计算的近邻关系,欧几里德距离,解决方案对每一个维度（特征）分布进行尺度均衡化，使得每一维上的变化范围都相等，如全部归一化成0, 1区间,Minkowski距离,d维空间中的Minkowski距离又称为Lk范数L2范数欧几里德距离L1范数Manhattan距离（街区距离） 范数a和b在d个坐标轴上投影距离的最大值,Minkowski距离,到原点的等距离面,Mahalanobis距离,Mahalanob
10、is距离（马氏距离）在计算距离时考虑特征之间的协方差Mahalanobis距离与多元正态分布的关系,Mahalanobis距离,例子a：0.8, 0.2t，b： 0.1, 0.5t从正态分布 抽取，其中 ，求a和b之间的马氏距离解：,集合之间的距离度量,Tanimoto距离n1，n2分别为集合S1和S2中的元素个数n12为两个集合交集中的元素个数应用场景两个模式（特征）之间要么相同，要么不同，无法计算某种分级的相似度例如如两个单词之间的Tanimoto距离，可以将每个单词看作一个字母的集合,集合之间的距离度量,Tanimoto距离例子根据Tanimoto距离，判断下列单词中哪个与pat最为接近
11、：cat，pots，pattern解所以cat与pat最为接近,集合之间的距离度量,Hausdorff距离“一个集合中的点到另一个集合中的点的最小距离的最大值” 为某种衡量两点a和b之间距离的度量欧几里德距离Manhattan距离Mahalanobis距离,集合之间的距离度量,Hausdorff距离例子计算集合 与 之间的Hausdorff距离解,集合之间的距离度量,Hausdorff距离练习计算集合 与 之间的Hausdorff距离,切空间距离,很多实际问题中，任意选择距离度量（如最常用的欧几里德距离）会带来糟糕的结果,切空间距离,不变量（invariance）问题平移旋转尺度变换线条粗细解
12、决方案预处理使用更加一般化（具有*不变性）的距离度量,切空间距离,切空间距离具有任意变换不变性假设问题可能会涉及r种变换对每一个训练样本x进行所有可能的变换，表示为 ，i=1,2,r，其中 为第i个变换的参数，如平移距离，旋转角度等对每一种变换，可以构造一个切向量（tangent vector）：所有变换的切向量张成x的一个切空间（tangent space），该切空间是对x可能发生的所有变换的一个线性逼近，其中每个点对应一种可能的变换测试点x到x的切空间距离即x到x的切空间的最小距离，因此可认为具有任意变换不变性,切空间距离,例：旋转与细化的切空间,切空间距离,求x到x的切空间距离,切空间距
13、离,基于切空间距离的最近邻分类器通常具有很高的准确率但是，切空间距离的计算要求设计者预先知道所有可能的变换，并且能够在每个原型点（训练样本点）上应用这些变换，这一要求在实践中有时无法满足切空间距离的计算复杂度较高，在数据量较大时计算量可能无法忍受,小结,kn-近邻估计,小结,最近邻规则直接估计后验概率误差率误差界,小结,k-近邻规则误差界降低k-近邻计算复杂度的方法计算部分距离预建立结构对训练样本加以剪辑,如果 是在S中出现频率最高的类，则判断x的类别为,小结,距离度量的性质非负性自反性对称性三角不等式常用距离度量欧几里德距离Minkowski距离Mahalanobis距离,小结,集合之间的距离度量Tanimoto距离Hausdorff距离切空间距离任意变换不变性,
