宋 威，鄭川龍

(北方工業(yè)大學(xué) 信息學(xué)院 北京 100144)

0 引言

作為數(shù)據(jù)挖掘[1-2]的主要研究問題之一，頻繁項(xiàng)集[3-4]旨在發(fā)現(xiàn)那些支持度不低于用戶指定閾值的所有項(xiàng)目。如何設(shè)置合適的閾值，一直是頻繁項(xiàng)集挖掘面臨的難題之一。為解決這一問題，學(xué)者們提出了挖掘top-k頻繁項(xiàng)集[5-6]的問題，即發(fā)現(xiàn)支持度最高的k個(gè)頻繁項(xiàng)集。這類問題通過設(shè)置更易理解的結(jié)果項(xiàng)集數(shù)量k，來取代最小支持度閾值，更適合于非領(lǐng)域?qū)＜业挠脩羰褂?，并已在若干領(lǐng)域得到了應(yīng)用[7]。TopKRules[6]是一種挖掘top-k關(guān)聯(lián)規(guī)則的方法，挖掘top-k頻繁項(xiàng)集可以看作是TopKRules方法2個(gè)階段中的第1個(gè)階段。top-kMiner算法[8]使用2-頻繁項(xiàng)集產(chǎn)生更長的候選項(xiàng)集，再從候選項(xiàng)集中得到真正的top-k頻繁項(xiàng)集。BTK[9-10]算法用頻繁項(xiàng)集挖掘中的包含索引結(jié)構(gòu)來提高挖掘效率。TKFIM算法[11]利用集合論方法，特別是等價(jià)類技術(shù)來挖掘top-k頻繁項(xiàng)集。這些方法均使用樹或列表來轉(zhuǎn)換原始數(shù)據(jù)，并通過逐步過濾不可能產(chǎn)生最終結(jié)果的項(xiàng)集來加快搜索空間的遍歷。由于需要不斷保存與更新中間結(jié)果，計(jì)算開銷較大仍然是此類問題最大的挑戰(zhàn)。

由于能快速挖掘到可接受的近似結(jié)果，利用啟發(fā)式方法來挖掘項(xiàng)集的研究正在興起，如GA-Apriori[12]、HUIM-ABC[13]、HUIM-SPSO[14]等方法。這類方法不需要額外的數(shù)據(jù)結(jié)構(gòu)，通過模擬生物群體或物理現(xiàn)象來挖掘近似的項(xiàng)集，不但易于實(shí)現(xiàn)，而且具有較高的挖掘效率。據(jù)我們所知，目前尚沒有基于啟發(fā)式方法的top-k頻繁項(xiàng)集挖掘的工作。

交叉熵(cross entropy, CE)方法[15]是基于概率模型采樣生成試探解的全局優(yōu)化算法，通過更新概率分布模型，不斷優(yōu)化群體中解的質(zhì)量，這與挖掘top-k頻繁項(xiàng)集的本質(zhì)是一致的。因此，本文提出了一種基于交叉熵的top-k頻繁項(xiàng)集挖掘算法(top-kfrequent itemset mining algorithm based on cross entropy,KCE)。

KCE算法用位圖來轉(zhuǎn)換原始數(shù)據(jù)和項(xiàng)集，并直接使用項(xiàng)集的支持度作為優(yōu)化函數(shù)。在概率向量的更新過程中，KCE算法確保了支持度高的項(xiàng)目在后續(xù)迭代中出現(xiàn)的概率更大。為了約簡搜索空間，KCE算法提出了過濾支持度的概念，從一開始就避免搜索那些不可能出現(xiàn)在結(jié)果中的項(xiàng)目。此外，KCE算法提出了按位交叉策略，提高了樣本的多樣性，有助于發(fā)現(xiàn)更為精確的結(jié)果。實(shí)驗(yàn)結(jié)果表明，KCE算法具有挖掘效率較高，存儲開銷較小的優(yōu)勢，且可以發(fā)現(xiàn)絕大多數(shù)精確的top-k頻繁項(xiàng)集。

1 問題描述

1.1 top-k頻繁項(xiàng)集挖掘

設(shè)IS={i1,i2,…,im}是項(xiàng)目(item)的集合，α?IS稱作項(xiàng)集(itemset)。設(shè)TDB={T1,T2, …,Tn}是事務(wù)數(shù)據(jù)庫，每條事務(wù)Td∈TDB(1≤d≤n)是一個(gè)項(xiàng)集，擁有唯一的標(biāo)識d。若項(xiàng)集α?Td，則稱事務(wù)Td包含α。

事務(wù)數(shù)據(jù)庫TDB中包含項(xiàng)集α的事務(wù)數(shù)稱為α的支持度，定義為

σ(α)=|{Tq|α?Tq∧Tq∈TDB}|。

(1)

若支持度高于項(xiàng)集α的項(xiàng)集不超過k個(gè)，則α就是一個(gè)top-k頻繁項(xiàng)集。所謂top-k頻繁項(xiàng)集挖掘就是找出事務(wù)數(shù)據(jù)庫中支持度最高的前k個(gè)項(xiàng)集。

與普通的頻繁項(xiàng)集挖掘任務(wù)不同，挖掘top-k頻繁項(xiàng)集不需要用戶指定最小支持度閾值，或者也可以說是將最小支持度閾值設(shè)置為0。這就意味著對于同樣的事務(wù)數(shù)據(jù)庫，top-k頻繁項(xiàng)集挖掘比一般的頻繁項(xiàng)集挖掘需要遍歷更大的搜索空間，計(jì)算開銷更為巨大。

本文將使用示例數(shù)據(jù)庫EDB={(T1：A，B，C，E), (T2：B，C，F(xiàn)), (T3：D，E), (T4：A，B，C，D，E), (T5：C，E)}，來對概念和算法做解釋說明。該數(shù)據(jù)庫由5條事務(wù)組成，如(T1：A，B，C，E)表示事務(wù)T1，該事務(wù)由4個(gè)項(xiàng)目A、B、C、E組成。項(xiàng)集{CE}分別出現(xiàn)在事務(wù)T1、T4以及T5中，故其支持度σ(CE)=3。為簡便起見，本文后續(xù)的描述中均省略項(xiàng)集的括號，如將{CE}記為CE。示例數(shù)據(jù)庫中，top-5頻繁項(xiàng)集為{C: 4,E: 4,B: 3,BC: 3,CE: 3}，其中冒號后面的數(shù)值代表項(xiàng)集的支持度。

1.2 交叉熵方法

交叉熵方法既可以用于估計(jì)復(fù)雜隨機(jī)網(wǎng)絡(luò)中罕見事件的概率，也可用于解決復(fù)雜的組合優(yōu)化問題(combinatorial optimization problem, COP)。在本文中，我們利用交叉熵解決COP的思路來挖掘top-k頻繁項(xiàng)集。

經(jīng)典的交叉熵方法解決COP所使用的向量定義如下。假設(shè)Y=(y1,y2,…,yn)是一個(gè)n維二進(jìn)制向量。交叉熵的目標(biāo)是使用隨機(jī)搜索算法，通過最大化函數(shù)S(X)的值，來重構(gòu)未知向量Y，

(2)

使S(X)=n的直接方法便是不斷生成不同的二進(jìn)制樣本向量X=(x1,x2,…,xn)，使其等于向量Y。在交叉熵方法中，我們使用隨機(jī)伯努利分布來產(chǎn)生這些不同的樣本向量X，并使用概率向量P=(p1,p2,…,pn)來記錄每輪更新后不同樣本向量中每個(gè)元素出現(xiàn)的概率，經(jīng)過不斷的迭代更新后，概率向量P的不同位將穩(wěn)定為0或1，從而使由P確定的樣本向量收斂，得到最優(yōu)解。

交叉熵方法首先隨機(jī)初始化概率向量P0=(1/2, 1/2,…, 1/2)，然后采用隨機(jī)伯努利方法產(chǎn)生不同的樣本向量X1，X2，…，XN，再根據(jù)一定的評判標(biāo)準(zhǔn)，在樣本中計(jì)算適應(yīng)度函數(shù)S(Xi)。這里假設(shè)γt是樣本的ρ分位點(diǎn)所對應(yīng)的數(shù)值，記為

γt=S(X「N×ρ?)，

(3)

其中:「N×ρ?表示不小于N×ρ的最小整數(shù)。我們把目標(biāo)函數(shù)值位于總體樣本ρ分位點(diǎn)內(nèi)的所有向量Xi所構(gòu)成的樣本稱為精英樣本Se，即

Se={Xi|S(Xi)≥γt}。

(4)

再使用公式(5)更新概率向量的每一位，

(5)

其中：j=1, 2, …,n；Xi=(xi1,xi2, …,xin)；t是迭代次數(shù)；I(·)是指示函數(shù)。

(6)

其中E是一個(gè)事件。

交叉熵方法使用公式(5)不斷更新概率向量，并根據(jù)概率向量更新樣本向量，直到滿足終止條件為止。終止條件一般是分位值γt穩(wěn)定不變，或者概率向量趨于二進(jìn)制向量。

2 KCE算法

2.1 項(xiàng)集信息的位圖表示

位圖是項(xiàng)集挖掘中常用的數(shù)據(jù)結(jié)構(gòu)，具有存儲開銷小，便于使用高效位操作的優(yōu)勢。在KCE算法中，我們使用位圖來轉(zhuǎn)換原始的事務(wù)數(shù)據(jù)庫。位圖中的每個(gè)元素由公式(7)計(jì)算得到，

(7)

其中：ik代表第k個(gè)項(xiàng)目；Tj代表第j個(gè)事務(wù)。由公式(7)可知：若ik出現(xiàn)在Tj中，則第j行第k列的位圖元素值取1；否則取0。

表1是示例數(shù)據(jù)庫EDB的位圖表示。例如，項(xiàng)目A出現(xiàn)在T1和T4中，故A的位圖表示為Bt(A)=(10010)。同理，B的位圖表示為Bt(B)=(11010)。如果我們要得到項(xiàng)集AB的位圖，則只需對Bt(A)和Bt(B)做按位與運(yùn)算，即Bt(AB)=Bt(A) &Bt(B)=(10010)。結(jié)果中含有兩個(gè)“1”，表示項(xiàng)集AB的支持度為2。

表1 示例數(shù)據(jù)庫的位圖表示Table 1 The bitmap representation of the example database

2.2 基于交叉熵的模型構(gòu)建

在將數(shù)據(jù)庫轉(zhuǎn)換為位圖之后，我們同樣可以將項(xiàng)集用二進(jìn)制向量來表示，稱這種二進(jìn)制向量為項(xiàng)集向量。

我們直接使用項(xiàng)集的支持度作為優(yōu)化對象，即對于項(xiàng)集α，

S(α)=σ(α)。

(8)

在第t次迭代時(shí)，我們把N個(gè)項(xiàng)集向量按照S(Xi)的降序進(jìn)行排序，并更新分位點(diǎn)γt的位置和概率向量Pt中每一位所對應(yīng)的概率值。

2.3 剪枝策略

由于項(xiàng)集的支持度滿足向下閉合性質(zhì)，即：對任意兩個(gè)項(xiàng)集α，β，若α?β，則σ(α)≥σ(β)。由此可知，若項(xiàng)集α不是top-k頻繁項(xiàng)集，那么α的所有超集均不是top-k頻繁項(xiàng)集；反之，若項(xiàng)集α是top-k頻繁項(xiàng)集，那么α的所有子集也是top-k頻繁項(xiàng)集[8-9]。這是top-k頻繁項(xiàng)集挖掘中最基本的剪枝手段。KCE算法同樣也使用了該剪枝策略。

基于啟發(fā)式方法的項(xiàng)集挖掘算法，一般在開始階段都會固定項(xiàng)集向量中包含的項(xiàng)目個(gè)數(shù)[12-13]。因此，在最初的搜索階段就刪去那些不可能出現(xiàn)在top-k頻繁項(xiàng)集中的項(xiàng)目，可有效地約簡搜索空間，提高挖掘效率。

定義1設(shè)ik∈IS，Sk={ix|σ(ix) >σ(ik)}，若|Sk|=k-1，則稱σ(ik)為過濾支持度，記作σf，其中|Sk|代表集合Sk中項(xiàng)目的個(gè)數(shù)。

由定義1可知，數(shù)據(jù)庫中過濾支持度即為支持度按由高到低順序排列的第k個(gè)項(xiàng)目的支持度。

定理1若項(xiàng)集α的支持度小于過濾支持度σf，則α及其超集都不是top-k頻繁項(xiàng)集。

證明假設(shè)σk是數(shù)據(jù)D中top-k頻繁項(xiàng)集實(shí)際的最小支持度，根據(jù)定義1，有σf≤σk。

若σ(α)<σf，則σ(α)<σk，即α不是top-k頻繁項(xiàng)集。

對?β?α，有σ(β)≤σ(α)，故σ(β)<σk，即β也不是top-k頻繁項(xiàng)集。

根據(jù)定理1，一旦確定某個(gè)項(xiàng)目的支持度低于過濾支持度，則該項(xiàng)目的所有超集均不可能在結(jié)果中出現(xiàn)。因此，該項(xiàng)目無須出現(xiàn)在算法的項(xiàng)集向量中。

考慮從示例數(shù)據(jù)庫EDB中挖掘top-5頻繁項(xiàng)集，可知σf=2。由于σ(F)=1<σf，故項(xiàng)集向量只包含A、B、C、D、E，而無須考慮項(xiàng)目F。

2.4 按位交叉策略

基于啟發(fā)式方法挖掘頻繁項(xiàng)集，很難保證在有限的迭代次數(shù)內(nèi)完全得到精確的解，增加樣本的多樣性是解決這一問題的有效手段[13-14]。

為提高樣本多樣性，我們提出了項(xiàng)集向量的按位交叉策略，其核心思想是從精英樣本Se中選一部分項(xiàng)集向量，按照交叉部分位的取值，而不是概率向量的方式，產(chǎn)生新的向量。具體而言，給定種群規(guī)模N和交叉系數(shù)δ(0<δ<1)，在每次產(chǎn)生的個(gè)體之中，?|Se|×δ」個(gè)新的項(xiàng)集向量由按位交叉策略產(chǎn)生，其余的N-?|Se|×δ」個(gè)新的項(xiàng)集向量由當(dāng)前的概率向量產(chǎn)生，其中：|Se|代表精英樣本的數(shù)量；?|Se|×δ」表示不超過|Se|×δ的最大整數(shù)。

對按位交叉策略，每次選取2個(gè)項(xiàng)集向量Vm和Vn，假設(shè)項(xiàng)集向量的長度為l，則先隨機(jī)產(chǎn)生一個(gè)整數(shù)j(1≤j≤l)，再從l位中隨機(jī)確定j位，記為b1，b2，…，bj，再將Vm和Vn中第b1位，b2位，…，和bj位的值互換，這樣便產(chǎn)生了兩個(gè)新的項(xiàng)集向量V′m和V′n。重復(fù)這種逐對按位交叉操作，直到隨機(jī)選定的?|Se|×δ」個(gè)項(xiàng)集向量均處理完畢為止。

假設(shè)選定了兩個(gè)項(xiàng)集向量V1=<11010>和V2=<00110>，通過產(chǎn)生隨機(jī)數(shù)來確定二者的第1位和第2位作按位交叉，得到新的項(xiàng)集向量V′1=<00010>和V′2=<11110>。

2.5 算法描述

算法1KCE的總體流程。

輸入： 事務(wù)數(shù)據(jù)庫TDB，結(jié)果數(shù)量k，種群規(guī)模N，分位點(diǎn)ρ，交叉比例δ，最大迭代次數(shù)miter。

輸出： top-k頻繁項(xiàng)集。

1) Initialization( )；

2) whilet≤miterandPt不是二進(jìn)制向量 do

3) 由公式(5)計(jì)算Pt；

4) 隨機(jī)選取?|Se|×δ」個(gè)項(xiàng)集向量，執(zhí)行按位交叉操作；

5) 根據(jù)Pt產(chǎn)生剩余的N-?|Se|×δ」個(gè)項(xiàng)集向量；

6) 依據(jù)支持度由大到小的順序排列樣本，得到新一代群體，記為X1，X2，…，XN；

7) 更新top-k頻繁項(xiàng)集；

8) 由公式(3)計(jì)算γt；

9)t++；

10) end while

11) 輸出top-k頻繁項(xiàng)集。

KCE算法首先調(diào)用過程Initialization(算法2所示)進(jìn)行初始化。一次迭代過程中，首先更新概率向量，然后選取一部分精英樣本執(zhí)行按位交叉操作，再由概率向量產(chǎn)生其他的下一代項(xiàng)集向量，進(jìn)而更新top-k頻繁項(xiàng)集，增加迭代次數(shù)。重復(fù)以上迭代過程，直到達(dá)到循環(huán)結(jié)束條件為止。

算法2Initialization( )

1) 掃描一遍數(shù)據(jù)庫，根據(jù)過濾支持度刪去無效的項(xiàng)目；

2) 用二進(jìn)制位圖表示數(shù)據(jù)庫；

3)P0=(1/2, 1/2, …, 1/2)；

4) 由P0產(chǎn)生第一代種群；

5) 依據(jù)支持度由大到小的順序排列樣本，記為X1，X2，…，XN；

6) 計(jì)算top-k頻繁項(xiàng)集；

7) 由公式(3)計(jì)算γt；

8)t=1。

初始化過程首先根據(jù)定理1對項(xiàng)目進(jìn)行剪枝，再將數(shù)據(jù)庫轉(zhuǎn)換為位圖形式。概率向量的每個(gè)概率元素的初始值均設(shè)為0.5，并據(jù)此得到初始種群和初始top-k頻繁項(xiàng)集。最后，將迭代次數(shù)設(shè)置為1。

3 實(shí)驗(yàn)驗(yàn)證

我們與TopKRules[6]和TKFIM[11]兩種算法進(jìn)行了實(shí)驗(yàn)對比，其中：TopKRules算法的代碼由SPMF平臺下載獲得[16]，TKFIM算法的代碼由文獻(xiàn)[11]獲得。TopKRules算法的挖掘結(jié)果是top-k關(guān)聯(lián)規(guī)則，為公平對比，我們省略了該算法由項(xiàng)集產(chǎn)生規(guī)則所帶來的計(jì)算開銷。此外，TKFIM算法的代碼只能處理每行列數(shù)相同的數(shù)據(jù)集，對Retail這種每條事務(wù)包含項(xiàng)目數(shù)不等的數(shù)據(jù)則無法處理。因此，在3.2節(jié)與3.3節(jié)的實(shí)驗(yàn)結(jié)果中，未報(bào)告TKFIM算法在Retail數(shù)據(jù)集上的效率與內(nèi)存消耗。

3.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集

KCE算法使用Java語言實(shí)現(xiàn)，實(shí)驗(yàn)平臺的配置為macOS 11.1操作系統(tǒng)、2.3 GHz 4核CPU和8 GB RAM。

使用4個(gè)數(shù)據(jù)集驗(yàn)證算法的性能，其中：T20I30D10k和T40I45D50k是由SPMF平臺[16]提供的數(shù)據(jù)生成器產(chǎn)生的合成數(shù)據(jù)集；Chess和Retail為真實(shí)數(shù)據(jù)，由SPMF平臺下載獲得。數(shù)據(jù)集的參數(shù)特征如表2所示。

表2 數(shù)據(jù)集的特征Table 2 Characteristics of the dataset

對于所有的實(shí)驗(yàn)，我們設(shè)置每輪迭代的樣本的大小N為2 000，分位點(diǎn)ρ為0.2，交叉系數(shù)δ為0.2，最大迭代次數(shù)miter為2 000。

3.2 時(shí)間消耗

圖1展示了k取不同值時(shí)，3種算法在4個(gè)數(shù)據(jù)集上運(yùn)行時(shí)間的對比，圖1(b)、(c)縱坐標(biāo)T為時(shí)間變量取對數(shù)后的結(jié)果。

圖1 時(shí)間消耗比較Figure 1 Time consumption comparison

由圖1可知，算法TKFIM的效率最低。這主要是由于TKFIM算法基于等價(jià)類的思想，通過反復(fù)對包含項(xiàng)集的事務(wù)集合作交運(yùn)算，來維護(hù)臨時(shí)的top-k頻繁項(xiàng)集。除支持度和包含項(xiàng)集的事務(wù)差異之外，缺少更為高效的剪枝策略。

除Chess數(shù)據(jù)集外，KCE的運(yùn)行時(shí)間始終優(yōu)于TopKRules。KCE算法在Chess數(shù)據(jù)集上的運(yùn)行時(shí)間不如TopKRules的原因在于，該數(shù)據(jù)集的規(guī)模非常小，僅有3 196條數(shù)據(jù)和75個(gè)不同的項(xiàng)目。啟發(fā)式算法用于構(gòu)建向量、計(jì)算過濾支持度、執(zhí)行按位交叉策略的時(shí)間，反而超過了這些策略所能節(jié)約的時(shí)間。反之，當(dāng)數(shù)據(jù)集較大時(shí)，如Retail數(shù)據(jù)集上，k取100時(shí)，使用過濾支持度可以在挖掘初期就刪去16 370個(gè)不可能產(chǎn)生最終結(jié)果的項(xiàng)目，從而大大約簡了搜索空間，提高了挖掘效率。

3.3 內(nèi)存開銷

3種算法的內(nèi)存開銷比較結(jié)果如圖2所示。3種算法的內(nèi)存開銷與運(yùn)行時(shí)間對比結(jié)果一致。TKFIM算法的內(nèi)存開銷依然最高，這主要是其使用的top-k列表結(jié)構(gòu)需要保存大量中間結(jié)果而造成的。

圖2 內(nèi)存開銷比較Figure 2 Memory consumption comparison

盡管KCE同樣在Chess數(shù)據(jù)集上比TopKRules消耗了更多的內(nèi)存。但隨著k值的不斷增加，二者之間的差距呈現(xiàn)了逐步減少的趨勢。特別是當(dāng)k取100時(shí)，KCE與TopKRules的內(nèi)存消耗幾乎完全一致。在其他3個(gè)數(shù)據(jù)集上，KCE的整體內(nèi)存消耗均優(yōu)于TopKRules。特別是在較大的數(shù)據(jù)集Retail上優(yōu)勢較為明顯，由于過濾支持度在初始階段就刪去了大量不可能出現(xiàn)在最終結(jié)果內(nèi)的項(xiàng)目，KCE在Retail數(shù)據(jù)集上內(nèi)存消耗量平均是TopKRules內(nèi)存消耗量的23.07%。

此外，相對于TopKRules而言，KCE的內(nèi)存消耗總體上呈現(xiàn)出了較為平穩(wěn)的趨勢。這證明了基于啟發(fā)式方法挖掘頻繁項(xiàng)集無須建立額外的樹或列表結(jié)構(gòu)，一旦確定了向量的大小，開始了迭代挖掘，內(nèi)存總體消耗就基本可以確定了。

3.4 精度測量

考慮到啟發(fā)式top-k頻繁項(xiàng)集挖掘算法無法保證在一定的迭代次數(shù)之內(nèi)找到所有準(zhǔn)確的結(jié)果。我們用來度量KCE方法的精度公式為

Ck/k×100%，

(9)

其中：Ck是KCE挖掘到的真實(shí)top-k頻繁項(xiàng)集的數(shù)量。而實(shí)際的top-k頻繁項(xiàng)集由精確算法TopKRules挖掘得到。

與3.2節(jié)和3.3節(jié)一樣，我們在每個(gè)數(shù)據(jù)集上取5組不同的k值，共進(jìn)行了20次實(shí)驗(yàn)。其中：KCE算法在T20I30D10k上的5次實(shí)驗(yàn)均能找到全部正確結(jié)果，而在T40I45D50k、Chess和Retail數(shù)據(jù)集上能找到全部正確結(jié)果的次數(shù)分別為4次、4次和2次。也就是說，在20次實(shí)驗(yàn)中，KCE算法能夠得到全部正確結(jié)果的次數(shù)為15次，占總實(shí)驗(yàn)次數(shù)的75%；而且所有結(jié)果的精度均在90%以上。

4 總結(jié)

提出了一種基于交叉熵的top-k頻繁項(xiàng)集挖掘算法KCE。算法通過組合優(yōu)化方式直接輸出用戶期望數(shù)量的頻繁項(xiàng)集，并針對top-k頻繁項(xiàng)集挖掘問題的特征，提出了搜索空間剪枝策略與保持樣本多樣性的策略，在基于啟發(fā)式方法挖掘top-k頻繁項(xiàng)集方面進(jìn)行了有益的嘗試。