支持向量机及其他核算法在化学计量学中的应用

支持向量机及其它核函数算法在化学计量学中的应用陈念贻收稿日期：2002-06-10；修回日期：2002-09-10资金资助：国家自然科学基金委和美国福特公司联合资助，批准号：9716214收稿日期：2002-06-10；修回日期：2002-09-10资金资助：国家自然科学基金委和美国福特公司联合资助，批准号：9716214作者简介：陈念贻（1931-），男，教授，研究方向：计算机化学(1.上海大学化学系计算机化学研究室，上海，200436;2.上海交通大学图象及模式识别研究所，上海，200030)摘要:化学、化工领域中多数数据处理问题属于数学中的“不适定问题”（ill-posedproblem）,而传统的化学计量学算法如线性和非线性回归，人工神经网络等忽略了这一特点，将其作为“适定问题”(well-posedproblem)求解。是引发数据处理中“过拟合”问题的重要原因。近年来新提出的“支持向量机算法”适合于处理不适定问题，能限制过拟合，且因采用核函数算法，能有效处理非线性数据集。和当前化学化工中应用极广的人工神经网络相比，优越性明显。在化学化工中具有巨大的应用潜力。关键词:不适定问题;过拟合;支持向量机算法;化学化工中的应用中图分类号：O06-04ApplicationofSupportVectorMachineandKernelFunctioninchemometricsCHENNian-yi1,LUWen-cong1,YEChen-zhou2,LIGuo-zheng2(1.LaboratoryofChemicalDataMining,DepartmentofChemistry,ShanghaiUniversity,Shanghai,200436,China)(2.InstituteofImageandPatternRecognition,JiaotongUniversity,Shanghai,200030,China)Abstract:Inthefieldsofchemistryandchemicalengineering,mostofthedataminingproblemsareactually“ill-posedproblems”.Butthetraditionalmethodsinchemometrics,suchaslinearornonlinearregressionandartificialneuralnetworks,usuallyignoretheill-posedcharacteristicsandtreatthemas“well-posedproblems”.Thisignoranceusuallyinducessignificantoverfittingproblems.Anewlyproposedtechniqueofdatamining,called“supportvectormachine”,issuitableforthedataminingofill-posedproblems,withoutsignificantoverfitting.Besides,sincekernelfunctionisusedinthismethod,itisverysuitableforthedataminingofnonlineardatasets.SincethisnewmethodhassignificantadvantagescomparedwithANN,whichisnowwidelyusedinthefieldsofchemistryandchemicalengineering,supportvectormachineexhibitsgreatpotentialitiesformanyapplicationtopicsinchemistryandchemicalengineering.Keywords:ill-posedproblem;overfitting;supportvectormachine;applicationsinchemistryandchemicalengineering.许多化学化工中的数据处理问题都是数学上的“不适定问题”(ill-posedproblems),而传统的化学计量学算法将其当作适定问题求解建模，是造成过拟合的重要原因在各种化学，化工的研究和应用工作中，经常要从已知数据中总结规律，用以预报未知。自从计算机技术长足进展以来，应用计算机从已知数据中总结规律，即所谓“机器学习”(machinelearning)的应用已很普遍。除传统的线性回归外，人工神经网络和各种模式识别技术都在广泛使用。并已取得许多成果。当数据的规律接近线性时，用线性回归总结规律，通常认为是标准的、最可靠的方法。如果规律偏离线性，则通常用人工神经网络总结规律，或在线性方程中添加平方或其它高阶项作非线性回归这就是当前化学化工领域中常用的数据处理算法。数据处理，总结数学模型的目的是为了预报未知。但是在实践中，人们经常发现用上述各方法总结的数学模型对已知数据（即所谓训练集）常能拟合较好，而在预报未知样本时，偏差往往较大。当训练样本较少，而影响因素（自变量）较多时，亦即在小样本问题中此问题尤其严重。在数学上将这种现象称为数学模型的“推广能力”（generalizationability)不足的问题。如何提高算法和数学模型的推广能力，以确保我们预报结果的可靠性，显然是化学化工数据处理中非常重要的课题。这其实就是如何避免“过拟合”(overfitting)和“欠拟合”(underfitting)现象的问题。可举本论文系列中报导的氧化铟半导体薄膜的厚度预报为例。根据薄膜厚度和影响因素（溶液成分，粘度，提拉速度，提拉次数等）对应的实测数据，用PLS线性回归总结出的数学模型厚度预报值和厚度实测值的对照图如图1。图1氧化铟半导体薄膜厚度PLS计算值与实测值的对比Fig.1Thecomparisonoftheexperimentalandcalculatedvalues(byPLS)ofthethicknessofindiumoxidesemiconductingfilms容易看出：实测数据对预测的直线关系有系统偏离。若用一条二次曲线拟合会更好。但普通的PLS程序只提供线性方程供拟合之用。这就产生拟合不足即“欠拟合”现象，从而在预报时要造成偏差。如果我们用人工神经网络拟合，则因为三层人工神经网络拟合能力极强，有能力拟合任何函数。如果拟合彻底，就会连实验数据点分布不均匀，实验数据的误差等等“噪声”都按最小二乘判据拟合进数学模型。这当然也会造成预报的偏差。这就是“过拟合”的一个实例了。当然，按照传统的统计数学，我们应当将噪声看成“白噪声”，当训练样本数趋于无限大时，噪声总影响趋近于零。换言之，根据统计数学的大数定律：统计规律只有当训练样本数趋于无限大时，才能精确地总结出来。但是，在多数化学化工课题中，样本数是有限的，一般只有几十个或几百个，甚至更少。因此，以传统的统计数学为基础的各种算法，不可能有效地控制过拟合。现在在更普遍的范围内对此问题进一步讨论：设有化学化工课题的目标值为y，影响因素包括x1,x2,x3……xn。按传统统计数学应将问题表达为：y=f(x1,x2,……xn)(1)然后按最小二乘判据拟合求精确解。换言之，这种计算策略的前提是：通过拟合能够获得唯一的精确解。这只有当上述问题属于数学上的“适定问题”才是正确的。但实际上，化学化工中我们要解决的实际问题，多数是数学上的“不适定问题”(ill-posedproblems)或称“病态问题”。因为：（1）上式左右两侧的实验数据测量中都难免有误差，因此y值和各x值都在置信范围内有不确定性；（2）上式中右侧的自变量中，有时是取控制目标值，例如我们控制样品制备炉温为1000℃，实际上控制的温度是在10005℃范围波动，因此温度值也有某种不确定性；（3）上式右侧的自变量中，有时采用某种估计值，例如在QSAR计算中，常根据量子化学参数，如ELUMO、EHOMO、Hansch分析的疏水性参数KOW等对生物活性找关系。但这些估算值都有误差。例如许多未知分子的KOW值通常用碎片常数和结构因子加合计算，但有些碎片常数波动范围高达20％…仅就因为这些原因，就已经决定了（1）式根本不是一个精确方程式。我们不应该要求拟合精度最高的唯一解，而只应指望得到无限多的一组解。否则我们得到的拟合精确解只能是连有限样本的误差也拟合进去的解，给过拟合提供了条件。其实，问题尚不止此。因为：（1）由于许多化学化工问题极其复杂，在求数学模型时难于肯定自变量是否取完备了，如果忽略了某因素，上式总会造成欠拟合误差；（2）有时由于拟合算法的限制，不可能避免欠拟合。在化学化工工作中常用线性算法，而实际数据又常常或多或少带有非线性的情况下，欠拟合是不可避免的。在这种情况下，追求拟合的最精确解更是没有意义的。以上是以拟合求定量模型为例说明化学化工中数据处理的不适定性质。如果考察一下分类判据问题，则会发现不适定特征更为明显。例如：对于偏置型数据文件，用PLS或Fisher法都可求分类判据，但所得的判别方程式总是不相同的。又如，用各种特征筛选算法处理数据文件，所得的结果也往往不同甚至互相矛盾。实际上无法要求唯一的“精确解”。因此，对于化学化工中这些不适定问题的求解，不应当象传统的化学计量学方法那样用拟合求唯一的“精确解”，而应当在承认误差和欠拟合造成的不确定性的前提下，设法以某种合理的判据，从一组解中找出预报能力最强，或过拟合最小的解，作为我们的数学模型。这里要解决的问题是：如何在追求合理的拟合精度的同时，最大限度地控制或限制过拟合？这就是“小样本数据集”的统计学习理论要解决的问题。这个问题不止是化学化工领域特有的问题，而是几乎所有“机器学习”实际上都有的共性问题。以“大数定律”为基础的、传统的统计数学没有给这一重要的实际问题以答案。从二十世纪六十年代开始，以Vapnik为代表的少数数学家就认识到上述问题的重要性，孜孜不倦地开展了严格的数学理论研究。一直到1992年，在第五届计算机学习理论年度讨论会上发表了根据他们创立的“统计学习理论”(statisticallearningtheory,简称SLT)建立的数据处理新算法“支持向量机算法”(supportvectormachine,简称SVM)后，由于该算法不但理论基础严格，而且在解决图象、语音识别和生物信息学的基因表达研究中取得优异成绩，遂引起了计算机科学界的重视。从那时起，几种重要的有关学报已发表了数百篇论文，掀起了研究SLT和SVM的热潮。最近，有关学术刊物“MachineLearning”等都为SVM出版专刊，说明该算法的理论和技术上已趋成熟。应用范围也在迅速扩大。2001年开始，国际上已开始有SVM用于QSAR和药物设计的论文发表，说明SVM也开始扩大应用于化学领域。近一年来，我们将SVM以及SVM中应用的核算法(kernel-basedmethods,简称KMs)广泛地应用于分析化学的多变量校正(multi-variatecalibration)和数据处理、商品检验、材料研制的实验设计、相图评估和新化合物的预报、有关环境污染的数学模型和赤潮形成研究、精密化工的配方设计等领域，多数结果表明：SVM算法在这些问题上应用中的预报效果，常优于原有的化学计量学中常用的人工神经网络、PLS、Fisher法等算法。根据SVM法预报，还发现了Cs2CaF4等新化合物，纠正了前人一个相图测定中的失误。这些初步研究结果表明：SVM在化学化工领域也必将成为一种重要的数据处理算法。Vapnik学派根据他们建立的统计学习理论，成功地解决了过拟合的控制问题，提高了新算法的预报能力传统的模式识别分类算法认定空间维数n和训练样本数l之比是决定过拟合的因素，规定在分类问题中，样本数必须较空间维数大三倍以上，最好大十倍以上。但在许多实际课题中，样本数少而影响因素多，达到此要求常有困难。因此传统的模式识别算法极其需要特征筛选(featureselection)或通过投影降维。Vapnik学派建立的统计学习理论从理论上证明：对于多维空间中线性可分的分类问题，其误报率的上限主要由下列三个因素中最小的一个因素决定：误报率EPerror≤min(m/l),(R2||w||2/l),(n/l)(2)此处三个因素分别为：(n/l)是空间维数n和训练样本数l之比，(m/l)是“支持向量”数m和训练样本数l之比。此处“支持向量”是指在多维空间中距离最佳分界面最近的那一部分训练样本（见图2），(R2||w||2/l)中R是包络全体样本点的超球半径，(||w||2/l)的倒数代表两类点分布区中间空白（没有样本点）间隔宽度。图2两类样本点分布区的空白间隔和支持向量示意图Fig.2Amapforillustrationofthesupportvectorandtheblankregionbetweentheregionsofdistributionoftwokindsofsamplepoints由此可见：训练样本数和空间维数并不是控制过拟合的唯一因素。如果能充分利用另外两个因素，即设法使两类点中距离分界面最近的点在全体样本中所占比例降低（压低m/l比值），或设法加大两类点分布区中间空白区的宽度（增大l/||w||2比值），都能压低过拟合。据此，SVM算法与传统的模式识别算法相反，不强调降维而采用升维技术。利用适当的升维手段使形成的高维空间中两类样本点线性可分，并能有较小的支持向量数，两类点分布区间空白区较宽。求出距离两类点最远的分类“最佳超平面”作为分类判据，就能建立预报能力好的数学模型（见图3）图3支持向量在全体样本中的比例和两类点分布区空白间隔宽度对误报率的影响（示意图）Fig.3Amapfortheillustrationoftheinfluenceoftheratioofthenumberofsupportvectorstothenumberofallsamples;(b)thewidthoftheblankregionbetweenthedistributionregionsoftwokindsofsamplepointstotherateofcorrectnessofprediction.Vapnik学派在建立SVM分类算法后，又于1995年提出SVM的定量拟合的回归算法，即支持向量回归(supportvectorregression，简称SVR)。这一新算法基于两个基本概念：不敏感函数和||w||2的最小化。不敏感函数的涵义是：当函数拟合到残差小于（此值根据留一法预报效果最佳决定）时，即不再要求进一步减少残差。这样得到的不是唯一解而是一组解。然后根据增强预报能力的要求，从中选出预报能力强的唯一解。选择的标准是使回归方程的系数平方和||w||2极小化。其几何意义为使拟合的超曲面尽量达到“平坦化”（flatness）。这一判据可从下面两方面理解：根据误差传递理论，回归方程总误差和各自变量的误差i间的关系为：总误差等于各自变量的误差与其回归系数乘积平方和的平方根：总误差＝(wii)21/2(3)由此可见：回归系数愈大，则拟合总误差也愈大。限制回归系数或||w||2不过大，可以达到限制过拟合的目的。非线性回归比线性回归有更强的“多解性”。因为在特征空间中，从理论上说通过有限个点的超曲面的数目是无限多个。使||w||2极小化就能排除那些涨落大的超曲面，避免无缘无故设定许多极大和极小点，而选取较有根据、较为可信的拟合结果。当然，对于小样本集而言，其包含的信息量较小，完全避免预报失误是不可能的。SVM算法所能做到的，只是尽可能避免传统算法的失误造成的信息流失，减少由此产生的误报。比如说：如果小样本数据集遗漏了客观上确实存在的极大或极小点，靠SVM的“平坦化”判据当然也不可能避免误报的（见示意图4）。图4若存在未知的极大，极小点，SVM也会误报Fig.4Ifthereexistssomeunknownmaximumorminimumpoint,SVMalsocannotgiveuscorrectprediction.3Vapnik学派在SVM算法中，巧妙地利用核函数（kernel）达到升维而不大批增加可调参数的目的，同时也解决了用线性算法解决非线性数据处理问题采用核函数是SVM算法成功的一大技术关键。SVM的成功还引发了利用核函数改造PCA、PLS、Fisher法等传统的模式识别算法，使之更适合非线性数据集的运算的研究热潮。多数化学化工数据文件带有一定程度的非线性，只靠线性算法不能最有效地作数据处理。为解决此问题，传统的化学计量学算法之一是采用人工神经网络，但这会引起过拟合和局部极小等问题；另一算法是在线性方程中添加平方项或高阶项。但这会引起可调参数大批增加，有时能造成“维数灾难”使计算无法实施。SVM使用另一种算法核函数算法(kernel-basedmethods,简称KMs)解决处理非线性数据的问题。核函数算法的创立，可以追朔到1964年Aizerman提出的势函数法。该法在化学计量学中被看成是KNN法的一个变种。其物理模型是：设想每个“1”类点带一个正点荷，每个“2”类点带一个负电荷，这些电荷形成的电场充满在特征空间中。任何一个测试样本处的电场应等于正负电场之和。按库仑定律，正负电场+，分别等于：+=1/di=-1/dj(4)按上式将原始自变量（如各训练样本点的坐标等）变换成非线性函数+,后，只要用下列简单的线性式算出该处总电场的符号，便可判别测试样本的类别：＝+＋(5)这样，即使原来的数据文件是强非线性的，也可通过(4)式的变换将其化为线性方程(5)式运算求解。图5势函数法将非线性问题转化为线性问题建模Fig.5Bypotentialfunctionmethod,somenonlinearproblemscanbeconvertedtolinearproblemsforsolution.势函数法其实是核算法的一个特例。核函数的优越性，就在于它能将一个在原有空间中的非线性问题转化为另一个称为特征空间中的线性问题，而且实际所涉及的计算又都只需在原有空间进行。这就为人们开拓了一条解决非线性算法的捷径。abAizerman虽然早在1964年就提出了实质上是核函数算法的势函数法，但当时人们囿于势函数法的物理模型，未能体会到核函数算法的普遍意义。一直到1992年Vapnik发表的SVM算法巧妙地应用核函数成功，才引起人们对核函数算法的重视，掀起了将传统的模式识别算法如PCA、PLS、Fisher法等加以“核化”（kernelize）的研究热潮，显著增强了这些原来以线性投影为基础的算法处理非线性问题的能力。为了显示核函数算法的效用，我们在此引用本论文系列中镍氢电池材料性能优化计算中一个实例（图6）。计算表明：原来在原有的四维空间中“优”“劣”ab图6镍氢电池材料优化计算引用核函数的效果Fig.6TheeffectofintroducingkernelfunctionontheresultofcomputationfortheoptimizationofthematerialsofNi/Hbattery我们在此针对图6的特例探讨应用核函数改善分类效果的具体原因：我们在以前就曾指出：特征空间中两类样本点分布的有序性可分为“整体有序”和“局部有序”两大类（图7）。传统的模式识别线性投影算法一般只能显示整体有序，而KNN方法只能显示局部有序。容易理解：径向核函数K(x,x’)=exp(x-x’)2/2也是显示局部有序的有用参数。径向核函数与能显示整体有序的Fisher法相结合，自然能同时具有显示两类有序的能力。这就是在Fisher法中引入径向核函数能显著改善两类样本点分类的原因。图7整体有序和局部有序（示意图）Fig.7Amapfortheillustrationof“globalorder”and“localorder”核函数的定义是：若x,z都是空间X中的向量，是能将空间X中的向量映射到另一空间F的算子，则函数K(x,z)=(x)(z)为核函数，此处符号代表内积。在SVM计算用软件中，有一批常用的核函数供选择，并能根据留一法预报正确率最高为判据，搜索最佳核函数供计算用。此外，我们也将核函数算法与我们以前使用的PCA、PLS、LMAP和Fisher法相结合，发展各种核函数算法。4SVM和其他核函数算法在化学化工领域应用前景的估计：经过三十年的理论准备和十年的算法研究，SVM及核函数算法在理论和算法的整体架构已趋成熟，在文字、人脸、语音识别和基因表达等领域的应用已取得较大成效，在药物设计和QSAR研究的应用已有结果。本论文系列更展示了在广泛的化学化工领域的应用前景根据本论文序列的初步结果，可以估计SVM及其它核算法至少在下列领域有重要应用：（1）实验设计：我们的研究表明：用SVM建立的半导体薄膜质量控制和电池材料的质量优化用的数学模型的可靠性较好。因此SVM可望成为化学实验甚至化工扩大实验的有力工具，对精密化工配方优化设计也可能很有用。（2）商品检验：我们的研究表明：用SVM和微量元素分析相结合，判别茶叶品牌很有效。因此，类似方法很可能对名牌烟、酒等商品的检验和“打假”有用。（3）环境保护：我们的研究表明：SVM在环境保护有关的数据处理方面（如多环芳烃的环化行为研究，汽车尾气排放数据分析，河流海洋污染规律研究等）比现在常用的线性回归和人工神经网络算法更有效。（4）药物设计：国外已有用SVM建模研究药物设计和QSAR的论文发表。我们在本论文系列中也有这方面的工作，估计SVM将成为QSAR和分子设计的有用工具。（5）相图评估和新化合物预报：我们已将SVM用于熔盐相图智能数据库，并根据SVM－原子参数方法预报CsF-CaF2系相图有一个前人忽略了的化合物：Cs2CaF4。据此我们重新测定了这一相图，用差热分析和X射线衍射发现了这个化合