關(guān)聯(lián)規(guī)則挖掘技術(shù)在零售業(yè)中的應(yīng)用

[摘 要] 簡(jiǎn)要地介紹數(shù)據(jù)挖掘和關(guān)聯(lián)規(guī)則的概念，關(guān)聯(lián)規(guī)則的基本理論，討論了Apriori算法的核心內(nèi)容，同時(shí)針對(duì)Apriori算法的不足，提出了解決方法，描述了幾種優(yōu)化算法。最后分析了關(guān)聯(lián)規(guī)則挖掘在零售業(yè)中的應(yīng)用。

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

數(shù)據(jù)挖掘就是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識(shí)的過(guò)程。人工智能領(lǐng)域習(xí)慣稱知識(shí)發(fā)現(xiàn)，而數(shù)據(jù)庫(kù)領(lǐng)域習(xí)慣稱數(shù)據(jù)挖掘。

由于條形碼技術(shù)的發(fā)展，零售部門可以利用前端收款機(jī)收集交易數(shù)據(jù)，并把這些數(shù)據(jù)存儲(chǔ)在后臺(tái)海量數(shù)據(jù)庫(kù)中。如果對(duì)這些歷史數(shù)據(jù)進(jìn)行分析，從中獲得顧客購(gòu)買行為特征，對(duì)商家來(lái)說(shuō)是極有價(jià)值的信息。這些信息有助于規(guī)劃市場(chǎng)、合理安排貨架等。Agrawal針對(duì)大型超市的銷售數(shù)據(jù)庫(kù)建立了關(guān)聯(lián)規(guī)則模型和數(shù)據(jù)挖掘算法。

一、關(guān)聯(lián)規(guī)則的基本理論

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

關(guān)聯(lián)規(guī)則是形如XY的邏輯蘊(yùn)含式，其中XI，YI，且X⌒Y=φ。如果事務(wù)數(shù)據(jù)庫(kù)D中有要s%的事務(wù)包含XY，則稱關(guān)聯(lián)規(guī)則XY的支持度為s%，實(shí)際上，支持度是一個(gè)概率值。若項(xiàng)集X的支持度記為sup port(X)，規(guī)則的信任度為sup port(XY)/sup port(X)。這是一個(gè)條件概率P(Y/Y)。也就是:

sup port(XY)=P(XY)

confidence(XY)=P(Y/Y)

關(guān)聯(lián)規(guī)則就是支持度和信任度分別滿足用戶給定閾值的規(guī)則。發(fā)現(xiàn)關(guān)聯(lián)規(guī)則需要經(jīng)歷如下兩個(gè)步驟:

1.找出所有頻繁項(xiàng)集。

2.由頻繁項(xiàng)集生成滿足最小信任度閾值的規(guī)則。

二、關(guān)聯(lián)規(guī)則的挖掘算法

1.Apriori算法

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

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

通過(guò)已知的頻繁項(xiàng)集構(gòu)成長(zhǎng)度更大的項(xiàng)集，并將其稱為潛在頻繁項(xiàng)集。潛在頻繁k項(xiàng)集的集合Ck是指由有可能成為頻繁k項(xiàng)集的項(xiàng)集組成的集合。以后只需計(jì)算潛在頻繁項(xiàng)集的支持度，而不必計(jì)算所有不同項(xiàng)集的支持度，因此在一定程度上減少了計(jì)算量。具體的實(shí)現(xiàn)過(guò)程為:

(1)通過(guò)單趟掃描數(shù)據(jù)庫(kù)D計(jì)算出各個(gè)1項(xiàng)集的支持度，從而得到頻繁1項(xiàng)集構(gòu)成的集合L1。

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

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

(4)通過(guò)單趟掃描數(shù)據(jù)庫(kù)D，計(jì)算Ck中各個(gè)項(xiàng)集的支持度。

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

通過(guò)迭代循環(huán)，重復(fù)上述步驟(2)～(5)，直到不能產(chǎn)生新的頻繁項(xiàng)集的集合(非空集合)時(shí)為止，Apriori 算法求出所有滿足最小支持度的頻繁項(xiàng)集。

2.Apriori 算法的優(yōu)化

雖然Apriori算法本身已經(jīng)進(jìn)行了一定的優(yōu)化，但是一方面由于對(duì)海量數(shù)據(jù)庫(kù)的多趟掃描，另一方面用JOIN產(chǎn)生潛在頻繁項(xiàng)集。仍存在一些不足。目前許多專家學(xué)者通過(guò)大量的研究工作，提出了一些優(yōu)化的算法以提高Apriori的效率。

(1)基于哈希表技術(shù)

Park等人提出把哈希表結(jié)構(gòu)用于關(guān)聯(lián)規(guī)則挖掘，在掃描數(shù)據(jù)庫(kù)中的事務(wù)用以生成頻繁k項(xiàng)集的同時(shí)，可以從事務(wù)中生成所有的(k+1)項(xiàng)集，并將其用Hash函數(shù)映射到哈希表結(jié)構(gòu)中，同時(shí)增加相應(yīng)的桶計(jì)數(shù)。該趟掃描結(jié)束時(shí)，將桶計(jì)數(shù)低于支持度閾值的項(xiàng)集從潛在頻繁項(xiàng)集中刪除。實(shí)質(zhì)上是在生成潛在頻繁項(xiàng)集時(shí)完成剪枝工作。算法核心是通過(guò)改變數(shù)據(jù)結(jié)構(gòu)來(lái)增加關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)效率。

(2)事務(wù)壓縮技術(shù)

Agrawal等提出壓縮進(jìn)一步迭代掃描的事務(wù)數(shù)據(jù)的方法。因?yàn)椴话魏蝛項(xiàng)集的事務(wù)，不可能包含任何(k+1)項(xiàng)集，可對(duì)這些事務(wù)加上刪除標(biāo)志，掃描數(shù)據(jù)庫(kù)時(shí)不再考慮。若一個(gè)事物不包含任何k項(xiàng)集，則該事物包含的項(xiàng)數(shù)必定小于k，同時(shí)必小于(k+1)，則該事物不會(huì)包含在任何(k+2)項(xiàng)集中。由此在掃描事務(wù)數(shù)據(jù)庫(kù)產(chǎn)生I項(xiàng)集之前，先把該事物刪除以提高掃描效率，在以后的操作中則不需要該事物。

(3)雜湊技術(shù)

一個(gè)高效地產(chǎn)生頻集的基于雜湊的算法由Park等提出。通過(guò)實(shí)驗(yàn)我們可以發(fā)現(xiàn)尋找頻集主要的計(jì)算是在生成頻繁2-項(xiàng)集Lk上，Park等就是利用了這個(gè)性質(zhì)引入雜湊技術(shù)來(lái)改進(jìn)產(chǎn)生頻繁2-項(xiàng)集的方法。

(4)劃分技術(shù)

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

(5)抽樣技術(shù)

基本思想是在給定數(shù)據(jù)的一個(gè)子集挖掘。對(duì)前一遍掃描得到的信息，仔細(xì)地組合分析，可以得到一個(gè)改進(jìn)的算法，Mannila等先考慮了這一點(diǎn)，他們認(rèn)為采樣是發(fā)現(xiàn)規(guī)則的一個(gè)有效途徑。隨后又由Toivonen進(jìn)一步發(fā)展了這個(gè)思想，先使用從數(shù)據(jù)庫(kù)中抽取出來(lái)的采樣得到一些在整個(gè)數(shù)據(jù)庫(kù)中可能成立的規(guī)則，然后對(duì)數(shù)據(jù)庫(kù)的剩余部分驗(yàn)證這個(gè)結(jié)果。

(6)動(dòng)態(tài)項(xiàng)集計(jì)數(shù)

Brin等人采用動(dòng)態(tài)項(xiàng)集計(jì)數(shù)方法求解頻繁項(xiàng)集。首先把數(shù)據(jù)庫(kù)分成若干個(gè)塊，并在每個(gè)塊的起始點(diǎn)加上標(biāo)記。然后用到目前標(biāo)記為止的計(jì)數(shù)信息動(dòng)態(tài)地估計(jì)所有項(xiàng)集的支持度，如果所有子集均估計(jì)為頻繁的，則將該項(xiàng)集加入潛在頻繁項(xiàng)集中，從而形成與Apriori算法不同的生成潛在頻繁項(xiàng)集的方法。

三、關(guān)聯(lián)規(guī)則挖掘的應(yīng)用

在零售業(yè)，數(shù)據(jù)挖掘可有助于識(shí)別顧客購(gòu)買行為，發(fā)現(xiàn)顧客購(gòu)買模式和趨勢(shì)，改進(jìn)服務(wù)質(zhì)量，取得更好的顧客保持力和滿意程度，提高貨品銷量比率，設(shè)計(jì)更好的貨品運(yùn)輸與分銷策略，減少商業(yè)成本。

下面給出一個(gè)某超市顧客購(gòu)買商品的事務(wù)數(shù)據(jù)庫(kù)中的數(shù)據(jù)，說(shuō)明關(guān)聯(lián)規(guī)則對(duì)商品銷售數(shù)據(jù)的挖掘過(guò)程，通過(guò)挖掘發(fā)現(xiàn)顧客的購(gòu)買習(xí)慣和偏好。

某超市對(duì)一定時(shí)期內(nèi)顧客購(gòu)買商品的數(shù)據(jù)收集如下:

數(shù)據(jù)挖掘過(guò)程如下:

第一步，計(jì)算出表中每種商品的關(guān)聯(lián)規(guī)則支持度，根據(jù)定義，計(jì)算出

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%

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

第三步，計(jì)算商品的關(guān)聯(lián)規(guī)則信任度。

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

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

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

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

為了簡(jiǎn)便，其余數(shù)據(jù)通過(guò)X=>Y的信任度表表示如下

第四步，根據(jù)設(shè)定的最小信任度閥值，設(shè)最小信任度閥值為0.6，得到如下規(guī)則:

第五步，根據(jù)上述關(guān)聯(lián)規(guī)則，可以發(fā)現(xiàn)超市顧客的購(gòu)買習(xí)慣和偏好，銷售管理人員可采取如下措施:一是調(diào)整貨架，將商品帽子、圍巾統(tǒng)一放置在一起，便于顧客選購(gòu)，甚至可考慮將商品帽子、圍巾和手套，商品棉衣和手套捆綁銷售;二是在進(jìn)貨或倉(cāng)儲(chǔ)方面，可考慮將關(guān)聯(lián)商品統(tǒng)購(gòu)統(tǒng)存;三是印發(fā)關(guān)聯(lián)商品的促銷廣告，提高商品的支持度和信任度;四是在企業(yè)網(wǎng)絡(luò)銷售中，應(yīng)將關(guān)聯(lián)商品放在同一頁(yè)面或增加關(guān)聯(lián)商品間的鏈接。在采取以上措施后，超市可以擴(kuò)大銷售額，提高了服務(wù)水平，顧客可以擴(kuò)大交叉購(gòu)買，增加消費(fèi)。

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

上述銷售管理的數(shù)據(jù)挖掘，可應(yīng)用于商品批零業(yè)和大型超市等商業(yè)企業(yè)中。為更好地滿足客戶需求，通過(guò)對(duì)商品數(shù)據(jù)的挖掘，發(fā)現(xiàn)商品之間的關(guān)聯(lián)特征，在有效利用企業(yè)有限資源的基礎(chǔ)上，采取相應(yīng)的銷售策略，既能夠提高企業(yè)的服務(wù)水平，提高客戶滿意度，又能夠節(jié)約企業(yè)資源，利用最小的投入，獲得到較大的收益。在信息時(shí)代，對(duì)提高企業(yè)的競(jìng)爭(zhēng)力，更好地應(yīng)對(duì)機(jī)遇和挑戰(zhàn)具有重要作用和意義。

參考文獻(xiàn):

[1]李雄飛 李 軍:數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)[M].北京:高等教育出版社，2003

[2]安淑芝等:數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘[M].北京:清華大學(xué)出版社，2005 .6