基于垂直格式的頻繁項集挖掘算法研究.pdf

1、長春工業(yè)大學(xué)碩士學(xué)位論文摘要頻繁項集的挖掘技術(shù)在如今的數(shù)據(jù)“爆炸”時代，有著越來越重要的地位，它是解決實際問題的一種非常重要的手段。很多學(xué)者在最近20年中提出了許多有關(guān)挖掘頻繁項集的相關(guān)算法以用來解決生產(chǎn)中的實際問題。但隨著我們的數(shù)據(jù)量級呈幾何倍增增長，我們對頻繁項集挖掘算法的執(zhí)行效率越來越重視。。本文首先把有關(guān)頻繁項集的國內(nèi)外的研究成果進行了匯總，并對這些研究成果進行了深入的分析。并且著重分析了基于水平數(shù)據(jù)格式的Apriori算法和F

2、P—growth算法，以及基于垂直數(shù)據(jù)格式的Eclat算法相關(guān)理論、實現(xiàn)流程以及在時間性能和空間性能的具體情況。之后比較了每一個算法的優(yōu)、缺點，這么做的目的是為了提出性能更高效的算法做好充分的理論儲備。本文是在結(jié)合這些研究成果的一些優(yōu)點的基礎(chǔ)上，提出了一種基于垂直格式的數(shù)據(jù)存儲形式基礎(chǔ)上全新的頻繁挖掘算法——FDSL算法(FrequentDeepSearchList)。該算法通過把水平數(shù)據(jù)結(jié)構(gòu)變成一種有序的垂直數(shù)據(jù)存儲結(jié)構(gòu)，并根據(jù)這個結(jié)

3、構(gòu)構(gòu)建了相應(yīng)地搜索bitmap，通過掃描這個bitmap，構(gòu)造出一個有序搜索列表，然后利用深度優(yōu)先查找策略，對這個有序的搜索列表進行深度搜索，這樣就可以同時生成候選集以及候選集的支持度。這樣在O(n)時間復(fù)雜度下利用上述搜索策略就可以生成相應(yīng)的頻繁項集。為了證明本文提出的FDSL算法的性能，本文使用C編程語言分別實現(xiàn)了Apriori算法、Ecalt算法以及FDSL算法，并選用等長和不等長兩種不同的數(shù)據(jù)格式的數(shù)據(jù)集對上述三種頻繁項集挖掘算

4、法進行了充分的比較并獲得了大量實驗數(shù)據(jù)。實驗結(jié)果表明，本文提出的算法在與傳統(tǒng)的基于水平格式的Apriori算法以及垂直格式的Eclat算法在不同的支持度閾值上進行了充分的比較后發(fā)現(xiàn)，本文提出的算法(FDSL)在時間性能上相對于其他算法優(yōu)勢還是比較明顯。關(guān)鍵詞：垂直格式有序搜索列表深度搜索bitmapFDSL長春工業(yè)大學(xué)碩士學(xué)位論文目錄摘要IAbstractII第一章緒論l11研究背景112研究的意義和目的113本文的主要創(chuàng)新成果214本

5、文的結(jié)構(gòu)安排2第二章數(shù)據(jù)挖掘概述42i數(shù)據(jù)挖掘的背景422數(shù)據(jù)挖掘的定義423關(guān)聯(lián)規(guī)則挖掘技術(shù)5231關(guān)聯(lián)規(guī)則的基本概念5232關(guān)聯(lián)規(guī)則的挖掘步驟6233關(guān)聯(lián)規(guī)則評估性能的方法624有關(guān)頻繁挖掘領(lǐng)域的國內(nèi)外研究的現(xiàn)狀725本章小結(jié)8第三章頻繁項集挖掘的經(jīng)典算法931頻繁項集挖掘算法的分類932基于水平格式的頻繁挖掘算法9321Apriori算法9322FP—growth算法1l33基于垂直格式的頻繁挖掘算法1433本章小結(jié)17第四章基于