數(shù)據(jù)挖掘FP與Apriori試驗(yàn)報(bào)告

1、數(shù)據(jù)挖掘買(mǎi)驗(yàn) 數(shù)據(jù)挖掘?qū)嶒?yàn)報(bào)告 - Apriori算法和FP增長(zhǎng)算法挖掘頻繁項(xiàng)集 問(wèn)題描述: 一、數(shù)據(jù)庫(kù)有5個(gè)事務(wù)如：表設(shè)min_sup=60%zmin_conf=80% TID 購(gòu)買(mǎi)的商品 T100 M,O,N,K,E,Y T200 D,O,N,K,E,Y T300 M,A,K,E T400 M,U,C,K,Y T500 C,O,O,K,I,E 表 分別使用Apriori和FP增長(zhǎng)算法找出所有頻繁項(xiàng)集。并比較兩種挖掘過(guò)程的效率。 列舉所有與卜面元規(guī)則匹配的強(qiáng)關(guān)聯(lián)規(guī)則(給出支持度s和置信度c),其中，X是代表 顧客的變量，itemi是表示項(xiàng)的變量(如“A”，B”)： V x transacti

2、on,buys(X, item!) A buys(X, item2) = buys(X, iteni3) s, c 問(wèn)題分析： 1. 分別使用Apriori算法和FP算法逐步求的所有的頻繁項(xiàng)集，記錄各自使用的掃描事務(wù)的 總次數(shù)，用于探究各自的效率。 2. 對(duì)于問(wèn)題二可以采取如卜步驟解決：首先找出所仔三項(xiàng)頻繁項(xiàng)集，然后按照元規(guī)則匹配 出關(guān)聯(lián)規(guī)則，最后利用支持度和置信度選出強(qiáng)關(guān)聯(lián)規(guī)則。 解決方案: 1.采用Aporior算法挖掘所有頻繁項(xiàng)集的步驟： 1) 掃描數(shù)據(jù)庫(kù)，對(duì)每個(gè)候選計(jì)數(shù)，得頻繁一項(xiàng)候選集C1如表1： 項(xiàng)集 支持度計(jì)數(shù) A 1 C 2 D 1 E 4 0) 1 K 5 M 3 N 2 0

3、 3 數(shù)據(jù)挖掘買(mǎi)驗(yàn) U 1 Y 3 數(shù)據(jù)挖掘買(mǎi)驗(yàn) 表1 2）由比較候選支持度計(jì)數(shù)與最小支持度計(jì)數(shù)（min_sup*5=3）得頻繁一項(xiàng)集L1如表2 項(xiàng)集 支持度計(jì)數(shù) E 4 的 5 M 3 0 3 Y 3 表2 3）連接（L1XL1）得頻繁二項(xiàng)候選集C2如表3： 項(xiàng)集 k持度計(jì)數(shù) E，K 4 E，M 2 E,0 3 E,Y 2 K,M 3 K,0 3 K,Y 3 M,0 1 M,Y 2 0，Y 2 表3 4）掃描數(shù)據(jù)咋由比較候選支持度計(jì)數(shù)與最小支持度計(jì)數(shù)得頻繁二項(xiàng)集L2如表.4： 項(xiàng)集 k持度計(jì)數(shù) E,K 4 E,。 3 K,M 3 K,0 3 K,Y 3 表4 5）重復(fù)步驟3）（此處可以不用掃

4、描數(shù)據(jù)庫(kù)而是利用Aprioir剪枝進(jìn)行選擇）求的頻繁三項(xiàng) 候選集C3如表5： 項(xiàng)集 支持度計(jì)數(shù) E,K,0 3 E,K,M ) 2 E,K,Y 2 K,M,0 1 K,M,Y 2 K,O,Y 2 表5 6）使用Apriori剪枝可以去掉C3中的E,K,M,E,K,Y,K,M,O,K,M,Y,K,Y,O（因?yàn)檫@些項(xiàng)集中 存在數(shù)據(jù)挖掘買(mǎi)驗(yàn) 不屬于L2中的子集），求的L3。數(shù)據(jù)挖掘買(mǎi)驗(yàn) L3=E,K,0 即求的所有頻繁項(xiàng)集LL L2, L3。 2.采用FP增長(zhǎng)算法挖掘所有頻繁項(xiàng)集得步驟： 1）掃描事務(wù)數(shù)據(jù)庫(kù)，收集頻繁一項(xiàng)集L和對(duì)應(yīng)的支持度計(jì)數(shù)并按降序排列得表6： 項(xiàng)集 支持度計(jì)數(shù) 的 5 E 4 M

5、 3 Y 3 0 3 2）再次掃描事務(wù)數(shù)據(jù)庫(kù)，構(gòu)造FP樹(shù)如圖-1所示: 頻繁模式信息的FP樹(shù)圖.1 3）通過(guò)創(chuàng)建條件模式基挖掘FP樹(shù): 項(xiàng) 條件模式基 條件FP樹(shù) 頻繁項(xiàng)集 Y K,E,M,Y:1,K,E,Y:1,K,M,Y:1 K,Y M K,E,M:2,K,M:1 K,M 0 K,E,M,Y:1,K,E,Y:1,K,E:1 K,O,E,O,K,E,O E K：5 (K：5 K,E 數(shù)據(jù)挖掘買(mǎi)驗(yàn) 即求的所有頻繁項(xiàng)集。 效率分析：在Apriori算法中1） 2） 3） 4）步中分要掃描數(shù)據(jù)庫(kù)多次而在FP增長(zhǎng)算法中只 需要在1） 2）步驟中掃描數(shù)據(jù)庫(kù)。因此FP增長(zhǎng)算法的效率比Apriori算法效率高！ 由頻繁三項(xiàng)集L3=K,E,0產(chǎn)生關(guān)聯(lián)規(guī)則旦匹配元規(guī)則的關(guān)聯(lián)規(guī)則任 KAE=0 Confidence=2/4 E Confidence=100%min_conf=80% 強(qiáng)關(guān)聯(lián)規(guī)則 EAO= K Confidence=100%min_conf=80% 強(qiáng)關(guān)聯(lián)規(guī)則 注：s=3