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