（计算机软件与理论专业论文）基于联合特征提取的粗糙集文本分类的研究.pdf

北京科技人学硕七学位论文 摘要 目前传统的信息检索技术己不适应日益增加的大量文本数据处理的需要，用户需要 更加有效的检索算法实现文档重要性和相关性的排列，完成不同文档的分类比较，或找 出多文档的模式和趋势。所以，文本数据的挖掘成为数据挖掘中一个日益流行且重要的 研究课题。 文本挖掘中常用的技术有文本的自动分类、聚类、文本总结和关联分析等，其中文 本自动分类是一种重要的方法。利用文本的自动分类技术可以用来整理互联网内部的文 本，通过将文本分配到一个类别体系中，限定查找文本的范围；还可以应用到搜索引擎 的检索结果的组织上，将搜索引擎的检索结果划分为若干个具有明确主题的簇，使得用 户只考虑相关的簇，大大缩小了需要浏览的文本数量。 本论文主要探讨了文本自动分类的特征提取和分类算法，所作的主要工作如下： 1 研究了文本的特征提取方法，通过对互信息和贮统计的研究根据其各自的缺 陷，并对特征提取的方法进行了改进。 2 研究了如何利用粗糙集的知识约简理论提取文本分类规则的新方法，该方法可以 自动提取分类规则，比人工建立规则库容易实现得多： 基于粗糙集理论的文本分类算法中，将文本特征项的权值作为规则的条件属性，文 本所属的类别用作决策属性，构造决策信息表。首先将每一文本的每个特征项的权值进 行离散化处理，然后通过知识约简提取出文本的分类规则。该方法生成的规则易于理 解，分类准确度较高，分类的速度快。 最后，对本论文的内容进行了总结，并对文本挖掘的研究提出了展望 关键词：文本挖掘；文本分类；粗糙集：互信息；贮统计；联合提取特征 北京科技大学硕士学付论文 t h er e s e a r c ho ft e x t c a t e g o r i z a t i o nt e c h n i q u e sw i t h r o u g hs e tb a s e do ne x t r a c t i n gc o m b i n e df e a t u r e s a b s t r a c t a tp r e s e n t , t r a d i t i o n a li n f o r m a t i o nr e t r i e v a li sn o ta p p r o p r i mf o rd i s p o s i n gl a r g ea m o u n t s o f t e x td a t a t h em o r ee f f e c t i v e r e e v a a g o r i t b m sa r en e e d e db yu s 懿t od i s p o s ed o e t a n e m s b yt h e i ri m p o r t a n c eo rr e l e v a n c e , t oc o m p a r et h e i rc l a s s e s , o rt of i n dt h em o d e la n dt r e n do f m u l t i - d o c u m e n t s s o t e x t d a t a m i i l i l 唱( t e x t d m ) i s 孕a d u a i l y a p o p u l a r a n d i m p o r t a n t r e s e a r c h p r o j e c t t h eo o m l n o nc a t e g o r i z i n gt e c h n o l o g i e so f t e x td mi n c l u d ea u t o m a t i cl j e x tc a t e g o r i z i n g , a u t o m a t i c t e x t c l u s t e r i n g , t e x t s u m m a r i z i n g a n d t e x t r e l e v a n c e 赳m l y 2 i i 唱，e t c a m o n g t h e m , a u t o m a t i ct e x tc a t e g o r i z i n gi sa l li m p o r t a n tt e c h n o l o g y i tc a i ls o r tw e bd o c u m e n t s a n d d i s t r i b u t ee a c hd o c u m e n tt oa c a t e g o r i z i n gs e t t h i sw i l lc o n f i n et h es e e k i n gm l 咎o f d o c m n e n t s a l s oi tc a nb eu s e dt oo r g a n i z et h er e t r i e v a lr 趿l l t so f s e a r c h i n ge i l 蛳ns h a r p l yr l u c e st h e a m o u n to f t e x t sb yd i v i d i n gt h e mt oc l a s s e so f s p e c i f i ct o p i c s s oi ri sc o n v e n i e n tf o ru s e r st o c a r eo n l ya b o u tt h e 托l e v a n ts e t s i nt h i sp a p e r , a l g o r i t h m so f a u t o m a t i ct e x tc a t e g o r i z a t i o na l es t u d i e d t h em a i nw o r ki sa s f o l o w s ： 1 ) s t u d y t h ee x l r a c tt e x tf e a t u r e s , t h r o u g hm u t u a li n f o r m a t i o na n d 贮f u n c t i o ns t u d yi n a c c o r d a n c ew i t ht h e i rr e s p e c t i v ee l t o r s , a n di m p r o v et h ee x l r a c tt e x tf e a t u r e s 2 ) s t u d y h o wt oe x t r a c tt h er u l e so f t e x tc a t e g o r i z a t i o nb yt h ek n o w l e d g er e d u c t i o no f r s t h e o r y f o rt e x tc l a s s i f i c a t i o nb a s e do nr s t h e o r y , ad e c i s i o nt a b l ei sc r e a t e dw i t ht h ew e i g h t so f t e x tc h a r a c t e r i s t i ct e r m sd i s c r e d i t e da st h er u l e s c o n d i t i o na t t r i b u t e sa n dt h ec l a s s e so f t e x t sa s d e c i s i o na t t r i b u t e s t h e n , t h er u l e so f t e x tc a t e g o r i z a t i o na r ee x t r a c t e db yk n o w l e d g er e d u c t i o n o f r s t h er u l e sa r ee x t r a c t e db yt h i sm e t h o d 黜e a s yt ou n d e r s t a n d t h ea c c u r a c ya n d s p e e d i s h i 曲 a tt h ee n do f t h i sp a p e r , c o n t e n t so f t h i sp a p e ra r es u m m a r i z e d , a n dt h eo r i e n t a t i o no f t e x t d m m i l l i n gi sp r o p o s e & k e yw o r d s ：t e x tm i n i n g ；t e x tc a t e g o r i z a t i o n ；r o u g hs e t s ；m u t u a li n f o r m a t i o n ；f f u n c t i o n ；c o m b i n e de x t r a c tf e a t u r e s 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 北京科技大学或其他教育机构的学位或证书所使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表 示了谢意。 签名：拯喜习日期： 关于论文使用授权的说明 硼6 2 当 本人完全了解北京科技大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文。 ( 保密的论文在解密后应遵循此规定) 签名：盎臣阻导师签名孝雌日期： 2 叼众。够 北京科技大学硕士学位论文 引言 人类自进入信息时代( i n f o r m a t i o na g e ) 以来，随着信息量呈几何数的激增，尤其 是国际互连网络( i n t e m e t ) 及企业内部网络( i n u a n e t ) 的日益普及，信息朝着更加集 中、更加分布的两个极端快速发展。如何从i n t e r n e t 上快速准确获取信息成为人们日益 关心的问题。 然而通过传统的信息检索工具往往会遇到返回成百上千个文档的情况，面对如此庞 大数量的文档，用户只能从头到尾对反馈的结果进行翻阅浏览，以便寻找出自己真正想 要的内容。然而，在这些反馈的结果中真正有用的文档往往只占全部文档的一小部分。 这对于经常需要处理大量文本信息的研究人员、信息咨询人员、调查人员等明显是不现 实的。 而基于w e b 文本挖掘技术信息检索则可以用来解决这类问题，基于w e b 文本挖掘 技术的信息检索融合了文本挖掘的思想，并将单一的资源发现或者单一的信息提取的传 统的信息检索方法结合起来，从而达到在w w w 发现资源并将其中的信息提取出来进 行处理的目的。 全文共分为6 个章节，分别论述了基于文本挖掘技术、文本特征提取技术、粗糙集 理论、分类算法及实验对比等内容 绪论。本章论文对研究的背景、研究进展和所做的工作做了说明。 w e b 挖掘综述。本章论文对数据挖掘及w e b 挖掘进行了较为全面、系统地评述， 同时概要地介绍了一下企业信息化的内容。在此基础上，详细地介绍了w e b 文本挖掘 的描述性定义和w e b 文本挖掘的产生背景；然后评述了w e b 文本挖掘与信息检索的区 别；并讨论了w e b 文本挖掘技术的应用、发展情况以及所面临的问题。 w e b 文本分类。本章重点研究了文本分类中的特征提取算法，并对当前特征提取算 法中存在的不足之处指出，在研究特征提取算法的不足之处，并改进了文本特征提 取的算法，以提高特征项提取的准曲率，对文本分类的正确率有很大的提高。 文本分类的处理流程。本章对文本分类的一般处理流程的各个阶段做了全面的评 述。并重点研究了传统的特征提取方法存在的不足之处。 粗糙集理论简介。本章对涉及到文本分类的粗糙集知识做了详细的评述。 基于粗糙集文本分类的算法研究。本章对综合运用改进后的特征提取算法和粗糙集 的知识，进行文本分类。给出了分类的主要步骤、抽取规则和规则匹配的算法步骤。 北京科技大学硕十学位论文 试验分析。本章比较了传统的特征提取算法和改进后特征提取算法所得试验数据的 对比。 结论部分对于全部的研究工作进行了总结，指出了遗留和尚待解决的问题，并对今 后的工作进行了展望。 2 北京科技大学硕十学付论文 1 绪论 文本自动分类( a u t o m a t i ct e x tc a t e g o r i z a t i o n , a t c ) 能够合理地、有效地组织海量信 息资源，向用户提供简单有效的检索服务，被广泛应用于自动标引、文本过滤和词歧义 切分等文本自动处理技术。文本自动分类涉及信息检索、自然语言处理、计算语言学、 机器学习、统计学和心理学等多个学科领域，目前仍然面临着许多及待解决的难题。文 本信息资源爆炸性的增长趋势，使人们认识到文本自动分类研究的重要理论意义及其广 阔应用前景。 1 1 研究背景 1 1 1 文本自动分类研究的必要性 随着信息技术的飞速发展，特别是存储设备的迅速更新换代和i n t e m e t 的普及，电 子文本信息资源激剧增长。截止2 0 0 6 年1 1 月底，g o o g l e ( h t t p ：w w w g o o g l e t o m ) 和百 度( h t t p ：w w w b a i d u c o m ，世界上最大的中文搜索引擎) 索引的页面己分别超过8 0 亿和 3 亿。此外，大量的图书馆、出版社和信息中心等机构也纷纷建立文本数据库，以提供 目录、全文和摘要等信息检索服务。尽管用户对图像、视频和音频等信息资源的检索需 求也在急剧增加，文本仍然是最主要的非结构化信息资源【1 1 1 2 1 。通过人工方法来组织管 理海量信息资源，绝大多数机构面临着人力、物力和财力资源不足的困境。大量研究表 明，自动标引”1 1 4 1 、自动分类 5 1 1 6 1 1 7 1 、自动聚类 s l 、自动摘要 9 1 、文本过澎1 0 1 、叙词表自 动构建1 1 】【1 2 1 、相关反饼”】和主题发现【1 4 1 等文本自动处理技术，可以有效地组织、管理 和分析大规模文本信息资源，向用户提供高效的信息检索服务。 文本自动分类采用分类思想组织文献，不仅符合人们的思维习惯和应用习惯，而且 需求资源较少，操作简单，能够适应大规模文本处理的要求。文本自动分类是当前信息 检索和自然语言处理领域最活跃的研究主题之一。 1 1 2 研究进展 北京科技大学知识工程研究所在已有的研究基础上就知识发现领域继续进行了深入 地、完备地、系统地研究，并取得了较为重大的研究成果。并将研究重心从结构化数据 与知识库的挖掘转向非结构化与半结构化数据的w e b 挖掘，其主要研究成果包括： 1 ) 构造了k d t i m ( k n o w l e d g ed i s c o v e r yt h e o r yb a s e do n i n n e rm e c h a n i s m ) 理论 2 ) w e b 挖掘研究与开发 3 ) 软件系统i c c k d s s 3 北京科技大学硕士学位论文 基于以上的成果，本论文的主要目的是以往研究w e b 挖掘过程中的特征提取和分 类算法进行改进，以提高w 曲挖掘的效率。 1 1 3 本文所做的工作及其意义 本论文的研究重点集中于基于w e b 文本挖掘技术的文本特征提取和分类算法，并 应用粗糙集优越的属性约减特性提取文本分类规则，对文本进行分类。其研究的意义 为：本论文深入地研究了w e b 文本挖掘这个新的应用领域，改进特征提取得方法，运 用粗糙集对文本进行分类。企业信息化是社会信息化非常重要的一方面，将基于w e b 文本挖掘技术的智能检索技术应用于企业信息化，能够给各种信息化系统一个新的思 路，更加充分地利用网络资源。随着网络技术的成熟、网络硬件基础平台的构建完毕及 各种基于w w w 的企业应用软件的开发，本课题的深入研究将会产生较大的社会效益 和经济效益。 本论文的研究工作主要集中针对复杂、海量的文本数据类型，研究适用于文本信息 抽取、应用的理论方法与挖掘技术。 综上所述，本论文的创新点主要为： 1 ) 改进了文本特征提取的方法，联合应用互信息和f 方法对文本进行特征提取。 2 ) 在应用粗糙集理论对文本的特征项进行属性约减，以提取分类规则对文本进行 分类。 4 北京科技人学硕士学位论文 2 w e b 挖掘综述 2 1w r e b 挖掘产生背景 随着w w w 的飞速发展，因特网网页的总数已经达到数十亿，在这些大量、异质 的w e b 信息资源中，蕴涵着具有巨大潜在价值的知识。人们迫切需要能够从w e b 上快 速、有效地发现资源和知识的工具。w e b 上的搜索引擎部分地解决了资源发现问题，但 由于精度( p r e c i s i o n ) 不高、召回率( r e c a l l ) 有限等原因，其效果远不能使人满意。 此外，搜索引擎的目的在于发现w e b 上的资源，不能针对特定的用户给出特殊的服 务。就w e b 上的知识发现而言，即使检索精度再高，搜索引擎也不能够胜任。为此， 我们需要开发比信息检索层次更高的新技术，传统的数据挖掘技术正应用到对w e b 的挖 掘当中，这也正成为人们研究的焦点。 w e b 挖掘指使用数据挖掘技术在w w w 数据中发现潜在的、有用的模式或信息。 w e b 挖掘是从数据挖掘发展而来，因此其定义和传统数据挖掘相类似。但是，w e b 挖 掘又有许多独特之处。现有的k d d 方法和d m 技术不能直接用于w e b 挖掘。从本质 上来说，w e b 挖掘可以被认为是数据挖掘技术在处理复杂数据类型上的一个扩展。目 前，对于w 曲挖掘的含义、功能等尚无统一的结论，需要国内外学者在理论上开展更 多的讨论以进行精确地定义。此外，w e b 挖掘系统的开发对其研究也起到很大的推进作 用。 w e b 挖掘与数据挖掘的区别 w e b 上的信息量随着因特网的飞速发展以惊人的速度增长，面对w e b 上海量、分 布、动态、异质、复杂、非结构化的丰富信息资源，用户如何从中查找、抽取自己想要 的数据和有用信息，由此产生了w e b 挖掘技术。w e b 挖掘就是从大量的w e b 文档和 w e b 活动中发现、抽取感兴趣的、潜在的有用模式和隐含的、事先未知的、潜在的信 息。它以数据挖掘、文本挖掘、多媒体挖掘为基础，并综合运用计算机网络、数据库与 数据仓库、人工智能、信息检索、信息提取、机器学习、统计学、概率理论、可视化、 计算机语言学、自然语言理解等多个领域的技术，将传统的数据挖掘技术与w e b 结合 起来。w e b 挖掘是对数据挖掘的一种新的发展和应用，但又不同于传统的数据挖掘。其 区别在于： w e b 挖掘的对象是海量、分布、动态、异质的w e b 文档，其信息存储不同于结构 化的数据库； - 5 北京科技大学硕士学位论文 w e b 在逻辑上是一个由文档节点和超链接构成的图，因此w e b 挖掘所得到的模式 可能是关于w e b 内容的，也可能是关于w e b 结构的； w e b 数据的半结构化或非结构化特征，使得这些信息数据难以清楚地用数据模型加 以表示，且缺乏机器可理解的语义，而数据挖掘的对象局限于数据库中的结构化数据， 并利用关系表等存储结构来发现知识。 有些数据挖掘技术并不适用于w e b 挖掘，即使可用也需要建立在对w e b 文档进 行预处理的基础上。因此w e b 挖掘需要用到更多的有别于传统数据挖掘的技术。 w e b 挖掘定义 w c ；b 挖掘是一项综合技术，涉及w e b 、数据挖掘、计算机语言学、信息学等多个 领域。不同研究者从自身的领域出发，对w e b 挖掘的含义有着不同的理解，项目开发 也各有其侧重点。例如，有些计算机语言学家认为，w e b 文档为自然语言理解提供了丰 富的语料，可以从中自动地学习词语的意义，以进行词义辨析或确定词语所属的概念。 我们从更为一般的角度出发，对w e b 挖掘作如下定义。 定义2 1w e b 挖掘是指从大量w e b 文档的集合c 中发现隐含的模式p 。如果将c 看作输入，将p 看作输出，那么w e b 挖掘的过程就是从输入到输出的一个映射 ： c 。p 。 w e b 挖掘从数据挖掘发展而来，因此其定义与我们熟知的数据挖掘定义相类似。因 此w e b 挖掘在部分方法和技术研究方面也与数据挖掘相似，具有相通之处。 w e b 挖掘分类 w e b 挖掘一般定义为：从与w w w 相关的资源和行为中抽取感兴趣的、有用的模 式和隐含信息。一般地，w 曲挖掘可以分为三类：内容挖掘( w e bc o n t e n t m i n i n g ) 、 结构挖掘( w e bs t r u c t u r em i n i n g ) 和使用挖掘( w e bu s a g em i n i n g ) ，其分类方式如图 2 1 所示： 6 北京科技大学硕士学位论文 图2 1 w e b 挖掘的分类图 w e bc o n t e n tm i n i n g ( w e b 内容挖掘) w e b 内容挖掘是从w 曲文档内容或其描述中进行挖掘，进而抽取知识的过程。 其中内容的挖掘从挖掘对象上来分又可以分为两类：其一，对于文本文档的挖掘( 包括 t e x t ，h t m l 等格式) 和多媒体文档( 包括i m a g e ，a u d i o ，v i d e o 等媒体类型) 的挖 掘。w e b 内容挖掘有两种策略：直接挖掘文档的内容，或在其它工具搜索的基础上进行 改进。采用第一种策略的有针对w e b 的查询语言w e b l o g ，w e b s q l 等，利用启发式 规则来寻找个人主页信息的a h o y ，等等。采用第二种策略的方法主要是对搜索引擎的 查询结果进行进一步的处理，得到更为精确和有用的信息。属于该类的有w e b s q l ，及 对搜索引擎的返回结果进行聚类的技术等等。 w e b u s a g em i n i n g ( w e b 访问信息挖掘) w e b 访问信息挖掘主要目标则是从w e b 的访问记录中抽取感兴趣的模式。w w w 中的每个服务器都保留了访问日志( w e b a c c e s s l o g ) ，记录了关于用户访问和交互的信 息。分析这些数据可以帮助理解用户的行为，从而改进站点的结构，或为用户提供个性 化服务。这方面的研究主要有两个方向：一般的访问模式追踪和个性化的使用记录追 踪。一般的访问模式通过分析使用记录来了解用户的访问模式和倾向，以改进站点的组 织结构。而个性化的使用记录追踪则倾向于分析单个用户的偏好，其目的是根据不同用 户的访问模式，为每个用户提供定制的站点。 w e bs m a c t u r em i n i n g ( w e b 结构挖掘) w e b 结构挖掘是从w w w 的组织结构和链接关系中推导知识。由于文档之间的互 连，w w w 能够提供除文档内容之外的有用信息。利用这些信息，可以对页面进行排 序，发现重要的页面。这方面的工作的代表有p a g e r a n k 和c l e v e r 。此外，在多层次 w e b 数据仓库( m l d b ) 中也利用了页面的链接结构。 7 北京科技大学硕士学位论文 2 2 w 曲文本挖掘概述 在上面提到了w e b 挖掘产生背景、概念以及分类，下面针对本人将要研究的方 向基于w e b 文本挖掘技术的智能检索系统原型进行深入地分析和探讨。通过国内 外大量文献资料地检索和查新发现，w e b 文本挖掘系统目前尚属学术前沿研究范畴。它 是一个多学科交叉的研究领域，涉及到数据挖掘、机器学习、模式识别、人工智能、统 计学、数据库、计算机语言学、计算机网络技术、信息学等多个领域。在这里将把文本 挖掘的方法和技术应用到w e b 研究领域，实现基于w e b 文本挖掘技术的智能检索系统 原型设计分类算法应用系统一体化的研究体系。 从上面对于w e b 挖掘的概述中可以知道，w e b 文本挖掘系统属于w 曲内容的挖 掘，是知识发现在复杂文本数据上的一种扩展；并且它与信息检索( 服) 和信息提取 ( ) 等自然语言理解的研究方向密切相关。 2 2 1w e ；b 文本挖掘的定义 w e b 文本挖掘是以计算语言学、统计数理分析为理论基础，结合机器学习和信息检 索技术，从大量的文本数据中发现和提取隐含的、事先未知的知识，最终形成用户可理 解的、有价值的信息和知识的过程。作为一个新的数据挖掘研究领域，目前尚无统一 的、确切的定义。内容挖掘多为基于文本信息的挖掘。由于文本挖掘的信息源越来越多 地来自于w e b 上分布的、异构的w e b 文档，例如，客户的电子邮件、公司内部网积累 的文档资料、专家撰写的技术白皮书及新闻、广告等信息。因此文本挖掘的研究范围拓 展到w w w 中，称为w e b 文本挖掘。随着网络世界的不断扩张，w e b 文本挖掘的适用 范围将更加广泛，应用前景也更加乐观。 从广义的研究角度出发，对w e b 文本挖掘可以作如下的定义： 定义2 2w e b 文本挖掘是指从大量非结构化、异构的w e b 文档的集合c 中发现有 效的、新颖的、潜在可用的及最终可理解的模式p 的非平凡过程。如果将c 看作输 入，将尸看作输出的话，那么w e b 文本挖掘的过程就是从输入到输出的一个映射6 c ，。 2 2 2w e b 文本挖掘的方法 在w e b 文本挖掘中，文本的特征表示是挖掘工作的基础，而文本分类和聚类是 两种最重要、最基本的挖掘功能。 1 ) 文本的特征表示 与数据库中的结构化数据相比，w e b 文档具有有限的结构，或者根本就没有结构。 即使具有一些结构，也是着重于格式，而非文档内容。不同类型文档的结构也不一致。 8 北京科技人学硕士学 奇论文 此外，文档的内容是人类所使用的自然语言，计算机很难处理其语义，文本信息源的这 些特殊性使得现有的数据挖掘技术无法直接应用于其上。我们需要对文本进行预处理， 抽取代表其特征的元数据。这些特征可以用结构化的形式保存，作为文档的中间表示形 式。 文本特征指的是关于文本的元数据，分为描述性特征，例如文本的名称、日期、大 小、类型等；以及语义性特征，例如文本的作者、机构、标题、内容等。描述性特征易 于获得，而语义性特征则较难得到。w 3 c 近来制定的x m l ，r d f 等规范提供了x 寸w e b 文档资源进行描述的语言和框架，在此基础上，我们可以从半结构化的w e b 文档中抽 取作者、机构等特征。对于内容这个难以表示的特征，我们首先要找到一种能够被计 算机所处理的表示方法。矢量空间模型( v s m ) 是近年来应用较多且效果较好的方法之 一o 2 ) 文本分类 文本分类是一种典型的有教师的机器学习问题，一般分为训练和分类两个阶段， 具体过程如下； 训练阶段： ( 1 ) 定义类别集合c = q ，g q ，这些类别可以是层次式的，也可以是并列 式的： ( 2 ) 给出训练文档集合s = 溉，墨 ，每个训练文档s 被标上所属的类别 标识： ( 3 ) 统计s 中所有文档的特征矢量矿忸j ) ，确定代表c 中每个类别的特征矢量 矿b j ； 分类阶段： ( 4 ) 对于测试文档集合r = 瓴，d k ，4 中的每个待分类文档或，计算其特 征矢量矿( 以) 与每个矿心) 之间的相似度曲”( 或，q ) ； ( 5 ) 选取相似度最大的一个类别作为或的类别； 有时也可以为以指定多个类别，只要或与这些类别之间的相似度超过某个预定的 阈值。如果以与所有类别的相似度均低于阂值，那么通常将该文档放在一边， 由用户 来做最终决定。对于类别与预定义类别不匹配的文档而言，这是合理的，也是必须的。 9 北京科技大学硕士学位论文 如果这种情况经常发生，则说明需要修改预定义类别，然后重新进行上述训练与分类过 程。 3 ) 文本聚类 文本聚类与分类的不同之处在于，聚类没有预先定义好的主题类别，它的目标是将 文档集合分成若干个簇，要求同一簇内文档内容的相似度尽可能地大，而不同簇问的相 似度尽可能地小。是一种典型的无教师的机器学习问题。目前的文本聚类方法大致可以 分为层次凝聚法和平面划分法两种类型。 对于给定的文档集合d = p i ，一，吐，屯) ，层次凝聚法的具体过程如下： ( 1 ) 将d 中的每个文档d i 看作是一个具有单个成员的簇q = 缸 ，这些簇构成了 d 的一个聚类c = k ，q ，气， ； ( 2 ) 计算c 中每对簇( q ，c ，) 之间的相似度s f m ( c ，c ，) ； ( 3 ) 选取具有最大相似度的簇，并将q 和c ，合并为一个新的簇c ，= c ，u f j 从而够成 了d 的一个新的聚类c = b ，c 。_ ； ( 4 ) 重复上述步骤，直至c 中剩下一个簇为止。 该过程构造出一棵生成树，其中包含了簇的层次信息，以及所有簇内和簇间的相似 度。层次聚类方法是最为常用的聚类方法，它能够生成层次化的嵌套簇，且准确度较高 但是，在每次合并时，需要全局地比较所有簇之间的相似度，并选择出最佳的两个簇， 因此运行速度较慢，不适合于大量文档的集合。 平面划分法与层次凝聚法的区别在于，它将文档集合水平地分割为若干个簇，而不 是生成层次化的嵌套簇。对于给定的文档集合d = 瓴，或，以 ，平面划分法的 具体过程如下： ( 1 ) 确定要生成的簇的数目k ； ( 2 ) 按照某种原则生成k 个聚类中心作为聚类的种子s = k ，5 ， ， ； ( 3 ) 对d 中的每个文档d ，依次计算它与各个种子s ，的相似度j 加( 一，j ，) ； ( 4 ) 选取具有最大相似度的种子t ，将4 归入以j ，为聚类中心的簇c ，从而得到d 的一个聚类c = h ，气 ； ( 5 ) 重复步骤( 2 ) 、( 3 ) 、( 4 ) 若干7 欠以得到较为稳定的聚类结果 该方法的运行速度较快，但是必须事先确定k 的取值，且种子选取的好坏对聚类结 果有较大影响 1 0 北京科技大学硕七学位论文 2 2 3w e b 文本挖掘工具的使用情况 目前，w d a 文本挖掘的主要应用方向为：文本分类系统，文本聚类系统、w e b 文 档中关联规则发现系统、文献资料的浏览导航系统、文摘自动生成系统及w e b 文档的 分布分析与趋势预测系统【1 5 1 。 目前国外流行的w 曲文本挖掘工具的使用情况如下图2 2 所示。 图2 , 2w e b 文本挖掘工具使用情况一览表 2 3 w 曲信息检索溉述 2 3 1w d o 信息检索的定义 从6 0 年代以来，信息检索领域在索引模型、文档内容表示、匹配策略等方面取得 了许多研究成果。这些成果被成功地应用在w e b 上，产生了搜索引擎，例如： y a h o o ! ，al t a 2 v i s t a 等。搜索引擎工作的一般流程包括：使用r o b o t 搜集w e b 文档、 对文档集合建立倒排索引、分析用户的查询请求、匹配文档与查询请求以计算二者之间 的相似度、对查询结果进行排序以及用户相关度回馈t “。 定义2 3 ：w d a 信息检索是指从大量w e b 文档的集合c 中找到与给定的查询请求 q 相关的、恰当数目的文档子集s 。w e b 信息检索的过程也对应于一个映射f ：( cq ) + s o 北京科技大学硕士学位论文 2 3 2 信息检索与w 西文本挖掘的区别 w e b 文本挖掘与传统的信息检索的联系与区别如下所示旧： 1 1 方法论不同。信息检索是目标驱动的，用户需要明确提出查询要求；而w e b 文 本挖掘系统是机会主义的，其结果独立于用户的信息需求，也就是用户无法预知的； 着眼点不同。信息检索着重于文档中显示存储的字词和链接；而w e b 文本挖掘 系统则试图更多地理解其内容和结构； 3 1 目的不同。信息检索的目的在于帮助用户发现资源，即从大量文档中找到满足 其查询请求的文档子集；而w e b 文本挖掘系统是为了揭示文档中隐含的知识； 4 ) 评价方法不同。信息检索使用精度( p r e c i s i o n ) 和召回率( r e c a l l ) 等指标来评 价其性能，要求返回尽可能多的相关文档，同时不相关的文档尽可能少。而w e b 文本 挖掘系统则在查全率与查准率的基础上还采用综合分类率( f 1 值) 、平均准确率 ( a v e r a g ea c c t w a f i o n ) 、收益( g a i n ) 、置信度( c e r t a i n t y ) 、简洁性( s i m p l i c i t y ) 等 来衡量发现知识的有效性、新颖性、可用性和可理解性； 5 ) 使用场合不同。有时信息检索系统返回太多的结果以致用户无法一一浏览，有 时用户没有明确的信息需求，有时用户希望发现文档集合中所具有的结构、趋势、含 义，在这些场合下，就需要使用w e b 文本挖掘技术。 尽管w e b 文本挖掘系统是比信息检索层次更高的技术，但它并不是用来取代信息 检索技术，两者是相辅相成的。一方面，这两种技术各有所长，有各自适用的场合；另 一个方面，我们可利用w e b 文本挖掘系统的研究成果来提高信息检索的精度和效率， 改善检索结果的组织，使得信息检索系统发展到一个新的水平。 2 - 3 3 基于w e b 文本挖掘的信息检索 传统的信息检索包括了基于关键字检索和全文检索【1 酊。但是随着i n t e r n e t 及i n w a n e t 的迅猛发展，尤其是w e b 的全球普及，使得w e b 上信息量( 尤其是基于文本的信息 量) 无比丰富，因此，单靠传统的网络信息检索工具将不再能够满足用户的需要。这主 要是由于传统的网络信息检索工具本身的局限性所造成的。例如：利用传统的网络信息 检索工具进行网上检索时，它的一般过程是：用户向系统提出查询条件( 像输入关键词 等) ，系统调用搜索引擎开始工作，然后把搜索结果提交给用户。现阶段，根据用户希 望查找的对象可分为两种：资源发现和信息提取。前者目的在于根据用户要求找出有关 的w e b 文档位置；后者则是能自动从有关文档中抽取出满足用户需要的信息( 信息提 取在一定程度上，融合了文本挖掘的思想和技术，可以看成是文本挖掘中文摘自动生成 系统的应用) f 1 9 。资源发现本质上是网上搜索，关键在于自动生成w e b 文档的索引。 1 2 北京科技大学硕士学位论文 典型的索引生成系统有w e b c r a w l e r 和a l t a v i s t a 等等，它们能对上百万数量的w e b 文 档进行索引，文档中的每个单词的倒排索引均保存起来，技术上类似全文检索。用户通 过输入关键词就能对所有建了索引的文档进行检索【ls 】。目前在用的索引系统有十几种， 例如：中文y a h o o ，英文y a h o o ，搜狐，b i gy e l l o w ，l y o o s ，w e b c r a w l e r 等。用户输 入同样的关键词在不同的索引下可能会得到不同的返回结果。通常，如果用户输入的关 键词比较普遍的话，用户往往会遇到返回成百上千个文档的情况。面对如此庞大数量的 文档，用户只能从头到尾对反馈的结果进行翻阅浏览，以便寻找出自己真正想要的内 容。然而，在这些反馈的结果中真正有用的文档往往只占全部文档的一小部分。这对于 经常需要处理大量文本信息的研究人员、信息咨询人员、调查人员等明显是不现实的。 而基于w e b 文本挖掘技术信息检索则可以用来解决这类问题，基于w e b 文本挖掘 技术的信息检索融合了文本挖掘的思想，并将单一的资源发现或者单一的信息提取的传 统的信息检索方法结合起来，从而达到在w w w 发现资源并将其中的信息提取出来进 行处理的目的。 2 4 小结 本章论文对w e b 挖掘、w e b 文本挖掘以及w e b 信息检索进行了较为全面、系统地 评述。在此基础上，详细地介绍了w e b 文本挖掘的描述性定义；然后评述了w 西文本 挖掘与信息检索的区别：并讨论了基于w e b 文本挖掘技术的信息检索的产生背景和基 本概念。 - 1 3 北京科技大学硕士学位论文 3 w e b 文本分类 从教育资源网、数字图书馆、数字博物馆和i n t e r n e t 网络信息源等均提供了海量的 w e b 文本信息，如何从海量的w 西信息中准确获取所需信息，己成为信息处理的一个 关键问题。为了帮助人们有效地使用这些资源和服务，陆续有一些功能强大的搜索引擎 问世了。这些搜索引擎在给人们带来很大便利的同时也暴露出搜索结果不能很好地满足 用户需求的问题。如何有效的将大量的w e b 信息文档分类，成为提高领域知识查准率 的一个关键问题。w 西文本分类技术可以缩减搜索空间，加快检索速度，提高查询精 度，因而受到了人们的广泛关注。 3 1w 曲文本分类 3 1 1w e b 文本分类定义 w e b 文本分类是指按照预先定义的分类体系，将待分类的w e b 文本测试集合中的 每个文本归入一个或多个类别中，是一种典型的有教师的机器学习问题。经过文本分类 处理，用户不但能够方便浏览文本，而且可以通过限制搜索范围来使文本的查找更为容 易。目前，y a h o o 仍然是通过人工对w 曲文档进行分类，这大大限制了其索引页面的 数目和覆盖范围，可以说研究w e b 文本分类有着广泛的商业前景和应用价值。 从数学角度来看，文本分类是一个映射的过程，它将未标明类别的文本映射到己有 的类别中，用数学公式表示如下：f ：a 专b 。其中，彳为待分类的文本集合，曰为分 类体系中的类别集合。 文本分类是系统根据训练集的样本数据信息总结分类规律并确定待分类文本的相关 类别。文本分类是处理海量文本的有效方法，它能提供文本集的良好组织结构，大大简 化文本的存取和操作，提高文本处理效率。文本分类在数字存储技术日益普及的今天， 应用的范围十分广泛，例如：数字图书馆、电子邮件分类、新闻分类、文本检索等等。 3 1 2w 西文本聚类 w e b 文本聚类与分类的不同在于，聚类没有预先定义的主题类别，是一种典型的无 教师的机器学习问题。它的目标是将文档集合分成若干簇，且同一簇内的文档相似度尽 可能大，聚类的结果可以用来指导分类。 3 1 3w e b 文本分类过程 对文本进行分类，不言而喻，首先应该有一个主题类别表，类别表的制定一般取决 于应用的需要，不同的应用场合有不同的分类要求。例如，大多数图书馆都有自己的主 题分类系统，例如在我国许多图书馆采用中图分类法中规定的类别对图书文献进行分类 1 4 北京科技大学硕士学位论文 管理。图( 3 1 ) 列出了中图分类法中有关自动化技术和计算机技术的部分主题类别。 大多数门户网站都会提供一个层级的类别系统，这个类别系统主要用来引导用户快速定 位有关文献。不同的门户网站提供的类别系统并不完全相同，但大同小异。如果用户希 望查阅旅游信息，就可在门户网站提供的旅游类文献中寻找，租赁房舍可到有关房地产 类的文本中寻找信息。一些特定的组织也有自己的主题分类系统，著名的国际通讯 处一一路透社曾经制定过新闻主题分类系统，并根据该分类系统对一定数量的新闻进行 了分类，而且这些数据已经被用于支持对自动分类的研究。 t p 自动化技术、计算机技术 t p l 自动化基础理论 t p ll 自动化系统理论 t p l 3 自动化控制理论 t p l 4 自动信息理论 t p l 5 自动模拟理论( 自动仿真理论) t p l 7 开关电路理论 t p l 8 人工智能理论 ，t p 2 自动化技术及设备 t p 3 计算技术及计算机技术 t p 4 射流技术( 流控技术) t p 6 遥感技术 t p 8 远动技术 图3 1 中图分类法片断 为对文本进行分类，首先要对文本进行分析，提取出文本中的区别性特征。一般 为，在类别不同的文本中，词的分布规律不同。可以想象，在计算机类的文本中，“芯 片”“菜单”“点击”这样的词的出现次数一般较多，而“停火”“武器扩散”这样的 词则会很少出现，这些用词规律是分类的一个重要依据。所以自动分类系统通常首先要 1 5 北京科技大学硕士学位论文 对文本进行分析，并把文本分析结果用一定的形式表示出来，该分析结果理论上不含和 分类无关的信息，可以认为是文本的一种抽象表示，分析过程通常称作数据表示模型 ( d a t ar e p r e s e n t a t i o nm o d e l ) 。常用的文档表示模型是向量空间模型，在向量空间模型 中，任何文本都最终被表示成一个n 维向量x 。 然而分类器是怎样工作的呢? 它如何决定一个文本的类别呢? 不同的分类器使用不 同的判别策略，为了便于理解，首先假定分类器是二元分类器，任务是判别输入文本是 否属于文本类c 。如果能够设计出成功的二元分类器，多元分类问题也就迎刃而解。首 先假定二元分类器在其内部使用了下面的线性计算公式： g ( 工) = w 工+ w o ( 3 1 ) 在该公式中，w 是一个n 维向量，是一个常数。石代表要进行分类的文本。把 ，- 、一 任何文本向量代入该公式，都会得到一个数值g t 。我们暂不讨论公式中的参数w 和 ，、 w 0 是如何得到的，但这两个参数应保证对于所有c 类文本，都可以得到一个的g c x ) ，、，_ 、 值，而对所有非c 类文本都可得到一个非正的g 【”值。如果g 叫具有这样的特性，分 类器的工作原理就相当简单了，对于任何一个文本，分类器利用上述公式进行计算，如 果g l 叫 o ，分类器就认为是一个c 类文本，否则就是非c 类文本。在文本分类的文献 中，上述公式或类似的判别模式( 也不可能不是公式) ，一般称作分类模型 ( c l a s s i f i c a t i o n m o d e l ) ，简而言之，分类器利用分类