基于標簽相關性的多標簽分類算法

梁義珂，謝小蘭，張迎春，張 珣

(1.北京工商大學計算機學院，北京 100048;2.北京工商大學計算機網(wǎng)絡中心，北京 100048)

1 引言

目前，多標簽分類學習已逐漸成為機器學習領域的熱點研究問題[1，2]。對于單標簽分類問題，往往是將每個實體對應于唯一的類別標簽，但多標簽分類是將屬于多個類別的數(shù)據(jù)進行分類。在實際應用中，多標簽分類可用于多個研究領域，在文本分類中，一篇新聞可能同時屬于科技、教育等類別；在圖像識別中，一張圖片可能同時包含動物、植物；在生物科技分類中，一個基因可能同時擁有翻譯、轉(zhuǎn)錄功能等等[3，4]。

在多標簽分類問題中，多個標簽同時隸屬于一個實體，并且這些標簽存在一定的關聯(lián)性，但傳統(tǒng)的單標簽學習算法并不適用于多標簽數(shù)據(jù)，所以目前對于處理多標簽分類問題，主要分為兩類：問題轉(zhuǎn)換類和算法適應類。問題轉(zhuǎn)換類算法思想是將多標簽問題轉(zhuǎn)換成一個或多個單標簽問題，如：BR(Binary Relevance)算法是使用一對一策略將多標簽學習問題轉(zhuǎn)換為多個二元分類問題[5，6]；LP(Label Power-set)算法是將標簽集的冪集中的每個元素視為一個類，從而將多標簽分類問題轉(zhuǎn)化為多類分類問題[7，8]。算法適應類算法思想是對常用的監(jiān)督學習算法進行改進，將其直接用于多標簽分類，如：多標簽k-最近鄰算法(ML-KNN)是修改k-最近鄰(KNN)算法以處理多標簽數(shù)據(jù)，并通過最大化后驗概率的方式來預測樣本的標簽集合[9，10]；Rank-SVM算法是基于支持向量機(SVM)算法，在分類時引入標簽錯誤成本函數(shù)，建立的多標簽的標簽排序方法[11]?，F(xiàn)有的多標簽分類算法較少考量標簽之間的相關性，且泛化性能較差，如LP算法可能導致訓練樣本不足以及不能預測沒有在訓練集中出現(xiàn)的新標簽組合等問題；Rank-SVM算法需要計算大量的成本函數(shù)，算法時間復雜度較高[12]。

BP(back propagation)神經(jīng)網(wǎng)絡可以表示任意非線性函數(shù)，并具有自適應學習、并行分布處理和有較強的魯棒性及容錯性等特點，因此適用于對復雜非線性系統(tǒng)進行建模和控制。針對上述問題，即通過對傳統(tǒng)的BP神經(jīng)網(wǎng)絡分類模型進行改進得到MLBP算法，使其能夠?qū)哂卸鄻撕炋匦缘臄?shù)據(jù)進行分類，并在分類過程中分別考慮了標簽之間的二階和高階相關性，最后將MLBP算法與標簽之間相關性進一步融合，最終得到的PCC-MLBP算法和R-MLBP算法，通過與現(xiàn)有的多標簽分類算法實驗對比分析，兩種算法能夠高效、快速、準確的解決多標簽分類問題。

2 算法模型構(gòu)建

為了克服上述算法分類精度差和計算效率低的缺點，本文利用改進的神經(jīng)網(wǎng)絡來計算每個樣本數(shù)據(jù)屬于各個標簽的概率，同時在分類時考慮到標簽之間的相關性，將利用皮爾遜相關系數(shù)計算兩個標簽之間的相關性，利用關聯(lián)規(guī)則計算多個標簽之間的相關性，最后將BP神經(jīng)網(wǎng)絡的分類結(jié)果和標簽之間的相關性按照一定的規(guī)則進行融合，從而得到每個樣本屬于各個標簽的可能性大小。技術路線如圖1所示。

圖1 技術路線

2.1 基于BP神經(jīng)網(wǎng)絡的多標簽分類算法(MLBP算法)

目前，采用BP(back propagation)神經(jīng)網(wǎng)絡的控制方法已日益引起人們的重視。BP神經(jīng)網(wǎng)絡是一種模仿生物神經(jīng)網(wǎng)絡結(jié)構(gòu)和功能的計算模型[13，14]，將其作為分類器時通常由輸入層、隱藏層、輸出層和分類器組成。

圖2是一個用作多類分類的五層神經(jīng)網(wǎng)絡，xi(i=1，2…d)表示輸入單元，d表示輸入單元個數(shù)，hk(k=1，2…q)表示隱層單元，q表示隱層單元個數(shù)，yj(j=1，2，…J)表示原始輸出單元，J表示原始輸出單元個數(shù)，oj表示最終輸出單元，從輸入單元i到隱層單元k的連接權(quán)為wik，從隱層單元k到原始輸出單元j的連接權(quán)為vkj，softmax是一個優(yōu)化分類結(jié)果的學習算法，它將神經(jīng)網(wǎng)絡的輸出變成了一個概率分布，每個類別的概率都在0和1之間，且各個類別的概率和為1。

圖2 神經(jīng)網(wǎng)絡結(jié)構(gòu)圖

改進的BP神經(jīng)網(wǎng)絡由輸入層、隱藏層、原始輸出層、sigmoid層以及最終輸出層組成。如圖3所示。

圖3 改進的神經(jīng)網(wǎng)絡結(jié)構(gòu)圖

現(xiàn)有的BP神經(jīng)網(wǎng)絡用作分類時，分類得到的所有標簽的概率之和為1，所以只適用于多類分類情況(即從多個標簽中選擇概率最大的一個標簽作為輸入樣本的最終標簽)，為了使其能夠解決多標簽的分類問題，本文將對上述BP神經(jīng)網(wǎng)絡分類模型進行改進。圖3是本文改進的神經(jīng)網(wǎng)絡結(jié)構(gòu)圖，本算法利用sigmoid層替換了原始的softmax層，在每個原始輸出單元后加了一個sigmoid函數(shù)，sigmoid函數(shù)可以將任何輸入映射到[0，1]空間，其函數(shù)值恰好可以解釋該標簽屬于/不屬于輸入示例的概率(概率的取值范圍是0～1)。其中，隱藏層和原始輸出層的輸出計算方式不變，而最終輸出層的計算如下

(1)

利用改進的BP神經(jīng)網(wǎng)絡模型對多標簽數(shù)據(jù)分類，可以得到每個樣本數(shù)據(jù)屬于各個標簽的概率。

2.2 基于Pearson相關系數(shù)與BP神經(jīng)網(wǎng)絡的多標簽分類算法(PCC-MLBP算法)

2.2.1 利用皮爾遜相關系數(shù)計算兩個標簽之間的相關性

皮爾遜(Pearson)相關也稱為積差相關，被廣泛用于度量兩個變量之間的相關性，其值介于-1與1之間，可以根據(jù)Pearson 相關系數(shù)大小可判斷兩個變量的關聯(lián)程度[15，16]。Pearson 相關系數(shù)公式如下

(2)

最終計算出的相關系數(shù)的含義可以有如下理解：

1)當相關系數(shù)為0時，X和Y兩變量無關系。2)當X的值增大(減小)，Y值增大(減小)，兩個變量為正相關，相關系數(shù)在0與1之間。

3)當X的值增大(減小)，Y值減小(增大)，兩個變量為負相關，相關系數(shù)在-1與0之間。

利用Pearson相關系數(shù)計算多標簽數(shù)據(jù)中兩個標簽之間的相關性，X和Y表示本算法中的兩個標簽集合，ρXY絕對值越大表示這兩個標簽的相關性越大，ρXY絕對值越小表示這兩個標簽的相關性越小，由于Pearson相關系數(shù)只計算兩兩標簽之間的相關性，即只考慮了標簽的二階相關性，接下來還要分析標簽之間的高階相關性。

2.2.2 將MLBP神經(jīng)網(wǎng)絡分類結(jié)果與Pearson相關系數(shù)融合

設樣本合集S={s1，s2，…sr…sR}，sr表示第r個樣本，R表示樣本的個數(shù)，標簽合集：D={d1，d2…df…dF}，df表示第f個標簽，F(xiàn)表示標簽的個數(shù)，則融合的步驟如下：

1)通過改進的BP神經(jīng)網(wǎng)絡得到的樣本數(shù)據(jù)s1屬于各個標簽的概率合集為：{Ps11，Ps12…Ps1r…Ps1F}，Ps1r表示樣本數(shù)據(jù)s1屬于df標簽的概率。

2)計算得到標簽d1和其它F-1個標簽之間的Pearson相關系數(shù)的合集：{Cd12，Cd13…Cd1f…Cd1F}，Cd1f表示標簽d1和標簽df之間的Pearson相關系數(shù)；

3)計算樣本數(shù)據(jù)s1屬于標簽d1的最終概率Pcs1d1

Pcs1d1=αPs11+(1-α)max(Cd12，Cd13…Cd1f…Cd1F)

(3)

其中，Ps11表示神經(jīng)網(wǎng)絡得到的樣本數(shù)據(jù)s1屬于標簽d1的概率Ps11，max(Cd12，Cd13，…Cd1F)表示標簽d1和其它F-1個標簽之間的Pearson相關系數(shù)的最大值，α表示Ps11和max(Cd12，Cd13…Cd1f…Cd1F)在融合規(guī)則所占的權(quán)重比，α越大表示Ps11占的比重越大。

2.3 基于關聯(lián)規(guī)則與BP神經(jīng)網(wǎng)絡的多標簽分類算法( R-MLBP算法)

2.3.1 利用關聯(lián)規(guī)則得到多個標簽之間的相關性

若兩個或多個變量的取值之間存在某種規(guī)律性，則稱為關聯(lián)。關聯(lián)規(guī)則是反映一個事物與其它事物之間的相互依存性和關聯(lián)性[17，18]。如果兩個或多個事物之間存在一定的關聯(lián)關系，則其中一個事物就能通過其它事物預測到。設y1和y2表示兩個集合，關聯(lián)規(guī)則R：y1?y2，表示y1出現(xiàn)，則導致y2以某一概率也會出現(xiàn)，y1稱為規(guī)則前項，y2稱為規(guī)則后項。關聯(lián)規(guī)則的強度可以用它的支持度(support)和置信度(confidence)來度量。

關聯(lián)規(guī)則的支持度是同時包含多個樣本的樣本數(shù)與總樣本數(shù)之比即

(4)

其中，sup(y1?y2)表示y1和y2的支持度，count(y1∩y2)表示同時包含y1和y2的樣本數(shù)，|N|表示總樣本數(shù)；關聯(lián)規(guī)則的可信度是指包含多個樣本的樣本數(shù)與包含y1的樣本數(shù)之比，即

(5)

其中，conf(y1?y2)表示y1和y2的可信度，count(y1)表示包含y1的樣本數(shù)。為了找出數(shù)據(jù)集中的關聯(lián)規(guī)則，需要給定數(shù)據(jù)集的最小支持度(supmin)和最小可信度(confmin)，而關聯(lián)規(guī)則挖掘就是在數(shù)據(jù)集中找出支持度和置信度分別大于給定的最小支持度(supmin)和最小置信度(confmin)的關聯(lián)規(guī)則。

通過反復試驗確定多標簽數(shù)據(jù)集的最小支持(supmin)和最小可信度(confmin)，然后在多標簽數(shù)據(jù)集中找出支持度大于最小支持(supmin)且置信度大于最小可信度(confmin)的關聯(lián)規(guī)則，本文利用FP-growth算法來挖掘標簽之間的相關性。

FP-growth算法的主要思想：首先掃描一遍數(shù)據(jù)庫，得到頻繁1-項集和每個頻繁項的支持度，創(chuàng)建FP-Tree的根結(jié)點，記為T，并且標記為Null。然后根據(jù)每個頻繁項的支持度對頻繁1-項集降序排序。再次掃描事務數(shù)據(jù)庫，把數(shù)據(jù)庫中的頻繁集壓縮到一棵頻繁模式樹FP-Tree上。挖掘FP-Tree生成條件庫構(gòu)造條件FP-Tree，在條件FP-Tree遞歸挖掘，產(chǎn)生頻繁模式。具體算法描述如下：

輸入：事務數(shù)據(jù)庫D；最小支持度閾值supmin。

輸出：頻繁模式的完全集。

算法：

1)按以下步驟構(gòu)造FP-tree；

①掃描事務數(shù)據(jù)庫D一次。收集頻繁項的集合F和它們的支持度。對F按支持度降序排序，結(jié)果為頻繁項集L。

②創(chuàng)建FP-tree的根節(jié)點，以“Null”標記它。對于D中每個事務Trans，執(zhí) 行：選擇Trans中的頻繁項，并按L中的次序排序。設排序后的頻繁項表為[p|P]，其中p是第一個元素，而P是剩余元素的列表。調(diào)用insert＿tree([p|P]，T)。該過程執(zhí)行情況如下，若T有子女N使得N.item-name=p.item-name，則N的計數(shù)增加l；否則創(chuàng)建一個新節(jié)點N，將其計數(shù)設置為1，鏈接到它的父節(jié)點T，并且通過節(jié)點鏈結(jié)構(gòu)將其鏈接到具有相同item-name的節(jié)點，若P非空，遞歸地調(diào)用insert＿tree(P ，N)。

2)FP-Tree的挖掘通過調(diào)用過程FP-Growth(

FP-Tree，null)實現(xiàn)。

Procedure FP-Growth(Tree，null)

{

if Tree包含單條路徑P then

for 路徑P中節(jié)點的每個組合(記為β) do{

產(chǎn)生項目集β∪α，其支持度為β中節(jié)點的最小的支持度；

}

else

for each Tree的頭部αido{

產(chǎn)生項目β=αi∪α，其支持數(shù)為αi的支持數(shù)；

構(gòu)造β的條件模式基，然后構(gòu)造β的條件FP-樹treeβ；

if treeβ≠? then

調(diào)用FP-Growth(treeβ，β)；

}

end

}

2.3.2 將BP神經(jīng)網(wǎng)絡的分類結(jié)果與標簽之間的相關性進行融合

設樣本合集S={s1，s2，…sr…sR}，sr表示第r個樣本，R表示樣本的個數(shù)，標簽合集：D={d1，d2…df…dF}，df表示第f個標簽，F(xiàn)表示標簽的個數(shù)，則融合的步驟如下：

1)通過改進的BP神經(jīng)網(wǎng)絡得到的樣本數(shù)據(jù)s1屬于各個標簽的概率合集為：{Ps11，Ps12…Ps1r…Ps1F}，Ps1r表示樣本數(shù)據(jù)s1屬于df標簽的概率；

3)為概率集合{Ps11，Ps12…Ps1r…Ps1F}中各個概率設置一個閾值T(T=0.5)，并將概率合集中大于該閾值的概率作為一個新的合集D；

4)如果B?D，則計算得到標簽d1的關聯(lián)規(guī)則結(jié)果為Rd1=R(B?d1)。

5)計算樣本數(shù)據(jù)s1屬于標簽d1的最終概率PRs1d1

PRs1d1=βPs11+(1-β)maxRd1

(6)

其中，Ps11表示BP神經(jīng)網(wǎng)絡得到的樣本數(shù)據(jù)s1屬于標簽d1的概率，maxRd1表示標簽d1的關聯(lián)規(guī)則結(jié)果的最大值，β表示Ps11和maxRd1在融合規(guī)則所占的權(quán)重比，β越大表示Ps11占的比重越大。

3 實驗分析

3.1 實驗數(shù)據(jù)

為了檢驗本算法的有效性，本文在4 種多標簽數(shù)據(jù)集上(Emotions、Scene、Yeast、Enron)對多標簽分類模型進行驗證，這些數(shù)據(jù)都是在網(wǎng)站上的公共數(shù)據(jù)集，來自生活中的不同領域，其類型都是數(shù)值型。其中Emotions是音樂數(shù)據(jù)集，包含了593個音樂樣本實例和6個類別標簽；Scene是圖像數(shù)據(jù)集，包含了2407個圖象樣本實例和45個類別標簽；Yeast是基因樣本數(shù)據(jù)集，包含2417 個基因樣本實例和14個類別標簽；Enron是文本數(shù)據(jù)集，包含了1702個文本樣本實例和53個類別標簽。各個數(shù)據(jù)集的基本統(tǒng)計信息如表1所示。其中，標簽基數(shù)(Cardinality)表示樣本的平均標簽個數(shù)，標簽密度(Density)表示標簽的基數(shù)與標簽總數(shù)的比值。

表1 實驗數(shù)據(jù)集的統(tǒng)計信息

3.2 實驗評價指標

為了驗證基于標簽相關性的BP神經(jīng)網(wǎng)絡多標簽分類模型的性能，并使模型的分類結(jié)果更為準確可靠，本文采用十折交叉驗證法進行分類實驗，即將數(shù)據(jù)集平均分成十份，每次將其中9份作為訓練數(shù)據(jù)，另1份作為測試數(shù)據(jù)，進行10次試驗后將其結(jié)果加權(quán)求平均作為最終的訓練結(jié)果，采用如下指標來評估模型性能。

a)Hamming-loss

該評價指標用于考察樣本在單個標簽上的誤分類情況，例如，一個標簽不屬于一個示例而被預測為輸入該示例或者一個標簽屬于一個示例而沒被預測為屬于該示例。Hamming-loss數(shù)值在0和1之間，其數(shù)值越小，算法效果越好。

(7)

其中，n表示樣本個數(shù)，m表示標簽個數(shù)，h(Xi)表示第i個樣本對應的預測標簽，Yi表示第i個樣本對應真實標簽，算子Δ用于表示兩個集合之間的對稱差，|·|為返回集合大小。

b)One-Error

該評價指標用于考察在樣本的類別標簽排序序列中序列最前端的標簽不屬于相關標簽集合的情況，該指標取值越小，性能越好。

(8)

c)Coverage

該評價指標用于考察在樣本的類別標簽排序序列中覆蓋所有相關標簽所需的捜索深度情況。該指標取值越小，系統(tǒng)的性能越好。

(9)

其中，n示樣本個數(shù)，Yi表示第i個樣本對應的真實標簽，rank(xi，y)表示y標簽在預測序列中的排序，越大表示排序越低。

d)Ranking-loss

該指標用于考察在樣本的類別標簽排序序列中出現(xiàn)排序錯誤的情況，即無關標簽在排序序列中位于相關標簽之前。該指標取值越小，系統(tǒng)的性能越好。

(10)

e)Average precision

該指標用于考察在樣本的類別標簽排序序列中排在相關標簽之前的標簽仍為相關標簽的情況。Average precision數(shù)值越大，說明該多標簽學習算法學習效果越好。

(11)

其中，n表示樣本個數(shù)，Yi表示第i個樣本對應的真實標簽，y′和y表示樣本xi的兩個相關標簽，|y′|表示y′的個數(shù)，rank(xi，y′)和rank(xi，y)分別表示樣本xi的類別標簽y′和y的排序序列。

3.3 實驗結(jié)果與分析

在本文的實驗過程中有四個參數(shù)需要調(diào)節(jié)，分別是2.3.1中的最小支持度(supmin) 和最小可信度(confmin)以及式3中的權(quán)重系數(shù)α和式6中的權(quán)重系數(shù)β，經(jīng)過反復實驗發(fā)現(xiàn)當關聯(lián)規(guī)則的最小支持度(supmin)值大于0.1時，得到的關聯(lián)規(guī)則數(shù)量太少，因此將關聯(lián)規(guī)則的最小支持度(supmin)值設為0.1，最小可信度(confmin)設為0.6，同時，將式3中的權(quán)重系數(shù)α和式6中的權(quán)重系數(shù)β設為{0.6，0.7，0.8，0.9}。

為了體現(xiàn)算法的有效性，本文將MLBP算法、PCC-MLBP算法以及R-MLBP算法與已有的多標簽算法：ML-KNN算法、BP-MLL算法進行對比。表2～表5是在四個公共數(shù)據(jù)集上五個多標簽分類算法的實驗結(jié)果比較。

表2 多標簽分類算法在Scene數(shù)據(jù)集上的實驗結(jié)果比較

由表2可以看出，在Scene數(shù)據(jù)集上，PCC-MLBP算法在Coverage指標下，當參數(shù)α 為0.9時表現(xiàn)更好，而其它四個指標都是在α 為0.8時表現(xiàn)最好；而R-MLBP算法是β為0.8時，五種指標都表現(xiàn)為最好。

表3 多標簽分類算法在Emotions數(shù)據(jù)集上實驗結(jié)果比較

由表3可以看出，在Emotions數(shù)據(jù)集上，PCC-MLBP算法在Average Precision指標下，當參數(shù)α 為0.9時表現(xiàn)更好，而其它四個指標都是在α 為0.8時表現(xiàn)最好；而R-MLBP算法是β為0.8時，五種指標都表現(xiàn)為最好。

表4 多標簽分類算法在Yeast數(shù)據(jù)集上的實驗結(jié)果比較

由表4可以看出，在Yeast數(shù)據(jù)集上，PCC-MLBP算法在Hamming-loss指標下，當參數(shù)α 為0.9時表現(xiàn)更好，而其它四個指標都是在α 為0.8時表現(xiàn)最好；而R-MLBP算法是β為0.8時，五種指標都表現(xiàn)為最好。

表5 多標簽分類算法在Enron數(shù)據(jù)集上的實驗結(jié)果比較

由表5可以看出，在Enron數(shù)據(jù)集上，PCC-MLBP算法的參數(shù)α和R-MLBP算法的參數(shù)β都是在等于0.8時，五種指標表現(xiàn)為最好。

通過將本文提出的三種算法(MLBP，PCC-MLBP，R-MLBP)和經(jīng)典的兩種算法(BP-MLL，ML-KNN)在4個公共數(shù)據(jù)集上根據(jù)5 個評價指標的實驗結(jié)果綜合分析可得：

1)相對于現(xiàn)有的ML-KNN和BP-MLL多標簽算法，本文提出的PCC-MLBP算法和R-MLBP算法在四個公共數(shù)據(jù)集上的五種多標簽分類指標的效果都有所提升；

2)從表中的數(shù)據(jù)可以得出，說明MLBP算法在與式3中的相關系數(shù)及式6中的關聯(lián)規(guī)則結(jié)合時，神經(jīng)網(wǎng)絡所占權(quán)重為0.8時能得到最佳的分類效果。

3)在本文提出的三種算法MLBP、PCC-MLBP和R-MLBP中，R-MLBP算法在考慮多個標簽(大于兩個)之間的相關性時，可以全面地反映各個標簽之間的相關性，其分類效果較優(yōu)。

本文提出的算法在文本分類和圖像識別等多標簽分類問題中，可以更好地描述標簽之間的相關性，提升了分類精度。

4 結(jié)論

在多標簽分類問題中，標簽之間的相關性是影響分類效果的重要因素，本文提出了基于標簽相關性的BP神經(jīng)網(wǎng)絡多標簽分類算法。先是改進了傳統(tǒng)的BP神經(jīng)網(wǎng)絡，使其適應多標簽分類場景，然后在分類的過程中綜合考慮了標簽的二階和高階相關性，實現(xiàn)PCC-MLBP和R-MLBP算法。在此基礎上，在4種真實數(shù)據(jù)集上利用5種多標簽分類指標對算法進行有效性驗證。結(jié)果表明，利用本文提出的方法對具有多標簽特征的數(shù)據(jù)進行分類時準確率相對較高。后續(xù)工作將針對海量數(shù)據(jù)設計包括多個隱藏層的神經(jīng)網(wǎng)絡結(jié)構(gòu)，進一步提升算法的分類性能。