• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    在流滑動(dòng)窗體上挖掘Top—K高效用項(xiàng)集的有效算法

    2018-09-29 02:38郭世明金代亮高宏
    關(guān)鍵詞:數(shù)據(jù)流

    郭世明 金代亮 高宏

    摘 要:數(shù)據(jù)流上的頻繁項(xiàng)集挖掘是數(shù)據(jù)挖掘的一個(gè)重要話題,并在現(xiàn)實(shí)生活中應(yīng)用廣泛??墒沁@個(gè)問(wèn)題存在兩個(gè)限制:(1)項(xiàng)在數(shù)據(jù)流中的權(quán)重沒(méi)有被考慮;(2)項(xiàng)在每條事務(wù)中的數(shù)量沒(méi)有被考慮。因此,研究人員提出了“數(shù)據(jù)流上的高效用項(xiàng)集挖掘”的研究問(wèn)題。在這一問(wèn)題中,項(xiàng)的權(quán)重及項(xiàng)在事務(wù)中的數(shù)量被考慮,數(shù)據(jù)流上的高效用項(xiàng)集挖掘是指在數(shù)據(jù)流中挖掘所有效用值不小于用戶指定最小效用閾值的項(xiàng)集。對(duì)用戶而言,由于不了解數(shù)據(jù)流中數(shù)據(jù)的統(tǒng)計(jì)特性,很難設(shè)置一個(gè)合適的最小效用閾值,如果最小效用閾值設(shè)置過(guò)高,則挖掘算法返回高效用項(xiàng)集的數(shù)量過(guò)少,使得用戶無(wú)法準(zhǔn)確分析;如果最小效用閾值設(shè)置過(guò)低,則挖掘算法返回太多的高效用項(xiàng)集,使得用戶需要對(duì)結(jié)果集二次分析,為此研究人員提出了“數(shù)據(jù)流上的Top-K高效用項(xiàng)集挖掘”的研究問(wèn)題。數(shù)據(jù)流上的Top-K高效用項(xiàng)集挖掘是指在數(shù)據(jù)流中尋找前k個(gè)具有最高效用值的項(xiàng)集,通過(guò)設(shè)置k值取代最小效用閾值,可有效地控制算法的輸出規(guī)模,對(duì)用戶而言更直觀。與靜態(tài)數(shù)據(jù)相比,數(shù)據(jù)流具有如下特點(diǎn):快速的數(shù)據(jù)到達(dá)速率、數(shù)據(jù)流的尺寸未知和不能訪問(wèn)以前到達(dá)數(shù)據(jù)的特點(diǎn),因此很難將整個(gè)數(shù)據(jù)流放入內(nèi)存中處理,通常研究人員采用流滑動(dòng)窗體模型。流滑動(dòng)窗體是由固定數(shù)量的、最近到達(dá)的批數(shù)據(jù)組成,每個(gè)批數(shù)據(jù)包含一組事務(wù)集?,F(xiàn)有的挖掘流滑動(dòng)窗體上Top-K高效用項(xiàng)集的研究方法通常包含兩個(gè)階段:(1)采用高估技術(shù)高估項(xiàng)集在流滑動(dòng)窗體中的效用,將高估效用不小于由閾值提升技術(shù)獲得的最小效用閾值的項(xiàng)集選定為T(mén)op-K高效用項(xiàng)集候選項(xiàng)集;(2)通過(guò)掃描流滑動(dòng)窗體內(nèi)的批數(shù)據(jù),計(jì)算第一階段生成的候選項(xiàng)集的真實(shí)效用??墒?,這個(gè)方法存在兩個(gè)問(wèn)題:(1)第一階段生成的候選項(xiàng)集通常數(shù)量巨大,需要大量的存儲(chǔ)空間;(2)計(jì)算第一階段生成的候選項(xiàng)集的真實(shí)效用是非常耗時(shí)的。因此,本文提出一個(gè)在挖掘過(guò)程中不生成候選項(xiàng)集的流滑動(dòng)窗體上Top-K高效用項(xiàng)集挖掘算法TK-HIS,TK-HIS采用提出的HUIL-Tree和效用數(shù)據(jù)庫(kù)存儲(chǔ)流滑動(dòng)窗體中的項(xiàng)集及其在窗體事務(wù)中的效用,在HUIL-Tree和效用數(shù)據(jù)庫(kù)的構(gòu)建過(guò)程中提出兩個(gè)閾值提升策略提升初始值為0的最小效用閾值,在挖掘過(guò)程中TK-HIS維護(hù)前k個(gè)具有最高效用值的項(xiàng)集,使用模式增長(zhǎng)的方法生成搜索空間中的項(xiàng)集,對(duì)每一個(gè)項(xiàng)集通過(guò)效用數(shù)據(jù)庫(kù)直接計(jì)算其在流滑動(dòng)窗體中的效用。研究在稀疏數(shù)據(jù)流上進(jìn)行了大量的實(shí)驗(yàn)評(píng)估TK-HIS的性能,并與當(dāng)前最好的流滑動(dòng)窗體Top-K高效用項(xiàng)集挖掘算法T-HUDS進(jìn)行比較,實(shí)驗(yàn)結(jié)果表明在稀疏數(shù)據(jù)流上TK-HIS顯著優(yōu)于T-HUDS:運(yùn)行時(shí)間最快可提升一個(gè)數(shù)量級(jí)。

    關(guān)鍵詞:Top-K高效用項(xiàng)集; 模式增長(zhǎng); 數(shù)據(jù)流; 效用挖掘; 滑動(dòng)窗體

    Abstract: Frequent itemset mining over data streams (FIM-DS) is an important research topic in data mining, and has wide applications in real life. However, there are two limitations in FIM-DS: (1) The weight of items is not considered in a data stream; (2) The quantity of items is not considered in each transaction of the data stream. Thus High Utility Itemset Mining over Data Streams (HUIM-DS) has been proposed. In HUIM-DS, the weight of items in a data stream and the quantity of items in each transaction are considered. HUIM over a data stream refers to discovering the complete set of itemsets whose utilities in the data stream are no less than a user-specified minimum utility threshold. However it is difficult to set a proper value for the minimum utility threshold specified by users who are not familiar with the characteristics of the data stream. If the threshold is set too high, there are not enough high utility itemsets returned to analyze. If the threshold is set too low, too many high utility itemsets are returned, which makes users sift through the result to find the useful ones. In view of this, Top-K High Utility Itemsets Mining over Data Streams (T-HUIM-DS) has been proposed. T-HUIM over a data stream is to find itemsets with k highest utilities from the data stream. In comparison with HUIM-DS, T-HUIM-DS can preciously control the output size by setting k instead of a minimum utility threshold, and is more intuitive for users. In comparison with static data, data streams have the following properties: fast data arrival rate, unknown and unbound size of data and inability to backtrack previous data. It is intractable to handle the entire data stream in main memory. To deal with this problem, stream sliding window model has been widely used in resource-limited environment. A stream sliding window consists of a fixed number of most recent batches, each containing a set of transactions. The existing algorithm for mining top-K high utility itemsets over a stream sliding window contains two phases. In phase I, an over-estimation technique is adopted to over-estimate the utility of an itemset in the window, and itemsets whose over-estimated utilities are no less than the minimum utility threshold obtained by threshold-raising strategies are taken as candidate top-K high utility itemsets. In phase II, the candidates generated from phase I are verified through scanning the batches in the window. However this algorithm has two problems. (1) The number of candidates is usually very huge and extensive memory is required; (2) It is time consuming to verify candidates. Thus this paper proposes an efficient algorithm TK-HIS for mining Top-K high utility itemsets over a stream sliding window, which does not generate candidates during the mining process. TK-HIS adopts a novel tree structure HUIL-Tree and a utility database to store the itemsets in the window and their utilities in the transactions of the window. During the construction of HUIL-Tree and utility database, two threshold-raising strategies are proposed to raise the minimum utility threshold initialized to 0. During the mining process, TK-HIS maintains the itemsets with k highest utilities currently. TK-HIS exploits the pattern-growth method to generate itemsets from the search space, and the utility of each itemset in a stream sliding window is calculated directly. Extensive experiments on both real and synthetic stream datasets are performed to compare TK-HIS with the state-of-the-art algorithm T-HUDS. The experimental results show that TK-HIS significantly outperforms T-HUDS on sparse data streams: TK-HIS is one order of magnitude faster.

    Key words: Top-K high utility itemsets; pattern growth; data streams; utility mining; sliding window

    引言

    數(shù)據(jù)流上的頻繁項(xiàng)集挖掘(Frequent Itemset Mining over Data Streams, FIM-DS)是數(shù)據(jù)挖掘中一個(gè)重要的研究課題,并在現(xiàn)實(shí)生活中應(yīng)用廣泛。FIM-DS是指在數(shù)據(jù)流中尋找支持度(數(shù)據(jù)流中包含項(xiàng)集的事務(wù)數(shù)量)不小于用戶指定最小支持閾值的所有項(xiàng)集??墒荈IM-DS存在2個(gè)限制:

    (1)項(xiàng)在數(shù)據(jù)流中的權(quán)重未被考慮;

    (2)項(xiàng)在每條事務(wù)中的數(shù)量未被考慮。

    因此,研究人員提出了數(shù)據(jù)流上的高效用項(xiàng)集挖掘(High Utility Itemset Mining over Data Streams, HUIM-DS)的研究問(wèn)題。在HUIM-DS中,數(shù)據(jù)流中的項(xiàng)與一權(quán)重(項(xiàng)在數(shù)據(jù)流中的外部效用)關(guān)聯(lián),例如商品的單位利潤(rùn);在數(shù)據(jù)流每條事務(wù)中項(xiàng)關(guān)聯(lián)一個(gè)正整數(shù)(項(xiàng)在事務(wù)中的內(nèi)部效用),例如商品的購(gòu)買(mǎi)數(shù)量。HUIM-DS是指在數(shù)據(jù)流中尋找效用值不小于用戶指定最小效用閾值的所有項(xiàng)集。

    考慮一個(gè)在線銷售數(shù)據(jù)流(見(jiàn)圖1)和數(shù)據(jù)流中項(xiàng)的單位利潤(rùn)(見(jiàn)表1)。在圖1中字母代表商品名稱(項(xiàng)),每個(gè)商品關(guān)聯(lián)一個(gè)數(shù)量,代表商品的銷售數(shù)量。在每條事務(wù)中,項(xiàng)的效用定義為其外部效用與內(nèi)部效用的乘積,項(xiàng)集的效用定義為項(xiàng)集包含項(xiàng)的效用和。例如在第二條事務(wù)中,項(xiàng)A的利潤(rùn)(效用)為5 × 3 = 15,項(xiàng)集{AC}的利潤(rùn)為15 + 5 = 20。如果項(xiàng)集在數(shù)據(jù)流中的效用不小于用戶指定的最小效用閾值,則稱該項(xiàng)集為高效用項(xiàng)集。HUIM-DS在現(xiàn)實(shí)生活中隨處可見(jiàn),例如消費(fèi)者購(gòu)物行為分析、Web點(diǎn)擊流分析和股票市場(chǎng)價(jià)格預(yù)測(cè)等。

    與靜態(tài)數(shù)據(jù)相比,數(shù)據(jù)流存在如下特點(diǎn):快速的數(shù)據(jù)到達(dá)速率、數(shù)據(jù)流尺寸未知和無(wú)法訪問(wèn)以前到達(dá)的數(shù)據(jù),因此研究人員提出采用流滑動(dòng)窗體模型。流滑動(dòng)窗體由數(shù)量固定的、最近到達(dá)的批數(shù)據(jù)組成,當(dāng)窗體發(fā)生滑動(dòng)時(shí),將新到達(dá)的批數(shù)據(jù)添加到流滑動(dòng)窗體中,同時(shí)移除窗體內(nèi)時(shí)間上最早的批數(shù)據(jù)??墒怯捎谟脩舨涣私鈹?shù)據(jù)流中數(shù)據(jù)的統(tǒng)計(jì)特性,很難設(shè)置一個(gè)合適的最小效用閾值。最小效用閾值設(shè)置過(guò)高,則挖掘算法返回的高效用項(xiàng)集數(shù)量過(guò)少,使得用戶無(wú)法分析;最小效用閾值設(shè)置過(guò)低,則挖掘算法返回太多的高效用項(xiàng)集,使得用戶需要從結(jié)果中再次挑選。為了有效地控制挖掘算法的輸出規(guī)模,研究人員提出了流滑動(dòng)窗體上挖掘Top-K高效用項(xiàng)集(Top-K High Utility Itemset Mining over a stream Sliding Window,T-HUIM-SW)的研究問(wèn)題,T-HUIM-SW是指在流滑動(dòng)窗體上尋找前k個(gè)具有最高效用值的項(xiàng)集。

    現(xiàn)有的挖掘流滑動(dòng)窗體上Top-K高效用項(xiàng)集的方法通常包含兩個(gè)階段[1]:第一階段通過(guò)高估技術(shù)高估項(xiàng)集在流滑動(dòng)窗體中的效用,選擇高估效用不小于由閾值提升技術(shù)獲得的最小效用閾值的項(xiàng)集作為T(mén)op-K高效用項(xiàng)集的候選項(xiàng)集;第二階段通過(guò)掃描流滑動(dòng)窗體中的事務(wù),計(jì)算第一階段生成候選項(xiàng)集的真實(shí)效用。可是,這個(gè)方法存在兩個(gè)問(wèn)題:

    (1)第一階段生成的候選項(xiàng)集數(shù)量巨大,消耗了大量的內(nèi)存空間;

    (2)計(jì)算第一階段生成候選項(xiàng)集的真實(shí)效用耗時(shí)巨大。

    因此,本文提出一個(gè)不生成候選項(xiàng)集的流滑動(dòng)窗體Top-K高效用項(xiàng)集挖掘方法,本文貢獻(xiàn)如下:

    (1)提出了一個(gè)新的數(shù)據(jù)結(jié)構(gòu)HUIL-Tree (High Utility Itemset Tree which arranges items according to Lexicographic order),用于存儲(chǔ)流滑動(dòng)窗體中的項(xiàng)集。同時(shí),采用一個(gè)效用數(shù)據(jù)庫(kù)存儲(chǔ)項(xiàng)集在流滑動(dòng)窗體內(nèi)每條事務(wù)中的效用;

    (2)提出了一個(gè)挖掘流滑動(dòng)窗體上Top-K高效用項(xiàng)集的有效算法TK-HIS (Top-K High utility Itemset mining over a stream Siding window)。基于構(gòu)建的HUIL-Tree和效用數(shù)據(jù)庫(kù),TK-HIS采用模式增長(zhǎng)的方法生成搜索空間中的項(xiàng)集,對(duì)每1個(gè)項(xiàng)集直接計(jì)算其在流滑動(dòng)窗體中的效用,避免了Top-K高效用項(xiàng)集候選項(xiàng)集的生成;

    (3)在真實(shí)和合成數(shù)據(jù)集模擬的數(shù)據(jù)流中對(duì)TK-HIS進(jìn)行了性能評(píng)估,并與當(dāng)前最好的流滑動(dòng)窗體上Top-K高效用項(xiàng)集挖掘算法T-HUDS進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明在稀疏數(shù)據(jù)流中TK-HIS均顯著優(yōu)于T-HUDS:運(yùn)行時(shí)間可提升一個(gè)數(shù)量級(jí)。

    1 背景知識(shí)

    1.1 問(wèn)題描述

    1.2 相關(guān)工作

    在靜態(tài)數(shù)據(jù)庫(kù)中,研究人員對(duì)高效用項(xiàng)集挖掘進(jìn)行了廣泛研究,典型的算法包括IHUP[2]、Two-Phase[3]、IIDS[4]、UPGrowth[5]、HUI-Miner[6]和HUITWU[7]。由于數(shù)據(jù)流具有僅能訪問(wèn)一次的特性,使得上述算法無(wú)法應(yīng)用于數(shù)據(jù)流。現(xiàn)有的流滑動(dòng)窗體上挖掘高效用項(xiàng)集的算法通常包含兩個(gè)階段。第一階段生成流滑動(dòng)窗體內(nèi)高效用項(xiàng)集候選項(xiàng)集,第二階段掃描流滑動(dòng)窗體計(jì)算候選項(xiàng)集的真實(shí)效用。依據(jù)第一階段生成候選項(xiàng)集的不同方法,現(xiàn)有算法可劃分為兩類。第一類采用與Apriori[8]相似的候選項(xiàng)集生成和測(cè)試框架,首先高估單項(xiàng)集的效用上界,選擇效用上界不小于用戶指定最小效用閾值的單項(xiàng)集作為候選項(xiàng)集。通過(guò)掃描流滑動(dòng)窗體,遞歸地由長(zhǎng)度為k的候選項(xiàng)集生成長(zhǎng)度為(k + 1)的候選項(xiàng)集(k ≥ 1),典型的算法包括THUI-Mine[9]、MHUI-max[10]和MHUI-TID[11];第二類采用與FP-Growth[12]相似的模式增長(zhǎng)方法,這類算法通常采用樹(shù)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)流中項(xiàng)集及其高估效用,依據(jù)發(fā)現(xiàn)的候選1-項(xiàng)集,將搜索空間劃分為不同的子空間。在每個(gè)子空間中搜索局部候選項(xiàng),組合成為全局候選項(xiàng)集,典型的算法包括HUPMS[13]和SHU-Growth[14]。T-HUDS[1]為目前唯一的流滑動(dòng)窗體上挖掘Top-K高效用項(xiàng)集的算法,該算法同樣包含2個(gè)階段。第一階段將流滑動(dòng)窗體中高估效用不小于由閾值提升技術(shù)獲得的最小效用閾值的項(xiàng)集,作為T(mén)op-K高效用項(xiàng)集候選項(xiàng)集;第二階段校驗(yàn)第一階段生成的候選項(xiàng)集??墒?,該算法生成了太多的候選項(xiàng)集,使得算法耗費(fèi)了大量的內(nèi)存及計(jì)算時(shí)間。

    2 在流滑動(dòng)窗體上挖掘Top-K高效用項(xiàng)集

    一般來(lái)說(shuō),在流滑動(dòng)窗體上挖掘Top-K高效用項(xiàng)集首先需要對(duì)數(shù)據(jù)流中前winSize個(gè)批數(shù)據(jù)構(gòu)建挖掘算法采用的數(shù)據(jù)結(jié)構(gòu),然后基于構(gòu)建的數(shù)據(jù)結(jié)構(gòu)挖掘流滑動(dòng)窗體上的Top-K高效用項(xiàng)集,最后對(duì)構(gòu)建的數(shù)據(jù)結(jié)構(gòu)更新最新到達(dá)的批數(shù)據(jù),移除窗體內(nèi)時(shí)間上最早的批數(shù)據(jù)。本節(jié)首先介紹HUIL-Tree和效用數(shù)據(jù)庫(kù)的定義及構(gòu)建方法,然后描述TK-HIS提升最小效用閾值的策略及挖掘Top-K高效用項(xiàng)集的方法,最后給出當(dāng)流滑動(dòng)窗體發(fā)生滑動(dòng)時(shí),對(duì)HUIL-Tree和效用數(shù)據(jù)庫(kù)的更新算法。

    2.1 HUIL-Tree和效用數(shù)據(jù)庫(kù)

    TK-HIS采用樹(shù)結(jié)構(gòu)HUIL-Tree和效用數(shù)據(jù)庫(kù)存儲(chǔ)流滑動(dòng)窗體中項(xiàng)集及其在窗體事務(wù)中的效用,效用數(shù)據(jù)庫(kù)為一個(gè)一維數(shù)組,其長(zhǎng)度為流滑動(dòng)窗體內(nèi)所有項(xiàng)在事務(wù)中出現(xiàn)的頻度和。

    定義10 HUIL-Tree HUIL-Tree是滿足下列條件的一個(gè)樹(shù)結(jié)構(gòu)。

    (1)由一個(gè)根結(jié)點(diǎn)(標(biāo)記為null)、項(xiàng)前綴子樹(shù)集(作為根結(jié)點(diǎn)的子女)和一個(gè)頭表組成;

    (2)項(xiàng)前綴子樹(shù)中的每個(gè)結(jié)點(diǎn)包括3個(gè)域:項(xiàng)標(biāo)記、結(jié)點(diǎn)鏈接和事務(wù)指針數(shù)組。其中,結(jié)點(diǎn)鏈接是指連接樹(shù)中具有相同項(xiàng)標(biāo)記的下一個(gè)樹(shù)結(jié)點(diǎn),事務(wù)指針是指對(duì)效用數(shù)據(jù)庫(kù)中事務(wù)的鏈接;

    (3)頭表中的每條記錄包含3個(gè)域:項(xiàng)標(biāo)記、項(xiàng)在流滑動(dòng)窗體中的前綴效用及指向樹(shù)中第一個(gè)具有相同項(xiàng)標(biāo)記的樹(shù)結(jié)點(diǎn)的指針。

    由數(shù)據(jù)流首個(gè)流滑動(dòng)窗體生成的HUIL-Tree和效用數(shù)據(jù)庫(kù)由算法一構(gòu)建,構(gòu)建過(guò)程僅需要掃描流滑動(dòng)窗體一次,由每個(gè)流滑動(dòng)窗體中批數(shù)據(jù)構(gòu)建的HUIL-Tree和效用數(shù)據(jù)庫(kù)稱為全局HUIL-Tree和全局效用數(shù)據(jù)庫(kù)。算法1的流程描述如下。

    例如在圖1的流滑動(dòng)窗體SW1中,每條事務(wù)依據(jù)字母序排列,將第一條事務(wù)T1 = {(B, 1) (C, 1) (D, 1)}插入全局HUIL-Tree時(shí),結(jié)點(diǎn)NB被首先創(chuàng)建(結(jié)點(diǎn)NB的項(xiàng)標(biāo)記為B),計(jì)算項(xiàng)B在T1中的效用2 × 1 = 2,存儲(chǔ)在全局效用數(shù)據(jù)庫(kù)UDB的第一條記錄中。在頭表中添加項(xiàng)標(biāo)記為B的記錄,計(jì)算項(xiàng)B在T1中的前綴效用2,累計(jì)進(jìn)入頭表中項(xiàng)B在流滑動(dòng)窗體SW1中的前綴效用。對(duì)項(xiàng)C、項(xiàng)D執(zhí)行相同的操作,因項(xiàng)D為事務(wù)的最后一項(xiàng),將事務(wù)標(biāo)識(shí)符T1添加到ND結(jié)點(diǎn)的事務(wù)指針數(shù)組中。將SW1中所有事務(wù)插入到全局HUIL-Tree后,全局HUIL-Tree和全局效用數(shù)據(jù)庫(kù)如圖2所示。

    2.2 提出的挖掘方法TK-HIS

    流滑動(dòng)窗體上Top-K高效用項(xiàng)集挖掘算法通常將最小效用閾值初始化為0,在構(gòu)建數(shù)據(jù)結(jié)構(gòu)的過(guò)程中通過(guò)閾值提升技術(shù)提升最小效用閾值,在挖掘過(guò)程中通過(guò)項(xiàng)集的效用動(dòng)態(tài)地調(diào)整最小效用閾值。本小節(jié)首先介紹TK-HIS采用的閾值提升技術(shù),然后描述基于HUIL-Tree和效用數(shù)據(jù)庫(kù)挖掘Top-K高效用項(xiàng)集的方法。在此基礎(chǔ)上,將研究展開(kāi)如下。

    2.2.1 閾值提升技術(shù)研究

    閾值提升技術(shù)TK-HIS采用2個(gè)策略提升最小效用閾值,分別是流滑動(dòng)窗體中單項(xiàng)集的效用;HUIL-Tree的路徑效用。這里,可給出各要點(diǎn)內(nèi)容分述如下。

    (1)在全局HUIL-Tree和全局效用數(shù)據(jù)庫(kù)的構(gòu)建和更新過(guò)程中,TK-HIS維護(hù)一個(gè)二維數(shù)組P存儲(chǔ)流滑動(dòng)窗體中單項(xiàng)集的效用,P的長(zhǎng)度為流滑動(dòng)窗體的尺寸,寬度為流滑動(dòng)窗體中項(xiàng)的數(shù)量。對(duì) x ∈ I,P[x]為單項(xiàng)集{x}在流滑動(dòng)窗體中的效用,當(dāng)掃描批數(shù)據(jù)Bm中的事務(wù)Td = {i1, i2, …, im} (ij ∈ I, 1 ≤ j ≤ m)時(shí),單項(xiàng)集{ij}在Td中的效用累積進(jìn)入P[ij][m]。當(dāng)流滑動(dòng)窗體掃描結(jié)束后,最小效用閾值可設(shè)置為P[x]中第k位的效用值。例如在圖1的流滑動(dòng)窗體SW1中,當(dāng)掃描T1 = {B, C, D}時(shí),P[B][1]累積項(xiàng)B在T1中的效用u({B}, T1) = 2,P[C][1]累積項(xiàng)C在T1中的效用u({C}, T1) = 1,P[D][1]累積項(xiàng)D在T1中的效用u({D}, T1) = 4。SW1掃描結(jié)束后,得到結(jié)果可見(jiàn)表2。如果k設(shè)置為3,則最小效用閾值可提升為P[x]中第3位的效用值,也就是7。

    (2)在全局HUIL-Tree和全局效用數(shù)據(jù)庫(kù)的構(gòu)建完成后,遍歷HUIL-Tree尋找事務(wù)指針數(shù)組不為空的結(jié)點(diǎn),SET為由所有發(fā)現(xiàn)結(jié)點(diǎn)到根結(jié)點(diǎn)所形成路徑代表的項(xiàng)集所組成的集合,SET中每個(gè)項(xiàng)集在流滑動(dòng)窗體中的效用下界為代表項(xiàng)集路徑的效用,即效用數(shù)據(jù)庫(kù)中由事務(wù)指針數(shù)組所有鏈接事務(wù)的效用和。例如,在圖2的HUIL-Tree中存在4個(gè)結(jié)點(diǎn)的事務(wù)指針數(shù)組不為空,對(duì)事務(wù)指針數(shù)組包含T1的結(jié)點(diǎn),項(xiàng)集{BCD}在流滑動(dòng)窗體中的效用下界為效用數(shù)據(jù)庫(kù)中T1的事務(wù)效用,即2 + 1 + 4 = 7。如果k設(shè)置為3,則最小效用閾值可提升為SET中具有第3位效用下界值的項(xiàng)集的效用下界,即最小效用閾值可提升為4個(gè)結(jié)點(diǎn)代表項(xiàng)集的效用下界值{7, 23, 6, 9}中的7。

    2.2.2 挖掘Top-K高效用項(xiàng)集

    在全局HUIL-Tree和全局效用數(shù)據(jù)庫(kù)構(gòu)建完成后,TK-HIS采用模式增長(zhǎng)的方式挖掘流滑動(dòng)窗體內(nèi)Top-K高效用項(xiàng)集,對(duì)全局HUIL-Tree頭表采用自底向上的遍歷順序生成項(xiàng)集。Zihayat等[1]指出,項(xiàng)在流滑動(dòng)窗體中的前綴效用具有向下閉合屬性,并提出了引理1。

    引理1 假定在流滑動(dòng)窗體SW的每條事務(wù)中,項(xiàng)依據(jù)字母序排列,X為非空項(xiàng)集,ip為X的最后一項(xiàng),則ip在SW中的前綴效用不小于X在SW中的效用,即:PrefixUtil(ip, SW) ≥ u(X)。(證明略)

    引理1表明在HUIL-Tree頭表的遍歷過(guò)程中,如果頭表中項(xiàng)ip在流滑動(dòng)窗體中的前綴效用小于由閾值提升技術(shù)獲得的最小效用閾值,則以ip為最后一項(xiàng)的所有項(xiàng)集均不可能為T(mén)op-K高效用項(xiàng)集,也就是說(shuō),無(wú)需構(gòu)建{ip}的條件模式樹(shù)。因此,HUIL- Tree頭表中項(xiàng)在流滑動(dòng)窗體中的前綴效用可用于修剪搜索空間。

    如果頭表中項(xiàng)ip在流滑動(dòng)窗體中的前綴效用不小于當(dāng)前的最小效用閾值,則TK-HIS包含4步計(jì)算以ip為最后一項(xiàng)項(xiàng)集的效用。對(duì)其可闡釋如下。

    (1)通過(guò)遍歷全局HUIL-Tree中與ip相關(guān)的路徑,生成{ip}的條件模式庫(kù);

    (2)基于{ip}條件模式庫(kù)中的信息構(gòu)建{ip}的條件模式樹(shù)及{ip}的條件效用數(shù)據(jù)庫(kù);

    (3)[JP3]在{ip}的條件模式樹(shù)和條件效用數(shù)據(jù)庫(kù)中,遞歸地挖掘以ip為最后一項(xiàng)的Top-K高效用項(xiàng)集;

    (4)更新全局HUIL- Tree和全局效用數(shù)據(jù)庫(kù)中與項(xiàng)ip相關(guān)的信息。具體研究可詳見(jiàn)如下。

    2.2.2.1 生成條件模式庫(kù)

    如果全局HUIL-Tree頭表中的項(xiàng)ip (1 ≤ p ≤ n)在流滑動(dòng)窗體中的前綴效用不小于當(dāng)前的最小效用閾值,則首先計(jì)算1-項(xiàng)集{ip}的效用,然后按如下方式構(gòu)建{ip}的條件模式庫(kù):

    (1)遍歷頭表中由項(xiàng)標(biāo)記為ip的記錄出發(fā)的結(jié)點(diǎn)鏈接,收集結(jié)點(diǎn)鏈接上的樹(shù)結(jié)點(diǎn);

    (2)由(1)中的樹(shù)結(jié)點(diǎn)到全局HUIL-Tree根結(jié)點(diǎn)形成路徑所代表的項(xiàng)集,形成{ip}的條件模式庫(kù);

    (3)依據(jù)(1)中樹(shù)結(jié)點(diǎn)的事務(wù)指針數(shù)組,從全局效用數(shù)據(jù)庫(kù)收集(2)中路徑所有項(xiàng)在事務(wù)中的效用,載入{ip}的條件模式庫(kù)。

    2.2.2.2 構(gòu)建條件HUIL-Tree和條件效用數(shù)據(jù)庫(kù)

    {ip}的條件HUIL-Tree的構(gòu)建需要二次掃描{ip}的條件模式庫(kù),在條件模式樹(shù)的構(gòu)建中TK-HIS采用項(xiàng)集的事務(wù)權(quán)重值高估項(xiàng)集在流滑動(dòng)窗體中的效用。

    [JP3]定義11 項(xiàng)集的事務(wù)權(quán)重值(Transaction Weight Utility,TWU) 項(xiàng)集X的事務(wù)權(quán)重值是指流滑動(dòng)窗體SW中所有包含X的事務(wù)的事務(wù)效用和,即:TWU(X) = ∑Td∈SW∧XTdTU(Td)。

    例如在圖1的數(shù)據(jù)流中項(xiàng)集{BC}在流滑動(dòng)窗體SW1中的事務(wù)權(quán)重值TWU({BC}) =TU(T1) + TU(T3) = 13。

    很明顯,在流滑動(dòng)窗體中TWU(X)≥ u(X)。同時(shí)TWU(X)滿足向下閉合屬性,即如果項(xiàng)集Y是X的子集,則在流滑動(dòng)窗體中可得:TWU(Y) ≥TWU(X)。因此,項(xiàng)集的事務(wù)權(quán)重值可用于修剪搜索空間。

    在對(duì){ip}條件模式庫(kù)的第一次掃描中,累積{ip}條件模式庫(kù)中單項(xiàng)的事務(wù)權(quán)重值。第一次掃描結(jié)束后,事務(wù)權(quán)重值小于當(dāng)前最小效用閾值的項(xiàng)組成的集合由S代表。由于S中的項(xiàng)及其超集均不可能為高效用項(xiàng)集,所以在第二次掃描中對(duì)每條事務(wù)移除S中的項(xiàng)。對(duì)移除所有S中的項(xiàng)的事務(wù),可稱之為修訂事務(wù)。TK-HIS對(duì){ip}條件模式庫(kù)中的修訂事務(wù)采用與算法1相似的方式構(gòu)建{ip}的條件模式樹(shù)和{ip}的條件效用數(shù)據(jù)庫(kù),{ip}的條件模式樹(shù)與全局HUIL-Tree存在2點(diǎn)不同:

    (1){ip}條件模式樹(shù)的根結(jié)點(diǎn)標(biāo)記為{ip},也就是條件項(xiàng)集;

    (2)對(duì){ip}條件模式樹(shù)頭表中的項(xiàng)iq,條件項(xiàng)集{ip}在包含iq的所有事務(wù)中的效用需要累積進(jìn)入頭表iq在流滑動(dòng)窗體中的前綴效用。

    與全局效用數(shù)據(jù)庫(kù)相比,條件效用數(shù)據(jù)庫(kù)需要在每條事務(wù)中保留條件項(xiàng)集的效用。

    例如,在{E}的條件模式庫(kù)中(見(jiàn)表3),單項(xiàng)的事務(wù)權(quán)重值為{(A: 23), (B: 6), (C: 29)},其中“:”后面的數(shù)字代表單項(xiàng)的事務(wù)權(quán)重值。項(xiàng)B的事務(wù)權(quán)重值小于當(dāng)前的最小效用閾值min_util = 7,因此項(xiàng)B需要從{E}條件模式庫(kù)的每條事務(wù)中移除。完成修訂后,{E}的條件模式庫(kù)見(jiàn)表3第3列所示。創(chuàng)建{E}條件模式樹(shù)的根結(jié)點(diǎn),標(biāo)記為{E}。依據(jù)字母序?qū)Φ谝淮螔呙柚惺聞?wù)權(quán)重值不小于min_util的項(xiàng)排序(A, C),然后插入到{E}的條件模式樹(shù)的頭表中。在對(duì){E}條件模式庫(kù)的第二次掃描中,第一條修訂事務(wù)T2 = {(A, 1) (C, 1)}形成第一條分支,附著在{E}條件模式樹(shù)的根結(jié)點(diǎn),樹(shù)結(jié)點(diǎn)NC的事務(wù)指針設(shè)置為T(mén)2。項(xiàng)A和項(xiàng)C在事務(wù)T2中的效用存儲(chǔ)在{E}的條件效用數(shù)據(jù)庫(kù)的第一條記錄中。項(xiàng)A在T2中的前綴效用與條件項(xiàng)集{E}在T2中的效用和15 + 3 = 18,累積進(jìn)入項(xiàng)A在{E}條件模式樹(shù)頭表中的前綴效用,對(duì)項(xiàng)C在頭表中的前綴效用以相同的方式計(jì)算。在插入第二條修訂事務(wù)之后,{E}的條件模式樹(shù)及{E}的條件效用數(shù)據(jù)庫(kù)如圖3所示。

    2.2.2.3 從條件模式樹(shù)和條件效用數(shù)據(jù)庫(kù)挖掘Top-K高效用項(xiàng)集

    從條件模式樹(shù)和條件效用數(shù)據(jù)庫(kù)中挖掘高效用項(xiàng)集與從全局樹(shù)和全局效用數(shù)據(jù)庫(kù)中挖掘高效用項(xiàng)集包含相同的步驟,即如果頭表中iq的前綴效用不小于當(dāng)前的最小效用閾值,則首先計(jì)算由條件項(xiàng)集聯(lián)接iq組成的新項(xiàng)集X在流滑動(dòng)窗體中的效用,然后生成X的條件模式庫(kù),構(gòu)建X的條件模式樹(shù)和X的條件效用數(shù)據(jù)庫(kù),最后迭代地挖掘X的條件模式樹(shù)和條件效用數(shù)據(jù)庫(kù)。

    例如,在{E}的條件模式樹(shù)中(如圖3),項(xiàng)C在頭表中的效用27不小于當(dāng)前的最小效用閾值min_util = 7,計(jì)算項(xiàng)集{CE}的效用為(5 + 3) + (1 + 3) = 12,可知{CE}為一個(gè)高效用項(xiàng)集。然后構(gòu)建{CE}的條件模式樹(shù)及{CE}的條件效用數(shù)據(jù)庫(kù),如圖4所示。在{CE}的條件模式樹(shù)中,項(xiàng)A在頭表中的效用23不小于min_util = 7,計(jì)算項(xiàng)集{ACE}的效用為23,可知{ACE}為一個(gè)高效用項(xiàng)集。在{E}的條件模式樹(shù)中,當(dāng)完成所有包含項(xiàng)C項(xiàng)集的效用計(jì)算后,需要對(duì){E}的條件模式樹(shù)和條件效用數(shù)據(jù)庫(kù)進(jìn)行更新(更新過(guò)程在2.2.4中介紹)。繼續(xù)遍歷{E}條件模式樹(shù)的頭表,項(xiàng)A在頭表中的效用18不小于min_util,計(jì)算項(xiàng)集{AE}的效用為15 + 3 = 18,可知{AE}為一個(gè)高效用項(xiàng)集,此時(shí)高效用項(xiàng)集的數(shù)量達(dá)到k值3,調(diào)整當(dāng)前的最小效用閾值為{12, 23, 18}中第3位的效用值12。

    2.2.2.4 更新全局HUIL-Tree

    當(dāng)完成包含ip所有項(xiàng)集的效用計(jì)算后,TK-HIS需要更新全局HUIL-Tree,實(shí)現(xiàn)以頭表中后續(xù)遍歷項(xiàng)為最后一項(xiàng)項(xiàng)集效用的計(jì)算。全局HUIL-Tree的更新方式可闡述如下:

    在全局HUIL- Tree中所有項(xiàng)標(biāo)記為ip的樹(shù)結(jié)點(diǎn)將其事務(wù)指針數(shù)組中的事務(wù)標(biāo)識(shí)符傳遞給其在全局HUIL-Tree中的父結(jié)點(diǎn)。如果其父結(jié)點(diǎn)的事務(wù)指針數(shù)組不空,則將事務(wù)指針數(shù)組中的事務(wù)標(biāo)識(shí)符合并到其父結(jié)點(diǎn)的事務(wù)指針數(shù)組中。例如,在圖2的全局HUIL-Tree中,當(dāng)完成對(duì)包含項(xiàng)E項(xiàng)集的效用計(jì)算時(shí),對(duì)全局HUIL-Tree的更新如圖5所示。

    基于以上的分析,TK-HIS采用算法2挖掘流滑動(dòng)窗體上的Top-K高效用項(xiàng)集。算法2為一個(gè)迭代程序,首次調(diào)用的輸入?yún)?shù)為全局HUIL-Tree和全局效用數(shù)據(jù)庫(kù),項(xiàng)集X為空集。研發(fā)推得主要實(shí)現(xiàn)算法如下。

    2.3 更新全局HUIL-Tree和全局效用數(shù)據(jù)庫(kù)

    當(dāng)完成對(duì)流滑動(dòng)窗體中Top-K高效用項(xiàng)集的挖掘后,流滑動(dòng)窗體發(fā)生滑動(dòng),時(shí)間上最早的批數(shù)據(jù)從流滑動(dòng)窗體中移除,同時(shí)將新到達(dá)的批數(shù)據(jù)添加到流滑動(dòng)窗體中。TK-HIS在全局HUIL-Tree中維護(hù)一個(gè)指針數(shù)組,數(shù)組中的元素為指向流滑動(dòng)窗體中事務(wù)最后一項(xiàng)在全局HUIL-Tree中對(duì)應(yīng)的樹(shù)結(jié)點(diǎn),TK-HIS采用算法3完成全局HUIL-Tree和全局效用數(shù)據(jù)庫(kù)的更新。算法3的流程描述如下。

    例如,在圖1中當(dāng)流滑動(dòng)窗體SW1向SW2滑動(dòng)時(shí),B1需要從流滑動(dòng)窗體中移除,將B3添加到流滑動(dòng)窗體中。對(duì)B1中的事務(wù)例如T1,找到T1最后1項(xiàng)D在全局HUIL-Tree中對(duì)應(yīng)的結(jié)點(diǎn)ND,在其事務(wù)指針數(shù)組中移除事務(wù)標(biāo)識(shí)符T1。因ND的事務(wù)指針數(shù)組為空,同時(shí)ND為葉子結(jié)點(diǎn),刪除ND然后校驗(yàn)父結(jié)點(diǎn)NC是否滿足上述條件。NC為非葉子結(jié)點(diǎn),故停止刪除樹(shù)結(jié)點(diǎn),在頭表中移除項(xiàng)B、C和D在T1中的前綴效用2、3和7,最后移除UDB中第1條記錄。當(dāng)流滑動(dòng)窗體完成由SW1到SW2的更新后,全局HUIL-Tree和全局效用數(shù)據(jù)庫(kù)如圖6所示。

    3 性能評(píng)估

    在本節(jié)將對(duì)提出的TK-HIS進(jìn)行性能評(píng)估,并與當(dāng)前最好的流滑動(dòng)窗體上Top-K高效用項(xiàng)集挖掘算法T-HUDS進(jìn)行比較,選擇運(yùn)行時(shí)間和內(nèi)存使用峰值作為評(píng)估標(biāo)準(zhǔn)。2個(gè)算法均由C++語(yǔ)言實(shí)現(xiàn),采用g++編譯, 執(zhí)行環(huán)境為2.93 GHz Intel雙核處理器和4 G內(nèi)存的臺(tái)式機(jī),操作系統(tǒng)ubuntu12.04。

    實(shí)驗(yàn)選取了2個(gè)數(shù)據(jù)集Retail和T10I4D100K(http://fimi.ua.ac.be/)模擬流數(shù)據(jù),因數(shù)據(jù)集中未包含項(xiàng)的外部效用及項(xiàng)在事務(wù)中的內(nèi)部效用,研究采用文獻(xiàn)[2-3,6]中的性能評(píng)估方法:

    (1)將數(shù)據(jù)集中所有項(xiàng)的外部效用按對(duì)數(shù)正態(tài)分布生成0.01到10之間的隨機(jī)數(shù);

    (2)項(xiàng)的內(nèi)部效用按1到10的均勻分布隨機(jī)生成,選用數(shù)據(jù)集的統(tǒng)計(jì)特征可見(jiàn)表4。

    3.1 Retail上的實(shí)驗(yàn)評(píng)估

    在Retail模擬的數(shù)據(jù)流中,每個(gè)批數(shù)據(jù)的事務(wù)數(shù)量設(shè)置為5 000,窗體尺寸設(shè)置為8,則整個(gè)數(shù)據(jù)流產(chǎn)生11個(gè)窗體。圖7展示了2個(gè)算法的運(yùn)行時(shí)間及內(nèi)存使用峰值。從圖7 (a)中可以看出,TK-HIS的運(yùn)行時(shí)間比T-HUDS提升一個(gè)數(shù)量級(jí)。例如在k= 150時(shí),T-HUDS和TK-HIS的運(yùn)行時(shí)間為55 s和6.6 s。從圖7 (b)中可以看出,TK-HIS和T-HUDS的內(nèi)存使用峰值均比較穩(wěn)定,TK-HIS的內(nèi)存使用峰值遠(yuǎn)小于T-HUDS。例如在k = 150時(shí),T-HUDS的內(nèi)存使用峰值為T(mén)K-HIS的3.9倍。

    3.2 T10I4D100K上的實(shí)驗(yàn)評(píng)估

    在T10I4D100K模擬的數(shù)據(jù)流中,每個(gè)批數(shù)據(jù)的事務(wù)數(shù)量設(shè)置為10 000,窗體尺寸設(shè)置為5,則整個(gè)數(shù)據(jù)流產(chǎn)生6個(gè)窗體。圖8展示了2個(gè)算法的運(yùn)行時(shí)間及內(nèi)存使用峰值。從圖8 (a)中可以看出,TK-HIS的運(yùn)行時(shí)間比T-HUDS提升一個(gè)數(shù)量級(jí)。例如在k = 300時(shí),TK-HIS的運(yùn)行時(shí)間為T(mén)-HUDS的1/31。從圖8 (b)中可以看出,T-HUDS的內(nèi)存使用峰值比較穩(wěn)定,TK-HIS的內(nèi)存使用峰值遠(yuǎn)小于T-HUDS。例如當(dāng)k值為300時(shí),T-HUDS的內(nèi)存使用峰值為T(mén)K-HIS的3.4倍。

    從以上實(shí)驗(yàn)可以看出,TK-HIS的性能顯著優(yōu)于T-HUDS,這是由于T-HUDS采用首先計(jì)算Top-K高效用項(xiàng)集候選項(xiàng)集,然后計(jì)算候選項(xiàng)集的真實(shí)效用的框架。在多數(shù)情況下,候選項(xiàng)集的數(shù)量遠(yuǎn)遠(yuǎn)超過(guò)高效用項(xiàng)集,使得計(jì)算候選項(xiàng)集的真實(shí)效用耗費(fèi)了大量的運(yùn)行時(shí)間。而在TK-HIS中,通過(guò)使用本文提出的HUIL-Tree和效用數(shù)據(jù)庫(kù),項(xiàng)集在窗體中的效用可直接計(jì)算,避免了候選項(xiàng)集的生成,算法的性能顯著提升。

    4 結(jié)束語(yǔ)

    本文研究提出了一個(gè)有效的樹(shù)結(jié)構(gòu)HUIL-Tree和效用數(shù)據(jù)庫(kù)及流滑動(dòng)窗體上挖掘Top-K高效用項(xiàng)集的有效算法TK-HIS。TK-HIS采用HUIL-Tree和效用數(shù)據(jù)庫(kù)維護(hù)流滑動(dòng)窗體中項(xiàng)集及其在窗體事務(wù)中的效用,使用模式增長(zhǎng)的方法生成搜索空間中的項(xiàng)集,對(duì)每一個(gè)項(xiàng)集通過(guò)效用數(shù)據(jù)庫(kù)直接計(jì)算其在流滑動(dòng)窗體中的效用,在挖掘過(guò)程中動(dòng)態(tài)地調(diào)整當(dāng)前的最小效用閾值,避免了Top-K高效用項(xiàng)集候選項(xiàng)集的產(chǎn)生。在實(shí)驗(yàn)中,研究在真實(shí)和合成數(shù)據(jù)集模擬的數(shù)據(jù)流中評(píng)估了TK-HIS,并與當(dāng)前最好的流滑動(dòng)窗體Top-K高效用項(xiàng)集挖掘算法T-HUDS進(jìn)行比較,實(shí)驗(yàn)結(jié)果表明在稀疏數(shù)據(jù)流上TK-HIS顯著優(yōu)于T-HUDS:運(yùn)行時(shí)間可提升一個(gè)數(shù)量級(jí),同時(shí)使用更少的內(nèi)存。

    參考文獻(xiàn)

    [1] ZIHAYAT M, AN A. Mining top-k high utility patterns over data streams [J]. Information Science, 2014, 285: 138-161.

    [2] AHMED C F, TANBEER S K, JEONG B S, et al. Efficient tree structures for high utility pattern mining in incremental databases [J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(12): 1708-1721.

    [LL][3] LIU Y, LIAO W, CHOUDHARY A N. A two-phase algorithm for fast discovery of high utility itemsets [C]//Proc 9th Pacific-Asia Conf Advances in Knowledge Discovery and Data Mining. Heidelberg Berlin: Springer-Verlag, 2005: 689-695.

    [4] LI Y X, YEH J S, CHANG C C. Isolated items discarding strategy for discovering high utility itemsets [J]. Data & Knowledge Engineering, 2008, 64(1): 198-217.

    [5] TSENG V S, WU C W, SHIE B E, et al. UP-Growth: An efficient algorithm for high utility itemset mining [C]//Proc 16th ACM Conf Knowledge Discovery and Data Mining. New York: ACM Press, 2010: 253-262.

    [6] LIU M, QU J. Mining high utility itemsets without candidate generation [C]//Proc 21th ACM Conf Information and Knowledge Management. New York: ACM Press, 2012: 55-64.

    [7] GUO S, GAO H. HUITWU: An efficient algorithm for mining high utility itemsets from transaction databases [J]. Journal of Computer Science and Technology, 2016, 31(4): 776-786.

    [8] AGRAWAL R, SRIKANT R. Fast algorithms for mining association rules in large databases [C]//Proc 20th Conf Very Large Data Bases. San Francisco, CA: Morgan Kaufmann Press, 1994: 487-499.

    [9] CHU C J, TSENG V S, LIANG T.An efficient algorithm for mining temporal high utility itemsets from data streams [J]. Journal of System and Software, 2008, 81(7): 1105-1117.

    [10]LI H.MHUI-max: An efficient algorithm for discovering high-utility itemsets from data streams [J]. Journal of Information Science, 2011, 37(5): 532-545.

    [11]LI H, HUANG H, CHEN Y, et al. Memory efficient mining of high utility itemsets in data streams [C]//Proc 8th IEEE Conf Data Mining. Piscataway, NJ: IEEE Press, 2008: 881-886.

    [12]HAN J, PEI J, YIN Y. Mining frequent patterns without candidate generation [C]//Proc 2000 ACM SIGMOD Conf Management of data. New York: ACM Press, 2000: 1-12.

    [13]AHMED C F, TANBEER S K, JEONG B S, et al. Interactive mining of high utility patterns over data streams[J]. Expert System and Applications, 2012, 39(15): 11979-11991.

    [14]YUN U, RYANG H, RYU K H. High utility itemset mining with techniques for reducing overestimated utilities and pruning candidates [J]. Expert System and Applications, 2014, 41(8): 3861-3878.

    [15]LEUNG C K, KHAN Q I, LI Z, et al. CanTree: A canonical-order tree for incremental frequent-pattern mining [J]. Knowledge and Information System, 2007, 11(3): 287-311.

    猜你喜歡
    數(shù)據(jù)流
    應(yīng)用數(shù)據(jù)流分析排除起動(dòng)機(jī)不轉(zhuǎn)故障的研究
    數(shù)據(jù)流和波形診斷技術(shù)在發(fā)動(dòng)機(jī)故障診斷中的應(yīng)用
    數(shù)據(jù)流安全查詢技術(shù)綜述
    豐田卡羅拉汽車制動(dòng)時(shí)ABS系統(tǒng)“咔嚓”異響的故障排除
    城市軌道交通綜合監(jiān)控系統(tǒng)中數(shù)據(jù)庫(kù)軟件模塊的設(shè)計(jì)與分析
    發(fā)動(dòng)機(jī)高壓共軌電控系統(tǒng)的故障碼分析
    利用數(shù)據(jù)流進(jìn)行電控故障診斷的案例分析
    大眾車系發(fā)動(dòng)機(jī)存在故障的診斷與排除
    數(shù)據(jù)流技術(shù)在汽車維修中的應(yīng)用
    無(wú)源干擾裝備質(zhì)心干擾效果數(shù)字仿真試驗(yàn)軟件設(shè)計(jì)
    男女免费视频国产| 欧美日韩亚洲高清精品| 美女xxoo啪啪120秒动态图| 欧美bdsm另类| 免费av不卡在线播放| 久久国内精品自在自线图片| 久久99蜜桃精品久久| 黑人巨大精品欧美一区二区蜜桃 | 成人漫画全彩无遮挡| 成人亚洲精品一区在线观看| 水蜜桃什么品种好| 日韩三级伦理在线观看| 国产伦理片在线播放av一区| 亚洲四区av| 香蕉国产在线看| 秋霞伦理黄片| 亚洲精品久久午夜乱码| 成年美女黄网站色视频大全免费| 少妇熟女欧美另类| 啦啦啦在线观看免费高清www| 亚洲,欧美精品.| 老司机亚洲免费影院| 国产精品嫩草影院av在线观看| 日韩熟女老妇一区二区性免费视频| 日韩成人伦理影院| 巨乳人妻的诱惑在线观看| 女的被弄到高潮叫床怎么办| 亚洲精品成人av观看孕妇| 最近手机中文字幕大全| 亚洲欧美日韩卡通动漫| 男女国产视频网站| 色吧在线观看| 人人妻人人澡人人看| 色哟哟·www| 日本午夜av视频| 大香蕉久久成人网| 在线看a的网站| 波野结衣二区三区在线| 高清视频免费观看一区二区| 国产色爽女视频免费观看| 男人舔女人的私密视频| 国产在视频线精品| 国产免费视频播放在线视频| 人人妻人人添人人爽欧美一区卜| 国产亚洲午夜精品一区二区久久| 成人国语在线视频| 午夜av观看不卡| 亚洲精品乱码久久久久久按摩| 美女脱内裤让男人舔精品视频| 岛国毛片在线播放| 在线精品无人区一区二区三| 秋霞伦理黄片| 国产免费又黄又爽又色| 久久精品国产亚洲av天美| 国产精品久久久久久久久免| 久久精品夜色国产| 在线 av 中文字幕| 精品国产国语对白av| 亚洲色图综合在线观看| 国产精品女同一区二区软件| 日韩av免费高清视频| 亚洲国产精品专区欧美| 26uuu在线亚洲综合色| 国产一区二区三区av在线| 久久免费观看电影| 亚洲av欧美aⅴ国产| 在线天堂最新版资源| 大陆偷拍与自拍| 黄色一级大片看看| 国产伦理片在线播放av一区| 18+在线观看网站| 午夜视频国产福利| 亚洲国产看品久久| 国产又爽黄色视频| 老女人水多毛片| 日韩制服丝袜自拍偷拍| 飞空精品影院首页| 久久99热6这里只有精品| 亚洲国产精品成人久久小说| 亚洲四区av| 亚洲国产色片| 国产精品久久久久久精品电影小说| 精品国产国语对白av| 国产免费一区二区三区四区乱码| 一区二区三区四区激情视频| 校园人妻丝袜中文字幕| 黑人欧美特级aaaaaa片| 多毛熟女@视频| 国产亚洲午夜精品一区二区久久| 国产精品三级大全| 国产亚洲欧美精品永久| 国产欧美另类精品又又久久亚洲欧美| 少妇人妻 视频| 免费在线观看黄色视频的| 欧美人与性动交α欧美精品济南到 | 边亲边吃奶的免费视频| av.在线天堂| 熟女电影av网| 成年美女黄网站色视频大全免费| 九九在线视频观看精品| 老司机影院毛片| 成人免费观看视频高清| 亚洲人成77777在线视频| 90打野战视频偷拍视频| 波野结衣二区三区在线| 亚洲人成77777在线视频| 看十八女毛片水多多多| 色94色欧美一区二区| 女人久久www免费人成看片| 宅男免费午夜| 日韩一区二区视频免费看| 久久精品熟女亚洲av麻豆精品| h视频一区二区三区| 免费人成在线观看视频色| 国产精品三级大全| 久久久久视频综合| 黑人高潮一二区| 黑人高潮一二区| 各种免费的搞黄视频| 亚洲av男天堂| 黑人高潮一二区| 这个男人来自地球电影免费观看 | av天堂久久9| 黄片播放在线免费| 黄色怎么调成土黄色| 啦啦啦中文免费视频观看日本| 精品一区二区免费观看| 人体艺术视频欧美日本| 亚洲国产毛片av蜜桃av| 色婷婷久久久亚洲欧美| www.熟女人妻精品国产 | 一边亲一边摸免费视频| av网站免费在线观看视频| 午夜视频国产福利| 亚洲成人一二三区av| 免费观看无遮挡的男女| 精品国产一区二区久久| 午夜福利在线观看免费完整高清在| 国产xxxxx性猛交| 亚洲人与动物交配视频| 热99国产精品久久久久久7| 成年人午夜在线观看视频| 久久久久国产精品人妻一区二区| 99热6这里只有精品| 天堂俺去俺来也www色官网| 亚洲精品456在线播放app| 激情视频va一区二区三区| 国产69精品久久久久777片| 久热久热在线精品观看| 国产爽快片一区二区三区| 韩国精品一区二区三区 | 日本与韩国留学比较| 汤姆久久久久久久影院中文字幕| 两性夫妻黄色片 | 精品久久蜜臀av无| 少妇的逼好多水| 制服人妻中文乱码| 日本av手机在线免费观看| 久久 成人 亚洲| 精品久久久精品久久久| 人妻少妇偷人精品九色| 久久99热6这里只有精品| 久久久久久久国产电影| 新久久久久国产一级毛片| 日本欧美视频一区| 在线精品无人区一区二区三| 免费高清在线观看日韩| 男女免费视频国产| 大香蕉久久成人网| 亚洲国产av影院在线观看| 午夜久久久在线观看| 色视频在线一区二区三区| 99久久综合免费| 亚洲欧美中文字幕日韩二区| 天堂俺去俺来也www色官网| 97在线人人人人妻| 精品一品国产午夜福利视频| kizo精华| 国产精品一区二区在线观看99| 亚洲欧美精品自产自拍| 国产精品成人在线| 国产麻豆69| 欧美国产精品一级二级三级| 久久97久久精品| 国产精品嫩草影院av在线观看| 久久久精品区二区三区| 精品亚洲乱码少妇综合久久| 午夜视频国产福利| 亚洲中文av在线| 中文字幕人妻丝袜制服| 丝袜人妻中文字幕| 日本wwww免费看| 男女边吃奶边做爰视频| 日日摸夜夜添夜夜爱| 久久久久网色| 婷婷成人精品国产| 国产精品久久久av美女十八| 高清视频免费观看一区二区| 国产av码专区亚洲av| 视频在线观看一区二区三区| 午夜av观看不卡| 亚洲综合色网址| 亚洲欧洲精品一区二区精品久久久 | 黑人高潮一二区| 午夜免费鲁丝| 国产精品熟女久久久久浪| 美女视频免费永久观看网站| 午夜影院在线不卡| 国产探花极品一区二区| 中文字幕人妻丝袜制服| 男人操女人黄网站| 国产男人的电影天堂91| 男男h啪啪无遮挡| 九色亚洲精品在线播放| 国产爽快片一区二区三区| 久久久欧美国产精品| 国产在线视频一区二区| 精品熟女少妇av免费看| 婷婷色综合大香蕉| 三级国产精品片| 国产亚洲精品第一综合不卡 | 日韩三级伦理在线观看| 亚洲色图综合在线观看| 亚洲欧美中文字幕日韩二区| 亚洲精品一区蜜桃| 久久久欧美国产精品| 亚洲欧美精品自产自拍| 国产熟女午夜一区二区三区| 国产精品免费大片| 国精品久久久久久国模美| 最近2019中文字幕mv第一页| videos熟女内射| 欧美人与善性xxx| 肉色欧美久久久久久久蜜桃| 精品国产一区二区久久| 久久ye,这里只有精品| 夜夜骑夜夜射夜夜干| 成人二区视频| 久久精品熟女亚洲av麻豆精品| 欧美日韩综合久久久久久| 久久99精品国语久久久| 国产成人精品婷婷| 校园人妻丝袜中文字幕| 久久精品夜色国产| 国产精品久久久av美女十八| 亚洲精品美女久久av网站| 久久免费观看电影| 18禁裸乳无遮挡动漫免费视频| 久久青草综合色| 51国产日韩欧美| 又黄又爽又刺激的免费视频.| 黄色配什么色好看| a级毛片在线看网站| 国产一区亚洲一区在线观看| 国产高清国产精品国产三级| 两个人看的免费小视频| 国内精品宾馆在线| 久久久久久人人人人人| 国产成人午夜福利电影在线观看| 免费高清在线观看日韩| 日本午夜av视频| 国产视频首页在线观看| 一本大道久久a久久精品| 国产深夜福利视频在线观看| 国产成人一区二区在线| 国产女主播在线喷水免费视频网站| 国产精品秋霞免费鲁丝片| 中文字幕最新亚洲高清| a 毛片基地| 免费黄频网站在线观看国产| 免费看光身美女| 成人手机av| 午夜激情久久久久久久| av电影中文网址| 亚洲av在线观看美女高潮| 久久精品国产亚洲av涩爱| 欧美精品一区二区大全| 亚洲精品乱久久久久久| 久久97久久精品| 蜜桃国产av成人99| 国产不卡av网站在线观看| 制服丝袜香蕉在线| 成人国产av品久久久| 精品国产乱码久久久久久小说| 国产精品欧美亚洲77777| 女性被躁到高潮视频| 国产亚洲av片在线观看秒播厂| 99re6热这里在线精品视频| 亚洲精品日韩在线中文字幕| 亚洲av男天堂| 男男h啪啪无遮挡| 狠狠精品人妻久久久久久综合| 亚洲国产精品999| 天天操日日干夜夜撸| 一本—道久久a久久精品蜜桃钙片| 美女福利国产在线| 蜜桃国产av成人99| 亚洲欧美成人精品一区二区| 亚洲精品视频女| 精品久久国产蜜桃| 最近手机中文字幕大全| 极品少妇高潮喷水抽搐| 国产在线免费精品| 91aial.com中文字幕在线观看| 中国国产av一级| 国产日韩欧美视频二区| 人妻 亚洲 视频| 欧美xxⅹ黑人| 亚洲一级一片aⅴ在线观看| 美国免费a级毛片| av在线app专区| 久久久久久久久久久免费av| 成人国产麻豆网| 亚洲精品av麻豆狂野| 亚洲精品中文字幕在线视频| 深夜精品福利| av在线观看视频网站免费| 久久影院123| 一二三四在线观看免费中文在 | 亚洲中文av在线| 久久精品久久久久久噜噜老黄| 高清不卡的av网站| 在线观看www视频免费| 国产不卡av网站在线观看| 午夜日本视频在线| 国产视频首页在线观看| 欧美xxxx性猛交bbbb| 国产精品国产av在线观看| 国产女主播在线喷水免费视频网站| 国产精品人妻久久久影院| 午夜老司机福利剧场| 乱码一卡2卡4卡精品| 国产乱来视频区| 18禁国产床啪视频网站| 国产黄色免费在线视频| 色哟哟·www| 亚洲国产精品成人久久小说| 久久精品熟女亚洲av麻豆精品| 男女下面插进去视频免费观看 | 18禁观看日本| 国产一区二区激情短视频 | 久久久精品区二区三区| 亚洲国产精品999| 黄片无遮挡物在线观看| 狂野欧美激情性xxxx在线观看| 亚洲精品成人av观看孕妇| 日韩成人伦理影院| 午夜av观看不卡| 青青草视频在线视频观看| 99热这里只有是精品在线观看| 热99久久久久精品小说推荐| 不卡视频在线观看欧美| 亚洲美女黄色视频免费看| 青青草视频在线视频观看| 女人被躁到高潮嗷嗷叫费观| 免费看光身美女| 亚洲欧洲国产日韩| 最后的刺客免费高清国语| 少妇精品久久久久久久| 寂寞人妻少妇视频99o| 2018国产大陆天天弄谢| 少妇 在线观看| 熟女av电影| 香蕉国产在线看| 国产1区2区3区精品| 黑人巨大精品欧美一区二区蜜桃 | 综合色丁香网| 亚洲国产成人一精品久久久| 五月开心婷婷网| www.色视频.com| 欧美 亚洲 国产 日韩一| 国产xxxxx性猛交| 亚洲精品aⅴ在线观看| 亚洲av福利一区| 久久久久网色| 亚洲精品久久成人aⅴ小说| 一级片免费观看大全| 九色成人免费人妻av| 成年人午夜在线观看视频| 精品一品国产午夜福利视频| 久久久亚洲精品成人影院| 国产视频首页在线观看| 亚洲精品第二区| 午夜福利,免费看| 欧美日韩精品成人综合77777| 一区二区三区四区激情视频| 欧美成人午夜免费资源| 成人亚洲欧美一区二区av| 日本免费在线观看一区| 免费在线观看黄色视频的| 一二三四中文在线观看免费高清| 飞空精品影院首页| 欧美日本中文国产一区发布| 2022亚洲国产成人精品| 大码成人一级视频| 免费日韩欧美在线观看| 精品视频人人做人人爽| 亚洲第一区二区三区不卡| 亚洲国产欧美在线一区| 亚洲婷婷狠狠爱综合网| 丁香六月天网| 国产成人精品久久久久久| 我的女老师完整版在线观看| 午夜福利影视在线免费观看| 免费黄频网站在线观看国产| 欧美日韩一区二区视频在线观看视频在线| 一级毛片 在线播放| 国产精品久久久久久精品电影小说| 80岁老熟妇乱子伦牲交| 熟妇人妻不卡中文字幕| 全区人妻精品视频| 搡女人真爽免费视频火全软件| 精品一区在线观看国产| 午夜精品国产一区二区电影| 国产在线免费精品| 亚洲av男天堂| av天堂久久9| 97人妻天天添夜夜摸| tube8黄色片| 久久女婷五月综合色啪小说| 五月玫瑰六月丁香| 啦啦啦啦在线视频资源| 国产欧美亚洲国产| 日韩中文字幕视频在线看片| 51国产日韩欧美| 久久久久精品人妻al黑| 亚洲av男天堂| 在线观看免费高清a一片| 久久久国产精品麻豆| 免费不卡的大黄色大毛片视频在线观看| 97精品久久久久久久久久精品| 欧美激情 高清一区二区三区| 69精品国产乱码久久久| 午夜91福利影院| 亚洲三级黄色毛片| 美女主播在线视频| 春色校园在线视频观看| 国产淫语在线视频| 波多野结衣一区麻豆| 一本久久精品| 免费看不卡的av| 国产欧美日韩综合在线一区二区| 我要看黄色一级片免费的| 日韩欧美精品免费久久| 久久婷婷青草| 国产欧美日韩综合在线一区二区| 人妻人人澡人人爽人人| 国产精品不卡视频一区二区| 搡女人真爽免费视频火全软件| 亚洲国产精品成人久久小说| 99国产精品免费福利视频| 我的女老师完整版在线观看| 三级国产精品片| 波野结衣二区三区在线| 亚洲av福利一区| 女人被躁到高潮嗷嗷叫费观| 欧美xxⅹ黑人| 国产成人av激情在线播放| av黄色大香蕉| 亚洲精品,欧美精品| 亚洲成人手机| 亚洲精华国产精华液的使用体验| 久久久久久伊人网av| 免费黄色在线免费观看| 久久久久久久久久久免费av| 久久久国产一区二区| 欧美 日韩 精品 国产| av.在线天堂| 视频中文字幕在线观看| 日韩视频在线欧美| 欧美日韩视频精品一区| 国产精品三级大全| 丝袜在线中文字幕| 交换朋友夫妻互换小说| av国产精品久久久久影院| 日本欧美视频一区| 美女主播在线视频| 国产精品久久久久久精品电影小说| 五月开心婷婷网| www.熟女人妻精品国产 | 欧美日韩一区二区视频在线观看视频在线| 欧美精品av麻豆av| 久久久a久久爽久久v久久| 这个男人来自地球电影免费观看 | 亚洲,欧美,日韩| 亚洲国产av新网站| 激情视频va一区二区三区| 插逼视频在线观看| xxxhd国产人妻xxx| 国产免费又黄又爽又色| 欧美人与性动交α欧美精品济南到 | 秋霞伦理黄片| 亚洲综合色惰| 久久久精品区二区三区| 满18在线观看网站| 18禁在线无遮挡免费观看视频| 国产又色又爽无遮挡免| 七月丁香在线播放| 亚洲成人一二三区av| 国产成人精品无人区| 一二三四中文在线观看免费高清| 日韩精品免费视频一区二区三区 | 精品久久国产蜜桃| 国产在线一区二区三区精| 这个男人来自地球电影免费观看 | 十八禁网站网址无遮挡| 高清av免费在线| 精品亚洲乱码少妇综合久久| 亚洲精品,欧美精品| 99久久精品国产国产毛片| 精品酒店卫生间| 丰满乱子伦码专区| av黄色大香蕉| 国产精品偷伦视频观看了| a 毛片基地| 欧美最新免费一区二区三区| 亚洲av电影在线观看一区二区三区| 久久国产精品男人的天堂亚洲 | 黄色毛片三级朝国网站| 国产高清三级在线| 日韩制服骚丝袜av| 在线观看www视频免费| 男的添女的下面高潮视频| 好男人视频免费观看在线| 伦精品一区二区三区| √禁漫天堂资源中文www| 极品少妇高潮喷水抽搐| 婷婷色综合大香蕉| 国产黄色视频一区二区在线观看| 日本-黄色视频高清免费观看| 国精品久久久久久国模美| 国产午夜精品一二区理论片| 少妇人妻精品综合一区二区| 亚洲精品美女久久久久99蜜臀 | 精品一区二区免费观看| 黄色视频在线播放观看不卡| 亚洲人成77777在线视频| 人人澡人人妻人| 久久久欧美国产精品| 黑人高潮一二区| 十八禁高潮呻吟视频| 成人黄色视频免费在线看| 日韩一区二区三区影片| 1024视频免费在线观看| 国产精品熟女久久久久浪| 九九在线视频观看精品| 久久 成人 亚洲| 久久鲁丝午夜福利片| 亚洲情色 制服丝袜| 国产又色又爽无遮挡免| 亚洲av福利一区| tube8黄色片| 亚洲欧洲国产日韩| 久久久久久久大尺度免费视频| 最新的欧美精品一区二区| 欧美xxxx性猛交bbbb| 日本黄大片高清| 高清欧美精品videossex| 国产成人精品福利久久| 国产精品一区二区在线不卡| 一区二区日韩欧美中文字幕 | 一二三四中文在线观看免费高清| 国产毛片在线视频| 色哟哟·www| 精品一品国产午夜福利视频| 亚洲成国产人片在线观看| 久久精品国产亚洲av天美| 亚洲美女黄色视频免费看| 丰满饥渴人妻一区二区三| 大话2 男鬼变身卡| 黄片播放在线免费| 免费在线观看完整版高清| 久久久久人妻精品一区果冻| 男女无遮挡免费网站观看| 久久久久视频综合| 亚洲av在线观看美女高潮| 一区二区av电影网| 欧美亚洲日本最大视频资源| 国产 一区精品| 秋霞在线观看毛片| 日韩人妻精品一区2区三区| 婷婷色综合www| 国产有黄有色有爽视频| 在线观看美女被高潮喷水网站| av在线老鸭窝| 只有这里有精品99| 一区二区三区乱码不卡18| 国产不卡av网站在线观看| 日韩不卡一区二区三区视频在线| 一级毛片我不卡| 国产又色又爽无遮挡免| 亚洲国产精品专区欧美| 国产成人aa在线观看| 女人久久www免费人成看片| 有码 亚洲区| 国产精品久久久久久久久免| 人体艺术视频欧美日本| 精品第一国产精品| 新久久久久国产一级毛片| 2022亚洲国产成人精品| av电影中文网址| 欧美人与善性xxx| 日韩av免费高清视频| 国产在线一区二区三区精| 日韩av在线免费看完整版不卡| 日韩欧美精品免费久久| 尾随美女入室| 亚洲成国产人片在线观看| 国产精品蜜桃在线观看| 女人久久www免费人成看片| 国产亚洲欧美精品永久| 久久人人97超碰香蕉20202| 日韩一本色道免费dvd| 男人爽女人下面视频在线观看| 母亲3免费完整高清在线观看 |