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

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

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

2.2 新算法的優(yōu)勢
    在Lossy Counting算法的基礎(chǔ)上改進(jìn)的Lossy Weight算法保留了原有算法處理效率高、占用空間少、誤差精確可控的優(yōu)點。同樣地，算法實現(xiàn)簡明，很容易應(yīng)用到實踐當(dāng)中。新算法包含了原有的Lossy Counting算法，具有更大的靈活性。新算法可根據(jù)實際情況劃分窗口，時間窗口大小靈活可變。Lossy Counting算法的時間窗口不可變，事實上就是窗口大小為、權(quán)值為1時的Lossy Weight算法的特例。通過靈活地選取窗大小，新的Lossy Weight算法可以得到更好的內(nèi)存占用情況。
3 Lossy Weight算法的實驗分析
3.1 Lossy Weight算法的特性實驗
    本文采用國泰君安CSMAR(China Stock Market Ac-
counting Research)系列數(shù)據(jù)庫中的中國股票交易高頻數(shù)據(jù)庫作為實驗數(shù)據(jù)[3]。本實驗采用了上海證券交易所2009年12月5日～12月7日三天的股票交易高頻數(shù)據(jù)。日均20萬條交易記錄，總計為590 233條交易計錄。在流數(shù)據(jù)頻繁項挖掘?qū)嶒炛?，將?shù)據(jù)按時間排序，并模擬其實時到達(dá)的特性，對送達(dá)流數(shù)據(jù)處理引擎進(jìn)行頻繁項挖掘。
    對整個交易日所有個股的交易信息采用LW算法進(jìn)行數(shù)據(jù)處理，對交易量所占比重大于l％的個股進(jìn)行頻繁項挖掘，然后對內(nèi)存使用情況進(jìn)行分析。原有的LC算法不能處理帶權(quán)重的挖掘任務(wù)。在實驗中，定義了不同窗口大小，并對其進(jìn)行了分析。
    圖1所示實驗是在s=l％、ε=0．1％情況下，截取交易日前5 000個數(shù)據(jù)的內(nèi)存使用情況進(jìn)行對比。實驗顯示，LW算法的窗口尺寸越小，裁剪次數(shù)越頻繁，則內(nèi)存使用效果越好。但過多的裁剪無疑會加大系統(tǒng)的負(fù)荷。所以可以根據(jù)系統(tǒng)的負(fù)載大小來合理地確定窗口寬度。LW算法中窗口尺寸的可伸縮性使得算法適應(yīng)能力更強。

    LW算法的內(nèi)存占用情況取決于窗口尺寸和錯誤容許度s的大小。容許的錯誤度越大，內(nèi)存使用情況就越好。在窗口大小相等的情況下，對不同的錯誤容許度進(jìn)行頻繁項挖掘。
    圖2顯示了在相同窗口大小(width=1 000)情況下，不同ε的內(nèi)存占用情況。實驗顯示，LW算法對內(nèi)存空間的需求與誤差ε-1近似成正比。因此，在不影響最終決策的前提下，錯誤容許度ε越大越好。

3.2 LW算法對LC算法的對比實驗
    Lossy Weight算法是對Lossy Counting算法的改進(jìn)。在應(yīng)用上有更廣的范圍，在原有的問題領(lǐng)域，新算法同樣占有優(yōu)勢。LC算法的窗口大小是固定的ε-1，LW算法的窗口是動態(tài)的，可以應(yīng)對任意窗口大小。這就可以面對更復(fù)雜的應(yīng)用情況。在數(shù)據(jù)流量大時，擴大窗口尺寸，能起到批處理的效能。當(dāng)系統(tǒng)較空閑時，減少窗口尺寸，以得到更好的內(nèi)存使用情形。
    如圖3所示，在實驗中，截取交易日前5 000個數(shù)據(jù)的內(nèi)存使用情況進(jìn)行對比。實驗設(shè)置LW窗口大小為LC大小的一半。在第一個窗口，可以看到LW算法與LC算法的內(nèi)存占用是相同的。但到窗口邊沿時，裁剪后的內(nèi)存占用得到明顯的下降。通過對整個流的處理對比，可以明顯地看出LW算法具有更好的內(nèi)存使用情況。

    本文提出了一種新的基于權(quán)重的流數(shù)據(jù)頻繁項挖掘算法。擴展了流數(shù)據(jù)頻繁項的作用域。Lossy Weight算法不僅可用于傳統(tǒng)的基于計數(shù)的頻繁項挖掘，還可以挖掘出在整個流數(shù)據(jù)中所占權(quán)重比重大于門檻值的數(shù)據(jù)。
參考文獻(xiàn)
[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] 潘云鶴，王金龍，徐從富．?dāng)?shù)據(jù)流頻繁模式挖掘研究進(jìn)展[J]．自動化學(xué)報，2006，32(4)：594-602.
[3] 朱世武，嚴(yán)玉星．金融數(shù)據(jù)庫[M]．北京：清華大學(xué)出版社，2007：12-14.