共查询到18条相似文献,搜索用时 53 毫秒
1.
2.
挖掘数据流的频繁项已受到广泛关注,研究者们提出了一些高效的数据流上挖掘频繁项的算法,尽管这些算法能够比较好地找到频繁项,但对频繁项支持度的估计往往存在较大误差.而新的算法REC(rotative efficient count) 除了能够保证频率超过一定阈值的数据项都能被找到,并且能够尽可能准确地返回其频率.分析和实验表明,相比当前最好的两种算法,REC算法空间在同样空间代价下,对数据项频率的估计更为准确,尤其在数据分布比较平缓时表现得尤为明显. 相似文献
3.
提出新的数据结构ESBF(Extensible and Scalable Bloom Filter)-可扩展的Bloom Filter.并提出基于ESBF的数据流中频繁项近似挖掘算法,该算法在保证较高精度的同时,实现比同类算法具有更好的时间效率且在一般情况下具更好的空间效率,并证明只需ln(-M/lnρ)·e/ε·1/(ε·M)个计数器就能保证满足用户规定的误差ε及可信度ρ要求. 相似文献
4.
数据流的无限性、连续性和速度快等特点,使得挖掘出所有准确的数据流频繁项通常是不可能的.算法的空间复杂度和时间复杂度通常是评价频繁项挖掘算法优劣的两个主要度量.通过引入局部性原理改进数据流近似频繁项的挖掘算法,该算法的空间复杂性为O(1/ε),数据流每个数据项的最坏处理时间是O(1/ε),其最好处理时间是O(1),输出结果的频率值误差为∑_(i=2)^j(1-μi)×ki。 相似文献
5.
6.
基于计数的数据流频繁项挖掘算法 总被引:1,自引:0,他引:1
挖掘数据流的频繁项已受到广泛关注,经典的频繁项挖掘算法尽管能够比较好地找到频繁项,但对频繁项频数的估计往往存在较大误差.SRoEC(segment rotative efficient count),SReEC(segment reserve efficient count)和RFreq(reserve frequent)算法针对该问题,继承基于计数的算法思想,将计数器进行划分并定义相应的操作,以期提高频数统计准确度并减小噪音影响.实验和数据分析表明,这些算法不仅能够保证频数超过阈值的数据项都能被找到,而且大大提高了频繁项频数统计的准确性.在同样空间代价下,算法无论在模拟数据集和真实数据集实验中,都表现出较高的频数准确率、较低的频数偏差率和较高的频数保有率,尤其是数据分布较平缓时,算法优势更加明显. 相似文献
7.
滑动窗口是一种对最近一段时间内的数据进行挖掘的有效的技术,本文提出一种基于滑动窗口的流数据频繁项挖掘算法.算法采用了链表队列策略大大简化了算法,提高了挖掘的效率.对于给定的阈值S、误差ε和窗口长度n,算法可以检测在窗口内频度超过Sn的数据流频繁项,且使误差在εn以内.算法的空间复杂度为O(ε-1),对每个数据项的处理和查询时间均为O(1).在此基础上,我们还将该算法进行了扩展,可以通过参数的变化得到不同的流数据频繁项挖掘算法,使得算法的时间和空间复杂度之间得到调节.通过大量的实验证明,本文算法比其它类似算法具有更好的精度以及时间和空间效率. 相似文献
8.
一种数据流中的频繁模式挖掘算法 总被引:1,自引:0,他引:1
时序数据流的无限性、流动性和不规则性使得传统的频繁模式挖掘算法难以适用。针对时序数据流的特点,提出了一类特殊非规则数据流频繁模式挖掘的新算法。新算法采用时序数据分段的思想,逐段挖掘局部频繁模式,然后依据局部频繁模式有效地挖掘出所有的全局频繁模式。将新算法应用于电信领域的收入保障项目之中,结果表明,新算法具有良好的性能,能有效发现挖掘时序数据流中的频繁模式。 相似文献
9.
10.
《数字社区&智能家居》2008,(Z2)
介绍了数据流的定义和特点及数据流频繁模式的基本概念。针对数据流的特性,讨论分析了目前国内外数据流频繁模式挖掘算法、算法特性及应用情况,最后展望了数据流频繁模式挖掘的进一步研究工作。 相似文献
11.
近年来,数据流挖掘一直是国内外研究的热点,频繁项集挖掘又是数据流挖掘中的重要问题。根据数据流无限性和流动性的特点,提出了一种在滑动窗口中挖掘频繁项集的算法FIM-SW,FIM-SW算法主要是采用垂直的数据库表示方法,使用二进制向量表示每个数据项,并利用Apriori性质产生频繁项集。实验结果表明,这种算法显著地提高了挖掘效率。 相似文献
12.
提出了一种基于DSM MFI算法的改进算法DSMMFI DS算法,它首先将事务数据按一定的全序关系存入DSFI list列表中;然后按排序后的顺序存储到类似概要数据结构的树中;接着删除树中和DSFI list列表中的非频繁项,同时删除窗口衰退支持数大的事务项;最后采用自顶向下和自底向上的双向搜索策略来挖掘数据流的最大频繁项集。通过用例分析和实验表明,该算法比DSM MFI算法具有更好的执行效率。 相似文献
13.
Methods for mining frequent items in data streams: an overview 总被引:2,自引:2,他引:0
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. 相似文献
14.
Sliding window-based frequent pattern mining over data streams 总被引:2,自引:0,他引:2
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. 相似文献
15.
一些先进应用如欺诈检测和趋势学习等带来了数据流频繁模式挖掘的发展。不同于静态数据,数据流挖掘面临着时空约束和项集组合爆炸等问题。对已有数据流频繁模式挖掘算法进行综述并对经典和最新算法进行分析。按照模式集合的完整程度进行分类,数据流中频繁模式分为全集模式和压缩模式。压缩模式主要包括闭合模式、最大模式、top-k模式以及三者的组合模式。不同之处是闭合模式是无损压缩的,而其他模式是有损压缩的。为了得到有趣的频繁模式,可以挖掘基于用户约束的模式。为了处理数据流中的新近事务,将算法分为基于窗口模型和基于衰减模型的方法。数据流中模式挖掘常见的还包含序列模式和高效用模式,对经典和最新算法进行介绍。最后给出了数据流模式挖掘的下一步工作。 相似文献
16.
17.
近年来随着新的应用的出现,比如网络流量分析、在线事物分析和网络欺诈检测等,对数据流的挖掘成了一个越来越重要的课题。对于数据流频繁项集的挖掘,目前绝大部分的研究都集中在传统的窗口模式下进行,即时间衰退窗口模式、界标窗口模式和滑动窗口模式。Pauray S.M.Tsai于2009年提出了一种新的窗口模式:加权滑动窗口模式,并设计了两个基于此窗口模式的数据流频繁项集挖掘算法WSW和WSW-Imp,其中WSW-Imp是对WSW算法的改进。在研究了加权滑动窗口模式以及WSW-Imp算法的基础上,对WSW-Imp算法作了进一步的改进,设计了算法WSW-Imp2,并从理论上证明了WSW-Imp2算法比WSW-Imp算法更高效,实验结果也表明了这一点。 相似文献
18.
Methods for finding frequent items in data streams 总被引:1,自引:0,他引:1
Graham Cormode Marios Hadjieleftheriou 《The VLDB Journal The International Journal on Very Large Data Bases》2010,19(1):3-20
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. 相似文献