（计算机软件与理论专业论文）基于模板的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 页面信息的方法，这些方法各有所长，同 时也有各自的局限性。 根据在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 页面信息以及页面信息属性的算 法 根据w e b 页面信息的层次结构，提出了w e b 页面信息的树型结构存储 方式以及向某个数据模型转换的必要性。 在系统实现的过程中，使用了页面信息提取的准确率( p r e c i s i o 山和页面信 息的发现率( r e c a l l ) 两个指标衡量系统对w e b 页面信息提取的结果。实验结果显 示，使用本文提出的w e b 页面信息提取方法提取页面信息的准确率是非常高的， 该系统具有较强的实用价值。 关键词：w e b 页面信息，w e b 页面记号，类型，等频记号集合，频繁多记号集 合，w e b 页面模板，w e b 页面信息属性 a b s t r a c t a b s t r a c t w i t hi n f o r m a t i o nr a p i d l ye x p a n d i n gi nt h ew e b ，m a n yw e bs e r v i c e sa c c o r d i n g l yb o o m u p a sab u r g e o n i n gt e c l u r o l o g y , w e bd a t am i n i n gi sg e t t i n gm o r ea n d m o r ea t t e n t i o nb ym o r e a n dm o r er e s e a r c h e r so fw e ba n dd a t a b a s et e c h n o l o g y a sab a s i cf o u n d a t i o na n di m p o r t a n t c o m p o n e n to fw e bd a t am i n i n g ，e x t r a c t i n gi n f o r m a t i o nf r o mw e bp a g e si sa p p l y i n gi nm a n y f i r l d s ，h o w e v e r , f a c i n gw i t hp e o p l er e q u e s t i n gm o r ea n dm o r er i g o r o u sa n dp r o l i f i c ，p e o p l e n e e dm o r ea n dm o r ea c c u r a t ea n di n t e g r a t e di n f o r m a t i o no fw e bp a g e st os a t i s f yt h e i rn e e d s w e l l a sar e s u l t ，r e s e a r c h e r so fw e bd a t am i n i n gh a v ep r e s e n t e dm a n ym e t h o d so fe x t r a c t i n g i n f o r m a t i o nf r o mw e bp a g e s e a c ho f t h e s em e t h o d sh a si t so w na d v a n t a g e sa n dl i m i t a t i o n b a s e do nt h el o n g - t i m ea c c u m u l a t i o ni nt h ef i e l do fe x t r a c t i n gi n f o r m a t i o nf r o mw e b p a g e s ，a n dc o m b i n i n gt h ec u r r e n td e v e l o p i n gt e c h n o l o g yo ne x t r a c t i n gi n f o r m a t i o nf r o mw e b p a g e s ，t h i sa r t i c l eb r i n gf o r w a r das o l u t i o no fe x t r a c t i n gi n f o r m a t i o nf r o mw e bp a g e sb a s e d t e m p l a t ea n dt h e nam o d e lf o rt h es o l u t i o nw i l la l s ob ep r e s e n t e di nt h i sa r t i c l e ，w h e r et h e m o d e li sm a i n l yi n c l u d i n g5m o d u l e s ：p r e p a r a t i o no fw e bp a g e s ，g e n e r a t i o no fw e bp a g e t e m p l a t e ，e x t r a c t i o n o fi n f o r m a t i o nf r o mw e bp a g e s ，e x t r a c t i o no fa t t r i b u t e so fw e b i n f o r m a t i o na n di n f o n n a t i o ns t o r e t h i sp a p e rp r e s e n ta l g o r i t b l n sa n df l o wf o re a c hm o d u l e ， a n da l s oa d v a n c es e v e r a ln e w c o n c e p t s ，d e f i n i t i o n s ，t h e o r e m sa n da l g o r i t h m sa sf o l l o w s ： p r e s e n t i n gb a s i ct y p e ，t u p l et y p ea n ds e tt y p eb a s e do nt h ec o n c e p tb p eo ft o k e n s f r o mw e b p a g e s t h e nd e m o n s t r a t i n gt h e o r e m sa b o u tt h e s ec o n c e p t s p r e s e n t i n gd e f i u i t i o n so fe f t sa n dl e t s w h i c ha r eu s e di n t h ea l g o r i t h mo f g e n e r a t i o nt e m p l a t eo fw e bp a g e sb a s e do na n a l y z i n gt h et o k e n so f w e bp a g e s p r e s e n t i n gt h ea l g o r i t h mo fe x t r a c t i n gi n f o r m a t i o nf r o mw e bp a g e sa n dt h ea l g o r i t h m o f e x t r a c t i n ga t t r i b u t e so f w e bi n f o r m a t i o nb yw e bp a g et e m p l a t e p r e s e n t i n gam e t h o do f s t o r ew e bi n f o r m a t i o nb yt r e es t r u c t u r eb a s e do nt h eh i e r a r c h y o f w e bi n f o r m a t i o n t h e nd i s s e r t a t i n gt h en e c e s s i t yo f t r a n s f o r m i n gt r e es t r u c t u r ei n t o ak i n do f d a t as c h e m a u s i n gt w op a r a m e t e r s ：p r e c i s i o na n dr e c a l lt ot e s tt h ee f f i c i e n c yo fo u rm o d e lf o r e x t r a c t i n gi n f o r m a t i o nf r o mw e bp a g e s t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h i sw o r ki s e f f e c t i v ea n dt h es y s t e mh a sas t r o n ga p p l i c a t i o ni ne x t r a c t i n gi n f o r m a t i o nf r o mw e b p a g e s k e y w o r d ：i n f o r m a t i o no fw e bp a g e s ，q b k e n so fw e bp a g e s ，t y p e ，e q u i v a l e n tt o k e ns e t ， l a r g ea n de q u i v a l e n tt o k e ns e t ，t e m p l a t eo f w e bp a g e s ，a t t r i b u t eo f w e bi n f o r m a t i o n i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如f 各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存沦文；学校有权提供目录检索以及提供 本学位沧文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作携名：舶感 支。寸译1 只印 经指导教师同意，本学位论文属于保密，在年解密后适用 木授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 南开大学学位论文原创性声明 本人郑蕈声明：所呈交的学位沦文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做山贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：粕硪 d 6 j 一年j , - 月2 ，尹r 第一章绪论 第一章绪论 第一节信息时代的新技术 当历史将人类送入廿一世纪的时候，我们会惊异地发现，互联网络正在以其 独有的魅力，吸引着越来越多的人进入这片神奇的领地，来领略它的博大精深， 来尽享它所提供的瑰宝奇珍。人们频繁地接近它、访问它、点击它，这种对互联 网的亲密接触，使人们随时能够从中获取到有价值的信息，解决实际中所遇到的 问题。想了解国内外的重大事件么，想查阅某些资料或弄清某些事实么，想即时 对某件事情直抒胸臆么，想在繁忙、紧张的工作、学习之余为使疲惫的神经得以 放松而听听音乐或与朋友聊天么这一切都可以通过对互联网的访问加以实 现。总之，互联网进入了人们生活中的每一个细节，互联网提供的价值已经涵盖 了人们可以想象的各个方面，已经深入到生活的每。个角落，它的形式和内容已 经超过过去人们所能想象的任何范围。 二十几年前，互联网才刚刚起步，仅仅为人们架起了信息沟通的桥梁。今天， 网络正在以惊人的速度改变着人们的工作、学习、生活和娱乐的方式。1 9 9 4 年 互联网正式进入中国，到今天互联网用户数已经接近1 亿，中国已经成为世界第 二大的互联网用户拥有数的国家，而且有关专家认为到2 0 0 6 年中国互联网用户 数量将居世界首位。 互联网是一个巨火的、分布广泛和全球性的信息服务中心。它涉及新闻、广 告、消息信息、金融信息、教育、政府、电子商务和许多其他信息服务。互联网 作为全球最大、最方便的信息集散地，更是积聚了耿之不尽、用之不竭的信息， 成为人们工作与学习的最大信息数据库。然而，w e b 信息的急速膨胀，在给人们 提供丰富信息的同时，又使人们在对它们的有效使用方面面临个巨大的挑战。 一方面网上的信息多种多样、丰富多彩，而另一方面用户却找不到他们所需要的 信息。冈而摹于w w 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 数据挖掘技术必须从数据挖掘技 术谈起。 1 2 1 数据挖掘技术概述 数据挖掘，又称为数据采掘、数据开采，相近的术语有k d d ( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ，数据库知识发现) 、数据分析、数据融合( d a t af u s i o n ) 等。 根据w j f r a w l e y 和g p s h a p i r o 等人在 1 中的定义，数据挖掘就是从大量的、不 完全的、有噪声的、模糊的、随机的实际应用数据中，抽取隐含在其中的、人们 事先不知道的，但又是潜在有用的信息和知识的过程。提取的信息和知识表示为 概念( c o n c e p t s ) 、规则( r u l e ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式f 2 。 数据挖掘技术是人们对数据库技术不断研究和开发的结果，是继宽带网络之 后的又一个技术热点。自1 9 8 9 年出现以来，经过十多年的发展，数据挖掘技术 已趋于成熟，并已投入商业应用。世界上比较有影响的典型数据挖掘系统有： s p s s 公司的c l e m e n t i n e ，i b m 公司的i n t e l l i g e n t m i n e r ，s g i 公司的s e t m i n e r ， s a s 公司的e n e r p r i s e m i n e r ，r u l e q u e s t r e s e r c h 公司的s e e 5 ，还有c o v e r s t o r y 、 e x p l o r a 、k n o w l e d g e d i s c o v e r r y w o r k b e n c h 、d b m i n e r 、q u e s t 等。 1 2 2 数据挖掘的任务 数据挖掘的任务主要是关联分析、聚类分析、分类、预测、时序模式和偏差 分析等1 3 j 0 ( 1 ) 关联分析( a s s o c i a t i o na n a l y s i s ) 关联规则挖掘是由r a k e s ha p w a l 等人首先提出的。两个或两个以上变量的 取值之间存在某种规律性，就称为关联。数据关联是数据库中存在的一类重要的、 可被发现的知识。关联分为简单关联、时序关联和因果关联。关联分析的目的是 找出数据库中隐藏的关联网。一般用支持度和可信度两个阀值来度量关联规则的 相关性，还不断引入兴趣度、相关性等参数，使得所挖掘的规则更符合需求。 ( 2 ) 聚类分析( c l u s t e r i n g ) 聚类是把数据按照相似性归纳成若干类别，同一类中的数据彼此相似，不同 2 第一章绪论 类中的数据相异。聚类分析可以建立宏观的概念，发现数据的分布模式，以及可 能的数据属性之间的相互关系。 ( 3 ) 分类( c l a s s i f i c a t i o n l 分类就是找出一个类别的概念描述，它代表了这类数据的整体信息，即该类 的内涵描述，并用这种描述来构造模型，一般用规则或决策树模式表示。分类是 利用训练数据集通过一定的算法而求得分类规则。分类可被用于规则描述和预 测。 ( 4 ) 预测( p r e d i c a t i o n ) 预测是利用历史数据找出变化规律，建立模型，并由此模型对未来数据的种 类及特征进行预测。预测关心的是精度和不确定性，通常用预测方差来度量。 ( 5 ) 时序模式( t i m e s e r i e sp a t t e m l 时序模式是指通过时间序列搜索出的重复发生概率较高的模式。与回归一 样，它也是用己知的数据预测未来的值，但这些数据的区别是变量所处时间的不 同。 ( 6 ) 偏差分析( d e v i a t i o n ) 在偏差中包括很多有用的知识，数据库中的数据存在很多异常情况，发现数 据库中数据存在的异常情况是非常重要的。偏差检验的基本方法就是寻找观察结 果与参照之问的差别。 1 2 3 数据挖掘对象 根据信息存储格式，用于挖掘的对象有关系数据库、面向对象数据库、数据 仓库、文本数据源、多媒体数据库、空间数据库、时态数据库、异质数据库以及 i n t e r n e t 等。 1 2 4 数据挖掘流程 ( 1 ) 定义问题：清晰地定义出业务问题，确定数据挖掘的目的。 ( 2 ) 数据预处理：包括选择数据一在大型数据库和数据仓库目标中提取数 据挖掘的目标数据集；数据预处理一进行数据再加工，包括检查数据的完整性及 数据的一致性、去噪声，填补丢失的域，删除无效数据等。 ( 3 ) 数据挖掘：根据数据功能的类型和数据的特点选择相应的算法，在净 化和转换过的数据集上进行数据挖掘。 ( 4 ) 结果分析：对数据挖掘的结果进行解释和评价，转换成为能够最终被 用户理解的知识。 ( 5 ) 知识的运用：将分析所得到的知识集成到业务信息系统的组织结构中 第一章绪论 去。 1 2 5 数据挖掘的方法 ( 1 ) 神经网络方法 神经网络由于本身良好的鲁棒性、自组织自适应性、并行处理、分布存储和 高度容错等特性非常适合解决数据挖掘的问题，因此近年来越来越受到人们的关 注。典型的神经网络模型主要分3 大类：以感知机、b p 反向传播模型、函数型 网络为代表的，用于分类、预测和模式识别的前馈式神经网络模型：以h o p f i e l d 的离散模型和连续模型为代表的，分别用于联想记忆和优化计算的反馈式神经网 络模型；以a r t 模型、k o h o l o n 模型为代表的，用于聚类的自组织映射方法。 神经网络方法的缺点是”黑箱”性，人们难以理解网络的学习和决策过程。 ( 2 ) 遗传算法 遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法，是一种仿生 全局优化方法。遗传算法具有的隐含并行性、易于和其它模型结合等性质使得它 在数据挖掘中被加以应用。 s u n i l 已成功地开发了一个基于遗传算法的数据挖掘工具，利用该工具对两 个飞机失事的真实数据库进行了数据挖掘实验，结果表明遗传算法是进行数据挖 掘的有效方法之一。遗传算法的应用还体现在与神经网络、粗集等技术的结合上。 如利用遗传算法优化神经网络结构，在不增加错误率的前提下，删除多余的连接 和隐层单元：用遗传算法和b p 算法结合训练神经网络，然后从网络提取规则等。 但遗传算法的算法较复杂，收敛于局部极小的较早收敛问题尚未解决。 ( 3 ) 决策树方法 决策树是一种常用于预测模型的算法，它通过将大量数据有目的分类，从中 找到一些有价值的，潜在的信息。它的主要优点是描述简单，分类速度快，特别 适合大规模的数据处理。最有影响和最早的决策树方法是由q u i n l a n 提出的著名 的基于信息熵的i d 3 算法。它的主要问题是：i d 3 是非递增学习算法；i d 3 决策 树是单变量决策树，复杂概念的表达困难；同性问的相互关系强调不够；抗噪性 差。针对上述问题，出现了许多较好的改进算法，如s c h l i m m e r 和f i s h e r 设计 了1 d 4 递增式学习算法；钟鸣，陈文伟等提出了1 b l e 算法等。 ( 4 ) 粗集方法 粗集理论是一种研究不精确、不确定知识的数学工具。粗集方法有几个优点： 不需要给出额外信息t 简化输入信息的表达空间；算法简单，易于操作。粗集处 理的对象是类似二维关系表的信息表。目前成熟的关系数据库管理系统和新发展 起来的数据仓库管理系统，为粗集的数据挖掘奠定了坚实的基础。但粗集的数学 4 第一章绪论 基础是集合论，难以直接处理连续的属性。而现实信息表中连续属性是普遍存在 的。因此连续属性的离散化是制约粗集理论实用化的难点。现在国际上已经研制 出来了一些基于粗集的工具应用软件，如加拿大r e g i n a 大学开发的k d d - r ；美国 k a n s a s 大学开发的l e r s 等。 ( 5 ) 覆盖正例排斥反例方法 它是利用覆盖所有正例、排斥所有反例的思想来寻找规则。首先在正例集合 中任选+ 个种予，到反例集合中逐个比较。与字段取值构成的选择子相容则舍去， 相反则保留。按此思想循环所有正例种子，将得到正例的规则( 选择子的合取式) 。 比较典型的算法有a q l l 方法、a q l 5 方法以及a e 5 方法等等。 ( 6 ) 统计分析方法 在数据库字段项之间存在两种关系：函数关系( 能用函数公式表示的确定性 关系) 和相关关系( 不能用函数公式表示，但仍是相关确定性关系) ，对它们的分析 可采用统计学方法，即利用统计学原理对数据库中的信息进行分析。可进行常用 统计( 求大量数据中的最大值、最小值、总和、平均值等) 、回归分析( 用回归方程 来表示变量间的数量关系) 、相关分析( 用相关系数来度量变量间的相关程度) 、差 异分析( 从样本统计量的值得出差异来确定总体参数之问是否存在差异) 等。 ( 7 ) 模糊集方法 该方法利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识 别和模糊聚类分析。系统的复杂性越高，模糊性越强，一般模糊集合理沦是用隶 属度来刻画模糊事物的亦此亦彼性的。李德毅等人在传统模糊理论和概率统计的 基础卜，提出了定性定量不确定性转换模型云模型，并形成了云理论。 从更广义的角度来讲，数据挖掘意味着在一些事实或观察数据的集合中寻找 模式的决策支持过程。因而，数据挖掘的对象不仅是数据库，还可以是任何组织 在一起的数据集合，如互联网信息资源等。目前数据挖掘工具能处理数值型的结 构化数据，而处理文本、图形、数学公式、图像或互联网信息资源等半结构、无 结构的数据形式将是数据挖掘的挑战之一。 第三节w e b 数据挖掘技术 w e b 目前是一个巨大的、分布广泛的全球性信息服务中心，它涉及新闻、消 费信息、金融管理、教育、政府、电子商务和许多其他信息服务。w e b 还包含了 丰富和动态的超链接信息，以及w e b 页面的访问和使用信息，这为数据挖掘提供 了丰富的资源。尽管w e b 中的信息数据是那么的复杂、那么不规则，但是作为 第一章绪论 数据库技术的研究者们还是致力于对这个大数据库中的数据进行分析研究，w e b 数据挖掘就是在这个环境下产生的。 1 3 1w e b 数据挖掘的定义 文献【4 】【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 e b 信息检索与w e b 信息内容的开发也有站在信息服务的角 度上提出“数据挖掘”，指出其有别于传统的信息检索，能够在异构数据组成的 信息库中，从概念及相关因素的延伸比较上找出用户需要的深层次的信息，并提 出数据挖掘将改革传统的信息服务方式而形成一个全新的适合网络时代要求的 信息服务组合。 1 32w e b 数据挖掘的分类 根据挖掘的对象不同，w e b 数据挖掘可以分为w e b 内容挖掘( w e bc o n t e n t m 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 e m i n i n g ) 6 【7 】。 ( 1 ) w e b 内容挖掘 w e b 内容挖掘即从w e b 页面中发现有用信息的过程。w e b 信息资源类型众 多，i n t e m e t 出现之前的g o p h e r 、f t p 、u s e n e t 资源逐渐隐藏到w 珥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 页面中提取出的信息进行分类，并利用数据库 组织和存储这些信息，然后利用数据挖掘技术对信息数据进行分析，最后得到一 6 第一章绪论 些有价值的知识。w e b 页面文本信息的挖掘的方法主要采用的是数据库方法， 即把半结构化的w e b 信息重构得更加结构化，然后使用标准化的数据库查询机 制和数据挖掘方法进行分析【8 】【9 m 。w e b 页面多媒体信息的挖掘先要应用多媒体 信息特征提取工具，提取出i m a g e 和v i d e o 的文件名，u r l ，类型，键值表，颜 色向量等信息，形成二维表，然后就可以采用传统的数据挖掘方法进行挖掘分析。 w e b 内容挖掘的工具主要分为两类，一是传统的从互联网上提耿信息的搜 索引擎，包括：l y c o s ，v i s t a ，w e b c r a w l e r ，a l i w e b ，m e t a c r a w l e r 4 2 】 4 3 】等等； 二是从互联网中智能地提取信息的搜索工具，包括i n t e l l i g e n tw e ba g e n t ， i n f o r m a t i o nf i l t e r i n g c a t e g o r i z a t i o n ，p e r s o n a l i z e dw e b a g e n t s 删【4 5 】 4 6 1 等。 ( 2 ) w e b 结构挖掘 w e b 结构挖掘即挖掘w e b 潜在的链接结构模式。这种思想源于引文分析， 即通过分析个网页链接和被链接数量以及对象来建立w e b 自身的链接结构模 式。这种模式可以用于网页归类，并且可以由此获得有关不同网页间相似度及关 联度的信息。w e b 结构挖掘有助于用户找到相关主题的权威站点，并且可以概 观指向众多权威站点的相关主题的站点。 ( 3 ) 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 3 3w e b 数据挖掘的步骤 w e b 数据挖掘分为如下四个步骤( 如图1 1 ) ： ( 1 ) 资源发现，即检索所需的w e b 文档： ( 2 ) 信息选择和预处理，即从检索到的w e b 资源中自动挑选和预先处理得 到专门的信息； ( 3 ) 概括化，即从单个的w e b 站点以及多个站点之间发现普遍的模式； ( 4 ) 分析，对挖掘出的模式进行确认或者解释。 7 第一章绪论 图1 ，1w e b 数据挖掘的步骤图 1 3 4w e b 数据挖掘面临的技术难点 与传统的数据库数据相比，w e b 数据具有特殊性，其特点就是数据没有严格 的结构模式、含有不同格式的数据( 文本、声音、图像等) 、面向显示的h t m l 文本无法区分数据类型，并且存在大量的冗余和噪声，同时w e b 是一个动态性极 强的信息源，所以面向w e b 的数据挖掘研究极具挑战性。 ( 1 ) 对有效的数据挖掘而言，w e b 数据量太庞大了面且仍然在迅速地增长。这 使得几乎不可能去构造一个数据库对w e b 上所有数据进行复制、存储或集成。 ( 2 ) w e b 页面的复杂性远比任何传统的文本文档复杂的多。w e b 页面缺乏统一 的结构，它包含了远比任何一组书籍或其他文本文档多得多的风格和内容。w e b 可以看作是一个巨大的数字图书馆；然而，这一图书馆中的大量文档并不根据任 何有关排列次序加以组织。它没有分类索引，更没有建立按标题、作者、封页、 目次等的索引。在这样一个图书馆中搜索希望得到信息是极具挑战性的。 ( 3 ) w e b 是一个动态性极强的信息源。w e b 不仅以极快地速度增长，而且其信 息还在不断地发生着更新。新闻、股票市场、公司广告和w e b 服务中心都在不 断地更新各自地页面。链接信息和访问记录也在频繁地更新之中。 ( 4 ) w e b 面对的是一个广泛的、形形色色的用户群体。w e b 的用户群仍在不断 扩张中，各个用户具有不同的背景、兴趣和使用目的。大部分用户并不了解信息 网络结构，不清楚搜索的高昂代价，极容易在“跳跃式”访问中烦乱不已，或者 在等待一段信息中失去耐心。 ( 5 ) 虽然说互联网上信息很多，但实际是你需要的信息却不多，一个用户只是 关心w e b 上非常小的一部分信息，w e b 所包含的其余信息对该用户来说是不感 兴趣的。如何在信息海洋中不被淹没，尽可能地找到用户所需要的信息也是一个 8 第一章绪论 难题。 可以说，在互联网中应用数据挖掘技术的前途是光明的，但道路也是曲折的。 1 3 5 研究w e b 数据挖掘的意义和应用前景 目前，数据挖掘技术已经广泛地应用于金融业、零售业、远程通讯业、政府 管理、制造业、医疗服务以及体育事业中，而它在w e b 中的应用也正在成为一 个热点。国外在w e b 数据挖掘这一领域的研究中已经取得了初步的成果并推出 了一些原型系统，如w i n d j o 】、w e b m i n n e r 【3 】、w e b w a t c h e r 1 1 】、w t t o w e d a 2 】 等等，而国内的研究则刚刚起步。w e b 数据挖掘的应用涉及到电子商务、网站 设计和搜索引擎服务等众多方面。下面主要从这三个方面介绍其应用。 ( 1 ) 电子商务 运用w e b 用法挖掘技术能够从服务器以及浏览器端的日志记录中自动发现 隐藏在数据中的模式信息，了解系统的访问模式以及用户的行为模式，从而作出 预测性分析。例如通过评价用户对某一信息资源浏览所花的时间，可以判断出用 户对资源兴趣如何；对日志文件所收集到的域名数据，根据国家或类型 ( c o m ，e d u ，g o v ) 进行分类分析；应用聚类分析来识别用户的访问动机和访问趋 势等。这项技术已经有效地运用在电子商务之中。 ( 2 ) 网站设训 通过对网站内容的挖掘，主要是对文本内容的挖掘，可以有效地组织网站信 息，例如采用自动归类技术实现网站信息的层次性( h i e r a r c h y ) 组织；同时可以结 合对用户访问f i 志记录信息的挖掘，把握用户的兴趣，从而有助于开展网站信息 推送服务以及个人信息的定制服务。目自ip d a ( p e r s o n a ld i g i m la s s i s t a n t 个人数 字助理) 以及c e l l u l a rp h o n e ( 移动电话) 都已经可以直接接受网络信息服务。 这些设备的显示界面较小，因而网站面向这些设备的设计就应当突出精品化、个 性化的特点，而这类特色推送服务就必须采用w e b 数据挖掘技术。 ( 3 ) 搜索引擎 w e b 数据挖掘技术在搜索引擎上的应用在上一节中已经作了一些介绍。 g o o g l e 搜索的最大特色就体现在它所采用的对网页l i n k s 信息的挖掘技术上。而 实际上，w e b 数据挖掘是目前网络信息检索发展的一个关键。如通过对w e b 页 面内容挖掘，可以实现对网页的聚类、分类，实现网络信息的分类浏览与检索； 同时，通过用户所使用的提问式( q u e r y ) 的历史记录的分析，可以有效地进行 提问扩展( q u e r ye x p a n s i o n ) ，提高用户的检索效果( 查全率，p r e c i s i o n ；查准 率，r e c a l l ) ；另外，运用w e b 内容挖掘技术改进关键词加权算法，提高网络信 息的标引准确度，从而改善检索效果。 9 第一章绪论 上面仅仅列举了w e b 数据挖掘技术在这三个方面的应用。这项技术的应用 正变得越来越广泛；用户对高品质、个性化的信息的需求也将进一步推动着学术 界与实业界的研究开发工作。 第四节本文的研究内容 本文的研究内容是关于w e b 内容挖掘领域中w e b 页面信息提取的问题。本 文对该问题做了深入的研究，提出了w e b 页面信息提取的方法并设计出系统模 型。论文的主要研究内容如下： 1 、研究国内外w e b 信息提取技术的最新进展并总结w e b 页面信息提取技 术的关键技术和主要分类； 2 、提出基于模板的w e b 页面信息提取方法，包括主要思想和相关算法； 3 、设计并实现了w e b 页面信息提取的系统模型，并分析系统测试结果。 第五节论文的组织结构 第二章介绍了w e b 页面信息提取的研究现状和热门的发展方向，以及所面临 的主要问题；第三章论述了基于模板w e b 页面信息提取的方法，包括w e b 页面模 板生成、w e b 页面信息提取、w e b 页面信息属性的提取等几个关键问题；第四章 设计出了基于模板的w e b 页面信息提取的系统模型以及模型中每个模块涉及到 的关键问题和解决方法；第j i 章实现了w e b 页面信息提取系统模型并且分析了系 统的实验结果；最后，阐述了需要进一步研究的问题并总结全文。 1 0 第二章页面信息提取技术的相关研究 第二章页面信息提取技术的相关研究 w e b 页面信息提取作为w e b 数据挖掘的一项基础性的工作正在如火如荼地 快速发展着。国内外很多w e b 与数据库技术的研究者正在致力于这项技术的研 究。目前，对于w e b i 页面信息提取技术的研究方向主要有两类3 1 ：一是使用h t m l 文档的树型结构模型对w e b 页面信息进行提取和存储【“】【1 5 【1 6 】；二是将构成w e b 页 面的h t m l 代码看作特殊的字符串，使用字符串进行处理的相关技术和方法进行 w e b 页面信息提取m 【”】【1 9 】 2 0 】。在早期的研究中，通常使用人工的方法来提取w e b 页面信息，如文献【2 1 】 2 2 1 【2 3 【2 4 】【2 5 】，这种方式不仅需要大量的人力进行繁重的 工作，而且人工方法得到的w e b 页面信息提取系统很不稳定而且通用性极差口6 1 。 近几年，w e b 页面信息提取技术的研究者在该技术的两个研究方向上，逐步地研 究出多种w e b 页面信息提取方法并使用应用程序构建系统加以实现。下面介绍几 种有代表性的w e b 页面信息提取方法。 第一节r o a d r u n n e r v c r e s c e n z i 、g m e e c a 和p m e r i a l d o 在口6 1 中提出了从w e b 页面中自动提取信 息的方法r o a d r t m n e r 。使用r o a d r u n n e r 方法的前提是假设进行信息提取的w e b 页面具有相似的结构，如图2 1 所示，页面p a g e l 和p a g e 2 具有相似的结构。 21 1 基本思想 r o a d r u n n e r 方法采用的是字符串处理的思想，使用字符串的正规表达式来表 示w e b 页面。 r o a d r u n n e r 规定，页面的正规表达式u f r e ( u n i o n f r e er e g u l a re x p r e s s i o n ) 由这样一组符号组成： ，# p c d a t a ，4 - ，十，? ，( ，) ，占 其中，# p c d a l 为一个特殊的字符串，为不包括# p c d a t a 的其它字符串的 集合，s 为空字符串，集合中的剩余字符作为构成正规表达式的辅助标记，关于 这些字符或字符串的说明如下： ( 1 ) 女l i 果a 茅口b u f r e ，贝0 a b 、( n ) + 、和( 口) ? 是u f r e ( 2 ) + 表示字符串的重复出现，l n l 比( a ) + 2 d ，a a ，a a a ，“甲，璺) ( 3 ) ( 日) ? 表示( 口i s ) ，因此( 口) ? 有两个取值，( 珂) ? = “ “ 【s 第二章页面信息提取技术的相关研究 ( 4 ) ( d ) + 表示的是表达式( ( ) + ) ? ，即( 口) 2 ( s ，口，d o ，a a a ，a a a a ，b g ) 代表w e b 页面的字符串正规表达式可以看作w e b 页面的包装器( w r a p p e r ) ，包装 器的作用是与实际的w e b 页面进行字符串匹配，去掉w e b 页面中与w r a p p e r q u 相同 的字符串( 也就是w r a p p e r e 0 除了# p c d a t a 以外的所有其它字符串) ，最后， w e b 页面中保留的字符串就是# p c d a t a 所表示的w 曲页面信息。 2 1 2r o a d r u n n e r 生成w e b 页面包装器 w r a p p e r 实际上是一组w e b 页面的共同部分，它通过对w e b 页面字符串进 行两两匹配的方法生成。任意选取两个结构相似的w e b 页面，假设其中的一个 作为w r a p p e r ( 包装器) ，另一个作为s a m p l e ( 实例) ，如图2 1 所示： 图2 1w e b 页面信息提取r o a d r u n n e r 方法的页面示例 先对这两个页面进行字符串匹配，生成一个与这两个页面相适应的w r a p p e r ，然 后