一、Apriori算法簡介

? ? ? ?Apriori算法用于解決大規(guī)模數(shù)據(jù)集的關(guān)聯(lián)分析問題。關(guān)聯(lián)分析（association analysis）或關(guān)聯(lián)規(guī)則學(xué)習(xí)（association rule learning）是從大規(guī)模數(shù)據(jù)集中尋找物品間的隱含關(guān)系。但是，尋找物品的不同組合是一項十分耗時的任務(wù)，計算代價高，蠻力搜索并不能解決問題，所以需要更智能的方法在合理時間范圍內(nèi)找到頻繁項集。Apriori算法就是解決這個問題的。

二、關(guān)聯(lián)分析

? ? ? ?關(guān)聯(lián)分析是一種在大規(guī)模數(shù)據(jù)集中尋找有趣關(guān)系的任務(wù)。這些關(guān)系可以有兩種形式：（1）頻繁項集，（2）關(guān)聯(lián)規(guī)則。

（1）頻繁項集

頻繁項集：是經(jīng)常出現(xiàn)在一塊的物品的集合。

量化方法：支持度（support）。支持度是數(shù)據(jù)集中包含該項集的記錄所占的比例。例如數(shù)據(jù)集[[1, 3, 4], [2, 3, 5], [1, 2, 3], [2, 5]]中，項集{2}的支持度為3/4，項集{2,3}的支持度為1/2。

（2）關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則：暗示兩種物品之間可能存在很強的關(guān)系。

量化計算：可信度或置信度（confidence）。可信度是針對一條關(guān)聯(lián)規(guī)則（如{2}-->{3}）來定義的。{2}-->{3}這條規(guī)則的可信度為“支持度{2，3}/支持度{2}”，即2/3，意味著包含{2}的所有記錄中2/3符合規(guī)則包含{2,3}。

三、Apriori原理

? ? ? ?無論頻繁項集還是關(guān)聯(lián)規(guī)則都需要計算支持度。如果數(shù)據(jù)量小，計算一個項集的支持度可以針對每個項集掃描所有數(shù)據(jù)，然后統(tǒng)計該項集出現(xiàn)的總數(shù)除以總的交易記錄數(shù)，就可以得到支持度。但是對于N個物品的數(shù)據(jù)集共有2N-1中項集組合，即使4個物品也需要遍歷數(shù)據(jù)集15次，100種物品有中可能的項集組合，對現(xiàn)代計算機而言，需要很長的時間才能完成運算，何況事實上，商店都會有上百上千種商品。

? ? ? ?Apriori算法可以降低計算時間，減少可能感興趣的項集。

? ? ? ?Apriori原理：如果某個項集是頻繁的，那么它的所有子集也是頻繁的。如若{2,3}是頻繁的，那么{0}、{1}也一定是頻繁的。反過來同樣，如果一個項集是非頻繁集，那么它的所有超集也是非頻繁的。如若{2,3}是非頻繁的，那么{0,2,3}、{1,2,3}、{0,1,2,3}也是非頻繁項。所以如果計算出{2,3}的支持度是非頻繁的，那么{0,2,3}、{1,2,3}、{0,1,2,3}的支持度就不用計算了。

Apriori原理可以避免項集數(shù)目的指數(shù)增長，從而在合理時間內(nèi)計算出頻繁項集。

四、Apriori算法發(fā)現(xiàn)頻繁項集

Apriori算法流程：

1）首先，基于數(shù)據(jù)集生成個數(shù)為1的項集的列表C1；

2）根據(jù)頻繁項集函數(shù)，計算C1中各元素的支持度，去掉不滿足最小支持度的元素，生成滿足最小支持度的頻繁項集列表L1；

3）根據(jù)創(chuàng)建候選項集函數(shù)，基于L1生成k=2的候選項集列表C2；

4）根據(jù)頻繁項集函數(shù)，基于C2生成滿足最小支持度的k=2的頻繁項集列表L2；

5）增加k的值，重復(fù)3）、4）生成Lk，直到Lk為空時，返回L列表，L包含L1、L2、L3...

? ? ? ?以下是創(chuàng)建候選項集函數(shù)及解釋。

? ? ? ?至于為什么是比較前k-2個元素呢，一般初始項集個數(shù)為1，由k=1的項集生成k=2的項集。所以k的初始值也為2。如果要生成個數(shù)為k的項集，則比較前k-2項，如果相等合并，正好比較的項各剩下1個不相等的元素，這樣合并后個數(shù)就為k-2+1+1=k項。（以下是舉例推導(dǎo)過程，忽略C2經(jīng)過濾后生成L2，直接將C2視為L2，相當(dāng)于支持度為0）

? ? ? ?比較前k-2個元素，可以減少遍歷列表的次數(shù)。比如想利用{0,1}、{0,2}、{1,2}來創(chuàng)建三元素項集，如果將每兩個集合合并，就會得到{0,1,2}、{0,1,2}、{0,1,2}。同樣的結(jié)果結(jié)合會重復(fù)3次，還需要處理以得到非重復(fù)結(jié)果?，F(xiàn)在只比較第k-2=1個元素，第1個元素相同才合并集合，得到{0,1,2}，只有一次操作，這樣就不需要遍歷列表來尋找非重復(fù)值。

五、從頻繁項集中挖掘關(guān)聯(lián)規(guī)則

? ? ? ?首先從一個頻繁項集開始，接著創(chuàng)建一個規(guī)則列表，其中規(guī)則右部只包含一個元素，然后對這些規(guī)則進(jìn)行測試。接下來合并所有剩余規(guī)則來創(chuàng)建一個新的規(guī)則列表，其中規(guī)則右部包含兩個元素。這種方法也被稱作分級法。【待續(xù)】

總結(jié)

以上是生活随笔為你收集整理的Apriori算法通俗讲解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。