概念漂移数据流挖掘算法综述

数据流是一种新型的数据模型,具有动态、无限、高维、有序、高速和变化等特性。在真实的数据流环境中,一些数据分布是随着时间改变的,即具有概念漂移特征,称为可变数据流或概念漂移数据流。因此处理数据流模型的方法需要处理时空约束和自适应调整概念变化。对概念漂移问题和概念漂移数据流分类、聚类和模式挖掘等内容进行综述。首先介绍概念漂移的类型和常用概念改变检测方法。为了解决概念漂移问题,数据流挖掘中常使用滑动窗口模型对新近事务进行处理。数据流分类常用的模型包括单分类模型和集成分类模型,常用的方法包括决策树、分类关联规则等。数据流聚类方式通常包括基于k- means的和非基于k- means的。模式挖掘可以为分类、聚类和关联规则等提供有用信息。概念漂移数据流中的模式包括频繁模式、序列模式、episode、模式树、模式图和高效用模式等。最后详细介绍其中的频繁模式挖掘算法和高效用模式挖掘算法。     

基于相对熵的数据流概念漂移检测算法

针对数据流中出现的概念漂移问题,采用决策树作为分类器,提出一种基于相对熵的数据流概念漂移检测算法。提出的算法将分类器的准确率与相对熵作为判断该数据块是否发生概念漂移的标准。通过5个数据集对该方法进行验证,该算法在其中4个数据集上都获得了最优的结果,在另一个数据集上获得了次优结果。实验结果表明采用该方法不仅能够有效地检测概念漂移的发生,而且还能提高分类器的准确率。     

分段加权的概念漂移检测方法

针对现有漂移检测方法无法平衡检测延迟、误报与漏报以及时空效率等问题，提出一个新的阶段转换阈值参数，在概念漂移检测中引入包含“稳定阶段-警告阶段-漂移阶段”的分段加权机制，对实例分阶段地赋予权重，并将该机制应用在双层滑动窗口中；然后基于Hoeffding不等式提出一种分段加权的概念漂移检测方法（MSDDM）。在人工数据集上，相较于FHDDM、HDDM等漂移检测方法，MSDDM能够更快地检测出突变与渐变概念漂移，同时又能保持较低的误检率与漏检率；在真实数据集上，MSDDM相较于其他方法在大部分情况下都具有最高的分类准确率。实验结果表明，MSDDM能够以较高的漂移检测性能和较优的时空效率检测出数据流中的概念漂移。     

基于先验简洁关联知识的故障诊断方法

在系统故障诊断优化问题的研究中,建立故障与故障表象之间的关系,对故障进行分析和预测是一种重要的故障检测手段.数据挖掘中的关联规则表达了事物间关系,在离散事件分析中具有分类和预测的功能.然而普通关联规则具有表达冗余量大和计算复杂的缺点,提出采用直接生成闭模式并生成的简洁关联规则的方法,挖掘并表达故障特征间的关联关系,并建立故障分析过程.在离散事件的分析系统中,改进方法相对于基于普通规则的处理方法,既减小了知识表达的空间,又提升了处理的效率.结果表明,提出的检测方法准确、有效,具有一定的实用性和推广价值.     

面向工业过程难测参数建模的双窗口概念漂移检测

针对工业过程数据固有概念漂移特性导致软测量模型性能恶化、需识别漂移样本以有效更新模型等问题,提出一种面向工业过程难测参数建模的双窗口概念漂移检测方法.首先,在离群样本检测窗口采用支持向量回归获得实时过程数据中包含的离群样本;接着,在分布检测窗口计算离群样本与历史样本集间的欧氏距离;最后,结合多种分布检验方法,新定义能够表征离群样本蕴含分布变化的检验漂移度指标,进而实现漂移样本的有效识别.采用合成和真实工业过程数据集验证了所提方法的有效性,表明具有优于已有方法的性能.     

基于量化相关模式的多值关联规则挖掘算法

为了解决多值关联规则挖掘中忽视罕见且有价值的非频繁模式的问题,提出了一种新的多值关联规则挖掘算法-QCoMine.该算法引入了量化相关模式的概念,通过考察多值属性间互信息熵和全置信度,找到具有强信息关系的属性集进而产生规则.实验结果表明,由于在属性层和区间层进行了剪枝,因此缩减了搜索空间,提高了算法的性能,且得到更高置信度、更有价值的规则.     

基于模糊逻辑和免疫遗传算法的入侵检测

随着网络入侵方法和网络计算环境的变化，使得入侵越来越难以被检测和防范。该文论述了通过使用模糊数据挖掘和免疫遗传算法，分别对正常行为模式和待检测行为模式建立关联、序列规则集，进而通过比较待检测行为模式的规则集与正常行为模式的规则集的相似度，确定是否有入侵事件发生。经过仿真测试，证明该方法可以有效地检测异常攻击事件。     

数据挖掘在异常入侵检测系统中的应用

在分析现有入侵检测技术和系统的基础上，本文提出了一种基于数据挖掘和可滑动窗口的异常检测模型，该模型综合利用了关联规则和序列模式算法对网络数据进行充分挖掘，分别给出了基于时间窗口的训练阶段和检测阶段的挖掘算法，并建立贝叶斯网络，进一步判定规则挖掘中的可疑行为，提高检测的准确率。     

一种杂交特征选择算法及其应用

提出一种新的特征选择算法,融合了信息熵和关联规则理论,并应用于检测P2P下载的数据集,目的是检测局域网内占用较大带宽下载的用户。该方法计算含有和不含有P2P下载的数据集各属性的熵值,对两者进行对比,将熵值变化大的属性标记为感兴趣属性。利用关联规则对含有P2P下载的数据集挖掘出大于一定阈值的1频繁项目集的属性,得到精简的属性集。利用该精简属性集,提出一种检测模型,用于检测局域网中P2P大规模下载的用户,取得了较好的效果。     

一种杂交特征选择算法及其应用

提出一种新的特征选择算法,融合了信息熵和关联规则理论,并应用于检测P2P下载的数据集,目的是检测局域网内占用较大带宽下载的用户.该方法计算含有和不含有P2P下载的数据集各属性的熵值,对两者进行对比,将熵值变化大的属性标记为感兴趣属性.利用关联规则对含有P2P下载的数据集挖掘出大于一定阈值的1频繁项目集的属性,得到精简的属性集.利用该精简属性集,提出一种检测模型,用于检测局域网中P2P大规模下载的用户,取得了较好的效果.     

基于交叠数据窗距离测度概念漂移检测新方法

针对数据流中的概念漂移检测存在错误检测、延迟检测等问题,提出了一种基于交叠数据窗距离测度的在线概念漂移检测方法。通过将数据流划分成大小相等且交叠的数据窗并计算相邻交叠数据窗异构欧氏距离,同时利用近邻原则判别数据窗中样本不一致程度,从而实现分布差异性评价和漂移的检测。为评价该方法的有效性,在具有不同漂移严重程度和漂移速度的公开数据集上进行了实验,实验结果表明:该方法能够准确快速地检测到不同类型的概念漂移且能够找出概念漂移发生的具体位置。     

F-粗糙集视角的概念漂移与属性约简

概念漂移探测是数据流挖掘具有挑战意义的研究难点,属性约简是粗糙集理论的研究核心.从概念漂移的角度研究了粗糙集理论的属性约简,从粗糙集属性约简的角度研究了概念漂移,将概念漂移和属性约简进行分析比较,指出了它们之间的区别和联系.提出了基于属性依赖度和条件熵的概念漂移探测准则,并将两种常用的概念漂移探测准则与属性依赖度、条件熵探测准则进行了比较.属性依赖度和条件熵兼具分类准确率的可实验检验和联合概率分布可进行理论分析的优点,还可以进行属性约简（或特征选择）.实验结果显示,属性依赖度、条件熵和分类准确率都能有效地探测概念漂移,但是,与分类准确率相比,属性依赖度和条件熵在探测概念漂移时可以增加可重用性,减少工作量.属性约简和概念漂移之间关系的研究为属性约简、概念漂移的研究提供了新方法,为粗糙集、粒计算进一步融入大数据时代潮流提供了新思路.     

网络流量识别的自适应分级滑动窗决策树算法

针对网络流量存在概念漂移、不同应用类型数据流偏态分布等特性, 提出了基于Hoeffding决策树的自适应分级滑动窗决策树的网络流量识别算法。该算法根据节点信息增益率检测概念漂移、动态调整概念漂移检测窗口及不同类型训练样本集窗口, 实现对不同速率概念漂移的自适应分类和决策树更新。实验结果显示新算法对劣势频繁漂移的应用类型的识别准确率与batch C4. 5算法接近, 比CVFDT算法提高约20%, 可以获得更加均衡的不同应用类型分类准确度。     

改进Hoeffding不等式的概念漂移检测方法

针对大多数概念漂移检测算法都存在高延迟和对噪声过于敏感的问题,提出了一种基于四分位距交叠滑动窗口的概念漂移检测方法,该方法使用四分位距窗口中的样本和改进的Hoeffding不等式进行概念漂移检测。为更好地避免噪声对分类器性能的影响,算法在Hoeffding不等式中引入了一个基于当前样本分类正确率的动态系数。实验结果表明,改进后的方法可以有效提高概念漂移检测的准确率,减少漂移检测延迟。     

面向工业过程软测量建模的概念漂移检测综述

基于数据驱动的软测量模型广泛用于工业过程中产品质量与环保指标等难测参数的在线测量,该过程中存在的概念漂移问题易导致模型精度下降.如何有效识别过程概念变化并精准检测漂移样本是提高模型测量性能的关键.本文总结并分析目前漂移检测的研究思路与进展,为面向工业过程软测量的漂移检测算法提供设计指导.首先,介绍了概念漂移的通常定义与其在工业过程中的表现形式;然后,从检测依据与检测对象两个视角分析了目前具有代表性的检测方法;接着,讨论了这些算法的技术特点和当前工业领域的研究难点;最后,展望了未来的研究方向.     

DetectA: abrupt concept drift detection in non-stationary environments

Almost all drift detection mechanisms designed for classification problems work reactively: after receiving the complete data set (input patterns and class labels) they apply a sequence of procedures to identify some change in the class-conditional distribution – a concept drift. However, detecting changes after its occurrence can be in some situations harmful to the process under analysis. This paper proposes a proactive approach for abrupt drift detection, called DetectA (Detect Abrupt Drift). Briefly, this method is composed of three steps: (i) label the patterns from the test set (an unlabelled data block), using an unsupervised method; (ii) compute some statistics from the train and test sets, conditioned to the given class labels for train set; and (iii) compare the training and testing statistics using a multivariate hypothesis test. Based on the results of the hypothesis tests, we attempt to detect the drift on the test set, before the real labels are obtained. A procedure for creating datasets with abrupt drift has been proposed to perform a sensitivity analysis of the DetectA model. The result of the sensitivity analysis suggests that the detector is efficient and suitable for datasets of high-dimensionality, blocks with any proportion of drifts, and datasets with class imbalance. The performance of the DetectA method, with different configurations, was also evaluated on real and artificial datasets, using an MLP as a classifier. The best results were obtained using one of the detection methods, being the proactive manner a top contender regarding improving the underlying base classifier accuracy.     

基于在线性能测试的概念漂移检测方法

概念漂移是动态流数据挖掘中一类常见的问题,但混杂噪声或训练样本规模过小而产生的伪概念漂移会引起与真实概念漂移相似的结果,即模型在线测试性能的不稳定波动,导致二者容易混淆,发生概念漂移的误报.针对流数据中真伪概念漂移的混淆问题,提出一种基于在线性能测试的概念漂移检测方法(concept drift detection method based on online performance test,简称CDPT).该方法将最新获得的数据集进行均匀分组,在每组子数据集上分别进行在线学习,同时记录每组子数据集训练测试得到的分类精度向量,并计算相邻学习时间单元之间的精度落差,依据测试精度下降阈值得到有效波动位点.然后采用交叉检验的方式整合不同分组中的有效波动位点,以消除流数据在线学习过程中由于训练样本过小导致模型不稳定造成的检测干扰,根据精度波动一致性得到一致波动位点.最后,通过跟踪在线学习分类准确率,得到一致波动位点邻域参照点的测试精度变化,比较一致波动位点邻域参照点对应的模型测试精度下降幅度及收敛情况,以有效检测一致波动位点当中真实的概念漂移位点.实验结果表明,该方法能够有效辨识流数据在线学习过程中发生的真实概念漂移,并能有效避免训练样本过小或者流数据中噪声对检测结果的负面影响,同时提高模型的泛化性能.     

基于模糊聚类的数据流概念漂移检测算法

针对数据流中可能出现的概念漂移现象,采用改进的FCM算法进行模糊聚类,提出在大小可变的滑动窗口中通过度量相邻窗口之间的差异性来判断是否发生了概念漂移,并给出了相应的处理方法。实验表明该算法能够有效地检测出数据流中的概念漂移现象,具有很好的聚类效果和很高的时间效率。     

Exponentially weighted moving average charts for detecting concept drift

Classifying streaming data requires the development of methods which are computationally efficient and able to cope with changes in the underlying distribution of the stream, a phenomenon known in the literature as concept drift. We propose a new method for detecting concept drift which uses an exponentially weighted moving average (EWMA) chart to monitor the misclassification rate of an streaming classifier. Our approach is modular and can hence be run in parallel with any underlying classifier to provide an additional layer of concept drift detection. Moreover our method is computationally efficient with overhead O(1) and works in a fully online manner with no need to store data points in memory. Unlike many existing approaches to concept drift detection, our method allows the rate of false positive detections to be controlled and kept constant over time.     

基于主要特征抽取的重现概念漂移处理算法

针对重现概念漂移检测中的概念表征和分类器选择问题,提出了一种适用于含重现概念漂移的数据流分类的算法——基于主要特征抽取的概念聚类和预测算法（Conceptual clustering and prediction through main feature extraction, MFCCP）。MFCCP通过计算不同批次样本的主要特征及影响因子的差异度以识别重复出现的概念,为每个概念维持且及时更新一个分类器,并依据Hoeffding不等式选择最合适的分类器对当前样本集实施分类,以 提高对概念漂移的反应能力。在3个数据集上的实验表明：MFCCP在含重现概念漂移的数据集上的分类准确率,对概念漂移的反应能力及对概念漂移检测的准确率均明显优于其他4种 对比算法,且MFCCP也适用于对不含重现概念漂移的数据流进行分类。