（计算机应用技术专业论文）基于本体的web页面聚类挖掘.pdf

太原理l 大学硕士研究生学位论文 基于本体的w e b 页面聚类挖掘 摘要 随着互联网络的发展，w e b 页面的数量激增，人们需要对大量的文 本资源进行有效的组织，以有利于信息检索、模式发现、为用户提供推 荐服务，以及为进一步的分类提供模式基础，于是w e b 页面的聚类技术 成为一种迫切需要，针对传统聚类方法的不足，将领域本体引入聚类中， 实验验证，提高了聚类的效率，增强了结果的可解释性，大大节省了用 户查找信息的时间。 本文研究本体在w e b 页面中的聚类挖掘。本体作为领域模型，提供 了人们对领域概念和概念层次的共同理解，同时其应用降低了对自然语 言理解技术的依赖。本文主要的工作和成果如下： 提出了一种基于本体的文本表示模型。针对传统模型中的不足，通 过引入本体，能更好的表示文档集合的特征。 提出了一种基于本体的聚类算法，通过利用本体提供的领域知识， 有效地解决传统方法中参数确定和结果可解释性等问题。 构建了一个基于本体的w e b 页面聚类挖掘系统，原型系统通过结合 领域本体的优势，在一个引擎的环境下对返回的页面进行聚类，实验验 证，这样有效地减少了用户寻找信息的时间，同时增强了聚类结果可解 释性。 太原理工大学硕士研究生学位论文 关键字：本体，文本聚类，语义度量，空间向量模型，k - m e a n s 太原理工大学硕士研究生学位论文 o n t o l o g y - b a s e dw e bp a g e s c l u s t e r i n gm i n i n g a b s t r a c t w k ht h ed e v e l o p m e n to fi n t e r n e tt e c h n o l o g y , p r o c e s s i n gd o c u m e n tb y h a n dn o l o n g e r m a t c h e st h e i n c r e a s i n gs p e e d a n dm e e t s p e o p l e s r e q u i r e m e n t s w h a tp e o p l en e e di so r g a n i z i n gd o c u m e n t si na ne f f e c t i v ef o r m ， f o rt h ec o n v e n i e n c eo fi n f o r m a t i o n r e t r i e v e ，p a t t e r nd i s c o v e r y a n d r e c o m m e n d a t i o n ，a n da l s of o rp u r p o s eo fp r e p a r i n gf o rc a t e g o r i z i n gt h en e w c o m i n gd o c u m e n t s ，s ow e bp a g e sc l u s t e r i n gb e c o m ev e r yi m p o r t a n t t h i sp a p e ri sm a i n l yr e s e a r c hc l u s t e r i n gm i n i n go fw e bp a g e sb a s e do n o n t o l o g y o n t o l o g ya sa d o m a i nm o d e l ，i tp r o v i d e su sac o m m o nu n d e r s t a n d t od o m a i nc o n c e p ta n dc o n c e p tl e v e l a tt h es a m et i m e ，t h ea p p l i c a t i o no f o n t o l o g yg r e a t l yd e c r e a s e st h er e l i a b i l i t yt ou n d e r s t a n do fn l pt e c h n o l o g y t h em a i nc o n t r i b u t i o n sa n di n n o v a t i o n so ft h i sd i s s e r t a t i o na r ea sf o l l o w s ： w ep r e s e n tan e wt e x tp r e s e n t a t i o nm o d e lb a s e do no n t o l o g y t h e c h a r a c t e ro ft e x ts e tc a np r e s e n tm o r ef i tt h o u g ho n t o l o g y w ed e s i g na c l u s t e r i n gs y s t e mo fw e bp a g e sb a s e do no n t o l o g y t h e s y s t e mu s e t h ea d v a n t a g e o u so fd o m a i no n t o l o g y , i td e c r e a s e st h et i m eo ft h e t i i 太原理f ：人学硕十研究生学位论文 p e o p l ef i n dt h ei n f o r m a t i o nw h e nt h e yl o o kf o rt h ep a g e ，t h r o u g hc l u s t e r i n g t h ew e bp a g e st h a tr e t u r n e di nas e a r c he n g i n e a tl a s t ，ar e s u l to f e x p l a i n a b l e c l u s t e r i n gi sr e t u r nt oe n d i n gu s e r s k e y w o r d s ：o n t o l o g y , t e x tm i n i n g ，s e m a n t i cm e a s u r e ，v s m ，k - m e a n s i v 声明 本人郑重声明：所呈交的学位论文。是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均己在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名： 、 葛乏小彳犀 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定。其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) o 签名一垫! 坠日期：剥川 导师签名：日期：翌 ：! ：! ! 太原理工大学硕士研究生学位论文 1 1 课题的背景和意义 第一章绪论 随着互联网络的发展，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 文本聚类挖掘的 结合必定会成为一项研究热点。 1 2 领域研究的现状 1 2 1 文本聚类的研究现状 文本聚类是在传统的聚类分析的基础上发展的，但是传统的聚类方法效果并不 十分理想，文本数据是半结构数据，这使得基于数据库的许多算法都不适用文本聚 类。文本聚类在如何将文本内容表示成在数学上可分析处理的形式方面，s a l t o n 教 授提出了向量空间模型( v e c t o rs p a c em o d e l ，v s m ) “1 ，v s m 通过将文档集合表示成高 维空间的一个向量，这样便于利用各种数学工具对其进行处理。但由于空间向量模 型表示方法构建的向量维度非常高，采用距离尺度的传统聚类算法很难取得令人满 意的聚类效果，这样许多的方法应用起来，如p c a ( p i n c i p a lc o m p o n e n ta n a l y s i s ) 、 l s i ( l a t e n ts e m a n t i ci n d e x i n g ) 、c i ( c o n c e p ti n d e x i n g ) 、s o f m ( k o h o n e n s e l f - o r g a n i z i n gf e a t u r em a p ) 和帅s ( m u l t i d i m e n s i o n a ls c a l i n g ) 等。在具体的 聚类方法方面，有基于层次的、基于分割的、基于密度的和基于网格的聚类算法等， 算法方面许多学者做了大量的工作，如在基于k - m e a n s 算法的改进文本聚类算法的 研究方面，r a y m o n dt m 和k o l l i c sg m 通过随机选择样本建立中心点来优化大规模 文档的聚类；针对大规模数据流数据( 包括文档) 的聚类，s u d i p t og “1 和j e s s i c al ” 采用统计信息来处理，这些改进都取得比较好的效果。在文本聚类的应用研究方面， 也有很多的例子，如文本知识发现搜索器可以使用聚类挖掘搜索结果的结构；文本 聚类可以将w e b 的搜索结果组织成主题层次树，让浏览文本集和寻找兴趣点变得容 易嘲：应用在w e b 挖掘中改善网络搜索性能“，采用有监督聚类改进文本分类技术 等。 2 太原理工大学硕士研究生学位论文 1 2 2 本体的研究现状 随着s e m a n t i cw e b 的发展，作为s e m a n t i cw e b 的主要技术o n t o l o g y ，也受到越 来越多的人关注。因为o n t o l o g y 具有良好的概念结构和对逻辑推理的支持，在知识 检索中有了广泛应用，如项目o n t o b r o k e r ，在项目中主要利用o n t o l o g y 怎样更好的 去发现用户所关心的内容，还有s k c ，在其中主要解决信息系统语义异构的问题，实 现异构自治系统问的互操作，希望通过在o n t o l o g y 上的一个代数系统来实现 o n t o l o g y 之间的互操作，从而实现异构系统之间的互操作。为了便于在w e b 上应用 程序使用，需要有个通用的o n t o l o g y ，这样出现了一些表示的语言，如r d f s 、o i l 、 o w l 等9 1 。o w l 是目前最新的w e bo n t o l o g y 语言标准，于2 0 0 4 年2 月1 0 号正式成为 w 3 c 的推荐标准。 1 3 课题研究的主要内容 1 3 1 文本聚类 文本聚类是一种典型的无指导机器学习问题，它把一个文档集分割成不同的类 组，使得在同一组里的文档描述同一个主题，组里的文档尽可能相似，不同组之间 尽可能不同。在本课题中主要研究空间向量模型，同时研究将传统的聚类方法用在 文本聚类上的一些问题。 1 3 2 本体 本体是一种对共享概念模型的明确的形式化规范说明。本体方面在课题中涉及 到通过工具j e n a 将用o w l 表示的本体进行解析；将用户的查询匹配到领域本体上得 到一个背景知识，这个背景知识帮助聚类参数的确定，同时为后阶段结果展示服务。 1 4 本文的组织安排 本文在文本聚类的基础上结合领域本体，通过将用户查询匹配到一个领域本体 太原理工大学硕士研究生学位论文 上得到一个信息，作为后阶段文本聚类处理时的背景知识，最后实现了一个简单系 统论证了其可行性。 第一章绪论，主要分析课题的背景和课题的意义，以及本领域当前国内外研究 的现状。 第二章主要介绍课题当中涉及到的两个领域。文本聚类方面重要分析了当前的 一些经典的文本表示模型，然后对一些文本聚类的算法进行了分析；本体方面主要 是课题当中涉及到的本体的解析和本体的匹配问题。 第三章是本文的核心，主要提出了一个新的模型，然后具体讲怎样在课题当中 应用本体，结合本体来对w e b 页面进行表示和聚类方法的具体实现。 第四章是实验部分，在这部分主要对传统方法和结合本体后的新方法的对比实 验和分析。 第五章主要介绍一个简单实验系统的设计和实现过程。 第六章主要是本文总结和贡献的一个概要，然后提出了进一步以后的研究方向。 4 太原理工大学硕士研究生学位论文 2 1 文本聚类挖掘 第二章文本聚类挖掘与本体 传统的聚类研究主要针对结构化的数据，而文本聚类是一种有效的文本挖掘方 法，能从大量的文本数据中发现潜在的知识和规律，是一个知识获取技术，也是一 种文本处理过程。文本聚类的一般过程可以用下图2 - 1 表示： 图2 - 1 文本聚类 f i g2 - 1t e x tc l u s t e r i n g 1 ) 数据准备 针对聚类的目标收集、整理原始文档集，为后阶段的处理提供数据源。 2 ) 特征的建立 因为文本是非结构化的，在进行处理前，必须把要处理的文档集表示成能处理 的数学模型，在一般的情况下，一般通过将文本解析，将文档集表示成空间向量的 模型。 3 ) 特征集缩减 一般将文档表示为特征向量，由于文档的特性，这个向量比较大，不好处理， 需要通过一些方法将向量降维，方便进一步处理。 4 ) 模式提取 对特征向量降维的基础上，运用聚类的方法，将文档集自动的分类，得到分类 的模式。 5 太原理工大学颐卜研究生学位论文 5 ) 模式评价 在上阶段得到模式后，要评估这个模式是否满意，如果不行，必须返回前面阶 段重新进行处理。 2 1 1 自动分词技术 自动分词是指按照特定规范，在中文文本中连续的对能够代表语义单元的词或 者1 7 元词条间加入分隔符。它是各种中文信息处理技术的基础，也是中西文之间研 究文本自动分类的主要差异所在。如何把文章切分为词条，并从中提取特征词条构 成特征向量已经成为文本处理的关键。 经验证明：要想建立一个好的分词系统，关键是选择一个好的自动分词算法和 建立一个好的分词词库。目前，自动分词算法大致可分为三大类：基于词库的分词 方法、基于统计的分词方法和基于理解的切分方法。 1 基于词库的分词方法 基于词库的分词方法是目前最常使用的、简单有效的方法，它是按照一定策略 将待分析的汉字串与一个“充分大的”机器词典中的词条进行匹配，若在词典中找 到某个字符串，则匹配成功( 识别出一个词) 。常用的基于词库的分词方法有最大匹 配法、逆向最大匹配法、逐词遍历法“”。此方法的优点是使用了我们所熟知的一般 词法知识，对中文有一定了解的人很容易判别其正确性。词库具有通用性，但有一 个前提条件，就是该方法要求有一个较全词库，事实上，做到这一点很难。 此外，该方法无法正确切分出词表中未及时收录的新词，不具备自适应性是其 一个弱势。实际使用的分词系统，都是把基于词典的分词方法作为一种最初切分手 段，还需要通过利用其它各种语言信息来进一步提高切分的准确率。 2 基于统计的分词方法 在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词，所以字 与字相邻共现的频率或概率能够较好地反映成词的可信度“”。定义两个字的互现信 息为： m ( x ，l ，) 一1 0 9 下篇特 公式( 2 1 ) 6 太原理工大学硕士研究生学位论文 其中尸( zj ) 是汉字氨y 的相邻共现概率，尸( 肋、尸( 分别是瓜j ，在语料中出现 的概率。互现信息体现了汉字之间组合关系的紧密程度，当紧密程度高于某一个阙 值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行 统计，不需要切分词典，因而又叫无词典分词法或统计取词方法。但这种方法经常 会抽出一些共现频度高、但并不是词的常用字组，例如“之一”、“我的”、“有的” 等，并且对常用词的识别精度差，时空开销大。 3 基于理解的切分方法 针对以上方法的不足，人们提出了理解式切分方法。这样的分词系统由词库、 知识库和推理机三部分组成。词库中存放词条；知识库中存放已经形式化的各种语 法规则、语法知识，以及语言学家在分词过程中进行推理判断的经验知识；推理机 制利用词库和知识库提供的大量数据与知识，模拟语言学家的逻辑思维过程，实现 自动分词。这种分词方法需要使用大量语言知识和信息，但由于汉语语言知识的笼 统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此目前基于理 解的分词系统还处在试验阶段。 2 1 2 特征表示与提取 1 项的选择 项可以是文本中的各种语言单位，对中文来说有字、词、短语，甚至是句子或 旬群等更高单位。项也可以是相应词语或者短语的语义概念类。因此，项的选择只 能由处理速度、精度、存储空间等方面的具体要求来决定。选出的项越具代表性， 语言层次越高，所包含的信息就越丰富，但是分析的代价就越大，而且受分析精度 的影响就越大。由于词汇是文本最基本的表示项，在文本中的出现频度较高，呈现 一定的统计规律，再考虑到处理大规模真实文本所面临的困难，选择词或者短语作 为特征项是比较合理的“”。但是直接选用文本中的词或者词组作为文本特征项也会 存在以下问题： 1 ) 文本中存在一些没有实际意义但使用频率很高的虚词和功能词。如中文中的 “的”、“了”、“把”等，常常把一些真正有分类作用的实词淹没掉。解决这个问题 7 太原理工大学硕士研究生学位论文 的方法是把这些词组织成一个停用词表，把表中的词从特征集中滤掉。此外，还可 以在文本预处理时进行词性标注，从词汇特征集中滤去那些对区别特征贡献极小的 大部分虚词和功能词。 2 ) 一词多义或词汇变形问题。事实上，自然语言有着极为丰富的语言现象。例 如词汇之间的关系，就有同义关系、近义关系、关联关系等。另外词汇的歧义也很 普遍，例如“她高兴地走了”( 副词“地”应是停用词) ，“地很平”( 名词“地”不 应作为停用词) 。因此，不同的词义当作不同的项来看待会更合理。 2 特征提取方法 词、词组和短语是组成文本的基本元素，并且在不同内容的文本中，各词条出 现频率有一定规律性，不同的特征词条就可以区分不同内容的文本。因此我们可以 抽取一些特征词条构成特征向量，用这个特征向量来表示w e b 文本。一个有效的特 征词条集，必须具备以下三个特征： 1 ) 完全性：特征词条能够确实表示目标内容； 2 ) 区分性：根据特征向量，能将目标同其他文本相区分； 3 ) 精练性：特征向量的维数应该尽可能小。 用分词算法或词频统计方法得到的特征项来表示文本，向量维数非常巨大，这 种未经处理的文本矢量给后续处理工作带来巨大的计算开销，使整个处理过程的效 率非常低下。因此，我们必须对文本向量做进一步净化处理，在保证原文含义的基 础上，找出对文本特征类别最具代表性的文本特征，提取的特征也称为二次特征。 有研究证明，在经过特征压缩后的特征空间中进行文本分类不但不会降低分类系统 的分类性能，而且会有助于提高分类精度。 统计学、模式识别和机器学习中都有许多特征抽取方法，但是面对超高维的原 始文本特征集时变得不再适用。目前，在对文本特征进行抽取时，常采用特征独立 性假设来简化特征选择过程，达到计算时间和计算质量之间的折衷。一般做法是采 用某种评估函数对每个文本特征独立进行打分，然后把特征按分值高低排列，通过 设置特征阀值来选择预定数目的最佳特征作为文本特征子集。在文本分类中得到应 用的特征抽取评估函数主要有：文本频数、信息增益、期望交叉熵、互信息、z2 统 8 太原理工大学硕士研究生学位论文 w e b 网页是采用超文本标记语言编写的、半结构化的文本文件，其所含信息 体现在三个部分：网页正文、网页所含的超文本标记、网页间的超连接。 对网页进行特征提取首先要对超文本进行网页过滤，过滤处理后分别获得网 页正文、超文本标记，超链接信息。此时，网页正文与普通文本基本一样，对它 的处理可转化为中文文本处理。 标记的作用是提供有关文本结构的信息( 如标题、头部和段落等) 和格式( 如 粗体和斜体等) 。h t m l 中有很多标记，它们标示的文字往往对揭示网页的主题内 容具有更加重要作用。所以在网页特征提取时，统计这些标记中的特征词条和出 现次数，为它们赋予较大权重。对标记信息的统计，既有效利用了标记对关键词 重要程度的标示作用，又对网页的理解增加了准确尺度。超链接所包含的信息有： ( 1 ) u r l 字符串中的字符信息； ( 2 ) 链接文本( 链接标记 和 间的文字信息； ( 3 ) 链接所引入的超文本文件内容间的相关性。 超链接包括同一网页内部的相互链接和网页间的相互链接。网页间的相互链接 又可以细分为与文本文件的链接、与图片的链接、与声音文件的链接、与程序的链 接、与数据库的链接等等。超链接虽然引入了网页内容间的相关性，但这种相关性 是不确定的。即相链接的网页间内容上可能相关，也可能无关。比如出于商业的目 的，许多网站上链接了与其内容无关的电子广告。 考虑到超链接信息的不确定性和所有的数据特点，本模型对网页的特征提取来 自正文和标记信息。 4 特征项权重计算 在确定了原始特征项，并通过特征提取算法得到了二次特征之后，另一个很重 要问题就是特征项的权重问题。目前最普遍的赋权重方法是运用统计方法，即用文 本的统计信息，主要是词频，来计算特征项权重。被广泛应用的权重计算公式t f i d f 公式： 矿n2 矿t + f d 厂i i 公式( 2 6 ) t f , r z e r mf r e q u e n c y ) 表示项“在文本口中的文本频度，礤( i n v e r s ed o c u m e n t i o 太原理工大学硕士研究生学位论文 计法、文本证据权、优势率等。下面列出了几种重要方法在w e b 上进行文本挖掘时 所采用的数学表示“”。 1 信息增益( i n f o r m a t i o ng a i n ) 信息增益常被应用于机器学习领域中，它通过文本特征在文本中出现与不出现 的情况来推算该特征的信息量。 h f g a i n ( ，) _ 肌) 军p ( c 小) l o g 等州- ) ；，( c ，向o g 等馘但q 2 期望交叉熵( e x p e c t e dc r o s se n t r o p y ) c r o s s e n t 珥t x t ( t ) 训莩唰f ) l o g 号等 公式q 。3 它与信心增益唯一的不同之处在于没有考虑单词未发生情况。 3 互信息( m u t u a li n f o r m a t i o n ) m u t u a u n f o t x t ( t ) = 军( c , ) l o g 等 馘q 。4 它与期望交叉熵的本质不同在于它没有考虑单词发生频度，这是互信息一个很大 的缺点，因为它造成了互信息评估函数经常倾向于选择稀有单词。 4 z2 统计法( c h i ) 在现有的测试集上，彳用来表示特征t 和类c 同时发生的次数；口表示特征 t 发生而类c 不发生的次数；f 表示特征t 不发生而类c 发生的次数；刀表示特 征t 和类c 同时不发生的次数；n 是文本集总数；则特征t 和类c 之间的值z2 就 可以计算为： zl ( i ，c ) 。( _ 可可罟名罴再￥暑丌再而 公式2 5 在这几种特征选择方法中，信息增益的缺点在于考虑特征未发生情况，互信 息的缺点在于没有考虑特征出现频繁程度尸( 幻因子，以致倾向于稀有单词：期 望交叉熵克服了两者的缺点，所以效果比它们都好。 本模型以上述评价函数公式为依据，通过测试比较，选出适合该系统的最优 方法，以便获取好的分类性能。经过验证我们发现，对于我们的数据，期望交叉 熵效果最好，因此，本模型采用期望交叉熵作为提取依据。 3 特征词条的取得 9 太原8 2 - 大学硕士研究生学位论文 f r e q u e n c y ) 表示项“的反比文本频数，它们有多种计算方法，较为常用的公式是： w 。：t f 。l o g ( 旦+ 0 0 1 ) 公式( 2 7 ) 其中班表示项“在文本中历中出现的次数，表示总文本数，7 * 表示训练文本中出现 “的文本数。我们可以这样理解向量空间中的每个分量：每个分量刻画了项“区分文 本内容属性的能力，一个项在文本集中出现范围越广，说明它区分文本内容属性的能 力越低；在一个特定文本中出现频度越高，说明它在区分该文本内容属性方面的能 力越强。 考虑到文本长度对权重的影响，还应该对项权重公式做归一处理，将各项权重 规范到 0 ，1 之间。另外，标题、副标题和关键字表中出现的词汇和短语，在设置权 重时应单独考虑，使其具有较高权重。多年实验表明，t f i d f 是文本处理的一个有效 工具。事实上，这一公式不仅在信息检索中得到了成功应用，它对其他文本处理领 域，如信息分发、信息过滤和文本分类也有很好的借鉴意义。本文研究的文本自动 分类系统也是以它作为文本特征权重。 2 1 3 文本的表示模型 数据挖掘用于发现大量数据中所蕴含的知识或者是规则，这种发现是建立在数 据表示之上的，也就是说在建立了正确的数据表示以后，才能利用各种方法来对数 据潜在的信息进行挖掘，所以构造恰当的，并且是适用于当前数据分析的数据表示 形式显得尤为重要。 在前面已经提到了关于文本的向量表示，它是一种文本数据的表示形式，它能 够很好的反映文本集合中某个词与包含该词的文本的关系，通常把这种反映整个数 据集中某一个部分或者个体的表示称为模式( p a t t e r n ) 。但是这种描述只是局限于数 据的局部，只能反映个体数据的情况，不能从全局出发考虑整个数据集合的结构， 而在对数据进行分析处理的过程中，不仅仅要从局部出发，更多的时候还需要从全 局的角度来进行研究，这个时候就需要建立能够反映数据整体结构的“模型” ( m o d e l ) “。所以一般可以将数据的描述分为两种：一种是全局的模型( m o d e l ) ，一 种是局部的模式( p a t t e r n ) 。 太原理工大学硕士研究生学位论文 这里把模型定义为对数据集的全局性总结，它对整个测量空间的每一个点做出 全局性的描述。例如，如果把数据矩阵的各行看作p 维向量( 也就是p 维空间中的 点) ，那么模型可以对这个空间中的每一点( 也就是所有对象) 做出描述。通过对于这 种全局性表示进行分析，可以把一个点分配到一个聚类或者预测出某一个模型变量 的值。模型是对一个数据集的高层次、全局性的表示，它能通过一个很大的样本透 视总体。模型可以是描述性的以方便简捷的方式归纳数据；也可以是推理性的， 允许对数据所在的数据总体或者未来数据做出某种判断。 一个简单的模型可以表示成这样：j ，= a x 叼，其中j ，和j 是变量，a 和c 是 模型中的参数，通过这个模型可以看出，它重点描绘的并不是某一个数据部分，而 是对整个数据空间做出了一个表示，所有符合上面模型的数据，都要落在模型描述 的空间中“”。当然这只是一个比较简单的模型，在实际的应用中，一般使用的模型 要更为复杂。但是这个简单的例子已经足够用来了解模型的基本含义。 在这个模型表述了变量j ，与j 之间的关系，其中的a 和c 通常称之为参数，在 实际的使用中经常用口来表示一般参数或者一系列参数的向量。此实例中，口 = a ，c 。在给定的模型形式或者结构以后，接下来的任务就是通过估计为模型选择 适合的参数值，也就是选择一个适合的评分函数来衡量模型与数据之间的拟合情况， 然后通过最小化或者最大化为该函数选择合适的参数，关于这方面的技术将在后面 的文章中加以介绍。然而，在估计模型的参数之前，必须首先为模型本身选择一个 合适的函数形式。 为了便于计算机处理，需要将文本转换为计算机可以识别的格式。根据“贝叶 斯假设”，假定文本中的字或词在确定文本类别的作用上相互独立，这样就使用文 本中出现的字或词的集合来代表文本，这样丢失了大量的文章内容方面的信息，但 这种假设可以使文本的表示和处理形式化，并且在应用中证明有好的效果。 在信息检索的概念提出后，出现了许多基于文档和查询之间的文本计算模型， 代表性的有布尔模型( b o o l e a nm o d e l ) ，概率模型( p r o b a b i l i s t i cm o d e l ) 和空间 向量模型( v e c t o rs p a c em o d e l ，简称v s m ) 等“”。这些方法从不同的角度出发， 使用不同的方法处理特权加权、类别学习和相似度的计算问题，下面是这几个模型 的简单介绍。 1 2 太原理工大学硕士研究生学位论文 1 布尔模型 布尔模型是采用布尔表达式对文本进行标识。布尔模型在传统的信息检索中有 广泛的应用。它通过与用户给出的检索式进行逻辑比较来检索文档，是一种基于关 键字的匹配。在标准的布尔模型中，文档采用如下的表达形式： d f = ( 正- ，d z ，d 3 ，d 0 公式( 2 - 8 ) 其中，n 为特征项的个数，以为o 或1 ，分别表示特征项j 在文档k 中出现与否。 在传统的信息检索中，用户表达式是把用户给出的检索词用布尔运算符“八” ( a n d ) ，“v ”( o r ) 连接起来的式子。设文本集 d = 似t ，d ：，d ，正) 公式( 2 9 ) a i 矗：_ l z ，为文档集中某一文档，又设乃= 矗。厶t a , j 为a i 的标引词集，则 对于形如 q = 形一 。 a w , 公式( 2 1 0 ) 的检索式，如果彤乃，彤乃，孵乃，厣；乃，则0 i 检索到的文本，我们称西为 命中文档，否则口i 为不命中文档，而对于形如： 9 = w , v w , v w , v v w , 公式( 2 1 1 ) 的检索式，如果至少存在某个成乃( 肛l ，2 ，3 ，d ，则西为命中文档，否则西为不 命中文档。 实现布尔检索，首先要对文本集中的每个文档进行标识，标引词可以采用关键 字、自由词、作者、篇名等能反映文档特征的词，其次，要对文档进行合理组织， 建立文档的索引，通常把文档组织成倒排文档结构，就是把某标引词有关的所有文 档的号数通过索引集中在一起，当通过该标引词查找文档时，可以立即找到文档所 在的位置，从而检索到文档。布尔检索具有简单，易理解，实现时速度快的优点， 故在许多检索系统中得到应用。虽然布尔检索有着许多优点，但也存在许多缺点： 检索结果无法按用户定义的重要性排序，用户需要浏览所有结果才能找到最 合适自己需要的文档。 1 3 太原理工大学硕士研究生学位论文 匹配标准存在不合理的地方。如：在“八”时将含有一个或多个但非全部检 索词的文档看作与不含任何检索词的文档排除。 布尔逻辑式的构造不能全面反映用户的需求。 针对这些缺点，人们对布尔检索理论进行了改造，如将标引词加权，权值大小 反映词在文档中的重要程度，称为扩展布尔模型。 2 概率模型 概率模型是于1 9 7 6 年由r o b e r s t o n 和s p a r c kj o n e s 提出，也即后来有名的二 值独立检索( b i n a r yi n d e p e n d e n tr e t r i e v a l ，b i r ) 模型。概率模型试图在概率的 框架下解决信息检索问题，是基于查询词在相关和非相关文献中的分布概率的，其 基本思想就是根据关键词在相关文档中出现的概率和无关文档中出现概率来判断该 关键词的权重。其计算公式如下： w v = l o g ( r r r ) g ( n r ) ( n 一”一r + ，) ) 】 公式( 2 1 2 ) 其中，野是索引词在查询- ，中的权重，r 是查询所得到的相关文献中包含 索引词j 的文献数量，刀是与查询- ，相关的文献总数，力是用于检索的所有文献中 包含索引词j 的文献数量，是文献总集包含的文献数目。 相关反馈机制的研究表明：利用少量相关文献计算调整索引词权重可以促使检 索性能显著改进，在此方法中就采用i d f 度量，这表明概率模型对于相关反馈中调 整词权这一方面是很有用的。索引词的权重计算公式如下： w e i g h t , = ( 1 0 9z ( f r e q - + 1 ) x 1 d f , ) l o g , m , 公式( 2 1 3 ) 其中w e i g h t , k 是索引词f 在文献k 中的权重，f r e q ，k 是词，在文献k 中的出现频 率，版是文献中的词的总量。 i d f , = l o g ：( n u m d 一) + l 公式( 2 1 4 ) 其中是文档集合的文档总数， t 胧易是文档集合中包含索引词f 的文献总数。 以上描述了仅对用户给出的查询词的重新加权算法，另一种较为复杂的做法是对查 询进行扩展。 概率模型的主要优点在于：从理论上讲，文档根据它们相关的概率按递减的顺 序排列。其缺点是： 太原理工大学硕士研究生学伊论文 需要最初把文档分成相关的集合和不相关的集合。 这种方法并不考虑标引词在文献中出现的频率，即所有的权值都是二值的。 假设标引词相互独立。然而，如同向量模型一样，并不能明确标引词的独立 性在实际情况中是否是一个不利的假设。 3 空间向量模型 向量空间模型( v e c t o rs p a c em o d e l ，简写为v s m ) 由s a l t o n 等人于2 0 世纪 6 0 年代末提出，是一种简便而高效的文本表示模型，其理论基础是代数学。与布尔 模型不同，向量空间模型把用户的查询要求和数据库文档信息表示成由检索项构成 的向量空间中的点。而通过计算向量之间的距离来判定文档和查询之间的相似程度。 然后，根据相似程度排列查询结果。向量空间模型的关键在于特征向量的选取和特 征向量的权值计算两个部分。用向量空间模型计算向量距离时，一般采用向量的夹 角余弦来表示，两个文档之间相同的词越多且这些词的权重越高，则其距离越近“”， 计算权重的目的是要正确突出每个索引项在文章中的重要程度，一般来讲，某个词 在某文本中经常出现且在其他文本中不常出现，就说明该词对该文本或该类文本更 具有代表性，应具有更高的权重。另一方面，如果一个索引项在很多文档中都出现， 那么这个索引项不能很好地代表某一类文档，权重就较小。v s m 的一些基本概念如 下： 文档( d o c u m e n t ) ：泛指一般的文档或文档片断。 特征项( t e r m ) ：当文档的内容被简单看成是基本语言单位集合时，这些基本 的语言单位被称为特征项，即文档可用项集来表示为口( “如如，妨，其 中t l 是第f 个特征项，l j 。 特征项权值( t e r mw e i g h t ) ：对于含有力个项的文档口( “t 2 ，0 ，特 征项t ，常被赋以一定的权重形来表示它在文档中的重 要程度，即口= ( ， ，“； ) ，也可以简记为口 = l w l w e # ) ， v s m ：给定一个文档d = ( ， ， ) ，可以将t ，坛t n 看成是一个n 维的坐标系，而彤，以形为相应的坐标值，因而 口( 彤，鼢可以看成是力维空间中的一个向量。我们称( 彤，助 1 5 太原理工大学硕士研究生学位论文 为文档d 的向量表示。 向量空间模型最主要的优点在于： 该模型的权重计算方法能够提高系统的检索性能： 模型中使用的部分匹配方法能检索出与用户的查询输入条件“近似”的文 档； 在模型中用余弦方法进行距离度量，因此可以根据检索出的结果与查询条件 的相关程度对结果进行排序。 向量空间模型也有缺点。在该模型中有一个假定：所有的索引项之间是相互独 立的，在权重计算公式中就没有考虑索引项之间的相互关系，但人们发现，在实践 中，这些检索项的相互依赖性对系统的性能将造成影响。因为在某些文档中，很多 索引项都是相互依赖的，如果将它们不加选择地应用于语料库所有的文档中，必将 损害系统的性能。 2 1 4 常用的文本聚类算法 聚类在本质上是一种通过对对象集合按照某种规则进行划分或覆盖从而发现隐 含的潜在有用的信息的一种知识发现的方法。文本聚类是对文本数据集合进行聚类 分析的过程。在文本聚类的过程中使用的方法，从本质上讲，和前面提到的聚类分 析中的方法并没有什么区别。但是，由于文本聚类分析中所处理的文本数据从结构 上有一定的特殊性，所以使用的聚类方法同处理普通结构化数据的方法又有很大的 不同。文本聚类是一个典型的无监督的机器学习问题，文档集合作为一种特殊的对象 集合，它拥有适合自身特征的聚类算法：层次聚类法、平面划分法、简单贝叶斯法 和神经网络聚类方法等。 1 层次聚类法 层次聚类是建立在给定数据对象集合的一个层次性的分解，根据层次分解的形 成过程，这类方法可分为分裂( 自顶向下) 的，或合并( 自底向上) 的。为了弥补合并 或分裂的严格性，层次聚类方法的聚类质量可以通过分析每个层次划分中的对象链 接，或集成其它的聚类技术来改进。 1 6 太原理 大学硕士研究生学位论文 对于给定的文档集合伊元以以一，层次聚类的具体过程如下： 1 ) 将口中的每个文档西看作一个具有单个成员的类白= 以，这些类构成了口 的一个聚类仁向，岛”二； 2 ) 计算f 中每对类“o 之间的相似度s i r e ( e , , c j ； 3 ) 选取具有最大相似度的类对a r g m a x s i m f 乙，并将讲和。合并为一个 新的类o = o ，ue j ，从而构成口的一个新的聚类庐( c ，g 。) 4 ) 重复上述步骤，直至f 中剩下一个类为止。 该过程构造出一颗生成树，其中包含了类的层次信息以及所有类内和类间的相 似度。层次聚类方法是最常用的聚类方法，它能够生成层次化的嵌套类，而且准确 度高。但是，在每次合并时，需要全局地比较所有类之间的相似度，并选择出最佳 的两个类，因此运算速度比较慢，不适合大量文档的集合。 2 平面划分法 平面划分法与层次聚类法的区别在于，它将文档集合水平地分割为若干类，而 不是生成层次化的嵌套类。它首先得到初始k 个划分的集合，参数k 是要构建划分 的数目，然后它采用迭代重定位技术，试图通过将对象从一个簇( c l u s t e r ) 移到另一 个簇来改进划分的质量。 对于给定的文档集合庐( 以以西，国，平面划分法的具体过程如下： 1 ) 确定要生成的类的数目岛 2 ) 按照某种原则生成k 个聚类中心作为聚类的种子s = ( 巩易岛，s j ； 3 ) 对口中的每个文档击，依次计算它与所有各个种子研的相似度 s i m ( d s i ) 4 ) 选取具有最大相似度的种子a r g m a x s i m f 乙，将4 归入以研为聚类中心 心的类白，从而得到口的一个聚类庐( 白，岛，g 一，) ； 5 ) 重复步骤2 、3 、4 若干次，以得到比较稳定的聚类结果。 该方法的运行速度快，但是必须事先确定k 的取值，且种子选取的好坏对聚类结 构有较大的影响。 一种典型的平面划分聚类方法是k - m e a n s 算法，在数据挖掘领域中得到了最广泛 的应用。给定一个例子集合，其中每一个属性均为数值属性，和一个整数k ( 功， 1 7 太原理工大学硕士研究生学位论文 k 表示要分成簇的数目。k - m e a n s 算法将z 分割为k 个聚类并使得每个聚类中所有 值与该聚类中心距离的总行最小。每个聚类的聚类中心是每个聚类的均值。该过程 可以被描述为如下数学问题： 最小化：p 缈，q ) 蹇毫k 一( ；r ，q ) 公式q - 1 5 满足：杰一，- 1 ，一，一- 1 n ，- 1 ，i 公式2 1 6 其中，矿是一个n x k 的分割矩阵，用以表示每个例子在哪个聚类中，通常每一 行的和为1 ，口= ( 岛，以，劬为聚类结果的集合。d ( ) 是两个对象欧氏距离的平 方。 问题p 可以通过反复求解如下两个子问题只和只而得到解决。 ( 1 ) 问题只：固定q 一孬，解决简化后的问题p