數(shù)據(jù)挖掘-概念與技術(shù)：Lecture 4 關(guān)聯(lián)規(guī)則挖掘

1、2022/8/11Data Mining1Lecture 4： 挖掘關(guān)聯(lián)規(guī)則什么是關(guān)聯(lián)規(guī)則：一個示例若干基本概念挖掘單維布爾關(guān)聯(lián)規(guī)則的Apriori算法改進基于頻繁模式樹的算法2022/8/11Data Mining2示例購物籃序號購買的商品內(nèi)容購買1牛奶、面包、啤酒、花生購買2牛奶、面包、黃油購買3牛奶、面包、雞蛋購買4糖、雞蛋、啤酒、花生購買5黃油、雞蛋、啤酒、花生購買6糖、雞蛋、面包、花生買牛奶就買面包？買啤酒就買花生？2022/8/11Data Mining3示例關(guān)鍵詞序號論文的關(guān)鍵詞論文1數(shù)據(jù)挖掘、機器學習、聚類分析論文2機器學習、貝葉斯分類、信息提取、數(shù)據(jù)挖掘論文3自動推理、機器學

2、習、算法復(fù)雜性分析論文4數(shù)據(jù)挖掘、空間推理、空間聚類分析、機器學習數(shù)據(jù)挖掘機器學習2022/8/11Data Mining4Lecture 4： 挖掘關(guān)聯(lián)規(guī)則什么是關(guān)聯(lián)規(guī)則：一個示例若干基本概念挖掘單維布爾關(guān)聯(lián)規(guī)則的Apriori算法改進基于頻繁模式樹的算法2022/8/11Data Mining5基本概念 I關(guān)聯(lián)規(guī)則:頻繁模式（Frequent pattern）： 在數(shù)據(jù)庫中頻繁出現(xiàn)的模式（項集 、 序列 等）。在事務(wù)數(shù)據(jù)庫、關(guān)系數(shù)據(jù)庫及其它信息庫中發(fā)現(xiàn)對象集合之間的頻繁出現(xiàn)的模式，關(guān)聯(lián)，相關(guān)性或因果關(guān)系。規(guī)則形式：x1 x2 xn y1 y2 ym?？梢宰x作：如果x1 x2 xn ，那么y

3、1 y2 ym 。2022/8/11Data Mining6基本概念 IIk項集 ：含有k個元素的集合，X=x1, , xk。對于規(guī)則XY，定義支持度與置信度如下：支持度（Support），事務(wù)包含XY的概率，即support P(XY)置信度（Confidence），事務(wù)同時包含X與Y的條件概率，即confidence P(Y|X).2022/8/11Data Mining7基本概念 III最小支持度與最小置信度：由用戶提供，即挖掘出的關(guān)聯(lián)規(guī)則的支持度與置信度必須分別大于最小支持度與最小置信度。2022/8/11Data Mining8基本概念 IV支持度計數(shù)：模式或項集在DB中出現(xiàn)的頻率（

4、次數(shù)）。頻繁模式（頻繁項集）：支持度大于或等于最小支持度（用戶自定義）的模式（項集）。關(guān)聯(lián)規(guī)則挖掘的任務(wù)：發(fā)現(xiàn)所有滿足最小支持度與最小可信度、形如XY的規(guī)則。2022/8/11Data Mining9支持度的計算2022/8/11Data Mining10置信度的計算2022/8/11Data Mining11支持度與置信度的計算示例對于規(guī)則 A C:support = support(AC) = 50%confidence = support(AC)/support(A) = 66.6%最小支持度： 50%最小置信度： 50%Transaction-idItems bought10A, B,

5、 C20A, C30A, D40B, E, F頻繁模式SupportA75%B50%C50%A, C50%2022/8/11Data Mining12Apriori算法什么是關(guān)聯(lián)規(guī)則：一個示例若干基本概念挖掘單維布爾關(guān)聯(lián)規(guī)則的Apriori算法改進基于頻繁模式樹的算法2022/8/11Data Mining13單維布爾關(guān)聯(lián)規(guī)則對于規(guī)則XY，其中 X=x1, , xk， Y=y1, , ym ，即：如果買X，那么買Y，或為If Buys(p, X) Buys(p, Y) 。這里的買或者Buys是一個二元謂詞。在我們這里只牽涉到一個謂詞，因此稱為單維關(guān)聯(lián)規(guī)則；同時因為只涉及到買還是不買，因此稱為布

6、爾關(guān)聯(lián)規(guī)則。2022/8/11Data Mining14其它形式的關(guān)聯(lián)規(guī)則多維關(guān)聯(lián)規(guī)則：規(guī)則中有兩個以上的謂詞。量化關(guān)聯(lián)規(guī)則（Quantitative association rule）：描述量化的項或?qū)傩灾g的關(guān)聯(lián)。例如：Age(X, “30到40”)Income(X, “4萬6萬”）Buys(X, “computer”)2022/8/11Data Mining15挖掘單維布爾關(guān)聯(lián)規(guī)則：窮舉法設(shè)事務(wù)表中有n件不同的商品x1, x2, , xn，顯然有窮舉法如下：對于從2-項集到n-項集，枚舉所有的集合檢查其子項集之間是否存在關(guān)聯(lián)。如對于2-項集，檢查是否存在關(guān)聯(lián)規(guī)則xi xj（i 1, 2

7、, n, j 1, 2 , n, i j）2022/8/11Data Mining16挖掘單維布爾關(guān)聯(lián)規(guī)則：窮舉法那么這種方法是否實用呢？若對這么多子集進行測試，算法的時間復(fù)雜性如何？顯然，一個n個元素集合有2n子集（對于我們這個問題，有2n - n - 1個子集）2022/8/11Data Mining172022/8/11Data Mining18表2 計算機速度提高10倍后，不同算法復(fù)雜性求解規(guī)模的擴大情況 算法A1A2A3A4A5A6時間復(fù)雜性nnlognn2n32nn!n2和n1的關(guān)系 10n18.38n13.16n12.15n1n1+3.3n12022/8/11Data Minin

8、g19Apriori: 一個候選集產(chǎn)生與測試算法一個頻繁集的任意子集也必須是頻繁集如果 A, B, C是頻繁集, 則A, B也是頻繁集。每一個事務(wù)若包含 A, B, C ，則它也包含 A, BApriori裁剪原理： 對于任意項集，如果它不是頻繁集，則它的任何超集不用產(chǎn)生/測試!2022/8/11Data Mining20Apriori算法算法：Apriori 使用根據(jù)候選生成的逐層迭代找出頻繁項集輸入：事務(wù)數(shù)據(jù)庫D；最小支持度閾值min_sup.輸出：D中的所有頻繁項集方法：2022/8/11Data Mining21While(Lk-1 )（ Lk-1 表示k-1頻繁項集 ）從Lk-1利用

9、連接操作產(chǎn)生候選項集Ck;對于Ck中的每一個元素c，掃描數(shù)據(jù)庫檢查c是否是k-頻繁項集;Lk=c | c是k-頻繁項集k = k 1；輸出 kLk2022/8/11Data Mining22連接操作對于兩個k-項集I1, I2, , Ik-1, Ik， I1, I2, , Ik-1, Ik，能夠連接產(chǎn)生一個k+1項集，當且僅當Ii=Ii, 其中i 1, 2, , k-1且Ik Ik，連接結(jié)果為( k+1項集)：I1, I2, , Ik-1, Ik, Ik如A, C, D與A, C, E連接產(chǎn)生A, C, D, E；而A, C, D與A, B, D不能連接。2022/8/11Data Minin

10、g23Apriori算法示例事務(wù)數(shù)據(jù)庫TDB1st scanC1L1L2C2C22nd scanC3L33rd scanTidItems10A, C, D20B, C, E30A, B, C, E40B, EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA, BA, CA, EB, CB, EC, EItemsetsupA, B1A, C2A, E1B, C2B, E3C, E2ItemsetsupA, C2B, C2B, E3C, E2ItemsetB, C, EItemsetsupB, C, E22022/8/11Data Mining24從頻繁

11、項集中產(chǎn)生關(guān)聯(lián)規(guī)則對于頻繁項集I=I1, I2, , Ik-1, Ik如何產(chǎn)生關(guān)聯(lián)規(guī)則？是否滿足支持度？是否滿足置信度對于每個頻繁項集I，產(chǎn)生它的所有非空子集m；對于每個m，如果 滿足下式 ，則輸出規(guī)則m(I m)。關(guān)聯(lián)規(guī)則的提升度GameNonGameSumrowVideo400035007500NonVideo20005002500Sumcol60004000100002022/8/11Data Mining25Corr(A,B)=P(AB)/(P(A)P(B)=P(B|A)P(A)/(P(A)P(B)= P(B|A)/P(B) = P(A|B)/P(A)上式也稱為規(guī)則AB(或BA)的提升

12、度。若大于1，二者正相關(guān)；等于1，二者獨立；小于1，則負相關(guān)。Corr(Video, Game)=0.4/(0.75*0.6) = 0.89 1.Video Game 4000/10000, 4000/7500 40/75 60%Game Video 4000/10000, 4000/6000 4/6 75%2022/8/11Data Mining26Apriori算法存在的問題多次掃描數(shù)據(jù)庫；產(chǎn)生大量的候選集合；如何改進？2022/8/11Data Mining27Lecture 4： 挖掘關(guān)聯(lián)規(guī)則什么是關(guān)聯(lián)規(guī)則：一個示例若干基本概念挖掘單維布爾關(guān)聯(lián)規(guī)則的Apriori算法改進基于頻繁模式樹

13、的算法2022/8/11Data Mining28TIDItems bought (ordered) frequent items100f, a, c, d, g, i, m, pf, c, a, m, p200a, b, c, f, l, m, of, c, a, b, m300 b, f, h, j, o, wf, b400 b, c, k, s, pc, b, p500 a, f, c, e, l, p, m, nf, c, a, m, pmin_support = 3f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem frequency

14、head f4c4a3b3m3p32022/8/11Data Mining29包含p的頻繁模式f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem frequency head f4c4a3b3m3p3pc:32022/8/11Data Mining30包含m的頻繁模式f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem frequency head f4c4a3b3m3p3am: 3, cm:3, fm:3cam:3, fam:3, fcm:3fcam:32022/8/11Data Mining31包

15、含b的頻繁模式f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem frequency head f4c4a3b3m3p3包含b的頻繁模式為空2022/8/11Data Mining32包含a的頻繁模式f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem frequency head f4c4a3b3m3p3ca:3, fa:3fca:32022/8/11Data Mining33包含c的頻繁模式f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem freq

16、uency head f4c4a3b3m3p3fc:3多維關(guān)聯(lián)規(guī)則挖掘基本思路：與單維布爾關(guān)聯(lián)規(guī)則挖掘類似數(shù)據(jù)預(yù)處理：如對數(shù)值數(shù)據(jù)離散化等構(gòu)建謂詞數(shù)據(jù)集利用Apriori算法挖掘頻繁謂詞模式得到多維關(guān)聯(lián)規(guī)則2022/8/11Data Mining關(guān)系數(shù)據(jù)2022/8/11Data MiningkeyAgeIncomeProduct1180.4小米2314.5Computer3355Computer4262.3iPhone2022/8/11Data MiningIDItems1A(1820), I(00.5), B(小米)2A(3040), I(46), B(Computer)3A(3040),

17、 I(46), B(Computer)4A(2129), I(13), B(iPhone)謂詞數(shù)據(jù)（經(jīng)過離散）挖掘頻繁謂詞模式2022/8/11Data Mining謂詞計數(shù)A(1820)1A(2129)1A(3040)2B(Computer)2B(iPhone)1B(小米)1I(00.5)1I(13)1I(46)2謂詞計數(shù)A(3040)2B(Computer)2I(46)2C1L1挖掘頻繁謂詞模式2022/8/11Data Mining謂詞計數(shù)A(3040)2B(Computer)2I(46)2L1謂詞計數(shù)A(3040), B(Computer)2A(3040), I(46)2B(Compu

18、ter), I(46)2C2謂詞計數(shù)A(3040), B(Computer)2A(3040), I(46)2B(Computer), I(46)2L2謂詞計數(shù)A(3040), B(Computer), I(46)2C3挖掘頻繁謂詞模式2022/8/11Data Mining謂詞計數(shù)A(3040), B(Computer), I(46)2L3討論：科學研究的第四范式2007年，已故的圖靈獎得主吉姆格雷（Jim Gray）在他最后一次演講中描繪了數(shù)據(jù)密集型科研“第四范式”的愿景。將大數(shù)據(jù)科研從第三范式（計算機模擬）中分離出來單獨作為一種科研范式，是因為其研究方式不同于基于數(shù)學模型的傳統(tǒng)研究方式。2

19、022/8/11Data Mining40Jim Gray“I wanted to point out that almost everything about science is changing because of the impact of information technology. Experimental, theoretical, and computational science are all being affected by the data deluge, and a fourth, “data-intensive” science paradigm is eme

20、rging.”2022/8/11Data Mining41一些驚人言論谷歌公司的研究部主任彼得諾維格（Peter Norvig）的一句名言可以概括兩者的區(qū)別：“所有的模型都是錯誤的，進一步說，沒有模型你也可以成功”（All models are wrong, and increasingly you can succeed without them）。PB級數(shù)據(jù)使我們可以做到?jīng)]有模型和假設(shè)就可以分析數(shù)據(jù)。將數(shù)據(jù)丟進巨大的計算機機群中，只要有相互關(guān)系的數(shù)據(jù)，統(tǒng)計分析算法就可以發(fā)現(xiàn)過去的科學方法發(fā)現(xiàn)不了的新模式、新知識甚至新規(guī)律。實際上，谷歌的廣告優(yōu)化配置、戰(zhàn)勝人類的IBM沃森問答系統(tǒng)都是這么實現(xiàn)的，這就是“第四范式”的魅力！2022/8/11Data Mining42一些極端言論美國連線雜志主編克里斯安德森2008年曾發(fā)出“理論已終結(jié)”的驚人斷言