萬(wàn)潤(rùn)君,郭嗣琮,劉海濤,曾繁慧
(1.遼寧工程技術(shù)大學(xué) 理學(xué)院,遼寧 阜新 123000;2.遼寧工程技術(shù)大學(xué) 智能工程與數(shù)學(xué)研究院,遼寧 阜新 123000)
多標(biāo)記學(xué)習(xí)源于在文檔分類(lèi)任務(wù)中遇到的歧義性問(wèn)題[1-2],不僅是應(yīng)用在結(jié)構(gòu)化的文本數(shù)據(jù)分類(lèi)上[3-4],更多應(yīng)用于現(xiàn)代生活所產(chǎn)生的半結(jié)構(gòu)化和非結(jié)構(gòu)化數(shù)據(jù)分類(lèi)上[5-7],如圖片的語(yǔ)義分類(lèi)、音樂(lè)的情感分類(lèi)、蛋白質(zhì)的功能分類(lèi)等.多標(biāo)記學(xué)習(xí)已經(jīng)成為國(guó)際機(jī)器學(xué)習(xí)領(lǐng)域的重要研究熱點(diǎn)之一[7-8],在現(xiàn)實(shí)生活的應(yīng)用中具有重要的意義.與單標(biāo)記學(xué)習(xí)不同,多標(biāo)記學(xué)習(xí)任務(wù)的一個(gè)實(shí)例通常關(guān)聯(lián)一個(gè)非空標(biāo)記集,豐富的標(biāo)記與特征需要高維的標(biāo)記空間與特征空間來(lái)表征,因此維度災(zāi)難成為多標(biāo)記學(xué)習(xí)的一大挑戰(zhàn)[9].
多標(biāo)記學(xué)習(xí)最基本的任務(wù)是多標(biāo)記分類(lèi)和標(biāo)記排序.目前,對(duì)多標(biāo)記的研究主要集中在以下方面:①尋找更好的算法,對(duì)樣例進(jìn)行準(zhǔn)確的分類(lèi);②對(duì)已分類(lèi)樣例的標(biāo)記集合排序;③對(duì)多標(biāo)記學(xué)習(xí)中高維數(shù)據(jù)的處理.近年來(lái),大量的多標(biāo)記學(xué)習(xí)算法[10-11]被提出,大致分為以下幾類(lèi).①問(wèn)題轉(zhuǎn)換型方法,包括二值相關(guān)(binary relevance,BR)、分類(lèi)器鏈(Classifier Chain,CC)、校準(zhǔn)的標(biāo)記排序(Calibrated Label Ranking,CLR)等. PEREIRA R B[10]等提出經(jīng)典BR算法,將多標(biāo)記學(xué)習(xí)問(wèn)題轉(zhuǎn)化為多個(gè)獨(dú)立的二分類(lèi)問(wèn)題,每個(gè)二分類(lèi)器對(duì)應(yīng)于標(biāo)記空間中的一個(gè)標(biāo)記.READ J[12]等提出多標(biāo)記學(xué)習(xí)的CC算法,將多個(gè)基二分類(lèi)器通過(guò)一個(gè)鏈串聯(lián)起來(lái),考慮標(biāo)記間的相關(guān)性,但與標(biāo)記空間的維數(shù)是非線(xiàn)性關(guān)系.FURNKRANZ J[13]等提出CLR算法,將多標(biāo)記學(xué)習(xí)問(wèn)題轉(zhuǎn)化為標(biāo)記排序問(wèn)題,并在標(biāo)記空間中引入校準(zhǔn)標(biāo)記,用于區(qū)分相關(guān)標(biāo)記和無(wú)關(guān)標(biāo)記,額外的標(biāo)記引入以至復(fù)雜度較高.②算法適應(yīng)型方法,包括預(yù)測(cè)聚類(lèi)樹(shù)(Predictive Clustering Trees,PCT)、基于決策樹(shù)的多標(biāo)記學(xué)習(xí)(ML-C4.5)、基于排序的支持向量機(jī)(Ranking-SVM)、基于BP神經(jīng)網(wǎng)絡(luò)的多標(biāo)記學(xué)習(xí)(BPMLL)、基于KNN的多標(biāo)記學(xué)習(xí)(MLKNN)等. CLARE A[14]等將決策樹(shù)算法C4.5進(jìn)行了改進(jìn),更改了熵的計(jì)算公式,定義了多標(biāo)記熵的概念,建立ML-C4.5學(xué)習(xí)算法,使其能夠處理多標(biāo)記數(shù)據(jù). ANDRé E[15]等提出Ranking-SVM算法,定義了最大化多標(biāo)記間隔和Ranking loss代價(jià)函數(shù)來(lái)處理多標(biāo)記數(shù)據(jù).ZHANG M L[16]等基于BP神經(jīng)網(wǎng)絡(luò)算法,提出多標(biāo)記學(xué)習(xí)算法BPMLL,通過(guò)標(biāo)記排序來(lái)確定最終的標(biāo)記集合;還提出多標(biāo)記學(xué)習(xí)算法MLkNN(懶惰學(xué)習(xí)方法),對(duì)于一個(gè)未知的實(shí)例,首先查找出其k近鄰樣本集,然后求出其統(tǒng)計(jì)信息,并采用最大后驗(yàn)概率(Maximum A Posterior,MAP)原理來(lái)判斷未知樣本的標(biāo)記集合.③集成算法型方法,包括隨機(jī)k標(biāo)記集(RAndomk-labELsets ,RAKEL)、集成分類(lèi)器鏈(Ensembles of classifier chains,ECC)等.TSOUMAKAS G[17]等提出基于標(biāo)記冪集(Label Powerset,LP)的多標(biāo)記學(xué)習(xí)算法RAKEL,它隨機(jī)選取標(biāo)記空間中不同子集,來(lái)構(gòu)造一個(gè)LP基分類(lèi)器,然后利用集成學(xué)習(xí)將多個(gè)LP基分類(lèi)器的結(jié)果進(jìn)行集成,以此來(lái)處理多標(biāo)記學(xué)習(xí)的問(wèn)題.劉軍煜[18]等通過(guò)挖掘標(biāo)記間的關(guān)聯(lián)性,基于關(guān)聯(lián)規(guī)則挖掘方法提出多標(biāo)記分類(lèi)算法.
這些算法已成功地應(yīng)用于各個(gè)研究領(lǐng)域,但多標(biāo)記學(xué)習(xí)中的高維數(shù)據(jù)問(wèn)題和標(biāo)記間相關(guān)性的問(wèn)題,依然有待研究.為此,提出一種層次樹(shù)結(jié)構(gòu)來(lái)解決高維數(shù)據(jù)計(jì)算復(fù)雜度高的問(wèn)題,采用聚類(lèi)的方式來(lái)解決標(biāo)記間相關(guān)性的問(wèn)題,提高多標(biāo)記分類(lèi)的效果和效率.
多標(biāo)記學(xué)習(xí)任務(wù)的數(shù)學(xué)描述[8]如下.
設(shè)X={x1,x2,… ,xm}為m個(gè)實(shí)例的集合,其中每個(gè)實(shí)例均含有d個(gè)特征屬性,故每個(gè)實(shí)例可記為d維屬性向量xi=(xi1,… ,xid),i=1,2,… ,m.又Y={y1,… ,yq}為標(biāo)記集合.給定訓(xùn)練數(shù)據(jù)集,其中xi∈X,Y上的子集合Yi?Y為對(duì)應(yīng)于xi的標(biāo)記向量. 2Y為Y的所有子集構(gòu)成的集合族,多標(biāo)記學(xué)習(xí)的任務(wù)是通過(guò)訓(xùn)練集合D,建立多標(biāo)記分類(lèi)器h:X→ 2Y,使對(duì)于任意給定測(cè)試實(shí)例的屬性向量xj?D,通過(guò)分類(lèi)器h可以預(yù)測(cè)該實(shí)例的標(biāo)記集h(xj) ∈ 2Y.
為建立多標(biāo)記分類(lèi)器h,多標(biāo)記學(xué)習(xí)系統(tǒng)對(duì)應(yīng)于某個(gè)實(shí)值函數(shù)f:X×2Y→R,f(xi,Yi)被看作是實(shí)例xi的“置信度”,f(xi,Yi)越大,表示xi具有標(biāo)記Yi的可能性越大.對(duì)于一個(gè)給定的實(shí)例xi及其對(duì)應(yīng)的標(biāo)記集Yi,學(xué)習(xí)目標(biāo)是在屬于Yi的有關(guān)標(biāo)記y上輸出一個(gè)較高的置信度,而在不屬于Y的無(wú)關(guān)標(biāo)記上輸出一個(gè)較低的置信度,即對(duì)于與,滿(mǎn)足.因此,由此實(shí)值函數(shù) (,)fxy可以得到分類(lèi)器h為
式中,(tx)為閾值函數(shù),用于區(qū)分標(biāo)記空間為相關(guān)標(biāo)記集和無(wú)關(guān)標(biāo)記集.在實(shí)際應(yīng)用中,通??梢栽O(shè)置為常值函數(shù).
對(duì)于多標(biāo)記學(xué)習(xí)數(shù)據(jù)
其高維性主要體現(xiàn)在實(shí)例個(gè)數(shù)m、屬性維度d和標(biāo)記空間維度q等足夠大.
針對(duì)標(biāo)記空間的高維性,提出一種層次樹(shù)結(jié)構(gòu)模型(ML-HTM).其主要思想是采取分而治之的策略,將具有大量的復(fù)雜多標(biāo)記通過(guò)分類(lèi)轉(zhuǎn)化為更簡(jiǎn)單的樹(shù)狀層次結(jié)構(gòu)的多標(biāo)記分類(lèi),每個(gè)分類(lèi)器只需要完成少量的標(biāo)記分類(lèi)任務(wù),所處理的標(biāo)記個(gè)數(shù)要遠(yuǎn)小于標(biāo)記空間維度,這很大程度地提高了預(yù)測(cè)性能,降低了計(jì)算復(fù)雜度.多標(biāo)記層次樹(shù)結(jié)構(gòu)見(jiàn)圖1.
圖1 多標(biāo)記學(xué)習(xí)層次樹(shù)結(jié)構(gòu) Fig.1 hierarchical tree structure of Multi-label learning
多標(biāo)記學(xué)習(xí)層次樹(shù)由標(biāo)記結(jié)點(diǎn)(用圓圈表示)和分類(lèi)器結(jié)點(diǎn)(用方框表示)通過(guò)樹(shù)狀連接構(gòu)成,其中,根結(jié)點(diǎn)和底層結(jié)點(diǎn)都屬于標(biāo)記結(jié)點(diǎn).每個(gè)標(biāo)記結(jié)點(diǎn)都是由標(biāo)記集Y的子集構(gòu)成.標(biāo)記根結(jié)點(diǎn)由Y構(gòu)成,第2層標(biāo)記結(jié)點(diǎn)為Y1,Y2,…,Yk,是標(biāo)記集的一個(gè)劃分,即
第3層標(biāo)記結(jié)點(diǎn)分別為子集合Y1,Y2,…,Yk(第2層結(jié)點(diǎn))的劃分;類(lèi)似的,第i層結(jié)點(diǎn)為與之相連接的第i-1層結(jié)點(diǎn)的1個(gè)劃分.樹(shù)的底層葉子結(jié)點(diǎn)共有q個(gè),每個(gè)結(jié)點(diǎn)為標(biāo)記集Y的1個(gè)元素,即
定義結(jié)點(diǎn)n的組合標(biāo)記當(dāng)訓(xùn)練樣本的標(biāo)記集Ln中至少含有一個(gè)標(biāo)記時(shí),則使用組合標(biāo)記un對(duì)該訓(xùn)練樣本進(jìn)行注釋.
分類(lèi)器結(jié)點(diǎn)h存在于任意非葉標(biāo)記結(jié)點(diǎn)與其子結(jié)點(diǎn)之間,具有n+1層標(biāo)記結(jié)點(diǎn)的層次樹(shù)含有n層分類(lèi)器結(jié)點(diǎn).分類(lèi)器結(jié)點(diǎn)依據(jù)劃分的結(jié)果,建立從標(biāo)記結(jié)點(diǎn)屬性到子標(biāo)記結(jié)點(diǎn)的映射.其任務(wù)則是預(yù)測(cè)子標(biāo)記結(jié)點(diǎn)的組合標(biāo)記.因此,hn的標(biāo)記集合為
圖1顯示了一個(gè)具有q個(gè)標(biāo)記的ML-HTM模型.通過(guò)訓(xùn)練數(shù)據(jù)即可建立該模型,流程見(jiàn)圖2.
圖2 ML-HTM模型構(gòu)建流程 Fig.2 flow chart for building ML-HTM model
(1)建立層次樹(shù)
假設(shè)存在訓(xùn)練樣本集
每個(gè)訓(xùn)練樣本均包含一個(gè)屬性向量xi和標(biāo)記集Yi,Yi?Y.模型從根結(jié)點(diǎn)開(kāi)始,自頂向下的深度優(yōu)先方式遞歸創(chuàng)建此層次樹(shù).從根結(jié)點(diǎn)開(kāi)始,根結(jié)點(diǎn)使用整個(gè)訓(xùn)練樣本集Droot=D;在每個(gè)結(jié)點(diǎn)n處,首先創(chuàng)建k個(gè)子結(jié)點(diǎn),若|Ln|<k,則創(chuàng)建|Ln|個(gè)子結(jié)點(diǎn);將當(dāng)前結(jié)點(diǎn)中的標(biāo)記集通過(guò)聚類(lèi)算法將相關(guān)性高的標(biāo)記聚到相同的分支中,相關(guān)性低的標(biāo)記聚到不同的分支中,并將聚類(lèi)結(jié)果作為當(dāng)前結(jié)點(diǎn)的各子結(jié)點(diǎn)的標(biāo)記集;遞歸執(zhí)行該過(guò)程,直至某個(gè)分支中標(biāo)記個(gè)數(shù)僅有1個(gè),即該分支已建立到葉子結(jié)點(diǎn),便可結(jié)束該分支的遞歸任務(wù);當(dāng)所有分支的遞歸任務(wù)均已結(jié)束,便建立起了該多標(biāo)記層次樹(shù).
聚類(lèi)操作是層次樹(shù)建立的核心,聚類(lèi)效果和效率直接影響多標(biāo)記學(xué)習(xí)結(jié)果.ML-HTM模型使用文獻(xiàn)[19]提出的一種快速密度聚類(lèi)算法,該算法尋找局部密度峰值點(diǎn)作為聚類(lèi)中心,用密度和距離同時(shí)作為聚類(lèi)依據(jù),從而實(shí)現(xiàn)對(duì)樣本數(shù)據(jù)的快速聚類(lèi).其核心思想是:聚類(lèi)中心被局部密度較低的數(shù)據(jù)點(diǎn)包圍,且遠(yuǎn)離其他密度值較大的點(diǎn).在聚類(lèi)過(guò)程中,對(duì)于任一數(shù)據(jù)點(diǎn)i,計(jì)算出它的局部密度值ρi和它到較大密度點(diǎn)的最小距離δi.而以上兩個(gè)量?jī)H取決于數(shù)據(jù)點(diǎn)之間的距離dij,因此計(jì)算過(guò)程中只需計(jì)算一次兩兩樣本點(diǎn)之間的距離.
數(shù)據(jù)點(diǎn)i的局部密度值為
式中,當(dāng)x< 0時(shí),χ(x)=1;當(dāng)x≥ 0時(shí),dc為截?cái)嗑嚯x,需要提前指定一個(gè)常值.
數(shù)據(jù)點(diǎn)i到較大密度點(diǎn)的最小距離為
式中,dij為數(shù)據(jù)點(diǎn)i與數(shù)據(jù)點(diǎn)j之間的距離,數(shù)據(jù)點(diǎn)j滿(mǎn)足ρj>ρi.
由快速密度聚類(lèi)算法思想可以看出,該算法在聚類(lèi)過(guò)程中會(huì)形成聚類(lèi)不平衡情況,即存在聚類(lèi)結(jié)果的各類(lèi)中數(shù)據(jù)點(diǎn)個(gè)數(shù)差別較大,導(dǎo)致標(biāo)記分配不均,進(jìn)而使得層次樹(shù)的構(gòu)建復(fù)雜度較高,影響多標(biāo)記學(xué)習(xí)效率.為此,提出改進(jìn)的快速密度聚類(lèi)算法,應(yīng)用一種軟均衡策略,解決聚類(lèi)不平衡問(wèn)題.其與強(qiáng)制平衡策略(聚類(lèi)過(guò)程中嚴(yán)格要求各類(lèi)中數(shù)據(jù)點(diǎn)個(gè)數(shù)相同)不同,體現(xiàn)在執(zhí)行分配過(guò)程中,即使在某個(gè)類(lèi)已達(dá)到最大容量使得不平衡情況出現(xiàn),也不會(huì)將某數(shù)據(jù)點(diǎn)分配到其他局部密度比自己小的中心點(diǎn)所屬類(lèi)中.軟均衡策略分為如下步驟:①計(jì)算出平衡策略下各類(lèi)中的元素最大個(gè)數(shù);②在非中心點(diǎn)分配時(shí),先判斷鄰居所屬類(lèi)別是否已達(dá)到最大容量.若是,將該點(diǎn)與鄰居之間的距離修改為∞,并重新尋找距離最小且局部密度大于自身的鄰居,若不存在另外滿(mǎn)足條件的鄰居,則依舊更改為最初的鄰居;若不是,則令其鄰居不變;③將該點(diǎn)分配給上一步中確定的鄰居所在類(lèi).
(2)構(gòu)建分類(lèi)器
在建立起的層次樹(shù)基礎(chǔ)上,從根結(jié)點(diǎn)至葉子結(jié)點(diǎn),通過(guò)SVM學(xué)習(xí)算法訓(xùn)練結(jié)點(diǎn)i處的屬性向量和標(biāo)記集數(shù)據(jù)(xi,Yi),得到樹(shù)中每個(gè)分支處的多標(biāo)記分類(lèi)器hi.hi用于預(yù)測(cè)未知實(shí)例在該結(jié)點(diǎn)處子節(jié)點(diǎn)的組合標(biāo)記un,從而得到最終的標(biāo)記集.
通過(guò)以上過(guò)程,可建立基于訓(xùn)練數(shù)據(jù)集的多標(biāo)記學(xué)習(xí)層次樹(shù).未知實(shí)例的標(biāo)記預(yù)測(cè)過(guò)程為(流程見(jiàn)圖3):對(duì)于給定一個(gè)未知實(shí)例x',層次樹(shù)模型從根結(jié)點(diǎn)開(kāi)始,并遵循如下遞歸過(guò)程,在結(jié)點(diǎn)c處,當(dāng)且僅當(dāng)組合標(biāo)記uc在其父結(jié)點(diǎn)的預(yù)測(cè)中時(shí),才將實(shí)例x'轉(zhuǎn)發(fā)給結(jié)點(diǎn)c的多標(biāo)記分類(lèi)器hc.最終,該過(guò)程由多標(biāo)記分類(lèi)器hc預(yù)測(cè)進(jìn)行至一個(gè)或多個(gè)單標(biāo)記的葉子結(jié)點(diǎn)yi,這些預(yù)測(cè)出的葉子結(jié)點(diǎn)所包含單標(biāo)記的并集Y'= ∪yi,即為該未知實(shí)例x'的預(yù)測(cè)標(biāo)記.
圖3 ML-HTM模型標(biāo)記預(yù)測(cè)流程 Fig.3 flow chart for predicting label by ML-HTM model
選6個(gè)被廣泛用于多標(biāo)記學(xué)習(xí)的高維數(shù)據(jù)集[11],分別體現(xiàn)在示例空間維度高、屬性空間維度高和標(biāo)記空間維度高.數(shù)據(jù)集詳細(xì)信息見(jiàn)表1.
表1 實(shí)驗(yàn)數(shù)據(jù)集信息 Tab.1 experiment dataset Information
多標(biāo)記學(xué)習(xí)的性能評(píng)價(jià)有別于傳統(tǒng)的單標(biāo)記學(xué)習(xí)評(píng)價(jià)體系.本文中所包含的所有多標(biāo)記學(xué)習(xí)實(shí)驗(yàn),采用文獻(xiàn)[20]提出的評(píng)價(jià)指標(biāo)體系,從中選取如下適于多標(biāo)記分類(lèi)任務(wù)的評(píng)價(jià)指標(biāo),即基于實(shí)例的評(píng)價(jià)指標(biāo)和基于標(biāo)記的評(píng)價(jià)指標(biāo).各評(píng)價(jià)指標(biāo)及分類(lèi)見(jiàn)圖4.
圖4 多標(biāo)記分類(lèi)任務(wù)評(píng)價(jià)指標(biāo) Fig.4 evaluation measures for multi-label classification task
以上各個(gè)評(píng)價(jià)指標(biāo)都是從不同的側(cè)面來(lái)衡量建立的學(xué)習(xí)模型的泛化能力,作為模型評(píng)價(jià)的參考指標(biāo).
使用6種常見(jiàn)的經(jīng)典多標(biāo)記學(xué)習(xí)方法(BR、CC、ML-C4.5、PCT、RAkEL、MLkNN)和本文建立的ML-HTM模型,基分類(lèi)器均選擇支持向量機(jī)(Support Vector Machine,SVM),在6個(gè)數(shù)據(jù)集下進(jìn)行多標(biāo)記學(xué)習(xí)實(shí)驗(yàn),并通過(guò)測(cè)試數(shù)據(jù)對(duì)模型效果進(jìn)行評(píng)估,得到12個(gè)不同評(píng)價(jià)指標(biāo)值.將各個(gè)數(shù)據(jù)集按實(shí)例空間維度高、屬性空間維度高和標(biāo)記空間維度高的顯著特性繪制每個(gè)學(xué)習(xí)算法的評(píng)價(jià)指標(biāo)值折線(xiàn)圖,以便檢驗(yàn)提出的多標(biāo)記學(xué)習(xí)算法在高維數(shù)據(jù)集下的多標(biāo)記學(xué)習(xí)效果,見(jiàn)圖5.圖5中,所有評(píng)價(jià)指標(biāo)值均已進(jìn)行歸一化,歸一化后的指標(biāo)值均以大為優(yōu).
圖5 各算法在6個(gè)數(shù)據(jù)集上的性能 Fig.5 performance for MLL algorithms on six datasets
對(duì)于漢明損失指標(biāo),歸一化公式為
對(duì)于其他指標(biāo),歸一化公式為
由評(píng)價(jià)指標(biāo)折線(xiàn)圖可以發(fā)現(xiàn),ML-HTM算法學(xué)習(xí)效果在12個(gè)評(píng)價(jià)指標(biāo)上明顯優(yōu)于經(jīng)典的多標(biāo)記學(xué)習(xí)算法,整體上在不同數(shù)據(jù)集和不同評(píng)價(jià)指標(biāo)上表現(xiàn)較好,在高維數(shù)據(jù)集上提高了模型學(xué)習(xí)的準(zhǔn)確率和學(xué)習(xí)效率.
(1)提出一種適于高維數(shù)據(jù)的多標(biāo)記學(xué)習(xí)方法ML-HTM,從標(biāo)記間的相關(guān)性出發(fā),構(gòu)建多標(biāo)記學(xué)習(xí)框架,將其應(yīng)用到文本和多媒體不同領(lǐng)域下的6個(gè)數(shù)據(jù)集中.
(2)實(shí)驗(yàn)結(jié)果表明:ML-HTM模型解決了多標(biāo)記學(xué)習(xí)數(shù)據(jù)集標(biāo)記空間維度大造成的學(xué)習(xí)困難;充分考慮了標(biāo)記間的相關(guān)性,降低學(xué)習(xí)過(guò)程計(jì)算復(fù)雜度;優(yōu)于多種現(xiàn)有的多標(biāo)記學(xué)習(xí)方法,明顯提高了學(xué)習(xí)效率和預(yù)測(cè)能力,更加準(zhǔn)確地對(duì)標(biāo)記進(jìn)行預(yù)測(cè).后續(xù)將繼續(xù)對(duì)層次結(jié)構(gòu)進(jìn)行優(yōu)化,進(jìn)一步提升模型的學(xué)習(xí)性能.