關(guān)聯(lián)規(guī)則挖掘算法探討

摘要：關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘領(lǐng)域的重要課題之一，本文對(duì)數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則挖掘算法進(jìn)行研究，總結(jié)出算法的性能缺陷，展望了關(guān)聯(lián)規(guī)則挖掘的未來發(fā)展方向。

關(guān)鍵詞：數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；Apriori算法

1、引言

在數(shù)據(jù)挖掘所有的知識(shí)模式中，關(guān)聯(lián)規(guī)則模式是非常重要的一種，也是最活躍的一個(gè)分支。采用關(guān)聯(lián)模型比較經(jīng)典的例子是“啤酒和尿布”的案例，在美國(guó)，一些年輕的父親下班后經(jīng)常到超市去買嬰兒尿布，超市經(jīng)過對(duì)顧客的購(gòu)物信息進(jìn)行挖掘，發(fā)現(xiàn)在購(gòu)買嬰兒尿布的年輕父親中，有30％-40％的人同時(shí)要買一些啤酒。超市隨后調(diào)整了貨架的擺放，把尿布和啤酒放在一起。結(jié)果是銷售額明顯增加了。這一案例中的關(guān)聯(lián)規(guī)則可以表示為：購(gòu)買了項(xiàng)目A和B的顧客中有某一百分比的人又買了C和D。從這些規(guī)則可找出顧客購(gòu)買行為模式，從而應(yīng)用于商品貨架設(shè)計(jì)、生產(chǎn)安排、針對(duì)性的市場(chǎng)營(yíng)銷等。

2、相關(guān)概念

定義2.1 關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘的數(shù)據(jù)集記為D（一般為事務(wù)數(shù)據(jù)庫(kù)）， ={t1，t2，…，tk,，…，tn}, tk= {i1，i2，…，ip，…，im}, tk (k=1，2，…，n)稱為事務(wù)，ip (p=1，2，…，m)稱為項(xiàng)目。

定義2.2 設(shè)I={i1，i2，…，im}是D中全體項(xiàng)目組成的集合，I的任何子集A稱為D中的項(xiàng)目集,A=Ｋ稱集合A為K項(xiàng)目集。設(shè)tk和A分別為Ｄ中的事務(wù)和項(xiàng)目集，如果Ａ?坳tk，則稱事務(wù)tk包含項(xiàng)目集A。每一個(gè)事務(wù)都有一個(gè)唯一的標(biāo)識(shí)符，稱為TID。

定義2.3 數(shù)據(jù)集D中包含項(xiàng)目集A的事務(wù)數(shù)稱為項(xiàng)目集A的支持?jǐn)?shù)，記為?滓?琢。項(xiàng)目集A的支持度記為：sup port(A)，及概率P(A)。

sup port(A)= ×100% （或 sup port(A)= ）

其中D是事務(wù)數(shù)據(jù)庫(kù)D的事務(wù)數(shù)，若support(A)不小于指定的最小支持度（minsupport），則稱A為頻繁項(xiàng)目集，否則稱為非頻繁項(xiàng)目集。

定義2.4 若A、B為項(xiàng)目集，且A∩B = ?準(zhǔn)，蘊(yùn)含式A?圯B稱為關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則A?圯B的支持度記作：sup port(A?圯B)

sup port(A?圯B) = sup port(A∪B) = P (A∪B)

關(guān)聯(lián)規(guī)則A?圯B的可信度為D中事務(wù)包含A的事務(wù)的同時(shí)也包含B的百分比，即條件概率P(B| A)。記作 confidence (A?圯B) = ×100%

定義2.5 若規(guī)則的可信度confidence (A?圯B)≥min confidence，且支持度sup port(A?圯B)≥min sup port，則稱關(guān)聯(lián)規(guī)則A?圯B為強(qiáng)關(guān)聯(lián)規(guī)則，否則稱為弱關(guān)聯(lián)規(guī)則。

關(guān)聯(lián)規(guī)則挖掘就是找到支持度和可信度均大于用戶指定的最小支持度和最小可信度的規(guī)則。

3、Apriori算法

Apriori算法是挖掘產(chǎn)生布爾關(guān)聯(lián)規(guī)則所需頻繁項(xiàng)集的基本算法，它是一個(gè)很有影響的關(guān)聯(lián)規(guī)則挖掘算法。Apriori算法就是根據(jù)有關(guān)頻繁項(xiàng)集特性的先驗(yàn)知識(shí)而命名的。關(guān)聯(lián)規(guī)則的挖掘可以分兩步來進(jìn)行：

（1）找出所有的頻繁項(xiàng)集：根據(jù)前面定義，這些項(xiàng)集出現(xiàn)的頻率不小于預(yù)先定義的最小支持度。

（2）由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則：根據(jù)前面定義，這些規(guī)則的支持度和可信度不小于最小支持度與最小可信度。這兩步中，第二步比較容易，挖掘關(guān)聯(lián)規(guī)則的總體性能主要是由第一步?jīng)Q定。

Apriori算法主要就是基于第一步中的操作處理。它是R.Agrawal和R.Srikan提出的布爾關(guān)聯(lián)規(guī)則挖掘頻繁項(xiàng)集的原創(chuàng)性算法。

算法步驟如下：

第一步：初始化數(shù)據(jù)庫(kù)，根據(jù)條件初始化數(shù)據(jù)庫(kù)，掃描事務(wù)數(shù)據(jù)庫(kù)，從中找出所有的項(xiàng)集長(zhǎng)度為k=l的項(xiàng)集，形成候選1項(xiàng)集C1,得出每項(xiàng)的支持度，跟最小支持度進(jìn)行比較，支持度大于minsupport，形成頻繁1項(xiàng)集L1；

第二步：根據(jù)頻繁k項(xiàng)集產(chǎn)生候選（k+1）項(xiàng)候選項(xiàng)集Ck+1，如果Ck+1≠?準(zhǔn)進(jìn)入下一步，否則循環(huán)結(jié)束；

第三步：掃描數(shù)據(jù)庫(kù)，以確定每個(gè)候選項(xiàng)集的支持度；

第四步：刪除候選項(xiàng)中支持度小于minsupport的候選項(xiàng)，形成（k+1）項(xiàng)頻繁項(xiàng)集Lk+1；

第五步：k=k+1，轉(zhuǎn)入第二步；

第六步：由得到的所有頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則。

4、算法性能缺陷

第一個(gè)缺陷是在多次掃描事務(wù)數(shù)據(jù)庫(kù)D的項(xiàng)目集時(shí)，需要很大的I/O時(shí)空開銷。對(duì)于每次k循環(huán)，候選項(xiàng)目集Ck中的每個(gè)元素都必須通過全部掃描事務(wù)集數(shù)據(jù)庫(kù)D一次來計(jì)算其支持度，因此產(chǎn)生巨大的I/O時(shí)空開銷。

第二個(gè)缺陷是可能產(chǎn)生非常龐大的候選項(xiàng)目集。由Lk-1產(chǎn)生候選項(xiàng)目集Ck是指數(shù)增長(zhǎng)的，產(chǎn)生如此多的候選項(xiàng)目集對(duì)執(zhí)行時(shí)間和內(nèi)存空間都將是一種嚴(yán)峻的挑戰(zhàn)。

第三個(gè)缺陷是現(xiàn)有關(guān)聯(lián)規(guī)則挖掘算法主要是基于“可信度-支持度”的結(jié)構(gòu)。在實(shí)際應(yīng)用中，僅僅考慮可信度和支持度是遠(yuǎn)遠(yuǎn)不夠的，容易產(chǎn)生誤導(dǎo)，挖掘出沒有實(shí)際意義的規(guī)則。

第四個(gè)缺陷是關(guān)聯(lián)規(guī)則挖掘算法忽視了反面事例的情況。舉例說明：我們無(wú)法挖掘出“交易記錄中56%買了咖啡不買奶粉，買了咖啡的人中不買奶粉的可能性為40%”，C代表咖啡，M代表奶粉，則規(guī)則c?圯M的支持度為56%，可信度為40%。這條規(guī)則在現(xiàn)實(shí)中很可能存在，并且對(duì)商家來說也是一條有用的信息，但是Apriori算法并不能挖掘出這些有用的反面規(guī)則。

5、發(fā)展方向

關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘中一個(gè)非?；钴S的研究領(lǐng)域，國(guó)內(nèi)外在關(guān)聯(lián)規(guī)則挖掘方面的研究也已經(jīng)取得了很大的進(jìn)步，但關(guān)聯(lián)規(guī)則挖掘技術(shù)在有些方面仍然存在著不足，需要進(jìn)一步研究和改進(jìn)。

（1）增強(qiáng)與用戶的交互性

目前關(guān)聯(lián)規(guī)則的衡量方法主要是基于支持度——可信度的標(biāo)準(zhǔn)，事先定義好最小支持度和最小可信度，然后通過掃描數(shù)據(jù)集找出所有的頻繁項(xiàng)目集，并根據(jù)頻繁項(xiàng)目集生成關(guān)聯(lián)規(guī)則，最后將挖掘出的關(guān)聯(lián)規(guī)則提交給用戶。如果結(jié)果不符合用戶的需求，則需要修改最小支持度、最小可信度等，并再次運(yùn)行關(guān)聯(lián)規(guī)則挖掘算法，用戶要得到滿意的結(jié)果可能需要上述過程的多次反復(fù)，因此需要較長(zhǎng)時(shí)間。如何增強(qiáng)關(guān)聯(lián)規(guī)則挖掘算法與用戶的交互性，是以后的一個(gè)重點(diǎn)研究方向。

（2）提高挖掘的效率

數(shù)據(jù)庫(kù)的規(guī)模不斷增大，不僅加大了挖掘算法的搜索空間，而且也增加了盲目挖掘的可能性。為了保證數(shù)據(jù)挖掘算法的高效性，并且能從大量數(shù)據(jù)中提煉有用信息，算法的運(yùn)行時(shí)間一定是可預(yù)測(cè)的和能夠接受的。因此必須結(jié)合相關(guān)領(lǐng)域知識(shí)，去提取與我們發(fā)現(xiàn)任務(wù)有關(guān)的數(shù)據(jù)，刪除無(wú)用的數(shù)據(jù)，有效地降低問題的維數(shù)，提高挖掘算法的效率。

（3）融合其它技術(shù)

許多其它領(lǐng)域的研究者從事關(guān)聯(lián)規(guī)則問題的研究，使得關(guān)聯(lián)規(guī)則挖掘可以吸收其它領(lǐng)域的研究成果。如關(guān)聯(lián)規(guī)則挖掘技術(shù)與數(shù)據(jù)立方、數(shù)據(jù)倉(cāng)庫(kù)等數(shù)據(jù)庫(kù)技術(shù)的融合將推動(dòng)關(guān)聯(lián)規(guī)則挖掘技術(shù)進(jìn)一步實(shí)用化，關(guān)聯(lián)規(guī)則與其它技術(shù)的進(jìn)一步深入結(jié)合，將可以提高其應(yīng)用能力和挖掘效率。

（4）可視化挖掘技術(shù)

數(shù)據(jù)挖掘技術(shù)本身具有一定的復(fù)雜性，除了專業(yè)人員以外一般用戶很難掌握，用戶很難理解得到的結(jié)果。圖形和圖像的表現(xiàn)方式，用戶更加容易理解和接受，可視化數(shù)據(jù)挖掘技術(shù)（VDM）正在興起，如何將可視化技術(shù)應(yīng)用于數(shù)據(jù)挖掘是今后的一個(gè)研究重點(diǎn)。

6、結(jié)束語(yǔ)

數(shù)據(jù)挖掘仍然是一個(gè)不斷發(fā)展的技術(shù)，因此，關(guān)聯(lián)規(guī)則挖掘技術(shù)的發(fā)展也從未停止，隨著新的情況的出現(xiàn)，關(guān)聯(lián)規(guī)則技術(shù)的應(yīng)用將更加廣泛，其在未來還有很大的發(fā)展空間。

參考文獻(xiàn)

[1] Jiawei Han，Micheline Kamber.數(shù)據(jù)挖掘概念與技術(shù)【M】.機(jī)械工業(yè)出版社，2007

[2] 許婭.關(guān)聯(lián)規(guī)則更新算法研究與應(yīng)用[D].合肥工業(yè)大學(xué)，2009.5

作者簡(jiǎn)介：

趙晨（1982-），西安電子科技大學(xué)在讀研究生，講師，工作單位：陜西交通職業(yè)技術(shù)學(xué)院，從事計(jì)算機(jī)專業(yè)教學(xué)工作與研究。