基于整体模式匹配的深度网集成系统的研究

邵秀丽， 孙 杰， 侯乐彩

(南开大学信息技术科学学院，天津300071)

0 引 言

Deep Web研究目的是为用户提供一个统一的访问途径以自动获取和利用分布在Web上的一些Deep Web的信息。尽管DeepWeb中几乎包含了所有我们需要的信息，但是要想以人工方式利用这些信息实际上是一件非常困难的事情，而Deep Web数据集成正是为了以尽可能自动的方式来达到对Web数据库中信息有效利用的目的[1-2]。因此，具有很好的研究和应用价值。

本文研究并设计实现了DeepWeb集成系统，以通过一个统一的接口访问所有分布的Web数据源，获得质量优结构好的信息[3]。其中，DeepWeb查询接口模式抽取部分本文采用了人工介入配置形成所需信息，从而保证基础研究的模式信息的准确性。模式匹配部分是DeepWeb信息集成的基本问题，本文提出了新相关度度量标准 S-measure进行数据挖掘的整体性模式匹配方法[4-6]，利用整体性方法进行的模式匹配有别于传统1:1的匹配，不仅可以发现简单的1:1匹配，还可以发现m:n的复杂匹配，匹配精确度和效率均很高。它可以在两个模式之外挖掘上下文信息，比如，跨多源的相似属性，属性间的共存模式等。在完成了模式匹配给出输入模式集的属性间的同义匹配结果的基础上，本文设计实现了面向Deep Web对象的查询接口集成系统。根据源查询接口的属性出现频率和属性模式匹配结果，选择全局查询接口的属性，然后生成属性对应的表单元素，主要是基于属性在模式中出现的频数和属性间的同义信息，最终提交集成的全局模式给用户，从而生成全局的查询接口，方便用户实现查询。

1 集成系统的架构设计

本文将特定领域(如图书领域)的多个Web查询接口页面作为输入，从查询接口中抽取模式信息；然后通过数据挖掘的方式进行模式间的复杂匹配，这部分处理功能主要包含：数据预处理、匹配发现和匹配构建；基于匹配结果生成全局的查询接口，从而完成查询接口集成。系统的架构如图1所示，其中：

(1)查询接口模式抽取：主要完成从Html格式的Web查询接口中抽取模式信息的功能。由于作为系统输入的Web查询接口页面是Html格式的，而且包含许多接口外的无用信息，所以在进行模式匹配之前，需要设计一个接口抽取器，用于实现从各个参与Deep Web的接口中抽取模式信息。本文在设计的DeepWeb搜索原型系统中，采用了人工获取这些接口信息，以避免因模式数据的错误而引起的匹配错误。并配置各种所需要抽取的模式信息，包括属性信息、元素信息、元素值域、查询接口网址。

(2)查询接口模式匹配：对于人工抽取出的原始模式数据(其中的接口模式包含属性信息为商品名、著译者等)进行模式匹配。方法是：先对这些模式数据(主要属性名)进行预处理，使它们适于数据挖掘。而后是对这些人工采集的模式进行匹配发现，该部分工作是模式匹配的核心部分。为发现可能的匹配，本文提出了一种相关性挖掘算法——整体模式匹配算法，算法实现的思想是：首先使用正相关挖掘挖掘出可能的成组属性；然后使用负相关挖掘出可能的匹配(即同义属性)；最后进行匹配构建工作，首先按照匹配的相关度排列发现的匹配，然后采用一致性约束策略筛选出最可信、最一致的匹配。

(3)查询接口集成：本文基于模式匹配的结果和源Web查询接口的属性信息共同选择全局查询接口的属性。具体做法是选择在源查询接口中出现次数较多的属性，每组同义属性(即每个匹配)中选择一个代表性的属性，且尽量选择包含属性多的成组属性。然后再生成属性对应的表单元素及其对应的元素值域。

图1 系统工作流程

2 人工接口模式抽取

在模式匹配之前，需要得到一个带有属性信息的模式集。这就需要对同一领域(如图书)的查询接口进行模式抽取，可以进行人工抽取[7]，也可使用成熟的数据抽取工具自动抽取[8-9]。本文采用人工抽取的方法，对查询接口的属性信息进行配置。

为更好地开展模式抽取工作，首先要清楚需要抽取哪些信息。分为3块工作：首先，为了进行模式匹配，必须抽取属性信息及属性与接口模式的对应信息；其次，为了生成统一的查询接口，进而将用户查询转换为到各个数据源的查询，必须抽取属性对应的表单元素信息，包括元素类型、元素名称、元素值域等；最后，为了提交查询从而得到结果数据，必须抽取接口的网址信息和提交方法信息。

2.1 配置接口信息

由于一个查询接口包含多个属性，一个属性可能包含多个元素，一个元素包含一个表单控件和相关的描述信息，一个元素可能对应多个候选值，所以采用查询接口、属性、元素、元素值4级表结构来存储接口信息。

首先配置查询接口基本信息，包括站点名称、网址、提交action、提交方法、所属领域等，如图2所示。存储网址、方法信息是为了完成统一查询接口到Web查询接口的映射，向Web查询接口提交查询请求，并得到返回的结果。

图2 配置接口信息

然后为每一个查询接口配置对应的属性信息，主要包括属性名称，如图3所示。为了更适合于后续的模式匹配挖掘算法，这里对属性标签做一些处理，使属性名称尽量简化：例如：①去除一般意义上的常用词，如“的”、“了”和英语中的“on”、“of”、“the”等；②去除 Web常用词，如“搜索”、“页面”、“查询”等；③去除网站名称词，如“卓越”、“当当”等；④去除领域词，如“图书”、“中药”等。

图3 属性配置

接着配置属性对应的元素信息，包括元素标签、表单名称、表单Id、表单类型、表单值数据类型、默认值等，如图4所示。

图4 元素配置

最后配置元素对应的值域，如图5所示。

图5 元素值域配置

配置元素信息是为了转换生成Web查询接口的查询串，完成全局查询接口元素到Web源查询接口元素的匹配，从而在后续的查询转换时获得查询串的参数名称，值域对应查询串的参数值。

2.2 数据预处理

上面在配置属性信息时，已做了初步的简化工作，下面在此基础上继续对属性信息进行句法合并处理：通过衡量属性名称和属性值域的句法相似性合并属性实体，例如可通过名称相似性将“title of book”合并到“title”。

通过考察语言相似度来合并句法相似的实体是一种常见的数据清洗技术[10-11]。本文通过分别衡量属性名称和属性值的句法相似性设计了基于名称的合并和基于值域的合并。句法合并将会减少属性实体的数目，增加单个的属性实体在不同模式中出现的频数，从而可以增强相关挖掘的效果。

(1)基于名称的合并

如果两个属性的名称相似，则合并它们。观察发现大多数DeepWeb数据源使用简洁的核心的属性名称(如title)，而其它的数据源使用这些核心词汇的变形(如titleofbook)。因此，如果属性Ap的名称包含属性Aq的名称 (即Ap的名称是Aq的名称的变形)而且Aq比Ap更常出现(即Aq是大多数)，则认为Ap是与 Aq名称相似的。这种基于频率的策略可以避免绝对合并。例如，在Books领域，lastname就不会被合并到name中，这是因为lastname比name更常出现，这种情况下本文认为它们是两个不同的属性实体。

(2)基于值域的合并

如果两个属性的元素的值域相似，则合并它们。对查询接口来说，本文认为属性的元素值域是其可选择的值的集合。这些值在Web表单中经常以select控件选项或radio button的形式出现。本文只考虑带有string类型值的属性，因为对于其它数据类型的值来说，值相似通常并不意味着属性相似。例如，在机票领域，passengers的整型数值与connections的整型数值非常相似，但事实上它们表示不同的意思。

将属性的元素可选值看作单词包(即，单词频数的计数)，称为集合值，属性A的集合值记作VA。对于单词w，其在VA中的频率记作。属性Ap和Aq的值域相似性即和的相似性。理论上，任何合理的相似度函数在此都适用。本文特别选择作为相似度函数。

例如：假设机票领域的 3 个模式：S1、S2、S3，S1的包含的属性实体为，S2包含的属性实体为，S3包含的属性实体为。

属性实体triptype出现在S1和S2中，所以其集合值为Vtrip type={round:2,trip:2,one:2,way:2,multi:1,city:1}，其中每个单词后面标着它的频数。特别地，Vtriptype(round)=2，因为round在两个模式中都出现了。类似的Vtickettype={round:1,trip:1,one:1,way:1}。所以根据上面的相似度函数可以得到

由于相似度数相当大，因此两个属性是相似的，可以合并为一个属性实体trip type。

3 查询接口模式匹配

本文的模式匹配工作由匹配发现和匹配构建这两个前后相连的步骤组成。将模式匹配问题分成上述两个处理功能模块，明确定义两个模块之间的接口，这样就可以建立模块化的解决方案。在匹配发现和构建匹配之前，需要对输入的模式数据进行数据预处理工作，即将输入的模式数据属性名尽量简化，使其容易被挖掘。

3.1 匹配发现

匹配发现工作的目的是在属性信息的基础上应用本文的整体模式匹配算法来发现所有候选匹配，此候选匹配集中即包含简单的1:1匹配，也包含复杂的m:n匹配，而且可能包含n元复杂匹配。这些候选匹配可能是正确匹配也可能是错误匹配，这一步是模式匹配工作的重点，目的是从特定领域的多个接口模式中获得不同属性间的所有可能的语义同义信息[12-13]。工作流程是首先在属性上进行正相关挖掘，以发现可能的成组属性，然后将成组属性加入源模式信息，在此基础上再进行负相关挖掘，发现可能的同义属性。

本文将查询接口看作一个包含一系列属性实体的扁平模式。属性实体定义为属性名称和属性元素。每个属性实体被赋予一个唯一的属性标识(简称为属性)。为方便描述，在属性实体上进行匹配时，使用属性名称作为属性标识。

匹配发现步骤的形式化描述为：给定一个同一领域的模式集I={Q1,Q2,…,QN}作为输入(其中Qi为一个属性集)，发现所有的候选匹配R={M1,…,MV}，其中Mj为一个候选的n元的复杂匹配，其中是一个属性组(即语义上等价于另一个属性或另一个属性组的一组属性)，而且。每个Mj表示属性组间的语义同义关系，而每个表示中属性间的成组关系。

相关挖掘的一个关键问题是相关度的度量方法，即如何计算多个属性的正相关度和如何计算多个属性、属性组的负相关度。为解决这个问题，本文设计了一个具有Apriori特征的度量方法，由计算两个数据项的相关度开始，逐步计算3项、4项、……数据的相关度。

3.2 匹配构建

匹配构建的工作重点是从候选匹配集中采用一致性约束策略选择语义上最可信、最一致的子集作为最终的匹配结果，这步工作就是对匹配结果的优化，本文使用基于相关度分值的匹配排列和基于一致性约束的选择策略。

匹配构建工作的主要目的是在候选匹配集中选择可信度高的、不互相冲突的匹配。

给定发现的候选匹配集R={M1,…,MV}，匹配构建工作包括：匹配排列和匹配筛选。

在匹配排列阶段，按照特定的排列标准C给所有的候选匹配排序，排序后用RC={}表示。以往的模式匹配算法几乎都是以发现成对语义相关匹配为目的的，在此类模式匹配算法中，匹配排列阶段都非常简单，直接根据匹配发现步骤计算出的分值排列候选匹配。然而，在本文的寻找n元复杂匹配的方案框架下，这种简单的排列策略就不再适用了，所以开发出了一种不同评分策略Cmax。

匹配筛选阶段，选出RC的一个子集作为最后的匹配进程的输出。大多数模式匹配方案都基于一致性约束选择候选匹配，比如两个覆盖同一个属性(本文称之为冲突)的匹配不能同时被选中，本文也采用这样的一致性策略来筛选候选匹配。

4 查询接口的集成

Deep Web数据集成的核心即是形成统一的查询接口界面，即查询接口的集成。查询接口集成的目的是为用户提供统一的全局查询接口，用户在此接口界面上输入查询信息，点击查询后即可获得多个Web源的查询结果[14-15]。

本文基于模式匹配的结果和源Web查询接口的属性信息共同选择全局查询接口的属性。方法是选择在源查询接口中出现次数较多的属性，每组同义属性(即每个匹配)中选择一个代表性的属性，且尽量选择包含属性多的成组属性。然后再生成属性对应的表单元素及其对应的元素值域。最后基于接口模式和模式匹配结果形成一个全局的查询接口。查询接口集成包括属性选择，表单元素生成和元素值域生成3部分工作。

4.1 属性选择

首先统计各属性和属性组在接口中出现的概率，存入数据库相应字段。研究表明，出现概率在20%以上的属性占领域内所有属性的80%，据此选择出现概率20%以上的属性和属性组作为候选属性(组)。

考虑到后续的查询转换步骤，知道从属性组到单个属性的转换要比从单个属性到属性组转换更容易，前者只需要简单的将各个属性对应的元素值组合起来，而后者需要对属性的元素值进行拆分。所以在进行属性选择时优先选择属性组，而且优先选择包含属性较多的属性组。综合以上分析，属性选择规则如下：

第一步，对于在同义属性Mj：Gj1=Gj2=…=Gjw中出现的候选属性(组)，按以下规则选择一个Gjk代表此同义概念出现在最终的查询接口中：

(1)若Mj包含成组属性，且成组属性出现概率在20%以上，优先选择成组属性；若无成组属性，再选单个属性；

(2)选择成组属性时，优先选择包含属性多、出现次数多的组，相同时，任选其一；

(3)选择单个属性时，优先选择出现次数多的属性，次数一样多时，任选其一。

第二步，对于不在同义属性中出现的候选属性Ai，此属性需出现在最终的查询接口中。

将选出的属性和成组属性存入新的数据库表 generalAttribute和 GeneralGroup。

4.2 表单元素生成

统一查询接口的属性确定之后，就需要为各个属性生成表单控件[10]。通过4.1知道，查询接口中的表单控件类型一般有text、radio、checkbox、select、textarea这5种，其中radio和select都是单选，其效果是相同的；text和textarea都是文本输入框，也认为其作用是相似的。因此，出现在最终的统一查询接口中的表单控件类型可以简化为text、select、checkbox这3种。

考虑到后续的查询转换步骤，很明显将select的值转换为text的值要比从后者到前者的转换容易得多，因为text的值是用户输入的，很难保证其在select中有对等的值。因此，系统更倾向于使用select控件。类似的，当select和checkbox比较时，倾向于使用select控件，这是因为单选到多选的转换比多选到单选的转换相对容易得多。当checkbox和text比较时，倾向于使用checkbox控件。综合以上分析，为属性生成表单控件时，具体做法如下：

对于上文选出的属性，考察它即其同义属性在原始查询接口中包含的表单元素的元素类型、元素数目及其出现的次数。

式中：C(n)select——对应n个select元素的属性出现的次数，其它类似。

GmaxSelect=max(G(n1)select,G(n2)select,…,G(nm)select)，GnumberSelect为取到最大值的G(n)select对应的nj。

GmaxCheck、GnumberCheck与 GmaxText、GnumberText也作类似定义。

比较 GmaxSelect、GmaxCheck、GmaxText的大小，可得：

(1)若 GmaxSelect>=GmaxCheck且 GmaxSelect>=GmaxText，则属性对应的表单控件是GnumberSelect个select列表，元素名称为select1、select2、…；

(2)若 GmaxCheck>GmaxSelect且 GmaxCheck>=GmaxText，则属性对应的表单控件是GnumberCheck个checkbox，元素名称为check1、check2、…；

(3)若GmaxText>GmaxSelect且GmaxText>GmaxCheck，则属性对应的表单元素是 GnumberText个 text，元素名称为 text1、text2、…。

4.3 值域生成

设置select控件、checkbox控件的值域。

select控件：若GnumberSelect=1，对于可选值较少且比较固定的值域，如折扣，在人工抽取阶段统一处理，如30折以下录入时改为3折以下。对可选值较多且不同接口的相应元素间差别较大的值域，如图书类型，选择对应元素的值域的并集作为统一接口中对应元素的值域；若GnumberSelect>1，选择一个元素类型为select、元素数目为GnumberSelect的对应属性的元素值域，直接一一对应赋值给各个select元素。Post值与显示值相同。

checkbox控件：若GnumberCheck=1，选择对应元素的值域的并集作为统一接口中对应元素的值域；若GnumberCheck>1，选择一个元素类型为checkbox、元素数目为GnumberCheck的对应属性的元素值域，直接一一对应赋值给各个checkbox元素。

4.4 集成接口

选择出属性、生成属性对应的表单元素及其值域之后，就可以生成全局的查询接口[11]。将选择出来的属性和生成的表单元素布局到同一个页面，为了界面的友好性和易用性，采用如下规则：

(1)每个属性的属性名及其对应的元素布局到同一行；不同的属性布局在不同行。

(2)根据元素类型动态生成对应类型的元素，对于text类型的元素，直接布局与对应属性的后面；对于和checkbox类型的元素和select类型的元素，通过查询值域表得到选项值。

(3)最后加入搜索按钮，形成全局查询接口。

5 Deep Web图书搜索系统实际应用情况

DeepWeb图书搜索系统试图建立一个全局的图书搜索界面，用户只需要在这个界面中输入一次查询信息，即可在互联网上众多的网上书店站点中查询相应的图书信息，减轻用户的搜索负担和输入负担。

该系统主要功能模块包括抽取多个网上书店的查询接口信息，在抽取的模式信息上进行模式匹配，利用源模式属性信息和模式匹配的结果3部分。抽取出的模式信息存入关系数据库中，显示、配置效果如图6所示。

图6 Deep Web图书搜索系统接口配置界面

抽取的模式信息中，共有32个属性实体，属性实体及其出现频数，例如出现概率在20%以上的属性有：出版社(频数14)，ISBN(频数 12)，作者(频数 11)，书名(频数 10)，售价(频数 9)等。在这些接口信息上进行模式匹配，发现接口间属性信息的同义匹配关系有{出版日期}={出版时间}(排列分值为0.765625)、{分类}={类别}(排列分值为 0.70000)、{名称}={书名}(排列分值为0.757575)、{著译者}={作者 (排列分值为0.733333)}。结果表明模式匹配的结果是具有很高的准确率和有效性。最后综合源模式的属性信息和模式匹配结果自动生成统一的全局网上图书查询界面如图7所示，该界面包括了网上书店查询接口的绝大部分意义相当的查询条件，取得了良好的准确性、友好性、易用性。

图7 Deep Web图书搜索查询接口

6 结束语

本文对Deep Web查询接口模式抽取、Deep Web查询接口模式匹配及查询接口的集成进行了研究，并在这些研究基础上建立了一个面向Deep Web对象的查询接口集成系统，达到了对Deep Web关键技术的探讨和实践的目的。但仍然处于探索性的工作，要实现一个真正可用的自动集成系统仍然有许多的问题，例如：接口模式的自动获取等有待更深入的研究。

[1]Kabra G,Zhang Z.Dewex an exploration facility for enabling the deep web integaration[C].Proceedings of 23rd International Conference on Data Engineering,2007:1511-1512.

[2]Liu W,Meng X F,Meng W Y.A survey of deep web data integration[J].Chinese Journal of Computers,2007,30(9):1475-1489.

[3]刘伟,孟小峰,孟卫一.Deep Web数据集成研究综述[J].计算机学报,2007,30(9):1475-1489.

[4]Avigdor Gal.Interpreting similarity measures:bridging the gap between schema matching and data integration[C].International Conference on Data Engineering,2008:278-285.

[5]Chuang S L,Chang K C.Integrating web query results:holistic schema matching[C].Proceeding of the 17th ACM Conference on Information and Knowledge Management.New York,USA:ACM Press,2008:33-42.

[6]Zhontian He,Jun Hong,David Bill.Schema matching across query interfaces on the deep web[C].Proceedings of the 25th British National Conference on Databases,2008:51-62.

[7]Chang K C C,He Bin,Li Cengkai,et al.The UIUC web integration repository[EB/OL].http://metaquerier.cs.uiuc.edu/repository/datasets/tel-8/browsable.html.2007-10-21.

[8]Zhang Z,He B,Chang K C C.Understanding web query interfaces:Best-effort parsing with hidden syntax[C].Proc of the ACM SIGMOD Conference.New York,USA:ACM Press,2004:107-118.

[9]Qian L H,Zhou GD,Zhu QM,et al.Exploiting constituentdependencies for tree kernel-based semantic relation extraction[C].Proceedings of the 22nd International Conference on Computational Linguistics,2008:696-704.

[10]刘玉,陈金雄.数据仓库中的数据清洗[J].医学信息,2008(11):55-71.

[11]王咏梅,嵇晓,汪恒杰,等.面向多数据源的数据清洗关键技术的研究[J].科技资讯,2009(1):35-43.

[12]He B,Chang K C.Making holistic schema matching robust:An ensemble approach[C].Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining.Chicago,USA:ACM Press,2005:429-438.

[13]Evermann J.Theries of meaning in schema matching:an exploratory study[J].Information Systems,2009,34(1):28-44.

[14]Liu Wei,Li Xian,Ling Yanyan,et al.A deep web data integration system for job search[J].Wuhan University Journal of Natural Sciences,2006,11(5):34-40.

[15]Jiang Fangjiao,Jia Linlin,Meng Xiaofeng.Query translation on the fly in deep web integration[J].Wuhan University Journal of Natural Sciences,2007,12(5):29-34.