（计算机软件与理论专业论文）svm在web文本挖掘中的应用与研究.pdf

堕笙鎏! ：型查堂堡堂垡堡茎 摘要 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 文本挖掘；统计学习理论；支持向量机；增量学习 哈尔滨l ：栏火学硕士学位论文 a b s t r a c t w e bh a sb e c o m eas i g n i f i c a n tm e t h o do fg a i n i n gi n f o r m a t i o n o f f e r i n g a b u n d a n ti n f o r m a t i o ns o u r c e s v a s tw e bp a g e sa l s op u tf o r w a r dac h a l l e n g ea tt h e s a m et i m e ，i ti sh o wt og e tw a n t e di n f o r m a t i o nf r o mt h ei n f o r m a t i o no c e a n q u i c k l y t h et e c h n o l o g yo fw e bt e x tm i n i n gi sak i n do fs o l u t i o n w h i l e ，t h e a p p l i c a t i o ne f f e c to f w e b t e x tm i n i n gt e c h n o l o g i e si ne x i s t e n c ei sn o ti d e a le n o u g h ， a n dc a n n o tf i tt h en e e d o fw e bd o c u m e n t se x p a n d i n gi n h i g hs p e e d s o ， d e v e l o p i n gn e ww e bt e x tm i n i n gt e c h n o l o g i e sh a sb e c o m ear e s e a r c hh o t s p o t d i r e c ta g a i n s tt h ea b o v es i t u a t i o n ，t h i st e x th a sd o n et h ew o r ko ft h r e ef o l l o w i n g r e s p e c t sm a i n l y f i r s t l y , t h i st e x ti n t r o d u c e st h eb a s i cc o n c e p t ，k i n da n dm e t h o do fw e bd a t a m i n i n g w i mt h ec o n c r e t ep r o c e d u r ea n dc o r r e l a t e dt h e o r i e so fw e bt e x tm i n i n g w ei n t r o d u c e t e c h n o l o g i e s o fc h a r a c t e rd e n o t a t i o na n dc h a r a c t e r p i c k u p e s p e c i a l l ya n db r i n gf o r w a r dan e wc h a r a c t e rs e l e c t i o nm e t h o d t h i sm e t h o dc a n s e l e c tt h ec h a r a c t e r sh a v i n gt h em o s ts o r td e n o t a t i o nm e a n i n ga n db e n e f i t i n gt o c l a s s i l y i n gm o s t ，w i t hk e e p i n gd o w nt h ec h a r a c t e rs p a c eg r e a t l ya tt h es a l n et i m e s e c o n d l y , w es t u d yt h es t a t i s t i c a ll e a r n i n gt h e o r y ( s e t ) a n ds u p p o r tv e c t o r m a c h i n e ( s v m ) t h e o r ys e r i o u s l y , a n dd i s c u s sc l a s s i l y i n ga l g o r i t h ma n dk e r n e l f u n c t i o n w ee x p a t i a t et h er e s e a r c ha n da p p l i c a t i o ns t a t u so fs u p p o r tv e c t o r m a r c h i n e ，a n dp o i n to u ts o m ei m p o r t a n ti s s u e sw h i c hi st ob er e s l o v e dw h e n r e s e a r c h e r sd of u r t h e rr e s e a r c ho fs v m 。 f i n a l l y , w ec o m b i n es v m w i t hi n c r e m e n t a ls t u d yi n t ow e bt e x tm i n i n ga n d p u tf o r w a r dan e ws v mi n c r e m e n t a ls t u d ya l g o r i t h m i tc a na b n e g a t eu s e l e s s s a m p l e sa n dm a k et h ek n o w l e d g eo fs t u d yo b j e c t sa c c u m u l a t e t h i sa l g o r i t h m ，i n t h ei n c r e m e n t a ls t u d yq u e s t i o n ，i sm o r ee f f e c t i v et h a nt h et r a d i t i o n a ls u p p o r t v e c t o rm a c h i n e 、v i t l ia s s u r i n gt h ec l a s s i f ya c c u r a c y k e y w o r d a ：w e bt e x tm i n i n g ；s l t ；s v m ；i n c r e m e n t a ls t u d y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 日期：2 _ o v 5 - 年2 月7 , 3 日 第1 章绪论 1 1 课题的来源、目的和意义 本课题来源于黑龙江省自然科学基金项目，即“基于w e b 的数据挖掘 技术的研究”。近年来，i n t e r n e t 正以令人难以置信的速度在飞速发展， 在信息时代最显著的特征之一就是信息的产生，传播速度更加迅速，信息 的交流量日益增加。目前网络上普遍存在着“信息爆炸”的问题，即信息 极大丰富而知识相对匮乏。据美国基础软件丌发商英克托米( i n k t o m i c o m ) 的一项研究结果表明，i n t e r n e t 上可编索引的网页已超过1 0 亿，如果加 上大量无法索引的页面，i n t e r n e t 上的网页总数则更多。所以w e b 已经发 展成为拥有1 0 多亿页面的分布式信息空间，而且这个数字仍以每4 至6 个 月翻一倍的速度增加。 为了从大量数据的集合中发现有效、新颖、潜在有用的、可理解的模 式。在数据库领域采用了数据挖掘技术。但是，数据挖掘的绝大部分工作 所涉及的是结构化数据库，很少有处理w e b 上的大量、异质、非结构化信 息的工作。f o r r e s tr e s e a r c h 的统计资料指出，在i n t e r n e t 中8 0 以上的 数据都是以非结构化的形式存在，如技术报告、技术文档、e m a i l 等。解 决这些问题的个途径就是将传统的数据挖掘技术和w e b 结合起来，进行 w e b 挖掘。w e b 挖掘即是从w e b 文档和w e b 活动中抽取感兴趣的、潜在的 有用模式和隐藏的信息。w e b 挖掘作为数据挖掘的一个新主题，引起了人 们的极大兴趣。 对w e b 进行快速、有效的资源和知识发现具有极大的挑战性。考虑到 在i n t e r n e t 上最多的就是文本信息，w e b 信息处理的核心就是如何处理 w e b 文档。因此，基于w e b 的文本挖掘将作为本文研究的重点而加以讨论。 哈尔滨，i ：穗人学硕士学位论文 1 2w e b 文本挖掘研究现状 1 2 1 国外的研究现状 w e b 文本挖掘”“和一直都存在的信息检索有较深的渊源，因此，许多 技术都是原子信息检索领域。互联网上信息量大，由于这信息缺乏结构化、 组织的规整性，目前几乎多数的互联网查询工具都面临匹配的查准率低， 给出的查询结果大量冗余，但是查全率却不高的问题。对于这个问题的研 究，学术界有两派。 一是从信息检索角度研究这个问题，主要研究如何处理文本格式和超 级链接文档，这些数据是非结构化或者是半结构化的。数据以词组、短语、 n 维词元等形式表示，采用t f i d f 和变量、机器学习和词组统计( n l p ) 等研 究方法对文档进行分类、聚类、研究抽取词组在文档中出现的规律。c r a v e n 等研究了用关系原型表示文档内容，采用了修改了的贝叶斯算法，给超文 本链接分类，寻求w e b 页面关系，抽取规则。c r j m m i s 研究了用短语、超 链接和信息元素表示文档内容，采用自动和非自动学习的分类算法，对文 档进行聚类和分层分类。f u m k r a n z 、j o a c h i m s 用词包和超级链接信息表示 文档内容，采用规则学习算法t f i d f ，对超级链接文档进行分类。m u s l e a 等用词包、表识和词位信息表示文档，采用规则学习算法，训练抽取规则。 二是从数据库角度研究，主要处理半结构化的w e b 数据库，也就是超 级链接文档，数据多采用带权图或者对象嵌入模型( o e m ) ，或者关系数据库 表示，应用p r o p r i e t a r y 算法、i l p 或者经过修改了的关联规则挖掘算法， 从而寻找出网站页面之间的内在联系。g o l d m a n 、n e s t o r o v 等人用o e m 表 示文档，采用p r o p r i e t a r y 算法，分别在半结构化数据中，寻找标引字段 和数据的层次结构。z a i a b e 和h a n 用关系数据库表示数据，采用面向对象 的推理方法，寻找多层次数据库的构建策略，为文献标引提供决策依据。 无论是从i r 角度还是从数据库角度研究，都是为了研究如何实现文本 分析、文本解释和文本分类等工作的自动化。从而提高网上搜索引擎的查 准率和查全率。 哈尔滨i 释火学硕士学位论文 1 ，2 2 国内的研究现状 国内互联网是从1 9 9 7 年开始迅速蓬勃发展起来的。国内学者从1 9 9 9 年才开始关注w e b 数据挖掘，与国外相比起步较晚。 北京科技大学的唐箐等人，构建了一个适用于现代远程教育的文本挖 掘系统。它能充分利用w e b 站点( 远程教育站点) 上积累的丰富文本信息， 更好地服务于远程教育。该系统采用的分类挖掘算法是向量空间的距离测 度分类法，该算法与朴素贝叶斯分类算法、k 邻近分类算法相比而言，主 要是分类的算法容易实现，分类速度也比较迅速。该系统的查准率和查全 率都比较高，表现出来的算法性能比较好。 中科院软件研究所、北京邮电大学模式识别与智能实验、微软亚洲研 究院室等多家研究机构也都进行着相关的理论研究。可见，w e b 数据挖掘 在国内已经逐渐引起人们的关注。但是，目前国内在w e b 数据挖掘方面的 研究还处于起步阶段。 1 3 统计学习理论与支持向量机算法 统计学习理论【一1 ( s t a t i s t i c a ll e a r n i n gt h e o r y 或s 【t ) 是一种专门研究小 样本情况下机器学习规律的理论。该理论针对小样本统计问题建立了一套 新的理论体系，在这种体系下的统计推理规则不仅考虑了对渐进性能的要 求，而且追求在有限信息的条件下得到最优结果。v a p n i k 等人从六、七十 年代开始致力于此方面的研究，到九十年代中期，随着其理论的不断发展 和成熟，也由于神经网络学习方法在理论上缺乏实质性进展，统计学习理 论开始受到越来越广泛的重视。 统计学习理论的一个核心概念就是v c 维( v cd i m e n s i o n ) 概念，它是 描述函数集或学习机器的复杂性或者说是学习能力的一个重要指标，在此 概念基础上发展出了一些关于统计学习的一致 生( c o n s i s t e n e y ) 、收敛速 度、推广性能( g e n e r a l i z a t i o np e r f o r m a n c e ) 等重要结论。 统计学习理论是建立在一套较坚实的理论基础之上的，为解决有限样 本学习问题提供了一个统一的框架。它能将很多现有方法纳入其中，有望 3 哈尔滨1 ：程大学硕士学位论文 帮助解决许多原来难以解决的问题( 比如神经网络结构选择问题、局部极小 点问题等) ；同时在这一理论基础上发展了一种新的通用学习方法一支持向 量机( s u p p o r tv e c t o rm a c h i n e 或s v m ) ，已初步表现很多优于已有方法的性 能。一些学者认为，s l t 和s v m f 在成为继神经网络研究之后新的研究 热点，并将推动机器学习理论和技术的重大发展。 支持向量机刚方法是建立在统计学习理论的v c 维理论和结构风险最 小原理基础上的，根据有限的样本信息在模型的复杂性( 即对特定训练样本 的学习精度，a c c u r a c y ) 和学习能力( 即无错误地识别任意样本的能力) 之间 寻求最佳折衷，以期获得最好的推广能力( g e n e r a l i z a t i o n a b i l i t y ) 。支持向 量机方法的几个主要优点有： 1 它是专门针对有限样本情况的，其目标是得到现有信息下的最优解 而不仅仅是样本数趋于无穷大时的最优值： 2 算法最终将转化为一个二次型寻优问题，从理论上说，得到的将是 全局最优点，解决了在神经网络方法中无法避免的局部极值问题： 3 算法将实际问题通过非线性变换转到高维的特征空间，在高维的特 征空间中构造线性判别函数来实现原空间中的非线性判别函数，特征性能 保证机器有较好的推广能力，同时它巧妙地解决了维数问题，其算法复杂 度与样本维数无关； 在s v m 方法中，只要定义不同的内积函数，就可以实现多项式逼近、 贝叶斯分类器、径向基函数方法、多层感知器网络等多种现有学习算法。 统计学习理论从七十年代术诞生，到九十年代之前都处在初级研究和 理论准备阶段，近几年才逐渐得到重视，其本身也趋向完善，并产生了支 持向量机这一将这种理论付诸实现的有效的机器学习方法。目前，支持向 量机算法在模式识别、回归估计、概率密度函数估计等方面又有应用。例 如在模式识别方面，对于手写体数字识别、人脸识别与人脸检测、以及文 本分类等各个领域。研究支持向量机在w e b 文本挖掘中的应用是本论文的 主要内容。 堕i ! 鎏! ：壁查鲎堡主堂鱼垒銮 1 4 本篇论文的组织结构 本文认真研究分析了基于支持向量机的w e b 文本数据挖掘的基本原理 和一般方法，对支持向量机分类和w e b 数据挖掘的定义、相关技术以及国 内外研究现状进行了认真地归纳总结，并在此基础上对支持向量机分类算 法进行了研究。 全文分为五章。 第一章是绪论，介绍了本课题的来源、目的和意义；基于w e b 的文本 挖掘技术的研究现状以及统计学习理论和支持向量机算法。 第二章首先介绍了w e b 数据挖掘的基本概念、分类和方法：然后主要 介绍了w e b 文本挖掘的一些基础知识、w e b 文本挖掘的具体过程，重点介 绍了w e b 文本挖掘中的特征表示与特征提取技术，并提出了一种新的类别 区分词的特征选择方法。 第三章是机器学习、统计学习理论概述，主要介绍统计学习理论研究 内容。 第四章是介绍支持向量机的主要研究内容。并介绍了关于支持向量机 理论的研究与应用。同时指出对支持向量机进一步研究和应用需要解决的 一些重要问题。 第五章是有关s v m 在w e b 文本挖掘中的应用讨论了基于s v m 寻优 问题的k k t 条件和样本之间的关系，分析了样本增加后支持向量集的变化 情况，基于分析结论提出了一种新的s v m 增量学习算法。 堕笙鋈! ：型丛堂堡主兰堡鲨茎 第2 章w e b 文本挖掘的研究 2 1w e b 挖掘的起源 w e b 已经成为信息发布、交互及获取的重要工具，它是一个巨大的、 分布广泛的、全球的信息服务中心。它涉及新闻、广告、消费信息、金融 管理、教育、政府、电子商务和其他许多信息服务。现代社会的竞争趋势 要求对i n t e r n e t 上大量产生和出现的信息进行实时、多视角、多层次的分 析。虽然可以借助于强大的搜索引擎和搜索技术，但是用户仍然在分析和 使用这些信息时面临许多困难：首先查询信息的查准率和查全率低，表现 在返回很多不相关的结果和找不到相关的文档：其次大多数搜索引擎仅仅 用关键字查找，不具备机器学习和数据挖掘技术；最后，不能了解用户的 兴趣爱好，无法提供个性化服务。当今世界上研究的热门领域w e b 挖掘能 直接或间接地解决上述问题。w e b 挖掘是数据库、数据挖掘、人工智能、 信息检索、自然语言理解等技术的综合应用。由于w e b 是异质分布且不断 增长的信息系统，对其挖掘并不是上述技术的简单综合，它需要有新的数 据模型、体系结构和算法等。 2 2w 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 数据挖掘还应 考虑以下问题n 一】i 6 哈尔滨i ：程入学硕士学位论文 ( 1 ) 数据来源分析 在对网站进行数据挖掘时，所需要的数据主要来自于三方面：w e b 服务 器中的日志文件、w e b 服务器中的其它信息以及客户的背景信息。每当站 点被访问一次，w e b l o g 在同志数据库中就增加相应的记录。w e b 分析工具 可以通过分析和处理w e b 服务器的同志文件生成有意义的信息。w e b 服务 器还可以存储其他有关的w e b 使用信息，如c o o k i e 和用户提交的查询信息 等。如何从这些非结构化数据信息中有效地挖掘出有用的信息时对数据挖 掘领域的一个新挑战。 ( 2 ) 异构数据环境 从数据库研究的角度出发，w e b 网站上的信息也可以看作一个数据库， 一个更大，更复杂的数据库。w e b 上的每一个站点就是一个数据源，每个 数据源都是异构的，因而每一个站点之间的信息和信息的组织都不一样， 这就构成了一个巨大的异构数据环境。如果想要利用这些数据进行挖掘， 首先，必须要研究站点之间异构数据的继承问题，只有将这些站点的数据 都集成起来，提供给用户一个统一的视图，爿有可能从巨大的数据资源中 获取所需要的信息。其次，还要解决w e b 上的数据查询问题，因为如果不 能很有效地得到所需的数据，对这些数据进行分析、集成、处理就无从谈 起。 ( 3 ) 半结构化的数据结构 w e b 上的数据与传统的数据库中的数据不同：传统的数据库都有一定 的数据模型，可以根据模型来具体描述特定的数据；而w e b 上的数据非常 复杂，没有特定的模型描述。每一个站点的数据都各自独立设计，并且数 据本身具有自述性和动态可变性。因而，w e b 上的数据具有一定的结构性， 但因自述层次的存在，从而是一种非完全结构化的数据，这也被称之为半 结构化数据。半结构化数据是w e b 上数据的最大特点。 ( 4 ) 解决半结构化的数据源问题 w e b 数据挖掘技术首先要解决半结构化数据源模型和半结构化数据模 型的查询与集成问题。解决w e b 上的异构数据的集成与查询问题，就必须 要有一个模型来清晰地描述w e b 上的数据。针对w e b 上的数据半结构化的 特点，寻找一个半结构化的数据模型是解决问题的关键所在。除了要定义 7 哈尔滨i ：程入学硕士学位论文 一个半结构化数据模型外，还需要一种半结构化模型抽取技术，即自动地 从现有数据中抽取半结构化数据模型的技术。面向w e b 的数据挖掘必须以 半结构化模型和半结构化数据模型抽取技术为前提。 ( 5 ) 文本总结 其目的是对文本信息进行浓缩，给出它的紧凑描述。文本总结是指从 文档中抽取关键信息，用简洁的形式对文档内容进行摘要或解释。这样， 用户不需要浏览全文就可以了解文档或文档结合的总体内容。 2 3w e b 挖掘的分类 我们可以将w e b 挖掘一般定义为：从与w w w 相关的资源和行为中抽取 感兴趣的、有用的模式和隐含信息。而w e b 资源有三种类型：h t m l 标记的 w e b 文档数据、w e b 文档内的连接的结构数据和用户访问数据，如服务器的 l o g 同志信息。按照对应的数据类型，w e b 挖掘可分为3 类：w e b 内容挖掘 ( w e bc o n t e n tm i n i n g ) ，w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) 和w e b 使 用记录的挖掘( w e bu s a g em i n i n g ) 。图2 1 给出了w e b 挖掘的分类图。 图2 1w e b 挖掘分类 哈尔滨i ：程大学硕士学位论文 2 3 1 w e b 内容挖掘 w e b 内容挖掘是从文档内容或其描述中抽取知识的过程。w e b 文档内容 的挖掘，基于概念索引的资源发现，以及基于代理的技术都属于这一类。 w e b 内容挖掘有两种策略：直接挖掘文档的内容，或在其他工具搜索的基 础上进行改进。采用第一种策略的有针对w e b 的查询语言w e bl o g ， w e b s q l 等。利用启发式规则来寻找个人主页信息a h o y ，等等。采用第二种策 略的方法主要是对搜索引擎的查询结果进行进步的处理，得到更为精确 和有用的信息。属于该类的有w e bs q l ，及对搜索引擎的返回结果进行聚类 的技术等。 2 3 2w e b 结构挖掘 w e b 结构挖掘是从w w w 的组织结构和超链接关系中推导知识。由于文 档之间的互连，w w w 能够提供除文档内容之外的有用的信息。由于w e b 中 包含的结构信息处理起来比较困难，因此通常的w e b 搜索引擎等工具仅将 w e b 看作是一个平面文档的集合，而忽略了其中的结构信息。w e b 结构挖掘 的目的在于揭示蕴含在这些文档结构信息中的有用的模式。 2 3 3w e b 使用挖掘 w e b 使用挖掘的主要目标是从w e b 的访问记录中抽取感兴趣的模式。 w w w 中的每个服务器都保留了访问同志( w e ba c c e s sl o g ) ，记录了关于用户 访问和交互的信息。分析这些数据可以帮助理解用户的行为，从而改进站 点的结构，或为用户提供个性化的服务。这方面的研究主要有两个方向： 一般的访问模式追踪和个性化的使用记录追踪。一般的访问模式追踪通过 分析使用记录来了解用户的访问模式和倾向，以改进站点内的组织结构。 而个性化的使用记录追踪则倾向于分析单个用户的偏好，其目的是根据不 同的访问模式，为每个用户提供定制的站点。 哈尔滨t 程大学硕士学位论文 2 4w e b 文本挖掘 文本挖掘是近几年来数据挖掘领域的一个新兴分支，其基本思想是： 首先利用文本切分技术，抽取文本特征，将文本数据转化为能描述文本内 容的结构化数据，然后利用聚类、分类技术和关联分析等数据挖掘技术， 形成结构化文本树，并根据该结构发现新的概念和获取相应的关系。以w e b 文本文档为对象的文本挖掘被称为w e b 文本挖掘。w e b 文本挖掘属于w e b 内容挖掘的范畴，可以对w e b 上大量文档集合的内容进行概括、分类、聚 类、关联分析。 2 4 1f f e b 文本挖掘的相关术语 ( 1 ) 文本 文本概括是指从w e b 文档中抽取主要的信息，从而形成关于文本内容 的简洁摘要，这属于自动摘要的技术。例如，搜索引擎在向用户返回查询 结果的时候，通常需要给出文档的摘要，是用户在浏览全文之前可以快速 了解文档的主要内容。目前，绝大部分搜索引擎采用的方法是截取文档中 出现检索词频次最高的几行或者几句话作为摘要，并不考虑检索词位置和 匹配长度问题，因此摘要的效果很差。 ( 2 ) 文本分类 文档分类是w e b 文本挖掘的一项重要技术，是指将w e b 文档集合中每 个文档归入一个预先定义的类别之中。这样，用户在浏览w e b 文档时，就 不会因为纵横交错的超级链接而“迷路”，而是基于一种主题分类的指导， 目前，y a h o o 等搜索引擎通过人工来对w e b 上的文档进行分类，这大大影 响了索引的页面数目，不能适应于w e b 上文档高速膨胀的需要。 ( 3 ) 文本聚类 文档聚类与分类的不同之处再与，聚类没有预先定义好的主题类别， 它的目标是将文档集合分成若各个簇，要求同一簇内文档内容的相似度尽 可能地大，而不同簇间的相似度尽可能地小。h e a r s t 等人的研究已经证明 了“聚类假设”，基于用户查询相关的文档通常会聚类的比较靠近，而远离 哈尔滨i ：程火学硕士学位论文 与用户查询不相关的文档。 ( 4 ) 关联分析 关联分析最早被应用于“货篮子”的研究，这里是指文档之间以及文 档集合中不同词语之间的关联关系，即不同的几个词语出现在同一篇文档 中的概率研究。例如b r i n 提出了一种从大量文档中发现一对词语出现模式 的算法，并用来在w e b 上寻找作者和书名的出现模式，从而发现了数千本 在a m a z o n 网站上找不到的新书籍。 2 4 2w e b 文本挖掘的具体过程 w e b 文本挖掘的具体过程一般分为四部分：特征提取、文本挖掘过程、 质量评估、信息表示和信息导航。图2 2 显示了w e b 文本挖掘的一般过程 匪咂m m 斗圈 图2 。2w e b 文本挖掘的一般过程 ( 1 ) 文档采集模块主要是w e b 文档采集器。w e b 文档采集器能够自动漫 游于w e b 站点之间，按照某种策略进行远程数据的搜索与获取。并将获取 的文本集成在系统的本地文本库中，用于进一步的分析之用。 ( 2 ) 特征提取：对w e b 上采集到的挖掘目标样本进行特征提取，采用空 间向量模型、潜在语义索引和小波分析方法生成挖掘目标的特征矢量；同 时应根据特征项集选取的两个基本原则即完全性和区分性原则进行特征项 集的选取。并将提取到的特征矢量经过特征子集的选取后存放到文本特征 库中形成文本中间表示形式。 基于w e b 的文本挖掘的特征提取重点是对文本中出现的词汇、名字、 术语、同期和短语的特征提取，目标是实现提取过程的自动化。事实上， 文本中词汇、名字和日期一般在文中出现很多，因而特征提取已成为基于 w e b 文件挖掘中的一项关键技术。本文将在2 4 3 节中详细讨论。 用特征词条及其权值代表目标信息，词条在不同文档中所呈现出的频 率分布是不同的，因此可以根据词条的频率特性进行特征提取和权值评价。 哈尔滨掰掣人学硕士学位论文 w e b 文本中存在大量的h t m l 格式的文本，与普通的文本相比，h t m l 文档中 有明显的标识符，结构信息更加明显，在计算特征词条权值时，可以充分 考虑h t m l 文档的特点，对于标题和特征信息较多的文本赋予较高权值。由 于w e b 文本的数据信息非常巨大，往往提取出来的特征向量的维数非常高， 为了提高运行效率，需要对特征向量进行降维处理，仅保留权值较高的词 条作为文档的特征项，从而形成维数较低的目标特征向量。 ( 3 ) 文本挖掘过程 文本挖掘是采用各种方法对w e b 文本进行挖掘处理，最终得到潜在的 知识或者模式。挖掘处理方法有分类、聚类、关联分析等。其中分类是w e b 挖掘中一项非常重要的任务，分类的目的是让机器学会一个分类函数或分 类模型，该模型能把w e b 文本映射到已存在的多个类别中的某一类，使检 索或查询的速度更快，准确率更高。文本分类是将待分类的w e b 文本分配 到已经存在的某些类别中，属于有指导的机器学习问题。 常见的文本分类方法包括贝叶斯分类方法、矢量质心相似度法、k 最 近邻居分类器、支持向量枫、其他分类方法。 贝叶斯分类方法是一种最常用的有指导的分类方法。以贝叶斯定理为 理论基础，是一种在已知先验概率与条件概率的情况下的模式识别方法。 贝叶斯分类器分为两种。一种是朴素贝叶斯分类器，它假设一个属性对给 定类的影响独立于其他属性，即特征独立性假设。当假设成立时，于其它 分类算法相比，朴素贝叶斯分类器是最精确的。但是，文本属性之间的依 赖关系是可能存在的。另种是贝叶斯网络分类器。可以考虑属性之间的 依赖程度，其计算复杂度比朴素贝叶斯高很多，但更能反映真实文本的情 况。 矢量质心相似度方法的思想是在向量空间模型中，每个文本表示为一 个特征向量，计算两个特征向量之间的距离，以距离来衡量两个文本的近 似程度。它是一种简单的有指导学习算法，也是其它分类算法的基础。 k 最近邻居分类( k n n ) 方法是传统的模式识别算法，是一种基于实例的 文本分类方法，在文本分类方面得到了广泛的研究与应用。它是通过计算 文本间的相似度，找出训练集合中与测试文本最相似的k 篇文本，然后制 定类别。k n n 方法实际上是矢量质心相似度方法的一种改进。它有两种基 1 2 堕! 墨! ：型丛堂堕主兰笪鲨墨 本的实现方式。一种首先计算测试文本与训练文本集中每个文本的文本相 似度，找出k 个最相似的训练文本，然后统计这k 篇训练样本中属于某一 类的文本数，哪类最多，则测试样本就属于哪一类。另一种首先计算测试 文本与训练文本集中每个文本的文本相似度，找出k 个晟相似的训练文本， 然后计算这k 个训练样本中属于某一类的相似度之和，哪类最大，则测试 样本就属于哪一类。如果将认为超过某一阀值就可以判为哪一类，则得到 相应的k n n 多分类器。 支持向最机由v a p n i k 等人根据统计学习理论提出的一种新的学习方 法，近年来受到了国际学术界的重视，已经在很多领域得到了应用。支持 向量机的最大特点是根据v a p n i k 结构分线最小化理论原则，尽量提高学习 机的泛化能力。支持向量机算法相当于求解一个凸集优化问题，因此局部 最优解一定是全局最优解。这些特点是其它算法所不及的。将支持向量机 应用于文本分类，不仅可以有效地避免了维数灾难、计算灾难，而且很多 研究表明s v m 分类器是优越的分类器之一。本文将在第四章和第五章做详 尽的研究。 常见的文本分类器还有决策树分类器、神经网络分类器、线性最小方 差匹配分类器等。决策树是使用最广泛的一种机器学习方法，它在每个节 点测试一个单词是否在文本中出现，对应的分支是否已直顺畅直达叶子节 点，或者说最后的分类是否被达到。神经网络领域采用感知算法进行分类， 最常见的有b p 算法等。在这种模型中，分类知识存储在连接的权值上，使 用迭代算法确定权值。当网络输出判别正确时，权向量不变，否则进行增 加或降低的调整。对线性可分的情况，感知算法是收敛的，对于线性不可 分的情况，一般不收敛，可以采用最小均方差误差准则。线性最小方差匹 配分类器从训练文本集合和它们的类别中自动学习一个多变回归模型。训 练数据被表示为输入输出向量对的形式，输入向量仍是传统的向量空间模 型中的一个文本向量，输出向量有对应文本的类别组成。通过解线性最小 方差匹配，可以获得一个从任意文件到加权类向量的一个匹配。权重越大， 就说明文本越可能属于此类别。 ( 4 ) 质量评估 对i n t e r n e t 上的文本数据进行文本挖掘可以看作是一种机器学习的 1 j 堕笙鎏! ：堡盔堂堡主堂壁堡茎 过程，在机器学习中的学习的结果是某种知识模型m ，机器学习的一个重 要组成部分便是对产生的模型m 进行评估。在机器学习中常用的模型质量 评估指标有分类正确率，查准率与查全率”1 ，查准率与查全率的几何平均 数，信息估值，兴趣性) 其中兴趣性是一个客观结合的评价指标。 查全率= 分类的正确文本数应有的文本数，它是人工分类结果应有 的文本分类中分类系统吻合的文本所占的比率。 查准率= 分类的正确文本数实际分类的文本数，它是所有判断的文 本中与人工分类结果吻合的文本所占的比率。 ( 5 ) 信息表示和导航 基于w e b 的文本挖掘系统最终挖掘出来的知识或者模式信息如果能够 以可视化的方式进行显示，同时对用户提供信息导航的功能，那么将在极 大的程度上方便用户有效、快速地浏览和获取信息。通过使用可视化图形 界面的信息表示技术和信息导航技术，用户将能够更快地接受信息并根据 自己的兴趣度对所反馈的挖掘结果进行有目的的查询和浏览。 2 5w e b 文本挖掘中的特征表示和特征提取技术 与数据库中的结构化数据相比，w e b 文档具有有限的结构，或者根本 就没有结构。同时，w e b 文档的内容是人类所使用的自然语言，而计算机 只能处理a s c i i 文件。文本信息源的这些特殊形式使得现有的数据挖掘技 术无法直接应用于其上。我们需要对文本进行预处理，抽取代表其特征的 元数据，将这些文档转化为一种类似关系数据库中记录的比较规整且能反 映文档内容特征的表示，实现文档的量化处理，建立起文档模型。但此时 文档向量会达到数十万的惊人维数，因此特征集的缩减成为文本数据挖掘 中必不可少的一步。 在此，本文将详细讨论文档模型建立、特征选取算法等相关技术，这 是进行一切w e b 文本挖掘应用的前提。 w e b 文档模型建立主要有三种方法：( 1 ) 统计模型方法主要是采用矢量 空间模型( v s m ，v e c t o rs p a c em o d e l ) 。( 2 ) 潜在语义索引( l s i ，l a t e n t s e m a n t i ci n d e x i n g ) 也用矢量表示特征项，但是每一个向量代表一个“概 1 4 哈尔滨i ：程火学硕士学位论文 念”。( 3 ) 概率模型方法是用概率架构来表示特征项。其中矢量空间模型是 近年来应用较多且效果较好的方法之一，其技术是通过分词和词频统计方 法，从文档中选出尽可能多的词、词组和短语，由它们来构成文档矢量。 2 。5 。1 自动分词技术及常见算法 理解汉语首先要把连续的汉字串分割成词的序列。自动分词”是汉语 自然语言处理的第一步。所谓自动分词技术是在中文文本中连续地能够代 表语义单元的词或者n 元词条间加入分隔符。 自动分词方法大致可以归结为以下三大类：基于词典的方法( l e x i c a l m e t h o d ) 、基于统计的方法( s t a t i s t i c a lm e t h o d ) 、混合方法( h y b r i d m e t h o d ) 。 2 5 1 1 基于词典分词方法 基于词典方法的基本思想是：首先建立一个包含所有可能出现的词词 库。然后对给定的待分词的汉字串s ，按照某种确定的算法切取s 的子串， 若该子串与词库中的某词条相匹配。则该子串是词，继续分割剩余的部分， 直到剩余部分为空：否则，该子串不是词，转上重新切取s 的子串进行匹 配。 使用该方法，词典的涵盖程度决定了词汇切分的准确率，要做到这一 点很不容易。此外浚方法无法j 下确切分出词表中未收录的新词，不具备自 适应性。实际使用的分词系统，都是把基于词典的分词方法作为一种最初 的切分手段，还需要利用各种其他语言信息来迸一步提高切分的准确率。 2 5 1 2 基于统计的分词方法 基于统计的分词方法是基于这样一个语言信息：在文章中，相邻的词 同时出现的次数越多，就越有可能构成一个词，所以字与字相邻共出现的 频率或者概率能够较好地反映他们成为词的可信度。 设p ( x ，y ) 为汉字x ，y 的相邻共现概率，p ( x ) ，p ( y ) 分别是x 、y 在语料 中出现的概率。定义两个字的互信息为：m ( x ，y ) ：l o g ( p ( x ，y ) p ( x ) p ( y ) ) ， 1 5 嗡尔滨i ：程大学硕士学位论文 互信息体现了汉字件组合关系的紧密程度。设定一个阀值，使得当m ( x ，y ) 高于某一个阀值时，便认为两个字可能构成了一个词，采用这种方法，得 到的非真实词条会很多，识别精度较差，时空开销大。 混合的方法是将上述两种方法结合起来使用。在这三大类的基础上， 还可以将各种分词的基本方法进一步分为如下几种：词典匹配法、设立标 志法、词频统计法、联想词群法、语义语用法、知识与规则法、人工智能 法等。 上述方法中比较简单有效的分词方法是基于大型词典的机器分词法。 此外将词典匹配法中的正向最大匹配法和逆向最大匹配法结合使用，可以 发现许多交叉类歧义型字段，免去了其他处理方法多次煮找、判断歧义型 字段的操作。 随着计算机汉字输入输出问题的基本解决，汉语信息处理技术已经从 “字处理”转移到“词处理”，但是，由于词语存在统一、多义以及对短语 和上下文的依赖等现象，单纯基于词形的技术中，把意义密切相关的词孤 立提取，忽略了词语的语言学特征和相互关系，存在较大的局限性。在分 词技术中，借助语法、语义等深层语言信息有助于进一步提高分词精度。 目前，在文本挖掘过程中采用全部或部分理解文本语义的基于语义相关技 术和基于对词的理解之上的概念生成的概念相关技术已经成为一个新的研 究方向。 2 5 2w e b 文本的特征表示 词、词组和短语是组成文档的基本元素，并且在不同内容的文档中， 各词条出现频率有一定的规律性，不同的特征词条可以区分不同内容的文 本。因此我们可以抽取一些特征词条构成特征矢量，用这个特征矢量来表 示w e b 文本。这是一个非结构化相结构化转化的处理步骤，特征表示的构 造过程就是挖掘模型的构造过程。 常用文本特征表示方法有：矢量空间模型、布尔模型、概率型等。 哈尔滨，l 程人学硕士学位论文 2 5 2 1 文档、项、项的权重的概念 ( 1 ) 文档：泛指一般的文本或文本中的片断，一般指一篇文章。( 2 ) 项： 文本中的内容特征常用它所含的基本语言单位( 字、词、词组、短语等) 来 表示，这些基本的语言单位被统称为文本的项，即文本可用项集表示为 d ( t ，：，。) ，其中是项。( 3 ) 项的权重：对于含有n 个项的文本，不同 的项“，其区分文本的能力不同，故t 。常被赋予不同的权重w k ( d ) ，表示他 们在文本中的重要程度，d = ( 小w 1 ( d ) ；r ，w 。( d ) ；f 。，( d ) ) 。 2 5 2 2 矢量空间模型 在v s m 模型中，把， ，r 。看成一个n 维的坐标系， w ，( d ) ，w ：( d ) ，w n ( d ) 为相应的坐标值，因而文本d 被看成是n 维空间中的 一个规范化特征向量v ( d ) = ( 小w l ( d ) ；，w ，( d ) ；f 。，w ( d