關(guān)聯(lián)規(guī)則算法

1、一種基于Hadoop的并行關(guān)聯(lián)規(guī)則算法,關(guān)聯(lián)規(guī)則的動(dòng)機(jī),動(dòng)機(jī): 從數(shù)據(jù)中發(fā)現(xiàn)規(guī)律 什么產(chǎn)品被一起購買? 啤酒和尿布?! 客戶在購買了計(jì)算機(jī)之后還會(huì)購買什么產(chǎn)品? 哪種病菌的DNA對(duì)一種新開發(fā)的藥物非常敏感? 對(duì)web文檔進(jìn)行分類,項(xiàng)是數(shù)據(jù)庫中不可分割的最小單位信息，一般用i表示。項(xiàng)的集合稱為項(xiàng)集，一般用I表示。例如: I=i1,i2，ij項(xiàng)集。包含k個(gè)項(xiàng)目的項(xiàng)集稱為k-項(xiàng)集。 例如，集合面包，牛奶，黃油，啤酒，尿布是一個(gè)5-項(xiàng)集 X Lk !=; k+) do begin Ck+1 = candidates generated from Lk; for each transaction t i

2、n database do increment the count of all candidates in Ck+1 that are contained in t Lk+1 = candidates in Ck+1 with min_support end return k Lk;,stetp1:,Apriori算法實(shí)例,現(xiàn)有A、B、C、D、E五種商品的交易記錄表，試找出三種商品關(guān)聯(lián)銷售情況(k=3)，最小支持度=50%。,實(shí)例解答,K=1,支持度50,用 FP-tree挖掘頻繁項(xiàng)集,韓家煒等人于2000年提出一種富有創(chuàng)新性的方法FP-growth,這種算法采用了一種分而治之的策略。 基本

3、思想 ：分而治之 用FP-tree遞歸增長頻繁集 方法 ： 對(duì)每個(gè)項(xiàng)，生成它的 條件模式庫, 然后是它的 條件 FP-tree 對(duì)每個(gè)新生成的條件FP-tree，重復(fù)這個(gè)步驟 直到結(jié)果FP-tree為空, 或只含唯一的一個(gè)路徑 (此路徑的每個(gè)子路徑對(duì)應(yīng)的都是頻繁集),FP-tree算法的一個(gè)例子,事物數(shù)據(jù)庫 ：,第一步、構(gòu)造FP-tree,掃描事務(wù)數(shù)據(jù)庫得到頻繁1-項(xiàng)目集F 定義minsup=20%，即最小支持度為2 重新排列F，把項(xiàng)按支持度遞減排序：,重新調(diào)整事務(wù)數(shù)據(jù)庫,創(chuàng)建根結(jié)點(diǎn)和頻繁項(xiàng)目表,Null,加入第一個(gè)事務(wù)(I2,I1,I5),Null,I2:1,I1:1,I5:1,加入第二個(gè)事

4、務(wù)(I2,I4),Null,I2:2,I1:1,I5:1,I4:1,加入第三個(gè)事務(wù)(I2,I3),Null,I2:3,I1:1,I5:1,I4:1,I3:1,加入第四個(gè)事務(wù)(I2,I1,I4),Null,I2:4,I1:2,I5:1,I4:1,I3:1,I4:1,加入第五個(gè)事務(wù)(I1,I3),Null,I2:4,I1:2,I5:1,I4:1,I3:1,I4:1,I1:1,I3:1,加入第六個(gè)事務(wù)(I2,I3),Null,I2:5,I1:2,I5:1,I4:1,I3:2,I4:1,I1:1,I3:1,加入第七個(gè)事務(wù)(I1,I3),Null,I2:5,I1:2,I5:1,I4:1,I3:2,I4:

5、1,I1:2,I3:2,加入第八個(gè)事務(wù)(I2,I1,I3,I5),Null,I2:6,I1:3,I5:1,I4:1,I3:2,I4:1,I1:2,I3:2,I5:1,I3:1,加入第九個(gè)事務(wù)(I2,I1,I3),Null,I2:7,I1:4,I5:1,I4:1,I3:2,I4:1,I1:2,I3:2,I5:1,I3:2,第二步、FP-growth,首先考慮I5，得到條件模式基 、 構(gòu)造條件FP-tree 得到I5頻繁項(xiàng)集：I2,I5:2,I1,I5:2,I2,I1,I5:2,Null,I2:2,I1:2,I3:1,第二步、FP-growth,接著考慮I4，得到條件模式基 、 構(gòu)造條件FP-tr

6、ee 得到I4頻繁項(xiàng)集：I2,I4:2,Null,I2:2,I1:1,第二步、FP-growth,然后考慮I3，得到條件模式基 、 構(gòu)造條件FP-tree 由于此樹不是單一路徑，因此需要遞歸挖掘I3,Null,I2:4,I1:2,I1:2,第二步、FP-growth,遞歸考慮I3，此時(shí)得到I1條件模式基 ,即I1I3的條件模式基為 構(gòu)造條件FP-tree 得到I3的頻繁項(xiàng)目集I2,I3:4,I1,I3:4,I2,I1,I3:2,Null,I2:2,第二步、FP-growth,最后考慮I1，得到條件模式基 構(gòu)造條件FP-tree 得到I1的頻繁項(xiàng)目集I2,I1:4,Null,I2:4,存在的問題

7、,Apriori算法和FP-tree算法是基于單節(jié)點(diǎn)的算法。但是,現(xiàn)在的數(shù)據(jù)庫越來越大,達(dá)到了TB級(jí)甚至更大，采用傳統(tǒng)的算法將非常緩慢，甚至不能服務(wù)于有時(shí)限性的問題。 為此，研究人員提出了多種并行挖掘算法，主要有CD、DD、CaD等。CD算法是Apriori的并行實(shí)現(xiàn)，其基本思想是將數(shù)據(jù)平均分配到N個(gè)計(jì)算節(jié)點(diǎn)上，在每個(gè)節(jié)點(diǎn)是采用類似Apriori的算法。 這些并行算法解決了挖掘效率的問題，但是由于并行計(jì)算是由很多計(jì)算節(jié)點(diǎn)組成，節(jié)點(diǎn)失效、負(fù)載不易均衡帶來的問題仍然會(huì)給計(jì)算帶來很多障礙。,存在的問題,例如，CD算法有兩個(gè)嚴(yán)重缺陷: 1) 某個(gè)計(jì)算節(jié)點(diǎn)失敗， 會(huì)導(dǎo)致整個(gè)計(jì)算失敗 2) 計(jì)算節(jié)點(diǎn)的速度

8、存在差異時(shí)，計(jì)算時(shí)間由計(jì)算性能差的節(jié)點(diǎn)決定，這樣會(huì)導(dǎo)致計(jì)算資源的浪費(fèi) 為解決以上問題，在CD算法的基礎(chǔ)上本文提出了基于Hadoop的并行關(guān)聯(lián)規(guī)則算法。 Hadoop是一個(gè)分布式基礎(chǔ)架構(gòu)，是Google Map-Reduce算法的開源實(shí)現(xiàn)，Map-Reduce的執(zhí)行流程主要包括map和reduce兩步。基于Hadoop來改進(jìn)CD算法，可以彌補(bǔ)上述兩個(gè)缺陷。,Dear Car Bear,Car Car River,Dear 1 Dear 1,Car 1 Car 1 Car 1,Bear 1 Bear 1,River 1 River 1,Dear 2,Car 3,Bear 2,River 2,1.I

9、nput,2.splitting,3.mapping,4.shuffing,5.reducing,6.result,Map-Reduce執(zhí)行流程的一個(gè)例子,基于Hadoop的并行關(guān)聯(lián)規(guī)則算法的偽代碼描述,Main() while( k 項(xiàng)候選集非空) job = new job job SetInputClass( class MyInput) / /設(shè)置處理輸 入數(shù)據(jù)的類， class MyInput 處理輸入數(shù)據(jù)產(chǎn)生 key value 對(duì) job SetOutputKey( class outputkey) / /設(shè)置輸出 數(shù)據(jù)的關(guān)鍵字類型 job SetOutputValue( cla

10、ss outputvalue) / /設(shè)置輸 出數(shù)據(jù)的值類型 job SetMap ( class MyMapClass) / /設(shè)置進(jìn)行各塊數(shù)據(jù)統(tǒng)計(jì)的類 job SetReduce( class MyReduceClass) / /設(shè)置合 并各個(gè)分塊統(tǒng)計(jì)的類 job run / /運(yùn)行,GetNextCdt / /根據(jù)k 項(xiàng)頻繁項(xiàng)集產(chǎn)生k + 1 項(xiàng)候 選集 k = k + 1 End Main map 的偽代碼描述: Class MyMapClasss / /若干其它定義 map ( InputKey， InputValue， OutputKey， OuputValue ) / /實(shí)現(xiàn) m

11、ap GetCount( InputKey， InputValue) / /統(tǒng)計(jì)計(jì)數(shù) OutResult( OutputKey， OutputValue) / /輸出本塊 的候選集的計(jì)數(shù) End map ,基于Hadoop的并行關(guān)聯(lián)規(guī)則算法的偽代碼描述,reduce 的偽代碼描述如下: Class MyReduce / /若干其它定義 reduce ( InputKey， InputValue， OutputKey， OutputVal- ue) / /實(shí)現(xiàn) reduce GetAllCount( InputKey， InputValue) 合并各個(gè)塊的候 選集計(jì)數(shù) OutResult( OutputKey， OutputValue) / / 輸出候選集 的全局計(jì)數(shù) End reduce ,基于Hadoop的并行關(guān)聯(lián)規(guī)則算法的流程圖,K-1項(xiàng)頻繁項(xiàng)集,Main(),K項(xiàng)候選集,Reduce合并全局s,Main(s),K+1項(xiàng)頻繁項(xiàng)集,K=K+1,yes,結(jié)束,No,算法可靠性和均衡