An ensemble method for data stream classification in the presence of concept drift

One recent area of interest in computer science is data stream management and processing. By ‘data stream', we refer to continuous and rapidly generated packages of data. Specific features of data streams are immense volume, high production rate, limited data processing time, and data concept drift; these features differentiate the data stream from standard types of data. An issue for the data stream is classification of input data. A novel ensemble classifier is proposed in this paper. The classifier uses base classifiers of two weighting functions under different data input conditions. In addition, a new method is used to determine drift, which emphasizes the precision of the algorithm. Another characteristic of the proposed method is removal of different numbers of the base classifiers based on their quality. Implementation of a weighting mechanism to the base classifiers at the decision-making stage is another advantage of the algorithm. This facilitates adaptability when drifts take place, which leads to classifiers with higher efficiency. Furthermore, the proposed method is tested on a set of standard data and the results confirm higher accuracy compared to available ensemble classifiers and single classifiers. In addition, in some cases the proposed classifier is faster and needs less storage space.

A Classifier Using Online Bagging Ensemble Method for Big Data Stream Learning

By combining multiple weak learners with concept drift in the classification of big data stream learning, the ensemble learning can achieve better generalization performance than the single learning approach. In this paper,we present an efficient classifier using the online bagging ensemble method for big data stream learning. In this classifier, we introduce an efficient online resampling mechanism on the training instances, and use a robust coding method based on error-correcting output codes. This is done in order to reduce the effects of correlations between the classifiers and increase the diversity of the ensemble. A dynamic updating model based on classification performance is adopted to reduce the unnecessary updating operations and improve the efficiency of learning.We implement a parallel version of EoBag, which runs faster than the serial version, and results indicate that the classification performance is almost the same as the serial one. Finally, we compare the performance of classification and the usage of resources with other state-of-the-art algorithms using the artificial and the actual data sets, respectively. Results show that the proposed algorithm can obtain better accuracy and more feasible usage of resources for the classification of big data stream.

Drift DetectionMethod Using DistanceMeasures and Windowing Schemes for Sentiment Classification

Textual data streams have been extensively used in practical applications where consumers of online products have expressed their views regarding online products.Due to changes in data distribution,commonly referred to as concept drift,mining this data stream is a challenging problem for researchers.The majority of the existing drift detection techniques are based on classification errors,which have higher probabilities of false-positive or missed detections.To improve classification accuracy,there is a need to develop more intuitive detection techniques that can identify a great number of drifts in the data streams.This paper presents an adaptive unsupervised learning technique,an ensemble classifier based on drift detection for opinion mining and sentiment classification.To improve classification performance,this approach uses four different dissimilarity measures to determine the degree of concept drifts in the data stream.Whenever a drift is detected,the proposed method builds and adds a new classifier to the ensemble.To add a new classifier,the total number of classifiers in the ensemble is first checked if the limit is exceeded before the classifier with the least weight is removed from the ensemble.To this end,a weighting mechanism is used to calculate the weight of each classifier,which decides the contribution of each classifier in the final classification results.Several experiments were conducted on real-world datasets and the resultswere evaluated on the false positive rate,miss detection rate,and accuracy measures.The proposed method is also compared with the state-of-the-art methods,which include DDM,EDDM,and PageHinkley with support vector machine(SVM)and Naive Bayes classifiers that are frequently used in concept drift detection studies.In all cases,the results show the efficiency of our proposed method.

基于增量加权的不平衡漂移数据流分类算法

概念漂移是数据流学习领域中的一个难点问题,同时数据流中存在的类不平衡问题也会严重影响算法的分类性能。针对概念漂移和类不平衡的联合问题,在基于数据块集成的方法上引入在线更新机制,结合重采样和遗忘机制提出了一种增量加权集成的不平衡数据流分类方法(incremental weighted ensemble for imbalance learning,IWEIL)。该方法以集成框架为基础,利用基于可变大小窗口的遗忘机制确定基分类器对窗口内最近若干实例的分类性能,并计算基分类器的权重,随着新实例的逐个到达,在线更新IWEIL中每个基分器及其权重。同时,使用改进的自适应最近邻SMOTE方法生成符合新概念的新少数类实例以解决数据流中类不平衡问题。在人工数据集和真实数据集上进行实验,结果表明,相比于DWMIL算法,IWEIL在HyperPlane数据集上的G-mean和recall指标分别提升了5.77%和6.28%,在Electricity数据集上两个指标分别提升了3.25%和6.47%。最后,IWEIL在安卓应用检测问题上表现良好。

基于聚簇模型重用的概念漂移数据流半监督分类算法

带概念漂移的半监督数据流分类任务中,仅有少部分的数据被标记,这给分类器的训练、概念漂移的检测以及分类器对新概念的适应带来了巨大的挑战。现有的半监督聚簇分类算法仅对分类器池中的聚簇模型进行简单的增量更新,未能有效重用历史聚簇模型。因此,文中提出了一种新的聚簇模型重用的半监督分类算法,称为CDCMR。首先,数据流以数据块的形式到来,对数据块分完类后,训练一个簇数自适应确定的聚簇模型。其次,通过计算分类器池中的各组件分类器与聚簇模型之间的相似度,挑选多个组件分类器。再次,用当前数据块对挑选出来的组件分类器进行模型重用后,与聚簇模型集成。然后,将分类器池划分为新旧更替和多样性最大化分类器池进行更新。最后,对下一个数据块的样本进行集成分类。在多个人工和真实数据集上进行实验,结果表明,所提算法1)能有效适应概念漂移,与现有方法相比其性能有显著性提升。

基于在线集成的概念漂移自适应分类方法

针对流数据中概念漂移发生后,在线学习模型不能对分布变化后的数据做出及时响应且难以提取数据分布的最新信息,导致学习模型收敛较慢的问题,提出一种基于在线集成的概念漂移自适应分类方法(adaptive classification method for concept drift based on online ensemble,AC_OE).一方面,该方法利用在线集成策略构建在线集成学习器,对数据块中的训练样本进行局部预测以动态调整学习器权重,有助于深入提取漂移位点附近流数据的演化信息,对数据分布变化进行精准响应,提升在线学习模型对概念漂移发生后新数据分布的适应能力,提高学习模型的实时泛化性能;另一方面,利用增量学习策略构建增量学习器,并随新样本的进入进行增量式的训练更新,提取流数据的全局分布信息,使模型在平稳的流数据状态下保持较好的鲁棒性.实验结果表明,该方法能够对概念漂移做出及时响应并加速在线学习模型的收敛速度,同时有效提高学习器的整体泛化性能.

一种面向动态不平衡数据流的集成超限学习机分类算法

随着数据收集、存储和传输技术的快速发展,数据流的挖掘处理技术正在成为机器学习中的一个热点问题。在许多情形下,持续到达的数据之间可能会呈现出不平衡的态势,甚至是动态不平衡,这给许多机器学习算法造成了困难。文中提出面向动态不平衡数据流的集成超限学习机算法,设计了数据流中不平衡率变化的快速监测方法,修正了历史数据不平衡率的计算方式,使其更接近不平衡率的实时变化,并结合超限学习机的特点,将增量学习与集成学习结合。定期剔除权重低的基分类器,利用新到达的数据更新集成中的基分类器和训练新的基分类器。该方法针对动态不平衡数据流设计,具有很好的学习能力,同时也能适用于静态或者平衡的数据流的分类。实验中,将该方法与其他几种常用的方法在一些不同类型的数据流上进行了比较,结果表明,文中方法的分类性能更好。

基于差异指标的概念漂移数据流集成分类仿真

集成算法是处理概念漂移数据流的常用方法之一。为了更全面反映基分类器在模型中的整体价值,提出了一种基于差异指标的概念漂移数据流的集成分类算法AE-Div(Ensemble Algorithm for Data Streams with Concept Drift Based on Diversity Measure)。将基分类器的分类准确率和集成差异性进行融合,结合时间因子作为综合度量指标,并根据概念漂移检测情况对基分类器设置不同权重。将AE-Div算法与其它几种使用广泛的概念漂移分类算法在合成数据集与真实数据集上进行仿真。结果表明,AE-Div具有更高的准确率和更好的适应性和稳定性。

面向概念漂移数据流的在线集成自适应算法

概念漂移是流数据的主要特征之一,如何检测概念漂移的发生以及调整预测模型去适应概念漂移现象备受研究者的关注.目前有关概念漂移的大多数算法仅仅针对单一类型的概念漂移检测,并且需限制输入数据服从某一分布,所以在检测多种类型概念漂移时效果不理想.提出一种在线集成自适应算法(KSHPR),在自适应随机森林(Adaptive Random Forests,ARF)算法和流随机补丁(Streaming Random Patch,SRP)算法的基础上进行优化改进,采用非参数检验与滑动窗口相结合的策略进行概念漂移检测,降低窗口平均值对算法性能的影响,并以此为基础建立四个基学习者的集成学习模型,根据基学习者预测准确率,动态分配权值,有效解决流式数据中学习模型精度低的问题.实验证明,提出的算法在真实数据集和合成数据集中均表现优良,与其他算法相比,该算法的稳定性、分类准确性与多类型概念漂移适应能力均有所提升.

数据流挖掘分类技术综述

数据流挖掘作为从连续不断的数据流中挖掘有用信息的技术,近年来正成为数据挖掘领域的研究热点,并有着广泛的应用前景.数据流具有数据持续到达、到达速度快、数据规模巨大等特点,因此需要新颖的算法来解决这些问题.而数据流挖掘的分类技术更是当前的研究热点.综述了当前国际上关于数据流挖掘分类算法的研究现状,并从数据平稳分布和带概念漂移两个方面对这些方法进行了系统的介绍与分析,最后对数据流挖掘分类技术当前所面临的问题和发展趋势进行了总结和展望.

一种不平衡数据流集成分类模型

针对不平衡数据流的分类问题,结合基于权重的集成分类器与抽样技术,本文提出了一种处理不平衡数据流集成分类器模型.理论分析与实验验证表明,该集成分类器具有更低的计算复杂度,更能适应存在概念漂移的不平衡数据流挖掘分类,其整体分类性能优于基于权重的集成分类器模型,能明显提升少数类的分类精度.

基于信息熵的数据流自适应集成分类算法

数据流分类模型是面向连续变化的实时分析的基本问题.目前大多数的数据流算法只针对突变式或渐变式概念漂移进行处理的,并未充分考虑概念会重现的特点.为此提出了一种具有概念漂移检测机制的自适应集成算法.从信息熵的角度出发,用Jensen-Shannon散度度量相邻两个窗口间数据分布的距离,不仅能检测出不同类型的概念漂移,且能有效地发现重现的概念;采用分类器池机制来保存历史概念,从而实现对概念的重用.将所提出的算法与几种经典的学习算法在人工合成和真实数据集上进行了广泛的对比实验.实验结果表明,所提出的算法在平均分类准确率上具有明显的优势,比其他集成算法消耗更少的时间,适合多种类型概念漂移的环境,并具有较高的抗噪性.

数据流上概念漂移的检测和分类

挖掘带有概念漂移的数据流对于许多实时决策是十分重要的.本文使用统计学理论估计某一确定模型在最新概念上的真实错误率的置信区间,在一定概率保证下检测数据流中是否发生了概念漂移,并将此方法和KMM(核平均匹配)算法引入集成分类器框架中,提出一种数据流分类的新算法WSEC.在仿真和真实数据流上的试验结果表明该算法是有效的.

具有回忆和遗忘机制的数据流挖掘模型与算法

集成式数据流挖掘是对存在概念漂移的数据流进行学习的重要方法.针对传统集成式数据流挖掘存在的缺陷,将人类的回忆和遗忘机制引入到数据流挖掘中,提出基于记忆的数据流挖掘模型MDSM(memorizing based data stream mining).该模型将基分类器看作是系统获得的知识,通过"回忆与遗忘"机制,不仅使历史上有用的基分类器因记忆强度高而保存在"记忆库"中,提高预测的稳定性,而且从"记忆库"中选取当前分类效果好的基分类器参与集成预测,以提高对概念变化的适应能力.基于MDSM模型,提出了一种集成式数据流挖掘算法MAE(memorizing based adaptive ensemble),该算法利用Ebbinghaus遗忘曲线对系统的遗忘机制进行设计,并利用选择性集成来模拟人类的"回忆"机制.与4种典型的数据流挖掘算法进行比较,结果表明:MAE算法分类精度高,对概念漂移的整体适应能力强,尤其对重复出现的概念漂移以及实际应用中存在的复杂概念漂移具有很好的适应能力.不仅能够快速适应新的概念变化,并且能够有效抵御随机的概念波动对系统性能的影响.

数据流滑动窗口方式下的自适应集成分类算法

针对基于数据块的集成算法,存在数据块大小影响分类效果,且不能及时应对完整式概念漂移的问题,提出了一种考虑数据流局部特征的和能应对多种类型概念漂移的集成分类算法.用滑动窗口作为概念漂移检测器,当检测到概念漂移时,则建立新的分类器并加入到集成分类器中.本文提出的算法在人工合成和真实数据集上与经典算法进行了广泛的对比实验.结果表明:提出的算法在分类准确率上具有明显优势,消耗更少的内存,更适合多种类型概念漂移的环境.

面向噪音和概念漂移数据流的集成分类算法

隐含概念漂移的数据流分类问题是数据挖掘领域研究的热点之一,而实际数据流中的噪音会影响数据流的分类质量,为此,提出一种面向噪音和概念漂移数据流的集成分类算法.该算法使用支持向量机作为基分类器,采用贝叶斯分类器过滤噪音,利用Hoeffding Bounds不等式确定的双阈值检测概念漂移,并动态地更新分类模型以适应数据流环境的变化.实验结果表明,本文提出的算法可以有效地跟踪检测含噪数据流中的概念漂移,并且具有较好的分类精度.

基于实例加权方法的概念漂移问题研究

数据流上的漂移概念发现已成为数据挖掘领域的研究热点之一。针对存在概念漂移的数据流分类问题,提出一种基于实例加权方法的数据流分类算法(EWAMDS),根据基分类器在训练实例上的分类结果调整该实例的权值,以增强漂移实例在新分类器中的影响,同时引入动态的权值修改因子以提高算法的适应性。实验结果表明,动态地调整实例的权值时算法的适应性更强;与weighted-bagging相比,EWAMDS的时间开销显著降低、分类正确率显著提高。

一种面向不平衡数据流的集成分类算法

大部分数据流算法都是基于类分布大致平衡这一假设的,然而在现实世界中数据流中类的分布往往是不平衡的.同时,数据流中目标概念可能会随着时间发生变化,即概念漂移.本文针对数据流中的概念漂移和类不平衡问题,提出了一种基于集成的不平衡数据流分类算法.在分类之前加入采样方法应对类不平衡问题,并采取有效的基分类器更新和加权策略应对概念漂移现象,从而提高分类器的性能.针对本文所提出的算法,和几种经典学习算法,在人工合成和真实数据集上进行了广泛的对比实验.实验结果表明本文所提出的算法,其整体分类性能优于其他算法,更能适应存在概念漂移和类不平衡的数据流环境.

结合无监督学习的数据流分类算法

为了能有效应对数据流中的概念漂移现象,提出结合无监督学习的数据流分类算法.该算法以集成式分类技术为基础,在分类过程中引入属性约简,利用聚类算法对数据进行聚类,通过对比分类和聚类结果的准确率,判断是否发生概念漂移.实验表明,文中算法在综合时间花销和准确率上取得较好效果.

一种基于分类器相似性集成的数据流分类研究

数据流分类已成为当前研究热点之一,如何解决其中的概念漂移和噪声是关键问题,为此提出了一种新的基于分类器相似性的动态集成算法。由于数据流中相邻数据具有相同概念的概率较大,因此用最新基分类器代表数据流中即将出现的概念,同时基于此分类器求出基分类器之间的相似性作为权值进行加权多数投票,并根据相似性大小淘汰较弱基分类器以适应概念漂移和噪声。在标准仿真数据集上进行了仿真实验,结果表明该算法相比其他集成方法在抗噪性能和分类准确性方面均得到显著提高。