论文部分内容阅读
摘要:根据数据流的海量特性和时变特性，提出一种基于事务链表组的数据流频繁集挖掘算法T-Stream。在变尺度滑动窗口机制下，该算法采用改进事务链表组的概要数据结构，能够根据数据流的数据分布变化自适应调整窗口大小。仿真实验结果表明，T-Stream相比Manku算法提高了挖掘数据流频繁集的时间与空间效率。
关键词: 数据流；事务链表组；频繁集；变尺度滑动窗口
中图分类号：TP311文献标识码：Adoi:10.3969/j.issn.1003-6970.2010.10.015
Improved Transaction List Group Based Frequent Itemsets Mining Algorithm Based Frequent Itemsets Mining Algorithm On Data Streams
ZHANG Xueli 1
(1. Computer Science And Technology School , China University of Mining and Technology,Xuzhou 221116,Jiangsu)
Abstract: According to the characteristics of mass and time-varying for data, a improved transaction list group based frequent itemsets mining algorithm T-Stream upon data streams is proposed. The algorithm could self-adaptively adjust the size of time windows. In the algorithm, transaction list group is adopted as synopsis data structure. The experiments indicate that the T-Stream algorithm is more effective than the Manku algorithm in term of temporal and spatial performance.
Key words: Data stream; Transaction list group; Frequent itemsets; Variable slide window
1. 引言
近年来，在很多应用领域中，出现了一种新的数据模式，其数据不是以传统的有限数据集形式，而是以连续的数据流形式出现，这些应用领域包括传感器网络、电信数据管理、网络安全和金融数据在线分析等。起源于20世纪 90年代的关联规则是数据挖掘的一个核心课题。与基于统计回归等数学方法进行数据分析不同，关联规则显得隐蔽而难以直接发现。挖掘关联规则的关键步骤是从数据中得到满足一定支持度的频繁项集。经典的 Apriori 算法通过分析购物篮事务数据得到该事务数据库上的频繁项集[1]。Han等[2]提出的FP-Growth算法进一步提高了挖掘频繁项集的性能。然而,这些频繁项集挖掘算法都需要多次扫描数据，不能满足数据流挖掘的要求。
国内外学者在数据流的频繁项集挖掘上提出了许多算法，他们都是针对传统数据挖掘技术的多次扫描数据进行改进或者提出新的思路。如Manku等[3]首次使用近似算法进行数据流的频繁项集挖掘，该方法仅需一次扫描数据，并且通过牺牲挖掘结果的精确性来提高挖掘的效率。但该算法挖掘的是整个历史数据流上的频繁项集，而在许多情况下，用户仅关心最近数据上的频繁项集；且该算法使用缓存技术 ,占用大量的内存空间。由于用户对最近的数据兴趣度更高，一些基于此要求的数据处理机制，如滑动窗口方法和数据衰减方法被成功地应用于数据流挖掘。文献[7]提出一种改进的FP树结构 ,能够有效挖掘具有长频繁模式的数据流。
根据以上问题，本文提出一种基于事务链表组的数据流频繁集挖掘算法T-Stream。该算法根据数据流本身的变化在变尺度时间窗口上进行自适应调整，采用改进事务链表组的概要数据结构，同时利用近似技术一次扫描数据快速得到频繁项集。理论分析和仿真实验均表明，T-Stream在时间和空间效率上得到了提高。
2. 基本概念和技术
2.1 变尺度滑动窗口
在以往数据流挖掘算法中,很多算法基于不变的滑动窗口机制,在时空复杂度等性能方面取得了较大成果.但这些技术大都忽略了具体问题中数据流的时变特性,当数据分布特征不断变化时,很难实现模型的自适应调整[4 ,5 ,8 ]。文献[9]对于任意时间序列上的变化，如果该序列变化在同一区间可以认为是微小变化，在计算时其权重应考虑降低，且此处可以是时间窗口的划分点；反之如果该区间变化明显，则此处应考虑加大计算权重，且不应该是时间窗口的划分点由此，在计算出有关时间窗口宽度时尽可能地保留了原序列中极值等重要特征信息的变化过程在此基础上，针对区间极值对数据对比的影响设定比较权值因子，使对比结果对均值平稳的独立噪声干扰不敏感或比较敏感该方法较其他方法，表现更快速，更准确。
变尺度时间窗口是根据数据流的流速变化以及数据分布的变化自适应地调整时间窗口大小,以达到最小的内存空间和处理时间的消耗。
2.2 问题描述
数据流是以时序不断出现的有序的项目序列，与传统的静态数据不同,数据流是连续的、 无边界的，通常高速地出现,并且随时间变化数据分布特征不断变化.在一般的变尺度滑动时间窗口下，数据流频繁项集挖掘可以形式化描述如下：
令数据流DS是由
无限的事务块构成的序列,每个事务块关联一个时间窗口,令 是最近的事务块。每个
事务块是由一组事务构成的集合，
假设每个块的事务数不一定相等。因此，数据流在时间域上的长度是
，其中
表示集合
的基数。给定最小支持度 s ，一个项集 X 在时
间域上是频繁项集,当且仅当
。所以给定一个最小
支持度，数据流上频繁项集挖掘问题规约到使用尽可能少的时间和空间消耗来发现一定时间域上所有的频繁项集。变尺度滑动窗口的窗口尺寸是根据数据流的流速变化来确定的。当流速很快时，及时缩小滑动窗口的长度；而当流速很慢时，实时地增长滑动窗口的长度。
2.3 概要数据结构
数据流挖掘在考虑时间效率的同时，也需要尽可能少地使用内存空间。Borgelt[10]在人工合成数据集和真实数据集上的实验表明，事务链表组数据结构能表现出比 Apriori 算法[1]和 FP-growth算法[2]更好的空间性能。将事务链表组的概要数据结构记为TLG。相关定义如下：
1) 事务链表组中的每个元素entry定义为(item , f ,Δ, list ) 。其中item为数据流中的一个单项，f记录了item的频繁度，Δ代表f中最大可能的出错数，而list记录的是以item为首项的项集链表。这些entry在本文中记为表头元素。
2) list中的每个元素entry定义为(itemset , f ,Δ) 。其中itemset为数据流中以该事务链头元素为首项的项集，f记录了itemset的频繁度，Δ代表f中最大可能的出错数。例如一个头元素entry为( a ,5 ,5 , list) ,list中每个项集的 entry又为( acd ,5 ,3) , ( abd ,10 ,3) 等,
如图1所示。
为进一步降低算法运行时的空间消耗, 在T-Stream算法中 ,改进事务链表组的概要数据结构，记为TL GⅡ，如图2所示。其思路是基于自然数中素数的特征,在该数组中,每个项用一个唯一的素数表示，每个项集用该项集所组成的项所对应的素数乘积表示.在建立事务链表组TLGⅡ时,按照表1转换相应的项与项集。
这种采用素数映射的方法在许多文献中被采用，如文献[11]。在TLGⅡ中，项与项集用相应的素数和素数积表示，对于大量持续的数据流而言，能更有效地减少内存空间的消耗。当然，随着项的数目的增加，素数积会逐渐增大。如果整数存储为4个字节，则TLGⅡ的方式可支持长度为10的项集，足够保证常规的频繁集挖掘。但当项集长度超过10时，则不能采用 TL GⅡ的数据结构，而应选用TL G的方式。
3. T-Stream算法
T-Stream算法的主要思想是：对持续不断的数据流,根据流速确立不同尺度的时间窗口,建立并维护一个事务链表组的概要数据结构(如后面的图3(a)所示)。同时对数据流中的每个事务计数，然后对事务链表组进行更新和修剪。一旦从客户端发送对频繁项集的请求时，T-Stream 算法将根据事务链表组输出挖掘结果。为了方便读者理解以TL G为例作为数据流的概要数据结构，基于TLGⅡ的T-Stream 算法描述,仅需要在输入和输出时作相应的素数映射与解码操作。T-Stream算法描述如下：
Input : DS;
User-defined support thresholds ; errorrateε.
Output : A set of f requent items and itemsets
1) Initialization:TLG←;Items←;Itemsets←; bcurrent←1
2) Foreach Batches e ←next itemset ;
3) UPDATE( e , f ,Δ, s ,ε ) ;
4)if BatchEnd doPRUNE(TLG,bcurrent);
5) bcurrent ←bcurrent + 1
6) endif
算法中的变量含义如下：s是用户定义的支持度阈值或称最小支持度；ε是近似计数的误差，一般设为最小支持度的十分之一或百分之一；bcurrent是桶的标记；变量Item和Itemset 分别表示输出的频繁项和频繁项集。下面给出算法的详细过程。
Step1：每个不同尺度的时间窗口对应一个桶，每个桶存放一个事务数据块，如 。将读入
的事务数据流存到该时间窗口所
对应的桶中。每个桶的宽度不需要相同，每个桶最多存放w= [1/ε]个事务。每个桶有唯一的标志bcurrent，初始值为1。当跳转到下一个时间窗口时，桶的标志增1。
Step2：为数据流中到当前时刻出现的每个单项创建一个单项数据链表e。每个entry为(item, f,Δ, list)，list中保存的是以首项为前缀的项集，list中元素entry定义为(itemset , f ,Δ)。
Step3：当一个新的项集e到达时，如果事务链表组中存在e ，则找到e的首项所对应的事务链，使e的频度加1，并将e的Δ值更新为事务链表中e的超集的最小Δ值。当一个新的项集e到达时，如果事务链表组中不存在e，则找到e的首项所对应的事务链，将(e , f , bcurrent - 1) 加入事务链表组中。另外在当前事务链中更新现存的e的子项集频度。如果e是唯一单项，则需要建立新的头元素。
Step4 ：剪枝操作在时间窗口跳转时发生，对于任何项( e , f ,Δ) ，如果f +Δ≤bcurrent,则删除。删除方法为扫描事务链表组TLG的每个事务链，如果某事务链中有项集e的entry ,且满足f +Δ≤bcurrent ，则将e从TLG中脱离.把该事务链中的所有脱离的项集去除首项，并以该条事务链的所有脱离项集来创建一个临时的事务链表组TLG′，同时更新频度。一条事务链表扫描完毕后，把TL G′合并到TL G，在合并过程中更新相应项集的频度。合并完后回收TLG′占用的内存，最后得到新的事务链表组TL G。依次循环，直到挖掘完最后一个事务链表后结束。事务链表组的剪枝与合并如图3(b)，3 (c) 所示。
Step5：当收到对挖掘频繁项集结果的请求后，输出满足f ≥( s -ε)的entry的项集。输出方法为扫描事务链表组的一个内存副本TLG*的每个事务链，如果某事务链中有项集e的 entry，且满足f ≥( s -ε)，则输出频繁项集。项集输出后将e从TLG*中脱离，并以该条事务链的所有脱离项集来创建一个临时的事务链表组TLG′，同时更新频率。一条事务链表扫描完毕后，把TL G′合并到TL G*，在合并过程中更新相应项集的频率。合并完后回收 TL G′所占内存，最后得到新的事务链表组TLG*。依次循环，直到挖掘完最后一个事务链表后结束，此时已经输出了所有挖掘出的频繁项集，最后回收副本TLG3*的内存。
4. 实验结果与分析
4.1 实验结果
实验数据来源于IBM数据产生器(http://www.almaden.ibm.com/software/quest/ Resources/index.shtml)。按照平均事务长度,平均频繁集长度和事务数这3个参数分别生成多组数据集。取平均事务长度为4 ,7 ,10 ,平均频繁集长度为2,4,6。误差阈值始终取值为最小支持度的0.1。
实验过程中，每个窗口的事务数有较大的差别。Manku采用的是等宽度的时间窗口 ，而T-Stream算法采用变尺度滑动窗口，根据事务数的多少设置窗口大小。实验中算法程序的输入就是按照不同窗口大小设置不同数量的事务数。
对T-Stream算法随事务数变化和最小支持度变化在挖掘时间和内存消耗上进行了实验。另外，本文还实现了Manku算法用来进行性能对比实验。图4 (a) 给出了基于TLG的T-Stream算法当事务数在10～50万之间变化时，不同支持度下的算法运行时间的比较。图4(b)给出了T-Stream算法与缓冲内存分别是30M和40M的Manku算法之间的运行时间比较。图4 (c)给出了基于TLG和TLGⅡ的T-Stream算法随支持度变化的空间效率变化。图4 (d)给出了当最小支持度分别为0.01和0.1时，T-Stream算法随事务数变化的内存消耗。
4.2 实验结果分析
从图4(a)中可以看出T-Stream算法与最小支持度和挖掘事务数之间的关系。挖掘相同的事务数，最小支持度越低，运行时间越长。这是因为最小支持度越低，挖掘相同事务数会产生越多的频繁集。对于同一支持度，越多的事务数则含有越多的频繁项集，运行时间越长。
从图4(b)中可以看出，与Manku算法相比，T-Stream算法明显提高了挖掘频繁集的时间效率。这是因为T-Stream算法采用变尺度滑动窗口，根据4.2实验结果分析从图4(a)中可以看出T-Stream算法与最小支持度和挖掘事务数之间的关系。挖掘相同的事务数，最小支持度越低，运行时间越长。这是因为最小支持度越低，挖掘相同事务数会产生越多的频繁集。对于同一支持度，越多的事务数则含有越多的频繁项集，运行时间越长。
从图4(b)中可以看出，与Manku算法相比，T-Stream算法明显提高了挖掘频繁集的时间效率。这是因为T-Stream算法采用变尺度滑动窗口 ,根据事务数的多少设置窗口大小实验中算法程序的输入就是按照不同窗口大小设置不同数量的事务数，从而表现出较高的运行效率。TLG的数据结构具有很高的空间优越性，它不需要缓冲存储区的辅助空间。如实验中Manku算法需要30M和更高的缓存,而T-Stream仅需要几兆的内存消耗。因此，与Manku算法需要较多的缓冲内存相比，T-Stream算法的事务链表组的数据结构能有效降低内存的消耗。
从图4(c)，4(d)的实验结果中可进一步看出TLGⅡ在空间性能上的提高。图4(c)给出了分别挖掘10万个和50万个事务，基于TLG与TLGⅡ的T-Stream算法随最小支持度变化的内存消耗变化。图4(d)给出了分别设置最小支持度为0.01和0.1时，基于TLG与TLGⅡ的T-Stream算法随挖掘事务数变化的内存消耗变化。实验结果表明，在挖掘大量的事务数时或者在最小支持度较小时，TLGⅡ相比TLG在内存开销上的优势更加明显。
5. 结论
本文同时考虑数据流的海量特性和时变特性，提出了一种基于改进事务链表的数据流频繁集挖掘算法T-Stream，能在变尺度的时间窗口上挖掘频繁项集。算法采用近似挖掘技术，一次扫描数据快速得到频繁项集，改善了在挖掘海量数据时的内存开销。实验结果表明了T-Stream算法在性能上的优势。本文算法尤其适用于流速显著变化的数据流频繁集挖掘应用领域。
参考文献
[1] Agrawal R,Imielinski T , Swami A. Mining association rules between set s of items in large databases[C]. Procof the 1993 ACM SIGMOD Int Confon Management of Data.Washington DC, 1993:207-216.
[2] Han J , Pei J , Yin Y. Mining f requent patterns without candidate generation [C].Int Confon Management of Data. Dallas, 2000: 432-444.
[3] Manku G S , Motwani R. Approximate frequecy counts over data st reams [C].28th Int Confon Very Large Data Bases. Hong Kong, 2002:356-357.
[4] Chang JH,Lee WS. A sliding window method for finding recently frequent itemsets over online data streams [J] . J of Information Science and Engineering,2004, 20 (4) : 753-762.
[5] Zhu X D , Huang Z Q. Conceptual modeling rules extracting for data streams [J]. Knowledge-based System, 2008, 21(8):934-940.
[6] Chang J H, Lee W S. Zhou A. Finding recent frequent itemsets adaptively over online data streams [C]. ACM SIGKDD Int Confon Knowledge Discovery and Data Mining.San Diego, 2003:487-492.
[7] J in R M, Agrawal G. Frequent pat tern mining in data streams[M].New York: Springer , 2007: 61-84.
[8] Lin C-H, Chiu D-Y, Wu Y-H , et al . Mining frequent itemset s f rom data st reams with a time-sensitive sliding window[C].SIAM Int Conf on Data Mining. Newport Beach,2005: 59-66.
[9] LI Feng，XIAO Jianhua. How to Get Effective Slide-window Size in Time Series Similarity Search[J]. Journal of Frontiers of Computer Science and Technology,2009,3(1):105-112
[10] Borgelt C. Finding frequent itemsets by recursive elimination [C].Workshop Open Source Data Mining Software. Chicago, 2005:66-70.
[11] Sivanandam S N, Sumathi D, Hamsapriya T , et al.A hybrid parallel frequent itemset mining algorithm for very large databases [J]. Academic Open Internet Journal, http: // www. acadjournal.com,2004, 13.
作者简介: 张雪丽(1987年－), 女，安徽淮北人,硕士研究生，主要研究领域为数据挖掘.
注：“本文中所涉及到的图表、公式、注解等请以PDF格式阅读”
关键词: 数据流；事务链表组；频繁集；变尺度滑动窗口
中图分类号：TP311文献标识码：Adoi:10.3969/j.issn.1003-6970.2010.10.015
Improved Transaction List Group Based Frequent Itemsets Mining Algorithm Based Frequent Itemsets Mining Algorithm On Data Streams
ZHANG Xueli 1
(1. Computer Science And Technology School , China University of Mining and Technology,Xuzhou 221116,Jiangsu)
Abstract: According to the characteristics of mass and time-varying for data, a improved transaction list group based frequent itemsets mining algorithm T-Stream upon data streams is proposed. The algorithm could self-adaptively adjust the size of time windows. In the algorithm, transaction list group is adopted as synopsis data structure. The experiments indicate that the T-Stream algorithm is more effective than the Manku algorithm in term of temporal and spatial performance.
Key words: Data stream; Transaction list group; Frequent itemsets; Variable slide window
1. 引言
近年来，在很多应用领域中，出现了一种新的数据模式，其数据不是以传统的有限数据集形式，而是以连续的数据流形式出现，这些应用领域包括传感器网络、电信数据管理、网络安全和金融数据在线分析等。起源于20世纪 90年代的关联规则是数据挖掘的一个核心课题。与基于统计回归等数学方法进行数据分析不同，关联规则显得隐蔽而难以直接发现。挖掘关联规则的关键步骤是从数据中得到满足一定支持度的频繁项集。经典的 Apriori 算法通过分析购物篮事务数据得到该事务数据库上的频繁项集[1]。Han等[2]提出的FP-Growth算法进一步提高了挖掘频繁项集的性能。然而,这些频繁项集挖掘算法都需要多次扫描数据，不能满足数据流挖掘的要求。
国内外学者在数据流的频繁项集挖掘上提出了许多算法，他们都是针对传统数据挖掘技术的多次扫描数据进行改进或者提出新的思路。如Manku等[3]首次使用近似算法进行数据流的频繁项集挖掘，该方法仅需一次扫描数据，并且通过牺牲挖掘结果的精确性来提高挖掘的效率。但该算法挖掘的是整个历史数据流上的频繁项集，而在许多情况下，用户仅关心最近数据上的频繁项集；且该算法使用缓存技术 ,占用大量的内存空间。由于用户对最近的数据兴趣度更高，一些基于此要求的数据处理机制，如滑动窗口方法和数据衰减方法被成功地应用于数据流挖掘。文献[7]提出一种改进的FP树结构 ,能够有效挖掘具有长频繁模式的数据流。
根据以上问题，本文提出一种基于事务链表组的数据流频繁集挖掘算法T-Stream。该算法根据数据流本身的变化在变尺度时间窗口上进行自适应调整，采用改进事务链表组的概要数据结构，同时利用近似技术一次扫描数据快速得到频繁项集。理论分析和仿真实验均表明，T-Stream在时间和空间效率上得到了提高。
2. 基本概念和技术
2.1 变尺度滑动窗口
在以往数据流挖掘算法中,很多算法基于不变的滑动窗口机制,在时空复杂度等性能方面取得了较大成果.但这些技术大都忽略了具体问题中数据流的时变特性,当数据分布特征不断变化时,很难实现模型的自适应调整[4 ,5 ,8 ]。文献[9]对于任意时间序列上的变化，如果该序列变化在同一区间可以认为是微小变化，在计算时其权重应考虑降低，且此处可以是时间窗口的划分点；反之如果该区间变化明显，则此处应考虑加大计算权重，且不应该是时间窗口的划分点由此，在计算出有关时间窗口宽度时尽可能地保留了原序列中极值等重要特征信息的变化过程在此基础上，针对区间极值对数据对比的影响设定比较权值因子，使对比结果对均值平稳的独立噪声干扰不敏感或比较敏感该方法较其他方法，表现更快速，更准确。
变尺度时间窗口是根据数据流的流速变化以及数据分布的变化自适应地调整时间窗口大小,以达到最小的内存空间和处理时间的消耗。
2.2 问题描述
数据流是以时序不断出现的有序的项目序列，与传统的静态数据不同,数据流是连续的、 无边界的，通常高速地出现,并且随时间变化数据分布特征不断变化.在一般的变尺度滑动时间窗口下，数据流频繁项集挖掘可以形式化描述如下：
令数据流DS是由
无限的事务块构成的序列,每个事务块关联一个时间窗口,令 是最近的事务块。每个
事务块是由一组事务构成的集合，
假设每个块的事务数不一定相等。因此，数据流在时间域上的长度是
，其中
表示集合
的基数。给定最小支持度 s ，一个项集 X 在时
间域上是频繁项集,当且仅当
。所以给定一个最小
支持度，数据流上频繁项集挖掘问题规约到使用尽可能少的时间和空间消耗来发现一定时间域上所有的频繁项集。变尺度滑动窗口的窗口尺寸是根据数据流的流速变化来确定的。当流速很快时，及时缩小滑动窗口的长度；而当流速很慢时，实时地增长滑动窗口的长度。
2.3 概要数据结构
数据流挖掘在考虑时间效率的同时，也需要尽可能少地使用内存空间。Borgelt[10]在人工合成数据集和真实数据集上的实验表明，事务链表组数据结构能表现出比 Apriori 算法[1]和 FP-growth算法[2]更好的空间性能。将事务链表组的概要数据结构记为TLG。相关定义如下：
1) 事务链表组中的每个元素entry定义为(item , f ,Δ, list ) 。其中item为数据流中的一个单项，f记录了item的频繁度，Δ代表f中最大可能的出错数，而list记录的是以item为首项的项集链表。这些entry在本文中记为表头元素。
2) list中的每个元素entry定义为(itemset , f ,Δ) 。其中itemset为数据流中以该事务链头元素为首项的项集，f记录了itemset的频繁度，Δ代表f中最大可能的出错数。例如一个头元素entry为( a ,5 ,5 , list) ,list中每个项集的 entry又为( acd ,5 ,3) , ( abd ,10 ,3) 等,
如图1所示。
为进一步降低算法运行时的空间消耗, 在T-Stream算法中 ,改进事务链表组的概要数据结构，记为TL GⅡ，如图2所示。其思路是基于自然数中素数的特征,在该数组中,每个项用一个唯一的素数表示，每个项集用该项集所组成的项所对应的素数乘积表示.在建立事务链表组TLGⅡ时,按照表1转换相应的项与项集。
这种采用素数映射的方法在许多文献中被采用，如文献[11]。在TLGⅡ中，项与项集用相应的素数和素数积表示，对于大量持续的数据流而言，能更有效地减少内存空间的消耗。当然，随着项的数目的增加，素数积会逐渐增大。如果整数存储为4个字节，则TLGⅡ的方式可支持长度为10的项集，足够保证常规的频繁集挖掘。但当项集长度超过10时，则不能采用 TL GⅡ的数据结构，而应选用TL G的方式。
3. T-Stream算法
T-Stream算法的主要思想是：对持续不断的数据流,根据流速确立不同尺度的时间窗口,建立并维护一个事务链表组的概要数据结构(如后面的图3(a)所示)。同时对数据流中的每个事务计数，然后对事务链表组进行更新和修剪。一旦从客户端发送对频繁项集的请求时，T-Stream 算法将根据事务链表组输出挖掘结果。为了方便读者理解以TL G为例作为数据流的概要数据结构，基于TLGⅡ的T-Stream 算法描述,仅需要在输入和输出时作相应的素数映射与解码操作。T-Stream算法描述如下：
Input : DS;
User-defined support thresholds ; errorrateε.
Output : A set of f requent items and itemsets
1) Initialization:TLG←;Items←;Itemsets←; bcurrent←1
2) Foreach Batches e ←next itemset ;
3) UPDATE( e , f ,Δ, s ,ε ) ;
4)if BatchEnd doPRUNE(TLG,bcurrent);
5) bcurrent ←bcurrent + 1
6) endif
算法中的变量含义如下：s是用户定义的支持度阈值或称最小支持度；ε是近似计数的误差，一般设为最小支持度的十分之一或百分之一；bcurrent是桶的标记；变量Item和Itemset 分别表示输出的频繁项和频繁项集。下面给出算法的详细过程。
Step1：每个不同尺度的时间窗口对应一个桶，每个桶存放一个事务数据块，如 。将读入
的事务数据流存到该时间窗口所
对应的桶中。每个桶的宽度不需要相同，每个桶最多存放w= [1/ε]个事务。每个桶有唯一的标志bcurrent，初始值为1。当跳转到下一个时间窗口时，桶的标志增1。
Step2：为数据流中到当前时刻出现的每个单项创建一个单项数据链表e。每个entry为(item, f,Δ, list)，list中保存的是以首项为前缀的项集，list中元素entry定义为(itemset , f ,Δ)。
Step3：当一个新的项集e到达时，如果事务链表组中存在e ，则找到e的首项所对应的事务链，使e的频度加1，并将e的Δ值更新为事务链表中e的超集的最小Δ值。当一个新的项集e到达时，如果事务链表组中不存在e，则找到e的首项所对应的事务链，将(e , f , bcurrent - 1) 加入事务链表组中。另外在当前事务链中更新现存的e的子项集频度。如果e是唯一单项，则需要建立新的头元素。
Step4 ：剪枝操作在时间窗口跳转时发生，对于任何项( e , f ,Δ) ，如果f +Δ≤bcurrent,则删除。删除方法为扫描事务链表组TLG的每个事务链，如果某事务链中有项集e的entry ,且满足f +Δ≤bcurrent ，则将e从TLG中脱离.把该事务链中的所有脱离的项集去除首项，并以该条事务链的所有脱离项集来创建一个临时的事务链表组TLG′，同时更新频度。一条事务链表扫描完毕后，把TL G′合并到TL G，在合并过程中更新相应项集的频度。合并完后回收TLG′占用的内存，最后得到新的事务链表组TL G。依次循环，直到挖掘完最后一个事务链表后结束。事务链表组的剪枝与合并如图3(b)，3 (c) 所示。
Step5：当收到对挖掘频繁项集结果的请求后，输出满足f ≥( s -ε)的entry的项集。输出方法为扫描事务链表组的一个内存副本TLG*的每个事务链，如果某事务链中有项集e的 entry，且满足f ≥( s -ε)，则输出频繁项集。项集输出后将e从TLG*中脱离，并以该条事务链的所有脱离项集来创建一个临时的事务链表组TLG′，同时更新频率。一条事务链表扫描完毕后，把TL G′合并到TL G*，在合并过程中更新相应项集的频率。合并完后回收 TL G′所占内存，最后得到新的事务链表组TLG*。依次循环，直到挖掘完最后一个事务链表后结束，此时已经输出了所有挖掘出的频繁项集，最后回收副本TLG3*的内存。
4. 实验结果与分析
4.1 实验结果
实验数据来源于IBM数据产生器(http://www.almaden.ibm.com/software/quest/ Resources/index.shtml)。按照平均事务长度,平均频繁集长度和事务数这3个参数分别生成多组数据集。取平均事务长度为4 ,7 ,10 ,平均频繁集长度为2,4,6。误差阈值始终取值为最小支持度的0.1。
实验过程中，每个窗口的事务数有较大的差别。Manku采用的是等宽度的时间窗口 ，而T-Stream算法采用变尺度滑动窗口，根据事务数的多少设置窗口大小。实验中算法程序的输入就是按照不同窗口大小设置不同数量的事务数。
对T-Stream算法随事务数变化和最小支持度变化在挖掘时间和内存消耗上进行了实验。另外，本文还实现了Manku算法用来进行性能对比实验。图4 (a) 给出了基于TLG的T-Stream算法当事务数在10～50万之间变化时，不同支持度下的算法运行时间的比较。图4(b)给出了T-Stream算法与缓冲内存分别是30M和40M的Manku算法之间的运行时间比较。图4 (c)给出了基于TLG和TLGⅡ的T-Stream算法随支持度变化的空间效率变化。图4 (d)给出了当最小支持度分别为0.01和0.1时，T-Stream算法随事务数变化的内存消耗。
4.2 实验结果分析
从图4(a)中可以看出T-Stream算法与最小支持度和挖掘事务数之间的关系。挖掘相同的事务数，最小支持度越低，运行时间越长。这是因为最小支持度越低，挖掘相同事务数会产生越多的频繁集。对于同一支持度，越多的事务数则含有越多的频繁项集，运行时间越长。
从图4(b)中可以看出，与Manku算法相比，T-Stream算法明显提高了挖掘频繁集的时间效率。这是因为T-Stream算法采用变尺度滑动窗口，根据4.2实验结果分析从图4(a)中可以看出T-Stream算法与最小支持度和挖掘事务数之间的关系。挖掘相同的事务数，最小支持度越低，运行时间越长。这是因为最小支持度越低，挖掘相同事务数会产生越多的频繁集。对于同一支持度，越多的事务数则含有越多的频繁项集，运行时间越长。
从图4(b)中可以看出，与Manku算法相比，T-Stream算法明显提高了挖掘频繁集的时间效率。这是因为T-Stream算法采用变尺度滑动窗口 ,根据事务数的多少设置窗口大小实验中算法程序的输入就是按照不同窗口大小设置不同数量的事务数，从而表现出较高的运行效率。TLG的数据结构具有很高的空间优越性，它不需要缓冲存储区的辅助空间。如实验中Manku算法需要30M和更高的缓存,而T-Stream仅需要几兆的内存消耗。因此，与Manku算法需要较多的缓冲内存相比，T-Stream算法的事务链表组的数据结构能有效降低内存的消耗。
从图4(c)，4(d)的实验结果中可进一步看出TLGⅡ在空间性能上的提高。图4(c)给出了分别挖掘10万个和50万个事务，基于TLG与TLGⅡ的T-Stream算法随最小支持度变化的内存消耗变化。图4(d)给出了分别设置最小支持度为0.01和0.1时，基于TLG与TLGⅡ的T-Stream算法随挖掘事务数变化的内存消耗变化。实验结果表明，在挖掘大量的事务数时或者在最小支持度较小时，TLGⅡ相比TLG在内存开销上的优势更加明显。
5. 结论
本文同时考虑数据流的海量特性和时变特性，提出了一种基于改进事务链表的数据流频繁集挖掘算法T-Stream，能在变尺度的时间窗口上挖掘频繁项集。算法采用近似挖掘技术，一次扫描数据快速得到频繁项集，改善了在挖掘海量数据时的内存开销。实验结果表明了T-Stream算法在性能上的优势。本文算法尤其适用于流速显著变化的数据流频繁集挖掘应用领域。
参考文献
[1] Agrawal R,Imielinski T , Swami A. Mining association rules between set s of items in large databases[C]. Procof the 1993 ACM SIGMOD Int Confon Management of Data.Washington DC, 1993:207-216.
[2] Han J , Pei J , Yin Y. Mining f requent patterns without candidate generation [C].Int Confon Management of Data. Dallas, 2000: 432-444.
[3] Manku G S , Motwani R. Approximate frequecy counts over data st reams [C].28th Int Confon Very Large Data Bases. Hong Kong, 2002:356-357.
[4] Chang JH,Lee WS. A sliding window method for finding recently frequent itemsets over online data streams [J] . J of Information Science and Engineering,2004, 20 (4) : 753-762.
[5] Zhu X D , Huang Z Q. Conceptual modeling rules extracting for data streams [J]. Knowledge-based System, 2008, 21(8):934-940.
[6] Chang J H, Lee W S. Zhou A. Finding recent frequent itemsets adaptively over online data streams [C]. ACM SIGKDD Int Confon Knowledge Discovery and Data Mining.San Diego, 2003:487-492.
[7] J in R M, Agrawal G. Frequent pat tern mining in data streams[M].New York: Springer , 2007: 61-84.
[8] Lin C-H, Chiu D-Y, Wu Y-H , et al . Mining frequent itemset s f rom data st reams with a time-sensitive sliding window[C].SIAM Int Conf on Data Mining. Newport Beach,2005: 59-66.
[9] LI Feng，XIAO Jianhua. How to Get Effective Slide-window Size in Time Series Similarity Search[J]. Journal of Frontiers of Computer Science and Technology,2009,3(1):105-112
[10] Borgelt C. Finding frequent itemsets by recursive elimination [C].Workshop Open Source Data Mining Software. Chicago, 2005:66-70.
[11] Sivanandam S N, Sumathi D, Hamsapriya T , et al.A hybrid parallel frequent itemset mining algorithm for very large databases [J]. Academic Open Internet Journal, http: // www. acadjournal.com,2004, 13.
作者简介: 张雪丽(1987年－), 女，安徽淮北人,硕士研究生，主要研究领域为数据挖掘.
注：“本文中所涉及到的图表、公式、注解等请以PDF格式阅读”