相似度计算公式.doc

相似度计算在数据挖掘中经常需要用到比较两个东西的相似度。比如搜索引擎要避免非常相似的文档出现在结果的前几页,再比如很多网站上都有的“查找与你口味相似的用户”、“你可能喜欢什么什么”之类的功能。后者其实是很大的一块叫做“协同过滤”的研究领域,留待以后详谈。首先我们定义两个集合S,ard相似度:Sim(S,T)=|S,T的交集|/|S,T的并集|。直观上就容易感觉出这是一个很简单而且比较合理的度量,我不清楚有没有什么理论上的分析,在此省略。下面先主要说一下文档的相似度。如果是判断两个文档是否完全相同,问题就变得很简单,只要简单地逐字符比较即可。但是在很多情况下并不是这样,比如网站文章的转载,主体内容部分是相同的,但是不同网页本身有自己的Logo、导航栏、版权声明等等,不能简单地直接逐字符比较。这里有一个叫做Shingling的方法,其实说起来很圡,就是把每相邻的k个字符作为一个元素,这样整篇文档就变成了一个集合。比如文档是"banana",若k=2,转化以后得到集合为{"ba","an","na"},于是又变成了前述集合相似度的问题。关于k值的设置,显然过小或过大都不合适,据说比较短的比如email之类可以设k=5,比如长的文章如论文之类可以设k=9。当然,这是一个看上去就很粗糙的算法,这里的相似度比较只是字符意义上的,如果想进行语义上的比较就不能这么简单了(我觉得肯定有一摞摞的paper在研究这个)。不过同样可以想见的是,在实际中这个粗糙算法肯定表现得不坏,速度上更是远优于复杂的NLP方法。在实际工程中,必然糙快猛才是王道。有一点值得注意的是,Shingling方法里的k值比较大时,可以对每个片段进行一次hash。比如k=9,我们可以把每个9字节的片段hash成一个32bit的整数。这样既节省了空间又简化了相等的判断。这样两步的方法和4-shingling占用空间相同,但是会有更好的效果。因为字符的分布不是均匀的,在4-shingling中实际上大量的4字母组合没有出现过,而如果是9-shingling再hash成4个字节就会均匀得多。在有些情况下我们需要用压缩的方式表示集合,但是仍然希望能够(近似)计算出集合之间的相似度,此时可用下面的Minhashing方法。首先把问题抽象一下,用矩阵的每一列表示一个集合,矩阵的行表示集合中所有可能的元素。若集合c包含元素r,则矩阵中c列r行的元素为1,否则为0。这个矩阵叫做特征矩阵,往往是很稀疏的。以下设此矩阵有R行C列。所谓minhash是指把一个集合(即特征矩阵的一列)映射为一个0..R-1之间的值。具体方法是,以等概率随机抽取一个0..R-1的排列,依此排列查找第一次出现1的行。例如有集合S1={a,d},S2={c},S3={b,d,e},S4={a,c,d},特征矩阵即如下     S1  S2  S3  S4  0a   1   0   0   1 1b   0   0   1   0 2c   0   1   0   1 3d   1   0   1   1 4e   0   0   1   0设随机排列为43201(edcab),按edcab的顺序查看S1列,发现第一次出现1的行是d(即第3行),所以h(S1)=3,同理有h(S2)=2,h(S3)=4,h(S4)=3。此处有一重要而神奇的结论:对