面向購物籃數(shù)據(jù)的稀有序列模式挖掘算法

周忠玉,皮德常

(南京航空航天大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,南京 211106)

1 引 言

購物籃數(shù)據(jù)是指人們每天去超市購買食品,包括肉類、谷物、蔬菜、水果、牛奶、雞蛋、酒類等日常生活用品的數(shù)據(jù).這些數(shù)據(jù)能夠真實(shí)地反映出人們的生活水平和生活質(zhì)量.因此,挖掘此類數(shù)據(jù)對提高人類的生活水平和生活質(zhì)量具有顯著的意義.目前多數(shù)數(shù)據(jù)挖掘研究者偏好挖掘頻繁的數(shù)據(jù)項(xiàng),而忽視了稀有模式挖掘.以購物籃數(shù)據(jù)為例,為了提高商品的整體銷售量,商家通常會將那些消費(fèi)者經(jīng)常一起購買的商品放在一起銷售.因此,他們通常會對一批數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘,找出頻繁序列,摒棄非頻繁的序列.然而,參照聯(lián)合廣告的互補(bǔ)性和非互補(bǔ)性,我們設(shè)想:既然兩種毫無關(guān)聯(lián)的廣告產(chǎn)品放在一起會加深人們對兩種品牌的認(rèn)識,那么我們是否也可以將兩種毫不相關(guān)的商品也放在一起銷售,從而引起消費(fèi)者對新品牌的注意,加深對老品牌的印象？這可能也是一種提高銷售量的策略.如果假設(shè)成立,那就意味著我們不能像關(guān)聯(lián)規(guī)則那樣隨意丟棄非頻繁(稀有)的序列,相反要利用好這些非頻繁的序列,找出它們的規(guī)律.為此很有必要對商品進(jìn)行稀有序列模式挖掘的研究.

本文針對上述問題及假設(shè),結(jié)合購物籃數(shù)據(jù)提出了一種稀有序列模式挖掘算法ISM-BD(Infrequent Sequence Mining of Shopping Basket Data).該算法通過挖掘稀有數(shù)據(jù)中的隱藏規(guī)律來進(jìn)一步提高商品銷售量.本文做出的主要貢獻(xiàn)如下:

1)ISM-BD算法設(shè)置時間變量來限制序列項(xiàng)的時間,從而使挖掘結(jié)果具有時效性與可用性.

2)ISM-BD算法的提出充分利用了本該舍棄的非頻繁數(shù)據(jù).

3)提出綜合權(quán)重因子,使得算法的挖掘結(jié)果更符合實(shí)際的區(qū)域差異性.

4)在ISM-BD算法的基礎(chǔ)上,給出了一種異常值檢測算法ISMO(Infrequent Sequence Mining based Outlier)來檢測購物籃數(shù)據(jù)中的異常數(shù)值.

本文的組織結(jié)構(gòu)如下:第2節(jié)介紹關(guān)于稀有的數(shù)據(jù)挖掘研究的相關(guān)工作;第3節(jié)對面向購物籃數(shù)據(jù)的稀有序列模式挖掘算法進(jìn)行討論分析并給出算法擴(kuò)展;第4節(jié)使用公開的購物籃數(shù)據(jù)進(jìn)行實(shí)驗(yàn),驗(yàn)證本文提出的ISM-BD算法的正確性和有效性;第5節(jié)對全文做出概要性的總結(jié)并給出進(jìn)一步的研究方向.

2 相關(guān)工作

2000年,Han提出的FreeSpan算法[2]是第一個涉及模式增長的算法.2001年,Pei Jian對FreeSpan算法做了改進(jìn),提出了PrefixSpan算法[3].同年,Zaki提出了SPADE算法[4],其算法的大體思想是利用等價類對全空間進(jìn)行劃分,從而得到一系列的子空間,以此來提高算法效率.2004年,Pei和Hant提出了Prefix算法[5].該算法摒棄了生成候選集的通用策略.因此,它的運(yùn)行速度比一般的算法都要快.2016年,宋海濤等提出基于模式挖掘的用戶行為異常檢測算法[11].該算法通過比較挖掘出的頻繁模式來檢測用戶行為的異常值.本文的擴(kuò)展算法ISMO也是基于這種理念提出的,但本文采用的是稀有模式,而非頻繁模式.同一年,為簡化交易過程,提高網(wǎng)絡(luò)交易的可靠性,王艷冰等提出FPM算法[12].該算法借助日志與頻繁模式的一致性來保證挖掘結(jié)果的正確性.2017年,韓楠等提出FPNMine算法[13].該算法引入支持度技術(shù)矩陣,極大地提高了算法的挖掘效率.同年8月,呂存?zhèn)サ忍岢鯡HUSN算法[14].該算法能夠?qū)Ψ呛蜻x集序列進(jìn)行快速剪枝,從而提高算法效率.同年9月,謝志軒等改進(jìn)了HUM-UT算法,并提出IHUM-UT算法[15].該算法主要通過壓縮原算法表頭的大小來提高算法的時間效率.2018年,李維娜等提出一種新的頻繁模式挖掘算法SG-FIP[16].該算法通過精簡挖掘結(jié)果來提高挖掘精度.

至此,所有的關(guān)于序列挖掘的研究都是挖掘頻繁序列的,并沒有挖掘稀有序列.

2007年L.Szathmary提出了著名的Apriori-Rare算法[6].這是關(guān)于稀有序列挖掘的首篇文章.此后,許多稀有序列挖掘算法都是據(jù)此提出的.2011年S.Tsang提出了一種基于樹結(jié)構(gòu)的稀有模式挖掘算法RP-Tree[7].2012年L.Szathmary又提出了一種優(yōu)化的Walky-G算法[8].2015年ARSPM算法[9]被提出.在此基礎(chǔ)上又提出了一種更為高效的AMRSPM算法[9].同年,Sweetlin Hemalatha提出了一種基于異常值的稀有序列模式挖掘算法——MIP-DS[10],并進(jìn)一步拓展為MIFPOD算法[1].2016年Ouyang在AMRSPM算法的基礎(chǔ)上提出了基于大量事務(wù)的最小稀有模式挖掘算法——MRSP算法[10].其中以MIP-DS算法較為經(jīng)典,該算法的思想大致如下:①生成1-序列;②通過計算1-序列的支持度判斷生成1-稀有序列,并排序;③以1-稀有序列為基礎(chǔ)生成候選序列;④計算候選序列的支持度,生成稀有最終的稀有序列.

本文在MIP-DS等算法的基礎(chǔ)上,提出了ISM-BD算法.該算法修正了滑動窗口,使之與序列項(xiàng)的數(shù)量關(guān)聯(lián);引入了時間變量用于限制序列項(xiàng)的有效時間;采用綜合權(quán)重因子作為衡量序列的區(qū)域差異性的標(biāo)準(zhǔn).結(jié)合購物籃數(shù)據(jù)對算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證和分析.

3 稀有序列挖掘算法

本文提出了一種面向購物籃數(shù)據(jù)的稀有序列模式挖掘算法ISM-BD.該算法主要的思想大致如下:由原始序列生成1-序列;判斷其時間限度是否在指定的范圍內(nèi),以決定是否生成1-稀有序列;將1-稀有序列作為原始序列,生成候選序列;判斷候選集的時效性和其支持度,生成最終的稀有序列.

3.1 基于綜合權(quán)重因子的稀有序列挖掘

購物籃數(shù)據(jù)受許多因素影響,如工資水平、生活習(xí)性、地方習(xí)慣、甚至于自然災(zāi)害等因素.我們不可能要求經(jīng)濟(jì)發(fā)達(dá)地區(qū)同落后地區(qū)具有相同的購買力;也不可能將北方的面食消費(fèi)量和稻米消費(fèi)量放在一起比較.如果通過直接設(shè)定統(tǒng)一的閾值δ來判定某一序列項(xiàng)是否為稀有項(xiàng),往往不具有通用性.例如可能存在如下情景:

情景1.設(shè)定某一區(qū)域h1的閾值δ= 0.3.理論上,只要Support(a)< 0.3,Support(b)< 0.3,序列項(xiàng)a和序列項(xiàng)b都被認(rèn)為是稀有項(xiàng).但實(shí)際上由于序列項(xiàng)a和序列項(xiàng)b的實(shí)際購買力不同,只有當(dāng)Support(b)< 0.2時,序列項(xiàng)b才能被認(rèn)為是稀有項(xiàng).

情景2.設(shè)定區(qū)域h1和區(qū)域h2的閾值δ= 0.3.理論上,對于區(qū)域h1和區(qū)域h2來說只要Support(c)< 0.3,那么序列項(xiàng)c就被認(rèn)為是稀有項(xiàng).但實(shí)際上由于不同區(qū)域的飲食習(xí)性不同,對于h2地區(qū)來說只需要Support(c)< 0.4,序列c就應(yīng)該被認(rèn)定為是稀有項(xiàng).

可見,設(shè)定統(tǒng)一的固定閾值δ不能滿足挖掘結(jié)果準(zhǔn)確性和通用性的需求.甚至?xí)沟闷渫诰蚪Y(jié)果是完全錯誤的.為此本文提出一種固有動態(tài)閾值σ的概念.固有是指在同一區(qū)域下,序列組的判定閾值是確定的.動態(tài)是指在不同區(qū)域下,序列組的判定閾值是不確定的.我們把同一區(qū)域下每個序列項(xiàng)對序列組的影響稱為影響因子,用矩陣X表示:

其中xij表示在區(qū)域i下,第j個序列項(xiàng)的影響因子(i=1,2,…,m,j=1,2,…,n).

定義一組單映射fi,記作:

fi:xij→σi

其中σi為區(qū)域i對應(yīng)的判定閾值;fi為區(qū)域i下的單映射關(guān)系,也可以將上述映射用公式(1)式表示:

σi=fi(xij)

(1)

將上述這種固有動態(tài)閾值稱為綜合權(quán)重因子,用符號σ表示.通過采用綜合權(quán)重因子會使得挖掘結(jié)果更符合實(shí)際情況并且具有一致性和準(zhǔn)確性.綜合權(quán)重因子是衡量序列組的區(qū)域差異性度量.其值為影響某一序列組的各種因素權(quán)重的加權(quán)求和,用公式(2)表示:

(2)

其中hi為區(qū)域i對序列組的影響因素,稱之為環(huán)境因子.由此可見不同區(qū)域的閾值是不同的.但是針對實(shí)際情況,只要閾值滿足公式(3),它們的挖掘結(jié)果在稀有程度上是相當(dāng)?shù)?

(3)

其中,σmax是最大的綜合權(quán)重因子,σmin是最小的綜合權(quán)重因子,α為常數(shù)(0<α<0.5).

算法1.ISM-BD

Algorithm1.Infrequent Sequence Mining of Shopping Basket Data

Input:原始序列S,滑動窗口長度|SW|,環(huán)境因子hk,矩陣X,最小時間間隔minGap和最大時間間隔maxGap.

Output:稀有序列.

1.SC1←{1-sequence}

2.For each 1≤k≤m

3. For each 1≤l≤n

4.σk=∑hkxkl(xkl是矩陣X的元素)

5. End for

6. For every sequencei∈[minGap,maxGap]

10. End for

11. For every sequencei∈[minGap,maxGap] & & SiF1

12. SCnext←Candidate(i)

15. End for

16. iFk=iF1∪iFnext

17.End for

算法1說明:

步驟1.從原始序列S中找到所有長度為1的序列,放入集合SC1中.

步驟2.判斷挖掘區(qū)域hk.計算區(qū)域hk下對應(yīng)的綜合權(quán)重因子σk.

步驟3-5.取出矩陣X中的k行元素,利用公式(2)計算綜合權(quán)重因子σk.

步驟6.限定集合SC1中所有1-序列的時間間隔.若在有效時間內(nèi)則進(jìn)入步驟7-9.若不在有效期內(nèi)則放棄該序列并返回步驟6判斷下一個序列,直至所有1-序列判斷完畢.

步驟7-10.分別計算SC1中所有1-序列的支持度并將其按照支持度升序排序,然后根據(jù)判斷公式選出集合SC1中所有1-稀有序列并將它們放入集合iF1中.

步驟11.判斷除了iF1中序列以外的所有剩余原始序列是否在限定的時間間隔內(nèi).若在有效時間內(nèi)則進(jìn)入步驟12-15.若不在有效期內(nèi)則放棄該序列并返回步驟11判斷下一個序列,直至所有序列判斷完畢.

步驟12-15.在剩余序列中生成候選集,放入集合SCnext中.之后計算候選集中所有序列的支持度,根據(jù)判斷公式選出所有剩余的稀有序列并將其放入集合iFnext中.

步驟16.合并集合iF1與集合iFnext形成區(qū)域hk下最終的稀有序列集iFk.若只有一種區(qū)域,則結(jié)束算法.否則返回步驟2.

3.2 基于異常值的算法擴(kuò)展

在3.1節(jié)中研究的序列都是理想的序列,即不存在錯誤、空白、人為失誤等異常因素.然而,在現(xiàn)實(shí)生活中這樣的情況往往不會發(fā)生.因此,為了使算法更符合實(shí)際情況,我們把異常值考慮進(jìn)去.

異常值是一種與大多數(shù)觀測值大不相同的值[1].例如:在滑動窗口SW中有一序列s的屬性與其他序列的屬性大不相同,我們就把序列s稱為滑動窗口SW中的異常值.

為了更加清楚的介紹基于異常值的稀有算法,我們引入異常值判斷公式(4)至公式(6).首先給出序列權(quán)重因子(SWF).假設(shè)S = {s1,s2,s3,…,sn-1,sn}是滑動窗口SW中的n個序列,IF為所有稀有序列的集合.對于每一個序列s,它的SWF可以用公式(4)來計算.

(4)

顯然,如果序列s中存在異常值,那么它會生成更多的稀有序列,即IF會增多.反之,如果序列s的SWF值越小,那么它越有可能存在異常值.

下面給出稀有序列誤差因子(IDF).假設(shè)S = {s1,s2,s3,…,sn-1,sn}是滑動窗口SW中的n個序列,由公式(2)計算得出的綜合權(quán)重因子為σ,對于每個稀有序列is,其IDF為:

(5)

顯然,如果序列s的支持度小于綜合權(quán)重因子為σ,那么它就是稀有序列.但是序列的異常程度是由序列s偏離綜合權(quán)重因子σ的程度決定的.因此,對于基于異常值的稀有算法,IDF是必不可少的.

最后,給出基于異常值的稀有序列因子(IOF).對于每個序列s,它的IOF為:

(6)

其中SWF是序列權(quán)重因子,IDF是稀有序列誤差因子.基于異常值的擴(kuò)展算法偽代碼見算法2.

算法2.ISMO

Algorithm2.Infrequent Sequence Mining based Outlier

Input:原始序列S,稀有序列的長度|IF|,環(huán)境因子hk,矩陣X.

Output:異常序列集.

1.For each 1≤k≤m

2. For each 1≤l≤n

3.σk=∑hkxkl(xkl是矩陣X的元素)

4. End for

1Basket實(shí)驗(yàn)數(shù)據(jù)集公開地址： http://files.cnblogs.com/files/fengfenggirl/%E5%85%B3%E8%81%94%E8%A7%84%E5%88%99%E6%95%B0%E6%8D%AE.rar

5. IF←iFk// using IDMBDSB Algorithm

6. For every s ∈SW

7. S(s)=0 A(s)=0

8. For everyi∈IF

10. ifi? s

11. S(s)+=1

12. A(s)+=IDF(i)

13. End if

14. End for

15. SWF(s)=S(s)÷|IF|

16. IOF(s)=1-(SWF(s)*A(s))

17. if (IOF(s)>σk)

18. output s

19. End if

20. End for

21.End for

算法2說明:

步驟1.判斷挖掘區(qū)域hk.計算區(qū)域hk下對應(yīng)的綜合權(quán)重因子σk.

步驟2-4.取出矩陣X中的k行元素,利用公式(2)計算綜合權(quán)重因子σk.

步驟5.將算法ISM-BD形成的稀有序列集iFk賦值給集合IF.

步驟8-14.利用公式(5)計算IF中所有稀有序列的稀有序列誤差因子IDF值.

步驟15-16.分別利用公式(4)和公式(6)來計算稀有序列的序列權(quán)重因子SWF和稀有序列因子IOF.

步驟17-21.判斷序列s的稀有序列因子IOF是否大于綜合權(quán)重因子σk.若是,則輸出;否則繼續(xù)循環(huán)操作,直至不能產(chǎn)生新的異常序列為止.循環(huán)結(jié)束后,若只有hk則結(jié)束算法,否則返回步驟1.

4 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)設(shè)置2個不同的環(huán)境因子以作對比.其中h1=0.1,h2=0.5.實(shí)驗(yàn)的數(shù)據(jù)來源于公開的basket數(shù)據(jù)集1.

該數(shù)據(jù)集的商品總數(shù)有16469個,購物的商品序列項(xiàng)種類總共有11種,序列項(xiàng)個數(shù)總共有2800個.具體分布情況見表1.

實(shí)驗(yàn)采用的是同一批數(shù)據(jù)源(表1數(shù)據(jù)源)在區(qū)域h1和區(qū)域h2下挖掘稀有序列.由于區(qū)域差異性,不同區(qū)域內(nèi)的各個序列項(xiàng)的影響因子可能不盡相同.為此,在不同區(qū)域h1和h2內(nèi),我們使用的各個序列項(xiàng)的影響因子分別為x1j和x2j(j=1,2,…,11).其具體數(shù)值如表2所示.

根據(jù)公式(2)計算得出綜合權(quán)重因子σ1=0.2,σ2=0.265.ISM-BD算法在區(qū)域h1下對購物籃數(shù)據(jù)的挖掘結(jié)果如表3所示,在區(qū)域h2下對購物籃數(shù)據(jù)的挖掘結(jié)果如表4所示.

其中,表3和表4的第1列是結(jié)果,第2列是條件,第3列是支持度,第4列是置信度.例如:表3的第一行表示購買鮮肉的顧客就不會購買汽水.其支持度為4.2%,置信度為22.95%.通過表3可以發(fā)現(xiàn)使用ISM-BD算法在區(qū)域h1下可以挖掘出3個稀有模式.模式1:購買鮮肉(freshmeat)或奶制品(dairy)或兩者都買的顧客不會購買汽水(softdrink);模式2:購買鮮肉或汽水或兩者都買的顧客不會購買奶制品;模式3:購買奶制品或汽水或兩者都買的顧客不會購買鮮肉.從這3種模式中,可以看出顧客不會同時購買鮮肉、汽水和奶制品.從它們的支持度可以看出上述3種食品兩兩購買的情況只占4.2%、3.3%和3.5%,3種食品全部都購買的情況則只占0.7%.可見,算法1挖掘出來的結(jié)果是正確的,它們都是不頻繁(稀有)出現(xiàn)的序列.因此,在區(qū)域h1下,對于某新型品牌的奶制品,可以將其和鮮肉或汽水放在一起銷售.這樣做可引起顧客的注意,打響品牌知名度,從側(cè)面提升銷售量.從表4的第3列支持度同樣可以看出ISM-BD算法在區(qū)域h2下的挖掘結(jié)果也為不頻繁(稀有)序列.由此可見該算法在不同區(qū)域下都能很好的挖掘出稀有序列,算法是有效的.

表1 購物籃原始數(shù)據(jù)項(xiàng)分布
Table 1 Original data in the shopping basket distribution

序列項(xiàng) 數(shù)量fruitveg299freshmeat183dairy177cannedveg303cannedmeat204frozenmeal302beer293wine287softdrink184fish292confectionery276合計2800

表2 影響因子的值
Table 2 Value of the influencing factors

j值x1jx2j10.220.0520.140.0330.120.0340.220.0550.140.0460.220.0570.200.0580.200.0590.140.03100.200.05110.200.05

表3 區(qū)域h1下的挖掘結(jié)果
Table 3 Result of mining in region h1

綜合權(quán)重因子σ1=0.2后項(xiàng)前項(xiàng)支持度 %置信度 %softdrinkfreshmeat4.2022.95dairy3.5019.77freshmeat dairy0.7021.21dairyfreshmeat3.3018.03softdrink3.5019.02freshmeat softdrink0.7016.67freshmeatsoftdrink4.2022.83dairy3.3018.64dairy softdrink0.7020.00

表4 區(qū)域h2下的挖掘結(jié)果
Table 4 Result of mining in region h2

綜合權(quán)重因子σ2=0.265后項(xiàng)前項(xiàng)支持度 %置信度 %softdrinkfreshmeat4.2022.95dairy3.5019.77cannedmeat4.2020.59freshmeat dairy0.7021.21freshmeat cannedmeat1.3031.71dairy cannedmeat0.9029.03freshmeat dairy cannedmeat0.3042.86dairyfreshmeat3.3018.03softdrink3.5019.02cannedmeat3.1015.20freshmeat softdrink0.7016.67freshmeat cannedmeat0.7017.07softdrink cannedmeat0.9021.43freshmeat softdrink cannedmeat0.3023.08freshmeatcannedmeat4.1020.10softdrink4.2022.83dairy3.3018.64dairy softdrink0.7020.00dairy cannedmeat0.7022.58softdrink cannedmeat1.3030.95dairy softdrink cannedmeat0.3033.33cannedmeatfreshmeat4.1022.40dairy3.1017.51softdrink4.2022.83freshmeat dairy0.7021.21freshmeat softdrink1.3030.95dairy softdrink0.9025.71freshmeat dairy softdrink0.3042.86

對比表4和表3可以看出,在不同環(huán)境h1和h2下,即使數(shù)據(jù)源相同,但挖掘的結(jié)果卻有很大的差異.例如:在環(huán)境h1下挖掘出了3種稀有模式,而在環(huán)境h2下挖掘出了4種稀有模式并且數(shù)目也完全不同.這就體現(xiàn)了綜合權(quán)重因子的意義.它會挖掘出更加符合當(dāng)?shù)貐^(qū)域的稀有序列,也會使得挖掘結(jié)果更符合實(shí)際情況.

對數(shù)據(jù)源做進(jìn)一步的處理,為其增加時間項(xiàng).設(shè)置時間變量為minGap和maxGap.ISM-BD算法采用時間變量,MIP-DS算法未使用,而閾值等其他條件相同.表5給出了兩種算法挖掘結(jié)果對比.

從表5可以看出dairy項(xiàng)不在[minGap,maxGap]內(nèi),不具時效性.ISM-BD算法采用時間變量,其挖掘結(jié)果比沒有采用時間變量的MIP-DS算法簡單有效.它僅包含具有時效性的稀有序列模式.以后項(xiàng)汽水(softdrink)為例,ISM-BD算法只包含一條稀有序列,當(dāng)顧客購買鮮肉(freshmeat)后不會購買汽水;MIP-DS算法包含三條稀有序列,當(dāng)顧客購買鮮肉或奶制品(dairy)或兩者都購買的時不會購買汽水.ISM-BD算法的挖掘結(jié)果都在時效內(nèi),都是有效的稀有序列;MIP-DS算法的9條挖掘結(jié)果中僅有2條在時效內(nèi),其余均為無效序列.所以,ISM-BD算法的挖掘結(jié)果具有非常高的有效性.

表5 采用時間變量前后的算法結(jié)果對比
Table 5 Comparison of the results of the algorithm before and after using time variable

ISM-BD算法:采用時間變量 后項(xiàng) 前項(xiàng)支持度%置信度%softdrinkfreshmeat4.222.95freshmeatsoftdrink4.222.83MIP-DS算法:未采用時間變量 后項(xiàng) 前項(xiàng)支持度%置信度%freshmeat4.222.95softdrinkdairy3.519.77freshmeat dairy0.721.21freshmeat3.318.03 dairysoftdrink3.519.02freshmeat softdrink0.716.67softdrink4.222.83freshmeatdairy3.318.64 dairy softdrink0.720.00

5 結(jié) 論

本文針對頻繁序列模式挖掘?qū)Ψ穷l繁項(xiàng)不加以利用而普遍舍棄以及挖掘結(jié)果存在時效性和區(qū)域差異性的問題.提出了基于綜合權(quán)重因子的稀有序列模式挖掘算法.該算法能夠很好的利用稀有序列,挖掘出它們的規(guī)律.既能夠從側(cè)面提高商品的銷售量,又能夠符合實(shí)際區(qū)域環(huán)境.采用公開數(shù)據(jù)驗(yàn)證了算法的有效性.今后還要采用更多大量的數(shù)據(jù)來改進(jìn)實(shí)驗(yàn)以求得更為準(zhǔn)確的結(jié)果.也可以對算法2做出進(jìn)一步的改進(jìn),提高其效率.