【摘要】

計算機技術和通信技術的迅猛發展將人類社會帶入到了信息時代。在最近十幾年里，數據庫中存儲的數據急劇增大。例如，NASA軌道衛星上的地球觀測系統EOS每小時會向地面發回50GB的圖像數據；世界上最大的數據倉庫之一，美國零售商系統Wal-Mart每天會產生2億左右的交易數據；人類基因組數據庫項目已經搜集了數以GB計的人類基因編碼數據；大型天文望遠鏡每年會產生不少于10TB的數據，等等。大量的信息在給人們提供方便的同時也帶來了一系列問題，由于信息量過大，超出人們掌握、理解信息的能力，因而給正確運用信息帶來了困難。

數據挖掘和知識發現是一個涉及多學科的研究領域。數據庫技術、人工智能、機器學習、統計學、粗糙集、模糊集、神經網絡、模式識別、知識庫系統、高性能計算、數據可視化等均與數據挖掘相關。

近年來，KDD（即與數據庫的知識發現）研究領域已經成為熱點，其中關聯規則數據挖掘算法尤為引人注目。關聯規則反映一個事物與其他事物之間的相互依存性和關聯性。

IBM公司Almaden研究中心的R.Agrawal首先提出關聯規則模型，并給出求解算法AIS。隨后又出現了SETM和Apriori等算法。Apriori是關聯規則模型中的經典算法。

關鍵詞：數據挖掘 知識發現 Apriori算法 FP算法

一、問題重述

1.1相關信息

Apriori算法在發現關聯規則領域具有很大影響力。算法命名源于算法使用了頻繁項集性質的先驗（prior）知識。在具體實驗時，Apriori算法將發現關聯規則的過程分為兩個步驟：第一步通過迭代，檢索出事務數據庫中的所有頻繁項集，即支持度不低于用戶設定的閾值的項集；第二步利用頻繁項集構造出滿足用戶最小信任度的規則。其中，挖掘或識別出所有頻繁項集是該算法的核心，占整個計算量的大部分。

在對深度優先數據挖掘算法的研究工作中，Han等人沒有采用潛在頻繁項集的方法求解頻繁項集，而是提出了稱為頻率模式增長（FP_growth）的算法。該算法通過掃描數據庫創建FP_tree的根節點并標示為null，對數據庫D中的每一個事務Tran，按L中的次序對Tran中的頻繁項排序，設Tran中排序后的頻繁項列表[p|P]，這里p是第一個元素，P是保留列表。接著調用函數insert_tree（[p|P]，T），如果樹T有一個子節點N且N.item_name=p.item_name，就將N節點計數加1；否則就創建一個新節點N，設計數為1，它的父節點連接到T，節點連接到同名的節點連接結構上。如果P是非空的，就遞歸調用insert_tree（P，N）。由于壓縮了數據庫內容，并且在將頻繁項寫入FP_tree結構時，保留了項集間的相連信息。求解頻繁項集的問題，就轉化為遞歸地找出最短頻繁模式并連接其后綴構成長頻繁模式的問題。[1]

1.2問題重述

近年來，KDD（即與數據庫的知識發現）研究領域已經成為熱點，其中關聯規則數據挖掘算法尤為引人注目。關聯規則反映一個事物與其他事物之間的相互依存性和關聯性。

IBM公司Almaden研究中心的R.Agrawal首先提出關聯規則模型，并給出求解算法AIS。隨后又出現了SETM和Apriori等算法。Apriori是關聯規則模型中的經典算法。[1]

1、分析Apriori算法與FP算法的優缺點

2、分別使用兩種算法找出頻繁項集

3、挖掘出所有的強關聯規則

4、實驗數據如下表:

二、模型求解

2—頻繁項集的強關聯

Confidence(A=>B)=P(B|A)=P(AB)/P(A)=3/4=0.75

Confidence(B=>A)=P(A|B)=P(AB)/P(B)=3/3=1

Confidence(A=>C)=P(C|A)=P(AC)/P(A)=4/4=1

Confidence(C=>A)=P(C|A)=P(AC)/P(C)=4/4=1

Confidencd(B=>C)=P(C|B)=P(BC)/P(B)=3/3=1

Confidence(C=>B)=P(B|C)=P(BC)/P(C)=3/4=0.75

在滿足minconf = 80%的前提下，結果為：B=>A；A=>C；C=>A;B=>C

3—頻繁項集的強關聯

Confidencd(AB=>C)=P(ABC)/P(AB)=3/3=1

Confidencd(AC=>B)=P(ABC)/P(AC)=3/4=0.75

Confidence(BC=>A)=P(ABC)/P(BC)=3/3=1

在滿足minconf = 80%的前提下，結果為：AB=>C；BC=>A

利用FP一樹算法求頻繁項集

Procedure FP_growth（Tree，a）

（1） ifTree包含一個單一路徑P then

（2） ??for each 路徑P中節點組合（記為β）

（3） ????生成模式β∪α，擁有支持度為β節點中的最小支持度

（4） Else for each樹的頭列表節點αi{

（5） ???生成模式β=αi∪β且support=ai.support

（6） ???構成β的條件模式基和β的條件FP_Treeβ

（7） ???IfTreeβ≠фthen

（8） ?????Call FP_growth（Treeβ，β）；}[1]

FP-Tree算法使用頻繁模式增長方法，第一次掃描與Apriori相同，它導出頻繁項(1-項集)的集合，并得到它們的支持度計數(頻繁性)。設最小支持度計數為2.頻繁項的集合按支持度計數的遞減序排序。結果集或表記作L，這樣，我們有L={A:4,C:4,B:3}。

圖為存放壓縮的頻繁模式信息的FP_tree：

三、模型評價

Apriori算法時間消耗的主要癥結反映在兩個方面，一是由于對海量數據庫的多趟掃描，另一個是用JOIN產生潛在頻繁項集。

FP-Tree結構在完備性方面，它不會打破交易中的任何模式，而且包含了挖掘序列模式所需的全部信息；在緊密性方面，它不剔除不相關信息，不包含非頻繁項，按支持度降序排列，支持度高的項在FP-Tree中共享的機會也高。

性能研究顯示FP-growth比Apriori快一個數量級，這是由于FP-growth不生成候選集，不用候選集測試，而且使用緊縮的數據結構，避免重復數據庫掃描。[1]

四、參考文獻

[1] 李雄飛 李軍，《數據挖掘與知識發現》，北京：高等教育出版社，2003。

總結

以上是生活随笔為你收集整理的数据挖掘实验报告-关联规则算法实验的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。