結(jié)合類屬特征及因果發(fā)現(xiàn)的序列優(yōu)化分類器鏈

羅森林， 王海州， 潘麗敏

(北京理工大學(xué) 信息與電子學(xué)院，北京 100081)

在圖像標(biāo)注[1-2]、文本分類[3-4]等應(yīng)用場(chǎng)景中一個(gè)樣本可以同時(shí)屬于多個(gè)類. 比如在圖像標(biāo)注應(yīng)用中，一個(gè)圖像可能同時(shí)被標(biāo)注為“海洋”和“船”；在文本分類應(yīng)用中，一段文本可能同時(shí)包含“演唱會(huì)”和“門票”等多個(gè)主題. 這種數(shù)據(jù)被稱為多標(biāo)簽數(shù)據(jù)，針對(duì)多標(biāo)簽數(shù)據(jù)的分類被稱為多標(biāo)簽分類. 在多標(biāo)簽分類問題中，標(biāo)簽之間存在關(guān)聯(lián). 比如標(biāo)記為“沙漠”的圖片很可能被標(biāo)記為“駱駝”，幾乎不可能被標(biāo)記為“雨林”. 挖掘利用標(biāo)簽間的關(guān)聯(lián)關(guān)系能夠有效地提升多標(biāo)簽分類效果[5-6].

基于上述分析，針對(duì)分類器鏈中各標(biāo)簽的基學(xué)習(xí)器均在完整特征空間中訓(xùn)練導(dǎo)致學(xué)習(xí)特征冗余，以及因標(biāo)簽學(xué)習(xí)順序隨機(jī)且分類器鏈訓(xùn)練過程單向無反饋導(dǎo)致的標(biāo)簽間相關(guān)信息利用不充分等問題，提出一種結(jié)合類屬特征及因果發(fā)現(xiàn)的序列優(yōu)化分類器鏈(sequence optimization classifier chain based on label-specific features and causal discovery, SOCC). 使用仿射傳播聚類構(gòu)建類屬特征，并將類屬特征引入分類器鏈；使用條件熵挖掘標(biāo)簽間因果關(guān)系以優(yōu)化分類器鏈的標(biāo)簽順序；在多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明有良好的分類能力.

1 相關(guān)工作

多標(biāo)簽數(shù)據(jù)通常具有高維度特征，這些特征并不是與每一個(gè)標(biāo)簽都相關(guān). 每個(gè)標(biāo)簽都有對(duì)應(yīng)的類屬特征. 使用類屬特征進(jìn)行分類能夠減少特征空間的冗余信息. 現(xiàn)有類屬特征構(gòu)造方法主要包括基于特征選擇的方法和基于特征變換的方法. 基于特征選擇的方法，其原理是從特征中選出每個(gè)標(biāo)簽的特征子集. 比如HUANG等[7]提出的LLSF方法，基于兩個(gè)強(qiáng)相關(guān)標(biāo)簽比兩個(gè)弱相關(guān)或不相關(guān)標(biāo)簽共享更多特征的假設(shè)，采用線性回歸的方法得到每個(gè)標(biāo)簽的特征權(quán)重，確定每個(gè)標(biāo)簽的特征. HAN等[8]提出的LSF-CI方法，利用概率鄰域圖計(jì)算樣本關(guān)聯(lián)，利用余弦相似度計(jì)算標(biāo)簽相關(guān)性. 然后利用樣本關(guān)聯(lián)和標(biāo)簽關(guān)聯(lián)對(duì)特征進(jìn)行誘導(dǎo)，以選擇更健壯的特征. 基于特征變換的方法，其原理是對(duì)原始特征進(jìn)行變換，以得到標(biāo)簽的類屬特征. 比如ZHANG等[9]提出LIFT方法，對(duì)于每個(gè)標(biāo)簽，考慮樣本之間的關(guān)聯(lián)，通過K-means聚類獲得其正、負(fù)樣本的中心. 然后，根據(jù)樣本到聚類中心的歐氏距離對(duì)特征進(jìn)行變換. ZHANG等[10]提出ML-DFL方法，該方法針對(duì)LIFT方法沒有利用正負(fù)樣本之間判別信息的問題，使用聚類方法利用正負(fù)樣本之間的局部結(jié)構(gòu)，通過查詢聚類結(jié)果將原始特征轉(zhuǎn)換為用于判別過程的特征. WENG等[11]提出LF-LPLC方法，為在LIFT的基礎(chǔ)上利用標(biāo)簽相關(guān)性，在聚類前設(shè)置每個(gè)標(biāo)簽的聚類簇?cái)?shù)相同. 完成特征構(gòu)建后通過樣本嵌入實(shí)現(xiàn)局部相關(guān)性的利用.

現(xiàn)有標(biāo)簽相關(guān)性利用的方法主要包括二階方法和高階方法. 二階方法只考慮標(biāo)簽之間的成對(duì)相關(guān)性，不能反映更復(fù)雜的相關(guān)性，比如Rank-LSVM[12]和CML-kNN[13]等；高階方法挖掘所有標(biāo)簽之間的相關(guān)性來解決多標(biāo)簽分類問題. READ等[14]提出的CC是重要的高階方法之一，利用標(biāo)簽向量作為附加特征，按照隨機(jī)順序訓(xùn)練得到一個(gè)鏈?zhǔn)降亩鄻?biāo)簽分類器. READ等[15]提出ECC方法，為緩解標(biāo)簽順序隨機(jī)對(duì)分類器鏈的不良影響，按照CC的方式生成多個(gè)分類器鏈，再利用集成方法整合所有分類器鏈的結(jié)果以獲得最終分類. CHENG等[16]提出PCC方法，在訓(xùn)練階段同樣使用隨機(jī)順序. 對(duì)于測(cè)試階段的每個(gè)樣本，估計(jì)所有可能的標(biāo)簽組合的聯(lián)合分布，并尋求最大化標(biāo)簽組合的后驗(yàn)概率. SILVA等[17]提出OOCC方法，按隨機(jī)順序建立若干分類器鏈，對(duì)于測(cè)試樣本，在訓(xùn)練集中找到它的K近鄰，并尋找在這些近鄰樣本中性能最佳的分類器鏈. 然后，將這個(gè)分類器鏈用于該測(cè)試樣本的分類.

綜上所述，現(xiàn)有分類器鏈方法的改進(jìn)主要是減輕標(biāo)簽順序隨機(jī)對(duì)分類結(jié)果的不良影響，而不是通過優(yōu)化學(xué)習(xí)順序來提高分類效果；同時(shí)沒有為基分類器構(gòu)建類屬特征，造成基分類器特征冗余. 針對(duì)以上問題，提出結(jié)合類屬特征及因果發(fā)現(xiàn)的序列優(yōu)化分類器鏈.

2 算法原理

2.1 原理框架

針對(duì)分類器鏈方法訓(xùn)練過程使用全部特征導(dǎo)致基分類器特征冗余的問題，通過仿射傳播聚類為基分類器構(gòu)建類屬特征，對(duì)劃分后的正負(fù)類樣本，經(jīng)過樣本間的消息傳遞確定聚類中心，根據(jù)樣本到聚類中心的距離實(shí)現(xiàn)特征構(gòu)建；針對(duì)分類器鏈對(duì)標(biāo)簽間相關(guān)信息利用不充分的問題，利用條件熵挖掘標(biāo)簽間因果關(guān)系，確定標(biāo)簽順序，并使用分類器鏈按順序進(jìn)行分類. SOCC方法的原理如圖1所示.

圖1 SOCC原理圖Fig.1 SOCC algorithm principle diagram

2.2 類屬特征構(gòu)建

在多標(biāo)簽分類問題中，使用D={(xi,yi)|1≤i≤N,xi∈X,yi?Y}代表由N個(gè)樣本組成的訓(xùn)練集，其中(xi,yi)表示一個(gè)樣本；xi為一個(gè)d維的向量，每一個(gè)元素代表一個(gè)特征；yi為一個(gè)Q維的向量，每一個(gè)元素代表一個(gè)標(biāo)簽，如果第i個(gè)樣本屬于標(biāo)簽lj，那么yij=+1，否則yij=-1.

針對(duì)標(biāo)簽lk，將訓(xùn)練集劃分成正類Pk和負(fù)類Nk，

Pk={xi|(xi,yi)∈D,yik=+1}

(1)

Nk={xi|(xi,yi)∈D,yik=-1}

(2)

(3)

式中d(·,·)代表的是兩者間的歐氏距離. 這一過程與LIFT算法中的類屬特征構(gòu)建相似，但是LIFT算法使用的是K-means聚類方法，K-means聚類本身是不穩(wěn)定的，聚類結(jié)果受初始值和噪聲影響大，并且K-means聚類需要人為地指定聚類簇個(gè)數(shù)，這會(huì)導(dǎo)致聚類中心發(fā)生偏移，影響類屬特征的穩(wěn)定. 為了解決這一問題，SOCC采用仿射傳播聚類替代K-means聚類. 仿射傳播聚類能在沒有任何先驗(yàn)知識(shí)的情況下自動(dòng)確定聚類簇個(gè)數(shù)，并且仿射傳播聚類結(jié)果對(duì)初始值和噪聲不敏感，彌補(bǔ)K-means聚類的缺陷.

2.3 標(biāo)簽順序獲取

分類器鏈可以看作是一種有向無環(huán)圖(DAG)，每個(gè)基分類器作為DAG中的一個(gè)節(jié)點(diǎn)[19]. 在DAG中，使用條件熵對(duì)標(biāo)簽間的因果關(guān)系進(jìn)行挖掘以確定標(biāo)簽順序.

H(Y1|Y2)=H(Y1)-I(Y1,Y2)

(4)

式中Y1、Y2分別代表訓(xùn)練集中l(wèi)1、l2的取值向量，H(·)代表熵;I(·,·)代表互信息. 使用H(Y1|Y2)來衡量l1對(duì)l2的因果關(guān)系. 若H(Y1|Y2)為0，表示在已知l2的情況下l1能被完美的預(yù)測(cè).H(Y1|Y2)越小，l2能為l1提供越多的信息，即l2和l1的因果關(guān)系越強(qiáng). 依據(jù)這種關(guān)系來確定標(biāo)簽的訓(xùn)練順序. 首先分別計(jì)算標(biāo)簽兩兩之間的條件熵，得到一個(gè)Q×Q的矩陣. 計(jì)算矩陣每一行的和，選擇值最小的那一行，記錄該行對(duì)應(yīng)的標(biāo)簽i，并刪除第i行以及第i列，剩下一個(gè)(Q-1)×(Q-1)的矩陣. 重復(fù)這個(gè)過程，直到所有標(biāo)簽都被記錄為止. 標(biāo)簽順序獲取偽代碼如下.

輸入：Y={Yi,i=1,2,…,Q}

輸出：Order

1.計(jì)算條件熵H(Yi|Yj),i,j∈[1,Q]

2.初始化剩余的標(biāo)簽集合L={1,2,…,Q}

3.初始化標(biāo)簽順序Order={}

4. While |L|>0

5.對(duì)于L中的每一項(xiàng)計(jì)算sumH(i)=∑j∈L,j≠iH(Yj|Yi)

7.將i*加入Order中，并從L中刪除i*

8. end

9. returnOrder

2.4 分類器鏈構(gòu)建

SOCC選擇SVM作為分類器鏈的基分類器，將經(jīng)過仿射傳播聚類構(gòu)建的類屬特征作為輸入，按照依據(jù)條件熵獲取的標(biāo)簽順序構(gòu)建分類器鏈CC={cci,i=1,2,…,|Q|}. 值得注意的是，在之前的分類器鏈方法中靠后的分類器的輸入特征是由樣本特征與前面所有分類器的輸出組成的，這在各標(biāo)簽獨(dú)立的假設(shè)上有詳細(xì)地理論推導(dǎo). 但是標(biāo)簽之間的相關(guān)性導(dǎo)致各標(biāo)簽不滿足獨(dú)立的假設(shè)，使用樣本特征與前面所有的分類器的輸出組成輸入特征的方式會(huì)導(dǎo)致特征冗余. 所以使用余弦相關(guān)性對(duì)前面的分類器的輸出進(jìn)行篩選，將余弦相關(guān)性低于閾值t的從輸入特征中剔除. 分類器鏈構(gòu)建的偽代碼如下.

輸入：D={(φk(xi),yi)|1≤i≤N,xi∈X,yi?Y}，Order

輸出：CC

1.CC={}

2. forj∈Orderdo

3.D′j={}

4.y′={y1,y2,…yj-1}

5. forn∈[1,j-1] do

7.y′=y′-yn

8. end

9. end

10. for (φk(xi),yi)∈Ddo

13. end

14.訓(xùn)練模型ccj

15.CC=CC∪ccj

16. end

17. ReturnCC

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

3.1 實(shí)驗(yàn)?zāi)康?/h3>

為了驗(yàn)證SOCC算法在多標(biāo)簽分類問題上的分類效果，在5個(gè)有代表性的數(shù)據(jù)集上將SOCC算法與對(duì)比算法進(jìn)行比較.

3.2 實(shí)驗(yàn)數(shù)據(jù)

數(shù)據(jù)集的詳細(xì)信息如表 1所示，其中，|D|、dim(D)和L(D)分別代表樣本數(shù)量、特征數(shù)量和標(biāo)簽數(shù)量.

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

3.3 對(duì)比算法

實(shí)驗(yàn)采用10次十折交叉方法，將SOCC同4種多標(biāo)簽分類方法進(jìn)行比較，包括ECC[15](2011)、LIFT[9](2015)、LF-LPLC[11](2018)以及MLFE[20](2018)方法. 其中ECC、MLFE和LF-LPLC利用了標(biāo)簽相關(guān)性，LIFT、LF-LPLC利用了類屬特征. SOCC同其他算法的對(duì)比如表2所示.

表2 Image數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

ECC方法通過集成學(xué)習(xí)與分類器鏈結(jié)合的策略進(jìn)行多標(biāo)簽分類，其中分類器鏈數(shù)量L設(shè)置為10. MLFE方法使用基于稀疏重構(gòu)的特征空間結(jié)構(gòu)豐富標(biāo)簽信息，其調(diào)和參數(shù)設(shè)置為β1={1,2,…,10}，β2={1,10,15}，β3={1,10}. LIFT方法將原始特征轉(zhuǎn)換為類屬特征以提升多標(biāo)簽分類效果，控制聚類簇?cái)?shù)的參數(shù)r設(shè)為0.1. LF-LPLC方法在LIFT的基礎(chǔ)上加入局部的標(biāo)簽相關(guān)性，其中近鄰樣本數(shù)k設(shè)為10. 另外，將SOCC、LF-LPLC、LIFT和ECC算法使用的SVM的核函數(shù)設(shè)置為L(zhǎng)inear核.

3.4 評(píng)價(jià)指標(biāo)

為評(píng)價(jià)SOCC以及對(duì)比算法的性能，選擇5個(gè)廣泛應(yīng)用于多標(biāo)簽學(xué)習(xí)的評(píng)價(jià)指標(biāo)[21]：漢明損失(Hamming loss)、排序損失(ranking loss)、1-錯(cuò)誤率(one-error)、覆蓋率(coverage)和平均精度(average precision).

漢明損失表示所有分類錯(cuò)誤的標(biāo)簽占總標(biāo)簽數(shù)的比例，其定義為

(5)

式中:Δ表示對(duì)稱差運(yùn)算;h(xi)表示模型對(duì)xi標(biāo)簽的預(yù)測(cè).

排序損失表示的是相關(guān)標(biāo)簽與無關(guān)標(biāo)簽對(duì)排序錯(cuò)誤的比例，其定義為

(6)

1-錯(cuò)誤率計(jì)算模型預(yù)測(cè)樣本最可能的標(biāo)簽與真實(shí)標(biāo)簽不符的個(gè)數(shù)，其定義為

(7)

覆蓋率評(píng)估平均要在預(yù)測(cè)的標(biāo)簽序列中搜索多少標(biāo)簽才能夠覆蓋該樣本所有真正屬于的標(biāo)簽，其定義為

(8)

式中Trank代表排序操作，如果xi屬于標(biāo)簽lk的概率越大，其排名越靠前，Trank(xi,lk)值越小.

平均精度評(píng)估在一個(gè)給定標(biāo)簽，有多少實(shí)際包含標(biāo)簽的Trank在其之前，即預(yù)測(cè)標(biāo)簽的平均精度，其定義為

(9)

除平均精度的值越大越好外，其余4個(gè)指標(biāo)的值越小越好.

3.5 實(shí)驗(yàn)結(jié)果

SOCC與對(duì)比算法在5個(gè)數(shù)據(jù)集上的性能評(píng)價(jià)結(jié)果如表2～表6所示，其中，Rank表示算法在各個(gè)評(píng)價(jià)指標(biāo)上的平均排名，以此反應(yīng)算法的綜合性能. 從結(jié)果中可以看出，在image、scene和emotions數(shù)據(jù)集上，SOCC在漢明損失、排序損失、1-錯(cuò)誤率、覆蓋率和平均精度5個(gè)指標(biāo)上均優(yōu)于對(duì)比算法；而針對(duì)CAL500數(shù)據(jù)集，其標(biāo)簽相關(guān)性信息相較特征信息更為豐富，因此SOCC在1-錯(cuò)誤率指標(biāo)的表現(xiàn)略弱于著重利用標(biāo)簽相關(guān)性信息的ECC方法；對(duì)于enron數(shù)據(jù)集，SOCC方法在平均精度指標(biāo)的表現(xiàn)則略弱于對(duì)稀疏的文本數(shù)據(jù)適應(yīng)性更好的MLFE方法. 為了更清楚地說明SOCC的效果，圖2展示了各算法在所有數(shù)據(jù)集上Trank的平均值，其中Trank值越低表示該算法性能越好. 由此可知，SOCC的綜合表現(xiàn)優(yōu)于對(duì)比算法，表現(xiàn)出了良好的多標(biāo)簽分類性能.

表3 Scene數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

表4 CAL500數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

表5 Emotions數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

表6 enron實(shí)驗(yàn)結(jié)果

圖2 各算法的Rank平均值Fig.2 Average rank of each algorithm

4 結(jié) 論

提出結(jié)合類屬特征及因果發(fā)現(xiàn)的序列優(yōu)化分類器鏈(SOCC). 該方法首先使用仿射傳播聚類，根據(jù)樣本到各聚類中心的距離為每個(gè)基分類器構(gòu)建類屬特征；然后通過條件熵挖掘標(biāo)簽間因果關(guān)系，確定標(biāo)簽順序；最后使用分類器鏈依標(biāo)簽順序進(jìn)行分類. 為了評(píng)估該方法在多標(biāo)簽分類問題上分類效果，將SOCC同LF-LPLC、LIFT、MLFE等多標(biāo)簽分類方法在多個(gè)領(lǐng)域的數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn)，依據(jù)漢明損失、排序損失、1-錯(cuò)誤率、覆蓋率和平均精度5個(gè)指標(biāo)進(jìn)行評(píng)價(jià)，結(jié)果表明，SOCC能夠有效提高分類效果，具有較高的實(shí)用價(jià)值.

研究未來將繼續(xù)關(guān)注于提升SOCC對(duì)稀疏特征的利用與重構(gòu)，提高其在文本分類等任務(wù)上的應(yīng)用效果，同時(shí)嘗試通過考慮標(biāo)簽的局部相關(guān)性，以進(jìn)一步提升其多分類性能.