一种基于混合模型的数据流概念漂移检测算法

由于在信用卡欺诈分析等领域的广泛应用,学者们开始关注概念漂移数据流分类问题.现有算法通常假设数据一旦分类后类标已知,利用所有待分类实例的真实类别来检测数据流是否发生概念漂移以及调整分类模型.然而,由于标记实例需要耗费大量的时间和精力,该解决方案在实际应用中无法实现.据此,提出一种基于KNNModel和增量贝叶斯的概念漂移检测算法KnnM-IB.新算法在具有KNNModel算法分类被模型簇覆盖的实例分类精度高、速度快优点的同时,利用增量贝叶斯算法对难处理样本进行分类,从而保证了分类效果.算法同时利用可变滑动窗口大小的变化以及主动学习标记的少量样本进行概念漂移检测.当数据流稳定时,半监督学习被用于扩大标记实例的数量以对模型进行更新,因而更符合实际应用的要求.实验结果表明,该方法能够在对数据流进行有效分类的同时检测数据流概念漂移及相应地更新模型.     

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

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

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

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

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

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

低代价的数据流分类算法

现有数据流分类算法大多使用有监督学习,而标记高速数据流上的样本需要很大的代价,因此缺乏实用性.针对以上问题,提出了一种低代价的数据流分类算法2SDC.新算法利用少量已标记类别的样本和大量未标记样本来训练和更新分类模型,并且动态监测数据流上可能发生的概念漂移.真实数据流上的实验表明,2SDC算法不仅具有和当前有监督学习分类算法相当的分类精度,并且能够自适应数据流上的概念漂移.     

一种面向不完全标记的文本数据流自适应分类方法

现实生活中网络监控、网络评论以及微博等应用领域涌现了大量文本数据流,这些数据的不完全标记和频繁概念漂移给已有的数据流分类方法带来了挑战。为此,面向不完全标记的文本数据流提出了一种自适应的数据流分类算法。该算法以一个标记数据块作为起始数据块,对未标记数据块首先提取标记数据块与未标记数据块之间的特征集,并利用特征在两个数据块间的相似度进行概念漂移检测,最后计算未标记数据中特征的极性并对数据进行预测。实验表明了算法在分类精度上的优越性,尤其在标记信息较少和概念漂移较为频繁时。     

基于子空间集成的概念漂移数据流分类算法

具有概念漂移的复杂结构数据流分类问题已成为数据挖掘领域研究的热点之一。提出了一种新颖的子空间分类算法,并采用层次结构将其构成集成分类器用于解决带概念漂移的数据流的分类问题。在将数据流划分为数据块后,在每个数据块上利用子空间分类算法建立若干个底层分类器,然后由这几个底层分类器组成集成分类模型的基分类器。同时,引入数理统计中的参数估计方法检测概念漂移,动态调整模型。实验结果表明：该子空间集成算法不但能够提高分类模型对复杂类别结构数据流的分类精度,而且还能够快速适应概念漂移的情况。     

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

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

基于McDiarmid界的概念漂移数据流分类算法

数据流中的概念漂移会导致已有的分类模型性能显著下降.目前处理概念漂移的数据流分类算法大都只针对单一类型的概念漂移(如突变型、渐变型或重复型等),难以同时适应不同场景.为此,提出了一种新的适于多类型概念漂移的数据流分类算法.该算法通过双层窗口保存当前最新的分类结果,根据模糊集隶属度函数对窗口中数据分配权重并计算加权错误率,然后利用McDiarmid界分析当前窗口和过去窗口内错误率的差异δ,根据δ是否具有显著性检测概念漂移.检测到漂移后,使用半参数对数似然算法检验当前概念是否为过去概念的重现,进而决定是否复用旧分类器.实验结果表明,与以往同类算法相比,所提算法在漂移检测延迟、误报率、分类准确率和运行时间等指标上均有一定优势.     

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

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

基于概率相关性的多标签数据流变化检测

由于传统的概念漂移检测研究主要针对单标签数据流,对现实中常见的多标签数据流却缺乏足够的关注,多标签数据流概念漂移检测问题有待进一步的研究。因此,通过分析多标签数据流中存在的特殊依赖关系,提出了一种基于概率相关性的多标签数据流概念漂移检测算法。其基本思想是从概念漂移的产生原因出发,利用概率相关性近似描述数据分布来监测新旧数据分布变化,判断概念漂移是否发生。实验结果表明,提出的算法能够比较快速、准确地检测到概念漂移,并在多标签概念漂移数据流分类问题上取得了预期的学习效果。     

基于聚类假设的数据流分类算法*

获取数据流上样本的真实类别的代价很高,因此标记所有样本的方式缺乏实用性,而随机标记部分样本又会导致模型的不稳定.针对上述问题,文中提出基于聚类假设的数据流分类算法.基于通过聚类算法分到同类中的样本可能具有相同类别这一聚类假设,利用训练数据集上的聚类结果拟合样本的分布情况,在分类阶段有目的性地选取很难分类或潜在概念漂移的样本更新模型.为了训练数据集上每个类别的样本,建立各自对应的基础分类器,当数据流中样本的类别消失或重现时,只需要冻结或激活与之对应的基础分类器,而无需再重新学习之前已经掌握的知识.实验表明,文中算法能够在适应概念漂移的前提下,减少更新模型需要的样本数量,并且取得和当前数据流上的分类算法相当或更好的分类效果.     

Dynamic weighted selective ensemble learning algorithm for imbalanced data streams

Data stream mining is one of the hot topics in data mining. Most existing algorithms assume that data stream with concept drift is balanced. However, in real-world, the data streams are imbalanced with concept drift. The learning algorithm will be more complex for the imbalanced data stream with concept drift. In online learning algorithm, the oversampling method is used to select a small number of samples from the previous data block through a certain strategy and add them into the current data block to amplify the current minority class. However, in this method, the number of stored samples, the method of oversampling and the weight calculation of base-classifier all affect the classification performance of ensemble classifier. This paper proposes a dynamic weighted selective ensemble (DWSE) learning algorithm for imbalanced data stream with concept drift. On the one hand, through resampling the minority samples in previous data block, the minority samples of the current data block can be amplified, and the information in the previous data block can be absorbed into building a classifier to reduce the impact of concept drift. The calculation method of information content of every sample is defined, and the resampling method and updating method of the minority samples are given in this paper. On the other hand, because of concept drift, the performance of the base-classifier will be degraded, and the decay factor is usually used to describe the performance degradation of base-classifier. However, the static decay factor cannot accurately describe the performance degradation of the base-classifier with the concept drift. The calculation method of dynamic decay factor of the base-classifier is defined in DWSE algorithm to select sub-classifiers to eliminate according to the attenuation situation, which makes the algorithm better deal with concept drift. Compared with other algorithms, the results show that the DWSE algorithm has better classification performance for majority class samples and minority samples.

     

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

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

Using dynamical systems tools to detect concept drift in data streams

Real-world data streams may change their behaviors along time, what is referred to as concept drift. By detecting those changes, researchers obtain relevant information about the phenomena that produced such streams (e.g. temperatures in a region, bacteria population, disease occurrence, etc.). Many concept drift detection algorithms consider supervised or semi-supervised approaches which tend to be unfeasible when data is collected at high frequencies, due to the difficulties involved in labeling. Complementarily, current studies usually assume data as statistically independent and identically distributed, disregarding any temporal relationship among observations and, consequently, risking the quality of data modeling. In order to tackle both aspects, we employ dynamical system modeling to represent the temporal relationships among data observations and how they modify along time in attempt to detect concept drift. This approach considers Taken’s immersion theorem to unfold consecutive windows of data observations into the phase space in attempt to represent and compare time dependencies. From this perspective, we proposed four new concept drift detection algorithms based on the unsupervised machine learning paradigm. The first algorithm builds dendrograms of consecutive phase spaces (every phase space represents the time relationships for the observations contained in a particular data window) and compare them out by using the Gromov–Hausdorff distance, providing enough guarantees to detect concept drifts. The second algorithm employs the Cross Recurrence Plot and the Recurrence Quantification Analysis to detect relevant changes in consecutive phase spaces and warn about relevant data modifications. We also preprocess data windows by considering the Empirical Mode Decomposition method and Mutual Information in attempt to take only the deterministic stream behavior into account. All algorithms were implemented as plugins for the Massive Online Analysis (MOA) software and then compared to well-known algorithms from literature. Results confirm the proposed algorithms were capable of detecting most of the behavior changes, creating few false alarms.     

Catching the Trend: A Framework for Clustering Concept-Drifting Categorical Data

Although the problem of clustering numerical time-evolving data is well-explored, the problem of clustering categorical time-evolving data remains as a challenge issue. In this paper, we propose a generalized clustering framework which utilizes existing clustering algorithms and adopts sliding window technique to detect if there is a drifting-concept or not in the incoming sliding window. The framework is composed of two algorithms: Drifting Concept Detecting (abbreviated as DCD) algorithm detecting the changes of cluster distributions between the current sliding window and the last clustering result, and Cluster Relationship Analysis (abbreviated as CRA) algorithm analyzing the relationship between clustering results at different time. In DCD, the concept is said to drift if quite a large number of outliers are found in the current sliding window, or if quite a large number of clusters are varied in the ratio of data points. The drifted sliding window will perform re-clustering to capture the recent concept. In CRA, a visualizing method is devised to facilitate the observation of the evolving clustering results. The framework is validated on real and synthetic data sets, and is shown to not only accurately detect the drifting-concepts but also attain clustering results of better quality.     

含缺失标签的大规模多标签分类算法

在对大规模多标签数据进行人工标注时极易产生标签的缺失。现有算法大多利用被所有实例共享的全局标签相关性来解决该问题,即对不同实例而言,标签之间的相关性是相同的。然而在实际应用中,不同实例的标签相关性并非完全相同,此时采用局部方式获取的标签相关性将更加准确。因此,本文提出一种基于局部标签相关性的解决方法。该方法利用局部标签相关性来恢复缺失标签,利用低秩矩阵分解技术来构造适用于大规模数据的分类器。此外,为了加快模型的训练,该方法将这两个过程融合到一个统一的框架中,并采用迭代优化的方式进行求解。大量实验结果表明,该方法在预测准确度上至少比现有算法高2个百分点,在训练速度上至少提升5个百分点。