基于隨機標(biāo)記子集的多標(biāo)記數(shù)據(jù)流分類算法

孫艷歌，尤 磊，卲 罕，李艷靈

(信陽師范學(xué)院 計算機與信息技術(shù)學(xué)院，河南 信陽 464000)

0 引言

在眾多實際問題中，數(shù)據(jù)都是以流的形式不斷產(chǎn)生的.這種快速到達的、實時的、連續(xù)的和無界的數(shù)據(jù)序列稱為數(shù)據(jù)流(Data Streams)[1].近年來，針對單標(biāo)記數(shù)據(jù)流分類問題,國內(nèi)外學(xué)者進行了廣泛深入的研究.傳統(tǒng)的單標(biāo)記數(shù)據(jù)流分類算法沒有充分考慮到數(shù)據(jù)流中的數(shù)據(jù)可能同時隸屬于多個標(biāo)記的情況，因此無法對多標(biāo)記數(shù)據(jù)流進行分類.然而在現(xiàn)實世界中多標(biāo)記數(shù)據(jù)流是非常普遍的.例如，用戶可能對交叉領(lǐng)域的文章感覺興趣，同時這些興趣并不是一成不變的，如何預(yù)測用戶對同時屬于某些多個類別的文章是否感興趣，這些都是典型的多標(biāo)記數(shù)據(jù)流分類問題.

從學(xué)習(xí)和預(yù)測的觀點來看，標(biāo)記間的依賴關(guān)系是重要的信息來源，可以用于彌補待預(yù)測實例本身信息不足的缺點[2].例如，當(dāng)一部電影被標(biāo)有“武俠”和“古裝”兩個標(biāo)記時，它被標(biāo)記為“動作”的可能性就很高；當(dāng)一則新聞被標(biāo)記為“軍事”時，它就不太可能同時擁有“娛樂”標(biāo)記.因此，近年來大量多標(biāo)記學(xué)習(xí)的研究工作都在于標(biāo)記間依賴關(guān)系的發(fā)現(xiàn)和利用.在多數(shù)據(jù)流環(huán)境中，數(shù)據(jù)流的潛在分布會隨著時間的發(fā)生變化，這使得訓(xùn)練數(shù)據(jù)的分布與測試數(shù)據(jù)的分布不一致，這種現(xiàn)象稱為概念漂移(Concept Drift)[3].這使得原有的分類模型不再適用，就需要快速地檢測到這種變化，并動態(tài)更新模型以適應(yīng)這種改變.

本文在分析多標(biāo)記數(shù)據(jù)流學(xué)習(xí)特性的基礎(chǔ)上，提出了一種考慮標(biāo)記間依賴關(guān)系的，應(yīng)對多種類型概念漂移的自適應(yīng)集成分類算法.本文主要貢獻如下：

(1)利用集成的周期加權(quán)的機制來應(yīng)對漸變式概念漂移，同時引入內(nèi)部的概念漂移檢測機制以增加對突變式概念漂移的適應(yīng)性.

(2)提出了一種基于隨機劃分的標(biāo)記子集的概率分類器鏈算法，在充分利用標(biāo)記間依賴關(guān)系的同時，又有效地降低了概率分類器鏈的時間復(fù)雜度.

1 相關(guān)工作

近年來，研究者提出了眾多的多標(biāo)記分類算法，總體可以分為兩類：算法適應(yīng)方法和問題轉(zhuǎn)化方法[4].算法適應(yīng)方法是通過擴展現(xiàn)有的單標(biāo)記學(xué)習(xí)算法，使其能直接處理多標(biāo)記數(shù)據(jù)，典型的算法有基于決策樹[5]、KNN[6]和神經(jīng)網(wǎng)絡(luò)的改進算法[7]等.對于不同的學(xué)習(xí)模式一般都采用不同的擴展策略，通常一種學(xué)習(xí)模型的拓展策略并不適用于其他模型.問題轉(zhuǎn)化方法是將一個多標(biāo)記實例集轉(zhuǎn)化成一個或多個單標(biāo)記實例集，從而可以直接應(yīng)用已有的單標(biāo)記分類模型來解決多標(biāo)記分類學(xué)習(xí)問題.因此相比較下問題轉(zhuǎn)化策略具有更好的靈活性.典型的問題轉(zhuǎn)化方法包括基于二值的BR(Binary Relevance)轉(zhuǎn)化和基于標(biāo)記冪集合的LP(Labelset Power)轉(zhuǎn)化.READ等[8]提出了分類器鏈算法，在保持了BR轉(zhuǎn)化的簡單有效性同時，又考慮了標(biāo)記間的依賴關(guān)系.在分類器鏈的基礎(chǔ)上，DEMBCYNSKI等[9]提出了概率分類器鏈PCC(Probabilistic Classifier Chains)算法.PCC算法從最小化損失和貝葉斯最優(yōu)估計角度來解釋多標(biāo)記問題.

上述的多標(biāo)記算法都是基于靜態(tài)數(shù)據(jù)集的，無法直接應(yīng)用多標(biāo)記數(shù)據(jù)流環(huán)境中.QU等[10]提出MBR算法，將數(shù)據(jù)流劃分成連續(xù)的數(shù)據(jù)塊，在每個數(shù)據(jù)塊上用BR方法轉(zhuǎn)換過的多標(biāo)記分類器，在分類時只保存最新k個分類器，采用集成的方式對樣本進行分類.KONG和YU[11]提出了多標(biāo)記數(shù)據(jù)流隨機生成樹算法(Streaming Multi-lAbel Random Trees，SMART)，可以有效地更新模型結(jié)構(gòu)和統(tǒng)計多標(biāo)記數(shù)據(jù)流中在樹的每個節(jié)點的數(shù)目，但是算法并未考慮概念漂移問題.READ等[12]提出的多標(biāo)記Hoeffding樹算法(Mudti-Label Hoeffding Tree，MLHT)與SMART類似，此算法是Hoeffding tree算法在多標(biāo)記數(shù)據(jù)流學(xué)習(xí)中的擴展.隨后READ等[13]又提出了EaHTps算法，采用自適應(yīng)窗口算法作為概念檢測器，當(dāng)發(fā)現(xiàn)有概念漂移發(fā)生時建立新的分類器，使用PS算法剪枝葉子節(jié)點中不頻繁出現(xiàn)的標(biāo)記組合.SPYROMITROS-XIOUFIS等[14]用多個窗口的方法(Multiple Windows，MW)解決多標(biāo)記數(shù)據(jù)流中的數(shù)據(jù)概念漂移和數(shù)據(jù)傾斜問題，由于算法需要事先對窗口參數(shù)進行設(shè)置，因此很難在實際中操作.

2 基于隨機標(biāo)記子集的多標(biāo)記數(shù)據(jù)流集成分類算法

2.1 多標(biāo)記數(shù)據(jù)流分類模型描述

設(shè)x?Rd為樣本空間，L= {l1,l2,…,lm}為含有m個標(biāo)記的標(biāo)記集合.在多標(biāo)記數(shù)據(jù)流學(xué)習(xí)中，數(shù)據(jù)流可表示為：

S={(x1,y1),…, (xt,yt) ,…}，

2.2 基于隨機標(biāo)記子集的概率分類器鏈

為提高概率分類器鏈的運行效率，本文提出一種基于隨機劃分的標(biāo)記子集的概率分類器鏈算法(RAndom K labelset Probabilistic Classifier Chain, RAKPCC).算法的主要思想是將原始較大的標(biāo)記集隨機地劃分為多個較小的標(biāo)記子集，并針對每個標(biāo)記子集訓(xùn)練一個概率分類器鏈.當(dāng)對一個未知實例分類時，使用所有的概率分類器鏈對其分類并組合所有分類結(jié)果.這樣在充分考慮標(biāo)記間依賴關(guān)系的同時，又有效地降低了概率分類器鏈的時間復(fù)雜度.

給定標(biāo)記子集大小k，劃分大小為m的初始標(biāo)記集合L的最簡單策略就是將其劃分為n=「m/k?個互不相交的子集l1,l2,…,ln，其中從l1到ln-1，各子集的大小都為k.如果m為k的整數(shù)倍，則子集ln的大小也為k，否則其大小為m除以k的余數(shù)，即包含L中最后小于k個標(biāo)記.此時，將各標(biāo)記子集看作一個單獨的分類任務(wù)，分為針對其學(xué)習(xí)一個分類器.

劃分標(biāo)記子集后的下一關(guān)鍵步驟是為每個標(biāo)記子集li生成其相對應(yīng)的訓(xùn)練實例集合Di.此處采用了與基于二值的BR轉(zhuǎn)化類似的方法，Di包含了原始實例集合D中的所有實例.對訓(xùn)練集D={(x1,C1), (x2,C2) ,…, (xn,Cn)}中的實例xi，首先設(shè)其有|li|個標(biāo)記，|li|為標(biāo)記子集li中包含標(biāo)記的個數(shù).然后針對li中的每一個標(biāo)記lij，若lij∈Ci，則將實例xi相對應(yīng)標(biāo)記設(shè)為1，否則就設(shè)為0.可見，該轉(zhuǎn)化過程與BR轉(zhuǎn)化類似，不同的是BR轉(zhuǎn)化只針對一個標(biāo)記，而此處是針對多個標(biāo)記.生成訓(xùn)練集后，即可為每個標(biāo)記子集訓(xùn)練一個概率分類器鏈.因此，基于該劃分策略的算法流程如算法1所示.

算法1 RAKPCC算法的訓(xùn)練過程

輸入：訓(xùn)練集合D={(x1,C1),…,(xn,Cn)},標(biāo)記集L,標(biāo)記子集大小k.

輸出：隨機劃分的n=「m/k?個標(biāo)記子集，以及在其上訓(xùn)練的概率分類器鏈.

算法流程:

01.將原標(biāo)記集L劃分成n=「m/k?個不相交的標(biāo)記子集,并生成其相應(yīng)的實例集合Di;

02.設(shè)i等于1，循環(huán)加1，直到i等于n.在第i次循環(huán)過程中為第i個標(biāo)記子集li訓(xùn)練一個分類器鏈.循環(huán)過程為：

對標(biāo)記子集li中的標(biāo)記進行排序,

設(shè)j等于1，循環(huán)加1，直到i等于j=|li|,循環(huán)過程為：

(1)設(shè)Dij={},

(2)對Di中的每個實例d=(x,C),產(chǎn)生一個新屬性集合x′={x,λ1,λ2,…,λi-1},生成新實例d′=(x′,λi)并將其添加到Dij中,

(3)在實例集合Di訓(xùn)練針對第i個標(biāo)記的一個二類分類器：

fi:Dij→{0,1},

(4)生成分類器鏈CCi=(f1,f2, …,f|li|);

03.返回n個分類器鏈(CC1,CC2,…,CCn).

當(dāng)對待測實例x分類時使用所有的概率分類器鏈，每個分類器鏈只針對其所對應(yīng)的標(biāo)記子集進行，然后組合所有分類器鏈的分類結(jié)果即可得到最終的分類結(jié)果向量.分類過程如算法2所示.

算法2 RAKPCC的分類過程

輸入： 待測實例x.

輸出： 實例x的標(biāo)記向量Y=(y1,y2,…,yn),其中yk=1表示x屬于第k個類，yk=0表示x不屬于第k個標(biāo)記.

算法流程：

01. 設(shè)標(biāo)記向量Y為空，Y← {};

02. 設(shè)i等于1，循環(huán)加1，直到i等于n.在第i次循環(huán)過程中使用第i個概率分類器鏈對x進行分類. 找出聯(lián)合概率最大的標(biāo)記向量值yi;

03. 組合各分類器的結(jié)果向量返回分類結(jié)果Y=(y1,y2,…,yn).

所提出的算法相比基本的概率分類器鏈極大地簡化了概率分類器鏈算法的計算效率.概率分類器鏈的時間復(fù)雜度為O(2m)，RAKPCC的時間復(fù)雜度僅為n*O(2k)，n=「m/k?為標(biāo)記子集個數(shù).例如，當(dāng)標(biāo)記集L的大小m為20時，為遍歷每種可能的分類結(jié)果，概率分類器鏈需要訓(xùn)練220-1=4095個分類器，而將L劃分成k= 5的子集時，僅需訓(xùn)練4*(25-1)=124個分類器，當(dāng)k取更小時，所需訓(xùn)練的分類器更少.

2.3 基于隨機標(biāo)記子集的多標(biāo)記數(shù)據(jù)流分類算法

本文提出的采用基于隨機標(biāo)記子集的多標(biāo)記數(shù)據(jù)流分類算法(Multi-Label ensemble with Adaptive Windowing，MLAW)，采用RAKPCC在不同時間段的數(shù)據(jù)塊上學(xué)習(xí)，順序產(chǎn)生組合分類器.當(dāng)一個新的數(shù)據(jù)塊達到時，根據(jù)其在當(dāng)前最新數(shù)據(jù)塊上的評價更新它們的組合權(quán)重，采用最大投票策略預(yù)測待分類實例的類別.

同時，在集成算法中引入了自適應(yīng)滑動窗口算法[21](ADaptive WINdowing, ADWIN)來處理概念漂移.其核心思想是：把W劃分為兩個子窗W0和W1，監(jiān)測這兩個子窗口中數(shù)據(jù)分布的變化.當(dāng)兩個子窗口均值大于εcut，則表示兩子窗口的期望值不一致，進而認為兩個子窗口之間概念不相同，即發(fā)生概念漂移.εcut根據(jù)Hoeffding Bound不等式獲得:

(1)

其中：δ(0, 1)為置信度，|W0|和|W1|分別表示W(wǎng)0和W1長度，且滿足W= |W0|+|W1|.

用E= {C1,C2, …,Ck}來表示由k個組合分類器組成的集成，C′表示建立的新分類器.采用滑動窗口模型把數(shù)據(jù)流劃分成大小相等的數(shù)據(jù)塊，對于源源不斷到達的實例(xi,yi)，用ADWIN檢測概念漂移，當(dāng)檢測到有概念漂移發(fā)生，則新建一個分類器加入到分類器池中，替換性能最差的分類器.接著根據(jù)每個基分類器Ci(i= 1, 2, …,k)在最新數(shù)據(jù)塊上的分類情況，按公式(2)對采用非線性的方式對其進行加權(quán).

(2)

算法3 本文算法偽代碼

輸入:數(shù)據(jù)流S, 自適應(yīng)滑動窗口檢測器D, 分類器數(shù)k, 數(shù)據(jù)塊大小d;

輸出: 集成分類器E;

01：for 所有xt∈Sdo;

02： if |W|

03： else 用xt替換窗口中最早的實例;

04： 對所有基分類根據(jù)公式(2)加權(quán);

05： iftmodd== 0 or 檢測到有概念漂移發(fā)生 then;

06： 用RAKPCC算法在最新的數(shù)據(jù)塊上建立新的分類器C′;

07： if |E|

08： else 用C′替換集成分類器中性能最差的分類器;

09： end if

10： end if

11：end for.

3 實驗評價

3.1 數(shù)據(jù)集描述

本文實驗分別選取4數(shù)據(jù)集對所提出模型進行驗證，如表1所示.

表1 數(shù)據(jù)集合基本信息Tab. 1 The characteristics of datasets

3.2 實驗結(jié)果分析

實驗是在MOA(Massive Online Analysis)下實現(xiàn)的，所提算法與MBR, MHT和MLOzaBag以下算法進行對比：算法使用MOA平臺下的默認參數(shù).對于集成算法：數(shù)據(jù)塊大小設(shè)置為1000，基分類器數(shù)目為15.自適滑動窗口概念檢測算法的參數(shù)：置信度δ=0.002.分別從海明損失、子集準確率、F1測度、召回率和運行時間共5個方面性能進行比較. 從表2～表5中可以看出，本文所提出算法在總體上優(yōu)于其他3種算法，特別是在漢明損失、子集正確率和召回率3個項指標(biāo)上，優(yōu)勢較為明顯.

表2 不同算法的漢明損失Tab. 2 Hamming loss of different algorithms

表3 不同算法的子集準確率(%)Tab. 3 Subset Accuracy of different algorithms

表4 不同算法的召回率Tab. 4 Recall of different algorithms

表5 不同算法的F1值Tab. 5 F1of different algorithms

這是由于本文算法具有概念漂移檢測機制，因此能較好適應(yīng)于概念漂移的數(shù)據(jù)流環(huán)境.在運行時間方面，如表6所示，單分類器MBR算法消耗時間最少，其次是本文算法，MLOzaBag算法消耗時間最長.這樣由于本文基于隨機劃分的標(biāo)記子集的概率分類器鏈算法，在充分利用標(biāo)記間依賴關(guān)系的同時，又有效地降低了概率分類器鏈的時間復(fù)雜度，因此在時間上要有優(yōu)勢.單分類器算法MBR雖然速度最快，但卻在分類準確率上表現(xiàn)最差.

圖1給出了算法在概念漂移的環(huán)境下分類準確率隨著處理數(shù)據(jù)增多而變化的情況.通過分析發(fā)現(xiàn)，當(dāng)在50 K處發(fā)生概念突變時所有算法的準確率曲線均出現(xiàn)不同程度的下降，而本文算法的準確率曲線相對平穩(wěn)，受到數(shù)據(jù)中概念漂移影響最小.這正驗證了本文自適應(yīng)滑動窗口的概念漂移檢測方法，能夠指導(dǎo)分類模型進行及時更新，從而適應(yīng)概念漂移的環(huán)境.而MHT和MBR波動較大，這時由于這兩個算法在設(shè)計中并未考慮概念漂移的問題，因此不適合不平穩(wěn)的數(shù)據(jù)流環(huán)境.

表6 不同算法的消耗時間 (s)Tab. 6 Running time of different algorithms

圖1 Random Tree數(shù)據(jù)集上分類準確率比較Fig. 1 Accuracy on the Random Tree dataset

4 結(jié)束語

本文針對多標(biāo)記數(shù)據(jù)流中概念漂移現(xiàn)象，在考慮標(biāo)記間依賴關(guān)系的基礎(chǔ)上，設(shè)計并實現(xiàn)一種具有更好適應(yīng)性的基于隨機標(biāo)記子集的多標(biāo)記數(shù)據(jù)流分類算法.算法采用自適應(yīng)滑動窗口算法作為一個概念漂移檢測器引入到數(shù)據(jù)流集成算法中，通過在人工合成和真實數(shù)據(jù)集上進行比較發(fā)現(xiàn)，所提模型能夠應(yīng)對概念漂移，該算法在大多數(shù)數(shù)據(jù)集合上能夠更有效地預(yù)測實例的類標(biāo)集合.