卞舒逸

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

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

DOIDOI：10.11907/rjdk.181079

中圖分類號(hào)：TP3-0

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

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

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

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

1.1基于增量的KNNModel算法

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

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

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

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

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

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

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

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

1.2CVFDT決策樹算法

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

決策樹處理過(guò)程如下：

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

輸出：Tree是用來(lái)分類的決策樹；

過(guò)程：For W 中的每個(gè)實(shí)例K

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

For 實(shí)例K所經(jīng)過(guò)的每個(gè)節(jié)點(diǎn)L

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

For L節(jié)點(diǎn)替代子樹ALT中的每一個(gè)子樹

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

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

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

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

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

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

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

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

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

算法過(guò)程如下：

輸入：

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

成員分類模型個(gè)數(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；

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

通過(guò)計(jì)算成員分類Mi的分類誤差；

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

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

再對(duì)抽樣訓(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））

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

Return M；

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

3仿真驗(yàn)證

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

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

4結(jié)語(yǔ)

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

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

[1]李思男，李寧，李戰(zhàn)懷.多標(biāo)簽數(shù)據(jù)挖掘技術(shù)研究綜述[J].計(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ù)流中概念漂移檢測(cè)與分類方法研究[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.