基于密度網格的概念漂移檢測算法研究

◆崔澤林

（北京交通大學計算機與信息技術學院 北京 100044）

基于密度網格的概念漂移檢測算法研究

◆崔澤林

（北京交通大學計算機與信息技術學院 北京 100044）

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

數據流挖掘；聚類；密度網格；概念漂移

0 引言

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

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

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

1 研究相關工作

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

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

圖1 可變滑動窗口調整策略

2 基于密度網格的概念漂移檢測算法

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

2.1 概念漂移檢測算法

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

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

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

2.2 滑動窗口調整策略

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

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

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

3 實驗結果

3.1 實驗設備與數據集

我們為了驗證我們提出的框架概念漂移算法和聚類效果，實驗環境采用真實的數據集KDD CUP-99，這個數據集被多篇數據流聚類文章引用。這個數據包含了麻省理工學院林肯實驗室收集的網絡入侵檢測的數據流數據，數據集包含了41維屬性，其中有34維連續型數值屬性和7中分類型屬性。

3.2 實驗結果評價指標

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

3.3 實驗結果對比

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

圖3 時間消耗的比較

[1]曹付元．面向分類數據的聚類算法研究[D]．山西大學，2010．

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