数据挖掘--数据流挖掘

一个多月没更新了，去考托福和gre了，英语太差有点难过。。。

我最近看到数据流这个字眼，想到对数据流挖掘了解的太少了，几乎是一窍不通，因此就像学学数据流挖掘。

这篇博客算是我学习数据流的一个笔记吧。

一些我看到比较有收获的网站

https://www.cnblogs.com/jean925/p/8963512.html

https://blog.csdn.net/viewcode/article/details/9088467

https://blog.csdn.net/dashuniuniu/article/details/50705389

基本知识

（https://blog.csdn.net/viewcode/article/details/9088467 ）

1. 数据流的查询

   固定查询：对前来的数据一直在执行查询和计算

   即时查询ad hoc：仅当一个查询操作提交时，才对数据进行计算查询

2. 算法策略

   内存有大小限制，因此，数据流处理算法的两个策略：

   计算问题的近似解，比精确解高效的多

   hash技术，对求解近似解非常有帮助

3. 抽样计算

   从流中选择一个子集，以便能够对它进行查询并给出统计性上对整个流具有代表性的结果。数据流巨大时，只需随机抽样一部分数据，进行存储，并供ad hoc分析使用。

   统计用户的重复查询问题：抽样时，涉及概率的乘法定理要谨慎处理，因为抽样后的概率运行可能与全集下的概率运算结果完全不同。

   解决方法：对用户进行抽样，而不是对每个用户的数据进行抽样。

   一个抽样的方法–蓄水池采样

   (来自 https://blog.csdn.net/dm_ustc/article/details/45875971)

我们要从数据流中随机抽取k个元素。如果数据流长度m事先已经知道，那这个问题就非常简单，每个元素以k/m的概率选取即可。但这个问题要求m未知，那就不太好搞了。这个问题的解法是保存一个k大小的窗口。数据流的前k个元素依次加入到窗口。对于数据流第i个元素（i>k），以k/i的概率替换窗口中的某个元素。最终窗口的元素出现概率均为k/m。

下面使用数学归纳法给出该算法合理性的简单证明。

1.假设i=1，元素被选中的概率为1；

2.设前i个元素被选中的概率为k/i。对于第i+1个元素，我们以k/i+1的概率替换窗口中的元素。其中k/i为某个元素在第i+1个元素来到前被选中的概率。如果第i+1个元素替换窗口内的元素，则以1/k的概率从窗口选一个元素去除，将第i+1个元素添加进去。计算出的结果表明元素仍存在窗口的概率为k/(i+1)。得证。

一个实际例子(来自mining massive dataset)

1.问题：对于搜索引擎是不断有查询流的，这些数据可以用来研究典型用户的行为。假设数据流的每个元素由三元组组成(user,query,time)。假设想要查询“在过去一个月中典型用户所提交重复查询的比例是多少”。假设我们只希望存储1/10的元素。

2.错误做法

一个很容易的做法就是对于每个查询都以1/10的概率进行保存。但是这个方法对于我们的问题会带来错误结果。假定某用户在过去一个月有s个查询只提交过1次，有d个查询提交过两次，不存在提交超过2次的查询。该用户提交重复查询的比例为s/(s+d)。

如果我们的查询比例为1/10，那么在该用户的查询中，提交过1次的查询达到我们期望的s/10。而出现2次的d个查询中只有d/100会在样本中出现1次（两个相同的查询都出现在样本中的概率为(1/10)(1/10)=1/100），有18d/100的查询在样本中出现1次（两个相同的查询只有一个出现在样本中，概率为(1/10)(9/10)*2=(18/100)）。则该用户提交重复查询比例为(d/100)/(d/100+s/10+18d/100)=d/(10s+19d)。显然和期望值不相等。

3.正确做法

对于这类问题，不能从每个用户查询的抽样样本中得到正确答案。所以我们必须挑选出1/10的用户，将他们的所有查询放入到样本中，而不考虑其他用户的查询。也就是说我们采样的对象不是查询，而是用户。

4.一般性的抽样问题：

将某些字段看成关键字组合，并利用hash的a/b策略，即b个桶，a作为阈值，保留小于a的采样值。

新问题： 新用户出现，每个用户的样本规模不断变大，以至于抽样的数据都超出了分配的空间，如何处理？

那么就设定新的阈值a-1，即降低阈值，并将hash值等于a的数据删除，这样可以提高效率，节省空间。

1. 过滤数据–bloom过滤器https://www.jianshu.com/p/6f9b2d6fba68https://www.jianshu.com/p/6f9b2d6fba68 里面的例子很清楚

   比如垃圾邮件的过滤，采用布隆过滤的方法，创建一个位数组，初始化所有值为0，将合法的邮件映射到位数组上，并设置值为1，用不同的hash函数检查邮件，如果有一个值为0，则拒绝

2. 统计某时段内，出现的不同元素的数目

   一种方案是内存中保存当前所有元素列表，可以用hash或搜索树来保存和检索数据。问题：元素数目可能大到无法全部放入内存。

   解决方案：

   1.使用多台机器，并行处理

   2.FM（Flajolet-Martin）算法，统计某元素hash后尾部0的个数，若其hash值尾部0的个数至少为r的概率是2^(-r)，而任何元素hash值尾部都不满足至少有r个0的概率为(1 - 2(-r))m。 然后估计出所有元素的个数m：2^R, 最大尾长为R

   优化策略： 多个hash函数，分组：组内平均值 + 组件中值滤波（取中位数）

Flajolet-Martin(FM)算法能够较好地解决估算数据流序列中独立元素数目的问题。

（https://blog.csdn.net/llwszjj/article/details/25629009?utm_source=blogxgwz3）

假设我们有1万个int型数字可重复的），我们想找出这个数字集合中不重复的数字的个数。怎么办呢？很简单，将这1万个数字读进内存，存放到hashset中，那么hashset的size就是不重复数字的个数。接下来，问题变得更加的复杂，有100亿个数字，怎么办? 全部读取到内存中可能会有问题，如果这其中有1亿个不重复的数字，那么至少需要内存 100M sizeof(int)，内存也许不够。 FM算法就是为了解决这个问题。假设n个object，其中有m个唯一的，那么FM算法只需要log(m)的内存占用（实际操作中会是klog(m)），以及O(n)的运算时间。当然，FM的问题是，它的结果只是一个估计值，不是精确结果。

具体思路如下：

假定哈希函数H(e)能够把元素e映射到[0, 2^m-1]区间上；再假定函数TailZero(x)能够计算正整数x的二进制表示中末尾连续的0的个数，譬如TailZero(2) = TailZero(0010) = 1，TailZero(8) = TailZero(1000) = 3，TailZero(10) = TailZero(1010) = 1；我们对每个元素e计算TailZero(H(e))，并求出最大的TailZero(H(e))记为Max，那么对于独立元素数目的估计为2^Max。

举例来说，给定序列{e1, e2, e3, e2}，独立元素数目N = 3。假设给定哈希函数H(e)，有：

H(e1) = 2 = 0010，TailZero(H(e1)) = 1

H(e2) = 8 = 1000，TailZero(H(e2)) = 3

H(e3) = 10 = 1010，TailZero(H(e3)) = 1

第1步，将Max初始化为0；

第2步，对于序列中第1项e1，计算TailZero(H(e1)) = 1 > Max，更新Max = 1；

第3步，对于序列中第2项e2，计算TailZero(H(e2)) = 3 > Max，更新Max = 3；

第4步，对于序列中第3项e3，计算TailZero(H(e3)) = 1 ≤ Max，不更新Max；

第5步，对于序列中第4项e2，计算TailZero(H(e2)) = 3 ≤ Max，不更新Max；

第6步，估计独立元素数目为N’ = 2^Max = 2^3 = 8。

在这个简单例子中，实际值N = 3，估计值N’ = 8，误差比较大。此外，估计值只能取2的乘方，精度不够高。

在实际应用中，为了减小误差，提高精度，我们通常采用一系列的哈希函数H1(e), H2(e), H3(e)……，计算一系列的Max值Max1, Max2, Max3……，从而估算一系列的估计值2^Max1, 2^Max2, 2^Max3……，最后进行综合得到最终的估计值。具体做法是：首先设计A*B个互不相同的哈希函数，分成A组，每组B个哈希函数；然后利用每组中的B个哈希函数计算出B个估计值;接着求出B个估计值的算术平均数为该组的估计值；最后选取各组的估计值的中位数作为最终的估计值。

举例来说，对于序列S，使用3*4 = 12个互不相同的哈希函数H(e)，分成3组，每组4个哈希函数，使用12个H(e)估算出12个估计值：

第1组的4个估计值为<2, 2, 4, 4>，算术平均值为(2 + 2 + 4 + 4) / 4 = 3；

第2组的4个估计值为<8, 2, 2, 2>，算术平均值为(8 + 2 + 2 + 2) / 4 = 3.5；

第3组的4个估计值为<2, 8, 8, 2>，算术平均值为(2 + 8 + 8 + 2) / 4 = 5；

3个组的估计值分别为<3, 3.5, 5>，中位数为3.5；

因此3.5 ≈ 4即为最终的估计值。

1. 总结一下数据流相关的例子

（https://blog.csdn.net/sun33170161/article/details/18769541 ）

1.数据抽样

比如过去一个月中典型用户所提交的重复 查询的数目。在用户规模较大的时候，将用户hash到不同的桶中，当空间不足时，则丢弃一部分桶。

2.流过滤

比如垃圾邮件的过滤，采用布隆过滤的方法，创建一个位数组，初始化所有值为0，将合法的邮件映射到位数组上，并设置值为1，用不同的hash函数检查邮件，如果有一个值为0，则拒绝

3.独立元素统计

比如统计web查询的数目，可以应用FM算法，将所有的査询hash到一个位串中，检查其末尾最大0的数目，设为R，则总数可以估计为2^R。

4.元素分布

一般用二阶矩估计，即每个元素出现数目的平方和来判断流元素分布的均匀性。可以采用AMS算法来近似计算二阶矩：在流中随机选取多个位置，并统计每个位置上的元素出现的次数，设为c，用n表示总的元素数目，则二阶矩为n*(2*c-1)的均值

5.计数

为了能够查询窗口内任意数目的元素中1的个数，采用DGIM算法，每出现元素1，则创建一个新的桶，并递归地尝试合并之前的桶，使得每个桶的大小为2的幂，且相同大小的桶最多为2个。每个桶只用保存最近的时间戳和桶的大小，有效避免了精确计数带来的空间开销。为了减小估计结果的误差，可以增加所允许出现的相同大小的桶的数目。

6.流行元素

比如最近流行的电影，可以定义一个衰减窗口，独立计算每一部电影流，对每张新的电影票，首先将所有的电影乘以一个衰减值，然后检查电影票对应的电影得分是否已存在，如果不存在，则创建新的电影流并设置得分为1，否则将该电影的得分加1。为了减少需要统计的数目，可以设置一个阀值，将低于阀值的得分丢掉。

1. 数据流分析有以下方面

   数据流频繁项集挖掘

   数据流聚类

   数据流分类

   数据流离群点检测

   数据流Skyline计算

   数据流子序列匹配

   数据流索引结构

   数据流概要结构生成

   数据采样以及压缩

   数据流粒度表示

   数据流相似性度量

   数据流趋势预测

数据流聚类

我有点好奇这个，因此想仔细看看

支撑知识（在csdn上下载了一个ppt看的）

1. 数据流模型

• 按照算法处理数据流时所采用的时序范围分类按照算法处理数据流时所采用的时序范围分类：

  (1)快照模型 ( Snapshot Model) :处理数据的范围限制在两个预定义的时间戳之间。

  (2)界标模型 (Landmark Model) :处理数据的范围从某一个已知的初始时间点到当前时间点为止。

  (3)滑动窗口模型 (Sliding Window Model) :处理数据的范围由某个固定大小的滑动窗口确定 ,此滑动窗口的终点永远为当前时刻。其中 ,滑动窗口的大小可以由一个时间区间定义 ,也可以由窗口所包含的数据项数目定义。

• 数据流中的数据项 x 1 , …, xi , …, xn 依次按下标顺序到达 ,它们描述了一个信号 A。

  按 xi描述信号 A的方式 ,数据流模型可分为以下几类:

  (1)时序( Time Series)模型:A [ i ] = xi 。

  (2)现金登记 (Cash Register)模型:令 xi = ( j,Ii ) ,且 Ii≥0,则 Ai [j] =Ai-1 [ j ] + I i。此时 ,数据流中的多个数据项增量式地表达一个 A [ j ]。

  (3)十字转门( Turnstile)模型:令 xi = ( j,Ui) ,则Ai[ j ] =Ai -1 [ j ] +Ui。其中 , Ui可为正数 ,也可为负数。

1. 基于数据的技术

• 抽样（Sampling）

  使用水库抽样（reservior sampling）在“水库”中维护s个候选的样本，随着数据流的流动，新的数据元素都有一定的概率替代水库中的元素。

• 梗概（Sketching）

  梗概是一个将数据流中的数据向量做一个随机投影的过程。它建立这些分布向量（如直方图）的小空间汇总。梗概广泛用于不同数据流的比较和聚集查询。缺乏精度。

1. 衰减函数（Fading Function）

   强调近期数据的重要性、消减历史数据对计算结果影响的方法是衰减因子和衰减函数。数据元素在参与计算前，先经过衰减函数的作用。因此，每个数据元素对最终结果的影响将随着时间的推移逐渐减小。一种常用的衰减函数形式为指数形式。

stream聚类

对于数据流来说，使用批处理的方式。

STREAM算法采用分级聚类的方法，首先对最初的m 个输入数据进行聚类得到O(K)个1 级带权质心，然后将上述过程重复m/O(K) 次，得到m 个1 级带权质心，然后对这m 个1 级带权质心再进行聚类得到O(K) 个2级带权质心；同理，每当得到m 个i 级带权质心时，就对这些质心进行一次聚类得到O(K) 个i+1 级带权质心；重复这一过程直到得到最终的O(K)个质心。对于每个第i+1 级带权质心而言，其权值是与它对应的i 级质心的权值之和。

也就是将大量的数据分成m批，每一批内部使用k-means聚类，这样可到mk个质心，对mk作为新的数据进行批处理聚类，得到了m’k’个质心，这样一级级向上聚类。

clustream

引入的新的概念：

• 簇，在线部分，微聚类
• 时间帧，离线部分，宏聚类

1. 在线部分（微簇）

• 初始化簇

  首先在磁盘上存储最初始的initNumber个数据点，然后采用标准的k-means算法形成q个微簇：M1、M2…Mq。

• 在线处理　　

  对于以后达到的每一个数据点Xik，要么被上述的某个微簇吸收，要么放进它自己的簇中。首先计算Xik与q个微簇中的每一个的距离（实际上是其中心）。将其放到离它最近的那个簇Mp中。

  特殊情况：

  1.Xik虽然离Mp最近，但是Xik却在Mp的边界外；

  2.由于数据流的演化，Xik可能是一个新簇的开端。

  处理方法：

  为落在边界外的数据点创建一个带独有标志id的新簇，这需要减少一个其他已经存在的簇。这可以通过删除一个最早的簇或者合并两个最早的簇来实现。

1. 离线处理（时间帧，宏簇）

   用户在该部分可以在不同时间幅度内发现簇。这部分所用的数据是在线部分形成的统计信息，这可以满足内存有限的需求。用户提供两个参数h和k，h是时间幅度，k是预定义的需要形成的簇的数目。

   算法：

   该部分采用改进的k-means算法

• 初始阶段

  不再随机的选取种子，而是选择可能被划分到给定簇的种子，这些种子其实是对应微簇的中心。

• 划分阶段

  一个种子到一个“伪数据点”（也就是微簇）的距离就等于它到“伪数据点”中心的距离。

• 调整阶段

  一个给定划分的新种子被定义成那个划分中带权重的微簇中心

总结：离线聚类就是在在线聚类的基础上，对在线簇进行聚类

下面是数据流聚类的方法，我想等到具体应用的时候再仔细研究剩下的方法

数据流分类

https://blog.csdn.net/tanhy21/article/details/53363508