基于分解策略的多標簽在線特征選擇算法*

張 永 偉，朱 祁，吳 永 城

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

0 引言

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

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

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

1 相關(guān)工作

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

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

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

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

2 多標簽在線特征選擇算法

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

另外，標簽集合也可以表示成二進制的形式：

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

2.1 二類分解策略

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

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

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

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

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

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

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

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

t時刻，分類器更新模型，其中η表示學習率：

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

2.3 基于分解策略的多標簽在線特征選擇算法

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

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

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

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

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

3 實驗結(jié)果與分析

3.1 實驗設(shè)置

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

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

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

3.2 實驗結(jié)果與分析

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

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

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

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

表2是四種算法在六個不同數(shù)據(jù)集上的漢明損失值。可以看出，MLFSGD算法取得比較低的值，尤其在數(shù)據(jù)特征數(shù)比較大的Tmc2007和Rcv1v2數(shù)據(jù)集上，MLFSGD算法的漢明損失值小于MOFS和ML RAND算法。表3所示為四種算法在不同數(shù)據(jù)集上的1-錯誤率值，在六個數(shù)據(jù)集上除了Delicious數(shù)據(jù)集以外，MLFSGD算法都取得最小的值，特別是數(shù)據(jù)集Tmc2007和Rcv1v2。表4是四種算法的排序損失值，MLFSGD算法在大部分數(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)。通過以上實驗證明，本文提出的MLFSGD算法在做多標簽在線特征選擇時能夠取得比較好的結(jié)果。

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

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

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

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

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

4 結(jié)論

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