数据流频繁模式挖掘综述

打开文本图片集

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

关键词：数据流; 数据流挖掘; 频繁模式挖掘; 序列模式挖掘; 高效用模式挖掘

中图分类号： TP18

文献标志码：A

文章编号：1001-9081（2019）03-0719-09

Abstract： Advanced applications such as fraud detection and trend learning lead to the development of frequent pattern mining over data streams. Data stream mining has to face more problems than static data mining like spatio-temporal constraint and combinatorial explosion of itemsets， which are different from static data mining. In the paper， the existing frequent pattern mining algorithms over data streams were reviewed， and some classical algorithms and some newest algorithms were analyzed. According to the completeness of pattern set， frequent patterns of data stream could be divided into complete patterns and compressed patterns. Compressed patterns include closed frequent patterns， maximal frequent patterns， top-k frequent patterns and combinations of them. Between them， only closed frequent patterns are losslessly compressed. And constrained frequent pattern mining was used to narrow the result set obtained， satisfying the user"s demand more. Algorithms based on sliding window model and time decay model were used to better handle recent transactions which occupy an important position in data stream mining. Moreover， two of the common algorithms， sequential pattern mining and high utility pattern mining algorithms were introduced. At last， further research direction of frequent pattern mining over data streams were discussed.

Key words： data stream; data stream mining; frequent pattern mining; sequential pattern mining; high utility pattern mining

0 引言

在一些新興的应用场景下，例如智能城市、大型基础设施监控、物联网等，数据产生的速度越来越快。数据流（data stream）被认为是高速率数据，通常被认为是大数据，它是无限的、快速的、变化的和有序的。在某些环境下，数据流的处理方法必须快速且能适应变化。数据流模型面临的主要约束[1]包括：

1）数据量巨大，可以认为是无限的。因此，无法存储所有的数据。合理的方法是存储数据的概要信息。

2）数据到达的速度快。因此，需要实时处理数据，且处理后数据即被丢弃。

3）数据项的分布可能随着时间而变化。因此，历史数据会变得无用甚至有害。

在进行数据流挖掘时，需要考虑这些约束。近年来，研究者关注数据流中分类、聚类以及模式挖掘等问题的研究。频繁模式是指在数据集中出现的次数高于用户定义的最小支持数/度阈值的项的集合。数据流频繁模式挖掘方法通常可以分为两类。第一类是基于统计来估计模式频度。如算法Sticky Sampling[2]采用统计抽样技术来估计项集的支持数。它是挖掘数据流频繁模式的近似算法，是基于概率统计的，丢失可能频繁模式的概率不高于用户定义的参数值。算法Lossy Counting[2]是数据流频繁模式挖掘经典方法之一，它给定了错误参数来挖掘数据流中的频繁模式。第二类是基于草图来近似估计模式频度。草图是一种概率数据结构，它用于处理项出现频度。最经典的算法是CountSketch[3]，它使用有限的存储空间来估计数据流中频繁项，主要依赖于草图数据结构。Pyramid框架[4]使用草图数据结构来发现数据流中频繁模式，该算法在算法正确率以及算法速度方面有一定的优势。