SAS關(guān)聯(lián)規(guī)則及相關(guān)算法

1關(guān)聯(lián)規(guī)則挖掘2關(guān)聯(lián)規(guī)則挖掘1、關(guān)聯(lián)規(guī)則挖掘的概念2、二值型關(guān)聯(lián)規(guī)則挖掘3、并行關(guān)聯(lián)規(guī)則挖掘4、數(shù)值型關(guān)聯(lián)規(guī)則挖掘5、多層次關(guān)聯(lián)規(guī)則挖掘6、關(guān)聯(lián)規(guī)則的增量挖掘關(guān)聯(lián)規(guī)則的類型11~16關(guān)聯(lián)規(guī)則相關(guān)定義3~10關(guān)聯(lián)規(guī)則的應(yīng)用173什么是關(guān)聯(lián)規(guī)則？關(guān)聯(lián)規(guī)則：描述數(shù)據(jù)庫中各數(shù)據(jù)項之間存在的潛在關(guān)系，形式為XY，其中XI，YI，且XY=，X稱為規(guī)則頭(antecedent)，Y稱為規(guī)則尾(consequent)。項集之間的關(guān)聯(lián)表示如果X出現(xiàn)在一條交易中，那么Y在這條交易中同時出現(xiàn)的可能性比較高。關(guān)聯(lián)規(guī)則就是希望發(fā)現(xiàn)事務(wù)數(shù)據(jù)庫中不同商品（項）之間的關(guān)聯(lián)，反映顧客的購買行為模式，比如購買某一商品對購買其他商品的影響。例如，80%的顧客如果買了牛奶，通常也會買面包。應(yīng)用發(fā)現(xiàn)所有*面包的關(guān)聯(lián)規(guī)則，促進面包的銷售發(fā)現(xiàn)所有牛奶*的關(guān)聯(lián)規(guī)則，了解終止牛奶的銷售的影響發(fā)現(xiàn)商場里貨架A和貨架B上商品之間的關(guān)聯(lián)規(guī)則，調(diào)整商品的布置，提高銷售量4關(guān)聯(lián)規(guī)則的基本概念Given:(1)事務(wù)/交易數(shù)據(jù)庫

(2)顧客每次購買的商品構(gòu)成一條事務(wù)(3)每種商品是一個數(shù)據(jù)項（簡稱項）I={ii，i2，…，im}是全體數(shù)據(jù)項的集合數(shù)據(jù)項集(Itemset)，簡稱為項集是由數(shù)據(jù)項構(gòu)成的非空集合。項集X包含的元素個數(shù)稱為項集的長度，長度為k的項集稱為k階項集(k_itemset)D為事務(wù)數(shù)據(jù)庫，每個事務(wù)T有唯一的TID標識，對應(yīng)一個項集T，有T

I。交易T包含項集X當且僅當XT5事務(wù)(交易)數(shù)據(jù)庫的例子預(yù)處理6支持數(shù)(度)、支持閾值與大項集項集X在事務(wù)集合D中的支持數(shù)(supportcount)是D中包含X的事務(wù)數(shù)，記作X.sup或者support(X)。X在D中的支持度(support)就是X的支持數(shù)與D的總事務(wù)數(shù)之比，從統(tǒng)計的角度看，X的支持度就是X在D中出現(xiàn)的概率，用符號Pr(X)表示。支持閾值表示項集在統(tǒng)計意義上的最低重要性，用符號s表示。如果事務(wù)數(shù)據(jù)庫的事務(wù)量是固定的，常用最小支持數(shù)（minsup=s|D|，其中|D|是總事務(wù)數(shù)）代替支持閾值。

事先給定一個minsup（或s），如果項集X的支持數(shù)X.supminsup（或項集X的支持度Pr(X)s），則X稱為大項集(largeitemset)或者頻繁項集(frequentitemset)。7例子令minsup=2，計算項集及其支持數(shù)。其中，{果醬面包}、{香蕉}、{酸奶}、{香蕉，果醬面包}的支持數(shù)minsup，所以是大項集。

8置信度與置信閾值規(guī)則XY的支持度定義為Pr(XY)，表示X，Y同時出現(xiàn)的可能性。規(guī)則XY的置信度（confidence）定義為Pr(XY)/Pr(X)=support(XY)/support(X)，表示D中包含X的事務(wù)同時也包含Y的可能性，記為conf(XY)。由于這個數(shù)值等于在X出現(xiàn)的條件下Y也出現(xiàn)的概率，因此規(guī)則的置信度也可以用條件概率符號Pr(Y|X)表示。置信閾值表示規(guī)則在統(tǒng)計意義上應(yīng)該滿足的最低置信度，用符號minconf表示。9關(guān)聯(lián)規(guī)則挖掘XY是關(guān)聯(lián)規(guī)則，給定支持閾值、置信閾值支持度(support),

s：包含{X,Y}的概率置信度(confidence),

c：一條包含{X}的交易也同時包含Y的條件概率支持度和置信度不小于給定閾值強關(guān)聯(lián)規(guī)則:對于給定的支持閾值和置信閾值，發(fā)現(xiàn)那些置信度和支持度都大于或等于相應(yīng)閾值的規(guī)則稱為強關(guān)聯(lián)規(guī)則。購買“嬰兒尿布”的顧客Customerbuysboth購買“啤酒”的顧客10關(guān)聯(lián)規(guī)則挖掘示例規(guī)則

A

C:support=support({A,C})=50%confidence=support({A,C})/support({A})=66.6%規(guī)則C

A:support=support({A,C})=50%confidence=support({A,C})/support({C})=100%支持閾值50%置信閾值50%11關(guān)聯(lián)規(guī)則的類型關(guān)聯(lián)規(guī)則按規(guī)則的變量類型分按規(guī)則中數(shù)據(jù)的抽象層次分按規(guī)則涉及的數(shù)據(jù)維數(shù)分特殊類型的關(guān)聯(lián)規(guī)則按應(yīng)用領(lǐng)域分分二值（布爾）型關(guān)聯(lián)規(guī)則數(shù)值型關(guān)聯(lián)規(guī)則單維關(guān)聯(lián)規(guī)則多維關(guān)聯(lián)規(guī)則否定關(guān)聯(lián)規(guī)則帶約束關(guān)聯(lián)規(guī)則帶權(quán)值關(guān)聯(lián)規(guī)則空間關(guān)聯(lián)規(guī)則時序關(guān)聯(lián)規(guī)則單層關(guān)聯(lián)規(guī)則多層關(guān)聯(lián)規(guī)則12二值（布爾）型關(guān)聯(lián)規(guī)則vs數(shù)值型(量化)關(guān)聯(lián)規(guī)則二值型關(guān)聯(lián)規(guī)則處理的數(shù)據(jù)都是離散的、分類化的，用來顯示這些變量之間的關(guān)系。buys(x,“面包”)

buys(x,“牛奶”)[0.5%,60%]buys(x,“SQLServer”)^buys(x,“DMBook”)

buys(x,“DBMiner”)[0.2%,60%]在關(guān)聯(lián)規(guī)則挖掘中加入數(shù)量信息以及其它的交易信息(如商品的單價、一次購買的數(shù)量和總價等)，得到的規(guī)則稱為數(shù)值型關(guān)聯(lián)規(guī)則;也可將關(guān)聯(lián)規(guī)則擴展到關(guān)系數(shù)據(jù)庫中，表示屬性值之間的關(guān)聯(lián)關(guān)系。age(x,“30..39”)^income(x,“42..48K”)

buys(x,“PC”)[1%,75%]13單層關(guān)聯(lián)規(guī)則vs多層關(guān)聯(lián)規(guī)則單層關(guān)聯(lián)規(guī)則：所有的變量都是細節(jié)數(shù)據(jù)(原始的商品)，沒有層次的區(qū)分多層關(guān)聯(lián)規(guī)則：體現(xiàn)了數(shù)據(jù)的層次性（用概念樹或者概念圖表示），發(fā)生關(guān)聯(lián)的數(shù)據(jù)可能位于同一層次（同層關(guān)聯(lián)規(guī)則），也可能位于不同的層次（層間關(guān)聯(lián)規(guī)則）。IBM臺式機HP打印機（細節(jié)層次上的單層關(guān)聯(lián)規(guī)則）臺式機HP打印機（較高層次和細節(jié)層次之間的層間關(guān)聯(lián)規(guī)則）臺式機打印機（高層次上的同層關(guān)聯(lián)規(guī)則）14單維關(guān)聯(lián)規(guī)則vs多維關(guān)聯(lián)規(guī)則單維關(guān)聯(lián)規(guī)則只涉及數(shù)據(jù)表的一個字段，多維關(guān)聯(lián)規(guī)則涉及數(shù)據(jù)表的多個字段。buys(x,”啤酒“)buys(x,”尿布“)：單維關(guān)聯(lián)規(guī)則gender(x,“女”)

job(x,“秘書”)：二維關(guān)聯(lián)規(guī)則age(x,“20…30”)

job(x,“學(xué)生”)

buys(x,“筆記本電腦”)：三維關(guān)聯(lián)規(guī)則根據(jù)是否允許同一個字段在規(guī)則中重復(fù)出現(xiàn)，多維關(guān)聯(lián)規(guī)則又可以分為維間關(guān)聯(lián)規(guī)則（不允許字段在規(guī)則中重復(fù)出現(xiàn)）和混合維關(guān)聯(lián)規(guī)則（允許字段在規(guī)則的左右部分同時出現(xiàn)）。age(x,“20…30”)

buys(x,“筆記本電腦”)buys(x,“打印機”):混合維關(guān)聯(lián)規(guī)則15特殊類型的關(guān)聯(lián)規(guī)則有約束的關(guān)聯(lián)規(guī)則：對關(guān)聯(lián)規(guī)則施加語義約束，限制規(guī)則左部或者規(guī)則右部必需包含某些字段或?qū)σ?guī)則形式進行約束發(fā)現(xiàn)所有規(guī)則右部中包含“面包”的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)單價在100元以上或者購買數(shù)量不小于10的商品之間的關(guān)聯(lián)規(guī)則否定關(guān)聯(lián)規(guī)則：限制某些字段不出現(xiàn)在規(guī)則中咖啡茶葉：如果不購買咖啡，那么買茶葉的可能性較大帶權(quán)值的關(guān)聯(lián)規(guī)則：將商品的價格或購買數(shù)量作為權(quán)值洗滌劑消毒柜

16其它領(lǐng)域的關(guān)聯(lián)規(guī)則空間關(guān)聯(lián)規(guī)則發(fā)現(xiàn)地理位置的關(guān)聯(lián)性85%的靠近高速公路的大城鎮(zhèn)與水相鄰發(fā)現(xiàn)通常與高爾夫球場相鄰的對象時態(tài)關(guān)聯(lián)規(guī)則附加了時間維度，從交易數(shù)據(jù)集中找出相似的交易關(guān)聯(lián)規(guī)則交易序列的關(guān)聯(lián)規(guī)則常常帶有周期性，如季節(jié)性的購物高峰，這樣的規(guī)則稱為循環(huán)規(guī)則，即在一定時間間隔內(nèi)周期性出現(xiàn)的規(guī)則

17關(guān)聯(lián)規(guī)則的應(yīng)用零售業(yè)：安排商品布局，提供購買建議市場營銷：分析顧客的購買行為和習(xí)慣

識別欺詐：發(fā)現(xiàn)異常事件

因特網(wǎng)：提高網(wǎng)絡(luò)的響應(yīng)速度，調(diào)度網(wǎng)絡(luò)代理的緩存，發(fā)現(xiàn)用戶的瀏覽模式

醫(yī)學(xué)：預(yù)測一次手術(shù)、藥物檢驗或藥物治療的效果

18關(guān)聯(lián)規(guī)則挖掘的算法關(guān)聯(lián)規(guī)則挖掘AIS算法Apriori算法Hash算法多層次關(guān)聯(lián)規(guī)則抽樣算法分區(qū)算法分布算法增量算法數(shù)值型關(guān)聯(lián)規(guī)則提高效率算法關(guān)聯(lián)規(guī)則概念擴展其它序列模式模糊關(guān)聯(lián)規(guī)則否定關(guān)聯(lián)規(guī)則有約束的關(guān)聯(lián)規(guī)則SETM算法并行算法帶權(quán)值的關(guān)聯(lián)規(guī)則19關(guān)聯(lián)規(guī)則挖掘1、關(guān)聯(lián)規(guī)則挖掘的概念2、二值（布爾）型關(guān)聯(lián)規(guī)則挖掘3、并行關(guān)聯(lián)規(guī)則挖掘4、數(shù)值型關(guān)聯(lián)規(guī)則挖掘5、多層次關(guān)聯(lián)規(guī)則挖掘6、關(guān)聯(lián)規(guī)則的增量挖掘20關(guān)聯(lián)規(guī)則挖掘的兩個步驟大項集的搜索：搜索支持度不小于指定支持閾值的項集需要掃描數(shù)據(jù)庫，是關(guān)聯(lián)規(guī)則挖掘的主要步驟根據(jù)搜索的方向、范圍、目標和數(shù)據(jù)格式，可以構(gòu)造不同的搜索算法

關(guān)聯(lián)規(guī)則的生成：對每一個大項集L，檢查L的每個非空子集X，生成規(guī)則XL-X，它的支持度為Pr(L)，置信度為Pr(L)/Pr(X)，只有那些大于或等于用戶給定的置信閾值的規(guī)則才被保留下來。根據(jù)支持度的性質(zhì)，這個步驟可簡化為先檢驗L的最大子集，只有當生成規(guī)則的置信度不小于置信閾值時才檢驗更小的子集。例如，L={A,B,C,D}，如果規(guī)則{ABC}{D}的置信度達不到置信閾值，則{AB}{CD}也達不到置信閾值(因為Pr({AB})≥Pr({ABC}))。

21大項集的搜索策略大項集的搜索按搜索的順序分按搜索的范圍分按搜索的目標分按數(shù)據(jù)存儲格式分由底向上由頂向下混合全搜索最大項集搜索橫向搜索縱向搜索完備搜索啟發(fā)式搜索22關(guān)聯(lián)規(guī)則挖掘的第一個算法：AIS過程：AIS算法的基本思想是通過多次循環(huán)來計算大項集。Ck:k階候選項集

Lk:k階大項集首先，掃描數(shù)據(jù)庫，得到一階大項集。然后，在第k（k>1）次掃描時，對每條交易t，找到它所包含的所有k-1階的大項集Lk-1，根據(jù)t中出現(xiàn)的數(shù)據(jù)項，把它們分別擴展成k階項集，加入到k階候選項集的集合中，同時對候選項集的支持數(shù)進行累加。例如，如果{A,B,C,D}是當前處理的交易，{AB}是它所包含的2階大項集，由{AB}擴展得到{ABC}，{ABD}，作為3階候選項集。當完成一遍掃描后，就可以得到k階候選項集的支持數(shù)，那些支持數(shù)不小于最小支持數(shù)的項集就是k階大項集。開始下一次掃描，直到候選項集為空時，算法停止。23AIS算法示例事務(wù)數(shù)據(jù)庫D掃描DC1L2掃描DL1C2minsup=3C3掃描Dminconf=80%強關(guān)聯(lián)規(guī)則是：EB24Apriori算法AIS算法的瓶頸:候選項集是在掃描事務(wù)數(shù)據(jù)庫時構(gòu)造的，產(chǎn)生的候選項集中有很多并不是大項集，這樣不僅會浪費計算時間，還會占用大量的存儲空間。Apriori算法:利用上次循環(huán)產(chǎn)生的大項集構(gòu)造新的候選項集，然后掃描數(shù)據(jù)庫，計算候選項集的支持數(shù)，掃描結(jié)束時得到大項集依據(jù)：一個項集是大項集當且僅當它的所有子集都是大項集。反之，如果一個項集的某個子集不是大項集，那么這個項集也不可能是大項集。例如，如果{AB}是大項集，

那么{A}，{B}也是大項集25算法過程掃描數(shù)據(jù)庫，計算1階大項集；從2階開始，每次循環(huán)利用上次循環(huán)產(chǎn)生的大項集構(gòu)造新候選項集，然后計算每個候選項集的支持度，得到下一階大項集；重復(fù)以上步驟，直到某階大項集為空。26Apriori算法示例事務(wù)數(shù)據(jù)庫D掃描DC1C2掃描DC2L1L2minsup=3C3itemset{BCE}27問題(1):如何產(chǎn)生候選數(shù)據(jù)項集？假設(shè)數(shù)據(jù)項按順序排列Step1:大項集自連接Ck=Lk-1Lk-1

Step2:削減forallCk

中的每個元素cdoforallc的子集sdoif(s不再大項集Lk-1中)thendeletecfromCk28Apriori_gen示例L3={abc,abd,acd,ace,bcd}自連接:L3L3{abcd}，{abce}，{acde}削減:{acde}isremovedbecause{ade}isnotinL3同理：{abce}也要被刪除。C4={abcd}29交易號項集合T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3表1交易數(shù)據(jù)庫D

例：找出頻繁項集－－Apriori算法30項集支持度計數(shù)｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2項集支持度計數(shù)｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2C1L1掃描D，對每個候選計數(shù)比較候選支持度計數(shù)與最小支持度計數(shù)找出頻繁1－項集的集合L1找出頻繁項集－－Apriori算法例：最小支持度閾值為231項集支持度計數(shù)｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2項集｛I1，I2｝｛I1，I3｝｛I1，I4｝｛I1，I5｝｛I2，I3｝｛I2，I4｝｛I2，I5｝｛I3，I4｝｛I3，I5｝｛I4，I5｝L1C2由L1產(chǎn)生候選C2Lk-1用于產(chǎn)生候選Ck

找出頻繁項集－－Apriori算法連接&剪枝32項集支持度計數(shù)｛I1，I2｝4｛I1，I3｝4｛I1，I4｝1｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2｛I3，I4｝0｛I3，I5｝1｛I4，I5｝0項集支持度計數(shù)｛I1，I2｝4｛I1，I3｝4｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2C2L2比較候選支持度計數(shù)與最小支持度計數(shù)掃描D，對每個候選計數(shù)33項集支持度計數(shù)｛I1，I2｝4｛I1，I3｝4｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2L2項集｛I1，I2，I3｝｛I1，I2，I5｝由L2產(chǎn)生候選C3C3連接&剪枝34連接：C3＝L2

L2＝{{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,I5}}

{{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,I5}}={{I1,I2,I3},{I1,I2,I5},{I1,I3,I5},{I2,I3,I4},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}}35剪枝：{I1,I2,I3}的2-項子集是{I1,I2},{I1,I3}和{I2,I3}。{I1,I2,I3}的所有2-項子集都是L2的元素。因此，保留{I1,I2,I3}在C3中。{I2,I3,I5}的2-項子集是{I2,I3},{I2,I5}和{I3,I5}。{I3,I5}不是L2的元素，因而不是頻繁的。因此，由C3中刪除{I2,I3,I5}。剪枝后C3＝{{I1,I2,I3},{I1,I2,I5}}。

36項集支持度計數(shù)｛I1，I2，I3｝2｛I1，I2，I5｝2C3掃描D，對每個候選計數(shù)比較候選支持度計數(shù)與最小支持度計數(shù)項集支持度計數(shù)｛I1，I2，I3｝2｛I1，I2，I5｝2L337步驟：a.

對于每個頻繁項集l，找出l的所有非空子集；b.對于l的每個非空子集a，如果

support_count(l)/support_count(a)≥min_conf，則輸出規(guī)則“a＝>（l－a）”。頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則38例：假定數(shù)據(jù)包含頻繁集l＝{I1,I2,I5}，L的非空子集有{I1,I2},{I1,I5},{I2,I5},{I1},{I2},和{I5}。可以由l產(chǎn)生的關(guān)聯(lián)規(guī)則：

I1I2I5，confidence＝2/4＝50%；

I1I5I2，confidence＝2/2＝100%；

I2I5I1，confidence＝2/2＝100%；

I1I2I5，confidence＝2/6＝33%；

I2I1I5，confidence＝2/7＝29%；

I5I1I2,confidence＝2/2＝100%；若最小置信度閾值為70%，則只有I1I5I2，I2I5I1，I5I1I2可輸出，是強關(guān)聯(lián)規(guī)則39Apriori算法—例子數(shù)據(jù)庫D掃描DC1L1L2C2C2掃描DC3L3掃描Ditemset{235}例：最小支持度閾值為240Apriori算法的瓶頸Apriorialgorithm的核心根據(jù)頻繁(k-1)-itemsets產(chǎn)生候選k-itemsets每次循環(huán)掃描數(shù)據(jù)庫，計算候選k-itemsets的支持度Apriori的瓶頸大量的候選項集(尤其是C2)n個大1-itemsetn*(n-1)/2個候選2-itemsets多次掃描數(shù)據(jù)庫需要掃描n+1次，n是大項集的最大長度41Apriori算法的改進策略改進策略減少掃描數(shù)據(jù)量減少掃描次數(shù)減少候選項集利用前綴樹提高搜索速度AprioriTidAprioriHybral縱向算法DHP抽樣算法SEARSpearFP-treePartitionDIC42AprioriTid算法原理：如果一個事務(wù)不包含k階大項集，那么也必然不包含k+1階大項集，因此，將這些事務(wù)刪除后，下一次循環(huán)就可減少掃描事務(wù)量，而不影響候選項集的支持數(shù)43方法：構(gòu)造一個Tid表，用來記錄每條事務(wù)包含的候選項集。k階候選項集的Tid表記作：Ck

，其形式為<t.TID,{CCk|Ct}>，其中TID是事務(wù)t的標識，C是事務(wù)t中包含的k階候選項集。如果一個事務(wù)不包含任何k階候選項集，那么這條事務(wù)就不會出現(xiàn)在中。由于1階候選項集就是所有的項，與D相同。當k>1時，由產(chǎn)生。對每個k階候選項集C，如果C的兩個子集都包含在里的某條記錄中，那么就添加C到的相應(yīng)記錄中。由Tid表得到k階候選項集的支持數(shù)，避免對事務(wù)數(shù)據(jù)庫的重復(fù)掃描。當k較大時，Tid表的元素個數(shù)遠遠小于總事務(wù)數(shù)，且每個事務(wù)只包含少量的候選項集，因此隨著循環(huán)的增加，掃描的數(shù)據(jù)量逐漸降低。

44AprioriTid算法示例事務(wù)數(shù)據(jù)庫DTid1C2L1L2minsup=3Tid245分區(qū)算法原理：“分而治之”，先把數(shù)據(jù)庫從邏輯上分成幾個不相交的分區(qū)，劃分的原則是使得每個分區(qū)的數(shù)據(jù)都能夠存入內(nèi)存,并且各分區(qū)的支持閾值和全局的支持閾值相同。性質(zhì)：如果一個項集是全局大項集，那么它至少在一個分區(qū)中是大項集。劃分算法的過程：首先對每個分區(qū)分別計算局部大項集（如果項集在分區(qū)中的支持度不小于支持閾值，則稱為局部大項集），再將結(jié)果合并得到全局大項集（如果項集在整個數(shù)據(jù)庫中的支持度不小于支持閾值，則稱為全局大項集）。46Partition算法：每次處理一個分區(qū)，利用Apriori算法得到本分區(qū)的局部大項集；然后將各分區(qū)的局部大項集合并，生成候選項集，掃描整個事務(wù)數(shù)據(jù)庫，計算這些項集的支持度，最終得到全局大項集。由于局部大項集的生成在內(nèi)存中進行，整個過程只需要掃描兩次數(shù)據(jù)庫，一次用來讀入分區(qū)，另一次用來計算全局大項集。Partition算法適用于數(shù)據(jù)規(guī)模較大,不能一次讀入內(nèi)存的情況,而且可以并行地執(zhí)行，每個處理器處理一個分區(qū)的數(shù)據(jù)，得到局部大項集之后，經(jīng)過處理器之間的通信，產(chǎn)生全局的候選項集。47分區(qū)算法示例事務(wù)數(shù)據(jù)庫DCL掃描D支持閾值=50%分區(qū)2L1L2itemsetsup{BC}1{BE}1分區(qū)1L1L2L3itemsetsup.{A}2{B}2{C}3{E}248關(guān)聯(lián)規(guī)則挖掘1、關(guān)聯(lián)規(guī)則挖掘的概念2、二值型關(guān)聯(lián)規(guī)則挖掘3、并行關(guān)聯(lián)規(guī)則挖掘4、數(shù)值型關(guān)聯(lián)規(guī)則挖掘5、多層次關(guān)聯(lián)規(guī)則挖掘6、關(guān)聯(lián)規(guī)則的增量挖掘49Count分布(CD)算法過程每個處理器分配一部分數(shù)據(jù)每個處理器的內(nèi)存復(fù)制全部候選項集每個處理器獨立執(zhí)行Apriori算法，掃描本地數(shù)據(jù)，計算局部支持度，通過處理器之間的通訊得到全局支持度50Count分布(CD)算法優(yōu)缺點各處理器獨立計算，只在循環(huán)結(jié)束時交互支持度，降低了通訊量內(nèi)存利用率低，各處理器存儲各自的候選項集，如果候選項集數(shù)量很大時，必須分幾次裝入內(nèi)存，造成數(shù)據(jù)庫的多次掃描適應(yīng)于項數(shù)小和min_support大的情形51關(guān)聯(lián)規(guī)則挖掘1、關(guān)聯(lián)規(guī)則挖掘的概念2、二值型關(guān)聯(lián)規(guī)則挖掘3、并行關(guān)聯(lián)規(guī)則挖掘4、數(shù)值型關(guān)聯(lián)規(guī)則挖掘5、多層次關(guān)聯(lián)規(guī)則挖掘6、關(guān)聯(lián)規(guī)則的增量挖掘52數(shù)值型關(guān)聯(lián)規(guī)則分類型變量有限取值，無序數(shù)值型變量連續(xù)，有序方法將數(shù)據(jù)轉(zhuǎn)化為布爾型數(shù)據(jù)每個分類型數(shù)值映射為一個變量對每個連續(xù)型變量分段，每段映射為一個變量如何對數(shù)值型屬性分段？主要問題是區(qū)間的劃分和合并先對數(shù)值型屬性細分，計算每個區(qū)間的支持度，再合并相鄰的區(qū)間，直到支持度超過一個指定的閾值為止。54關(guān)聯(lián)規(guī)則挖掘1、關(guān)聯(lián)規(guī)則挖掘的概念2、二值型關(guān)聯(lián)規(guī)則挖掘3、并行關(guān)聯(lián)規(guī)則挖掘4、數(shù)值型關(guān)聯(lián)規(guī)則挖掘5、多層次關(guān)聯(lián)規(guī)則挖掘6、關(guān)聯(lián)規(guī)則的增量挖掘55概念層次樹概念層次樹是一棵從一般概念到具體概念的層次關(guān)系樹，樹的根結(jié)點是最一般的概念，樹的葉結(jié)點是最具體的概念即原始數(shù)據(jù)。設(shè)a,b是兩個概念，若b是以a為根的子樹中的結(jié)點，則稱b是a的后代或a是b的祖先。如果a是b的直接祖先，則a稱是b的父親，或b是a的兒子。

衣服鞋子

外套襯衫

運動鞋長靴

夾克滑雪衫56多層次關(guān)聯(lián)規(guī)則為什么挖掘多層次關(guān)聯(lián)規(guī)則？數(shù)據(jù)項之間經(jīng)常存在概念層次層次越高，數(shù)據(jù)項的支持度也越大某些高層次上的規(guī)則或許能顯示有用的信息57多層關(guān)聯(lián)規(guī)則項通常具有層次底層的項通常支持度也低某些特定層的規(guī)則可能更有意義食品面包牛奶脫脂奶光明統(tǒng)一酸奶白黃58多層關(guān)聯(lián)規(guī)則

支持度不變vs.支持度遞減支持度不變:在各層之間使用統(tǒng)一的支持度

一個最小支持度閾值.如果一個項集的父項集不具有最小支持度，那他本身也不可能滿足最小支持度。如果支持閾值太高丟失底層關(guān)聯(lián)規(guī)則太低生成太多的高層關(guān)聯(lián)規(guī)則支持度遞減:隨著層次的降低支持度遞減59支持度不變支持度不變多層挖掘牛奶[support=10%]酸奶

[support=6%]脫脂奶[support=4%]層1min_sup=5%層2min_sup=5%60支持度遞減支持度遞減多層挖掘酸奶

[support=6%]脫脂奶[support=4%]層1min_sup=5%層2min_sup=3%牛奶[support=10%]61多層關(guān)聯(lián)：冗余過濾由于“祖先”關(guān)系的原因，有些規(guī)則可能是多余的。例子牛奶白面包[support=8%,confidence=70%]

(1)酸奶白面包[support=2%,confidence=72%](2)我們稱第一個規(guī)則是第二個規(guī)則的祖先參考規(guī)則的祖先，如果他的支持度與我們“預(yù)期”的支持度近似的話，我們就說這條規(guī)則是冗余的。62食品面包牛奶脫脂奶光明統(tǒng)一酸奶白黃63挖掘多層次關(guān)聯(lián)規(guī)則同層關(guān)聯(lián)規(guī)則處于同概念層的關(guān)聯(lián)規(guī)則，挖掘在特定概念層上逐層展開，需對項的每個層次進行處理，一般采用自頂向下的策略。對每一層，可以使用類似于單層關(guān)聯(lián)規(guī)則挖掘的發(fā)現(xiàn)頻繁項集的任何算法；算法：ML-T2、ML_T1LA、ML-SH、ML-T2+等層間關(guān)聯(lián)規(guī)則跨越層邊界，規(guī)則中的項不要求屬于同一概念層。算法：ML-CH等64同層關(guān)聯(lián)規(guī)則的挖掘步驟對概念層次樹進行編碼將事務(wù)的項用對應(yīng)的編碼代替，構(gòu)成編碼數(shù)據(jù)庫從高到低依次搜索各層的大項集由各層的大項集分別生成關(guān)聯(lián)規(guī)則65概念層次樹及事務(wù)的編碼先對根結(jié)點編碼，再按照從上到下的順序?qū)γ繉拥慕Y(jié)點逐層編碼。一個概念的子結(jié)點的序號為：1,2,3…。子結(jié)點代碼=父結(jié)點代碼+子結(jié)點在子樹中的序號，依此類推把數(shù)據(jù)庫中的值用其編碼代替

66層交叉過濾如果數(shù)據(jù)項A是非頻繁的，那么A的后代也是非頻繁的如果某個數(shù)據(jù)項是非頻繁的，那么包含其后代的數(shù)據(jù)項集也必定是非頻繁的利用上層大項集對下層事務(wù)進行消減ML_T1L2算法、ML_T1LA算法等

67層交叉過濾體育類商品（支持度＝10％）籃球足球非頻繁不考察不考察層2支持閾值＝3%

層1支持閾值＝12%

一個第i層的k－項集被考察，當且僅當它在第（i-1）層的父節(jié)點k－項集是頻繁的。68ML_T2算法ML_T2算法[32]采用交易削減的方法，減小了掃描的數(shù)據(jù)量，從而提高算法的效率。該算法按照概念層次從高到低的順序，搜索每層的大項集。69ML_T2算法步驟：在最高概念層次上，函數(shù)get_large_1_itemset掃描T[1]（原始數(shù)據(jù)庫D），得到一階大項集；由函數(shù)get_filtered_table利用一階大項集對T[1]過濾，刪除每條交易中祖先不屬于大項集的項，如果某交易所有的項都被刪除，那么該交易也被刪除，最終得到削減的數(shù)據(jù)庫T[2]。然后，利用Apriori算法通過循環(huán)得到各階大項集。從第2層開始，算法掃描T[2],依次得到每層的大項集。當達到了最大層次數(shù)或者某層上的1階大項集為空時，算法停止。70ML_T2算法示例T[1]L1L2minsup=4T[2]L2L1minsup=3L1L2minsup=3L3itemsetsup.{11*}5{12*}4{21*}4{22*}471ML_T1LA算法ML_T1LA算法與ML_T1算法的過程基本相同，區(qū)別是ML_T1LA在每層都執(zhí)行類似的交易削減。在任意的p層上，得到一階大項集后，對數(shù)據(jù)庫T[p]進行過濾，得到T[p+1],從而實現(xiàn)逐層減小掃描的數(shù)據(jù)量，但這種方法只在每層所過濾掉的數(shù)據(jù)量較大時比較有效.72ML_T1LA算法示例T[1]L1L2minsup=4T[2]L2L1minsup=3T[3]L1L2minsup=3L3itemsetsup.{11*}5{12*}4{21*}4{22*}473層間關(guān)聯(lián)規(guī)則的挖掘定義2.17層間關(guān)聯(lián)規(guī)則又稱為廣義關(guān)聯(lián)規(guī)則，形式為XY，其中X，Y是任意概念層次上的大項集，滿足X∩Y=

，且Y不包括X中的項的祖先。2023/2/4決策量化技術(shù)74定義2.18設(shè)項集X={x1,x2,…,xk}，Y={y1,y2,…,yk}，其中yj是xj的祖先概念。如果已知Y的支持度為Pr(Y)，那么X的期望支持度等于：EY(Pr(X))=(Pr(X1)/Pr(Y1)*Pr(X2)/Pr(Y2)*…….Pr(XK)/Pr(YK))*Pr(Y)75定義2.19設(shè)XY是一條規(guī)則，Z是X的祖先，W是Y的祖先。如果已知規(guī)則ZW的置信度為Pr(W|Z)，那么規(guī)則XY的期望置信度等于：EZW(Pr(XY))

=

(Pr(Y1)/Pr(W1)*Pr(Y2)/Pr(W2)*…….Pr(YK)/Pr(WK))*Pr(W|Z)76如果“衣服”

“鞋子”是一條關(guān)聯(lián)規(guī)則，支持度為20%，置信度為60%。假設(shè)買衣服的交易中外套占50%，那么根據(jù)統(tǒng)計規(guī)律，“外套”

“鞋子”的期望支持度應(yīng)該為10%，期望置信度為60%。如果經(jīng)過計算發(fā)現(xiàn)實際的支持度和置信度與期望值相近，那么這條規(guī)則就是冗余的。

衣服鞋子

外套襯衫

運動鞋長靴

夾克滑雪衫77如果項集Y是項集X的祖先，而且不存在其它的項集Z，滿足Y是Z的祖先，Z是X的祖先，那么稱Y是X的最近祖先或者父項集。78

衣服鞋子

外套襯衫

運動鞋長靴

夾克滑雪衫例如，{外套，長靴}，{夾克，鞋子}都是{夾克，長靴}的父項集.而{衣服，長靴}是{夾克，長靴}的祖先但不是父項集，因為{衣服，長靴}是{外套，長靴}的祖先，而{外套，長靴}又是{夾克，長靴}的祖先。評價規(guī)則是否是冗余的，首先要根據(jù)其父項集計算規(guī)則的期望支持度和期望置信度。79定義2.20給定興趣閾值R，如果XY沒有祖先，或者它的支持度是相對于父項集的期望支持度的R倍，或者置信度是期望置信度的R倍，那么這條規(guī)則是有趣的，否則就是冗余的。廣義關(guān)聯(lián)規(guī)則挖掘就是找到置信度和支持度都大于相應(yīng)閾值的非冗余規(guī)則。80例2.15假設(shè)我們從事務(wù)數(shù)據(jù)庫中得到以下項集和規(guī)則，令興趣閾值R=2，判斷規(guī)則的冗余性。

項集 支持度衣服 0.5外套 0.2夾克 0.1規(guī)則支持度衣服鞋子

1外套鞋子0.8夾克鞋子0.4

衣服