《流数据分析技术》课件03-流数据概要结构-.pptx

1、1流数据概要结构2抽样概要结构3草图概要结构4直方图概要结构5小波概要结构 概要数据结构（Synopsis Data Structure）一种按照流数据处理模型，使用一定流数据分析技术，构建出的一个流数据的主要特征集 目的 对流数据关键特征的抽取，以方便应用快速查询 为其他更深度的流数据特征挖掘提供基础2 抽样（Sampling）从原始数据集N中抽取小部分样本形成样本集S，代表整合数据集，以减小数据集规模 保证样本集与原始数据集的同分布，可以将传统数据挖掘处理方法应用到概要数据结构上 草图（Sketches）用专用数据结构抽取流数据特征，以快速抽取常用的统计型的指标，以减小内存占用并降低处理时

2、延 在最少的空间占用和最快的查询速度之间进行平衡，加速对流数据特征的查询响应速度3 小波（Wavelets）小波是一种通用的数字信号处理技术，类似于傅立叶变换，可根据输入的模拟量，变换成一系列的小波参数 用多阶误差树来刻画原始数据，高阶系数反映数据的大趋势，低阶系数反映更局部的趋势 直方图（Histograms）将大数据集按照一定规则划分为小数据集（桶，bucket），通过对每个小数据集的特征分析来刻画大数据集的特征轮廓 通过与抽样、小波、草图等不同的方法整合，实现对概要结构的不同轮廓的刻画41流数据概要结构2抽样概要结构3草图概要结构4直方图概要结构5小波概要结构 抽样（Sampling）从

3、原始数据集 N 中抽取小部分样本形成样本集 S代表整个数据集 目的：减小数据集规模，使得传统数据挖掘算法能够被应用到大规模数据集或流数据集 特点 是一种近似技术 能够提供可证明的无偏估计和误差保证 易于应用到高维场景6 设 流数据全集为：N 数据内容为：X1Xn 预期的数据挖掘结果：f(N)获得函数 抽样 基于抽样集合：S 获得抽样函数：f(S)条件：能够通过对函数 f(S)的均值 和标准差 等的计算 估计函数 f(N)用于估计 f(S)概率界限的这些不等式被称为尾界 （Tail Bounds）7 均匀抽样（Uniform Sampling）数据集 N 中不同元素入选样本集合 S 的概率相同

4、如：使用固定的时间间隔进行抽样 偏倚抽样（Biased Sampling）数据集 N 中不同元素入选样本集合 S 的概率不同 如：考虑空间网格划分，基于密度不同设置不同的概率进行抽样 混合抽样 均匀抽样与偏倚抽样联合8 伯努利抽样（Bernoulli Sampling）设：数据集 N 中各元素 X1Xn 服从伯努利分布（Bernoulli Distribution，或称0-1分布）入选概率：p(0,1 落选概率：q=1-p 抽样概率：P(S;N)=p|S|(1-p)|N|-|S|优点：采样均匀，过程简单，时间成本低 缺点：需要对数据集分布概率需要有预知 水库抽样（Reservoir Sampl

5、ing）设：样本集 S 的大小为 s 入选：第 n 个抽样样本的入选概率为 s/n 去除：如果当前样本集合中的样本量超过抽样集大小 s，从样本集合 S 中随机去除一个样本 优点：各元素入选抽样数据集合的概率相同（随机均匀抽样）9pppps/n s/n s/ns/n随机删除随机删除 简明抽样（Concise Sampling）扩展水库抽样，每个采样点一个计数器 入选：1/1/（，概率逐渐变小）去除：/优点：支持重复数据均匀抽样 链式抽样（Chain Sampling）针对滑动窗口 设：滑动窗口大小 W 入选：第 n 个抽样样本的入选概率 1/min(n,W)替换：从n+1n+W中随机选择备选样本

6、，在抵达时替换当前样本（随机选择）粘性抽样（Sticky Sampling）有损计数（Lossy Counting）101/概率删除概率删除1/1/1/1/min(2,W)1/min(3,W)1/min(4,W)n+1n+WW 计数抽样（Counting Sampling）设：样本集 S 的大小为 s 入选：样本量超过抽样集大小 s 时，首先将参数 提高到，先以概率/，之后以概率 1/判断样本集中的样本计数器是否减 1 去除：如果样本计数器取值减为 0，则删除样本 有效获得数据集中的热门元素 加权抽样（Weighted Sampling）带权值的偏倚抽样 将使用率高的小数据集赋予更大的权重，以

7、体现数据集的实际分布11/1/普遍命中随机命中谁被减为0的概率大？60%30%10%国会抽样（Congressional Sampling）将数据集进行分组，不同分组内进行独立的水库抽样，不同组之间使用加权抽样 大组抽样率比小组高 兼顾组内的公平性和组间的影响力 分层抽样（Stratified Sampling）利用数据分布的历史经验对数据进行分层 重要的层被设置为大组，抽取更多的采样点 正确体现数据的重要特征1260%30%10%组内均匀抽样高频组中频组低频组组间加权抽样均匀抽样13均匀抽样要求：数据的抽样分布与原始分布一致方法：对每个到达的数据按照相同的概率进行判断“去”或“留”14ppp

8、p12345678910111213141516171819202122例如：一个伯努利序列（0-1分布）N 1234567891011S pppppppppppppppppp原始序列 N 的均值 0.5采样序列 S 的均值 0.545用0.5采样率能获得与原始序列相同分布的子序列吗？分析 n 为随机变量个数，H(n)为 n 次处理出现成功的次数（真值）TRUE的概率 p，FALSE的概率 q=1-p（pn：预测值）在 n 次处理过程中，成功次数不超过 k 次的概率为：当 k=(p-)n 时Hoeffding不等式 当 k=(p+)n 时Hoeffding不等式 合并 设 取值 误差 的概率边

9、界15n22 0.37483590.995867865 0.25341930.999526680 0.23404130.99968751150.20312630.9998488n2600.14624380.99997043200.1342610.99998054600.11545020.999990565050.03673941 复习一下置信度与置信区间 无法预计准确值只能提供一个估计 如果有70%样本落在实际取值中心 正负偏差 到+之间 置信度：70%置信区间：（均值标准差）目标：伯努利抽样的抽样结果与原序列具有相同分布的置信度满足要求1670%设 X 均值（均值 ）预期的下界Xi 属于 a

10、i,bi误差为 t（标准差 ）对于伯努利分布 Xi 属于 1,0均值超出误差的概率下界为（1-置信度）为避免均值超出误差采样 n 的取值例如 输入序列符合伯努利分布（0-1分布）如果希望 t 0.1 0.117则=65tn0.10.050.010.165801150.052603204600.01650580101150518例如：一个伯努利序列（0-1分布）tn0.10.050.010.165801150.052603204600.016505801011505 如果希望 t 0.05 0.05n 320注意：这里说的是什么问题？必须采样到320才行？12345678910111213141

11、516171819202122N 1234567891011S 窗口内的实际数据量要不小于32019(0,1 随机数落选概率向下取整()：步长=0：选当前元素0：跳过元素m=m+1 指示下一个入选点的位置注意：也是入选概率20取值取值0.10.20.30.40.50.60.70.80.90.121.85 10.32 6.46 4.51 3.32 2.51 1.91 1.43 1.00 0.215.28 7.21 4.51 3.15 2.32 1.76 1.34 1.00 0.70 0.311.43 5.40 3.38 2.36 1.74 1.31 1.00 0.75 0.52 0.48.70

12、4.11 2.57 1.79 1.32 1.00 0.76 0.57 0.40 0.56.58 3.11 1.94 1.36 1.00 0.76 0.58 0.43 0.30 0.64.85 2.29 1.43 1.00 0.74 0.56 0.42 0.32 0.22 0.73.39 1.60 1.00 0.70 0.51 0.39 0.30 0.22 0.15 0.82.12 1.00 0.63 0.44 0.32 0.24 0.19 0.14 0.10 0.91.00 0.47 0.30 0.21 0.15 0.11 0.09 0.07 0.05 10.000.000.000.000.0

13、00.000.000.000.00比例0.12350.23260.35710.45450.5556 0.6667 0.7692 0.8333 0.9091随机数取值（均匀分布）入选概率取值m=0m=m+1020406080100120140160180p=0.10510152025303540p=0.50510152025p=0.9实际步长 需要预知数据的分布特征无法应对概念漂移 可以支持滑动窗口，但是只能代表窗口内数据的采样结果，并不是整个流数据的无偏估计无法预计流数据大小，因此也无法预计对整个流数据的采样率2112345678910111213141516171819202122N 123

14、4567S 45678910S 均匀抽样22 均匀抽样 要求：数据的抽样分布与原始分布一致2312345678910111213141516171819202122N S S 1234567891011121323467910111215161922目标：在抽样完成后，获得大小为 S 的无偏样本 均匀抽样 目标：在抽样完成后，S 中的每一个元素都是按照 S/N 的概率抽取 问题：由于流数据的特点，无法预知 N 的大小2412345678910111213141516171819202122N S 24568911121316192012122以多大的概率入池？以多大的概率将池中的哪个元素删除？

15、算法思路 第1s个元素，按照概率 1 入池 后继第 n 个元素，按照 s/n 概率入池 池中元素，按照 1/s 概率删除2512345678910111213141516171819202122N S 24568911121316192012122s/n1/s1/1313/21s/n13/22概率删除概率入池26s/N27初始抵达元素全部入池kU：0k的随机数以 1/k 的概率，用入池的数据元素替换掉蓄水池中的原有元素抵达元素是下一跳元素Data Stream Management：Processing High-Speed Data Streams p2128找到最小的，使其概率恰巧小于U就

16、是必须得入池的步数s/(n+1)入池概率1-s/(n+1)不入池概率(1-s/(n+1)个都不入池概率使用最优化方法避免计算超范围*A.M.Law,Simulation Modeling and Analysis,4th edn.(McGraw-Hill,New York,2007)均匀抽样29 均匀抽样 要求：数据的抽样分布与原始分布一致3012345678910111213141516171819202122N S 12345678910111213如果流数据中存在大量的重复元素，水库抽样存在的问题：样本集中需要存储大量重复样本，空间利用率低 简明抽样（精确抽样）设：样本集 S 的大小为

17、s 阈值参数（初始化取值1）入选：样本量小于抽样集大小 s，以概率 1/入选（计数器+1）样本量大于抽样集大小 s，以概率 1/入选（）去除：样本量大于抽样集大小 s，以概率/选择样本集中的样本，将计数器减 1（)直到某一样本计数器取值减为 0，删除样本 特点：随数据流推进，抽样概率逐渐降低 适合重复数据较多的情况3132S110S221S333S411S57S62S715S88102133721581021331071589203196137以概率/=0.91选择样本=1=1.1以概率/=0.91选择样本-1-1多次迭代，/=0.91，样本被选中概率很高普遍都减了几次低频率的样本被首先减到0

18、33 面向具有重复项的流 以概率/删除样本集元素 高频度的元素更大概率保留 低频度的元素更大概率删除 以概率 1/选择新元素 出现新元素的时候，抽样率降低，抽到低频新元素的概率也低了 低抽样率对高频新元素被抽到的概率影响不大 如果出现概念漂移 全时段都低频度的元素更易被删除 曾经高频出现的元素更易被保留 特点：是数据流的无偏抽样元素存在：频度增加 删除低频元素增加新元素/元素不存在：偏倚抽样34 是数据流的无偏抽样 如果样本集空间有限，高频特征会更易于体现 如何能多保留一些低频特征？35删除低频元素增加新元素低频特征也可能很重要元素存在：频度增加 元素不存在：计数抽样（Counting Sam

19、pling）设：样本集 S 的大小为 s 阈值参数（初始化取值1）入选 样本量小于抽样集大小 s，以概率 1/入选（计数器+1）样本量大于抽样集大小 s，以概率 1/入选（）去除：样本量大于抽样集大小 s，先以概率/，后以概率 1/选择样本集中的样本，将计数器减 1（)如果样本计数器取值减为 0，则删除样本 与简明抽样的差异 多了“以概率 1/选择样本集中的样本”3637S110S22S333S43S57S62S715S8810233721581023322158913161137以概率/=0.95选择样本=1.8=1.9以概率 1/=0.53选择样本-1-1多次迭代，/=0.95，样本被选中

20、概率很高1/=0.53，样本被选中的概率就没那么高普遍都减了几次但不一定最低频率的样本被首先减到0可能相近的样本被首先减到038/1/随机命中随机命中使得高频度的元素被减为0的概率加大，低频度的元素更易于保留在样本集删除低频元素增加新元素频度增加删除的不一定是低频元素增加新元素简明抽样计数抽样/普遍命中1/元素存在：频度增加 元素不存在：1流数据概要结构2抽样概要结构3草图概要结构4直方图概要结构5小波概要结构 草图（Sketches）使用概率数据结构（Probabilistic Data Structures）来抽取流数据的特征，以减小内存占用并降低处理时延 本质是随机投影技术在时间序列领域

21、的扩展，能够用于估计流数据集的二阶矩大小、自连接大小、热门元素列表等 随机投影（Random Projection）理论依据：J-L Lemma公式*核心思想：降维将高维欧氏空间里的点集映射到低维空间，相对距离得到某误差范围内的保持 将时间序列的长度当作维度，可以将这个原理扩展到时间序列域 可以在给定长度的滑动窗口上执行相同的计算*https:/en.wikipedia.org/wiki/JohnsonLindenstrauss_lemma 设 数据点维数：d 随机向量维数：k 随机向量 k 的每一个分量是平均值和单位方差为零的正态分布 随机投影 计算维数 d 的数据点与随机向量 k 的每一个

22、分量的点积，将数据点投影到维数 k 的坐标系 数据点之间的距离在变化前后能够被近似的保持下来 距离值的精度界限仅取决于 k 41维数：d维数：k42 Johnson-Lindenstrauss Lemma 布隆过滤器 判断新抵达的数据元素是否存在于数据集中，如判断到达的数据元素是否曾经被访问过 计数布隆过滤器CBF（Counting Bloom Filter）SBF（Spectral Bloom Filter）计数草图 统计流数据中某元素的出现频率（不需精确计数）CM草图（Count-Min Sketch）CMM草图（Count-Mean-Min Sketch）FM草图 判断数据的基数（Car

23、dinality），即数据集中不同元素的个数 FM草图（FM-Sketch）43 布隆过滤器（Bloom Filter）基础方法 创建长度为m的BIT数组BITMAPm 投影：用哈希函数将数据元素映射到0 m-1之间 冲突避免：多个哈希函数，选全1的结果 计数布隆过滤器（CBF：Counting Bloom Filter）BF改进，支持计数 频率布隆过滤器（SBF：Spectral Bloom Filter）BF改进，支持出现频率判断44C010101HHTRUEC010102HHTRUE&1 CM草图（Count-Min Sketch）基础方法 创建长度为m的计数器数组COUNTMAPm 计

24、数：用哈希函数将数据元素映射到0 m-1之间 冲突避免：多个哈希函数，选映射值最小的 CMM草图（Count-Mean-Min Sketch）CM改进，进一步避免冲突 冲突避免：取所有计数器的中位数 CML草图（Count-Min-Log Sketch）CM改进，避免计数器浪费空间 计数：以 x-c 的概率增加计数器（x为大于1的log底，c为当前需要插入元素的估值）45C12HHC12HHMM00.10.20.30.40.50.6024681012投影分布概率 FM草图（Flajolet-Martin Sketch）判断数据的基数（Cardinality）设“在一个整数集中，取值为2K 的数

25、其二进制比特序列将存在 K 个 0 组成的尾部”使用一个非均匀的投影函数，将小于基数 m 的数据大概率分布在 k 以下，使得 m 接近 2k 的取值 如果存储器大小 L m，则大于 m 的取值出现概率非常小46布隆过滤器47 面临的问题：统计流数据中某元素是否出现过 如果不需精确判断呢？（允许一定的误判率）48设置标识位记录是否存在如何快速的查找标识位？哈希表存在的问题：精确查找 空间消耗大（填充率50%）超过填充率性能急剧下降32bit整数：200,000,0004Bytes763MBytes 布隆过滤器 BF（Bloom Filter）1970年Burton Bloom在论文Space/t

26、ime trade-offs in hash coding with errors中提出 核心思想 用一系列随机映射函数解决一个映射函数的冲突问题 用一个很长的二进制向量来解决存储空间爆炸问题 准确率换空间思想延伸 优点：空间效率和查询时间都远超过一般的算法 缺点：有一定的误识别率，删除困难49 用一个很长的二进制向量来解决存储空间爆炸问题 用一个包含m位的二进制位数组存储BITMAP12345678mHashData1Data2m-1m-2m-3m-4m-5m-6m-7BITMAP00010000000000000000100000000000如果冲突怎么办？Data300001000000

27、00000 用一系列随机映射函数解决一个映射函数的冲突问题 K个相互独立的哈希函数映射到1,m的范围12345678mH1H2H3HkData10001001001000100m-1m-2m-3m-4m-5m-6m-7Data20001001000010010BITMAP 避免冲突 将 d 维数据投影到 1 维的时候，可能产生冲突 用相互独立的 k 维投影，避免冲突 共享空间 k 维投影共享同一个空间，提高空间利用率520000001000000000d 维数据HASH 1HASH 20001000000000000HASH 30000000000001000HASH k00000000100

28、00000投影到2维投影到1维投影到3维投影到k维 构建 n 个元素集合 S=x1,x2,xn 包含 m 位的二进制位数组 BITMAPm k 个相互独立的哈希函数，输入映射到 1,m 范围 S 集合中的每个元素用 k 个哈希函数映射到1,m范围，并将BITMAP相应的位置设置为1初始化时m 位数组置零对集合中的每个元素xj 分别进行k 次hash，If Hi(xj)=a,set Ba=1.0000000000000000BITMAP0100101001110110BITMAP 使用 判断数据 y 是否在集合 S=x1,x2,xn 中存在 计算 y 的 k 个哈希函数的取值 判断BITMAP相

29、应的位置取值是否为1540110111001110110BITMAPH1H2H3HkData3Data40110 存在误报 哈希函数存在冲突 BITMAP中的每一位是 k 个哈希函数映射结果的叠加550111111001110111BITMAPH1H2H3HkData1Data2Data3假阳性 FP（False Positive）当集合 S=x1,x2,xn 的所有元素都被 k 个哈希函数映射到 m 位的位数组中时，位数组中某一位是0的概率是：构建布隆过滤器后某一位为1的概率是1-q 假阳性率（False Positive Rate）就是一个不在集合中的字符串经过 K 次Hash后对应的位都

30、为1的概率：mknknemq/)11(kkmknqef)1()1(/Hash函数的个数 k 不是越大越好，k 如何取才能使得 f 最小 q=1/2时错误率最小，也就是让一半的位空着)1ln()ln(g 最小f最小时，g所以当#)#1ln(g令)1ln(exp()1()1(/qqnmekekfeqfmknmknkmknknmnmk*693.0*2ln 假设允许的False Rate为p 假阳性率（False Positive Rate）随Hash函数个数和存储空间增加成指数级降低(1/p)log*1.44*n (1/p)log*e log*222nmm/nkk=1k=2k=3k=4k=5k=6k

31、=7k=8k=9k=1021.390.3930.400 32.080.2830.2370.253 42.770.2210.1550.1470.160 53.460.1810.1090.0920.0920.101 64.160.1540.08040.06090.05610.05780.0638 74.850.1330.06180.04230.03590.03470.0364 85.550.1180.04890.03060.0240.02170.02160.0229 96.240.1050.03970.02280.01660.01410.01330.01350.0145106.930.09520.

32、03290.01740.01180.009430.008440.008190.00846117.620.08690.02760.01360.008640.00650.005520.005130.005090.00531 128.320.080.02360.01080.006460.004590.003710.003290.003140.003170.00334139.010.0740.02030.008750.004920.003320.002550.002170.001990.001940.00198149.70.06890.01770.007180.003810.002440.001790

33、.001460.001290.001210.00121510.40.06450.01560.005960.0030.001830.001280.0010.0008520.0007750.0007441611.10.06060.01380.0050.002390.001390.0009350.0007020.0005740.0005050.000471711.80.05710.01230.004230.001930.001070.0006920.0004990.0003940.0003350.0003021812.50.0540.01110.003620.001580.0008390.00051

34、90.000360.0002750.0002260.0001981913.20.05130.009980.003120.00130.0006630.0003940.0002640.0001940.0001550.0001322013.90.04880.009060.00270.001080.000530.0003030.0001960.000140.0001088.89e-052114.60.04650.008250.002360.0009050.0004270.0002360.0001470.0001017.59e-056.09e-052215.20.04440.007550.002070.

35、0007640.0003470.0001850.0001127.46e-055.42e-054.23e-052315.90.04250.006940.001830.0006490.0002850.0001478.56e-055.55e-053.92e-052.97e-052416.60.04080.006390.001620.0005550.0002350.0001176.63e-054.17e-052.86e-052.11e-052517.30.03920.005910.001450.0004780.0001969.44e-055.18e-053.16e-052.11e-051.52e-05

36、26180.03770.005480.001290.0004130.0001647.66e-054.08e-052.42e-051.57e-051.1e-052718.70.03640.00510.001160.0003590.0001386.26e-053.24e-051.87e-051.18e-058.07e-062819.40.03510.004750.001050.0003140.0001175.15e-052.59e-051.46e-058.96e-065.97e-062920.10.03390.004440.0009490.0002769.96e-054.26e-052.09e-0

37、51.14e-056.85e-064.45e-063020.80.03280.004160.0008620.0002438.53e-053.55e-051.69e-059.01e-065.28e-063.35e-063121.50.03170.00390.0007850.0002157.33e-052.97e-051.38e-057.16e-064.1e-062.54e-063222.20.03080.003670.0007170.0001916.33e-052.5e-051.13e-055.73e-063.2e-061.94e-06http:/pages.cs.wisc.edu/cao/pa

38、pers/summary-cache/node8.html BF/SBF（Standard Bloom Filter）m长BITMAP的每一个槽位只有1位，只能表示0,1，代表“有”或“无”缺点：无法删除数据 计数型布隆过滤器 CBF（Counting Bloom Filter）将m长BITMAP的每一个槽位修改为多位，形成COUNTER_MAP，如3位，则可以表示0,1,7 优点：可以删除数据 插入数据时，Counter自增；删除数据时，Counter自减 基本思想：元素 x 对应的 k 个counter中的最小值 mx=出现频率 fx fx mx 的概率与SBF的误判概率相同5016111

39、210 SBF（Standard Bloom Filter）在 q 最小的时候，BF的装载率约50%SBF固定大小无法扩展 动态布隆过滤器 DBF（Dynamic Bloom Filter）-多个稍小的SBF代替一个大SBF-预设SBF的容量，插入超过容量时创建新SBF计数草图63 面临的问题：统计流数据中某元素的出现频率 如果不需精确计数呢？64设置计数器记录频率如何快速的查找计数器？哈希表存在的问题：精确查找 空间消耗大（填充率50%）超过填充率性能急剧下降32bit整数：200,000,0004Bytes763MBytes 数据结构 设置 d 个哈希函数 H，每个哈希函数的取值范围为 1

40、,w 设置 dw 个计数器数组 COUNTMAPd,w 计数增加 哈希函数的编号对应行，哈希函数的输出对应列，数组单元自增 计数查询 哈希函数的编号对应行，哈希函数的输出对应列，取最小值65wd66即，希望查询结果小于因子 的概率大于 对于一个序列，元素的频度不等式成立的概率至少为 对于在这一定理条件下，CM草图参数取值：An Improved Data Stream Summary:The Count-Min Sketch and its Applications设 问题 CM草图每次都要进行 d 次哈希计算 核心思想 在CM草图之前增加一个过滤器，用于缓存高频度的计数器，并记录该计数器的计

41、数差值 操作 先查询过滤器，如命中则仅更新过滤器，未命中但过滤器未满则插入过滤器并更新计数器 更新计数器的时候如果发现计数器的值大于过滤器的最小值，则交换 优点：高频记录优先命中过滤器，提高查询速度67FM草图68 面临的问题：如何估计流数据的基数 基本思路 基本假设：“在一个整数集中，取值为 2K 的数其二进制比特序列将存在 K 个 0 组成的尾部”含义：只要保证尾部出现 0 的概率 出现 1 的概率，则这个整数就会趋向于尾部全 0 的取值69501632974811？要用哈希表保存每一个到达的数据吗？2K+2K-m+2K-n 2K 如果 m、n 等足够小27=12827+24=144703

42、2112345671/232/23=1/224/23=1/21 LL-1k321m/2Lm/2L-1m/2km/22m/210 例如 m=16，L=8 将第一个0的位置设置为 k，则可以考虑 m 的取值为 2k718765432116/2216/2116/2316/2416/2616/2516/2716/2816/416/216/816/1616/6416/3216/12816/256被选中的概率越来越小以极大的概率被选中，置 10000111150123467k 置位方法 定义一个哈希函数 H(x)将数据元素均匀地映射到 1,2,3,.2L 1 定义 BITMAP0 L-1 数组，标识经过

43、H(x)计算后，再取log2，四舍五入后取值的映射位置（2K 的 K 的对应位置）判断方法 取BITMAP中 0 出现的最小位置为 K K 的数学期望为 方差为(R)1.12 基数 m 的取值：2K/720010111111XiH(x)Log2(H(x)=4.95 525-1=3150123467891流数据概要结构2抽样概要结构3草图概要结构4直方图概要结构5小波概要结构 直方图（histogram）将一个大数据集按照一定规则划分为小数据集（桶，bucket）通过对每个小数据集的特征分析，来刻画大数据集的特征轮廓 注意 直方图并不一定按照时间/空间顺序排列 不同维度、不同特征按照不同原则描绘

44、出不同的分布特征直方图与原始数据并不需要空间一一对应 等宽直方图（Equi-Width Histogram）把数据离散成相等的桶（等长、等宽或等深），并分别在桶上统计特征 压缩直方图（Compressed Histogram）针对特征分布不均匀情况 在等宽直方图基础上，为热门元素单独创建桶 指数直方图（Exponential Histogram）桶的容量按照不同级别呈指数递增 低级别的桶的数量如果超出阈值，则合并该级别最“旧”的两个桶，放到高一级别中 低级别的桶存储的都是最新的数据，越高级别的桶存储的越是旧的数据75桶相等桶相等，内容不同桶不等，指数分布 V-优化直方图（V-Optimal H

45、istogram）使各桶的方差之和最小 不经过遍历难以确定各个桶的方差之和，无法应用在流数据环境 小波直方图 使用小波分解获取频域特征 用不同的分解层级做桶 草图直方图 使用草图获取统计特征 用不同的草图输出等级做桶76k1k2k3每一个桶都能还原信号，还原粒度不同 等宽直方图 使用固定的取值宽度（等宽）或固定的元素数据量（等深）的桶来进行分割77取值宽度相等（等宽）很容易计算不同数量比例如：获取分位点（Quantile）元素数量相等（等深）类比内容滑动窗口如：固定样本数量取特征1流数据概要结构2抽样概要结构3草图概要结构4直方图概要结构5小波概要结构 小波（Wavelet）小波变换本质是对时

46、空频率进行伸缩平移运算，将数据特征分解成一组小波函数和基函数（将输入模拟量变换成一系列小波参数）高阶系数反映了数据的大趋势，低阶系数反映了更局部的趋势（选择少数小波参数就可以近似还原原始信号）可以对信号（函数）进行多尺度的细化 离散小波变换（DWT：Discrete Wavelet Transform）向量 S=(x1,x2,x3,xn)m 个小波系数 (cl,c2,cm)设序列 S 的长度 n 是 2 的幂，哈尔小波分解为 k 阶，即分解为2(k-1)个系数 哈尔小波分解过程可表示成树形结构误差树（Error Tree）79每个树中间节点 ci 为对应的小波系数每个叶子节点 xi 为对应的原始数据k 为小波分解的层级重构 xi 的时候，xi 的取值仅与从根节点到叶结点的路径有关80误差树（Error Tree）1流数据概要结构2抽样概要结构3草图概要结构4直方图概要结构5小波概要结构6小结82