一種基于計(jì)數(shù)的數(shù)據(jù)流頻繁項(xiàng)挖掘算法的改進(jìn)

吳媚　高玲

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

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

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

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

1 概述

1.1 基本定義

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

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

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

1.2 Space Saving算法描述

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

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

2 新算法描述

2.1 關(guān)鍵思想

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

2.2 改進(jìn)算法

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

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

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

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

⑶IF fi

⑷ELSE ai保留在S1

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

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

⑺ELSE ai保留在S2

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

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

⑽END

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

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

⑴合并樣本集S1，S2為S

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

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

3 實(shí)驗(yàn)對(duì)比分析

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

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

4 結(jié)束語(yǔ)

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

[參考文獻(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ù)流近似頻繁項(xiàng)算法 [J].軟件學(xué)報(bào)，2007，18（4）：884-892.