一、Apriori算法簡(jiǎn)介： Apriori算法是一種挖掘關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集算法，其核心思想是通過候選集生成和情節(jié)的向下封閉檢測(cè)兩個(gè)階段來挖掘頻繁項(xiàng)集。 Apriori（先驗(yàn)的，推測(cè)的）算法應(yīng)用廣泛，可用于消費(fèi)市場(chǎng)價(jià)格分析，猜測(cè)顧客的消費(fèi)習(xí)慣；網(wǎng)絡(luò)安全領(lǐng)域中的入侵檢測(cè)技術(shù)；可用在用于高校管理中，根據(jù)挖掘規(guī)則可以有效地輔助學(xué)校管理部門有針對(duì)性的開展貧困助學(xué)工作；也可用在移動(dòng)通信領(lǐng)域中，指導(dǎo)運(yùn)營商的業(yè)務(wù)運(yùn)營和輔助業(yè)務(wù)提供商的決策制定。

　　二、挖掘步驟：

　　1.依據(jù)支持度找出所有頻繁項(xiàng)集（頻度）

　　2.依據(jù)置信度產(chǎn)生關(guān)聯(lián)規(guī)則（強(qiáng)度）

　　三、基本概念

　　對(duì)于A-》B

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

　　②置信度：

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

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

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

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

　?、廴绻录嗀中包含k個(gè)元素，那么稱這個(gè)事件A為k項(xiàng)集事件A滿足最小支持度閾值的事件稱為頻繁k項(xiàng)集。

　?、芡瑫r(shí)滿足最小支持度閾值和最小置信度閾值的規(guī)則稱為強(qiáng)規(guī)則

　　四、實(shí)現(xiàn)步驟

　　Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法Apriori使用一種稱作逐層搜索的迭代方法，“K-1項(xiàng)集”用于搜索“K項(xiàng)集”。

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

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

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

　　簡(jiǎn)單的講，1、發(fā)現(xiàn)頻繁項(xiàng)集，過程為（1）掃描（2）計(jì)數(shù)（3）比較（4）產(chǎn)生頻繁項(xiàng)集（5）連接、剪枝，產(chǎn)生候選項(xiàng)集 重復(fù)步驟（1）~（5）直到不能發(fā)現(xiàn)更大的頻集

　　2、產(chǎn)生關(guān)聯(lián)規(guī)則，過程為：根據(jù)前面提到的置信度的定義，關(guān)聯(lián)規(guī)則的產(chǎn)生如下：

　　（1）對(duì)于每個(gè)頻繁項(xiàng)集L，產(chǎn)生L的所有非空子集；

　?。?）對(duì)于L的每個(gè)非空子集S，如果

　　P（L）/P（S）≧min_conf

　　則輸出規(guī)則“SàL-S”

　　注：L-S表示在項(xiàng)集L中除去S子集的項(xiàng)集

　　?

　　上一篇文章中對(duì)Apriori算法以及步驟進(jìn)行了簡(jiǎn)單的描述，，現(xiàn)在用偽代碼實(shí)現(xiàn)，及對(duì)經(jīng)典例子進(jìn)行描述

　　一、Apriori算法偽代碼實(shí)現(xiàn)：

　　偽代碼描述：

　　// 找出頻繁 1 項(xiàng)集

　　L1 =find_frequent_1-itemsets（D）;

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

　　// 產(chǎn)生候選，并剪枝

　　Ck =apriori_gen（Lk-1 ）;

　　// 掃描 D 進(jìn)行候選計(jì)數(shù)

　　For each 事務(wù)t in D{

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

　　For each 候選 c 屬于 Ct

　　c.count++;

　　}

　　//返回候選項(xiàng)集中不小于最小支持度的項(xiàng)集

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

　　}

　　Return L= 所有的頻繁集；

　　第一步：連接（join）

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

　　For each 項(xiàng)集 l1 屬于 Lk-1

　　For each 項(xiàng)集 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 // 連接步：產(chǎn)生候選

　　//若k-1項(xiàng)集中已經(jīng)存在子集c則進(jìn)行剪枝

　　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算法例子：

　　?

　　三、總結(jié)：

　?、貯priori算法的缺點(diǎn)：（1）由頻繁k-1項(xiàng)集進(jìn)行自連接生成的候選頻繁k項(xiàng)集數(shù)量巨大。（2）在驗(yàn)證候選頻繁k項(xiàng)集的時(shí)候需要對(duì)整個(gè)數(shù)據(jù)庫進(jìn)行掃描，非常耗時(shí)。

　?、诰W(wǎng)上提到的頻集算法的幾種優(yōu)化方法：1. 基于劃分的方法。2. 基于hash的方法。3. 基于采樣的方法。4. 減少交易的個(gè)數(shù)。

　　我重點(diǎn)看了“基于劃分的方法”改進(jìn)算法，現(xiàn)在簡(jiǎn)單介紹一下實(shí)現(xiàn)思想：

　　基于劃分（partition）的算法，這個(gè)算法先把數(shù)據(jù)庫從邏輯上分成幾個(gè)互不相交的塊，每次單獨(dú)考慮一個(gè)分塊并 對(duì)它生成所有的頻集，然后把產(chǎn)生的頻集合并，用來生成所有可能的頻集，最后計(jì)算這些項(xiàng)集的支持度。

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

　　看這個(gè)圖基本再對(duì)照偽代碼，基本就可以看懂了~簡(jiǎn)單明了