◆崔澤林

（北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 北京 100044）

基于密度網(wǎng)格的概念漂移檢測(cè)算法研究

◆崔澤林

（北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 北京 100044）

數(shù)據(jù)流的概念會(huì)隨著時(shí)間的變化而變化，例如天氣預(yù)報(bào)和網(wǎng)絡(luò)監(jiān)控。這種隨時(shí)改變概念的現(xiàn)象叫做概念漂移。如果不處理好概念漂移不僅降低聚類的質(zhì)量，并且還會(huì)導(dǎo)致錯(cuò)誤的聚類結(jié)果。現(xiàn)有的概念漂移算法大多都依據(jù)分類算法，根據(jù)分類算法中的錯(cuò)誤率來(lái)判斷概念漂移。然而，在隨時(shí)變化的數(shù)據(jù)流中很難發(fā)現(xiàn)類標(biāo)簽。在聚類檢測(cè)概念漂移中，很多聚類算法都是再概念漂移檢測(cè)之前，所以當(dāng)發(fā)生概念漂移的時(shí)候還要重新聚類。我們提出了一種基于密度網(wǎng)格的數(shù)據(jù)流聚類和概念漂移檢測(cè)算法，這個(gè)框架采用了一種策略動(dòng)態(tài)地改變滑動(dòng)窗口。由于用到了密度網(wǎng)格技術(shù)，它提升了DCDA檢測(cè)算法的效率，并且利用可變滑動(dòng)窗口替換了固定滑動(dòng)窗口以適應(yīng)數(shù)據(jù)流的變化。實(shí)驗(yàn)結(jié)果證明我們的框架在準(zhǔn)確率和時(shí)間效率上好于DCDA。

數(shù)據(jù)流挖掘；聚類；密度網(wǎng)格；概念漂移

0 引言

數(shù)據(jù)流聚類[11]在許多決策支持系統(tǒng)應(yīng)用的信息分析中發(fā)揮著越來(lái)越重要的作用，如網(wǎng)絡(luò)流量監(jiān)測(cè)、股票市場(chǎng)和信用卡欺詐檢測(cè)[2]等。聚類分析可以幫助我們理解數(shù)據(jù)分布和本質(zhì)。以往的研究表明，數(shù)據(jù)流的特點(diǎn)是實(shí)時(shí)、快速、海量、和無(wú)限的[8]。由于這樣的特點(diǎn)，數(shù)據(jù)流是不可能被控制順序并且難以放置所有數(shù)據(jù)流在內(nèi)存中的處理（通常，數(shù)據(jù)被處理一次，不能再次訪問(wèn)）。其聚類要求就是數(shù)據(jù)流聚類算法的時(shí)間復(fù)雜度必須低。

然而，數(shù)據(jù)流的概念也會(huì)隨時(shí)間的變化而變化的，即概念漂移[9]。換句話說(shuō)，我們從當(dāng)前數(shù)據(jù)中分析的概念會(huì)隨時(shí)間推動(dòng)而漂移。例如，客戶的購(gòu)買偏好可能會(huì)隨著時(shí)間而改變，這中購(gòu)買偏好可能取決星期、愛好的轉(zhuǎn)移、折現(xiàn)率等[3]。如果我們不及時(shí)檢測(cè)到概念漂移，我們最終可能得到錯(cuò)誤的概念，這不僅降低了聚類的質(zhì)量，也可能導(dǎo)致意想不到的聚類結(jié)果。因此，處理概念漂移在許多應(yīng)用中是至關(guān)重要的。

在本文中，我們提出一個(gè)新概念漂移檢測(cè)框架，這個(gè)框架基于密度網(wǎng)格[1]。此外，我們提出了一個(gè)可變大小的滑動(dòng)窗口，根據(jù)我們提出的策略動(dòng)態(tài)的改變滑動(dòng)窗口的大小以適應(yīng)數(shù)據(jù)流的變化，并加快檢測(cè)速度和準(zhǔn)確度。實(shí)驗(yàn)結(jié)果表明，我們提出的檢測(cè)框架比現(xiàn)有方法更準(zhǔn)確和更有效。

1 研究相關(guān)工作

概念漂移[9]是由Schlimmer和Granger提出。數(shù)據(jù)流中的概念漂移是指數(shù)據(jù)點(diǎn)在不同的時(shí)間段服從不同的分布模型的現(xiàn)象。Stream-detect[7]提出了通過(guò)隨著時(shí)間的推移測(cè)量在線聚類結(jié)果偏差，識(shí)別數(shù)據(jù)流的變化。通過(guò)比較聚類中心均值、標(biāo)準(zhǔn)偏差、平均聚類規(guī)模、集群中新老聚類中心的聚類特征來(lái)度量聚類之間的偏差。如果超過(guò)一定的閾值，那么概念已經(jīng)改變。但無(wú)論數(shù)據(jù)流是否漂移，流檢測(cè)需要重新聚類的每一步。因此它的時(shí)間效率非常低。在論文[2]，基于粗糙集理論和滑動(dòng)窗口技術(shù)，作者提出了一種改進(jìn)依賴于聚類的檢測(cè)算法算法，它通過(guò)計(jì)算當(dāng)前滑動(dòng)窗口和歷史滑動(dòng)窗口之間的距離來(lái)檢測(cè)概念漂移。只有當(dāng)距離大于閾值時(shí)，才在當(dāng)前滑動(dòng)窗口中進(jìn)行重新聚類，以捕捉新出現(xiàn)的新概念。結(jié)果時(shí)間效率有所提升。不幸的是，該算法只適用于分類性數(shù)據(jù)流，并且因?yàn)榛瑒?dòng)窗口是固定的，它不適應(yīng)數(shù)據(jù)流的變化。

基于密度網(wǎng)格的聚類算法已經(jīng)成為了一個(gè)被廣泛接受的聚類框架[1]，并且有很好的聚類效果。它可以找到任意形狀的簇集和有效地處理噪聲。在此基礎(chǔ)上也有許多基于密度網(wǎng)格的聚類算法被提出，如D-Stream I[4]、DD-Stream[10]和GDC-Stream[6]。這些都是單遍掃描算法，只處理原始數(shù)據(jù)一次，并且不需要設(shè)置的簇群個(gè)數(shù)。網(wǎng)格具有統(tǒng)計(jì)效果，所以聚類僅依賴于網(wǎng)格的數(shù)量，而不再管數(shù)據(jù)流中數(shù)據(jù)點(diǎn)的實(shí)數(shù)?；诿芏染W(wǎng)格的聚類算法采用兩階段方案[5]，包括一個(gè)在線組件和離線組件。在在線組件鐘，將讀取的數(shù)據(jù)點(diǎn)映射到網(wǎng)格中，并更新的網(wǎng)格鐘的密度。在離線組件中，它使用不完全分區(qū)策略，將密度網(wǎng)格聚類得到結(jié)果。

圖1 可變滑動(dòng)窗口調(diào)整策略

2 基于密度網(wǎng)格的概念漂移檢測(cè)算法

我們提出框架是一種基于密度網(wǎng)格的聚類框架[1]，有一個(gè)在線組件和離線組件。在在線組件中，我們定義一個(gè)臨時(shí)密度網(wǎng)格和舊密度網(wǎng)格?？勺兓瑒?dòng)窗口讀取新的數(shù)據(jù)流記錄。當(dāng)可變滑動(dòng)窗口滿時(shí)，將數(shù)據(jù)流映射到臨時(shí)密度網(wǎng)格中，臨時(shí)網(wǎng)格單元更新網(wǎng)格中的特征向量。然后計(jì)算臨時(shí)密度網(wǎng)格和舊密度網(wǎng)格概念之間的距離。如果距離小于某一閾值，則將臨時(shí)密度網(wǎng)格合并到舊密度網(wǎng)格中，并通過(guò)策略改變滑動(dòng)窗口的大小。否則，如果距離大于閾值，它會(huì)清除舊的密度網(wǎng)格和交換舊的密度網(wǎng)格和臨時(shí)密度網(wǎng)格之間的作用，并且初始化滑動(dòng)窗口大小。在離線組件中，我們對(duì)舊密度網(wǎng)格進(jìn)行聚類并得到聚類結(jié)果。

2.1 概念漂移檢測(cè)算法

在線部件處理過(guò)程中，為了檢測(cè)概念漂移我們提高了DCDA算法檢測(cè)模型，我們通過(guò)計(jì)算舊密度網(wǎng)格和臨時(shí)密度網(wǎng)格的距離判斷概念漂移是否發(fā)生。我們利用網(wǎng)格的統(tǒng)計(jì)特性，這意味著我們的方法適用于一般數(shù)據(jù)。我們的方法只依賴于網(wǎng)格的數(shù)量，而不管數(shù)據(jù)流的實(shí)數(shù)。因此，大大提高了檢測(cè)速度。此外，DCDA使用一個(gè)固定大小的滑動(dòng)窗口，不能適應(yīng)數(shù)據(jù)流的變化。在本文中，我們利用一個(gè)可變的滑動(dòng)窗口，我們將在下一節(jié)描述。

我們改進(jìn)的檢測(cè)公式如下：

那么T與O關(guān)于屬性空間S的距離可以表示為：

2.2 滑動(dòng)窗口調(diào)整策略

滑動(dòng)窗口的大小對(duì)于概念漂移檢測(cè)算法非常重要，它不僅影響著檢測(cè)效率還影響著檢測(cè)的準(zhǔn)確度。在文章[3]中所提到的，我們需要一個(gè)相對(duì)小的滑動(dòng)窗口來(lái)捕捉不穩(wěn)定的數(shù)據(jù)流頻繁的發(fā)生概念漂移。對(duì)于穩(wěn)定的、不經(jīng)常發(fā)生概念漂移的數(shù)據(jù)流，我們需要一個(gè)相對(duì)較大尺寸的滑動(dòng)窗口，以提高檢測(cè)效率。但是，具有挑戰(zhàn)意義的是，一些數(shù)據(jù)流可能會(huì)交替出現(xiàn)相對(duì)穩(wěn)定和頻繁變化兩種現(xiàn)象。對(duì)于這些數(shù)據(jù)流，由于其DCDA采用固定滑動(dòng)窗口大小，DCDA的檢測(cè)是無(wú)效的。

在本節(jié)中，我們提出了一個(gè)可變的滑動(dòng)窗口，如圖1所示。

首先，我們初始化一個(gè)滑動(dòng)窗口大小N和基于內(nèi)存容量設(shè)置最大值滑動(dòng)窗口NMAX。當(dāng)數(shù)據(jù)流裝滿滑動(dòng)窗口時(shí)，我們的框架把滑動(dòng)窗口中的映射到相應(yīng)的網(wǎng)格中。當(dāng)前副本網(wǎng)格是空的，所以我們復(fù)制當(dāng)前網(wǎng)格的特征向量復(fù)制到副本網(wǎng)格中，并清空當(dāng)前網(wǎng)格數(shù)據(jù)。我們使用我們提出的檢測(cè)當(dāng)前網(wǎng)格和副本網(wǎng)格之間是否發(fā)生概念漂移。如果當(dāng)前網(wǎng)格和副本網(wǎng)格是相同的概念，我們尋找是否有新的密度網(wǎng)格在當(dāng)前網(wǎng)格而不在網(wǎng)格副本中，計(jì)算所有新增的密度網(wǎng)格的密度，然后設(shè)置滑動(dòng)窗口大小為N = N + M（如果N+M大于NMAX，然后N=NMAX），將當(dāng)前網(wǎng)格數(shù)據(jù)合并到副本網(wǎng)格中；如果當(dāng)前網(wǎng)格數(shù)據(jù)和副本網(wǎng)格發(fā)生概念漂移，則在下一步恢復(fù)滑動(dòng)窗口為原來(lái)的大小。

3 實(shí)驗(yàn)結(jié)果

3.1 實(shí)驗(yàn)設(shè)備與數(shù)據(jù)集

我們?yōu)榱蓑?yàn)證我們提出的框架概念漂移算法和聚類效果，實(shí)驗(yàn)環(huán)境采用真實(shí)的數(shù)據(jù)集KDD CUP-99，這個(gè)數(shù)據(jù)集被多篇數(shù)據(jù)流聚類文章引用。這個(gè)數(shù)據(jù)包含了麻省理工學(xué)院林肯實(shí)驗(yàn)室收集的網(wǎng)絡(luò)入侵檢測(cè)的數(shù)據(jù)流數(shù)據(jù)，數(shù)據(jù)集包含了41維屬性，其中有34維連續(xù)型數(shù)值屬性和7中分類型屬性。

3.2 實(shí)驗(yàn)結(jié)果評(píng)價(jià)指標(biāo)

為了與DCDA概念漂移檢測(cè)聚類框架做對(duì)比，我們的實(shí)驗(yàn)采用了跟它一樣的評(píng)價(jià)指標(biāo)即使用精度和召回率。如果a是數(shù)據(jù)集中存在的概念漂移現(xiàn)象次數(shù)，b是我們提出的框架檢測(cè)出來(lái)的概念漂移現(xiàn)象的個(gè)數(shù)和c是我們正確檢測(cè)出概念漂移現(xiàn)象的個(gè)數(shù)。那么精度和召回率分別定義為：

3.3 實(shí)驗(yàn)結(jié)果對(duì)比

為了和DCDA框架的實(shí)驗(yàn)結(jié)果綜合比較，我們隨滑動(dòng)窗口大小不同做實(shí)驗(yàn)并采用的評(píng)價(jià)標(biāo)準(zhǔn)和測(cè)試兩個(gè)實(shí)驗(yàn)框架的時(shí)間效率。首先我們?cè)O(shè)置概念漂移檢測(cè)閾值 θ= 0.1和參數(shù) α= 0.5。實(shí)驗(yàn)結(jié)果如圖2所示：我們可以看出在前部分F1值我們的框架比DCDA高，往后跟DCDA趨于平衡。從圖3可以看出時(shí)間的性能比較，很明顯，我們的框架概念漂移檢測(cè)時(shí)間成本比DCDA低很多。

圖3 時(shí)間消耗的比較

[1]曹付元．面向分類數(shù)據(jù)的聚類算法研究[D]．山西大學(xué)，2010．

[2]張杰，趙峰．流數(shù)據(jù)概念漂移的檢測(cè)算法[J]．控制與決策，2013．