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

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

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

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

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

5、達(dá)方式提出了兩個(gè)代表性的算法，其中BorIFISM算法基于邊界集表達(dá)方式，CloIFISM算法基于閉合集表達(dá)方式。通過(guò)實(shí)驗(yàn)也表明這些算法在挖掘各種規(guī)模與特性的數(shù)據(jù)集時(shí)具有較高的效率 與可伸縮性。關(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頻繁集簡(jiǎn)化表達(dá)方式的挖掘算法 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頻繁項(xiàng)算法概述 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實(shí)驗(yàn)3.3.1實(shí)驗(yàn)數(shù)據(jù)3.3.2實(shí)驗(yàn)環(huán)境3.3.3實(shí)驗(yàn)內(nèi)容與結(jié)果30323233333.4小結(jié)第四章頻繁集簡(jiǎn)化表達(dá)方式挖掘算法 3739BorlFISM 算法理論依據(jù)404.1.2算法描述414.1.3算法的正確性45394.2 CloIFISM 算法4.2.1 算法描述 464.2.2算法的正確性53464.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

33、的數(shù)據(jù)(b)減少候選模式的數(shù)量。候選模式數(shù)量的減少可以節(jié)省處理候選模式所需的 計(jì)算時(shí)間和存儲(chǔ)空間。一般來(lái)說(shuō)，減少I/O操作和減少候選項(xiàng)目集的數(shù)量是一對(duì)矛盾，如何處理這 一對(duì)矛盾，尋找最佳的平衡點(diǎn)是提高頻繁集挖掘算法效率的關(guān)鍵。關(guān)于頻繁集挖 掘的算法很多，隨后章節(jié)中將著重介紹三類算法：完整頻繁集挖掘算法。這類算法返回完整的頻繁集。頻繁集簡(jiǎn)化表達(dá)方式的挖掘算法。這類算法的結(jié)果是頻繁集的子集，但可 以在不重新訪問(wèn)數(shù)據(jù)集的情況下生成完整的頻繁集。增量頻繁集挖掘算法。這類算法假定數(shù)據(jù)集是變化的，它在運(yùn)行過(guò)程中不僅要訪問(wèn)現(xiàn)在的數(shù)據(jù)集，也會(huì)利用以前生成的頻繁集。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代表長(zhǎng)度為i的頻繁模式，Ci代表長(zhǎng)度為i的候選模式的集合。Apriori算法的基 礎(chǔ)是頻繁模式的反單調(diào)性屬性，遵循自底向上廣度優(yōu)先的搜索策略。它首先產(chǎn)生 長(zhǎng)度為1的頻繁集L1，然后是長(zhǎng)度為2的頻繁集L2，直到有某個(gè)k值使得Lk為 空，此時(shí)算法終止。在每次循環(huán)中，首先產(chǎn)生長(zhǎng)度為k的候選集Ck, Ck中的每一個(gè)模式是由只有最后

35、一項(xiàng)不同的兩個(gè)長(zhǎng)度為k-1的頻繁模式連接來(lái)產(chǎn)生的。然后檢測(cè)Ck中的每個(gè)候選模式的長(zhǎng)度為k-1的子集是否都屬于Lk-1，如存在子集不 屬于Lk-1，則該模式必為非頻繁的，從Ck中刪除該模式。Ck中的剩余模式需要掃描數(shù)據(jù)集求得它們的支持度來(lái)決定它們是否是頻繁模式。最后的頻繁集Lk必定是Ck的一個(gè)子集。算法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í)的頻繁模式，即頻繁模式的計(jì)數(shù) 必須不小于2。因?yàn)閒的計(jì)數(shù)為1,項(xiàng)目f不是頻繁模式。L1=a(4), b,c(4), d(5), e(3)。C2=ab, ac, a

37、d, ae, bc, bd, be, cd, ce, de。因?yàn)?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。因?yàn)?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算法有兩個(gè)顯著的特點(diǎn)，一是掃描數(shù)據(jù)集的次數(shù)等于頻繁模式的最大 長(zhǎng)度；二是需要產(chǎn)生候選集。當(dāng)支持度閾值取值較小時(shí)，頻繁集中可能包含長(zhǎng)度 很大的頻繁模式，并且算法可能需要檢測(cè)大量的候選模式，此時(shí)Apriori算法的性能會(huì)顯

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

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

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

42、例，使用FP-growth算法挖掘 =0.3時(shí)的頻繁模式。(1)除f外所有的項(xiàng)目都是頻繁的。按照計(jì)數(shù)的降序排序，其次序如下：b(5)，d(5)，a，c(4)，e(3)。去掉非頻繁項(xiàng)并且排序后的示例數(shù)據(jù)集見表 2-2。表2-2排序后的示例數(shù)據(jù)集ID事務(wù)排序后頻繁項(xiàng)目1abcdebdace2bdefbde3acddac4bcdbdc5abebae6abcdbdac將每個(gè)事務(wù)中排序后的頻繁項(xiàng)插入到FP-tree,形成的結(jié)果如圖2-1所示：（3）首先挖掘e的條件子樹?？梢缘玫筋l繁模式e : 3和三個(gè)包含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對(duì)應(yīng)的條件子樹如圖2-1（因?yàn)閏的計(jì)數(shù)為1,故它不在條件子樹中出現(xiàn)）。使 用e的條件子樹可以得到頻繁模式ea： 2和兩個(gè)包含a的路徑：b： 3 , d： 2 ,a： 1和b： 3 , a： 1。則包含a的條件路徑為：b： 1 , d： 1和b： 1 , ea對(duì)應(yīng) 的條件子樹如圖2-1。使用ea的條件子樹可以得到頻繁模式eab: 2。再次使用e 的條件子樹可以得到頻繁模式ed： 2和一個(gè)包含d的路徑：b： 3 , d： 2。注意 包

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

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

46、有事務(wù)的交集。如果P=c(P)，那么P是閉合模式。如果一 個(gè)模式既是閉合的也是頻繁的，則它被稱為頻繁閉合模式。所有頻繁閉合模式的 集合被稱為頻繁閉合集，記為FC。定義2-5閉合集表達(dá)方式包含頻繁閉合集及每個(gè)頻繁閉合模式的支持度?？?以通過(guò)下面的方法來(lái)決定任意頻繁模式的支持度。定理 2-2 模式 P,如果 ZFC，ZP,那么 PF 并且 s(P)= max(s(Y)|YFCYP)， 否則PF。例2-3以表2-1中的數(shù)據(jù)集為例，給出=0.3的閉合集表達(dá)方式。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)生集表達(dá)方式定義2-6如果模式P的任意真子集的支持度都大于 P的支持度，則稱P是 產(chǎn)生模式(Generator或Free Itemset)。所有產(chǎn)生模式的集合被稱為產(chǎn)生集，記為 G。如果一個(gè)模式既是頻繁模式又是產(chǎn)生模式，則它被稱為頻繁產(chǎn)生模式。所有 頻繁產(chǎn)生模式的集合被稱為頻繁產(chǎn)生集，記為FG。所有真子集均為頻繁產(chǎn)生模式的非頻繁產(chǎn)生模式的集合稱為負(fù)產(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的一個(gè)子集丫，s(Y)=s(X)， 即包含Y的事務(wù)都包含X。記Z=(P-X)Y，Z是P的子集。因?yàn)榘?Y的事務(wù)都包 含X,所以s(Z)= s(P-X)Y)=s(P-X)X)=s(P)。這顯然與P是產(chǎn)生模式的假設(shè)相矛 盾，故X必須是產(chǎn)生模式。類似的方法可以證明定理的第二部分。僅通過(guò)頻繁產(chǎn)生集本身，無(wú)法決定一個(gè)模式是否頻繁，需要把它和邊界集結(jié) 合起來(lái)，才可以確定頻繁模式及其支持度。定義2-7產(chǎn)生集表達(dá)方式的組成包含兩部分：(a)頻繁產(chǎn)生集FG及其中每 一個(gè)模式的支持度；(

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)生集表達(dá)方式。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。無(wú)析取集表達(dá)方式定義2-8對(duì)于模式P,如果有項(xiàng)印、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對(duì)于模式P，如果可以找到基于它的確定的二元析取規(guī)則，則它被 稱為二元析取模式，否則被稱為非二元析取模式 (Disju nctio n-free Itemset)。非二元 析取模式也具有反單調(diào)性：非二元析取模式的任意子集都是非二元析取模式，二 元析取模式的任意超集都是二元析取模式。所有非二元析取模式的集

51、合被稱為非 二元析取集，記為BDFree。頻繁非二元析取集被記為 FBDFree。產(chǎn)生模式是無(wú)析取模式的特例。如果模式P是非產(chǎn)生模式，則存在項(xiàng)目a，aP，s(P-a)= s(P)，那么規(guī)則P-aa必然是確定的，P不是無(wú)析取模式。同樣， 如果P是無(wú)析取模式，那么P必然是產(chǎn)生模式。定義2-10二元無(wú)析取集表達(dá)方式BDFR的定義如下：FBDFree及其中模式的支持度；+ - FBDFreeB =XXFXBDFree(YX, YFBDFree)及其中模式的支持度；FBDFreeB-=XXF(YX, YFBDFree)。例2-5以表2-1中的數(shù)據(jù)集為例，給出=0.3的無(wú)析取集表達(dá)方式。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二元無(wú)析取集表達(dá)方式也是一種頻繁集的無(wú)損表達(dá)方式，通過(guò)舉例來(lái)說(shuō)明計(jì)算頻繁模式及其支持度的方法。判斷模式ace和abc是否頻繁并求出其中頻繁模式的支持度。因?yàn)閍ce是ce的超集，故ace不是頻繁模式。因?yàn)閍bc是bc的超集，故abc是二元析取模式。因?yàn)橐?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將無(wú)析取集表達(dá)方式和產(chǎn)生集表達(dá)方式相結(jié)合，提出了無(wú)析取產(chǎn)生 集表達(dá)方式。引入產(chǎn)生集表達(dá)方式的作用在于減少邊界集中模式的數(shù)量。2.222閉合集挖掘算法在本節(jié)介紹的算法中，Close算法源于Apriori算法，CLOSET算法源于FP- growth 算法。Close 算法基于閉合模式的思想，Pasquier提出了基于Apriori算法的Close算法12。Close算法借鑒了 Apriori算法的設(shè)計(jì)思想，采用

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

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

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

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

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

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

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