2020/1/28北京邮电大学信息工程学院模式识别导论盛立东北京邮电大学信息工程学院2020/1/28北京邮电大学信息工程学院参考书•模式识别人民邮电出版社罗耀光盛立东•模式识别清华大学出版社边肇祺•模式识别及应用科学出版社付京荪•SyntacticPatternRecognitionandApplicationK.S.Fu•PatternRecognitionPrinciplesJ.T.TomR.C.Gouzales2020/1/28北京邮电大学信息工程学院•作业:大型上机作业题•考试:开卷考试2020/1/28北京邮电大学信息工程学院第一章概论§1-1模式识别的基本概念一.模式识别的基本定义模式(pattern)------存在于时间,空间中可观察的事物,具有时间或空间分布的信息。模式识别(PatternRecognition)------用计算机实现人对各种事物或现象的分析,描述,判断,识别。模式识别与图象识别,图象处理的关系模式识别是模拟人的某些功能模拟人的视觉:计算机+光学系统模拟人的听觉:计算机+声音传感器模拟人的嗅觉和触觉:计算机+传感器2020/1/28北京邮电大学信息工程学院二.模式识别的发展史•1929年G.Tauschek发明阅读机,能够阅读0-9的数字。•30年代Fisher提出统计分类理论,奠定了统计模式识别的基础。因此,在60~70年代,统计模式识别发展很快,但由于被识别的模式愈来愈复杂,特征也愈多,就出现“维数灾难”。但由于计算机运算速度的迅猛发展,这个问题得到一定克服。统计模式识别仍是模式识别的主要理论。2020/1/28北京邮电大学信息工程学院•50年代NoamChemsky提出形式语言理论美籍华人付京荪提出句法结构模式识别。•60年代L.A.Zadeh提出了模糊集理论,模糊模式识别理论得到了较广泛的应用。•80年代Hopfield提出神经元网络模型理论。近些年人工神经元网络在模式识别和人工智能上得到较广泛的应用。•90年代小样本学习理论,支持向量机也受到了很大的重视。2020/1/28北京邮电大学信息工程学院三.关于模式识别的国内、国际学术组织•1973年IEEE发起了第一次关于模式识别的国际会议“ICPR”,成立了国际模式识别协会---“IAPR”,每2年召开一次国际学术会议。•1977年IEEE的计算机学会成立了模式分析与机器智能(PAMI)委员会,每2年召开一次模式识别与图象处理学术会议。•国内的组织有电子学会,通信学会,自动化协会,中文信息学会….。2020/1/28北京邮电大学信息工程学院§1-2模式识别系统•信息的获取:是通过传感器,将光或声音等信息转化为电信息。信息可以是二维的图象如文字,图象等;可以是一维的波形如声波,心电图,脑电图;也可以是物理量与逻辑值。•预处理:包括A\D,二值化,图象的平滑,变换,增强,恢复,滤波等,主要指图象处理。2020/1/28北京邮电大学信息工程学院•特征抽取和选择:在模式识别中,需要进行特征的抽取和选择,例如,一幅64x64的图象可以得到4096个数据,这种在测量空间的原始数据通过变换获得在特征空间最能反映分类本质的特征。这就是特征提取和选择的过程。•分类器设计:分类器设计的主要功能是通过训练确定判决规则,使按此类判决规则分类时,错误率最低。把这些判决规则建成标准库。•分类决策:在特征空间中对被识别对象进行分类。2020/1/28北京邮电大学信息工程学院§1-3模式识别的应用1.字符识别:包括印刷体字符的识别;手写体字符的识别(脱机),各种OCR设备例如信函分拣、文件处理、卡片输入、支票查对、自动排板、期刊阅读、稿件输入;在线手写字符的识别(联机),各种书写输入板。2.医疗诊断:心电图,脑电图,染色体,癌细胞识别,疾病诊断,例如关幼波肝炎专家系统。3.遥感:资源卫星照片,气象卫星照片处理,数字化地球,图象分辨率可以达到1米。2020/1/28北京邮电大学信息工程学院4.指纹识别脸形识别5.检测污染分析,大气,水源,环境监测。6.自动检测:产品质量自动检测7.语声识别,机器翻译,电话号码自动查询,侦听,机器故障判断。8.军事应用2020/1/28北京邮电大学信息工程学院§1-4模式识别的基本问题一.模式(样本)表示方法1.向量表示:假设一个样本有n个变量(特征)Ⅹ=(X1,X2,…,Xn)T2.矩阵表示:N个样本,n个变量(特征)变量样本x1x2…xnX1X11X12…X1nX2X21X22…X2n……………XNXN1XN2…XNn2020/1/28北京邮电大学信息工程学院3.几何表示一维表示X1=1.5X2=3二维表示X1=(x1,x2)T=(1,2)TX2=(x1,x2)T=(2,1)T三维表示X1=(x1,x2,x3)T=(1,1,0)TX2=(x1,x2,x3)T=(1,0,1)T2020/1/28北京邮电大学信息工程学院4.基元(链码)表示:在右侧的图中八个基元分别表示0,1,2,3,4,5,6,7,八个方向和基元线段长度。则右侧样本可以表示为X1=006666这种方法将在句法模式识别中用到。2020/1/28北京邮电大学信息工程学院二.模式类的紧致性1.紧致集:同一类模式类样本的分布比较集中,没有或临界样本很少,这样的模式类称紧致集。2020/1/28北京邮电大学信息工程学院2.临界点(样本):在多类样本中,某些样本的值有微小变化时就变成另一类样本称为临界样本(点)。3.紧致集的性质①要求临界点很少②集合内的任意两点的连线,在线上的点属于同一集合③集合内的每一个点都有足够大的邻域,在邻域内只包含同一集合的点4.模式识别的要求:满足紧致集,才能很好的分类;如果不满足紧致集,就要采取变换的方法,满足紧致集.2020/1/28北京邮电大学信息工程学院三.相似与分类1.两个样本xi,xj之间的相似度量满足以下要求:①应为非负值②样本本身相似性度量应最大③度量应满足对称性④在满足紧致性的条件下,相似性应该是点间距离的单调函数2.用各种距离表示相似性:①绝对值距离已知两个样本xi=(xi1,xi2,xi3,…,xin)Txj=(xj1,xj2,xj3,…,xjn)T2020/1/28北京邮电大学信息工程学院②欧几里德距离③明考夫斯基距离其中当q=1时为绝对值距离,当q=2时为欧氏距离nkjkikijXXd1||nkjkikijXXd12nkjkikqijXXqqd1||1)(2020/1/28北京邮电大学信息工程学院④切比雪夫距离q趋向无穷大时明氏距离的极限情况⑤马哈拉诺比斯距离其中xi,xj为特征向量,为协方差。使用的条件是样本符合正态分布||max)(1jkiknkijXXd1)(jijiTijXXXXMd2020/1/28北京邮电大学信息工程学院⑥夹角余弦为xixj的均值即样本间夹角小的为一类,具有相似性例:x1,x2,x3的夹角如图:因为x1,x2的夹角小,所以x1,x2最相似。nkjknkiknkjkikijXXXXC12121x1x2x1x2x3XXji,2020/1/28北京邮电大学信息工程学院⑦相关系数为xixj的均值注意:在求相关系数之前,要将数据标准化3.分类的主观性和客观性①分类带有主观性:目的不同,分类不同。例如:鲸鱼,牛,马从生物学的角度来讲都属于哺乳类,但是从产业角度来讲鲸鱼属于水产业,牛和马属于畜牧业。②分类的客观性:科学性判断分类必须有客观标准,因此分类是追求客观性的,但主观性也很难避免,这就是分类的复杂性。nknkjkjikinkjkjikiXXXXXXXXrij11221jiXX,2020/1/28北京邮电大学信息工程学院四.特征的生成1.低层特征:①无序尺度:有明确的数量和数值。②有序尺度:有先后、好坏的次序关系,如酒分为上,中,下三个等级。③名义尺度:无数量、无次序关系,如有红,黄两种颜色2.中层特征:经过计算,变换得到的特征3.高层特征:在中层特征的基础上有目的的经过运算形成例如:椅子的重量=体积*比重体积与长,宽,高有关;比重与材料,纹理,颜色有关。这里低、中、高三层特征都有了。2020/1/28北京邮电大学信息工程学院五.数据的标准化1.极差标准化,一批样本中,每个特征的最大值与最小值之差。极差极差标准化2.方差标准化Si为方差标准化的方法很多,原始数据是否应该标准化,应采用什么方法标准化,都要根据具体情况来定。ijijiXXRminmaxiiijRXXXijiiijSXXXij