第三章相似项发现-.ppt

第三章相似项发现-
3.1 近邻搜索的应用
相似度：通过计算交集的相对大小来获得集合之间的相似度，也称为Jaccard相似度
Sim (C1, C2) = |C1C2|/|C1C2|.
Example: Jaccard Similarity
3 in intersection.
8 in union.
Jaccard similarity
= 3/8
3
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.3.1 集合的矩阵表示
矩阵的列表示各个集合，行表示所有可能的元素
S1={a,d},s2={c},s3={b,d,e},s4={a,c,d}
元素
s1
s2
s3
s4
A
1
0
0
1
B
0
0
1
0
C
0
1
0
1
D
1
0
1
1
e
0
0
1
0