(42)--ch3近邻法模式识别.pdf

《(42)--ch3近邻法模式识别.pdf》由会员分享，可在线阅读，更多相关《(42)--ch3近邻法模式识别.pdf（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、近近邻邻法法原原理理快快速速搜搜索索近近邻邻法法剪剪辑辑近近邻邻法法压压缩缩近近邻邻法法主要内容近近邻邻法法原原理理 模模式式识识别别的的分分类类方方法法分分成成两两类类：（1）将特特征征空空间间划分成决决策策域域 判判别别函函数数（2）模模板板匹匹配配 与标准模板进行比比较较近近邻邻法法原原理理 最最小小距距离离分分类类器器 极极端端情情况况 全全部部训训练练样样本本作作为为标标准准模模板板 测测试试数数据据与与每每一一个个模模板板进进行行比比较较 最最近近邻邻的的模模板板标标签签作作为为分分类类结结果果近近邻邻法法原原理理近近邻邻法法原原理理近近邻邻法法原原理理 k k-近近邻邻法法是最近

2、邻法的扩扩展展方方法法 决策依据：用k k个个最最近近样样本本代替最近邻样本 取k个样本中出出现现最最多多的分类作为决策 k一般采用奇奇数数近近邻邻法法原原理理 近近邻邻法法的的特特点点 优优点点：当模板数量很大时，错错误误率率指指标标较较好好 缺缺点点：计算量大、存储量大近近邻邻法法原原理理 改改进进算算法法 组组织织整整理理样样本本集集：避免每每个个样样本本都需要计算 缩缩小小样样本本集集：不不损损失失性性能能为前提本本节节结结束束近近邻邻法法原原理理快快速速搜搜索索近近邻邻法法剪剪辑辑近近邻邻法法压压缩缩近近邻邻法法主要内容快快速速搜搜索索近近邻邻法法 基基本本思思想想 样样本本集集 分

3、分组组（临近关系）求出每组质质心心 求出组内样本到质心的最最大大距距离离 形成层层次次结结构构 算算法法过过程程 样样本本集集分分解解 搜搜索索规规则则快快速速搜搜索索近近邻邻法法快快速速搜搜索索近近邻邻法法 搜搜索索规规则则 快速排除不不可可能能包含最近邻的子子集集 快速排除子集中不不可可能能为最近邻的样样本本快快速速搜搜索索近近邻邻法法 搜搜索索规规则则快快速速搜搜索索近近邻邻法法快快速速搜搜索索近近邻邻法法快快速速搜搜索索近近邻邻法法 算算法法思思想想 高高层层次次 低低层层次次 同层次多结点：深深度度优优先先 核核对对修修正正快快速速搜搜索索近近邻邻法法 算算法法特特点点 能能够够一一

4、定定程程度度减减少少计计算算量量 不不能能减减少少样样本本集集存存储储量量本本节节结结束束近近邻邻法法原原理理快快速速搜搜索索近近邻邻法法剪剪辑辑近近邻邻法法压压缩缩近近邻邻法法主要内容剪剪辑辑近近邻邻法法 快快速速搜搜索索近近邻邻法法 减减少少计算量 没没减减少少数据存储量剪剪辑辑近近邻邻法法 不同类别的样本在分布上有交交迭迭部部分分 错错误误率率主要来自处于交交迭迭区区剪剪辑辑近近邻邻法法 基基本本思思路路 考考察察样样本本是否可能为误误导导样样本本 若是误误导导样样本本 剪剪辑辑 步骤：试试分分类类 剪剪辑辑模模板板 分分类类剪剪辑辑近近邻邻法法 两两分分剪剪辑辑法法 将训练集划划分分为

5、两个子集，一个为训训练练集集，一个为考考试试集集 利用训练集对考试集的每个样本使用最最近近邻邻法法分分类类 若分类正正确确 保保留留 若分类错错误误 剪剪辑辑剪剪辑辑近近邻邻法法剪剪辑辑近近邻邻法法 多多重重剪剪辑辑法法(MMU UL LT TI IE EDDI IT T)剪剪辑辑近近邻邻法法 减减少少标标准准模模板板的的数数据据存存储储量量 减减少少分分类类过过程程中中的的计计算算量量 改改进进分分类类器器性性能能，降降低低错错误误率率本本节节结结束束近近邻邻法法原原理理快快速速搜搜索索近近邻邻法法剪剪辑辑近近邻邻法法压压缩缩近近邻邻法法主要内容压压缩缩近近邻邻法法 剪剪辑辑近近邻邻法法对对

6、标标准准模模板板数数量量的的压压缩缩效效果果有有限限 靠靠近近类类别别中中心心的的大大量量模模板板被被保保留留 这这些些样样本本对对分分类类决决策策结结果果影影响响很很小小压压缩缩近近邻邻法法 算算法法思思想想：利利用用训训练练样样本本集集生生成成新新样样本本集集 保保留留最最少少量量样样本本，且且维维持持分分类类正正确确 最最大大程程度度保保留留原原训训练练集集的的分分类类特特性性压压缩缩近近邻邻法法 定定义义两两个个存存储储器器：S St to or re eGGr ra ab bb ba ag g（1 1）初初始始化化：S St to or re e为为空空，GGr ra ab bb ba ag g存存储储训训练练集集，从Grabbag中任意选择一样本存入Store（2 2）生生成成样样本本集集：用最近邻法对Grabbag中每一个样本使用Store中的样本集进行分类，若若分分类类错错误误，则移入Store（3 3）终终止止条条件件：若Grabbag中所有样本都可以用Store中的样本集分分类类正正确确，或Grabbag成为空空集集，则算法终止，否则重复（2 2）压压缩缩近近邻邻法法本本节节结结束束