PDF《一种基于数据挖掘的 D eep W eb模式匹配方法》

・提出新算法 在分析基础上提出一种新的大规模模式 匹配算法 ;

・实验分析 全面评价该算法的查全率和效率.

1 相关工作 传统的模式匹配一般是手工操作 ,可以通过图形化用户接 口得到支持 ,当Web迅速发展时 ,手工模式匹配已经不能适应 这样大规模的模式匹配.近年来开发的自动或半自动模式匹配 第 5期 钟昕等 :一种基于数据挖掘的 Deep W eb模式匹配方法

47 系统集中在处理简单的 1: 1匹配上 [6 ] .代表性的有 : M ircosoft 研究的 Cupid方法 [13 ] , Stanford大学研究的 Sim ilarity Flooding方法[18 ] ,W ashington大学研究的 GLUE和LSD 方法 [14 -

16 ] , Leipzig 大学研究的 COMA方法 [17 ] 等.这些系统大部分可以完成 1:

1 的匹配工作 ,只有少数能完成 1: n的匹配 ,而且大都需要较多的 人工干预才能完成.并且它们目前的实验结果都只建立在小范 围数据集上 ,没有扩展到大规模动态数据集. 目前 ,为建立统一的查询接口而研究的大规模模式匹配技 术大致可分为两类 :基于模式的匹配和基于实例的匹配.基于 模式的匹配主要考虑查询接口的模式的标签信息 ,主要有以下 几种方法 :统计模型方法 [4 ] MGS (Hypothesis Modeling, Genera2 tion, Selection) 、 双重相关性挖掘方法 [9 ] DCM (Dual Correlation M ining) 、 基于聚类的交互式方法 [8 ] 、 基于语料库的匹配 [10 ] ;

基 于实例的匹配主要通过考虑查询接口模式的实例信息来进行属 性的匹配 ,根据实例来源的不同 ,分为基于 W eb实例的模式匹 配[11 ] 和基于在线数据库实例的模式匹配 [7 ] . 本文主要讨论基于模式的整体性匹配方法.就是输入一组 模式源 ,输出一个包含输入源中所有匹配的语义模型 ,如图 2所示.整体性模式匹配技术现已开发了两种方法 :全局性的评估 方法 (MGS)和局部性的评估方法 (DCM) . 图2整体性模式匹配方法

2 M GS和DCM 方法的分析与比较 2.

1 全局性评估方法 (M GS) 在对 Deep W eb的调查中 ,观察到同类资源有一些共同的 属性词汇.基于这种发现 , B. He等开发了 MGS框架 [4 ] .MGS 方法假设每个应用领域有一个存在的隐式生成模型 ,这样就可 以把模式看成从带着一些可能出现的行为的模型中产生的实 例.因此 ,模式匹配就被转化为发现含有一系列模式实例的隐 式模型.MGS方法主要分为三步 : (1) 假设建模 首先指定一个假设的隐式生成模型的参数 化结构.特别地 ,这样的模型应该可以捕获我们想要从事的模 式匹配工作的目标问题. (2) 假设产生 然后产生所有 一致 的模型 ,这些模型可 能能实例化观察到的模式示例. (3) 假设选择 最后选择与实例有充足统计一致性的模 型.这样的潜在模型是最可能产生输入模式的 ,因此它的结构 将能回答我们的目标问题. 2.

2 局部性评估方法 (DCM ) 复杂模式匹配也就是 m: n匹配.可以发现成组属性 (如:first name, last name)在查询界面中是同时出现的 ,因此是积极 相关的.而同义属性几乎不同时出现 ,因此是消极相关的.基 于此 B. He等开发了 DCM 框架 [9 ] ,它采用关联挖掘的方法 ,利 用积极相关和消极相关双重挖掘来同时处理简单的 1: 1匹配和 复杂的 m: n匹配 ,考虑到在处理稀疏模式数据、 微小消极相关 性以及高频异常属性方面的不充分性 ,开发了一个新的相关性 度量标准 H2 Measure,优于其他度量标准.DCM 方法主要分为 三步 : (1) 组发现 挖掘积极相关的属性以得到潜在的属性组 , 在此过程中 ,只有与其他属性组有同义关系的组才能保留下来. (2) 匹配发现 在组发现的基础上 ,挖掘消极相关的属性 组以得到潜在的复杂匹配.作为一种统计方法 ,关联挖掘能发 现正确的语义匹配 ,但是会由于巧合关联的存在而出现错误. (3) 匹配选择 在发现的匹配中进行筛选 ,构建模型. DCM框架中开发了一个迭代的算法 ,每次选最高可信度的匹配 来逐步构建模型 ,这样可以避免匹配冲突. 2.