模式识别理论.ppt

模式识别理论,Pattern Recognition,什么是模式识别,模式识别（Pattern Recognition）是一种从大量信息和数据出发，在专家经验和已有认识的基础上，利用计算机和数学推理的方法对形状、模式、曲线、数字、字符格式和图形自动完成识别的、评价的过程。 从数学角度而言，模式识别也是一个数学建模过程。只是给出的是定性结论而不是定量指标。,什么是模式识别,模式识别包括两个阶段，即学习阶段和实现阶段，前者是对样本进行特征选择，寻找分类的规律，后者是根据分类规律对未知样本集进行分类和识别。 广义的模式识别属计算机科学中智能模拟的研究范畴，内容非常广泛，包括声音和语言识别、文字识别、指纹识别、声纳信号和地震信号分析、照片图片分析、化学模式识别等等。计算机模式识别实现了部分脑力劳动自动化。,模式识别的特点,模式识别的理论基础是多元统计理论和一些近代数学方法（如神经元网络理论）。 模式识别给出的是统计和经验的规律，无法提供关于样本理论模型。,用计算机模式识别方法总结规律预报未知，虽然不如纯粹的理论方法严格和有明确的机理及解释，但却有广泛的适应面，能够在现有知识、理论不够完善的情况下发挥作用。在用计算机模式识别方法解决问题时，我们仍需要借助于与研究对象相关的理论知识，去估计、判断影响研究对象的大致因素，用这些因素的参数构筑多维空间（即模式空间）描述研究对象的特征，才能用模式识别的方法总结规律。,模式识别计算过程示意图,有监督模式识别（判别分析）,如果样本的类别数是已知的，先用一组已知类别的样本作为训练集，建立判别模型，再用建立的模型根据相似性原则来对未知样本进行识别，称为判别分析。 判别分析是在事先知道类别特征的情况下建立判别模型对样本进行识别归属，是一种有监督模式识别。,无监督模式识别（聚类分析）,如果预先不知道样本的类别，要在学习过程中根据样本的相似性对被识别的样品进行识别分类和归类，称为聚类分析。 聚类分析是完全依靠样本自然特性进行识别的方法，是一种无监督模式识别。,模式空间,样本xi可用一组参量(矢量)来表征，即 xi=(xi1, xi2, ., xin)，在模式识别中，这种参量值又称特征。通常这些参量实际上就是原始数据。这样一组参量构成了模式识别空间的一个点，或称一个n维的模式。由这些模式所构成的n维变量空间，称为模式空间。因高维模式空间提供了更多的信息，故有可能解决一些低维空间中难于解决的问题。,模式识别常用术语,特征抽提（Feature Extraction） 训练集（Training Set） 识别率（Recognition Rate） 预测能力（Predictive Ability）,注意事项,训练集的数据一定要可靠。 训练集的样本数目要足够多，样本数m与模 式空间维数n 的比值至少应满足m/n3，最好m/n10。 模式空间特征的选择是成败的关键，要选取与样本分类有关的特征，如果不能包括与分类有关的主要特征，模式识别就不会有好的效果。,模式识别的数据预处理,模式间相似度的度量,模式识别方法I有监督模式识别法（判别分析法）Supervised pattern recognition (Discriminating analysis methods),参数判别分析法 包括距离判别、Fisher判别与Beayes 判别分析法等 非参数判别分析法 包括线性学习机、K-最近邻法、人工神经网络法等,K-Nearest Neighbors Discrimination Method,KNN法的基本假设： “同类样本在模式空间中相互较靠近，不同类样本在模式空间中相互远离” 。,K最近邻法考查未知样本点的K个近邻（K为单数整数），若近邻某一类样本最多，则可将未知样本判为该类。 为了进行定量判别，可先找出待分类样本的最近邻，并事先约定最近邻区域中的训练集样本数。如果只取一个最近邻样本点，即样本数为，则称1NN法；如果取个最近邻样本点，即样本数为2，则称2NN法；如果样本数为K，则称K近邻法，简称KNN法。,KNN算法,计算未知样本点和所有训练集样本点之间的距离。 从最小距离开始计样本数，一直计到有K个样本数为止，此时所对应的距离就为最近邻的最小距离。 如果在这个最小距离中，距某一类训练集中的样本数多，距离又小，则可将待分类样本划到该类中。 优点：对数据结构无特殊要求，简单易行，不需要训练过程。 缺点：未对训练点进行信息压缩，每判断一个点都要将其对所有已知点的距离计算一遍,工作量较大。,简化的KNN法类重心法,将训练集中每类样本点的重心求出，然后判别未知样本点与各类样本点重心的距离。未知样本点距哪一类重心距离最近，即未知样本属于哪一类。 例：有两种地层，用7种指标的分析数据判别，先从已经准确判断的地层中各取9个样本，测得的数据如下表：,1. 将上表数据进行归一化处理后计算两类的重心得： C1=-0.0103,0.0402,-0.0246,0.0166, 0.0313,-0.0246,-0.0174 C2=0.0103,-0.0402,0.0246,-0.0166, -0.0313,0.0246,0.0174 2. 计算地层I、II的每一个矢量与C1和C2的距离，分别如表a和表b所示：,线性学习机法Linear learning machineLLM,作为模式识别中决策分类的一种方法，该法希望通过某种方法，在模式空间中到找到一个判决面（此面叫做分类器），使不同类的模式点分别位于判别面的两侧。未知模式的分类可根据它位于判别面的哪一侧来定。若判别面是一个线性超平面，就叫线性分类器。,例子 现有甲状腺病人（记为类1）和正常人（记为类2）各10例，分别测试5项功能指标，测试结果见表a和表b所示。以每一类的前8个 样本作为训练集（表a），后2个作为测试集（表b）。用LLM法对其进行判别。,Fisher线性判别,二维模式向一维空间投影示意图,二维模式向一维空间投影示意图,二维模式向一维空间投影示意图,o,x,y,o,x,y,（1)求解Fisher准则函数,类间离差度为：,并使其最大,上式称为Fisher准则函数。,利用二次型关于矢量求导的公式可得：,（2) 求解Fisher最佳鉴别矢量,令,可得：,上式右边后两项因子的乘积为一标量，令其为 ，于是可得 式中 为一标量因子，其不改变轴的方向，可以取为1,于是有,此时的 可使Fisher准则函数取最大值，即是n 维空间到一维空间投影轴的最佳方向，由,和,JF 最大值为:,即 称 为Fisher变换函数,JF=,由于变换后的模式是一维的，因此判别界面实际上是各类模式所在轴上的一个点，所以可以根据训练模式确定一个阈值 yt，于是Fisher判别规则为:,（3) 求解Fisher判别函数,判别阈值可取两个类心在u方向上轴的投影连线的中点作为阈值，即:,（7） 计算 。,（8） 计算yt 。,（9） 对未知模式x判定模式类。,以100元A面数据和50元A面数据为例 100元A面:(64,76,99,84,98,95,88,83), 50元A面:(65,67,82,80,89,94,86,92), N1=N2=60算得: m1=(69.3,61.9,83.5,70.8,97.7,91.5,87.6,82.4) m2=(59.2,55.5,81.9,63.9,95.1,91.0,91.1,86.5),m1=(69.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.4) m2=(59.2, 55.5, 81.9, 63.9, 95.1, 91.0, 91.1, 86.5),m1=(69.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.4) m2=(59.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.5),m1=(69.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.4) m2=(59.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.5),m1=(69.3, 61.9, 83.5, 70.8, 97.7, 91.5, 87.6, 82.4) m2=(59.2, 55.5, 81.9, 63.9, 95.1, 91, 91.1, 86.5),无监督模式识别法,不需要训练集，对所研究的模式进行适当分类的问题则需要用无监督模式识别方法，这类模式识别方法又叫聚类分析法(clustering analysis method)。,常用聚类分析方法有： 分级聚类分析法Hierarchical clustering methods 最小（大）生成树法Minimun（Max） Spanning Tree Method K均值聚类法K-means Clustering Method 模糊聚类法Fuzzy clustering method PCA投影分类法等等,主成分分析的数学与几何意义示意图,16个脑组织试样进行分析，在色谱图中取多达156参量（可辨认的156个峰处的峰高），组成(16156)阶矩阵，通过将矩阵作主成分分解，分别求得对应于两个最大特征值的得分矢量t1和t2，并以t1和t2为投影轴作图，得到下图。其中正方形是有肿瘤的脑组织样，圆是正常脑组织样。,Projection discrimination based onprincipal component analysis,最大生成树法,上图点与点之间的数据叫作路径强度，表示两样本点间的相似程度。如果一个路径的起点与终点重合，称这条路径构成一个回路，对于图中砍去某些边得到的树叫生成树。若某生成树所有路径的强度都大于或等于其它生成树的路径强度，则称此生成树为最大生成树。 只要找到相似关图的最大生成树，就可以根据最大生成树进行模糊聚类分析，其分类准则是：对于规定的阈值水平，路径强度大于的顶点可归为一类。,根据最大生成树进行聚类分析的方法如下： （1）先连接路径强度最大的两点，然后连接路径强度次大的两点； （2）继续连接所剩下点的最大路径强度的两点，直到所有的点都被连接； （3）对连接所得到的树进行检查，找到最小路径的边，将其割断就得到两类，如此继续分割，直至类数已达到所要分的类数。,