由啤酒和尿布引出：

在一家超市中，人們發現了一個特別有趣的現象：尿布與啤酒這兩種風馬牛不相及的商品居然擺在一起。但這一奇怪的舉措居然使尿布和啤酒的稍量大幅增加了。這可不是一個笑話，而是一直被商家所津津樂道的發生在美國沃爾瑪連鎖超市的真實案例。原來，美國的婦女通常在家照顧孩子，所以她們經常會囑咐丈夫在下班回家的路上為孩子買尿布，而丈夫在買尿布的同時又會順手購買自己愛喝的啤酒。這個發現為商家帶來了大量的利潤，但是如何從浩如煙海卻又雜亂無章的數據中，發現啤酒和尿布銷售之間的聯系呢？這又給了我們什么樣的啟示呢？這是怎么做到的呢，這就是數據的挖掘，需要對數據之間的關聯規則進行分析，進行購物籃分析。

Apriori算法是一種挖掘關聯規則的頻繁項集算法，其核心思想是通過候選集生成和情節的向下封閉檢測兩個階段來挖掘頻繁項集。而且算法已經被廣泛的應用到商業、網絡安全等各個領域。

Apriori算法是一種最有影響的挖掘布爾關聯規則頻繁項集的算法。很多的的挖掘算法是在Apriori算法的基礎上進行改進的，比如基于散列（Hash）的方法，基于數據分割（Partition）的方法以及不產生候選項集的FP-GROWTH方法等。因此要了解關聯規則算法不得不先要了解Apriori算法。

Apriori算法是一種最有影響的挖掘布爾關聯規則頻繁項集的算法。其核心是基于兩階段頻集思想的遞推算法。該關聯規則在分類上屬于單維、單層、布爾關聯規則。在這里，所有支持度大于最小支持度的項集稱為頻繁項集，簡稱頻集。可能產生大量的候選集,以及可能需要重復掃描數據庫，是Apriori算法的兩大缺點

頻繁項集:

項的集合稱為項集。包含k個項的項集稱為k-項集。集合{computer,ativirus_software}是一個二項集。項集的出項頻率是包含項集的事務數，簡稱為項集的頻率，支持度計數或計數。注意，定義項集的支持度有時稱為相對支持度，而出現的頻率稱為絕對支持度。如果項集I的相對支持度滿足預定義的最小支持度閾值，則I是頻繁項集。

布爾關聯規則:

關聯規則是形如X→Y的蘊涵式，其中且， X和Y分別稱為關聯規則的先導(antecedent或left-hand-side, LHS)和后繼(consequent或right-hand-side, RHS) 。

定義

根據韓家煒等觀點，關聯規則定義為： 假設I是項的集合。給定一個交易數據庫D，其中每個事務(Transaction)t是I的非空子集，即，每一個交易都與一個唯一的標識符TID(Transaction ID)對應。關聯規則在D中的支持度(support)是D中事務同時包含X、Y的百分比，即概率；置信度(confidence)是D中事物已經包含X的情況下，包含Y的百分比，即條件概率。如果滿足最小支持度閾值和最小置信度閾值。這些閾值是根據挖掘需要人為設定。 基本概念表1：關聯規則的簡單例子

TID	網球拍	網 球	運動鞋	羽毛球
1	1	1	1	0
2	1	1	0	0
3	1	0	0	0
4	1	0	1	0
5	0	1	1	1
6	1	1	0	0

用一個簡單的例子說明。表1是顧客購買記錄的數據庫D，包含6個事務。項集I={網球拍,網球,運動鞋,羽毛球}。考慮關聯規則（頻繁二項集）：網球拍與網球，事務1,2,3,4,6包含網球拍，事務1,2,6同時包含網球拍和網球，X^Y=3, D=6，支持度(X^Y)/D=0.5；X=5, 置信度(X^Y)/X=0.6。若給定最小支持度α = 0.5，最小置信度β = 0.6，認為購買網球拍和購買網球之間存在關聯。 來自：百度百科 關聯規則

1．?挖掘關聯規則

1.1???什么是關聯規則

一言蔽之，關聯規則是形如X→Y的蘊涵式，表示通過X可以推導“得到”Y，其中X和Y分別稱為關聯規則的先導(antecedent或left-hand-side, LHS)和后繼(consequent或right-hand-side, RHS)

1.2???如何量化關聯規則

關聯規則挖掘的一個典型例子便是購物車分析。通過關聯規則挖掘能夠發現顧客放入購物車中的不同商品之間的關聯，分析顧客的消費習慣。這種關聯規則的方向能夠幫助賣家了解哪些商品被顧客頻繁購買，從而幫助他們開發更好的營銷策略。比如：將經常同時購買的商品擺近一些，以便進一步刺激這些商品一起銷售；或者，將兩件經常同時購買的商品擺遠一點，這樣可能誘發買這兩件商品的用戶一路挑選其他商品。

在數據挖掘當中，通常用“支持度”（support）和“置性度”（confidence）兩個概念來量化事物之間的關聯規則。它們分別反映所發現規則的有用性和確定性。

對于A->B

①支持度：P(A ∩ B)，既有A又有B的概率

②置信度：

P(B|A)，在A發生的事件中同時發生B的概率 p(AB)/P(A) ? ? 例如購物籃分析：牛奶 ? 面包

例子：[支持度：3%，置信度：40%]

支持度3%：意味著3%顧客同時購買牛奶和面包

置信度40%：意味著購買牛奶的顧客40%也購買面包

比如：

Computer => antivirus_software ,?其中?support=2%, confidence=60%

表示的意思是所有的商品交易中有2%的顧客同時買了電腦和殺毒軟件，并且購買電腦的顧客中有60%也購買了殺毒軟件。在關聯規則的挖掘過程中，通常會設定最小支持度閾值和最小置性度閾值，如果某條關聯規則滿足最小支持度閾值和最小置性度閾值，則認為該規則可以給用戶帶來感興趣的信息。

1.3???關聯規則挖掘過程

1）幾個基本概念：

關聯規則A->B的支持度support=P(AB)，指的是事件A和事件B同時發生的概率。

置信度confidence=P(B|A)=P(AB)/P(A),指的是發生事件A的基礎上發生事件B的概率。

同時滿足最小支持度閾值和最小置信度閾值的規則稱為強規則。

如果事件A中包含k個元素，那么稱這個事件A為k項集，并且事件A滿足最小支持度閾值的事件稱為頻繁k項集。

2）挖掘過程：

第一，找出所有的頻繁項集；

第二，由頻繁項集產生強規則。

2．?什么是Apriori

2.1???Apriori介紹

Apriori算法使用頻繁項集的先驗知識，使用一種稱作逐層搜索的迭代方法，k項集用于探索(k+1)項集。首先，通過掃描事務（交易）記錄，找出所有的頻繁1項集，該集合記做L₁，然后利用L₁找頻繁2項集的集合L₂，L₂找L₃，如此下去，直到不能再找到任何頻繁k項集。最后再在所有的頻繁集中找出強規則，即產生用戶感興趣的關聯規則。

其中，Apriori算法具有這樣一條性質：任一頻繁項集的所有非空子集也必須是頻繁的。因為假如P(I)<?最小支持度閾值，當有元素A添加到I中時，結果項集（A∩I）不可能比I出現次數更多。因此A∩I也不是頻繁的。

2.2??連接步和剪枝步
1）??連接步
若有兩個k-1項集，每個項集按照“屬性-值”（一般按值）的字母順序進行排序。如果兩個k-1項集的前k-2個項相同，而最后一個項不同，則證明它們是可連接的，即這個k-1項集可以聯姻，即可連接生成k項集。使如有兩個3項集：｛a, b, c｝{a, b, d}，這兩個3項集就是可連接的，它們可以連接生成4項集｛a, b, c, d｝。又如兩個3項集｛a, b, c｝｛a, d, e｝，這兩個3項集顯示是不能連接生成3項集的。
剪枝步 若一個項集的子集不是頻繁項集，則該項集肯定也不是頻繁項集。這個很好理解，舉一個例子，若存在3項集｛a, b, c｝，如果它的2項子集｛a, b｝的支持度即同時出現的次數達不到閾值，則｛a, b, c｝同時出現的次數顯然也是達不到閾值的。因此，若存在一個項集的子集不是頻繁項集，那么該項集就應該被無情的舍棄。 Apriori算法流程： 1. 過單趟掃描數據庫D；計算出各個1項集的支持度，得 到頻繁1項集的集合。

2. 從2項集開始循環，由頻繁k-1項集生成頻繁頻繁k項集。

???? ?2.1? 連接步：為了生成，預先生成,由2個只有一個項不同的屬于的頻集做一 個（k-2）JOIN運算得到的。

?? ?2.2? 剪枝步：由于是的超集，所以可能有些元素不是頻繁的。舍棄掉子集不是頻繁項集即不在頻繁k-1項集中的項集

?? ?2.3? 掃描數據庫，計算2.3步中過濾后的k項集的支持度，舍棄掉支持度小于閾值的項集，生成頻繁k項集。

3.? 當當前生成的頻繁k項集中只有一個項集時循環結束

【注意】
在剪枝步中的每個元 素需在交易數據庫中進行驗證來決定其是否加入，這里的驗證過程 是算法性能的一個瓶頸。這個方法要求多次掃描可能很大的交易數據庫。可能產生大量的候選集，以及可能需要重復掃描數據庫，是Apriori算法的兩大缺 點。

???Apriori算法實例

交易ID	商品ID列表
T100	I1，I2，I5
T200	I2，I4
T300	I2，I3
T400	I1，I2，I4
T500	I1，I3
T600	I2，I3
T700	I1，I3
T800	I1，I2，I3，I5
T900	I1，I2，I3

上圖為某商場的交易記錄，共有9個事務，利用Apriori算法尋找所有的頻繁項集的過程如下:

詳細介紹下候選3項集的集合C3的產生過程：從連接步，首先C3={{I1,I2,I3}，{I1,I2,I5}，{I1,I3,I5}，{I1,I2,I4}，{I2,I3,I4}，{I2,I3,I5}，{I2,I4,I5}}（C3是由L2與自身連接產生）。根據Apriori性質，頻繁項集的所有子集也必須頻繁的，可以確定有4個候選集{I1,I3,I5}，{I2,I3,I4}，{I2,I3,I5}，{I2,I4,I5}}不可能時頻繁的，因為它們存在子集不屬于頻繁集，因此將它們從C3中刪除。注意，由于Apriori算法使用逐層搜索技術，給定候選k項集后，只需檢查它們的（k-1）個子集是否頻繁。

又如：

3、總結與優化

??①Apriori算法的缺點：(1)由頻繁k-1項集進行自連接生成的候選頻繁k項集數量巨大。(2)在驗證候選頻繁k項集的時候需要對整個數據庫進行掃描，非常耗時。

??②網上提到的頻集算法的幾種優化方法：1.?基于劃分的方法。2.?基于hash的方法。3.?基于采樣的方法。4.?減少交易的個數。

???我重點看了“基于劃分的方法”改進算法，現在簡單介紹一下實現思想：

基于劃分(partition)的算法，這個算法先把數據庫從邏輯上分成幾個互不相交的塊，每次單獨考慮一個分塊并?對它生成所有的頻集，然后把產生的頻集合并，用來生成所有可能的頻集，最后計算這些項集的支持度。

其中，partition算法要注意的是分片的大小選取，要保證每個分片可以被放入到內存。當每個分片產生頻集后，再合并產生產生全局的候選k-項集。若在多個處理器分片，可以通過處理器之間共享一個雜湊樹來產生頻集。

轉自：http://blog.csdn.net/lizhengnanhua/article/details/9061755 http://blog.csdn.net/qustdjx/article/details/12770883

總結

以上是生活随笔為你收集整理的Apriori算法简介---关联规则的频繁项集算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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