我的读书笔记(一)：数据信息中的相似度计算算法

我的读书笔记(一)：数据信息中的相似度计算算法无意中发现这本貌似不错的书MiningofMassiveDatasets，随便记一下学到的东西。因为对数据挖掘没什么研究，理解肯定很肤浅，请过往大牛指教。下面内容来自此书第三章的前面部分。在数据挖掘中经常需要用到比较两个东西的相似度。比如搜索引擎要避免非常相似的文档出现在结果的前几页，再比如很多网站上都有的''查找与你口味相似的用户〃、“你可能喜欢什么什么〃之类的功能。后者其实是很大的一块叫做''协同过滤〃的研究领域，留待以后详谈。首先我们定义两个集合S,T的Jaccard相似度：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},特征矩阵即如下SIS2S3S4TOC\o"1-5"\h\z0a10011b00102c01013d10114e0010设随机排列为43201(edcab),按edcab的顺序查看S1列,发现第一次出现1的行是d(即第3行)，所以h(S1)=3,同理有h(S2)=2,h(S3)=4,h(S4)=3。此处有一重要而神奇的结论：对于等概率的随机排列，两个集合的minhash值相同的概率等于两个集合的Jaccard相似度。证明：同一行的两个元素的情况有三种：X■两者都为1；Y■—个1一个0；乙两者都为0。易知Jaccard相似度为|X|/(|X|+|Y|)。另一方面，若排列是等概率的，则第一个出现的X中元素出现在Y中元素之前的概率也为|X|/(|X|+|Y|)，而只有这种情况下两集合的minhash值相同。于是方法就有了，我们多次抽取随机排列得到n个minhash函数hl,h2,…,hn，依此对每一列都计算n个minhash值。对于两个集合，看看n个值里面对应相等的比例，即可估计出两集合的Jaccard相似度。可以把每个集合的n个minhash值列为一列，得到一个n行C列的签名矩阵。因为n可远小于R,这样我们就把集合压缩表示了，并且仍能近似计算出相似度。在具体的计算中，可以不用真正生成随机