第5講-關(guān)聯(lián)規(guī)則挖掘

第五章關(guān)聯(lián)規(guī)則挖掘什么是關(guān)聯(lián)規(guī)則挖掘？關(guān)聯(lián)規(guī)則挖掘：從事務(wù)數(shù)據(jù)庫，關(guān)系數(shù)據(jù)庫和其他信息存儲中的大量數(shù)據(jù)的項集之間發(fā)現(xiàn)有趣的、頻繁出現(xiàn)的模式、關(guān)聯(lián)和相關(guān)性。應(yīng)用：購物籃分析、分類設(shè)計、捆綁銷售和虧本銷售分析“尿布與啤酒”——典型關(guān)聯(lián)分析案例采用關(guān)聯(lián)模型比較典型的案例是“尿布與啤酒”的故事。在美國，一些年輕的父親下班后經(jīng)常要到超市去買嬰兒尿布，超市也因此發(fā)現(xiàn)了一個規(guī)律，在購買嬰兒尿布的年輕父親們中，有30%～40%的人同時要買一些啤酒。超市隨后調(diào)整了貨架的擺放，把尿布和啤酒放在一起，明顯增加了銷售額。同樣的，我們還可以根據(jù)關(guān)聯(lián)規(guī)則在商品銷售方面做各種促銷活動。購物籃分析如果問題的全域是商店中所有商品的集合，則對每種商品都可以用一個布爾量來表示該商品是否被顧客購買，則每個購物籃都可以用一個布爾向量表示（0001001100）；而通過分析布爾向量則可以得到商品被頻繁關(guān)聯(lián)或被同時購買的模式，這些模式就可以用關(guān)聯(lián)規(guī)則表示關(guān)聯(lián)規(guī)則的兩個興趣度度量支持度置信度關(guān)聯(lián)規(guī)則：基本概念給定：項的集合：I={i1,i2,...,in}任務(wù)相關(guān)數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合，每個事務(wù)T則是項的集合，使得每個事務(wù)由事務(wù)標(biāo)識符TID標(biāo)識；A,B為兩個項集，事務(wù)T包含A當(dāng)且僅當(dāng)則關(guān)聯(lián)規(guī)則是如下蘊(yùn)涵式：其中并且，規(guī)則在事務(wù)集D中成立，并且具有支持度s和置信度c規(guī)則度量：支持度和置信度CustomerbuysdiaperCustomerbuysbothCustomerbuysbeer對所有滿足最小支持度和置信度的關(guān)聯(lián)規(guī)則支持度s是指事務(wù)集D中包含的百分比置信度c是指D中包含A的事務(wù)同時也包含B的百分比假設(shè)最小支持度為50%，最小置信度為50%，則有如下關(guān)聯(lián)規(guī)則AC(50%,66.6%)CA(50%,100%)大型數(shù)據(jù)庫關(guān)聯(lián)規(guī)則挖掘過程基本概念k－項集：包含k個項的集合{牛奶，面包，黃油}是個3－項集項集的頻率是指包含項集的事務(wù)數(shù)如果項集的頻率大于（最小支持度×D中的事務(wù)總數(shù)），則稱該項集為頻繁項集大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則挖掘包含兩個過程：找出所有頻繁項集大部分的計算都集中在這一步由頻繁項集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則即滿足最小支持度和最小置信度的規(guī)則關(guān)聯(lián)規(guī)則挖掘——一個線路圖關(guān)聯(lián)規(guī)則有多種分類：根據(jù)規(guī)則中所處理的值類型布爾關(guān)聯(lián)規(guī)則量化關(guān)聯(lián)規(guī)則根據(jù)規(guī)則中設(shè)計的數(shù)據(jù)維單維關(guān)聯(lián)規(guī)則多維關(guān)聯(lián)規(guī)則根據(jù)規(guī)則集所涉及的抽象層單層關(guān)聯(lián)規(guī)則多層關(guān)聯(lián)規(guī)則根據(jù)關(guān)聯(lián)挖掘的各種擴(kuò)充挖掘最大的頻繁模式（該模式的任何真超模式都是非頻繁的）挖掘頻繁閉項集（一個項集c是頻繁閉項集，如果不存在其真超集c`，使得每個包含c的事務(wù)也包含c`）由事務(wù)數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則最簡單的關(guān)聯(lián)規(guī)則挖掘，即單維、單層、布爾關(guān)聯(lián)規(guī)則的挖掘。最小支持度50%最小置信度50%對規(guī)則A

C，其支持度=50%置信度Apriori算法Apriori算法利用頻繁項集性質(zhì)的先驗知識（priorknowledge），通過逐層搜索的迭代方法，即將k-1項集用于探察k項集，來窮盡數(shù)據(jù)集中的所有頻繁項集。先找到頻繁1-項集集合L1,然后用L1找到頻繁2-項集集合L2，接著用L2找L3，直到找不到頻繁k-項集，找每個Lk需要一次數(shù)據(jù)庫掃描。Apriori性質(zhì)：頻繁項集的所有非空子集也必須是頻繁的。（

模式不可能比A更頻繁的出現(xiàn)）Apriori算法是反單調(diào)的，即一個集合如果不能通過測試，則該集合的所有超集也不能通過相同的測試。Apriori算法步驟Apriori算法由連接和剪枝兩個步驟組成。連接：為了找Lk，通過Lk-1與自己連接產(chǎn)生候選k-項集的集合，該候選k項集記為Ck。Lk-1中的兩個元素L1和L2可以執(zhí)行連接操作的條件是Ck是Lk的超集，即它的成員可能不是頻繁的，但是所有頻繁的k-項集都在Ck中（為什么？）。因此可以通過掃描數(shù)據(jù)庫，通過計算每個k-項集的支持度來得到Lk

。為了減少計算量，可以使用Apriori性質(zhì)，即如果一個k-項集的(k-1)-子集不在Lk-1中，則該候選不可能是頻繁的，可以直接從Ck刪除。Apriori算法——示例DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}2使用Apiori性質(zhì)由L2產(chǎn)生C31．連接：C3=L2L2={{A,C},{B,C},{B,E}{C,E}}{{A,C},{B,C},{B,E}{C,E}}={{A,B,C},{A,C,E},{B,C,E}}2．使用Apriori性質(zhì)剪枝：頻繁項集的所有子集必須是頻繁的，對候選項C3，我們可以刪除其子集為非頻繁的選項：{A,B,C}的2項子集是{A,B},{A,C},{B,C}，其中{A,B}不是L2的元素，所以刪除這個選項；{A,C,E}的2項子集是{A,C},{A,E},{C,E}，其中{A,E}

不是L2的元素，所以刪除這個選項；{B,C,E}的2項子集是{B,C},{B,E},{C,E}，它的所有2－項子集都是L2的元素，因此保留這個選項。3．這樣，剪枝后得到C3={{B,C,E}}由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則同時滿足最小支持度和最小置信度的才是強(qiáng)關(guān)聯(lián)規(guī)則，從頻繁項集產(chǎn)生的規(guī)則都滿足支持度要求，而其置信度則可由以下公式計算：每個關(guān)聯(lián)規(guī)則可由如下過程產(chǎn)生：對于每個頻繁項集l，產(chǎn)生l的所有非空子集；對于l的每個非空子集s，如果 則輸出規(guī)則“ ”(P155)提高Apriori算法的有效性(1)Apriori算法主要的挑戰(zhàn)要對數(shù)據(jù)進(jìn)行多次掃描；會產(chǎn)生大量的候選項集；對候選項集的支持度計算非常繁瑣；解決思路減少對數(shù)據(jù)的掃描次數(shù)；縮小產(chǎn)生的候選項集；改進(jìn)對候選項集的支持度計算方法方法1：基于hash表的項集計數(shù)將每個項集通過相應(yīng)的hash函數(shù)映射到hash表中的不同的桶中，這樣可以通過將桶中的項集技術(shù)跟最小支持計數(shù)相比較先淘汰一部分項集。提高Apriori算法的有效性(2)方法2：事務(wù)壓縮（壓縮進(jìn)一步迭代的事務(wù)數(shù)）不包含任何k-項集的事務(wù)不可能包含任何(k+1)-項集，這種事務(wù)在下一步的計算中可以加上標(biāo)記或刪除。方法3：劃分挖掘頻繁項集只需要兩次數(shù)據(jù)掃描D中的任何頻繁項集必須作為局部頻繁項集至少出現(xiàn)在一個部分中。第一次掃描：將數(shù)據(jù)劃分為多個部分并找到局部頻繁項集第二次掃描：評估每個候選項集的實際支持度，以確定全局頻繁項集提高Apriori算法的有效性(3)方法4：選樣（在給定數(shù)據(jù)的一個子集挖掘）基本思想：選擇原始數(shù)據(jù)的一個樣本，在這個樣本上用Apriori算法挖掘頻繁模式通過犧牲精確度來減少算法開銷，為了提高效率，樣本大小應(yīng)該以可以放在內(nèi)存中為宜，可以適當(dāng)降低最小支持度來減少遺漏的頻繁模式可以通過一次全局掃描來驗證從樣本中發(fā)現(xiàn)的模式可以通過第二此全局掃描來找到遺漏的模式方法5：動態(tài)項集計數(shù)在掃描的不同點(diǎn)添加候選項集，這樣，如果一個候選項集已經(jīng)滿足最少支持度，則在可以直接將它添加到頻繁項集，而不必在這次掃描的以后對比中繼續(xù)計算。多層關(guān)聯(lián)規(guī)則數(shù)據(jù)項中經(jīng)常會形成概念分層底層的數(shù)據(jù)項，其支持度往往也較低在適當(dāng)?shù)牡燃壨诰虺鰜淼臄?shù)據(jù)項間的關(guān)聯(lián)規(guī)則可能是非常有用的通常，事務(wù)數(shù)據(jù)庫中的數(shù)據(jù)也是根據(jù)維和概念分層來進(jìn)行儲存的在多個抽象層挖掘關(guān)聯(lián)規(guī)則，并在不同的抽象層進(jìn)行轉(zhuǎn)化，是數(shù)據(jù)挖掘系統(tǒng)應(yīng)該提供的能力ComputeraccessorylaptopfinancialmousecolorprintercomputerdesktopIBMedu.Microsoftb/wHPSonywristpadLogitechTIDItemsT1{IBMD/C,Sonyb/w}T2{M.Sw.,Ms.fin.Sw.}T3{Logi.mouse,Ergowaywristpad}T4{IBMD/C,Ms.Fin.Sw.}T5{IBMD/C}ErgowayAllsoftware挖掘多層關(guān)聯(lián)規(guī)則的方法通常，多層關(guān)聯(lián)規(guī)則的挖掘還是使用置信度－支持度框架，可以采用自頂向下策略由概念層1開始向下，到較低的更特定的概念層，對每個概念層的頻繁項計算累加計數(shù)可以使用Apriori等多種方法請注意：概念分層中，一個節(jié)點(diǎn)的支持度肯定不小于該節(jié)點(diǎn)的任何子節(jié)點(diǎn)的支持度例如：先找高層的關(guān)聯(lián)規(guī)則：computer->printer[20%,60%]再找較低層的關(guān)聯(lián)規(guī)則：laptop->colorprinter[10%,50%]交叉層關(guān)聯(lián)規(guī)則跨越概念層邊界的規(guī)則：Computer=>b/wprinter使用較低層的最小支持度值多層關(guān)聯(lián)——一致支持度VS.遞減支持度一致支持度：對所有層都使用一致的最小支持度優(yōu)點(diǎn)：搜索時容易采用優(yōu)化策略，即一個項如果不滿足最小支持度，它的所有子項都可以不用搜索缺點(diǎn)：最小支持度值設(shè)置困難太高：將丟掉出現(xiàn)在較低抽象層中有意義的關(guān)聯(lián)規(guī)則太低：會在較高層產(chǎn)生太多的無興趣的規(guī)則遞減支持度：在較低層使用遞減的最小支持度抽象層越低，對應(yīng)的最小支持度越小min_sup=5%min_sup=5%min_sup=3%多層關(guān)聯(lián)——搜索策略具有遞減支持度的多層關(guān)聯(lián)規(guī)則的搜索策略逐層獨(dú)立：完全的寬度搜索，沒有頻繁項集的背景知識用于剪枝層交叉單項過濾：一個第i層的項被考察，當(dāng)且僅當(dāng)它在第（i-1）層的父節(jié)點(diǎn)是頻繁的層交叉k項集過濾：一個第i層的k項集被考察，當(dāng)且僅當(dāng)它在第(i-1)層的對應(yīng)父節(jié)點(diǎn)k-項集是頻繁的搜索策略比較逐層獨(dú)立策略條件松，可能導(dǎo)致底層考察大量非頻繁項層交叉k項集過濾策略限制太強(qiáng)，僅允許考察頻繁k-項集的子女層交叉單項過濾策略是上述兩者的折中，但仍可能丟失低層頻繁項受控的層交叉單項過濾策略設(shè)置一個層傳遞臨界值，用于向較低層傳遞相對頻繁的項。即如果滿足層傳遞臨界值，則允許考察不滿足最小支持度臨界值的項的子女用戶對進(jìn)一步控制多概念層上的挖掘過程有了更多的靈活性，同時減少無意義關(guān)聯(lián)的考察和產(chǎn)生min_sup=12%level_passage_support=8%min_sup=3%檢查冗余的多層關(guān)聯(lián)規(guī)則挖掘多層關(guān)聯(lián)規(guī)則時，由于項間的“祖先”關(guān)系，有些發(fā)現(xiàn)的規(guī)則將是冗余的例如：desktopcomputer=>b/wprinter[sup=8%,con=70%] (1)IBMdesktopcomputer=>b/wprinter[sup=2%,con=72%](2)上例中，我們說第一個規(guī)則是第二個規(guī)則的“祖先”如果規(guī)則(2)中的項用它在概念分層中的“祖先”代替，能得到(1)，而且(1)的支持度和置信度都接近“期望”值，則(1)是冗余的。多維關(guān)聯(lián)規(guī)則——概念單維關(guān)聯(lián)規(guī)則：buys(X,“milk”)＝buys(X,“bread”)多維關(guān)聯(lián)規(guī)則：涉及兩個或多個維或謂詞的關(guān)聯(lián)規(guī)則維間關(guān)聯(lián)規(guī)則：不包含重復(fù)的謂詞age(X,”19-25”)∧occupation(X,“student”)=>buys(X,“coke”)混合維關(guān)聯(lián)規(guī)則：包含某些謂詞的多次出現(xiàn)age(X,”19-25”)∧buys(X,“popcorn”)=>buys(X,“coke”)分類屬性具有有限個不同值，值之間無序量化屬性數(shù)值類型的值，并且值之間有一個隱含的序挖掘多維關(guān)聯(lián)規(guī)則的技術(shù)在多維關(guān)聯(lián)規(guī)則挖掘中，我們搜索的不是頻繁項集，而是頻繁謂詞集。k-謂詞集是包含k個合取謂詞的集合。例如：{age,occupation,buys}是一個3-謂詞集挖掘多維關(guān)聯(lián)規(guī)則的技術(shù)可以根據(jù)量化屬性的處理分為三種基本方法：1.量化屬性的靜態(tài)離散化使用預(yù)定義的概念分層對量化屬性進(jìn)行靜態(tài)地離散化2.量化關(guān)聯(lián)規(guī)則根據(jù)數(shù)據(jù)的分布，將量化屬性離散化到“箱”3.基于距離的關(guān)聯(lián)規(guī)則考慮數(shù)據(jù)點(diǎn)之間的距離，動態(tài)地離散化量化屬性多維關(guān)聯(lián)規(guī)則挖掘——使用量化屬性的靜態(tài)離散化量化屬性使用預(yù)定義的概念分層，在挖掘前進(jìn)行離散化數(shù)值屬性的值用區(qū)間代替如果任務(wù)相關(guān)數(shù)據(jù)存在關(guān)系數(shù)據(jù)庫中，則找出所有頻繁的k-謂詞集將需要k或k+1次表掃描數(shù)據(jù)立方體技術(shù)非常適合挖掘多維關(guān)聯(lián)規(guī)則n-維方體的單元用于存放對應(yīng)n-謂詞集的計數(shù)或支持度，0-D方體用于存放任務(wù)相關(guān)數(shù)據(jù)的事務(wù)總數(shù)如果包含感興趣的維的數(shù)據(jù)立方體已經(jīng)存在并物化，挖掘?qū)芸?，同時可以利用Apriori性質(zhì)：頻繁謂詞集的每個子集也必須是頻繁的(income)(age)()(buys)(age,income)(age,buys)(income,buys)(age,income,buys)挖掘基于距離的關(guān)聯(lián)規(guī)則等寬劃分將很近的值分開，并創(chuàng)建沒有數(shù)據(jù)的區(qū)間等深劃分將很遠(yuǎn)的值放在一組基于距離的關(guān)聯(lián)規(guī)則挖掘考慮屬性值的接近性，緊扣區(qū)間數(shù)據(jù)的語義，并允許值的類似基于距離的關(guān)聯(lián)規(guī)則挖掘的兩遍算法：1.使用聚類找出區(qū)間或簇2.搜索頻繁的一起出現(xiàn)的簇組，得到基于距離的關(guān)聯(lián)規(guī)則因為未考慮數(shù)據(jù)點(diǎn)之間或區(qū)間的相對距離，分箱方法不是總能緊扣區(qū)間數(shù)據(jù)的語義關(guān)聯(lián)規(guī)則的興趣度度量客觀度量兩個流行的度量指標(biāo)支持度置信度主觀度量最終，只有用戶才能確定一個規(guī)則是否有趣的，而且這種判斷是主觀的，因不同的用戶而異；通常認(rèn)為一個規(guī)則（模式）是有趣的，如果：它是出人意料的可行動的（用戶可以使用該規(guī)則做某些事情）挖掘了關(guān)聯(lián)規(guī)則后，哪些規(guī)則是用戶感興趣的？強(qiáng)關(guān)聯(lián)規(guī)則是否就是有趣的？對強(qiáng)關(guān)聯(lián)規(guī)則的批評（1）例1：(Aggarwal&Yu,PODS98)在5000個學(xué)生中3000個打籃球3750個喝麥片粥2000個學(xué)生既打籃球又喝麥片粥然而，打籃球=>喝麥片粥[40%,66.7%]是錯誤的，因為全部學(xué)生中喝麥片粥的比率是75%，比打籃球?qū)W生的66.7%要高打籃球=>不喝麥片粥[20%,33.3%]這個規(guī)則遠(yuǎn)比上面那個要精確，盡管支持度和置信度都要低的多對強(qiáng)關(guān)聯(lián)規(guī)則的批評（2）例1：(書P168，表5-7)上述數(shù)據(jù)可以得出buys(X,“computergames”)=>buys(X,“videos”)[40%,60%]但其實全部人中購買錄像帶的人數(shù)是75%，比60%多；事實上錄像帶和游戲是負(fù)相關(guān)的。由此可見A=>B的置信度有欺騙性，它只是給出A,B條件概率的估計，而不度量A,B間蘊(yùn)涵的實際強(qiáng)度。由關(guān)聯(lián)分析到相關(guān)分析我們需要一種度量事件間的相關(guān)性或者是依賴性的指標(biāo)當(dāng)項集A的出現(xiàn)獨(dú)立于項集B的出現(xiàn)時，P(A∪B)=P(A)P(B)，即corrA,B＝1，表明A與B無關(guān)，corrA,B>1表明A與B正相關(guān)，corrA,B<1表明A與B負(fù)相關(guān)將相關(guān)性指標(biāo)用于前面的例子，可以得出錄像帶和游戲?qū)⒌南嚓P(guān)性為：P({game,video})/(P({game})×P({video}))=0.4/(0.75×0.6)=0.89結(jié)論：錄像帶和游戲之間存在負(fù)相關(guān)基于約束的關(guān)聯(lián)挖掘如何對海量數(shù)據(jù)進(jìn)行交互性的，解釋性的挖掘？充分的利用各種約束條件知識類型約束數(shù)據(jù)約束維/層約束興趣度約束規(guī)則約束指定要挖掘的規(guī)則形式，可以用元規(guī)則來表示，說明規(guī)則的前件和后件中謂詞的最大和最小個數(shù)，或?qū)傩?、屬性值?或聚集之間的聯(lián)系關(guān)聯(lián)規(guī)則的元規(guī)則制導(dǎo)挖掘（1）元規(guī)則使得用戶可以說明他們感興趣的規(guī)則的語法形式例：在AllElectronics數(shù)據(jù)庫中挖掘時使用一個元規(guī)則表達(dá)顧客的特點(diǎn)和他購買的商品之間的關(guān)聯(lián)（具有哪兩種特點(diǎn)的顧客會買educationalsoftware?）P1(X,Y)∧P2(X,W)=>buys(X,"educationalsoftware")Y,W分別取賦給謂詞變量P1,P2的屬性值一般，元規(guī)則形成一個用戶希望探察的假定，而系統(tǒng)則尋找與該元規(guī)則匹配的規(guī)則，例如：age(X,"30-39")income(X,"42K-60K")buys(X,"educationalsoftware")關(guān)聯(lián)規(guī)則的元規(guī)則制導(dǎo)挖掘（2）假定我們希望挖掘的元規(guī)則形式為：P1∧P2∧…∧Pl=>Q1∧Q2∧…∧Qr設(shè)元規(guī)則中謂詞的個數(shù)為p=l+r，則找出符合該模板的關(guān)聯(lián)規(guī)則需以下兩步驟：找出所有的頻繁p-謂詞集Lp計算Lp中的l-謂詞子集的支持度，然后計算由Lp導(dǎo)出的規(guī)則的置信度數(shù)據(jù)立方體具有存放聚集維值的能力，適合多維關(guān)聯(lián)規(guī)則的挖掘，在n維數(shù)據(jù)立方體中(n>=p)挖掘上述