數(shù)據(jù)挖掘FPtree樹

1、數(shù)據(jù)倉庫與數(shù)據(jù)挖掘課程報告 FP-tree算法的思考與實現(xiàn)扌旨導老師：蔣良孝姓名：趙冠豪班級：086131學號：201310025622015年10月FP-Tree算法的思考與實現(xiàn)1. 發(fā)現(xiàn)問題在學習數(shù)據(jù)倉庫與數(shù)據(jù)挖掘課程中， 有關關聯(lián)分析的算法，首先是在1994年R.Agrawal 和R.Srikant提出的布爾關聯(lián)規(guī)則挖掘頻繁項集的原創(chuàng)性算法一一Apriori算法，一種使用候選產生發(fā)現(xiàn)頻繁項集的算法。下面以課本P151頁例5-3來進行Apriori算法的演示。AllElectro nics某分店的業(yè)務數(shù)據(jù)TID商品ID的列表T100I1 ， I2 ， I3T200I2，I4T30012,1

2、3T400I1 ， I2 ， I4T500I1，I3T600I2，I3T700I1，I3T800I1 ， I2 ， I3 ， I5T900I1 ， I2 ， I3假設候選項集和頻繁項集的產生，最小支持計數(shù)為那么根據(jù)Apriori算法進行演示：2L1項集支持度計數(shù)掃描D,對每116個候選計數(shù)1127136I42I52項集支持度計數(shù)比較候選支持度6計數(shù)與最小支持I1度計數(shù)I27*I36I42I52C1C2項集11 ,1211 ,13I1 ,14I1 ,15I2 ,1312 ,14I2 ,15I3 ,14I3 ,15由L1產生候 選C2,并掃描 D對每個候選 計數(shù)14 ,15支持度計數(shù)4412422

3、010比較候選支 持度計數(shù)與 最小支持度 計數(shù)L2項集11 ,1211 ,1311 ,15I2 ,1312 ,4I2 ,15支持度計數(shù)442422由L2產生候 選C3 ,并掃描 D對每個候選 計數(shù)通過此演示，我們可以清晰地發(fā)現(xiàn)：雖然在許多情況下，Apriori的候選產生-檢查方法顯著壓縮了候選項集的大小，并導致很好的性能。然而，Apriori算法的每次迭代都會掃描事 務數(shù)據(jù)庫，并且每次每次都會產生大量候選項集，這是 Apriori算法的致命缺陷。例如，如果有10A4個頻繁1項集，則Apriori算法需要產生多達 10A7個候選二項集。 此外為發(fā)現(xiàn)長度為100的頻繁模式，如a1,a2,a100,

4、必須產生總過多達 2人100大約為10A30個候選。再如，Apriori算法需要不斷重復掃描數(shù)據(jù)庫，通過模式匹配檢查一個很大 的候選集合。檢查數(shù)據(jù)庫中的每個事務來確定候選項集的支持度的開銷非常大。因此我們可以得到一個很清晰的結論，在一般情況下，我們在使用Apriori算法（使用候選產生發(fā)現(xiàn)頻繁項集的方法）進行關聯(lián)分析時，想要找到感興趣的規(guī)則，開銷是非常大的，而這正是Apriori算法在實際運用中要改善的問題。2. 分析問題經(jīng)過上面的分析我們可以確定，Apriori算法的兩大限制：產生大量的候選集；O 2重復掃描事務數(shù)據(jù)庫。那么我們分析如何提高Apriori算法的效率時，就有著兩大分析方向。一是

5、考慮降低是事務數(shù)據(jù)庫的掃描次數(shù)，如能不能先掃描一次事務數(shù)據(jù)庫，然后進行分類劃分，找出局部頻繁項集，然后在進行下次掃描。二是考慮如何壓縮候選集，在產生的時候就進行剔除，或者對未來要產生的候選項集，增加一個規(guī)則，壓縮未來迭代掃描的事務數(shù)。顯 然無論是降低掃描的事務數(shù)據(jù)庫的次數(shù)，還是壓縮產生的候選集，都是針對于Apriori算法本身的調整，這就不可能在本質上解決Apriori算法的效率低下問題。在思考這個問題時，我很容易想到，既然是產生大量的候選項集，那么一個很直接的辦法就是：能不能不產生候選集，而直接發(fā)現(xiàn)頻繁項集，從而找出感興趣的關聯(lián)規(guī)則呢。如果我們不產生大量的候選集，那么掃描事務數(shù)據(jù)庫進行匹配的

6、次數(shù)也自然就會大大降低。我在思考過程中，想到老師上課講到的一句話“把條件進行簡單化處理，先找出一個可行解”，這樣思維就大大開闊。聯(lián)系到數(shù)據(jù)倉庫與數(shù)據(jù)挖掘在開始的課程“分類”中的第一個方 法：決策樹，顯然關聯(lián)分析是進行名詞性布爾值的分析，而決策樹的應用范圍也正是名詞性數(shù)據(jù)的分類。我們來對比下，在決策樹算法中，我們根據(jù)元組的信息增益的大小來進行生成 樹的判斷依據(jù)。類比決策樹算法，我們可以利用關聯(lián)分析中事務發(fā)生的支持計數(shù)的大小來代 替熵減值。根據(jù)我在算法導論中所學習到的思想一一遞歸算法中的分治策略，再加上決策樹這個“先例”的借鑒，我對于提高Apriori算法的效率有了一個較為清晰的方向。首先，對于事

7、務數(shù)據(jù)庫中的所有事務都是由一項集構成的，所以我們可以根據(jù)在整個事務數(shù)據(jù)庫中所有的一項集的支持計數(shù)來進行排序（類似決策樹中對于每個元組的熵減值計 算）。接著，參考決策樹算法中樹的生成方法和分治策略思想，我們在掃描事務數(shù)據(jù)庫的一個事務時，根據(jù)第一步的排序順位，進行調整，將該事務的所有項都有序化，依照順序建立一棵樹，下次的事務按照這個方法繼續(xù)對前面的樹的節(jié)點值進行修改、增加節(jié)點或者生成另一棵樹，這樣我們就可以保證越靠近樹根的支持計數(shù)越高，而葉子節(jié)點的支持計數(shù)越低，十分有利于降低我們在挖掘有趣規(guī)則時的開銷。3. 解決問題經(jīng)過上面的分析后，我們對于怎么提高 Apriori算法的有了一個有效的解決辦法。而

8、且在2000年針對Apriori算法的固有缺陷，J.Han等人提出了不產生候選頻繁項集的方法即 FP-tree算法。該算法直接將事務數(shù)據(jù)庫壓縮成一個頻繁模式樹，然后通過這棵樹生成關聯(lián)規(guī)則。而這個算法和我上面分析時提出的思想大致相同，下面我們仍然根據(jù)書上的例子進行FP-tree算法的演示：第一步，進行事務數(shù)據(jù)庫的掃描，得到每個一項集的支持計數(shù)，然后進行排序。所有一項集的計數(shù)：11,6 ，12,713,6,14,2,15,2；按照支持計數(shù)進行排序I27I16I36I42I52第二步，掃描事務數(shù)據(jù)庫的每個事務，生成樹。Null141513: 213: 2I3: 212: 7I5: 1I4: 111:

9、 411: 2第三步，進行強關聯(lián)規(guī)則的挖掘。挖掘前，先進行一下解釋和定義：由每個長度為1的頻繁模式（初始后綴模式）開始，構造它的條件模式基（一個“子數(shù)據(jù)庫”，由FP樹與后綴式一起出現(xiàn)的前綴路徑集組成），然后，構造它的（條件）FP樹，并遞歸地對該樹進行挖掘。模式增長通過后綴模式與條件FP樹產生的頻繁模式連接實現(xiàn)。首先考慮I5 L中的最后一項，而不是第一個。I5出現(xiàn)在樹最深層的葉子節(jié)點上，并且有兩個葉子節(jié)點，我們把這兩條路徑列出來12 ,11，I5 : 1,12 ，I1，I3，I5 : 1，顯然I5的前綴路徑是I2，I1 ： 1，I2，I1，I3 : 1，形成I5的條件模式基，而它的條件 FP樹顯

10、然只包含12,11:2（ I3只出現(xiàn)一次，小于最小支持計數(shù)2）。因此次路徑產生的頻繁模式的所有組合：I2，15:2,11，15:2,12，I1，I5 : 2。那么基于I5的所有條件模式產生的頻繁模式都找到了。同樣的方法進行I4，I3 I1的迭代，得到下表：項條件模式基條件FP樹產生的頻繁模式I5I2 I1:1,<12:2,I1 :2> I2 I5:2,I1 I5:2I2 I1，I3 :1I2 I1 I5:2I4I2 I1:1<12:2>I2 I4:2I2:1I3I2 I1:2<12:4,I1 :2> I2 I3:4,I1 I3:4I2:2,I1 :2 <

11、;11:2>I2 I1 I3:2I1I24<I2:4>I2 11:44.得出結論根據(jù)上面的算法演示，我們接下來進行試驗測試。首先根據(jù)上機時老師講到的利用 Myeclipse將weka當做一個項目文件，在java平臺運行。由于我只是實現(xiàn)了 FP-tree算法, 所以我直接運用 weka平臺進行數(shù)據(jù)測試，測試數(shù)據(jù)為weka平臺自帶的數(shù)據(jù)supermarket.arff 。O supermarket2015/9/9 10:32 ARFF Data File1百79 KB首先我先用 Apriori算法進行測試，supermarket.arff(1979Start開始，到運行處結果，大

12、概用了8s。測試結果如下圖：KB大小的數(shù)據(jù))，從點擊CliGcafy削怙 5ela<c ftitrxtiu.C4c 譏調叮乂刖-JI 100 -C 0 3 -T (- O' - L ! H Q L -5 I (J f Is&Jifine:ws-iaHiBs-DEiati,Apriort -Jr Id -T d -c 0,90-05 -tr l.fl -M G-1 -S -1.0 -e -11£ 1 EL&laL!iiLAtaZLCtfH： 4&S.7list of 直tiribq三書工 caeitteci=»Txde 1 (fiLll

13、±Ea.a.ing-=-=-=t li Kt (f iIE 27 X - Mi軸LMlrLTiLr. sijpptir匸：L -1±LaatidJizea)Miftiirtt<MfiS±attee>L O-QKmir電t flf cyeieairr.era：cc|i e-t a zf 1 q r>:Z12=crdetarla±牡lbPiaeLa工：SLEEof0otlarffelcei53e-3bll)iED3k>cpFafIqrqc-讓口ir二曹Z(3>7913Else；二aeiorliE昶iGeraeLali*F：eza

14、11KBaf3«toflargeiumjcTjLtSM10&31Horseilifgt沁訶ll«>:1二.:巳0 «> Eread sim 2- bo k iJig tired41: faijl亡tldE_4t fELiili-t"(5Cl .* head and皐 bikLoa ?Lfcfrd#-. tr俯盟 3。衛(wèi)-匚 rxuiw-te «> brcdd3鬣723CakeiT.剖6 iU.J bi?euit5*T fry i e*t:tekLigih 15 *> ftT'-sd aff! 亡品冷4版C

15、OSE： L0.9ZIoanf: 0.爐70S 8El£H0 沖器oonf"(0-9215-aq.aX Xci-3=-t trUiTc cozaillqfc E54 => 口二亡&3 ar4 £.&*&= 7B呂tl ecuz. -s 二tce:三且 fczda-t ve ?e3a±l=total-ill st "3"?>tread and cat=-z 725ccr_： : Da 91J?-bHkjLng Ziwdn：掃丄三匚LDlixt v-=ctabl-=i=.ttatai=r.igE F,&

16、gt;br-ed and cak=-t 701cix=f : 0.呂.t-lcMlLa=X fzulx二 Cm匸:曲4獨 ild nA brri&dl ojl! 出l豊三匸 £<4: (0.41)氛 fEC«n (cmxI fmt-c 代工匕比“自二 wtal-hiffn 634 > brefl-a sud75 conf： (091；109 fr-ownfrait=t ssIMilgIn 營琳=> fcrJid and G«k«=t "VT centr (Q .Htji接著我利用FPGrowth算法進行了測試，耗時不到

17、1s。測試結果如下:方曲疆 rlhE-afr OlETAT AllWClIt 再L*t!haiwiilwCLfilrii mvwih T3!嚀 F -S LP -7 D 4 t 卡口 鼻啡* P < P ISTa-r寸 he片* ma lAlCMKlM陷7電h.t 3.由皿.2 Jd Ay申占RUtliEMinprmrkcn：t!LSt-SL：-6S旺廠1LTLj.pr|s =£ iaTtErauTBii, raut'EiadJkrssEX七ei=F芒:wrrt £uiu L4 suLescop 10>-N ID -I D -C 0>-也白-皿-4

18、i 1_>3 -M 4.1C. jrrni-tgi fFism辛戶;i 'B& > 7J3 «-GKf; r-V3>> L-tfts >71 ipwrft smvf|3.2 zb itch-i?MdB=r= biSMl-5_ tcrame: GD => trwd erf 7Hke=:J - <!< tcccZ: C. !2« ? Lz±t; l.r> 1-" < .021 nxrv; i 3.2 ： J3. LfCtill-Tf IMUJd沖色咖“F CH4L«410J

19、 I Finfl 44kM| I HI 瓷朋祖1律冊汁 LlfQl |L.21| IfW 01MI4a IfTOlE#-!, llEJ*U£lti5»Ztl tl3Ct-lTJ*CP nLb2.«nijtL| L £L 5|£1«羈0 L±I±*E : 7 <4 <QljOnf： j,適| 了 14，rE- ll-57jODDV! 43-24iJ - | Ftdll十” AH二丫 jxacic f =dj"ic,r c=t.kl.4i| 皀)4 =a | bnad ujeL: TTS <

20、j=ee±Plk j 1jx±1 l I l.Zj Lav-：, . D41 sirr二 p ,13)«» larwtliMFT rreinwt414)L?1il: nF so frnid iM eich“卜“駅珂1J6I 3«*_ (03) aav： n. selli. Et 尹鈕fclWE. t42ibflfelculrp-T, MT4 二羽 1G11 "I > krtU a mF mEei:和LlitM!1.25i le? it. T1J OMnn FL!_ |trui£.-tP jQL>zijLEA-tr

21、 tDt&L血bj: m > q膽勺 ud ostxj : E 空 cioh£: 0. *L | lilt J hl. 2«3< lnai4t-£>4| eull j 1|IL irews.fmmx.訊f E>A f 訴+ «4 f仙fJi 717 ewCr1>P.W3R 34穴；【入MF|。«!沖 cdh*; mL1. Ifzaifc-ip ficxen "anfe-t-; M3 > 'imaS and ca.let|; !T? szcn±<0-?ll > Hit; il九睥 ;cczrr;壯我分別選取兩個算法生成的頻繁項集的最強關聯(lián)規(guī)則的項集如下：Apriori 算法：1. biscuits=t frozen