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

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

1 引言

分類算法是機(jī)器學(xué)習(xí)方法的重要內(nèi)容，能夠有效解決應(yīng)用領(lǐng)域數(shù)據(jù)的分類問(wèn)題。傳統(tǒng)分類算法主要解決的是單標(biāo)簽分類問(wèn)題，然而隨著信息技術(shù)的發(fā)展，多標(biāo)簽分類已經(jīng)成為分類問(wèn)題中不可或缺的一部分，在現(xiàn)實(shí)生活中多標(biāo)簽分類[1,2]問(wèn)題的應(yīng)用也變得越來(lái)越廣泛，例如，場(chǎng)景分類、生物信息學(xué)、多媒體自動(dòng)標(biāo)記與數(shù)據(jù)挖掘等領(lǐng)域的應(yīng)用。在多標(biāo)簽分類問(wèn)題中，標(biāo)簽之間存在著一定的關(guān)聯(lián)性，若忽略標(biāo)簽之間的關(guān)系，則會(huì)損失標(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í)的“維數(shù)災(zāi)難”問(wèn)題。

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

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

為克服現(xiàn)有技術(shù)的不足，本文提出一種基于關(guān)聯(lián)規(guī)則的MLKNN多標(biāo)簽分類算法FP-MLKNN。該算法針對(duì)多標(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算法，并通過(guò)了算法的有效性檢驗(yàn)。實(shí)驗(yàn)結(jié)果表明，本文所提出的基于關(guān)聯(lián)規(guī)則的MLKNN多標(biāo)簽分類算法極大地提高了多標(biāo)簽數(shù)據(jù)分類的準(zhǔn)確性。

2 相關(guān)介紹

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

令X={x1,x2,…,xn}表示樣本空間，L={l1,l2,…,ln}表示標(biāo)簽集合，Y={yx1,yx2,…,yxn}表示標(biāo)簽空間，對(duì)于L中的任意一項(xiàng)li(1≤i≤q)，都有l(wèi)i∈{0,1}，li取0時(shí)表示該標(biāo)簽為無(wú)相關(guān)標(biāo)簽，li取1時(shí)表示該標(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)練得到一個(gè)多標(biāo)簽分類器h:X→2L，通過(guò)訓(xùn)練得到的多標(biāo)簽分類器來(lái)預(yù)測(cè)未知樣本所包含的標(biāo)簽集合。但是，在大多數(shù)情況下，多標(biāo)簽分類系統(tǒng)的輸出對(duì)應(yīng)于一個(gè)實(shí)值函數(shù)f:X×L→R，f(xi,li)為樣本xi包含標(biāo)簽li的置信度。當(dāng)給定一個(gè)樣本數(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ù)，用來(lái)決定是否應(yīng)該將數(shù)據(jù)xi歸屬到標(biāo)簽li中。

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

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

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

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

Freq(is∩it)/|D|

(1)

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

規(guī)則is?it在D中的置信度是指同時(shí)包含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時(shí)，認(rèn)為該關(guān)聯(lián)規(guī)則是有效的，稱為強(qiáng)關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則挖掘算法主要有Apriori算法和FP-Growth算法[12]，Apriori算法效率相對(duì)較低且存在冗余模式，因此本文采用FP-Growth進(jìn)行關(guān)聯(lián)規(guī)則的挖掘，進(jìn)而得到多個(gè)標(biāo)簽之間的相關(guān)性。FP-Growth算法只需要對(duì)數(shù)據(jù)庫(kù)進(jìn)行2次掃描，通過(guò)FP-tree[14]數(shù)據(jù)結(jié)構(gòu)對(duì)原始數(shù)據(jù)進(jìn)行壓縮。

2.3 求解策略

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

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

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

(3)高階策略：此類策略考慮了標(biāo)簽之間的高階相關(guān)性，對(duì)每一類標(biāo)簽，需要考慮標(biāo)簽集中其他標(biāo)簽對(duì)其的影響。該類策略可以較好地反映真實(shí)世界問(wèn)題的標(biāo)簽相關(guān)性，并且相對(duì)于以上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ī)則對(duì)現(xiàn)有的多標(biāo)簽分類算法MLKNN進(jìn)行優(yōu)化。

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

3.1 基于FP-Growth算法的頻繁項(xiàng)集挖掘

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

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

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

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

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

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

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

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

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

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

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

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

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

(3)

(4)

(5)

(6)

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

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

(7)

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

%計(jì)算先驗(yàn)概率

forl∈ydo

end

%計(jì)算后驗(yàn)概率

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，用來(lái)存儲(chǔ)k個(gè)近鄰中分別包含和不包含標(biāo)簽l的個(gè)數(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

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

end

forl∈ydo

j=∑a∈N(t)ya(l);/*j表示測(cè)試樣本t的k個(gè)近鄰中包含標(biāo)簽l的個(gè)數(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ì)算出每個(gè)樣本根據(jù)特征得到的擁有標(biāo)簽的概率，即樣本的特征置信度。

(8)

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

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

(9)

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

步驟3通過(guò)步驟1將預(yù)測(cè)概率大于0.5的標(biāo)簽篩選出來(lái)組成集合Lt，然后從步驟2中篩選出集合A屬于集合Lt子集的最大Confa，即max(Confsa)，其中，Confsa為Confa中的元素。再計(jì)算樣本最終擁有某標(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，測(cè)試集T，近鄰數(shù)k，標(biāo)簽相關(guān)性的影響程度w。

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

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

fori=1,2,3,…,qdo

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

end

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

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

將T對(duì)應(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)計(jì)算標(biāo)簽概率P(li);

ifP(li)>0.5then

li∈Yt

end

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

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

Table 1 Experimental datasets

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

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

4.2 評(píng)價(jià)指標(biāo)

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

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

(11)

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

One-error指標(biāo)用來(lái)評(píng)估在輸出結(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)錯(cuò)誤排序的情況，即無(wú)關(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)對(duì)應(yīng)的排序函數(shù),f(xi,l)表示標(biāo)簽l的預(yù)測(cè)概率。

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

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

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

從表中的實(shí)驗(yàn)結(jié)果可以看出，選擇合適的w改進(jìn)的算法相對(duì)于原始算法MLKNN性能有所提升。這是由于標(biāo)簽之間是存在相關(guān)性的，MLKNN算法沒(méi)有考慮標(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)算法相對(duì)原始算法復(fù)雜度也有所增加，在樣本數(shù)為N、標(biāo)簽數(shù)為M的數(shù)據(jù)集中，尋找某個(gè)樣本的k近鄰，需要計(jì)算出其與所有樣本的距離，時(shí)間復(fù)雜度為O(N)，然后對(duì)這些距離進(jìn)行排序，使用最優(yōu)排序算法的時(shí)間復(fù)雜度為O(NlogN)，所以MLKNN算法訓(xùn)練過(guò)程的時(shí)間復(fù)雜度為O(N2logN)。本文算法在MLKNN算法的基礎(chǔ)上增加了對(duì)標(biāo)簽之間相關(guān)性的挖掘，相對(duì)MLKNN算法增加了關(guān)聯(lián)規(guī)則算法的復(fù)雜度。使用FP-Growth算法進(jìn)行關(guān)聯(lián)規(guī)則的挖掘，在第1次遍歷數(shù)據(jù)庫(kù)時(shí)，時(shí)間復(fù)雜度為O(N)，第2次遍歷數(shù)據(jù)庫(kù)時(shí)，完成對(duì)FP-tree的構(gòu)建，時(shí)間復(fù)雜度為O(NlogN)，挖掘頻繁模式時(shí)，對(duì)所有項(xiàng)的條件模式進(jìn)行遞歸查找，時(shí)間復(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í)驗(yàn)對(duì)比，其中 MLKNN 和 AdaBoostMH 算法屬于一階處理方法，BPMLL是二階處理方法。實(shí)驗(yàn)中FP-MLKNN和MLKNN的k取值都為10，F(xiàn)P-MLKNN算法在yeast、emotions、enron數(shù)據(jù)集上w的取值分別為0.9,0.8,0.7。從實(shí)驗(yàn)對(duì)比可知，本文提出的基于關(guān)聯(lián)規(guī)則的MLKNN多標(biāo)簽分類算法FP-MLKNN在3個(gè)數(shù)據(jù)集上的性能均優(yōu)于其他多標(biāo)簽分類算法的，這說(shuō)明了本文所提出的基于關(guān)聯(lián)規(guī)則的MLKNN多標(biāo)簽分類算法的科學(xué)性和準(zhǔn)確性。

Table 5 Experimental comparison ofmulti-label classification algorithms

5 結(jié)束語(yǔ)

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