文本相似度计算方法归类

基于字符串。该方法从字符串匹配度出发，以字符串共现和重复程序为相似度的衡量标准。如编辑距离。
基于语料库。该方法利用从语料库中获取的信息计算文本相似度。如Word2Vec。
基于搜索引擎。主要是基于归一化谷歌距离(Normalized Google Distance, NGD)，通过计算关键词x, y网页数据的归一化实现计算文本相似度。
基于世界知识。该方法利用具有规范组织体系的知识库计算文本相似度，主要分为基于本体知识与基于网络知识两种。其典型的是语义相似性。
去重算法(搜索引擎提法比较多)。如Google的SimHash。

1564111127132

参考：文本相似度计算方法研究综述. 2017. 陈二静, 姜恩波.

流程

1564141808708

算法对比

算法特点与工程特性。

算法	特点
KShingle	特征向量是超高维，很大的时间复杂度和空间复杂度
Minhash	针对KShingle，Minhash算法设计了一种最小哈希函数，将原始超高维的稀疏向量转化为低维的稠密向量
SimHash	KShingle算法和Minhash算法都需要生成一个庞大的Shingle词组库。 Simhash算法仅基于文档中包含的词汇生成文档的特征向量
KSentence	算法基于一个朴素的假设：两个重复文本中，最长的K个句子应该是完全一样的

preview

实验对比Minhash、Simhash、KSentence的性能，结果如下：

运行速度：KSentence > Simhash > Minhash

准确率：KSentence > Minhash > Simhash

召回率：Simhash > Minhash > KSentence

工程应用上，海量文本用Simhash，短文本用Minhash，追求速度用KSentence。

Ref: https://zhuanlan.zhihu.com/p/43640234

SimHash算法

特点：工程实践性强，速度快，资源消耗少。

原理

img

simhash值计算

将Doc进行关键词抽取(其中包括分词和计算权重)，抽取出n个(关键词，权重)对，即图中的(feature, weight)们。记为 feature_weight_pairs =[fw1, fw2 … fwn]，其中 fwn = (feature_n,weight_n)。
hash_weight_pairs = [ (hash(feature), weight) for feature, weight in feature_weight_pairs ] 生成图中的(hash,weight)们, 此时假设hash生成的位数bits_count = 6（如图）;
然后对 hash_weight_pairs 进行位的纵向累加，如果该位是1，则+weight,如果是0，则-weight，最后生成bits_count个数字，如图所示是[13, 108, -22, -5, -32, 55], 这里产生的值和hash函数所用的算法相关。
[13,108,-22,-5,-32,55] -> 110001，正1负0。

simhash值的海明距离计算

simhash本质上是局部敏感性的hash，和md5之类的不一样。所以我们可以使用海明距离来衡量simhash值的相似度。

二进制串A 和二进制串B 的海明距离就是 A xor B 后二进制中1的个数。

举例如下：

A = 100111;
B = 101010;
hamming_distance(A, B) = count_1(A xor B) = count_1(001101) = 3;

文档是否相似的条件

A和B的海明距离是否小于等于n，这个n值根据经验一般取值为3。

Demo

s1 = '''
基于深度神经网络的机器学习模型在很多任务上达到了前所未有的性能。这些模型一般被视为复杂的系统,很难进行理论分析。此外,
由于主导最优化过程的通常是高维非凸损失曲面,因此要描述这些模型在训练中的梯度动态变化非常具有挑战性。就像在物理学中常⻅的那
样,探索此类系统的理想极限有助于解决这些困难问题。对于神经网络来说,其中一个理想极限就是无限宽度( infinite width ),即全连
接层中的隐藏单元数,或者卷积层中的通道数无穷大。'''

s2 = '''
基经网络的机器学习模型在很多任务上达到了前所未有的性能。这些模型一般被视为复杂的系统,很难进行理论分析。此外,
由于主导最优化过程的通常是高维非凸损失曲面,因此要描述这些模型在训练中的梯度动态变化非常具有挑战性。就像在物理学中常⻅的那
样,探索此类系统的理想极限有助于解决这些困难问题。对于神经网络来说,其中一个理想极限就是无限宽度( infinite width ),即全连
接层中的隐藏单元数,或者卷积层中的通道数无穷大。'''

s3 = '''
我们是的神经网络的机器学习模型在很多任务上达到了前所未有的性能。这些模型一般被视为复杂的系统,很难进行理论分析。此外,
由于主导最优化过程的通常是高维非凸损决这些困难问题。对于神经网络来说,其中一个理想极限就是无限宽度( infinite width ),即全连
接层中的隐藏单元数,或者卷积层中的通道数无穷大。'''

s4 = '''
目前,微信智言团队由来自微软和 CMU 的 T4 专家坐镇,共有 10 多名成员,全部来自国外内顶尖高校的硕士及博士,且都具备学术研究能
力与开发能力。微信智言透露,团队每两个月都会请第三方机构对团队的对话系统实力进行评估。结果表明,从对话、用户满意度角度来
说,微信智言基本上处于第一梯队。不过,微信智言也强调:竞赛成绩能够展现研究实力,但团队最主要重心,始终在业务上。瞄准四大领
域微信智言的目标,是打造 “ 对话即服务 ” 平台。'''

s5 = 'aa'

相似结果：

BenchMark

两篇各2000字中文文档，基于jieba分词，i5-6500单核，17秒/200轮。

改进

计算feature时使用TF-IDF计算。

Ref

SimHash pip: https://github.com/leonsim/simhash

SimHash Python实现与讲解：https://blog.csdn.net/madujin/article/details/53152619

SimHash 原理: http://yanyiwu.com/work/2014/01/30/simhash-shi-xian-xiang-jie.html

可视化

如以编辑距离呈现的可对比图。

不足：

其以行为单位计算diff
改动比较大时，行内的不同之处就无法呈现，因其直接计算成替换了

改进：

diff一般是字符为单位的删除、插入等，可以改造为手动实现以句为单位的diff。

1564113104326

图片

是否考虑图片相似性，如phash算法。

文本相似度计算与展示