文本相似性问题个人见解

? ? ? ?Jaccard :?

? ? ? ? 这是一种经典的计算相似性的方法，本文中主要讲下自己对于其如何应用于文章相似性的度量之中，其有效性根据实际数据集可能有所区别。

? ? ? ? ?对于需要计算的两篇文章A,B,通过对全文提取关键词，根据权重，选择top-K个关键词，这里的K可以自己调整，我采用的是10，通过计算A

? ? ?与B的关键字集合的Jaccard系数作为相似性度量，从而判断文章A,B是否相似。比如A的10个关键词为S(A){a,b,c,d,e,f,g,h,i,j}，B的关键词为S(B)

? ? {a,l,m,n,y,z}，其中小写字母表示某个关键词。那么Jaccard(A,B) = |S(A)交S(B)| / |S(A)并S(B)|，则Jaccard的可能取值为 i/(20-i)，i从0到10。

? ? ? ? ?这时，就涉及到，相似的阈值，以及重复的阈值了，就是min_threshold与max_threshold了，当Jaccard > min_threshold时，表示文章A、B相似，

? ? 而Jaccard > max_threshold时，则表示A、B过于相似，可认为文章重复，具体参数可根据数据集的不同，进行调整，这种方法虽然简单，但是经本

? ? 人通过项目中数据的判断结果观察，其效果还不错，用于相似文章判断，以及文章去重都可以。当然，前提是关键词要提取的准确，否则基本上不会

? ? 出现相似。

? ? ? ?SimHahs:

? ? ? ? ?这在我上篇博客中有讲到，这里重复一点概念吧，就是通过全文的划词结果，对于每个词计算权重，当然最简单的方式就是不计算权重，直接用划

? ? 词结果作计算，出现多次的词权重自然增加了。则对于每个词，计算其64位的Hash值，用64个实数保存对应位的结果，Hash值为1则加1，否则减1，当

? ? 所有词都计算完成之后，通过对应位的实数值不小于0则置为1，否则对应位置为0，从而得到一个64位的位数据D。通过对文章A、B的位数据D(A)与D(B)

? ? 进行异或操作，统计异或结果中位为 1 的个数，即不同位的个数，如果小于 n ，则表示文章非常相似，经验值为3。这是用来判断文章重复的方法，其作

? ? 为相似性度量方法似乎不佳，我做过实验，发现很多结果为30左右的，根本无法区分，当然可能这部分区分并无很大的意义，可是用于分类，尤其是聚类

? ? 准确的相似性的值还是非常重要的。

? ? ? ?cos:

? ? ? ? ? ?这是初中就开始学的东西了，没想到那么经用，cos即指余弦值，即然是余弦肯定有角度，那么也有边，就是说需要将文章向量化。一般是通过TFIDF

? ? 将文章转换为向量，再以向量之间的cos值作为相似性度量的方法，TFIDF这里就不详解了，自己百度，或者我以后可能会写点相关内容说明下，对于代表

? ? 文章A、B的向量V(A)、V(B)，计算cos值的公式为：V(A)点乘V(B)/(|V(A)|*|V(B)|)。cos值也算是非常经典的方法，其效果也还是不错的，就是时间消耗比较

? ? 大，不适用于海量数据的聚类或者其它数据挖掘任务。

? ? ? ? PS：提一下就今天同事说的一个面试别人的算法题，反转链表，仅说下方法。1. 递归，参数为下一结点，函数以尾结点为递归结果，指向当前结点，需要

? ? 将头结果作为引用参数传入，指向最后一次递归，即尾结点；2.利用栈，相当于模拟递归，从头入栈，出栈挨个链上；3. 采用循环实现，用三个指针即可。p

? ? 指向当前反转后的头，q下一个，r是q下一个用于标记，以名结点找不到了哈哈。q->next=p,p=q，q=r,r=q->next，加上些许边界判断，即可。