学习笔记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讲大数据近似算法魏哲巍

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181010G0I1N600?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励