基于共現結構的頻繁高效用項集挖掘算法

楊海軍，張博嵐，路永華

(蘭州財經大學 信息工程學院，甘肅 蘭州 730020)

0 引言

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

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

本文提出頻繁高效用項集挖掘算法(improved FHM with Support，iFHMS)，該算法是基于傳統高效用項集挖掘算法(Fast High-Utility Miner，FHM)的拓展，通過構建1個改進的共現結構，實現數據庫中頻繁高效用項集的挖掘.

1 基本知識

數據庫D由1組事務Tj(j=1，2，…，m)組成，即D={T1，T2，…，Tm}，每個Tj都是1個項集I，由n個項構成，即D={i1，i2，…，in}，項的個數為k的項集被稱為k-項集.D中的每條事務Tj都有且僅有1個事務標識符，記作TID.

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

表1 數據庫實例

表2 項的外部效用

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

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

(1)

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

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

(2)

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

定義3項集X在數據庫D中的效用U(X)，表示為

(3)

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

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

(4)

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

定義5項集X的事務加權效用TWU(X)，表示為

(5)

例如，項集{ac}的事務加權效用TWU({ac})=TU(T1)+ TU(T2)+ TU(T3)=65.

性質1事務加權向下閉包屬性.對于用戶設定的最小效用閾值mutil，若有TWU(X)

例如，項集{ac}的支持度計數Sup({ac})=3.

定義7項集X在事務Tj中的剩余效用RU(X，Tj).項集X?Tj，數據庫中的所有項按順序?排列，排在X之后的所有項的集合被記為Tj/X，則RU(X，Tj)為集合Tj/X的效用值[2]，即

(6)

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

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

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

問題定義：頻繁高效用項集挖掘算法的目的是發現數據庫中所有效用不小于最小效用閾值并且支持度不小于最小效用閾值的項集[4]，即

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

例如，當mutil=40，minSup=2時，數據庫D的FHUIs={dbec}.

2 iFHMS算法

本文提出的iFHMS算法構建了1個新的數據結構——USCS(Utility and Support Co-occurrence Structure)，其對FHM算法中構建的EUCS(Estimated Utility Co-occurrence Structure)做出了2方面的改進.一方面，USCS在原EUCS的基礎上新增了支持度的存儲；另一方面，USCS不再存儲不滿足效用約束或支持度約束的相應2-項集的TWU和支持度.

若對表1設定mutil=40，minSup=2，則iFHMS算法構建的USCS見表3.

由于iFHMS算法是在FHM算法的基礎上加上了支持度約束，其搜索空間和存儲結構均與FHM算法相同，參考文獻[11]即可，只是在效用列表中新增了1項支持度計數的統計信息，通過統計效用列表的TID的總數獲得.

2.1 剪枝策略

策略1Item剪枝.對于1-項集X，若有TWU(X)

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

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

實際上，以上3種剪枝策略都是在效用約束條件的基礎上加入支持度約束條件，只要2個條件中有1個不能滿足，就可認定該項集及其所有的擴展項集一定不是頻繁高效用項集.

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

對于策略3，假設項集X的超集為X′，則有[5]

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

綜上，USCS結構以及3個剪枝策略對于頻繁高效用項集挖掘是有效的.

2.2 效用列表的構建

iFHMS算法同樣需通過構建效用列表結構，并對其進行連接來實現頻繁高效用項集的挖掘過程，根據策略1構建的初始效用列表見圖1.

圖1 初始效用列表

根據策略3，只對1-項集g0gggggg有∑(iutil+rutil)=53>40，即有且僅有項d的擴展項集中可能存在頻繁高效用項集，故根據策略2構建2-項集的效用列表，見圖2.

根據策略3，只有{db}的擴展項集中可能存在頻繁高效用項集，故構建的3-項集的效用列表如圖3所示.

根據策略3，只有{dbe}的擴展項集中可能存在頻繁高效用項集，故構建的4-項集的效用列表如圖4所示.

圖2 2-項集效用列表

圖3 3-項集效用列表

圖4 4-項集效用列表

挖掘過程結束，FHUIs={dbec}.

2.3 算法流程介紹

iFHMS算法的實現過程見 Algorithm 1.算法以用戶數據庫D、設定最小支持度閾值minSup和最小效用閾值mutil為輸入值.算法首先對數據庫D進行2次掃描，第1次掃描計算出所有項的支持度和事務加權效用TWU；第2次掃描時根據策略 1 將Sup

Algorithm 1 iFHMS算法輸入:事務數據庫D;最小支持度minSup;最小效用閾值mutil輸出:頻繁高效用項集FHUIs1.掃描數據庫D,計算所有項的Sup和TWU;2.若有Sup(i)≥minSup且TWU(i)≥mutil,則項i∈I?;3.按I?中元素的TWU升序,排列數據庫中的事務;4.掃描更新后的數據庫D,構建共現結構和效用列表;5.Search(?,I?,mutil,minSup,USCS).2-項集及k-項集(k≥3)效用列表的構建過程及高效用項集挖掘過程分別是Algorithm 2和Algorithm 3.Algorithm 2 Search過程(挖掘過程)輸入:P.UL:項集P的效用列表;Px.UL:項集P的擴展項集Px的效用列表;mutil:最小效用閾值;minSup:最小支持度;USCS:共現結構;輸出:頻繁高效用項集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過程(效用列表構建過程)輸入:P.UL:項集P的效用列表;Px.UL:項集Px的效用列表;Py.UL:項集Py的效用列表(x∈E(P),y∈E(P))輸出:Pxy.UL:項集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 實驗及結果分析

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

實驗使用的數據集均是從SPMF(見網頁http://www.philippe-fournier-viger.com/spmf/.)公開資源庫中下載的標準數據集，見表4.數據集Retail是消費記錄數據，包含了真實的外部效用和內部效用，采用對數正態分布分別在[1，1 000]和[1，5]之間隨機產生數據集Accident和Mushroom的外部效用和內部效用.

表4 數據集特性

實驗結果表明，iFHMS算法在內存占用方面基本無改善，故這里不再討論.

3.1 最小效用閾值對時間效率的影響

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

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

圖5 不同mutil下算法時間對比

3.2 最小支持度閾值對時間效率的影響

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

圖6 不同minSup下算法時間對比

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

3.3 結果分析

與SFHM算法相比，iFHMS算法在空間和時間上都能一定程度地減少消耗.因為利用USCS可以同時對2-項集的TWU和支持度計數進行計算，iFHMS算法一旦發現某個值小于其閾值，就進行下一個項集的計算和判斷，從而避免了需對某些2-項集的TWU和支持度都構建存儲結構并進行計算的可能.比如，在對數據庫D進行挖掘的整個過程中，當判斷了只有g0gggggg的擴展項集中存在頻繁高效用項集時，iFHMS算法通過USCS結構就能直接知道，只需構建2-項集{db}、{de}、{dc}的效用列表.但SFHM算法就必須分別計算{da}、{db}、{dc}、{de}的EUCS和ESCS，并與mutil和minSup比較，才能確定有希望的頻繁高效用2-項集.這就是iFHM算法優于SFHM算法的原因所在.

4 結論

考慮到頻繁高效用項集在實際生活中的應用價值，本文通過構建一個改進的共現結構USCS，并提出基于此結構的iFHMS算法實現頻繁高效用項集挖掘.iFHMS算法將EUCS和ESCS結構進行合并形成USCS，其優勢主要體現在2-項集效用列表的構建過程中能夠減少沒有希望的2-項集的效用列表.最后通過對比實驗說明，iFHMS算法能夠有效發現數據庫中的頻繁高效用項集，且在時間效率方面有一定程度的提升.后續也會針對剪枝策略進行改進，以進一步提高算法效率.