關聯規則挖掘算法探討

摘要：關聯規則挖掘是數據挖掘領域的重要課題之一，本文對數據挖掘中的關聯規則挖掘算法進行研究，總結出算法的性能缺陷，展望了關聯規則挖掘的未來發展方向。

關鍵詞：數據挖掘；關聯規則；Apriori算法

1、引言

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

2、相關概念

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

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

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

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

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

定義2.4 若A、B為項目集，且A∩B = ?準，蘊含式A?圯B稱為關聯規則。關聯規則A?圯B的支持度記作：sup port(A?圯B)

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

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

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

關聯規則挖掘就是找到支持度和可信度均大于用戶指定的最小支持度和最小可信度的規則。

3、Apriori算法

Apriori算法是挖掘產生布爾關聯規則所需頻繁項集的基本算法，它是一個很有影響的關聯規則挖掘算法。Apriori算法就是根據有關頻繁項集特性的先驗知識而命名的。關聯規則的挖掘可以分兩步來進行：

（1）找出所有的頻繁項集：根據前面定義，這些項集出現的頻率不小于預先定義的最小支持度。

（2）由頻繁項集產生強關聯規則：根據前面定義，這些規則的支持度和可信度不小于最小支持度與最小可信度。這兩步中，第二步比較容易，挖掘關聯規則的總體性能主要是由第一步決定。

Apriori算法主要就是基于第一步中的操作處理。它是R.Agrawal和R.Srikan提出的布爾關聯規則挖掘頻繁項集的原創性算法。

算法步驟如下：

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

第二步：根據頻繁k項集產生候選（k+1）項候選項集Ck+1，如果Ck+1≠?準進入下一步，否則循環結束；

第三步：掃描數據庫，以確定每個候選項集的支持度；

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

第五步：k=k+1，轉入第二步；

第六步：由得到的所有頻繁項集產生強關聯規則。

4、算法性能缺陷

第一個缺陷是在多次掃描事務數據庫D的項目集時，需要很大的I/O時空開銷。對于每次k循環，候選項目集Ck中的每個元素都必須通過全部掃描事務集數據庫D一次來計算其支持度，因此產生巨大的I/O時空開銷。

第二個缺陷是可能產生非常龐大的候選項目集。由Lk-1產生候選項目集Ck是指數增長的，產生如此多的候選項目集對執行時間和內存空間都將是一種嚴峻的挑戰。

第三個缺陷是現有關聯規則挖掘算法主要是基于“可信度-支持度”的結構。在實際應用中，僅僅考慮可信度和支持度是遠遠不夠的，容易產生誤導，挖掘出沒有實際意義的規則。

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

5、發展方向

關聯規則是數據挖掘中一個非常活躍的研究領域，國內外在關聯規則挖掘方面的研究也已經取得了很大的進步，但關聯規則挖掘技術在有些方面仍然存在著不足，需要進一步研究和改進。

（1）增強與用戶的交互性

目前關聯規則的衡量方法主要是基于支持度——可信度的標準，事先定義好最小支持度和最小可信度，然后通過掃描數據集找出所有的頻繁項目集，并根據頻繁項目集生成關聯規則，最后將挖掘出的關聯規則提交給用戶。如果結果不符合用戶的需求，則需要修改最小支持度、最小可信度等，并再次運行關聯規則挖掘算法，用戶要得到滿意的結果可能需要上述過程的多次反復，因此需要較長時間。如何增強關聯規則挖掘算法與用戶的交互性，是以后的一個重點研究方向。

（2）提高挖掘的效率

數據庫的規模不斷增大，不僅加大了挖掘算法的搜索空間，而且也增加了盲目挖掘的可能性。為了保證數據挖掘算法的高效性，并且能從大量數據中提煉有用信息，算法的運行時間一定是可預測的和能夠接受的。因此必須結合相關領域知識，去提取與我們發現任務有關的數據，刪除無用的數據，有效地降低問題的維數，提高挖掘算法的效率。

（3）融合其它技術

許多其它領域的研究者從事關聯規則問題的研究，使得關聯規則挖掘可以吸收其它領域的研究成果。如關聯規則挖掘技術與數據立方、數據倉庫等數據庫技術的融合將推動關聯規則挖掘技術進一步實用化，關聯規則與其它技術的進一步深入結合，將可以提高其應用能力和挖掘效率。

（4）可視化挖掘技術

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

6、結束語

數據挖掘仍然是一個不斷發展的技術，因此，關聯規則挖掘技術的發展也從未停止，隨著新的情況的出現，關聯規則技術的應用將更加廣泛，其在未來還有很大的發展空間。

參考文獻

[1] Jiawei Han，Micheline Kamber.數據挖掘概念與技術【M】.機械工業出版社，2007

[2] 許婭.關聯規則更新算法研究與應用[D].合肥工業大學，2009.5

作者簡介：

趙晨（1982-），西安電子科技大學在讀研究生，講師，工作單位：陜西交通職業技術學院，從事計算機專業教學工作與研究。