第七章模式识别

1、 第八章 模式识别方法8.1 导言 模式识别方法是50年代早期提出来的，60-80年代在各个学科得到广泛应用。化学学科在此期间发表了数百篇文章。到80年代，模式识别方法发展为一种非常成熟的多元分析方法。 在低维空间如二维、三维空间，人眼对模式识别能力最强，但是在高维空间则必须借助于数学的方法才能够对模式进行区分。 什么是模式识别？ 模式识别属于多元识别方法，它借助于计算机来揭示隐含于事物内部规律的一种综合分析技术。 模式识别是一种从大量信息和数据出发,在专家经验和已有认识的基础上,利用计算机和数学推理的方法对形状、模式、曲线、数字、字符格式和图形自动完成识别的过程。 模式识别包括相互关联的两个

2、阶段,即学习阶段和实现阶段,前者是对样本进行特征选择,寻找分类的规律；后者是根据分类规律对未知样本集进行分类和识别。 模式识别的类型： 有监督模式识别：在模式识别时，如果样品的类别是已知的，先用一组已知类别的化合物作为训练集，建立判别模型，再用建立的模型根据相似性原则来对未知样品进行识别，称谓判别分析。判别分析是在事先知道样本类别的特征的情况下建立判别模型对样本进行识别归属，是一种有监督模式识别。包括线形判别，逐步判别方法，KNN法，SIMCA方法，神经网络等 无监督模式识别：如果预先不知道样本的类别，要在学习过程中根据样本的相似性对被识别的样品进行识别分类和归类，称为聚类分析。聚类分析是完全

3、依靠样本自然特性进行识别的方法，是一种无监督模式识别。包括最小生成树，聚类分析等。 模式识别的研究内容和应用领域： 广义的模式识别属计算机科学中智能模拟的研究范畴,内容非常广泛,包括声音和语言识别、文字识别、指纹识别、声纳信号和地震信号分析、照片图片分析、化学模式识别等等。 模式识别可用来进行有机结构解析，研究定量构效关系，识别真伪商品，追踪污染源，进行药物分类、临床诊断、矿物普查、考古研究、材料设计等。模式识别过程的框图8.2 数据的表示及预处理 在模式识别中，常把实验数据表示为多维空间中的点。对于一次观察（称样本），可用矢量表示为x = (x1, x2, , xn)T 其中xi 为变量i

4、的值，n为多维空间的维数，即变量个数。在模式识别中亦称为特征（feature）。一张图谱可视为多维空间的一个点，它的维数即为从此谱中抽提出的特征数。如C-13 NMR谱，它的特征为化学位移，而对于质谱，它的特征为质/荷（m/e）比。 在n维空间中，两个样本的相似程度反映了n对变量间的接近程度。反过来，这n对变量在多维空间中的距离是与其相互间的相似程度相关的。数据预处理是模式识别中的重要步骤：标准化处理（autoscaling） 1. 其中，xij 为标准化数据。经标准化处理的变量权重相同，均值为零，方差为1n1jijixn1xSnxxiijijn112()iiij ijSxxxmnmmnnxx

5、xxxxxxxX2122221112112. 加权重 加权重仅在有监督的方法中使用，其方法可用一定的经验式统计，给比较重要的变量赋予较大的权重。3.转化 当变量的动态范围较大时，可采用x，x 或 （x + 常数） 等方法进行转化。对于光谱图谱，可采用傅立叶、Hadamard 和 Naesh 等转化。4.组合 将原来的变量，按一定的方式，如变量相加，变量相减等进行组合以产生新的变量。8.3 特征的提取和压缩特征的提取和压缩特征的提取特征的提取 特征的提取在模式识别中是最关键的一步，在化学中所用特征可分为6类：（1）拓扑特征：此类特征由分子的二维联接表派生出来，如原子以及键的属性，记数，原子的连接

6、度，以及各种各样的拓扑指数。（2）几何特征：此类特征由分子的三维模型派生出来，其中包括惯性动量，分子体积，分子表面积和分子的立体参数等。（3）电子特征：如原子电荷，原子半径，键的强度等。（4）物理化学参数：如化合物的疏水性等。（5）化合物的谱图特征：如碳-13 NMR共振波谱中的化学位移，质谱中的峰位（即m/e）等。1.（6）化学组成：如某类物质的无机化学组成及有机化学组成等。2. 特征的压缩 在模式识别中应使特征量数减至最少。一是因为有些特征与分类关系不大，若把这些特征作为模式变量，则可能导致分类结果变差；二是所选择的特征量数目(空间维数)d与样本数n之间要保持一个合适的比例,通常至少是n/

7、d3,最好是n/d10。增加特征量数目d,相应地需要增加样本数n,增加实验费用。 在特征选择中，有一些属于统计方法，如数据的偏差，以所得结果为依据来确定比较重要的特征。另外一些方法是测试特征对分类结果的影响，影响大的选之，否则，弃之，特征的选择在模式识别中尽管研究得很广泛，但尚无一通用理论可以遵循。目前常用选择方法有；偏差权重法 对分类而言，偏差大的变量比偏差小的变量要更重要。特征i 的标准偏差vi为： 其中，为特征 i 之均值，即即Vi值可作为特征选取的一种判据。Vnxxiijijn1112()xnkijxnx112. Fisher比率法 特征i 的Fisher 比率Fi为： 式中，xi1，

8、xi2 分别为类 1 和类 2 中变量的均值， vi1，vi2分别为类 1 和类 2 中变量 i 的标准偏差。 Fi 值越大，意味着变量 i 重要。21221)(iiiiivvxxF3. 概率比率法 概率比率的定义为： 其中， pi1 和 pi2 分别为第 i 个特征在类 1 和类 2 中出现的概率。剔除特征的规则为：（1）在两类中均不出现的特征；（2）在两类中出现次数很少；（3）在两类中出现的概率相同。4. 逐步判别 逐步判别分析为模式识别的一种方法，同时，该种方法亦用于变量的选择。特别是两变量共线，即相关系数较大时，用逐步判别方法可以消去不应选取的变量。21iiipplgR 5. 学习机械

9、法 学习机械（learning machine）法为模式识别的一种方法。同时它可用于特征的选取。在特征选取时首先将判别函数系数 wi 赋予任意初值，如均为“+1”。然后，逐步校正 wi ，直到 wi 不能够进一步改善为止。再将wi均赋值以“-1”，重复如上迭代过程。同样，程序执行到wi 不能进一步改善为止。在两次结果中，剔除 wi 符号有改变的特征。重复如上全部过程，直到再无特征可以剔除为止。6. 主成分分析法 在初选的特征量间可能存在相关，此时亦可采用原特征的线性组合，以形成新的特征量，并根据它们的特点，选取与问题最相关的特征参与以后的分类。 如何进行变量间的组合，主成分分析为我们提供了一条

10、可行的途径。主成分分析所得本征矢量为原变量的线性组合，且本征矢量间相互正交，根据本征值的大小可以选择少量本征矢量作为新的特征。8.4 相似系数和距离 在n维空间中，有向量xi = (xi1, xi2, , xin) 。其中，xij表示 i 第个样本的第 j 个特征。下面介绍在模式识别中常用的相似系数及距离。8.4.1 相似系数1. 夹角余弦如进行图谱比较时，当两张图完全相同时cos ij = 1，完全不同时， cos ij = 0。nknkjkiknkjkikij)x)(x(xxcos112212. 相关系数其中 分别为第 i 个和第 j 个样本的均值。3. 指数相似系数其中， sk 表示第

11、k 个变量的标准偏差。)xx()xx()xx)(xx(rnkjjknkiikjjknkiikij21211nkk)xx(ijsenrjkik124321jixx 和4. 非参数法如果与相似，上述相关系数近于1，否则近于0。nkjkjknkjkijijxxxxr11),max(),min(nkjkjknkjkijijxxxxr11),max(21),min(nkjkiknkjkijijxxxxr11),min(8.4.2 距离 令D (xi, xj) 为样本 xi 与 xj 之间的距离，则在泛函分析中一般要求 D (xi, xj) 满足（1） D (xi, xj) = 0，当xi = xj时（2

12、） D (xi, xj) 0，当xi xj时（3） D (xi, xj) = D (xi, xj)（4） D (xi, xj) D (xi, xk) + (xk, xj)nkqqjkikijxxD11明考斯基距离当q=1时，叫做绝对距离或城市距离（city block）， 当q =2时，即为欧氏距离。nkjkikijxxD1nkjkikijxxD12122. 马氏距离用V表示协方差阵，它的元素用 vij 表示其中，n为变量数。如果V的逆矩阵存在，则马氏距离为 马氏距离在一定程度上克服了由于变量的相关性及变量间量纲不同产生的影响。tjijiijxxVxxD)()(1)xx)(xx(nVjkjnk

13、ikiij1113. 兰氏距离此公式一般对 xij 是同号时使用。nk)xx(xxDjkikjkikij14.海明（Haming）距离5. 塔尼莫特（Tanimoto）距离D = 1 Dij式中，AND，OR，和XOR分别为逻辑操作“与”， “或”和“排斥”。)x,x(OR)x,x(ANDDjkikjkikijnk)x ,x(XORDjkikij18.5 模式识别方法8.5.1 有监督的方法 这一类方法是用一组已知类别的化合物作训练集，并由这个训练集得到判别模型，然后用另外一组已知归属的“未知样本”来测试所得数学模型。在训练中，所得到的识别能力通常称为识别率（recognition）,用测试集

14、所得结果通常成为预测率（prediction）。 在训练集中，如以两类划分为例，在类1和类2中样本数不应差别太大，而以两类样本数相等为宜。Fisher意义下的判别 方法的基本思想：设法找出一最佳投影方向，将m维空间中的点投影到低维空间，如一维空间中，使不同类的点尽可能分离开来，然后在低维空间再分类。 下面以两个母体分类的情况为例： 我们将样本的观察数据记为 xigk i = 1, 2, ,m; g = 1, 2, ,G; k = 1, 2, , ng ; n1 + n2 + + ng = N 其中g表示类，ng表示g中的样本数。投影，实际即为线性变换。m维空间向一维空间的投影可写为： g =

15、1,2; k = 1,2, ng 式中 v = (v1, v2 vm)T 就是我们要寻找的投影方向。令w(Z)和b(Z)分别为Z的组内和组间离差：niigkigkxvz1GgnkggkgZZZw11)()(GgggZZnZb1)()(可以证明：Ggjkjgknkigigkijxxxxwg11)( )( mimjjiijvvwZw11)( mimjjiijvvbZb11)(ggjigiiggijxxxxnb1)(其中及其中为使Z的组间与组内离差比)()(ZWZbr 达到最大投影方向v = (v1, v2 vm)T ，则v应满足0ivr经演算，最终可得到：)(211iimijijxxcvw其中mj

16、jiivxxnnnnrc1212121)(1c与i无关，对所求的v1, v2 vm仅起放大或缩小的作用，并不影响vi之间的相对比例关系。在实际计算时，可取一适当值，如令c=(N-2)以提高计算的精度。（8.1） 由式8.1可求出矢量v，因为投影空间为一直线，则可计算两组样本在投影空间上的均值miigigxvZ1及其在直线上的分解点2211*ZNnZNnZ对于任意给定的 x = (x1, x2, xm)T ，算出它们的判别函数，即投影点：当Z（x）Z*时，把x归为第一个母体，当Z（x）1时，未知样本所属的类，用获多数“选票”的方法确定。所谓多数选票，即在最近邻的样本中，视其属于哪一类为多，则未知

17、样本就属于哪一类。8.5.2 无监督方法系统聚类分析1. 聚类分析是数理统计中的一种方法，特别适用于样本归属不清楚的情况。它所基于的主要思想是在多维空间中，同类化合物应彼此靠得近些，彼此间的距离小些；不同类化合物应彼此靠得远些，彼此间的距离大些。聚类分析即为如何使相似的样本“聚”在一起，从而达到分类的目的。聚类分析为无监督方法，其中用得最多的为系统聚类法（hierarchical clustering）. 系统聚类的基本思想是首先定义样本之间和类与类之间的距离。在各自成类样本中，将距离最近的两类合并，重新计算新类与其它类的距离，并按最小距离归类，重复此过程，每次减少一类，知道所有的样本成为一类

18、为止。其聚类过程用图表示，称为聚类图。（1）最短距离法定义类Gi 与Gj之间的距离为klGxGxijdminDjlik 其中dkl是样本xk 与xl的距离。也就是说两类之间的距离等于两类中最近样品之间的距离。 设某一步将类Gp和Gq合并成Gr ，则类与距离的递推公式为：iqipirddD,min（2）最长距离法 在此种方法中类与类之间的距离等于两类中最远样本的距离，即klGxGxijdDjlik max显然，最长距离法的递推公式是：iqipirddD,max（3）中间距离法 在中间距离法中，类与类之间的距离既不采用两类之间最近的距离，也不采用最远距离，而是采用最远和最近之间的距离。 如果在某一

19、步将Gp类Gq和合并为Gr ，任一类Gi与Gr的距离的取法可由如下三角形说明。Gi Gi Gq Gp Diq Dip Dpq 由初等几何知道，该三角形的中线为：21222412121）（中线pqiqipDDD04121212222，pqiqipirDDDD当= - 时，就是上述三角形中线。上式即为中间距离法的递推公式。（4）重心法 该方法定义两类之间的距离为对应这两类重心之间的距离。对样本来说，每一类的重心即为该类样本的均值。 设某一步将Gp类Gq和合并为Gr ，它们各含有np, nq, nr (nr =np+nq) 个样本，则此方法的递推公式为：22222pqrqpiqrqiprpirDnn

20、nDnnDnnD（5）类平均法 在该类方法中，类Gp，Gq之间的距离表示为： PIqjGxGxijqppqdnnD221 其中，为类Gp，Gq中的样本数。就是说类之间的平方距离等于各元素两两之间的平方距离的平均。其递推公式为：222iqrqiprpirDnnDnnD（6）可变类平均法类平均法的距离递推公式中对于Gp和Gq之间的距离没有反映进去，可变类平均法将之改进为：2222)1 ()1 (pqiqrqiprpirDDnnDnnD其中，可变，1。（7）可变法 此种方法的递推公式为：22221pqiqipirDDDD其中，可变，1。（8）方差平方和 该方法由Ward提出，故文献中常称为Ward法。该方法基本思想是方差分析。例如：G1=x1, x2=1, 2 G2=x3, x4=4.5, 6 G3=x5=8 G1与G2合并，两类中所有元素的均值为：那么G1与G2方差平方和为：(1-3.667)2+(2-3.667)2+(4.5-3.667)2+(6-3.667)2+(8-3.667)2=15.687若将G1与G3合并，其方差平方和为28.667；若将G2与G3合并，其方差平方和为6.117在这三中分类中以G2与G3合并方差平方和最小，故为最佳方案。37536542141.).(x 一般来讲，该种方法是将某一步中G1, G2, ,Gk类合并成k-1类，而由此