（计算机应用技术专业论文）半结构化web信息抽取研究.pdf

哙尔滨t 程大学硕士学位论文 摘要 随着互联网的侠速发展和普及，入翻越来越依赖于鼹络获取信惠。翔柯 从中快速高效的获得想簧的信患成为迫切需要解决的问题，w e b 僚患抽取技 术应运悉生。露前，己经产生了各种各样的方法来生成包装器，餐这些方法 有苓网的局限性，在精确度、健壮性和通用性方瑟难以达到很高熬要求。因 此，信息抽取的研究重点就是如何构建良好的包装器。 本文首先对现有的信息抽取技术和x m l 技术进行分析与研究，提出一 个基于x m l 技术的w e b 信息抽取系统。通过该系统用户能够将h t m l 页蘧 中感兴趣的信息点抽取出来，并用结构化和扩展性强的x m l 来表示抽取结 果。该系统具有较好的逶用性期灵活性，用声能够快速定铡应用予不露领域 的w e b 信息掏取包装器。本文应焉x p a t h 技术在数据定位方面的特点，提出 一种基于d o m 的x p a t h 生成算法。本文利瘸x s l t 作为掏取规燹| j 的描述语 言，荠使用x p a t h 来定位待抽取信息赢。 对于w e b 信息抽取的问题利用本文提出的w e b 信息抽取方法能够较好 她解决，露时，系统的召圆率和准确率能够达到较高的酉分比。 关键谲：数据挖懿；锗崽捶取；半结构化数攥；w e b 略尔滨= l 二程大学硕士学袋论文 a b s tr a c t w i t ht h er a p i dd e v e l o p m e n ta n dp o p u l a r i z a t i o no fi n t e r a c t ，m o r ea n dm o r e p e o p l eo b t a i ni n f o r m a t i o nf r o mw c b t of i n dn e c e s s a r yi n f o r m a t i o nq u i c k l ya n d e f f i c i e n t l yf r o mw e bh a sb o m eas e r i o u sp r o b l e m 。w e bi n f o r m a t i o ne x t r a c t i o n t e c h n o l o g yc o m e si n t o 蜥耀。m a n ya p p r o a c h e sh a v eb e e np r o p o s e dt og e n e r a t e w r a p p e r , b u tt h e yh a v et o od i f f e r e n tl i m i t a t i o n st om a k ew r a p p e ra c c u r a t e ，r o b u s t o rg e n e r a l s o ，t h ep r e p a r i n gb e t t e rw r a p p e rh a sb e c o m et h er e s e a r c he m p h a s e so f i n f o r m a t i o ne x t r a c t i o n a f t e rh a v i n ga n a l y z e da n dr e s e a r c h e dt h et e c h n o l o g i e so fx m la n d i n f o r m a t i o ne x t r a c t i o n , as y s t e mo f 飘毫i n f o r m a t i o ne x t r a c t i o nb a s e do nx m li s d e v e l o p e di nt h i sp a p e r w i t ht h i ss y s t e m , 稿鞫e 懋c a l le x t r a c ti n t e r e s * 戳li n f o r m a t i o n f r o mh t m l p a g e s ，t h ee x t r a c t i o nr e s u l t sa r ee x p r e s s e di nx m l w h i c hh a v es t r o n g s t r u c t u r ea n de x p a n s i o n 。朝瓣s y s t e mh a st h eg e n e r a l i t ya n df l e x i b i l i t y u s e r sc a n q u i c k l yc u s t o m i z et h ew e bi n f o r m a t i o ne x t r a c t i o nw r a p p e ra p p l i e dt od i f f e r e n t 羽嬲i nt h i sp a p e r , b yu s i n gt h ec h a r a c t e ro ft h ex p a t hp o s i t i o n i n gt e c h n o l o g yi n d a t aa r e a , aa l g o r i t h mo fx p a t hb a s e do nd o mi si m p l e m e n t e d x s l ti su s e da s t h ed e s c r i p t i o nl a n g u a g eo fe x t r a c t i o nr u l e sa n dx p a t hi s u s e dt ol o c a t e i n f o r m a t i o nt ob ee x t r a c t e d 期舱m e t h o di nw 曲i n f o r m a t i o ne x t r a c t i o np r e s e n t e di nt h i sd i s s e r t a t i o n 嘲 b e t t 娌s o l v et h ep r o b l e mo f 曲i n f o r m a t i o ne x t r a c t i o n , a n da l s ot h ep r e c i s i o na n d r e c a l lo ft h es y s t e mc a nr e a c hah i g h e rp r o p o r t i o n k e y w o r d s ：d a t am i n i n g ；i n f o r m a t i o ne x t r a c t i o n ；s e m i s t r u c t u r e dd a t a ；w e b 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。太；7 珏 作者( 签字) ：一三樯 溉 日期：伽1 年3 月，2 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学尊哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本入保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 留在授予学位后即可口在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关 作者( 签字) ：j 习秀了琶 日期：协 年胃秘日 j 哈尔滨下程大学硕士学位论文 第1 章绪论 1 1 课题的研究背景及意义 随着互联网以及相关技术的发展与成熟，互联网尤其是万维阏逐渐成为 人们发布和获取信息的主要方式，从网络上收集信息资源己经成为当今以至 未来社会人们获取信息的重要手段。然而，随着互联网上信息量呈爆炸式的 增长，互联网中数据的组织类型更加多样化并且信息缺乏统一管理，人们想 要获取一条自己需要的信息交得墨益圈难，人们对高效率的信息获取技术的 需求越来越迫切。 由于目前h t m l 是大部分w e b 数据的表示形式，丽h t m l 语言的一个 显著特点是结构隐含、不规则或不完整。结果使得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 信息的再利用成为可能，因此有着明显的优势和广阔的前景，是 当今多个领域的研究热点。而以3 3 m l 技术为基础的新一代的w w w 环境是 直接面对w e b 数据的，不仅可以很好地兼容原有的w e b 应用，而且可以更 好地实现w w w 这一分布计算环境下的信息共享与交换。因此，基于x m l 的w e b 数据抽取技术的研究将w e b 信息表达语言- x m l ，应用于数据抽取， 对w e b 数据获取、数据转换、数据抽取提出新的方法，并实现一个快速通用 的数据抽取原型系统，从而为w e b 信息集成，智能信息处理，数据源闻的相 互操作，客户应用的快速构建等相关w e b 应用提供一种获取和利用w e b 信息 的通用平台。 哈尔滨工程大学硕+ 学位论文 1 2 国内外研究现状 w e b 信息抽取是将w e b 作为信息源的一类抽取。w e b 信息抽取是研究如 何将分散在i n t e r n e t 上的半结构化的h t m l 页面中的隐含的信息点提取出来， 并以更为结构化、语义更为清晰的形式表示，为用户在w 曲中查询数据、应 用程序直接利用w e b 中的数据提供便利。 从2 0 世纪8 0 年代末开始，信息抽取研究蓬勃开展起来，这主要得益于 消息理解系列会议m u c i l 的召开。正是m u c 系列会议使信息抽取发展成为 自然语言处理领域的一个重要分支，并一壹推动这一领域的研究离翦发展。 从1 9 8 7 年开始到1 9 9 8 年，m u c 会议共举行了七届，它由美国国防高级研究 计划委员会( d a r p a ，t h ed e f e n s ea d v a n c e dr e s e a r c hp r o j e c t sa g e n c y ) 资助。 m u c 的显著特点并不是会议本身，而在于对信息抽取系统的评测诩。只有参 加信息抽取系统评测的单位才被允许参加m u c 会议。在每次m u c 会议前， 组织者首先向各参加者提供样例消息文本和有关抽取任务的说明，然后各参 加者开发能够处理这种消息文本的信息抽取系统。在正式会议前，各参加者 运行各皇的系统处理给定的测试涪息文本集合，由各个系统的输出结果与手 工标注的标准结果相对照得到最终的评测结果，最后才是所谓的会议，由参 与者交流思想和感受。蘑来，这种评测驱动的会议模式褥到广泛推广，如1 9 9 2 年开始举行的文本检索会议( t r e c ，t e x tr e t r i e v a lc o n f e r e n c e ) 等。 近几年，信息抽取技术的研究与应用更为活跃。在研究方恧，主要侧重 于以下凡方面：利用机器学习技术增强系统的可移植能力、探索深层理解技 术、篇章分析技术、多语言文本处理能力、w e b 信息抽取以及对时间信息的 处理等等。在应用方面，信息抽取应用的领域更秀羁广泛，除自成系统以外， 还往往与其他文档处理技术结合建立功能强大的信息服务系统。至今，已经 有不少以信息抽取技术产品隽主的公司出现，比较著名的有：c y m f o n y 、 b h a s h a 、l i n g u a m a t i c s 、r e v s o l u t i o n s 等。 曩前，除强烈的应用需求外，正在推动信息抽取研究进一步发展的动力 主要来自美国国家标准技术研究所( n i s t ，n a t i o n a li n s t i t u t eo fs t a n d a r d sa n d t e c h n o l o g y ) 组织的自动内容抽取【3 1 ( a c e ， a u t o m a t i cc o n t e n te x t r a c t i o n ) 评测 2 哈尔滨工程大学硕士学位论文 ；n , , , 1 , , 1 , 1 , , ,i i i i i i ih i i i i i i _ m i i l u l l鞘警 会议。这项评测从1 9 9 9 年7 月开始酝酿，2 0 0 0 年1 2 月正式开始启动，迄今 已经举办过六次评测。这项评测旨在开发自动内容抽取技术以支持对三种不 同来源( 普通文本、由自动语音识别得到的文本、由光学字符识别褥到的文本) 的语言文本的自动处理，研究的主要内容是自动抽取新闻语料中出现的实体、 关系、事馋等内容，即对新闻语料中实体、关系、事件的识别与搓述。与 m u c 相比，目前的a c e 评测不针对某个具体的领域或场景，采用基于漏报( 标 准答案中有蔼系统输出中没有) 和误掇( 标准答案中没有焉系统输出中有) 为基 础的套评价体系，还对系统跨文档处理能力进行评测。这一新的评测会议 将信息抽取技术研究引向额的态度。 随着w e b 的出现和繁荣，信息抽取研究人员逐渐将兴趣转移到w e b 信 息抽取的研究上，涌现了许多算法和系统。其中最知名的研究项目是卡耐 基梅隆大学g 自动学习和发现中心打的“w e b 挖掘”网项目。该项目的霸 标是通过自动的从w 拍中提取信息，来创建大型的、结构化的数据库。其主 要的技术途径是研究概器学习算法，通过训练，能够自动提出信息。用户首 先定义要被提取的类( 比如公司、产品、雇员) 和关系( 比如“被雇佣”) ，并通 过w e b 提供彭l l 练样本，系统然蕨使用这些训练数据学习通用的信息提取步骤， 然后按照这个步骤从其他w e b 页面中提取信息。 另外，南加州大学信息科学研究所研制的一个信息集成系统i t ) ，其特点 是发展和应用了多种人工智能技术，访问各类信息源，构造了一个智能的动 态接口。系统设计者认为h t m l 具有严谨的结构，如层次树型结构，它采用 元组列表的形式来表达半结构化的信息。元组列表带有明确豹分隔符以区分 不同的元素。为了描述文档的结构，其设计了一种叫做嵌入式目录的表达形 式，用于表达半结构化文档的信息。其中，树时代表将被提取的信息，每一 个内节点代表一个同构列表( 如一个名字的列表) 或一个异构元组( 如一个包含 姓名、地址和序列号码的三元组) ，对待提取项目的识别被认为是一个对树的 搜索过程，搜索状态的改变依据是各个节点处的路标，路标的不同值导致搜 索转向不同的分支，生成的规则以一种路径表达式的形式给出。 美国纽约大学开展的l i n g u i s t i cs t r i n g t 5 颂离开始于6 0 年代中期并一鲞 延续到8 0 年代。该项目的主要研究内容是建立一个大规模的英语计算语法， 与之相关的应用是从医疗领域的x 光报告和医院出院记录中抽取信怠格式 3 哈尔滨工程大学硕士学位论文 ( i n f o r m a t i o nf o r m a t s ) ，这种信息格式实际上就是现在作者所说的模板 ( t e m p l a t e s ) 。另一个相关的长期项目是由耶鲁大学r o g e rs c h a n k 及其同事2 0 世纪7 0 年代开展的有关故事理解的研究，由他的学生o c r a l dd ej o n g 设计 实现的f r u m p 系纠6 】是根据故事脚本理论建立的一个信息抽取系统，该系 统从新闻报道中抽取信息，内容涉及地震、工人罢工等缀多领域或场景，采 用了期望驱动t o p - d o w n 脚本与数据驱动b o t t o m u p 输入文本相结合的处理方 法这种方法蘑来被许多信息抽取系统采用。 美国斯坦福大学的j h a m m e r 等人开发了一个信息提取工具i 刀，从w e b 上提取半结构化的信息。它主要是基于网页的结构，准确率高，但是对不同 的结构需要不同的抽取规则文件，而且定义规则文件非常繁琐，不具有通用 性。 犀蠹一些科研单像在某些领域范围感也对信息抽取进行了研究。 中国人民大学数据与知识研究所提出的基于预定义模式的包装器【8 j ，e l l 用户定义模式并给出模式与圈贾的映射关系，接着系统推导出规则同时生成 包装器。中科院软件所提出的基于d o m 的信息提出1 9 j ，该算法以文档对象 模型为基础，将所要提取的信息在层次结构孛的路径作为信息抽取的“坐标， 并以这个基本原理为基础设计了一种归纳学习算法来半自动化地生成提取规 则，然后根据提取规则生成类，将该类作为七数据源包装器组成的重要构件。 中国科技大学提出的基于多层模式的多记录网页信息抽取方法l l 谢，基本 思想是网页信息抽取只是利用多层模式来加以描述，以便能够利用各层模式 之阅褶互联系豹特点帮助动态获取各层串与页面蠹容具体摇述格式密切相关 的信息识别模式知识并最终再利用所获得的多层信息识别模式之时，完成相 应各个网页的具体信息抽取工作。 1 。3 研究内容及论文结构 本文针对研究中所存在问题，研究分析信息抽取的流程及信息抽取过程 中关键技术的实现，主要研究内容如下述。 ( 1 ) 阐述了信息抽取的基本思路，提出了一个广泛适用的信息抽取模型。 在分析w e b 信息抽取的难点，并瞬确w e b 信息抽玻的匿标，在研究x m l 结 4 哈尔滨工程大学硕士学位论文 构特性以及学习现有的信息抽取技术的基础上，提出了一种基于x m l 的w e b 信息抽取思路，利用标准的x m l 技术来解决w e b 信息抽取问题，提出一个 基予x m l 的透用w e b 信息抽取系统的设计方案以及本文进行w e b 信息抽取 的工作流程。 g ) 研究并实现了震j a v a 编程实现解析x m l 文件生成d o m 树的方法， 最终通过深度优先遍历算法将d o m 树转换成j t r e e 树，实现了用j t r e e 树直 观地显示d o m 树，实现橱型结构数据的图形化表示。 ( 3 ) 提出了一种基于x p a t h 的w e b 抽取规则表示方法，并对该方法中表 达信息抽取路径的x p a t h 表达式进行研究，设计并实现了一种基于d o m 树 结构的x p a t h 生成算法。 ( 4 ) 设计了一个基于w e b 信息抽取的原型系统。 本文共分4 章。各章安排如下。 第l 章介绍课题研究的背景和意义。阐述当前w e b 信息抽取所面临的问 题和x m l 技术在信息抽取中的作用。 第2 章是本文中用到的信息抽取的相关技术综述。介绍数据挖掘的概念、， 功能及其分类；介绍w e b 信息抽取的定义、特点、分类、抽取模型；介绍 x m l 技术的特点和结构，以及d o m 、x p a t h 和x s l t 技术等等。 第3 章针对信息抽取存在的主要问题，给出解决问题的基本思路和技术 路线，并对信息抽取的流程进行设计，是第4 章信息抽取系统设计与实现的 研究基础。 第4 章是本文研究的核心。首先，提出了一个信息抽取的通麓模型；其 次，以实际网页为例子，详细阐述对网页进行信息抽取的解决方案，包括抽 取流程中每一步采用的技术和解决技术难点的细节；最蜃，利用本文的原型 系统进行信息抽取的实验，包括对信息抽取的评价指标的介绍和实验结果及 其分析。 哈尔滨 程大学硕士学位论文 第2 章相关技术 w e b 上的信息抽取技术是露前较热的研究项露。这项技术处予不断地发 展中，是目前w e b 信息抽取研究的重点之一。本章分别依次介绍数据挖掘技 术、信息抽取技术、x m l 相关技术，这些技术是本文研究的基础。 2 。_ l 数据挖掘技术 2 。l 。1 数据挖掘概念 从1 9 8 9 年到现在，数据挖掘的定义随着人们研究的不断深入也在不断完 善，霸前比较公认的定义是f a y y a d 等给出豹数据挖掘是从数据集中识别出有 效的、新颖的、潜在有用的以及最终可理解模式的高级处理过程【1 1 1 。还有一 些褶近术语，如麸数据库中发现知识( k d d ) 、数据分析、数据融合以及决策 支持等【1 2 , 1 3 】。人们将原始数据看作是形成知识的源泉，就像从矿石中采矿一 样。原始数据可以是结构化的，如关系数据库孛的数据，也可以是半结构优 的，如文本、图形、图像数据，甚至是分布在网络上的异构型数据。发现知 识的方法可以是数学的，也可以是非数学的，可以是演绎的，也可以是归纳 的。发现了的知识可以被用于信息管理、查询优化、决策支持、过程控制等， 还可以用于数据自身的维护。因此，数据挖掘是一门很广义的交叉学科，它 汇聚了不同领域的研究者，尤其是数据库、人工智能、数理统计、可视化、 并行计算等方面的学者和工程技术人员。 篱单地说，数据挖掘就是从大量的数据中提取或者发现知识。在诲多场 合下，数据挖掘又被称为数据库中的知识发现。但是，更科学的说法是将数 据挖掘视为数据库知识发现的一个基本步骤。在这种情况下，数据库的知识 发现过程由以下几个步骤组成。 ( 1 ) 数据清理：消除噪声或者不一致数据。 6 哈尔滨工程大学碳士学位论文 ( 2 ) 数据集成：多种数据源可以组合在一起。它和数据清理一起被视为预 处理步骤，结果数据存放在数据仓库中。 ( 3 ) 数据选择：从数据库中检索与分析任务褶关的数据。 ( 4 ) 数据变换；将数据变换或统一成适合挖掘的形式，如通过汇总或聚集 操俸。在有些场合下，数据变换在数据选择过程之蔫进行，特别是在数据仓 库的情况下。 ( 5 数据挖掘：运用选定的知识发现算法，放数据中提取出用户所需要的 知识，这些知识可以用一种特定的方式表示或使用些常用的表示方式，如 产生式规则镣。 ( 6 ) 模式解释：对发现的模式进行解释，在此过程中，为了取得更为有效 的知识，可能会返回前面处理步骤中的某些步以反复提取，从而提取出更有 效的知识。 ( 7 ) 知识袭示：使用可视化和知识表示技术，向用户提供挖掘的知识。 2 2 数据挖掘功能 数据挖掘功能用予指定数据挖掘任务中要找的模式类型。数据挖掘任务 一般可以分为两类，描述和预测。描述性挖掘任务刻划数据库中数据的一般 特健，瑟预测牲挖掘任务剡在豢 ；誊数据上进行接辑，苏进孬预测醛4 1 尊 在很多情况，用户并不知道什么样的模式是有趣的，因此可能想探索多 种不同酶模式，以从中选择出良己感兴趣熬模式。这藏要求数据挖掘系统应 该熊够挖掘多种类型豹模式，以适应不嗣的需求。此外，数据挖搦系统应该 缝够发现各种粒度帮不同鳇抽象层靛模式，应当允许耀户绘出提示，指导或 聚焦有趣模式的搜索。 数据挖掘的功能以及可以发现的模式类型有类概念描述、关联分析、分 类和预测、聚类分橇、孤立煮分析和演变分析瑟辩。 ( 1 ) 类概念描述。数据可以与类或概念相关联。用汇总的、简洁的、精确 的方式描述每个类和概念可能是有用的。这种类或概念的描述称为类概念接 述。这神描述可以通过以下方法褥到，数据特征纯是麓标类数据的一般特征 或特性的汇总，数据区分将鏊标类对象的一般特性与一个或多个对拢类对象 7 烩尔滨工程大学硕士学位论文 ；眷i i l l l l l ! i i i i i i i 一 i l l 1 1 1 i i i i i l ly i i i i 宣；眷蒜 的一般特性比较。 q ) 关联分析。关联分析用于发现关联规则，关联规则描述了给定数据集 孛豹顼之闻的有趣联系。关联分析广泛疲霜予购物箍或事务数据分析。祆大 量商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定，如 分类设计、交叉赡物和贱卖分析等 嘲。 ( 3 ) 分类和预测。分类是找出描述并区分数据类或概念的模型的过程，以 便能够使用模型预测类标号未知的对象类。预测是构造和使用模型评估无标 号样本类，或评估给定样本可能具有的属性值或值嚣闻。分类和预测之阅的 区别在于，分类是预测类标号或离教值，丽预测是建立连续值函数模型。例 如，可以建立一个分类模型，对银行贷款的安全或风险进杼分类。阍对可以 建立预测模型，给定潜在顾客的收入和职业，预测它们在计算机设备上的花 费。 吣聚类分析。聚类将数据瓣象分组成为多个类或簇，在同一个簇中的对 象之闻具有较离的相似度，面不同簇中髀对象差别较大。与分类不丽的是， 它要划分的类是未知的。 岱) 孤立点分析。在数据库中经常存在一些数据对象，它们不符合数据的 一般模型。这样的数据对象被称为孤立点，它们与数据的其他韵部分不同或 不一致。孤立点可能是度量或执行错误所导致的。例如，数据库记录中有一 些入的年龄是一，这可能是这些入年龄没有被记录，而系统给未记录的年龄 的缺省值就是一。孤立点也可能是固有的数据变异厝的结果。例如，一个公 司总裁的薪水可能远远高于其他职员的薪水，他的薪承就成为了一个孤立点。 在许多时候，孤立点被视为噪声或遗产丽被丢弃，但是，在一些应用中，孤 立点可能会缀有震。铡懿，在嚣疗分橱巾，某些对多种治疗方式的不寻常的 反应数据可能成为孤立点，但是这些数据对予治疗却非常重要。对孤立点数 挺进行分析称隽孤立点分析u 玎。 ( 6 ) 演变分析。数据演变分析描述行为随时间变化的对象的规律或趋势， 并对其建模。这种分析可能包搔时闻褶关数据酶特征化、送分、关联、分类 或聚炎，但是它的不同特点包括时间序列数据分析、序列或周鲻模式匹配和 基于类似性的数据分析。 8 哈尔滨 工程大学硕士学位论文 宣昌i _ 1 1 i i i i i i l l ii i i i i i ii i i i l i 1 i 茹 2 1 3 数据挖掘分类 从不同的角度看，数据挖掘技术有几种分类方法，根据发现知识的种类 进行分类，根据挖掘的数据库的种类进行分类和根据采用的技术分类。 ( 1 ) 根据发现知识的种类分类。这种分类方法有总结挖掘、特征挖掘、关 联挖掘、分类挖掘、聚类挖掘、趋势分析、偏差分析、模式分析等。如果以 挖掘知识的抽象层次划分，又有原始层次的数据挖掘、高层次的数据挖掘和 多层次的数据挖掘。 圆根据挖掘数据库的类型分类。数据挖掘基于的数据库有关系型、事务 型、面向对象型、主动型、空间型、文本型、多媒体型、异质数据库等。 ( 3 ) 根据采用的技术，最常用的数据挖掘技术有人工神经网络它从结构上 模仿生物神经网络，是一种通过训练来学习的非线性预测模刑。可以完成分 类、聚类、特征挖掘等多种数据挖掘任务。 2 2 信息抽取技术 随着计算机的普及以及互联网的迅猛发展，大量的信息以电子文档的形 式密现在人们面前。为了应对信息爆炸带来的严重挑战，迫切需要一些自动 化的工具帮助人们在海量信息源中迅速找到真正需要的信息。信息抽取 ( i n f o r m a t i o ne x t r a c t i o n ) 技术的研究芷是在这种背景下产生的。 信息抽取的主要西的是从半结构或无结构的信息中抽取出特定的事实信 息( f a c t u a li n f o r m a t i o n ) 。比如，从新闻报道中抽取出恐怖事件的详细情况， 时闻、地点、作案者、受害者、袭击冒标、使髑的武器等；从经济新闻中抽 取出公司发布新产品的情况：公司名、产品名、发布时间、产品性能等；从 病人的医疗记录中抽取出症状、诊断记录、检验结果、处方等等。逶常，被 抽取出来的信息以结构化的形式描述，可以直接存入数据库中，供用户查询 以及进一步分析利用。 信息抽取技术的核心是能够从无结构或半结构的信息中识别用户感兴趣 的数据，并将其转化为更为结构化、语义更为清晰的格式。传统方式下，信 啥尔滨工程大学硕士学位论文 息抽取是通过被称作包装器的程序来实现的，下面给出信息抽取的定义。 2 2 1 信息抽取的定义及特点 信息抽取实际上是从无结构或半结构的信息中识剃感用户感兴趣的数 据，并将其转化为更为结构化、语义更为清晰的数据的过程，该过程定义如 下； 信息抽取过程i _ s w + sd 其中映射w 为包装器，完成从无结构或半结构的信息到结构化信息的 转换功能，s 为包含一组隐含并待抽取对象的无结构或半结构的信息源( 比 如，w e b 页蕊) ；sd 为一种更为结构化，语义更为清晰的数据结构( 如x m l ， 关系数据库等) 。 2 2 2 信息抽取的分类 随着需求的增加，近来涌现出了多种信息抽取工具，采用的技术也各不 相同，涉及多个研究领域，如数据库、人工智能、信息检索等。为了对信息 抽取技术作进一步研究，以增强本文原型系统的易用和实用性，有必要对现 有的信息抽取技术进行分析。 信息抽取技术有多种分类方式瑟渊1 ( 1 ) 按自动化程度分类 这种分类方法比较简单，分为人工方式、半盘动方式和全自动方式。 ( 2 ) 按抽取原理分类 根据冬种抽取工具所采用的原理将现有的工具分为矗类：基予自然语畜 处理方式的信息抽取、基于包装器归纳方式的信息抽取、基于本体方式的信 息抽取、基于h t m l 结构的信息抽取和基于w e b 查询的信息抽取嘲1 。 下面结合典型的系统，在语义的附加方式、模式的定义方式、规则的表 现形式、语义项的定位方式、对象的定位方式等几方面进行分析和比较。其 中结构化的数据称为对象；模式的定义方式主要两种，信息抽取之前给出瓣 1 0 哈尔滨工程大学硕士学位论文 象模式的称为先模式，反之称为质模式。 1 基于自然语言处理方式的信息抽取 这类信息抽取主要适用予源文档中包含大量文本的情况( 特别铮对于合 乎文法的文本) ，在一定程度上借鉴了自然语言处理技术，利用子句结构、短 语和子旬之间的关系，建立基予语法和语义的抽取规燹| j 实现信息抽取。目前 采用这种原理的典型系统有r a p i e r 口u ，s r v 啪1 ，w h i s k 。下面结合比较 典型的系统w h i s k 来详细说明这种方式的信息抽取。 w h i s k 系统既适用予结构纯、半结构化的文本也适用于自由文本。系统 主要是根据语义项的上下文实现感兴趣信息的定位。此时基本上没有利用到 自然语言处理技术，对这种情况这里不作详细的分析。对自由文本，系统首 先根据分割符将源文档分割成多个实例。在交互式的环境下，相同和一次呈 现给用户一组实例用户在可视化的环境下根据系统提供的实例标记出感兴 趣的信息并定义模式。系统使用语法分析器和语义类( 如人名、机构名) 分析 器，分析出用户标记信息的语法成分和对应的语义类，生成基于语法标记和 语义类标记的抽取规则，实现信息抽取。系统采用了先模式的方式。 这种基于自然语言理解方式的信息抽取技术，是将w e b 文档视为文本进行 处理的，主要适用予含有大量文本的w e b 页面，抽取的实现没有利用至u w e b 文 档独特于普通文本的层次特性。获得有效的抽取规则需要大量的样本学习； 2 基于包装器归纳方式的信息抽取 包装器归纳方式的信息抽取根据事先由用户标记的样本实例应用机器学 习方式的归纳算法，生成基于定界符的抽取规则。其中定界符实质上是对感 兴趣语义顼上下文的描述，郎根据语义项的左右边界来定位语义项。该类信 息抽取方式和基于自然语言理解方式的信息抽取技术最大的不同在于仅仅使 用语义项的上下文来定位信息，并没有使用语言的语法约束。采用这种原理 的典型的系统有s t a l k e r 渊，s o f t m e a l y t 2 s 3 和w i e n 嘲。下面根据具体酶 系统来详细分析这类信息抽取技术。 s t a l k e r 系统根据用户事先标记的样本页面和用户嵌入式分类树( 氍t e m b e d d e x tc a t a l o gt r e e ) 形式提供的页面的结构信息，应用逐步覆盖算法 ( s e q u e n t i a lc o v e r i n ga l g o r i t h m ) ，逐步归纳生成基于定界符的精确的抽取规 则，实现层次信息抽取。 l l 蛤尔滨工程大掌硕士掌位论文 嵌入式分类树在该系统中是一个重要的概念，它是用户根据页面结构定 义的嵌套模式，该树形结构一方面描述了页丽的逻辑结构，另一方丽提供了 模式信息和语义蓓惠橱中节点的名称) 。信息抽取遘过系统遍历e c t 来实现。 若根节点的孩子为l i s t 节点则在源文档中应用普通抽取规则抽取出多个对象 组成的信息浚，然惹再在获得的信息块中应用迭代规剃实现单令对象的定位， 若该u s t 节点的孩子为叶节点，则系统在上一步获得的单个对象构成的信息 块串执行升节点对应的掬取规则获得单个语义项。 该系统拳语义的附加和模式的定义是在用户宠义嵌入戴分类耩阶段完成 的，属于先模式的方式。信息定位的实质是使用左右边赛实现感兴趣信息的 识别。该系统在一定程魔上是按结构抽取和按文本抽取的结合，所以可以抽 取复杂的对象。但是规则中的定界符不仅仅是由h t m l 标记组成，嚣且还有某 类瓣赢经常出现的关键字组成。所以该类信息抽取不僵对页面豹结构有所依 赖，褥且对踺员的内容也有所依赖，要想获褥精确的抽取撬刘，必须进行大 量的样本诩练。 w e n 系统中事先蠢用户标记样本页面，系统根据页瑟逻辑结构的不同， 使用不露的痘发式舞纳算法生成不同的包装器。例如，产生一个h l r t ( h e a d ， b o d y ，t a i l ) 包装器。 该系统语义和模式信息是用户附加的。逶过感兴趣信息的左右边界实现 信息的定位。方式和上面系统类似，本文不谗介绍。只是该系统对复杂对象 不傲处理。 3 。基子本体方式的倍息摧取 该类信患抽取介绍主要利用对数据本身的描述倍息实现抽取，对网页结 构的依赖较少。由b y u ( b r i g h a my o n g 溉v e 懿魏势开发酶信息抽取工具淄1 孛采 用了这种方式。 b y u 系统事先需要毒领域专家采鞠人工方式书写某一领域的本体。系统 根据边界分割符和启发信息将源文档分割为多个搦述某一事物( 如汽车) 不同 实铡的无结构文本块，然后根据本体中的描述信患产生抽取规则，对任意无 结构的文本块进行抽取获得各语义项的值，最后将抽取出的结果放入根据本 体的描述信息生成的数据库中。 该系统中语义的附加和模式酶定义是在书写菜领域的本体的时候完成 1 2 晗尔滨工程大学礤士学稼论文 豹，朗人工方式附加语义信息，并且采用了先模式的方式事先确定了对象豹 描述。系统最大的优点是对网贾的结构依赖较少，只要创建的应用领域本体 足够强大丰富，系统可以对菜应焉领域孛的各种鹧页实现信息接取。但是 系统使用不太方便，某应用领域的本体只能由领域知识专家创建。另外由 于是根据数据本身实现锩惠抽取的，因就在减少了对阏页麴结掏莜赖翡嗣对， 增加了对网页中包含的数据结构的要求，如要求内容中包含时间、日期、王d 号 码等一定的格式内容。 4 基予粼，结构的信惠抽取 该类信息抽取技术的特点是根据w e b 页面的结构定位信息。在信息抽取之 前，通过解析器将w e b 文档解析成语法树( 或者一类似的撅签树t a g - t r e e ) ， 通过自动或者半自动的方式产生抽取规则，将信息抽取转化失对语法树的操 作实现信息抽取。采用该类介绍的典型系统有x w 黜谨溉铷等。下面对具有代 表性的系统进行分析，详细的磺究请参考对应的参考文献。 x w r a p 系统通过交互的方式，壶用户在样本页中指定抽取区域的起始 位置，系统确定整个抽取区域，并确定区域的类型，然后遴过可视纯的方式， 由用户在样本夏孛指定语义项( 翔表头) 以及与之对应的实铡，系统囊动产生 抽取规则实现信息抽取，最后系统利用启发信息获得数据闻的层次结构关系， 生成x 娩文档。该系统采用用户在鼹页中撬定语义顼鳇方式附加语义信息，即 将阏页的部分内容作为语义项，对应不同的区域类型( 如t a b l e ，l i s t 等) 采用不 同抽取规刹提高系统的灵活性翻效率。 5 。基于w e b 查询的信息抽取 使用w e b 的相关技术解决w e b 的问题称为w e b 技术规范。 在2 。2 。2 节所列的僖患抽取王其，采用了不露的原理，抽取规则的形式和 感兴趣信息的定位方式也各不相同，因此均不具有通用性。具有w e b 技术规范 的信息捶取，将w e b 信崽抽取转纯为使用标准的w e b 查诲语言对w e b 文档的查 询，具有通用性。采用该类技术的典型的系统有自主开发的原型系统 p q a g e n t 。1 。 p q a g e n t 系统采用了交互式的方式，系统通过祥本学习生成基于x o u e r y 的抽取规则，利用生成的抽取规则实现对相似结构页面的信息抽取。要求事 先运过颈处理使漂文档符合黼l 语法规范，然霜喜接剩用x q u e r y 孳l 擎执行 1 3 哈尔滨工程大学硕士学豫论文 i ；篙i i l l i l i i i i ini i i i i i i i i i ii i i i i ij y i i 6ini i i i i i； x q u e r y 查询语句实现信息抽取。 该系统采用先模式的方式，由用户附加语义并确定模式。抽取规则以 x q u e r y 豹形式表忝。应用抽取溉则可宣接定位到对象。相对于前面的系统， 该系统的抽取规则相当健壮，莉很强的表达能力，并统一了h t m l 和x m l 查 询，不仅便予最终用户使用，也便于律为包装器w r a p p e r ，由应用套询调用， 这是其它方法无法比拟的优点。但是系统对于网页结构的依赖性仍比较强。 2 。2 。3 信患抽取的模型 有关信息抽取的模型发展榴当迅速。在1 9 9 3 举的m u c 5 ，只提议了两 个自动产生规则系统：a u t o s l o g 和p a l k a 。之藤，大量的信息抽取系统获 得了发展：h a s t e n ，l i e p ，w r a p - u p ，c r y s t a l ，r a p l 嚣r ，w h i s k ，s r v , s t a l k e r , h m m 等等。尽管嚣前的文本信怠抽取系统在技术上存在差别，毽 是搬据采用的模型嚣不同霹以将他们分戚三类：基于词典的抽取模型，基于规 则的抽取模型和基于隐马尔可失模型( h m m ，h i d d e nm a r k o vm o d e l ) 的抽取模 型。 1 基予词典的信息抽取模型 基于词典蛉文本信息抽取模型需要首先构造抽取模式词典，然后使用该 模式词典从来标记文本中抽取所需信息。这些系统有a u t o s l o g , a u t o s l o g t s ， c r y s 裂选，s 聪圣弧s 砭烈，l i e p , p a l k a 等。文献 3 11 从训练示例中学习文本抽 取词典；文献【3 2 】应用多级自举算法圊时产生语义词典和抽取模式词典。基 于词典的文本信息抽取需要对概念结点进行定义，建立和维护相关的模式， 知识工作量魄较大，最佳词典的产生也托较麻烦，领域桷关性太强，应焉苓 是很广泛，常常和基予规则的模型结合在一起使用。 2 。基于规粼魏信悫按取模攫 基于规则的模型需要先构造抽取规则集，利用这些通用的规则从文本中 抽取信息。基于规烫| j 的模型也叫w r a p p e r 模型。w r a p p e r 是一种软件构件， 一个w r a p p e r 类一般针对菜一单一数据源中的一类页瑟，负责将数据和查询 请求由一种模式转换成另一种模式。在w e b 环境下，w r a p p e r 负责将隐含在 h t m l 文搂中的信息掏取出来，并且转换成匏够被迸一步处理的以菜静数据 1 4 哈尔滨工程大学硕士掌位论文 结构存储的数据。在彤式主，个w r a p p e r 类实际上是一类页瑟到该页面所 含元组集合的函数。典型的w r a p p e r 系统有w i e n ，s o r m e a l y , s t a l k e r , w h i s k , w r a p p e r - u p , t - w r a p p e r 等。文献【3 3 】使用监督学习，麸手王标记鹩调 练示例中推导出一个抽取规则集；文献【3 4 】讨论了自动构造w r a p p e r 类的有 效性和表达性，并描述了六个w r a p p e r 类。文献f 1 2 】| 以文档对象模受d o m 鸯 基础，将所要抽取的信息在d o m 层次结构中的路径作为信息抽取的“坐标茚， 并以这个基本原理力基确设计了一种翔纳学习算法来半自动地生成抽取规 剡，然后根据抽取规则生成j a v a 类。生成的j a v a 类可以作为w e b 数据源 w r a p p e r 类组成的重要构件。基于规则的抽取模型比较常用，在很多情况下 其耪发也菲常令人满意，僵无论是手工构造规则还是机器麴纳学习规则，都 比较复杂，适应性较差。 3 基予隐马尔可夫的信息捆取模型 利用h m m 进行文本信息抽取是种基于统计学习的信息抽取方法。 h m m 提供了适合自然语畜任务的强大的统计学基础。使用h m m 的劣势在 于两个必要静条件：模型拓扑斡先验观念和统计学技术所需的大量训练数据。 但现有的一些成熟的模型学习、训练和评估算法都其有缀离的计算效率，使 得模型易于建立。h m m 不需要大规模的词典集与规则集，虽然在莱些专门 领域精度不如基于规则盼模型，但它能健壮地处理叛数据，可移植性好，应 用领域广，有时甚至可以将规则的方法融入到