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

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

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

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