文|劉建平

導(dǎo)語(yǔ)：關(guān)聯(lián)算法是數(shù)據(jù)挖掘中的一類(lèi)重要算法。1993年,R.Agrawal等人首次提出了挖掘顧客交易數(shù)據(jù)中項(xiàng)目集間的關(guān)聯(lián)規(guī)則問(wèn)題，其核心是基于兩階段頻繁集思想的遞推算法。該關(guān)聯(lián)規(guī)則在分類(lèi)上屬于單維、單層及布爾關(guān)聯(lián)規(guī)則，典型的算法是Apriori算法。Apriori算法將發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的過(guò)程分為兩個(gè)步驟：第一步通過(guò)迭代，檢索出事務(wù)數(shù)據(jù)庫(kù)1中的所有頻繁項(xiàng)集，即支持度不低于用戶(hù)設(shè)定的閾值的項(xiàng)集；第二步利用頻繁項(xiàng)集構(gòu)造出滿(mǎn)足用戶(hù)最小信任度的規(guī)則。其中，挖掘或識(shí)別出所有頻繁項(xiàng)集是該算法的核心，占整個(gè)計(jì)算量的大部分。

Apriori算法是常用的用于挖掘出數(shù)據(jù)關(guān)聯(lián)規(guī)則的算法，它用來(lái)找出數(shù)據(jù)值中頻繁出現(xiàn)的數(shù)據(jù)集合，找出這些集合的模式有助于我們做一些決策。比如在常見(jiàn)的超市購(gòu)物數(shù)據(jù)集，或者電商的網(wǎng)購(gòu)數(shù)據(jù)集中，如果我們找到了頻繁出現(xiàn)的數(shù)據(jù)集，那么對(duì)于超市，我們可以?xún)?yōu)化產(chǎn)品的位置擺放，對(duì)于電商，我們可以?xún)?yōu)化商品所在的倉(cāng)庫(kù)位置，達(dá)到節(jié)約成本，增加經(jīng)濟(jì)效益的目的。下面我們就對(duì)Apriori算法做一個(gè)總結(jié)。

1. 頻繁項(xiàng)集的評(píng)估標(biāo)準(zhǔn)

什么樣的數(shù)據(jù)才是頻繁項(xiàng)集呢？也許你會(huì)說(shuō)，這還不簡(jiǎn)單，肉眼一掃，一起出現(xiàn)次數(shù)多的數(shù)據(jù)集就是頻繁項(xiàng)集嗎！的確，這也沒(méi)有說(shuō)錯(cuò)，但是有兩個(gè)問(wèn)題，第一是當(dāng)數(shù)據(jù)量非常大的時(shí)候，我們沒(méi)法直接肉眼發(fā)現(xiàn)頻繁項(xiàng)集，這催生了關(guān)聯(lián)規(guī)則挖掘的算法，比如Apriori, PrefixSpan, CBA。第二是我們?nèi)狈σ粋€(gè)頻繁項(xiàng)集的標(biāo)準(zhǔn)。比如10條記錄，里面A和B同時(shí)出現(xiàn)了三次，那么我們能不能說(shuō)A和B一起構(gòu)成頻繁項(xiàng)集呢？因此我們需要一個(gè)評(píng)估頻繁項(xiàng)集的標(biāo)準(zhǔn)。

常用的頻繁項(xiàng)集的評(píng)估標(biāo)準(zhǔn)有支持度,置信度和提升度三個(gè)。

支持度就是幾個(gè)關(guān)聯(lián)的數(shù)據(jù)在數(shù)據(jù)集中出現(xiàn)的次數(shù)占總數(shù)據(jù)集的比重。或者說(shuō)幾個(gè)數(shù)據(jù)關(guān)聯(lián)出現(xiàn)的概率。如果我們有兩個(gè)想分析關(guān)聯(lián)性的數(shù)據(jù)X和Y，則對(duì)應(yīng)的支持度為:

以此類(lèi)推，如果我們有三個(gè)想分析關(guān)聯(lián)性的數(shù)據(jù)X，Y和Z，則對(duì)應(yīng)的支持度為:

一般來(lái)說(shuō)，支持度高的數(shù)據(jù)不一定構(gòu)成頻繁項(xiàng)集，但是支持度太低的數(shù)據(jù)肯定不構(gòu)成頻繁項(xiàng)集。

置信度體現(xiàn)了一個(gè)數(shù)據(jù)出現(xiàn)后，另一個(gè)數(shù)據(jù)出現(xiàn)的概率，或者說(shuō)數(shù)據(jù)的條件概率。如果我們有兩個(gè)想分析關(guān)聯(lián)性的數(shù)據(jù)X和Y，X對(duì)Y的置信度為 Apriori算法 也可以以此類(lèi)推到多個(gè)數(shù)據(jù)的關(guān)聯(lián)置信度，比如對(duì)于三個(gè)數(shù)據(jù)X，Y，Z,則X對(duì)于Y和Z的置信度為：

舉個(gè)例子，在購(gòu)物數(shù)據(jù)中，紙巾對(duì)應(yīng)雞爪的置信度為40%，支持度為1%。則意味著在購(gòu)物數(shù)據(jù)中，總共有1%的用戶(hù)既買(mǎi)雞爪又買(mǎi)紙巾;同時(shí)買(mǎi)雞爪的用戶(hù)中有40%的用戶(hù)購(gòu)買(mǎi)紙巾。

提升度表示含有Y的條件下，同時(shí)含有X的概率，與X總體發(fā)生的概率之比，即:

提升度體先了X和Y之間的關(guān)聯(lián)關(guān)系, 關(guān)聯(lián)度高則提升度小，一個(gè)特殊的情況，如果X和Y獨(dú)立，則有

達(dá)到最大，因?yàn)榇藭r(shí)

一般來(lái)說(shuō)，要選擇一個(gè)數(shù)據(jù)集合中的頻繁數(shù)據(jù)集，則需要自定義評(píng)估標(biāo)準(zhǔn)。最常用的評(píng)估標(biāo)準(zhǔn)是用自定義的支持度，或者是自定義支持度和置信度的一個(gè)組合。

2. Apriori算法思想

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

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

可見(jiàn)這個(gè)算法還是很簡(jiǎn)潔的，第i次的迭代過(guò)程包括掃描計(jì)算候選頻繁i項(xiàng)集的支持度，剪枝得到真正頻繁i項(xiàng)集和連接生成候選頻繁i+1項(xiàng)集三步。

我們下面這個(gè)簡(jiǎn)單的例子看看：

我們的數(shù)據(jù)集D有4條記錄，分別是134,235,1235和25。現(xiàn)在我們用Apriori算法來(lái)尋找頻繁k項(xiàng)集，最小支持度設(shè)置為50%。首先我們生成候選頻繁1項(xiàng)集，包括我們所有的5個(gè)數(shù)據(jù)并計(jì)算5個(gè)數(shù)據(jù)的支持度，計(jì)算完畢后我們進(jìn)行剪枝，數(shù)據(jù)4由于支持度只有25%被剪掉。我們最終的頻繁1項(xiàng)集為1235，現(xiàn)在我們鏈接生成候選頻繁2項(xiàng)集，包括12,13,15,23,25,35共6組。此時(shí)我們的第一輪迭代結(jié)束。

進(jìn)入第二輪迭代，我們掃描數(shù)據(jù)集計(jì)算候選頻繁2項(xiàng)集的支持度，接著進(jìn)行剪枝，由于12和15的支持度只有25%而被篩除，得到真正的頻繁2項(xiàng)集，包括13,23,25,35。現(xiàn)在我們鏈接生成候選頻繁3項(xiàng)集,123, 125，135和235共4組，這部分圖中沒(méi)有畫(huà)出。通過(guò)計(jì)算候選頻繁3項(xiàng)集的支持度，我們發(fā)現(xiàn)123,125和135的支持度均為25%，因此接著被剪枝，最終得到的真正頻繁3項(xiàng)集為235一組。由于此時(shí)我們無(wú)法再進(jìn)行數(shù)據(jù)連接，進(jìn)而得到候選頻繁4項(xiàng)集，最終的結(jié)果即為頻繁3三項(xiàng)集235。

Aprior算法流程

下面我們對(duì)Aprior算法流程做一個(gè)總結(jié)。

輸入：數(shù)據(jù)集合D，支持度閾值α" style="box-sizing: border-box; margin: 0px; padding: 0px; display: inline; line-height: normal; font-size: 12px; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">αα

輸出：最大的頻繁k項(xiàng)集

1）掃描整個(gè)數(shù)據(jù)集，得到所有出現(xiàn)過(guò)的數(shù)據(jù)，作為候選頻繁1項(xiàng)集。k=1，頻繁0項(xiàng)集為空集。

2）挖掘頻繁k項(xiàng)集

a) 掃描數(shù)據(jù)計(jì)算候選頻繁k項(xiàng)集的支持度

b) 去除候選頻繁k項(xiàng)集中支持度低于閾值的數(shù)據(jù)集,得到頻繁k項(xiàng)集。如果得到的頻繁k項(xiàng)集為空，則直接返回頻繁k-1項(xiàng)集的集合作為算法結(jié)果，算法結(jié)束。如果得到的頻繁k項(xiàng)集只有一項(xiàng)，則直接返回頻繁k項(xiàng)集的集合作為算法結(jié)果，算法結(jié)束。

c) 基于頻繁k項(xiàng)集，連接生成候選頻繁k+1項(xiàng)集。

3） 令k=k+1，轉(zhuǎn)入步驟2。

從算法的步驟可以看出，Aprior算法每輪迭代都要掃描數(shù)據(jù)集，因此在數(shù)據(jù)集很大，數(shù)據(jù)種類(lèi)很多的時(shí)候，算法效率很低。

Aprior算法總結(jié)

Aprior算法是一個(gè)非常經(jīng)典的頻繁項(xiàng)集的挖掘算法，很多算法都是基于Aprior算法而產(chǎn)生的，包括FP-Tree,GSP, CBA等。這些算法利用了Aprior算法的思想，但是對(duì)算法做了改進(jìn)，數(shù)據(jù)挖掘效率更好一些，因此現(xiàn)在一般很少直接用Aprior算法來(lái)挖掘數(shù)據(jù)了，但是理解Aprior算法是理解其它Aprior類(lèi)算法的前提，同時(shí)算法本身也不復(fù)雜，因此值得好好研究一番。

不過(guò)scikit-learn中并沒(méi)有頻繁集挖掘相關(guān)的算法類(lèi)庫(kù)，這不得不說(shuō)是一個(gè)遺憾，不知道后面的版本會(huì)不會(huì)加上。