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

張全貴 曹 陽 李志強

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

0 引 言

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

雖然基于效用的框架大大增強了所得模式的實用性[9]，但是當效用被認為是選擇模式的唯一指標時，挖掘出來的項集有可能是低頻的，這往往對商家并沒有太大意義。例如，在商場中，鉆石的利潤比普通銀飾高得多，但其銷量要遠低于普通銀飾。傳統的高效用模式挖掘可能認為銷售鉆石是高效用的模式，但是從實際營銷來看，如果很長時間才賣出一件商品，雖然利潤很高，但是從長遠的角度來看對商家并不一定有太大好處。在現實生活中，僅僅關注單件商品的利潤是不夠的，顧客購買的商品頻率對商家來說也很重要。商家要將兩者綜合考慮來對商品進行擺放和管理。

因此本文提出了一個新的高效用模式挖掘算法，目的是將一些頻繁出現的，但因為效用值偏低而被傳統的高效用模式過濾掉的模式挖掘出來。這樣在零售業的經營中，可以幫助零售商和店主發現最有利可圖的產品或產品組合，以便更好地建立能夠獲得高利潤的營銷策略。

1 相關工作

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

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

2 問題定義

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

表1 數據集片段

表2 效用表

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

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

(1)

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

(2)

定義3項集X在整個數據庫D中的效用值u(X)為:

(3)

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

(4)

定義5在一個事務數據庫中，一個項集X的頻數是項集X在數據庫中出現的次數，表示為SN(X)。

項集X的頻率SUP(X)為:

(5)

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

定義7一個項集X的事務權重效用值TWU(X)為：

(6)

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

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

性質1項集的事務權重效用值TWU符合閉包屬性[10]:如果某個項集是候選項集，那么其非空子集也是一個候選項集；如果某個項集是非候選項集，那么其超集也是一個非候選項集。

性質2同一個項目在不同事務中的效用可能是不同的，因為需要考慮到每一個項目數量。

例如，在表1中，假設給定的最小效用閾值是50，傳統的高效用模式會將交易T4中的項集挖掘出來，而其他項集會被過濾掉。然而，在本文定義的高效用模式中，因為項集{CDE}在整個數據集中只出現一次，所以u(CDE)=60×1/6=10，而項集{ABD}在數據庫中出現3次，u(ABD)=(16+8+12) ×3/6=18。假設將最小效用閾值設置為15，{ABD}是一種高效用模式。

3 UFCP-Miner算法

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

(1) 通過兩次掃描數據集計算效用值，并將事務項集整理到UFCP-Tree上。

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

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

3.1 創建UFCP-Tree

算法采用樹結構來保存項目集的所有信息。通過一個頭表來實現樹的遍歷。節點的第一個位置存儲的是項目名，第二個數代表項目對應的頻數，第三個數代表項目對應的效用值。創建UFCP-Tree的過程算法如下：

算法1

輸入：事務數據庫D；

用戶最小效用閾值min_uti。

輸出：UFCP-Tree。

1) 掃描D中所有事務，計算每項的SN，SUP，TWU;

2)forD中的每個事務Tcdo;

3)forTc中的每個項ikdo;

4)If(twu≤min_uti)then;

5) 刪除該項;

6)Endfor

7)Endfor

8) 對Tc中剩余項按TWU值降序排序;

9) 將D中不在頭表中的項刪除;

10) 將D中保留下來的項按表中的順序進行排序;

11) 重新計算每項的TWU值;

12) 將事務項集按順序添加到UFCP-Tree上;

13)End

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

圖1 UFCP-Tree的構建

表3 重組的數據集

在掃描數據集的過程中，UFCP-Miner算法還計算了各項在數據庫中的最大效用值[17]，如表4所示。

表4 項最大效用表

3.2 產生候選項集

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

算法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

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

圖2 子頭表和子樹的構建

3.3 得到高效用模式

第三次掃描數據庫，將所有候選項集的真實效用值統計出來，并將其與項集的頻率相乘，若結果大于給定的最小效用閾值，該項集就是高效用項集。

4 實 驗

4.1 實驗介紹

為了檢驗算法的性能，本文將提出的算法和經典的UP-Growth算法進行了對比分析。實驗采用的系統是64位的Windows 7，內存為4 GB，處理器Intel Core i5-2450M CPU 2.50 GHz，算法是由Python語言編程實現。

實驗采用四個典型數據集對算法進行實驗分析，表5列出了各個數據集的參數。由于所選數據集都不包含項的內部及外部效用值, 因此采用文獻[18-19]中的方法，每個事務中項目的個數由1到5隨機生成，項目的單位效用值由1到1 000隨機生成。由于在現實生活中，相對來說單位效用值高的項目較少，這里隨機產生的單位效用值的數量服從對數正態分布。為了確保實驗結果的客觀性，每個實驗結果都是采用運行多次取其平均值的方法。

表5 數據集特征

4.2 實驗結果分析

圖3給出了在四個不同的數據集上，通過設置不同的最小效用閾值，挖掘出高效用模式的數量和運行時間。很明顯隨著最小效用閾值的提高，候選項的數量隨之變少，因此需要更少的運行時間。在圖3(a)的實驗中，當閾值從30%提高到35%的時候，算法的運行時間會急劇減少，這是因為隨著閾值變化生成的候選項數量明顯變少，所以在最后判斷時只需要計算少量的項集頻率。而在稀疏數據集Foodmart上進行測試時，如圖3(c)所示，隨著閾值的提高候選項數量也在減少，但時間增長的相對平穩，主要是因為該Foodmart中事務項集平均長度只有4.4，所以計算候選項集的頻率的時間會遠少于事務項集平均長度較長的數據集。因此，算法的運行時間變化相對平緩。

(a) Chess

(b) Mushroom

(c) Foodmart

(d) Retail圖3 運行時間和候選項數量

因為本文是為了挖掘出更高效用的項集而重新定義了高效用模式，所以將提出的算法和經典的高效用挖掘算法UP-Growth在挖掘結果的效用值上進行了對比分析。首先將UP-Growth算法挖掘出來的高效用項集與項集對應的頻率相乘，然后取兩種算法挖掘結果的前10、20、30、40、50個模式的效用和在兩個稀疏和兩個稠密數據集上進行對比，如圖4所示。由圖可以很明顯看出，提出的算法和UP-Growth算法在所得模式的效用值上有較大差異，并且數據越稠密，項集平均長度越大，差異越明顯。主要是因為UP-Growth算法挖掘出來的模式可能是低頻的，所以乘以頻率之后結果要小于UFCP算法得到的結果。UFCP算法挖掘出的結果是具有高頻率的高效用模式，使最終結果會優于UP-Growth算法。此外，隨著模式的增多，效用值差距也會變大。

(a) Chess

(b) Mushroom

(c) Foodmart

(d) Retail圖4 模式的效用

綜上所述，UFCP-Miner算法在傳統高效用模式的基礎上加入頻率因素，從而獲得更為高效的模式。此外，在產生候選項集的過程中，通過優化算法，過濾掉了一些非候選項集，使得運行時間相對減少。但UFCP-Miner算法在計算項集頻率時仍會消耗一定的時間。

5 結 語

本文通過對現有高效用模式挖掘算法的分析，提出了一種頻率約束的高效用模式挖掘算法。基于實際問題重新定義了高效用模式，在挖掘過程中考慮項集在整個數據庫中出現的頻率，將那些出現頻率較高但因效用值偏低而被過濾的模式挖掘出來并過濾掉低頻的模式。實驗采用4個典型數據集，實驗結果也證明了本文提出的算法在挖掘結果上不同于傳統的高效用模式挖掘，這樣的挖掘結果對商家來說更有意義。未來的工作是進一步優化算法的時間復雜度，并將此算法遷移到高效用序列模式挖掘領域。