1.2 國(guó)內(nèi)外研究現(xiàn)狀

由于靜態(tài)數(shù)據(jù)集和動(dòng)態(tài)數(shù)據(jù)流的數(shù)據(jù)特征不同，從中挖掘頻繁模式或高效用模式的算法也有所不同；但是靜態(tài)數(shù)據(jù)集的挖掘算法是動(dòng)態(tài)數(shù)據(jù)流中挖掘算法的基礎(chǔ)，本節(jié)分別從靜態(tài)數(shù)據(jù)集、動(dòng)態(tài)數(shù)據(jù)流兩方面介紹頻繁模式和高效用模式挖掘算法的研究現(xiàn)狀。

1.2.1 傳統(tǒng)數(shù)據(jù)集中頻繁模式挖掘算法的研究

1．靜態(tài)數(shù)據(jù)集上頻繁模式挖掘算法

Agrawal等[1,2]首先提出了頻繁模式挖掘問(wèn)題的原始算法，并給出了著名的Apriori算法。該算法的主要理論依據(jù)是頻繁項(xiàng)集的兩個(gè)基本性質(zhì)：①頻繁項(xiàng)集的所有非空子集都是頻繁項(xiàng)集；②非頻繁項(xiàng)集的超集都是非頻繁項(xiàng)集。算法Apriori首先產(chǎn)生頻繁1-項(xiàng)集L1，然后利用頻繁1-項(xiàng)集產(chǎn)生頻繁2-項(xiàng)集L2，直到有某個(gè)r值使得Lr為空為止。在第k次循環(huán)中，算法先產(chǎn)生候選k-項(xiàng)集的集合Ck, Ck中每一個(gè)項(xiàng)集是用兩個(gè)只有一項(xiàng)不同的Lk-1中進(jìn)行并集產(chǎn)生的。Ck中的項(xiàng)集是用來(lái)產(chǎn)生頻繁k-項(xiàng)集的候選項(xiàng)集，即頻繁項(xiàng)集Lk是Ck的一個(gè)子集。Ck中的每個(gè)項(xiàng)集需要統(tǒng)計(jì)在數(shù)據(jù)集中的個(gè)數(shù)，從而來(lái)決定其是否加入Lk，即需要掃描一遍數(shù)據(jù)集來(lái)計(jì)算Ck中的每個(gè)項(xiàng)集的支持度。

Apriori是首次提出采用逐層挖掘的算法，并且是逐層挖掘算法中的代表算法，之后的很多算法都是在此基礎(chǔ)上進(jìn)行改進(jìn)，如算法DHP[3]采用Hash技術(shù)來(lái)優(yōu)化Apriori算法中候選項(xiàng)集的產(chǎn)生過(guò)程。Cheung等[4]采用并行方式對(duì)Apriori算法進(jìn)行改進(jìn)，將數(shù)據(jù)集劃分為多個(gè)小數(shù)據(jù)塊，在每次迭代產(chǎn)生頻繁項(xiàng)集過(guò)程中，首先并行計(jì)算所有候選項(xiàng)集在各個(gè)數(shù)據(jù)塊的支持?jǐn)?shù)，然后匯總每個(gè)候選項(xiàng)集的總支持?jǐn)?shù)（即可從候選項(xiàng)集中找到頻繁項(xiàng)集），最后再利用當(dāng)前層產(chǎn)生的頻繁項(xiàng)集來(lái)產(chǎn)生新的候選項(xiàng)集來(lái)進(jìn)行下次的迭代。算法Apriori的主要缺點(diǎn)：①掃描數(shù)據(jù)集的次數(shù)至少等于最長(zhǎng)的頻繁項(xiàng)集的長(zhǎng)度；②需要維護(hù)算法過(guò)程中產(chǎn)生的候選項(xiàng)集（中間結(jié)果）。

算法Apriori在挖掘過(guò)程中產(chǎn)生了大量的候選項(xiàng)集，并且需要反復(fù)掃描數(shù)據(jù)集，嚴(yán)重影響了算法效率。為此，Han等人提出了一種無(wú)須產(chǎn)生候選項(xiàng)集的算法FP-Growth[5]，該算法只需要掃描數(shù)據(jù)集兩次：第一次掃描數(shù)據(jù)集得到頻繁1-項(xiàng)集；第二次掃描數(shù)據(jù)集時(shí)，利用頻繁1-項(xiàng)集來(lái)過(guò)濾數(shù)據(jù)集中的非頻繁項(xiàng)，同時(shí)生成FP-Tree，然后在FP-Tree上執(zhí)行遞歸算法，挖掘所有的頻繁項(xiàng)集。實(shí)驗(yàn)分析表明FP-Growth算法比Apriori算法快一個(gè)數(shù)量級(jí)。

算法FP-Growth是采用模式增長(zhǎng)的方式直接生成頻繁模式，該算法是模式增長(zhǎng)算法中的典型算法，同時(shí)也是第一個(gè)模式增長(zhǎng)算法，之后提出的模式增長(zhǎng)挖掘算法[6-18]都是在此基礎(chǔ)上進(jìn)行改進(jìn)的，包括不確定數(shù)據(jù)集中頻繁模式挖掘和高效用模式挖掘中的很多算法。

算法COFI[19]不需要遞歸的構(gòu)建子樹，該算法通過(guò)項(xiàng)集枚舉的方法來(lái)挖掘頻繁模式；在稀疏數(shù)據(jù)集上，該算法的時(shí)間和空間效率優(yōu)于算法FP-Growth，但在處理稠密數(shù)據(jù)集或長(zhǎng)事務(wù)數(shù)據(jù)集的時(shí)候，該算法的處理效率比較低。

之后提出了很多頻繁項(xiàng)集挖掘算法[20-30]，包含完全頻繁項(xiàng)集挖掘[5,19,21,22,24,26,31-35]、閉項(xiàng)集挖掘[20,28,36]和最大頻繁項(xiàng)集挖掘[23,25,27,29,37]；其中國(guó)內(nèi)在這領(lǐng)域研究也有較大的進(jìn)展[7,38-74]，包括TOP-K頻繁項(xiàng)集挖掘[75-77]、負(fù)關(guān)聯(lián)規(guī)則挖掘算法[78,79]等。

2．?dāng)?shù)據(jù)流中頻繁項(xiàng)集挖掘算法

和靜態(tài)數(shù)據(jù)集相比，動(dòng)態(tài)數(shù)據(jù)流上有更多的信息需要跟蹤，如以前頻繁模式后來(lái)變?yōu)榉穷l繁項(xiàng)集，或以前非頻繁模式后來(lái)變?yōu)轭l繁模式；另外，由于數(shù)據(jù)的流動(dòng)性，當(dāng)前內(nèi)存中維護(hù)的數(shù)據(jù)要不斷地調(diào)整。數(shù)據(jù)流中的頻繁模式挖掘算法一般采用窗口方法獲取當(dāng)前用戶關(guān)注的數(shù)據(jù)；然后基于已有的靜態(tài)數(shù)據(jù)集上的頻繁模式挖掘算法，提出可以挖掘數(shù)據(jù)流中被關(guān)注數(shù)據(jù)的算法。目前存在3種典型的窗口模型[80]：界標(biāo)窗口模型（Landmark Window Model）、時(shí)間衰減窗口模型（Damped Window Model）和滑動(dòng)窗口模型（Sliding Window Model）。

界標(biāo)窗口模型中的窗口指特定一時(shí)間點(diǎn)（或數(shù)據(jù)流中一條特定的數(shù)據(jù)）到當(dāng)前時(shí)間（或當(dāng)前條數(shù)據(jù)）之間的數(shù)據(jù)，界標(biāo)窗口模型如圖1.1（a）所示，在C1、C2和C3時(shí)刻，窗口中的數(shù)據(jù)分別包含了從S點(diǎn)到C1點(diǎn)、C2點(diǎn)和C3點(diǎn)之間的數(shù)據(jù)。文獻(xiàn)[81-85]中頻繁項(xiàng)集挖掘算法都是基于界標(biāo)窗口，文獻(xiàn)[82]提出算法DSM-FI（Data Stream Mining for Frequent Itemsets）是基于界標(biāo)窗口，它以數(shù)據(jù)開(kāi)始點(diǎn)為界標(biāo)點(diǎn)，該算法有三個(gè)重要特征：①整個(gè)挖掘過(guò)程只需要一遍數(shù)據(jù)集掃描；②擴(kuò)展前綴樹存儲(chǔ)挖掘的模式；③自上而下的方式挖掘頻繁項(xiàng)集。文獻(xiàn)[83]提出一個(gè)基于界標(biāo)窗口的頻繁閉項(xiàng)集挖掘算法FP-CDS，該算法將一個(gè)界標(biāo)窗口劃分為多個(gè)基本窗口，每個(gè)基本窗口作為一個(gè)更新單元（每個(gè)基本窗口中的數(shù)據(jù)也可以稱為一批數(shù)據(jù)）：首先從每個(gè)基本窗口中挖掘出潛在的頻繁閉項(xiàng)集，同時(shí)存儲(chǔ)在FP-CDS樹上，最終從FP-CDS樹上挖掘出所有的頻繁閉項(xiàng)集。文獻(xiàn)[84]提出一個(gè)近似算法Lossy Counting，該算法以批為處理單元，每來(lái)一批就更新一次已有頻繁項(xiàng)集的支持?jǐn)?shù)，頻繁的項(xiàng)集被保留下來(lái)，不頻繁的被刪除，同時(shí)也將當(dāng)前批中新的頻繁項(xiàng)集保留下來(lái)。

時(shí)間衰減窗口模型和界標(biāo)窗口模型所包含的數(shù)據(jù)是相同的，只是衰減窗口中的每條數(shù)據(jù)有不同的權(quán)重，距離當(dāng)前時(shí)間越近，數(shù)據(jù)的權(quán)重越大，如圖1.1（b）所示；實(shí)際上，時(shí)間衰減窗口模型是界標(biāo)窗口模型的一個(gè)特例。文獻(xiàn)[86-90]中算法都是基于時(shí)間衰減窗口模型。文獻(xiàn)[86]提出一個(gè)基于衰減窗口模型的近似算法，該算法用一個(gè)樹結(jié)構(gòu)FP-stream來(lái)存儲(chǔ)兩類項(xiàng)集：頻繁項(xiàng)集和潛在頻繁項(xiàng)集。當(dāng)新來(lái)一批數(shù)據(jù)的時(shí)候，更新樹結(jié)構(gòu)上這兩類項(xiàng)集的支持?jǐn)?shù)，如果更新后的項(xiàng)集既不是頻繁項(xiàng)集，也不是潛在頻繁項(xiàng)集，則將這類項(xiàng)集從樹上刪除；同時(shí)新來(lái)一批數(shù)據(jù)中新產(chǎn)生的頻繁項(xiàng)集或潛在頻繁項(xiàng)集也要存儲(chǔ)在這個(gè)樹結(jié)構(gòu)上。文獻(xiàn)[87]引入一個(gè)時(shí)間衰減的函數(shù)來(lái)計(jì)算項(xiàng)集支持?jǐn)?shù)以及總的事務(wù)支持?jǐn)?shù)。文獻(xiàn)[88]采用固定的衰減值，當(dāng)新來(lái)一個(gè)事務(wù)項(xiàng)集的時(shí)候，已有的頻繁項(xiàng)集的支持?jǐn)?shù)都乘以固定的衰減值，如果新來(lái)的事務(wù)包含某一頻繁項(xiàng)集，則該項(xiàng)集的支持?jǐn)?shù)再加上1。

滑動(dòng)窗口模型中當(dāng)前處理數(shù)據(jù)的個(gè)數(shù)固定，或者是當(dāng)前處理數(shù)據(jù)的時(shí)間段長(zhǎng)度固定，如圖1.1（c）所示。基于滑動(dòng)窗口模型的頻繁項(xiàng)集挖掘算法研究比較多[91-100]。文獻(xiàn)[92]提出一個(gè)挖掘算法DST，該算法指定一個(gè)窗口中有固定批的數(shù)據(jù)，并且每批數(shù)據(jù)中事務(wù)個(gè)數(shù)也是固定的，每新到一批數(shù)據(jù)就更新一次窗口；DST將窗口中事務(wù)數(shù)據(jù)保存到樹DST-Tree上，DST-Tree的節(jié)點(diǎn)結(jié)構(gòu)如圖1.2（a）所示，節(jié)點(diǎn)上的P字段記錄節(jié)點(diǎn)當(dāng)前窗口中每批數(shù)據(jù)中的支持?jǐn)?shù)，同時(shí)每個(gè)節(jié)點(diǎn)還用L字段記錄更新該節(jié)點(diǎn)的最后批次；每新來(lái)一批數(shù)據(jù)，將新到的數(shù)據(jù)添加到樹DST-Tree上，同時(shí)修改相應(yīng)節(jié)點(diǎn)上的P值和L值。算法DST在挖掘窗口中頻繁項(xiàng)集之前，先把樹上不再有用的節(jié)點(diǎn)（垃圾節(jié)點(diǎn)）從樹上刪除，然后用算法FP-Growth挖掘每個(gè)窗口中的頻繁項(xiàng)集。文獻(xiàn)[92]的作者后來(lái)又提出一個(gè)算法DSP[93]，算法DSP和DST的主要區(qū)別是DSP采用COFI來(lái)挖掘窗口中的頻繁項(xiàng)集，而DST是用FP-Growth挖掘窗口中的頻繁項(xiàng)集；算法DSP存儲(chǔ)事務(wù)項(xiàng)集的樹結(jié)構(gòu)和DST的相同。

文獻(xiàn)[95]提出一個(gè)基于滑動(dòng)窗口的頻繁項(xiàng)集挖掘算法CPS，在算法CPS中，每個(gè)窗口是由固定批的數(shù)據(jù)組成，以批為單位更新窗口中數(shù)據(jù)，該算法將窗口中事務(wù)項(xiàng)集保存到一棵CPS-Tree樹上，樹CPS-Tree上有兩類節(jié)點(diǎn)：正常節(jié)點(diǎn)（normal node）和尾節(jié)點(diǎn)（tail-node），正常節(jié)點(diǎn)上只記錄該節(jié)點(diǎn)總的支持?jǐn)?shù)S，如圖1.2（b）所示；而尾節(jié)點(diǎn)要記錄總的支持?jǐn)?shù)S，同時(shí)還用一個(gè)數(shù)組P記錄一個(gè)節(jié)點(diǎn)當(dāng)前窗口中每批數(shù)據(jù)上的支持?jǐn)?shù)，如圖1.2（c）所示。每新來(lái)一批數(shù)據(jù)，該算法會(huì)將樹中的垃圾節(jié)點(diǎn)刪除，采用FP-Growth算法挖掘每個(gè)窗口中的頻繁項(xiàng)集。

1.2.2 不確定數(shù)據(jù)集中的頻繁模式挖掘算法的研究

隨著數(shù)據(jù)挖掘技術(shù)的廣泛應(yīng)用、數(shù)據(jù)采集中的不確定性和誤差性等原因，現(xiàn)實(shí)中會(huì)產(chǎn)生很多不確定的數(shù)據(jù)，例如一個(gè)病人在問(wèn)診中，往往并不能根據(jù)病人的癥狀而被百分之百地確診為某一病；通過(guò)RFID或者GPS獲取的目標(biāo)位置都有誤差[101,102]；用商業(yè)網(wǎng)站或歷史數(shù)據(jù)中挖掘到的購(gòu)物習(xí)慣來(lái)預(yù)測(cè)某些顧客下一步購(gòu)買的商品都存在一定的不確定性。表1.1是一個(gè)不確定數(shù)據(jù)集的例子，每個(gè)事務(wù)表示某一顧客最近要買哪些商品以及買這些商品的可能性（概率）。因此隨著不確定數(shù)據(jù)在很多領(lǐng)域的產(chǎn)生，對(duì)該類數(shù)據(jù)進(jìn)行挖掘分析又成為數(shù)據(jù)挖掘領(lǐng)域一個(gè)新的研究問(wèn)題[103-124]。由于不確定數(shù)據(jù)集和傳統(tǒng)數(shù)據(jù)集的數(shù)據(jù)結(jié)構(gòu)不同，并且兩類數(shù)據(jù)集上的頻繁模式挖掘模型也不同，因此不能用傳統(tǒng)數(shù)據(jù)集中的算法來(lái)挖掘不確定數(shù)據(jù)集中的頻繁模式。本節(jié)根據(jù)數(shù)據(jù)集的靜態(tài)和動(dòng)態(tài)特性，分別描述不確定數(shù)據(jù)集上頻繁模式挖掘算法的研究現(xiàn)狀。

1．靜態(tài)數(shù)據(jù)集

不確定事務(wù)數(shù)據(jù)集的頻繁項(xiàng)集挖掘算法主要分為逐層挖掘（level-wise）和模式增長(zhǎng)（pattern-growth）兩種方法。逐層挖掘的算法基于算法Apriori，模式增長(zhǎng)方式的算法則基于算法FP-Growth。表1.2列出了一些重要算法及其一些特征。

U-Apriori[121]是第一個(gè)不確定數(shù)據(jù)集上的頻繁項(xiàng)集挖掘算法，該算法是基于Apriori提出的。該算法和Apriori的主要區(qū)別是前者掃描數(shù)據(jù)集是為了計(jì)算每個(gè)候選項(xiàng)集的期望支持?jǐn)?shù)，而后者掃描數(shù)據(jù)集是為了計(jì)算候選項(xiàng)集的支持?jǐn)?shù)。因此U-Apriori算法的缺陷同Apriori算法一樣：產(chǎn)生候選項(xiàng)集，以及需要多遍掃描數(shù)據(jù)集來(lái)統(tǒng)計(jì)每層候選項(xiàng)集的期望支持?jǐn)?shù)，如果最長(zhǎng)的頻繁項(xiàng)集長(zhǎng)度是k，則最少需要掃描k次數(shù)據(jù)集。因此，如果數(shù)據(jù)集比較大、事務(wù)項(xiàng)集長(zhǎng)度比較長(zhǎng)或設(shè)定的最小期望支持?jǐn)?shù)比較小，則U-Apriori的時(shí)間和空間性能都會(huì)受到很大的影響。

2011年，Wang等[115]提出一個(gè)不確定數(shù)據(jù)集的頻繁項(xiàng)集挖掘算法MBP。該算法主要是對(duì)U-Apriori算法的改進(jìn)，作者提出了兩種策略來(lái)提高計(jì)算候選項(xiàng)集的期望支持?jǐn)?shù)的效率：①在掃描數(shù)據(jù)集的過(guò)程中，如果一個(gè)候選項(xiàng)集提前被識(shí)別為非頻繁項(xiàng)集，就停止計(jì)算該項(xiàng)集的實(shí)際期望支持?jǐn)?shù)；②掃描數(shù)據(jù)集的過(guò)程中，如果一個(gè)候選項(xiàng)集的當(dāng)前期望支持?jǐn)?shù)已經(jīng)大于預(yù)定義的最小期望支持?jǐn)?shù)，就停止計(jì)算該項(xiàng)集的實(shí)際期望支持?jǐn)?shù)。因此，算法MBP在時(shí)間和空間性能上得到了很大的提升。

2012年，Sun等[111]改善了算法MBP，基于MBP算法給出一個(gè)不確定數(shù)據(jù)集中頻繁項(xiàng)集挖掘的近似算法IMBP。IMBP時(shí)間和空間性能優(yōu)于MBP，然而，其準(zhǔn)確性并不穩(wěn)定，并且在稠密數(shù)據(jù)集中的精確度比較低。

2007年，Leung等[122]提出一個(gè)基于樹的模式增長(zhǎng)的算法UF-Growth，該算法中還提出一個(gè)新的樹結(jié)構(gòu)UF-Tree來(lái)存儲(chǔ)不確定事務(wù)數(shù)據(jù)集，采用模式增長(zhǎng)的方式從樹上挖掘頻繁項(xiàng)集。UF-Growth和FP-Growth的主要區(qū)別有兩點(diǎn)：①UF-Tree樹上每個(gè)節(jié)點(diǎn)除了保存和FP-Tree樹上節(jié)點(diǎn)相同的信息外，還保存了每個(gè)節(jié)點(diǎn)的概率值，因此只有項(xiàng)相同，并且其相應(yīng)的概率值相同的項(xiàng)才能共享同一個(gè)節(jié)點(diǎn)；而FP-Tree中，只要項(xiàng)相同就可以共享同一節(jié)點(diǎn)。②UF-Growth中計(jì)算頻繁項(xiàng)集的時(shí)候都是統(tǒng)計(jì)項(xiàng)集的期望支持?jǐn)?shù)，F(xiàn)P-Growth是計(jì)算項(xiàng)集的支持?jǐn)?shù)。因此，UF-Tree樹上的節(jié)點(diǎn)比較多，例如，對(duì)于兩個(gè)不確定事務(wù)項(xiàng)集{a:0.50, b:0.70, c:0.23}和{a:0.55, b:0.80, c:0.23}，當(dāng)按照字典順序插入樹中時(shí)，由于兩個(gè)事務(wù)中項(xiàng)a的概率不相等，所以這兩個(gè)項(xiàng)集不能共享同一個(gè)節(jié)點(diǎn)a，從而算法UF-Growth需要更多的空間和時(shí)間來(lái)處理UF-Tree。

Leung等[120]又改善UF-Growth以減小UF-Tree樹的大小。改進(jìn)算法的思想：先預(yù)定義一個(gè)k值，只考慮事務(wù)項(xiàng)集中概率值小數(shù)點(diǎn)之后的前k位數(shù)，如果兩個(gè)概率的小數(shù)點(diǎn)之后的前k位數(shù)值都相同，則認(rèn)為這兩個(gè)概率值相同。例如，設(shè)定k值為1，當(dāng)這兩個(gè)事務(wù)項(xiàng)集{a∶0.50, b:0.70, c:0.23}和{a∶0.55, b∶0.80, c∶0.23}再按字典順序添加到UF-Tree上時(shí)，則項(xiàng)a的概率均為0.5，則這兩個(gè)項(xiàng)集可以共享同一個(gè)節(jié)點(diǎn)a；但若k設(shè)定為2，則項(xiàng)a概率分別為0.50和0.55，則這兩個(gè)項(xiàng)集就不能共享同一個(gè)節(jié)點(diǎn)a。k值越小，改進(jìn)后的算法消耗的內(nèi)存越小，但改進(jìn)后的算法仍然不能創(chuàng)建一棵與原始FP-Tree一樣壓縮率的UF-Tree，并且改進(jìn)后的算法還可能會(huì)丟失一些頻繁項(xiàng)集。

算法UH-Mine[125]也是一個(gè)模式增長(zhǎng)的算法，它和UF-Growth算法的主要區(qū)別：UF-Growth算法采用FP-Tree保存事務(wù)項(xiàng)集，而UH-Mine采用非壓縮的結(jié)構(gòu)H-struct[26]來(lái)保存事務(wù)項(xiàng)集。在將事務(wù)項(xiàng)集存儲(chǔ)到H-struct上時(shí)，沒(méi)有任何的壓縮，即任兩個(gè)項(xiàng)集都不會(huì)共享任何節(jié)點(diǎn)。H-struct的創(chuàng)建也需要掃描數(shù)據(jù)集兩遍：第一遍，創(chuàng)建一個(gè)有序的頻繁1-項(xiàng)集頭表；第二遍，將事務(wù)項(xiàng)集添加到H-struct中，同時(shí)按頭表的順序添加，并且刪除事務(wù)項(xiàng)集中非頻繁的項(xiàng)。頭表中還保存有每個(gè)頻繁項(xiàng)在樹上的所有節(jié)點(diǎn)。該算法在較小的數(shù)據(jù)集上，能獲得較好的效果，然而在大數(shù)據(jù)集上，因?yàn)镠-struct需要較多的空間來(lái)存儲(chǔ)，同時(shí)也需要較多的時(shí)間來(lái)處理H-struct上的所有節(jié)點(diǎn)。

文獻(xiàn)[125]也將經(jīng)典算法FP-Growth擴(kuò)展到不確定事務(wù)數(shù)據(jù)集，擴(kuò)展后的算法命名為UFP-Growth。UFP-Growth采用FP-Growth的方法創(chuàng)建了一棵同樣壓縮率的樹，但是創(chuàng)建的樹會(huì)丟失事務(wù)項(xiàng)集相應(yīng)的概率信息，所以UFP-Growth只是先從樹上產(chǎn)生候選項(xiàng)集，最后通過(guò)一遍原始數(shù)據(jù)集的掃描確認(rèn)真正的頻繁項(xiàng)集。

2011年，Lin等[109]提出一個(gè)新的不確定事務(wù)項(xiàng)集的頻繁項(xiàng)集挖掘算法CUFP-Mine。該算法是將事務(wù)項(xiàng)集壓縮到一個(gè)新的樹結(jié)構(gòu)CUFP-Tree上，一棵CUFP-Tree樹的創(chuàng)建需要掃描兩遍數(shù)據(jù)集：第一遍掃描是為創(chuàng)建一個(gè)有序的頻繁1-項(xiàng)集頭表；第二遍掃描中，將事務(wù)項(xiàng)集按頭表排序，同時(shí)刪除事務(wù)項(xiàng)集中的非頻繁項(xiàng)。假設(shè)項(xiàng)集Z（{Z1, Z2, …, Zi, …, Zm}）是有序，并且所有項(xiàng)都是頻繁的，則當(dāng)任一項(xiàng)Zi被添加到樹上時(shí)，在對(duì)應(yīng)節(jié)點(diǎn)上需要將Zi的所有超集（超集是由項(xiàng)Z1, Z2, …, Zi中的任意項(xiàng)組合的）及每個(gè)超集對(duì)應(yīng)的期望支持?jǐn)?shù)保存到該節(jié)點(diǎn)上。

CUFP-Mine的主要思想：所有的事務(wù)項(xiàng)集壓縮到樹上后，再統(tǒng)計(jì)相同節(jié)點(diǎn)上所有超集的總的期望支持?jǐn)?shù)，即可判斷哪些超集是頻繁的。CUFP-Mine的優(yōu)點(diǎn)是不需要遞歸的挖掘頻繁項(xiàng)集；在設(shè)定閾值較大的情況下，能夠較快地發(fā)現(xiàn)頻繁項(xiàng)集。該算法的主要缺點(diǎn)是需要較多的內(nèi)存來(lái)保存事務(wù)項(xiàng)集；另外，隨著數(shù)據(jù)集的變大和設(shè)定的最小期望支持?jǐn)?shù)變小，該算法很容易發(fā)生內(nèi)存溢出。

2．動(dòng)態(tài)數(shù)據(jù)流

針對(duì)不確定數(shù)據(jù)流中頻繁項(xiàng)集挖掘，已有的算法主要基于UF-Growth及滑動(dòng)窗口技術(shù)或時(shí)間衰減窗口技術(shù)[112-114,116,119,124]。

Leung等[119]提出兩個(gè)基于滑動(dòng)窗口的算法UF-streaming和SUF-Growth，每個(gè)滑動(dòng)窗口包含固定批數(shù)的數(shù)據(jù)，當(dāng)一個(gè)窗口滿了以后，每來(lái)一批數(shù)據(jù)，都會(huì)先從窗口中刪除一批最老的數(shù)據(jù)，然后再將新來(lái)數(shù)據(jù)添加到窗口中。

算法UF-streaming采用FP-streaming[86]的方法，預(yù)定義兩個(gè)最小期望支持?jǐn)?shù)preMinsup和minSup（preMinsup<minSup）, UF-streaming挖掘的頻繁項(xiàng)集的支持?jǐn)?shù)大于等于minSup，而支持?jǐn)?shù)介于preMinsup和minSup之間的項(xiàng)集稱為潛在頻繁項(xiàng)集，也會(huì)和頻繁項(xiàng)集一起保存到一棵樹UF-stream上。該算法利用UF-Growth挖掘每批數(shù)據(jù)中的支持?jǐn)?shù)大于等于preMinsup的項(xiàng)集作為候選項(xiàng)集，然后將每批數(shù)據(jù)中的候選項(xiàng)集保存到一個(gè)樹UF-stream上，UF-stream樹上每個(gè)節(jié)點(diǎn)記錄窗口中每批數(shù)據(jù)的支持?jǐn)?shù)（假設(shè)一個(gè)窗口中包含w批數(shù)據(jù)，則每個(gè)節(jié)點(diǎn)上需要記錄w個(gè)支持?jǐn)?shù)）；當(dāng)新來(lái)一批數(shù)據(jù)中的候選項(xiàng)集被添加到UF-stream樹上之前，會(huì)將樹上最老批次數(shù)據(jù)對(duì)應(yīng)的候選項(xiàng)集從樹上刪除；當(dāng)一個(gè)節(jié)點(diǎn)上總的支持?jǐn)?shù)（所有批上的支持?jǐn)?shù)的和）大于等于minSup，則該節(jié)點(diǎn)到根節(jié)點(diǎn)對(duì)應(yīng)的項(xiàng)集就是一個(gè)頻繁項(xiàng)集。該算法是一個(gè)近似的挖掘算法，會(huì)丟失一部分頻繁項(xiàng)集。

SUF-Growth算法主要基于算法UF-Growth，該算法將每批數(shù)據(jù)添加到樹UF-Tree的時(shí)候，節(jié)點(diǎn)分別記錄每批數(shù)據(jù)的支持?jǐn)?shù)（假設(shè)一個(gè)窗口中包含w批數(shù)據(jù)，則每個(gè)節(jié)點(diǎn)上需要記錄w個(gè)支持?jǐn)?shù)）；當(dāng)新來(lái)一批數(shù)據(jù)的時(shí)候，會(huì)首先將樹上最老批次的數(shù)據(jù)刪除；最老批次數(shù)據(jù)刪除之后，則將新來(lái)數(shù)據(jù)添加到樹上；挖掘頻繁項(xiàng)集的時(shí)候從該樹上讀取數(shù)據(jù)，采用模式增長(zhǎng)的方式挖掘頻繁項(xiàng)集。

文獻(xiàn)[113,114]中提出的算法采用的是時(shí)間衰減窗口模型，仍然采用UF-Tree來(lái)存儲(chǔ)窗口中的事務(wù)項(xiàng)集。由于UF-Tree共享同一個(gè)節(jié)點(diǎn)時(shí)，不僅要求項(xiàng)相同，還要求項(xiàng)對(duì)應(yīng)的概率值也相同，因此該樹結(jié)構(gòu)的存儲(chǔ)需要大量的空間，同時(shí)也需要較多的處理時(shí)間。

1.2.3 高效用項(xiàng)集挖掘算法的研究

傳統(tǒng)數(shù)據(jù)集中頻繁模式挖掘僅僅考慮了一個(gè)項(xiàng)集在多少個(gè)事務(wù)中出現(xiàn)，并沒(méi)有考慮項(xiàng)集中各項(xiàng)的重要度、利潤(rùn)、價(jià)格和數(shù)量等效用值相關(guān)的信息，而效用值可以度量項(xiàng)集的成本、利潤(rùn)值或其他重要度等信息。例如，在傳統(tǒng)數(shù)據(jù)集的購(gòu)物單中，只考慮一個(gè)購(gòu)物單中包含了哪些商品，而沒(méi)有考慮一個(gè)購(gòu)物單中每個(gè)商品的數(shù)量、價(jià)格或利潤(rùn)，然而在現(xiàn)實(shí)的很多應(yīng)用中，購(gòu)物單中商品的數(shù)量以及每種商品的單位利潤(rùn)都是很重要的。表1.3和表1.4是一個(gè)具有效用信息的數(shù)據(jù)集，該類數(shù)據(jù)中的高效用模式可以用來(lái)最大化一個(gè)企業(yè)的商業(yè)利潤(rùn)，這里稱此類數(shù)據(jù)為帶有效用的數(shù)據(jù)集。其中表1.3的前兩列是一個(gè)包含7個(gè)事務(wù)的事務(wù)數(shù)據(jù)集，表1.4是各事務(wù)項(xiàng)的單位利潤(rùn)（效用）值；表1.3中的第三列t u（Ti）給出了每個(gè)事務(wù)的總效用值，后面三列則分別是B、C、{BC}三個(gè)項(xiàng)集在每個(gè)事務(wù)上的效用值。下面給出靜態(tài)和動(dòng)態(tài)數(shù)據(jù)集上的高效用模式挖掘算法的研究現(xiàn)狀。

1．靜態(tài)數(shù)據(jù)集

表1.5列出了一些高效用模式挖掘的主要算法。2004年，Yao等[126]首先提出了高效用項(xiàng)集挖掘的相應(yīng)定義和數(shù)學(xué)模型：數(shù)據(jù)集Dut上一個(gè)項(xiàng)集X的效用值 u（X），被 定 義 為 X 在 所 有 事 務(wù) t 上 的 效 用 值 的 總 和，即，其中Dut是一個(gè)帶有效用值的數(shù)據(jù)集、u（X, t）是項(xiàng)集X在事務(wù)t上的效用；它是一個(gè)項(xiàng)集的總的利潤(rùn)（總的效用值），例如：“牛奶”+“面包”組合為所有的購(gòu)物記錄中所產(chǎn)生的利潤(rùn)的總和。高效用項(xiàng)集挖掘的目標(biāo)，就是找出效用值u（X）高出用戶預(yù)先設(shè)定的最小效用值的所有項(xiàng)集。

在文獻(xiàn)[126]中Yao等還提出一種挖掘算法，該算法首先估計(jì)項(xiàng)集效用的期望值，然后用估計(jì)的期望值來(lái)判斷一個(gè)項(xiàng)集是否是一個(gè)候選項(xiàng)集。但是，當(dāng)用戶設(shè)定的最小效用值比較低的時(shí)候，或者事務(wù)中包含比較多的事務(wù)項(xiàng)集的時(shí)候，該方法產(chǎn)生的候選項(xiàng)集個(gè)數(shù)接近于所有項(xiàng)的組合數(shù)。針對(duì)上述算法中產(chǎn)生大量候選項(xiàng)集的問(wèn)題，在2006年，他們又在文獻(xiàn)[127]中提出了兩個(gè)新的算法：UMining和UMining_H。UMining算法采用效用值上限的剪枝策略來(lái)降低候選項(xiàng)集個(gè)數(shù)，UMining_H算法采用啟發(fā)式的策略來(lái)降低候選項(xiàng)集的個(gè)數(shù)；同時(shí)這兩個(gè)算法會(huì)失去一些高效用項(xiàng)集，并且產(chǎn)生的候選項(xiàng)集個(gè)數(shù)還是比較多。

自Yao等提出高效用項(xiàng)集挖掘之后，高效用項(xiàng)集挖掘也成為一個(gè)研究熱點(diǎn)[126-140]。2005年，Liu等[128]提出了一個(gè)典型算法Two-Phase，同時(shí)作者還提出一個(gè)twu（transaction-weighted-utilization）模型，即一個(gè)項(xiàng)集的twu值不小于用戶設(shè)定的最小效用值，該項(xiàng)集就是一個(gè)候選項(xiàng)集。該模型同時(shí)也滿足向下封閉屬性，即如果一個(gè)項(xiàng)集的twu值不小于用戶設(shè)定的最小效用值，則該項(xiàng)集的任何非空子集的twu值也不小于用戶設(shè)定的最小效用值；如果一個(gè)項(xiàng)集的twu值小于用戶設(shè)定的最小效用值，則該項(xiàng)集的任何超集的twu值也小于用戶設(shè)定的最小效用值。Two-Phase算法主要分為兩步來(lái)完成：首先利用twu模型和Apriori算法，挖掘出所有的候選項(xiàng)集；再掃描一遍數(shù)據(jù)集來(lái)確定哪些候選項(xiàng)集是高效用項(xiàng)集。Two-Phase算法確實(shí)優(yōu)于文獻(xiàn)[126]中的方法，但是該算法包含了Apriori算法需要掃描多遍數(shù)據(jù)集的缺點(diǎn)；同時(shí)該方法也是通過(guò)候選項(xiàng)集來(lái)產(chǎn)生高效用項(xiàng)集，其時(shí)間效率仍然不是很理想。

為了解決已存在算法的低效率問(wèn)題，特別是挖掘稠密數(shù)據(jù)集時(shí)的低效率問(wèn)題，2007年，Erwin等[137]提出了一個(gè)基于樹結(jié)構(gòu)的高效用項(xiàng)集挖掘算法CTU-Mine。然而，該算法只是在挖掘稠密數(shù)據(jù)集或用戶設(shè)定的最小效用值比較低的時(shí)候，性能才優(yōu)于Two-Phase算法。

2008年，Li等[135]針對(duì)Two-Phase算法中產(chǎn)生過(guò)多候選項(xiàng)集的問(wèn)題，提出了降低候選項(xiàng)集的策略IIDS（Isolated Items Discarding Strategy），并將提出的策略應(yīng)用到已存在的層次挖掘算法中，分別得到兩個(gè)新的算法FUM和DCG+。這兩個(gè)算法都優(yōu)于它們?cè)瓉?lái)的算法，但是這兩個(gè)算法還是存在同樣的問(wèn)題：通過(guò)候選項(xiàng)集來(lái)挖掘高效用項(xiàng)集。2007年，Hu等[136]還提出一個(gè)近似的方法來(lái)挖掘高效用項(xiàng)集；2011年，Lin等[134]提出一個(gè)新算法HUP-Growth，該算法首先通過(guò)兩遍數(shù)據(jù)集掃描，將事務(wù)項(xiàng)集維護(hù)在一棵類FP-Tree的樹上，處理樹上每一項(xiàng)的時(shí)候，需要產(chǎn)生包含該項(xiàng)的所有項(xiàng)集，同時(shí)需要計(jì)算這些項(xiàng)集的效用值，即可以從中確認(rèn)真實(shí)的高效用項(xiàng)集；該算法的計(jì)算量比較大，但是該算法的時(shí)間效率優(yōu)于算法Two-Phase。

以上提出的算法基本上都是通過(guò)多遍掃描數(shù)據(jù)集來(lái)產(chǎn)生候選項(xiàng)集；2009年，Ahmed等[132]提出一個(gè)不需要多次掃描數(shù)據(jù)集的算法IHUP。算法IHUP先將事務(wù)項(xiàng)集及效用信息存儲(chǔ)在一棵IHUP-Tree上，這里以表1.3和表1.4的數(shù)據(jù)為例來(lái)描述算法IHUP，最小效用值（記為minUti）設(shè)為70。

該算法首先掃描一遍數(shù)據(jù)集，計(jì)算各項(xiàng)的twu值，刪除twu值小于70的項(xiàng)，然后將剩余的項(xiàng)按twu值大小的逆序排序，如圖1.3中左邊的頭表。創(chuàng)建好頭表后，接下來(lái)就可以創(chuàng)建樹，首先將事務(wù)項(xiàng)集按頭表中項(xiàng)的順序排序，同時(shí)刪除不在頭表中的項(xiàng)，計(jì)算修改后的事務(wù)項(xiàng)集的twu值，再將有序的項(xiàng)集添加到樹上，同時(shí)將新計(jì)算到的twu值累加到該項(xiàng)集在樹中的所有節(jié)點(diǎn)上。表1.3和表1.4中數(shù)據(jù)所對(duì)應(yīng)的IHUP-Tree如圖1.3所示。創(chuàng)建完樹后，采用模式增長(zhǎng)的方式從樹上產(chǎn)生候選項(xiàng)集；最后再掃描一遍數(shù)據(jù)集從候選項(xiàng)集中識(shí)別出高效用項(xiàng)集。該算法的挖掘效率相對(duì)于已有的算法有很大的提高。

Tseng等在文獻(xiàn)[130,131]中對(duì)算法IHUP進(jìn)行改進(jìn)，主要是針對(duì)建樹方法的改進(jìn)，進(jìn)而得到算法UP-Growth。Tseng等考慮到處理樹上每個(gè)節(jié)點(diǎn)的時(shí)候，子孫節(jié)點(diǎn)不再參與當(dāng)前節(jié)點(diǎn)的處理過(guò)程，因此Tseng等人在將一個(gè)準(zhǔn)備好的項(xiàng)集添加到樹上，并在處理該項(xiàng)集中每一項(xiàng)的時(shí)候，只將該項(xiàng)及祖先項(xiàng)的效用值的和累加到該項(xiàng)在樹上對(duì)應(yīng)的節(jié)點(diǎn)上，如圖1.4所示，當(dāng)表1.3中第二個(gè)事務(wù)（B,2）（C,2）（E,1）（G,4）被添加到樹上的時(shí)候，首先被處理的項(xiàng)集為“C:2, E:3, B:6”（其中的數(shù)值為各項(xiàng)在該事務(wù)中的效用值），當(dāng)各項(xiàng)被添加到樹上的時(shí)候，如項(xiàng)E對(duì)應(yīng)的節(jié)點(diǎn)只將項(xiàng)C和E的效用值累加到該節(jié)點(diǎn)效用值上，項(xiàng)B對(duì)應(yīng)的節(jié)點(diǎn)將這三項(xiàng)的效用值都累加到該節(jié)點(diǎn)效用值上，如圖1.4的路徑root-C-E-B所示。對(duì)比圖1.3和圖1.4，會(huì)發(fā)現(xiàn)后者樹上很多節(jié)點(diǎn)的效用值降低了很多，從而在創(chuàng)建條件子樹的時(shí)候，會(huì)有很多項(xiàng)排除在條件子樹之外，即條件子樹中節(jié)點(diǎn)也會(huì)減少，因此UP-Growth算法的效率比IHUP算法提高了很多。

算法D2HUP[141]采用項(xiàng)集枚舉的方法挖掘高效用項(xiàng)集，該算法主要通過(guò)剪枝策略提高挖掘的時(shí)間效率，但是需要大量的空間來(lái)維護(hù)枚舉樹和事務(wù)項(xiàng)集。HUI-Miner[133]同Apriori算法采用層次方式產(chǎn)生高效用項(xiàng)集，每層中需要產(chǎn)生大量的項(xiàng)集，并計(jì)算每個(gè)項(xiàng)集的效用值；同時(shí)還需要維護(hù)每個(gè)項(xiàng)集所在事務(wù)ID、相應(yīng)事務(wù)中的效用值和事務(wù)中其余項(xiàng)的效用值信息，因此該算法空間消耗較大。

2．動(dòng)態(tài)數(shù)據(jù)流

Tseng等[138,139]提出了第一個(gè)數(shù)據(jù)流中高效用項(xiàng)集挖掘算法THUI，該算法整合了Two-Phase算法和滑動(dòng)窗口的方式來(lái)挖掘數(shù)據(jù)流上的高效用項(xiàng)集，每個(gè)窗口中有固定批數(shù)的數(shù)據(jù)，每批數(shù)據(jù)又有固定個(gè)數(shù)的事務(wù)項(xiàng)集。該算法首先挖掘出窗口的第一批數(shù)據(jù)中的候選2項(xiàng)集，當(dāng)?shù)诙鷶?shù)據(jù)到來(lái)的時(shí)候，再挖掘出前二批數(shù)據(jù)中的候選2項(xiàng)集，依次挖掘出整個(gè)窗口中的候選2項(xiàng)集，用所有的候選2項(xiàng)集再產(chǎn)生全部的候選項(xiàng)集，最后還需要再掃描一遍數(shù)據(jù)集從候選項(xiàng)集中確認(rèn)高效用項(xiàng)集。維護(hù)候選2項(xiàng)集的時(shí)候，還將每個(gè)候選項(xiàng)集產(chǎn)生的開(kāi)始批次保存下來(lái)，當(dāng)刪除老數(shù)據(jù)的時(shí)候，只將候選項(xiàng)集的twu值減去該項(xiàng)集在最老批次數(shù)據(jù)中的twu值，同時(shí)將修改項(xiàng)集的開(kāi)始批次增加1；當(dāng)新來(lái)數(shù)據(jù)的時(shí)候，修改當(dāng)前維護(hù)的候選項(xiàng)集的twu值，同時(shí)將新來(lái)批數(shù)據(jù)中新產(chǎn)生的候選項(xiàng)集添加到維護(hù)的候選項(xiàng)集集合中。該算法是一個(gè)近似算法，它的主要問(wèn)題是需要產(chǎn)生并維護(hù)候選項(xiàng)集，并且還需要掃描數(shù)據(jù)集來(lái)統(tǒng)計(jì)每個(gè)候選項(xiàng)集的效用值，甚至有時(shí)候會(huì)產(chǎn)生大量的候選項(xiàng)集。

Li等[129]提出兩個(gè)基于滑動(dòng)窗口的算法：MHUI-BIT和MHUI-TID，這兩個(gè)算法都采用類Apriori算法的特點(diǎn)逐層產(chǎn)生所有的候選項(xiàng)集，然后再掃描數(shù)據(jù)集來(lái)統(tǒng)計(jì)候選項(xiàng)集的效用值。算法MHUI-BIT和MHUI-TID分別采用bit-vector和TID-lists兩個(gè)結(jié)構(gòu)來(lái)存儲(chǔ)當(dāng)前窗口中每批數(shù)據(jù)，利用這兩個(gè)結(jié)構(gòu)能檢索到與候選項(xiàng)集相關(guān)的事務(wù)，從而可以快速地統(tǒng)計(jì)候選項(xiàng)集的效用值，實(shí)驗(yàn)結(jié)果也驗(yàn)證了這兩個(gè)算法的時(shí)間效率優(yōu)于算法THUI。

2010年，Ahmed等[140]提出一個(gè)仍然基于滑動(dòng)窗口的算法HUPMS，該算法采用樹結(jié)構(gòu)來(lái)維護(hù)窗口中每批數(shù)據(jù)的事務(wù)項(xiàng)集，通過(guò)一遍數(shù)據(jù)集掃描，將窗口中的事務(wù)項(xiàng)集維護(hù)在一棵樹上，當(dāng)新來(lái)一批數(shù)據(jù)的時(shí)候，先將最老數(shù)據(jù)從樹上刪除，再將新的數(shù)據(jù)添加到樹上；當(dāng)需要挖掘窗口中的高效用項(xiàng)集的時(shí)候，采用模式增長(zhǎng)的方式從樹上挖掘出所有的候選項(xiàng)集；最后再掃描一次數(shù)據(jù)集來(lái)統(tǒng)計(jì)所有候選項(xiàng)集的效用值。該算法相對(duì)算法MHUI-BIT和MHUI-TID，可以有效地減少候選項(xiàng)集的個(gè)數(shù)，實(shí)驗(yàn)也驗(yàn)證了該算法有比較好的時(shí)間性能。

1.2.4 大數(shù)據(jù)集下的頻繁模式挖掘研究

目前，針對(duì)大數(shù)據(jù)環(huán)境下的數(shù)據(jù)流頻繁模式挖掘算法研究比較少，主要集中在靜態(tài)的大數(shù)據(jù)中研究。PFP[142]是一個(gè)基于MapReduce的FP-Growth算法的實(shí)現(xiàn)，該算法需要兩次MapReduce。首先，PFP算法利用MapReduce建立一個(gè)頭表。第二次MapReduce，在Map過(guò)程中，每個(gè)事務(wù)項(xiàng)集都按頭表的順序排序，并且刪除事務(wù)項(xiàng)集中不頻繁的項(xiàng)，將有序事務(wù)項(xiàng)集中每項(xiàng)之前的項(xiàng)集（稱為子事務(wù)項(xiàng)集）作為value值，該項(xiàng)作為key值輸出，即如果一個(gè)事務(wù)項(xiàng)集中包含k項(xiàng)，則該事務(wù)項(xiàng)集會(huì)產(chǎn)生（k-1）個(gè)（key, value）鍵值對(duì)，即一個(gè)事務(wù)項(xiàng)集被分配給全局頭表中多項(xiàng)來(lái)創(chuàng)建子樹；在Reduce過(guò)程中，采用FP-Growth算法挖掘各項(xiàng)對(duì)應(yīng)的子事務(wù)項(xiàng)集中的頻繁項(xiàng)集。PFP算法的最大缺點(diǎn)是不能將數(shù)據(jù)均勻分配給各個(gè)節(jié)點(diǎn)，有的節(jié)點(diǎn)上數(shù)據(jù)量會(huì)很大，因此會(huì)影響到整體的時(shí)間效率。文獻(xiàn)[143]針對(duì)云制造環(huán)境下數(shù)據(jù)挖掘的需求，提出了一種新的利用鍵值存儲(chǔ)系統(tǒng)優(yōu)化PFP-Growth算法。

Apriori算法的MapReduce實(shí)現(xiàn)的研究比較多，文獻(xiàn)[144-151]中的算法都是基于MapReduce的Apriori實(shí)現(xiàn)的研究。已存在的基于Apriori的算法主要采用多次MapReduce來(lái)實(shí)現(xiàn)Apriori算法的并行算法，如果數(shù)據(jù)集中存在最大長(zhǎng)度是k的頻繁項(xiàng)集，則需要最少k次MapReduce。首先MapReduce一遍數(shù)據(jù)集產(chǎn)生頻繁1-項(xiàng)集；然后用頻繁1-項(xiàng)集組合產(chǎn)生候選2-項(xiàng)集，將候選2-項(xiàng)集分配到各個(gè)節(jié)點(diǎn)上，進(jìn)行第二次MapReduce掃描數(shù)據(jù)集，統(tǒng)計(jì)各個(gè)候選項(xiàng)集在各個(gè)節(jié)點(diǎn)上支持?jǐn)?shù)，在Reduce過(guò)程中再統(tǒng)計(jì)各個(gè)候選項(xiàng)集在全部數(shù)據(jù)集上的支持?jǐn)?shù)，即可發(fā)現(xiàn)頻繁2-項(xiàng)集；繼續(xù)產(chǎn)生候選k-項(xiàng)集，進(jìn)行k次MapReduce掃描數(shù)據(jù)集，從中發(fā)現(xiàn)頻繁k項(xiàng)集（k≥3）。文獻(xiàn)[151]中還提出三個(gè)算法FPC和DPC和SPC:FPC在每次迭代過(guò)程中，產(chǎn)生固定層次的候選項(xiàng)集，如產(chǎn)生k+1, k+2, …, k+l的候選項(xiàng)集（l為某一固定值）；而算法DPC是對(duì)FPC的一個(gè)改進(jìn)，在每次的迭代過(guò)程中，將FPC中的l變?yōu)橐粍?dòng)態(tài)值；算法SPC[151]是每次迭代中只產(chǎn)生一層候選項(xiàng)集。通過(guò)實(shí)驗(yàn)分析，發(fā)現(xiàn)算法SPC和FPC的時(shí)間性能比較好，并且兩算法的時(shí)間性能也比較接近，但是算法FPC在每次迭代中會(huì)產(chǎn)生過(guò)多候選項(xiàng)集，內(nèi)存需求會(huì)比較多。

文獻(xiàn)[147]提出了基于MapReduce的Apriori算法近似頻繁項(xiàng)集挖掘算法PSON，通過(guò)兩次MapReduce（第一次是挖掘每個(gè)節(jié)點(diǎn)上的局部頻繁項(xiàng)集，然后合并所有節(jié)點(diǎn)上的局部頻繁項(xiàng)集作為候選項(xiàng)集；第二次MapReduce，再掃描一遍數(shù)據(jù)集統(tǒng)計(jì)所有候選項(xiàng)集的支持?jǐn)?shù)），即可從候選項(xiàng)集中發(fā)現(xiàn)所有支持?jǐn)?shù)大于等于設(shè)定的最小支持?jǐn)?shù)的頻繁項(xiàng)集。該算法的問(wèn)題就是輸出的是<key,1>鍵值對(duì)，并且該算法挖掘的結(jié)果中會(huì)丟失部分頻繁項(xiàng)集。