赞
踩
相似度度量指的是计算个体间相似程度,一般使用距离来度量,相似度值越小,距离越大,相似度值越大,距离越小。在说明文本相似度概念和计算方式之前,先回顾下余弦相似度。
衡量文本相似度最常用的方法是使用余弦相似度。
– 空间中,两个向量夹角的余弦值作为衡量两个个体之间差异的大小
– 余弦值接近1,夹角趋于0,表明两个向量越相似
– 余弦值接近0,夹角趋于90,表明两个向量越不相似
度量两篇文文章的相似度流程如下:
思路: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(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)。
IDF的思想是:在词频的基础上,赋予每个词权重,进一步体现该词的重要性。最常见的词(“的”、“是”、“在”)给予最小的权重,较常见的词(“国内”、“中国”、“报道”)给予较小的权重,较少见的词(“养殖”、“维基”)给与较大的权重。
计算公式:
IDF = log(词料库的文档总数/包含该词的文档数+1)
TF-IDF与一个词在文档中的出现次数成正比,与包含该词的文档数成反比。值越大就代表这个词越关键。
使用TF-IDF算法,可以找出两篇文章的关键词;可以设置一个阀值,超过该值的认定为关键词,或者取值排名靠前的n个词作为关键词。
每篇文章各取出若干个关键词(比如20个),合并成一个集合,计算每篇文章对于这个集合中的词的词频(为了避免文章长度的差异,可以使用相对词频,即除以对应文章的总词数,相当于对词频进行了标准化处理)。
生成两篇文章各自的词频向量,计算两个向量的余弦相似度,值越大就表示越相似。
文章的信息都包含在句子中,有些句子包含的信息多,有些句子包含的信息少。"自动摘要"就是要找出包含信息最多的句子。句子的信息量用"关键词"来衡量。如果包含的关键词越多,就说明这个句子越重要。
只要关键词之间的距离小于“门槛值”,就认为处于同一个簇之中,如果两个关键词距离有5个词以上(值可调整),就把这两个关键词分在两个不同的簇中。
对于每个簇,计算它的重要性分值。
例如:其中的某簇一共有7个词,其中4个是关键词。因此,它的重要性分值等于 ( 4 x 4 ) / 7 =2.3
简化做法:不再区分"簇",只考虑句子包含的关键词。
下面使用Python计算TF-IDF,前提是有一个预料库。这里总共有508篇文章,每篇文章中,都已经提前做好了分词。
思路:将语料库中的每篇文章放入各自的set集合中,再设定一个大的set,将之前各篇文章的set集合依次放入这个大的set中,得到的即每个词以及词出现的次数,词对应的次数即拥有该词的文章数。
- import os
- import sys
-
- files_dir = sys.argv[1] //获得输入的参数,即语料库路径
-
- for file_name in os.listdir(files_dir): //函数会返回目录下面的所有文件名称
- file_path = files_dir + file_name
- file_in = open(file_path, 'r') //将文章内容读取到file_in中,即获得输入流
- tmp_list = [] //将每个文章的每一段内容都放在数组tmp_list中
- for line in file_in: //一行一行地读取
- tmp_list.append(line.strip())
- print '\t'.join([file_name, ' '.join(tmp_list)]) //文件名和文件内容按照tab符号分割,每个文章内部的每一段按照空格连接起来,最后会只形成一段。
- [root@master 5_codes]# python convert.py /usr/local/src/code/5_codes/input_tfidf_dir/ > convert.data #将内容输出到一个文件中
- [root@hadoop-senior01 5_codes]# head -1 convert.data //可以内容,验证结果
这个时候,即将所有文章整合到一个convert.data文件中,每一段都代表一篇文章的词,且词不重复。
通过conver.py,获取到了所有文章的词汇,接下就需要将所有的词取出来,并且存储到一个大的set集合中,计算拥有该词的文章数。为此,我们将通过map和reduce两个步骤分别进行,目的是为了使程序能够通过hadoop的MapReduce进行分布式运算(当语料库非常大的时候,这是非常有必要的,如果仅仅是为了实践如何计算TF-IDF,也可以将这两步合并成一步,通过一台电脑进行计算)。
- import sys
-
- for line in sys.stdin: //map是通过标准输入读到数据,将convert.data内容读进去
- ss = line.strip().split('\t') //ss为每篇文章的名称和属于这篇文章的所有词
- file_name = ss[0].strip()
- file_context = ss[1].strip()
- word_list = file_context.split(' ') //将文本内容按照空格分割
- word_set = set()
- for word in word_list: #这步是为了去重
- word_set.add(word)
- for word in word_set:
- print '\t'.join([word, '1']) //这里输出的是每个文章的不同的字的,只统计是否有,为了给red中的计算做准备
[root@master 5_codes]# cat convert.data | python map.py >map.data
经过map后,再通过reduce计算词的文章数。这里需要注意的是,将map.data的数据输入到red.py前,需要先进行排序,在hadoop的MapReduce中,这个步骤将会自动完成,但是在使用MapReduce前,我们本地验证时候将通过sort命令进行排序。
- import sys
- import math
-
- current_word = None
- doc_cnt = 508 //文章总篇数
- sum = 0
-
- for line in sys.stdin:
- ss = line.strip().split('\t')
- if len(ss)!=2: //判断格式是否是正确的
- continue
- word,val = ss
- if current_word == None:
- current_word = word
- if current_word != word: //如果读进来的单词和之前的不一致,说明之前的已经读完,可以开始计算idf值
- idf_score = math.log(float(doc_cnt)/(float(sum+1)))
- print '\t'.join([current_word,str(idf_score)])
- current_word = word
- sum = 0
- sum = sum+1
- //这里要计算最后一个词的idf词
- idf_score = math.log(float(doc_cnt)/(float(sum+1)))
- print '\t'.join([current_word,str(idf_score)])
- [root@hadoop-senior01 5_codes]# cat map.data | sort -k1 | python red.py > myred.tmp
- [root@hadoop-senior01 5_codes]# cat myred.tmp | sort -k2 -nr > result.data 按照分值,从大到小排序
- import sys
- word_dict = {}
- idf_dict = {}
- def read_idf_func(idf): #读取idf值文件的函数
- with open(idf,'r') as fd:
- for line in fd:
- kv=line.strip().split('\t')
- idf_dict[kv[0].strip()] =float(kv[1].strip())
- return idf_dict
- def mapper_func(idf):
- idf_dict = read_idf_func(idf)
- for line in sys.stdin:
- ss = line.strip().split('\t')
- fn = ss[0].strip()
- fc = ss[1].strip()
- word_list = fc.split(' ')
- cur_word_num = len(word_list)
- for word in word_list:
- if word not in word_dict:
- word_dict[word]=1
- else:
- word_dict[word]+=1
- for k,v in word_dict.items():
- if k!='':#判断key是否为空格
- print fn, k, float(v/float(cur_word_num)*idf_dict[k])
-
-
- if __name__ == "__main__": #函数模块化,
- module = sys.modules[__name__]
- func = getattr(module, sys.argv[1])
- args = None
- if len(sys.argv) > 1:
- args = sys.argv[2:]
- 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前,通过如下代码将空格过滤掉了。
- if len(ss)!=2: //判断格式是否是正确的
- continue
解决的办法就是忽略文章中的空格,因此加入了if k!='':,若是空格就忽略掉。
最长公共子序列(Longest Common Subsequence),一个序列S任意删除若干个字符得到的新序列T,则T叫做S的子序列。
两个序列X和Y的公共子序列中,长度最长的那个,定义为X和Y的最长公共子序列。
- 字符串12455与245576的最长公共子序列为2455
- 字符串acdfg与adfc的最长公共子序列为adf
最长公共子串(Longest Common Substring)与最长公共子序列不同的是,最长公共子串要求字符相邻。
1)生物学家常利用最长的公共子序列算法进行基因序列比对,以推测序列的结构、功能和演化过程。
2)描述两段文字之间的“相似度”。
辨别抄袭,对一段文字进行修改之后,计算改动前后文字的最长公共子序列,将除此子序列外的部分提取出来,该方法判断修改的部分。
3)可以推荐不同类型的事物,增强用户体验。
• 假定字符串X,Y的长度分别为m,n;
• X的一个子序列即下标序列{1,2,……,m}严格递增子序列,因此,X共有2的m次方个不同子序列;同理,Y有2的n次方个不同子序列;(每个字符都对应着删除或者不删除,所以可以有如上的不同子序列个数)
• 穷举搜索法时间复杂度O(2的m次方 ∗ 2的n次方);
• 对X的每一个子序列,检查它是否也是Y的子序列,从而确定它是否为X和Y的公共子序列,并且在检查过程中选出最长的公共子序列,也就是说要遍历所有的子序列。
• 复杂度高,不可用!
• 字符串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。
首先准备一个输入数据,该文件中每行有两句,中间用制表符分隔。
- import sys
-
- def cal_lcs_sim(first_str, second_str):
- len_vv = [[0] * 50] * 50 // 50*50的矩阵,保证够大就行
- first_str = unicode(first_str, "utf-8", errors='ignore') //设置支持中文,否则会出现乱码
- second_str = unicode(second_str, "utf-8", errors='ignore')
-
- len_1 = len(first_str.strip())
- len_2 = len(second_str.strip())
- //从左到右,从上到下计算最长公共子串
- for i in range(1, len_1 + 1):
- for j in range(1, len_2 + 1):
- if first_str[i - 1] == second_str[j - 1]: //如果相等,则对角线的值+1,这里i,j的范围从1到len+1,是为了防止在计算[0][0]时,出现越界。
- len_vv[i][j] = 1 + len_vv[i - 1][j - 1]
- else:
- len_vv[i][j] = max(len_vv[i - 1][j], len_vv[i][j - 1])
- return float(float(len_vv[len_1][len_2] * 2) / float(len_1 + len_2)) //相似度公式可以自定义
-
- //计算框架的入口,接收输入的文本数据
- for line in sys.stdin:
- ss = line.strip().split('\t')
- if len(ss) != 2:
- continue
- first_str = ss[0].strip()
- second_str = ss[1].strip()
- sim_score = cal_lcs_sim(first_str, second_str)
- print '\t'.join([first_str, second_str, str(sim_score)])
- HADOOP_CMD="/usr/local/src/hadoop-1.2.1/bin/hadoop"
- STREAM_JAR_PATH="/usr/local/src/hadoop-1.2.1/contrib/streaming/hadoop-streaming-1.2.1.jar" #这是hadoop1.0采用的hadoop-streaming的jar包
- #HADOOP_CMD="/usr/local/src/hadoop-2.6.1/bin/hadoop"
- #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包
-
-
- INPUT_FILE_PATH_1="/lcs_input.data"
- OUTPUT_PATH="/lcs_output"
-
- $HADOOP_CMD fs -rmr -skipTrash $OUTPUT_PATH
-
- # Step 1.
-
- $HADOOP_CMD jar $STREAM_JAR_PATH \
- -input $INPUT_FILE_PATH_1 \
- -output $OUTPUT_PATH \
- -mapper "python map.py" \
- -jobconf "mapred.reduce.tasks=0" \
- -jobconf "mapred.job.name=mr_lcs" \
- -file ./map.py
最终在hdfs上可以看到生成了/lcs_output的文件夹,查看内部文件,检查结果。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。