基于STORM的流数据分类挖掘算法的研究

发布时间：2018-05-02 06:12

本文选题：流数据 + 分类挖掘　；参考：《南京邮电大学》2016年硕士论文

【摘要】：随着网络、传感器技术的快速发展与应用,越来越多的流数据正在产生,因此针对流数据的挖掘技术逐步兴起。流数据挖掘是指从大规模、快速到达、异构的数据源中有效地挖掘有价值知识的数据处理技术。本文把面向流数据的分类挖掘算法作为研究重点,以提高流数据分类挖掘效率以及分类精度为目标,既研究算法本身的改进又研究算法基于流数据处理平台Storm的分布式并行化。以提高实时在线流数据的分类挖掘时间效率为目标,将快速决策树算法VFDT部署到流数据计算平台Storm上,设计了VFDT算法基于Storm的分布式并行化方案。通过正确设计Topology中的Spout/Bolt实现各模块的功能,通过为分类Bolt设定多个Task来实现分类模块的并行化;用内存数据库Redis实现模块的有效衔接和决策树的保存;用消息中间件Kafka来提高算法对流数据突增的容忍度。基于该方案的VFDT算法实现与测试结果表明,在Storm集群环境下,VFDT算法的时间效率相对于单机环境有显著提高,而且合理设定分类Bolt的Task可使分类效率进一步提高。针对高维数据集,以进一步提高在线流数据分类模型建立的时间效率为目标,对VFDT算法实施垂直并行化,设计了垂直并行化的快速决策树算法(Vertical Parallelism Very Fast Decision Tree,VPVFDT)。该算法将VFDT算法的属性信息增益的计算做并行化处理,从而提高样本处理效率。在此基础上,通过将VPVFDT部署到Storm平台上运行,更进一步提高了算法的处理效率,也增强了算法的可拓展性。实验结果表明,在Storm集群环境下,VPVFDT算法在一定程度上可以提高高维训练样本的处理效率。以提高VFDT算法的分类精确度为目标,将随机森林算法思想集成到VFDT算法中,提出了基于随机森林的快速决策树算法(Random Forest Very Fast Decision Tree,RFVFDT)。RFVFDT算法采用随机森林的决策树构造标准建立分类器模型,并采用滑动窗口技术来满足流数据的无界性以及避免在算法执行过程中的延迟和数据丢失。通过基于Storm平台的仿真实验验证了RFVFDT算法在分类精度和可拓展性方面的优势。本文所研究的方案和算法能适应大规模流数据的实时性、快速性和无限性,研究内容较先进,研究成果具有一定的理论价值和较好的实用性,可用于电子商务、互联网等拥有流数据的应用场景。
[Abstract]:With the rapid development and application of network and sensor technology, more and more stream data are being generated. Stream data mining is a kind of data processing technology which can effectively mine valuable knowledge from large scale, fast arriving and heterogeneous data sources. This paper focuses on the classification mining algorithm for stream data, aiming at improving the efficiency and accuracy of stream data classification mining. It not only studies the improvement of the algorithm itself, but also studies the distributed parallelization of the algorithm based on the stream data processing platform Storm. In order to improve the efficiency of classifying and mining real-time online stream data, the fast decision tree algorithm (VFDT) is deployed to the stream data computing platform (Storm), and a distributed parallelization scheme based on Storm is designed for VFDT algorithm. Through the correct design of Spout/Bolt in Topology to realize the function of each module, by setting several Task for classification Bolt to realize the parallelization of classification module, using the memory database Redis to realize the effective connection of module and the preservation of decision tree; The message middleware Kafka is used to improve the tolerance of algorithm convection data burst. The implementation and test results of VFDT algorithm based on this scheme show that the time efficiency of VFDT algorithm in Storm cluster environment is significantly higher than that in single machine environment, and the classification efficiency can be further improved by reasonably setting the Task of classification Bolt. Aiming at high dimensional data sets, aiming at further improving the time efficiency of online data classification model, the vertical parallelization of VFDT algorithm is implemented, and a fast decision tree algorithm, Vertical Parallelism Very Fast Decision tree algorithm, is designed. The algorithm parallelizes the calculation of the attribute information gain of the VFDT algorithm to improve the efficiency of sample processing. On this basis, by deploying VPVFDT to the Storm platform, the processing efficiency of the algorithm is further improved and the expansibility of the algorithm is also enhanced. The experimental results show that the VPVFDT algorithm can improve the processing efficiency of high-dimensional training samples in Storm cluster environment. In order to improve the classification accuracy of VFDT algorithm, the idea of stochastic forest algorithm is integrated into VFDT algorithm. A fast decision tree algorithm based on random forest, Random Forest Very Fast Decision tree algorithm named Random Forest Very Fast Decision tree, is proposed to establish classifier model by using the decision tree construction standard of random forest. The sliding window technique is used to satisfy the unboundedness of the stream data and to avoid the delay and data loss in the execution of the algorithm. Simulation experiments based on Storm platform verify the advantages of RFVFDT algorithm in classification accuracy and scalability. The scheme and algorithm studied in this paper can adapt to the real-time, fast and infinity of large-scale stream data, and the research content is advanced. The research results have certain theoretical value and good practicability, and can be used in electronic commerce. Application scenarios with streaming data, such as the Internet.
【学位授予单位】：南京邮电大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP311.13

【相似文献】