數(shù)據(jù)流挖掘抑制概念漂移不良影響研究

卞舒逸

摘要：提升基于數(shù)據(jù)流的數(shù)據(jù)挖掘正確率并克服概念漂移的影響是當(dāng)前的研究熱點之一。相對于傳統(tǒng)意義上的數(shù)據(jù)挖據(jù)，基于數(shù)據(jù)流的數(shù)據(jù)挖掘具有動態(tài)、數(shù)量多、持續(xù)性強(qiáng)等特點。由于傳統(tǒng)的數(shù)據(jù)挖掘算法都是應(yīng)用于靜態(tài)數(shù)據(jù)，挖掘結(jié)果并不完全匹配動態(tài)變化。將樣本數(shù)據(jù)流進(jìn)行數(shù)據(jù)塊化處理后使用集成算法，可提升流數(shù)據(jù)挖掘的準(zhǔn)確性。其中集成算法基分類器包括決策樹和KNNModel算法等。對于不同算法的效果給予不同權(quán)值，提升算法相比于基分類器，能夠更加準(zhǔn)確地判定概念漂移的發(fā)生。實驗結(jié)果表明，通過集成學(xué)習(xí)方法可以有效提升學(xué)習(xí)效果及分類判定準(zhǔn)確率，非同質(zhì)類型的集成算法對于抑制概念漂移的不良影響可起到一定作用。

關(guān)鍵詞：數(shù)據(jù)流挖掘； 概念漂移； 數(shù)據(jù)塊； 集成算法

DOIDOI：10.11907/rjdk.181079

中圖分類號：TP3-0

文獻(xiàn)標(biāo)識碼：A文章編號文章編號：16727800（2018）009006403

英文標(biāo)題Research on Data Flow Learning Suppression of Concept Drift Adverse Effects

——副標(biāo)題

英文作者BIAN Shuyi

英文作者單位（School of Computer， Nanjing University of Posts and Telecommunications， Nanjing 210003， China）

英文摘要Abstract：It is an important research hotspot to improve the accuracy of data mining based on data mining and to deal with the impact of conceptual drift.Compared with data mining in the traditional sense，data mining of the data stream has such characteristics as dynamic， large amount and continuity.As the traditional data mining algorithms are applied to static data， the data mining results do not exactly match.In this paper， we improve the accuracy of streaming data mining by using an integrated algorithm.The integrated algorithm base classifier includes decision tree and KNNModel algorithm.Different weights are given to the corresponding algorithms.Compared with the base classifier， the lifting algorithm can determine the occurrence of concept drift more accurately.The integrated learning method can effectively improve the learning effect.The nonhomogeneous type of integration algorithm plays a certain role in suppressing the adverse effects of concept drift.

英文關(guān)鍵詞Key Words：data mining； concept drift； data block； integrated algorithm

0引言

如今，數(shù)據(jù)流挖掘在越來越多的領(lǐng)域得到大量應(yīng)用，常見應(yīng)用有銀行業(yè)務(wù)中的信用卡欺詐判別、阿里巴巴等在線平臺對客戶消費的推薦與預(yù)測，百度、谷歌等公司對于大量搜索信息的挖掘，電信、移動等運營商的通訊信息處理等。數(shù)據(jù)流挖掘已經(jīng)成為當(dāng)前的研究熱點之一[1]。然而，由于數(shù)據(jù)流本身的動態(tài)特性，特別是其中存在的概念漂移問題，使傳統(tǒng)意義上的數(shù)據(jù)挖掘算法無法達(dá)到令人滿意的效果。由于概念漂移現(xiàn)象的影響，數(shù)據(jù)流挖掘需要在數(shù)據(jù)特性隨時間變化時能夠自適應(yīng)地跟隨變化，從而保證流數(shù)據(jù)挖掘的性能[2]。

最早提出的針對概念漂移的數(shù)據(jù)流分類方法是2001年Hulten等[3]提出的CVFDT算法，其將VFDT算法進(jìn)行改進(jìn)，通過構(gòu)建替代子樹的方法克服概念漂移的影響。當(dāng)檢測到概念漂移時，CVFDT使用所構(gòu)建的替代子樹替換原有VFDT樹中的子樹，使VFDT能夠及時更新，從而適應(yīng)新數(shù)據(jù)環(huán)境。因此，CVFDT算法不僅繼承了VFDT分類效率高的特點，而且能夠克服概念漂移對模型造成的影響，以保持分類的準(zhǔn)確與穩(wěn)定。隨著研究的深入，利用增量式學(xué)習(xí)思想對模型進(jìn)行實時更新成為新的研究熱點。Aboalsamh等[4]提出一種使用增量式學(xué)習(xí)方法的數(shù)據(jù)流分類模型，通過將分類模型學(xué)習(xí)過程進(jìn)行增量式處理，能夠加快模型的自我更新速度，從而通過不斷更新模型的方式解決概念漂移問題；Kuncheva等[5]對數(shù)據(jù)流分類模型進(jìn)行研究，發(fā)現(xiàn)分類模型的準(zhǔn)確率不僅受到概念漂移及數(shù)據(jù)本身質(zhì)量的影響，而且還與滑動窗口大小有關(guān)。因此，基于以上觀察，提出一種可變滑動窗口的數(shù)據(jù)流分類模型。當(dāng)發(fā)生概念漂移時，滑動窗口能夠自動放大或縮小窗口，使分類模型能夠有效地檢測概念漂移，以保證分類模型的及時更新，提高分類過程的準(zhǔn)確率；Seo等[6]對多變量數(shù)據(jù)流進(jìn)行研究，使用時間變量挖掘數(shù)據(jù)流中各屬性之間的關(guān)聯(lián)關(guān)系，進(jìn)而使用這些關(guān)系對數(shù)據(jù)流分類進(jìn)行指導(dǎo)。

根據(jù)強(qiáng)可學(xué)習(xí)和弱可學(xué)習(xí)的概念，由于在實際應(yīng)用中，弱可學(xué)習(xí)算法更容易被發(fā)現(xiàn)，而其又可以被證明與強(qiáng)可學(xué)習(xí)算法等價[7]，所以使用集成學(xué)習(xí)方法，對應(yīng)不同應(yīng)用條件，相對賦予其中算法不同權(quán)值，可以得到更好的學(xué)習(xí)效果。本文主要研究非同質(zhì)型集成算法對于概念漂移自適應(yīng)能力的提升。

1基礎(chǔ)分類器算法介紹

1.1基于增量的KNNModel算法

KNNModel算法與傳統(tǒng)的KNN算法相比，k值的確定更為容易，而且KNNModel能較好地滿足數(shù)據(jù)流挖掘工作對效率的要求。KNNModel算法的核心思想與KNN相近，以一個特征點為圓心作為分類區(qū)域，一方面盡可能包括相同樣本，另一方面要避免包括異類，使圓盡量大[8]。保存下來比較有效的模型簇形式是四元組和五元組，包括類別、半徑、數(shù)量和圓心。通過不斷迭代，最終達(dá)到分類目的[9]。

層次糾錯輸出編碼相對于傳統(tǒng)算法事先構(gòu)造出同一編碼矩陣進(jìn)行分割，其能使用簇描述數(shù)據(jù)分布，是一種構(gòu)建層次的方法。層次糾錯輸出編碼的核心思想是，通過對同類簇采用一一對應(yīng)的方式編碼，使相同簇合并，并按照由多到少、由下到上的順序?qū)⒆罱咏膬蓚€簇合并起來[10]。上述方法的通用性在于其可以與其它算法相融合，擴(kuò)大算法適用范圍，從而使該算法在分類和糾錯方面具有突出效果。

在此基礎(chǔ)上發(fā)展而來的基于增量的KNNModel動態(tài)層次糾錯輸出編碼算法可以處理概念漂移問題，其核心思想為：首先將數(shù)據(jù)流劃分為數(shù)據(jù)塊，在第一個數(shù)據(jù)塊上進(jìn)行學(xué)習(xí)；然后建立類別規(guī)則區(qū)域，之后建立層次樹層次碼，并以中心點和邊界距離為依據(jù)；最后采用可增量學(xué)習(xí)分類算法進(jìn)行學(xué)習(xí)，生成分類器集合。分類器集合生成過程的終點利用活躍程度進(jìn)行判斷[11]。

基于增量的KNNModel算法學(xué)習(xí)過程具體步驟如下：

（1）在數(shù)據(jù)塊上進(jìn)行預(yù)學(xué)習(xí)，建立規(guī)則區(qū)域，選擇合適的代表簇，建立層次樹層次編碼，利用學(xué)習(xí)算法學(xué)習(xí)后生成分類器集。

（2）開始進(jìn)行增量學(xué)習(xí)，具體步驟為：①數(shù)據(jù)到來后，根據(jù)代表簇對層次樹進(jìn)行更新；②有新類別出現(xiàn)時，依次計算已有類別的漂移度；③從漂移度最小的類別開始，根據(jù)情況進(jìn)行更新。

（3）根據(jù)編碼矩陣訓(xùn)練單分類器。

（4）學(xué)習(xí)后檢查編碼個數(shù)，對編碼進(jìn)行修剪。

1.2CVFDT決策樹算法

該算法中最重要的步驟是對概念漂移的判斷與處理，在接收到數(shù)據(jù)時，解決窗口內(nèi)的概念差異。該算法將窗口劃分為若干個基本窗口，然后選擇最新概念的數(shù)據(jù)。為了保證準(zhǔn)確性，算法記錄了滑動窗口的歷史分類[12]。若模型判斷發(fā)生了概念漂移，則選用集成分類器，去掉沒有價值的決策樹分支子樹并進(jìn)行重建。因為概率分布不均，若滑動窗口概念混亂將造成決策樹分類錯誤，所以不一致的分類屬性需要暫時緩存。決定對決策樹中各個節(jié)點進(jìn)行分類或替代需要等待一段時間進(jìn)行處理[13]，該處理方法可以在數(shù)據(jù)處理過程中減少噪聲的影響。

決策樹處理過程如下：

輸入：W={D1，D2，…，Dm}是滑動窗口數(shù)據(jù)塊集合；

輸出：Tree是用來分類的決策樹；

過程：For W 中的每個實例K

用Tree將K排入葉子節(jié)點L中

For 實例K所經(jīng)過的每個節(jié)點L

更新流入L節(jié)點實例概要結(jié)構(gòu)的N

For L節(jié)點替代子樹ALT中的每一個子樹

遞歸調(diào)用該過程處理決策樹的子樹

若L節(jié)點觀察的實例不全屬于同一類，且在當(dāng)前節(jié)點觀察的實例數(shù)大于數(shù)據(jù)塊

借助概要結(jié)構(gòu)N找到最佳分裂屬性Xa和次佳分類屬性Xb

若Xa與Xb間的信息熵之差滿足在閾值內(nèi)

則可認(rèn)為Xa是最佳分裂屬性，并在L點進(jìn)行分裂

初始化各個分裂節(jié)點的ALT樹與概要結(jié)構(gòu)N

2非同質(zhì)型集成算法

在集成算法中，分為同質(zhì)型集成算法即基分類器類別相同，以及非同質(zhì)型集成算法即基分類器類型不同。當(dāng)個體分類器差異變小時，不易提高集成分類器的準(zhǔn)確率，所以嘗試將KNN和決策樹兩種不同模型進(jìn)行混合，以期達(dá)到更好的學(xué)習(xí)性能[14]。

在集成策略中，使用最廣泛的是經(jīng)典提升算法Adaboost。Adaboost算法與Bagging算法類似，都有放回抽樣，不同的是訓(xùn)練數(shù)據(jù)權(quán)重不同。在Adaboost算法中，每個訓(xùn)練數(shù)據(jù)被賦予相同的初始權(quán)值。隨著分類訓(xùn)練的進(jìn)行，錯誤樣本會得到更高的權(quán)重，而正確分類的數(shù)據(jù)則會被降低權(quán)重。對于分類器，樣本權(quán)重越高，分類難度越大[15]。由于所有訓(xùn)練數(shù)據(jù)都被更新過一次，因此需要再次對其進(jìn)行規(guī)范化處理。

算法過程如下：

輸入：

訓(xùn)練數(shù)據(jù)集D

成員分類模型個數(shù)k

學(xué)習(xí)算法SM

輸出：集成分類模型M

方法：

將訓(xùn)練數(shù)據(jù)集D中的每條數(shù)據(jù)初始化權(quán)重置為1/d；

For i=1…k

從訓(xùn)練數(shù)據(jù)集D中挑出高權(quán)重樣本并產(chǎn)生訓(xùn)練子集D1；

對訓(xùn)練子集Di使用選定算法得到成員分類器Mi；

通過計算成員分類Mi的分類誤差；

If成員分類器Mi的分類誤差>0.5

重新將訓(xùn)練子集數(shù)據(jù)的初始化權(quán)重置為1/d；

再對抽樣訓(xùn)練數(shù)據(jù)子集產(chǎn)生新的成員分類器Mi；

End if

For 訓(xùn)練子集Di中被正確分類的數(shù)據(jù)

更新權(quán)重，用現(xiàn)有權(quán)重乘以error（Mi）/（1-error（Mi））

對更新完權(quán)重的數(shù)據(jù)作規(guī)范化處理；

Return M；

通過集成算法可以更加準(zhǔn)確地發(fā)現(xiàn)概念漂移現(xiàn)象，并及時調(diào)整分類模型，提高分類正確率。改進(jìn)的KNN和CVFDT都對概念漂移有一定自適應(yīng)能力，將這兩個模型作為弱分類器，采用集成算法結(jié)合生成混合模型。新模型對數(shù)據(jù)流變化有更好的適應(yīng)能力，同時也可通過混合模型方式減少決策樹算法對樣本的過度依賴。

3仿真驗證

為了驗證非同質(zhì)型集成算法的自適應(yīng)能力與應(yīng)對概念漂移的有效性，采用MATLAB仿真工具對新集成算法的有效性進(jìn)行檢測與分析，測試該方法在多種數(shù)據(jù)集下的效果。該仿真數(shù)據(jù)集由MATLAB仿真工具隨機(jī)生成，生成的數(shù)據(jù)集特征如表1所示。

從以上實驗結(jié)果可以看出，相對于改進(jìn)的KNN和決策樹，其集成后的模型性能得到提升。KNN對概念漂移的自適應(yīng)是最慢的，最后穩(wěn)定效果也最差；改進(jìn)的決策樹初始效果超過了KNN，最后的穩(wěn)定性能也比KNN好，但有可能出現(xiàn)過度依賴樣本的狀況；集成算法開始時的自適應(yīng)效果比決策樹略差，但之后逐漸提升，最后穩(wěn)定在比決策樹略高的水平上。由此可得，這種差異化的集成算法在應(yīng)對概念漂移方面具有更好的性能。

4結(jié)語

混合模型吸取了集成算法的優(yōu)點，將弱學(xué)習(xí)模型通過一定比例組合，以提升模型性能，并通過試驗進(jìn)行了驗證，但模型復(fù)雜度也相對變大。在決策樹算法中由罰函數(shù)抑制過擬合問題，可防止決策樹模型過于復(fù)雜，但只能適應(yīng)樣本，無法適應(yīng)新數(shù)據(jù)。對于該項研究的下一階段目標(biāo)是仿照決策樹方法，構(gòu)建合適的罰函數(shù)模型，以檢測該混合模型是否出現(xiàn)了過擬合現(xiàn)象。

參考文獻(xiàn)參考文獻(xiàn)：

[1]李思男，李寧，李戰(zhàn)懷.多標(biāo)簽數(shù)據(jù)挖掘技術(shù)研究綜述[J].計算機(jī)科學(xué)，2013，40（4）：1421.

[2]ELWELL R，POLIKAR R.Incremental learning of concept drift in nonstationary environments [J].Neural Networks，IEEE Transactions on，2011，22（10）：15171531.

[3]KOTSIANTIS S B，PINTELAS P E.Recent advances in clustering：a brief survey [J].WSEAS Trans on Information Science and Application，2004，11（1）：7381.

[4]WANG S，MINKU L L，GHEZZI D，et al.Concept drift detection for online class imbalance learning[C].Neural Networks （IJCNN），The 2013 International Joint Conference on.IEEE，2013：110.

[5]GUO G，WANG H，BELL D，et al.Using KNN model for automatic text categorization [J].Soft Computing，2006，10（5）：423430.

[6]李培培.數(shù)據(jù)流中概念漂移檢測與分類方法研究[D].合肥：合肥工業(yè)大學(xué)，2012.

[7]TSYMBAL A，PECHENIZKIY M，CUNNINGHAM P，et al.Dynamic integration of classifiers for handling concept drift [J].Information Fusion，2008，9（1）：5668.

[8]KOLTER J Z，MALOOF M A.Dynamic weighted majority：an ensemble method for drifting concepts [J].Journal of Machine Research，2007，8（12）：27552790.