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

1、2022-3-251關(guān)聯(lián)規(guī)則挖掘算法FP-growth2022-3-252關(guān)聯(lián)規(guī)則的基本概念 數(shù)據(jù)挖掘是指從大量的、不完全的、有噪聲的、模糊的、隨機的數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的但又是潛在有用的信息和知識的過程 數(shù)據(jù)關(guān)聯(lián)是數(shù)據(jù)庫中存在的一類重要的可被發(fā)現(xiàn)的知識。若兩個或多個變量的取值之間存在某種規(guī)律性，就稱為關(guān)聯(lián)關(guān)聯(lián)分析的目的是找出數(shù)據(jù)庫中隱藏的關(guān)聯(lián)網(wǎng)。2022-3-253關(guān)聯(lián)規(guī)則的基本概念 支持度：P(AUB)，即A和B這兩個項集在事務(wù)集D中同時出現(xiàn)的概率 置信度：P(B I A)，即在出現(xiàn)項集A的事務(wù)集D中，項集B也同時出現(xiàn)的概率2022-3-254關(guān)聯(lián)規(guī)則的基本概念 bre

2、ad=milk支持度-7,置信度-65 P(breadUmilk)=7 P(milkIbread)=65 如果一條關(guān)聯(lián)規(guī)則同時滿足最小支持度閾值和最小置信度閾值，那么就認(rèn)為它是有趣的，并稱為強關(guān)聯(lián)規(guī)則。 給定一個事務(wù)集D，挖掘關(guān)聯(lián)規(guī)則問題就是產(chǎn)生支持度和可信度分別大于用戶給定的最小支持度和最小可信度的關(guān)聯(lián)規(guī)則，也就是產(chǎn)生強規(guī)則的問題。2022-3-255FP-tree構(gòu)造算法 掃描事務(wù)數(shù)據(jù)庫一次。收集頻繁項的集合F和它們的支持度。對F按支持度降序排序，結(jié)果為頻繁項表L。 創(chuàng)建FP-tree的根結(jié)點(null)。對于D中每個事務(wù)：選擇事務(wù)中的頻繁項，并按L中的次序排序。設(shè)排序后的頻繁項表為p|P

3、，其中p是第一個元素，而P是剩余元素的表調(diào)用insert_tree(p| P，T)。 如果T有子女N使得N.item-name=p.item-name，則N的計數(shù)增加1；否則創(chuàng)建一個新節(jié)點N，將其計數(shù)設(shè)置為1，連接到他的父節(jié)點T，并通過節(jié)點鏈結(jié)構(gòu)將其連接到具有相同item-name的節(jié)點如果P非空，遞歸的調(diào)用insert_tree(P，N)2022-3-256FP-growth算法1.Procedure FP-growth(Tree，a)2.if Tree包含單個路徑 p then3. for路徑P中每個節(jié)點組合(記做)4. 產(chǎn)生模式a，其支持度support=中節(jié)點的最小 支持度;5.els

4、e for each ai在tree的頭部6.產(chǎn)生一個模式=aia，其支持度support=ai.support;7.構(gòu)造的條件模式基，構(gòu)建的條件FP-tree Tree;8.if Tree then9.調(diào)用FP-growth(Tree，);10. 2022-3-257事務(wù)數(shù)據(jù)庫TidItems1I1,I2,I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I32022-3-258第一步、構(gòu)造FP-tree 掃描事務(wù)數(shù)據(jù)庫得到頻繁1-項目集F 定義minsup=20%，即最小支持度為2 重新排列FI1I2I3I4I56762

5、2I2I1I3I4I5766222022-3-259重新調(diào)整事務(wù)數(shù)據(jù)庫TidItems1I2, I1,I52I2,I43I2,I34I2, I1,I45I1,I36I2,I37I1,I38I2, I1,I3,I59I2, I1,I32022-3-2510創(chuàng)建根結(jié)點和頻繁項目表Item-nameNode-headI2NullI1NullI3NullI4NullI5NullNull2022-3-2511加入第一個事務(wù)(I2,I1,I5)Item-nameNode-headI2I1I3NullI4NullI5NullI2:1I1:1I5:12022-3-2512加入第二個事務(wù)(I2,I4)Item-

6、nameNode-headI2I1I3NullI4I5NullI2:2I1:1I5:1I4:12022-3-2513加入第三個事務(wù)(I2,I3)Item-nameNode-headI2I1I3I4I5NullI2:3I1:1I5:1I4:1I3:12022-3-2514加入第四個事務(wù)(I2,I1,I4)Item-nameNode-headI2I1I3I4I5NullI2:4I1:2I5:1I4:1I3:1I4:12022-3-2515加入第五個事務(wù)(I1,I3)Item-nameNode-headI2I1I3I4I5NullI2:4I1:2I5:1I4:1I3:1I4:1I1:1I3:1202

7、2-3-2516加入第六個事務(wù)(I2,I3)Item-nameNode-headI2I1I3I4I5NullI2:5I1:2I5:1I4:1I3:2I4:1I1:1I3:12022-3-2517加入第七個事務(wù)(I1,I3)Item-nameNode-headI2I1I3I4I5NullI2:5I1:2I5:1I4:1I3:2I4:1I1:2I3:22022-3-2518加入第八個事務(wù)(I2,I1,I3,I5)Item-nameNode-headI2I1I3I4I5NullI2:6I1:3I5:1I4:1I3:2I4:1I1:2I3:2I5:1I3:12022-3-2519加入第九個事務(wù)(I2,

8、I1,I3)Item-nameNode-headI2I1I3I4I5NullI2:7I1:4I5:1I4:1I3:2I4:1I1:2I3:2I5:1I3:22022-3-2520第二步、FP-growth 首先考慮I5，得到條件模式基 、 構(gòu)造條件FP-tree 得到I5頻繁項集：I2,I5:2,I1,I5:2,I2,I1,I5:2Item-nameNode-headI2I1NullI2:2I1:2I3:12022-3-2521第二步、FP-growth 接著考慮I4，得到條件模式基 、 構(gòu)造條件FP-tree 得到I4頻繁項集：I2,I4:2Item-nameNode-headI2NullI2:2I1:12022-3-2522第二步、FP-growth 然后考慮I3，得到條件模式基 、 構(gòu)造條件FP-tree 由于此樹不是單一路徑，因此需要遞歸挖掘I3Item-nameNode-headI2I1NullI2:4I1:2I1:22022-3-2523第二步、FP-growth 遞歸考慮I3，此時得到I1條件模式基 ,即I1I3的條件模式基為 構(gòu)造條件FP-tree 得到I3的頻繁項目集I2,I3:4,I1,I3:4,I2,I1,I3:2Item-nam