一種基于計數的數據流頻繁項挖掘算法的改進

吳媚　高玲

摘 要：查找數據流中的頻繁項是數據流挖掘中的熱點問題之一。挖掘數據流頻繁項在網絡流量監測、金融服務等多個領域有著廣泛的應用。本文首先概述經典算法Space Saving的思想并分析其性能，提出一種基于計數的改進算法維護樣本集。實驗表明，改進的算法能一定程度上提高準確率，避免對頻繁項的錯誤判斷。

關鍵詞：數據挖掘；數據流；頻繁項；頻數統計

近年來，隨著數據量以每天數以百萬計甚至無上限的速度增長，如何在復雜的資料中獲取有用的信息成為數據時代的我們所要面對的新考驗。數據流挖掘作為數據挖掘的一個分支方向，其中的挖掘數據流頻繁項作為熱點問題，所研究領域所涉及的應用廣泛，存在于商業金融，網絡流量監控，入侵檢測等多個方面。

數據流挖掘技術大致分為四類：聚類、分類、頻數統計和時間序列分析。頻數統計包括在單個或多個數據流上提取出現頻率超過指定閾值的頻繁項或者項集，是研究的重點。頻數統計主要涉及：頻繁項或頻繁項集挖掘、Top-K數據項及數據項集挖掘等。本文在Space Saving算法基礎上，提出維護兩個樣本集的思路以期挖掘出的Top-K頻繁項集的結果能減少對數據項的錯誤判斷并一定程度上提高算法的效率。

1 概述

1.1 基本定義

數據流DS為：隨著時間到來的有序無限的數據項集合，表示成DS={a1，a2…an}，其中任何數據項ai都來源于集合{1，2，…，Z}，Z代表數據項的分布范圍；fi代表數據項ai出現的頻數；F=f1+f2+…+fn，F為到達的n個數據項的頻數之和。

Top-K數據項的定義如下：時間t1-t2內對于所有數據項，按照它們出現的真實或估算頻數排序，其中頻數最高的K個數據項就是真實或估算的Top-K數據項，K為任意數值。由于挖掘算法僅保存數據流中部分的數據，數據分布又隨時間變化，準確挖掘頻繁項通常是不可能的，故文中涉及的算法都是基于抽樣的近似算法，挖掘出的Top-K也為近似結果。

實驗中我們參考其他文獻用個數準確率、錯誤偏差率描述各個算法的優劣。個數準確率：算法挖掘出的Top-K數據項中屬于真實數據項的個數之和與K的比率。錯誤偏差率：算法挖掘出的Top-K所有數據項的估算頻數之和與這些數據項真實頻數之和的比與標準單位1的絕對偏差率。

1.2 Space Saving算法描述

文獻[1]認為Space Saving算法[2]是當前在數據流上做頻繁項挖掘最好的算法。令t1到t2內每個經過的數據項形式為{（a1，1），（a2，1），…（an，1）}，樣本集為S，統計頻數的計數器為（ai，fi）。初始時，算法依次掃描到來的數據項，若ai存在在樣本集S中，在其數據項對應的計數器上加1；若ai不在S中且樣本集不滿，將（ai，fi）加入到樣本集S中；否則ai不在S中且S已滿，首先做刪除頻數最小的數據項am的操作，后把fi+fm作為新數據項ai的初始頻數插入到樣本集S中。

分析算法可知若某數據項ai的頻數超過F/S的值，則它必然出現在最后的緩沖區中，并且實驗發現在數據分布較平緩時，SS算法估算數據項頻率時也不夠準確。

2 新算法描述

2.1 關鍵思想

針對SS算法若某數據項ai的頻數超過數據項頻率F/樣本集S時，則它必然出現在最后的緩沖區中這一問題。在新算法內，增加一個樣本集S2，即將樣本集S分成S1和S2兩個樣本集來存儲，判定閾值m即為F/S的值，若頻數大于m則將對應數據項存入S2進行下一輪計數，當隨著計數小于m時，則從S2將對應的數據退回到S1中。

2.2 改進算法

更新操作用來根據閾值更新并維護樣本集內的數據，描述如下：

輸入：數據流DS 輸出：樣本集S1，S2

⑴F=F+fi；m=F/S

⑵IF ai在S1中；ai對應的計數器fi ++

⑶IF fi

⑷ELSE ai保留在S1

⑸ELSE IF ai在S2中；ai對應的計數器fi ++

⑹IF fi>m將ai移入S1中，并刪除S2中ai

⑺ELSE ai保留在S2

⑻ELSE IF S2不滿；將加到S2中

⑼ELSE 選取S2中計數值fm最小的數據項am；將加入S2中；刪除數據項am

⑽END

查詢操作即是在維護的樣本集中挖掘Top-k頻繁項的具體結果，描述如下：

輸入：樣本集合S1、S2，K。輸出：Top-k頻繁項。

⑴合并樣本集S1，S2為S

⑵遍歷樣本集S中數據項并按照頻次從大到小排序

⑶輸出所有Top-k頻繁數據項。

3 實驗對比分析

為了說明新算法在挖掘Top-k頻繁項時體現的效率，我們選取與Lossy Counting[3]算法、SS算法以及Efficient Count[4]一同比較。算法均在Visual Studio 2010開發使用C++語言編寫，實驗在Intel Core i7 CPU、主頻2.4G、內存8G的PC上運行。實現數據采用matlab隨機生成的模擬數據，各算法的個數準確率、錯誤偏差率和運行時間結果如下所示：

分析上述實驗結果，圖1中一開始數據量較小的情況下，LC和SS算法準確率較高，隨著數據量增大，四種算法的準確性都一定程度上下降，但LC和新算法的優勢就凸顯出來。圖2中可以明顯看出EC、SS算法的的錯誤偏差率很高，而新算法在能否準確的搜索頻繁項方面優于LC和SS算法。綜合考慮時空效率及實驗結果，新算法在一定程度上能提高搜索頻繁項的準確率。

4 結束語

數據流頻繁項集挖掘是一個具有挑戰性的問題，因數據流的特點，算法只能對數據進行一次掃描且存儲空間有限。本文在挖掘數據流上的頻繁項時，采用的模型僅考慮如何維護樣本集中的數據項，這是基于計數方法的模型框架，還可以嘗試其他的模型架構。本文在經典算法的基礎上提出對樣本集維護策略的改變。實驗表明，改進的算法能一定程度上提高挖掘頻繁項的準確率，減少對數據項的錯誤判斷。

[參考文獻]

[1]Liu H，Lin Y，Han J.Methods for mining frequent items in data streams：an overview[J].Knowledge and information systems，2011，26（1）：1-30.

[2]Metwally A，Agrawal D，El Abbadi A.Efficient computation of frequent and top-k elements in data streams[M].Database Theory-ICDT 2005.Springer Berlin Heidelberg，2005：398-412.

[3]Manku G S，Motwani R.Approximate frequency counts over data streams[C].Proceedings of the 28th international conference on Very Large Data Bases.VLDB Endowment，2002： 346-357.

[4]王偉平，李建中，張冬冬，等.一種有效的挖掘數據流近似頻繁項算法 [J].軟件學報，2007，18（4）：884-892.