第三章 相似项发现.pptxVIP

第三章 相似项发现3.1 近邻有哪些信誉好的足球投注网站的应用相似度：通过计算交集的相对大小来获得集合之间的相似度，也称为Jaccard相似度Sim (C1, C2) = |C1?C2|/|C1?C2|.Example: Jaccard Similarity3 in intersection.8 in union.Jaccard similarity = 3/83.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个字母之一，可能有27^5个字串对于论文来说，k取9较为合适3.2.3 对shingle进行哈希直接将长度为k的字符串用哈希函数映射成桶的编号，用这些桶的编号的集合来表示文件。由文档产生9 shingle 集合，在把每个9 shingle 映射成4个字节长的桶编号如果采用4 shingle，与上面方法占用的空间相似。但是性能不一样。如果只有20个字符出现频繁，则4-shingle的数量是20^4。大部分项集是空的如果是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 sudzo3.3 保持相似度的集合摘要Shingle 集合非常大。一个4 shingle 集合也是原始文件的4倍想办法计算文件的签名（一个较小的文件），通过计算签名的相似性来推断文件之间的相似性。3.3.1 集合的矩阵表示元素s1s2s3s4A1001B0010C0101D1011e0010矩阵的列表示各个集合，行表示所有可能的元素S1={a,d},s2={c},s3={b,d,e},s4={a,c,d}3.3.2 最小哈希首先选择行的一个排列变换。任