關(guān)聯(lián)規(guī)則挖掘的apriori算法改進(jìn)綜述

《關(guān)聯(lián)規(guī)則挖掘的apriori算法改進(jìn)綜述》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、關(guān)聯(lián)規(guī)則挖掘的Apriori算法改進(jìn)綜述1引言數(shù)據(jù)挖掘是一種半自動(dòng)地從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中,提取出隱含在其中潛在有用的信息和知識(shí)的過(guò)程。數(shù)據(jù)挖掘從數(shù)據(jù)中提取人們感興趣的可用信息和知識(shí)，并將提取出來(lái)的信息和知識(shí)表示成概念、規(guī)則、規(guī)律和模式。數(shù)據(jù)挖掘，又稱數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)(KnowledgeDiscoveryinDatabase,KDD)，指的是從大型數(shù)據(jù)庫(kù)的數(shù)據(jù)倉(cāng)庫(kù)中提取人們感興趣的知識(shí)，這些知識(shí)是隱含的、事先未知的潛在有用信息，換言之，數(shù)據(jù)挖掘是一個(gè)利用各種分析工具在海量數(shù)據(jù)

2、中，發(fā)現(xiàn)模型和數(shù)據(jù)間關(guān)系的過(guò)程，這些模型和關(guān)系可以用來(lái)作出預(yù)測(cè)。對(duì)于數(shù)據(jù)挖掘技術(shù)的研究已引起了國(guó)際人工智能和數(shù)據(jù)庫(kù)等領(lǐng)域?qū)＜遗c學(xué)者的廣泛關(guān)注，這其中在事務(wù)數(shù)據(jù)庫(kù)中挖掘關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘領(lǐng)域中的一個(gè)非常重要的研究課題。關(guān)聯(lián)規(guī)則是美國(guó)IBMAlmadenresearchcenter的RabeshAgrawal等人于1993年首先提出的，最近幾年在數(shù)據(jù)挖掘研究領(lǐng)域?qū)﹃P(guān)聯(lián)規(guī)則挖掘的研究開展得比較積極和深入[1]。關(guān)聯(lián)規(guī)則挖掘是發(fā)現(xiàn)大量數(shù)據(jù)中項(xiàng)集之間有趣的關(guān)聯(lián)或相關(guān)關(guān)系。隨著大量數(shù)據(jù)不停被地收集和存儲(chǔ)，許多業(yè)界人士

3、對(duì)于從數(shù)據(jù)庫(kù)中挖掘關(guān)聯(lián)規(guī)則越來(lái)越感興趣。2Apriori算法2.1關(guān)聯(lián)規(guī)則挖掘問(wèn)題的形式化描述對(duì)于經(jīng)常使用的數(shù)據(jù)，同一文件的不同版本之間的內(nèi)容往往會(huì)有重復(fù)，因此數(shù)據(jù)冗余比較多，如果采用增量式壓縮就可以大大節(jié)省磁盤空間。但是這樣的數(shù)據(jù)是壓縮的，一旦用戶需要查詢/恢復(fù)數(shù)據(jù)就需要解壓過(guò)程，因此這會(huì)使系統(tǒng)性能降低。設(shè)I={i1，i2，…，im}是由m個(gè)不同的項(xiàng)目組成的集合，給定一個(gè)事務(wù)數(shù)據(jù)庫(kù)D，其中的每一個(gè)事務(wù)T是I中一組項(xiàng)目的集合，即T?I，T有一個(gè)唯一的標(biāo)識(shí)符TID。若項(xiàng)集X?I且X?T，則事務(wù)T包含項(xiàng)集X。

4、一條相聯(lián)規(guī)則就是形如X?Y的蘊(yùn)涵式，其中X?I，Y?I，x∩Y=Φ。相聯(lián)規(guī)則X?Y成立的條件是:(l)它具有支持度s，即事務(wù)數(shù)據(jù)庫(kù)D中至少有s%的事務(wù)包含XY∪；(2)它具有置信度c，即在事務(wù)數(shù)據(jù)庫(kù)D中包含X的事務(wù)至少有c%同時(shí)也包含Y。關(guān)聯(lián)規(guī)則的挖掘問(wèn)題就是在事務(wù)數(shù)據(jù)庫(kù)D中找出具有用戶給定的最小支持度minsup和最小置信度minconf的關(guān)聯(lián)規(guī)則。2.2Apriori算法簡(jiǎn)介1994年，RakeshAgrawalRama和KrishnanSkrikant首先提出了Apriori算法[2]，它是一種最有

5、影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法，其核心是使用候選項(xiàng)集找頻繁項(xiàng)集。Apriori算法使用一種稱作逐層搜索的迭代方法k-項(xiàng)集用于搜索以(k+l)-項(xiàng)集。首先，找出頻繁1-項(xiàng)集的集合，該集合記作L1，L1用于找頻繁2-項(xiàng)集的集合L2，L2從用于找L3.如此下去，直到不能找到頻繁項(xiàng)集。3Apriori算法的改進(jìn)3.1DDApriori算法[3]從Apriori算法可以看出,對(duì)每一Ci均對(duì)數(shù)據(jù)庫(kù)掃描一次,而這時(shí)有些事務(wù)已經(jīng)對(duì)頻繁項(xiàng)集的生成不產(chǎn)生

6、作用,減少數(shù)據(jù)庫(kù)D內(nèi)不起作用的事務(wù)對(duì)于算法來(lái)說(shuō)是很有必要的,本算法的基本思想就基于此。該算法是在每次計(jì)算Ci支持記數(shù)的過(guò)程中,給不包含Ci中的任何項(xiàng)集的事務(wù)打上刪除標(biāo)記,在以后的掃描計(jì)數(shù)中不加考慮。其實(shí)在Ci掃描過(guò)數(shù)據(jù)庫(kù)后,與Ci中某一項(xiàng)集相同的事務(wù)t,如果其支持記數(shù)小于Vminsup,這一事務(wù)對(duì)后面的頻繁項(xiàng)集將不產(chǎn)生作用,因此它也可以從數(shù)據(jù)庫(kù)中刪去。本算法通過(guò)增加這一事實(shí),得出的算法比[3]中算法更有效。隨著i值的增大,刪除的事務(wù)也不斷增大,因而有效降低了候選項(xiàng)集的計(jì)數(shù)速度,提高了整個(gè)算法的效率。算法:

7、DDApriori使用根據(jù)候選生成的逐行迭代找出頻繁項(xiàng)集
輸入:事務(wù)數(shù)據(jù)庫(kù)D;最小支持記數(shù)閾值Vminsup
輸出:D中的頻繁項(xiàng)集L
方法:10)
L1=findfrequent1-itemsets(D);
/20)
for(i=2;Li-1≠;i++){30)

Ck=aproiri_gen(Li-1,Vminsup);
//產(chǎn)生新的候選項(xiàng)集,此函數(shù)同于Apriori算法中的函數(shù)40)

foreachtransactiont∈D{
//掃描D并計(jì)數(shù)41)



ift.delete=0thendobe

8、gin50)




Ct=subset(Ci,t);
//獲取t的子集作為候選51)



ifCt=then52)




t.delete=1
//打上刪除標(biāo)志53)



else
//對(duì)每一個(gè)Ct進(jìn)行計(jì)數(shù)并記錄內(nèi)容54)




ifCt=cthent.count++,t.text=c60)




foreachcandidatec∈Ct.70)




c.count++;71)


end80)
}81)
if