分布式数据流挖掘技术综述

网络信息技术的高速发展产生了新的数据模型,即数据流模型,并且越来越多的领域出现了对数据流实时处理的需求,庞大且高速的数据以及应用场景的实时性需求均推进了数据流挖掘技术的发展。首先介绍了常见的数据流模型;然后根据数据流模型的特点总结数据流挖掘的支撑技术;最后,分析了分布式数据流挖掘的重要性和有效性,给出了算法并行化的数学模型,并介绍了几种具有代表性的分布式数据流处理系统。     

分布式数据流挖掘的研究进展

随着通信技术和硬件设备的不断发展,尤其是小型无线传感设备的广泛应用,数据采集和生成技术变得越来越便捷和趋于自动化,研究人员正面临着如何管理和分析大规模动态数据集的问题。能够产生数据流的领域应用已经非常普通,例如传感器网络、金融证券管理、网络监控、Web日志以及通信数据在线分析等新型应用。这些应用的特征是环境配备有多个分布式计算节点;这些节点往往临近于数据源;分析和监控这种环境下的数据,往往需要对挖掘任务、数据分布、数据流入速率和挖掘方法有一定的了解。综述了分布式数据流挖掘的当前进展概况,并展望了未来可能的、潜在的专题研究方向。     

挖掘数据流最近时间窗口内频繁模式

由于流数据的流动性与连续性,传统的频繁模式挖掘算法不能直接应用于数据流频繁模式挖掘.挖掘数据流上最近的频繁模式算法使用模式树RFP-tree增量维护数据流上最近的频繁模式,且仅需单次扫描流数据;另外,保守计算策略保证模式挖掘的正确性.仿真试验结果显示,该算法的效率优于其它同类算法.     

MARSW:一种高效的基于滑动窗口数据流关联规则挖掘方法

数据流中的关联规则在预测和在线分析系统中有重要应用.现有的研究大多集中在事务数据模型上,鲜有对数据项之间的关联规则挖掘.由于数据的实时性特点,用户又往往对新产生的数据所包含的信息更感兴趣.为了实时而准确地挖掘最近一段时间内数据项间的关联规则,提出了MARSW(mining association rules on sliding window)算法,利用滑动窗口模型对数据流进行关联规则挖掘.MARSW算法在给定的误差范围内,能够有效去除历史数据的影响,并以有限的空间代价快速挖掘大量数据间存在的关联规则.大量仿真实验结果表明,MARSW算法具有较高的效率和优良的可扩展性.     

数据流频繁模式挖掘算法设计

介绍了数据流频繁模式的概念和定义,提出了数据流频繁模式挖掘算法的通用数据流处理模型,详细总结了数据流频繁模式挖掘算法的三种分类方式:"窗口模型"、"结果集类型"和"结果集精确性".基于这些分类方法提出了数据流频繁模式挖掘算法的设计立方体,该立方体不仅涵盖了现有的数据流频繁模式挖掘算法,还对设计新的算法具有指导意义.基于设计立方体,分析了设计算法时应当采取的有效策略,旨在为设计新算法提供一个有力参考.最后讨论了数据流频繁模式挖掘的进一步研究工作.     

一种基于时间衰减模型的数据流闭合模式挖掘方法

数据流是随着时间顺序快速变化的和连续的,对其进行频繁模式挖掘时会出现概念漂移现象。在一些数据流应用中,通常认为最新的数据具有最大的价值。数据流挖掘会产生大量无用的模式,为了减少无用模式且保证无损压缩,需要挖掘闭合模式。因此,提出了一种基于时间衰减模型和闭合算子的数据流闭合模式挖掘方式TDMCS （Time-Decay-Model-based Closed frequent pattern mining on data Stream）。该算法采用时间衰减模型来区分滑动窗口内的历史和新近事务权重,使用闭合算子提高闭合模式挖掘的效率,设计使用最小支持度-最大误差率-衰减因子的三层架构避免概念漂移,设计一种均值衰减因子平衡算法的高查全率和高查准率。实验分析表明该算法适用于挖掘高密度、长模式的数据流;且具有较高的效率,在不同大小的滑动窗口条件下性能表现是稳态的,同时也优于其他同类算法。     

数据流挖掘分类技术综述

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

流数据中一种高效剪枝的频繁序列挖掘算法

序列模式挖掘就是在时序数据库中挖掘相对时间或其他模式出现频率高的模式.序列模式发现是最重要的数据挖掘任务之一,并有着广阔的应用前景.针对静态数据库,序列模式挖掘已经被深入的研究.近年来,出现了一种新的数据形式:数据流.针对基于数据流的序列模式挖掘的研究还不是十分深入.提出一个有效的基于数据流的挖掘频繁序列模式的算法SSPM,利用到2个数据结构(F-list和Tatree)来处理基于数据流的序列模式挖掘的复杂性问题.SSPM的优点是可以最大限度地降低负正例的产生,实验表明SSPM具有较高的准确率.     

数据流频繁模式挖掘综述

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

数据流聚类算法研究

许多应用程序会产生大量的流数据,如网络流、web点击流、视频流、事件流和语义概念流。数据流挖掘已成为热点问题,其目标是从连续不断的流数据中提取隐藏的知识/模式。聚类作为数据流挖掘领域的一个重要问题,在近期被广泛研究。不同于传统的静态数据聚类问题,数据流聚类面临有限内存、一遍扫描、实时响应和概念漂移等许多约束。本文对数据流挖掘中的各种聚类算法进行了总结。首先介绍了数据流挖掘的约束;随后给出了数据流聚类的一般模型,并描述了其与传统数据聚类之间的关联;最后提出数据流聚类领域中进一步的研究热点和研究方向。     

挖掘数据流频繁模式的相关技术和算法研究综述

数据流本身的特点使得静态挖掘方法不再满足要求。国内外学者已提出许多新的挖掘数据流频繁模式的方法和技术。对这些技术和算法进行了综述。首先介绍数据流的概念和特点,分析国内外的研究现状,总结了数据流中挖掘频繁模式的特点,并列出挖掘方法的常用技术和基于这些技术的代表性算法,最后讨论了将来的研究方向。     

流数据挖掘综述

作为一种新的数据形态，流数据对数据挖掘提出了诸多挑战。学者们已提出大量处理流数据的挖掘算法。本文对这些算法进行了综述。首先介绍了多个不同的数据流模型，这些模型对算法设计有着不同的要求。然后，总结了流数据挖掘算法的特点，并给出了算法中常用的技术。最后，分析了各个流数据挖掘任务中的代表性算法。     

挖掘数据流界标窗口Top-K频繁项集

数据流频繁项集挖掘是目前数据挖掘与知识发现领域的热点研究课题,在许多领域有重要应用.然而支持度阈值的设定需要一定的领域知识,设置不当会给后续的分析处理带来很多困难和不必要的负担,因此挖掘数据流top-K频繁项集有重要意义.提出一个挖掘数据流界标窗口top-K频繁项集的动态增量近似算法TOPSIL-Miner,为此设计了存储流数据摘要信息的概要结构TOPSIL-Tree以及动态记录挖掘相关信息的树层最大支持度表MaxSL、项目序表OIL,TOPSET和最小支持度表MinSL等,并分析了与这些概要结构相关的挖掘特性.在此基础上研究算法的3种优化措施:1)剪枝当前数据流的平凡项集;2)挖掘过程中启发式自适应提升挖掘阈值;3)动态提升剪枝阈值.对算法的误差上界进行了分析研究.最后通过实验验证了算法的可行性、精确性和时空高效性.     

数据流中基于滑动窗口的序列模式挖掘算法

序列模式发现是最重要的数据挖掘任务之一,并有着广阔的应用前景。针对静态数据库,序列模式挖掘已经被深入地研究,但针对基于数据流的序列模式挖掘的研究还不是十分深入。数据流有着无限性的特性,因此往往不能保存数据流中全部的数据,同时很多时候只对最近的时间段的序列模式感兴趣,提出一个有效的结合滑动窗口技术的挖掘序列模式的算法FPM-SW,算法利用到3个数据结构（PatternTable,CountTable和Ta-tree）来处理基于数据流的序列模式挖掘的复杂性问题。算法通过CountTable结构来保存以往的潜在频繁序列,考虑到在某些情况下CountTable占用内存过多,算法还结合了一种压缩CountTable技术来减少内存占用。FPM-SW的优点是可以最大限度地降低负正例的产生,实验表明FPM-SW具有较高的准确率。     

A survey on algorithms for mining frequent itemsets over data streams

The increasing prominence of data streams arising in a wide range of advanced applications such as fraud detection and trend learning has led to the study of online mining of frequent itemsets (FIs). Unlike mining static databases, mining data streams poses many new challenges. In addition to the one-scan nature, the unbounded memory requirement and the high data arrival rate of data streams, the combinatorial explosion of itemsets exacerbates the mining task. The high complexity of the FI mining problem hinders the application of the stream mining techniques. We recognize that a critical review of existing techniques is needed in order to design and develop efficient mining algorithms and data structures that are able to match the processing rate of the mining with the high arrival rate of data streams. Within a unifying set of notations and terminologies, we describe in this paper the efforts and main techniques for mining data streams and present a comprehensive survey of a number of the state-of-the-art algorithms on mining frequent itemsets over data streams. We classify the stream-mining techniques into two categories based on the window model that they adopt in order to provide insights into how and why the techniques are useful. Then, we further analyze the algorithms according to whether they are exact or approximate and, for approximate approaches, whether they are false-positive or false-negative. We also discuss various interesting issues, including the merits and limitations in existing research and substantive areas for future research.     

流式数据上关联规则挖掘研究综述*

当前许多工程领域产生大量高速实时的流式数据,基于流式数据的关联规则挖掘应用广泛,与传统的静态数据相比,流式数据上关联分析面临极大的资源挑战。提出了流式数据上关联规则的形式化定义和基本挖掘算法,系统地回顾了近年来流式数据上关联规则挖掘的研究进展,详细分析了目前挖掘算法研究中存在的主要问题和解决途径,阐述了未来的研究方向。     

差分隐私保护研究综述

差分隐私保护通过添加噪声使数据失真,从而起到保护隐私的目的,对于一个严格定义下的攻击模型,其具有添加噪声少、隐私泄露风险低的优点。介绍了差分隐私保护的理论基础和最新研究进展,详细阐述了分类、聚类等差分隐私学习方法的最新研究情况,介绍了一个差分隐私保护的应用框架PINQ(privacy integratedqueries),并对未来的研究发展方向进行了展望。     

一种支持多目标的数据流操作语言

随着数据流在各个应用领域的涌现和广泛应用，数据流相关的研究已经成为数据库技术中一个新的研究方向，并得到了越来越多的关注．数据流的操作语言作为用户与数据流管理系统之问进行语义交换的桥梁，从很大程度上体现出了数据流处理的特点．提出了一种数据流管理系统中支持多目标的数据流操作语言．它可以同时完成对数据流和关系表的操作．此外针对数据流的特性，语言中还引入了时间戳，时间粒度，连续查询，近似查询等相关概念，并以丰富灵活的语法支持了各种相关技术．     

Detection and removal of infrequent behavior from event streams of business processes

Process mining aims at gaining insights into business processes by analyzing the event data that is generated and recorded during process execution. The vast majority of existing process mining techniques works offline, i.e. using static, historical data, stored in event logs. Recently, the notion of online process mining has emerged, in which techniques are applied on live event streams, i.e. as the process executions unfold. Analyzing event streams allows us to gain instant insights into business processes. However, most online process mining techniques assume the input stream to be completely free of noise and other anomalous behavior. Hence, applying these techniques to real data leads to results of inferior quality. In this paper, we propose an event processor that enables us to filter out infrequent behavior from live event streams. Our experiments show that we are able to effectively filter out events from the input stream and, as such, improve online process mining results.     

TOPSIL-Miner: an efficient algorithm for mining top-K significant itemsets over data streams

Frequent itemset mining over data streams becomes a hot topic in data mining and knowledge discovery in recent years, and has been applied to different areas. However, the setting of a minimum support threshold needs some domain knowledge. It will bring a lot of difficulties or much burden to users if the support threshold is not set reasonably. It is interesting for users to find top-K frequent itemsets over data streams. In this paper, a dynamical incremental approximate algorithm TOPSIL-Miner is presented to mine top-K significant itemsets in landmark windows. A new data structure, TOPSIL-Tree, is designed to store the potential significant itemsets and other data structures of maximum support list, ordered item list, TOPSET and minimum support list are devised to maintain information about mining results. Moreover, three optimal strategies are exploited to reduce time and space cost of the algorithm: (1) pruning trivial nodes in the current data stream, (2) promoting mining support threshold during mining process adaptively and heuristically, and (3) promoting pruning threshold dynamically. The accuracy of the algorithm is also analyzed. Extensive experiments are performed to evaluate the good effectiveness and the high efficiency and precision of the algorithm.