第5章---關(guān)聯(lián)規(guī)則模型及應(yīng)用

1、數(shù)據(jù)挖掘技術(shù)與應(yīng)用 陳燕教授第5章 關(guān)聯(lián)規(guī)則模型及應(yīng)用大連海事大學(xué)本章提綱 關(guān)聯(lián)規(guī)則的基礎(chǔ)理論5.1 Apriori關(guān)聯(lián)規(guī)則算法5.2 改進(jìn)的Apriori關(guān)聯(lián)規(guī)則方法5.3 Apriori關(guān)聯(lián)規(guī)則方法的實(shí)例5.4 小結(jié)5.55.1關(guān)聯(lián)規(guī)則的基礎(chǔ)理論5.1.1 關(guān)聯(lián)規(guī)則的定義與解釋5.1.2 關(guān)聯(lián)規(guī)則在知識管理過程中的作用5.1.1 關(guān)聯(lián)規(guī)則的定義與解釋關(guān)聯(lián)規(guī)則（Association Rules）是指在大型的數(shù)據(jù)庫系統(tǒng)中，迅速找出各事物之間潛在的、有價(jià)值的關(guān)聯(lián)，用規(guī)則表示出來，經(jīng)過推理、積累形成知識后，得出重要的相關(guān)聯(lián)的結(jié)論，從而為當(dāng)前市場經(jīng)濟(jì)提供準(zhǔn)確的決策手段。關(guān)聯(lián)規(guī)則的應(yīng)用已經(jīng)比較廣泛，

2、如條形碼的應(yīng)用已使大型零售商品的組織問題成為現(xiàn)實(shí)，從決策領(lǐng)域到通訊報(bào)警系統(tǒng)的應(yīng)用，以及診斷和預(yù)測等相關(guān)領(lǐng)域。 5.1.1 關(guān)聯(lián)規(guī)則的定義與解釋關(guān)聯(lián)規(guī)則的研究和應(yīng)用是數(shù)據(jù)挖掘中最活躍和比較深入的分支，目前，已經(jīng)提出了許多關(guān)聯(lián)規(guī)則挖掘的理論和算法。最為著名的是R.Agrawal等提出的Apriori及其改進(jìn)算法。為了發(fā)現(xiàn)有意義的關(guān)聯(lián)規(guī)則，需要給定兩個閾值：最小支持度（Minimum Support）和最小可信度（Minimum Confidence）。5.1.1 關(guān)聯(lián)規(guī)則的定義與解釋挖掘出的關(guān)聯(lián)規(guī)則必須滿足用戶規(guī)定的最小支持度，它表示了一組項(xiàng)目關(guān)聯(lián)在一起需要滿足的最低聯(lián)系程度。挖掘出的關(guān)聯(lián)規(guī)則也必

3、須滿足用戶規(guī)定的最小可信度，它反映了一個關(guān)聯(lián)規(guī)則的最低可靠度。在這個意義上，數(shù)據(jù)挖掘系統(tǒng)的目的就是從數(shù)據(jù)庫中挖掘出滿足最小支持度和最小可信度的關(guān)聯(lián)規(guī)則。 5.1.2 關(guān)聯(lián)規(guī)則在知識管理過程中的作用 知識管理是一個過程，通過這一過程可以學(xué)習(xí)新知識和獲得新經(jīng)驗(yàn)，并將這些新知識和新經(jīng)驗(yàn)反映出來，進(jìn)行共享，以用來促進(jìn)、增強(qiáng)個人的知識和機(jī)構(gòu)組織的價(jià)值。如果我們將數(shù)據(jù)管理中的數(shù)據(jù)提取作為數(shù)據(jù)倉庫的低層管理過程的話，那么數(shù)據(jù)庫知識發(fā)現(xiàn)（Knowledge Discovery in Databases, KDD）的過程則可作為數(shù)據(jù)倉庫的高層管理的過程，而關(guān)聯(lián)規(guī)則又作為數(shù)據(jù)倉庫的主要內(nèi)容出臺，所以關(guān)聯(lián)規(guī)則作為知

4、識管理過程的重要內(nèi)容。 5.1.2 關(guān)聯(lián)規(guī)則在知識管理過程中的作用 知識管理過程及其發(fā)展 5.1.2 關(guān)聯(lián)規(guī)則在知識管理過程中的作用 知識管理的基礎(chǔ)內(nèi)容包括從系統(tǒng)繼承過來的模型與知識。在未來的發(fā)展趨勢中，也可以根據(jù)模型的集成進(jìn)行模型的推理、知識的推理等推導(dǎo)過程來產(chǎn)生規(guī)則和獲得知識。這個階段產(chǎn)生的規(guī)則應(yīng)該是信息集成后的規(guī)則。當(dāng)然，知識集成是按照新的、更高更復(fù)雜的問題需求而集成的。這個階段的基礎(chǔ)應(yīng)該是KDD處理后的結(jié)果，也就是說KDD作為知識集成階段的基礎(chǔ)。因此，知識管理是以DBS為基礎(chǔ)，應(yīng)用多種知識發(fā)現(xiàn)和決策支持理論與技術(shù)方法。而模型的挖掘與知識的挖掘、模型的集成與知識的集成階段將是知識管理的未

5、來發(fā)展趨勢。5.1.2 關(guān)聯(lián)規(guī)則在知識管理過程中的作用 關(guān)聯(lián)規(guī)則在大型的數(shù)據(jù)庫系統(tǒng)中為我們提供了各屬性（項(xiàng)）之間的潛在的、有價(jià)值的聯(lián)系，使用關(guān)聯(lián)規(guī)則也能找出其它主題的大型數(shù)據(jù)庫中的各屬性之間的潛在的間接的關(guān)聯(lián)。這對于分析各類事物將要導(dǎo)致其它的潛在的發(fā)展趨勢是十分重要的。在KDD中利用關(guān)聯(lián)規(guī)則算法解決這一類問題是目前挖掘潛在的相聯(lián)的各事物間關(guān)系較好的方法。關(guān)聯(lián)規(guī)則在知識管理中起著一種橋梁的作用，在數(shù)據(jù)倉庫系統(tǒng)中屬于數(shù)據(jù)挖掘和DSS的技術(shù)。5.1.2 關(guān)聯(lián)規(guī)則在知識管理過程中的作用 關(guān)聯(lián)規(guī)則在知識管理中的橋梁作用 5.2關(guān)聯(lián)規(guī)則的基礎(chǔ)理論5.2.1 關(guān)聯(lián)規(guī)則算法的相關(guān)概念5.2.2 關(guān)聯(lián)規(guī)則算法的

6、流程5.2.1 關(guān)聯(lián)規(guī)則算法的相關(guān)概念 1.項(xiàng)集或候選項(xiàng)集項(xiàng)集Item=Item1, Item2,., Itemm；TR是事物的集合；TRItem，并且TR是一個0,1屬性的集合。集合k_Item=Item1, Item2,., Itemk稱為k項(xiàng)集或者k項(xiàng)候選項(xiàng)集。假設(shè)DB包含m個屬性（A, B,., M）；1項(xiàng)集1_Item=A, B,., M，共有m個候選項(xiàng)集；2項(xiàng)集2_Item=A, B, A, C,.,A, M, B, C,., B, M, C, D,., L, M，共有m(m-1)/2個項(xiàng)集；依次，m項(xiàng)集m_Item=A, B, C, M，有1個項(xiàng)集。5.2.1 關(guān)聯(lián)規(guī)則算法的相關(guān)

7、概念 2. 支持度支持度support簡寫sup，指的是某條規(guī)則的前件或后件對應(yīng)的支持?jǐn)?shù)與記錄總數(shù)的百分比。假設(shè)A的支持度是sup(A)，sup(A)=TRTRA/n；AB的支持度sup(AB) = sup(AB) =|TR|TRAB|/|n|，其中，n是DB中的總的記錄數(shù)目。3. 可信度可信度confidence簡寫conf，規(guī)則AB具有可信度conf(AB)表示DB中包含A的事物同時(shí)也包含B的百分比，是AB的支持度sup(AB)與前件A的支持度sup(A)的百分比：conf(AB)=sup(AB)/sup(A)。 5.2.1 關(guān)聯(lián)規(guī)則算法的相關(guān)概念 4. 強(qiáng)項(xiàng)集和非頻繁項(xiàng)集如果某k項(xiàng)候選項(xiàng)

8、集的支持度大于等于所設(shè)定的最小支持度閾值，則稱該k項(xiàng)候選項(xiàng)集為k項(xiàng)強(qiáng)項(xiàng)集（Large k-itemset）或者k項(xiàng)頻繁項(xiàng)集（Frequent k-itemset）。同時(shí)，對于支持度小于最小支持度的k項(xiàng)候選項(xiàng)集稱為k項(xiàng)非頻繁項(xiàng)集。定理（頻繁項(xiàng)集的反單調(diào)性）：設(shè)A，B是數(shù)據(jù)集DB中的項(xiàng)集，若A包含B，則A的支持度大于B的支持度；若A包含于B，且A是非頻繁項(xiàng)集，則B也是非頻繁項(xiàng)集；若A包含于B，且B是頻繁項(xiàng)集，則A也是頻繁項(xiàng)集。 5.2.1 關(guān)聯(lián)規(guī)則算法的相關(guān)概念 5. 產(chǎn)生關(guān)聯(lián)規(guī)則若A，B為項(xiàng)集，AItem，BItem并且AB=，一個關(guān)聯(lián)規(guī)則是形如AB的蘊(yùn)涵式。當(dāng)前關(guān)聯(lián)規(guī)則算法普遍基于Suppor

9、t-Confidence模型。支持度是項(xiàng)集中包含A和B的記錄數(shù)與所有記錄數(shù)之比，描述了A和B這兩個物品集的并集在所有的事務(wù)中出現(xiàn)的概率有多大，能夠說明規(guī)則的有用性。規(guī)則AB在項(xiàng)集中的可信度，是指在出現(xiàn)了物品集A的事務(wù)T中，物品集B也同時(shí)出現(xiàn)的概率有多大，能夠說明規(guī)則的確定性。5.2.1 關(guān)聯(lián)規(guī)則算法的相關(guān)概念 產(chǎn)生關(guān)聯(lián)規(guī)則，即是從強(qiáng)項(xiàng)集中產(chǎn)生關(guān)聯(lián)規(guī)則。在最小可信度的條件門檻下，若強(qiáng)項(xiàng)集的可信度滿足最小可信度，稱此k項(xiàng)強(qiáng)項(xiàng)集為關(guān)聯(lián)規(guī)則。例如：若A,B為2項(xiàng)強(qiáng)項(xiàng)集，同時(shí)conf(AB)大于等于最小可信度，即sup(AB)min_sup且conf(AB)min_conf，則稱AB為關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則

10、算法的流程 R.Agrawal等人在1993年設(shè)計(jì)了一個Apriori算法是一種最有影響力的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。其核心是基于兩階段的頻集思想的遞推算法。該關(guān)聯(lián)規(guī)則在分類上屬于單維、單層、布爾關(guān)聯(lián)規(guī)則。該算法將關(guān)聯(lián)規(guī)則挖掘分解為兩個子問題：（1）找出存在于事務(wù)數(shù)據(jù)庫中所有的頻繁項(xiàng)目集。即那些支持度大于用戶給定支持度閾值的項(xiàng)目集。（2）在找出的頻繁項(xiàng)目集的基礎(chǔ)上產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則。即產(chǎn)生那些支持度和可信度分別大于或等于用戶給定的支持度和可信度閾值的關(guān)聯(lián)規(guī)則。 關(guān)聯(lián)規(guī)則算法的流程 第二步相對容易些，因?yàn)樗恍枰谝呀?jīng)找出的頻繁項(xiàng)目集的基礎(chǔ)上列出所有可能的關(guān)聯(lián)規(guī)則，同時(shí)，滿足支持度和可信度閾值

11、要求的規(guī)則被認(rèn)為是有趣的關(guān)聯(lián)規(guī)則。第一個步驟是挖掘關(guān)聯(lián)規(guī)則的關(guān)鍵步驟，挖掘關(guān)聯(lián)規(guī)則的總體性能由第一個步驟決定，因此，所有挖掘關(guān)聯(lián)規(guī)則的算法都是著重于研究第一個步驟。關(guān)聯(lián)規(guī)則算法的流程 Apriori算法在尋找頻繁項(xiàng)集時(shí)，利用了頻繁項(xiàng)集的向下封閉性（反單調(diào)性），即頻繁項(xiàng)集的子集必須是頻繁項(xiàng)集，采用逐層搜索的迭代方法，由候選項(xiàng)集生成頻繁項(xiàng)集，最終由頻繁項(xiàng)集得到關(guān)聯(lián)規(guī)則，這些操作主要是由連接和剪枝來完成。Apriori算法最大的問題是產(chǎn)生大量的候選項(xiàng)集，可能需要頻繁重復(fù)掃描數(shù)據(jù)庫，因此為候選項(xiàng)集合理分配內(nèi)存，實(shí)現(xiàn)對大型數(shù)據(jù)庫系統(tǒng)快速掃描的技術(shù)和方法是提高管理規(guī)則效率的重要途徑，面向大型數(shù)據(jù)庫，從海量

12、數(shù)據(jù)中高效提取關(guān)聯(lián)規(guī)則是非常重要的。 關(guān)聯(lián)規(guī)則算法的流程 L1=Large 1-itemsets /掃描所有事務(wù)，計(jì)算每項(xiàng)出現(xiàn)次數(shù)，產(chǎn)生頻繁1-項(xiàng)集集合L1for (k=2; Lk-1; k+) do /進(jìn)行迭代循環(huán)，根據(jù)前一次的Lk-1得到頻繁k-項(xiàng)集集合Lk begin Ck=join(Lkm,Lkn) / join對每兩個有k-1個共同項(xiàng)目的長度為k的模式Lkm和Lkn進(jìn)行連接 Ck =prune(Ck)/ prune根據(jù)頻繁項(xiàng)集的反單調(diào)性，對Ck進(jìn)行減枝，得到Ck Ck= apriori-gen(Lk-1) /產(chǎn)生k項(xiàng)候選項(xiàng)集Ck for all transactions tD do

13、/掃描數(shù)據(jù)庫一遍 begin Ct=subset(Ck,t) / 確定每個事務(wù)t所含k-候選項(xiàng)集的subset(Ck，t) for all candidates c Ct do c.count+ /對候選項(xiàng)集的計(jì)數(shù)存放在hash表中 end Lk=c Ct | c.count min_sup /刪除候選項(xiàng)集中小于最小支持度的,得到k-頻繁項(xiàng)集Lk end for all subset sLk /對于每個頻繁項(xiàng)集Lk，產(chǎn)生Lk的所有非空子集s If conf(s Lk -s )=min_conf /可信度大于最小可信度的強(qiáng)項(xiàng)集為關(guān)聯(lián)規(guī)則 Then Output ( s Lk -s) /由頻繁項(xiàng)集

14、產(chǎn)生關(guān)聯(lián)規(guī)則 endend /得到所有的關(guān)聯(lián)規(guī)則 5.3改進(jìn)的Apriori關(guān)聯(lián)規(guī)則方法5.3.1 動態(tài)存儲空間的構(gòu)建5.3.2 快速產(chǎn)生強(qiáng)項(xiàng)集的算法流程5.3.3 改進(jìn)算法的時(shí)間復(fù)雜性分析動態(tài)存儲空間的構(gòu)建 為了充分利用空間，在程序設(shè)計(jì)中采用了合理分配內(nèi)存的方法，給出了計(jì)算長度k的強(qiáng)項(xiàng)集存儲分配公式： 其中Ck表示k項(xiàng)侯選項(xiàng)集。 這個公式為動態(tài)運(yùn)行機(jī)制開辟了準(zhǔn)確的存儲空間。動態(tài)存儲空間的構(gòu)建 設(shè)共有M個屬性k=1時(shí)，1-項(xiàng)強(qiáng)項(xiàng)集共有m1個屬性，即 。k=2時(shí)，2-項(xiàng)候選集為1-項(xiàng)強(qiáng)項(xiàng)集中屬性的兩兩組合，所以2-項(xiàng)候選集中所占空間為 ；掃描數(shù)據(jù)庫，求2-項(xiàng)強(qiáng)項(xiàng)集。2-項(xiàng)強(qiáng)項(xiàng)集共有m2個屬性即

15、。k=3時(shí)，3-項(xiàng)候選集為2-項(xiàng)強(qiáng)項(xiàng)集中每次取出首位相同的兩個項(xiàng)集做連接操作，其中，將首位相同的這些屬性的集合用S3i表示 。相對應(yīng)在2-項(xiàng)強(qiáng)項(xiàng)集中，包含這些屬性的項(xiàng)出現(xiàn)的次數(shù)分別合計(jì)為： ，3-項(xiàng)候選項(xiàng)集所占空間為 。掃描數(shù)據(jù)庫，求3-項(xiàng)強(qiáng)項(xiàng)集。 動態(tài)存儲空間的構(gòu)建 同理，依次求k-1項(xiàng)強(qiáng)項(xiàng)集，k-1項(xiàng)強(qiáng)項(xiàng)集共有mk-1個屬性 。當(dāng)求k項(xiàng)強(qiáng)項(xiàng)集時(shí)，將（k-1）項(xiàng)強(qiáng)項(xiàng)集中各個項(xiàng)集前（k-2）個屬性相同的這些屬性的集合用Ski表示，相對應(yīng)在（k-1）項(xiàng)強(qiáng)項(xiàng)集中，包含這些屬性的項(xiàng)出現(xiàn)的次數(shù)分別合計(jì)為 ，k項(xiàng)候選項(xiàng)集所占空間為 ： 快速產(chǎn)生強(qiáng)項(xiàng)集的算法流程 1. 掃描事務(wù)數(shù)據(jù)庫中的每個事務(wù)，產(chǎn)生候選

16、1-項(xiàng)集的集合C1；2. 根據(jù)最小支持度min_sup，由候選1-項(xiàng)集的集合C1，產(chǎn)生強(qiáng)1-項(xiàng)集合L1，對于在事務(wù)數(shù)據(jù)庫中出現(xiàn)次數(shù)比最小支持度min_sup計(jì)數(shù)少的屬性列進(jìn)行邏輯標(biāo)記，在以后的各次掃描中跳過這些屬性；3. 求k項(xiàng)集，令k=1；4. 由Lk產(chǎn)生候選（k+1）-項(xiàng)集的集合Ck+1；快速產(chǎn)生強(qiáng)項(xiàng)集的算法流程 5. 根據(jù)最小支持度min_sup，由候選（k+1）-項(xiàng)集的集合Ck+1，產(chǎn)生(k+1)-強(qiáng)項(xiàng)集的集合Lk+1，方法是：掃描數(shù)據(jù)庫，當(dāng)執(zhí)行到第i行時(shí)，（1）若該行的項(xiàng)集長度小于（k+1），則對該行作出邏輯標(biāo)記，在以后的各次掃描中，都可以跳過該行，不再掃描；（2）若該行的項(xiàng)集長度等

17、于（k+1），確定該行項(xiàng)集的模式，與候選項(xiàng)集中的模式進(jìn)行匹配，匹配成功則該項(xiàng)集的支持度計(jì)數(shù)器+1，對候選項(xiàng)集中的其它模式，在本行中不再掃描；匹配不成功則跳過本行；快速產(chǎn)生強(qiáng)項(xiàng)集的算法流程 （3）若該行的長度大于（k+1），將此行中與候選k+1項(xiàng)集模式相匹配的項(xiàng)集支持度計(jì)數(shù)器+1。將候選集Ck+1中所有項(xiàng)集的支持度與min_sup進(jìn)行比較，產(chǎn)生Lk+1；6. 若Lk+1，則k=k+1，跳往步驟4，否則，跳往步驟7；7. 根據(jù)最小置信度min_conf，由強(qiáng)項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則，結(jié)束?？焖佼a(chǎn)生強(qiáng)項(xiàng)集的算法流程 快 速產(chǎn)生強(qiáng)關(guān)聯(lián)屬性(Lk)的方法 改進(jìn)算法的時(shí)間復(fù)雜性分析 Apriori算法的時(shí)間復(fù)雜性

18、為 。 一般來說， ，而p作為被刪除的列，k作為強(qiáng)項(xiàng)集的長度。對改進(jìn)后的關(guān)聯(lián)規(guī)則算法的時(shí)間復(fù)雜度的分析：（1）在最壞的情況下，當(dāng)p=k時(shí)，有：（2）當(dāng)kp或者kp（屬于一般的情況）時(shí)，滿足：因此，共節(jié)省時(shí)間是 一般地說，kp 。 改進(jìn)算法的時(shí)間復(fù)雜性分析 在解決以上三個主要研究問題后，總結(jié)改進(jìn)的Apriori方法的計(jì)算步驟，快速產(chǎn)生強(qiáng)關(guān)聯(lián)屬性的關(guān)聯(lián)規(guī)則方法總體流程為：1. 將DBS問題轉(zhuǎn)換成抽象的DBS：將數(shù)據(jù)庫中的數(shù)量相關(guān)的問題轉(zhuǎn)換成邏輯相關(guān)的問題。按照決策問題要求，將數(shù)據(jù)庫中的各個屬性轉(zhuǎn)換成多維邏輯屬性。 2. 求強(qiáng)項(xiàng)集：該問題可以分解為兩個子問題：（1）求出D中滿足最小支持度min_sup的所有強(qiáng)項(xiàng)集；（2）利用強(qiáng)項(xiàng)集生成滿足最小可信度min_conf的所有關(guān)聯(lián)規(guī)則。3. 將抽象的DBS問題轉(zhuǎn)換成DBS，表達(dá)關(guān)聯(lián)規(guī)則。 改進(jìn)算法的時(shí)間復(fù)雜性