基于統計顯著性檢驗的高效用項集挖掘算法

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

關鍵詞：數據挖掘；高效用項集挖掘；統計顯著性檢驗；Fisher檢驗；置換檢驗

中圖分類號：TP391 文獻標志碼：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 引言

發現數據中有趣和實用的項集是數據挖掘中一個重要的研究領域。在該領域中，頻繁項集挖掘是研究最為全面的任務［1］。但實際應用中發現報告的大部分頻繁項集都不具備有趣性和實用性。例如，在超市購買記錄中，雖然{牛奶，面包}項集通常出現的頻率很高，但其不具備有趣性和實用性，因為該項集提供的信息是一種普遍的消費行為。導致上述現象的原因是頻繁項集挖掘任務設定每個項具有相同的權重。

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

在具有類型標簽的事務中，項集發現任務的主要研究方向是找到能夠揭示不同類型事務差別特征的項集［15］。相關挖掘算法已被廣泛應用于不同領域的問題研究中，例如在醫學中探索不同癌癥之間的癥狀差別［16］，在教育學中發現不同學生群體的學習和心理狀態差別［17］，在市場營銷學中揭示不同顧客群體的消費行為差別［18］。當傳統高效用項集挖掘算法應用于具有類型標簽的事務時，雖然能夠報告大量滿足效用閾值約束的高效用項集，但其中大部分高效用項集表達的信息并不能正確體現事務的特征差別，即存在大量隨機產生的假陽性高效用項集。基于假陽性高效用項集提供的虛假特征作出的決策大概率會導致失敗的結果，因此找到結果中的假陽性高效用項集并將其剔除是至關重要的。

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

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

1 基本概念

1.1 高效用項集

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

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

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

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

項集X在事務dv中的效用由u（X， dv）表示，定義為

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

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

項集X在事務集合D中的效用由u（X， D）表示，定義為

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

例如，同樣假設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}為高效用項集。高效用項集挖掘任務的目標是找到事務集合D中所有效用不低于αuti的項集。

1.2 統計顯著性檢驗

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

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

2 挖掘算法

2.1 FHUI算法

FHUI算法的核心思路是先使用待檢驗高效用項集在不同類型事務中的頻率分布刻畫效用分布，再使用Fisher檢驗將該頻率分布作為項集的零分布并從中計算出p值。具體而言，設類型標簽集合C={c1，c2}，根據C可以將D劃分成D=D1∪D2，其中D1中事務的類型標簽均為c1，D2中事務的類型標簽均為c2。待檢驗高效用項集X在D中的頻率列聯表如表3所示。

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

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

根據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）中包含了大量的二項式計算，導致計算開銷較高。為了快速計算出待檢驗高效用項集的p值，參考了文獻［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達到控制假陽性高效用項集數量的目的。BH方法計算公式如下：

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

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

算法1 FHUI 算法

輸入：事務集合D；效用閾值αuti；統計顯著水平αsig。

輸出：統計顯著高效用項集集合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（）方法依據項集長度分組（步驟a）b）），分組檢驗的目的是為了避免項集長度的影響。利用fac_buffer（）方法構建階乘緩存加速后續二項式的計算（步驟c））。

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

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

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

2.2 PHUI算法

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

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

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

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

事務間置換策略通過置換事務之間的類型標簽、項及其內部效用構造置換事務集合。詳細步驟如下：

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

b）生成一個事務編號的隨機置換序列，根據該序列首先置換每條事務的類型標簽，然后置換每條事務在G中標記位置對應的項及其內部效用。置換后事務若存在相同的項，則進行內部效用合并。

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

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

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

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

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

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

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

算法2 PHUI 算法

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

輸出：統計顯著高效用項集集合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描述了基于事務內置換策略的per_trans（）方法。針對每條事務d，先使用ran_items（）方法生成一個項的隨機置換序列M，再使用in_permute（）方法根據M置換每個項的內部效用便得到了一條置換事務d。最后，返回包含所有d的置換事務集合D。

算法3 基于事務內置換策略的per_trans（）方法

輸入：原始事務集合D。

輸出：置換事務集合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描述了基于事務間置換策略的per_trans（）方法。首先，使用ran_number（）生成一個［1， min_trans（D）］之間的隨機整數z，并使用ran_positions（）為每條事務標記z個項的隨機位置存入G中；接著，使用ran_tids（）方法生成一個事務編號的隨機置換序列F；然后，針對每條事務d，先使用lab_ permute（）方法根據F置換類型標簽得到d1，再根據F和G置換d1中標記位置對應的項及其內部效用得到一條置換事務d2；最后，返回包含所有d2的置換事務集合D。

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

輸入：原始事務集合D。

輸出：置換事務集合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算法的時間復雜度主要由四部分構成：待檢驗高效用項集挖掘、置換檢驗零分布生成、p值計算以及假陽性結果剔除。其中，待檢驗高效用項集挖掘和假陽性結果剔除這兩部分與FHUI算法采用了相同的步驟，因此其時間復雜度也相同，分別為O（e2log e）和O（|R|log|R|+|R|）。每個項集的p值能夠通過置換檢驗零分布直接計算得出，因此所有待檢驗高效用項集p值計算的時間復雜度是O（|R|）。

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

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

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

3 實驗結果與分析

3.1 實驗對比算法

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

3.2 實驗基本設置

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

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

3.3 實驗數據信息

3.3.1 基準事務集合信息

實驗采用了高效用項集挖掘任務中廣泛使用的4個基準事務集合：chess［27］、mushroom［27］、connect［27］、protein［8］，詳細信息如表4所示。其中，connect集合含有3種類型標簽，為了便于呈現實驗結果，將“loss”和“draw”對應的事務進行了合并。

3.3.2 仿真事務集合信息

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

a）假設Ifal={i1，i2，…，i60}表示構成隨機項集的字母表集合；Itru={i61，i62，…，i74}表示構成真實植入項集的字母表集合；C= {c1，c2}表示類型標簽集合。

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

c）將Ifal中的項分為20組，每組包含3個項。為了構造一條事務dsyn，從每組中隨機抽取一個項ifal，并為每個抽取的項分配一個［1，10］的整數作為內部效用，即iu（ifal， dsyn） ∈［1，10］。

d）重復執行上一步驟直至構造4 000條事務。將c1分配給前2 000條事務構成D1，c2分配給后2 000條事務構成D2，計算4 000條事務的總效用utotal。

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

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

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

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

實驗結果中，如果報告的一個高效用項集只包含Ifal中的項，那么該項集被認定為假陽性高效用項集，因為這樣的項集沒有包含任何真實信息。此外，為了避免偶然性，分別使用內部效用主導、外部效用主導和頻率分布主導的植入方式獨立構造10個仿真事務集合。

3.4 基準事務集合實驗

3.4.1 報告的高效用項集數量

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

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

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

YRuH10HvBUDCHOLRA2IQZOLxDBMqfFsCwnm4sSn428I=3.4.2 分類任務正確率

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

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

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

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

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

3.5 仿真事務集合實驗

3.5.1 報告的高效用項集情況

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

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

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

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

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

3.5.2 平均效用

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

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

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

3.5.3 運行時間

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

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

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

在硬件要求方面，FHUI和HUSP算法不依賴計算機集群實施分布式并行化計算，從而其對硬件配置的要求相較于PHUI-w和PHUI-b算法更低。進一步而言，當缺少計算機集群設備支持時，PHUI-w和PHUI-b算法的運行時間將會進一步增加；反之，當集群設配資源更為充足時，PHUI-w和PHUI-b算法的運行時間將會進一步減少。綜上，就運行時間和硬件要求而言，FHUI和HUSP算法的可用性更強。

3.6 實驗結果綜合分析

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

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

4 結束語

為了剔除隨機產生的假陽性高效用項集，提出了兩個基于不同類型統計顯著性檢驗的高效用項集挖掘算法——FHUI和PHUI算法。FHUI算法基于Fisher檢驗生成零分布，PHUI算法基于置換檢驗生成零分布。此外，PHUI算法還設計了兩種置換策略。基準和仿真事務集合中實驗結果表明，FHUI和PHUI算法成功剔除了結果中一定數量的假陽性高效用項集，從而報告的統計顯著高效用項集更加可靠和實用。對比而言，FHUI算法運行時間更短且硬件要求更低，PHUI算法分類正確率更高且假陽性高效用項集數量占比更低。在后續研究中，會嘗試把FHUI算法融入到待檢驗高效用項集挖掘過程中，也會嘗試在不實際構造置換事務集合的情況下直接計算PHUI算法的零分布，達到進一步降低FHUI和PHUI算法運行時間的目的。同時，后續研究也會針對結果中提供了相同信息的冗余高效用項集設計篩除算法。

參考文獻：

［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］張春硯， 韓萌， 孫蕊， 等. 高效用模式挖掘關鍵技術綜述 ［J］. 計算機應用研究， 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］單芝慧， 韓萌， 韓強. 動態數據上的高效用模式挖掘綜述 ［J］. 計算機應用， 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］. 計算機應用研究， 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.