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

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

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

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

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

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

    本文提出了一種新的基于權(quán)重的流數(shù)據(jù)頻繁項(xiàng)挖掘算法。擴(kuò)展了流數(shù)據(jù)頻繁項(xiàng)的作用域。Lossy Weight算法不僅可用于傳統(tǒng)的基于計(jì)數(shù)的頻繁項(xiàng)挖掘，還可以挖掘出在整個(gè)流數(shù)據(jù)中所占權(quán)重比重大于門(mé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]．自動(dòng)化學(xué)報(bào)，2006，32(4)：594-602.
[3] 朱世武，嚴(yán)玉星．金融數(shù)據(jù)庫(kù)[M]．北京：清華大學(xué)出版社，2007：12-14.