文本相似度的计算方法.docx

相似度计算方面Jaccard相似度：集合之间的Jaccard相似度等于交集大小与并集大小的比例。适合的应用包括文档文本相似度以及顾客购物习惯的相似度计算等。Shingling：k-shingle是指文档中连续出现的任意k个字符。如果将文档表示成其k-shingle集合，那么就可以基于集合之间的Jaccard相似度来计算文档之间的文本相似度。有时，将shingle哈希成更短的位串非常有用，可以基于这些哈希值的集合来表示文档。最小哈希：集合上的最小哈希函数基于全集上的排序转换来定义。给定任意一个排列转换，集合的最小哈希值为在排列转换次序下出现的第一个集合元素。最小哈希签名：可以选出多个排列转换，然后在每个排列转换下计算集合的最小哈希值，这些最小哈希值序列构成集合的最小哈希签名。给定两个集合，产生相同哈希值的排列转换所占的期望比率正好等于集合之间的Jaccard相似度。高效最小哈希：由于实际不可能产生随机的排列转换，因此通常会通过下列方法模拟一个排列转换：选择一个随机哈希函数，利用该函数对集合中所有的元素进行哈希操作，其中得到的最小值看成是集合的最小哈希值。签名的局部敏感哈希：该技术可以允许我们避免计算所有集合对或其最小哈希签名对之间的相似度。给定集合的签名，我们可以将它们划分成行条，然后仅仅计算至少有一个行条相等的集合对之间的相似度。通过合理选择行条大小，可以消除不满足相似度阈值的大部分集合对之间的比较。向量空间距离方面欧式距离：n维空间下的欧式距离，是两个点在各维上差值的平方和的算数平方根。适合欧式空间的另一个距离是曼哈顿距离，指两个点各维度的差的绝对值之和。Jaccard距离：1减去Jaccard相似度也是一个距离测度。余弦距离：向量空间下两个向量的夹角大小。编辑距离：该距离测度应用于字符串，指的是通过需要的插入、删除操作将一个字符串处理成另一个字符串的操作次数。编辑距离还可以通过两个字符串长度之和减去两者最长公共子序列长度的两倍来计算。海明距离：应用于向量空间。两个向量之间的海明距离计算的是它们之间不相同的位置个数。索引辅助方面字符索引：如果将集合表示成字符串，且需要达到的相似度阈值接近1。那么就可以将每个字符串按照其头部的一小部分字母建立索引。需要索引的前缀的长度大概等于整个字符串的长度乘以给定的最大的Jaccard距离。位置索引：我们不仅可以给出索引字符串前缀中的字符，也可以索引其在前缀中的位置。如果两个字符串共有的一个字符并不出现在双方的第一个位置，那么我们就知道要么存在某些前面的字符出现在并集但不出现在交集中，那么在两个字符串中存在一个更前面的公共字符。这样的话，我们就可以减少需要比较的字符串对数目。后缀索引：我们不仅可以索引字符串前缀中的字符及其位置，还可以索引当前字符后缀的长度，即字符串中该字符之后的位置数量。由于相同字符但是后缀长度不同意味着有额外的字符必须出现在并集但不出现在交集中，因此上述结构能够进一步减少需要比较的字符串数目。总结以上的一些概念和方法可以配合使用，可以基本满足许多场景下的相似度计算。相似度计算又可以为相关推荐做基础。怎么做好词的粒度切分，怎么划定阈值，选择何种距离测算，如何优化实现方法还是要下很多功夫的。两个例子Levenshtein其实是编辑距离，下面计算编辑距离的方法是把两个String串里的字/词当成一个矩阵来比较和计算。javaview plaincopy1. packagezbf.search.recommend;2. 3. publicclassLevenshteinDis4. 5. publicstaticvoidmain(Stringargs)6. /要比较的两个字符串7. Stringstr1=相似度计算方法;8. Stringstr2=文本相似项发现;9. levenshtein(str1,str2);10. 11. 12. publicstaticvoidlevenshtein(Stringstr1,Stringstr2)13. 14. intlen1=str1.length();15. intlen2=str2.length();16. 17. intdif=newintlen1+1len2+1;18. 19. for(inta=0;a=len1;a+)20. difa0=a;21. 22. for(inta=0;a=len2;a+)23. dif0a=a;24. 25. 26. inttemp;27. for(inti=1;i=len1;i+)28. for(intj=1;ji)51. min=i;52. 53. 54. returnmin;55. 56. 57. 下面是余弦距离计算的例子：javaview plaincopy1. publicclassCosineSimilarAlgorithm2. publicstaticdoublegetSimilarity(Stringdoc1,Stringdoc2)3. if(doc1!=null&doc1.trim().length()0&doc2!=null4. &doc2.trim().length()0)5. 6. MapAlgorithmMap=newHashMap();7. 8. /将两个字符串中的中文字符以及出现的总数封装到，AlgorithmMap中9. for(inti=0;idoc1.length();i+)10. chard1=doc1.charAt(i);11. if(isHanZi(d1)12. intcharIndex=getGB2312Id(d1);13. if(charIndex!=-1)14. intfq=AlgorithmMap.get(charIndex);15. if(fq!=null&fq.length=2)16. fq0+;17. else18. fq=newint2;19. fq0=1;20. fq1=0;21. AlgorithmMap.put(charIndex,fq);22. 23. 24. 25. 26. 27. for(inti=0;idoc2.length();i+)28. chard2=doc2.charAt(i);29. if(isHanZi(d2)30. intcharIndex=getGB2312Id(d2);31. if(charIndex!=-1)32. intfq=AlgorithmMap.get(charIndex);33. if(fq!=null&fq.length=2)34. fq1+;35. else36. fq=newint2;37. fq0=0;38. fq1=1;39. AlgorithmMap.put(charIndex,fq);40. 41. 42. 43. 44. 45. Iteratoriterator=AlgorithmMap.keySet().iterator();46. doublesqdoc1=0;47. doublesqdoc2=0;48. doubledenominator=0;49. while(iterator.hasNext()50. intc=AlgorithmMap.get(iterator.next();51. denominator+=c0*c1;52. sqdoc1+=c0*c0;53. sqdoc2+=c1*c1;54. 55. 56. returndenominator/Math.sqrt(sqdoc1*sqdoc2);57. else58. thrownewNullPointerException(59. theDocumentisnullorhavenotcahrs!);60. 61. 62. 63. publicstaticbooleanisHanZi(charch)64. /判断是否汉字65. return(ch=0x4E00&ch=0x9FA5);66. 67. 68. 69. /*70. *根据输入的Unicode字符，获取它的GB2312编码或者ascii编码，71. *72. *paramch73. *输入的GB2312中文字符或者ASCII字符(128个)74. *returnch在GB2312中的位置，-1表示该字符不认识75. */76. publicstaticshortgetGB2312Id(charch)77. try78. bytebuffer=Character.toString(ch).getBytes(GB2312);79. if(buffer.length!=2)80. /正常情况下buffer应该是两个字节，否则说明ch不属于GB2312编码，故返回?，此时说明不认识该字符81. return-1;82. 83. intb0=(int)(buffer0&0x0FF)-161;/编码从A1开始，因此减去0xA1=16184