Ch近邻法和集群.ppt

第1章 绪论 9 9 8 8 8 7 7 7 7 6 9 8 9 8 7 9 8 7 6 8 x20 x19 x18 x17 x16 x15 x14 x13 x12 x11 第4章 近邻法和集群 6 6 2 2 2 1 1 1 0 0 特征y 7 6 3 2 1 2 1 0 1 0 特征x x10 x9 x8 x7 x6 x5 x4 x3 x2 x1 样本 3.举例：已知有20个2维样本，数据分布如下图： 第4章 近邻法和集群 第一步：令c=2，选初始聚类中心为： 第4章 近邻法和集群 第4章 近邻法和集群 第三步：根据新分成的两类建立新的聚类中心 第四步： ∵ 转第二步。 第二步：重新计算 到m1(2) , m2(2) 的距离，把它们归为最近聚类中心，重新分为两类. * * 近邻法和集群 模式识别 钟珞等编著 武汉大学出版社 2006.9 本章主要内容 4.1 最近邻法 4.2 k近邻法及模糊k近邻分类器 4.3 关于近邻法的讨论 4.4 改进的近邻法 4.5 集群 4.6 本章小结 第4章 近邻法和集群 4.1 最近邻法 近邻法属于有监督学习，是由Cover和Hart于1968年提出来的。 近邻法是在已知模式类别的训练样本的条件下，绕开概率的估计，按最近距离原则对待识别模式直接进行分类。 4.1.1 最近邻法决策准则 将与测试样本最近邻样本的类别作为决策依据的决策方法。 给定c个类别 ，每类有标明类别的样本Ni个样本（i=1,2,…,c），x与?i的最小距离为： 第4章 近邻法和集群 决策规则为： 直观的说，就是对待识别的模式向量x，只要比较x与所有已知类别的样本之间的距离，并决策x与离它最近的样本同类。 第4章 近邻法和集群 4.1.2 最近邻法的错误率分析 定理：最邻近法的渐近平均错误率P满足关系式： 其中P*为Bayes错误率 证明：设N个样本的平均错误率为PN(x)，且样本x的最近邻为x’，则有： 最邻近法的平均错误率为： （1) P的下界 最近邻法属于随机化决策，待分类模式x的近邻随样本集的变化而随机变化。设其最近邻为x’，条件错误率为PN(e|x,x’) 。对于x’取平均得给定x时的条件错误率： 其中x’是x最近邻，在已知x时，x’在x附近的概率最大。 第4章 近邻法和集群 即： 第4章 近邻法和集群 第4章 近邻法和集群 当 时： 当 时 总之，有P*=P （2) P的上界 第4章 近邻法和集群 第4章 近邻法和集群 综上：P*=P=2P* 4.2 K近邻法及模糊K近邻分类器 4.2.1 K近邻法 k—近邻法是近邻法的改进。在x的k个近邻中，按出现最多的样本类别作为x的类别。 设有N个样本，ω1中有N1个，ω2中有N2个，…，ωc中有Nc个;k1,k2,…,kc是k（k=k1+k2+…+kn）个近邻中分别属于ω1，ω2，…，ωc的样本数，定义判别函数为： gi(x)=ki i=1,2,…,c 决策规则： gj(x)=max(ki)→x?ωj 例4.3 在图中有63个训练样 本，分别属于ω1，ω2，ω3 。对于x0,取k＝5,采用欧氏 距离。可将x0归于类别ω0. 第4章 近邻法和集群 4.2.2 K近邻法错误率分析 对k近邻法则，以ω1和ω2二类问题为例，讨论错误率问题。为避免出现不能判决情况，取k＝k1+k2 为奇数。对待识别模式x误分类有以下两种情况： 其中：情况1为x实属于ω1误判为ω2 ；情况2为x实属于ω2误判为ω1，且有P(ω2|x)=1-P(ω1|x)。 第4章 近邻法和集群 对于给定的x，其渐近条件错误率为： 第4章 近邻法和集群 第4章 近邻法和集群 Bayes条件错误率为： P*(e|x)＝min[P(ω1|x),P(ω2|x)]＝min[P(ω1|x),1-P(ω1|x)] 4.2.3 模糊K近邻法分类器 隶属函数：表示一个对象属于某一集合的程度。 在K近邻算法中，得到样本x的k个近邻x1,x2,