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

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

一种基于集成的不均衡数据流分类算法

目前数据流分类算法大多是基于类分布这一理想状态,然而在真实数据流环境中数据分布往往是不均衡的,并且数据流中往往伴随着概念漂移。针对数据流中的不均衡问题和概念漂移问题,提出了一种新的基于集成学习的不均衡数据流分类算法。首先为了解决数据流的不均衡问题,在训练模型前加入混合采样方法平衡数据集,然后采用基分类器加权和淘汰策略处理概念漂移问题,从而提高分类器的分类性能。最后与经典数据流分类算法在人工数据集和真实数据集上进行对比实验,实验结果表明,本文提出的算法在含有概念漂移和不均衡的数据流环境中,其整体分类性能优于其他算法的。     

复杂数据流在线集成分类算法综述

复杂数据流中所存在的概念漂移及不平衡问题降低了分类器的性能。传统的批量学习算法需要考虑内存以及运行时间等因素,在快速到达的海量数据流中性能并不突出,并且其中还包含着大量的漂移及类失衡现象,利用在线集成算法处理复杂数据流问题已经成为数据挖掘领域重要的研究课题。从集成策略的角度对bagging、boosting、stacking集成方法的在线版本进行了介绍与总结,并对比了不同模型之间的性能。首次对复杂数据流的在线集成分类算法进行了详细的总结与分析,从主动检测和被动自适应两个方面对概念漂移数据流检测与分类算法进行了介绍,从数据预处理和代价敏感两个方面介绍不平衡数据流,并分析了代表性算法的时空效率,之后对使用相同数据集的算法性能进行了对比。最后,针对复杂数据流在线集成分类研究领域的挑战提出了下一步研究方向。     

基于Hellinger距离的不平衡漂移数据流Boosting分类算法

数据流中的不平衡问题会严重影响算法的分类性能,其中概念漂移更是流数据挖掘研究领域的一个难点问题。为了提高此类问题下的分类性能,提出了一种新的基于Hellinger距离的不平衡漂移数据流Boosting分类BCA-HD算法。该算法创新性地采用实例级和分类器级的权重组合方式来动态更新分类器,以适应概念漂移的发生,在底层采用集成算法SMOTEBoost作为基分类器,该分类器内部使用重采样技术处理数据的不平衡。在16个突变型和渐变型的数据集上将所提算法与9种不同算法进行比较,实验结果表明,所提算法的G-mean和AUC的平均值和平均排名均为第1名。因此,该算法能更好地适应概念漂移和不平衡现象的同时发生,有助于提高分类性能。     

概念漂移复杂数据流分类方法综述

传统分类器难以应对含概念漂移的复杂类型数据流分类这一难题,且得到的分类效果往往不尽如人意。针对不同类型数据流中处理概念漂移的方法,从不平衡、概念演化、多标签和含噪声4个方面对概念漂移复杂数据流分类方法进行了综述。首先,对基于块的和基于在线的学习方式对不平衡概念漂移数据流、基于聚类和基于模型的学习方式对概念演化概念漂移数据流、基于问题转换和基于算法适应的学习方式对多标签概念漂移数据流和含噪声概念漂移数据流这四个方面的分类方法进行了分析介绍;然后,对所提到概念漂移复杂数据流分类方法的实验结果及性能指标进行了详细的对比和分析;最后,给出了现有方法的不足和下一步研究方向。     

集成基于EP的分类器用于分类数据流

近年来,数据流挖掘已成为知识发现领域中的一个研究热点.数据流中数据的无限性和概念漂移等特征使得传统的分类算法不能很好地适用于数据流环境.提出了一种基于eEP的分类器集成算法CEEPCE(classification by eEP-based classifiers ensemble)对数据流进行分类.CEEPCE使用eEP建立基分类器,当新数据块流入时训练新的分类器,并调整集成分类器中的基分类器.依据基分类器在新流入数据上的分类误差对其进行加权,集成权重最高的若干个基分类器来分类未来数据.实验表明,与单分类器相比,CEEPCE具有更好的分类准确率,并足以与以C4.5为基分类器的集成方法相媲美.     

一种多样性和精度加权的数据流集成分类算法

为了克服数据流中概念漂移对分类的影响,提出了一种基于多样性和精度加权的集成分类方法（diversity and accuracy weighting ensemble classification algorithm, DAWE）,该方法与已有的其他集成方法不同的地方在于,DAWE同时考虑了多样性和精度这两种度量标准,将分类器在最新数据块上的精度及其在集成分类器中的多样性进行线性加权,以此来衡量一个分类器对于当前集成分类器的价值,并将价值度量用于基分类器替换策略。提出的DAWE算法与MOA中最新算法分别在真实数据和人工合成数据上进行了对比实验,实验表明,提出的方法是有效的,在所有数据集上的平均精度优于其他算法,该方法能有效处理数据流挖掘中的概念漂移问题。     

概念漂移数据流集成分类算法综述

针对概念漂移数据流集成分类算法的基本概念、相关工作、适用范围及优缺点等方面进行具体阐述,重点分析突变型、渐变型、重复型和增量型集成分类算法,以及集成分类中的Bagging、Boosting、基分类器组合学习策略与在线学习、基于块的集成、增量学习关键技术,指出现阶段概念漂移数据流集成分类算法所需解决的主要问题,并对集成基分类器的动态更新与加权组合、多类型概念漂移的快速检测等研究方向进行分析和展望。     

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

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

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

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

多重选择决策树算法挖掘概念漂移数据流

重点研究了数据流分类挖掘中存在的概念漂移问题,并在CVFDT算法改进的基础上,提出了一种多重选择决策树算法mCVFDT.该算法将多重属性的选择机制加入到节点结构中,克服了CVFDT无法自动检测概念漂移的缺陷,同时避免了对决策树的重复遍历,提高了算法的分类精度和效率.实验结果证明该,算法随着样本数目的增加,在分类精度上比CVFDT算法有更好的表现.     

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

针对不平衡噪声数据流的分类问题,本文利用基于平均概率的集成分类器AP与抽样技术,提出了一种处理不平衡噪声数据流的集成分类器(IMDAP)模型。实验结果表明,该集成分类器更能适应存在概念漂移与噪声的不平衡数据流挖掘分类,其整体分类性能优于AP集成分类器模型,能明显提升少数类的分类精度,并且具有与AP相近的时间复杂度。     

针对标记数据不足的数据流分类器

大部分数据流分类算法解决了数据流无限长度和概念漂移这两个问题。但是,这些算法需要人工专家将全部实例都标记好作为训练集来训练分类器,这在数据流高速到达并需要快速分类的环境中是不现实的,因为标记实例需要时间和成本。此时,如果采用监督学习的方法来训练分类器,由于标记数据稀少将得到一个弱分类器。提出一种基于主动学习的数据流分类算法,该算法通过选择全部实例中的一小部分来人工标记,其中这小部分实例是分类置信度较低的样本,从而可以极大地减少需要人工标记的实例数量。实验结果表明,该算法可以在数据流存在概念漂移情况下,使用较少的标记数据对数据流训练出分类器,并且分类效果良好。     

一种基于哈希链表的高效概念漂移连续属性处理算法

本文重点研究了数据流挖掘中存在概念漂移情形的连续属性处理算法。数据流是一种增量、在线、实时的数据模型。VFDT是数据流挖掘中数据呈稳态分布情形下最成功的算法之一;CVFDT是有效解决数据流挖掘中概念漂移问题的算法之一。基于CVFDT,本文提出了有效地解决数据流挖掘中存在概念漂移情形的连续属性处理问题的扩展哈希表算法HashCVFDT。该算法在属性值插入、查找和删除时具有哈希表的快速性,而在选取每个连续属性的最优化划分节点时解决了哈希表不能有序输出的缺点。     

Classification in an informative sample subspace

We have developed an informative sample subspace (ISS) method that is suitable for projecting high-dimensional data onto a low-dimensional subspace for classification purposes. In this paper, we present an ISS algorithm that uses a maximal mutual information criterion to search a labelled training data set directly for the subspace's projection base vectors. We evaluate the usefulness of the ISS method using synthetic data as well as real world problems. Experimental results demonstrate that the ISS algorithm is effective and can be used as a general method for representing high-dimensional data in a low-dimensional subspace for classification.     

基于Spark的快速短文本数据流分类方法

微博、脸书等社交网络平台涌现的短文本数据流具有海量、高维稀疏、快速可变等特性，使得短文本数据流分类面临着巨大挑战。已有的短文本数据流分类方法难以有效地解决特征高维稀疏问题，并且在处理海量数据流时时间代价较高。基于此，提出一种基于Spark的分布式快速短文本数据流分类方法。一方面，利用外部语料库构建Word2vec词向量模型解决了短文本的高维稀疏问题，并构建扩展词向量库以适应文本的快速可变性，提出一种LR分类器集成模型用于短文本数据流分类，该分类器使用一种FTRL方法实现模型参数的在线更新，并引入时间因子加权机制以适应概念漂移环境；另一方面，所提方法的使用分布式处理提高了海量短文本数据流的处理效率。在3个真实短文本数据流上的实验表明：所提方法在提高分类精度的同时，降低了时间消耗。     

An efficient discriminant-based solution for small sample size problem

Classification of high-dimensional statistical data is usually not amenable to standard pattern recognition techniques because of an underlying small sample size problem. To address the problem of high-dimensional data classification in the face of a limited number of samples, a novel principal component analysis (PCA) based feature extraction/classification scheme is proposed. The proposed method yields a piecewise linear feature subspace and is particularly well-suited to difficult recognition problems where achievable classification rates are intrinsically low. Such problems are often encountered in cases where classes are highly overlapped, or in cases where a prominent curvature in data renders a projection onto a single linear subspace inadequate. The proposed feature extraction/classification method uses class-dependent PCA in conjunction with linear discriminant feature extraction and performs well on a variety of real-world datasets, ranging from digit recognition to classification of high-dimensional bioinformatics and brain imaging data.     

基于自动子空间划分的高光谱数据特征提取

针对遥感高光谱图像数据量大、维数高的特点,提出了一种自动子空间划分方法用于高光谱图像数据量减小处理。该方法主要包括3个处理步骤:数据空间划分,子空间主成分分析和基于类别可分性准则的特征选择。该方法充分利用了高光谱图像各波段数据之间的局部相关性,将整个数据划分为若干个具有较强相关性的独立子空间,然后在子空间内利用主成分分析进行特征提取,根据各类地物间的类别可分性选择有效特征,最后利用地物分类来验证该方法的有效性。实验结果表明,该方法能够有效地实现高光谱图像数据维数减小和特征提取,同现有的自适应子空间分解方法和分段主成分变换方法相比,该方法所提取的特征用于分类时能获得较好的分类精度。利用该方法进行处理,当高光谱数据维数降低了90%时,9类地物分类实验的总体分类精度可以达到80.2%。     

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.