一、Apriori算法簡介： Apriori算法是一種挖掘關聯規則的頻繁項集算法，其核心思想是通過候選集生成和情節的向下封閉檢測兩個階段來挖掘頻繁項集。 Apriori（先驗的，推測的）算法應用廣泛，可用于消費市場價格分析，猜測顧客的消費習慣；網絡安全領域中的入侵檢測技術；可用在用于高校管理中，根據挖掘規則可以有效地輔助學校管理部門有針對性的開展貧困助學工作；也可用在移動通信領域中，指導運營商的業務運營和輔助業務提供商的決策制定。

　　二、挖掘步驟：

　　1.依據支持度找出所有頻繁項集（頻度）

　　2.依據置信度產生關聯規則（強度）

　　三、基本概念

　　對于A-》B

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

　　②置信度：

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

　　例子：［支持度：3%，置信度：40%］

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

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

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

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

　　四、實現步驟

　　Apriori算法是一種最有影響的挖掘布爾關聯規則頻繁項集的算法Apriori使用一種稱作逐層搜索的迭代方法，“K-1項集”用于搜索“K項集”。

　　首先，找出頻繁“1項集”的集合，該集合記作L1。L1用于找頻繁“2項集”的集合L2，而L2用于找L3。如此下去，直到不能找到“K項集”。找每個Lk都需要一次數據庫掃描。

　　核心思想是：連接步和剪枝步。連接步是自連接，原則是保證前k-2項相同，并按照字典順序連接。剪枝步，是使任一頻繁項集的所有非空子集也必須是頻繁的。反之，如果某

　　個候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的，從而可以將其從CK中刪除。

　　簡單的講，1、發現頻繁項集，過程為（1）掃描（2）計數（3）比較（4）產生頻繁項集（5）連接、剪枝，產生候選項集 重復步驟（1）~（5）直到不能發現更大的頻集

　　2、產生關聯規則，過程為：根據前面提到的置信度的定義，關聯規則的產生如下：

　　（1）對于每個頻繁項集L，產生L的所有非空子集；

　　（2）對于L的每個非空子集S，如果

　　P（L）/P（S）≧min_conf

　　則輸出規則“SàL-S”

　　注：L-S表示在項集L中除去S子集的項集

　　?

　　上一篇文章中對Apriori算法以及步驟進行了簡單的描述，，現在用偽代碼實現，及對經典例子進行描述

　　一、Apriori算法偽代碼實現：

　　偽代碼描述：

　　// 找出頻繁 1 項集

　　L1 =find_frequent_1-itemsets（D）;

　　For（k=2;Lk-1 ！=null;k++）{

　　// 產生候選，并剪枝

　　Ck =apriori_gen（Lk-1 ）;

　　// 掃描 D 進行候選計數

　　For each 事務t in D{

　　Ct =subset（Ck，t）; // 得到 t 的子集

　　For each 候選 c 屬于 Ct

　　c.count++;

　　}

　　//返回候選項集中不小于最小支持度的項集

　　Lk ={c 屬于 Ck | c.count》=min_sup}

　　}

　　Return L= 所有的頻繁集；

　　第一步：連接（join）

　　Procedure apriori_gen （Lk-1 ：frequent（k-1）-itemsets）

　　For each 項集 l1 屬于 Lk-1

　　For each 項集 l2 屬于 Lk-1

　　If（ （l1 ［1］=l2 ［1］）&&（ l1 ［2］=l2 ［2］）&& ……&& （l1 ［k-2］=l2 ［k-2］）&&（l1 ［k-1］《l2 ［k-1］） ）

　　then{

　　c = l1 連接 l2 // 連接步：產生候選

　　//若k-1項集中已經存在子集c則進行剪枝

　　if has_infrequent_subset（c， Lk-1 ） then

　　delete c; // 剪枝步：刪除非頻繁候選

　　else add c to Ck;

　　}

　　Return Ck;

　　第二步：剪枝（prune）

　　Procedure has_infrequent_sub （c:candidate k-itemset; Lk-1 ：frequent（k-1）-itemsets）

　　For each （k-1）-subset s of c

　　If s 不屬于 Lk-1 then

　　Return true;

　　Return false;

　　二、Apriori算法例子：

　　?

　　三、總結：

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

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

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

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

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

　　看這個圖基本再對照偽代碼，基本就可以看懂了~簡單明了