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ù)項(xiàng)之間存在的潛在關(guān)系，形式為XY，其中XI，YI，且XY=，X稱為規(guī)則頭(antecedent)，Y稱為規(guī)則尾(consequent)。項(xiàng)集之間的關(guān)聯(lián)表示如果X出現(xiàn)在一條交易中，那么Y在這條交易中同時(shí)出現(xiàn)的可能性比較高。關(guān)聯(lián)規(guī)則就是希望發(fā)現(xiàn)事務(wù)數(shù)據(jù)庫中不同商品（項(xiàng)）之間的關(guān)聯(lián)，反映顧客的購買行為模式，比如購買某一商品對(duì)購買其他商品的影響。例如，80%的顧客如果買了牛奶，通常也會(huì)買面包。應(yīng)用發(fā)現(xiàn)所有*面包的關(guān)聯(lián)規(guī)則，促進(jìn)面包的銷售發(fā)現(xiàn)所有牛奶*的關(guān)聯(lián)規(guī)則，了解終止牛奶的銷售的影響發(fā)現(xiàn)商場(chǎng)里貨架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)每種商品是一個(gè)數(shù)據(jù)項(xiàng)（簡(jiǎn)稱項(xiàng)）I={ii，i2，…，im}是全體數(shù)據(jù)項(xiàng)的集合數(shù)據(jù)項(xiàng)集(Itemset)，簡(jiǎn)稱為項(xiàng)集是由數(shù)據(jù)項(xiàng)構(gòu)成的非空集合。項(xiàng)集X包含的元素個(gè)數(shù)稱為項(xiàng)集的長度，長度為k的項(xiàng)集稱為k階項(xiàng)集(k_itemset)D為事務(wù)數(shù)據(jù)庫，每個(gè)事務(wù)T有唯一的TID標(biāo)識(shí)，對(duì)應(yīng)一個(gè)項(xiàng)集T，有T

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

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

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

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

c：一條包含{X}的交易也同時(shí)包含Y的條件概率支持度和置信度不小于給定閾值強(qiáng)關(guān)聯(lián)規(guī)則:對(duì)于給定的支持閾值和置信閾值，發(fā)現(xiàn)那些置信度和支持度都大于或等于相應(yīng)閾值的規(guī)則稱為強(qiáng)關(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ī)則時(shí)序關(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ù)量信息以及其它的交易信息(如商品的單價(jià)、一次購買的數(shù)量和總價(jià)等)，得到的規(guī)則稱為數(shù)值型關(guān)聯(lián)規(guī)則;也可將關(guān)聯(lián)規(guī)則擴(kuò)展到關(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ī)則：所有的變量都是細(xì)節(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臺(tái)式機(jī)HP打印機(jī)（細(xì)節(jié)層次上的單層關(guān)聯(lián)規(guī)則）臺(tái)式機(jī)HP打印機(jī)（較高層次和細(xì)節(jié)層次之間的層間關(guān)聯(lián)規(guī)則）臺(tái)式機(jī)打印機(jī)（高層次上的同層關(guān)聯(lián)規(guī)則）14單維關(guān)聯(lián)規(guī)則vs多維關(guān)聯(lián)規(guī)則單維關(guān)聯(lián)規(guī)則只涉及數(shù)據(jù)表的一個(gè)字段，多維關(guān)聯(lián)規(guī)則涉及數(shù)據(jù)表的多個(gè)字段。buys(x,”啤酒“)buys(x,”尿布“)：?jiǎn)尉S關(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ù)是否允許同一個(gè)字段在規(guī)則中重復(fù)出現(xiàn)，多維關(guān)聯(lián)規(guī)則又可以分為維間關(guān)聯(lián)規(guī)則（不允許字段在規(guī)則中重復(fù)出現(xiàn)）和混合維關(guān)聯(lián)規(guī)則（允許字段在規(guī)則的左右部分同時(shí)出現(xiàn)）。age(x,“20…30”)

buys(x,“筆記本電腦”)buys(x,“打印機(jī)”):混合維關(guān)聯(lián)規(guī)則15特殊類型的關(guān)聯(lián)規(guī)則有約束的關(guān)聯(lián)規(guī)則：對(duì)關(guān)聯(lián)規(guī)則施加語義約束，限制規(guī)則左部或者規(guī)則右部必需包含某些字段或?qū)σ?guī)則形式進(jìn)行約束發(fā)現(xiàn)所有規(guī)則右部中包含“面包”的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)單價(jià)在100元以上或者購買數(shù)量不小于10的商品之間的關(guān)聯(lián)規(guī)則否定關(guān)聯(lián)規(guī)則：限制某些字段不出現(xiàn)在規(guī)則中咖啡茶葉：如果不購買咖啡，那么買茶葉的可能性較大帶權(quán)值的關(guān)聯(lián)規(guī)則：將商品的價(jià)格或購買數(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)通常與高爾夫球場(chǎng)相鄰的對(duì)象時(shí)態(tài)關(guān)聯(lián)規(guī)則附加了時(shí)間維度，從交易數(shù)據(jù)集中找出相似的交易關(guān)聯(lián)規(guī)則交易序列的關(guān)聯(lián)規(guī)則常常帶有周期性，如季節(jié)性的購物高峰，這樣的規(guī)則稱為循環(huán)規(guī)則，即在一定時(shí)間間隔內(nèi)周期性出現(xiàn)的規(guī)則

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

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

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

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

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ī)則概念擴(kuò)展其它序列模式模糊關(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ī)則挖掘的兩個(gè)步驟大項(xiàng)集的搜索：搜索支持度不小于指定支持閾值的項(xiàng)集需要掃描數(shù)據(jù)庫，是關(guān)聯(lián)規(guī)則挖掘的主要步驟根據(jù)搜索的方向、范圍、目標(biāo)和數(shù)據(jù)格式，可以構(gòu)造不同的搜索算法

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

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

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

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

Step2:削減forallCk

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

例：找出頻繁項(xiàng)集－－Apriori算法30項(xiàng)集支持度計(jì)數(shù)｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2項(xiàng)集支持度計(jì)數(shù)｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2C1L1掃描D，對(duì)每個(gè)候選計(jì)數(shù)比較候選支持度計(jì)數(shù)與最小支持度計(jì)數(shù)找出頻繁1－項(xiàng)集的集合L1找出頻繁項(xiàng)集－－Apriori算法例：最小支持度閾值為231項(xiàng)集支持度計(jì)數(shù)｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2項(xiàng)集｛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

找出頻繁項(xiàng)集－－Apriori算法連接&剪枝32項(xiàng)集支持度計(jì)數(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項(xiàng)集支持度計(jì)數(shù)｛I1，I2｝4｛I1，I3｝4｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2C2L2比較候選支持度計(jì)數(shù)與最小支持度計(jì)數(shù)掃描D，對(duì)每個(gè)候選計(jì)數(shù)33項(xiàng)集支持度計(jì)數(shù)｛I1，I2｝4｛I1，I3｝4｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2L2項(xiàng)集｛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-項(xiàng)子集是{I1,I2},{I1,I3}和{I2,I3}。{I1,I2,I3}的所有2-項(xiàng)子集都是L2的元素。因此，保留{I1,I2,I3}在C3中。{I2,I3,I5}的2-項(xiàng)子集是{I2,I3},{I2,I5}和{I3,I5}。{I3,I5}不是L2的元素，因而不是頻繁的。因此，由C3中刪除{I2,I3,I5}。剪枝后C3＝{{I1,I2,I3},{I1,I2,I5}}。

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

對(duì)于每個(gè)頻繁項(xiàng)集l，找出l的所有非空子集；b.對(duì)于l的每個(gè)非空子集a，如果

support_count(l)/support_count(a)≥min_conf，則輸出規(guī)則“a＝>（l－a）”。頻繁項(xiàng)集產(chǎn)生強(qiáng)關(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可輸出，是強(qiáng)關(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ù)庫，計(jì)算候選k-itemsets的支持度Apriori的瓶頸大量的候選項(xiàng)集(尤其是C2)n個(gè)大1-itemsetn*(n-1)/2個(gè)候選2-itemsets多次掃描數(shù)據(jù)庫需要掃描n+1次，n是大項(xiàng)集的最大長度41Apriori算法的改進(jìn)策略改進(jìn)策略減少掃描數(shù)據(jù)量減少掃描次數(shù)減少候選項(xiàng)集利用前綴樹提高搜索速度AprioriTidAprioriHybral縱向算法DHP抽樣算法SEARSpearFP-treePartitionDIC42AprioriTid算法原理：如果一個(gè)事務(wù)不包含k階大項(xiàng)集，那么也必然不包含k+1階大項(xiàng)集，因此，將這些事務(wù)刪除后，下一次循環(huán)就可減少掃描事務(wù)量，而不影響候選項(xiàng)集的支持?jǐn)?shù)43方法：構(gòu)造一個(gè)Tid表，用來記錄每條事務(wù)包含的候選項(xiàng)集。k階候選項(xiàng)集的Tid表記作：Ck

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

44AprioriTid算法示例事務(wù)數(shù)據(jù)庫DTid1C2L1L2minsup=3Tid245分區(qū)算法原理：“分而治之”，先把數(shù)據(jù)庫從邏輯上分成幾個(gè)不相交的分區(qū)，劃分的原則是使得每個(gè)分區(qū)的數(shù)據(jù)都能夠存入內(nèi)存,并且各分區(qū)的支持閾值和全局的支持閾值相同。性質(zhì)：如果一個(gè)項(xiàng)集是全局大項(xiàng)集，那么它至少在一個(gè)分區(qū)中是大項(xiàng)集。劃分算法的過程：首先對(duì)每個(gè)分區(qū)分別計(jì)算局部大項(xiàng)集（如果項(xiàng)集在分區(qū)中的支持度不小于支持閾值，則稱為局部大項(xiàng)集），再將結(jié)果合并得到全局大項(xiàng)集（如果項(xiàng)集在整個(gè)數(shù)據(jù)庫中的支持度不小于支持閾值，則稱為全局大項(xiàng)集）。46Partition算法：每次處理一個(gè)分區(qū)，利用Apriori算法得到本分區(qū)的局部大項(xiàng)集；然后將各分區(qū)的局部大項(xiàng)集合并，生成候選項(xiàng)集，掃描整個(gè)事務(wù)數(shù)據(jù)庫，計(jì)算這些項(xiàng)集的支持度，最終得到全局大項(xiàng)集。由于局部大項(xiàng)集的生成在內(nèi)存中進(jìn)行，整個(gè)過程只需要掃描兩次數(shù)據(jù)庫，一次用來讀入分區(qū)，另一次用來計(jì)算全局大項(xiàng)集。Partition算法適用于數(shù)據(jù)規(guī)模較大,不能一次讀入內(nèi)存的情況,而且可以并行地執(zhí)行，每個(gè)處理器處理一個(gè)分區(qū)的數(shù)據(jù)，得到局部大項(xiàng)集之后，經(jīng)過處理器之間的通信，產(chǎn)生全局的候選項(xiàng)集。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)算法過程每個(gè)處理器分配一部分?jǐn)?shù)據(jù)每個(gè)處理器的內(nèi)存復(fù)制全部候選項(xiàng)集每個(gè)處理器獨(dú)立執(zhí)行Apriori算法，掃描本地?cái)?shù)據(jù)，計(jì)算局部支持度，通過處理器之間的通訊得到全局支持度50Count分布(CD)算法優(yōu)缺點(diǎn)各處理器獨(dú)立計(jì)算，只在循環(huán)結(jié)束時(shí)交互支持度，降低了通訊量?jī)?nèi)存利用率低，各處理器存儲(chǔ)各自的候選項(xiàng)集，如果候選項(xiàng)集數(shù)量很大時(shí)，必須分幾次裝入內(nèi)存，造成數(shù)據(jù)庫的多次掃描適應(yīng)于項(xià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ù)每個(gè)分類型數(shù)值映射為一個(gè)變量對(duì)每個(gè)連續(xù)型變量分段，每段映射為一個(gè)變量如何對(duì)數(shù)值型屬性分段？主要問題是區(qū)間的劃分和合并先對(duì)數(shù)值型屬性細(xì)分，計(jì)算每個(gè)區(qū)間的支持度，再合并相鄰的區(qū)間，直到支持度超過一個(gè)指定的閾值為止。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é)點(diǎn)是最一般的概念，樹的葉結(jié)點(diǎn)是最具體的概念即原始數(shù)據(jù)。設(shè)a,b是兩個(gè)概念，若b是以a為根的子樹中的結(jié)點(diǎn)，則稱b是a的后代或a是b的祖先。如果a是b的直接祖先，則a稱是b的父親，或b是a的兒子。

衣服鞋子

外套襯衫

運(yùn)動(dòng)鞋長靴

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

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

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

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

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

層1支持閾值＝12%

一個(gè)第i層的k－項(xiàng)集被考察，當(dāng)且僅當(dāng)它在第（i-1）層的父節(jié)點(diǎn)k－項(xiàng)集是頻繁的。68ML_T2算法ML_T2算法[32]采用交易削減的方法，減小了掃描的數(shù)據(jù)量，從而提高算法的效率。該算法按照概念層次從高到低的順序，搜索每層的大項(xiàng)集。69ML_T2算法步驟：在最高概念層次上，函數(shù)get_large_1_itemset掃描T[1]（原始數(shù)據(jù)庫D），得到一階大項(xiàng)集；由函數(shù)get_filtered_table利用一階大項(xiàng)集對(duì)T[1]過濾，刪除每條交易中祖先不屬于大項(xiàng)集的項(xiàng)，如果某交易所有的項(xiàng)都被刪除，那么該交易也被刪除，最終得到削減的數(shù)據(jù)庫T[2]。然后，利用Apriori算法通過循環(huán)得到各階大項(xiàng)集。從第2層開始，算法掃描T[2],依次得到每層的大項(xiàng)集。當(dāng)達(dá)到了最大層次數(shù)或者某層上的1階大項(xiàng)集為空時(shí)，算法停止。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層上，得到一階大項(xiàng)集后，對(duì)數(shù)據(jù)庫T[p]進(jìn)行過濾，得到T[p+1],從而實(shí)現(xiàn)逐層減小掃描的數(shù)據(jù)量，但這種方法只在每層所過濾掉的數(shù)據(jù)量較大時(shí)比較有效.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是任意概念層次上的大項(xiàng)集，滿足X∩Y=

，且Y不包括X中的項(xiàng)的祖先。2023/2/4決策量化技術(shù)74定義2.18設(shè)項(xiàng)集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)計(jì)規(guī)律，“外套”

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

衣服鞋子

外套襯衫

運(yùn)動(dòng)鞋長靴

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

衣服鞋子

外套襯衫

運(yùn)動(dòng)鞋長靴

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

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

1外套鞋子0.8夾克鞋子0.4

衣服