程大勇

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

0 引言

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

1 基于k近鄰法的多標簽分類算法概述

1.1 基本原理

假設存在獨立同分布的訓練樣本集為:

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

(1)

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

1.1.1基于k近鄰法的多標簽分類算法[5]

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

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

(2)

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

1.1.2k近鄰法的多標簽分類流程

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

圖1 k近鄰多標簽算法測試階段流程圖

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

1.2 樣本距離計算方法概述

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

1.2.1歐氏距離

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

(3)

1.2.2余弦距離

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

(4)

因為直接計算內(nèi)積,強度低,誤差較大,適用于文本分類中。

1.2.3曼哈頓距離

曼哈頓距離用以標明兩個點在標準坐標系上的絕對軸距總和,定義的公式為

(5)

1.3 算法評價的準則

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

1.3.1基于樣本的評價準則

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

1.3.2基于排序的評價準則

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

1.3.3基于標簽的評價準則

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

2 實驗結果與分析

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

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

2.2 5種算法性能分析

為了比較5種后處理算法的性能差異,采用歐氏距離計算樣本之間的距離,分別對3個數(shù)據(jù)集(yeast,image135,scene)的數(shù)據(jù)進行測試。其中,k值過小,整體模型變得復雜,估計誤差較大,容易出現(xiàn)過擬合;k值過大,近似誤差較大,預測結果可信度較低,所以實驗中將k值設為經(jīng)驗值10。為了清晰顯示各算法之間的差異,將k/2法作為基準,將其設為1,其他算法的評價值分別與k/2法中的各個評價值相除,得到相對改進量。對于值越大越好的標準,值大于1則表示有改進;對于值越小越好的指標,值小于1表示有改進。如圖1所示,在yeast數(shù)據(jù)集上(圖2),可以發(fā)現(xiàn)離散bayes法、多輸出線性回歸以及l(fā)ogistic回歸法都有不錯的表現(xiàn),其中l(wèi)ogistic回歸法的性能最優(yōu),而線性閾值函數(shù)法的各項指標值都不是很好。原因可能是用最小平法誤差法估計系數(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近鄰的多標簽算法中,選擇的k個近鄰對于尋找未知樣本的所屬標簽有非常重要的影響。尋找的k個近鄰與未知樣本特征越相近,預測的準確性就越高。目前比較常用的計算k近鄰的方法有:歐氏距離、曼哈頓距離以及余弦距離。為了比較不同距離對算法性能的影響,在yeast數(shù)據(jù)集上計算5種算法在hamming-loss,ranking-loss,macro-precision,micro-precision指標的值,比較它們的時間性能差異。

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

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

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

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

3 結論

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

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種距離的時間性能差異明顯,歐氏距離時間性能最好,余弦距離最差。