基于劃分子集主題模型的多標簽極限分類

楊菊英，劉 燚，羅 佳

(1.電子科技大學成都學院 計算機系，四川 成都 611731；2.西華師范大學 計算機學院，四川 南充 637009)

0 引 言

多標簽學習中每個訓練樣本可能同時帶有多個標簽，當標簽規模成千上萬時，傳統方法往往遇到可擴展性和高時間開銷問題[1,2]。

極限多標簽分類方法的目的是在解決上述問題、處理巨大數據集和大規模標簽的同時，控制算法的時間開銷，使分類成為事實可用的方法[3]。

在多標簽學習領域，MIMLfast可以高效地處理大規模數據集[4]，但實驗結果表明其處理的數據集的標簽數量是有限的。基于支持向量機的多標簽學習[5]在多個數據集上取得了不錯的分類精度，但時間開銷偏大，使其應用于大規模數據集的有效性受限。隱含狄利克雷分配(latent Dirichlet allocation, LDA)模型是多標簽學習領域的經典方法[6]。基于此模型，不少學者提出了其應用于極限學習場景的改進方法，例如基于緩存計算的LDA[7]、FUN-LDA[8]和DOLDA[9]等，這些取得了較好的實驗效果，但極限多標簽分類的伸縮性和效率問題仍未徹底解決。

帶標簽的隱含狄利克雷分配(labeled latent Dirichlet allocation, LLDA)模型是近年來熱門的多標簽學習方法，基于這一類方法，學者們在圖像標簽學習、文本標簽分類等領域取得了不少的成果[10,11]。雖然LLDA在大規模數據訓練中的時間復雜度不再依賴標簽集的規模L，但與每個實例的平均標簽數量有關，因此仍然不適用于復雜多標簽學習問題。本文提出了一種劃分子集的帶標簽隱含狄利克雷分配模型，改模型可進一步提高算法在大規模極限學習時的可擴展性和時間效率。

1 LDA與LLDA

1.1 隱含狄利克雷分配模型

隱含狄利克雷模型是一種經典的、高效的概率主題模型。為了統一對模型的描述，首先規定如下：設樣本的標簽總數為L，特征總數為V，l表示一個標簽，v表示一種特征類型，wi是特征在樣本位置i處的標記，樣本的總數為M，其中MTRAIN和MTEST分別表示訓練集和測試集的規模，m表示一個樣本。此外，Lm表示樣本m的標簽數量，Nm表示它的非零特征數量。

隱含狄利克雷模型假設當給定一個樣本集時，存在兩種分布的集合，標簽-特征分布稱之為φ，實例-標簽分布稱之為θ。LDA模型通過對φ和θ進行邊緣化操作，只使用隱含變量分配z來求解模型。在采樣過程中算法使用兩個計數矩陣，其中一個矩陣用于記錄特征v被分配給標簽l的次數nlv，另一個用于記錄樣本m的特征被分配給標簽l的次數nml。LDA原理如圖1所示。

圖1 LDA原理

在采樣階段，LDA根據l∈{1,…,L}來更新wi的硬分配參數zi，對于數據集中的所有標記，更新時按照固定的迭代次數順序執行的。更新方程如式(1)所示

(1)

式中：α和β是超參數。完成上述流程后，可以通過計算參數φ和θ進行點估計。

1.2 帶標簽的隱含狄利克雷分配模型

帶標簽的隱含狄利克雷模型對傳統狄利克雷模型的改進主要在于根據觀測到的樣本標簽來限制某個標記分配給某個標簽的概率。對測試實例的推理類似于無監督的LDA，標簽-特征分布φ與之前在訓練數據中學習到的內容相匹配，而測試數據的θ分布參數通過估計獲得。

LLDA在標簽上使用對稱的超參數α，給它們賦予相同的權重，然而在絕大多數真實應用中，標簽往往呈偏態分布。并且，特別是當標簽規模增大時，對標簽依賴關系建模可以提高模型表現。為解決這些問題，學者在LLDA的基礎上提出了Prior-LDA和Dep-LDA[12]。Prior-LDA通過非對稱α超參數整合訓練集中觀察到的標簽頻率，更頻繁出現的標簽將獲得更大的α′值，如式(2)所示

α′l=η·fl+α

(2)

式中：fl表示標簽l在訓練集中的頻率，fl∈[0,1]。

Dep-LDA是一個兩階段的算法，首先通過T個主題訓練一個非監督的LDA模型。通過估計得到的LDA模型將包含有關標簽依賴性的信息，因為相關標簽往往由同一個或同一批主題描述。其次，Dep-LDA將訓練一個帶標簽的隱含狄利克雷分配模型，之前通過訓練估計的非監督LDA模型的參數θ′和φ′將被用來計算非對稱的α′ml。特別是向量α′m將通過式(3)計算

α′m=η(θ′m·φ′)+α

(3)

帶標簽的隱含狄利克雷分配模型的原理如圖2所示。

圖2 LLDA原理

2 劃分子集的LLDA

當標簽集的規模過大時(例如大于104)，LLDA即將難以適應問題的規模，因為它是與L的規模線性相關的。不幸的是現有的各種LLDA的變種模型也不是針對這一問題進行改進的。

2.1 Subset LLDA原理

為解決以上問題，我們對經典的LLDA模型的預測過程進行了不同的改進，通過限制標簽空間，算法可以在其中搜索解決方案。我們提出的改進模型可以分為如下兩個階段：

(1)首先，對于每個測試樣本都定義了一個候選的標簽集，記為Lm Rel。可以采用多種方法來確定此候選列表，在本文中我們在訓練集中搜索m個最鄰近的樣本，記作Mm Rel，并將候選列表設置為檢索到的實例標記的聯合。

(2)其次，我們通過LLDA來做預測，但是限制可能的標簽數量為Lm Rel。與Prior-LDA類似，我們修正了實例-主題分布的先驗以表示標簽在m個最鄰近的相似樣本中的出現頻率。例如，當m=10時，如果一個給定的標簽lA在3個相似的臨近樣本中出現，另一個給定的標簽lB在5個相似的臨近樣本里出現，我們就讓α′lA=η+0.3α，α′lB=η+0.5α。

從形式上來說，我們提出的改進的主題模型帶有如下假設：首先，對于一個給定的樣本s和給定的已經標記的實例集合MTRAIN，s的標簽集合Ls將包含MTRAIN中m個臨近的最相似的樣本的標簽的聯合。顯然，這一假設保證n→MTRAIN，但是在其它任何樣例中它將表示一種近似，并且我們希望Ls?Ls Rel。第二個假設與Gibbs采樣中的每個標簽權重有關，我們假設對于一個給定的實例s，它的標簽可以通過對多項式分布φ′m的采樣實現。這個假設與Prior-LDA中的策略非常類似，都是通過限制實例的標簽只能通過Lm Rel而不是L來產生。基于劃分子集的帶標簽狄利克雷分配模型的原理如圖3所示。

圖3 Subset LLDA原理

如圖3所示，在Subset LLDA模型中，對于給定的實例m，其標簽可以通過對m的臨近相似實例的多項式分布采樣而獲得。

Subset LLDA模型的原理如上所述，其生成過程如算法1所示。

算法1: Subset LLDA模型的生成過程

標簽l∈L，樣例m，V上的采樣φl～Dirchlet(β)

begin

(1)Sampleninstance fromMTRAIN

(2)SetLm Rel=∪Lmiwithmi∈Mm Relandi∈{1,…,n}

(3)Sample a multinomial distributionφ′m～Dirchlet(β′)

(4)Calculateα′ according to Equation 2

(5)Sample a distributionθm～Dirichlet(α′) overLm Rel

(6)For each feature positioni∈{1…Nm}

Sample a labelzi～Multinomial(θm)

Sample a feature typevi～Multinomial(φl)with

l=zi

end

由于另一個原因，在預測期間約束標簽集也很有用：LLDA需要搜索整個標簽空間以便給一個給定的測試樣本推薦合適的標簽，由于它是基于概率的模型，算法可能會陷入局部最優解，特別是當L的規模比較大時。例如一個訓練好的LLDA模型來處理一個具有很高的φlv概率值的特殊的特征v；或者例如一個測試實例m包含特征v，其中只有一個上述標簽在語義上相關。在以上這些情況下，這些噪聲標簽，再加上LLDA的概率特性，可能會導致算法以犧牲正確標簽為代價，偏向其中一個無關標簽。這些問題當然可以通過增大樣本數量并應用馬爾可夫鏈方法解決，但這樣時間開銷太大，并不實用。因此，對LLDA進行特征子集的劃分，在控制時間復雜度上也很有意義。

最終，我們用tf-idf方法和余弦相似度來選擇每個實例的最相似臨近實例，并設置n=10。

2.2 時間復雜度分析

對于數據集中每個樣本的所有特征標記，LDA模型在求解時需要計算所有標簽的概率分布，然后為標記采樣標簽。因此標準的LDA模型的時間復雜度是與標簽集的規模L線性相關的，如式(4)所示

(4)

對于LLDA，通過限制特征標記可以在實例的標簽集Ld上獲取的可能標簽，從而可以在訓練期間引入監督。一般來說，訓練LLDA的時間開銷如式(5)所示

TLLDA∝Ο(MTRAIN·Vm·Lm)

(5)

根據之前的分析，LLDA測試過程的時間開銷與LDA相同，所以可以通過式(4)計算，而本文提出的基于劃分子集的LLDA模型在測試期間，只需要考慮最相似的n個樣本的標簽，因此Subset LLDA的總的時間復雜度包含尋找n個最相似臨近樣本的時間開銷，如式(6)所示

(6)

其中，SubsetLLDA通過縮小標簽集的規模，大大降低了算法的時間復雜度。

3 實 驗

3.1 實驗數據集

在實驗部分，我們選擇了多個經典的多標簽開放數據集，我們將這些數據集劃分為4個小規模的樣本集和4個大規模的樣本集，每個數據集的統計特征見表1。

表1 實驗數據集的統計特征

將實驗數據分為4個小數據集和4個大數據集是為了便于將本文提出的方法和其它LLDA的變種方法以及其它極限分類方法作對比。

3.2 實驗結果與分析

本文提出的模型基于Java平臺實現，為了對照實驗的公平性，我們在模型訓練中為所有的基于LLDA的模型選擇了相同的參數，取αl=50/L，α=0.1，β=0.01，在預測階段，設η=50，α=30/L，β=0.01。在訓練階段以及預測階段，我們對所有數據集的處理都采用同樣的馬爾可夫鏈方法，迭代輪數為200輪。

為了驗證劃分子集的主題模型方法是否可有效控制標簽集規模，我們驗證了不同算法對各數據集標簽規模的情況，實驗結果見表2。

表2 各算法在不同數據集上的標簽規模

準確率是分類問題最直觀的性能指標。為此，我們對比了各種算法在不同數據集上的Precision，所有算法為每個實例輸出相關標簽的排名，實驗結果見表3。

表3 各算法在不同數據集上的Precision

如表3所示，與EL-LLDA、LDAIEC和Parabel算法相比，Subset LLDA模型不僅具有最高的標簽預測綜合準確率，而且各數據集上的預測準確率比較穩定，是所有對照算法中差異最小的。

對于多分類問題，我們希望在n個二分類混淆矩陣上綜合考察查準率和查全率。一種直接的做法是先在各混淆矩陣上分別計算出查準率和查全率，記為(P1,R1),(P2，R2)，…,(Pn，Rn)，再計算平均值，這樣就得到“宏查準率Macro-P”、“宏查全率Macro-R”，以及相應的“宏F1”(Macro-F1)，如式(7)所示

(7)

此外，我們可以通過真正例TP、假正例FP、真反例TN和假反例FN求得“微F1(Micro-F1)”如式(8)所示

(8)

我們用Micro-F1指標和Macro-F1指標衡量算法的性能，并與多個經典方法進行對比，實驗結果見表4和表5。

表4 各算法在不同數據集上的Micro-F1

表5 各算法在不同數據集上的Macro-F1

如表4、表5所示，我們的對比方法包括屬于LLDA類模型的經典或最新算法EL-LLDA[13]和LDAIEC[14]，以及非LLDA類的極限分類算法Parabel[15]。無論是與LLDA類的算法相比，還是和其它極限分類算法相比，本文提出的模型都有更高的分類性能。雖然各種算法在不同數據集上的表現各有差異，但Subset LLDA無論在大多數數據集上還是在綜合表現上，都優于對照算法。實驗結果還表明，相對非LLDA類的方法，LLDA類方法是具有一定的性能優勢的。

綜合表3～表5的實驗結果可知，與各種類型的經典方法相比，本文提出的SubsetLLDA模型都具有較高的多標簽預測的準確率、召回率以及在不同類型數據集上性能的穩定性，從多標簽分類精度的角度而言，Subset LLDA模型是一種理想的多標簽學習工具。

對于極限學習方法，時間開銷是衡量算法性能的重要指標，由于前文實驗所采用的8個數據集規模各不相同，因此我們依然使用之前的數據集，衡量各種算法在不同數據規模下的時間開銷。實驗結果見表6。

表6 各算法在不同數據集上的時間開銷/s

此外，我們通過實驗測試了各對照算法的時間開銷隨數據集規模的變化情況，實驗結果如圖4所示。

圖4 時間開銷隨數據規模的變化對比

在表6中，時間開銷的度量單位為s，如表6所示，相對其它極限分類方法，LLDA類方法的時間開銷較高，但Subset LLDA在LLDA類方法中的時間開銷并不高。圖4 中數據量單位為MB，時間單位為s，如圖4所示，在各類基于LDA的方法中，隨著數據規模的增大，本文提出算法的時間開銷增長最為緩慢。本文提出的多標簽學習方法在提高準確率的同時控制了時間開銷，并未以增大計算復雜度作為代價，反而由于劃分子集的策略，在一定程度上減小了時間開銷。

4 結束語

多標簽分類問題是大數據時代巨量數據挖掘的重要問題，帶標記的隱含狄利克雷模型是解決多標簽分類的重要方法。雖然LLDA在這一領域取得了不少成果，但其準確率和效率依然具有提升空間。本文提出了一種基于劃分子集的Subset LLDA方法，通過限制候選標簽的規模，進一步提高了LLDA模型的精度和效率。應用于多個數據集的實驗結果表明，本文提出方法具有高于經典極限學習方法的多標簽預測準確率，并且相對于其它LLDA類方法，降低了時間開銷，使模型具有更強的實際應用價值。

隨著社會網絡實時用戶生成內容的增加，并行化處理、流式計算變得越來越重要。Subset LLDA如何與分布式、流式計算平臺融合，通過集群運算進一步降低時間開銷，將是這一領域未來有價值的研究方向。