關(guān)聯(lián)分析由候選項集產(chǎn)生頻繁項集產(chǎn)生候選項集由項產(chǎn)生候選項集A，B，C，D，E五個Item產(chǎn)生25=32個項集2暴力破解(Brute-force)法算法過程：候選項集支持度計數(shù)444…332…21…11………{面包，牛奶}3{面包，尿布}3………{面包，牛奶}3{面包，尿布}3{面包，啤酒}2………{面包，牛奶，尿布}2………minSup=3/NminSup=2/N事務(wù)……3根據(jù)購物籃事務(wù)數(shù)據(jù)產(chǎn)生項列表產(chǎn)生候選項集計算每個項集的支持度(/計數(shù))確定閾值，得到頻繁項集暴力破解(Brute-force)法事務(wù)候選項集……算法的時間復(fù)雜度為O(NMW)N為事務(wù)的項數(shù)W為事務(wù)中項集的維度M為候選項集的項數(shù)支持度計數(shù)444…332…21…11………MN算法過程：W4根據(jù)購物籃事務(wù)數(shù)據(jù)產(chǎn)生項列表產(chǎn)生候選項集計算每個項集的支持度(/計數(shù))確定閾值，得到頻繁項集產(chǎn)生頻繁項集改進的：先驗算法AprioriFP-Growth算法5先驗算法AprioriApriori算法是一種基于Apriori原理的，最有影響的挖掘單維布爾關(guān)聯(lián)規(guī)則頻繁項集的算法該算法能較大程度上降低算法復(fù)雜度6先驗原理Apriori如果一個項集是頻繁的，則它的所有子集一定也是頻繁的；對于一個項集{CDE}，其子集為{CD}、{CE}或{DE}，也可以是{C}、{D}或{E}。7先驗原理Apriori相反，如果一個項集是非頻繁的，則它的所有超集也一定是非頻繁的。對于項集{AB}，其超集為{A

B

C}、{A

BD}、{ABE}，或{ABCD}、{ABCE}、{ABDE}、{ABCDE}。根據(jù)先驗原理，圖中若AB項集是非頻繁的，則在虛線包圍中的所有AB項集的超集都是非頻繁的，可以將這些項集剪除，稱其為剪枝。8支持度度量的單調(diào)性例1：產(chǎn)生頻繁項集利用先驗原理，產(chǎn)生頻繁項集。提取頻繁1-項集：共有6個項，即候選1-項集。其中，{可樂}和{雞蛋}的支持度(計數(shù))不滿足閾值要求，所以被剪除。得到頻繁1-項集：設(shè)定支持度閾值minSup=60%，也就是最小支持度計數(shù)為3。9例1：產(chǎn)生頻繁項集利用先驗原理，產(chǎn)生頻繁項集。提取頻繁2-項集：其中，{面包，啤酒}和{牛奶，啤酒}的支持度（計數(shù)）不滿足閾值要求，被剪枝得到頻繁2-項集：由頻繁1-項集中的4個項，可以組合出共6個候選2-項集：計算支持度計數(shù)10設(shè)定支持度閾值minSup=60%，也就是最小支持度計數(shù)為3。例1：產(chǎn)生頻繁項集利用先驗原理，產(chǎn)生頻繁項集。產(chǎn)生頻繁2-項集時，對支持度不滿足要求的

{面包

啤酒}和{牛奶

啤酒}項集進行了剪除處理，按照先驗原理，也可以將候選3-項集中的這些項集所在的項集剪除。提取頻繁3-項集：獲取頻繁2-項集中的4個項組合出共4個候選3-項集：計算支持度計數(shù)其中，{面包，牛奶，尿布}的支持度（計數(shù)）不滿足閾值要求，被剪枝得到頻繁3-項集：11設(shè)定支持度閾值minSup=60%，也就是最小支持度計數(shù)為3。例1：產(chǎn)生頻繁項集利用先驗原理，產(chǎn)生頻繁項集。枚舉法產(chǎn)生候選項集：先驗法產(chǎn)生候選項集：12設(shè)定支持度閾值minSup=60%，也就是最小支持度計數(shù)為3。

+++++++

先驗算法Apriori算法函數(shù)apriori_gen()來產(chǎn)生候選項集subset()來識別屬于事務(wù)t的候選項集σ(c)為候選項集的支持度計數(shù)13i：某數(shù)據(jù)項I：數(shù)據(jù)集中數(shù)據(jù)項集合

t：事務(wù)項T：事務(wù)項的集合N：事務(wù)集合中事務(wù)項的數(shù)量Ck：候選k-項集的集合c：候選項集Fk：頻繁k-項集的集合先驗算法Apriori

規(guī)則

事務(wù)

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

頻繁項集

候選項集

Apriori原理頻繁1-項集候選1-項集

候選2-項集

頻繁2-項集……候選k-項集

頻繁k-項集

14

練習(xí)1TIDItemsT1I1，I2，I5，I7T2I2，I4，I6T3I2，I3，I6T4I1，I2，I4T5I1，I3，I6T6I2，I3T7I1，I2，I3，I6，I7T8I1，I2，I3，I5，I7T9I1，I3T10I1，I2，I3，I5，I6，I7T11I1，I2，I3，I7求所有的頻繁項集（設(shè)支持度計數(shù)閾值為4，即支持度閾值為4/11）15TIDI1I2I3I4I5I6I7T1TT

T

TT2

T

T

T

T3

TT

T

T4TT

T

T5T

T

T

T6

TT

T7TTT

TTT8TTT

T

TT9T

T

T10TTT

TTTT11TTT

T練習(xí)116掃描數(shù)據(jù)，對每項計數(shù)選擇候選支持度計數(shù)≥支持度計數(shù)閾值，產(chǎn)生頻繁1-項集F1由F1組合產(chǎn)生候選2-項集C2。再次掃描數(shù)據(jù)，計算C2各項集支持度計數(shù)

根據(jù)支持度閾值確定頻繁2-項集F2由F2中各項組合產(chǎn)生候選3-項集。因其中{I1，I6}、{I6，I7}是非頻繁的，可對其超集進行基于非頻繁子集的剪枝。

再次掃描數(shù)據(jù)，計算各3-項集支持度計數(shù)由F3中的各項組合產(chǎn)生候選4-項集C4

再次掃描數(shù)據(jù)，計算各4-項集支持度計數(shù)根據(jù)支持度閾值確定頻繁3-項集F3產(chǎn)生頻繁4-項集F4

幾個問題改進組合產(chǎn)生候選項集的方法Fk-1

F1方法Fk-1

Fk-1方法17產(chǎn)生候選項集計算支持度產(chǎn)生候選項集Fk-1

F1方法利用已經(jīng)得到的頻繁1-項集和頻繁(k-1)-項集，組合產(chǎn)生候選k-項集，在經(jīng)過剪枝，得到頻繁k-項集。每個頻繁k-項集都由一個頻繁(k-1)-項集和一個頻繁1-項集組成的，方法是完備的。18產(chǎn)生候選項集Fk-1

F1方法19將產(chǎn)生|Fk-1|×|F1|個候選k-項集復(fù)雜度產(chǎn)生候選項集Fk-1

F1方法難以避免重復(fù)比蠻力方法改進明顯，但仍產(chǎn)生大量不必要的候選項集。例如，通過合并{啤酒，尿布}和{牛奶}而得到的候選是不必要的。因為它的子集{啤酒，牛奶}是非頻繁的。確保每個頻繁項集中的項以字典序存儲，每個頻繁(k-1)-項集X只用字典序比X中所有的項都大的頻繁項進行擴展（如：項集{面包，尿布}可以用項集{牛奶}擴展，因為“牛奶”(milk)在字典序下比“面包”(bread)和“尿布”(diaper)都大）。20產(chǎn)生候選項集Fk-1

Fk-1方法合并一對頻繁(k-1)-項集，僅當(dāng)它們的前k-2個項(經(jīng)排序)都相同例如：算法不會合并項集{啤酒，尿布}和{尿布，牛奶}，因為它們的第一個項不相同。{面包，尿布}{面包，牛奶}{面包，尿布，牛奶}21+產(chǎn)生候選項集Fk-1

Fk-1方法合并一對頻繁(k-1)-項集，僅當(dāng)它們的前k-2個項(經(jīng)排序)都相同頻繁2-項集項集{啤酒，尿布}{面包，尿布}{面包，牛奶}{尿布，牛奶}頻繁2-項集項集{啤酒，尿布}{面包，尿布}{面包，牛奶}{尿布，牛奶}候選產(chǎn)生項集{面包，尿布，牛奶}候選剪枝項集{面包，尿布，牛奶}由于每個候選都由一對頻繁(k-1)-項集合并而成，因此，需要附加的候選剪枝步驟來確保該候選的其余k-2個子集是頻繁的。22產(chǎn)生候選項集算法23join()：合并組合l1、l2前k-2個項has….()：檢驗候選項集中是否有非頻繁項練習(xí)2TIDItemsT1I1，I2，I5，I7T2I2，I4，I6T3I2，I3，I6T4I1，I2，I4T5I1，I3，I6T6I2，I3T7I1，I2，I3，I6，I7T8I1，I2，I3，I5，I7T9I1，I3T10I1，I2，I3，I5，I6，I7T11I1，I2，I3，I7求所有的頻繁項集（設(shè)支持度計數(shù)閾值為4，即支持度閾值為4/11）24使用Fk-1

Fk-1方法TIDI1I2I3I4I5I6I7T1TT

T

TT2

T

T

T

T3

TT

T

T4TT

T

T5T

T

T

T6

TT

T7TTT

TTT8TTT

T

TT9T

T

T10TTT

TTTT11TTT

T練習(xí)225掃描數(shù)據(jù)，對每項計數(shù)選擇候選支持度計數(shù)≥支持度計數(shù)閾值，產(chǎn)生頻繁1-項集F1由F1組合產(chǎn)生候選2-項集C2。再次掃描數(shù)據(jù)，計算C2各項集支持度計數(shù)

根據(jù)支持度閾值確定頻繁2-項集F2由F2中各項按Fk-1×Fk-1方法