程大勇

(安徽工業(yè)職業(yè)技術(shù)學(xué)院 信息工程系,安徽 銅陵 244000)

0 引言

多標(biāo)簽分類作為分類問題中的一種,在現(xiàn)實(shí)生活中廣泛存在。目前,多標(biāo)簽分類問題的算法有兩大類[1]:一類是基于數(shù)據(jù)集分解的方法,將多標(biāo)簽分類問題分解成多個單標(biāo)簽分類問題,通過處理這些單標(biāo)簽分類問題最終得到多標(biāo)簽分類問題的解[2];另一類是基于單個優(yōu)化問題的方法,通過對一般的多類分類算法進(jìn)行改造,完成能夠直接處理多標(biāo)簽分類問題的任務(wù)[3]。k近鄰法是模式識別中比較常用的分類方法,與一般分類算法需要訓(xùn)練分類器模型不同,它通過計算樣本之間的距離,結(jié)合已知樣本類別投票來決定新樣本的類別[4]?；趉近鄰的多標(biāo)簽分類算法是對基本k近鄰算法的直接擴(kuò)展,可以直接用于多標(biāo)簽分類問題[5]。本文利用k近鄰的多標(biāo)簽分類算法訓(xùn)練已知樣本,使用k/2法、Bayes法、Logistic回歸法、線性閾值函數(shù)法以及多輸出線性回歸法5種方法進(jìn)行后處理并作進(jìn)一步的比較研究。為了比較不同情況下各類算法的性能差異,實(shí)驗(yàn)中將測試歐氏、曼哈頓和余弦等3種距離,同時會使用酵母(Yeast)、圖像(Image)和基因(Scene)3種類型的數(shù)據(jù)集進(jìn)行測試,以求準(zhǔn)確分析出不同算法的適用情景以及不同算法之間的差異。

1 基于k近鄰法的多標(biāo)簽分類算法概述

1.1 基本原理

假設(shè)存在獨(dú)立同分布的訓(xùn)練樣本集為:

{(x1,y1),…,(xi,yi),…,(xl,yl)}

(1)

式中:xi∈Rd是d維的特征向量。Q={1,2,…,c}是類標(biāo)簽集(c是類別總數(shù))。對于經(jīng)典的多類問題,yi只能取Q中的一個類別號,而對于多標(biāo)簽問題,yi可能取Q中的若干類別(即一個標(biāo)簽相關(guān)子集)。

1.1.1基于k近鄰法的多標(biāo)簽分類算法[5]

傳統(tǒng)的k近鄰法主要針對單標(biāo)簽分類,多標(biāo)簽分類則需要對算法進(jìn)行兩方面的改造:1)將多標(biāo)簽樣本看成同時屬于多個不分主次的類別,在計算判別函數(shù)時,給不同的類別計算近鄰樣本數(shù)。2)需要增加一個后處理的學(xué)習(xí)算法來確定樣本的相關(guān)標(biāo)簽。對于某一待分類樣本x,同樣先尋找其k個近鄰樣本。由于現(xiàn)在近鄰樣本都可能包含多個標(biāo)簽,故將判別函數(shù)定義為：

gi(x)=| {j|i∈yj′,j=1,…,k}|,i=1,…,c

(2)

即計算在k個近鄰中第i個類標(biāo)簽出現(xiàn)的次數(shù)。

1.1.2k近鄰法的多標(biāo)簽分類流程

多標(biāo)簽分類主要分為兩個階段:訓(xùn)練階段和測試階段。在訓(xùn)練階段,需要對數(shù)據(jù)進(jìn)行預(yù)處理,即利用留一法,通過歐氏距離(曼哈頓距離、余弦距離)計算訓(xùn)練樣本的k個近鄰,統(tǒng)計每一類標(biāo)簽的得票數(shù),從而將原始訓(xùn)練數(shù)據(jù)集轉(zhuǎn)化成一個新的數(shù)據(jù)集,再將轉(zhuǎn)化得到的新的數(shù)據(jù)集用于5種后處理算法模型中進(jìn)行訓(xùn)練。在測試階段,也需要按照訓(xùn)練階段的數(shù)據(jù)集轉(zhuǎn)化方法對原始測試數(shù)據(jù)集進(jìn)行轉(zhuǎn)化,再將轉(zhuǎn)化好的數(shù)據(jù)集代入已經(jīng)訓(xùn)練好的模型,得出新的準(zhǔn)則函數(shù)預(yù)測測試樣本的標(biāo)簽集,并且計算各項評價指標(biāo)。具體的流程如圖1所示。

圖1 k近鄰多標(biāo)簽算法測試階段流程圖

為了建立確定x的相關(guān)標(biāo)簽集的后處理模型,本文收集與編程4種學(xué)習(xí)方法:離散Bayes方法、線性閾值法、多輸出線性回歸法與Logistic回歸法,而且對各個算法進(jìn)行訓(xùn)練與測試。

1.2 樣本距離計算方法概述

為了對原始數(shù)據(jù)集進(jìn)行轉(zhuǎn)化,需要計算每個樣本的k個近鄰,也即計算每個樣本到其他樣本的距離。

1.2.1歐氏距離

歐氏距離[6]描述的是在d維空間中兩點(diǎn)的真實(shí)距離,設(shè)x=(x1,x2,…,xd)T和y=(y1,y2,…,yd)T之間的距離D(x,y)定義為式(3)

(3)

1.2.2余弦距離

余弦距離的值介于0～1之間,描述的是兩個向量之間的夾角,定義的公式為：

(4)

因?yàn)橹苯佑嬎銉?nèi)積,強(qiáng)度低,誤差較大,適用于文本分類中。

1.2.3曼哈頓距離

曼哈頓距離用以標(biāo)明兩個點(diǎn)在標(biāo)準(zhǔn)坐標(biāo)系上的絕對軸距總和,定義的公式為

(5)

1.3 算法評價的準(zhǔn)則

多標(biāo)簽分類算法的評價準(zhǔn)則與一般的單標(biāo)簽分類系統(tǒng)有所不同。在單標(biāo)簽系統(tǒng)中常用的評價準(zhǔn)則包括精度、準(zhǔn)確度、recall以及F measure。在多標(biāo)簽分類系統(tǒng)中,評價的準(zhǔn)則變得更加復(fù)雜。本文中將采用3種類型(基于排序、基于樣本、基于標(biāo)簽)的評價準(zhǔn)則對實(shí)驗(yàn)的數(shù)據(jù)做評價,以求更加全面準(zhǔn)確的分析實(shí)驗(yàn)結(jié)果和算法性能。

1.3.1基于樣本的評價準(zhǔn)則

Hamming損失(Hamming Loss):評價樣本標(biāo)簽對錯分的次數(shù);召回率(Recall):對于一個樣本來說,指它的真實(shí)標(biāo)簽有多少被正確預(yù)測出來,評價的是預(yù)測結(jié)果的全面性,也即查全率,該值在0～1之間,值越大,性能愈好;精度(Presicion): 對于一個樣本來說,指它預(yù)測的準(zhǔn)確性,也即預(yù)測出來的標(biāo)簽中有幾個是正確的,該值在0～1之間,值越大,性能愈好;正確率(Accuracy):評價的是預(yù)測正確的樣本在整個樣本集中所占的比例。該值在0～1之間,值越大,性能愈好;子集正確率(Subset Accuracy):是嚴(yán)格的評價準(zhǔn)則,它要求預(yù)測的標(biāo)簽集與樣本的實(shí)際標(biāo)簽完全相同。該值在0～1之間,值越大越好;F度量(F measure):它是召回率和精度的調(diào)和平均,該值在0～1之間,值越大越好。

1.3.2基于排序的評價準(zhǔn)則

錯誤率(One Error):評價預(yù)測出的樣本標(biāo)簽排序最靠前的標(biāo)簽不屬于樣本實(shí)際標(biāo)簽的的次數(shù)。該評價為0,表明分類的結(jié)果是最好的,該指標(biāo)的值越小,預(yù)測效果越好;覆蓋率(Coverage):評價對于預(yù)測出的標(biāo)簽排序,要將樣本的所有實(shí)際標(biāo)簽都包含進(jìn)去至少需要幾個標(biāo)簽。這個值越小,預(yù)測效果越好;排序損失(Ranking Loss):評價的是相關(guān)標(biāo)簽排在不相關(guān)標(biāo)簽之后的次數(shù)。當(dāng)排序是完美時,它的值為0。值越小,預(yù)測效果越好;平均精度(Average Precision):評價的是樣本實(shí)際標(biāo)簽排序的平均分?jǐn)?shù)。

1.3.3基于標(biāo)簽的評價準(zhǔn)則

Accuracy,Roc曲線下面的區(qū)域AUC,precision和recall在兩類評價中經(jīng)常使用。對所有標(biāo)簽計算這些評價值可以獲得兩類操作符,稱作macro averaging和micro averaging。這些方法在信息查詢?nèi)蝿?wù)中會考慮平均的accuracy,recall,F measure。

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

2.1 數(shù)據(jù)來源

實(shí)驗(yàn)數(shù)據(jù)分別為3組不同類型的數(shù)據(jù)集,包括yeast,image135和scene。yeast數(shù)據(jù)集包括訓(xùn)練樣本1 500個,測試樣本917個,樣本最多包含103個特征值,共有14個標(biāo)簽,每個樣本平均擁有4個標(biāo)簽;image135數(shù)據(jù)集共有1 200個訓(xùn)練樣本,800個測試樣本,135個特征向量維數(shù),5個類別,每個樣本平均擁有1.3個標(biāo)簽;scene數(shù)據(jù)集也是圖像數(shù)據(jù)集,包括1 211個訓(xùn)練樣本,1 196個測試樣本,294個特征向量,6個類別,樣本平均標(biāo)簽1個。

2.2 5種算法性能分析

為了比較5種后處理算法的性能差異,采用歐氏距離計算樣本之間的距離,分別對3個數(shù)據(jù)集(yeast,image135,scene)的數(shù)據(jù)進(jìn)行測試。其中,k值過小,整體模型變得復(fù)雜,估計誤差較大,容易出現(xiàn)過擬合;k值過大,近似誤差較大,預(yù)測結(jié)果可信度較低,所以實(shí)驗(yàn)中將k值設(shè)為經(jīng)驗(yàn)值10。為了清晰顯示各算法之間的差異,將k/2法作為基準(zhǔn),將其設(shè)為1,其他算法的評價值分別與k/2法中的各個評價值相除,得到相對改進(jìn)量。對于值越大越好的標(biāo)準(zhǔn),值大于1則表示有改進(jìn);對于值越小越好的指標(biāo),值小于1表示有改進(jìn)。如圖1所示,在yeast數(shù)據(jù)集上(圖2),可以發(fā)現(xiàn)離散bayes法、多輸出線性回歸以及l(fā)ogistic回歸法都有不錯的表現(xiàn),其中l(wèi)ogistic回歸法的性能最優(yōu),而線性閾值函數(shù)法的各項指標(biāo)值都不是很好。原因可能是用最小平法誤差法估計系數(shù)的過程中,可能出現(xiàn)奇異矩陣。 而在image135數(shù)據(jù)集上(圖3),線性閾值函數(shù)法比在yeast數(shù)據(jù)集上表現(xiàn)優(yōu)越很多,相反,logistic回歸法表現(xiàn)的卻不是很好,bayes法和多輸出線性回歸表現(xiàn)相近。在scene數(shù)據(jù)集上(圖4),5種算法的性能沒有太大差異,相對較好的是Bayes法,相對較差的是線性閾值函數(shù)法和Logistic回歸。

圖2 yeast數(shù)據(jù)集5種算法性能比較圖

圖3 image135數(shù)據(jù)集5種算法性能比較圖

圖4 scene數(shù)據(jù)集5種算法性能比較圖

2.3 距離對算法性能的影響

在基于k近鄰的多標(biāo)簽算法中,選擇的k個近鄰對于尋找未知樣本的所屬標(biāo)簽有非常重要的影響。尋找的k個近鄰與未知樣本特征越相近,預(yù)測的準(zhǔn)確性就越高。目前比較常用的計算k近鄰的方法有:歐氏距離、曼哈頓距離以及余弦距離。為了比較不同距離對算法性能的影響,在yeast數(shù)據(jù)集上計算5種算法在hamming-loss,ranking-loss,macro-precision,micro-precision指標(biāo)的值,比較它們的時間性能差異。

由圖5分析可得,不同算法的3種不同距離對算法性能的影響不是特別明顯,但存在一定影響。對k/2法而言,余弦距離的性能最好;對Bayes法而言,曼哈頓距離性能最好;對線性閾值函數(shù)法而言,歐氏距離和曼哈頓距離一樣好;對多輸出線性回歸而言,曼哈頓距離最好;對Logistic回歸法而言,歐氏距離最好。同時,采用歐氏距離進(jìn)行多標(biāo)簽分類時,Logistic回歸法性能最好;采用曼哈頓和余弦距離進(jìn)行多標(biāo)簽分類時,離散Bayes法性能最好。因此相同的距離計算方法在不同的算法上效果不同,相同的算法不同的距離計算方法性能也有差異。

圖5 各個算法的3種距離比較圖

此外,3種距離因其計算的復(fù)雜度,在時間性能上存在明顯的差異。由圖6可得,相同算法下,3種距離的時間性能差異明顯,歐氏距離時間性能最好,余弦距離最差。

圖6 不同數(shù)據(jù)集對LORM時間性能的影響

3 結(jié)論

通過5種基于k近鄰的多標(biāo)簽分類算法性能比較分析,發(fā)現(xiàn)每個都具有比較好的分類性能,并且具有一定的推廣能力。結(jié)論如下:

1)在yeast數(shù)據(jù)集上,logistic回歸法的性能最優(yōu),線性閾值函數(shù)法最差;在image135數(shù)據(jù)集上,線性閾值函數(shù)法性能最優(yōu),logistic回歸法性能較差;在scene數(shù)據(jù)集上, Bayes法性能最優(yōu),線性閾值函數(shù)法和Logistic回歸較差;

2)不同算法的3種不同距離對算法性能的影響不是特別明顯;

3)相同算法下,3種距離的時間性能差異明顯,歐氏距離時間性能最好,余弦距離最差。