第3卷第1期 智能系统学报 Vol.3 Ne 1 2008年2月 CAAI Transactions on Intelligent Systems Fcb.2008 半监督多标记学习的基因功能分析 陈晓峰，王士同，曹苏群2 (1.江南大学信息工程学院，江苏无锡214122：2.淮阴工学院机械系，江苏淮安223001) 摘要：传统的机器学习主要解决单标记学习，即一个样本仅有一个标记.在生物信息学中，一个基因通常至少具有 一个功能，即至少具有一个标记，与传统学习方法相比，多标记学习能更有效地识别生物相关基因组的功能.目前的 研究主要集中在监督多标记学习算法.然而，研究半监督多标记学习算法，从已标记和未标记的基因表达数据中学 习，仍然是未解决问题.提出一种有效的基因功能分析的半监督多标记学习算法SML SVM.首先，SML SVM根据 PT4方法，将半监督多标记学习问题转化为半监督单标记学习问题，然后根据最大后验概率原则(MAP)和K近邻 方法估计未标记样本的标记，最后，用SVM求解单标记学习问题.在yeast基因数据和genbase蛋白质数据上的实验 表明，SML_SVM性能比基于PT4方法的MLSVM和自训练MLSVM更优 关键词：半监督；多标记；自训练，支持向量机 中图分类号：TP181文献标识码：A文章编号：16734785(2008)01-008308 Gene function analysis of semi supervised multi-la bel learning CHEN Xiao-feng',WANG Shi-tong',CAO Surqun'2 (1.School of Information Technology,Jiangnan University,Wuxi 214122,China;2.Department of Mechanical Engineering, Huaiyin Institute of Technology,Huai'an 223001,China) Abstract:Conventional machine learning is used only for single label learning,implying that every sample has only one label.However,in bioinformatics,a gene has more than one function,so it needs more than one label.Therefore,multi-label learning is more effective for identifying gene groups than conventional learning approach.Current research mainly focuses on supervised multi-label learning.The problem of ef- fective semi-supervised multi-label learning strategies for labeled examples and unlabeled examples of gene expression datasets still remains unsolved.In this paper,a semi-supervised multi-label learning algorithm, named SML_SVM,is presented as an effective multi-label learner for analysis of gene expressions with at least one function.First,the proposed SML_SVM algorithm transforms the semi-supervised multi-label learning into corresponding semi-supervised single-label learning by the PT4 method,then it labels unla- beled examples using the maximum a posteriori(MAP)principle in combination with the K-nearest neigh- bor method,and finally,it solves the corresponding single-label learning problem using SVM.The dis- tinctive characteristic of the proposed algorithm is its efficient integration of SVM-based single-label learn- ing with MAP and K-nearest neighbor methods.Experimental results with a real Yeast gene expression dataset and a Genbase protein dataset show that the proposed SML_SVM algorithm outperforms the PT4- based MLSVM method and self-training MLSVM. Keywords:semi-supervised;multi-label;self-training;support vector machine 基因功能预测是生物学的重要任务，它有助于理解细胞的分子生物机制.随着DNA微序列技术 收稿日期：2007-0413. 的发展，生物学家可以同时监测成千上万的基因.微 基金项目：国家“863”基金资助项目(2006AA10Z313):国家自然科学 序列技术的使用，产生了大量的基因表达数据.早期 基金资助项目(60773206/F020106,60704047/F030304): 国防应用基础研究基金资助项目(A1420461266);教育部 研究中，通常用无监督聚类方法分析基因表达数据， 跨世纪优秀人才支持计划基金资助项目(NCE下O4 0496);教育部科学研究重点基金资助项目(105087). 如层次聚类四、自组织映射)和基于SSMCL的 通讯作者：王士同.wxwangst@yahoo.com,cn. OPTOC!)等.这些聚类算法假定相似的基因表达数 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 3 卷第 1 期 智 能 系 统 学 报 Vol. 3 №. 1 2008 年 2 月 CAA I Transactions on Intelligent Systems Feb. 2008 半监督多标记学习的基因功能分析 陈晓峰1 ,王士同1 ,曹苏群1 ,2 (1. 江南大学 信息工程学院 ,江苏 无锡 214122 ;2. 淮阴工学院 机械系 ,江苏 淮安 223001) 摘 要 :传统的机器学习主要解决单标记学习 ,即一个样本仅有一个标记. 在生物信息学中 ,一个基因通常至少具有 一个功能 ,即至少具有一个标记 ,与传统学习方法相比 ,多标记学习能更有效地识别生物相关基因组的功能. 目前的 研究主要集中在监督多标记学习算法. 然而 ,研究半监督多标记学习算法 ,从已标记和未标记的基因表达数据中学 习 ,仍然是未解决问题. 提出一种有效的基因功能分析的半监督多标记学习算法 SML_SVM. 首先 ,SML_SVM 根据 PT4 方法 ,将半监督多标记学习问题转化为半监督单标记学习问题 ,然后根据最大后验概率原则 (MAP) 和 K 近邻 方法估计未标记样本的标记 ,最后 ,用 SVM 求解单标记学习问题. 在 yeast 基因数据和 genbase 蛋白质数据上的实验 表明 ,SML_SVM 性能比基于 PT4 方法的 MLSVM 和自训练 MLSVM 更优. 关键词 :半监督 ;多标记 ;自训练 ;支持向量机 中图分类号 : TP181 文献标识码 :A 文章编号 :167324785 (2008) 0120083208 Gene function analysis of semi2supervised multi2label learning CH EN Xiao2feng 1 , WAN G Shi2tong 1 , CAO Su2qun 1 ,2 (1. School of Information Technology , Jiangnan University , Wuxi 214122 , China ; 2. Department of Mechanical Engineering , Huaiyin Institute of Technology , Huai’an 223001 ,China) Abstract :Conventional machine learning is used only for single label learning , implying t hat every sample has only one label. However , in bioinformatics , a gene has more than one f unction , so it needs more than one label. Therefore , multi2label learning is more effective for identifying gene group s t han conventional learning approach. Current research mainly focuses on supervised multi2label learning. The problem of ef2 fective semi2supervised multi2label learning strategies for labeled examples and unlabeled examples of gene expression datasets still remains unsolved. In t his paper , a semi2supervised multi2label learning algorithm , named SML_SVM , is presented as an effective multi2label learner for analysis of gene expressions wit h at least one f unction. First , t he proposed SML _SVM algorit hm transforms t he semi2supervised multi2label learning into corresponding semi2supervised single2label learning by the PT4 met hod , t hen it labels unla2 beled examples using the maximum a posteriori (MAP) principle in combination wit h t he K2nearest neigh2 bor met hod , and finally , it solves t he corresponding single2label learning problem using SVM. The dis2 tinctive characteristic of t he proposed algorithm is its efficient integration of SVM2based single2label learn2 ing wit h MA P and K2nearest neighbor met hods. Experimental results wit h a real Yeast gene expression dataset and a Genbase protein dataset show that t he proposed SML_SVM algorit hm outperforms t he PT42 based ML SVM met hod and self2training ML SVM. Keywords :semi2supervised ; multi2label ; self2training ; support vector machine 收稿日期 :2007204213. 基金项目 :国家“863”基金资助项目(2006AA10Z313) ;国家自然科学 基金资助项目 (60773206/ F020106 ,60704047/ F030304) ; 国防应用基础研究基金资助项目(A1420461266) ;教育部 跨世纪优秀人 才支持计划基 金资助项目 ( NCET2042 0496) ;教育部科学研究重点基金资助项目(105087) . 通讯作者 :王士同. wxwangst @yahoo. com. cn. 基因功能预测是生物学的重要任务 ,它有助于 理解细胞的分子生物机制. 随着 DNA 微序列技术 的发展 ,生物学家可以同时监测成千上万的基因. 微 序列技术的使用 ,产生了大量的基因表达数据. 早期 研究中 ,通常用无监督聚类方法分析基因表达数据 , 如层次聚类[1 ] 、自组织映射[2 ] 和基于 SSMCL 的 OPTOC [3 ]等. 这些聚类算法假定相似的基因表达数
·84 智能系统学报 第3卷 据仅有一个相似的功能.非监督的聚类算法的优点 况下，多标记学习器学习实值函数f:XXY→R,如 是在训练中不需要先验知识.然而，如果获取到基因 果样本x的标记集为Y,对于属于Y,的标记，实值 表达数据的先验信息或功能信息，且有些基因同时 函数f的输出值较大，如y∈Y,2∈Y,则f(x, 具有若干种功能，在这种情况下，非监督聚类算法不 )>f(x,)01 是基因功能预测的最好选择 实值函数∫(·)可以转化为排列函数 如果将基因的功能视为标记，则在传统学习中， ranky(),它将函数f(x,以的输出映射到{1,2， 每个基因表达数据样本属于一个类，即一个样本有 Q},如果f(x,)>f(x,2),则 且仅有一个标记.在很多真实世界问题中，一个样本 rank(x,y)rank,(x,y2). 可能同时属于多个类，即样本有多个标记.例如，在 求解多标记学习问题的策略分两类：1)将多标 文本分类中，每篇文档会同时属于多个主题，文档的 记学习转化为单标记学习；2)将传统算法改造为能 内容同时涉及多个方面，如“政府”和“健康51.在 处理多标记问题的算法山 生物信息学中，一个基因序列具有若干个功能，如 将多标记学习转化为单标记学习，有6种策 “新陈代谢”和“蛋白质合成州6，在语义场景分类中， 略：1)主观地或随机地选择多标记样本的某一个 场景图片会属于多个类别，如“沙滩”和“日出州).在 标记为训练标记，而丢弃该样本的其他标记，记为 音乐分类中，乐曲同时属于“摇滚”和“民谣】.研究 PT1:2)丢弃训练集的所有多标记样本，仅保留单标 人员提出了多标记学习算法来解决上述问题 记样本，记为PT2;3)将具有相同标记的多标记样 在基因功能预测方面，获得已标记样本的代价 本组成一个新单标记类，记为PT3;4)训练1个分 比较高，一方面是因为需要较多的人力参与，另一方 类器H:X→1，l},其中每个分类器H将 面是因为样本数量急剧增长，大规模的标定样本非 样本分为fl,1}(l∈Yy,记为PT4;5)根据样 常困难.由于DNA测序的自动化，使得生物序列数 本的标记，将所有样本分为Q类单标记数据集，即 据库的数量以指数方式急剧增长，而基因功能分析 将样本(x,Y)分解为Y个样本(x,1)(l∈Y), 的速度没有大的变化，不能满足应用需求.在这种情 然后学习Q个基于覆盖的单标记分类器，记为 况下用于基因序列功能预测的已标记样本远小于 PT5,6)将样本(x,Y)分解为1Y个样本(x,l 未标记样本.近年来，研究人员提出了监督的多标记 Y[1a),如果l∈Y,则Y[lJ=1,否则Y[la]= 学习算法，在监督多标记学习中，不考虑未标记样本 -1,记为PT6.其中，策略PT1和PT2会丢失多标 的内在信息.与监督学习相比，半监督学习同时使用 记信息，很少使用， 已标记数据和未标记数据，提高了学习器的性能，在 研究人员还将传统算法做一定的修改，使之能 性能上具有一定优势.将半监督学习引入多标记 处理多标记问题，如变体的C4.5算法2]、Ada 学习，可以降低多标记学习在应用中的成本，使得在 boost.MH和Adaboost..MRI、ML-kNNIO,] 仅需人力处理少量样本的情况下，得到比监督多标 SVM6,1)BP MLL6]Boosting!等.在半监督 记学习更好的效果 学习方面，文献[18]提出一种半监督多标记学习框 针对上述问题，文中提出一种半监督多标记支 架，根据输入空间和输出空间的相似性，把半监督多 持向量算法(semi-supervised multi-label support 标记学习转化为NMF问题来求解.文献[19]用 vector machine,SML_SVM),并给出解决该问题的 Bayes语义模型和EM算法解决Web文本挖掘问 策略.SML SVM先用PT4策略把半监督多标记学 题，文献[20]提出文本分类的TFDF-NB协同训练 习问题转化为半监督单标记学习问题，然后用基于 算法，这2种算法实质上可以被认为是半监督多标 后验概率最大原则对未标记样本进行标记，再用 记算法 SVM求解每个单标记学习问题 衡量多标记数据集性质的2个指标，标记均值 1多标记学习 和标记密度定义如下 标记均值为数据集的样本平均标记数，按下式 设训练集为T={(x,Y),(x,Y), 计算 (xm,Ym}(x∈X,Y三Y),其中X为输入空间， Y=1,2,…Q为有限个标记的集合.多标记学习 LC( 1) 从训练集中构造多标记学习器h:X→2'.在一般情 标记密度为数据集样本的标记数除以YⅥ的平 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
据仅有一个相似的功能. 非监督的聚类算法的优点 是在训练中不需要先验知识. 然而 ,如果获取到基因 表达数据的先验信息或功能信息 ,且有些基因同时 具有若干种功能 ,在这种情况下 ,非监督聚类算法不 是基因功能预测的最好选择. 如果将基因的功能视为标记 ,则在传统学习中 , 每个基因表达数据样本属于一个类 ,即一个样本有 且仅有一个标记. 在很多真实世界问题中 ,一个样本 可能同时属于多个类 ,即样本有多个标记. 例如 ,在 文本分类中 ,每篇文档会同时属于多个主题 ,文档的 内容同时涉及多个方面 ,如“政府”和“健康”[425 ] . 在 生物信息学中 ,一个基因序列具有若干个功能 ,如 “新陈代谢”和“蛋白质合成”[ 6 ] . 在语义场景分类中 , 场景图片会属于多个类别 ,如“沙滩”和“日出”[ 7 ] . 在 音乐分类中 ,乐曲同时属于“摇滚”和“民谣”[8 ] . 研究 人员提出了多标记学习算法来解决上述问题. 在基因功能预测方面 ,获得已标记样本的代价 比较高 ,一方面是因为需要较多的人力参与 ,另一方 面是因为样本数量急剧增长 ,大规模的标定样本非 常困难. 由于 DNA 测序的自动化 ,使得生物序列数 据库的数量以指数方式急剧增长 ,而基因功能分析 的速度没有大的变化 ,不能满足应用需求. 在这种情 况下 ,用于基因序列功能预测的已标记样本远小于 未标记样本. 近年来 ,研究人员提出了监督的多标记 学习算法 ,在监督多标记学习中 ,不考虑未标记样本 的内在信息. 与监督学习相比 ,半监督学习同时使用 已标记数据和未标记数据 ,提高了学习器的性能 ,在 性能上具有一定优势[9 ] . 将半监督学习引入多标记 学习 ,可以降低多标记学习在应用中的成本 ,使得在 仅需人力处理少量样本的情况下 ,得到比监督多标 记学习更好的效果. 针对上述问题 ,文中提出一种半监督多标记支 持向量算法 ( semi2supervised multi2label support vector machine ,SML_SVM) ,并给出解决该问题的 策略. SML_SVM 先用 PT4 策略把半监督多标记学 习问题转化为半监督单标记学习问题 ,然后用基于 后验概率最大原则对未标记样本进行标记 ,再用 SVM 求解每个单标记学习问题. 1 多标记学习 设训练集为 T = { ( x1 , Y1 ) , …, ( xi , Yi ) , …, ( xm , Ym ) } ( xi ∈X, Yi Α Y) , 其中 X 为输入空间 , Y= { 1 ,2 , …, Q}为有限个标记的集合. 多标记学习 从训练集中构造多标记学习器 h : X →2 Y . 在一般情 况下 ,多标记学习器学习实值函数 f : X ×Y →R,如 果样本 xi 的标记集为 Yi ,对于属于 Yi 的标记 ,实值 函数 f 的输出值较大 ,如 y1 ∈Yi , y2 ∈Yi ,则 f ( xi , y1 ) > f ( xi , y2 ) [10 ] . 实值 函 数 f ( ·) 可 以 转 化 为 排 列 函 数 rankf ( ·) ,它将函数 f ( xi , y) 的输出映射到{ 1 , 2 , …, Q } , 如 果 f ( xi , y1 ) > f ( xi , y2 ) , 则 rankf ( xi , y1 ) < rankj ( xi , y2 ) . 求解多标记学习问题的策略分两类 :1) 将多标 记学习转化为单标记学习 ;2) 将传统算法改造为能 处理多标记问题的算法[11 ] . 将多标记学习转化为单标记学习 ,有 6 种策 略[11 ] :1) 主观地或随机地选择多标记样本的某一个 标记为训练标记 ,而丢弃该样本的其他标记 ,记为 PT1 ;2) 丢弃训练集的所有多标记样本 ,仅保留单标 记样本 ,记为 PT2 ;3) 将具有相同标记的多标记样 本组成一个新单标记类 ,记为 PT3 ;4) 训练| Y| 个分 类器 Hl ab : X →{ lab , l ab } ,其中每个分类器 Hl ab 将 样本分为{ lab , lab } ( lab ∈Y) ,记为 PT4 ; 5) 根据样 本的标记 ,将所有样本分为 Q 类单标记数据集 ,即 将样本( xi , Yi) 分解为| Yi | 个样本 ( x , lab ) ( lab ∈Yi) , 然后学习 Q 个基于覆盖的单标记分类器 , 记为 PT5 ;6) 将样本 ( xi , Yi) 分解为| Y| 个样本 ( xi , lab , Y[ lab ]) ,如果 lab ∈Yi ,则 Y[ lab ] = 1 ,否则 Y[ lab ] = - 1 ,记为 PT6. 其中 ,策略 PT1 和 PT2 会丢失多标 记信息 ,很少使用. 研究人员还将传统算法做一定的修改 ,使之能 处理多标记问题 , 如变体的 C415 算法[12 ] 、Ada2 boost. M H 和 Adaboost. MR [5 ] 、ML2kNN [10 ,13 ] 、 SVM [6 ,14215 ] 、BP_MLL [16 ] 、Boosting [17 ] 等. 在半监督 学习方面 ,文献[ 18 ]提出一种半监督多标记学习框 架 ,根据输入空间和输出空间的相似性 ,把半监督多 标记学习转化为 NMF 问题来求解. 文献 [ 19 ] 用 Bayes 语义模型和 EM 算法解决 Web 文本挖掘问 题 ,文献[20 ]提出文本分类的 TFIDF2NB 协同训练 算法 ,这 2 种算法实质上可以被认为是半监督多标 记算法. 衡量多标记数据集性质的 2 个指标 ,标记均值 和标记密度定义如下 : 标记均值为数据集的样本平均标记数 ,按下式 计算 : LC( T) = 1 m ∑ m i =1 | Yi | . (1) 标记密度为数据集样本的标记数除以| Y| 的平 · 48 · 智 能 系 统 学 报 第 3 卷
第1期 陈晓峰，等：半监督多标记学习的基因功能分析 ·85* 均值，按下式计算： 1为已标记数据集的样本数量，“为未标记数据集的 LD(7 -1L 样本数量，一般来说，在半监督学习中，有1《u为 2 m,←Y 简便起见，文中假定在已标记数据集L中不存在标 设测试集为Z=(xⅪ，Y),(¤，)，(x, 记缺失的情况，标记集Y中的所有成员都在L中出 Y)},多标记学习算法的性能衡量指标如下： 1)汉明损失：测试样本的全体误分率，即不属于 现，即，yY=Y i类的样本被预测为1类，或者属于1类但没有被标 设(x,Y)为已标记样本，Y={.1,…y.} 记为1类汉明损失越小越好，计算公式如下： (h),Y为样本x对应的标记集，.4为x的第 0uaY 1个标记.与传统的单标记学习不同的是，在多标记 (3) 学习中，习，样本x至少有一个标记.多标记学习 式中：△表示2个集合差异，h为多标记学习器 的一种解决方法是把多标记学习转化为单标记学 2)一类错误：假如多标记分类器对样本x求出 习.如前所述，有6种转化策略，其中，PT1和PT2 的排序最高的标记不在x,对应的Y,中，则称为一 两种转化策略会丢失较多的多标记信息，不考虑使 类错误，表示为one-error(f),该值越小越好，计算用，PT3方法是通过把具有相同标记的多标记样本 公式如下： 组成单标记数据集的方法转化的，往往会使新单标 oneerror()argmaxr( 记数据集样本数量较少，在半监督多标记学习中，由 于己标记样本远小于未标记样本，这种转化对学习 (4) 是不利的，因此PT3策略不适合半监督多标记学 3)覆盖率：平均需要将标记序列下降多少可以 习.文中用PT4策略把多标记学习转化为单标记学 覆盖样本对应的所有标记，表示为coverage(f).该 习 值越小越好，其计算公式如下： 将L按照PT4策略转化，对于样本(x,Y),首 coverage(f)=max rank(x.y)1. 先根据标记集Y把(x,Y)分解成单标记样本集 Q,={(x,,(x,},0,中有1：个单标记 (5) 4)排列损失：样本标记排列次序的平均错误，表 样本，这样多标记数据集L转化为L'=,9,= 示为s(f),该值越小越好，计算公式如下： {(0,,(0,n.),(X,.1),(,.4}= r,←|￥川Y |{h,2}|f(x,W≤ ,US。,S为L数据集中具有标记1的样本的集 f(x,2),(y,2)∈YXY1 6) 合1Y表示标记集Y的样本数目.根据L学习引Y 式中Y,表示Y的补集. 个二分的分类器Has:X一{lm,l},其中每个分 5)平均精度：多标记学习器预测样本的多标记 类器H按照样本是否具有标记1将数据集L分 是正确标记的平均比例，表示为avgprecc(f),该值 为{l,1}(1=1,…,两类. 通过上述的转化方式，半监督多标记学习问题 越大越好，计算公式如下： 被转化成了若干个半监督单标记学习问题.根据近 邻最大后验概率方法计算未标记样本被正确标记的 ,rank Cx Srank∈Y 概率，其方法叙述如下： rank(x.y) 设在对标记1。分类的半监督单标记学习中 (7) L={(x,),(w,y)}为己标记数据集，U= {+1,+2,+}为未标记数据集.在L中，如 2半监督多标记学习算法SML SVM 果x具有标记1，则y=+1,否则y=·1 2.1 SML_SVM N(x)表示x在训练集的K个近邻里具有+1标 设L=/(x,Y),(,,(x,Y/为己标记 记样本的集合，N·(x)表示x的在训练集的K个 数据集，U=x+1,x+2,,x+}为未标记数据集. 近邻里具有-1标记样本的集合 其中，x∈X(i=1,1+W,X为输入空间，YSY 设未标记样本为，首先分别计算它在训练集 (1=1,),Y=1,2,…Q为有限个标记的集合， 的K个近邻中具有+1和·1标记的样本，记为 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
均值 ,按下式计算 : LD ( T) = 1 m ∑ m i =1 | Yi | Y . (2) 设测试集为 Z = { ( x1 , Y1 ) , ( x2 , Y2 ) , …, ( xr , Yr) } ,多标记学习算法的性能衡量指标如下 : 1) 汉明损失 :测试样本的全体误分率 ,即不属于 i 类的样本被预测为 i 类 ,或者属于 i 类但没有被标 记为 i 类. 汉明损失越小越好 ,计算公式如下 : hloss ( h) = 1 r ∑ r i = 1 1 Q | h( xi)ΔYi | . (3) 式中 :Δ表示 2 个集合差异 , h 为多标记学习器. 2) 一类错误 :假如多标记分类器对样本 xi 求出 的排序最高的标记不在 xi 对应的 Yi 中 ,则称为一 类错误 ,表示为 one2error ( f ) ,该值越小越好 ,计算 公式如下 : one2error ( f ) = 1 r ∑ r i = 1 argmax y ∈Yi f ( xi , y) Yi . (4) 3) 覆盖率 :平均需要将标记序列下降多少可以 覆盖样本对应的所有标记 ,表示为 coverage ( f ) . 该 值越小越好 ,其计算公式如下 : coverage ( f ) = 1 r ∑ r i =1 max y rank i f ( xi , y) - 1. (5) 4) 排列损失 :样本标记排列次序的平均错误 ,表 示为 rloss ( f ) ,该值越小越好 ,计算公式如下 : rloss ( f) = 1 r ∑ r i =1 1 | Yi | | Yi | | { ( y1 , y2 )} | f ( xi , yi) ≤ f ( xi , y2 ) , ( y1 , y2 ) ∈Yi ×Yi | . (6) 式中 :Yi 表示 Y的补集. 5) 平均精度 :多标记学习器预测样本的多标记 是正确标记的平均比例 ,表示为 avgp recc ( f ) ,该值 越大越好 ,计算公式如下 : avgprecc ( f ) = 1 r ∑ r i = 1 1 | Yi | y∑∈Yi | { y′| rankf (xi , y′) ≤rankf ( xi , y) , y′∈Yi | rankf (xi , y) . (7) 2 半监督多标记学习算法 SML_SVM 211 SML_SVM 设 L = { ( x1 , Y1 ) , ( x2 , Y2 ) , …, ( xl , Yl}为已标记 数据集 ,U = { xl + 1 , xl + 2 , …, xl + u } 为未标记数据集. 其中 , xi ∈X( i = 1 , …, l + u) , X 为输入空间 , Yi Α Y ( i = 1 , …, l) , Y= { 1 ,2 , …, Q}为有限个标记的集合 , l 为已标记数据集的样本数量 , u 为未标记数据集的 样本数量 ,一般来说 ,在半监督学习中 ,有 l ν u. 为 简便起见 ,文中假定在已标记数据集 L 中不存在标 记缺失的情况 ,标记集 Y中的所有成员都在 L 中出 现 , 即 ∪ m i = 1 Yi = Y. 设( xi , Yi ) 为已标记样本 , Yi = { yi ,1 , …, yi , t i } ( ti ≥1) , Yi 为样本 xi 对应的标记集 , yi , t 1 为 xi 的第 t 个标记. 与传统的单标记学习不同的是 ,在多标记 学习中 , ti ≥1 ,样本 xi 至少有一个标记. 多标记学习 的一种解决方法是把多标记学习转化为单标记学 习. 如前所述 ,有 6 种转化策略 ,其中 , PT1 和 PT2 两种转化策略会丢失较多的多标记信息 ,不考虑使 用 ,PT3 方法是通过把具有相同标记的多标记样本 组成单标记数据集的方法转化的 ,往往会使新单标 记数据集样本数量较少 ,在半监督多标记学习中 ,由 于已标记样本远小于未标记样本 ,这种转化对学习 是不利的 ,因此 PT3 策略不适合半监督多标记学 习. 文中用 PT4 策略把多标记学习转化为单标记学 习. 将 L 按照 PT4 策略转化 ,对于样本 ( xi , Yi) ,首 先根据标记集 Yi 把 ( xi , Yi ) 分解成单标记样本集 Ωi = { ( xi , yi ,1 ) , …, ( xi , yi , t i ) } ,Ωi 中有 ti 个单标记 样本 ,这样多标记数据集 L 转化为 L′= ∪ l i =1 Ωi = { ( x1 , y1 ,1 ) , …, ( x1 , y1 , t 1 ) , …, ( xi , yl ,1 ) , …, ( xl , yl, t 1 )} = ∪ Q l ab =1 Sl ab , Sl ab为 L′数据集中具有标记 l ab的样本的集 合. | Y| 表示标记集 Y的样本数目. 根据 L′学习| Y| 个二分的分类器 Hlab : X →{ lab , lab } ,其中每个分 类器 Hl ab按照样本是否具有标记 l ab将数据集 L′分 为{ lab , lab } ( l ab = 1 , …, Q) 两类. 通过上述的转化方式 ,半监督多标记学习问题 被转化成了若干个半监督单标记学习问题. 根据近 邻最大后验概率方法计算未标记样本被正确标记的 概率 ,其方法叙述如下 : 设在对标记 lab 分类的半监督单标记学习中 , L l ab = { ( x1 , y1 ) , …, ( xl , yl) } 为已标记数据集 , U = { xl + 1 , xl + 2 , …, xl + u } 为未标记数据集. 在 L l ab 中 ,如 果 xi 具有标记 l ab , 则 yi = + 1 , 否则 yi = - 1. N + ( xi) 表示 xi 在训练集的 K 个近邻里具有 + 1 标 记样本的集合 , N - ( xi) 表示 xi 的在训练集的 K 个 近邻里具有 - 1 标记样本的集合. 设未标记样本为 u ,首先分别计算它在训练集 的 K 个近邻中具有 + 1 和 - 1 标记的样本 , 记为 第 1 期 陈晓峰 ,等 :半监督多标记学习的基因功能分析 · 58 ·
·86· 智能系统学报 第3卷 N*四和N',lN*1和N·⊙1表示N* 集U中删除.因此，在第2次迭代中，已标记样本数 和N·d的样本数目.用H表示ù具有标记-1， 为1+upp,未标记样本数为u(1-p.以此类推 H6表示i不具有标记-1，用H表示1具有标记 在第ⅰ次迭代中，已标记样本数和未标记样本数分 +1,Ho表示ù不具有标记+1.根据N+(和 别为I+p+upp2(1-p)++upp2(1- N·d计算标记的最大后验概率的公式如下： pm2=1+wpm(1-(1-pm))和u1-p)1.由 yi argmaxsero.u.P(H II N (W)= 此可知，任意一个半监督单标记迭代学习中，训练样 ar gmaxe(i Maxlter P(N(W 本总数为1+p:1·1·pW》= argmaxsEo.v.(P(HB)P(1 NHB). MaxIter(l+up:)up2 11-p)Mh ,由于 (8) 为计算，需要从训练集中计算先验概率 SML_SVM将半监督多标记学习问题转化为YI个 P(H)(q∈{+，-}，b∈0,1)和后验概率 半监督单标记学习问题，在SML_SVM中，参与训 PAN9(o‖H). 练的样本总数为|Y|(MaxIter(I+upm)·upm 在半监督单标记学习中，先用已标记数据集 1-11-p)Maxlte -).由于|Y (MaxIter(1+up)- p L,训练一个SVM分类器，然后对未标记数据集U 1-61-p)Maxker 进行标记，根据SVM分类器的分类结果，与分类超 up )<Y MaxIter(1+upz)<Y p 平面距离越远的点，越可能被正确分类，而在分类超 MaxIter(I+W,故SMLSVM算法的训练样本复 平面附近的点，错分的可能比较大，也就是说，与分 杂度为O(MaxIter)lI(1+W. 类超平面距离远的点分类结果的信任度高.从未标 记数据集中选择具有最高信任度的样本组成候选未 表1 SML_SVM算法步骤 标记数据集U',再根据最大后验概率原则，把U中 Table 1 Steps of SML_SVM algorithm 被正确标记的概率最大样本取出，组成己标记集 SML SVM(L.U.K,MaxIter,p,p2) L(·下一轮迭代的训练集为LUL,循环该过程， 输入参数： 直到达到算法的最大迭代次数.SML_SVM算法步 L:已标记数据集， 骤如表1所示」 U:未标记数据集： 2.2计算复杂度 K:近邻数： MaxIter:半监督训练最大迭代次数； SML SVM算法的复杂度与SVM的复杂度紧 p1:从U中选择构建U的未标记样本比例： 密相关，然而，SVM的不同优化求解方法的时间复 P2:从U中选择构建L的未标记样本比例 杂度和空间复杂度差异较大，因此直接计算SML 步骤： SVM的复杂度并不方便.根据文献[21]，文中通过 1)把多标记数据集L根据PT4策略转化为单标记数 计算SML SVM训练中所有样本的总数来衡量算 据集L', 法的复杂度.定理1表明，SML SVM算法与标记 2)根据训练若干个单标记SVM分类器，构成多标记 样本与未标记的数量是线性关系而不是指数关系 分类器SML SVM: 定理1 SML_SVM算法的训练中的样本复杂 3)Iter+1; 度为O(MaxIter|Y](I+l),其中MaxIter是最大 4)while (Iter <Maxlter) a)用SML SVM对U标记； 迭代次数，1Y为训练集中的标记类别数，1和“分 b)从U计算标记信任度最高的p1比例的样本，组 别是己标记样本数量和未标记样本数量， 成U'; 证明SML SVM将半监督多标记学习问题 c)计算U中样本标记的最大后验概率，取pm比例 转化为1个半监督单标记学习问题.首先计算任 的后验概率最高的样本组成L': 意一个半监督单标记迭代学习中的样本总数.设1由 d)跟据LUL',训练新的SML SVM: 为标记集Y中的任意1个标记，在第1次迭代训练 e)Iter +Iter+1; 中，1和u分别为已标记样本和未标记样本的数量. 5)end while. 在第1次迭代后，ppm个未标记样本被标记，且加 输出： 入到已标记样本中，且up个样本将从未标记样本 半监督多标记学习器SML SVM 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
N + (u) 和 N - (u) ,| N + (u) | 和| N - (u) | 表示 N + (u) 和 N - (u) 的样本数目. 用 H - 1 表示 u 具有标记 - 1 , H - 0 表示 u 不具有标记 - 1 ,用 H + 1 表示 u 具有标记 + 1 , H + 0 表示 u 不具有标记 + 1. 根据 N + ( u) 和 N - (u) 计算 u 标记的最大后验概率的公式如下 : yu = argmaxb∈{ 0 ,1} , q∈{ + , - } { P( H q b ‖N q (u) | ) } = argmaxb∈{ 0 ,1} , q∈{ + , - } { P( H q b ) P(| N q (u) ‖H q b ) P(| N q (u) | ) } = argmaxb∈{ 0 ,1} , q∈{ + , - } { P( H q b ) P(| N q (u) ‖H q b ) } . (8) 为计算 yu , 需要从训练集中计算先验概率 P( H q p ) ( q ∈{ + , - } , b ∈{ 0 , 1 }) 和 后 验 概 率 P(| N q (u) ‖H q b ) . 在半监督单标记学习中 , 先用已标记数据集 L l ab训练一个 SVM 分类器 ,然后对未标记数据集 U 进行标记 ,根据 SVM 分类器的分类结果 ,与分类超 平面距离越远的点 ,越可能被正确分类 ,而在分类超 平面附近的点 ,错分的可能比较大 ,也就是说 ,与分 类超平面距离远的点分类结果的信任度高. 从未标 记数据集中选择具有最高信任度的样本组成候选未 标记数据集 U′,再根据最大后验概率原则 ,把 U′中 被正确标记的概率最大样本取出 , 组成已标记集 L′l ab . 下一轮迭代的训练集为 L ∪L′. 循环该过程 , 直到达到算法的最大迭代次数. SML_SVM 算法步 骤如表 1 所示. 212 计算复杂度 SML_SVM 算法的复杂度与 SVM 的复杂度紧 密相关 ,然而 ,SVM 的不同优化求解方法的时间复 杂度和空间复杂度差异较大 ,因此直接计算 SML _ SVM 的复杂度并不方便. 根据文献[ 21 ] ,文中通过 计算 SML_SVM 训练中所有样本的总数来衡量算 法的复杂度. 定理 1 表明 ,SML _SVM 算法与标记 样本与未标记的数量是线性关系而不是指数关系. 定理 1 SML_SVM 算法的训练中的样本复杂 度为 O(MaxIter| Y| ( l + u) ) ,其中 MaxIter 是最大 迭代次数 ,| Y| 为训练集中的标记类别数 , l 和 u 分 别是已标记样本数量和未标记样本数量. 证明 SML _SVM 将半监督多标记学习问题 转化为| Y| 个半监督单标记学习问题. 首先计算任 意一个半监督单标记迭代学习中的样本总数. 设 lab 为标记集 Y中的任意 1 个标记 ,在第 1 次迭代训练 中 , l 和 u 分别为已标记样本和未标记样本的数量. 在第 1 次迭代后 , u p1 p2 个未标记样本被标记 ,且加 入到已标记样本中 ,且 u p1 个样本将从未标记样本 集 U 中删除. 因此 ,在第 2 次迭代中 ,已标记样本数 为 l + u p1 p2 ,未标记样本数为 u(1 - p1 ) . 以此类推 , 在第 i 次迭代中 ,已标记样本数和未标记样本数分 别为 l + u p1 p2 + u p1 p2 (1 - p1 ) + …+ u p1 p2 ( 1 - p1 ) i - 2 = l + u p2 (1 - (1 - p1 ) i - 1 ) 和 u (1 - p1 ) i - 1 . 由 此可知 ,任意一个半监督单标记迭代学习中 ,训练样 本总 数 为 ∑ MaxIter i = 1 ( l + up2 (1 - (1 - p1 ) i- 1 ) ) = MaxIter ( l + up2 ) - up2 1 - (1 - p1 ) MaxIter p1 . 由于 SML_SVM 将半监督多标记学习问题转化为| Y| 个 半监督单标记学习问题 ,在 SML_SVM 中 ,参与训 练的样 本总数为 | Y| ( MaxIter ( l + u p2 ) - u p2 1 - (1 - P1 ) MaxIter p1 ) . 由于| Y| ( MaxIter ( l + u p2 ) - u p2 1 - (1 - p1 ) MaxIter p1 ) < | Y| MaxIter ( l + u p2 ) < | Y| MaxIter ( l + u) ,故 SML _SVM 算法的训练样本复 杂度为 O(MaxIter) | Y| ( l + u) . 表 1 SML_SVM 算法步骤 Table 1 Steps of SML_SVM algorithm SML_SVM(L ,U , K ,MaxIter , p1 , p2 ) 输入参数 : L :已标记数据集 ; U :未标记数据集 ; K:近邻数 ; MaxIter :半监督训练最大迭代次数 ; p1 :从 U 中选择构建 U′的未标记样本比例 ; p2 :从 U′中选择构建 L′的未标记样本比例. 步骤 : 1)把多标记数据集 L 根据 PT4 策略转化为单标记数 据集 L′; 2)根据训练若干个单标记 SVM 分类器 ,构成多标记 分类器 SML_SVM ; 3) Iter ←1 ; 4) while (Iter < = MaxIter) a) 用 SML_SVM 对 U 标记 ; b)从 U 计算标记信任度最高的 p1 比例的样本 ,组 成 U′; c) 计算 U′中样本标记的最大后验概率 ,取 p2 比例 的后验概率最高的样本组成 L′; d)跟据 L ∪L′,训练新的 SML_SVM ; e) Iter ←Iter + 1 ; 5) end while. 输出 : 半监督多标记学习器 SML_SVM · 68 · 智 能 系 统 学 报 第 3 卷
第1期 陈晓峰，等：半监督多标记学习的基因功能分析 ·87 策略的半监督多标记支持向量算法，它同时使用己 3基因功能分析 标记的多标记样本和未标记的多标记样本训练多标 记支持向量机，在每轮训练中，具有最高信任度的样 3.1实验设置 文中实验主要是在酵母菌基因数据集和gem 本会加入到训练集，反复训练，直到达到停止条件 base蛋白质功能数据集上进行的.MLSVM(multi- 与MLSVM相比，SML_SVM可以根据未标记样本 提高分类器性能，而与Self-training ML SVM相比， label support vector machine)是基于PT4策略的 多标记支撑向量机算法，它是监督学习算法，在 SML SVM选择未标记样本加入训练集的策略是 MLSVM中，仅使用己标记数据训练多标记分类 不同的，性能更优.文中的实验中，将SML_SVM分 器，未标记数据不参与训练，这就意味着未标记数据 别与MLSVM和Self-training MLSVM对比，考察 不能用于提高分类器的精度.在半监督学习中，自训 SML_SVM的性能 练策略是一种常用的半监督学习方法).在自训练 3.2酵母菌基因功能分析 的半监督学习中，首先根据少量的已标记数据训练 酵母菌基因数据集(yeast saccharomyces cere- 出分类器，然后用该分类器对未标记数据进行分类， visiae)是常用的多标记学习算法性能测试数据 再把符合预定准则（如信任度最高）的分类结果视为 集6,12].它分为训练集和测试集2个部分，其中， 己标记数据加入到训练集中，根据更新后的训练集 训练集的样本为1500个，测试集的样本为917个， 重新训练分类器，直到达到训练停止条件为止.自训 特征为103维，均为数值型，样本标记为14种，标记 练ML SVM是基于自训练策略的半监督多标记支 均值为4.25，标记密度为0.3.图1给出了yeast基 持向量算法 因功能分类第1层次及基因YAL041W的4个 MLSVM是只根据已标记的多标记样本训练 功能 多标记支持向量机的算法，未标记的多标记样本并 没有被利用.Self-training MLSVM是基于自训练 Yeast Saccharomyces cerevisiae Metabolis Transcripti Transport onic Faculitanon Homeostasis Energy Protein Synthesis Cellular Protein Death and Aging Biogenesis Destination Cell.Transport, Cell Growth I ransport Cell Division Cellular Cell.Communi cation,Signal Mechanisms DNA synthesis Organization Transduction Transposable ts Viral and YLL041W Plasmid Proteins 图1 Yeast基因功能分类第1层次，基因YAL041W有4个功能（粗框表示） Fig I The first level of hierarchy of the yeast gene functional classes, and gene YAL041W with four labels (shown with bold borders) 实验1对比SML_SVM与MLSVM和Self 信任度最高的10%未标记样本组成候选未标记数 training MLSVM的性能.实验方法是从训练集中 据集U'SML SVM算法的近邻数K取3.实验重 随机抽取10%，即150个样本，组成已标记数据集 复10次，平均结果如表2所示，其中“↓”表示该性 L,即1=150，将训练集余下的1350个样本和测试 能指标越小越好，“↑”表示该性能指标越大越好 集917个样本组成未标记数据集U,即u=2267.实 实验2考察了SML_SVM算法的近邻数K 验结果的性能指标均是在yeast数据集的测试集上 对算法的影响.实验中，SML SVM算法的已标记 取得的.在实验中，3种算法的核函数均为高斯核， 数据集、未标记数据集、核函数参数和最大迭代次数 C=100.0=0.1.SML_SVM Self-training MLS- 与实验1相同.表3给出K在不同取值时SML VM的最大均迭代次数均为10次，每轮训练均选取 SVM算法性能指标的均值，其中K=3时的实验结 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
3 基因功能分析 311 实验设置 文中实验主要是在酵母菌基因数据集和 gen2 base 蛋白质功能数据集上进行的. ML SVM (multi2 label support vector machine) 是基于 PT4 策略的 多标记支撑向量机算法 ,它是监督学习算法[ 11 ] . 在 ML SVM 中 ,仅使用已标记数据训练多标记分类 器 ,未标记数据不参与训练 ,这就意味着未标记数据 不能用于提高分类器的精度. 在半监督学习中 ,自训 练策略是一种常用的半监督学习方法[11 ] . 在自训练 的半监督学习中 ,首先根据少量的已标记数据训练 出分类器 ,然后用该分类器对未标记数据进行分类 , 再把符合预定准则(如信任度最高) 的分类结果视为 已标记数据加入到训练集中 ,根据更新后的训练集 重新训练分类器 ,直到达到训练停止条件为止. 自训 练 ML SVM 是基于自训练策略的半监督多标记支 持向量算法. MLSVM 是只根据已标记的多标记样本训练 多标记支持向量机的算法 ,未标记的多标记样本并 没有被利用. Self2training ML SVM 是基于自训练 策略的半监督多标记支持向量算法 ,它同时使用已 标记的多标记样本和未标记的多标记样本训练多标 记支持向量机 ,在每轮训练中 ,具有最高信任度的样 本会加入到训练集 ,反复训练 ,直到达到停止条件. 与 ML SVM 相比 ,SML_SVM 可以根据未标记样本 提高分类器性能 ,而与 Self2training ML SVM 相比 , SML_SVM 选择未标记样本加入训练集的策略是 不同的 ,性能更优. 文中的实验中 ,将 SML_SVM 分 别与 ML SVM 和 Self2training MLSVM 对比 ,考察 SML_SVM 的性能. 312 酵母菌基因功能分析 酵母菌基因数据集 (yeast saccharomyces cere2 visiae) 是常用的多标记学习算法性能测试数据 集[6 ,11 ,22 ] . 它分为训练集和测试集 2 个部分 ,其中 , 训练集的样本为 1 500 个 ,测试集的样本为 917 个 , 特征为 103 维 ,均为数值型 ,样本标记为 14 种 ,标记 均值为 4125 ,标记密度为 013. 图 1 给出了 yeast 基 因功能分类第 1 层次及基因 YAL041W 的 4 个 功能. 图 1 Yeast 基因功能分类第 1 层次 ,基因 YAL041W 有 4 个功能(粗框表示) Fig11 The first level of hierarchy of the yeast gene functional classes , and gene YAL041W with four labels (shown with bold borders) 实验 1 对比 SML_SVM 与 ML SVM 和 Self2 training ML SVM 的性能. 实验方法是从训练集中 随机抽取 10 % ,即 150 个样本 ,组成已标记数据集 L ,即 l = 150 ,将训练集余下的 1 350 个样本和测试 集 917 个样本组成未标记数据集 U ,即u = 2 267. 实 验结果的性能指标均是在 yeast 数据集的测试集上 取得的. 在实验中 ,3 种算法的核函数均为高斯核 , C = 100 ,σ= 011. SML_SVM 和 Self2training MLS2 VM 的最大均迭代次数均为 10 次 ,每轮训练均选取 信任度最高的 10 %未标记样本组成候选未标记数 据集 U′. SML_SVM 算法的近邻数 K 取 3. 实验重 复 10 次 ,平均结果如表 2 所示 ,其中“↓”表示该性 能指标越小越好“, ↑”表示该性能指标越大越好. 实验 2 考察了 SML _SVM 算法的近邻数 K 对算法的影响. 实验中 ,SML _SVM 算法的已标记 数据集、未标记数据集、核函数参数和最大迭代次数 与实验 1 相同. 表 3 给出 K 在不同取值时 SML _ SVM 算法性能指标的均值 ,其中 K = 3 时的实验结 第 1 期 陈晓峰 ,等 :半监督多标记学习的基因功能分析 · 78 ·