《模式识别复习资料.ppt》由会员分享，可在线阅读，更多相关《模式识别复习资料.ppt（45页珍藏版）》请在金锄头文库上搜索。
1、复习 1 模式和模式识别的概念 1 模式 对某些感兴趣的客体的定量的或结构的描述 模 式类是具有某些共同特性的模式的集合 2 模式识别 研究一种自动技术 依靠这种技术 计算机 将自动地 或人尽量少地干涉 把待别识模式分配到各自 的模式类中去 复习 2 模式识别系统组成 学习过程 判决过程 分类规则训练 分类决策 数据获取 预处理 特征选择 或提取 模式识别系统框图 复习 1 监督分类 需要依靠已知类别的训练样本集 按 照他们特征向量的分布来确定判别函数 然后利用判 别函数对未知模式进行分类 需要足够的先验知识 判别 需要有足够的先验知识 2 非监督分类 用于没有先验知识的情况 通常采 用聚类分
2、析的方法 3 监督分类和无监督分类 复习 4 模式识别整体知识结构 5 最大最小距离算法 小中取大距离算法 算法描述 选任意一模式样本做为第一聚类中心Z1 选择离Z1距离最远的样本作为第二聚类中心Z2 逐个计算各模式样本与已确定的所有聚类中心之间的距离 并选出其中的最小距离 例当聚类中心数k 2时 计算 min Di1 Di2 i 1 N N个最小距离 复习 将样本 按最近距离划分到相应聚类中心对应 的类别中 重复步骤 直到没有新的聚类中心出现为止 在所有最小距离中选出最大距离 如该最大值达到 的一定分数比值 阈值T 以上 则相应的样本点取为新的聚类 中心 返回 否则 寻找聚类中心的工作结束
3、用试探法取为一固定分数 如1 2 则Z3存在 例k 2时 复习 例2 1 对图示模式样本用最大最小距离算法进行聚类分析 选Z1 X1 距Z1最远 选为Z2 计算T 对应最小距离 中的最大值 且 T 选作Z3 结果 Z1 X1 Z2 X6 Z3 X7 用全体模式对三个聚 类中心计算最小距离中 的最大值 无 T 情况 停止寻找中心 聚类 10个最小距离中 X7对 应的距离 T 算法描述 1 N个初始模式样本自成一类 即建立N 类 计算各类之间 即各样本间 的距离 得一N N维距离矩阵D 0 0 表示初始状态 G Group 6 层次聚类法 2 假设已求得距离矩阵D n n为逐次聚类合并的次数 找
4、出D n 中的最小元素 将其对应的两类合并为一类 由此建立 新的分类 3 计算合并后新类别之间的距离 得D n 1 4 跳至第2步 重复计算及合并 复习 结束条件 1 取距离阈值T 当D n 的最小分量超过给定值 T 时 算法停 止 所得即为聚类结果 2 或不设阈值T 一直将全部样本聚成一类为止 输出聚类的分 级树 复习 例 给出6个五维模式样本如下 按最短距离准则进行系统聚类 分类 计算各类间欧氏距离 解 1 将每一样本看作单独一类 得 D D 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 将最小距离 对应的类 和 合并为1类 得 新的分类 计算聚类后的距离矩阵D 1 由D 0
5、 递推出D 1 得距离矩阵D 0 D D 0 0 0 0 0 0 0 0 0 0 0 0 0 0 D D 1 1 0 0 0 0 0 0 0 0 0 0 3 将D 1 中最小值 对应的类合为一类 得D 2 D D 2 2 0 0 0 0 0 0 0 0 4 将D 2 中最小值 对应的类合为一类 得D 3 D D 2 2 0 0 0 0 0 0 0 0 D D 3 3 0 0 0 0 0 0 若给定的阈值为 D 3 中的最小元素 聚类结束 若无阈值 继续分下去 最终全部样本归为一类 可给出聚类 过程的树状表示图 层次聚类法的树状表示 类间距离 阈值增大 分类变粗 7 K 均值算法 算法描述 1
6、任选K个初始聚类中心 Z1 1 Z2 1 ZK 1 2 按最小距离原则将其余样品分配到K个聚类中心中的某一 个 Nj 第j类的样本数 3 计算各个聚类中心的新向量值 4 如果 则回到 2 将模式 样本逐个重新分类 重复迭代计算 算法收敛 计算完毕 如果 复习 例2 3 已知20个模式样本如下 试用K 均值算法分类 解 取K 2 并选 计算距离 聚类 可得到 计算新的聚类中 判断 故返回第 步 从新的聚类中心得 有 计算聚类中心 返回第 步 以Z1 3 Z2 3 为中心进行聚类 以新的聚类中心分类 求得的分类结果与前一次迭代结果相 同 计算新聚类中心向量值 聚类中心与前一次结果相同 即 故算法收
7、敛 得聚类中心为 结果图示 图2 10 K 均值算法聚类结果 X1 X4X3X5 X8 X9 X7 X10 X2 X6 x1 x2 1 3 5 7 9 13 579 0 X11 X12X13X14X15 X16X17X18 X19X20 上述K 均值算法 其类型数目假定已知为K个 当K未知时 可以令K逐渐增加 此时J j 会单调减少 最初减小速度快 但当 K 增加到一定数值时 减小速度会减慢 直到K 总样本数N 时 Jj 0 Jj K关系曲线如下图 8 聚类准则函数Jj与K的关系曲线 Jj A 135 7246 0 8109 K 曲线的拐点 A 对应着接近最优 的K值 J 值减小量 计算量以及
8、 分类效果的权衡 并非所有的情况都容易找到关 系曲线的拐点 迭代自组织的数据 分析算法可以确定模式类的个数K 两分法 1 多类情况1 用线性判别函数将属于 i类的模式与其余不属于 i类的 模式分开 将某个待分类模式 X 分别代入 M 个类的d X 中 若只有di X 0 其他d X 均 0 则判为 i类 识别分类时 9 线性判别函数复习 全部 不属任何类 IR 可能 属于 1 w或 3 w 1 w 2 w 3 w 0 2 Xd 0 3 Xd IR 可能 属于 3 w或 2 w 0 1 Xd 0 0 31 2 dd d 0 0 32 1 dd d 0 0 3 21 d dd IR 可能属于 1
9、w或 2 w 0 0 21 3 dd d 2 x 1 x 对某一模式区 di X 0 的条件超过一个 或全部 的di X 0 分类失效 相当于不确定区 indefinite region IR 此法将 M 个多类问题分成M个两类问题 识别每一类均 需M个判别函数 识别出所有的M类仍是这M个函数 例3 1 设有一个三类问题 其判别式为 现有一模式 X 7 5 T 试判定应属于哪类 并画出三类模式 的分布区域 解 将X 7 5 T代入上三式 有 三个判别界面分别为 图示如下 1 0 1 1 2 x 1 x 0 2 Xd 0 3 Xd 1 0 Xd 4 4 步骤 a 画出界面直线 b 判别界面正负侧
10、 找特殊点带入 c 找交集 感知器算法步骤 1 选择N个分属于 1和 2类的模式样本构成训练样本集 X1 XN 构成增广向量形式 并进行规范化处理 任取权向量初始 值W 1 开始迭代 迭代次数k 1 2 用全部训练样本进行一轮迭代 计算WT k Xi 的值 并修 正权向量 分两种情况 更新权向量的值 9 感知器算法 复习 c 正的校正增量 分类器对第i个模式做了错误分类 权向量校正为 统一写为 分类正确 权向量不变 3 分析分类结果 只要有一个错误分类 回到 2 直至 对所有样本正确分类 分类正确时 对权向量 赏 这里用 不罚 即权向量不变 分类错误时 对权向量 罚 对其修改 向正确的方向转换
11、 感知器算法是一种赏罚过程 例3 8 已知两类训练样本 解 所有样本写成增广向量形式 进行规范化处理 属于 2的样本乘以 1 用感知器算法求出将模式分为两类的权向量解和判别函数 任取W 1 0 取c 1 迭代过程为 第一轮 有两个WT k Xi 0的情况 错判 进行第二轮迭代 第二轮 第三轮 第四轮 该轮迭代的分类结果全部正确 故解向量 相应的判别函数为 当c W 1 取其他值 时 结果可能不一样 所以感知器算法的解不是 单值的 判别界面d X 0如图示 10 最小错误率贝叶斯决策 对两类问题 若 则 若 则 可改写为 统计学中称l12 X 为似然比 为似然比阈值 若 则 4 8 例4 1 假
12、定在细胞识别中 病变细胞的先验概率和正常细胞的 先验概率分别为 现有一待识别细胞 其观察值为X 从类条件概率密度发布曲线上查得 试对细胞X进行分类 解 方法1 通过后验概率计算 方法2 利用先验概率和类概率密度计算 是正常细胞 最小风险贝叶斯决策基本思想 以各种错误分类所造成的平均风险最小为规则 进行分类 决策 11 最小风险贝叶斯决策 2 两类情况 对样本 X 当X 被判为 1类时 当X 被判为 2类时 4 15 4 16 由 4 15 式 决策规则 令 称似然比 为阈值 计算 计算 定义损失函数Lij 判别步骤 类概率密度函 数 p X i 也称 i 的似然函数 解 计算 和 得 例4 2
13、 在细胞识别中 病变细胞和正常细胞的先验概率 分别为 现有一待识别细胞 观察值为X 从类概率密度分布曲线上查得 损失函数分别为L11 0 L21 10 L22 0 L12 1 按最小风险贝 叶斯决策分类 为病变细胞 经过选择或变换 组成识别特征 尽可能保留分类信息 在 保证一定分类精度的前提下 减少特征维数 使分类器的工作即 快又准确 12 特征选择和提取的目的 13 特征选择和特征提取的异同 1 特征选择 从L个度量值集合 中按一定准 则选出供分类用的子集 作为降维 m维 m L 的分类 特征 2 特征提取 使一组度量值 通过某种变换 产生新的m个特征 作为降维的分类特征 其中 复习 14 特征提取的方法 其中 第二步 计算C的特征值 对特征值从小到大进行排队 选择 前m个 第四步 利用A对样本集 X 进行变换 则m维 m n 模式向量X 就是作为分类用的模式向量 解 1 求样本均值向量和协方差矩阵 由 得 由归一化特征向量u1构成变换矩阵A 变换前 变换后 多类类内散布矩阵Sw 15 特征选择 从n个特征中选择d个 d n 最优特征构成分类用特征向量 1 散布矩阵准则 类别可分性测度 类间散布矩阵Sb 多类总体散布矩阵St 特征选择准则 使tr Sw 最小 使tr Sb 最大 使J1 J4最大 复习 例 从5个特征中选出2个特征作为模式向量
