大数据分析分享部分.ppt

《大数据分析分享部分.ppt》由会员分享，可在线阅读，更多相关《大数据分析分享部分.ppt（83页珍藏版）》请在三一文库上搜索。

1、电子商务新进展大数据分析, 0551-62904991,刘业政,2019年3月19日,一、大数据时代 二、大数据分析基础 三、相似项发现 四、流数据分析,提纲,一、大数据时代 二、大数据分析基础 三、相似项发现 四、流数据分析,2019年3月19日,一、大数据时代 二、大数据分析基础 三、相似项发现 四、流数据分析,提纲,一、大数据时代 二、大数据分析基础 三、相似项发现 四、流数据分析,2019年3月19日,准备知识,向量空间模型(Vector Space Model)：模型根据文本中的词汇出现在整个文本集中的频次为每个词汇计算出一个权重，形成关于该文本的向量空间。 假定文档集中有N篇文档，

2、词项i出现在ni个文档中且在文档j中出现的次数为fij ，文档j包含的词数为fj，则： TF(Term Frequency): TFij=fij/fj IDF(Inverse Document Frequency)：IDFi=log2 N/ni 则词项i在页面j上的权重wij计算如下： wij=TFijIDFi （TFIDF模型：有多种计算策略）,2019年3月19日,准备知识,哈希函数h：将哈希键值（整数）随机化。 输入：哈希键值(hash-key) 输出：桶编号(bucket number) 不同类型的数据都可以转化成比特位序列，从而都可以解释为整数。 用哈希函数构建索引 输入：用于建立索

3、引的一个或多个字段 输出：桶编号，每条记录映射到一个桶，具有相同输入的不同字段，可以映射到同一个桶。 其他相关知识：磁盘存储、幂律分布,2019年3月19日,基于Map-Reduce的基本运算,矩阵-向量乘积 假定矩阵M=mijnn，向量V=vjn, n足够大，但V可以一次读入内存 Map函数：每个Map任务将整个向量V和矩阵M的一个文件块作为输入。对每个矩阵元素mij，Map任务会产生键值对(i, mijvj)。例如， (i, mi1v1), (i, minvn) Reduce函数：Reduce任务将所有与给定键i关联的值相加即可得到。,2019年3月19日,基于Map-Reduce的基本运

4、算,矩阵-向量乘积 假定矩阵M=mijnn，向量V=vjn, n足够大且V无法一次读入内存 处理思路： 将M分割成k个宽度相等的垂直条，对应的将V分成k个高度相等的水平条。分割后的每个水平条都能够放入内存。 将每个垂直条、水平条都存成一个文件 这样就转换成向量可读入内存的矩阵-向量乘积。,2019年3月19日,基于Map-Reduce的基本运算,关系选择 对关系R的每个元组应用条件C，得到仅满足条件C的元组，记为C(R)。(select * where C from R) Map函数：对R中的每个元组t，检测它是否满足C。如果满足，则产生一个键值对(t,t)。键和值都是t。 Reduce函数：

5、类似于恒等运算，将每个键值对传递到输出部分即可。,2019年3月19日,基于Map-Reduce的基本运算,关系投影 对关系R的某个属性子集S，从每个元组中得到仅包含S中属性的元素。记为S(R)。 (select S from R) Map函数：对R中的每个元组t，剔除t中属性不在S中的字段得到元组t，输出键值对(t, t)。将可能存在t相同的多个键值对转换成键值表对，即(t,t,t,t) Reduce函数：将(t,t,t,t)转换成(t, t)输出，以保证对任意键t仅产生一个键值对(t, t)。,2019年3月19日,基于Map-Reduce的基本运算,分组与聚合 设关系为R(A,B,C)，

6、分组：按照属性子集A对元组进行分割，A的所有属性值相同的元组分为一组。聚合：对每个组中所有元组的B属性值进行运算， 运算包括sum, count, avg, min, max。A,(B)(R)，A、B由用户指定。 Map函数：对R中的每个元组(a,b,c)，生成键值对(a,b) Reduce函数：对于相同的键a，输入到对应的Reduce任务的键值表对为(a,b1,.,bn) ，对值表b1,.,bn进行操作，得到结果x。则键a对应的输出为：(a, x),2019年3月19日,基于Map-Reduce的基本运算,两个关系的并 对两个属性集相同的关系R、S中的所有元组进行“并”操作。Union (R

7、, S) Map函数：将每个输入元组t转变为键值对(t,t)。输入文件可能来自关系R的文件块，也可能来自关系S的文件块。 Reduce函数：和每个键关联的可能有一个值或两个值，两种情况下都输出(t, t)。,2019年3月19日,基于Map-Reduce的基本运算,两个关系的交 对两个属性集相同的关系R、S中的所有元组进行“交”操作。Intersection (R, S) Map函数：将每个输入元组t转变为键值对(t,t)。 Reduce函数：和每个键关联的可能有一个值或两个值，如果键值表对为(t,t,t)，则输出(t,t)；若键值表对为(t,t)，则输出(t,NULL),2019年3月19日

8、,基于Map-Reduce的基本运算,两个关系的差 对两个属性集相同的关系R、S中的所有元组进行“差”操作。Difference(R, S)=R-S Map函数：将每个输入元组t转变为键值对(t,R)或(t,S)。 Reduce函数：输入到Reduce函数的键值表对有三种情况，即(t,R), (t,S), (t,R,S) ，如果键值表对为(t,R)，则输出(t,t)；否则输出(t,NULL),2019年3月19日,基于Map-Reduce的基本运算,两个关系的自然连接 给定两个关系R(A,B)、S(B,C)，B是R、S的所有共同属性子集。比较R、S的每对元组，若两个元组关于子集B的所有属性值相

9、同，则生成一个新元组(A,B,C)。RS Map函数：对于R的每个元组(a,b)，生成键值对(b, (R, a)；对于S的每个元组(b, c)，生成键值对(b, (S, c) 。 Reduce函数：对于相同的键b，输入到对应的Reduce任务的键值表对为(b,(R,a1),.,(R,am); (S,c1),(S,cn) ，则键b对应的输出为： (b, (a1,b,c1),(a1,b,cn),(am,b,c1),(am,b,cn) 连接运算可能导致元组数目大大增加。,2019年3月19日,基于Map-Reduce的基本运算,矩阵乘积 假定矩阵M=mijml，N=njkln 处理思路： 将M、N分

10、别看成两个关系M(I, J, V)、N(J, K, W)，对应的元组分别为(i, j, mij)和(j, k, njk) 。 将矩阵乘法转换为两个关系的自然连接与分组和聚合运算。,2019年3月19日,基于Map-Reduce的基本运算,矩阵乘积（两步运算） Map1函数：将mij转换为(j,(M,i,mij)，将njk转换为(j,(N,k,njk) Reduce1函数：对于每个键j，输入到指定Reduce任务的键值表对为(j,(M,1,m1j),(M,m,mmj); (N,1,nj1) , , (N,n,njn)，输出为(j,(i,k, mijnjk),; i=1,m; k=1,n) Map

11、2函数：将Reduce的输出作为Map2的输入，输出键值对(i,k), mijnjk) Reduce2函数：对于每个键(i,k)，输入到指定Reduce任务的键值表对为(i,k),mi1n1k, mi2n2k, milnlk)，计算与键(i,k)关联的所有值之和v= mi1n1k+mi2n2k+milnlk ，输出(i,k),v)，v是矩阵P=MN的第i行第k列的元素值。,2019年3月19日,基于Map-Reduce的基本运算,矩阵乘积（单步运算） Map函数：将mij转换为(i, k),(M,j,mij)，k=1,n；将njk转换为(i, k),(N,j,njk)，i=1,m Reduce

12、函数：每个键(i,k)关联的值为(M,j,mij)和(N,j,njk)，j=1,2,l。将 (M,j,mij)和(N,j,njk)按j值排序放在不同的列表中，将两个列表的第j个元组中的mij和njk抽出来相乘，然后再将积按j相加得到v，最后输出(i,k),v) 。,2019年3月19日,集群计算的算法效率问题（自学参考）,集群计算的通信开销模型 集群计算的开销主要来自任务间数据的移动：通信开销，而不是任务的执行时间。因为：算法中每个执行任务都非常简单，时间复杂度最多和输入规模成线性关系；数据传输速度相对于处理器执行指令的速度要慢。 通信开销仅考虑所有输入的开销而不考虑输出的开销。因为：任务T的

13、输出是另一个任务的输入，因此当度量接收任务的输入规模时，T的输出规模已被计算；一般而言，最终输出结果相对于输入规模或中间数据相比，都要更小一些。,2019年3月19日,集群计算的算法效率问题,实耗通信开销 在工作流网络中，所有路径中的最大通信开销。路径通信开销是指该路径上所有任务的通信开销之和。,2019年3月19日,集群计算的算法效率问题,多路连接（n路连接） 选定自然连接中的关系的连接属性A1,A2,An，并将这些属性值哈希到一定数量的桶中（桶编号与哈希值一一对应）； 对每个连接属性Ai(i=1,n)选定桶的数量ti（对应的桶编号记为0(i),ti-1(i)），使得t1t2tn=k，k为R

14、educe任务数； 记桶编号向量为V=v1,vi,vn，其中vi是连接属性ai的某个桶编号，每一个向量V标记一个Reduce任务； 将每个关系的元组传递给相应的Reduce任务。由于元组可能只有部分连接属性有值，因此哈希形成的向量V中存在某些分量未知，因此要将该元组传递给未知分量所有可能取值所对应的所有Reduce任务。,2019年3月19日,集群计算的算法效率问题,三个关系的连接 设待连接的三个关系分别为R(C, A1)、S(A1, A2)、T(A2, D)，规模分别为r, s, t。且假定R与S、S与T可连接的概率均为p。 连接策略一：采用两次二路连接完成三个关系的连接 先连接RS，再连接

15、T，总通信开销为2r+2s+2prs+2t 先连接ST，再连接R，总通信开销为2t+2s+2pts+2r 连接策略二：采用一次三路连接完成三个关系的连接 设计划的Reduce任务数为k，记b, c为将连接属性A1和A2哈希到的桶数，bc=k，对应的哈希函数分别为h和g。每当h(v)=i且g(w)=j，对应桶(i,j)的Reduce任务就负责连接元组R(u,v),S(v,w)和T(w,x)。,2019年3月19日,集群计算的算法效率问题,三个关系的连接 计算连接策略二的通信开销 Map的输入总开销：r+s+t Reduce的输入总开销：rc+s+bt。由于Map任务在传递R中的某个元组（设R.A

16、1=v）时，只能知道A1的哈希值h(v) ，R中的元组不包含A2，此时桶编号向量为(h(v), NULL)，因此必须要将该元组传递给桶编号向量的第一个分量为h(v)所对应的所有Reduce任务，共计c个。 优化设计：r+s+t是常数，可优化的对象是Reduce的输入总开销，约束条件是bc=k，求解可得b=(kr/t)1/2时开销最小。,2019年3月19日,集群计算的算法效率问题,三个关系的连接 比较连接策略一与连接策略二的通信开销优劣 连接策略一的总开销为2r+2s+2prs+2t 。 连接策略二的总开销为r+s+t+s+2(krt)1/2 假设R,S,T都是同一个关系R，R是Faceboo

17、k上的朋友关系，则RRR可找出每个用户所拥有的朋友的朋友的朋友的数目或具有最多的朋友的朋友的朋友的用户。 连接策略一的总开销为6r+2pr2=6r+2dr（d为每个用户的朋友数） 连接策略二的总开销为4r+2rk1/2 若两种策略没有优劣之分，则有d+1=k1/2 可见，d越大越不宜使用策略一，k越大则越不宜使用策略二。,2019年3月19日,集群计算的算法效率问题,星型连接 R(A,B,C,X),S(A,D),T(B,E),U(C,F) 多路连接的通信开销：T=r+s+t+u+r+sbc+tac+uab, 其中abc=k。 优化结果： a=(ks2/tu)1/3, b=(kt2/su)1/3

18、, c=(ku2/st)1/3 T=2r+s+t+u+3(k2tus)1/3 若s=t=u，则T=2r+3s(1+k2/3) 通常情况下，rs，因此适合使用多路连接策略。,2019年3月19日,一、大数据时代 二、大数据分析基础 三、相似项发现 四、流数据分析,提纲,一、大数据时代 二、大数据分析基础 三、相似项发现 四、流数据分析,2019年3月19日,相似项发现的应用,相似项发现（邻近搜索）是许多数据分析任务的基础。在管理实践中也有着广泛的应用。例如，文档相似性（抄袭、镜像、同源新闻稿）、图片相似性（识别未知图片的身份）等等。 下面我们以文档间的相似性发现加以阐述。,2019年3月19日,

19、距离测度,欧式距离 Jaccard距离 集合S和T的Jaccard相似度定义为|ST|/|ST|。 余弦距离：两个向量夹角的余弦。 编辑距离：仅适用于字符串比较，两个字符串x,y的距离等于将x转换为y所需要的单字符插入及删除操作的最小数目。x=abcde, y=acfdeg, dxy=3 海明距离：给定一个向量空间，海明距离定义为两个向量中不同分量的个数。x=10101, y=11011, dxy=3,2019年3月19日,文档的Shingling,k-Shingle 文档的k-shingle定义为其中任意长度为k的子串。 D=abcdabd, k=2，D2-shingle=ab,bc,cd,

20、da,bd k的选择 k值的大小依赖于文档的典型长度以及典型的字符表大小。k的大小应保证随机产生的k-Shingle在文档中出现的概率较低。,2019年3月19日,文档的Shingling,k的选择 例如，如果文档集由电子邮件组成，那么k取多少比较合适呢？k=5是一个比较好的选择，因为写邮件通常用到27个字符（26个字母+空格），275=14348907，邮件的长度远远低于该长度。 思考 各字母出现的概率相差很大对k选择有什么影响？中文怎么选？能否将Jaccard相似度与TF.IDF相结合用于比较两个文档的相似性（可考虑到语义）？,2019年3月19日,文档的Shingling,基于词的Shi

21、ngle 为了近似检测两篇文档，可将Shingle定义为一个停用词加上后续的两个词。其好处是当某文档如网页存在许多周边元素（不常使用停用词）时，能有效剔除这些干扰信息。例如，“Buy Sudzo”可能就是周边元素，而“A spokesperson for the Sudzo Corporation revealed today that studies have shown it is good for people to buy Sudzo Products”就是一篇正常文档。 对Shingle进行哈希 通过某个哈希函数将Shingle后的字符串映射为桶编号。,2019年3月19日,保持相似

22、度的集合摘要,文档的Shingle集合一般非常大，即使经过哈希映射，一篇文档所需要的空间仍然是该文档所需空间的4倍。我们的目标是将上述大集合替换成规模小很多、但却能保持文档相似性的签名集合。 集合的矩阵表示 设全集为a,b,c,d,e，集合S1=a,d,S2=c,S3=b,d,e, S4=a,c,d，则S1-S4的特征矩阵表示为：,2019年3月19日,保持相似度的集合摘要,最小哈希 传统的hash算法只负责将原始内容尽量均匀随机地映射为一个签名值。如果hash算法产生的两个签名相等，说明原始内容在一定概率下是相等的；否则除了说明原始内容不相等外，不再提供任何信息，因为即使原始内容只相差一个字

23、节，所产生的签名也很可能差别极大。 因此要设计一个hash算法，对相似的内容产生的签名也相近。 MinHash由Andrei Broder提出，最初用于在搜索引擎中检测重复网页。它也可以应用于大规模聚类问题。,2019年3月19日,保持相似度的集合摘要,最小哈希 最小哈希过程：将哈希函数作用于某个集合的所有元素，返回最小哈希值对应的那个元素。 对集合每进行一次最小哈希过程，即可得到该集合的一个签名。 针对特征矩阵表示的集合的最小哈希过程(最小哈希函数就是置换函数)：选择矩阵的一个行排列置换（设函数f:AA, A是一个集合。如果f是一一映射，就称f是A的一个排列置换，也称置换运算，即将行号重新排

24、列），任意一列（对应一个集合）的最小哈希值是：在新的行排列次序下，第一个列值为1的行的行号或行元素。,2019年3月19日,保持相似度的集合摘要,最小哈希 例如：对原矩阵行abcde进行置换运算形成新的行顺序：dcbea，该排列置换定义了一个最小哈希函数h。h(S1)=d， h(S2)=c， h(S3)=d， h(S4)=d。,2019年3月19日,保持相似度的集合摘要,最小哈希与Jaccard相似度的关系 两个集合经随机置换运算后得到的两个最小哈希值相等的概率=这两个集合的Jaccard相似度 证明：设两个集合S1和S2，对应的矩阵列经随机置换后的每行结果分为三种情况：X类行，X.S1=X.

25、S2=1; Y类行，Y.S1 Y.S2；Z类行，Z.S1=Z.S2=0。X类和Y类的行数目x,y决定了SIM(S1,S2)和p(h(S1)=h(S2)。容易理解：SIM(S1,S2)=x/(x+y) 另一方面，当从矩阵的第一行开始扫描矩阵时，在Y类行之前遇到X类行的概率为x/(x+y)。若先遇到X类行，则h(S1)=h(S2)，若先遇到Y类行，则h(S1)h(S2)。因此， p(h(S1)=h(S2)=x/(x+y)。#,2019年3月19日,保持相似度的集合摘要,最小哈希签名及其计算 最小哈希签名：随机选择集合的特征矩阵M的n个“行置换”运算，集合S的最小哈希签名向量为h1(S),h2(S)

26、,.,hn(S)，其中hi为对应第i个置换的最小哈希函数。基于矩阵M可构建一个最小哈希签名矩阵。 最小哈希签名的计算：对大规模特征矩阵进行“行置换”运算是极其耗时的。有效的方法是通过一个随机哈希函数对行号进行哈希操作，将其映射到与行数目k相等的桶中。在哈希过程中，可能出现不愿看到的现象，即不同的行号被映射到同一个桶中，而某些桶没有被映射到。但只要k足够大且哈希结果的冲突不太频繁，问题就不大。,2019年3月19日,保持相似度的集合摘要,最小哈希签名及其计算 最小哈希签名的计算：因此，可不对行进行置换，而随机选择n个哈希函数h1,.,hn作用于行。具体计算过程： 令SIG(i,c)表示签名矩阵中

27、第i个哈希函数在第c列上的元素，对于所有的i和c，初始化SIG(i,c)=。 对行r，计算h1(r),.,hn(r) 对每列c：(1)若c在第r行为0，则跳过；(2)若c在第r行为1，那么对于每个i=1,.,n，将SIG(i,c)置换为原来SIG(i,c)和hi(r)之中的较小者。,2019年3月19日,保持相似度的集合摘要,最小哈希签名及其计算 例：随机选择两个哈希函数h1，h2作用于矩阵的行得到下图。通常哈希结果会有冲突。（集合相似性的近似度量）,2019年3月19日,文档的局部敏感哈希算法,在比较文档相似性时，文档对的数目可能很多（O(n2)，n为文档数），因此应用最小哈希方法寻找具有最

28、大相似度的文档对仍然是不可能的。 在实际应用中，我们并不关心所有文档对之间的相似性，而是关心那些可能相似的文档对。 处理思路：将文档转换成Shingle集合，再经过哈希处理形成签名集合（矩阵），最后应用局部敏感哈希（Locality-sensitive hashing，LSH）或近邻搜索（Near-neighbor search）得到最相似文档对。,2019年3月19日,文档的局部敏感哈希算法,面向最小哈希的LSH 解决思路：对目标项进行多次哈希处理，使得相似项会比不相似项更可能哈希到同一个桶中。然后，将至少有一次哈希到同一个桶的文档对看成候选对。对候选对做相似性分析。 哈希函数的设计是问题的

29、关键。伪正例（不相似的文档对哈希到同一个桶）、伪反例（相似的文档没有哈希到同一个桶）。,2019年3月19日,文档的局部敏感哈希算法,面向最小哈希的LSH 多次哈希策略：将最小签名矩阵分割成b个行条，每个行条由r行组成。选择一个哈希函数LSH，对每个行条的每个列向量（每个文档对应的最小签名集合的一部分）进行哈希处理，每个行条使用独立的桶数组。,2019年3月19日,文档的局部敏感哈希算法,行条化策略分析 设行条数为b，每个行条包含r行。假定某对文档的相似度为s（签名矩阵中某行有关该文档对的两个签名相等的概率为s），则该文档对之间的签名存在如下概率关系： 在某个具体行条中所有行的两个签名相等的概

30、率为sr； 在某个具体行条中至少有一对签名不相等的概率为1-sr； 在每个行条中都至少有一对签名不相等的概率为(1-sr)b； 至少有一个行条，其中所有行的两个签名都相等的概率为1-(1-sr)b。（文档对是相似候选对的概率，此时两个文档落入同一个桶中）,2019年3月19日,文档的局部敏感哈希算法,行条化策略分析 阈值：曲线上升最陡的点，对应p关于s的二阶导数=0。此时，s(1/b)1/r。对于给定的签名数，b越大，阈值越小，伪正例越多且计算量越大；反之，伪反例越多。图中签名数为64。,2019年3月19日,文档的局部敏感哈希算法,相似项发现方法小结 选择某个k值，对文档集中的所有文档构建其

31、k-Shingle集合，将这些k-Shingle映射成更短的桶编号；输出文档集的特征矩阵，矩阵的行按桶编号排序（不必要）。 随机选择n个哈希函数对矩阵的行分别进行哈希映射，按照最小哈希签名的计算方法求出最小哈希签名。 选择行条数b和每个行条中的行数r，使得br=n。阈值t (1/b)1/r。调节b，可控制伪正例或伪反例数量以及计算速度。 利用局部敏感哈希（LSH）构建候选对； 检查每个候选对的签名，检查其一致性是否大于t； 检查候选对的两个本身是否真正相似。,2019年3月19日,局部敏感函数理论（自学参考）,局部敏感函数 判定两个输入项x, y是否是候选对。 设判定函数为f(x,y)，若f判

32、定x,y是候选对，则记为f(x)=f(y)；否则记为f(x)f(y)。这种形式的一系列函数集合构成一个函数族，并要求满足以下三个条件： 选择近距离而不是远距离作为候选对； 函数之间必须在统计上相互独立，即两个函数的联合概率等于每个函数独立事件的概率之积； 能够在比扫描所有文档对小很多的时间内识别候选对；可以组合在一起以更好地避免伪正例或伪反例。,2019年3月19日,局部敏感函数理论,局部敏感函数 令d1d2是定义在某个距离测度下的两个距离值。如果一个函数族F中的每一个函数f都满足： (1)如果d(x, y)d1，那么f(x)=f(y)的概率至少是p1； (2)如果d(x, y)d2，那么f(

33、x)=f(y)的概率最大是p2； 则称F是(d1, d2, p1, p2)-敏感的函数族。 最小哈希函数（置换函数）族是(d1, d2, 1-d1, 1-d2)-敏感的函数族。 因为当d(x, y)d1时，p(h(x)=(y)=SIM(x,y)=1- d(x, y)1-d1；而当d(x, y)d2时，p(h(x)=(y)=SIM(x,y) =1-d(x, y)1-d2。,2019年3月19日,局部敏感函数理论,2019年3月19日,局部敏感函数理论,局部敏感函数族的构造 设函数族F是(d1, d2, p1, p2)-敏感的函数族。 “与”构造函数族F：F的每个成员函数f由r个F成员函数f1,f

34、2,.,fr组成，r为固定常数（行条的行数）。f(x)=f(y) iff f1(x)=f1(y) and .and fr(x)=fr(y)。即一个行条中所有r行的x,y值都相等，则基于整个行条就可以认为x,y是候选对。F是(d1, d2, p1r, p2r)-敏感的函数族。 “与”构造过程降低了所有的概率，但可通过谨慎选择F和r，可使得p2r非常接近于0，而大概率p1r显著偏离0。,2019年3月19日,局部敏感函数理论,局部敏感函数族的构造 “或”构造函数F： F的每个成员函数有b个(行条数）F成员函数f1,f2,.,fb组成。f(x)=f(y) iff f1(x)=f1(y) or . o

35、r fb(x)=fb(y)。即如果某个行条能够使x,y成为候选对，则x,y就是候选对。F是(d1, d2, 1-(1-p1)b, 1-(1-p2)b)-敏感的函数族。 “或”构造过程提升了所有的概率，但可通过谨慎选择F和b，可使得1-(1-p1)b非常接近于1，而1-(1-p2)b有界远离1。 通过串联“与”和“或”构造函数F1，F1是(d1, d2, 1-(1-p1r)b, 1-(1-p2r)b)-敏感的函数族。1-(1-p2r)b接近于0，同时1-(1-p1r)b接近于1。 通过串联“或”和“与”构造函数F2 ,F2是(d1, d2, (1-(1-p1)b)r, (1-(1-p2)b)r)

36、-敏感的函数族。 (1-(1-p1)b)r接近于1的同时(1-(1-p2)b)r也得以上升，从而增加了伪正例数目，这种做法不一定是最优的。,2019年3月19日,局部敏感函数理论,与或串联,或与串联,2019年3月19日,不同距离测度的LSH函数族,海明距离的LSH函数族 设向量空间的维数为n，h(x,y)表示向量x,y的海明距离，随机选择向量的任一维i，定义fi(x)为向量x的第i维分量，当且仅当x和y的第i维分量相等时有fi(x)=fi(y)。对随机选择的i，p(fi(x)=fi(y)=1-h(x,y)/n。因此，对于任意d1d2，由f1,f2,.,fn构成的函数族是(d1,d2,1-d1

37、/n,1-d2/n)-敏感的哈希函数族。该函数族与最小哈希函数族的区别有两点：Jaccard距离的取值范围是0-1，而海明距离的取值范围是0-n，因此，需要除以n才能转化成概率；最小哈希函数族的函数个数理论上可以有无限个（我们一般取数十数百个），而海明距离的函数族为n个。,2019年3月19日,不同距离测度的LSH函数族,余弦距离的LSH函数族 如图，x, y是n维空间的两个向量，其余弦距离为。x, y定义了一个平面，记为A；任意选择一个通过坐标原点的超平面B或C(实际是随机选择一个超平面的法向量v)，它与A相交于一条直线(蓝线和红线)，存在两种相交模式：一种使x, y在直线的同侧(蓝线)，另

38、一种则在异侧(红线)。,2019年3月19日,不同距离测度的LSH函数族,余弦距离的LSH函数族 设v是该超平面的法线，则v与x, y的内积存在下列关系：同侧分割时（B），内积的正负性相同，异侧分割时（A），内积的正负性相反。 那么，内积的正负性相反的概率为/180；内积的正负性相同的概率为1-/180。（相似性越大， 越小，内积的正负性相同的概率越大）,2019年3月19日,不同距离测度的LSH函数族,余弦距离的LSH函数族 LSH函数族的每一个哈希函数f都是来自一个随机选择的法向量vf，向量x,y当且仅当内积vf.x与vf.y的正负性相同时，有f(x)=f(y)。对随机选择的vf，p(f(

39、x)=f(y)=1-/180。因此，对于任意d1d2，由f1, f2,.构成的函数族F是(d1,d2,1-d1/180, 1-d2/180)-敏感的哈希函数族。 不需要在所有的向量空间选择v，可以限定在分量为+1和-1的向量集合中随机选择，可选空间为2n。（形成x的“梗概(Sketch)”）,2019年3月19日,不同距离测度的LSH函数族,欧氏距离的LSH函数族 LSH函数族的每一个哈希函数f都是来自一个随机选择的直线l，并将直线按长度a分段，向量x, y当且仅当在l上的投影落入同一个分段区间内，有f(x)=f(y)。对随机选择的l，p(f(x)=f(y)=1-c/a。c为向量x, y在l上

40、的投影距离，要求ca。因此，对于任意d1d2，由f1,f2,.构成的函数族F是(d1,d2,1-c1/a, 1-c2/a)-敏感的哈希函数族。,l,2019年3月19日,一、大数据时代 二、大数据分析基础 三、相似项发现 四、流数据分析,提纲,一、大数据时代 二、大数据分析基础 三、相似项发现 四、流数据分析,2019年3月19日,流数据模型,流数据源 传感器：生产数据、GPS跟踪等 图像数据：视频监控系统 互联网及Web：数据包、网站访问,2019年3月19日,流数据模型,数据流管理系统,2019年3月19日,流数据模型,流处理器 可看做一种数据管理系统，对输入的数据流进行存储、查询、编辑（

41、增、删、更新）、抽样等操作。 流数据存储 工作存储器：用于流汇总数据或部分流数据以备应答查询。可以是磁盘，可以是内存，取决于查询速度的要求。 归档存储器：将流数据按照一定的规范组织存储，以备检索查询。大容量、处理速度慢、离线。,2019年3月19日,流数据模型,数据流查询 固定查询：一种永远不变的查询，并在适当的时候输出结果。例如，监控温度超过某一个值时报警；输出最近24次读数的平均值、最高温度等。 特别/临时/即席查询(ad hoc query)：对当前某个或多个流数据仅提交一次的、任务不确定的查询。为了应对特别查询，需要将一段时间或一定量的流数据（滑动窗口, sliding window）

42、保存在工作存储器中，以备查询。 数据流处理的特殊性：实时（内存存储）,2019年3月19日,流数据抽样,从流中选择一个子集，以便能够对它进行查询并给出统计性上对整个流具有代表性的结果。 错误抽样的结果：在搜索引擎搜索流中统计“用户所提交的重复搜索的比例”，样本选择1/10。如何抽样？抽样策略是对每个搜索产生一个09的随机数，并当且仅当随机数为0时成为样本。假设某用户提交了1次的搜索有s个，提交了2次的搜索有d个，不存在超过2次的搜索。则总共产生(s+2d)/10个样本，其中s个单次搜索的样本数是s/10，2次搜索中同时进入样本的概率是1/100，因此共有2d/100个样本，2次搜索仅有1次进入

43、样本的有2d/10-2d/100=18d/100。 实际重复搜索比例是d/(s+d)，而按抽样结果计算出的重复搜索比例是：(d/100)/(s/10+18d/100+d/100)=d/(10s+19d),2019年3月19日,流数据抽样,正确抽样：针对上述问题，可采用随机整群抽样策略，即将一个用户的搜索看成一个群，抽取1/10用户的搜索行为即可。抽样策略是将每个搜索的用户名哈希到09的桶中，并当且仅当用户名哈希到第0个桶时，该搜索成为样本。 一般抽样问题：若流数据是由一系列n个字段(如name, query, time)的元组构成，样本的选择基于关键字段(如name)。假定抽样后的样本规模为a

44、/b (如1/10)，则可以将每个元组的关键字段值哈希到某个桶中（桶的总数是b），将哈希值小于a的元组放入样本。选出的关键字段值数目占总体的比例约为a/b。,2019年3月19日,流数据抽样,一般抽样问题：若存储空间预先有设置，则随着样本的增加而超过预先设置时，可采用去除某些关键字段值的样本元组来释放存储空间（例如，开始记录100人的搜索记录，随着样本数的增加，逐渐减为99人、98人、，并去除原来存储的被减去的人的元组）。具体办法如下，选择一个哈希函数h，可将关键字段值K映射到一个很大的取值范围（例如，一开始可以容纳很多人的搜索），桶的总数B很大，并维护一个阈值t，其初始值设为B-1。任何时候

45、，样本都有K满足h(K)t的元组构成。如果存储空间不足，则可将阈值降低为t-1，并将那些满足h(K)=t的元组删除。,2019年3月19日,流过滤,垃圾邮件过滤 设有m个非垃圾邮件地址构成的集合S 邮件数据流通过垃圾邮件过滤器时进行过滤操作，过滤的办法是检查该邮件地址是否在S集合中 由于m数量一般很大，且每个邮件地址都有20左右的字节，直接将S存放在内存中是不合适的；此外，只要检查该邮件地址是否在S中，并不需要关心到底是哪个邮件地址。因此布隆过滤器是一种有效的垃圾邮件过滤技术。,2019年3月19日,流过滤,布隆过滤器 将内存当做位数组使用，N字节内存对应8N个位，记为n。(设1个字节占8位)

46、，每个位的初始值为0。 m个邮件地址（键值）组成集合S。 k个哈希函数组成哈希函数族h1,h2,.,hk。每个哈希函数可以将一个邮件地址映射到某个位上。 布隆过滤器的目的是让邮件地址在S中的流数据通过，不在S中的流数据大部分被阻挡。,2019年3月19日,流过滤,布隆过滤器工作流程 首先用k个哈希函数组成的哈希函数族h1,h2,.,hk对S中的每个键值做k次映射，只要某个位被映射到1次，位值则改记为1。 当键值为K的流元素到达时，检查所有的h1(K),.,hk(K)是否全为1，如果是，则允许通过，否则阻挡。,2019年3月19日,流过滤,布隆过滤器性能分析 给定键值不能哈希到给定位的概率：(n

47、-1)/n 每个键值哈希k次，所有键值都哈希不到给定位的概率： (n-1)/n)km=(1-1/n)n)km/n=e-km/n 伪正例的概率=某个键值经过k次映射均为1的概率=一个位为1的概率的k次方=(1-e-km/n)k 设m=1G, N=1G, n=8G，m/n=1/8 k=1，给定位未被哈希到的概率=e-1/8，而至少被哈希到1次的概率为1-e-1/8=0.1175，略小于1/8。0.1175也是伪正例概率。 k=2，伪正例概率=(1-e-1/4)20.0493。,2019年3月19日,独立元素数的估计,任务：估计流中所出现的不同元素的数目。 FM算法(Flajolet-Martin)

48、：将流中的每个元素（总数为m）哈希到一个足够长的位串（位串长度大到能容纳哈希函数的可能结果数目），使用多个不同的哈希函数。这样，流中看到的不同元素越多，则看到不同的哈希值也越多，尾数连续为0的哈希值也越多（尾数连续0的数目称为尾长）。设截止目前看到的最大尾长为R，则独立元素估计为2R。,2019年3月19日,独立元素数的估计,性能分析 给定元素的哈希值尾长为r的概率为2-r，流中的任何元素的哈希值都没有尾长达到r的概率为(1-2-r)m=exp(-m2-r) 如果m远大于2r，则发现一个尾部长度至少为r的概率接近1；如果m远小于2r，则发现一个尾部长度至少为r的概率接近0。因此，m的估计值取2

49、R是合理的。 内存性能：仅保存每个哈希函数产生的最大尾长。 问题分析及对策 当R出现异常时（哪怕仅异常1位），估计误差就达1倍。 将哈希函数分成若干组，每组的哈希函数的数目约为klog2m, k是一个小整数。 按组计算估计值的平均值，再取各组平均值的中位数。,2019年3月19日,矩估计,矩定义 给定的数据流由选自某个全集上的元素构成，假定该全集的所有元素都排好序，则可用整数i标记第i个元素，若元素i出现在流中的次数为mi（0），则流的k阶矩(kth-order moment)是所有i上的(mi)k之和。 0阶矩：出现在数据流中的独立元素的个数。 1阶矩：当前数据流中的元素个数=整个流的长度。 2阶矩（奇异数）：当前数据流中，每个独立元素i出现次数mi的平方和，它可度量流中元素分布的非均匀性，奇异数越大，均匀性越差。,20