楊 立

（運(yùn)城學(xué)院 公共計(jì)算機(jī)教學(xué)部，山西 運(yùn)城044000）

基于計(jì)數(shù)的頻繁項(xiàng)挖掘算法適用于每個(gè)數(shù)據(jù)元組所含知識(shí)相等或近似的情況，例如用戶在網(wǎng)頁(yè)上的點(diǎn)擊流，搜索引擎的關(guān)鍵詞流、路由器上的IP包流等情況。但在更多的情況下，每個(gè)事務(wù)代表的知識(shí)是不相等的。如電信系統(tǒng)中的通話記錄，每個(gè)用戶的電話用時(shí)是不相同的；在證券交易中心，每筆交易的金額也是不同的。許多小客戶的事務(wù)數(shù)多，但每筆事務(wù)的權(quán)值很小；重要的大客戶事務(wù)數(shù)雖少，但每筆事務(wù)的權(quán)值很大。如果此時(shí)用原有的頻繁項(xiàng)挖掘算法，將不能很好地體現(xiàn)那些事務(wù)數(shù)少但重要性高的客戶。而采用新的基于權(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)重的混合查詢。

1 Lossy Counting算法

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

2 Lossy Weight算法

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

新算法同樣滿足實(shí)時(shí)性的要求。在任意時(shí)間內(nèi)，用戶都可以提交查詢，算法的結(jié)果滿足以下的要求：(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.1 Lossy Weight算法實(shí)現(xiàn)

新算法有如下的定義：用戶必須明確地指定門(mén)檻參數(shù)s和誤差參數(shù)ε，并且定義流數(shù)據(jù)當(dāng)前大小為N。

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

當(dāng)一個(gè)新元素e到達(dá)時(shí)，將e的權(quán)值Wi加入計(jì)數(shù)器V，之后對(duì)D進(jìn)行更新操作。首先查找D中是否存在e。如果存在，將e的權(quán)值加入W。否則新建成員(e，Wi，εVb-1)。

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

2.2 新算法的優(yōu)勢(shì)

3 Lossy Weight算法的實(shí)驗(yàn)分析

3.1 Lossy Weight算法的特性實(shí)驗(yàn)

本文采用國(guó)泰君安CSMAR(China Stock Market Accounting 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ù)。

[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]潘云鶴，王金龍，徐從富.數(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.