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

◆崔澤林

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

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

◆崔澤林

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

2.1 概念漂移檢測算法

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

我們改進的檢測公式如下：

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

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

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

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

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

3 實驗結(jié)果

3.1 實驗設(shè)備與數(shù)據(jù)集

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

3.2 實驗結(jié)果評價指標(biāo)

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

3.3 實驗結(jié)果對比

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

圖3 時間消耗的比較

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

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