Survey of Ensemble Classification Algorithms for Data Streams with Concept Drift

doi:10.19678/j.issn.1000-3428.0055747

Abstract

Abstract: This paper overviews available ensemble classification algorithms for data streams with concept drift,in terms of their basic concepts,related studies,scope of applications and advantages/disadvantages.Among the ensemble classification algorithms,those for sudden drifts,gradual drifts,reoccurring drifts and incremental drifts are analyzed in detail.This paper also focuses on the learning strategy and key techniques used in the algorithms,including Bagging,Boosting,base classifier combination,online learning,block-based ensembles,and incremental learning.Then this paper points out the main problems to be solved by existing ensemble classification algorithms for data streams.At last,this paper analyzes and prospects the directions of further studies,including dynamic updates for ensemble base classifiers,weighted combination of ensemble base classifiers,rapid detection of multi-typed concept drift,etc.

Key words: dynamic data stream, ensemble, classification, concept drift, incremental learning

摘要： 针对概念漂移数据流集成分类算法的基本概念、相关工作、适用范围及优缺点等方面进行具体阐述，重点分析突变型、渐变型、重复型和增量型集成分类算法，以及集成分类中的Bagging、Boosting、基分类器组合学习策略与在线学习、基于块的集成、增量学习关键技术，指出现阶段概念漂移数据流集成分类算法所需解决的主要问题，并对集成基分类器的动态更新与加权组合、多类型概念漂移的快速检测等研究方向进行分析和展望。

关键词: 动态数据流, 集成, 分类, 概念漂移, 增量学习

CLC Number:

TP393

DU Shiyu, HAN Meng, SHEN Mingyao, ZHANG Chunyan, SUN Rui. Survey of Ensemble Classification Algorithms for Data Streams with Concept Drift[J]. Computer Engineering, 2020, 46(1): 15-24,30.

杜诗语, 韩萌, 申明尧, 张春砚, 孙蕊. 概念漂移数据流集成分类算法综述[J]. 计算机工程, 2020, 46(1): 15-24,30.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0055747

http://www.ecice06.com/EN/Y2020/V46/I1/15

Figures/Tables 2

References

[1] ZHAO Qiangli,JIANG Yanhuang,XU Ming.Incremental learning by heterogeneous Bagging ensemble[C]//Proceedings of the 6th International Conference Advanced Data Mining and Applications.Berlin,Germany:Springer,2010:1-12.
[2] LIANG N Y,HUANG G B,SARATCHANDRAN P,et al.A fast and accurate online sequential learning algorithm for feedforward networks[J].IEEE Transactions on Neural Networks,2006,17(6):1411-1423.
[3] BIFET A,HOLMES G,PFAHRINGER B.Leveraging Bagging for evolving data streams[C]//Proceedings of European Conference on Machine Learning and Knowledge Discovery in Databases.Berlin,Germany:Springer,2010:135-150.
[4] REN Siqi,LIAO Bo,ZHU Wen,et al.Knowledge-maximized ensemble algorithm for different types of concept drift[J].Information Sciences,2018,430:261-281.
[5] BRZEZINSKI D,STEFANOWSKI J.Accuracy updated ensemble for data streams with concept drift[C]//Proceedings of the 6th International Conference on Hybrid Artificial Intelligent Systems.Berlin,Germany:Springer,2011:155-163.
[6] TEGJYOT S S,MEHMED K.Handling adversarial concept drift in streaming data[J].Expert Systems with Applications,2018,97:18-40.
[7] FRIEDMAN J,HASTIE T,TIBSHIRANI R.Additive logistic regression:a statistical view of Boosting(with discussion and a rejoinder by the authors)[J].The Annals of Statistics,2000,28(2):337-407.
[8] BRZEZINSKI D,STEFANOWSKI J.Combining block-based and online methods in learning ensembles from concept drifting data streams[J].Information Sciences,2014,265:50-67.
[9] GU Xiaofeng,XU Jiawen,HUANG Shijing,et al.An improving online accuracy updated ensemble method in learning from evolving data streams[C]//Proceedings of International Computer Conference on Wavelet Active Media Technology and Information Processing.Washington D.C.,USA:IEEE Press,2015:1-8.
[10] YIN Xucheng,HUANG Kaizhu,HAO Hongwei.DE²:dynamic ensemble of ensembles for learning nonstationary data[J].Neurocomputing,2015,165:14-22.
[11] JOAO R B J,NICOLETTI M D C.An iterative boosting-based ensemble for streaming data classification[J].Information Fusion,2018,45:66-78.
[12] WANG Biao,MAO Zhizhong.Outlier detection based on a dynamic ensemble model:applied to process monitoring[J].Information Fusion,2019,51:244-258.
[13] STREET W N,KIM Y.A Streaming Ensemble Algorithm(SEA) for large-scale classification[C]//Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2001:377-382.
[14] WANG Haixun,FAN Wei.Mining concept-drifting data streams using ensemble classifiers[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2003:226-235.
[15] MAHDI O A,PARDEDE E,CAO J L.Combination of information entropy and ensemble classification for detecting concept drift in data stream[C]//Proceedings of Australasian Computer Science Week Multiconference.Australia,Sydney:[s.n.],2018:1-7.
[16] ABDUALRHMAN M,PADMA M C.Deterministic concept drift detection in ensemble classifier based data stream classification process[J].International Journal of Grid and High Performance Computing,2019,11(4):29-48.
[17] SU Guanming,ZHANG Chengcui,WANG Haohong,et al.Selection-based resampling ensemble algorithm for nonstationary imbalanced stream data learning[EB/OL].[2019-07-08].https://www.researchgate.net/publication/328045547_Selection-based_resampling_ensemble_algorithm_for_nonstationary_imbalanced_stream_data_learning.
[18] ESCOVEDO T,KOSHIYAMA A,VELLASCO M,et al.DetectA:abrupt concept drift detection in non-stationary environments[J].Applied Soft Computing,2018,62:119-133.
[19] GAMA J,MEDAS P,CASTILLO G,et al.Learning with drift detection[M].Berlin,Germany:Springer,2004.
[20] BAENA-GARCIA M,CAMPO-AVILA J,FIDALGO R.Early drift detection method[C]//Proceedings of the 17th European Conference on Machine Learning.Berlin,Germany:Springer,2006:77-86.
[21] BARROS R S M,CABRAL D R L,GONCALVES P M,et al.RDDM:reactive drift detection method[J].Expert Systems with Applications,2017,90:344-355.
[22] ABBASZADEH O,AMIRI A,KHANTEYMOORI A R.An ensemble method for data stream classification in the presence of concept drift[J].Frontiers of Information Technology and Electronic Engineering,2015,16(12):1059-1068.
[23] GONCALVES P M,BARROS R S M.RCD:a recurring concept drift framework[J].Pattern Recognition Letters,2013,34(9):1018-1025.
[24] ZHANG Hang,LIU Weike,SHAN Jicheng,et al.Online active learning paired ensemble for concept drift and class imbalance[EB/OL].[2019-07-08].https://www.researchgate.net/publication/329159411_Online_Active_Learning_Paired_Ensemble_for_Concept_Drift_and_Class_Imbalance.
[25] SANTOS S G T C,GONCALVES P M,SILVA G D S,et al.Speeding up recovery from concept drifts[C]//Proceedings of European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases.Washington D.C.,USA:IEEE Press,2014:179-194.
[26] BARROS R S M,SANTOS S G T C,GONCALVES P M.A Boosting-like online learning ensemble[C]//Proceedings of 2016 IEEE International Conference on Neural Networks.Washington D.C.,USA:IEEE Press,2016:1871-1878.
[27] BABU D K,RAMADEVI Y,RAMANA K V.RGNBC:Rough Gaussian naive Bayes classifier for data stream classification with recurring concept drift[J].Arabian Journal for Science and Engineering,2017,42(2):705-714.
[28] LI Hongtao.Research on dynamic learning for data stream Bayesian classification[D].Beijing:Beijing Jiaotong University,2018.(in Chinese) 李宏韬.面向数据流贝叶斯分类的动态学习策略研究[D].北京:北京交通大学,2018.
[29] MIRZA B,LIN Z,LIU N.Ensemble of subset online sequintal extreme learning machine for class imbalance and concept drift[J].Neurocomputing,2015,149:316-329.
[30] LI Peipei,WU Xindong,LIANG Qianhui,et al.Learning concept-drifting data streams with random ensemble decision trees[J].Neurocomputing,2015,166:68-83.
[31] HAN Jie,NI Zhiwei,JU Dongdong,et al.A classification algorithm for mining data streams based on naive Bayes and unsupervised learning[C]//Proceedings of the 12th China Management Annual Conference.Tianjin:[s.n.],2017:1-5.(in Chinese) 韩杰,倪志伟,巨东东,等.基于朴素贝叶斯和无监督学习的数据流分类算法[C]//第十二届中国管理学年会论文集.天津:[出版者不详],2017:1-5.
[32] KRAWCZYK B,CANO A.Online ensemble learning with abstaining classifiers for drifting and noisy data streams[J].Applied Soft Computing,2018,68:677-692.
[33] CHU Guang,HU Xuegang,ZHANG Yuhong.Semantic-based concept drift detection algorithm for text data stream[J].Computer Engineering,2018,44(2):24-30.(in Chinese) 储光,胡学钢,张玉红.基于语义的文本数据流概念漂移检测算法[J].计算机工程,2018,44(2):24-30.
[34] MINKU L L,YAO X.DDD:a new ensemble approach for dealing with concept drift[J].IEEE Transactions on Knowledge and Data Engineering,2012,24(4):619-633.
[35] COLLELL G,PRELEC D,PATIL K R.A simple plug-in Bagging ensemble based on threshold-moving for classifying binary and multiclass imbalanced data[J].Neurocomputing,2018,275:330-340.
[36] GU Hui,XU Lu,TU Mengying,et al.Bagging classification tree-based robust variable selection for radial basis function network modeling in metabonomics data analysis[J].Chemometrics and Intelligent Laboratory Systems,2018,174:76-84.
[37] CHENG Jin,WANG Jian.An association-based evolutionary ensemble method of variable selection[J].Expert Systems with Applications,2019,124(15):143-155.
[38] RAGHUWANSHI B S,SHUKLA S.Under Bagging based reduced kernelized weighted extreme learning machine for class imbalance learning[J].Engineering Applications of Artificial Intelligence,2018,74:252-270.
[39] RAGHUWANSHI B S,SHUKLA S.Class imbalance learning using under Bagging based kernelized extreme learning machine[J].Neurocomputing,2019,329:172-187.
[40] SUN J,LANG J,FUJITA H,et al.Imbalanced enterprise credit evaluation with DTE-SBD:decision tree ensemble based on SMOTE and Bagging with differentiated sampling rates[J].Information Sciences,2018,425:76-91.
[41] LEE S J,XU Z,LI T,et al.A novel Bagging C4.5 algorithm based on wrapper feature selection for supporting wise clinical decision making[J].Journal of Biomedical Informatics,2018,78:144-155.
[42] BEYGELZIMER A,KALE S,LUO H.Optimal and adaptive algorithms for online Boosting[C]//Proceedings of the 32nd International Conference on Machine Learning.Lille,France:[s.n.],2015:2313-2321.
[43] YU Z,WANG D,YOU J,et al.Progressive subspace ensemble learning[J].Pattern Recognition,2016,60:692-705.
[44] KIDERA T,OZAWA S,ABE S.An incremental learning algorithm of ensemble classifier systems[C]//Proceedings of International Joint Conference on Neural Networks.Washington D.C.,USA:IEEE Press,2006:3421-3427.
[45] SABZEVARI M,SUAREZ A.Vote-boosting ensembles[J].Pattern Recognition,2018,83:119-133.
[46] MA Xianzhe.Study on data streams classification algorithms based on ensemble classifier[D].Changchun:Northeastern University,2012.(in Chinese)马宪哲.基于集成分类器的数据流分类算法研究[D].长春:东北大学,2012.
[47] BARTOSZ K.One-class classifier ensemble pruning and weighting with firefly algorithm[J].Neurocomputing,2015,150:490-500.
[48] KONRAD J.New diversity measure for data stream classification ensembles[J].Engineering Applications of Artificial Intelligence,2018,74:23-34.
[49] WANG Junhong,XU Shuliang,DUAN Bingqian.An ensemble classification algorithm based on information entropy for data streams[J].Neural Processing Letters,2019,3:1-17.
[50] JABER G,CORNUEJOLS A,TARROUX P.A new on-line learning method for coping with recurring concepts:the ADACC system[C]//Proceedings of International Conference on Neural Information Processing.Berlin,Germany:Springer,2013:595-604.
[51] HU Xugang,WANG Haiyan,LI Peipei.Online Biterm topic model based short text stream classification using short text expansion and concept drifting detection[J].Pattern Recognition Letters,2018,116:187-194.
[52] REN Siqi,LIAO Bo,ZHU Wen,et al.The gradual resampling ensemble for mining imbalanced data streams with concept drift[J].Neurocomputing,2018,286:150-166.
[53] HUANG Shan,WANG Botao,QIU Junhao,et al.Parallel ensemble of online sequential extreme learning machine based on MapReduce[J].Neurocomputing,2016,74:352-367.
[54] XU Shuliang,WANG Junhong.A fast incremental extreme learning machine algorithm for data streams classification[J].Expert Systems with Applications,2016,65:332-344.
[55] JIA Tao,HAN Meng,WANG Shaofeng,et al.Survey of decision tree classification methods over data streams[J].Journal of Nanjing Normal University(Natural Science Edition),2019,42(3):1-13.(in Chinese)贾涛,韩萌,王少峰,等.数据流决策树分类方法综述[J].南京师大学报(自然科学报),2019,42(3):1-13.
[56] LI Yanxia,CHAI Yi,HU Youqiang,et al.Review of imbalanced data classification methods[J].Control and Decision,2019,34(4):7-12.(in Chinese)李艳霞,柴毅,胡友强,等.不平衡数据分类方法综述[J].控制与决策,2019,34(4):7-12.
[57] WEN Xueyan,CHEN Jianan,JING weipeng,et al.Research on optimization of classification model for imbalanced data set[J].Computer Engineering,2018,44(4):268-273.(in Chinese)温雪岩,陈家男,景维鹏,等.面向不平衡数据集分类模型的优化研究[J].计算机工程,2018,44(4):268-273.

Please choose a citation manager

Content to export