ch多类分类器的设计之_第六章_近邻法.pptVIP

第六章 近邻法 最近邻法(The nearest neighbor(NN) rule ) -以与未知样本X最近邻的点的类别作为X的分类. k—近邻法(The k-nearest neighbor(k-NN)rule) -根据未知样本X最近邻的k个样本点中多数点的类别来分类。 6.1 最近邻法(nearest-neighbor) 代表点:将各类的全部样本作为该类的代表点.即: w1类有N1个代表点, w2类有N2个代表点,… 分子类: 每个子类包含1个样本点 定义各子类的判别函数: 定义各类的判别函数: 6.2 k -近邻法The k-nearest neighbor (k-NN) rule 代表点:未知样本x 的 k 个近邻 定义各类的判别函数: 决策规则: 6.3 近邻法的快速算法 基本思想： 将样本集分成多个子集（树状结构）； 每个子集（结点）包含少量样本； 将待识别样本与各结点比较，排除大量候选样本； 只在最后的结点中逐个样本比较，找出最近邻 6.3.1分支定界算法（Branch-Bound Algorithm) 分支定界有哪些信誉好的足球投注网站算法： 6.3.2 剪辑近邻法 错误率分析（渐近分析） 6.3.3 压缩近邻法 6.3.3 压缩近邻法 6.4 可做拒绝决策的近邻法 问题的引入： 由于近邻法决策实际只取决于个别样本，当两类近邻数接近时，因此有时风险较大，可考虑引入拒绝决策。 6.5 为近邻法选择最佳距离度量 小结 * * * * 第i类中各样本与x的最短距离 决策：x与离它最近的样本同类! 按最近法得到的分界面是类别间最近邻点连线的垂直平分超平面的组合。 优缺点分析： –优点：对大多数的线性可分的情况，能达到较好的效果。 –缺点：需要存储所有的样本，并且没有充分利用所有的样本信息，因而受噪声影响较大。 –折衷策略: 1. 利用集群方法 2. k-近邻方法 集群方法: ①根据一定的准则，把一类样本分成子集，利用各个子集的平均样本表示。 ②每类以几个平均样本点代表，使用最近邻法分类。 ③好处：节省存储，减少计算量 第四章的聚类算法就是这个思想，不过聚类算法理论上是无导师的自学习过程。 k-近邻方法: 根据未知样本X最近的k个样本点中多数点的类别来分类。 计算X与所有训练样本的距离，找到最近的k个点，根据如下规则确定X的类别: k-近邻具有较好的噪声免疫性能。但是加权 值相同的假设有些不合理。 k-近邻方法: 根据未知样本x最近的k个样本点中多数点的类别来分类。 计算x与所有训练样本的距离，找到最近的k个点，根据如下规则确定x的类别: k-近邻具有较好的噪声免疫性能。但是加权值相同的假设有些不合理。 最近邻法的错误率分析（渐近分析）: 我们定义最近邻法的渐近平均错误率为P 一般来说最近邻法的错误率落在图中的阴影区域中． 前提： 样本集独立同分布 问题： ①存储量和计算量； ②判决函数接近时风险加大；有噪声时风险加大； ③有限样本下性能如何？ 改进： ①减少存储量和计算量； ②判决函数加权（考虑样本比例、先验概率等）；引入拒绝机制 ③在有限样本下；选择最佳距离度量； 基本算法： 分支定界算法（Branch-Bound Algorithm) 分支定界是一种自上而下的方法，具有回溯功能，通过合理地组织有哪些信誉好的足球投注网站过程，使得可以避免某些计算而不影响结果的最优性，其前提条件为有哪些信誉好的足球投注网站判据(评价方法)的单调性。简单说,就是在遍历有哪些信誉好的足球投注网站树时根据单调性跳开一些计算。 算法分为两个阶段: Ⅰ、聚类－将样本集分解成一些不相交的子集; Ⅱ、有哪些信誉好的足球投注网站－在子集的基础上进行有哪些信誉好的足球投注网站; 第二阶段：有哪些信誉好的足球投注网站x的k个近邻; K－近邻法时只需修正上述6。 引出：处于两类交界处或分布重合区的样本（误导样本）可能误导近邻法决策，应将他们从样本集中去掉 基本思路： 考查样本是否为可能的误导样本（若是，则从样本集中去掉－剪辑）； 考查方法－试分类（认为错分的样本为误导样本）； 基本思路： MULTIEDIT算法应用举例1： 两类正态分布时 图6.5 原始样本集 图6.8 剪辑后留下的样本集 MULTIEDIT算法应用举例2： 两类非正态分布时 图6.9 原始样本集 图6.11 剪辑后留下的样本集 Edit training sets的结果只是去掉两类交界处（重叠处）的样本，而靠近两类中心处的样本大多数对决策面的生成没什么影响，因此，可在Edit的基础上对training sets再进行Condense. 参见： Yingquan Wu, Krassimir Ianakiev, Venu Govindaraju “Improved k-nearest neighbor classification” Pattern Recognition 35 (200