流挖掘算法介绍00：序——背景，流数据模型，近似算法评估，2-Universal 哈希

背景

假如（假如。。。）我是Facebook，Twitter，或者是Weibo的工程师（额，，，）；

每日就有数百万网民在这一社交平台上表达不满情绪，并分享生活点滴、展示爱情故事以及炫耀财富。也存在大量

我们就想知道，下面这些问题：

• 在过去的一天内（按小时与分钟划分），大概有多少个不同的人在发牢骚？
  • 在过去的一天内（按小时与分钟划分），秀恩爱行为最活跃的前十分之一级别的活跃用户群体是哪些？具体包括编号为（1-1/1, 2-2/1, ..., 999-999/9, 1,000-1/9）等具体用户。
  • 假设每位用户的日均发送推文数量服从正态分布，则可识别出发送推文数量显著高于平均值一定倍数的离群用户。

这类问题在数据量较小时相对容易解决可以通过哈希表或者堆等数据结构进行记录之后再进行一次全面检查以确保完整性

但是当数据量达到百十G级别时,单台服务器难以承载如此庞大的规模；另一方面,管理层也不愿增加计算资源来执行这种无意义的功能模块;此外,采用基于Hadoop的分布式架构来构建一个复杂的分布式系统以支撑业务需求也显得力不从心（甚至调侃一下目前的人力资源配置情况）

总的来说现有算法在大数据上有这些缺点

• 必须进行多次数据扫描；这就要求将数据库存储到存储介质上并进行读取操作；由于在大数据规模下缺乏足够的存储介质且读写速度较慢的问题尤为突出；
  • 处理时间不受时序限制；
  • 内存使用通常与数据量呈线性或平方关系；（例如面对100G规模的数据；垂直切分方法虽然有效但具有较大破坏性；此外还牵涉到网络带宽问题，在大规模数据环境下同样是个难点）
  • 并非所有算法都能支持分布式处理或垂直切分后的合并运算（例如无法计算最近1小时内不同用户数量的事件数）

不过我们的要求又是：

• 只扫一遍数据

• 希望能实时的处理数据，希望每天处理上亿个推

• 避免使用与数据量相当数量的内存空间；最理想的状态是采用 log n 的内存复杂度。

  • 通常情况下建议支持分布式计算方式。
  • 仅需估算结果即可。

本系列旨在介绍的方法即采用数学领域中的概率算法基于理论基础下确保一定的准确度来进行计算

流数据模型

简单说，就是每次从流中读到一个数据，就再也无法读到这个数据了，

在每次读取数据后，在内存中将一定数量的数据进行保存，并避免过多。

近似算法评估

我们是近似算法是A，正确算法是 Φ ，一个 (ε, δ) 近似算法满足：

直观理解就是A算法偏差超过 ±ε 的概率不超过 δ 。

因为 Φ 可能为0，所以也常常用另外一种方法来评估：

2-Universal 哈希

考虑两个集合X和Y，并将集合X中的元素映射至集合Y中。通常情况下|X|大于|Y|（即集合X的大小大于集合Y），为了实现所谓的"2-Universal哈希"（Hashing），必须满足以下条件：

大致来说，在空间X中建立与Y之间的对应关系，在应用该哈希函数时会生成一系列数据，并且该哈希函数具有完全随机且均匀的概率分布特性。

• 选取两对 (x, y) 旨在说明两次hash事件的独立性；
  • 任意选取量词是为了表明哈希结果的随机特性；
  • **选取概率值1/|Y|^2 旨在表明均匀分布特性。

这里只是一个数学上严格的概念，用于理论推导冲突的概率等；

为了避免王垠附体，在遇到特例之前我并不去深究。