第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 ·
·88 智能系统学报 第3卷 果己经在表2中给出，故不再重复 在表2中可以看出，在5个性能指标上，SML SVM算法都有一定的提高.Self-training MLSVM 表2 Yeast数据集的实验结果 5个性能指标上都是最低的，在平均精度上甚至低 Table 2 Experimental results of yeast dataset 于随机猜测.显然，Self-training MLSVM会把每次 Self-training 训练的错误累计到分类器中，不但不能提高性能，反 SML SVM SVM MLSVM 而使性能严重下降。 表3的实验结果显示，近邻数K对SML_SVM Hamming Loss 0 24778 0 011 0 27099 010 049938015 的影响不大，较好的结果是在K=2和K=5时得 到的，然而，在K取其他值时，SML_SVM变化仍然 Ranking Loss↓02389015026146h017049729h24 比较小.这说明SML_SVM对K是鲁棒的 0 neeror↓028571n02903707n0B4065649h037 最大迭代次数对SML SVM的影响比较大，从 表4可以看出，当MaxIter较小的时候，算法的性能 Coverage↓ 7775h40788220411 1069030512 是差的，随着MaxIter的增加，性能逐渐变好，当达 Average Precision t Q 7081022 0 6614021 0 435960 023 到一定限度后，增加最大迭代次数就不起作用了.事 实上，最多迭代10次就可以达到最好的性能.这说 明，SML_SVM对未标记样本数据集的内在信息的 表3K的不同取值时的实验结果 利用是有限度的，在最大后验概率准则下，避免由于 Table 3 Experimental results with different K 引入未标记样本参与训练而带来的累计训练误差 2 5 6 3.3 Genbase蛋白质功能预测分析 Genbase是生物蛋白质结构数据集1,2).训练 Hamming Loss↓02462202443502444302462024445 集有463个蛋白质样本，测试集有199个蛋白质样 Ranking Loss↓023876024680241260.23878024126 本.特征为1185维，所有的属性均为离散的.在gen base蛋白质数据集中，共有27种标记，标记均值为 One-error↓ 02879027699027808028791027809 1.35,标记密度为0.05.表5列出了若干蛋白质族 和它们对应的功能，其中PDOC X×××X表示蛋 Coverage↓ 766197.90737.70777.661917.70782 白质族」 Average Precision↑0700840.69647070080700850.70080 表5蛋白质族及其对应功能 Table 5 Protein family and its functions 实验3考察最大迭代次数对算法的影响.实验 蛋白质族 功能 中其他参数均与实验1相同.为简洁起见，仅在表4 PD0C00064 氧还原酶 给出K-3,MaxIter取不同值时，SML SVM算法 性能指标的均值」 PDOC00154 异构酶 PD0C00224 细胞活素类和增长因子 表4K=3,lax Iter取不同值时的实验结果 PDOC00343 结构蛋白质 ble 4 Experimental results with different Maxlter when K=3 PDOC00561 受体 Iteration 2 45 0 PD0C00662 DNA或RNA关联蛋白质 Hamming L0ss↓02475502477024661024624024778 PD0C00670 转移酶 Ranking Loss↓02412502402602391802387702389 PD0C00791 蛋白质分泌和衍生物 Oneerror↓ 030316028353028899028791028571 PD0C50007 水解酶 Coverage↓765987.68167.65767.66217.7775 在该实验中，参数设置同3.2节酵母菌基因功 Average Precision↑0694540699670700130.70083070081 能分析实验相同.表6~8给出实验结果.表6表明， C 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
果已经在表 2 中给出 ,故不再重复. 表 2 Yeast 数据集的实验结果 Table 2 Experimental results of yeast dataset SML_SVM SVM Self2training MLSVM Hamming Loss ↓ 01247 78 ±01011 01270 99 ±01010 01499 38 ±01015 Ranking Loss ↓ 01238 9 ±01015 01261 46 ±01017 01497 29 ±01024 One2error ↓ 01285 71 ±01029 01370 77 ±01034 01656 49 ±01037 Coverage ↓ 71777 5 ±0140 71882 2 ±01411 101690 3 ±01512 Average Precision ↑ 01700 81 ±01022 01661 4 ±01021 01435 96 ±01023 表 3 K的不同取值时的实验结果 Table 3 Experimental results with different K K 2 4 5 6 7 Hamming Loss ↓ 01246 22 01244 35 01244 43 01246 22 01244 45 Ranking Loss ↓ 01238 76 01246 8 01241 26 01238 78 01241 26 One2error ↓ 01287 9 01276 99 01278 08 01287 91 01278 09 Coverage ↓ 71661 9 71907 3 71707 7 71661 91 71707 82 Average Precision ↑01700 84 01696 47 01700 8 01700 85 01700 80 实验 3 考察最大迭代次数对算法的影响. 实验 中其他参数均与实验 1 相同. 为简洁起见 ,仅在表 4 给出 K = 3 ,MaxIter 取不同值时 ,SML_SVM 算法 性能指标的均值. 表 4 K= 3 ,MaxIter 取不同值时的实验结果 Table 4 Experimental results with different MaxIter when K= 3 Iteration 2 3 4 5 10 Hamming Loss ↓ 01247 55 01247 7 01246 61 01246 24 01247 78 Ranking Loss ↓ 01241 25 01240 26 01239 18 01238 77 01238 9 One2error ↓ 01303 16 01283 53 01288 99 01287 91 01285 71 Coverage ↓ 71659 8 71681 6 71657 6 71662 1 71777 5 Average Precision ↑01694 54 01699 67 01700 13 01700 83 01700 81 在表 2 中可以看出 ,在 5 个性能指标上 ,SML_ SVM 算法都有一定的提高. Self2training ML SVM 5 个性能指标上都是最低的 ,在平均精度上甚至低 于随机猜测. 显然 ,Self2training ML SVM 会把每次 训练的错误累计到分类器中 ,不但不能提高性能 ,反 而使性能严重下降. 表 3 的实验结果显示 ,近邻数 K 对 SML_SVM 的影响不大 ,较好的结果是在 K = 2 和 K = 5 时得 到的 ,然而 ,在 K 取其他值时 ,SML_SVM 变化仍然 比较小. 这说明 SML_SVM 对 K 是鲁棒的. 最大迭代次数对 SML_SVM 的影响比较大 ,从 表 4 可以看出 ,当 MaxIter 较小的时候 ,算法的性能 是差的 ,随着 MaxIter 的增加 ,性能逐渐变好 ,当达 到一定限度后 ,增加最大迭代次数就不起作用了. 事 实上 ,最多迭代 10 次就可以达到最好的性能. 这说 明 ,SML_SVM 对未标记样本数据集的内在信息的 利用是有限度的 ,在最大后验概率准则下 ,避免由于 引入未标记样本参与训练而带来的累计训练误差. 313 Genbase 蛋白质功能预测分析 Genbase 是生物蛋白质结构数据集[11 , 23 ] . 训练 集有 463 个蛋白质样本 ,测试集有 199 个蛋白质样 本. 特征为1 185维 ,所有的属性均为离散的. 在 gen2 base 蛋白质数据集中 ,共有 27 种标记 ,标记均值为 1135 ,标记密度为 0105. 表 5 列出了若干蛋白质族 和它们对应的功能 ,其中 PDOC ×××××表示蛋 白质族. 表 5 蛋白质族及其对应功能 Table 5 Protein family and its functions 蛋白质族 功能 PDOC00064 氧还原酶 PDOC00154 异构酶 PDOC00224 细胞活素类和增长因子 PDOC00343 结构蛋白质 PDOC00561 受体 PDOC00662 DNA 或 RNA 关联蛋白质 PDOC00670 转移酶 PDOC00791 蛋白质分泌和衍生物 PDOC50007 水解酶 在该实验中 ,参数设置同 312 节酵母菌基因功 能分析实验相同. 表 6～8 给出实验结果. 表 6 表明 , · 88 · 智 能 系 统 学 报 第 3 卷
第1期 陈晓峰，等：半监督多标记学习的基因功能分析 ·89· SML_SVM的性能比MLSVM和Self-training 于后验概率最大原则对未标记样本分类，通过迭代 MLSVM更优，在5个指标上均达到最好.SML 的方式求解每个半监督单标记学习问题.实验表明， SVM在K,MaxIter参数上的实验结论与3.2节酵 SML SVM比自训练MLSVM和MLSVM性能更 母菌基因功能分析实验相似，且最大迭代次数Max 好，提高多标记学习的性能.在yeast基因功能分析 Iter对SML_SVM的影响比较大 和genbase蛋白质数据上的实验表明，SML_SVM 能利用未标记样本的信息，提高多标记学习的性能， 表6 Genbase数据集实验结果 SML SVM算法的不利之处是由于将多标记问题 Table 6 Experimental results of genbase dataset 转化为若干个不相关的单标记问题，所以，各标记间 SML_SVM MLSVM Self-training 的信息在算法中没有得到充分的利用，未来的工作 MLSVM 是研究标记间信息对半监督多标记学习的影响」 Hamming Loss X103 5 45454 6455426 4686±259 参考文献： Ranking Loss X103 4 4546 84249占940682254 [1]EISEN M B,SPELLMAN P T,BROWN P O,et al. Cluster analysis and display of genome-wide expression 0 neerror XI0~2↓31818±226377122820503844 patterns[C]//Proceedings of the National Academy of Science of the United States of America.Washington,D. Coverage↓ 05409100854059187h09441.07159034 C,USA,1998. [2]TAMAYO P,SLONIM D,MESIROV J,et al.Inter- Average Precision 0 959 89 0 0379 0 928 996 4520 595 65 043 preting patterns of gene expression with self-organizing maps[C]//Proceedings of the National Academy of Sci- 表7K取不同值时的实验结果 ences of the United States of America.Washington.D. Table 7 Experimental results with different K C,USA,1999. 2 4567 8 [3]WU S,LIEW A WC,YAN H,et al.Cluster analysis Hamming Loss XI0-3↓6181860455618185455604566364 of gene expression data based on self-splitting and mer- Ranking Loss003↓688263241683244546324121352 ging competitive learning[J].IEEE Transactions on In formation Technology in Biomedicine,2004,8(1):5-15. 0 eror02↓4431844304544318318182704528409 [4]MCCALLUM A K.Multi-label text classification with a Coverage 059773057841059773058091057841060341 mixture model trained by EM[C]//Working Notes of Average Precis0n↑09366509436109366509398909436109366 the AAAI'99 Workshop on Text Learning.Orlando, USA,1999. 表8K=3时不同的实验结果 [5]SCHAPIRE R E,SIN GER Y.Boostexter:a boosting Table 8 Experimental results with different when K=3 based system for text categorization[J].Machine Learn- Iteration 2 3 4 10 ing,2000,39(23):135168. [6]EL ISSEEFF A,WESTON J.A kernel method for multi- Hamming Loss X10~3↓5636456182555015487654545 labeled classification[Cl//Advances in Neural Informa- Ranking Loss XⅪ0-3↓683546027452113444214454 tion Processing Systems 14.Cambridge:MIT Press, 0 neerror X102↓501247126466544521144315 2002 Coverage↓ 0590910583410567305488054091 [7]BOUTELL M R,LUO J,SHEN X,et al.Learning multilabel scene classification [J ]Pattern Recognition, Average Precision↑0.93078093869094250.9434095989 2004,37(9):17571771. [8]OGIHARA LI T M.Detecting emotion in music [C]// 4 结束语 Proceedings of the International Symposium on Music In- formation Retrieval.Maryland,USA:ISMIR Press, 文中提出了基因表达数据的半监督多标记学习 2003. 问题，实现了半监督多标记支撑向量算法SML [9]ZHU X J.Semi-supervised learning literature survey SVM.SML SVM首先使用PT4策略把半监督多 [R].Department of Computer Sciences,University of 标记学习问题转化为半监督单标记问题，然后用基 Wisconsin,Madison,2005. 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
SML _ SVM 的 性 能 比 ML SVM 和 Self2training ML SVM 更优 ,在 5 个指标上均达到最好. SML _ SVM 在 K ,MaxIter 参数上的实验结论与 312 节酵 母菌基因功能分析实验相似 ,且最大迭代次数 Max2 Iter 对 SML_SVM 的影响比较大. 表 6 Genbase 数据集实验结果 Table 6 Experimental results of genbase dataset SML_SVM MLSVM Self2training MLSVM Hamming Loss ×10 - 3 ↓ 51454 5 ±214 61455 4 ±216 46186 ±2519 Ranking Loss ×10 - 3 ↓ 41454 ±316 81424 9 ±319 4016812 ±2514 One2error ×10 - 2 ↓ 31181 8 ±2126 31777 1 ±2128 201503 ±8144 Coverage ↓ 01540 91 ±01085 4 01591 87 ±01094 411071 59 ±0134 Average Precision ↑ 01959 89 ±01037 9 01928 996 ±0145201595 65 ±01043 表 7 K取不同值时的实验结果 Table 7 Experimental results with different K K 2 4 5 6 7 8 Hamming Loss×10 - 3 ↓ 61181 8 61045 5 61181 8 51454 5 61044 5 61636 4 Ranking Loss ×10 - 3 ↓ 61883 2 61324 1 61883 2 41454 61324 1 71135 2 One2error ×10 - 2 ↓ 41431 8 41430 45 41431 8 31181 8 21704 5 21840 9 Coverage ↓ 01597 73 01578 41 01597 73 01580 91 01578 41 01603 41 Average Precision↑ 01936 65 01943 61 01936 65 01939 89 01943 61 01933 65 表 8 K= 3 时不同的实验结果 Table 8 Experimental results with different when K= 3 Iteration 2 3 4 5 10 Hamming Loss ×10 - 3 ↓51636 4 51618 2 51550 1 51487 6 51454 5 Ranking Loss ×10 - 3 ↓ 61835 4 61027 4 51211 3 41442 1 41454 One2error ×10 - 2 ↓ 51012 41712 6 41665 4 41521 1 41431 5 Coverage ↓ 01590 91 01583 41 01567 3 01548 8 01540 91 Average Precision ↑ 01930 78 01938 69 01942 5 01943 4 01959 89 4 结束语 文中提出了基因表达数据的半监督多标记学习 问题 ,实现了半监督多标记支撑向量算法 SML _ SVM. SML_SVM 首先使用 PT4 策略把半监督多 标记学习问题转化为半监督单标记问题 ,然后用基 于后验概率最大原则对未标记样本分类 ,通过迭代 的方式求解每个半监督单标记学习问题. 实验表明 , SML_SVM 比自训练 ML SVM 和 MLSVM 性能更 好 ,提高多标记学习的性能. 在 yeast 基因功能分析 和 genbase 蛋白质数据上的实验表明 ,SML _SVM 能利用未标记样本的信息 ,提高多标记学习的性能. SML_SVM 算法的不利之处是由于将多标记问题 转化为若干个不相关的单标记问题 ,所以 ,各标记间 的信息在算法中没有得到充分的利用 ,未来的工作 是研究标记间信息对半监督多标记学习的影响. 参考文献 : [1 ] EISEN M B , SPELLMAN P T , BROWN P O , et al. Cluster analysis and display of genome2wide expression patterns[ C]/ / Proceedings of the National Academy of Science of the United States of America. Washington ,D. C ,USA , 1998. [2 ] TAMA YO P , SLONIM D , MESIROV J , et al. Inter2 preting patterns of gene expression with self2organizing maps[C]/ / Proceedings of the National Academy of Sci2 ences of the United States of America. Washington ,D. C ,USA , 1999. [3 ]WU S , L IEW A W C , YAN H , et al. Cluster analysis of gene expression data based on self2splitting and mer2 ging competitive learning [J ]. IEEE Transactions on In2 formation Technology in Biomedicine , 2004 , 8 (1) :5215. [4 ]MCCALLUM A K. Multi2label text classification with a mixture model trained by EM [ C ]/ / Working Notes of the AAAI’99 Workshop on Text Learning. Orlando , USA ,1999. [5 ] SCHAPIRE R E , SIN GER Y. Boostexter : a boosting2 based system for text categorization[J ]. Machine Learn2 ing , 2000 , 39 (223) :1352168. [6 ] EL ISSEEFF A , WESTON J. A kernel method for multi2 labeled classification[ C]/ / Advances in Neural Informa2 tion Processing Systems 14. Cambridge : MIT Press , 2002. [7 ] BOU TELL M R , LUO J , SHEN X , et al. Learning multi2label scene classification [J ]. Pattern Recognition , 2004 , 37 (9) : 175721771. [8 ]O GIHARA L I T M. Detecting emotion in music [ C]/ / Proceedings of the International Symposium on Music In2 formation Retrieval. Maryland , USA : ISMIR Press , 2003. [ 9 ] ZHU X J. Semi2supervised learning literature survey [ R ]. Department of Computer Sciences , University of Wisconsin , Madison , 2005. 第 1 期 陈晓峰 ,等 :半监督多标记学习的基因功能分析 · 98 ·
·90· 智能系统学报 第3卷 [10]ZHANG ML,ZHOU Z H.ML-KNN:a lazy learning GON G Xiujun,SHI Zhongzhi.Semi-supervised web approach to multi-label learning [J ]Pattern Recogni- mining based on bayes latent semantic model [J ]Jour- tion,2007,40(7):2038-2048. nal of Software,2002,12(8):15081514. [11]TSOUMA KAS G,KA TA KIS I.Multi-label classifica- [20]彭雅，林亚平，陈治平.TFDF_NB协同训练算法 tion:an overview [J].International Journal of Data [0].小型微型计算机，2004,25(12)：2243-2246. Warehousing and Mining,2007,3(3):1-13. PEN G Ya,L IN Yaping,CHEN Zhiping.TFIDF-NB [12]CLARE A,KING R D.Knowledge discovery in multi- co-operative training algorithm [J ]Mini-micro Sys label phenotype data[C]//Proceedings of the 5th Euro- tems,2004,25(12):22432246. pean Conference on Principles of Data Mining and [21]KLAUS B,JOHANNS F,EYKE H.A unified model Knowledge Discovery (PKDD 2001).Freiberg,Germa- for multilabel classification and ranking C]//Proceed- ny:Springer,2001. ing of the 15th Eureopean Conference on Artificial Intel- [13 ]LUO X,ZINCIR H.Evaluation of two systems on ligence.Riva del Garda,Italy:IOS Press,2006. multi-class multi-label document classification [C]// [22]PAVL IDIS P,WESTON J,CAIJ,et al.Combining Lecture Notes in Computer Science.Freiberg,Germa- microarray expression data and phylogenetic protellles ny:Springer,2005. to learn functional categories using support vector ma- [14]GODBOL E S,SARAWA GI S.Discriminative methods chines [R].CUCS-011-000,Department of Computer for multi-labeled classification [Cl//Lecture Notes in Science,Columbia University,Columbia,2000. Computer Science.Germany:Springer,2004. [23]DIPLARIS S,TSOUMA KAS G,MITKAS P,et al. [15]ZHOU Z H,ZHANG M L.Multi-instance multi-label Protein classification with multiple algorithms [C1// learning with application to scene classification [C]// Lecture Notes in Computer Science.Volos,Greece: Advances in Neural Information Processing Systems Springer,2005. Cambridge:MIT Press,2007. 作者简介： [16]ZHANG ML,ZHOU Z H.Multilabel neural networks 陈晓峰，男，1977年生，博士研究生，主要 with applications to functional genomics and text catego- 研究方向为机器学习、模式识别 rization[J ]IEEE Transactions on Knowledge and Data Engineering,2006,18(10):1338-1351. [17]施彤年，卢忠良，荣融，等.多类多标签汉语文本自动 分类的研究[U」.情报学报，2003,22(3)：306309. SHI Tongnian,LU Zhongliang,RONG Rong,et al. 王士同，男，1964年生，教授，博士生导 Research on the Chinese text categorization of multi- 师，主要研究方向为模糊人工智能、模式识 classification and multi-label [J].Journal of the China 别、图像处理和生物信息学等，先后十多次留 Society for Scientific and Technical Information,2003, 学英国、日本和香港地区，在国内外重要杂志 22(3):306309. 上发表学术论文数十篇」 [18 ]LIU Y,JIN R,LIU Y.Semi-supervised multi-label learning by constrained nom negative matrix factoriza- tion [C]//Proceeding of the Twenty-First National 曹苏群，男，1976年生，博士研究生，主要 Conference on Artificial Intelligence,Eighteenth Con- 研究方向为模式识别，图像处理、软件工程 ference on Innovative Applications of Artificial Intelli- 等 gence.Boston:AAAI Press,2006. [l9]宫秀军，史忠植.基于Bayes潜在语义模型的半监督 Web挖掘J1.软件学报，2002,12(8)：1508-1514. @1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
[10 ]ZHAN G M L , ZHOU Z H. ML2KNN : a lazy learning approach to multi2label learning [J ]. Pattern Recogni2 tion , 2007 , 40 (7) : 203822048. [11 ] TSOUMA KAS G, KA TA KIS I. Multi2label classifica2 tion : an overview [J ]. International Journal of Data Warehousing and Mining , 2007 , 3 (3) :1213. [12 ]CLARE A , KIN G R D. Knowledge discovery in multi2 label phenotype data[C]/ / Proceedings of the 5th Euro2 pean Conference on Principles of Data Mining and Knowledge Discovery ( PKDD 2001) . Freiberg , Germa2 ny : Springer , 2001. [ 13 ] LUO X , ZINCIR H. Evaluation of two systems on multi2class multi2label document classification [ C ]/ / Lecture Notes in Computer Science. Freiberg , Germa2 ny : Springer ,2005. [14 ] GODBOL E S , SARAWA GI S. Discriminative methods for multi2labeled classification [ C ]/ / Lecture Notes in Computer Science. Germany : Springer ,2004. [15 ]ZHOU Z H , ZHAN G M L. Multi2instance multi2label learning with application to scene classification [ C ]/ / Advances in Neural Information Processing Systems. Cambridge : MIT Press ,2007. [ 16 ]ZHAN G M L , ZHOU Z H. Multilabel neural networks with applications to functional genomics and text catego2 rization[J ]. IEEE Transactions on Knowledge and Data Engineering , 2006 , 18 (10) : 133821351. [17 ]施彤年 , 卢忠良 , 荣 融 ,等. 多类多标签汉语文本自动 分类的研究[J ]. 情报学报 , 2003 , 22 (3) : 3062309. SHI Tongnian , LU Zhongliang , RON G Rong , et al. Research on the Chinese text categorization of multi2 classification and multi2label [J ]. Journal of the China Society for Scientific and Technical Information , 2003 , 22 (3) : 3062309. [ 18 ] L IU Y , J IN R , L IU Y. Semi2supervised multi2label learning by constrained non2negative matrix factoriza2 tion [ C ]/ / Proceeding of the Twenty2First National Conference on Artificial Intelligence , Eighteenth Con2 ference on Innovative Applications of Artificial Intelli2 gence. Boston : AAAI Press , 2006. [19 ]宫秀军 , 史忠植. 基于 Bayes 潜在语义模型的半监督 Web 挖掘[J ]. 软件学报 , 2002 , 12 (8) :150821514. GON G Xiujun , SHI Zhongzhi. Semi2supervised web mining based on bayes latent semantic model[J ]. Jour2 nal of Software , 2002 , 12 (8) : 150821514. [20 ]彭 雅 , 林亚平 , 陈治平. TFIDF_NB 协同训练算法 [J ]. 小型微型计算机 , 2004 , 25 (12) : 224322246. PEN G Ya , L IN Yaping , CHEN Zhiping. TFIDF2NB co2operative training algorithm [J ]. Mini2micro Sys2 tems , 2004 , 25 (12) : 224322246. [21 ] KLAUS B , JO HANNS F , EYKE H. A unified model for multilabel classification and ranking [ C]/ / Proceed2 ing of the 15th Eureopean Conference on Artificial Intel2 ligence. Riva del Garda , Italy : IOS Press , 2006. [22 ] PAVL IDIS P , WESTON J , CAI J , et al. Combining microarray expression data and phylogenetic protellles to learn functional categories using support vector ma2 chines [ R ]. CUCS20112000 , Department of Computer Science , Columbia University , Columbia , 2000. [23 ]DIPLARIS S , TSOUMA KAS G, MIT KAS P , et al. Protein classification with multiple algorithms [ C ]/ / Lecture Notes in Computer Science. Volos , Greece : Springer , 2005. 作者简介 : 陈晓峰 ,男 ,1977 年生 ,博士研究生 ,主要 研究方向为机器学习、模式识别. 王士同 ,男 , 1964 年生 ,教授 ,博士生导 师 ,主要研究方向为模糊人工智能、模式识 别、图像处理和生物信息学等 ,先后十多次留 学英国、日本和香港地区 ,在国内外重要杂志 上发表学术论文数十篇. 曹苏群 ,男 ,1976 年生 ,博士研究生 ,主要 研究方向为模式识别 ,图像处理、软件工程 等. · 09 · 智 能 系 统 学 报 第 3 卷
