· 3202·
计 算 机 应 用 研 究
第 27 卷
则挖掘的方法必须适应其不断变化的数据分布， 否则容易引起 概念迁移问题
［7 ］
a） 界标模型。它是在整个数据流的历史时间域上某个称 之为界标的位置到当前这一时间跨度内挖掘所有的频繁项集 。 很多文献提出的算法是基于这一模型进行的
［8 ， 13 ］
由无限的事务块构成的序列 。图 1 为时间 的一个事务数据流， 窗口下的事务数据块。 其中每个元组块关联一个时间窗 口 ［ ak ， bk ］ ， 令 B 是最近的事务块。 每个事务块 B 是由一组事
k Bb T1 ， T2 ， …， T m］， 这里每个块的事务数不一 务构成的集合， ak =［ bn an bk ak
Review of association rules mining in data streams
ZHU Xiao-dong1 ，SHEN Guo-hua2
（ 1 ． Institute of Information Management ＆ Electronic Business，Management School，University of Shanghai for Science ＆ Technology，Shanghai 200093 ，China； 2 ． College of Information Science ＆ Technology，Nanjing University of Aeronautics ＆ Astronautics，Nanjing 210016 ，China）
［14 ， 15 ］
无限和资源有限的矛盾， 需要一种适应有限资源的挖掘机制， 如考虑内存空间消耗和能量消耗等， 否则挖掘结果的精度会 降低。
1
频繁项集挖掘算法
关联规则的挖掘分为两个关键步骤： 挖掘数据集上的频繁
。这一模型对新旧事务考
适用于老的事务对挖掘结果有影响 、 但是影响 虑不同的权值， 随着时间推移减小的应用领域 。 c） 滑动窗口模型。 它在滑动窗口上发现和维持 频 繁 项 集。当数据流入时， 只有滑动窗口中的一部分数据流被存储和 处理
Abstract ： Vast realtime high speed streams data generate upon many engineering fields． Compared with traditional static data ，streams data analysis faces great challenge in terms of resources． Association rules mining in data streams attract much attention due to its significant application in industries． This papr presented related formal definitions of association rules and the basic algorithm for association rules mining in data streams． Based on systematic investigation of association rules mining researches on streams data，analyzed issues and how they were resolved in current literatures． Also discussed the future directions in association rules mining． Key words： data mining； data streams； association rules； frequent itemsets； frequent patterns； knowledge discovery
静态数据相比， 流式数据上关联分析面临极大的资源挑战。提出了流式数据上关联规则的形式化定义和基本挖 掘算法， 系统地回顾了近年来流式数据上关联规则挖掘的研究进展， 详细分析了目前挖掘算法研究中存在的主 阐述了未来的研究方向。 要问题和解决途径， 关键词： 数据挖掘； 数据流； 关联规则； 频繁项集； 频繁模式； 知识发现 中图分类号： TP311 文献标志码： A 文章编号： 1001-3695 （ 2010 ） 09-3201-05 doi： 10． 3969 / j． issn． 1001-3695． 2010． 09． 001
第 27 卷第 9 期 2010 年 9 月
计 算 机 应 用 研 究 Application Research of Computers
Vol． 27 No． 9 Sep． 2010
流式数据上关联规则挖掘研究综述
1 2 朱小栋 ，沈国华
*
（ 1． 上海理工大学 管理学院 信息管理与电子商务研究所， 上海 200093 ； 2． 南京航空航天大学 信息科学与技术 学院，南京 210016 ） 摘 要： 当前许多工程领域产生大量高速实时的流式数据， 基于流式数据的关联规则挖掘应用广泛， 与传统的
0
引言
近年来， 数据流在金融、 股市、 电子商务网络交易、 无线传
而是 数据流处理的输入数据不是固定在磁盘或者存储器上的， 连续的、 大量的随机出现的数据流； b ） 数据流的大小是潜在的 无限大的， 相比大量的数据流来说， 主存或者磁盘空间的容量 太小， 不能作为数据流的存储器； c ） 数据流是不断出现的， 因 此要不断地对数据流挖掘的结果进行实时更新， 即提供连续的 这些项目序 结果； d） 不能控制数据流的项目序列到来的顺序， 列是以流的形式随机到来的 。 数据流的特征要求数据的分析处理是即时或在线的， 对数 据流的挖掘算法不能像传统数据挖掘那样可以多次扫描数据 库， 而且数据的存储方式也取代了原有的先存储到数据库中再 进行处理的方式， 而是要求在有限的内存空间内进行数据挖掘 基于传统数据的关联规则算法已不能 得到知识或规则。因此， 适应数据流。 总结流式数据关联规则挖掘面临的挑战如下： a ） 对于在 线数据流来说， 没有足够的空间来存储所有的流式数据， 压缩 存储空间对于关联规则挖掘来说是必要的； b ） 由于数据流连 续、 无边界、 高速的特征， 数据流上关联规则挖掘不允许重复扫 描整个数据库或者像传统数据挖掘算法那样只要有更新就可 以及计算机网络监视等许多领域中的广泛存在， 带来 数据流挖掘的研究热潮 。 不仅因为传统的静态数据挖掘技术 不能适应这种新的数据形式， 而且对数据流进行数据挖掘已成 为这些领域的迫切需要 。数据流里的数据称为流式数据， 是一 个随着时间推移不断出现的项目序列， 与传统的静态数据相 比， 数据流是连续、 潜在无边界的， 通常高速地出现。面向数据 流的数据采集与数据挖掘给计算机的存储空间 、 处理器、 能源 供应带来新的挑战。 关联规则分析是数据挖掘的核心课题， 起源于 20 世纪 90 年代
X 在时间窗口［a i ， b i］上是频繁项集， 当且仅当 Σ σ （ X ） ≥ s ×
t = ai i | Bb 数据流上频繁项集挖掘问题 a i | 。所以给定一个最小支持度，
bi
规约到使用尽可能少的时间和空间消耗来发现一定时间域上 所有的频繁项集。 定义 2 关联规则是形如 X→Y 的蕴涵表达式。 其中 X ∩ Y = 。关联规则的强度用支持度 s 和置信度 c 度量。
b 集， 则称事务 t i 包括项集 X。 事务块 B ak 上项集 X 的支持度计 k
的概念模型。 这三种数据处理模型有各自的应用领域和特点， 具体选择 哪一种数据处理模型主要根据应用的需要 。 同时它们之间可 如基于界标模型的算法可以通过对将要到来的数 以进行转换， 据流增加衰减函数转换到衰减模型， 也可以通过在一个特定的 滑动窗口上跟踪和处理数据转换到滑动窗口模型 。 1. 2 概要数据结构 在数据流处理中， 由于数据流的数据量远远大于可用的系 统内存， 系统无法在内存中保存所有遍历过的数据， 而与之矛 盾的是， 数据流查询与挖掘经常会要求读取这些数据 。为了避 数据流处理系统必须在内存维持一个 免代价昂贵的磁盘存取， 概要数据结构以保留遍历过的信息 。目前， 生成数据流概要数 据结构的主要技术包括采样 变换
［6 ］
与传统的静态数据不同， 数据流有许多新的特征： a ） 进行
收稿日期： 2010-03-21 ； 修回日期： 2010-05-12
基金项目： 上海理工大学博士科研启动经费资助项目（ 1D-10-303-002 ） ； 上海市第三期
本科教育高地建设资助项目 —上海理工大学电子商务交易教育高地子课题； 国家自然科学基金资助项目（ 70973079 ） 作者简介： 朱小栋（ 1981-） ， 男， 安徽太湖人， 博士， 主要研究方向为数据工程与知识工程、 流式数据管理（ zhuxd@ usst． edu． cn ） ； 沈国华（ 1976-） ， 男， 副教授， 博士， 主要研究方向为数据仓库 、 语义 Web 等．
［1 ］
， 与基于统计回归等数学分析方法不同， 关联规则的发
［2 ］
现显得隐蔽而难以发现 。 基于数据流的关联规则挖掘可应用 到估计传感器网络中丢失的数据 繁模式
［3 ］
、 评估互联网数据包的频
［5 ］
、 监视制造业数据流 。
［4 ］
、 发现数据流中的异常事件
等。基于 Web 日志数据流关联规则挖掘可预测失效或产生错 误报告
定。挖掘的结果则依赖于数据流在滑动窗口跨度内最近产生 的数据。在滑动窗口中所有的事务需要维护， 在其超出滑动窗 口的范围 后 要 消 除 它 们 在 当 前 挖 掘 结 果 上 的 影 响 。 Zhu 等 人
［17 ］
在滑动窗口模型的基础上提出了提取流式数据关联规则
i2 ， …， i d ｝ 是事务数据流中单个项的集合， 定相等。令 I = ｛ i1 ， 每个事务 T i 包含的项集是 I 的子集。包括一个以上项的集合 如果一个项集包含 k 个项， 则称它为 k项集。 事务 称为项集， 的宽度是事务 t i 中出现项的个数， 如果项集 X 是事务 t i 的子