面向不確定數(shù)據(jù)模式指標的通用界值估算方法

王 菊，劉付顯，靳春杰

(1.空軍工程大學 防空反導(dǎo)學院，西安 710051； 2. 93527部隊，河北 張家口 075000)(*通信作者電子郵箱yonglingjuke@126.com)

0 引言

作為頻繁模式挖掘的拓展，基于約束的模式挖掘近年來引起了越來越多的關(guān)注[1-2]。當前關(guān)于該問題的研究主要集中在如何將不同的模式指標融入到算法的執(zhí)行過程中以減小搜索空間，尤其是針對難約束指標[3-5]。其中一個通用處理辦法就是估計給定項集X的所有超集關(guān)于模式指標的一個上/下界。如果這個界值小于/大于一個給定的最小/最大閾值，那么X的所有超集就要從全集中被剪除[6]，因此，模式指標的界值估算是約束模式挖掘中的一個核心問題。

當前雖然在實際應(yīng)用的驅(qū)動下，一些模式指標及其上界的估算方法已經(jīng)被提出，如模式效用[7-8]、模式占有度[9]和有權(quán)置信度[10]等，但是這些研究的局限性在于它們不具有普遍性，即每當一個新的難約束指標被提出時，都需要花費較大代價去找到相應(yīng)有效的上/下界，因此，文獻[11]提出了一種基于帶有權(quán)值的確定型事務(wù)數(shù)據(jù)庫的通用界值估算方法，但是，該文獻中所提出的方法沒有指明在帶有權(quán)值的不確定型事務(wù)數(shù)據(jù)庫上如何進行運算。

為此，針對在帶有權(quán)值的不確定型事務(wù)數(shù)據(jù)庫上模式指標的界值估算問題，本文提出了一種通用的估算方法，在傳統(tǒng)界值估算方法的基礎(chǔ)上，增加了處理不確定性的功能。其基本思想是在給定項集滿足最小支持度閾值的情況下，通過采用不考慮項標記而只考慮支持數(shù)據(jù)庫中出現(xiàn)項的權(quán)值和存在概率的策略，使得模式指標值在相應(yīng)的事務(wù)中達到最大或者最小。

1 問題闡述

1.1 數(shù)據(jù)庫模型

當前關(guān)于模式指標的界值估算方法大多基于確定型數(shù)據(jù)庫，少有關(guān)于該問題在不確定型數(shù)據(jù)庫上的探討。針對這一不足，本文將側(cè)重于研究帶有權(quán)值的不確定型事務(wù)數(shù)據(jù)庫D={T1,T2,…,Tq,…,Tm}。其中，m表示該數(shù)據(jù)庫中事務(wù)的數(shù)量；當D中包含的所有項的數(shù)量為L時，可以用有限集合I={i1,i2,…,ip,…,iL}表示該數(shù)據(jù)庫中的所有項，此時該數(shù)據(jù)庫中的任意一個事務(wù)Tq代表I中有限數(shù)目的項，被表示為Tq={i1,i2,…,il}(1≤l≤L)；任意一個項ip都對應(yīng)于一個權(quán)值u(ip,Tq)和一個存在概率p(ip,Tq)，它們分別表示ip在事務(wù)Tq中的權(quán)值和ip存在于事務(wù)Tq中的概率。

不難發(fā)現(xiàn)，這種帶有權(quán)值的不確定型事務(wù)數(shù)據(jù)庫可以作為一般常用數(shù)據(jù)庫的通用形式。例如當所有權(quán)值為1時，該數(shù)據(jù)庫可以退化為一個不確定型事務(wù)數(shù)據(jù)庫；當所有存在概率值都為1時，該數(shù)據(jù)庫可以退化為一個帶有權(quán)值的確定型事務(wù)數(shù)據(jù)庫。表1是一個帶有權(quán)值的不確定型事務(wù)數(shù)據(jù)庫的示例。

表1 帶有權(quán)值的不確定型事務(wù)數(shù)據(jù)庫示例

表1中的不確定型事物數(shù)據(jù)庫可以被表示為D={T1,T2,…,T8}，有限集合I={A,B,C,D,E,F,G}，各個事務(wù)所包含的項以及項中對應(yīng)的權(quán)值和概率信息在表1中都有明確的表示。在實際應(yīng)用中，表1中的(A,3,0.81)可以解釋為購物者T1會以概率0.81購買項A，它帶給零售商的利潤值(權(quán)值在該應(yīng)用中的實際含義)為3。在該應(yīng)用中，那些購物者會以高概率購買且能帶來高利潤值的項或項集是零售商們所歡迎的商品或商品集。

1.2 模式指標定義

為發(fā)現(xiàn)在帶有權(quán)值的不確定型事務(wù)數(shù)據(jù)庫中以高概率出現(xiàn)且具有高權(quán)值的項集，本文定義了模式指標PI來綜合評估項集的權(quán)值和存在概率。其主要需要三個輸入：項集的支持數(shù)據(jù)庫以及每個項在其出現(xiàn)事務(wù)上的權(quán)值與存在概率。模式指標PI的數(shù)學形式可以定義為：

(1)

其中：X表示數(shù)據(jù)庫D中的任意一個項集；DX表示項集X的支持數(shù)據(jù)庫；U表示DX中項到權(quán)值的映射；P表示DX中項到存在概率的映射。

根據(jù)模式指標PI對項集進行綜合評估時，常采用“當模式指標PI滿足一定條件時，其相應(yīng)的項集為高概率出現(xiàn)且具有高權(quán)值的項集；否則就不是該類項集”這樣的約束形式，因此本文將模式指標PI轉(zhuǎn)換為約束：

(2)

這個約束可以進一步簡化為：

PI(X,D,U,P)≥或≤β

(3)

其中：β∈R+。

通常不同的指標約束具有不同的性質(zhì)，常用的可以用于縮減搜索空間的性質(zhì)有：單調(diào)性、簡潔性、可轉(zhuǎn)換單調(diào)性、松散反單調(diào)性、靈活性、有界性等，但是在實際應(yīng)用過程中，有很多約束不滿足所有這些可縮減搜索空間的性質(zhì)，這類約束被統(tǒng)稱為難約束。為降低計算復(fù)雜度，減小搜索空間，對難約束的一個通用處理辦法就是估計給定項集X的所有父項集關(guān)于給定模式指標PI的一個上/下界。如果這個界值小于/大于一個給定的最小/最大閾值，那么X的所有超集就要從全集中被剪除。當前針對某個或某幾個特定的難約束，相關(guān)學者分別提出了其相應(yīng)的上/下界，但是這些研究的局限性在于每當一種模式指標被提出時，都要花費較大的代價去計算其上/下界。

因此，本文通過分析帶有權(quán)值的不確定型事務(wù)數(shù)據(jù)庫的特點和之前關(guān)于特定難約束指標界估計方法的相同點，提出了一種面向不確定數(shù)據(jù)模式指標的通用界值估算方法。該方法可以在帶有權(quán)值的不確定型事務(wù)數(shù)據(jù)庫上對新的難約束指標進行高效的界值估算，其研究思路和通用估算方法將在下文中展開詳細論述。

2 研究思路

給定項集X，模式指標PI的界值估算問題就是研究如何能夠快速計算出所有X的超集關(guān)于PI的一個上/下界。一種非常直接但耗時的解決方案就是分別計算項集X所有超集的模式指標值，然后選擇其中最大/小值作為X的超集關(guān)于PI的上/下界，這種方法的運算次數(shù)正比于2|I|-|X|，呈現(xiàn)出了指數(shù)增長。為提高上述界值估算方案的效率，本文通過不考慮項標記而只考慮支持數(shù)據(jù)庫中出現(xiàn)項的權(quán)值和存在概率，設(shè)計了如2.2節(jié)中所示的基本框架。此外，由于θ=‘≤’的情況與θ=‘≥’的情況在研究方法與內(nèi)容上類似，下文在不加以說明的位置都只估算了模式指標的上界，即θ=‘≥’的情況。

2.1 符號說明

由于文中涉及到的符號較多，本節(jié)就這些符號進行說明，如表2所示。

表2 符號說明

例如在表1的示例中，LT=[5,3,2,3,2,4,3,4]。當X={AC}時，DX={T1,T4,T6}，XS=[1,4,6]，LS=[3,1,2]，LSp=[3,2,1]，|X|=2，將期望支持度sX按照文獻[12]中的定義進行計算后得2.204 8，此時相應(yīng)的Pu和Su矩陣在采用不考慮項標記而只考慮支持數(shù)據(jù)庫中出現(xiàn)項的權(quán)值和存在概率的策略后，如圖1所示。

圖1 當X={AC}時表1數(shù)據(jù)庫的變形

從圖1中可知，當X={AC}時，Pu(4,1)=18，Su(6,2)=4，圖1中沒有顯示的矩陣值都為0，例如Pu(2,2)=0，Su(4,2)=0。

2.2 基本框架

針對帶有權(quán)值的不確定型事務(wù)數(shù)據(jù)庫D，給定項集X、模式指標PI以及最小期望支持度閾值σ，上述界值估算問題的基本研究框架如下。

輸入：不確定型事務(wù)數(shù)據(jù)庫D，項集X、模式指標PI以及最小期望支持度閾值σ。

輸出：X的超集關(guān)于PI的一個上界。

計算項集X的期望支持度sX

IfsX<σ

Return 0;

Else

對于一組給定的α和β，提出一個函數(shù)F(α,β,sX,Pu,Su)滿足條件：PI(X′,DX′,U,P)≤F(α,β,sX,Pu,Su);

Forα=1:|DX|

Forβ=0:LSp(1)

A(α,β)=F(α,β,sX,Pu,Su)；

End

End

Return max(A)

End

其中LSp(1)表示DX中相對于X的最大擴展長度。采用表2中的基本框架，只要計算|DX|×(LSp(1)+1)次函數(shù)F的值，呈現(xiàn)出了線性增長的方式。相比分別計算項集X所有超集的模式指標值所帶來的指數(shù)級增長，縮減了計算空間。例如在表1的示例中，當X={AC}時，采用直接計算的方式，計算次數(shù)為27-2=32次，而采用表2中的方法只要計算3×(3+1)=12次函數(shù)F的值即可。

3 界值的快速估算方法

在上述基本框架中，為快速估算出X的超集關(guān)于PI的上界值，本章主要圍繞兩個問題展開研究：一是當給定一組α和β時，怎樣高效地計算出函數(shù)F的值；二是怎樣遍歷α,β的取值，才能盡快得到上界值。

3.1 函數(shù)F的計算方法

針對項集X，對于一組α和β，雖然采用遍歷矩陣Pu和Su的方法可以計算出函數(shù)F的值，但是需要花費較長的計算時間，進而降低了上界估算方法的效率。本節(jié)提供了一種快速計算F(α,β,sX,Pu,Su)的方法，其具體流程如下。

步驟1 當LS(i)<β(1≤i≤|LS|)時，從向量XS中剔除相應(yīng)的XS(i)得到XSβ，從而確定可能包含X′的候選事務(wù)集C(由于X′相對于X的擴展長度為β，因此當X在其支持事務(wù)上的后綴長度小于β時，該事務(wù)中一定不包含X′)。

步驟2 根據(jù)候選事務(wù)集C和XSβ中存儲的事務(wù)編號，將Su(XSβ(j),max(LS))(1≤j≤|XSβ|)中的元素按照由大到小的順序需進行排序得到Sup(XSβ(j),max(LS))，進而對Sup(XSβ(j),max(LS))中前β個元素的模式指標值進行求和得到sumβ。

步驟3 對Pu(XSβ(j),max(LS))中前|X|個元素的模式指標值進行求和得到sum|X|，進而可以得到局部上界值sumβ+sum|X|。

步驟4 從步驟3中得到的所有局部上界值中選出前α個最大值，對它們進行求和后得到函數(shù)F的值。

3.2 α和β之間的關(guān)系

在3.1節(jié)所示的F函數(shù)計算方法中可以發(fā)現(xiàn)：X′相對于X的擴展長度β可以影響到可能包含X′的事務(wù)個數(shù)α。這意味著α和β在所提的計算方法中不是兩個相互獨立的參數(shù)，它們之間存在一定的關(guān)系。本節(jié)就它們之間的相互關(guān)系進行研究，主要分為兩個部分：一是當α值固定時，研究β的取值范圍；二是當β固定時，研究α的取值范圍。

1)當α值固定時。

(4)

2)當β值固定時。

(5)

采用表2中的搜索方法，至少要計算|DX|×(LSp(1)+1)次函數(shù)F的值，但是基于α和β之間的關(guān)系后，運算次數(shù)變?yōu)?LSp(1)+1)+(LSp(2)+1)+…+(LSp(|DX|)+1)。由于LSp(1)≤LSp(2)≤…≤LSp(|DX|)，因此就有(LSp(1)+1)+(LSp(2)+1)+…+(LSp(|DX|)+1)≤(LSp(|DX|)+1)+(LSp(|DX|)+1)+…+(LSp(|DX|)+1)=|DX|×(LSp(1)+1)。也就是說基于α和β之間的關(guān)系，可以進一步減小搜索空間，降低對F函數(shù)的計算次數(shù)，進而可以提高模式指標PI上界值的估算效率。例如在表1的示例中，當X={AC}時，采用表2中的計算方法要計算3×(3+1)=12次函數(shù)F的值，而采用上述α和β之間的關(guān)系后，計算次數(shù)可以減為(3+1)+(2+1)+(1+1)=9。

除此之外，根據(jù)部分模式指標所設(shè)計的函數(shù)具有單調(diào)性、有界性等性質(zhì)，基于這些性質(zhì)可以進一步地縮減搜索空間，提高計算效率，但是由于本文的主要研究內(nèi)容是通用模式指標的界值估算問題，關(guān)于這些具有特定性質(zhì)的F函數(shù)如何進一步地減小搜索空間不在本文的研究內(nèi)容之中，因此文中沒有對這些性質(zhì)的應(yīng)用問題作詳細論述。

4 舉例說明

在基于約束的模式挖掘問題中，一些常用的難約束模式指標有模式效用、模式占有度、塊模式指標以及有權(quán)置信度等。本章以模式效用和模式占有度為例，說明文中所提出的基本框架及方法可以應(yīng)用于這些模式指標的界值估計。

模式效用是一種典型的難約束，其在帶有權(quán)值的不確定型事務(wù)數(shù)據(jù)庫上的計算方法如定義1所示，本章將給出其F函數(shù)的具體形式及相應(yīng)的上界。

定義1 項集的效用值。針對帶有權(quán)值的不確定型事務(wù)數(shù)據(jù)庫D，項集X的效用值被定義為項集X在其支持事務(wù)上的效用值總和，被表示為：

(6)

例如項集{AC}，其最小期望支持度s{AC}=2.204 8，因此當σ=2時，效用值μ(AC)=3+5+18+11+25+17=79；當σ=3時，效用值μ(AC)=0。

按照2.2節(jié)中的基本框架和第3章中的估算方法，針對項集X和一組給定的α和β，可以將函數(shù)F用數(shù)學表達式(8)表示且該函數(shù)滿足性質(zhì)1。

F(α,β,sX,Pu,Su)=

(7)

性質(zhì)1 當X′的擴展長度為β，支持事務(wù)個數(shù)為α時，該項集在帶有權(quán)值的不確定型事務(wù)數(shù)據(jù)庫上的模式效用滿足：

μ(X′)≤F(α,β,sX,Pu,Su)

(8)

證明 當sX′<σ時，μ(X′)=F(α,β,sX,Pu,Su)=0，滿足式(8)。

當sX′≥σ時，由于

因此不等式

成立。

根據(jù)性質(zhì)1，可以很容易得到項集X所有父項集關(guān)于模式效用的一個上界：

(9)

例如表1中的示例，當最小期望支持度閾值σ=3時，項集{AC}的模式效用上界為0；當最小期望支持度閾值σ=2時，項集{AC}的模式效用上界為：

根據(jù)式(8)可得：

F(3,0,sX,Pu,Su)=8+29+42=79

F(3,1,sX,Pu,Su)=24+38+66=128

F(2,2,sX,Pu,Su)=36+70=106

F(1,3,sX,Pu,Su)=44

模式占有度也是一種典型的難約束，其計算方法如定義2所示。

定義2 項集的占有度。針對帶有權(quán)值的不確定型事務(wù)數(shù)據(jù)庫D，項集X的占有度被定義為：

(10)

同理，根據(jù)2.2節(jié)中的基本框架和第3章中的估算方法，可以得到模式占有度的F函數(shù)以及上界的表達式分別如式(11)和(12)所示：

F(α,β,sX,Pu,Su)=

(11)

(12)

5 實驗結(jié)果與分析

模式效用是一種常用的模式指標，本文實驗中以模式效用為例，用于驗證所提通用模式指標上界估算方法在帶有權(quán)值的不確定型事務(wù)數(shù)據(jù)庫上的有效性。由于在帶有權(quán)值的不確定型事務(wù)數(shù)據(jù)庫上關(guān)于高效用模式挖掘問題的研究極少，目前只有UHUI-Apriori(High Utility Itemsets mining from Uncertain datasets based on Apriori)[13]、PHUI-UP(Potential High-Utility Itemsets UPper-bound-based mining)和PHUI-List(Potential High-Utility Itemsets PU-list-based mining)[14]算法可用于解決該問題，且都需要估算模式效用在不確定型事務(wù)數(shù)據(jù)庫上的界值，因此這些算法的實驗過程和結(jié)果都很相似。為了驗證所提通用上界估算方法的有效性，以PHUI-UP算法為牽引，分別采用項集的事務(wù)加權(quán)效用值(Transaction Weighted Utilization, TWU)、本文方法所得的上界估算值和實際上界值來減少該算法在帶有權(quán)值的不確定型事務(wù)數(shù)據(jù)庫上挖掘高效用模式時所產(chǎn)生的候選項集。實驗中，本文對比了PHUI-UP算法在上述3種界值計算方法下的運行時間和內(nèi)存占用情況，實驗數(shù)據(jù)集和實驗結(jié)果下文分別進行介紹。

所有的算法都用Matlab實現(xiàn)，運行在一臺裝有32位Windows 7操作系統(tǒng)的臺式計算機上。該計算機帶有兩個因特爾酷睿i5- 4590處理器和4 GB的RAM。

5.1 實驗數(shù)據(jù)集

本節(jié)實驗運行在人工數(shù)據(jù)集T10I4D100K和實際數(shù)據(jù)集mushroom、connect和accidents上。它們是關(guān)于高效用模式挖掘問題的常用數(shù)據(jù)集，其參數(shù)和特點分別如表3～4所示。

表3 所使用數(shù)據(jù)集的參數(shù)

表4 所使用數(shù)據(jù)集的特點

為滿足PHUI-UP算法對數(shù)據(jù)集的要求，根據(jù)文獻[15]所提出的仿真模型生成分別在區(qū)間[1,1 000]和[1,5]中的服從對數(shù)正態(tài)分布的隨機數(shù)來模擬這些數(shù)據(jù)集中外部效用值和內(nèi)部效用值。此外，生成(0,1)區(qū)間的均勻隨機數(shù)來模擬這些數(shù)據(jù)集中的概率信息。本文方法中所采用的權(quán)值對應(yīng)于PHUI-UP算法中的效用值，即數(shù)據(jù)集中每個項的內(nèi)部效用與其相應(yīng)外部效用的乘積。

5.2 結(jié)果分析

當給定最小期望支持度閾值σ=2時，在本節(jié)的實驗中比較了PHUI-UP算法在分別采用上述3種上界值后的運行時間和內(nèi)存使用情況，分別如圖2～3所示。

從圖2～3中可以看出，當PHUI-UP算法采用TWU時，該算法的運行時間和所占用內(nèi)存都是最少的，尤其是在稀疏數(shù)據(jù)集T10I4D100K，這是因為TWU是通過事務(wù)的權(quán)值來松散地估算項集的權(quán)值，計算復(fù)雜度較小。當本文中的上界值估算方法和PHUI-UP算法相結(jié)合后，運行時間和占用內(nèi)存相對于TWU都略大，造成這個結(jié)果的原因主要有兩個：一是本文所提出的界值估算方法是一種通用的方法，不只是適用于高效用模式的上界估計，因此相比TWU有較大的計算復(fù)雜度；二是由于本文所提出的界值估算方法用被估算項集的權(quán)值及其后綴中項的權(quán)值來估算該項集權(quán)值的上界，因此在計算過程中需要重復(fù)的讀取數(shù)據(jù)集中的數(shù)據(jù)。此外，從圖2～3中還可以看出，PHUI-UP算法在采用TWU和本文方法所估算的界值后，運行時間和占用內(nèi)存都比在采用實際上界值時少很多，這是由于實際上界值的計算過程中需要分別計算項集X所有超集的權(quán)值，計算復(fù)雜度非常高。

圖2 不同上界值計算方法下PHUI-UP的運行時間

圖3 不同上界值計算方法下PHUI-UP的內(nèi)存占用情況

因此，通過上述的實驗結(jié)果和分析，可以得出結(jié)論：本文所提出的上界估算方法省去了針對不同難約束模式指標都需要估算其相應(yīng)上界的過程，代價是相對于這些特定的上界可能會占用較多的運行時間和內(nèi)存，但是相對于計算項集的實際上界值，本文所提出的方法仍然節(jié)省了大量的運行時間和內(nèi)存。

6 結(jié)語

針對約束模式挖掘中模式指標的界值估算問題，本文在帶有權(quán)值的不確定型事務(wù)數(shù)據(jù)庫上提出了一種通用上/下界計算方法，建立了對難約束指標進行上/下界值估算的統(tǒng)一框架，可以快速實現(xiàn)對候選項集的剪除。

本文提出了一種面向不確定數(shù)據(jù)模式指標的通用上/下界估算方法，通過對比PHUI-UP算法分別與TWU、本文方法和實際上界值相結(jié)合后的運行時間和內(nèi)存占用情況，驗證了本文方法的可行性和有效性。

本文所建立的通用上/下界值估算方法都是面向形如PI(X,D,U,P)≥或≤β的模式指標，在后續(xù)的研究中可以通過考慮一些其他形式的模式指標約束來改進該方法。不確定性理論、智能搜索算法與通用上/下界值估算方法的結(jié)合也將是下一步的研究內(nèi)容。

References)

[1] ZHU F, ZHANG Z, QU Q. A direct mining approach to efficient constrained graph pattern discovery [C]// SIGMOD 2013: Proceedings of the 2013 Special Interest Group on Management of Data. New York: ACM, 2013: 821-832.

[2] GUNS T, NIJSSEN S, RAEDT L.K-pattern set mining under constraints [J]. IEEE Transaction on Knowledge and Data Engineering, 2013, 25(2): 402-418.

[3] ZENG X, PEI J, WANG K, et al. PADS: a simple yet effective pattern-aware dynamic search method for fast maximal frequent pattern mining [J]. Knowledge and Information Systems, 2009, 20(3): 243-252.

[4] GAO L. Domain-driven data mining: challenges and prospects [J]. IEEE Transaction on Knowledge and Data Engineering, 2010, 22(6): 755-769.

[5] AGRAWAL R, IMIELINSKI T, SWAMI A. Mining association rules between sets of items in large databases [C]// SIGMOD’ 93: Proceedings of the 1993 ACM Special Interest Group on Management of Data. New York: ACM, 1993: 207-216.

[6] BONCHIA F, GIANNOTTIB F, LUCCHESB C, et al. A constraint-based querying system for exploratory pattern discovery [J]. Information Systems, 2009, 34(1): 3-27.

[7] YAO H, HAMMILTON H J, BUTZ C J. A foundational approach to mining itemset utilities from databases [C]// SDM 2004: Proceedings of the 2004 Siam International Conference on Data mining. New York: ACM, 2004: 482-486.

[8] WU C, SHIE B, TSENG V, et al. Mining top-Khigh utility itemsets [C]// KDD 2012: Proceedings of the 2012 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2012: 78-86.

[9] TANG L, ZHANG L, LUO P, et al. Incorporating occupancy into frequent pattern mining for high quality pattern recommendation [C]// Proceedings of the 2013 ACM International Conference on Information and Knowledge Management. New York: ACM, 2013: 75-84.

[10] YUN U. Efficient mining of weighted interesting patterns with a strong weight and/or support affinity [J]. Information Sciences, 2007, 177(17): 213-241.

[11] 張磊.基于約束的頻繁模式挖掘方法[D].合肥：中國科學技術(shù)大學，2014:73-116.(ZHANG L. Constraint-based frequent pattern mining: novel applications and new techniques [D]. Hefei: University of Science and Technology of China, 2014: 73-116.)

[12] GREEN T, TANNEN V. Models for incomplete and probabilistic information [C]// Proceedings of the 2006 IEEE International Conference on Extending Database Technology. Piscataway, NJ: IEEE, 2006: 278-296.

[13] LIN C W, HONG T P, LU W H. An effective tree structure for mining high utility itemsets [J]. Expert Systems with Applications, 2011, 38(6): 7419-7424.

[14] LIU M, QU J. Mining high utility itemsets without candidate generation [C]// KDD 2012: Proceedings of the 2012 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2012: 78-86.

[15] LIU Y, LIAO W, CHOUDHARY A. A two-phase algorithm for fast discovery of high utility itemsets [C]// Proceedings of the 2005 Pacific-Asia Conference on Knowledge Discovery and Data Mining. New York: ACM, 2005: 689-695.

WANGJu, born in 1991, Ph. D. candidate. Her research interests include data mining, pattern recognition.

LUIFuxian, born in 1962, Ph. D., professor. His research interests include simulation of warfare, data mining.

JINChunjie, born in 1989, assistant engineer. His research interests include data mining, pattern recognition.