一种有效的挖掘数据流近似频繁项算法

数据流频繁项是指在数据流中出现频率超出指定阈值的数据项.查找数据流频繁项在网络故障监测、流数据分析以及流数据挖掘等多个领域有着广泛的应用.在数据流模型下,算法只能一遍扫描数据,并且可用的存储空间远远小于数据流的规模,因此,挖掘出所有准确的数据流频繁项通常是不可能的.提出一种新的挖掘数据流近似频繁项的算法.该算法的空间复杂性为O(ε^-1),每个数据项的平均处理时间为O(1),输出结果的频率误差界限为ε(1-s+     

一种轮转的数据流频繁项挖掘算法

挖掘数据流的频繁项已受到广泛关注,研究者们提出了一些高效的数据流上挖掘频繁项的算法,尽管这些算法能够比较好地找到频繁项,但对频繁项支持度的估计往往存在较大误差.而新的算法REC(rotative efficient count) 除了能够保证频率超过一定阈值的数据项都能被找到,并且能够尽可能准确地返回其频率.分析和实验表明,相比当前最好的两种算法,REC算法空间在同样空间代价下,对数据项频率的估计更为准确,尤其在数据分布比较平缓时表现得尤为明显.     

数据流中频繁项近似挖掘算法

提出新的数据结构ESBF(Extensible and Scalable Bloom Filter)-可扩展的Bloom Filter.并提出基于ESBF的数据流中频繁项近似挖掘算法,该算法在保证较高精度的同时,实现比同类算法具有更好的时间效率且在一般情况下具更好的空间效率,并证明只需ln(-M/lnρ)·e/ε·1/(ε·M)个计数器就能保证满足用户规定的误差ε及可信度ρ要求.     

挖掘数据流近似频繁项的改进算法

数据流的无限性、连续性和速度快等特点,使得挖掘出所有准确的数据流频繁项通常是不可能的.算法的空间复杂度和时间复杂度通常是评价频繁项挖掘算法优劣的两个主要度量.通过引入局部性原理改进数据流近似频繁项的挖掘算法,该算法的空间复杂性为O（1/ε）,数据流每个数据项的最坏处理时间是O（1/ε）,其最好处理时间是O（1）,输出结果的频率值误差为∑_(i=2)^j（1-μ_i）×k_i。     

SWFPM:一种有效的数据流频繁项挖掘算法*

分析了数据流频繁项挖掘算法EC的不足之处,如不能准确地挖掘最近一段时间内数据流的频繁项。提出了一种频繁项样本特征复合四元组的数据结构来保存样本集合,在此基础上,提出了一种基于滑动窗口的数据流频繁项挖掘算法——SWFPM。该算法能准确地挖掘出该滑动窗口中的频繁项。实验数据采用IBM合成数据发生器产生的顾客购物数据和1998年世界杯官方网站的访问日志数据。实验结果表明,该算法具有很高的频繁项挖掘准确度、快速的数据处理能力。     

基于计数的数据流频繁项挖掘算法

挖掘数据流的频繁项已受到广泛关注,经典的频繁项挖掘算法尽管能够比较好地找到频繁项,但对频繁项频数的估计往往存在较大误差.SRoEC(segment rotative efficient count),SReEC(segment reserve efficient count)和RFreq(reserve frequent)算法针对该问题,继承基于计数的算法思想,将计数器进行划分并定义相应的操作,以期提高频数统计准确度并减小噪音影响.实验和数据分析表明,这些算法不仅能够保证频数超过阈值的数据项都能被找到,而且大大提高了频繁项频数统计的准确性.在同样空间代价下,算法无论在模拟数据集和真实数据集实验中,都表现出较高的频数准确率、较低的频数偏差率和较高的频数保有率,尤其是数据分布较平缓时,算法优势更加明显.     

挖掘滑动窗口中的数据流频繁项算法

滑动窗口是一种对最近一段时间内的数据进行挖掘的有效的技术,本文提出一种基于滑动窗口的流数据频繁项挖掘算法.算法采用了链表队列策略大大简化了算法,提高了挖掘的效率.对于给定的阈值S、误差ε和窗口长度n,算法可以检测在窗口内频度超过Sn的数据流频繁项,且使误差在εn以内.算法的空间复杂度为O(ε-1),对每个数据项的处理和查询时间均为O(1).在此基础上,我们还将该算法进行了扩展,可以通过参数的变化得到不同的流数据频繁项挖掘算法,使得算法的时间和空间复杂度之间得到调节.通过大量的实验证明,本文算法比其它类似算法具有更好的精度以及时间和空间效率.     

一种数据流中的频繁模式挖掘算法

时序数据流的无限性、流动性和不规则性使得传统的频繁模式挖掘算法难以适用。针对时序数据流的特点,提出了一类特殊非规则数据流频繁模式挖掘的新算法。新算法采用时序数据分段的思想,逐段挖掘局部频繁模式,然后依据局部频繁模式有效地挖掘出所有的全局频繁模式。将新算法应用于电信领域的收入保障项目之中,结果表明,新算法具有良好的性能,能有效发现挖掘时序数据流中的频繁模式。     

数据流上的频繁闭项集挖掘算法

针对频繁闭项集挖掘算法中数据结构与处理机制复杂的问题,提出窗口快速滑动的数据流频繁闭项集挖掘算法——MFWSR。算法通过采用紧致的数据结构和简化的判断过程提高时空效率,支持响应不同用户支持度阈值的查询。实验结果表明,在保持已有算法精度的情况下,MFWSR具有更高的时空效率。     

数据流的频繁模式挖掘算法浅析

介绍了数据流的定义和特点及数据流频繁模式的基本概念。针对数据流的特性,讨论分析了目前国内外数据流频繁模式挖掘算法、算法特性及应用情况,最后展望了数据流频繁模式挖掘的进一步研究工作。     

数据流频繁项集的快速挖掘方法

近年来,数据流挖掘一直是国内外研究的热点,频繁项集挖掘又是数据流挖掘中的重要问题。根据数据流无限性和流动性的特点,提出了一种在滑动窗口中挖掘频繁项集的算法FIM-SW,FIM-SW算法主要是采用垂直的数据库表示方法,使用二进制向量表示每个数据项,并利用Apriori性质产生频繁项集。实验结果表明,这种算法显著地提高了挖掘效率。     

一种改进的数据流最大频繁项集挖掘算法

提出了一种基于DSM MFI算法的改进算法DSMMFI DS算法,它首先将事务数据按一定的全序关系存入DSFI list列表中;然后按排序后的顺序存储到类似概要数据结构的树中;接着删除树中和DSFI list列表中的非频繁项,同时删除窗口衰退支持数大的事务项;最后采用自顶向下和自底向上的双向搜索策略来挖掘数据流的最大频繁项集。通过用例分析和实验表明,该算法比DSM MFI算法具有更好的执行效率。     

Methods for mining frequent items in data streams: an overview

In many real-world applications, information such as web click data, stock ticker data, sensor network data, phone call records, and traffic monitoring data appear in the form of data streams. Online monitoring of data streams has emerged as an important research undertaking. Estimating the frequency of the items on these streams is an important aggregation and summary technique for both stream mining and data management systems with a broad range of applications. This paper reviews the state-of-the-art progress on methods of identifying frequent items from data streams. It describes different kinds of models for frequent items mining task. For general models such as cash register and Turnstile, we classify existing algorithms into sampling-based, counting-based, and hashing-based categories. The processing techniques and data synopsis structure of each algorithm are described and compared by evaluation measures. Accordingly, as an extension of the general data stream model, four more specific models including time-sensitive model, distributed model, hierarchical and multi-dimensional model, and skewed data model are introduced. The characteristics and limitations of the algorithms of each model are presented, and open issues waiting for study and improvement are discussed.     

Sliding window-based frequent pattern mining over data streams

Finding frequent patterns in a continuous stream of transactions is critical for many applications such as retail market data analysis, network monitoring, web usage mining, and stock market prediction. Even though numerous frequent pattern mining algorithms have been developed over the past decade, new solutions for handling stream data are still required due to the continuous, unbounded, and ordered sequence of data elements generated at a rapid rate in a data stream. Therefore, extracting frequent patterns from more recent data can enhance the analysis of stream data. In this paper, we propose an efficient technique to discover the complete set of recent frequent patterns from a high-speed data stream over a sliding window. We develop a Compact Pattern Stream tree (CPS-tree) to capture the recent stream data content and efficiently remove the obsolete, old stream data content. We also introduce the concept of dynamic tree restructuring in our CPS-tree to produce a highly compact frequency-descending tree structure at runtime. The complete set of recent frequent patterns is obtained from the CPS-tree of the current window using an FP-growth mining technique. Extensive experimental analyses show that our CPS-tree is highly efficient in terms of memory and time complexity when finding recent frequent patterns from a high-speed data stream.     

数据流频繁模式挖掘综述

一些先进应用如欺诈检测和趋势学习等带来了数据流频繁模式挖掘的发展。不同于静态数据,数据流挖掘面临着时空约束和项集组合爆炸等问题。对已有数据流频繁模式挖掘算法进行综述并对经典和最新算法进行分析。按照模式集合的完整程度进行分类,数据流中频繁模式分为全集模式和压缩模式。压缩模式主要包括闭合模式、最大模式、top-k模式以及三者的组合模式。不同之处是闭合模式是无损压缩的,而其他模式是有损压缩的。为了得到有趣的频繁模式,可以挖掘基于用户约束的模式。为了处理数据流中的新近事务,将算法分为基于窗口模型和基于衰减模型的方法。数据流中模式挖掘常见的还包含序列模式和高效用模式,对经典和最新算法进行介绍。最后给出了数据流模式挖掘的下一步工作。     

对数据流频繁项集挖掘算法WSW-Imp的改进

近年来随着新的应用的出现,比如网络流量分析、在线事物分析和网络欺诈检测等,对数据流的挖掘成了一个越来越重要的课题。对于数据流频繁项集的挖掘,目前绝大部分的研究都集中在传统的窗口模式下进行,即时间衰退窗口模式、界标窗口模式和滑动窗口模式。Pauray S.M.Tsai于2009年提出了一种新的窗口模式：加权滑动窗口模式,并设计了两个基于此窗口模式的数据流频繁项集挖掘算法WSW和WSW-Imp,其中WSW-Imp是对WSW算法的改进。在研究了加权滑动窗口模式以及WSW-Imp算法的基础上,对WSW-Imp算法作了进一步的改进,设计了算法WSW-Imp2,并从理论上证明了WSW-Imp2算法比WSW-Imp算法更高效,实验结果也表明了这一点。     

Methods for finding frequent items in data streams

The frequent items problem is to process a stream of items and find all items occurring more than a given fraction of the time. It is one of the most heavily studied problems in data stream mining, dating back to the 1980s. Many applications rely directly or indirectly on finding the frequent items, and implementations are in use in large scale industrial systems. However, there has not been much comparison of the different methods under uniform experimental conditions. It is common to find papers touching on this topic in which important related work is mischaracterized, overlooked, or reinvented. In this paper, we aim to present the most important algorithms for this problem in a common framework. We have created baseline implementations of the algorithms and used these to perform a thorough experimental study of their properties. We give empirical evidence that there is considerable variation in the performance of frequent items algorithms. The best methods can be implemented to find frequent items with high accuracy using only tens of kilobytes of memory, at rates of millions of items per second on cheap modern hardware.