ＳＷＦＰＭ：一種有效的數(shù)據(jù)流頻繁項(xiàng)挖掘算法
2009-01-01 00:00:00鄺祝芳陽(yáng)國(guó)貴辛動(dòng)軍
計(jì)算機(jī)應(yīng)用研究 2009年2期
（1.中南林業(yè)科技大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院， 長(zhǎng)沙 410004；2.國(guó)防科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)學(xué)院， 長(zhǎng)沙 410073)
摘 要：分析了數(shù)據(jù)流頻繁項(xiàng)挖掘算法EC的不足之處，如不能準(zhǔn)確地挖掘最近一段時(shí)間內(nèi)數(shù)據(jù)流的頻繁項(xiàng)。提出了一種頻繁項(xiàng)樣本特征復(fù)合四元組的數(shù)據(jù)結(jié)構(gòu)來保存樣本集合，在此基礎(chǔ)上，提出了一種基于滑動(dòng)窗口的數(shù)據(jù)流頻繁項(xiàng)挖掘算法——SWFPM。該算法能準(zhǔn)確地挖掘出該滑動(dòng)窗口中的頻繁項(xiàng)。實(shí)驗(yàn)數(shù)據(jù)采用IBM合成數(shù)據(jù)發(fā)生器產(chǎn)生的顧客購(gòu)物數(shù)據(jù)和1998年世界杯官方網(wǎng)站的訪問日志數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明，該算法具有很高的頻繁項(xiàng)挖掘準(zhǔn)確度、快速的數(shù)據(jù)處理能力。
關(guān)鍵詞：數(shù)據(jù)流；數(shù)據(jù)挖掘；頻繁項(xiàng)；滑動(dòng)窗口
中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A
文章編號(hào)：10013695(2009)02046604
SWFPM：efficient algorithm for mining frequent item over data streams
KUANG Zhufang1，YANG Guogui2，XIN Dongjun1
(1.College of Computer， Central South University of Forestry Technology， Changsha 410004， China;2.College of Computer， National University of Defense Technology， Changsha 410073， China)
Abstract:The disadvantage which the algorithm EC for mining frequent item over data streams was analyzed， such as the inaccurate of the frequent item mined in a recent period of time over the data stream.Put forward a data structure the frequent item sample in the form of 4 member group.Then，presented an algorithm SWFPM which based on sliding window for mining frequent item over data streams.The SWFPM algorithm can accurately mine the frequent item over the sliding window.The IBM synthesizes data generation which output customer shopping a data and the accessing record of the world cup official website data in 1998 are adopted as experiment data. The algorithm is of high preciseness for mining frequent item， and high perfor-mance for data processing.
Key words:data streams；data mining；frequent item；sliding window
0 引言
隨著計(jì)算機(jī)網(wǎng)絡(luò)和傳感器網(wǎng)絡(luò)技術(shù)的快速發(fā)展，數(shù)據(jù)流廣泛出現(xiàn)在眾多應(yīng)用領(lǐng)域。例如，傳感器網(wǎng)絡(luò)中的監(jiān)測(cè)信號(hào)、互聯(lián)網(wǎng)中傳遞的IP數(shù)據(jù)包、Web服務(wù)器上的用戶點(diǎn)擊記錄、電信公司的通話記錄等。與傳統(tǒng)的數(shù)據(jù)庫(kù)不同，數(shù)據(jù)流中的數(shù)據(jù)是按照時(shí)間遞增順序排列的無窮序列，無法全部保存下來，并且數(shù)據(jù)流上的查詢具有很強(qiáng)的實(shí)時(shí)性要求。因此，對(duì)在線數(shù)據(jù)分析和挖掘提出了新的挑戰(zhàn)。作為一種基礎(chǔ)且重要的數(shù)據(jù)挖掘手段——頻繁項(xiàng)挖掘在數(shù)據(jù)流環(huán)境下已成為當(dāng)前數(shù)據(jù)挖掘領(lǐng)域一個(gè)新的研究熱點(diǎn)[1]。近年來，對(duì)于數(shù)據(jù)流上頻繁項(xiàng)的挖掘，人們大多研究基于一遍掃描的頻繁項(xiàng)挖掘近似算法，并取得了一些研究成果[2~7]。這些研究成果按照所采用的技術(shù)來劃分，可以分為hash和抽樣兩大類。
在基于hash的方法中，Charikar等人[2]提出了Count Sketch方法；Cormode等人[3]提出了groupTest算法；Jin等人[4]提出了hCount算法。基于hash的方法均是(ε，δ)隨機(jī)近似算法。其中多數(shù)算法需要知道數(shù)據(jù)流的值域范圍，而數(shù)據(jù)流的值域通常是未知的。
抽樣是另一種挖掘數(shù)據(jù)流頻繁項(xiàng)的常用技術(shù)。Manku等人[5]提出了一種確定的ε近似算法——Lossy Counting算法。在同一篇文章中，他們還提出了一種(ε，δ)隨機(jī)近似算法——Sticky算法。Demaine等人[7]使用k個(gè)計(jì)數(shù)器，輸出了出現(xiàn)頻率超過1/(k+1)的頻繁項(xiàng)。但在數(shù)據(jù)流數(shù)據(jù)分布未知的情況下，他們提出的算法不能給出輸出結(jié)果頻率值的誤差范圍。文獻(xiàn)[6，8]中算法思想基本相似，文獻(xiàn)[8]中王偉平等人[8]提出了一種計(jì)算確定近似算法εEC算法。該算法動(dòng)態(tài)地維護(hù)1/ε個(gè)樣本，當(dāng)用戶查詢支持度超過s的頻繁項(xiàng)時(shí)，EC算法能夠給出近似查詢結(jié)果。但是，由于數(shù)據(jù)流中的數(shù)據(jù)分布隨著時(shí)間不斷地改變，頻繁項(xiàng)往往隨時(shí)間而不斷進(jìn)化；由于數(shù)據(jù)流分布的這種變化性，使得在舊的數(shù)據(jù)上建立的模型和新的數(shù)據(jù)分布不一致，需要頻繁地更新模型。在某一時(shí)間段內(nèi)出現(xiàn)的頻繁項(xiàng)集可能在下一個(gè)時(shí)間段內(nèi)變成非頻繁的項(xiàng)集。同樣在某一時(shí)間段非頻繁的項(xiàng)集在下一時(shí)間段可能變成頻繁的項(xiàng)集。如果只在數(shù)據(jù)結(jié)構(gòu)中存儲(chǔ)頻繁項(xiàng)集的計(jì)數(shù)，當(dāng)需要一些潛在的、稍后變?yōu)轭l繁項(xiàng)集的非頻繁項(xiàng)集的計(jì)數(shù)時(shí)，將得不到這些信息。在實(shí)際應(yīng)用中，人們也往往比較關(guān)心最近一段時(shí)間內(nèi)數(shù)據(jù)流中的頻繁項(xiàng)。滑動(dòng)窗口技術(shù)能夠針對(duì)窗口大小的數(shù)據(jù)流進(jìn)行挖掘，不會(huì)受到以前挖掘結(jié)果的影響，無須頻繁地更新模型。
1 EC算法簡(jiǎn)述
1.1 算法描述
EC算法使用樣本集合D保存1/ε個(gè)樣本，每個(gè)樣本為一個(gè)四元組(e，f，Ne，df)。其中:e是數(shù)據(jù)流中的一個(gè)數(shù)據(jù)項(xiàng)；f和df為兩個(gè)計(jì)數(shù)器；Ne為這個(gè)四元組加入到樣本集合D時(shí)，數(shù)據(jù)流到來的數(shù)據(jù)項(xiàng)個(gè)數(shù)。在任意時(shí)刻，令N表示當(dāng)前數(shù)據(jù)流中到來的數(shù)據(jù)項(xiàng)個(gè)數(shù)。EC算法由ECOUNT和FQuery兩部分組成。當(dāng)數(shù)據(jù)流來到新的數(shù)據(jù)項(xiàng)時(shí)，ECOUNT算法負(fù)責(zé)維護(hù)樣本集合D；當(dāng)用戶發(fā)出頻繁項(xiàng)查詢時(shí)，F(xiàn)Query算法負(fù)責(zé)輸出查詢結(jié)果。算法的詳細(xì)描述如下：
刪除D中所有f==0的四元組，加入新的(e，1，N，0）
ECOUNT算法工作如下:
初始時(shí)，樣本集合D為空。當(dāng)數(shù)據(jù)流來到一個(gè)數(shù)據(jù)項(xiàng)e時(shí)，若e已經(jīng)在D中，則將e對(duì)應(yīng)的f計(jì)數(shù)器加1。若e不在D中，但D不滿，則在D中加入一個(gè)新的四元組(e，1，N，0)；若e不在D中，并且樣本集合D已滿，則需要?jiǎng)h除D中的一個(gè)(或幾個(gè))四元組。ECOUNT不斷地將樣本集合D中每個(gè)四元組的f計(jì)數(shù)器同時(shí)減1，與此同時(shí)，將每個(gè)四元組的df計(jì)數(shù)器加1，直到集合D中有四元組的f計(jì)數(shù)器等于0為止。ECOUNT算法刪除D中所有f計(jì)數(shù)器為0的四元組，然后將新的四元組(e，1，N，0)加入到樣本集合D。在任意時(shí)刻，當(dāng)用戶查詢支持度超過s的頻繁項(xiàng)時(shí)，F(xiàn)Query算法輸出樣本集合D中所有f+df>(s-ε)N的四元組。其中，f+df的值為算法給出的數(shù)據(jù)項(xiàng)e的出現(xiàn)頻率。
1.2 EC算法存在的問題
假設(shè)有一數(shù)據(jù)流DS=(a，a，a，a，b，b，b，b，c)，長(zhǎng)度為N=9，給每一個(gè)數(shù)據(jù)項(xiàng)一個(gè)時(shí)標(biāo)，為Ti，設(shè)Ti為一個(gè)單位時(shí)間。為了說明問題的方便性，假設(shè)ε=0.5，則EC算法的樣本空間D中只能保存兩個(gè)樣本，算法處理過程如表1所示。
表1 EC算法處理數(shù)據(jù)流DS的過程
時(shí)標(biāo)數(shù)據(jù)流EC算法中樣本集合D時(shí)標(biāo)數(shù)據(jù)流EC算法中樣本集合D
由表1可知，在T9時(shí)刻，樣本集合D中只有項(xiàng)c。如果在T9時(shí)刻，用戶需要查詢數(shù)據(jù)流當(dāng)中最近8個(gè)單位時(shí)間最頻繁的項(xiàng)，或者用戶要查詢最近8個(gè)單位時(shí)間高于某一出現(xiàn)頻率的頻繁項(xiàng)，顯然EC算法無法給出正確的結(jié)果。在最近8個(gè)單位時(shí)間內(nèi)出現(xiàn)頻率最高的應(yīng)該是項(xiàng)b。
在實(shí)際當(dāng)中，應(yīng)該是一個(gè)很小的數(shù)，本例中假設(shè)ε=0.5只是說明問題的方便，實(shí)際上對(duì)于ε取一個(gè)很小的數(shù)，上面這種情況也是存在的，這說明EC算法存在的不足。因此本文提出了一種頻繁項(xiàng)樣本特征復(fù)合四元組的數(shù)據(jù)結(jié)構(gòu)來保存樣本集合，給每一數(shù)據(jù)項(xiàng)引入時(shí)標(biāo)，根據(jù)時(shí)標(biāo)動(dòng)態(tài)的維護(hù)樣本集合，在此基礎(chǔ)上提出了基于滑動(dòng)窗口的頻繁項(xiàng)挖掘算法SWFPM。
2 基于滑動(dòng)窗口的頻繁項(xiàng)挖掘
2.1 頻繁項(xiàng)樣本特征復(fù)合四元組
設(shè)數(shù)據(jù)流為一個(gè)不斷增長(zhǎng)的元組集合X1…Xj…Xn ，各元組的時(shí)標(biāo)為T1…Tj…Tn，且對(duì)任意i 為了挖掘滑動(dòng)窗口中元組的頻繁項(xiàng)，設(shè)計(jì)了一種近似結(jié)構(gòu)，稱為頻繁項(xiàng)樣本特征復(fù)合四元組，每一個(gè)復(fù)合四元組描述一個(gè)頻繁項(xiàng)的特征。頻繁項(xiàng)樣本特征復(fù)合四元組的定義如下： 定義1 一組具有時(shí)標(biāo)Ti1…Tij…Tin的元組集合Xi1…Xij…Xin，元素Xij的頻繁項(xiàng)樣本特征復(fù)合四元組為FP(Xij)=（Xij，f，N，(Tk1 …Tkf)）。其中:Xij表示元組序列中具有時(shí)標(biāo)Tij的元素；f表示Xij出現(xiàn)的次數(shù)；N表示當(dāng)前時(shí)刻，數(shù)據(jù)流到來的數(shù)據(jù)項(xiàng)的個(gè)數(shù)；Tk1…Tkf表示Xij在序列中出現(xiàn)f次的時(shí)標(biāo)；Tkp表示Xij第p次出現(xiàn)的時(shí)標(biāo)（i1＜kp＜in，1＜p＜f）。 定義2 設(shè)滑動(dòng)窗口的長(zhǎng)度為W，當(dāng)前時(shí)標(biāo)為T，如果時(shí)標(biāo)Γ＜T-W，則稱Γ為過期時(shí)標(biāo)。 定義3 如果頻繁項(xiàng)樣本特征復(fù)合四元組FP(X)的時(shí)標(biāo)序列中含有過期時(shí)標(biāo)，則稱頻繁項(xiàng)樣本X含有過期時(shí)標(biāo)。 2.2 算法描述 SWFPM算法使用樣本集合D保存頻繁項(xiàng)，每一個(gè)項(xiàng)為一個(gè)復(fù)合四元組FP(Xij)，滑動(dòng)窗口長(zhǎng)度為W。SWFPM算法由SWFPCount和SWFPQuery兩部分組成。當(dāng)數(shù)據(jù)流來到新的數(shù)據(jù)項(xiàng)時(shí)，SWFPCount算法負(fù)責(zé)維護(hù)滑動(dòng)窗口中頻繁項(xiàng)樣本集合；當(dāng)用戶發(fā)出頻繁項(xiàng)查詢時(shí)，SWFPQuery算法負(fù)責(zé)用戶的查詢，輸出頻繁項(xiàng)。 2.2.1 頻繁項(xiàng)樣本集合的維護(hù) SWFPCount算法負(fù)責(zé)維護(hù)滑動(dòng)窗口中頻繁項(xiàng)樣本集合，SWFPCount算法所做的工作是：初始時(shí)，樣本集合D為空。當(dāng)數(shù)據(jù)流來到一個(gè)具有時(shí)標(biāo)Tij的數(shù)據(jù)項(xiàng)Xij時(shí)，如果滑動(dòng)窗口滿，則搜索具有過期時(shí)標(biāo)的頻繁項(xiàng)樣本，并且刪除其過期時(shí)標(biāo)；若Xij在樣本集合D中，則頻繁項(xiàng)樣本Xij的計(jì)數(shù)器f加1，并且將時(shí)標(biāo)Tij加入到復(fù)合四元組的第四維時(shí)標(biāo)序列中；若Xij不在樣本集合D中，則f賦值為1，且將四元組（Xij，1，N，(Tij)）加入到樣本集合中。算法描述如下: 算法3 SWFPCount 輸入:樣本集合D，新到元組Xij。 輸出:樣本集合D。 count++; if 滑動(dòng)窗口滿{ while 樣本集合D中每一個(gè)復(fù)合四元組{ if該復(fù)合四元組包含過期時(shí)標(biāo){ 刪除該復(fù)合四元組中過期的時(shí)標(biāo) 該復(fù)合四元組f--;} } } if在D中{ f++;N=count; 當(dāng)前時(shí)標(biāo)加入到第四維時(shí)標(biāo)序列中； } else{ f=1; 將（Xij，1，N，(Tij)）加入到D中 } 2.2.2 頻繁項(xiàng)的生成 SWFPQuery算法負(fù)責(zé)用戶的查詢，輸出頻繁項(xiàng)。在任何時(shí)刻，當(dāng)用戶查詢支持度超過s的頻繁項(xiàng)時(shí)，SWFPQuery算法輸出樣本集合D中所有f≥(s-ε)W的四元組，s為用戶指定的支持度，ε為用戶指定的誤差。其中，f表示頻繁項(xiàng)在長(zhǎng)度為W的滑動(dòng)窗口中出現(xiàn)的頻率。算法描述如下: 算法4 SWFPQuery 輸入:樣本集合D，支持度s，誤差ε。 輸出:頻繁項(xiàng)。 while 樣本集合D中每一個(gè)復(fù)合四元組{ if該復(fù)合四元組的f≥(s-ε)W 輸出復(fù)合四元組（Xij，f，N，(Tk1…Tkp)） } 2.3 SWFPM算法處理實(shí)例 下面對(duì)數(shù)據(jù)流DS=(a，a，a，a，b，b，b，b，c)，長(zhǎng)度為N=9，利用SWFPM算法進(jìn)行處理，處理過程如表2所示。 表2 SWFPM算法處理數(shù)據(jù)流DS的過程 時(shí)標(biāo)數(shù)據(jù)流SWFP算法中樣本集合D(W=8) 由表2可知，在T9時(shí)刻，樣本集合D中含有項(xiàng)a，b，c。如果在T9時(shí)刻，不管用戶需要查詢數(shù)據(jù)流當(dāng)中最近8個(gè)單位時(shí)間最頻繁的項(xiàng)，還是要要查詢最近8個(gè)單位時(shí)間高于某一出現(xiàn)頻率的頻繁項(xiàng)，SWFPM算法都能給出正確的結(jié)果。 3 實(shí)驗(yàn)結(jié)果及分析 本文所有實(shí)驗(yàn)在一臺(tái)Pentium4 2.8 GHz、內(nèi)存為1 GB的PC上進(jìn)行，操作系統(tǒng)為Windows 2000專業(yè)版，算法用Visual C++實(shí)現(xiàn)。使用模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集對(duì)SWFPM算法的性能進(jìn)行了測(cè)試，比較的算法是EC算法。 3.1 模擬數(shù)據(jù)集 模擬數(shù)據(jù)集是由IBM合成數(shù)據(jù)發(fā)生器[9]產(chǎn)生的顧客購(gòu)物數(shù)據(jù)，實(shí)驗(yàn)采用的數(shù)據(jù)集是T7I4D5000K。其中:T表示數(shù)據(jù)集中事務(wù)的平均長(zhǎng)度；I表示潛在頻繁項(xiàng)集的平均長(zhǎng)度;D表示總的事務(wù)數(shù)目。數(shù)據(jù)集有1K個(gè)不同項(xiàng)目，數(shù)據(jù)發(fā)生器的其他參數(shù)采用缺省值。 實(shí)驗(yàn)分為兩部分內(nèi)容:實(shí)驗(yàn)1是比較SWFPM算法與EC算法挖掘頻繁項(xiàng)的準(zhǔn)確度；實(shí)驗(yàn)2是比較SWFPM算法與EC算法的處理時(shí)間。 在模擬數(shù)據(jù)實(shí)驗(yàn)1中，針對(duì)數(shù)據(jù)集T7I4D5000K，首先，觀察當(dāng)支持度設(shè)置為s=0.2，滑動(dòng)窗口的長(zhǎng)度設(shè)置為W=1000和W=5 000，隨著誤差參數(shù)ε的變化，比較SWFPM算法與EC算法的準(zhǔn)確度，如圖1所示。其次，觀察當(dāng)支持度設(shè)置為s=0.2，誤差參數(shù)設(shè)置為ε=0.1%，隨著滑動(dòng)窗口長(zhǎng)度W的變化，比較SWFPM算法與EC算法挖掘頻繁項(xiàng)的準(zhǔn)確度，如圖2所示。從實(shí)驗(yàn)結(jié)果中分析得知，EC算法挖掘頻繁項(xiàng)的準(zhǔn)確度隨著誤差參數(shù)ε的變化而不同，誤差參數(shù)ε越大，EC算法挖掘頻繁項(xiàng)的準(zhǔn)確度越差，這是因?yàn)檎`差參數(shù)ε的大小直接決定了EC算法樣本空間的大小，ε越大，EC算法的樣本空間越小，能保存的樣本越小，則挖掘效果越差。然而，無論滑動(dòng)窗口長(zhǎng)度誤差參數(shù)如何變化，SWFPM算法挖掘出當(dāng)前窗口中的頻繁項(xiàng)的正確性恒為1，這是因?yàn)镾WFPM算法保存了每一個(gè)數(shù)據(jù)項(xiàng)的時(shí)標(biāo)，根據(jù)滑動(dòng)窗口的長(zhǎng)度，及時(shí)刪除過期時(shí)標(biāo)，保證了算法能夠準(zhǔn)確地挖掘出當(dāng)前窗口中的頻繁項(xiàng)。 在模擬數(shù)據(jù)實(shí)驗(yàn)2中，針對(duì)數(shù)據(jù)集T7I4D5000K，支持度設(shè)置為s=0.2，滑動(dòng)窗口長(zhǎng)度設(shè)置為W=1 000，隨著誤差參數(shù)ε的變化，比較SWFPM算法與EC算法的時(shí)間開銷，如圖3所示。從實(shí)驗(yàn)結(jié)果中可以分析得知，EC算法的處理時(shí)間隨著誤差參數(shù)ε的越大，處理時(shí)間越小，并且相同的誤差參數(shù)ε，滑動(dòng)窗口增大，處理時(shí)間也相應(yīng)地增大。然而，誤差參數(shù)ε改變，SWFPM算法的處理時(shí)間基本保持不變，這是因?yàn)镾WFPM的處理時(shí)間與誤差參數(shù)ε沒關(guān)系，當(dāng)滑動(dòng)窗口增大時(shí)，SWFPM的處理時(shí)間相應(yīng)地有一點(diǎn)增加。 3.2 真實(shí)數(shù)據(jù)集 在真實(shí)數(shù)據(jù)實(shí)驗(yàn)中，使用1998年世界杯官方網(wǎng)站的訪問日志作為實(shí)驗(yàn)數(shù)據(jù)[10]。這份日志記錄了在1998年世界杯比賽期間，世界杯官方網(wǎng)站的所有訪問請(qǐng)求(共計(jì)1 352 804 107個(gè))。每個(gè)訪問請(qǐng)求包括訪問時(shí)間、源IP地址、訪問頁(yè)面的ID等8個(gè)屬性。本文提取了其中的訪問頁(yè)面ID作為實(shí)驗(yàn)數(shù)據(jù)。通過挖掘訪問頁(yè)面的頻繁項(xiàng)，可以了解世界杯期間某段時(shí)間哪些頁(yè)面是最熱的。 真實(shí)實(shí)驗(yàn)包含兩部分，即實(shí)驗(yàn)1是比較SWFPM算法與EC算法的處理時(shí)間和實(shí)驗(yàn)2是比較SWFPM算法與EC算法的內(nèi)存開銷。在實(shí)驗(yàn)中，提取200萬(wàn)個(gè)訪問頁(yè)面ID作為實(shí)驗(yàn)數(shù)據(jù)。 在真實(shí)數(shù)據(jù)實(shí)驗(yàn)1中，比較EC算法與SWFPM算法的處理時(shí)間，滑動(dòng)窗口長(zhǎng)度設(shè)置為W=1 000，誤差參數(shù)分別設(shè)置為0.1%和0.2%并進(jìn)行比較如圖4所示。通過對(duì)實(shí)驗(yàn)結(jié)果分析可知，SWFPM算法的處理時(shí)間低于EC算法的處理時(shí)間，并且處理時(shí)間與誤差參數(shù)ε沒關(guān)系。 在真實(shí)數(shù)據(jù)實(shí)驗(yàn)2中，比較EC算法與SWFPM算法的內(nèi)存開銷，滑動(dòng)窗口長(zhǎng)度設(shè)置為W=1 000，誤差參數(shù)分別設(shè)置為0.1%和0.05%進(jìn)行比較如圖5所示。通過對(duì)實(shí)驗(yàn)結(jié)果分析可知，EC算法的內(nèi)存開銷只與ε有關(guān)，而SWFPM算法的處于一種波動(dòng)狀態(tài)。 4 結(jié)束語(yǔ) 本文提出了一種頻繁項(xiàng)樣本特征復(fù)合四元組的數(shù)據(jù)結(jié)構(gòu)來保存樣本集合，給每一數(shù)據(jù)項(xiàng)引入時(shí)標(biāo)，根據(jù)時(shí)標(biāo)動(dòng)態(tài)地維護(hù)樣本集合，在此基礎(chǔ)上提出了基于滑動(dòng)窗口的頻繁項(xiàng)挖掘算法SWFPM。但實(shí)現(xiàn)滑動(dòng)窗口的長(zhǎng)度W可調(diào)還有待進(jìn)一步研究。 參考文獻(xiàn)： ［1］ BABCOCK A K，BABU S，DATAR M.Model and issues in data stream systems[C]//Proc of the 21st ACM SIGACTSIGMODSIGART Symp on Principles of Database Systems. Madison:ACM Press，2002:116. [2]CHARIKAR M，CHEN K，F(xiàn)ARACHCOLTON M.Finding frequent items in data streams[C]//WIDMAYER P，RUIZ F T，BUENO R M，et al.Proc of the Int’l Colloquium on Automata， Languages and Programming.Malaga:SpringerVerlag，2002:693703. [3]CORMODE G，MUTHUKRISHNAN S.What’s hot and what’s not:tracking most frequent items dynamically[C]//HALEVY A Y，IVES Z G，DOAN A H，et al.Proc of the 22nd ACM SIGACTSIGMODSIGART Symp on Principles of Database Systems. San Diego: ACM Press，2003:296306. [4]JIN C，QIAN W，SHA C，et al.Dynamically maintaining frequent items over a data stream[C]//CARBONELL J.Proc of the 2003 ACM CIKM Int’l Conf on Information and Knowledge Management. New Orleans: ACM Press，2003:287294. [5]MANKU G S，MOTWANI R.Approximate frequency counts over data streams[C]//BERNSTEIN P，IOANNIDIS Y，RAMAKRISHNAN R，et al.Proc of the 28th Int’l Conf on Very Large Data Bases. Hong Kong: Morgan Kaufmann Publishers，2002:346357. [6]KARP R，PAPADIMITRIOU C，SHENKER S.A simple algorithm for finding frequent elements in sets and bags[J].Trans on Database Systems，2003，28(1):5155. [7]DEMAINE E， LPEZORTIZ A，MUNRO J I.Frequency estimation of Internet packet streams with limited space[C]//MHRING R H，RAMAN R，et al.Proc of the 10th Algorithms ESA 2002，Annual European Symp. Rome: SpringerVerlag，2002:348360. [8]王偉平，李建中，張冬冬，等. 一種有效的挖掘數(shù)據(jù)流近似頻繁項(xiàng)算法[J].軟件學(xué)報(bào)，2007，18(4):884892. [9][EB/OL].http://www.almaden.ibm.com/cs/projects/iis/hdb/Projects/data_mining/datasets/syndata.html#instructions. [10]1998 World Cup Web Site Access Logs[EB/OL].(2004).http://ita.ee.lbl.gov/html/contrib/WorldCup.html.
