基于前缀树的数据流容错概要结构构造

由育阳 张健沛

(哈尔滨工程大学计算机学院，哈尔滨 150001)

杨志宏

(中国医学科学院药用植物研究所，北京 100193)

由 勇

(空军航空医学研究所，北京 100142)

基于前缀树的数据流容错概要结构构造

由育阳 张健沛

(哈尔滨工程大学计算机学院，哈尔滨 150001)

杨志宏

(中国医学科学院药用植物研究所，北京 100193)

由 勇

(空军航空医学研究所，北京 100142)

应用于数据流环境的数据挖掘算法应首要考虑算法的时空复杂性，而要实现消耗巨大计算资源的容错模式挖掘则更要专注于算法的效率.容错模式挖掘是为了从被噪声干扰的真实世界数据中获取允许一定程度错配的、更加泛化的有用知识.提出一种新的单遍历、高压缩的容错前缀树形概要结构DSFT-tree(Data Stream Fault-Tolerant Frequent Pattern Tree)，用来捕捉最近到达的数据流中的数据元素，并且能够高效移除过期数据，实现最大限度地降低计算资源消耗.利用滑动窗指针和位向量表达法实现容错树形概要结构的高效重构，并进一步基于滑动窗口技术实现了数据流环境下的容错频繁项挖掘.实验采用IBM数据发生器产生事务数据，在合理时间内最终挖掘频繁项的数量为FP-stream算法的1.5倍.

数据流;概要结构;容错模式;前缀树

区别于传统数据模型，流数据模型具有以下特点:数据实时到达;数据到达次序独立，不受应用系统所控制;数据规模宏大且不能预知其最大值;数据一经处理，除非特意保存，否则不能被再次取出处理，或再次提取数据代价昂贵［1－2］.1998年数据流作为一种新的数据处理模型被正式提出，因其巨大的应用前景而引起了领域内研究者的广泛关注.由于数据流的潜在无穷、高速到达等特性，数据挖掘算法只能够扫描原数据一次来支持对其的各种计算，这对算法的时间效率和空间效率提出了严格要求［3－4］.

传统的数据流频繁模式挖掘是在数据不含有噪声并且严格匹配的假设下，基于支持度-置信度框架下的精确模式挖掘，只能从精确匹配的频繁模式中推导出关联规则.这使得挖掘算法普遍存在容错性不强的问题，许多重要的有用信息并不能被挖掘出来.2001年文献［5］首次提出了容错频繁项集的概念，并且论述了基于容错思想的关联规则所表述的知识更具有实际应用价值.首先，现实世界中数据广泛存在噪声或数据缺失问题，合理设置频繁模式最小支持度阈值、获得理想挖掘结果是非常困难的.如果最小支持度阈值设置太大则造成最终发现的频繁模式数量很少，难以得到满意结果;如果最小支持度阈值设置太小则会产生数量巨大的无效短模式，耗费了很多时间和计算资源并且无法判定所挖掘模式的有效性.其次，现实世界中并非所有的有效模式都是严格匹配的.假设存在规则R:(患者A，咳嗽)∪(患者A，发烧)∪(患者 A，头疼)∪(患者 A，咽喉疼痛)→(患者A，感冒)，同时具有4种症状的患者被确诊为感冒，而现实生活中患者具有以上3种甚至两种症状就被认为是感冒.基于以上论述，在进行数据挖掘时可适当放宽对模式包含的定义，除了精确包含的频繁模式外，还应当允许挖掘包含一定数量错误数据项的频繁模式，这样才能比较真实地挖掘出更多有用的关联规则，这种模式称为容错式频繁模式.国内外关于容错频繁模式挖掘的研究大多基于静态数据集.2008年文献［6］首次实现了容错模式的增量挖掘算法.目前，针对数据流环境下的容错模式挖掘研究尚处于起步阶段.

本文提出了一种应用于数据流环境下的单遍历、高压缩容错前缀树形概要结构DSFT-tree(Data Stream Fault-Tolerant Frequent Pattern Tree)实现容错项的挖掘.采用窗口指针和位向量表达的方法能够精确定位每一个频繁项的来源.当新的事务数据到达而过期的事务数据被移除时，可以进行树形概要结构的整支排序，而无需按结点逐个排序，从而实现了容错概要结构的高效重构.

1 相关概念

容错频繁模式挖掘是一类复杂度非常大的计算任务，算法的目标搜索空间范围在理论上是精确频繁模式的指数级.DSFT-tree算法是一种基于滑动时间窗技术的通用高效容错前缀树形概要结构，结点根据频繁降序排列同时可以针对每个子结点所处理数据性质的不同调整窗口大小.处理稀疏数据的时候加宽窗口提高处理速度，处理稠密数据时减窗口提高频繁项挖掘质量［7］.

定义1令模式I={i1，i2，…，in}是长度为n的项集.令T={t1，t2，…，tm}为一个事务数据集，并且T中的每个项都是项集I中的元素，T中的每个事务数据都有唯一的编号，记为TID.事务数据流 TDS={T1，T2，…，Tm}是一个连续的时间序列.

定义2设TDS是事务数据流.在TDS中包含模式A的事务数据量称为A的支持度，记为sup(A).给定一个事务数据流TDS和一个由用户定义的支持度阈值min_sup＞0，模式A是频繁模式当且仅当sup(A)≥min_sup.

定义3给定一个容错因子 δ(δ＞0)，事务数据集T=(TID，X)被称作容错包涵模式A，当且仅当存在模式A'，并满足 A'⊆A，A'⊆X 且|A'|≥(|A|－δ).在事务数据T中容错包含模式A的数目被称作容错支持度，记为supFT(A).

令B(A)为一个事务数据集并且容错包含模式A.给定最小支持度阈值min_supITEM和最小容错支持度阈值min_supFT，模式A被称作容错频繁模式，当且仅当:

1)supFT(A)≥min_supFT，且

2)对于每一个项 a，且 a∈A，supB(A)(a)≥min_supITEM，其中supB(A)(a)是B(A)中事务数据集包含项a的数目.

在事务数据流中，将流入的数据分成包含相同数目事务数据的子块，每一个子块被称作基本窗.滑动窗记为 WS={W1，W2，…，Wm}，其中每个基本窗口Wi又可以分解为包含相同数目事务数据的若干个批次(Batch)［8］.

2 树形结构的构造与重构

DSFT-tree算法用来在数据流环境下利用滑动窗技术实现容错模式挖掘.将一个基本窗口分为相等且不重叠的几个批次，当窗口在数据流上滑动的时候，随着最新到达的数据流入最新的批次，过期数据将被移除最早的批次.DSFT-tree算法能够动态地自身重构，始终保持频繁降序排列.整个过程分为两个阶段，即插入阶段和重构阶段.当新的数据流入时处于插入阶段，DSFT-tree算法捕捉事务数据流的重要信息，并在项头表中依照当前次序排列;当新数据流入而过期数据流出时处于重构阶段，利用窗口指针和位向量表达方法高效重新排列结点.概要结构的构造以插入阶段开始，结束于重构阶段，在整个容错频繁项挖掘的过程中依次反复重复.

2.1 前缀树的结构

由被标记为“NULL”的根结点、依据频繁降序排列的子结点和项头表I-list构成.当流入的事务数据中不同的项之间存在相同的特征时，DSFT-tree算法尽可能多地使不同的项利用相同的路径，最大限度地降低概要结构的规模和复杂性，前缀树的规模受到数据量大小、窗口尺寸和支持度阈值等多种因素限制，共享路径的长度不确定.相同路径最大限度共享机制使前缀树能够快速地更新和计算.每一个子结点包含频繁项编号、支持度、容错支持度和窗口指针，结构如图1所示.

图1 子结点结构

滑动窗口指针被定义为(m1，m2…∶v1，v2…)形式，其中mi记录在当前的滑动窗中所有项的批次来源;vi为对应于mi的每个批次中当前项的位向量表达.位向量是一种对当前窗口批次中的项进行记录的有效表达方式.对于任意项a，存在位宽为当前窗口批次尺寸的Bit(a)，如果当前窗口批次中存在项a，则令Bit(a)=1，如果不存在则令Bit(a)=0.窗口指针P可以准确地定位数据流中当前窗口中每一项的准确位置，当概要结构处于插入阶段时，首先在项头表I-list中按当前次序记录项集，然后按频繁降序重新排列项集，继而进一步构造DSFT-tree前缀树.容错支持度被定义为 SFT(x，y)且x≤SFT≤y，x和 y分别代表容错支持度的上下限.前缀树的主要思想就是最大限度地利用共享路径压缩概要结构的复杂度，但是无法表达由项数据缺失而产生的容错项集，在传统的容错模式挖掘中并不存在容错支持度的上下限问题.为了使树形概要结构能够应用于容错模式挖掘而定义了容错支持度的上下限，合理表达缺失项.假设存在事务数据流片段如表1所示.

表1 事务数据流片段

令由用户设定的支持度阈值min_sup=3，对于模式 A={c，e，f}可以计算 TID为20，40 和60 的事务数据为频繁项集，令容错支持度阈值min_supFT=4，容错因子 δ=1，则对于模式 B={b，c，e，f}可以计算TID为20，40，60和80的事务数据为容错频繁项集.将表1中的事务数据分为两个基本窗口，窗口宽度为 6.TID为 10，20，30，40，50 和60 的事务数据组成窗口1，TID为 40，50，60，70，80和90的事务数据组成窗口2，且基本窗口划分为两个批次.由表1中数据片段构建DSFT-tree前缀树的插入阶段，结构如图2所示.

2.2 DSFT-tree算法的重构

当滑动窗口移动新的数据到达而过期数据被移除时，DSFT-tree算法重复插入阶段计算，同时进入重构过程.树形结构的结点频繁进行交换、合并和分裂计算，大量的结点排列计算工作依次进行，直到遍历当前窗口中所有的插入项集后才结束.窗口指针中的mi记录了插入阶段所有项的来源，使得重新排列频繁降序的工作可以无需改变事务数据的物理地址，从而避免了由于结点的交换、合并和分裂而带来的大量计算，节省计算资源提高算法的效率.位向量表达方法则记录了任意项在任意批次中的位置，同样在概要结构的重构过程中实现不改变事务数据的物理地址就可以高效地移除过期数据.表1数据片段中，在基本窗口1的第一个批次中，项e的位向量表达为Bit(e)=110.由表1中数据片段构建DSFT-tree前缀树的重构阶段，结构如图3所示.

通过以上计算分析可以推导出DSFT-tree前缀树的性质如下.

图2 DSFT-tree构建

图3 DSFT-tree重构

性质1DSFT-tree前缀树任意结点的支持度大于等于其子结点的支持度之和.

性质2DSFT-tree前缀树任意结点的容错支持度大于等于其子结点的容错支持度之和.

性质3DSFT-tree前缀树任意尾结点的容错因子必然等于0，且容错支持度下限必然等于0.

3 实验结果分析与比较

为验证DSFT-tree算法的时间效率和空间效率，在实验中与经典的FP-stream算法进行了比较，实验结果如图4～图6所示.

图4 泛化能力

图5 运行效率随支持度阈值变化

图6 运行效率随数据量变化

实验数据采用IBM数据发生器产生数据集T7.I4.D1000k，T，I和 D 分别代表平均事务数据长度、最大频繁项集长度和产生事务数据的总数量.实验在主频为3.0GHz Intel Celeron处理器及512MB内存的Windows XP系统平台下采用Visual C++6.0编程实现，实验中批次宽度均设置为5 000.实验过程比较了利用DSFT-tree算法和FP-stream算法所产生频繁项集的数量，即泛化能力.当支持度发生变化时两种概要结构的运行效率和数据量发生变化时DSFT-tree算法的运行效率，如图5、图6所示.

FP-stream算法产生近似模式并不是精确模式，用来与DSFT-tree算法相比较更加具有实际意义.根据实验结果可以看出在δ=0.1%，而其他参数相同的条件下，采用DSFT-tree前缀树概要结构挖掘容错项集的数量约为FP-stream的1.5倍，这证明了容错概要结构的泛化能力比近似模式提高很多.这些容错项集并不都是有效的，其有效性判定在前期研究工作中已经完成.随着支持度阈值变大，计算容错项集产生所耗费的时间也逐渐变大，当数据量变大时概要结构构建所耗费的时间基本成线性变化.DSFT-tree算法所消耗的计算资源比较大，但是所发现的容错项集数量也大大增加，多耗费的计算资源尚可承受.从图中的纵坐标来看，DSFT-tree是完全可以适应数据流环境的.

4 结论

本文提出了新的高压缩、单遍历、应用于数据流环境下的容错前缀树形概要结构DSFT-tree.由于容错项搜索空间远远大于频繁项搜索空间，因而概要结构算法的运行效率仍然是最主要的制约因素.窗口指针的应用使DSFT-tree算法不用逐个结点比较就可以按子树路径重新构造，大幅度提高了算法效率，显著地减小了容错项集的计算时间.支持度阈值和容错因子δ的取值对DSFT-tree算法效能的影响至关重要，只有合理错配才能得到满意的计算结果.容错项集允许一定程度的错配，最终产生的容错项集数目远大于近似项集，适当的容错上下限能够合理地表达更加广义泛化的容错模式，在进一步的研究工作中应采用限定容错搜索空间范围的方法降低算法复杂性.本文给出了容错前缀树形概要结构从插入阶段到重构阶段的完整构造方法，为进一步研究数据流环境下的容错模式挖掘奠定了基础.

References)

［1］ Beringer J，Hullermeier E.Online clustering of parallel data streams［J］.Data ＆ Knowledge Engineering，2006，58(2):180－204

［2］ Li H F，Lee SY.Mining frequent itemsets over data streams using efficient window sliding techniques［J］.Expert Systems with Applications，2009，36(2):1466 －1477

［3］ Chang JH，Lee W S.Online data stream mining of recent frequent itemsets by sliding window method［J］.Journal of Information Science，2005，31(2):76 －90

［4］ Yu JX，Chong Z H，Lu H J，et al.A false negative approach to mining frequent itemsets from high speed transactional data streams［J］.Information Sciences，2006，176(14):1986 －2015

［5］ Yang C，Fayyad U，Bradley PS.Efficient discovery of error-tolerant frequent itemsets in high dimensions［C］ //Proc of 2001 ACM Int Conf on Knowledge Discovery in Databases.San Francisco，CA:Association for Computing Machinery，2001:194－203

［6］ Bashir S，Halim Z，Baig A R.Mining fault tolerant frequent patterns using pattern growth approach［C］ //AICCSA 08-6th IEEE/ACS International Conference on Computer Systems and Applications.Doha，Qatar:Inst of Elec and Elec Eng Computer Society，2008:172 －179

［7］ Zhang SC，Zhang JL，Zhang C Q.EDUA:an efficient algorithm for dynamic database mining［J］.Information Sciences，2007，177(13):2756－2767

［8］ Chi Y，Wang H，Yu P S，et al.Catch the moment:maintaining closed frequent itemsets over a data stream sliding window［J］.Knowledge and Information Systems，2006，10(3):265 －294

(编 辑:李 晶)

Construction of fault-tolerant synopsis over data stream based on prefix-tree

You Yuyang Zhang Jianpei

(College of Computer Science and Technology，Harbin Engineering University，Harbin 150001，China)

Yang Zhihong

(Institute of Medicinal Plant Development CAMS and PUMC，Beijing 100193，China)
You Yong

(Institute of Aviation Medicine，Beijing 100036，China)

Complexity of data mining algorithm over data stream is the most important and it should be more focused on algorithm efficiency because of the great consumption of algorithm resources.Fault-tolerant frequent pattern mining is more generalized and suitable for extracting interesting knowledge from real-world data stream polluted by noise.An algorithm，called data stream fault-tolerant frequent pattern tree(DSFT-tree)，was proposed.It could achieve a frequency-descending and highly compact prefix-tree structurewith a single-pass to capture fault-tolerant frequent item sets in recent sliding window.To completely and efficiently perform the tree restructuring operation，an efficient mechanism based on sliding window pointer and bit-vector representation were utilized to restructure the tree.The efficient reconstruction mechanism greatly reduced the consumption of calculation resources and achieved fault-tolerant frequent item sets mining.Experimental transaction database was generated by IBM synthetic data generator.The number of frequent item sets extracted by DSFT-tree is1.5 fold greater than that extracted by FP-stream.Experimental results show that developed algorithm is an efficient fault-tolerant synopsis.

data stream;synopsis;fault-tolerant frequent pattern;prefix-tree

TP 311.13

A

1001-5965(2011)05-0564-05

2010-11-02

国家自然科学基金资助项目(61073041)

由育阳(1977－)，男，黑龙江哈尔滨人，博士生，arthurwy@163.com.