基于Apriori算法的超商品銷售數(shù)據(jù)的關(guān)聯(lián)規(guī)則分析

1、基于Apriori算法的超市商品銷售數(shù)據(jù)的關(guān)聯(lián)規(guī)則分析鄭印(華中師范大學(xué)計(jì)算機(jī)學(xué)院，湖北武漢430079)AprioriassociationrulesalgorithmbasedsupermarketmerchandisesalesdataZhengyin(ComputerCollege,CentralChinaNormalUniversity,Hubei430079,China)摘要：Apriori算法廣泛應(yīng)用于商業(yè)中，應(yīng)用于消費(fèi)市場價(jià)格分析中，它能夠很快的求出各種產(chǎn)品之間的價(jià)格關(guān)系和它們之間的影響。尤其是在超市零售業(yè)中的應(yīng)用更是廣泛，通過對銷售數(shù)據(jù)記錄的分析，挖掘出商品的關(guān)聯(lián)規(guī)則，有利于

2、提高超市零售業(yè)的銷售利率，增強(qiáng)其市場競爭力。關(guān)鍵詞：關(guān)聯(lián)規(guī)則；Apriori算法；銷售利率Abstract:Apriorialgorithmiswidelyusedinbusinessandprice'sanalysisofconsumermarket,itcanquicklydeterminetheimpactofprice'srelationshipsbetweenthevariousproducts.Especiallyusinginsupermarketretailingisevenmorewidespread,throughtheanalysisofsalesdata

3、ofrecord,theassociationruleminingcommodities,helptoimprovethesupermarketretailsalesrates,andenhancetheirmarketcompetitiveness.Keywords:Associationrules;Apriorialgorithm;salesrate1 .研究背景超市零售業(yè)是數(shù)據(jù)挖掘應(yīng)用較為活躍的一個(gè)領(lǐng)域。了解客戶的購買習(xí)性和趨勢，對于零售商制訂銷售策略是至關(guān)重要的。通過關(guān)聯(lián)規(guī)則的挖掘，分析客戶對商品的需求狀況，發(fā)現(xiàn)顧客的潛在需求特征，有目的性的開展廣告和銷售業(yè)務(wù)。通過對顧客的忠誠度分析，

4、相應(yīng)調(diào)整商品的價(jià)格和類型，改進(jìn)銷售服務(wù)，有利于保持現(xiàn)有客戶，尋找潛在的客戶，擴(kuò)大銷售的范圍和規(guī)模，從而增加銷售量。通過分析銷售的數(shù)據(jù)記錄，目前主要應(yīng)用于銷售預(yù)測、庫存需求、零售點(diǎn)選擇和價(jià)格分析，分析客戶的購買行為和習(xí)慣，分析商場的銷售商品的構(gòu)成，使商品的選擇與搭配更為科學(xué)。因此，對超市經(jīng)營信息、數(shù)據(jù)的整理、挖掘，從中得出對經(jīng)營有用的信息，增強(qiáng)超市的競爭能力，已經(jīng)成為各家超市企業(yè)面臨的一個(gè)緊迫課題，同時(shí)，Apriori算法作為關(guān)聯(lián)規(guī)則挖掘的重要算法，也被各個(gè)企業(yè)所運(yùn)用。2 .關(guān)聯(lián)規(guī)則的基本概念設(shè)I=i1,i2,im是項(xiàng)的集合。設(shè)任務(wù)相關(guān)的數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合，其中每個(gè)事務(wù)T是項(xiàng)的集合。每一個(gè)

5、事務(wù)有一個(gè)標(biāo)識符，稱作TID。設(shè)A是一個(gè)項(xiàng)集，事務(wù)T包含A當(dāng)且僅當(dāng)ATo關(guān)聯(lián)規(guī)則是形如AB的蘊(yùn)涵式，其中AI,BI,并且AnB=。關(guān)聯(lián)分析中還包括兩個(gè)重要的參數(shù)，支持度（min_sup）和置信度（min_conf）。具體定義如下：支持度：support（AB）=P（AUB）,即A和B這兩個(gè)項(xiàng)集在事務(wù)集D中同時(shí)出現(xiàn)的概率。置信度:confidence（AB）=P（B|A）,即在出現(xiàn)項(xiàng)集A的事務(wù)集D中，項(xiàng)集B也同時(shí)出現(xiàn)的概率。同時(shí)滿足最小支持度（min_sup）和最小置信度（min_conf）的規(guī)則稱作強(qiáng)規(guī)則。項(xiàng)的集合稱為項(xiàng)集（itemset）,包含k個(gè)項(xiàng)的項(xiàng)集稱為k項(xiàng)集。項(xiàng)集的出現(xiàn)頻率是包含項(xiàng)集

6、的事務(wù)數(shù)，簡稱為項(xiàng)集的頻率、支持計(jì)數(shù)或計(jì)數(shù)。如果項(xiàng)集的出現(xiàn)頻率大于或等于最小支持度，則稱為頻繁項(xiàng)集頻繁k-項(xiàng)集的集合通常記作Lko3 .Apriori算法分析關(guān)聯(lián)規(guī)則（AssociationRules）的挖掘是數(shù)據(jù)挖掘中的一個(gè)重要問題。我們采用的是相關(guān)性分析的方法，采用的是Apriori算法。Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。其核心是基于兩階段頻集思想的遞推算法。該關(guān)聯(lián)規(guī)則在分類上屬于單維、單層、布爾關(guān)聯(lián)規(guī)則。在這里，所有支持度大于最小支持度的項(xiàng)集稱為頻繁項(xiàng)集，簡稱頻集。該算法的基本思想是：首先找出所有的頻集，這些項(xiàng)集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣。然

7、后由頻集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度和最小可信度。然后使用第1步找到的頻集產(chǎn)生期望的規(guī)則，產(chǎn)生只包含集合的項(xiàng)的所有規(guī)則，其中每一條規(guī)則的右部只有一項(xiàng)，這里采用的是中規(guī)則的定義。一旦這些規(guī)則被生成，那么只有那些大于用戶給定的最小可信度的規(guī)則才被留下來。為了生成所有頻集，使用了遞推的方法。Apriori算法采用連接步和剪枝步兩種方式來找出所有的頻繁項(xiàng)集。1）連接步為找出Lk（所有的頻繁k項(xiàng)集的集合），通過將Lk-1（所有的頻繁k-1項(xiàng)集的集合）與自身連接產(chǎn)生候選k項(xiàng)集的集合。候選集合記作Cko設(shè)l1和l2是Lk-1中的成員。記lij表示li中的第j項(xiàng)。假設(shè)Apriori算法對事務(wù)或項(xiàng)

8、集中的項(xiàng)按字典次序排序，即對于（k-1）項(xiàng)集li,li1<li2<,.<lik-1o將Li與自身連接，如果（l11=l21）&&（l12=l22）&&,.&&（l1k-2=l2k-2）&&（l1k-1<l2k-1），那認(rèn)為11和l2是可連接。連接l1和l2產(chǎn)生的結(jié)果是l11,l12,l1k-1,l2k-1o2）剪枝步G是Lk的超集，也就是說，Ck的成員可能是也可能不是頻繁的。通過掃描所有的事務(wù)（交易），確定G中每個(gè)候選的計(jì)數(shù)，判斷是否小于最小支持度計(jì)數(shù)，如果不是，則認(rèn)為該候選是頻繁的。為了壓縮Q,可以利用A

9、priori性質(zhì)：任一頻繁項(xiàng)集的所有非空子集也必須是頻繁的，反之，如果某個(gè)候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的，從而可以將其從Q中刪除。4 .數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘的實(shí)現(xiàn)過程a）數(shù)據(jù)采集數(shù)據(jù)是數(shù)據(jù)挖掘的前提，數(shù)據(jù)采集是獲取數(shù)據(jù)的方法與實(shí)現(xiàn)?？梢詫?shù)據(jù)庫中的數(shù)據(jù)進(jìn)行抽樣篩選得到與數(shù)據(jù)挖掘所處理的相關(guān)數(shù)據(jù)。也可以利用視圖對數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行篩選。1-1首先從數(shù)據(jù)中抽取同一購物單上的物品組成事務(wù)，用于關(guān)聯(lián)挖掘如表物品一物品二物品三物品四物品五物品六手套科普牙膏電視機(jī)電視機(jī)洗衣機(jī)T恤牙刷牛奶表1-1關(guān)聯(lián)事務(wù)表b)數(shù)據(jù)預(yù)處理在數(shù)據(jù)采集的基礎(chǔ)上，處理數(shù)據(jù)，使數(shù)據(jù)易于進(jìn)彳f挖掘處理。主要進(jìn)行了下面幾

10、個(gè)步驟：1)將商品信息表、銷售記錄表合并到一起(即數(shù)據(jù)集成)，返回銷售關(guān)聯(lián)信息。2)去除不用的數(shù)據(jù)字段，比如，銷售日期、商品數(shù)量等等對數(shù)據(jù)挖掘沒有作用，在預(yù)處理階段就把這些字段排除。C)數(shù)據(jù)挖掘Apriori算法是一種最有影響的挖掘布爾型關(guān)聯(lián)規(guī)則頻繁項(xiàng)目集的算法。算法思想的是基于先驗(yàn)知識，Apriori算法所采用的是逐層迭代搜索方法，K-項(xiàng)目集用于搜索(K+1)-項(xiàng)目集，首先，尋找出頻繁1-項(xiàng)目集的集合，該集合記作L1,L1用來尋找頻繁2-項(xiàng)目集的集合L2,再用L2尋找出L3,以此類推，直到不能找到頻繁M-項(xiàng)目集為止。每次找出一個(gè)Lk,就需要掃描數(shù)據(jù)庫一次，即如下所述：尋找頻繁項(xiàng)目集算法的基本

11、思路是Apriori的性質(zhì)，即頻繁項(xiàng)目的所有非空子集都必須是頻繁的。利用這個(gè)性質(zhì)在搜索頻繁項(xiàng)目集時(shí)，非常有利于壓縮搜索空間，從而提高頻繁項(xiàng)目集逐層搜索的效率。在第一遍掃描中，計(jì)算單個(gè)項(xiàng)目的支持度，確定哪些項(xiàng)目是頻繁項(xiàng)目，即它們需具有最小支持度。在后來的掃描中，均將前一次掃描得到的頻繁項(xiàng)目作為基礎(chǔ)項(xiàng)目，利用這個(gè)基礎(chǔ)項(xiàng)目產(chǎn)生出新的頻繁項(xiàng)目集，這樣的頻繁項(xiàng)目集稱作候選項(xiàng)目集(CandidateItemsets),并且在掃描數(shù)據(jù)的過程中計(jì)算這些候選項(xiàng)目集的實(shí)際支持度計(jì)數(shù)。掃描結(jié)束后，確定哪些候選項(xiàng)目集才是真正的頻繁項(xiàng)目，然后將是頻繁項(xiàng)目的這些候選項(xiàng)目集作為下一次掃描用的基礎(chǔ)項(xiàng)目。重復(fù)此過程直到?jīng)]有新的

12、頻繁項(xiàng)目集產(chǎn)生為止。一般地，算法要對數(shù)據(jù)庫進(jìn)行多次掃描。由于Apriori算法要求項(xiàng)目集的所有非空子集都必須是頻繁的，因此在數(shù)據(jù)庫中D的事務(wù)中尋找頻繁項(xiàng)目集時(shí)，需要進(jìn)行連接和剪枝，才能挖掘強(qiáng)關(guān)聯(lián)規(guī)則。如果在數(shù)據(jù)庫D中的事務(wù)找出所有的頻繁項(xiàng)目集以后，由他們產(chǎn)生滿足最小支持度和最小的可信度的強(qiáng)關(guān)聯(lián)規(guī)則就很容易了，可用如下式的條件概率計(jì)算出可信度，Confidence(A=B)=P(A|B)=support_count(A3)/support_count(A)其中support_count(A5)是包含項(xiàng)目集A_；B的事務(wù)數(shù)，support_count(A)是包含項(xiàng)目集A的事務(wù)數(shù)。根據(jù)該式，關(guān)聯(lián)規(guī)則

13、的可以產(chǎn)生如下：1)對于每個(gè)頻繁項(xiàng)目集L,產(chǎn)生L的所有非空子集。2)對于L的所有非空子集S,如果support_count(L)/support_count(S)>min_confidence,貝U輸出關(guān)聯(lián)規(guī)則"S=L-S",其中min_confidence是最小可信度閾值。由于規(guī)則由頻繁項(xiàng)目集產(chǎn)生，每個(gè)規(guī)則都滿足大于最小支持度，頻繁項(xiàng)目與他們的支持度可預(yù)先存放在散列表中，以加快訪問速度。讓我們以上例子說明關(guān)聯(lián)規(guī)則的挖掘，在該事務(wù)數(shù)據(jù)庫中，假定數(shù)據(jù)包含頻繁項(xiàng)目集L=I1,I2,I5,可以由L產(chǎn)生的關(guān)聯(lián)規(guī)則，L的非空子集由I1,I2,I1,I5,I2,I5,I1,I2和

14、I5,其支持度分別是4,2,2,6,7,2。得出的關(guān)聯(lián)規(guī)則如下：(每個(gè)都列出其可信度)11I2=I5,Confidence=2/4=50yy/OIiAI5=I2,Confidence=2/2=10012T5=Ii,Confidence=2/2=10011=12AI5,Confidence=2/6=3312.IiI5,Confidence=2/7=2915.IiI2,Confidence=2/2=100如果最小的可信度閾值是70%,則只有第2、3和最后一個(gè)規(guī)則可以輸出，因?yàn)檫@些產(chǎn)生的是強(qiáng)規(guī)則d)Apriori算法實(shí)現(xiàn)偽代碼K=1Fk=i|iGIAb(i)>Nxminsup發(fā)現(xiàn)所有的頻繁1項(xiàng)

15、集RepeatK=k+1Ck=apriorigen(Fk-)產(chǎn)生候選項(xiàng)集For每個(gè)事務(wù)tTdoCt=subset(Ck,t)識別屬于t的所有候選For(每個(gè)候選項(xiàng)集cGCtdob(c)=b(c)+1支持度計(jì)數(shù)增值EndforEndforFk=c|cGCkAo-(c)>NXminsup提取頻繁k項(xiàng)集UntilFk=nullResult=UFke）挖掘結(jié)果支持度閾值用于篩選出商品的頻繁項(xiàng)集集合，從而算出支持度；信任度閾值用于篩選出符合要求的商品集合之間信任度集合。通過支持度閾值和信任度閾值用戶可以根據(jù)實(shí)際需要來決定篩選的程度。同時(shí)購買商品的數(shù)據(jù)：牛肉,雞肉,牛蝸牛肉，蝸酪奶酪，靴子牛肉,雞肉

16、,奶酪牛肉雞肉工衣服媯酪，牛螃雞肉，衣服，牛妍雞肉沖帆衣耐設(shè)置支持度為：2信任度為：0.7則頻繁集牛奶；衣服；：3牛肉；雞肉；：3奶酪；雞肉；：2牛奶；衣服；雞肉；：3奶酪；：4衣服；雞肉；：3奶酪；牛肉；：3牛奶；牛肉；：2牛肉；：4雞肉；：5奶酪；牛肉；雞肉；：2牛奶；雞肉；：4牛奶；：4牛奶；牛肉；雞肉；：2衣服；：3關(guān)聯(lián)規(guī)則牛奶；衣服;->雞肉；：1.0牛奶;->雞肉；：1.0衣服；->雞肉；：1.0牛肉；->奶酪；：0.75牛奶;->衣服；：0.75牛奶;->衣服；雞肉；：0.75牛奶；牛肉；->雞肉；：1.0奶酪；雞肉；->牛肉；：1

17、.0衣服；->牛奶；：1.0牛肉；->雞肉；：0.75牛奶；雞肉；->衣服；：0.75雞肉；->牛奶；：0.8衣服；雞肉；->牛奶；：1.0衣服;->牛奶；雞肉；：1.0奶酪;->牛肉；：0.75f）結(jié)果分析從上面我們可以看到事務(wù)集中的所有頻繁項(xiàng)集，如牛奶；衣服；：3;牛肉；雞肉；：3;奶酪；雞肉；：2;牛奶；衣服；雞肉；：3等，他們的支持度都大于2。在這些頻繁集中，牛奶，衣服可以和雞肉建立關(guān)聯(lián)規(guī)則，因?yàn)樗麄兊男湃味却笥谒O(shè)定的最小信任度，如上面所示還有很多頻繁項(xiàng)集可建立關(guān)聯(lián)規(guī)則。與此同時(shí)，我們還可以看出顧客的消費(fèi)習(xí)慣和那些商品顧客會同時(shí)購買，超市應(yīng)該根據(jù)上面的分析結(jié)果來進(jìn)購商品和安