[1]WEN Yimin,QIANG Baohua,FAN Zhigang.A survey of the classification of data streams with concept drift[J].CAAI Transactions on Intelligent Systems,2013,8(2):95-104.[doi:10.3969/j.issn.1673-4785.201208012]
Copy

A survey of the classification of data streams with concept drift

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 8 Number of periods: 2013 2 Page number: 95-104 Column: 综述 Public date: 2013-04-25
Title:
A survey of the classification of data streams with concept drift
Author(s):
WEN Yimin1;  QIANG Baohua1;  FAN Zhigang2
1. College of Computer Science and Engineering, Guilin University of Electronic Technology, Guilin 541004, China;
2. Shanghai Advanced Research Institute, Chinese Academy of Sciences, Shanghai 201203, China
Keywords:
big data;  concept drift;  incremental learning;  adaptive learning;  data stream; machine learning
CLC:
TP391.4
DOI:
10.3969/j.issn.1673-4785.201208012
Abstract:
Because the current machine learning algorithms all are essentially an optimization procedure that aims to ensure the generalization ability based on static learning environment, the classification data streams with concept drift has brought severe challenges to machine learning. In order to address these concerns， a survey was developed consisting of four aspects: the introduction to data streams and concept drift, the development process and future trends, the main research fields, and the new developments in the study field of the classification data streams with concept drift. The existing problems relating to classification data streams with concept drift were discussed at last.
References:
［1］MITCHELL T M. Machine learning［M］. New York: McGraw-Hill, 1997: 15-37.
?［2］SCHLIMMER J，GRANGER R. Incremental learning from noisy data［J］. Machine Learning, 1986, 1(3): 317-354.
［3］GROSSBERG S. Nonlinear neural networks: principles, mechanisms and architecture［J］. Neural Network, 1988, 1(1): 17-61.
［4］KUNCHEVA L I. Classifier ensembles for changing environments［C］//Proceedings of the Fifth Workshop on Multiple Classifier Systems. Cagliari, Italy, 2004: 1-15.
?［5］TSYMBAL A. The problem of concept drift: definitions and related work. TCD-CS-2004-15［R］. Dublin: Department of Computer Science Trinity College, 2004.
?［6］王涛, 李舟军, 颜跃进, 等. 数据流挖掘分类技术综述［J］. 计算机研究与发展, 2007, 44(11): 1809-1815.
?WANG Tao, LI Zhoujun, YAN Yuejin, et al. A survey of classification of data streams［J］. Journal of Computer Research and Development, 2007, 44(11): 1809-1815.
［7］LIOBAITI. Learning under concept drift: an overview［EB/OL］.［2012-01-12］.http://zliobaite.googlepages.com/Zliobaite_CDoverview.pdf.
［8］HOENS T R, POLIKAR R, CHAWLA N V. Learning from streaming data with concept drift and imbalance: an overview［J］. Progress in Artificial Intelligence, 2012, 1(1): 89-101.
［9］GAMA J. A survey on learning from data streams: current and future trends［J］. Progress in Artificial Intelligence, 2012, 1(1): 45-55.
［10］OVERPECK J T, MEEHL G A, BONY S, et al. Climate data challenges in the 21st century［J］. Science, 2011, 331(6018): 700-702.
?［11］STREET W N, KIM Y S. A streaming ensemble algorithm (SEA) for large-scale classification［C］//Proceedings of the Seventh International Conference on Knowledge Discovery and Data Mining. San Francisco, USA, 2001: 377-382.
［12］ANGLUIN D. Queries and concept learning［J］. Machine Learning, 1988, 2(4): 319-342.
［13］DOMINGOS P, HULTEN G. Mining high-speed data stream［C］//Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Boston, USA, 2000: 71-80.
［14］HULTEN G, SPENCER L, DOMINGOS P. Mining time-changing data streams［C］//Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Francisco, USA, 2001: 97-106.
［15］WIDMER G, KUBAT M. Effective learning in dynamic environments by explicit context tracking［C］//Proceedings of the Sixth European Conference on Machine Learning. Vienna, Austria, 1993: 69-101.
?［16］KELLY M, HAND D, ADAMS N. The impact of changing populations on classifier performance［C］//Proceedings of the Fifth International Conference on Knowledge Discovery and Data Mining. San Diego, USA, 1999: 367-371.
［17］NARASIMHAMURTHY A, KUNCHEVA L I. A framework for generating data to simulate changing environments［C］//Proceedings of the 25th IASTED International Multi-Conference: Artificial Intelligence and Applications. Innsbruck, Austria, 2007: 384-389.
［18］MINKU L L, WHITE A P, YAO X. The impact of diversity on online ensemble learning in the presence of concept drift［J］. IEEE Transactions on Knowledge and Data Engineering, 2010, 22(5): 730-742.
［19］ELWELL R, POLIKAR R. Incremental learning of concept drift in nonstationary environments［J］. IEEE Transactions on Neural Networks, 2011, 22(10): 1517-1531.
［20］MASUD M, GAO J, KHAN L, et al. Integrating novel class detection with classification for concept-drifting data streams［C］//Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases. Bled, Slovenia, 2009: 79-94. 
［21］MORENO-TORRES J G, RAEDER T, ALAIZ-RODRIGUEZ R. A unifying view on dataset shift in classification［J］. Pattern Recognition, 2012, 45: 521-530.
［22］KILANDER F, JANSSON C. COBBIT—a control procedure for COBWEB in the presence of concept drift［C］//Proceedings of the Sixth European Conference on Machine Learning. Helsinki, Finland, 1993: 244-261. 
［23］BLACK M, HICKEY R J. Maintaining the performance of a learned classifier under concept drift ［J］. Intelligent Data Analysis, 1999, 3(6): 453-474.
［24］KUN A, PETSCHE T, RIVEST R L. Learning time-varying concepts［C］//Proceedings of the Conference Neural Information Processing Systems. Denver, USA, 1990: 183-189.
［25］HELMBOLD D P, LONG P M. Tracking drifting concepts by minimizing disagreements［J］. Machine Learning, 1994, 14(1): 27-45.
［26］BARVE R D, LONG P M. On the complexity of learning from drifting distributions［C］//Proceedings of the Ninth Annual Conference on Computational Learning Theory. Desenzano Sul Garda, Italy, 1996： 122-130.
［27］DIETTERICH T, WIDMER G, KUBAT M. Special issue on context sensitivity and concept drift［J］. Machine Learning, 1998, 32(2): 83-201.
［28］WANG H, FAN W, YU P S, et al. Mining concept-drifting data streams using ensemble classifiers［C］//Proceedings of the Ninth International Conference on Knowledge Discovery and Data Mining. Washington， DC, USA, 2003: 226-235.
?［29］KOLTER J Z, MALOOF M A. Dynamic weighted majority: a new ensemble method for tracking concept drift ［C］// Proceedings of the Third IEEE International Conference on Data Mining. Washington， DC, USA, 2003: 123-130. 
［30］KOLTER J Z, MALOOF M A. Using additive expert ensembles to cope with concept drift［C］//Proceedings of the 22nd International Conference on Machine Learning. Bonn, Germany, 2005: 449-456.
［31］BIFET A, HOLMES G, PFAHRINGER B, et al. New ensemble methods for evolving data streams［C］//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris, France, 2009: 139-148.
?［32］KLINKENBERG R. Using labeled and unlabeled data to learning drifting concepts［C］//Proceedings of the Workshop Notes of the IJCAI-01 Workshop on Learning from Temporal and Spatial Data. Menlo Park, USA , 2001: 16-24.
［33］KLINKENBERG R. Detection concept drift with support vector machines［C］//Proceedings of the Seventeenth International Conference on Machine Learning. Stanford, California, USA, 2000: 487-494.
［34］LANQUILLON C. Information filtering in changing domains［C］//Proceedings of the 16th International Joint Conference on Artificial Intelligence. Stockholm, Sweden, 1999: 41-48.
［35］KUBAT G, GAMA J, UTGOFF P. Special issue on incremental learning systems capable of dealing with concept drift［Z］. Amsterdam: Intelligent Data Analysis, 2004.
［36］GAO J, DING B, FAN W, et al. Classifying data stream with skewed class distributions and concept drifts［J］. IEEE Transactions on Internet Computing, 2008, 12(6): 37-49 .
［37］CHEN S, HE H. SERA: selectively recursive approach towards nonstationary imbalanced stream data mining［C］//Proceedings of the 2009 International Joint Conference on Neural Networks. Atlanta, USA, 2009: 522-529.
［38］CHEN S, HE H, LI K, et al. MuSeRA: multiple selectively recursive approach towards nonstationary imbalanced stream data mining［C］//Proceedings of the 2010 International Joint Conference on Neural Networks. Barcelona, Spain, 2010: 1-8.
［39］CHEN S, HE H. Towards incremental learning of nonstationary imbalanced data stream: a multiple selectively recursive approach［J］. Evolving Systems, 2010, 2(1): 35-50.
［40］LICHTENWALTER R N, CHAWLA N V. Adaptive methods for classification in arbitrarily imbalanced and drifting data streams［C］//Proceedings of the 13th Pacific-Asia Conference on Knowledge Discovery and Data Mining. Bangkok, Thailand, 2009: 53-75.
［41］GREGORY D, ROBI P. An ensemble based incremental learning framework for concept drift and class imbalance［C］//Proceedings of the 2010 International Joint Conference on Neural Networks. Barcelona, Spain, 2010: 9-17.
［42］ZHANG J, HU X, ZHANG Y, et al. An efficient ensemble method for classifying skewed data streams［C］//Proceedings of the 7th International Conference on Intelligent Computing. Zhengzhou, China, 2011: 144-151.
［43］RAMAMURTHY S, BHATNAGAR R. Tracking recurrent concept drift in streaming data using ensemble classifiers［C］//Proceedings of the 6th International Conference on Machine Learning and Applications. Cincinnati, USA, 2007: 404-409.
［44］LI P P, WU X D, HU X G. Mining recurring concept drifts with limited labeled streaming data［C］//Proceedings of the 2th Asian Conference on Machine Learning. Tokyo, Japan, 2010: 241-252.
［45］MASUD M M, AL-KHATEEB T M, KHAN L, et al. Detecting recurring and novel classes in concept-drifting data streams［C］//Proceedings of the 2011 International Conference on Data Mining. Vancouver, Canada, 2011: 1176-1181.
［46］XUE J C, WEISS G M. Quantification and semi-supervised classification methods for handling changes in class distribution［C］//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris, France, 2009: 897-906.
?［47］ZHANG P, ZHU X, GUO L. Mining data streams with labeled and unlabeled training examples［C］//Proceedings of the Ninth IEEE International Conference on Data Mining. Miami, USA, 2009: 627-636.
［48］LI P, WU X D, HU X G. Learning from concept drift data streams with unlabeled data［C］//Proceedings of the 24th AAAI Conference on Artificial Intelligence. Atlanta, USA, 2010: 1945-1946.
［49］FAN W, HUANG Y, WANG H, et al. Active mining of data streams［C］//Proceedings of the 4th SIAM International Conference on Data Mining. Lake Buena Vista, USA, 2004: 457-461.
［50］ZHU X, ZHANG P, LIN X. Active learning from stream data using optimal weight classifier ensemble［J］. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2010, 40(6): 1607-1621.
［51］MASUD M, GAO J, KHAN L, et al. Classification and novel class detection in data streams with active mining［C］//Proceedings of the 14th Pacific-Asia Conference on Knowledge Discovery and Data Mining. Hyderabad, India, 2010: 311-324.
［52］ZLIOBAITE I, BIFET A, PFAHRINGER B, et al. Active learning with evolving streaming data［C］//Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases. Athens, Greece, 2011, 11: 597-612.
［53］CHU W, ZINKEVICH M, LI L, et al. Unbiased online active learning in data streams［C］//Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego, USA, 2011: 195-203.
［54］KHOLGHI M, KEYVANPOUR M R. Active learning framework combining semi-supervised approach for data stream mining［J］. Intelligent Computing and Information Science, 2011, 135: 238-243.
［55］FORMAN G. Tackling concept drift by temporal inductive transfer［C］//Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Toronto, Canada, 2006: 252-259.
［56］BEN D S, BORBELY R S. A notion of task relatedness yielding provable multiple-task learning guarantees［J］. Machine Learning, 2008, 73(3): 273-287.
［57］FOLINO G, PAPUZZO G. Handling different categories of concept drifts in data streams using distributed GP［C］//Berlin: Springer-Verlag, 2010: 74-85.
［58］YANG S, YAO X. Population-based incremental learning with associative memory for dynamic environments［J］. IEEE Transactions on Evolutionary Computation, 2008, 12(5): 542-561.
［59］WENERSTROM B, GIRAUD-CARRIER C. Temporal data mining in dynamic feature spaces［C］//Proceedings of the 2006 International Conference on Data Mining. Las Vegas, USA, 2006: 1141-1145.
?［60］CHEN H L, CHEN M S, LIN S C. Catching the trend: a framework for clustering concept-drifting categorical data［J］. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(5): 652-665.
［61］MASUD M, GAO J, KHAN L, et al. Classification and novel class detection in concept-drifting data streams under time constraints［J］. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(6): 859-874. 
［62］ZHANG P, LI J, WANG P, et al. Enabling fast prediction for ensemble models on data streams［C］// Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego, USA, 2011: 177-185.
［63］KOREN Y. Collaborative filtering with temporal dynamics［J］. Communications of the ACM, 2010, 53(4): 89-97.
［64］KLINKENBERG R, JOACHIMS T. Detecting concept drift with support vector machines［C］//Proceedings of the 17th International Conference on Machine Learning. San Francisco, USA, 2000: 487-494.
［65］WIDMER G, KUBAT M. Learning in the presence of concept drift and hidden contexts［J］. Machine Learning, 1996, 23(1): 69-101.
［66］FAN W. Systematic data selection to mine concept-drifting data streams［C］//Proceedings of the Tenth International Conference on Knowledge Discovery and Data Mining. Seattle, USA, 2004: 128-137.
［67］SALGANICOFF M. Tolerating concept and sampling shift in lazy learning using prediction error context switching［J］. Artificial Intelligence Review, 1997, 11(1/2/3/4/5): 133-155.
［68］LIOBAITI. Combining similarity in time and space for training set formation under concept drift［J］. Intelligent Data Analysis, 2011, 15(4): 589-611.
［69］KLINKENBERG R. Learning drifting concepts: example selection vs. example weighting［J］. Intelligent Data Analysis, 2004, 8(3): 200-281. 
［70］KOYCHEV I. Gradual forgetting for adaption to concept drift［C］//Proceedings of the ECAI 2000 Workshop Current Issue in Spatio-Temporal Reasoning. Berlin, Germany, 2000: 101-106.
［71］OOMMEN J, RUEDA L. Stochastic learning-based weak estimation of multinomial random variables and its applications to pattern recognition in non-stationary environments［J］. Pattern Recognition, 2006, 39(3): 328-341.
［72］NUNEZ M, FIDALGO R, MORALES R. Learning in environments with unknown dynamics towards more robust concept learners［J］. Journal of Machine Learning Research, 2007, 8: 2595-2628.
［73］KYOSUKE N, KOICHIRO Y, TAKASHI O. ACE: adaptive classifier-ensemble system for concept-drifting environments［C］//Proceedings of the 6th International Workshop on Multiple Classifier Systems. Heidelberg, Germany, 2005: 176-185.
［74］MUHLBAIER M D, POLIKAR R. Multiple classifiers based incremental learning algorithm for learning in nonstationary environments［C］//Proceedings of the 6th IEEE International Conference on Machine Learning and Cybernetics. Hong Kong, China, 2007: 3618-3623.
［75］文益民, 王耀南, 张莹. 基于可信多数投票的快速概念漂移检测［J］. 湖南大学学报：自然科学版, 2010, 37（6）: 36-40.
WEN Yimin, WANG Yaonan, ZHANG Ying. Fast detection of concept drifts based on confident majority voting［J］. Journal of Hunan University：Natural Sciences, 2010, 37（6）: 36-40.
［76］关菁华, 刘大有. 一种挖掘概念漂移数据流的选择性集成算法［J］. 计算机科学, 2010, 37(1)： 204-207. G
UAN Jinghua, LIU Dayou. Selected ensemble of classifiers for handling concept-drifting data streams［J］. Computer Science, 2010, 37(1)： 204-207.
［77］朱群, 张玉红, 胡学钢, 等. 一种基于双层窗口的概念漂移数据流分类算法［J］. 自动化学报, 2011, 37(9): 1078-1083.
ZHU Qun, ZHANG Yuhong, HU Xuegang, et al. A double-window-based classification algorithm for concept drifting data streams［J］. Acta Automatica Sinica, 2011, 37(9): 1078-1083.
［78］孙岳, 毛国君, 刘旭, 等. 基于多分类器的数据流中的概念漂移挖掘［J］. 自动化学报, 2008, 34(1): 93-97.
?SUN Yue, MAO Guojun, LIU Xu, et al. Mining concept drifts from data streams based on multi-classifiers［J］. Acta Automatica Sinica, 2008, 34(1): 93-97.
［79］辛轶, 郭躬德, 陈黎飞, 等. IKnnM-DHecoc：一种解决概念漂移问题的算法［J］. 计算机研究与发展, 2011, 48(4): 592-601.
?XIN Yi, GUO Gongde, CHEN Lifei, et al. IKnnM-DHecoc: a method for handling the problem of concept drift［J］. Journal of Computer Research and Development, 2011, 48(4): 592-601.
［80］KUNCHEVA L I, ZLIOBAITE I. On the window size for classification in changing environments［J］. Intelligent Data Analysis, 2009, 13 (6): 314-323.
［81］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.
［82］KLINKENBERG R, RENZ I. Adaptive information filtering: learning in the presence of concept drifts［C］// Proceedings of the Workshop of the AAAI-98/ICML-98 on Learning for Text Categorization. Madison, USA, 1998: 33-40.
［83］LAST M. Online classification of nonstationary data streams ［J］. Intelligent Data Analysis, 2002, 6 (2): 1-16.
［84］GAMA J, MEDAS P, CASTILLO G, et al. Learning with drift detection［C］//Proceedings of the 17th Brazilian Symposium on Artificial Intelligence. Sao Luís, Brazil, 2004: 286-295.
［85］NISHIDA K, YAMAUCHI K. Detecting concept drift using statistical testing［C］//Proceedings of the 10th International Conference on Discovery Science. Sendai, Japan, 2007: 264-269.
［86］罗秀, 王大玲, 冯时, 等. 一种面向周期性概念漂移的数据流分类算法［J］. 计算机研究与发展, 2009, 46(Suppl): 400-405. LUO Xiu, WANG Daling, FENG Shi, et al. An algorithm for classifying data stream with recurrent concept drift［J］. Journal of Computer Research and Development, 2009, 46(Suppl.): 400-405. 
［87］KATAKIS I, TSOUMAKAS G, VLAHAVAS I. Tracking recurring contexts using ensemble classifiers: an application to email filtering［J］. Knowledge and Information Systems, 2010, 22(3): 371-391.
［88］ALIPPI C, ROVERI M. Just-in-time adaptive classifiers—part I: detecting nonstationary changes［J］. IEEE Transactions on Neural Networks, 2008, 19(7): 1145-1153.
［89］ALIPPI C, ROVERI M. Just-in-time adaptive classifiers—part II: designing the classifier［J］. IEEE Transactions on Neural Networks, 2008, 19(12): 2053-2064.
［90］ALIPPI C, BORACCHI G, ROVERI M. An effective just-in-time adaptive classifier for gradual concept drifts［C］//Proceedings of the 2011 International Joint Conference on Neural Networks. San Jose, USA, 2011: 1675-1681.
［91］PETER V，ABRANHAM B. Entropy-based concept drift detection［C］//Proceedings of the 6th International Conference on Data Mining. Hong Kong, China, 2006: 1113-1118.
［92］KUNCHEVA L. Change detection in streaming multivariate data using likelihood detectors［J］. IEEE Transactions on Knowledge and Data Engineering, 2007, 6(1): 1-7.
［93］KUBAT M. To load balancing in computer networks［J］. International Journal of Cybernetics and System, 1992, 23(3/4): 389-400.
［94］COHEN L, AVRAHAMI-BAKISH G, LAST M, et al. Real-time data mining of non-stationary data streams from sensor networks［J］. Information Fusion, 2008, 9(3): 344-353.
［95］HARRIES M, HORN K. Detecting concept drift in financial time series prediction using symbolic machine learning［C］//Proceedings of the Eighth Australian Joint Conference on Artificial Intelligence. Canberra, Australia, 1995: 91-98.
［96］MOVELLAN J R, MINEIRO P. Robust sensor fusion: analysis and application to audio visual speech recognition［J］. Machine Learning, 1998, 32(2): 85-100.
［97］BERNSTEIN A, VORBURGER P, EGGER P. A scenario-based approach for direct interruptability prediction on wearable devices［J］. International Journal of Pervasive Computing and Communications, 2008, 3(4): 426-438.
Similar References:

Memo

-

Last Update: 2013-05-26

Copyright © CAAI Transactions on Intelligent Systems