·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 卷