模式识别电子教材-北京航空航天大学

第一章引论1·1概述1.1.1模式识别模式识别(PatternRecognition)：确定一个样本的类别属性（模式类）的过程，即把某一样本归属于多个类型中的某个类型。样本（Sample)：一个具体的研究（客观）对象。如患者，某人写的一个汉字，一幅图片等。模式(Pattern)：对客体（研究对象）特征的描述（定量的或结构的描述），是取自客观世界的某一样本的测量值的集合（或综合）。特征(Features)：能描述模式特性的量（测量值）。在统计模式识别方法中，通常用一个矢量表示，称之为特征矢量，记为模式类(Class)：具有某些共同特性的模式的集合。1.1.2模式识别系统⑴特征提取从模式空间中选择最有利于模式分类的量作为特征，压缩模式维数，以便于处理，减少消耗。特征提取一般以分类中使用的某种判决规则为准则。所提取的特征使在某种准则下的分类错误最少。为此需要考虑特征之间的统计关系，选用适当的正交变换，才能提取出最有效的特征。⑵特征选择特征选择同样需要某种分类准则，在该准则下选择对分类贡献较大的特征，删除贡献较小的那些特征。⑶学习和训练根据已知类别的样本确定分类判决准则矫正特征提取选择方法等⑷分类识别分类是把特征空间划分成类型空间。把未知类别属性的样本确定为类型空间里的某一类型。分类错误率越小越好，分类错误率的分析和计算比较困难。影响分类错误率的因数–分类方法–分类器设计–提取的特征–样本质量等1.1.3模式识别的基本方法㈠统计模式识别理论基础：概率论，数理统计主要方法：线性、非线性分类、Bayes决策、聚类分析主要优点：1）比较成熟2）能考虑干扰噪声等影响3）识别模式基元能力强主要缺点：1）对结构复杂的模式抽取特征困难2）不能反映模式的结构特征，难以描述模式的性质3）难以从整体角度考虑识别问题㈡句法模式识别模式描述方法：符号串，树，图模式判定：是一种语言，用一个文法表示一个类，m类就有m个文法，然后判定未知模式遵循哪一个文法。在学习过程中，确定基元与基元之间的关系，推断出生成景物的方法。判决过程中，首先提取基元，识别基元之间的连接关系，使用推断的文法规则做句法分析。若分析成立，则判断输入的景物属于相应的类型。理论基础：形式语言，自动机技术主要方法：自动机技术、CYK剖析算法、Early算法、转移图法主要优点：1）识别方便，可以从简单的基元开始，由简至繁。2）能反映模式的结构特征，能描述模式的性质。3）对图象畸变的抗干扰能力较强。主要缺点：当存在干扰及噪声时，抽取特征基元困难，且易失误。㈢模糊模式识别模式描述方法：模糊集合A={(a,a),(b,b),...(n,n)}模式判定：是一种集合运算。用隶属度将模糊集合划分为若干子集，m类就有m个子集，然后根据择近原则分类。理论基础：模糊数学主要方法：模糊统计法、二元对比排序法、推理法、模糊集运算规则、模糊矩阵主要优点：由于隶属度函数作为样本与模板间相似程度的度量，故往往能反映整体的与主体的特征，从而允许样本有相当程度的干扰与畸变。主要缺点：准确合理的隶属度函数往往难以建立，故限制了它的应用。㈣人工神经网络法模式描述方法：以不同活跃度表示的输入节点集（神经元）模式判定：是一个非线性动态系统。通过对样本的学习建立起记忆，然后将未知模式判决为其最接近的记忆。理论基础：神经生理学，心理学主要方法：BP模型、HOP模型、高阶网主要优点：可处理一些环境信息十分复杂，背景知识不清楚，推理规则不明确的问题。允许样本有较大的缺损、畸变。主要缺点：模型在不断丰富与完善中，目前能识别的模式类还不够多。㈤人工智能方法模式描述方法：字符串表示的事实模式判定：是一种布尔运算。从事实出发运用一系列规则，推理得到不同结果，m个类就有m个结果。理论基础：演绎逻辑，布尔代数主要方法：产生式推理、语义网推理、框架推理主要优点：已建立了关于知识表示及组织，目标搜索及匹配的完整体系。对需要众多规则的推理达到识别目标确认的问题，有很好的效果。主要缺点：当样本有缺损，背景不清晰，规则不明确甚至有歧义时，效果不好。1·2特征矢量和特征空间特征矢量：设一个研究对象的个特征量测量值分别为,我们将它们作为一个整体来考虑,让它们构成一个维特征矢量。特征空间:各种不同取值的特征矢量的全体构成了维特征空间。注：特征矢量就是特征空间中的一个点。1·3随机矢量的描述㈠随机矢量的分布函数设为随机矢量，为确定性矢量。随机矢量的联合概率分布函数定义为(1-3-1)写成矢量形式(1-3-2)约定，随机矢量的联合概率密度函数定义为(1-3-3)设集合由类模式组成，第类记为。类的模式特征矢量的分布函数及密度函数分别定义为(1-3-4)(1-3-5)㈡随机矢量的数字特征⑴均值矢量(期望矢量)维随机矢量的数学期望定义为(1-3-6)其中，的分量i是各随机分量的均值，即(1-3-7)式中，是的第个分量的边缘密度。⑵条件期望在模式识别中，经常以类别作为条件（即，），在这种情况下随机矢量的条件期望矢量定义为(1-3-8)⑶协方差矩阵随机矢量的自协方差矩阵表征各分量围绕其均值的散布情况及各分量间的相关关系，其定义为(1-3-9)式中是的个分量与第个分量的协方差，当时，便是的方差。(1-3-10)⑷自相关矩阵随机矢量的自相关矩阵定义为(1-3-11)由定义可知，的协方差矩阵和自相关矩阵间的关系是(1-3-12)⑸相关系数(1-3-13)由布尼亚科夫斯基不等式知所以(1-3-14)相关系数矩阵定义为⑹协方差矩阵的非负定性显然，协方差矩阵和自相关矩阵都是对称矩阵。设为对称矩阵，对任意的矢量，是的二次型。若对任意的恒有则称为非负定矩阵。如果对任意的，恒有则称为正定矩阵。对于正定矩阵，各阶主子式非零(包括)。协方差矩阵是非负定的。㈢随机变量、随机矢量间的统计关系⑴不相关随机矢量的第个分量和第个分量若有（协方差为0）则称它们不相关。和不相关等价于(1-3-15)随机矢量和不相关的充要条件是互协方差矩阵，亦即(1-3-16)⑵正交随机矢量和若满足(1-3-17)则称和正交。⑶独立随机矢量和的联合概率密度函数若满足(1-3-18)则称和独立。（4）两者关系独立必不相关，反之不然。独立性是比不相关性更强的条件。㈥随机矢量的变换设随机矢量是另一随机矢量的函数，即若它们的函数关系一一对应，这两个随机矢量的概率密度函数之间有关系式中，雅可比行列式(1-3-19)J表示变换后体积微元的变化，坐标系中体积微元，表示的绝对值。当和之间只是线性变换时，此时，，表示矩阵取行列式，从而随机矢量的概率密度函数式中表示行列式取绝对值。设的均值矢量为，协方差矩阵为，则的均值矢量的协方差阵1·4正态分布在概率论、数理统计及决策理论的研究和应用中，正态分布是一种最重要的分布。㈠正态分布的定义⑴一维随机变量的正态分布正态分布的一维随机变量的概率密度函数定义为(1-4-1)式中，为随机变量的数学期望，是的方差。它们分别由下式定义和算得(1-4-2)(1-4-3)随机变量的概率密度函数由两个参数和就可以完全确定，可记为～或～任何随机变量的概率密度函数都满足下式，正态分布的随机变量也不例外。(1-4-4)(1-4-5)随机变量在其均值周围散布。在以为中心的区间中出现的概率所以越大，随机变量的取值的分散程度也越大。图(1-4-1)(a)二维正态分布概密函数，(b)二维正态分布等概密点轨迹⑵多变量正态分布元正态分布的随机矢量的概率密度函数定义为(1-4-6)式中，为的数学期望矢量，为的协方差矩阵。(1-4-7)(1-4-8)它们的元素(1-4-9)(1-4-10)式中，和为的边缘分布概密，为随机矢量各分量定义域的直积空间。易知为对称正定矩阵。㈡多元正态分布的性质多元正态分布有许多易于分析和十分有用的性质，下面给出一些重要的内容。⑴正态分布完全由和确定元正态分布随机矢量的概率密度函数由均值矢量的个分量和协方差阵的个独立阵元所完全确定。多元正态分布的随机矢量常简记为～或～。⑵等概率密度点的轨迹为一超椭球面由式(1-4-6)可知，当指数为常数时，的值不变，因此等概率密度点应满足常数(1-4-11)易证上式的解是一个超椭球面，其中心为，椭球面的形状由确定，取不同的就对应不同的超椭球面，每个等概密椭球面的主轴在协方差矩阵的特征矢量方向上，其长度与相应的特征值的方根成正比。上式中的值称为到的马氏(Mahalanobis)距离，对应于马氏距离为的超椭球的体积为(1-4-12)其中是维单位超球体的体积可知，对于取定的维数，的散布程度只与有关。由所定义的椭球体包含的概率值，其中是自由度为的-分布的上百分位数。⑶对于正态分布，不相关与独立是等价的如果多元正态分布随机矢量的两个分量和之间是不相关的，则它们之间一定是独立的。这是因为若和不相关，由定义，它们的协方差，从而协方差阵成为对角阵进而因此(1-4-13)上式正是独立性的充要条件，从而证明了上面等价性的结论。⑷多元正态随机矢量的边缘概密和条件概密仍是正态分布下面只给出二元情况的证明，更多元的情况是类似的。由可得由定义可算得(1-4-14)同理，可以推出～。由贝叶斯定理(1-4-15)并由上面推导可知，可表为～(1-4-16)同理也可以导出的函数形式。一般性的结论是，设～，，，，在条件下，的条件概密函数～(1-4-17)这里、的维数与的行数相同，、的维数与的行数相同。⑸多元正态随机矢量的线性变换仍为多元正态随机矢量证：设～，为非奇异阵，令，有，雅可比行列式，于是的概率密度函数与的概率密度函数之间的关系为上式中的表示行列式取绝对值，由于由上面诸式可得即得证～由于是对称阵，必存在非奇异矩阵，使的协方差阵为对角阵，此时的各分量彼此独立。这表明可以通过某种变换使变换后的各分量相互独立。更一般的有，如果～，是秩为的矩阵，，则服从正态分布。⑹多元正态随机矢量的分量的线性组合是一正态随机变量这实际上是性质⑸简单的引论。若～，则是一个正态随机变量，～。令为非奇异阵，由性质⑸知，～，又由性质⑷知，～。习题（1.1）试证明，对于正态分布，不相关与独立是等价的。（1.2）试证明，多元正态随机矢量的线性变换仍为多元正态随机矢量。（1.3）试证明，多元正态随机矢量的分量的线性组合是一正态随机变量。第二章聚类分析2·1聚类分析(ClusteringAnalysis)的概念㈠基本思想根据各个待分类的模式特征相似程度进行分类，相似的归为一类。是无监督分类。㈡特征量的类型由于分类对象或目的不同，对象的特征数值化结果有下述三种类型：⒈物理量：直接反映特征的实际物理意义，如长度、重量、速度等。处理前需要对这些连续量离散化。⒉次序量：按某种规则确定的特征的等级，它只反映次序关系。是离散量，如产品的等级、人的学识、技能的等级、病症的级或期。⒊名义量：用数字代表的各种状态。如男性与女性、事物的状态、种类等，无数量含义，也无次序关系。㈢方法的有效性取决于模式特征点在特征空间中的分布情况。如果特征点按类群聚，则分类方法一般是有效的，反之则否。应重新提取特征，选取它们之间显著不同的特征。⒈特征选取不当使分类无效图(2-1-1)(a)所示⒉特征选取不足可能使不同类别的模式判为一类如图(2-1-1)(b)，图(2-1-1)⒊特征选取过多可能无益反而有害，增加分析负担并使分析效果变差若新增加的特征和原有特征是相关的，这样并没有引入更多的有用信息但增加了数据的冗余。除了计算量增加外，更为严重的是，由于多了一些相关的特征，可能使对不同类具有显著差别的重要特征在各种特征“总合”中占的比重变小。引入对各类均无显著差别的特征也会产生这个问题。特征量纲选取：应尽量选用不受量纲影响的相似性测度。2·2模式相似性测度定义模式相似性测度，描述各模式之间特征的相似程度。㈠距离测度(差值测度)两矢量的距离定义应满足下面的公理：设矢量和的距离记为，⑴，当且仅当时，等号成立，即；⑵；⑶；需要指出，模式识别中定义的某些距离测度不满足⑶，只是在广义意义上称之为距离。下面给出距离测度的几种具体算式。设，。⑴欧氏(Euclidean)距离(2-2-1)⑵绝对值距离