在流滑動窗體上挖掘Top—K高效用項集的有效算法

郭世明 金代亮 高宏

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

關鍵詞：Top-K高效用項集； 模式增長； 數據流； 效用挖掘； 滑動窗體

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

引言

數據流上的頻繁項集挖掘（Frequent Itemset Mining over Data Streams， FIM-DS）是數據挖掘中一個重要的研究課題，并在現實生活中應用廣泛。FIM-DS是指在數據流中尋找支持度（數據流中包含項集的事務數量）不小于用戶指定最小支持閾值的所有項集。可是FIM-DS存在2個限制：

（1）項在數據流中的權重未被考慮；

（2）項在每條事務中的數量未被考慮。

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

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

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

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

（1）第一階段生成的候選項集數量巨大，消耗了大量的內存空間；

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

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

（1）提出了一個新的數據結構HUIL-Tree （High Utility Itemset Tree which arranges items according to Lexicographic order），用于存儲流滑動窗體中的項集。同時，采用一個效用數據庫存儲項集在流滑動窗體內每條事務中的效用；

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

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

1 背景知識

1.1 問題描述

1.2 相關工作

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

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

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

2.1 HUIL-Tree和效用數據庫

TK-HIS采用樹結構HUIL-Tree和效用數據庫存儲流滑動窗體中項集及其在窗體事務中的效用，效用數據庫為一個一維數組，其長度為流滑動窗體內所有項在事務中出現的頻度和。

定義10 HUIL-Tree HUIL-Tree是滿足下列條件的一個樹結構。

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

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

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

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

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

2.2 提出的挖掘方法TK-HIS

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

2.2.1 閾值提升技術研究

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

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

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

2.2.2 挖掘Top-K高效用項集

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

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

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

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

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

（2）基于{ip}條件模式庫中的信息構建{ip}的條件模式樹及{ip}的條件效用數據庫；

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

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

2.2.2.1 生成條件模式庫

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

（1）遍歷頭表中由項標記為ip的記錄出發的結點鏈接，收集結點鏈接上的樹結點；

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

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

2.2.2.2 構建條件HUIL-Tree和條件效用數據庫

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

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

例如在圖1的數據流中項集{BC}在流滑動窗體SW1中的事務權重值TWU（{BC}） =TU（T1） + TU（T3） = 13。

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

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

（1）{ip}條件模式樹的根結點標記為{ip}，也就是條件項集；

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

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

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

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

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

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

2.2.2.4 更新全局HUIL-Tree

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

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

基于以上的分析，TK-HIS采用算法2挖掘流滑動窗體上的Top-K高效用項集。算法2為一個迭代程序，首次調用的輸入參數為全局HUIL-Tree和全局效用數據庫，項集X為空集。研發推得主要實現算法如下。

2.3 更新全局HUIL-Tree和全局效用數據庫

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

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

3 性能評估

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

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

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

（2）項的內部效用按1到10的均勻分布隨機生成，選用數據集的統計特征可見表4。

3.1 Retail上的實驗評估

在Retail模擬的數據流中，每個批數據的事務數量設置為5 000，窗體尺寸設置為8，則整個數據流產生11個窗體。圖7展示了2個算法的運行時間及內存使用峰值。從圖7 （a）中可以看出，TK-HIS的運行時間比T-HUDS提升一個數量級。例如在k= 150時，T-HUDS和TK-HIS的運行時間為55 s和6.6 s。從圖7 （b）中可以看出，TK-HIS和T-HUDS的內存使用峰值均比較穩定，TK-HIS的內存使用峰值遠小于T-HUDS。例如在k = 150時，T-HUDS的內存使用峰值為TK-HIS的3.9倍。

3.2 T10I4D100K上的實驗評估

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

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

4 結束語

本文研究提出了一個有效的樹結構HUIL-Tree和效用數據庫及流滑動窗體上挖掘Top-K高效用項集的有效算法TK-HIS。TK-HIS采用HUIL-Tree和效用數據庫維護流滑動窗體中項集及其在窗體事務中的效用，使用模式增長的方法生成搜索空間中的項集，對每一個項集通過效用數據庫直接計算其在流滑動窗體中的效用，在挖掘過程中動態地調整當前的最小效用閾值，避免了Top-K高效用項集候選項集的產生。在實驗中，研究在真實和合成數據集模擬的數據流中評估了TK-HIS，并與當前最好的流滑動窗體Top-K高效用項集挖掘算法T-HUDS進行比較，實驗結果表明在稀疏數據流上TK-HIS顯著優于T-HUDS：運行時間可提升一個數量級，同時使用更少的內存。

參考文獻

[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.