數(shù)據(jù)流頻繁集挖掘算法研究

1、電子科技大學(xué)UNIVERSITY OF ELECTRONIC SCIENCE AND TECHNOLOGY OF CHINA工程碩士學(xué)位論文ENGINEERING MASTER DISSERTATION論文題目:工程領(lǐng)域:指導(dǎo)教師:作者姓名:班學(xué)號：數(shù)據(jù)流頻繁集挖掘算法研究軟件工程盧國明教授趙傳冰200892303008分類號UDC密級學(xué)位論文數(shù)據(jù)流頻繁集挖掘算法研究趙傳冰指導(dǎo)教師姓名盧國明 教授（職務(wù)、職稱、學(xué)位、單位名稱及地址）申請學(xué)位級別工程碩士專業(yè)名稱軟件工程論文提交日期論文答辯日期學(xué)位授予單位和日期答辯委員會主席評閱人注1注明國際十進分類法UDC的類獨創(chuàng)性聲明本人聲明所呈交的學(xué)位論文

2、是本人在導(dǎo)師指導(dǎo)下進行的研究工 作及取得的研究成果。據(jù)我所知，除了文中特別加以標注和致謝的 地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不 包含為獲得電子科技大學(xué)或其它教育機構(gòu)的學(xué)位或證書而使用過的 材料。與我一同工作的同志對本研究所做的任何貢獻均已在論文中 作了明確的說明并表示謝意。簽名： 日期：年 月 日關(guān)于論文使用授權(quán)的說明本學(xué)位論文作者完全了解電子科技大學(xué)有關(guān)保留、使用學(xué)位論 文的規(guī)定，有權(quán)保留并向國家有關(guān)部門或機構(gòu)送交論文的復(fù)印件和 磁盤，允許論文被查閱和借閱。本人授權(quán)電子科技大學(xué)可以將學(xué)位 論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢索，可以采用影印、 縮印或掃描等復(fù)制手段

3、保存、匯編學(xué)位論文。（保密的學(xué)位論文在解密后應(yīng)遵守此規(guī)定）簽名：導(dǎo)師簽名：日期：年 月日摘要I摘要I摘要頻繁集挖掘是數(shù)據(jù)挖掘領(lǐng)域的一個重要的研究方向，它的研究成果已被廣泛 應(yīng)用到關(guān)聯(lián)規(guī)則挖掘、關(guān)聯(lián)分類和序列模式挖掘等許多應(yīng)用中。在過去的十幾年 間研究人員對頻繁集挖掘進行了深入廣泛的研究，取得了一系列研究成果。近年來在高速網(wǎng)絡(luò)、事務(wù)日志、金融和傳感器網(wǎng)絡(luò)等領(lǐng)域出現(xiàn)了一種稱為數(shù) 據(jù)流的新的數(shù)據(jù)類型。它具有與普通數(shù)據(jù)集截然不同的特點，如持續(xù)不斷產(chǎn)生數(shù) 據(jù)、數(shù)據(jù)產(chǎn)生速度快、數(shù)據(jù)太多以致只能順序訪問一遍數(shù)據(jù)、無法控制數(shù)據(jù)產(chǎn)生 的次序等。針對數(shù)據(jù)流的數(shù)據(jù)挖掘已經(jīng)成為研究的熱點。但因為現(xiàn)存的絕大多數(shù) 頻繁集

4、挖掘算法面向保存在持久存儲介質(zhì)中的數(shù)據(jù)并且在算法運行過程中需要多 次訪問數(shù)據(jù)，它們無法被直接應(yīng)用到數(shù)據(jù)流領(lǐng)域。本文詳細討論了基于數(shù)據(jù)流的頻繁集挖掘，提出了一系列高性能、低空間需 求和高準確度的單遍掃描算法：結(jié)合頻繁項挖掘算法，提出了兩個基于數(shù)據(jù)流中觀察到的所有數(shù)據(jù)的頻繁 集挖掘算法SinScanFISM算法和MulScanFISM算法。SinScanFISM算法逐個處理 新產(chǎn)生的事務(wù)，而MulScanFISM算法則批量處理新產(chǎn)生的事務(wù)。頻繁集挖掘算法往往會產(chǎn)生大量的頻繁模式，這不僅會影響算法的性能， 也會影響對算法結(jié)果的理解，解決方法之一就是利用頻繁集的無損簡化表達方式。結(jié)合頻繁集的無損簡化表

5、達方式提出了兩個代表性的算法，其中BorIFISM算法基于邊界集表達方式，CloIFISM算法基于閉合集表達方式。通過實驗也表明這些算法在挖掘各種規(guī)模與特性的數(shù)據(jù)集時具有較高的效率 與可伸縮性。關(guān)鍵詞：數(shù)據(jù)挖掘，SinScanFISM算法，MulScanFISM 算法，BorIFISM算法,CloIFISM 算法 # iiABSTRACTABSTRACTFrequent itemset mining is one of the important subjects of data mining, which has bee n studied exte nsively in the last

6、decade. It is used by many data mining applicati ons, such as the discovery of associati on rules, correlati ons, seque ntial rules and episodes.Recently, there has been much interest in data arriving in the form of continuous streams, which is often referred to data streams. Data streams arise in s

7、everal application domains like high-speed networking, transaction logs, finance and sensor n etworks. Data streams possessdisti net computati onal characteristics, such as unknown or unboun ded len gth, possibly very fast arrival rate, in ability to backtrack over previously arrived items (only one

8、 seque ntial pass over the data is permitted), and a lack of system con trol over the order in which the data arrive. Among the researches toward data streams, exte nding mining tech niq ues to data streams has attracted much atte nti on. However, most algorithms for frequent itemset mining have typ

9、ically been developed for datasets stored in persiste nt storage and invo Ive multiple passes over the dataset, so they cannot be directly applied to data streams.This thesis discusses the problem of freque nt itemset mi ning over data streams in detail and proposes a series of on e-pass algorithms

10、with fast update speed, low space requireme nts and accurate results.Inspired by algorithms for frequent items mining, two algorithms for frequent itemset mining over the en tire history of data streams are proposed. Sin Sca nF ISM algorithm processes new transactions one by one, and MulScanFISM alg

11、orithm processes a con siderable nu mber of tran sact ions together.The algorithms for freque nt itemset mining may gen erate a great nu mber of frequent itemsets, which may affect both the efficiency and effectiveness. One ofABTRACT iiiABTRACT #alter natives is to use con cise represe ntati on sof

12、freque nt itemsets.The paper proposes two representative algorithms, which BorlFISM algorithm is based on the generator representation and CloIFISM algorithm is based on the closed itemset representation.Extensive experimental results highlight significant gains in scalability and efficie ncy on bot

13、h sparse and dense datasets at all levels of support threshold.Key words: association rule,SinScanFISM algorithm, MulScanFISM algorithm , BorIFISM algorithm , CloIFISM algorithm目錄 目錄 TOC o 1-5 h z HYPERLINK l bookmark16 o Current Document 第一章緒論 1 HYPERLINK l bookmark18 o Current Document 1.1數(shù)據(jù)挖掘概述 1

14、 HYPERLINK l bookmark20 o Current Document 1.1.1數(shù)據(jù)挖掘的定義1 HYPERLINK l bookmark22 o Current Document 1.1.2數(shù)據(jù)挖掘的分類21.2數(shù)據(jù)流概述 31.2.1基于數(shù)據(jù)流的頻繁集算法 41.3本文的工作 51.4本文的結(jié)構(gòu) 5第二章頻繁集挖掘算法概述 72.1頻繁集挖掘的應(yīng)用 7 HYPERLINK l bookmark24 o Current Document 2.2頻繁集挖掘算法 8 HYPERLINK l bookmark26 o Current Document 2.2.1完整頻繁集挖掘算法9

15、 HYPERLINK l bookmark28 o Current Document 2.2.2頻繁集簡化表達方式的挖掘算法 14 HYPERLINK l bookmark30 o Current Document 2.2.3增量頻繁集挖掘算法 18 HYPERLINK l bookmark32 o Current Document 2.3小結(jié) 20第三章完整頻繁集挖掘算法 21 HYPERLINK l bookmark34 o Current Document 3.1頻繁項算法概述 22 HYPERLINK l bookmark36 o Current Document Lossy Coun

16、 ti ng 算法23 HYPERLINK l bookmark38 o Current Document SinScanFISM 算法24 HYPERLINK l bookmark40 o Current Document MulScanFISM 算法273.2 CP-tree 3.3實驗3.3.1實驗數(shù)據(jù)3.3.2實驗環(huán)境3.3.3實驗內(nèi)容與結(jié)果30323233333.4小結(jié)第四章頻繁集簡化表達方式挖掘算法 3739BorlFISM 算法理論依據(jù)404.1.2算法描述414.1.3算法的正確性45394.2 CloIFISM 算法4.2.1 算法描述 464.2.2算法的正確性53464.

17、3實驗534.4小結(jié)第五章總結(jié)和展望5657參考文獻59第一章緒論 電子科技大學(xué)工程碩士學(xué)位論文 第一章緒論1.1數(shù)據(jù)挖掘概述最近幾十年，隨著科學(xué)技術(shù)的迅猛發(fā)展和信息技術(shù)的廣泛應(yīng)用，人類產(chǎn)生數(shù) 據(jù)和獲取數(shù)據(jù)的能力迅速提高，從制造業(yè)到服務(wù)業(yè)，從生物研究到空間探索，無 時無刻不在產(chǎn)生著大量數(shù)據(jù)。與這種現(xiàn)象相對應(yīng)的是，人類處理和分析數(shù)據(jù)的能 力卻相當(dāng)有限?；ヂ?lián)網(wǎng)的興起更加加劇了數(shù)據(jù)爆炸，知識匱乏”這一趨勢。數(shù)據(jù)挖掘作為新一代的、智能輔助人類從海量數(shù)據(jù)中發(fā)現(xiàn)有用知識的技術(shù)正是在這種 背景下產(chǎn)生并迅速發(fā)展起來，成為了知識發(fā)現(xiàn)的一個重要的研究領(lǐng)域。數(shù)據(jù)挖掘是統(tǒng)計分析、數(shù)據(jù)可視化、人工智能、機器學(xué)習(xí)、高性能

18、計算和數(shù) 據(jù)庫技術(shù)等眾多領(lǐng)域交叉形成的新興學(xué)科，在市場營銷、金融預(yù)測和決策支持等 領(lǐng)域具有廣泛的應(yīng)用前景。1.1.1數(shù)據(jù)挖掘的定義數(shù)據(jù)挖掘，又稱為數(shù)據(jù)庫中知識發(fā)現(xiàn) （Knowledge Discovery in Database，簡稱KDD），是指一個從大量的數(shù)據(jù)中提取出未知的、潛在有用的、可理解的模式的 高級過程。其中：數(shù)據(jù)：是用來描述事物的信息，是進一步發(fā)現(xiàn)知識的基礎(chǔ)。未知：經(jīng)過數(shù)據(jù)挖掘提取出的模式必須是新穎的。潛在有用：提取出的模式應(yīng)該是有意義的，可以用某些標準來衡量?？杀蝗死斫猓簲?shù)據(jù)集中隱含的模式要以容易被人理解的形式表現(xiàn)出來，從而幫助人們更好地理解數(shù)據(jù)中所包含的信息。高級過程：一個多

19、步驟的處理過程，多步驟之間相互影響、反復(fù)調(diào)整，形成一種螺旋式上升過程。數(shù)據(jù)挖掘是對數(shù)據(jù)進行更深層次處理的過程， 而不僅僅對數(shù)據(jù)進行加減求和等簡單運算或查詢，因此說它是一個高級 的過程。1.1.2數(shù)據(jù)挖掘的分類數(shù)據(jù)挖掘通過關(guān)聯(lián)分析、分類分析、聚類分析、異常性分析、趨勢分析等知 識發(fā)現(xiàn)活動，尋找頻繁模式、關(guān)聯(lián)規(guī)則、分類規(guī)則、聚類模式、異常模式、周期 性規(guī)律等類型的知識。關(guān)聯(lián)分析關(guān)聯(lián)規(guī)則反映了數(shù)據(jù)中對象之間依賴或關(guān)聯(lián)的知識。關(guān)聯(lián)規(guī)則挖掘的一個典 型應(yīng)用是零售業(yè)，比如超市的銷售管理。關(guān)聯(lián)規(guī)則可辨別商品之間是否存在某種 關(guān)聯(lián)關(guān)系。例如， 購買了商品A和B的顧客中有90%的人又購買了商品C和D就是 一條關(guān)

20、聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則提供的信息可以用作設(shè)計商品銷售目錄、商場布置、市 場營銷的參考。關(guān)聯(lián)規(guī)則是基于數(shù)據(jù)項目的同時出現(xiàn)特征，不是基于數(shù)據(jù)自身的固有屬性（例如函數(shù)依賴關(guān)系），不能通過數(shù)據(jù)庫的邏輯操作（如表的聯(lián)接）或統(tǒng)計的方法得出。分類分析和估值分析分類從數(shù)據(jù)中發(fā)現(xiàn)對象的共性，并將對象分成不同種類。在分類中，一個其 中元組的種類都已知的樣本數(shù)據(jù)集被當(dāng)作訓(xùn)練集。分類的目標首先是對訓(xùn)練數(shù)據(jù) 進行分析，使用數(shù)據(jù)的某些特征屬性，給出每個類的準確描述，然后使用這些描 述，對其它數(shù)據(jù)進行分類。估值與分類類似，不同之處在于分類描述離散型變 量，估值會產(chǎn)生連續(xù)值的輸出。常用的方法有決策樹歸納、貝葉斯分類、神經(jīng)網(wǎng) 絡(luò)、K

21、-最臨近分類、粗糙集、關(guān)聯(lián)分類和遺傳算法等。聚類分析聚類是指將對象分成若干類對象，在每類對象內(nèi)部，對象之間具有較高的相 似性，而在不同類的對象之間，相似性則比較低。它與分類不同，聚類事先不知 道對象所屬的類。在數(shù)據(jù)挖掘中，聚類也是一個活躍的研究領(lǐng)域。聚類算法可以 分為基于劃分的方法、層次方法、基于密度的方法、基于網(wǎng)格的方法和基于模型 的方法。4數(shù)據(jù)概括數(shù)據(jù)概括是把數(shù)據(jù)集從較低概念層次抽象到較高概念層次的過程。通常數(shù)據(jù) 集中的數(shù)據(jù)是比較具體和詳細的。但在某些應(yīng)用中，用戶需要在更高的抽象級別 上分析數(shù)據(jù)，這就要進行一定的抽象化即數(shù)據(jù)概括。12數(shù)據(jù)流概述伴隨著計算機技術(shù)的日新月異，數(shù)據(jù)管理技術(shù)發(fā)展迅

22、速并且得到了廣泛應(yīng) 用。一方面，出現(xiàn)了多種數(shù)據(jù)管理模型，從層次數(shù)據(jù)庫、網(wǎng)狀數(shù)據(jù)庫、關(guān)系數(shù)據(jù) 庫、對象數(shù)據(jù)庫，直到關(guān)系對象數(shù)據(jù)庫等；另一方面，數(shù)據(jù)量也越來越大，很多 大型數(shù)據(jù)庫的容量已經(jīng)達到甚至超出了 TB級。這些數(shù)據(jù)管理技術(shù)的一個共同點 是：據(jù)存儲在輔助存儲介質(zhì)中，可以多次訪問。在上世紀末，一種新的數(shù)據(jù)類型 的出現(xiàn)卻對已有的數(shù)據(jù)管理模型提出了有力的挑戰(zhàn)。在網(wǎng)絡(luò)通信、金融、科學(xué)觀 察、電信等領(lǐng)域中，如網(wǎng)絡(luò)監(jiān)聽和流量控制、股票的價格預(yù)測、傳感器網(wǎng)絡(luò)、電 話通信等應(yīng)用，數(shù)據(jù)以流的形式產(chǎn)生，實時的、連續(xù)的、有序的數(shù)據(jù)不斷到達， 沒有終點。這種一系列連續(xù)且有序的數(shù)據(jù)組成的序列被稱為數(shù)據(jù)流。區(qū)別于傳統(tǒng)數(shù)據(jù)

23、類型，數(shù)據(jù)流具有以下特點：數(shù)據(jù)流中的數(shù)據(jù)可能隨時到達，無法預(yù)測數(shù)據(jù)到達的時間；無法控制數(shù)據(jù)項到達的次序，其次序是隨機的；不限制數(shù)據(jù)量的大小，可以認為其是無限的；數(shù)據(jù)一經(jīng)處理，通常不能被再次訪問，再次提取數(shù)據(jù)代價昂貴。大多數(shù)數(shù)據(jù)挖掘算法的設(shè)計都基于兩個基本假設(shè)。其一，在數(shù)據(jù)挖掘過程 中，數(shù)據(jù)集是靜態(tài)的。無論是否有新數(shù)據(jù)產(chǎn)生或者部分數(shù)據(jù)失效，數(shù)據(jù)挖掘使用 的是挖掘過程開始時的數(shù)據(jù)集的一個快照。其二，執(zhí)行環(huán)境總是能為算法運行提 供足夠的資源。算法可以不受限制多次訪問數(shù)據(jù)，隨時可以得到足夠的內(nèi)存和執(zhí) 行能力。但對于數(shù)據(jù)流，這兩個假設(shè)都不成立，因而絕大多數(shù)數(shù)據(jù)挖掘算法都無 法直接應(yīng)用到數(shù)據(jù)流領(lǐng)域。雖然不

24、可能將數(shù)據(jù)流產(chǎn)生的數(shù)據(jù)全部保存在內(nèi)存中， 但是可以通過建立保存在內(nèi)存中的數(shù)據(jù)摘要提供給數(shù)據(jù)流算法訪問已處理數(shù)據(jù)的 能力。盡管數(shù)據(jù)摘要通常無法保證處理的準確性，但可以保證結(jié)果的實時性。設(shè) 計單遍掃描數(shù)據(jù)的算法，建立有效的數(shù)據(jù)摘要，實時地給出近似結(jié)果就成為數(shù)據(jù) 流模型下數(shù)據(jù)挖掘的目標5-9。1.2.1基于數(shù)據(jù)流的頻繁集算法頻繁集挖掘首先由10提出，它是很多其它挖掘問題的基礎(chǔ)。隨著產(chǎn)生數(shù)據(jù) 流的應(yīng)用不斷增多，基于數(shù)據(jù)流的頻繁集挖掘也得到越來越多的關(guān)注。區(qū)別于傳 統(tǒng)的靜態(tài)數(shù)據(jù)，數(shù)據(jù)流具有連續(xù)性、無序性、無界性及實時性的特點，通常要求 算法能夠及時地反映數(shù)據(jù)變化。已有的基于數(shù)據(jù)流的頻繁集挖掘算法可分為兩

25、 類：批處理方法和啟發(fā)式方法。批處理方法的主要思想是將數(shù)據(jù)流中的數(shù)據(jù)按照 產(chǎn)生的次序分成不同的部分，通過不同部分上的局部頻繁模式來計算全局頻繁模 式。批處理方法雖然處理速度較快，但需要積攢足夠數(shù)據(jù)，在一定程度上損害了 結(jié)果的實時性。啟發(fā)式方法的主要思想是隨著數(shù)據(jù)的不斷到達，由已知頻繁模式 逐步生成新的頻繁模式。啟發(fā)式方法能夠隨數(shù)據(jù)的到達直接進行處理，可以實時 地反映頻繁模式的變化，但由于其處理速度有限，在處理限高速到達的數(shù)據(jù)流時 存在困難，而且模式計數(shù)通常不包含歷史信息使得模式估計與查詢精度較低?；?于普通數(shù)據(jù)集的頻繁集挖掘已經(jīng)是一個相對成熟的研究領(lǐng)域，而基于數(shù)據(jù)流的頻 繁集挖掘仍然存在許多尚

26、待解決之處。目前該研究方向存在的主要問題有：數(shù)據(jù)流挖掘算法通常返回近似結(jié)果，因而需要一個衡量算法準確性的標準。目前尚不存在這樣一個標準，致使無從比較算法之間的優(yōu)劣。雖然普通數(shù)據(jù)集挖掘算法和數(shù)據(jù)流挖掘算法存在很多不同之處，但是普通 數(shù)據(jù)集挖掘算法的很多研究成果仍然可以應(yīng)用到數(shù)據(jù)流領(lǐng)域，在該方面的所做工 作遠遠不夠。提出的算法往往有一定的限制條件，沒有提出完整的解決方案。本文系統(tǒng) 地研究了基于數(shù)據(jù)流的頻繁集挖掘問題，提出了一系列高時間效率、低空間需求 的算法。1.3本文的工作本文中論述的內(nèi)容大體可以分為兩部分：挖掘完整頻繁集的算法，包括逐個處理事務(wù)的Sin Sea nFISM算法和批量處理事務(wù)的M

27、ulSea nFISM算法。Sin Sea nFISM算法使用了延遲加入顯著模式的方 法，有效地減少了顯著模式的數(shù)量；而MulSeanFISM算法則隨著批量處理的事務(wù)數(shù)量的增多，新加入的顯著模式在隨后的更新過程中被刪除的概率則會變小。挖掘頻繁集簡化表達方式的算法，包括挖掘帶有邊界集的簡化表達方式的BorIFISM 算法和挖掘閉合集表達方式的CloIFISM 算法。BorIFISM 算法首次將邊界集和產(chǎn)生集表達方式結(jié)合在一起，避免在更新過程中產(chǎn)生過多的候選模式； CloIFISM算法則提出使用模式的支持度來尋找閉合模式的方法，支持搜索空間的 有效剪裁。第四章的研究成果是基于頻繁集簡化表達方式的增

28、量挖掘算法的系統(tǒng) 總結(jié)，其成果不僅僅是適用于數(shù)據(jù)流，也適用于普通數(shù)據(jù)集。1.4本文的結(jié)構(gòu)在第二章全面地介紹了頻繁集的理論和主要算法。著重介紹了三類算法：完整頻繁集的挖掘算法、頻繁集簡化表達方式的挖掘算法和增量頻繁集挖掘算法。在第三章中討論了挖掘基于數(shù)據(jù)流已處理過的所有數(shù)據(jù)的完整頻繁集的算 法。該章引入了顯著模式和顯著集的概念，使得有了一個量化的標準去衡量算法 的準確性；其次提出了逐條處理新產(chǎn)生事務(wù)的SinScanFISM算法和批量處理新產(chǎn)生事務(wù)的MulScanFISM算法。在第四章中介紹了頻繁集的簡化表達方式在數(shù)據(jù)流中的應(yīng)用。頻繁集的簡化 表達方式可分為兩類：帶有邊界集的表達方式和閉合集表達方

29、式。與它們相對 應(yīng)，提出了 BorlFISM算法和CloIFISM算法。最后一章回顧了本文的主要工作，闡述了本文的創(chuàng)新之處，指出了進一步研 究的方向。第二章頻繁集挖掘算法概述 電子科技大學(xué)工程碩士學(xué)位論文 第二章頻繁集挖掘算法概述定義2-1給定項目集l=ii, i2,，im，其中ik(1求命)是一個項目。I的非 空子集被稱為模式。一個模式所包含的項目數(shù)被稱為該模式的長度。長度為k的模式可簡寫為k-模式。定義2-2事務(wù)是I的非空子集，每個事務(wù)都有唯一的標志符。數(shù)據(jù)集 D是一 組事務(wù)的集合，即 D=Ti, T2,，Tn , Tkl(1來奪)。數(shù)據(jù)集的大小即為數(shù)據(jù)集 中包含的事務(wù)的數(shù)量，記為|D|。

30、定義2-3數(shù)據(jù)集D中包含模式P的事務(wù)的數(shù)量稱為在 D中P的計數(shù)，記為 發(fā)fD(P)或簡寫為f(P)。數(shù)據(jù)集D中包含模式P的事務(wù)在所有事務(wù)中所占的比例稱 為在D中P的支持度，記為sd(P)或簡寫為s(P)。顯然s(P)=f(P)/|D|。假定(0 是事先設(shè)定的支持度閾值，如果s(P)青則稱P是頻繁模式。所有頻繁模 式的集合稱為頻繁集，記為F。定理2-1頻繁模式具有反單調(diào)性，即頻繁模式的子集是頻繁的；非頻繁模式 的超集是非頻繁的。證明：結(jié)論是顯而易見的。2.1頻繁集挖掘的應(yīng)用頻繁集挖掘是數(shù)據(jù)挖掘的一個重要研究領(lǐng)域，頻繁集可以用來解決其它數(shù)據(jù) 挖掘問題。關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則是如下形式的邏輯蘊涵：XY,其

31、中XI, YI并且XY=。通常采用兩個標準來衡量關(guān)聯(lián)規(guī)則：(1)支持度，即s(XY)，表明在數(shù)據(jù)集中事務(wù)同時包含模 式X和丫的概率；(2)置信度，即s(XY)/s(X)，表明在包含模式X的事務(wù)包含模式Y(jié)的概率。同時滿足支持度閾值和最小置信度的規(guī)則稱為強規(guī)則。關(guān)聯(lián)規(guī)則挖掘 問題實際上就是產(chǎn)生強規(guī)則的問題。關(guān)聯(lián)規(guī)則挖掘問題一般可以分為兩個步驟：找出數(shù)據(jù)集中所有的頻繁模式的集合；(2)根據(jù)頻繁模式，產(chǎn)生所有強關(guān)聯(lián)規(guī)則。由于關(guān)聯(lián)規(guī)則挖掘算法的性能主要由第一步的性能決定，所以目前對關(guān)聯(lián)規(guī) 則算法的研究主要集中在頻繁集挖掘算法上。關(guān)聯(lián)分類關(guān)聯(lián)分類實際上是關(guān)聯(lián)規(guī)則的一個特殊應(yīng)用。對于關(guān)聯(lián)規(guī)則XY,如果丫是類

32、標識，該規(guī)則可以用于數(shù)據(jù)分類。序列模式給定一個序列數(shù)據(jù)集，它記錄了多個數(shù)據(jù)序列，每個序列由若干按時間排序 的事務(wù)組成，每個事務(wù)由若干項目組成。序列模式是在序列數(shù)據(jù)集中出現(xiàn)次數(shù)超 過預(yù)先設(shè)定值的模式序列，其組成的基本元素就是頻繁模式。2.2頻繁集挖掘算法從1994年Agrawal等人10提出第一個頻繁集挖掘算法到現(xiàn)在，關(guān)于頻繁集挖掘算法的研究已經(jīng)有了突飛猛進的發(fā)展。從時間復(fù)雜度和空間復(fù)雜度來考慮，提高頻繁集挖掘算法的性能的手段主要有兩種：(a)減少I/O操作。被挖掘的數(shù)據(jù)集通常包含大量的數(shù)據(jù)，頻繁的 I/O操作必將增加算法的運行時間。減少I/O操作主要是減少掃描數(shù)據(jù)集的次數(shù)和掃描數(shù)據(jù)集時需要訪問

33、的數(shù)據(jù)(b)減少候選模式的數(shù)量。候選模式數(shù)量的減少可以節(jié)省處理候選模式所需的 計算時間和存儲空間。一般來說，減少I/O操作和減少候選項目集的數(shù)量是一對矛盾，如何處理這 一對矛盾，尋找最佳的平衡點是提高頻繁集挖掘算法效率的關(guān)鍵。關(guān)于頻繁集挖 掘的算法很多，隨后章節(jié)中將著重介紹三類算法：完整頻繁集挖掘算法。這類算法返回完整的頻繁集。頻繁集簡化表達方式的挖掘算法。這類算法的結(jié)果是頻繁集的子集，但可 以在不重新訪問數(shù)據(jù)集的情況下生成完整的頻繁集。增量頻繁集挖掘算法。這類算法假定數(shù)據(jù)集是變化的，它在運行過程中不僅要訪問現(xiàn)在的數(shù)據(jù)集，也會利用以前生成的頻繁集。2.2.1完整頻繁集挖掘算法本節(jié)概括介紹了一系

34、列完整頻繁集挖掘算法，其中最具代表性的算法是Apriori 算法和 FP-growth 算法。Apriori 算法Apriori算法是Agrawal等人于1994年提出的關(guān)聯(lián)規(guī)則挖掘算法5，是關(guān) 聯(lián)規(guī)則挖掘的經(jīng)典算法。Apriori算法中產(chǎn)生頻繁集的偽代碼見算法2-1。其中L代表長度為i的頻繁模式，Ci代表長度為i的候選模式的集合。Apriori算法的基 礎(chǔ)是頻繁模式的反單調(diào)性屬性，遵循自底向上廣度優(yōu)先的搜索策略。它首先產(chǎn)生 長度為1的頻繁集L1，然后是長度為2的頻繁集L2，直到有某個k值使得Lk為 空，此時算法終止。在每次循環(huán)中，首先產(chǎn)生長度為k的候選集Ck, Ck中的每一個模式是由只有最后

35、一項不同的兩個長度為k-1的頻繁模式連接來產(chǎn)生的。然后檢測Ck中的每個候選模式的長度為k-1的子集是否都屬于Lk-1，如存在子集不 屬于Lk-1，則該模式必為非頻繁的，從Ck中刪除該模式。Ck中的剩余模式需要掃描數(shù)據(jù)集求得它們的支持度來決定它們是否是頻繁模式。最后的頻繁集Lk必定是Ck的一個子集。算法2-1 Apriori算法In put: and DOutput: FL1=freque nt 1-itemsetsFor (k=2; L k-1; k+)Ck=Apriori-Gen( Lk-1)/新的候選集For each TDFor each PCkIf PT Then /檢查事務(wù)中是否包含

36、候選模式f(P)=f(P)+1Lk= P|PCkf(P)|D|F=kLkApriori-Ge n= Ck=P1P2P1, P2Lk-1P1.item1= P2.item1P1.itemic2 P2.itemk-2P1.itemk-1 P2.itemk-1For each PCkFor each (k-1)-subset S of PIf SLk-1 thendelete P from Ck例2-1以表2-1中數(shù)據(jù)集為例，挖掘=0.3時的頻繁模式，即頻繁模式的計數(shù) 必須不小于2。因為f的計數(shù)為1,項目f不是頻繁模式。L1=a(4), b,c(4), d(5), e(3)。C2=ab, ac, a

37、d, ae, bc, bd, be, cd, ce, de。因為 f(ce)=1, ce 被從 C2 中刪除。L2=ab(3), ac(3), ad(3), ae(2) , bc(3), bd,be(3), cd, de(2)。C3=abc, abd, abe , acd , bcd , bde。 C3 中的所有模式都是頻繁的。L3= abc(2) , abd(2) , abe(2) , acd(3) , bcd(3) , bde(2)。C4= abcd , abde。因為 f(abd=1, abde被從 C4 中刪除。L4=abcd(2)。C5=,算法終止。F=L1L2L3L4=a(4),

38、b(5) , c(4), d(5) , e(3), ab(3) , ac(3) , ad(3) , ae(2),bc(3), bd(4), be(3), cd,de(2), abc(2), abd(2), abe(2), acd(3), bed(3), bde(2), abcd(2)。表2-1示例數(shù)據(jù)集ID事務(wù)1abcde2bdef3acd4bcd5abe6abcdApriori算法有兩個顯著的特點，一是掃描數(shù)據(jù)集的次數(shù)等于頻繁模式的最大 長度；二是需要產(chǎn)生候選集。當(dāng)支持度閾值取值較小時，頻繁集中可能包含長度 很大的頻繁模式，并且算法可能需要檢測大量的候選模式，此時Apriori算法的性能會顯

39、著降低。在Apriori算法公布之后，很多人在該算法的基礎(chǔ)上作了進一步的 研究。FP-Growth 算法Han等人提出了一種全新的頻繁集挖掘算法 FP-Growth11，克服了 Apriori 算法必須產(chǎn)生候選集的缺點，提出了一種基于 FP-tree的無候選集的新方法。FP- Growth算法的特點體現(xiàn)在兩個方面：它利用了一種緊湊的數(shù)據(jù)結(jié)構(gòu)FP-tree,存儲了模式的計數(shù)信息。FP-tree結(jié) 構(gòu)包括一個由頻繁項組成的表與一個根節(jié)點標識為“n ull和其它節(jié)點為頻繁項的樹。表中的每條記錄包含兩個域：項和指針。指針指向樹中第一個同項目同名的 節(jié)點。樹中的每個節(jié)點包括三個域：項目名、計數(shù)和節(jié)點鏈接

40、。其中項目名記錄 了節(jié)點所代表的項目；計數(shù)記錄了樹中到達這個節(jié)點的路徑所代表的事務(wù)的數(shù)目；節(jié)點鏈接指向樹中下一個同名節(jié)點，如果沒有同名節(jié)點則指向空。支持度高 的節(jié)點靠近數(shù)的根節(jié)點，從而支持度高的模式比支持度低的模式更可能共享同一 個節(jié)點。注意FP-tree中只保存了滿足支持度閾值的項目。所以，首先需要對數(shù) 據(jù)集進行第一次掃描得出滿足支持度閾值的項并將它們按降序排列在FP-tree結(jié)構(gòu)的表中，然后對數(shù)據(jù)集進行第二次掃描，對每個事務(wù)處理中包含的頻繁項按照 其在表中的先后順序插入到樹中。它使用了基于FP-tree的模式片斷成長算法，首先處理葉節(jié)點，從長度為1的頻繁模式開始，從包含它的分枝生成條件子樹

41、，并且在子樹中遞歸挖掘，模式 的成長通過結(jié)合條件子樹中產(chǎn)生的后綴模式來實現(xiàn)。挖掘過程中采用了分而治之 (Divide and Conquer)的方法，而不是 Apriori算法中自底向上的方法，它將發(fā)現(xiàn) 長頻繁模式的問題轉(zhuǎn)化為尋找短模式再進行連接，避免了產(chǎn)生長候選模式。FP-Growth算法的主要問題是：在挖掘頻繁模式時，它需要遞歸地生成條件FP樹，并且每產(chǎn)生一個頻繁模式就可能生成一個條件FP樹。在支持度閾值較小或處理密集數(shù)據(jù)集時，即使對于很小的數(shù)據(jù)集，也會產(chǎn)生大量的頻繁模式，這 時FP-Growth算法可能需要動態(tài)生成和釋放大量的條件子樹，將耗費大量時間和 空間。例2-2以表2-1中數(shù)據(jù)集為

42、例，使用FP-growth算法挖掘 =0.3時的頻繁模式。(1)除f外所有的項目都是頻繁的。按照計數(shù)的降序排序，其次序如下：b(5)，d(5)，a，c(4)，e(3)。去掉非頻繁項并且排序后的示例數(shù)據(jù)集見表 2-2。表2-2排序后的示例數(shù)據(jù)集ID事務(wù)排序后頻繁項目1abcdebdace2bdefbde3acddac4bcdbdc5abebae6abcdbdac將每個事務(wù)中排序后的頻繁項插入到FP-tree,形成的結(jié)果如圖2-1所示：（3）首先挖掘e的條件子樹?？梢缘玫筋l繁模式e : 3和三個包含e的路徑：b： 5, d： 4, a： 2, c： 2, e： 1, b： 5, d： 4, e：

43、1 , b: 5, a： 1, e： 1。則包 含 e 的條件路徑為：b： 1, d： 1, a： 1, c： 1, b： 1, d： 1, b： 1, a：1, e對應(yīng)的條件子樹如圖2-1（因為c的計數(shù)為1,故它不在條件子樹中出現(xiàn)）。使 用e的條件子樹可以得到頻繁模式ea： 2和兩個包含a的路徑：b： 3 , d： 2 ,a： 1和b： 3 , a： 1。則包含a的條件路徑為：b： 1 , d： 1和b： 1 , ea對應(yīng) 的條件子樹如圖2-1。使用ea的條件子樹可以得到頻繁模式eab: 2。再次使用e 的條件子樹可以得到頻繁模式ed： 2和一個包含d的路徑：b： 3 , d： 2。注意 包

44、含a的節(jié)點無需再考慮了，因為已經(jīng)得到了包含 ea的頻繁模式。則包含d的條件 路徑為：b： 2 , ed對應(yīng)的條件子樹如圖2-1。利用該子樹得到頻繁模式edb：2。最后使用e的條件子樹還可以得到頻繁模式eb： 3。（4）接著利用FP-tree挖 掘c的條件子樹。注意此時無需考慮FP-tree中包含e的節(jié)點。隨后利用FP-tree依次挖掘a , d , b的子樹。其具體的過程可參考步驟3roof;IMrecO血創(chuàng)b b:2OtfWt圖2-1FP-Growth算法的運算過程2.2.2頻繁集簡化表達方式的挖掘算法因為數(shù)據(jù)集中模式的數(shù)目和項目的數(shù)量成指數(shù)關(guān)系，算法可能產(chǎn)生大量的頻 繁模式，這不僅嚴重影響

45、算法的效率，也會影響對結(jié)果的理解。人們提出了多種 簡化表達方式來取代頻繁集。在介紹的幾種無損簡化表達方式中，關(guān)于閉合集表 達方式和最大集表達方式的挖掘算法的研究最為充分。2.2.2.1頻繁集簡化表達方式概述無損簡化表達方式將是介紹的重點。所謂無損簡化表達方式，是指可以重新 生成整個頻繁集并給出每個頻繁模式的準確支持度的簡化表達方式。它們主要有 閉合集表達方式12,13、產(chǎn)生集表達方式14和無析取集表達方式15等。閉合集表達方式定義2-4如果模式P的任何真超集的支持度都小于 P的支持度，則稱P是閉 合模式。P的閉包，c(P)，定義為包含P的長度最小的閉合模式。實際上c(P)就是數(shù)據(jù)集中包含P的所

46、有事務(wù)的交集。如果P=c(P)，那么P是閉合模式。如果一 個模式既是閉合的也是頻繁的，則它被稱為頻繁閉合模式。所有頻繁閉合模式的 集合被稱為頻繁閉合集，記為FC。定義2-5閉合集表達方式包含頻繁閉合集及每個頻繁閉合模式的支持度?？?以通過下面的方法來決定任意頻繁模式的支持度。定理 2-2 模式 P,如果 ZFC，ZP,那么 PF 并且 s(P)= max(s(Y)|YFCYP)， 否則PF。例2-3以表2-1中的數(shù)據(jù)集為例，給出=0.3的閉合集表達方式。FC=a(4)， b(5)，d(5)，ab(3)，bd，be(3)，cd(4)，abe(2)，acd(3)，bcd(3)，bde(2)， ab

47、cd(2)。產(chǎn)生集表達方式定義2-6如果模式P的任意真子集的支持度都大于 P的支持度，則稱P是 產(chǎn)生模式(Generator或Free Itemset)。所有產(chǎn)生模式的集合被稱為產(chǎn)生集，記為 G。如果一個模式既是頻繁模式又是產(chǎn)生模式，則它被稱為頻繁產(chǎn)生模式。所有 頻繁產(chǎn)生模式的集合被稱為頻繁產(chǎn)生集，記為FG。所有真子集均為頻繁產(chǎn)生模式的非頻繁產(chǎn)生模式的集合稱為負產(chǎn)生邊界集，記為GB-，即卩GB-=X|XGXF(YX,YFG)。產(chǎn)生模式同頻繁模式一樣，也具有反單調(diào)性。產(chǎn)生模式和頻繁模式結(jié)合 在一起，可以有效地減少候選集的數(shù)量。定理2-3產(chǎn)生模式的任意子集都是產(chǎn)生模式；非產(chǎn)生模式的任意超集都是非

48、產(chǎn)生模式。證明：先用反證法證明定理的第一部分。假定 P是產(chǎn)生模式，X是P的子集 但X不是產(chǎn)生模式。則根據(jù)產(chǎn)生模式的定義存在 X的一個子集丫，s(Y)=s(X)， 即包含Y的事務(wù)都包含X。記Z=(P-X)Y，Z是P的子集。因為包含 Y的事務(wù)都包 含X,所以s(Z)= s(P-X)Y)=s(P-X)X)=s(P)。這顯然與P是產(chǎn)生模式的假設(shè)相矛 盾，故X必須是產(chǎn)生模式。類似的方法可以證明定理的第二部分。僅通過頻繁產(chǎn)生集本身，無法決定一個模式是否頻繁，需要把它和邊界集結(jié) 合起來，才可以確定頻繁模式及其支持度。定義2-7產(chǎn)生集表達方式的組成包含兩部分：(a)頻繁產(chǎn)生集FG及其中每 一個模式的支持度；(

49、b) GB-=XG|XF(YX，YFG)。定理2-4模式P，如果ZGB-并且ZX，那么PF ;否則，PF并且 s(P)=min(s(丫)|YFGYX)。例2-4以表2-1中的數(shù)據(jù)集為例，給出 =0.3的產(chǎn)生集表達方式。FG=a(4)，b(5)，c(4)，d(5)，e(3)，ab(3)，ac(3)，ad(3)，ae(2)，bc(3)，bd，de(2), abc(2)，abd(2)，GB-=(ade，ce。無析取集表達方式定義2-8對于模式P,如果有項印、a2和模式X，并且XP和P-X=a1，a2，則規(guī)則Xaia2被稱為基于P的二元析取規(guī)則。其中 X可以為空或者ai等于 a2。該規(guī)則的支持度被定義

50、為包含X和ai或者X和a2的事務(wù)的數(shù)量，s(Xaia2)=s(Xai)+s(Xa2)-s(Xaia2)，它的可信度定義為conf(Xaia2)=s(Xaia2)/s(X)。如果規(guī)則的可信度等于1,則該規(guī)則被稱為確定的。Xaia2是確定規(guī)則意味著包含 X的事務(wù)必然或者包含ai或者包含a2。定義2-9對于模式P，如果可以找到基于它的確定的二元析取規(guī)則，則它被 稱為二元析取模式，否則被稱為非二元析取模式 (Disju nctio n-free Itemset)。非二元 析取模式也具有反單調(diào)性：非二元析取模式的任意子集都是非二元析取模式，二 元析取模式的任意超集都是二元析取模式。所有非二元析取模式的集

51、合被稱為非 二元析取集，記為BDFree。頻繁非二元析取集被記為 FBDFree。產(chǎn)生模式是無析取模式的特例。如果模式P是非產(chǎn)生模式，則存在項目a，aP，s(P-a)= s(P)，那么規(guī)則P-aa必然是確定的，P不是無析取模式。同樣， 如果P是無析取模式，那么P必然是產(chǎn)生模式。定義2-10二元無析取集表達方式BDFR的定義如下：FBDFree及其中模式的支持度；+ - FBDFreeB =XXFXBDFree(YX, YFBDFree)及其中模式的支持度；FBDFreeB-=XXF(YX, YFBDFree)。例2-5以表2-1中的數(shù)據(jù)集為例，給出=0.3的無析取集表達方式。FBDFree=a

52、(4)，b(5)，c(4)，d(5)，e(3)，ab(3)，ac(3)，ae(2)，+FBDFreeB =ad(3)，bc(3)，bd(4), be(3)，cd(4)，de(2)，F(xiàn)BDFreeB-= ce。例2-6二元無析取集表達方式也是一種頻繁集的無損表達方式，通過舉例來說明計算頻繁模式及其支持度的方法。判斷模式ace和abc是否頻繁并求出其中頻繁模式的支持度。因為ace是ce的超集，故ace不是頻繁模式。因為abc是bc的超集，故abc是二元析取模式。因為規(guī)則be是確定的，則 規(guī)則 abc也是確定的，s(a)=s(a bc)。由 s(abc)=s(ab)+s(ac)-s(abc)可以得到

53、 s(a bc)= s(ab)+s(ac)-s(abc)，貝U s(abc)=s(ab)+s(ac)-s(a bc)= s(ab)+s(ac)-s(a)=(3+3- 4)/6=1/3。83將無析取集表達方式和產(chǎn)生集表達方式相結(jié)合，提出了無析取產(chǎn)生 集表達方式。引入產(chǎn)生集表達方式的作用在于減少邊界集中模式的數(shù)量。2.222閉合集挖掘算法在本節(jié)介紹的算法中，Close算法源于Apriori算法，CLOSET算法源于FP- growth 算法。Close 算法基于閉合模式的思想，Pasquier提出了基于Apriori算法的Close算法12。Close算法借鑒了 Apriori算法的設(shè)計思想，采用

54、自底向上廣度優(yōu)先的搜索策略。 長度為k+l的頻繁產(chǎn)生模式是從長度為 k的頻繁產(chǎn)生模式進行連接得到的長度為 k+1的候選集中得到的。Close算法在生成長度為k的頻繁產(chǎn)生集之后就掃描數(shù)據(jù) 集求得它們的閉包，從而得到對應(yīng)的閉合模式。Close算法掃描數(shù)據(jù)集的次數(shù)和候選集中模式的個數(shù)一般要少于Apriori算法。CLOSET 算法Pei等人提出了挖掘頻繁閉合集CLOSET算法13。CLOSET算法基于FP-Growth算法，但它對條件子樹的生成做了針對性的修改，通過額外檢查步驟去掉 了那些不是閉合模式的頻繁模式。另外，它提出了分割FP-tree的方法來處理大型數(shù)據(jù)集。它和FP-Growth算法有同樣

55、的缺點，可能需要構(gòu)造大量的條件子 樹。CHARM 算法CHARM算法16是Zaki等提出基于垂直數(shù)據(jù)表達方式的深度優(yōu)先算法。CHARM使用了一種新穎的樹結(jié)構(gòu)一IT(ltemset-Tidset)樹。結(jié)點表示成Xt(X),X代 表模式，t(X)是包含模式X的事務(wù)標識符的集合。節(jié)點 X的子節(jié)點為Xht(Xh)，Xl2t(Xl2),，Xlnt(Xln),其中Ik為某一項目。實際上 CHARM 算法就是對IT樹 的深度優(yōu)先遍歷。在遍歷過程中，算法利用下面的性質(zhì)裁減IT樹。對于兩個不同的模式X、丫，如果t(X)=t(Y),那么c(X)=c(Y)=c(XY)，用XY代替X,刪除代表丫的節(jié)點及子 樹；如果t

56、(X)t(Y)，那么c(X)c(Y)并且c(X)=c(XY)，可用XY替代X,但不刪除代表 丫的節(jié)點；如果t(Y)t(X)，那么c(X)c(Y)并且c(Y)=c(XY)，刪除代表丫的節(jié)點及子樹；如果t(X)t(Y),那么c(X)c(Y)并且c(X)=c(XY)，既不能裁剪分枝，也不能減少 子樹的高度。CHARM算法在執(zhí)行過程中按支持度的升序來重新排列候選模式，以求盡早 刪除非頻繁模式。2.2.3增量頻繁集挖掘算法在現(xiàn)實生活中恒定不變的數(shù)據(jù)是很少存在的，數(shù)據(jù)總是處在不斷的變化過程 中。當(dāng)數(shù)據(jù)發(fā)生變化時，以前的計算結(jié)果便會失效，如果想再次得到頻繁集，可 以重新運行頻繁集挖掘算法來得到結(jié)果，但這樣做

57、沒有充分利用已有的結(jié)果，因 為數(shù)據(jù)的更新往往只會導(dǎo)致小部分頻繁模式發(fā)生變化。因而人們提出了增量頻繁 集挖掘，可以利用已有的計算結(jié)果來生成新的頻繁集。為簡化表述，假定D為原有的數(shù)據(jù)集，d+是新增事務(wù)的集合，d-是刪除的事務(wù)的集合，N是更新后的數(shù)據(jù) 集，即N=D+d+-d-。對于修改的數(shù)據(jù)可以視為刪除原有事務(wù)后再增加一個新事務(wù)。FUP算法Cheung等人首先引入了增量關(guān)聯(lián)規(guī)則挖掘，提出了處理新增數(shù)據(jù)4+的FUP算法17。FUP算法遵循Apriori算法的設(shè)計思想，按照自頂向下廣度優(yōu)先的策 略計算頻繁集。每一次循環(huán)都需要掃描整個數(shù)據(jù)集一次，掃描數(shù)據(jù)集的次數(shù)和最大的頻繁模式的長度相同。在每次循環(huán)中，F(xiàn)

58、UP算法與Apriori算法的主要不同體現(xiàn)在以下三個方面：掃描數(shù)據(jù)集d+，計算原有數(shù)據(jù)集D中長度為k的頻繁集(LJd中的各模式在數(shù)據(jù)集d沖的支持度，結(jié)合已有的支持度，計算在N中(LJd中模式的支持度。如果其中模式的支持度大于，就將它加入 N上的頻繁集(LQn。在完成以上步驟的同時，計算集合(Ck)N-(L0D中模式在d+中的支持度。(CQn是使用和Apriori算法中Apriori_Gen方法相同的方法從(L中得到的。)如 果其中模式的支持度不大于，則將其從集合中刪除；掃描數(shù)據(jù)集D，計算(Ck)N-(L0D中剩余模式在D中的支持度，結(jié)合(b)的結(jié) 果，求得在N上的支持度，將頻繁模式加入(LQn

59、。保證FUP算法正確性的依據(jù)是如果在 N中模式是頻繁的，那么它或者在D中是頻繁的或者在d+中它是頻繁的。2邊界集算法Thomas等人提出了基于邊界集的增量挖掘算法18，算法不僅維護頻繁集， 而且也維護邊界集。邊界集包含所有子集為頻繁模式的非頻繁模式。這兩個算法 大體可以分為兩個步驟：(1)檢測階段。掃描d+，確定原來的頻繁集Ld中的模式在N上是否仍然是頻 繁的；檢測邊界集中是否包含在N上的頻繁模式。如果邊界集中不包含頻繁模式，說明新增數(shù)據(jù)不會引入任何頻繁集。這是因為任何新引入的頻繁模式或者屬 于邊界集或者它的某個真子集屬于邊界集。更新階段。刪除Ld中的非頻繁模式，利用邊界集中的頻繁模式生成頻繁

60、 模式的候選集，在遍歷數(shù)據(jù)集后將其中的頻繁模式加入N的頻繁集Ln。2.3小結(jié)本章系統(tǒng)介紹了頻繁集挖掘的理論和主要算法，著重闡述了三類算法： 完整頻繁集挖掘算法。主要介紹了Apriori算法和FP-growth算法以及它 們的改進算法。頻繁集簡化表達方式的挖掘算法。著重介紹了閉合集表達方式挖掘算法。增量頻繁集挖掘算法。概括介紹了 FUP等算法。第三章完整頻繁集挖掘算法 電子科技大學(xué)工程碩士學(xué)位論文 第三章完整頻繁集挖掘算法隨著數(shù)據(jù)流中新數(shù)據(jù)的不斷產(chǎn)生，一個當(dāng)前的非頻繁模式可能在將來變成頻 繁模式，因此如果想得到一個準確的頻繁集，任何在數(shù)據(jù)流中出現(xiàn)的模式以及它 的支持度都應(yīng)該被記錄下來。但是模式的