一種基于交叉熵的top-k頻繁項(xiàng)集挖掘算法

宋 威，鄭川龍

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

0 引言

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

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

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

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

1 問(wèn)題描述

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

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

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

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

(1)

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

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

本文將使用示例數(shù)據(jù)庫(kù)EDB={(T1：A，B，C，E), (T2：B，C，F(xiàn)), (T3：D，E), (T4：A，B，C，D，E), (T5：C，E)}，來(lái)對(duì)概念和算法做解釋說(shuō)明。該數(shù)據(jù)庫(kù)由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。為簡(jiǎn)便起見(jiàn)，本文后續(xù)的描述中均省略項(xiàng)集的括號(hào)，如將{CE}記為CE。示例數(shù)據(jù)庫(kù)中，top-5頻繁項(xiàng)集為{C: 4,E: 4,B: 3,BC: 3,CE: 3}，其中冒號(hào)后面的數(shù)值代表項(xiàng)集的支持度。

1.2 交叉熵方法

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

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

(2)

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

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

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

(3)

其中:「N×ρ?表示不小于N×ρ的最小整數(shù)。我們把目標(biāo)函數(shù)值位于總體樣本ρ分位點(diǎn)內(nèi)的所有向量Xi所構(gòu)成的樣本稱(chēng)為精英樣本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)，具有存儲(chǔ)開(kāi)銷(xiāo)小，便于使用高效位操作的優(yōu)勢(shì)。在KCE算法中，我們使用位圖來(lái)轉(zhuǎn)換原始的事務(wù)數(shù)據(jù)庫(kù)。位圖中的每個(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ù)庫(kù)EDB的位圖表示。例如，項(xiàng)目A出現(xiàn)在T1和T4中，故A的位圖表示為Bt(A)=(10010)。同理，B的位圖表示為Bt(B)=(11010)。如果我們要得到項(xiàng)集AB的位圖，則只需對(duì)Bt(A)和Bt(B)做按位與運(yùn)算，即Bt(AB)=Bt(A) &Bt(B)=(10010)。結(jié)果中含有兩個(gè)“1”，表示項(xiàng)集AB的支持度為2。

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

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

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

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

S(α)=σ(α)。

(8)

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

2.3 剪枝策略

由于項(xiàng)集的支持度滿足向下閉合性質(zhì)，即：對(duì)任意兩個(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)集挖掘算法，一般在開(kāi)始階段都會(huì)固定項(xiàng)集向量中包含的項(xiàng)目個(gè)數(shù)[12-13]。因此，在最初的搜索階段就刪去那些不可能出現(xiàn)在top-k頻繁項(xiàng)集中的項(xiàng)目，可有效地約簡(jiǎn)搜索空間，提高挖掘效率。

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

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

定理1若項(xiàng)集α的支持度小于過(guò)濾支持度σ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)集。

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

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

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

2.4 按位交叉策略

基于啟發(fā)式方法挖掘頻繁項(xiàng)集，很難保證在有限的迭代次數(shù)內(nèi)完全得到精確的解，增加樣本的多樣性是解決這一問(wèn)題的有效手段[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|×δ」表示不超過(guò)|Se|×δ的最大整數(shù)。

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

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

2.5 算法描述

算法1KCE的總體流程。

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

算法2Initialization( )

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

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

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。

初始化過(guò)程首先根據(jù)定理1對(duì)項(xiàng)目進(jìn)行剪枝，再將數(shù)據(jù)庫(kù)轉(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)對(duì)比，其中：TopKRules算法的代碼由SPMF平臺(tái)下載獲得[16]，TKFIM算法的代碼由文獻(xiàn)[11]獲得。TopKRules算法的挖掘結(jié)果是top-k關(guān)聯(lián)規(guī)則，為公平對(duì)比，我們省略了該算法由項(xiàng)集產(chǎn)生規(guī)則所帶來(lái)的計(jì)算開(kāi)銷(xiāo)。此外，TKFIM算法的代碼只能處理每行列數(shù)相同的數(shù)據(jù)集，對(duì)Retail這種每條事務(wù)包含項(xiàng)目數(shù)不等的數(shù)據(jù)則無(wú)法處理。因此，在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語(yǔ)言實(shí)現(xiàn)，實(shí)驗(yàn)平臺(tái)的配置為macOS 11.1操作系統(tǒng)、2.3 GHz 4核CPU和8 GB RAM。

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

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

對(duì)于所有的實(shí)驗(yàn)，我們?cè)O(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í)間的對(duì)比，圖1(b)、(c)縱坐標(biāo)T為時(shí)間變量取對(duì)數(shù)后的結(jié)果。

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

由圖1可知，算法TKFIM的效率最低。這主要是由于TKFIM算法基于等價(jià)類(lèi)的思想，通過(guò)反復(fù)對(duì)包含項(xiàng)集的事務(wù)集合作交運(yùn)算，來(lái)維護(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ì)算過(guò)濾支持度、執(zhí)行按位交叉策略的時(shí)間，反而超過(guò)了這些策略所能節(jié)約的時(shí)間。反之，當(dāng)數(shù)據(jù)集較大時(shí)，如Retail數(shù)據(jù)集上，k取100時(shí)，使用過(guò)濾支持度可以在挖掘初期就刪去16 370個(gè)不可能產(chǎn)生最終結(jié)果的項(xiàng)目，從而大大約簡(jiǎn)了搜索空間，提高了挖掘效率。

3.3 內(nèi)存開(kāi)銷(xiāo)

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

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

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

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

3.4 精度測(cè)量

考慮到啟發(fā)式top-k頻繁項(xiàng)集挖掘算法無(wú)法保證在一定的迭代次數(shù)之內(nèi)找到所有準(zhǔn)確的結(jié)果。我們用來(lái)度量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é)一樣，我們?cè)诿總€(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次。也就是說(shuō)，在20次實(shí)驗(yàn)中，KCE算法能夠得到全部正確結(jié)果的次數(shù)為15次，占總實(shí)驗(yàn)次數(shù)的75%；而且所有結(jié)果的精度均在90%以上。

4 總結(jié)

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