關(guān)聯(lián)分析產(chǎn)生關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則

2關(guān)聯(lián)規(guī)則產(chǎn)生事務(wù)TIDITEMS1I1,I2,I32I2,I3,I43I1,I3,I5,...………關(guān)聯(lián)規(guī)則{I1,I2}{I3}{Ii,Ij}{Ik}……c≥minConf“候選”關(guān)聯(lián)規(guī)則{I1,I2}{I3}{I1,I3}{I2}

{I1,I5}

{I2}{Ii,Ij}{Ik}……頻繁項集+支持度{I1}，7

{I2}，6{I3}，5{I1,I2}，5{I1,I3}，4{I1,I2,I3}，4……，…s≥minSup3方法：對于頻繁k-項集Z，

將集合Z

劃分為

X

和Y

兩個不重疊子集，

由X

和Y

生成“候選”的關(guān)聯(lián)規(guī)則。

若候選規(guī)則X

Y

的置信度滿足閾值，

則X

Y

為關(guān)聯(lián)規(guī)則。

Z

X

Y

這樣的規(guī)則必然已經(jīng)滿足支持度閾值，因為它們是由頻繁項集產(chǎn)生的那么產(chǎn)生關(guān)聯(lián)規(guī)則，是對于所產(chǎn)生出的頻繁k-項集Z，關(guān)聯(lián)規(guī)則產(chǎn)生從頻繁項集產(chǎn)生候選的關(guān)聯(lián)規(guī)則例：頻繁項集{ABCD}，候選規(guī)則有：{ABC}{D}，{ABD}{C}，{ACD}{B}，{BCD}{A}{AB}{CD}，{AC}{BD}，{AD}{BC}，{BC}{AD}，{BD}{AC}，{CD}{AB}{A}{BCD}，{B}{ACD}，{C}{ABD}，{D}{ABC}4前件3，后件1前件2，后件2前件1，后件3還可以產(chǎn)生ABCD、關(guān)聯(lián)規(guī)則產(chǎn)生關(guān)聯(lián)規(guī)則X

Y的強度的度量指標(biāo)：支持度

s：確定規(guī)則可以用于給定數(shù)據(jù)集的頻繁程度置信度c：確定

Y在包含

X的事務(wù)中出現(xiàn)的頻繁程度計算關(guān)聯(lián)規(guī)則的置信度并不需要再次掃描事務(wù)數(shù)據(jù)集5

生成“候選”規(guī)則6暴力破解法基于Apriori的方法暴力破解法(Brute-forceapproach）

計算代價過高7fk

h

fk-h

h

fk-hApriori原理8支持度度量的單調(diào)性按照Apriori原理置信度也遵循“先驗”規(guī)則被剪枝的規(guī)則低置信度規(guī)則9

按照Apriori原理如果規(guī)則X

Y

不滿足置信度閾值，則形如X-

Y+

的規(guī)則一定也不滿足置信度閾值，其中

是X

的子集。例如：10

大家可以看到，前件中項的數(shù)量逐漸變少，后件中項的數(shù)量逐漸變多…算法針對每一個不同大小的頻繁項集，依次處理。根據(jù)頻繁項集

fk和后件Sm，計算規(guī)則(fk-Sm)→Sm的置信度，若滿足閾值要求，則確認該規(guī)則并輸出；基于后件Sm，產(chǎn)生增加了一個項的后件Sm+1的集合{Sm+1}，對其中的每各后件Sm+1，結(jié)合頻繁項集fk，遞歸調(diào)用gen_rules()，處理所有的規(guī)則組合。11如果它滿足閾值要求，則確認該規(guī)則并輸出{1237}

{}{123}{7}{127}{3}{137}{2}{12}

{37}{13}

{27}{23}{17}{1}-{237}{7}-{123}{3}-{127}{17}{23}{27}-{13}{237}{1}{37}-{12}{2}-{137}12{I7I3I2I1}

{}{I7I3I2}{I1}{I7I3I1}{I2}{I7I2I1}{I3}{I7I3}{I2I1}{I7I2}{I3I1}{I3I2}{I7I1}{I7}-{I3I2I1}{I1}-{I7I3I2}{I2}-{I7I3I1}{I7I1}{I3I2}{I3I1}-{I7I2}{I3I2I1}{I7}{I2I1}-{I7I3}{I3}-{I7I2I1}13【例】購物籃分析支持度計數(shù)≥4轉(zhuǎn)換為二元數(shù)據(jù)去除非頻繁項組合產(chǎn)生候選2-項集，并計數(shù)按列求和，統(tǒng)計各數(shù)據(jù)項計數(shù)去除非頻繁項14【例】購物籃分析支持度計數(shù)≥4組合產(chǎn)生候選3-項集（Fk-1

Fk-1）去除非頻繁2-項集超集和非頻繁項組合產(chǎn)生候選4-項集（Fk-1

Fk-1）去除非頻繁2-項集超集和非頻繁項15【例】購物籃分析支持度計數(shù)≥4置信度≥0.85生成規(guī)則提取關(guān)聯(lián)規(guī)則16從頻繁2-項集和頻繁1-項集以及它們的支持度計數(shù)，【例】購物籃分析支持度計數(shù)≥4置信度≥0.85生成規(guī)則提取時，可先提取前件為2-項集，后件為1-項集的規(guī)則，如果置信度不滿足要求，則不再提取前件為1-項集后件為2-項集的規(guī)則。17【例】購物籃分析支持度計數(shù)≥4置信度≥0.85生成規(guī)則提取時，可先提取前件為3-項集，后件為1-項集的規(guī)則，若置信度滿足要求，才繼續(xù)提取22形式的規(guī)則，否則向下剪枝；如果22形式的規(guī)則滿足要求，才繼續(xù)提取13形式的規(guī)則。18【例】購物籃分析支持度計數(shù)≥4置信度≥0.8519{I1,I2,I3,I7}{I1,I2,I3}→{I7}{I1,I2,I7}→{I3}{I1,I3,I7}→{I2}{I2,I3,I7}→{I1}{I3,I7}→{I1,I2}{I2,I7}→{I1,I3}{I1,I7}→{I2,I3}{I2,I3}→{I1,I7}{I1,I3}→{I2,I7}{I1,I2}→{I3,I7}{I7}→{I1,I2,I3}{I3}→{I1,I2,I7}{I2}→{I1,I2,I7}{I1}→{I2,I3,I7}

在格結(jié)構(gòu)中，由這些關(guān)聯(lián)規(guī)則向下衍生出來的規(guī)則，需要進行置信度閾值檢驗；【例】購物籃分析支持度計數(shù)≥4置信度≥0.85關(guān)聯(lián)規(guī)則：

{I7}{I1}，1.0

{I7}{I2}，1.0{I1I2I3}

{I7}，1.0{I1I3I7}{I2}，1.0{I3I7}{I1I2}，1.0{I2I3I7}{I1}，1.0{I1I7}

{I2}，1.0{I7}

{I1I2}，1.0{I2I7}

{I1}，1.0{I3I7}

{I1}，1.0{I3I7}

{I2}，1.020【例】購物籃分析WEKA運行結(jié)果1.I7/5==>I1/5<conf:(1)>lift:(1.38)lev:(0.12)[1]conv:(1.36)2.I7/5==>I2/5<conf:(1)>lift:(1.22)lev:(0.08)[0]conv:(0.91)3.I2/I7/5==>I1/5<conf:(1)>lift:(1.38)lev:(0.12)[1]conv:(1.36)4.I1/I7/5==>I2/5<conf:(1)>lift:(1.22)lev:(0.08)[0]conv:(0.91)5.I7/5==>I1/I2/5<conf:(1)>lift:(1.83)lev:(0.21)[2]conv:(2.27)6.I3/I7/4==>I1/4<conf:(1)>lift:(1.38)lev:(0.1)[1]conv:(1.09)7.I3/I7/4==>I2/4<conf:(1)>lift:(1.22)lev:(0.07)[0]conv:(0.73)8.I2/I3/I7/4==>I1/4<conf:(1)>lift:(1.38)lev:(0.1)[1]conv:(1.09)9.I1/I3/I7/4==>I2/4<conf:(1)>lift:(1.22)lev:(0.07)[0]conv:(0.73)10.I1/I2/I3/4==>I7/4<conf:(1)>lift:(2.2)lev:(0.2)[2]conv:(2.18)11.I3/I7/4==>I1/I2/4<conf:(1)>lift:(1.83)lev:(0.17)[1]conv