模式识别理论专业教学

《模式识别理论专业教学》由会员分享，可在线阅读，更多相关《模式识别理论专业教学（66页珍藏版）》请在装配图网上搜索。

1、模式识别理论 Pattern Recognition什么是模式识别什么是模式识别 模式识别（Pattern Recognition）是一种从大量信息和数据出发，在专家经验和已有认识的基础上，利用计算机和数学推理的方法对形状、模式、曲线、数字、字符格式和图形自动完成识别的、评价的过程。 从数学角度而言，模式识别也是一个数学建模过程。只是给出的是定性结论而不是定量指标。什么是模式识别什么是模式识别 模式识别包括两个阶段，即模式识别包括两个阶段，即学习阶段学习阶段和和实现阶段实现阶段，前者前者是对样本进行是对样本进行特征选择特征选择，寻找分类的规律，寻找分类的规律，后者后者是根据分类规律对未知样本集

2、进行是根据分类规律对未知样本集进行分类和识分类和识别别。 广义的模式识别属计算机科学中智能模拟的研究广义的模式识别属计算机科学中智能模拟的研究范畴，内容非常广泛，包括声音和语言识别、文范畴，内容非常广泛，包括声音和语言识别、文字识别、指纹识别、声纳信号和地震信号分析、字识别、指纹识别、声纳信号和地震信号分析、照片图片分析、化学模式识别等等。计算机模式照片图片分析、化学模式识别等等。计算机模式识别实现了部分脑力劳动自动化。识别实现了部分脑力劳动自动化。模式识别的特点模式识别的特点 模式识别的理论基础是多元统计理论模式识别的理论基础是多元统计理论和一些近代数学方法（如神经元网络和一些近代数学方法（

3、如神经元网络理论）。理论）。 模式识别给出的是统计和经验的规律，模式识别给出的是统计和经验的规律，无法提供关于样本理论模型。无法提供关于样本理论模型。 用计算机模式识别方法总结规律预报未知，用计算机模式识别方法总结规律预报未知，虽然不如纯粹的理论方法严格和有明确的虽然不如纯粹的理论方法严格和有明确的机理及解释，但却有广泛的适应面，能够机理及解释，但却有广泛的适应面，能够在现有知识、理论不够完善的情况下发挥在现有知识、理论不够完善的情况下发挥作用。在用计算机模式识别方法解决问题作用。在用计算机模式识别方法解决问题时，我们仍需要借助于与研究对象相关的时，我们仍需要借助于与研究对象相关的理论知识，去

4、估计、判断影响研究对象的理论知识，去估计、判断影响研究对象的大致因素，用这些因素的参数构筑多维空大致因素，用这些因素的参数构筑多维空间（即模式空间）描述研究对象的特征，间（即模式空间）描述研究对象的特征，才能用模式识别的方法总结规律。才能用模式识别的方法总结规律。模式识别计算过程示意图模式识别计算过程示意图有监督模式识别（判别分析有监督模式识别（判别分析） 如果样本的类别数是已知的，先用一组已如果样本的类别数是已知的，先用一组已知类别的样本作为训练集，建立判别模型，知类别的样本作为训练集，建立判别模型，再用建立的模型根据相似性原则来对未知再用建立的模型根据相似性原则来对未知样本进行识别，称为样

5、本进行识别，称为判别分析判别分析。 判别分析是在事先知道类别特征的情判别分析是在事先知道类别特征的情况下建立判别模型对样本进行识别归属，况下建立判别模型对样本进行识别归属，是一种是一种有监督模式识别有监督模式识别。 无监督模式识别（聚类分析）无监督模式识别（聚类分析） 如果预先不知道样本的类别，要在学习过如果预先不知道样本的类别，要在学习过程中根据样本的相似性对被识别的样品进程中根据样本的相似性对被识别的样品进行识别分类和归类，称为行识别分类和归类，称为聚类分析聚类分析。 聚类分析是完全依靠样本自然特性进聚类分析是完全依靠样本自然特性进行识别的方法，是一种行识别的方法，是一种无监督模式识别无监

6、督模式识别。 模式空间模式空间 样本样本xi可用一组参量可用一组参量( (矢量矢量) )来表征，来表征，即即 xi=(xi1, xi2, ., xin)，在模式识别中，这，在模式识别中，这种参量值又称种参量值又称特征特征。通常这些参量实际上。通常这些参量实际上就是原始数据。这样一组参量构成了模式就是原始数据。这样一组参量构成了模式识别空间的一个点，或称一个识别空间的一个点，或称一个n维的维的模式模式。由这些模式所构成的由这些模式所构成的n维变量空间，称为维变量空间，称为模式空间模式空间。因高维模式空间提供了更多的。因高维模式空间提供了更多的信息，故有可能解决一些低维空间中难于信息，故有可能解决

7、一些低维空间中难于解决的问题解决的问题。模式识别常用术语模式识别常用术语 特征抽提（特征抽提（Feature Extraction） 训练集训练集（Training Set） 识别率识别率（Recognition Rate） 预测能力预测能力（Predictive Ability） 注意事项注意事项l 训练集的数据一定要可靠。训练集的数据一定要可靠。l 训练集的样本数目要足够多，样本训练集的样本数目要足够多，样本数数m与模与模 式空间维数式空间维数n 的比值至少应满足的比值至少应满足m/n3，最好，最好m/n10。l 模式空间特征的选择是成败的关键，要选取与模式空间特征的选择是成败的关键，要选

8、取与样本分类有关的特征，如果不能包括与分类有样本分类有关的特征，如果不能包括与分类有关的主要特征，模式识别就不会有好的效果。关的主要特征，模式识别就不会有好的效果。模式识别的数据预处理模式识别的数据预处理 模式间相似度的度量模式识别方法模式识别方法I有监督模式识别法（判别分析法有监督模式识别法（判别分析法）Supervised pattern recognition (Discriminating analysis methods)l参数判别分析法参数判别分析法 包括包括距离判别距离判别、Fisher判别判别与与Beayes 判别分析法等判别分析法等l非参数判别分析法非参数判别分析法 包括包括

9、线性学习机、线性学习机、K-最近邻法、人工最近邻法、人工神经网络法等神经网络法等 K-Nearest Neighbors Discrimination Method KNNKNN法的基本假设法的基本假设： “同类样本在模式空间中相互较靠近，同类样本在模式空间中相互较靠近，不同类样本在模式空间中相互远离不同类样本在模式空间中相互远离” 。l K K最近邻法考查未知样本点的最近邻法考查未知样本点的K K个近邻（个近邻（K K为单数整为单数整数），若近邻某一类样本最多，则可将未知样本数），若近邻某一类样本最多，则可将未知样本判为该类。判为该类。 l 为了进行定量判别，可先找出待分类样本的最近为了进行

10、定量判别，可先找出待分类样本的最近邻，并事先约定最近邻区域中的训练集样本数。邻，并事先约定最近邻区域中的训练集样本数。如果只取一个最近邻样本点，即样本数为，则如果只取一个最近邻样本点，即样本数为，则称称1NN1NN法；如果取个最近邻样本点，即样本数为法；如果取个最近邻样本点，即样本数为2 2，则称，则称2NN2NN法；如果样本数为法；如果样本数为K K，则称，则称K K近邻法，近邻法，简称简称KNNKNN法。法。KNNKNN算法算法l 计算未知样本点和所有训练集样本点之间的距离。计算未知样本点和所有训练集样本点之间的距离。l 从最小距离开始计样本数，一直计从最小距离开始计样本数，一直计到有到有

11、K个样本数个样本数为止，此时所对应的距离就为最近邻的最小距离。为止，此时所对应的距离就为最近邻的最小距离。l 如果在这个最小距离中，距某一类训练集中的样如果在这个最小距离中，距某一类训练集中的样本数多，距离又小，则可将待分类样本划到该类本数多，距离又小，则可将待分类样本划到该类中。中。l 优点：对数据结构无特殊要求，简单易行，不需优点：对数据结构无特殊要求，简单易行，不需要训练过程。要训练过程。l 缺点：未对训练点进行信息压缩，每判断一个点缺点：未对训练点进行信息压缩，每判断一个点都要将其对所有已知点的距离计算一遍都要将其对所有已知点的距离计算一遍, ,工作量较工作量较大。大。 简化的简化的K

12、NNKNN法法类重心法类重心法l将训练集中每类样本点的重心求出，然将训练集中每类样本点的重心求出，然后判别未知样本点与各类样本点重心的后判别未知样本点与各类样本点重心的距离。未知样本点距哪一类重心距离最距离。未知样本点距哪一类重心距离最近，即未知样本属于哪一类。近，即未知样本属于哪一类。例例：有两种地层，用有两种地层，用7 7种指标的分析数据种指标的分析数据判别，先从已经准确判断的地层中各取判别，先从已经准确判断的地层中各取9 9个样本，测得的数据如下表：个样本，测得的数据如下表： 1. 将上表数据进行归一化处理后将上表数据进行归一化处理后计算计算两类的重心得：两类的重心得： C C1 1=-

13、0.0103,0.0402,-0.0246,0.0166, =-0.0103,0.0402,-0.0246,0.0166, 0.0313,-0.0246,-0.0174 0.0313,-0.0246,-0.0174 C C2 2=0.0103,-0.0402,0.0246,-0.0166,=0.0103,-0.0402,0.0246,-0.0166, -0.0313,0.0246,0.0174 -0.0313,0.0246,0.0174 2. 计算地层计算地层I I、IIII的每一个矢量的每一个矢量与与C C1 1和和C C2 2的距离，分别的距离，分别如表如表a a和表和表b b所示：所示：

14、 线性学习线性学习机法机法Linear learning machineLLM例子例子 现有甲状腺病人（记为类现有甲状腺病人（记为类1）和正）和正常人（记为类常人（记为类2）各）各10例，分别测试例，分别测试5项项功能指标，测试结果功能指标，测试结果见表见表a a和表和表b所示。所示。以每一类的前以每一类的前8个个 样本作为训练集（样本作为训练集（表表a），后），后2个作为测试集（个作为测试集（表表b）。用）。用LLM法对其进行判别。法对其进行判别。 FisherFisher线性判别线性判别二维模式向一维空间投影示意图二维模式向一维空间投影示意图oxy二维模式向一维空间投影示意图二维模式向一维

15、空间投影示意图tyoxy二维模式向一维空间投影示意图二维模式向一维空间投影示意图tyoxyoxy（1)1)求解求解FisherFisher准则函数准则函数uSuuSSusssWWWWWW)(2121222uSumumumumummsBB)()(21212212类间离差度为：类间离差度为：uSuuSussmmuJWBWWF2222121)()(并使其最大并使其最大, ,上式称为上式称为FisherFisher准则函数准则函数。利用二次型关于矢量求导的公式可得：利用二次型关于矢量求导的公式可得：2)()(2)(2uSuuSuSuuSuSuuSuuSuuuJWWBBWWBF（2) 2) 求解求解Fi

16、sherFisher最佳鉴别矢量最佳鉴别矢量uSuuSuWB令令uSuSWB可得：可得： 上式右边后两项因子的乘积为一标量，上式右边后两项因子的乘积为一标量，令其为令其为 ，于是可得，于是可得 式中式中 为一标量因子，其不改变轴的方为一标量因子，其不改变轴的方向，可以取为向，可以取为1,于是有于是有)(211mmSuW)(211mmSuWummmmSuSSuWBW)(212111uSuuSuuJWBF)()()(21121mmSmmW此时的此时的 可使可使Fisher准则函数取最大值，即是准则函数取最大值，即是n 维维空间到一维空间投影轴的最佳方向，由空间到一维空间投影轴的最佳方向，由u)(2

17、11mmSuW)(2121mmmmSB和和JF 最大值为最大值为:)()()()()(2111212112121121mmSSSmmmmSmmmmSmmWWWWW即即称称为为Fisher变换函数变换函数)()(21121mmSmmWxSmmyW121)(J JF F= 由于变换后的模式是一维的，因此判别界面实际由于变换后的模式是一维的，因此判别界面实际上是各类模式所在轴上的一个点，所以可以根据训练上是各类模式所在轴上的一个点，所以可以根据训练模式确定一个阈值模式确定一个阈值 y yt t，于是，于是FisherFisher判别规则判别规则为为: : 21xyyxut221mmyt（3) 3)

18、求解求解FisherFisher判别函数判别函数判别阈值可取两个类心在判别阈值可取两个类心在u u方向上轴的投影连线的方向上轴的投影连线的中点作为阈值，即中点作为阈值，即: :ijijijijiimuxuNyNm)()(11（7 7） 计算计算 。im221mmyt（8 8） 计算计算yt 。21xyyxut（9 9） 对未知模式对未知模式x判定模式类。判定模式类。以以100100元元A A面数据和面数据和5050元元A A面数据为例面数据为例100100元元A A面面:(64,76,99,84,98,95,88,83),:(64,76,99,84,98,95,88,83),5050元元A A

19、面面:(65,67,82,80,89,94,86,92),:(65,67,82,80,89,94,86,92),N N1 1=N=N2 2=60=60算得算得: :m m1 1=(69.3,61.9,83.5,70.8,97.7,91.5,87.6,82.4)=(69.3,61.9,83.5,70.8,97.7,91.5,87.6,82.4)m m2 2=(59.2,55.5,81.9,63.9,95.1,91.0,91.1,86.5)=(59.2,55.5,81.9,63.9,95.1,91.0,91.1,86.5)m m1 1=(=(69.3, 61.9, 83.5, 70.8, 97.7

20、, 91.5, 87.6, 82.469.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.4) )m m2 2=(=(59.2, 55.5, 81.9, 63.9, 95.1, 91.0, 91.1, 86.559.2, 55.5, 81.9, 63.9, 95.1, 91.0, 91.1, 86.5) )m m1 1=(=(69.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.469.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.4) )m m2 2=(=(59.2, 55.5, 8

21、1.9, 63.9, 95.1, 91, 91.1, 86.559.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.5) )m m1 1=(=(69.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.469.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.4) )m m2 2=(=(59.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.559.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.5) )m m1 1=(=(69.3,

22、61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.469.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.4) )m m2 2=(=(59.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.559.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.5) )无监督模式识别法无监督模式识别法 不需要训练集，对所研究的模式进行适当分类的问题则需要用无监督模式识别方法，这类模式识别方法又叫聚类分析法(clustering analysis method)。 常用聚类分析方法有：

23、分级聚类分析法分级聚类分析法Hierarchical clustering methods 最小（大）生成树最小（大）生成树法法Minimun（Max） Spanning Tree Method K均值聚类均值聚类法法K-means Clustering Method 模糊聚类法模糊聚类法Fuzzy clustering method PCA投影分类法等等投影分类法等等主成分分析的数学主成分分析的数学与几何意义示意图与几何意义示意图 1616个脑组织试样进行分析，在色谱图中个脑组织试样进行分析，在色谱图中取多达取多达156156参量（可辨认的参量（可辨认的156156个峰处的峰个峰处的峰高），

24、组成高），组成(16(16 156)156)阶矩阵，通过将矩阵作阶矩阵，通过将矩阵作主成分分解，分别求得对应于两个最大特征主成分分解，分别求得对应于两个最大特征值的得分矢量值的得分矢量t t1 1和和t t2 2，并以，并以t t1 1和和t t2 2为投影轴作为投影轴作图，得到下图。其中正方形是有肿瘤的脑组图，得到下图。其中正方形是有肿瘤的脑组织样，圆是正常脑组织样。织样，圆是正常脑组织样。Projection discrimination based onprincipal component analysis最大生成树法最大生成树法 上图点与点之间的数据叫作上图点与点之间的数据叫作路径强

25、度路径强度，表，表示两样本点间的相似程度。如果一个路径示两样本点间的相似程度。如果一个路径的起点与终点重合，称这条路径构成一个的起点与终点重合，称这条路径构成一个回路回路，对于图中砍去某些边得到的树叫，对于图中砍去某些边得到的树叫生生成树成树。若某生成树所有路径的强度都大于。若某生成树所有路径的强度都大于或等于其它生成树的路径强度，则称此生或等于其它生成树的路径强度，则称此生成树为成树为最大生成树。最大生成树。 只要找到相似关图的最大生成树，就可以只要找到相似关图的最大生成树，就可以根据最大生成树进行模糊聚类分析，其分根据最大生成树进行模糊聚类分析，其分类准则是：对于规定的阈值水平类准则是：对

26、于规定的阈值水平 ，路径强，路径强度大于度大于 的顶点可归为一类的顶点可归为一类。根据最大生成树进行聚类分析的方法如下：根据最大生成树进行聚类分析的方法如下： （1）先连接路径强度最大的两点，然后）先连接路径强度最大的两点，然后连接路径强度次大的两点；连接路径强度次大的两点； （2）继续连接所剩下点的最大路径强度）继续连接所剩下点的最大路径强度的两点，直到所有的点都被连接；的两点，直到所有的点都被连接； （3）对连接所得到的树进行检查，找到）对连接所得到的树进行检查，找到最小路径的边，将其割断就得到两类，如最小路径的边，将其割断就得到两类，如此继续分割，直至类数已达到所要分的此继续分割，直至类数已达到所要分的类类数。数。