數(shù)據(jù)挖掘ppt3 第三章 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則分析目錄背景基本概念關(guān)聯(lián)規(guī)則挖掘過(guò)程Apriori算法FP-Growth算法關(guān)聯(lián)規(guī)則評(píng)價(jià)

“尿布與啤酒”——典型關(guān)聯(lián)分析案例

采用關(guān)聯(lián)規(guī)則比較典型的案例是“尿布與啤酒”的故事。在美國(guó)，一些年輕的父親下班后經(jīng)常要到超市去買(mǎi)嬰兒尿布，超市也因此發(fā)現(xiàn)了一個(gè)規(guī)律，在購(gòu)買(mǎi)嬰兒尿布的年輕父親們中，有30%～40%的人同時(shí)要買(mǎi)一些啤酒。超市隨后調(diào)整了貨架的擺放，把尿布和啤酒放在一起，明顯增加了銷(xiāo)售額。同樣的，我們還可以根據(jù)關(guān)聯(lián)規(guī)則在商品銷(xiāo)售方面做各種促銷(xiāo)活動(dòng)。

怎么會(huì)出現(xiàn)這種情況呢？“啤酒和尿布”的故事是營(yíng)銷(xiāo)屆的神話(huà)，“啤酒”和“尿布”兩個(gè)看上去沒(méi)有關(guān)系的商品擺放在一起進(jìn)行銷(xiāo)售、并獲得了很好的銷(xiāo)售收益，這種現(xiàn)象就是賣(mài)場(chǎng)中商品之間的關(guān)聯(lián)性，研究“啤酒與尿布”關(guān)聯(lián)的方法就是購(gòu)物籃分析，購(gòu)物籃分析是沃爾瑪秘而不宣的獨(dú)門(mén)武器，購(gòu)物籃分析可以幫助我們?cè)陂T(mén)店的銷(xiāo)售過(guò)程中找到具有關(guān)聯(lián)關(guān)系的商品，并以此獲得銷(xiāo)售收益的增長(zhǎng)！

背景

關(guān)聯(lián)規(guī)則最初提出的動(dòng)機(jī)是針對(duì)購(gòu)物籃分析(MarketBasketAnalysis)問(wèn)題提出的。

假設(shè)分店經(jīng)理想更多的了解顧客的購(gòu)物習(xí)慣。特別是，想知道哪些商品顧客可能會(huì)在一次購(gòu)物時(shí)同時(shí)購(gòu)買(mǎi)？為回答該問(wèn)題，可以對(duì)商店的顧客事物零售數(shù)量進(jìn)行購(gòu)物籃分析。

該過(guò)程通過(guò)發(fā)現(xiàn)顧客放入“購(gòu)物籃”中的不同商品之間的關(guān)聯(lián)，分析顧客的購(gòu)物習(xí)慣。這種關(guān)聯(lián)的發(fā)現(xiàn)可以幫助零售商了解哪些商品頻繁的被顧客同時(shí)購(gòu)買(mǎi)，從而幫助他們開(kāi)發(fā)更好的營(yíng)銷(xiāo)策略。目錄背景基本概念關(guān)聯(lián)規(guī)則挖掘過(guò)程Apriori算法FP-Growth算法關(guān)聯(lián)規(guī)則評(píng)價(jià)

基本概念

設(shè)I={i1,

i2,…,im}是項(xiàng)(Item)的集合。

D是事務(wù)(Transaction)的集合(事務(wù)數(shù)據(jù)庫(kù))。

事務(wù)T是項(xiàng)的集合，且對(duì)于每一個(gè)事務(wù)具有唯一的標(biāo)識(shí)：事務(wù)號(hào)，記作TID。

設(shè)A是I中的一個(gè)項(xiàng)集，如果A?T，那么事務(wù)T包含A。

基本概念

項(xiàng)目（item）：其中的可樂(lè)，薯片，面包，啤酒，尿布都稱(chēng)作item。項(xiàng)集（itemset）：item的集合，例如{可樂(lè)，薯片}，{可樂(lè)，面包}等，每個(gè)顧客購(gòu)買(mǎi)的都是一個(gè)項(xiàng)集。其中，項(xiàng)集中item的個(gè)數(shù)稱(chēng)為項(xiàng)集的長(zhǎng)度，含有k個(gè)item的項(xiàng)集稱(chēng)為K-itemset。

基本概念定義1：關(guān)聯(lián)規(guī)則：

關(guān)聯(lián)規(guī)則是形如A->B的邏輯蘊(yùn)含式，其中A,B都不為空，且A?I，B?I，并且A

B=

。

基本概念定義2：支持度（Support）：支持度描述了A和B這兩個(gè)物品集在所有的事物中同時(shí)出現(xiàn)的概率有多大。規(guī)則A->B在數(shù)據(jù)庫(kù)D中具有支持度S，即概率P(AB),即其中|D|表示事物數(shù)據(jù)庫(kù)D的個(gè)數(shù)，|AB|表示A、B兩個(gè)項(xiàng)集同時(shí)發(fā)生的事物個(gè)數(shù)。

基本概念【例1】表3.1所示的商店事務(wù)數(shù)據(jù)，顧客購(gòu)買(mǎi)可樂(lè)又購(gòu)買(mǎi)薯片有1筆，顧客購(gòu)買(mǎi)可樂(lè)又購(gòu)買(mǎi)面包有3筆，則可樂(lè)和薯片同時(shí)出現(xiàn)的次數(shù)是1，事務(wù)數(shù)據(jù)庫(kù)一共有5條數(shù)據(jù),所以可樂(lè)和薯片的關(guān)聯(lián)規(guī)則的支持度?？蓸?lè)和面包的支持度

基本概念定義3：置信度（confidence）：置信度就是指在出現(xiàn)了物品集A的事物T中，物品集B也同時(shí)出現(xiàn)的概率。

規(guī)則A->B具有置信度C，表示C是是包含A項(xiàng)集的同時(shí)也包含B項(xiàng)集的概率，即P(B|A),所以其中|A|表示數(shù)據(jù)庫(kù)中包含項(xiàng)集A的事務(wù)個(gè)數(shù)。

基本概念【例2】表3.1所示的商店事務(wù)數(shù)據(jù)，顧客購(gòu)買(mǎi)可樂(lè)有4筆，顧客購(gòu)買(mǎi)可樂(lè)又購(gòu)買(mǎi)薯片有1筆，顧客購(gòu)買(mǎi)可樂(lè)又購(gòu)買(mǎi)面包有3筆，那么購(gòu)買(mǎi)可樂(lè)又會(huì)購(gòu)買(mǎi)薯片的置信度，購(gòu)買(mǎi)可樂(lè)又會(huì)購(gòu)買(mǎi)面包的置信度。這說(shuō)明買(mǎi)可樂(lè)也會(huì)買(mǎi)面包的關(guān)聯(lián)性比薯片強(qiáng)，營(yíng)銷(xiāo)上可以做一些組合策略銷(xiāo)售。

基本概念 規(guī)則的支持度和置信度是規(guī)則興趣度的兩種度量。支持度是對(duì)關(guān)聯(lián)規(guī)則重要性的衡量，置信度是對(duì)關(guān)聯(lián)規(guī)則的準(zhǔn)確度的衡量，支持度說(shuō)明了這條規(guī)則在所有事務(wù)中有多大代表性。

顯然支持度越大，關(guān)聯(lián)規(guī)則越重要。有些關(guān)聯(lián)規(guī)則置信度雖然很高，但支持度卻很低，說(shuō)明該關(guān)聯(lián)規(guī)則實(shí)用的機(jī)會(huì)很小，因此也不重要。

可樂(lè)和面包同時(shí)出現(xiàn)的次數(shù)是3，事務(wù)數(shù)據(jù)庫(kù)一共有5條數(shù)據(jù)。故Support(可樂(lè)->面包)=3/5;可樂(lè)和面包同時(shí)出現(xiàn)的個(gè)數(shù)是3，可樂(lè)單獨(dú)出現(xiàn)的次數(shù)為4.故Confidence(可樂(lè)->面包)=3/4;

基本概念定義4：強(qiáng)關(guān)聯(lián)規(guī)則： D

在I上滿(mǎn)足最小支持度和最小可信度的關(guān)聯(lián)規(guī)則稱(chēng)為強(qiáng)關(guān)聯(lián)規(guī)則。

通常所說(shuō)的關(guān)聯(lián)規(guī)則一般指上面定義的強(qiáng)關(guān)聯(lián)規(guī)則。

基本概念定義5：提升度Lift：

提升度表示A項(xiàng)集的出現(xiàn)，對(duì)B項(xiàng)集的出現(xiàn)有多大影響。

公式反映了項(xiàng)集A和項(xiàng)集B的相關(guān)程度。若I(A->B)=1即P(AB)=P(A)P(B)，說(shuō)明項(xiàng)集A和項(xiàng)集B是相互獨(dú)立的。若I(A->B)<1說(shuō)明項(xiàng)集A和項(xiàng)集B是負(fù)相關(guān)的。若I(A->B)>1說(shuō)明項(xiàng)集A和項(xiàng)集B是正相關(guān)的。

關(guān)聯(lián)規(guī)則挖掘基本過(guò)程關(guān)聯(lián)規(guī)則挖掘問(wèn)題就是根據(jù)用戶(hù)指定的最小支持度和最小置信度來(lái)尋找強(qiáng)關(guān)聯(lián)規(guī)則。頻繁項(xiàng)集：滿(mǎn)足最小支持度的項(xiàng)集稱(chēng)為頻繁項(xiàng)集。頻繁k-項(xiàng)集的集合通常記作Lk。關(guān)聯(lián)規(guī)則挖掘問(wèn)題可以劃分成兩個(gè)子問(wèn)題：1.發(fā)現(xiàn)頻繁項(xiàng)目集:通過(guò)用戶(hù)給定最小支持度，尋找所有頻繁項(xiàng)目集或者最大頻繁項(xiàng)目集。2.生成關(guān)聯(lián)規(guī)則:通過(guò)用戶(hù)給定最小可信度，在頻繁項(xiàng)目集中，尋找關(guān)聯(lián)規(guī)則。關(guān)于支持度和置信度描述正確的是（）支持度是項(xiàng)集頻度表示，置信度是規(guī)則的準(zhǔn)確度支持度是規(guī)則準(zhǔn)確性表示，置信度是項(xiàng)集頻度表示支持度是規(guī)則準(zhǔn)確性表示，置信度是重要性體現(xiàn)ABCD提交單選題1分

Apriori算法項(xiàng)目集格空間理論定理：設(shè)X,Y是數(shù)據(jù)集D中的項(xiàng)集：

（1）若X?Y，則Support(X)>=Support(Y)。

（2）若X?Y，如果X是非頻繁項(xiàng)集，則Y也是非頻繁項(xiàng)集。

（3）若X?Y，如果Y是頻繁項(xiàng)集，則X也是頻繁項(xiàng)集。性質(zhì)：1.任何頻繁項(xiàng)集的子集都是頻繁項(xiàng)集。2.任何非頻繁項(xiàng)集的超集都為非頻繁項(xiàng)集。3.任何頻繁k項(xiàng)集都是由頻繁k?1項(xiàng)集組合生成的4.頻繁k項(xiàng)集的所有k?1項(xiàng)子集一定都是頻繁k?1項(xiàng)集Apriori算法一個(gè)項(xiàng)集，如果有至少一個(gè)非空子集是非頻繁的，那么這個(gè)項(xiàng)集一定是非頻繁的。即，如果一個(gè)項(xiàng)集是非頻繁的，則它所有的超集都是非頻繁的，這種基于支持度度量修剪指數(shù)搜索空間的策略稱(chēng)為基于支持度的剪枝（support-basedpruning）這種剪枝策略依賴(lài)于支持度度量的一個(gè)關(guān)鍵性質(zhì)，即一個(gè)項(xiàng)集的支持度決不會(huì)超過(guò)它的子集的支持度。這個(gè)性質(zhì)也稱(chēng)為支持度度量的反單調(diào)性（anti-monotone）。該算法使用一種逐層搜索的迭代方法，即從頻繁1-項(xiàng)集到最長(zhǎng)的頻繁項(xiàng)集，它每次遍歷項(xiàng)集格中的一層，利用k-項(xiàng)集探索(k+1)-項(xiàng)集。

Apriori算法

具體做法：首先通過(guò)掃描數(shù)據(jù)庫(kù)，累計(jì)每個(gè)項(xiàng)的計(jì)數(shù)，并收集滿(mǎn)足最小支持度的項(xiàng)，找出頻繁1-項(xiàng)集的集合，記為L(zhǎng)1；再用L1找頻繁2-項(xiàng)集的集合L2；再用L2找L3…如此下去，直到不能找到頻繁k-項(xiàng)集為止。找出每個(gè)Lk需要一次數(shù)據(jù)庫(kù)的完整掃描。

格結(jié)構(gòu)

常常用來(lái)表示所有可能的項(xiàng)集。從中可以看出頻繁項(xiàng)集的搜索空間是指數(shù)搜索空間，隨著事務(wù)數(shù)據(jù)庫(kù)中項(xiàng)的增加，候選項(xiàng)集和比較次數(shù)都指數(shù)級(jí)增長(zhǎng)，計(jì)算復(fù)雜度很高。下圖為項(xiàng)集I={a,b,c,d,e}的格集圖

頻繁項(xiàng)集的所有非空子集也一定是頻繁的

說(shuō)明：這個(gè)概念很容易理解了，比如一個(gè)項(xiàng)集{I1,I2,I3}是頻繁的，那么，說(shuō)明這三個(gè)項(xiàng)同時(shí)出現(xiàn)的次數(shù)是大于最小支持度計(jì)數(shù)的，所以，我們可以推知，他的任何非空子集，{I1},{I2,I3}等等的支持度計(jì)數(shù)也一定比預(yù)先定義的閾值要大，故而都是頻繁的。

格結(jié)構(gòu)

先驗(yàn)原理:

如圖所示，如果{c，d，e}是頻繁的，則它的所有子集也是頻繁的。

例子：

非頻繁項(xiàng)集被剪枝的超集

Apriori算法步驟分為兩個(gè)步驟：第一步通過(guò)迭代，檢索出事務(wù)數(shù)據(jù)庫(kù)中的所有頻繁項(xiàng)集，即支持度不低于用戶(hù)設(shè)定的閾值的項(xiàng)集；第二步利用頻繁項(xiàng)集構(gòu)造出滿(mǎn)足用戶(hù)最小信任度的規(guī)則。

Apriori算法頻繁項(xiàng)集產(chǎn)生Apriori算法的頻繁項(xiàng)集產(chǎn)生的部分有兩個(gè)重要的特點(diǎn)：它是一個(gè)逐層算法。即從頻繁1-項(xiàng)集到最長(zhǎng)的頻繁項(xiàng)集，它每次遍歷項(xiàng)集格中的一層它使用產(chǎn)生-測(cè)試策略來(lái)發(fā)現(xiàn)頻繁項(xiàng)集。在每次迭代，新的候選項(xiàng)集由前一次迭代發(fā)現(xiàn)的頻繁項(xiàng)集產(chǎn)生，然后對(duì)每個(gè)候選的支持度進(jìn)行計(jì)數(shù)，并與最小支持度閾值進(jìn)行比較。該算法需要的總迭代次數(shù)是kmax+1，其中kmax是頻繁項(xiàng)集的最大長(zhǎng)度。該環(huán)節(jié)可由連接、剪枝和掃描篩選這三步組成，連接和剪枝來(lái)產(chǎn)生候選項(xiàng)集，通過(guò)掃描篩選來(lái)實(shí)現(xiàn)進(jìn)一步的刪除小于支持度閾值的項(xiàng)集。

概念：連接步：要從k-1項(xiàng)集找出k項(xiàng)集，通過(guò)k-1項(xiàng)集與自身連接產(chǎn)生候選k項(xiàng)集合。若p1和p2項(xiàng)集中，只有一項(xiàng)是不同的，那么可以認(rèn)為p1p2是可連接的，剪枝步：從第k-1項(xiàng)生成第k項(xiàng)之后要從第k項(xiàng)中刪去子集不為頻繁項(xiàng)的k項(xiàng)集

，即支持度<最小支持度數(shù)的候選集。掃描事務(wù)數(shù)據(jù)庫(kù)：因?yàn)楫?dāng)前候選頻繁k項(xiàng)集Ck中仍然可能存在支持度小于支持度閾值min_sup的項(xiàng)集，所以需要做進(jìn)一步篩選。

具體做法：

首先掃描全部數(shù)據(jù)，產(chǎn)生候選項(xiàng)1項(xiàng)集的集合C1，根據(jù)最小支持度，由候選1項(xiàng)集的集合C1產(chǎn)生頻繁1-項(xiàng)集，記為L(zhǎng)1。然后利用L1連接來(lái)產(chǎn)生候選項(xiàng)集C2，對(duì)C2中的項(xiàng)進(jìn)行判定挖掘出L2，即頻繁2-項(xiàng)集；（刪除C2中那些支持度小于最小支持度的項(xiàng)）不斷如此循環(huán)下去直到無(wú)法發(fā)現(xiàn)更多的頻繁k-項(xiàng)集為止。每挖掘一層Lk就需要掃描整個(gè)數(shù)據(jù)庫(kù)一遍。

Apriori算法例子

交易數(shù)據(jù)表如下（假設(shè)給定的最小支持度為2,最小置信度為0.6）

交易號(hào)碼商品100可樂(lè)雞蛋漢堡200可樂(lè)尿布啤酒300可樂(lè)尿布啤酒漢堡400尿布啤酒項(xiàng)集支持度計(jì)數(shù)可樂(lè)3雞蛋1尿布3啤酒3漢堡2C1項(xiàng)集支持度計(jì)數(shù)可樂(lè)3尿布3啤酒3漢堡2根據(jù)最小支持度計(jì)數(shù)，生成頻繁1項(xiàng)集L1項(xiàng)集可樂(lè)尿布可樂(lè)啤酒可樂(lè)漢堡尿布啤酒尿布漢堡啤酒漢堡由L1生成候選2項(xiàng)集項(xiàng)集支持度計(jì)數(shù)可樂(lè)尿布2可樂(lè)啤酒2可樂(lè)漢堡2尿布啤酒3尿布漢堡1啤酒漢堡1掃描D，對(duì)每個(gè)候選2項(xiàng)集計(jì)數(shù)L1C2項(xiàng)集支持度計(jì)數(shù)可樂(lè)尿布2可樂(lè)啤酒2可樂(lè)漢堡2尿布啤酒3根據(jù)支持度計(jì)數(shù)，生成頻繁-2項(xiàng)集L2項(xiàng)集可樂(lè)尿布啤酒由L2生成候選集3項(xiàng)集C3項(xiàng)集支持度計(jì)數(shù)可樂(lè)尿布啤酒2掃描D，對(duì)每個(gè)候選3項(xiàng)集計(jì)數(shù)C3項(xiàng)集支持度計(jì)數(shù)可樂(lè)尿布啤酒2L3根據(jù)最小支持度計(jì)數(shù)，生成頻繁3項(xiàng)集為什么沒(méi)有{可樂(lè),尿布,漢堡}或者{可樂(lè),啤酒,漢堡}這兩個(gè)項(xiàng)集呢？根據(jù)性質(zhì)1，{尿布,漢堡}和{啤酒,漢堡}這兩個(gè)子項(xiàng)集不是頻繁的上述過(guò)程得到各級(jí)頻繁項(xiàng)集，下面進(jìn)入第二個(gè)階段：產(chǎn)生關(guān)聯(lián)規(guī)則由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則產(chǎn)生步驟如下：1）

對(duì)于每個(gè)頻繁項(xiàng)集l，產(chǎn)生其所有非空真子集；2）

對(duì)于每個(gè)非空真子集s,如果 >=min_conf，

則輸出

A->B，其中，min_conf是最小置信度閾值。

例如，在上述例子中，頻繁3項(xiàng)集{可樂(lè)，啤酒，尿布}。頻繁2項(xiàng)集有{可樂(lè)，尿布}，{可樂(lè)，啤酒}，{可樂(lè)，漢堡}，{尿布，啤酒}

可以產(chǎn)生哪些關(guān)聯(lián)規(guī)則？

頻繁2項(xiàng)集：{可樂(lè)，尿布}生成強(qiáng)規(guī)則過(guò)程如下：{可樂(lè)，尿布}的非空真子集{可樂(lè)}{尿布}

C(可樂(lè)=>尿布)=2/3>0.6C(尿布=>可樂(lè))=2/3>0.6

都大于最小置信值，所以規(guī)則可樂(lè)=>尿布和尿布=>可樂(lè)都是強(qiáng)關(guān)聯(lián)規(guī)則。

同理計(jì)算頻繁2項(xiàng)集{可樂(lè),啤酒}生成的強(qiáng)關(guān)聯(lián)規(guī)則：

C(可樂(lè)=>啤酒)=2/3>0.6 C(啤酒=>可樂(lè))=2/3>0.6

都大于最小置信值，所以規(guī)則可樂(lè)=>啤酒和啤酒=>可樂(lè)都是強(qiáng)關(guān)聯(lián)規(guī)則。

同理計(jì)算頻繁2項(xiàng)集{可樂(lè),漢堡}生成的強(qiáng)關(guān)聯(lián)規(guī)則：

C(可樂(lè)=>漢堡)=2/3>0.6 C(漢堡=>可樂(lè))=1>0.6

都大于最小置信值，所以規(guī)則可樂(lè)=>漢堡和漢堡=>可樂(lè)都是強(qiáng)關(guān)聯(lián)規(guī)則。

同理計(jì)算頻繁2項(xiàng)集{尿布,漢堡}生成的強(qiáng)關(guān)聯(lián)規(guī)則：

C(尿布=>漢堡)=1>0.6 C(漢堡=>尿布)=2/3>0.6

都大于最小置信值，所以規(guī)則尿布=>漢堡和漢堡=>尿布都是強(qiáng)關(guān)聯(lián)規(guī)則。

頻繁3項(xiàng)集：{可樂(lè),尿布,啤酒}生成強(qiáng)規(guī)則過(guò)程如下：

非空真子集{可樂(lè)},{尿布},{啤酒},{可樂(lè),尿布},{尿布,啤酒},{可樂(lè),啤酒}

分別進(jìn)行計(jì)算： C(啤酒=>{可樂(lè),尿布})=p({啤酒,可樂(lè),尿布})/P(啤酒)=2/3 C(可樂(lè)=>{啤酒,尿布})=P(啤酒,尿布,可樂(lè))/P(可樂(lè))=2/3 C(尿布=>{啤酒,可樂(lè)})=P(啤酒,尿布,可樂(lè))/P(尿布)=2/3 C({尿布,可樂(lè)}=>啤酒)=2/2=1 C({啤酒,尿布}=>可樂(lè))=2/3 C({啤酒,可樂(lè)}=>尿布)=2/2=1

因此都為強(qiáng)規(guī)則。方法：

L1=find_frequent_1-itemsets(D);//

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

For(k=2;Lk-1!=null;k++){

Ck=apriori_gen(Lk-1);//

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

Foreach

事務(wù)tinD{//

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

Ct

=subset(Ck,t);//

得到t的子集

Foreach

候選c

屬于

Ct

c.count++;

}

Lk={c屬于Ck

|c.count>=min_sup}ReturnL=所有的頻繁集；

Procedureapriori_gen(Lk-1:frequent(k-1)-itemsets)

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

Foreach項(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)生候選

ifhas_infrequent_subset(c,Lk-1)then

deletec;//剪枝步：刪除非頻繁候選

elseaddctoCk;

}

ReturnCk;

Procedurehas_infrequent_sub(c:candidatek-itemset;Lk-1:frequent(k-1)-itemsets)

Foreach(k-1)-subsetsofc

Ifs不屬于Lk-1

then

Returntrue;

Returnfalse;輸入：D-

事務(wù)數(shù)據(jù)庫(kù)；min_sup-

最小支持度計(jì)數(shù)閾值輸出：L-D中的頻繁項(xiàng)集

Apriori算法的特點(diǎn)Apriori算法是應(yīng)用最廣泛的關(guān)聯(lián)規(guī)則挖掘算法，它有如下優(yōu)點(diǎn)：1）Apriori算法是一個(gè)迭代算法。2）數(shù)據(jù)采用水平組織方式。3）采用Apriori優(yōu)化方法。4）適合事務(wù)數(shù)據(jù)庫(kù)的關(guān)聯(lián)規(guī)則挖掘。5）適合稀疏數(shù)據(jù)集。

優(yōu)點(diǎn)

Apriori算法的特點(diǎn)Apriori算法有如下缺點(diǎn)：1）多次掃描事務(wù)數(shù)據(jù)庫(kù),需要很大的I/O負(fù)載。對(duì)每個(gè)k=1,2，…,m，為了計(jì)算候選k-項(xiàng)集的支持度，都需要掃描一次事務(wù)數(shù)據(jù)庫(kù)，才能確定候選k-項(xiàng)集的支持度，其計(jì)算時(shí)間開(kāi)銷(xiāo)很大。2）可能產(chǎn)生龐大的候選集。例如，當(dāng)事務(wù)數(shù)據(jù)庫(kù)有104個(gè)頻繁1-項(xiàng)集時(shí)，Apriori算法就需要產(chǎn)生多達(dá)107個(gè)候選2-項(xiàng)集，即對(duì)存儲(chǔ)空間要求會(huì)影響算法的執(zhí)行效率。3）候選項(xiàng)集支持度計(jì)算量大，尤其在頻繁項(xiàng)目集長(zhǎng)度變大的情況下,運(yùn)算時(shí)間顯著增加。

缺點(diǎn)Apriori算法的特點(diǎn)改進(jìn)的Apriori大體思路：1）減少交易數(shù)據(jù)庫(kù)的掃描次數(shù)。2）減少候選項(xiàng)集的數(shù)量。3）提高候選頻繁項(xiàng)支持度計(jì)算效率。

改進(jìn)關(guān)聯(lián)規(guī)則挖掘的基本過(guò)程包括兩部分（）尋找頻繁項(xiàng)集挖掘強(qiáng)關(guān)聯(lián)規(guī)則計(jì)算提升度規(guī)則價(jià)值分析ABCD提交多選題1分

FP-Growth算法

Apriori算法候選集產(chǎn)生的時(shí)空復(fù)雜度都比較高，特別是每計(jì)算一次候選K項(xiàng)集的支持度就需要掃描一遍事務(wù)數(shù)據(jù)庫(kù)。 JiaweiHan等人在2000年提出了一種試圖這樣做的有趣的方法,叫頻繁模式增長(zhǎng)算法（FrequentPatternGrowth：FP-Growth）。

簡(jiǎn)介

FP-Growth算法是基于Apriori原理提出的關(guān)聯(lián)分析算法，它采取分治策略，將提供頻繁項(xiàng)集的數(shù)據(jù)庫(kù)壓縮到一棵頻繁模式樹(shù)（FrequentPatternTree：FP-tree），并保留項(xiàng)集關(guān)聯(lián)信息。

然后，把這種壓縮后的數(shù)據(jù)庫(kù)劃分成一組條件數(shù)據(jù)庫(kù)，每個(gè)數(shù)據(jù)庫(kù)關(guān)聯(lián)一個(gè)頻繁項(xiàng)或“模式段”，并分別挖掘每個(gè)條件數(shù)據(jù)庫(kù)。

過(guò)程 FP-growth算法發(fā)現(xiàn)頻繁項(xiàng)集的過(guò)程：

(1)構(gòu)建FP樹(shù)；

(2)從FP樹(shù)中挖掘頻繁項(xiàng)集。

FP-Tree：將事務(wù)數(shù)據(jù)表中的各個(gè)事務(wù)數(shù)據(jù)項(xiàng)按照支持度排序后，把每個(gè)事務(wù)中的數(shù)據(jù)項(xiàng)按降序依次插入到一棵以

NULL為根結(jié)點(diǎn)的樹(shù)中，同時(shí)在每個(gè)結(jié)點(diǎn)處記錄該結(jié)點(diǎn)出現(xiàn)的支持度。

條件模式基：包含在FP-Tree中與后綴模式一起出現(xiàn)的前綴路徑的集合，也就是同一個(gè)頻繁項(xiàng)在FP樹(shù)中的所有節(jié)點(diǎn)的祖先路徑的集合。

條件樹(shù)：將條件模式基按照FP-Tree的構(gòu)造原則形成的一個(gè)新的FP-Tree子樹(shù)。

具體步驟如下1.第一次掃描事務(wù)數(shù)據(jù)庫(kù)，得到頻繁1項(xiàng)集，并按支持度降序排序。2.刪掉不滿(mǎn)足設(shè)定最小支持度的項(xiàng)。3.第二次掃描數(shù)據(jù)庫(kù)，剔除掉原始數(shù)據(jù)中非頻繁1項(xiàng)集，并將原始數(shù)據(jù)按支持度降序排序。4.構(gòu)造FP樹(shù)：讀入排序后的數(shù)據(jù)集，插入FP樹(shù)，插入時(shí)按照排序后的順序，插入FP樹(shù)中，排序靠前的節(jié)點(diǎn)是祖先節(jié)點(diǎn)，而靠后的是子孫節(jié)點(diǎn)。如果有共用的祖先，則對(duì)應(yīng)的公用祖先節(jié)點(diǎn)計(jì)數(shù)加1。插入后，如果有新節(jié)點(diǎn)出現(xiàn)，則項(xiàng)頭表對(duì)應(yīng)的節(jié)點(diǎn)會(huì)通過(guò)節(jié)點(diǎn)鏈表鏈接上新節(jié)點(diǎn)。直到所有的數(shù)據(jù)都插入到FP樹(shù)后，F(xiàn)P樹(shù)的建立完成。5.從FP樹(shù)中挖掘頻繁項(xiàng)集：從項(xiàng)頭表的底部項(xiàng)依次從下向上找到項(xiàng)頭表項(xiàng)所有包含該項(xiàng)的前綴路徑，即其條件模式基（CPB，conditionalpatternbase）,從條件模式基遞歸挖掘得到項(xiàng)頭表項(xiàng)的頻繁項(xiàng)集。遞歸調(diào)用樹(shù)結(jié)構(gòu)構(gòu)造FP子樹(shù)時(shí)，刪除小于最小支持度的項(xiàng)。如果條件模式基（FP子樹(shù)）最終呈現(xiàn)單一路徑的樹(shù)結(jié)構(gòu)，則直接列舉所有組合；非單一路徑的則繼續(xù)調(diào)用樹(shù)結(jié)構(gòu)，直到形成單一路徑即可。結(jié)合例子1：1.第一次掃描事務(wù)數(shù)據(jù)庫(kù)，得到頻繁1項(xiàng)集，并按支持度降序排序。原始數(shù)據(jù)：

頻繁1項(xiàng)集：

支持度降序：ItemsI1I2I5I2I4I6I2I3I7I1I2I4I1I3I2I3I8I1I3I1I2I3I5I1I2I3項(xiàng)支持度計(jì)數(shù)I16I27I36I42I52I61I71I81項(xiàng)支持度計(jì)數(shù)I27I16I36I42I52I61I71I81

2.刪掉不滿(mǎn)足設(shè)定最小支持度的項(xiàng)。(假設(shè)當(dāng)前最小支持度為2)項(xiàng)支持度計(jì)數(shù)I27I16I36I42I52I61I71I81項(xiàng)支持度計(jì)數(shù)I27I16I36I42I52 3.第二次掃描數(shù)據(jù)庫(kù)，剔除掉原始數(shù)據(jù)中非頻繁1項(xiàng)集，并將原始數(shù)據(jù)按支持度降序排序。I2:7I1:6I3:6I4:2I5:2I1I2I5I2I4I6I2I3I7I1I2I4I1I3I2I3I8I1I3I1I2I3I5I1I2I3項(xiàng)頭表剔除非頻繁1項(xiàng)集原始數(shù)據(jù):I1I2I5I2I4I2I3I1I2I4I1I3I2I3I1I3I1I2I3I5I1I2I3I2I1I5I2I4I2I3I2I1I4I1I3I2I3I1I3I2I1I3I5I2I1

I3

支持度降序排序4.構(gòu)造FP樹(shù)：讀入排序后的數(shù)據(jù)集，插入FP樹(shù)，插入時(shí)按照排序后的順序，插入FP樹(shù)中，排序靠前的節(jié)點(diǎn)是祖先節(jié)點(diǎn)，而靠后的是子孫節(jié)點(diǎn)。如果有共用的祖先，則對(duì)應(yīng)的公用祖先節(jié)點(diǎn)計(jì)數(shù)加1。插入后，如果有新節(jié)點(diǎn)出現(xiàn)，則項(xiàng)頭表對(duì)應(yīng)的節(jié)點(diǎn)會(huì)通過(guò)節(jié)點(diǎn)鏈表鏈接上新節(jié)點(diǎn)。直到所有的數(shù)據(jù)都插入到FP樹(shù)后，F(xiàn)P樹(shù)的建立完成。I2I1I5I2I4I2I3I2I1I4I1I3I2I3I1I3I2I1I3I5I2I1

I3

5.挖掘頻繁項(xiàng)集

可以按照從下往上的順序:先考慮I5：得到條件模式基

<(I2,I1)>

,<(I2,I1,I3)>（條件模式基：順著I5的鏈表，找出所有包含I5的前綴路徑，這些前綴路徑就是I5的條件模式基）。復(fù)制圖結(jié)構(gòu)，我們接著將所有的祖先節(jié)點(diǎn)計(jì)數(shù)設(shè)置為葉子節(jié)點(diǎn)的計(jì)數(shù)，刪除小于支持度的節(jié)點(diǎn)，F(xiàn)P子樹(shù)如下圖右。

形成單條路徑后進(jìn)行組合。得到I5頻繁項(xiàng)集:{{I2,I5},{I1,I5},{I2,I1,I5}}。

接著考慮I4，得到條件模式基<(I2,I1)>、<(I2)>,構(gòu)造條件FP樹(shù)（下圖右）：得到I4頻繁項(xiàng)集：{{I2,I4}}

然后考慮I3，得到條件模式基<(I2,I1)>、<(I2)>、<(I1)>構(gòu)造條件FP樹(shù)：

由于此樹(shù)不是單一路徑,因此需要遞歸挖掘I3。

遞歸考慮I3，此時(shí)得到I1條件模式基<(I2)>,即I1I3的條件模式基為<(I2)>構(gòu)造條件FP樹(shù)：

得到I3的頻繁項(xiàng)目集{{I2,I3},{I1,I3},{I2,I1,I3}}。

最后考慮I1，得到條件模式基<(I2)>構(gòu)造條件FP樹(shù)：得到I1的頻繁項(xiàng)目集{{I2,I1}}。

FP-growth算法總結(jié) FP-growth算法的工作流程：首先構(gòu)建FP樹(shù)，然后利用它來(lái)挖掘頻繁項(xiàng)集。為構(gòu)建FP樹(shù)，需要對(duì)原始數(shù)據(jù)集掃描兩遍。第一遍對(duì)所有元素項(xiàng)的出現(xiàn)次數(shù)進(jìn)行計(jì)數(shù)。數(shù)據(jù)庫(kù)的第一遍掃描用來(lái)統(tǒng)計(jì)出現(xiàn)的頻率，而第二遍掃描中只考慮那些頻繁元素。 FP-growth算法將數(shù)據(jù)存儲(chǔ)在一種稱(chēng)為FP樹(shù)的緊湊數(shù)據(jù)結(jié)構(gòu)中。FP樹(shù)通過(guò)鏈接（link）來(lái)連接相似元素，相似項(xiàng)之間的鏈接稱(chēng)為節(jié)點(diǎn)鏈接（nodelink），用于快速發(fā)現(xiàn)相似項(xiàng)的位置。被連起來(lái)的元素項(xiàng)可以看成一個(gè)鏈表。

與一般搜索樹(shù)不同的是，一個(gè)元素項(xiàng)可以在一棵FP樹(shù)中出現(xiàn)多次。FP樹(shù)中存儲(chǔ)項(xiàng)集的出現(xiàn)頻率，而每個(gè)項(xiàng)集會(huì)以路徑的方式存儲(chǔ)在樹(shù)中。存在相似元素的集合會(huì)共享樹(shù)的一部分。只有當(dāng)集合之間完全不同時(shí)，樹(shù)才會(huì)分叉。樹(shù)節(jié)點(diǎn)上給出集合中的單個(gè)元素及其在序列中的出現(xiàn)次數(shù)，路徑會(huì)給出該序列的出現(xiàn)次數(shù)。

FP-GROWTH算法的優(yōu)點(diǎn)相比Apriori算法需要多次掃描數(shù)據(jù)庫(kù)，F(xiàn)PGrowth只需要對(duì)數(shù)據(jù)庫(kù)掃描2次。第1次掃描事務(wù)數(shù)據(jù)庫(kù)獲得頻繁1項(xiàng)集。第2次掃描建立一顆FP-Tree樹(shù)。

輸入:事務(wù)集合List<List<String>>transactions

輸出:頻繁模式集合及相應(yīng)的頻數(shù)Map<List<String>,Integer>FrequentPattens

初始化PostModel=[],CPB=transactionsvoid

FPGrowth(List<List<String>>CPB,List<String>PostModel){

if

CPB為空：//條件向量模式基

return

統(tǒng)計(jì)CPB中每一個(gè)項(xiàng)目的計(jì)數(shù)，把計(jì)數(shù)小于最小支持?jǐn)?shù)minSuport的刪除掉，對(duì)于CPB中的每一條事務(wù)按項(xiàng)目計(jì)數(shù)降序排列。

由CPB構(gòu)建FP-Tree，F(xiàn)P-Tree中包含了表頭項(xiàng)headers，每一個(gè)header都指向了一個(gè)鏈表HeaderLinkList，鏈表中的每個(gè)元素都是FP-Tree上的一個(gè)節(jié)點(diǎn)，且節(jié)點(diǎn)名稱(chēng)與相同。

for

headerinheaders:

newPostModel=+PostModel

把<newPostModel,header.count>加到FrequentPattens中。

newCPB=[]

for

TreeNodeinHeaderLinkList:

得到從FP-Tree的根節(jié)點(diǎn)到TreeNode的全路徑path，把path作為一個(gè)事務(wù)添加到newCPB中，要重復(fù)添加TreeNode.count次。

關(guān)聯(lián)規(guī)則評(píng)價(jià)

1、主觀(guān)標(biāo)準(zhǔn)以決策者的主觀(guān)知識(shí)或領(lǐng)域?qū)＜业南闰?yàn)知識(shí)等建立的評(píng)價(jià)標(biāo)準(zhǔn)，稱(chēng)為主觀(guān)興趣度。關(guān)聯(lián)規(guī)則{尿布}

{啤酒}確實(shí)是有趣的，因?yàn)檫@種聯(lián)系十分出人意料，并且可能為零售商提供新的交叉銷(xiāo)售機(jī)會(huì)。

2、客觀(guān)標(biāo)準(zhǔn)以統(tǒng)計(jì)理論為依據(jù)建立的客觀(guān)評(píng)價(jià)標(biāo)準(zhǔn)，稱(chēng)為客觀(guān)興趣度。(1)客觀(guān)興趣度以數(shù)據(jù)本身推導(dǎo)出的統(tǒng)計(jì)量來(lái)確定規(guī)則是否是有趣的。(2)支持度，置信度，提升度等都是客觀(guān)興趣度，也就是客觀(guān)標(biāo)準(zhǔn)。

關(guān)聯(lián)規(guī)則評(píng)價(jià)

隨著有些數(shù)據(jù)問(wèn)題的出現(xiàn)，我們不禁會(huì)有這么一個(gè)疑問(wèn)，僅有支持度、置信度和提升度就足以評(píng)價(jià)物品間的關(guān)系了嗎？那么接下來(lái)看一個(gè)例子。

這是一個(gè)購(gòu)物籃數(shù)據(jù)，我們可以分析下購(gòu)買(mǎi)游戲和購(gòu)買(mǎi)影片之間的關(guān)聯(lián)關(guān)系。交易數(shù)據(jù)集有10000條數(shù)據(jù)，其中有6000條包括購(gòu)買(mǎi)游戲，7500條包括購(gòu)買(mǎi)影片，4000條包含既購(gòu)買(mǎi)游戲又購(gòu)買(mǎi)影片。數(shù)據(jù)集如下表所示：表1買(mǎi)游戲不買(mǎi)游戲行總計(jì)買(mǎi)影片400035007500不買(mǎi)影片20005002500列總計(jì)6000400010000

假設(shè)我們?cè)O(shè)置的最小支持度為30%，最小置信度為60%。從上表可以得到。

Support（買(mǎi)游戲->買(mǎi)影片）=4000/10000*100%=40% Confidence（買(mǎi)游戲->買(mǎi)影片）=4000/6000*100%=66%

可以看出，這條規(guī)則的支持度和置信度都滿(mǎn)足要求。因此我們很開(kāi)心，找到了一條強(qiáng)規(guī)則，于是我們建議超市把影片光碟和游戲光碟放在一起，可以提高銷(xiāo)量。

可是我們?cè)偎伎枷拢粋€(gè)愛(ài)玩游戲的人會(huì)有時(shí)間看影片嗎，這個(gè)規(guī)則是不是有問(wèn)題？事實(shí)上這條規(guī)則誤導(dǎo)了我們。我們可以使用提升度來(lái)驗(yàn)證下 Lift(買(mǎi)游戲->買(mǎi)影片)=(4000/10000)/(6000/10000)*(7500/10000)=8/9<1。結(jié)果是成負(fù)相關(guān)的，恰恰說(shuō)明了買(mǎi)游戲光碟限制了影片的銷(xiāo)量。也就是說(shuō)購(gòu)買(mǎi)了游戲光碟的人更傾向于不購(gòu)買(mǎi)影片光碟，這才是符合現(xiàn)實(shí)的。

從上面例子可以看出，支持度和置信度并不能成功過(guò)濾掉那些我們不感興趣的規(guī)則。因此我們需要一些新的評(píng)價(jià)標(biāo)準(zhǔn)。下面介紹五種評(píng)價(jià)標(biāo)準(zhǔn)：卡方系數(shù)、全自信度、最大自信度、kulc、cosine距離。

基本概念定義5：提升度Lift：

提升度表示A項(xiàng)集的出現(xiàn)，對(duì)B項(xiàng)集的出現(xiàn)有多大影響。

公式反映了項(xiàng)集A和項(xiàng)集B的相關(guān)程度。若I(A->B)=1即P(AB)=P(A)P(B)，說(shuō)明項(xiàng)集A和項(xiàng)集B是相互獨(dú)立的。若I(A->B)<1說(shuō)明項(xiàng)集A和項(xiàng)集B是負(fù)相關(guān)的。若I(A->B)>1說(shuō)明項(xiàng)集A和項(xiàng)集B是正相關(guān)的。

卡方系數(shù)

卡方分布是數(shù)理統(tǒng)計(jì)中的一個(gè)重要分布，利用卡方系數(shù)我們可以確定兩個(gè)變量是否相關(guān)，卡方系數(shù)的定義：

公式中O表示數(shù)據(jù)的實(shí)際值，E表示期望值，我們?cè)賮?lái)看一個(gè)例子。表2買(mǎi)游戲不買(mǎi)游戲行總計(jì)買(mǎi)影片4000（4500）3500（3000）7500不買(mǎi)影片2000（1500）500（1000）2500列總計(jì)6000400010000表中括號(hào)中表示的是期望值，以第一行第一列4500為例，其計(jì)算方法是6000*（7500/10000）?？傮w記錄中有75%買(mǎi)了影片，而買(mǎi)游戲的只有6000人。于是我們希望這6000人中