数据流频繁模式挖掘综述

一些先进应用如欺诈检测和趋势学习等带来了数据流频繁模式挖掘的发展。不同于静态数据,数据流挖掘面临着时空约束和项集组合爆炸等问题。对已有数据流频繁模式挖掘算法进行综述并对经典和最新算法进行分析。按照模式集合的完整程度进行分类,数据流中频繁模式分为全集模式和压缩模式。压缩模式主要包括闭合模式、最大模式、top-k模式以及三者的组合模式。不同之处是闭合模式是无损压缩的,而其他模式是有损压缩的。为了得到有趣的频繁模式,可以挖掘基于用户约束的模式。为了处理数据流中的新近事务,将算法分为基于窗口模型和基于衰减模型的方法。数据流中模式挖掘常见的还包含序列模式和高效用模式,对经典和最新算法进行介绍。最后给出了数据流模式挖掘的下一步工作。     

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

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

基于时间衰减模型的数据流频繁模式挖掘

频繁模式挖掘是数据流挖掘中的重要研究课题. 针对数据流的时效性和流中心的偏移性特点, 提出了界标窗口模型与时间衰减模型相结合的数据流频繁模式挖掘算法. 该算法通过动态构建全局模式树, 利用时间指数衰减函数对模式树中各模式的支持数进行统计, 以此刻画界标窗口内模式的频繁程度; 进而, 为有效降低空间开销, 设计了剪枝阈值函数, 用于对预期难以成长为频繁的模式及时从全局树中剪除. 本文对出现在算法中的重要参数和阈值进行了深入分析. 一系列实验表明, 与现有同类算法MSW相比, 该算法挖掘精度高(平均超过90%), 内存开销小, 速度上可以满足高速数据流的处理要求, 且可以适应不同事务数量、不同事务平均长度和不同最大潜在频繁模式平均长度的数据流频繁模式挖掘.     

基于滑动窗口模型的数据流闭合高效用项集挖掘

从数据流中挖掘高效用项集是一项具有挑战性的任务,因为传入的数据必须在时间和存储内存约束下进行实时处理数据流挖掘通常会产生大量冗余的项集,为了减少这些无用的项集数量且保证无损压缩,需要挖掘闭合项集,它可以比全集高效用项集的集合小几个数量级.为了解决以上问题,提出一种基于滑动窗口模型的数据流闭合高效用项集挖掘(closed high utility itemsets mining over data stream based on sliding window model,CHUI_DS)算法.在 CHUI DS 中设计了 一种新的效用列表结构,该结构在提升批次插入和删除的速度方面非常有效此外,应用修剪策略来改进闭合项集挖掘过程,消除潜在的低效用候选对象.对真实数据集和合成数据集进行的广泛实验评估显示了该算法的效率以及可行性就速度而言,它优于先前提出的主要以批处理模式运行的算法.且它适用于不同大小的滑动窗口,在事务数量等方面具有较强的扩展性.     

挖掘数据流任意滑动时间窗口内频繁模式

由于数据流的流动性与连续性,数据流所蕴含的知识会随着时间的推移而发生变化.因此,在绝大多数数据流的应用中,用户往往对新产生的流数据所包含的知识要比对历史流数据所包含的知识感兴趣得多.提出了一种挖掘数据流任意大小滑动时间窗口内频繁模式的方法MSW(mining sliding window).当数据流流过时,该方法使用滑动窗口树SW-tree在单遍扫描流数据的条件下及时捕获数据流上最新的模式信息.同时,该方法还周期性地删除滑动窗口树上过期的及不频繁的模式分支,从而降低滑动窗口树的空间复杂度与维护代价.此外,该方法还应用时间衰减模型逐步降低历史事务模式支持数的权重,并由此来区分最近产生事务与历史事务的模式.大量仿真实验的结果表明,算法MSS具有较高的效率与优良的可扩展性,同时也优于其他同类算法.     

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

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

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

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

数据流高效用模式挖掘综述

数据流高效用模式挖掘方法是以二进制的频繁模式挖掘方法为前提,引入项的内部效用和外部效用,在模式挖掘过程中可以考虑项的重要性,从而挖掘更有价值的模式。从关键窗口技术、常用方法、表示形式等角度对数据流高效用模式挖掘方法进行分析并总结其相关算法,从而研究其特点、优势、劣势以及其关键问题所在。具体来说,说明了数据流高效用模式常用的概念;对处理数据流高效用模式的关键窗口技术进行了分析,涉及到滑动、衰减、界标和倾斜窗口模型;研究了一阶段和两阶段的数据流高效用模式挖掘方法;分析了高效用模式的表示形式,即完全高效用模式和压缩高效用模式;介绍了其他的数据流高效用模式,包括序列高效用模式、混合高效用模式以及高平均效用模式等;最后展望了数据流高效用模式挖掘的进一步研究方向。     

挖掘滑动窗口中的数据流频繁模式

随着数据流应用的不断增多,数据流环境下的数据挖掘技术受到了越来越多的关注.文章结合数据流的特点,提出一种新的基于滑动窗口的频繁模式挖掘算法:DSFPM.算法分块挖掘数据流,在内存中维持一个用于保存所有潜在的频繁模式信息的存储结构DSFPM-Tree,并在各个基本窗口进入滑动窗口后动态更新该存储结构.算法仅处理和保存各个基本窗口的临界频繁闭合项集,极大地提高了时间和空间效率.实验结果表明,该算法具有良好的性能.     

挖掘数据流滑动时间窗口内Top-K频繁模式

由于数据流滑动时间窗口中流数据包含模式的支持度是动态变化的,很难给出一个合适的支持度门限来挖掘数据流滑动时间窗口内的频繁模式.在研究数据流滑动时间窗口内流数据变化特点的基础上,论文提出了一种挖掘数据流滑动时间窗口内Top-k频繁模式的方法,该方法能够在保证模式挖掘误差基础上快速删除窗口内不频繁模式信息,保留重要的模式信息,并能按照支持度降序输出Top-k频繁模式.仿真实验结果表明,该算法具有较好的效率和正确性,并优于其它同类算法.     

数据流模式依赖挖掘及应用

针对数据流间“模式依赖”问题，给出了一种模式依赖挖掘算法，该算法包括：挖掘前时间序列分段和模式表示，条件规则元组的创建和维护，模式依赖的置信度和支持度计算，2个或N个数据流概要结构的设计等。股票数据实验和实际系统表明，该挖掘方法能够有效地发现数据流间的模式依赖，可用于预测。     

基于显露模式的数据流贝叶斯分类算法

基于模式的贝叶斯分类模型是解决数据挖掘领域分类问题的一种有效方法.然而,大多数基于模式的贝叶斯分类器只考虑模式在目标类数据集中的支持度,而忽略了模式在对立类数据集合中的支持度.此外,对于高速动态变化的无限数据流环境,在静态数据集下的基于模式的贝叶斯分类器就不能适用.为了解决这些问题,提出了基于显露模式的数据流贝叶斯分类模型EPDS（Bayesian classifier algorithm based on emerging pattern for data stream）.该模型使用一个简单的混合森林结构来维护内存中事务的项集,并采用一种快速的模式抽取机制来提高算法速度.EPDS采用半懒惰式学习策略持续更新显露模式,并为待分类事务在每个类下建立局部分类模型.大量实验结果表明,该算法比其他数据流分类模型有较高的准确度.     

数据流挖掘算法研究综述

流数据挖掘是数据挖掘的一个新的研究方向,已逐渐成为许多领域的有用工具。在介绍数据流的基本特点以及数据流挖掘的意义的基础上,对现有数据流挖掘算法的主要思想方法进行了总结,并指出了这些方法的局限性。最后对数据流挖掘的发展方向进行了展望。     

数据流中一种快速启发式频繁模式挖掘方法

在现有的数据流频繁模式挖掘算法中,批处理方法平均处理时间短,但需要积攒足够的数据,使得其实时性差且查询粒度粗;而启发式方法可以直接处理数据流,但处理速度慢.提出一种改进的字典树结构--IL-TREE(improved lexicographic tree),并在其基础上提出一种新的启发式算法FPIL-Stream(frequent pattem mining based on improved lexicographic tree),在更新模式和生成新模式的过程中,可以快速定位历史模式.算法结合了倾斜窗口策略,可以详细记录历史信息.该算法在及时处理数据流的前提下,也降低了数据的平均处理时间,并且提供了更细的查询粒度.     

基于概率衰减窗口模型的不确定数据流频繁模式挖掘

考虑到不确定数据流的不确定性,设计了一种新的概率频繁模式树PFP-tree和基于该树的概率频繁模式挖掘方法PFP-growth.PFP-growth使用事务性不确定数据流及概率衰减窗口模型,通过计算各概率数据项的期望支持度以发现概率频繁模式,其主要特点有:考虑到窗口内不同时间到达数据项的贡献度不同,采用概率衰减窗口模型计算期望支持度,以提高模式挖掘准确度;设置数据项索引表和事务索引表,以加快频繁模式树检索速度;通过剪枝删除不可能成为频繁模式的结点,以降低模式树的存储及检索开销;对每个结点都设立一个事务概率信息链表,以支持数据项在不同事务中具有不同概率的情形.实验结果表明,PFP-growth在保证挖掘模式准确度的前提下,在处理时间和内存空间等方面都具有较好的性能.     

数据流挖掘研究

上世纪末,为适应网络监控、入侵检测、情报分析、商业交易管理和分析等应用的要求,数据流技术应运而生。数据流独特的特点,对传统数据的处理方法带来了很大的挑战。介绍了数据流的有关概念及数据流挖掘的特点,讨论了数据流挖掘的研究现状。最后,举例说明了数据流挖掘的应用,并展望了数据流挖掘未来的研究方向。     

高效用模式挖掘关键技术综述

通过分析有关高效用模式挖掘(high utility pattern mining,HUPM)最先进的方法,对其进行全面和结构化的概述。首先,通过介绍HUPM的相关概念、公式并给出应用示例,对HUPM有更深一步的理解;针对用于挖掘不同类型HUPM的最常见和最先进的关键技术进行分类,包括基于Apriori、基于树、基于列表、基于映射、基于垂直/水平数据格式、基于索引等方法。针对现有关键技术的用途和优缺点进行了全面概述,由于静态数据难以满足实际需要,总结了在数据流上应用的HUPM方法,主要包括基于增量方法、基于滑动窗口模型方法、基于时间衰减模型方法、基于地标模型方法等。最后,给出了现有技术的不足和改进方向,并且有针对性地提出了新的研究方法。     

数据流挖掘研究

上世纪末，为适应网络监控、入侵检测、情报分析、商业交易管理和分析等应用的要求，数据流技术应运而生。数据流独特的特点，对传统数据的处理方法带来了很大的挑战。介绍了数据流的有关概念及数据流挖掘的特点，讨论了数据流挖掘的研究现状。最后，举例说明了数据流挖掘的应用，并展望了数据流挖掘未来的研究方向。