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