資源描述：
《基于矩陣的apriori算法的優(yōu)化》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、計(jì)算機(jī)與現(xiàn)代化2008年第l2期JISUANJIYUXIANDAIHUA總第160期文章編號(hào)：1006-2475(2008)12-0005-03基于矩陣的Apriori算法的優(yōu)化梅成，周興斌(南昌大學(xué)計(jì)算中心，江西南昌330031)摘要：在數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則挖掘是很重要的一個(gè)方面，而Aprion算法是進(jìn)行關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法。本文首先分析了經(jīng)典Apd算法，然后利用矩陣的思想對(duì)其改進(jìn)，并利用事務(wù)壓縮的思想對(duì)矩陣進(jìn)行壓縮。改進(jìn)后的算法明顯提高了Apriori算法的效率。關(guān)鍵詞：關(guān)聯(lián)規(guī)則；Aprio
2、ri算法；事務(wù)壓縮；矩陣中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：AAnImprovementofAprioriAlgorithmBasedonMatrixMEICheng，ZHOUXing—bin(ComputingCenter，NanchangUIliversity，Nanehang330031，China)Abstract：Miningassociationruleisaveryimportantfacetfordatamining．whileApriorialgorithmisclassical
3、gorithmforassoei—ationrule．ThepaperanalyzestheclassicApriorialgorithmfirst，thenmodifiesitbasedonmarxandcompassesthematrixbasedontransactioncompression．ThemodifedalgorithmobviouslyimprovestheefieeneyofApriorialgorithm．Keywords：associationrule；Aprioria
4、lgorithm；transactioncompression；matrix庫(kù)D的多次搜索來(lái)發(fā)現(xiàn)所有的頻繁項(xiàng)集在一次掃描0引·言中，就可以得到一種長(zhǎng)度的頻繁項(xiàng)集集合。首先，找近些年來(lái)數(shù)據(jù)挖掘(DataMining)已被數(shù)據(jù)庫(kù)界出頻繁1．項(xiàng)集的集合，記作L1。L1用于找頻繁2碩所廣泛研究。它具體的是指從大型數(shù)據(jù)庫(kù)或數(shù)據(jù)倉(cāng)集的集合L2，而L2用于找L3，依次類推，直到不能找?guī)熘刑崛∪藗兏信d趣的知識(shí)¨】，而數(shù)據(jù)挖掘中的一到頻繁項(xiàng)集為止。個(gè)非常重要的方法就是基于關(guān)聯(lián)規(guī)則的知識(shí)挖掘。Apfiofi算法性質(zhì)
5、口引：頻繁項(xiàng)集的所有非空子集關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)庫(kù)挖掘領(lǐng)域中較早提出的一個(gè)都必須也是頻繁的。Apfiofi算法性質(zhì)基于以下觀研究方向，目前該領(lǐng)域的新算法、新應(yīng)用層出不窮，察：根據(jù)定義，如果項(xiàng)集I不滿足最小支持度min—相關(guān)問題定義和背景也不盡相同。在關(guān)聯(lián)規(guī)則挖掘sup，則I不是頻繁的，即P(I)<(rain—sup)。如果項(xiàng)中Aori算法是比較經(jīng)典的一個(gè)算法，但Apfiofi算A添加到I，則結(jié)果項(xiàng)集I即(IuA)不可能比I更頻法也存在一些不足之處【2。繁出現(xiàn)。因此，P(IuA)也不是頻繁的，即P(
6、IuA)<(min—sup)o1Apriori算法Apfiofi算法的實(shí)現(xiàn)過(guò)程主要有連接和剪枝兩步：Apfiofi算法是1994年由R．Agrawal和R．Srikant(1)連接步。提出的。Apd算法采用一種逐層搜索的迭代方C。=I，I為事務(wù)所包含的項(xiàng)目，掃描數(shù)據(jù)庫(kù)，得到法，k一項(xiàng)集用于搜索(k+1)一項(xiàng)集。通過(guò)對(duì)事務(wù)數(shù)據(jù)頻繁1一項(xiàng)目集L，執(zhí)行連接C=L。∞L，產(chǎn)生C，掃收稿日期：2007．11．12基金項(xiàng)目：江西省科技攻關(guān)資助項(xiàng)目(S00036)作者簡(jiǎn)介：梅成(1985．)，男，江西九江人，
7、南昌大學(xué)計(jì)算中心碩士研究生，研究方向：軟件工程；周興斌(1970-)，男，江西泰和人，副教授，研究方向：軟件工程。6計(jì)算機(jī)與現(xiàn)代化2008年第l2期描數(shù)據(jù)庫(kù)，得到L2，執(zhí)行連接C，=L2∞L2，產(chǎn)生C。。101O110O如此下去，在第k遍掃描中，則是首先利用L一來(lái)生11001011成c=L∞Lk一，若C=，則算法結(jié)束，否則掃描D=(Dt,D2，?，Ds)=11l1O110100100l0數(shù)據(jù)庫(kù)得到L。001O0000(2)剪枝步。此矩陣的行表示項(xiàng)(Ij表示第j個(gè)項(xiàng))，列表示事利用Apfiod算法
8、性質(zhì)，進(jìn)行對(duì)事務(wù)的刪除，提高務(wù)(D；就表示第i個(gè)事務(wù))，如果取值為0就表示事掃描的效率。在第k遍掃描中，第一步，利用第(k一務(wù)中不含相應(yīng)的項(xiàng)，為1則表示事務(wù)中含有相應(yīng)的1)次掃描得到的Lk-1來(lái)產(chǎn)生C，首先將IJk一中前k-I項(xiàng)。項(xiàng)相同的項(xiàng)集進(jìn)行連接產(chǎn)生C，接著將連接得到的各個(gè)項(xiàng)的最小支持度計(jì)數(shù)計(jì)算如下：項(xiàng)集，若其子集Lk一不是頻繁項(xiàng)集，那么任何(k一1)min_eount(I1)=dIl+d2t+?+dst=4I>2項(xiàng)集都不可能是頻繁項(xiàng)集，則刪除，即修剪；第二步，rain_count(I2)=
