1、基于Apriori算法的關聯規則挖掘系統    摘    要 隨著信息時代的發展，信息量呈幾何級數增長，人們發現從這些海量信息中獲取有用的信息越來越 困難，要找出信息背后隱藏的規律更是不可想象。數據挖掘就是從大量數據中獲取有用信息的一門 新技術，關聯規則挖掘是數據挖掘方法中的一種。本文詳細論述了基于Apriori算法的關聯規則挖 掘系統的設計開發過程。系統基于經典的Apriori算法，對事務數據庫進行了位圖矩陣轉換，大大 提高了搜索效率，并能分別挖掘頻繁項集和關聯規則。 論文組織如下：首先介紹了數據挖掘的產生、定義和應用；接

2、著闡述了關聯規則挖掘的基本概念； 然后對系統的需求進行了分析，并提出設計方案；緊接著是系統的具體實現；最后對系統進行了測 試，將系統用于挖掘中藥方劑庫中的藥對藥組，驗證了系統的正確性和實用性。 關鍵詞：數據挖掘；關聯規則；Apriori算法 目錄 論文總頁數：27頁 1引言 1 2數據挖掘概述 1 2.1數據挖掘的產生 1 2.2數據挖掘的定義 1 2.3 數據挖掘的應用 4 3關聯規則挖掘 4 3.1基本概念 4 3.2購物籃分析 5 3.3Apriori經典算法 6 4需求分析和設計方案 8

3、 4.1需求分析 8 4.2設計方案 8 5基于Apriori算法的關聯規則挖掘系統 10 5.1數據挖掘在中藥方劑研究中的應用 10 5.2基于Apriori算法的關聯規則挖掘系統的實現 11 5.2.1連接數據庫 11 5.2.2位圖矩陣的建立 11 5.2.3頻繁項集 13 5.2.4關聯規則 14 6系統測試 19 6.1系統的使用 19 6.2對顯示數據的解釋 22 6.3分析 23 結    論 24 參考文獻&#

4、160;24 致    謝 26 聲    明 27   3.2購物籃分析 先看看購物籃分析，這是一個引發關聯規則挖掘的典型例子。 例1 超市的經理想了解顧客的購物習慣。例如，想知道“哪些商品組合常常被顧客同時購買？”為 回答這一問題，可以在超市的事務數據庫上運行購物籃分析。分析結果可以幫助超市經理設計不同 的商品布局。一種策略是：將經常一塊購買的商品放近一些，以便進一步刺激這些商品一起銷售。 例如，如果顧客購買牛奶也傾向于同時購買面包，那么將牛奶和面包擺放得近一點，可能有助于增 加二者的銷售。另一種策略

5、是：將牛奶和面包分別放在超市的進、出口，可能誘發買這些商品的顧 客一路挑選其他商品。例如，顧客在買了牛奶之后，去找面包，路上看到水果，可能會決定也買一 些水果。購物籃分析也可以幫助超市規劃什么商品降價出售。如果顧客趨向于同時購買數字彩電和 DVD機，數字彩電降價出售可能既促使購買數字彩電，又促使購買DVD機。 想象全域是超市中可利用的商品的集合，則每種商品有一個布爾變量，表示該商品的有無。每個籃 子則可用一個布爾向量表示。可以分析布爾向量，得到反映商品頻繁關聯或同時購買的購買模式。 這些模式可以用關聯規則的形式表示。例如，購買牛奶也趨向于同時購買面包可以用以下關聯規則 表示：  牛奶

6、Þ面包  support= 2% ,confidence= 60% 規則的支持度和置信度是兩個規則興趣度度量，它們分別反映發現規則的有用性和確定性。上一條 關聯規則的支持度2%意味分析中的全部事務的 2%同時購買牛奶和面包。置信度60%意味購買牛奶的 顧客60%也購買面包。如果關聯規則滿足最小支持度閾值和最小置信度閾值，則被認為是有趣的。 這些閾值可以由用戶或領域專家設定。 3.3Apriori經典算法 下面介紹形式最簡單的關聯規則挖掘方法。這種關聯規則是單維、單層、布爾關聯規則，如前面討 論的購物籃分析。 關聯規則的挖掘分兩步： 1) 找出所有頻繁項集：根據定義，這些項集

7、出現的頻繁性至少和預定義的最小支持計數一樣。 2) 由頻繁項集產生強關聯規則：根據定義，這些規則必須滿足最小支持度和最小置信度。 也可以使用附加的興趣度度量。這兩步中，第二步最容易。挖掘關聯規則的總體性能由第一步決定 。 Apriori算法是一種最有影響的挖掘布爾關聯規則頻繁項集的算法。算法的名字基于頻繁項集性質 的先驗知識，正如我們將看到的。Apriori使用逐層搜索的迭代方法，k-項集用于探索(k+1)-項集 。首先，找出頻繁1-項集的集合。該集合記作L1。L1用于找頻繁2-項集的集合L2，而L2用于找L3， 如此下去，直到不能找到頻繁 k-項集。找每個Lk需要一次數據庫掃描。 為提高頻繁

8、項集逐層產生的效率，一種稱作Apriori性質的重要性質用于壓縮搜索空間。我們先介 紹該性質，然后用一個例子解釋它的使用。 Apriori性質：頻繁項集的所有非空子集都必須也是頻繁的。Apriori性質基于如下觀察：根據定義 ，如果項集I不滿足最小支持度閾值min_sup，則I不是頻繁的，即P(I)<min_sup。如果項A添加到I ，則結果項集（即IA）不可能比I更頻繁出現。因此，IA也不是頻繁的，即P(IA)<min_sup。 該性質屬于一種特殊的分類，稱作反單調(anti-monotone)，意指如果一個集合不能通過測試，則 它的所有超集也都不能通過相同的測試。稱它為反單調，

9、是因為在通不過測試的意義下，該性質是 單調的。 “如何將Apriori性質用于算法？”為理解這一點，我們必須看看如何用Lk找Lk-1。下面的兩步過 程由連接和剪枝組成。 (1) 連接步：為找Lk ，通過Lk-1 與自己連接產生候選k-項集的集合。該候選項集的集合記作Ck。 設l1和l2是Lk-1中的項集。記號lij表示li的第j項（例如，l1k- 2 表示l1的倒數第3項）。為 方便計，假定事務或項集中的項按字典次序排序。執行連接Lk1Lk1 ，其中Lk1的元素是可 連接的，如果它們前(k- 2 )個項相同。即是，L k1的元素l1和l2是可連接的，如果(l¬11 = l21)(l1

10、2 =l2 2) . . . (l1k-2= l2k-2)(l1k-1< l2k-1 )。條件(l1k- 1< l2k-1 )是簡單地保證不產生重復。連接l1和l2產生的結果項集是l11 l22. l1k- 1 l2k- 1 。 (2) 剪枝步：Ck是Lk的超集；即是，它的成員可以是也可以不是頻繁的，但所有的頻繁k-項集都包 含在Ck中。掃描數據庫，確定Ck中每個候選的計數，從而確定Lk（即根據定義，計數值不小于最小 支持度計數的所有候選是頻繁的，從而屬于Lk）。然而，Ck可能很大，這樣所涉及的計算量就很大 。為壓縮Ck，可以用以下辦法使用 Apriori性質：任何非頻繁的 (k-

11、1)-項集都不可能是頻繁的， 從而可以由Ck中刪除。這種子集測試可以使用所有頻繁項集的散列樹快速完成。 下面的Apriori算法是Agrawal R提出來的： 算法1：Apriori使用根據候選生成的逐層迭代找出頻繁項集。 輸入：事務數據庫D；最小支持度閾值min_sup。 輸出：D中的頻繁項集L。 方法： 1)     L1= find_frequent_1-itemsets(D) ; 2)     for (k = 2; Lk-1 ; k+) 3)     &#

12、160;   Ck= aproiri_gen(Lk-1 ,min_sup) ; 4)         for each transaction tD /scan D for counts 5)              Ct = subset(Ck , t); /get the subsets of t 6)     

13、         for each candidate cCt 7)                  c.count+; 8)         9)         Lk= cC | c.

14、count min_sup 10)    11)    return  L = kLk; procedure apriori_gen(Lk-1:frequent(k-1)-itemsets;        min_sup:minimum support threshold) 1)     for each itemset l1Lk-1 2)      

15、60; for each itemset l2 Lk-1 3)           if (l11=l21)(l12=l22). . .(l1k-2 =l2k-2)       (l1 k-1<l2k-1)   then  4)              c = l1l2

16、;     /join step: generate candidates 5)              if  has_infrequent_subset(c,Lk-1 )  then 6)                delete c;  /

17、 prune step: remove unfruitful cadidate 7)              else add c to Ck ; 8)           9)    return Ck ; procedure has_infrequent_subset(c:candidate k-itemset;  

18、60;      L :frequent (k- 1 )- itemset )/ use prior knowledge 1)    for each (k-1)-subset s of c 2)          if  s Lk-1 then 3)                return TRUE ; 4)     return FALSE; 如上所述，Apriori_gen做兩個動作：連接和剪枝。在連接部分，Lk與Lk-1連接產生可能的候選（ 第1-4步）。剪枝部分（第5-7步）使用Apriori性質刪除具有非頻繁子集的候選。非頻繁子集的測 試在過程has_infrequent_subset中。 一旦由數據庫D中的事務找出頻繁項集，由它們產生強關聯規則是直接了當的（強關聯規則滿最小 支持度和最小置信度）。對于置信度，可以用下式，其中條件概率用項集支持