《相似项发现》PPT课件.ppt

第三章 相似项发现,3.1 近邻搜索的应用,相似度：通过计算交集的相对大小来获得集合之间的相似度，也称为Jaccard相似度Sim(C1,C2)=|C1C2|/|C1C2|.,3,Example:Jaccard Similarity,3 in intersection.8 in union.Jaccard similarity=3/8,3.1.2 文档的相似度,Jaccard相似度在如下问题取得较好效果：在大的语料库(web,新闻）中寻找文本内容相似的文档。这里主要指字面上的相似，而非语义上的相似如果只需要检查两个文档是否严格相同，只需要逐字比较就可以。很多应用里，两篇文档不是完全重复，只是大部分相同。,3.1.2 文档的相似度,应用场景抄袭文档。抄袭者可能会从其它文档中将某些部分的文档据为己有，同时可能对某些词语或者原始文本中的次序进行改变。镜像页面。重要的web站点会在多个主机建立镜像页面。这些镜像的主要内容相似，但是也包括不同的内容（每个站点都指向其他站点而不指向自己）。搜索引擎需要过滤掉内容相同的镜像站点同源新闻稿。一个记者可能把一个新闻稿件投到多家报刊。每家报刊进行修改后刊发。Google new能够发现此类稿件，只显示一个版本。,3.1.3 协同过滤,在协同过滤中，系统会向用户推荐相似用户所喜欢的那些项。在线购物。两个用户兴趣相似，如果他们购买的商品集合有较高的Jaccard相似度。20%就很高了。两个商品相似，如果顾客集合有较高的Jaccard相似度可能需要一些辅助工作来发现相似。如两个顾客各自购买了大量科幻小说，但是这些科幻小说都不相同，通过相似度发现和聚类，把这些科幻小说归为一类，从而提高这两个顾客的相似度。,3.1.3 协同过滤,电影评级。NETFLix不仅记录了每个用户租借电影的情况，还记录了顾客对这些电影的打分/评级情况如果电影被许多相同的用户租借或者打分，则认为这些电影相似如果用户租借很多相同的电影或者对它们打分很高，则认为这些用户相似。,3.2 文档的shingling,为了识别字面上相似的文档，需要将文档表示为文档中的短字符串集合。简单的构建方法将导致大量相同的公共集合元素，即使两篇文档彻底不同Shingling是构建表示文中的短字符串集合的方法,3.2.1 k-shingle,把一篇文档看成是一个字符串。文档的k-shingle就是文档中出现过的长度为k的字符串。一篇文档表示为k-shingle的集合例3.3 假设文档为字符串abcdabd,k=2，则所有2-shingle组成的集合为ab,bc,cd,da,bd，注意ab在字符串里出现了两次，但是在集合里面只有一次,3.2.2 shingle大小的选择,如果k取得太小，大部分长度为k的字符串会出现在大部分文档中，导致相似度较高。好处是？对于邮件来说，k=5，每个字串的位置可能是27个字母之一，可能有275个字串对于论文来说，k取9较为合适,3.2.3 对shingle进行哈希,直接将长度为k的字符串用哈希函数映射成桶的编号，用这些桶的编号的集合来表示文件。由文档产生9 shingle 集合，在把每个9 shingle 映射成4个字节长的桶编号如果采用4 shingle，与上面方法占用的空间相似。但是性能不一样。如果只有20个字符出现频繁，则4-shingle的数量是204。大部分项集是空的如果是9 shingle,数量大为增加，映射到4个字节的桶，则每个桶出现的概率大大增加,3.2.4 基于词的shingle,在一个网页中，即有新闻报导，也有周边元素。在新闻报导和大量散文中，包括大量停用词，and,you,to等，频率高于周边元素。在多数应用中，都忽略掉这些词。如果是想比较新闻文本的相似性，则可以利用这个特点。Shingle定义为停用词后面的两个词（不管是否是停用词）,例子,A spokeperson for the sudzo Corporation revealed today that studies have shown it is good for people to buy sudzo products.A spokepersonfor the sudzothe sudzo CorporationBuy sudzo,3.3 保持相似度的集合摘要,Shingle 集合非常大。一个4 shingle 集合也是原始文件的4倍想办法计算文件的签名（一个较小的文件），通过计算签名的相似性来推断文件之间的相似性。,3.3.1 集合的矩阵表示,矩阵的列表示各个集合，行表示所有可能的元素S1=a,d,s2=c,s3=b,d,e,s4=a,c,d,3.3.2 最小哈希,首先选择行的一个排列变换。任意一列的最小哈希值是在该行排列顺序下第一个列值为1的行的行号。H(S1)=a,H(s2)=c,H(s3)=b,H(s4)=a,3.3.3 最小哈希及jaccard相似度,两个集合经随机排列转换之后得到的两个最小哈希值相等的概率等于这两个集合的jaccard相似度假设只考虑s1和s2两个集合对应的列。,四种类型,Given columns C1 and C2,rows may be classified as:C1C2a11b10c01d00两列同时为0的行对于这两列的相似性没有贡献。.设x是两列都为1的行的数目 y是其中一行为1的数目Note Sim(C1,C2)=x/(x+y).,3.3.3 最小哈希,对行进行随机转换后，从上往下扫描。遇到两行均为1的概率是x/(x+y)总共有x+y行，两行均为1的个数有x个。两行均为1，也就是H(s1)=H(s1),3.3.4 最小哈希签名,对于每一个行排列方式，每一个集合都有一个最小哈希值如果有n个行排列方式（n一般是1百到数百），每个集合就能产生n个最小哈希值，把这些哈希值写成一个列向量。也称为哈希签名。每个集合的列向量组合在一起，写成一个矩阵，称为签名矩阵。文档的相似性就等于最小哈希值相等的概率,3.3.5 最小哈希签名的计算,操作矩阵较为困难，操作较小的签名矩阵是可以的用签名矩阵记录行变换的结果，每一个位置只记录当前变换的最小的位置,3.4 文档的局部敏感哈希算法,即使可以使用最小哈希将大文档压缩成小的签名并同时保存任意文档对之间的相似度，寻找相似文档对仍然是不可能的文档的数目太大实际上，只需要寻找那些相似性大于某个门限的文档对，而不是全部文档对。这就是局部敏感哈希,3.4 文档的局部敏感哈希算法,假设文档先表示为shingle集合，通过哈希处理，变为短签名集合基本想法：把签名矩阵分成子矩阵，使用多次哈希函数。具有相同部分的列将被哈希到同一个桶中只考察那些哈希到同一个桶里面的列的相似性,26,Partition Into Bands,Matrix M,r rowsper band,b bands,Onesignature,27,Matrix M,r rows,b bands,Buckets,28,What b Bands of r Rows Gives You,Similarity s of two sets,Probabilityof sharinga bucket,t,29,Example:b=20;r=5,30,LSH小结,找出具有相似签名的集合对，删除大部分不相似的集合对在内存里面检查这些候选的集合对,3.4.3 上述技术的综合,选择k，构建文档的shingle集合将文档-shingle对按照shingle 排序构建最小哈希签名用局部敏感最小哈希算法选择可能的相似对。,3.5 距离侧度,两个集合越相似，距离越近（越小）Jaccard测度，两个集合越相似，Jaccard测度越大Jaccard距离，则：1-Jaccard测度本节介绍其他的距离定义,3.5.1 距离侧度的定义,距离的定义有一些点组成的集合，也称为空间在该空间定义一个函数d(x,y)，x,y是空间的点，该函数输出一个实数D(x,y）=0D(x,y）=0 if and only if x=yD(x,y)=D(y,x)D(x,y)=D(x,z)+D(z,y)(三角不等式）,3.5.2 欧式距离,3.5.3 Jaccard距离,D(x,y)=s-sim(x,y),3.5.4 余弦距离,在有限维的欧式空间，每个点表示一个向量。两个向量的夹角定义为：两个向量的内积与两个点之间的欧式距离的比值。再用这个比值去反余弦，获得夹角度数。,3.5.5 编辑距离,两个字符串的距离定义为把一个字符串变为另外一个字符串需要插入的单字符和删除的字符的最小数目例如：x=abcde,y=acfdeg。把x变为y至少需要三步删除bC后插入fE后插入g,3.5.5 编辑距离,X和y的最长公共子序列（LCS）：通过在x和y的某些位置进行删除，得到x,y的最长公共字符串。编辑距离等于x的长度,y的长度的和减去两倍的LCS如x=abcde,y=acfdeg。Lcs=acde编辑距离=5+6-2*4=3,3.5.6 汉明距离,汉明距离定义为两个向量中不同分量的个数。例如：10101和11110的距离是3,40,3.6 局部敏感函数理论:哈希函数簇,一个“哈希”输入两个集合元素，输出结果是：这两个元素是否相同(做相似性检测）Shorthand:h(x)=h(y)means“h says x and y are equal.”上述函数的集合称为哈希函数簇,41,局部敏感哈希函数,在集合S上面定义了距离空间d.函数簇 H 称为(d1,d2,p1,p2)-sensitive，如果对于S中的x和y:如果d(x,y)d2,对于H中的所有h，对于H中的所有h，h(x)=h(y)的概率最多是 p2.,42,LS Families:Illustration,d1,d2,Highprobability;at least p1,Lowprobability;at most p2,?,43,Example:LS Family,设 S=sets,d=Jaccard distance,H是所有行变换条件下的最小哈希函数构成的集合.Then Probh(x)=h(y)=1-d(x,y).回忆最小哈希函数和 Jaccard相似性的关系的定理.,44,Example:LS Family(2),记号:H is a(1/3,2/3,2/3,1/3)-sensitive family for S and d.,45,Comments,For Jaccard similarity,最小哈希函数给出了(d1,d2,(1-d1),(1-d2)-的函数簇.定理没有说明d1 and d2之间的取值.,46,局部敏感函数簇的放大,在签名矩阵使用的“bands”技术可以做通用化扩展.Goal:the“S-curve”效果.AND construction like“rows in a band.”OR construction like“many bands.”,47,AND of Hash Functions,给定一个函数簇 H,构建函数簇 H，H中德每个函数由H中的 r 个函数构成。For h=h1,hr in H,h(x)=h(y)if and only if hi(x)=hi(y)for all i.Theorem:If H is(d1,d2,p1,p2)-sensitive,then H is(d1,d2,(p1)r,(p2)r)-sensitive.Proof:Use fact that hi s are independent.,48,OR of Hash Functions,Given family H,construct family H consisting of b functions from H.For h=h1,hb in H,h(x)=h(y)if and only if hi(x)=hi(y)for some i.Theorem:If H is(d1,d2,p1,p2)-sensitive,then H is(d1,d2,1-(1-p1)b,1-(1-p2)b)-sensitive.,49,Effect of AND and OR Constructions,AND 使得所有的概率减少,如果恰当的选择 r,可以使低的概率趋于0而高的概率不变。OR 使所有的概率增加，如果恰当的选择 b,可以使高的概率趋于1而低的概率不变。,50,组合使用两种构建方法,对于签名矩阵，可以在 AND 构建后使用 OR 构建.Or vice-versa.Or any sequence of ANDs and ORs alternating.,51,AND-OR Composition,概率 p 变为 1-(1-pr)b.The“S-curve”studied before.Example:Take H and construct H by the AND construction with r=4.Then,from H,construct H by the OR construction with b=4.,52,Table for Function 1-(1-p4)4,Example:Transforms a(.2,.8,.8,.2)-sensitivefamily into a(.2,.8,.8785,.0064)-sensitive family.,53,OR-AND Composition,Each of the two probabilities p is transformed into(1-(1-p)b)r.The same S-curve,mirrored horizontally and vertically.Example:Take H and construct H by the OR construction with b=4.Then,from H,construct H by the AND construction with r=4.,54,Table for Function(1-(1-p)4)4,Example:Transforms a(.2,.8,.8,.2)-sensitivefamily into a(.2,.8,.9936,.1215)-sensitive family.,55,3.8 LSH函数的应用,3.8.2 实体关联两个记录集合A和B，每个集合有106个记录每个记录有名字、号码、和住址三个项名字之间的距离用编辑距离每一项完全匹配得分100，三项总分300分需要找出相似的记录方法一把具有相同号码的记录哈希到一个桶里把具有相同地址的记录哈希到一个桶里把具有相同名字的记录哈希到一个桶里方法二对所有记录按名字排序，只对具有相同名字的记录计算总分对所有记录按地址排序，只对具有相同地址的记录计算总分对所有记录按号码排序，只对具有相同号码的记录计算总分,3.8.2 实体关联,方法二对所有记录按名字排序，只对具有相同名字的记录计算总分对所有记录按地址排序，只对具有相同地址的记录计算总分对所有记录按号码排序，只对具有相同号码的记录计算总分,57,3.8 LSH函数的应用,3.8.4 指纹匹配把指纹表示为网格指纹匹配就转换为两个集合的对比，就可以采用前面的Jaccard距离定义3.8.5 使用与指纹匹配的LSH函数簇预先使用多个函数，并计算已有指纹的哈希值，把已有指纹映射到桶中计算需要比较的指纹的哈希值，把它映射到桶中，并与桶中的其他指纹比较,58,3.9 面向高相似度的方法,3.9.1 相等项发现：比较完全相等对象对文档头哈希，只对进入同一个桶的文件比较对整篇文档哈希对文档中的随机点哈希,59,3.9 面向高相似度的方法,3.9.2 集合的字符串表示方法把集合中的元素按照某个固定的顺序排序，这这个列表看成是一个字符串。每个字符只出现一次如果两个字符出现在两个字符串中，它们的先后顺序一致d,a,b按照字母顺序表示为a,b,c,3.9.3 基于长度的过滤,将所有的字符串按照长度排序，然后将字符串s与后面不远的另外一个字符串t比较假设两个字串的Jaccard上界不超过J。记排序后的字串s和t的长度分别为Ls和Lt。这两个字串的交集不超过Ls,并集不超过Lt则JLs/Lt,例如，设字符串长度为9，需要找出所有相似度不小于0.9的字符串。9/0.9=10，只需要考察长度为9和10的字符串。,3.9.4 前缀索引,对每个字符串s，选择由前p个符号构成的前缀。P的大小取决于Ls(字串s的长度）和jaccard距离的下界J。把该前缀的每一个符号的索引中加入字符串S每个符号的索引包括多个需要互相比较的字符串的桶对每一个字串t，选择p，保证如下条件：任意满足sim(s,t)J的字符串t，该字串的前缀中至少包括一个符号，这个符号也出现在s的前缀中,3.9.4 前缀索引,假定虽然sim(s,t)=J，但是t不包括s中前P个字符中的任意字符。只有t成为s的后缀，s和t的相似性才最大。此时，相似性为(Ls-P)/Ls(Ls-P)/LsJ,得P的至少是:floor(1-J)Ls)+1,3.9.5 位置信息的使用,例子：s=acdefghijk,t=bcdefghijk.J=0.9根据上节，s建立a和c前缀索引，t建立b和c索引。在索引c中，s和t相遇。Sim(s,t)=9/110.9如何利用c的位置来减少s,t的比较用（符号，位置）建立索引根据J，计算出位置j，对小于j的索引都进行检索,使用位置和长度信息的索引,用（字符，字符位置，后缀长度）作为索引可进一步较少桶内比较次数,3.8 LSH函数的应用,