基于Mahalanobis距离的凝聚力和分离指数的概念漂移数据流分类和新型类检测算法

摘要

数据流挖掘已成为数据挖掘的研究热点，并引起了许多学者的注意。然而，传统的数据流挖掘技术仍然有一些问题在处理概念漂移和概念演变中仍有一些问题。为了缓解概念漂移和概念演化对新型类检测和分类的影响，提出了一种基于Mahalanobis距离的凝聚力和分离指数的分类和新型类检测算法。实验结果表明，该算法可以有效地减轻概念漂移对分类和新类检测的影响。

1.介绍

近年来，随着互联网的持续推广和事物互联网和数据采集技术的不断发展，数据已爆炸。互联网，金融，医学和生态监测中出现了不断变化的时间戳数据模型。在互联网和无线通信网络的出现之后，作为一种新型数据模型的数据流引起了社会的越来越关注[1，2］．数据流具有与传统数据集不同的特征。它具有时间顺序，快速变化和大规模的，潜在的无限等特征。正是由于数据流的独特特征，即数据流的数据处理模型与传统的数据挖掘技术非常不同。由传统的数据挖掘技术处理的数据是静态数据集，其可以永久存储在介质中，并且可以在数据分析过程中扫描和使用多次。与传统的静态数据库不同，数据流的数据处理模型以更快的速率更新，并不断流入计算机系统。因此，从数据流处理数据中的两个最大挑战是其固有的无限长度和实时数据变化中发生的概念漂移。概念漂移意味着模型试图以不可预测的方式预测改变时间的目标变量的统计特性。因此，使用传统的数据挖掘技术，存储和使用所有历史数据进行培训是不切实际的，这使得有必要改变现有的数据挖掘技术和设计新数据模型的新挖掘算法。

数据流新类检测是在数据流中检测新类别的一种技术。许多传统的数据流分类算法使用固定的类数来训练数据流分类器。但在现实中，随着时间的推移，数据流中会出现异常值和新类，这将导致传统数据流分类算法的准确率逐渐下降。因此，针对数据流的特点，设计一种新的类检测算法迫在眉睫。

本文的其余部分组织如下2介绍了数据流分类和新型类检测的相关研究。部分3.详细介绍C&NCBM算法。部分4描述了不同数据集中的实验结果和详细分析。研究中的研究以及未来研究的挑战和方向介绍5．

2.相关工作

2.1。在概念漂移的存在下数据流分类

在文献中[3.[近年来概念漂移背景下的各种学习算法进行综述。1986年，斯基拉姆和格兰杰[4]首先提出了“概念漂移”，随后引起了学术界越来越多的关注。从1986年到2000年，研究主要集中在使用单一分类器实现概念漂移数据流分类。Widmer和Kubat提出CBBIT [5， Hulten等人提出了FLORA [6］．与此同时，研究者开始关注概念漂移数据流分类的理论问题。

由于使用单一分类器处理概念漂移数据流时需要不断更新分类模型，且分类器的泛化能力不高[7]，黑色和黑威[8第一次提出并提出了AES算法的概念漂移数据流分类的综合学习。因此，大约2000年后，人们开始转向综合分类器，以便研究概念漂移数据流。此时，概念漂移数据流分类研究进入了快速发展的时期，开始研究近距离现实的概念漂移数据流。Klinkenberg和Lanquillon早些时候在某些情况下研究了概念漂移，用户反馈或没有反馈[8- - - - - -11］．2004年，《智能数据分析杂志》发表了概念漂移数据流专刊[12，主要讨论了如何使用增量学习方法使现有分类器以较小的代价使用概念漂移。随后，越来越多的人开始关注班级学习不平衡等问题[13，14，概念重复学习[15，16]，半体育学习[17，18]，积极学习[19，20.]在概念漂移数据流的分类中。桌子1总结了2000 - 2016年主要的三类概念漂移数据流分类技术。

２.２.存在概念漂移的新型类检测

在文献中[33]， Masud等人提出了一种新的概念漂移和无限长数据流中的类检测方法。然而，该方法并没有解决特征演化的问题。在文献中[34]，解决概念的演变问题，同时解决了概念演化的问题，但文献[33，34对于某些数据集仍然具有太高的误报率，无法区分不同的新型类别问题。Masud等人。［35]提出了一种方法来解决由于新类的出现而引起的概念演变。此方法将辅助分类器集添加到主分类器集。当数据流中的每个到达实例被主分类器集和关联分类器集确定为次级离群值时，它被临时存储在缓冲区中。当缓冲区中有足够的实例时，将调用新的类检测模块进行检测。如果发现一个新类，则相应地标记新类实例。在文献中[36]，提出了特征空间变换技术来处理数据流特征的演化。将传统的数据流集成分类器与新型的类检测技术相结合，解决了数据流中的特征演化问题。

Chandak [37]提出了一种基于字符串的数据流处理方法，主要通过CON_EVOLUTION算法解决数据流概念演化问题。Miao等人[38解决了在Mineclass算法的框架中只能解决数值数据的问题。提出了一种可以处理混合属性数据的新型类检测算法，并且通过使用VFDTC分类器优化算法框架的处理时间和模型大小。Zaremoodi等。［39]使用局部模式和邻近图来解决数据流中的概念演化问题。局部模式是影响序列特征和分类特征的布尔特征组，用来提高分类精度。同时，在候选的新类类中，利用近邻图分析相关对象，提高了新类检测的准确性。

在许多研究人员持续探索它之后，新型类检测已经取得了许多结果。然而，大多数新颖的类算法同时无法解决多个新颖类问题的问题，并且在实例中不考虑不同属性的交互来确定新颖类。因此，基于先前的研究并考虑到属性的作用，本文提出了一种新型类检测算法，可以区分不同类别的新型类。

3.基于Mahalanobis距离的分类和新型类检测算法（C＆NCBM）

３.１.基于马氏距离的内聚和分离指数

基于马氏距离[40[Masud等人提出的粘性分离指数N-NSC。［33，提出了一种新的类检测指标。相关定义如下。

定义1。(R-outlier)(见[33])。让x是测试点和是最接近的聚类结果点x．如果x是否在包含的特征空间所决定的范围之外 ，然后x是一个R-outlier。

定义2。(F-outlier)(见[33])。如果x是所有分类器的r异常值吗在分类集中 ，然后x是一个F-outlier。

定义3。（ -邻居）（见[33])。这 -F-viellier的邻居x是一套n最接近的邻居x在课堂上 ，用符号表示的 ，在哪里n是用户设置的参数。
根据上述定义，我们给出了基于马氏距离的内聚性和分离指数MN-NSC的定义。

定义4。(MN-NSC)。让是F-viellier的平均mahalanobis距离来 ， 是F-viellier的平均mahalanobis距离x来 ，和的最小值 ；然后MN-NSC定义如下： 在哪里代表了 -的邻居其他f异常值和代表了 -的邻居到它现有的类。
根据定义，MN-NSC的取值范围为[−1,1]。MN-NSC为负时，表示x更接近现有的类，远离f离群值;当MN-NSC为阳性时，意味着x离现有的类更远，接近于f异常值。当至少N（>n) f -离群值MN-NSC值大于0，表示数据流中产生了新的异构。

3.2。算法

本节将详细阐述基于马氏距离内聚分离指标的分类算法过程和新型类检测算法，并分析数据流中的概念漂移处理。

首先，将数据流分成大小相同的数据块和最后到达的数据块 ，当前最优分类器集 ，最近的邻居 ，和新的班级门槛被视为算法的输入。然后，分类数据块中的实例以确定实例是r-vistier。如果实例是r-vistier，则它将添加到异常集中 ． -方法用于群集集合中的实例并创建一个聚集点对于每个集群。这保存每个群集的群集中心和群集半径，并计算每个簇点的MN-NSC值 ．当MN-NSC值大于零的聚类点个数大于设置的阈值时，算法判定生成了新的类，并对其进行分类。当所有数据输入是显著的,用于训练一个新模型 ． ，从集合中选择具有最低分类精度的模型,取而代之的是 ．通过上述方法，可以随时维护当前最新概念的分类模型，从而解决数据流中的概念漂移问题(算法)1)．算法的伪代码如下所示。

4.实验和分析

为了验证本文提出的基于马氏距离内聚分离指标的分类算法和新的类检测算法，在两个真实数据集和一个合成数据集上进行了三组实验。然而,(K-最近的邻居） [41选择作为C＆NCBM算法的总数据流分类器，以确认实例的最终预测类别。本文提出的算法的本质基于KNN。为了验证算法的有效性，使用KNN分类数据流和Mineclass的算法[33] Masud等人提出的算法。选择用于比较实验。

4.1。实验数据集

选择KDD Cup 1999，CoverType和Africycds数据集作为实验数据集。表中显示了每个数据集的类别数，维度数量和数据集样本的总数2．

以下4.4.1。数据集

（http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html)．KDD Cup 1999 DataSet是ACM在1999年年度竞争中使用的数据集。数据集由共有494,021个数据样本组成，每个数据示例包含42个属性。本文使用10％版本的KDD Cup数据集。

4.1.2。CoverType DataSet.

（http://archive.ics.uci.edu/ml/datasets/covertype.)．Covertype数据集是美国林务局(USFS)地区2的资源信息系统(RIS)数据。数据集包含总共581,012个实例的7种类型，每个实例的属性维度为54。

4.1.3。artycipds dataset.

（https://moa.cms.waikato.ac.nz/)．人工cds数据集是由MOA自动生成的随机概念漂移数据流。数据流包含5个类，总共有100,000个实例，每个示例的属性维度是27。

4．2.性能指标

4.2.1。分类准确性

该实验使用精度[42]评估时间[33]来评价不同算法的质量，是分类算法领域广泛使用的评价标准。我们期望一种好的分类算法能在保证较高的分类精度的同时满足较短的评价时间。

4.2.2。kappa统计信息

Kappa统计(43]是评估分类准确性的指标。 在哪里是分类器一致的比例，即每个正确分类的样本总数除以样本总数，和为随机分类协议的比例。

4.3。实验结果与分析

本节单独进行比较和验证所提出的算法分类性能和算法对概念漂移的影响，给出结果分析。

4.3.1。实验1

根据上述实验目标，我们选择了COTEDTYPE，KDD杯1999和Arifalcds数据集作为实验数据集，并将C＆NCBM，Mineclass和KNN的分类精度和评估时间进行了比较在上述三个数据集中。在该实验中，不同数据集的算法参数的特定值如表所示3.．三个数据集上的实验结果如表所示4- - - - - -6．

从表中的实验结果可以看出4- - - - - -6即，在整个数据流分类过程中，与其他两个算法相比，C＆NCBM的分类精度在整个实验中非常稳定，并且显着高于其他两个。算法Mineclass还具有比单独使用KNN的更好的分类效果。C＆NCBM的评估时间显着长于其他两个算法的时间，并且单独使用KNN的评估时间与单独使用KNN的时间差。C＆NCBM的准确性高于Mineclass，但它也需要更多的评估时间。

三组实验在两个真实数据集和一个人工数据集上的结果表明，本文提出的算法用于处理与概念漂移和新型类的数据流分类，具有以下特征。（1）当新颖类出现在概念漂移数据流中时，能够及时判断，并在制造它之后自适应地更新原始模型，这对概念漂移数据流中具有更强的分类稳健性。（2）与使用普通分类器相比，分类准确性有显着提高，与分类和新型类检测算法相比，分类精度得到了一定程度的改进，并在一定程度上得到了改善和新的类检测算法[33基于欧几里得距离。(3)计算时间比其他算法略长。

4.3.2。实验2

数据流中概念漂移的出现表明属性和类别之间的映射关系发生了变化，数据流上的分类器就是基于这种映射关系的。当属性到类别的映射关系发生变化时，分类器的分类精度指标Kappa Statistic不可避免地会发生显著变化。因此，在本节中，我们将利用分类器分类精度的差异来确定不同算法对概念漂移的敏感性。

我们选择了CoverType和Articalcds数据集作为实验数据集，并分别比较了C＆NCBM，Mineclass和Knn分类精度指数Kappa统计信息。数据集上的比较结果如图所示1．

为了介绍概念漂移，我们重新排列了CoverType数据集，以便最多如图3所示，至少2个类别同时出现在任何块中，并且新类别随机出现。布置的CoverType数据集的概念漂移主要在块3和5中。MoA自动生成的Agerycds数据集是增量漂移，主要出现在块4和6中。图的结果1表明，由于缺乏概念漂移处理机制，KNN具有分类准确性指数kappa统计的最快下降。Mineclass部分受到影响，但减少小于KNN。C＆NCBM受概念漂移的影响最小，分类精度曲线是最渐进的。当在数据流中发生概念漂移时，所有三种算法都将受到一定程度的影响。本文提出的C＆NCBM算法具有更好的概念漂移适应性，可以在一定程度上降低概念漂移对分类的影响。

结论

本文提出了一种基于马氏距离内聚分离指标的MN-NSC模型。在此基础上，提出了一种新的基于马氏距离的分类和类检测算法C&NCBM。与传统的用欧几里得距离测量实例间距离不同，该方法更注重实例间的相似性，能够敏感地检测离群点之间的微小变化。通过KNN算法和MineClass算法的对比实验，验证了分类算法的有效性。比较了C&NCBM算法、KNN算法和MineClass算法的分类精度Kappa Statistic。结果表明，所提出的C&NCBM算法是最优的。漂移适应性概念可以在一定程度上处理数据流中概念漂移对分类的影响。但是，由于添加马氏距离的问题，本文提出的算法相对于其他算法需要稍长的时间。如何在保证算法分类有效性的同时提高计算时间是本文未来的研究方向。

数据可用性

用于支持本研究结果的数据包括在文章中。

利益冲突

作者声明他们没有利益冲突。

致谢

这项工作由中国国家自然科学基金资助（61862042和61762062,61601215）;江西省科技创新平台项目（第20181BCD40005）;江西省主要纪律学术学术和技术领导计划项目（20172BCB22030）;江西省初级研究与发展计划（第20192Bbe50075,20181ACE50033,20171BBE50064,2013ZBBE50018）;江西省自然科学基金（20192BAB207019和20192BAB207020）;江西省毕业生创新基金项目（NOS。YC2019-S100和YC2019-S048）。

参考

1. U. R. Salunkhe和S. N.Mali，“使用分类器合并的入侵检测系统中的安全富集”，“电子与计算机工程学报， vol. 2017，文章编号1794849,6页，2017。查看在：出版商的网站|谷歌学术
2. “基于KNN分类算法的无线传感器网络入侵检测系统研究”，电子与计算机工程学报，卷。2014年，第24021717号，8页，2014年。查看在：出版商的网站|谷歌学术
3. 卢建军，刘安，董峰，顾峰，J. Gama，张光，“概念漂移下的学习研究”，IEEE知识与数据工程汇刊，卷。31，不。12，pp。2346-2363,2018。查看在：出版商的网站|谷歌学术
4. J. C. Schlimmer和R. H. Granger，《从嘈杂数据中增量学习》，机器学习，卷。1，不。3，pp。317-354,1986。查看在：出版商的网站|谷歌学术
5. G. Widmer和M. Kubat，“通过显式上下文跟踪，”在动态环境中有效地学习“第六届欧洲机器学习会议的诉讼程序，第69-101页，奥地利维也纳，1993年。查看在：谷歌学术
6. G. Hulten，L. Spencer和P. Domingos，“采矿时间改变数据流”第七届ACM SIGKDD知识发现和数据挖掘国际会议论文集- kdd ' 01，pp。97-106，旧金山，加利福尼亚州，2001年。查看在：出版商的网站|谷歌学术
7. Y. Wen，B. Qiang和Z.Fan，“具有概念漂移的数据流分类的调查”智能系统学报第46卷，第46期11, pp. 2656-2665, 2013。查看在：谷歌学术
8. M. Black和R. J. Hickey，“维护概念漂移下学习分类器的表现，”智能数据分析，第3卷，第2期。6，第453-474页，1999。查看在：出版商的网站|谷歌学术
9. W. Nick Street和Y.Kim，“媒体集合算法（海）用于大规模分类”第七届ACM SIGKDD知识发现和数据挖掘国际会议论文集- kdd ' 01，第377-382页，旧金山，加利福尼亚，美国，2001。查看在：出版商的网站|谷歌学术
10. R. Klinkenberg，“使用标记和未标记的数据来学习漂移概念”IJCAI-1时间和空间数据学习讲习班讲习班说明汇编，第16-24页，门洛帕克，加州，美国，2001。查看在：谷歌学术
11. R. Klinkenberg和T. Joachims，“基于支持向量机的检测概念漂移”第十七届国际机器学习会议论文集，pp.487-494，斯坦福，加州，美国，2000。查看在：谷歌学术
12. C. Lanquillon，“变化域中的信息过滤”第16届国际人工智能联合会议论文集，第41-48页，瑞典斯德哥尔摩，1999年。查看在：谷歌学术
13. M. Kubat, J. Gama，和P. Utgoff，“能够处理概念漂移的增量学习系统特刊”，智能数据分析，第8卷，第2期3, 2004。查看在：出版商的网站|谷歌学术
14. H. He和S. Chen，“非平稳不平衡数据流的增量学习:多重选择性递归方法”，进化系统，卷。2，不。1，pp。35-50,2011。查看在：出版商的网站|谷歌学术
15. S. Ramamurthy和R.Bhatnagar，“跟踪反复概念使用集合分类器的流数据漂移，”第六届机器学习和申请国际会议的诉讼程序， pp. 404-409，辛辛那提，俄亥俄州，美国，2007。查看在：谷歌学术
16. P. Li，X. Wu和X. Hu，“挖掘重复概念与有限标记的流数据漂移，”第2届机器学习会议的诉讼程序，PP。241-252，东京，日本，2010年。查看在：谷歌学术
17. J. C. Xue和G. M.Weiss，“用于处理阶级分布变化的量化和半监督分类方法”ACM SIGKDD国际知识发现和数据挖掘会议论文集，第897-905页，法国巴黎，2009。查看在：谷歌学术
18. p. li，x. wu和x. hu，“从概念漂移数据流中学习与未标记的数据，”第24届AAAI人工智能会议论文集，第1945-1946页，美国佐治亚州亚特兰大，2010。查看在：谷歌学术
19. I.ž.tavail，a。bifet，b. pfahringer和g. holmes，“与不断发展的流媒体数据一起学习”机器学习与数据库知识发现原理与实践欧洲会议论文集，第597-612页，希腊雅典，2011年。查看在：谷歌学术
20. L. nan，“概念漂移数据流分类算法及其应用，”福建师范大学，福州，福建，2013，硕士论文。查看在：谷歌学术
21. P. Domingos和G. Hulten，“挖掘高速数据流”，在第六届ACM SIGKDD国际知识发现国际会议和数据挖掘 - KDD'00，第71-80页，ACM，波士顿，马，美国，2000。查看在：出版商的网站|谷歌学术
22. A. Bifet和R. Gavaldà，“从进化的数据流中进行自适应学习”智能数据分析进展8亚当斯(n.m. Adams)、罗巴代(C. Robardet)、西贝斯(A. Siebes)和j - f。Boulicaut, Eds。，pp. 249–260, Springer Berlin Heidelberg, Berlin, Germany, 2009.查看在：谷歌学术
23. S. R. Kumari和P. Kumari，“使用优化Hoeffding树的自适应异常入侵检测系统”，工程与应用科学学报第95卷第1期17, pp. 22-26, 2014。查看在：谷歌学术
24. 冯丽峰，“一种改进的Hoeffding-ID数据流分类算法”，超级计算杂志，卷。72，没有。7，pp。2670-2681,2016。查看在：出版商的网站|谷歌学术
25. C. C. Aggarwal，P. S. Yu，J. Han和J. Wang，“群体演化数据流”的框架“第29届超大数据库国际会议论文集-第29卷，第81-92页，VLDB基金会，柏林，德国，2003年9月。查看在：出版商的网站|谷歌学术
26. F.Cao，M. Ester，W.Qian和A.周，基于密度的聚类，在不断发展的数据流中，噪音“第六届暹罗国际数据挖掘国际会议的诉讼程序， pp. 328-339, Bethesda, MD, USA, 2006。查看在：出版商的网站|谷歌学术
27. a . Amini, H. Saboohi, T. Herawan, T. Y. Wah，《multi - density clustering algorithm for evolution data stream》，网络与计算机应用学报，卷。59，没有。1，pp。370-385,2016。查看在：出版商的网站|谷歌学术
28. “基于增量熵的概念漂移分类数据流聚类”，以知识为基础的系统，卷。59，没有。2，pp。33-47,2014。查看在：出版商的网站|谷歌学术
29. 杨振平，杨振平，杨伟，“基于集成分类器的多标签漂移数据流挖掘”第六届模糊系统与知识发现国际会议论文集，卷。5，PP。中国天津275-279，2009年。查看在：出版商的网站|谷歌学术
30. 张鹏，朱旭东，“基于鲁棒集成学习的噪声数据流挖掘”，决策支持系统，卷。50，不。2，pp。469-479，2011。查看在：出版商的网站|谷歌学术
31. D. M. Farid，L. Zhang，A. Hossain等，“用于挖掘概念漂移数据流的自适应合奏分类器”，专家系统与应用，第40卷，第5期。15, pp. 595 - 596, 2013。查看在：出版商的网站|谷歌学术
32. T.Al-Khateeb，M.M. Masud，K.M.Al-Naami等，“使用基于类的集合进行经常性和新的类检测，以便不断发展数据流”IEEE知识与数据工程汇刊第28卷第2期10, pp. 2752-2764, 2016。查看在：出版商的网站|谷歌学术
33. M. M. Masud, J. Gao, L. Khan, J. Han, and B. Thuraisingham，“将新的类检测与概念漂移数据流的分类集成”，在数据库中的机器学习和知识发现，第79-94页，施普林格柏林，海德堡，柏林，海德堡，2009。查看在：谷歌学术
34. M. M. Masud，Q. Chen，J.Gao，L. Khan，J. Han和B. Thuraisingham，“动态特征空间中数据流的分类和新类检测”数据库中的机器学习和知识发现，页337-352，施普林格柏林海德堡，柏林，海德堡，2010。查看在：谷歌学术
35. M. M. Masud, T. M. al - khateeb, L. Khan等人，“在概念漂移的数据流中检测重复的和新颖的类”2011年IEEE第11届数据挖掘国际会议论文集，pp.1176-1181，温哥华，BC，加拿大，2011年。查看在：谷歌学术
36. M. M. Masud，Q.陈，L.Khan等，“特征演化数据流的分类和自适应小组检测”，IEEE知识与数据工程汇刊，第25卷，第2期7, pp. 1484-1497, 2013。查看在：出版商的网站|谷歌学术
37. M. Chandak，“大数据在数据流分类和新型类检测中的作用”，大数据杂志，第3卷，第2期。1, pp. 1 - 9, 2016。查看在：出版商的网站|谷歌学术
38. Y.Miao，L.邱，H.陈，J. Zhang和Y. Wen，数据流分类中的小型课程检测，“神经网络国际研讨会的诉讼程序，第413-420页，施普林格，柏林，海德堡，德国，2013。查看在：谷歌学术
39. P. ZareMoodi, H. Beigy，和S. Kamali Siahroudi，“使用局部模式和邻域图的数据流的新类检测”，Neurocomputing，卷。158，pp。234-245,2015。查看在：出版商的网站|谷歌学术
40. P. C. Mahalanobis，《关于统计中的广义距离》国家科学研究院的诉讼程序1936年，印度加尔各答。查看在：谷歌学术
41. N. S. Altman，“内核和最近邻的非参数回归介绍”美国统计学家第46卷，第46期3，pp。175-185,1992。查看在：出版商的网站|谷歌学术
42. D. J. Hand和R. J. Till，“将ROC曲线下的面积简单概括为多类分类问题，”机器学习，卷。45，不。2，pp。171-186,2001。查看在：出版商的网站|谷歌学术
43. J.科恩，《标称尺度的一致系数》，教育与心理测量，卷。20，没有。1，pp。37-46,960。查看在：出版商的网站|谷歌学术

版权

版权所有©2020 Xiangjun Li等。这是分布下的开放式访问文章知识共享署名许可协议如果正确引用了原始工作，则允许在任何媒体中的不受限制使用，分发和再现。