相似度算法

2017-04-23文本相似度算法一、引语通过采集系统我们采集了大量文本数据，但是文本中有很多重复数据影响我们对于结果的分析。分析前我们需要对这些数据去除重复，如何选择和设计文本的去重算法？我们知道一篇文章或网页与某些内容或关键字之间的相关联程度，但是，有的时候，我们还想知道，某两篇文章是不是讲的是同一个主题，同一种内容。比如，我们想知道两篇文章是否都是金融类文章或者都是医学类文章。要知道，能不能确定两篇文章是否相似一、利用余弦定理是用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小的度量一、利用余弦定理TF-IDF（termfrequency–inversedocumentfrequency）是一种用于资讯检索与资讯探勘的常用加权技术。TF：TermFrequency词频IDF：Inversedocumentfrequency倒文档频率一、利用余弦定理频率的计算方法：用该网页的关键字出现的次数除以网页的总字数。我们把这个商称为TF（关键字的频率或者单文本的频率）。比如，某个网页中共有1000个词，其中“原子能”，“的”，“应用”分别出现了2次，35次和5次，那么它们的词频就分别是（2/1000）=0.002，（35/1000）=0.035，（5/1000）=0.005，这三个词频相加之和0.042就是这个网页相对于“原子能应用”这个关键字的TF（单文本词频）一、利用余弦定理含义：如果某个关键词出现在网页中出现，在网页总数个情况下，值越大，我们就认为关键词的权重越小，反之亦然。（如关键字“python”在10万个网页中出现，而“gensim”只在1000个网页中出现，那么“gensim”的权重就会比“python”多，这样搜索出来的结果就与你想要的结果越贴近）比如，假定中文网页数是=10亿，“的”在所有的网页中都出现，即D=10亿，那么它的IDF=log(10亿/10亿)=log(1)=0。假如专用词“原子能”在两百万个网页中出现，即Dw=200万，则它的权重IDF=log(500)=2.7。又假定通用词“应用”，出现在五亿个网页中，它的权重IDF=log(2)则只有0.3。一、利用余弦定理首先，我们针对一篇文章中所有实词计算出它们的TF-IDF值。然后，把这些值对应实词在词汇表中的位置进行排列，就能得到一个向量。比如，词汇表中有64000个词，其编号和词如下图从而，我们能够得到64000个数，组成64000维向量。我们使用这个向量来代表这个文章的特征信息一、利用余弦定理将三角形的两边b和c看成是以A为起点的向量，其中，分母表示两个向量b和c的长度，分子表示两个向量的内积一、利用余弦定理举一个具体的例子，假如文章X和文章Y对应的向量分别是那么它们的夹角的余弦等于一、利用余弦定理由于向量中的每一个变量都是正数，因此余弦的取值在0和1之间，也就是说夹角在0度到90度之间。当两篇文章的向量的余弦等于1时，这两个向量的夹角为零，两篇文章完全相同；当夹角的余弦接近于1时，两篇文章相似，可以认为属于同一类文章；当夹角的余弦趋近于零甚至于等于零时，说明它们直接相似度很低，甚至完全无关，术语两种完全不同的文章二、欧氏距离欧氏距离衡量的是空间各点的绝对距离，跟各个点所在的位置坐标直接相关欧氏距离和余弦距离各自有不同的计算方式和衡量特征，因此它们适用于不同的数据分析模型：欧氏距离能够体现个体数值特征的绝对差异，所以更多的用于需要从维度的数值大小中体现差异的分析，如使用用户行为指标分析用户价值的相似度或差异。余弦距离更多的是从方向上区分差异，而对绝对的数值不敏感，更多的用于使用用户对内容评分来区分兴趣的相似度和差异，同时修正了用户间可能存在的度量标准不统一的问题（因为余弦距离对绝对数值不敏感）。三、Jaccard相似度两个集合的交集除以两个集合的并集，所得的就是两个集合的相似度四、最长公共子串字符串的相似性：如果将一个串转换成为另一个串所需的操作数最少，那么可以说这两个串是相似的另外一种权衡的方法是，寻换第三个串s3，如果s3都出现在s1和s2中，且出现的顺序相同，但不要求在s1和s2中连续，那么s3的长度越大，就说明相似度越高。如果用暴力搜索的方法求解LCS问题，就要穷举X的所有子序列，对每个子序列进行检查，看它是否是Y的子序列，记录找到的最长的子序列。X对应下标人格集合{1，2，3……m}的一个子集，那么X的子序列就有2^m个五、编辑距离编辑距离的算法是首先由俄国科学家Levenshtein提出的，故叫Levenshtein距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。其它算法这些算法对于待比较的文本数据不多时还比较好用，如果我们的爬虫每天采集的数据以千万计算，我们如何对于这些海量千万级的数据进行高效的合并去重simhash算法simhash方法是在大文本重复识别常用的一个方法，该方法主要是通过将对象的原始特征集合映射为一个固定长度的签名，将对象之间的相似度的度量转化为签名的汉明距离，通过这样的方式，极大限度地进行了降低了计算和存储的消耗。1、分词把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重，我们假设权重分为5个级别（1~5）。比如：“美国“51区”雇员称内部有9架飞碟，曾看见灰色外星人”==分词后为“美国（4）51区（5）雇员（3）称（1）内部（2）有（1）9架（3）飞碟（5）曾（1）看见（3）灰色（4）外星人（5）”，括号里是代表单词在整个句子里重要程度，数字越大越重要。simhash算法2、hash通过hash算法把每个词变成hash值，比如“美国”通过hash算法计算为100101,“51区”通过hash算法计算为101011。这样我们的字符串就变成了一串串数字，还记得文章开头说过的吗，要把文章变为数字计算才能提高相似度计算性能，现在是降维过程进行时。3、加权通过2步骤的hash生成结果，需要按照单词的权重形成加权数字串，比如“美国”的hash值为“100101”，通过加权计算为“4-4-44-44”；“51区”的hash值为“101011”，通过加权计算为“5-55-555”。simhash算法4、合并把上面各个单词算出来的序列值累加，变成只有一个序列串。比如“美国”的“4-4-44-44”，“51区”的“5-55-555”，把每一位进行累加，“4+5-4+-5-4+54+-5-4+54+5”==》“9-91-119”。这里作为示例只算了两个单词的，真实计算需要把所有单词的序列串累加。5、降维把4步算出来的“9-91-119”变成01串，形成我们最终的simhash签名。如果每一位大于0记为1，小于0记为0。最后算出结果为：“101011”。其它算法simhash算法但是如何计算两个simhash的相似度呢？比较两个simhash的01有多少个不同海明距离两个simhash对应二进制（01串）取值不同的数量称为这两个simhash的海明距离举例如下：10101和00110从第一位开始依次有第一位、第四、第五位不同，则海明距离为3。通过大量测试，simhash用于比较大文本，比如500字以上效果都还蛮好，距离小于3的基本都是相似，误判率也比较低。但是如果我们处理的是微博信息，最多也就140个字，使用simhash的效果并不那么理想。精确率和召回率又被称为查准率和查全率为什么不直接hash“你妈妈喊你回家吃饭哦，回家罗回家罗”“你妈妈叫你回家吃饭啦，回家罗回家罗”。通过simhash计算结果为：10000100101011011111111000001010110100010011111000010010110010111000010010101101011111100000101011010001001111100001101010001011通过hashcode计算为：11111111111111111111111111111111100010000011001101001110110111101010010001111111110010110011101传统hash函数解决的是生成唯一值，比如md5、hashmap等。md5是用于生成唯一签名串，只要稍微多加一个字符md5的两个数字看起来相差甚远；总计及其他算法minhash方法介绍基于主题的相似度计算LSA简介基于hash方法的相似计算plas介绍simhash方法向量空间模型（Vectorspacemodel）余弦定理欧式距离shingling算法THANKS