‘壹’ 文本、语音相似度算法
前段时间公司项目用到了语音识别,图像识别,视频识别等,其实不能说是识别,应该说是相似度对比吧,毕竟相似度对比还上升不了到识别哈,等以后有了更深的理解再来讨论修改下!这次就当做一个总结吧!
其实它的原理和视频图像相似度算法类似，将一系列的向量,特征,权重,进行合并,然后降维降到一维,其实这个算法也就是采用降维技术,将所有的特征都用一个唯一标识来表示.然后这个标识是经过这个算法内部的计算,再利用海明距离计算相似度，视频和图片是经过汉明距离计算的
文本我们是采用simhash算法：
1.我们给文本里面的词进行分词,我们是用ik算法,这个算法就是while循环,读取一行,然后调用ik智能分词的类,智能去切割里面的分词;
2.根据里面的词频,simhash算法会加一个权重,当然,得词频达到多少个的时候才会有有权重,这也是它的缺点,一般文本数据较少的时候,他是不准确的,一般数据量在500+;算法内部的话会将一系列的向量,特征,权重,进行合并,然后降维降到一维,其实这个算法也就是采用降维技术,将所有的特征都用一个唯一标识来表示.然后这个标识是经过这个算法内部的计算,然后得到的一个指纹签名；
3.然后对比两个文本的相似度就是将两个指纹签名进行海明距离计算,如果海明距离<8(根据业务和场景去判断这个值，8是建议，参考)的话,表示两个相似,小于3的话.表示两个文本重复.
simhash算法我们还可以做语音相似度,它的基本原理就是根据傅里叶变换处理得到声波的形状。
语音的坡度如果向上我们就用1表示,向下我们就用0表示,这样的话,我们也可以用二进制码去描述一首歌曲.得到一个唯一的指纹签名,对比两个音频的相似度就是将两个指纹签名进行海明距离计算<8的话,我们就默认两个音频相似.
总结：都是把特征降到一维，然后采用海明距离计算。计算的值小于多少时，就当做是相似。我这边讲的太浅了，实在领悟有限，时间有限，触摸不深，等下次有新的领悟再来补充！
‘贰’ 怎么用lucene判断两篇文章的相似度 java
用算法中的求最大相似子字符串的方法LCS或许可以，它可以找到两个字符串中最大相似的子字符串。
Java code
/*
* @author talent_marquis<甜菜侯爵>
* Email: [email protected]
* Copyright (C) 2007 talent_marquis<甜菜侯爵>
* All rights reserved.
*/
package ustc.mse.algorithms.dynamicProgramming;
/*
* LCS, Longest-Common-Subsequence
*/
public class LCS
{
public enum DIRECTION{ TOP, TOP_LEFT, LEFT };
private char[] first;
private char[] second;
private int[][] lcsTable;
private DIRECTION[][] lcsAssistTable;
private int lcsLength;
private String lcs_str, lcsMatrix_str, lcsAssistMatrix_str;
private StringBuffer str_buffer;
public LCS( String str1, String str2 )
{
first = str1.toCharArray();
second = str2.toCharArray();
lcsTable = new int[ first.length + 1 ][ second.length + 1 ];
lcsAssistTable = new DIRECTION[ first.length + 1 ][ second.length + 1];
lcs_str = null;
‘叁’ 文本相似度算法
TF是指归一化后的词频，IDF是指逆文档频率。给定一个文档集合D，有d1,d2,d3,......,dn∈D。文档集合总共包含m个词（注：一般在计算TF−IDF时会去除如“的”这一类的停用词），有w1,w2,w3,......,wm∈W。我们现在以计算词wi在文档dj中的TF−IDF指为例。
TF的计算公式为：
TF=freq(i,j) / maxlen(j)
在这里freq(i,j) 为wi在dj中出现的频率，maxlen(j)为dj长度。
TF只能时描述词在文档中的频率，但假设现在有个词为”我们“，这个词可能在文档集D中每篇文档中都会出现，并且有较高的频率。那么这一类词就不具有很好的区分文档的能力，为了降低这种通用词的作用，引入了IDF。
IDF的表达式如下：
IDF=log(len(D) / n(i))
在这里len(D)表示文档集合D中文档的总数，n(i)表示含有wi这个词的文档的数量。
得到TF和IDF之后，我们将这两个值相乘得到TF−IDF的值：
TF−IDF=TF∗IDF
TF可以计算在一篇文档中词出现的频率，而IDF可以降低一些通用词的作用。因此对于一篇文档我们可以用文档中每个词的TF−IDF组成的向量来表示该文档，再根据余弦相似度这类的方法来计算文档之间的相关性。
BM25算法通常用来做搜索相关性评分的，也是ES中的搜索算法，通常用来计算query和文本集合D中每篇文本之间的相关性。我们用Q表示query，在这里Q一般是一个句子。在这里我们要对Q进行语素解析（一般是分词），在这里以分词为例，我们对Q进行分词，得到q1,q2,......,qt这样一个词序列。给定文本d∈D，现在以计算Q和d之间的分数（相关性），其表达式如下：
Score(Q,d)=∑ti=1wi∗R(qi,d)
上面式子中wi表示qi的权重，R(qi,d)为qi和d的相关性，Score(Q,d)就是每个语素qi和d的相关性的加权和。
wi的计算方法有很多，一般是用IDF来表示的，但这里的IDF计算和上面的有所不同，具体的表达式如下：
wi=IDF(qi)=logN−n(qi)+0.5n(qi)+0.5
上面式子中N表示文本集合中文本的总数量，n(qi)表示包含qi这个词的文本的数量，0.5主要是做平滑处理。
R(qi,d)的计算公式如下：
R(qi,d)=fi∗(k1+1)fi+K∗qfi∗(k2+1)qfi+k2
其中
K=k1∗(1−b+b∗dlavgdl)
上面式子中fi为qi在文本d中出现的频率，qfi为qi在Q中出现的频率，k1,k2,b都是可调节的参数，dl,avgdl分别为文本d的长度和文本集D中所有文本的平均长度。
一般qfi=1，取k2=0，则可以去除后一项，将上面式子改写成：
R(qi,d)=fi∗(k1+1)fi+K
通常设置k1=2,b=0.75。参数b的作用主要是调节文本长度对相关性的影响。
‘肆’ 如何用wordnet计算 文本相似度 算法实现
1.信息检索中的重要发明TF-IDF
1.1TF
Term frequency即关键词词频，是指一篇文章中关键词出现的频率，比如在一篇M个词的文章中有N个该关键词，则
（公式1.1-1）
为该关键词在这篇文章中的词频。
1.2IDF
Inverse document frequency指逆向文本频率，是用于衡量关键词权重的指数，由公式
（公式1.2-1）
计算而得，其中D为文章总数，Dw为关键词出现过的文章数。
2.基于空间向量的余弦算法
2.1算法步骤
预处理→文本特征项选择→加权→生成向量空间模型后计算余弦。
2.2步骤简介
2.2.1预处理
预处理主要是进行中文分词和去停用词，分词的开源代码有：ICTCLAS。
然后按照停用词表中的词语将语料中对文本内容识别意义不大但出现频率很高的词、符号、标点及乱码等去掉。如“这，的，和，会，为”等词几乎出现在任何一篇中文文本中，但是它们对这个文本所表达的意思几乎没有任何贡献。使用停用词列表来剔除停用词的过程很简单，就是一个查询过程：对每一个词条，看其是否位于停用词列表中，如果是则将其从词条串中删除。
‘伍’ 相似度计算
你是求一个相似度算法：
如果一个公司真实排名为x1,
而你的打分排名是
x2，
怎么搞一个合理的评分数呢？
对差值的绝对值进行打分
|x1-x2|=0
得14分（28的一半)
|x1-x2|>=14
得
0分
就是：|差值|>14
得0分，|差值|<=14,得
14-|差值|
满分
14x28
分，
这样对28个排名，就可以算出得分了
相似度=得分/(14x28)
x
100
(%)
用c语言编个计算小程序很简单。
‘陆’ 文本相似度-bm25算法原理及实现
BM25算法，通常用来作搜索相关性平分。一句话概况其主要思想：对Query进行语素解析，生成语素qi；然后，对于每个搜索结果D，计算每个语素qi与D的相关性得分，最后，将qi相对于D的相关性得分进行加权求和，从而得到Query与D的相关性得分。
BM25算法的一般性公式如下：
其中，Q表示Query，qi表示Q解析之后的一个语素（对中文而言，我们可以把对Query的分词作为语素分析，每个词看成语素qi。）；d表示一个搜索结果文档；Wi表示 语素qi的权重 ；R(qi，d)表示 语素qi与文档d的相关性得分 。
下面我们来看如何定义 。判断 一个词的权重 ，方法有多种，较常用的是IDF。这里以IDF为例，公式如下：
其中，N为索引中的 全部文档数 ，n(qi)为 包含了qi的文档数。
根据IDF的定义可以看出，对于给定的文档集合， 包含了qi的文档数越多，qi的权重则越低 。也就是说，当很多文档都包含了qi时，qi的区分度就不高，因此使用qi来判断相关性时的重要度就较低。
我们再来看语素qi与文档d的相关性得分 。首先来看BM25中相关性得分的一般形式：
其中，k1，k2，b为 调节因子 ，通常根据经验设置，一般k1=2，k2=1，b=0.75；fi为 qi在d中的出现频率 ，qfi为 qi在Query中的出现频率 。dl为 文档d的长度 ，avgdl为 所有文档的平均长度 。由于绝大部分情况下，qi在Query中只会出现一次， 即qfi=1 ，因此公式可以简化为：
从K的定义中可以看到，参数b的作用是 调整文档长度对相关性影响的大小 。 b越大，文档长度的对相关性得分的影响越大 ，反之越小。而 文档的相对长度越长，K值将越大，则相关性得分会越小 。这可以理解为，当文档较长时，包含qi的机会越大，因此，同等fi的情况下，长文档与qi的相关性应该比短文档与qi的相关性弱。
综上，BM25算法的相关性得分公式可总结为：
分段再分词结果
列表的每一个元素是一个dict，dict存储着 一个文档中每个词的出现次数
存储每个词的idf值
['自然语言', '计算机科学', '领域', '人工智能', '领域']与每一句的相似度
https://github.com/jllan/jannlp/blob/master/similarity/bm25.py
‘柒’ 经典大规模文本相似识别架构和算法总结
在数据分析和挖掘领域，我们经常需要知道个体间差异大小，从而计算个体相似性。如今互联网内容爆发时代，针对海量文本的相似识别拥有极大需求。本文将通过识别两段文本是否相似，来看看常见的相似算法，及线上落地方案。
一般情况下，我们会将数据进行向量化，将问题抽象为数学问题。比如两个样本X、Y，X=（x1, x2, x3, … xn），Y=（y1, y2, y3, … yn）表示N维向量空间的两个样本，分析差异主要有距离度量和相似度度量。
文本向量化有很多方法，切词、ngram是最常用方法。一般的，分词加预处理能更好的表达语义，我们通过预处理，过滤掉无效字符及停用词。
对"组装衣柜，刚买不久" 和 "组装鞋柜，全新"向量化
距离（Distance）用于衡量样本在空间上的距离，距离越大，差异越大。
欧氏距离是最容易直观理解的距离度量方法，我们认知中两个点在空间中的距离就是欧氏距离。扩展到高维空间中，欧式距离的计算公式如图1：
图1 欧氏距离欧式距离因为计算是基于各维度特征的绝对数值，所以欧氏度量需要保证各维度指标在相同的刻度级别，当不同维度单位不同将使距离失去意义。
余弦相似度用向量空间中两个向量夹角余弦值作为衡量两个个体间差异的大小。余弦相似度更加注重两个向量在方向上的差异，而非距离或长度。公式如图2：
图2 余弦相似度
通过三维坐标系可以很直观的看到两者的区别，如图3所示：
图3 欧式距离和余弦相似度区别
欧氏距离和余弦相似度各自的计算方式和衡量特征，分别适用于不同的数据分析模型：欧式距离适应于需要从维度大小中体现差异的场景，余弦相似度更多的是方向上的差异。如果我们分词后，将每个词赋予一定的权重，那么可以使用欧氏距离。更多情况下，我们采用余弦相似度来计算两文本之间相似度。
上面的相似算法，适用于小量样本，两两计算。那么在大规模样本下，给定新的样本怎么找到相似的样本呢？
下面我们将引入 SimHash 算法。
SimHash是Google在2007年发表的一种指纹生成算法或者叫指纹提取算法（如图4），其主要思想是降维。
图4 SimHash算法
算法主要原理分为这几步：
大家可能存在疑问：生成一串二进制需要这么麻烦吗？直接用hash函数生成0和1的不是更简单。比如：md5和hashcode等。
可以看得出来，相似两个文本，simhash局部变化而普通的hashcode却天壤之别。文本转换为SimHash后，我们通过海明距离（Hamming distance）计算两个SimHash是否相似。
Google的论文给出的数据中，64位的签名，在汉明距离为3的情况下， 可认为两篇文档是相似。
为了查询相似，我们依然需要两两比较。但汉明距离算法给了我们降维的捷径。
可以证明，汉明距离小于3情况下，将hash code等分为4份，则必有一份完全相同。
基于上述特点，我们设计一个MySQL存储索引方案来实现，如图5所示。
图5 MySQL存储索引方案
‘捌’ 文本相似度之Sim_hash算法
本文记录的目的是方便自己学习和复习，有误之处请谅解，欢迎指出。
最近项目有用到Sim_hash，做个简单记录。
Sim_hash是Google用来处理大量文本去重的算法，属于 局部敏感哈希（Locality Sensitive Hashing，LSH） ，LSH哈希能够使两篇只有小部分改动的文章编码后哈希值具有相似性，既可用于去重，也可用于计算相似度。对于只有小部分改动的两篇文章，在计算他们之间的相似度时，如果采用md5，两篇文章的md5编码值差异会非常大。但使用局部敏感哈希可以使相似的文章哈希编码后聚集在一起，删除符合阈值条件的文章，达到去重的效果。
一、算法流程
1）分词：对文本进行去停用词、分词，提取n个关键词和关键词的tf-idf权重来表征文章。如下图分词及权重。
2）关键词哈希编码：每个关键词通过hash函数生成固定位数二进制哈希。
3）权重编码：二进制编码中0调整为-1变为权重向量，与权重相乘。
4）权重编码叠加：将所有权重编码纵向求和，得到最终的文章权重。
5）二值化：按正数为1负数为0的规则将文章权重二值化。
6）汉明距离相似度：排除汉明距离小于阈值的文章，一般设置为3。汉明距离计算速度快，思路简单，原理是计算两个二值化编码相同位置处的不同值的个数。
二、Sim_hash整体流程
需求： 来了一个相似文章推荐需求，需要推荐出与文章内容相似的数据，但又不能完全相似。利用目前库中已有的POI标签和POI权重数据，结合simhash算法，计算出每个文章poi_sim_hash，计算距离
数据： 线上拉取10W文章数据
测试结果： 下图为随机抽样的测试结果（第一条为查询数据），基本 符合预期效果 。前期还可以使用 类目和发布时间 进行前置过滤，减少数据量。