基于信息熵的動態(tài)數(shù)據(jù)流分類模型

郭延鋒

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

0 引 言

如何對動態(tài)數(shù)據(jù)流進行快速、準確分類，成為近些年學(xué)術(shù)界研究的重點問題之一［1］。由于數(shù)據(jù)流具有動態(tài)變化性特點［2，3］，這就要求數(shù)據(jù)流分類模型和方法必須能夠適應(yīng)數(shù)據(jù)流的特點，才能最終對數(shù)據(jù)分類［4］。相比而言，傳統(tǒng)數(shù)據(jù)分類模型大多基于靜態(tài)數(shù)據(jù)設(shè)計，因此應(yīng)用到數(shù)據(jù)流分類過程中往往無法得到令人滿意的結(jié)果，因此針對數(shù)據(jù)流特點設(shè)計分類模型成為分類問題研究的核心。

近些年，隨著研究的深入，多種數(shù)據(jù)流分類模型被提出。Yi等人［5］提出一種針對網(wǎng)絡(luò)攻擊數(shù)據(jù)的增量式支持向量機模型，通過在數(shù)據(jù)集中尋找潛在的支持向量數(shù)據(jù)，從而將訓(xùn)練集進行壓縮，減少訓(xùn)練集大小，提高分類模型的更新速度。此外，他還使用均值和方差對核函數(shù)進行修改，減少數(shù)據(jù)噪音對分類的影響。Orriols等人［6］從數(shù)據(jù)流中抽取模糊知識，從更高層面對數(shù)據(jù)進行表達，并且對于所抽取知識使用增量式學(xué)習(xí)的方式進行分類，提高模型抗概念漂移能力。盡管基于增量式學(xué)習(xí)的數(shù)據(jù)流分類方法，在一定程度上可以滿足數(shù)據(jù)流分類要求，但是由于分類模型增量式更新是盲目而頻繁的，使得無效更新次數(shù)過多，給分類系統(tǒng)增加額外負擔(dān)。

此外，Li等人［7］使用集成學(xué)習(xí)思想構(gòu)建數(shù)據(jù)流分類模型，通過動態(tài)調(diào)整集成分類模型中個體分類器數(shù)量，在保證數(shù)據(jù)流分類準確率的前提下，降低系統(tǒng)資源消耗，提高分類速度。Dai等人［8］同樣使用集成學(xué)習(xí)模型的思想對數(shù)據(jù)流分類問題進行研究，提出使用分類器競爭機制，對于集成分類模型中的個體分類器進行優(yōu)化，從而提高數(shù)據(jù)流分類效果和準確率?；诩蓪W(xué)習(xí)的數(shù)據(jù)流分類方法，可以對數(shù)據(jù)流進行有效分類，通過使用多個分類模型，克服了單一模型的局限性，對數(shù)據(jù)流動態(tài)環(huán)境更為適應(yīng)。但該方法的缺點是需要保存多個分類模型，且每個分類模型需要定期更新，大大降低模型整體分類速度，不利于數(shù)據(jù)流實時分類。

綜上，盡管當(dāng)前已提出方法可以在一定程度上滿足數(shù)據(jù)流分類的要求，但在實時分類問題中，仍然受到概念漂移的影響而導(dǎo)致分類效果地下甚至完全失效。針對上述問題，本文創(chuàng)新性的提出一種基于信息熵和分類器池的數(shù)據(jù)流分類模型。該分類模型將概念漂移檢測引入數(shù)據(jù)流分類模型中，首先對數(shù)據(jù)流中概念漂移進行檢測，若檢測到概念漂移則及時更新分類模型滿足分類要求；否則分類模型將不會被更新，減少因模型更新所消耗的時間，提高分類速度。這樣既能提高模型抗概念漂移的能力，又減少了分類時間。此外，通過將歷史出現(xiàn)的不同概念及其對應(yīng)的分類器放入分類器池中進行保存，防止重復(fù)概念（recurrence concept drifting）出現(xiàn)導(dǎo)致的模型重復(fù)訓(xùn)練的問題，進一步減少分類模型更新次數(shù)，提高模型實時分類能力和分類效果。所提出動態(tài)數(shù)據(jù)流分類模型的整體流程如圖1所示。

圖1 動態(tài)數(shù)據(jù)流分類模型整體流程

1 支持向量機模型介紹

支持向量機模型最早由Vapnik教授于1995 年首次提出，盡管提出時間較長，但隨著后續(xù)研究的不斷深入和支持向量機模型自身的優(yōu)點，目前已經(jīng)在各種不同領(lǐng)域被廣泛應(yīng)用，例如異常檢測、內(nèi)容過濾等領(lǐng)域［9］。從本質(zhì)上說，支持向量機模型的核心思想是，通過將數(shù)據(jù)映射到高維空間后，尋找實驗性誤差與真實誤差之間的平衡（即VC 維度平衡）。分類過程是，支持向量機通過在高維空間（或數(shù)據(jù)空間）中尋找最大分類超平面（將兩類數(shù)據(jù)最大間隔的分類），對數(shù)據(jù)進行分類。支持向量機基本分類過程如圖2所示。

如圖2所示，假設(shè)訓(xùn)練集表示為｛xi，yi｝，其中i＝1，2，…，l，yi∈｛－1，1｝，xi∈Rn。xi表示n 維輸入數(shù)據(jù)值，yi表示數(shù)據(jù)對應(yīng)的類別標(biāo)簽。通過基本的空間幾何知識可知，空間中的超平面函數(shù)可以表示為w＊x＋b＝0，但空間中存在不止一個超平面，因此將超平面與最近樣本的距離最大的那個，作為最優(yōu)超平面。因此將分類問題轉(zhuǎn)化為尋找最優(yōu)超平面問題，即

圖2 支持向量機模型

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

2 基于信息熵的數(shù)據(jù)流分類模型

2.1 KDQ 樹

KDQ 樹結(jié)構(gòu)類似于二叉樹，它是KD 樹和Q 樹相結(jié)合的產(chǎn)物，對于高維數(shù)據(jù)具有更好的適應(yīng)性［10］。其構(gòu)建方法是假設(shè)數(shù)據(jù)流為X，那么所得到的數(shù)據(jù)塊表示為X＝｛D1，D2，…，Dn｝，且數(shù)據(jù)塊Di容量均為N。然后，對于每一個屬性尋找中間節(jié)點，即能夠?qū)?shù)據(jù)塊進行劃分，使得左右兩部分樣本數(shù)量基本相等，然后在劃分后的子部分中繼續(xù)尋找中間節(jié)點，重復(fù)以上步驟，直至數(shù)據(jù)塊滿足終止條件。通過KDQ 樹劃分后得到的數(shù)據(jù)向量表示為V＝｛v1，v2，…，vn｝。以二維數(shù)據(jù)塊為例，KDQ樹劃分數(shù)據(jù)過程如圖3所示。

圖3 KDQ 樹劃分過程

其中圓圈數(shù)字表示劃分的次數(shù)，例如，①表示第一次劃分，以第一個屬性（橫向）為標(biāo)準，將數(shù)據(jù)塊劃分為兩部分，且左右兩部分中所包含的數(shù)據(jù)量基本相同；②表示第二次劃分，以第二個屬性為標(biāo)準（縱向）從第一次劃分得到的左右兩個部分中，分別進行劃分。其余次數(shù)以此類推，直到滿足終止條件，即達到提前設(shè)定的最小劃分數(shù)據(jù)或者最多劃分次數(shù)。此外，每條劃分線上的數(shù)據(jù)點就是所謂的中間節(jié)點，這些點被保留用來構(gòu)建KDQ樹結(jié)構(gòu)。為了讓KDQ樹劃分過程更為直觀，我們以二維數(shù)據(jù)塊舉例，如圖4所示。

圖4 KDQ 樹舉例說明

其中數(shù)據(jù)塊D 包含兩個屬性，均為數(shù)值型。KDQ 樹構(gòu)建首先從屬性1中尋找中間點，通過將屬性1所有值進行排序后，發(fā)現(xiàn)數(shù)據(jù)（5，7）為中間節(jié)點，它可以把數(shù)據(jù)塊劃分為兩個均等的部分。然后分別在劃分后得到的連個子部分中，以屬性2 為標(biāo)準分別尋找各自的中間點，即（3，3）和（7，6）完成一次劃分，重復(fù)這個過程直到劃分完畢。劃分完畢后可以得到圖4中虛線框出的數(shù)據(jù)向量，其中每一個值表示落入此范圍中的數(shù)據(jù)樣本個數(shù)，使用V＝｛v1，v2，…，vn｝表示。

2.2 概念漂移檢測

信息熵是信息領(lǐng)域經(jīng)典的理論，其核心是使用一種數(shù)學(xué)的方式度量信息中所包含的信息量［11］。本文創(chuàng)新性的使用信息熵作為兩個數(shù)據(jù)塊是否發(fā)生概念漂移的度量，進而達到檢測概念漂移的目的。假設(shè)向量T＝｛d1，…，dn｝包含n維屬性，則其熵值H 可定義為

式中：b——對數(shù)所使用的對數(shù)底，通常等于2。變量p（di）代表X 中第i維屬性出現(xiàn)某種情況的概率值。

正因為受到信息熵的思想的啟發(fā)，本文區(qū)別于傳統(tǒng)概念漂移檢測方法（例如使用準確率等參數(shù)檢測概念漂移［12］），創(chuàng)新性的提出一種基于信息熵的概念漂移檢測方法，其具體步驟如下：

（1）使用滑動窗口方法，將動態(tài)數(shù)據(jù)流劃分為靜態(tài)數(shù)據(jù)塊形式，如圖5所示，其中任意一個數(shù)據(jù)塊Di中保存有N 個數(shù)據(jù)樣本。變量N 為固定常數(shù)且需提前人為設(shè)定，在本實驗中變量N 等于2000。

圖5 數(shù)據(jù)流劃分

（2）建立KDQ 樹對原始數(shù)據(jù)塊進行轉(zhuǎn)化，構(gòu)建過程如2.1節(jié)所述。通過所構(gòu)建的KDQ 樹，將數(shù)據(jù)塊變?yōu)橐环N數(shù)據(jù)向量的形式，在后續(xù)計算中均使用KDQ 樹轉(zhuǎn)化后的數(shù)據(jù)向量V＝｛v1，v2，…，vn｝進行。這里需要注意的是，后續(xù)數(shù)據(jù)塊均按照已經(jīng)建立好的KDQ 樹進行轉(zhuǎn)換，直至發(fā)生概念漂移，此時KDQ 樹已經(jīng)無法滿足新概念的數(shù)據(jù)轉(zhuǎn)化，因此需要依據(jù)新概念重新對KDQ 樹進行構(gòu)建。

（3）利用信息熵思想，對不同數(shù)據(jù)塊之間是否發(fā)生概念漂移進行計算。假設(shè)所要比較的數(shù)據(jù)塊為Ds和Ds＋1，其通過KDQ 樹后得到的向量為Vs和Vs＋1，則基于信息熵的概念漂移檢測（kld）計算過程描述為

式中：N——數(shù)據(jù)塊中樣本數(shù)量，T——向量V 中的塊數(shù)，例如圖4中T 等于4，ws，j和ws＋1，j分別表示向量Vs和Vs＋1中，樣本在第i個KDQ 樹劃分塊中的數(shù)量。通過上述計算，得到不同數(shù)據(jù)塊之間的差異值，并通過比較差異值判斷是否發(fā)生概念漂移。

2.3 分類器池

在概念漂移中，有一種是重復(fù)出現(xiàn)的漂移，例如一年四季，因此為了防止歷史出現(xiàn)過的概念漂移，造成分類模型重復(fù)更新的問題，本文提出一種分類器池結(jié)構(gòu)，用來保存歷史出現(xiàn)過的不同概念。分類器池的基本原理如圖6所示。

圖6 分類器池

其中不同的形狀代表不同的概念，并且對于分類器池中的概念，利用所設(shè)計的遺忘函數(shù)進行精簡，保持分類器池的容量的穩(wěn)定。

根據(jù)圖6描述，分類器池的基本原理如下：

（1）若當(dāng)前數(shù)據(jù)塊檢測出發(fā)生概念漂移，則將當(dāng)前數(shù)據(jù)塊與分類器池中所保存的數(shù)據(jù)塊，利用式（4）計算信息熵。

（2）若計算后發(fā)現(xiàn)，分類器池中有與當(dāng)前數(shù)據(jù)塊信息熵的值小于提前設(shè)置的閾值，則表示存在與當(dāng)前數(shù)據(jù)塊相似的概念，則使用此概念所對應(yīng)的分類器對當(dāng)前數(shù)據(jù)塊進行分類。

（3）若當(dāng)前數(shù)據(jù)塊在分類器池中沒有找到與其類似的概念，則表示該數(shù)據(jù)塊所表示的概念為新的。使用人工方式對當(dāng)前數(shù)據(jù)塊進行標(biāo)注，然后訓(xùn)練對應(yīng)分類器，將其放入分類器池中保存。

此外，為防止在數(shù)據(jù)流分類過程中，因產(chǎn)生概念過多，所帶來的分類器池容量增加，系統(tǒng)負擔(dān)過重的問題，本文設(shè)計了一種遺忘函數(shù)對池中概念進行精簡。假設(shè)每個概念的當(dāng)前權(quán)重為wi，初始權(quán)重為W，那么遺忘函數(shù)如下

式中：ε——權(quán)重遞減速度，i＝2，3，…表示在分類器池中進行尋找相似概念的次數(shù)。若某個概念長期沒有被選中，則表明該概念已經(jīng)過時，因此其權(quán)重會逐漸降低，當(dāng)超過遺忘參數(shù)時，將其從分類器池中刪除。

2.4 算法的基本步驟

基于信息熵的動態(tài)數(shù)據(jù)流分類模型的基本步驟如下：

步驟1 數(shù)據(jù)初始化。使用滑動窗口方法將動態(tài)數(shù)據(jù)流轉(zhuǎn)變?yōu)殪o態(tài)數(shù)據(jù)塊，且每個數(shù)據(jù)塊所包含樣本數(shù)量相同，用N 表示。

步驟2 數(shù)據(jù)轉(zhuǎn)化。使用KDQ 樹對數(shù)據(jù)塊進行轉(zhuǎn)化，獲得數(shù)據(jù)塊所對應(yīng)的向量V＝ ｛v1，v2，…，vn｝。使用建立的KDQ 樹結(jié)構(gòu)對后續(xù)數(shù)據(jù)塊進行轉(zhuǎn)化，直到發(fā)生概念漂移，此時重新建立KDQ 樹。

步驟3 概念漂移檢測。使用KDQ 樹轉(zhuǎn)化后的數(shù)據(jù)向量V＝｛v1，v2，…，vn｝代表實際數(shù)據(jù)塊，計算不同數(shù)據(jù)塊信息熵，計算方法如式（4）所示。

步驟4 如果未發(fā)生概念漂移，則繼續(xù)使用最近的分類模型對的當(dāng)前數(shù)據(jù)塊進行分類。

步驟5 若發(fā)生概念漂移，則將當(dāng)前數(shù)據(jù)塊與分類器池中保存的數(shù)據(jù)塊使用式（4），計算信息熵。若能找到相似的概念，則使用分類器池中此概念所對應(yīng)的分類模型（支持向量機模型）對當(dāng)前數(shù)據(jù)塊進行分類；如果沒有找到合適分類器，則人工對當(dāng)前數(shù)據(jù)塊類別進行標(biāo)注，并使用該數(shù)據(jù)塊重新訓(xùn)練分類模型，最后將數(shù)據(jù)塊及其分類模型加入到分類器池中。

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

本實驗使用支持向量機模型作為分類器，且以高斯徑向基（RBF）作為核函數(shù)。實驗數(shù)據(jù)使用概念漂移生成器［13］生成，其中每種類型包含160000個樣本，且每4000條樣本漂移一次，生成器相關(guān)參數(shù)見表1?；瑒哟翱诖笮≡O(shè)定為2000，即每個數(shù)據(jù)塊包含2000條數(shù)據(jù)。

此外，本實驗使用3 種分類模型：KNN、決策樹（DT）、增量式支持向量機模型（SVM），進行比較性實驗。實驗結(jié)果見表2和表3。

表1 人造數(shù)據(jù)基本參數(shù)

表2 人造數(shù)據(jù)分類準確率

表3 人造數(shù)據(jù)分類耗時／s

從表2中可以看到，所提出模型的分類準確率要優(yōu)于其它分類模型，其原因是通過將概念漂移檢測機制引入到分類過程中，使得分類模型能夠更及時地進行自我更新，以適應(yīng)新數(shù)據(jù)環(huán)境的變化，保持分類準確率的穩(wěn)定。而其它分類模型，當(dāng)發(fā)生概念漂移時，由于更新不夠及時，導(dǎo)致分類準確率降低。

從表3中可以看到，盡管所提出模型在分類過程中增加了概念漂移檢測以及分類器池，但是分類整體速度卻未受影響，值得注意的是，所提出模型所消耗時間要少于增來式支持向量機模型所消耗時間。通過分析，可以發(fā)現(xiàn)由于使用了概念漂移檢測以及分類器池機制，能夠有效控制模型更新次數(shù)，做到有效更新，從而降低由于模型更新所消耗的時間，提高整體分類速度。這也說明所提出數(shù)據(jù)流分類模型能夠有效降低模型消耗時間，滿足數(shù)據(jù)流實時分類要求。

為了驗證分類器池遺忘機制的有效性，本實驗中以Circle數(shù)據(jù)為例，對分類器池中的概念數(shù)量進行統(tǒng)計，統(tǒng)計結(jié)果如圖7所示。通過分析，可以發(fā)現(xiàn)在開始階段，隨著數(shù)據(jù)流中數(shù)據(jù)的增加，概念呈現(xiàn)增長的趨勢，這時候也是發(fā)生概念漂移最多的時候。但是，當(dāng)數(shù)據(jù)達到一定數(shù)量時，分類器池中已經(jīng)包含了足夠多的概念，可以很好地描述數(shù)據(jù)流各種概念漂移情況，因此池中的概念數(shù)量保持穩(wěn)定，且使用遺忘機制后，舊的概念被刪除，即便有新概念出現(xiàn)也能控制分類器池的大小，基本控制在10左右，因此不會隨著數(shù)據(jù)量的增加，給系統(tǒng)造成額外負擔(dān)。

圖7 概念數(shù)量變化

4 結(jié)束語

概念漂移是數(shù)據(jù)流分類過程中的最棘手的問題。當(dāng)前流行的數(shù)據(jù)流分類方法在理概念漂移的時候，都有其局限性。針對這個問題，本文在借鑒所提出方法的基礎(chǔ)上，提出一種利用概念漂移檢測以及分類器池的數(shù)據(jù)流分類模型，在基本數(shù)據(jù)分類模型（支持向量機）進行分類之前，使用上述兩種機制對數(shù)據(jù)進行概念漂移檢測，這樣能夠提高分類模型對于概念漂移的使用度，且能夠減低概念漂移對于分類模型的影響。和傳統(tǒng)分類模型（支持向量機、KNN 模型、決策樹）相比，該算法能夠大大提高分類模型抗數(shù)據(jù)流概念漂移的能力，并且提高了分類的準確率。實驗中分別使用人造數(shù)據(jù)和真實數(shù)據(jù)對所提出模型進行驗證，證明其對于概念漂移具有更好的適應(yīng)性。

［1］BAO Liqun，MA Hongfeng，LI Xianglin.On concept drift in Bayesian spam classification ［J］.Computer Application and Software，2001，28 （9）：116－118 （in Chinese）. ［包理群，馬宏鋒，李祥林.貝葉斯郵件分類中概念漂移問題研究 ［J］.計算機應(yīng)用與軟件，2011，28 （9）：116－118.］

［2］GE Junwei，JIANG Xian，F(xiàn)ANG Yiqiu.Optimization of Map－Reduce data flow with message broker mechanism ［J］.Computer Engineering and Applications，2013，49 （5）：120－122（in Chinese）.［葛君偉，蔣仙，方義秋.消息代理機制下的MapReduce數(shù)據(jù)流優(yōu)化 ［J］.計算機工程與應(yīng)用，2013，49（5）：120－122.］

［3］ZHANG Zhongping，WANG Hao，XUE Wei，et al.Approach for data streams clustering over dynamic sliding windows［J］.Computer Engineering and Applications，2011，47 （7）：135－138 （in Chinese）.［張忠平，王浩，薛偉，等.動態(tài)滑動窗口的數(shù)據(jù)流聚類方法 ［J］.計算機工程與應(yīng)用，2011，47（7）：135－138.］

［4］CHEN Zhaoyang，HUANG Shangteng.On concept drift in stream data classification ［J］.Computer Application and Software，2009，26 （2）：254－257 （in Chinese）. ［陳照陽，黃上騰.流數(shù)據(jù)分類中的概念漂移問題研究 ［J］.計算機應(yīng)用與軟件，2009，26 （2）：254－257.］

［5］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.

［6］Orriols Puig A，Casillas J.Fuzzy knowledge representation study for incremental learning in data streams and classification problems［J］.Soft Computing，2011，15 （12）：2389－2414.

［7］Li L J，Zou B，Hu Q H，et al.Dynamic classifier ensemble using classification confidence ［J］.Neurocomputing，2013，99 （5）：581－591.

［8］Dai Q.A competitive ensemble pruning approach based on cross－validation technique ［J］.Knowledge－Based Systems，2013，37 （3）：394－414.

［9］Dries A，Rückert U.Adaptive concept drift detection ［J］.Statistical Analysis and Data Mining，2009，2 （6）：311－327.

［10］Hofer V，Krempl G.Drift mining in data：A framework for addressing drift in classification ［J］.Computational Statistics and Data Analysis，2013，57 （1）：377－391.

［11］Minku L L，Yao X.DDD：A new ensemble approach for dealing with concept drift［J］.IEEE Transactions on Knowledge and Data Engineering，2012，24 （4）：619－633.

［12］CHEN Wansong，ZHAO Lei.A new data stream feature selection algorithm based on attribute relevance［J］.Computer Application and Software，2012，29 （2）：254－257 （in Chinese）.［陳萬松，趙雷.一種新的基于屬性相關(guān)性的數(shù)據(jù)流特征選擇算法的研究 ［J］.計算機應(yīng)用與軟件，2012，29（2）：254－257.］

［13］Zhou J，F(xiàn)u Y，Wu Y，et al.Anomaly detection over concept drifting data streams［J］.Journal of Computational Information Systems，2009，5 （6）：1697－1703.