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

郭世明 金代亮 高宏

摘 要：數(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.