《计算化学》-计算化学-第5章

第5章模式识别方法模式识别方法是20世纪50年代旱期提出的.60-80年代在各个学科得到广泛应用.到80年代.模式识别方法发展成为一种非常成熟的多元分析方法。实际上.我们时时处处都在使用模式识别.如我们用眼睛可以区分道路、房屋、汽车.敲碗通过声音来判别碗是否裂缝.中医凭舌苔和脉搏进行诊断.化学家通过谱图来辨别化合物等。在低维空间如二维、三维空间.人类对模式的识别能力最强.但是在高维空间则必须借助于数学的方法才能对模式进行区分。模式识别方法可分为有管理方法、无管理方法和显示方法等几类。其中.在有管理方法中需要有一训练集。如对于两类的情况.在训练集中.有一些样本属于A类.另外一些样本属于B类.然后交给计算机.计算机经过训练之后则可识别末知样本。有管理模式识别包括线性判别、逐步判别分析、KNN方法、SIMCA方法等;无管理方法包括最小生成树、聚类分析等;显不方法包括变量一变量绘图、线性投影、非线性影射等。返回5.1数据的表示及预处理在模式识别中.常把实验数据表r为多维空间的点。对于一次观察(称为样本).可用矢量表示为式中.xi为变量i的值;n为多维空间维数.即变量个数。在模式识别中.n亦称为变量的特征(feature)或描述符(descriptor)。一张谱图可视为多维空间中的一个点.它的维数即为从此谱图中抽提出的特征数。如13CNMR波谱.它的特征为化学位移.而对于质谱.它的特征为质/荷(m/e)比。下一页返回5.1数据的表示及预处理在n维空间中.两个样本间的相似程度反映了n对变量间的接近程度。反过来.这n对变量在多维空间中的距离是与其相互间的相似程度相关的。在模式识别中.数据的预处理非常重要.因为用于同一分类的各个特征的类型可能差别很大。如有的为谱图数据.有的可能为化合物的物理化学性质或结构方面的特征。数据间不仅量纲不一样.其绝对值大小有时会有几个数量级之差上一页下一页返回5.1数据的表示及预处理1.标准化处理式中.xij为标准化数据。经过标准化处理的变量权重相同.均值为零.方差为1上一页下一页返回5.1数据的表示及预处理2.加权重加权重仅在有管理的方法中使用。其方法可用一定的经验式统计.给比较重要的变量赋予较大的权重值。3.转换当变量的动态范围较大时.则可采用lgx或lg(x+常数)等方法进行转换。对于光谱谱图.可采用傅立叶、Hadamard和Naesh等转换。4.组合将原来的变量.按照一定的方式.如变量相加、变量相减等进行组合以产生新的变量。上一页返回5.2特征的提取和压缩5.2.1特征的提取特征的提取.从某种意义上讲在模式识别中是最关键的一步。在化学中.所用特征大体上可以分为六大类。①拓扑特征.此类特征由分子二维连接表派生出来。如原子及键的属性、计数、原子的连接度.以及各种各样的拓扑指数等。②几何特征.此类特征由分子的三维模型派生出来.其中包括惯性动量、分子体积、分子表面积和分子的立体参数。③电子特征.如原子电荷、原子半径、原子实半径、键的强度等。下一页返回5.2特征的提取和压缩④物理化学参数.如化合物的疏水性(lgp)等。⑤化合物的谱图特征.如13CNMR共振波谱中的化学位移.质谱中的峰位(即m/e比)等。⑥化学组成.如某类物质的无机化学组成及有机化学组成等。在实际工作中.可以提取一种特征.也可进行多类特征的相互组合.其原则是以得到好的分类结果为宗旨在某些情况下可能特征数很多.此时则需对所选特征进行压缩上一页下一页返回5.2特征的提取和压缩5.2.2特征的压缩在模式识别中.应使特征数减少到最小。一是因为有些特征与分类关系不大.若把这些特征作为模式变量.则有可能导致分类结果变差;二是在一般情况下应使特征数大大小于样本数.如，n/f>3.其中n为样本数，f为特征数.而最好满足n/f＞10。在特征选择中.有一些属于统计方法.如数据的偏差.以所得的结果为依据来确定比较重要的特征。另外一些方法是测试特征对分类结果的影响.影响大的选之.否则.弃之。目前.在模式识别中应用较广的特征选择方法有以下6种上一页下一页返回5.2特征的提取和压缩1.偏差权重法对于分类而言.偏差大的变量比偏差小的变量更重要。特征i的标准vi为式中，为特征i的均值.即即vi值可以作为特征选取的一种判据上一页下一页返回5.2特征的提取和压缩2.Fisher比率法特征的Fisher比率Fi为式中，分别为类1和类2中变量i的均值;vi1和vi2分别为类1和类2中变量i的标准偏差。Fi值越大.意味着变量i越重要。上一页下一页返回5.2特征的提取和压缩3.概率比率法概率比率的定义为式中.Pi1和Pi2分别为第i个特征在类1和类2中出现的概率剔除特征的规则为①在两类中均不出现的特征;②在两类中出现的次数很少;③在两类中出现的概率相同。上一页下一页返回5.2特征的提取和压缩4.逐步判别逐步判别分析为模式识别的一种方法.同时.该种方法亦用于变量的选择。特别是两变量共线.即相关系数较大时.用逐步判别分析可以消去不应选取的变量5.学习机械法学习机械((learningmachine)法为模式识别的一种方法。同时它也可以用于特征的选取。在特征选取时.首先将判别函数系数ωi赋以任意初值.如均为“+1”。然后.逐步矫正ωi，直到ωi不能够进一步改善为止。再将ωi均赋值以“-1”.重复上述迭代过程。同样.程序执行到ωi不能够进一步改善为止。在两次结果中.剔除ωi符号有改变的特征。重复上述全部过程.直到再无特征可以剔除为止。上一页下一页返回5.2特征的提取和压缩

6.主成分分析法在初选的特征量间可能存在相关.此时亦可采用原特征的线性组合.以形成新的特征量.并根据它们的特点.选取与问题最相关的特征参与以后的分类。如何进行变量间的组合.主成分分析法为我们提供了一条可行途径。主成分分析法所得本征矢量为原变量的线性组合.且本征矢量间相互正交.根据本征值的大小可以选取少量本征矢量作为新的特征上一页返回5.3相似系数和距离在n维空间中.有向量其中，xij表示第i个试样的第j个特征下面介绍在模式识别中常用的相似度系数及距离。对于距离.应满足:①试样A和B间及试样A和B自身的距离D必须是②距离必须对称③距离满足三角不等式下一页返回5.3相似系数和距离④当A≠B时当属性为二值.即仅0或1时.则相似度和距离计算的表达式(所用符号及意义见表5.1)可以简化.如试样A位串中“1”的位数试样B位串中“1”的位数

试样A和B位串中共为“1”的位数试样A和B位串中共为“0”的位数上一页下一页返回5.3相似系数和距离由此n=a+b-c+d若采用集合论的表不方式.设xA为值是“1”的xjA的集合;xB为值是“1”的xjB的集合.则并进而有相似度和距离的主要计算公式(所用符号及意义见表5.1)如下。上一页下一页返回5.3相似系数和距离1.欧氏(Euclidean)距离对于连续变量对于二值变量对于集合论其值范围对于连续变量和二值变量分别为∞~0和n~0。在实际应用中.为了避免开平方.所以以它的平方形式表示。上一页下一页返回5.3相似系数和距离海明距离和欧氏距离是明考斯基(Minkowski)距离的特例显然.当t=1时为海明距离.而当t=2时为欧氏距离上一页下一页返回5.3相似系数和距离2.海明(Haming)距离此类距离也称曼哈坦(Manhattan)距离和城市(City-Block)距离。对于连续变量对于二值变量集合论的定义为其值范围.对于连续变量为∞~0;对于二值变量为n~0。对于二值变量.海明距离与欧氏距离的平方值相等。上一页下一页返回5.3相似系数和距离3.塔尼莫特系数此系数也称为牙卡德(Jaccard)系数。对于连续变量对于二值变量对于集合论对于连续变量及二值变量的取值范围分别为-0.333~+1及0~+1。塔尼莫特系数与Dice系数单调一致。上一页下一页返回5.3相似系数和距离4.数尔格(Soergel)距离对于连续变量对于二值变量对于集合论取值范围为1~0。对于二值变量.数尔格距离与塔尼莫特系数相等上一页下一页返回5.3相似系数和距离5.迪斯(Dice)系数迪斯系数也称为杰克诺斯基(Czekanowski)系数及莎荏荪(Srensun)系数.它与电子密度函数重叠的Hodgkin指数大体上是相当的。对于连续变量对于二值变量对于集合论对于连续杏量及二值变量的取值范围分别为-1~+1及0~+1。上一页下一页返回5.3相似系数和距离6.余弦(Cosine)系数余弦系数也称为Ochiai系数.它相当于电子密度重叠的Curbo指数。对于连续变量对于二值变量对于集合论对于连续变量及二值变量的取值范围分别为-1~+1及0~+1。余弦系数与塔尼莫特系数高度相关.尽管二者并不单调一致。欧氏距离、海明距离和塔尼莫特系数及余弦系数的区别在于前者较后者能更有效地表征相比较的二试样中共同缺少的属性(对于连续变量为低值属性)。上一页返回5.4模式识别方法5.4.1有管理的模式识别方法有管理的模式识别方法.是用一组已知类别的化合物作为别练集.并由这个别练集得到判别模型.然后用另外一组已知归属的“末知试样”来测试所得数学模型。在别练中.所得的识别能力通常称为识别(recognition)率.用测试集所得结果通常称为预测(prediction)率。在训练集中.如以两类划分为例.在类1和类2中试样数不应该差别太大.而以两类试样数相等为宜。下一页返回5.4模式识别方法1.Bayes意义上的判别分析(1)正太母体下的判别函数假设由m个变量x1,x2,...,xm组成的每一个个体都来自G个母体A1,A2,...,AG中的一个。今给出一个个体.用矢量记为xT=(x1,x2,...,xm)，现在需要判定来自哪个母体。换句话说.需要把x划归G个母体中的某一个Ag(g=1,2,...,G)。把x看成m维空间中的一个点.Bayes准则就是找出把空间R(m)分为互不相交的G个完备子空间R1,R2,...,RG的一种划分方法。一旦子空间划定之后.任一事物二就必然落在且仅落在这G个子空间中某一子空间Rg中.则把某一个体x划入Ag类。记观测到的试样数据为上一页下一页返回5.4模式识别方法它表不第i个变量在第g个母体中的第k次观测值;ng表不来自第g个母体的观测次数。若N为观测的总次数·则n1+n2+...+ng=N。这时试样的协方差阵为上一页下一页返回5.4模式识别方法S矩阵的逆矩阵记为S-1逆阵兀索记为sij，即对于正太母体.满足Bayes准则的判别数为式中，pg为先验概率.可用代替。判别系数为上一页下一页返回5.4模式识别方法为了分类.可把个体xT=(x1,x2,...,xm)值代入判别函数.算出y1(x),y2(x),...yg(x)，若则把x划归第g*个母体。后验概率的计算公式为其中上一页下一页返回5.4模式识别方法(2)判别效果的检验①检验两个母体之间的判别效果。检验两个母体之间的判别效果可以借助T2的统计量其中上一页下一页返回5.4模式识别方法由于遵从F分布.自由度分别为m和n1+n2-m-1，当F＞Fa，则表明m个变量可以区分两个母,体.即判别效果显著。对于多个母体的情况.可以把各个母体两两配对.通过逐对计算检验.判明各配对的判别效果。上一页下一页返回5.4模式识别方法在实际计算时还可以对上面定义的式子做一些改进.如要检验母体e和f的效果判别时.F统计量可以表达为其中这里Fef遵从F分布.自由度分布是m和N-G-m+1。当Fef＞Fa时.表明判别效果显著。上一页下一页返回5.4模式识别方法②检验对多个母体的判别效果。在检验对多个母体的判别效果时.可用WilksΛ准则。仍将试样数据记为xigk(i=1,2,...,m;g=1,2,...,ng)，它为来自G个具有相同协方差矩阵的m维正太母体。令定义的组内协方差矩阵W=(ωij)m·n，组间协方差矩阵B=(bij)m·n，和总协方差矩阵T=W+B，其中上一页下一页返回5.4模式识别方法WilksΛ准则为U是两个行列式之比.在单个变量情况下.U是组内协方差与总协方差之比。显然.U值越小越有利于G个母体的分类.因此U可以看成是判别能力的度量。由于U分布函数计算困难.可采用Bartlett近似式其中即利用统计量U作χ2检验。计算值大于χ2临界值时·说明m个变量可以对G个母体进行区分。反之.若计算值小于χ2的临界值.则说明分类效果不明显。上一页下一页返回5.4模式识别方法另外.Wilks量还可以用F统计量来近似代替。其中最简单的形式为，m=1.即一维的Wilks量有对于某一变量式中，i表示第i个变量。F越大(U越小)越有利于分类上一页下一页返回5.4模式识别方法2.Fisher意义上的判别分析Fisher在20世纪30年代提出了一种判别方法.即Fisher分析。这种方法的中心思想是.设法找出一最佳投影方向.将，，，维空间中的点投影到低维空间.如一维空间中.使不同类的点尽可能地分离开来.然后在低维空间中再分类。本小节仅介绍两个母体分类的情况。将试样的观测数据记为式中.g为类;ng为类g中的试样数。上一页下一页返回5.4模式识别方法投影.实际即为线性变换m维空间向一维空间的投影可写为式中，就是我们要寻找的投影方向。令ω(Z)和b(Z)分别为Z的组内和组间协方差可以证明上一页下一页返回5.4模式识别方法其中及其中上一页下一页返回5.4模式识别方法在上述式中.为X测试矩阵的相应列均值为使Z的组间与组内协方差比达到最大投影方向，则v应满足上一页下一页返回5.4模式识别方法经演算，最终可得到其中c与i无关.对所求的v1,v2,...,vm仅起放大或缩小的作用.并不影响vi之间的相对比例关系在实际计算时.可取一适当值.如令c=N-2,以提高计算的精度上一页下一页返回5.4模式识别方法由式(5.6)可求出矢量v,应在投影空间为一直线.则可计算两组试样在投影空间上的均值及在直线上的分界点对于任意给定的.算出它们的判ail数.即投影点当Z(x)>Z*时.把二归为第一个母体.当Z(x)<Z*时将x归为第二个母体上一页下一页返回5.4模式识别方法例如：早已发现.在生物体中存在着微量元索。不同的动物.某种元索有一最适的范围。当该种元索低于这个范围时.则会在生理上产生异常.若补充其不足.则有可能恢复正常;相反.如某种元索过剩或浓度偏高.则会产生毒性作用。目前所知生物体所必需的微量元索有Cu,Zn,Mn,Sr,Co,Cr,Ni,Se,V,13,F,Sn,Mo,Si等。为探索微量元索与冠心病的关系.在学者的实验室曾经测定过冠心病人血中Sr,Cu,Mg和Gn共4种元索.其结果T于表5.2中.序号1~13为冠心病患者.序号14~26为健康人。这4种元索分另屿变量x1、x2、x3和x4相对应.即每一试样为由上述变量所构成的4维空间中的一个点。也就是说.G=2,n1=13,n2=13.n1+n2=N=26,m=4。上一页下一页返回5.4模式识别方法Fisher意义下判别分析的计算结果如下式中，为均值矢量方程式(5.6)(右端常数c=N-2)为式中.左端为协方差矩阵W与矢量v相乘;右端为两类均值矢量对应元索相减并乘以c(N-2=24)。上一页下一页返回5.4模式识别方法由此解出判别系数为并可得到及临界值所得到的判别函数对原试样做检查.算出各试样的判别值和判别分类也列于表5.2的最后两列结果表明.试样2和试样15与原归类不相一致。上一页下一页返回5.4模式识别方法3.逐步判别分析逐步判别的基本思想和逐步回归一样.每一步选一个判别能力最显著的自变量进入判别函数.而且在每次选变量之前都对已经进入判别函数的诸变量检验其显著性.如果发现有某个变量由于新变量的引入而变得不重要.即在判别函数中判别能力不显著时.就剔除这个变量.直到判别函数中包含的所有变量判别能力都显著为止。因此.逐步判别分析也可作为模式识别中的一种特征选择方法。逐步判别分析.由于是从众多的自变量中选出最重要的变量构成判另of函数.因而可以增加判别数的稳定性上一页下一页返回5.4模式识别方法设原始数据为上一页下一页返回5.4模式识别方法其计算步骤如下。(1)计算分类均值和总均值上一页下一页返回5.4模式识别方法(2)计算组内协方差矩阵W和总协方差矩阵T上一页下一页返回5.4模式识别方法(3)逐步计算假设已计算l步(包括l=0).判别函数中引入了某L个变量(即l为步数.L为引入的变量数).则第l+1步的计算内容如下①计算出全部变量的判别能力。若xi是未选量.则若xi为已选量.则上一页下一页返回5.4模式识别方法②在已选变量中考虑剔除可能存在的最不显著的变量。这时从已选变量中寻找最大的.即最小的F.假设式中.i∈L表示xi为已选量。作F检验若F≤Fa(Fa为给定值).则把xr从判别函数中剔除出去.其后的计算见③。若F＞Fa.则改为考虑从末选变量中选出最显著的量.这时从末选变量中寻找最小的即为最大的F。上一页下一页返回5.4模式识别方法假设式中，i∉L，表示xi是末选量。作F检验若F＞Fa，则把xr引入判别函数.其后计算见③。上一页下一页返回5.4模式识别方法③不论xr是选入或剔除.都有同样的计算公式首先计算Wilks量然后同时消去W与T两矩阵的第r列上一页下一页返回5.4模式识别方法至此.第l+1步计算结束.其后重复①~③进行下一步计算。上一页下一页返回5.4模式识别方法上面的计算表明.在每一步总是先考虑剔除变量.仅当不需要剔除时才考虑引入。在实际问题中.先引入判别函数的变量.其后又被剔除的情况并不常见。剔除后又被重新选人的情况.理论上不能排除.但实际上是罕见的。在既不能剔除.又无法引入新变量的情况下.逐步计算结束。上一页下一页返回5.4模式识别方法(4)计算判别系数假设引入了L个变量，并且得到ωij(l)，则判别系数的计算为上一页下一页返回5.4模式识别方法(5)判别效果的检验①对G个母体的判别效果。②对e和f两个母体的判别效果。上一页下一页返回5.4模式识别方法(6)判别分类设试样并将之代入判别函数可得若则把x归为第g*类计算后检验概率上一页下一页返回5.4模式识别方法在上述计算中.为了判别变量的显著性,Fa需事先给定。当Fa足够小时.全部变量将会被选中.此时逐步判别分析即为一般判别分析。但是当自变量间由于相关性而引起|W|=0(或接近0)时.逐步判另of将自动放弃一些变量.从而避免了计算上的困难.所以这比一般的判别方法稳妥。Fa取不同的值可以调节最终选人的变量个数。【例5.1】仍以前面冠心病人血中微量兀索的测定为例。为了阅读和比较所得结果的方便.则把原始数据重新列于表5.3中。基本参数是:上一页下一页返回5.4模式识别方法(1)计算分类均值和总均值均值计算结果列于表5.4中(2)计算组内协方差矩阵W和总协方差矩阵T计算结果为上一页下一页返回5.4模式识别方法(3)逐步计算(l为步数.L为引入的变量个数)第一步(l=0,L=0)判别数尚末形成.不必考虑剔除.计算可以看出minUi=U2=0.700058上一页下一页返回5.4模式识别方法F＞Fal=4，故引入。上一页下一页返回5.4模式识别方法第二步(l=1,L=1)变换矩阵得新矩阵上一页下一页返回5.4模式识别方法因判别函数中只有一个变量，此时不必考虑剔除，引入新变量作计算:在上述三个未选量中，U3|2最小，并计算相应F=11.95266＞Fal=4，故将变量x3引入。上一页下一页返回5.4模式识别方法第三步(l=2，L=2)，变换矩阵得新矩阵上一页下一页返回5.4模式识别方法一般在前两步中引入的变量不考虑剔除，继续计算得上一页下一页返回5.4模式识别方法在两个末选量中，U4|23较小.相应的F值为上一页下一页返回5.4模式识别方法第四步(l=3，L=3).变换矩阵得新矩阵上一页下一页返回5.4模式识别方法并算得在此步中首先考虑剔除在已选的三个变量中U2|34最大.计算相应F得故将变量x2剔除。上一页下一页返回5.4模式识别方法第五步(l=4，L=2)，变换矩阵得新矩阵上一页下一页返回5.4模式识别方法在第五步中也应首先考虑剔除.计算得在两个已选量中.U4|3

较大.计算相应F得F=11.44959＞Fa2=4.变量x4不能剔除。转而计算新变量在两个未选量中U1|34;较小，其相应F=5.813033＞Fa2=4，故将变量x1引入上一页下一页返回5.4模式识别方法第六步(l=6,L=3)，将矩阵变换为新矩阵上一页下一页返回5.4模式识别方法继续计算，得首先考虑剔除在三个已选变量中.U1|34最大.计算F值F＞Fa2=4故变量x1不剔除。考虑引入.此时仅x2未引入F＜Fa2=4，故x2不再引入。即在第六步中.既不能将已选变量剔除.又不能将末选变量引入.故计算结束最终选出变量为x1、x3和x4。上一页下一页返回5.4模式识别方法(4)计算判别数及显著性检验其判别函数为两母体间差异的显著性检验结果为即在显著性水平a=0.01下.两类母体间差异显著。其后检验概率列于表5.3中。对于多类时.如三类.需分别计算D212、D213和D223及F12、F13和F23。上一页下一页返回5.4模式识别方法4.学习方法(1)方法原理学习机械(learningmachine,LM)这种方法也称纠错反馈(error-correctionfeedback)法。最旱由Kowalski等将此种方法用于化学数据.之后被广泛应用于质谱、红外光谱及核磁共振波谱。至今.LM在化学中仍为应用最广泛的方法之一。若为两类划分.就是要寻找一个判别函数.它能够将，，，维空间的点(如化合物)分成两个部分。这个函数在二维空间为一直线.在三维空间为一平面.在多维空间为一超平面。所谓将化合物划分成两部分.就是使化合物分居于超平面的两侧。由于希望超平面通过坐标原点.则将维数增广(如加1)。上一页下一页返回5.4模式识别方法若试样以矢量表示则判别函数可用下式表示其中ωi为权重矢量的分量，ω的求得是通过训练集来实现的。一旦ω获得之后.末知试样x可代入上述公式以计算判函数s的值。若S>0，则将试样x划归为类1;S＜0，则将试样x划归为类2。上一页下一页返回5.4模式识别方法为了求取ω，一开始可将之赋以初值.然后将训练集中的试样一一代入判别函数进行计算.若试样末能得以正确分类.则对ω进行修正.重复计算(即迭代).直至全部试样可以得到正确划分或迭代达到预定次数.则计算结束。很显然.为了完成上述计算.有两个问题需要解决:①如何将权重矢量ω赋初值;②若权重矢量ω不合适.如何对之进行修正。权重矢量ω赋初值的方式有多种.但不同的初值其迭代收敛的速率及最终超平面的位置均不同。一般来说.初值中若已经蕴含类属信息.则可加快收敛速度。其中一种简单的方法是用类平均的矢量差作为初值进行迭代。实际上.最简单的方法是将ωi赋以“+1”或“-1”。上一页下一页返回5.4模式识别方法修正权重矢量ω可用下式计算其中文献上称这种方法为判别平面关于错分试样x的反射(图5.1)。美国学者Jurs等在质谱方面的大量实验表明.这种判别平面反射法在权重矢量修正的方法中是收敛速度最快的一种方法。上一页下一页返回5.4模式识别方法上面我们简单介绍了学习机械法的原理.这种方法在应用中可能会碰到两个问题:①试样的线性不可分;②判别平面的最终位置问题为了解决试样的线性不可分问题.有研究者曾建议一种“‘平均子集学习机械法”。这种方法的基本思想是把训练集分成若干子集.每一子集为线性可分。首先对子集进行训练.然后将所得各子集的权重矢量进行加和，由此得到一平均权重矢量。还有人提出其他方案.此处不再赘述。关于第二个问题及采取的相应措施将在下边两个部分给子介绍上一页下一页返回5.4模式识别方法(2)方法的改良(“死区”训练)判别平面的最终位置不仅与判别平面的初始位置(即权重矢量所赋的初值)有关.而且与训练集中试样的训练顺序有关.由此.有时会导致判别平面落在较差的位置(图5.2(a))。另外.在某些情况下.异常试样点也会导致判别平面落在不适当的位置(图5.2(b))。正如图5.2所示，尽管判别平面可以将训练集中两类进行正确的划分.但其稳定性较差.对于末知试样的预测一般难以得到理想的结果。为了解决这个问题一种改进的方法是“加厚”判别平面.即“死区(deadzone)训练”法。确定“死区”的操作常采用逐步加厚法.即一步一步地将厚度加大.直到训练过程不能够收敛为止在两类间划定一厚度.其判别平面就有可能落在区分两类的最佳位置(图5.3)。上一页下一页返回5.4模式识别方法在有“厚度”的情况下.判别的准则为若S＞t，则为类1;若S＜-t，则为类2;若训练集中所有的试样均可划归为两类中的任一类.则死区为空。实际应用表明.判别平面有了厚度后可以显著提高其划分性能。另外.由于不可分试样落到了死区.所以可使迭代过程收敛(3)判别函数的单纯形最优化前面已经介绍过.LM法的核心是寻找判别矢量ωT(ω1,ω2,...,ωn)。对于同一组训练集.所得ω并非唯一即便是可以100%划分两类试样.所求得的。也不一定为最优.然而.单纯形法为我们提供了达到最优的一条途径。上一页下一页返回5.4模式识别方法假若将正确分类率定义为“响应”.那么最优化的过程就是使响应达到最大。这个过程犹如登山.山就是n维空间中的响应曲面.其坐标轴为ω1,ω2,...,ωn权重矢量。的最优化就意味着登上了这座山的最高处——找到了最大的响应。在模式识别中.所谓最大响应.即使类间得到最好的划分.对于学习机械法.即使判别平面落在最佳判别位置。单纯形就是在n+1维空间中的一个几何图形.如在二维平面上.单纯形为一三角形.在三维空间.单纯形为一四面体.在多维空间为一超四面体。为方便计.假设讨论的为二维最优化问题.则改良单纯形的基本步骤如下上一页下一页返回5.4模式识别方法①为n+1个顶点初始化。所谓初始化.即确定初始单纯形的坐标。如表5.5所不.假若由LM法已经求得权重矢量ωT(ω1,ω2,...,ωn)，那么，ω2,ω3,...,ωn+1可由表5.5中所示方法得到其中，A为常数。②根据重心公式求出重心及反射点。计算单纯形nil个顶点的响应(即对于类与类.如两类划分的结果).求得最佳点WB;、最差点Wω,和次好点WN(图5.4)。重心WC为即在计算重心时.要排除最差点反射点为上一页下一页返回5.4模式识别方法③最佳新顶点的确定(图5.4)。a.假若反射顶点WR比最佳顶点为好.则单纯形扩展到WE。若WE好于WR.则WE:作为新顶点.否则WR为新顶点。b.若反射点WR次于最好点WB.则WR为单纯形的新顶点c.若WR比Wω好，但比WB差，则WR为新单纯形的顶点④迭代的终止。假若训练集为线性可分.则当识别率达到100%时.停止单纯形的寻优过程.若训练集线性不可分时.有人建议.在一次寻优过程中.若10次连续迭代.其响应(识别率)的变化小于100.可放弃迭代.但以最后所得单纯形为一初始单纯形.按照表5.5给定初始坐标的方法重新开始寻优。由几次单纯形寻优所得结果.依具体情况.可以给定一判别.使整个迭代过程终止。上一页下一页返回5.4模式识别方法5.KNN方法KNN(K-nearestneighbours)是在化学上应用得最为广泛的一种模式识别方法。该种方法可用于线性不可分的多类化合物的识别。如图5.5所示学习机械(LM)法对其无能为力.因为无法画出一条直线将图中二类分开.而KNN方法则可用于此种情况的试样分类。上一页下一页返回5.4模式识别方法(1)基本原理KNN为有管理的方法.但它不需要对机器进行已知试样的训练。这种方法的基本思想是在，了维空间中要找到与末知试样最近邻的点(如化合物).而将末知试样归入所属的类为此.则需计算在n维空间中末知试样与所有已知试样间的距离。关于距离的测量.可用欧氏距离、海明距离和塔尼莫特距离等。在划分中.最近邻的个数通常以“K”标注。近邻个数为1时.即K=1.为1NN方法;当K=3时.为3NN方法……。当K＞1时.末知试样所属的类.用获多数“选票”的方法确定。所谓多数选票.即在最近邻的试样中.视其属于哪一类为多.则末知试样就归属于哪一类。因而一般K采用奇数。如图5.6所示,K=3,其中两票(即两个最近邻)属于类1，一票(即一个最近邻)属于类2.因而末知试样归入类to另外.最近邻试样对于“选票”所起的作用.则可用相应的距离将之赋权。上一页下一页返回5.4模式识别方法式中.Vi为对于两类划分.当其近邻属于第一类时.为“+1”,属于第二类时.为“-1";Di为未知试样与第i个近邻的距离;k为最近邻数。当“票选”V总＞0时.则末知试样归入类1;否则.末知试样归入类2。上一页下一页返回5.4模式识别方法(2)K值选择为了测试K个最近邻试样的风险值(risk)可用下式式中.a为常数;δ(k)为K个末知试样最近邻的已知试样的平均距离;R*为期望Bayes值。由上式可见.若要使Ri(k)变小.可增大K值.使1/K项减小.但当K值增大时.式中另一项δ2(k)也增大.也就是说.这两项对于风险值Ri(k)的作用是相互矛盾的。如图5.7所示,K值的选择会直接影响到分类结果。1NN时.末知试样属于类1;3NN时.末知试样属于类2;5NN时.末知试样属于类1。究竞如何选择K值.通常由具体情况而定不过经验告诉我们.1NN可适用于多种数据类型。上一页下一页返回5.4模式识别方法(3)类重心法一般KNN方法的最大缺陷是每判别一个试样需计算它与所有已知试样的距离.为此.有人提出类重心法.即将训练集中每类的重心求出.而判别末知试样时仅需计算它与类重心的距离。也就是说.末知试样与哪一类重心的距离最小.则将其归入哪一类。显然.这种方法的计算量可得以大大减小.但由于在数据间关系表达上的过于简化.使此种方法仅适用于特定的数据结构系统。如图5.8所示.末知试样应属于类2.但是由于d(x，c1)＜d(x，c2).则被归入类1。类重心法尽管有上述不足.但是由于计算上的简单性.所以在实际问题中仍有应用上一页下一页返回5.4模式识别方法6.ALKNN方法ALKNN(AlternativeKNN)方法是KNN方法的一种改良。在KNN方法中.对所有的类选取相同的K值。ALKNN方法对K值的选取是根据每类中试样的数目和分散程度进行的.对不同的类可以选取不同的K值。当各类的K;值选定后.用一定的算法对类中试样的概率进行估计.并且根据概率大小对它们进行类的划分。在ALKNN方法中.以xi与gi的凡个近邻中最远一个试样的距离r为半径.以xi为中心.计算相应的超球的体积.并且认为球体积越小.类gi在xi处的概率密度越大。其概率密度可由Loftsgaroden和Quesenberry方程计算。式中.v(xi/gi)为类gi的超球体积.该超球中心为xi，半径为r。上一页下一页返回5.4模式识别方法为了Ki的选择和相应厂的计算.我们采用欧氏距离m维超球体积的一般表达式为式中.Γ为gamma函数。在实际计算中.上述方程根据m的奇偶性可以写成下列两种形式。当m为偶数时当m为奇数时上一页下一页返回5.4模式识别方法注意.在ALKNN计算中Ki≠1.否则概率密度公式中的分子将为零。由此导致分类结果的简并.Ki必须按优化过程选择.即要选出最优的Ki.这样对于各类概率密度P(xi/gi)的测试才能相一致。在经典的KNN方法中.采用依次拿出一个(leave-one-out)试样作为末知来无偏测试分类率。同样.在ALKNN方法中.也采用这种操作.但K不是单个值.而是一组Ki(i=1,2,...,G)。对Ki值的选取可采用下列公式即选取使g(Ki)为极大值的Ki。上一页下一页返回5.4模式识别方法对试样的分类采用后验概率.其计算公式为即试样划归于具有最大后验概率的类中。下面通过一个具体实例来说明上述的计算过程上一页下一页返回5.4模式识别方法【例5.2】如甲状腺病人的某些功能(5项)测定列于表5.6中。其中.正常功能(类1)和病人(类2)各为10个试样首先以第一类(EU)中第1个试样为例.令K=2。步骤1.计算试样1与类1(EU)中其他试样的欧氏距离d(1,i)。上一页下一页返回5.4模式识别方法步骤2.由于K=2,所以选取第二个最小的d(1,i).并以此为半径r.计算超球体积.此时变量为5个.即m=5,r=d(1,7)=0.4679.故步骤3.计算P(x1/EU)。上一页下一页返回5.4模式识别方法步骤4.对于类1(EU)中试样2~10.重复上述步骤1~步骤3的操作.得表5.7当K=3~5时.而且对类1(EU)和类2(HYPO)两类中试样进行步骤1~步骤4的计算。所得g(K)列于表5.8中。由表5.8可见.对于EU和HYPO两类.相应于最大的.即最佳的g(K)值,K均等于2,在此条件下.两类中的概率密度均可得到最佳测定。表5.9所不为两类中所有试样当K=2时的概率密度和后验概率等。上一页下一页返回5.4模式识别方法如已经介绍过的.对于EU.后验概率用下式计算判别试样所属类别用下列规则:若P(EU/xii≥0.5。将试样归入EU类;若P(EU/xi)<0.5.将试样归入HYPO类表5.9结果表明.所有试样均被正确归入所属的类。对于EU类.所有试样的P(EU/xi)近于1.0.而对于HYPO,所有试样的P(EU/xi)近于0.0。上一页下一页返回5.4模式识别方法7.SIMCA方法SIMCA(softindependentmodellingofclassanalogy或statisticalisolinearmulticategoryanalogy)属于类模型方法.即对每类构造一主成分回归的数学模型.并在此基础上进行试样的分类。此法在1976年由瑞典学者Wold所提出.很快受到普遍的重视.并在化学中得到广泛的应用。如有数据阵见表5.10上一页下一页返回5.4模式识别方法对于某一类.主成分回归模型为式中ai为变量i的均值;A为主成分数;βiα为变量i在主成分α上的装载;Θak为试样k关于主成分a的得分;εik为偏差。对于多类，则主成分回归模型为式中.q表示类。上一页下一页返回5.4模式识别方法SIMCA方法分类的主要操作步骤可归结如下。(1)数据标准化若数据来源不一时.变量间彼此差别可能很大.则必须将数据进行标准化(autoscaling)处理。经过标准化处理的每一变量均值为0.方差为1。(2)主成分数A的测定确定S值的最有效的方法为交又验证(crossvalidation)法。这种方法的操作过程如下。①将训练集中的某类分成T组.在分组中要尽可能考虑到试样的代表性.如某类由25个试样所组成.令T=8.即将之分为8组。第一组为1,9,17和25.第二组为2,10和18.第三组为3,11和19等.直到第八组.试样为8,16和24。上一页下一页返回5.4模式识别方法②首先将第一组试样从训练集中除去.并设降维的数据矩阵为Y—.试样数为n—。③对于Y-.应用前述单类主成分模型式(5.9)去拟合。拟合中依次令A=0,1,2,…直到M-2或n-2(取决于二者中小者)。④运用在③中建立的数据模型去拟合所除去的试样。此步中A=0,1,…并且α,β固定不变。相应于每一A值.计算试样的偏差εik，由此得到这些偏差平方的加和△A。⑤将所除去的那组试样重新放回数据阵Y。⑥由数据阵Y中除去下一组试样.从而得到一新的降维数据阵Y—.回到第③步。若每一组均被除去一次.则到第⑦步。⑦对于每一A值.将△A加和得到DA.由(DA-1一DA)/n对DA/[n(M—A一1)]作F检验来判断A的重要性.从而确定A值。一旦每类A值确定之后则可使式(5.10).即多类主成分模型对于试样的判别能力达到极大。上一页下一页返回5.4模式识别方法(3)主成分模型中β，Θ等参数的测定式(5.10)中βia，Θak由矩阵Z(q)TZ(q)对角化求得。其中Z(q)为第q类训练集中每一变量减去平均值后所形成的数据阵.Z(q)T为Z(q)的转置矩阵。εik(q)可由Z值减去公式中β和Θ的乘积项得到.则方差可由式(5.11)求得。一旦每一类中上述参数求出之后.即可运用主成分回归模型预测末知试样上一页下一页返回5.4模式识别方法(4)末知试样测试用主成分回归模型拟合末知试样Yip与一般多元回归相同，此时为因变量，为自变量。式中.ca为回归系数。表征试样p拟合好坏·可由偏差εip的方差表示上一页下一页返回5.4模式识别方法判别试样p是否属于q类.则用F显著性检验。对于类内试样F检验的公式为式中.校正因子的加入是因为当计算该类β和Θ时p试样已被包括进去。将F的计算值与临界值[自由度分别为和]相比较·若F＜F临界，则试样回归入q类.否则.将试样p拟合于其他类。当试样p拟合于其他类时.即p已不是类内试样，其F显著检验的公式为同样将F的计算值与临界值[自由度分别为(M-Aq)和(nq-Aq-1)(M-Aq)]相比较.若计算值小于临界值.则将试样p归入其他类q类.否则试样p为一新类。上一页下一页返回5.4模式识别方法(5)两类间相似度——非相似度测量用类r中的所有试样拟合类q主成分模型.则可得到类间的相似度测量.类r与q间的方差为同样可以得到将式(5.13)所得方差与式(5.11)所得方差相比较.则可得两类间相似度的测量上一页下一页返回5.4模式识别方法(6)变量重要性的测量变量在判别中的重要性可由残余方差(residualvariance)与原始数据的方差相比较而得。若原始数据经过标准化处理.则所有变量:的方差相同由此可得Ui值越大.即残余方差与原始数据方差的比值越小.该变量在主成分模型中的作用越大。上一页下一页返回5.4模式识别方法(7)试样相关性测量与变量相类同.即将试样的残余方差式(5.12)与某一类整个方差式(5.11)相比较(F检验).其残余方差越小.该试样与此类的相关性越大【例5.3】莺尾花的分类。在20世纪30年代.由Fisher所收集的有关莺尾花的数据.是后来常被用于模式识别的一套经典的数据。我们取其一部分.即第一类多刚毛(setose)莺尾花和第二类杂色(versicolor)莺尾花。每类25个试样.两类共50个。对花的描述是:①花警长度(x1);②花警宽度(x2);③花瓣长度(x3);①花瓣宽度(x4)。这50个试样的测试数据及相应的归类示于表5.11中。对于原始数据.每个试样按照类分别减去均值。然后.按照类分别进行主成分分析。取一个主成分.则在主成分回归方程中βia(装载)和Θak(得分)分别于表5.12和表5.13中。上一页下一页返回5.4模式识别方法类1和类2的标准方差分别为S0(1)2=0.0257和以S0(2)2=0.0525。试样分别拟合于两类主成分，回归模型的标准方差及F检验分别表示于表5.14中。两类显著性检验F的临界值相同.即均为F(3,69)a=0.01=4.08。在表5.14中第2和第3列.括弧中数码1或2分别表示用类1模型计算或用类2模型计算所得方差。所以.“最近类”即为此试样最有可能所属的类。“第2个最近类”可依此类推。但是否属于类1或类2.则还要通过F检验来确定。如前所述.假若F的计算值小于F的临界值.则将试样归于此类.否则归于其他类。若某试样不能归于任一类.则该试样为新的一类。依此.观察表5.14则可发现.对于类1模型.试样1~25.只有第23的F计算值(4.64)大于4.08(临界值).故试样23不能归于类1;试样26~50可全部正确归于类2。相类同.对于类2模型.试样26~50均可正确地归于类2;试样1~25.除了试样23.其他均可正确归于类1。由于试样23的F计算值大于临界值4.08.故也不能归于类2。试样23为一异常试样.应归于新的一类。在50个试样中.仅有一个试样不能正确归类.所以识别率为98%。上一页下一页返回5.4模式识别方法5.4.2无管理的模式识别方法1.系统聚类分析聚类分析是数理统计中的一种方法.特别适用于试样归属不清楚的情况。它所基于的主要思想是在多维空间中.同类化合物应靠得近些.彼此间的距离小些;相反.不同类的化合物应离得远些.彼此间的距离大些聚类分析即为如何相似的试样“聚”在一起.从而达到分类的目的。聚类分析为无管理方法.其中用得最多的为系统聚类(hierarchicalclusrering)法。系统聚类法的基本思想是首先定义试样之间和类与类之间的距离。在各自成类试样中.将距离最近的两类合并.重新计算新类与其他类间的距离.并按最小距离归类.重复这些过程.每次减少一类.直到所有的试样成为一类为止。其聚类过程用图表不.称为聚类图。定义类与类之间的距离有多种方法.不同的定义就产生了不同的系统聚类分析方法。常用的方法有8种这些方法如下上一页下一页返回5.4模式识别方法(1)最短距离法这种方法定义Gi与Gj之间的距离为式中dkl是试样xk与xl的距离。也就是说两类之间的距离等于两类中最近试样之间的距离。设某一步将类Gp和Gq合并成Gr.则类Gi与Gr距离的递推公式为上一页下一页返回5.4模式识别方法(2)最长距离法在此种方法中类与类之间的距离等于两类中最远试样的距离.即显然，最长距离法的递推方法是上一页下一页返回5.4模式识别方法(3)中间距离法在中间距离法中.类与类之间的距离既不采用两类之间最近的距离.也不采用最远距离.而是采用最远和最近之间的距离如果在某一步将类Gp和Gq合并为Gr.任一类Gi与Gr的距离的取法可由如图5.9所示三角形来说明。如果用最短距离法.Dir等于Dip和Diq中短的边;如果用最长距离法，Di等于Dip和Diq中长的边。在中间距离法中，Dir既不取Dip，也不取Diq，Dir取的是夹在这两条边之间的三角形中线。由初等几何知道:取当β=-1/4时.Dir就是上述的三角形中线。上式即为中间距离法的递推公式。上一页下一页返回5.4模式识别方法(4)重心法此类方法定义两类之间的距离为对应这两类重心之间的距离。对试样来说.每一类的重心即为该类试样的均值。设某一步将Gp与Gq合并成Gr，它们各含有np,nq,nr(nr=np+nq)个试样，则此种方法的递推公式为上一页下一页返回5.4模式识别方法(5)类平均法在此种方法中.类Gp与Gq之间的距离表示为式中，np,nq为类Gp，Gq中的试样数。就是说类之间的平方距离等于各元索两两之间的平方距离的平均。其递推公式为上一页下一页返回5.4模式识别方法(6)可变类平均法类平均法的距离递推公式中对于类Gp和Gq之间的距离没有反映进去.可变类平均是将其改进为式中，β可变，β＜1。上一页下一页返回5.4模式识别方法(7)可变法此种方法的递推公式为式中，β可变，β＜1。上一页下一页返回5.4模式识别方法(8)方差平方和法这个方法首先由Ward提出.故文献中常称之为Ward法。该方法所基于的思想为方差分析。如某一步中.G1={x1,x2}={1,2},G2={x3,x4}={4.5,6},G3={x5}={8}.若将G1,G2合并.则两类中所有元索的均值为(1+2+4.5+6)/4=3.375.那么方差和为(1-3.375)2+(2-3.375)2+(2-3.375)2+(4.5-3.375)2+(6-3.375)2=15.687。若将G1与G3合并.则其方差平方和为(1-3.667)2+(2-3.667)2+(8-3.667)2=28.667。若将G2和G3合并.则其方差平方和为5.117在这三种分类方案中.以G2和G3合并增加的方差平方和为最小.故将G2和G3合并。也就是说.这种方法是将某一步中G1,G2,...,Gk类合并成k-1类.而由此增加的方差平方和为最小该种方法的递推公式为上一页下一页返回5.4模式识别方法上述几种方法总的递推公式为方法不同.式中αp,αq,β,γ的取值也不同。取值方法示于表5.15中。其中.ni,np,nq和nr为相应类中试样数。在可变法及可变类平均法中的β可变.分类效果与β取值关系极大。β若近于1，分类效果不好。通常β取负值。下面我们以一个极为简单的例子来说明聚类分析方法的步骤。上一页下一页返回5.4模式识别方法【例5.4】如有5个试样.每一试样仅有一个特征:1,2,4.5,6,8。(1)计算试样之间的距离此处选用绝对距离.得表5.16(2)定义类与类之间的距离如采用最短距离法。(3)逐步归类开始时.5个试样各自成一类.类间距离即为试样间距离.即Dij=dij。选择最小的Dij，此时为类G1和G2，将它们合并成新类G6.并计算与其类间的距离.得表5.17。重复如上过程可得表5.18和表5.19.其归类结果如图5.10所示。上一页下一页返回5.4模式识别方法2.最小生成树最小生成树是图论中的一种算法。由图论可知.图G由两个集合组合:一是顶点的集合V(G).另一是边的集合E(G)。图G可记为聚类开始时.图G为所有的顶点相连的连通图。图中顶点为要分类的化合物.边为多维空间中化合物的距离.当从任一顶点遍历图时.必定将边的集合D(G)分成两个集合T(G)和B(G).其中.T(G)是遍历图时所通过的边集,B(G)是剩余的边集。显然.G'=(V,T)是G的子图.称之为连通图的生成树(spanningtree)o所谓最小生成树(minimalspanningtree)即为连通n个顶点的n-1条边的加和。上一页下一页返回5.4模式识别方法最小生成树的生成步骤如下①设T的初态为空集。②在连通图上任选一顶点加人到V(T)集合中去。③将下列步骤重复n-1次;a.在i属于V(T)，j不属于V(T)的边中选取权值最小的边(i,j)；b.将顶点j加入到V(T)中去;c.输出i,j及相应权值ωij。【例5.5】取本章表5.11中两类的各前10个试样.即试样1~10为多刚毛莺尾花;11~20为杂色莺尾花两个试样间的距离即图G中边的权重以欧氏距离量度式中.xik为第i个试样的第k个特征.即莺尾花的花瓣特征。对一组数据.在最小生成树中结点(试样)对及其边的权重值示不表5.20中。上一页下一页返回5.4模式识别方法图5.11所T为该最小生成树的二维影射图.它由主成分分析(K-L转换)方法所得。若由结点4和18间(点间距离最大者)断开.则形成两个部分:左侧全部为类1.即多刚毛莺尾花;右侧全部为类2.即杂色莺尾花。由此可见.此最小生成树反映了原数据空间中数据间相邻关系。上一页返回5.5显示方法如前所述一种化合物总是定义为多维空间中的一个点.但在多维空间中点的分布(即数据结构)是什么样则超出了人类视觉判别能力。假若有办法把这些点投影到低维.如二维或三维空间中则可借助于图不进行化合物的分类。下一页返回5.5显示方法5.5.1线性映射主成分分析(PCA)有多种形式.它们构成了多维数据分析的数学基础。Karhunen-Loeve(K-L)转换是一种形式。该种转换是使二维空间中的两个坐标y1和y2(或三维空间中的三个坐标y1,y2和y3)是高维空间中原坐标x1,x2,...,xn的线性组合.并且y1和y2(或y1,y2和y3)正交。K-L转换为二维(或三维)坐标中引进均方误差最小的一种转换。如在m维空间中n个点的矩阵为上一页下一页返回5.5显示方法它的协方差阵为式中，为m维空间中n个点的重心上一页下一页返回5.5显示方法将协方差阵对角化.则得本征矢量矩阵T和本征值λ1，λ2，...，λm，其中，在如上计算中也可用相关矩阵(见后边数字例子).最终所得结论是一致的。为了在低维如二维空间进行试样点的显不.取与两个最大的本征值λ1和λ2相对应的本征矢量t(1)和t(2)来计算新的坐标y1和y2.上一页下一页返回5.5显示方法但根据情况.有时也取第1,3;2,3或3,4等与本征值相对应的本征矢量进行计算。运用此种方法所得图形的可信度可用下式判定其比率越大.说明λ1和λ2的代表性越强.即所包含的信息量越大.则所得映射图越接近理想情况经验表明.其百分比率一般应大于80%。上一页下一页返回5.5显示方法【例5.6】老年性自内障是老年人弱视力的主要致因。在自内障形成时.不仅Na/K的比例有改变.而且其他金属兀索也相应有所变化。实验室测定了自内障晶体状体和对照组中Ca,Mg,Na,K,Mn,Fe,Cu和Zn等8种金属兀索.其结果列于表5.21中。对原始数据进行了标准化处理用下式计算相关矩阵。式中,rij为变量xi和xj的相关系数.当i=j时.rij=1;下标p=8。上一页下一页返回5.5显示方法运用Jacobi方法计算特征值及与之相应的本征矢量其本征值为上一页下一页返回5.5显示方法与之相对应的前四个本征矢量为上一页下一页返回5.5显示方法利用式(5.16)可计算新坐标y1,y2,...,y8(即主成分PC1,PC2,...,PC8)。以主成分1和主成分