数据流挖掘

数据流

在很多数据挖掘的场景下，我们并不会预先知道所有的数据集，而是一段段接收到需要处理的数据，这种形式的数据又叫做数据流，而数据流的管理也是数据挖掘中一个很重要的话题，比如谷歌搜索引擎和推特的热榜，都需要面对数据流的场景，这种场景下我们可以认为数据是无限多并且非固定的，也就是说数据的分布情况可能会随着时间的变化而变化。

很显然一个数据处理系统不可能保存所有的流数据，并且流数据输入的速度也是不一定的，因此如何对流数据进行建模就变的非常重要。我们常说的SGD其实就是一个非常经典的流算法，因为SGD对于每个输入的样本都进行微小的梯度更新，这种方式在机器学习中也被称为在线学习，数据流挖掘需要解决的问题主要有：

• 从流中进行采样
• 基于滑动窗口进行查询
• 过滤数据集，筛选出所有符合条件的数据
• 统计不同元素的个数
• 找到出现频率高的元素

数据流挖掘的方法可以使用的应用场景有：

• 对查询流进行挖掘，比如搜索引擎
• 点击流挖掘，比如wiki统计最近一个小时内访问频率最高的页面
• 社交网络挖掘，推特热搜
• 传感器网络的通信数据挖掘
• 电话记录分析，IP包检测……

从数据流中进行采样

受限于存储空间，我们不能存储数据流中所有的数据，一个解决的办法就是采样，用采样得到的数据来代表整体，而采样问题可以分成下面两种：

• 采样固定比例的元素(比如1/10)
• 在无限的数据流输入中维护一个定长的随机采样

我们希望采样的结果的概率分布和数据流整体的分布基本一致。

定比例采样

定比例采样常见的场景有搜索引擎数据流等等，以搜索引擎为例，我们可以对一系列客户端的查询内容维持固定比例的采样，并从中分析出最近的搜索热点，很naive的采样方式是等间隔采样，比如要采样1/10的内容，那么就每隔10个采样一个，但是这种方法会导致在有重复查询的时候，采样得到的查询内容概率分布和实际概率分布不一致。

另一种方法是选择用户来采样，比如可以选取1/10的用户并将其所有的搜索查询作为采样结果

定长度采样

定长度采样要求不管数据流有多长，都保留固定个数的数据作为采样结果，一种可行的方式是Reservoir Sampling，包含如下几个步骤：

• 假设我们需要对数据流采样s个样本，首先保留数据流的前s个作为初始采样

• 然后在数据流已经有n-1个数据之后，对于第n个出来的数据：

  • 用的概率保留这个元素作为采样，否则就丢弃
  • 如果保留了第n个新来的数据，就从已有的s个采样数据中随机替换掉一个

这个算法的合理性证明就略过了。

滑动窗口查询

滑动窗口是另一种处理了流数据的工具，就是在流中维护一个长度为N的窗口保留最近的N个元素，用这N个元素来估计整个流的性质，常见的任务有统计元素的个数，比如给定一个01流，用一个长度为N的窗口来估计最近的M个数字中有多少个1(M要大于N)

• 具体的就不深入探究了，这一部分内容感觉意义不是很大，更偏向于传统的算法了

数据流过滤

• 待补充

元素计数

• 待补充