基于十字鏈表的Apriori算法的實現(xiàn)

宋廣佳，張艷明

（黑龍江中醫(yī)藥大學(xué) 現(xiàn)代教育技術(shù)與信息中心，黑龍江 哈爾濱 150040）

基于十字鏈表的Apriori算法的實現(xiàn)

宋廣佳，張艷明

（黑龍江中醫(yī)藥大學(xué) 現(xiàn)代教育技術(shù)與信息中心，黑龍江 哈爾濱 150040）

針對A p r i o r i算法的若干不足，如需要多次連接數(shù)據(jù)庫，多次掃描事務(wù)記錄，在剪枝步驟比對次數(shù)過多等缺點，文章實現(xiàn)了把數(shù)據(jù)庫映射到十字鏈表的方法，并且與傳統(tǒng)A p r i o r i算法進行了對比，實驗表明十字鏈表的方法可以大幅度減少數(shù)據(jù)挖掘所需時間，可明顯減少連接及掃描數(shù)據(jù)庫次數(shù)，減少剪枝步驟對比次數(shù)，提升算法執(zhí)行效率.

關(guān)聯(lián)規(guī)則；Apriori；十字鏈表；數(shù)據(jù)挖掘

1 介紹

數(shù)據(jù)挖掘也稱為知識發(fā)現(xiàn)，是當(dāng)今數(shù)據(jù)庫研究中的技術(shù)熱點.發(fā)現(xiàn)關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的主要目的，關(guān)聯(lián)規(guī)則是指在大型事務(wù)或關(guān)系數(shù)據(jù)集中各個項之間的有趣關(guān)聯(lián)或相關(guān).例如可以通過“購物籃”中不同的商品去分析顧客的購物習(xí)慣.目前關(guān)聯(lián)規(guī)則廣發(fā)的應(yīng)用于醫(yī)療保健、電子商務(wù)、金融證券及生物基因分析等領(lǐng)域.A p r i o r i算法是RA g r a w a l和R S r i k a n t于1994年提出的關(guān)聯(lián)規(guī)則挖掘的原創(chuàng)性算法[1,2].算法的基本思想如下：頻繁項集的任何子集也一定是頻繁的.其中頻繁項集是指滿足最小支持度的項目集合，比如{A B}是頻繁的，則{A}和{B}也一定是頻繁的.基于以上原理，A p r i o r i算法使用逐層搜索的迭代方法，用K項集去搜索K+1項集[8].

1.2 A p r i o r i算法步驟如下

（1）首先掃描原始數(shù)據(jù)庫D B，生成頻繁一項集L 1

（2）連接步：L k-1通過自身連接產(chǎn)生候選k項集C k

（3）剪枝步：根據(jù)A p r i o r i性質(zhì)，掃描數(shù)據(jù)庫D B，對每個候選項集進行計數(shù)，將支持度小于給定閾值的候選項去掉，從而確定L k.

以上（2），（3）步驟循環(huán)，直到新產(chǎn)生的L k為空為止[3].

1.3 A p r i o r i算法的不足

通過對算法的分析可以發(fā)現(xiàn)算法存在很多不足：

（1）算法需要掃描數(shù)據(jù)庫多次

（2）生成的候選集巨大，而其中很對候選項對于生成頻繁集無用，同時時間耗費巨大.

針對（1）可將原始數(shù)據(jù)庫轉(zhuǎn)化為某種內(nèi)存中的某種數(shù)據(jù)結(jié)構(gòu)，這樣再算法運行時只需掃描數(shù)據(jù)庫一次.常見的轉(zhuǎn)換方式有將原始數(shù)據(jù)庫轉(zhuǎn)換為十字鏈表[4]，轉(zhuǎn)換為圖，轉(zhuǎn)換為向量，轉(zhuǎn)換為矩陣等等[5,6,7,9].針對（2）可采用候選樹分割的方法將時間上的耗費部分轉(zhuǎn)移到空間上去，即采用空間換時間的方法.

2 十字鏈表方法

2.1 將事務(wù)數(shù)據(jù)庫轉(zhuǎn)換為十字鏈表

事務(wù)T={t i|1<=i<=n},n為事務(wù)的長度，且事務(wù)中各項按字典有序.如有如下事務(wù)數(shù)據(jù)庫D B，則采用圖1所示的節(jié)點結(jié)構(gòu)可將其轉(zhuǎn)化為如下形式

表1

十字鏈表節(jié)點數(shù)據(jù)結(jié)構(gòu)

表2

其中：I t e m表示項目名稱，N u m b e r表示該項目到事務(wù)末尾的長度，D o w n是指向下一個事務(wù)中此項的指針，R i g h t是指向同一事務(wù)中下一項的指針.事務(wù)數(shù)據(jù)庫D B的十字鏈表表示如下：

2.2 十字鏈表的特性

性質(zhì)1：如果事務(wù)T中的項與C j[1]匹配成功，且此項的N u m b e r值小于k，則該事務(wù)T對產(chǎn)生頻繁項集無用.

圖1

性質(zhì)2：候選k-項集中的任意項集C i與十字鏈表中的事務(wù)匹配時，假設(shè)C i[j]與十字鏈表中某事務(wù)T中的項t匹配成功，C i[j+1]與t的下一項匹配時，如果此項按字典順序在C i[j+1]之后則停止匹配，此事務(wù)對C i的支持度計數(shù)沒有影響[4].

如果給定支持度為M i n S u p，算法描述如下：(1)掃描十字鏈表生成頻繁一項集L 1. (2)如果L k-1非空，連接L k-1生成C k.

(3)在候選集C k中，沿十字鏈表的I t e m表頭搜索，將c i[1]與I t e m表頭中節(jié)點進行匹配，直到匹配成功為止.

(4)在I t e m表頭中，沿匹配成功節(jié)點的d o w n向下域搜索.根據(jù)性質(zhì)1，判斷指向的節(jié)點的N u m b e r域，如果n u m b e r=k則沿此節(jié)點的r i g h t指針進行k項集匹配.

(5)在匹配過程中如果項集c i已經(jīng)與事務(wù)t的前j項匹配成功，在進行j+1項匹配時如果按字典順序c i[j+1]在事務(wù)t進行匹配的項之后，則根據(jù)性質(zhì)3，停止匹配，否則如果一直匹配成功則c i的支持度計數(shù)加1.

(6)如果c i的支持度不小于M i n S u p則將其添加到L k中.

(7)去下一個c i，繼續(xù)重復(fù)(3)~(6)直到C k中所有的k項集全部掃描結(jié)束為止.

(8)輸出頻繁項集L k，轉(zhuǎn)至(2).

3 十字鏈表的VB實現(xiàn)

3.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計

轉(zhuǎn)換之后的十字鏈表有三種結(jié)構(gòu)的節(jié)點，一種為左側(cè)垂直的T i d事務(wù)標(biāo)識頭表，一種為上部水平的I t e m項目頭表，最后一種為剩余的普通節(jié)點.定義這三種節(jié)點的數(shù)據(jù)結(jié)構(gòu)如下：

以事務(wù)數(shù)據(jù)庫T以文件方式存儲為例，為將事務(wù)數(shù)據(jù)庫T轉(zhuǎn)換為十字鏈表，編寫了如下四個過程：

生成I t e m項目表頭：C r e a t e I t e m H e a d(D B N a m e)

生成T i d事務(wù)標(biāo)識表頭：C r e a t e T i d H e a d(D BN a m e)生成十字鏈表普通節(jié)點：C r e a t e N o d e(D B N a m e)完成所有節(jié)點的d o w n指針及r i g h t指針：F u l l N o d e()

調(diào)用以上四個過程可以生成完整的十字鏈表，然后掃描十字鏈表生成頻繁一項集L 1，代碼如下：

M i n S u p=2'最小支持度

通過L k-1的自身連接可以生成C k，對C k中的項進行支持度計數(shù)是A p r i o r i算法中耗費時間較多的步驟，因為理論上檢查每個c i的支持度計數(shù)都要掃描整個事務(wù)數(shù)據(jù)庫，但在十字鏈表中根據(jù)性質(zhì)1和性質(zhì)2，對候選集C k進行A p r i o r i性質(zhì)檢查的步驟可以快速的進行，實現(xiàn)的代碼如下：

圖2

E n dS u b

與傳統(tǒng)A p r i o r i算法進行對比實驗，實驗環(huán)境為：C P U為I n t e l Q 8300，內(nèi)存d d r 28002 G B，操作系統(tǒng)為w i n d o w sX PS P 3，數(shù)據(jù)庫采用T 40 I 10 D 100 K，支持度15%.算法執(zhí)行時間對比如下：

結(jié)果分析：從曲線上來看，十字鏈表方法的執(zhí)行時間明顯少于傳統(tǒng)A p r i o r i算法，拋物線上升趨勢上也比傳統(tǒng)A p r i o r i算法平緩的多，從時間對比上來看，執(zhí)行之間要比S Q L方法提升了至少25%.

本文用V B語言以十字鏈表數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)實現(xiàn)了A p r i o r i算法，通過實驗分析表明：通過轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)可以減少連接數(shù)據(jù)庫次數(shù)及I/O操作，利用十字鏈表的特性額可以有效地減少掃描數(shù)據(jù)庫次數(shù)，從而使數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘的時間大幅減少.

〔1〕Agrawal R,Imielinski T,Swami A.Mining Association Rules Between Sets of Items in Large Database[C].Proceedings of the ACM SIGMOD Conference on Managementof Data.Wasington,USA.1993

〔2〕Agrawal R,Srikant R Fast Algotihms for mining Association Rules[C].In Proc 1994 Int Conf Very Large Data Base Santiago,Chile.1994.

〔3〕于衛(wèi)紅.用VB對基于Apriori算法的數(shù)據(jù)挖掘的實現(xiàn)[J].計算機工程，2004，30(2):196-197.

〔4〕黃建明，趙文靜，王星星.基于十字鏈表的Apriori改進算法 [J].計算機工程，2009，30(2):37-38,41.

〔5〕白似雪，朱濤，梅君.基于圖的Apriori改進算法[J].南昌大學(xué)學(xué)報，2009，30(1):36-39.

〔6〕方煒煒，楊炳儒，宋威，侯偉.基于布爾矩陣的關(guān)聯(lián)規(guī)則算法研究 [J].計算機應(yīng)用研究，2008，25 (7):1964-1966.

〔7〕劉江華，戴新喜，白似雪.基于模式矩陣的P_Ma

trix算法[J].南昌大學(xué)學(xué)報，2007,31(5):496-499.

〔8〕JiaWeiHan,Michline Kamber.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機械工業(yè)出版社，2008.

〔9〕李超,余昭平.基于矩陣的Apriori算法改進[J].計算機工程，2006，32(23):68-69.

〔10〕YanbinYe,Chia-ChuChiang.A Parallel Apriori Algorithm for Frequent Itemsets Mining [C].Proceedings of the Fourth InternationalConference on software Engineering Research, Management and Applications, SERA 2006,p 87-94.

T P 311.13

A

1673-260 X（2012）09-0032-03