基于矩陣相乘的Apriori改進(jìn)算法

《基于矩陣相乘的Apriori改進(jìn)算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、計(jì)算機(jī)科學(xué)2005Vo1.32N4.7(增刊1i)基于矩陣相乘的Apriori改進(jìn)算法關(guān)ImprovedAprioriAlgorithmBasedonMatrixMultiplying高明劉希玉盛立(山東師范大學(xué)信息管理學(xué)院濟(jì)南250010AbstractThispaperpresentsanimprovedApriorialgorithm(MM一Apriori)basedonmatrixmultiply.Thenewal-gorithmiscomparedwithApriori切theexperiment,andshowsthatthealgorithmoutperformApriori

2、.KeywordsDatamining,Associationrules,Frequentitems,Matrix由于第二步比較簡(jiǎn)單，因此關(guān)聯(lián)規(guī)則挖掘的研1引言究主要集中在第一步，即從交易數(shù)據(jù)庫(kù)中找出符合數(shù)據(jù)挖掘(DataMining)，也稱(chēng)數(shù)據(jù)庫(kù)中知識(shí)發(fā)指定支持度和置信度條件的所有頻繁項(xiàng)集。目前最現(xiàn)KDD(KnowledgeDiscoveryinData-base)，是指有影響的關(guān)聯(lián)規(guī)則挖掘算法是Apriori算法D]，后從大量原始數(shù)據(jù)中挖掘出隱含的、有用的、尚未發(fā)現(xiàn)來(lái)的研究者也陸續(xù)提出了一些新的算法'z,81，但大的信息和知識(shí)(如知識(shí)規(guī)則、限制等)，被認(rèn)為是目多數(shù)算法還是以Aprior

3、i算法為核心，Apriori算法前解決“數(shù)據(jù)爆炸”和“數(shù)據(jù)豐富，信息貧乏(Data的思想利用了Apriori性質(zhì)，即頻繁項(xiàng)集的所有非RichandInformationPoo,ar)”的一種有效方法?？兆蛹仨氁彩穷l繁的，由k-項(xiàng)頻繁集1,*連接得關(guān)聯(lián)規(guī)則的挖掘是數(shù)據(jù)挖掘的重要領(lǐng)域之一。到k+1一項(xiàng)侯選頻繁集q十，，然后進(jìn)行修剪，過(guò)濾出隨著大型連鎖零售商店在零售市場(chǎng)上份額的增加，頻繁項(xiàng)集，直到?jīng)]有頻繁項(xiàng)集被發(fā)現(xiàn)為止。越來(lái)越多的超市或連鎖店希望發(fā)現(xiàn)其龐大的交易數(shù)2Apriori算法據(jù)庫(kù)中隱含的銷(xiāo)售信息，這是一種寶貴的信息資源，可以很好地支持人們的決策。關(guān)聯(lián)規(guī)則的應(yīng)用包括Apriori算法是關(guān)

4、聯(lián)規(guī)則挖掘的經(jīng)典算法，算法商場(chǎng)的顧客購(gòu)物分析、商品廣告郵寄分析、網(wǎng)絡(luò)故障通過(guò)多次掃描數(shù)據(jù)集挖掘頻繁項(xiàng)集。第一次掃描，分析等。關(guān)聯(lián)規(guī)則的挖掘引起了研究人員與企業(yè)界算法對(duì)所有數(shù)據(jù)項(xiàng)進(jìn)行計(jì)數(shù)并找出所有頻繁1一項(xiàng)人士的共同關(guān)注。集。在接下來(lái)的每一遍掃描中，算法使用前一遍處關(guān)聯(lián)規(guī)則的定義可形式化描述如下:設(shè)I={il,理發(fā)現(xiàn)的頻繁項(xiàng)集生成新的候選頻繁項(xiàng)集，并通過(guò)i2I...Ii.}是所有項(xiàng)目(item)的集合，令D為一個(gè)事掃描數(shù)據(jù)庫(kù)對(duì)這些候選頻繁項(xiàng)集進(jìn)行計(jì)數(shù)，然后，使務(wù)數(shù)據(jù)庫(kù)，其中的每一個(gè)事務(wù)T都是項(xiàng)目的集合，用支持度閡值對(duì)不滿足支持度條件的候選頻繁項(xiàng)集且T=I。關(guān)聯(lián)規(guī)則是形如X=>y的蕊含式，其中

5、進(jìn)行修剪，過(guò)濾出頻繁項(xiàng)集，直到?jīng)]有頻繁項(xiàng)集被發(fā)X,Y為項(xiàng)目集合，并且Xny=必。定義支持度現(xiàn)為止。Apriori算法描述如下:(support)為D中包含XUY的百分比，置信度算法:Apriori(confidence)為D中包含X的事務(wù)同時(shí)也包含Y的輸人:事務(wù)數(shù)據(jù)庫(kù)D;最小支持度闌值minsup,百分比。即:sup(X=>Y)=P(XUY);confidence(X輸出:D中的頻繁集l,o=;>Y)=P(Y}X)。項(xiàng)的集合稱(chēng)為項(xiàng)集。包含k個(gè)方法:項(xiàng)的項(xiàng)集稱(chēng)為k一項(xiàng)集。項(xiàng)集滿足最小支持度min-1)1,1={large1一itemsets};sup，如果項(xiàng)集的出現(xiàn)頻率大于或等于minsup

6、與D2)for(k=2;1-k_1護(hù)爭(zhēng);k++)dobegin3)q=Apriori-gen(Lk_1);中事務(wù)總數(shù)的乘積。如果項(xiàng)集滿足最小支持度，則4)foralltransactionsteDdobegin稱(chēng)它為頻繁項(xiàng)集(frequentitemset)。頻繁項(xiàng)集的集5)C=subset(q，t);6)forallcandidatesc任C,do合記做Lk。7)c.count斗一+;從大型數(shù)據(jù)庫(kù)中挖掘關(guān)聯(lián)規(guī)則分為兩個(gè)步驟:8)end9)1,k={CECkIc.count>,minsup二i'1'I}1)找出所有的頻繁項(xiàng)集。10)end2)由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則。11)Answer=U

7、k1"k;，)基金項(xiàng)目:山東省自然科學(xué)基金重大項(xiàng)目(Z2004G02)，山東省中青年科學(xué)家獎(jiǎng)勵(lì)基金項(xiàng)目2003年(03BS0035),·209·其中，Apriori-gen是以頻繁(k-1)項(xiàng)目序列集(2)掃描一遍數(shù)據(jù)庫(kù)統(tǒng)計(jì)各個(gè)項(xiàng)對(duì)應(yīng)的行中ILk-,為自變量的候選項(xiàng)集生成函數(shù)。該函數(shù)分連接的個(gè)數(shù)，生成頻繁1一項(xiàng)集;和修剪兩步執(zhí)行:(3)刪除矩陣A中支持度不滿足mirisup的項(xiàng)(1)連接(join)所在的行，生成矩陣M(