学习笔记DB4：大数据近似算法

分类：IT>数据库

1、处理大数据的两种思维模式是什么？

处理大数据的问题主要是如何扩展计算能力，扩展计算能力的方案主要有以下两种：

（1）超级计算机分布式系统问题：成本昂贵、能源消耗

（2）降低数据规模通过引入近似/允许误差，将大数据变为小数据

优点：成本小，可与方案一结合

缺点：需要针对特定问题设计特定算法

2、什么是大数据近似算法？

大数据近似算法：利用采样（sampling）、略图（sketch）、摘要（summary）等技术，引入可控误差，解决由数据规模扩大带来的时间/空间/通讯量效率问题。

大数据的特点：

大数据通常有冗余，有价值的数据量可能很小

统计量从宏观上能反映实际问题的特质

现有的数据采集系统和分析算法也不可避免的会产生误差

3、数据流模型为什么适合处理大数据？

数据流是一个由海量数据组成的数据序列

Single pass：每个数据最多访问一次

Small space：存储空间非常小

Small time：更新（插入删除）速度快

4、分布式模式为什么适合处理大数据？

针对MapReduce、Hadoop等分布式计算平台

输入数据分布在多个节点

每个节点基于其数据，独立计算摘要

将多个摘要在主节点合并，回答关于原始输入数据的查询

分布式模式的例子有哪些？

模拟传感器网络中的网络内聚合（In-network aggregation）

每个传感器独立观测数据（如湿度、温度、车流量等），并计算摘要

摘要通过通讯依次传输合并

最后在主节点合并所有摘要，形成对聚合数据的估计

5、什么是随机采样算法？

随机采样算法就是在元数据中随机选取一些数据作为“代表”，回答近似查询。

无偏估计：对于AVG、COUNT、SUM等查询，随机采样给出的查询结果的期望就是真实结果

需要多少个采样？

根据大数定理，采样数越多，结果越精确，误差越小

Probably approximately correct（PAC），可能近似正确的保证

以99.99%的概率/置信度，误差不超过0.01%

Chernoff不等式：当采样数达到时，以的置信度，保证误差不超过

大数据->小数据：当误差和置信度确定后，采样数与元数据大小无关

采样数和误差平方成反比，1%误差需要10000+个采样

6、水塘采样算法

给定N个元素，希望随机选取k个元素，使得每个元素被选取的概率都是k/n？

数据流模型：只能扫描所有元素一遍，可用空间为k

水塘采样算法（Reservoir Sampling）

选取前k个元素放入水塘

对于i>k，当扫描到第i个元素时，以k/i的概率选取

若被选取，从水塘中随机剔除一个元素，将加入水塘

随机采样与大数定理

随机采样应用实例：Online Aggregation

水塘采样算法

随机采样的融合

随机采样的合并

7、基于计数的近似算法有哪些？

（1）多数问题（Majority）

（2）Misra-Gries（MG）算法

8、什么是多数问题？多数问题的算法是什么？

多数问题

Majority

输入：N个元素

输出：Majority即出现次数超过N/2的元素

算法1：扫描所有元素，给每个出现过的元素分配一个计数器记录其出现次数，如果某个元素出现次数超过N/2，即为Majority

时间复杂度：O(N)（扫描一遍）

空间复杂度：O(N)

算法2：对每个出现过的元素，扫描一遍N个元素，并记录其出现的次数。如果某个元素出现次数超过N/2，即为Majority

时间复杂度：O(N2)（如果N个元素都不相同，需要扫描N遍）

空间复杂度：O(1)

大数据时代改变了算法对于可计算性以及计算复杂度的认识

算法3：扫描所有元素，储存一个计数器与对应元素。当扫描到的元素与存储元素相同时，给计数器加1；当扫描到元素与存储元素不同时，给计数器减1；当计数器归零时，重新开始。

性质：如果存在Majority，则扫描完毕时，存储元素一定是Majority

时间复杂度O(N)空间复杂度：O(1)

扫描第二遍，确定候选元素是否为Majority

Majority算法分析

定理：如果一个元素出现次数超过N/2，那么它一定会被存储

N=数据流中的元素个数

每次减一操作可以看成将两个不同元素抵消（当前计数器的元素以及当前扫描到的元素）

总共有N个元素可以抵消

最多能执行N/2此减一操作

如果一个元素出现次数超过N/2，那么它最多被减N/2次，因此一定会被存储。

9、Misra-Gries算法是什么？如何证明？

输入：N个元素，整数k

输出：出现次数超过N/k的元素

算法：保存k-1个元素与其对应的计数器，对于每一个新纪录

如果该元素已经被记录，则该元素对应的计数器加一

否则如果未满k-1个元素，则记录新元素，计数器设置为1

否则所有计数器减一，移除计数器为的元素

定理：如果一个元素未被记录，它出现的次数不会超过N/k

N=数据流中的元素个数

误差

每次减一，我们减去了k个元素：1个新元素和k-1个老元素

最多能减掉N个元素

最多能产生N/k次所有元素减一操作

1%误差->99个计数器

10、Misra-Gries合并算法是什么？如何证明？

输入：两个摘要MG1和MG2，参数为k，元数据大小为N1和N2

输出：合集的摘要MG12

算法一：对应计数器相加，但是摘要变大了。

算法二：找出第k大计数器Ck，从所有计数器中减去Ck，移除为负数或者为的计数器

课后证明：该算法是否能保证合并后的摘要误差不超过（N1+N2）/k

11、基于哈希的近似算法——布隆过滤器的定义、构造及分析

布隆过滤器

1970年由布隆提出

针对字典问题（dictionary problem）

输入：一个集合S，大小为n

查询：给定一个元素x，问x是否属于S

字典问题是很多问题的抽象：路由器查找URL，数据库查找记录是否存在

优点：空间效率和查询时间都远远超过一般的算法

缺点：有一定的误识别率和删除困难

布隆过滤器（Bloom Filter）的构造

使用一个长度为m的0-1比特数组（m就是布隆过滤器的长度），以及k个哈希函数h1….hk

插入元素x：将h1(x)….hk(x)设为1

查询元素x是否属于S：检测h1(x)….hk(x)是否都为1

性质：若x属于S，则h1(x)….hk(x)都为1

若x属于S，则h1(x)….hk(x)已经被设为1，回答正确，布隆过滤器没有false negative

若x不属于S，h1(x)….hk(x)仍然有可能被其他元素设为1，可能出现错误。布隆过滤器有可能出现false positive

布隆过滤器分析

布隆过滤器出现false positive的概率

某个元素y和某个哈希函数hj将h1(x)设为1的概率：1/m

一共有n个元素，k个哈希函数

H1(x)没有任何元素的哈希值设成1个概率：（1-1/m）^kn

H1(x)…..hk(x)中全部被设成1的概率为（1-（（1-1/m）^kn））^k

N=1 billion m=8 billion

K=1: false positive=0.1175

K=2: false positive=0.0493

当我们增加K时，false positive的概率会先降后升

K的最优值：m/n ln(2)

12、何为计数布隆过滤器？

计数布隆过滤器（counting bloom filter），支持删除

将m个比特改为m个计数器

插入元素x：将h1(x)….hk(x)对应的计数器加1

删除元素x：将h1(x)….hk(x)对应的计数器减1

由于哈希函数平均分配元素，每个计数器无需记录太多元素

可证明：在没有重复元素的情况下，每个计数器只需要4比特

布隆过滤器仍然是一个活跃的研究领域，在数据库中通常被称为“signature file”

参考资料：

MOOC中国人民大学《数据库系统概论（新技术篇）》

第17讲大数据近似算法魏哲巍