一种基于改进事务链表组的数据流频繁集挖掘算法

来源:用户上传      作者:

　　摘要:根据数据流的海量特性和时变特性，提出一种基于事务链表组的数据流频繁集挖掘算法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) 等,

转载注明来源:https://www.xzbu.com/8/view-8773590.htm