基于元学习策略的分类器融合方法及应用.doc

第10期王浩畅等：基于元学习策略的分类器融合方法及应用13基于元学习策略的分类器融合方法及应用王浩畅1,2, 赵铁军1, 郑德权1, 于浩1(1. 哈尔滨工业大学 计算机与技术学院, 黑龙江 哈尔滨 150001；2. 大庆石油学院 计算机与信息技术学院，黑龙江 大庆 163318)摘 要：提出了基于元学习策略的分类器融合的新模型，使用了两类元学习策略将4种分类算法即Generalized Winnow算法、支持向量机算法、条件随机域算法和最大熵算法进行融合，并根据具体领域的应用任务和分类器特点选择了有效特征信息，在面向生物医学文本命名实体识别的应用中取得了较高识别精度。实验结果表明基于元学习策略的分类器融合方法明显优于单分类器方法，并且也优于基于判别规则的分类器融合方法。关键词：元学习；分类器融合；叠加归纳；级联归纳；命名实体识别中图分类号：TP391 文献标识码：A 文章编号：1000-436X(2007)10-0007-07Meta-learning based classifier ensemble strategy and its applicationWANG Hao-chang1,2, ZHAO Tie-jun1, ZHENG De-quan1, YU Hao1(1. School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China; 2. College of Computer and Information Technology, Daqing Petroleum Institute, Daqing 163318, China)Abstract: A novel meta-learning based classifier ensemble model was presented. Four classifiers i.e. Generalized Winnow, support vector machine, conditional random fields, and maximum entropy were combined using two different meta-learning strategies. Various evidential features specified for the application of biomedical named entity recognition were incorporated into the system to help improve recognition performance. Experimental results show that the classifier ensemble strategy based on meta-learning is obviously superior to the individual classifier based method and superior to the arbitration rule based ensemble method.Key words: meta-learning; classifier ensemble; stacked generalization; cascade generalization; named entity recognition1 引言统计机器学习方法的主要目的之一是解决分类问题，其过程就是通过样本集建立适当的统计模型，以此模型对新的数据进行分类识别。近年来，多分类器融合方法已经成为机器学习和模式识别领域的前沿课题，选择不同的特征或不同的分类器可以得到不同的分类识别结果，这些结果之间往往具有互补性，因此多分类器融合能够有效提高学习系统的分类精度。收稿日期：2007-05-16；修回日期：2007-08-10基金项目：国家高技术研究发展计划（“863”计划）基金资助项目(2004AA11701008，2006AA01Z150)Foundation Item: The National High Technology Research and Development Program of China (863 Program) (2004AA11701008, 2006AA01Z150)以分类为目标的学习算法有着广泛的应用。近年来，随着生命科学研究的飞速发展，大量的生物医学知识以非结构化的形式被记载在各种形式的文本文件中。从海量相关文献中直接获取本领域相关信息并使其变为生物学家可直接利用的知识，是一项迫在眉睫的任务。以MEDLINE数据库为例，这个权威性最高的著名医学文献数据库，其文献总数目前已达到1 600万，近几年每年有60万篇文献发表。因此生物医学领域迫切需要有效的学习算法进行文本知识挖掘。因此，本文以生物医学领域文本知识挖掘为背景，研究多分类器融合方法及其应用。文本知识挖掘的基本任务之一是命名实体识别。其目的是从特定领域的文本集合中识别出指定类型的名称，例如生物医学领域的蛋白质、基因、核糖核酸、脱氧核糖核酸等。这些获取的知识有着广泛应用价值，例如疾病的诊断、预防和治疗。就分类器算法的应用而言，生物医学领域命名实体识别是一项具有挑战性的研究。其主要原因是：新的命名实体不断出现，形成了命名实体开放集；相同名称可能表示不同类别的生物医学命名实体，要依据上下文才能区分；很多生物医学命名实体拥有几个不同的名称。此外，还存在着实体名称过长、复合词多、缩写词比例大、命名实体嵌套等现象。目前，在三类识别方法即基于启发式规则的方法1,2，基于字典的方法和基于统计机器学习的方法3,4中，后一种方法已经成为主流。但是目前国内外用于本任务的大部分识别模型都是建立在单个学习算法的基础上，而且还没有一种学习算法能够取得很好的识别结果。因此，本文提出了应用于生物医学命名实体识别的基于元学习策略的分类器融合方法，实验结果表明其识别精度有了较大幅度的提高。本文其余部分安排如下：第2节介绍了元学习策略中基分类器的算法；第3节详细描述了元学习过程；第4节介绍了本系统中选择的特征；第5节描述了实验设置和实验结果，并对实验结果做了详细的分析；最后给出了结束语。2 算法分类器融合是否有效取决于基分类器的性能和独立性，即要求基分类器有较低的错误率，至少比随机预测的结果要好，并且产生的错误相互独立。基分类器产生的错误相互独立要满足以下任一条件：一是基分类器选用不同的特征描述，二是对于每一个基分类器使用不同的分类方法进行模式分类。使用不同的特征描述集合能够减少基分类器输出结果的相关性。不同的分类方法通常使用不同的关于数据结构的假设和不同的统计模型，这就导致产生不同的后验概率估计。本文研究中采用了4种不同的统计学习算法，即Generalized Winnow、支持向量机（SVM, support vector machine）、条件随机域（CRF, conditional random fields）和最大熵（ME, maximum entropy）作为基分类器算法，提出了基于元学习策略的分类器融合方法，以此方法为基础，应用于生物医学命名实体识别。该方法通过不同分类器的识别能力之间的互补性来提高整体识别性能。下面对4个分类器算法分别加以简要介绍。2.1 Generalized Winnow算法Generalized Winnow算法非常适用于自然语言处理研究中的分类问题，对处理不相关的特征有很好的稳定性。命名实体识别问题可以定义成分类问题。这里用表示文本中的词汇序列，识别的目标是给每一个文本词汇分配一个分类标签，的取值为预先定义的分类集合。学习系统的任务就是预测每一个文本词汇符号的分类标签，通过估计条件概率估计每一个分类标签值，其中是和相关的特征向量。假设，即特征向量依赖于前面预测的分类标签，这种假设是局部依赖。在Generalized Winnow算法中，上述条件概率模型写为以下形式5(1)其中，将截取到区间0,1。是线性权重向量，为常量。参数和能够从训练数据中估计。给定训练数据，模型的估计可以由式（2）给出，它解决了每一个值的最优化问题。(2)其中，当时，否则，功能函数定义如下(3)给定以上条件概率模型，在解码阶段用动态规划的方法估计最可能的序列。2.2 SVM算法SVM是一种基于核函数方法的统计学习方法，主要思想就是将在低维空间不能线性分类的数据通过核函数变换到高维空间，找到对应的超平面来线性分类。高维空间的构建比较困难，然而核函数的存在使得变换时并不需要显式构建高维空间，这使得SVM的应用变得比较方便6。假设有二元分类问题的训练样本，其中是词的特征向量， +1,1 为对应的类别标识。SVM分类器给出输入特征向量x的决策函数f(x)，其目的是预测未知样本x的分类t。最优分类函数为(4)当x为正例时，f(x) = +1；当x为反例时，f(x) = 1。式中为具有非零值的系数，zi 称为支持向量，是x 对应的类别标注，K()为核函数，通过它SVM将线性不可分的样本映射到高维空间, 从而使得这些样本在高维空间线性可分。2.3 CRF算法CRF模型思想主要来源于最大熵模型。可以把CRF看成是一个无向统计图模型或马尔可夫随机场，非常适用于自然语言处理领域当中的标注序列化数据的任务。CRF模型定义了给定文本词序列，标注序列的条件概率。(5)其中，是归一化因子，是特征函数，是学习到的特征函数的权重。CRF算法的详细描述参见文献7。2.4 ME算法最大熵模型是一个在自然语言处理领域应用比较广泛的统计模型，其基本思想是为所有已知的因素建立模型, 对未知事物不做任何假设8，也就是说,要找到这样一个概率分布需满足所有已知的事实，且不受任何未知因素的影响。最大熵模型的一个最显著的特点是其不要求具有条件独立的特征，因此可以灵活地运用各种类型的特征，而不用顾及它们之间的相互影响。假设训练样本，其中 是特征向量, 为对应的类别标识。利用最大熵模型得出的特征限制下最优概率分布，即概率值。根据最大熵原理，概率值的取值符合下面的指数模型(6)(7)其中，为最大熵模型的特征，它是一个二值函数，描述某一个特定的事实。是每个特征的权重,在x一定的情况下为一范化常数。3 元学习策略分类器融合的目的是将不同的成员分类器也就是基分类器进行有机结合，以获得比基分类器更好的分类能力。分类器融合的首要问题是选择合适的融合策略。本文使用两类不同的元学习策略融合基分类器的预测结果，这2种策略分别是叠加归纳法和级联归纳法。叠加归纳法包括类叠加法和类及属性叠加法。元学习是在学习结果的基础上进行再学习或多次学习而得到最终结果9。元学习研究如何从经验中学习以增强学习性能，常见的一种元学习方法称为叠加归纳，简称叠加。叠加法有较强的可扩展性，叠加的层次可以从一层至多层向上伸延，每一层中各个模型可以使用任何分类算法来构造。在介绍叠加归纳过程之前，约定以下符号：x表示待分类的样本实例，给定K个学习算法Lk（k = 1, 2, K），这些学习算法训练获得的K个分类模型表示为Mk（k = 1, 2, K），每个分类模型对待分类实例x的预测分类结果表示为Ck(x)（k = 1, 2, , K），class(x) 和attrvec(x)分别表示正确的分类标识和实例x的特征向量。给定数据集D=(class(xi), attrvec(xi), i=1, I，随机将数据集分成J个大小基本相等的数据集D1,Dj，定义Dj和D(j)=DDj分别为J折交叉验证的第J折测试集和训练集。给定的K个学习算法，称为第0层归纳算法。在训练集D(j)上训练第k个学习算法产生分类器模型Mk(j)，对于模型Mk(j) （k = 1, 2, K），则称为第0层模型，也称为基分类器。对于测试集Dj中的每一个样本实例xi，Cki(xi)表示分类器模型Mk(j)的预测。在交叉验证过程结束后，集合从K个分类器模型的输出结果产生新的数据集DCV =(class(xi), C1i(xi), CKi(xi), i = 1,I，称为第1层训练集，也称为元训练集。使用元训练集训练一个学习算法产生的学习模型Mstack称为第1层模型，也称为元模型或元分类器，算法称为第1层归纳算法。对待分类的新样本实例进行决策时，首先通过第0层归纳算法在训练集D上进行训练学习产生模型Mk(k = 1, 2, K)，对给定的一个新实例，模型Mk生成一个预测向量C1(x), CK(x)，这个向量是元分类器Mstack的输入，其输出为最终预测结果。叠加法由Wolpert 10提出，过程如图1所示。图1 叠加归纳法对于元训练集，包括基分类器的预测和正确分类标识，也可以包含属性特征向量。基于元训练集属性的差异，本文使用2种叠加方案进行实验。类叠加法：元训练集包含基分类器的预测和正确的分类标识，即T = (class(x),C1(x),C2(x), , CK(x) | x D。类及属性叠加法：元训练集包含基分类器的预测和正确的分类标识以及特征向量即T= (class(x), C1(x),C2(x),CK(x), attrvec(x) | x D。级联归纳法也是一种元学习方法11，是指顺序调用每个基分类器，前一个分类器的学习结果送给后一个分类器使用。设级联归纳法所用的K个学习算法为Lk（k = 1, 2, K），级联归纳法的学习模型Mk是通过将基分类算法的学习结果依次加入到特征向量中得到的，即MK=LK (TK1)，TK1为第(K1)层元训练集。元训练集的组成为正确的分类标识、特征向量attrvec(x)和顺序加入的分类器预测结果，即TK1= (class(x), Ck1(x), attrvec(x) | x D，其中Ck1(x)为第(K2)层分类器的预测结果，如图2所示。图2 级联归纳法4 特征选择特征选择的目的是寻找那些帮助识别和分类命名实体的文本属性。由于识别生物医学命名实体有一定的难度，所以选择特征时不仅要考虑词一级的特征，还要结合更多有信息量的特征。本系统中使用的特征可分为三类：局部特征、全文特征和外部资源特征。局部特征主要是词本身的特征和词临近的上下文特征。系统中使用的局部特征主要包括词特征、词形特征、标准化拼写特征、词性特征、词法特征、语块特征、核心词特征、频率特征、多元文法特征等。下面加以简要介绍。词形特征：词形特征是命名实体识别任务中被广泛使用的一种特征。根据生物医学领域文本中命名实体的特点定义了词形特征，这些特征对识别未登录词、缩写词、命名实体的边界都很有帮助。标准化拼写特征：某些属于同一类的命名实体，它们的拼写方式非常相似，例如：IL-2 and IL-4。因此使用简单的方法归一化所有相似词。具体方法如下：大写字符都用A替换，小写字符用a替换，数字用0替换，非英语字符用_替换，例如Kappa-B则可以规范化为“Aaaaa_A”。进一步地，连续的相同字符缩短为一个字符，则“Aaaaa_A”被规范化为“Aa_A”。因此，通过标准化拼写特征能够帮助将拼写相似的命名实体分类为相同的命名实体类别。词性特征：本文研究使用了GENIA tagger2.0.212词性标注器，GENIA tagger不仅使用通用语料训练，还使用GENIA语料和PennBioIE 语料13训练，因此GENIA tagger在本领域文本中的词性标注达到了较高的性能，对正确识别命名实体有很大帮助。词法特征：即前后缀特征，使用统计方法从训练语料中获得的高频前后缀词表。语块特征：系统中使用了GENIA tagger2.0.2进行语块标注作为特征。语块特征对识别命名实体的边界很有帮助。核心词特征：使用统计方法在训练语料中统计出的高频命名实体核心词，实验表明这些核心词也是重要的识别特征。上下文特征：根据不同的特征，上下文窗口大小定为2, 2。上下文特征对区分不同类别的命名实体提供了重要线索，尤其是同形不同类的命名实体。全文特征主要使用了别名特征等。别名特征是将在文本前面句子中已经识别出来的命名实体存放在一个列表中，当系统遇到一个命名实体候选词时，一个别名识别算法被激活去动态地决定是否命名实体候选词是前面已经识别出来的命名实体列表中词的别名。为了提供更多的可靠分类证据，本文还使用了外部资源特征。本文研究中使用的外部资源特征主要是词典资源，有通用词词典、物种名词典、矿物名词典、化学物质名称后缀词典和停用词词典等。5 实验与结果分析本文研究使用JNLPB2004评测语料对系统进行训练和测试。其中训练语料为2 000篇，测试语料为404篇。语料中的命名实体分为5类：DNA、RNA、protein、cell_line和cell_type。实验结果的评价标准是精确率（P），召回率（R）和F测度（F）评价。本文使用了全部匹配模式对实验结果进行评测，即识别出的命名实体全部和正确答案的命名实体完全相匹配则认为是正确识别。为了验证元学习策略的有效性，共进行了4组实验。在实验1中，测试基于单分类器的识别性能，由于4个单分类器对不同特征的敏感程度不尽相同，训练学习的速度也有差异，因此4个模型选择的特征也不完全相同。CRF模型使用了大部分局部特征和部分外部资源特征；Generalized Winnow模型使用了局部特征，全局特征和部分外部资源特征；SVM模型由于运行效率低，只使用了词及其上下文特征；ME模型使用了局部特征、全局特征和外部资源特征。系统没有加入任何后处理过程。表1为4个单分类器在测试语料上的结果。CRF模型取得了最好的识别结果；ME算法训练学习速度最快，Generalized Winnow算法次之；SVM算法占用较多的CPU时间。表1单分类器结果算法P/%R/%F/%GW67.9972.4870.16CRF70.0272.3571.17SVM64.0462.3263.17ME65.1271.1968.02由表1可以看出，单分类器的性能约为60%70%。在实验2中，采用了判决规则法进行融合实验，用以和本文提出的元学习策略进行对比。判决规则方法是一种常用的机器学习融合方法。当参与预测的基分类器的结果不能达成一致时，判决规则使用启发式规则判断选择其中某一个基分类器的预测结果为最后的预测结果9。图3描述了判决规则的预测过程。图3 判决规则对于判决规则融合策略，本文先使用多数表决规则融合4个成员分类器(Generalized Winnow、CRF 、SVM和ME)的识别结果。如果4个成员分类器不能达成一致决策，则按照如下实体顺序选择判别结果：protein、DNA、RNA、cell-type、cell-line和“Non-entity”。实验结果如表2所示。在实验3中，本文使用叠加归纳法融合4个不同的分类算法包括：Generalized Winnow、CRF 、SVM和ME。使用JNLPBA训练语料通过4折交叉验证方法产生元训练集，过程如文中第3节所述。由于CRF模型结合了生成模型和分类模型的优点，既能像分类模型一样支持与输入相关的更丰富的特征表示以及判定性的训练方式，也能像生成模型一样考虑整个模型输出从而获得全局最优输出，我们选择CRF作为元分类器。表2多分类器融合实验结果实验P/%R/%F/%判决规则71.5174.8873.16类叠加法72.3675.2073.75类及属性叠加法75.5779.6877.57级联归纳法74.7678.4276.24在实验4中，本文使用级联归纳法依次加入SVM、ME、Generalized Winnow和CRF学习模型。对于学习模型的加入顺序对实验结果的影响，本文进行了进一步的实验。实验结果表明：最大相差0.1%，因此模型的加入顺序对结果影响不大。从实验结果中可以看出，判决规则融合方法能够有效地利用基分类器的分类结果，达到了73%的 F测度值，优于基于单分类器系统的性能，但是效果不显著。类叠加法和判决规则相比，结果又有了进一步提高，原因是CRF元分类器能够自动赋予每个成员分类器适当的权重，并且元学习方法能够有效利用各个基分类器结果之间的相互作用关系。类及属性叠加法获得最好的学习性能，取得了约为78%的F测度值。级联归纳法也非常有效，获得了76%的F测度值。这2个实验之所以获得了较高的性能，原因是它们有效地利用了可以获取的全部特征线索来提高系统的性能。表3列出了本文实验中最好结果和JNLPBA任务前三名的系统的比较结果。从中可以看出，本文方法优于国际同类研究的结果。表3与国际同类研究结果的比较系统P/%R/%F/%类及属性叠加法75.5779.6877.57Zho1469.476.072.6Fin1568.671.670.1Set1669.370.369.8上述实验结果表明，元学习策略是一种有效的分类器融合方法，对于特定领域命名实体识别任务非常有效。此外，特征选择对于系统性能的影响也很重要，实验结果表明：本文针对特定领域文本中命名实体特点进行的特征选择对系统性能提高贡献较大。6 结束语本文提出了基于元学习策略的分类器融合的新模型并应用于识别生物医学命名实体，该方法利用了不同分类器决策之间的互补性和相关性，性能明显优于基于单分类器的识别系统，也优于基于判决规则法的分类器融合方法的性能。同时，针对特定领域命名实体而选择的特征也非常有效。在今后的研究工作中将尝试基于特征空间的差异进行分类器融合，以进一步提高相关系统的性能。参考文献：1ANZEN K, ERIKSSON G, OLSSON F. Protein names and how to find themJ. IntJ Med Inf, 2002, 67:49-61.2FUKUDA K, TAMURA A, TSUNODA T. Toward information extraction: identifying protein names from biological papersA. Proceedings of Pacific Symposium on Biocomputing98C. Hawaii,1998. 707-718.3ZHOU G, ZHANG J, Su J, et al. Recognizing names in biomedical texts: a machine learning approachJ. Bioinformatics, 2004, 20(7): 1178-1190.4SEKI K, MOSTAFA J. A pobabilistic mdel for ientifying potein nmes and their nme bundariesA. Proceedings of the Computational Systems BioinformaticsC. Stanford, 2003.251-259.5ZHANG T, DAMERAU F, JOHNSON D. Text chunking based on a generalization of WinnowJ. Journal of Machine Learning Research, 2002, (2): 615-637.6BOSER B, GUYON I, VAPNIK V. An training algorithm for optimal margin classifiersA. Fifth Annual Workshop on Computational Learning TheoryC. Pittsburgh, 1992. 144-152.7LAFFERTY J, MCCALLUM A, PEREIRA F. Conditional random fields: probabilistic models for segmenting and labeling sequence dataA. Proc of ICMLC. San Francisco, 2001. 282-289.8BERGER A L, DELLA P S A, DELLA P V J. A maximum entropy approach to natural language processingJ. Computational Linguistics, 1996, 22(1):39-71.9PRODROMIDIS A, CHAN P, STOLFO S. Meta-learning in distributed data mining systems: issues and approachesA. Advances in Distributed and Parallel Knowledge DiscoveryC. Kargupta, 2000. 81-114.10WOLPERT D. Stacked generalizationJ. Neural Networks, 1992, 5 (2) : 241-259.11GAMA J, BRAZDIL P. Cascade generalizationJ. Machine Learning, 2000, 41(3):315-343.12TSURUOKA Y, TATEISHI Y, KIM J D, et al. Developing a robust part-of-speech tagger for biomedical textA. Advances in Informatics- 10th Panhellenic Conference on InformaticsC. Greece,