數(shù)據(jù)流上頻繁項(xiàng)挖掘方法研究畢業(yè)論文

1、<p>　　畢 業(yè) 設(shè) 計(jì)（論 文）</p><p>　　題 目： 數(shù)據(jù)流上頻繁項(xiàng)挖掘方法研究 </p><p>　　專 業(yè)： 信息安全 </p><p>　　學(xué)生姓名： </p><p>　　班級(jí)學(xué)號(hào)：

2、 </p><p>　　指導(dǎo)教師： </p><p>　　指導(dǎo)單位： 信息安全系 </p><p>　　日期： 2008年 3 月 21 日至 2008 年 6 月10日</p><p><b>　　摘 要&

3、lt;/b></p><p>　　發(fā)現(xiàn)數(shù)據(jù)流中的頻繁項(xiàng)是數(shù)據(jù)流挖掘中最基本的問(wèn)題之一。數(shù)據(jù)流的無(wú)限性和流動(dòng)性使得傳統(tǒng)的頻繁模式挖掘算法難以適應(yīng)。針對(duì)數(shù)據(jù)流的特點(diǎn)，論文對(duì)數(shù)據(jù)流處理技術(shù)和數(shù)據(jù)流挖掘中的關(guān)鍵問(wèn)題進(jìn)行了研究和總結(jié)，并對(duì)一些經(jīng)典的頻繁項(xiàng)挖掘算法進(jìn)行了介紹。在借鑒FP-growth算法的基礎(chǔ)上，采用了一種較新的數(shù)據(jù)流頻繁模式挖掘的算法：FP-stream算法。算法受能夠進(jìn)行有效頻繁項(xiàng)挖掘的數(shù)據(jù)結(jié)構(gòu)FP

4、-tree的啟發(fā)，創(chuàng)造了一個(gè)可以在數(shù)據(jù)流上進(jìn)行有效挖掘的數(shù)據(jù)結(jié)構(gòu)FP-stream。一個(gè)FP-stream結(jié)構(gòu)包含(a)一個(gè)可捕捉頻繁項(xiàng)和次頻繁項(xiàng)的內(nèi)存中的頻繁樹(shù)，(b)每一個(gè)頻繁項(xiàng)都有的傾斜時(shí)間窗口表。構(gòu)建、更新和維護(hù)該結(jié)構(gòu)實(shí)現(xiàn)了在數(shù)據(jù)流上的挖掘。分析和實(shí)驗(yàn)證明了其性能。最后對(duì)未來(lái)的研究方向進(jìn)行了展望。</p><p>　　關(guān)鍵詞: 數(shù)據(jù)流； 頻繁項(xiàng)； 流數(shù)據(jù)挖掘； FP-stream算法； 傾斜時(shí)間窗口；&l

5、t;/p><p><b>　　ABSTRACT</b></p><p>　　Finding frequent items is one of the most basic problems in the data stream. The limitless and mobility of data streams make the traditional frequent

6、-pattern algorithm difficult to extend to data streams. According to the character of data streams, a new FP-stream algorithm for mining frequent items for data streams is proposed. Inspired by the fact that the FP-tree

7、provides an effective data structure for frequent pattern mining, we develop FP-stream, an effective FP-tree-based model for mining</p><p>　　Key words data streams; frequent items; stream data mining; FP-st

8、ream algorithm; tilted-time window</p><p><b>　　目 錄</b></p><p><b>　　第一章 緒論1</b></p><p>　　1.1課題背景和研究現(xiàn)狀1</p><p>　　1.2 課題內(nèi)容3</p><p&g

9、t;　　第二章 數(shù)據(jù)流和數(shù)據(jù)流挖掘4</p><p><b>　　2.1 數(shù)據(jù)流4</b></p><p>　　2.2 數(shù)據(jù)流挖掘算法和特點(diǎn)5</p><p>　　2.3 數(shù)據(jù)流挖掘的關(guān)鍵問(wèn)題6</p><p>　　2.4 本章小結(jié)8</p><p>　　第三章 頻繁項(xiàng)挖掘及相關(guān)算法

10、9</p><p>　　3.1 頻繁模式概念9</p><p>　　3.2 挖掘方法10</p><p>　　3.3 有關(guān)算法12</p><p>　　3.4 本章小結(jié)13</p><p>　　第四章 數(shù)據(jù)流上頻繁項(xiàng)挖掘算法14</p><p>　　4.1 改進(jìn)的FP-stream算

11、法關(guān)鍵點(diǎn)14</p><p>　　4.1.1頭表fList的設(shè)計(jì)14</p><p>　　4.1.2 傾斜時(shí)間窗口維護(hù)策略15</p><p>　　4.2 改進(jìn)的FP-stream算法設(shè)計(jì)18</p><p>　　4.2.1 FP-stream的模式樹(shù)結(jié)構(gòu)18</p><p>　　4.2.2 FP-strea

12、m結(jié)構(gòu)20</p><p>　　4.3 對(duì)FP-stream的更新和維護(hù)22</p><p>　　第五章 改進(jìn)的FP-stream算法實(shí)現(xiàn)23</p><p>　　5.1 FP-tree的構(gòu)建23</p><p>　　5.2 FP-tree的更新25</p><p>　　5.3 分析和評(píng)價(jià)29</p

13、><p>　　5.4.1 數(shù)據(jù)處理29</p><p>　　5.4.2 結(jié)果分析和性能分析29</p><p>　　5.4.3 應(yīng)用展望31</p><p><b>　　結(jié)束語(yǔ)32</b></p><p><b>　　致 謝33</b></p><

14、p><b>　　參考文獻(xiàn)34</b></p><p><b>　　第一章 緒論</b></p><p>　　隨著信息技術(shù)的高速發(fā)展，海量數(shù)據(jù)的積累成指數(shù)級(jí)增長(zhǎng)，人類面臨數(shù)據(jù)海洋、知識(shí)匾乏的難題。數(shù)據(jù)挖掘技術(shù)旨在從大量數(shù)據(jù)中提取有用的知識(shí)，幫助人們進(jìn)行科學(xué)分析和決策。經(jīng)過(guò)近十幾年的發(fā)展，很多有用的挖掘算法和模型相繼被提出，數(shù)據(jù)挖掘技術(shù)已經(jīng)

15、被應(yīng)用到多個(gè)相關(guān)領(lǐng)域。然而，近年來(lái)，產(chǎn)生了一種新的數(shù)據(jù)形式，如傳感器網(wǎng)絡(luò)、電子商務(wù)記錄、網(wǎng)絡(luò)監(jiān)控日記。這些數(shù)據(jù)源源不斷的到來(lái)，并且是快速的、無(wú)限的。這種數(shù)據(jù)流挖掘算法只能對(duì)數(shù)據(jù)進(jìn)行一次順序掃描，有限的內(nèi)存也無(wú)法處理高速大量的數(shù)據(jù)。傳統(tǒng)的數(shù)據(jù)挖掘算法不能適用于這種數(shù)據(jù)流模型，這促使人們?cè)O(shè)計(jì)新的算法來(lái)適應(yīng)數(shù)據(jù)流挖掘。</p><p>　　1.1課題背景和研究現(xiàn)狀</p><p>　　數(shù)據(jù)挖掘技

16、術(shù)出現(xiàn)于20世紀(jì)80年代后期，90年代有了突飛猛進(jìn)的發(fā)展。數(shù)據(jù)挖掘技術(shù)是人們長(zhǎng)期對(duì)數(shù)據(jù)庫(kù)技術(shù)進(jìn)行研究和開(kāi)發(fā)的結(jié)果。起初各種商業(yè)數(shù)據(jù)是存儲(chǔ)在計(jì)算機(jī)的數(shù)據(jù)庫(kù)中的，然后發(fā)展到可對(duì)數(shù)據(jù)庫(kù)進(jìn)行查詢和訪問(wèn)，進(jìn)而發(fā)展到對(duì)數(shù)據(jù)庫(kù)的即時(shí)遍歷。數(shù)據(jù)挖掘使數(shù)據(jù)庫(kù)技術(shù)進(jìn)入了一個(gè)更高級(jí)的階段，它不僅能對(duì)過(guò)去的數(shù)據(jù)進(jìn)行查詢和遍歷，并且能夠找出過(guò)去數(shù)據(jù)之間的潛在聯(lián)系，從而促進(jìn)信息的傳遞?，F(xiàn)在數(shù)據(jù)挖掘技術(shù)在商業(yè)應(yīng)用中己經(jīng)可以馬上投入使用，因?yàn)閷?duì)這種技術(shù)進(jìn)行支持的三種基

17、礎(chǔ)技術(shù)已經(jīng)發(fā)展成熟，分別是:</p><p><b>　　海量數(shù)據(jù)搜集；</b></p><p>　　強(qiáng)大的多處理器計(jì)算機(jī)；</p><p><b>　　數(shù)據(jù)挖掘算法。</b></p><p>　　數(shù)據(jù)挖掘是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中，提取隱含在其中的人們事先不知道的、但又是

18、潛在有用的信息和知識(shí)的過(guò)程[1]。與數(shù)據(jù)挖掘相近的同義詞有數(shù)據(jù)融合、數(shù)據(jù)分析和決策支持等。這個(gè)定義包含好幾層含義:數(shù)據(jù)源必須是真實(shí)的、大量的、含噪聲的;發(fā)現(xiàn)的是用戶感興趣的知識(shí);發(fā)現(xiàn)的知識(shí)要可接受、可理解、可運(yùn)用;知識(shí)從廣義上理解為數(shù)據(jù)和信息。但人們更把概念、規(guī)則、模式、規(guī)律和約束等看作知識(shí)。原始數(shù)據(jù)可以是結(jié)構(gòu)化的，如關(guān)系數(shù)據(jù)庫(kù)中的數(shù)據(jù)；也可以是半結(jié)構(gòu)化的，如文本、圖形和圖像數(shù)據(jù)；甚至是分布在網(wǎng)絡(luò)上的異構(gòu)型數(shù)據(jù)。發(fā)現(xiàn)的知識(shí)的方法可以是數(shù)

19、學(xué)的，也可以是非數(shù)學(xué)的；可以是演繹的，也可以是歸納的。發(fā)現(xiàn)的知識(shí)可以被用于信息管理，查詢優(yōu)化，決策支持和過(guò)程控制等，還可以用于數(shù)據(jù)自身的維護(hù)。因此，數(shù)據(jù)挖掘是一門(mén)交叉學(xué)科，它把人們對(duì)數(shù)據(jù)的應(yīng)用從低層次的簡(jiǎn)單查詢，提升到從數(shù)據(jù)中挖掘知識(shí)，提供決策支持。在這種需求牽引下，匯聚了不同領(lǐng)域的研究者，尤其是數(shù)據(jù)庫(kù)技術(shù)、人工智能技術(shù)、數(shù)理統(tǒng)計(jì)、可視化技術(shù)、并行計(jì)算等方面的學(xué)者和工程技術(shù)人員，投身到數(shù)據(jù)挖掘這一新興的研究領(lǐng)域，形成新的技術(shù)熱點(diǎn)。<

20、;/p><p>　　盡管傳統(tǒng)數(shù)據(jù)庫(kù)獲得了巨大的成功，但是在20世紀(jì)末，一種新的應(yīng)用模型卻對(duì)它提出了有力的挑戰(zhàn)。這種名為數(shù)據(jù)流(data stream)的應(yīng)用模型廣泛出現(xiàn)在眾多領(lǐng)域,其中也包括安全領(lǐng)域。數(shù)據(jù)流的處理技術(shù)最早就是出現(xiàn)在網(wǎng)絡(luò)監(jiān)控方面，人們用它來(lái)做網(wǎng)絡(luò)質(zhì)量分析，流量統(tǒng)計(jì)等。</p><p>　　數(shù)據(jù)庫(kù)技術(shù)的不斷發(fā)展及數(shù)據(jù)庫(kù)管理系統(tǒng)的廣泛應(yīng)用，數(shù)據(jù)庫(kù)中存儲(chǔ)的數(shù)據(jù)量急劇增大，在大量的數(shù)據(jù)背

21、后隱藏著許多重要的信息，如果能把這些信息從數(shù)據(jù)庫(kù)中抽取出來(lái)，將為公司創(chuàng)造很多潛在的利潤(rùn)，數(shù)據(jù)挖掘概念就是從這樣的商業(yè)角度提出來(lái)的。數(shù)據(jù)挖掘(Data Mining)是指從大型數(shù)據(jù)庫(kù)或數(shù)據(jù)倉(cāng)庫(kù)中提取隱含的、未知的、非平凡的及有潛在應(yīng)用價(jià)值的信息或模式，它是數(shù)據(jù)庫(kù)研究中的一個(gè)很有應(yīng)用價(jià)值的領(lǐng)域，最近十幾年出現(xiàn)了大量的數(shù)據(jù)挖掘方法，比如聚類，分類，關(guān)聯(lián)分析等。</p><p>　　隨著數(shù)據(jù)流管理系統(tǒng)和數(shù)據(jù)流處理技術(shù)研究

22、和發(fā)展，人們開(kāi)始考慮能像以前的數(shù)據(jù)庫(kù)一樣，從數(shù)據(jù)流中發(fā)現(xiàn)知識(shí)，于是數(shù)據(jù)流挖掘算法隨之出現(xiàn)。數(shù)據(jù)流挖掘類似數(shù)據(jù)挖掘，都是從大量的數(shù)據(jù)中獲取有用的知識(shí)，不過(guò)挖掘?qū)ο笫菙?shù)據(jù)流。數(shù)據(jù)流管理系統(tǒng)、數(shù)據(jù)流處理技術(shù)和傳統(tǒng)的數(shù)據(jù)挖掘，為數(shù)據(jù)流挖掘的研究提供了一系列方法。傳統(tǒng)的數(shù)據(jù)挖掘問(wèn)題也被引入到數(shù)據(jù)流挖掘領(lǐng)域，比如聚類，分類，頻繁模式挖掘等。</p><p>　　數(shù)據(jù)流還是一門(mén)較新的領(lǐng)域，對(duì)于數(shù)據(jù)流的查詢和分析以及數(shù)據(jù)流挖掘有

23、許多的發(fā)展空間和研究方向。目前研究比較多的是:</p><p>　　數(shù)據(jù)流處理的模型和語(yǔ)言；</p><p>　　處理類似于普通數(shù)據(jù)庫(kù)查詢的流查詢；</p><p>　　數(shù)據(jù)流的采樣和近似技術(shù)；</p><p>　　數(shù)據(jù)流處理時(shí)對(duì)內(nèi)存的管理；</p><p>　　數(shù)據(jù)流處理與數(shù)據(jù)庫(kù)的結(jié)合；</p><

24、;p>　　對(duì)高速數(shù)據(jù)流的挖掘算法；</p><p>　　新型的數(shù)據(jù)流處理的應(yīng)用。</p><p>　　這些都是一些重要的和活躍的研究領(lǐng)域，國(guó)外許多大學(xué)和研究機(jī)構(gòu)都在對(duì)數(shù)據(jù)流做進(jìn)一步的探討。國(guó)內(nèi)的數(shù)據(jù)流的研究還不是很多，但己有一些大學(xué)、研究院開(kāi)始了數(shù)據(jù)流的相關(guān)研究，并己有一些相關(guān)的論文出現(xiàn)于國(guó)內(nèi)刊物上。最近幾 年，數(shù)據(jù)流上的頻繁模式挖掘被廣泛的進(jìn)行研究。Manku提出的Lossy co

25、unting算法[2]，通過(guò)對(duì)當(dāng)前整個(gè)數(shù)據(jù)流的事務(wù)進(jìn)行近似計(jì)數(shù)挖掘頻繁項(xiàng)。Charikar 提出了一次掃描數(shù)據(jù)流的算法返回當(dāng)前最頻繁項(xiàng)。Chang提出了estDec算法，通過(guò)定義按時(shí)間指數(shù)進(jìn)行衰減的策略挖掘最近的頻繁項(xiàng)集。Giannella和Jiawei Han 等提出了在任意時(shí)間間隔上挖掘頻繁項(xiàng)集的近似算法[3.4]，該算法采用在內(nèi)存中保存頻繁項(xiàng)的FP-stream數(shù)據(jù)結(jié)構(gòu)，通過(guò)把數(shù)據(jù)流分成等長(zhǎng)的數(shù)據(jù)段，對(duì)數(shù)據(jù)流進(jìn)行批量處理，然后把歷

26、史數(shù)據(jù)保存在對(duì)數(shù)傾斜時(shí)間窗口中，能夠?qū)崿F(xiàn)對(duì)任意時(shí)間段的數(shù)據(jù)進(jìn)行查詢。由于是對(duì)數(shù)據(jù)流進(jìn)行分段處理，不能實(shí)時(shí)的對(duì)數(shù)據(jù)流進(jìn)行處理，處理時(shí)間粒度較粗。Huafu Li等提出DSM-MFI算法，用于挖掘最近的最大頻繁項(xiàng)集，通過(guò)SFI-forest數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)當(dāng)前的概要頻繁項(xiàng)集。頻繁模式</p><p><b>　　1.2 課題內(nèi)容</b></p><p>　　基于數(shù)據(jù)流模型的挖

27、掘算法，必須在有限的內(nèi)存空間內(nèi)完成，數(shù)據(jù)流高速到達(dá)的特性要求挖掘算法盡量采用增量更新的方法。本課題研究了一種有效的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)流的概要信息，基于滑動(dòng)窗口實(shí)現(xiàn)挖掘算法的增量更新，主要研究?jī)?nèi)容包括以下幾個(gè)方面。</p><p>　　第一: 分析數(shù)據(jù)流的特點(diǎn)，對(duì)比傳統(tǒng)數(shù)據(jù)挖掘與數(shù)據(jù)流挖掘的不同，理解數(shù)據(jù)流模型。</p><p>　　第二: 研究存儲(chǔ)數(shù)據(jù)流的概要信息的數(shù)據(jù)結(jié)構(gòu)，F(xiàn)P-tree是

28、目前比較有效的存儲(chǔ)結(jié)構(gòu)，在此基礎(chǔ)上提出的FP-stream結(jié)構(gòu)，類似于前綴樹(shù)，并且通過(guò)時(shí)間窗口保存歷史頻繁計(jì)數(shù)。</p><p>　　第三: 在用FP-stream結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)流概要信息的基礎(chǔ)上，研究數(shù)據(jù)流上頻繁項(xiàng)挖掘算法FP-stream算法，以指數(shù)直方圖形式處理高速、大量的數(shù)據(jù)流，更好地適應(yīng)數(shù)據(jù)流挖掘的特點(diǎn)。</p><p>　　第四: 通過(guò)進(jìn)行大量的實(shí)驗(yàn)，結(jié)合理論定理的說(shuō)明，在時(shí)間復(fù)

29、雜度和空間復(fù)雜度上證明算法的有效性。</p><p>　　第二章 數(shù)據(jù)流和數(shù)據(jù)流挖掘</p><p><b>　　2.1 數(shù)據(jù)流</b></p><p>　　傳統(tǒng)的數(shù)據(jù)庫(kù)存儲(chǔ)的是靜態(tài)的關(guān)系型數(shù)據(jù)記錄的集合，它們具有限定的大小、可控制的操作、詳細(xì)定義的結(jié)構(gòu)，同時(shí)這些數(shù)據(jù)具有持久性。傳統(tǒng)數(shù)據(jù)庫(kù)中的計(jì)算具有較高時(shí)間復(fù)雜度和空間復(fù)雜度，其查詢處理為單

30、次查詢，查詢計(jì)劃為靜態(tài)的，且最終生成確定的查詢結(jié)果。另外，傳統(tǒng)數(shù)據(jù)基本沒(méi)有時(shí)間的概念。但許多當(dāng)前的及今后的應(yīng)用，要求能對(duì)不斷快速變化的數(shù)據(jù)流提供在線分析支持。當(dāng)網(wǎng)絡(luò)控制器、電信數(shù)據(jù)管理、網(wǎng)絡(luò)個(gè)性化、生產(chǎn)、傳感器網(wǎng)絡(luò)等應(yīng)用出現(xiàn)之后，數(shù)據(jù)大都是連續(xù)的數(shù)據(jù)流，并且與過(guò)去的那種單次查詢相反，用戶需要長(zhǎng)期的、連續(xù)的查詢，這就對(duì)數(shù)據(jù)庫(kù)系統(tǒng)以及數(shù)據(jù)的處理算法等提出了新的挑戰(zhàn)。</p><p>　　數(shù)據(jù)流是連續(xù)的、無(wú)限的、快速的

31、、隨時(shí)間變化的數(shù)據(jù)元素的流。與傳統(tǒng)的數(shù)據(jù)相比，流式數(shù)據(jù)具有許多特點(diǎn):它是大量的、連續(xù)的、無(wú)限的數(shù)據(jù)；變化很快，并且要求快速的即時(shí)響應(yīng)；數(shù)據(jù)流管理中隨機(jī)存取采用的是一種代價(jià)昂貴的單一線性的掃描算法；僅僅存儲(chǔ)到目前為止的現(xiàn)有數(shù)據(jù)。</p><p>　　2.1.1 數(shù)據(jù)流的特點(diǎn)</p><p>　　數(shù)據(jù)流不同于傳統(tǒng)的數(shù)據(jù)倉(cāng)庫(kù)，數(shù)據(jù)流的到來(lái)往往是高速的，并且數(shù)據(jù)量是無(wú)窮的，通過(guò)對(duì)比傳統(tǒng)關(guān)系型數(shù)據(jù)，

32、數(shù)據(jù)流具有以下幾個(gè)特點(diǎn)。</p><p>　　(1) 數(shù)據(jù)記錄是動(dòng)態(tài)的，即數(shù)據(jù)不是靜態(tài)的，需要?jiǎng)討B(tài)的進(jìn)行更新并存</p><p>　　儲(chǔ)在管理系統(tǒng)中以備使用。</p><p>　　(2) 數(shù)據(jù)流管理系統(tǒng)DSMS無(wú)法知道下個(gè)到達(dá)的數(shù)據(jù)是什么，甚至在同一個(gè)數(shù)據(jù)流中，DSMS也無(wú)法控制待處理的數(shù)據(jù)記錄的順序。</p><p>　　(3) 本質(zhì)上，數(shù)

33、據(jù)流的長(zhǎng)度是無(wú)限的，查詢處理的數(shù)據(jù)流是高速的、連續(xù)的、隨時(shí)間變化的。</p><p>　　(4) 數(shù)據(jù)流中的記錄一旦被處理，可能拋棄，也可能歸檔；無(wú)論是哪一種處理方式，很難重新查詢。</p><p>　　(5) 在數(shù)據(jù)流處理中，可能會(huì)結(jié)合DBMS。例如，某一次數(shù)據(jù)查詢中，可能需要用到關(guān)系數(shù)據(jù)庫(kù)中的數(shù)據(jù)，或者，連接操作，可能把數(shù)據(jù)流與關(guān)系表連接，以獲得所需的數(shù)據(jù)流。</p>&

34、lt;p>　　2.1.2 數(shù)據(jù)流模型的特點(diǎn)</p><p>　　數(shù)據(jù)流的這些特點(diǎn)要求一個(gè)完整、優(yōu)秀的數(shù)據(jù)流處理系統(tǒng)必須具有以下特點(diǎn):</p><p>　　1. 實(shí)時(shí)接受到達(dá)的數(shù)據(jù)，在不作存儲(chǔ)的情況下立即處理，處理速度滿足輸入數(shù)據(jù)的速度要求。</p><p>　　2. 由于數(shù)據(jù)流無(wú)邊界，所以其處理結(jié)果的反饋也必須是實(shí)時(shí)的:結(jié)果即時(shí)更新、即時(shí)可查。</p

35、><p>　　其處理算法必須滿足一次掃描的要求，即不再對(duì)數(shù)據(jù)做重復(fù)掃描和計(jì)算。</p><p><b>　　圖 2-1</b></p><p>　　2.2 數(shù)據(jù)流挖掘算法和特點(diǎn)</p><p>　　數(shù)據(jù)流具有以下幾種性質(zhì):數(shù)據(jù)快速持續(xù)地到達(dá)、數(shù)據(jù)海量、數(shù)據(jù)到達(dá)有序。在傳統(tǒng)的數(shù)據(jù)挖掘過(guò)程中一個(gè)重要的問(wèn)題在于數(shù)據(jù)獲取困難，從而導(dǎo)

36、致在小樣本上出現(xiàn)過(guò)配；而如今大量數(shù)據(jù)迅速到達(dá)樣本獲取不再困難，但處理時(shí)的資源消耗成為主要的瓶頸；而且對(duì)數(shù)據(jù)流進(jìn)行分析時(shí)不能忽略它的另一個(gè)重要性質(zhì):數(shù)據(jù)經(jīng)過(guò)處理后，除非有其特殊價(jià)值，否則不進(jìn)行保存，這主要是因?yàn)閮?nèi)存有限而使用外存增加處理時(shí)間。為了和數(shù)據(jù)流模型相適應(yīng)，對(duì)應(yīng)的數(shù)據(jù)挖掘算法需要能夠只需要單遍掃描樣本子集就能有效地快速地進(jìn)行學(xué)習(xí)。另外和現(xiàn)實(shí)數(shù)據(jù)相關(guān)的數(shù)據(jù)流還有一些不可以忽略的性質(zhì)，例如數(shù)據(jù)分布可能隨時(shí)間變化而改變等，這就需要對(duì)一定

37、時(shí)間內(nèi)子樣本進(jìn)行學(xué)習(xí)的結(jié)果進(jìn)行更新，這樣的算法才能自適應(yīng)數(shù)據(jù)分布的變化。相對(duì)于普通的數(shù)據(jù)挖掘算法，數(shù)據(jù)流的算法時(shí)空復(fù)雜度小，但是大多得到的是相對(duì)于普通算法的次優(yōu)解，于是對(duì)數(shù)據(jù)流挖掘算法和普通算法差異的</p><p>　　界的討論也是必要的。</p><p>　　數(shù)據(jù)流挖掘算法和傳統(tǒng)挖掘算法相對(duì)比有其特殊的地方。無(wú)論是分類、聚類還是頻繁模式挖掘，數(shù)據(jù)流上的算法注重的都是一遍掃描數(shù)據(jù)集，并盡

38、可能對(duì)結(jié)果集壓縮存儲(chǔ)。所有的分類和聚類算法注重模型的定義及再建立，以取得更好的匹配效果，使得分類或聚類的效果更好，而時(shí)間效率并不太關(guān)心；在數(shù)據(jù)流上進(jìn)行分類或聚類算法則注意動(dòng)態(tài)的適應(yīng)數(shù)據(jù)的變化，盡可能及時(shí)地調(diào)整模型，算法的執(zhí)行速度要達(dá)到一定要求，而建模的精確程度沒(méi)有過(guò)多研究。原有的頻繁模式挖掘算法因?yàn)樽罱K結(jié)果是固定的，所以算法重點(diǎn)在于減少掃描數(shù)據(jù)集的次數(shù)， 以獲得更好的時(shí)間效果；在數(shù)據(jù)流上挖掘頻繁模式，算法一方面要保證只掃描一遍數(shù)據(jù)，另一

39、方面要使結(jié)果集與統(tǒng)計(jì)的結(jié)果相比盡可能準(zhǔn)確，挑戰(zhàn)是可想而知的。有的算法通過(guò)哈?；虺闃拥确椒?，在保證一定誤差下降低處理的數(shù)據(jù)量，加快響應(yīng)時(shí)間:有的算法以低支持度闡值的方法，來(lái)保證在一遍掃描的前提下，及時(shí)記錄可能頻繁的模式，使挖掘結(jié)果的誤差盡量低。</p><p>　　數(shù)據(jù)歷史信息的壓縮存儲(chǔ)也是數(shù)據(jù)流挖掘算法共同關(guān)心的問(wèn)題。一般來(lái)說(shuō)，算法只保存數(shù)據(jù)的概要信息，如統(tǒng)計(jì)值；或分時(shí)間段保存數(shù)據(jù)，將大量信息存儲(chǔ)為幾個(gè)代表點(diǎn)。另

40、外，隨著數(shù)據(jù)的流動(dòng)，部分信息可能過(guò)時(shí)，算法通常以一定策略進(jìn)行刪除，以釋放存儲(chǔ)空間。</p><p>　　2.3 數(shù)據(jù)流挖掘的關(guān)鍵問(wèn)題</p><p>　　頻繁項(xiàng)集挖掘是找出支持度大于給定支持度的所有項(xiàng)集。這些項(xiàng)集被稱為頻繁項(xiàng)集。由于數(shù)據(jù)流的連續(xù)性、無(wú)限性、商速性及數(shù)據(jù)分布隨時(shí)間不斷改變這些特性，傳統(tǒng)的頻繁項(xiàng)集挖掘方法不再完全適用。這就使得我們?cè)谶M(jìn)行數(shù)據(jù)流中頻繁項(xiàng)集的挖掘時(shí)需要考慮比傳統(tǒng)的數(shù)

41、據(jù)庫(kù)中頻繁項(xiàng)集挖掘更多的問(wèn)題。</p><p>　　由于數(shù)據(jù)流的特點(diǎn)，在對(duì)數(shù)據(jù)流進(jìn)行頻繁項(xiàng)挖掘時(shí)我們需要考慮以下問(wèn)題：</p><p>　　數(shù)據(jù)處理模型建立進(jìn)行挖掘的數(shù)據(jù)流中數(shù)據(jù)的處理模型；</p><p>　　壓縮數(shù)據(jù)結(jié)構(gòu)建立壓縮的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)無(wú)限的數(shù)據(jù)中的有用數(shù)據(jù)；</p><p>　　計(jì)算高效的一追掃描算法高速處理數(shù)據(jù)流；</p&

42、gt;<p>　　概念漂移適應(yīng)數(shù)據(jù)分布的變化；</p><p>　　自適應(yīng)性根據(jù)資源和數(shù)據(jù)流自己進(jìn)行調(diào)整。</p><p>　　2.3.1 數(shù)據(jù)處理模型</p><p>　　在進(jìn)行數(shù)據(jù)流挖掘算法設(shè)計(jì)時(shí)，首先要考慮的問(wèn)題是要對(duì)數(shù)據(jù)流中哪些數(shù)據(jù)進(jìn)行哪些挖掘。數(shù)據(jù)處理模型便是對(duì)數(shù)據(jù)流中數(shù)據(jù)進(jìn)行處理、挖掘的模型。當(dāng)前的數(shù)據(jù)流挖掘算法中主要存在三中數(shù)據(jù)模型：La

43、ndmark Windows、Damped Windows、Slinding Windows。</p><p>　　Landmark Windows模型挖掘從某一叫做landmark的時(shí)間點(diǎn)到現(xiàn)在的所有歷史數(shù)據(jù)中的頻繁項(xiàng)集。無(wú)限的窗口是這一模型的特殊情況。它挖掘從數(shù)據(jù)流開(kāi)始到當(dāng)前所有的數(shù)據(jù)中的頻繁項(xiàng)集。但是，這一模型不適合于人們只對(duì)數(shù)據(jù)流中最近的信息感興趣的應(yīng)用。</p><p>　　Da

44、mped Windows模型也叫做時(shí)間衰退(Time-fading)模型。在這種模型中，數(shù)據(jù)流中每一個(gè)項(xiàng)集都有一個(gè)權(quán)重。該權(quán)重隨時(shí)間逐漸減小，即新出現(xiàn)的項(xiàng)集對(duì)該項(xiàng)集的頻度影響大于原來(lái)的項(xiàng)集。這種模型考慮對(duì)新的和舊的數(shù)據(jù)賦予不同的權(quán)重。這適合于舊的數(shù)據(jù)對(duì)挖掘結(jié)果產(chǎn)生影響但是會(huì)隨著時(shí)間減弱的應(yīng)用.</p><p>　　Slinding Window模型挖掘和維護(hù)當(dāng)前窗口中的頻繁項(xiàng)集.窗口的大小根據(jù)應(yīng)用和資源來(lái)確定。在

45、金融和股票交易中，使用滑動(dòng)窗口模型更合適。</p><p>　　一個(gè)Landmark模型可以轉(zhuǎn)變成其它兩種模型。在其上加上時(shí)間衰退函數(shù)就能使其轉(zhuǎn)變?yōu)镈amped模型。在其上跟蹤、處理一個(gè)滑動(dòng)的窗口中的數(shù)據(jù)就能使該模型變?yōu)橐粋€(gè)Slinding Windows模型.</p><p>　　不同的數(shù)據(jù)模型適用于不同的具體應(yīng)用。在進(jìn)行數(shù)據(jù)流挖掘算法設(shè)計(jì)時(shí)，具體使用哪種模型根據(jù)具體的應(yīng)用對(duì)象而定。&l

46、t;/p><p>　　2.3.2 壓縮的數(shù)據(jù)結(jié)構(gòu)</p><p>　　靜態(tài)數(shù)據(jù)上的頻繁項(xiàng)集挖掘是在多追掃描數(shù)據(jù)庫(kù)之后，收集所有項(xiàng)集的計(jì)數(shù)信息并且丟棄非頻縈項(xiàng)集和它們的計(jì)數(shù)信息。但是在數(shù)據(jù)流上進(jìn)行頻繁項(xiàng)集挖掘時(shí)這種方法是不可行的。第一，當(dāng)巨大的數(shù)據(jù)流連續(xù)不斷的到來(lái)時(shí)，不可能在內(nèi)存中存儲(chǔ)所有的項(xiàng)集和它們的計(jì)數(shù)。第二，項(xiàng)集計(jì)數(shù)隨新到來(lái)的數(shù)據(jù)而改變。一種算法是存儲(chǔ)最頻繁的項(xiàng)集和它們的計(jì)數(shù)。這種算法存儲(chǔ)

47、了最重要的信息，但是丟棄了非頻繁項(xiàng)集的計(jì)數(shù)和將來(lái)有可能成為頻繁項(xiàng)集的項(xiàng)集?？梢钥吹剑瑸榱耸占嗟馁Y源來(lái)獲得更精確的結(jié)果就會(huì)使用更多的內(nèi)存空間和需要更多的處理時(shí)間。這就 需 要 一個(gè)有效的壓縮的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)更新和檢索收集的信息。由于有限的內(nèi)存空間和巨大的數(shù)據(jù)流連續(xù)不斷的到來(lái)。不能建立這樣一種數(shù)據(jù)結(jié)構(gòu)將會(huì)很大程度的降低挖掘算法。因?yàn)榧词刮覀冊(cè)诖疟P(pán)上存儲(chǔ)了這些信息，附加的I/O操作將會(huì)增加處理時(shí)間。由于巨大的數(shù)據(jù)量不可能重新掃描整個(gè)輸入數(shù)

48、據(jù)來(lái)滿足在線查詢高度響應(yīng)的要求，因此數(shù)據(jù)結(jié)構(gòu)必須增量維護(hù)。</p><p>　　能否建立一個(gè)好的壓縮數(shù)據(jù)結(jié)構(gòu)是一個(gè)數(shù)據(jù)流挖掘算法性能好壞甚至是否可行的重要基礎(chǔ)。</p><p>　　現(xiàn)存的一些算法使用的壓縮數(shù)據(jù)結(jié)構(gòu)有FP-樹(shù)、前綴樹(shù)。樹(shù)形結(jié)構(gòu)壓縮程度較高，是常用的數(shù)據(jù)結(jié)構(gòu)。略圖是進(jìn)行頻繁項(xiàng)集統(tǒng)計(jì)的一種有效的壓縮數(shù)據(jù)結(jié)構(gòu)。它將計(jì)數(shù)映射到一個(gè)Sketch數(shù)據(jù)結(jié)構(gòu)中進(jìn)行壓縮統(tǒng)計(jì)。在設(shè)計(jì)算法時(shí)，選

49、擇適合的項(xiàng)集壓縮數(shù)據(jù)結(jié)構(gòu)和項(xiàng)集計(jì)數(shù)的統(tǒng)計(jì)壓縮數(shù)據(jù)結(jié)構(gòu)。此外，還有一些其它的概要數(shù)據(jù)結(jié)構(gòu)。</p><p>　　2.3.3 概念漂移</p><p>　　數(shù)據(jù)流中的數(shù)據(jù)分布隨著時(shí)間不斷的改變。這些變化經(jīng)常使在舊的數(shù)據(jù)上建立的模型和新的數(shù)據(jù)產(chǎn)生不一致，而且需要頻繁的更新模型。在某一時(shí)間段內(nèi)出現(xiàn)的頻繁項(xiàng)集可能在下一個(gè)時(shí)間段內(nèi)變成非頻繁的項(xiàng)集。同樣在某一時(shí)間段非頻繁的項(xiàng)集在下一時(shí)間段可能變成頻繁的

50、項(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ù)。</p><p>　　滑動(dòng)窗口技術(shù)能夠針對(duì)窗口大小的數(shù)據(jù)流進(jìn)行挖掘，不會(huì)受到以前挖掘結(jié)果的影響。FP-stream算法中在頻繁模式樹(shù)中嵌入時(shí)間窗口，可以挖掘不同時(shí)間粒度的頻繁項(xiàng)集。 Slinding Window方法挖掘滑動(dòng)窗口中的頻繁項(xiàng)集。在設(shè)計(jì)針對(duì)數(shù)據(jù)

51、分布不斷變化的挖掘算法時(shí)，可以考慮使用滑動(dòng)窗口技術(shù)挖掘不同范圍和不同時(shí)間粒度的數(shù)據(jù)。</p><p>　　2.3.4 自適應(yīng)性</p><p>　　在數(shù)據(jù)挖掘中，內(nèi)存和CPU等資源十分珍貴。如何有效利用這些資源是設(shè)計(jì)數(shù)據(jù)流挖掘算法時(shí)需要考慮的又一問(wèn)題。</p><p>　　當(dāng)可用資源較少時(shí)，流數(shù)據(jù)高速到來(lái)很快就會(huì)耗盡資源。如果在算法中不考慮資源的使用情況，則很可能導(dǎo)

52、致大量數(shù)據(jù)的丟失甚至挖掘產(chǎn)生錯(cuò)誤和失敗。當(dāng)可用資源較多時(shí)，算法能夠根據(jù)可用資源來(lái)進(jìn)行調(diào)整則可以提高挖掘的精度和速度。另外，當(dāng)前各種手持設(shè)備和傳感器網(wǎng)絡(luò)的普及也要求算法能夠根據(jù)不同的設(shè)備和資源來(lái)自行調(diào)整。</p><p>　　所以，根據(jù)資源來(lái)自行調(diào)整挖掘參數(shù)進(jìn)行有效的挖掘是算法設(shè)計(jì)時(shí)要考慮的問(wèn)題之一。</p><p>　　降載技術(shù)在一定程度上可以解決數(shù)據(jù)流爆發(fā)或者數(shù)據(jù)流輸入超過(guò)系統(tǒng)處理能力的

53、情況。但是降載技術(shù)丟棄了一些比較重要的數(shù)據(jù)。因此，在使用降載技術(shù)解決數(shù)據(jù)流挖掘算法的自適應(yīng)性問(wèn)題時(shí)，要慎重考慮。此外，數(shù)據(jù)流挖掘算法還可以考慮在處理能力有限的情況下，</p><p>　　使用一些概要的數(shù)據(jù)結(jié)構(gòu)代表數(shù)據(jù)進(jìn)行粗粒度的數(shù)據(jù)處理。</p><p><b>　　2.4 本章小結(jié)</b></p><p>　　本章主要介紹了數(shù)據(jù)流這一新型數(shù)

54、據(jù)類型的特點(diǎn)，管理數(shù)據(jù)流應(yīng)該采用的數(shù)據(jù)流管理系統(tǒng)模型。對(duì)比傳統(tǒng)的數(shù)據(jù)挖掘，由于數(shù)據(jù)流本身所具有的特點(diǎn)，在數(shù)據(jù)流上執(zhí)行挖掘要面臨許多新的困難。</p><p>　　介紹了數(shù)據(jù)流的特點(diǎn)、數(shù)據(jù)流挖掘的關(guān)鍵問(wèn)題和數(shù)據(jù)流處理技術(shù)。數(shù)據(jù)流是一個(gè)隨時(shí)間到來(lái)的數(shù)據(jù)序列。它具有連續(xù)性、無(wú)限性、高速性、分布隨時(shí)間改變的特點(diǎn)。由于數(shù)據(jù)流的這些特點(diǎn)，我們?cè)谶M(jìn)行數(shù)據(jù)流挖掘時(shí)必須考慮更多的問(wèn)題。在對(duì)數(shù)據(jù)流進(jìn)行挖掘時(shí)我們要考慮到數(shù)據(jù)處理模型、

55、壓縮的數(shù)據(jù)結(jié)構(gòu)、計(jì)算高效的一遍掃描算法、概念漂移、自適應(yīng)性等關(guān)鍵的問(wèn)題。數(shù)據(jù)流的處理技術(shù)主要有基于數(shù)據(jù)的和基于任務(wù)的兩種。其中基于數(shù)據(jù)的技術(shù)主要有概要數(shù)據(jù)結(jié)構(gòu)(Synopsis data structures)和聚集(Aggregation)、采樣(sampling)、降載(Load shedding)、略圖(Skeching)等技術(shù)?；谌蝿?wù)的技術(shù)主要有近似算法</p><p>　　(Approximation

56、 algorithm)、窗口(window)和算法輸出粒度(Algorithm output granularity)等技術(shù)。還介紹了數(shù)據(jù)流上數(shù)據(jù)挖掘的思路，說(shuō)明了數(shù)據(jù)流挖掘在側(cè)重點(diǎn)上有哪些變化。</p><p>　　第三章 頻繁項(xiàng)挖掘及相關(guān)算法</p><p>　　頻繁項(xiàng)挖掘作為關(guān)聯(lián)規(guī)則挖掘的基礎(chǔ)，一直是數(shù)據(jù)挖掘領(lǐng)域的重點(diǎn)。其中FP-growth算法是較為有效的一種挖掘算法</p&

57、gt;<p>　　3.1 頻繁模式概念</p><p>　　給定項(xiàng)目集I = {i1,i2,...,im}。其中，ik(1≤k≤m)是一個(gè)項(xiàng)目(item)，I的非空子集稱為模式。一個(gè)模式所包含的項(xiàng)目的數(shù)量稱為該模式的長(zhǎng)度。數(shù)據(jù)集D是一組事務(wù)的集合，事務(wù)是I的非空子集，數(shù)據(jù)集D包含的事務(wù)的總數(shù)記為|D|。</p><p>　　數(shù)據(jù)集D中包含模式P的事務(wù)的數(shù)量稱為P的計(jì)數(shù)，記為f

58、(P)。P的計(jì)數(shù)與數(shù)據(jù)集中事務(wù)的總數(shù)的比值稱為P的支持度(support)，記為s(P)。假定ξ是事先設(shè)定的最小支持度，如果s(P)≥ξ，則稱P是頻繁的。所有頻繁模式的集合稱為頻繁集，記為F。</p><p>　　頻繁模式挖掘通常用于進(jìn)一步產(chǎn)生關(guān)聯(lián)規(guī)則，或直接作為決策支持的輔助信息，主要應(yīng)用于分類設(shè)計(jì)、交叉購(gòu)物和賤賣(mài)分析等等。典型的例子是購(gòu)物籃分析，通過(guò)了解哪些商品頻繁地被顧客同時(shí)購(gòu)買(mǎi)，可以幫助零售商制訂營(yíng)銷策略

59、。然而，現(xiàn)在大多數(shù)公司組織都采用電子方式記錄他們涉及的每一件事務(wù)，當(dāng)這個(gè)組織變大，記錄的結(jié)果每天也就相應(yīng)的迅速增加，無(wú)論是支持商業(yè)決策而挖掘的銷售數(shù)據(jù)，還是Web挖掘所用的日志數(shù)據(jù)，其增長(zhǎng)速率都在飛速提高，例如Google網(wǎng)站每天處理1億500萬(wàn)條搜索記錄。并且，例如決策支持、傳感器數(shù)據(jù)分析和個(gè)性化推薦等，這些頻繁模式挖掘的應(yīng)用領(lǐng)域?qū)?dòng)態(tài)反饋的要求都比較高，簡(jiǎn)單提高傳統(tǒng)算法的時(shí)間效率并不能完全滿足數(shù)據(jù)流上這些要求。必須以數(shù)據(jù)流的方式處理

60、這些數(shù)據(jù)，研究數(shù)據(jù)流中頻繁模式挖掘的方法。數(shù)據(jù)流頻繁模式挖掘應(yīng)用廣泛，近年來(lái)網(wǎng)絡(luò)安全是應(yīng)用數(shù)據(jù)流挖掘技術(shù)比較多的一個(gè)領(lǐng)域，但傳統(tǒng)的網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)多采用預(yù)先設(shè)置好規(guī)則，然后進(jìn)行規(guī)則對(duì)比發(fā)現(xiàn)威脅，網(wǎng)絡(luò)流的高速要求實(shí)時(shí)對(duì)數(shù)據(jù)進(jìn)行處理，挖掘網(wǎng)絡(luò)流的頻繁模式就能進(jìn)一步為網(wǎng)絡(luò)入侵系統(tǒng)提供有用信息。除此之外數(shù)據(jù)流中的頻繁模式挖掘還廣泛應(yīng)用于傳感器網(wǎng)絡(luò)等。</p><p>　　3.1.1 頻繁模式分類</p>&

61、lt;p>　　定義3.1：設(shè)所有項(xiàng)的集合={I1，I2...Im}，Ii為第i個(gè)項(xiàng)。事務(wù)數(shù)據(jù)庫(kù)D{T1,T2...Tn}，Ti是第i個(gè)事務(wù)，Ti是的子集，例如:TI={I1，I3，I7}，|D|為事務(wù)數(shù)據(jù)庫(kù)的長(zhǎng)度。項(xiàng)Ii在事務(wù)數(shù)據(jù)庫(kù)中出現(xiàn)的次數(shù)記為Si,用戶定義最小支持度(0<1)，如果Si大于|D|，項(xiàng)Ii就是頻繁項(xiàng)。項(xiàng)集F是E的子集，如果項(xiàng)集F在事務(wù)數(shù)據(jù)庫(kù)中出現(xiàn)的次數(shù)大于|D|，那么項(xiàng)集F就是頻繁項(xiàng)集。</p>

62、;<p>　　依據(jù)Apriori性質(zhì)得到，頻繁項(xiàng)集的子集也是頻繁的，只要得到最大頻繁項(xiàng)集或頻繁閉項(xiàng)集就能得到大部分頻繁項(xiàng)集。</p><p>　　定義3.2：最大頻繁項(xiàng)集(M)是指頻繁項(xiàng)集的任何超集都不是頻繁的。挖掘最大頻繁項(xiàng)集的結(jié)果集數(shù)量遠(yuǎn)遠(yuǎn)小于頻繁項(xiàng)集的數(shù)量，從最大頻繁項(xiàng)集的子集得到的頻繁項(xiàng)集丟失了頻繁計(jì)數(shù)信息。所以，只挖掘最大頻繁項(xiàng)集會(huì)丟失大量有用信息。</p><p>

63、;　　定義3.3：頻繁閉項(xiàng)集(C)是指頻繁項(xiàng)集的頻繁計(jì)數(shù)大于任何超集的頻繁數(shù)。挖掘頻繁閉項(xiàng)集的結(jié)果數(shù)量遠(yuǎn)遠(yuǎn)小于頻繁項(xiàng)集的數(shù)量，從頻繁項(xiàng)集的子集得到的頻繁項(xiàng)集，它的支持度一定等于頻繁閉項(xiàng)集的支持度。所以頻繁項(xiàng)集的信息得到了保存。</p><p><b>　　3.2 挖掘方法</b></p><p>　　數(shù)據(jù)流中頻繁模式挖掘算法按挖掘方式的不同，可以分為批處理算法與啟發(fā)式

64、算法兩種。批處理方法的處理速度較快，但需要積攢足夠數(shù)據(jù)，無(wú)法滿足實(shí)時(shí)性要求，并且查詢粒度通常較粗。啟發(fā)式方法能夠隨流數(shù)據(jù)的到達(dá)直接進(jìn)行處理，在一定程度上可以實(shí)時(shí)反映頻繁模式的變化，但對(duì)于高速到達(dá)的數(shù)據(jù)流，其處理速度仍然有限，且現(xiàn)有算法的模式統(tǒng)計(jì)計(jì)數(shù)不包含詳細(xì)歷史信息，使得模式估計(jì)與查詢精度仍然較低。</p><p>　　3.2.1 批處理方法</p><p>　　批處理方法主要思想是對(duì)數(shù)據(jù)

65、流分片，通過(guò)分片上的局部頻繁模式來(lái)求解全局頻繁模式。批處理方法中有代表性的是Manku提出的Lossy counting算法Gialmela等提出的FP-stream 算法。</p><p>　　Lossy counting算法中，數(shù)據(jù)流被分為均勻分片，每片包含1/個(gè)事務(wù)，初始分片編號(hào)為1，之后依次遞增。其中是事先指定的允許誤差，遠(yuǎn)遠(yuǎn)小于通常使用的頻繁度闡值。頻繁模式集以三元組(set,f,)存儲(chǔ)模式，set標(biāo)識(shí)

66、唯一模式，f為模式計(jì)數(shù)，為計(jì)數(shù)誤差。算法每次處理個(gè)分片，若分片中的模式包含于頻繁模式集，則按在分片中的出現(xiàn)次數(shù)更新那些被包含模式的f值；若不包含于頻繁模式集，則判斷模式在分片中的出現(xiàn)次數(shù)是否大于民若是則將該模式加入頻繁模式集，新加入模式的值為當(dāng)前分片編號(hào)減1。算法定期掃描頻繁模式集，若模式的(f+)值小于當(dāng)前編號(hào)，則將模式從頻繁模式集中刪除。</p><p>　　Lossy Counting算法的頻繁模式集中包含

67、所有真實(shí)計(jì)數(shù)大于。N的模式，N是當(dāng)前數(shù)據(jù)流中的事務(wù)數(shù)。如果一個(gè)模式包含于頻繁模式集，其真實(shí)計(jì)數(shù)一定在f與(f+)之間。如果用戶以闡值5查詢頻繁模式，算法輸出頻繁模式集中f值大于(s-)N的所有模式。</p><p>　　FP-stream算法基本思想與Lossy Counting算法一致。FP-Stream算法在將數(shù)據(jù)流均勻分片后，依照模式在第一分片中的計(jì)數(shù)排序，構(gòu)造字典樹(shù)來(lái)存儲(chǔ)頻繁模式集。算法在當(dāng)前分片中，以不

68、指定閥值的FP一Growth算法挖掘模式。如果模式存在于字典樹(shù)中，則更新其計(jì)數(shù);若不存在，則判斷其計(jì)數(shù)是否大于指定誤差￡與分片包含事務(wù)數(shù)B的乘積，如果大于則將其插入字典樹(shù)。</p><p>　　FP-stream算法利用時(shí)間窗口記錄模式的歷史信息來(lái)回答用戶對(duì)各個(gè)時(shí)間段的查詢。基于人們對(duì)越新的事物關(guān)心程度越高的事實(shí)，算法使用一種“傾斜”的時(shí)間窗以不同粒度壓縮不同時(shí)間段的數(shù)據(jù)，給出在這種時(shí)間窗下保證模式查詢精度的斷言

69、與證明。并對(duì)該算法進(jìn)行了改進(jìn)，提出全局時(shí)間窗方法，以衰減的策略發(fā)現(xiàn)最近頻繁的模式。</p><p>　　批處理方法時(shí)間效率較好，但不能實(shí)時(shí)處理流數(shù)據(jù)和響應(yīng)用戶對(duì)當(dāng)前數(shù)據(jù)的查詢，并且算法查詢精度較低，即使使用時(shí)間窗口，其窗口粒度仍然較粗(等于每分片包含的事務(wù)數(shù))。</p><p>　　3.2.2 啟發(fā)式方法</p><p>　　啟發(fā)式方法的主要思想是隨著流數(shù)據(jù)的不斷到

70、達(dá)，由己知頻繁模式逐步生成新的頻繁模式，基本過(guò)程是當(dāng)新事務(wù)到達(dá)后，判斷其中新模式蘊(yùn)含的所有父模式，只有當(dāng)新模式的所有父模式都己經(jīng)存在于頻繁模式集，才將其加入模式集。</p><p>　　由于在啟發(fā)式挖掘頻繁模式過(guò)程中，長(zhǎng)度為k的模式只有在其所有長(zhǎng)度為k-1的父模式都被發(fā)現(xiàn)的前提下，才能被考慮，因而存在模式計(jì)數(shù)偏小的問(wèn)題。Hidber提出Carma算法對(duì)這個(gè)問(wèn)題進(jìn)行了改進(jìn)，提出以父模式中的最小頻數(shù)估計(jì)新產(chǎn)生模式的頻

71、數(shù)，算法中頻繁模式集也以三元組存儲(chǔ):計(jì)數(shù)count，首次發(fā)生時(shí)間firstTrans，最大誤差maxMissed。Carma算法中通過(guò)第二次掃描數(shù)據(jù)來(lái)保證最大誤差，從而使其在數(shù)據(jù)流挖掘中的應(yīng)用受到限制。</p><p>　　Chang等的estDec算法采用了字母序的字典樹(shù)存儲(chǔ)模式，應(yīng)用了類似Carma算法的估計(jì)頻數(shù)思想，也是以新模式的父模式中的最小計(jì)數(shù)來(lái)近似估計(jì)新模式的實(shí)際計(jì)數(shù)，并由闡值s與模式長(zhǎng)度k約束頻數(shù)上

72、限。算法通過(guò)按時(shí)間指數(shù)進(jìn)行衰減的策略，保證只挖掘最近發(fā)生的頻繁模式。</p><p>　　同批處理方法相比，啟發(fā)式方法不需要積累數(shù)據(jù)，具有較好的實(shí)時(shí)性和更高的查詢精度。但算法均以字典樹(shù)的結(jié)構(gòu)保存挖掘結(jié)果，而挖掘得到的模式較多，使得結(jié)構(gòu)較寬，無(wú)論是在其中對(duì)是否增加節(jié)點(diǎn)進(jìn)行判斷，還是更新節(jié)點(diǎn)的計(jì)數(shù)信息，都需要在結(jié)構(gòu)中橫向查找，其時(shí)間代價(jià)較大。對(duì)于高速到達(dá)的數(shù)據(jù)流，啟發(fā)式算法的處理速度仍然有限，且現(xiàn)有算法的模式計(jì)數(shù)不包

73、含詳細(xì)歷史信息，使得模式估計(jì)與查詢精度仍然較低。</p><p>　　3.2.3 增量更新方法</p><p>　　批處理的方法分片處理數(shù)據(jù)流，在每個(gè)分片上可以使用現(xiàn)有的各種快速挖掘算法，從而整體處理速度快。但數(shù)據(jù)流頻繁模式挖掘?yàn)榉乐箍赡茴l繁的模式不能被及時(shí)發(fā)現(xiàn)，通常使用較低的支持度閾值，這樣一來(lái)，數(shù)據(jù)流的分片寬度也隨之變大。在大的分片寬度下，算法要等待積攢足夠的數(shù)據(jù)才能執(zhí)行，從而使得對(duì)當(dāng)

74、前數(shù)據(jù)的處理不夠及時(shí)，也就不能盡快的反映頻繁模式的變化情況。并且由于分片寬度關(guān)系到窗口粒度，進(jìn)而與查詢精度相關(guān)，所以批處理方法的查詢粒度也較粗。</p><p>　　啟發(fā)式方法以事務(wù)為單位處理數(shù)據(jù)流，可以及時(shí)響應(yīng)對(duì)當(dāng)前數(shù)據(jù)的查詢，具有較好的實(shí)時(shí)性。由于挖掘任務(wù)通常在具有較多的項(xiàng)的數(shù)據(jù)集上進(jìn)行，如多種類的商品(購(gòu)物籃分析)，大量的網(wǎng)頁(yè)(Web挖掘、個(gè)性化推薦)等等。由大量的項(xiàng)所組成的事務(wù)也就包含了大量的模式，并且在

75、數(shù)據(jù)流頻繁模式挖掘所使用的低闡值下，相當(dāng)數(shù)量的模式被認(rèn)為是頻繁或者可能頻繁而被記錄。這樣在被大多算法使用的樹(shù)型模式存儲(chǔ)結(jié)構(gòu)中，表現(xiàn)出的后果就是樹(shù)的寬度極大，并進(jìn)一步導(dǎo)致在樹(shù)中查找模式的代價(jià)很大。啟發(fā)式算法在處理每個(gè)事務(wù)時(shí)，無(wú)論是對(duì)己有模式進(jìn)行更新，還是在增加新模式時(shí)對(duì)相應(yīng)父模式進(jìn)行判斷，都需要在樹(shù)中進(jìn)行查找操作，這使得算法整體時(shí)間效率較低。</p><p>　　數(shù)據(jù)流挖掘中人們往往關(guān)注最近的數(shù)據(jù)。本文以啟發(fā)式算法

76、為基礎(chǔ)，采用定量更新滑動(dòng)窗口技術(shù)來(lái)實(shí)現(xiàn)對(duì)當(dāng)前數(shù)據(jù)流的挖掘。</p><p><b>　　3.3 有關(guān)算法</b></p><p>　　3.3.1 Apriori算法</p><p>　　1994年Agrawal等在先前工作的基礎(chǔ)上，完善了一個(gè)稱為Apriori的關(guān)聯(lián)規(guī)則</p><p>　　挖掘算法。該算法是一種最有影響

77、的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法，是用先驗(yàn)知識(shí)，通過(guò)項(xiàng)目集元素?cái)?shù)目不斷增長(zhǎng)來(lái)逐步完成頻繁項(xiàng)目集的發(fā)現(xiàn)。首先找出頻繁1-項(xiàng)集的集合，記做L1。L1用于找頻繁2-項(xiàng)集合L2。L2而又用于找L3。如此下去，直到不能找到頻繁k-項(xiàng)集。</p><p>　　該算法基于這樣一個(gè)性質(zhì)：頻繁項(xiàng)目集的子集是頻繁項(xiàng)目集；非頻繁項(xiàng)目集</p><p>　　的超集是非頻繁項(xiàng)目集。是通過(guò)項(xiàng)目集元素?cái)?shù)目不斷增長(zhǎng)來(lái)逐步

78、完成頻繁項(xiàng)目集發(fā)現(xiàn)的。首先產(chǎn)生1-頻繁項(xiàng)集L1，然后是2-頻繁項(xiàng)集L2，直到不再能擴(kuò)展頻繁項(xiàng)集的元素?cái)?shù)目而算法停止。在第k次循環(huán)中，過(guò)程先產(chǎn)生k-候選項(xiàng)集的集合Ck然后通過(guò)掃描數(shù)據(jù)庫(kù)生成支持度并側(cè)試產(chǎn)生k-頻繁項(xiàng)集Lk。</p><p>　　Apriori算法有兩個(gè)致命的性能瓶頸：它可能產(chǎn)生很大的候選項(xiàng)集。例如，如果有104個(gè)頻繁1-項(xiàng)集，則Apriori算法可能產(chǎn)生接近107個(gè)元素的2-侯選集。這樣的龐大的候選

79、項(xiàng)集在時(shí)間和空間上都是很難接受的。</p><p>　　它可能重復(fù)掃描數(shù)據(jù)庫(kù)，需要很大的I/O負(fù)載。每產(chǎn)生一次候選項(xiàng)集都要掃</p><p>　　描一次數(shù)據(jù)庫(kù)。如果頻繁項(xiàng)集包含的項(xiàng)很多的話就需要多次掃描數(shù)據(jù)庫(kù)。這樣I/O</p><p><b>　　開(kāi)銷十分龐大。</b></p><p>　　3.3.2 Close算法&

80、lt;/p><p>　　1999年P(guān)asquier等人提出關(guān)閉項(xiàng)目集挖掘理論，并給出了基于這種理論的Close算法。他們給出了關(guān)閉項(xiàng)目集的概念，并討論了這個(gè)關(guān)閉項(xiàng)目集格空間上的基本操作算子。Close 算法是基于這樣原理的:一個(gè)頻繁關(guān)閉項(xiàng)目集的所有關(guān)閉子集一定是頻繁的，一個(gè)非頻繁關(guān)閉項(xiàng)目集的所有關(guān)閉超集一定是非頻繁的。因此，可以在關(guān)閉項(xiàng)目集空間格上討論頻策問(wèn)題。實(shí)驗(yàn)證明，它對(duì)特殊數(shù)據(jù)是可以減少數(shù)據(jù)庫(kù)掃描次數(shù)的。<

81、;/p><p>　　Close算法仍然沿用Apriori算法遞增測(cè)試項(xiàng)目集的方法來(lái)尋找頻繁項(xiàng)目集的，但是它是在關(guān)閉項(xiàng)目集格空間上側(cè)試，提高了生成頻繁項(xiàng)目集的效率，并且可能減少掃描數(shù)據(jù)庫(kù)的次數(shù)。</p><p>　　Close算法存在的主要問(wèn)題是：(1)當(dāng)最小支持度較小時(shí)，每個(gè)層次上的關(guān)閉頻繁項(xiàng)目集的數(shù)目仍很大，因此不可能大幅度提高效率；(2)事先很難確定具體的數(shù)據(jù)庫(kù)掃描次數(shù)；(3)為形成關(guān)閉項(xiàng)

82、目集需要額外的代價(jià)。.</p><p>　　3.3.3 FP-growth算法</p><p>　　2000年Han等提出了一種FP-growth算法。該算法挖掘全部的頻繁項(xiàng)集而不用產(chǎn)生候選項(xiàng)集。它將提供頻繁項(xiàng)集的數(shù)據(jù)庫(kù)壓縮到一顆頻繁模式樹(shù)，但仍保留項(xiàng)集關(guān)聯(lián)信息。通過(guò)頻繁模式樹(shù)挖掘出頻繁項(xiàng)集。該算法只需兩次掃描數(shù)據(jù)庫(kù)。構(gòu)造一顆頻繁模式樹(shù)的過(guò)程如下：</p><p>

83、　　掃描事務(wù)數(shù)據(jù)庫(kù)D一遍，生成頻繁1-項(xiàng)集。將頻繁項(xiàng)集降序排序，放入頻繁項(xiàng)表L。</p><p>　　創(chuàng)建FP-tree的根節(jié)點(diǎn)，以“null”標(biāo)記它。對(duì)于D中的事務(wù)丸選擇其中的頻繁項(xiàng)并按L中的次序排序。然后遞歸調(diào)用FP-growth來(lái)實(shí)現(xiàn)FP-tree增長(zhǎng)。</p><p><b>　　3.4 本章小結(jié)</b></p><p>　　本章主要介

84、紹了頻繁項(xiàng)集的概念、經(jīng)典的頻繁項(xiàng)集挖掘算法和實(shí)驗(yàn)分析。Apriori算法是較早提出的經(jīng)典頻繁項(xiàng)集挖掘算法。但是，該算法存在產(chǎn)生大量候選項(xiàng)集和I/O的瓶頸。在Apriori的基礎(chǔ)上產(chǎn)生了一些變形的算法來(lái)提高效率，這其中有基于hash項(xiàng)集記數(shù)、事務(wù)壓縮、分割、采樣、動(dòng)態(tài)項(xiàng)集記數(shù)等。Close算法是一種在關(guān)閉項(xiàng)目集概念的基礎(chǔ)上提出的算法，該算法在一定程度上提高了挖掘效率，但也存在一定的問(wèn)題。FP-growth算法是一種不需產(chǎn)生候選項(xiàng)集的算法。

85、該算法兩次掃描數(shù)據(jù)庫(kù)并將頻繁項(xiàng)集壓縮到頻繁模式樹(shù)。但是，該算法在某些情況下效率也不高。</p><p>　　通過(guò)實(shí)驗(yàn)可以看出Apriori算法和FP-growth算法都不能適用于數(shù)據(jù)流中頻繁項(xiàng)集的挖掘。此外，由于增量更新和適應(yīng)數(shù)據(jù)分布變化的原因使得經(jīng)典的頻繁項(xiàng)集挖掘算法也不能應(yīng)用于數(shù)據(jù)流中頻繁項(xiàng)集的挖掘。</p><p>　　第四章 數(shù)據(jù)流上頻繁項(xiàng)挖掘算法</p><

86、p>　　4.1 改進(jìn)的FP-stream算法關(guān)鍵點(diǎn)</p><p>　　數(shù)據(jù)流上的頻繁模式挖掘通常要涉及時(shí)間數(shù)據(jù)，也就是模式的歷史計(jì)數(shù)信息。這主要是因?yàn)橥诰蛞蟛煌?，要結(jié)合不同時(shí)間段來(lái)判斷模式頻繁與否，如回答對(duì)含時(shí)間段頻繁模式的查詢，只輸出最近一段時(shí)間的模式頻繁信息，越舊的信息價(jià)值越低、從而要及時(shí)修剪等等。為滿足這些挖掘要求，只維護(hù)模式計(jì)數(shù)是不夠的，要為模式保存一定量的歷史信息。由于數(shù)據(jù)流的長(zhǎng)度理論上為無(wú)限

87、大，簡(jiǎn)單保存全部時(shí)間段的數(shù)據(jù)是不可能的，要進(jìn)行壓縮存儲(chǔ)。</p><p>　　所有數(shù)據(jù)流應(yīng)用的目標(biāo)是，在最近得到的數(shù)據(jù)的統(tǒng)計(jì)信息的基礎(chǔ)上做出代表整體屬性的判斷。比如，有人可能會(huì)對(duì)最近一天內(nèi)一些路由器處理過(guò)的分組的統(tǒng)計(jì)信息感興趣。而且我們更希望這些統(tǒng)計(jì)信息能夠以一種連續(xù)的方式維護(hù)，這就需要利用滑動(dòng)窗口模型了：數(shù)據(jù)元素可能在任何時(shí)刻到達(dá)，每個(gè)數(shù)據(jù)元素都會(huì)正好在N個(gè)時(shí)間步后作廢(expire，過(guò)期)，并且和統(tǒng)計(jì)信息相關(guān)

88、的或者和查詢結(jié)果相關(guān)的數(shù)據(jù)正是最近到達(dá)的N個(gè)數(shù)據(jù)元素。這里滑動(dòng)窗口就是指給定時(shí)刻的活動(dòng)數(shù)據(jù)元素窗口。</p><p>　　我們考慮這樣一個(gè)問(wèn)題，在一個(gè)數(shù)據(jù)流上維護(hù)目前為止最近的N個(gè)數(shù)據(jù)元素的總計(jì)以及其他統(tǒng)計(jì)變量，我們把這種只考慮最近N個(gè)元素的模型稱為滑動(dòng)窗口模型。我們考慮下面這樣一個(gè)最基本的問(wèn)題：給定一個(gè)位流，我們維護(hù)一個(gè)計(jì)數(shù)器，統(tǒng)計(jì)目前為止最近N位中值為1的總位數(shù)。我們將看到，使用位的存儲(chǔ)，我們能在ε的誤差內(nèi)計(jì)

89、算出1的位數(shù)。對(duì)于任意的確定的或者隨機(jī)化算法，我們也給出了它們的空間復(fù)雜度的下確界(matching lower bound)為。我們?cè)诖嘶A(chǔ)上將算法擴(kuò)展為維護(hù)數(shù)據(jù)流中最后N個(gè)正整數(shù)的和，并給出了這個(gè)更一般問(wèn)題的復(fù)雜度的上確界和下確界。我們也討論了怎樣在滑動(dòng)窗口模型下利用我們的技術(shù)有效計(jì)算向量集的Lp(p∈[1,2])范數(shù)(Lp norms)。使用我們的算法，可以將很多其它技術(shù)引進(jìn)到滑動(dòng)窗口模型下，而存儲(chǔ)空間需要的額外代價(jià)只有，以及ε的

90、精度損失。這些技術(shù)包括維護(hù)近似直方圖，散列表，總計(jì)和平均值等統(tǒng)計(jì)值。</p><p>　　4.1.1頭表fList的設(shè)計(jì)</p><p>　　如FP-growth算法中所述，頭表fList是一個(gè)非常重要的結(jié)構(gòu)，按照頻度從大到小來(lái)保存所有頻繁項(xiàng)，然后以此為標(biāo)桿，以里面的結(jié)構(gòu)nodelink來(lái)縱向連接頻繁項(xiàng)便于后面的挖掘。但是這是建立在永久型數(shù)據(jù)庫(kù)的基礎(chǔ)上的。不但可以掃描數(shù)據(jù)庫(kù)兩遍，也同時(shí)一下

91、把數(shù)據(jù)庫(kù)里所有的頻繁項(xiàng)都直接處理得到，因此fList里的元素基本固定，不會(huì)再有更新。</p><p>　　但是這種模型就不適合于數(shù)據(jù)流上的頻繁項(xiàng)挖掘了。數(shù)據(jù)流的特點(diǎn)是不斷高速到來(lái)大量的新數(shù)據(jù)，不可能掃描數(shù)據(jù)庫(kù)兩遍。且由于各時(shí)間對(duì)下一個(gè)時(shí)間到來(lái)的數(shù)據(jù)是無(wú)法預(yù)見(jiàn)的，譬如說(shuō)會(huì)產(chǎn)生數(shù)據(jù)漂移的問(wèn)題。上一段時(shí)間頻繁出現(xiàn)的項(xiàng)可能在下一時(shí)刻中再也不出現(xiàn)。而下一時(shí)刻則可能再出現(xiàn)新的項(xiàng)，由此fList里的元素就得進(jìn)行更新。而如果按照

92、原有的排序規(guī)則就得重新更新fList，按照新的頻度順序來(lái)更改頭表，鏈表的改動(dòng)對(duì)算法的性能有影響。</p><p>　　但實(shí)際上，這里的fList其實(shí)按不按照降序排列已經(jīng)無(wú)關(guān)緊要，同樣也是因?yàn)橛锌赡芟乱粫r(shí)刻最頻繁度一項(xiàng)就再也不出現(xiàn)，而又有新項(xiàng)加入的原因，導(dǎo)致fList的標(biāo)桿作用已經(jīng)不明顯了。其實(shí)只要求處理的記錄按照頻度降序以及數(shù)字順序來(lái)排列即可，而這在處理數(shù)據(jù)時(shí)就已經(jīng)可以做到。而實(shí)際上頻繁度的變化就是通過(guò)每一項(xiàng)的傾

93、斜時(shí)間窗口反映出來(lái)的。通過(guò)觀察窗口是否為空來(lái)判斷是否可以刪除該項(xiàng)，即判斷該項(xiàng)是否已不再頻繁了。</p><p>　　由此，我們直接將新增項(xiàng)加在頭表末項(xiàng)，而舊有在新的時(shí)段已不再頻繁的項(xiàng)也不需刪除，并且不用對(duì)每一次的更新頭表來(lái)排序，簡(jiǎn)化了一些程序的復(fù)雜度。這樣頭表就不是一個(gè)復(fù)雜的復(fù)合結(jié)構(gòu)的鏈表了，而是較為簡(jiǎn)單的鏈表形式，可以用C++標(biāo)準(zhǔn)模板庫(kù)里提供的容器類向量(vector)來(lái)表示，這是由于其自身是動(dòng)態(tài)結(jié)構(gòu)，大小不固

94、定，可以增加或減少，這也符合fList的特點(diǎn)。而對(duì)于時(shí)間的反映，就放在對(duì)傾斜時(shí)間窗口的維護(hù)上。</p><p>　　4.1.2 傾斜時(shí)間窗口維護(hù)策略</p><p>　　原文中只談到了窗口這樣一個(gè)機(jī)制來(lái)反映歷史的數(shù)據(jù)摘要信息，并給出了兩個(gè)思路。一個(gè)是簡(jiǎn)單的自然傾斜時(shí)間窗口，就是不用考慮冗余和空間復(fù)雜度，來(lái)一個(gè)新值就增加一個(gè)窗口為之存儲(chǔ)。另一種就是用到指數(shù)傾斜時(shí)間窗口，可以大大減少窗口的數(shù)量

95、。但并沒(méi)有具體的實(shí)現(xiàn)方法。經(jīng)過(guò)老師的指導(dǎo)和自己的思考，我們采用的是指數(shù)直方圖的方式來(lái)保存時(shí)間窗口。但是，本來(lái)我們并不清楚要保存到何時(shí)，因?yàn)閿?shù)據(jù)流上的流數(shù)據(jù)的到來(lái)是無(wú)限時(shí)的，因此窗口就應(yīng)該是一個(gè)可以動(dòng)態(tài)增長(zhǎng)的結(jié)構(gòu)。但這樣一來(lái)，對(duì)窗口的更新與維護(hù)就變得相當(dāng)復(fù)雜。其實(shí)，采用了指數(shù)直方圖的方式，每一個(gè)窗口保存的是摘要信息，就算保存一年的信息，也最多需要17個(gè)窗口。而真正的應(yīng)用如在對(duì)入侵檢測(cè)中的異常發(fā)現(xiàn)也不會(huì)關(guān)注很多年一起的信息。所以可以直接設(shè)窗

96、口總數(shù)為一定值，高于17即可滿足日常的挖掘需要。這樣簡(jiǎn)化了對(duì)傾斜時(shí)間窗口的更新與維護(hù)。</p><p>　　假設(shè)當(dāng)前窗口保存了在最近一刻鐘的交易。剩下的桶則由近到遠(yuǎn)分別保存的是前半小時(shí)、前一小時(shí)、前兩小時(shí)、前四小時(shí)等等。可以發(fā)現(xiàn)尺寸是以2為底數(shù)的指數(shù)倍的增長(zhǎng)。根據(jù)該模型，即使按照一刻鐘的精度來(lái)存一年的數(shù)據(jù)，我們只需要個(gè)桶來(lái)保存，而并不需要366×24×4=35136個(gè)桶那么多。指數(shù)的傾斜時(shí)間窗

97、口非常省空間。</p><p>　　正式地，我們假設(shè)交易流被分成等長(zhǎng)的批量B1,B2,…,Bn,…,Bn是最近到達(dá)的一批而B(niǎo)1是最早達(dá)到的。設(shè)i≥j，用B(i,j)來(lái)表示。對(duì)給定的項(xiàng)目集I，用f(i,j)來(lái)代表I在B(i,j)上的頻繁度。指數(shù)的傾斜時(shí)間窗口將用來(lái)存儲(chǔ)項(xiàng)目集I的頻繁度。將以下面形式來(lái)保存頻繁度：</p><p>　　f(n,n)；f(n-1,n-1)；f(n-2,n-3)；f

98、(n-4,n-7)，…</p><p>　　我們解決基本計(jì)數(shù)問(wèn)題的方法是維護(hù)直方圖，記錄最近到達(dá)的N個(gè)元素中被選中的活動(dòng)的1進(jìn)入滑動(dòng)窗口時(shí)的時(shí)間戳。我們把這個(gè)直方圖叫做指數(shù)直方圖(exponential histogram, EH)，為什么叫指數(shù)直方圖的原因讀到本文的后面就會(huì)清楚。在詳述我們的算法之前，先介紹幾個(gè)名詞。</p><p>　　圖4-1 使用的名詞和所遵循的約定的圖解</

99、p><p>　　我們將遵守圖1中的描述的約定。特別的，我們假定數(shù)據(jù)是從右邊過(guò)來(lái)的，左邊的元素是已經(jīng)過(guò)去的元素。注意，每一個(gè)元素都有一個(gè)到達(dá)時(shí)間，每到達(dá)一個(gè)元素它的到達(dá)時(shí)間就增1，最左邊的元素，也就是最先到達(dá)的元素的到達(dá)時(shí)間為1。此外，我們還需要利用時(shí)間戳(timestamp)的概念，一個(gè)活動(dòng)元素的時(shí)間戳對(duì)應(yīng)于它在當(dāng)前窗口中的位置。我們從右向左給活動(dòng)元素加上時(shí)間戳，也就是說(shuō)最近到達(dá)的元素的時(shí)間戳為1。顯然，每當(dāng)有新的元

100、素到達(dá)時(shí)，已有元素的時(shí)間戳將會(huì)改變，不過(guò)我們不希望對(duì)已有元素的時(shí)間戳做顯式的修改。一個(gè)簡(jiǎn)單的解決辦法是，用logN個(gè)二進(jìn)位循環(huán)記錄元素的到達(dá)時(shí)間，那么過(guò)去元素的時(shí)間戳就可以用元素到達(dá)時(shí)間的差得到。如前面所說(shuō)，我們把重點(diǎn)放在數(shù)據(jù)流中值為1的位上。當(dāng)我們說(shuō)第k個(gè)1時(shí)，指的是數(shù)據(jù)流中第k個(gè)最近到達(dá)的1。</p><p>　　我們利用圖1描述的狀態(tài)，來(lái)加深對(duì)這些名詞的理解。圖中的當(dāng)前時(shí)刻是49，最近到達(dá)的元素為0。到達(dá)時(shí)

101、間為48的元素是最近到達(dá)的1，這個(gè)元素的時(shí)間戳為2，因?yàn)樗钱?dāng)前窗口第2個(gè)最近到達(dá)的元素。到達(dá)時(shí)間為44的元素是第2個(gè)最近到達(dá)的1，它的時(shí)間戳為6。</p><p>　　我們將維護(hù)數(shù)據(jù)流中當(dāng)前活動(dòng)的1的直方圖。對(duì)于直方圖中的每一個(gè)桶，我們記錄它的最近到達(dá)的1的時(shí)間戳(我們把它叫做這個(gè)桶的時(shí)間戳)和桶內(nèi)1的個(gè)數(shù)(我們把它叫做桶的大小)。例如，圖1中時(shí)間戳為2大小也為2的桶表示包含了最近到達(dá)的時(shí)間戳分別為2和6的1的

102、桶。要注意的是，每當(dāng)有新的元素到達(dá)時(shí)，每個(gè)桶的時(shí)間戳都將增加，當(dāng)一個(gè)桶的時(shí)間戳超過(guò)N(到達(dá)N+1)時(shí)，我們將不再對(duì)對(duì)這個(gè)桶內(nèi)的元素感興趣，因此我們可以丟掉這個(gè)桶并回收它占用的存儲(chǔ)。如果一個(gè)桶仍然是活動(dòng)的，我們可以肯定它至少包含了一個(gè)尚未作廢的1，因而，當(dāng)前最多只有1個(gè)桶(就是最左邊的桶)包含可能已經(jīng)作廢的1。在任何時(shí)刻，我們可以用下面的方法來(lái)估算活動(dòng)的1的個(gè)數(shù)。首先，我們把當(dāng)前活動(dòng)的桶，除了最左邊的桶其余所有的桶的1的個(gè)數(shù)相加，然后，我

103、們假設(shè)最左邊的桶的1的個(gè)數(shù)為C，那么最左邊的桶內(nèi)活動(dòng)的1的精確個(gè)數(shù)可能介于1和C之間，因此我們?nèi)∷墓烙?jì)值為C/2。因此我們得到如下的事實(shí)：</p><p>　　事實(shí)1 我們用上面的方法對(duì)當(dāng)前活動(dòng)1的個(gè)數(shù)的估計(jì)值的絕對(duì)誤差最多為C/2，這里C是最左邊的活動(dòng)桶的大小。</p><p>　　下面介紹一種維護(hù)EH(指數(shù)直方圖)的技術(shù)，在后面的挖掘算法中會(huì)用到。</p><p&

104、gt;　　每當(dāng)有新的數(shù)據(jù)元素到達(dá)，我們能用O(1)的時(shí)間更新這兩個(gè)計(jì)數(shù)器。下面詳述這個(gè)更新算法：</p><p>　　ALGORITHM INSERT</p><p>　　當(dāng)有新的數(shù)據(jù)元素到達(dá)時(shí)，計(jì)算新的作廢時(shí)間。如果最后的桶的時(shí)間已經(jīng)作廢，則刪除這個(gè)桶，并更新保存最后桶的大小的計(jì)數(shù)器LAST和保存所有桶大小之和的計(jì)數(shù)器TOTAL。</p><p>　　如果新到達(dá)的

105、元素為0，什么都不干；否則，建立一個(gè)大小為1的桶，并用當(dāng)前的時(shí)間設(shè)置這個(gè)桶的時(shí)間戳，將計(jì)數(shù)器TOTAL增1。</p><p>　　從右向左遍歷所有的桶，看看是否有桶的個(gè)數(shù)超過(guò)恒不等式2的限制。如果有k/2+2個(gè)連續(xù)的桶具有相同的大小，那么就將其中的兩個(gè)桶合并為1個(gè)新桶，新桶的大小為被合并的兩個(gè)桶的大小之和，新桶的時(shí)間戳為被合并的桶中右邊的桶(也就是更近到達(dá)的)的時(shí)間戳。(將大小為2r的桶合并可能導(dǎo)致大小為2r+1