Research on Dynamic Data Stream Classification Algorithm with New Class

doi:10.3778/j.issn.1673-9418.1909021

Abstract

Abstract:

Aiming at the low performance in detecting new class of classification algorithm on dynamic data stream with new class, a completely randomized forest algorithm based on k-nearest neighbor (KCRForest) is proposed. The algorithm constructs completely randomized trees of completely randomized forest by only known-class sam-ples in dynamic data stream, and divides the sample space into normal or abnormal region according to the average path length of leaf nodes. The outlier of a sample is obtained based on its k-nearest neighbor, when the sample falls into abnormal region. If the outlier is greater than the set threshold, the sample is judged to be new-class. Otherwise it is judged to be known-class. When the known-class sample falls into abnormal region, class distribution is obtai-ned based on its k-nearest neighbor. Otherwise class distribution can be obtained during training period. The label of known-class sample is identified by voting. When a certain number of new class samples are detected, the model is updated by the new-class sample information to detect other new classes. In order to verify the effectiveness of KCRForest algorithm in detecting new classes, experiments are carried out on 4 UCI datasets respectively, and comparisons are made with existing algorithms. The results show that the proposed method is equivalent to or better than iForest+SVM and LOF+SVM on new-class detection, and its classification accuracy is better than SENCForest.

Key words: new-class detection, completely randomized forest, dynamic data stream

摘要：

针对有新类的动态数据流分类算法检测新类性能不高的问题，提出一种基于k近邻的完全随机森林算法（KCRForest）。该算法利用动态数据流中已知类样本构建完全随机森林的完全随机树，并根据叶节点平均路径长度将样本空间分成正常区域与异常区域。通过落入异常区域中样本的k近邻计算该样本离群值。若样本离群值大于设定阈值，则判断样本为新类，否则为已知类。落入异常区域的已知类样本由该样本的k近邻得到样本标签分布，否则取该区域中原训练样本标签分布，投票得到样本标签。当新类样本检测达到一定数量时，利用新类样本信息更新模型，便于检测其他新类。为了验证KCRForest算法检测新类的有效性，分别在4个UCI数据集上进行实验，并与已有算法进行比较。结果表明该算法的新类检测性能优于或与iForest+SVM算法、LOF+SVM算法相当，分类准确率明显高于SENCForest算法。

关键词: 新类检测, 完全随机森林, 动态数据流

WU Weijie, ZHANG Jingxiang. Research on Dynamic Data Stream Classification Algorithm with New Class[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(1): 132-140.

武炜杰, 张景祥. 有新类的动态数据流分类算法研究[J]. 计算机科学与探索, 2021, 15(1): 132-140.

References

[1] LACHHAB F, BAKHOUYA M, OULADSINE R, et al. A con-text-driven platform using Internet of things and data stream processing for heating, ventilation and air conditioning systems control[J]. Journal of Systems and Control Engineering, 2019, 233(7): 877-888.
[2] NAZIR H M, HUSSAIN I, AHMAD I, et al. An improved framework to predict river flow time series data[J]. Env-ironmental Science, 2019, 7(7): e7183.
[3] QIDWAI U, CHAUDHRY J,?JABBAR S, et al. Using casual reasoning for anomaly detection among ECG live data stre-ams in ubiquitous healthcare monitoring systems[J]. Journal of Ambient Intelligence and Humanized Computing, 2019, 10(10): 4085-4097.
[4] XU G Y, HAN M, WANG S F, et al. Summarization of data stream ensemble classification algorithm[J]. Application Research of Computers, 2020, 37(1): 1-8.
许冠英, 韩萌, 王少峰, 等. 数据流集成分类算法综述[J]. 计算机应用研究, 2020, 37(1): 1-8.
[5] ZHANG B F, SU J S, XU X. A class-incremental learning method for multi-class support vector machines in text class-ification[C]//Proceedings of the 2006 International Confere-nce on Machine Learning and Cybernetics, Dalian, Aug 13-16, 2006. Piscataway: IEEE, 2006: 2581-2585.
[6] DA Q, YU Y, ZHOU Z H. Learning with augmented class by exploiting unlabeled data[C]//Proceedings of the 28th AAAI Conference on Artificial Intelligence, Québec City, Jul 27-31, 2014. Menlo Park: AAAI, 2014: 1760-1766.
[7] MASUD M 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.
[8] AL-KHATEEB T, MASUD M M, KHAN L, et al. Stream classification with recurring and novel class detection using classbased ensemble[C]//Proceedings of the 12th IEEE Inter-national Conference on Data Mining, Brussels, Dec 10-13, 2012. Washington: IEEE Computer Society, 2012: 31-40.
[9] HAQUE A, KHAN L, BARON M. Semi supervised adap-tive framework for classifying evolving data stream[C]//LNCS 9078: Proceedings of the 19th Pacific-Asia Conference on Ad-vances in Knowledge Discovery and Data Mining, Ho Chi Minh City, May 19-22, 2015. Berlin, Heidelberg: Springer, 2015: 383-394.
[10] HAWKINS D M. Identification of outlier[M]. Berlin, Heidel-berg: Springer, 1980.
[11] ZHANG Y, CHEN J, WANG X F, et al. Application of ran-dom forest on rolling element bearings fault diagnosis[J]. Journal of Computer Engineering and Applications, 2018, 54(6): 100-104.
张钰, 陈珺, 王晓峰, 等. 随机森林在滚动轴承故障诊断中的应用[J]. 计算机工程与应用,?2018,?54(6):?100-104.
[12] XU O Y, LI G H. Anomaly data detection using glowworm optimization and random forest in wireless sensor networks[J]. Journal of Computer Science and Technology, 2018, 12(10): 1633-1644.
许欧阳，李光辉. 萤火虫优化和随机森林的WSN异常数据检测[J]. 计算机科学与探索, 2018, 12(10): 1633-1644.
[13] ZHAO Q H, ZHANG Y H, MA J F, et al. Research on cla-ssification algorithm of imbalanced datasets based on im-proved SMOTE[J]. Computer Engineering and Applications, 2018, 54(18): 168-173.
赵清华, 张艺豪, 马建芬, 等. 改进SMOTE的非平衡数据集分类算法研究[J]. 计算机工程与应用,?2018,?54(18):?168-173.
[14] LIU F T, TING K M, ZHOU Z H. Isolation-based anomaly det-ection[J]. ACM Transcations on Knowledge Discovery from Data, 2012, 6(1): 1-39.
[15] MU X, TING K M, ZHOU Z H. Classification under strea-ming emerging new classes: a solution using completely-random trees[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 8(1): 1605-1618.
[16] BREUNIG M M, KRIEGAEL H, NG R T, et al. LOF: identifying density-based local outliers[C]//Proceedings of the 2000 ACM SIGMOD International Conference on Manag-ement of Data, Dallas, May 16-18, 2000. New York: ACM, 2000: 93-104.
[17] CHANG C C, LIN C J. LIBSVM: a library for support vec-tor machines[J]. ACM Transactions on Intelligent Systems and Technology, 2011, 2(3): 27.
[18] HAN J W, KAMBER M. Data mining: concepts and tech-niques[M]. 3rd ed. Beijing: China Machine Press, 2012.
HAN J W, KAMBER M. 数据挖掘: 概念与技术[M]. 范明, 孟小峰, 译. 3版. 北京: 机械工业出版社, 2012.