一種基于關聯規則的MLKNN多標簽分類算法*

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

(1.北京工商大學計算機與信息工程學院，北京 100048；2.北京工商大學信息網絡中心，北京 100048)

1 引言

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

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

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

為克服現有技術的不足，本文提出一種基于關聯規則的MLKNN多標簽分類算法FP-MLKNN。該算法針對多標簽數據考慮標簽與標簽之間的相關性，采用關聯規則算法挖掘標簽之間的高階相關性，用標簽之間的關聯規則改進MLKNN算法，并通過了算法的有效性檢驗。實驗結果表明，本文所提出的基于關聯規則的MLKNN多標簽分類算法極大地提高了多標簽數據分類的準確性。

2 相關介紹

2.1 多標簽問題的定義

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

2.2 關聯規則

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

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

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

Freq(is∩it)/|D|

(1)

其中，Freq(is∩it)表示同時包含is和it的樣本數。

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

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

Freq(is∩it)/Freq(is)

(2)

其中，Freq(is)表示包含is的樣本數。

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

2.3 求解策略

目前，基于標簽相關性的求解策略主要有3類：

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

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

(3)高階策略：此類策略考慮了標簽之間的高階相關性，對每一類標簽，需要考慮標簽集中其他標簽對其的影響。該類策略可以較好地反映真實世界問題的標簽相關性，并且相對于以上2類標簽相關性建模方式有更強的建模能力。關聯規則可以發現標簽之間的高階相關性，本文基于標簽之間的關聯規則對現有的多標簽分類算法MLKNN進行優化。

3 基于關聯規則的MLKNN多標簽分類算法FP-MLKNN

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

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

3.1.1 多標簽轉化為項集

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

3.1.2 生成關聯規則

對多標簽數據集中的標簽進行處理，采用FP-Growth對多標簽數據集標簽的項集進行頻繁項集的挖掘，根據頻繁項集生成多標簽數據標簽之間的關聯規則，然后對規則進行篩選。FP-Growth算法主要分為2部分：構建FP-tree以及利用FP-tree進行頻繁項集的挖掘，算法過程如下所示：

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

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

(3)讀取排序后的數據構建FP-tree，構建時按照排序號的順序插入FP-tree中。排序靠前的節點是祖先節點，靠后的節點是子孫節點。如果有公用的祖先節點，則對應的公用祖先節點加1。插入后，如果有新的節點出現，則項頭表對應的節點會通過節點鏈表連接上新節點。當所有的數據都插入到FP-tree中后，FP-tree建立完成。

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

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

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

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

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

(3)

(4)

(5)

(6)

其中，j代表測試樣本xi的k近鄰中包含標簽l的個數；c[j]代表在所有訓練樣本中，其k近鄰有j個含l標簽，且其自身也有l標簽的樣本個數。c′[j]代表在所有訓練樣本中，其k近鄰有j個含l標簽，且其自身不含l標簽的樣本個數。

本文通過式(7)計算得到樣本xi包含標簽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個近鄰中分別包含和不包含標簽l的個數*/

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

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

end

forl∈ydo

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

end

3.3 FP-MLKNN算法流程

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

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

(8)

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

步驟2采用FP-Growth算法進行關聯規則的挖掘生成頻繁項集，通過調節支持度與置信度得到一系列強關聯規則Confa。

(9)

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

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

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

(10)

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

基于關聯規則的MLKNN多標簽分類算法FP-MLKNN如算法1所示：

算法1FP-MLKNN算法

輸入：訓練數據集X，測試集T，近鄰數k，標簽相關性的影響程度w。

輸出：測試集T對應的標簽集Yt。

標簽集合L={l1,l2,l3,…,lq}

fori=1,2,3,…,qdo

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

end

由關聯規則算法，通過調節支持度(support)與置信度(confidence)得到一系列強關聯規則Confa;

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

將T對應的標簽li的特征置信度大于0.5的作為轉化為集合Lt

end

forConfsainConfa do

ifConfsa中的A是Lt的子集then

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

end

fori=1,2,3,…,qdo

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

ifP(li)>0.5then

li∈Yt

end

4 實驗與分析

4.1 實驗數據

本文在yeast、emotions和enron 3個不同領域的數據集上進行實驗，數據集的具體信息如表1所示。

Table 1 Experimental datasets

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

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

4.2 評價指標

實驗采用Hamming loss、One-error、Coverage、Ranking loss和Average precision多標簽分類算法評價指標對FP-MLKNN多標簽分類算法進行有效性驗證。

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

(11)

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

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

(12)

(13)

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

(14)

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

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

(15)

其中，rankf(xi,l)為實值函數f(xi,l)對應的排序函數,f(xi,l)表示標簽l的預測概率。

4.3 實驗結果及分析

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

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

從表中的實驗結果可以看出，選擇合適的w改進的算法相對于原始算法MLKNN性能有所提升。這是由于標簽之間是存在相關性的，MLKNN算法沒有考慮標簽之間的相關性，因此本文采用關聯規則算法挖掘標簽之間的相關性，并將標簽之間的關聯規則應用到MLKNN算法改進中，使得最后的分類效果所有提升。改進算法相對原始算法復雜度也有所增加，在樣本數為N、標簽數為M的數據集中，尋找某個樣本的k近鄰，需要計算出其與所有樣本的距離，時間復雜度為O(N)，然后對這些距離進行排序，使用最優排序算法的時間復雜度為O(NlogN)，所以MLKNN算法訓練過程的時間復雜度為O(N2logN)。本文算法在MLKNN算法的基礎上增加了對標簽之間相關性的挖掘，相對MLKNN算法增加了關聯規則算法的復雜度。使用FP-Growth算法進行關聯規則的挖掘，在第1次遍歷數據庫時，時間復雜度為O(N)，第2次遍歷數據庫時，完成對FP-tree的構建，時間復雜度為O(NlogN)，挖掘頻繁模式時，對所有項的條件模式進行遞歸查找，時間復雜度為O(MlogM)。綜上所述，關聯規則算法復雜度為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所示，將改進后的算法FP-MLKNN與其他多標簽分類算法MLKNN、BPMLL和AdaBoostMH進行實驗對比，其中 MLKNN 和 AdaBoostMH 算法屬于一階處理方法，BPMLL是二階處理方法。實驗中FP-MLKNN和MLKNN的k取值都為10，FP-MLKNN算法在yeast、emotions、enron數據集上w的取值分別為0.9,0.8,0.7。從實驗對比可知，本文提出的基于關聯規則的MLKNN多標簽分類算法FP-MLKNN在3個數據集上的性能均優于其他多標簽分類算法的，這說明了本文所提出的基于關聯規則的MLKNN多標簽分類算法的科學性和準確性。

Table 5 Experimental comparison ofmulti-label classification algorithms

5 結束語

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