Random Forest Based Very Fast Decision Tree Algorithm for Data Stream

doi:10.3969/j.issn.1673-5188.2017.S2.009

ZTE Communications ›› 2017, Vol. 15 ›› Issue (S2): 52-57.DOI: 10.3969/j.issn.1673-5188.2017.S2.009

收稿日期:2016-12-02 出版日期:2017-12-25 发布日期:2020-04-16

Random Forest Based Very Fast Decision Tree Algorithm for Data Stream

DONG Zhenjiang¹, LUO Shengmei¹, WEN Tao¹, ZHANG Fayang², LI Lingjuan²

1. ZTE Corporation, Nanjing 210012, China
2. School of Computer, Nanjing University of Posts and Telecommunications, Nanjing 210003, China

Received:2016-12-02 Online:2017-12-25 Published:2020-04-16
About author:DONG Zhenjiang (dong.zhenjiang@zte.com.cn) received his M.S. degree in telecommunication and electronics from Harbin Instituted of Technology in 1996. He is the deputy head of the Service Institute of ZTE Corporation. His research interests include cloud computing and the mobile Internet.|LUO Shengmei (luo.shengmei@zte.com.cn) received his M.S. degree in telecommunication and electronics from Harbin Instituted of Technology in 1996. He is now a chief architect at ZTE Corporation. His research interests include big data, cloud computing and network storage.|WEN Tao (wen.tao1@zte.com.cn) received his M.S. degree in computer science from Nanjing University of Aeronautics and Astronautics, China. He is a senior pre-research engineer at the Cloud Computing & IT Institute of ZTE Corporation. His research interests include cloud computing and big data technologies.|ZHANG Fayang (13041105@njupt.edu.cn ) is pursuing his master degree at School of Computer, Nanjing University of Posts and Telecommunications, China. His research interests include cloud computing, data mining, and big data technologies.|LI Lingjuan (lilj@njupt.edu.cn) is a full professor of School of Computer, Nanjing University of Posts and Telecommunications, China. She received her Ph.D. degree in computer application technology from Soochow University, China. Her research interests include cloud computing, data mining, information security, and big data technologies.
Supported by:
This work was supported by ZTE Industry-Academia-Research Cooperation Funds and National Natural Science Foundation of China under Grant(61302158);This work was supported by ZTE Industry-Academia-Research Cooperation Funds and National Natural Science Foundation of China under Grant(61571238)

摘要/Abstract

Abstract:

The Very Fast Decision Tree (VFDT) algorithm is a classification algorithm for data streams. When processing large amounts of data, VFDT requires less time than traditional decision tree algorithms. However, when training samples become fewer, the label values of VFDT leaf nodes will have more errors, and the classification ability of single VFDT decision tree is limited. The Random Forest algorithm is a combinational classifier with high prediction accuracy and noise-tolerant ability. It is constituted by multiple decision trees and can make up for the shortage of single decision tree. In this paper, in order to improve the classification accuracy on data streams, the Random Forest algorithm is integrated into the process of tree building of the VFDT algorithm, and a new Random Forest Based Very Fast Decision Tree algorithm named RFVFDT is designed. The RFVFDT algorithm adopts the decision tree building criterion of a Random Forest classifier, and improves Random Forest algorithm with sliding window to meet the unboundedness of data streams and avoid process delay and data loss. Experimental results of the classification of KDD CUP data sets show that the classification accuracy of RFVFDT algorithm is higher than that of VFDT. The less the samples are, the more obvious the advantage is. RFVFDT is fast when running in the multi-thread mode.

Key words: data stream, data classification, Random Forest algorithm, VFDT algorithm

. [J]. ZTE Communications, 2017, 15(S2): 52-57.

DONG Zhenjiang, LUO Shengmei, WEN Tao, ZHANG Fayang, LI Lingjuan. Random Forest Based Very Fast Decision Tree Algorithm for Data Stream[J]. ZTE Communications, 2017, 15(S2): 52-57.

图/表 5

Figure 1. Sliding window based on time granularity.

Table 1 Data set used in the experiments

Data set	NA	NCA	NTA_1	NTA_2
Nursery	9	5	380,000	10,000
Connection	42	3	380,000	10,000

Figure 2. The classification accuracy with the size of the training sample set increased.

Figure 3. The processing efficiency with different numbers of decision trees.

Figure 4. The processing efficiency of RFVFDT with different numbers of threads.

参考文献 11

[1]	M. Guo , “Research and design of real-time traffic classification for high-speed network,” MS thesis, Dept. of Computer application technology, Beijing University of Posts and Telecommunications, Beijing, China, 2010.
[2]	A. Bifet and G. De Francisci Morales , “Big data stream learning with samoa,” in IEEE International Conference on Data Mining Workshop, Shenzhen, China, Dec. 2014, pp. 1199-1202. doi: 10.1109/ICDMW.2014.24.
[3]	P. Domingos and G. Hulten , “Mining high-speed data streams,” in Proc. Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, USA, 2000, pp. 71-80. doi: 10.1145/347090.347107.
[4]	J. Gama, R. Rocha, and P. Medas , “Accurate decision trees for mining high speed data stream,” in Proc. Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, USA, 2003, pp. 523-528. doi: 0.1145/956750.956813.
[5]	B. Raahemi, W. Zhong, J. Liu , “Peer-to-Peer Traffic Identification by Mining IP Layer Data stream Using Concept-adapting Very Fast Decision Tree,” in 20th IEEE International Conference on Tools with Artificial Intelligence, Dayton, USA, Nov. 2008, pp. 525-532.doi: 10.1109/ICTAI.2008.12.
[6]	L. Breiman , “Random forests,” Machine Learning, vol. 44, no. 1, pp. 5-32, Oct. 2001. doi: 10.1023/A:1010933404324.
[7]	T. Wang, Z. Li, X. Hu, Y. Yan, and H. Chen , “An incremental fuzzy decision tree classification method for data stream mining based on threaded binary search trees,” Chinese Journal of Computers, vol. 30, no. 8, pp. 1244-1250, Aug. 2007. doi: 10.3321/j.issn:0254-4164.2007.08.005.
[8]	N. Littlestone , “Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm,” Machine Learning, vol. 2, no. 4, pp. 285-318, Apri. 1988. doi: 10.1007/BF00116827.
[9]	O. Maron , “Hoeffding Races--model selection for MRI classification,” MS thesis, Dept. of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, USA, 1994.
[10]	L. Jiang, Z. Cai, Z. Liu , “An algorithm of classification rules mining based on information gain,” Journal of Central South University of Technology, vol. 34, no. 2, pp. 69-71, July 2003.doi: 10.3969/j.issn.1672-7207.2003.z1.020.
[11]	A. Wang, G. Wan, Z. Chen , “Incremental extreme random forest classifier for online learning,” Journal of Software, vol. 22, no. 9, pp. 2059-2074, Sept. 2011. doi: 10.3724/SP.J.1001.2011.03.827.

Random Forest Based Very Fast Decision Tree Algorithm for Data Stream

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 11

相关文章 0

编辑推荐

Metrics