李 永,許 鵬

(北京工業(yè)大學(xué) 軟件學(xué)院,北京 100124)

傳統(tǒng)監(jiān)督學(xué)習(xí)認(rèn)為一個(gè)對(duì)象只具有一個(gè)標(biāo)記類別,屬于“單示例,單標(biāo)記”類型.在上述單一語(yǔ)義的情境中,監(jiān)督學(xué)習(xí)已經(jīng)取得了巨大的發(fā)展成果.然而在真實(shí)世界中,一個(gè)對(duì)象往往同時(shí)具有多種語(yǔ)義信息,屬于“單示例,多標(biāo)記”類型.例如在一篇新聞稿中可同時(shí)包含改革和經(jīng)濟(jì)兩個(gè)主題,一張風(fēng)景圖中天空和云朵往往會(huì)伴隨出現(xiàn),在這種情況下很難用單一語(yǔ)義標(biāo)記去描述對(duì)象信息.為此,多標(biāo)記學(xué)習(xí)框架應(yīng)運(yùn)而生,用于解決真實(shí)世界中一個(gè)對(duì)象同時(shí)具有多個(gè)語(yǔ)義標(biāo)記的問(wèn)題.因其可以良好的反映真實(shí)世界中包含的多語(yǔ)義信息,目前在文本分類[1],圖像標(biāo)注[2],生物基因分析[3]等領(lǐng)域得到了廣泛應(yīng)用.同時(shí)眾多學(xué)者也提出了一些多標(biāo)記學(xué)習(xí)算法,并取得了一定的成功.但是目前大部分已有的多標(biāo)記學(xué)習(xí)算法所采用的共同策略是基于同一特征屬性空間預(yù)測(cè)所有標(biāo)記類別,忽略了每個(gè)標(biāo)記獨(dú)有的特征信息,因此這種思路存在改進(jìn)優(yōu)化的空間.其中ML-KNN[4]作為一種使用簡(jiǎn)單,分類性能優(yōu)異的多標(biāo)記學(xué)習(xí)算法,其數(shù)學(xué)形式相對(duì)簡(jiǎn)單,模型易于優(yōu)化,在實(shí)際應(yīng)用和學(xué)術(shù)科研中得到了廣泛應(yīng)用.但是ML-KNN算法在模型訓(xùn)練過(guò)程中并沒(méi)有考慮標(biāo)記之間的相關(guān)性,同時(shí)也忽略了標(biāo)記特定特征信息.因此,在模型訓(xùn)練過(guò)程中考慮標(biāo)記相關(guān)性和引入標(biāo)記特定特征信息,可以進(jìn)一步提高算法的分類性能,基于此提出了本文算法.本文的整體組織結(jié)構(gòu)如下:第1 部分介紹相關(guān)工作,第2 部分描述本算法的實(shí)現(xiàn),第3 部分給出實(shí)驗(yàn)以及實(shí)驗(yàn)結(jié)果,最后進(jìn)行了總結(jié).

1 相關(guān)工作

在傳統(tǒng)“單示例,單標(biāo)記”的單語(yǔ)義環(huán)境中,傳統(tǒng)監(jiān)督學(xué)習(xí)已經(jīng)取得了巨大的發(fā)展[5–8].然而在真實(shí)世界中,語(yǔ)義信息往往是豐富多彩的,傳統(tǒng)監(jiān)督學(xué)習(xí)已經(jīng)不能對(duì)同時(shí)從屬于多個(gè)標(biāo)記類別下的單個(gè)示例進(jìn)行很好的語(yǔ)義表達(dá).相比于傳統(tǒng)監(jiān)督學(xué)習(xí),多標(biāo)記學(xué)習(xí)可以更好的反映真實(shí)世界中包含的語(yǔ)義信息.不同于傳統(tǒng)監(jiān)督學(xué)習(xí)所假設(shè)的“單示例,單標(biāo)記”情形,多標(biāo)記學(xué)習(xí)所研究的任務(wù)場(chǎng)景屬于“單示例,多標(biāo)記”類型.我們假設(shè)X=Rd代表d維特征空間,Y={l1,l2,···,lq}代表包含q個(gè)標(biāo)記類別的標(biāo)記空間.多標(biāo)記學(xué)習(xí)的任務(wù)是在訓(xùn)練集D={(xi,Yi)|1≤i≤m} 中訓(xùn)練一個(gè)分類器h:X→2Y,預(yù)測(cè)未知示例x∈X 所從屬的標(biāo)記集合h(x)?Y,其中xi∈X為特征空間中的一個(gè)示例,是一個(gè)d維特征向量,Yi∈Y 為示例xi所從屬的標(biāo)記集合,是標(biāo)記空間 Y中的一個(gè)子集.

目前多標(biāo)記學(xué)習(xí)研究所面臨的主要挑戰(zhàn)是標(biāo)記空間爆炸性增長(zhǎng)的問(wèn)題[9].即類別標(biāo)記集合數(shù)隨著標(biāo)記種類的增加而呈指數(shù)級(jí)增長(zhǎng),假設(shè)樣本中包含有q個(gè)類別標(biāo)記信息,則標(biāo)記輸出空間規(guī)模即可達(dá)到 2q級(jí)別的大小,為每個(gè)標(biāo)記子集單獨(dú)訓(xùn)練一個(gè)分類器是不切實(shí)際的.為了解決這個(gè)標(biāo)記空間爆炸的問(wèn)題,目前關(guān)于多標(biāo)記學(xué)習(xí)的研究大都集中在通過(guò)挖掘標(biāo)記之間的相關(guān)性來(lái)降低指數(shù)級(jí)別增長(zhǎng)的標(biāo)記空間.根據(jù)標(biāo)記相關(guān)性的利用策略,可以將多標(biāo)記學(xué)習(xí)算法分為3 類:(1)一階策略,完全忽略標(biāo)記之間的相關(guān)性,只是將一個(gè)多分類問(wèn)題轉(zhuǎn)換為多個(gè)獨(dú)立的二分類問(wèn)題,這類方法雖然實(shí)現(xiàn)簡(jiǎn)單但是缺少良好的泛化性能.(2)二階策略,考慮標(biāo)記之間的成對(duì)關(guān)聯(lián),例如相關(guān)標(biāo)記與無(wú)關(guān)標(biāo)記之間的排序關(guān)系,兩兩標(biāo)記之間的交互關(guān)系等構(gòu)造多標(biāo)記學(xué)習(xí)框架.這類算法具有一定的泛化性能,但是無(wú)法很好的解決標(biāo)記之間的關(guān)系超過(guò)二階時(shí)的問(wèn)題.(3)高階策略,考慮單個(gè)標(biāo)記與其它全部標(biāo)記之間的相關(guān)性,這類算法可以很好的反映真實(shí)世界的標(biāo)記相關(guān)性,但同時(shí)模型復(fù)雜度往往較高.目前眾多學(xué)者也提出了一些多標(biāo)記學(xué)習(xí)算法,例如由Boutell 等提出的一階策略算法BR (Binary Relevance)[10],由Fürnkranz 等提出的二階策略算法Calibrated Label Ranking[11],由Read 等提出的高階策略算法Classifer Chains[12]等.上述算法的共同點(diǎn)是將多分類問(wèn)題分解為多個(gè)二分類問(wèn)題進(jìn)行解決,屬于問(wèn)題轉(zhuǎn)換型.由Clare 等提出的一階策略算法ML-KNN,ML-DT[13]和Elisseeff A 提出的二階策略算法Rank-SVM[14]等算法是采用當(dāng)前的機(jī)器學(xué)習(xí)算法直接處理多分類問(wèn)題,屬于算法適應(yīng)型.但無(wú)論是問(wèn)題轉(zhuǎn)換型算法還是算法適應(yīng)型算法,上述提到的算法在預(yù)測(cè)標(biāo)記時(shí)都是假設(shè)所有標(biāo)記共享同一特征空間,并未對(duì)每種類別標(biāo)記獨(dú)有的特征信息進(jìn)行考慮.即多標(biāo)記學(xué)習(xí)框架得到的q個(gè)實(shí)值函數(shù) {f1,f2,···,fq}都是基于相同的屬性特征空間訓(xùn)練而來(lái).但是這種思路可能并不是最優(yōu)的,例如在圖像識(shí)別領(lǐng)域,在判斷“天空”和“沙漠”時(shí),顏色特征是需要優(yōu)先考慮的,而在判斷“藍(lán)天”和“大海”時(shí),考慮紋理特征相關(guān)屬性會(huì)大大提高分類器的性能.由此可見(jiàn),每個(gè)標(biāo)記都可能具有與其最大相關(guān)性的屬性特征,考慮每個(gè)標(biāo)記獨(dú)有的屬性特征對(duì)于提高算法分類性能具有一定的幫助,這些屬性特征是對(duì)該標(biāo)記最有區(qū)別度的特征,稱為標(biāo)記特定特征信息.

其中,ML-KNN 作為一種使用簡(jiǎn)單,分類性能高效的算法,在實(shí)際應(yīng)用中得到了廣泛應(yīng)用.但是ML-KNN算法屬于一階策略,并未對(duì)標(biāo)記之間相關(guān)性進(jìn)行考慮,同時(shí)也沒(méi)有考慮標(biāo)記特定特征信息.雖然該算法取得了巨大的成果,但是并未對(duì)標(biāo)記相關(guān)性和標(biāo)記特定特征信息加以利用,存在優(yōu)化改進(jìn)的空間.由Zhang 等提出了LIFT 算法[15]首次提出從引入標(biāo)記特定特征信息這一角度出發(fā)的研究思路,針對(duì)每一個(gè)標(biāo)記信息提取其特征信息,從而構(gòu)建標(biāo)記特征空間,之后基于標(biāo)記特征空間進(jìn)行模型訓(xùn)練.該算法基于多種公開(kāi)數(shù)據(jù)集證明了其思路的有效性,為多標(biāo)記學(xué)習(xí)指明了一個(gè)新的研究方向.但是該算法并未考慮標(biāo)記之間的相關(guān)性,屬于一階策略算法.基于此,我們通過(guò)融入標(biāo)記相關(guān)性和引入標(biāo)記特定特征信息對(duì)ML-KNN 算法進(jìn)行改進(jìn),進(jìn)一步提高算法分類性能.

2 ML-KNN 算法以及改進(jìn)算法

2.1 ML-KNN 算法

ML-KNN 算法是在k近鄰算法的基礎(chǔ)上,綜合貝葉斯理論提出的能夠處理多標(biāo)記分類問(wèn)題的KNN 算法.在此引入一些符號(hào)用于對(duì)該算法進(jìn)行說(shuō)明.在多標(biāo)記訓(xùn)練數(shù)據(jù)集D={(xi,Yi)|1≤i≤m} 中,xi∈X,Yi∈Y,Yx為示例xi所對(duì)應(yīng)的q維標(biāo)記向量.如果示例x具有類別標(biāo)記l(1≤l≤q),則定義Yx(l)=1,否則Yx(l)=0.另外假設(shè)N(x)代表示例x在訓(xùn)練集D中的k個(gè)近鄰集合,對(duì)這k個(gè)近鄰集合中擁有標(biāo)記l的樣本數(shù)量用Cx(l)表示,其中:

其中,Cx代表了示例x所對(duì)應(yīng)的k個(gè)近鄰集合中所包含的標(biāo)記信息.ML-KNN 算法為懶惰算法,當(dāng)有新的測(cè)試示例t需要進(jìn)行預(yù)測(cè)分類時(shí),ML-KNN 首先識(shí)別示例t在訓(xùn)練數(shù)據(jù)集D中的k個(gè)近鄰集合N(t),在這里設(shè)定H1l代表示例t擁有標(biāo)記l,相反,當(dāng)示例t沒(méi)有標(biāo)記l時(shí)用H0l表示.另外引入Elj表示在N(t)中有j個(gè)示例擁有標(biāo)記l,其中j∈{0,1,···,k},基于向量Ct,示例t所對(duì)應(yīng)的類別向量Yt可以使用如下最大后驗(yàn)概率來(lái)計(jì)算.

該式所代表的含義為已知在測(cè)試示例t的k個(gè)近鄰集合中有Ct(l)個(gè)樣本與標(biāo)記l相關(guān),示例t與標(biāo)記l是否相關(guān)取決于N(t)中是否與標(biāo)記l相關(guān)的最大概率.根據(jù)貝葉斯規(guī)則,上式可以進(jìn)一步變換為:

由上述公式可知,計(jì)算Yt(l)需要得到先驗(yàn)概率和條件概率這兩個(gè)值都是可以從訓(xùn)練數(shù)據(jù)樣本計(jì)算得到的.

2.2 基于ML-KNN 算法的改進(jìn)算法

LIFT 算法是由張敏靈等學(xué)者在研究多標(biāo)記學(xué)習(xí)算法時(shí)提出的一種全新的算法.該算法不同于之前研究點(diǎn)集中于挖掘標(biāo)記之間相關(guān)性上,而忽略了標(biāo)記特定特征信息.LIFT 算法從挖掘標(biāo)記特征這一角度出發(fā),針對(duì)每一個(gè)標(biāo)記類別,通過(guò)挖掘其特征信息構(gòu)建標(biāo)記特征空間,在模型訓(xùn)練過(guò)程中引入標(biāo)記特征,并且經(jīng)過(guò)大量實(shí)驗(yàn)表明LIFT 算法分類性能在公開(kāi)數(shù)據(jù)集上優(yōu)于其它多標(biāo)記學(xué)習(xí)算法,同時(shí)也證明了在模型訓(xùn)練過(guò)程中引入標(biāo)記特定特征信息提高算法分類性能這一思路的有效性,為后續(xù)多標(biāo)記學(xué)習(xí)研究提供了一種新的思路.

2.2.1 LIFT 算法基本模型

LIFT 算法通過(guò)對(duì)訓(xùn)練樣本中的每個(gè)類別標(biāo)記進(jìn)行聚類操作,分析每個(gè)標(biāo)記的特征信息,將原始樣本集合根據(jù)特征標(biāo)記劃分為與當(dāng)前標(biāo)記呈正相關(guān)的樣本和負(fù)相關(guān)的樣本.具體來(lái)說(shuō),對(duì)于標(biāo)記lj∈Y,根據(jù)式(4)和式(5)分別計(jì)算其正相關(guān)的示例集合Pj和負(fù)相關(guān)示例集合Nj.

其中,Yi表示實(shí)例xi所對(duì)應(yīng)的標(biāo)記向量,D為訓(xùn)練數(shù)據(jù)集,Pj代表包含標(biāo)記lj的示例集合,Nj代表不包含標(biāo)記lj的示例集合.之后采用K-means 聚類算法分別對(duì)兩個(gè)示例集合進(jìn)行聚類操作,得到在Pj上的個(gè)聚類中心和在Nj上的個(gè)聚類中心為了解決聚類中心不平衡的問(wèn)題,LIFT算法設(shè)定mj==,其中這兩個(gè)聚類中心集合分別代表著正負(fù)相關(guān)示例集合的內(nèi)在特征結(jié)構(gòu),可作為構(gòu)建標(biāo)記特定特征空間的基礎(chǔ).為了構(gòu)建標(biāo)記lj的特定特征空間Zj,采用如下映射φj:X→Zj,φj表達(dá)如下:

其中,d(·,·)代表兩個(gè)向量之間的歐式距離.根據(jù)映射φj,可以將原始訓(xùn)練數(shù)據(jù)集D轉(zhuǎn)換為標(biāo)記lj對(duì)應(yīng)的二分類訓(xùn)練集Z.之后在新的訓(xùn)練集Z上進(jìn)行模型的訓(xùn)練,可以構(gòu)建出一個(gè)基于標(biāo)記特定特征推導(dǎo)出的二分類器簇一般地,對(duì)于標(biāo)記lj∈Y,其對(duì)應(yīng)的二分類訓(xùn)練數(shù)據(jù)集可由映射φj表示為:

其中,如果標(biāo)記lj∈Yi,Yi(j)=1,否則Yi(j)=0.基于訓(xùn)練數(shù)據(jù)集,可推導(dǎo)出一個(gè)分類器:Zj→R.對(duì)于未知示例u,其對(duì)應(yīng)的標(biāo)記集合可以形式化的表示為其中t代表一個(gè)闕值函數(shù),一般設(shè)置為常數(shù)0.

2.2.2 MLF-KNN 算法

ML-KNN 算法屬于一階策略算法,在模型訓(xùn)練過(guò)程中沒(méi)有考慮標(biāo)記之間的相關(guān)性信息,同時(shí)在預(yù)測(cè)標(biāo)記時(shí)是基于相同的屬性特征集合,忽略了每個(gè)標(biāo)記所獨(dú)有的屬性特征信息,因此ML-KNN 算法存在優(yōu)化改進(jìn)的空間.LIFT 算法經(jīng)過(guò)大量實(shí)驗(yàn)表明該算法的分類性能與其它多標(biāo)記學(xué)習(xí)算法相比具有一定的競(jìng)爭(zhēng)力,證明了在模型訓(xùn)練過(guò)程中引入標(biāo)記特定特征信息可以提高算法分類性能這一思路的可行性和有效性.為此,我們借鑒該思路,對(duì)ML-KNN 算法進(jìn)行改進(jìn),并且融入標(biāo)記相關(guān)性信息,提出基于標(biāo)記特定特征新的多標(biāo)記分類新算法MLF-KNN (Multi-Label Feature-K Nearest Neighbor).本算法首先對(duì)多標(biāo)記訓(xùn)練樣本集合進(jìn)行預(yù)處理,通過(guò)對(duì)每個(gè)類別標(biāo)記進(jìn)行聚類分析構(gòu)建基本標(biāo)記特征,之后通過(guò)稀疏正則化的方式協(xié)同增強(qiáng)與其它類別標(biāo)記的信息從而增強(qiáng)對(duì)每個(gè)標(biāo)記特征信息的表述,進(jìn)而引入當(dāng)前標(biāo)記與其它標(biāo)記之間的相關(guān)性.基于得到的標(biāo)記特定特征,使用改進(jìn)后的ML-KNN 算法進(jìn)行分類.不失一般性,引入一些符號(hào)進(jìn)行本算法的說(shuō)明.在模型訓(xùn)練之前,首先需要構(gòu)建每個(gè)標(biāo)記所對(duì)應(yīng)的正負(fù)相關(guān)示例集合.對(duì)于訓(xùn)練樣本中的每個(gè)標(biāo)記lk∈Y(1≤k≤q),MLF-KNN 算法根據(jù)式(4)和式(5)將原始示例集合分為mk個(gè) 正相關(guān)特征集合Pk和mk個(gè)負(fù)相關(guān)特征集合Nk,其中mk=r·min(|lk∈Yk|,|lk?Yk|).之后在集合Pk>和Nk中采用K-means 聚類算法構(gòu)建聚類中心,用于構(gòu)建基本標(biāo)記特征空間.在正相關(guān)示例集合Pk中聚類中心可以通過(guò)表示,負(fù)相關(guān)特征集合Nk中聚類中心可以通過(guò)表示.對(duì)于示例x∈X,可通過(guò)計(jì)算示例x與聚類中心之間的距離構(gòu)建其基本標(biāo)記特征,最終生成的基本標(biāo)記特征空間是一個(gè)大小為2mk的矩陣φk:X→R2mk.

其中,d(·,·)不在采用LIFT 算法中的歐式距離進(jìn)行度量,而是采用標(biāo)準(zhǔn)歐式距離進(jìn)行計(jì)算,相比于歐式距離,標(biāo)準(zhǔn)歐式距離對(duì)于兩個(gè)向量中的維度不一致的情況進(jìn)行了考慮,對(duì)于維度不一致的示例具有更好的包容性,根據(jù)式(7),生成標(biāo)記lk的基本特定特征空間.此時(shí)基本標(biāo)記特定特征空間只是針對(duì)標(biāo)記lk所構(gòu)建,并未考慮lk與其它標(biāo)記之間的相關(guān)性.假設(shè)代表標(biāo)記向量lk,類似的,如果lk∈Yi,則yki=1,否則yki=0.進(jìn)一步,設(shè)定:

其中,φk(x)表示除標(biāo)記lk以外的其它所有類別標(biāo)記的特定特征信息,是一個(gè)維度為dk的特征向量,其中dk=將映射 φk應(yīng)用于全部訓(xùn)練樣本上,從而可以構(gòu)建出關(guān)于標(biāo)記lk并且維度為m×dk的標(biāo)記特定特征矩陣Xk,其中為了解決ML-KNN 算法并未考慮標(biāo)記之間相關(guān)性的問(wèn)題,我們需要對(duì)標(biāo)記之間相關(guān)性進(jìn)行挖掘并將相關(guān)性信息引入標(biāo)記特定特征空間中.具體來(lái)說(shuō),需要通過(guò)引入標(biāo)記lk與其它類別標(biāo)記之間的相關(guān)性對(duì)之前生成的基本標(biāo)記特征空間Xk進(jìn)行增強(qiáng).在本方法中將標(biāo)記之間相關(guān)性問(wèn)題轉(zhuǎn)換為最小二乘法優(yōu)化問(wèn)題,通過(guò)引入L1正則化項(xiàng)對(duì)其進(jìn)行優(yōu)化求解從而引入標(biāo)記lk與其它類別標(biāo)記之間的相關(guān)性,優(yōu)化最小二乘法問(wèn)題如下:

根據(jù)之前生成的基本標(biāo)記特征空間 φk中的數(shù)值取值介于0 到1 之間,在此我們將闕值 γ設(shè)定為常數(shù)值0.5.對(duì)于標(biāo)記lk,通過(guò)融合標(biāo)記相關(guān)性信息后對(duì)基本標(biāo)記特征進(jìn)行增強(qiáng),即可生成最終標(biāo)記特定特征ψk:X→Zk,其中ψk(x)表示形式如下:

針對(duì)訓(xùn)練樣本中的每一個(gè)標(biāo)記類別分別構(gòu)造其特定特征空間,在標(biāo)記空間集合中應(yīng)用改進(jìn)后的ML-KNN算法進(jìn)行模型訓(xùn)練,其中在計(jì)算兩個(gè)標(biāo)記之間距離時(shí)MLF-KNN 算法不同于ML-KNN 采用歐式距離直接計(jì)算,而是采用如下r階Minkowski 距離進(jìn)行計(jì)算[16].

其中,xl代表示例x的第l維,||·||表示取該實(shí)數(shù)值的絕對(duì)值.在計(jì)算兩個(gè)樣本之間的距離時(shí)采用Minkowski距離度量方法的主要出發(fā)點(diǎn)是考慮到不同數(shù)據(jù)集內(nèi)數(shù)據(jù)可能具有不同分布從而需要采取不同的距離計(jì)算方法,采用Minkowski 方法可以提高本算法對(duì)不同數(shù)據(jù)集的包容性.當(dāng)階數(shù)取值為1 時(shí),可以轉(zhuǎn)換為曼哈頓距離.當(dāng)階數(shù)取值為2 時(shí),可以轉(zhuǎn)換為歐氏距離.當(dāng)階數(shù)繼續(xù)增大到無(wú)窮大時(shí)可轉(zhuǎn)換為切比雪夫距離.在本實(shí)驗(yàn)中所采用的數(shù)據(jù)集中的數(shù)據(jù)取值規(guī)范,分布較為獨(dú)立,因此設(shè)定r值為2 轉(zhuǎn)換為歐式距離進(jìn)行試驗(yàn).當(dāng)數(shù)據(jù)集中的數(shù)據(jù)分布具有關(guān)聯(lián)性或者局限性時(shí),可以改變r(jià)值的取值以適配不同的數(shù)據(jù)分布.MLF-KNN 算法描述如算法1 所示.

算法1.MLF-KNN 算法步驟1.構(gòu)造基本標(biāo)記特征集.lk Y={l1,l2,···,lq}For in do利用式(4)和式(5)構(gòu)建標(biāo)記正相關(guān)樣本集 和負(fù)相關(guān)樣本集;End for lk Y={l1,l2,···,lq}For in do Pk Nk通過(guò)式(8)構(gòu)建針對(duì) 的標(biāo)記特征映射;lk φk End for

步驟2.增強(qiáng)基本標(biāo)記特征集,構(gòu)建標(biāo)記特征.lk Y={l1,l2,···,lq}For in do通過(guò)對(duì)式(10)進(jìn)行L1-范數(shù)正則化計(jì)算權(quán)重向量;βk通過(guò)式(11),式(12),構(gòu)建最終標(biāo)記特征;End for步驟3.構(gòu)建二分類訓(xùn)練集.lk Y={l1,l2,···,lq}For in do Dk根據(jù)式(13)構(gòu)建標(biāo)記 的二分類訓(xùn)練集;End for步驟4.計(jì)算先驗(yàn)概率.lk Y={l1,l2,···,lq}For in do lk Dk計(jì)算標(biāo)記 的先驗(yàn)概率:P(Hlb)(b∈{0,1},l∈Y)lk;End for步驟5.計(jì)算示例在標(biāo)記特定特征空間中的k 近鄰集合.xki Dk For in do通過(guò)式(14)計(jì)算k 近鄰集合,從而根據(jù)式(1)計(jì)算N(x)Cx(l)End for P(ElCx(l)|Hl1)P(ElCx(l)|Hl0)步驟6.計(jì)算各類標(biāo)記條件概率 和條件概率.步驟7.對(duì)待測(cè)樣例t 進(jìn)行分類,通過(guò)式(8)構(gòu)建新的樣本表達(dá),分別在計(jì)算和,利用式(3)計(jì)算其對(duì)應(yīng)的標(biāo)記向量.tk DkN(t)Ct(l)Yt

3 實(shí)驗(yàn)

為了檢驗(yàn)MLF-KNN 算法的分類效果,將本算法與ML-KNN,LIFT,Rank-SVM 等3 個(gè)多標(biāo)記學(xué)習(xí)算法在公開(kāi)酵母數(shù)據(jù)集yeast 和圖像數(shù)據(jù)集image 上進(jìn)行比較.其中ML-KNN 算法基于傳統(tǒng)k近鄰技術(shù)處理多標(biāo)記問(wèn)題,基于已有樣本的先驗(yàn)概率,通過(guò)在訓(xùn)練樣本中尋找距離最近的k個(gè)實(shí)例從而對(duì)未知示例進(jìn)行標(biāo)記預(yù)測(cè).但是該方法沒(méi)有考慮標(biāo)記之間的關(guān)聯(lián)信息,屬于算法適應(yīng)型一階策略算法.LIFT 算法通過(guò)構(gòu)造每一個(gè)標(biāo)記獨(dú)有的特征信息,基于標(biāo)記獨(dú)有的示例集合進(jìn)行模型訓(xùn)練,是從標(biāo)記特征信息研究的新型算法,但是同樣沒(méi)有引入標(biāo)記之間的相關(guān)信息,也屬于一階策略算法.Rank-SVM 算法使用最大化間隔思想處理多標(biāo)記問(wèn)題,該算法的核心是通過(guò)一組線性分類器對(duì)Ranking Loss 指標(biāo)進(jìn)行優(yōu)化,并通過(guò)引入“核技巧”處理非線性分類問(wèn)題[9],屬于算法適應(yīng)型二階策略算法.實(shí)驗(yàn)所采用的數(shù)據(jù)集yeast 和image 在多標(biāo)記學(xué)習(xí)領(lǐng)域是兩個(gè)公開(kāi)的數(shù)據(jù)集,分別在生物領(lǐng)域和圖像領(lǐng)域具有一定的代表性,兩個(gè)數(shù)據(jù)集詳細(xì)信息如表1所示.

表1 數(shù)據(jù)集詳細(xì)信息

由于每個(gè)示例同時(shí)類屬于多個(gè)標(biāo)記,因此傳統(tǒng)的單標(biāo)記評(píng)價(jià)指標(biāo)例如精度(accuracy)、查準(zhǔn)率(precision)和查全率(recall)等指標(biāo)不再適用.本文評(píng)價(jià)指標(biāo)基于Haming Loss,One-error,Coverage,Ranking Loss,Average Precision[17]等5 種在多標(biāo)記學(xué)習(xí)領(lǐng)域廣泛使用的評(píng)價(jià)指標(biāo).其中,對(duì)于Average Precision 指標(biāo)信息,數(shù)值越大代表分類性能越好,在表中使用 ↑表示,其余評(píng)價(jià)指標(biāo)數(shù)值越小則代表其分類性能越好,在表中使用 ↓表示.表2為各個(gè)算法在數(shù)據(jù)集yeast 上的測(cè)試結(jié)果,表3為在數(shù)據(jù)集image 上的測(cè)試結(jié)果.本文提出的算法基于ML-KNN 改進(jìn)而來(lái),圖1為MLF-KNN 算法與ML-KNN 算法在數(shù)據(jù)集yeast 上的隨k值變化的Coverage 評(píng)價(jià)指標(biāo)對(duì)比結(jié)果圖

表2 本文算法與其它算法在數(shù)據(jù)集yeast 上的實(shí)驗(yàn)結(jié)果對(duì)比

表3 本文算法與其它算法在數(shù)據(jù)集image 上的實(shí)驗(yàn)果對(duì)比

圖1 MLF-KNN 與ML-KNN 算法在數(shù)據(jù)集yeast 數(shù)據(jù)集隨k 值變化的Coverage 變化曲線圖

由圖1可以看出,本文提出的算法相比于ML-KNN算法在Coverage 評(píng)價(jià)指標(biāo)上表現(xiàn)性能十分優(yōu)異,當(dāng)k值繼續(xù)增大時(shí),Coverage 值可以接近最優(yōu)解1.0,代表MLF-KNN 算法對(duì)于測(cè)試樣本的預(yù)測(cè)所有相關(guān)性標(biāo)記的平均查找深度小,分類性能有所提高.由表2和表3的對(duì)比實(shí)驗(yàn)結(jié)果圖可以看出,本文所提出的算法MLFKNN 在數(shù)據(jù)集yeast 當(dāng)中表現(xiàn)優(yōu)異.反映在具體評(píng)價(jià)指標(biāo)上,MLF-KNN 算法在One-error,Ranking Loss 和Average Precision 指標(biāo)上表現(xiàn)不是最優(yōu),雖然Ranking Loss 指標(biāo)上的表現(xiàn)低于LIFT 算法,但是相比ML-KNN算法而言該評(píng)價(jià)指標(biāo)有所提高.在數(shù)據(jù)集image 中,本算法同樣在評(píng)價(jià)指標(biāo)Haming Loss 和Coverage 上表現(xiàn)最優(yōu).實(shí)驗(yàn)結(jié)果表明對(duì)ML-KNN 算法引入標(biāo)記特定特征和標(biāo)記相關(guān)性進(jìn)行改進(jìn)可以進(jìn)一步提高算法分類性能,尤其在Coverage 上表現(xiàn)更為明顯,同時(shí)也證明了從標(biāo)記特定特征對(duì)算法進(jìn)行改進(jìn)創(chuàng)新這一思路的有效性.

4 結(jié)論與展望

ML-KNN 算法在模型訓(xùn)練過(guò)程中沒(méi)有考慮到標(biāo)記之間的相關(guān)性,同時(shí)在預(yù)測(cè)不同標(biāo)記時(shí)基于同一特征空間,忽略了每個(gè)標(biāo)記所特定的標(biāo)記特征.LIFT 算法從利用每個(gè)標(biāo)記所獨(dú)有的特征出發(fā),為多標(biāo)記學(xué)習(xí)研究指明了一個(gè)新的方向.基于此,我們對(duì)ML-KNN 算法進(jìn)行改進(jìn),在構(gòu)造標(biāo)記特征空間的同時(shí)對(duì)其進(jìn)行增強(qiáng),引入與其它標(biāo)記之間的相關(guān)性,提高了算法分類性能.在之后的工作中,可以進(jìn)一步對(duì)構(gòu)建標(biāo)記特征空間的方法進(jìn)行創(chuàng)新,另外本算法并未對(duì)標(biāo)記不平衡的問(wèn)題進(jìn)行考慮,當(dāng)正負(fù)標(biāo)記樣本數(shù)量差異過(guò)大時(shí)會(huì)制約算法的分類性能,所以下一步工作可以將當(dāng)前多標(biāo)記學(xué)習(xí)領(lǐng)域?qū)φ?fù)標(biāo)記不平衡問(wèn)題的研究[18]引入到本算法當(dāng)中.