汪金苗, 張龍波， 閆光輝， 王鳳英

(1.山東理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 山東 淄博 255091；2.蘭州交通大學(xué) 電子與信息工程學(xué)院， 甘肅 蘭州 730070)

不確定性數(shù)據(jù)廣泛存在于多個(gè)應(yīng)用領(lǐng)域中，例如RFID(Radio Frequency Identification)，LBS (Location Based Services)，傳感器網(wǎng)絡(luò)等，其特點(diǎn)是每個(gè)數(shù)據(jù)對象不再是傳統(tǒng)的單個(gè)數(shù)據(jù)點(diǎn)，而是按照概率分布在多個(gè)數(shù)據(jù)點(diǎn)上[1].目前對不確定性數(shù)據(jù)挖掘算法的研究已經(jīng)成為了數(shù)據(jù)挖掘領(lǐng)域的新熱點(diǎn).不確定性數(shù)據(jù)挖掘主要包括分類、聚類、孤立點(diǎn)檢測、頻繁項(xiàng)集挖掘等方面，其中頻繁項(xiàng)集挖掘是重點(diǎn)研究的問題之一.

文獻(xiàn)[2]在Apriori算法的基礎(chǔ)上提出了適用于不確定數(shù)據(jù)挖掘的U-Apriori算法，文獻(xiàn)[3]在FP-growth算法的基礎(chǔ)上提出了基于樹結(jié)構(gòu)的不確定數(shù)據(jù)頻繁項(xiàng)集挖掘算法UF-growth，文獻(xiàn)[4-6]進(jìn)一步在此基礎(chǔ)上提出了包含約束條件的頻繁項(xiàng)集挖掘算法，文獻(xiàn)[7]綜述了不確定性數(shù)據(jù)中的頻繁項(xiàng)集挖掘算法，文獻(xiàn)[8]在基于約束的頻繁項(xiàng)集挖掘算法U-FPS的基礎(chǔ)上，提出了一種不確定性數(shù)據(jù)中基于約束的頻繁項(xiàng)集挖掘算法，其支持度的計(jì)算采用數(shù)據(jù)庫垂直模式求交集的方式.文獻(xiàn)[9]提出了一種不確定性數(shù)據(jù)中頻繁項(xiàng)的查詢算法，通過兩條過濾規(guī)則來減少檢測數(shù)據(jù)的數(shù)量，從而提高查詢精度.

目前，不確定性數(shù)據(jù)中最大頻繁項(xiàng)集的挖掘算法尚不多見，在此背景下本文提出一種不確定性數(shù)據(jù)中最大頻繁項(xiàng)集挖掘算法UMF-growth(Uncertain Maximal Frequent-growth)，該算法以UF-growth算法為基礎(chǔ)，可通過兩個(gè)步驟完成最大頻繁項(xiàng)集的挖掘：(1)獲取所有的頻繁1-項(xiàng)集，進(jìn)而挖掘出以所有頻繁1-項(xiàng)集為后綴的局部最大頻繁項(xiàng)集；(2)在UMF-tree的幫助下，從第(1)步得到的局部最大頻繁項(xiàng)集中挖掘出所有全局最大頻繁項(xiàng)集.

1 問題定義

在不確定性數(shù)據(jù)中，數(shù)據(jù)集D由d個(gè)事務(wù)t1,t2,…，td構(gòu)成，每個(gè)事務(wù)ti由多個(gè)項(xiàng)構(gòu)成，多個(gè)項(xiàng)的集合可用X來表示，每個(gè)項(xiàng)x在ti中出現(xiàn)的概率用P(x,ti)來表示.一個(gè)項(xiàng)集X出現(xiàn)在現(xiàn)實(shí)世界的概率(預(yù)計(jì)支持度except support)是通過將X出現(xiàn)在每個(gè)可能世界Wj的支持度相加得到的.用expSup(X)表示X出現(xiàn)在現(xiàn)實(shí)世界的預(yù)計(jì)支持度，可能世界Wj出現(xiàn)的概率用P(Wj)表示，X出現(xiàn)在可能世界Wj的概率用S(X,Wj)表示，則有如下公式：

P(Wj)=

(1)

expSup(X)=

(2)

如果一個(gè)由不確定性數(shù)據(jù)構(gòu)成的頻繁項(xiàng)集Y的所有超集都是非頻繁項(xiàng)集，則稱Y為最大頻繁項(xiàng)集，所有的最大頻繁項(xiàng)集記為UMF(Uncertain Maximal Frequent)；在挖掘過程中得到的、以某個(gè)項(xiàng)y為后綴的最大頻繁項(xiàng)集稱為y的局部最大頻繁項(xiàng)集，記為y-LUMF(Local Uncertain Maximal Frequent).

2 不確定性數(shù)據(jù)中最大頻繁項(xiàng)集挖掘算法UMF-growth

與UF-growth算法類似，我們提出的UMF-growth算法也是首先構(gòu)建UF-tree，然后借助UF-tree進(jìn)行最大頻繁項(xiàng)集的挖掘.UF-tree的每個(gè)節(jié)點(diǎn)包括三個(gè)字段：(1)項(xiàng)的名稱(2)預(yù)計(jì)支持度(3)預(yù)計(jì)支持度相等的同一個(gè)項(xiàng)出現(xiàn)的次數(shù)count.其構(gòu)建過程如下：

(a)掃描整個(gè)事務(wù)數(shù)據(jù)庫，分別將每個(gè)項(xiàng)的支持度進(jìn)行相加，結(jié)果(該項(xiàng)的預(yù)計(jì)支持度)不小于閾值的項(xiàng)記為頻繁1-項(xiàng)集，按照累加的預(yù)計(jì)支持度對所有的頻繁1-項(xiàng)集降序排序，結(jié)果保存在L中.

(b)類似與FP-tree的構(gòu)建過程，再一次掃描事務(wù)數(shù)據(jù)庫，將每條事務(wù)中的頻繁1-項(xiàng)集按照L中的順序進(jìn)行排序，然后插入到UF-tree中，同時(shí)舍棄非頻繁項(xiàng)，當(dāng)數(shù)據(jù)庫中所有包含頻繁1-項(xiàng)集的事務(wù)均插入到UF-tree中后即完成了UF-tree的構(gòu)建.UF-tree的構(gòu)建過程與FP-tree的不同之處在于，當(dāng)要插入某條事務(wù)時(shí)，當(dāng)且僅當(dāng)該事務(wù)包含的所有項(xiàng)的名稱及預(yù)計(jì)支持度依次與UF-tree中已有的某個(gè)分支上的項(xiàng)名及預(yù)計(jì)支持度完全一致時(shí)，該事務(wù)可以與這個(gè)分支合并，同時(shí)每個(gè)節(jié)點(diǎn)的count加1；如果即將插入的事務(wù)所包含的項(xiàng)與某個(gè)分支不完全一致，或者項(xiàng)名一致而某些項(xiàng)的預(yù)計(jì)支持度不一致，則該事務(wù)都要作為UF-tree的一個(gè)新的分支插入進(jìn)來.

完成UF-tree的構(gòu)建后就可以進(jìn)行最大頻繁項(xiàng)集的挖掘了.UMF-growth算法將挖掘過程分為兩個(gè)步驟，(1)采用LUMF-growth(Local Uncertain Maximal Frequent-growth)挖掘所有以頻繁1-項(xiàng)集為后綴的局部最大頻繁項(xiàng)集；(2)利用所有的局部最大頻繁項(xiàng)集構(gòu)建UMF-Tree，從而挖掘出所有的全局最大頻繁項(xiàng)集，即真正的最大頻繁項(xiàng)集.

2.1 局部最大頻繁項(xiàng)集挖掘算法LUMF-growth

UF-tree構(gòu)建完成后，從L中的最后一個(gè)項(xiàng)x(即支持度最小的頻繁1-項(xiàng)集)開始，遍歷UF-tree，找出所有包含x的分支，這些分支即表示以x為后綴的局部最大項(xiàng)集(不一定是頻繁的).局部最大項(xiàng)集可能有多個(gè)，設(shè)其中的一個(gè)為{X,x}，其中X包含k個(gè)項(xiàng)，x在此分支上的頻數(shù)count為n，計(jì)算項(xiàng)集{X,x}的預(yù)計(jì)支持度，根據(jù)不同的結(jié)果分兩種情況處理：

(1)如果得到的預(yù)計(jì)支持度不小于最小支持度閾值min_sup，即項(xiàng)集{X,x}是頻繁的，則將{X,x}記為以x為后綴的局部最大頻繁項(xiàng)集x-LUMF.同時(shí)按以下方法對UF-tree進(jìn)行剪枝操作：如果項(xiàng)集{X,x}包含該分支上的所有節(jié)點(diǎn)，則將這些節(jié)點(diǎn)的頻數(shù)count減n(即減去已參與計(jì)算的部分)，如果某些節(jié)點(diǎn)的count減為0，則將其剪枝.進(jìn)行剪枝的原理為：由于x是支持度最小的項(xiàng)，所以x必定位于UF-tree的葉子節(jié)點(diǎn)，這樣x-LUMF就包含了該分支上的所有節(jié)點(diǎn)，以該分支上其他節(jié)點(diǎn)為后綴的局部最大頻繁項(xiàng)集一定是x-LUMF的子集，因此都不可能是最大頻繁項(xiàng)集，所以將其進(jìn)行剪枝.

(2)如果得到的預(yù)計(jì)支持度小于支持度閾值min_sup，則對X生成包含k-1個(gè)項(xiàng)的子項(xiàng)集{X1,X2,…，Xk}，然后分別計(jì)算{X1,x}，{X2,x}，…，{X,x}的預(yù)計(jì)支持度.對于{X1,x}，如果其預(yù)計(jì)支持度不小于閾值min_sup，則按步驟(1)進(jìn)行處理；否則，繼續(xù)對X1生成包含k-2個(gè)項(xiàng)的子項(xiàng)集，然后按同樣的方式處理，直到找到以x為后綴的局部最大頻繁項(xiàng)集或者子項(xiàng)集為空.

重復(fù)步驟(1)與(2)，直到找到所有的x-LUMF，然后將UF-tree中所有包含x的節(jié)點(diǎn)刪除，對L中倒序排序的下一個(gè)頻繁1-項(xiàng)集按同樣的方式進(jìn)行處理，直到UF-tree為空.此時(shí)即得到了所有以頻繁1-項(xiàng)集為后綴的局部最大頻繁項(xiàng)集.

算法的偽代碼如下：

(Ⅰ)LUMF_growth(UF-tree,Header)

輸入：當(dāng)前的UF-tree，頭表Header

輸出：所有的局部最大頻繁項(xiàng)集

(1)forHeader中最后一個(gè)節(jié)點(diǎn)x的每個(gè)路徑{X,x}

(2)if (expSup{X,x}>=min_sup)

(3)x.LUMF=x.LUMF∪X

(4)ifX包含該路徑上的所有節(jié)點(diǎn)

(5) for每個(gè)節(jié)點(diǎn)β

(6)β.count=β.count-checkCount；

//checkCount指該節(jié)點(diǎn)參與計(jì)算的頻數(shù)

(7) if(β.count=0)

(8)Remove(β)；

//如果頻數(shù)減為0則將該節(jié)點(diǎn)刪除

(9)else

(10)getMFSubset(UF-tree，{X,x})；

(11)Remove(x)；//將節(jié)點(diǎn)x從UF-Tree刪除

(12)Delete(x)；//將x從Header中刪除

(13)LUMF_growth(UF-tree,Header)；

(Ⅱ)getMFSubset(UF-tree，{X,x})

輸入：當(dāng)前的UF-tree，項(xiàng)集 {X,x}

輸出：項(xiàng)集{X,x}的所有最長頻繁子項(xiàng)集

(1)k=getNodenum(X)；//獲得集合X包含的節(jié)點(diǎn)數(shù)

(2)if (k>1)

(5) if(expSup{Xi,x}>=min_sup)

(6)x.LUMF=x.LUMF∪Xi；

(7) return( )；

(8) else

(9)getMFSubset(UF-tree，{Xi,x})；

2.2 最大頻繁項(xiàng)集的挖掘

完成局部最大頻繁項(xiàng)集的挖掘后，通過構(gòu)建UMF-tree的方式來進(jìn)行最大頻繁項(xiàng)集的挖掘.UMF-tree的構(gòu)建過程與FP-tree類似，從L中的最后一個(gè)項(xiàng)、倒序開始(即按預(yù)計(jì)支持度從小到大的順序)，將每個(gè)以頻繁1-項(xiàng)集為后綴的局部最大頻繁項(xiàng)集作為UMF-tree的一個(gè)分支，但是在插入之前需要檢查UMF-tree中是否存在某個(gè)分支已包含該項(xiàng)集，如果存在這樣的分支，則說明UMF-tree中存在該局部最大頻繁項(xiàng)集的超集，則該項(xiàng)集就不可能是最大頻繁項(xiàng)集，將其舍棄，否則，按照FP-tree的構(gòu)建方式插入到UMF-tree中.對所有的局部最大頻繁項(xiàng)集進(jìn)行如上操作，最后得到的UMF-tree即包含了所有的最大頻繁項(xiàng)集.

根據(jù)局部最大頻繁項(xiàng)集的挖掘方式以及UMF-tree的構(gòu)建方式可以得出如下結(jié)論：將要插入到UMF-tree的局部最大頻繁項(xiàng)集，要么是UMF-tree中某個(gè)分支的子項(xiàng)集，要么是全局最大頻繁項(xiàng)集，而不會(huì)是在其之后插入的局部最大頻繁項(xiàng)集的子項(xiàng)集.這是因?yàn)椋M(jìn)行局部最大頻繁項(xiàng)集挖掘時(shí)，是從L中的最后一個(gè)項(xiàng)開始、倒序進(jìn)行的，也就是按頻繁1-項(xiàng)集的預(yù)計(jì)支持度從小到大的順序進(jìn)行的，這樣得到的局部最大頻繁項(xiàng)集是按照其后綴在L中的順序倒序排列的；而UMF-tree的構(gòu)建也是從L中的最后一個(gè)項(xiàng)開始、倒序進(jìn)行的，由局部最大頻繁項(xiàng)集的挖掘方法可知，先進(jìn)行插入操作的局部最大頻繁項(xiàng)集的后綴項(xiàng)，肯定不會(huì)出現(xiàn)在之后插入的局部最大頻繁項(xiàng)集中，即先插入的局部最大頻繁項(xiàng)集不可能是后插入的局部最大頻繁項(xiàng)集的子項(xiàng)集，而只能是其超集，所以可以得出上述結(jié)論.

根據(jù)這個(gè)結(jié)論得知：UMF-tree包含且僅包含了數(shù)據(jù)庫中的所有最大頻繁項(xiàng)集，其每個(gè)分支即為一個(gè)最大頻繁項(xiàng)集.

3 實(shí)驗(yàn)與分析

IBM數(shù)據(jù)生成器(IBM Quest Market-Basket Synthetic Data Generator)是數(shù)據(jù)挖掘領(lǐng)域常用的一種數(shù)據(jù)生成工具，本實(shí)驗(yàn)中所使用的數(shù)據(jù)集也是由該數(shù)據(jù)生成器生成.我們生成的事務(wù)數(shù)據(jù)庫中共含有1 000種項(xiàng)，包含100k條事務(wù)，平均事務(wù)長度為10，實(shí)驗(yàn)進(jìn)行之前，先對每條事務(wù)中的每個(gè)項(xiàng)設(shè)置一個(gè)隨機(jī)概率作為該項(xiàng)的支持度，其范圍為 (0,1].實(shí)驗(yàn)環(huán)境為CPU Intel core×2，內(nèi)存2G，操作系統(tǒng)為LINUX，算法采用C語言編寫，算法運(yùn)行時(shí)間包括CPU消耗時(shí)間及I/O時(shí)間，實(shí)驗(yàn)數(shù)據(jù)均是多次測試得到的平均值.

由于目前對不確定性數(shù)據(jù)的挖掘大都集中在完全頻繁項(xiàng)集，而尚未發(fā)現(xiàn)最大頻繁項(xiàng)集挖掘算法，因此無法進(jìn)行實(shí)驗(yàn)結(jié)果的對比.我們分別設(shè)計(jì)了4個(gè)實(shí)驗(yàn)來對UMF-growth算法的各項(xiàng)性能進(jìn)行測試，包括最小支持度閾值對算法性能的影響、算法的可伸縮性、數(shù)據(jù)集的稠密情況對算法性能的影響以及同一個(gè)項(xiàng)名不同支持度個(gè)數(shù)對算法性能的影響，并對每個(gè)實(shí)驗(yàn)的結(jié)果進(jìn)行了解釋與分析.

在第一個(gè)實(shí)驗(yàn)中，測試了支持度閾值對算法性能的影響，如圖1所示.UMF-growth算法的運(yùn)行時(shí)間隨支持度閾值的增大而逐漸增加，這是因?yàn)?，?dāng)支持度閾值較小時(shí)，最大頻繁項(xiàng)集長度較大，在局部最大頻繁項(xiàng)集挖掘過程中不用生成子項(xiàng)集，所以挖掘時(shí)間較少.隨著支持度閾值的增加，最大頻繁項(xiàng)集的長度越來越小，在局部最大頻繁項(xiàng)集挖掘過程中需要不斷生成這些非頻繁項(xiàng)集的子項(xiàng)集，所以挖掘時(shí)間隨支持度閾值的增加而增加.在實(shí)驗(yàn)過程中發(fā)現(xiàn)，UMF-growth算法的時(shí)間消耗大都集中在局部最大頻繁項(xiàng)集的挖掘部分，而UF-tree及UMF-tree的構(gòu)建時(shí)間所占比重較小，因此總體時(shí)間隨支持度閾值的增大而增加.

第二個(gè)實(shí)驗(yàn)測試的是UMF-growth算法的可伸縮性.這個(gè)實(shí)驗(yàn)中不僅要用到包含100KB個(gè)事務(wù)的數(shù)據(jù)集，還要用到另外9個(gè)不同規(guī)模的數(shù)據(jù)集，其規(guī)模大小為10KB，10KB，20KB，30KB，40KB，50KB，60KB，70KB，80KB和90KB.對這10個(gè)規(guī)模不同的數(shù)據(jù)集分別利用UMF-growth算法進(jìn)行最大頻繁項(xiàng)集的挖掘，其中支持度閾值設(shè)為0.1，得到的結(jié)果如圖2所示.UMF-growth算法的運(yùn)行時(shí)間隨數(shù)據(jù)庫規(guī)模的增大幾乎成線性增長，這說明UMF-growth算法具有良好的可伸縮性.

圖1 運(yùn)行時(shí)間隨閾值的變化

圖2 運(yùn)行時(shí)間隨數(shù)據(jù)集規(guī)模的變化

第三個(gè)實(shí)驗(yàn)進(jìn)行了數(shù)據(jù)集稠密程度對算法性能的影響測試.一個(gè)數(shù)據(jù)集的參數(shù)主要包含項(xiàng)的個(gè)數(shù)、事務(wù)個(gè)數(shù)、平均事務(wù)長度以及最大頻繁項(xiàng)集平均長度等.若某數(shù)據(jù)集的最大頻繁項(xiàng)集平均長度與平均事務(wù)長度相差很小，則認(rèn)為該數(shù)據(jù)集屬于稠密型，否則認(rèn)為該數(shù)據(jù)集屬于稀疏型.數(shù)據(jù)集的稠密程度往往會(huì)對算法的性能產(chǎn)生較大影響.選取兩個(gè)稠密程度不同的數(shù)據(jù)集對UMF-growth算法的性能進(jìn)行測試，觀察在不同的數(shù)據(jù)集上UMF-growth算法運(yùn)行時(shí)間的大小及其隨支持度閾值的變化情況，這兩個(gè)數(shù)據(jù)集的參數(shù)如表1所示，其中D1為稀疏型數(shù)據(jù)集，D2為稠密型數(shù)據(jù)集，實(shí)驗(yàn)結(jié)果如圖3所示.UMF-growth算法在D1上的運(yùn)行時(shí)間總是長于在D2上的運(yùn)行時(shí)間.這是因?yàn)镈1屬于稀疏型數(shù)據(jù)集，其最大頻繁項(xiàng)集平均長度遠(yuǎn)遠(yuǎn)小于平均事務(wù)長度，所以在挖掘過程中總是要產(chǎn)生非頻繁項(xiàng)集的子項(xiàng)集，子項(xiàng)集的生成消耗時(shí)間較長，導(dǎo)致挖掘時(shí)間較長；而數(shù)據(jù)集D2屬于稠密型數(shù)據(jù)集，其最大頻繁項(xiàng)集的長度與平均事務(wù)長度一致，在挖掘過程中可直接得到局部最大頻繁項(xiàng)集，無需產(chǎn)生子項(xiàng)集，所以挖掘時(shí)間較短.通過這個(gè)實(shí)驗(yàn)可以得知，UMF-growth算法特別適用于平均事務(wù)長度較短、比較稠密的數(shù)據(jù)集.

圖3 稀疏數(shù)據(jù)集VS.稠密數(shù)據(jù)集

數(shù)據(jù)集事務(wù)個(gè)數(shù)項(xiàng)個(gè)數(shù)平均事務(wù)長度最大頻繁項(xiàng)集長度稀疏數(shù)據(jù)集D1100KB1 000104稠密數(shù)據(jù)集D2100KB1 0001010

在最后一個(gè)實(shí)驗(yàn)中同一項(xiàng)名的不同支持度個(gè)數(shù)對算法性能的影響進(jìn)行了測試.本實(shí)驗(yàn)采用兩個(gè)規(guī)模及參數(shù)都相同的數(shù)據(jù)集，分別將其同一項(xiàng)名的不同支持度個(gè)數(shù)設(shè)置為較多個(gè)和較少個(gè)，對UMF-growth算法在這兩個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間進(jìn)行對比，實(shí)驗(yàn)結(jié)果如圖4所示.由圖可知，UMF-growth算法在具有較多支持度個(gè)數(shù)的數(shù)據(jù)集上的運(yùn)行時(shí)間要長于在具有較少支持度個(gè)數(shù)的數(shù)據(jù)集上的運(yùn)行時(shí)間.這是因?yàn)?，在?gòu)建UF-tree時(shí)我們規(guī)定，只有當(dāng)項(xiàng)名相同且支持度相同的情況下，兩個(gè)分支才可以合并，當(dāng)項(xiàng)名相同而支持度不同時(shí)，需要作為不同的分支插入到UF-tree中，此時(shí)UF-tree的規(guī)模會(huì)增大，UMF-growth的運(yùn)行時(shí)間會(huì)增加，所以具有較少支持度個(gè)數(shù)的數(shù)據(jù)集中分支可合并的概率更大，UF-tree的規(guī)模更小，運(yùn)行時(shí)間較短.

圖4 較少支持度VS.較多支持度

由以上4個(gè)實(shí)驗(yàn)可知，UMF-growth算法的運(yùn)行時(shí)間隨支持度閾值的增加而增加，同一項(xiàng)名支持度個(gè)數(shù)較少時(shí)效率較高，具有良好的可伸縮性并且特別適用于稠密型數(shù)據(jù)集.但是該算法也存在一些不足，例如在LUMF-growth步驟中需要不斷的產(chǎn)生非頻繁項(xiàng)集的子項(xiàng)集，當(dāng)事務(wù)平均長度較大且比較稀疏時(shí)，生成子項(xiàng)集需占用大量內(nèi)存、消耗大量時(shí)間，因此UMF-growth算法在稀疏型數(shù)據(jù)集上的效率還有待進(jìn)一步提高.

4 結(jié)束語

本文提出的基于UF-tree的最大頻繁項(xiàng)集挖掘算法UMF-growth算法，是通過兩個(gè)步驟完成最大頻繁項(xiàng)集的挖掘，首先在UF-tree的基礎(chǔ)上獲得局部最大頻繁項(xiàng)集，然后將局部最大頻繁項(xiàng)集插入U(xiǎn)MF-tree中獲得所有的最大頻繁項(xiàng)集.實(shí)驗(yàn)結(jié)果證明，UMF-growth算法具有良好的可伸縮性且特別適用于稠密型數(shù)據(jù)集，尤其是那些平均事務(wù)長度較短或最大頻繁項(xiàng)集長度與平均事務(wù)長度接近的數(shù)據(jù)集.但是，UMF-growth算法在稀疏型數(shù)據(jù)集，特別是平均事務(wù)長度較大的數(shù)據(jù)集中效率較低，因此該算法的效率還有待進(jìn)一步優(yōu)化提高.

[1]Leung C K S. Mining uncertain data[J]. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2011, 1(4): 316-329.

[2]Chui C K, Kao B, Hung E. Mining frequent itemsets from uncertain data[M]. Advances in knowledge discovery and data mining.Heidelberg:Springer Berlin, 2007: 47-58.

[3]Leung C K S, Mateo M A F, Brajczuk D A. A tree-based approach for frequent pattern mining from uncertain data[M]. Advances in Knowledge Discovery and Data Mining. Heidelberg:Springer Berlin, 2008: 653-661.

[4]Leung C K, Brajczuk D A. Efficient algorithms for the mining of constrained frequent patterns from uncertain data[J]. SIGKDD Explorations, 2010, 11(2):123-130.

[5]Cuzzocrea A, Leung C K. Distributed mining of constrained frequent sets from uncertain data[C]//Algorithms and Architectures for Parallel Processing. Springer Berlin Heidelberg, 2011: 40-53.

[6]Leung C K S, Sun L. Equivalence class transformation based mining of frequent itemsets from uncertain data[C]// Proceedings of the 2011 ACM Symposium on Applied Computing. ACM, 2011: 983-984.

[7]汪金苗, 張龍波, 鄧齊志，等．不確定數(shù)據(jù)頻繁項(xiàng)集挖掘方法綜述[J]. 計(jì)算機(jī)工程與應(yīng)用, 2011, 47(20):121-125．

[8]劉衛(wèi)明，楊健，毛伊敏．基于約束的不確定數(shù)據(jù)頻繁項(xiàng)集挖掘算法研究[J].計(jì)算機(jī)應(yīng)用研究，2012, 29(10): 3 669-3 671．

[9]王爽, 楊廣明, 朱志良．基于不確定數(shù)據(jù)的頻繁項(xiàng)查詢算法[J].東北大學(xué)學(xué)報(bào)：自然科學(xué)版，2011, 32(3): 344-347