实现向量空间模型内积计算相似度实验报告

实现向量空间模型内积计算相似度实验报告 实现向量空间模型内积计算相似度实验 报告 向量空间模型 向量空间模型(vector space model) 向量空间模型概念简单，把对文本内容的处理简化为向量空间中的向量运算，并且它以空间上的相似度表达语义的相似度，直观易懂。当文档被表示为文档空间的向量，就可以通过计算向量之间的相似性来度量文档间的相似性。文本处理中最常用的相似性度量方式是余弦距离。 VSM基本概念: (1) 文档(Document):泛指一般的文本或者文本中的片断(段落、句 群或句子),一般指一篇文章,尽管文档可以是多媒体对象,但是以下讨论中我们只认为是文本对象,本文对文本与文档不加以区别。 (2) 项(Term):文本的内容特征常常用它所含有的基本语言单位 (字、词、词组或短语等)来表示,这些基本的语言单位被统称为文本的项,即 (来自:www.XIelw.Com 写 论文网:实现向量空间模型内积计算相似度实验报告)文本可以用项集(Term List)表示为 D(T1,T2,,,,Tn)其中是项,1?k?n (3) 项的权重(TermWeight):对于含有n个项的文本D( ,„„„，,项常常被赋予一定的权重 ,,,?,表示他们在)。这时我们文本D中的重要程度,即D=(，说项的权重为(1?k?n)。 (4) 向量空间模型(VSM):给定一文本D=D(,„„„，)由于 在文本中既可以重复出现又应该有先后次序的关系,分析起来有一定困难。为了简化分析,暂时不考虑的顺序,并要求互异, 这时可以把 , „„„，看作是一个n维的坐标, 而 就是n维坐标所对应的值,所以文档D()就可以被看作一个n维的向量了。 (5) 相似度(Similarity)两个文本D,和DZ之间的(内容)相关程度 (Degree of Relevance)常常用他们之 间的相似度Sim(,)来度量,当文本被表示为向量空间模型时,我们可以借助与向量之间的某种距离来表示文本间的相似度常用向量之间的内积进行计算: Sim(,)= * 或者用夹角的余弦值表示: Sim( 可以看出，对向量空间模型来说，有两个基本问题:即特征项的选择和项的权重计算。 特征项选择 用来表示文档内容的项可以是各种类别，对汉语来说，有字、词、,)= 短语，甚至是句子或句群等更高层次的单位。项也可以是相应词或短语的语义概念类。 项的选择必须由处理速度、精度、存储空间等方面的具体要求来决定。特征项选取有几个原则:一是应当选取包含语义信息较多，对文本的表示能力较强的语言单位作为特征项;二是文本在这些特征项上的分布应当有较为明显的统计规律性，这样将适用于信息检索、文档分类等应用系统;三是特征选取过 程应该容易实现，其时间和空间复杂度都不太大。实际应用中常常采用字、词或短语作为特征项。 由于词汇是文本最基本的表示项,在文本中的出现频度较高,呈现一定的统计规律,在考虑到处理大规模真实文本所面临的困难,一般选择词汇或短语作为特征项,但是直接选用文本中的词或词组作为文本特征项也会存在以下问题: (1) 文本中存在一些没有实在意义但使用频率很高的虚词和功能词,如中文中“的”、“把”、“了”等,常常把一些真正有分类作用的实词淹没掉了。解决这个问题的方法是把这些词组织成一个禁用词表,或者进行权重计算时,使它们的权重很低,通过取阀值将它们丢弃。采用禁用词表时,词表的选择很关键,很难全面地包括所有的禁用词,并且语言是不断发展的,禁用词表也是随着训练文本集合的不同而不同,某个词在这里不是禁用词,到另外一类文本中可能就成了禁用词。另一方面考虑到,最能代表一篇文章实际意义的词,往往是那些实词,如形容词、动词、名词,而且同一个词,当处于不同词性时,可能分别属于和不属于禁用词表。例 如:“他高兴地走了”(副词“地”应是禁用词),“地很不平”(名词 “地”不应作为禁用词)针对这个现象,提出了只提取形容词、动词和名词作为特征项,并尝试着取代禁用词表方法. (2) 采用词语作为特征项时还会出现所谓的同义现象,同义现象是指:对于同一个事物不同的人会根据个人的需要、所处的环境、知识水平以及语言习惯有着不同的表达方式,因此所采用的词汇也有很大的不同。所以经常出现两个文本所用的词汇有所不同,但实际上两者是相似的，这就是词的同义现象造成的。例如电脑和计算机是同一个概念,应该属于同一个特征项,目前最常用的解决 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 是采用概念词典来解决这个问题。 分词 确定了特征项单位以后,接下来要做的就是把文本分割成特征项的表示。我们知道,词是最小的能够独立活动的有意义的语言成分。然而,汉语是以字为基本的 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 写单位,文本中词与词之间没有明确的分隔标记,而是连续的汉字串,显而易见,自动识别词边界,将汉字串分为正确的词串的汉语分词问题无疑是实现中文 信息处理各项任务的基础与关键。中文词语分析一般包括3个过程:预处理过程的词语粗切分、切分排歧与未登陆词识别、词性标注。目前中文词语分析采取的主要步骤是:先采取最大匹配、最短路径、概率统计、全切分等方法,得到一个相对最好的粗分结果,然后进行排歧、未登陆词识别,最后标注词性。在实际系统中,这三个过程可能相互交叉、反复融合,也可能不存在明显的先后次序。可以将现在的分词算法分为3大类:基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。 (1)基于字符串匹配的分词方法 这种方法又叫机械分词法,它按照一定的策略将待分析的汉字串与机器字典中的词条进行匹配,若在字典中可以找到某个字符串,则匹配成功(识别出一个词)。按照扫描方向的不同可以分为正向匹配和逆向匹配;按照不同长度优先匹配的情况,又可以分为最大(最长)匹配和最小(最短)匹配;按照是否与词性标注过程相结合,又可分为单纯分词法和分词与标注相结合的一体化方法。具体的方法主要有以下几种:(a)最大匹配法(maximum matching method, MM) 在计算机中存放一个已知的词表,这个词表叫底表,从被切分的语料中,按给定的顺序截取一个定长的字符串,通常为6-8个汉字,这个字符串的长度叫做最大词长,把这个具有最大词长的字符串与底表中的词相匹配,如匹配成功,则可确定这个字符串为词,然后指针向给定的方向移动与已经识别出的词长相应个数的汉字,继续进行匹配,否则,则把该字符串逐次减一,再与底表中的词长进行匹配,直到成功为止。MM的原理简单,易于在计算机上实现,实现复杂度比较低。缺点是最大词长难以确定,如果定得过长,则算法复杂度显著提高,如果定得太短,则不能切分长度大于它的词,导致切分正确率降低。 (b)逆向最大匹配法(reverse maximum matching method, RMM) 这种方法的原理与MM相同,不同的是切词的扫描方向,如果MM的方向是从左到右取字符串进行匹配,则RMM的切词方向就是从右到左取字符串进行匹配。试验证明RMM的切词正确率较MM更高一些。但是,RMM要求配置逆序的切词字典,这 种词典与人们的语言习惯不 篇二:信息检索几种相似度计算方法作对比 几种相似度计算方法作对比 句子相似度的计算在自然语言处理具有很重要的地位,如基于实例的机器翻译(Example Based Ma-chine Translation,EBMT)、自动问答技术、句子模糊匹配等.通过对术语之间的语义相似度计算,能够为术语语义识别[1]、术语聚类[2]、文本聚类[3]、本体自动匹配[4]等多项任务的开展提供重要支持。在已有的术语相似度计算方法中,基于搜索引擎的术语相似度算法以其计算简便、计算性能较高、不受特定领域语料库规模和质量制约等优点而越来越受到重视[1]。 相似度计算方法总述: 1 《向量空间模型信息检索技术讨论》，刘斌，陈桦发表于计算机学报，2007 相似度S(Similarity):指两个文档内容相关程度的大小，当文档以向量来表示时，可以使用向量文档向量间的距离来衡量，一般使用内积或夹角0的余弦来计算，两者夹角越小 说明 关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书 似度越高。由于查询也可以在同一空间里表示为一个查 询向量(见图1)，可以通过相似度计算公式计算出每个档向量与查询向量的相似度，排序这个结果后与设立的阈值进行比较。如果大于阈值则页面与查询相关，保留该页面查询结果;如果小于则不相关，过滤此页。这样就可以控制查询结果的数量，加快查询速度。 2 《相似度计算方法综述》 相似度计算用于衡量对象之间的相似程度，在数据挖掘、自然语言处理中是一个基础性计算。其中的关键技术主要是两个部分，对象的特征表示，特征集合之间的相似关系。在信息检索、网页判重、推荐系统等，都涉及到对象之间或者对象和对象集合的相似性的计算。而针对不同的应用场景，受限于数据规模、时空开销等的限制，相似度计算方法的选择又会有所区别和不同。下面章节会针对不同特点的应用，进行一些常用的相似度计算方法进行介绍。 内积表示法: 1 《基于语义理解的文本相似度算法》，金博，史彦君发表于大连理工大学学报，2007 在中文信息处理中,文本相似度的计 算广泛应用于信息检索、机器翻译、自动问答系统、文本挖掘等领域,是一个非常基础而关键的问题,长期以来一直是人们研究的热点和难点。计算机对于中文的处理相对于对于西文的处理存在更大的难度,集中体现在对文本分词的处理上。分词是中文文本相似度计算的基础和前提,采用高效的分词算法能够极大地提高文本相似度计算结果的准确性。本文在对常用的中文分词算法分析比较的基础上,提出了一种改进的正向最大匹配切分(MM)算法及歧义消除策略,对分词词典的建立方式、分词步骤及歧义字段的处理提出了新的改进方法,提高了分词的完整性和准确性。随后分析比较了现有的文本相似度计算方法,利用基于向量空间模型的TF-IDF方法结合前面提出的分词算法,给出了中文文本分词及相似度计算的计算机系统实现过程,并以科技文本为例进行了测试,对所用方 法进行了验证。这一课题的研究及其成果对于中文信息处理中的多种领域尤其是科技类文本相似度的计算比较,都将具有一定的参考价值和良好的应用前景。 2 《随机内积空间》，林熙，郭铁信发表于科学通报，2007 称(s，盘)为数域K上的以概率空间(口，a，)为基的随机内积空间 (Randominnerproductspace，简RI空间)，若s是数域K上的线性空间且映射盘:×_+L(口，)满足Vpg，?，V?K， (RIP一1):?L(口)且((。)一0as。{P一0(中零元); (RIP一2):M(m)一”(m);as其中x?表x的共轭随机变量。 (RIP一3):xo?(?)一aX?(?);a。s。 (RIP一4):X+。，，()一X，。，(?)+Xf，，(?)。a。s。 若还存在零测集?，使得对所有E口,?上述公理成立，则称0，。劈)为一致随机内积空间。在RIP空间中称x为p与9的随机内积。 余弦响亮度量方法: 1 《基于云计算的余弦向量度量法文本检索模型》，付永贵发表在情报科学，2012 目前信息检索技术在国内外已经取得了很大的究成果，为用户信息检索提 供了很大的便利，具体体现在不同的检索模型的应用，比如布尔模型、扩布尔模型、向量空间模型、概率模型、潜在语义模、统计语言模型等等，在文本信息检索中向量空间型中的余弦向量度量法是应用相对广泛而且效率。 经典的余弦向量度量法文本检索模型 (theclassiccosinevectormeasuringm ethodtextre?trievalmodel)中查询和文本均被看成是由索引项构成的向量，比如对于有n个索引项的文本检索，可以由这n个索引项构成的空间向量来表示查询q和文本dj。则查询q可以表示为:q=(t1q,t2q,?,tnq)，文本dj可以表示为:dj=(s1j,s2j,?,snj)。其中tkq，skj(1?k?n)分别表示查询q和文本dj的第k个索引项。在具体应用中通常用索引项在查询q和文本dj的权值来表示其在查询和文本中的重要程度，则查询q和文本dj可以用索引项权值构成的空间向量来表示，设 q=(w1q,w2q,?,wnq)，wkq(1?k?n)表示索引项tkq(1?k?n)在查询q中的权值，文本dj=(v1j,v2j,?,vnj)，vkj(1?k? n)表示索引项skj(1?k?n)在文本dj中的权值。 2 《基于项目评分预测的协同过滤推荐算法》，邓爱林,朱扬勇,施伯乐发表在软件学报，2012 度量用户间相似性的方法有多种，主要包括如3种方法【:余弦相似性相关相似性及修正的余弦相似性?余弦相似性(cosine):用户评分被看做是n维项目空间上的向量，如果用户对项目没有进行评分，则将用户对该项目的评分设为0，用户间的相似性通过向量间的余弦夹角度量。设用户i和用户-，在n维项目空间上的评分分别表示为向量，歹，则用户i 和用户之间的相似性sim(id) 分子为两个用户评分向量的内积，分母为两个用户向量模的乘积。相关相似性(correlation):设经用户i和用户共同评分的项目集合用表示，则用i和用户，之间的相似性sim(id)通过Pearson相关系数度量:Rf。表示用户i对项目C的评分，R和R，分别表示用户i和用户-，对项目的平均评分。修正的余弦相似性 (adjustedcosine):在余弦相似性度量方法中没有考虑不同用户的评分尺度问题， 修正的余弦相似性度量方法通过减去用户对项目的平均评分来改善上述缺陷，设经用户i和用户共同评分的项目集合用表示和分别表示经用户i和用户J评分的项目集合，则用户i和用户之间的相似性sim(ij)为 Rf。表示用户i对项目c的评分，R和R，分别表示用户i和用户J对项目的平均评分。 JaccardCoefficient: 1 《信息检索-向量空间模型》 此方法看上去很好理解，就是用query和文档共同出现的词的个数，除以一共的词数。当然也有很多问题 1没有考虑文档中词出现的次数(没有考虑tf因素) 2没有考虑文档的频率(没考虑idf因素) 3没有考虑文档的长度，长文档和短文档计算相似度的差别会很大 系数主要用于计算符号度量或布尔值度量的个体间的相似度，因为个体的特征属性都是由符号度量或者布尔值标识，因此无法衡量差异具体值的大小，只能获得“是否相同”这个结果，所以Jaccard系数只关心个体间共同具有的特征是否一致这个问题。如果比较X与Y 的Jaccard相似系数，只比较xn和yn中相同的个数。 信息科学与工程学院 肖艳丽 篇三:文本相似度算法 文本相似度算法 1.信息检索中的重要发明TF-IDF 1.1TF Term frequency即关键词词频，是指一篇文章中关键词出现的频率，比如在一篇M个词的文章中有N个该关键词，则 (公式1.1-1) 为该关键词在这篇文章中的词频。 1.2IDF 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(1800*3000)=0.86066 完毕。 2.3算法实现 开源代码:Text-Similarity-0.08 简介:PERL脚本、自定义去停用词 表、无语义识别功能、不适于中文。 局限:仅适用于英文、无语义相似 判别功能 编译安装: (1)进入代码主目录里的/bin 修改text_similarity.pl 将第一行改为#!/usr/bin/perl (2)退回代码主目录，分别执行 perl Makefile.PL make make test 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.4缺陷 这类算法没有很好地解决文本数据中存在的自然语言问题，即同义词和多义词。这样对于搜索的精度产生很大的影响。 2.5算法变体 图2.5-1算法变体(红) 3.改进算法 3.1隐形语义引标 隐性语义标引(LSI)利用矩阵理论中的“奇异值分解(SVD)”技术，将词频矩阵转化为奇异矩阵:首先从全部的文档集中生成一个文档矩阵，该矩阵的每个分量为整数值，代表某个特定的文档矩阵出现在某个特定文档中次数。然后将该矩阵进行奇异值分解，较小的奇异值被剔除。结果奇异向量以及奇异值矩阵用于将文档向量和查询向量映射到一个子空间中，在该空间中，来自文档 矩阵的语义关系被保留。最后，可以通过 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 化的内积计算来计算向量之间的夹角余弦相似度，进而根据计算结果比较文本间的相似度。LSI引入的唯一变化就是剔除小的奇异值，因为与小的奇异值相关联的特征实际上在计算相似度时并不相关，将它们包括进来将降低相关性判断的精确度。保留下来的特征是那些对文档向量在m维空间中的位置大有影响的特征。剔除小的奇异值将文档特征空间变为文档概念空间。概念向量之问使用内积的夹角余弦相似度计算比原来基于原文本向量的相似度计算更可靠，这也是使用LSI方法的主要原因所在。LSI的缺点在于它的效果依赖于上下文信息，过于稀疏的语料不能很好的体现其潜在的语义。 3.2基于语义相似度的文本相似度算法 用向量空间模型(VSM)来表示文本在该领域内普遍受到认可，是因为其在知识表示方法上的巨大优势。在该模型中，文本内容被形式化为多维空间中的一个点，通过向量的形式给出，把对文本内容的处理简化为向量空间中向量 的运算，使问题的复杂性大为降低。但是它很大的不足之处在于只考虑了词在上下文中的统计特性，假定关键词之间线性无关，而没有考虑词本身的语义信息，因此具有一定的局限性。