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

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

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

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

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

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

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

1 基本概念

1.1 高效用項集

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

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

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

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

項集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。

項集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被稱作高效用項集。例如，如果 αuti=25，那么表1中{i2， i3}為高效用項集。高效用項集挖掘任務(wù)的目標(biāo)是找到事務(wù)集合D中所有效用不低于αuti的項集。

1.2 統(tǒng)計顯著性檢驗

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

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

2 挖掘算法

2.1 FHUI算法

FHUI算法的核心思路是先使用待檢驗高效用項集在不同類型事務(wù)中的頻率分布刻畫效用分布，再使用Fisher檢驗將該頻率分布作為項集的零分布并從中計算出p值。具體而言，設(shè)類型標(biāo)簽集合C={c1，c2}，根據(jù)C可以將D劃分成D=D1∪D2，其中D1中事務(wù)的類型標(biāo)簽均為c1，D2中事務(wù)的類型標(biāo)簽均為c2。待檢驗高效用項集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檢驗［24］，可以將式（4）作為待檢驗高效用項集的零分布并從中計算出項集的p值，其中p值中的極端項集被定義為X在D1中頻率分布大于等于sup（X， D1）的情況。p值計算公式為

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

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

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）

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

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

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

算法1 FHUI 算法

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

輸出：統(tǒ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算法流程的說明如下：

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

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

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

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

2.2 PHUI算法

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

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

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

事務(wù)內(nèi)置換策略通過隨機(jī)置換每條事務(wù)的內(nèi)部效用構(gòu)造置換事務(wù)集合。具體而言，針對每一條事務(wù)，首先生成項的隨機(jī)置換序列，然后根據(jù)該序列置換項的內(nèi)部效用。例如，假設(shè)原始事務(wù)集合如圖1（a）所示，對于d1，生成的項的隨機(jī)置換序列是d1：{i4，i7，i5，i1，i3}。根據(jù)該序列，將i1的內(nèi)部效用置換給i4，將i3的內(nèi)部效用置換給i7，依此類推，直到完成所有內(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ù)間置換策略通過置換事務(wù)之間的類型標(biāo)簽、項及其內(nèi)部效用構(gòu)造置換事務(wù)集合。詳細(xì)步驟如下：

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

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

舉個例子，給定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ù)編號隨機(jī)置換序列為{d4，d1，d5，d2，d3}。根據(jù)該序列，先將d1的類型標(biāo)簽置換給d4，再將d1中{2，5}位置的項及其內(nèi)部效用置換到d4的{1，3}位置；先將d2的類型標(biāo)簽置換給d1，再將d2中{1，2}位置的項及其內(nèi)部效用置換給d1的{2，5}位置，置換后存在相同的項i4，故將其內(nèi)部效用合并得到（i4，5）；如此迭代，直至完成隨機(jī)置換序列所有的置換，最終構(gòu)造的置換事務(wù)集合D如圖1（c）所示。

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

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

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

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

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

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

算法2 PHUI 算法

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

輸出：統(tǒ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（）方法。針對每條事務(wù)d，先使用ran_items（）方法生成一個項的隨機(jī)置換序列M，再使用in_permute（）方法根據(jù)M置換每個項的內(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（）生成一個［1， min_trans（D）］之間的隨機(jī)整數(shù)z，并使用ran_positions（）為每條事務(wù)標(biāo)記z個項的隨機(jī)位置存入G中；接著，使用ran_tids（）方法生成一個事務(wù)編號的隨機(jī)置換序列F；然后，針對每條事務(wù)d，先使用lab_ permute（）方法根據(jù)F置換類型標(biāo)簽得到d1，再根據(jù)F和G置換d1中標(biāo)記位置對應(yī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算法的時間復(fù)雜度主要由四部分構(gòu)成：待檢驗高效用項集挖掘、置換檢驗零分布生成、p值計算以及假陽性結(jié)果剔除。其中，待檢驗高效用項集挖掘和假陽性結(jié)果剔除這兩部分與FHUI算法采用了相同的步驟，因此其時間復(fù)雜度也相同，分別為O（e2log e）和O（|R|log|R|+|R|）。每個項集的p值能夠通過置換檢驗零分布直接計算得出，因此所有待檢驗高效用項集p值計算的時間復(fù)雜度是O（|R|）。

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

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

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

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

3.1 實(shí)驗對比算法

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

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

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

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

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

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

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

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

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

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

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

c）將Ifal中的項分為20組，每組包含3個項。為了構(gòu)造一條事務(wù)dsyn，從每組中隨機(jī)抽取一個項ifal，并為每個抽取的項分配一個［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，計算4 000條事務(wù)的總效用utotal。

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

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

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

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

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

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

3.4.1 報告的高效用項集數(shù)量

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

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

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

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

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

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

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

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

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

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

3.5.1 報告的高效用項集情況

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

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

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

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

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

3.5.2 平均效用

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

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

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

3.5.3 運(yùn)行時間

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

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻(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ī)應(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). 動態(tài)數(shù)據(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］孫蕊， 韓萌， 張春硯， 等. 精簡高效用模式挖掘綜述 ［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.