当前位置:   article > 正文

数据挖掘基础-1.文本相似度_文本余弦相似度

文本余弦相似度

一、文本相似度

相似度度量指的是计算个体间相似程度,一般使用距离来度量,相似度值越小,距离越大,相似度值越大,距离越小。在说明文本相似度概念和计算方式之前,先回顾下余弦相似度。

1.余弦相似度

衡量文本相似度最常用的方法是使用余弦相似度。

 – 空间中,两个向量夹角的余弦值作为衡量两个个体之间差异的大小

 – 余弦值接近1,夹角趋于0,表明两个向量越相似

– 余弦值接近0,夹角趋于90,表明两个向量越不相似

2.计算文本相似度

度量两篇文文章的相似度流程如下:

思路:1、分词;2、列出所有词;3、分词编码;4、词频向量化;5、套用余弦函数计量两个句子的相似度。

下面我们介绍使用余弦相似度计算两段文本的相似度的具体例子。

使用余弦相似度算法计算文本相似度 - alunbar - 博客园
 
句子A:这只皮靴号码大了。那只号码合适。
句子B:这只皮靴号码不小,那只更合适。
1、分词:
使用结巴分词对上面两个句子分词后,分别得到两个列表:
listA=[‘这‘, ‘只‘, ‘皮靴‘, ‘号码‘, ‘大‘, ‘了‘, ‘那‘, ‘只‘, ‘号码‘, ‘合适‘]
listB=[‘这‘, ‘只‘, ‘皮靴‘, ‘号码‘, ‘不小‘, ‘那‘, ‘只‘, ‘更合‘, ‘合适‘]
 
2、列出所有词,将listA和listB放在一个set中,得到:
set={'不小', '了', '合适', '那', '只', '皮靴', '更合', '号码', '这', '大'}
将上述set转换为dict,key为set中的词,value为set中词出现的位置,即‘这’:1这样的形式。
dict1={'不小': 0, '了': 1, '合适': 2, '那': 3, '只': 4, '皮靴': 5, '更合': 6, '号码': 7, '这': 8, '大': 9},可以看出“不小”这个词在set中排第1,下标为0。
 
3、将listA和listB进行编码,将每个字转换为出现在set中的位置,转换后为:
listAcode=[8, 4, 5, 7, 9, 1, 3, 4, 7, 2]
listBcode=[8, 4, 5, 7, 0, 3, 4, 6, 2]
我们来分析listAcode,结合dict1,可以看到8对应的字是“这”,4对应的字是“只”,9对应的字是“大”,就是句子A和句子B转换为用数字来表示。
 
4、对listAcode和listBcode进行oneHot编码,就是计算每个分词出现的次数。oneHot编号后得到的结果如下:
listAcodeOneHot = [0, 1, 1, 1, 2, 1, 0, 2, 1, 1]
listBcodeOneHot = [1, 0, 1, 1, 2, 1, 1, 1, 1, 0]
下图总结了句子从分词,列出所有词,对分词进行编码,计算词频的过程

5、得出两个句子的词频向量之后,就变成了计算两个向量之间夹角的余弦值,值越大相似度越高。
listAcodeOneHot = [0, 1, 1, 1, 2, 1, 0, 2, 1, 1]
listBcodeOneHot = [1, 0, 1, 1, 2, 1, 1, 1, 1, 0]

根据余弦相似度,句子A和句子B相似度很高。

下面讲解如何通过一个预料库,提取出一篇文章的关键词。

二、TF-IDF

关键词可以让人快速了解一篇文章,根据上面分析,如果两篇文章的关键词是相似的,那么两篇文章就很可能是相似的。【当然,读者可能已经发现,本篇博客讲解的是通过字面来衡量两篇文章的相似度,而非通过字义角度】通常,使用TF-IDF值来度量一个词的重要性,该值越大,说明词越能描述文章的意思,下面具体讲解。

1.词频TF

如果一个词很重要,在文章中就会多次出现,这可以用词频—TF(Term Frequency)来衡量。

计算公式:

词频(TF) = 某个词在文章中出现的次数/文章的总词数

或者

词频(TF) = 某个词在文章中出现的次数/该文出现次数最多的词的出现次数

两个公式的区别是:第二个公式可以将不同词的TF值拉的更开。举个例子,假设某篇文章共1000个词,A出现了10次,B出现了11次,A和B通过公式1计算出的TF值差距很小,假设出现次数最多的词C出现的次数是100,A和B通过公式2计算出的TF值差距相比更大一些,更有利于区分不同的词。

在文章中,还存在“的”“是”“在”等常用词,这些词出现频率较高,但是对描述文章并没有作用,叫做停用词(stop words),必须过滤掉。同时如果某个词在语料库中比较少见,但是它在某文章中却多次出现,那么它很可能也反映了这篇文章的特性,这也可能是关键词,所以除了计算TF,还须考虑反文档频率(idf,inverse document frequency)

2.反文档频率IDF

IDF的思想是:在词频的基础上,赋予每个词权重,进一步体现该词的重要性。最常见的词(“的”、“是”、“在”)给予最小的权重,较常见的词(“国内”、“中国”、“报道”)给予较小的权重,较少见的词(“养殖”、“维基”)给与较大的权重。

计算公式:

IDF = log(词料库的文档总数/包含该词的文档数+1)

TF-IDF与一个词在文档中的出现次数成正比,与包含该词的文档数成反比。值越大就代表这个词越关键。

3.应用1-相似文章

使用TF-IDF算法,可以找出两篇文章的关键词;可以设置一个阀值,超过该值的认定为关键词,或者取值排名靠前的n个词作为关键词。

每篇文章各取出若干个关键词(比如20个),合并成一个集合,计算每篇文章对于这个集合中的词的词频(为了避免文章长度的差异,可以使用相对词频,即除以对应文章的总词数,相当于对词频进行了标准化处理)。

生成两篇文章各自的词频向量,计算两个向量的余弦相似度,值越大就表示越相似。

4.应用2-自动摘要

文章的信息都包含在句子中,有些句子包含的信息多,有些句子包含的信息少。"自动摘要"就是要找出包含信息最多的句子。句子的信息量用"关键词"来衡量。如果包含的关键词越多,就说明这个句子越重要。

只要关键词之间的距离小于“门槛值”,就认为处于同一个簇之中,如果两个关键词距离有5个词以上(值可调整),就把这两个关键词分在两个不同的簇中。

对于每个簇,计算它的重要性分值。

例如:其中的某簇一共有7个词,其中4个是关键词。因此,它的重要性分值等于 ( 4 x 4 ) / 7 =2.3

简化做法:不再区分"簇",只考虑句子包含的关键词。

三、TF-IDF的Python实现

下面使用Python计算TF-IDF,前提是有一个预料库。这里总共有508篇文章,每篇文章中,都已经提前做好了分词。

1.计算IDF

思路:将语料库中的每篇文章放入各自的set集合中,再设定一个大的set,将之前各篇文章的set集合依次放入这个大的set中,得到的即每个词以及词出现的次数,词对应的次数即拥有该词的文章数。

1)convert.py

  1. import os
  2. import sys
  3. files_dir = sys.argv[1]    //获得输入的参数,即语料库路径
  4. for file_name in os.listdir(files_dir):     //函数会返回目录下面的所有文件名称
  5.     file_path = files_dir + file_name
  6.     file_in = open(file_path, 'r') //将文章内容读取到file_in中,即获得输入流
  7.     tmp_list = []    //将每个文章的每一段内容都放在数组tmp_list中
  8.     for line in file_in: //一行一行地读取
  9.         tmp_list.append(line.strip())
  10. print '\t'.join([file_name, ' '.join(tmp_list)])  //文件名和文件内容按照tab符号分割,每个文章内部的每一段按照空格连接起来,最后会只形成一段。
  1. [root@master 5_codes]# python convert.py /usr/local/src/code/5_codes/input_tfidf_dir/ > convert.data #将内容输出到一个文件中
  2. [root@hadoop-senior01 5_codes]# head -1 convert.data //可以内容,验证结果

这个时候,即将所有文章整合到一个convert.data文件中,每一段都代表一篇文章的词,且词不重复。

2)map.py

通过conver.py,获取到了所有文章的词汇,接下就需要将所有的词取出来,并且存储到一个大的set集合中,计算拥有该词的文章数。为此,我们将通过map和reduce两个步骤分别进行,目的是为了使程序能够通过hadoop的MapReduce进行分布式运算(当语料库非常大的时候,这是非常有必要的,如果仅仅是为了实践如何计算TF-IDF,也可以将这两步合并成一步,通过一台电脑进行计算)。

  1. import sys
  2. for line in sys.stdin:   //map是通过标准输入读到数据,将convert.data内容读进去
  3.     ss = line.strip().split('\t') //ss为每篇文章的名称和属于这篇文章的所有词
  4.     file_name = ss[0].strip()
  5.     file_context = ss[1].strip()
  6.     word_list = file_context.split(' ') //将文本内容按照空格分割
  7.     word_set = set()
  8.     for word in word_list: #这步是为了去重
  9.         word_set.add(word)
  10.     for word in word_set:
  11.         print '\t'.join([word, '1']) //这里输出的是每个文章的不同的字的,只统计是否有,为了给red中的计算做准备
[root@master 5_codes]# cat convert.data | python map.py >map.data

3)red.py

经过map后,再通过reduce计算词的文章数。这里需要注意的是,将map.data的数据输入到red.py前,需要先进行排序,在hadoop的MapReduce中,这个步骤将会自动完成,但是在使用MapReduce前,我们本地验证时候将通过sort命令进行排序。

  1. import sys
  2. import math
  3. current_word = None
  4. doc_cnt = 508 //文章总篇数
  5. sum = 0
  6. for line in sys.stdin:
  7. ss = line.strip().split('\t')
  8. if len(ss)!=2: //判断格式是否是正确的
  9. continue
  10. word,val = ss
  11. if current_word == None:
  12. current_word = word
  13. if current_word != word: //如果读进来的单词和之前的不一致,说明之前的已经读完,可以开始计算idf值
  14. idf_score = math.log(float(doc_cnt)/(float(sum+1)))
  15. print '\t'.join([current_word,str(idf_score)])
  16. current_word = word
  17. sum = 0
  18. sum = sum+1
  19. //这里要计算最后一个词的idf词
  20. idf_score = math.log(float(doc_cnt)/(float(sum+1)))
  21. print '\t'.join([current_word,str(idf_score)])
  1. [root@hadoop-senior01 5_codes]# cat map.data | sort -k1 | python red.py > myred.tmp
  2. [root@hadoop-senior01 5_codes]# cat myred.tmp | sort -k2 -nr > result.data 按照分值,从大到小排序

2.计算TF

1)mp_tf.py

  1. import sys
  2. word_dict = {}
  3. idf_dict = {}
  4. def read_idf_func(idf): #读取idf值文件的函数
  5. with open(idf,'r') as fd:
  6. for line in fd:
  7. kv=line.strip().split('\t')
  8. idf_dict[kv[0].strip()] =float(kv[1].strip())
  9. return idf_dict
  10. def mapper_func(idf):
  11. idf_dict = read_idf_func(idf)
  12. for line in sys.stdin:
  13. ss = line.strip().split('\t')
  14. fn = ss[0].strip()
  15. fc = ss[1].strip()
  16. word_list = fc.split(' ')
  17. cur_word_num = len(word_list)
  18. for word in word_list:
  19. if word not in word_dict:
  20. word_dict[word]=1
  21. else:
  22. word_dict[word]+=1
  23. for k,v in word_dict.items():
  24. if k!='':#判断key是否为空格
  25. print fn, k, float(v/float(cur_word_num)*idf_dict[k])
  26. if __name__ == "__main__": #函数模块化,
  27.     module = sys.modules[__name__]
  28.     func = getattr(module, sys.argv[1])
  29.     args = None
  30.     if len(sys.argv) > 1:
  31.         args = sys.argv[2:]
  32. func(*args)
[root@master 5_codes]# cat convert.data | python mp_tf.py mapper_func result.data

这里需要注意,在上面的代码中,用 if k!='':对key进行了判断,如果不进行判断,则会出现如下的错误。

原因是在形成convert.data的时候出了问题,在某个文章中两个单词之间存在两个空格。而计算出的result.data中并不包含空格的idf值,因为在计算这个idf前,通过如下代码将空格过滤掉了。

  1. if len(ss)!=2: //判断格式是否是正确的
  2. continue

解决的办法就是忽略文章中的空格,因此加入了if k!='':,若是空格就忽略掉。

四、LCS

1.概念

最长公共子序列(Longest Common Subsequence),一个序列S任意删除若干个字符得到的新序列T,则T叫做S的子序列。

两个序列X和Y的公共子序列中,长度最长的那个,定义为X和Y的最长公共子序列。

 - 字符串12455245576的最长公共子序列为2455

 - 字符串acdfg与adfc的最长公共子序列为adf

最长公共子串(Longest Common Substring)与最长公共子序列不同的是,最长公共子串要求字符相邻。

2.作用

1)生物学家常利用最长的公共子序列算法进行基因序列比对,以推测序列的结构、功能和演化过程。

2)描述两段文字之间的“相似度”。

辨别抄袭,对一段文字进行修改之后,计算改动前后文字的最长公共子序列,将除此子序列外的部分提取出来,该方法判断修改的部分。

3)可以推荐不同类型的事物,增强用户体验。

3.求解—暴力穷举法

• 假定字符串X,Y的长度分别为m,n;

• X的一个子序列即下标序列{1,2,……,m}严格递增子序列,因此,X共有2的m次方个不同子序列;同理,Y有2的n次方个不同子序列;(每个字符都对应着删除或者不删除,所以可以有如上的不同子序列个数)

穷举搜索法时间复杂度O(2m次方 2n次方);

• 对X的每一个子序列,检查它是否也是Y的子序列,从而确定它是否为X和Y的公共子序列,并且在检查过程中选出最长的公共子序列,也就是说要遍历所有的子序列。

• 复杂度高,不可用!

4.求解—动态规划

• 字符串X,长度为m,从1开始数;

• 字符串Y,长度为n,从1开始数;

• Xi=<x1,……,xi>即X序列的前i个字符(1<=i<=m)(Xi计作“字符串X的i前缀” )

• Yj=<y1,……,yj>即Y序列的前i个字符(1<=j<=n)(Yj计作“字符串Y的j前缀” )

• LCS(X,Y)为字符串X和Y的最长公共子序列,即为Z=<z1,……,zk>

• 如果xm = yn(最后一个字符相同),则:Xm与Yn的最长公共子序列Zk的最后一个字符肯定是xm(=yn),所以zk=xm=yn,因此有LCS(Xm,Yn)= LCS(Xm-1,Yn-1)+xm。

• 如果xm ≠ yn,则LCS(Xm, Yn)=LCS(Xm−1, Yn),或者LCS(Xm, Yn)=LCS(Xm, Yn−1)

• 即LCS(Xm, Yn)=max{LCS(Xm−1, Yn), LCS(Xm, Yn−1)}

使用二维数组C[m,n],C[i,j]记录序列Xi和Yj的最长公共子序列的长度,因此得到C[m,n]的值时,即得到最长公共子序列的长度。当i=0或j=0时,空序列是Xi和Yj的最长公共子序列,故C[i,j]=0。

举例:计算X=<A, B, C, B, D, A, B> 和Y=<B, D, C, A, B, A>的最长公共子串。按照公式逐渐递推到X和Y的首个字母, 接着从两个序列的首个字母开始回溯,最终计算出结果。具体过程如下:

X0=0或Y0=0时,LCS=0,因此第一行和第一列都是0。接下来从(1,1)位置开始,按照从坐到右,上到下的顺序,一行一行地判断。

判断X1=A和Y1=B不一样,所以LCS(X1,Y1)=max{LCS(X0,Y1),LCS(X1,Y0)}=0。

接下来判断(1,2)位置的LCS值,根据公式,由于A和B元素不同,因此调用第3个公式,即取该点左边和上面点的最大值,由于此时最大值都是0,所以(1,2)位置的LCS值为0;同理一直到(1,4),由于A和A相同,因此调用第2个公式,即左上角的LCS值+1,因此可以得到C(1,2)=1。

以此类推,最终就可以得到C(7,6)的值,该值为4,即两个序列的最长公共子序列为4。

5.LCS的Python实现

首先准备一个输入数据,该文件中每行有两句,中间用制表符分隔。

1)map.py

  1. import sys
  2. def cal_lcs_sim(first_str, second_str):
  3.     len_vv = [[0] * 50] * 50         // 50*50的矩阵,保证够大就行
  4.     first_str = unicode(first_str, "utf-8", errors='ignore') //设置支持中文,否则会出现乱码
  5.     second_str = unicode(second_str, "utf-8", errors='ignore')
  6.     len_1 = len(first_str.strip())
  7.     len_2 = len(second_str.strip())
  8. //从左到右,从上到下计算最长公共子串
  9.     for i in range(1, len_1 + 1):
  10.         for j in range(1, len_2 + 1):
  11.             if first_str[i - 1] == second_str[j - 1]: //如果相等,则对角线的值+1,这里i,j的范围从1到len+1,是为了防止在计算[0][0]时,出现越界。
  12.                 len_vv[i][j] = 1 + len_vv[i - 1][j - 1]
  13.             else:
  14.                 len_vv[i][j] = max(len_vv[i - 1][j], len_vv[i][j - 1])
  15.     return float(float(len_vv[len_1][len_2] * 2) / float(len_1 + len_2)) //相似度公式可以自定义
  16. //计算框架的入口,接收输入的文本数据
  17. for line in sys.stdin:
  18.     ss = line.strip().split('\t')
  19.     if len(ss) != 2:
  20.         continue
  21.     first_str = ss[0].strip()
  22.     second_str = ss[1].strip()
  23.     sim_score = cal_lcs_sim(first_str, second_str)
  24. print '\t'.join([first_str, second_str, str(sim_score)])

2)run.sh

  1. HADOOP_CMD="/usr/local/src/hadoop-1.2.1/bin/hadoop"
  2. STREAM_JAR_PATH="/usr/local/src/hadoop-1.2.1/contrib/streaming/hadoop-streaming-1.2.1.jar" #这是hadoop1.0采用的hadoop-streaming的jar包
  3. #HADOOP_CMD="/usr/local/src/hadoop-2.6.1/bin/hadoop"
  4. #STREAM_JAR_PATH="/usr/local/src/hadoop-2.6.1/share/hadoop/tools/lib/hadoop-streaming-2.6.1.jar" #这是hadoop2.0采用的hadoop-streaming的jar包
  5. INPUT_FILE_PATH_1="/lcs_input.data"
  6. OUTPUT_PATH="/lcs_output"
  7. $HADOOP_CMD fs -rmr -skipTrash $OUTPUT_PATH
  8. # Step 1.
  9. $HADOOP_CMD jar $STREAM_JAR_PATH \
  10.     -input $INPUT_FILE_PATH_1 \
  11.     -output $OUTPUT_PATH \
  12.     -mapper "python map.py" \
  13.     -jobconf "mapred.reduce.tasks=0" \
  14.     -jobconf "mapred.job.name=mr_lcs" \
  15.     -file ./map.py

最终在hdfs上可以看到生成了/lcs_output的文件夹,查看内部文件,检查结果。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Li_阴宅/article/detail/941426
推荐阅读
相关标签
  

闽ICP备14008679号