一种基于数据不确定性的概念漂移数据流分类算法

doi:10.3969/j.issn.0255-8297.2017.05.003

Abstract

Abstract:

Data in the Web have much uncertainty because of privacy protection, data loss, network errors, etc. In a data stream system, data arrive continuously and therefore one cannot obtain all data in any time. In addition, the concept drift often occurs in the data stream. This paper constructs an incremental classifcation model to deal with data stream classifcation with data uncertainty and concept drift. In this model, a fast decision tree algorithm is used. It can analyze uncertain information quickly and effectively both in the learning stage and the classifcation stage. In the learning stage, it uses the Hoeffding bound theory to quickly construct a decision tree model for the data stream with data uncertainty. In the classifcation stage, it uses a weighted Bayes classifer in the tree leaves to improve precision of the classifcation. The use of a sliding window to replace the tree ensures that the algorithm can deal with concept drift. Experimental results show that the algorithm has good classifcation accuracy and execution efciency both on artifcial and real data.

Key words: concept drift, classifcation, data stream, data uncertainty, decision tree

CLC Number:

TP311

LÜ Yan-xia, WANG Cui-rong, WANG Cong, YUAN Ying. Data Stream Classifcation with Data Uncertainty and Concept Drift[J]. Journal of Applied Sciences, 2017, 35(5): 559-569.

References

[1] Tsang S, Kao B, Yip K Y, Ho W S, Lee S D. Decision trees for uncertain data[J]. IEEE Transactions on Knowledge & Data Engineering, 2009, 231:64-78.
[2] Hulten G, Spencer L, Domingos P. Mining time-changing data streams[J]. ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2001:220-224.
[3] Charu C A, Philip S Y. A survey of uncertain data algorithms and applications[J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21:609-623.
[4] Ding X, Lian X, Chen L, Jin H. Continuous monitoring of skylines over uncertain data streams[J]. Information Sciences, 2012:196-214.
[5] Gao C, Wang J. Direct mining of discriminative patterns for classifying uncertain data[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2010:861-870.
[6] Cao K Y, Wang G, Han D. An algorithm for classifcation over uncertain data based on extreme learning machine[J]. Neurocomputing, 2016, 174:194-202.
[7] Qin B, Xia Y, Wang S, Du X. A novel Bayesian classifcation for uncertain data[J]. Knowledge-Based System, 2011, 24:1151-1158.
[8] Liu J, Li X, Zhong W. Ambiguous decision trees for mining concept-drifting data streams[J]. Pattern Recognition Letters, 2009:1347-1355.
[9] Ahmadi Z, Kramer S. Prototype-based learning on concept-drifting data streams[J]. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2014:412-421.
[10] Sidhu P, Bhatia M P S. A novel online ensemble approach to handle concept drifting data streams-diversifed dynamic weighted majority[J]. International Journal of Machine Learning & Cybernetics, 2015:1-25.
[11] Liu S, Sun Z, Liu T. Research of incremental data stream classifcation based on sample uncertainty[J]. Journal of Chinese Computer Systems, 2015:193-196.
[12] Liang C, Zhang Y, Shi P, Hu Z. Learning accurate very fast decision trees from uncertain data streams[J]. International Journal of Systems Science, 2014:1-19.
[13] Lü Y, Wang C R, Wang C, Yuan Y. Online classifcation algorithm for uncertain data stream in big data[J]. Journal of Northeastern University (Natural Science), 2016, 37(9):1245-1249.
[14] Hoeffding W. Probability inequalities for sums of bounded random variables[J]. Journal of the American Statistical Association, 1962:13-30.
[15] Qin B, Xia Y, Li F. Dtu:a decision tree for uncertain data[J]. Lecture Notes in Computer Science, 2009:4-15.
[16] He J, Zhang Y, Shi X L P. Learning naive Bayes classifers from positive and unlabelled examples with uncertainty[J]. International Journal of Systems Science, 2012:1805-1825.
[17] West D H D. Updating mean and variance estimates:an improved method[J]. Communication of ACM, 1979:532-535.

Data Stream Classifcation with Data Uncertainty and Concept Drift

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	SUN Zhongjun, ZHAI Jiangtao, DAI Yuewei. An Encrypted Traffic Identification Method Based on DPI and Load Randomness [J]. Journal of Applied Sciences, 2019, 37(5): 711-720.
[2]	WANG Jingwei, WU Shaohua, QU Zhiguo. CFMoment: Closed Frequent Itemsets Mining Based on Data Stream [J]. Journal of Applied Sciences, 2019, 37(3): 389-397.
[3]	OUYANG Zhiyou, CHEN Chen, WANG Yuqian, CHEN Jingang, YIN Zhao, ZHOU Qingsong. Protein Small Molecule Affinity Prediction Based on Natural Language Processing [J]. Journal of Applied Sciences, 2019, 37(3): 327-335.
[4]	SONG Hai-feng, CHEN Guang-sheng, JING Wei-peng, YANG Wei-wei. Restricted Boltzmann Machine Algorithm for Image Classifcation and Its Parallel Implementation Based on (2D)² PCA [J]. Journal of Applied Sciences, 2018, 36(3): 495-503.
[5]	LIU Xiao-kai, YAO Heng, QIN Chuan. Improved Reversible Image Camouflage Method Based on Image Block Classifcation Threshold Optimization [J]. Journal of Applied Sciences, 2018, 36(2): 237-246.
[6]	FANG Zhi-jian, FU Yang-geng, CHEN Jian-hua. Belief Rule Base Inference for Texture Image Classifcation [J]. Journal of Applied Sciences, 2017, 35(5): 545-558.
[7]	WU Zhao-cong, LIU Pei, WU Yuan. Synthesis of Requirements in Applications of Multi-spectral Remote Sensing [J]. Journal of Applied Sciences, 2017, 35(5): 658-666.
[8]	WANG Peng, NI Cui, ZHANG Guang-yuan, LI Ke-feng. Improvement for R-Lambda Rate Control Model [J]. Journal of Applied Sciences, 2017, 35(3): 355-365.
[9]	LIU San-min, LIU Tao, WANG Zhong-qun, XIU Yu, LIU Yu-xia, MENG Chao. Data Stream Ensemble Classification Based on Classifier Confidence [J]. Journal of Applied Sciences, 2017, 35(2): 226-232.
[10]	ZHU Xiao-dong;HUANG Zhi-qiu;CHEN Sheng-qing;HUANG Feng;SHEN Guo-hua. Algorithm Management Framework for Data Stream Mining [J]. Journal of Applied Sciences, 2008, 26(1): 61-61 .
[11]	WANG Jin-dong, ZHOU Liang, ZHANG Lei, DING Qiu-lin. Load Shedding for Continuous Query Based on Sub-path Analysis [J]. Journal of Applied Sciences, 2007, 25(1): 63-68.
[12]	LIU Xue-jun, XU Hong-bing, DONG Yi-sheng, QIAN Jiang-bo, WANG Yong-li. Online Detection of Data Stream Changes Based on Maximum Frequent Itemset Entropy [J]. Journal of Applied Sciences, 2006, 24(5): 498-502.
[13]	WANG Jin-dong, ZHANG Lei, DING Qiu-lin, HUANG Tian-qiang. A Two-Tier Overlay Network Model for Distributed Data Stream Processing [J]. Journal of Applied Sciences, 2006, 24(4): 387-390.
[14]	WANG Yong-li, XU Hong-bing, DONG Yi-sheng, QIAN Jiang-bo, LIU Xue-jun. Detection and Repairing Method for Outliers over Data Streams [J]. Journal of Applied Sciences, 2006, 24(3): 256-261.
[15]	WANG Jin-dong, ZHOU Liang, ZHANG Lei, DING Qiu-lin. A Scalable Load-Balancing Algorithm for Distributed Data Stream Management Systems [J]. Journal of Applied Sciences, 2006, 24(3): 250-255.