潘敏瀾，孫占全，王朝立，曹高宇

(上海理工大學(xué) 光電信息與計算機工程學(xué)院，上海 200093)

1 引 言

多標(biāo)簽學(xué)習(xí)作為機器學(xué)習(xí)的一個分支，應(yīng)用廣泛，例如在文本分類[1]、圖像自動標(biāo)注[2]、基因分析[3]等領(lǐng)域有著廣泛的應(yīng)用.

隨著科學(xué)技術(shù)的迅速發(fā)展，數(shù)據(jù)維度變高，給多標(biāo)簽學(xué)習(xí)帶來巨大的挑戰(zhàn)，研究學(xué)者們稱之為維度災(zāi)難[4].維度災(zāi)難主要表現(xiàn)為以下兩個方面：首先，高維度數(shù)據(jù)會給多標(biāo)簽學(xué)習(xí)增加巨大的計算代價[5].其次，高維數(shù)據(jù)會帶來大量無關(guān)或冗余信息，多標(biāo)簽分類器在訓(xùn)練中大量擬合無關(guān)和冗余信息，使得泛化性能和預(yù)測精度降低[5].

多標(biāo)簽特征選擇作為一種降維技術(shù)，能有效解決上述的維度災(zāi)難問題.特征選擇能篩選出和學(xué)習(xí)問題相關(guān)的信息，剔除無關(guān)和冗余信息，達到提升分類器性能和減少計算代價的目的.多標(biāo)簽特征選擇算法分為3大類：袋裝式、嵌入式、過濾式.袋裝式算法篩選特征需要根據(jù)特定的分類器，每篩選一次特征都需要重新訓(xùn)練一次分類器，優(yōu)點是能考慮到特征組合的多樣性，缺點在于計算量非常大.由于實際上特征之間組合數(shù)非常浩大，故一般袋裝式算法會結(jié)合啟發(fā)式算法，如張敏靈等人提出的MLNB[6].嵌入式算法則和分類器融為一體，即它本身就是分類器.一般嵌入式算法結(jié)合凸優(yōu)化、正則化等方法得到權(quán)重矩陣來判別各特征的重要性，如JFSC[7]、SFUS[8].過濾式算法獨立于分類器，通常結(jié)合信息論指標(biāo)如互信息[9，10]、模糊互信息[11]、交互信息[12]、近鄰粒度[13]、統(tǒng)計學(xué)指標(biāo)余弦相關(guān)性和皮爾遜相關(guān)系數(shù)[14]、多標(biāo)簽代價敏感策略[15]，來評價特征的重要性.一般認為，過濾式算法計算簡便，靈活高效.

本文將結(jié)合互信息衡量標(biāo)簽和標(biāo)簽的相關(guān)性，再通過標(biāo)簽集的聚類結(jié)合最大相關(guān)最小冗余框架篩選特征.

2 理論基礎(chǔ)

2.1 信息熵

定義 1.熵(entropy)最早由香農(nóng)提出[16]，在信息學(xué)，熱力學(xué)，社會科學(xué)等領(lǐng)域有著廣泛的應(yīng)用.信息熵是衡量一個變量所攜帶的信息.在給定隨機變量X={x1，x2，…，xn}，熵的定義如下：

(1)

其中p(xi)表示變量xi出現(xiàn)的概率.

定義 2.二維聯(lián)合熵衡量兩個隨機變量一起包含的信息，給定隨機變量X={x1x2，…，xn}，Y={y1，y2，…，ym}，二維聯(lián)合熵的定義如下：

(2)

其中p(xi，yj)表示變量xi，yj的聯(lián)合概率.

定義 3.類似的定義可以擴展到高維熵：

H(X1，X2，…，Xn)

(3)

其中p(xi1，xi2，…，xik)是聯(lián)合概率.

定義 4.條件熵衡量在一個變量被觀察到的情況下，另一個變量單獨包含的信息.給定隨機變量X={x1，x2，…，xn}，Y={y1，y2，…，ym}，它的定義為：

(4)

其中p(xi，yj)和p(xi|yj)分別表示變量xi，yj的聯(lián)合概率.

性質(zhì) 1.聯(lián)合熵、條件熵、熵之間的關(guān)系：

H(X，Y)=H(Y)+H(X|Y)

(5)

2.2 互信息

定義 5.互信息衡量兩個變量共同的信息.給定隨機變量X={x1，x2，…，xn}，Y={y1，y2，…，ym}，互信息的定義如下：

(6)

性質(zhì) 2.互信息、熵、聯(lián)合熵之間的關(guān)系：

I(X，Y)=H(X)+H(Y)-H(X，Y)

(7)

定義 6.條件互信息衡量在給定一個隨機變量，另外兩個隨機變量共同包含的信息，它的定義如下：

I(X；Y|Z)=H(X|Z)-H(X|Y，Z)

(8)

定義 7.交互信息衡量3個變量之間的信息協(xié)同和冗余程度.當(dāng)交互信息為正時表明，3個變量的信息含有冗余，當(dāng)交互信息為負時表明3個變量信息具有協(xié)同作用.給定隨機變量X，Y，Z，交互信息定義如下：

I(X；Y；Z)=I(X；Y)-I(X；Y|Z)

(9)

性質(zhì) 3.交互信息具有對稱性：

I(X；Y；Z)=I(X；Z；Y)=I(Y；X；Z)

(10)

3 相關(guān)工作

J(f+)=I(S，f+；L)-I(S；L)

(11)

其中f+∈F-S，S是已選擇的特征集合，L是標(biāo)簽集.

根據(jù)公式(3)和公式(6)，可知公式(11)涉及高維熵和高維概率的計算，計算量極大.因此這現(xiàn)年學(xué)者大多從高維互信息或高維熵的近似估計的角度入手.

2012年，Lee和Kim提出AMI[17](Approximating mutual information)算法.該算法規(guī)避無法精確計算高維聯(lián)合互信息的問題，提出基于Shearer′s inequality[18]的高維互信息近似算法.該算法選擇特征通過最小化如下指標(biāo)：

(12)

從整體上該算法未能體現(xiàn)多標(biāo)簽的數(shù)據(jù)的特性，即未考慮標(biāo)簽與標(biāo)簽之間的相關(guān)性.2013年Lee和Kim提出了考慮成對標(biāo)簽相關(guān)性的特征選擇算法PMU[19](Pairwise Multi-label Utility)，該算法選擇特征最大化如下指標(biāo)：

(13)

該算法解決了標(biāo)簽相關(guān)性的問題，但涉及大量的交互信息計算，因此計算量極大.

2015年，Lee和Kim改進了PMU計算量大的問題，提出D2F[20]算法.和PMU算法相比D2F少了第3項，具體選擇特征最大化如下指標(biāo)：

(14)

同年，林耀進等人受單標(biāo)簽特征選擇算法MRMR[21](Max-Relevance and Min-Redundancy)的啟發(fā)，在多標(biāo)簽領(lǐng)域提出MDMR[22]算法，該算法選擇特征最大化如下指標(biāo)：

(15)

2017年，Lee和Kim在最大相關(guān)和最小冗余的框架下，提出基于兩者可伸縮的系數(shù)特征選擇算法SCLS[23].該算法有效解決因標(biāo)簽集過大而導(dǎo)致的評估誤差問題，該算法選擇特征最大化如下指標(biāo)：

(16)

2019年，張萍等人提出基于標(biāo)簽冗余的算法LRFS[24].該算法，針對兩種特定的標(biāo)簽類型，基于標(biāo)簽和標(biāo)簽之間的冗余來度量特征和標(biāo)簽的相關(guān)性.

在其他方向的多標(biāo)簽特征選擇領(lǐng)域中，如2020年孫林等人基于ReliefF提出名為RFNMIFS[25]的多標(biāo)簽特征選擇算法.同年Mohsen Paniri等人第一次在多標(biāo)簽特征選擇應(yīng)用蟻群算法(ACO)提出MLACO[14]算法，該算法結(jié)合皮爾遜相關(guān)性系數(shù)和余弦相關(guān)性系數(shù)構(gòu)造信息素和啟發(fā)因子篩選特征.

綜上所述，以上基于互信息的算法缺乏考慮標(biāo)簽集的結(jié)構(gòu)，如MDMR，LRFS，PMU，D2F都只考慮到二階標(biāo)簽相關(guān)性，沒有考慮標(biāo)簽集的高階相關(guān)性和語義結(jié)構(gòu).本文基于互信息和標(biāo)簽集的聚類，提出同時兼顧標(biāo)簽集高階相關(guān)性和語義結(jié)構(gòu)的多標(biāo)簽特征選擇算法.

4 所提方法

4.1 標(biāo)簽集聚類

標(biāo)簽集自身是帶有語義結(jié)構(gòu)的.例如假設(shè)一個自然景色的數(shù)據(jù)集有藍鯨、駱駝、仙人掌、海浪、森林、猴子、海鷗這7個標(biāo)簽.顯然自然風(fēng)景中，藍鯨和駱駝很難出現(xiàn)在一個樣本里，這兩個標(biāo)簽基本是互斥的.實際上，這7個標(biāo)簽很容易得到一個語義結(jié)構(gòu)：藍鯨、海鷗、海浪為一組，代表海洋風(fēng)景，森林和猴子為一組，代表森林風(fēng)景，仙人掌和駱駝為一組，代表沙漠風(fēng)景.傳統(tǒng)算法大多只考慮二階標(biāo)簽相關(guān)性而忽略二階以上的相關(guān)性，從而忽略標(biāo)簽集固有的語義結(jié)構(gòu).針對傳統(tǒng)算法的不足，本文應(yīng)用標(biāo)簽聚類獲得標(biāo)簽集語義結(jié)構(gòu).即將藍鯨、海鷗、海浪聚為一類，森林和猴子聚為一類，仙人掌和駱駝聚為一類.

我們先構(gòu)造標(biāo)簽相關(guān)性矩陣.假設(shè)訓(xùn)練集的標(biāo)簽集為：L={l1，l2，…，lq}.我們依據(jù)標(biāo)簽兩兩之間的互信息給出標(biāo)簽的相關(guān)性矩陣：

定義 8.互信息矩陣T：

T=(tij)q×q

(17)

若li≠lj，則tij代表標(biāo)簽li和標(biāo)簽lj的互信息，若li=lj，則tij=0.也即：

(18)

顯然T是對稱陣，主對角線元素均為0，即標(biāo)簽自身和自身的相關(guān)性不計入統(tǒng)計.為了防止標(biāo)簽熵的差異導(dǎo)致互信息相差過大這里我們引入互信息與標(biāo)簽熵權(quán)重占比的相關(guān)性矩陣，為了下文敘述方便，我們將稱之為互信息權(quán)重占比矩陣：

定義 9.互信息權(quán)重占比矩陣R：

R=(rij)q×q

(19)

其中

(20)

(21)

下面通過一個例子來說明標(biāo)簽的聚類.給定一個人工訓(xùn)練集數(shù)據(jù)標(biāo)簽集示例，具體如表1所示.

表1 人工訓(xùn)練集數(shù)據(jù)標(biāo)簽集示例Table 1 Artificial training data tag set example

第1步，基于上面的數(shù)據(jù)，根據(jù)(6)式計算出互信息矩陣T(式(6)中的對數(shù)我們以自然常數(shù)為底，取值保留4位小數(shù)，若為0則不計后4位小數(shù))：

(22)

第2步，按照定義9計算矩陣R：

(23)

可以看到，R中的取值集中在0到0.3之間.

(24)

最終得到結(jié)果：聚類向量[0 0 0 1 0]，即標(biāo)簽l1、l2、l3、l5為一類，l4為一類.

4.2 特征選擇

應(yīng)用AP算法得到了標(biāo)簽聚類簇記為C1，C2，…，Ck共k共個簇.其中，?Ci?L，包含ji個標(biāo)簽，即Ci={li1，li2，…，liji}.

為了分析方便，考慮標(biāo)簽只有7個的情況，我們結(jié)合信息韋恩圖來分析，原始標(biāo)簽集的信息韋恩圖如圖1所示.

圖1 7個標(biāo)簽的信息韋恩圖Fig.1 Information Venn diagram of 7 labels

聚類后的示意圖如圖2所示.

圖2 聚類后的信息韋恩圖Fig.2 Information Venn diagram after clustering

傳統(tǒng)的方式衡量相關(guān)項大多對標(biāo)簽無差別對待，沒有挖掘標(biāo)簽語義結(jié)構(gòu)信息.通過聚類把強相關(guān)性的標(biāo)簽歸為一簇，彼此弱相關(guān)的標(biāo)簽分離開.不同于標(biāo)簽傳統(tǒng)的相關(guān)性衡量式(25)，我們采用式(26)的近似方式.

Rel(f)=I(f；L)≈∑l∈LI(f；l)

(25)

Rel(f)=I(f；L)≈∑Ci?LI(f；Ci)

(26)

由于同簇中的標(biāo)簽相關(guān)性很強，以遍歷的方式累加則會造成互信息重復(fù)計算.以簇3為例說明，假定特征f與簇3的信息韋恩圖如圖3所示.

圖3 特征f與簇C3信息韋恩圖Fig.3 Information Venn diagram of feature f and cluster C3

當(dāng)出現(xiàn)如圖3所示的情況時，特征與l6，l7正確的相關(guān)性度量即互信息為：I(f；C3)=b+c.而傳統(tǒng)的遍歷累加方式為I(f；C3)=b+c+c，因此單從簇C3上的相關(guān)性度量上看，傳統(tǒng)的遍歷累加方式會多計算一遍c區(qū)域，因此傳統(tǒng)的方式會在相關(guān)性度量時造成巨大的誤差，從而影響算法的性能.

針對以上傳統(tǒng)方法的不足本文提出以下特征與簇相關(guān)性的近似估計方法.給定?Ci?L，我們采用新的相關(guān)性估計，簇Ci與特征的相關(guān)性為：

(27)

應(yīng)用式(27)驗證圖3中的情況，I(f；C3)=maxI(f；l6)，I(f；l7)=I(f；l6)=b+c，和真實的值b+c相同.

擴展到整個標(biāo)簽集根據(jù)式(26)，式(27)，可得到特征和標(biāo)簽集的相關(guān)性：

(28)

應(yīng)用最大相關(guān)最小冗余框架可得到篩選特征指標(biāo)：

J(f)=Rel(f)-Red(f)

(29)

其中Rel(f)根據(jù)式(28)計算.Red(f)代表特征f和已選特征子集的冗余，Red(f)的計算如式(30)所示:

(30)

其中S是已選特征子集.

由于算法前向式搜索在篩選特征過程中，已選特征子集數(shù)量是逐漸增長的，因此需要乘上一個平衡項，防止冗余項和相關(guān)項因簇的個數(shù)和已選特征子集的個數(shù)不平衡導(dǎo)致其中某一項的誤差被放大.結(jié)合式(29)得到最終的指標(biāo)如式(31)所示:

(31)

其中k為AP聚類算法得到的聚類個數(shù)，|S|代表已選特征子集的個數(shù).

本文所提算法的描述如算法1所示.

算法1.

輸入：訓(xùn)練集標(biāo)簽原始特征F={f1，f2，…，fn}，訓(xùn)練集標(biāo)簽集L={l1，l2，…，lq}，需要選擇的特征數(shù)d.

輸出：特征子集S.

Begin：

3.初始化S→?；

4.選擇第一個特征：使得∑l∈LI(f；l)最大的f；

與S：

5.更新F，F(xiàn)→F-f；

6.更新S，S→S+f；

7. while |S|

8. For infiinF；

9. 根據(jù)式(31)計算J(fi)；

10. 記錄7)中使得J(·)最大的特征fj；

11. 更新F，F(xiàn)→F-fj；

12. 更新S，S→S+fj；

13. end while；

14.返回特征子集S

End

假定數(shù)據(jù)集樣本個數(shù)為m，特征個數(shù)為d，需要選擇的特征個數(shù)為b，標(biāo)簽個數(shù)為q.本算法分為兩部分.第1部分聚類算法時間復(fù)雜度為：O(mq2).第2部分計算指標(biāo)的算法時間復(fù)雜度為：O(mdq)+O(mdb).故本文算法時間復(fù)雜度為：O(mq2+mdq+mdb).

5 實驗設(shè)計與分析

5.1 實驗數(shù)據(jù)

本文實驗數(shù)據(jù)為6個真實多標(biāo)簽數(shù)據(jù)集：Arts、Entertain、Recreation、Health、Social、Business.以上數(shù)據(jù)集均來源于Mulan Library[27].各數(shù)據(jù)集詳細信息如表2所示.

表2 多標(biāo)簽數(shù)據(jù)集Table 2 Multi label datasets

5.2 評價指標(biāo)

為了對比算法的性能，本文采用了漢明損失(Hamming Loss)，平均精度(Average Precision)，排序損失(Ranking Loss)，覆蓋率(Coverage)，0-1損失(One Error)5個評價指標(biāo)[28]，為了方便展示，5個評價指標(biāo)分別記為HL(↓)、AP(↑)、RL(↓)、 CV(↓)、 OE(↓).其中有標(biāo)↑記號的表示數(shù)值越大算法性能越好，標(biāo)↓記號的表示數(shù)值越小算法性能越好.

5.3 實驗設(shè)計及結(jié)果分析

本文選取近些年來著名的算法作為對比.分別為PMU[19]、D2F[20]、MDMR[22]、SCLS[23]、AMI[17]、LRFS[24]、MLACO[14].6個數(shù)據(jù)集均選擇50個特征，步長為1，每選一個特征就將所選的特征加入已選特征子集作為分類器的輸入.由于6個數(shù)據(jù)集特征數(shù)值是連續(xù)的，本文所提算法采取3等寬離散方式.

此外，分類器均用MLKNN[29]平滑系數(shù)設(shè)為1，近鄰系數(shù)k設(shè)為10.

實驗結(jié)果如表3-表7所示.其中每一個指標(biāo)的數(shù)值，是50次結(jié)果的平均值，結(jié)果保留4位小數(shù).表中黑體字代表同一個數(shù)據(jù)集上，該指標(biāo)最優(yōu)的結(jié)果.此外“Proposed”代表本文所提算法.

表3 所有算法在HL(↓)指標(biāo)下的結(jié)果Table 3 Results of all algorithms under HL(↓)index are compared

從表3-表7的結(jié)果上，不難發(fā)現(xiàn)本文所提算法在6個數(shù)據(jù)上的結(jié)果是最優(yōu)的.

在指標(biāo)HL上，如表3所示.本文算法在6個數(shù)據(jù)集上均取得最好的結(jié)果.其中在Entertain數(shù)據(jù)集上，本文算法的性能和AMI算法并列排名第一，在Business數(shù)據(jù)集上，本文算法的性能和LRFS以及AMI算法并列排名第一.

在指標(biāo)AP上，如表4所示.本文算法在6個數(shù)據(jù)集上均取得最好的結(jié)果.

在指標(biāo)RL上，如表5所示.本文算法在6個數(shù)據(jù)集上均取得最好的結(jié)果.

表4 所有算法在AP(↑)指標(biāo)下的結(jié)果Table 4 Results of all algorithms under AP(↑)index are compared

表5 各算法在RL(↓)指標(biāo)下的結(jié)果Table 5 Results of all algorithms under RL(↓)index are compared

表6 所有算法在CV(↓)指標(biāo)下的結(jié)果Table 6 Results of all algorithms under CV(↓)index are compared

在指標(biāo)CV上，如表6所示.本文算法在Entertain，Recreation，Health，Business數(shù)據(jù)集上取得最好結(jié)果.

在指標(biāo)OE上，如表7所示.本文算法在Arts、 Entertain、Recreation、Health數(shù)據(jù)集上取得最好結(jié)果.

表7 所有算法在OE(↓)指標(biāo)下的結(jié)果Table 7 Results of all algorithms under OE(↓)index are compared

從整體上看，本文算法在HL、AP、RL、CV、OE指標(biāo)上最優(yōu)率分別為100%，100%，100%，66.7%，66.7%，平均最優(yōu)率在86.7%，因此可以證明本文算法有很強的魯棒性和有效性.

為了展示更多的細節(jié)，本文給出了Health和Entertain兩個數(shù)據(jù)集上的各指標(biāo)趨勢圖，如圖4-圖5所示.其中橫坐標(biāo)為選擇特征的個數(shù)，縱坐標(biāo)是個指標(biāo)的數(shù)值.

以數(shù)據(jù)集Health中HL指標(biāo)為例.圖4中，從Health數(shù)據(jù)集上的HL指標(biāo)趨勢圖上，可以看到本文算法的大部分情況都是最優(yōu)的.此外，在選擇特征數(shù)為1-20時，本文算法明顯優(yōu)于其余算法，因此在特征選擇的簡約性上也明顯占優(yōu).其他四個指標(biāo)上，本文算法同樣是最優(yōu)的.

圖4 Health數(shù)據(jù)集上各指標(biāo)的趨勢圖Fig.4 Trend chart of each indicator on the Health data set

傳統(tǒng)的算法如PMU和D2F由于指標(biāo)中含有交互信息，累加過程中項數(shù)過多，導(dǎo)致誤差累積的越來越大，因此算法效果不佳.篩選特征指標(biāo)中含有交互信息項的算法MDMR和LRFS同樣存在類似的缺陷，因此在性能上都未能取得最優(yōu).MLACO的算法由于是基于余弦相關(guān)性和皮爾遜相關(guān)系數(shù)兩種線性相關(guān)性構(gòu)建篩選特征指標(biāo)，因此對非線性相關(guān)性挖掘不夠，因此性能上也未能達到最優(yōu).AMI和SCLS算法篩選特征是基于互信息的，忽略了標(biāo)簽和標(biāo)簽之間的相關(guān)信息，因此性能同樣未達到最優(yōu).

圖5 Entertain數(shù)據(jù)集上各指標(biāo)的趨勢圖Fig.5 Trend chart of each indicator on the Entertain data set

6 結(jié)束語

本文基于互信息和相關(guān)性聚類思想，提出了基于標(biāo)簽語義結(jié)構(gòu)的特征選擇算法.克服了傳統(tǒng)算法相關(guān)性度量通過累加形式導(dǎo)致忽略標(biāo)簽相關(guān)性或只考慮兩兩標(biāo)簽相關(guān)，以及引入交互信息增加計算量的缺點.本文算法和近幾年的7種算法在6個數(shù)據(jù)集上進行對比實驗.每個數(shù)據(jù)集上均用5個指標(biāo)作為結(jié)果對比.實驗結(jié)果表明本文算法具有明顯優(yōu)勢.盡管在這6個數(shù)據(jù)集上有著較好的表現(xiàn).但對于標(biāo)簽個數(shù)較少的數(shù)據(jù)集采用聚類方法可能導(dǎo)致效果不佳.因此在未來，我們著重探索其他相關(guān)性分析方法，挖掘標(biāo)簽集的語義結(jié)構(gòu)，從而提出更加精準(zhǔn)的特征選擇指標(biāo).