基于概念漂移檢測算法的數(shù)據(jù)流分類模型

孫 娜

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

0 引 言

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

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

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

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

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

圖1 模型整體框架

1 支持向量機(jī)模型

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

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

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

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

“蓄”，就是加快實(shí)施蓄水工程。建設(shè)河湖庫渠蓄水工程，存蓄雨洪資源和外調(diào)水，能夠有效減少地下水開采量。當(dāng)前試點(diǎn)區(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)有河湖庫渠進(jìn)行清淤疏浚、擴(kuò)容整治，重新恢復(fù)調(diào)蓄水功能，構(gòu)建布局合理、蓄泄兼?zhèn)?、引排得?dāng)、豐枯調(diào)劑、循環(huán)通暢的水網(wǎng)體系，確保外調(diào)水、過境水和雨洪水蓄得住、用得好。

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

圖2 支持向量機(jī)分類過程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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