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

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

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

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

AdBagging:自适应抽样参数在线装袋算法

通过对数据流分类中的概念漂移问题的研究,提出了一种在线装袋(Online Bagging)算法的改进算法——自适应抽样参数的在线装袋算法AdBagging(adaptive lambda bagging)。利用在分类过程中出现的误分样本数量来调整Online Bagging算法中的泊松(Poisson)分布的抽样参数,从而可以动态调整新样本在学习器中的权重,即对于数据流中的误分类样本给予较高的学习权重因子,而对于正确分类的样本给予较低的学习权重因子,同时结合样本出现的时间顺序调整权重因子,使得集成分类器可以动态调整其多样性(adversity)。该算法具有OnlineBagging算法的高效简洁优点,并能解决数据流中具有概念漂移的问题,人工数据集和实际数据集上的实验结果表明了该算法的有效性。     

SWFPM:一种有效的数据流频繁项挖掘算法*

分析了数据流频繁项挖掘算法EC的不足之处,如不能准确地挖掘最近一段时间内数据流的频繁项。提出了一种频繁项样本特征复合四元组的数据结构来保存样本集合,在此基础上,提出了一种基于滑动窗口的数据流频繁项挖掘算法——SWFPM。该算法能准确地挖掘出该滑动窗口中的频繁项。实验数据采用IBM合成数据发生器产生的顾客购物数据和1998年世界杯官方网站的访问日志数据。实验结果表明,该算法具有很高的频繁项挖掘准确度、快速的数据处理能力。     

基于主动学习的模式类别挖掘模型

在实际应用问题中,由于客观世界物质的多样性、模糊性和复杂性,经常会遇到大量未知样本类别信息的数据挖掘问题,而传统方法往往都依赖于已知样本类别信息才能对数据进行有效挖掘,对于未知模式类别信息的多类数据目前还没有有效的处理方法.针对未知类别信息的多类样本挖掘问题,提出了一种基于主动学习的模式类别挖掘模型(pattern class mining model based on active learning,PM_AL)来解决未知类别信息的模式类别挖掘问题.该模型通过衡量已得到的模式类别与未标记样本间的关系,引入样本差异度的方法来抽取最有价值样本,通过主动学习方式以较小的标记代价快速挖掘无标记样本所蕴含的可能模式类别,从而有助于将无类别标记的多分类问题转化成有类别标记的多分类问题.实验结果表明,PM_AL算法能够以较小的标记代价处理无类别信息的模式类别挖掘问题.     

低代价的数据流分类算法

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

基于动态特征提取和神经网络的数据流分类研究

为提高数据流分类的精确性和适应性,提出了一种新的数据流分类方法。该方法基于总体最小二乘法对数据流进行分段拟合,并将传统曲线分析算法——滑动窗口(SW)和在线数据分割(OSD)进行结合、改进,以可变滑动窗口算法实现对数据流的合理分割,提高趋势分析精度。在此基础上,对数据流进行动态特征提取和判断,并以神经网络对数据流特征进行模式识别,精确分类,进而对监控对象提供早期预警、状态评估和决策支持。实验结果表明,该方法能对数据流进行有效的动态特征描述,分类效果明显。     

基于概念漂移检测的网络数据流分类

互联网环境日新月异,使得网络数据流中存在概念漂移,对数据流的分类也由传统的静态分类变为动态分类,而如何对概念漂移进行检测是动态分类的关键。本文提出一种基于概念漂移检测的网络数据流自适应分类算法,通过比较滑动窗口中数据与历史数据的分布差异来检测概念漂移,然后将窗口中数据过采样来减少样本间的不均衡性,最后将处理后的数据集输入到OS-ELM分类器中进行在线学习,从而更新分类器使其应对数据流中的概念漂移。本文在MOA实验平台中使用合成数据集和真实数据集对提出的算法进行验证,结果表明,该算法较集成学习算法在分类准确率和稳定性上有一定的提升,并且随着数据流量的增加,时间性能上的优势开始体现,适合复杂多变的网络环境。     

对数据流频繁项集挖掘算法WSW-Imp的改进

近年来随着新的应用的出现,比如网络流量分析、在线事物分析和网络欺诈检测等,对数据流的挖掘成了一个越来越重要的课题。对于数据流频繁项集的挖掘,目前绝大部分的研究都集中在传统的窗口模式下进行,即时间衰退窗口模式、界标窗口模式和滑动窗口模式。Pauray S.M.Tsai于2009年提出了一种新的窗口模式：加权滑动窗口模式,并设计了两个基于此窗口模式的数据流频繁项集挖掘算法WSW和WSW-Imp,其中WSW-Imp是对WSW算法的改进。在研究了加权滑动窗口模式以及WSW-Imp算法的基础上,对WSW-Imp算法作了进一步的改进,设计了算法WSW-Imp2,并从理论上证明了WSW-Imp2算法比WSW-Imp算法更高效,实验结果也表明了这一点。     

融合SLDA主题模型的不均衡文本分类方法

在标签均衡分布且标注样本足够多的数据集上,监督式分类算法通常可以取得比较好的分类效果。然而,在实际应用中样本的标签分布通常是不均衡的,分类算法的分类性能就变得比较差。为此,结合SLDA（Supervised LDA）有监督主题模型,提出一种不均衡文本分类新算法ITC-SLDA（Imbalanced Text Categorization based on Supervised LDA）。基于SLDA主题模型,建立主题与稀少类别之间的精确映射,以提高少数类的分类精度。利用SLDA模型对未标注样本进行标注,提出一种新的未标注样本的置信度计算方法,以及类别约束的采样策略,旨在有效采样未标注样本,最终降低不均衡文本的倾斜度,提升不均衡文本的分类性能。实验结果表明,所提方法能明显提高不均衡文本分类任务中的Macro-F1和G-mean值。     

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

概念漂移是数据流学习领域中的一个难点问题,同时数据流中存在的类不平衡问题也会严重影响算法的分类性能。针对概念漂移和类不平衡的联合问题,在基于数据块集成的方法上引入在线更新机制,结合重采样和遗忘机制提出了一种增量加权集成的不平衡数据流分类方法(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在安卓应用检测问题上表现良好。     

Mining frequent itemsets in data streams using the weighted sliding window model

In recent years, data stream mining has become an important research topic. With the emergence of new applications, the data we process are not again static, but the continuous dynamic data stream. Examples include network traffic analysis, Web click stream mining, network intrusion detection, and on-line transaction analysis. In this paper, we propose a new framework for data stream mining, called the weighted sliding window model. The proposed model allows the user to specify the number of windows for mining, the size of a window, and the weight for each window. Thus users can specify a higher weight to a more significant data section, which will make the mining result closer to user’s requirements. Based on the weighted sliding window model, we propose a single pass algorithm, called WSW, to efficiently discover all the frequent itemsets from data streams. By analyzing data characteristics, an improved algorithm, called WSW-Imp, is developed to further reduce the time of deciding whether a candidate itemset is frequent or not. Empirical results show that WSW-Imp outperforms WSW under the weighted sliding window model.     

基于倾斜时间窗口的高效数据流偏向最近聚类分析算法

提出一种基于倾斜时间窗口的数据流偏向最近聚类算法。该算法首先通过将滑动窗口中数据等长分割形成不重叠的数据块——基本窗口,然后对每一基本窗口以Haar小波变换提取窗口数据的特征,通过改变所取各基本窗口小波变换系数个数达到保留较多最近数据细节特征的目的,即对于越近的基本窗口保留越多的小波系数而越旧的基本窗口保留越少的小波系数,最后通过定义数据流偏向最近距离,完成基于倾斜时间窗口的偏向最近聚类算法。该算法计算速度快,能高效地实现数据流偏向最近聚类分析。仿真实验验证了该算法的有效性。     

基于深度LightGBM集成学习模型的谷歌商店顾客购买力预测

针对轻量化梯度促进机（LightGBM）等集成学习模型只对数据信息进行一次挖掘,无法自动地细化数据挖掘粒度或通过深入挖掘得到更多的数据中潜在内部关联信息的问题,提出了深度LightGBM集成学习模型,该模型由滑动窗口和加深两部分组成。首先,通过滑动窗口使得集成学习模型能够自动地细化数据挖掘粒度,从而更加深入地挖掘数据中潜在的内部关联信息,同时赋予模型一定的表示学习能力。然后,基于滑动窗口,用加深步骤进一步地提升模型的表示学习能力。最后,结合特征工程对数据集进行处理。在谷歌商店数据集上进行的实验结果表明,所提深度集成学习模型相较原始集成学习模型的预测精度高出6.16个百分点。所提方法能够自动地细化数据挖掘粒度,从而获取更多数据集中的潜在信息,并且深度LightGBM集成学习模型与传统深度神经网络相比是非神经网络的深度模型,参数更少,可解释性更强。     

基于AO算法的数据流频繁项集挖掘

In view of a series of problems existing in support update, window update mode and frequent k-itemset mining of traditional frequent itemset mining algorithm in data flow, which results in low efficiency of space and time,an efficient AO algorithm for mining frequent itemsets in data streams is improved. The algorithm uses the idea of sliding window to mine the data stream in blocks; when there is new data flowing in the full window, the residual insertion is used to update the data; and operation is used to solve the support degree of frequent k-itemsets, and the superset detection is combined in the mining process, which greatly improves the mining efficiency.The experimental results show that the algorithm has good superiority in both time and space efficiency.     

挖掘滑动窗口中的数据流频繁项算法

滑动窗口是一种对最近一段时间内的数据进行挖掘的有效的技术,本文提出一种基于滑动窗口的流数据频繁项挖掘算法.算法采用了链表队列策略大大简化了算法,提高了挖掘的效率.对于给定的阈值S、误差ε和窗口长度n,算法可以检测在窗口内频度超过Sn的数据流频繁项,且使误差在εn以内.算法的空间复杂度为O(ε-1),对每个数据项的处理和查询时间均为O(1).在此基础上,我们还将该算法进行了扩展,可以通过参数的变化得到不同的流数据频繁项挖掘算法,使得算法的时间和空间复杂度之间得到调节.通过大量的实验证明,本文算法比其它类似算法具有更好的精度以及时间和空间效率.     

基于衰减滑动窗口数据流聚类算法研究

数据流具有数据流量大、流量连续且快速、难以存储和恢复等特性,其挖掘质量和效率是检验挖掘算法的重要标准.传统的数据流聚类挖掘算法是基于界标窗口、滑动窗口和衰减窗口模型,其算法的聚类质量较差,时间复杂度高等不足,就此类问题,研究一种滑动衰减窗口的数据流聚类算法,并对算法进行了设计与实现,有效的改善传统数据流算法聚类质量和时间效率的问题.仿真实验结果表明了该算法的有效性,达到了较满意的效果.     

一种基于滑动窗口的数据流频繁闭项集挖掘算法

频繁项集挖掘是数据流挖掘中的一个热点问题.提出了一种新的数据流频繁闭项集挖掘算法MFCI-SW.首先设计了两个新的数据结构:频繁闭项集表FCIL和频繁闭合模式树MFCI-SW-Tree,在此基础上以滑动窗口中的基本窗口为更新单位,在每个基本窗口中提取出频繁闭项集的数据项,将其支持度F和窗口序列号K存到FCIL中;然后随着新基本窗口的到来,通过删除频繁闭项集表中K值最小的数据项和插入新数据项完成对FCIL的更新和MFCI-SW-Tree树的裁剪;最后在MFCI-SW-Tree中可以迅速挖掘出满足用户需要的频繁闭项集.实验结果证明了该算法在执行效率上明显优于DS-CFI算法.     

基于距离的数据流离群点挖掘算法

传统的离群点挖掘算法无法有效挖掘数据流中的离群点。针对数据流的无限输入和动态变化等特点,提出一种新的基于距离的数据流离群点挖掘算法。通过Hoeffding定理及独立同分布中心极限定理,对数据流概率分布变化进行动态检测,利用检测结果自适应调整滑动窗口大小对数据流离群点进行挖掘。实验结果表明,该算法在人工数据集和真实数据集KDD-CUP99中可以对数据流中的离群点进行有效挖掘。