曾令偉　王冬　吳蔣

摘要：Apriori算法是數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則的經(jīng)典算法，該文首先分析算法的基本思想，然后，在c語(yǔ)言環(huán)境中實(shí)現(xiàn)得出結(jié)果。

關(guān)鍵詞：Apriori算法；C語(yǔ)言；數(shù)據(jù)挖掘

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044(2012)36-8692-03

關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘的目的是在一個(gè)數(shù)據(jù)集中找出項(xiàng)與項(xiàng)之間的關(guān)系，也稱之為購(gòu)物藍(lán)分析 (market basketanalysis)[1]。例如，購(gòu)買(mǎi)上衣的顧客，有30%的可能也會(huì)買(mǎi)褲子，50%的買(mǎi)牛奶的顧客，也會(huì)買(mǎi)面包。關(guān)聯(lián)規(guī)則的應(yīng)用場(chǎng)合：在保險(xiǎn)業(yè)務(wù)方面，如果出現(xiàn)了不常見(jiàn)的索賠要求組合，則可能為欺詐，需要作進(jìn)一步的調(diào)查；在商業(yè)銷售上，關(guān)聯(lián)規(guī)則可用于交叉銷售，以得到更大的收入；在醫(yī)療方面，可找出可能的治療組合；在銀行方面，對(duì)顧客進(jìn)行分析，可以推薦感興趣的服務(wù)等等。Apriori 算法是關(guān)聯(lián)規(guī)則里一項(xiàng)經(jīng)典算法，由Rakesh Agrawal 在 1994年提出[2]。

1 關(guān)聯(lián)規(guī)則的概念

聯(lián)規(guī)則挖掘可以發(fā)現(xiàn)存在于數(shù)據(jù)庫(kù)中的項(xiàng)目或?qū)傩蚤g的有趣關(guān)系，這些關(guān)系是預(yù)先未知的或者被隱藏的。下面用事務(wù)數(shù)據(jù)庫(kù)來(lái)定義關(guān)聯(lián)規(guī)則。

設(shè)交易(transaction) 的集合，，這里交易是項(xiàng)的集合，可以表述為：并且。中的元素稱為項(xiàng)。對(duì)應(yīng)每一個(gè)交易有唯一的標(biāo)識(shí)，如交易號(hào)，記作。設(shè)是數(shù)據(jù)集中所有項(xiàng)的集合，是二進(jìn)制文字的集合。中的任何子集稱為項(xiàng)目集(itemset)，若，則稱集合為項(xiàng)集。設(shè)和分別為中的事務(wù)和項(xiàng)目集，如果，稱事務(wù)包含項(xiàng)目集。項(xiàng)目集的支持率,若不小于用戶指定的最小支持率(記作：minsupport)，則稱為頻繁項(xiàng)目集，否則稱為非頻繁項(xiàng)目集。設(shè)，是數(shù)據(jù)集中的項(xiàng)目集。若，則；若，如果是非頻繁項(xiàng)目集，則也是非頻繁項(xiàng)目集；若，如果是頻繁項(xiàng)目集，則也是頻繁項(xiàng)目集[3]。

一個(gè)關(guān)聯(lián)規(guī)則是形如的蘊(yùn)涵式，這里，都是項(xiàng)目集，且，，并且，，分別稱為關(guān)聯(lián)規(guī)則的前提和結(jié)論[4]。一般使用支持度（support）和置信度（confidence）兩個(gè)參數(shù)來(lái)描述關(guān)聯(lián)規(guī)則的屬性。

給定一個(gè)事務(wù)集，挖掘關(guān)聯(lián)規(guī)則的問(wèn)題就是產(chǎn)生支持度和置信度分別大于用戶事先給定的最小支持度和最小置信度的關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則挖掘的任務(wù)就是要挖掘出中所有的強(qiáng)規(guī)則。強(qiáng)規(guī)則對(duì)應(yīng)的項(xiàng)目集必定是頻繁項(xiàng)目集，頻繁項(xiàng)目集導(dǎo)出的關(guān)聯(lián)規(guī)則的置信度可由頻繁項(xiàng)目集和的支持度計(jì)算[4]。

3.2算法步驟

1）首先單趟掃描數(shù)據(jù)集，計(jì)算各個(gè)一項(xiàng)集的支持度，根據(jù)給定的最小支持度閾值，得到一項(xiàng)頻繁集L1。

2）然后通過(guò)連接運(yùn)算，得到二項(xiàng)候選集，對(duì)每個(gè)候選集再次掃描數(shù)據(jù)集，得出每個(gè)候選集的支持度，再與最小支持度比較。得到二項(xiàng)頻繁集L2。

3）如此進(jìn)行下去，直到不能連接產(chǎn)生新的候選集為止。

4）對(duì)于找到的所有頻繁集，用規(guī)則提取算法進(jìn)行關(guān)聯(lián)規(guī)則的提取。

3.3 算法的流程圖

參考文獻(xiàn):

[1] Han Jiawei,Kamber M.數(shù)據(jù)挖掘：概念與技術(shù)[M].范明,譯.北京:機(jī)械工業(yè)出版社,2008.

[2] 陳京民.數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘技術(shù)[M].北京:北京電子工業(yè)出版社,2007.

[3] Cabena P.Discovering Data Mining From Concept to Implementation[Z].IBM,2009.

[4] 李緒成,王保保.挖掘關(guān)聯(lián)規(guī)則中Apriori算法的一種改進(jìn)[J].計(jì)算機(jī)工程,2010, 28(7).

[5] 顏雪松,蔡之華.一種基于Apriori的高效關(guān)聯(lián)規(guī)則挖掘算法的研究[J].計(jì)算機(jī)工程與應(yīng)用,2012(10).

[6] 張瑞雪.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則算法研究及應(yīng)用[D]. 哈爾濱:哈爾濱工程大學(xué),2006.

[7] 姚琛. 數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則更新算法的研究[D]. 長(zhǎng)春:吉林大學(xué),2005.

[8] 唐文志. 蟻群算法在關(guān)聯(lián)規(guī)則學(xué)習(xí)中的研究與應(yīng)用[D]. 北京:北京工業(yè)大學(xué), 2009.

[9] Apriori算法簡(jiǎn)介[EB/OL]. [2012-06-12].http://blog.csdn.net/qq675927952/article/details/6707704.

[10] 關(guān)聯(lián)規(guī)則挖掘-Apriori算法筆記 [EB/OL]. [2011-05-31].http://www.shamoxia.com/html/y2010/2280.html.