晏 杰

(武夷學(xué)院 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，福建 武夷山 354300)

0 引言

數(shù)據(jù)挖掘[1](Data Mining，簡記，DM)是數(shù)據(jù)庫中的知識(shí)發(fā)現(xiàn)( Knowledge Discover in Database，簡記，KDD)．關(guān)聯(lián)規(guī)則挖掘(Association Rule Mining)是數(shù)據(jù)挖掘范疇中的一個(gè)重要分支，用于在數(shù)據(jù)中發(fā)現(xiàn)某條件下的兩個(gè)或多個(gè)項(xiàng)集之間的依賴關(guān)系．本文重點(diǎn)研究了關(guān)聯(lián)規(guī)則Apriori算法的思想，提出了此算法的不足，并結(jié)合spss clementine軟件將關(guān)聯(lián)挖掘應(yīng)用于某超市的銷售數(shù)據(jù)，從大類及二級(jí)類商品之間兩個(gè)方面挖掘出商品間的聯(lián)系，為超市管理者合理的貨架陳列和銷售提供輔助決策信息．

1 相關(guān)概念

(1)設(shè)I=[i1,i2,,i3,…in]項(xiàng)的集合，事務(wù)數(shù)據(jù)集D，對(duì)于每個(gè)事務(wù)T滿足T?I．每個(gè)事務(wù)有個(gè)表示符TID．事務(wù)T包含一個(gè)項(xiàng)目集A當(dāng)且僅當(dāng)A?T，關(guān)聯(lián)規(guī)則R:A→B，其中A?I，B?I，并且A∩B=?．

(2)支持度Support(A→B)=Support(A∪B) =P(A∪B)=S，表示項(xiàng)集A和項(xiàng)集B同時(shí)出現(xiàn)的事務(wù)數(shù)量在事務(wù)數(shù)據(jù)集D中事務(wù)數(shù)的概率．支持度的高低體現(xiàn)了關(guān)聯(lián)規(guī)則是否具有普遍性[2]．

(3)置信度Confidence(A→B)=Support(A∪B)/Support(A)=P(B|A)=C，表示在出現(xiàn)項(xiàng)集A的事務(wù)數(shù)據(jù)集D中，項(xiàng)集B出現(xiàn)的概率．置信度的高低體現(xiàn)了關(guān)聯(lián)規(guī)則的可靠性[3]．

(4)提升度Lift(A→B)=P(B|A)/P(B)即置信度與期望置信度的比值，如果取值大于1說明項(xiàng)集A和項(xiàng)集B是正相關(guān)的，即項(xiàng)集A的出現(xiàn)可以帶動(dòng)項(xiàng)集B的出現(xiàn)，否則項(xiàng)集A和項(xiàng)集B是負(fù)相關(guān)或沒有關(guān)聯(lián)性．

強(qiáng)規(guī)則即支持度和置信度均不小于最小支持度閾值和最小置信度閾值的關(guān)聯(lián)規(guī)則，相反則稱為弱規(guī)則．關(guān)聯(lián)規(guī)則挖掘問題實(shí)質(zhì)上就是產(chǎn)生強(qiáng)規(guī)則的問題[4]．

2 關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法Apriori算法

2.1 算法思想

Apriori算法是1993年由R.Agrawal等人提出來挖掘布爾關(guān)聯(lián)規(guī)則所需頻繁項(xiàng)集的基本算法[5]．該算法應(yīng)用(性質(zhì)1:頻繁項(xiàng)集的全部非空子集也都是頻繁項(xiàng)目集，性質(zhì)2:非頻繁項(xiàng)目集的全部超集也都是非頻繁項(xiàng)目集)兩個(gè)重要的性質(zhì)來提高頻繁模式逐層產(chǎn)生的效率，也減小了搜索的空間．關(guān)聯(lián)規(guī)則的挖掘分為兩個(gè)步驟:首先通過對(duì)數(shù)據(jù)庫進(jìn)行掃描而得到頻繁1-項(xiàng)集的集合，緊接著用頻繁1-項(xiàng)集生成候選2-項(xiàng)集，然后為了找出頻繁2-項(xiàng)集，再對(duì)數(shù)據(jù)庫進(jìn)行掃描，如此循環(huán)下去，一直進(jìn)行到找出所有的頻繁項(xiàng)集．其次是由頻繁項(xiàng)集生成強(qiáng)關(guān)聯(lián)規(guī)則．

2.2 Apriori算法舉例

假設(shè)事務(wù)數(shù)據(jù)庫D中有10個(gè)事務(wù)，設(shè)最小支持度閾值為20%，即最小支持度計(jì)數(shù)是10*20%=2，如表1所示．

頻繁項(xiàng)集發(fā)現(xiàn)過程：

(1)掃描事務(wù)數(shù)據(jù)庫D，對(duì)事務(wù)中每個(gè)項(xiàng)集進(jìn)行支持度計(jì)數(shù)，并將其存在候選項(xiàng)集C1中；

(2)將C1中支持度計(jì)數(shù)大于等于設(shè)定閾值的項(xiàng)集組成頻繁項(xiàng)集L1， L1={{A7,3},{Q1,2},{Q3,2},{Q4,6},{R3,5},{R4,3},{R5,2},{S2,2},{S4,5},{S6,2}}；

表1 事務(wù)數(shù)據(jù)庫D

(3)為發(fā)現(xiàn)頻繁2-項(xiàng)集L2，算法連接L1產(chǎn)生候選2-項(xiàng)集的集合C2；

(4)掃描事務(wù)數(shù)據(jù)庫D，對(duì)候選項(xiàng)集C2中每個(gè)項(xiàng)集進(jìn)行支持度計(jì)數(shù)，將C2中支持度計(jì)數(shù)大于等于設(shè)定閾值的項(xiàng)集組成頻繁項(xiàng)集L2．L2={{A7Q4,2},{A7S2,2} ,{Q1S6,2} {Q4R3,3},{Q4R4,2},{Q4S4,4},{R3S4,4}}；

(5)候選項(xiàng)集C3由L2產(chǎn)生．C3={Q4R3S4}．掃描事務(wù)數(shù)據(jù)庫D，C3中的候選項(xiàng)集{Q4R3S4}支持度計(jì)數(shù)是3，因此L3={Q4R3S4},算法結(jié)束．

2.3 算法性能缺陷

Apriori算法應(yīng)用Apriori性質(zhì)來產(chǎn)生候選項(xiàng)集的方法，在少量數(shù)據(jù)的情況下大大減少了候選頻繁項(xiàng)集的規(guī)模，取得了很好的性能，但該算法也存在著性能缺陷，表現(xiàn)如下：

(1)反復(fù)掃描事務(wù)數(shù)據(jù)庫D， I/O開銷大．對(duì)于每次k循環(huán)，都必須通過重新掃描事務(wù)集數(shù)據(jù)庫D來計(jì)算候選項(xiàng)目集C 中每個(gè)項(xiàng)集的支持度，因此產(chǎn)生巨大的I/O時(shí)空開銷．

(2)產(chǎn)生龐大的候選項(xiàng)目集．候選項(xiàng)目集C 是指數(shù)增長的，產(chǎn)生龐大的的候選項(xiàng)目集將致使執(zhí)行時(shí)間顯著增加，運(yùn)行效率明顯降低[6]．

(3)“支持度—置信度”架構(gòu)的局限性．Apriori算法衡量和生成關(guān)聯(lián)規(guī)則的主要準(zhǔn)則是考慮支持度和置信度閾值,若是將支持度閾值設(shè)置過低，會(huì)生成過多的甚至是虛假的規(guī)則；若是設(shè)置過高，有可能會(huì)丟失一些有意義的規(guī)則；若是將兩個(gè)閾值設(shè)置的都很高,則往往產(chǎn)生的是早已經(jīng)被掌握的、不言而喻的關(guān)聯(lián)規(guī)則．

(4)Apriori算法忽視了反面事例的情況．例如我們無法挖掘出類似“交易記錄中54%買了方便面不買火腿腸，買了方便面的人中不買火腿腸的可能性”這些有用的反面規(guī)則[7]．

針對(duì)存在的以上問題，后來很多學(xué)者也提出了如基于Hash的方法、基于抽樣的方法、基于劃分的方法、基于動(dòng)態(tài)項(xiàng)集計(jì)數(shù)的方法、基于事務(wù)壓縮等方法來優(yōu)化Apriori算法．

3 關(guān)聯(lián)規(guī)則Apriori算法的應(yīng)用

目前各領(lǐng)域應(yīng)用的數(shù)據(jù)挖掘軟件輔助決策有許多，比較著名有SAS Enterprise Miner、SPSS Clementine、SQL Server Data Mining、IBM Intelligent Miner、Oracle DM等，在Clementine中關(guān)聯(lián)挖掘有“有序模型”、 “Carma模型”、“GRI模型”和“Apriori模型”[8]，本文選擇 “Apriori”算法構(gòu)建模型，針對(duì)武夷山某超市的銷售數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘．

3.1 數(shù)據(jù)預(yù)處理

在數(shù)據(jù)挖掘之前，需要針對(duì)收集的超市銷售數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗、數(shù)據(jù)集成、數(shù)據(jù)變換、數(shù)據(jù)歸約、數(shù)據(jù)離散化等預(yù)處理．比如在采集的數(shù)據(jù)中，包括流水號(hào)、日期時(shí)間、商品條碼、商品名稱、商品所屬大類、是否會(huì)員等字段，我們將與數(shù)據(jù)挖掘無關(guān)的字段日期時(shí)間、商品條碼刪除，因?yàn)樾⌒统兄袝?huì)員的數(shù)量少之甚少，這里我們也將是否會(huì)員字段刪除．

3.2 模型構(gòu)建

構(gòu)建的數(shù)據(jù)流如圖1所示[9]．

圖1 關(guān)聯(lián)規(guī)則挖掘數(shù)據(jù)流圖

這里設(shè)大類商品挖掘中最小支持度為10%，最小置信度為50%，挖掘結(jié)果如表2所示．設(shè)二級(jí)類商品之間的關(guān)聯(lián)挖掘最小支持度為60%，最小置信度為80%，挖掘結(jié)果如表3所示．

表2 大類商品關(guān)聯(lián)規(guī)則挖掘部分結(jié)果

表3 二級(jí)類商品關(guān)聯(lián)規(guī)則挖掘部分結(jié)果

3.3 結(jié)果分析及建議

從表2和表3中可以看到大部分規(guī)則的提升度大于1，說明前項(xiàng)和后項(xiàng)之間是正相關(guān)的，前項(xiàng)的銷售可以帶動(dòng)后項(xiàng)，小于1的成負(fù)相關(guān)，前項(xiàng)的銷售不會(huì)帶動(dòng)后項(xiàng)的銷售，即使放在一起，促銷成功的幾率也比較?。?第一行表示所有消費(fèi)者中買肉品的消費(fèi)者占到15.521%，買肉品的同時(shí)又購買蔬果的顧客占到買肉品顧客的78.958%，置信度很高要是把肉品和蔬果擺放在一起，肯定比分開擺放銷售額要好．同時(shí)消費(fèi)者在購買面包類、日配類、糧油類、生鮮類、肉品類的時(shí)候都不同程度的購買了蔬果類，說明超市的蔬果銷量很好，均是正相關(guān)的．建議管理者將購物架設(shè)置成圓形的，中間擺放蔬果類，周邊地區(qū)分別擺放肉品類、生鮮類、糧油類、日配類和面包類．表3為消費(fèi)者購買二級(jí)類商品的部分關(guān)聯(lián)情況，其中以香煙為例，可以看出消費(fèi)者在購買香煙的時(shí)候會(huì)購買休閑食品、熟食類、啤酒等作為輔料，支持度均為62.115%，其中在購買香煙的消費(fèi)者中購買啤酒的人數(shù)居多，占89.655%，香煙的購買帶動(dòng)休閑食品的購買的提升度則最高1.189．建議管理者在貨架陳列時(shí)，可以將前后項(xiàng)置信度較高的商品擺放在一起，這樣可以使消費(fèi)者輕松方便的選購，同時(shí)對(duì)于支持度較低的商品可以采取促銷或與其他商品捆綁銷售的方式增加銷售量．

4 結(jié)論

本文對(duì)數(shù)據(jù)挖掘中的重要分支關(guān)聯(lián)規(guī)則Apriori算法進(jìn)行了深入的研究，并通過實(shí)例分析了發(fā)現(xiàn)頻繁項(xiàng)集的過程，提出了Apriori算法的不足，并結(jié)合spss clementine軟件將關(guān)聯(lián)挖掘應(yīng)用于某超市的銷售數(shù)據(jù)，從大類和二級(jí)類兩個(gè)方面挖掘出商品間的聯(lián)系，針對(duì)挖掘結(jié)果進(jìn)行了分析并提出了相應(yīng)的建議，這對(duì)于提高超市銷售額有一定的現(xiàn)實(shí)意義．

[1]J.W.Han,Mi Kamber,范 明,孟小峰，譯.數(shù)據(jù)挖掘概念與技術(shù)[M].北京:機(jī)械工業(yè)出版社,2006.

[2]于海濤.抽樣技術(shù)在數(shù)據(jù)挖掘中的應(yīng)用研究[D].合肥：合肥工業(yè)大學(xué),2006.

[3]劉 強(qiáng).數(shù)據(jù)挖掘在大學(xué)生就業(yè)信息管理中的應(yīng)用研究[D].青島：山東科技大學(xué),2008.

[4]亓文娟,晏 杰,郭 磊,等.關(guān)聯(lián)規(guī)則挖掘在大學(xué)生心理健康測評(píng)系統(tǒng)中的應(yīng)用研究[J].湖南工業(yè)大學(xué)學(xué)報(bào)，2013，11：94～99.

[5]王德才.數(shù)據(jù)挖掘在校園卡消費(fèi)行為分析中的研究與應(yīng)用[D].哈爾濱：哈爾濱工程大學(xué),2010.

[6]晏 杰.亓文娟.基于Apriori&FP-growth算法的研究[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2013，5：122～125.

[7]羅 芳.基于聚類和壓縮矩陣的加權(quán)關(guān)聯(lián)規(guī)則算法的研究與應(yīng)用[D].上海：華東師范大學(xué)，2010，10:24～37.

[8]蔣盛益,李 霞,鄭 琪.數(shù)據(jù)挖掘原理與實(shí)踐[M].北京:電子工業(yè)出版社，2011.

[9]丘小婷.數(shù)據(jù)挖掘工具CLEMENTINE應(yīng)用[J].牡丹江大學(xué)學(xué)報(bào)，2007，(4):103～105．