楊海軍，張博嵐，路永華

(蘭州財(cái)經(jīng)大學(xué) 信息工程學(xué)院，甘肅 蘭州 730020)

0 引言

模式挖掘多年來(lái)一直是數(shù)據(jù)挖掘研究領(lǐng)域的重要課題，主要內(nèi)容包括頻繁項(xiàng)集挖掘、高效用項(xiàng)集挖掘、序列挖掘等.頻繁項(xiàng)集指的是在數(shù)據(jù)庫(kù)中的支持度不低于用戶指定的最小支持度閾值的項(xiàng)集.頻繁項(xiàng)集挖掘算法[1-5]的意義在于發(fā)現(xiàn)數(shù)據(jù)庫(kù)中大量出現(xiàn)的項(xiàng)集，其主要可分為2大類：基于水平層級(jí)機(jī)制和基于模式增長(zhǎng)機(jī)制，前者以Apriori算法[1]為代表，后者以FP-Growth算法[2]為代表.在實(shí)際應(yīng)用中，頻繁項(xiàng)集挖掘算法基于所有項(xiàng)都具有相同“利潤(rùn)”的假設(shè)是不能完全滿足實(shí)際需求的，因此高效用項(xiàng)集的概念和模型在文獻(xiàn)[6]中開(kāi)始被提出，并在同年發(fā)表的文獻(xiàn)[7]中通過(guò)TWDC(Transaction Weighted Download Closure)策略得到解決.高效用項(xiàng)集指的是數(shù)據(jù)庫(kù)中效用值不小于用戶設(shè)定的最小效用閾值的項(xiàng)集.一般的高效用項(xiàng)集挖掘算法[8-14]通過(guò)應(yīng)用效用模型(包括商品利潤(rùn)、物品重要性、用戶偏好程度等)發(fā)現(xiàn)數(shù)據(jù)庫(kù)中的所有高效用項(xiàng)集.但隨著頻繁項(xiàng)集挖掘算法和高效用項(xiàng)集挖掘算法的大量涌現(xiàn)和應(yīng)用，研究人員發(fā)現(xiàn)單獨(dú)使用頻繁項(xiàng)集挖掘或高效用項(xiàng)集挖掘方法在實(shí)際應(yīng)用中存在一定局限性，比如一些出現(xiàn)頻率很高的商品及商品組合能夠給商家提供的利潤(rùn)是很小的，例如食鹽；而一些效用很高的商品，出現(xiàn)頻率卻很低，例如奢侈品，會(huì)使得相應(yīng)頻繁項(xiàng)集或高效用項(xiàng)集的出現(xiàn)具有一定的偶然性.因此，發(fā)現(xiàn)既頻繁又高效用的項(xiàng)集具有重要的理論意義和實(shí)踐價(jià)值.

近兩年新穎的模式挖掘算法越來(lái)越多地被提出，如Min等[15]通過(guò)將字母分為強(qiáng)、中、弱3個(gè)部分，提出了3支挖掘算法，并在3種數(shù)據(jù)集上驗(yàn)證了該算法對(duì)于生物數(shù)據(jù)、時(shí)間序列數(shù)據(jù)和文本數(shù)據(jù)的靈活性和適用性.Dong等[16]以負(fù)序列為研究對(duì)象提出了top-k NSP(top-k Negative Sequential Pattern)算法，并針對(duì)有用負(fù)序列的挖掘方法和減少時(shí)間消耗問(wèn)題提出了2個(gè)解決策略.Wu等[17]為了減少無(wú)用項(xiàng)集的產(chǎn)生，基于網(wǎng)狀樹(shù)結(jié)構(gòu)提出了NetNCSP(Nettree for Nonoverlapping Closed Sequential Pattern)挖掘算法，對(duì)閉序列模式和無(wú)重疊序列模式挖掘都有較好的效果.

本文提出頻繁高效用項(xiàng)集挖掘算法(improved FHM with Support，iFHMS)，該算法是基于傳統(tǒng)高效用項(xiàng)集挖掘算法(Fast High-Utility Miner，F(xiàn)HM)的拓展，通過(guò)構(gòu)建1個(gè)改進(jìn)的共現(xiàn)結(jié)構(gòu)，實(shí)現(xiàn)數(shù)據(jù)庫(kù)中頻繁高效用項(xiàng)集的挖掘.

1 基本知識(shí)

數(shù)據(jù)庫(kù)D由1組事務(wù)Tj(j=1，2，…，m)組成，即D={T1，T2，…，Tm}，每個(gè)Tj都是1個(gè)項(xiàng)集I，由n個(gè)項(xiàng)構(gòu)成，即D={i1，i2，…，in}，項(xiàng)的個(gè)數(shù)為k的項(xiàng)集被稱為k-項(xiàng)集.D中的每條事務(wù)Tj都有且僅有1個(gè)事務(wù)標(biāo)識(shí)符，記作TID.

表1展示的是1個(gè)數(shù)據(jù)庫(kù)實(shí)例，它包含5條事務(wù)(T1，T2，T3，T4，T5)和7個(gè)不同的項(xiàng)(a，b，c，d，e，f，g)，每個(gè)項(xiàng)都有1個(gè)內(nèi)部效用iu(ip，Tj)和外部效用eu(ip)，分別為表1中括號(hào)內(nèi)的數(shù)字和表2中的Profit行中的數(shù)值.

表1 數(shù)據(jù)庫(kù)實(shí)例

表2 項(xiàng)的外部效用

定義1項(xiàng)ip在事務(wù)Tj中的效用u(ip，Tj)，表示為

u(ip，Tj)=iu(ip，Tj)× eu(ip)

(1)

例如，項(xiàng)a在T1中的效用U(a，T1)=1×5=5.

定義2項(xiàng)集X在事務(wù)Tj中的效用U(X，Tj)，表示為

(2)

例如，項(xiàng)集{ac}在T1中的效用U({ac}，T1)=1×5+1×1=6.

定義3項(xiàng)集X在數(shù)據(jù)庫(kù)D中的效用U(X)，表示為

(3)

例如，項(xiàng)集{ac}的效用U({ac})=(1×5+1×1)+(2×5+6×1)+(1×5+1×1)=28.

定義4事務(wù)Tj的效用TU(Tj)，表示為

(4)

例如，T4的效用TU(T4)=4×2+3×1+3×2+1×3=20.

定義5項(xiàng)集X的事務(wù)加權(quán)效用TWU(X)，表示為

(5)

例如，項(xiàng)集{ac}的事務(wù)加權(quán)效用TWU({ac})=TU(T1)+ TU(T2)+ TU(T3)=65.

性質(zhì)1事務(wù)加權(quán)向下閉包屬性.對(duì)于用戶設(shè)定的最小效用閾值mutil，若有TWU(X)

例如，項(xiàng)集{ac}的支持度計(jì)數(shù)Sup({ac})=3.

定義7項(xiàng)集X在事務(wù)Tj中的剩余效用RU(X，Tj).項(xiàng)集X?Tj，數(shù)據(jù)庫(kù)中的所有項(xiàng)按順序?排列，排在X之后的所有項(xiàng)的集合被記為T(mén)j/X，則RU(X，Tj)為集合Tj/X的效用值[2]，即

(6)

例如，假設(shè)?為字典序，有a?b?c?d?e?f?g，則項(xiàng)集{bd}在T3中的剩余效用為[3]

RU({bd}，T3)=u(e，T3)+u(f，T3)=3 + 5=8.

性質(zhì)2支持度向下閉包屬性.假設(shè)用戶設(shè)定的最小支持度閾值minSup，若有Sup(X)≥ minSup，則項(xiàng)集X及其所有非空子集均為頻繁項(xiàng)集；反之，項(xiàng)集X及其所有超集都不是頻繁項(xiàng)集.

問(wèn)題定義：頻繁高效用項(xiàng)集挖掘算法的目的是發(fā)現(xiàn)數(shù)據(jù)庫(kù)中所有效用不小于最小效用閾值并且支持度不小于最小效用閾值的項(xiàng)集[4]，即

FHUIs={X：Sup(X)：U(X)|X?I，Sup(X)≥ minSup，U(X)≥ mutil}.

例如，當(dāng)mutil=40，minSup=2時(shí)，數(shù)據(jù)庫(kù)D的FHUIs={dbec}.

2 iFHMS算法

本文提出的iFHMS算法構(gòu)建了1個(gè)新的數(shù)據(jù)結(jié)構(gòu)——USCS(Utility and Support Co-occurrence Structure)，其對(duì)FHM算法中構(gòu)建的EUCS(Estimated Utility Co-occurrence Structure)做出了2方面的改進(jìn).一方面，USCS在原EUCS的基礎(chǔ)上新增了支持度的存儲(chǔ)；另一方面，USCS不再存儲(chǔ)不滿足效用約束或支持度約束的相應(yīng)2-項(xiàng)集的TWU和支持度.

若對(duì)表1設(shè)定mutil=40，minSup=2，則iFHMS算法構(gòu)建的USCS見(jiàn)表3.

由于iFHMS算法是在FHM算法的基礎(chǔ)上加上了支持度約束，其搜索空間和存儲(chǔ)結(jié)構(gòu)均與FHM算法相同，參考文獻(xiàn)[11]即可，只是在效用列表中新增了1項(xiàng)支持度計(jì)數(shù)的統(tǒng)計(jì)信息，通過(guò)統(tǒng)計(jì)效用列表的TID的總數(shù)獲得.

2.1 剪枝策略

策略1Item剪枝.對(duì)于1-項(xiàng)集X，若有TWU(X)

策略2CS剪枝.對(duì)于2-項(xiàng)集X，若在USCS中，存在TWU(X)

策略3SU剪枝.對(duì)于k-項(xiàng)集X(k≥ 3)，若有∑(iutil+rutil)

實(shí)際上，以上3種剪枝策略都是在效用約束條件的基礎(chǔ)上加入支持度約束條件，只要2個(gè)條件中有1個(gè)不能滿足，就可認(rèn)定該項(xiàng)集及其所有的擴(kuò)展項(xiàng)集一定不是頻繁高效用項(xiàng)集.

對(duì)于策略1和策略2，根據(jù)已有的眾多經(jīng)典頻繁項(xiàng)集挖掘算法和高效用挖掘算法，已經(jīng)充分論證了TWU向下閉包屬性和支持度向下閉包屬性，而從USCS結(jié)構(gòu)的存儲(chǔ)原則來(lái)看，所有TWU或支持度的值小于最小效用閾值或最小支持度閾值的項(xiàng)都已被剔除，被剔除項(xiàng)組成的2-項(xiàng)集一定不滿足TWU和支持度向下閉包屬性，所以包含被剔除2-項(xiàng)集的任意超集都不可能是頻繁高效用項(xiàng)集.

對(duì)于策略3，假設(shè)項(xiàng)集X的超集為X′，則有[5]

所以如果存在U(X)+ RU(X)

綜上，USCS結(jié)構(gòu)以及3個(gè)剪枝策略對(duì)于頻繁高效用項(xiàng)集挖掘是有效的.

2.2 效用列表的構(gòu)建

iFHMS算法同樣需通過(guò)構(gòu)建效用列表結(jié)構(gòu)，并對(duì)其進(jìn)行連接來(lái)實(shí)現(xiàn)頻繁高效用項(xiàng)集的挖掘過(guò)程，根據(jù)策略1構(gòu)建的初始效用列表見(jiàn)圖1.

圖1 初始效用列表

根據(jù)策略3，只對(duì)1-項(xiàng)集syggg00有∑(iutil+rutil)=53>40，即有且僅有項(xiàng)d的擴(kuò)展項(xiàng)集中可能存在頻繁高效用項(xiàng)集，故根據(jù)策略2構(gòu)建2-項(xiàng)集的效用列表，見(jiàn)圖2.

根據(jù)策略3，只有{db}的擴(kuò)展項(xiàng)集中可能存在頻繁高效用項(xiàng)集，故構(gòu)建的3-項(xiàng)集的效用列表如圖3所示.

根據(jù)策略3，只有{dbe}的擴(kuò)展項(xiàng)集中可能存在頻繁高效用項(xiàng)集，故構(gòu)建的4-項(xiàng)集的效用列表如圖4所示.

圖2 2-項(xiàng)集效用列表

圖3 3-項(xiàng)集效用列表

圖4 4-項(xiàng)集效用列表

挖掘過(guò)程結(jié)束，F(xiàn)HUIs={dbec}.

2.3 算法流程介紹

iFHMS算法的實(shí)現(xiàn)過(guò)程見(jiàn) Algorithm 1.算法以用戶數(shù)據(jù)庫(kù)D、設(shè)定最小支持度閾值minSup和最小效用閾值mutil為輸入值.算法首先對(duì)數(shù)據(jù)庫(kù)D進(jìn)行2次掃描，第1次掃描計(jì)算出所有項(xiàng)的支持度和事務(wù)加權(quán)效用TWU；第2次掃描時(shí)根據(jù)策略 1 將Sup

Algorithm 1 iFHMS算法輸入:事務(wù)數(shù)據(jù)庫(kù)D;最小支持度minSup;最小效用閾值mutil輸出:頻繁高效用項(xiàng)集FHUIs1.掃描數(shù)據(jù)庫(kù)D,計(jì)算所有項(xiàng)的Sup和TWU;2.若有Sup(i)≥minSup且TWU(i)≥mutil,則項(xiàng)i∈I?;3.按I?中元素的TWU升序,排列數(shù)據(jù)庫(kù)中的事務(wù);4.掃描更新后的數(shù)據(jù)庫(kù)D,構(gòu)建共現(xiàn)結(jié)構(gòu)和效用列表;5.Search(?,I?,mutil,minSup,USCS).2-項(xiàng)集及k-項(xiàng)集(k≥3)效用列表的構(gòu)建過(guò)程及高效用項(xiàng)集挖掘過(guò)程分別是Algorithm 2和Algorithm 3.Algorithm 2 Search過(guò)程(挖掘過(guò)程)輸入:P.UL:項(xiàng)集P的效用列表;Px.UL:項(xiàng)集P的擴(kuò)展項(xiàng)集Px的效用列表;mutil:最小效用閾值;minSup:最小支持度;USCS:共現(xiàn)結(jié)構(gòu);輸出:頻繁高效用項(xiàng)集FHUIs1.for each Px do if SUM(Px.UL.iutil)≥mutil and Sup(Px)≥minSup then2. OUTPUT Px;3. end if SUM(Px.UL.iutil)+SUM(Px.UL.rutil)≥mutil and Sup(Px)≥minSup then6. exULs=NULL;7. for each Py(y>x)do8. if ?(x,y,c,s)∈USCS 且c≥mutil and s≥minSup then9. Pxy←Px∪Py;10. Pxy.UL←Construct(P,Px,Py);11. Ext(Px)←Ext(Px∪Py);12. end13. end14. Search(Px,Ext(Px),minutil,minSup,USCS);15. end16.end

Algorithm 3 Construct過(guò)程(效用列表構(gòu)建過(guò)程)輸入:P.UL:項(xiàng)集P的效用列表;Px.UL:項(xiàng)集Px的效用列表;Py.UL:項(xiàng)集Py的效用列表(x∈E(P),y∈E(P))輸出:Pxy.UL:項(xiàng)集Pxy的效用列表1.Pxy.UL=NULL;2.foreach ex∈Px.UL do;3.if ? ey∈Py.UL and ex.tid=ey.TID then4. if P.UL≠NULL then5. 查找所有滿足條件e.TID=ex.TID的元素e,e∈P.UL;6. exy=;7. else 8. exy=;9. end10. Pxy.UL←exy;11. end12.end

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

為驗(yàn)證本文提出的iFHMS算法中做出的2個(gè)改進(jìn)之處是否有效，實(shí)驗(yàn)將該算法與SFHM(Fast High-Utility Mining with Support)算法進(jìn)行了對(duì)比，其中，SFHM算法是在FHM[11]算法中增加存儲(chǔ)2-項(xiàng)集支持度的結(jié)構(gòu)ESCS(Estimated Support of Co-occurrence Structure)的變體.實(shí)驗(yàn)環(huán)境：硬件：4G內(nèi)存惠普臺(tái)式電腦；軟件：Ubuntu、Java、Maven.

實(shí)驗(yàn)使用的數(shù)據(jù)集均是從SPMF(見(jiàn)網(wǎng)頁(yè)http://www.philippe-fournier-viger.com/spmf/.)公開(kāi)資源庫(kù)中下載的標(biāo)準(zhǔn)數(shù)據(jù)集，見(jiàn)表4.數(shù)據(jù)集Retail是消費(fèi)記錄數(shù)據(jù)，包含了真實(shí)的外部效用和內(nèi)部效用，采用對(duì)數(shù)正態(tài)分布分別在[1，1 000]和[1，5]之間隨機(jī)產(chǎn)生數(shù)據(jù)集Accident和Mushroom的外部效用和內(nèi)部效用.

表4 數(shù)據(jù)集特性

實(shí)驗(yàn)結(jié)果表明，iFHMS算法在內(nèi)存占用方面基本無(wú)改善，故這里不再討論.

3.1 最小效用閾值對(duì)時(shí)間效率的影響

為研究最小效用閾值對(duì)iFHMS算法挖掘時(shí)間效率的影響，實(shí)驗(yàn)需保持每個(gè)數(shù)據(jù)集的最小支持閾值不變，3個(gè)數(shù)據(jù)集上的最小支持度閾值minSup分別設(shè)為40%、10%、0.05%.iFHMS算法的挖掘時(shí)間t隨最小效用閾值變化情況如圖5所示.

從圖中可以看出，在不同數(shù)據(jù)集上，iFHMS算法的挖掘時(shí)間隨最小效用閾值的增大而逐漸減小，這說(shuō)明該算法是可行的.同時(shí)，iFHMS算法的時(shí)間效率相比對(duì)比算法有一定程度的提升，在3個(gè)不同數(shù)據(jù)集上的平均減少幅度分別為6.69%、7.43%、4.05%.

圖5 不同mutil下算法時(shí)間對(duì)比

3.2 最小支持度閾值對(duì)時(shí)間效率的影響

為探討最小支持度閾值對(duì)iFHMS算法挖掘時(shí)間效率的影響，實(shí)驗(yàn)需在保持每個(gè)數(shù)據(jù)集的最小效用閾值不變的情況下進(jìn)行，3個(gè)數(shù)據(jù)集上的最小效用閾值mutil分別設(shè)為3×106、1×105、200[7].iFHMS算法的挖掘時(shí)間t隨最小支持度閾值變化情況如圖6所示.

圖6 不同minSup下算法時(shí)間對(duì)比

從圖中可以看到，iFHMS算法的挖掘時(shí)間都隨最小支持度閾值的增大而減少，這說(shuō)明該算法對(duì)于挖掘頻繁高效用項(xiàng)集是可行的.并且iFHMS算法的時(shí)間效率是有一定程度的提升的，在3個(gè)數(shù)據(jù)集上的平均提升幅度分別為2.88%、3.01%、2.36%.

3.3 結(jié)果分析

與SFHM算法相比，iFHMS算法在空間和時(shí)間上都能一定程度地減少消耗.因?yàn)槔肬SCS可以同時(shí)對(duì)2-項(xiàng)集的TWU和支持度計(jì)數(shù)進(jìn)行計(jì)算，iFHMS算法一旦發(fā)現(xiàn)某個(gè)值小于其閾值，就進(jìn)行下一個(gè)項(xiàng)集的計(jì)算和判斷，從而避免了需對(duì)某些2-項(xiàng)集的TWU和支持度都構(gòu)建存儲(chǔ)結(jié)構(gòu)并進(jìn)行計(jì)算的可能.比如，在對(duì)數(shù)據(jù)庫(kù)D進(jìn)行挖掘的整個(gè)過(guò)程中，當(dāng)判斷了只有syggg00的擴(kuò)展項(xiàng)集中存在頻繁高效用項(xiàng)集時(shí)，iFHMS算法通過(guò)USCS結(jié)構(gòu)就能直接知道，只需構(gòu)建2-項(xiàng)集{db}、{de}、{dc}的效用列表.但SFHM算法就必須分別計(jì)算{da}、{db}、{dc}、{de}的EUCS和ESCS，并與mutil和minSup比較，才能確定有希望的頻繁高效用2-項(xiàng)集.這就是iFHM算法優(yōu)于SFHM算法的原因所在.

4 結(jié)論

考慮到頻繁高效用項(xiàng)集在實(shí)際生活中的應(yīng)用價(jià)值，本文通過(guò)構(gòu)建一個(gè)改進(jìn)的共現(xiàn)結(jié)構(gòu)USCS，并提出基于此結(jié)構(gòu)的iFHMS算法實(shí)現(xiàn)頻繁高效用項(xiàng)集挖掘.iFHMS算法將EUCS和ESCS結(jié)構(gòu)進(jìn)行合并形成USCS，其優(yōu)勢(shì)主要體現(xiàn)在2-項(xiàng)集效用列表的構(gòu)建過(guò)程中能夠減少?zèng)]有希望的2-項(xiàng)集的效用列表.最后通過(guò)對(duì)比實(shí)驗(yàn)說(shuō)明，iFHMS算法能夠有效發(fā)現(xiàn)數(shù)據(jù)庫(kù)中的頻繁高效用項(xiàng)集，且在時(shí)間效率方面有一定程度的提升.后續(xù)也會(huì)針對(duì)剪枝策略進(jìn)行改進(jìn)，以進(jìn)一步提高算法效率.