郭世明 金代亮 高宏

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

關(guān)鍵詞：Top-K高效用項集； 模式增長； 數(shù)據(jù)流； 效用挖掘； 滑動窗體

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

（1）項在數(shù)據(jù)流中的權(quán)重未被考慮；

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

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

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

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

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

（1）第一階段生成的候選項集數(shù)量巨大，消耗了大量的內(nèi)存空間；

（2）計算第一階段生成候選項集的真實效用耗時巨大。

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

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

（2）提出了一個挖掘流滑動窗體上Top-K高效用項集的有效算法TK-HIS （Top-K High utility Itemset mining over a stream Siding window）?；跇?gòu)建的HUIL-Tree和效用數(shù)據(jù)庫，TK-HIS采用模式增長的方法生成搜索空間中的項集，對每1個項集直接計算其在流滑動窗體中的效用，避免了Top-K高效用項集候選項集的生成；

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

1 背景知識

1.1 問題描述

1.2 相關(guān)工作

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

2 在流滑動窗體上挖掘Top-K高效用項集

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

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

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

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

（1）由一個根結(jié)點（標(biāo)記為null）、項前綴子樹集（作為根結(jié)點的子女）和一個頭表組成；

（2）項前綴子樹中的每個結(jié)點包括3個域：項標(biāo)記、結(jié)點鏈接和事務(wù)指針數(shù)組。其中，結(jié)點鏈接是指連接樹中具有相同項標(biāo)記的下一個樹結(jié)點，事務(wù)指針是指對效用數(shù)據(jù)庫中事務(wù)的鏈接；

（3）頭表中的每條記錄包含3個域：項標(biāo)記、項在流滑動窗體中的前綴效用及指向樹中第一個具有相同項標(biāo)記的樹結(jié)點的指針。

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

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

2.2 提出的挖掘方法TK-HIS

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

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

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

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

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

2.2.2 挖掘Top-K高效用項集

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

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

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

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

（1）通過遍歷全局HUIL-Tree中與ip相關(guān)的路徑，生成{ip}的條件模式庫；

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

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

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

2.2.2.1 生成條件模式庫

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

（1）遍歷頭表中由項標(biāo)記為ip的記錄出發(fā)的結(jié)點鏈接，收集結(jié)點鏈接上的樹結(jié)點；

（2）由（1）中的樹結(jié)點到全局HUIL-Tree根結(jié)點形成路徑所代表的項集，形成{ip}的條件模式庫；

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

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

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

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

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

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

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

（1）{ip}條件模式樹的根結(jié)點標(biāo)記為{ip}，也就是條件項集；

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

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

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

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

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

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

2.2.2.4 更新全局HUIL-Tree

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

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

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

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

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

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

3 性能評估

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

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

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

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

3.1 Retail上的實驗評估

在Retail模擬的數(shù)據(jù)流中，每個批數(shù)據(jù)的事務(wù)數(shù)量設(shè)置為5 000，窗體尺寸設(shè)置為8，則整個數(shù)據(jù)流產(chǎn)生11個窗體。圖7展示了2個算法的運行時間及內(nèi)存使用峰值。從圖7 （a）中可以看出，TK-HIS的運行時間比T-HUDS提升一個數(shù)量級。例如在k= 150時，T-HUDS和TK-HIS的運行時間為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時，T-HUDS的內(nèi)存使用峰值為TK-HIS的3.9倍。

3.2 T10I4D100K上的實驗評估

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

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

4 結(jié)束語

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