（计算机应用技术专业论文）属性约简算法和文本相似度计算在智能分析系统的研究.pdf

摘要 信息化的发展无疑对当前公安工作产生了深远的影响，其最直接的表现就是 促进了当前公安工作运行模式的转变。公安的行为由行政行为和侦查行为构成， 其中侦查行中的案件现场记录、物证获取和保存、确定或排除嫌疑犯等均是公安 的重要职责。为了更好的履行这些职责的需要，在对案件进行分析时，公安部门 对应用现代的信息技术的需求越来越迫切。比如：智能分析是办案过程中一个很 重要的过程，但是以往的办法是人工分析，耗费了大量的人力物力，而且效果并 不显著。基于以上原因本文力图为公安系统的案件现场智能分析的串并案分析方 面做出技术分析和实现。其中使用的技术主要是不完备信息系统下基于粗糙集的 属性约简技术和基于分词的知网文本语义相似度计算技术。 首先，研究了在不完备信息系统下的属性约煎算法。基于改进的相容关系， 提出了一种属性约简的方法，并通过实例分析说明该算法是可行且有效的。并设 计了一个基于本文提出的基于相容关系的属性约简算法的原型系统，目的是对公 安系统的智能分析系统提供一种新的决策支持方法，迸一步提高案件分析的及时 性和准确性。本文设计的知识获取模型主要是解决案件串并问题。该模型可扩展， 具有一定的普遍性。 。 在中文信息处理中，文本相似度的计算广泛应用于信息检索、机器翻译、自 动问答系统、文本挖掘等领域，是一个非常基础而关键的问题，长期以来一直是 人们研究的热点和难点。本文分析比较了现有的文本相似度计算方法，然后提出 了一种新方法，它基于知网语义相似度计算的文本相似度计算方法，随后利用此 方法结合分词算法，给出了中文文本相似度计算的计算机系统实现过程，并以i t 文本为例进行了测试，对所用方法进行了验证。这一课题的研究及其成果对于中 文信息处理中的多种领域尤其是科技类文本相似度的计算比较，都将具有一定的 参考价值和良好的应用前景。 本文在对上诉两种技术做了介绍和改进后，针对公安的实际需求，实现了智 能分析的串并案智能分析子系统，并通过实验验证了其正确性。 关键词：租糙集，不完备信息系统，属性约简，分词，文本相似度，知网 a b s t r a c t a b s t r a c t w i t h o u td o u b t , t h e d e v e l o p m e n t o fi n f o r m a t i o n i z a t i o nc o m ei n t o b e i n g f a r - r e a c h i n gi n f l u e n c et oc u r r e n tp o l i c ew o r ka n di t sd i r e c te x h i b i t i o ni sa c c e l e r a t i n g t r a n s f o r m a t i o no fc u r r e n t p o l i c e s w o r km o d e p o l i c eb e h a v i o ri sf o r m e db y a d m i n i s t r a t i v eb e h a v i o ra n db e h a v i o ro fi n v e s t i g a t i n gw h i c hc o n c l u d ei n v e s t i g a t ee a s e o fc o n d u c tw r i t ed o w no ns p o t , m a t e r i a le v i d e n c eo b t a i na n dk e e p c o n f i r mo rg e tr i do f s u s p e c t , e t c i m p o r t a n td u t yo fp u b l i cs e c u r i t ya m o n gt h e m f o rt h en e e d so ft h e s e d u t i e so fb e t t e rp e r f o r m a n c e , w h e nt h ee a s ea n a l y z e ，t h ed e m a n df o rt h em o d e m i n f o r m a t i o nt e c h n o l o g yt ou s i n go f p u b l i cs e c u r i t yd e p a r t m e n ti sm o r ea n dm o r ea r g e n t f o re x a m p l e , av e r yi m p o r t a n tp r o c e s si nc o u r s ei si n t e l l i g e n ta n a l y s i s ，b u tt h ep a s t m e t h o di sg o t - u pa n a l y s i st h a tu s eal o to fm a n p o w e ra n dm a t e r i a lr e s o u r c 燃a n di t s e f f e c ti sn o tm a r k e d s ot h et h e s i st r yh a r dt od os o m et e c h n i c a la n a l y s i sa n dr e a l i z ei t o nc a s e sa n a l y s i s t h et e c h n o l o g i e su s e da m o n gt h e ma r ea t t r i b u t er e d u c t i o na n d c h i n e s et e x ts i m i l a r i t yc o m p u t i n gb a s e de l lw o r ds e g m e n t a t i o n f i r s n 弘t h ea t t r i b u t e sr e d u c t i o na l g o r i t h m i ss m d i e du n d e rt h ei n c o m p l e t e i n f o r m a t i o ns y s t e m s an e wa t t r i b u t e sr e d u c t i o na l g o r i t h mi sp u tf o r w a r db a s e do n t o l e r a n c er e l a t i o n , a n dt h ee f f e c t i v e n e s si si l l u s t r a t e db ya ne x a m p l ea n a l y z i n g a n da a n t e t y p es y s t e mf o rt h ei n c o m p l e t ei n f o r m a t i o ns y s t e m sf o rt h ep o l i c es y s t e mo nt h e b a s i so ft h et o l e r a n c er e l a t i o na t t r i b u t e sr e d u c t i o ni sd e s i g n e d a c c o r d i n gt oi t , an e w d e c i s i o n - m a k i n g 印p r o a c hc a l lb ep r o v i d e dt oi m p r o v ec a s e - a n a l y s i s st i m e l ya sw e l l a sm a k et h e a n a l y s i sm o r ev e r a c i t y t h em o d e l w h i c ht e n d s t os o l v et h e c a s e - i n t e l l i g e n t - a n a l y s i sp r o b l e m s c a nb eb o 也w i d e l yu s e da n d “p a n d e d 。 i nc h i n e s ei n f o r m a t i o np r o c e s s i n g t e x ts i m i l a r i t yc o m p u t i n gi sw i d e l yu s e di nt h e a l e ao fi n f o r m a t i o nr e t r i e v a l ，m a c h i n et r a n s l a t i o n , a u t o m a t i cq u e s t i o n - a u s w e r i n gt e x t m i n i n ga n de t c i t saq u e s t i o no fm u c he s s e n t i a la n di m p o r t a n tt h a tp e o p l es t u d ya sa h o t s p o ta n dd i f f i c u l t yf o ral o n gt i m e i nt h i sp a p e r , o nt h eb a s i so fa n a l y s i sa n dc o n t r a s t o fe x i s t i n gt e x ts i m i l a r i t yc o m p u t i n gm e t h o d s , an e wt e x ts i m i l a r i t ym e t h o di sp u t f o r w a r db a s e do nh o w - n e tc o m b i n e d t h er e a l i z a t i o no fc h i n e s et e x tw o r d s e g m e n t a t i o na n ds i m i l a r i t yc o m p u t i n g 谢t hc o m p u t e rs y s t e mi sp u tf o r w a r da n dc a r r y a b s t r a c t t h r o u g hm a n yt c s t i n gi tt e x t sa l et e s t e da se x a m p l et ov a l i d a t et h em e t h o dt h a tu s e d t h er e s e a r c ha n di t so u t c o m ew i l lh a v ev a l u a b l er e f e r e n c ea n d g o o da p p l i c a b l ep r o s p e c t t om a n yd o m a i n si nc h i n e s ei n f o r m a t i o np r o c e s s i n ge s p e c i a l l yi nt e c h n o l o g i c a lt e x t s i m i l a r i t yc o m p u t i n g t h i st h e s i sd i r e c t sm e e tt h ep o l i c e m e n sa c t u a ld e m a n d a f t e rt h et w o t e c h n o l o g i e s h a sb e e nd e s c r i b e da n di m p r o v e d ，t h et h e s i sr e a l i z ei n t e l l i g e n ta n a l y s i sa n dp r o v ei t e x a c t n e s st h r o u g ht h ee x p e r i m e n t k e y w o r d s ：r o u g hs e t , d i s c e r n i b i l i t ym a t r i x ，a t t r i b u t er e d u c t i o n , w o r ds e g m e n t a t i o n ， t e x ts i m i l a r i t y , h o w n e t i l l 修改提纲 1 论文题目 原题目为： 属 生约简算法和文本相似度计算在智能分析系统的应用研究 修改为： 属性约简算法和文本相似度计算在智能分析系统的研究 2 第2 4 页第三段 增加一段： 这里的阈值卢不是随意设置的，我们先把过往数据人工进行分类，然后利用 算法一次一次实验，最后得到一个最优结果。 3 第5 3 页图4 5 重新画图 指导老师： 答辩主席 沪7 年么月日 l 庞钐蕊黪 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 躲卑魄句年垆月妒 f 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 躲缱 第一章绪论 第一章绪论 1 1 本文研究的目的及意义 1 1 1 研究目的 目前案件现场智能分析系统中对串并案的处理方法通常为简单的字符匹配， 甚至不少公安部门仍然采用人工分析的方法，这些方法在效率和准确性上都不够， 不能给破案人员以最大的帮助，也无法提高破案的速度和效率，而目前的公安信 息管理系统的数据又属于不完备信息。针对这种情况，本系统试图利用改进的在 不完备信息系统下的属性约简技术和改进的基于分词的相似度计算技术来实现两 个案件的串并，为破案人员提供更准确的信息，提高破案效率。 一 当今社会已经进入了网络信息时代，计算机与网络信息技术的飞速发展使得 各个领域的数据和信息急剧增加( 信息爆炸) ，并且，由于人类的参与使得数据与 信息系统中的不确定性更加显著( 复杂系统) 。数据的丰富带来了强有力的数据分 析工具的需求，大量的数据被描述成“数据丰富，但信息贫乏”。快速增长的海量 数据收集、存放在大型和大量数据库中，没有强有力的工具，单靠人自身去理解 它们已经远远超出了入的能力。其结果是，收集在大型数据库中的数据变成难得 再访问的数据档案，这样，重要的决定常常不是基于数据库中信息丰富的数据， 而是基于决策者的直觉。如何从大量的、杂乱无章的、强干扰的数据( 海量数据) 中挖掘潜在的、有利用价值的信息( 有用知识) ，这给人类的智能信息处理能力提 出了前所未有的挑战，由此产生了人工智能研究的一个崭新领域数据挖掘 ( d 1 4 ) _ 和数据库知识发现( j ( d d ) 。 所谓数据挖掘，就是对观测到的数据集进行分析，目的是发现未来的关系和 以数据拥有者可以理解并对他有价值的新颖方式来总结数据。 人们一方面要面对海量数据，同时还可能面临质量低下的问题，即大量的不 确定信息。信息不确定有如下几种涵义：( 1 ) 信息不准确；( 2 ) 信息不完备；( 3 ) 模糊信息：( 4 ) 不确定性假设。处理不确定信息有很多方法，如证据理论，模糊 理论，概率统计等。但这些理论需要数据集合的额外信息，如证据理论中的信任 函数、模糊理论中的隶属函数、概率统计中的分布函数等。可想而知，对将要处 电子科技大学硕士学位论文 理的海量数据库去确定合适的信任函数、隶属函数和概率分布是不现实的。 粗糙集理论正是这样一种既能满足数据集合不同简洁程度表示的要求，又不 需要数据额外信息的处理不确定信息的知识表达、归纳和推理的数学理论。它能 在保持原数据集合分类能力或决策能力不变的前提下，以消除冗余的信息，从而 获取知识。它的最突出的优点是不需要数据集合之外的任何信息。因此，利用粗 糙集理论获得的知识更具客观性。 粗糙集理论提供的知识获取方法可以看作是k d d ( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ) 中的一种有效途径。正是因为它在k d d 中的成功运用，才引起了计算 机、人工智能等领域研究人员的广泛关注并得以迅速发展。经典z p a w l a k 的粗糙 集的研究对象是完全信息表，其条件属性值域是完全和经典的c o n t o r 集合。而在 科学研究、生产实践等活动中，由于数据测量、数据理解或获取的限制等原因， 在知识获取时往往面对的是不完备信息系统，如在现有的公安信息管理领域，由 于数据采集的不完整、使得信息系统不完备，从而影响了相关预测的精度呻。而以 满足自反性、对称性、传递性的等价关系为基础的经典租糙集模型并不适用于不 完备信息系统的信息处理”。近年来，不完备信息系统知识获取已成为粗集理论 与应用研究的热点。 属性约简是粗糙集理论的另一核心内容，众所周知，知识库中的知识( 属性) 并不是同等重要的。甚至其中某些知识是冗余的。特别是当数据是随机采集时， 其冗余性更为普遍。冗余知识的存在，一方面是对资源( 存储空间) 的浪费；另 一方面，干扰人们作出正确而简洁的决策。所谓属性约简。就是在保持数据库分 类或决策能力不变的条件下，删除其中不相关或不重要的知识“】 通过对不完备信息系统中的粗糙集属性约简算法的研究，目的是扩展信息系 统在数据不完备情况下数据挖掘的应用范围，即利用改进的相容关系对不完备信 息系统进行属性约简，提高算法的有效性和完备性，算法的提出给不完备信息系 统下的粗糙集算法研究提供了一些新的思路。 一般来说，r s 理论只能处理离散属性，所以有人也把属性约简过程归类到符 号( s y m b o l i c ) 机器学习中。但是在现场勘查系统中也有连续型数据，能否把案 件串并起来的关键就是看两个案件有多大的相似度。而当今世界以信息技术为代 表的现代科技日新月异，并正在对人类社会发展产生不可估量的巨大而深刻的影 响。如何在海量的信息中快速查找相关信息变得非常重要，用户的检索结果中经 常出现大量重复文本信息，使得有效的信息提取技术的研究越来越重要。文本相 似度是表示两个或多个文本之间匹配程度的一个度量参数，相似度大，说明文件 2 第一章绪论 相似程度高，反之文件相似程度就低。对于文本聚类、信息检索、问答系统，网 页去重，文本分类等很多领域，文本相似度的有效计算问题是进行信息处理的关 键。在信息检索中，为了提高检索的查全率和查准率，需要对文档进行分类、聚 类、排序和相关性反馈，这些操作都需要计算和分析文档之间的相似度。 分词系统是中文信息处理中的一个主要组成部分，是中文自然语言理解、文 献检索、搜索引擎以及文本挖掘系统中最基本的一部分。汉语的中文信息处理就 是要“用计算机对汉语的音、形、义进行处理”。然而，汉语文本中的词与词之间 却没有明确的分隔标记，而是连续的汉字串。分词体现了汉语与英语的显著的不 同。英语文本是小字符集上的已充分分隔开的词串，而汉语文本是大字符集上的 连续字串中文文本自动分词的研究从2 0 世纪8 0 年代初开始，目前比较常用和 实用的主要有最大匹配法、反向最大匹配法、二次扫描法、联想一回溯法、基于 词频统计的分词法以及基于知识的专家系统方法、神经网络方法等等，每种方法 都有其适用领域及优缺点，有时需要多种方法同时使用才能达到良好的效果分 词处理的好坏直接影响最后相似度计算结果的准确性。在这里，我们采用中国科 学院计算技术研究所的基于层叠隐马模型的汉语词法分析系统i c t c l a s 来对中文 文本进行分词处理并进行歧义校正。并在现有的计算相似度各种方法的基础上继 续探索改进，来提高相似度计算的准确性，为相关业务提供决策支持。 利用本文提出的扩展模型及约简算法和文本相似度计算方法，建立不完备信 息系统的现场勘查系统数据库中的知识获取模型，目的是对案件串并提供一种新 的决策支持方法，进一步提高现勘系统智能分析系统的针对性和实用性。并对进 一步促进粗糙集理论和文本相似度计算的实用化有着重要的理论和现实意义。 1 1 2 研究意义 希望通过本课题的研究，改进现行案件现勘系统智能分析的串并案子系统。 在现行的案件现场勘查系统下，智能分析系统还不够完善，尤其是串并案子系统， 从而造成现行智能分析系统无法真正实现智能分析。通过本课题的研究，可以在 相当程度上实现若干个案件的串并，通过实践证明，准确性上也有大幅提高，从 而能为案件侦破提供快速而准确的信息。本课题基础性作用十分明确，对具体实 践也具有较高的指导意义。 1 2 国内外研究现状 电子科技大学硕士学位论文 1 2 1 粗糙集的研究现状 粗糙集理论是波兰数学家z p a w l a k 于1 9 8 2 年首先提出的一个分析数据的数 学理论，在分类的意义下，这个理论定义了模糊性和不确定性的概念。在该理论 刚刚问世的几年，由于理论还不成熟，因而并未受到国际计算机学界的重视，当 时主要在波兰等几个东欧国家进行研究。直至八十年代末，粗糙集理论才引起了 世界各国学者的注意嗍。自1 9 9 2 年在波兰举行了r o u g hs e t 理论的第一届国际研 讨会以来，每年一度的国际r o u g hs e t 理论研讨会定期在世界各国召开。可以这 样说，目前r o u g hs e t 理论己经成为国际上人工智能研究的热点。 目前，国外对粗糙集理论的研究和应用发展的都比较快，尤其是1 9 9 2 年 r s l o w i n s k i 主编的关于粗糙集应用及其相关方法”1 比较研究的论文集的出版，推 动了国际上对粗糙集理论和方法的深入研究。1 9 9 2 年，在波兰召开了第一届国际 粗糙集研讨会，这次会议着重讨论了集合近似定义的基本思想及其应用，其中粗 糙集环境下机器学习的基础研究是这次会议的四个专题之一。1 9 9 3 年在加拿大召 开了第二届国际粗糙集与知识发现研讨会，这次会议极大地推动了国际上对粗糙 集理论与应用的研究，其主题是粗糙集、f u z z y 集与知识发现。1 9 9 4 年在美国召 开了第三届国际粗糙集与软件研讨会，这次会议广泛探讨了粗糙集与模糊逻辑、 神经网络、进化论等融合问题。粗糙集理论及应用的几位主要倡导者，在1 9 9 5 年 第1 1 期a c m 通讯上撰文，概括性地介绍了目前人工智能应用新技术之一的粗糙集 理论的基本概念，及其在知识获取和机器学习、决策分析、知识发现等领域的具 体研究项目和进展。尤其是1 9 9 5 年召开的第4 届模糊理论与技术国际研讨会，在 这次会议上，针对粗糙集与模糊集合的基本观点与相互关系展开了激烈的讨论， 较大地促进了粗糙集的研究。1 9 9 6 年在日本东京召开了第5 届国际粗糙集研讨会， 这是第一次在亚洲地区召开的范围广泛的粗糙集研讨会。1 9 9 9 年1 1 月在日本、2 0 0 0 年1 0 月在加拿大又召开了第l 届和第2 届“粗糙集和计算的当前趋势”学术会议， 来自波兰、美国、加拿大、日本、挪威、俄罗斯、乌克兰和印度等国家的研究人 员参加了会议，会议阐述了当前粗糙集、模糊集的研究现状和发展趋势，指出将 着重在软计算、数据库、人工智能和近似推理等理论和应用方面发展。目前，许 多关于人工智能、模糊理论、信息管理与知识发现等国际会议上经常可以看到涉 及粗糙集的论文。 在国内，对粗糙集( r o u g hs e t ) 理论的研究始于9 0 年代中期，现在已有许 多高校和科研院所的专家、学者对r o u g hs e t 的理论和应用进行一系列的研究， 4 第一章绪论 并取得了令人鼓舞的成果。2 0 0 1 年5 月在重庆邮电学院举办了首届中国r o u g hs e t 和软计算学术研讨会( c r s s c 2 0 0 1 ) ，2 0 0 2 年1 0 月在苏州大学举办了第二届中国 r o u g hs e t 和软计算学术研讨会( c r s s c 2 0 0 2 ) ，2 0 0 3 年5 月在重庆邮电学院同时 举办第三届中国r o u g hs e t 和软计算学术研讨会( c r s s c 2 0 0 3 ) ，2 0 0 4 年1 0 在浙 江舟山举行由浙江海洋学院承办，同济大学协办的第四届中国r o u g h 集与软计算 学术研讨会( c r s s c 2 0 0 4 ) ，2 0 0 5 年8 将由鞍山科技大学承办的第五届r o u g hs e t 和软计算学术研讨会( c r s s c 2 0 0 5 ) 和第九届粗集、模糊集、数据挖掘与粒度计 算国际学术会议( r s f d g r c 2 0 0 3 ) ，这些会议的举办表明我国r o u g hs e t 理论研究 的队伍正在不断壮大，己经得到国际同行的重视和认可。虽然，国内对租糙集理 论的研究和应用还处于探索阶段，没有成形的实验系统但是我国在这个领域的 发展速度很快，目前中科院、清华大学等研究所和高校己经加入到这个领域中， 并取得了一定的成果。相比之下，国外已建立了不少的数据库领域知识发现( 1 ( d d ) 系统，它们一般都由数据预处理、基于粗糙集或其扩展理论的数据约简、决策算 法等部分组成。其大概思想是先进行必要的数据预处理，为数据约简做准备，。并 在此基础上根据值约简等减少属性和个体数目，最终提取规则并将之应用于新对 象的分类。比较有代表性的有美国k a n s a s 大学开发的基于租糙集的实例学习系统 ( l e r s ) r o u g bs e td a t ae x p l o r e r ( r 0 s e ) r e g i n a 大学利用粗糙集理论开发的 知识发现系统k d d - r ，该系统目前被广泛的应用于医疗诊断、电信业等领域”3 ，还 有美国k a n s a s 大学开发的l e r s ( l e a r n i n gf r o m e x a m p l e sb a s e do nr s ) 系统， 该系统被应用于医疗诊断、社区规划、全球气象等研究方面嘲。 国外目前在粗糙集领域的研究主要集中在约简的优化算法、粗糙集理论和模 糊理论，粗糙集理论同神经网络理论等其他人工智能技术的结合、粗糙逻辑等课 题上。 1 2 2 不完备信息处理的研究现状 在日常的各项现代化、信息化任务中，各层管理人员使用的主要是数据库 ( 表) 。这些数据库不仅是巨大的，而且还常常遇到数据缺损( 信息不完备) 情况。 例如，在为医学诊断提供辅助决策支持的应急诊断智能系统中，智能系统辅助决 策能力的强弱取决于它从大量的病例数据库中获取的知识。而在数据库中，患者 的症状一般是通过病人描述、仪器检查、医生观察等方式来获得。但由于病人描 述不清楚、或者病人不适合做某项仪器检查、或者由于当时时间紧迫来不及做详 5 电子科技大学硕士学位论文 细检查等原因，病人( 对象) 的某些症状( 属性) 的描述就不能够获得。这种情 形在银行贷款、供应链管理、交通管理、故障诊断等领域也是不可避免的。此时， 如何从这些不完备信息系统获取有用的知识就具有重要的理论和现实意义。 不完备信息系统的知识发现是人工智能领域的重要问题。目前有多种方法用 于不完备信息系统的知识获取问题，其中处理空值最简单直接的方法是删除带有 空值的对象，但删除空值可能造成数据浪费；第二种方法是通过数据补齐将不完 备信息系统转化为完备信息系统，再利用完备信息系统的处理方法进行处理。如 通过统计分析填补空值。“”1 ，利用其它条件属性的取值和决策属性的取值或属性之 间的关联来估计空值“”“4 ；利用贝叶斯模型“”和证据理论m 1 也是比较常见的数据 补齐方法，但贝叶斯模型需要知道概率密度，而证据理论则需要证据函数，这些 数据之外的信息往往很难得到；在粗糙集理论中，t z u n g - p e ih o n g 等人利用上下 近似提出了一种填补空值并同时提取规则的方法，但这种方法无法处理空值较多 的信息系统。另一种做法是让专家根据一定的条件给出空值的估计值，但这种方 法有很大的主观性和随意性。在商业软件l e r s “”中，还提到一种处理空值的方法： 用所有可能的取值代替空值，根据不同的组合把不完备信息系统转化为完备信息 系统。但这种方法当信息系统中空值较多时计算复杂度过高，效率极其低h ，同 时得到的知识也并非可靠。卫金贸讨论了空值环境下决策规则的形式“”；但没有 进一步讨论决策规则提取的有效方法。 由于上述两种空值处理方法的局限性，人们提出了第三种处理方式：在不改 变信息系统的前提下对不完备信息系统进行研究。但由于不确定性值的出现，不 能够在对象集上找到符合实际需要的等价关系，因此，只能从对象之间的相似形 来考虑对象之间的关系。就目前的研究情况来看，对不完备信息系统的粗糙集理 论的研究主要采用了相容关系“”、非对称相似关系和量化容差关系“”，王国胤“” 提出了限制容差关系，y a oy y 啪1 通过定义邻域算子研究了般二元关系的粗糙集 模型，虽然此文并未特别针对不完备信息系统，但完全可以推广到不完备信息系 统上的一般二元关系。 在不完备信息系统约简方面，最常见的是利用辨识矩阵和布尔推理方法o ”， k r y s z k i e w i c zm 啪1 给出了不完备决策表的知识约简方法，并且提出了种获取最 优规则的方法。l e u n g 3 等利用极大相容块的概念，刻画了不完备信息系统中隐含 于相似关系中的知识信息，建立了不完备信息系统中知识获取的一种方法一极 大相容块技术。国内学者也提出了许多约简算法，如分层递阶约简算法和基于散 列的约简算法等等，而且还在不断地发展和完善之中。 6 第一章绪论 1 2 3 文本相似度计算的研究现状 所谓文本相似度计算是指利用计算机自动计算文本间的相似度，文本相似度 是表示两个或多个文本之间匹配程度的一个度量参数，相似度大，说明文件相似 程度高，反之文件相似程度就低。目前，国内外很多学者在研究文本相似度计算 问题，并提出了一些解决方案，如g e r a r ds a l t o n 和m c g i l l 于1 9 6 9 年提出的向 量空间模型v s m ( v e c t o rs p a c em o d e l ) ，它的基本思想是把文档简化为以特征项 的权重为分量的向量表示，通过词频统计和向量降维处理计算相似度。基于向量 的文本相似度计算方法是最常用的文本相似度计算方法，该方法将要比较相似度 的文本根据文本中的词语将文本映射为n 维空间向量，然后通过比较向量间的关 系来确定文本间的相似度，其中最为常用的方法是计算向量间的余弦系数，但传 统向量空间模型缺点是模型中各词语间相互独立，无语义上的关系。为此，广义 向量空间模型( g e n e r a l i z e dv e c t o rs p a c em o d e l ，g v s m ) 就利用文本而不是用词 来表示词间关系。挪威a g d e r 大学的v l a d i m i ro l e s h c h u k 等人提出基于o n t o l o g y 的文本相似度比较方法，将本体论引入了文本相似度计算，它能计算文本的语义 相似度。此外还有学者在研究句子间相似度的计算，如哥伦比亚大学的c a r b o ne l l j 等人的最大边缘相关的方法删r ( m a x i m a lm a r g i n a lr e l e v a n c e ) 方法。学者c h r i s h q d i n g 采用隐性语义索引模型l s i ( l a t e n ts e m a n t i ci n d e x i n g ) 方法，先从 全部的文档集中生成一个标引项一文档矩阵，该矩阵的每个分量为整数值，代表 某个特定的标引项出现在某个特定文档中次数。然后将该矩阵进行奇异值分解， 较小的奇异值被剔除。结果奇异向量以及奇异值矩阵用于将文档向量和带比较文 本向量映射到一个子空间中，在该空间中，来自标引项一文档矩阵的语义关系被 保留，同时标引项用法的变异被抑制。最后，可以通过标准化的内积计算来计算 向量之间的夹角余弦相似度，根据这个值来比较文本间的相似度。l a m b r o s 等提出 同时依据句子的表层结构和内容计算相似度的方法。在计算相似度时，系统使用 了两级动态规划技术，应用动态规划算法允许在两个长度不同的句子之间计算语 句相似度。n i r e n b u r g 等提出了两种串匹配的方法，即更规范的“切块+ 匹配+ 重组” 方法和整句级匹配的方法。这两种方法所采用的相似度衡量机制都是词组合法。 该系统的相似度计算采用罚分制，两个句子匹配所得到的总罚分值由句子中每个 对应单词对的比较所得的罚分组合而成。其它方法还有b e l k i n 和c r o f t 予1 9 9 2 年提出的概率模型等。 国内学者潘谦红、王炬、史忠植( 1 9 9 9 ) 提出利用属性论计算文本相似度， 7 电子科技大学硕士学位论文 建立了文本属性重心剖分模型，通过坐标点与坐标点的距离计算关键词与关键词 的相关性，通过坐标点与单纯形的关系计算关键词与文本的相关度，通过单纯形 与单纯形的关系计算文本与文本的相似性。张焕炯、王国胜、钟义信( 2 0 0 1 ) 提 出了基于汉明距离的文本相似度计算，该方法提出了汉明码概念。与其它的文本 相似度计算公式相比较，因该方法只是利用模2 加等运算，其方便性是不言而喻 的，它完全避开了诸如在欧氏空间中求相似度的大量乘法运算，因此，可以较大 的提高速度。其次，它跳出了传统的借用空间的理念，而是用码字的方法来表征 文本信息的特征，可以不仅限于关键字等孤立的信息，这为联合的描述文本的信 息提供了可能。晋耀红( 2 0 0 4 ) 提出了基于语境框架的文本相似度计算方法，它 把文本内容抽象成领域( 静态范畴) 、情景( 动态描述) 、背景( 褒贬、参照等) 三个侧面，从概念层面入手，充分考虑了文本的领域和对象的语义角色对相似度 的影响，重点针对文本中的歧义、多义、概念组合现象，以及语言中的褒贬倾向， 实现了文本间语义相似程度的量化。此外还有霍华、冯博琴( 2 0 0 5 ) 提出的基于 压缩稀疏矩阵矢量相乘的文本相似度计算方法，能够减少计算和存储空间的开销。 该方法仅对非零元素存储和表示，然后用压缩稀疏矩阵矢量相乘的方法计算文本 和查询的相似度，可通过给定相似度阈值来判定一个文本是否和查询相似。各种 文本相似度计算方法均在特定领域取得了良好的效果，但还都存在着缺点与不足， 尚需进一步加以改进。 1 3 本文的研究内容和内容安排 1 3 1 本文研究内容 本次课题主要有以下几个方面的研究工作： ( 1 ) 了解知识发现的体系结构，学习粗糙集理论的基本概念，研究不完备信 息系统下粗糙集理论进行属性约简的算法； ( 2 ) 了解一些常用的经典文本相似度计算方法，研究它们的性能和优缺点以 及存在的问题和发展方向； ( 3 ) 研究在不完备信息系统中基于粗糙集属性重要性的属性约简算法； ( 4 ) 研究基于分词的文本相似度的计算； ( 5 ) 具体的串并案智能分析子系统的建立。 1 3 2 本文内容安排 第一章绪论 本文章节及内容安排如下： 第1 章绪论 主要介绍本文研究的且的和意义，介绍各类文献资料上前人关于相关研究方 向的研究成果，最后介绍了课题研究的主要内容； 一 笫2 章不完备信息系统中属性约简算法的研究 介绍了粗糙集理论中出现到的相关概念：知识和知识库、不可分辨关系、上 下近似、正域、负域和边界、约简和核、知识的依赖性、知识依赖性的度量等。 同时介绍了信息熵、条件熵等重要的概念；针对现有系统数据的不完备性，介绍 了现有常见的相容关系，提出了一种改进的相容关系，并给出了基于属性重要性 的约简算法；同时给出了这个算法的分析和验证 第3 章基于分词的中文文本相似度计算 介绍了基于分词的中文文本相似度计算模型及常用的计算方法；并做出了选 择和改进，对中文文本相似度过程进行了仿真分析； 第4 章串并案智能分析子系统的实现 介绍在不完备信息系统下粗糙集算法和文本相似度计算研究中开发的实际应 用系统，并通过一系列的实例验证前述所提方法的准确性 第5 章结论与展望 对本课题提出的研究方法的特点、结论和意义进行了总结和探讨，指出其缺 点和不足，对今后的研究工作及其方向提出展望。 9 电子科技大学硕士学位论文 第二章不完备信息系统中属性约简算法的研究 2 1 粗糙集理论基础 粗糙集理论是一种新的处理模糊和不确定性知识的数学工具。其以不可分辨 关系为基础，给出知识表达系统这一模型，利用精确的上、下近似集逼近不精确 对象，赋予知识清晰的数学意义，从而提供了用数理逻辑方法来表达、约简、分 析、推理不精确知识的新思路。目前，粗糙集理论已被成功地应用于机器学习、 决策分析、过程控制、模式识别和数据挖掘等领域。 2 1 1 粗糙集理论的基本概念 本节主要介绍粗糙集理论的一些主要概念和结果。 定义2 一l一般地，一个信息表知识表达系统s 可以表示为四元组 s = ( u ，a = c u d ，y ，力。其中u 是表示对象的非空有限集合，称为论域；a = c u d 是表示属性的非空有限集合，c 称为条件属性集合，d = 表示决策属性集合， 且c n d = o ；矿= u 圪，圪表示属性口的值域；，表示u x a _ 矿的一个信息函 a e a 数，它为每个对象在每个属性上赋予一个信息值，即v a a ，x u ，f o ，4 ) 圪。 若d = o ，则称信息系统为数据表；否则称为决策表，决策表是一种特殊而重要的 知识表达系统，也是一种特殊的信息表示，它表示当满足某些条件时，决策应当 如何进行。若存在一个工u ，口c ，f ( x ，a ) 未知( 记作：f ( x ，a ) = + ) ，则称信 息系统是不完备的；否则称信息系统是完备的。 定义2 2对信息系统s = ( u ，a = c u d ，v ，d ，b a 确定【厂上的不可分辨关 系如，如下： j c 如y v 6 b ，f ( x ，6 ) = 厂( y ，b ) 石，y u 公式( 2 1 ) 显然吃满足自反性、对称性和传递性，因此是一个等价关系。通过这个不可 分辨关系，可以得到决策系统的一个划分，我们称划分后的等价类为不可分辨类， 通常记【x 。= o u ：x r b y 为工所在的b 等价类，则u 中所有对象的不同等价类构 成u 的一个划分，记为u 。 定义2 3令x u ，当x 能用属性子集p 确切的描述( 即是属性子集尸所 1 0 第二章不完备信息系统中属性约简算法的研究 确定的u 上的不可分辨集的并) 时，称z 是p 可定义的，否则称石是尸不可定义 的。p 可定义集也称为p 精确集，p 不可定义集也称为p 非精确集或p 粗糙集。 对于一个样例子集，根据一个条件子集所确定的不可分辨关系，我们有时能 够准确的判断一些样例是否属于该概念，也有可能不能够判定这些样例是否属于 该概念为了描述这个问题，粗糙集理论采用了上近似集、下近似集的概念。 定义2 - 4 对信息系统s = ，a = c u d ，v ，力，对于每个子集x c u ，b a 且 b 。集合石的曰下近似罡( x ) 、b 上近似口一( z ) 和边界占。( 幻分别定义如下： 罡( 习= 协u ： 工l 互石 b 一( 幻= x e u ： x j n 石中) b n n ( 柳zb - ( z ) 一盈( 朋 公式( 2 2 ) 公式( 2 - 3 ) 公式( 2 - 4 ) 定义2 5假定集合z 是论域u 上的一个关于知识p 的粗糙集，定义其p 精 度为：d ，( 幻爿a p t , ( 柳i i a p t , 一c a d i ，其中若j = o ，则d ，( = 1 精度d 。) 用来反映我们对于了解集合z 的完全程度，对于每一个p 且 x u ，有0 d 。( 朋s 1 ；当时d 。( 朋= 1 ，z 的边界为空，集合z 为p 可定义的； 当d 。( 石) 1 时，则集合x 有非空边界域，该集合为p 不可定义的。 定义2 - 6假定集合工是论域u 上的一个关于知识p 的粗糙集，定义其p 租 糙度为：p 。( 石) = l d ( 幻 显然0 岛( 1 。当岛( 幻= 1 时，说明u 中没有一个对象可以肯定属于石， 此时说明石关于口是最粗糙的；当风( z ) = 0 时，说明u 中对象要么肯定属于石， 要么肯定不属于石，此时说明石关于b 是清晰( 精确) 的。当0 风( 朋 1 时， 称j 是关于占的粗糙集，此时也称知识曰不能完全刻画x ；当风( 石) = o 时，则x 是关于占的精确集，此时也称知识b 能完全刻画j 。风( 工) 越大，则x 关于曰越 粗糙，不确定性越大；岛( 幻越小，则z 关于占越精确，不确定性越小。 2 1 2 属性约简 知识约简是指在不影响知识表达能力的条件下，通过消除冗余知识，从而获 得知识库的简洁表达的方法。在粗糙集理论中，就是针对信息系统，在保持信息 系统分类能力不变的前提下，通过消除冗余属性和冗余属性值，最终得到信息系 统的分类或决策规则的方法。知识约简是粗糙集理论的精髓，是从信息系统中获 取知识的方法和途径，也是粗糙集理论的重要研究内容和热点之一 电子科技大学硕士学位论文 在粗糙集理论中，知识约简分为属性约简和属性值约简，由于属性值约简相 对较为简单，相关内容可参见文献。属性约简则困难得多，甚至到现在还没有 完全解决，因此仍是研究的重点。 下面首先介绍与属性约简有关的一些基本概念，然后介绍属性约简的常见约 简方法。 1 相