摘 要: 關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的主要技術(shù)之一,它是描述數(shù)據(jù)庫中一組數(shù)據(jù)項(xiàng)之間的某種潛在關(guān)系的規(guī)則。關(guān)聯(lián)規(guī)則挖掘算法——Apriori算法,主要過程是對(duì)頻繁項(xiàng)集的挖掘,而在對(duì)頻繁項(xiàng)集的挖掘中首先要生成候選頻繁項(xiàng)集,然后再從候選集中確定出滿足最小支持度計(jì)數(shù)的頻繁項(xiàng)集,這會(huì)耗費(fèi)大量的CPU開銷。使用垂直數(shù)據(jù)格式挖掘頻繁項(xiàng)集可避免候選項(xiàng)目集的求解。
關(guān)鍵詞: 關(guān)聯(lián)規(guī)則;Apriori算法;頻繁項(xiàng)集;垂直數(shù)據(jù)格式
通常,關(guān)聯(lián)規(guī)則挖掘是指從一個(gè)大型的數(shù)據(jù)集中發(fā)現(xiàn)有趣的關(guān)聯(lián)或相關(guān)關(guān)系,即從數(shù)據(jù)集中識(shí)別出頻繁出現(xiàn)的屬性值集(Sets of Attribute-Values),也稱為頻繁項(xiàng)集(Frequent Itemsets,簡稱頻繁集),然后再利用這些頻繁集創(chuàng)建描述關(guān)聯(lián)規(guī)則的過程。
1 關(guān)聯(lián)規(guī)則挖掘算法
關(guān)聯(lián)規(guī)則挖掘算法——Apriori算法是使用候選項(xiàng)集找頻繁項(xiàng)集的過程。
Apriori算法通過對(duì)數(shù)據(jù)庫D的多趟掃描來發(fā)現(xiàn)所有的頻繁項(xiàng)目集。在第一趟掃描數(shù)據(jù)庫時(shí),對(duì)項(xiàng)集I中的每一個(gè)數(shù)據(jù)項(xiàng)計(jì)算其支持度,確定出滿足最小支持度的頻繁1項(xiàng)集的集合L1,然后,L1用于找頻繁2項(xiàng)集的集合L2,如此下去……在后續(xù)的第k次掃描中,首先以k-1次掃描中所發(fā)現(xiàn)的含k-1個(gè)元素的頻繁項(xiàng)集的集合Lk-1為基礎(chǔ),生成所有新的候選項(xiàng)目集CK(Candidate Itemsets),即潛在的頻繁項(xiàng)目集,然后掃描數(shù)據(jù)庫D,計(jì)算這些候選項(xiàng)目集的支持度,最后從候選集CK中確定出滿足最小支持度的頻繁k項(xiàng)集的集合Lk,并將Lk作為下一次掃描的基礎(chǔ)。重復(fù)上述過程直到不再發(fā)現(xiàn)新的頻繁項(xiàng)目集[1]。
2 關(guān)聯(lián)規(guī)則算法的改進(jìn)
從Apriori算法中由k頻繁項(xiàng)集生成k+1頻繁項(xiàng)集時(shí),首先生成候選項(xiàng)目集Ck+1,該函數(shù)不僅要對(duì)k項(xiàng)集的所有符合Apriori算法條件的數(shù)據(jù)進(jìn)行交集,并且要判斷候選項(xiàng)目集的所有子集是否在k頻繁項(xiàng)集中。該函數(shù)生成的許多候選項(xiàng)目集并不是要找的頻繁項(xiàng)集,但在掃描數(shù)據(jù)庫時(shí),要記錄下這些數(shù)據(jù)的出現(xiàn)次數(shù),這會(huì)耗費(fèi)大量的CPU開銷。如果D中的事務(wù)數(shù)很大,k頻繁項(xiàng)集中項(xiàng)數(shù)很多,則侯選項(xiàng)目集的元素個(gè)數(shù)就會(huì)很大,例如2 000個(gè)頻繁1項(xiàng)集,將產(chǎn)生2 000×999/2=999 000個(gè)候選2項(xiàng)集。如此巨大數(shù)量的候選項(xiàng)目集,對(duì)它進(jìn)行出現(xiàn)次數(shù)的統(tǒng)計(jì)時(shí)開銷非常大,這也是整個(gè)算法性能優(yōu)劣的關(guān)鍵所在。
(1)使用垂直數(shù)據(jù)格式挖掘頻繁項(xiàng)集
Apriori算法是從TID項(xiàng)集格式(即{TID:itemset})的事務(wù)集挖掘頻繁模式,其中TID是事務(wù)標(biāo)識(shí)符,而itemset是事務(wù)TID中購買的商品集。這種數(shù)據(jù)格式稱作水平數(shù)據(jù)格式。另外,數(shù)據(jù)也可以用項(xiàng)-TID集格式(即{item:TID_set})表示,其中item是項(xiàng)的名稱,而TID_set是包含item事務(wù)標(biāo)識(shí)符的集合。這種格式稱作垂直數(shù)據(jù)格式。下面使用垂直數(shù)據(jù)格式進(jìn)行有效的挖掘頻繁項(xiàng)集。
首先,通過掃描一次數(shù)據(jù)庫D,在求頻繁l項(xiàng)集的同時(shí),把數(shù)據(jù)由水平格式轉(zhuǎn)化為垂直格式,即記錄下每個(gè)項(xiàng)集在事務(wù)數(shù)據(jù)庫中出現(xiàn)時(shí)該條數(shù)據(jù)在數(shù)據(jù)庫D中的TID號(hào),則項(xiàng)集的支持度計(jì)數(shù)直接是項(xiàng)集的TID集的長度。從k=2開始,根據(jù)Apriori性質(zhì)中相交條件的項(xiàng)集進(jìn)行Apriroi連接運(yùn)算,使用頻繁k項(xiàng)集來構(gòu)造候選k+1項(xiàng)集。通過取頻繁k項(xiàng)集的TID集的交計(jì)算對(duì)應(yīng)的k+1項(xiàng)集的TID集。如果該TID集的長度大于最小支持度計(jì)數(shù),則該記錄為頻繁項(xiàng)集。重復(fù)該過程,每次k值增加1,直到不能再找到頻繁項(xiàng)集或候選項(xiàng)集。
通過挖掘可以驗(yàn)證最終得到的頻繁項(xiàng)集和用Apriori算法得到的結(jié)果是相同的[2-3]。
3 改進(jìn)算法的分析
理論上,改進(jìn)算法應(yīng)快于算法Apriori,原因如下:
(1)該算法不用求候選頻繁項(xiàng)集,從而省去了項(xiàng)集進(jìn)行連接步以后對(duì)該項(xiàng)集所有子集的判斷,這會(huì)節(jié)省大量
的CPU開銷,尤其是當(dāng)數(shù)據(jù)庫D中的數(shù)據(jù)比較多,同時(shí)候選項(xiàng)集比較多時(shí),例如頻繁1項(xiàng)集2 000個(gè),根據(jù)Apriori性質(zhì),則候選頻繁1項(xiàng)集要有2 000×999/2=999 000個(gè),但其中也許只有少數(shù)是要找的頻繁2項(xiàng)集。Apriori算法要求其中所有999 000個(gè)在數(shù)據(jù)庫中的頻繁度。
(2) 除了由頻繁k項(xiàng)集產(chǎn)生候選k+1項(xiàng)集時(shí)利用Apriori性質(zhì)之外,這種方法的另一優(yōu)點(diǎn)是不需要掃描數(shù)據(jù)庫來確定k+1項(xiàng)集(k≥1)的支持度。這是因?yàn)槊總€(gè)k項(xiàng)集的TID集攜帶了計(jì)算該支持度所需的完整信息。
該算法的缺點(diǎn)是TID集可能很長,長集合不僅需要大量空間,而且求交運(yùn)算需要大量計(jì)算時(shí)間。
參考文獻(xiàn)
[1] 韓家煒. 數(shù)據(jù)挖掘概念與技術(shù)[M].北京:機(jī)械工業(yè)出版社,2000.
[2] 陸楠.關(guān)聯(lián)規(guī)則的挖掘及其算法的研究[D]. 長春:吉林大學(xué),2007.
[3] 羅可,張學(xué)茂. 一種高效的頻集挖掘算法[J]. 長沙理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2006,3(3):84-90.
[4] 汪光一. 關(guān)聯(lián)規(guī)則挖掘算法的研究[D]. 北京:北京交通大學(xué),2007.
[5] 高峰,謝劍英. 發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的增量式更新算法[J].計(jì)算機(jī)工程,2000(12):49-50.
[6] KANTARDZIC M(美).數(shù)據(jù)挖掘-概念、模型、方法和算法[M]. 北京:清華大學(xué)出版社,2003.