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