面向分布式漂移數據流的集成分類模型

尹春勇，張幗杰

（南京信息工程大學計算機與軟件學院，南京 210044）

0 引言

移動互聯網、傳感器網絡以及人工智能技術的快速發展產生了海量的數據，稱之為“大數據”，這些數據具有4V 屬性［1］：規模大（Volume），聚集速度快（Velocity），類型多（Variety），價值大（Value）。目前，大數據知識挖掘問題已經受到國內外學者和研究機構的廣泛關注，并且大數據挖掘技術已經得到廣泛運用。2013年，Wu等［2］探討了大數據分析的核心問題，并設計了一個大數據挖掘的核心模型；2017 年，Moreno［3］等將大數據分析技術應用于智慧城市，提出了一種適用于不同智慧城市應用場景的基于物聯網的通用體系結構；2019 年，Edstrom 等［4］在移動設備硬件設計過程中引入大數據挖掘技術，提出了一種低成本的自恢復視頻存儲系統，有效地解決了視頻數據量大、計算量大帶來的能耗問題。

在大型的電子商務網站交易系統、銀行業務系統、網絡監控、傳感器網絡等應用場景中，大數據都呈現出了分布式和流動性的特征［5-6］，因此，本文的研究重點是具有分布式和流動性技術特征的大數據的分類方法。流式數據也稱為數據流［7］，可以看作一個有序的數據序列，具有實時、快速、連續、無限等特點，在網絡監控系統中尤為常見，表現為網絡流量隨時間增長，并且隱藏在數據中的知識在動態變化。分布式數據流是指各個節點數據獨立但是邏輯上關聯的數據流［8］，也就是說，雖然數據分布在不同地理位置的局部節點上，但是這些數據有相同的屬性集，將局部數據匯總到中心節點，可以學習到性能更好的全局分類器。

分布式數據流挖掘系統既要有局部節點的分析，又要有全局性的模式發現。局部節點的分析處理側重實時性和高效性，全局分類模式旨在構造全局共享的分類器。整個分布式數據流分類系統由三個部分組成：局部節點數據收集、數據傳輸和全局分類器的構建。最經典的層次式分布式數據流挖掘框架DS-means模型［9］將挖掘任務分成三個步驟：局部聚類、模式傳輸和全局聚類，該模型在聚類操作中采用的是經典的無監督K-means算法，中心節點的k值設定根據局部聚類結果動態變化。

由于分布式數據流挖掘系統涉及數據的傳輸，就必須要考慮到通信的代價，因此，如何在不影響全局分類器精度的情況下降低通信代價是系統設計的關鍵科學問題［10］。目前使用較多的策略是局部節點只向中心節點傳輸關鍵的統計數據而非原始數據，最經典的算法是2008 年Masud 等［11］提出的微簇算法，該算法將局部節點的原始數據先進行K-means 聚類，然后提取簇的統計信息，如方差、均值、樣本數目等，但是這個是針對單數據流的。后來Wang 等［12］設計了一個面向分布式數據流的挖掘框架，提出的數據概要思想也是向中心節點傳輸統計值，這類思想能夠有效地降低數據傳輸代價，避免帶寬有限帶來的通信限制。

除此之外，數據在經歷局部挖掘和傳輸后質量會有所下降，因此，構造的全局共享分類器需要具備一定的抗噪性能。集成學習技術相對成熟，具有很好的魯棒性和預測能力，2017年，毛國君等［13］在微簇思想的基礎上，提出了BDS-ensemble模型，該模型在構建全局分類器時就是采用了集成學習的方法，該方法可以歸納為學習樣本的淘汰策略，即被正確預測的學習樣本將會被淘汰，不再用于其他弱分類器的訓練，這種策略能夠提高對樣本的覆蓋度。

此外，集成學習還可以處理數據流中出現的概念漂移［14］現象。概念漂移是數據流中一個常見的現象，會很大程度地影響數據流分類算法的性能，它的表現形式是數據流中的實例屬性和類別標簽的映射隨著時間變化，導致預先訓練的分類器無法適應新的實例。目前，解決概念漂移主要有三種方法：窗口技術、漂移檢測和集成方法。窗口技術最經典的是概念自適應快速決策樹（Concept-adaptive Very Fast Decision Tree，CVFDT）算法［15］，該算法雖然能適應數據流中的動態變化，但是，窗口大小難以確定，設定太大會影響對概念漂移的檢測實時性，設定太小則會增加計算量，影響整個分類器的性能。漂移檢測器是一種能夠及時檢測出數據流分布變化的方法，檢測原理通常是基于分類器的表現或者新到來數據本身的信息。漂移檢測方法（Drift Detection Method，DDM）［16］是經典的基于統計過程控制的檢測器，該方法認為在分類器訓練方法收斂的情況下，分類器的錯誤率會隨著訓練樣本數目的增加而減小，否則，證明數據流中存在概念漂移。ADWIN［17］通過比較兩個時間窗口的平均值來檢測數據分布的變化，當兩個時間窗口的平均值變化較大時，則說明發生了概念漂移。集成學習方法是將多個弱分類器通過加權等方式組合成集成分類器，集成學習的框架如圖1所示。

圖1 集成學習框架Fig.1 Ensemble learning framework

在集成學習中，基分類器的訓練數據一般是由原始數據集bootstrap（有放回）抽樣所得，或者是將原始數據集劃分成n個子集，用子集訓練不同的基分類器，這樣可以保持基分類器的多樣性。基分類器的組合策略有多種，最主流的是選擇多數分類器給出的預測結果作為整個集成分類器的分類結果。現有的研究表明，集成學習比單一的分類器預測準確率更高，并且具有很好的魯棒性。在數據流分類算法中，集成方法可以分為兩種：基于塊和在線學習方法。基于塊的方法是將到達的實例分為固定大小的數據塊，對每個數據塊進行分類器的訓練，這種方法對時間和內存的要求比較高；在線學習方法是對到來的訓練實例進行增量學習，學習出一個從一組屬性值到一個類標的映射函數［18］，可以滿足時效和內存的限制，但是在分類準確率上稍遜于基于塊的方法。基于塊的方法中最經典的是數據流集成算法（Stream Ensemble Algorithm，SEA）［19］，該算法一直從新的數據塊中學習新的分類器，并將分類器加入到集成模型中，當基分類器的數量達到上限，新創建的分類器就會替代過時分類器（分類性能比新分類器差），由于基分類器是根據不同的數據塊創建的，因此該算法能夠保持基分類器的多樣性，避免過擬合的情況發生。在線學習方法最經典的是動態加權多數投票（Dynamic Weighted Majority，DWM）算法［20］，該算法中的基分類器的權重是動態更新的，當基分類預測錯誤，它的權重會相應減小。當集成模型對訓練實例錯誤分類，則會創建新的分類器重新學習新的概念，權重太小的分類器會被淘汰，每次刪除和添加分類器，權重會進行歸一化操作，避免新的分類器權重過大，對整個集成分類結果起主導作用。在線學習的思想在漂移檢測中也經常用到，如文獻［21］提出的基于在線性能測試的漂移檢測方法，該方法在每個子訓練集上進行在線學習，檢測出真實漂移位點，可以區分真實漂移和由噪聲導致的偽概念漂移。

文獻［22］中提出了在線主動學習集成模型（Online Active Learning Ensemble model，OALEnsemble），是近兩年解決概念漂移最具代表性的模型，該集成分類模型由一個穩定分類器和一定數目的動態分類器組成，采用多層阻尼滑動窗口存放數據來構建分類器，通過權重的動態變化來適應概念漂移。穩定分類器的作用是跟蹤數據流分布的長期趨勢，以適應概念漸變漂移；動態分類器可以迅速捕捉突變漂移，及時更新集成分類器。由于該模型采用多層窗口技術，因此，每個分類器從創建時刻起，需要學習后面到來的所有實例，因此需要一定的空間來存儲數據塊，而且重復的計算會使得處理數據流時間復雜度較高，不適用于分布式挖掘環境中。本文在OALEnsemble 基礎上改進，同樣構建兩種分類器：動態分類器和穩定分類器，動態分類器通過基于塊的方法創建，穩定分類器通過在線學習的方法更新。穩定分類器在部署到數據流環境之前已經創建完畢，在分類過程中選擇最具價值的實例來更新或淘汰穩定分類器；動態分類器通過固定大小的數據塊創建，減少不必要的空間開銷，因此不管從時間還是空間復雜度上都是優于OALEnsemble，更適用于分布式挖掘框架中。

本文針對現階段對于大數據的挖掘技術需求，聚焦大數據中分布式和流動性這兩個技術特征，提出一個系統的分布式數據流挖掘模型，并在模型的關鍵挖掘步驟設計相應的算法，最后通過實驗證明本文算法的有效性。本文工作主要有兩點：

1）BDS-ensemble［13］在局部節點收集數據，并將它們的統計信息發送到中心節點，然后由中心節點根據統計信息重構出樣本集來訓練集成分類器。該方法雖然能夠在較小的通信代價下完成分布式數據流挖掘工作，但是，當數據流中發生概念漂移時，整個分類性能會急劇下降，因為中心節點的集成分類算法不具備漂移自適應性。本文在集成算法上進行改進，使其在漂移數據流環境中也能維持很好的分類性能。

2）OALEnsemble 模型能夠很好地處理數據流中的概念漂移，但是該模型的空間復雜度和空間復雜度都較高，本文在不降低分類性能的前提下簡化了該模型，使其能運用到分布式數據流挖掘環境中。

1 相關工作

1.1 分布式數據流

假設有n個節點，維度為d，每個節點產生一個單數據流Si（i=1，2，…，n），中心節點接收的數據流S=，每個Si是d維數據元組序列，該定義的數據形態可以在網絡流量監控、交易系統等場景下作為收集模型使用，在現實生活中，數據不是一成不變的，數據中隱藏的知識會隨著時間變化，因此需要實時更新分類器，以確保分類器的準確預測。

1.2 微簇

當局部節點收集到數據后，需要進行局部模式的挖掘，挖掘的目的是找到一個合適的表達數據塊的方式，因為在現實生活中，可能受到帶寬的限制，局部節點向中心節點傳輸的信息不能太多，否則延遲太高，影響分類的效率，然而，如果傳遞的信息不夠全面，就會影響全局分類器的精度。因此，局部模式的挖掘實際上就是一個傳輸代價和分類精度的平衡優化問題，需要找到一個“緊湊”的表達方式。“緊湊”是指信息容量小，但是具有代表性，并且到達節點后可以恢復，因為全局分類器需要學習恢復的數據集。本文借鑒了微簇模式，先將數據塊中的樣本通過K-means方法聚類成k個簇，然后將每個簇的簇內樣本數、樣本均值、平方和、方差和簇的類標識組成一個五元組來代表這個簇。

假設X={x1，x2，…，xm}是一個含有m個樣本的簇，其中每個樣本都是一個d維的向量xi=，則這個簇可以簡化成一個五元組的微簇模式MC=(m，ave，s，var，y)，分別代表簇內樣本數、樣本均值、平方和、方差和類標識，其中類標識是指每個簇樣本標簽的眾數，樣本均值、平方和及方差的計算方式如式（1）～（3）所示：

上面定義的微簇模式滿足局部模式對于數據集表達方式“緊湊”性的需求，能夠使用最小的通信代價傳輸局部節點收集的數據，當數據到達中心節點時，全局模式需要對各個數據流的潛在的知識模式進行共性歸納，集成學習能夠構造一個預測能力較強、概念漂移自適應的分類器，因此，本文將改進現有的集成學習技術，在中心節點創建一個全局共享的分類器。

1.3 概念漂移

數據流中的“概念”，最早將其定義為一組對象的集合，顯然這個定義不適用于動態變化的數據流環境，文獻［23］中將“概念”定義為底層的數據分布，將“目標概念”定義為待學習的概念或者函數，具體用聯合概率分布P(x，y)來表示［24］，其中x是d維的特征向量，y是標簽。用Pt(x，y)表示t時刻輸入特征和目標變量y之間的聯合概率分布，在t時刻，每個實例都是由聯合概率分布為Pt(x，y)的數據流源生成，當且僅當數據流中的實例都是由同一聯合概率分布的數據源生成時，數據流中的“概念”才是穩定的，如果存在x，使得Pt(x，y) ≠Pt+1(x，y)，則說明在t時刻發生概念漂移。根據貝葉斯理論，可以將聯合概率分布表示為P(x，y)=P(x)P(y|x)，因此可以從概率論的角度將概念漂移分為兩類：真實漂移和虛擬漂移。先驗概率P(x)發生變化，而條件概率P(y|x)不變，因此不會影響決策邊界，這種漂移被稱為“虛擬漂移”；條件概率分布發生變化，不管先驗概率有沒有變化，都會影響決策邊界，進而影響分類器的學習準確率，這種漂移稱為“真實漂移”。文獻［25］中根據變化形式，將概念漂移分為四種類型。

突變漂移 突變漂移的表現形式是數據流中的數據分布在很短時間內被另一種分布所取代，這種變化可能會導致分類模型失效。因此，在處理時，要求分類模型有較高的靈敏度，能夠及時捕捉數據分布的變化并更新模型以適應后來的數據流實例。

漸變漂移 漸變漂移是一種變化幅度較小的漂移，需要很長時間才能發現，這種漂移對分類模型準確率的影響較小，因為即使發生了，變化前后的概念也是極其相似的。

增量漂移 增量漂移與漸變漂移相似，概念的變化幅度都較小，表現為概念增量式變化，由多個數據分布產生數據，但是數據分布之間相差不大，因此，概念變化也不大。

重現式漂移 重現式概念漂移表現為之前學習的概念經過一段時間后再次出現，在現實生活中很常見，比如，人們關注的主題，如“春運”會在每個年關周期出現。在處理這種類型的概念漂移時，需要把之前學習的知識重復利用，不僅能提高模型的學習準確率，還能避免歷史學習資源的浪費。

2 分布式數據流分類框架

分布式數據流的分類模型可以定義為Model=(T，D，O，P)，其中：T={t1，t2，…}是局部節點收集收據的時刻序列；D是來自n個局部節點的數據流，為全局分類器提供樣本來源；O是對數據流實例的操作算子；P是最終訓練完成的全局分類器。

整個挖掘模式如圖2 所示，假設網絡中有三個局部節點，則整個挖掘框架由三個部分組成：

圖2 分布式數據流挖掘框架Fig.2 Distributed data stream mining framework

1）局部模式。按照之前設定的時間點序列收集局部節點窗口數據，形成數據塊{D1，D2，…}，挖掘每個數據塊的微簇集{c1，c2，…，ck}，ci是指第i個簇的微簇形式，微簇模式是用第一個數據塊的微簇集初始化的。假設Dt是當前時刻窗口中的數據，則可以用Dt中的數據對上一個挖掘點所維護的微簇模式MCt-1進行更新，即MCt={MCt-1；Dt}。大數據背景下，更新操作后會增加局部節點維護的微簇的數目，為了防止微簇數目的無限膨脹導致后面中心節點計算量大、學習效率低等問題，局部節點采用幾何輪廓相似度函數［26］計算簇之間的相似度，將相似度較高的兩個簇合并。

2）模式傳輸。當微簇模式更新完成后，將其傳輸到中心節點。

3）全局模式。中心節點設置了緩沖池，等待所有局部節點的微簇模式傳輸完成后將其發送到中心節點；然后，中心節點采用樣本重構算法，將微簇轉化成和原始樣本具有相同分布特征的合成樣本，使用合成樣本學習分類器。基于集成學習技術創建的分類器，當一個歷史窗口的所有節點的微簇模式都發送到緩沖池后，可以觸發全局分類器更新機制，即使用新的實例對全局分類器進行增量式更新。

3 各步驟挖掘算子

根據上面提到的分布式數據流分類框架，本文主要用到的算法有微簇提取、微簇合并、訓練樣本恢復和全局集成分類算法。其中，微簇提取算法比較簡單，主要公式在相關工作中已經介紹，這里不再贅述。

3.1 微簇合并

一個局部節點維護的微簇模式需要不斷更新來適應數據的變化，具體方法是挖掘新到來的數據塊的微簇集合來增量式更新上一個挖掘時刻維護的微簇模式。這種更新方式會導致微簇的數量無限增加，增加后面樣本重構和分類器學習的時間，因此，必須要對微簇的數目加以控制，比如設置閾值，當更新操作中微簇的數目超過給定的閾值，就需要進行微簇合并操作，找到當前維護的微簇模式中相似度最高的兩個簇，并將它們合并成一個簇。考慮到微簇模式只是保存的原來簇的統計值，而非數據點，本文用微簇中的均值代表這個簇，因此簇與簇之間的相似度計算可以轉化為均值樣本的相似度計算。本文根據幾何輪廓相似度函數計算兩個簇的相似度，然后設定閾值ξ，大于閾值ξ的兩個簇進行合并操作。

幾何輪廓相似度函數是建立在伽羅華群-單純型理論［27］上的多維對象親疏性度量方法，假設當前數據流是S，S是d維數據元組序列，S={x1，x2，…，xn}，xi是數據流S的第i個樣本，xi=是xi的第j個特征變量，則點集Qi=是樣本xi的幾何輪廓。樣本xs和樣本xt的幾何輪廓相似度函數為：

當局部節點維護的微簇數目超過閾值L時，隨機選取兩個微簇，計算它們微簇均值的相似度λ，然后將λ與設定的閾值ξ比較，如果λ＞ξ，說明比較的兩個微簇比較相似，需要進行微簇合并操作。用c1和c2表示合并之前的兩個簇，用c3表示合并后的簇，因為微簇模式不是直接存放原始數據點，所以，c3的微簇模式不能用之前的方法提取，只能由c1和c2的統計值推導出，如下所示，給出了c3統計值推導過程，其中c1和c2的原始簇的樣本集分別為｛x1，x2，…xp｝和｛y1，y2，…，yq｝：

通過式（8）～（11），可以由c1和c2的統計值推導出c3的統計值，這樣就能將兩個相似的簇合并成一個簇。當增量式更新局部模式時，如果局部模式中的微簇數量超過給定閾值L，就需要選擇最相似的簇合并，整個的增量式更新過程如算法1所示。

算法1 Microcluster-merging。

輸入 當前數據塊挖掘出的微簇集MC*，上一挖掘點維護的微簇模式MCt-1，微簇數量最大值L，簇相似度閾值ξ；

輸出 更新后的微簇模式MCt。

算法1 中第2）行用N表示MCt中的微簇數目，從第3）～13）行，如果當前微簇數目一直超過閾值L，就會執行合并操作，即在當前微簇集中隨機選取兩個微簇c1和c2，用x1和x2分別表示它們的均值向量，如果x1和x2的相似度大于閾值ξ，就會根據式（8）～（11）合并c1和c2，形成一個新的微簇c3，然后在當前微簇集中加入c3，去除原來的相似簇c1和c2，以此方式循環，直到MCt中的微簇數目小于閾值L。

3.2 微簇重構

當所有的局部節點將更新完成后的微簇模式傳入到中心節點后，中心節點就會學習一個全局集成分類器，但是微簇集并不是原始的樣本，不能作為分類器的訓練樣本。因此，需要根據微簇的統計信息，重新構造樣本集來訓練分類器。本文借鑒了文獻［13］中提出的樣本重構算法，假設原始樣本是正態分布的，那么由微簇重新構成訓練樣本集的過程如算法2所示。

算法2 Samples-remaking。

輸入 微簇c，樣本數據維度d；

輸出 重構訓練集X。

在算法2 中，l是重新構成的簇的半徑，l的證明過程可以參考文獻［13］，用簇半徑l乘以在-1～1 的隨機變量r，可以在簇的均值向量周圍生成訓練樣本集，且生成的樣本集和原始樣本具有同樣的分布。

3.3 全局分類算法

本文改進現有的集成方法，利用重新構成的訓練樣本集，學習一個高歸納性、抗干擾性強并且可以適應概念漂移的集成分類器，該集成分類器用到了主動學習。主動學習就是從一堆不帶標簽的樣本中按照一定的準則選擇一部分來標記，這種學習方式可以在保證分類器性能的同時控制標記成本。

從圖3 中可以清楚地看到在線集成學習的框架。三角形和正方形分別表示穩定分類器和動態分類器，具體表示為Cs1，Cs2，…，Csn和Cd1，Cd2，…，Cdn。對于數據流S，將用于動態基分類器的實例I視為每個等大小的數據塊M1，M2，…，Mn，而穩定基分類器只需使用實例I進行自我更新。由于標記成本較高，每個數據塊只選取最不確定的實例進行標記，并利用標記實例生成新的動態分類器和更新穩定分類器。本文采用混合標記策略［20］來選擇每個塊中的實例，該策略由不確定性策略和隨機策略組成。在不確定性策略中，一個測試實例的裕度值由公式確定：P(yc1|x)-P(yc2|x)，其中yc1和yc2分別表示具有最大后驗概率和第二大后驗概率的類別，預測裕度可以識別出每個塊中預測結果最不確定的實例，并以此作為判斷實例是否需要標記的依據。具體來說，如果實例的裕度值小于閾值θm，則該實例將被標記。當數據流中出現概念漂移時，裕度值小于閾值的實例數量將顯著增加，從而導致標記開銷過大。因此，在該策略中，動態地降低閾值θm，以確保對最不確定的實例進行標記，同時最小化標記成本。隨機策略可以發現數據塊中潛在的概念漂移。它首先生成0 到1 范圍內的隨機變量φ，然后將φ與閾值σ進行比較。如果φ不大于閾值σ，則實例將被標記。這樣，可以對沒有被不確定策略標記的實例進行隨機標注，捕捉到潛在的概念漂移實例，從而生成更好的動態分類器，有效地更新穩定分類器。

圖3 集成模型框架Fig.3 Ensemble model framework

在真實環境的數據流中部署穩定分類器之前，需要對其進行訓練。本文使用AdaBoost算法來建立一個穩定的集成分類器。然后，將這個集成分類器部署在數據流中，穩定基分類器在數據流分類過程中進行在線學習。動態基分類器的數目和穩定基分類器一樣，都是n，但與穩定基分類器不同，動態基分類器不需要預先訓練，而是通過逐漸到達的數據流實例來創建。當方法被部署到數據流中時，數據流被視為等大小的塊M1，M2，…，Mn，每個塊有m個數據流實例。第一個動態基分類器由塊M1創建，表示為Cd1，Cd2由M2創建，其余n-2動態基分類器用相同的方法創建。在數據塊中，實例選擇標記方法基于上述混合標記策略，具體過程如圖4 和算法3所示。

圖4 混合標記策略Fig.4 Mixed labeling strategy

算法3 混合標記策略。

輸入 測試實例x；裕度閾值θm；隨機策略閾值σ；

輸出 true 或者false。

當動態分類器的數目達到n個時，新的分類器將取代舊的分類器，具體地說，一旦數據流實例填滿數據塊Mn+1，新的動態基分類器Cdn+1將由Mn+1構造出來，并加入到集成模型中，此時Cd1將從集成分類器中移除，Cd2取代Cd1的位置，以此類推來響應突發的概念漂移。

集成模型是穩定基分類器和動態基分類器的加權組合，在該集成模型中，穩定的基分類器將始終存在，且權重保持不變。但是動態基分類器會在一段時間內產生并消失，因此動態基分類器的權重會隨著時間的推移而衰減。下面的公式顯示了每個基本分類器的權重，其中ws和wd分別表示穩定基分類器和動態基分類器的權重。

從式（12）和（13）可以看出，ws始終保持不變。動態基分類器越新，其權重值越大，在線集成學習方法如算法4所示。

算法4 在線集成學習。

輸入 動態基分類器Cd，穩定基分類器Cs，數據流實例xi，當前數據塊M，訓練數據集D，數據流S，動態分類器數量n；

輸出 集成模型E。

算法4 中設置了一個緩沖區A用來存放被選中標記的實例，對于數據塊中的每一個實例，使用混合標記策略確定其是否需要人工標記（第6）行），標記后的實例可以對穩定分類器進行更新（第9）行），然后加入緩沖區A中，最后使用A中的有標簽實例創建一個動態分類器（第13）行）。

該集成模型可以有效地緩解數據流分類不準確的問題，但當概念突然漂移時，穩定的基分類器可能無法適應環境，從而影響分類結果。因此，本文將在穩定基分類器中引入abandonment方法［28］。

abandonment 方法的作用是刪除集成模型中過時的穩定基分類器，本文給出了分類器中的誤差閾值θ，它代表了整個集成分類器所能容忍的單個分類器的最大錯誤數。也就是說，如果一個穩定分類器的錯誤預測數達到θ，它將放棄參與投票。因此，對于每個實例I，集成模型將選擇滿足閾值限制的分類器進行決策，以減少過時概念對分類結果的影響，具體見算法5。

算法5 穩定基分類器的abandonment方法。

輸入 數據流實例I，穩定基分類器Cs，最大錯誤次數θ；

輸出 集成模型E。

上面算法中，第2）行初始化所有穩定分類器的錯誤次數為0，第7）～11）行，如果單個穩定分類器的預測結果和集成分類器不一致，就會被判定會預測錯誤，增加一次錯誤次數，當錯誤次數達到上限θ，集成分類器就會拋棄這個弱分類器。

3.4 算法復雜度分析

1）時間復雜度：假設訓練一個實例的時間是Ti，訓練穩定分類器的實例數目是Ns，標記一個實例的時間是TL，每用一個實例更新一個穩定分類器的時間是TU，一個數據塊中被標記的實例比率是α，數據塊的大小是Nd，那么處理一個數據塊的時間是Ns*Ti+Nd*α*TL*Ti+Nd*α*TL*n*TU。如果數據流中的實例總數目是N，那么本文提出全局集成分類算法的時間復雜度是O[N/Nd*(Ns*Ti+Nd*α*TL*Ti+Nd*α*TL*n*TU)]，約等于O(N)。

2）空間復雜度：假設每個數據塊的大小是Nd，窗口中的數據塊數量是n，存儲每個實例所需空間是Si，那么集成算法所需的空間是O(n*Nd*Si)。

4 實驗結果和分析

本文在真實數據集和虛擬數據集上驗證本文提出的EDD模型（Ensemble model for Distributed Drift data streams）的有效性，硬件平臺為一臺酷睿i7，內存16 GB 的PC，使用VM Workstation 在一臺主機上構建4 臺虛擬機，其中三個虛擬機作為局部節點，一個作為中心節點，以此來模擬分布式環境，在每個局部節點使用大規模在線分析平臺（Massive Online Analysis，MOA）［29］來模擬數據流的產生并實施算法。

4.1 數據集與評價指標

本實驗主要在4 個數據集上進行：SEA、Radial Basis Function（RBF）、NSL-KDD 和MNIST。其中SEA 和RBF 都是由MOA 數據流產生器生成的，NSL-KDD 和MNIST 是真實數據集。

SEA 數據集一種突變型概念漂移數據流集，有三個屬性兩個類別，但是決定分類結果的只有兩個屬性。該數據集會有兩次突變漂移，在第3×105和第7×105個實例處。

RBF 數據集是一種漸變式概念漂移數據流集，該數據集生成器預先生成一定數量的中心點，每個中心點由位置、標簽和權值確定。然后隨機選取一個中心生成樣本，權值越高的中心點被選中的概率越高，通過對中心位置的改變來產生概念漂移，本實驗使用RBF 生成器生成的數據集有20 個類，在第1.5×105、5×105和7.5×105個實例處發生漸變式漂移。

NSL-KDD 是對KDDCup99 數據集的改進，KDDCup99 是美國空軍模擬網的流量監控數據，由MIT林肯實驗室收集，被哥倫比亞大學等整理的公共數據集。該數據集是網絡連接記錄的時間序列，被當成數據流挖掘和入侵檢測的標尺數據集，有5×106個以上的訓練實例、41 個屬性和2 個類別：正常和攻擊。NSL-KDD 是KDDCup99 數據集的重采樣版本，解決了訓練集中類別不均衡問題，同時NSL-KDD 去除了訓練集和測試集中的冗余記錄，控制訓練集和測試集的實例數量，實施實驗時不需要隨機選取一部分，降低了實驗成本，訓練集和測試集的數量分別是125 973和22 544，屬性數量不變。

MNIST 是一個手寫數據集，有6×104個訓練樣本和1×104個測試樣本，每個樣本是一個28*28 像素的手寫數字0～9 的圖像。

本文提出的分布式數據流分類模型需要在多個節點上經過多步驟完成，挖掘的最終目標是要學習一個全局共享的分類器，因此，全局分類器的精度是評價該模型的最重要的指標；除此之外，整個模型挖掘過程中的內存消耗也將作為輔助評價指標。本文的對比模型是DS-means［9］、BDS-ensemble［13］和OALEnsemble［22］：DS-means 和BDS-ensemble 和本文模型一樣，都是由局部節點和中心節點組成的層次式挖掘框架；OALEnsemble 是目前性能較好的概念漂移數據流集成分類模型，可以與本文的集成分類模型比較。

4.2 參數選擇

本文提出的EDD 模型有三個重要的參數：局部模式中的微簇數量閾值L、基分類器的數量n以及每個數據塊M的樣本數m。為了確定每個參數的最佳選值，本文在四個數據集上分別實驗，對比不同參數下的分類準確率，找到每個數據集的最佳參數，每次實驗的準確率都是10 次運算結果的平均值，不同參數下的準確率如表1～3所示。

表1 不同參數L下的準確率比 單位：%Tab.1 Comparison of accuracy under different L unit：%

由表1 可知，四個數據集的最佳L參數設定應是10、20、10 和10，當L超過最佳值時，準確率變化不明顯，為了減少全局分類器的學習時間，L的參數不能設置過大。在數據集RBF 的實驗中，當L=10 時，分類準確率較低，主要原因是RBF中有20 個類別，將微簇最大數目設置為10 時，會導致算法將不屬于同個類別的微簇合并，從而導致分類錯誤。由表2 和表3 得到參數n和m的最佳值分別是20 和35，本文按照參數的最佳選值來設置。

表2 不同參數n下的準確率比 單位：%Tab.2 Comparison of accuracy under different n unit：%

表3 不同參數m下的準確率比 單位：%Tab.3 Comparison of accuracy under different m unit：%

4.3 對比實驗

本文從實時準確率、整個過程平均準確率和內存消耗角度分別比較EDD、DS-means、BDS-ensemble 和OALEnsemble，其中，對于SEA 和RBF 數據集而言，實時準確率是指測試點前后10 000 個實例的平均準確率，NSL-KDD 和MNIST 是前后1 000 個實例的平均準確率（因為這兩個數據集測試實例較少）。例如，在SEA 數據集上，第2×105個實例的實時準確率是第1.9×105個實例到第2.1× 105個實例的平均預測準確率。圖5 給出了各種模型隨著數據流實例增多時實時準確率的變化情況。

如圖5（a）所示，EDD 模型與其他三種模型相比，準確率一直占優勢，剛開始時，各類模型的準確率相差不大，但是由于DS-means 和BDS-ensemble 不能處理概念漂移數據流，因此，在3× 105和8× 105個實例處，這兩個模型都受到突變漂移影響較大，并且準確率不可恢復，而EDD 和OALEnsemble則能夠響應突變漂移并及時恢復原來的準確率，且EDD 在整體準確率上略高于OALEnsemble。

如圖5（b）所示，在RBF 數據集上，各個模型的分類性能相對穩定，特別是EDD 和OALEnsemble，漸變漂移對這兩個模型的影響不大，但是對于無法適應漂移數據流的其他兩種模型來說，準確率就會緩慢下降。總體上，EDD 模型性能最好，DS-means 模型的性能最差，主要原因是這個模型主要挖掘算法是無監督K-means 聚類算法，因此在整體分類效果上肯定比較差。

如圖5（c）所示，由NSL-KDD 模擬出的數據流中沒有漂移現象，所以分類算法的精度不會受到影響，各個模型的預測準確率都是在一個很小的區間波動，其中本文提出的EDD 模型整體的分類性能都維持在一個很高的水平。

如圖5（d）所示，在手寫數字集MNIST 上實驗可以看出，DS-means 和BDSEnsemble 的準確率較低并且波動幅度較大，而EDD 和OALEnsemble 的波動幅度較小，并且本文提出的EDD分類準確率略高于OALEnsemble。

圖5 在不同數據集上的實時準確率比較Fig.5 Comparison of real-time accuracy on different datasets

前面幾個實驗展示了4 個模型在4 個數據集上實時準確率變化情況，每個實驗中設置了10 個檢測點，考慮到檢測點設置可能具有偶然性，下面實驗比較了各個模型整個過程中的平均準確率，結果如表4 所示。由表4 可以看出，本文提出的EDD 模型具有較高的整體分類準確率，綜上，不管從實時分類性能還是整體準確率，EDD 模型相較于其他三個對比模型，都有顯著的提升。除此之外，分布式數據流分類算法還需要考慮代價和精度的平衡問題，前面的實驗中已經證明本文模型在精度上的優勢，下面實驗主要描述了各個模型中心節點的內存消耗隨著時間增長的變化情況。

表4 在不同數據集上的平均準確率比 單位：%Tab.4 Comparison of average accuracy on different datasets uint：%

如圖6 所示，隨著處理實例時間的增長，內存消耗都逐漸增加，DS-means內存消耗較少，主要原因是K-means聚類較為簡單，空間復雜度較低，但是在面對概念漂移數據流時，DSmeans 和BDS-ensemble 模型準確率會急劇下降并且無法恢復，而EDD 模型受漂移影響較小，并且從實時準確率角度來看，本文模型明顯高于這兩個模型。與OALEnsemble 相比，EDD 內存消耗略低，并且在各個數據集上分類性能都優于OALEnsemble。在大數據環境下，面向分布式漂移數據流，本文提出的EDD 模型可以在較小的內存代價下獲得較大的分類準確性的提升，并且能夠適應數據流中的概念漂移，是平衡代價和精度的較優化的解決方法。

圖6 內存消耗隨時間變化情況Fig.6 Memory consumption varying with time

5 結語

隨著互聯網、傳感設備的發展，數據量急劇增長，在大數據挖掘理論和方法上的需求越來越迫切，本文從大數據的分布式和流動性特點出發，系統化地設計了大數據的挖掘模型和對應的算法，同時，考慮到數據流中可能存在的概念漂移現象，在挖掘模型的中心節點處，改進現有的集成分類算法，提高模型對漂移的適應能力。本文提出了分布式數據流的挖掘框架，能夠平衡分類精度和通信代價。最后，將本文提出的模型與其他分布式數據流挖掘模型和概念漂移分類模型進行對比，結果表明本文的模型具有更好的分類精度和穩定性。

本文提出的模型還有以下缺陷：1）本文借鑒的樣本重構算法是假設數據集中樣本是正態分布的，如果數據分布不規范，可能會導致集成分類器分類精度的下降；2）本文提出的集成分類模型是基于塊的方法來學習弱分類器的，因此在大數據背景下會導致內存消耗過大的問題。