關(guān)聯(lián)規則算法的實(shí)現與優(yōu)化

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