基于RD-PSO優(yōu)化算法的自適應(yīng)數(shù)據(jù)流分類

鄒勁松 李 芳

1(重慶水利電力職業(yè)技術(shù)學(xué)院普天大數(shù)據(jù)產(chǎn)業(yè)學(xué)院 重慶 402160) 2(重慶大學(xué)計(jì)算機(jī)學(xué)院 重慶 400044)

0 引 言

由于無處不在的互聯(lián)網(wǎng)和激增的移動設(shè)備，各種來源的數(shù)據(jù)流數(shù)量指數(shù)級增長，這樣的流通常以高速和數(shù)據(jù)分布隨時(shí)間的變化為特征[1]，非平穩(wěn)數(shù)據(jù)流分類在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域的重要性與日俱增。概念漂移分為多種類型，如突變式、漸進(jìn)式和重現(xiàn)式等[2]。其中：突發(fā)式概念漂移指數(shù)據(jù)的分布突然被新的分布所取代；漸進(jìn)式概念漂移是指傳入數(shù)據(jù)的新分布比例會提高，而來自前一分布的數(shù)據(jù)的比例會隨著時(shí)間的推移而下降；重現(xiàn)式概念漂移指相同的舊數(shù)據(jù)分布在經(jīng)過一段時(shí)間后以不同的分布重新出現(xiàn)[3-4]。比較理想的非平穩(wěn)數(shù)據(jù)流分類方法應(yīng)能夠在最小化計(jì)算復(fù)雜度的同時(shí)具有最小可能的誤分類率，并可以快速適應(yīng)可能的概念漂移。

集成學(xué)習(xí)技術(shù)使用投票機(jī)制創(chuàng)建并組合多個(gè)分類器，以建立單個(gè)類作為數(shù)據(jù)實(shí)例的輸出[5-6]。由于其在訓(xùn)練和更新分類器方面的靈活性，集成技術(shù)對非平穩(wěn)環(huán)境中的流分類有較好的性能。粒子群優(yōu)化(Particle Swarm Optimisation, PSO)算法是通過模擬鳥群或魚群中覓食行為而發(fā)展起來的一種基于群體協(xié)作的隨機(jī)搜索算法[7-8]，它的主要目標(biāo)是找到函數(shù)的全局最小值。PSO通過創(chuàng)建候選解的初始隨機(jī)群來進(jìn)行初始化，然后粒子以動態(tài)速度在搜索空間中適應(yīng)性移動以找到最佳解決方案[9-10]。

近年來，有關(guān)非平穩(wěn)數(shù)據(jù)流分類已取得若干成果。文獻(xiàn)[11]提出了一種基于增量式半監(jiān)督模糊聚類算法的數(shù)據(jù)流分類方法，用來處理不同類型的數(shù)據(jù)。它創(chuàng)建與類數(shù)量相同的群集，但是固定數(shù)量的群集可能無法充分捕獲流數(shù)據(jù)的演變結(jié)構(gòu)。文獻(xiàn)[12]提出了基于規(guī)則的多標(biāo)簽分類方法和基于連續(xù)數(shù)據(jù)流的集成學(xué)習(xí)方法，該方法基于目標(biāo)回歸算法將類標(biāo)簽子集的規(guī)則專門化，而不是通常的局部(每個(gè)輸出的單個(gè)模型)或全局(所有輸出的一個(gè)模型)方法。文獻(xiàn)[13]提出了一種用于進(jìn)化數(shù)據(jù)流分類的自適應(yīng)隨機(jī)森林(Adaptive Random Forest, ARF)算法，它通過在原始數(shù)據(jù)的重新采樣版本上對決策樹進(jìn)行訓(xùn)練和隨機(jī)選擇少量可在每個(gè)節(jié)點(diǎn)處檢查以進(jìn)行拆分的特征來生成決策樹。該方法是一種使用機(jī)制檢測概念漂移并立即作出反應(yīng)的顯式方法，其最大缺點(diǎn)在于對噪聲比較敏感，導(dǎo)致準(zhǔn)確性會因?yàn)殄e誤檢測到概念漂移而降低。

在研究了現(xiàn)有數(shù)據(jù)流分類的基礎(chǔ)上，為了有效地適應(yīng)最新的數(shù)據(jù)分布類型，本文提出一種基于復(fù)制動力學(xué)和粒子群優(yōu)化(RD-PSO)的自適應(yīng)數(shù)據(jù)流分類技術(shù)，RD-PSO通過從目標(biāo)數(shù)據(jù)集的屬性集合中隨機(jī)選擇特征生成三個(gè)不同分類類型的分類器集合，通過將復(fù)制動力學(xué)(Replicator Dynamics, RD)應(yīng)用于集合的所有層來使所選擇集合的每一層需要的分類類型的數(shù)量隨著層中每種分類類型中的特征數(shù)量的增加而減少，從而實(shí)現(xiàn)無縫適應(yīng)最新數(shù)據(jù)分布類型的目的，使用粒子群優(yōu)化技術(shù)的非規(guī)范版本來確保快速適應(yīng)不同的概念漂移。

1 基于RD-PSO的數(shù)據(jù)流分類

RD-PSO算法通過從目標(biāo)數(shù)據(jù)集的屬性集合中隨機(jī)選擇特征(子空間)生成的不同分類類型的三層次分類器集合，應(yīng)用RD-PSO算法來優(yōu)化所有層，以此來無縫且有效地適應(yīng)最新的數(shù)據(jù)分布類型。

圖1給出了三層的RD-PSO算法的示意圖。左邊三角形表示分類類型的范圍及它們在每一層中所覆蓋的特征，直角三角形表示每種分類類型向全局和局部最優(yōu)移動的速度，分類類型越小(特征越少)，它們向最優(yōu)方向移動的速度越快。

圖1 三層RD-PSO算法描述

1.1 創(chuàng)建分層

本文算法使用每個(gè)層中特征的隨機(jī)子空間創(chuàng)建三個(gè)不同的包含特定數(shù)量類型的層，每個(gè)分類類型覆蓋來自預(yù)定義特征池的特定百分比的特征，每種類型中特征的百分比與每層中的類型數(shù)之間呈負(fù)線性相關(guān)。換言之，每種類型在同一層中需要覆蓋的要素?cái)?shù)量隨著每一層內(nèi)的類型數(shù)量的變大而減小，即：

(1)

式中：m表示類型的總數(shù)；n表示要為每種類型選擇的特征總數(shù)；f表示目標(biāo)數(shù)據(jù)流的特征總數(shù)。

每個(gè)層的參數(shù)一旦被指定，就從所有屬性的集合中隨機(jī)選擇nl個(gè)特征(屬性)，此步驟對每層重復(fù)ml次，l表示層號(l=1,2,3)。因此，在此步驟結(jié)束時(shí)每層都有ml個(gè)獨(dú)立的類型。

1.2 復(fù)制動力學(xué)

對所創(chuàng)建集合的每一層，應(yīng)用復(fù)制動力學(xué)(RD)選擇每層中的分類類型和特征的數(shù)量，使得該層需要的分類類型的數(shù)量隨著層中每種分類類型的特征數(shù)量的增高而降低。

(1) RD概述。RD是選擇過程的顯性模型，它將表現(xiàn)好于平均收益的類型規(guī)模增加，而那些表現(xiàn)比平均收益差的類型規(guī)模減少。該模型在離散時(shí)間進(jìn)行選擇，下一次選擇中的每種類型群體作為該類型的收益及其在群體中的當(dāng)前比例的函數(shù)，由式(2)給出。

(2)

式中：W表示游戲的正常形式的支付矩陣；(Wx)i表示個(gè)人的預(yù)期收益；xTWx表示人口狀態(tài)x的平均收益。

在所設(shè)計(jì)的方法中，分類類型是目標(biāo)數(shù)據(jù)流的特征總數(shù)的隨機(jī)子空間，一種類型的收益是同一類型內(nèi)部分類器的平均精度，而預(yù)期收益是所有現(xiàn)有分類器的平均精度。

(2) 初始訓(xùn)練。所有層被創(chuàng)建后，集合使用RD開始訓(xùn)練數(shù)據(jù)。在原始RD中，需要添加到子空間的樹的數(shù)量分別為：

(3)

(4)

式中：Ta(i)表示要添加的樹的數(shù)量；Tr(i)表示要移除的樹的數(shù)量；a(ti)表示正在處理的子空間i的精度；m表示類型的總數(shù)；Tn(i)表示當(dāng)前在子空間i內(nèi)的樹的總數(shù)。

當(dāng)添加到子空間的樹的數(shù)量大于1時(shí)，將使用引導(dǎo)聚合模型創(chuàng)建不同的樹，此時(shí)輸入數(shù)據(jù)用于測試和訓(xùn)練，而不能進(jìn)行先驗(yàn)評估，因?yàn)樵诿總€(gè)時(shí)間步驟中只能創(chuàng)建一棵樹，但是因?yàn)橥镀蹦康慕o它分配更高的權(quán)重，因此權(quán)重為2的樹在投票機(jī)制中有更高的影響。該策略中的移除機(jī)制基于分類器的性能，例如，當(dāng)移除的樹的數(shù)量為2時(shí)，在最后的數(shù)據(jù)塊里從集合中移除兩個(gè)最不準(zhǔn)確的樹。

(3) 投票階段。多數(shù)投票通過式(5)獲得的權(quán)重來組合每一層的輸出從而確定集合的輸出。

Wi=Wi-1+α(Pi-1-Ai-1)

(5)

式中：Wi-1表示第(i-1)個(gè)數(shù)據(jù)塊上的層的權(quán)重；Pi-1表示第(i-1)個(gè)數(shù)據(jù)塊上同一層的精度；Ai-1表示第(i-1)個(gè)數(shù)據(jù)塊上所有層的平均精度；α表示最近數(shù)據(jù)的系數(shù)，該系數(shù)是本文算法的任意參數(shù)(α>1)。

(4) 評估階段。評估階段通過計(jì)算其準(zhǔn)確性對每個(gè)類型的決策樹進(jìn)行評估以對輸入實(shí)例進(jìn)行分類，每種類型的精確度是其組成決策樹的平均精確度，整個(gè)集合的精確度可以用式(6)來確定。

(6)

式中：ci表示第i個(gè)數(shù)據(jù)塊中正確分類的實(shí)例數(shù)量；db表示每個(gè)數(shù)據(jù)塊中的實(shí)例總數(shù)。

式中：a(ti)表示第i種類型的精度；m表示類型的總數(shù)；grow表示添加新的分類器/類型；shrink表示去除性能差的分類器/類型。本文預(yù)期收益被設(shè)置為每一層中所有類型的平均精確度。

為了設(shè)置框架內(nèi)分類器(決策樹)數(shù)量的邊界，為集合中的所有類型設(shè)置了max=10的任意上限，一旦超過了一種類型分類器的數(shù)量，就會移除相同類型的性能最差的決策樹，從而為新構(gòu)建的分類器騰出空間。為了防止類型被完全刪除，將min=1作為下限分配給所有類型。

1.3 粒子群優(yōu)化

粒子群優(yōu)化通過創(chuàng)建候選解的初始隨機(jī)群來進(jìn)行初始化，然后粒子以動態(tài)速度在搜索空間中移動以找到最佳解決方案。粒子的運(yùn)動由稱為先前最佳(previous best, pbest)和全局最佳(global best, gbest)這兩個(gè)極值來更新自己，pbest位置是整個(gè)歷史中粒子本身的最優(yōu)解，gbest位置是整個(gè)群體中所有粒子的最優(yōu)解，在每次迭代時(shí)重復(fù)該過程以便發(fā)現(xiàn)令人滿意的解決方案。粒子的速度(V)和位置(P)分別根據(jù)式(9)和式(10)更新。

Vi(t+1)=ωVi(t)+r1(pbest(i,t)-Pi(t))+r2(gbest(t)-Pi(t))

(9)

Pi(t+1)=Pi(t)+Vi(t+1)

(10)

式中：ω表示用于平衡全局和局部開發(fā)的慣性權(quán)重；r1和r2為加速度系數(shù)。

典型的PSO由于針對靜態(tài)數(shù)據(jù)進(jìn)行迭代導(dǎo)致只有一個(gè)可能的最優(yōu)解。在數(shù)據(jù)流分類任務(wù)中數(shù)據(jù)以在線方式出現(xiàn)，最優(yōu)解會隨著時(shí)間而變化，因此本文使用非規(guī)范化的PSO來優(yōu)化每層內(nèi)部類型特征的組合。PSO將所有隨機(jī)創(chuàng)建的類型作為其輸入，并嘗試在每次迭代(接收到新的數(shù)據(jù)塊時(shí))中以指定的速度將它們移動到全局最優(yōu)和局部最優(yōu)解決方案類型。“將粒子以一定速度移動到特定空間”是指將粒子特征的組合進(jìn)行重組，使其類似于具有速度的特定特征子空間。

在本文算法中，對于第3層、第2層和第1層，常數(shù)β的值分別被任意分配為1、0.7和0.4，因此在每種類型中具有最少特征數(shù)的第3層中的最大速度被設(shè)置為100%，類似地，第2層和第1層的最大速度分別設(shè)置為70%和40%。

PSO在本文算法的每一層中單獨(dú)執(zhí)行，并在集合接收的每個(gè)數(shù)據(jù)塊中迭代。結(jié)果集合的每一層內(nèi)的粒子(類型)以指定的速度向同一層的全局最優(yōu)和局部最優(yōu)移動，該速度是基于它們在最后一個(gè)數(shù)據(jù)塊上的性能計(jì)算的，其中它們的真實(shí)標(biāo)簽是已知的。注意，PSO的每次迭代僅在RD處理相同的數(shù)據(jù)塊之后才開始。

2 實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證本文算法的性能，本文在Intel Core i7-4702MQ CPU @2.20 GHz和8 GB RAM的機(jī)器上進(jìn)行實(shí)驗(yàn)，所有測試均在大規(guī)模在線分析(Massive Online Analysis, MOA)平臺上實(shí)現(xiàn)，MOA是一個(gè)基于WEKA用Java實(shí)現(xiàn)的數(shù)據(jù)流在線分類、聚類平臺。選取模擬概念隨時(shí)間漂移的合成數(shù)據(jù)流生成器SEA進(jìn)行實(shí)驗(yàn)，SEA可以在三維空間生成隨機(jī)點(diǎn)。數(shù)據(jù)塊中的實(shí)例數(shù)為1 000，每個(gè)分類類型中分類器的數(shù)量為1到10，第1層到第3層的初始權(quán)重分別為1、2和4，最大速度閾值為x=2%。

圖2給出了本文算法與自適應(yīng)隨機(jī)森林(ARF)算法[13]、動態(tài)加權(quán)多數(shù)(DWM)算法和OSBoost算法在所有數(shù)據(jù)集的即時(shí)和延遲設(shè)置中的總體平均精度。即時(shí)設(shè)置是指使用優(yōu)先評估技術(shù)通過特定方法將所選數(shù)據(jù)集通過特定方法傳遞并立即訪問實(shí)例的真實(shí)標(biāo)簽；延遲設(shè)置是指實(shí)例的真實(shí)標(biāo)簽在指定的延遲后顯示給整體，本文延遲參數(shù)設(shè)置為1 000，即在傳遞1 000個(gè)實(shí)例后每個(gè)實(shí)例的實(shí)際標(biāo)簽都會顯示給系統(tǒng)。

圖2 各算法在即時(shí)和延遲設(shè)置中的總體平均準(zhǔn)確度

可以看出本文算法在兩種設(shè)置中都具有最佳的平均準(zhǔn)確度，這是因?yàn)楸疚乃惴ㄡ槍Σ煌沫h(huán)境和概念漂移采用不同的策略和使用不同的PSO優(yōu)化層及其動態(tài)權(quán)重。

表1給出了各算法在即時(shí)設(shè)置中的評估時(shí)間。由于延遲設(shè)置中的評估時(shí)間類似于即時(shí)設(shè)置，本文僅給出即時(shí)設(shè)置的結(jié)果。可以看出，本文方法的總體評估時(shí)間不是最優(yōu)，這是由于集合中分類器的數(shù)量隨著目標(biāo)數(shù)據(jù)流中的特征數(shù)量而增加，這些限制可以通過應(yīng)用并行化獨(dú)立處理來克服，這是未來研究的內(nèi)容。

表1 即使設(shè)置中各算法的評估時(shí)間 s

圖3到圖6將不同類型的概念漂移添加到由SEA數(shù)據(jù)流生成器生成的數(shù)據(jù)集。其中：圖3給出了本文算法與ARF算法、DWM算法和OSBoost算法在實(shí)例編號200k添加寬度為1的突變式漂移的適應(yīng)情況；圖4給出了各算法以10k的寬度添加漸變式漂移的適應(yīng)情況；圖5給出了各算法在實(shí)例編號600k處添加寬度為1的重現(xiàn)式漂移的適應(yīng)情況；圖6給出了各算法在實(shí)例編號為795k時(shí)以10k的寬度添加重現(xiàn)漸變式漂移的適應(yīng)情況。

圖3 各算法在實(shí)例編號200k時(shí)寬度為1的突變式漂移

圖4 各算法以10k的寬度添加漸變式漂移

圖5 各算法在實(shí)例編號600k處寬度為1k的重現(xiàn)式漂移

圖6 各算法在實(shí)例編號795k處寬度為10k的重現(xiàn)漸變式漂移

可以看出，本文算法在突變式漂移和漸變式漂移以及重現(xiàn)式漂移中均可以快速地恢復(fù)，并且具有最高的精確度。這是因?yàn)楸疚乃惴ㄊ褂酶倪M(jìn)的RD來無縫地不同的概念漂移，使用PSO技術(shù)的非規(guī)范版本對每一層進(jìn)行優(yōu)化，使每一層中的類型以指定的速度走向局部最優(yōu)和全局最優(yōu)。因此，本文算法比DWM和OSBoot有更好的準(zhǔn)確性和魯棒性。

3 結(jié) 語

為了使數(shù)據(jù)挖掘和優(yōu)化技術(shù)適應(yīng)概念漂移，本文提出一種基于復(fù)制動力學(xué)和粒子群優(yōu)化的自適應(yīng)數(shù)據(jù)流分類技術(shù)。該技術(shù)基于三層體系結(jié)構(gòu)創(chuàng)建不同大小的分類類型，不同的分類類型通過從目標(biāo)數(shù)據(jù)流的特征池中隨機(jī)選擇一定百分比的特征來創(chuàng)建，使用改進(jìn)的RD通過增加表現(xiàn)好的類型規(guī)模和減少表現(xiàn)差類型的樹的規(guī)模來無縫地適應(yīng)不同的概念漂移，所有分類類型中的所選特征組合分別使用粒子群優(yōu)化技術(shù)的非規(guī)范版本對每一層進(jìn)行優(yōu)化，使每一層中的類型以指定的速度走向局部最優(yōu)和全局最優(yōu)。實(shí)驗(yàn)表明，本文算法在準(zhǔn)確性和魯棒性方面均優(yōu)于現(xiàn)有方法，但其總體評估時(shí)間不是最優(yōu)。未來的工作是并行化獨(dú)立操作的優(yōu)化層來處理具有大量特征的目標(biāo)數(shù)據(jù)流以減少評估時(shí)間，并設(shè)計(jì)一種方法來選擇動態(tài)使用最大允許速度的閾值參數(shù)。