基于權重的流數據頻繁項挖掘算法的應用

楊 立

（運城學院 公共計算機教學部，山西 運城044000）

基于計數的頻繁項挖掘算法適用于每個數據元組所含知識相等或近似的情況，例如用戶在網頁上的點擊流，搜索引擎的關鍵詞流、路由器上的IP包流等情況。但在更多的情況下，每個事務代表的知識是不相等的。如電信系統中的通話記錄，每個用戶的電話用時是不相同的；在證券交易中心，每筆交易的金額也是不同的。許多小客戶的事務數多，但每筆事務的權值很小；重要的大客戶事務數雖少，但每筆事務的權值很大。如果此時用原有的頻繁項挖掘算法，將不能很好地體現那些事務數少但重要性高的客戶。而采用新的基于權重的算法，則可以很好地找出那些重要性高的元素。

本文提出的基于權重的新算法是對原有Lossy Counting[1]的擴展。不僅可以解決基于計數的頻繁項挖掘問題，還能解決基于權重的頻繁項挖掘問題。并且Lossy Counting算法本質上是新算法的一個特例(窗口定長，權值為1)。新算法在應用域上超出了原有算法，甚至可支持基于計數與權重的混合查詢。

1 Lossy Counting算法

算法數據結構為三元組(e，f，Δ)的集合D。其中 e表示為流中的元素，f為估計的計數，Δ為f可能的最大誤差。D初始為空，每當有一個新元素e到達時，首先在D中查找是否已存在包含e的元組。若存在則對應的該元組計數 f加 l；否則創建一個新的元組(e，1，bcurr-1)。當到達窗口邊界時，對 D進行如下裁剪：若元組（e，f，Δ)滿足f+Δ≤bcurr，則刪除該元組。當查詢到達時，返回所有 f≥(s-ε)N的元組。

2 Lossy Weight算法

本文提出的基于權重的頻繁項挖掘算法(Lossy Weight Algorithm)與原有算法有著相同的定義：根據用戶定義的門檻參數s∈(0，1)，輸出在整個流數據中所占權重比重大于s的所有元素。

新算法同樣滿足實時性的要求。在任意時間內，用戶都可以提交查詢，算法的結果滿足以下的要求：(1)數據所有占權重比超過s的元素都被輸出；(2)所有占權重比小于 s-ε都不會被輸出；(3)權重頻繁項的誤差至多為ε。

新的算法保持了原有的Lossy Counting實現簡單、處理速度快的特點。同樣地，在誤差的精確控制上有這樣兩 個 特 點[2]：(1)存 在 誤 報 可 能(false positive)；(2)誤 報 的誤差可控制。

2.1 Lossy Weight算法實現

新算法有如下的定義：用戶必須明確地指定門檻參數s和誤差參數ε，并且定義流數據當前大小為N。

初始，D=φ，Vb-1=0。

當一個新元素e到達時，將e的權值Wi加入計數器V，之后對D進行更新操作。首先查找D中是否存在e。如果存在，將e的權值加入W。否則新建成員(e，Wi，εVb-1)。

在窗口的邊界，對D進行裁剪。裁剪的規則很簡單，當 W+Δ≤εV時，即從 D中刪除該元組。裁剪后，更新Vb-1的值為當前的V。當查詢到達時，返回所有W≥(sε)N的元組。

2.2 新算法的優勢

3 Lossy Weight算法的實驗分析

3.1 Lossy Weight算法的特性實驗

本文采用國泰君安CSMAR(China Stock Market Accounting Research)系列數據庫中的中國股票交易高頻數據庫作為實驗數據[3]。本實驗采用了上海證券交易所2009年12月5日～12月7日三天的股票交易高頻數據。日均20萬條交易記錄，總計為590 233條交易計錄。在流數據頻繁項挖掘實驗中，將數據按時間排序，并模擬其實時到達的特性，對送達流數據處理引擎進行頻繁項挖掘。

對整個交易日所有個股的交易信息采用LW算法進行數據處理，對交易量所占比重大于l%的個股進行頻繁項挖掘，然后對內存使用情況進行分析。原有的LC算法不能處理帶權重的挖掘任務。在實驗中，定義了不同窗口大小，并對其進行了分析。

圖1所示實驗是在s=l%、ε=0.1%情況下，截取交易日前5 000個數據的內存使用情況進行對比。實驗顯示，LW算法的窗口尺寸越小，裁剪次數越頻繁，則內存使用效果越好。但過多的裁剪無疑會加大系統的負荷。所以可以根據系統的負載大小來合理地確定窗口寬度。LW算法中窗口尺寸的可伸縮性使得算法適應能力更強。

LW算法的內存占用情況取決于窗口尺寸和錯誤容許度s的大小。容許的錯誤度越大，內存使用情況就越好。在窗口大小相等的情況下，對不同的錯誤容許度進行頻繁項挖掘。

圖2顯示了在相同窗口大小(width=1 000)情況下，不同ε的內存占用情況。實驗顯示，LW算法對內存空間的需求與誤差ε-1近似成正比。因此，在不影響最終決策的前提下，錯誤容許度ε越大越好。

3.2 LW算法對LC算法的對比實驗

Lossy Weight算法是對Lossy Counting算法的改進。在應用上有更廣的范圍，在原有的問題領域，新算法同樣占有優勢。LC算法的窗口大小是固定的ε-1，LW算法的窗口是動態的，可以應對任意窗口大小。這就可以面對更復雜的應用情況。在數據流量大時，擴大窗口尺寸，能起到批處理的效能。當系統較空閑時，減少窗口尺寸，以得到更好的內存使用情形。

如圖3所示，在實驗中，截取交易日前5 000個數據的內存使用情況進行對比。實驗設置LW窗口大小為LC大小的一半。在第一個窗口，可以看到LW算法與LC算法的內存占用是相同的。但到窗口邊沿時，裁剪后的內存占用得到明顯的下降。通過對整個流的處理對比，可以明顯地看出LW算法具有更好的內存使用情況。

本文提出了一種新的基于權重的流數據頻繁項挖掘算法。擴展了流數據頻繁項的作用域。Lossy Weight算法不僅可用于傳統的基于計數的頻繁項挖掘，還可以挖掘出在整個流數據中所占權重比重大于門檻值的數據。

[1]MANKU Q S，MOTWANI R.Approximate frequency counts over data streams[C].Proc.of the 28th Intl.Conf.on VeD，Large Data Bases.Hongkong：MorganKaufmann，2002：346-357.

[2]潘云鶴，王金龍，徐從富.數據流頻繁模式挖掘研究進展[J].自動化學報，2006，32(4)：594-602.

[3]朱世武，嚴玉星.金融數據庫[M].北京：清華大學出版社，2007：12-14.