流数据挖掘综述孙玉芬.docx
《流数据挖掘综述孙玉芬.docx》由会员分享，可在线阅读，更多相关《流数据挖掘综述孙玉芬.docx（25页珍藏版）》请在冰点文库上搜索。
流数据挖掘综述孙玉芬
流数据挖掘综述＊）
孙玉芬 卢炎生
（华中科技大学计算机科学与技术学院 武汉430074）
在这3种模型中,Turnstile是最具一般性的数据流模
型,其适用范围最广,也最难处理。
流数据分类与聚类通常使
用的是时序模型,它们将数据流中的每个数据项看作一个独
立的对象。
若将A[j]记为信号j出现的次数,则流数据频繁
模式挖掘通常使用的是CashRegister模型,只允许数据的插
入。
也有算法研究了同时存在数据插入和删除时的流数据频
繁模式挖掘问题。
此时,算法应用的是数据流的Turnstile模
型。
由于数据流是一个长期、动态的过程,部分算法在处理数
据流时并不是将所有的数据流数据作为处理对象,而是根据
应用需求选取某个时间范围内的数据进行处理。
按算法处理
数据流时所选取的时序范围,数据流模型可分为以下几类[9]:
（1）快照模型（snapshotmodel）:
处理数据的范围限制在
两个预定义的时间戳之间。
（2）界标模型（landmarkmodel）:
处理数据的范围从某一
个已知的初始时间点到当前时间点为止。
（3）滑动窗口模型（slidingwindowmodel）:
处理数据的范
围由某个固定大小的滑动窗口确定,此滑动窗口的终点永远
为当前时刻。
其中,滑动窗口的大小可以由一个时间区间定
义,也可以由窗口所包含的数据项数目定义。
在这3种模型中,界标模型和滑动窗口模型是采用得比
较多的模型。
界标模型通常将数据流的起始点作为数据处理
的初始时间点。
此时,算法对数据流中所有数据进行处理,数
据流上只存在插入操作。
在滑动窗口模型中,窗口随着数据
的流入向前滑动,窗口中存在数据的插入和删除。
滑动窗口
模型非常适用于只要求对最近时间段内的数据进行处理的应
用。
3 流数据挖掘算法的特点
数据流实时、连续、有序、快速到达的特点以及在线分析
的应用需求,对流数据挖掘算法提出了诸多挑战。
数据流对
挖掘算法的典型要求如下:
（1）单次线性扫描。
即算法只能按数据的流入顺序依次
读取数据一次。
（2）低的时间复杂度。
流算法是在线算法,为了跟上数据
流的流速,算法处理每个数据项的时间不能太长,最好能为常
数时间。
（3）低的空间复杂度。
流算法是主存算法,其可用的空间
是有限的,算法的空间复杂度不能随数据量无限增长。
（4）能在理论上保证计算结果具有好的近似程度。
（5）能适应动态变化的数据与流速。
产生数据的现象可
能在不断变化,导致数据内容与流速的改变。
（6）能有效处理噪音与空值。
这是一个具有健壮的算法
所必须具有的能力。
（7）能作ondemand的挖掘。
即能响应用户在线提出的
任意时间段内的挖掘请求。
（8）能作anytime的回答。
即算法在任何时刻都能给出
当前数据的挖掘结果。
（9）建立的概要数据结构具有通用性。
算法所构建的概
要数据结构不仅能支持算法当前的目标计算,而且能支持其
他的计算。
在上述要求中,第1至3条是一个流数据挖掘算法所必
须满足的。
早期的流数据挖掘算法都是以这三项为目标设计
的,如文[10,11]。
对于算法的空间复杂度,理想的情况是它
与数据流长度N无关。
但是,目前大部分问题都无法找到这
样的解。
因此,这个要求就让步为找到空间复杂度为O（poly
（logN））的算法,即次线性算法。
算法的时间复杂度通常以
每个数据项到来时,更新概要数据结构或目标计算结果所需
要的时间来衡量,理想的情况是算法处理每个数据项的时间
为常数。
其中,概要数据结构是算法为支持目标计算而在内
存中保存的数据流数据的压缩信息。
对于构建概要数据结构
的算法,通常没有对在概要数据结构上计算目标函数所需要
的时间做严格的要求。
近似性与自适应性是数据流算法的两大特点[3]。
由于一
次线性扫描以及时间与空间的限制,数据流算法往往只能得
到对所处理的问题的近似计算结果。
能在理论上保证其计算
结果的近似程度,是算法应该考虑的一个问题。
算法的自适
应性是指当流数据内容或流速受各种因素的影响而发生改变
时,算法能够根据这些改变自动调整计算策略与计算结果。
噪音与空值是一个健壮的算法所必须解决的问题。
对于
流数据挖掘算法,这个问题显得更为突出。
这是因为在挖掘
数据库中的静态数据集之前,通常会进行数据的预处理,消除
数据中的噪音与空值。
而在在线进行的流数据挖掘过程中,
无法在挖掘前对数据进行预处理。
而且,数据流中的数据在
采集以及传输过程中,都可能出现错误,产生噪音或空值。
数
据流的动态变化性更进一步增加了噪音识别的困难。
当产生
数据流的现象发生改变时,新数据无法被现有数据模型所描
述,可能被误认为是噪音。
在一些应用中,用户可能在数据流流入过程中提出对某
个时间段内的数据进行挖掘的请求。
能回答这种请求的算法
被称为具有ondemand回答能力的算法。
算法通常采用多窗
口技术来近似解决这类问题。
能对挖掘请求给出anytime的
回答,指算法在任何时刻都能给出对当前数据最精确的计算
结果。
这要求算法每读取一个数据项,就更新处理结果。
有些算法构建的概要数据结构只能用来支持算法的目标
计算,如文[12]中为计算数据流对之间的滞后关联而保留的
统计量。
有的概要数据结构是对数据流数据一般性的压缩,
还可用来支持其他计算,如文[13]中保留的多个基本窗口内
数据的傅立叶变换系数。
这样的概要数据结构显然比只能支
持当前计算的概要数据结构更为有用。
4 相关技术
基于对多个流数据挖掘算法的分析,我们总结了算法常
用的一些技术。
这些技术主要包括概要数据结构、滑动窗口
技术、多窗口技术、衰减因子、近似技术等。
4.1 概要数据结构
在流数据处理系统中,由于数据量远大于可用内存,系统
无法在内存中保存所有扫描过的数据,而流数据查询与挖掘
经常会要求读取这些数据。
为了避免代价昂贵的磁盘存取,
流数据处理系统必须在内存维持一个概要数据结构,以保留
扫描过的信息。
文[9]已对建立概要数据结构的方法作了综
述,本文在这里只作一个简单的介绍。
目前,生成数据流概要数据结构的主要方法包括取样
（sampling）、直方图（histogram）、小波变换、Sketching、Load
shedding和哈希方法。
其中,取样方法将数据流中的数据项
以一定概率抽取到概要数据结构中。
直方图按照数据项的取
值或出现频率将数据项划分为桶,对每个桶压缩表示。
小波
方法对原有数据做小波变换,将保留原有数据主要信息的少
·2·
5.1.2 主分量计算
文[15]对多条数据流组成的矩阵作奇异值分解（Singular
ValueDecomposition,SVD）分析,并使用得到的特征值和特
征向量表达数据流之间的关联。
文章采用数据流的十字转门
（Turnstile）模型,给出了界标模型和滑动窗口模型下的算法。
其中,采用滑动窗口模型的算法将滑动窗口内的数据划分为
多个段,分段保存矩阵的组成数据,当某个段的时间戳滑出滑
动窗口时,将整个段删去。
文[15]在数据流上进行SVD分析的计算代价过大。
文
[2]采用PCA（principalcomponentanalysis）技术分析多数据
流,将n条数据流用k个隐藏变量表示,其中kn。
但是,它
没有使用SVD计算主分量,而是基于自适应过滤技术（adap-
tivefilteringtechniques）实现了一个增量式的主分量获取算
法。
文中使用指数衰减因子来逐渐消除历史数据对计算结果
的影响。
5.1.3 多数据流聚类
与定量计算数据流之间的关联统计量不同,另一种多数
据流关联分析方法对多条数据流进行聚类分析[18,19],发现彼
此间相似的数据流。
文[18]主要讨论了如何减少每个时刻需
要计算的数据流对之间的距离。
文章采用数据流的界标模
型。
文[19]提出一个滑动窗口模型下的多数据流聚类方法。
此方法基于一个层次概要数据结构支持任意大小滑动窗口内
的多数据流聚类。
5.2 单数据流挖掘
为避免与已有文献的重复,对于单数据流挖掘,本文只分
析了各项挖掘任务中最具有代表性的算法,更全面的算法介
绍请参见文[20]。
5.2.1 分类
为了对数据流进行实时处理,要求算法在看到整个数据
流之前就能处理数据并得到处理结果。
而传统的判定树构造
算法必须从一开始就能够读取整个数据集。
文[21]提出一个
针对数据流的增量式判定树构造算法。
算法基于Hoeffding
不等式,以一定概率保证其增量式生成的判定树与使用传统
算法在整个数据集上生成的树相差不大。
设数据中包含c个类别,G（Xi）为构建判定树时为选择
分裂属性所计算的各属性的信息增益。
设在读取n个数据
后,G（Xa）最大,G（Xb）次大。
对于某个指定的δ,若ΔG=G
（Xa）-G（Xb）≥（logc）2ln（1/δ）2n,则Hoeffding不等式以概
率1-δ保证选择Xa作为分裂属性是正确的。
此时,算法只
使用部分数据项就能以一定概率正确选择树节点的分裂属
性,从而将只能在整个数据集进行的批处理式的判定树构造
算法改进为一个增量式的判定树构造算法。
文[22]设计了一个基于聚类分析的数据流分类算法。
还
有大量文献研究了如何在变化的数据流上建立分类
器[14,23～29],这些文献将在后面详细讨论。
5.2.2 频繁项挖掘
在动态数据集上挖掘频繁项是一项困难的任务[30]。
数
据流所要求的单次线性扫描进一步增加了这项任务的难度。
随着数据的不断流入,频繁项可能会变得不频繁,非频繁项也
可能成为频繁项。
要精确地计算数据流中的频繁项,算法必
须保存所有的历史数据。
但是,对于流数据,这是一个无法达
到的要求。
因此,数据流上的频繁项挖掘算法只能得到近似
计算结果。
文[10]提出一个近似的流数据频繁项挖掘算法。
算法保
存多个三元组记录:
（e,f,Δ）,其中,e是数据流中的元素,f
为e的估计频率,Δ是e的最大可能的错误,即若记e的真实
频率为fe,则fe≤f+Δ。
对于选定的参数ε,每当算法遇到
一个没有被记录的新元素e′时,就生成一个新元组（e′,1,
εN）;每当算法读取1ε个数据项时,就删除所有f+Δ≤
εN的元组。
其中,N为目前已读取的总的数据项数目。
通过
这种处理,算法保证所有fe>εN的元素都被记录,且f≤
fe≤f+εN。
对于任意的频繁度阈值s>ε,输出满足条件f≥
（s-ε）N的项就保证所有fe≥sN的项都被输出,且所有输出
项都满足条件fe≥（s-ε）N。
在实际应用中,大部分数据的
出现频率都较低,通过采用上述方法,算法不需要记录出现频
率较低的数据,从而既节省了计算空间,同时又保证了输出的
质量。
上述算法采用的是数据流的界标模型,在整个数据流上
进行计算。
文[31]将其扩展到数据流的时间窗口模型上,实
现了多时间粒度的频繁项挖掘。
5.2.3 聚类
第一个以数据流为分析对象的聚类算法是由斯坦福大学
的SudiptoGuha等人提出的[32]。
这个算法采用分而制之
（Divide-and-Conquer）的思想,将数据流划分为多个段,算法
对每段分别聚类,得到第一层簇中心。
当第一层簇中心达到
一定数目后,对其进行聚类,得到第二层簇中心。
这样的过程
伴随数据的流入一直进行,在每个时刻,系统最多维持m个
第i层中心点。
此算法在整个数据流上进行计算。
由于每次
都要积累一定数目的数据后才进行处理,此算法只能看作是
分批批处理算法。
算法CluStream[16]与HPStream[17]是流数据挖掘中的两
个重要的聚类分析算法。
这两个算法都在线计算micro-clus-
ter[33]。
CluStream使用金字塔时间结构（PyramidalTime
Frame）保存一系列micro-clusters的快照,从而能够以较小的
误差计算任意时间段内的聚类,且能够分析随时间推进聚类
的改变。
HPStream针对高维聚类问题,动态地选择使聚类
体积最小的那些维与聚类关联,实现了一个子空间聚类算法。
与CluStream在整个数据流上计算micro-cluster不同的是,
HPStream使用衰减因子随时间推进不断衰减历史数据,并
在聚类数目过多时,删除最早加入的聚类。
CluStream与
HPStream都是增量式的聚类算法,在每个数据项到来时都
进行处理,因此它们都能作anytime的回答。
在流数据聚类研究中,还出现大量其他的挖掘方法。
文
[34]和文[35]将基于网格的聚类算法应用到数据流上。
文
[36]扩展了K-划分算法和CURE算法。
文[37]提出K-
means算法的变体以聚类二元数据流。
文[38]实现了一个滑
动窗口模型上的K-Medians聚类算法。
5.3 挖掘变化的数据流
由于数据流是一类流速与数据内容都随时间动态变化的
数据对象,挖掘变化的数据流成为流数据挖掘领域的一个特
有的研究内容。
目前,挖掘变化的数据流包括两方面的研究:
模型跟踪[28]和变化挖掘[39]。
其中,模型跟踪与机器学习中
的概念跟踪[40～43]可以看作同一个概念。
变化挖掘与统计中
的改变点检测（change-pointdetection）[44]和时序数据上的分
割（segmentation）[45,46]类似。
在变化的数据流上建立分类模型,是一个研究得比较多
·4·
个小波参数作为概要数据保存。
Sketching对数据作垂
直取样。
Loadshedding在负载过大时直接丢弃一些数据项。
哈希方法通过一组哈希函数,将大量数据映射到少量桶中。
4.2 滑动窗口技术
使用滑动窗口的需求来自于算法和应用。
在算法方面,
滑动窗口减少了算法需要处理的数据量,并对挖掘变化的数
据流提供支持。
在应用方面,有些应用只对最近的数据感兴
趣,要求算法对以当前时间为终点的某个滑动窗口内的数据
进行处理。
在滑动窗口上进行数据挖掘最大的困难在于过期数据的
移除。
随着数据的流入,滑动窗口中最早到达的数据将滑出
窗口的范围,算法需要消除这些数据对滑动窗口上的目标计
算所造成的影响。
解决这个问题的最直接的做法是保存滑动
窗口内的所有数据,当某个数据滑出窗口时,根据这个数据的
值,将其从计算结果中消除。
目前,多个采用滑动窗口模型的
挖掘算法使用这种方法实现滑动窗口上的计算,如
CVFDT[14]。
这种方法可以精确地对滑动窗口内的计算结果
进行增量式地更新。
但是,由于要保存窗口内的所有数据,对
于其大小超过可用内存空间的滑动窗口,仍然需要进行磁盘
存取。
为减少滑动窗口内数据所占用的空间,另一种方法以降
低滑动窗口上计算的精度为代价,使用小于滑动窗口内数据
体积的空间,支持滑动窗口上计算的增量式更新。
这种方法
将数据流划分为小的固定长度的段（bucket,或basicwin-
dow）,对每个段,仅保存段内数据的概要信息,如StaS-
tream[13]。
滑动窗口在这些段上滑动。
当流入的数据积累成
一段时,抽取这一段的概要信息,将其加入滑动窗口,并从滑
动窗口中删除最早的段。
这样,内存中就只需要保存滑动窗
口中多个段的概要信息。
此时,滑动窗口的增量式更新粒度
由一个数据项增大为一个数据段。
这种方法通常只支持大小
为段大小的整数倍的滑动窗口上的计算[15]。
文[13]通过保
存每个段的数据的离散傅立叶变换系数,能支持任意窗口大
小内的数据流关联系数计算。
4.3 多窗口技术
基于滑动窗口的方法一般都要求用户事先指定窗口大
小,算法在运行过程中只能给出此滑动窗口上的计算结果。
而在很多应用中,用户可能在线提出某个窗口上的挖掘请求,
此窗口的大小没有事先确定,而且窗口的终点可能也不是当
前时刻。
为了支持这样的应用需求,学者们提出一种多窗口
方法,支持用户的在线挖掘请求。
多窗口技术在内存或磁盘中保存数据流上多个窗口内数
据的概要信息。
在有些算法中,每个窗口的范围都是从数据
流起始点到窗口建立的时刻点,窗口中的数据存在重叠,如
CluStream所使用的pyramidal时间框架[16]。
另一类多窗口
技术将数据流划分为多个固定长度的段,每个段都形成一个
窗口。
当内存中的窗口数达到一定数目时,就将这多个窗口
合并,形成概要层次更高的窗口。
随着数据流的流入,概要层
次不同的多个窗口形成一个层次结构。
此时,每个窗口相当
于对数据流上两个预定义的时间戳之间数据的一个快照。
4.4 衰减因子
除了滑动窗口技术,另一种可被用来消除历史数据对当
前计算结果的影响的方法是使用衰减因子[17]。
在这种方法
中,每个数据项都被赋予一个随时间不断减小的衰减因子,数
据项的值与衰减因子相乘后再参与计算。
因此,数据项对计
算结果的影响随时间的推移逐渐减小。
这种方法的实现很简
单,但是,与滑动窗口技术相比,其计算结果的意义不是非常
明确。
在使用滑动窗口的算法中,用户明确地知道他是在对
哪些数据进行处理。
而在使用衰减因子的方法中,每项数据
都只是部分地参与了计算,用户无法确定计算结果到底由哪
些数据得到。
4.5 近似技术
由于数据流处理严格的时间与空间限制,确定且精确的
数据流算法比较少见。
对于大多数算法,只能以降低计算结
果的精度为代价,换取算法时空复杂度的降低。
能在理论上
保证近似程度的算法是比较理想的近似算法。
目前,有多种近似技术可用来降低算法的时空复杂度。
例如,基于概要数据结构的算法都是近似算法。
这是因为在
构建概要数据结构时,不可避免地存在着信息的损失。
概要
数据结构只能近似还原原有数据。
基于多窗口技术和衰减因
子的算法也是近似算法。
除了使用这些通用的压缩技术,也
可针对具体的挖掘任务,设计相应的近似算法[10]。
4.6 自适应技术
由于数据流是动态变化的,处理数据流的算法必须能够
根据数据分布的变化以及数据流流速的变化自动调节算法的
处理策略。
动态系统中的自适应技术根据系统的反馈自动调
节系统参数。
目前,在处理变化的数据流时,算法通常将分类
器的分类精度作为反馈,在精度下降时重新建立分类模型。
5 流数据挖掘算法
流数据挖掘的对象可以是多条数据流,也可以是单条数
据流。
挖掘多条数据流的主要目的是分析多条并行到达的数
据流之间的关联[2,12,13,15,18,19]。
对单数据流的挖掘则涵盖了
分类、频繁模式挖掘、聚类等多项传统数据挖掘中的主要任
务。
挖掘变化的数据流是一项特殊的任务,目前主要是以单
数据流为对象进行研究的。
5.1 多数据流关联分析
现有的多数据流关联分析主要采用3种方法,即计算数
据流对之间的关联系数[12,13]、计算多条数据流的主分
量[2,15],以及计算多条数据流中存在的聚类[18,19]。
5.1.1 关联度计算
关联度计算指在多条数据流中,计算每对数据流之间的
关联系数,从而发现具有高的正关联或负关联的数据流对。
当数据流数目较大时,在线计算每对数据流之间的关联系数
是不现实的。
文[13]实现的StaStream系统通过使用离散傅
立叶变换的保距特性与系数的对称特性,推导出数据流对傅
立叶变换系数之间的距离与关联系数之间的关系。
系统只对
傅立叶变换系数之间距离满足一定条件的数据流对计算关联
系数。
StaStream采用数据流的滑动窗口模型,并将每条数据
流划分为小的固定长度为b的段（基本窗口）,对每个段,保存
段内数据的离散傅立叶变换系数。
系统将滑动窗口内的段作
为数据流的概要数据结构。
这个概要数据结构还可为其他计
算提供支持。
StaStream没有对数据流对之间存在滞后关联的情况作
太多讨论,但是这种情况在应用中比较常见。
文[12]提出的
BRAID方法,讨论了滞后关联（lagcorrelation）的计算。
BRAID采用界标模型,对数据流从起始到当前时刻所有的数
据进行处理。
其概要数据结构只能用来计算数据流对之间的
关联系数。
·3·
本文得到湖北省自然科学基金项目“时空数据库的关键技术研究与实验”（ABA048）的资助。
孙玉芬 博士生,研究方向为流数据挖掘和聚
类分析;卢炎生 教授,博导,研究方向为特种数据库、数据挖掘和软件测试。
题[14,23～27,29]。
文[14]中提出的CVFDT基于文[21]中
的VFDT算法,在一个动态调节大小的滑动窗口上,增量式
地建立一个随数据变化动态变化的判定树。
为消除历史数据
对判定树计算的影响,算法必须保留整个滑动窗口内的所有
数据。
另一类在变化的数据流上建立分类模型的方法通过建立
多个分类模型来实现模型的跟踪[24～29]。
文[27]第一个将机
器学习中的集成方法（ensemblemethods）用来对变化的数据
流分类。
算法在数据流上维持一个由固定数目的分类模型组
成的ensemble。
每当算法读取一定量的数据后,就在此段数
据上建立一个分类模型。
若此分类模型能够提高ensemble
的分类性能,则用其替换ensemble中性能最差的一个分类模
型。
Ensemble使用无权重的majorityvoting投票规则对数
据进行分类。
文[24]与文[25]根据各分类模型在当前数据段
上的预测错误期望,赋予它们适当的权重。
文[28]使用logis-
tic回归技术,通过最大化数据的似然给ensemble中的各个分
类模型赋予最优的权重。
文[26]在ensemble中的所有分类
模型中找出其训练数据集与当前数据最相似的分类模型。
为
了实现这个分类模型选择策略,算法为每个分类模型保存相
应的训练数据集。
这种选择策略可有效减少ensemble中的
冗余信息,尽可能扩大ensemble中分类模型的数据覆盖范
围。
在对当前数据进行分类时,文[24～28]都是使用多个分
类模型分类结果的组合,文[29]在多个分类模型中选择对当
前数据分类效果最好的分类模型进行分类。
文[47]按数据流中是否发生概念转移以及训练模型的数
据是否充分这几种不同的情况,使用不同的数据集训练得到
多个分类模型,然后选择分类正确度最高的模型作为当前最
优模型。
文[48]研究了如何发现数据流中数据分布的改变并将其
可视化。
文章通过计算数据流入时数据空间中各数据点密度
的改变情况,发现数据点的转移轨迹与趋势,并将这些转移以
图形的形式表示出来。
比较两个数据集的数据分布是否相同,是统计上曾经研
究过的一个问题[49]。
通过在数据流上维持多个数据窗口,文
[50]将检测数据流中的变化转化为比较两个数据集的分布是
否相同的问题,并提出一个非参数方法来解决这个问题。
文
[51]更进一步,设计了一个新的数据结构来度量两个数据集
之间的相似度。
结束语 本文介绍了现有的数据流模型,总结了流数据
挖掘算法的九大特点,并讨论了算法中常用的几种技术。
文
中还针对不同的挖掘任务,分析了其代表性算法。
这些内容
对于深入了解流数据挖掘并提出新的挖掘算法,都有重要意
义。
参考文献
1HenzingerMR,RaghavanP,RajagopalanS.Computingondata
streams.SRCTechnicalNote1998-011.Digitalsystemsresearch
center:
PaloAlto,California,1998
2PapadimitriouS,SunJ,Faloutso
升级会员 