一種基于關(guān)聯(lián)規(guī)則的MLKNN多標(biāo)簽分類算法*

楊嵐雁，靳 敏，張迎春，張 珣

(1.北京工商大學(xué)計算機(jī)與信息工程學(xué)院，北京 100048；2.北京工商大學(xué)信息網(wǎng)絡(luò)中心，北京 100048)

1 引言

分類算法是機(jī)器學(xué)習(xí)方法的重要內(nèi)容，能夠有效解決應(yīng)用領(lǐng)域數(shù)據(jù)的分類問題。傳統(tǒng)分類算法主要解決的是單標(biāo)簽分類問題，然而隨著信息技術(shù)的發(fā)展，多標(biāo)簽分類已經(jīng)成為分類問題中不可或缺的一部分，在現(xiàn)實(shí)生活中多標(biāo)簽分類[1,2]問題的應(yīng)用也變得越來越廣泛，例如，場景分類、生物信息學(xué)、多媒體自動標(biāo)記與數(shù)據(jù)挖掘等領(lǐng)域的應(yīng)用。在多標(biāo)簽分類問題中，標(biāo)簽之間存在著一定的關(guān)聯(lián)性，若忽略標(biāo)簽之間的關(guān)系，則會損失標(biāo)簽間的關(guān)聯(lián)信息。故本文采用關(guān)聯(lián)規(guī)則[3,4]算法挖掘標(biāo)簽之間的相關(guān)性，將標(biāo)簽之間的關(guān)聯(lián)規(guī)則應(yīng)用到多標(biāo)簽分類算法中進(jìn)行改進(jìn)，這樣既不改變樣本分布，又能避免標(biāo)記增多時的“維數(shù)災(zāi)難”問題。

在多標(biāo)簽研究中，主要有2類多標(biāo)簽分類算法：問題轉(zhuǎn)化法和算法轉(zhuǎn)化法。問題轉(zhuǎn)化法是將多標(biāo)簽分類問題分解為多個單標(biāo)簽分類問題，再利用傳統(tǒng)的單標(biāo)簽分類方法進(jìn)行分類，簡單易行，但這樣就忽略了多標(biāo)簽數(shù)據(jù)集的所有特性。如復(fù)制轉(zhuǎn)化CO(COpy transformation)[5]法通過直接復(fù)制樣本將多標(biāo)簽的問題轉(zhuǎn)換成多類問題，簡單易行，但是完全把多標(biāo)簽問題當(dāng)成單標(biāo)簽問題進(jìn)行求解，忽略了多標(biāo)簽數(shù)據(jù)集的所有特性。二元關(guān)聯(lián)BR(Binary Relevance)[6]算法通過將多標(biāo)簽學(xué)習(xí)問題轉(zhuǎn)化為每個標(biāo)簽獨(dú)立的二元分類問題，并為每個標(biāo)簽構(gòu)建一個獨(dú)立的分類器，每個分類器使用全部訓(xùn)練樣本進(jìn)行學(xué)習(xí)，這種算法忽略了標(biāo)簽和標(biāo)簽之間的相關(guān)性，分類準(zhǔn)確率有待提升。標(biāo)簽冪集LP(Label Power-set)算法考慮了標(biāo)簽之間的相關(guān)性，通過二進(jìn)制編碼將每個樣本可能擁有的標(biāo)簽合并成為一個新的標(biāo)簽，但是該算法會導(dǎo)致融合后的標(biāo)簽呈指數(shù)級增長，樣本不足不具備良好的泛化性。多標(biāo)簽隨機(jī)游走RAKEL(RAndom K-labELsets)算法[7]是由Tsoumakas等人提出的一種隨機(jī)選擇多個標(biāo)簽集合的子集建立LP分類器的多標(biāo)簽分類算法，為了彌補(bǔ)LP算法的短處，其在原始標(biāo)簽集中隨機(jī)選用部分標(biāo)簽子集來訓(xùn)練每個分類器。但是，由于RAKEL算法是隨機(jī)構(gòu)造標(biāo)簽空間，并未充分考慮到樣本和多個標(biāo)簽之間的相關(guān)性，從而造成分類精度不高。

算法轉(zhuǎn)化法是通過對傳統(tǒng)的分類方法進(jìn)行改進(jìn)，使其能適用于多標(biāo)簽數(shù)據(jù)的分類。該類算法主要有AdaBoost算法[8,9]、C4.5算法[10]、多標(biāo)簽K近鄰算法MLKNN(Multi-Label K-Nearest Neighbor)[11]和反向傳播多標(biāo)簽學(xué)習(xí)BPMLL(Back-Propagation for Multi-Label Learning)算法[12]等。AdaBoost算法是由Schapire等人[8]提出的一種基于迭代的多標(biāo)簽文本分類算法，其核心思想是針對同一個訓(xùn)練集訓(xùn)練不同的分類器(弱分類器)，然后把這些弱分類器集合起來，構(gòu)成一個更強(qiáng)的最終分類器(強(qiáng)分類器)。這類算法可以根據(jù)弱分類器的反饋，自適應(yīng)地調(diào)整假定的錯誤率，執(zhí)行的效率高，但在訓(xùn)練過程中會使得難于分類樣本的權(quán)值呈指數(shù)增長，導(dǎo)致算法易受噪聲干擾。此外，這類算法依賴于弱分類器，而弱分類器的訓(xùn)練時間往往很長。C4.5算法是由Quinlan[9]提出的用于產(chǎn)生決策樹的算法，該算法產(chǎn)生的分類規(guī)則易于理解且準(zhǔn)確率較高，但該算法在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進(jìn)行多次順序掃描和排序，因而導(dǎo)致算法的效率較低。MLKNN算法是Zhang[10]提出的一種基于KNN的多標(biāo)簽分類算法。該算法的基本原理是通過KNN算法尋找和樣本最近的k個樣本，然后對這k個最近鄰樣本的標(biāo)簽集進(jìn)行統(tǒng)計分析，計算出這些近鄰樣本包含各個標(biāo)簽的概率，利用最大后驗概率方法來確定當(dāng)前未知樣本的標(biāo)簽集。此算法易于理解且容易實(shí)現(xiàn)，但并未考慮標(biāo)簽之間的相關(guān)性。BPMLL算法[11]是在流行的反向傳播算法中引入了一個考慮排序損失的新誤差函數(shù)，該算法考慮標(biāo)簽兩兩之間的相關(guān)性對泛化性能有一定的幫助，但是當(dāng)現(xiàn)實(shí)中數(shù)據(jù)之間的關(guān)聯(lián)性超過二階時，此類處理方法就會受到一定的影響。

為克服現(xiàn)有技術(shù)的不足，本文提出一種基于關(guān)聯(lián)規(guī)則的MLKNN多標(biāo)簽分類算法FP-MLKNN。該算法針對多標(biāo)簽數(shù)據(jù)考慮標(biāo)簽與標(biāo)簽之間的相關(guān)性，采用關(guān)聯(lián)規(guī)則算法挖掘標(biāo)簽之間的高階相關(guān)性，用標(biāo)簽之間的關(guān)聯(lián)規(guī)則改進(jìn)MLKNN算法，并通過了算法的有效性檢驗。實(shí)驗結(jié)果表明，本文所提出的基于關(guān)聯(lián)規(guī)則的MLKNN多標(biāo)簽分類算法極大地提高了多標(biāo)簽數(shù)據(jù)分類的準(zhǔn)確性。

2 相關(guān)介紹

2.1 多標(biāo)簽問題的定義

令X={x1,x2,…,xn}表示樣本空間，L={l1,l2,…,ln}表示標(biāo)簽集合，Y={yx1,yx2,…,yxn}表示標(biāo)簽空間，對于L中的任意一項li(1≤i≤q)，都有l(wèi)i∈{0,1}，li取0時表示該標(biāo)簽為無相關(guān)標(biāo)簽，li取1時表示該標(biāo)簽為相關(guān)標(biāo)簽。給定訓(xùn)練集D={(xi,li)|1≤i≤n,xi∈X,li∈L}，多標(biāo)簽學(xué)習(xí)的目標(biāo)是從給定訓(xùn)練集D中訓(xùn)練得到一個多標(biāo)簽分類器h:X→2L，通過訓(xùn)練得到的多標(biāo)簽分類器來預(yù)測未知樣本所包含的標(biāo)簽集合。但是，在大多數(shù)情況下，多標(biāo)簽分類系統(tǒng)的輸出對應(yīng)于一個實(shí)值函數(shù)f:X×L→R，f(xi,li)為樣本xi包含標(biāo)簽li的置信度。當(dāng)給定一個樣本數(shù)據(jù)xi，若樣本xi的標(biāo)簽集yxi中包含標(biāo)簽li，則f(xi,li)的值較大；反之，f(xi,li)的值較小。多標(biāo)簽分類還可以由此函數(shù)得到：h(xi)={li|f(xi,li)>t(xi),li∈L}，其中t:X→R作為閾值函數(shù)，用來決定是否應(yīng)該將數(shù)據(jù)xi歸屬到標(biāo)簽li中。

2.2 關(guān)聯(lián)規(guī)則

基于關(guān)聯(lián)規(guī)則的分類是針對數(shù)據(jù)集挖掘頻繁模式建立分類器，實(shí)現(xiàn)對未知樣本分類的方法。相關(guān)定義如下：給定數(shù)據(jù)集D，|D|為數(shù)據(jù)集樣本總數(shù)，I={i1,i2,…,im}為所有項的集合，is和it是I中任意項集，數(shù)據(jù)集D中的關(guān)聯(lián)規(guī)則表示為蘊(yùn)含式is?it，且is?I，it?I，is∩it≠?，關(guān)聯(lián)規(guī)則的強(qiáng)度可由支持度和置信度來度量，支持度表示規(guī)則的頻度，置信度表示規(guī)則的強(qiáng)度。

規(guī)則is?it在D中的支持度是指同時包含is和it的樣本數(shù)與數(shù)據(jù)集樣本總數(shù)之比，記作：

Support(is?it)=P(is∩it)=

Freq(is∩it)/|D|

(1)

其中，F(xiàn)req(is∩it)表示同時包含is和it的樣本數(shù)。

規(guī)則is?it在D中的置信度是指同時包含is和it的樣本數(shù)與包含is的樣本數(shù)之比，記作：

Confidence(is?it)=P(is|it)=

Freq(is∩it)/Freq(is)

(2)

其中，F(xiàn)req(is)表示包含is的樣本數(shù)。

關(guān)聯(lián)規(guī)則挖掘就是在數(shù)據(jù)集D中找出支持度和置信度分別大于用戶給定的最小支持度(Minsup)和最小置信度 (Minconf)的關(guān)聯(lián)規(guī)則。當(dāng)規(guī)則的置信度和支持度分別大于Minsup和Minconf時，認(rèn)為該關(guān)聯(lián)規(guī)則是有效的，稱為強(qiáng)關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則挖掘算法主要有Apriori算法和FP-Growth算法[12]，Apriori算法效率相對較低且存在冗余模式，因此本文采用FP-Growth進(jìn)行關(guān)聯(lián)規(guī)則的挖掘，進(jìn)而得到多個標(biāo)簽之間的相關(guān)性。FP-Growth算法只需要對數(shù)據(jù)庫進(jìn)行2次掃描，通過FP-tree[14]數(shù)據(jù)結(jié)構(gòu)對原始數(shù)據(jù)進(jìn)行壓縮。

2.3 求解策略

目前，基于標(biāo)簽相關(guān)性的求解策略主要有3類：

(1)一階策略：逐一考察單個標(biāo)簽，將多標(biāo)簽分類問題轉(zhuǎn)化為多個獨(dú)立的二分類問題。此類策略將標(biāo)簽之間的關(guān)系看作是相互獨(dú)立的，彼此之間沒有任何影響，需要針對每一個類別或者一組標(biāo)簽訓(xùn)練一個分類器。雖然這類策略實(shí)現(xiàn)簡單，但是沒有考慮標(biāo)簽之間的相關(guān)性，在標(biāo)簽個數(shù)較多的時候需要訓(xùn)練很多分類器，分類效率和準(zhǔn)確率可能不是最優(yōu)。

(2)二階策略：考察標(biāo)簽兩兩之間的相關(guān)性(例如相關(guān)標(biāo)簽與無關(guān)標(biāo)簽之間的排序關(guān)系等)，此策略在一定程度上考慮了標(biāo)簽之間的相關(guān)性，對泛化性能有一定的幫助，但是當(dāng)現(xiàn)實(shí)中數(shù)據(jù)之間的關(guān)聯(lián)性超過二階時，此類策略就會受到一定的影響，且在標(biāo)簽規(guī)模較大時需要考慮的兩兩標(biāo)簽的相關(guān)性將變得非常多。

(3)高階策略：此類策略考慮了標(biāo)簽之間的高階相關(guān)性，對每一類標(biāo)簽，需要考慮標(biāo)簽集中其他標(biāo)簽對其的影響。該類策略可以較好地反映真實(shí)世界問題的標(biāo)簽相關(guān)性，并且相對于以上2類標(biāo)簽相關(guān)性建模方式有更強(qiáng)的建模能力。關(guān)聯(lián)規(guī)則可以發(fā)現(xiàn)標(biāo)簽之間的高階相關(guān)性，本文基于標(biāo)簽之間的關(guān)聯(lián)規(guī)則對現(xiàn)有的多標(biāo)簽分類算法MLKNN進(jìn)行優(yōu)化。

3 基于關(guān)聯(lián)規(guī)則的MLKNN多標(biāo)簽分類算法FP-MLKNN

3.1 基于FP-Growth算法的頻繁項集挖掘

FP-Growth算法是通過構(gòu)造一個樹結(jié)構(gòu)來壓縮數(shù)據(jù)記錄，使得挖掘頻繁項集只需要掃描2次數(shù)據(jù)庫，該算法不需要生成候選集合，效率比較高。

3.1.1 多標(biāo)簽轉(zhuǎn)化為項集

對多標(biāo)簽數(shù)據(jù)集中的標(biāo)簽進(jìn)行處理，將其轉(zhuǎn)化為關(guān)聯(lián)規(guī)則中的項集，以便后續(xù)的挖掘應(yīng)用。多標(biāo)簽數(shù)據(jù)集中樣本的標(biāo)簽是形如F=[1,0,0,1,0,1,…]的形式。數(shù)組F的長度表示數(shù)據(jù)集標(biāo)簽的數(shù)量，F(xiàn)[i]表示第i個標(biāo)簽，當(dāng)F[i]為0時，表示樣本不包含該標(biāo)簽；當(dāng)F[i]為1時，表示樣本包含該標(biāo)簽。本文首先對數(shù)據(jù)集標(biāo)簽進(jìn)行處理，將其轉(zhuǎn)化為項集的形式。如F1=[0,1,1,0,0,1]轉(zhuǎn)化成[1,2,5]的形式，表示該樣本擁有的標(biāo)簽下標(biāo)為1,2,5。本文對多標(biāo)簽數(shù)據(jù)進(jìn)行樣本標(biāo)簽的轉(zhuǎn)化(即把數(shù)據(jù)集中的樣本用樣本所包含標(biāo)簽的下標(biāo)來表示)，便于關(guān)聯(lián)規(guī)則的挖據(jù)。

3.1.2 生成關(guān)聯(lián)規(guī)則

對多標(biāo)簽數(shù)據(jù)集中的標(biāo)簽進(jìn)行處理，采用FP-Growth對多標(biāo)簽數(shù)據(jù)集標(biāo)簽的項集進(jìn)行頻繁項集的挖掘，根據(jù)頻繁項集生成多標(biāo)簽數(shù)據(jù)標(biāo)簽之間的關(guān)聯(lián)規(guī)則，然后對規(guī)則進(jìn)行篩選。FP-Growth算法主要分為2部分：構(gòu)建FP-tree以及利用FP-tree進(jìn)行頻繁項集的挖掘，算法過程如下所示：

(1)對轉(zhuǎn)化后的數(shù)據(jù)樣本標(biāo)簽進(jìn)行掃描(第1次掃描)，得到所有頻繁項集的計數(shù)以及對應(yīng)的支持度，然后刪除支持度低于閾值的項，將頻繁項集放入項頭表，并按照支持度進(jìn)行降序排列。

(2)對數(shù)據(jù)進(jìn)行掃描(第2次掃描)，將讀到的原始數(shù)據(jù)刪除非頻繁項集，并按照支持度降序排列。

(3)讀取排序后的數(shù)據(jù)構(gòu)建FP-tree，構(gòu)建時按照排序號的順序插入FP-tree中。排序靠前的節(jié)點(diǎn)是祖先節(jié)點(diǎn)，靠后的節(jié)點(diǎn)是子孫節(jié)點(diǎn)。如果有公用的祖先節(jié)點(diǎn)，則對應(yīng)的公用祖先節(jié)點(diǎn)加1。插入后，如果有新的節(jié)點(diǎn)出現(xiàn)，則項頭表對應(yīng)的節(jié)點(diǎn)會通過節(jié)點(diǎn)鏈表連接上新節(jié)點(diǎn)。當(dāng)所有的數(shù)據(jù)都插入到FP-tree中后，F(xiàn)P-tree建立完成。

(4)從項頭表的底部項依次向上找到項頭表項對應(yīng)的條件模式基，從條件模式基遞歸挖掘得到項頭表項的頻繁項集。

(5)如果沒有限制頻繁項集的項數(shù)，則返回步驟(4)得到所有的頻繁項集，否則只返回滿足項數(shù)要求的頻繁項集。

3.2 基于MLKNN算法求樣本的特征置信度

利用MLKNN算法計算出每個樣本根據(jù)特征得到的擁有標(biāo)簽的概率，即特征置信度。MLKNN算法是通過KNN算法尋找和樣本最近的k個樣本，統(tǒng)計這k個樣本中每個類別的個數(shù)，再通過最大后驗概率計算樣本包含每個標(biāo)簽的概率。設(shè)訓(xùn)練集X={x1,x2,…,xn}，標(biāo)簽集Y={yx1,yx2,…,yxn}。

基于貝葉斯概率公式的MLKNN算法的分類函數(shù)如式(3)所示，通過式(3)來確定樣本xi是否包含標(biāo)簽l。只需看b∈{0,1}中哪種情況使得式(3)的值最大，若b=1時最大，則xi包含標(biāo)簽l，yxi(l)=1；若b= 0時最大，則xi不包含標(biāo)簽l，yxi(l)=0。

(3)

(4)

(5)

(6)

其中，j代表測試樣本xi的k近鄰中包含標(biāo)簽l的個數(shù)；c[j]代表在所有訓(xùn)練樣本中，其k近鄰有j個含l標(biāo)簽，且其自身也有l(wèi)標(biāo)簽的樣本個數(shù)。c′[j]代表在所有訓(xùn)練樣本中，其k近鄰有j個含l標(biāo)簽，且其自身不含l標(biāo)簽的樣本個數(shù)。

本文通過式(7)計算得到樣本xi包含標(biāo)簽l的概率：

(7)

基于MLKNN算法求樣本的特征置信度過程描述如下：

%計算先驗概率

forl∈ydo

end

%計算后驗概率

IdentifyN(xi)，i∈{1,2,…,n};/*N(xi)為樣本xi的近鄰集合*/

forl∈ydo

forj∈{0,1…,k}do

c[j]=0;c′[j]=0;/*c[j]和c′[j]初始化均為0，用來存儲k個近鄰中分別包含和不包含標(biāo)簽l的個數(shù)*/

end

fori∈{1,2,…,n}do

δ=Cxi(l);

if(yxi(l)==1)then

c[δ]=c[δ]+1;

elsec′[δ]=c′[δ]+1;

end

forj∈{0,1…,k}do

%計算訓(xùn)練樣本的特征置信度P(l)

end

forl∈ydo

j=∑a∈N(t)ya(l);/*j表示測試樣本t的k個近鄰中包含標(biāo)簽l的個數(shù)*/

end

3.3 FP-MLKNN算法流程

本文提出了一種基于關(guān)聯(lián)規(guī)則的MLKNN多標(biāo)簽分類算法，采用關(guān)聯(lián)規(guī)則算法挖掘標(biāo)簽之間的高階相關(guān)性，并將其融入到MLKNN中進(jìn)行改進(jìn)。算法流程如下所示：

步驟1利用MLKNN算法計算出每個樣本根據(jù)特征得到的擁有標(biāo)簽的概率，即樣本的特征置信度。

(8)

其中，Confm(li)表示樣本擁有標(biāo)簽的li預(yù)測概率。

步驟2采用FP-Growth算法進(jìn)行關(guān)聯(lián)規(guī)則的挖掘生成頻繁項集，通過調(diào)節(jié)支持度與置信度得到一系列強(qiáng)關(guān)聯(lián)規(guī)則Confa。

(9)

其中，Confa是求所有A?li的置信度，{A，li}組成的所有集合為基于FP-Growth算法挖掘生成的頻繁項集。

步驟3通過步驟1將預(yù)測概率大于0.5的標(biāo)簽篩選出來組成集合Lt，然后從步驟2中篩選出集合A屬于集合Lt子集的最大Confa，即max(Confsa)，其中，Confsa為Confa中的元素。再計算樣本最終擁有某標(biāo)簽的概率。

P(li)=w*Confm+(1-w)*max(Confsa)

(10)

其中，P(li)為樣本最終擁有某標(biāo)簽的概率，w為標(biāo)簽相關(guān)性的影響程度。

基于關(guān)聯(lián)規(guī)則的MLKNN多標(biāo)簽分類算法FP-MLKNN如算法1所示：

算法1FP-MLKNN算法

輸入：訓(xùn)練數(shù)據(jù)集X，測試集T，近鄰數(shù)k，標(biāo)簽相關(guān)性的影響程度w。

輸出：測試集T對應(yīng)的標(biāo)簽集Yt。

標(biāo)簽集合L={l1,l2,l3,…,lq}

fori=1,2,3,…,qdo

根據(jù)式(8)計算得到測試集T的特征置信度。

end

由關(guān)聯(lián)規(guī)則算法，通過調(diào)節(jié)支持度(support)與置信度(confidence)得到一系列強(qiáng)關(guān)聯(lián)規(guī)則Confa;

fori=1,2,3,…,q)do

將T對應(yīng)的標(biāo)簽li的特征置信度大于0.5的作為轉(zhuǎn)化為集合Lt

end

forConfsainConfa do

ifConfsa中的A是Lt的子集then

Confsa=p(li|A={l1∪l2∪…∪ln})

end

fori=1,2,3,…,qdo

由式(10)計算標(biāo)簽概率P(li);

ifP(li)>0.5then

li∈Yt

end

4 實(shí)驗與分析

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

本文在yeast、emotions和enron 3個不同領(lǐng)域的數(shù)據(jù)集上進(jìn)行實(shí)驗，數(shù)據(jù)集的具體信息如表1所示。

Table 1 Experimental datasets

其中，Cardinality和Density分別表示標(biāo)簽的基數(shù)和標(biāo)簽的密度，標(biāo)簽的基數(shù)為樣本的平均標(biāo)簽個數(shù)，標(biāo)簽的密度為標(biāo)簽的基數(shù)與標(biāo)簽總數(shù)的比值。

本文采用十折交叉驗證法，即將數(shù)據(jù)集分成10份，輪流將其中9份作為訓(xùn)練數(shù)據(jù)，1份作為測試數(shù)據(jù)進(jìn)行驗證。本文進(jìn)行了10次十折交叉驗證，并求其平均值作為最終對模型精度的估計。

4.2 評價指標(biāo)

實(shí)驗采用Hamming loss、One-error、Coverage、Ranking loss和Average precision多標(biāo)簽分類算法評價指標(biāo)對FP-MLKNN多標(biāo)簽分類算法進(jìn)行有效性驗證。

Hamming loss指標(biāo)考察樣本在單個標(biāo)簽上的錯誤分類的情況，即屬于該樣本的標(biāo)簽沒有出現(xiàn)在該樣本的標(biāo)簽集合中，不屬于該樣本的標(biāo)簽出現(xiàn)在該樣本的標(biāo)簽集合中。該指標(biāo)越小，被錯分類的情況越少，算法性能越好，最優(yōu)值為hloss(h)s=0。

(11)

其中，h為分類器，Δ表示2個集合之間的對稱差(異或)，s表示測試樣本個數(shù)，q表示所有標(biāo)簽個數(shù)，h(xi)表示樣本xi預(yù)測標(biāo)簽的集合，Yi表示測試樣本xi實(shí)際標(biāo)簽的集合。

One-error指標(biāo)用來評估在輸出結(jié)果中排序第一的標(biāo)簽并不屬于實(shí)際標(biāo)簽集的概率。該指標(biāo)取值越小算法性能越優(yōu)，最優(yōu)值為one-errors(f)=0。

(12)

(13)

Ranking loss指標(biāo)表示在樣本擁有的標(biāo)簽集合排序序列中出現(xiàn)錯誤排序的情況，即無關(guān)標(biāo)簽在排序序列中位于相關(guān)標(biāo)簽之前。該值越小算法性能越優(yōu)，最優(yōu)值為rlosss(f)=0。

(14)

Average precision指標(biāo)表示在樣本擁有的標(biāo)簽集合排序序列中，排在相關(guān)標(biāo)簽集的標(biāo)簽前面，且屬于相關(guān)標(biāo)簽集的概率。該指標(biāo)越大算法性能越優(yōu)，最優(yōu)值為avgprecs(f)=1。

rankf(xi,l),l′∈Yi|)/rankf(xi,l)

(15)

其中，rankf(xi,l)為實(shí)值函數(shù)f(xi,l)對應(yīng)的排序函數(shù),f(xi,l)表示標(biāo)簽l的預(yù)測概率。

4.3 實(shí)驗結(jié)果及分析

采用改進(jìn)后的算法在yeast、emotions和enron 3個數(shù)據(jù)集上進(jìn)行實(shí)驗。首先，選取合適的支持度與置信度篩選出每個數(shù)據(jù)集合適的強(qiáng)關(guān)聯(lián)規(guī)則；然后調(diào)整相關(guān)性的影響程度w進(jìn)行驗證。表2～表4是近鄰數(shù)k為3,6和10時原始算法與改進(jìn)算法的實(shí)驗結(jié)果比較；表5是近鄰數(shù)k為10時改進(jìn)算法與MLKNN、AdaBoostMH、BPMLL這3種算法的實(shí)驗對比。符號↓表示該指標(biāo)越小性能越好，↑表示該指標(biāo)越大性能越好，加粗表示在同一行中對應(yīng)參數(shù)下最好的結(jié)果。

從表2～表4中可以看出，近鄰數(shù)越大，分類效果越好，這是因為k值越大，近鄰中包含的信息越多，從而能更好地利用標(biāo)簽之間的相關(guān)性使得分類結(jié)果更加準(zhǔn)確，但是較大的k值需要找到更多的近鄰，從而增加了算法的復(fù)雜度。而對于參數(shù)w(0≤w≤1)，在取值變化過程中,對于包含不同標(biāo)簽集的數(shù)據(jù)集而言，w并不是取值越大越好，對于不同的數(shù)據(jù)集，使得算法性能最好的w值是不一樣的。這是因為不同的數(shù)據(jù)集中樣本的個數(shù)以及標(biāo)簽集的大小是不同的，其對應(yīng)標(biāo)簽的關(guān)聯(lián)規(guī)則也是不同的。因此，要選擇合適的w進(jìn)行算法的改進(jìn)。

從表中的實(shí)驗結(jié)果可以看出，選擇合適的w改進(jìn)的算法相對于原始算法MLKNN性能有所提升。這是由于標(biāo)簽之間是存在相關(guān)性的，MLKNN算法沒有考慮標(biāo)簽之間的相關(guān)性，因此本文采用關(guān)聯(lián)規(guī)則算法挖掘標(biāo)簽之間的相關(guān)性，并將標(biāo)簽之間的關(guān)聯(lián)規(guī)則應(yīng)用到MLKNN算法改進(jìn)中，使得最后的分類效果所有提升。改進(jìn)算法相對原始算法復(fù)雜度也有所增加，在樣本數(shù)為N、標(biāo)簽數(shù)為M的數(shù)據(jù)集中，尋找某個樣本的k近鄰，需要計算出其與所有樣本的距離，時間復(fù)雜度為O(N)，然后對這些距離進(jìn)行排序，使用最優(yōu)排序算法的時間復(fù)雜度為O(NlogN)，所以MLKNN算法訓(xùn)練過程的時間復(fù)雜度為O(N2logN)。本文算法在MLKNN算法的基礎(chǔ)上增加了對標(biāo)簽之間相關(guān)性的挖掘，相對MLKNN算法增加了關(guān)聯(lián)規(guī)則算法的復(fù)雜度。使用FP-Growth算法進(jìn)行關(guān)聯(lián)規(guī)則的挖掘，在第1次遍歷數(shù)據(jù)庫時，時間復(fù)雜度為O(N)，第2次遍歷數(shù)據(jù)庫時，完成對FP-tree的構(gòu)建，時間復(fù)雜度為O(NlogN)，挖掘頻繁模式時，對所有項的條件模式進(jìn)行遞歸查找，時間復(fù)雜度為O(MlogM)。綜上所述，關(guān)聯(lián)規(guī)則算法復(fù)雜度為O(N)+O(NlogN)+O(MlogM)。

Table 2 Comparison of experimental results between the original algorithmand the improved algorithm with differentwvalues whenk=3

Table 3 Comparison of experimental results between the original algorithmand the improved algorithm with different w values whenk=6

Table 4 Comparison of experimental results between the original algorithmand the improved algorithm with differentwvalues whenk=10

如表5所示，將改進(jìn)后的算法FP-MLKNN與其他多標(biāo)簽分類算法MLKNN、BPMLL和AdaBoostMH進(jìn)行實(shí)驗對比，其中 MLKNN 和 AdaBoostMH 算法屬于一階處理方法，BPMLL是二階處理方法。實(shí)驗中FP-MLKNN和MLKNN的k取值都為10，F(xiàn)P-MLKNN算法在yeast、emotions、enron數(shù)據(jù)集上w的取值分別為0.9,0.8,0.7。從實(shí)驗對比可知，本文提出的基于關(guān)聯(lián)規(guī)則的MLKNN多標(biāo)簽分類算法FP-MLKNN在3個數(shù)據(jù)集上的性能均優(yōu)于其他多標(biāo)簽分類算法的，這說明了本文所提出的基于關(guān)聯(lián)規(guī)則的MLKNN多標(biāo)簽分類算法的科學(xué)性和準(zhǔn)確性。

Table 5 Experimental comparison ofmulti-label classification algorithms

5 結(jié)束語

在多標(biāo)簽學(xué)習(xí)中，標(biāo)簽之間的相關(guān)性是一個不可忽略的因素，已有的MLKNN算法并沒有考慮標(biāo)簽之間的相關(guān)性。為了充分利用標(biāo)簽之間的相關(guān)性來優(yōu)化多標(biāo)簽分類算法的性能，本文提出了一種基于關(guān)聯(lián)規(guī)則的MLKNN多標(biāo)簽分類算法FP-MLKNN。針對多標(biāo)簽數(shù)據(jù)考慮標(biāo)簽與標(biāo)簽之間的相關(guān)性，采用關(guān)聯(lián)規(guī)則算法挖掘標(biāo)簽之間的高階相關(guān)性，將標(biāo)簽之間的關(guān)聯(lián)規(guī)則應(yīng)用到MLKNN算法改進(jìn)中。在具體實(shí)施中，采用改進(jìn)后的算法對yeast、emotions和enron 3個數(shù)據(jù)集進(jìn)行實(shí)驗，并將改進(jìn)后的算法FP-MLKNN與其他多標(biāo)簽分類算法MLKNN、BPMLL和AdaBoostMH進(jìn)行實(shí)驗對比，實(shí)驗結(jié)果表明，本文所提出的基于關(guān)聯(lián)規(guī)則的MLKNN多標(biāo)簽分類算法極大地提高了多標(biāo)簽數(shù)據(jù)分類的準(zhǔn)確性。