關(guān)聯(lián)規(guī)則算法的研究及應(yīng)用

晏 杰

(武夷學院 數(shù)學與計算機學院，福建 武夷山 354300)

0 引言

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

1 相關(guān)概念

(1)設(shè)I=[i1,i2,,i3,…in]項的集合，事務(wù)數(shù)據(jù)集D，對于每個事務(wù)T滿足T?I．每個事務(wù)有個表示符TID．事務(wù)T包含一個項目集A當且僅當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，表示項集A和項集B同時出現(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)項集A的事務(wù)數(shù)據(jù)集D中，項集B出現(xiàn)的概率．置信度的高低體現(xiàn)了關(guān)聯(lián)規(guī)則的可靠性[3]．

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

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

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

2.1 算法思想

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

2.2 Apriori算法舉例

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

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

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

(2)將C1中支持度計數(shù)大于等于設(shè)定閾值的項集組成頻繁項集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-項集L2，算法連接L1產(chǎn)生候選2-項集的集合C2；

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

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

2.3 算法性能缺陷

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

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

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

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

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

針對存在的以上問題，后來很多學者也提出了如基于Hash的方法、基于抽樣的方法、基于劃分的方法、基于動態(tài)項集計數(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)建模型，針對武夷山某超市的銷售數(shù)據(jù)進行關(guān)聯(lián)規(guī)則挖掘．

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

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

3.2 模型構(gòu)建

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

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

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

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

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

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

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

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