基于DEC算法的多標(biāo)記學(xué)習(xí)

王一賓，李閃閃，裴根生

(1.安慶師范大學(xué)計算機(jī)與信息學(xué)院，安徽安慶246133；2.安徽省高校智能感知與計算重點實驗室，安徽安慶246133)

聚類分析是機(jī)器學(xué)習(xí)[1]與數(shù)據(jù)挖掘領(lǐng)域中一種多元統(tǒng)計分析算法[2]，在模式識別、圖像處理、文本分析等領(lǐng)域有著廣泛的應(yīng)用。由于各領(lǐng)域數(shù)據(jù)本身的復(fù)雜性，聚類算法在處理低維數(shù)據(jù)時效果不錯，但在高維空間，直接聚類存在一定的挑戰(zhàn)。為了解決這一問題，將降維思想與聚類相結(jié)合解決實際問題的方法相繼被提出[3]，其中，PCAKM算法[4-5]、LDAKM算法[6]最為常見。而判別嵌入式聚類（Discriminative Embedded Clustering，DEC）算法[7]是一種聚類高維數(shù)據(jù)的整合框架，將降維與聚類迭代交替進(jìn)行，規(guī)避了傳統(tǒng)聚類算法存在的缺點。現(xiàn)今大數(shù)據(jù)時代，多標(biāo)記學(xué)習(xí)已成為國內(nèi)外機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點[8-9]。但在實際應(yīng)用中，多標(biāo)記學(xué)習(xí)會涉及許多高維數(shù)據(jù)。因此，鑒于DEC算法有效解決高維數(shù)據(jù)的特點，針對多標(biāo)記學(xué)習(xí)中可能存在的“維度災(zāi)難”問題[10]，本文提出基于DEC算法的多標(biāo)記學(xué)習(xí)。

1 DEC算法

DEC算法[7]是一種集合多種維度約簡算法處理高維數(shù)據(jù)的整合框架，而PCAKM算法（當(dāng)平衡參數(shù)λ→0時）、OCMKM算法[11]（當(dāng)平衡參數(shù)λ=1時）、MMCKM算法[12]（當(dāng)平衡參數(shù)λ=2時），均可看做是DEC算法的特例，其基本差異在于平衡參數(shù)λ的取值不同。DEC算法包含維度約簡函數(shù)和聚類損失函數(shù)兩個目標(biāo)函數(shù)。

DEC算法中維度約簡部分，以MMC算法為例，對應(yīng)目標(biāo)函數(shù)描述如下：

其中，Q ∈ RD×d表示轉(zhuǎn)換矩陣c(xj-xˉi)T為類內(nèi)散布矩陣。這里高維空間數(shù)據(jù){xi∈RD|i=1,2,…,n}，對應(yīng)到低維空間描述為{yi∈Rd|i=1,2,…,n}，D和d分別指高維空間和低維空間對應(yīng)的維度。

此處，與低維空間矩陣Y對應(yīng)，X=[ X1,X2…,Xn]∈RD×n為高維空間的數(shù)據(jù)矩陣。

2 多標(biāo)記學(xué)習(xí)

2.1 問題定義

假設(shè)有p維樣本空間X=Rp，Y={ y1,y2,…,yq}表示包含q個不同的分類標(biāo)簽的標(biāo)簽屬性。給定多標(biāo)記數(shù)據(jù)集D=其中每一個xi=[xi1,xi2,…,xip]都是p維屬性向量，Yi=[yi1,yi2,…,yiq]表示與xi相對應(yīng)的一組標(biāo)簽向量。多標(biāo)記學(xué)習(xí)主要就是在給定數(shù)據(jù)集D的情形下，構(gòu)造一個多標(biāo)記分類器，使得當(dāng)輸入待分類的實例屬性xi∈X時，分類器f能夠推測出從屬于該實例的類別標(biāo)記集合f(x) ?Y。

2.2 多標(biāo)記學(xué)習(xí)評價指標(biāo)

由于多標(biāo)記學(xué)習(xí)框架中，每個對象同時屬于多個類別標(biāo)簽，因此其性能評價指標(biāo)與傳統(tǒng)單標(biāo)記學(xué)習(xí)有所不同。最為經(jīng)典的多標(biāo)記評價指標(biāo)有平均查準(zhǔn)率（Average Precision，AP）、覆蓋率（Coverage，CO）、漢明損失（Hamming Loss，HL）、一錯誤率（One-Error，OE）、排位損失（Ranking Loss，RL）[8]等。設(shè)有預(yù)測函數(shù)f( )·,·，定義排序函數(shù)rankf( )·,·，若給定多標(biāo)記測試集S=則各評價指標(biāo)定義如下[8]。

AP用于評估全部樣本的預(yù)測標(biāo)記排序，排在相關(guān)標(biāo)記之前的標(biāo)記也屬于相關(guān)標(biāo)記的概率的平均。APS越大，分類性能越優(yōu)，當(dāng)APS(f)=1時，取得最好結(jié)果。

CO用于評估樣本的預(yù)測標(biāo)記排序，平均需要移動多少步才能覆蓋樣本的全部相關(guān)標(biāo)記。COS(f)越小，分類性能越優(yōu)，最好的分類結(jié)果為

其中Δ表示兩個集合之間的“對稱差”，HL用于評估樣本標(biāo)簽被錯誤分類的情況，即相關(guān)標(biāo)記未出現(xiàn)在該樣本的預(yù)測標(biāo)簽集中，而無關(guān)標(biāo)記卻出現(xiàn)在該樣本的預(yù)測標(biāo)簽集中。HLS()h越小，分類性能越優(yōu)，當(dāng)HLS()h =0時，分類結(jié)果最好。

RL用于評估不相關(guān)標(biāo)記排位高于相關(guān)標(biāo)記排位的次數(shù)情況。RLS(f)越小，分類性能越優(yōu)，當(dāng)RLS(f)=0時，分類結(jié)果最優(yōu)。

OE用于評估所有樣本的預(yù)測標(biāo)記排序，排在最前面的標(biāo)記不屬于該樣本的相關(guān)標(biāo)記集的次數(shù)情況。越小，分類性能越優(yōu)，當(dāng)0時，分類結(jié)果最好。

3 基于DEC算法的多標(biāo)記學(xué)習(xí)

3.1 算法描述

多標(biāo)記學(xué)習(xí)的主要任務(wù)是多標(biāo)記維度約簡和多標(biāo)記分類，本文基于DEC算法，對數(shù)據(jù)做維度約簡處理，訓(xùn)練多標(biāo)記分類器，最后分析算法的實驗性能。算法具體流程如下：

1）輸入數(shù)據(jù)集以及平衡參數(shù)λ；

2）通過PCA等算法初始化轉(zhuǎn)換矩陣Q，執(zhí)行K-means算法計算QTX、初始化聚類指示器F；

3）交替更新Q，G，F(xiàn)直至收斂：通過某種比較準(zhǔn)則更新聚類指示器F，根據(jù)計算第d個特征值對應(yīng)的特征向量并更新轉(zhuǎn)換矩陣更新聚類中心矩陣G；

4）輸出轉(zhuǎn)換矩陣Q及聚類指示器F；

5）設(shè)定最終聚類數(shù)目k以及特征維數(shù)d，得到約簡數(shù)據(jù)集；

6）數(shù)據(jù)處理，劃分訓(xùn)練集和測試集比例；

7）訓(xùn)練多標(biāo)記分類器MLKNN（MLNB），輸出各評價指標(biāo)。

λ是平衡維度約簡與聚類效果的參數(shù)，λ越大，表明越重視聚類的影響。λ=2時，算法性能較好，而且在λ=2時，DEC算法采用MMC算法代替其他維度約簡算法，其鑒別準(zhǔn)則為類間散布矩陣與類內(nèi)散布矩陣的跡之差，避免了因矩陣不可逆而無法求解的問題[7，10]。因此本文取λ=2。對于不同的數(shù)據(jù)集，聚類數(shù)目k以及約簡維數(shù)d設(shè)定值也不相同；d太大，無法降低數(shù)據(jù)冗余，d太小可能造成不同聚類間的重疊，因此需要多次試驗以選擇實驗結(jié)果最優(yōu)的取值。

3.2 計算復(fù)雜度分析

若將n個D維數(shù)據(jù)構(gòu)成c類，則K-means算法的計算復(fù)雜度為O( n cD)。DEC算法分為特征分解以及聚類兩個步驟，對應(yīng)的計算復(fù)雜度分別為假定迭代次數(shù)為T，則DEC算法的計算復(fù)雜度為O((D2n+ncd)T)。由此看出，算法的計算主要在于特征分解部分，對于維度很高的大規(guī)模數(shù)據(jù)集，算法運行速度還有待提升。

4 實驗及結(jié)果分析

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

為了分析基于DEC算法的多標(biāo)記學(xué)習(xí)算法的實驗性能[13]，本文共選取了5個公開的多標(biāo)記數(shù)據(jù)集如表1所示，這些數(shù)據(jù)集全部來自http://mulan.sourceforge.net/datasets.html.，其基本信息描述如表1所示。

表1 多標(biāo)記數(shù)據(jù)集

4.2 實驗環(huán)境與方法

實驗均在3.30 GHz的處理器、2.00 GB的內(nèi)存、Windows7系統(tǒng)及Matlab R2012b的實驗平臺上運行。多標(biāo)記分類方法參數(shù)值設(shè)定如下：

1)基于K近鄰分類器的多標(biāo)記學(xué)習(xí)算法[14]（MLKNN），平滑參數(shù)設(shè)定s=1，近鄰k=10；

2)基于樸素貝葉斯分類器的多標(biāo)記學(xué)習(xí)算法[15]（MLNB），平滑參數(shù)設(shè)定為默認(rèn)值s=1。

實驗主要分為兩個部分，第一部分利用多次交叉驗證的思想，先使用DEC算法對多標(biāo)記數(shù)據(jù)集進(jìn)行維度約簡，然后分別采用MLKNN和MLNB分類，進(jìn)行多次驗證，對比未使用DEC算法直接分類的結(jié)果。第二部分將基于DEC算法的多標(biāo)記學(xué)習(xí)與其他多標(biāo)記維度約簡方法PCA、MLKNN、MDDM[16]、PMU[17]等對比。為了便于對比，在DEC算法作降維處理前，先對數(shù)據(jù)集做兩折離散化處理。

4.3 多次交叉驗證結(jié)果與分析

為了分析DEC算法在多標(biāo)記學(xué)習(xí)中的性能，實驗采取多次驗證。一個交叉驗證是將樣本數(shù)據(jù)集分成訓(xùn)練集和測試集兩個互補(bǔ)的子集，然而訓(xùn)練和測試比例每次不同的劃分結(jié)果，都會導(dǎo)致實驗性能的差異。為了降低交叉驗證結(jié)果的差異，對每個數(shù)據(jù)集做多次不一樣的劃分，得到不一樣比例的互補(bǔ)子集，然后做多次驗證，即訓(xùn)練集與測試集分別按照9∶1、8∶2、7∶3、6∶4、5∶5的比例進(jìn)行實驗，最終實驗結(jié)果則選擇了多次驗證的均值。

表2分別給出在Arts，Health，Entertainment，Computers和Reference數(shù)據(jù)集上的算法實驗結(jié)果。緊隨每個評價指標(biāo)之后的“↑”表示該評價指標(biāo)取值越大，實驗效果越好；“↓”則表示該評價指標(biāo)取值越小，實驗效果越好。表格中斜體加粗的數(shù)字則表示算法對數(shù)據(jù)集分類處理的效果更佳。

表2 不同數(shù)據(jù)集下算法分類性能對比

由表2可以看出，處理Arts數(shù)據(jù)集時，在分類之前利用DEC算法對多標(biāo)記數(shù)據(jù)進(jìn)行維度約簡，再利用MLKNN進(jìn)行分類處理，實驗結(jié)果所得的5個多標(biāo)記學(xué)習(xí)評價指標(biāo)值都明顯優(yōu)于未使用DEC約簡的分類結(jié)果。因此，基于DEC算法的多標(biāo)記分類比MLKNN直接分類的效果更佳。利用MLNB算法進(jìn)行多標(biāo)記分類處理之前，如果先采取DEC算法對數(shù)據(jù)集進(jìn)行維度約簡，則AP、CO、HL這3個評價指標(biāo)都明顯優(yōu)于未采取DEC算法的分類結(jié)果。由此可以得出，在處理諸如上述多標(biāo)記數(shù)據(jù)集時，由DEC算法約簡之后再分類，最終可以取得相對不錯的實驗結(jié)果。

4.4 多標(biāo)記學(xué)習(xí)算法性能比較

該實驗與5種多標(biāo)記維數(shù)約簡算法PCA、MLKNN、MDDMspc[16]、MDDMproj[16]以及PMU比較，同時以PMU離散化為標(biāo)準(zhǔn)，本次實驗在進(jìn)行特征降維前對數(shù)據(jù)進(jìn)行了兩折離散化處理。該實驗訓(xùn)練MLKNN分類器處理約簡后的數(shù)據(jù)集，同時選取AP、HL、RL、OE 4個評價指標(biāo)評估實驗結(jié)果。表3給出基于4個評價指標(biāo)的算法分類性能對比，表格中斜體加粗的數(shù)字則表示算法對數(shù)據(jù)集分類處理的效果更佳，僅加粗的數(shù)字表示在對比算法中性能居于第二。

由表3可以看出，PCA算法僅在OE這一個評價指標(biāo)占據(jù)優(yōu)勢，而從其他評價指標(biāo)來看，PCA效果遠(yuǎn)遠(yuǎn)不及其他算法。在AP這一指標(biāo)上，基于DEC的多標(biāo)記學(xué)習(xí)算法（表3中將此算法表示為MLDEC）要明顯優(yōu)于其他5個算法；HL的取值僅在處理Entertainment這一數(shù)據(jù)集的實驗對比結(jié)果不是很好；RL也只是處理Reference數(shù)據(jù)集的實驗性能不及PMU算法。從評價指標(biāo)OE可以看出，本文算法結(jié)果雖不如PCA，但卻優(yōu)于MLKNN、MDDMproj以及PMU等。因此，根據(jù)以上分析可得，基于DEC算法的多標(biāo)記學(xué)習(xí)的實驗結(jié)果整體較優(yōu)，換句話說，DEC算法在多標(biāo)記學(xué)習(xí)中的應(yīng)用是可行的。

表3 各評價指標(biāo)下算法分類性能對比

5 總結(jié)

本文提出的基于DEC算法的多標(biāo)記學(xué)習(xí)，即首先采取判別嵌入式聚類（DEC）算法對多標(biāo)記數(shù)據(jù)集進(jìn)行降維處理，對降維后的數(shù)據(jù)再采取MLKNN和MLNB多標(biāo)記分類方法進(jìn)行分類處理。與未采取DEC算法的多標(biāo)記分類以及其他多標(biāo)記維度約簡算法對比結(jié)果表明，基于DEC算法的多標(biāo)記學(xué)習(xí)在一定程度上提升了多標(biāo)記數(shù)據(jù)的分類性能，但是，對不同的多標(biāo)記數(shù)據(jù)集，采取DEC算法作維度約簡處理時，數(shù)據(jù)集約簡的維數(shù)以及聚類的類別數(shù)目會影響最終的分類性能。因此，下一步研究計劃提出一種能自動計算出最恰當(dāng)?shù)木垲悢?shù)和約簡維數(shù)的算法，從而使分類器性能達(dá)到最優(yōu)。

[1]MITCHELL T M.Machine learning[D].New York:McGraw-Hill,1997.

[2]范明,孟小峰.數(shù)據(jù)挖掘概念與技術(shù)[M].北京:機(jī)械工業(yè)出社,2012:48.

[3]徐勇,陳亮.一種基于降維思想的K均值聚類[J].湖南城市學(xué)院學(xué)報,2017,26(1):55-61.

[4]師黎,楊振興,王治忠,等.基于PCA和改進(jìn)K均值算法的動作電位分類[J].計算機(jī)工程,2011,37(16):182-184.

[5]潘巍,周曉英,吳立峰,等.基于半監(jiān)督K-Means的屬性加權(quán)聚類算法[J].計算機(jī)應(yīng)用與軟件,2017,34(3):190-193.

[6]DELA T F,KABADE T.Discriminative c1uster analysis[C].International Conference on Machine Learning,New York:ACM,2006:241-248.

[7]HOU C P,NIE F P,TAO D C.Discriminative embeded clustering:A general framework for grouping high dimensional data[J].IEEE Transactions on Neural Networks&Learning Systems,2015,26(6):1287-1299.

[8]ZHANG M L,ZHOU Z H.A review on multi-label learning algorithms[J].IEEE Trans on Knowledge and Data Engineering,2014,26(8):1819-1837.

[9]余鷹,多標(biāo)記學(xué)習(xí)研究綜述[J].計算機(jī)工程與應(yīng)用,2015,51(17):20-27.

[10]燕凱.多標(biāo)記維度約簡和分類算法研究[D].重慶:重慶大學(xué),2014.

[11]盧桂馥,鄒健,陳富春.一種求解MMC的快速算法[J].安徽工程大學(xué)學(xué)報,2014,29(4):57-62.

[12]支曉斌,燕華芳.改進(jìn)的判別嵌入式聚類算法[J].西安郵電大學(xué)學(xué)報,2017,22(1):34-37.

[13]劉景華,林夢雷,王晨曦,等.基于局部子空間的多標(biāo)記特征選擇算法[J].模式識別與人工智能,2016,29(3):240-251.

[14]ZHANG M L,ZHOU Z H.ML-kNN:a lazy learning approach to multi-label learning[J].Pattern Recognition,2007,40(7):2038-2048.

[15]ZHANG M L,ROBLES V.Feature selection for multi-label naive bayes classification[J].Information Sciences,2009,179:3218-3229.

[16]ZHANG Y,ZHOU Z H.Multi-label dimensionality reduction via dependency maximization[J].ACM Transactions on Knowledge Discovery from Data,2010,4(3):14-24.

[17]LEE J,KIM D W.Mutual information-based multi-label feature selection using interaction information[J].Expert Systems withApplications,2015,42(4):2013-2025.