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

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

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

4、-tree的啟發(fā)，創(chuàng)造了一個可以在數(shù)據(jù)流上進行有效挖掘的數(shù)據(jù)結(jié)構(gòu)FP-stream。一個FP-stream結(jié)構(gòu)包含(a)一個可捕捉頻繁項和次頻繁項的內(nèi)存中的頻繁樹，(b)每一個頻繁項都有的傾斜時間窗口表。構(gòu)建、更新和維護該結(jié)構(gòu)實現(xiàn)了在數(shù)據(jù)流上的挖掘。分析和實驗證明了其性能。最后對未來的研究方向進行了展望。</p><p>　　關(guān)鍵詞: 數(shù)據(jù)流； 頻繁項； 流數(shù)據(jù)挖掘； FP-stream算法； 傾斜時間窗口；&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ù)流挖掘算法和特點5</p><p>　　2.3 數(shù)據(jù)流挖掘的關(guān)鍵問題6</p><p>　　2.4 本章小結(jié)8</p><p>　　第三章 頻繁項挖掘及相關(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ù)流上頻繁項挖掘算法14</p><p>　　4.1 改進的FP-stream算

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

12、m結(jié)構(gòu)20</p><p>　　4.3 對FP-stream的更新和維護22</p><p>　　第五章 改進的FP-stream算法實現(xiàn)23</p><p>　　5.1 FP-tree的構(gòu)建23</p><p>　　5.2 FP-tree的更新25</p><p>　　5.3 分析和評價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é)束語32</b></p><p><b>　　致 謝33</b></p><

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

47、了最重要的信息，但是丟棄了非頻繁項集的計數(shù)和將來有可能成為頻繁項集的項集。可以看到，為了收集更多的資源來獲得更精確的結(jié)果就會使用更多的內(nèi)存空間和需要更多的處理時間。這就 需 要 一個有效的壓縮的數(shù)據(jù)結(jié)構(gòu)來存儲更新和檢索收集的信息。由于有限的內(nèi)存空間和巨大的數(shù)據(jù)流連續(xù)不斷的到來。不能建立這樣一種數(shù)據(jù)結(jié)構(gòu)將會很大程度的降低挖掘算法。因為即使我們在磁盤上存儲了這些信息，附加的I/O操作將會增加處理時間。由于巨大的數(shù)據(jù)量不可能重新掃描整個輸入數(shù)

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

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

50、項集。如果我們只在數(shù)據(jù)結(jié)構(gòu)中存儲頻繁項集的計數(shù)，當我們需要一些潛在的、稍后變?yōu)轭l繁項集的非頻繁項集的計數(shù)時，我們得不到這些信息。因此需要考慮處理概念漂移的技術(shù)。</p><p>　　滑動窗口技術(shù)能夠針對窗口大小的數(shù)據(jù)流進行挖掘，不會受到以前挖掘結(jié)果的影響。FP-stream算法中在頻繁模式樹中嵌入時間窗口，可以挖掘不同時間粒度的頻繁項集。 Slinding Window方法挖掘滑動窗口中的頻繁項集。在設(shè)計針對數(shù)據(jù)

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

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

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

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

55、壓縮的數(shù)據(jù)結(jié)構(gòu)、計算高效的一遍掃描算法、概念漂移、自適應(yīng)性等關(guā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ù)挖掘的思路，說明了數(shù)據(jù)流挖掘在側(cè)重點上有哪些變化。</p><p>　　第三章 頻繁項挖掘及相關(guān)算法</p><p>　　頻繁項挖掘作為關(guān)聯(lián)規(guī)則挖掘的基礎(chǔ)，一直是數(shù)據(jù)挖掘領(lǐng)域的重點。其中FP-growth算法是較為有效的一種挖掘算法</p&

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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