基于DBP的Top-k高效用項集挖掘算法

蔣 華，路昕宇，王慧嬌，宋佳璐

(1.桂林電子科技大學 廣西可信軟件重點實驗室，廣西 桂林 541004； 2.西安郵電大學 計算機學院，陜西 西安 710061)

0 引 言

近年來高效用項集挖掘[1-4]成為數據挖掘領域的重要研究方向。Top-k高效用項集挖掘巧妙地將設定最小效用閾值的問題轉變為設定所需高效用項集數量的問題，因此受到廣泛關注。

由于多次掃描數據庫并且產生大量候選集的缺點，以TKU算法[5]和REPT算法[6]為代表，二階段算法逐漸被一階段算法替代。一階段算法則通過改進數據結構方式去解決二階段算法的問題。TKO算法[5]采用效用鏈表結構，在算法第一次掃描數據庫時將關鍵信息存入效用鏈表，之后只需掃描效用鏈表信息，通過連接操作和遞歸效用鏈表構建過程挖掘高效用項集。TOPKHUP[7]算法提出HUP-Tree結構，將事務效用保存到樹結構中，使用HUP-Tree計算項集效用。TKHUP[8]算法采用投影方式將事務效用鏈表投影到投影表，并通過4種策略操作子投影表構建過程挖掘Top-k高效用項集。KHMC[9]算法在TKO算法基礎上提出多種修剪策略降低候選集產生。Vert_Top-k DS[10]算法加入滑動窗口模式可以處理流數據。RHUM算法[11]提出重用鏈表R-list結構降低內存消耗。

上述Top-k高效用項集算法挖掘時需要不斷合并項集構造效用鏈表，卻忽略管理內存空間的效用鏈表，導致算法內存消耗量大，運行時間長。因此本文提出數據緩沖池(data buffer pool，DBP)結構的高效用項集挖掘算法TKBPH。算法將效用鏈表存儲在數據緩沖池并由索引鏈表記錄其位置，挖掘過程中通過直接訪問索引鏈表讀取效用鏈表位置，在數據緩沖池動態插入和刪除效用鏈表，降低內存空間消耗，提升算法效率。

1 相關定義及問題陳述

設由m個項組成的項集I={i1,i2,i3,…,im}，則項集長度為m或稱為m-項集。設事務數據庫D={T1,T2,T3,…,Tn}，對于每個事務Tk(1≤k≤n)都由I的子集組成。項集I中的每個項ik(1≤k≤m)都與有內部效用qi(數量)和外部效用pi(利潤)與之關聯，如表1所示，事務T1中的項a和項b的內部效用分別為2和1。項的外部效用見表2。

表1 事務數據庫

表2 外部效用

定義1 令事務Tk中項i的效用為u(i,Tk),u(i,Tk)=p(i)×q(i,Tk)。

定義2 令事務Tk中項集X的效用為u(X,Tk)，u(X,Tk)=∑i∈Xu(i,Tk)。

定義3 令數據庫D中項集X的效用為u(X)，u(X)=∑X?Tk?Du(X,Tk)。

定義4 令事務Tk的事務效用為Tk中項集效用值之和，記作TU(Tk)=∑i∈Tku(i,Tk)。

定義5 用戶給定最小效用閾值minUtil，如果項集X的效用u(X)≥minUtil，則稱項集X為高效用項集，反之則稱項集X為低效用項集。

頻繁項集挖掘算法中基于支持度的反單調性。修剪搜索空間的方式不能直接用于效用度量來挖掘高效用項集。高效用項集挖掘算法通常采用事務加權效用(transition weighted utility，TWU)度量高估項集效用來解決這個問題。事務加權效用度量假定所有項的外部效用均為正值，定義如下。

定義6 設項集X的事務加權效用為所有包含項集X的事務效用之和，記作TWU(X)=∑Tk∈g(x)TU(Tk)。

性質1 項集X的事務加權效用不低于它的效用，TWU(X)≥u(X)

性質2 如果項集X的事務加權效用TWU(X)

定義7 令項集I為數據庫D中所有項的集合并以事務加權效用值升序排列。數據庫D中項集X的效用鏈表記作PX.UL，效用鏈表由(tid,iutil,rutil)形式的元組構成。tid為事務Tk的唯一標識符，iutil為事務Tk中項集X的效用，rutil為事務Tk中除項集X外其余項集效用之和，記作∑i∈Ttid∧i?x?x∈Xu(i,Ttid)。

性質3 項集X的效用為u(X)可以通過效用鏈表中iutil值的總和來計算。如果iutil之和SumIutil小于min-Util，那么項集X為低效用項集。否則，項集X是高效用項集。

定義8 數據庫D的評估效用共現結構(estimated utility co-occurrence structure，EUCS)記作EUCSD，EUCSD={(a,b,TWU(ab))∈I*×I*×R+}，I*是數據庫D中不小于最小效用閾值minUtil的項集。

2 基于DBP的Top-K高效用項集挖掘算法

2.1 DBP結構

為了有效管理項集挖掘過程中的內存管理，提高內存復用率，降低系統內存空間消耗，本文提出數據緩沖池(data buffer pool，DBP)結構用于管理Top-k高效用項集挖掘過程的內存空間，具體定義如下：

定義9 令I為數據庫D中所有項的集合，TidD為數據庫中所有事務標識符的集合，數據庫D的數據緩沖池結構記作DBP。DBP采用(tid∈TidD,iutil∈R,rutil∈R)的元組形式存儲效用鏈表，這些元組稱為數據段。

為了快速訪問和維護存儲在數據緩沖池的相關信息，采用索引鏈表存儲數據段在數據緩沖池的位置信息和效用信息，索引鏈表定義如下：

定義10 令X為數據庫D中的項集，IndexList(X)為項集X相關信息的索引鏈表，IndexListD={IndexList(X),X?I}。IndexList(X)存儲的元組形式為(X,StartPos,EndPos,SumIutil,SumRutil)。其中StartPos和EndPos元素分別表示數據緩沖池中數據段起始位置和結束位置。SumIutil元素存儲效用鏈表PX.UL中iutil之和。SumRutil元素存儲效用鏈表PX.UL中rutil之和。

在應用數據緩沖池結構中，TKBPH算法創建4個鏈表，分別是Tids、Iutils、Rutils和IndexList。前3個鏈表存儲數據段，IndexList索引鏈表記錄數據段的位置信息和效用信息。如圖1所示，項g的效用為u(g,T5)=8，剩余效用為ru(g,T5)=29，項g只出現在事務T5，所以項g只有一個數據段為(5,8,29)。由于g是第一個插入IndexList索引鏈表的項，起始位置StartPos和結束位置EndPos分別為0和1，總效用之和SumIutil為8，剩余效用之和SumRutil為29。

圖1 數據緩沖池中的項g

在挖掘過程開始時，TKBPH算法將這4個鏈表初始化為空并將單一項的效用鏈表分別存放在4個鏈表。隨著挖掘過程的進行，項集的效用鏈表全部插入到數據緩沖池。>如圖2所示，表1中所有項的效用鏈表均存儲在數據緩沖池。

圖2 插入項集后的數據緩沖池

當數據緩沖池初始化的內存空間已滿，數據緩沖池會自動擴充內存空間存放效用鏈表。當數據緩沖池中的效用鏈表不在被挖掘過程所需要時，數據緩沖池會釋放相應的效用鏈表，將回收的內存空間重新分配給需要插入的效用鏈表，同時更新IndexList索引鏈表中效用鏈表的位置信息。

在進入搜索子程序時發現項集X和X的分支項集可能是一個潛在的高效用項集，TKBPH算法通過將項集X的效用鏈表臨時插入到數據緩沖池尾部，并記錄存儲其存放位置StartPos和EndPos。當需要查找項集X的效用鏈表時，TKBPH算法可以直接訪問索引鏈表中StartPos和EndPos信息讀取相關數據。假設TKBPH算法正在處理項集g0gggggg，通過索引鏈表IndexList查詢項集g0gggggg的信息，根據StartPos和EndPos的位置信息直接訪問數據緩沖池g0gggggg的效用鏈表。當搜索子程序完成對項集X的效用鏈表搜索時，算法將數據緩沖池分配給項集X效用鏈表的臨時內存重新分配給其它需要被搜索的項集效用鏈表，提高內存復用率。具體數據緩沖池構建過程見算法1。

算法1：數據緩沖池構建過程

輸入：數據緩沖池DBP，索引鏈表IndexList，項集P，Px，Py

輸出：更新數據緩沖池DBP和索引鏈表IndexList中的Pxy

設PPnt，PxPnt，PyPnt分別為索引鏈表IndexList(P).StartPos，IndexList(Px).StartPos，IndexList(Py).StartPos起始位置的3個指針同時指向數據緩沖池DBP。

(1)如果指針PxPnt指向元組中Tids小于指針PyPnt指向元組中Tids，那么將指針PxPnt向右移動一位；

(2)如果指針PxPnt指向元組中Tids大于指針PyPnt指向元組中Tids，那么將指針PyPnt向右移動一位；

(3)如果指針PxPnt指向元組中Tids等于指針PyPnt指向元組中Tids并且索引鏈表IndexList(P)不為空，那么指針PPnt連續向右移動，直到指針PPnt移動到IndexList(P)的結束位置或者指針PPnt指向元組中Tids和指針PxPnt指向元組中Tids相同；

(4)數據緩沖池DBP的尾部添加一個新元組，令Tids為指針PxPnt指向的Tids，Iutils為指針PxPnt指向的Iutils加指針PyPnt指向的Iutils減去指針PPnt指向的Iutils，Rutils為指針PyPnt指向的Rutils；

(5)當指針PxPnt沒有指向索引鏈表IndexList(Px)的結束位置EndPos，并且指針PyPnt沒有指向索引鏈表IndexList(Py)的結束位置EndPos時，返回步驟(1)；

(6)更新索引鏈表Pxy和數據緩沖池IndexList。

2.2 TKBPH算法

TKBPH算法是一階段高效用項集挖掘算法，即算法在執行過程中僅需掃描一次數據庫計算項集的加權事務效用值。數據庫中項集的效用鏈表全部存入數據緩沖池，并將相關信息存入索引鏈表IndexList。挖掘過程時將需要挖掘項集X的效用鏈表依次插入數據緩沖池尾部，完成挖掘后不再需要項集X的效用鏈表時，TKBPH算法將數據緩沖池中分配給項集X的效用鏈表臨時內存空間回收并重新分配給其它需要挖掘的效用鏈表。

TKBPH算法主要分為3步，第一步掃描數據庫計算單一項的加權事務效用值并按升序排列；第二步建立數據緩沖池DBP和索引鏈表IndexList；第三步調用搜索子程序Search挖掘高效用項集，通過用戶設定的k值，不斷更新最小效用閾值minUtil，挖掘出前k個高效用項集，整體算法見算法2。

算法2：TKBPH算法

輸入：事務數據庫D，k值

輸出：高效用項集

(1)初次掃描事務數據庫D并計算單一項的加權事務效用值，將最小效用閾值minUtil初始化為0；

(2)將單一項的效用鏈表存入初始化鏈表I*并按加權事務效用值升序排列；

(3)再次掃描數據庫D，數據緩沖池DBP和索引鏈表IndexList，建立EUCS結構，創建高效用項集隊列；

(4)調用搜索子程序Search，將初始化鏈表I*、EUCS結構、數據緩沖池DBP和索引鏈表IndexList傳入子程序Search；

(5)輸出前k個高效用項集。

搜索子程序Search是一個遞歸過程，根據之前算法得到的項集P和P的分支項集，挖掘高效用項集。在算法挖掘過程中通過性質2和性質3，判斷項集P和項集P的分支項集是否為高效用項集。如果項集P為高效用項集則將項集P加入到高效用項集鏈表。如果項集P的分支項集為高效用項集，那么通過調用數據緩沖池構建過程挖掘高效用項集，直到遍歷完所有項集。具體實現見算法3。

算法3：搜索子程序Search

輸入：初始化鏈表I*，EUCS結構，數據緩沖池DBP，索引鏈表IndexList，項集P和P的分支項集

輸出：高效用項集

(1)對于每一個項集P的分支項集Px，如果索引鏈表IndexList(Px)的SumIutil不小于最小效用閾值minUtil，那么將項集Px加入到高效用項集隊列。在項集Px加入之前判斷隊列長度是否大于k值，若小于k值，直接將項集Px插入隊列；若隊列長度大于k值，則比較項集Px的效用值和高效用隊列中的最小值。如果項集Px的效用值小于高效用隊列中的最小值，則不插入隊列。如果項集Px的效用值大于高效用隊列中的最小值，則刪除最小值的項集，插入項集Px并將minUtil更新為高效用項集最新的最小值；

(2)如果項集Px的索引鏈表IndexList(Px)中的SumIutil與SumRutil之和不小于最小效用閾值minUtil，那么Px的分支項集則可能是高效用項集；

(3)對于每個項集P的分支項集Py，Py與Px合并使得y>x并且TWU({x,y})≥minUtil，形成新的Pxy分支繼續執行；

(4)將項集P，Px，Py，數據緩沖池DBP，索引鏈表IndexList作為參數調用數據緩沖池構建過程；

(5)完成數據緩沖池構建后，若Pxy鏈表不為空，則Pxy及其分支項集將被搜索進程Search繼續挖掘，不斷地遞歸此程序直到沒有分支項集。

2.3 算法性能分析

從內存空間方面分析，TKBPH算法采用數據緩沖池進行高效內存管理，在挖掘開始時將單一項效用鏈表一次性插入到數據緩沖池。在搜索子程序Search挖掘分支項集時僅需在數據緩沖池尾部臨時插入需要挖掘的項集效用鏈表，搜索子程序Search完成對該項集效用鏈表的挖掘時回收該項集所占用內存空間重新分配給其它需要挖掘的項集效用鏈表，極大地提高內存復用率，減少內存空間浪費。

從時間復雜度方面分析，TKBPH算法在輸入數據集后，算法的第一步是計算單一項的TWU值，需要掃描一次數據庫，設數據庫D有m個事務，其中最大事務包含n個項，時間復雜度為O(mn)。在之前算法中，通過某些子集的效用鏈表相交構造項集的效用鏈表。對于鏈表Px.UL中每個元組都需要在鏈表Py.UL二分查找是否存在相同元組。設s和t分別為Px.UL和Py.UL，則效用鏈表構建過程的時間復雜度表示為O(slogn)。TKBPH算法提出數據緩沖池結構，將數據緩沖池的數據段位置信息記錄在索引鏈表。通過讀取索引鏈表，TKBPH算法直接訪問數據緩沖池中數據段的效用鏈表，構建過程的時間復雜度為O(s+t)。所以TKBPH算法的總體時間復雜度為max{O(mn)+O(s+t)}。

3 仿真實驗及結果分析

3.1 實驗設置

本文從運行時間和內存消耗兩個方面作為標準評估算法的性能。實驗選取目前主流的TKO、TKU和Vert_topk DS算法與本文提出的TKBPH算法進行對比。算法均采用Java編寫，實驗設備處理器為英特爾酷睿i5-4300，8 G內存，搭配64位Window 7操作系統。對比算法的Java源碼和數據集來自于SPMF[12]和UP-Miner[13]，數據集的數據特征見表3。

表3 實驗數據集

實驗采用兩個稠密數據集和兩個稀疏數據集對TKBPH算法進行充分對比。數據集Mushroom、Retail和Chess是來自現實場景的真實數據集，數據集T10I4D100K是由IBM數據合成器生成的語義數據集。所有數據集使用對數正態分布生成項的外部效用介于-1000和1000之間，項數量在1和5之間隨機生成。由于k值設置較低，所以算法運行時間超過200 s或者內存溢出則視為低效，立刻終止算法運行。

3.2 運行時間分析

將TKO、TKU、Vert_top-k DS算法與TKBPH算法在不同數據集進行測試，運行結果如圖3所示。在語義數據集T10I4D100K上，當k值等于4000時，TKBPH算法僅需5.28 s，而TKU算法的運行時間已經高達121.47 s，其余TKO和Vert_top-k DS算法也分別為24.46 s和29.71 s。在稀疏數據集Retail上，TKBPH算法不僅運行時間最短，而且隨著k值的增長，時間效率變化非常平穩。當k值從200上升至800，TKBPH算法的運行時間僅從25.76 s上升至28.66 s，然而Vert_top-k DS算法已經從121.75 s上升至431.39 s。在稠密數據集Chess和Mushroom上，TKBPH算法同樣性能優異，對比在Chess數據集上進行實驗的其它算法，在同等k值情況下，僅需其它算法大約二分之一的運行時間。主要原因是單一項效用鏈表在鏈表初始化時已經插入到數據緩沖池，當搜索子程序Search挖掘分支項集時，只需把合并項集的效用鏈表插入到緩沖池，根據索引鏈表IndexList中單一項效用鏈表的位置信息直接讀取效用鏈表信息進行計算，從而避免之前算法項集合并時大量比較操作，提高算法運行效率。

圖3 4種算法在不同數據集下的運行時間對比

3.3 內存消耗分析

通過將4種算法在不同數據集上運行，監測內存空間使用量如圖4所示。TKBPH算法提出的數據緩沖池結構，將單一項的效用鏈表存儲在數據緩沖池，將數據緩沖池內效用鏈表的位置信息存儲在索引鏈表。挖掘新的分支項集時只需在緩沖尾部加入新的項集，當完成挖掘操作不再需要此項集時，數據緩沖池會回收此項集所占用的內存空間等待分配給其它需要的項集。數據緩沖池充當內存管理者角色，將內存中不需要的空間回收再利用，使得算法運行時內存空間的消耗大幅降低。相比其它算法，TKBPH算法在實驗中所需的內存僅需二分之一甚至更少。由于緩沖池結構的內存復用，在調整k值的過程中，內存消耗的波動非常平穩。在數據集T10I4D100K的實驗中TKBPH算法內存從50.32 MB上升至54.14 MB，然而其它算法中內存消耗最小的TKO算法內存消耗從286.1 MB至538.38 MB，內存波動最小的TKU算法在551.68 MB到567.76 MB，但內存消耗比TKBPH算法相比高一個數量級。

圖4 4種算法在不同數據集下的內存消耗對比

4 結束語

本文提出一種Top-k高效用項集挖掘算法TKBPH，該算法主要采用數據緩沖池結構和索引鏈表方式與構造效用鏈表過程相結合，通過內存復用的方式減少挖掘高效用項集所需運行時間和內存空間。通過選取4個不同類型的數據集對算法運行時間和內存使用量進行實驗論證，實驗結果表明TKBPH算法提出數據緩沖池結構相比于傳統的效用鏈表構建過程，時間和內存使用量最多降低一個數量級。

隨著在線交易系統、無線傳感器網絡、社交媒體等領域的廣泛應用，流數據處理逐漸成為研究熱點。在未來工作中，對于流數據和緩沖區結構的特性，將數據緩沖池結構應用于流數據的高效用項集挖掘算法。