一種頻率約束的高效用模式挖掘算法

張全貴 曹 陽(yáng) 李志強(qiáng)

(遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院 遼寧 葫蘆島 125105)

0 引 言

傳統(tǒng)的頻繁模式挖掘只考慮項(xiàng)在事務(wù)中是否出現(xiàn)[1-3]，而忽略了項(xiàng)本身所擁有的效用信息。如:商場(chǎng)中鉆石和牛奶的效用信息差距較大，二者不能同等對(duì)待。因此，基于支持度的頻繁模式挖掘已很難適用于實(shí)際問(wèn)題。從而高效用項(xiàng)目集挖掘方法得到更多的重視[4-8]。效用模式將賦予每個(gè)項(xiàng)不同的權(quán)重并且同一項(xiàng)可以在各個(gè)事務(wù)中重復(fù)出現(xiàn)，這更符合現(xiàn)實(shí)社會(huì)的供應(yīng)和需求。

雖然基于效用的框架大大增強(qiáng)了所得模式的實(shí)用性[9]，但是當(dāng)效用被認(rèn)為是選擇模式的唯一指標(biāo)時(shí)，挖掘出來(lái)的項(xiàng)集有可能是低頻的，這往往對(duì)商家并沒(méi)有太大意義。例如，在商場(chǎng)中，鉆石的利潤(rùn)比普通銀飾高得多，但其銷量要遠(yuǎn)低于普通銀飾。傳統(tǒng)的高效用模式挖掘可能認(rèn)為銷售鉆石是高效用的模式，但是從實(shí)際營(yíng)銷來(lái)看，如果很長(zhǎng)時(shí)間才賣出一件商品，雖然利潤(rùn)很高，但是從長(zhǎng)遠(yuǎn)的角度來(lái)看對(duì)商家并不一定有太大好處。在現(xiàn)實(shí)生活中，僅僅關(guān)注單件商品的利潤(rùn)是不夠的，顧客購(gòu)買的商品頻率對(duì)商家來(lái)說(shuō)也很重要。商家要將兩者綜合考慮來(lái)對(duì)商品進(jìn)行擺放和管理。

因此本文提出了一個(gè)新的高效用模式挖掘算法，目的是將一些頻繁出現(xiàn)的，但因?yàn)樾в弥灯投粋鹘y(tǒng)的高效用模式過(guò)濾掉的模式挖掘出來(lái)。這樣在零售業(yè)的經(jīng)營(yíng)中，可以幫助零售商和店主發(fā)現(xiàn)最有利可圖的產(chǎn)品或產(chǎn)品組合，以便更好地建立能夠獲得高利潤(rùn)的營(yíng)銷策略。

1 相關(guān)工作

目前，已經(jīng)有很多算法對(duì)高效用模式挖掘進(jìn)行了研究。文獻(xiàn)[10]在2004年第一次引入了高效用模式挖掘的概念。隨后，文獻(xiàn)[11]提出了Two-Phase算法，并且提出了TWU(Transaction weighted utilization)模型。該算法通過(guò)層次的方式產(chǎn)生候選項(xiàng)，需要對(duì)數(shù)據(jù)集進(jìn)行多次掃描，時(shí)間和空間的代價(jià)較大。文獻(xiàn)[12]提出IHUP算法，其在增量數(shù)據(jù)庫(kù)中挖掘高效用模式，采用模式增長(zhǎng)的方式生成候選項(xiàng)集，雖然沒(méi)有多次重復(fù)掃描數(shù)據(jù)庫(kù)，但候選模式的數(shù)量還是很多。為了克服這個(gè)問(wèn)題，文獻(xiàn)[13]提出的UP-Growth算法針對(duì)建樹(shù)的方法給出了改進(jìn)策略，減少了候選項(xiàng)的數(shù)目，算法的時(shí)間效率得以提高。

然而，現(xiàn)有的高效用模式挖掘算法[14-16]都不適用于解決本文提出的問(wèn)題。因此，本文針對(duì)UP-Growth算法進(jìn)行改進(jìn)，提出了一種頻率約束的高效用模式挖掘算法。通過(guò)同時(shí)考慮頻率因素和效用因素，對(duì)高效用模式的定義和事務(wù)加權(quán)效用值的計(jì)算公式進(jìn)行了修改，以便能挖掘出更為高效的模式。并通過(guò)優(yōu)化策略，縮小候選項(xiàng)集，提升高效用模式的生成效率。

2 問(wèn)題定義

給定的I={i1,i2,…,im}是數(shù)據(jù)庫(kù)中的項(xiàng)集。設(shè)D={T1,T2,…,Tn}為包含n個(gè)事務(wù)項(xiàng)集。每個(gè)事務(wù)Tc∈D是由I中的項(xiàng)目組成。每個(gè)項(xiàng)ik∈I(1≤k≤m)都包含內(nèi)部效用和外部效用，內(nèi)部效用是指項(xiàng)目的數(shù)量，記作q(ik,Tc)∈(1,2,3,…)。外部效用是指項(xiàng)目的單位效用，記作p(ik)。在數(shù)據(jù)集D中可以用|D|表示事務(wù)的個(gè)數(shù)。表1給出的是數(shù)據(jù)集片段，表2是效用表。

表1 數(shù)據(jù)集片段

表2 效用表

定義1項(xiàng)目ik在事務(wù)Tc中的效用值u(ik,Tc)為:

u(ik,Tc)=p(ik)×q(ik,Tc)

(1)

定義2項(xiàng)集X在事務(wù)Tc中的效用值u(X,Tc)為:

(2)

定義3項(xiàng)集X在整個(gè)數(shù)據(jù)庫(kù)D中的效用值u(X)為:

(3)

定義4一個(gè)事務(wù)Tc的事務(wù)效用值TU(Tc)為:

(4)

定義5在一個(gè)事務(wù)數(shù)據(jù)庫(kù)中，一個(gè)項(xiàng)集X的頻數(shù)是項(xiàng)集X在數(shù)據(jù)庫(kù)中出現(xiàn)的次數(shù)，表示為SN(X)。

項(xiàng)集X的頻率SUP(X)為:

(5)

定義6高效用項(xiàng)集是指項(xiàng)集的效用值乘以項(xiàng)集的頻率不低于用戶指定的最小效用閾值(記作min_uti)的項(xiàng)目集，找到這些項(xiàng)目集就是高效用模式挖掘的目標(biāo)。

定義7一個(gè)項(xiàng)集X的事務(wù)權(quán)重效用值TWU(X)為：

(6)

定義8若TWU(X)≥min_uti，X是候選項(xiàng)集；若TWU(X)

定義9如果不存在u(ik,Tc′)>u(ik,Tc)的事務(wù)Tc′，那么項(xiàng)目ik在交易Tc中的效用被稱為項(xiàng)目的最大效用max(uik)。

性質(zhì)1項(xiàng)集的事務(wù)權(quán)重效用值TWU符合閉包屬性[10]:如果某個(gè)項(xiàng)集是候選項(xiàng)集，那么其非空子集也是一個(gè)候選項(xiàng)集；如果某個(gè)項(xiàng)集是非候選項(xiàng)集，那么其超集也是一個(gè)非候選項(xiàng)集。

性質(zhì)2同一個(gè)項(xiàng)目在不同事務(wù)中的效用可能是不同的，因?yàn)樾枰紤]到每一個(gè)項(xiàng)目數(shù)量。

例如，在表1中，假設(shè)給定的最小效用閾值是50，傳統(tǒng)的高效用模式會(huì)將交易T4中的項(xiàng)集挖掘出來(lái)，而其他項(xiàng)集會(huì)被過(guò)濾掉。然而，在本文定義的高效用模式中，因?yàn)轫?xiàng)集{CDE}在整個(gè)數(shù)據(jù)集中只出現(xiàn)一次，所以u(píng)(CDE)=60×1/6=10，而項(xiàng)集{ABD}在數(shù)據(jù)庫(kù)中出現(xiàn)3次，u(ABD)=(16+8+12) ×3/6=18。假設(shè)將最小效用閾值設(shè)置為15，{ABD}是一種高效用模式。

3 UFCP-Miner算法

本文提出的算法是基于UP-Growth算法進(jìn)行改進(jìn)的，將改進(jìn)后的算法記為UFCP-Miner算法。由于UFCP-Miner算法將頻率因素和效用因素同時(shí)考慮進(jìn)高效用模式挖掘中，因此在創(chuàng)建UFCP-Tree的過(guò)程中，通過(guò)第一次掃描數(shù)據(jù)集，按照定義5給出的公式計(jì)算每項(xiàng)出現(xiàn)的頻數(shù)及其頻率，在計(jì)算TWU時(shí)，根據(jù)定義7將項(xiàng)目頻率和效用值相乘。這樣可以將傳統(tǒng)算法挖掘出來(lái)的低頻高效用模式直接過(guò)濾掉。并且在高效用模式的判斷過(guò)程中，重新計(jì)算真實(shí)效用值和頻率的乘積，這樣也保證了結(jié)果的準(zhǔn)確性。此外，算法在產(chǎn)生候選項(xiàng)集的過(guò)程中，通過(guò)對(duì)項(xiàng)目最大效用值的計(jì)算，可以直接排除一些非候選項(xiàng),以提高算法的性能。UFCP-Miner算法按三個(gè)步驟來(lái)執(zhí)行：

(1) 通過(guò)兩次掃描數(shù)據(jù)集計(jì)算效用值，并將事務(wù)項(xiàng)集整理到UFCP-Tree上。

(2) 通過(guò)創(chuàng)建條件模式基依次從UFCP-Tree中找到候選項(xiàng)目集。

(3) 從得到的候選項(xiàng)目集中判斷哪些是高效用項(xiàng)目集。

3.1 創(chuàng)建UFCP-Tree

算法采用樹(shù)結(jié)構(gòu)來(lái)保存項(xiàng)目集的所有信息。通過(guò)一個(gè)頭表來(lái)實(shí)現(xiàn)樹(shù)的遍歷。節(jié)點(diǎn)的第一個(gè)位置存儲(chǔ)的是項(xiàng)目名，第二個(gè)數(shù)代表項(xiàng)目對(duì)應(yīng)的頻數(shù)，第三個(gè)數(shù)代表項(xiàng)目對(duì)應(yīng)的效用值。創(chuàng)建UFCP-Tree的過(guò)程算法如下：

算法1

輸入：事務(wù)數(shù)據(jù)庫(kù)D；

用戶最小效用閾值min_uti。

輸出：UFCP-Tree。

1) 掃描D中所有事務(wù)，計(jì)算每項(xiàng)的SN，SUP，TWU;

2)forD中的每個(gè)事務(wù)Tcdo;

3)forTc中的每個(gè)項(xiàng)ikdo;

4)If(twu≤min_uti)then;

5) 刪除該項(xiàng);

6)Endfor

7)Endfor

8) 對(duì)Tc中剩余項(xiàng)按TWU值降序排序;

9) 將D中不在頭表中的項(xiàng)刪除;

10) 將D中保留下來(lái)的項(xiàng)按表中的順序進(jìn)行排序;

11) 重新計(jì)算每項(xiàng)的TWU值;

12) 將事務(wù)項(xiàng)集按順序添加到UFCP-Tree上;

13)End

例如，本文以表1和表2中列出的數(shù)據(jù)為例, 這里設(shè)定15為最小閾值。通過(guò)第一次掃描數(shù)據(jù)集，結(jié)果如圖1(a)所示。因?yàn)镕、G的TWU值小于15，所以，F(xiàn)、G被刪除。排序后的結(jié)果如圖1(b)所示。刪除不在H1中的項(xiàng)，重組后的事務(wù)如表3所示。圖1(c)給出了重新計(jì)算后的TWU值。然后將表3中的事務(wù)依次添加到UFCP-Tree上，如圖1(d)所示。

圖1 UFCP-Tree的構(gòu)建

表3 重組的數(shù)據(jù)集

在掃描數(shù)據(jù)集的過(guò)程中，UFCP-Miner算法還計(jì)算了各項(xiàng)在數(shù)據(jù)庫(kù)中的最大效用值[17]，如表4所示。

表4 項(xiàng)最大效用表

3.2 產(chǎn)生候選項(xiàng)集

創(chuàng)建好UFCP-Tree之后，就是如何產(chǎn)生候選高效用項(xiàng)目集。算法首先從頭表底部開(kāi)始依次處理每一項(xiàng),若其估計(jì)效用值高于min_util，為項(xiàng)目創(chuàng)建條件模式基，并為當(dāng)前條件模式基創(chuàng)建子頭表。根據(jù)子頭表中的數(shù)據(jù)，為其創(chuàng)建條件效用子樹(shù)，然后統(tǒng)計(jì)每一項(xiàng)的最大效用，若最大效用小于假定的最小效用閾值，該項(xiàng)就不是一個(gè)候選項(xiàng)集[17]，同時(shí)刪除子頭表中小于最小效用閾值的項(xiàng)。最后按順序依次處理子頭表中的所有項(xiàng)，直到挖掘出全部候選項(xiàng)集。算法如下：

算法2

Input: A UFCP-TreeTx, a header tableHxforTxand an itemsetX

Output: All PHUIs inTx

ProcedureUFCP(Tx,Hx,X)

1)ForeachitemikinHxdo

2)Foreachentrynjfor the itemikinTxdo

3) estimate utility+=nj.utility;

4)Endfor

5)If(estimate utility≥min_uti)then

6) Generate a PHUIY=X∪ik;

7) Construct Y’s conditional pattern base Y-CPB;

8) Calculated Y’s maximum utility according to maximum item utility table

9) Remove unpromising items inHy;

10)IfTy≠nullthencallUFCP(Ty,Hy,Y);

11)Endfor

例如，根據(jù)圖1(c)，首先考慮項(xiàng){B},由于其估計(jì)效用值(即36)高于min_uti，因此為B創(chuàng)建條件模式基。B的最大效用是將項(xiàng)目B的最大效用值乘以項(xiàng)目B的頻數(shù)，再乘以項(xiàng)目B的頻率，即3×3×0.5=4.5，由于4.5<15，則{B}不是一個(gè)候選項(xiàng)集。通過(guò)掃描UFCP-Tree上節(jié)點(diǎn)“B”到根節(jié)點(diǎn)路徑上的所有項(xiàng)，一條路徑{B-A-D}被發(fā)現(xiàn)，計(jì)算出每項(xiàng)的路徑效用，即重組的數(shù)據(jù)集中包含項(xiàng)集(BAD)的事務(wù)效用和，記為PU。為了方便起見(jiàn)，因?yàn)槊織l路徑中都必須包含“B”，所以表中只保存除了“B”以外的其余項(xiàng)。如圖2所示。最終可以得到和項(xiàng)“B”相關(guān)的候選項(xiàng)集有{BA}{BD}{BAD}。

圖2 子頭表和子樹(shù)的構(gòu)建

3.3 得到高效用模式

第三次掃描數(shù)據(jù)庫(kù)，將所有候選項(xiàng)集的真實(shí)效用值統(tǒng)計(jì)出來(lái)，并將其與項(xiàng)集的頻率相乘，若結(jié)果大于給定的最小效用閾值，該項(xiàng)集就是高效用項(xiàng)集。

4 實(shí) 驗(yàn)

4.1 實(shí)驗(yàn)介紹

為了檢驗(yàn)算法的性能，本文將提出的算法和經(jīng)典的UP-Growth算法進(jìn)行了對(duì)比分析。實(shí)驗(yàn)采用的系統(tǒng)是64位的Windows 7，內(nèi)存為4 GB，處理器Intel Core i5-2450M CPU 2.50 GHz，算法是由Python語(yǔ)言編程實(shí)現(xiàn)。

實(shí)驗(yàn)采用四個(gè)典型數(shù)據(jù)集對(duì)算法進(jìn)行實(shí)驗(yàn)分析，表5列出了各個(gè)數(shù)據(jù)集的參數(shù)。由于所選數(shù)據(jù)集都不包含項(xiàng)的內(nèi)部及外部效用值, 因此采用文獻(xiàn)[18-19]中的方法，每個(gè)事務(wù)中項(xiàng)目的個(gè)數(shù)由1到5隨機(jī)生成，項(xiàng)目的單位效用值由1到1 000隨機(jī)生成。由于在現(xiàn)實(shí)生活中，相對(duì)來(lái)說(shuō)單位效用值高的項(xiàng)目較少，這里隨機(jī)產(chǎn)生的單位效用值的數(shù)量服從對(duì)數(shù)正態(tài)分布。為了確保實(shí)驗(yàn)結(jié)果的客觀性，每個(gè)實(shí)驗(yàn)結(jié)果都是采用運(yùn)行多次取其平均值的方法。

表5 數(shù)據(jù)集特征

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

圖3給出了在四個(gè)不同的數(shù)據(jù)集上，通過(guò)設(shè)置不同的最小效用閾值，挖掘出高效用模式的數(shù)量和運(yùn)行時(shí)間。很明顯隨著最小效用閾值的提高，候選項(xiàng)的數(shù)量隨之變少，因此需要更少的運(yùn)行時(shí)間。在圖3(a)的實(shí)驗(yàn)中，當(dāng)閾值從30%提高到35%的時(shí)候，算法的運(yùn)行時(shí)間會(huì)急劇減少，這是因?yàn)殡S著閾值變化生成的候選項(xiàng)數(shù)量明顯變少，所以在最后判斷時(shí)只需要計(jì)算少量的項(xiàng)集頻率。而在稀疏數(shù)據(jù)集Foodmart上進(jìn)行測(cè)試時(shí)，如圖3(c)所示，隨著閾值的提高候選項(xiàng)數(shù)量也在減少，但時(shí)間增長(zhǎng)的相對(duì)平穩(wěn)，主要是因?yàn)樵揊oodmart中事務(wù)項(xiàng)集平均長(zhǎng)度只有4.4，所以計(jì)算候選項(xiàng)集的頻率的時(shí)間會(huì)遠(yuǎn)少于事務(wù)項(xiàng)集平均長(zhǎng)度較長(zhǎng)的數(shù)據(jù)集。因此，算法的運(yùn)行時(shí)間變化相對(duì)平緩。

(a) Chess

(b) Mushroom

(c) Foodmart

(d) Retail圖3 運(yùn)行時(shí)間和候選項(xiàng)數(shù)量

因?yàn)楸疚氖菫榱送诰虺龈咝в玫捻?xiàng)集而重新定義了高效用模式，所以將提出的算法和經(jīng)典的高效用挖掘算法UP-Growth在挖掘結(jié)果的效用值上進(jìn)行了對(duì)比分析。首先將UP-Growth算法挖掘出來(lái)的高效用項(xiàng)集與項(xiàng)集對(duì)應(yīng)的頻率相乘，然后取兩種算法挖掘結(jié)果的前10、20、30、40、50個(gè)模式的效用和在兩個(gè)稀疏和兩個(gè)稠密數(shù)據(jù)集上進(jìn)行對(duì)比，如圖4所示。由圖可以很明顯看出，提出的算法和UP-Growth算法在所得模式的效用值上有較大差異，并且數(shù)據(jù)越稠密，項(xiàng)集平均長(zhǎng)度越大，差異越明顯。主要是因?yàn)閁P-Growth算法挖掘出來(lái)的模式可能是低頻的，所以乘以頻率之后結(jié)果要小于UFCP算法得到的結(jié)果。UFCP算法挖掘出的結(jié)果是具有高頻率的高效用模式，使最終結(jié)果會(huì)優(yōu)于UP-Growth算法。此外，隨著模式的增多，效用值差距也會(huì)變大。

(a) Chess

(b) Mushroom

(c) Foodmart

(d) Retail圖4 模式的效用

綜上所述，UFCP-Miner算法在傳統(tǒng)高效用模式的基礎(chǔ)上加入頻率因素，從而獲得更為高效的模式。此外，在產(chǎn)生候選項(xiàng)集的過(guò)程中，通過(guò)優(yōu)化算法，過(guò)濾掉了一些非候選項(xiàng)集，使得運(yùn)行時(shí)間相對(duì)減少。但UFCP-Miner算法在計(jì)算項(xiàng)集頻率時(shí)仍會(huì)消耗一定的時(shí)間。

5 結(jié) 語(yǔ)

本文通過(guò)對(duì)現(xiàn)有高效用模式挖掘算法的分析，提出了一種頻率約束的高效用模式挖掘算法。基于實(shí)際問(wèn)題重新定義了高效用模式，在挖掘過(guò)程中考慮項(xiàng)集在整個(gè)數(shù)據(jù)庫(kù)中出現(xiàn)的頻率，將那些出現(xiàn)頻率較高但因效用值偏低而被過(guò)濾的模式挖掘出來(lái)并過(guò)濾掉低頻的模式。實(shí)驗(yàn)采用4個(gè)典型數(shù)據(jù)集，實(shí)驗(yàn)結(jié)果也證明了本文提出的算法在挖掘結(jié)果上不同于傳統(tǒng)的高效用模式挖掘，這樣的挖掘結(jié)果對(duì)商家來(lái)說(shuō)更有意義。未來(lái)的工作是進(jìn)一步優(yōu)化算法的時(shí)間復(fù)雜度，并將此算法遷移到高效用序列模式挖掘領(lǐng)域。