分布式并行化数据流频繁模式挖掘算法

为了提高数据流频繁模式挖掘的效率,文中基于经典的数据流频繁模式挖掘算法FP-Stream和分布式并行计算原理,设计了一种分布式并行化数据流频繁模式挖掘算法—DPFP-Stream(Distributed Parallel Algorithm of Mining Frequent Pattern on Data Stream)。该算法将建立频繁模式树的任务分为local和global两部分,并设置了参数"当前时间";将到达的流数据平均分配到多个不同的local节点,各local节点使用FP-Growth算法产生该单位时间内本节点的候选频繁项集,并按照单位时间将候选频繁项集及其支持度计数打包发送至global节点;global节点按"当前时间"合并各local节点的中间结果并更新模式树Pattern-Tree。在分布式数据流计算平台Storm上进行的算法实现和性能测试结果表明,DPFP-Stream算法的计算效率能够随着local节点或local bolt线程的增加而提高,适用于高效挖掘数据流中的频繁模式。

面向Redis的数据序列化算法研究

为了解决实时计算中半结构化和非结构化数据的存储问题,借助内存数据库Redis可以存储键值型数据和支持全内存运算的优势,结合文件序列化、图像序列化、JSON序列化和Java对象序列化技术,设计了面向Redis的半结构化和非结构化数据的序列化算法。该序列化算法不仅解决了半结构化和非结构化数据无法直接存入Redis的问题,而且由于在序列化过程中实现了对这些数据的深拷贝,使得反序列化可以完美地还原初始数据。此外,序列化过程还支持通过加解密来保障数据安全。基于Storm平台的实验结果表明,所设计的序列化算法快速、有效且性能稳定。在海量数据实时计算中,无论使用哪种开发语言,将该算法与Redis数据库结合,既能利用Redis带来的高读写效率,又能存储任何半结构化和非结构化数据对象而无需重复开发代码。

面向流数据的DPFP-Stream算法的设计与实现

从海量数据中发现频繁模式一直是数据挖掘研究的热点,在零售市场数据分析、网络监控、网络使用挖掘和股票市场的预测等领域中也有着广泛的应用。尽管在过去的十年里,很多学者提出了许多基于静态数据集的频繁模式挖掘算法,而由于流数据持续、无限、有序而高速产生的特性,在流数据中隐藏的数据知识很可能随着时间的推移而产生变化,因而基于流数据的频繁模式挖掘应不同于以往基于静态数据集的频繁模式挖掘算法。为了更好地分析在线流数据,基于不同的时间粒度从流数据中抽取频繁模式并且监控频繁模式的变化,基于高效的FP-tree结构,借助倾斜时间窗口和MapReduce的思想,提出了针对数据流的频繁模式挖掘算法DPFP-stream。并将该算法在Storm平台上实现,算法数据源采用Kafka,并将中间结果存入内存数据库Redis中。通过大量的实验表明,该算法从高速的数据流中发现频繁模式的效率很高且性能稳定。在海量数据实时计算中,采用该算法,不仅能应对高速的数据流,而且能监控不同时间粒度的频繁模式的变化过程。

基于主成分分析的并行化数据流降维算法研究

降维是指将样本从输入空间通过线性或非线性方法映射到一个低维空间,从而获得一个关于原数据集的低维表示的过程,它是高维数据挖掘的重要预处理手段之一。文中以适应数据流挖掘需求和保证降维后数据的可用性为目标,设计了基于主成分分析的并行化数据流降维算法PSPCA。该算法使用滑动窗口机制来确定处理数据的范围,同时合并了PCA的标准化过程,改变了相关系数矩阵的计算方法,将有关计算过程基于MapReduce并行化,还将所设计的算法基于流平台Storm进行了实现。并以聚类算法K-means为例,通过实验,对比了K-means在降维前和降维后的数据集上的聚类效果。实验结果表明,PSPCA适用于数据流降维,且降维后的数据能将原数据的信息量保留在合理范围内,能保证后续数据挖掘的准确性。