共查询到20条相似文献,搜索用时 156 毫秒
1.
挖掘数据流滑动时间窗口内Top-K频繁模式 总被引:1,自引:0,他引:1
陈辉 《小型微型计算机系统》2010,31(6)
由于数据流滑动时间窗口中流数据包含模式的支持度是动态变化的,很难给出一个合适的支持度门限来挖掘数据流滑动时间窗口内的频繁模式.在研究数据流滑动时间窗口内流数据变化特点的基础上,论文提出了一种挖掘数据流滑动时间窗口内Top-k频繁模式的方法,该方法能够在保证模式挖掘误差基础上快速删除窗口内不频繁模式信息,保留重要的模式信息,并能按照支持度降序输出Top-k频繁模式.仿真实验结果表明,该算法具有较好的效率和正确性,并优于其它同类算法. 相似文献
2.
基于时间衰减模型的数据流频繁模式挖掘 总被引:1,自引:0,他引:1
频繁模式挖掘是数据流挖掘中的重要研究课题. 针对数据流的时效性和流中心的偏移性特点, 提出了界标窗口模型与时间衰减模型相结合的数据流频繁模式挖掘算法. 该算法通过动态构建全局模式树, 利用时间指数衰减函数对模式树中各模式的支持数进行统计, 以此刻画界标窗口内模式的频繁程度; 进而, 为有效降低空间开销, 设计了剪枝阈值函数, 用于对预期难以成长为频繁的模式及时从全局树中剪除. 本文对出现在算法中的重要参数和阈值进行了深入分析. 一系列实验表明, 与现有同类算法MSW相比, 该算法挖掘精度高(平均超过90%), 内存开销小, 速度上可以满足高速数据流的处理要求, 且可以适应不同事务数量、不同事务平均长度和不同最大潜在频繁模式平均长度的数据流频繁模式挖掘. 相似文献
3.
4.
为了更好的挖掘数据流,对传统的滑动窗口机制进行改进,提出一种大小可变的滑动窗口机制的数据流频繁集挖掘算法DS-stream算法.该算法能够根据数据流的数据分布变化自适应调整窗口大小,节省了没必要的空间与时间消耗.算法采用一种分区窗口机制,结合基本窗口和时间窗口,同时考虑数据流的海量特性和时变特性,利用前缀树的概要数据结... 相似文献
5.
张月琴 《计算机工程与应用》2010,46(16):132-134
根据数据流的流动性与连续性,提出了一种滑动窗口中频繁项集挖掘算法NSW,满足了人们快速获取最近到达数据中频繁项集的需求。该算法采用二进制矩阵表示滑动窗口中的事务列表,通过直接删除最老事务、不产生候选项集等方法控制时间和空间的开销。实验表明,该算法具有较好的时间和空间效率。 相似文献
6.
7.
数据流的流动性与连续性,使得数据流所蕴含的知识会随着时间的推移而发生变化。挖掘数据流中的频繁项集是一项意义重大且具有挑战性的工作。提出一种基于滑动窗口数据流的频繁项集挖掘——FIUT-Stream算法,FIUT-Stream算法分块挖掘数据流,在内存中维持一个滑动窗口数据的概要结构,随着窗口滑动动态更新该存储结构,利用FIUT算法进行频繁项集挖掘。实验表明,该算法能节省内存空间、精确获得频繁项集。 相似文献
8.
一种基于时间衰减模型的数据流闭合模式挖掘方法 总被引:1,自引:0,他引:1
数据流是随着时间顺序快速变化的和连续的,对其进行频繁模式挖掘时会出现概念漂移现象。在一些数据流应用中,通常认为最新的数据具有最大的价值。数据流挖掘会产生大量无用的模式,为了减少无用模式且保证无损压缩,需要挖掘闭合模式。因此,提出了一种基于时间衰减模型和闭合算子的数据流闭合模式挖掘方式TDMCS (Time-Decay-Model-based Closed frequent pattern mining on data Stream)。该算法采用时间衰减模型来区分滑动窗口内的历史和新近事务权重,使用闭合算子提高闭合模式挖掘的效率,设计使用最小支持度-最大误差率-衰减因子的三层架构避免概念漂移,设计一种均值衰减因子平衡算法的高查全率和高查准率。实验分析表明该算法适用于挖掘高密度、长模式的数据流;且具有较高的效率,在不同大小的滑动窗口条件下性能表现是稳态的,同时也优于其他同类算法。 相似文献
9.
10.
时间敏感数据流上的频繁项集挖掘算法 总被引:3,自引:0,他引:3
数据流中的数据分布随着时间动态变化,但传统基于事务的滑动窗口模型难以体现该特征,因此挖掘结果并不精确.首先提出时间敏感数据流处理中存在的问题,然后建立基于时间戳的滑动窗口模型,并转换为基于事务的可变滑动窗口进行处理,提出了频繁项集的挖掘算法FIMoTS.该算法引入了类型变化界限的概念,将项集进行动态分类,根据滑动窗口大小的变化对项集进行延迟处理,仅当项集的类型变化界限超出一定阈值的时候才进行支持度的重新计算,能够达到剪枝的目的.在4种不同密度的数据集上完成的实验结果显示,该算法能够在保证内存开销基本不变的情况下显著提高计算效率. 相似文献
11.
Broadcast disk technique has been often used to disseminate frequently requested data efficiently to a large volume of mobile clients over wireless channels. In broadcast disk environments, a server often broadcasts different data items with differing frequencies to reflect the skewed data access patterns of mobile clients. Previously proposed concurrency control methods for mobile transactions in wireless broadcast environments are focused on the mobile transactions with uniform data access patterns. These protocols perform poorly in broadcast disk environments where the data access patterns of mobile transactions are skewed. In broadcast disk environments, the time length of a broadcast cycle usually becomes large to reflect the skewed data access patterns. This will often cause read-only transactions to access old data items rather than the latest data items. Furthermore, updating mobile transactions will be frequently aborted and restarted in the final validation stage due to the update conflict of the same data items with high access frequencies. This problem will increase the average response time of the update mobile transactions and waste the uplink communication bandwidth. In this paper, we extend the existing FBOCC concurrency control method to efficiently handle mobile transactions with skewed data access patterns in broadcast disk environments. Our method allows read-only transactions to access the more updated data, and reduces the average response time of updating transactions through early aborts and restarts. Our method also reduces the amount of uplink communication bandwidth for the final validation of the update transactions. We present an in-depth experimental analysis of our method by comparing with existing concurrency control protocols. Our performance analysis shows that it significantly decreases the average response time and the amount of uplink bandwidths over existing methods. 相似文献
12.
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. 相似文献
13.
Finding recently frequent itemsets adaptively over online transactional data streams 总被引:1,自引:0,他引:1
A data stream is a massive unbounded sequence of data elements continuously generated at a rapid rate. Consequently, the knowledge embedded in a data stream is more likely to be changed as time goes by. Identifying the recent change of a data stream, especially for an online data stream, can provide valuable information for the analysis of the data stream. However, most of mining algorithms or frequency approximation algorithms over a data stream do not differentiate the information of recently generated data elements from the obsolete information of old data elements which may be no longer useful or possibly invalid at present. Therefore, they are not able to extract the recent change of information in a data stream adaptively. This paper proposes a data mining method for finding recently frequent itemsets adaptively over an online transactional data stream. The effect of old transactions on the current mining result of a data steam is diminished by decaying the old occurrences of each itemset as time goes by. Furthermore, several optimization techniques are devised to minimize processing time as well as memory usage. Finally, the performance of the proposed method is analyzed by a series of experiments to identify its various characteristics. 相似文献
14.
Sliding window is a widely used model for data stream mining due to its emphasis on recent data and its bounded memory requirement. The main idea behind a transactional sliding window is to keep a fixed size window over a data stream. The window size is kept constant by removing old transactions from the window, when new transactions arrive. Older transactions of window are removed irrespective to whether a significant change has occurred or not. Another challenge of sliding window model is determining window size. The classic approach for determining the window size is to obtain it from the user. In order to determine the precise size of the window, the user must have prior knowledge about the time and scale of changes within the data stream. However, due to the unpredictable changing nature of data streams, this prior knowledge cannot be easily determined. Moreover, by using a fixed window size during a data stream mining, the performance of this model is degraded in terms of reflecting recent changes. Based on these observations, this study relaxes the notion of window size and proposes a new algorithm named VSW (Variable Size sliding Window frequent itemset mining) which is suitable for observing recent changes in the set of frequent itemsets over data streams. The window size is determined dynamically based on amounts of concept change that occurs within the arriving data stream. The window expands as the concept becomes stable and shrinks when a concept change occurs. In this study, it is shown that if stale transactions are removed from the window after a concept change, updated frequent itemsets always belong to the most recent concept. Experimental evaluations on both synthetic and real data show that our algorithm effectively detects the concept change, adjust the window size, and adapts itself to the new concepts along the data stream. 相似文献
15.
窗口模式下在线数据流中频繁项集的挖掘* 总被引:1,自引:1,他引:0
拟采用一种基于滑动窗模式的单遍挖掘算法,专注于处理近期数据;为了减少处理时间和占用的内存,设计了一种新的事务表示方法。通过处理这个事务的表达式,频繁项集可以被高效输出,并解决了使用基于Apriori理论的算法时,由候选频繁1-项集生成频繁2-项集时数据项顺序判断不准确问题。该算法称为MRFI-SW算法。 相似文献
16.
《Information and Software Technology》2006,48(7):606-618
Conventional data mining methods for finding frequent itemsets require considerable computing time to produce their results from a large data set. Due to this reason, it is almost impossible to apply them to an analysis task in an online data stream where a new transaction is continuously generated at a rapid rate. An algorithm for finding frequent itemsets over an online data stream should support flexible trade-off between processing time and mining accuracy. Furthermore, the most up-to-date resulting set of frequent itemsets should be available quickly at any moment. To satisfy these requirements, this paper proposes a data mining method for finding frequent itemsets over an online data stream. The proposed method examines each transaction one-by-one without any candidate generation process. The count of an itemset that appears in each transaction is monitored by a lexicographic tree resided in main memory. The current set of monitored itemsets in an online data stream is minimized by two major operations: delayed-insertion and pruning. The former is delaying the insertion of a new itemset in recent transactions until the itemset becomes significant enough to be monitored. The latter is pruning a monitored itemset when the itemset turns out to be insignificant. The number of monitored itemsets can be flexibly controlled by the thresholds of these two operations. As the number of monitored itemsets is decreased, frequent itemsets in the online data stream are more rapidly traced while they are less accurate. The performance of the proposed method is analyzed through a series of experiments in order to identify its various characteristics. 相似文献
17.
Hui Chen 《Journal of Intelligent Information Systems》2014,42(1):111-131
Frequent pattern mining in data streams is an important research topic in the data mining community. In previous studies, a minimum support threshold was assumed to be available for mining frequent patterns. However, setting such a threshold is typically difficult. Hence, it is more reasonable to ask users to set a bound on the result size. The present study considers mining top-k frequent patterns from data streams using a sliding window technique. A single-pass algorithm, called MSWTP, is developed for the generation of top-k frequent patterns without a threshold. In the method, the content of the transactions in the sliding window is incrementally maintained in a summary data structure, named SWTP-tree, by scanning the stream only once. To make the mining operation efficient, insignificant patterns are distinguished from others by applying the Chernoff bound. Two kinds of obsolete pattern and one kind of insignificant pattern are periodically pruned from the pattern tree. Whenever necessary, the k most frequent patterns can be selected from SWTP-tree in order of their descending frequency. The performance of the proposed technique is evaluated via simulation experiments. The results show that the proposed method is both efficient and scalable, and that it outperforms comparable algorithms. 相似文献
18.
Ying-Ho Liu 《Applied Intelligence》2013,39(2):315-344
In this paper, we propose mining frequent patterns from univariate uncertain data streams, which have a quantitative interval for each attribute in a transaction and a probability density function indicating the possibilities that the values in the interval appear. Many data streams comprise flows of univariate uncertain data, for example, the records of atmospheric pollution sensors, and network monitoring records. We propose two algorithms to address this issue: the ExactU2Stream algorithm and the ApproxiU2Stream algorithm. The former incrementally stores the incoming transactions, and delays the mining process until it is requested. The latter mines the transactions immediately when they arrive, and stores the derived frequent patterns. Compared with the latter, the former returns results that are more accurate, but it also requires more response time. Both algorithms utilize the sliding window scheme, which decomposes the continuous data stream into discrete, overlapping chunks. The proposed algorithms outperform the compared methods in terms of runtime and memory usage. We have applied the two proposed algorithms to the data streams recording the air quality in Taiwan; the derived frequent patterns not only show the common air quality in Taiwan but also show the extremely bad air quality when a sand storm affects Taiwan. 相似文献
19.
序列模式挖掘就是在时序数据库中挖掘相对时间或其他模式出现频率高的模式.序列模式发现是最重要的数据挖掘任务之一,并有着广阔的应用前景.针对静态数据库,序列模式挖掘已经被深入的研究.近年来,出现了一种新的数据形式:数据流.针对基于数据流的序列模式挖掘的研究还不是十分深入.提出一个有效的基于数据流的挖掘频繁序列模式的算法SSPM,利用到2个数据结构(F-list和Tatree)来处理基于数据流的序列模式挖掘的复杂性问题.SSPM的优点是可以最大限度地降低负正例的产生,实验表明SSPM具有较高的准确率. 相似文献
20.
基于概率衰减窗口模型的不确定数据流频繁模式挖掘 总被引:2,自引:0,他引:2
考虑到不确定数据流的不确定性,设计了一种新的概率频繁模式树PFP-tree和基于该树的概率频繁模式挖掘方法PFP-growth.PFP-growth使用事务性不确定数据流及概率衰减窗口模型,通过计算各概率数据项的期望支持度以发现概率频繁模式,其主要特点有:考虑到窗口内不同时间到达数据项的贡献度不同,采用概率衰减窗口模型计算期望支持度,以提高模式挖掘准确度;设置数据项索引表和事务索引表,以加快频繁模式树检索速度;通过剪枝删除不可能成为频繁模式的结点,以降低模式树的存储及检索开销;对每个结点都设立一个事务概率信息链表,以支持数据项在不同事务中具有不同概率的情形.实验结果表明,PFP-growth在保证挖掘模式准确度的前提下,在处理时间和内存空间等方面都具有较好的性能. 相似文献