第4章 關(guān)聯(lián)規(guī)則1.ppt

1、2020/10/11,1,數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘技術(shù),五邑大學(xué)計(jì)算機(jī)學(xué)院 2009.05,何國(guó)輝 教授,2020/10/11,2,關(guān)聯(lián)規(guī)則(Association Rule Mining)挖掘是數(shù)據(jù)挖掘中最活躍的研究方法之一 最早是由R.Agrawal等人提出的 其目的是為了發(fā)現(xiàn)超市交易數(shù)據(jù)庫(kù)中不同商品之間的關(guān)聯(lián)關(guān)系。 一個(gè)典型的關(guān)聯(lián)規(guī)則的例子是：70%購(gòu)買(mǎi)了牛奶的顧客將傾向于同時(shí)購(gòu)買(mǎi)面包。 經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法：Apriori算法和FP-growth算法,第4章 關(guān)聯(lián)規(guī)則挖掘 ,4.1關(guān)聯(lián)規(guī)則挖掘的基本概念,2020/10/11,3,1. 購(gòu)物籃分析引發(fā)關(guān)聯(lián)規(guī)則挖掘的例子 問(wèn)題：“什么商品組或

2、集合顧客多半會(huì)在一次購(gòu)物中同時(shí)購(gòu)買(mǎi)？” 購(gòu)物籃分析：設(shè)全域?yàn)樯痰瓿鍪鄣纳唐返募希错?xiàng)目全集），一次購(gòu)物購(gòu)買(mǎi)（即事務(wù)）的商品為項(xiàng)目全集的子集，若每種商品用一個(gè)布爾變量表示該商品的有無(wú)，則每個(gè)購(gòu)物籃可用一個(gè)布爾向量表示。通過(guò)對(duì)布爾向量的分析，得到反映商品頻繁關(guān)聯(lián)或同時(shí)購(gòu)買(mǎi)的購(gòu)買(mǎi)模式。這些模式可用關(guān)聯(lián)規(guī)則描述。,2020/10/11,4,例購(gòu)買(mǎi)計(jì)算機(jī)與購(gòu)買(mǎi)財(cái)務(wù)管理軟件的關(guān)聯(lián)規(guī)則可表示為： computer financial_management_software support=2%,confidence=60% support為支持度，confidence為置信度。 該規(guī)則表示：在所分析的全部

3、事務(wù)中，有2的事務(wù)同時(shí)購(gòu)買(mǎi)計(jì)算機(jī)和財(cái)務(wù)管理軟件；在購(gòu)買(mǎi)計(jì)算機(jī)的顧客中60也購(gòu)買(mǎi)了財(cái)務(wù)管理軟件。,2020/10/11,5,2. 關(guān)聯(lián)規(guī)則 關(guān)聯(lián)（Associations）分析的目的是為了挖掘隱藏在數(shù)據(jù)間的相互關(guān)系，即對(duì)于給定的一組項(xiàng)目和一個(gè)記錄集，通過(guò)對(duì)記錄集的分析，得出項(xiàng)目集中的項(xiàng)目之間的相關(guān)性。 項(xiàng)目之間的相關(guān)性用關(guān)聯(lián)規(guī)則來(lái)描述，關(guān)聯(lián)規(guī)則反映了一組數(shù)據(jù)項(xiàng)之間的密切程度或關(guān)系。,2020/10/11,6,以商場(chǎng)超市的市場(chǎng)數(shù)據(jù)庫(kù)為例，形式化地描述關(guān)聯(lián)規(guī)則。 定義41 設(shè)I=i1，i2，,im是項(xiàng)的集合，表示各種商品的集合；D= t1，t2，,tn為交易集，表示每筆交易的集合（是全體事務(wù)的集合）

4、。其中每一個(gè)事務(wù)T都是項(xiàng)的集合，且有TI。每個(gè)事務(wù)都有一個(gè)相關(guān)的唯一標(biāo)識(shí)符和它對(duì)應(yīng)，也就是事務(wù)標(biāo)識(shí)符或TID。 設(shè)X為一個(gè)由項(xiàng)目構(gòu)成的集合，稱(chēng)為項(xiàng)集，當(dāng)且僅當(dāng)XT時(shí)我們說(shuō)事務(wù)T包含X。 項(xiàng)集X在在事務(wù)數(shù)據(jù)庫(kù)DB中出現(xiàn)的次數(shù)占總事務(wù)的百分比叫做項(xiàng)集的支持度。 如果項(xiàng)集的支持度超過(guò)用戶(hù)給定的最小支持度閾值，就稱(chēng)該項(xiàng)集是頻繁項(xiàng)集（或大項(xiàng)集）。,2020/10/11,7,關(guān)聯(lián)規(guī)則是形如XY的蘊(yùn)含式，其中XI，YI且XY=，則X稱(chēng)為規(guī)則的條件，Y稱(chēng)為規(guī)則的結(jié)果。 如果事務(wù)數(shù)據(jù)庫(kù)DB中有s%的事務(wù)包含XY，則稱(chēng)關(guān)聯(lián)規(guī)則XY的支持度為s%。支持度是一個(gè)概率值。,2020/10/11,8,表4-1,2020/

5、10/11,9,定義42關(guān)聯(lián)規(guī)則 XY對(duì)事物集D的支持度（support）定義為D中包含有事務(wù)X和Y的百分比。關(guān)聯(lián)規(guī)則XY對(duì)事務(wù)集合D的置信度（confidence）定義為D中包含有X的事務(wù)數(shù)與同時(shí)包含Y的百分比。即： lsupport(XY)(包含X和Y的事務(wù)數(shù)/事務(wù)總數(shù))100 lconfidence(XY)(包含X和Y的事務(wù)數(shù)/包含X的事務(wù)數(shù))100,2020/10/11,10,定義43置信度和支持度均大于給定閾值（即最小置信度閾值和最小支持度閾值）。即： support(XY) min_sup confidence(XY) min_conf 的關(guān)聯(lián)規(guī)則稱(chēng)為強(qiáng)規(guī)則；否則稱(chēng)為弱規(guī)則。 數(shù)據(jù)

6、挖掘主要就是對(duì)強(qiáng)規(guī)則的挖掘。通過(guò)設(shè)置最小支持度和最小置信度可以了解某些數(shù)據(jù)之間的關(guān)聯(lián)程度。,2020/10/11,11,強(qiáng)規(guī)則XY對(duì)應(yīng)的項(xiàng)集（XY）必定是頻繁集。因此，可以把關(guān)聯(lián)規(guī)則挖掘劃分為以下兩個(gè)子問(wèn)題： 根據(jù)最小支持度找出事務(wù)集D中的所有頻繁項(xiàng)集。核心 根據(jù)頻繁項(xiàng)集和最小置信度產(chǎn)生關(guān)聯(lián)規(guī)則。較易,2020/10/11,12,3. 關(guān)聯(lián)規(guī)則挖掘 關(guān)聯(lián)規(guī)則挖掘：給定一組Item和記錄集合，挖掘出Item間的相關(guān)性，使其置信度和支持度分別大于用戶(hù)給定的最小置信度和最小支持度。,例 購(gòu)買(mǎi)商品事務(wù)如下表所示，設(shè)最小支持度為50%, 最小可信度為 50%, 則可得到以下關(guān)聯(lián)規(guī)則： A C (50%,

7、 66.6%) C A (50%, 100%),支持度,可信度,表4-2,2020/10/11,13,4.關(guān)聯(lián)規(guī)則挖掘的分類(lèi) （1）基于規(guī)則中處理的變量的類(lèi)別 基于規(guī)則中處理的變量的類(lèi)別,關(guān)聯(lián)規(guī)則可以分為布爾型和數(shù)值型。 布爾型關(guān)聯(lián)規(guī)則：如果規(guī)則考慮的關(guān)聯(lián)是項(xiàng)“在”或“不在”，則關(guān)聯(lián)規(guī)則是布爾型的。例如，由購(gòu)物籃分析得出的關(guān)聯(lián)規(guī)則。 量化型關(guān)聯(lián)規(guī)則：如果描述的是量化的項(xiàng)或?qū)傩灾g的關(guān)聯(lián)，則該規(guī)則是量化型的關(guān)聯(lián)規(guī)則。,2020/10/11,14,例如： 以下是量化型關(guān)聯(lián)規(guī)則的一個(gè)例子（其中X為表示顧客的變量，量化屬性age 和income已經(jīng)離散化）： age(X,“3039”)income(“

8、42K48K”) buys(X,“high_resolution_TV”) 量化型關(guān)聯(lián)規(guī)則中也可以包含多種變量。例如： 性別=“女”=職業(yè)=“秘書(shū)” ，是布爾型關(guān)聯(lián)規(guī)則； 性別=“女”=avg（月收入）=2300，涉及的收入是數(shù)值類(lèi)型，所以是一個(gè)量化型關(guān)聯(lián)規(guī)則。,2020/10/11,15,（2）基于規(guī)則中數(shù)據(jù)的抽象層次 基于規(guī)則中數(shù)據(jù)的抽象層次,可以分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則。 單層的關(guān)聯(lián)規(guī)則：所有的變量都不涉及不同抽象層次的項(xiàng)或?qū)傩浴?例如： buys(X, “computer”) buys(X, “printer”) 顧客X購(gòu)買(mǎi)的商品不涉及不同抽象層次（“computer” 和“pr

9、inter”在同一個(gè)抽象層），因此是單層關(guān)聯(lián)規(guī)則。 多層的關(guān)聯(lián)規(guī)則：變量涉及不同抽象層次的項(xiàng)或?qū)傩浴?例如： age(X,“3039”)buys(X, “l(fā)aptop computer”) age(X,“3039”)buys(X, “computer”) 顧客X購(gòu)買(mǎi)的商品涉及不同抽象層次（“computer” 在比“l(fā)aptop computer”高的抽象層），因此是多層關(guān)聯(lián)規(guī)則。,2020/10/11,16,（3）基于規(guī)則中涉及到的數(shù)據(jù)的維數(shù) 基于規(guī)則中涉及到的數(shù)據(jù)的維數(shù),關(guān)聯(lián)規(guī)則可以分為單維的和多維的。 單維關(guān)聯(lián)規(guī)則：處理單個(gè)維中屬性間的關(guān)系，即在單維的關(guān)聯(lián)規(guī)則中，只涉及到數(shù)據(jù)的一個(gè)維。

10、例如：用戶(hù)購(gòu)買(mǎi)的物品：“咖啡=砂糖”，這條規(guī)則只涉及到用戶(hù)的購(gòu)買(mǎi)的物品。 多維關(guān)聯(lián)規(guī)則：處理多個(gè)維中屬性之間的關(guān)系，即在多維的關(guān)聯(lián)規(guī)則中，要處理的數(shù)據(jù)將會(huì)涉及多個(gè)維。 例如：性別=“女”=職業(yè)=“秘書(shū)”，這條規(guī)則就涉及到兩個(gè)維中字段的信息，是兩個(gè)維上的一條關(guān)聯(lián)規(guī)則。,2020/10/11,17,給出了關(guān)聯(lián)規(guī)則的分類(lèi)之后，就可以考慮某個(gè)具體的關(guān)聯(lián)規(guī)則挖掘算法適用于哪一類(lèi)規(guī)則的挖掘，某類(lèi)關(guān)聯(lián)規(guī)則又可以用哪些不同的方法進(jìn)行處理。 最簡(jiǎn)單的是單維、單層、布爾型的關(guān)聯(lián)規(guī)則。,2020/10/11,18,1. 術(shù)語(yǔ) 關(guān)聯(lián)規(guī)則挖掘即給定一組Item和記錄集合，挖掘出Item間的相關(guān)性，使其置信度和支持度分別

11、大于用戶(hù)給定的最小置信度和最小支持度。,4.2關(guān)聯(lián)規(guī)則挖掘的過(guò)程,2020/10/11,19,定義44在關(guān)聯(lián)規(guī)則挖掘算法中，把項(xiàng)目的集合稱(chēng)為項(xiàng)集（itemset），包含有k個(gè)項(xiàng)目的項(xiàng)集稱(chēng)為k-項(xiàng)集。包含項(xiàng)集的事務(wù)數(shù)稱(chēng)為項(xiàng)集的出現(xiàn)頻率，簡(jiǎn)稱(chēng)為項(xiàng)集的頻率或支持度計(jì)數(shù)。如果項(xiàng)集的出現(xiàn)頻率大于或等于最小支持度s與D中事務(wù)總數(shù)的乘積，則稱(chēng)該項(xiàng)集滿(mǎn)足最小支持度s。如果項(xiàng)集滿(mǎn)足最小支持度，則稱(chēng)該項(xiàng)集為頻繁項(xiàng)集（frequent itemset）。,2020/10/11,20,例一個(gè)食品連鎖店保留著每周的事務(wù)記錄，其中每一條事務(wù)表示在一項(xiàng)收款機(jī)業(yè)務(wù)中賣(mài)出的項(xiàng)目。連鎖店的管理會(huì)收到一個(gè)事務(wù)匯總報(bào)告，報(bào)告表明了每

12、種項(xiàng)目的銷(xiāo)售量是多少。此外，他們要定期了解哪些項(xiàng)目經(jīng)常被顧客一起購(gòu)買(mǎi)。他們發(fā)現(xiàn)顧客購(gòu)買(mǎi)了花生醬后，100%地會(huì)購(gòu)買(mǎi)面包。而且，顧客購(gòu)買(mǎi)了花生醬后，有33%也購(gòu)買(mǎi)果凍。不過(guò)，所有事務(wù)中大約只有50%包含花生醬。 被用于在其中尋找關(guān)聯(lián)規(guī)則的數(shù)據(jù)庫(kù)可以看作為一個(gè)元組集合，每個(gè)元組包含一組項(xiàng)目。一個(gè)元組可能是： 花生醬、面包、果凍 包含三個(gè)項(xiàng)目：花生醬、面包、果凍 每個(gè)項(xiàng)目表示購(gòu)買(mǎi)的一種產(chǎn)品 一個(gè)元組是一次購(gòu)買(mǎi)的產(chǎn)品列表,2020/10/11,21,表4-3,2020/10/11,22,項(xiàng)目的個(gè)數(shù)成指數(shù)增長(zhǎng)：從5個(gè)項(xiàng)目的集合得到31個(gè)項(xiàng)目集合（忽略空集）,表4-4,2020/10/11,23,2關(guān)聯(lián)規(guī)

13、則的挖掘過(guò)程,最常用的關(guān)聯(lián)規(guī)則挖掘方法被分解為下面兩步： 第1步：找出所有的頻繁項(xiàng)集，即找出支持度大于或等于給定的最小支持度閾值的所有項(xiàng)集?？梢詮?到k遞歸查找k-頻繁項(xiàng)集。 第2步：由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，即找出滿(mǎn)足最小支持度和最小置信度的關(guān)聯(lián)規(guī)則。,找出滿(mǎn)足定義的大項(xiàng)目集,從大項(xiàng)目集（頻繁項(xiàng)目集）生成關(guān)聯(lián)規(guī)則,2020/10/11,24,定義45大（頻繁）項(xiàng)目集是出現(xiàn)次數(shù)大于閾值S的項(xiàng)目集。用符號(hào)L表示大項(xiàng)目集組成的整個(gè)集合，用表示一個(gè)特定的大項(xiàng)目集。 一旦找出大項(xiàng)目集，則對(duì)于任何有趣的關(guān)聯(lián)規(guī)則XY，在頻繁項(xiàng)目集的集合中一定有XY。,任何大項(xiàng)目集的子集也是大的,4.3 大項(xiàng)目集,2020

14、/10/11,25,關(guān)聯(lián)規(guī)則中使用了大量的符號(hào)，這些符號(hào)匯總?cè)缦隆?一個(gè)特定符號(hào)所帶的下標(biāo)表示所考慮的集合的大小，例如，lk表示一個(gè)大小為k的項(xiàng)目集。 一些算法將事務(wù)集合分為若干個(gè)分區(qū)，在這種情況下，用p表示分區(qū)的數(shù)目，用上標(biāo)表明分區(qū)的編號(hào)。例如，Di表示D的第i個(gè)分區(qū)。,表10-5,2020/10/11,26,找出大項(xiàng)目集的算法可以很簡(jiǎn)單，但代價(jià)很高。 簡(jiǎn)單的方法是：對(duì)出現(xiàn)在事務(wù)中的所有項(xiàng)目集進(jìn)行計(jì)數(shù)。 給定一個(gè)大小為m的項(xiàng)目集合，共有2m個(gè)子集，去掉空集，則潛在的大項(xiàng)目集數(shù)為2m - 1。隨著項(xiàng)目數(shù)的增多，潛在的大項(xiàng)目集數(shù)成爆炸性增長(zhǎng)。（當(dāng)m=5，為31個(gè)；當(dāng)m=30，變成10737418

15、23個(gè)） 解決問(wèn)題的難點(diǎn)：如何高效確定所有大項(xiàng)目集。,大部分關(guān)聯(lián)規(guī)則算法都利用巧妙的方法來(lái)減少要計(jì)數(shù)的項(xiàng)目集。,2020/10/11,27,幾個(gè)概念： 潛在的大項(xiàng)目集稱(chēng)為候選。 所有被計(jì)數(shù)的（潛在大的）項(xiàng)目集的集合稱(chēng)為候選項(xiàng)目集C。 關(guān)聯(lián)規(guī)則使用的一個(gè)性能度量指標(biāo)是C的大小。,找出所有大項(xiàng)目集以后，關(guān)聯(lián)規(guī)則的生成變得非常直接。,2020/10/11,28,有關(guān)算法： 改自AS94，用support返回輸入項(xiàng)目集的支持度。 輸入： D/事務(wù)數(shù)據(jù)庫(kù) I/項(xiàng)目集合 L/大項(xiàng)目集 s/支持度 /可信度（置信度） 輸出: R/滿(mǎn)足s和的關(guān)聯(lián)規(guī)則集合 ARGen算法： R = ； for each lL

16、do for each x l such that x do if support(l)/support(x) then R = R x (l-x)；,2020/10/11,29,有關(guān)算法演示：參考表4-3、4-4 假定輸入的支持度和可信度分別為s=30%和 =50%。利用該s值得到如下大項(xiàng)目集的集合： L=啤酒,面包,牛奶，花生醬, 面包、花生醬 查看最后一個(gè)大項(xiàng)目集可以生成的關(guān)聯(lián)規(guī)則,其中： l = 面包、花生醬 有兩個(gè)非空子集： 面包和花生醬 對(duì)于第一個(gè)非空子集，可得： support(面包、花生醬)/support(面包) = 60/80 = 0.75 意味著關(guān)聯(lián)規(guī)則：“面包花生醬”的

17、置信度為75%，因?yàn)槠渲眯哦雀哂?，所以是一條有效的關(guān)聯(lián)規(guī)則。,2020/10/11,30,對(duì)于第二個(gè)非空子集，可得： support(面包、花生醬)/support(花生醬) = 60/60 = 1 意味著關(guān)聯(lián)規(guī)則：“花生醬面包”的置信度為100%， 也是一條有效的關(guān)聯(lián)規(guī)則。,2020/10/11,31,4.4 關(guān)聯(lián)規(guī)則挖掘的Apriori算法,4.4.1 Apriori算法的基本思想 Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則大（頻繁）項(xiàng)目集的算法。它使用一種稱(chēng)作逐層搜索的迭代算法，通過(guò)k-項(xiàng)集用于探索（k+1）-項(xiàng)集。已經(jīng)為大部分商業(yè)產(chǎn)品所使用。,2020/10/11,32,Apr

18、iori算法的基本思想是： 首先，通過(guò)掃描數(shù)據(jù)集，產(chǎn)生一個(gè)大的候選數(shù)據(jù)項(xiàng)集,并計(jì)算每個(gè)候選數(shù)據(jù)項(xiàng)發(fā)生的次數(shù)，然后基于預(yù)先給定的最小支持度生成頻繁1-項(xiàng)集的集合，該集合記作 ； 然后基于 和數(shù)據(jù)集中的數(shù)據(jù)，產(chǎn)生頻繁2-項(xiàng)集 ； 用同樣的方法，直到生成頻繁n-項(xiàng)集，其中已不再可能生成滿(mǎn)足最小支持度的（N+1）項(xiàng)集 。 最后，從大數(shù)據(jù)項(xiàng)集中導(dǎo)出規(guī)則。,在第一次迭代的第一步中，產(chǎn)生的候選集包含所有1-項(xiàng)集，實(shí)為數(shù)據(jù)庫(kù)中所有的項(xiàng)，再計(jì)算各自的支持度。,2020/10/11,33,1. 大項(xiàng)目集的性質(zhì),大項(xiàng)目集的任一子集也一定是大的。 大項(xiàng)目集也稱(chēng)作是向下封閉的，如果一個(gè)項(xiàng)目集滿(mǎn)足最小支持度的要求，其所有

19、的子集也滿(mǎn)足這一要求。 其逆命題：如果知道一個(gè)項(xiàng)目集是小的，就不需要生成它的任何超集來(lái)作為它的候選集，因?yàn)樗鼈円惨欢ㄊ切〉摹?Apriori性質(zhì)基于如下事實(shí)：根據(jù)定義，如果項(xiàng)集I不滿(mǎn)足最小支持度閾值min_sup，則I不是頻繁的，即sup（I） min_sup。如果將項(xiàng)A添加到I，則結(jié)果項(xiàng)集（即IA）不可能比I更頻繁出現(xiàn)。因此，IA也不是頻繁的，即sup（IA） min_sup。 頻繁項(xiàng)集的Apriori性質(zhì)用于壓縮搜索空間（剪枝），以提高逐層產(chǎn)生頻繁項(xiàng)集的效率。,Apriori算法利用了大項(xiàng)目集的這些性質(zhì),2020/10/11,34,用圖表示上述性質(zhì)，例子中有四個(gè)項(xiàng)目A，B，C，D，格中的線(xiàn)

20、表示子集關(guān)系，大項(xiàng)目集的性質(zhì)表明：如果原來(lái)的項(xiàng)目集是大的，則在路徑中位于其上的任何集合也一定是大的。,A，B，C，D項(xiàng)目集的格結(jié)構(gòu),項(xiàng)目ACD的非空子集是： AC，AD，CD，A，C，D,2020/10/11,35,如果A，C，D是大的，則其每一個(gè)子集也是大的，如果其任何一個(gè)子集是小的，則 A，C，D也是小的。,A，C，D的子集,項(xiàng)目ACD的非空子集是： AC，AD，CD，A，C，D,2020/10/11,36,按照Apriori算法： 在第i趟掃描的過(guò)程中，對(duì)Ci進(jìn)行計(jì)數(shù)，只有那些大的候選集被用于生成下一趟掃描的候選集，即用Li生成Ci+1。 只有一個(gè)項(xiàng)目集的所有子集都是大的，它才被認(rèn)為是候

21、選。 為了生成大小為i+1的候選，要對(duì)前一趟掃描發(fā)現(xiàn)的大項(xiàng)目集進(jìn)行連接運(yùn)算。 表示：Lk*Lk = XY 其中 X，Y Lk，|XY|=k 1 例：對(duì)表4-3進(jìn)行演算，其中s=30%， =50%,2020/10/11,37,表4-3,回憶,2020/10/11,38,對(duì)表4-3采用Apriori算法,為了組合出下一級(jí)候選，每個(gè)項(xiàng)目集除了一個(gè)項(xiàng)目之外，其它的項(xiàng)目都相同。,因?yàn)橹挥幸粋€(gè)大小為2的大項(xiàng)目集，所以沒(méi)有大小為3的候選,2020/10/11,39,4.4.2 Apriori算法中的關(guān)鍵步驟,Apriori算法中的關(guān)鍵步驟是由Lk-1找Lk，該步驟可分為兩步： 第1步（連接）：為找Lk，通過(guò)

22、Lk-1與自己連接產(chǎn)生候選K-項(xiàng)集的集合。將該候選項(xiàng)集的集合記作Ck。設(shè)l1和l2是Lk-1中的項(xiàng)集，記號(hào)lij表示li的第j項(xiàng)。執(zhí)行連接Lk-1和Lk-1，其中Lk-1的元素是可連接，如果它們前（k-2）個(gè)項(xiàng)相同而且第（k-2）項(xiàng)不同（為簡(jiǎn)單計(jì)，設(shè)l1k-1l2k-1），即： l11= l21 l12=l22l1k-2=l2k-2 l1k-1l2k-1 則Lk-1的元素l1和l2是可連接的。連接l1和l2產(chǎn)生的結(jié)果的項(xiàng)集是l11l12l1k-1l2k-1。,2020/10/11,40,第2步（剪枝）：Ck是Lk的超集，即它的成員可以是也可以不是頻繁的，但所有的頻繁k-項(xiàng)集都包含在Ck中。掃描

23、數(shù)據(jù)庫(kù)，確定Ck中每個(gè)候選的計(jì)數(shù)，從而確定Lk。然而，Ck可能很大，這樣所涉及的計(jì)算量就很大。為壓縮Ck，可以用以下辦法使用Apriori性質(zhì)：任何非頻繁的（k-1）-項(xiàng)集都不可能是頻繁k-項(xiàng)集的子集。因此，如果一個(gè)候選k-項(xiàng)集的（k-1）-子集不在Lk-1中，則該候選也不可能是頻繁的，從而可以由Ck中刪除。,2020/10/11,41,一個(gè)稱(chēng)為Apriori-Gen的算法： 用于生成除第一趟之外的每一趟掃描的候選項(xiàng)目集。 所有的單元素項(xiàng)目集在第一趟時(shí)作為候選使用。 前一趟發(fā)現(xiàn)的大項(xiàng)目集的集合Li-1與自身進(jìn)行連接運(yùn)算以確定候選。 為了組合出下一級(jí)候選，每個(gè)項(xiàng)目集除了一個(gè)項(xiàng)目之外，其它的項(xiàng)目都

24、相同。,2020/10/11,42,Apriori-Gen算法實(shí)例：一個(gè)女士服裝店在一天中有20個(gè)收款機(jī)事務(wù)記錄，如表：,2020/10/11,43,2020/10/11,44,Apriori-Gen算法處理過(guò)程： 第一趟掃描得到6個(gè)候選項(xiàng)目集，其中5個(gè)候選是大的。 對(duì)該5個(gè)候選應(yīng)用Apriori-Gen算法，將每一個(gè)候選與另外4個(gè)進(jìn)行組合，得到第二趟掃描：4+3+2+1=10個(gè)候選，其中7個(gè)候選是大的。 在7個(gè)候選中再應(yīng)用Apriori-Gen算法，將每一個(gè)項(xiàng)目集與另外一個(gè)與之具有一個(gè)公共成員的項(xiàng)目集進(jìn)行連接運(yùn)算，第三趟掃描后得到4個(gè)大項(xiàng)目集。 第四趟掃描后只剩下一個(gè)大項(xiàng)目集，也不存在下一趟

25、計(jì)數(shù)為5個(gè)的新項(xiàng)目集。,2020/10/11,45,為了對(duì)大數(shù)據(jù)庫(kù)中的項(xiàng)目集進(jìn)行高效計(jì)數(shù)，可以對(duì)數(shù)據(jù)庫(kù)進(jìn)行抽樣。 最初的抽樣算法在最理想的情況下可將數(shù)據(jù)庫(kù)的掃描趟數(shù)減少到1，在最壞的情況下將掃描趟數(shù)減少到2。 數(shù)據(jù)庫(kù)抽樣的大小要保證它能駐留在內(nèi)存中。 知識(shí)準(zhǔn)備： 大項(xiàng)目集被看作是潛在大的（Potentially Large，PL）項(xiàng)目集，并作為候選用整個(gè)數(shù)據(jù)庫(kù)對(duì)其進(jìn)行計(jì)數(shù)。 另外的候選則通過(guò)作用于樣本中大項(xiàng)目集的負(fù)邊界函數(shù)BD-來(lái)確定。 因此整個(gè)候選集為：C = BD-(PL)(PL),4.4.3 抽樣算法,2020/10/11,46,負(fù)邊界函數(shù)是Apriori-Gen算法的一種推廣，它的定義

26、是： 本身不在PL中但其子集都在PL中的項(xiàng)目集的最小集合 負(fù)邊界函數(shù)在一些Apriori的改進(jìn)算法中很重要，例如生成大項(xiàng)集或?qū)С鲐?fù)關(guān)聯(lián)規(guī)則時(shí)提高了有效性。,2020/10/11,47,例子：假定項(xiàng)目集合是A，B，C，D，從數(shù)據(jù)庫(kù)樣本中發(fā)現(xiàn)的大項(xiàng)目集集合是PL = A，C，D，CD。第一趟掃描整個(gè)數(shù)據(jù)庫(kù)生成下面的候選集： C = BD-(PL)(PL) = B，AC，AD A，C，D，CD 加入理由： 加入了AC，因?yàn)锳和C都在PL中； 加入了AD，同理，因?yàn)锳和D都在PL中； 沒(méi)有加入ACD，因?yàn)锳C和AD都不在PL中； 加入了B，因?yàn)槠渌凶蛹紴榭眨士梢哉J(rèn)為其子集也在PL中。,2020/

27、10/11,48,有關(guān)格結(jié)構(gòu)表示：,大項(xiàng)目集,2020/10/11,49,BD-(PL)(PL),2020/10/11,50,抽樣算法的實(shí)現(xiàn)： 具體措施： 在掃描整個(gè)數(shù)據(jù)庫(kù)時(shí)，大項(xiàng)目集的集合被用作候選集。 如果一個(gè)項(xiàng)目集在抽樣中是大的，則它被認(rèn)為在整個(gè)數(shù)據(jù)庫(kù)中可能是大的，因此抽樣中的大項(xiàng)目集集合被稱(chēng)為PL。 為了在第一趟掃描時(shí)獲得所有的大項(xiàng)目集，用PL的負(fù)邊界對(duì)其進(jìn)行擴(kuò)充，因此整個(gè)候選集為：C = BD-(PL)(PL),補(bǔ)充說(shuō)明： Apriori算法用來(lái)發(fā)現(xiàn)樣本中的大項(xiàng)目集，也可以使用任何其它大項(xiàng)目集發(fā)現(xiàn)方法。 可以使用任意的數(shù)據(jù)庫(kù)抽樣算法。,2020/10/11,51,抽樣算法實(shí)現(xiàn)過(guò)程：

28、在第一趟掃描數(shù)據(jù)庫(kù)時(shí)，對(duì)C中的所有候選進(jìn)行計(jì)數(shù)。如果所有大的候選都在PL中（沒(méi)有在BD-(PL)中），那么發(fā)現(xiàn)了所有的大項(xiàng)目集。但如果有一些大項(xiàng)目集在負(fù)邊界中，則需要進(jìn)行第二趟掃描。所有項(xiàng)目集的集合被分到4個(gè)區(qū)域： 已知為大的部分 已知為小的部分 已知為大的項(xiàng)目集的負(fù)邊界 以及其它部分,可以認(rèn)為負(fù)邊界是大項(xiàng)目集邊界的一個(gè)緩沖區(qū)，代表有可能為大的的項(xiàng)目集的最小集合。,2020/10/11,52,第二趟掃描時(shí)，生成其它候選，并進(jìn)行計(jì)數(shù)，這樣一來(lái)做能保證找出所有大項(xiàng)目集。用缺失大項(xiàng)目集（Missing Large Itemset，ML）表示那些在L中，但卻不在PL中的項(xiàng)目集。 為了在第二趟掃描中發(fā)現(xiàn)

29、所有剩余的大項(xiàng)目集，抽樣算法將重復(fù)應(yīng)用負(fù)邊界函數(shù)，直到可能的候選集合不再進(jìn)一步擴(kuò)大為止。,2020/10/11,53,抽樣算法： 輸入： I/項(xiàng)目集合 D/事務(wù)數(shù)據(jù)庫(kù) S/支持度 輸出： L/大項(xiàng)目集 抽樣算法： Ds=Sample draw from D； PL=Apriori(I,Ds,smalls)； C = BD-(PL)(PL) L = ； for each IiC do Ci = 0；/每個(gè)項(xiàng)目集的初始計(jì)數(shù)設(shè)為0； for each tjD do /第一趟掃描計(jì)數(shù)； for each IiC do if Ii tj then Ci = Ci + 1；,2020/10/11,54,f

30、or each IiC do if Ci(s|D|) then L = LIi ； ML = x|xBD-(PL) xL；/缺失的大項(xiàng)目集 if ML then C = L；/將候選設(shè)置為大項(xiàng)目集 repeat C = C BD-(C)；/用負(fù)邊界對(duì)候選集進(jìn)行擴(kuò)充 until no new itemsets are added to C； for each IiC do Ci = 0；/每個(gè)項(xiàng)目集的初始計(jì)數(shù)設(shè)為0； for each tjD do /第二趟掃描計(jì)數(shù)； for each IiC do if Ii tj then Ci = Ci + 1； for each IiC do if Ci

31、(s|D|) then L = LIi ；,2020/10/11,55,算法中應(yīng)用了一個(gè)稱(chēng)為smalls的支持度，smalls可以是比s小的任意支持度值。 基本思路：發(fā)現(xiàn)抽樣中的大項(xiàng)目集時(shí)通過(guò)減小支持度，能從完整數(shù)據(jù)庫(kù)中發(fā)現(xiàn)更多真正的大項(xiàng)目集。,2020/10/11,56,例：使用抽樣算法發(fā)現(xiàn)食品店數(shù)據(jù)中的所有大項(xiàng)目集，其中s=20%。假定抽樣數(shù)據(jù)庫(kù)包括前兩個(gè)事務(wù)： Ds = t1 = 面包，果凍，花生醬， t2 = 面包，生醬 如果將s減小到smalls = 10%，那么對(duì)于一個(gè)在抽樣中為大的項(xiàng)目集來(lái)說(shuō)，它必須在至少0.12個(gè)事務(wù)中出現(xiàn)，也就是必須在其中一個(gè)事務(wù)中出現(xiàn)。 對(duì)Ds應(yīng)用Aprio

32、ri算法可以得到： PL = 面包，果凍，花生醬， 面包，果凍，面包，花生醬， 果凍，花生醬， 面包，果凍，花生醬 計(jì)算負(fù)邊界： BD-(PL) = 啤酒，牛奶 在第一趟數(shù)據(jù)庫(kù)掃描時(shí)，對(duì)以下候選集計(jì)數(shù)： C = 面包，果凍，花生醬， 面包，果凍，面包，花生醬， 果凍，花生醬， 面包，果凍，花生醬， 啤酒，牛奶 ,2020/10/11,57,掃描時(shí)使用s=20%，并應(yīng)用于整個(gè)數(shù)據(jù)庫(kù)的5個(gè)事務(wù)。因此對(duì)于一個(gè)大的項(xiàng)目集來(lái)說(shuō)，必須至少在0.25個(gè)或1個(gè)事務(wù)中出現(xiàn)。 可以發(fā)現(xiàn)啤酒和牛奶是大的，ML=啤酒，牛奶，根據(jù)算法，首先令C=L，也即PL。 計(jì)算負(fù)邊界可得： C = BD-(C) = 啤酒，面包，

33、啤酒，果凍，啤酒，牛奶， 啤酒，花生醬， 面包，牛奶， 果凍，牛奶， 牛奶，花生醬 由于發(fā)現(xiàn)了新的項(xiàng)目集，重復(fù)上述過(guò)程，并發(fā)現(xiàn)所有大小為3的項(xiàng)目集。 最后一趟將發(fā)現(xiàn)所有大小為4的項(xiàng)目集，并針對(duì)剩余的不知是否為大的項(xiàng)目集掃描數(shù)據(jù)庫(kù)。,2020/10/11,58,基于抽樣的方法的本質(zhì)是選取給定事務(wù)集D的隨機(jī)樣本S，在S中找出頻繁項(xiàng)集，即以犧牲精度換取效率。 Mannila等先考慮了這一點(diǎn)，他們認(rèn)為抽樣是發(fā)現(xiàn)規(guī)則的一個(gè)有效途徑。 隨后又由Toivonen進(jìn)一步發(fā)展了這個(gè)思想，先使用從數(shù)據(jù)庫(kù)中抽取出來(lái)的采樣得到一些在整個(gè)數(shù)據(jù)庫(kù)中可能成立的規(guī)則，然后對(duì)數(shù)據(jù)庫(kù)的剩余部分驗(yàn)證這個(gè)結(jié)果。 由于是從樣本中分析大

34、項(xiàng)目集，故對(duì)樣本采用了比最小支持度閾值更低的支持閾值來(lái)獲得潛在大項(xiàng)目集。 Toivonen的算法相當(dāng)簡(jiǎn)單并顯著地減少了I/O代價(jià)，但是一個(gè)很大的缺點(diǎn)就是產(chǎn)生的結(jié)果不精確，即存在所謂的數(shù)據(jù)扭曲(data skew)。,2020/10/11,59,該方法只需對(duì)事務(wù)數(shù)據(jù)庫(kù)進(jìn)行兩次掃描。 數(shù)據(jù)庫(kù)被劃分成若干個(gè)非重疊的分區(qū)。 每個(gè)分區(qū)都按可以小到適合內(nèi)存的大小。 主要優(yōu)點(diǎn)： 提高了算法的效率 突破了內(nèi)存限制 很容易構(gòu)造并行和/或分布式算法 通過(guò)將數(shù)據(jù)庫(kù)的當(dāng)前狀態(tài)作為一個(gè)分區(qū)，而將新的數(shù)據(jù)條目作為第二個(gè)分區(qū)，更容易實(shí)現(xiàn)增量挖掘關(guān)聯(lián)規(guī)則。,4.4.4 基于劃分的Apriori方法,2020/10/11,60

35、,具體思路： 第一趟掃描數(shù)據(jù)庫(kù)，發(fā)現(xiàn)所有分區(qū)中的大項(xiàng)目集。Li代表從分區(qū)Di中發(fā)現(xiàn)的大項(xiàng)目集。 在第二趟掃描時(shí)，只有那些至少在一個(gè)分區(qū)中為大項(xiàng)目集被用作候選并進(jìn)行計(jì)數(shù)，以確定它們?cè)谡麄€(gè)數(shù)據(jù)庫(kù)中是否為大。,2020/10/11,61,該算法可以高度并行，即可以把每一分區(qū)分別分配給某一個(gè)處理器生成頻繁集。產(chǎn)生頻繁集的每一個(gè)循環(huán)結(jié)束后，處理器之間進(jìn)行通信來(lái)產(chǎn)生全局的候選k-項(xiàng)集。 通常通信過(guò)程是算法執(zhí)行時(shí)間的主要瓶頸；而另一方面，每個(gè)獨(dú)立的處理器生成頻繁集的時(shí)間也是一個(gè)瓶頸。,2020/10/11,62,實(shí)例,D1,D2,2020/10/11,63,劃分算法在購(gòu)物籃中的應(yīng)用：數(shù)據(jù)庫(kù)被劃分成兩個(gè)分區(qū)，

36、第一個(gè)分區(qū)包含兩個(gè)事務(wù)，第二個(gè)分區(qū)包含三個(gè)事務(wù)， 采用10%的支持度計(jì)算出的大項(xiàng)目集L1和L2為： L1 = 面包，果凍，花生醬， 面包，果凍， 面包，花生醬， 果凍，花生醬， 面包，果凍，花生醬 L2 = 啤酒，面包，牛奶，花生醬， 啤酒，面包， 啤酒，牛奶，面包，牛奶，面包，花生醬， 牛奶，花生醬， 面包，牛奶，花生醬 如果項(xiàng)目分布均勻分布在各個(gè)分區(qū)中，則大部分局部大項(xiàng)目集在全局都是大的，如果數(shù)據(jù)分布是不均勻的，則錯(cuò)誤候選的比例就會(huì)大。,2020/10/11,64,4.5 頻繁模式增長(zhǎng)（FP）算法,由于Apriori算法和Apriori算法的變形都需要產(chǎn)生大量的候選項(xiàng)集，Apriori算法

37、的變形雖然使其得到一定程度的改善，但并未根本改觀。 例如：如果生成一個(gè)長(zhǎng)度為100的頻繁模式，如a1,a2,a100，那么產(chǎn)生的候選集的數(shù)量至少為： 100 ( ) = 2100 1 1030 i=1 計(jì)算的復(fù)雜性成指數(shù)增長(zhǎng)。 Han等人引入“頻繁模式增長(zhǎng)”（簡(jiǎn)稱(chēng)FP-增長(zhǎng)）的概念，可以不產(chǎn)生候選就能夠找出所有的頻繁項(xiàng)集。,i,100,2020/10/11,65,4.5.1 FP-增長(zhǎng)算法的基本思想,FP-增長(zhǎng)算法的基本思想是： 采用分治策略，將提供頻繁項(xiàng)集的數(shù)據(jù)庫(kù)壓縮到一棵頻繁模式樹(shù)，但還是保留項(xiàng)集關(guān)聯(lián)信息；然后，將這種壓縮后的數(shù)據(jù)庫(kù)分成一組條件數(shù)據(jù)庫(kù)，每個(gè)關(guān)聯(lián)一個(gè)頻繁項(xiàng)，并分別挖掘每個(gè)數(shù)據(jù)

38、庫(kù)。 即：首先進(jìn)行數(shù)據(jù)庫(kù)投影，得到頻繁項(xiàng)，然后通過(guò)構(gòu)造一個(gè)壓縮的數(shù)據(jù)庫(kù)結(jié)構(gòu)FP樹(shù)來(lái)對(duì)它進(jìn)行挖掘。,2020/10/11,66,例使用頻繁模式增長(zhǎng)的方法，來(lái)考慮下面的例子。,2020/10/11,67,第一遍掃描數(shù)據(jù)庫(kù)D的結(jié)果與Apriori相同，它導(dǎo)出頻繁1-項(xiàng)集的集合，并得到它們的支持度計(jì)數(shù)。設(shè)最小支持度計(jì)數(shù)為2。頻繁項(xiàng)的集合按照支持度計(jì)數(shù)的遞減順序排序。即： L=I2：7，I1：6，I3：6，I4：2，I5：2。 構(gòu)造FP-樹(shù)：首先，創(chuàng)建樹(shù)的根節(jié)點(diǎn)，用“null”標(biāo)記。第二遍掃描數(shù)據(jù)庫(kù)D。每個(gè)事務(wù)中的項(xiàng)按照L中的次序處理并對(duì)每個(gè)事務(wù)創(chuàng)建一個(gè)分枝。,2020/10/11,68,例如：第一個(gè)事

39、務(wù)“T100：I1，I2，I5”按L的次序包含三個(gè)項(xiàng)I2，I1，I5，導(dǎo)致構(gòu)造樹(shù)的第一個(gè)分枝（I2：1），（I1：1），（I5：1）。該分枝具有三個(gè)節(jié)點(diǎn)，其中，I2作為根的子女鏈接，I1鏈接到I2，I5鏈接到I1。 第二個(gè)事務(wù)T002按L的次序包含I2和I4，它導(dǎo)致一個(gè)分枝，其中，I2鏈接到根，I4鏈接到I2。然而，該分枝應(yīng)當(dāng)與T100已存在的路徑共享前綴I2。這樣，將節(jié)點(diǎn)I2的計(jì)數(shù)增加1，并創(chuàng)建一個(gè)新節(jié)點(diǎn)（I4：1），它作為（I2：2）的子女鏈接。一般地，當(dāng)為一個(gè)事務(wù)考慮增加分枝時(shí)，沿著共同前綴上的每個(gè)節(jié)點(diǎn)的計(jì)數(shù)增加1，為跟隨在前綴之后的項(xiàng)創(chuàng)建節(jié)點(diǎn)并鏈接。,2020/10/11,69,存放壓

40、縮的頻繁模式信息的FP樹(shù),2020/10/11,70,為方便樹(shù)的遍歷，創(chuàng)建一個(gè)項(xiàng)頭表，使得每個(gè)項(xiàng)通過(guò)一個(gè)節(jié)點(diǎn)鏈指向它在樹(shù)中的出現(xiàn)位置（節(jié)點(diǎn)）。掃描所有的事務(wù)之后得到的樹(shù)，帶有相關(guān)節(jié)點(diǎn)鏈。這樣，數(shù)據(jù)庫(kù)頻繁模式的挖掘問(wèn)題就轉(zhuǎn)換成挖掘FP-樹(shù)的問(wèn)題。 FP-樹(shù)挖掘：由長(zhǎng)度為1的頻繁模式（初始后綴模式）開(kāi)始，構(gòu)造它的條件模式基，然后構(gòu)造FP樹(shù)，并遞歸地在該樹(shù)上進(jìn)行挖掘。通過(guò)后綴模式與由FP樹(shù)產(chǎn)生的頻繁模式連接實(shí)現(xiàn)模式增長(zhǎng)。 注：條件模式基是一個(gè)子數(shù)據(jù)集，由FP樹(shù)中與后綴模式一起出現(xiàn)的前綴路徑集組成。,2020/10/11,71,FP-樹(shù)挖掘總結(jié)：L中的最后一項(xiàng)，而不是第一項(xiàng)開(kāi)始。通過(guò)上述方法我們可以知

41、道：,對(duì)于I5有兩個(gè)分枝。這些路徑由分枝,形成。這樣，考慮I5為后綴，它的兩個(gè)對(duì)應(yīng)的前綴路徑是,它們形成I5的條件模式基。它的條件FP-樹(shù)只包含單個(gè)路徑;不包含I3，因?yàn)樗闹С侄扔?jì)數(shù)為1，小于最小支持度計(jì)數(shù)。該單個(gè)路徑產(chǎn)生頻繁模式的所有組合：I2 I5：2，I1 I5：2，I2 I1 I5：2。,2020/10/11,72,例通過(guò)創(chuàng)建條件模式基挖掘FP-樹(shù)。 Item 條件模式基 條件FP=數(shù) 產(chǎn)生的頻繁模式 I5 （I2 I1：1），（I2 I1 I3：1） I2：2，I1：2 I2 I5：2，I2 I1 I5：2 I4 （I2 I1：1），（I2：1） I2：2 I2 I4：2 I3 （

42、I2 I1：2），（I2：2），（I1：2） I2：4，I1：2 I2 I3：4 I2 I1：2 I1 （I2：4） I2：4 I2 I1：4,對(duì)于I4，它的兩個(gè)前綴形成條件模式基（I2 I1：1），（I2：1），產(chǎn)生一個(gè)單節(jié)點(diǎn)的條件FP-樹(shù)I2：2，并導(dǎo)出一個(gè)頻繁模式I2 I4：2。 注意，盡管I5跟在第一個(gè)分枝中的I4之后，也沒(méi)有必要在此分析中包含I5，因?yàn)樯婕癐5的頻繁模式在I5的考察時(shí)已經(jīng)分析過(guò)。這就是我們?yōu)槭裁丛贚的后端，而不是在前端開(kāi)始處理的原因。,2020/10/11,73,與以上分析類(lèi)似，I3的條件模式基是（I2 I1：2），（I2：2），（I1：2）。它的條件FP-樹(shù)有兩個(gè)分

43、枝,.它產(chǎn)生模式集：I2 I3：4，I1 I3：2，I2 I1：2。 最后，I1的條件模式基是（I2：4），它的FP-樹(shù)包含一個(gè)節(jié)點(diǎn)I2：4，產(chǎn)生一個(gè)頻繁模式I2 I1：4。,2020/10/11,74,算法：FP-增長(zhǎng)。使用FP-樹(shù)，通過(guò)模式段增長(zhǎng)，挖掘頻繁模式。 輸入：事務(wù)數(shù)據(jù)庫(kù)D；最小支持度閾值min_sup. 輸出：頻繁模式的完全集,4.5.2 FP-增長(zhǎng)算法的描述,2020/10/11,75,方法： 按以下步驟構(gòu)造FP-樹(shù)： 掃描事務(wù)數(shù)據(jù)庫(kù)D 一次。收集頻繁項(xiàng)的集合F和它們的支持度。對(duì)F按支持度降序排序，結(jié)果為頻繁項(xiàng)表L。 創(chuàng)建FP-樹(shù)的根節(jié)點(diǎn)，以：“null”標(biāo)記它。對(duì)于D每個(gè)事務(wù)

44、Trans，執(zhí)行： 選擇Trans中的頻繁項(xiàng)，并按L中的次序排序。設(shè)排序后的頻繁項(xiàng)表示為p/P，其中p是第一個(gè)元素，而P是剩余元素的表。調(diào)用insert_tree(p/P,T).該過(guò)程執(zhí)行情況如下。如果T有子女N使得N.item_name=p.item_name，則N節(jié)點(diǎn)的計(jì)數(shù)增加1；否則創(chuàng)建一個(gè)新節(jié)點(diǎn)N，將其計(jì)數(shù)設(shè)置為1，鏈接到它的父節(jié)點(diǎn)T，并且通過(guò)節(jié)點(diǎn)鏈接結(jié)構(gòu)將其鏈接到具有相同item_name的節(jié)點(diǎn)。如果P非空，就遞歸地調(diào)用insert_tree（P，N）。,2020/10/11,76,方法(續(xù)）： FP樹(shù)的挖掘：通過(guò)調(diào)用FP_growth（FP_tree,null）實(shí)現(xiàn)。 該過(guò)程實(shí)現(xiàn)如

45、下： Procedure FP_growth（Tree， ） if Tree 含單個(gè)路徑P then for each 路徑P中節(jié)點(diǎn)的每個(gè)組合（記作） 產(chǎn)生模式U，擁有支持度為節(jié)點(diǎn)中的最小支持度； else for each 樹(shù)的頭部列表節(jié)點(diǎn)ai 產(chǎn)生一個(gè)模式=aiU ，其支持度support=ai.support； 構(gòu)造的條件模式基，然后構(gòu)造的條件FP-樹(shù)Tree if Tree then 調(diào)用FP_growth（Tree，）,2020/10/11,77,對(duì)FP-樹(shù)方法的性能的研究表明：對(duì)于挖掘長(zhǎng)的和短的頻繁模式，它都是有效的和可伸縮的，并且大約比Apriori算法快一個(gè)數(shù)量級(jí)。,4.5.3

46、 FP-增長(zhǎng)算法的評(píng)價(jià),2020/10/11,78,有關(guān)技術(shù)能用于產(chǎn)生比基本規(guī)則更復(fù)雜的關(guān)聯(lián)規(guī)則。,4.6 高級(jí)關(guān)聯(lián)規(guī)則技術(shù),2020/10/11,79,概念層次表明了不同項(xiàng)目之間的集合關(guān)系。 泛化關(guān)聯(lián)規(guī)則利用概念層次產(chǎn)生不同層次的關(guān)聯(lián)規(guī)則。 利用概念層次，可以在任何層次以及所有層次上生成關(guān)聯(lián)規(guī)則。,4.6.1 泛化關(guān)聯(lián)規(guī)則技術(shù),2020/10/11,80,圖中表示了食品的部分概念層次，該層次表明小麥面包是面包的一種。 關(guān)聯(lián)規(guī)則“面包花生醬”比“谷物花生醬”具有更低的支持度和閾值。也很顯然，包含任何一種谷物的事務(wù)比包含面包的事務(wù)多。 要在初級(jí)概念層次上找到高支持的購(gòu)買(mǎi)模式是困難的。 泛化關(guān)聯(lián)規(guī)

47、則的表示與常規(guī)關(guān)聯(lián)規(guī)則類(lèi)似（X Y），但要求Y中不存在比X中任何項(xiàng)目更高層次的項(xiàng)目。,2020/10/11,81,泛化關(guān)聯(lián)規(guī)則的一個(gè)變種是多層關(guān)聯(lián)規(guī)則。 對(duì)于多層關(guān)聯(lián)規(guī)則，項(xiàng)目集可以出現(xiàn)在概念層次的任何層次上。 利用Apriori算法的一個(gè)變種，可以用自頂向下的方式遍歷概念層次，并生成大項(xiàng)目集。 發(fā)現(xiàn)層次i的大項(xiàng)目集后，可以生成層次i+1的大項(xiàng)目集。 概念層次中某一層次的k階大項(xiàng)目集可以用作候選，以便生成下一層次中孩子節(jié)點(diǎn)的k階大項(xiàng)目集。 概念層次中越高層的項(xiàng)目集的支持度也越高，關(guān)聯(lián)規(guī)則所需的最小支持度會(huì)隨著不同的層次而變化。應(yīng)用規(guī)則： 概念層次中處于同一層次的所有結(jié)點(diǎn)的最小支持度是一樣的。

48、如果用ai表示概念層次中層次i的最小支持度，用ai-1表示層次i-1的最小支持度，則ai-1ai。,4.6.2 多層關(guān)聯(lián)規(guī)則,2020/10/11,82,迄今討論的關(guān)聯(lián)規(guī)則算法假定數(shù)據(jù)是類(lèi)別型的。 數(shù)量關(guān)聯(lián)規(guī)則涉及了類(lèi)別型和數(shù)量型數(shù)據(jù)。 一個(gè)數(shù)量關(guān)聯(lián)規(guī)則的例子是： 顧客買(mǎi)3050美元一瓶的白酒他也買(mǎi)魚(yú)子醬 不同于傳統(tǒng)關(guān)聯(lián)規(guī)則，如： 顧客買(mǎi)白酒他也買(mǎi)魚(yú)子醬 消費(fèi)數(shù)量被劃分到一個(gè)區(qū)間（像聚類(lèi)或分類(lèi)中處理數(shù)值數(shù)據(jù)一樣），項(xiàng)目可能是(面包：01),(面包：(12), (面包：(2), (果凍：01.5), (果凍：(1.5) 因?yàn)閷⒁粋€(gè)大項(xiàng)目分成了幾個(gè)項(xiàng)目，需要降低用于數(shù)量關(guān)聯(lián)規(guī)則的最小支持度或最小置

49、信度。 當(dāng)存在大量區(qū)間時(shí)，最小支持度問(wèn)題會(huì)顯著惡化。,4.6.3 數(shù)量關(guān)聯(lián)規(guī)則,2020/10/11,83,4.7 由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則,一旦從數(shù)據(jù)庫(kù)D的事務(wù)中找出了頻繁項(xiàng)集，由它們產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則是直截了當(dāng)?shù)?。置信度使用下式?jì)算：,Confidence(A B)=support_count(AB)/support_count(A) 其中：support_count(AB) 是包含AB的事務(wù)數(shù)， support_count(A) 是包含A的事務(wù)數(shù)。,2020/10/11,84,關(guān)聯(lián)規(guī)則產(chǎn)生的步驟： 第1步：對(duì)于每一個(gè)頻繁項(xiàng)集I，產(chǎn)生I的所有非空子集。 第2步：對(duì)于I的每一個(gè)非空子集s，如果 s

50、upport_count(I)/support_count(s) = min_conf 則輸出關(guān)聯(lián)規(guī)則“s （I-s）” ，其中min_conf為最小置信度閾值。,2020/10/11,85,例假設(shè)數(shù)據(jù)包含頻繁項(xiàng)集I=I1，I2，I5： 第1步：對(duì)于頻繁項(xiàng)集I=I1，I2，I5，產(chǎn)生I的所有非空子集:I1,I2,I1,I5,I2,I5,I1,I2,I5 第2步：對(duì)于I的每一個(gè)非空子集s，輸出關(guān)聯(lián)規(guī)則“s （I-s）” I1I2I5 confidence=2/4=50% I1I5I2 confidence=2/2=100% I2I5I1 confidence=2/2=100% I1I2I5 co

51、nfidence=2/6=33% I2I1I5 confidence=2/7=29% I5I1I2 confidence=2/7=100%,2020/10/11,86,如果最小置信度設(shè)定為70，則只有以下三個(gè)關(guān)聯(lián)規(guī)則輸出： I1I5I2 confidence=2/2=100% I2I5I1 confidence=2/2=100% I5I1I2 confidence=2/7=100%,2020/10/11,87,當(dāng)用數(shù)據(jù)挖掘的算法得出了一些結(jié)果之后，數(shù)據(jù)挖掘系統(tǒng)如何知道哪些規(guī)則對(duì)于用戶(hù)來(lái)說(shuō)是有用的、有價(jià)值的，這里有兩個(gè)層面： 用戶(hù)主觀的層面 系統(tǒng)客觀的層面。,4.8 關(guān)聯(lián)規(guī)則價(jià)值衡量的方法,20

52、20/10/11,88,很多的算法都使用“支持度-可信度”的框架。 并不是所有被挖掘出的強(qiáng)關(guān)聯(lián)規(guī)則都有意義或都有用。 這樣的結(jié)構(gòu)有時(shí)會(huì)產(chǎn)生一些錯(cuò)誤的結(jié)果。,4.8.1 系統(tǒng)客觀層面,2020/10/11,89,例如下是從一個(gè)有5000名學(xué)生的學(xué)校的調(diào)查結(jié)果中進(jìn)行挖掘的實(shí)例。提供早餐的零售商對(duì)這些學(xué)生每天早上所從事的活動(dòng)進(jìn)行了一次調(diào)查。數(shù)據(jù)表明：60%的學(xué)生（3000名學(xué)生）打籃球，75%的學(xué)生（3750名學(xué)生）吃這種早餐，40%的學(xué)生（2000名學(xué)生）既打籃球，也吃這種早餐。那么如果設(shè)minsup為40%，minconf為60%挖掘關(guān)聯(lián)規(guī)則，我們可以得到如下的關(guān)聯(lián)規(guī)則： 打籃球吃早餐（1） 這

53、條規(guī)則相應(yīng)的置信度為2000/3000=0.66，是錯(cuò)誤的關(guān)聯(lián)規(guī)則，因?yàn)槌栽绮偷膶W(xué)生的比例是75%，大于66%。打籃球和吃早餐實(shí)際上是負(fù)關(guān)聯(lián)的。,只憑支持度和置信度閾值未必總能找出符合實(shí)際的規(guī)則,2020/10/11,90,為了消除這種誤導(dǎo)的規(guī)則，應(yīng)該在關(guān)聯(lián)規(guī)則AB的置信度超過(guò)某個(gè)特定的度量標(biāo)準(zhǔn)時(shí)，定義它為有意義的。 因此有如下關(guān)聯(lián)規(guī)則S（A，B）/S（A） - S（B） d或者：S（A，B）- S（A）*S（B） k 式中d和k是適當(dāng)?shù)牧俊?從而提出了興趣度的概念,2020/10/11,91,為了刪掉一些無(wú)趣的規(guī)則，即避免生成“錯(cuò)覺(jué)”的關(guān)聯(lián)規(guī)則，人們定義了興趣度的度量值，通過(guò)興趣度來(lái)修剪無(wú)趣

54、的規(guī)則 。 今后確定關(guān)聯(lián)規(guī)則可以采用三個(gè)度量值：支持度、置信度、興趣度。,興趣度的定義,2020/10/11,92,引入如下計(jì)算公式： InterestR = (CR - SRH)/maxCR , SRH 其中：CR為規(guī)則R的置信度， SRH為原始記錄中支持該規(guī)則推出的信息，即規(guī)則右部H的比例。 早餐問(wèn)題的興趣度計(jì)算： InterestR = (CR - SRH)/maxCR , SRH =（0.66 0.75）/0.75 = -0.12,（一）面向差異思想的興趣度定義,2020/10/11,93,（二）已有的幾種興趣度的定義,除了把興趣度作為修剪無(wú)價(jià)值規(guī)則的工具，現(xiàn)在已有許多其他的工作重新認(rèn)

55、識(shí)項(xiàng)集，如Brin等考慮的相關(guān)規(guī)則中，討論了蘊(yùn)涵（暗示）規(guī)則(implication rule)，規(guī)則的蘊(yùn)涵強(qiáng)度在0,之間變化，其中蘊(yùn)涵強(qiáng)度為1表示完全無(wú)關(guān)的規(guī)則，表示完備的規(guī)則，如果蘊(yùn)涵強(qiáng)度大于1則表示更大的期望存在性。 另一個(gè)度量值“收集強(qiáng)度”(collective strength)被定義，他們?cè)O(shè)想使用“大于期望值”來(lái)發(fā)現(xiàn)有意義的關(guān)聯(lián)規(guī)則。項(xiàng)集的“收集強(qiáng)度”是0,之間的一個(gè)數(shù)值，其中0表示完備的否定相關(guān)性，而值表示完備的正相關(guān)性。,2020/10/11,94,結(jié)論： 一條規(guī)則的興趣度越大于0，說(shuō)明我們對(duì)這條規(guī)則越感興趣，即實(shí)際利用價(jià)值越大。 一條規(guī)則的興趣度越小于0，說(shuō)明我們對(duì)這條規(guī)則的

56、反面規(guī)則越感興趣，即其反面規(guī)則的實(shí)際利用價(jià)值越大。 另外一個(gè)事實(shí)：興趣度門(mén)限值定得越高，挖掘出的規(guī)則越少，反之，挖掘出的規(guī)則越多。,（三）興趣度的實(shí)際意義,2020/10/11,95,以上討論只是基于系統(tǒng)方面的考慮，但是一個(gè)規(guī)則的有用與否最終取決于用戶(hù)的感覺(jué)。只有用戶(hù)可以決定規(guī)則的有效性、可行性。所以應(yīng)該將用戶(hù)的需求和系統(tǒng)更加緊密的結(jié)合起來(lái)。,4.8.2 用戶(hù)主觀層面,提出了一種基于約束的挖掘,2020/10/11,96,具體約束的內(nèi)容可以有： 數(shù)據(jù)約束。用戶(hù)可以指定對(duì)哪些數(shù)據(jù)進(jìn)行挖掘，而不一定是全部的數(shù)據(jù)。 指定挖掘的維和層次。用戶(hù)可以指定對(duì)數(shù)據(jù)在哪些維以及在這些維上哪些層次進(jìn)行挖掘。 規(guī)則

57、約束。可以指定哪些類(lèi)型的規(guī)則是我們所需要的。引入一個(gè)模板的概念，用戶(hù)使用它來(lái)確定哪些規(guī)則是令人感興趣的而哪些則不然：如果一條規(guī)則匹配一個(gè)包含的模板，則是令人感興趣的，然而如果一條規(guī)則匹配一個(gè)限制的模板，則被認(rèn)為是缺乏興趣的。,2020/10/11,97,在算法中結(jié)合約束條件： 提高了效率 使挖掘的目的更加明確化 具體方法： Kleinberg等人引入并研究了一個(gè)新的優(yōu)化問(wèn)題分段問(wèn)題，這個(gè)框架包含了一些標(biāo)準(zhǔn)的組合分類(lèi)問(wèn)題。這個(gè)模型根據(jù)基本的目標(biāo)函數(shù)，對(duì)“被挖掘的數(shù)據(jù)”的價(jià)值提供一個(gè)特殊的算法的視角，顯示了從這方面導(dǎo)出的具體的優(yōu)化問(wèn)題的廣泛的應(yīng)用領(lǐng)域。 Korn等就利用猜測(cè)誤差(使用“均方根”來(lái)定

58、義)來(lái)作為一些從給定的數(shù)據(jù)集中對(duì)所發(fā)現(xiàn)規(guī)則的“好處”的度量，他們所定義的比例規(guī)則就是如下的規(guī)則：顧客大多數(shù)分別花費(fèi) 1 : 2 : 5的錢(qián)在“面包”:“牛奶”:“奶油”上。,2020/10/11,98,通過(guò)確定未知的(等價(jià)的，被隱藏的，丟失的)值，比例規(guī)則可以用來(lái)作決策支持。如果數(shù)據(jù)點(diǎn)線(xiàn)性地相關(guān)的話(huà)，那么比例規(guī)則能達(dá)到更緊湊的描述，即關(guān)聯(lián)規(guī)則更好地描述了相關(guān)性,2020/10/11,99,在客戶(hù)關(guān)系管理（CRM）理論中有一個(gè)經(jīng)典的2/8原則，即80%利潤(rùn)來(lái)自20%客戶(hù)。那么，這20%的客戶(hù)都有什么特征呢？ 調(diào)查發(fā)現(xiàn)，大部分企業(yè)每年有20%50%的客戶(hù)是變動(dòng)的。企業(yè)一方面在挖空心思爭(zhēng)取新客戶(hù)，另

59、一面卻不斷失去老客戶(hù)。有沒(méi)有辦法找出，失去的是哪一類(lèi)型的客戶(hù)，得到的又是哪種類(lèi)型的客戶(hù)。在競(jìng)爭(zhēng)激烈的商業(yè)時(shí)代，資源占有成為決定企業(yè)生死成敗的關(guān)鍵。在客戶(hù)關(guān)系方面，企業(yè)總希望建立與客戶(hù)最穩(wěn)固的關(guān)系，并最有效率地把這種關(guān)系轉(zhuǎn)化為利潤(rùn)，即留住老顧客、發(fā)展新顧客并鎖定利潤(rùn)率最高的客戶(hù)，這也就是CRM要重點(diǎn)研究的問(wèn)題。 為了實(shí)現(xiàn)這個(gè)目標(biāo)，企業(yè)就需要盡可能地了解客戶(hù)的行為，但這種了解不可能通過(guò)與客戶(hù)接觸直接獲得，因?yàn)槠髽I(yè)不可能挨個(gè)與客戶(hù)交談，而且他們所需要的信息單個(gè)客戶(hù)往往無(wú)法提供。,4.9 關(guān)聯(lián)規(guī)則挖掘在CRM中的應(yīng)用,4.9.1 CRM簡(jiǎn)介,2020/10/11,100,企業(yè)所能做的，就是盡可能收集顧客的信息，借助各種分析方法，透過(guò)無(wú)序的、表層的信息挖出內(nèi)在的知識(shí)和規(guī)律，這就當(dāng)前十分流行的數(shù)據(jù)挖掘技術(shù)所研究的。 在挖出大量信息之后，企業(yè)就可以根據(jù)這些規(guī)律或用這些信息設(shè)計(jì)數(shù)學(xué)模型，對(duì)未發(fā)生行為做出結(jié)果預(yù)測(cè)，為企業(yè)的綜合經(jīng)營(yíng)決策、市場(chǎng)策劃提供依據(jù)。 在CRM中，數(shù)據(jù)挖掘是從大量的有關(guān)客戶(hù)的數(shù)據(jù)中挖掘出隱含的、先前未知的、對(duì)企業(yè)決策有潛在價(jià)值的知識(shí)和規(guī)則。,2020