關聯規則挖掘技術在零售業中的應用

[摘 要] 簡要地介紹數據挖掘和關聯規則的概念，關聯規則的基本理論，討論了Apriori算法的核心內容，同時針對Apriori算法的不足，提出了解決方法，描述了幾種優化算法。最后分析了關聯規則挖掘在零售業中的應用。

[關鍵詞] 關聯規則 數據挖掘 Apriori 算法

數據挖掘就是從大量的、不完全的、有噪聲的、模糊的、隨機的數據中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。人工智能領域習慣稱知識發現，而數據庫領域習慣稱數據挖掘。

由于條形碼技術的發展，零售部門可以利用前端收款機收集交易數據，并把這些數據存儲在后臺海量數據庫中。如果對這些歷史數據進行分析，從中獲得顧客購買行為特征，對商家來說是極有價值的信息。這些信息有助于規劃市場、合理安排貨架等。Agrawal針對大型超市的銷售數據庫建立了關聯規則模型和數據挖掘算法。

一、關聯規則的基本理論

設I={i1，i2，…，im}為所有項目的集合，D為事務數據庫，事務 T是一個項目子集(TT)。每一個事務具有惟一的事務標識Tid。設A是一個由項目構成的集合，稱為項集。事務T包含項集A，當且僅當AT。如果項集A中包含k個項目，則稱其為k項集。項集A在事務數據庫D中出現的次數占D中總事務的百分比叫做項集的支持度。如果項集的支持度超過用戶給定的最小支持度閾值，就稱該項集是頻繁項集(或大項集)。

關聯規則是形如XY的邏輯蘊含式，其中XI，YI，且X⌒Y=φ。如果事務數據庫D中有要s%的事務包含XY，則稱關聯規則XY的支持度為s%，實際上，支持度是一個概率值。若項集X的支持度記為sup port(X)，規則的信任度為sup port(XY)/sup port(X)。這是一個條件概率P(Y/Y)。也就是:

sup port(XY)=P(XY)

confidence(XY)=P(Y/Y)

關聯規則就是支持度和信任度分別滿足用戶給定閾值的規則。發現關聯規則需要經歷如下兩個步驟:

1.找出所有頻繁項集。

2.由頻繁項集生成滿足最小信任度閾值的規則。

二、關聯規則的挖掘算法

1.Apriori算法

Apriori算法在發現關聯規則領域具有很大影響力。算法命名源于算法使用了頻繁項集性質的先驗(Prior)知識。在具體實現時，Apriori算法將發現關聯規則的過程分為兩個步驟:第一步通過迭代，檢索出事務數據庫中的所有頻繁項集，即支持度不低于用戶設定的閾值的項集;第二步利用頻繁項集構造出滿足用戶最小信任度的規則。其中，挖掘或識別出所有頻繁項集是該算法的核心，占整個計算量的大部分。

由m個項目形成的不同項集的數目可以達到2m-1個，尤其在海量數據庫D中，這是一個NP難度的問題。為了避免計算所有項集的支持度(實際上頻繁項集只占很少一部分)，Apriori算法引入潛在頻繁項集的概念。若潛在頻繁k項集的集合記為Ck，頻繁k項集的集合記為Lk，m個項目構成的k項集的集合為Ckm，則三者之間滿足關系LkCkCkm。構成潛在頻繁項集所遵循的原則是“頻繁項集的子集必為頻繁項集”。

通過已知的頻繁項集構成長度更大的項集，并將其稱為潛在頻繁項集。潛在頻繁k項集的集合Ck是指由有可能成為頻繁k項集的項集組成的集合。以后只需計算潛在頻繁項集的支持度，而不必計算所有不同項集的支持度，因此在一定程度上減少了計算量。具體的實現過程為:

(1)通過單趟掃描數據庫D計算出各個1項集的支持度，從而得到頻繁1項集構成的集合L1。

(2)連接步:為了產生頻繁k項集構成的集合Lk，預先生成一個潛在頻繁k項集的集合Ck。潛在頻繁項集的集合由JOIN運算得到。若p，q∈Lk-1，P{p1，p2，…，pk-2，pk-1}，q={q1，q2，…，pk-2，pk-1，qk-1}，并且當1≤i≤k-1時，pi=qi，當i=k-1時，pk-1≠qk-1，則pq={p1，p2，…，pk-2，pk-1，qk-1}是潛在頻繁k項集的集合Ck中的元素。這里的潛在頻繁k項集的集合Ck是指由有可能成為頻繁k項集的項集組成的集合。

(3)剪枝步:由于Ck是Lk的超集，可能有些元素不是頻繁的。Ck很龐大時會帶來巨大的計算量，為減少Ck的規模，Apriori遵從下列性質:任何非頻繁的(k-1)項集必定不是頻繁k項集的子集。所以，當潛在k項集的某個(k-1)子集不是Lk-1中的成員時，則該潛在頻繁項集不可能是頻繁的，可以從Ck中移去，這就是Apriori剪枝思想。

(4)通過單趟掃描數據庫D，計算Ck中各個項集的支持度。

(5)將Ck中不滿足最小支持度的項集剔除，形成由頻繁k項集構成的集合Lk。

通過迭代循環，重復上述步驟(2)～(5)，直到不能產生新的頻繁項集的集合(非空集合)時為止，Apriori 算法求出所有滿足最小支持度的頻繁項集。

2.Apriori 算法的優化

雖然Apriori算法本身已經進行了一定的優化，但是一方面由于對海量數據庫的多趟掃描，另一方面用JOIN產生潛在頻繁項集。仍存在一些不足。目前許多專家學者通過大量的研究工作，提出了一些優化的算法以提高Apriori的效率。

(1)基于哈希表技術

Park等人提出把哈希表結構用于關聯規則挖掘，在掃描數據庫中的事務用以生成頻繁k項集的同時，可以從事務中生成所有的(k+1)項集，并將其用Hash函數映射到哈希表結構中，同時增加相應的桶計數。該趟掃描結束時，將桶計數低于支持度閾值的項集從潛在頻繁項集中刪除。實質上是在生成潛在頻繁項集時完成剪枝工作。算法核心是通過改變數據結構來增加關聯規則的發現效率。

(2)事務壓縮技術

Agrawal等提出壓縮進一步迭代掃描的事務數據的方法。因為不包含任何k項集的事務，不可能包含任何(k+1)項集，可對這些事務加上刪除標志，掃描數據庫時不再考慮。若一個事物不包含任何k項集，則該事物包含的項數必定小于k，同時必小于(k+1)，則該事物不會包含在任何(k+2)項集中。由此在掃描事務數據庫產生I項集之前，先把該事物刪除以提高掃描效率，在以后的操作中則不需要該事物。

(3)雜湊技術

一個高效地產生頻集的基于雜湊的算法由Park等提出。通過實驗我們可以發現尋找頻集主要的計算是在生成頻繁2-項集Lk上，Park等就是利用了這個性質引入雜湊技術來改進產生頻繁2-項集的方法。

(4)劃分技術

Savasere等設計了一個基于劃分的算法，這個算法先把數據庫從邏輯上分成幾個互不相交的塊，每次單獨考慮一個分塊并對它生成所有的頻集，然后把產生的頻集合并，用來生成所有可能的頻集，最后計算這些項集的支持度。這里分塊的大小選擇要使得每個分塊可以被放入主存，每個階段只需被掃描一次。而算法的正確性是由每一個可能的頻集至少在某一個分塊中是頻集保證的。

(5)抽樣技術

基本思想是在給定數據的一個子集挖掘。對前一遍掃描得到的信息，仔細地組合分析，可以得到一個改進的算法，Mannila等先考慮了這一點，他們認為采樣是發現規則的一個有效途徑。隨后又由Toivonen進一步發展了這個思想，先使用從數據庫中抽取出來的采樣得到一些在整個數據庫中可能成立的規則，然后對數據庫的剩余部分驗證這個結果。

(6)動態項集計數

Brin等人采用動態項集計數方法求解頻繁項集。首先把數據庫分成若干個塊，并在每個塊的起始點加上標記。然后用到目前標記為止的計數信息動態地估計所有項集的支持度，如果所有子集均估計為頻繁的，則將該項集加入潛在頻繁項集中，從而形成與Apriori算法不同的生成潛在頻繁項集的方法。

三、關聯規則挖掘的應用

在零售業，數據挖掘可有助于識別顧客購買行為，發現顧客購買模式和趨勢，改進服務質量，取得更好的顧客保持力和滿意程度，提高貨品銷量比率，設計更好的貨品運輸與分銷策略，減少商業成本。

下面給出一個某超市顧客購買商品的事務數據庫中的數據，說明關聯規則對商品銷售數據的挖掘過程，通過挖掘發現顧客的購買習慣和偏好。

某超市對一定時期內顧客購買商品的數據收集如下:

數據挖掘過程如下:

第一步，計算出表中每種商品的關聯規則支持度，根據定義，計算出

Support(棉衣)=2/5=0.4=40%

Support(帽子)=3/5=0.6=60%

Support(圍巾)=3/5=0.6=60%

Support(手套)=3/5=0.6=60%

Support(毛巾)=1/5=0.2=20%

Support(毛毯)=1/5=0.2=20%

第二步，根據設定的最小支持度閥值，將大于或等于最小支持度閥值的商品挑選出來，設最小支持度閥值為0.3，可挑選出商品棉衣、帽子、圍巾和手套。

第三步，計算商品的關聯規則信任度。

根據定義，計算出棉衣、帽子、圍巾和手套四種商品的信任度。

Confidence(棉衣=>帽子)= Support(棉衣=>帽子)/ Support(棉衣)=20%/40%=0.5;

Confidence(棉衣=>圍巾)=Support(棉衣=>圍巾) / Support(棉衣)= 20%/40%=0.5;

Confidence(棉衣=>手套)=Support(棉衣=>手套) / Support(棉衣)= 40%/40%=1，說明該規則有100%的情況是成立的。

為了簡便，其余數據通過X=>Y的信任度表表示如下

第四步，根據設定的最小信任度閥值，設最小信任度閥值為0.6，得到如下規則:

第五步，根據上述關聯規則，可以發現超市顧客的購買習慣和偏好，銷售管理人員可采取如下措施:一是調整貨架，將商品帽子、圍巾統一放置在一起，便于顧客選購，甚至可考慮將商品帽子、圍巾和手套，商品棉衣和手套捆綁銷售;二是在進貨或倉儲方面，可考慮將關聯商品統購統存;三是印發關聯商品的促銷廣告，提高商品的支持度和信任度;四是在企業網絡銷售中，應將關聯商品放在同一頁面或增加關聯商品間的鏈接。在采取以上措施后，超市可以擴大銷售額，提高了服務水平，顧客可以擴大交叉購買，增加消費。

通常關聯規則挖掘普遍使用“支持度——信任度”度量機制，但需要注意的是，在實際應用中，不加額外的限制條件會產生大量的規則。這些規則并不是對用戶都是有用的或感興趣的。衡量關聯規則挖掘結果的有效性應該從多種綜合角度來考慮。一是準確性:挖掘出的規則必須反映數據的實際情況。盡管規則不可能是100%適用。二是實用性:挖掘出的規則必須是簡潔可用的，而且是針對挖掘目標的。不能是有100條規則，其中50條與商業目標無關，30條用戶無法理解。三是新穎性:挖掘出的規則可以為用戶提供新的有價值信息。但如果它們是用戶事先知道的，那么這樣的規則即使再正確也是毫無價值的。

上述銷售管理的數據挖掘，可應用于商品批零業和大型超市等商業企業中。為更好地滿足客戶需求，通過對商品數據的挖掘，發現商品之間的關聯特征，在有效利用企業有限資源的基礎上，采取相應的銷售策略，既能夠提高企業的服務水平，提高客戶滿意度，又能夠節約企業資源，利用最小的投入，獲得到較大的收益。在信息時代，對提高企業的競爭力，更好地應對機遇和挑戰具有重要作用和意義。

參考文獻:

[1]李雄飛 李 軍:數據挖掘與知識發現[M].北京:高等教育出版社，2003

[2]安淑芝等:數據倉庫與數據挖掘[M].北京:清華大學出版社，2005 .6