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

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

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

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

Real-time data mining of non-stationary data streams from sensor networks

In real-world sensor networks, the monitored processes generating time-stamped data may change drastically over time. An online data-mining algorithm called OLIN (on-line information network) adapts itself automatically to the rate of concept drift in a non-stationary data stream by repeatedly constructing a classification model from every sliding window of training examples. In this paper, we introduce a new real-time data-mining algorithm called IOLIN (incremental on-line information network), which saves a significant amount of computational effort by updating an existing model as long as no major concept drift is detected. The proposed algorithm builds upon the oblivious decision-tree classification model called “information network” (IN) and it implements three different types of model updating operations. In the experiments with multi-year streams of traffic sensors data, no statistically significant difference between the accuracy of the incremental algorithm (IOLIN) vs. the regenerative one (OLIN) has been observed.     

一种自适应局部概念漂移的数据流分类算法

本文基于DB2算法提出一个能实时检测局部概念漂移,并随之自适应调整的数据流分类算法IncreDB2.该算法动态增量维护一个层次分类树.当局部概念漂移出现时,IncreDB2不是重新构造一个全新的分类树,而是仅更新漂移所影响到的局部结点,具有较高的时间效率.实验结果表明了该算法的正确性和有效性.     

Detecting anomalies from high-dimensional wireless network data streams: a case study

In this paper, we study the problem of anomaly detection in wireless network streams. We have developed a new technique, called Stream Projected Outlier deTector (SPOT), to deal with the problem of anomaly detection from multi-dimensional or high-dimensional data streams. We conduct a detailed case study of SPOT in this paper by deploying it for anomaly detection from a real-life wireless network data stream. Since this wireless network data stream is unlabeled, a validating method is thus proposed to generate the ground-truth results in this case study for performance evaluation. Extensive experiments are conducted and the results demonstrate that SPOT is effective in detecting anomalies from wireless network data streams and outperforms existing anomaly detection methods.     

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.     

新型含噪数据流集成分类的算法

针对数据流中概念漂移和噪声问题,提出一种新型的增量式学习的数据流集成分类算法。首先,引入噪声过滤机制过滤噪声;然后,引入假设检验方法对概念漂移进行检测,以增量式C4.5决策树为基分类器构建加权集成模型;最后,实现增量式学习实例并随之动态更新分类模型。实验结果表明,该集成分类器对概念漂移的检测精度达到95%~97%,对数据流抗噪性保持在90%以上。该算法分类精度较高,且在检测概念漂移的准确性和抗噪性方面有较好的表现。     

一种面向周期性概念漂移的数据流分类算法

数据流挖掘已在许多领域得到应用,概念漂移检测是数据流挖掘研究中的一个重点.目前关于数据流中的概念检测的研究虽然取得了很多成果,却没有充分考虑到数据流概念"周期性"出现的特点.针对周期性概念漂移的特点,提出了当"历史概念"重现时,利用对应的模型来对数据流进行分类的方法,从而减小模型更新的代价,加快分类预测的速度.实验证明这种方法提高了运行效率.     

面向高速数据流的集成分类器算法

数据流挖掘要求算法在占用少量内存空间的前提下快速地处理数据并且自适应概念漂移,据此提出一种面向高速数据流的集成分类器算法。该算法将原始数据流沿着时间轴划分为若干数据块后,在各个数据块上计算所有类别的中心点和对应的子空间;此后将各个数据块上每个类别的中心点和对应的子空间集成作为分类模型,并利用统计理论的相关知识检测概念漂移,动态地调整模型。实验结果表明,该方法能够在自适应数据流概念漂移的前提下对数据流进行快速的分类,并得到较好的分类效果。     

基于自适应快速决策树的不确定数据流概念漂移分类算法

由于不确定数据流中一般隐藏着概念漂移问题, 对其进行有效分类存在着很多困难. 为此, 提出一种基于自适应快速决策树的算法. 该算法基于一般决策树算法的原理, 以自适应学习规则计算信息增益, 以无标记情景学习拆分原理检测不确定数据流中的不确定数值属性, 通过自适应快速决策树节点的拆分方法将不确定数值属性转化为不确定分类属性, 以实现对不确定数据流的有效分类, 进而有效检测到其中隐含的概念漂移现象. 仿真结果验证了所提出方法的可靠性.

     

基于分层校验的多标签数据流概念漂移检测

现有的概念漂移检测方法大多集中于单标签数据流,难以满足多标签数据流概念漂移检测的需要,因此文中提出基于分层校验的多标签数据流概念漂移检测算法.算法包括检验层和校验层,检验层通过检测数据分布变化判断是否发生概念漂移,校验层通过判断标签混淆矩阵的变化程度验证是否真正发生概念漂移.在真实多标签数据集和合成多标签数据集上的实验表明,文中算法表现更优,可以有效检测概念漂移,提升分类性能.     

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

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

A data mining approach for machine fault diagnosis based on associated frequency patterns

Bearings play a crucial role in rotational machines and their failure is one of the foremost causes of breakdowns in rotary machinery. Their functionality is directly relevant to the operational performance, service life and efficiency of these machines. Therefore, bearing fault identification is very significant. The accuracy of fault or anomaly detection by the current techniques is not adequate. We propose a data mining-based framework for fault identification and anomaly detection from machine vibration data. In this framework, to capture the useful knowledge from the vibration data stream (VDS), we first pre-process the data using Fast Fourier Transform (FFT) to extract the frequency signature and then build a compact tree called SAFP-tree (sliding window associated frequency pattern tree), and propose a mining algorithm called SAFP. Our SAFP algorithm can mine associated frequency patterns (i.e., fault frequency signatures) in the current window of VDS and use them to identify faults in the bearing data. Finally, SAFP is further enhanced to SAFP-AD for anomaly detection by determining the normal behavior measure (NBM) from the extracted frequency patterns. The results show that our technique is very efficient in identifying faults and detecting anomalies over VDS and can be used for remote machine health diagnosis.     

基于流量异常分析多维优化的入侵检测方法

入侵检测系统在检测和预防各种网络异常行为的过程中,海量和高维的流量数据使其面临着低准确率和高误报率的问题。本文提出一种基于流量异常分析多维优化的入侵检测方法,该方法在入侵检测数据的横向维度和纵向维度两个维度进行优化。在横向维度优化中,对数量较多的类别进行数据抽样,并采用遗传算法得到每个类别的最佳抽样比例参数,完成数据的均衡化。在纵向维度优化中,结合特征与类别的相关分析,采用递归特征添加算法选择特征,并提出平均召回率指标评估特征选择效果,实现训练集的低维高效性。基于优化的入侵检测数据,进一步通过训练数据集得到随机森林分类器,在真实数据集UNSW_NB15评估和验证本文提出的算法。与其他算法相比,本文算法具有高准确率和低误报率,并在攻击类型上取得了有效的召回率。     

An approach of support approximation to discover frequent patterns from concept-drifting data streams based on concept learning

In an online data stream, the composition and distribution of the data may change over time, which is a phenomenon known as concept drift. The occurrence of concept drift can affect considerably the performance of a data stream mining method, especially in relation to mining accuracy. In this paper, we study the problem of mining frequent patterns from transactional data streams in the presence of concept drift, considering the important issue of mining accuracy preservation. In terms of frequent-pattern mining, we give the definitions of concept and concept drift with respect to streaming data; moreover, we present a categorization for concept drift. The concept of streaming data is considered the relationships of frequency between different patterns. Accordingly, we devise approaches to describe the concept concretely and to learn the concept through frequency relationship modeling. Based on concept learning, we propose a method of support approximation for discovering data stream frequent patterns. Our analyses and experimental results have shown that in several studied cases of concept drift, the proposed method not only performs efficiently in terms of time and memory but also preserves mining accuracy well on concept-drifting data streams.     

基于改进主元分析方法的隧道应变实时监测预警系统

针对同步多维数据流异常分析技术提出了一种改进的主元分析(PCA)方法。将原始数据流空间的变化趋势映射到特征向量空间内,求解稳态特征向量,以瞬时特征向量与稳态特征向量之间的关系作为判据来对同步多维数据流进行异常变化诊断。将该方法应用于某隧道应变监测数据的异常诊断中,并利用VC++实现了隧道应变实时监测预警系统。实验结果表明,使用该方法能够实时反映非周期性监控变量的变化情况,较好地实现同步多维数据流的异常诊断。     

基于贝叶斯树的主机异常检测

主要研究Windows平台下异常检测方法,提出了一种利用Windows Native API调用序列和基于贝叶斯树算法的主机服务进程规则和对应概率分布的生成算法,并建立正常模型.根据长为N-1的Windows Native APIs调用序列预测第N个调用的概率分布,对生成的概率序列用U检验方法作为异常检测算法.实验结果...     

流数据概念漂移的检测算法

鉴于流数据具有实时、连续、有序和无限等特点,使用近似方法便可检测连续分时段的流数据序列,基于此,运用目标分布数据,结合相似分布理论,提出了利用 Tr-OEM 算法对流数据中的概念漂移现象进行检测.该算法能够动态地判断流数据概念漂移的发生,自适应地优化概念漂移的检测值,适用于不同类型的流数据.通过分析和实验仿真可以表明,该算法在处理流数据概念漂移时具有较好的适应性.     

基于向量表示和标签传播的半监督短文本数据流分类算法

社交网络平台产生海量的短文本数据流,具有快速、海量、概念漂移、文本长度短小、类标签大量缺失等特点.为此,文中提出基于向量表示和标签传播的半监督短文本数据流分类算法,可对仅含少量有标记数据的数据集进行有效分类.同时,为了适应概念漂移,提出基于聚类簇的概念漂移检测算法.在实际短文本数据流上的实验表明,相比半监督分类算法和半监督数据流分类算法,文中算法不仅提高分类精度和宏平均,还能快速适应数据流中的概念漂移.     

自适应概念漂移的在线集成分类器

数据流挖掘要求算法能快速地响应、占用少量内存和自适应概念漂移。根据以上要求提出一种自适应概念漂移的基于Hoeffding树在线Bagging分类算法。利用统计学理论,检验分类模型在自适应窗口内数据的分类精度是否落入真实错误率的单侧置信区间,由检测结果决定更新Hoeffding树或重建新Hoeffding树。实验结果表明,该算法在处理带有概念漂移的数据流上表现出较高的分类精度。