數(shù)據(jù)挖掘算法Apriori算法

1、一、 算法概念引入什么是關(guān)聯(lián)規(guī)則按常規(guī)思維，尿布與啤酒風(fēng)馬牛不相及，若不是借助數(shù)據(jù)挖掘技術(shù)對(duì)大量交易數(shù)據(jù)進(jìn) 行挖掘分析，沃爾瑪是不可能發(fā)現(xiàn)數(shù)據(jù)內(nèi)在這一有價(jià)值的規(guī)律的。數(shù)據(jù)關(guān)聯(lián)是數(shù)據(jù)庫(kù)中存在的一類重要的可被發(fā)現(xiàn)的 知識(shí)。若兩個(gè)或多個(gè)變量的取值之間存在某種規(guī)律性，就 稱為關(guān)聯(lián)。關(guān)聯(lián)可分為簡(jiǎn)單關(guān)聯(lián)、時(shí)序關(guān)聯(lián)、因果關(guān)聯(lián)。 關(guān)聯(lián)分析的目的是找出數(shù)據(jù)庫(kù)中隱藏的關(guān)聯(lián)網(wǎng)。有時(shí)并不 知道數(shù)據(jù)庫(kù)中數(shù)據(jù)的關(guān)聯(lián)函數(shù)，即使知道也是不確定的， 因此關(guān)聯(lián)分析生成的規(guī)則帶有可信度。關(guān)聯(lián)規(guī)則挖掘發(fā)現(xiàn) 大量數(shù)據(jù)中項(xiàng)集之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系。Agrawal等于 1993年首先提出了挖掘顧客交易數(shù)據(jù)庫(kù)中項(xiàng)集間的關(guān)聯(lián)規(guī) 則問題，以后

2、諸多的研究人員對(duì)關(guān)聯(lián)規(guī)則的挖掘問題進(jìn)行了大量的研究。他們的工作包括對(duì) 原有的算法進(jìn)行優(yōu)化，如引入隨機(jī)采樣、并行的思想等，以提高算法挖掘規(guī)則的效率；對(duì)關(guān) 聯(lián)規(guī)則的應(yīng)用進(jìn)行推廣在數(shù)據(jù)挖掘中是一個(gè)重要的課題，最近幾年已被業(yè)界所廣泛研究。經(jīng)典案例1：尿布和啤酒的故事關(guān)于這個(gè)算法有一個(gè)非常有名的故事：尿布和啤酒。故事是這樣的：美國(guó)的婦女們經(jīng) 常會(huì)囑咐她們的丈夫下班后為孩子買尿布，而丈夫在買完尿布后又要順手買回自己愛喝的啤 酒，因此啤酒和尿布在一起被購(gòu)買的機(jī)會(huì)很多。這個(gè)舉措使尿布和啤酒的銷量雙雙增加，并 一直為眾商家所津津樂道。介紹案例2：床單和枕套的故事通過調(diào)查商場(chǎng)里顧客買的東西發(fā)現(xiàn)，30%的顧客會(huì)同時(shí)

3、購(gòu)買床單和枕套，而購(gòu)買床單的 人中有80%購(gòu)買了枕套，這里面就隱藏了一條關(guān)聯(lián)：床單一枕套，也就是說很大一部分顧 客會(huì)同時(shí)購(gòu)買床單和枕套，那么對(duì)于商場(chǎng)來說，可以把床單和枕套放在同一個(gè)購(gòu)物區(qū)，那樣 就方便顧客進(jìn)行購(gòu)物了。二、Apriori數(shù)據(jù)挖掘算法Apriori algorithm是關(guān)聯(lián)規(guī)則里一項(xiàng)基本算法。是由Rakesh Agrawal和Ramakrishna Srikant兩位博士在1994年提出的關(guān)聯(lián)規(guī)則挖掘算法。關(guān)聯(lián)規(guī)則的目的就是在一個(gè)數(shù)據(jù)集中找出項(xiàng)與項(xiàng)之間的關(guān)系，也被稱為購(gòu)物藍(lán)分析(Market Basket analysis)，因?yàn)椤百?gòu)物藍(lán)分析”很貼切的表達(dá)了適用該算法情景中的一個(gè)子

4、集。概念和定義1 ti&m s etS Lip .1rm卜Ir|目Y) = supp(X UY) /supp(X) =P(Y|X)。歷史數(shù)據(jù)中，已經(jīng)買了某某(例如：A、B)的支持度和經(jīng)過挖掘的某規(guī)則(例如： A=B)中A的支持度的比例，也就是說買了入和日的人和已經(jīng)買了入的人的比例，這就 是對(duì)A推薦B的置信度(A=B的置信度)候選集(Candidate itemset):通過向下合并得出的項(xiàng)集。定義為Ck。頻繁集(Frequent itemset):支持度大于等于特定的最小支持度(Minimum Support/minsup)的項(xiàng)集。表示為 Lk。注意，頻繁集的子集一定是頻繁集。提升比率(提升度

5、 Lift): lift(X - Y) = lift(Y - X) = conf(X - Y)/supp(Y) = conf(Y - X)/supp(X) = P(X and Y)/(P(X)P(Y)經(jīng)過關(guān)聯(lián)規(guī)則分析后，針對(duì)某些人推銷(根據(jù)某規(guī)則)比盲目推銷(一般來說是整個(gè)數(shù) 據(jù))的比率，這個(gè)比率越高越好，我們稱這個(gè)規(guī)則為強(qiáng)規(guī)則；剪枝步只有當(dāng)子集都是頻繁集的候選集才是頻繁集，這個(gè)篩選的過程就是剪枝步；概念和定義的案例說明先看一個(gè)簡(jiǎn)單的例子，假如有下面數(shù)據(jù)集，每一組數(shù)據(jù)ti表示不同的顧客一次在商場(chǎng) 購(gòu)買的商品的集合：tit.4牛肉、雞肉牛奶牛肉、蛆酪2奶酪、靴子彖牛肉、鴉肉、奶酪牛肉、器肉衣服奶

6、酷I牛奶尸雞肉、衣服、牛蛆雞肉、牛奶、衣服J假如有一條規(guī)則：牛肉一雞肉，那么同時(shí)購(gòu)買牛肉和雞肉的顧客比例是3/7 (支持度)， 而購(gòu)買牛肉的顧客當(dāng)中也購(gòu)買了雞肉的顧客比例是3/4 (置信度)。這兩個(gè)比例參數(shù)是很重 要的衡量指標(biāo)，它們?cè)陉P(guān)聯(lián)規(guī)則中稱作支持度(support)和置信度(confidence) o對(duì)于規(guī)則：牛肉一雞肉，它的支持度為3/7,表示在所有顧客當(dāng)中有3/7同時(shí)購(gòu)買牛 肉和雞肉，其反應(yīng)了同時(shí)購(gòu)買牛肉和雞肉的顧客在所有顧客當(dāng)中的覆蓋范圍；它的置信度為 3/4,表示在買了牛肉的顧客當(dāng)中有3/4的人買了雞肉，其反應(yīng)了可預(yù)測(cè)的程度，即顧客 買了牛肉的話有多大可能性買雞肉。從集合角度去看

7、這個(gè)問題，假如看作是概率問題，則可以把“顧客買了牛肉之后又多 大可能性買雞肉”看作是條件概率事件，而從集合的角度去看，可以看下面這幅圖：S表示所有的顧客，而A表示買了牛肉的 顧客，B表示買了雞肉的顧客，C表示既買了 牛肉又買了雞肉的顧客。那么C. /S,=3/7, C. /A,=3/4。count countcount count上述例子中的所有商品集合I=牛肉， 雞肉，牛奶，奶酪，靴子，衣服稱作項(xiàng)目集合，每位顧客一次購(gòu)買的商品集合ti稱為一個(gè)事務(wù)，所有的事務(wù)T=t1,t2,.t7稱作事務(wù) 集合，并且滿足ti是I的真子集。一條關(guān)聯(lián)規(guī)則是形如下面的蘊(yùn)含式：XY，X，Y滿足：X，Y是I的真子集，并

8、且X和Y的交集為空集其中X稱為前件，Y稱為后件。對(duì)于規(guī)則XY，上面例子可以知道它的支持度(support)=(X,Y).count/T.count，置 信度(confidence)=(X,Y).count/X.count。其中(X,Y).count 表示T 中同時(shí)包含X 和 Y 的 事務(wù)的個(gè)數(shù)，X.count表示T中包含X的事務(wù)的個(gè)數(shù)。關(guān)聯(lián)規(guī)則挖掘則是從事務(wù)集合中挖掘出滿足支持度和置信度最低閾值要求的所有關(guān)聯(lián) 規(guī)則，這樣的關(guān)聯(lián)規(guī)則也稱強(qiáng)關(guān)聯(lián)規(guī)則。對(duì)于支持度和置信度，我們需要正確地去看待這兩個(gè)衡量指標(biāo)。一條規(guī)則的支持度表示 這條規(guī)則的可能性大小，如果一個(gè)規(guī)則的支持度很小，則表明它在事務(wù)集合中覆蓋

9、范圍很小， 很有可能是偶然發(fā)生的；如果置信度很低，則表明很難根據(jù)乂推出丫。根據(jù)條件概率公式 P(Y|X)=P(X,Y)/P(X)，即 P(X,Y)=P(Y|X)*P(X)P(Y|X)代表著置信度，P(X,Y)代表著支持度，所以對(duì)于任何一條關(guān)聯(lián)規(guī)則置信度總是 大于等于支持度的。并且當(dāng)支持度很高時(shí)，此時(shí)的置信度肯定很高它所表達(dá)的意義就不是那么有用了這 里要注意的是支持度和置信度只是兩個(gè)參考值而已，不是絕對(duì)的，也就是說假如一條關(guān)聯(lián) 規(guī)則的支持度和置信度很高時(shí)，不代表這個(gè)規(guī)則之間就一定存在某種關(guān)聯(lián)。舉個(gè)最簡(jiǎn)單的例子，假如X和Y是最近的兩個(gè)比較熱門的商品，大家去商場(chǎng)都要買， 比如某款手機(jī)和某款衣服，都是

10、最新款的，深受大家的喜愛，那么這條關(guān)聯(lián)規(guī)則的支持度和 置信度都很高，但是它們之間沒有必然的聯(lián)系。然而當(dāng)置信度很高時(shí)，支持度仍然具有參考 價(jià)值，因?yàn)楫?dāng)P(Y|X)很高時(shí)，可能P(X)很低，此時(shí)P(X,Y)也許會(huì)很低。關(guān)聯(lián)規(guī)則挖掘的原理和過程從上面的分析可知，關(guān)聯(lián)規(guī)則挖掘是從事務(wù)集合中挖掘出這樣的關(guān)聯(lián)規(guī)則：它的支持度和置信度大于最低閾值(minsup,minconf)，這個(gè)閾值是由用戶指定 的。根據(jù)支持度=(X,Y)./T.，置信度=(X,Y)./X.，要想找出滿足條件的count countcount count關(guān)聯(lián)規(guī)則，首先必須找出這樣的集合F=X U Y，它滿足F.匚t minsup， 其中

11、F.count是T中包含F(xiàn)的事務(wù)的個(gè)數(shù)，然后再?gòu)腇中找出這樣的蘊(yùn)含式XY， 它滿足(X,Y). t/X. t minconf,并且X=F-Y。我們稱像F這樣的集合稱為頻繁 項(xiàng)目集，假疝0岸中的芫素個(gè)數(shù)為k，我們稱這樣的頻繁項(xiàng)目集為k-頻繁項(xiàng)目集，它是 項(xiàng)目集合I的子集。所以關(guān)聯(lián)規(guī)則挖掘可以大致分為兩步：從事務(wù)集合中找出頻繁項(xiàng)目集；從頻繁項(xiàng)目集合中生成滿足最低置信度的關(guān)聯(lián)規(guī)則。最出名的關(guān)聯(lián)規(guī)則挖掘算法是Apriori算法，它主要利用了向下封閉屬性：如果一 個(gè)項(xiàng)集是頻繁項(xiàng)目集，那么它的非空子集必定是頻繁項(xiàng)目集。它先生成1-頻繁項(xiàng)目集， 再利用1-頻繁項(xiàng)目集生成2-頻繁項(xiàng)目集。然后根據(jù)2-頻繁項(xiàng)目集

12、生成3-頻繁項(xiàng)目 集。依次類推，直至生成所有的頻繁項(xiàng)目集，然后從頻繁項(xiàng)目集中找出符合條件的 關(guān)聯(lián)規(guī)則。下面來討論一下頻繁項(xiàng)目集的生成過程，它的原理是根據(jù)蚪頻繁項(xiàng)目集生成(k+1) -頻繁項(xiàng)目集。因此首先要做的是找出1-頻繁項(xiàng)目集，這個(gè)很容易得到，只要循環(huán)掃描 一次事務(wù)集合統(tǒng)計(jì)出項(xiàng)目集合中每個(gè)元素的支持度，然后根據(jù)設(shè)定的支持度閾值進(jìn)行篩 選，即可得到1-頻繁項(xiàng)目集。下面證明一下為何可以通過k-頻繁項(xiàng)目集生成(k+1)- 頻繁項(xiàng)目集：假設(shè)某個(gè)項(xiàng)目集S=s，s .，s是頻繁項(xiàng)目集，那么它的(n-1)非空子集s， TOC o 1-5 h z 12n1s，.s ，s，s，.s s .s，s，.s 必定都

13、是頻繁項(xiàng)目集，通過觀察，任何 2n-112n-2， n 23n一個(gè)含有n個(gè)元素的集合A=a，a，.a，它的(n-1)非空子集必行包含兩項(xiàng)a，12n1a，.a ，a 和a，a，.a ，a ，對(duì)比這兩個(gè)子集可以發(fā)現(xiàn)，它們的前。-2)2n-2n-112n-2 n項(xiàng)是相同的，它們的并集就是集合A。對(duì)于2-頻繁項(xiàng)目集，它的所有1非空子集也必 定是頻繁項(xiàng)目集，那么根據(jù)上面的性質(zhì)，對(duì)于2-頻繁項(xiàng)目集中的任一個(gè)，在1-頻繁項(xiàng) 目集中必定存在2個(gè)集合的并集與它相同。因此在所有的1-頻繁項(xiàng)目集中找出只有最 后一項(xiàng)不同的集合，將其合并，即可得到所有的包含2個(gè)元素的項(xiàng)目集，得到的這些包 含2個(gè)元素的項(xiàng)目集不一定都是頻

14、繁項(xiàng)目集，所以需要進(jìn)行剪枝。剪枝的辦法是看它的 所有1非空子集是否在1-頻繁項(xiàng)目集中，如果存在1非空子集不在1-頻繁項(xiàng)目集中， 則將該2項(xiàng)目集剔除。經(jīng)過該步驟之后，剩下的則全是頻繁項(xiàng)目集，即2-頻繁項(xiàng)目集。 依次類推，可以生成3-頻繁項(xiàng)目集。直至生成所有的頻繁項(xiàng)目集。得到頻繁項(xiàng)目集之后，則需要從頻繁項(xiàng)目集中找出符合條件的關(guān)聯(lián)規(guī)則。最簡(jiǎn)單的 辦法是：遍歷所有的頻繁項(xiàng)目集，然后從每個(gè)項(xiàng)目集中依次取1、2、.k個(gè)元素作為 后件，該項(xiàng)目集中的其他元素作為前件，計(jì)算該規(guī)則的置信度進(jìn)行篩選即可。這樣的窮 舉效率顯然很低。假如對(duì)于一個(gè)頻繁項(xiàng)目集f，可以生成下面這樣的關(guān)聯(lián)規(guī)則： (f-6)一6那么這條規(guī)則的置

15、信度=土t/(f-6). t根據(jù)這個(gè)置信度計(jì)算公式可知，對(duì)于一個(gè)頻繁項(xiàng)目集f_nt是不變的，而假設(shè)該規(guī) 則是強(qiáng)關(guān)聯(lián)規(guī)則，則(f-6 b)一6 b也是強(qiáng)關(guān)聯(lián)規(guī)則，其中蒞b是6的子集，因?yàn)?f-6 b). t肯定小于(f-6).即給定一個(gè)頻繁項(xiàng)目集f，如果一藁強(qiáng)關(guān)聯(lián)規(guī)則的后件為6,那么H以&的非空子集為后洋的關(guān)聯(lián)規(guī)則都是強(qiáng)關(guān)聯(lián)規(guī)則。所以可以先生成所有的1-后件 (后件只有一項(xiàng))強(qiáng)關(guān)聯(lián)規(guī)則，然后再生成2-后件強(qiáng)關(guān)聯(lián)規(guī)則，依次類推，直至生成 所有的強(qiáng)關(guān)聯(lián)規(guī)則。下面舉例說明Apiori算法的具體流程：假如有項(xiàng)目集合1=1，2, 3, 4, 5，有事務(wù)集T：1,2,31,2,41,3,41,2,3,51,

16、3,52,4,51,2,3,4命定 minsup=3/7 , misconf=5/7。首先：生成頻繁項(xiàng)目集：1-頻繁項(xiàng)目集：1，3，4，5生成2-頻繁項(xiàng)目集：根據(jù)1-頻繁項(xiàng)目集生成所有的包含2個(gè)元素的項(xiàng)目集：任意取兩個(gè)只有最后一個(gè)元素不同 的1-頻繁項(xiàng)目集，求其并集，由于每個(gè)1-頻繁項(xiàng)目集元素只有一個(gè)，所以生成的項(xiàng)目集如下：1，2，1，3，1，4，1，52,3，2,4，2, 53,4，3, 54,5計(jì)算它們的支持度，發(fā)現(xiàn)只有1，2，1，3，1，4，2,3，2,4，2,5的支持度 滿足要求，因此求得2-頻繁項(xiàng)目集：1，2，1，3，1，4，2,3，2,4生成3-頻繁項(xiàng)目集：因?yàn)?，2，1，3，1，

17、4除了最后一個(gè)元素以外都相同，所以求1，2，1，3的并集 得到1，2,3，1，2和1，4的并集得到1，2,4，1，3和1，4的并集得到1，3,4。 但是由于1，3，4的子集3，4不在2-頻繁項(xiàng)目集中，所以需要把1，3，4剔除掉。然后再來 計(jì)算1，2，3和1，2，4的支持度，發(fā)現(xiàn)1，2，3的支持度為3/7，1，2,4的支持度為 2/7，所以需要把1，2，4剔除。同理可以對(duì)2，3，2,4求并集得到2，3,4，但是2， 3,4的支持度不滿足要求，所以需要剔除掉。因此得到3-頻繁項(xiàng)目集：1，2,3。到此頻繁項(xiàng)目集生成過程結(jié)束。注意生成頻繁項(xiàng)目集的時(shí)候，頻繁項(xiàng)目集中的元素個(gè)數(shù)最大 值為事務(wù)集中事務(wù)中含有的最大元素個(gè)數(shù)，即若事務(wù)集中事務(wù)包含的最大元素個(gè)數(shù)為k，那么最 多能生成k-頻繁項(xiàng)目集，這個(gè)原因很簡(jiǎn)單，因?yàn)槭聞?wù)集合中的所有事務(wù)都不