基于核極限學(xué)習(xí)機(jī)的多標(biāo)簽數(shù)據(jù)流集成分類方法

張海翔，李培培，胡學(xué)鋼

（1.大數(shù)據(jù)知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室（合肥工業(yè)大學(xué)），合肥 230601；2.合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院，合肥 230601）

引 言

為了克服傳統(tǒng)單標(biāo)簽分類的缺陷，多標(biāo)簽分類（Multi?label classification，MLC）［1］，即一個(gè)事物對(duì)應(yīng)多個(gè)類標(biāo)簽概念的研究變得尤為重要。在實(shí)際應(yīng)用領(lǐng)域中多標(biāo)簽數(shù)據(jù)流呈現(xiàn)出海量快速、概念漂移等特點(diǎn)，使得傳統(tǒng)多標(biāo)簽分類算法無(wú)法直接解決此類問(wèn)題。因而，如何在有限的時(shí)間和內(nèi)存下快速處理這些新到來(lái)的數(shù)據(jù)，并適應(yīng)數(shù)據(jù)流環(huán)境下的概念漂移等，設(shè)計(jì)魯棒的多標(biāo)簽數(shù)據(jù)流分類方法成為重要而具有挑戰(zhàn)的任務(wù)之一。

目前，已有的多標(biāo)簽分類方法主要包括：批處理方法和在線學(xué)習(xí)方法［1］。其中批處理方法默認(rèn)每次訓(xùn)練與測(cè)試的數(shù)據(jù)集一次性到來(lái)，根據(jù)已有全部信息采用問(wèn)題轉(zhuǎn)化、算法自適應(yīng)［2］解決多標(biāo)簽分類問(wèn)題。Huang［3?4］提出的極限學(xué)習(xí)機(jī)（Extreme learning machine，ELM）及其改進(jìn)算法［5］具有高速和高效等特點(diǎn)，避免了繁瑣的迭代學(xué)習(xí)過(guò)程以及傳統(tǒng)前饋神經(jīng)網(wǎng)絡(luò)的迭代學(xué)習(xí)引起的學(xué)習(xí)參數(shù)隨機(jī)設(shè)置、容易陷入局部最小值等問(wèn)題，同時(shí)改進(jìn)算法能進(jìn)一步提高分類精度。因此，基于（核）極限學(xué)習(xí)機(jī)的相關(guān)研究被廣泛應(yīng)用于多標(biāo)簽分類問(wèn)題，并取得了一系列的成果［6?10］。然而，實(shí)際應(yīng)用領(lǐng)域涌現(xiàn)的數(shù)據(jù)流由于具有海量快速等特點(diǎn)，難以一次性全部獲取。同時(shí)，當(dāng)新數(shù)據(jù)到來(lái)時(shí)這些批處理算法不斷對(duì)新數(shù)據(jù)重新訓(xùn)練而拋棄舊模型，導(dǎo)致有效歷史數(shù)據(jù)的大量丟失，因此能夠處理數(shù)據(jù)流環(huán)境下的學(xué)習(xí)模型也越來(lái)越受到重視［11］。目前已有一些成果［12］采用滑動(dòng)窗口技術(shù)將極限學(xué)習(xí)機(jī)應(yīng)用解決數(shù)據(jù)流多標(biāo)簽分類，但該方法未考慮多標(biāo)簽間的類標(biāo)簽相關(guān)問(wèn)題以及數(shù)據(jù)流環(huán)境下的概念漂移等問(wèn)題。另一方面，文獻(xiàn)［13］指出在處理數(shù)據(jù)流時(shí)需要考慮模型在有限的時(shí)間和內(nèi)存下做出精準(zhǔn)預(yù)測(cè)并包含應(yīng)對(duì)概念漂移問(wèn)題的解決方案。這些需求為多標(biāo)簽數(shù)據(jù)流分類帶來(lái)更多的挑戰(zhàn)。數(shù)據(jù)流環(huán)境下的多標(biāo)簽分類算法［14］大多采用問(wèn)題轉(zhuǎn)化，將分類轉(zhuǎn)化為一系列穩(wěn)定的學(xué)習(xí)任務(wù)，雖然在一定程度上該方法能夠適用，卻忽略了標(biāo)簽之間的相關(guān)性［15］。同時(shí)未考慮到新到來(lái)的數(shù)據(jù)中高速、多變特性，而且其中隱含的概念漂移問(wèn)題也是問(wèn)題轉(zhuǎn)化方法難以解決的［16］。

1 相關(guān)工作

本節(jié)將簡(jiǎn)要概述基于ELM的多標(biāo)簽分類方法與多標(biāo)簽數(shù)據(jù)流分類方法。

1.1 基于ELM的多標(biāo)簽分類方法

Huang等［3?4］提出的ELM在一次學(xué)習(xí)中就可得到一個(gè)恰當(dāng)?shù)慕?，避免了如誤差反向傳播算法（Back propagation，BP）［17］等基于梯度下降的復(fù)雜耗時(shí)方法。因而利用ELM學(xué)習(xí)速度快、實(shí)驗(yàn)效果更好的性能，在多標(biāo)簽分類問(wèn)題上將ELM作為訓(xùn)練模型成為一種新的研究方向。文獻(xiàn)［18?20］利用給定數(shù)據(jù)集將ELM應(yīng)用多標(biāo)簽分類問(wèn)題。然而，一方面由于ELM的隱藏層節(jié)點(diǎn)設(shè)置的隨機(jī)性會(huì)引起隱藏層輸出矩陣的振蕩，從而降低網(wǎng)絡(luò)結(jié)構(gòu)的穩(wěn)定性。另一方面，考慮到ELM隱藏層將輸入樣本映射至線性可分的空間，該映射過(guò)程與內(nèi)核函數(shù)的內(nèi)積運(yùn)算將特征向量從高維映射到低維空間原理一致［5］。因此，Luo等［10］提出基于核極限學(xué)習(xí)機(jī)（Kernel extreme learning machine，KELM）的多標(biāo)簽分類方法ML?KELM，相較于ELM，ML?KELM只需確定內(nèi)核函數(shù)和相關(guān)參數(shù)，就可得到穩(wěn)定結(jié)果。針對(duì)高維數(shù)據(jù)環(huán)境，Lin等［21］提出多標(biāo)簽核判別分析方法，利用核函數(shù)技術(shù)整體處理多標(biāo)簽并實(shí)現(xiàn)非線性降維。為了解決神經(jīng)網(wǎng)絡(luò)中的過(guò)擬合問(wèn)題，Zhang等［22］提出一種基于徑向基函數(shù)（Radial basis function，RBF）的多層ELM網(wǎng)絡(luò)模型用于多標(biāo)簽分類問(wèn)題ML?ELM?RBF。Kongsorot等［23］提出基于模糊集理論的增量核ELM方法，將實(shí)例及其對(duì)應(yīng)類之間的關(guān)系定義為模糊成員。Law等［24］提出一種用于多標(biāo)簽數(shù)據(jù)分類的級(jí)聯(lián)神經(jīng)網(wǎng)絡(luò)，將堆疊式自動(dòng)編碼器（Stacked auto?encoder，SAE）和ELM合并協(xié)作。Wang等［25］利用標(biāo)簽相關(guān)性和非平衡參數(shù)得到非平衡標(biāo)簽補(bǔ)全矩陣，將其與核極限學(xué)習(xí)機(jī)進(jìn)行聯(lián)合學(xué)習(xí)。上述方法探索了在多標(biāo)簽分類問(wèn)題上ELM模型的應(yīng)用，并取得了一定的成果。然而，這些方法都是批處理方法，難以直接應(yīng)用于海量快速的數(shù)據(jù)流分類問(wèn)題。

1.2 多標(biāo)簽數(shù)據(jù)流分類方法

為解決多標(biāo)簽數(shù)據(jù)流分類問(wèn)題，已有方法多采用問(wèn)題轉(zhuǎn)化與算法適應(yīng)的策略［26］。其中，基于問(wèn)題轉(zhuǎn)化策略相關(guān)工作包括：Qu等［27］提出基于二元相關(guān)（Binary relevance，BR）的多標(biāo)簽數(shù)據(jù)流分類方法，采用增量批處理技術(shù)，其模型在順序到來(lái)的同等大小數(shù)據(jù)塊上學(xué)習(xí)。Xioufis等［28］采用BR通過(guò)將多標(biāo)簽任務(wù)轉(zhuǎn)換為若干二進(jìn)制分類任務(wù)來(lái)解決MLC，通過(guò)為每個(gè)標(biāo)簽維護(hù)2個(gè)可變大小窗口來(lái)處理概念漂移。文獻(xiàn)［29］提出增量多標(biāo)簽決策樹(shù)方法，將Hoeffding樹(shù)［30］轉(zhuǎn)化為適應(yīng)數(shù)據(jù)流多標(biāo)簽分類；多標(biāo)簽Hoeffding樹(shù)與Pruned Set分類器［31］合并，當(dāng)此節(jié)點(diǎn)中獲取樣本的緩沖區(qū)已滿時(shí)，修剪每個(gè)葉節(jié)點(diǎn)處的標(biāo)簽組合；此外Hoeffding樹(shù)還與ADWIN Bagging［32］（EaHTps）結(jié)合以解決概念漂移問(wèn)題。Shi等［33］使用Apriori和集成方法（Ensemble methods，EM）算法將類標(biāo)簽集基于依賴性劃分為不同的子集，這些子集被視為新類標(biāo)簽，用于注釋每個(gè)到達(dá)的樣本；同時(shí)，提出一種基于標(biāo)簽組合與閾值的概念漂移檢測(cè)方法。然而上述方法忽略標(biāo)簽間的相關(guān)性，造成分類精度較差。

基于算法適應(yīng)策略相關(guān)工作包括：Shi等［34］通過(guò)動(dòng)態(tài)識(shí)別新頻繁標(biāo)簽組合并更新標(biāo)簽組合集方法解決類標(biāo)簽相關(guān)分析問(wèn)題；Osojnik等［14］將多目標(biāo)回歸應(yīng)用于數(shù)據(jù)流的多標(biāo)簽學(xué)習(xí)，但該方法僅側(cè)重于學(xué)習(xí)靜止概念問(wèn)題；Nguyen等［35］提出一種基于貝葉斯的多標(biāo)簽數(shù)據(jù)流學(xué)習(xí)方法，可以從每個(gè)真實(shí)標(biāo)簽的樣本中學(xué)習(xí)標(biāo)簽間相關(guān)性，并根據(jù)霍夫丁不等式和標(biāo)簽基數(shù)來(lái)調(diào)整預(yù)測(cè)標(biāo)簽的數(shù)目，通過(guò)“未確定的值”方法擴(kuò)展了標(biāo)簽特征值表來(lái)解決缺失值問(wèn)題。此外，作者進(jìn)一步提出基于加權(quán)聚類模型的增量在線多標(biāo)簽分類方法［36］，利用衰減機(jī)制來(lái)適應(yīng)概念漂移。雖然文獻(xiàn)［35?36］利用模型本身優(yōu)勢(shì)學(xué)習(xí)標(biāo)簽間的相關(guān)性，并引入損失函數(shù)降低歷史數(shù)據(jù)影響以適應(yīng)概念漂移，但在計(jì)算特征與標(biāo)簽間聯(lián)合分布過(guò)程中消耗過(guò)多時(shí)間。

2 數(shù)據(jù)流多標(biāo)簽分類集成方法

首先給出數(shù)據(jù)流多標(biāo)簽分類問(wèn)題的定義：給定一個(gè)多標(biāo)簽數(shù)據(jù)流D，根據(jù)滑動(dòng)窗口機(jī)制，將所述多標(biāo)簽數(shù)據(jù)流D等分成n個(gè)數(shù)據(jù)塊集合D={D1，D2，…，Dk，…，DN}，k=1，2，…，N，其中Dk為所述多標(biāo)簽數(shù)據(jù)流D中的第k個(gè)數(shù)據(jù)塊，Dk={(x1，y1)，(x2，y2)，…，(xi，yi)，…，(xn，yn)}表示所述多標(biāo)簽數(shù)據(jù)流D中的第k個(gè)數(shù)據(jù)塊Dk中的第i個(gè)多標(biāo)簽示例，xi∈Rm表示樣本m維特征空間，yi表示所述第k個(gè)數(shù)據(jù)塊Dk中的第i個(gè)多標(biāo)簽示例的類標(biāo)簽，滿足yi∈Y，Y表示標(biāo)簽空間中包含L個(gè)不同標(biāo)簽，記為Y={l1，l2，…，lL}。在線多標(biāo)簽分類器任務(wù)是學(xué)習(xí)從多標(biāo)簽數(shù)據(jù)流塊中找到其實(shí)例的類標(biāo)簽，即f∑kDk：x→2M，xi∈x，yi∈y。對(duì) 于 新 到 來(lái) 未 知 標(biāo) 簽 數(shù) 據(jù) 塊Dk+1中 的 樣 本xj∈Dk+1，分 類 器f(·)預(yù) 測(cè)f(xj)?Y作為它的可能標(biāo)簽集合。

本文所提方法采用增量批處理技術(shù)，算法分為4個(gè)步驟：（1）初始假設(shè)選取前k個(gè)數(shù)據(jù)塊構(gòu)成基分類器集合D={D1，D2，…，Dk}；（2）根據(jù)已有的k個(gè)訓(xùn)練數(shù)據(jù)分別分析其內(nèi)部類標(biāo)簽關(guān)系，得到關(guān)聯(lián)規(guī)則，并構(gòu)建MUENLForeset概念漂移檢測(cè)機(jī)制；（3）利用得到的關(guān)聯(lián)規(guī)則構(gòu)建基于核的極限學(xué)習(xí)機(jī)KELM的多標(biāo)簽數(shù)據(jù)流集成分類模型OS?KELM，然后對(duì)于新到來(lái)的數(shù)據(jù)塊Dk+1，先利用訓(xùn)練好的模型和關(guān)聯(lián)規(guī)則輸出預(yù)測(cè)結(jié)果，并將新數(shù)據(jù)塊替換基分類器中效果最差的數(shù)據(jù)塊數(shù)據(jù)；（4）在預(yù)測(cè)過(guò)程中判斷Dk+1是否發(fā)生漂移，若發(fā)生漂移則對(duì)基分類器數(shù)據(jù)塊引入權(quán)重?fù)p失函數(shù)降低舊數(shù)據(jù)的貢獻(xiàn)程度。算法框架流程圖如圖1所示。

圖1 本文方法整體框架圖Fig.1 Framework of the proposed method

2.1 基于Apriori算法的類標(biāo)簽相關(guān)性分析

在多標(biāo)簽分類過(guò)程中，樣本實(shí)例與多個(gè)標(biāo)簽相對(duì)應(yīng)并且標(biāo)簽集合中可能存在標(biāo)簽關(guān)聯(lián)［34?37］性質(zhì)，即標(biāo)簽數(shù)據(jù)集合中存在一種關(guān)聯(lián)關(guān)系使得一個(gè)標(biāo)簽屬于該樣本隱含著另一個(gè)標(biāo)簽也屬于該樣本。通過(guò)找到這些成對(duì)的標(biāo)簽間關(guān)系并在預(yù)測(cè)過(guò)程中引入以提高整體的分類精度。基于上述分析，提出基于Apriori關(guān)聯(lián)規(guī)則算法的類標(biāo)簽相關(guān)性分析策略。

針對(duì)到來(lái)的每個(gè)數(shù)據(jù)塊Di，在利用Di中所包含信息訓(xùn)練KELM模型之前，對(duì)其標(biāo)簽集Yi?Y采用Apriori算法［37］計(jì)算此數(shù)據(jù)塊標(biāo)簽集中所蘊(yùn)含的標(biāo)簽間關(guān)聯(lián)規(guī)則集合rules，根據(jù)關(guān)聯(lián)規(guī)則找到所有滿足置信度的成對(duì)標(biāo)簽，將同現(xiàn)標(biāo)簽的置信度引入到基于集成模型的預(yù)測(cè)過(guò)程中以提高整體的分類精度。本文Apriori算法支持度設(shè)置為0.3，置信度為0.6。

2.2 基于核極限學(xué)習(xí)機(jī)的集成模型構(gòu)建與預(yù)測(cè)

隨著前k個(gè)數(shù)據(jù)塊Di（1≤i≤k）的到來(lái)，分別構(gòu)建核極限學(xué)習(xí)機(jī)，針對(duì)第i個(gè)數(shù)據(jù)塊Di={(xi，yi)}，特征向量可表示為m×n的矩陣，m表示將每一數(shù)據(jù)塊中特征維度，n表示數(shù)據(jù)塊中實(shí)例個(gè)數(shù)，所有實(shí)例的類標(biāo)簽分布表示為Yi={yi}。由特征映射形成隱層矩陣由文獻(xiàn)［10］得到關(guān)于ELM的數(shù)學(xué)模型和KTT條件得到該數(shù)據(jù)塊的ELM模型輸出，即

式中：H表示訓(xùn)練數(shù)據(jù)隱層輸出矩陣；Y為訓(xùn)練數(shù)據(jù)的標(biāo)簽集合；C和I分別表示嶺回歸參數(shù)和單位矩陣。最后采用核函數(shù)HHT(i，j)=K(xi，xj)，(ΩELM)ij=h(xi)·h(xj)=K(xi，xj)代替ELM的隱層映射使神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)趨于穩(wěn)定思想得到OS?KELM輸出模型為

式中：Ω為核函數(shù)矩陣。本文采用徑向基核函數(shù)

式中σ為徑向基函數(shù)。初始設(shè)定基分類器個(gè)數(shù)為k，對(duì)其中每一個(gè)數(shù)據(jù)塊均做以上處理后得到基分類器集成模型為f={f1()x，f2(x)，…，fk(x)}。

當(dāng)?shù)趉+1個(gè)數(shù)據(jù)塊到來(lái)時(shí)，集成模型f對(duì)該數(shù)據(jù)塊中的每個(gè)實(shí)例x進(jìn)行預(yù)測(cè)

式中Conf為標(biāo)簽間置信度。根據(jù)式（4）計(jì)算結(jié)果P(lj|x)，若大于τ，表示該標(biāo)簽屬于此樣本，反之不屬于（本文設(shè)定閾值τ=0），最后所有滿足閾值的類標(biāo)簽集作為當(dāng)前實(shí)例x的類標(biāo)簽Y*。

2.3 基于MuENLForest模型的概念漂移檢測(cè)與模型更新

為處理多標(biāo)簽數(shù)據(jù)流中由于數(shù)據(jù)分布變化引起的概念漂移問(wèn)題，本文引入MuENLForest模型［16］，通過(guò)檢測(cè)新數(shù)據(jù)特征對(duì)應(yīng)的標(biāo)簽數(shù)據(jù)分布發(fā)生變化來(lái)判斷概念漂移是否發(fā)生。隨著前k個(gè)數(shù)據(jù)塊的到來(lái)，所提方法會(huì)相應(yīng)構(gòu)建k個(gè)MuENLTree決策樹(shù)模型組成MuENLForest決策森林模型。其中每個(gè)MuENLTree決策樹(shù)模型是由內(nèi)部節(jié)點(diǎn)和葉節(jié)點(diǎn)組成的二叉樹(shù)，令a=[Xk，Yk]表示第k個(gè)具有預(yù)測(cè)值的訓(xùn)練樣本。每個(gè)內(nèi)部節(jié)點(diǎn)以下劃分策略分為2個(gè)子節(jié)點(diǎn)，其中p1和p2是2個(gè)具有q屬性的聚類中心，aq為a的q投影，q=[q1，q2]，q1和q2分別是從輸入樣本屬性集和特征樣本屬性集中隨機(jī)選擇的K個(gè)屬性，每個(gè)葉子節(jié)點(diǎn)定義半徑為r=maxx∈S‖ ‖a-m的球覆蓋S（即屬于該葉子節(jié)點(diǎn)的所有訓(xùn)練實(shí)例集合），其中m=mean(S)。為了在訓(xùn)練過(guò)程中生成MuENLTree，在構(gòu)建內(nèi)部節(jié)點(diǎn)之前遞歸地劃分訓(xùn)練集，直到滿足以下任何條件：（1）樹(shù)達(dá)到限制高度h；（2）|S|=1；（3）S中的所有實(shí)例具有相同的xq值。對(duì)于MuENLForest的構(gòu)建，采用其預(yù)測(cè)值擴(kuò)充每個(gè)實(shí)例，以便可以同時(shí)考慮特征和標(biāo)簽信息。投影在一組隨機(jī)選擇的屬性上，每個(gè)內(nèi)部節(jié)點(diǎn)基于任一分支上的群集中心進(jìn)行拆分，結(jié)果同一葉節(jié)點(diǎn)內(nèi)的實(shí)例在要素或預(yù)測(cè)值或兩者的某些屬性上必須相似。

構(gòu)造好MuENLForest后，當(dāng)?shù)趉+1個(gè)數(shù)據(jù)塊到來(lái)時(shí)，需要對(duì)該數(shù)據(jù)塊中的每個(gè)未知實(shí)例進(jìn)行類分布變化的檢測(cè)。當(dāng)新實(shí)例到來(lái)后檢測(cè)結(jié)果落在球外即大于半徑r，則認(rèn)為當(dāng)前的實(shí)例數(shù)據(jù)分布發(fā)生變化。統(tǒng)計(jì)新到來(lái)數(shù)據(jù)塊中實(shí)例發(fā)生概念漂移的個(gè)數(shù)是否滿足閾值，若滿足，則認(rèn)為發(fā)生概念漂移，并對(duì)基分類器所有數(shù)據(jù)塊設(shè)置損失函數(shù)2-et以降低其權(quán)重，削弱舊數(shù)據(jù)的影響程度，同時(shí)新的數(shù)據(jù)塊替代效果最差預(yù)測(cè)對(duì)應(yīng)數(shù)據(jù)塊，構(gòu)建新的基分類器C′，設(shè)置新的數(shù)據(jù)塊所在位置權(quán)重為1；若不滿足閾值，則表示無(wú)概念漂移發(fā)生，不引入損失函數(shù)，僅進(jìn)行更新操作構(gòu)建新的基分類器C′，所有分類器權(quán)重設(shè)置為1。

2.4 時(shí)間復(fù)雜度分析

本文算法在樣本(X，Y)上的訓(xùn)練過(guò)程復(fù)雜度為其中|q|表示構(gòu)建MuENLTree時(shí)隨機(jī)選擇分割屬性的個(gè)數(shù)；Q表示候選項(xiàng)目組成的集合；n表示數(shù)據(jù)塊的實(shí)例個(gè)數(shù)；h表示構(gòu)建MuENLTree的最大樹(shù)高；g表示構(gòu)建的MuENLTree的個(gè)數(shù)。Apriori算法時(shí)間復(fù)雜度為表示生成每個(gè)候選項(xiàng)目的復(fù)雜度，s(c)表示計(jì)算候選項(xiàng)目的復(fù)雜度，由于計(jì)算每一個(gè)項(xiàng)目的支持度都需掃描數(shù)據(jù)庫(kù)使s(c)?g(c)，因而上式復(fù)雜度表示為每計(jì)算一個(gè)c的支持度都需要掃描當(dāng)前數(shù)據(jù)塊中單個(gè)實(shí)例數(shù)據(jù)，假定每個(gè)數(shù)據(jù)塊中實(shí)例數(shù)為n，則上式又可以表示為O(∑||Q×n)。OS?KELM的計(jì)算過(guò)程主要體現(xiàn)在使用核函數(shù)K(u，v)代替ELM的隱層映射，使網(wǎng)絡(luò)結(jié)構(gòu)趨于穩(wěn)定，其訓(xùn)練時(shí)間為樣本數(shù)N的3次冪，因而時(shí)間復(fù)雜度為O(n3)。概念漂移檢測(cè)時(shí)間消耗在檢測(cè)器MuENLForest的構(gòu)建過(guò)程，每個(gè)節(jié)點(diǎn)都涉及k個(gè)均值聚類，其中包含2個(gè)具有時(shí)間復(fù)雜度O(|q|n)的聚類。此外還涉及n個(gè)實(shí)例引入樹(shù)高度h限制，因此對(duì)于帶有g(shù)個(gè)MuENLTrees的MuENL?Forest時(shí)間復(fù)雜度為O(|q|ghn)。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集與評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)選擇10個(gè)廣泛用于多標(biāo)簽分類的真實(shí)數(shù)據(jù)集。表1總結(jié)了10組數(shù)據(jù)集的數(shù)據(jù)規(guī)模、屬性維、標(biāo)簽個(gè)數(shù)和標(biāo)簽基數(shù)。

表1 數(shù)據(jù)集Table 1 Datasets

本文的算法評(píng)價(jià)指標(biāo)分類兩類［1］：基于實(shí)例的評(píng)價(jià)指標(biāo)（Example?based metrics）與基于類標(biāo)簽排名的指標(biāo)（Label ranking?based）。其中前者包 括Hamming_loss、Accuracy與F1?measure；后者 包 含Coverage、Ranking loss與Average preci?sion。

3.2 基準(zhǔn)算法與參數(shù)設(shè)置

本文在數(shù)據(jù)集批處理方式上采用數(shù)據(jù)塊方式，其中每個(gè)數(shù)據(jù)塊的大小經(jīng)過(guò)反復(fù)實(shí)驗(yàn)調(diào)整得到最佳實(shí)驗(yàn)效果。對(duì)比實(shí)驗(yàn)選擇了3個(gè)基準(zhǔn)算法，在線序列極限學(xué)習(xí)機(jī)OS?ELM［12］、基于貝葉斯網(wǎng)絡(luò)權(quán)重?fù)p失的半監(jiān)督多標(biāo)簽學(xué)習(xí)方法（DS?BW?MLC）［35］與基于加權(quán)聚類模型的增量式在線多標(biāo)簽分類方法（OMLC?WC）［36］。此外，文中也分別在OS?KELM基礎(chǔ)上增添關(guān)聯(lián)規(guī)則和概念漂移后的實(shí)驗(yàn)對(duì)比。所提算法在實(shí)驗(yàn)運(yùn)算前選取k個(gè)數(shù)據(jù)塊構(gòu)建模型來(lái)預(yù)測(cè)新數(shù)據(jù)分類精度。3個(gè)基準(zhǔn)算法的分類器分別采用ELM、貝葉斯網(wǎng)絡(luò)和聚類模型。為更好地模擬出流式數(shù)據(jù)環(huán)境，在參數(shù)設(shè)置上選取6個(gè)基分類器，基分類器大小根據(jù)不同數(shù)據(jù)集設(shè)置不同值，新到來(lái)數(shù)據(jù)塊大小根據(jù)不同數(shù)據(jù)集設(shè)置不同大小，正則化系數(shù)設(shè)置為{50，100，200，500}。測(cè)試環(huán)境基于Intel Core i5處理器、頻率2.90 GHz和內(nèi)存8 GB的一體機(jī)。

3.3 性能分析

本節(jié)主要考察所提方法的2大實(shí)驗(yàn)性能：一是與3個(gè)基本算法對(duì)比，考察所提方法在多標(biāo)簽數(shù)據(jù)流上的分類性能；另外，由于一些數(shù)據(jù)集內(nèi)部可能存在概念漂移問(wèn)題，導(dǎo)致原始基分類器難以適應(yīng)當(dāng)前概念，所以在所提方法中又引入基分類器更新策略，并通過(guò)實(shí)驗(yàn)驗(yàn)證新增方法在數(shù)據(jù)集上的分類性 能。主要討 論OS?KELM、OS?KELM?Ap、Proposed method與OS?ELM算法 在Yeast、Scene、Corel5k、Enron、Medical數(shù)據(jù) 集 上 結(jié)果對(duì) 比 以 及與DS?BW?MLC和OMLC?WC算 法在20NG、En?ron、IMDBF、OHSUMED、SLASHDOT、TMC2007數(shù)據(jù)集上結(jié)果對(duì)比，如表2～5所示。各類算法描述如下：

表2 2種算法在5個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Table 2 Experimental results of two multi?label algorithms on five datasets

（1）OS?KELM：采用滑動(dòng)窗口方法將數(shù)據(jù)流環(huán)境以數(shù)據(jù)塊形式不斷到來(lái)。選取一定規(guī)模的數(shù)據(jù)塊作為基分類器訓(xùn)練集，使用KELM神經(jīng)網(wǎng)絡(luò)訓(xùn)練得到集成模型對(duì)新數(shù)據(jù)塊預(yù)測(cè)結(jié)果。

（2）OS?KELM?Ap：在OS?KELM基礎(chǔ)上引入關(guān)聯(lián)規(guī)則，利用關(guān)聯(lián)規(guī)則分析標(biāo)簽空間中標(biāo)簽的關(guān)聯(lián)性，在預(yù)測(cè)過(guò)程中對(duì)KELM基分類器的預(yù)測(cè)結(jié)果額外使用關(guān)聯(lián)性調(diào)優(yōu)，得到數(shù)據(jù)塊的最終結(jié)果。

（3）OS?ELM：基于OS?ELM模型對(duì)多標(biāo)簽數(shù)據(jù)流直接進(jìn)行預(yù)測(cè)，模型本身具有迭代優(yōu)化措施，可以很好應(yīng)對(duì)各種概念漂移情況，但數(shù)據(jù)塊規(guī)模過(guò)大對(duì)其計(jì)算過(guò)程的時(shí)間消耗存在負(fù)擔(dān)。

（4）DS?BW?MLC：基于貝葉斯網(wǎng)絡(luò)權(quán)重?fù)p失的半監(jiān)督多標(biāo)簽學(xué)習(xí)方法，從每個(gè)樣本標(biāo)簽空間中自主學(xué)習(xí)標(biāo)簽間關(guān)聯(lián)關(guān)系，使用霍夫丁不等式與標(biāo)簽基數(shù)動(dòng)態(tài)調(diào)整預(yù)測(cè)的標(biāo)簽個(gè)數(shù)，此外還通過(guò)未確定值方法擴(kuò)展標(biāo)簽特征值解決缺失問(wèn)題。

表3 3種算法在5個(gè)數(shù)據(jù)集上2種指標(biāo)的實(shí)驗(yàn)結(jié)果Table 3 Experimental results of three multi?label algorithms on five datasets regarding two evaluation metrics

表4 3種算法在5個(gè)數(shù)據(jù)集上所有指標(biāo)的實(shí)驗(yàn)結(jié)果Table 4 Experimental results of three multi?label algorithms on five datasets regarding all evaluation metrics

表5 3種算法在另外5個(gè)數(shù)據(jù)集上所有指標(biāo)的實(shí)驗(yàn)結(jié)果Table 5 Experimental results of three multi?label algorithms on remaining five datasets regarding all evalua?tion metrics

（5）OMLC?WC：基于加權(quán)聚類模型的流多標(biāo)簽分類方法，利用損失函數(shù)的衰減機(jī)制保證分類器能夠適應(yīng)潛在的概念漂移。

根據(jù)表2～5實(shí)驗(yàn)結(jié)果可知：

（1）由表2所示，本文所提方法在Yeast、Scene、Corel5k數(shù)據(jù)集上的Accuracy、F1?measure上顯著優(yōu)于OS?ELM。因?yàn)樗崴惴ú粌H利用ELM的高效快速高精度優(yōu)勢(shì)，還引入核ELM克服ELM網(wǎng)絡(luò)結(jié)構(gòu)不穩(wěn)定等缺陷，并發(fā)掘到來(lái)數(shù)據(jù)塊標(biāo)簽空間中蘊(yùn)含的標(biāo)簽間相關(guān)性。此外，為應(yīng)對(duì)數(shù)據(jù)流環(huán)境下多標(biāo)簽分類過(guò)程出現(xiàn)由于樣本數(shù)據(jù)分布變化導(dǎo)致精度下降問(wèn)題，構(gòu)建概念漂移檢測(cè)器并使用損失函數(shù)降低歷史數(shù)據(jù)的影響程度，因此實(shí)驗(yàn)結(jié)果顯著優(yōu)于OS?ELM。

（2）通過(guò)比較表2和表4～5中OS?ELM和OS?KELM、OS?KELM?Ap以及所提方法的4組實(shí)驗(yàn)結(jié)果可以得出，OS?KELM在流式環(huán)境中并沒(méi)有OS?ELM分類能力高，原因在于OS?ELM方法對(duì)模型更新過(guò)程中可以充分利用已到來(lái)的所有歷史信息，而OS?KELM只能對(duì)單獨(dú)到來(lái)數(shù)據(jù)塊分別進(jìn)行集成分類器訓(xùn)練，雖然在批處理環(huán)境中引入核函數(shù)技術(shù)相較于極限學(xué)習(xí)機(jī)在分類上有一定優(yōu)勢(shì)，但是在流式環(huán)境中忽略了數(shù)據(jù)之間的關(guān)系和歷史數(shù)據(jù)的保留。在引入標(biāo)簽相關(guān)性的OS?KELM?Ap和添加標(biāo)簽相關(guān)性、概念漂移的所提方法后實(shí)驗(yàn)效果才有明顯提升，通過(guò)4組方法在實(shí)驗(yàn)數(shù)據(jù)集Yeast、Scene、Enron上的Accuracy、F1?measure、Hamming loss評(píng)價(jià)指標(biāo)結(jié)果也驗(yàn)證了方法元素的有效性。

（3）此外與DS?BW?MLC和OMLC?WC在6個(gè)高維特征數(shù)據(jù)集上對(duì)比，表3中實(shí)驗(yàn)結(jié)果可知：在TMC2007和IMDBF、Enron數(shù)據(jù)集上的Average precision實(shí)驗(yàn)指標(biāo)，所提算法優(yōu)于DS?BW?MLC；在SLASHDOT和OHSUMEDF上的Average precision優(yōu)于OMLC?WC，其他5個(gè)數(shù)據(jù)集上所提算法在Ranking loss優(yōu)于OMLC?WC。原因在于所提算法在高維大樣本數(shù)據(jù)集的處理能力有待改進(jìn)，僅依賴標(biāo)簽相關(guān)性和概念漂移檢測(cè)技術(shù)遠(yuǎn)遠(yuǎn)不夠，還應(yīng)考慮高維數(shù)據(jù)環(huán)境下的特征降維。

（4）在TMC2007數(shù)據(jù)集上，由于數(shù)據(jù)集中舊樣本數(shù)據(jù)占比較新樣本更重，所提方法更新策略雖然在一定程度上能夠適應(yīng)新的數(shù)據(jù)，但是忽略了對(duì)于歷史數(shù)據(jù)的保留，針對(duì)這類數(shù)據(jù)集本文方法在與未引入更新策略的OS?KELM和關(guān)聯(lián)規(guī)則OS?KELM?Ap實(shí)驗(yàn)效果對(duì)比明顯降低。

（5）所提方法使用集成模型的核極限學(xué)習(xí)機(jī)與基于Apriori算法的類標(biāo)簽相關(guān)性分析以及基于MuENLForest模型的概念漂移檢測(cè)與模型更新機(jī)制。為驗(yàn)證所用技術(shù)有效性，本文分別在10個(gè)數(shù)據(jù)集上做增量式自對(duì)比實(shí)驗(yàn)，結(jié)果如表4～5所示。從10個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果可以看出，所提方法明顯優(yōu)于OS?KELM和OS?KELM?Ap，進(jìn)一步反應(yīng)出在多標(biāo)簽數(shù)據(jù)流分類過(guò)程中合理使用標(biāo)簽間相關(guān)性、適應(yīng)概念漂移方法的重要性。無(wú)論是在低維的Yeast、Scene還是高維20NG、IMDBF數(shù)據(jù)集上，所提方法都比OS?KELM在所有評(píng)價(jià)指標(biāo)上實(shí)驗(yàn)結(jié)果有很大提升。為單獨(dú)驗(yàn)證標(biāo)簽相關(guān)性的作用，對(duì)比OS?KELM與OS?KELM?Ap的實(shí)驗(yàn)結(jié)果可知，在數(shù)據(jù)集Yeast、Scene、Enron上Accuracy、F1?measure提升效果明顯，但在高維數(shù)據(jù)集上由于部分?jǐn)?shù)據(jù)集的標(biāo)簽平均相關(guān)度不高（樣本數(shù)據(jù)標(biāo)簽間的相關(guān)性值，取該數(shù)據(jù)集整體標(biāo)簽空間中標(biāo)簽對(duì)的相關(guān)性平均值，例如數(shù)據(jù)集20NG的標(biāo)簽平均相關(guān)度為0.364 1、OHSUMED：0.380 2、Enron：0.881 1、Scene：0.674 4）導(dǎo)致標(biāo)簽相關(guān)性技術(shù)不能很好地發(fā)揮作用，實(shí)驗(yàn)結(jié)果也顯示出標(biāo)簽相關(guān)性技術(shù)帶來(lái)的提升效果不明顯。但所提方法的概念漂移檢測(cè)與模型更新機(jī)制有效性與OS?KELM?Ap實(shí)驗(yàn)相比，無(wú)論是高維數(shù)據(jù)TMC2007、SLASHDOT和OHSUMEDF還是低維數(shù)據(jù)Yeast、Scene、Corel5k，實(shí)驗(yàn)精度Accuracy、Average precision、Coverage、Ranking loss顯著提高，驗(yàn)證了概念漂移機(jī)制的有效性，可以及時(shí)發(fā)現(xiàn)新樣本標(biāo)簽數(shù)據(jù)分布變化，集成模型迭代更新的正確時(shí)機(jī)。

（6）使用Nemenyi?Test檢驗(yàn)對(duì)比算法的實(shí)驗(yàn)性能是否存在顯著差異。將本文工作的統(tǒng)計(jì)檢驗(yàn)視為控制算法，記錄每個(gè)算法在運(yùn)行數(shù)據(jù)集上的平均等級(jí)，其中各算法之間的差異用臨界差異（Critical dif?ference，CD）校準(zhǔn)。如果它們的平均等級(jí)相差至少1個(gè)CD（本文中CD分別為2.728和2.097 6；比較算法分別為4個(gè)和5個(gè)，數(shù)據(jù)集N=5），則認(rèn)為性能差異是顯著的。

為了在直觀上顯示算法間的性能差異，圖2～6給出了相應(yīng)指標(biāo)下的CD圖，其在Accuracy、Aver?age precision、Ranking loss等 方 面。在 每 個(gè)CD圖中，算法間的平均等級(jí)沿著軸標(biāo)記右下方的等級(jí)。此外，任何具有一個(gè)CD內(nèi)的平均等級(jí)與本文所提算法的平均等級(jí)的比較算法用粗線相互連接，否則其性能被認(rèn)為與本文算法存在顯著差異。根據(jù)實(shí)驗(yàn)結(jié)果，所提算法在統(tǒng)計(jì)顯著性方面效果良好。

圖2 在Accuracy度量標(biāo)準(zhǔn)上的統(tǒng)計(jì)結(jié)果Fig.2 Statistic test on Accuracy

圖3 在F1-measure度量標(biāo)準(zhǔn)上的統(tǒng)計(jì)結(jié)果Fig.3 Statistic test on F1-measure

圖4 在Hamming loss度量標(biāo)準(zhǔn)上的統(tǒng)計(jì)結(jié)果Fig.4 Statistic test on Hamming loss

圖5 在Ranking loss度量標(biāo)準(zhǔn)上的統(tǒng)計(jì)結(jié)果Fig.5 Statistic test on Ranking loss

圖6 在Average precision度量標(biāo)準(zhǔn)上的統(tǒng)計(jì)結(jié)果Fig.6 Statistic test on Average precision

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

本文提出一種基于核極限學(xué)習(xí)機(jī)的多標(biāo)簽數(shù)據(jù)流集成分類方法，利用核極限學(xué)習(xí)機(jī)通過(guò)對(duì)已有的多標(biāo)簽信息進(jìn)行在線分類預(yù)測(cè)處理，為充分利用潛在標(biāo)簽集合間的相關(guān)性，在分類過(guò)程中利用Apriori算法得到標(biāo)簽間關(guān)聯(lián)規(guī)則用以提高分類精度。同時(shí)為了適應(yīng)不斷到來(lái)的新數(shù)據(jù)可能引起概念漂移問(wèn)題，本文采用利用舊數(shù)據(jù)構(gòu)建概念漂移檢測(cè)森林，并對(duì)分類器更新策略采用最差原理，每次使用由最新數(shù)據(jù)塊得到的分類器替換當(dāng)前效果最差的分類器來(lái)完成對(duì)基分類器的更新操作。大量對(duì)比實(shí)驗(yàn)表明，所提方法具有良好的分類效果，同時(shí)能夠適應(yīng)小樣本數(shù)據(jù)流中概念漂移問(wèn)題。下一步工作將針對(duì)高維空間中的大樣本稀疏問(wèn)題展開(kāi)研究探討，并將進(jìn)一步合理利用已拋棄的有效歷史數(shù)據(jù)對(duì)未來(lái)重現(xiàn)概念漂移的問(wèn)題研究。