寧夏大學(xué)

第十一章Apriori算法Apriori算法www.islide.cc2目錄

CONTENT01引言02算法概述03實驗數(shù)據(jù)04算法實戰(zhàn)05本章小結(jié)01引言

Apriori算法是用于挖掘出數(shù)據(jù)關(guān)聯(lián)規(guī)則的算法，它用來找出數(shù)據(jù)值中頻繁出現(xiàn)的數(shù)據(jù)集合，通過這些集合的模式有助于我們做一些決策。比如在常見的超市購物數(shù)據(jù)集，或者電商的網(wǎng)購數(shù)據(jù)集中，如果我們找到頻繁出現(xiàn)的數(shù)據(jù)集合，那么對于超市，我們可以優(yōu)化產(chǎn)品的擺放位置，對于電商，我們可以優(yōu)化商品所在的倉庫為止，達(dá)到節(jié)約成本，增加經(jīng)濟(jì)效益的目的。引言02算法概述1基本概念關(guān)聯(lián)分析關(guān)聯(lián)分析（associationanalysis）是一種在大規(guī)模數(shù)據(jù)集中尋找有趣關(guān)系的非監(jiān)督學(xué)習(xí)算法。這種關(guān)系可以有兩種形式：頻繁項集或者關(guān)聯(lián)規(guī)則。頻繁項集（frequentitemsets）是經(jīng)常出現(xiàn)在一塊的物品的集合，關(guān)聯(lián)規(guī)則（associationrules）暗示兩種物品之間可能存在很強(qiáng)的關(guān)系。

頻繁項集1基本概念關(guān)聯(lián)規(guī)則

1基本概念

通常，頻繁項集產(chǎn)生所需的計算開銷遠(yuǎn)大于產(chǎn)生關(guān)聯(lián)規(guī)則所需的計算開銷。那有沒有辦法可以減少這種無用的計算呢？

我們可以通過下面這兩種方法可以降低產(chǎn)生頻繁項集的計算復(fù)雜度：

（1）減少候選項集的數(shù)目M。

（2）減少比較次數(shù)。替代將每個候選項集與每個事務(wù)相匹配，可以使用更高級的數(shù)據(jù)結(jié)構(gòu)，或者存儲候選項集或者壓縮數(shù)據(jù)集，來減少比較次數(shù)。

這些策略將在Apriori算法基本思想中進(jìn)行討論。2

Apriori算法思想對于Apriori算法，我們使用支持度來作為我們判斷頻繁項集的標(biāo)準(zhǔn)。Apriori算法的目標(biāo)是找到最大的K項頻繁集。這里有兩層意思，第一層意思是我們要找到符合支持度標(biāo)準(zhǔn)的頻繁項集，但這樣的頻繁項集可能有很多。第二層意思就是我們要找到最大個數(shù)的頻繁項集。比如我們找到符合支持度的頻繁項集AB和ABE，那么我們會拋棄AB，只保留ABE，因為AB是2項頻繁集，而ABE是3項頻繁集。那么具體的Apriori算法是如何做到挖掘K項頻繁項集的呢？

Apriori算法采用的是逐層搜索的迭代方法，先搜索出候選1項集及對應(yīng)的支持度，剪枝去掉低于支持度的1項集，得到頻繁1項集。然后對剩下的頻繁1項集進(jìn)行連接，得到候選的頻繁2項集，篩選去掉低于支持度的候選頻繁2項集，得到真正的頻繁2項集，以此類推，迭代下去，直到無法找到頻繁k+1項集為止，對應(yīng)的頻繁k項集的集合即為算法的輸出結(jié)果。2

Apriori算法思想為了方便讀者了解Apriori算法，這里以一個簡單的例子，對該算法中的各個步驟進(jìn)行解釋分析，假定事物數(shù)據(jù)集如下所示：2

Apriori算法思想將所有的單個項作為候選集，通過掃描數(shù)據(jù)集中所有事務(wù)，生成一個候選1-項集C1；然后計算出每個候選集出現(xiàn)的次數(shù)，并根據(jù)預(yù)先設(shè)定的最小閾值（最小支持度為2，支持度50%）選擇頻繁1-項集L1。2

Apriori算法思想通過項集L1產(chǎn)生候選頻繁2-項集L22

Apriori算法思想通過項集L2產(chǎn)生候選頻繁3-項集L3因為L3無法產(chǎn)生候選4項集，所有終止迭代過程。在實際情況中，當(dāng)數(shù)據(jù)較多時，一層層向上尋找，當(dāng)無法繼續(xù)構(gòu)造時停止處理。2

Apriori算法思想根據(jù)產(chǎn)生的頻繁項集生成關(guān)聯(lián)規(guī)則，利用L3={B,C,D}產(chǎn)生關(guān)聯(lián)規(guī)則，確定該頻繁項集中的所有非空子集：2

Apriori算法思想根據(jù)各項子集產(chǎn)生關(guān)聯(lián)規(guī)則，并計算各個表達(dá)式的可信度從上述過程中可以看出，支持度大，置信度則越高（如關(guān)聯(lián)規(guī)則2與關(guān)聯(lián)規(guī)則3），關(guān)聯(lián)規(guī)則的實用機(jī)會就大，此關(guān)聯(lián)規(guī)則就越重要；一些關(guān)聯(lián)規(guī)則置信度很高，但支持度很低（如關(guān)聯(lián)規(guī)則9,10,11），則此關(guān)聯(lián)規(guī)則就不那么重要。03實驗數(shù)據(jù)1準(zhǔn)備數(shù)據(jù)數(shù)據(jù)集介紹購物籃分析時大型零售商用來發(fā)現(xiàn)商品之間關(guān)聯(lián)的關(guān)鍵技術(shù)之一。它的工作原理是尋找在交易中經(jīng)常一起出現(xiàn)的項目組合。本數(shù)據(jù)集有38765行來自雜貨店的客戶的采購訂單，分別包括客戶編號、購買日期以及產(chǎn)品清單。數(shù)據(jù)集下載

Kaggle是一個數(shù)據(jù)分析的競賽平臺，在該平臺上可以尋找當(dāng)前熱門的比賽和可用的數(shù)據(jù)集。本實驗數(shù)據(jù)集鏈接為：/heeraldedhia/groceries-dataset導(dǎo)入數(shù)據(jù)集2分析數(shù)據(jù)接下來，我們將探索以獲取有關(guān)數(shù)據(jù)的理解。首先通過下面的代碼可以看到數(shù)據(jù)集中38765個實例和3個屬性以及前5行的數(shù)據(jù)2分析數(shù)據(jù)查看數(shù)據(jù)集摘要，并查看銷量最高的10件商品3處理數(shù)據(jù)將數(shù)據(jù)集處理為只有商品數(shù)據(jù)的數(shù)據(jù)集，方便算法在該數(shù)據(jù)集上的應(yīng)用我們現(xiàn)在已經(jīng)準(zhǔn)備好將處理后的數(shù)據(jù)集輸入到Apriori算法中進(jìn)行關(guān)聯(lián)分析。04算法實戰(zhàn)1算法構(gòu)建整個Apriori算法的偽代碼如下：接下來，我們通過偽代碼的流程來完成完整的Apriori算法。1算法構(gòu)建構(gòu)建候選集通過for循環(huán)遍歷整個數(shù)據(jù)集生成C1候選集通過頻繁項集Lk-1創(chuàng)建Ck候選集，并通過遍歷找出前n-1個元素相同的項生成下一候選項1算法構(gòu)建構(gòu)建頻繁項集通過候選項ck生成lk，并將各頻繁項的支持度保存到support_data字典中。生成所有頻繁項集的主函數(shù)，k為最大頻繁項的大小1算法構(gòu)建生成關(guān)聯(lián)規(guī)則根據(jù)頻繁項集和支持度生成關(guān)聯(lián)規(guī)則2訓(xùn)練測試數(shù)據(jù)3結(jié)果分析從運行結(jié)果中可以看出，設(shè)定最小可信度為0.8時，可信度<0.8的結(jié)果將會被舍棄，不會放入到結(jié)果數(shù)據(jù)中。05本章小結(jié)本章小節(jié)關(guān)聯(lián)分析是用于發(fā)現(xiàn)大數(shù)據(jù)集中元素間關(guān)系的一個工具集，可以采用兩種方式來量化這些關(guān)系。第一種方式是使用頻繁項集，它會給出經(jīng)常在一起的元素項。第二種方式是關(guān)聯(lián)規(guī)則，每條關(guān)聯(lián)規(guī)則意味著元素項之間的“如果·····那么”關(guān)系。

Apriori算法是關(guān)聯(lián)規(guī)則最經(jīng)典的方法，常用于挖掘出數(shù)據(jù)關(guān)聯(lián)規(guī)則的算法，它用來找出數(shù)據(jù)值中頻繁出現(xiàn)的數(shù)據(jù)集合并找出這些集合的模式，這樣有助于我們進(jìn)行一些決策。該算法的優(yōu)點在于使用