（通信与信息系统专业论文）web数据挖掘算法研究.pdf

摘要 摘要 基于文本语义的文本挖掘系统的研究已经取得一定的成绩。但除了文 本之外，w e b 中还存在其他的海量媒体如图像、音频、视频等，这对数据 挖掘提出了新的机遇和挑战。 本文主要针对的是图像的高层语义特征进行研究。图像是我们能够获 捕的最有效的外界多媒体信息之一，并且在图像的各层特征中，顶层语义 特征( 又称上层特征) 是最重要的并且是最容易得到的特征。作为多媒体信息 的数据挖掘研究的初探，我们选择图片高层语义与文本语义作为多媒体信 息挖掘的研究对象。 首先，本文研究了网页主题提取和文本语义与图像语义，以及各种表 示模型。在此基础上提出了一种基于启发式规则的多媒体信息挖掘框架。 整个系统包括6 个模块：页面分析器、主题内容提取，文本图片信息抽取、 特征提取器、融合模型( 数据挖掘器) 、判别器、语义浓缩器。系统最重要的 模块是融合模型和语义浓缩器，这两个模块运用了很多自然语言处理f 比如 分词，特征项的提取，n e 命名实体等) 和数据挖掘的理论。 其次，本文采用关联矩阵在语义层次融合了文本语义和图像语义：进 一步把网页中的文本信息进行语义浓缩，研究了句子相似度计算算法并对 目前算法的不足做出改进，从而较为精确地说明网页中的图片，及其更加 丰富地说明图片的语义最后对基于启发式规则的多媒体信息数据挖掘系统 进行了封闭性的测试，实验表明该方法具有较高的精确率和较满意的效果。 在w i n d o w 2 0 0 0 下用j a v a 语言实现了各模块功能，实验表明我们提出的模 型是可行的。 关键词数据挖掘；w e b 内容挖掘；语义；融合模型；启发式规则；自然 语言处理 燕山大学工学颁十学位论文 a b s t r a c t r e s e a r c ho ft h et e x tm i n i n gs y s t e mt h a tb a s e do nt h et e x ts e n m n t i c sh a s a t t a i n e dv e r yg o o dr e s u l t s w i t ht h ed e v e l o p m e n to f t h ei n t e m e t ，i n f o r m a t i o no n t h ew e bh a sg r o w nt r e m e n d o u s l yb e s i d e st h et e x t ，t h e r ea r em a n yk i n d so f m e d i ao ni n t e r n e ts u c ha s i m a g e ，v i d e o ，a u d i oe t c ，w h i c hh a v eb e c o m e i n c r e a s i n g l yi m p o r t a n td a t ao nt h ew e b t h i sp r o v i d e sb o t hc h a l l e n g e sa n d o p p o r t u n i t i e sf o rd a t am i n i n g t h ei m a g ei so n eo f t h em o s ti m p o r t a n tm u l t i m e d i ao ni n t e r n e t ，a n di t st h e m o s te a s i l ya t t a i n a b l em u l t i m e d i af r o mt h ei n t e r n e t a n dt h ef e a t u r e so fi m a g e e x i s t e di ni m a g e se v e r yl a y e r , a n dt h es e m a n t i cf e a t u r ei si m p o r t a n ta n dt h e e f f e c t i v e ，w h i c hi so nt h et o pl a y e r s oi nt h i sp a p e r ，w ew i l ld ot h em u l t i m e d i a i n f o r m a t i o nm i n i n gb yu s i n gt h ei m a g et o pl a y e rs e m a n t i ca n dt e x ts e m a n t i c a tf i r s t ，t h i sp a p e r ，p a ym u c ha t t e n t i o no n w e b - p a g ei n f o r m a t i o ne x t r a c t i o n , i m a g es e m a n t i c ，t e x ts e m a n t i ca n de x p r e s s i o nm o d e l o nt h eb a s eo ft h e s e ，t h i s p a p e rm o t i o n sam u l t i m e d i ai n f o r m a t i o nm i n i n gf l a m e t h i ss y s t e mc o n s i s t so f s e v e nm o d u l e s ：p a g ep a r s e r , t h em a i nc o n t e n te x t r a c t i o n , t e x t i m a g ei n f o r m a t i o n e x t r a c t i o i l ，f e a t u r es e l e c t i o 玛f u s i o nm o d e l ，s e m a n t i cc o n d e n s a t i o n t h em o s t i m p o r t a n tm o d e l so ft h es y s t e ma r et h ef u s i o nm o d e la n dt h es e m a n t i c c o n d e n s a t i o n ，t h e s em o d e l su s et h en l ps u c ha ss p l i t t i n gw o r d ，d a t am i n i n g a ts e c o n d ，t h i sp a p e ru s e da s s o c i a t i o nm a t r i xf u s et h et e x ts e m a n t i ca n d i m a g es e m a n t i c ，a n dw ed i ds o m ew o r k so nt h es e n t e n c e ss i m i l a r i t ya c c o u n tt o c o n d e n s i n gt h et e x ti n f o r m a t i o nt oe x p r e s st h ei m a g ei n f o r m a t i o nm o r ep e r f e c t l y t h e nr e a l i z e st h e s ef u n c t i o nu n d e rw i n d o w s2 0 0 0i nj a v al a n g u a g e ，t h e e x p e r i m e n ts h e w st 1 1 a to u rf f a m e w o r ki se f f e c t i v e k e y w o r d sd a t am i n i n g ；w e bc o n t e n tm i n i n g ；s e m a n t m ；f u s i o nm o d e l ； h e u r i s t i cr u l e s ；n a t u r el a n g u a g ep r o c e s s ( n l p ) 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文 w e b 数据挖掘算法研究， 是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研究工作所 取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表或撰 写过的研究成果。对本文的研究工作做出重要贡献的个人和集体，均已在 文中以明确方式注明。本声明的法律结果将完全由本人承担a 作者签字：研锄 日期：甜1 年9 月工7 日 燕山大学硕士学位论文使用授权书 ( w e b 数据挖掘算法研究系本人在燕山大学攻读硕士学位期间在导 师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所有，本人 如需发表将署名燕山大学为第一完成单位及相关人员。本人完全了解燕山 大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送交论 文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山大学，可 以采用影印、缩印或其它复制手段保存论文，可以公布论文的全部或部分 内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密瓯 ( 请在以上相应方框内打“4 ”) 作者签名： 卯1 劝 导师签名： 日期：纠年月叼日 日期：9 乃姊 第1 章绪论 第1 章绪论 1 1 研究的背景及目的 数据挖掘技术【啦】自9 0 年代产生以来，其研究已经相当深入，研究范围 涉及到关联规则挖掘、分类规则挖掘、聚类规则挖掘、趋势分析等方面。 然而这些研究基本上是基于结构化数据，比如事物数据库，却很少有工作 研究异质、非结构化数据。 另一方面，当今的世界是信息的世界，作为人们传递信息的桥梁， i n t e m e t 起到了极大的作用。随着i n t c r n e t 的迅猛发展，网络已经发展成为拥 有3 亿页面且还在不断扩张的分布式信息空间，其中包括了从技术资料、商 业信息到新闻报道、娱乐信息等大量异质、非结构化的信息。甚至有工业 分析人士认为非结构化数据占了企业信息资源的8 0 ，而数据库中的数据 仅占2 0 。 从而，扩大数据挖掘研究对象的范围，更多的研究非结构化数据，如 文本、网络页面、e m a i l 等，成为数据挖掘的一个新的研究方向，由此网络 挖掘p 】、文本挖掘、多媒体挖掘便应运而生。 n t e r n e t 上的内容，越来越多的以多媒体的形式出现了( 比如视频、音频、 图片以及文本) ，所以从各种媒体中获得潜在的知识就成为知识发现领域中 的重要方面。w e b 挖掘也成为数据挖掘的几个热点，包括网站的数据挖掘 ( w e bs i t ed a a t am i n i n g ) 、生物信息或基因( b i o i n f o r - m a t i c s g e n o m i c s ) 的数 据挖掘及其文本的数据挖掘( t e x t u a lm i n i n g ) q a 的一个。w e b 数据挖掘是一门 涉及数据挖掘技术、文本处理技术、图像处理技术、人工智能技术的综合 学科。 w b b 挖掘从功能上可以分为总结、分类、聚类、趋势预测等。其中总结 是指按照一定的规则或者模型，将网页中的文档集合中的每个文档自动地 摘要出主要内容或者关键词。这样，用户不但能够方便浏览文档，而且可 以通过全文搜索、文摘搜索或者关键词搜索来使文档的查找更为容易。目 燕山大学工学硕士论文 前，有的门户网站中是通过人工对w e b 文档手动摘要，这大大限制了其索引 页面的数目和覆盖范围。可以说研究多媒体语义地融合和浓缩有着广泛的 商业前景和应用价值。 语义融合和语义浓缩是多媒体高效检索的前提，是海量多媒体信息库 的一种数据组织技术，高质量的语义融合和语义浓缩本可大大提高多媒体 检索( 比如图像检索、视频检索) 的速度和精度，其本身也是一种高效的检索 手段。自动文摘的生成可节约大量人力和财力，避免人工带来的周期长、 费用高、效率低等诸多缺陷。也可以减少在文本分类、文本搜索时服务器 系统运行成本过高的弊端。 本文首先讨论了数据挖掘，自动文摘的定义、功能、分类等问题，接 着重点研究了中语义融合涉及的关键技术问题，包括页面主题提取、文本 语义以及图像语义获取方法、特征提取和空间降维等方面，并详细叙述了 本文开发的基于启发式规则的多媒体语义融合和语义浓缩系统。 1 2 数据挖掘 数据挖掘，顾名思义就是从大量的数据中挖掘出有用的信息。随着计 算机应用的越来越广泛，每年都要积累大量的数据，运用数据挖掘技术在 这些数据当中本文可以找出这些有用的东西来。下面首先从历史和发展方 向等方面为数据挖掘做个概述。 1 2 1 数据挖掘的由来 我们现在已经生活在一个网络化信息化的时代，通信、计算机和网络 技术正改变着整个人类和社会。大量信息在给人们带来方便的同时也带来 了信息过量，难以消化的问题。人们开始考虑：“如何才能不被信息淹没， 而是从中及时发现有用的知识、提高信息利用率? ” 面对这一挑战，数据开采和知识发现( d a t am “n ga n dk n o w l e d g ed i s c - o v e r yd m k d ) 技术应运而生，并显示出强大的生命力。 另一方面，随着数据库技术的迅速发展以及数据库管理系统的广泛应 用，人们积累的数据越来越多。激增的数据背后隐藏着许多重要的信息， 2 第1 章绪论 人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。但目 前的数据库系统无法发现数据中存在的关系和规则，缺乏挖掘数据背后隐 藏的知识的手段，导致了数据爆炸但知识贫乏的现象。 数据挖掘使数据库技术进入了一个更高级的阶段，它不仅能对过去的 数据进行查询和遍历，并且能够找出过去数据之间潜在的联系。现在对数 据挖掘进行支持的三种技术已经发展成熟，他们是：海量数据搜集，强大 的多处理器计算机和数据挖掘算法。 数据挖掘的核心模块技术历经了数十年的发展，其中包括数理统计、 人工智能、机器学习等。今天，这些成熟的技术，加上高性能的关系数据 库引擎以及广泛的数据集成，让数据挖掘技术在当前的数据仓库环境中进 行了实用的阶段。 1 2 2 数据挖掘的定义 数据挖掘( d a t am i n i n g ) 是从大量的、不完全的、有噪声的，模糊的、随 机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜 在有用的信息和知识的过程。与数据挖掘相近的同义词有数据融合、数据 分析和决策支持等。 这里的知识包含是概念、规则、模式、规律和约束等广义的知识。原 始数据可以是结构化的，如关系数据库中的数据；也可以是半结构化的， 如文本、图形和图像数据；或是分布在网络上的异构型数据。发现知识的 方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。 因此，数据挖掘是- f - j 交叉学科，涉及到数据库技术、人工智能技术、数 理统计、可视化技术、并行计算等研究领域。 数据挖掘与传统的数据分析( 如查询、报表、联机应用分析) 不同，其本 质区别是数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数 据挖掘所得到的信息应具有先未知，有效和实用三个特征。但数据挖掘不 是为了替代传统的统计分析技术。相反，它是统计分析方法学的延伸和扩 展。 大多数的统计分析技术都是基于完善的数学理论和高超的技巧，预测 燕山大学工学硕士论文 的准确度还是令人满意的，但对使用者的要求很高。数据挖掘就是利用了 统计和人工智能技术的应用程序，把这些复杂的技术封装起来，使人们不 用自己掌握这些技术也能完成这些相应的功能，并且更专注于自己要解决 的问题。 1 2 3 数据挖掘研究的内容和本质 随着数据挖掘研究逐步走向深入，数据挖掘和知识发现的研究已经形 成了三根强大的技术支柱：数据库、人工智能和数理统计。目前数据挖掘 的主要研究内容包括基础理论、发现算法、数据仓库、可视化技术、定性 定量互换模型、知识表示方法、发现知识的维护和再利用等。 数据挖掘所发现的知识 4 1 最常见的有以下四类： ( 1 ) 广义知识( g e n e r a l i z a t i o nk n o w l e d g e ) 广义知识指类别特征的概括 性描述知识。根据数据的微观特性发现其表征的、带有普遍性的、较高层 次概念的、中观和宏观的知识，反映同类事物共同的性质，是对数据的概 括、精练和抽象。广义知识的发现方法和实现技术有很多，如数据立方体、 面向属性的归纳等。数据立方体方法的基本思想是实现某些常用的代价较 高的聚集函数的计算，诸如计数、求和、平均、最大值等，并且将这些实 现视图存储存在多维数据库中。另一种广义知识发现方法是加拿大s i m o n f r a s e r 大学提出的面向属性的归纳方法。这种方法以类s q l 语言表示数据挖 掘查询，收集数据库中的相关数据集，然后在相关数据集上应用一系列数 据推广技术进行数据推广，包括属性删除、概念树提升、属性阈值控制、 计数及其他聚集函数传播等。 ( 2 ) 关联知识( a s s o c i a t i o nk n o w l e d g e ) 关联知识反映一个事件和其他 事件之间依赖或关联的知识。如果两项或多项属性之间存在关联，那么其 中一项属性值就可以依赖其他属性值进行预测。最为著名的关联规则发现 方法是1 l a g r a w a l 提出的a p r i o r i 算法。关联规则的发现可分为两步。第一步 是迭代识别所有的频繁项目集，要求频繁项目集的支持率不低于用户设定 的最低值的规则。识别或发现所有频繁项目集是关联规则发现算法的核心， 也是计算量最大的部分。 4 第1 章绪论 ( 3 ) 预测型知识( p r e d i c t i o nk n o w l e d g e ) 预测型知识根据时间序列型数 据，由历史的和当前的数据去推测未来的数据，也可以认为是以时间为关 键属性的关联知识。目前，时间序列预测方法有经典的统计方法、神经网 络和机器学习等。1 9 6 8 年b o x 春r f l j e n k i n s 提出了一套比较完善的时间序列建模 理论和分析方法，这些经典的数学方法通过建立随机模型，如自回归模型、 自回归滑动平均模型、求和自回归滑动平均模型和季节调整模型等，进行 时间序列的预测。由于大量的时间序列是非平稳的，其特征参数和数据分 布随着时间的推移而发生变化。因此，仅仅通过对某段历史数据的训练， 建立单一的神经网络预测模型，还无法完成准确的预测任务。为此，人们 提出了基于统计学和基于精确性的再训练方法，当发现现存预测模型不再 适用于当前数据时，对模型重新训练，获得新的权重参数，建立新的模型。 也有许多系统借助并行算法的计算优势进行时间序列预测。 ( 4 ) 分类知识( c l a s s i f i c a t i o nk n o w m d g e ) 分类知识反映同类事物共同性 质的特征型知识和不同事物之间的差异型特征知识。最为典型的分类方法 是基于决策树的分类方法。它是从实例集中构造决策树，是种有指导的 学习方法。该方法先根据训练子集( 又称为窗口) 形成决策树。如果该树不能 对所有对象给出正确的分类，那么选择一些例外加入到窗口中，重复该过 程一直到形成正确的决策集。最终结果是一棵树，其叶结点是类名，中间 结点是带有分支的属性，该分支对应该属性的某一可能值。最为典型的决 策树学习系统是i d 3 ，它采用自顶向下不回溯策略，能保证找到一个简单的 树。算法“5 和c 5 0 都是i d 3 的扩展，它们将分类领域从类别属性扩展到数 值型属性。分类还有统计、粗糙集( r o u g h ! s e t ) 、线性回归和线性辨别分析等 方法。 1 2 4 数据挖掘的功能 数据挖掘通过预测未来趋势及行为，做出基于知识的决策。数据挖掘 的目标是从数据中发现隐含的、有意义的知识，主要有以下五类功能。 ( 1 ) 自动预测趋势和行为数据挖掘自动在大型数据库中寻找预测性信 息，以往需要进行大量手工分析的问题如今可以迅速直接由数据本身得出 燕山大学工学硕士论文 结论。 一个典型的例子是市场预测问题，数据挖掘使用过去有关促销的数据 来寻找未来投资中回报最大的用户。 ( 2 ) 关联分析数据关联是数据库中存在的一类重要的可被发现的知 识。若两个或多个变量的取值之间存在某种规律性，就称为关联。 关联可分为简单关联、时序关联、因果关联。关联分析的目的是找出 数据库中隐藏的关联网。 ( 3 ) 聚类数据库中的记录可被化分为一系列有意义的子集，即聚类。 聚类增强了人们对客观现实的认识，是概念描述和偏差分析的先决条件。 聚类技术主要包括传统的模式识别方法和数学分类学。 8 0 年代初，m c h a l s k i 提出了概念聚类技术，其要点是：在划分对象时不 仅考虑对象之间的距离，还要求划分出的类具有某种内涵描述，从而避免 了传统技术的某些片面性。 ( 4 ) 概念描述概念描述就是对某类对象的内涵进行描述，并概括这类 对象的有关特征。概念描述分为特征性描述和区别性描述，前者描述某类 对象的共同特征，后者描述不同类的对象之间的区别。生成一个类的特征 性描述只涉及该类对象中所有对象的共性。生成区别性描述的方法很多， 如决策树方法、遗传算法等。 ( 5 ) 偏差检测数据库中的数据常有一些异常记录，从数据库中检测这 些偏差很有意义。偏差包括很多潜在的知识，如分类中的反常实例、不满 足规则的特例、观测结果与模型预测值的偏差、量值随时间的变化等。偏 差检测的基本方法是，寻找观测结果与参照值之间有意义的差别。 1 2 5 数据挖掘未来研究方向 当前，d m k d 的研究方兴未艾，其研究与开发的总体水平仅相当于数 据库技术在7 0 年代所处的地位，迫切需要类似于关系模式、d b m s 系统和 s q l 查询语言等理论和方法的指导，才能使d m k d 的应用得以普遍推广。 预计数据挖掘的研究还会形成更大的高潮，研究焦点可能会集中到以下的 几个方面：发现语言的形式化描述，即研究专门用于知识发现的数据挖掘 6 第1 苹绪论 语言，也许会像s q l 语言一样走向形式化和标准化；寻求数据挖掘过程中 的可视化方法，使知识发现的过程能够被用户理解，也便于在知识发现的 过程中进行人杌交互；研究在网络环境下的数据挖掘技术( w e bm i n i n g ) ，特 别是在i n t e r n e t 上建立d m k d 服务器，并且与数据库服务器配合，实现w e b m i n i n g ：加强对各种非结构化数据的开采( d a t am i n i n ga u d i ov i d e o ) ，如对 文本数据、图形数据、视频图像数据、声音数据乃至综合多媒体数据的开 采，交互式发现，知识的维护更新。 就目前来看，将来的几个热点包括网站的数据挖掘( w e bs i t ed a t a m i n i n g ) 、生物信息或基因佃i o i n f o n m t i e s ) 的数据挖掘及其文本的数据挖掘 ( t e x t u a lm i n i n g ) 。下面就这几个方面加以简单介绍。 ( 1 ) 网站的数据挖掘( 又称站点挖掘)在对网站进行数据挖掘时，所需 要的数据主要来自于两个方面；一方面是客户的背景信息，此部分信息主 要来自于客户的登记表；而另外一部分数据主要来自浏览者的点击流 ( c l i c k - s t r e a m ) ，此部分数据主要考察客户的行为表现。但有的时候，客户对 自己的背景信息十分珍重，不肯把这部分信息填写在登记表上，这就会给 数据分析和挖掘带来不便。在这种情况下，就不得不从浏览者的表现数据 中来推测客户的背景信息，进而再加以利用。 就分析和建立模型的技术和算法而言，网站的数据挖掘和原来的数据 挖掘差别不是特别大，很多方法和分析思想都可以运用。所不周的是网站 的数据格式有很大一部分来自点击流，和传统的数据库格式有区别。因而 对电子商务网站进行数据挖掘所作的主要工作是数据准备。 ( 2 ) 生物信息或基因的数据挖掘生物信息或基因的数据挖掘则完全属 于另外一个领域，例如，基因的组合千变万化，使得患有某种疾病的人的 基因和正常人的基因到底差别多大? 能否找出其中不同的地方，进而对其 不同之处加以改变或者病交处理，使之成为正常基因，这都需要数据挖掘 技术的支持。 对于生物信息或基因的数据挖掘和通常的数据挖掘相比，无论在数据 的复杂程度、数据量还是分析和建立模型的算法方面，都要复杂的多。从 分析算法上讲，更需要一些可信的和好的算法。 7 燕山大学工学硕士论文 ( 3 ) 多媒体信息的数据挖掘无论是在数据结构还是在分析处理方法方 面，多媒体信息的数据挖掘和前面谈到的数据挖掘相差很大，如果把w e b 网页视为多媒体数据源，对w e b 网页内容的挖掘也属于多媒体信息的数据挖 掘。多媒体数据挖掘并不是一件容易的事情，尤其是在分析方法和多媒体 信息特征的选择和提取以及模型的建立方面，还有很多需要研究的专题。 1 3 国内外相关研究 为了有效地解决w w w 上大量多媒体内容安全问题，就需要分析w e b 页面布局结构并提取相应的逻辑完整的单元中媒体的内容。w e b 页面内容 分析是w e b 内容信息安全过滤的一个关键环节。这就需要先对w e b 页面布局 结构进行分析，把其中的主题内容抽取出来，并对其内容分类进行安全语 义分析。 w e b 内容实际上就是多种媒体通过超文本的有机连接。因此w 曲内容 安全分析在某种意义上就是对超文本中主要逻辑块中相关媒体语义进行分 析。w e b 内容分析涉及视频、音频( 包括语音识辨) 、文本( 语义分类与识辨) 、 图像语义分类与识辨等等，其分析方法涉及到统计学习、神经网络、机器 学习、数据挖掘理论技术以及自然语言处理等。对w e b 内容分析既可对 w e b 整体内容安全进行分析，也可对w e b 中某一逻辑块内容进行分析。考 虑到w 曲内容的动态性和实时性，其内容安全分析也应该是主动在线式学 习过程。利用网络c a c h e 技术，后台在线式智能化处理。w e b 内容安全分 析就是要建立多种媒体流语义融合模型，综合分析w e b 内容语义，从而可 确定出w e b 内容是否安全。 在完成了w 曲页面结构分析后，w e b 内容的语义的分析和关联分析就 成了网络安全过滤发展的瓶颈。由于w e b 页面的内容包含有大量的多媒体 信息如文本信息，图片甚至视频，音频等信息，要把各种不同的信息进行 融合，从而建立多种媒体信息流的语义融合模型。目前在这个方向的研究 尚处在初步研究阶段。 目前国内从事w e b 语义研究同样也处在初级阶段，基本上都是在多媒 体信息的语义研究还没有正式对w e b 内容的语义进行研究。有北京大学、 第1 章绪论 上海交通大学、哈尔滨工业大学、燕山大学等一些学校。其中北京大学、 清华大学、复旦大学、中科院、上海交通大学、哈尔滨工业大学等在文本 内容分析方面和图像语义方面已经取得了进展。大都也是对各种不同信息 分别进行研究，很少有融合在一起的。 清华大学提出了“文本为主”的多模态特征融合的新闻视频分类算法。 该算法采用文本为主，图像声音为铺的特征融合模式【5 】。 北京电子科技学院多媒体组，在研究新闻故事单元中提出了一个基于 视频和音频的双层单元融合模型，对新闻视频中视频和音频的特征提取以 及融合提出了一个新的算法等成果睁1 们。该课题组在文本方面也提出了基于 文本语义概念的中文文本分类的方法 1 l l 。 同时中科院和复旦大学在图像语义上的研究工作进展很快。不过，很 多都是基于反馈式图像检索的i m l 4 】研究。 9 0 年代中期国外提出v i s u a ls e m a n t i c s ，是在报纸新闻中通过从有文本 伴随的图片中提取视觉感觉信息。并基于v i s u a ls e m a n t i c s 建立一个p i c t i o n 系统口习。 哥伦比亚大学也做过类似的研究，通过把图像低层特征信息映射到高层 语义层，在联合文本的相识特征对图像在语义层上进行分类 1 6 , 1 7 1 。 加尼弗尼亚大学提出了一种多媒体数据分析的优化融合模型。但是所 提取的特征( 如图像的特征) 都是低层特征，并没有上升到语义特征层这个阶 段【1 8 】。g o o g k 和m i tc s a i l 提出了a u t o m a t i n gt h eu n w r a p p i n go f s e m a n t i c c o n t e n tf r o mt h ew o r l dw i d ew e b 1 9 】。也有不少对w e b 图像语义进行研究。 如澳门大学提出了基于相关文本的w e b 图像语义聚类算法，构造了一个 t e r ms e m a n t i cn c t w o r k 【2 0 】。不过，对于单纯的某一类信息的语义的研究进行 的却是很顺利。如只基于图像的或者只基于文本的。对图像语义的研究基 本上都是用在图像检索和查询方面【2 卜。3 1 。 1 4 论文研究的内容及结构 论文的内容和结构安排体现了本课题研究采用的方法以及实验的具体 过程过程，也体现了课题的逻辑性和延续性。本论文的内容和结构具体安 9 燕山大学工学硕士论文 排如下。 1 4 1 论文研究的内容 ( 1 ) w e b 页面主体内容分析在多媒体组已经把网页的主体内容提取出 来的基础上，对网页的主体内容如：文本，图像，相关链接等相关媒体语 义进行分析和语义扩展。 ( 2 ) w e b 主题内容语义融合建立数据库，把已经从网页中提取出来的 主体内容作为语料入库，建立一个有多种媒体的语料库。建立融合模型， 把语料库中各种媒体的语义进行融合。 ( 3 ) w e b 主体内容语义浓缩在建立多种媒体( 主要是文本和图像) 语义 融合模型的基础上，提出自动文摘算法模型来综合分析w e b 内容语义。 ( 4 ) 实验研究建立融合模型和语义浓缩算法对多种媒体语义分析，并 验证该模型得出的结果的准确率和精确度。 1 4 2 论文的结构 第1 章绪论，介绍了研究背景及目的，简述了数据挖掘、文本挖掘、图 像语义的相关历史和现状。 第2 章讲述了获取w e b 页面主题信息的常用技术以及在本文提出的系统 框架中所采用的技术。 第3 章讲述了获取文本语义和图像语义的常用方法，表示模型和研究概 况。 第4 章详细的描述了本文提出的一种启发式规则的多媒体信息融合系 统的融合过程以及实验结果。 第5 章详细描述了融合系统的最后一步语义浓缩算法和实验结果演示。 结束语，对工作进行了总结和对未来工作的展望。 1 0 第2 章获取w e b 主题内容的关键技术 第2 章获取w e b 主题内容的关键技术 2 1 主题抽取算法概况 在w e b 信息抽取领域，已经有大量的研究工作，但在必须指出的是， 不同于信息抽取，这里介绍的是提取主题内容而不是提取细粒度数据。在 内容提取领域，有一类方法着眼于探测同一站点网页中的一般模式。这些 方法都是一句这样的时候，“对同一个网站，那些于主题无关的部分常常有 着相同的内容和表现风格” 2 5 ，2 6 1 。b 孙y 0 s s e 产刀把页面之间相同的部分称为 模板( t e m p l a t e ) 。他们的实验表明删掉这些模板可以提高搜索引擎c l e v e r 的 准确率，而不引起召回率下降。l i n a n d h o 田】提出的系统( i n f o d i s c o v e r ) 首先 根据t a b l e 标签把网页分成若干个内容块，然后，词作为特征抽取出来并 计算每个词的熵值，进而计算每个内容块的熵值。最后通过设定熵的阂值 来划分有关内容块和无关内容块。尽管以上方法取得了定的效果，但都 是针对单一的站点，所以有一定的局限性。 另类方法是从另一种角度一视觉特征对页面结构进行挖掘。典型的 代表就是微软亚洲研究院提出的v i p s ( v i s i o n - b a s e dp a g es e g m e n t a t i o n ) 。它 充分利用了字体大小、背景颜色、空白区域等视觉特征，通过制定相应的 规则把页面分成了各个视觉信息块。这种方法能在一定程度上满足复杂页 面对算法的要求，但由于视觉特征的复杂性，运用的启发知识往往较为模 糊，需要人工不断地总结调整规则，所以如何保证规则集的一致性是一大 难点。 还有一类方法集中在对d o m 树的挖掘上。g u p t a 等人 2 9 1 通过保留一个 不断更新的广告服务器列表来移除广告，通过计算链接数非链接文字数来 移除链接列表。但是这种方法不能识别相关图片，也极易删除相关链接列 表。而且对于不同的网页，需要手工调整参数的闯值才能达到最佳抽取效 果。 另外，f i n n 等人【3 0 】将h t m l 文档看作字符和标签组成的序列，在字符 燕山大学工学硕士论文 集中的区域提取文字。这种方法仅适合主题文字集中的网页，如果段落间 有表格或链接等标签丰富的结构，就不能有效处理，而且该方法时间复杂 度高。k o v a c e v i c 等人【3 1 】利用位置将页面分为头、脚、左、右和中间区域。 这种方法的缺点是这种网页结构模板不可能适用于所有网页，而且这种划 分区域的方法也难以保证每个区域的语义一致性。 上述方法都忽略了一个有用的事实，那就是网页是为人设计的。研究 表明用户总是希望特定功能的部分出现在网页中特定的位置【3 “，如l o g o 一 般出现在网页的左上角，主题信息一般出现在网页的中部。基于这个事实， 本文的多媒体信息融合模型系统并没有采用上述的各种方法进行网页主题 的抽取。而是采用了由北京电子科技学院重点实验室封化民老师课题组的 研究成果一基于新型坐标树的页面分析和内容提取方法 2 5 2 6 i 。 2 2 融合模型采用的主题提取系统结构 图2 1 给出 w e b 页面分析和内容提取系统的模型【2 4 1 ，它由6 个功能器组 成：h t m l 解析器、坐标计算器、遍历器、页面分析器、g r a p h 生成器和相 关链接识别器。 图2 1 信息提取框架 f 嘻2 - 1t h ei n f o r m a t i o ne x t r a c t i o nf r a m e w o r k 解析器将h t m l 文档转化为d o m 树，本系统采用c y b e r n e k oh t m l 1 2 第2 章获取w e b 主题内容的关键技术 p a r s e r 3 2 , 3 3 。坐标计算器就是计算d o m 树中各节点的位置，并将d o m 转换 为坐标树。遍历器遍历坐标树，删除无关节点，遇到分块节点送页面分析 器计算其特征并删除无关内容块。g r a p h 生成器计算叶节点间的空间关系。 相关链接识别器保留相关链接。最后融合遍历器和相关链接识别器的结果， 输出只含有主体内容的h t m l 文档。更加清晰的信息提取系统构架如图2 2 所示。 图2 - 2 信息提取系统 f i g 2 - 2i n f o r m a t i o ne x t r a c t i o ns y s t e m 2 3 信息提取系统主要构建以及算法描述 信息抽取系统是构建整个多媒体信息融合模型系统的前提条件，信息 抽取系统的准确率对后期的网页多媒体主题信息的研究( 信息融合，语义浓 缩1 有着重要的影响。 2 3 1 分块及其页面结构分析算法 网页设计之初，作者通常会先做一个模板来为后续设计作指导。这个 模板一般会包括以下几个部分：头、脚、左、右和中间区域。识别这几个 区域对于本文来说是极其有用的，因为抽取网页的主题信息就是要保留位 燕山大学工学硕士论文 于网页中间区域的内容，而删除位于其它区域的内容。 经过对各种主要的页面分析方法的分析，在本文提出的多媒体信息融 合模型中的页面分析器决定采用对网页进行分块的方法，鉴于现在t a b l e 标签广泛应用于页面布局【2 引，该系统将t a b l e 、t d 和d i v 标签作为分块 节点。这样在页面结构分析过程中，只对分块节点进行判断。 页面结构分析算法首先遍历器从 节点开始深度优先搜索坐标 树，当遇到分块节点，该系统将依次判断它是否属于头、脚、左和右区域。 如果属于其中任何一个区域，它将被删除。 否则，该页面分析系统将考察该节点的子孙节点中是否含有分块节点， 如果有则表明该节点含有的语义并不唯一，是由几种区域或者一种区域的 几个分块的内容构成的，它将被再次分割；如果没有，该系统则认为它是 一个不可再分的内容块，该系统将计算其局部相关度( 0 2l c 表示) ，如果大 于给定的阈值( 如何设定阀值，将在后面讲述) ，它将作为无意义的内容块被 删除，反之，它将被保留。上述过程将一直循环下去直到所有的分块节点 都被划分到上述几个区域中。 该算法采用了一种分块节点的高宽比来动态的选取阀值的方法。高宽 比越小，阀值就越大，反之高宽比越大，阀值就越小。也就是说越细长的 块( 比如网页左右两边的内容) 就越有可能被删除。阀值t 的计算公式，如式 ( 2 ，1 ) 所示。 t ：b a s p t h r e s h d 埘+ f ( h e i g h t 。i ( 2 1 ) 一 w i d f h 式中f ( x ) = _ 生。h e i g h t 和w i d t h 分别表示块节点的高和宽度，口，b 和 d 工十c c 都是常量。已经通过实验验证，当b a s et h r e s h o l d = 1 5 0 ，a = 4 0 ，b = 2 0 ， e = 1 时，该抽取系统达到最佳性能。 探测左部和右部的方法与上述的方法类似。因为左右区域的划定依赖 于网页的宽度，所以阈值也需要能对网页宽度自适应。通过试验和观察获 得最优化的结果，在使用中定义网页左1 4 的区域为左部，右1 4 的区域为 右部。 1 4 第2 章获取w e b 主题内容的关键技术 2 3 2 计算局部相关度 通过对一些网页的观察，本文发现仅靠位置是不足以区分主题信息和 无关信息的，因为位于中间区域的内容并不都与主题相关。在对该系统的 研究中，发现与主题无关的“内容块”总是含有大量无关链接和极少非链 接文字。于是该提取系统定义了局部相关度来表示节点与主题相关的程度， 其计算公式，如式( 2 2 ) 所示。 l c ( b l o c k ) = l i n k c o u n t ( b l o c k ) c o n t e n t l e n g t h ( b l o c k ) ( 2 2 ) 式中b l o c k 代表一个分块节点，l i n k c o u n t 代表该节点中链接数之和， c o n t e n t l e n g t h 代表该节点中非链接文字数之和。 如果分块节点的局部相关度大于阚值( 实验中局部相关度阈值取为 o 5 1 ，那么该节点将被删除。这种方法对于移除链接从而保留主题文字已经 被g - u p t as , k a i s e r 2 9 1 证明是行之有效的，但缺点是极易删除与正文相关的链 接和图片。为弥补这种不足，我们将分别识别相关图片和相关链接。 相关图片通常为j p g 格式，其尺寸往往比较大，并且高宽比一般不大 于2 5 ，最重要的是，相关图片往往位于一个内容丰富的块中，其周围总有 一些描述性的文字。根据这些特点，该系统制定了相应的启发式规则来识 别并保留相关图片。 网页中相关连接的判别也是非常重要的，对于相关链接的识别算法将 在随后介绍。 在上述过程中，值得一提的是，为了防止主体内容被误删，该主题提 取系统采取一种“回滚”机制：每在网页上删除一个区域都要和此次删除 前的网页进行比较，如果发现删除的内容过多。这次删除动作将被取消， 网页回到此次删除前的状态。 2 3 3 g r a p h 生成算法 如果能够知道网页中各个节点的坐标以及相邻节点间的空间关系，则 将能更好地理解各个节点的语义并有助于探测如相关链接这样的逻辑单 元。因此该信息提取系统建立了网页的图( g r a p h ) 模型。首先系统指定坐标 1 5 燕山大学工学硕士论文 树中所有的叶节点为g r a p h 中的基本元素，然后分析相邻基本元素间的边 界( e d g e ) 。 假设l 代表所有的基本元素，p ，q e l ，p ，q 分别代表p ，q 在屏幕上 所占据的区域。如果p ，q 相邻，则有四种可能的位置关系：p 在q 左边、 右边、上边或下边，相应的就有四种边界来代表p ，q 之间的区域，分别为 上边界，下边界，左边界，右边界。 为了量化的表示边界，我们定义边界包含两个属性，分别是a l i g n 和 d i s t a n c e 。a l i g n 表示边界的排列方式( 与x 轴平行或垂直) ，d i s t a n c e 表示边 界的宽度。 2 3 4 相关链接识别算法 相关链接通常是一系列竖状的链接，并且这些链接总是以“相关链接” 等敏感词作为标题。根据这些特征，我们制定了以下的启发式规则。 设，如乙代表g r a p h 上的文字链接，对于相邻的每一对，。，+ l ， 其对应的边界应该与x 轴平行；对于相邻的每一对f 。，f 。，不存在其它元 素与z 。有上边界，与，。有下边界，也就是说没有元素位于，t + 。之间。如 果有，。，。满足以上条件，检查位于t 上边的文本元素，该边界宽 度不应大于d ( 在实验中d = 5 ) ，且该文本节点中的文字应为“相关链接”、 “相关新闻”、“相关报道”等敏感词( 多为网页中直接给出并且很容易判断 的词) 。敏感词可以根据需要继续添加。 如果以上条件都满足，这些链接被识别为相关链接。 2 4 结果演示 图2 - 4 和图2 5 演示了使用该主题提取系统对网页页面进行主题抽取的 试验结果。通过对图2 - 4 和图2 5 的对比，可以很清楚的看到，主题信息抽 取之前与主题信息抽取之后网页页面的差别：网页周边的广告图片被删除 掉了，并且不相关的链接也被删除掉了，只留下了网页中的主题信息。 试验结果说明该主题信息提取系统的试验结果能够很好的满足多媒体 信息融合模型的要求。 1 6 第2 章获取w e b 主题内容的关键技术 图2 - 4 抽取主题信息之前的页面 f i g 2 - 4t h ew e