模式识别复习资料ppt课件.ppt

复习 1 模式和模式识别的概念1 模式 对某些感兴趣的客体的定量的或结构的描述 模式类是具有某些共同特性的模式的集合 2 模式识别 研究一种自动技术 依靠这种技术 计算机将自动地 或人尽量少地干涉 把待别识模式分配到各自的模式类中去 复习 2模式识别系统组成 复习 1 监督分类 需要依靠已知类别的训练样本集 按照他们特征向量的分布来确定判别函数 然后利用判别函数对未知模式进行分类 需要足够的先验知识 判别 需要有足够的先验知识 2 非监督分类 用于没有先验知识的情况 通常采用聚类分析的方法 3监督分类和无监督分类 复习 4模式识别整体知识结构 5最大最小距离算法 小中取大距离算法 算法描述 选任意一模式样本做为第一聚类中心Z1 选择离Z1距离最远的样本作为第二聚类中心Z2 逐个计算各模式样本与已确定的所有聚类中心之间的距离 并选出其中的最小距离 例当聚类中心数k 2时 计算 复习 将样本按最近距离划分到相应聚类中心对应的类别中 重复步骤 直到没有新的聚类中心出现为止 在所有最小距离中选出最大距离 如该最大值达到的一定分数比值 阈值T 以上 则相应的样本点取为新的聚类中心 返回 否则 寻找聚类中心的工作结束 例k 2时 复习 例2 1对图示模式样本用最大最小距离算法进行聚类分析 选Z1 X1 距Z1最远 选为Z2 计算T 对应最小距离中的最大值 且 T 选作Z3 结果 Z1 X1 Z2 X6 Z3 X7 用全体模式对三个聚类中心计算最小距离中的最大值 无 T情况 停止寻找中心 聚类 算法描述 1 N个初始模式样本自成一类 即建立N类 计算各类之间 即各样本间 的距离 得一N N维距离矩阵D 0 0 表示初始状态 G Group 6层次聚类法 2 假设已求得距离矩阵D n n为逐次聚类合并的次数 找出D n 中的最小元素 将其对应的两类合并为一类 由此建立新的分类 3 计算合并后新类别之间的距离 得D n 1 4 跳至第2步 重复计算及合并 复习 结束条件 1 取距离阈值T 当D n 的最小分量超过给定值T时 算法停止 所得即为聚类结果 2 或不设阈值T 一直将全部样本聚成一类为止 输出聚类的分级树 复习 例 给出6个五维模式样本如下 按最短距离准则进行系统聚类分类 计算各类间欧氏距离 解 1 将每一样本看作单独一类 得 2 将最小距离对应的类和合并为1类 得新的分类 计算聚类后的距离矩阵D 1 由D 0 递推出D 1 得距离矩阵D 0 3 将D 1 中最小值对应的类合为一类 得D 2 4 将D 2 中最小值对应的类合为一类 得D 3 若给定的阈值为 D 3 中的最小元素 聚类结束 若无阈值 继续分下去 最终全部样本归为一类 可给出聚类过程的树状表示图 层次聚类法的树状表示 类间距离阈值增大 分类变粗 7K 均值算法 算法描述 1 任选K个初始聚类中心 Z1 1 Z2 1 ZK 1 2 按最小距离原则将其余样品分配到K个聚类中心中的某一个 Nj 第j类的样本数 3 计算各个聚类中心的新向量值 4 如果 则回到 2 将模式样本逐个重新分类 重复迭代计算 算法收敛 计算完毕 如果 复习 例2 3 已知20个模式样本如下 试用K 均值算法分类 解 取K 2 并选 计算距离 聚类 可得到 计算新的聚类中 从新的聚类中心得 有 计算聚类中心 返回第 步 以Z1 3 Z2 3 为中心进行聚类 以新的聚类中心分类 求得的分类结果与前一次迭代结果相同 计算新聚类中心向量值 聚类中心与前一次结果相同 即 故算法收敛 得聚类中心为 结果图示 图2 10K 均值算法聚类结果 上述K 均值算法 其类型数目假定已知为K个 当K未知时 可以令K逐渐增加 此时Jj会单调减少 最初减小速度快 但当K增加到一定数值时 减小速度会减慢 直到K 总样本数N时 Jj 0 Jj K关系曲线如下图 8聚类准则函数Jj与K的关系曲线 曲线的拐点A对应着接近最优的K值 J值减小量 计算量以及分类效果的权衡 并非所有的情况都容易找到关系曲线的拐点 迭代自组织的数据分析算法可以确定模式类的个数K 用线性判别函数将属于 i类的模式与其余不属于 i类的模式分开 识别分类时 9线性判别函数 复习 对某一模式区 di X 0的条件超过一个 或全部的di X 0 分类失效 相当于不确定区 indefiniteregion IR 此法将M个多类问题分成M个两类问题 识别每一类均需M个判别函数 识别出所有的M类仍是这M个函数 例3 1设有一个三类问题 其判别式为 现有一模式 X 7 5 T 试判定应属于哪类 并画出三类模式的分布区域 解 将X 7 5 T代入上三式 有 三个判别界面分别为 图示如下 步骤 a 画出界面直线 b 判别界面正负侧 找特殊点带入 c 找交集 感知器算法步骤 1 选择N个分属于 1和 2类的模式样本构成训练样本集 X1 XN 构成增广向量形式 并进行规范化处理 任取权向量初始值W 1 开始迭代 迭代次数k 1 2 用全部训练样本进行一轮迭代 计算WT k Xi的值 并修正权向量 分两种情况 更新权向量的值 9感知器算法 复习 c 正的校正增量 分类器对第i个模式做了错误分类 权向量校正为 统一写为 3 分析分类结果 只要有一个错误分类 回到 2 直至对所有样本正确分类 分类正确时 对权向量 赏 这里用 不罚 即权向量不变 分类错误时 对权向量 罚 对其修改 向正确的方向转换 感知器算法是一种赏罚过程 例3 8已知两类训练样本 解 所有样本写成增广向量形式 进行规范化处理 属于 2的样本乘以 1 用感知器算法求出将模式分为两类的权向量解和判别函数 任取W 1 0 取c 1 迭代过程为 第一轮 有两个WT k Xi 0的情况 错判 进行第二轮迭代 第二轮 第三轮 第四轮 该轮迭代的分类结果全部正确 故解向量 相应的判别函数为 当c W 1 取其他值时 结果可能不一样 所以感知器算法的解不是单值的 判别界面d X 0如图示 10最小错误率贝叶斯决策 对两类问题 可改写为 统计学中称l12 X 为似然比 为似然比阈值 例4 1假定在细胞识别中 病变细胞的先验概率和正常细胞的先验概率分别为 现有一待识别细胞 其观察值为X 从类条件概率密度发布曲线上查得 试对细胞X进行分类 解 方法1 通过后验概率计算 方法2 利用先验概率和类概率密度计算 是正常细胞 11最小风险贝叶斯决策 2 两类情况 对样本X 当X被判为 1类时 当X被判为 2类时 4 15 4 16 由 4 15 式 决策规则 为阈值 计算 计算 定义损失函数Lij 判别步骤 类概率密度函数p X i 也称 i的似然函数 解 计算和得 例4 2在细胞识别中 病变细胞和正常细胞的先验概率分别为 现有一待识别细胞 观察值为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 变换前 变换后 多类类内散布矩阵