蔣偉東,黃 睿
上海大學(xué) 通信與信息工程學(xué)院,上海 200444
多標(biāo)簽分類針對(duì)具有多個(gè)類別標(biāo)簽的實(shí)例進(jìn)行類別劃分,是數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)之一,已在文本分類、信息檢索、生物信息提取等方面獲得廣泛應(yīng)用[1-3]。與單標(biāo)簽分類一樣,多標(biāo)簽分類也會(huì)因標(biāo)記樣本有限而受到維數(shù)災(zāi)難問(wèn)題的影響,導(dǎo)致分類器性能降低。通過(guò)多標(biāo)簽特征選擇技術(shù)降低數(shù)據(jù)維數(shù),可有效提高分類器性能。
相對(duì)于傳統(tǒng)單標(biāo)簽特征選擇,多標(biāo)簽數(shù)據(jù)的特征選擇更加復(fù)雜。張振海等提出基于信息熵的多標(biāo)簽特征選擇算法,通過(guò)計(jì)算每個(gè)特征與標(biāo)簽間的信息增益關(guān)系以及設(shè)置信息增益閾值,剔除不相關(guān)特征,得到最佳特征子集[4]。文獻(xiàn)[5]則是在原始的信息增益多標(biāo)簽算法基礎(chǔ)上引入標(biāo)簽間的相關(guān)性以實(shí)現(xiàn)特征重要度排序。文獻(xiàn)[6]提出一種融合特征排序的多標(biāo)記特征選擇算法,首先在標(biāo)簽下自適應(yīng)粒化樣本,構(gòu)造特征與標(biāo)簽間鄰域關(guān)系并進(jìn)行排序,最后通過(guò)聚類融合形成新的特征排序。對(duì)已有單標(biāo)簽特征選擇算法進(jìn)行改造應(yīng)用于多標(biāo)簽數(shù)據(jù)也是一種可行的方法。如:文獻(xiàn)[7]通過(guò)對(duì)多標(biāo)簽數(shù)據(jù)相關(guān)性與特征權(quán)值的分析,提出基于ReliefF的多標(biāo)簽特征選擇(Multi-Label ReliefF,ML-ReliefF);Spolaor等提出基于Label Powerset處理方式的信息增益算法(Information Gain-Label Powerset,IG-LP),通過(guò)考慮不同的標(biāo)簽組合,將多標(biāo)簽直接轉(zhuǎn)換為單標(biāo)簽,之后采用信息增益算法衡量每個(gè)特征與標(biāo)簽間的相關(guān)度[8]。Chang等提出一種凸半監(jiān)督多標(biāo)簽特征選擇算法(Convex Semisupervised multi-label Feature Selection,CSFS),通過(guò)最小化最小二乘損失函數(shù)進(jìn)行稀疏特征選擇,可用于大規(guī)模數(shù)據(jù)集[9]。Ma等提出基于多標(biāo)簽學(xué)習(xí)的稀疏特征選擇算法(Sub-Feature Uncovering with Sparsity,SFUS),一方面通過(guò)稀疏空間選擇出最具有辨別力的特征,同時(shí)也考慮不同標(biāo)簽間的相關(guān)性[10]。Alalga等將不同樣本的類別標(biāo)簽相似性定義為軟約束,并用以修正鄰接矩陣,提出一種半監(jiān)督的軟約束Laplacian Score(Soft-Constrained Laplacian Score,S-CLS)[11]。
在多標(biāo)簽數(shù)據(jù)分類中,樣本的類別標(biāo)簽通常為邏輯型,即若樣本屬于該類別則置為“1”,否則置為“0”。這樣的表示方法沒(méi)有考慮到不同類別標(biāo)簽對(duì)于同一樣本的重要性往往是不同的。Hou等利用流形學(xué)習(xí)思想對(duì)類別標(biāo)簽的重要性進(jìn)行量化,將邏輯型類別標(biāo)簽映射為數(shù)值型類別標(biāo)簽[12]。受此啟發(fā),本文提出一種基于流形學(xué)習(xí)的約束Laplacian分值多標(biāo)簽特征選擇方法(Manifold-based Constraint Laplacian Score,M-CLS)。方法首先從數(shù)據(jù)空間對(duì)特征進(jìn)行評(píng)分,利用邏輯型類別標(biāo)簽間的相似性修正Laplacian分值;接著在標(biāo)簽空間通過(guò)流形學(xué)習(xí)將邏輯型類別標(biāo)簽映射為數(shù)值型類別標(biāo)簽,并計(jì)算相應(yīng)的Laplacian分值;兩種分值之積為最終的特征分值。實(shí)驗(yàn)結(jié)果表明,所提M-CLS方法能提取出更有效的特征子集,獲得更好的多標(biāo)簽分類性能。
對(duì)于單標(biāo)簽數(shù)據(jù),樣本間的關(guān)系可以直接劃分為同類和異類。但對(duì)于多標(biāo)簽數(shù)據(jù),由于每個(gè)樣本都具有多個(gè)類別標(biāo)簽,需要衡量不同樣本間類別標(biāo)簽的相似性。定義樣本xi與xj的邏輯型類別標(biāo)簽的相似性為:
其中,δ(?)為狄拉克函數(shù),有:
在此基礎(chǔ)上定義特征空間鄰接矩陣如下:
其中,t為可調(diào)參數(shù)。對(duì)于第n個(gè)特征 fn(1≤n≤N),特征空間的約束Laplacian分值定義為[13]:
在多標(biāo)簽數(shù)據(jù)分類中,邏輯型的類別標(biāo)簽無(wú)法反映出實(shí)例所具有的不同標(biāo)簽的重要度。利用流形學(xué)習(xí)思想,將邏輯型標(biāo)簽轉(zhuǎn)化為數(shù)值型,通過(guò)標(biāo)簽的實(shí)值體現(xiàn)不同類別標(biāo)簽的相對(duì)重要性[12]。根據(jù)平滑假設(shè)(即相鄰的點(diǎn)很可能屬于同一類別)[14],特征空間的拓?fù)浣Y(jié)構(gòu)可以傳遞到類別標(biāo)簽的數(shù)值空間。通過(guò)極小化下式得到特征流形結(jié)構(gòu):
若 xj不是xi的近鄰,則將置為0。通過(guò)求解最小二乘問(wèn)題獲得ψ。定義與邏輯型標(biāo)簽對(duì)應(yīng)的實(shí)值標(biāo)簽為zi∈RC。在獲得數(shù)據(jù)特征空間的流形結(jié)構(gòu)后,類別標(biāo)簽的流形結(jié)構(gòu)表示為:
在給定ψ的前提下極小化上式,獲得實(shí)值標(biāo)簽z。實(shí)值標(biāo)簽一方面反映了同一實(shí)例具有的不同類別標(biāo)簽的重要度差異,另一方面也體現(xiàn)了同一類別標(biāo)簽對(duì)不同實(shí)例的重要度差異。
在此基礎(chǔ)上,定義標(biāo)簽空間的鄰接矩陣如下:
其中,dmax和dmin分別為實(shí)值標(biāo)簽間的最大和最小歐式距離。對(duì)于第n個(gè)特征 fn(1≤n≤N),實(shí)值標(biāo)簽空間的Laplacian分值定義為:
結(jié)合式(4)和(8),對(duì)于第 n個(gè)特征 fn(1≤n≤N),基于流形的約束Laplacian分值定義如下:
下面對(duì)M-CLS的流程進(jìn)行了總結(jié):
輸入:數(shù)據(jù)集X,多標(biāo)簽集Y,近鄰數(shù)k
輸出:每個(gè)特征的M-CLS分值
1.根據(jù)式(1)、(2)、(3)計(jì)算特征空間的約束鄰接矩陣SF,并以此計(jì)算DF和LF。
2.根據(jù)式(7)計(jì)算數(shù)值型標(biāo)簽空間的鄰接矩陣SL,并以此計(jì)算DL和LL。
ford=1∶D
3.根據(jù)式(4)、(8)、(9)計(jì)算每個(gè)特征的M-CLS分值。
end
4.對(duì)特征按M-CLS值排序。
為驗(yàn)證所提算法M-CLS的性能,在多標(biāo)簽數(shù)據(jù)集Recreation和Yeast上進(jìn)行了特征選擇與分類實(shí)驗(yàn),并與4種多標(biāo)簽特征選擇算法IG-LP、CSFS、SFUS和ML-ReliefF的實(shí)驗(yàn)結(jié)果進(jìn)行比較。分類器為ML-KNN[15],近鄰數(shù)k設(shè)為10。采用漢明損失(Hamming Loss),排序損失(Ranking Loss),1-錯(cuò)誤率(One Error),覆蓋長(zhǎng)度(Coverage)和預(yù)測(cè)精度(Precision)這5個(gè)性能評(píng)價(jià)指標(biāo)進(jìn)行性能評(píng)價(jià)[16],其中,前4個(gè)指標(biāo)與預(yù)測(cè)精度相反,值越小表示分類效果越好。表1給出了所用數(shù)據(jù)集的具體描述。
表1 實(shí)驗(yàn)所用數(shù)據(jù)集
表2、3分別列出了不同特征選擇方法在數(shù)據(jù)集Recreation和Yeast上的分類結(jié)果。此外,還給出了采用全部特征時(shí)的分類性能指標(biāo),作為比較基準(zhǔn)。可以看到,所提算法的5個(gè)指標(biāo)與其他特征選擇方法相比不但具有明顯優(yōu)勢(shì);而且也優(yōu)于采用特征全集時(shí)的性能指標(biāo)。圖1進(jìn)一步給出了不同方法對(duì)于Recreation數(shù)據(jù)選擇不同特征數(shù)時(shí)的性能指標(biāo),橫坐標(biāo)為所選特征數(shù),縱坐標(biāo)為參數(shù)值,可以看到,特征選擇方法的性能并沒(méi)有隨著特征數(shù)的增多而逐漸提升,而是存在明顯起伏,這在M-CLS上表現(xiàn)的尤為突出。M-CLS在選擇較少特征數(shù)時(shí)體現(xiàn)出更好的性能,說(shuō)明此方法在特征子集規(guī)模相同情況下能選擇出更有效的特征構(gòu)成子集。
表2 不同方法在Recreation數(shù)據(jù)集上的性能比較
表3 不同方法在Yeast數(shù)據(jù)集上的性能比較
圖1 Recreation數(shù)據(jù)集分類結(jié)果對(duì)比
表4、5列出了兩個(gè)數(shù)據(jù)集采用不同方法進(jìn)行特征評(píng)分時(shí),所選出的最重要特征??梢钥吹?,不同特征選擇方法選擇出的最重要特征均不同。本文所提算法MCLS在Recreation、Yeast數(shù)據(jù)集上選擇出的最重要特征編號(hào)分別為Att493、Att34。
表4 不同方法在Recreation數(shù)據(jù)集上所選特征比較
表5 不同方法在Yeast數(shù)據(jù)集上所選特征比較
提出一種基于流形學(xué)習(xí)的約束Laplacian分值多標(biāo)簽特征選擇方法M-CLS。本文方法首先在特征空間利用邏輯型類別標(biāo)簽的相似性對(duì)鄰接矩陣進(jìn)行改進(jìn),定義了約束Laplacian分值;接著基于流形學(xué)習(xí)將邏輯型類別標(biāo)簽映射為數(shù)值型類別標(biāo)簽,在實(shí)值標(biāo)簽空間定義新的鄰接矩陣,由此定義Laplacian分值;最后將兩種分值相乘獲得最終的特征評(píng)分。實(shí)驗(yàn)結(jié)果表明,本文算法M-CLS能選擇出更有效的特征構(gòu)成子集,性能優(yōu)于多種多標(biāo)簽特征選擇方法。