吳媚　高玲

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

關(guān)鍵詞：數(shù)據(jù)挖掘；數(shù)據(jù)流；頻繁項；頻數(shù)統(tǒng)計

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

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

1 概述

1.1 基本定義

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

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

實驗中我們參考其他文獻(xiàn)用個數(shù)準(zhǔn)確率、錯誤偏差率描述各個算法的優(yōu)劣。個數(shù)準(zhǔn)確率：算法挖掘出的Top-K數(shù)據(jù)項中屬于真實數(shù)據(jù)項的個數(shù)之和與K的比率。錯誤偏差率：算法挖掘出的Top-K所有數(shù)據(jù)項的估算頻數(shù)之和與這些數(shù)據(jù)項真實頻數(shù)之和的比與標(biāo)準(zhǔn)單位1的絕對偏差率。

1.2 Space Saving算法描述

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

分析算法可知若某數(shù)據(jù)項ai的頻數(shù)超過F/S的值，則它必然出現(xiàn)在最后的緩沖區(qū)中，并且實驗發(fā)現(xiàn)在數(shù)據(jù)分布較平緩時，SS算法估算數(shù)據(jù)項頻率時也不夠準(zhǔn)確。

2 新算法描述

2.1 關(guān)鍵思想

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

2.2 改進(jìn)算法

更新操作用來根據(jù)閾值更新并維護(hù)樣本集內(nèi)的數(shù)據(jù)，描述如下：

輸入：數(shù)據(jù)流DS 輸出：樣本集S1，S2

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

⑵IF ai在S1中；ai對應(yīng)的計數(shù)器fi ++

⑶IF fi

⑷ELSE ai保留在S1

⑸ELSE IF ai在S2中；ai對應(yīng)的計數(shù)器fi ++

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

⑺ELSE ai保留在S2

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

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

⑽END

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

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

⑴合并樣本集S1，S2為S

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

⑶輸出所有Top-k頻繁數(shù)據(jù)項。

3 實驗對比分析

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

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

4 結(jié)束語

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

[參考文獻(xiàn)]

[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]王偉平，李建中，張冬冬，等.一種有效的挖掘數(shù)據(jù)流近似頻繁項算法 [J].軟件學(xué)報，2007，18（4）：884-892.