模式识别详细PPT.ppt

1 模式识别 主讲 蔡宣平教授电话 73441 O 73442 H E mail xpcai 单位 电子科学与工程学院信息工程系 2 课程对象 相关学科 教学方法 教学目标 基本要求 教材 参考文献 关于本课程的有关说明 3 课程对象 信息工程专业本科生的专业课 学院硕士研究生的学位课 学院博士研究生的必修课之一 4 相关学科 统计学 概率论 线性代数 矩阵计算 形式语言 人工智能 图像处理 计算机视觉等等 5 教学方法 着重讲述模式识别的基本概念 基本方法和算法原理 注重理论与实践紧密结合实例教学 通过实例讲述如何将所学知识运用到实际应用之中 避免引用过多的 繁琐的数学推导 6 教学目标 掌握模式识别的基本概念和方法 有效地运用所学知识和方法解决实际问题 为研究新的模式识别的理论和方法打下基础 7 基本要求 基本 完成课程学习 通过考试 获得学分 提高 能够将所学知识和内容用于课题研究 解决实际问题 飞跃 通过模式识别的学习 改进思维方式 为将来的工作打好基础 终身受益 8 教材 参考文献 孙即祥 现代模式识别 国防科技大学出版社 2003年 吴逸飞译 模式识别 原理 方法及应用 清华大学出版社 2003年 李晶皎等译 模式识别 第三版 电子工业出版社 2006年 9 讲授课程内容及安排 第一章引论第二章聚类分析第三章判别域代数界面方程法第四章统计判决第五章学习 训练与错误率估计第六章最近邻方法第七章特征提取和选择上机实习 10 第一章引论 1 1概述1 2特征矢量和特征空间1 3随机矢量的描述1 4正态分布 概念 模式识别 PatternRecognition 确定一个样本的类别属性 模式类 的过程 即把某一样本归属于多个类型中的某个类型 样本 Sample 一个具体的研究 客观 对象 如患者 某人写的一个汉字 一幅图片等 模式 Pattern 对客体 研究对象 特征的描述 定量的或结构的描述 是取自客观世界的某一样本的测量值的集合 或综合 特征 Features 能描述模式特性的量 测量值 在统计模式识别方法中 通常用一个矢量表示 称之为特征矢量 记为 模式类 Class 具有某些共同特性的模式的集合 概念 模式识别的例子 计算机自动诊断疾病 获取情况 信息采集 测量体温 血压 心率 血液化验 X光透射 B超 心电图 CT等尽可能多的信息 并将这些信息数字化后输入电脑 当然在实际应用中要考虑采集的成本 这就是说特征要进行选择的 运行在电脑中的专家系统或专用程序可以分析这些数据并进行分类 得出正常或不正常的判断 不正常情况还要指出是什么问题 14 各类空间 Space 的概念 模式采集 从客观世界 对象空间 到模式空间的过程称为模式采集 特征提取和特征选择 由模式空间到特征空间的变换和选择 类型判别 特征空间到类型空间所作的操作 模式识别三大任务 15 1 1概述 模式识别系统 通常在采集信息过程中 还要去除所获取信息中的噪声 增强有用的信息等工作 这种使信息纯化的处理过程叫做信息的预处理 分类识别是根据事先确定的分类规则对前面选取的特征进行分类 即识别 通常能描述对象的元素很多 为节约资源和提高处理速度 有时更为了可行性 在满足分类识别正确率要求的条件下 按某种准则尽量选用对正确分类识别作用较大的特征 使得用较少的特征就能完成分类识别任务 预处理这个环节的内容很广泛 与要解决的具体问题有关 例如 从图象中将汽车车牌的号码识别出来 就需要先将车牌从图像中找出来 再对车牌进行划分 将每个数字分别划分开 做到这一步以后 才能对每个数字进行识别 以上工作都应该在预处理阶段完成 数字化 比特流 16 1 1概述 模式识别系统 17 1 1概述 模式识别系统 模式识别系统的主要环节 特征提取 符号表示 如长度 波形 特征选择 选择有代表性的特征 能够正确分类学习和训练 利用已知样本建立分类和识别规则分类识别 对所获得样本按建立的分类规则进行分类识别 18 纸币识别器对纸币按面额进行分类面额 1 1概述 系统实例 5元10元20元50元100元 19 1 1概述 系统实例 长度 mm 宽度 mm 5元1366310元1417020元1467050元15170100元15677 20 1 1概述 系统实例 磁性金属条位置 大约 5元有54 8210元有54 8720元有57 8950元有60 91100元有63 93 5元10元20元50元100元 12345678 反射光波形 22 1 1概述 系统实例 数据采集 特征提取 长度 宽度 磁性 磁性的位置 光反射亮度 光透射亮度等等 特征选择 长度 磁性及位置 反射亮度 分类识别 确定纸币的面额及真伪 23 1 1概述 系统实例 训练集 是一个已知样本集 在监督学习方法中 用它来开发出模式分类器 测试集 在设计识别和分类系统时没有用过的独立样本集 系统评价原则 为了更好地对模式识别系统性能进行评价 必须使用一组独立于训练集的测试集对系统进行测试 24 例 汽车车牌识别 从摄像头获取包含车牌的彩色图象车牌定位和获取字符分割和识别 25 26 27 1 1概述 模式识别的基本方法 一 统计模式识别二 句法模式识别三 模糊模式识别四 人工神经网络法五 人工智能方法 28 1 1概述 模式识别的基本方法 一 统计模式识别 模式描述方法 特征向量模式判定 模式类用条件概率分布P X i 表示 m类就有m个分布 然后判定未知模式属于哪一个分布 29 1 1概述 模式识别的基本方法 一 统计模式识别 理论基础 概率论 数理统计主要方法 线性 非线性分类 Bayes决策 聚类分析主要优点 1 比较成熟2 能考虑干扰噪声等影响3 识别模式基元能力强主要缺点 1 对结构复杂的模式抽取特征困难2 不能反映模式的结构特征 难以描述模式的性质3 难以从整体角度考虑识别问题 30 1 1概述 模式识别的基本方法 二 句法模式识别 模式描述方法 符号串 树 图模式判定 是一种语言 用一个文法表示一个类 m类就有m个文法 然后判定未知模式遵循哪一个文法 31 例2 如下图中一幅图形 要识别图中的物体 选用句法模式识别方法 1 1概述 模式识别的基本方法 32 解 图形结构复杂 首先应分解为简单的子图 背景 物体 构成一个多级树结构 1 1概述 模式识别的基本方法 33 在学习过程中 确定基元与基元之间的关系 推断出生成景物的方法 判决过程中 首先提取基元 识别基元之间的连接关系 使用推断的文法规则做句法分析 若分析成立 则判断输入的景物属于相应的类型 1 1概述 模式识别的基本方法 34 理论基础 形式语言 自动机技术主要方法 自动机技术 CYK剖析算法 Early算法 转移图法主要优点 1 识别方便 可以从简单的基元开始 由简至繁 2 能反映模式的结构特征 能描述模式的性质 3 对图象畸变的抗干扰能力较强 主要缺点 当存在干扰及噪声时 抽取特征基元困难 且易失误 1 1概述 模式识别的基本方法 35 1 1概述 模式识别的基本方法 三 模糊模式识别 模式描述方法 模糊集合A a a b b n n 模式判定 是一种集合运算 用隶属度将模糊集合划分为若干子集 m类就有m个子集 然后根据择近原则分类 36 理论基础 模糊数学主要方法 模糊统计法 二元对比排序法 推理法 模糊集运算规则 模糊矩阵主要优点 由于隶属度函数作为样本与模板间相似程度的度量 故往往能反映整体的与主体的特征 从而允许样本有相当程度的干扰与畸变 主要缺点 准确合理的隶属度函数往往难以建立 故限制了它的应用 1 1概述 模式识别的基本方法 37 1 1概述 模式识别的基本方法 四 人工神经网络法 模式描述方法 以不同活跃度表示的输入节点集 神经元 模式判定 是一个非线性动态系统 通过对样本的学习建立起记忆 然后将未知模式判决为其最接近的记忆 38 理论基础 神经生理学 心理学主要方法 BP模型 HOP模型 高阶网主要优点 可处理一些环境信息十分复杂 背景知识不清楚 推理规则不明确的问题 允许样本有较大的缺损 畸变 主要缺点 模型在不断丰富与完善中 目前能识别的模式类还不够多 1 1概述 模式识别的基本方法 39 1 1概述 模式识别的基本方法 五 逻辑推理法 人工智能法 模式描述方法 字符串表示的事实模式判定 是一种布尔运算 从事实出发运用一系列规则 推理得到不同结果 m个类就有m个结果 40 理论基础 演绎逻辑 布尔代数主要方法 产生式推理 语义网推理 框架推理主要优点 已建立了关于知识表示及组织 目标搜索及匹配的完整体系 对需要众多规则的推理达到识别目标确认的问题 有很好的效果 主要缺点 当样本有缺损 背景不清晰 规则不明确甚至有歧义时 效果不好 1 1概述 模式识别的基本方法 41 1 1概述 模式识别的发展简史 1929年G Tauschek发明阅读机 能够阅读0 9的数字 30年代Fisher提出统计分类理论 奠定了统计模式识别的基础 50年代NoamChemsky提出形式语言理论 傅京荪提出句法 结构模式识别 60年代L A Zadeh提出了模糊集理论 模糊模式识别方法得以发展和应用 42 1 1概述 模式识别的发展简史 80年代以Hopfield网 BP网为代表的神经网络模型导致人工神经元网络复活 并在模式识别得到较广泛的应用 90年代小样本学习理论 支持向量机也受到了很大的重视 43 1 1概述 模式识别的应用 举例 生物学自动细胞学 染色体特性研究 遗传研究天文学天文望远镜图像分析 自动光谱学经济学股票交易预测 企业行为分析医学心电图分析 脑电图分析 医学图像分析 44 1 1概述 主要实用系统举例 文字识别 CharacterRecognition OCR OpticalCharacterRecognition 智能交通 IntelligentTraffic 车牌 车型 语音识别 Speechrecognition 翻译机 身份识别等目标识别ATR AutomaicTargetRecognition 45 46 1 2特征矢量和特征空间 47 1 3随机矢量的描述 随机矢量 在模式识别过程中 要对许多具体对象进行测量 以获得许多次观测值 每次观测值不一定相同 所以对许多对象而言 各个特征分量都是随机变量 即许多对象的特征向量在n维空间中呈随机性分布 称为随机矢量 48 1 3随机矢量的描述 一 随机矢量的分布函数 设为随机矢量 为确定性矢量 随机矢量的联合概率分布函数定义为 式中表示括号中事件同时发生的概率 49 1 3随机矢量的描述 一 随机矢量的分布函数 随机矢量的联合概率密度函数定义为 50 1 3随机矢量的描述 51 1 3随机矢量的描述 x p x 52 1 3随机矢量的描述 53 1 3随机矢量的描述 二 随机矢量的数字特征 其中 的分量 式中 是的第个分量的边缘密度 随机矢量的均值矢量的各分量是相应的各随机分量的均值 54 1 3随机矢量的描述 二 随机矢量的数字特征 条件期望在模式识别中 经常以类别作为条件 在这种情况下随机矢量的条件期望矢量定义为 55 1 3随机矢量的描述 随机矢量的自协方差矩阵表征各分量围绕其均值的散布情况及各分量间的相关关系 其定义为 二 随机矢量的数字特征 协方差矩阵 56 1 3随机矢量的描述 57 1 3随机矢量的描述 58 1 3随机矢量的描述 二 随机矢量的数字特征 相关系数 由布尼亚科夫斯基不等式知 相关系数矩阵定义为 59 1 3随机矢量的描述 60 1 3随机矢量的描述 61 1 3随机矢量的描述 62 1 3随机矢量的描述 63 1 4正态分布 64 1 4正态分布 1 一维随机变量的正态分布 65 1 4正态分布 66 1 4正态分布 2 随机矢量的正态分布 正态分布随机矢量的概率密度函数定义为 67 1 4正态分布 68 1 4正态分布 2 二维随机变量的正态分布 69 1 4正态分布 范例木板图象512 512d 3长度纹理亮度c 2松木 桦木 维数无限有限 很大R有限d不大c 总结 模式识别过程 d R 无限 71 试证明 对于正态分布 不相关与独立是等价的 试证明 多元正态随机矢量的线性变换仍为多元正态随机矢量 试证明 多元正态随机矢量X的分量的线性组合是一正态随机变量 习题 72 模式识别 主讲 蔡宣平教授电话 73441 O 73442 H E mail xpcai 单位 电子科学与工程学院信息工程系 73 第二章聚类分析 ClusteringAnalysis 2 1聚类分析的概念2 2模式相似性测度2 3类的定义与类间距离2 4聚类的算法 74 2 1聚类分析的概念 一 聚类分析的基本思想 相似的归为一类 模式相似性的度量和聚类算法 无监督分类 Unsupervised 二 特征量的类型 物理量 重量 长度 速度 次序量 等级 技能 学识 名义量 性别 状态 种类 第二章聚类分析 75 三 方法的有效性取决于分类算法和特征点分布情况的匹配 2 1聚类分析的概念 分类无效时的情况1 特征选取不当使分类无效 第二章聚类分析 76 三 方法的有效性取决于分类算法和特征点分布情况的匹配 2 1聚类分析的概念 分类无效时的情况2 特征选取不足可能使不同类别的模式判为一类 第二章聚类分析 77 三 方法的有效性取决于分类算法和特征点分布情况的匹配 2 1聚类分析的概念 分类无效时的情况3 特征选取过多可能无益反而有害 增加分析负担并使分析效果变差 第二章聚类分析 78 三 方法的有效性取决于分类算法和特征点分布情况的匹配 2 1聚类分析的概念 分类无效时的情况4 量纲选取不当 第二章聚类分析 79 三 方法的有效性取决于分类算法和特征点分布情况的匹配 2 1聚类分析的概念 分类无效时的情况4 量纲选取不当 第二章聚类分析 80 三 方法的有效性取决于分类算法和特征点分布情况的匹配 2 1聚类分析的概念 分类无效时的情况4 量纲选取不当 第二章聚类分析 81 下列是一些动物的名称 羊 sheep 狗 dog 蓝鲨 blueshark 蜥蜴 lizard 毒蛇 viper 猫 cat 麻雀 sparrow 海鸥 seagull 金鱼 goldfish 绯鲵鲣 red mullet 蛙 frog 要对这些动物进行分类 则不同的特征有不同的分法 特征选取不同对聚类结果的影响 第二章聚类分析 82 特征选取不同对聚类结果的影响 羊 狗 猫蓝鲨 蜥蜴 毒蛇 麻雀 海鸥 金鱼 绯鲵鲣 青蛙 a 按繁衍后代的方式分 哺乳动物 非哺乳动物 第二章聚类分析 83 金鱼绯鲵鲣蓝鲨 羊 狗 猫蜥蜴 毒蛇麻雀 海鸥青蛙 b 按肺是否存在分 无肺 有肺 特征选取不同对聚类结果的影响 第二章聚类分析 84 青蛙 羊 狗 猫蜥蜴 毒蛇麻雀 海鸥 金鱼绯鲵鲣蓝鲨 c 按生活环境分 陆地 水里 两栖 特征选取不同对聚类结果的影响 第二章聚类分析 85 蓝鲨 金鱼绯鲵鲣 蜥蜴 毒蛇麻雀 海鸥青蛙 羊 狗 猫 d 按繁衍后代方式和肺是否存在分 非哺乳且有肺 哺乳且无肺 哺乳且有肺 非哺乳且无肺 特征选取不同对聚类结果的影响 第二章聚类分析 86 距离测度不同 聚类结果也不同 数据的粗聚类是两类 细聚类为4类 第二章聚类分析 87 综上可见 选择什么特征 选择多少个特征 选择什么样的量纲 选择什么样的距离测度 这些对分类结果都会产生极大影响 第二章聚类分析 88 聚类过程遵循的基本步骤 一 特征选择 featureselection 尽可能多地包含任务关心的信息 二 近邻测度 proximitymeasure 定量测定两特征如何 相似 或 不相似 三 聚类准则 clusteringcriterion 以蕴涵在数据集中类的类型为基础 四 聚类算法 clusteringalgorithm 按近邻测度和聚类准则揭示数据集的聚类结构 五 结果验证 validationoftheresults 常用逼近检验验证聚类结果的正确性 六 结果判定 interpretationoftheresults 由专家用其他方法判定结果的正确性 89 聚类应用的四个基本方向 一 减少数据许多时候 当数据量N很大时 会使数据处理变得很费力 因此可使用聚类分析的方法将数据分成几组可判断的聚类m m N 来处理 每一个类可当作独立实体来对待 从这个角度看 数据被压缩了 第二章聚类分析 90 二 假说生成在这种情况下 为了推导出数据性质的一些假说 对数据集进行聚类分析 因此 这里使用聚类作为建立假说的方法 然后用其他数据集验证这些假说 聚类应用的四个基本方向 第二章聚类分析 91 聚类应用的四个基本方向 三 假说检验用聚类分析来验证指定假说的有效性 例如 考虑这样的假说 大公司在海外投资 要验证这个假说是否正确 就要对大公司和有代表性的公司按规模 海外活跃度 成功完成项目的能力等进行聚类分析 从而来支持这个假说 第二章聚类分析 92 四 基于分组的预测对现有数据进行聚类分析 形成模式的特征 并用特征表示聚类 接下来 对于一个未知模式 就可以用前面的聚类来确定是哪一类 聚类应用的四个基本方向 例如 考虑被同种疾病感染的病人数据集 先按聚类分析进行分类 然后对新的病人确定他适合的聚类 从而判断他病情 第二章聚类分析 93 2 2模式相似性测度 用于描述各模式之间特征的相似程度 距离测度 相似测度 匹配测度 第二章聚类分析 94 2 2模式相似性测度 一 距离测度 差值测度 测度基础 两个矢量矢端的距离测度数值 两矢量各相应分量之差的函数 第二章聚类分析 95 2 2模式相似性测度 常用的距离测度有 1 欧氏 Euclidean 距离 第二章聚类分析 96 2 2模式相似性测度 4 明氏 Minkowski 距离 2 2 4 2 绝对值距离 街坊距离或Manhattan距离 2 2 2 3 切氏 Chebyshev 距离 2 2 3 第二章聚类分析 97 2 2模式相似性测度 第二章聚类分析 98 2 2模式相似性测度 5 马氏 Mahalanobis 距离 注意 马氏距离对一切非奇异线性变换都是不变的 这说明它不受特征量纲选择的影响 并且是平移不变的 上面的V的含义是这个矢量集的协方差阵的统计量 故马氏距离加入了对特征的相关性的考虑 第二章聚类分析 99 2 2模式相似性测度 第二章聚类分析 100 101 现金识别例子 欧氏平均距离 数据样本介绍 10个文本文件文件名 rmb00 txt rmb09 txt每个文件有4个币种的数据 分别是 100圆 50圆 20圆 10圆每个币种有新旧两种版本 4个方向 故有8个数据块 如100圆的8个数据块 data100a data100b data100c data100d 老版data100e data100f data100g data100h 新版每个数据块有8个传感器数据 传感器1 传感器2 传感器8每个传感器有60个采样数据 数据1 数据2 数据60 102 现金识别例子 Eucliden 15 000000Manhattan 33 000000Chebyshev 11 000000Minkowski 11 039449 m 8 100元A面第1个样本第10点和20点的距离X 75 76 101 83 102 96 91 82 Y 70 74 90 76 99 96 90 86 X Y 5 2 11 7 3 0 1 4 距离测度rmbdis 103 现金识别例子 欧式平均距离 100a 100a 2 65 49 66 24 41100a 100b 16 37 55 87 33 97100a 100c 3 87 58 34 29 41100a 100d 6 86 53 74 33 04100a 100e 3 87 62 12 27 51100a 100f 13 60 67 61 34 67100a 100g 11 40 68 56 32 27100a 100h 11 27 68 61 34 43100a 50a 18 76 76 20 40 72100a 20a 13 23 81 28 42 87100a 10a 12 45 90 91 54 99 104 现金识别例子 100圆A面的马式矩阵SW为 43 553 964 852 752 752 346 837 953 9132 0137 5107 859 674 052 131 564 8137 5165 9124 174 684 167 637 152 7107 8124 1105 557 567 254 535 252 759 674 657 576 271 765 857 952 374 084 167 271 773 162 855 046 852 167 654 565 862 859 651 937 931 537 135 257 955 051 954 7 105 现金识别例子 SW的逆矩阵为 0 3 0 00 1 0 1 0 1 0 1 0 20 2 0 00 3 0 1 0 10 1 0 60 30 20 1 0 10 3 0 1 0 0 0 2 0 30 4 0 1 0 1 0 10 20 10 3 0 1 0 2 0 10 1 0 00 10 7 0 7 0 40 2 0 1 0 6 0 20 3 0 72 2 0 0 1 0 0 20 3 0 3 0 1 0 4 0 01 2 0 50 20 20 4 0 20 2 1 0 0 51 0 106 现金识别例子 马式平均距离 100a 7 46 80 05 39 73100b 26 75 179 86 91 89100c 14 50 231 44 103 76100d 11 69 155 28 78 58100e 5 65 2968 84 247 42100f 39 19 2191 91 108 10100g 10 68 2875 99 265 16100h 9 41 2673 54 107 5650a 22 78 221 07 101 4120a 22 51 343 26 162 9010a 20 93 975 67 256 38 107 现金识别例子 马式平均距离 a 39 73101 41162 90256 38b 91 89230 25288 69659 47c 103 76135 94257 57724 96d 78 58171 10330 97675 90e 247 42443 46333 93218 71f 108 10328 11305 19607 51g 265 16956 58818 83348 42h 107 56339 64387 10628 88 100圆50圆20圆10圆 其中马式矩阵为100圆A面的 上面是各面到100圆A面的均值点的平均马式距离 108 现金识别例子 100圆A面的传感器1到其它各面传感器1的街坊距离 109 2 2模式相似性测度 二 相似测度测度基础 以两矢量的方向是否相近作为考虑的基础 矢量长度并不不重要 设 1 角度相似系数 夹角余弦 2 2 11 注意 坐标系的旋转和尺度的缩放是不变的 但对一般的线形变换和坐标系的平移不具有不变性 110 现金识别例子 100圆A面传感器1与其它各面的相似系数 111 2 2模式相似性测度 二 相似测度2 相关系数它实际上是数据中心化后的矢量夹角余弦 2 2 12 112 现金识别例子 100圆A面传感器1与其它各面的相关系数 113 2 2模式相似性测度 二 相似测度3 指数相似系数 2 2 13 式中为相应分量的协方差 为矢量维数 它不受量纲变化的影响 114 现金识别例子 100圆A面传感器1与其它各面的相关系数 115 2 2模式相似性测度 当特征只有两个状态 0 1 时 常用匹配测度 0表示无此特征1表示有此特征 故称之为二值特征 对于给定的x和y中的某两个相应分量xi与yj若xi 1 yj 1 则称xi与yj是 1 1 匹配 若xi 1 yj 0 则称xi与yj是 1 0 匹配 若xi 0 yj 1 则称xi与yj是 0 1 匹配 若xi 0 yj 0 则称xi与yj是 0 0 匹配 二 匹配测度 116 2 2模式相似性测度 117 2 2模式相似性测度 三 匹配测度 1 Tanimoto测度 118 例2 2 2 可以看出 它等于共同具有的特征数目与分别具有的特征种类总数之比 这里只考虑 1 1 匹配而不考虑 0 0 匹配 设 则 2 2模式相似性测度 119 现金识别例子 100圆A面与其它各面的匹配系数Tanimoto 120 2 2模式相似性测度 三 匹配测度 2 Rao测度 注 1 1 匹配特征数目和所选用的特征数目之比 121 现金识别例子 100圆A面与其它各面的匹配系数Rao 122 2 2模式相似性测度 三 匹配测度 3 简单匹配系数 注 上式分子为 1 1 匹配特征数目与 0 0 匹配特征数目之和 分母为所考虑的特征数目 123 现金识别例子 100圆A面与其它各面的匹配系数Simple 124 2 2模式相似性测度 三 匹配测度 4 Dice系数 5 Kulzinsky系数 125 现金识别例子 100圆A面与其它各面的匹配系数dice 126 现金识别例子 100圆A面与其它各面的匹配系数Kulzinsky 127 作业 P44 2 1 2 3 128 2 3类的定义与类间距离 2 3 1类的定义 定义之1设集合S中任意元素xi与yj间的距离dij有dij h其中h为给定的阀值 称S对于阀值h组成一类 类的定义有很多种 类的划分具有人为规定性 这反映在定义的选取及参数的选择上 一个分类结果的优劣最后只能根据实际来评价 书中的其它定义方法请大家自行参考学习 129 2 3类的定义与类间距离 2 3 2类间距离测度方法 最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法 130 2 3类的定义与类间距离 2 3 2类间距离测度方法 最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法 131 现金识别例子 100圆A面与其它各面的最小距离 132 2 3类的定义与类间距离 2 3 2类间距离测度方法 最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法 133 现金识别例子 100圆A面与其它各面的最大距离 134 2 3类的定义与类间距离 2 3 2类间距离测度方法 最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法 p q k 135 2 3类的定义与类间距离 2 3 2类间距离测度方法 最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法 np nq分别为类wp和wq的样本个数 136 2 3类的定义与类间距离 2 3 2类间距离测度方法 最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法 137 现金识别例子 100圆A面与其它各面的平均距离 138 2 3类的定义与类间距离 2 3 2类间距离测度方法 最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法 分别为对应类的重心 类内离差平方和 递推公式为 139 140 2 3类的定义与类间距离 2 3 3聚类的准则函数 判别分类结果好坏的一般标准 类内距离小 类间距离大 某些算法需要一个能对分类过程或分类结果的优劣进行评估的准则函数 如果聚类准则函数选择得好 聚类质量就会高 聚类准则往往是和类的定义有关的 是类的定义的某种体现 141 2 3 3聚类的准则函数 一 类内距离准则设有待分类的模式集在某种相似性测度基础上被划分为类 类内距离准则函数定义为 表示类的模式均值矢量 2 3 20 2 3类的定义与类间距离 142 2 3类的定义与类间距离 143 加权类内距离准则 2 3 22 2 3 23 144 2 3类的定义与类间距离 145 加权类间距离准则 2 3 25 146 2 3类的定义与类间距离 147 的类内离差阵定义为 2 3 28 2 3类的定义与类间距离 式中为类的模式均值矢量 2 3 29 148 149 例2 3 1证明 2 3类的定义与类间距离 150 聚类的基本目的是使或 利用线形代数有关矩阵的迹和行列式的性质 可以定义如下4个聚类的准则函数 2 3类的定义与类间距离 151 2 3类的定义与类间距离 由它们的构造可以看出 为得到好的聚类结果 应该使它们尽量的大 这类准则也大量用在特征提取和选择中 152 2 3类的定义与类间距离 J1 7 60886J2 0 0010397J3 15 6089J4 62 9116 用纸币数据计算获得的结果 153 作业 P44 2 4 2 5 2 6 154 2 4聚类的算法 2 4 1聚类的技术方案 聚类分析有很多具体的算法 有的比较简单 有的相对复杂和完善 但归纳起来就是三大类 1 按最小距离原则简单聚类方法2 按最小距离原则进行两类合并的方法3 依据准则函数动态聚类方法 155 2 4聚类的算法 1 简单聚类方法 针对具体问题确定相似性阈值 将模式到各聚类中心间的距离与阈值比较 当大于阈值时该模式就作为另一类的类心 小于阈值时按最小距离原则将其分划到某一类中 这类算法运行中模式的类别及类的中心一旦确定将不会改变 156 2 4聚类的算法 首先视各模式自成一类 然后将距离最小的两类合并成一类 不断地重复这个过程 直到成为两类为止 2 按最小距离原则进行两类合并的方法 这类算法运行中 类心不断地修正 但模式类别一旦指定后就不再改变 就是模式一旦划为一类后就不再被分划开 这类算法也称为谱系聚类法 157 2 4聚类的算法 3 依据准则函数动态聚类法 设定一些分类的控制参数 定义一个能表征聚类结果优劣的准则函数 聚类过程就是使准则函数取极值的优化过程 算法运行中 类心不断地修正 各模式的类别的指定也不断地更改 这类方法有 C均值法 ISODATA法等 158 2 4聚类的算法 简单聚类方法 159 2 4聚类的算法 简单聚类方法 160 2 4聚类的算法 简单聚类方法 161 2 4聚类的算法 简单聚类方法 这类算法的突出优点是算法简单 但聚类过程中 类的中心一旦确定将不会改变 模式一旦指定类后也不再改变 算法特点 从算法的过程可以看出 该算法结果很大程度上依赖于距离门限T的选取及模式参与分类的次序 如果能有先验知识指导门限T的选取 通常可获得较合理的效果 也可考虑设置不同的T和选择不同的次序 最后选择较好的结果进行比较 162 2 4聚类的算法 简单聚类方法 简单聚类图例 163 例2 4 1 初始条件不同的简单聚类结果 初始中心不同 12345 12345 12345 12345 1098 1098 876 876 1167 1167 91011 91011 164 2 4聚类的算法 简单聚类法程序 simpleclustering 165 2 4聚类的算法 最大最小距离法 166 2 4聚类的算法 最大最小距离法 算法原理步骤 167 计算未被作为聚类中心的各模式特征矢量 与 之间的距离 并求出它们之中的最小值 为表述简洁 虽然某些模式已选做聚类中心 但上面仍将所有模式下角标全部列写出来 因这并不影响算法的正确性 即 168 169 170 2 4聚类的算法 最大最小距离法程序 maxminclustering 171 2 4聚类的算法 层次聚类法 HierarchicalClusteringMethod 系统聚类法 谱系聚类法 按最小距离原则不断进行两类合并 2 4 3谱系聚类法 172 2 4聚类的算法 层次聚类法 HierarchicalClusteringMethod 系统聚类法 谱系聚类法 按最小距离原则不断进行两类合并 算法思想首先将N个模式视作各自成为一类 然后计算类与类之间的距离 选择距离最小的一对合并成一个新类 计算在新的类别分划下各类之间的距离 再将距离最近的两类合并 直至所有模式聚成两类为止 2 4 3谱系聚类法 173 2 4聚类的算法 2 4 3谱系聚类法 174 2 4聚类的算法 2 4 3谱系聚类法 175 例2 4 3 如下图所示1 设全部样本分为6类 2 作距离矩阵D 0 3 求最小元素 4 把 1 3合并 7 1 3 4 6合并 8 4 6 5 作距离矩阵D 1 D 0 176 例2 4 3 如下图所示1 设全部样本分为6类 2 作距离矩阵D 0 3 求最小元素 4 把 1 3合并 7 1 3 4 6合并 8 4 6 5 作距离矩阵D 1 D 1 177 6 若合并的类数没有达到要求 转3 否则停止 3 求最小元素 4 8 5 2合并 9 2 5 4 6 178 179 2 4聚类的算法 谱系聚类法程序 Hierarchicalclustering 180 2 4聚类的算法 最大距离和层次聚类算法的一个共同特点是某个模式一旦划分到某一类之后 在后继的算法过程中就不改变了 而简单聚类算法中类心一旦选定后在后继算法过程中也不再改变了 因此 这些方法效果一般不会太理想 181 2 确定评估聚类质量的准则函数 3 确定模式分划及聚类合并或分裂的规则 2 4聚类的算法 动态聚类算法要点 182 2 4聚类的算法 动态聚类的基本步骤 建立初始聚类中心 进行初始聚类 计算模式和类的距离 调整模式的类别 计算各聚类的参数 删除 合并或分裂一些聚类 从初始聚类开始 运用迭代算法动态地改变模式的类别和聚类的中心使准则函数取得极值或设定的参数达到设计要求时停止 183 2 4聚类的算法 动态聚类的框图 产生初始聚类中心 聚类 检验聚类合理性 待分类模式 184 条件及约定设待分类的模式特征矢量集为 类的数目C是事先取定的 2 4聚类的算法 2 4 3动态聚类法 C 均值法 算法思想该方法取定C个类别和选取C个初始聚类中心 按最小距离原则将各模式分配到C类中的某一类 之后不断地计算类心和调整各模式的类别 最终使各模式到其判属类别中心的距离平方之和最小 185 2 4聚类的算法 2 4 3动态聚类法 C 均值法 186 2 4聚类的算法 2 4 3动态聚类法 C 均值法 187 选代表点 4 动态聚类框图 2 4聚类的算法 2 4 3动态聚类法 C 均值法 188 例2 4 2使用聚类算法实现图像分割 在散射图上形成了两个聚类 利用模式识别的方法将其分开 就实现了图象的分割 189 例2 4 3 已知有20个样本 每个样本有2个特征 数据分布如下图 使用C 均值法实现样本分类 C 2 第一步 令C 2 选初始聚类中心为 190 191 0 0 第二步 192 193 194 195 第三步 更新聚类中心 196 197 第四步 第二步 第三步 更新聚类中心 198 199 clustering 2 4聚类的算法 2 4 3动态聚类法 C 均值法程序 200 作业 P45 2 7 2 8 201 2 4聚类的算法 2 4 3动态聚类法 C 均值法 关于C 均值法收敛性的分析 202 2 4聚类的算法 2 4 3动态聚类法 C 均值法 当模式分布呈现类内团聚状 C 均值算法是能达到很好的聚类结果 故应用较多 从算法的迭代过程看 C 均值算法是能使各模式到其所判属的类别中心距离 平方 之和为最小的最佳聚类 203 2 4聚类的算法 2 4 3动态聚类法 C 均值法的改进 在类别数未知的情况下 可使类数C由较小值逐步增加 对于每个选定的C分别使用该算法 显然准则函数J是随C的增加而单调减少 C的调整作一条C一J曲线 其曲率变化的最大点对应的类数是比较接近最优的类数 在增加过程中 总会出现使本来较密集的类再拆开的情况 此时J虽减小 但减小速度将变缓 如果作一条C一J曲线 其曲率变化的最大点对应的类数是比较接近最优的类数 然而在许多情况下 曲线并无明显的这样的点 204 2 4聚类的算法 2 4 3动态聚类法 C 均值法的改进 初始聚类中心的选取 凭经验选择初始类心 将模式随机地分成C类 计算每类中心 以其作为初始类心 最大密度 求以每个特征点为球心 某一正数d0为半径的球形域中特征点个数 这个数称为该点的密度 选取密度最大的特征点作为第一个初始类心Z1 然后在与Z1大于某个距离d的那些特征点中选取具有 最大 密度的特征点作为第二个初始类心Z2 如此进行 选取C个初始聚类中心 205 2 4聚类的算法 2 4 3动态聚类法 C 均值法的改进 初始聚类中心的选取 用相距最远的C个特征点作为初始类心 具体地讲 是按前述的最大最小距离算法求取C个初始聚类中心 当N较大时 先随机地从N个模式中取出一部分模式用谱系聚类法聚成C类 以每类的重心作为初始类心 设已标准化的待分类模式集为希望将它们分为C类 206 设已标准化的待分类模式集为希望将它们分为C类 设 计算 显然0 ai C 若ai最接近整数j 则把xi分划至中wj 对所有样本都实行上述处理 就可实现初始分类 从而产生初始聚类中心 207 2 4聚类的算法 2 4 3动态聚类法 C 均值法的改进 用类核代替类心 前面的算法存在一个不足 即只用一个聚类中心点作为一类的代表 但一个点往往不能充分地反映该类的模式分布结构 从而损失了很多有用的信息 当类的分布不是球状或近似球状时 这种算法很难有较好的效果 此时 可用类核代替类心 类核可以是一个函数 一个点集或其他适当的模型 比如前面我们讲过的马式距离 208 3 动态聚类法 ISODATA算法 IterativeSelf OrganizingDataAnalysisTechniquesAlgorithm迭代自组织数据分析 特点 启发性推理 分析监督 控制聚类结构及人机交互 算法思想 在每轮迭代过程中 样本重新调整类别之后计算类内及类间有关参数 并和设定的门限比较 确定是两类合并为一类还是一类分裂为两类 不断地 自组织 以达到在各参数满足设计要求条件下 使各模式到其类心的距离平方和最小 209 ISODATA算法原理步骤 预置 设定聚类分析控制参数 预期的类数 每一类中允许的最少模式数目 初始聚类中心个数 可以不等于c 类内各分量分布的距离标准差上界 分裂用 两类中心间的最小距离下界 合并用 在每次迭代中可以合并的类的最多对数 允许的最多迭代次数 210 ISODATA算法原理步骤 211 ISODATA算法原理步骤 212 ISODATA算法原理步骤 计算各类的中心 计算分类后的参数 各类中心 类内平均距离及总体平均距离 计算各类中模式到类心的平均距离 计算各个模式到其类内中心的总体平均距离 213 ISODATA算法原理步骤 214 ISODATA算法原理步骤 计算各类类内距离的标准差矢量 式中 为分量编号 为类的编号 为矢量维数 是的第个分量 是的第个分量 215 ISODATA算法原理步骤 216 ISODATA算法原理步骤 217 ISODATA算法原理步骤 218 ISODATA算法原理步骤 219 220 ISODATA算法举例 二维 1 初始值设定 类间距离上限 距离标准差上界 最少模式数目 合并的类的最多对数 221 ISODATA算法举例 2 聚类 只有一个中心 222 ISODATA算法举例 3 因 无合并 4 计算聚类中心 类内平均距离和总的平均距离 223 ISODATA算法举例 5 因不是最后一步迭代 且 转至 6 求的标准差矢量 224 ISODATA算法举例 7 算得 6 因且将分裂成两类 取 则 且转 2 225 ISODATA算法举例 2 聚类 两个中心 3 因 无合并 226 ISODATA算法举例 4 计算聚类中心 类内平均距离和总的平均距离 5 因这是偶次迭代 满足算法原理步骤 中 的条件 故转 227 ISODATA算法举例 11 因不是最后一次迭代 题设 判断是否修改参数 由上面结果可知 已获得所要求类别数目 类间距离大于类内距离 每类样本数都有样本总数的足够大的百分比 因此不改变参数 228 2 4 计算结果与前一次迭代结果相同 7 分裂条件不满足 转至 无新的变化 转至 6 计算和的标准差矢量 5 没有任一种情况被满足 到 与前一次迭代结果相同 无合并发生 229 与前一次迭代结果相同 因是最后一次迭代 令 转至 同前 因 无合并发生 因是最后一次迭代 结束 230 ISODATA流程 231 232 233 输入样本数据 置c Nc 选初始类心zj j 1 2 Nc 1 置控制参数 n s D L I 2 聚类 ifdil min D xi z1 D xi z2 D xi zNc thenxi l 3 合并判决 nj n N Y Nc Nc 1 4 计算分类后的参数 类心zj 类内平均距离dj 总类内平均距离d 234 作业 P45 2 9 2 10 235 模式识别 主讲 蔡宣平教授电话 73441 O 73442 H E mail xpcai 单位 电子科学与工程学院信息工程系 236 第三章判别域代数界面方程法 3 1用判别域界面方程分类的概念 3 2线性判别函数 3 3判别函数值的鉴别意义 权空间及解空间 3 4Fisher线性判别 3 5一次准则函数及梯度下降法 3 6二次准则函数及其解法 3 9广义线性判别函数 3 10二次判别函数 3 12位势函数分类法 237 3 1用判别域界面方程分类的概念 238 两类的分类问题 它们的边界线就是一个判别函数 239 两类问题中线性不可分的实例 240 三类的分类问题 它们的边界线也是一个判别函数 241 3 1用判别域界面方程分类的概念 第三章判别域代数界面方程法 242 3 2线性判别函数 第三章判别域代数界面方程法 243 244 245 多类问题图例 第一种情况 不确定区域 246 1 第一种情况 续 判别规则为 如果 则判 比如对图的三类问题 如果对于任一模式如果它的则该模式属于 1类 247 1 第一种情况 续 如果某个X使二个以上的判别函数di 0 则此模式X就无法作出确切的判决 如图 另一种情况是IR2区域 判别函数都为负值 IR1 IR2 IR3 IR4 都为不确定区域 248 1 第一种情况 续 解 三个判别边界分别为 249 1 第一种情况 续 结论 因为所以它属于 2类 250 1 第一种情况 续 251 252 2 第二种情况 续 多类问题图例 第二种情况 253 254 d12 x d21 x x1 x2 5 0 d12 x 为正 两分法例题图示 d21 x 为正 255 d23 x d32 x x1 x2 0 d32 x 为正 d23 x 为正 256 d13 x d31 x x1 3 0 d31 x 为正 d13 x 为正 257 3类判别区域d31 x 0d32 x 0 258 259 3 第三种情况 续 多类问题图例 第三种情况 260 261 上述三种方法小结 方法 判别函数的数目和方法 相同 但没有不确定区 分析简单 是最常用的一种方法 262 3 3判别函数值的鉴别意义 权空间及解空间 第三章判别域代数界面方程法 263 此方程表示一超平面 它有以下三个性质 1 系数矢量 是该平面的法矢量 2 判别函数的绝对值正比于到超平面的距离 3 判别函数值的正负表示出特征点位于哪个半空间中 3 3判别函数值的鉴别意义 权空间及解空间 第三章判别域代数界面方程法 264 图3 3 1点面距离及界面的正负侧示意图 265 266 267 268 证明 判别函数值的正负表示出特征点位于哪个半空间中 269 这说明判别函数值的正负表示出特征点位于哪个半空间中 或者换句话说 表示特征点位于界面的哪一侧 270 例3 3 1 利用判别函数的鉴别意义 试分析d x1 x2 x1 x2 1 271 3 3 2权空间 解矢量与解空间 3 3判别函数值的鉴别意义 权空间及解空间 272 2 解矢量 3 3 2权空间 解矢量与解空间 3 3判别函数值的鉴别意义 权空间及解空间 273 2 解矢量 3 3 2权空间 解矢量与解空间 3 3判别函数值的鉴别意义 权空间及解空间 274 3 3 2权空间 解矢量与解空间 3 3判别函数值的鉴别意义 权空间及解空间 275 3 解空间 3 3 2权空间 解矢量与解空间 3 3判别函数值的鉴别意义 权空间及解空间 先看一个简单的情况 设一维数据1 2属于w1 1 2属于w2求将w1和w2区分开的w0 w1 276 3 解空间 3 3 2权空间 解矢量与解空间 3 3判别函数值的鉴别意义 权空间及解空间 先看一个简单的情况 设一维数据1 2属于w1 1 2属于w2求将w1和w2区分开的w0 w1 w0 w1 277 3 解空间 3 3 2权空间 解矢量与解空间 3 3判别函数值的鉴别意义 权空间及解空间 先看一个简单的情况 设一维数据1 2属于w1 1 2属于w2求将w1和w2区分开的w0 w1 w0 w1 278 3 解空间 3 3 2权空间 解矢量与解空间 3 3判别函数值的鉴别意义 权空间及解空间 先看一个简单的情况 设一维数据1 2属于w1 1 2属于w2求将w1和w2区分开的w0 w1 w0 w1 279 3 解空间 3 3 2权空间 解矢量与解空间 3 3判别函数值的鉴别意义 权空间及解空间 先看一个简单的情况 设一维数据1 2属于w1 1 2属于w2求将w1和w2区分开的w0 w1 w0 w1 280 3 解空间 3 3 2权空间 解矢量与解空间 3 3判别函数值的鉴别意义 权空间及解空间 先看一个简单的情况 设一维数据1 2属于w1 1 2属于w2求将w1和w2区分开的w0 w1 w0 w1 281 3 解空间 3 3 2权空间 解矢量与解空间 3 3判别函数值的鉴别意义 权空间及解空间 282 3 3 2权空间 解矢量与解空间 3 3判别函数值的鉴别意义 权空间及解空间 每一个训练模式都对解区提供一个约束 训练模式越多 解区的限制就越多 解区就越小 就越靠近解区的中心 解矢量就越可靠 由它构造的判别函数错分的可能性就越小 283 4 余量 3 3 2权空间 解矢量与解空间 3 3判别函数值的鉴别意义 权空间及解空间 284 4 余量 3 3 2权空间 解矢量与解空间 3 3判别函数值的鉴别意义 权空间及解空间 引入了余量可有效地避免量测的误差 引入的误差以及某些算法求得的解矢量收敛于解区的边界上 从而提高了解的可靠性 285 设一3类问题有如下判决函数d1 x x1d2 x x1 x2 1d3 x x1 x2 1试画出下列各种情况的判决边界及各类的区域 1 满足3 4 2节中的第一种情况 2 满足3 4 2节中的第二种情况 且令d12 x d1 x d13 x d2 x d23 x d3 x 3 满足3 4 2节中的第三种情况 作业 286 3 4Fisher线性判别 第三章判别域代数界面方程法 287 二维模式向一维空间投影示意图 288 二维模式向一维空间投影示意图 289 二维模式向一维空间投影示意图 o x y o x y 290 1 求解Fish准则函数 291 292 类间离差度为 293 并使其最大 上式称为Fisher准则函数 294 利用二次型关于矢量求导的公式可得 2 求解Fisher最佳鉴别矢量 令 可得 295 296 上式右边后两项因子的乘积为一标量 令其为 于是可得式中为一标量因子 其不改变轴的方向 可以取为1 于是有 297 此时的可使Fisher准则函数取最大值 即是n维空间到一维空间投影轴的最佳方向 由 和 JF最大值为 298 即称为Fisher变换函数 JF 299 由于变换后的模式是一维的 因此判别界面实际上是各类模式所在轴上的一个点 所以可以根据训练模式确定一个阈值yt 于是Fisher判别规则为 3 求解Fisher判别函数 判别阈值可取两个类心在u方向上轴的投影连线的中点作为阈值 即 300 301 7 计算 8 计算yt 9 对未知模式x判定模式类 302 以100元A面数据和50元A面数据