python code（17）
首先自己建立了一个停用词表，表中有各种符号，没有查询意义的中文词，以及英文词，在语音识别系统运行过程中，始终都维护着一个停用词表，但是在对结巴分词后的词进行过滤的时候出现了编码不一致的情况导致无意义词不能得到有效过滤。后来参考该链接：http://san-/blog/1544123，以及使用python的chardet库的detect方法检测字符的字符集属性，然后使用对应的codecs模块的相关方法1、将停用词文本中的字符转化为utf-8类型，2、将结巴分词的结果（本是unicode类型）也转化为utf-8类型，最终的目的即是将两者的字符集保持一致，这样才会达到过滤的效果。
代码如下：可通过修改注释部分结合相关链接，从而了解代码逻辑。最后如期过滤掉了“逗号，于”等字符
# -*- coding: utf-8 -*-
import jieba
import sys,time
import urllib2
import nltk
import codecs
import chardet
recognitionResult = &小明硕士毕业于中国科学院计算所，后在日本京都大学深造&
look = codecs.lookup(&gbk&)
look2 = codecs.lookup(&utf-8&)
# print &jsu&,chardet.detect(recognitionResult)
def getStopWords(): # 返回停用词list
global look
with codecs.open('stop.txt') as fp:
for ln in fp:
el = ln[:-2]
# print &el1&,type(el),el,[el],chardet.detect(el)
buff.append(el)
# el = look.decode(el)
# el = look.encode(el[0])
# print &el2&,type(el),el[0],el,chardet.detect(el[0])
# buff.append(ln[:-2])
print 'buff',buff
return buff
stopWords = getStopWords()
def getKeyWords(recognitionResult):
global look2
if len(recognitionResult)&3: # 识别结果无效
segList = jieba.cut_for_search(recognitionResult)
# 搜索引擎模式进行切割
# print &原来&, &,&.join(segList)# generator类型，只能用一次
keyWords = []
for el in segList: # 过滤掉无意义的词
# el = look.decode(el)
# print 'el11', type(el), el, chardet.detect(el) # el11 &type 'unicode'& 小明
el = look2.encode(el)[0]
# print 'el22',type(el),el,[el],chardet.detect(el)
# keyWords.append(el)
if el not in stopWords and len(el)&1: #关键词的长度默认大于1
# print 'el33', type(el), el, [el], chardet.detect(el)
keyWords.append(el)
print 'keyWords',keyWords
return keyWords
# getKeyWords(recognitionResult)
for ell in getKeyWords(recognitionResult):
print look2.decode(ell)[0]
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1315次
排名：千里之外
原创：11篇
译文：13篇
(1)(6)(17)(2)2071人阅读
Python（7）
C/C++（61）
在文本处理中，比如商品评论挖掘，有时需要了解每个评论分别和商品的描述之间的相似度，以此衡量评论的客观性。
评论和商品描述的相似度越高，说明评论的用语比较官方，不带太多感情色彩，比较注重描述商品的属性和特性，角度更客观。
那么Python 里面有计算文本相似度的程序包吗，恭喜你，不仅有，而且很好很强大。
这是从52nlp大神的里面发现的，其实具体的处理流程和程序和他的基本一致，只要仔细研读他的这几篇博客文章即可。
（竟然还没提到程序包的名字，退票。。退票。。）
其实题目就讲到了这个包的名字啦：
真心好用，谁用谁知道。。。
接下来主要说一下针对商品评论和商品描述之间的相似度，怎么使用gensim来计算。
1、文本相似度计算的需求始于搜索引擎。
搜索引擎需要计算“用户查询”和爬下来的众多”网页“之间的相似度，从而把最相似的排在最前返回给用户。
2、主要使用的算法是tf-idf
tf：term frequency&词频
idf：inverse document frequency&倒文档频率
主要思想是：如果某个词或短语在一篇文章中出现的频率高，并且在其他文章中很少出现，则认为此词或者短语具有很好的类别区分能力，适合用来分类。
第一步：把每个网页文本分词，成为词包（bag of words）。
第三步：统计网页（文档）总数M。
第三步：统计第一个网页词数N，计算第一个网页第一个词在该网页中出现的次数n，再找出该词在所有文档中出现的次数m。则该词的tf-idf 为：n/N * 1/(m/M) &（还有其它的归一化公式，这里是最基本最直观的公式）
第四步：重复第三步，计算出一个网页所有词的tf-idf 值。
第五步：重复第四步，计算出所有网页每个词的tf-idf 值。
3、处理用户查询
第一步：对用户查询进行分词。
第二步：根据网页库（文档）的数据，计算用户查询中每个词的tf-idf 值。
4、相似度的计算
使用余弦相似度来计算用户查询和每个网页之间的夹角。夹角越小，越相似。
主要分成三步。
第一步，计算所有评论的tf-idf 值。
第二步，使用所有评论的tf-idf 值算出商品描述的tf-idf 值。
第三步，计算每一个评论和商品描述之间的tf-idf 余弦相似度。
① 商品评论的储存形式（把Excel 中的评论数据分词并去停用词存储在txt 文档中）：
txt 文档。每条评论为一行。分词并去除。效果如下图：
② 使用gensim 计算所有评论的tf-idf 值
# 读取txt 文档中的每条评论并用itertools 的yield 方法存储起来（比起把所有数据存在数组中，使用itertools 的内存效率高，具体原理请google）class MyCorpus(object):
def __iter__(self):
for line in open(datapath):
yield line.split()
from gensim import corpora, models, similarities
# 以下是把评论通过gensim 转化为tf-idf 形式，程序具体解释参见52nlp的博客或gensim官方文档
Corp = MyCorpus()
dictionary = corpora.Dictionary(Corp)
corpus = [dictionary.doc2bow(text) for text in Corp] #把所有评论转化为词包（bag of words）
tfidf = models.TfidfModel(corpus) #使用tf-idf 模型得出该评论集的tf-idf 模型
corpus_tfidf = tfidf[corpus]
#此处已经计算得出所有评论的tf-idf 值
① 整个商品描述只有一行，经过分词和去停用词处理，得到与上面相似的txt 文档。只是它只有一行。
② 把商品描述看成是查询，把商品评论看成是网页，即可计算商品描述的tf-idf 值。
#读取商品描述的txt 文档q_file = open(querypath, 'r')
query = q_file.readline()
q_file.close()
vec_bow = dictionary.doc2bow(query.split()) #把商品描述转为词包
vec_tfidf = tfidf[vec_bow]
#直接使用上面得出的tf-idf 模型即可得出商品描述的tf-idf 值
① 计算相似度，然后写入txt 文档中
index = similarities.MatrixSimilarity(corpus_tfidf) #把所有评论做成索引
sims = index[vec_tfidf]
#利用索引计算每一条评论和商品描述之间的相似度
similarity = list(sims)
#把相似度存储成数组，以便写入txt 文档
sim_file = open(storepath, 'w')
for i in similarity:
sim_file.write(str(i)+'\n')
#写入txt 时不要忘了编码
sim_file.close()
② 写入文档后相似度如图：
最后总的程序如下：
#! /usr/bin/env python2.7
#coding=utf-8
import logging
from gensim import corpora, models, similarities
def similarity(datapath, querypath, storepath):
logging.basicConfig(format='%(asctime)s : %(levelname)s : %(message)s', level=logging.INFO)
class MyCorpus(object):
def __iter__(self):
for line in open(datapath):
yield line.split()
Corp = MyCorpus()
dictionary = corpora.Dictionary(Corp)
corpus = [dictionary.doc2bow(text) for text in Corp]
tfidf = models.TfidfModel(corpus)
corpus_tfidf = tfidf[corpus]
q_file = open(querypath, 'r')
query = q_file.readline()
q_file.close()
vec_bow = dictionary.doc2bow(query.split())
vec_tfidf = tfidf[vec_bow]
index = similarities.MatrixSimilarity(corpus_tfidf)
sims = index[vec_tfidf]
similarity = list(sims)
sim_file = open(storepath, 'w')
for i in similarity:
sim_file.write(str(i)+'\n')
sim_file.close()
包计算文本相似度基本也是这个步骤。而且gensim 除了提供了tf-idf 算法之外，还提供了LDA，LSV等更先进的方法。请各位客官慢慢享用。。。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：64208次
积分：1991
积分：1991
排名：第13375名
原创：124篇
转载：94篇
(5)(8)(1)(8)(11)(16)(26)(22)(19)(8)(2)(19)(49)(15)(11)&&国之画&&&& &&&&&&
&& &&&&&&&&&&&&&&&&&&&&
鲁ICP备号-4
打开技术之扣，分享程序人生！对Python中文分词模块结巴分词算法过程的理解和分析
转载原因：52nlp等链接中深入挖掘内容很多，值得一看
结巴分词是国内程序员用python开发的一个中文分词模块, 源码已托管在github, 地址在:&
作者的文档写的不是很全, 只写了怎么用, 有一些细节的文档没有写.
以下是作者说明文件中提到的结巴分词用到的算法:
基于Trie树结构实现高效的词图扫描，生成句子中汉字所有可能成词情况所构成的有向无环图（DAG)
采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合
对于未登录词，采用了基于汉字成词能力的HMM模型，使用了Viterbi算法
因为最近有点兴趣想了解中文分词, 所以看了大量的资料, 对上面的三条有了一点点理解, 不再是两眼一抹黑了.转载请注明: 本文来自Django梦之队,&/blog/archive//69/jieba-fenci-suanfa-lijie/
先推荐大家看& （我爱自然语言处理）的一系列关于概率、中文分词、HMM隐马尔科夫模型的文章， 然后再回头看看结巴分词的代码。
然后推荐大家看看《解密搜索引擎技术实战：Lucene&Java精华版》，如果看不到， 可以看看这里的在线版， 虽然很短， 但是基本的思想都说明白了， 地址：&&(4.6 概率语言模型的分词方法)
看了这本书的第4章， 或者看了那个在线的那个章节的前后部分， 基本上可以说， 结巴分词， 在很大的程度上类似于书中说的例子。（上面的链接，是作者算法的第2条， 动态规划查找最大概率路径），当然， 结巴分词使用了HMM模型对未登录词进行识别（上面的第3条）
至于第1条， 作者的trie树，可以看这篇文章对python中如何保存trie树结构的词典进行深刻理解：& Trie in Python&这篇写的很好，&主要分析 Trie 实现原理，并给出 Python 的实现，还和正则联系到一起了。
上面列出的三个链接, 里面讲到的知识, 基本上将结巴分词的算法都讲到了。所以有兴趣的人， 一定要仔细看我上面给的三个链接。
下面， 结合自己看结巴分词的代码， 讲讲我自己看过资料和代码后的理解。
先从作者的三条说起。
第一条：基于Trie树结构实现高效的词图扫描，生成句子中汉字所有可能成词情况所构成的有向无环图（DAG)
这个看上面的trie树的python实现， 结巴分词自带了一个叫做dict.txt的词典, 里面有2万多条词, 包含了词条出现的次数(这个次数是于作者自己基于人民日报语料等资源训练得出来的)和词性. 这个第一条的trie树结构的词图扫描, 说的就是把这2万多条词语, 放到一个trie树中, 而trie树是有名的前缀树, 也就是说一个词语的前面几个字一样, 就表示他们具有相同的前缀, 就可以使用trie树来存储, 具有查找速度快的优势.
聪明的人可能会想到把 dict.txt中所有的词汇全部删掉, 然后再试试结巴能不能分词, 结果会发现, 结巴依然能够分词, 不过分出来的词, 大部分的长度为2.这个就是第三条, 基于HMM来预测分词了.
接着说DAG有向无环图, 就是后一句的 生成句子中汉字所有可能成词情况所构成的有向无环图, 这个是说的, 给定一个句子, 要你分词, 也就是给定一个 待分词的句子, 对这个句子进行生成有向无环图. 如果对有向无环图理解不了可以百度或者google搜索, 也可以看这篇& 比较形象的用图来表示了一个待分词句子的切分情况.
作者是怎么切分的呢? 1. 根据dict.txt生成trie树, 2, 对待分词句子, 根据dict.txt生成的trie树, 生成DAG, 实际上通俗的说, 就是对待分词句子, 根据给定的词典进行查词典操作, 生成几种可能的句子切分. dag是啥玩意?记录了啥呢? 作者的源码中记录的是句子中某个词的开始位置, 从0到n-1(n为句子的长度), 每个开始位置作为字典的键, value是个list, 其中保存了可能的词语的结束位置(通过查字典得到词, 开始位置+词语的长度得到结束位置)
例如:{0:[1,2,3]} 这样一个简单的DAG, 就是表示0位置开始, 在1,2,3位置都是词, 就是说0~1, 0~2,0~3这三个起始位置之间的字符, 在dict.txt中是词语.
第二条:采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合
关于动态规划查找最大概率路径, 这个在一些大学课程中讲的很多了, 不熟悉的或者忘记了的翻翻百度就行了. 上面给的那个在线书籍的链接中也说的很明白了, 我这里就说说作者的代码:
作者的代码中讲字典在生成trie树的同时, 也把每个词的出现次数转换为了频率. 关于频率和概率, 这里在啰嗦几句: 按照定义, 频率其实也是一个0~1之间的小数, 是 事件出现的次数/实验中的总次数, 因此在试验次数足够大的情况下, 频率约等于概率, 或者说频率的极限就是概率. 不过通常人们混淆的是频率和次数, 经常把频率等同于事件出现的次数, 比如这里就是某个词语出现的次数, 所以, 频率在引起混淆的时候, 对中国人来说, 还是先理解为出现次数, 然后理解发现有问题, 就理解为出现次数/总数这个比率吧.
动态规划中, 先查找待分词句子中已经切分好的词语, 对该词语查找该词语出现的频率(次数/总数), 如果没有该词(既然是基于词典查找, 应该是有的), 就把词典中出现频率最小的那个词语的频率作为该词的频率, 也就是说P(某词语)=FREQ.get('某词语',min_freq), 然后根据动态规划查找最大概率路径的方法, 对句子从右往左反向计算最大概率(一些教科书上可能是从左往右, 这里反向是因为汉语句子的重心经常落在后面, 就是落在右边, 因为通常情况下形容词太多, 后面的才是主干, 因此, 从右往左计算, 正确率要高于从左往右计算, 这个类似于逆向最大匹配), P(NodeN)=1.0, P(NodeN-1)=P(NodeN)*Max(P(倒数第一个词))...依次类推, 最后得到最大概率路径, 得到最大概率的切分组合.
第三条,&对于未登录词，采用了基于汉字成词能力的HMM模型，使用了Viterbi算法
未登录词, 作者说的是什么意思? 其实就是词典 dict.txt 中没有记录的词. 上面说了, 把dict.txt中的所有词语都删除了, 结巴分词一样可以分词, 就是说的这个.
怎么做到的? 这个就基于作者采用的HMM模型了, 中文词汇按照BEMS四个状态来标记, B是开始begin位置, E是end, 是结束位置, M是middle, 是中间位置, S是singgle, 单独成词的位置, 没有前, 也没有后. 也就是说, 他采用了状态为(B,E,M,S)这四种状态来标记中文词语, 比如北京可以标注为 BE, 即 北/B 京/E, 表示北是开始位置, 京是结束位置, 中华民族可以标注为BMME, 就是开始, 中间, 中间, 结束.
经过作者对大量语料的训练, 得到了finalseg目录下的三个文件(来自结巴项目的issues):
要统计的主要有三个概率表：
prob_trans.py
1)位置转换概率，即B（开头）,M（中间),E(结尾),S(独立成词）四种状态的转移概率；
{'B': {'E': 0.1658, 'M': 0.83422},
'E': {'B': 0.4425, 'S': 0.55755},
'M': {'E': 0.6911, 'M': 0.3088},
'S': {'B': 0.94563, 'S': 0.0544}}
P(E|B) = 0.851, P(M|B) = 0.149，说明当我们处于一个词的开头时，下一个字是结尾的概率
要远高于下一个字是中间字的概率，符合我们的直觉，因为二个字的词比多个字的词更常见。
prob_emit.py
2）位置到单字的发射概率，比如P(&和&|M)表示一个词的中间出现”和&这个字的概率；
prob_start.py
3) 词语以某种状态开头的概率，其实只有两种，要么是B，要么是S。这个就是起始向量, 就是HMM系统的最初模型状态
实际上, BEMS之间的转换有点类似于2元模型, 就是2个词之间的转移 二元模型考虑一个单词后出现另外一个单词的概率，是N元模型中的一种。 例如：一般来说，&中国&之后出现&北京&的概率大于&中国&之后出现&北海&的概率，也就是：中国北京 比 中国北海出现的概率大些, 更有可能是一个中文词语.
不过, 作者这里应该不是用的2元分词模型的, 这里的BEMS只提供了单个汉字之间的转换, 发射概率, 并没有提供粒度更大的, 基于词语的发射和转移概率, 当然, 也有可能我理解的不够深入.
给定一个 待分词的句子, 就是观察序列, 对HMM(BEMS)四种状态的模型来说, 就是为了找到一个最佳的BEMS序列, 这个就需要使用viterbi算法来得到这个最佳的隐藏状态序列, 具体的python版的viterbi算法请看维基百科:http://zh.wikipedia.org/wiki/%E7%BB%B4%E7%89%B9%E6%AF%94%E7%AE%97%E6%B3%95&维特比算法
通过作者之前训练得到的概率表和viterbi算法, 就可以得到一个概率最大的BEMS序列, 按照B打头, E结尾的方式, 对待分词的句子重新组合, 就得到了分词结果. 比如 对待分词的句子 '全世界都在学中国话' 得到一个BEMS序列 [S,B,E,S,S,S,B,E,S] 这个序列只是举例, 不一定正确, 通过把连续的BE凑合到一起得到一个词, 单独的S放单, 就得到一个分词结果了: 上面的BE位置和句子中单个汉字的位置一一对应, 得到全/S 世界/BE &都/S 在/S 学/S 中国/BE 话/S 从而将句子切分为词语.&
以上, 就是作者这三条介绍的全部理解和分析, 对于其中任何术语不理解, 请使用搜索引擎.
结巴分词的过程:
1. 加载字典, 生成trie树
2. 给定待分词的句子, 使用正则获取连续的 中文字符和英文字符, 切分成 短语列表, 对每个短语使用DAG(查字典)和动态规划, 得到最大概率路径, 对DAG中那些没有在字典中查到的字, 组合成一个新的片段短语, 使用HMM模型进行分词, 也就是作者说的识别新词, 即识别字典外的新词.
3. 使用python的yield 语法生成一个词语生成器, 逐词语返回. 当然, 我认为直接返回list, 效果也差不到哪里去.
另外谈谈结巴分词的不足和局限:
1 在中文分词的时候, 字典起到的作用貌似不大, 因为基于单字的HMM(BEMS)模型貌似就可以分词了, 不管正确率如何, 总算能分了.字典起到的作用在后面说.说作用不大, 是因为没有字典也能分词. 另外, 生成了DAG之后, 又用动态规划, 觉得浪费步骤.小概率连乘下限可能溢出已修正, 就不多说了.
2. 中文分词加载dict.txt这个字典后, 占用的内存为140多M, 觉得占用内存过多. 专业化的词典生成, 还不方便. 怎么训练自己的专用概率表, 就没有提供工具, 如果提供了训练自己的HMM模型工具, 估计更好.
3. 没有那个字典的话, Trie和DAG都不起作用, 仅靠HMM模型的viterbi算法起作用, 因此看出词典的作用就是用来矫正HMM模型的分词结果, 但是HMM分词的结果生成方式是把B开始E结束的序列, 组合成一个词, 因此, 这种判断方法不一定正确, 比如BES能不能算作一个词的序列我觉得值得考虑.
4. HMM是不是真的能够识别新词呢? 我认为是肯定的, 但是是要打折扣的. 这个跟作者训练的词库有关系, 新词的字出现的概率在一段时间内会井喷, 但在长期的语言现象中, 应该还是平稳的, 除非这个词从一出现就很流行, 而且会流行很长的时间.因此HMM识别新词的功能在时效性上是不足的, 他只能识别2个字的词, 对于3个字的新词, 估计就能力有限了. 这个有待于BEMS序列组合成词的算法的改变和新词获取算法的改变, 才能得到改善.
5. 引入二元分词的判断, 可能对词典的依赖会降低一点, 现在的词典的使用就是为了弥补HMM在识别多字词方面能力欠佳的问题, 所以词典中保存的是3 ,4 个字的词语.
6. 词性标注的问题, 在分词的时候, 不能同时识别词性, 因为分词的时候没有处理词性, 也就是说分词的时候, 没有语义分析的.词性标注的部分, 是使用另外的posseg模块进行的.还有一个问题是新词的词性可能没法识别, 同样这个是说那些3, 4字词.
7. 对专有名词比如人名 地名 机构名 的识别, 不能说好.
8. 文档太少了, 关于词性标注, 得到的结果没有一点分析, 词性来源于哪里都没有说明. 不利于大家一起改进.句法分析, 语义分析都是没有的.
9. 词性标注应该也是基于BEMS标注进行的. 不知道是不是可以独立出来.就是说基于语义来标示词性或者基于词语在句子中的位置来做推断进行标注词性.
10. 分词过程中, 不能获得这个句子中出现的词的次数信息, 或者说出现频率高的词, 不能用于抽取文章的关键词. 第12次修改, 全文完, 欢迎拍砖.转载请注明来自Django梦之队,&/blog/archive//69/jieba-fenci-suanfa-lijie/
本分类共有文章11篇,更多信息详见
& 2012 - 2016 &
&All Rights Reserved. &
/*爱悠闲图+*/
var cpro_id = "u1888441";
/*爱悠闲底部960*75*/
var cpro_id = "u1888128";文本相似度算法
1.信息检索中的重要发明TF-IDF
Term frequency即关键词词频，是指一篇文章中关键词出现的频率，比如在一篇M个词的文章中有N个该关键词，则
（公式1.1-1）
为该关键词在这篇文章中的词频。
Inverse document frequency指逆向文本频率，是用于衡量关键词权重的指数，由公式
（公式1.2-1）
计算而得，其中D为文章总数，Dw为关键词出现过的文章数。
2.基于空间向量的余弦算法
2.1算法步骤
预处理&文本特征项选择&加权&生成向量空间模型后计算余弦。
2.2步骤简介
2.2.1预处理
预处理主要是进行中文分词和去停用词，分词的开源代码有：ICTCLAS。
然后按照停用词表中的词语将语料中对文本内容识别意义不大但出现频率很高的词、符号、标点及乱码等去掉。如&这，的，和，会，为&等词几乎出现在任何一篇中文文本中，但是它们对这个文本所表达的意思几乎没有任何贡献。使用停用词列表来剔除停用词的过程很简单，就是一个查询过程：对每一个词条，看其是否位于停用词列表中，如果是则将其从词条串中删除。
图2.2.1-1中文文本相似度算法预处理流程
2.2.2文本特征项选择与加权
过滤掉常用副词、助词等频度高的词之后，根据剩下词的频度确定若干关键词。频度计算参照TF公式。
加权是针对每个关键词对文本特征的体现效果大小不同而设置的机制，权值计算参照IDF公式。
2.2.3向量空间模型VSM及余弦计算
向量空间模型的基本思想是把文档简化为以特征项（关键词）的权重为分量的N维向量表示。
这个模型假设词与词间不相关（这个前提造成这个模型无法进行语义相关的判断，向量空间模型的缺点在于关键词之间的线性无关的假说前提），用向量来表示文本，从而简化了文本中的关键词之间的复杂关系，文档用十分简单的向量表示，使得模型具备了可计算性。
在向量空间模型中，文本泛指各种机器可读的记录。
用D（Document）表示文本，特征项（Term，用t表示）指出现在文档D中且能够代表该文档内容的基本语言单位，主要是由词或者短语构成，文本可以用特征项集表示为D（T1，T2，&，Tn），其中Tk是特征项，要求满足1&=k&=N。
下面是向量空间模型（特指权值向量空间）的解释。
假设一篇文档中有a、b、c、d四个特征项，那么这篇文档就可以表示为
D（a，b，c，d）
对于其它要与之比较的文本，也将遵从这个特征项顺序。对含有n个特征项的文本而言，通常会给每个特征项赋予一定的权重表示其重要程度，即
D＝D（T1，W1；T2，W2；&，Tn，Wn）
D＝D（W1，W2，&，Wn）
我们把它叫做文本D的权值向量表示，其中Wk是Tk的权重，1&=k&=N。
在上面那个例子中，假设a、b、c、d的权重分别为30，20，20，10，那么该文本的向量表示为
D（30，20，20，10）
在向量空间模型中，两个文本D1和D2之间的内容相关度Sim（D1，D2）常用向量之间夹角的余弦值表示，公式为：
其中，W1k、W2k分别表示文本D1和D2第K个特征项的权值，1&=k&=N。
下面是利用模型进行余弦计算的示例。
在自动归类中，我们可以利用类似的方法来计算待归类文档和某类目的相关度。
假设文本D1的特征项为a，b，c，d，权值分别为30，20，20，10，类目C1的特征项为a，c，d，e，权值分别为40，30，20，10，则D1的向量表示为
D1（30，20，20，10，0）
C1的向量表示为
C1（40，0，30，20，10）
则根据上式计算出来的文本D1与类目C1相关度是0.86。
那么0.86具体是怎么推导出来的呢？
在数学当中，n维向量是
V{v1，v2，v3，...，vn}
|v|=sqrt（v1*v1+v2*v2+&+vn*vn）
两个向量的点积
m*n=n1*m1+n2*m2+......+nn*mn
sim＝（m*n）/（|m|*|n|）
它的物理意义就是两个向量的空间夹角的余弦数值。
下面是代入公式的过程：
d1*c1=30*40+20*0+20*30+10*20+0*10=2000
|d1|=sqrt（30*30+20*20+20*20+10*10+0*0）=sqrt（1800）
|c1|=sqrt（40*40+0*0+30*30+20*20+10*10）=sqrt（3000）
sim=d1*c1/（|d1|*|c1|）=2000/sqrt（）=0.86066
2.3算法实现
开源代码：Text-Similarity-0.08
简介：PERL脚本、自定义去停用词表、无语义识别功能、不适于中文。
局限：仅适用于英文、无语义相似判别功能
编译安装：
（1）进入代码主目录里的/bin
修改text_similarity.pl
将第一行改为#!/usr/bin/perl
（2）退回代码主目录，分别执行
perl Makefile.PL
make install
（3）重新进入主目录/bin进行测试
图2.3-1代码效果
可以看见语句&.......this is one&与&????this is two&的匹配度是0.66；
&.......this is one&与&.......this is two&的匹配度仍然是0.66；
&.......this is one&与&&&.this is one&的匹配度是1；
&.......this is one&与&..（）（）this is one&的匹配度是1。
说明匹配的算法去停用字功能存在。
这类算法没有很好地解决文本数据中存在的自然语言问题，即同义词和多义词。这样对于搜索的精度产生很大的影响。
2.5算法变体
图2.5-1算法变体（红）
3.改进算法
3.1隐形语义引标
隐性语义标引（LSI）利用矩阵理论中的&奇异值分解（SVD）&技术，将词频矩阵转化为奇异矩阵：首先从全部的文档集中生成一个文档矩阵，该矩阵的每个分量为整数值，代表某个特定的文档矩阵出现在某个特定文档中次数。然后将该矩阵进行奇异值分解，较小的奇异值被剔除。结果奇异向量以及奇异值矩阵用于将文档向量和查询向量映射到一个子空间中，在该空间中，来自文档矩阵的语义关系被保留。最后，可以通过标准化的内积计算来计算向量之间的夹角余弦相似度，进而根据计算结果比较文本间的相似度。LSI引入的唯一变化就是剔除小的奇异值，因为与小的奇异值相关联的特征实际上在计算相似度时并不相关，将它们包括进来将降低相关性判断的精确度。保留下来的特征是那些对文档向量在m维空间中的位置大有影响的特征。剔除小的奇异值将文档特征空间变为文档概念空间。概念向量之问使用内积的夹角余弦相似度计算比原来基于原文本向量的相似度计算更可靠，这也是使用LSI方法的主要原因所在。LSI的缺点在于它的效果依赖于上下文信息，过于稀疏的语料不能很好的体现其潜在的语义。
3.2基于语义相似度的文本相似度算法
用向量空间模型（VSM）来表示文本在该领域内普遍受到认可，是因为其在知识表示方法上的巨大优势。在该模型中，文本内容被形式化为多维空间中的一个点，通过向量的形式给出，把对文本内容的处理简化为向量空间中向量的运算，使问题的复杂性大为降低。但是它很大的不足之处在于只考虑了词在上下文中的统计特性，假定关键词之间线性无关，而没有考虑词本身的语义信息，因此具有一定的局限性。
结合语义相似度计算后的算法流程如下所示：
图3.2-1基于向量空间的语义相似度算法流程图
其中，语义相关度计算获得相似度矩阵的方向有两个：基于知网HowNet或者基于WordNet。
4.其它算法涉及的相似度衡量方式
4.1基于拼音相似度的汉语模糊搜索算法
不同于传统的以关键词匹配为核心的匹配技术，这里提出基于拼音相似度的编辑距离来衡量汉字字符串之间的相似度。
论文提出三种编辑距离：基于汉字的编辑距离、基于拼音的编辑距离，以及基于拼音改良的编辑距离。
4.2最长公共子序列
（1）将两个字符串分别以行和列组成矩阵。
（2）计算每个节点行列字符是否相同，如相同则为1。
（3）通过找出值为1的最长对角线即可得到最长公共子串。
为进一步提升该算法，我们可以将字符相同节点的值加上左上角（d[i-1，j-1]）的值，这样即可获得最大公共子串的长度。如此一来只需以行号和最大值为条件即可截取最大子串。
4.3最小编辑距离算法
（1）狭义编辑距离
设A、B为两个字符串，狭义的编辑距离定义为把A转换成B需要的最少删除（删除A中一个字符）、插入（在A中插入一个字符）和替换（把A中的某个字符替换成另一个字符）的次数，用ED（A，B）来表示。直观来说，两个串互相转换需要经过的步骤越多，差异越大。
1.对两部分文本进行处理，将所有的非文本字符替换为分段标记&#&
2.较长文本作为基准文本，遍历分段之后的短文本，发现长文本包含短文本子句后在长本文中移除，未发现匹配的字句累加长度。
3.比较剩余文本长度与两段文本长度和，其比值为不匹配比率。
衡量文本相似度的几种手段：
（1）最长公共子串（基于词条空间）
（2）最长公共子序列（基于权值空间、词条空间）
（3）最少编辑距离法（基于词条空间）
（4）汉明距离（基于权值空间）
（5）余弦值（基于权值空间）
阅读(...) 评论()