摘  要： 針對Lossy Counting算法，即一個基于計數的確定性方案，提出一種新的基于權重的流數據頻繁項挖掘算法（Lossy Weight），擴展了流數據頻繁項的作用域。Lossy Weight算法不僅可用于傳統的基于計數的頻繁項挖掘，還可以挖掘出在整個流數據中所占權重比重大于門檻值的數據。實驗數據分析證明該方案是有效的。
關鍵詞： 頻繁項；數據挖掘；權值

    基于計數的頻繁項挖掘算法適用于每個數據元組所含知識相等或近似的情況，例如用戶在網頁上的點擊流，搜索引擎的關鍵詞流、路由器上的IP包流等情況。但在更多的情況下，每個事務代表的知識是不相等的。如電信系統中的通話記錄，每個用戶的電話用時是不相同的；在證券交易中心，每筆交易的金額也是不同的。許多小客戶的事務數多，但每筆事務的權值很小；重要的大客戶事務數雖少，但每筆事務的權值很大。如果此時用原有的頻繁項挖掘算法，將不能很好地體現那些事務數少但重要性高的客戶。而采用新的基于權重的算法，則可以很好地找出那些重要性高的元素。
    本文提出的基于權重的新算法是對原有Lossy Counting[1]的擴展。不僅可以解決基于計數的頻繁項挖掘問題，還能解決基于權重的頻繁項挖掘問題。并且Lossy Counting算法本質上是新算法的一個特例(窗口定長，權值為1)。新算法在應用域上超出了原有算法，甚至可支持基于計數與權重的混合查詢。

2 Lossy Weight算法
    本文提出的基于權重的頻繁項挖掘算法(Lossy Weight Algorithm)與原有算法有著相同的定義：根據用戶定義的門檻參數s∈(0，1)，輸出在整個流數據中所占權重比重大于s的所有元素。
    新算法同樣滿足實時性的要求。在任意時間內，用戶都可以提交查詢，算法的結果滿足以下的要求：(1)數據所有占權重比超過s的元素都被輸出；(2)所有占權重比小于s-ε都不會被輸出；(3)權重頻繁項的誤差至多為ε。
    新的算法保持了原有的Lossy Counting實現簡單、處理速度快的特點。同樣地，在誤差的精確控制上有這樣兩個特點[2]：(1)存在誤報可能(false positive)；(2)誤報的誤差可控制。

2.2 新算法的優勢
    在Lossy Counting算法的基礎上改進的Lossy Weight算法保留了原有算法處理效率高、占用空間少、誤差精確可控的優點。同樣地，算法實現簡明，很容易應用到實踐當中。新算法包含了原有的Lossy Counting算法，具有更大的靈活性。新算法可根據實際情況劃分窗口，時間窗口大小靈活可變。Lossy Counting算法的時間窗口不可變，事實上就是窗口大小為、權值為1時的Lossy Weight算法的特例。通過靈活地選取窗大小，新的Lossy Weight算法可以得到更好的內存占用情況。
3 Lossy Weight算法的實驗分析
3.1 Lossy Weight算法的特性實驗
    本文采用國泰君安CSMAR(China Stock Market Ac-
counting 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.