（管理科学与工程专业论文）基于xml和svm的web文本挖掘研究.pdf

人连理t 大学硕十研究生学位论文 摘要 随着互联网的发展，i n t e m e t 上的信息快速增长，目前我们面临的情况是一乃面用 户对快速、准确地获得所需要的信息的渴望，另一方面是i n t e r n e t 上信息量的巨大以及 信息内容结构的复杂性，使得处理这些信息具有很多困难。为了解决这个矛盾，w e b 挖 掘技术提供了一种途径，目前w e b 挖掘的研究f 处在不断发展的阶段，需要在理论、 实现方法与技术卜进行人量的研究。论文主要研究w e b 文本挖掘技术。 论文依照w e b 文本挖掘的过程对w e b 文本挖掘进行了详细的研究，构建了一个基 于可扩展标记语占( x m l ) 和支持向量机( s v m ) 的w e b 文本挖掘模型。论文着重对 w e b 文本预处理的过程和方法进行研究，论文提出用x m l 技术将w e b 页面上的信息进 行结构化，进而再将这些w e b 文本表示成计算机能够处理的形式，提取出对文本挖掘 有用的信息，缩减数据量，形成个文本特征库来做为w e b 文本挖掘的基础。w e b 文 本预处理的结果对w e b 文本挖掘的质量和效率有着很重要的影响，因此，w e b 文本预 处理阶段是至关重要的，需要进行洋细而完善的研究。论文还构建了一个w e b 文本挖 捌模型，这个基于x m l 和s v m 的w e b 文本挖掘的模型主要包含了w e b 文本预处理和 w e b 文本挖掘的功能，它的优点存于它利用权威页面的确定、x m l 技术以及特征提取 逐步地缩小了数据量，同时得到了能够准确表达文本内容的特征词条集合，用支持向量 机的方法降低高维数据的维数，使文本挖掘处理的数据更加精炼。 关键词：w e b 文本挖掘；w e b 文本预处理；x m l ；特征提取；支持向量机 任爽：基十x m l 和s v m 的w e b 文本挖掘研究 r e s e a r c ho nw e bt e x tm i n i n gb a s e do i lx m la n ds v m a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e r n e t i n f o r m a t i o no fi n t e r n e ti n c r e a s eq u i c k l y o n eo ft h e i n s t a n c e sw ef a c en o wi st h eu s e r sa s p i r a t i o no fo b t a i n i n gn e e d f u li n f o r m a t i o nq u i c k l ya n d e x a c t l y ，t h eo t h e ro n ei sh u g ea m o u n to fi n f o r m a t i o na n dc o m p l e x i t yo fi n f o r m a t i o ns t r u c t u r e ， t h e s et h i n g sm a k ed i f f i c u l tp r o c e s si n f o r m a t i o n t os o l v et h ec o n f l i c t ，w e bm i n i n gt e c h n i q u e s p r o v i d ea l la p p r o a c h ，r e s e a r c ho fw e bm i n i n gi sd e v e l o p i n gn o w ，i tn e e dt or e s e a r c ha b o u t t h e o r ya n dt e c t m i q u e t h ed i s s e r t a t i o nm a i n l yr e s e a r c h e sa b o u tw e bt e x tm i n i n gt e c h n i q u e s t h ed i s s e r t a t i o nr e s e a r c h e st h ew e bt e x tm i n i n gi nd e t a i la c c o r d i n gt ot h ep r o c e s so fw e b t e x tm i n i n g ，c o n s t r u c t saw e bt e x tm i n i n gm o d e lb a s e do ne x t e n s i b l em a r k u pl a n g u a g e ( x m l ) a n ds u p p o r tv e c t o rm a c h i n e ( s v m ) 1 1 1 ed i s s e r t a t i o nf o c u s e so nr e s e a r c ho fp r o c e s s a n dt e c h n i q u eo fw e bt e x tp r e p r o c e s s i n g ，t h ed i s s e r t a t i o ni n d i c a t e ss t r u c t u r i n gt h ei n f o r m a t i o n i nw e b p a g e sb yx m l ，a n dt h e ne x p r e s st h e s et e x t sb yf o m l a tt h a tc o m p u t e rc a r ld e a lw i t h ， e x t r a c tu s e f u li n f o r m a t i o nf o rt e x tm i n i n g ，r e d u c et h ea m o u n to fd a t a ，f o r mat e x tf e a t u r e d a t a b a s ef o rt e x tm i n i n g r e s u l to fw e bt e x t p r e p r o c e s s i n gi n f l u e n c e t h eq u a l i t ya n d e f f i c i e n c yo fw e b t e x tm i n i n g ，t h e r e f o r e w e bt e x tp r e p r o c e s s i n gi sv e r yi m p o r t a n tf o rw e b t e x tm i n i n g i tn e e dp a r t i c u l a ra n di n t e g r a t e dr e s e a r c h t h ed i s s e r t a t i o na l s oc o n s t r u c t saw e b t e x tm i n i n gm o d e l ，t h ew e bt e x tm i n i n gm o d e lb a s e do nx m la n ds v m p o s s e s s e sf t m c t i o n o fw e bt e x tp r e p r o c e s s i n ga n dw e bt e x tm i n i n g i t sa d v a n t a g e so l - er e d u c i n ga m o u n to fd a t a s t e pb ys t e pb yf i x i n go na u t h o r i t yp a g e s ，x m lt e c h n i q u e ，f e a t u r es e l e c t i o ni no r d e rt oo b t a i n t e r mg a t h e rt h a tc a ne x p r e s st e x tc o r r e c t l ya n dr e d u c i n gd i m e n s i o no f h i g h - d i m e n s i o nd a t ab y s u p p o r tv e c t o r sm a c h i n e ，r e f i n e sd a t at h a tt e x tm i n i n gn e e dt op r o c e s s k e yw o r d s ：w e bt e x tm i n i n g ；w e bt e x tp r e p r o c e s s i n g ；x m l ；f e a t u r es e l e c t i o n ；s v m 独创性说明 作者郑重声明：本硕上学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 大连理工大学硕十研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电予 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名：j 堡夔 导师签名： 塑! 年三月婆日 犬迕理1 人学硕十研究生学位论文 1 绪论 1 1 问题的提出 随着训算机信息技术和网络技术的发展，使今天的w e b 成为信息发布、交瓦和获取 的丰要工具。万维网是一个巨人、分布广泛、全球性的信息服务中心，它涉及新闻、广 告、消费信息、会融管理、教育、政府、电子商务和许多其它信息服务，然而，互联网 的快速发展却给我们带来了信息爆炸的问题，据2 0 0 5 年4 月1 4n 国务院信息化工作办 公室发布的中国互联网络信息资源数量调查报告的结果显示，2 0 0 4 年全国网页总数已经 达到8 亿6 千万个，而2 0 u 3 的全闭网页总数为3 亿2 千多万个，2 0 0 2 年的全国网页总 数为1 亿5 千多万个，j 年来的统计结果显示，网页数量正以成倍的速度增长，仝球内 的网页数量在2 0 0 4 年底也已经突破了1 0 0 倒。”。这些丰富的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 中资源主要是眭iw e b 页面构成的，具有半结构化、复杂性等特点，最 近一份f o r r e s tr e s e a r c h 的统计资料指出：“在i n t e m e t 和i n t r a n e t 中8 0 以上的数据都 是以半结构化的形式存在，如技术报告、技术文档、e m a i l 、专家陈述等1 4 j 。”，冈此 在w e b 上进行挖掘就要将传统的数据挖掘技术和能够处理半结构化数据的技术结合起 来。 i n t e m e t 上信息的特点足信息数量的巨大化、信息存在形式的动态化和信息管理需求 的个性化，但是传统的进行手1 分类的方法已经无法适应这种需要，而自动分类正在成 为目前自然语言处理研究领域的一个热点，现在已经出现了许多自动分类的方法，但是 由于渐进理论的条件不易满足或耆由于难以修改或者由于文本向量的维数特别大等原 因，导致分类效果才i 够理想。 任爽：基丁x m l 和s v m 的w e b 文本挖掘研究 为了解决上面提到的这些w e b 文本半结构化、网上信息的来源比较广泛、文本向量 维数特别大的问题，本文运用了x m l 技术以及s v m 这种数据挖掘的新的方法，建立 了w e b 文本挖掘的模型，为实际的w e b 文本挖掘系统的开发提供了指导。 1 2w e b 文本挖掘概述 w e b 文本挖掘足指从大量半结构化、异构的w e b 文档的集合d 中发现有效的、新 颖的潜在可用的及最终可理解的知识k n o w l e d g e ( 包括概；含( c o n c e p t s ) 、模式( p a r t e r n s l 、 规贝j j ( r u l e ) 、规律( r e g u l a r i t i e s ) 、约束( c o n s t r a i m s ) ) 及t w 视化( v i s u a l i z a t i o n ) 等形式) 的过程 p 1c 它可以对w e b 上文档集合的大量内容进行总结、分类、聚类、关联分析以及利用 w e b 文档进行趋势预测等。 1 21w e b 文本总结 w e b 文本总结是指从w e b 文档中抽取出关键的信息，从而形成关于文本内容的简 洁概要，使用户无霞浏览全文即u 门解文档或文档集合的总体内容，这属于自动摘要的 技术。其目的是对文本信息进行浓缩，给出紧凑的描述，文本总结在有些场合十分有用， 比如搜索引擎在向用户返回查洵结果时，通常给出文档的摘要。目前，绝大部分搜索引 擎采用的方法是截取文档中m 现检索词频次最高的几行或几句话作为摘要，并叫i 考虑检 索词位置和匹配长度问题，因此摘要的效果很差【6 】。 12 2w e b 文本分类 w e b 文本分类是指将w e b 文档集合中每个文档归入一个预先定义的类别之中，这 样，用户在浏览w e b 文档时，就不会因为纵横交错的超链接而“迷路”，而是基于一 种j 三体分类的指导。文本分类就是用大量的带有类标志的文本，对分类准则或模型参数 进行训练，然后用训练得到的结果对未知类别的文本进行识别。这样，客户不但能够方 便地浏览文件，而且可以通过限制搜索范围来使文件的查找更为容易。网页文本分类包 括网页类型( 文本、图形、图像、声音) 的确定、分词或词性标注、特征抽取、特征匹配、 索引生成等过程。但文本挖掘处理的是大量的半结构化的用自然语言描述的无统一结构 的文本数据，在对文档进行特征提取前，需要先对这些文本数据进行相应的预处理，它 将直接影响文本挖掘的效率和准确度以及最终模式的有效性。【7 1 利用文本分类技术可对 大量文件进行快速、有效的自动分类。文本分类的算法有很多种，比如统计法、机器学 习法、神经网络法、矩阵变换法等，常用决策树嘲、k - 邻近算法【9 】和n a i v eb a y e s t l 0 1 等进 行文本分类。 人连理丁大学硕士研究生学传论文 文本分类是一种典型的有指导机器学习问题。一般分为训练和分类两个阶段，具体 过程如卜 1 l 】： 训练阶段： ( 1 ) 根据该专、i k 领域已有的分类体系，事先确定类别的集合c = c ，c ，c 。 ，这些 类别可以是层次式的，也可以是并列式的； ( 2 ) 选择适量具有代表性的w e b 文档，给t 扫i ) i l 练文档集合s = s 。，s ，s 。) ： ( 3 ) 对于s 中的每个洲练文档s ，确定其所属的类别c ，： ( 4 ) 抽取训练文梢s 的特征，得到特征向量v ( s ，) ； ( 5 ) 统计s 中所有文档的特征矢量v ( s 。) ，以此确定代表c 中每个类别的特征矢量 v ( c ) ； 分类阶段： ( 6 ) 对于测试文档集合t = d 。d 。，d ， 中每个待分类文档d 。，计算其特征矢量 v ( d 。) 与每个v ( c ) 之间的相似度s i m ( d k ，c 。) ； ( 7 ) 选取相似度最大的一个类别作为d 。的类别，有时也可以为d 。指定多个类别，只 要d 。与这些类别之间的相似度超过某个预定的阈值。如果d 。与所有类别的相似度均低 于闽值，那么通常将该文档放存边，由用户来做最终决定。对于类别与预定义类别不 匹配的文档而言，这是合理的，也是必须的。如果这种情况经常发生，则说明需要修改 预定义类别，然后重新进行上述训练与分类过程。在计算s i m ( d 。，c 。) 时，有多种方法 u r 供选择。最简单的方法是仅考虑两个特征矢量中所包含的词条的重叠程度，即 s 删一) = 粼1 3 ( 1 1 ) i d ci 其中，n 、( d 。，c 。) 是v ( d 。) 和v ( c ；) 具有的相同词条数目，n y ( d 。，c 。) 是v ( d k ) 着1 1 v ( c ，) 具有 的所有词条数目。 最常用的方法是考虑两个特征矢量之闻的夹角余弦，即 s i m 一，2 嵩拼 z ， 12 3w e b 文本聚类 w e b 文档聚类的目标足把一组对象结合按照相似性归成若干类别。文本聚类与分类 的不同之处在于，聚类没有预先定义好的主题类别，需要南聚类学习算法来自动确定， 任爽：基丁x m l 和s v m 的w e b 文本挖掘研究 它的目标是将文件集合分成若干个簇，要求同一簇内文件内容的相似度尽可能地大，而 小同簇间的相似度尽可能地小”“。h e a r s t 等人的研究己经证明了“聚类假设”，即与客 户查询相关的文件通常聚类得比较靠近，而远离与客户查询不相关的文档f 1 3 】，因此，可 以利用文本聚类技术，提供大规模文档集内容的总结；识别隐藏的文档间的相似度；减 轻浏览相关、相似信息的过程。如将查找引擎的检索结果划分为若干个簇，客户只需要 考虑那些相关的簇，大大缩小了所需要浏览的结果数量口4 。 目前，有多种文本聚类算法，大体可以分为两种类型：以g - h a c 等算法为代表的 层次聚类i 】5 j 和分裂聚类，以k - m e a n s 等算法为代表的平面划分法【1 6 1 。层次聚类法是最为 常用的聚类算法，它能够牛成层次化的嵌套簇，且准确度较高。但是在每次合并时，需 要全局地比较所有簇之问的相似度，并选择出最佳的两个簇，因此运行速度较慢，不适 合 i 大量文档的集合。平面划分泣是将文档集水平地分为若干个簇，不生成层次化的嵌 套簇，因此其运行速度较快，但缺点足它须事先确定簇的数目，且对噪声点和输入顺序 都是敏感的，特别是当数据维数较高时，该算法的性能和聚类质量均明显下降【1 ”。平面 划分法与层次聚类法之间的区别在十它将文档集合水平地分割为若干个簇，而不足生成 层次化的嵌套簇。 文本聚类是。种无指导的机器学习问题，不是按照预先的类表进行归类，而是从给 定的文档本身出发，根据义档特征同矢量，将相关者聚成类。根据文本聚类的结果不 同，可以将聚类方法分为层次聚类法和平面聚类法两种类型。 对于给定的文档集合d = d 。，d ，d 。 ，层次聚类的过程如下： ( 1 ) 将d 中的每一个文档d ，作为一个聚类中心c ；= ( d ， ，形成d 的一个聚类集合 c 2 c 。c 1 ，c 。) ： ( 2 ) 计算c 巾每个聚类对 c c 之间的相似度s i m ( c ，c ) ； ( 3 ) 选取具有最大相似度的两个聚类( c ，c ) lm a xs i r e ( c 。，c ，) ，将合并成个新的聚类 c 。= c ，uc ，同时合并c i 和c ，的特征矢量，从而构成了d 的一个新聚类集合 c 2 c ”c ”，c ) ； ( 4 ) 重复上述步骤，根掘所要产牛聚类的数目和相似度阈值限制，得到最终聚类结果。 从上而的聚类过程可以看出，层次聚类对文档集合d 中的每一个文档进行了多次遍 历，其结果实质上构造出了一个生成树，其中包含了聚类的动态过程和层次信息。层次 聚类方法是最为常用的聚类方法，因为它能够产生层次化的嵌套聚类，所以准确度很高。 另外，在层次聚类过程中，最大相似度呈递减趋势，因此必须确定适当的相似度阂值， 保证同一个类中的文档紧密相关。甲面划分法与层次聚类法的区别在于它将文档集合水 大连理t 大学硕士研究生学位论文 平地分割为若干个类，而不是生成层次化的嵌套聚类。对于给定的文档集合 d = d ，d ，d 。) ，平面划分法的具体过程如下： ( 1 ) 确定要生成的类的数目k ； ( 2 ) 抽取d 中每个文档的特征矢量v ( d ) ； ( 3 ) 从d 中抽取k 个文档形成聚类的中心s = s ，s ，s 。 。为了提高聚类的准确度， 住确定聚类中心时应该依据一定的原则。常用的确定聚类中心的方法有逆中心距法和密 度测试法等。 ( 4 ) 对d 中的剩下的文档，依次计算它们与各个聚类中心的相似度s i m ( d ，s ，) ；根据 预定的相似度闽值，将文档聚集在聚类中心的周围，形成稳定的聚类结果。 这种方法的运行速度较快，但是必须事先确定k 的取值，且种子选取的好坏对聚类 结果有较大影响】。 1 3x b l 技术 1 9 9 6 年，叫扩展标记语言( e x t e n s i b l em a r k u pl a n g u a g e ，简称x m l ) 以种开放的、 自我描述的方式定义数掘结构，i 以以容易而一致的方式格式化和传送数据( 通常是在 w o r l dw i d ew e b 上) 。x m l 发计成s t a n d a r dg e n e r a l i z e dm a r k u pl a n g u a g e ( 标准通用标记 语言，简称s g m l ) 的一个子集，它是简化的，而且目标足面向w e b 。x m l 提供了一种 独立的运行程序的方式来共享数据，它是用来自动描述信息的一种新的标准语言，它能 使计算机通信把i n t e r n e t 的功能山信息传递扩大到人类其他多种多样的活动中去。x m l 由若干规则组成，这些规则町用于创建标记语言，并能用一种被称作分析程序的简明程 序处理所有新创建的标记语言。x m l 能够将内容与商业逻辑和表示( p r e s e n t a t i o n ) 分开， 通过将文件的内容与其格式分开定义，x m l 使得在其他的应用或表示环境中重复使用 内容更加容易【l 1 。 与h t m l 相比，x m l 具有内容与形式分离的特性，以及良好的可扩展性，跨平台 移植性和自描述性： ( 1 ) 内容与形式的分离性 在h t m lr f l ，数据内容和表现形式是混在一起的。这样，当数据的表现形式需要改 变时，文档更新的工作量会比较大。而对于x m l ，标记是包含信息的，比如关键字、 继承关系等，这些信息对于数据的检索、描述将起到极大的简化作用。利用x m l 这 特性，当数据的表现形式有所改变时，仅需修改x m l 文档中分离出的用于描述数据表 现形式的样式单就可以了。 ( 2 ) 良好的可扩展性 任爽：基于x m l 和s v m 的w e b 文本挖掘研究 x m l 允许程序员制定自己的标记集，允许一个行业或某个特定领域制定在本范 围内的通用标记集。这样，x m l 就可以轻松地适应每一个领域而不需要对语言本身作 大的修改。另外，由丁：x m l 的数据定义和数据本身也是分离的，这就使得x m l 的标 记集不会无限扩大。 ( 3 ) 良好的跨平台移植性 x m l 语言可以定义各种数据，如文本、图像、声音等。虽然这些数据的格式不同， 但x m l 能通过一种用于交换数据格式的文件x v i l 文档，来处理由x m l 标注的各种数 据，从而实现不同格式数据的跨平台交换。 ( 4 ) 良好的自描述性 h t m l 良好的自描述性使得其数据能够被不同的应用程序分析处理。并且，人们可 以通过标记及元素之间的天系，很清楚地看出数据要表达的内容u 9 l 。 x m l 给基于w e b 的数据挖掘技术赋予了强大的功能和灵活性，在数据的集成、发 送、处理和显示的各环节中无不表现出其卓越的性能。 ( 1 ) 实现异构数据的集成 从某种意义上说，x m l 就是一种半结构化的数据模型，而且我们很容易就可以将 其和关系数据库中的属性 。对应起来，实施精确地查询与模型抽取。因此，x m l 解 决了搜索多样的不兼容的数据库的问题。它使得不同来源的半结构化数据可以很容易地 结合在一起。这样，软件代理商i j 以在中间层的服务器上对从后端数据库器i ，j _ 以显示 x m l ，那么，你可以直接将x m l 文档发送给浏览器，或者使用x s l 将x m l 翻泽成你 的浏览器可来的数据进行集成，然后，再将数据发送到客户或其他服务器作迸一步的集 成、处理和开发。而在x m l 出现之前，如果要在异质数据库之间进行搜索，就必须了 解每个数据库的构建情况，返在实际应用中是不可能的。 ( 2 ) 易于作数据交换 在w e b 数据挖掘过程中，客，经常需要和不同结构的数据源之间进行业务数据传 递。与旧的电子数据交换( e d i ) 格式相比。x i v l l 的自定义性及可扩展性是以标示各种类 型的数据，自然也以描述从各站点搜集到的w e b 页中的数据记录。客户接收到数据后 可以进行处理，也可以在不同数据库间进行传递。总之，在这类应用中，x m l 解决了 数据的统接v 1 问题。但是，与其他的数据传递标准不同的是，x v l l 并没有定义文件 中数据出现的具体规范，而是在数据中附加标志来表达数据的逻辑结构和含义，这使得 x m l 成为一种程序能自动理解的规范。 ( 3 ) 将计算负载从w e b 服务器转移 人连理r 大学硕士研究生学位论文 数据处理阶段的处理速度是w e b 数据挖掘的关键环节。如果按照传统的 “c l i e n t s e r v e r ”j 二作模式，刚络管理者必须首先调查各种不问的用户请求，冉设计出 相应的应用程序。然后，客户端才能向服务器发出各自的不同的请求，服务器分别予以 响应。这样做，不仅加重了的工作负荷，延迟了有用信息的发掘时间，而且限制了客户 端的请求类型，使得双方都很被动。特别是，如果用户的需求繁杂而多变，则服务器端 的编程人员，可能来不及满足众多的应用需求，也很难跟上需求的变化。因而，将所有 业务都集中在服务器端显然是小合适的。而x m l 将数据处理的主动权交给了客户，w e b 服务器所要做的只是尽町能准确、完善地将数据装进x m l 文件后发送给客户。客户端 根据自己的需求选择和制作卜同的应用程序以解析数据并对数据进行编辑和处理。x m l 自带的解释执行系统在接收到数据的同时也理解了数据的逻辑结构和含义，因而使得分 布式计算成为可能。 ( 4 ) 根据需要过滤显示信息 h t m l 描述数据的外观，而x m l 描述数据本身。由于数据显示与内容分开，x m l 允许为定义的数据指定不同显示方式，使本地的数据更加合理地以客户配置，使用者选 择或其他标准方式动态地表现出米。x m l 还可以对所取得的信息进行裁减和编辑以适 应不同用户的需求。它采用简单灵活的格式分离使用者观察数据的界面，将同样的数据 以小同的浏览形式提供给不同的用户。如果浏览器可以显示x m l ，那么可以直接将x m l 文档发送给浏览器，或者使用x s l 将x m l 翻译成浏览器可处理的内容【2 0 1 。 x m l 解决了h t m l 不能解决的两个w e b 问题，即i n t e m e t 发展速度快而接入速度 慢的问题，以及虽然w e b 上存在海量的信息，但却难以找到自己需要的那部分信息的 问题。x m l 能增加结构和语义信息问题，可是计算机和服务器即时处理多种形式的信 息。由于x m l 能够使不同来源的结构化的文本很容易地结合在一起，因而使搜索多样 的不兼容的文本库能够成为可能，从而为解决w e b 文本挖掘难题带来了希望。x m l 的 扩展性和灵活性允许x m l 描述搜集的w e b 页巾的不同类型文本【2 ”。 1 4 支持向量机 支持向量机( s v m ) 是一种建市在统计学习理论基础上的机器学习方法，为了最小化 经验风险的上界，s v m 方法存固定学习机经验风险的条件下最小化置信范围【2 2 j 。其主 要思想是针对二类分类问题，在商维空间中寻找一个超平面作为二类的分割，以保证最 小的分类错误率。该算法将原始数据集合压缩到支持向量集合( i s 常为前者的3 5 ) ，然后用子集学习得到新知识，同时也给出由这些支持向量决定的规则。并且可得 到学习错误的概率上界，叩支持向量的期望数目和训练集合大小的比值。它具有以下四 任爽：基丁x m l 和s v m 的w e b 文本挖掘研究 个理论要点：( 1 ) 非线性峡射是理论的基础；( 2 ) 对特征空间划分的最优超平面( o p t i m a h y p e r p l a n e ，简称o h p ) 是s v m 的目标；( 3 ) 支持向量( s v ) 是s v m 的结果；( 4 ) = 次规划 足计算s u 的手段1 2 3 ) 。 传统的统计方法只有在样本数趋向无穷大时其性能才有理论上的保证。对于应用中 的优先样本难以取得理想的效果：支持向量机方法是一种小样本学习方法，支持向量机 方法能在训练样本数很小的情况下达到很好分类推广能力的学习算法。s v m 可以给出 学习结果的推广能力的界。s v m 是种处理非线性分类和非线性回归的有效方法。s v m 方法的计算量与样本向量的维数几乎无关，这在某种意义避免了“维数灾”。以卜+ 这些 是支持向量机方法的优点。 尽管支持向量机方法存有些方面比其他学习机器更具优越性，但是在实际应用中也 暴露出+ 些缺点，如计算量大、速度慢、参数选择经验性强、不能很好地解决多分类问 题等。其中速度问题在很大程度上限制了s y m 的应用，成为s v m 方法进入大规模实 用化阶段的瓶颈。s v m 训练速度慢的主要原因是训练过程中进行了大量的二次规划计 算，而分类速度慢的主要原因是分类过程中有大量的支持向量参与了计算。 为了解决上面的提到的缺点利问题，有很多解决方法从支持向量计算角度着手，也 有从二次规划方法改进着手的 2 4 1 。 s v m 的训练本质是解决一个次规划的问题，但是这种传统的算法通常对规模小的 样本数据，一旦样本数据量增大，就会由于过多地占用内存，导致训练时间过长和效果 不佳，所以对于数据挖掘而言，需要处理的数据是海量数据，s v m 的传统算法显然不 适合，需要采用其他更优化的算法。目前，研究人员已经提出了几种更有效的算法。 o s u n a 等人提出了一种分解方法，该算法首先选择一个小的工作集，在这个工作集 上进行优化，然后从工作集中移走个样本，加入一个不满足k u h n t u c k e r 条件的样本， 冉进行优化，重复进行。闪为工作集相对较小，所以每一步都很容易得到q p 问题的最 优解。而且，在同一时间，算法的运行只需要有限的内存消耗。 在o s u n a 提出的分解方法的基础上，通过适当的选择工作集进行优化，j o a c h i m s 提 m 了s v m l i 曲t 算法，该方法能够在同一时间处理一定数量的样本，从而也能有效地解 决内存消耗。 p l a t t 提出的s m o 算法日，其算法的特点是能够在同一时间处理两个样本例子；此 外，还有o l v il m a n g a s a t i a n 等提出的l s v m l a s v m 、s o r s s v n 等【2 6 1 。 s v m 分类可以获得较高的精确率，但是对于网页分类而言，如果利用s v m 的重叠 性进行通用的多类分类，会造成训练时间过长。事实上实际应用中大量的专业网页分类， 人连理 一大学硕士研究生学位论文 则可以考虑采用s v m 进行二类分类，然后再用其他方法对专业类别进行多样分类，这 样既能获得较好的分类结果，义能提高分类效率【2 7 】。 1 5 论文的研究思路及工作 本文构建了一个基于x m l 和s v ? v l 的w e b 文本挖掘的模型，就模型的设计以及w e b 文 本预处理、w e b 文本挖掘的方法做了较为深入的研究。 沦文首先论述了w e b 文本挖掘的必要性，接着介绍了w e b 文本挖掘的流程及存在的 困难，针对这些难点提出了基丁x m l 和s v m 的w e b 文本挖掘的总体结构模型，介绍模型 每一部分的功能和优点，然后对w e b 文本预处理、w e b 文本挖掘所采用的各种方法做了 详细的阐述，其中着重对w e b 文本预处理的过程和方法进行研究，最后给出了w e b 文本 挖掘的应用实例。 论文的主要_ j 一作有： ( 1 ) 提出了一个基于x m l 和s v m 的w e b 文本挖掘的模型； ( 2 ) 着重研究如何进行w e b 文本的预处理，w e b 文本预处理的过程包括了文本抽取， 文本处理，特征抽取以及将文本表示为特征向量的形式，这几个步骤都能够在不影响文 本表达和不影响文本分类精度的情况下尽量减少需要处理的数据量，提高分类的效率和 精度； ( 3 ) 在特征向量的基础上进行文奉挖掘，并用文本集测试分类和聚类的结果； ( 4 ) 将这个w e b 文本挖掘模型应用在科技文献的分类上。 堡鍪二垄兰! 塑l 塑型堕坠! 塞查垂塑堕壅 2w e b 文本分类与聚类方法的比较 上一章介绍过了w e b 文本分类和聚类的计算过程，这章主要对几种文本分类聚 荚的方法进行介绍和分析。 2 1 w e b 文本分类方法比较 常用的w e b 文本分类分析方法主要有：统计法( 如n a v y eb a y e s i a l l 方法和非参数法) 、 机器学习法( 如决策树法和规则归纳法及利用b o o s t i n g 解决兼类问题的方法) 、神经网珞 法、矩阵变换法等等。 ( 1 ) 向景距离分类法2 8 1 。向量距离分类法的分类思路十分简单，根据算术平均值为每 类文本集生成一个代表该类的中心向量，然后在新文本来到时，确定新文本的向量，计 算该向量与每类中心向量间的相似度，最后判定文本属于哪个与文本距离最近的类，计 算新文本特征向量和每类中心向量间的相似度的公式为： s i r e ( d 。，d 。) = j ( 22m m ) ( 2 1 ) 詈妻，d j 为新文本的特征向量，吨为第j 类的中心向量，m 为特征向量的维数，w k 为向 罱的第k 维。 ( 2 ) 朴素贝叶斯分类方法2 9 1 。朴素贝叶斯分类方法利用下面的贝叶斯公式通过类别的 先验概率和词的分布来计算未知文本属于某一类别的概率： p ( c j ) p ( dc ，) p ( d ) ( 2 2 1 其中，p ( c ，i d ) 为样本d 属于类c ，的概率，p ( d i c 。) 为类c 中含有样本d 的概率。在 所有p ( c j d ) ( j 2 l ，f c 【) 中，p ( c 。i d ) t 直最) r ，则文本d 归为c 。类。由于p ( d ) 是 常数，因此将要求解p ( c f d ) 的问题转换为只要求解p ( c 。) p ( d c ) 。假设文本中的词的 分布是条件独立的，则 m p ( c 。d ) 2 p ( c j ) p ( d t c 。) 2 兀p ( d 。 c j ) i = l ( 2 3 ) 人连埋r 大学硕士研究生学位论文 其中p c c j ，= 号瓣：p c a f c 。，= 生享拳嘉砉筹。尽管词的分布是条 件独立的这个假设在实际文木中是不成立的，但在实际应用中朴素贝叶斯分类一般都 能取得相对较好的效果。 ( 3 ) k 最近邻分类方法3 。k 一最近邻分类方法是一种基于实例的文本分类方法。首 先，对于一个待分类文本，计算它与训练样本集中每个文本的文本相似度，根据文本相 似度找出k 个最相似的训练文本。这最相似的k 个文本按其和待分类文本的相似度高低 对类别予以加权平均，从而预测待分类文本的类别。其中最重要的是参数k 的选择，k 过小，不能充分体现待分类文本的特点；k 过大，会造成噪声增加而导致分类效果降低。 文本向量d 属于类别c ，的权值w ( c id ) 由下式计算，权值越高，认为文本向量d 属丁类别c 的概率就越高： w ( c ：l d ) 2 ：s ( d ，d 。) p ( c j d 。) ( 2 4 ) 百 。 。 其中，s ( d ，d ) 是向量之间的余弦相似度；d d 。是训练集中与d 余弦相似度最大的 k 个文本向量；而p ( c ：| d 、) ，当d 属于类别c ，时为1 ，否则为0 。 通过上面的分析可知，k 一最近邻分类方法的实质就是以特征属性权值作为特征空间 的坐标系测度，先计算测试集与训练集之间在该坐标系中的余弦距离，然后根据测试集 l 训练集的距离远近来确定炎别。显然，它没有考虑特征属性关联及贡献等因素对文本 相似度的影响，如果加以适当地考虑，k 一最近邻分类方法的效果会更好。 分类方法1 1 以根据下列标准进行比较和评估l ”j ： ( 1 ) 速度。这涉及产生和使用模型的计算花费。 ( 2 ) 强壮性。这涉及给定噪卢数据或具有空缺值的数据。 ( 3 ) 可伸缩性。这涉及给定大量数据，有效地构造模型的能力。 ( 4 ) 可解释性。这涉及学习模型提供的理解和洞察的层次。 朴素贝叶斯算法方法具有较小的出错率，另外还可以结合主动学习的方法，先用较 小的样本进行学习，然后按照某种启发式规则对未标记样本进行贴标签，加入标记样本 集合，重新进行学习，更新原来的知识，再进行未标记样本的选取，继续进行学习。 k 最近邻方法在分类效果上是最佳的，具有分类速度快，易于快速实现，方法简单 的优点，同时在训练过程中投入的时间最少，但是在分类过程中花费的时间较多，不利 于文本的实时处理。另外，它的训练样本直到未标记样本需要分类时才建立分类，如果 训练样本数量很大，那么计算很集中的特点会导致极大的开销，需要有效的索引技术。 任炎：基于x m l 和s v i v l 的w e b 文本挖掘研究 k 一最近邻方法错误率为：p4 p p + ( 2 之p ) ，因而可以粗略地认为k - 最近邻方法的 c 一1 错误率在贝叶斯和两倍贝叶斯之川。 2 2w e b 文本聚类方法比较 常用的w e b 文本聚类分析方法主要有：层次聚类分析方法，平面划分聚类分析方 法( 如k - m o a n s 聚类算法、k 一叶i 心点聚类算法) ，基于模型的聚类分析方法( 如神经网络算 法、统计学算法) ，基于密度的聚类分析方法，基于网格的聚类分析方法等等。 ( o k m e a n s 聚类算法“。给定文档集合d = f d i ，d ，d 。 ，k - m e a n s 文本聚类算法 具体过程如下： 确定要生成的簇的数目k ： 按照某种原则选取k 个初始聚类中心，c = ( c 1 c 2 ，c k ) ，并设置初始迭代次数f 1 ； 对文档集中的每一个文档d ，依次计算它与各个聚类中心c 。的相似度sj m ( d ，c ，) ； 选择具有最大相似度的聚类中心a r gm a xs i m ( d ，c ) ，将d 归入以c 。为中心的簇 中； 计算新的聚类中心，新的聚类中心为这一轮迭代中分到该簇中的所有文档矢量的 均值，刘c = 二d ，其中r 为聚簇c 的文档集合，n 。为f ，中的文档数； 。n j 蕊 如果所有聚类中心均达到稳定，则结束；否则，r = r + l ，g o t o ( 3 ) 。 该算法的优点是运行速度快，时间复杂性为0 ( k r n ) ，其中n 为总文档数，k 为得到 的聚簇数，r 为迭代次数。缺点是必须事先确定k 值，而在许多情况下，无法市先知道 文档集合中的主题类别数目。 ( 2 ) s o m 算法3 “。基于神经网络方法的文本聚类算法，将高维空问的点投影到低维空 间，而在变换过程中保留点弓点之问的相似关系，但是神经网络算法所处理的数据的维 度越高，收敛的速度也越慢，从而妨碍了在高维、大规模数据中的应用。算法的学习步 骤如下： 初始化权值矢量。 对于当前输入矢量x 选择最相似的权值矢量作为获胜神经元。权值矢量是竞争层 的神经元到输入层的每个节点的连接的权值构成的矢量，共有m * m 个。 1， r 2 以获胜的神经元为中心，按照墨西哥草帽函数v ：h ：( 三车) e 2 一( 或它的某种近 盯。 似形式) 米确定侧反馈的影响区域( 活性泡) 。 大连理- i ：大学硕十研究生学位论文 以一定的比率活性泡中的权值矢量向获胜神经元的权值矢量移动。 适当更新参数( 学习速度和活性泡的大小) 。 转到步继续处理卜个输入矢量，直到权值不再发生明显变化。 s o m 算法是。个两阶段( 指定聚类、聚类中心的修改) 基于欧氏距离反复循环的过程。 其最大的问题是学习模式较少时，效果取决于模式输入的先后顺序，而且网络连接权向 量的初始状态对网络的收敛性有很火影响。 聚类方法是否有效，可以从下面几个方面来看。“： ( 1 ) 训扩展性。许多聚类算法存小数据集( 少于2 0 0 个数据对象) 是可以很好地工作， 但是一个大数掘库可能包含 ：百万个对象，利用采样方法进行聚类分析可能得到一个有 偏差的结果，这时就需要可扩展的聚类算法。 ( 2 ) 需要由用户决定的输入参数最少。许多