(數(shù)據(jù)挖掘)關(guān)聯(lián)規(guī)則挖掘-Apriori算法、fp-Tree算法課件

1、關(guān)聯(lián)規(guī)則挖掘7/27/2022 1、Apriori算法Apriori算法命名源于算法使用了頻繁項(xiàng)集性質(zhì)的先驗(yàn)（Prior）知識。 Apriori算法將發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的過程分為兩個(gè)步驟：通過迭代，檢索出事務(wù)數(shù)據(jù)庫中的所有頻繁項(xiàng)集，即支持度不低于用戶設(shè)定的閾值的項(xiàng)集；利用頻繁項(xiàng)集構(gòu)造出滿足用戶最小信任度的規(guī)則。挖掘或識別出所有頻繁項(xiàng)集是該算法的核心，占整個(gè)計(jì)算量的大部分。 Apriori的性質(zhì)： 性質(zhì)1：頻繁項(xiàng)集的所有非空子集必為頻繁項(xiàng)集。性質(zhì)2：非頻繁項(xiàng)集的超集一定是非頻繁的。 Apriori的步驟： 連接步：為找Lk ，通過將Lk-1與自身連接產(chǎn)生候選k項(xiàng)集的集合剪枝步：Ck是Lk 的超集，也就

2、是說，Ck的成員可以是也可以不是頻繁的，但所有的頻繁k項(xiàng)集都包含在Ck中。 任何非頻繁的（k-1）項(xiàng)集都不是頻繁k項(xiàng)集的子集。Apriori算法(1) L1=頻繁1項(xiàng)集; (2) for(k=2;Lk-1;k+) do begin (3) Ck=apriori_gen(Lk-1); /新的候選頻繁項(xiàng)集 (4) for all transactions tD do begin /掃描計(jì)數(shù)(5) Ct=subset(Ck,t); /得到t的子集，它們是候選 (6) for all candidates cCt do (7) c.count+; (8) end; (9) Lk=cCk|c.count

3、minsup (10) end; (11) Answer= Apriori算法實(shí)例現(xiàn)有A、B、C、D、E五種商品的交易記錄表，試找出三種商品關(guān)聯(lián)銷售情況(k=3)，最小支持度=50%。實(shí)例解答K=1支持度50K=2支持度50支持度50支持度50支持度50Apriori算法的不足Ck中的項(xiàng)集是用來產(chǎn)生頻集的候選集，最后的頻集Lk必須是Ck的一個(gè)子集。Ck中的每個(gè)元素需在交易數(shù)據(jù)庫中進(jìn)行驗(yàn)證來決定其是否加入Lk，這里的驗(yàn)證過程是算法性能的一個(gè)瓶頸。這個(gè)方法要求多次掃描可能很大的交易數(shù)據(jù)庫，即如果頻集最多包含10個(gè)項(xiàng)，那么就需要掃描交易數(shù)據(jù)庫10遍，這需要很大的I/O負(fù)載。提高Apriori算法的方

4、法Hash-based itemset counting（散列項(xiàng)集計(jì)數(shù)）Transaction reduction（事務(wù)壓縮）Partitioning（劃分）Sampling（采樣）Hash-based itemset counting（散列項(xiàng)集計(jì)數(shù)）將每個(gè)項(xiàng)集通過相應(yīng)的hash函數(shù)映射到hash表 中的不同的桶中，這樣可以通過將桶中的項(xiàng)集 計(jì)數(shù)跟最小支持計(jì)數(shù)相比較先淘汰一部分項(xiàng)集。Transaction reduction（事務(wù)壓縮）減少用于未來掃描的事務(wù)集的大小。一個(gè)基本的原理就是當(dāng)一個(gè)事務(wù)不包含長度為k的頻集，則必然不包含長度為k+1的頻集。從而我們就可以將這些事務(wù)加上標(biāo)記或者刪除，這樣

5、在下一遍的掃描中就可以減少進(jìn)行掃描的事務(wù)集的個(gè)數(shù)。這個(gè)就是AprioriTid的基本思想。Partitioning（劃分）挖掘頻繁項(xiàng)集只需要兩次數(shù)據(jù)庫掃描D中的任何頻繁項(xiàng)集必須作為局部頻繁項(xiàng)集至少出現(xiàn)在一個(gè)部分中第一次掃描：將數(shù)據(jù)劃分為多個(gè)部分并找到局部頻繁項(xiàng)集第二次掃描：評估每個(gè)候選項(xiàng)集的實(shí)際支持度，以確定全局頻繁項(xiàng)集Sampling（采樣）基本思想：選擇原始數(shù)據(jù)的一個(gè)樣本，在這個(gè)樣本上用Apriori算法挖掘頻繁模式通過犧牲精確度來減少算法開銷，為了提高效率，樣本大小應(yīng)該以可以放在內(nèi)存中為宜，可以適當(dāng)降低最小支持度來減少遺漏的頻繁模式可以通過一次全局掃描來驗(yàn)證從樣本中發(fā)現(xiàn)的模式可以通過第二

6、此全局掃描來找到遺漏的模式2000年，Han等提出了一個(gè)稱為FP-tree的算法。 FP-tree算法只進(jìn)行2次數(shù)據(jù)庫掃描。它不使用候選集，直接壓縮數(shù)據(jù)庫成一個(gè)頻繁模式樹，最后通過這棵樹生成關(guān)聯(lián)規(guī)則。FP-tree算法由兩個(gè)主要步驟完成：利用事務(wù)數(shù)據(jù)庫中的數(shù)據(jù)構(gòu)造FP-tree；從FP-tree中挖掘頻繁模式。2、FP-tree 算法（不用生成候選項(xiàng)集）具體過程：掃描數(shù)據(jù)庫一次，得到頻繁1-項(xiàng)集把項(xiàng)按支持度遞減排序再一次掃描數(shù)據(jù)庫，建立FP-tree步驟1：構(gòu)造 FP-tree樹完備: 不會(huì)打破交易中的任何模式包含了頻繁模式挖掘所需的全部信息緊密去除不相關(guān)信息不包含非頻繁項(xiàng)支持度降序排列: 支

7、持度高的項(xiàng)在FP-tree中共享的機(jī)會(huì)也高決不會(huì)比原數(shù)據(jù)庫大（如果不計(jì)算樹節(jié)點(diǎn)的額外開銷)FP-tree 結(jié)構(gòu)的好處步驟2：頻繁模式的挖掘具體過程:(1 ) 根據(jù)事務(wù)數(shù)據(jù)庫D 和最小支持度min_sup， 調(diào)用建樹過程建立FP-tree;(2 ) if (FP-tree 為簡單路徑) 將路徑上支持度計(jì)數(shù)大于等于min_sup 的節(jié)點(diǎn)任意組合，得到所需的頻繁模式 else 初始化最大頻繁模式集合為空(3 ) 按照支持頻率升序，以每個(gè)1 頻繁項(xiàng)為后綴，調(diào)用挖掘算法挖掘最大頻繁模式集(4 ) 根據(jù)最大頻繁模式集合中最大頻繁模式，輸出全部的頻繁模式 FP-tree算法的一個(gè)例子TidItems1I1,

8、I2,I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3事物數(shù)據(jù)庫 ： 第一步、構(gòu)造FP-tree掃描事務(wù)數(shù)據(jù)庫得到頻繁1-項(xiàng)目集F定義minsup=20%，即最小支持度為2重新排列F，把項(xiàng)按支持度遞減排序：I1I2I3I4I567622I2I1I3I4I576622 重新調(diào)整事務(wù)數(shù)據(jù)庫TidItems1I2, I1,I52I2,I43I2,I34I2, I1,I45I1,I36I2,I37I1,I38I2, I1,I3,I59I2, I1,I3 創(chuàng)建根結(jié)點(diǎn)和頻繁項(xiàng)目表Item-nameNode-headI2NullI1

9、NullI3NullI4NullI5NullNull 加入第一個(gè)事務(wù)(I2,I1,I5)Item-nameNode-headI2I1I3NullI4NullI5NullI2:1I1:1I5:1 加入第二個(gè)事務(wù)(I2,I4)Item-nameNode-headI2I1I3NullI4I5NullI2:2I1:1I5:1I4:1 加入第三個(gè)事務(wù)(I2,I3)Item-nameNode-headI2I1I3I4I5NullI2:3I1:1I5:1I4:1I3:1 加入第四個(gè)事務(wù)(I2,I1,I4)Item-nameNode-headI2I1I3I4I5NullI2:4I1:2I5:1I4:1I3:1

10、I4:1 加入第五個(gè)事務(wù)(I1,I3)Item-nameNode-headI2I1I3I4I5NullI2:4I1:2I5:1I4:1I3:1I4:1I1:1I3:1 加入第六個(gè)事務(wù)(I2,I3)Item-nameNode-headI2I1I3I4I5NullI2:5I1:2I5:1I4:1I3:2I4:1I1:1I3:1 加入第七個(gè)事務(wù)(I1,I3)Item-nameNode-headI2I1I3I4I5NullI2:5I1:2I5:1I4:1I3:2I4:1I1:2I3:2 加入第八個(gè)事務(wù)(I2,I1,I3,I5)Item-nameNode-headI2I1I3I4I5NullI2:6I1

11、:3I5:1I4:1I3:2I4:1I1:2I3:2I5:1I3:1 加入第九個(gè)事務(wù)(I2,I1,I3)Item-nameNode-headI2I1I3I4I5NullI2:7I1:4I5:1I4:1I3:2I4:1I1:2I3:2I5:1I3:2 第二步、FP-growth首先考慮I5，得到條件模式基、構(gòu)造條件FP-tree得到I5頻繁項(xiàng)集：I2,I5:2,I1,I5:2,I2,I1,I5:2Item-nameNode-headI2I1NullI2:2I1:2I3:1 第二步、FP-growth接著考慮I4，得到條件模式基、構(gòu)造條件FP-tree得到I4頻繁項(xiàng)集：I2,I4:2Item-nameNode-headI2NullI2:2I1:1 第二步、FP-growth然后考慮I3，得到條件模式基、 構(gòu)造條件FP-tree由于此樹不是單一路徑，因此需要遞歸挖掘I3Item-nameNode-headI2I1NullI2:4I1:2I1:2 第二步、FP-growth遞歸考慮I3，此時(shí)得到I1條件模式基,即I1I3的條件模式基為構(gòu)造條件FP-tree得到I3的頻繁項(xiàng)目集I2,I3:4,I1,I3:4,I2,I1,I3:2Item-nameNode-headI2NullI2:2 第二步、FP-