集合相似度-minhash.doc

集合相似度-minhash
文章来源:http://fuliang./blog/1025638
第三章查找相似的Items
,从网页集合中找到近似重复的网页,这类网页通常是内容相同,但是有一些是关于不同站点和镜像的内容。
这章从集合中找到交集,交集和集合大小的相对比率表示相似度,展开介绍相似度。我们会介绍怎样把文本文档的相似性表示为集合问题,这种技术被称为指纹方式。然后介绍了minhashing,他可以将大的集合压缩,并从压缩后的版本导出原来集合的相似度。。
一个非常重要的问题是,我们要搜索相似的Items,我们需要比较两两比较,这需要比较太多
的次数,即使每一对比较都非常的简单,但是仍然需要非常大的计算量。使用"locality-senitive hashing"可以解决这个问题,他只搜索可能相似的pair。
最后,介绍了不通过集合交集来表达的形似度计算方法,然后介绍了LSH通用的框架,可以使用其他定义的相似度算法。
临近搜索应用

ard 相似度表示为: 两个集合S和T,
SIM(S,T) = |S ∩ T |/|S ∪ T |.
文档相似度
从文档比如网页或者新闻文章集中找出文本相似的文档,ard相似度可以很好的解决。
文本相似度具有很大的用处,比如找出重复或者近似重复的文档,测试两个文档完全重复是很好做的事情,但是有一些应用中,他们不是完全一样,而是共享很大一部分内容。有以下应用:
文章抄袭
查找文档的抄袭可以检测我们查找文档相似度的能力。抄袭者可能只有一部分时他自己的,他可能修改了措辞或者调整了句子的顺序,但是仍有50%是抄袭别人的。简单的逐字的对比来是检测不出复杂的抄袭。
镜像网页
一些流行的网站会把网页镜像到不同的域中,以此来均衡服务器压力。网站的镜像中的网页非常相似,但是并不是完全相同,他们可能会包含自己的域的信息,链接到其他的镜像而不是他们自身。能够检测出重复网页是一个很重要的应用,比如搜索引擎应该避免近似相同的两个网页同时出现在搜索结果的第一页。
同一个来源的文章
一个记者写的一篇新闻,可能被多个媒体使用,每一个可能只是将这篇文章做了一些修改,
比如删除掉了一些段落,添加了他们自己的内容,内容周边环绕了他们的logo,广告,链接到他们自己网站的其他文章。Google新闻应该能够找到这个文章的所有版本,并只显示出一个,这需要查找两篇文章的文本相似度。
基于相似集合的协同过滤
另一类使用集合相似度的应用是协同过滤,协同过滤描述了把具有相似口味的用户的items推荐给其他用户。
在线购物
比如在亚马逊有上百万的用户和物品,记录了哪些用户买了哪些物品,ard相似度,那么这两个客户也是相似的。
ard相似度,还需要一些其他的工具,比如两个客户都喜欢看科幻小说,但是他们购买了不同的小说,具有很少的重复,那么我们还需要通过组合相似度和聚类来做协同过滤。
电影分级评分
NetFlix记录了哪些客户租了哪些电影,已经他们对这些电影的评分,我们可以认为如果相同的顾客对不同电影评分比较高的,它们具有很大的相似性。
bag相似度:
{a, a,