（信息与通信工程专业论文）文本相似性度量中参数相关性与优化配置研究.pdf

l i l li imi lli l li i 1 l i y 1719 4 2 1 r e s e a r c ho np a r a m e t e r sc o r r e l a t i o na n do p t i m i z a t i o ni n t e x ts i m i l a r i t ym e a s u r e m e n t s p e c i a l t y ：一i n f o r m a t i o n a n dc o m m u n i c a t i o n e n g i n e e r i n g m a s t e rd e g r e ec a n d i d a t e ：x i nx u s u p e r v i s o r ：p r o f z u p i n gz h a n g e r v l s o rp r o t z u p m g s c h o o lo fi n f o r m a t i o ns c i e n c e & e n g i n e e r i n g c e n t r a ls o u t hu n i v e r s i t y c h a n g s h ah u n a np r c 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名： 眺垃让月嗲日 学位论文版权使用说明书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：师签名( 例湖 y 一一 咻扭年勘尹 摘要 随着计算机网络及应用技术的飞速发展，i n t e m e t 成为信息存储 和交流的主要渠道，但同时也引发了信息爆炸式增长的灾难，因此数 据挖掘、信息检索和文本分类等信息处理技术应运而生，作为这些信 息处理技术的基础，文本相似性度量技术有着深刻的研究意义和广泛 的应用前景。 本文针对文本相似性度量中的相似度阈值、准确率、召回率、 s h i n g l e 滑动窗口大小、s h i n g l e 权重门限、s h i n g l e 抽取率和文本属性 等参数相互影响、关系复杂的问题，首先以文本相似性度量的实现过 程为线索，对文本数学表示、特征生成、特征选择和相似度计算等关 键技术进行了详细的分析；在此分析基础上实现并比较了两种最具典 型性的文本相似性度量算法：基于特征向量的算法和基于s h i n g l e 的 算法；然后结合s h i n g l i n g 算法的实验，研究了这些参数之间的相关 性，最后提出了s h i n g l e 滑动窗v i 大小、s h i n g l e 权重门限和相似度阈 值等参数可优化配置的建议，分析与设计了相似度阈值等参数可适应 的相似性度量算法。 通过某基金2 0 0 9 年的7 3 7 8 个项目申请书的比对分析，结果表明： 这种相似度阈值等参数可适应的算法不但适用于大规模的文本集合， 而且在短小的文本集合中进行相似性度量也具有很高的实际利用价 值，其准确率和召回率均可高达9 5 以上。 关键词文本相似性度量，算法，邻接词组，参数相关性，召回率 a b s t r a c t w i t ht h e d e v e l o p m e n to fc o m p u t e rn e t w o r ka n d a p p l i c a t i o n t e c h n o l o g i e s ，i n t e m e tb e c o m e st h ep r i m a r yc h a n n e lo fi n f o r m a t i o n m e m o r ) ，a n dc o m m u n i o n ，b u ti ta l s ob r i n g st h ed i s a s t e ro fi n f o r m a t i o n h i 曲。s p e e di n c r e a s e s oi n f o r m a t i o np r o c e s s i n gt e c h n o l o g i e ss u c ha sd a t a e x c a v a t i o n ，i n f o r m a t i o nr e t r i e v a la n dt e x tc l a s s i f i c a t i o ne m e r g e a st h e 。 一 一一 b a s i so ft h o s el n f o r m a t i o n p r o c e s s i n gt e c h n o l o g i e s ，t e x ts i m i l a r i t y m e a s u r e m e n tt e c h n o l o g yh a sd e e p s t u d ys i g n i f i c a n c ea n de x t e n s i v e a p p l i c a t i o np r o s p e c t p a r a m e t e r si nt e x t s i m i l a r i t ym e a s u r e m e n ts u c h a ss i m i l 撕t y t h r e s h o l d ，p r e c i s i o n ，r e c a l lr a t e ，s i z eo fm o v i n gw i n d o w , s h i n g l em e a s u r e c o e 伍c i e n tt h r e s h o l d ，e x t r a c t i v er a t ea n dl e n g t ho ft e x ta r ei n t e r r e l a t e da n d c o m p l i c a t e d n et h e s i sf i r s t l ya n a l y s e sp i v o t a lt e c h n o l o g i e ss u c ha st e x t m a t h e m a t i c a l e x p r e s s i o n ，f e a t u r eg e n e r a t i o n ，f e a m r e p i c k i n g a n d s i m i l a r i t yc a l c u l a t i o na c c o r d i n gt ot h ec l u eo ft e x ts i m i l a r i t ym e a s u r e m e n t i m p l e m e n t a t i o np r o c e s s ；b a s e do nt h i s ，i ti m p l e m e n t sa n dc o m p a r e st w o k i n d so ft h em o s tt y p i c a la l g o r i t h m s ；t h e ni ts t u d i e st h ec o r r e l a t i o no f t h o s ep a r a m e t e r sc o m b i n i n gt h es h i n g l i n ga l g o r i t h m e x p e r i m e n t ；a tl a s ti t p r o p o s e st h ep a r a m e t e r so p t i m i z a t i o ns u g g e s t i o n s ，a n dp r o p o s e sa n d a n a l y z e st h ep a r a m e t e r ss u c ha ss i m i l a r i t yt h r e s h o l da d a p t a b l ea l g o r i t h m f o rt e x ts i m i l a r i t ym e a s u r e m e n t t h ea l g o r i t h mi s a p p l i e d t ot h e s y s t e m o ft e x t s i m i l a r i t y m e a s u r e m e n tf o r t h ef u n dw h i c hh a s7 3 7 8p r o p o s a l si n2 0 0 9 t h er e s u l t s s h o wt h a tt h ea l g o r i t h mh a sh i g hp e r f o r m a n c ei np r a t i c a lu s e ，a n dc a l l m a k ep r e c i s i o na n dr e c a l lr a t ea c h i e v e u pt om o r et h a n9 5 n om a t t e rt h e l e n g t ho ft h et e x ti sl o n go rs h o r t k e yw o r d st e x t s i m i l a r i t ym e a s u r e m e n t ，a l g o r i t h m ，s h i n g l e , p a r a m e t e r sc o r r e l a t i o n ，r e c a l lr a t e 目录 摘要i a b s t r a ( 玎i i 目录i i i 第一章绪论1 1 1 文本研究意义及背景1 1 2 国内外研究现状1 1 3 本文研究内容及组织结构3 第二章文本相似性度量概述4 2 1 文本相似性度量基本概念4 2 1 1 文本相似性度量的作用4 2 1 2 中文文本相似性度量的一般实现过程5 2 1 3 文本相似性度量性能评估6 2 2 中文文本分词8 2 2 1 中文文本盼特点8 2 2 2 中文分词的原则规范8 2 2 3 中文分词方法的分析及比较9 2 3 文本相似性度量关键技术分析12 2 3 1 文本数学表示模型。1 2 2 3 2 文本特征表示18 2 3 3 文本特征选择19 2 3 4 文本特征权重的计算2 2 2 4 文本相似性度量化计算2 5 2 4 1 相同特征数量统计2 5 2 4 2 余弦相似度计算。2 6 2 5 小结2 6 第三章典型文本相似性度量算法的实现及比较分析2 7 3 1 基于特征向量的文本相似性度量算法2 8 3 1 1v s m 文本表示2 8 3 1 2 算法的基本思路2 9 3 1 3 基于v s m 算法描述31 3 2 基于s h i n g l e 的文本相似性度量算法3 2 3 2 1 算法的基本思路3 3 3 2 2 基于滑动窗口机制的s h i n g l e 生成方法3 4 3 2 3 基于s h i n g l e 权重的抽取策略3 5 3 2 4 改进的相似度计算3 6 3 2 5s h i n g l i n g 算法描述3 7 3 3 两种文本相似性度量算法的实验与结果3 8 3 3 1 实验数据来源3 8 3 3 2 实验步骤3 9 3 3 3 实验结果3 9 i i i 两种文本相似性度量算法的比较分析4 3 3 4 1 准确率和召回率比较4 3 3 4 2f m e a s u r e 平衡系数比较4 4 3 4 3 运行效率比较4 5 3 4 4 实际应用比较。4 5 小结z 炻 文本相似性度量中参数相关性的分析4 7 s h i n g l i n g 算法中各参数概述4 7 4 1 1 文本属性。4 7 4 1 2s h i n g l e 滑动窗口大小4 8 4 1 3s h i n g l e 权重门限4 8 4 1 4s h i n g l e 抽取率4 8 4 1 5 相似度阈值4 8 文本集合属性分析4 9 4 2 1 文本内容格式4 9 4 2 2 文本集合中文本篇幅的分布4 9 4 2 3 文本相似特征分析5 0 4 2 4 文本集合空间的扩展性分析5 0 文本属性和滑动窗口大小分析5 1 4 3 1 文本篇幅属性滑动窗口大小5 1 4 3 2 文本相似特征属性滑动窗口大小5 2 4 3 3s h i n g l e 滑动窗口大小准确率分析5 2 s h i n g l e 权重门限分析5 3 4 4 1 文本篇幅属性s h i n g l e 权重门限5 3 4 4 2s h i n g l e 抽取率s h i n g l e 权重门限5 4 4 4 3s h i n g l e 权重门限准确率分析5 4 相似度阈值、准确率和召回率分析5 4 4 5 1 相似度阈值分析5 4 4 5 2 文本篇幅属性相似度阈值准确率5 5 4 5 3 文本篇幅属性相似度阈值召回率5 6 准确率、召回率和f m e a s u r e 平衡系数5 7 4 6 1 准确率召回率分析。5 7 4 6 2f m e a s u r e 平衡系数分析。5 8 爿、结5 9 文本相似性度量中各参数的优化配置6 0 滑动窗口大小的动态性6 0 5 1 1 动态滑动窗口机制6 0 5 1 2 滑动窗口大小动态性的实现6 1 s h i n g l e 权重门限的自反馈6 2 5 2 1s h i n g l e 权重门限的自反馈机理6 2 5 2 2s h i n g l e 权重门限自反馈的实现6 3 5 3 相似度阈值自动适应化6 4 5 3 1 相似度阈值自动适应化原理6 4 5 3 2 相似度阈值自动适应化参数训练6 5 i v 5 4 各参数可优化配置的简单应用6 5 5 4 1 各参数可优化配置的应用框架6 6 5 4 2 相似度阈值等参数可优化配置的算法6 6 5 5 小结6 8 第六章总结与展望6 9 6 1 本文的主要工作6 9 6 2 进一步的工作7 0 参考文献7 1 1 改谢7 6 攻读硕士学位期间参与项目及发表论文7 7 v 硕士学位论文第一章绪论 1 1 文本研究意义及背景 第一章绪论 i n t o r n o t 计算机网络和电子信息技术自上世纪9 0 年代以来飞速发展，计算机 应用已经融入到了人们生活的各个领域，使得人们已经改变了传统的信息存储和 交流方式，取而代之的是存储空间小、传递速度快、持久性强的电子信息存储、 交流方式。小到个人信件、超市记账，大到各企业的经营管理以及教育、政府等 事业单位的事务处理，都使用电子存储、交流信息的方式。高科技给人们带来便 利的同时，也引发了信息爆炸式地增长。i n t o r n o t 成为新闻热点、广告、论文文 献等信息抄袭和仿效的主要渠道之一，因此导致海量文本信息中存在近乎一半的 相似信息。这不仅浪费了大量的存储空间，而且为快捷、准确的检索信息带来了 许多的难题，因此数据挖掘、信息检索等相关信息处理技术应运而生。文本相似 性度量技术是信息处理的基础，简而言之，就是根据文本的内容属性和篇幅属性， 来度量两个电子文档的相似程度，以排除用户认为相似度高的文本信息，为信息 检索提供了更高效的搜索策略和更准确的查询结果，对用户快捷、高效获取信息 起着深刻的实际指导意义 本文研究背景是某些基金权威性机构对项目文本相似性检测的需求，即在每 年以百万计增长的基金申报项目中，要避免一个项目多人申报、一个项目多年重 复申报和窃取他人项目成果等不良现象发生，确保基金项目申报的公平和公正 1 2 国内外研究现状 文本相似性度量技术的研究开始主要面向的是大型文件系统，m a n b o r 在 1 9 9 4 年提出了s i f 算法【，它是基于大型文件系统的相似文档查找技术。该算法 的核心技术就是为每个待比较的文档生成一个指纹，“指纹 本质上就是文本字 符串的哈希值集合，代表了一个文本的内容和属性特征。而当比较两个文本的相 似度的时候，只要提取它们各自的“指纹一，计算出两者相同哈希值的数目，用 户只要设定一个阈值，如果两个文本的相同哈希值的数目超过该阈值，则判定为 相似文本。后来许多研究人士都借鉴m a n b e r 的字符串匹配的基本思想：斯坦福 大学的b r i n 和g a r e i a - m o l i n a 等人在1 9 9 5 年研究开发了c o p s 2 文本相似性度量 检测系统，c o p s 首先将待比较的有效文本集合分解成句子的集合，并计算每个 句子的h a s h 值，最后通过比较两个文本相同的h a s h 值的数量来衡量两个文本的 相似度，但是该系统的句子划分不准确，例如英文文本里的“一是英文名中的 在国内，文本相似性度量技术的研究虽然刚刚起步，相对于国外还是比较滞 后。主要原因是中文文本相比于英文文本，文本内容结构复杂，并非像英文文本 那样语义单元是用空格隔开的英语单词，而且中文文本语义丰富多变。但随着 i n t e m e t 的发展，国内研究人员也逐渐重视文本相似性度量的研究，开始引进国 外的文本处理技术，并逐渐探索适用于中文文本特征的相似性度量技术，现在东 北大学、清华大学、大连理工大学、上海交通大学和中科院有关研究人士在分析 过滤中文语义技术方面进行了更加深入的研究。2 0 0 8 年s h a o z h iy e ，j i - r o n gw e n 和w e i - y m gm a t l 3 l 提出了抽取率可适应的s h i n g l i n g 算法，即以1 砌伽是正整数) 的抽取率随机的抽取一定数量的s h i n g l e ，计算其相似度，然后分别进行了刀次 试验，取该一次实验结果的平均值作为最后的相似度结果。2 0 0 3 年，西安交通 大学的宋擒豹为防止数字产品的复制剽窃，提出了c d s d g 1 4 】原型系统，它是为 解决数字产品的非法复制和扩散问题的系统。该系统与c h e c k 系统的实现原理 基本相同，也是将中文文本内容按照章节组织结构分解成树形结构，进而研究文 本的相似性，但它同时还引进了c o p s 系统基于句子匹配的相似性度量技术。 2 硕士学位论文第一章绪论 1 3 本文研究内容及组织结构 随着每年申报项目的数量的剧增，项目文本集合大小将达数百万。对于这种 大规模文本集合，s h i n g l i n g 1 5 l 是一种技术相对成熟，性能相对稳定的文本相似性 度量技术。因此本文将以s h i n g l i n g 算法为基础来研究文本相似性度量技术。为 了处理大规模数据，许多算法都考虑到了s h i n g l e 抽取的策略，但是没有考虑相 似度阈值、s h i n g l e 滑动窗口大小、s h i n g l e 权重门限、s h i n g l e 抽取率和文本属性 等参数对文本相似性度量算法的准确率和召回率的影响，并且没有消除用户对相 似度阈值把握的盲目性即便后来2 0 0 8 年s h a o z l dy e 等人研究了一些参数的相 关性，但也缺乏完美：未考虑s h i n g l e 在文档中的出现频率和权重；只考虑文本 篇幅属性，而未考虑文本的相似特征属性；其抽取策略：以1 n ( 刀为正整数) 作为抽取率，进行了开次实验，再求刀次实验的相似度结果的平均值，作为最后 的比较结果，因此供比对的总s h i n g l e 数目实质上并未减少，仍然是原文的1 0 0 ( 刀+ ( 1 厢) ) ：未考虑s h i n g l e 在文本中的出现频率：在大规模文本中，准确率和召 回率对抽取率的敏感性很小，而对相似度阈值很敏感，未提出相似度阈值可适应 的算法；并在词数很少的小规模文本中，抽取策略严重降低了准确率和召回率。 基于以上的问题，本文研究了相似度阈值跏曲、准确率p r e c i s i o n 、召回率r e c a l l 、 s h i n g l e 滑动窗口大小w 、s h i n g l e 权重门限只血、s h i n g l e 抽取率，和文本属性这 些参数的相关性，提出了在文本相似性度量中各参数的优化配置方案。 为了让读者更加清晰深入的了解各参数可优化配置的相似性度量技术，本人 精心地安排了论文的组织结构： 第l 章表明本文的选题背景及意义、讨论文本相似性度量技术国内外的研 究现状 第2 章概述文本相似性度量的定义、实现过程、判断标准及其性能评估指 标等基本内容，并对相似性度量的文本数学表示模型、中文分词技术、文本特征 生成及提取、文本相似度计算等关键技术进行了深入的分析。 第3 章实现两种最具有代表性的文本相似性度量算法：基于特征向量的文 本相似性度量算法和s h i n g l i n g 算法，并根据实验结果对这两个算法进行了性能 评估，为下一章研究文本相似性度量中的各参数的相关性分析打下了实验基础。 第4 章详细分析文本相似性度量中相似度阈值肋玎墒、准确率p r e c i s i o n 、 召回率r e c a l l 、s h i n g l e 滑动窗口大小w 、s h i n g l e 权重门限、s h i n g l e 抽取率， 和文本属性等参数的相关性。 第5 章在以上论述分析的基础上，结合实际应用，提出文本相似性度量中 各个参数的优化配置方案，并介绍该方案的实际应用 第6 章总结本文的工作，并提出文本相似性度量的下一步工作。 3 硕士学位论文第二章文本相似性度量概述 第二章文本相似性度量概述 本文是在文本相似性度量这个大的环境下进行展开的，因此在研究各个参数 的相关性和优化配置之前，首先对文本相似性度量的基本概念及其关键技术进行 介绍分析。 2 1 文本相似性度量基本概念 相似性度技术是数据挖掘、信息分类，信息检索等电子信息处理研究领域的 基础，电子信息包括数学数据信息、图片信息、多媒体信息和文本信息等等。所 谓相似性度量，就是计算- n 电子信息的内容和另外一则或者多则电子信息的相 似度，就是它们之间有百分之几十的内容彼此是相同的，相似度是介于0 和l 之间的一个百分数，用以衡量两个待比较信息的相似程度，最终目的还是要防止 电子信息的抄袭剽窃。剽窃不仅仅意味着大块文本信息的抄袭复制，更包括对原 文词语语义信息的位置变化等。本文的研究目的也就是要找出大规模文本中两两 项目文本信息的相似程度，为评审专家评审基金项目提供一个有力的参考。 2 1 1 文本相似性度量的作用 文本相似性度量技术，为用户减小信息的存储空间，高速搜索信息，防止论 文网页抄袭剽窃提供了很好的解决方案。 1 减小文本数据的存储空间 用户可以根据相似性度量的结果，把相似度超过一定阈值的文本视为相似文 本，并且在硬件存储空间里只保留该文本的一个样本，以后只要与该样本的相似 的即可不要再存储进来，这样在不影响工作的情况下，为用户节省了许多硬件资 源，同时也减少了人力和财力。众所周知，当今i n t e m e t 存在着无数的重复网页， 有的甚至只改变网页的头部和页脚信息，而内容却一字不动的复制下来，试想如 果没有一个网页相似性的评判工具，庞大的网页数据将需要的w e b 服务器的数 量将难以想象。 2 提高搜索性能 信息爆炸式地增长使得用户对于信息检索性能的要求越来越高，同时也是对 文本信息处理技术的一大挑战。g o o g l e 、百度、搜狐等搜索软件，以及数字图书 馆，资料档案库迫切需要用户查找信息的等待时间要短暂。而相似性度量技术在 提高搜索速度方面起着重要的辅助作用。相似性度量为用户剔除了许多冗余的信 息，每条信息在数据库只保留一个副本，这样就提高了用户搜索信息的效率，否 4 硕士学位论文第二章文本相似性度量概述 则在众多的文本数据里查找所需信息就犹如海底捞针。 3 避免抄袭剽窃 特别在论文撰写和基金项目申报领域，抄袭剽窃的识别是知识产权保护中一 项重要的内容。如何区别参考他人的文献和剽窃他人的技术成果这两种现象，是 在学术界领域防止抄袭剽窃，消除学术不正之风的迫切需要文本相似性度量技 术正是要解决两个文本相似度的问题，根据两个文本的相似度的百分值，即可精 确地判断出两文本的相似程度，从而使得查找抄袭剽窃他人成果的学术论文或基 金项目的问题就迎刃而解了。 2 1 2 中文文本相似性度量的一般实现过程 早期的文本相似性度量技术主要应用于英文文本，处理对象是一些由字母组 成的单词的集合，而本文研究的是相似性度量技术在中文文本中的处理过程，针 对的是各种中文文本格式。中文文本相似性度量技术的基本实现过程如图2 1 所 示。 图2 - 1 文本相似性度量的实现过程图 1 文本格式分析 我们常用的文本格式主要有w o r d 、h t i v i l 、p d f 、t x t 、c a j 、n i t 、k n i - i 、 x m l 和数据库文件等等但是为了能够应用于文本处理技术，最终都要处理成 盯盯、x l v i l 或数据库文件，以便于系统检索，因为只有这些格式才支持文本行的 检索。 2 文本预处理 文本预处理工作包括有效文本提取和分诃处理。 文本相似性度量只对文本文件里的文字信息感兴趣，但是像w e b 网页等文 5 硕士学位论文第二章文本相似性度量概述 件还存在图片和表格等干扰信息，或者用户只关注整个文本文件中的某部分文本 的相似性度量，这时需要相应的第三方软件来剔除这些噪音信息，有时候还需要 把文本中不同的内容用段落符号隔开，以分别进行相似度比较，具体情况视用户 的具体需求而定，这样才能提高文本相似性度量的处理效率。 以前的文本相似性度量技术主要是面向英文文本的，英文文本特征是语义最 小单元就是单词，并且有空格隔开，因此实现过程中没有分词这一步，但是本文 研究的是中文文本，因此中文文本分词是进行其他一切工作必不可少的一步，中 文文本的词语需要逐个的划分出来，并且最好去掉频用词和虚词，简单举例如下： 待分词的文本：s h i n g l e 被广泛的应用于大规模文本重复检测技术。 分词：s h i n g l el 广泛i 应用l 大规模i 文本i 重复i 检测l 技术 3 文本特征表示 为了精确地计算两个文档的相似度，必须表示出一个文档区别于其它文档的 特征，以作为比较的素材。有了以上的分词作为基础，那么文档特征表示的基本 单元是词语。最常见的文本特征表示法就是基于词性表示的方法，即根据每个划 分出来的词语的词性，过滤掉一些无实际意义的虚词和频用词，以筛选出具有实 际语义的实词作为文本的特征，这对于降低特征维度从而降低特征比较的时间复 杂度，具有重要的意义。而s l 蚴i n g 算法的文本特征表示比起基于词性的特征 表示方法，更加先进。其核心思想便是用两个或两个以上的相邻连接的词语绑在 一起作为文本特征表示的最小单元。第三章的s h i n g l i n g 算法中将对其进行详细 的分析。 4 文本特征选择 当文本集合的空间大到数百万时，并且文本篇幅也达到上万词长，此时生成 的特征元素数量巨大，如果把所有生成的特征元素都作为比较的素材，那么系统 运行的时间复杂度就会相应的增加。因此文本特征的抽取也是文本相似性检测的 必不可少的一步。抽取策略一般是基于特征元素权重的，但是也有研究人士按照 一定的比例随机抽取特征元素，不管怎么样，最终目的都是要减少供比较的特征 元素。 5 相似度计算 当生成并提炼了所有文本的特征元素之后，剩下的工作就是根据两个文本的 特征来计算他们的相似程度。一般的相似度计算公式有基于v s m 的余弦计算公 式和基于相同特征数量统计的方法，后面将做详细介绍。 2 1 3 文本相似性度量性能评估 文本相似性度量系统的性能评估参数【1 5 - 1 8 】主要有准确率p r e c i s i o n 、召回率 r e c a l l 和f - m e a s u r e 平衡系数。 6 硕士学位论文第二章文本相似性度量概述 1 准确率和召回率 参照文本分类，文本信息检索中的系统评估指标参数【1 9 t ，我们也使用准确 率p r e c i s i o n 和召回率r e c a l l 来评价文本相似性度量的性能。为了定义这两个指标 我们建立了相依表，如表2 1 所示。 表2 - 1 文本相似性度量相依表 实际相似的文本数量实际不相似的文本数量 检测到的相似文本数量 d sd n 未检测到的相似文本数量硼u 准确率和召回率的定义公式分别如公式( 2 1 ) 0 9 和公式( 2 2 ) 【1 9 】所示。 p r e c i s i o n = 丽d s ( 2 - 1 ) r e c a l l ：j 坠一( 2 2 ) d s + u n 。 不难理解，p r e c i s i o n 是正确检测到的相似文本数所占检测到的所有相似文本 总数的比例，r e c a l l 则是正确检测到的相似文本数与实际存在的相似文本总数的 比值。 2 f - m e a s u r e 平衡系数 一般p r e c i s i o n 是随着r e c a l l 的增长而增长，但有时候p r e c i s i o n 满足了用户 的需要，而r e c a l l 难以达到用户的需求，相反有时候r e c a l l 达到了要求，而p r e c i s i o n 又反而下降了总而言之，这两个指标难以同时达到最佳平衡，为了综合考虑 p r e c i s i o n 和r e c a l l 两个指标的平衡性，我4 f 3 弓1 用了f - m e a s u r e 评估指标 2 0 - 2 2 在 统计学里，f - m e a s u r e 也称为f - s c o r e ，是一种测试准确率和召回率平衡性的方法 它既考虑了p r e c i s i o n 参数，又考虑了r e c a l l 参数，可以被理解为这两个评估指标 的权重均衡。当f - m e a s u r e 越接近于l 时，p r e c i s i o n 和r e c a l l 就均衡的越好，而 它的值为0 时，就说明这两个参数均衡性很差。 常见的f - m e a s u r e 计算公式( 2 3 ) 如下所示 2 0 1 。是一个随机的正实数，当 其取值为2 时，即r e c a l l 的权重是p r e c i s i o n 的2 倍，当其取值为0 5 时，则是 p r e c i s i o n 权重是r e c a l l 的两倍，当其取值为l 时，则p r e c i s i o n 和r e c a l l 的权重均 等。在文本相似性度量中，该参数一般取1 ，当其值取1 时，公式( 2 3 ) 就转化 成了公式( 2 - 4 ) f p - m e a s u r e 卿们蔽篙黯 c 2 一筇 7 硕士学位论文 第二章文本相似性度量概述 正撇“馏_2型prec器zslon r e c a ( 2 4 ) +“ 2 2 中文文本分词 中国上下五千年，汉语的发展源远流长，其在世界上有着“博大精深 的美 誉，然而中文分词却是一个艰难的过程。自从中文信息处理技术发展以来，总共 有三种中文信息处理【2 3 】：字处理，例如中文字符计算机编码；词处理和句子处 理。词语是中文语义的最小单元，由两字以上组成的词语占多半，而且每个词语 还根据其实际语义和实际作用被赋予了词性，分为实词与虚词两种。实词包括名 词、动词、形容词、副词等；虚词就是“之乎者也 、“的一、“地和“得之类。 中文分词就是按照一定的语义和切分规则把没有特殊符号隔开的中文文本，转化 成词语的集合，还涉及到未定义词识别及语言特例等方面。可见分词技术是中文 信息处理例如文本分类、自动检索等技术必不可少的预备工作，同样，分词也直 接影响了整个文本相似性度量的准确度。 2 2 1 中文文本的特点 本文针对的是中文文本相似性度量技术，因此处理对象是中文文本，而中文 分词也是汉语所特有的研究课题。中文比起其他国家的语种具有其独特的性质 1 2 4 】，英、法、印欧语言词与词之间是有专门的特殊符号隔开的，虽然日韩语言 也是连续组成的，但是其也有着词语分割信息，例如格助词、动词的变位、片假 名和平假名等；而中文则是根据语义随意组合的，即没有分割词语的特殊符号， 也没有指导分词的辅助信息，并且词序也是千变万化的，没有固定的语法搭配， 词汇数量达到了百万计甚至千万计，并且还存在着一词多义，同义词的现象，这 些都给中文分词技术带来巨大的困难。 2 2 2 中文分词的原则规范 1 9 8 8 年制定的 口2 = 0 、1 、1 ) d 3 = 1 、1 、1 安全匹配模型中操作符的优先级必须明确规定，一般是按照非、与、或的顺 序，有时为了提高处理的速度，也可以按照从左到右或从右到左的顺序进行计算 处理，还可以自定义操作符，例如我们需要知道彳和口两个特征向量元素在文 档中是否是相邻连接的，就可以定义j o i n 操作符，aj o i nb 结果为1 ，则说明彳 和b 为邻接关系，否则不是 安全匹配模型可以用严范数模型【3 6 】来进行扩展，设两个文档么与占的向量 分别为 a l ，a 2 ，锄) 和 6 l ，6 2 ，玩) ，其中锄和玩分别表示文本彳和口中第刀个特 征向量元素的重要程度，并且经过了归一化处理。定义两文本的相似度为公式 ( 2 5 ) 【蚓与公式( 2 6 ) 【3 6 1 ，其中p l 。 s i m ( a , ，) = 1 一 s i m ( a ，磁) = 窆郸叫，i _ 盟- 一i ， i 节 1 b 1 j 1 三 窆衫够l ， 世- i- 鲈 i 当p 正无穷大时，显而易见： s i m ( a 。) = m i n a t ) ， s i r a ( a ，或) = 肘撕“) ， ( 2 - 5 ) ( 2 6 ) ( 2 - 7 ) ( 2 - 8 ) 这就是产范数模型，如果规定重要程度数值取0 或1 ，便是上面介绍的安全匹 配模型了。利用数学归纳法可以证明关系式( 2 9 ) ： s j 妇t 占巳) 妇缸t 圆乙) s 妇缸t 圆0 ) 5 j 锄缸重芝) s h 以t 骘) s 妇t 霹) ( 2 9 | ) 2 概率推理模型 文本相似性度量系统与其他的信息处理系统一个明显的区别是，相似性度量 系统中存在着许多不确定的因素，因为待比较的两文档数据不具有针对性，处理 这种非确定性因素就是利用概率推理的方法。 b i r ( b i n a r yi n d e p e n d e n c er e t r i w a l ) 【2 4 l 二值独立检索模型是一种十分简单也 1 3 b r t i r ，岛i f , 一，：) ( 厂一，) 其中，是相关文档的总数；n 表示，中包含特征卯的文档数目；厂是整个文本集 合的数量；石表示厂中包含特征卯的文档数。这样估计的参数值只与用户给定的 文档集合有关，如果改变了文本相似性度量的文本数据，就要重新估计参数，此 种方法显然不够灵活。因此该模型使用了参数学习的方法：即根据具体的文档集 合的一部分来估计参数，再使用该参数来进行整个文档集合的相似性度量。图 2 2 1 2 4 1 介绍了三种参数学习的方法。 与文本相似性度量相关的学习方法，首先需要设定一个相似度阈值，然后再 从找出的相似文本集合中得到相关性信息，最后再利用该信息进行参数估计，只 1 4 硕士学位论文 第二章文本相似性度量概述 要相似度阈值和文本特征项不变，该方法就可以用于该文本集合的所有相似性度 量；与文本集合相关的学习和与相似度阈值相关的学习是正交关系。它把文本集 合固定，对应不同的相似度阈值，得到参数的反馈信息，但是整个文本集合的特 征项集合固定不变，该参数只是适应于固定文本集合和固定的特征项集合，灵活 性很差，因为用户的应用需求是变化莫测的，文本集合的数据也不可能固定不变， 相似度阈值的设定也应该是用户可以自由把握的，因此以上两种学习方法扩展性 和灵活性很差。而与模式相关的学习方法可以解决以上的问题，因为该方法首先 从文本集合中随机抽取一些文本样本，来进行相似性度量，从而获得一些参数的 数值，然后再让该数值在整个文本集合中推广，对所有文本进行相似性度量。这 样该方法就适用于所有特征的文本数据，打破了参数与文本集合、相似度阈值一 一映射的僵局。 相似度阈值 文本集合 相似度阈值 文本集合 应用 文本集合 相似度闺值 图2 - 2 文本相似性度量中的学习方法 ( a ) 与相似度阈值相关的学习( b 油文本集合相关的学习 ( c ) 与模式相关的学习 3 向量空间模型 向量空间模型v s m 【3 7 1 ( v e c t o rs p a c 宅m o d e l ) 是g e r a r ds a l t o n 等人在2 0 世 纪6 0 年代首次提出的一种文本数学表示模型，并且他后来又和m i c h a e lj m c g i l l 1 5 硕士学位论文 第二章文本相似性度量概述 成功地将该模型应用到s m a r t ( s