孫 娜

（遼寧工業(yè)大學(xué) 電子與信息工程學(xué)院，遼寧 錦州121001）

0 引 言

傳統(tǒng)數(shù)據(jù)分類方法，例如決策樹和KNN等，由于設(shè)計主要面向靜態(tài)數(shù)據(jù)進行數(shù)據(jù)挖掘，因此當應(yīng)用于數(shù)據(jù)流時往往顯得力不從心，甚至分類模型會完全失效。此外，隨著大數(shù)據(jù)時代的到來，以及物聯(lián)網(wǎng)發(fā)展深入，傳統(tǒng)數(shù)據(jù)挖掘技術(shù)正面臨著新的挑戰(zhàn)，首當其沖的就是數(shù)據(jù)的形式的轉(zhuǎn)變，由傳統(tǒng)的靜態(tài)數(shù)據(jù)類型全面轉(zhuǎn)變?yōu)閯討B(tài)的數(shù)據(jù)流數(shù)據(jù)，這也要求傳統(tǒng)數(shù)據(jù)挖掘模型必須進行調(diào)整，以適應(yīng)數(shù)據(jù)流環(huán)境的新特點［1］。

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

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

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

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

圖1 模型整體框架

1 支持向量機模型

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

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

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

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

“蓄”，就是加快實施蓄水工程。建設(shè)河湖庫渠蓄水工程，存蓄雨洪資源和外調(diào)水，能夠有效減少地下水開采量。當前試點區(qū)現(xiàn)有河渠坑塘年久失修，引水、蓄水功能基本喪失。滄州東光2009年開始推行“一村一坑塘”工程，幾年下來建設(shè)坑塘400多座，形成了一張較為系統(tǒng)的“農(nóng)田水網(wǎng)”，每年可蓄水3 000多萬m3，灌溉農(nóng)田61萬畝，占全縣耕地面積的80%。各地結(jié)合引調(diào)水工程，科學(xué)編制規(guī)劃，對現(xiàn)有河湖庫渠進行清淤疏浚、擴容整治，重新恢復(fù)調(diào)蓄水功能，構(gòu)建布局合理、蓄泄兼?zhèn)洹⒁诺卯?、豐枯調(diào)劑、循環(huán)通暢的水網(wǎng)體系，確保外調(diào)水、過境水和雨洪水蓄得住、用得好。

若數(shù)據(jù)線性可分，則分類問題轉(zhuǎn)化為

圖2 支持向量機分類過程

那么決策函數(shù)可以表示為

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

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

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

對于式 （3）的求解等同于二次問題，這里使用拉格朗日多項式方法進行計算，因此式 （3）轉(zhuǎn)變?yōu)?/p>

其中Q （i，j）＝y(tǒng)iyjK （xi，xj），C is懲罰參數(shù)，αi是拉格朗日多項式變量，進而得到

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

KDQ樹：在介紹概念漂移檢測算法之前，由于數(shù)據(jù)流無法使用信息熵進行計算，因此需要先對數(shù)據(jù)初始化，這里使用的方法是KDQ樹［10］，將原始數(shù)據(jù)塊轉(zhuǎn)變?yōu)槟軌騾⑴c信息熵計算的形式，其示例如圖3所示。

圖3 數(shù)據(jù)塊轉(zhuǎn)變過程舉例

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

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

（1）屬性值發(fā)生變化的概念漂移 （feature change）。這種類型的概念漂移往往是數(shù)據(jù)各個屬性值的取值區(qū)間發(fā)生變化，例如原本取值不大的數(shù)據(jù)值突然激增。此種概念漂移在網(wǎng)絡(luò)數(shù)據(jù)中比較常見，由于發(fā)生在屬性值層面，因此可以通過模型調(diào)整，適應(yīng)數(shù)據(jù)的變化。

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

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

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

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

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

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

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

3 實驗結(jié)果分析與討論

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

3.1 人造數(shù)據(jù)實驗結(jié)果及分析

實驗中所使用兩種數(shù)據(jù)對所提出分類模型進行驗證，即人造數(shù)據(jù)和真實數(shù)據(jù)。之所以使用人造數(shù)據(jù)，是因為能夠?qū)Ω拍钇莆恢谩?shù)量、種類等信息進行控制，使得對于所提出模型的驗證更加充分。人造數(shù)據(jù)通過一種數(shù)據(jù)生成器進行生成，共生成5種類型數(shù)據(jù)，每種類型包含160000個樣本，且每4000條樣本漂移一次。生成器相關(guān)參數(shù)見表1。

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

表2 Circle數(shù)據(jù)集實驗結(jié)果

表3 SineV數(shù)據(jù)集實驗結(jié)果

表4 Sine H數(shù)據(jù)集實驗結(jié)果

表5 Line數(shù)據(jù)集實驗結(jié)果

表6 Plane數(shù)據(jù)集實驗結(jié)果

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

3.2 真實數(shù)據(jù)實驗結(jié)果及分析

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

表7 真實數(shù)據(jù)相關(guān)信息

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

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

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

表8 MAGIC數(shù)據(jù)集比較實驗結(jié)果

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

4 結(jié)束語

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

［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）. ［何小東，尹海波.基于共享緩沖區(qū)的數(shù)據(jù)流處理框架設(shè)計與實現(xiàn)［J］.計算機工程與設(shè)計，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）. ［孫娜，郭延鋒.基于增量式學(xué)習(xí)的數(shù)據(jù)流實時分類模型 ［J］.計算機工程與設(shè)計，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，F(xiàn)eng 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.