基于概念漂移檢測算法的數據流分類模型

孫 娜

（遼寧工業大學 電子與信息工程學院，遼寧 錦州121001）

0 引 言

傳統數據分類方法，例如決策樹和KNN等，由于設計主要面向靜態數據進行數據挖掘，因此當應用于數據流時往往顯得力不從心，甚至分類模型會完全失效。此外，隨著大數據時代的到來，以及物聯網發展深入，傳統數據挖掘技術正面臨著新的挑戰，首當其沖的就是數據的形式的轉變，由傳統的靜態數據類型全面轉變為動態的數據流數據，這也要求傳統數據挖掘模型必須進行調整，以適應數據流環境的新特點［1］。

對于數據流本身來說，其具有3個特點［2］，即實時性、海量性和隨著時間動態變化性。而實時性和海量性目前已經有比較成熟的算法進行解決，分別通過提高分類模型的分類速度可以消化掉海量實時數據，對分類模型所帶來的影響。但是對于數據流動態性，即概念漂移問題，目前學術界仍然處于探索階段。

對于概念漂移問題來說，由于數據的分布隨著時間而發生變化，這就會造成已經構建好的分類模型，會逐漸不適應新數據環境，其分類準確率和性能會隨著時間而逐漸降低，甚至完全失效［3］。針對這個問題，目前比較流行的抗概念漂移的數據流分類方法主要有兩種：基于集成學習的數據流分類模型和基于增量式學習的數據流模型［4－6］。對于基于集成學習的數據流分類模型，其核心思想是通過使用多個個體分類模型同時進行分類，然后通過將不同分類器得到的分類結果進行匯總，得到最終的分類結果。此方法通過使用多的個體分類器，降低了數據流概念漂移對于分類模型整體的影響，并通過匯總保證分類的準確率。其優點是模型構建比較簡單，效果較好，但是由于需要多個分類器同時分類，以及模型包含多個分類器，因此分類模型需要較多系統資源支持［7］。

基于增量式學習的數據流模型，其核心思想是通過調整模型內部學習策略，加快分類模型的更新速度，以達到實時更新分類模型，適應數據流環境變化的目的。其優點是通過加快模型更新速度，提高模型更新頻率，減少因概念漂移對模型分類準確率造成的影響。但缺點是由于模型需要不斷更新，并且更新過程中有些時候是盲目的，因此無謂消耗大量系統資源［8］。

為保證數據流分類模型能夠既保證分類準確率，又能降低模型對系統資源的消耗，減少概念漂移對分類模型的影響，本文提出一種基于概念漂移檢測方法的數據流分類模型，通過將概念漂移檢測機制與分類模型相結合，通過概念漂移檢測做到分類模型有的放矢的更新，使得分類模型更加高效，并且實驗中分別使用兩種數據進行驗證，即人造概念漂移數據和真實數據，并使用多種經典分類模型與所提出模型進行比較實驗，對所提出模型進行驗證。所提出模型的整理流程如圖1所示。

圖1 模型整體框架

1 支持向量機模型

作為十大數據挖掘算法之一的支持向量機模型，一直是數據分類問題較好的解決方法。它最早由美國計算機學家Vapnic在1995年提出，由于其經典是解決了數據維度對分類模型的影響，而廣受好評［9］。

支持向量機模型的基本思想是，首先將數據映射到樣本空間中，然后將分類問題轉化為尋找超平面函數問題，并且所找到的超平面必須滿足距離分開數據的距離最遠這一必要條件，也正因為如此，在分類過程中，不需要考慮數據的維度，只需要尋找分類超平面即可，克服了高維數據難以分類的弊端，基本過程如圖2所示，其中實線為最優超平面，兩條虛線上的點是支持向量。

支持向量機原理可表述為，假設支持向量模型的訓練集 ｛xi，yi｝包含l個樣本，其中xi表示n維數據向量，yi表示向量對應的類別 （一般為1或－1）。那么對于超平面，可以利用空間幾何知識表示為w＊x＋b＝0，并且該超平面必須是距離數據點最遠的，即最大分類間隔。因此，可以將數據分類問題，最終轉化為最優超平面尋找問題。

對于超平面的尋找，往往會遇到兩種情況：

“蓄”，就是加快實施蓄水工程。建設河湖庫渠蓄水工程，存蓄雨洪資源和外調水，能夠有效減少地下水開采量。當前試點區現有河渠坑塘年久失修，引水、蓄水功能基本喪失。滄州東光2009年開始推行“一村一坑塘”工程，幾年下來建設坑塘400多座，形成了一張較為系統的“農田水網”，每年可蓄水3 000多萬m3，灌溉農田61萬畝，占全縣耕地面積的80%。各地結合引調水工程，科學編制規劃，對現有河湖庫渠進行清淤疏浚、擴容整治，重新恢復調蓄水功能，構建布局合理、蓄泄兼備、引排得當、豐枯調劑、循環通暢的水網體系，確保外調水、過境水和雨洪水蓄得住、用得好。

若數據線性可分，則分類問題轉化為

圖2 支持向量機分類過程

那么決策函數可以表示為

若數據無法線性可分，則此時需要將數據進行高維映射，這里所需映射函數稱為核函數，表示為K（xi，xj）＝（xi）（xj）。通過核函數映射后，將輸入空間中的非線性可分問題轉化為在高維空間中線性可分問題，進而使用線性可分計算過程尋找最優分類超平面，進而完成數據分類過程。這樣做的好處是通過映射弱化了數據維度對分類模型的影響，提高分類效果。

若數據存在噪聲，盡管通過核函數進行映射，但仍然找不到最優超平面，那么使用松弛變量ξi≥0，i＝1，2，...，l，其目的是將分類模型的錯誤忍受程度進行調整，容許有少量數據分錯的情況發生，從而保證大部分數據是分類準確的，這也是一種折中的方法。此時，支持向量機模型可以表示為

其中變量C表示懲罰系數，其控制分割最大化與誤分最小化的平衡。w是權重向量，b是偏離變量。

對于式 （3）的求解等同于二次問題，這里使用拉格朗日多項式方法進行計算，因此式 （3）轉變為

其中Q （i，j）＝yiyjK （xi，xj），C is懲罰參數，αi是拉格朗日多項式變量，進而得到

2 基于信息熵的概念漂移檢測方法

KDQ樹：在介紹概念漂移檢測算法之前，由于數據流無法使用信息熵進行計算，因此需要先對數據初始化，這里使用的方法是KDQ樹［10］，將原始數據塊轉變為能夠參與信息熵計算的形式，其示例如圖3所示。

圖3 數據塊轉變過程舉例

通過圖3可以看到，首先使用滑動窗口的方法將動態數據流轉化為靜態數據塊形式。然后，將數據塊按照所構建KDQ樹進行劃分，成為圖3中虛線框出數據集形式，參與到概念漂移檢測過程中。

由于概念漂移存在3種類別，即：

（1）屬性值發生變化的概念漂移 （feature change）。這種類型的概念漂移往往是數據各個屬性值的取值區間發生變化，例如原本取值不大的數據值突然激增。此種概念漂移在網絡數據中比較常見，由于發生在屬性值層面，因此可以通過模型調整，適應數據的變化。

（2）類 別發生 變化的 概念漂 移 （conditional change）。這種概念漂移主要是數據的類別標簽發生改變，例如原先屬于某一類的數據，在數據值沒有變化的情況下，突然屬于另外一類了。此種概念漂移在金融個人數據中比較常見，自然人的信用在不同時期往往是不同。當發生此類概念漂移時，模型必須通過重新訓練才能夠繼續對數據流進行分類，目前沒有更好的辦法進行解決。

（3）兩種變化同時發生的概念漂移 （dual change）。這種概念漂移是比較少見的情況，一般來說如果發生這種概念漂移，那么說明數據中存在大量噪聲，而完全失效，可以通過重新選擇數據的方式，或者將上述兩種概念漂移檢測方法同時使用，來達到檢測的目的。

因此針對上述3種概念漂移類型，本文設計3種不同的概念漂移檢測方法進行檢測，對于第一種屬性值發生變化，基于信息熵［11］的概念漂移檢測方法計算公式為

式中：ws，j、ws＋1，j——壓縮數據塊Vs、Vs＋1中，樣本在第i個KDQ樹劃分塊中的數量。

對于第二種類型的概念漂移類型，其檢測方法計算公式為

式中：ws，i，j、ws＋1，i，j——壓縮數據塊Vs、Vs＋1中，屬于第i類樣本，在第j個KDQ樹劃分塊中的數量。

除此之外，為了得到概念漂移顯著性參數，即是否發生概念漂移的閾值，本文使用Bootstrap［12］方法，通過對某類概念進行有放回抽取的方法，夠將多個數據集，并且對這些數據集的信息熵進行計算，然后將計算結果按照從大到小進行排序，使用前95%作為置信區間，尋找到概念漂移檢測閾值，為是否發生概念漂移提供標準。

3 實驗結果分析與討論

本實驗中為了驗證所提出模型的有效性，實驗中選取了兩種類別的數據，分別是人造數據和真實數據對所提出模型進行驗證。此外，還選取了兩種數據流分類模型，分別是KNN模型和決策樹模型，進行比較實驗。

3.1 人造數據實驗結果及分析

實驗中所使用兩種數據對所提出分類模型進行驗證，即人造數據和真實數據。之所以使用人造數據，是因為能夠對概念漂移位置、數量、種類等信息進行控制，使得對于所提出模型的驗證更加充分。人造數據通過一種數據生成器進行生成，共生成5種類型數據，每種類型包含160000個樣本，且每4000條樣本漂移一次。生成器相關參數見表1。

此外，為了驗證數據塊大小對于所提出模型分類的影響，實驗中使用不同的數據塊大小 （100，200，500，1000，2000）以從整體驗證所提出模型的分類準確率，實驗結果見表2至表6。

表2 Circle數據集實驗結果

表3 SineV數據集實驗結果

表4 Sine H數據集實驗結果

表5 Line數據集實驗結果

表6 Plane數據集實驗結果

通過對不同人造數據結果進行比較發現，所提出概念漂移檢測方法能夠有效應對各種不同的概念漂移類型，并且在保證分類準確率穩定的前提下，能夠提升分類模型抗概念漂移影響的能力，并且與其它傳統分類模型進行比較，可以明顯提高分類的準確率，這也證明了增加概念漂移檢測機制后，能夠有效提升分類準確率。此外，對于不同數據塊大小進行比較發現，所提出模型的分類準確率，隨著數據塊容量增大而增加，這說明通過增加數據塊大小，可以在一定程度上降低概念漂移對于分類模型的影響，但是這不能看成解決概念漂移的方法，因為隨著數據塊增加，模型更新所消耗時間勢必增加，從而無法滿足實時分類的要求。

3.2 真實數據實驗結果及分析

除了人造數據外，為了驗證所提出模型對于實際數據的有效性，本實驗中還使用了兩種真實數據，分別是MAGIC數據和Shuttle數據，對所提出模型進行驗證，它們都可以從開放數據庫UCI Machine Learning Repository（UCI）中下載得到，方便實驗的可重復性。所用到真實數據的相關信息見表7。

表7 真實數據相關信息

首先實驗中使用上述兩種真實數據集對所提出模型進行實驗，實驗結果如圖4和圖5所示。

通過分析圖4和圖5，發現所提出模型對于真實數據集的分類效果是比較穩定的，并沒有收到數據中概念漂移的影響。對于圖4來說，由于在數據后部發生了一次較大的概念漂移，因此分類準確率會有瞬時波動，但是準確率會迅速上升，這說明通過概念漂移檢測方法，能夠指導分類模型進行及時更新，適應新數據環境的變化，保持分類的準確性和穩定性。此外，通過比較不同數據塊的大小可以發現，當數據塊比較小時，模型對概念漂移具有很好的敏感度，分類準確率下降較少，可以很好的對其進行分類。

與另外兩種分類模型的比較實驗結果見表8和表9。

表8 MAGIC數據集比較實驗結果

通過對表8和表9進行分析比較發現，所提出模型與其它分類模型比較，可以明顯提高分類的準確率，通過配合數據塊容量的調整，對于具有概念漂移現象的數據流有很好的分類效果。

4 結束語

隨著物聯網的深入發展以及大數據時代的到來，針對數據流進行挖掘日益成為學術界和工商業界研究的熱點問題。由于數據流數據不同于傳統靜態數據，因此直接利用經典數據挖掘算法，往往無法得到滿意的結果。盡管目前所提出方法，能夠一定程度解決數據流分類問題，但是仍然存在很大弊端，例如集成學習的系統消耗問題等。因此，本文提出一種基于信息熵的概念漂移檢測方法，對數據流模型進行改進，通過調整模型更新頻率和次數，降低分類模型對系統資源的消耗，并且能夠做到在保證分類性能的前提下，做到模型更新有的放矢。此外實驗中使用兩種類型的數據和分類模型分別對所提出模型進行驗證，實驗結果表明其有效性和正確性，對未來數據流分類問題，提供新的思路。

［1］Yi Y，Wu J，Xu W.Incremental SVM based on reserved set for network intrusion detection ［J］.Expert Systems with Applications，2011，38 （6）：7698—7707.

［2］Zheng J，Yu H，Shen F.An online incremental learning support vector machine for large—scale data ［C］//Thessaloniki，Greece：20th International Conference on Artificial Neural Networks，2010：76—81.

［3］Tang Y，Zhang Y Q，Chawla N V.SVMs modeling for highly imbalanced classification ［J］.IEEE Transactions on Systems，Man and Cybernetics，Part B：Cybernetics，2009，39 （1）：281—288.

［4］Astudillo C A，Oommen B J.On achieving semi—supervised pattern recognition by utilizing tree—based SOMs ［J］.Pattern Recognition，2013，46 （1）：293—304.

［5］HE Xiaodong，YIN Haibo.Design and implementation of data stream processing framework based on shared buffer ［J］.Computer Engineering and Design，2012，33 （11）：4398—4401 （in Chinese）. ［何小東，尹海波.基于共享緩沖區的數據流處理框架設計與實現［J］.計算機工程與設計，2012，33 （11）：4398—4401.］

［6］SUN Na，GUO Yanfeng.Model on data stream classification with incremental learning ［J］.Computer Engineering and Design，2012，32 （11）：4225—4229 （in Chinese）. ［孫娜，郭延鋒.基于增量式學習的數據流實時分類模型 ［J］.計算機工程與設計，2012，32 （11）：4225—4229.］

［7］Plumpton C O，Kuncheva L I，Oosterhof N N，et al.Naive random subspace ensemble with linear classifiers for real—time classification of f MRI data ［J］.Pattern Recognition，2012，45 （6）：2101—2108.

［8］Okada S，Hasegawa O.On—line learning of sequence data based on self—organizing incremental neural network ［C］//Hong Kong，China：International Joint Conference on Neural Networks，2008：3847—3854.

［9］Yao Y，Feng L，Jin B，et al.An incremental learning approach with support vector machine for network data stream classification problem ［J］.Information Technology Journal，2012，11 （2）：200—208.

［10］Nguyen H M，Cooper E W，Kamei K.Mining imbalanced and concept—drifting data streams using support vector machines ［J］.ICIC Express Letters，2012，6 （2）：455—460.

［11］Wu X，Li P，Hu X.Learning from concept drifting data streams with unlabeled data ［J］.Neurocomputing，2012，92（15）：145—155.

［12］Wang X，Chen B，Chang F.A classification algorithm for noisy data streams with concept—drifting ［J］.Journal of Computational Information Systems， 2011， 7 （12 ）：4392—4399.