在流滑动窗体上挖掘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.