MMD_2a_FindSimilarSets

概述

application

there are many data-mining problems which can be expressed as finding similar sets, such as:

• pages with similar words, e.g., for classification by topic
• recommendation systems, classification by people or movie
• entity resolution, different informs all point to one person

这里写图片描述

essential parts

这里写图片描述

shingling

这里写图片描述

minhashing

jaccard similarity measure

这里写图片描述

matrix represent

这里写图片描述

minihash

总体步骤

这里写图片描述

例子

这里写图片描述

性质

这里写图片描述

签名的相似性

这里写图片描述

implementation

将对矩阵的转置操作用不同的hash函数代替。

这里写图片描述

LSH

LSH means locality-sensitive hashing.

概述

• general idea: generate from the collection of all elements (signatures in our examples) a small list of candidates pairs : pairs of elements whose similarity must be evaluated.
• for signature matrices: hush columns to many buckets, and make elements of the same bucket candidate pairs.

候选pairs的规则

这里写图片描述

LSH具体阐述

这里写图片描述

例子

这里写图片描述

概率分析

这里写图片描述

总结

这里写图片描述

得到更多的signature（但是会有更多的空间占用与计算），可以有更大的b和r，能够获得更step的函数。

LSH Application

entity resolution

fingerprint

similar news articles