《第三章相似项发现教学内容》由会员分享，可在线阅读，更多相关《第三章相似项发现教学内容（67页珍藏版）》请在金锄头文库上搜索。
1、第三章相似项发现,3.1近邻搜索的应用,相似度：通过计算交集的相对大小来获得集合之间的相似度，也称为Jaccard相似度Sim(C1,C2)=|C1C2|/|C1C2|.,3,Example:JaccardSimilarity,3inintersection.8inunion.Jaccardsimilarity=3/8,3.1.2文档的相似度,Jaccard相似度在如下问题取得较好效果：在大的语料库(web,新闻）中寻找文本内容相似的文档。这里主要指字面上的相似，而非语义上的相似如果只需要检查两个文档是否严格相同，只需要逐字比较就可以。很多应用里，两篇文档不是完全重复，只是大部分相同。,3.1
2、.3协同过滤,在协同过滤中，系统会向用户推荐相似用户所喜欢的那些项。在线购物。两个用户兴趣相似，如果他们购买的商品集合有较高的Jaccard相似度。20%就很高了。两个商品相似，如果顾客集合有较高的Jaccard相似度可能需要一些辅助工作来发现相似。如两个顾客各自购买了大量科幻小说，但是这些科幻小说都不相同，通过相似度发现和聚类，把这些科幻小说归为一类，从而提高这两个顾客的相似度。,3.1.3协同过滤,电影评级。NETFLix不仅记录了每个用户租借电影的情况，还记录了顾客对这些电影的打分/评级情况如果电影被许多相同的用户租借或者打分，则认为这些电影相似如果用户租借很多相同的电影或者对它们打分很
3、高，则认为这些用户相似。,3.2文档的shingling,为了识别字面上相似的文档，需要将文档表示为文档中的短字符串集合。简单的构建方法将导致大量相同的公共集合元素，即使两篇文档彻底不同Shingling是构建表示文中的短字符串集合的方法,3.2.1k-shingle,把一篇文档看成是一个字符串。文档的k-shingle就是文档中出现过的长度为k的字符串。一篇文档表示为k-shingle的集合例3.3假设文档为字符串abcdabd,k=2，则所有2-shingle组成的集合为ab,bc,cd,da,bd，注意ab在字符串里出现了两次，但是在集合里面只有一次,3.2.2shingle大小的选择,
4、如果k取得太小，大部分长度为k的字符串会出现在大部分文档中，导致相似度较高。好处是？对于邮件来说，k=5，每个字串的位置可能是27个字母之一，可能有275个字串对于论文来说，k取9较为合适,3.2.3对shingle进行哈希,直接将长度为k的字符串用哈希函数映射成桶的编号，用这些桶的编号的集合来表示文件。由文档产生9shingle集合，在把每个9shingle映射成4个字节长的桶编号如果采用4shingle，与上面方法占用的空间相似。但是性能不一样。如果只有20个字符出现频繁，则4-shingle的数量是204。大部分项集是空的如果是9shingle,数量大为增加，映射到4个字节的桶，则每个桶
5、出现的概率大大增加,3.2.4基于词的shingle,在一个网页中，即有新闻报导，也有周边元素。在新闻报导和大量散文中，包括大量停用词，and,you,to等，频率高于周边元素。在多数应用中，都忽略掉这些词。如果是想比较新闻文本的相似性，则可以利用这个特点。Shingle定义为停用词后面的两个词（不管是否是停用词）,例子,AspokepersonforthesudzoCorporationrevealedtodaythatstudieshaveshownitisgoodforpeopletobuysudzoproducts.AspokepersonforthesudzothesudzoCorp
6、orationBuysudzo,3.3保持相似度的集合摘要,Shingle集合非常大。一个4shingle集合也是原始文件的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相似度,两个集合经随机排列转换之后得到的两个最小哈
7、希值相等的概率等于这两个集合的jaccard相似度假设只考虑s1和s2两个集合对应的列。,四种类型,GivencolumnsC1andC2,rowsmaybeclassifiedas:C1C2a11b10c01d00两列同时为0的行对于这两列的相似性没有贡献。.设x是两列都为1的行的数目y是其中一行为1的数目NoteSim(C1,C2)=x/(x+y).,3.3.3最小哈希,对行进行随机转换后，从上往下扫描。遇到两行均为1的概率是x/(x+y)总共有x+y行，两行均为1的个数有x个。两行均为1，也就是H(s1)=H(s1),3.3.4最小哈希签名,对于每一个行排列方式，每一个集合都有一个最小哈
8、希值如果有n个行排列方式（n一般是1百到数百），每个集合就能产生n个最小哈希值，把这些哈希值写成一个列向量。也称为哈希签名。每个集合的列向量组合在一起，写成一个矩阵，称为签名矩阵。文档的相似性就等于最小哈希值相等的概率,3.3.5最小哈希签名的计算,操作矩阵较为困难，操作较小的签名矩阵是可以的用签名矩阵记录行变换的结果，每一个位置只记录当前变换的最小的位置,3.4文档的局部敏感哈希算法,即使可以使用最小哈希将大文档压缩成小的签名并同时保存任意文档对之间的相似度，寻找相似文档对仍然是不可能的文档的数目太大实际上，只需要寻找那些相似性大于某个门限的文档对，而不是全部文档对。这就是局部敏感哈希,3.
9、4文档的局部敏感哈希算法,假设文档先表示为shingle集合，通过哈希处理，变为短签名集合基本想法：把签名矩阵分成子矩阵，使用多次哈希函数。具有相同部分的列将被哈希到同一个桶中只考察那些哈希到同一个桶里面的列的相似性,26,PartitionIntoBands,MatrixM,rrowsperband,bbands,Onesignature,27,MatrixM,rrows,bbands,Buckets,28,WhatbBandsofrRowsGivesYou,Similaritysoftwosets,Probabilityofsharingabucket,t,29,Example:b=20;
10、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）=
11、0D(x,y）=0ifandonlyifx=yD(x,y)=D(y,x)D(x,y)=D(x,z)+D(z,y)(三角不等式）,3.5.2欧式距离,3.5.3Jaccard距离,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
12、和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“hsaysxandyareequal.”上述函数的集合称为哈希函数簇,41,局部敏感哈希函数,在集合S上面定
13、义了距离空间d.函数簇H称为(d1,d2,p1,p2)-sensitive，如果对于S中的x和y:如果d(x,y)d2,对于H中的所有h，对于H中的所有h，h(x)=h(y)的概率最多是p2.,42,LSFamilies:Illustration,d1,d2,Highprobability;atleastp1,Lowprobability;atmostp2,?,43,Example:LSFamily,设S=sets,d=Jaccarddistance,H是所有行变换条件下的最小哈希函数构成的集合.ThenProbh(x)=h(y)=1-d(x,y).回忆最小哈希函数和Jaccard相似性的关系
14、的定理.,44,Example:LSFamily(2),记号:Hisa(1/3,2/3,2/3,1/3)-sensitivefamilyforSandd.,45,Comments,ForJaccardsimilarity,最小哈希函数给出了(d1,d2,(1-d1),(1-d2)-的函数簇.定理没有说明d1andd2之间的取值.,46,局部敏感函数簇的放大,在签名矩阵使用的“bands”技术可以做通用化扩展.Goal:the“S-curve”效果.ANDconstructionlike“rowsinaband.”ORconstructionlike“manybands.”,47,ANDofHa
15、shFunctions,给定一个函数簇H,构建函数簇H，H中德每个函数由H中的r个函数构成。Forh=h1,hrinH,h(x)=h(y)ifandonlyifhi(x)=hi(y)foralli.Theorem:IfHis(d1,d2,p1,p2)-sensitive,thenHis(d1,d2,(p1)r,(p2)r)-sensitive.Proof:Usefactthathisareindependent.,48,ORofHashFunctions,GivenfamilyH,constructfamilyHconsistingofbfunctionsfromH.Forh=h1,hbinH
16、,h(x)=h(y)ifandonlyifhi(x)=hi(y)forsomei.Theorem:IfHis(d1,d2,p1,p2)-sensitive,thenHis(d1,d2,1-(1-p1)b,1-(1-p2)b)-sensitive.,49,EffectofANDandORConstructions,AND使得所有的概率减少,如果恰当的选择r,可以使低的概率趋于0而高的概率不变。OR使所有的概率增加，如果恰当的选择b,可以使高的概率趋于1而低的概率不变。,50,组合使用两种构建方法,对于签名矩阵，可以在AND构建后使用OR构建.Orvice-versa.OranysequenceofANDsandORsalternating.,51,AND-ORComposition,概率p变为1-(1-pr)b.The“S-curve”studiedbefore.Example:TakeHandconstructHbytheANDconstructionwith
