流挖掘技术

一，数据流特点

1.??????海量的，不可能在内存以及硬盘存储

2.??????传统的多遍扫描挖掘方式不切实际

3.??????快速变化的，不可能看到流中每一个元素，只能分析部分获取决策

4.??????时序的，只能是单次线性，按其流入顺序依次读取

5.??????很快的响应时间

6.??????高维的

二，数据模型

1.??????时序模型(time sevies):A[i] = X1,每一个数据项代表独立的信号

2.??????现金登记(cash register)：令Xi = (j,Ii)且Ii>=0,则Ai[j]=Ai-1[j]+Ii 数据流中多个数据项增量表达一个A[j]

3.??????十字转门：同上，Ai[j]随着流入，可能增加也可能减少。

按照时序范围，可分为：

1.??????快照模型：处理范围在两个预定的事件戳范围之内

2.??????界标模型：从已知的初始时间点到当前的时间点

3.??????滑动窗口模型：某个固定的滑动窗口确定，滑动窗口终点永远为当前时间。其中窗口的大小可以由一个时间区定义，也可以由窗口的数据项定义。

三，数据流挖掘挑战

1.??????单次线性扫描

2.??????低的时间复杂度

3.??????低的空间复杂度

4.??????在理论上保证计算结果具有好的近似度

5.??????能适应动态变化的数据和流速

6.??????能有效的处理噪音和空值

7.??????on-demand挖掘

8.??????anytime的响应

9.??????概要数据结构的通用性

四，生成数据流概要数据结构的方法

1.??????基于数据的：取样，直方图，小波变换，sketching，loadshedding，hash，聚集运算

2.??????基于任务的

①????滑动窗口技术，最大的问题在于过期数据的移除，需要消除滑动窗口上过期数据对目标计算结果的影响

②????多窗口技术，在内存或者磁盘上保存数据流上多个窗口的数据信息

③????衰减因子，每个数据项都被赋予一个随时间不断减少的因子，数据项的值与衰减因子相乘后再参与计算

④????近似技术，以降低计算结果的精度为代价，换取算法时空复杂度降低

⑤????自适应技术，根据数据分布的变化和流速的变化自动调节算法

五，挖掘技术

1.??????分类：

①????无权重的majority,voting,投票规则分类

②????根据各分类模型在当前数据段上

2.??????聚类：对已给的数据集合，将其中相似的对象划分为一个或者多组

①????对已发现的簇，提供一个简洁的表达方式

②????对新的数据元素的处理，增量的

③????清晰而快速的孤立检测点

??? 3.频繁挖掘模式