不確定數(shù)據(jù)流高效用頻繁模式挖掘研究(論文)綜述

1、項(xiàng)目名稱不確定數(shù)據(jù)流高效用頻繁模式挖掘研究項(xiàng)目負(fù)責(zé)人（簽名）所在學(xué)校（蓋章）1本項(xiàng)目研究意義及國內(nèi)外同類研究工作現(xiàn)狀（附主要參考文獻(xiàn)及出處）：研究意義：本課題將“高效用頻繁模式”的概念，及“跨數(shù)據(jù)流”和“跨事務(wù)”的組合模式概念拓展到不確定數(shù)據(jù)流領(lǐng)域，提出在多重不確定數(shù)據(jù)流上進(jìn)行模式挖掘建模及算法研究的計(jì)算框架；其算法實(shí)現(xiàn)（作為開源軟件發(fā)布）也可為數(shù)據(jù)分析行業(yè)的頻繁模式挖掘提供計(jì)算工具。研究背景、現(xiàn)狀和動機(jī)：頻繁模式 以事件發(fā)生的頻度為依據(jù)，揭示數(shù)據(jù)表象所可能隱含的規(guī)律。例如，從金融數(shù)據(jù)流中識別出的頻繁模式可用于發(fā)現(xiàn)可疑交易線索，醫(yī)療圖像中的頻繁模式可用于病灶的識別和分類等。 隨著社會行業(yè)對數(shù)據(jù)

2、分析技術(shù)的需求演進(jìn)，頻繁模式挖掘的數(shù)據(jù)對象也從確定性數(shù)據(jù)、布爾型事件（事件發(fā)生與否）拓展到不確定數(shù)據(jù)（ uncertain data）和包含效用（ utility）的數(shù)據(jù) 。數(shù)據(jù)的不確定性來源于數(shù)據(jù)產(chǎn)生、收集、存儲和傳輸過程中的隨機(jī)性因素、預(yù)處理中的統(tǒng)計(jì)計(jì)算、或數(shù)據(jù)概念本身的概率屬性等；例如，根據(jù)對電子商務(wù)網(wǎng)站頁面的訪問記錄，只能獲得潛在客戶對特定商品購買傾向的一個估計(jì)，即一個概率性指標(biāo)。數(shù)據(jù)的“效用”值表示該數(shù)據(jù)的利潤或重要度；例如購物單中商品的單價和數(shù)量等。由于數(shù)據(jù)的不確定性和數(shù)據(jù)的效用屬性普遍存在于現(xiàn)實(shí)世界各個領(lǐng)域中，因此近年來高效用模式（ high utility pattern ）挖

3、掘和不確定數(shù)據(jù)頻繁模式挖掘等研究逐漸成為數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)之一。但是，目前不確定數(shù)據(jù)集上的頻繁模式挖掘，僅僅考慮了模式的期望支持?jǐn)?shù)，而沒有考慮到模式的效用值；同時缺乏對多數(shù)據(jù)流及模式的時間關(guān)聯(lián)的綜合考慮，難以滿足數(shù)據(jù)分析行業(yè)的計(jì)算需求：首先，在許多領(lǐng)域應(yīng)用中，事件的“效用” （即收益，數(shù)值型屬性）可能具有不確定性。例如，根據(jù)特定的投資策略對金融歷史數(shù)據(jù)進(jìn)行回測時，由于高頻數(shù)據(jù)的隨機(jī)波動性，預(yù)定的成交時間和成交價格不可能被精確實(shí)現(xiàn)，實(shí)現(xiàn)的收益也是一個不確定數(shù)據(jù)。因此，效用概念的建模應(yīng)該導(dǎo)入不確定性，以適應(yīng)此類計(jì)算需求。其次，隨著大數(shù)據(jù)應(yīng)用的發(fā)展，特別是互聯(lián)網(wǎng)、物聯(lián)網(wǎng)的海量數(shù)據(jù)流和金融領(lǐng)域的高

4、頻數(shù)據(jù)的迅猛發(fā)展，數(shù)據(jù)流的綜合分析已經(jīng)成為大數(shù)據(jù)研究的關(guān)注點(diǎn)之一，因?yàn)閷Χ鄠€相互間有內(nèi)在關(guān)聯(lián)的數(shù)據(jù)流的綜合分析（即“跨流”分析） ，比僅僅分析單個數(shù)據(jù)流，更容易發(fā)現(xiàn)事物潛在的規(guī)律和模式。例如，綜合大氣溫度、云層分布、風(fēng)力變化等數(shù)據(jù)，對于估計(jì)未來颶風(fēng)的形成，要比單獨(dú)依賴一個因素更為可靠；根據(jù)多只股票的交易數(shù)據(jù)，結(jié)合社會和企業(yè)的經(jīng)濟(jì)狀況，及各事件在時間上的先后關(guān)系（即“跨事務(wù)”關(guān)聯(lián)）等信息，來尋找市場的發(fā)展趨勢，比單純考察一只股票的數(shù)據(jù)更為合理。因此，應(yīng)考慮在多重數(shù)據(jù)流上、并考慮到模式之間的時間關(guān)聯(lián)進(jìn)行模式挖掘的建模研究。綜上所述， 頻繁模式挖掘領(lǐng)域的科學(xué)研究，其發(fā)展趨勢，應(yīng)將研究對象拓展到包含效

5、用信息的多個不確定數(shù)據(jù)流上，研究其高效用頻繁模式挖掘的相關(guān)模型及算法。此研究有著強(qiáng)烈的社會需求背景，其成果可廣泛應(yīng)用于金融業(yè)、商業(yè)、制造業(yè)、氣象、環(huán)境、醫(yī)療乃至社會人文統(tǒng)計(jì)等各個領(lǐng)域。國內(nèi)外研究現(xiàn)狀分析：傳統(tǒng)的頻繁模式挖掘處理的是確定性的非數(shù)值型數(shù)據(jù)（“字面”數(shù)據(jù)） ，其典型算法包括Apriori 1、FP-Growth 2和 H-Mine 3 等。隨著不確定數(shù)據(jù)的迅速發(fā)展和業(yè)界對事務(wù)項(xiàng)效用值的重視，近年來， 高效用模式挖掘和不確定數(shù)據(jù)上的頻繁模式挖掘成為數(shù)據(jù)挖掘領(lǐng)域的熱點(diǎn)之一，在 KDD 、ICDM、PAKDD 、 ICDE 等重要會議和數(shù)據(jù)挖掘領(lǐng)域頂級期刊TKDE 等上也多有關(guān)注（參見表2

6、 和表 3）。目前，模式挖掘研究主要集中于單個數(shù)據(jù)集或數(shù)據(jù)流；下面分別介紹不確定數(shù)據(jù)集上頻繁模式挖掘、高效用模式挖掘、多重數(shù)據(jù)流及跨事務(wù)（事務(wù)間）模式挖掘，和模式挖掘并行算法的研究現(xiàn)狀。(1) 不確定數(shù)據(jù)中頻繁模式挖掘不確定數(shù)據(jù)是帶有概率屬性的數(shù)據(jù)；如表1 所示，不確定數(shù)據(jù)集中的每個事務(wù)項(xiàng)，都包含一個概率值，表示該事務(wù)項(xiàng)發(fā)生的概率。表 1一個不確定數(shù)據(jù)集的 例事 ID事 集t1(a: 0.8), (b: 0.7)(d: 0.9), (f: 0.5)t2(c: 0.8), (d: 0.85), (e: 0.4)t3(c: 0.85), (d: 0.6), (e: 0.6)不 確 定 數(shù) 據(jù) 集D

7、中 的 頻 繁 模 式X用 其 期望支持?jǐn)?shù) 描 述 ， 該 期望支持?jǐn)?shù) 定 義 為SC1 C2 C3SC1C2 C3SS1S2S3C1 C2C3數(shù)據(jù)流數(shù)據(jù)流數(shù)據(jù)流|0.34|0.6|0.8|1，其中 t 是事務(wù)， P(X, t)根據(jù)獨(dú)立同分布原則由X 中的所有事務(wù)項(xiàng)在事務(wù) t(a)界標(biāo)窗口模型(b)時間衰減窗口模型(c)滑動窗口模型|0.34|0.6|0.8|1|0.34|0.6|0.8|1S:數(shù)據(jù)流中指定的起點(diǎn); C1,C2,C3:分別為 3個不同的處理點(diǎn); S1,S2,S3:分別為 3個不同的起點(diǎn).中的概率的乘積給出。不 確 定 數(shù) 據(jù) 集 上 的 頻 繁 模 式 挖 掘 算 法 主 要

8、分 為 逐 層 挖 掘 (level-wise) 和 模 式 增 長(pattern-growth) 兩種方式，分別基于Apriori 和 FP-Growth 算法。(1.1) 靜態(tài)不確定數(shù)據(jù)集上的頻繁模式挖掘研究現(xiàn)狀表 2 列出了靜態(tài)數(shù)據(jù)集上的一些重要算法及其特征。其中，采用逐層挖掘的算法需要多次掃描數(shù)據(jù)集，并產(chǎn)生大量的候選項(xiàng)集來挖掘頻繁模式；該類算法的優(yōu)化主要是通過減少候選項(xiàng)集個數(shù)來提高算法效率。表 2 不確定數(shù)據(jù)集上的 繁模式挖掘的主要算法（ * 號者 本 的成果）時間研究者 文出 算法名稱方法2007Chui C KPAKDD 2007U-Apriori 4 level-wise,Ka

9、o Bcandidate-testLeung C2007S, Carmichael C L,ICDM Workshops 2007UF-Growth 5 pattern-growthHao B2009Aggarwal C C, Li YKDD 2009HU-Mine 6pattern-growth200KDD 20pattern-growth,Aggarwal C C, Li YUFP-Mine 6 candidate-te9t近似 /精確精確精確精確精確2011Wang L, Cheung D,IEEE TKDEMBP 7level-wise,Cheng Rcandidate-test201

10、2Sun X, Liu LJournal of AdvancementsIMBP 8 *level-wise,Wang Shin Computing Technologycandidate-test2012Lin C W, Hong T PExpert Systems withCUFP-Mine 9 candidate-testApplications2013Wang L, Feng LJournal of ComputersAT-Mine 10*pattern-growth精確近似精確精確模式增長方式的算法則需要遞歸地進(jìn)行子樹的創(chuàng)建。UF-Growth 的主要缺陷是不能將數(shù)據(jù)高效的壓縮到一棵

11、樹上，從而造成維護(hù)數(shù)據(jù)集的樹比較大，算法的挖掘效率受到影響。UFP-Mine將數(shù)據(jù)集高效的壓縮到樹上，但是壓縮的時候，丟失了事務(wù)項(xiàng)集的概率信息，因此只能從樹上得到候選項(xiàng)集，最后還需要掃描一遍數(shù)據(jù)集來計(jì)算候選項(xiàng)集的期望支持?jǐn)?shù)。CUFP-Mine 的優(yōu)點(diǎn)是不需要遞歸的挖掘頻繁模式；在設(shè)定閾值較大的情況下，能夠較快的發(fā)現(xiàn)頻繁模式；其缺點(diǎn)是內(nèi)存開銷較大。 本課題申請者 等提出算法 AT-Mine ，該算法將數(shù)據(jù)集以較大的壓縮比維護(hù)在一棵樹上，同時沒有丟失事務(wù)項(xiàng)集的概率信息，最終算法的挖掘效率得到了較大的提高。(1.2) 不確定數(shù)據(jù)流上的頻繁模式挖掘研究現(xiàn)狀數(shù)據(jù)流上的頻繁模式概念，仍然定義在單個事務(wù)上，

12、不考慮跨事務(wù)的模式（不同時間上的組合模式）；其挖掘方法，一般是采用“窗口”獲取當(dāng)前用戶關(guān)注的數(shù)據(jù)，然后基于已有的靜態(tài)數(shù)據(jù)集上的頻繁模式挖掘算法，設(shè)計(jì)數(shù)據(jù)流中被關(guān)注數(shù)據(jù)上的挖掘算法。目前有3 種典型的窗口模型 11 ：界標(biāo)窗口模型 (Landmark WindowModel) 、時間衰減窗口模型(Damped WindowModel) 和滑動窗口模型 (Sliding Window Model)，如圖 1 所示。SC1 C2 C3SC1 C2 C3S S1S2 S3C1 C2 C3數(shù)據(jù)流數(shù)據(jù)流數(shù)據(jù)流 |0.34|0.6|0.8|1 |0.34|0.6|0.8|1|0.34|0.6|0.8|1(a

13、)界標(biāo)窗口模型(b)時間衰減窗口模型(c)滑動窗口模型S: 數(shù)據(jù)流中指定的起點(diǎn); C1,C2,C3:分別為 3個不同的處理點(diǎn); S1,S2,S3:分別為 3個不同的起點(diǎn).圖1三種窗口模型界標(biāo)窗口模型中的窗口指特定一時間點(diǎn)（或數(shù)據(jù)流中一條特定的數(shù)據(jù)）到當(dāng)前時間（或當(dāng)前條數(shù)據(jù)）之間的數(shù)據(jù)，如圖1(a)所示，在C1、C2 和 C3 時刻，窗口中的數(shù)據(jù)分別包含了從S點(diǎn)到 C1 點(diǎn)、 C2 點(diǎn)和 C3 點(diǎn)之間的數(shù)據(jù)。時間衰減窗口模型和界標(biāo)窗口模型所包含的數(shù)據(jù)是相同的，只是衰減窗口中的每條數(shù)據(jù)有不同的權(quán)重，距離當(dāng)前時間越近，數(shù)據(jù)的權(quán)重越大，如圖1(b)所示；實(shí)際上，時間衰減窗口模型是界標(biāo)窗口模型的一個特例

14、。滑動窗口模型中，每次處理數(shù)據(jù)的個數(shù)固定或者是每次處理數(shù)據(jù)的時間段長度是固定的，如圖1(c) 所示。已有的不確定數(shù)據(jù)流上頻繁模式挖掘算法主要基于UF-Growth 及滑動窗口技術(shù)或時間衰減窗口技術(shù)構(gòu)造。Leung 等作者 12 提出兩個基于滑動窗口的算法 UF-streaming 和 SUF-Growth ，每個滑動窗口包含固定批數(shù)的數(shù)據(jù)，當(dāng)一個窗口滿了以后，每來一批數(shù)據(jù)，都會先從窗口中刪除一批最老的數(shù)據(jù)，然后再將新來數(shù)據(jù)添加到窗口中。算法 UF-streaming 采用 FP-streaming 13的方法， 預(yù)定義兩個最小期望支持?jǐn)?shù)preMinsup 和minSup (preMinsup

15、minSup)，UF-streaming 挖掘的頻繁模式的支持?jǐn)?shù)大于等于minSup，而支持?jǐn)?shù)介于 preMinsup 和 minSup 之間的項(xiàng)集稱為潛在頻繁模式，也會和頻繁模式一起保存到一棵樹UF-stream 上。該算法利用UF-Growth挖掘每批數(shù)據(jù)中的期望支持?jǐn)?shù)大于等于preMinsup 的項(xiàng)集做為候選項(xiàng)集，并保存到一個樹UF-stream 上， UF-stream 樹上每個節(jié)點(diǎn)記錄窗口中每批數(shù)據(jù)的期望支持?jǐn)?shù)；當(dāng)新來一批數(shù)據(jù)中的候選項(xiàng)集被添加到UF-stream 樹上之前，會將樹上最老批次數(shù)據(jù)對應(yīng)的候選項(xiàng)集從樹上刪除；當(dāng)一個節(jié)點(diǎn)上總的期望支持?jǐn)?shù)(所有批上的期望支持?jǐn)?shù)的和 ) 大于等

16、于 minSup，則該節(jié)點(diǎn)到根節(jié)點(diǎn)對應(yīng)的項(xiàng)集就是一個頻繁模式。該算法是一個近似的挖掘算法，會丟失一部分頻繁模式。SUF-Growth 算法主要基于算法 UF-Growth ，該算法將每批數(shù)據(jù)添加到樹 UF-Tree 的時候，節(jié)點(diǎn)分別記錄每批數(shù)據(jù)的期望支持?jǐn)?shù)；當(dāng)新來一批數(shù)據(jù)的時候，會首先將樹上最老批次的數(shù)據(jù)刪除，然后將新來數(shù)據(jù)添加到樹上；挖掘頻繁模式的時候從該樹上讀取數(shù)據(jù)，采用模式增長的方式進(jìn)行。文獻(xiàn) 14, 15 中提出的算法采用的是時間衰減窗口模型，仍然采用UF-Tree 來存儲窗口中的事務(wù)項(xiàng)集。 由于 UF-Tree 共享同一個節(jié)點(diǎn)時， 不僅要求項(xiàng)相同， 還要求項(xiàng)對應(yīng)的概率值也相同，因此該

17、樹結(jié)構(gòu)的存儲需要大量的空間，同時也需要較多的處理時間。本課題申請者等在文獻(xiàn) 16 中采用滑動窗口方式（模型），在算法 AT-Mine 的基礎(chǔ)上，給出一個不確定數(shù)據(jù)流上的頻繁模式挖掘算法UDS-FIM ；該算法給出兩種新的樹結(jié)構(gòu)分別來維護(hù)窗口中數(shù)據(jù)和挖掘過程中的子數(shù)據(jù)集，并保證挖掘過程中事務(wù)項(xiàng)集的信息不會丟失；最終使數(shù)據(jù)流上的頻繁模式挖掘算法的時空效率得到較大的提升。綜上所述， 目前的不確定數(shù)據(jù)流上的模式挖掘研究，尚有 3 個方面的問題沒有解決： 沒有考慮事務(wù)項(xiàng)的“效用值”（參見下節(jié)的闡述） 。局限在“事務(wù)內(nèi)”的模式挖掘，沒有考慮“跨事務(wù)” 的模式 （即來源于不同時間、不同事務(wù)的組合模式） 。

18、沒有考慮多重數(shù)據(jù)流問題；但多重數(shù)據(jù)流上的“跨流”模式具有重要的現(xiàn)實(shí)意義，因?yàn)樗蔷C合考察異構(gòu)數(shù)據(jù)流和多因素關(guān)聯(lián)的基礎(chǔ)。據(jù)此，在不確定數(shù)據(jù)流模式挖掘研究中，包含“效用”數(shù)據(jù)、建立“跨流”和“跨事務(wù)”模式，是此領(lǐng)域發(fā)展的必然趨勢。此為本課題的研究動機(jī)之一。(2) 高效用模式挖掘研究現(xiàn)狀2004 年， Yao 等首先提出了高效用模式挖掘的相應(yīng)定義和數(shù)學(xué)模型17 ：數(shù)據(jù)集 D 上一個項(xiàng) 集X的 效 用 值u(X) ， 被 定 義 為X 在 所 有 事 務(wù) t上 的 效 用 值 的 總 和 ， 即研究多重不確多重具有效用數(shù)據(jù)實(shí)驗(yàn)對定數(shù)據(jù)流多重具有效用值值的數(shù)據(jù)流高頻金融數(shù)據(jù)象）的不確定數(shù)據(jù)流）和電子商務(wù)

19、數(shù)（據(jù)，服務(wù)于：，其中 D 是一個帶有效用值的數(shù)據(jù)集、u(X, t)是項(xiàng)集 X 在事務(wù) t 上的線（線研路多重不確定數(shù)據(jù)路模式挖掘線的高效用模式挖掘1.樣本數(shù)據(jù)概念頻繁模式路高效用模式2.預(yù)處理實(shí)驗(yàn)?zāi)?.算法驗(yàn)證型高效用頻繁模式4.算法分析5.并行設(shè)計(jì)算6.模型修正多重不確定數(shù)多重數(shù)據(jù)流中7.應(yīng)用探索法據(jù)流中的頻繁究流中的高效用頻繁模式挖掘效用；它是一個項(xiàng)集的總利潤，例如：“牛奶” +“面包”組合在所有的購物記錄中所產(chǎn)生的利潤的總和，即為該模式的總效用值。高效用模式挖掘的目標(biāo)，就是找出效用值u( X)不小于用戶預(yù)先設(shè)定的最小效用值的所有項(xiàng)集。隨著行業(yè)對定量數(shù)據(jù)日益重視，高效用模式挖掘也成為數(shù)據(jù)

20、挖掘研究的一個熱點(diǎn)。下面就靜態(tài)數(shù)據(jù)和數(shù)據(jù)流兩種數(shù)據(jù)對象上的研究現(xiàn)狀進(jìn)行簡要介紹。(2.1) 靜態(tài)數(shù)據(jù)集上高效用模式挖掘研究現(xiàn)狀表 3 是靜態(tài)數(shù)據(jù)集上高效用模式挖掘的主要算法的一個簡要總結(jié)。表3 高效用模式挖掘的主要算法時研究者論文出處方法間2004Yao H, Hamilton HICDM 2004采用高估項(xiàng)集效用值的辦法來首J, et al.先挖掘候選項(xiàng)集，再從中識別高效用模式 17 。2005Liu Y , Liao W, et al.Advances in首先提出 twu 模型來計(jì)算候選項(xiàng)Knowledge集的高估值；然后給出一個層次Discovery and的挖掘算法 Two-Phas

21、e18 。Data Mining2006Yao H, Hamilton HData &UMining 19 ：采用效用值上限的.Knowledge剪枝策略來降低候選項(xiàng)集個數(shù)；EngineeringUMining_H 19：采用啟發(fā)式的策略來降低候選項(xiàng)集的個數(shù)。2008Li Y C, YData andIIDS 20 ：同 Apriori 采用層次方h J S, et al.Knowledge式產(chǎn)生高效用模式。Engineering2009Ahmed C F,IEEE TKDEIHUP 21 ：采用模式增長的方式Tanbeer S K, et al.產(chǎn)生候選項(xiàng)集，然后再掃描數(shù)據(jù)集從候選項(xiàng)集中確認(rèn)

22、高效用模式。2010Tseng V S, Wu CKDD 2010UP-Growth 22：對算法 IHUP 進(jìn)W, et行了優(yōu)化，減少候選項(xiàng)集的個數(shù)。al.特點(diǎn)產(chǎn)生候選項(xiàng)集； 需要多次數(shù)據(jù)集的掃描。產(chǎn)生候項(xiàng)集；需要多次數(shù)據(jù)集的掃描。產(chǎn)生候選項(xiàng)集； 需要次數(shù)據(jù)集的掃描； 會失去一部分高效用模式。產(chǎn)生候選項(xiàng)集； 多次掃描數(shù)據(jù)集。產(chǎn)生候選項(xiàng)集； 需要3 次數(shù)據(jù)集的掃描。產(chǎn)生候選項(xiàng)集； 需要3 次數(shù)據(jù)集的掃描。2011Lin C W, Hong T P,Expert Systemset al.withApplications2012Liu M, Qu J.CIKM 20122012Liu J, Wa

23、ng K, eIal.DM 20122013TsIEEE TKDEng V S, Shie B, etal.HUP-Growth 23 ：將事務(wù)項(xiàng)集及效用值信息維護(hù)在一棵樹上，然后計(jì)算每項(xiàng)所有可能超集的效用值，從中確認(rèn)高效用模式。HUI-Miner 24 ：同 Apriori 算法層次方式產(chǎn)生高效用模式。d2HUP 25 ：通過枚舉項(xiàng)集的方法來挖掘高效用模式；同時需要維護(hù)枚舉樹和事務(wù)項(xiàng)集。UP-Growth 26：對算法 IHUP 進(jìn)行了優(yōu)化，減少候選項(xiàng)集的個數(shù)。需要計(jì)算大量項(xiàng)集的效用值， 從中確認(rèn)高效用項(xiàng)集。層次方式產(chǎn)生項(xiàng)集，然后從相關(guān)效用數(shù)組中計(jì)算項(xiàng)集的效用值。枚舉項(xiàng)集的方法。產(chǎn)生候選項(xiàng)集

24、； 多次數(shù)據(jù)集掃描。2005 年， Liu 等18 提出了一個典型算法Two-Phase，相對文獻(xiàn) 17 中的方法， Two-Phase的時間效率得到了較大的提高，但是該算法仍然存在Apriori 算法需要掃描多遍數(shù)據(jù)集的缺點(diǎn)；同時該方法也是通過候選項(xiàng)集來產(chǎn)生高效用模式，其時間效率仍然不是很理想。為了解決已存在算法的低效率問題，特別是挖掘稠密數(shù)據(jù)集時的低效率問題，Erwin 等 27 提出了一個基于樹結(jié)構(gòu)的高效用模式挖掘算法CTU-Mine 。然而，該算法只是在挖掘稠密數(shù)據(jù)集或用戶設(shè)定的最小效用值比較低的時候，性能才優(yōu)于Two-Phase 算法。Ahmed 等 21 提出一個不需要多次掃描數(shù)據(jù)

25、集的算法IHUP 。算法 IHUP 先將事務(wù)項(xiàng)集及效用信息存儲在一棵IHUP-Tree 上，然后首先從樹上挖掘到候選項(xiàng)集，再掃描數(shù)據(jù)集來確認(rèn)候選項(xiàng)集的真實(shí)效用值，從中找到所有的高效用模式。Tseng 等在文獻(xiàn) 22, 26中對算法IHUP 進(jìn)行改進(jìn)，主要是針對建樹方法的改進(jìn)，主要目的是減少產(chǎn)生的候選項(xiàng)集個數(shù)。算法D 2HUP25 采用項(xiàng)集枚舉的方法挖掘高效用模式，該算法主要通過剪枝策略提高挖掘的時間效率，但是需要大量的空間來維護(hù)枚舉樹和事務(wù)項(xiàng)集。HUI-Miner 24 同 Apriori算法采用層次方式產(chǎn)生高效用模式，每層中需要產(chǎn)生大量的項(xiàng)集，并計(jì)算每個項(xiàng)集的效用值； 同時還需要維護(hù)每個項(xiàng)集

26、所在事務(wù) ID 、相應(yīng)事務(wù)中的效用值和事務(wù)中其余項(xiàng)的效用值信息，因此該算法空間消耗較大。(2.2) 數(shù)據(jù)流上高效用模式挖掘研究現(xiàn)狀Tseng 等 28 提出了第一個數(shù)據(jù)流中高效用模式挖掘算法THUI ，該算法整合了Two-Phase算法和滑動窗口的方式來挖掘數(shù)據(jù)流上的高效用模式，每個窗口中有固定批數(shù)的數(shù)據(jù)，每批數(shù)據(jù)又有固定個數(shù)的事務(wù)項(xiàng)集。該算法首先挖掘出窗口的第一批數(shù)據(jù)中的候選2 項(xiàng)集，當(dāng)?shù)诙鷶?shù)據(jù)到來的時候， 再挖掘出前二批數(shù)據(jù)中的候選2 項(xiàng)集，依次挖掘出整個窗口中的候選2 項(xiàng)集，用所有的候選2 項(xiàng)集再產(chǎn)生全部的候選項(xiàng)集，最后還需要再掃描一遍數(shù)據(jù)集從候選項(xiàng)集中確認(rèn)高效用模式。該算法是一個近似

27、算法，它的主要問題是需要產(chǎn)生并維護(hù)候選項(xiàng)集，并且還需要掃描數(shù)據(jù)集來統(tǒng)計(jì)每個候選項(xiàng)集的效用值，甚至有時候會產(chǎn)生大量的候選項(xiàng)集。Li 等 29 提出兩個基于滑動窗口的算法MHUI-BIT& MHUI-TID，這兩個算法都采用類Apriori 算法的方式逐層產(chǎn)生所有的候選項(xiàng)集，然后再掃描數(shù)據(jù)集來統(tǒng)計(jì)候選項(xiàng)集的效用值。算法 MHUI-BIT 和 MHUI-TID 分別采用 bit-vector 和 TID-lists 兩個結(jié)構(gòu)來存儲當(dāng)前窗口中每批數(shù)據(jù)，利用這兩個結(jié)構(gòu)能檢索到與候選項(xiàng)集相關(guān)的事務(wù)，從而可以快速的統(tǒng)計(jì)候選項(xiàng)集的效用值，實(shí)驗(yàn)結(jié)果也驗(yàn)證了這兩個算法的時間效率優(yōu)于算法THUI 。2010 年，

28、Ahmed 等 30 提出一個仍然基于滑動窗口的算法HUPMS ，該算法采用樹結(jié)構(gòu)來維護(hù)窗口中每批數(shù)據(jù)的事務(wù)項(xiàng)集，通過一遍數(shù)據(jù)集掃描，將窗口中的事務(wù)項(xiàng)集維護(hù)在一棵樹上；當(dāng)需要挖掘窗口中的高效用模式的時候，采用模式增長的方式從樹上挖掘出所有的候選項(xiàng)集；最后再掃描一次數(shù)據(jù)集來統(tǒng)計(jì)所有候選項(xiàng)集的效用值。該算法相對算法MHUI-BIT&MHUI-TID ，可以有效的減少候選項(xiàng)集的個數(shù)，實(shí)驗(yàn)也驗(yàn)證了該算法有比較好的時間性能。2013年，本課題申請者 等 31提出 HUM-UT 算法，通過一遍數(shù)據(jù)集掃描，即可在不產(chǎn)生候選項(xiàng)集的條件下完成挖掘，其時間效率有較大提高（一個數(shù)量級以上）。綜上所述，目前的高效用模

29、式挖掘研究，存在如下不足：沒有針對不確定數(shù)據(jù)的建模。 挖掘在單個數(shù)據(jù)流上進(jìn)行，并且沒有考慮跨事務(wù)的模式挖掘。此外，總效用的計(jì)算采用簡單求和方式，沒有考慮到效用的概率分布和波動等因素，偶然事件可能導(dǎo)致挖掘結(jié)果與實(shí)際模式的較大偏離。因此，根據(jù)行業(yè)實(shí)際需求修正現(xiàn)有的效用計(jì)算模型，包含不確定數(shù)據(jù)和多數(shù)據(jù)流處理等，有著重要的現(xiàn)實(shí)意義。此亦為本課題的研究動機(jī)之一。附：參考文獻(xiàn)：1 R. Agrawal, T. Imielinski and A. Swami. Mining association rules between sets of items in large databases. 1993 AC

30、M SIGMOD International Conference on Management of Data. 1993. Washington, DC, United States.2 J. Han, J. Pei and Y. Yin. Mining frequent patterns without candidate generation. ACM SIGMOD International Conference on Management of Data. 2000. Dallas, TX, United States.3 J. Pei, et al. H-mine: Hyper-s

31、tructure mining of frequent patterns in large databases. IEEE International Conference on Data Mining (ICDM 2001). 2001. San Jose, CA, United States.4 C. Chui, B. Kao and E. Hung. Mining frequent itemsets from uncertain data. 11th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD

32、 2007). 2007. Nanjing, China.5 C.K. Leung, C.L. Carmichael and B. Hao. Efficient mining of frequent patterns from uncertain data. IEEE International Conference on Data Mining Workshops (ICDM Workshops 2007). 2007. Omaha, NE, United States.6 C.C. Aggarwal, et al. Frequent pattern mining with uncertai

33、n data. 15th ACM SIGKDD International Conferenceon Knowledge Discovery and Data Mining (KDD 2009). 2009. Paris, France.7 L. Wang, et al. Efficient Mining of Frequent Itemsets on Large Uncertain Databases. IEEE Transactions on Knowledge and Data Engineering, 2012. 24(12): pp. 2170-2183.8 X. Sun, L. L

34、im and S. Wang. An approximation algorithm of mining frequent itemsets from uncertain dataset. International Journal of Advancements in Computing Technology, 2012. 4(3): pp. 42-49.9 C.W. Lin and T.P. Hong. A new mining approach for uncertain databases using CUFP trees. Expert Systems with Applicatio

35、ns, 2012. 39(4): pp. 4084 4093.10 L. Wang, L. Feng and M. Wu. AT-Mine: An Efficient Algorithm of Frequent Itemset Mining on Uncertain Dataset. Journal of Computers, 2013. 8(6): pp. 1417-1426.11 R. Rawat and N. Jain. A Survey on Frequent ItemSet Mining Over Data Stream. International Journal of Elect

36、ronics Communication and Computer Engineering (IJECCE), 2013. 4(1): pp. 86-87.12 C.K. Leung and B. Hao. Mining of frequent itemsets from streams of uncertain data. International Conference on13 C. Giannella, et al. Mining frequent patterns in data streams at multiple time granularities. Next generat

37、ion data mining, 2003. 2003(212): pp. 191-212.14 C.K. Leung and F. Jiang. Frequent itemset mining of uncertain data streams using the damped window model. 26th Annual ACM Symposium on Applied Computing (SAC 2011). 2011. TaiChung, Taiwan.15 C.K. Leung and F. Jiang. Frequent pattern mining from time-f

38、ading streams of uncertain data. 13th International Conference on Data Warehousing and Knowledge Discovery (DaWaK 2011). 2011. Toulouse, France.16 L. Wang, L. Feng and M. Wu. UDS-FIM: An efficient algorithm of frequent itemsets mining over uncertain transaction data streams. Journal of Software, 201

39、4. 9(1): pp. 44-56.17 H. Yao, H.J. Hamilton and G.J. Butz. A foundational approach to mining itemset utilities from databases. 4th SIAM International Conference on Data Mining (ICDM 2004). 2004. Lake Buena Vista, FL, United States.18 Y. Liu, W.K. Liao and A. Choudhary. A two-phase algorithm for fast

40、 discovery of high utility itemsets. 9th Pacific-Asia conference on Advances in Knowledge Discovery and Data Mining. 2005. Hanoi, Viet nam.19 H. Yao and H.J. Hamilton. Mining itemset utilities from transaction databases. Data and Knowledge Engineering, 2006. 59(3): pp. 603-626.20 Y.C. Li, J.S. Yeh a

41、nd C.C. Chang. Isolated items discarding strategy for discovering high utility itemsets. Dataand Knowledge Engineering, 2008. 64(1): pp. 198-217.21 C.F. Ahmed, et al. Efficient Tree Structures for High Utility Pattern Mining in Incremental Databases. IEEE Transactions on Knowledge and Data Engineeri

42、ng, 2009. 21(12): pp. 1708-1721.22 V.S. Tseng, et al. UP-Growth: An efficient algorithm for high utility itemset mining. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2010). 2010. Washington, DC, United States.23 C.W. Lin, T.P. Hong and W.H. Lu. An effective tree st

43、ructure for mining high utility itemsets. Expert Systemswith Applications, 2011. 38(6): pp. 7419-7424.24 M. Liu and J. Qu. Mining high utility itemsets without candidate generation. 21st ACM International Conference on Information and Knowledge Management (CIKM 2012). 2012. Maui, HI, United States.2

44、5 J. Liu, K. Wang and B. Fung. Direct Discovery of High Utility Itemsets without Candidate Generation. 12th IEEE International Conference on Data Mining (ICDM 2012). 2012.26 V.S. Tseng, et al. Efficient Algorithms for Mining High Utility Itemsets from Transactional Databases. IEEE Transactions on Kn

45、owledge and Data Engineering, 2013. 25(8): pp. 1772-86.27 A. Erwin, R.P. Gopalan and N.R. Achuthan. CTU-mine: An efficient high utility itemset mining algorithm usingthe pattern growth approach. 7th IEEE International Conference on Computer and Information Technology. 2007.28 V.S. Tseng, C. Chu and

46、T. Liang. Efficient mining of temporal high utility itemsets from data streams. 2nd International Workshop on Utility-Based Data Mining. 2006.29H. Li, et al. Fast and memory efficient mining of high utility itemsets in data streams. 8th IEEE InternationalConference on Data Mining (ICDM 2008 ). 2008.

47、30C.F. Ahmed, S.K. Tanbeer and B. Jeong, Efficient mining of high utility patterns over data streams with a slidingwindow method, in Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing2010. 2010, Springer Berlin Heidelberg. pp. 99-113.31 L. Feng, L. Wang and

48、B. Jin. UT-Tree: Efficient mining of high utility itemsets from data streams. Intelligent Data Analysis （SCI&EI ）, 2013. 17(4): pp. 585-602.2主要研究內(nèi)容、目標(biāo)、方案和進(jìn)度及擬解決的關(guān)鍵問題：研究內(nèi)容：本課題的核心， 在于 多重不確定數(shù)據(jù)流上模式挖掘的模型和算法的研究。 根據(jù)已有的研究基礎(chǔ)，本著循序漸進(jìn)的原則，擬定的研究內(nèi)容分3 個部分：(1)多重不確定數(shù)據(jù)流上的頻繁模式挖掘：建立多重不確定數(shù)據(jù)流上跨流、跨事務(wù)的“頻繁模式”的概念模型和挖掘模型，并設(shè)計(jì)挖掘

49、算法。(2)多重數(shù)據(jù)流上的高效用模式的挖掘：建立多重數(shù)據(jù)流上跨流、跨事務(wù)的“高效用模式”的概念模型和挖掘模型，并設(shè)計(jì)挖掘算法。(3)多重不確定數(shù)據(jù)流上的高效用頻繁模式的挖掘：融合上述兩個概念模型，建立多重不確定數(shù)據(jù)流上跨流、跨事務(wù)的“高效用頻繁模式”的概念模型和挖掘模型，并設(shè)計(jì)挖掘算法?，F(xiàn)將以上 3 方面的內(nèi)容詳述如下。(1) 多重不確定數(shù)據(jù)流上的頻繁模式挖掘多重不確定數(shù)據(jù)流上的頻繁模式，由模式的“期望支持?jǐn)?shù)”描述（這一點(diǎn)與已有的不確定數(shù)據(jù)流頻繁模式概念相同） ；它和已有概念的區(qū)別在于：此概念模型處理的是多個異構(gòu)數(shù)據(jù)流，其挖掘出的頻繁模式，包括“跨事務(wù)頻繁模式（來源自多個不同時間上、不同事務(wù)中的組合模式） ”和“跨數(shù)據(jù)流頻繁模式”兩種擴(kuò)展類型的頻繁模式。此項(xiàng)內(nèi)容研究在給定的期望支持?jǐn)?shù)下，應(yīng)用窗口技術(shù)，挖掘最小閾值下的頻繁模式和 top-k 頻繁模式的算法，并分析算法效率隨窗口寬度、模式長度、期望支持?jǐn)?shù)大小等的關(guān)系。該項(xiàng)研究的創(chuàng)新之處， 在于將模式在時間上的關(guān)聯(lián)關(guān)系、 以及不同流內(nèi)模式間關(guān)