Monthly Archives: January 2011

读书笔记:相似度计算(2)

如果有N个集合,求它们之间两两的相似度就需要N*(N-1)/2次计算,当N很大时这个代价仍然承受不起。于是我们需要一种方法能够不遍历所有可能的元素对就找出相似度较大的那些(大于某个给定的阈值t),这就是所谓Locality-Sensitive Hashing。第三章的后半部分基本全是围绕这一话题展开的。

这里又要出现一个比较神奇的方法了:由上篇文章所述,对每一列c(即每个集合)我们都计算出了n行minhash值,我们把这n个值均分成b组,每组包含相邻的r=n/b行。对于每一列,把其每组的r个数都算一个hash值出来,把此列的编号记录到hash值对应的bucket里。如果两列被放到了同一个bucket里,说明它们至少有一组(r个)数的hash值相同,此时可认为它们有较大可能相似度较高(称为一对candidate)。最后在比较时只对落在同一个bucket里的集合两两计算,而不是全部的两两比较。

下面进行一点理论上的分析。如果两个集合被放到一个桶里,说明它们至少有一组minhash值是相同的。设两个元素的一次minhash值相同的概率是s(就是那个Jaccard相似度),那么一组全相同的概率是s^r,则b组中至少有一组相同的概率为1-(1-s^r)^b。如果b和r固定,那么此概率与s值形成的曲线是一个S型。S型斜率最高的点大约在(1/b)^(1/r)处。

S-Curve

可以发现这个算法只能得到近似的结果,有可能两个相似度大于阈值t的集合没有被放到一个桶里,于是就漏掉了;另外也可能相似度小于t的集合被放到了一个桶里,造成了无效的计算。我们希望这两种错误都尽可能地小。形式化一点就是,我们定义一种函数(Locality-Sensitive Function, LSF),它把一个集合映射为一个值,如果两个集合映射到的值相同,就认为他们有可能相似度较高。这个函数的好坏可以用一个四元组(d1,d2,p1,p2)表示,意思是说,如果两集合的距离(此处我们把距离定义为1减去Jaccard相似度)小于d1,则它们至少有p1的概率映射为同一个值;如果两集合的距离大于d2,则它们至多有p2的概率映射为同一个值。可以发现对于同样的一对(d1,d2),p1越大p2越小,那么这个函数的效果就越好。

对于上述minhash的例子,如果只用一次minhash值作为LSF,那么它是(d1,d2,1-d1,1-d2)-sensitive,此时其实那个S-曲线是一条直线。比如令d1=0.2, d2=0.6,它就是(0.2, 0.6, 0.8, 0.4)。而如果我们用4组每组4个minhash值按上述方法计算,那么它是(0.2, 0.6, 0.8785, 0.0985),可以发现p1变大而p2变小了。在极端情况下,如果b和r都很大,那个S曲线将近似成为一个分段函数,一开始的时候几乎一直是0,突然极快地跳到接近1,这时效果是非常好的,但是需要大量的minhash值计算。

另外,这里对于LSH的讨论实际上是很一般化的,待比较的东西不一定是集合,“距离”的定义不一定非和Jaccard相似度有关,LSF函数也不一定和minhash算法有关。比如可以定义01串的hamming距离,或者欧氏空间中的点的距离等等。对于hamming距离,LSF可定义为随机取一个二进制位看其是否相同,那么对于两个长度为L,Hamming距离为d的串,相同的概率就是d/L,所以是(d1,d2,1-d1/L,1-d2/L)-sensitive,此时同样可以用多次取值的方法进行加强。对于欧氏空间的点,情况比较复杂,书上给了一个二维空间的例子,方法是随机取一条直线并将其划分成固定长度的小段,将两个点映射到这条线上,看其是否落入同一个小段内。也可以推出一个四元组的结果,不过推导比较麻烦,在此略过。

读书笔记:相似度计算(1)

无意中发现这本貌似不错的书 Mining of Massive Datasets,随便记一下学到的东西。因为对数据挖掘没什么研究,理解肯定很肤浅,请过往大牛指教。下面内容来自此书第三章的前面部分。

在数据挖掘中经常需要用到比较两个东西的相似度。比如搜索引擎要避免非常相似的文档出现在结果的前几页,再比如很多网站上都有的“查找与你口味相似的用户”、“你可能喜欢什么什么”之类的功能。后者其实是很大的一块叫做“协同过滤”的研究领域,留待以后详谈。

首先我们定义两个集合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},特征矩阵即如下
    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。

此处有一重要而神奇的结论:对于等概率的随机排列,两个集合的minhash值相同的概率等于两个集合的Jaccard相似度。

证明:同一行的两个元素的情况有三种:X.两者都为1;Y.一个1一个0;Z.两者都为0。易知Jaccard相似度为|X|/(|X|+|Y|)。另一方面,若排列是等概率的,则第一个出现的X中元素出现在Y中元素之前的概率也为|X|/(|X|+|Y|),而只有这种情况下两集合的minhash值相同。

于是方法就有了,我们多次抽取随机排列得到n个minhash函数h1,h2,…,hn,依此对每一列都计算n个minhash值。对于两个集合,看看n个值里面对应相等的比例,即可估计出两集合的Jaccard相似度。可以把每个集合的n个minhash值列为一列,得到一个n行C列的签名矩阵。因为n可远小于R,这样我们就把集合压缩表示了,并且仍能近似计算出相似度。

在具体的计算中,可以不用真正生成随机排列,只要有一个hash函数从[0..R-1]映射到[0..R-1]即可。因为R是很大的,即使偶尔存在多个值映射为同一值也没大的影响。

扫地僧

考期日近,吾焦头烂额之际,幸获密友所赠复习资料,乃欲翻印研习之。及至打印店,门庭若市,皆吾等为考试所苦之辈。

翻印毕,资料不慎遗落一页,打印店扫地小工拾之,凝视片刻曰:“此处有错矣。”吾初哂笑:“此课程唤作‘泛函分析’,繁复之至,虽系里学霸亦感棘手。汝区区小工,何口出狂言哉!”小工手指书页曰:“小子诚不欺君,此处漏一积分符号矣。”吾细观之,果如其所述,乃大惊,复问其详。小工遂将考试重点并繁复精微难解之处一一点拨,令吾顿生醍醐灌顶之感,自信及格无忧矣。

吾心下惊疑,故拜谢问曰:“君乃打印店小工,缘何精通此高等课程?”笑对曰:“小子来此久矣。每临期末,必有众生持各科资料来此翻印,小子偶尔留意之。汝等课程又多为死记硬背无需求甚解者,小子虽驽钝,耳濡目染,日复一日,不精亦难矣!”又曰:“非独‘泛函分析’,北洋学堂各门派类别课程,小子皆略知一二。”吾遂试以理工文史各门类课程问之,果如其所述,竟至“马克思主义”等奇诡之学,亦是对答如流。

吾惊为奇才,复问:“以足下之聪慧,若进京赶考,定能金榜题名,荣华富贵享用不尽。为何竟在此甘于小工也?”小工云:“实不相瞒,吾乃北方罗刹国人士。本与吾兄隐居山林,采菇为生,实无意功名利禄也。然吾兄近年痴迷数学,不事劳作,生计日艰。吾只得略作乔装,来此中原之地作工,以工资接济兄长。近获知吾兄终破解某绝世难题,心愿已了,乃重返山林劳作。吾不日亦将归矣。”

语讫,飘然而去。

================================================

后记:感于网上各种版本的扫地大妈故事流传,无聊YY了一篇。请轻拍,哈哈。

一篇总结

总的来说,两年半的研究生生活不很如意,各个方面都不很如意,但又不是糟糕到一塌糊涂,所以感觉就是很憋。显然没有什么开心的事能痛快地笑,但也没有什么特别难过的事能痛快地哭,各种不爽都无处发泄。相比于本科几年的风风火火大起大落,日子过得平淡而没有回忆,仿佛一眨眼之间几年就过去了。话说最近看到同学的入党申请书,从学习方面、生活方面、思想方面等等分别描述,下面我也就仿照此模式来写。

科研方面,不靠谱地混了下来,好歹毕业证是拿到了,我也从一个对学术研究有一定憧憬的无知少年,逐渐认清了无奈的现实。现实是什么呢?鉴于此blog的读者还有不少在读或将读研究生的,为了给小朋友们保留一个美好的想象,我就不详述了。概括来讲,我感觉自己就是这个笑话里的猪。Anyway,总算是要解放了,我已经战战兢兢憋闷了太久,想到今后自由的生活,我就忍不住热血沸腾啊沸腾。我要给不明真相的群众演示一下什么叫创造力和行动力,什么叫下山的猛虎入海的蛟龙脱缰的野驴奔腾的草泥马,wohaha……抱歉老衲失态了,继续继续。

找工作方面,结果也不是让我非常满意。最后是定下了腾讯北京,也拿到了几个差不多水平的其他offer,其实我也不清楚哪个选择是最好的。因为之前也没有任何公司的实习经历,完全是凭自己的主观印象以及师兄和同学的一些评价做的决定,好在换工作比换导师还是要容易很多的。在此也感谢在我找工作过程中给予帮助的人们,名单比较长我就不一一列举了,江湖路远,来日方长。

之所以说不是非常满意,主要还是因为被Google拖了一个半月然后拒掉这件事。在此我还是想重复一下我的RP观:除非有充分的把握,否则应按RP最坏的情况做出计划。一件坏事如果有0.1%的概率会发生,那么你可以无视,但如果有10%的概率会发生,你最好认为它一定会发生。ACMer都知道最坏情况复杂度分析,一个好的算法不应该假设数据是仁慈的,我认为人生也一样。譬如拿到Google的offer,这就是一件我没有充分把握的事情,所以就不要对好结果有过分的期待。如果真的想拿,如前所述,那就只有把自己的水平提高到有90%以上的把握。

插一句嘴,上面模型的参数10%是以我自己前二十多年的样本数据为训练集调出来的一个经验值,大家知道我的RP向来是比较低的,所以对读者您来说这个值可以设得大一些。不过也建议您不要过于乐观,因为如果您能看懂这篇文章,99%的可能您是一个中国人,不要忘了自己投胎时选的可是Hard模式。

感情方面,我只能说,弱水三千,可我拿着一把漏勺。按照上述理论分析的话,我觉得对这种事我这辈子也做不到90%以上的把握了,只能寄希望于我那可怜的RP了,希望某一天哪个姑娘一时想不开吧。曾经有一段时间找一个mm的愿望很迫切,结果就是很杯具地验证了什么叫欲速则不达。现在已经比较淡定了,觉得自己除了丑了点矮了点穷了点智商和情商低了点,其实也不算一无是处,努力改善一下自己的形象,补补漏勺上的窟窿眼,总有一天会遇到一个想不开的姑娘的。至于在这之前么……我刚买了一个500G的硬盘,你懂的。

最后一句话,我觉得其实我还是挺nb的。