文本相似度算法

近期在做关于文本相似度计算的研究，学习到一些计算文本相似度的方法，总结一下，大部分是转载别人的。

1.TF*IDF

（1）TF

Term frequency即关键词词频，是指一篇文章中关键词出现的频率，比如在一篇M个词的文章中有N个该关键词，则

　　　　　　　　　　　　

　为该关键词在这篇文章中的词频。

（2）IDF

Inverse document frequency指逆向文本频率，是用于衡量关键词权重的指数，由公式

 

　　　　　　　　　　　　　　

计算而得，其中D为文章总数，Dw为关键词出现过的文章数。

 

2.基于向量空间模型的余弦相似度计算

 

（1）算法步骤

　　　　预处理→文本特征项选择→加权→生成向量空间模型后计算余弦

（2）步骤简介

1）预处理

　　预处理主要是进行中文分词和去停用词，分词的开源代码有：ICTCLAS。

2）文本特征项选择与加权

　　过滤掉常用副词、助词等频度高的词之后，根据剩下词的频度确定若干关键词。频度计算参照TF公式。

　　加权是针对每个关键词对文本特征的体现效果大小不同而设置的机制，权值计算参照IDF公式。

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）常用向量之间夹角的余弦值表示，公式为：

 

　　　　　　　　　　　　　　　　　　

 下面是一个用余弦相似度计算两篇给定英文文档相似度的代码实现(python):

# -*- coding:gb2312 -*-
# -*- coding:utf-8 -*-
import re
from nltk.stem.porter import PorterStemmer
from numpy import zeros,dot
from numpy.linalg import norm
from nltk.corpus import *
from nltk.corpus import PlaintextCorpusReader

__all__=['compare']

corpus_root1 = 'f:/test'
stopwordlists = PlaintextCorpusReader(corpus_root1,'.*')
stopWords = stopwordlists.words('english_stopwords.tsv')

splitter=re.compile ( "[a-z\-']+", re.I )

def add_word(word,d):
    """
            将两篇文档中的词放入一个字典中（无重复），构成一个词汇字典
    """
    w=word.lower() 
    if w not in stopWords:
        ws=PorterStemmer().stem_word(w,0,len(w)-1)
        d.setdefault(ws,0)
        d[ws] += 1

def doc_vec(doc,key_idx):
    v=zeros(len(key_idx))
    for word in splitter.findall(doc):
        keydata=key_idx.get(PorterStemmer().stem_word(word,0,len(word)-1).lower(), None)
        if keydata:
             v[keydata[0]] = 1
    return v

def compare(doc1,doc2):
    '''
            将两篇文档的单词都放入一个字典中
    '''
    all_words=dict()

    for dat in [doc1,doc2]:
        [add_word(w,all_words) for w in splitter.findall(dat)]
 
        # 建立一个索引，知道单词所在的位置和出现的次数key_idx = {'a':(0,5),}
        key_idx=dict() # key-> ( position, count )
        keys=all_words.keys()
        keys.sort()
        
    for i in range(len(keys)):
        key_idx[keys[i]] = (i,all_words[keys[i]])
    del keys
    del all_words

    v1=doc_vec(doc1,key_idx)
    v2=doc_vec(doc2,key_idx)
    #return float(dot(v1,v2) / (norm(v1) * norm(v2)))    #这是余弦相似度
    return float(dot(v1, v2) / (norm(v1)+norm(v2)-dot(v1,v2))) #广义Jaccard相似度
 
 
if __name__ == '__main__':
    print "正在计算..." 
    doc1 = open("one.txt",'r').read()
    doc2=open("two.txt",'r').read()
 
    similarity = compare(doc1,doc2)
     
    print "相似度为： %s" % compare(doc1,doc2)

 

 4)缺陷

　　这类算法没有很好地解决文本数据中存在的自然语言问题，即同义词和多义词。这样对于搜索的精度产生很大的影响。

3.改进算法

（1）潜在语义分析（LSI）　　

　　隐性语义标引（LSI）利用矩阵理论中的“奇异值分解（SVD）”技术，将词频矩阵转化为奇异矩阵：首先从全部的文档集中生成一个文档矩阵，该矩阵的每个分量为整数值，代表某个特定的文档矩阵出现在某个特定文档中次数。然后将该矩阵进行奇异值分解，较小的奇异值被剔除。结果奇异向量以及奇异值矩阵用于将文档向量和查询向量映射到一个子空间中，在该空间中，来自文档矩阵的语义关系被保留。最后，可以通过标准化的内积计算来计算向量之间的夹角余弦相似度，进而根据计算结果比较文本间的相似度。LSI引入的唯一变化就是剔除小的奇异值，因为与小的奇异值相关联的特征实际上在计算相似度时并不相关，将它们包括进来将降低相关性判断的精确度。保留下来的特征是那些对文档向量在m维空间中的位置大有影响的特征。剔除小的奇异值将文档特征空间变为文档概念空间。概念向量之问使用内积的夹角余弦相似度计算比原来基于原文本向量的相似度计算更可靠，这也是使用LSI方法的主要原因所在。LSI的缺点在于它的效果依赖于上下文信息，过于稀疏的语料不能很好的体现其潜在的语义。

（2）基于语义相似度的文本相似度算法

　　用向量空间模型（VSM）来表示文本在该领域内普遍受到认可，是因为其在知识表示方法上的巨大优势。在该模型中，文本内容被形式化为多维空间中的一个点，通过向量的形式给出，把对文本内容的处理简化为向量空间中向量的运算，使问题的复杂性大为降低。但是它很大的不足之处在于只考虑了词在上下文中的统计特性，假定关键词之间线性无关，而没有考虑词本身的语义信息，因此具有一定的局限性。

 　　其中，语义相关度计算获得相似度矩阵的方向有两个：基于知网HowNet或者基于WordNet。