基于統(tǒng)計(jì)顯著性檢驗(yàn)的高效用項(xiàng)集挖掘算法

摘 要：針對(duì)傳統(tǒng)高效用項(xiàng)集挖掘算法在具有不同類(lèi)型標(biāo)簽事務(wù)中報(bào)告假陽(yáng)性高效用項(xiàng)集的問(wèn)題，提出兩個(gè)基于統(tǒng)計(jì)顯著性檢驗(yàn)的高效用項(xiàng)集挖掘算法——FHUI和PHUI算法。這兩個(gè)算法首先找到所有待檢驗(yàn)高效用項(xiàng)集并依據(jù)項(xiàng)集長(zhǎng)度進(jìn)行分組；然后，F(xiàn)HUI算法根據(jù)項(xiàng)集自身的頻率分布生成零分布，PHUI算法根據(jù)事務(wù)內(nèi)置換策略或事務(wù)間置換策略構(gòu)造置換事務(wù)集合來(lái)生成零分布。最后，F(xiàn)HUI和PHUI算法從零分布中計(jì)算出p值并運(yùn)用錯(cuò)誤發(fā)現(xiàn)率剔除假陽(yáng)性高效用項(xiàng)集?；鶞?zhǔn)事務(wù)集合實(shí)驗(yàn)結(jié)果顯示FHUI和PHUI算法能夠剔除大量的假陽(yáng)性高效用項(xiàng)集，在后續(xù)分類(lèi)任務(wù)中取得了更高的正確率；仿真事務(wù)集合實(shí)驗(yàn)結(jié)果顯示FHUI和PHUI算法報(bào)告的項(xiàng)集中假陽(yáng)性高效用項(xiàng)集數(shù)量占比低于4.8%且平均效用高于39 000。實(shí)驗(yàn)結(jié)果證明，在具有不同類(lèi)型的標(biāo)簽事務(wù)中，F(xiàn)HUI和PHUI算法報(bào)告的統(tǒng)計(jì)顯著高效用項(xiàng)集可靠性和實(shí)用性更強(qiáng)。

關(guān)鍵詞：數(shù)據(jù)挖掘；高效用項(xiàng)集挖掘；統(tǒng)計(jì)顯著性檢驗(yàn)；Fisher檢驗(yàn)；置換檢驗(yàn)

中圖分類(lèi)號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695（2024）10-013-2970-08

doi：10.19734/j.issn.1001-3695.2024.01.0027

Mining high utility itemsets based on statistical significance testing

Wu Jun， Wei Dandan， Ouyang Aijia， Wang Ya

（School of Information Engineering， Zunyi Normal University， Zunyi Guizhou 563000， China）

Abstract：Aiming at the problem of traditional high utility itemset mining algorithms reporting false positive high utility itemsets in transactions with class labels， this paper proposed two high utility itemset mining algorithms called FHUI and PHUI. The FHUI and PHUI firstly found all the candidates and grouped them by length. Then， the FHUI established null distributions with the frequency distributions， while the PHUI established null distributions by the permutation strategy within or between transactions. Finally， the FHUI and PHUI calculated the p values from the null distributions and exploited the false discovery rate to eliminate the false positive high utility itemsets. The experiments on the benchmark data sets show that the FHUI and PHUI can eliminate a large number of false positive itemsets， which allows them to achieve higher accuracy rates in the classification tasks. The experiments on synthetic data sets reveal that the proportions of false positive itemsets reported by FHUI and PHUI are lower than 4.8% and the average utility values are higher than 39 000. Experimental results prove that the statistically significant high utility itemsets reported by the FHUI and PHUI are more reliable and practical in transactions with class labels.

Key words：data mining; high utility itemset mining; statistical significance testing; Fisher testing; permutation testing

0 引言

發(fā)現(xiàn)數(shù)據(jù)中有趣和實(shí)用的項(xiàng)集是數(shù)據(jù)挖掘中一個(gè)重要的研究領(lǐng)域。在該領(lǐng)域中，頻繁項(xiàng)集挖掘是研究最為全面的任務(wù)［1］。但實(shí)際應(yīng)用中發(fā)現(xiàn)報(bào)告的大部分頻繁項(xiàng)集都不具備有趣性和實(shí)用性。例如，在超市購(gòu)買(mǎi)記錄中，雖然{牛奶，面包}項(xiàng)集通常出現(xiàn)的頻率很高，但其不具備有趣性和實(shí)用性，因?yàn)樵擁?xiàng)集提供的信息是一種普遍的消費(fèi)行為。導(dǎo)致上述現(xiàn)象的原因是頻繁項(xiàng)集挖掘任務(wù)設(shè)定每個(gè)項(xiàng)具有相同的權(quán)重。

為了發(fā)現(xiàn)真正有趣且實(shí)用的項(xiàng)集，頻繁項(xiàng)集挖掘任務(wù)被拓展成高效用項(xiàng)集挖掘任務(wù)［2］。高效用項(xiàng)集挖掘任務(wù)通過(guò)賦予項(xiàng)獨(dú)立的外部效用和內(nèi)部效用使得每個(gè)項(xiàng)具有不同的權(quán)重。至今，高效用項(xiàng)集被廣泛運(yùn)用到不同問(wèn)題中提供重要的數(shù)據(jù)特征［3］。由于項(xiàng)集的效用值不具備反單調(diào)性，高效用項(xiàng)集挖掘任務(wù)相較于頻繁項(xiàng)集挖掘任務(wù)更具有挑戰(zhàn)性。自高效用項(xiàng)集挖掘任務(wù)提出以來(lái)，研究人員陸續(xù)設(shè)計(jì)出一些有效的挖掘算法［4～7］。這些算法的不同之處在于搜索方法、事務(wù)表示形式、檢索策略、效用計(jì)算方式等方面。按照算法流程可以將現(xiàn)有的算法分為兩階段算法和一階段算法［8］。兩階段算法的核心思路是首先生成高效用項(xiàng)集的候選項(xiàng)集，然后計(jì)算候選項(xiàng)集的效用并篩除不滿(mǎn)足效用閾值的項(xiàng)集。該類(lèi)算法的代表有Two-Phase算法［9］、 HUI-PR算法［10］、HUIM-BDE算法［11］等。兩階段算法中生成并存儲(chǔ)不滿(mǎn)足效用閾值的候選項(xiàng)集浪費(fèi)了計(jì)算和存儲(chǔ)資源。為了避免資源浪費(fèi)，一些算法跳過(guò)候選項(xiàng)集生成步驟直接計(jì)算每個(gè)項(xiàng)集的效用并判斷其是否滿(mǎn)足效用閾值，即一階段算法。一階段算法的代表是FHM算法［12］、HUIM-SU算法［13］、MLHMiner算法［14］等。以上這些算法均為完全高效用項(xiàng)集挖掘算法，具有相同的輸入和輸出，只在運(yùn)行時(shí)間、內(nèi)存占用和可拓展性等性能方面存在差別。

在具有類(lèi)型標(biāo)簽的事務(wù)中，項(xiàng)集發(fā)現(xiàn)任務(wù)的主要研究方向是找到能夠揭示不同類(lèi)型事務(wù)差別特征的項(xiàng)集［15］。相關(guān)挖掘算法已被廣泛應(yīng)用于不同領(lǐng)域的問(wèn)題研究中，例如在醫(yī)學(xué)中探索不同癌癥之間的癥狀差別［16］，在教育學(xué)中發(fā)現(xiàn)不同學(xué)生群體的學(xué)習(xí)和心理狀態(tài)差別［17］，在市場(chǎng)營(yíng)銷(xiāo)學(xué)中揭示不同顧客群體的消費(fèi)行為差別［18］。當(dāng)傳統(tǒng)高效用項(xiàng)集挖掘算法應(yīng)用于具有類(lèi)型標(biāo)簽的事務(wù)時(shí)，雖然能夠報(bào)告大量滿(mǎn)足效用閾值約束的高效用項(xiàng)集，但其中大部分高效用項(xiàng)集表達(dá)的信息并不能正確體現(xiàn)事務(wù)的特征差別，即存在大量隨機(jī)產(chǎn)生的假陽(yáng)性高效用項(xiàng)集?；诩訇?yáng)性高效用項(xiàng)集提供的虛假特征作出的決策大概率會(huì)導(dǎo)致失敗的結(jié)果，因此找到結(jié)果中的假陽(yáng)性高效用項(xiàng)集并將其剔除是至關(guān)重要的。

分析發(fā)現(xiàn)，傳統(tǒng)算法報(bào)告大量假陽(yáng)性高效用項(xiàng)集的原因是這些算法無(wú)法識(shí)別項(xiàng)集在不同類(lèi)型事務(wù)中的效用分布。統(tǒng)計(jì)顯著性檢驗(yàn)是評(píng)估統(tǒng)計(jì)度量分布是否具有顯著性的有效方法［19］。目前，統(tǒng)計(jì)顯著性檢驗(yàn)被廣泛應(yīng)用于許多數(shù)據(jù)挖掘任務(wù)中篩除假陽(yáng)性結(jié)果，達(dá)到了提升挖掘結(jié)果可靠性的目的，例如社群發(fā)現(xiàn)任務(wù)［20］、對(duì)比序列模式挖掘任務(wù)［21］等。在高效用項(xiàng)集挖掘任務(wù)中，目前只存在少量基于統(tǒng)計(jì)顯著性檢驗(yàn)的高效用項(xiàng)集挖掘算法，例如HUSP算法［22］。因此，使用統(tǒng)計(jì)顯著性檢驗(yàn)剔除假陽(yáng)性高效用項(xiàng)集還需要投入大量的研究。

立足于上述分析，本文提出兩種基于不同類(lèi)型統(tǒng)計(jì)顯著性檢驗(yàn)的高效用項(xiàng)集挖掘算法：FHUI（Fisher testing-based high utility itemsets mining）和PHUI（permutation testing-based high utility itemsets mining）算法。該算法首先使用基于垂直事務(wù)結(jié)構(gòu)的ULB-Miner算法［23］找到原始事務(wù)集合中的待檢驗(yàn)高效用項(xiàng)集并根據(jù)項(xiàng)集長(zhǎng)度分組。接著，針對(duì)每組，F(xiàn)HUI算法使用Fisher檢驗(yàn)［24］根據(jù)高效用項(xiàng)集在不同類(lèi)型事務(wù)集合中的頻率分布生成零分布；而PHUI算法使用置換檢驗(yàn)［15］構(gòu)造置換事務(wù)集合并從中找到隨機(jī)效用差生成零分布。其中，PHUI算法設(shè)計(jì)了兩種置換策略：事務(wù)內(nèi)置換策略和事務(wù)間置換策略。最后，F(xiàn)HUI和PHUI算法從各自的零分布中計(jì)算出待檢驗(yàn)高效用項(xiàng)集的統(tǒng)計(jì)顯著性p值，并使用錯(cuò)誤發(fā)現(xiàn)率（false discovery rate， FDR）控制結(jié)果中的假陽(yáng)性高效用項(xiàng)集數(shù)量。基準(zhǔn)事務(wù)集合和仿真事務(wù)集合中的實(shí)驗(yàn)結(jié)果證明FHUI和PHUI算法能夠成功剔除一定數(shù)量的假陽(yáng)性高效用項(xiàng)集，從而達(dá)到更高的分類(lèi)任務(wù)正確率和平均效用，因此根據(jù)FHUI和PHUI算法報(bào)告的高效用項(xiàng)集作出的后續(xù)決策可靠性和實(shí)用性更強(qiáng)。此外，合理量化文獻(xiàn)［16～18］實(shí)例應(yīng)用中事務(wù)的內(nèi)部效用和外部效用后，F(xiàn)HUI和PHUI算法能夠直接應(yīng)用于對(duì)應(yīng)問(wèn)題的研究中。

1 基本概念

1.1 高效用項(xiàng)集

假設(shè)I={i1，i2，…，i|I|}表示項(xiàng)的集合，其中| |表示集合大小。每一個(gè)項(xiàng)ij都被分配了一個(gè)正整數(shù)eu（ij），表示其外部效用。項(xiàng)的集合X被稱(chēng)為項(xiàng)集，即XI。假設(shè)D={d1，d2，…，d|D|}表示一個(gè)事務(wù)集合，其中每一條dv由若干個(gè)項(xiàng)和一個(gè)類(lèi)型標(biāo)簽cq構(gòu)成。項(xiàng)ij在dv中的內(nèi)部效用被定義為一個(gè)正整數(shù)iu（ij， dv）。以超市消費(fèi)記錄事務(wù)為例，顧客的一次購(gòu)物記錄可以看作是一條事務(wù)，每個(gè)商品的利潤(rùn)可以量化為項(xiàng)的外部效用，每個(gè)商品購(gòu)買(mǎi)的數(shù)量可以量化為項(xiàng)的內(nèi)部效用。X在D中的支持度指的是D中包含X的事務(wù)數(shù)量，即sup（X， D）=|{dv|Xdv∧dv∈D}|。為了闡明基本概念，表1展示了一個(gè)事務(wù)集合的樣例，其中每個(gè)項(xiàng)的外部效用如表2所示。

項(xiàng)ij在事務(wù)dv中的效用由u（ij， dv）表示，定義為

u（ij，dv）=eu（ij）×iu（ij，dv）（1）

例如，表1中i2在d1中的效用u（i2， d1）=4×3=12。

項(xiàng)集X在事務(wù)dv中的效用由u（X， dv）表示，定義為

u（X，dv）=∑ij∈Xu（ij，dv）（2）

例如，假設(shè)X={i2， i3}，表1中u（X， d3） =4×4+1×2=18。

項(xiàng)集X在事務(wù)集合D中的效用由u（X， D）表示，定義為

u（X，D）=∑dv∈Du（X，dv）（3）

例如，同樣假設(shè)X={i2， i3}，表1中u（X， D）= u（X， d3）+u（X， d6）=18+10=28。

如果X在D中的u（X， D）不小于效用閾值αuti，那么X被稱(chēng)作高效用項(xiàng)集。例如，如果 αuti=25，那么表1中{i2， i3}為高效用項(xiàng)集。高效用項(xiàng)集挖掘任務(wù)的目標(biāo)是找到事務(wù)集合D中所有效用不低于αuti的項(xiàng)集。

1.2 統(tǒng)計(jì)顯著性檢驗(yàn)

面向具有類(lèi)型標(biāo)簽的事務(wù)時(shí)，由于傳統(tǒng)高效用項(xiàng)集挖掘算法無(wú)法捕獲高效用項(xiàng)集在不同類(lèi)型事務(wù)集合中的效用分布，結(jié)果中會(huì)存在一定數(shù)量隨機(jī)產(chǎn)生的假陽(yáng)性高效用項(xiàng)集。統(tǒng)計(jì)顯著性檢驗(yàn)是剔除假陽(yáng)性高效用項(xiàng)集的有效策略，其標(biāo)準(zhǔn)步驟是：首先，建立與任務(wù)匹配的零假設(shè)；其次，收集與零假設(shè)一致的證據(jù)值并使用這些證據(jù)值生成零分布；最后，從零分布中計(jì)算出待檢驗(yàn)?zāi)繕?biāo)的統(tǒng)計(jì)顯著性并作出是否拒絕零假設(shè)的決定。結(jié)合高效用項(xiàng)集挖掘任務(wù)，建立的零假設(shè)為待檢驗(yàn)高效用項(xiàng)集在不同類(lèi)型的事務(wù)集合中的效用分布是隨機(jī)產(chǎn)生的。證據(jù)值的收集與零分布的生成見(jiàn)2.1和2.2節(jié)具體的描述。

在統(tǒng)計(jì)顯著性檢驗(yàn)中，待檢驗(yàn)高效用項(xiàng)集的統(tǒng)計(jì)顯著性通常由p值量化，其定義是在零假設(shè)為真的前提下，發(fā)現(xiàn)一個(gè)比待檢驗(yàn)高效用項(xiàng)集更極端的項(xiàng)集概率，其中極端主要體現(xiàn)在證據(jù)值上。高效用項(xiàng)集挖掘算法通常會(huì)報(bào)告大量項(xiàng)集，該情況能夠使用多重假設(shè)檢驗(yàn)控制整體待檢驗(yàn)結(jié)果中假陽(yáng)性高效用項(xiàng)集的數(shù)量。在多重假設(shè)檢驗(yàn)中，F(xiàn)DR是使用最為頻繁的約束度量之一，其定義為在所有報(bào)告的結(jié)果中假陽(yáng)性結(jié)果占比的期望值。后續(xù)提出的FHUI和PHUI算法將使用FDR控制待檢驗(yàn)高效用項(xiàng)集中假陽(yáng)性高效用項(xiàng)集的數(shù)量。

2 挖掘算法

2.1 FHUI算法

FHUI算法的核心思路是先使用待檢驗(yàn)高效用項(xiàng)集在不同類(lèi)型事務(wù)中的頻率分布刻畫(huà)效用分布，再使用Fisher檢驗(yàn)將該頻率分布作為項(xiàng)集的零分布并從中計(jì)算出p值。具體而言，設(shè)類(lèi)型標(biāo)簽集合C={c1，c2}，根據(jù)C可以將D劃分成D=D1∪D2，其中D1中事務(wù)的類(lèi)型標(biāo)簽均為c1，D2中事務(wù)的類(lèi)型標(biāo)簽均為c2。待檢驗(yàn)高效用項(xiàng)集X在D中的頻率列聯(lián)表如表3所示。

根據(jù)表3中X的頻率分布，可以得出X的sup（X， D1）服從超幾何分布，即

h（sup（X，D1）|X）=|D1|sup（X，D1）|D2|sup（X，D2）|D|sup（X，D）（4）

根據(jù)Fisher檢驗(yàn)［24］，可以將式（4）作為待檢驗(yàn)高效用項(xiàng)集的零分布并從中計(jì)算出項(xiàng)集的p值，其中p值中的極端項(xiàng)集被定義為X在D1中頻率分布大于等于sup（X， D1）的情況。p值計(jì)算公式為

p1（X，D）=∑wj=1h（sup（X，D1）+j|X）（5）

其中：w=min{sup（X， D2）， |D1|－sup（X， D1）}。式（5）中包含了大量的二項(xiàng)式計(jì)算，導(dǎo)致計(jì)算開(kāi)銷(xiāo)較高。為了快速計(jì)算出待檢驗(yàn)高效用項(xiàng)集的p值，參考了文獻(xiàn)［25］中的近似上界方法加速p值計(jì)算，即

b（X，D）=sup（X，D2）（|D1|－sup（X，D1））（sup（X，D1）+1）（|D2|－sup（X，D2）+1）（6）

p1（X，D）≈h（sup（X，D1）|X）1－b（X，D）w+11－b（X，D）（7）

通過(guò)式（7）計(jì)算出所有待檢驗(yàn)高效用項(xiàng)集的p值后， FHUI算法使用BH方法［19］約束FDR達(dá)到控制假陽(yáng)性高效用項(xiàng)集數(shù)量的目的。BH方法計(jì)算公式如下：

BH（Rk，αsig）={X|p1（X，D）≤gX×αsig|Rk|∧X∈Rk}（8）

其中：Rk表示k長(zhǎng)度待檢驗(yàn)高效用項(xiàng)集的集合；αsig表示統(tǒng)計(jì)顯著水平；gX表示X在Rk中根據(jù)p值從小到大排序的索引值。詳細(xì)的FHUI算法流程見(jiàn)算法1。

算法1 FHUI 算法

輸入：事務(wù)集合D；效用閾值αuti；統(tǒng)計(jì)顯著水平αsig。

輸出：統(tǒng)計(jì)顯著高效用項(xiàng)集集合S。

a） R ← ULB_Miner （D， αuti）

b） R1， R2， …， Rmax_len （R） ← len_group（R）

c） L ← fac_buffer（D）

d） for k=1 to max_len （R） do

e） for each X in Rk do

f） X.w ← min{sup（X， D2）， |D1|－sup（X， D1）}

g） X.b ← b（X， D）

h） X.p ← p1（X， D， L）

i） end for

j） sort（Rk）

k） S ← S∪BH（Rk， αsig）

l） end for

m） return S

FHUI算法流程的說(shuō)明如下：

a）使用ULB-Miner算法［23］找到所有待檢驗(yàn)高效用項(xiàng)集，并使用len_group（）方法依據(jù)項(xiàng)集長(zhǎng)度分組（步驟a）b）），分組檢驗(yàn)的目的是為了避免項(xiàng)集長(zhǎng)度的影響。利用fac_buffer（）方法構(gòu)建階乘緩存加速后續(xù)二項(xiàng)式的計(jì)算（步驟c））。

b）針對(duì)各組中每個(gè)待檢驗(yàn)高效用項(xiàng)集X，先計(jì)算出其頻率分布上界X.w，再依據(jù)式（6）和（7）計(jì)算出X的p值（步驟d）～i））。

c）使用sort（）方法將每組中待檢驗(yàn)高效用項(xiàng)集依據(jù)p值從小到大進(jìn)行排序，再使用BH（）方法找到統(tǒng)計(jì)顯著高效用項(xiàng)集并放入集合S中（步驟j）～l））。最后，返回保存了所有統(tǒng)計(jì)顯著高效用項(xiàng)集的集合S（步驟m））。

FHUI算法的時(shí)間復(fù)雜度主要由四部分構(gòu)成：待檢驗(yàn)高效用項(xiàng)集挖掘、階乘緩存建立、零分布與p值計(jì)算以及假陽(yáng)性結(jié)果剔除。根據(jù)文獻(xiàn)［23］可知，ULB-Miner算法的時(shí)間復(fù)雜度是O（e2log e），其中e表示平均效用列表長(zhǎng)度；階乘緩存建立的時(shí)間復(fù)雜度為O（|D|）；每個(gè)項(xiàng)集生成零分布并從中計(jì)算p值是通過(guò)式（4）（6）（7）完成的，這三個(gè)公式的時(shí)間復(fù)雜度均為O（1），因此所有待檢驗(yàn)高效用項(xiàng)集零分布與p值計(jì)算的時(shí)間復(fù)雜度為O（|R|）；使用BH方法約束FDR剔除假陽(yáng)性結(jié)果的時(shí)間復(fù)雜度為O（|R|log|R|+|R|））。綜上，F(xiàn)HUI算法的時(shí)間復(fù)雜度為O（e2log e+|D|+|R|+|R|log|R|+|R|）），合并化簡(jiǎn)后的結(jié)果為O（e2log e+ |D|+|R|log|R|）。

2.2 PHUI算法

PHUI算法的核心思路是使用置換檢驗(yàn)構(gòu)造置換事務(wù)集合，利用從中收集的隨機(jī)效用差生成零分布并計(jì)算出項(xiàng)集的p值。效用差的定義為

udif（X，D）=abs（u（X，D1）－u（X，D2））（9）

其中：abs（）表示取絕對(duì)值。為了模擬隨機(jī)效用差的分布，PHUI算法在零假設(shè)約束下設(shè)計(jì)了兩種不同的置換策略構(gòu)造置換事務(wù)集合，即事務(wù)內(nèi)置換策略和事務(wù)間置換策略。

事務(wù)內(nèi)置換策略通過(guò)隨機(jī)置換每條事務(wù)的內(nèi)部效用構(gòu)造置換事務(wù)集合。具體而言，針對(duì)每一條事務(wù)，首先生成項(xiàng)的隨機(jī)置換序列，然后根據(jù)該序列置換項(xiàng)的內(nèi)部效用。例如，假設(shè)原始事務(wù)集合如圖1（a）所示，對(duì)于d1，生成的項(xiàng)的隨機(jī)置換序列是d1：{i4，i7，i5，i1，i3}。根據(jù)該序列，將i1的內(nèi)部效用置換給i4，將i3的內(nèi)部效用置換給i7，依此類(lèi)推，直到完成所有內(nèi)部效用的置換。假設(shè)余下事務(wù)的隨機(jī)置換序列為d2：{i4，i5，i2}、d3：{i7，i3，i6，i4}、d4：{i6，i4，i1}、d5：{i6，i4，i2，i1}。根據(jù)事務(wù)內(nèi)置換策略，最終構(gòu)造的置換事務(wù)集合D如圖1（b）所示。

事務(wù)間置換策略通過(guò)置換事務(wù)之間的類(lèi)型標(biāo)簽、項(xiàng)及其內(nèi)部效用構(gòu)造置換事務(wù)集合。詳細(xì)步驟如下：

a）選擇一個(gè)［1， min_tran（D）］的隨機(jī)整數(shù)z，其中min_tran（）返回D中最短的事務(wù)長(zhǎng)度；并為每條事務(wù)隨機(jī)標(biāo)記z個(gè)項(xiàng)的位置，將這些位置信息存入集合G中。

b）生成一個(gè)事務(wù)編號(hào)的隨機(jī)置換序列，根據(jù)該序列首先置換每條事務(wù)的類(lèi)型標(biāo)簽，然后置換每條事務(wù)在G中標(biāo)記位置對(duì)應(yīng)的項(xiàng)及其內(nèi)部效用。置換后事務(wù)若存在相同的項(xiàng)，則進(jìn)行內(nèi)部效用合并。

舉個(gè)例子，給定D如圖1（a）所示，從中可知min_tran（D）=3。假設(shè)z=2，G={d1：{2，5}， d2：{1，2}， d3：{3，4}， d4：{1，3}， d5： {2，3}}，生成的事務(wù)編號(hào)隨機(jī)置換序列為{d4，d1，d5，d2，d3}。根據(jù)該序列，先將d1的類(lèi)型標(biāo)簽置換給d4，再將d1中{2，5}位置的項(xiàng)及其內(nèi)部效用置換到d4的{1，3}位置；先將d2的類(lèi)型標(biāo)簽置換給d1，再將d2中{1，2}位置的項(xiàng)及其內(nèi)部效用置換給d1的{2，5}位置，置換后存在相同的項(xiàng)i4，故將其內(nèi)部效用合并得到（i4，5）；如此迭代，直至完成隨機(jī)置換序列所有的置換，最終構(gòu)造的置換事務(wù)集合D如圖1（c）所示。

使用事務(wù)內(nèi)或事務(wù)間置換策略構(gòu)造一定數(shù)量的置換事務(wù)集合后，PHUI算法從這些集合中收集待檢驗(yàn)高效用項(xiàng)集的隨機(jī)效用差為不同長(zhǎng)度的項(xiàng)集生成置換檢驗(yàn)零分布Nk。隨后，再通過(guò)式（10）計(jì)算出待檢驗(yàn)高效用項(xiàng)集p值：

p2（X，D，Nk）=|{j|udif（X，D）≤j∧j∈Nk}||Nk|（10）

計(jì)算出所有待檢驗(yàn)高效用項(xiàng)集的p值后，PHUI算法同樣使用BH方法約束FDR，即使用式（8）控制假陽(yáng)性高效用項(xiàng)集的數(shù)量。詳細(xì)的PHUI算法流程見(jiàn)算法2～4。其中，算法2流程的說(shuō)明如下：

a）使用ULB-Miner算法［23］找到所有待檢驗(yàn)高效用項(xiàng)集，并使用len_group（）方法分組。此外，將每組保存隨機(jī)效用差的集合Nk初始化為空集（步驟a）～c））。

b）執(zhí)行t次相同的置換策略生成置換事務(wù)集合，即采用基于事務(wù)內(nèi)置換策略的per_trans（）方法或采用基于事務(wù)間置換策略的per_trans（）方法。在每一次置換過(guò)程中，首先使用per_trans（）方法構(gòu)造置換事務(wù)集合D；接著使用uti_update（）方法更新待檢驗(yàn)高效用項(xiàng)集在D中的隨機(jī)效用差；最后使用uti_extract（）方法提取各長(zhǎng)度項(xiàng)集的隨機(jī)效用差并放入Nk中（步驟d）～j））。執(zhí)行完t次置換后，Nk中保存的隨機(jī)效用差構(gòu)成k長(zhǎng)度待檢驗(yàn)高效用項(xiàng)集的零分布。

c）根據(jù)式（10）計(jì)算出每組中所有待檢驗(yàn)高效用項(xiàng)集的p值后，使用sort（）和BH（）方法找到統(tǒng)計(jì)顯著高效用項(xiàng)集并放入集合S中（步驟k）～q））。最后，返回保存了所有統(tǒng)計(jì)顯著高效用項(xiàng)集的集合S（步驟r））。

算法2 PHUI 算法

輸入：事務(wù)集合D；效用閾值αuti；統(tǒng)計(jì)顯著水平αsig；置換次數(shù)t。

輸出：統(tǒng)計(jì)顯著高效用項(xiàng)集集合S。

a） R ← ULB_Miner （D， αuti）

b） R1， R2， …， Rmax_len （R） ← len_group（R）

c） N1， N2， …， Nmax_len（R）←

d） for j=1 to t do

e） D ← per_trans（D）

f） R← uti_update（D， R）

g） for k=1 to max_len （R） do

h） Nk ← Nk∪ uti_extract（R， k）

i） end for

j） end for

k） for k=1 to max_len （R） do

l） for each X in Rk do

m） X.p ← p2（X， D， Nk）

n） end for

o） sort（Rk）

p） S ← S∪BH（Rk， αsig）

q） end for

r） return S

算法3描述了基于事務(wù)內(nèi)置換策略的per_trans（）方法。針對(duì)每條事務(wù)d，先使用ran_items（）方法生成一個(gè)項(xiàng)的隨機(jī)置換序列M，再使用in_permute（）方法根據(jù)M置換每個(gè)項(xiàng)的內(nèi)部效用便得到了一條置換事務(wù)d。最后，返回包含所有d的置換事務(wù)集合D。

算法3 基于事務(wù)內(nèi)置換策略的per_trans（）方法

輸入：原始事務(wù)集合D。

輸出：置換事務(wù)集合D。

a） D←

b） for each d in D do

c） M ← ran_items（d）

d） d← in_permute（M）

e） D← D∪ d

f） end for

g） return D

算法4描述了基于事務(wù)間置換策略的per_trans（）方法。首先，使用ran_number（）生成一個(gè)［1， min_trans（D）］之間的隨機(jī)整數(shù)z，并使用ran_positions（）為每條事務(wù)標(biāo)記z個(gè)項(xiàng)的隨機(jī)位置存入G中；接著，使用ran_tids（）方法生成一個(gè)事務(wù)編號(hào)的隨機(jī)置換序列F；然后，針對(duì)每條事務(wù)d，先使用lab_ permute（）方法根據(jù)F置換類(lèi)型標(biāo)簽得到d1，再根據(jù)F和G置換d1中標(biāo)記位置對(duì)應(yīng)的項(xiàng)及其內(nèi)部效用得到一條置換事務(wù)d2；最后，返回包含所有d2的置換事務(wù)集合D。

算法4 基于事務(wù)間置換策略的per_trans（）方法

輸入：原始事務(wù)集合D。

輸出：置換事務(wù)集合D。

a） D← ， G ←

b） z ← ran_number（1， min_trans（D））

c） for each d in D do

d） G ← G∪ran_positions（d， z）

e） end for

f） F ← ran_tids（D）

g） for each d in D do

h） d1 ← lab_ permute（F）

i） d2← bet_permute（d1， F， G）

j） D← D∪ d2

k） end for

l） return D

PHUI算法的時(shí)間復(fù)雜度主要由四部分構(gòu)成：待檢驗(yàn)高效用項(xiàng)集挖掘、置換檢驗(yàn)零分布生成、p值計(jì)算以及假陽(yáng)性結(jié)果剔除。其中，待檢驗(yàn)高效用項(xiàng)集挖掘和假陽(yáng)性結(jié)果剔除這兩部分與FHUI算法采用了相同的步驟，因此其時(shí)間復(fù)雜度也相同，分別為O（e2log e）和O（|R|log|R|+|R|）。每個(gè)項(xiàng)集的p值能夠通過(guò)置換檢驗(yàn)零分布直接計(jì)算得出，因此所有待檢驗(yàn)高效用項(xiàng)集p值計(jì)算的時(shí)間復(fù)雜度是O（|R|）。

由于算法3和4使用了不同的置換策略構(gòu)造置換事務(wù)集合D，從而其生成置換檢驗(yàn)零分布的時(shí)間復(fù)雜度也不相同。具體而言，事務(wù)內(nèi)置換策略通過(guò)置換每條事務(wù)的內(nèi)部效用生成置換事務(wù)集合，其時(shí)間復(fù)雜度為O（|D|a），其中a表示d中包含的項(xiàng)的數(shù)量。事務(wù)間置換策略通過(guò)置換事務(wù)之間的類(lèi)型標(biāo)簽、項(xiàng)及其內(nèi)部效用構(gòu)造置換事務(wù)集合，其時(shí)間復(fù)雜度為O（|D|（z+a））。生成D后，兩種策略使用同樣的方式更新和提取隨機(jī)效用差，其時(shí)間復(fù)雜度為O（|R|）。因此，經(jīng)過(guò)t次事務(wù)內(nèi)置換策略生成置換檢驗(yàn)零分布的時(shí)間復(fù)雜度為O（t（|D|a+|R|））；經(jīng)過(guò)t次事務(wù)間置換策略生成置換檢驗(yàn)零分布的時(shí)間復(fù)雜度為O（t（|D|（z+a）+|R|））。

綜上，基于事務(wù)內(nèi)置換策略的PHUI算法的時(shí)間復(fù)雜度是O（e2log e+t（|D|a+|R|）+|R|+|R|log|R|+|R|），合并化簡(jiǎn)后的結(jié)果為O（e2log e+t|D|a+|R|（log|R|+t））；基于事務(wù)間置換策略的PHUI算法的時(shí)間復(fù)雜度是O（e2log e+t（|D|（z+a）+|R|）+|R|+|R|log|R|+|R|），合并化簡(jiǎn)后的結(jié)果為O（e2log e+t|D|（z+a）+|R|（log|R|+t））。

PHUI算法執(zhí)行過(guò)程中需要構(gòu)造t次置換事務(wù)集合，導(dǎo)致計(jì)算開(kāi)銷(xiāo)較大。為了提升算法的實(shí)用性，分析發(fā)現(xiàn)每個(gè)置換事務(wù)集合的構(gòu)造和處理是相互獨(dú)立的，該情況能夠使用分布式并行化技術(shù)減少置換事務(wù)集合構(gòu)造和處理的時(shí)間。具體而言，假設(shè)有y個(gè)并行任務(wù)節(jié)點(diǎn)，每個(gè)任務(wù)節(jié)點(diǎn)執(zhí)行完t/y次PHUI算法的步驟e）～i）后，將所有節(jié)點(diǎn)返回的局部Nk進(jìn)行合并就能得到各個(gè)長(zhǎng)度待檢驗(yàn)高效用項(xiàng)集的全局Nk。分布式并行化的PHUI算法流程如圖2所示。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)對(duì)比算法

為了分析與驗(yàn)證FHUI和PHUI算法挖掘高效用項(xiàng)集的能力，在基準(zhǔn)事務(wù)集合和仿真事務(wù)集合上實(shí)施了大量對(duì)比實(shí)驗(yàn)。對(duì)比算法為HUIM-SU算法［13］、EHNL算法［26］ 和HUSP算法［22］。HUIM-SU算法設(shè)計(jì)了簡(jiǎn)化的效用列表結(jié)構(gòu)快速計(jì)算項(xiàng)集的效用；EHNL算法在效用閾值約束的基礎(chǔ)上額外使用了長(zhǎng)度約束篩除部分冗余高效用項(xiàng)集。這兩個(gè)對(duì)比算法均為基于效用閾值約束的算法，未采用任何假陽(yáng)性高效用項(xiàng)集處理或預(yù)防策略。HUSP算法是基于統(tǒng)計(jì)顯著性檢驗(yàn)的算法，使用了LAMP方法計(jì)算項(xiàng)集的統(tǒng)計(jì)顯著性。為了便于實(shí)驗(yàn)對(duì)比，將原始HUSP算法使用的錯(cuò)誤率判斷族約束更改為FDR約束。此外，為了區(qū)分PHUI算法使用不同的置換策略，PHUI-w算法表示使用了事務(wù)內(nèi)置換策略，PHUI-b算法表示使用了事務(wù)間置換策略。

3.2 實(shí)驗(yàn)基本設(shè)置

在眾多分布式并行化計(jì)算框架中，Spark框架內(nèi)存計(jì)算效率高、MLlib庫(kù)豐富，使得其更加適用于迭代運(yùn)算較多的數(shù)據(jù)挖掘任務(wù)，目前許多傳統(tǒng)模式發(fā)現(xiàn)算法使用Spark框架完成了特定模式的分布式并行挖掘［1］，因此提出的PHUI算法同樣采用Spark框架實(shí)現(xiàn)置換事務(wù)集合生成和計(jì)算的分布式并行化。所有算法均使用Java語(yǔ)言實(shí)現(xiàn)，且所有實(shí)驗(yàn)均運(yùn)行在3臺(tái)計(jì)算機(jī)組成的集群上，每臺(tái)配置為3.60 GHz（12核）CPU和64 GB內(nèi)存。

在置換檢驗(yàn)中，需要構(gòu)造一定數(shù)量的置換事務(wù)集合生成零分布，數(shù)量越多，生成的零分布越準(zhǔn)確，但相應(yīng)的計(jì)算開(kāi)銷(xiāo)也越大，通常1 000是置換檢驗(yàn)中常用的數(shù)量設(shè)置［15］。對(duì)于αsig而言，閾值設(shè)置得越低，假陽(yáng)性結(jié)果的數(shù)量會(huì)減少，但同時(shí)非假陽(yáng)性結(jié)果的數(shù)量也會(huì)大量減少，因此需要在兩種結(jié)果中進(jìn)行相應(yīng)平衡，0.05是大部分統(tǒng)計(jì)顯著性檢驗(yàn)中常用的αsig閾值［19］。

3.3 實(shí)驗(yàn)數(shù)據(jù)信息

3.3.1 基準(zhǔn)事務(wù)集合信息

實(shí)驗(yàn)采用了高效用項(xiàng)集挖掘任務(wù)中廣泛使用的4個(gè)基準(zhǔn)事務(wù)集合：chess［27］、mushroom［27］、connect［27］、protein［8］，詳細(xì)信息如表4所示。其中，connect集合含有3種類(lèi)型標(biāo)簽，為了便于呈現(xiàn)實(shí)驗(yàn)結(jié)果，將“l(fā)oss”和“draw”對(duì)應(yīng)的事務(wù)進(jìn)行了合并。

3.3.2 仿真事務(wù)集合信息

基準(zhǔn)事務(wù)集合中缺少高效用項(xiàng)集的真假信息，于是實(shí)驗(yàn)構(gòu)造了仿真事務(wù)集合。內(nèi)部效用、外部效用和頻率分布是影響高效用項(xiàng)集效用分布的重要因素。根據(jù)這三個(gè)因素，分別構(gòu)造了三種不同類(lèi)型的仿真事務(wù)集合，具體步驟為：

a）假設(shè)Ifal={i1，i2，…，i60}表示構(gòu)成隨機(jī)項(xiàng)集的字母表集合；Itru={i61，i62，…，i74}表示構(gòu)成真實(shí)植入項(xiàng)集的字母表集合；C= {c1，c2}表示類(lèi)型標(biāo)簽集合。

b）分配一個(gè)［1，10］的隨機(jī)整數(shù)給Ifal中每一個(gè)項(xiàng)ifal作為該項(xiàng)的外部效用，即eu（ifal） ∈［1，10］。

c）將Ifal中的項(xiàng)分為20組，每組包含3個(gè)項(xiàng)。為了構(gòu)造一條事務(wù)dsyn，從每組中隨機(jī)抽取一個(gè)項(xiàng)ifal，并為每個(gè)抽取的項(xiàng)分配一個(gè)［1，10］的整數(shù)作為內(nèi)部效用，即iu（ifal， dsyn） ∈［1，10］。

d）重復(fù)執(zhí)行上一步驟直至構(gòu)造4 000條事務(wù)。將c1分配給前2 000條事務(wù)構(gòu)成D1，c2分配給后2 000條事務(wù)構(gòu)成D2，計(jì)算4 000條事務(wù)的總效用utotal。

e） 使用Itru中不同的項(xiàng)構(gòu)造5個(gè)1長(zhǎng)度、3個(gè)2長(zhǎng)度、1個(gè)3長(zhǎng)度的高效用項(xiàng)集。選擇f-1、f-2或f-3步驟中的其中一種方式進(jìn)行全部植入，并保證每個(gè)植入項(xiàng)集的效用在［0.01 utotal， 0.02 utotal］。

f-1）內(nèi)部效用主導(dǎo)植入方式：植入項(xiàng)集中每個(gè)項(xiàng)itru的eu（itru） ∈［1，10］，iu（itru， dsyn） ∈［20，30］，D1和D2的頻率分布在1.5∶1至3∶1之間。

f-2）外部效用主導(dǎo)植入方式：植入項(xiàng)集中每個(gè)項(xiàng)itru的eu（itru） ∈［20，30］，iu（itru， dsyn） ∈［1，10］，D1和D2的頻率分布在1.5∶1至3∶1之間。

f-3）頻率分布主導(dǎo)植入方式：植入項(xiàng)集中每個(gè)項(xiàng)itru的eu（itru） ∈［1，10］，iu（itru， dsyn） ∈［1，10］，D1和D2的頻率分布在3∶1至6∶1之間。

實(shí)驗(yàn)結(jié)果中，如果報(bào)告的一個(gè)高效用項(xiàng)集只包含Ifal中的項(xiàng)，那么該項(xiàng)集被認(rèn)定為假陽(yáng)性高效用項(xiàng)集，因?yàn)檫@樣的項(xiàng)集沒(méi)有包含任何真實(shí)信息。此外，為了避免偶然性，分別使用內(nèi)部效用主導(dǎo)、外部效用主導(dǎo)和頻率分布主導(dǎo)的植入方式獨(dú)立構(gòu)造10個(gè)仿真事務(wù)集合。

3.4 基準(zhǔn)事務(wù)集合實(shí)驗(yàn)

3.4.1 報(bào)告的高效用項(xiàng)集數(shù)量

為了比較各個(gè)算法挖掘高效用項(xiàng)集的能力，實(shí)驗(yàn)比較了各個(gè)算法在每個(gè)基準(zhǔn)事務(wù)集合中相同αuti參數(shù)下報(bào)告的高效用項(xiàng)集數(shù)量，其中chess集合的αuti=5.2×105，mushroom集合的αuti=2.5×105，connect集合的αuti=1.4×107，protein集合的αuti=3.4×105。各個(gè)算法報(bào)告的高效用項(xiàng)集數(shù)量如圖3所示，從中可以看出，報(bào)告的高效用項(xiàng)集數(shù)量關(guān)系為：HUIM-SU>EHNL>>PHUI-b>PHUI-w>FHUI>HUSP。

造成上述結(jié)果的原因是HUIM-SU和EHNL算法是基于效用閾值約束的算法，而HUSP、FHUI、PHUI-w和PHUI-b算法是基于統(tǒng)計(jì)顯著性檢驗(yàn)的算法?；谛в瞄撝导s束的算法只要項(xiàng)集滿(mǎn)足αuti閾值就會(huì)被報(bào)告；而基于統(tǒng)計(jì)顯著性檢驗(yàn)的算法不僅運(yùn)用了效用閾值約束項(xiàng)集，還在其基礎(chǔ)上引入統(tǒng)計(jì)顯著性檢驗(yàn)評(píng)估項(xiàng)集的效用分布可靠性。因此基于效用閾值約束的算法報(bào)告的結(jié)果中存在大量沒(méi)有正確表達(dá)不同類(lèi)型事務(wù)差別特征的項(xiàng)集，從而其報(bào)告的項(xiàng)集數(shù)量遠(yuǎn)遠(yuǎn)大于基于統(tǒng)計(jì)顯著性檢驗(yàn)的算法。此外，大量的高效用項(xiàng)集還會(huì)給后續(xù)任務(wù)帶來(lái)驗(yàn)證困難、抽樣選擇、合并表示等額外的問(wèn)題。

進(jìn)一步分析，在基于效用閾值約束的算法中，EHNL算法使用了項(xiàng)集長(zhǎng)度約束篩除較長(zhǎng)的冗余高效用項(xiàng)集，使得其項(xiàng)集數(shù)量相較于HUIM-SU算法更少。在基于統(tǒng)計(jì)顯著性檢驗(yàn)的算法中，各個(gè)算法使用不同的檢驗(yàn)方法計(jì)算p值，使得報(bào)告的統(tǒng)計(jì)顯著高效用項(xiàng)集數(shù)量也不相同，但整體數(shù)量差距并不巨大。由于不確定其中假陽(yáng)性高效用項(xiàng)集和非假陽(yáng)性高效用項(xiàng)集的數(shù)量，從而無(wú)法單從整體數(shù)量上對(duì)比各個(gè)算法挖掘能力的優(yōu)劣。

YRuH10HvBUDCHOLRA2IQZOLxDBMqfFsCwnm4sSn428I=3.4.2 分類(lèi)任務(wù)正確率

基準(zhǔn)事務(wù)集合缺少高效用項(xiàng)集的真假信息，為了驗(yàn)證各個(gè)算法報(bào)告的高效用項(xiàng)集的可靠性，接下來(lái)的實(shí)驗(yàn)將使用算法報(bào)告的高效用項(xiàng)集作為事務(wù)的特征進(jìn)行后續(xù)分類(lèi)任務(wù)。具體而言，如果一條事務(wù)包含某個(gè)高效用項(xiàng)集，則將該項(xiàng)集對(duì)應(yīng)的特征置1，反之則置0。該實(shí)驗(yàn)有效性的理論依據(jù)是在具有類(lèi)型標(biāo)簽的事務(wù)中報(bào)告的高效用項(xiàng)集應(yīng)當(dāng)體現(xiàn)不同類(lèi)型事務(wù)的特征差別，否則類(lèi)型標(biāo)簽毫無(wú)意義［6］。為了減少分類(lèi)器自身的影響，實(shí)驗(yàn)采用了樸素貝葉斯和隨機(jī)森林兩種不同類(lèi)型的分類(lèi)器。

兩種分類(lèi)器在各個(gè)基準(zhǔn)事務(wù)集合中的分類(lèi)正確率如表5所示，從中可以獲知HUIM-SU和EHNL算法構(gòu)造特征的分類(lèi)正確率明顯低于HUSP、FHUI、PHUI-w和PHUI-b算法。此外，基于統(tǒng)計(jì)顯著性檢驗(yàn)算法構(gòu)造特征分類(lèi)正確率的高低關(guān)系為HUSP＜FHUI＜PHUI-w＜PHUI-b。

在該實(shí)驗(yàn)結(jié)果中，導(dǎo)致HUIM-SU和EHNL算法構(gòu)造特征的分類(lèi)正確率低于HUSP、FHUI、PHUI-w和PHUI-b算法的主要原因是基于閾值約束的算法中未考慮高效用項(xiàng)集的效用分布，導(dǎo)致其大量的構(gòu)造特征源自于錯(cuò)誤表達(dá)事務(wù)差別特征的假陽(yáng)性高效用項(xiàng)集；反之，基于統(tǒng)計(jì)顯著性檢驗(yàn)的算法使用不同檢驗(yàn)方法剔除了一定數(shù)量的假陽(yáng)性高效用項(xiàng)集，因而其構(gòu)造特征對(duì)應(yīng)的統(tǒng)計(jì)顯著性高效用項(xiàng)集正確體現(xiàn)了不同類(lèi)型事務(wù)的差別特征。進(jìn)一步分析，對(duì)于分類(lèi)器而言，其根本目的是擬合訓(xùn)練數(shù)據(jù)的同時(shí)實(shí)現(xiàn)測(cè)試數(shù)據(jù)的良好泛化。由于假陽(yáng)性高效用項(xiàng)集對(duì)應(yīng)的特征無(wú)法體現(xiàn)不同類(lèi)型事務(wù)的差別，所以其本質(zhì)上是與分類(lèi)任務(wù)無(wú)關(guān)的特征［6］，這些無(wú)關(guān)特征的加入造成了輸入數(shù)據(jù)本身的偏差，從而嚴(yán)重影響了分類(lèi)器的泛化能力。此外，基于閾值約束的算法構(gòu)造特征的維度遠(yuǎn)大于基于統(tǒng)計(jì)顯著性檢驗(yàn)的算法，且大量特征是任務(wù)無(wú)關(guān)特征，導(dǎo)致同類(lèi)型事務(wù)在其相應(yīng)的特征空間中變得更加稀疏，進(jìn)一步增加了分類(lèi)任務(wù)的難度。

在基于統(tǒng)計(jì)顯著性檢驗(yàn)的算法中，HUSP 和FHUI算法構(gòu)造特征的分類(lèi)正確率低于PHUI-w和PHUI-b算法，其中的原因是HUSP 和FHUI算法均使用項(xiàng)集的頻率分布間接刻畫(huà)效用分布，而PHUI-w和PHUI-b算法使用隨機(jī)效用差直接刻畫(huà)效用分布。因此HUSP 和FHUI算法構(gòu)造特征主要源自頻率分布呈現(xiàn)顯著差別的高效用項(xiàng)集，未考慮效用分布與頻率分布不一致的高效用項(xiàng)集提供的差別特征。

進(jìn)一步而言，HUSP 算法構(gòu)造特征的分類(lèi)正確率低于FHUI算法，這是因?yàn)镠USP算法未進(jìn)行分組檢驗(yàn)，導(dǎo)致誤判了少量非假陽(yáng)性高效用項(xiàng)集；PHUI-w算法構(gòu)造特征的分類(lèi)正確率低于PHUI-b算法，其原因是事務(wù)內(nèi)置換策略固定了項(xiàng)集的頻率分布，事務(wù)間置換策略未固定項(xiàng)集的頻率分布，導(dǎo)致PHUI-w算法遺漏了效用分布主要體現(xiàn)在頻率分布差別的項(xiàng)集提供的特征。

3.5 仿真事務(wù)集合實(shí)驗(yàn)

3.5.1 報(bào)告的高效用項(xiàng)集情況

假陽(yáng)性高效用項(xiàng)集提供的錯(cuò)誤差別特征會(huì)誤導(dǎo)后續(xù)任務(wù)的決策，例如3.4.2節(jié)中的分類(lèi)任務(wù)等。為了直觀比較各個(gè)算法報(bào)告結(jié)果中高效用項(xiàng)集的具體情況，在三種不同類(lèi)型仿真事務(wù)集合中運(yùn)行了各個(gè)算法，其中αuti=3.0×104。

各個(gè)算法在三種仿真事務(wù)集合中報(bào)告的高效用項(xiàng)集信息如表6所示，其中每個(gè)結(jié)果取自于10個(gè)相同類(lèi)型仿真事務(wù)集合的平均值。從表6中可以獲知，HUIM-SU和EHNL算法在三種不同類(lèi)型的仿真事務(wù)集合中均報(bào)告了大量的假陽(yáng)性高效用項(xiàng)集，其數(shù)量占比達(dá)到了67%以上；相反地，HUSP、FHUI、PHUI-w和PHUI-b算法報(bào)告的結(jié)果中假陽(yáng)性高效用項(xiàng)集的數(shù)量占比均小于4.9%。該結(jié)果驗(yàn)證了基于統(tǒng)計(jì)顯著性檢驗(yàn)的算法能夠有效剔除結(jié)果中大量的假陽(yáng)性高效用項(xiàng)集，保留的項(xiàng)集可靠性更強(qiáng)。此外，提出的FHUI、PHUI-w和PHUI-b算法報(bào)告的結(jié)果中假陽(yáng)性高效用項(xiàng)集的數(shù)量占比低于HUSP算法。

對(duì)于內(nèi)部效用主導(dǎo)和外部效用主導(dǎo)的仿真事務(wù)集合，各個(gè)算法呈現(xiàn)的實(shí)驗(yàn)結(jié)果基本一致。其原因是雖然兩種不同類(lèi)型仿真事務(wù)集合植入項(xiàng)集的內(nèi)部效用和外部效用不相同，但其u（ij， dv）和頻率分布基本一致，從而不會(huì)對(duì)算法挖掘結(jié)果造成顯著影響。在這兩種仿真事務(wù)集合中，存在大量?jī)H由Ifal中的項(xiàng)隨機(jī)構(gòu)成的項(xiàng)集，且這些項(xiàng)集的效用恰好滿(mǎn)足αuti閾值，即假陽(yáng)性高效用項(xiàng)集。由于基于閾值約束的算法缺失隨機(jī)項(xiàng)集識(shí)別能力，導(dǎo)致其結(jié)果中假陽(yáng)性高效用項(xiàng)集占比很高；相反地，基于統(tǒng)計(jì)顯著性檢驗(yàn)的算法能夠根據(jù)效用分布識(shí)別隨機(jī)項(xiàng)集并將其剔除，從而其結(jié)果中假陽(yáng)性高效用項(xiàng)集占比較低。

進(jìn)一步分析，HUSP 和FHUI算法在這兩種仿真事務(wù)集合中報(bào)告的非假陽(yáng)性項(xiàng)集數(shù)量顯著低于PHUI-w和PHUI-b算法，從而使結(jié)果中假陽(yáng)性項(xiàng)集占比略高。造成該結(jié)果的原因是HUSP 和FHUI算法基于頻率分布計(jì)算p值，當(dāng)植入項(xiàng)集的頻率分布接近1.5∶1時(shí)，這兩個(gè)算法會(huì)將植入項(xiàng)集及其部分子項(xiàng)集或超項(xiàng)集判斷為假陽(yáng)性高效用項(xiàng)集；而PHUI-w和PHUI-b算法直接通過(guò)隨機(jī)效用差計(jì)算p值，對(duì)于上述項(xiàng)集的誤判概率較小。此外，由于HUSP算法未實(shí)施分組檢驗(yàn)，干擾了FDR約束截?cái)嚅撝档挠?jì)算，導(dǎo)致其非假陽(yáng)性項(xiàng)集數(shù)量和假陽(yáng)性項(xiàng)集占比劣于HUSP算法。PHUI-b算法的非假陽(yáng)性項(xiàng)集數(shù)量和假陽(yáng)性項(xiàng)集占比優(yōu)于PHUI-w算法，這是因?yàn)镻HUI-w算法使用的事務(wù)內(nèi)置換策略是有條件的假設(shè)檢驗(yàn)，即固定了項(xiàng)集的頻率分布，該條件會(huì)使得項(xiàng)集計(jì)算的p值相較于真實(shí)p值偏大［21］，從而導(dǎo)致FDR約束剔除的非假陽(yáng)性項(xiàng)集數(shù)量增多。值得注意的是，不能單純地從假陽(yáng)性項(xiàng)集數(shù)量判斷基于假設(shè)檢驗(yàn)算法的性能，因?yàn)樵贔DR約束下隨著非假陽(yáng)性項(xiàng)集數(shù)量的增加，假陽(yáng)性項(xiàng)集數(shù)量必然也會(huì)增加。

在頻率分布主導(dǎo)的仿真事務(wù)集合中，上述結(jié)果的差異分析同樣適用。進(jìn)一步縱向比較，HUIM-SU和EHNL算法的性能略微優(yōu)于其在效用主導(dǎo)的仿真事務(wù)集合，原因是隨著植入項(xiàng)集頻率分布的增加，其子項(xiàng)集或者超項(xiàng)集更容易達(dá)到αuti閾值。同樣地，HUSP 和FHUI算法的性能也要優(yōu)于其在效用主導(dǎo)的仿真事務(wù)集合中的表現(xiàn)，這是因?yàn)轭l率分布主導(dǎo)的仿真事務(wù)集合植入項(xiàng)集的最低頻率分布為3∶1，頻率分布的增加降低了這兩個(gè)算法對(duì)植入項(xiàng)集的子項(xiàng)集或超項(xiàng)集的誤判率。相反，PHUI-w算法在該仿真事務(wù)集合中的性能表現(xiàn)不及其余兩種類(lèi)型的仿真事務(wù)集合，其中的原因是PHUI-w算法固定了項(xiàng)集的頻率分布，當(dāng)項(xiàng)集頻率分布增大時(shí)，該變化無(wú)法直接反饋到效用分布的變化上。PHUI-b算法使用的事務(wù)間置換策略是無(wú)條件檢驗(yàn)，能夠識(shí)別植入項(xiàng)集頻率分布變化對(duì)效用分布的影響，因此其性能表現(xiàn)與其余兩種類(lèi)型的仿真事務(wù)集合一致。

3.5.2 平均效用

算法報(bào)告的高效用項(xiàng)集平均效用越高，表明其報(bào)告的高效用項(xiàng)集的實(shí)用性越強(qiáng)。舉例而言，在市場(chǎng)消費(fèi)應(yīng)用中，項(xiàng)集的效用越高意味著對(duì)應(yīng)商品的利潤(rùn)越高；在疾病基因分析中，項(xiàng)集的效用越高意味著對(duì)應(yīng)基因與疾病的關(guān)聯(lián)性越高。為了比較各個(gè)算法報(bào)告項(xiàng)集的實(shí)用性，實(shí)驗(yàn)統(tǒng)計(jì)了各個(gè)算法在30個(gè)仿真事務(wù)集合中報(bào)告的高效用項(xiàng)集的平均效用，詳細(xì)情況如圖4所示。從中可以看出，各個(gè)算法平均效用的高低關(guān)系為：EHNL＜HUIM-SU＜HUSP＜FHUI＜PHUI-w＜PHUI-b。

HUIM-SU和EHNL算法報(bào)告項(xiàng)集的平均效用低于基于統(tǒng)計(jì)顯著性檢驗(yàn)的算法，其原因是這兩個(gè)算法報(bào)告結(jié)果中隨機(jī)產(chǎn)生的大部分假陽(yáng)性高效用項(xiàng)集的效用僅僅略高于αuti閾值，而大部分統(tǒng)計(jì)顯著高效用項(xiàng)集的效用明顯超過(guò)αuti閾值。由于EHNL算法剔除的長(zhǎng)度較長(zhǎng)的高效用項(xiàng)集表現(xiàn)出了較高的效用，導(dǎo)致其平均效用低于HUIM-SU算法。

進(jìn)一步比較，HUSP和FHUI算法報(bào)告項(xiàng)集的平均效用低于PHUI-w和PHUI-b算法，這是因?yàn)檫@兩個(gè)算法誤判的低頻率分布植入項(xiàng)集及其超項(xiàng)集u（ij， dv）更高，容易表現(xiàn)出更高的效用。此外，由于PHUI-w算法計(jì)算p值偏大，而錯(cuò)誤剔除的非假陽(yáng)性項(xiàng)集也表現(xiàn)出了較高的效用，從而其報(bào)告項(xiàng)集的平均效用不及PHUI-b算法。綜上，PHUI-b算法報(bào)告的高效用項(xiàng)集實(shí)用性更強(qiáng)。

3.5.3 運(yùn)行時(shí)間

運(yùn)行時(shí)間是算法可用性的一個(gè)度量指標(biāo)，不同的后續(xù)任務(wù)場(chǎng)景會(huì)對(duì)算法運(yùn)行時(shí)間有不同的要求。例如有的后續(xù)任務(wù)需要快速找到事務(wù)集合中的高效用項(xiàng)集；有的后續(xù)任務(wù)需要在一個(gè)可接受的時(shí)間范圍內(nèi)找到事務(wù)集合中可靠性更強(qiáng)的高效用項(xiàng)集。為了比較各個(gè)算法在運(yùn)行時(shí)間方面的可用性，實(shí)驗(yàn)記錄了各個(gè)算法在不同αuti參數(shù)下三種仿真事務(wù)集合中的平均運(yùn)行時(shí)間，具體的αuti參數(shù)以及實(shí)驗(yàn)結(jié)果如圖5所示。圖5中各個(gè)算法在相同αuti參數(shù)下運(yùn)行時(shí)間的長(zhǎng)短關(guān)系為：HUIM-SU＜EHNL＜FHUI＜HUSP＜PHUI-w＜PHUI-b。

基于閾值約束的算法運(yùn)行時(shí)間明顯短于基于統(tǒng)計(jì)顯著性檢驗(yàn)的算法，其原因是基于統(tǒng)計(jì)顯著性檢驗(yàn)的算法均為后處理算法，即先使用基于閾值約束的算法挖掘出待檢驗(yàn)高效用項(xiàng)集，然后再對(duì)它們進(jìn)行統(tǒng)計(jì)顯著性檢驗(yàn)，因此基于閾值約束的算法相當(dāng)于基于統(tǒng)計(jì)顯著性檢驗(yàn)的算法的第一個(gè)步驟。雖然HUIM-SU和EHNL算法運(yùn)行時(shí)間短，但其報(bào)告的大量假陽(yáng)性高效用項(xiàng)集可靠性和實(shí)用性都較低。

在基于統(tǒng)計(jì)顯著性檢驗(yàn)算法中，HUSP和FHUI算法通過(guò)待檢驗(yàn)項(xiàng)集的頻率分布直接計(jì)算生成零分布，而PHUI-w和PHUI-b算法通過(guò)構(gòu)造置換事務(wù)集合，并從中提取效用差生成零分布，從2.1和2.2節(jié)的時(shí)間復(fù)雜度分析可知，計(jì)算生成零分布的計(jì)算開(kāi)銷(xiāo)遠(yuǎn)遠(yuǎn)小于從置換事務(wù)集合中提取效用差生成零分布的計(jì)算開(kāi)銷(xiāo)，因此FHUI和HUSP算法的運(yùn)行時(shí)間明顯短于PHUI-w和PHUI-b算法。進(jìn)一步討論，雖然HUSP和FHUI算法采用了相同的檢驗(yàn)策略，但FHUI算法對(duì)二項(xiàng)式的計(jì)算進(jìn)行了優(yōu)化加速處理，促使FHUI算法運(yùn)行時(shí)間快于HUSP算法；此外，PHUI-w算法使用的事務(wù)內(nèi)置換策略不需要進(jìn)行事務(wù)之間項(xiàng)的置換，從而不涉及大量項(xiàng)的交換操作，因此其運(yùn)行時(shí)間快于PHUI-b算法。

在硬件要求方面，F(xiàn)HUI和HUSP算法不依賴(lài)計(jì)算機(jī)集群實(shí)施分布式并行化計(jì)算，從而其對(duì)硬件配置的要求相較于PHUI-w和PHUI-b算法更低。進(jìn)一步而言，當(dāng)缺少計(jì)算機(jī)集群設(shè)備支持時(shí)，PHUI-w和PHUI-b算法的運(yùn)行時(shí)間將會(huì)進(jìn)一步增加；反之，當(dāng)集群設(shè)配資源更為充足時(shí)，PHUI-w和PHUI-b算法的運(yùn)行時(shí)間將會(huì)進(jìn)一步減少。綜上，就運(yùn)行時(shí)間和硬件要求而言，F(xiàn)HUI和HUSP算法的可用性更強(qiáng)。

3.6 實(shí)驗(yàn)結(jié)果綜合分析

上述實(shí)驗(yàn)結(jié)果表明，面向具有不同類(lèi)型標(biāo)簽的事務(wù)集合時(shí)，雖然傳統(tǒng)基于閾值約束的挖掘算法運(yùn)行時(shí)間較快，但其無(wú)法識(shí)別高效用項(xiàng)集在不同類(lèi)型事務(wù)中的效用分布，從而導(dǎo)致結(jié)果中存在大量隨機(jī)產(chǎn)生的假陽(yáng)性高效用項(xiàng)集。這些假陽(yáng)性高效用項(xiàng)集嚴(yán)重誤導(dǎo)了分類(lèi)決策并且表現(xiàn)出較低的平均效用，因此傳統(tǒng)基于閾值約束的算法在此類(lèi)事務(wù)數(shù)據(jù)應(yīng)用中報(bào)告的高效用項(xiàng)集可靠性和實(shí)用性較低。

在基于統(tǒng)計(jì)顯著性檢驗(yàn)的算法中，PHUI-w和PHUI-b算法在分類(lèi)正確率、非假陽(yáng)性項(xiàng)集數(shù)量、假陽(yáng)性項(xiàng)集占比、項(xiàng)集平均效用方面優(yōu)于HUSP和FHUI算法，但在運(yùn)行時(shí)間和硬件要求方面劣于HUSP和FHUI算法；此外，F(xiàn)HUI算法在上述各度量上均略?xún)?yōu)于HUSP算法。因此，當(dāng)缺少硬件設(shè)備實(shí)施分布式并行化計(jì)算或者后續(xù)任務(wù)需要快速找到統(tǒng)計(jì)顯著高效用項(xiàng)集時(shí)，更宜采用FHUI算法挖掘高效用項(xiàng)集。當(dāng)具備硬件支持或者后續(xù)任務(wù)對(duì)高效用項(xiàng)集的數(shù)量和可靠性要求較高時(shí)，更宜采用PHUI-w和PHUI-b算法。進(jìn)一步討論，上述情景中若事務(wù)數(shù)量較大時(shí)，PHUI-w算法更具備實(shí)用性，因?yàn)榇藭r(shí)PHUI-b算法中項(xiàng)交換的計(jì)算開(kāi)銷(xiāo)非常巨大；反之，則PHUI-b算法性能更強(qiáng)。

4 結(jié)束語(yǔ)

為了剔除隨機(jī)產(chǎn)生的假陽(yáng)性高效用項(xiàng)集，提出了兩個(gè)基于不同類(lèi)型統(tǒng)計(jì)顯著性檢驗(yàn)的高效用項(xiàng)集挖掘算法——FHUI和PHUI算法。FHUI算法基于Fisher檢驗(yàn)生成零分布，PHUI算法基于置換檢驗(yàn)生成零分布。此外，PHUI算法還設(shè)計(jì)了兩種置換策略?；鶞?zhǔn)和仿真事務(wù)集合中實(shí)驗(yàn)結(jié)果表明，F(xiàn)HUI和PHUI算法成功剔除了結(jié)果中一定數(shù)量的假陽(yáng)性高效用項(xiàng)集，從而報(bào)告的統(tǒng)計(jì)顯著高效用項(xiàng)集更加可靠和實(shí)用。對(duì)比而言，F(xiàn)HUI算法運(yùn)行時(shí)間更短且硬件要求更低，PHUI算法分類(lèi)正確率更高且假陽(yáng)性高效用項(xiàng)集數(shù)量占比更低。在后續(xù)研究中，會(huì)嘗試把FHUI算法融入到待檢驗(yàn)高效用項(xiàng)集挖掘過(guò)程中，也會(huì)嘗試在不實(shí)際構(gòu)造置換事務(wù)集合的情況下直接計(jì)算PHUI算法的零分布，達(dá)到進(jìn)一步降低FHUI和PHUI算法運(yùn)行時(shí)間的目的。同時(shí)，后續(xù)研究也會(huì)針對(duì)結(jié)果中提供了相同信息的冗余高效用項(xiàng)集設(shè)計(jì)篩除算法。

參考文獻(xiàn)：

［1］Kumar S， Mohbey K K. A review on big data based parallel and distributed approaches of pattern mining ［J］. Journal of King Saud University： Computer and Information Sciences， 2022， 34（5）： 1639-1662.

［2］Tung N T， Nguyen L T， Nguyen T D D，et al. Efficient mining of cross-level high-utility itemsets in taxonomy quantitative databases ［J］. Information Sciences， 2022， 587： 41-62.

［3］張春硯， 韓萌， 孫蕊， 等. 高效用模式挖掘關(guān)鍵技術(shù)綜述 ［J］. 計(jì)算機(jī)應(yīng)用研究， 2021， 38（2）： 330-340. （Zhang Chunyan， Han Meng， Sun Rui，et al. Survey of key technologies for high utility patterns mining ［J］. Application Research of Computers， 2021， 38（2）： 330-340.）

［4］單芝慧， 韓萌， 韓強(qiáng). 動(dòng)態(tài)數(shù)據(jù)上的高效用模式挖掘綜述 ［J］. 計(jì)算機(jī)應(yīng)用， 2022， 42（1）： 94-108. （Shan Zhihui， Han Meng， Han Qiang. Survey of high utility pattern mining on dynamic data ［J］. Journal of Computer Applications， 2022， 42（1）： 94-108.）

［5］孫蕊， 韓萌， 張春硯， 等. 精簡(jiǎn)高效用模式挖掘綜述 ［J］. 計(jì)算機(jī)應(yīng)用研究， 2021， 38（4）： 975-981. （Sun Rui， Han Meng， Zhang Chunyan，et al. Survey of algorithms for concise high utility pattern mining ［J］. Application Research of Computers， 2021， 38（4）： 975-981.）

［6］Almoqbily R S， Rauf A， Quradaa F H. A survey of correlated high utility pattern mining ［J］. IEEE Access，2021，9： 42786-42800.

［7］Luna J M， Kiran R U， Fournier V P，et al. Efficient mining of top-k high utility itemsets through genetic algorithms ［J］. Information Sciences， 2023， 624： 529-553.

［8］Kumar R， Singh K. A survey on soft computing-based high-utility itemsets mining ［J］. Soft Computing， 2022， 26（13）： 6347-6392.

［9］Gan Wensheng， Lin Chunwei， Fournier V P，et al. A survey of utility-oriented pattern mining ［J］. IEEE Trans on Knowledge and Data Engineering， 2019， 33（4）： 1306-1327.

［10］Wu Mingtai， Lin Chunwei， Tamrakar A. High-utility itemset mining with effective pruning strategies ［J］. ACM Trans on Knowledge Discovery from Data， 2019， 13（6）： 1-22.

［11］Krishna G J， Ravi V. High utility itemset mining using binary diffe-rential evolution： an application to customer segmentation ［J］. Expert Systems with Applications， 2021， 181： 115122.

［12］Kumar R， Singh K. High utility itemsets mining from transactional databases： a survey ［J］. Applied Intelligence， 2023， 53（22）： 27655-27703.

［13］Cheng Zhaihe， Fang Wei， Shen Wei，et al. An efficient utility-list based high-utility itemset mining algorithm ［J］. Applied Intelligence， 2023， 53（6）： 6992-7006.

［14］Tung N T， Nguyen L T T， Nguyen T D，et al. An efficient method for mining multi-level high utility itemsets ［J］. Applied Intelligence， 2022， 52（5）： 5475-5496.

［15］Tonon A， Vandin F. Permutation strategies for mining significant sequential patterns ［C］// Proc of the 21st IEEE International Confe-rence on Data Mining. Piscataway， NJ： IEEE Press， 2019： 1330-1335.

［16］Trasierras A M， Luna J M， Ventura S. A contrast set mining based approach for cancer subtype analysis ［J］. Artificial Intelligence in Medicine， 2023， 143： 102590.

［17］Kong Jie， Han Jiaxin， Ding Junping，et al. Analysis of students’learning and psychological features by contrast frequent patterns mi-ning on academic performance ［J］. Neural Computing and Applications， 2020， 32（1）： 205-211.

［18］Loyola-Gonzlez O， Medina-Pérez M A， Choo K K R. A review of supervised classification based on contrast patterns： applications， trends， and challenges ［J］. Journal of Grid Computing， 2020， 18： 797-845.

［19］Jenkins S， Walzer-Goldfeld S， Riondato M. SPEck： mining statistically significant sequential patterns efficiently with exact sampling ［J］. Data Mining and Knowledge Discovery， 2022， 36（4）： 1575-1599.

［20］He Zengyou， Chen Wenfang， Wei Xiaoqi，et al. Mining statistically significant communities from weighted networks ［J］. IEEE Trans on Knowledge and Data Engineering， 2022， 35（6）： 6073-6084.

［21］Pellegrina L， Riondato M， Vandin F. SPuManTE： significant pattern mining with unconditional testing ［C］// Proc of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM press， 2019： 1528-1538.

［22］Tang Huijun， Qian Jiangbo， Liu Yangguang，et al. Mining statistically significant patterns with high utility ［J］. International Journal of Computational Intelligence Systems， 2022， 15（1）： 88-107.

［23］Duong Q H， Fournier-Viger P， Ramampiaro H，et al. Efficient high utility itemset mining using buffered utility-lists ［J］. Applied Intelligence， 2018， 48（3）： 1859-1877.

［24］Zhao Guolong， Yang Huiyu， Yang Junxia，et al. A data-based adjustment for fisher exact test ［J］. European Journal of Statistics， 2021， 1： 74-107.

［25］Hamalainen W. New upper bounds for tight and fast approximation of Fisher’s exact test in dependency rule mining ［J］. Computational Statistics and Data Analysis， 2016， 93（2）： 469-482.

［26］Singh K， Kumar A， Singh S S，et al. EHNL： an efficient algorithm for mining high utility itemsets with negative utility value and length constraints ［J］. Information Sciences， 2019， 484： 44-70.

［27］Fournier-Viger P， Gomariz A， Gueniche T，et al. SPMF： a Java open-source pattern mining library ［J］. Journal of Machine Lear-ning Research， 2014， 15（1）： 3389-3393.