張 永 偉，朱 祁，吳 永 城

(1.南瑞集團(tuán)(國網(wǎng)電力科學(xué)研究院)有限公司，江蘇 南京 210003；2.南京南瑞智慧交通科技有限公司，江蘇 南京210032)

0 引言

近年來，隨著多標(biāo)簽分類問題的深入研究，出現(xiàn)了大量的多標(biāo)簽分類算法[1-2]。目前，在多標(biāo)簽分類中，存在四種主要的處理策略：數(shù)據(jù)分解法、算法擴(kuò)展法、混合法和集成法[3-4]。特征選擇是多標(biāo)簽分類問題中的一個(gè)重要課題，并且已經(jīng)進(jìn)行了廣泛研究。對(duì)于分類，特征選擇的目標(biāo)是通過相關(guān)特征的一個(gè)子集來構(gòu)建有效的預(yù)測(cè)模型，通過消除不相關(guān)和冗余特征，可以減輕維度災(zāi)難的影響，提高泛化性能，加快學(xué)習(xí)過程，提高模型預(yù)測(cè)的性能。特征選擇已在許多領(lǐng)域得到應(yīng)用，特別是在涉及高維數(shù)據(jù)的問題中。

雖然已經(jīng)進(jìn)行了廣泛研究，但大多數(shù)現(xiàn)有的特征選擇研究都局限于批量學(xué)習(xí)，假定特征選擇任務(wù)是以離線/批量學(xué)習(xí)的方式進(jìn)行的，而且訓(xùn)練實(shí)例的特征是先驗(yàn)的。這樣的假設(shè)并不總是適用于訓(xùn)練樣本以順序方式到達(dá)的實(shí)際應(yīng)用。與批量學(xué)習(xí)方式相比，在線學(xué)習(xí)方式[5]則采用增量的方式處理數(shù)據(jù)集，相對(duì)而言，計(jì)算代價(jià)要小于批量學(xué)習(xí)算法。在現(xiàn)有的多標(biāo)簽在線分類算法中計(jì)算數(shù)據(jù)的全部特征信息是需要代價(jià)的。尤其是存在高維數(shù)據(jù)和數(shù)據(jù)冗余時(shí)，傳統(tǒng)的多標(biāo)簽在線分類算法，需大量計(jì)算且分類性能較差。本文利用在線學(xué)習(xí)的優(yōu)勢(shì)，研究了多標(biāo)簽在線特征選擇問題，旨在通過有效地探索在線學(xué)習(xí)方法來解決多標(biāo)簽特征選擇問題。具體而言，多標(biāo)簽在線特征選擇的目標(biāo)是研究在線分類器，其僅涉及用于分類的少量和固定數(shù)量的特征。當(dāng)處理高維度的連續(xù)訓(xùn)練數(shù)據(jù)時(shí)，如在線垃圾郵件分類任務(wù)(其中傳統(tǒng)的批量特征選擇方法不能直接應(yīng)用)，在線特征選擇尤為重要和必要。

本文提出一種基于分解策略的多標(biāo)簽在線特征選擇算法——MLFSGD算法。該算法采用二類分解策略，將多標(biāo)簽特征選擇問題分解為二類特征選擇問題，然后應(yīng)用二類在線特征選擇算法，完成多標(biāo)簽在線分類任務(wù)。通過多標(biāo)簽特征選擇得到更好的特征子集，能高效地處理高維稀疏數(shù)據(jù)集。通過實(shí)驗(yàn)比較，結(jié)果顯示本文提出的MLFSGD算法能夠有效地降低數(shù)據(jù)維度，同時(shí)算法的分類性能也優(yōu)于其他多標(biāo)簽在線特征選擇算法。

1 相關(guān)工作

在機(jī)器學(xué)習(xí)算法中，在線學(xué)習(xí)是一類高效且擴(kuò)展性較好的方法，這種增量的方式使在線學(xué)習(xí)能夠有效地應(yīng)對(duì)數(shù)據(jù)規(guī)模較大的分類任務(wù)。其中，感知器算法是一種簡單、經(jīng)典的在線學(xué)習(xí)方法[6]，它通過預(yù)測(cè)樣本標(biāo)簽與真實(shí)的樣本標(biāo)簽是否相等，然后根據(jù)損失函數(shù)的大小，以梯度下降的方式求解并更新分類器模型。隨著在線學(xué)習(xí)方法的深入研究，大量的單標(biāo)簽在線分類算法被提出[7-8]。其中，OGD算法是以在線梯度下降算法優(yōu)化不同的損失函數(shù)定義的目標(biāo)函數(shù)。CW算法則通過最小化新的權(quán)值向量分布與之前的權(quán)值向量分布之間的KL散度(Kullback-Leibler Divergence)，來保證正確分類的概率大于設(shè)定的閾值，該算法采用一個(gè)比較主動(dòng)的方式更新權(quán)值向量的分布，可以實(shí)現(xiàn)快速更新模型。SCW算法則克服了CW算法線性不可分、數(shù)據(jù)和噪聲不敏感的缺點(diǎn)，通過在CW算法模型中加入了懲罰項(xiàng)，提高算法分類性能。

相比單標(biāo)簽在線分類問題，多標(biāo)簽在線分類問題的研究則更為復(fù)雜，也更符合現(xiàn)實(shí)應(yīng)用。文獻(xiàn)[9]用二類相關(guān)分解策略,結(jié)合已有的二類在線“被動(dòng)-進(jìn)攻”主動(dòng)學(xué)習(xí)算法,提出基于分解策略的多標(biāo)簽在線“被動(dòng)-進(jìn)攻”主動(dòng)學(xué)習(xí)算法。文獻(xiàn)[10]同樣利用二類分解策略，提出一種基于判別采樣和鏡像梯度下降規(guī)則的多標(biāo)簽在線主動(dòng)學(xué)習(xí)算法，從而更有助于分類器收斂到最佳狀態(tài)。

盡管相關(guān)文獻(xiàn)對(duì)多標(biāo)簽在線分類算法進(jìn)行了研究，但大多數(shù)多標(biāo)簽在線分類算法都需要訪問數(shù)據(jù)樣本的所有特征[11-12]。因此，為了降低模型學(xué)習(xí)成本和計(jì)算代價(jià)，在不影響模型的預(yù)測(cè)能力的前提下，有學(xué)者提出使用特征選擇方法[13-14]以降低學(xué)習(xí)成本和計(jì)算代價(jià)。依照不同的選擇標(biāo)準(zhǔn)，可以將多標(biāo)簽特征選擇方法分為三種：過濾(filter)法，包裹(wrapper)法和嵌入式(embedded)法[15-16]。過濾法是在分類算法開始之前通過測(cè)量樣本特征與類標(biāo)簽之間的相關(guān)性產(chǎn)生特征子集。包裹法依賴于預(yù)定的分類算法的性能來確定最優(yōu)特征子集。包裹法針對(duì)特定模型，易于產(chǎn)生較高的分類性能，但在計(jì)算上通常比過濾法花費(fèi)更大代價(jià)。嵌入法旨在將特征選擇過程嵌入到分類器訓(xùn)練過程中，將特征選擇和分類同時(shí)進(jìn)行。它們通常比包裹法更快并且能夠?yàn)閷W(xué)習(xí)算法提供合適的特征子集。

目前，有關(guān)多標(biāo)簽在線特征選擇算法的文獻(xiàn)很少。本文利用在線學(xué)習(xí)的方式，只允許分類模型訪問少量或固定數(shù)量的特征，其目標(biāo)是從高維的多標(biāo)簽稀疏數(shù)據(jù)集中學(xué)習(xí)線性分類器，進(jìn)而解決特征選擇問題，并對(duì)分類模型中的非零元素的數(shù)量進(jìn)行嚴(yán)格的約束。本文提出的在線特征選擇算法采用二類分解策略，將多標(biāo)簽分解成多個(gè)獨(dú)立的二分類問題。該策略簡單高效、計(jì)算代價(jià)低。在實(shí)驗(yàn)中采用5個(gè)評(píng)價(jià)指標(biāo)進(jìn)行比較，結(jié)果顯示MLFSGD相比其他算法都有比較好的性能，尤其是在特征數(shù)較多的數(shù)據(jù)集上，優(yōu)勢(shì)更加明顯。

2 多標(biāo)簽在線特征選擇算法

本文在處理多標(biāo)簽特征選擇問題時(shí)，設(shè)樣本標(biāo)簽的集合為Q={1，2，…，q}，q表示樣本標(biāo)簽個(gè)數(shù)；假設(shè)樣本X所對(duì)應(yīng)的相關(guān)標(biāo)簽集合L?2Q。給定一個(gè)大小為N且獨(dú)立同分布的訓(xùn)練樣本集合D：

另外，標(biāo)簽集合也可以表示成二進(jìn)制的形式：

其中，第i個(gè)樣本對(duì)應(yīng)的標(biāo)簽也可以表示為一個(gè)二進(jìn)制標(biāo)簽：yi∈{-1，1}q，1表示樣本Xi包含該標(biāo)簽，-1表示不包含該標(biāo)簽。

2.1 二類分解策略

多標(biāo)簽分類算法中，二類分解策略(Binary Relevance，BR)是一種數(shù)據(jù)分解的方法，將多標(biāo)簽分類問題分解成q個(gè)相互獨(dú)立的二類分類問題。對(duì)于一個(gè)標(biāo)簽集合為Q={1，2，…，q}的多標(biāo)簽分類問題，在二類分解方法中，被分解為q個(gè)二類分類的問題，每一個(gè)二類分類問題對(duì)應(yīng)標(biāo)簽集合Q中一個(gè)可能的類別標(biāo)簽。

二類分解的過程是首先為標(biāo)簽集合中的每一個(gè)標(biāo)簽建立對(duì)應(yīng)的二類的訓(xùn)練集合，對(duì)于第j個(gè)類別標(biāo)簽，可以將訓(xùn)練樣本集合分解為如下形式：

其中yj為-1或1，-1表示不是樣本的相關(guān)標(biāo)簽，1表示是樣本的相關(guān)標(biāo)簽。接著，BR方法利用單標(biāo)簽分類的二類分類算法來訓(xùn)練一個(gè)二類分類器hj。這樣，就會(huì)產(chǎn)生q個(gè)二類分類器，每一個(gè)多標(biāo)簽訓(xùn)練集D中的樣本都將參與這q個(gè)分類器的分類過程。在二類分類器hj中，如果樣本Xi與標(biāo)簽j相關(guān)聯(lián)，則被作為一個(gè)正類的樣本，否則，被作為一個(gè)負(fù)類的樣本，在預(yù)測(cè)階段，將未知標(biāo)簽的樣本在每一個(gè)二類分類器中的預(yù)測(cè)結(jié)果結(jié)合起來，就可以得到預(yù)測(cè)出的未知樣本的標(biāo)簽集合Lq，并且滿足：

與其他的多標(biāo)簽數(shù)據(jù)分解策略方法相比，BR方法不僅簡單有效，而且計(jì)算代價(jià)較低。不僅如此，二類相關(guān)分解方法假設(shè)標(biāo)簽之間是相互獨(dú)立的，對(duì)標(biāo)簽的添加或刪除都不會(huì)對(duì)剩余的其他標(biāo)簽產(chǎn)生影響，對(duì)某一個(gè)標(biāo)簽的訓(xùn)練和預(yù)測(cè)也不會(huì)對(duì)其他標(biāo)簽的分類過程產(chǎn)生影響，這樣有利于在線實(shí)現(xiàn)該方法。因此，BR方法適合于處理大規(guī)模的多標(biāo)簽分類問題。

2.2 二類在線特征選擇(OFS)算法

二類在線特征選擇OFS算法[17]是基于向量的分類器模型W∈Rn，其中最多包含B個(gè)非零元素，采用形式sign(W·X)表示，其中向量W中的每個(gè)元素表示分配給每個(gè)樣本Xt的特征權(quán)重。在t時(shí)刻，OFS算法的權(quán)重為Wt，yt(Wt·Xt)表示預(yù)測(cè)函數(shù)。

當(dāng)預(yù)測(cè)值大于0時(shí)，分類器預(yù)測(cè)正確。為了更好地預(yù)測(cè)樣本標(biāo)簽，OFS算法使用在線梯度下降(OGD)算法來優(yōu)化模型W。

其中，C〉0是懲罰參數(shù)，損失函數(shù)為鉸鏈損失(hinge loss)：

t時(shí)刻，分類器更新模型，其中η表示學(xué)習(xí)率：

為了更好地進(jìn)行特征選擇，在更新模型中使用截取函數(shù)，確保更新分類器模型W中的元素是最大的B個(gè)元素。算法1給出了截取函數(shù)的具體步驟。

2.3 基于分解策略的多標(biāo)簽在線特征選擇算法

結(jié)合二類分解策略，本文提出了基于分解策略的多標(biāo)簽在線特征選擇算法——MLFSGD算法。在多標(biāo)簽在線分類算法中，分類器以在線學(xué)習(xí)的方式預(yù)測(cè)樣本Xt的標(biāo)簽集合，最后根據(jù)樣本標(biāo)簽的真實(shí)集合計(jì)算損失來判斷分類器是否更新。然而，對(duì)于大數(shù)據(jù)量的數(shù)據(jù)集而言，這些數(shù)據(jù)具有復(fù)雜化與高維化的特點(diǎn)，尤其對(duì)于稀疏數(shù)據(jù)集而言更是存在著大量的冗余性和無關(guān)性的特征。而這些特征增加了機(jī)器學(xué)習(xí)算法的復(fù)雜度和運(yùn)行時(shí)間，同時(shí)降低了模型預(yù)測(cè)的準(zhǔn)確性。為了解決以上問題，本文使用在線特征選擇的處理方式。對(duì)于多標(biāo)簽數(shù)據(jù)集，每個(gè)樣本都包含多個(gè)標(biāo)簽，本文在不考慮標(biāo)簽相關(guān)性的條件下，使用分解策略將多標(biāo)簽特征選擇問題分解成二類特征選擇問題。具體地，MLFSGD算法首先初始化權(quán)重矩陣：

在t時(shí)刻，對(duì)于樣本Xt，MLFSGD算法首先計(jì)算其預(yù)測(cè)函數(shù)：

其中，sign(·)表示符號(hào)函數(shù)。利用分解策略方式，分類器將樣本Xt分解成q個(gè)獨(dú)立的二類在線OFS算法。每個(gè)樣本Xt含有q個(gè)標(biāo)簽，在t時(shí)刻，如果分類器預(yù)測(cè)樣本Xt錯(cuò)誤，則更新分類器權(quán)重Wt，j：

然后，根據(jù)投影公式對(duì)分類器做二次操作：

最后，利用截取方法選擇B個(gè)特征。算法2概括了MLFSGD算法的具體步驟。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)中采用了MuLan提供的多標(biāo)簽分類數(shù)據(jù)集，數(shù)據(jù)主要集中在文本、視頻和圖像等領(lǐng)域。表1列出了六個(gè)多標(biāo)簽基準(zhǔn)數(shù)據(jù)集(Mediamill、Scene、Delicious、Bibtex、Rcv1v2和Tmc2007)的詳細(xì)信 息。本文采用了5個(gè)多標(biāo)簽評(píng)價(jià)指標(biāo)(漢明損失(Hamming loss)、覆蓋率(coverage)、排序損失(ranking loss)、平均精度(average precision)和1-錯(cuò)誤率(one error))來進(jìn)行算法性能的比較。其中，為了方便表示，對(duì)于覆蓋率指標(biāo)，將該指標(biāo)結(jié)果做了歸一化處理，即將覆蓋率數(shù)值除以數(shù)據(jù)集的標(biāo)簽數(shù)。

本文在操作系統(tǒng)Windows 10環(huán)境中進(jìn)行實(shí)驗(yàn)，使用MATLAB2018b開發(fā)編碼。實(shí)驗(yàn)中，將所選特征的數(shù)量設(shè)置為每個(gè)數(shù)據(jù)集的10%(0.1×維度)，正則化參數(shù)λ設(shè)為0.01，學(xué)習(xí)率η設(shè)為0.2。所有多標(biāo)簽在線算法都使用相同的參數(shù)。對(duì)所有實(shí)驗(yàn)數(shù)據(jù)集進(jìn)行10次隨機(jī)排列，然后對(duì)結(jié)果進(jìn)行平均得到最終實(shí)驗(yàn)結(jié)果。

本文使用三個(gè)基于特征選擇的多標(biāo)簽特征選擇算法：MOFS[18]、MLPEtrun和MLRAND與本文提出的MLFSGD算法進(jìn)行比較。MOFS算法是將多標(biāo)簽數(shù)據(jù)集劃分為多個(gè)單標(biāo)簽數(shù)據(jù)集的一種在線特征選擇算法，解決不平衡數(shù)據(jù)集的分類性能問題。MLPEtrun算法是基于感知器的多標(biāo)簽算法，利用分解策略，將基于感知器的特征選擇算法推廣至多標(biāo)簽分類。MLRAND算法采用隨機(jī)查詢的方式，隨機(jī)選擇固定數(shù)量的特征值，并利用分解策略來解決多標(biāo)簽分類問題。

3.2 實(shí)驗(yàn)結(jié)果與分析

本文首先在兩個(gè)特征數(shù)較多的Rcv1v2和Tmc2007數(shù)據(jù)集上，給出漢明損失、平均精度、1-錯(cuò)誤率和覆蓋率四種指標(biāo)的比較結(jié)果，如圖1和圖2所示。其中圖1表示四種算法在數(shù)據(jù)集Rcv1v2上四種不同評(píng)價(jià)指標(biāo)的比對(duì)結(jié)果?？梢钥闯霰疚奶岢龅腗LFSGD算法優(yōu)于其他算法。圖2表示四種算法在數(shù)據(jù)集Tmc2007上不同評(píng)價(jià)指標(biāo)的對(duì)比結(jié)果，可以看到在評(píng)價(jià)指標(biāo)1-錯(cuò)誤率和平均精度上，MLFSGD算法明顯優(yōu)于其他算法，在另外兩種指標(biāo)中，MLFSGD算法優(yōu)于MOFS算法和MLRAND算法，僅次于MLPEtrun算法。同時(shí)可以看到隨著選擇特征比例的不斷增加，所有算法的分類性能沒有特別明顯的提升，這也證明特征選擇的優(yōu)勢(shì)。

圖1 四種算法在Rcv1v2上的比較結(jié)果

圖2 四種算法在Tmc2007上的比較結(jié)果

為了更好地評(píng)估本文提出的MLFSGD算法，表2～表6給出了在六個(gè)數(shù)據(jù)集上四種算法的實(shí)驗(yàn)結(jié)果。

表2是四種算法在六個(gè)不同數(shù)據(jù)集上的漢明損失值?？梢钥闯?，MLFSGD算法取得比較低的值，尤其在數(shù)據(jù)特征數(shù)比較大的Tmc2007和Rcv1v2數(shù)據(jù)集上，MLFSGD算法的漢明損失值小于MOFS和ML RAND算法。表3所示為四種算法在不同數(shù)據(jù)集上的1-錯(cuò)誤率值，在六個(gè)數(shù)據(jù)集上除了Delicious數(shù)據(jù)集以外，MLFSGD算法都取得最小的值，特別是數(shù)據(jù)集Tmc2007和Rcv1v2。表4是四種算法的排序損失值，MLFSGD算法在大部分?jǐn)?shù)據(jù)集上為最優(yōu)，其中，在Tmc2007數(shù)據(jù)集上，MLPEtrun算法要優(yōu)于文本提出的MLFSGD算法。表5所示為四種算法的覆蓋率值，從表中可以觀察到，MLFSGD算法除了在Tmc2007數(shù)據(jù)集次優(yōu)之外，其他數(shù)據(jù)集上結(jié)果最優(yōu)。表6所示為四種算法的平均精度值，MLFSGD算法在所有數(shù)據(jù)集上均為最優(yōu)。通過以上實(shí)驗(yàn)證明，本文提出的MLFSGD算法在做多標(biāo)簽在線特征選擇時(shí)能夠取得比較好的結(jié)果。

表2 四種算法在六個(gè)數(shù)據(jù)集上的漢明損失

表3 四種算法在六個(gè)數(shù)據(jù)集上的1-錯(cuò)誤率

表4 四種算法在六個(gè)數(shù)據(jù)集上的排序損失

表5 四種算法在六個(gè)數(shù)據(jù)集上的覆蓋率

表6 四種算法在六個(gè)數(shù)據(jù)集上的平均精度

4 結(jié)論

本文提出了基于分解策略的多標(biāo)簽在線特征選擇算法，將多標(biāo)簽在線特征選擇問題分解成多個(gè)二類在線特征選擇問題，進(jìn)而對(duì)樣本進(jìn)行特征選擇。實(shí)驗(yàn)基于六個(gè)數(shù)據(jù)集，使用不同的多標(biāo)簽評(píng)價(jià)指標(biāo)，比較MLFSGD算法和其他三種在線特征選擇算法在特征子集個(gè)數(shù)從10%增加到100%時(shí)的性能。實(shí)驗(yàn)表明，MLFSGD算法在處理多標(biāo)簽在線特征選擇時(shí)，性能優(yōu)于其他在線算法。由于該算法假設(shè)樣本之間相互獨(dú)立，并沒有考慮樣本標(biāo)簽相關(guān)性，未來工作中，將就標(biāo)簽的相關(guān)性進(jìn)行進(jìn)一步研究。