Apriori算法和FP-growth算法

1、 by王晨曦1.Apriori算法詳解 關(guān)聯(lián)分析是一種在大規(guī)模數(shù)據(jù)集中尋找有趣關(guān)系的任務(wù)。頻繁項(xiàng)集是經(jīng)常出現(xiàn)在一塊的物品的集合，關(guān)聯(lián)規(guī)則暗示兩種物品之間可能存在很強(qiáng)的關(guān)系。 頻繁項(xiàng)集是指那些經(jīng)常出現(xiàn)在一起的物品的集合，上表的集合葡萄酒，尿布，豆奶就是頻繁項(xiàng)集的一個(gè)例子，從上面的數(shù)據(jù)集也可以找到諸如尿布葡萄酒的關(guān)聯(lián)規(guī)則。交易號(hào)碼交易號(hào)碼商品商品0豆奶，萵苣1萵苣，尿布，葡萄酒，甜菜2豆奶，尿布，葡萄酒，橙汁3萵苣，豆奶，尿布，葡萄酒4萵苣，豆奶，尿布，橙汁 如何定義這些有趣的關(guān)系呢？誰(shuí)來(lái)定義什么是有趣的？當(dāng)尋找頻繁項(xiàng)集時(shí)，頻繁的定義是什么？有許多概念可以解答上述問(wèn)題，不過(guò)其中最重要的是支持度和置

2、信度。 一個(gè)項(xiàng)集的支持度被定義為數(shù)據(jù)集中包含該項(xiàng)集的記錄所占的比例。從表中可以得到，在5條交易記錄中有3條包含豆奶，尿布，因此豆奶，尿布的支持度是3/5。支持度是針對(duì)項(xiàng)集來(lái)說(shuō)的，因此可以定義一個(gè)最小支持度，而只保留滿(mǎn)足最小支持度的項(xiàng)集。 置信度或可信度是針對(duì)一條諸如尿布葡萄酒的關(guān)聯(lián)規(guī)則定義的。這條規(guī)則的可信度被定義為“支持度(尿布，葡萄酒) /支持度(尿布)”。從表中可以看到，由于尿布，葡萄酒的支持度為3/5，尿布的支持度為4/5，所以“尿布葡萄酒”的可信度為3/4=0.75。這意味著對(duì)于包含“尿布”的所有記錄，我們的規(guī)則對(duì)其中75%的記錄都適用。 支持度和可信度是用來(lái)量化關(guān)聯(lián)分析是否成功的方

3、法。假設(shè)想找到支持度大于0.8的所有項(xiàng)集，應(yīng)該如何去做？一個(gè)辦法是生成一個(gè)物品所有可能組合的清單，然后對(duì)每一種組合統(tǒng)計(jì)它出現(xiàn)的頻繁程度，可是當(dāng)物品成千上萬(wàn)時(shí)，上述做法非常非常慢。為了降低所需的計(jì)算時(shí)間，研究人員發(fā)現(xiàn)一種所謂的Apriori原理。 Apriori原理是說(shuō)如果某個(gè)項(xiàng)集是頻繁的，那么它的所有子集也是頻繁的。例如：項(xiàng)集豆奶,尿布是頻繁的，那么豆奶、尿布也一定是頻繁的，也就是說(shuō)如果一個(gè)項(xiàng)集是非頻繁項(xiàng)集，那么它的所有超集也是非頻繁的。如已知項(xiàng)集橙汁是非頻繁的，我們就知道萵苣，橙汁、牛奶，尿布，橙汁也是非頻繁的。使用該原理可以避免項(xiàng)集數(shù)目的指數(shù)增長(zhǎng)，從而在合理的時(shí)間內(nèi)計(jì)算出頻繁項(xiàng)集。 TID

4、 項(xiàng)目【例3】一個(gè)Apriori的具體例子，該例基于右圖某商店的事務(wù)DB。DB中有9個(gè)事務(wù)，Apriori假定事務(wù)中的項(xiàng)按字典次序存放。1 1，2，5 2，4 2 2，3 3 1，2，4 4 1，3 5 6 2，3 1，3 7 1，2，3，5 8 1，2，3 9 （1）在算法的第一次迭代，每個(gè)項(xiàng)都是候選1-項(xiàng)集的集合C1的成員。算法簡(jiǎn)單地掃描所有的事務(wù)，對(duì)每個(gè)項(xiàng)的出現(xiàn)次數(shù)計(jì)數(shù)。 C1 項(xiàng)集 支持度計(jì)數(shù) 1 6 掃描D,對(duì)每 個(gè)候選計(jì)數(shù) 2 7 3 6 4 2 5 2 （2）設(shè)最小支持計(jì)數(shù)為2，可以確定1-頻集的集合L 1。它由具有最小支持度的候選1-項(xiàng)集組成。L1 項(xiàng)集 支持度計(jì)數(shù) 1 6 比

5、較候選支持度計(jì)數(shù) 2 7 與最小支持度計(jì)數(shù) 3 6 4 2 5 2 （3）為發(fā)現(xiàn)繁-頻集的集合L2，算法 使用L1L1 產(chǎn)生候選2-項(xiàng)集集合C2。C2 項(xiàng)集 1，2 1，3 1，4 1，5 由L1產(chǎn)生候選C2 2，3 2，4 2，5 3，4 3，5 4，5 （4）掃描D中事務(wù)，計(jì)算C2中每個(gè)候選項(xiàng) 集的支持計(jì)數(shù)。 C2 項(xiàng)集 支持度計(jì)數(shù) 1，2 4 1，3 4 1，4 1 1，5 2 掃描D,對(duì)每 個(gè)候選計(jì)數(shù) 2，3 4 2，4 2 2，5 2 3，4 0 3，5 1 4，5 0 （5）確定2-頻集的集合L2 ，它由具 有最小支持度的C2中的候選2-項(xiàng)集組成。 L2 項(xiàng)集 支持度計(jì)數(shù) 1，2

6、4 1，3 4 比較候選支持度計(jì)數(shù) 與最小支持度計(jì)數(shù) 1，5 2 2，3 4 2，4 2 2，5 2 （6）候選3-項(xiàng)集的集合C3 的產(chǎn)生如下：連接：C3=L2 L2 項(xiàng)集項(xiàng)集1,2,31,2,51,3,52,3,42,3,52,4,5項(xiàng)集項(xiàng)集1,21,31,52,32,42,5L2C3利用Apriori性質(zhì)剪枝：頻繁項(xiàng)集的所有子集必須是頻繁的。存在候選項(xiàng)集， 判斷其子集是否頻繁。l 1,2,3的2-項(xiàng)子集是1,2，1,3和2,3, 它們都是L2的元素。因此保留1,2,3在C3中。 l 1,2,5的2-項(xiàng)子集是1,2，1,5和2,5, 它們都是L2的元素。因此保留1,2,5在C3中。 l 1,

7、3,5的2-項(xiàng)子集是1,3，1,5和3,5, 3,5不是L2的元素，因而不是頻繁的，由C3中 刪除1,3,5。l 2,3,4的2-項(xiàng)子集是2,3，2,4和3,4,其中3,4不是L2的元素，因而不是頻繁的， 由C3中刪除2,3,4。l 2,3,5的2-項(xiàng)子集是2,3，2,5和3,5, 其中3,5不是L2的元素，因而不是頻繁的， 由C3中刪除 2,3,5。 l 2,4,5的2-項(xiàng)子集是2,4，2,5和4,5, 其中4,5不是L2的元素，因而不是頻繁的， 由C3中刪除2,4,5 。 l 這樣，剪枝后C3=1,2,3，1,2,5。 （7）掃描D中事務(wù)，以確定L3 ，它由C3中具有 最小支持度的的候選3

8、-項(xiàng)集組成。 C3 項(xiàng)集 由L2產(chǎn)生候選C3 1，2，3 1，2，5 C3 項(xiàng)集 支持度計(jì)數(shù) 掃描D,對(duì)每 個(gè)候選計(jì)數(shù) 1，2，3 2 1，2，5 2 （8）算法使用L3L3 產(chǎn)生候選4-項(xiàng)集的集合C4。盡管連接產(chǎn)生結(jié)果 1,2,3,5, 這個(gè)項(xiàng)集被剪去，因?yàn)樗淖蛹?,3,5 不是頻繁的。則C4= ,因此算法終止， 找出了所有的頻繁項(xiàng)集。 L3 項(xiàng)集 支持度計(jì)數(shù) 比較候選支持度計(jì)數(shù) 1，2，3 2 與最小支持度計(jì)數(shù) 1，2，5 2 算法：Apriori。使用逐層迭代方法基于候選產(chǎn)生找出頻繁項(xiàng)集。輸入： D:實(shí)物數(shù)據(jù)庫(kù)； Min_sup:最小支持度計(jì)數(shù)閾值。輸出：L：D中的頻繁項(xiàng)集。方法： L

9、1=find_frequent_1-itemsets(D); for(k=2;Lk-1 !=；k+) Ck=apriori_gen(Lk-1); For each 事務(wù) tD/掃描D用于計(jì)數(shù) Ct=subset(Ck,t);/得到t的子集，它們是候選 for each候選cC; C.count+; Lk=cC|c.count=min_stp return L=UkLk；1.5 實(shí)驗(yàn)一# 加載數(shù)據(jù)集def loadDataSet(): return 1, 3, 4, 2, 3, 5, 1, 2, 3, 5, 2, 51.5 實(shí)驗(yàn)二使用UCI蘑菇數(shù)據(jù)集進(jìn)行實(shí)驗(yàn) for item in L1: if

10、 ersection(2): print item輸出：frozenset(2, 85)1.6 Apriori算法的缺點(diǎn)從以上的算法執(zhí)行過(guò)程可以看到Apriori算法的缺點(diǎn):第一:在每一步產(chǎn)生侯選項(xiàng)目集時(shí)循環(huán)產(chǎn)生的組合過(guò)多,沒(méi)有排除不應(yīng)該參與組合的元素;第二:每次計(jì)算項(xiàng)集的支持度時(shí)，都對(duì)數(shù)據(jù)庫(kù)D中的全部記錄進(jìn)行了一遍掃描比較，如果是一個(gè)大型的數(shù)據(jù)庫(kù)的話(huà)，這種掃描比較會(huì)大大增加計(jì)算機(jī)系統(tǒng)的I/O開(kāi)銷(xiāo)。而這種代價(jià)是隨著數(shù)據(jù)庫(kù)的記錄的增加呈現(xiàn)出幾何級(jí)數(shù)的增加。2. FP-growth算法詳解 FP-growth算法是在2000年提出的頻繁項(xiàng)集挖掘算法，前面我們介紹了Apriori挖掘

11、頻繁項(xiàng)集并且進(jìn)行關(guān)聯(lián)分析，這次的FP-growth和Apriori選擇頻繁集有點(diǎn)類(lèi)似的地方，但是本質(zhì)和Apriori完全不一樣。 FP-growth算法只需要對(duì)數(shù)據(jù)庫(kù)進(jìn)行兩次掃描，而Apriori算法對(duì)每個(gè)潛在的頻 繁項(xiàng)集都會(huì)掃描數(shù)據(jù)集判定給定模式是否頻繁，因此FP-growth算法的速度要比Apriori算法快。 FP-growth算法發(fā)現(xiàn)頻繁項(xiàng)集的基本過(guò)程如下：2.1 構(gòu)建FP樹(shù)為構(gòu)建FP樹(shù)，需要對(duì)原始數(shù)據(jù)集掃描兩遍。 第一遍對(duì)所有元素項(xiàng)的出現(xiàn)次數(shù)進(jìn)行計(jì)數(shù)，統(tǒng)計(jì)各個(gè)元素項(xiàng)的出現(xiàn)頻率，去掉不滿(mǎn)足最小支持度的元素項(xiàng)。 L= s: 3, r: 3, t: 3, y: 3, x: 4, z: 5

12、FP-growth算法還需要一個(gè)稱(chēng)為頭指針表來(lái)指定給定元素項(xiàng)的第一個(gè)樹(shù)節(jié)點(diǎn)并記錄各個(gè)元素項(xiàng)的出現(xiàn)次數(shù)。這樣每個(gè)元素項(xiàng)都構(gòu)成一條單鏈表，可以快速訪(fǎng)問(wèn)FP樹(shù)中一個(gè)給定元素項(xiàng)的所有元素。 事務(wù)事務(wù)ID事務(wù)中的元素項(xiàng)事務(wù)中的元素項(xiàng)001r, z, h, j, p002z, y, x, w, v, u, t, s003z004r, x, n, o, s005y, r, x, z, q, t, p006y, z, x, e, q, s, t, m第二遍掃描數(shù)據(jù)集用來(lái)構(gòu)建FP樹(shù)。在構(gòu)建時(shí)，讀入每個(gè)項(xiàng)集并將其添加到一條已經(jīng)存在的路徑中。如果該路徑不存在，則創(chuàng)建一條新路徑。在將每條事務(wù)加到樹(shù)之前，需要對(duì)每個(gè)集合

13、進(jìn)行排序。排序基于元素項(xiàng)的絕對(duì)出現(xiàn)頻率由高到低來(lái)進(jìn)行，并過(guò)濾出不在L中的非頻繁項(xiàng)。過(guò)濾及重排后的事務(wù)如下：事務(wù)事務(wù)ID事務(wù)中的元素項(xiàng)事務(wù)中的元素項(xiàng)過(guò)及重排序后的事務(wù)過(guò)及重排序后的事務(wù)001r, z, h, j, pz,r002z, y, x, w, v, u, t, sz,x,y,s,t003zz,004r, x, n, o, sx,s,r005y, r, x, z, q, t, pz,x,y,r,t006y, z, x, e, q, s, t, mz,x,y,s,t 在對(duì)事務(wù)記錄過(guò)濾和排序之后，就可以構(gòu)建FP樹(shù)了。從空集開(kāi)始，將過(guò)濾和重排序后的頻繁項(xiàng)集一次添加到樹(shù)中。如果樹(shù)中已存在現(xiàn)有元素，

14、則增加現(xiàn)有元素的值；如果現(xiàn)有元素不存在，則向樹(shù)添加一個(gè)分支。對(duì)前兩條事務(wù)進(jìn)行添加的過(guò)程： 依次將每個(gè)事務(wù)都加到FP樹(shù)，最后構(gòu)成的帶頭指針表(HeaderTable)的FP樹(shù)如下圖所示：2.2 從FP樹(shù)中挖掘頻繁項(xiàng)集從FP樹(shù)中抽取頻繁項(xiàng)集的三個(gè)基本步驟如下：1. 從FP樹(shù)中獲得條件模式基；2. 利用條件模式基，構(gòu)建一個(gè)條件FP樹(shù)；3. 迭代重復(fù)步驟1步驟2，直到樹(shù)包含一個(gè)元素項(xiàng)為止。第一步：從FP樹(shù)中獲得條件模式基 首先從頭指針表中的每個(gè)頻繁元素項(xiàng)開(kāi)始，對(duì)每個(gè)元素項(xiàng)，獲得其對(duì)應(yīng)的條件模式基（conditional pattern base）。條件模式基是以所查找元素項(xiàng)為結(jié)尾的路徑集合。每一條路徑

15、其實(shí)都是一條前綴路徑（prefix path）。簡(jiǎn)而言之，一條前綴路徑是介于所查找元素項(xiàng)與樹(shù)根節(jié)點(diǎn)之間的所有內(nèi)容。 每一個(gè)頻繁項(xiàng)的所有前綴路徑（頻繁模式基）為：頻繁項(xiàng)頻繁項(xiàng)前綴路徑前綴路徑z: 5rx, s: 1, z, x, y: 1, z: 1xz: 3, : 1yz, x: 3sz, x, y: 2, x: 1tz, x, y, s: 2, z, x, y, r: 1第二步：根據(jù)條件模式基構(gòu)建條件FP樹(shù) 對(duì)于每一個(gè)頻繁項(xiàng)，都要?jiǎng)?chuàng)建一棵條件FP樹(shù)。可以使用剛才發(fā)現(xiàn)的條件模式基作為輸入數(shù)據(jù)，并通過(guò)相同的建樹(shù)代碼來(lái)構(gòu)建這些樹(shù)。例如對(duì)于為頻繁項(xiàng)t構(gòu)建一個(gè)條件模式樹(shù)，然后對(duì)t,y,t,x重復(fù)該過(guò)程

16、。元素t的條件模式樹(shù)構(gòu)建過(guò)程如下圖所示：注意到元素項(xiàng)s以及r是條件模式基的一部分，但是它們并不屬于條件FP樹(shù)。第三步：遞歸查找頻繁項(xiàng)集 有了FP樹(shù)和條件FP樹(shù)，就可以在前兩步的基礎(chǔ)上遞歸得查找頻繁項(xiàng)集。仍然以元素項(xiàng)t為例，下圖為查找元素項(xiàng)t的頻繁項(xiàng)集的步驟： 圖中紅色的部分即頻繁項(xiàng)集。2.3 實(shí)驗(yàn) 以上述數(shù)據(jù)集為例運(yùn)行FP-growth程序的結(jié)果如下： 最后得到的所有頻繁項(xiàng)集為 set(y), set(y, x), set(y, z), set(y, x, z), set(s), set(x, s), set(t), set(y, t), set(x, t), set(y, x, t), set(z, t), set(y, z, t), set(x, z, t), set(y, x, z, t), set(r), set(x), set(x, z), set(z)實(shí)驗(yàn)二使用同Apriori算法相同的蘑菇數(shù)據(jù)集和相同的支持度，F(xiàn)P算法的運(yùn)行結(jié)果如下：3 總結(jié) FP-growth算法是一種用于發(fā)現(xiàn)數(shù)據(jù)集中頻繁模式的有效方法。由于只