ISSN 1002 - 4956實驗技術(shù)與管理第29卷第8期2012年8月CN11- 2034/TExperimental Technology and ManagementVol.29 No.8 Aug. 2012關(guān)聯(lián)規(guī)則算法的實現(xiàn)與優(yōu)化王晶'，趙志強2(1. 首都醫(yī)科大學(xué)科技處，北京10069;2. 首都醫(yī)科大學(xué)后勤集團，北京100069>摘要:對基于關(guān)聯(lián)規(guī)則的 數(shù)據(jù)挖掘算法進行了研究,對經(jīng)典的頻繁項集計數(shù)算法進行了改進.提高了關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘的效率。優(yōu)化結(jié)果證明了關(guān)聯(lián)規(guī)則算法在醫(yī)學(xué)科研實驗室數(shù)據(jù)挖掘中的重要作用。關(guān)鍵詞:關(guān)聯(lián)規(guī)則;算法優(yōu)化;數(shù)據(jù)挖掘中圖分類號: TP311.13文獻標(biāo)志碼: A文章 編號: 1002- 4956(2012)08- 0111 02.Implementation and optimization of algorithm of data miningassociation rules of data miningWang Jing'，Zhao Zhiqiang2(1. Office of Science and Technology, Capital Medical University, Beiing 10069, China;2. Logistics Service Group, Capital Medical University, Beijing 100069, China)Ahbstraet: This article analyses the algorithn to raise the asciation rules of data mining, and improves theclassic algorithm for Frequent Item Set Counting to raise the eficiecg of data mining. The opimized resultsshow that the algorithm of associaion rules of data mining in medical research laboratory has very importantrole.Key words: association rules; algorithm optimication; data mining本文對基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法進行了研I。稱事務(wù)T支持物品集X，如果XCT,關(guān)聯(lián)規(guī)則是究,分析了頻繁項目生成算法規(guī)則,包括對經(jīng)典算法如下形式的一種蘊含:X→Y,其中xC1,YC1,且x∩Apriori'I的設(shè)計與實現(xiàn)、分析與改進，以提高算法Y=φ。效率。(1)稱物品集X具有大小為s的支持度,如果D .中有s%的事務(wù)支持物品集x;1關(guān)聯(lián)規(guī)則挖掘定 義及形式(2)稱關(guān)聯(lián)規(guī)則X- +Y在事務(wù)數(shù)據(jù)庫D中具有大考察一些涉及許多物品的事務(wù):事務(wù)1中出現(xiàn)了小為s的支持度，如果物品集X∪Y的支持度為s;物品甲,事務(wù)2中出現(xiàn)了物品乙,事務(wù)3中則同時出現(xiàn).(3)稱規(guī)則x→Y在事務(wù)數(shù)據(jù)庫D中具有大小為了物品甲和乙。那么，物品甲和乙在事務(wù)中的出現(xiàn)相s的可信度,如果D中支持物品集X的事務(wù)中有c%互之間是否有規(guī)律可循呢?在數(shù)據(jù)庫的數(shù)據(jù)挖掘中，的事務(wù)同時也支持物品集Y。關(guān)聯(lián)規(guī)則就是描述這種在-個事務(wù)中物品之間同時出2 Apriori 算法現(xiàn)的規(guī)律的知識模式。更確切地說,關(guān)聯(lián)規(guī)則通過量化的數(shù)字描述物品甲的出現(xiàn)對物品乙的出現(xiàn)有多大的在基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)庫挖掘技術(shù)中，頻繁項目影響。集的計算問題(frequent item set counting, FIC) 是制設(shè)I= {i,iz, ..n. )是一組物品集(一個商場的約數(shù)據(jù)挖掘效率的關(guān)鍵。當(dāng)事務(wù)數(shù)據(jù)庫和所包含的項物品可能有上萬種),D是一組事務(wù)集(稱之為事務(wù)數(shù)目的數(shù)量很大時,頻繁項集的數(shù)目也會變得非常大,導(dǎo)據(jù)庫)。D中的每個事務(wù)T是一組物品,顯然滿足rS致頻繁項集計數(shù)問題所花費的時間代價很高。Aprio-ri算法采用中國煤化工，是解決FIC問收稿日期:2012- 01-27題的有效的作者簡介:王晶(1980-),女,山西晉城，工學(xué)碩士.助理研究員。從事科2.1算法思JYHCNMHG研信息管理及計算機技術(shù)應(yīng)用.主要用于關(guān)聯(lián)規(guī)則挖掘,即在交易數(shù)據(jù)、關(guān)系數(shù)據(jù)E-mail: wanging@ cmu. edu. cn或其他信息載體中,查找存在于項目集合或?qū)ο蠹?12實驗技術(shù)與管理之間的頻繁模式、關(guān)聯(lián)、相關(guān)性或因果結(jié)構(gòu)。其基本思3算法優(yōu)化想[27是:頻繁項集的任何子集也一定是頻繁的。所謂頻繁集是指滿足最小支持度的項目集合,如果{AB)是(1)從邏輯上把數(shù)據(jù)庫分成幾個互不相交的塊，頻繁集,則(A},{B}也-定是頻繁集。得到頻繁項集每次單獨考慮一個分塊并對它生成所有的頻集,然后后,便可產(chǎn)生基于該頻繁集的強關(guān)聯(lián)規(guī)則。合并產(chǎn)生的頻集生成所有可能頻集,最后計算這些項主要使用逐層搜索的迭代方法,即探索K項集來集的支持度[7。這里分塊的大小選擇要使每個分塊可產(chǎn)生(K+1)-集,并用數(shù)據(jù)庫掃描和模式匹配計算候放人主存,每個階段只需被掃描一次[8]。而算法的正選集的支持度”。首先,找出頻繁1-項集的集合。該確性是由每.-一個可能的頻集至少在某一-個分塊中是頻集合記作L1. L1用于找頻繁2-項集的集合,而L2用集保證[9的。于找L3 ,如此下去,直到不能找到頻繁K-項集。(2)基于前一遍掃描得到的信息進行組合分析，Apriori算法基于以下性質(zhì)來有效減少候選項目得到一個改進的算法[10 ,即在計算K-項集時，如果認(rèn)集數(shù)目:一個K-項集是頻繁項目集(1,當(dāng)且僅當(dāng)其所為某個(K + 1)項集可能是頻集時,就并行地計算這個有的(K-1)子項集是頻繁的。但在計算候選項集的(K+1)項集的支持度,這樣需要的總的掃描次數(shù)通常支持率方面仍然存在一些問題,在第K輪的遞推中，少 于最大的頻集的項數(shù)11]。數(shù)據(jù)庫中的每個事務(wù)t的所有K階子項集都要判斷(3)動態(tài)地評估已被計數(shù)的所有項集,可以避免其是否在K階候選項集中。為了降低這個過程的復(fù)僅在每次完整的數(shù)據(jù)庫掃描之前確定新的候選,它可雜性,其采用T Hash Tree和Hash Table表技術(shù)。但以在任何點添加，一旦一個項集的所有子集被確定為當(dāng)K較小時,該技術(shù)效果不理想。而K較小時(K-<是頻繁的，就可以啟動對該項集支持度的計算1[12]。因4)算法的計算量可占到執(zhí)行時間的90%以上。此所需的數(shù)據(jù)庫掃描次數(shù)要比原算法要少。2.2算法設(shè)計與實現(xiàn)改進后的算法較原算法在時間和空間上都有了明Apriori算法的實現(xiàn)過程分為2步:一為連接,二顯的提高。為剪枝。該算法基于一個頻繁項集中任一子 集也應(yīng)該參考文獻( References)是頻繁項集的性質(zhì),使用一種逐層搜索的迭代方法[5]，K-項集用于(K+1)項集。其算法流程如下:首先遍歷[1]柴華昕,干勇. Apriori挖掘頻繁項月集算法的改進[J].計算機工程目標(biāo)數(shù)據(jù)庫一次,記錄每個項目或?qū)傩缘某霈F(xiàn)次數(shù),即與應(yīng)用，2007(24):24-26.計算每個項目的支持度,收集所有支持度不低于用戶[2]謝宗毅.關(guān)聯(lián)規(guī)則挖掘Apriori算法的研究與改進[J].杭州電子科技大學(xué)學(xué)報,2006 ,23(3) :78-82.最小支持度的項目構(gòu)成頻繁1-項集L1,然后鏈接L1[3]錢少華,蔡勇,錢雪忠.基于數(shù)組的Apriori算法的改進[J].計算機中所有的元素形成候選2項集C2,再次遍歷事務(wù)數(shù)據(jù)應(yīng)用與軟件，2006 ,23(2)44-46.庫,計算C2中每個候選2項集的支持度,收集所有支[4]程玉勝,鄧小光，江效堯. Apriori算法中頻繁項集挖摑實現(xiàn)研究持度不低于用戶最小支持度的項目構(gòu)成頻繁2-項集J].計算機技術(shù)與發(fā)展，2006,16(3):58- 60.L2,再鏈接L2形成C3,遍歷數(shù)據(jù)庫得L3,反復(fù)執(zhí)行以[5]郭健美,宋順林?；贏priori算法的改進算法[J].計算機工程與.設(shè)計，2008.29<11).2814-2820.上過程，直到?jīng)]有候選項集為止。[6]張梅峰,張建偉。基于Apriori的有效關(guān)聯(lián)規(guī)則挖掘算法的研究首先在程序中用SQL語句生成了項集LI,即:[].計算機工程與應(yīng)用，2003.39<19);196-198.create tablel l(tl char(5) ,tcount integer)其中,tl表示[7]袁萬蓮,鄭誠、翟明清.一種改進的Apriori算法[J].計算機技術(shù)與項集中的每一項,tcount表示該項的支持度計數(shù)。掃發(fā)展,2008,18(5) :51-53.描表cP的tlist字段,根據(jù)該字段的存儲特點,需要將[8] J衛(wèi)平.關(guān)聯(lián)規(guī)則挖抿Apriori算法的改進及其應(yīng)用研究[J].南通大學(xué)學(xué)報,2008,7(1);50-53.tlist 字段各分量中以逗號分隔的數(shù)字取出并且通過模[9]何小東,劉衛(wèi)國.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則挖掘算法比較研究[J].計算式匹配統(tǒng)計它們的個數(shù),取消重復(fù)后分別存放到LI表機工程與設(shè)計.2005 ,26<5):1265-1267.的tl和tcount字段中。[10]王創(chuàng)新.關(guān)聯(lián)規(guī)則提取中對Apriori 算法的一種改進[J].計算機再逐層搜索迭代生成頻繁候選K-項集LK,根據(jù)工程與應(yīng)用,2004,40(34) :183-185.Apriori算法的思想，可以循環(huán)生成頻繁K-項集,若生[11]安建成,劉超惠.頻繁項集快速挖掘及更新算法[J].微電子學(xué)與計算機,2008,25(6);132-136.成的K項集為空集,則算法結(jié)束,K-I項集便是所求[12]吳偉平，中國煤化工關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法[J].的頻繁項集0]。計算機工YHCNMHG運用上述方法,得到頻繁項集后，即可產(chǎn)生關(guān)聯(lián)規(guī)則。由此我們可以實現(xiàn)算法。