基于RD-PSO優化算法的自適應數據流分類

鄒勁松 李 芳

1(重慶水利電力職業技術學院普天大數據產業學院 重慶 402160) 2(重慶大學計算機學院 重慶 400044)

0 引 言

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

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

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

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

1 基于RD-PSO的數據流分類

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

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

圖1 三層RD-PSO算法描述

1.1 創建分層

本文算法使用每個層中特征的隨機子空間創建三個不同的包含特定數量類型的層，每個分類類型覆蓋來自預定義特征池的特定百分比的特征，每種類型中特征的百分比與每層中的類型數之間呈負線性相關。換言之，每種類型在同一層中需要覆蓋的要素數量隨著每一層內的類型數量的變大而減小，即：

(1)

式中：m表示類型的總數；n表示要為每種類型選擇的特征總數；f表示目標數據流的特征總數。

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

1.2 復制動力學

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

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

(2)

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

在所設計的方法中，分類類型是目標數據流的特征總數的隨機子空間，一種類型的收益是同一類型內部分類器的平均精度，而預期收益是所有現有分類器的平均精度。

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

(3)

(4)

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

當添加到子空間的樹的數量大于1時，將使用引導聚合模型創建不同的樹，此時輸入數據用于測試和訓練，而不能進行先驗評估，因為在每個時間步驟中只能創建一棵樹，但是因為投票目的給它分配更高的權重，因此權重為2的樹在投票機制中有更高的影響。該策略中的移除機制基于分類器的性能，例如，當移除的樹的數量為2時，在最后的數據塊里從集合中移除兩個最不準確的樹。

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

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

(5)

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

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

(6)

式中：ci表示第i個數據塊中正確分類的實例數量；db表示每個數據塊中的實例總數。

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

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

1.3 粒子群優化

粒子群優化通過創建候選解的初始隨機群來進行初始化，然后粒子以動態速度在搜索空間中移動以找到最佳解決方案。粒子的運動由稱為先前最佳(previous best, pbest)和全局最佳(global best, gbest)這兩個極值來更新自己，pbest位置是整個歷史中粒子本身的最優解，gbest位置是整個群體中所有粒子的最優解，在每次迭代時重復該過程以便發現令人滿意的解決方案。粒子的速度(V)和位置(P)分別根據式(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)

式中：ω表示用于平衡全局和局部開發的慣性權重；r1和r2為加速度系數。

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

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

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

2 實驗與結果分析

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

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

圖2 各算法在即時和延遲設置中的總體平均準確度

可以看出本文算法在兩種設置中都具有最佳的平均準確度，這是因為本文算法針對不同的環境和概念漂移采用不同的策略和使用不同的PSO優化層及其動態權重。

表1給出了各算法在即時設置中的評估時間。由于延遲設置中的評估時間類似于即時設置，本文僅給出即時設置的結果。可以看出，本文方法的總體評估時間不是最優，這是由于集合中分類器的數量隨著目標數據流中的特征數量而增加，這些限制可以通過應用并行化獨立處理來克服，這是未來研究的內容。

表1 即使設置中各算法的評估時間 s

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

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

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

圖5 各算法在實例編號600k處寬度為1k的重現式漂移

圖6 各算法在實例編號795k處寬度為10k的重現漸變式漂移

可以看出，本文算法在突變式漂移和漸變式漂移以及重現式漂移中均可以快速地恢復，并且具有最高的精確度。這是因為本文算法使用改進的RD來無縫地不同的概念漂移，使用PSO技術的非規范版本對每一層進行優化，使每一層中的類型以指定的速度走向局部最優和全局最優。因此，本文算法比DWM和OSBoot有更好的準確性和魯棒性。

3 結 語

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