資源描述：
《數(shù)據(jù)挖掘原理與算法03關(guān)聯(lián)規(guī)則挖掘》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、第三章關(guān)聯(lián)規(guī)則挖掘理論和算法內(nèi)容提要基本概念與解決方法經(jīng)典的頻繁項(xiàng)目集生成算法分析Apriori算法的性能瓶頸問題Apriori的改進(jìn)算法2021/7/141關(guān)聯(lián)規(guī)則挖掘（AssociationRuleMining）是數(shù)據(jù)挖掘中研究較早而且至今仍活躍的研究方法之一。最早是由Agrawal等人提出的（1993）。最初提出的動(dòng)機(jī)是針對(duì)購(gòu)物籃分析（BasketAnalysis）問題提出的，其目的是為了發(fā)現(xiàn)交易數(shù)據(jù)庫（TransactionDatabase）中不同商品之間的聯(lián)系規(guī)則。關(guān)聯(lián)規(guī)則的挖掘工作成果頗豐。例如，關(guān)聯(lián)規(guī)則的挖掘理論、算法設(shè)計(jì)、算法的性能以及應(yīng)用推廣、并行關(guān)聯(lián)規(guī)則挖掘（Pa
2、rallelAssociationRuleMining）以及數(shù)量關(guān)聯(lián)規(guī)則挖掘（QuantitiveAssociationRuleMining）等。關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘的其他研究分支的基礎(chǔ)。3.1基本概念與解決方法2021/7/1423.1基本概念與解決方法事務(wù)數(shù)據(jù)庫設(shè)I={i1，i2，…，im}是一個(gè)項(xiàng)目集合，事務(wù)數(shù)據(jù)庫D={t1，t2，…，tn}是由一系列具有唯一標(biāo)識(shí)TID的事務(wù)組成，每個(gè)事務(wù)ti（i=1，2，…，n）都對(duì)應(yīng)I上的一個(gè)子集。一個(gè)事務(wù)數(shù)據(jù)庫可以用來刻畫：購(gòu)物記錄：I是全部物品集合，D是購(gòu)物清單，每個(gè)元組ti是一次購(gòu)買物品的集合（它當(dāng)然是I的一個(gè)子集）。其它應(yīng)用問題2
3、021/7/143支持度與頻繁項(xiàng)目集定義3-1（項(xiàng)目集的支持度）.給定一個(gè)全局項(xiàng)目集I和數(shù)據(jù)庫D，一個(gè)項(xiàng)目集I1?I在D上的支持度（Support）是包含I1的事務(wù)在D中所占的百分比：support（I1）=
4、
5、{t?D
6、I1?t}
7、
8、/
9、
10、D
11、
12、。定義3-2（頻繁項(xiàng)目集）.給定全局項(xiàng)目集I和數(shù)據(jù)庫D，D中所有滿足用戶指定的最小支持度（Minsupport）的項(xiàng)目集，即大于或等于minsupport的I的非空子集，稱為頻繁項(xiàng)目集（頻集：FrequentItemsets）或者大項(xiàng)目集（LargeIitemsets）。在頻繁項(xiàng)目集中挑選出所有不被其他元素包含的頻繁項(xiàng)目集稱為最大頻繁項(xiàng)目集
13、（最大頻集：MaximumFrequentItemsets）或最大大項(xiàng)目集（MaximumLargeIitemsets）。2021/7/144可信度與關(guān)聯(lián)規(guī)則定義3-3（關(guān)聯(lián)規(guī)則與可信度）.給定一個(gè)全局項(xiàng)目集I和數(shù)據(jù)庫D，一個(gè)定義在I和D上的關(guān)聯(lián)規(guī)則形如I1?I2，并且它的可信度或信任度或置信度（Confidence）是指包含I1和I2的事務(wù)數(shù)與包含I1的事務(wù)數(shù)之比，即Confidence（I1?I2）=support（I1∪I2）/support（I1），其中I1，I2?I，I1∩I2=Ф。定義3-4（強(qiáng)關(guān)聯(lián)規(guī)則）.D在I上滿足最小支持度和最小信任度（Minconfidence）的
14、關(guān)聯(lián)規(guī)則稱為強(qiáng)關(guān)聯(lián)規(guī)則（StrongAssociationRule）。2021/7/145關(guān)聯(lián)規(guī)則挖掘基本過程關(guān)聯(lián)規(guī)則挖掘問題可以劃分成兩個(gè)子問題：1.發(fā)現(xiàn)頻繁項(xiàng)目集:通過用戶給定Minsupport，尋找所有頻繁項(xiàng)目集或者最大頻繁項(xiàng)目集。2．生成關(guān)聯(lián)規(guī)則:通過用戶給定Minconfidence，在頻繁項(xiàng)目集中，尋找關(guān)聯(lián)規(guī)則。第1個(gè)子問題是近年來關(guān)聯(lián)規(guī)則挖掘算法研究的重點(diǎn)。2021/7/1463.2經(jīng)典的頻繁項(xiàng)目集生成算法分析項(xiàng)目集空間理論經(jīng)典的發(fā)現(xiàn)頻繁項(xiàng)目集算法關(guān)聯(lián)規(guī)則生成算法2021/7/1473.2.1項(xiàng)目集空間理論Agrawal等人建立了用于事務(wù)數(shù)據(jù)庫挖掘的項(xiàng)目集格空間理論（
15、1993,Appriori屬性）。定理3-1（Appriori屬性1）.如果項(xiàng)目集X是頻繁項(xiàng)目集，那么它的所有非空子集都是頻繁項(xiàng)目集。證明設(shè)X是一個(gè)項(xiàng)目集，事務(wù)數(shù)據(jù)庫T中支持X的元組數(shù)為s。對(duì)X的任一非空子集為Y，設(shè)T中支持Y的元組數(shù)為s1。根據(jù)項(xiàng)目集支持?jǐn)?shù)的定義，很容易知道支持X的元組一定支持Y，所以s1≥s，即support（Y）≥support（X）。按假設(shè)：項(xiàng)目集X是頻繁項(xiàng)目集，即support(X)≥minsupport，所以support（Y）≥support（X）≥minsupport，因此Y是頻繁項(xiàng)目集?！醵ɡ?-2（Appriori屬性2）.如果項(xiàng)目集X是非頻繁項(xiàng)目
16、集，那么它的所有超集都是非頻繁項(xiàng)目集。證明（略）2021/7/1483.2.2經(jīng)典的發(fā)現(xiàn)頻繁項(xiàng)目集算法1994年，Agrawal等人提出了著名的Apriori算法。算法3-1Apriori（發(fā)現(xiàn)頻繁項(xiàng)目集）（1）L1={large1-itemsets};//所有1-項(xiàng)目頻集（2）FOR（k=2;Lk-1??;k++）DOBEGIN（3）Ck=apriori-gen（Lk-1）;//Ck是k-候選集（4）FORalltransactionst?DDOBEGI
