摘要
从海量数据中发现频繁模式一直是数据挖掘研究的热点,在零售市场数据分析、网络监控、网络使用挖掘和股票市场的预测等领域中也有着广泛的应用。尽管在过去的十年里,很多学者提出了许多基于静态数据集的频繁模式挖掘算法,而由于流数据持续、无限、有序而高速产生的特性,在流数据中隐藏的数据知识很可能随着时间的推移而产生变化,因而基于流数据的频繁模式挖掘应不同于以往基于静态数据集的频繁模式挖掘算法。为了更好地分析在线流数据,基于不同的时间粒度从流数据中抽取频繁模式并且监控频繁模式的变化,基于高效的FP-tree结构,借助倾斜时间窗口和MapReduce的思想,提出了针对数据流的频繁模式挖掘算法DPFP-stream。并将该算法在Storm平台上实现,算法数据源采用Kafka,并将中间结果存入内存数据库Redis中。通过大量的实验表明,该算法从高速的数据流中发现频繁模式的效率很高且性能稳定。在海量数据实时计算中,采用该算法,不仅能应对高速的数据流,而且能监控不同时间粒度的频繁模式的变化过程。
Finding frequent patterns in a continuous stream of transactions is critical for many applications such as retail market data analy- sis, 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 or- dered sequence of data elements generated at a rapid rate in a data stream. As a result,the knowledge embedded in a data stream is more likely to be changed as time goes by. Therefore, extracting frequent patterns from data at multiple time granularities and monitoring the gradual changes of frequent patterns can enhance the analysis of online data streams. Based on efficient FP-tree structure,according to the ideas of tilted-time windows and MapReduce,the DPFP-stream is proposed and implemented in Storm. The data resource of it uses Kaf- ka and stores middle result into Redis. Extensive experiment shows that the algorithm proposed is highly efficient in terms of time com- plexity when finding recent frequent patterns from a high-speed data stream. With the application of the algorithm in real-time compu- ting,it can not only process high speed stream,but also monitor the change of frequent patterns with tilted-time windows.
出处
《计算机技术与发展》
2017年第7期29-33,共5页
Computer Technology and Development
基金
国家自然科学基金资助项目(61302158
61571238)
