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