基于XML Schema的Deep Web查询接口分类研究*

2016-05-30 11:12苟和平景永霞吴多智
长春大学学报 2016年4期
关键词:分类

苟和平,景永霞,吴多智

(琼台师范高等专科学校 信息技术系,海口 571100)



基于XML Schema的Deep Web查询接口分类研究*

苟和平,景永霞,吴多智

(琼台师范高等专科学校 信息技术系,海口 571100)

摘要:Deep Web在线数据库蕴含大量的信息,但由于这些信息检索困难,利用率不高,本文提出一种基于XML Schema 的查询接口分类方法,建立数据查询接口的XML Schema文档,通过各数据源名的语言学相似度实现查询接口的初次分类;根据查询接口标签属性,建立特征-接口向量空间模型实现查询接口向量化,再采用KNN算法进行二次分类,减少KNN算法分类带来的计算开销,提高Deep Web数据检索的效率。

关键词:Deep Web;XML Schema;查询接口;分类

0引言

网络技术的成熟使得Web迅速发展为一个巨大数据源,根据数据源的深度,整个Web可以划分为Surface Web (浅层网络)和Deep Web (深层网络)两大部分。Surface Web是指通过超链接能够被搜索引擎所检索到的静态Web页面的集合,而Deep Web是指不能被传统的搜索引擎所检索到的信息,这些信息内容存放在真正的在线Web数据库中,只能通过查询接口访问获得。由于Deep Web蕴含的信息量是Surface Web的400~500倍,且在Deep Web上95%的信息是可以公开访问的[1,2]。因此,为用户提供Deep Web特定领域的访问接口,实现其中丰富信息资源自动获取的研究有着重要的现实意义。

由于Deep Web信息来源于不同的领域,将用户针对Deep Web上的查询自动映射到不同领域的查询接口,实现数据的快速查询,首先需要实现将用户特定Deep Web查询接口按照领域进行分类,缩减数据检索范围,目前有许多关于查询接口分类的研究,但他们都绝大多数集中在基于统计、关联规则和聚类的方法[4-6],这类方法对查询接口的结构和语义考虑较少。也有研究采用本体的方案[7],但随着查询接口的增减,此类方案在维护一个庞大的本体上付出代价太高。K最近邻(KNN)[8]自动文本分类算法,是一种简单、有效的学习方法,在文本分类中得到了广泛的应用,取得了较好的效果。因此本文提出一种基于XML Schema的查询接口分类方案,主要利用XML Schema的结构特点,采用数据源名语言学相似度和KNN算法实现查询接口分类。

1Deep Web查询接口XML表示

图1 allbookstores网站的图书查询接口

Deep Web查询接口是实现Deep Web在线数据库访问的入口,例如我们访问图书网站allbookstores,通过Search菜单进行查询图书,其查询接口如图1所示。

将查询接口表示成XML结构:

(1)采用作为根节点,包含两类子节点

是对查询接口对应的数据源名称。是针对此数据源的查询表单。

(2)关于表单中的标签、文本框和列表框的描述方法有所不同,例如:对于Author项的XML描述:

(3)对于Format等具有固定选择值的属性描述:

对于上述关于allbookstores的查询接口,其XML Schema表示如下:

(1)对于一个Deep Web数据源采用作为根节点,根节点中包含接口来源的属性节点,名称和查询表单节点。其结构如图2所示。

图2 数据源节点的XML Schema结构

(2)查询接口表单节点是由若干个属性组组成,其中每个属性组又包含多个属性元素。其结构如图3所示。

因此,按照上述的XML Schema结构对不同的访问借口进行转换操作,建立XML Schema树。

2基于 XML Schema的Deep Web查询接口分类

2.1关键实现方案

为了实现对Deep Web数据库的快速查询,需要事先将用户的查询接口进行分类,将其映射到某个领域,缩小查询扫描范围,以实现快速的查询定位和数据检索,提高查询效率。

设用户的查询接口为t1,对于查询接口样本集T,对t1的分类过程设计如下两个方面:

(1)分别获得t1和样本t2(t2∈T)的XML Schema树中的 属性,对其采用属性标签的语言学相似性来度量。如待分类接口t1和t2(t2∈T)中 属性值完全相似或者基本相似(即其相似度大于预先设定的相似度阈值),则待分类接口t1属于接口t2所在的领域。

(2)如果待分类接口t1和所有的t2(t2∈T)不相似(即其相似度小于预先设定的相似度阈值),则对查询接口样本集T中的所有样本,获得其XML Schema中的节点的节点,将其节点属性值作为待分类特征属性,对来自所有领域的接口进行向量化,采用KNN算法进行分类。

图3 查询表单节点的XML Schema结构

2.2节点语言学相似度计算

对于查询接口XML schema,其属性元素是代表其数据来源,表示结构如下:

因此直接判断此节点值,有助于提高查询匹配的效率,本文采用对此节点属性值的语言学相似度lingSim()来判断相似性。对于查询接口t1和样本t2(t2∈T),其获取的属性值为v(t1)和v(t2)

对v(t1)和v(t2)名称字符串进行预处理,主要是实现字符串的拆分、去除一些虚词和特殊连字符等,分解成独立的单词集(tokens)S1T1和S2T2,然后进行语相似性分析,主要是采用基于wordnet来计算语义相似度。语言学相似度计算如公式(1)所示。

(1)

其中,

2.3查询接口属性选择及权值计算

为了实现查询接口快速分类,需要在分类前获取所有的查询接口对应的接口属性元素的name值,选择策略是只要在查询接口集中有接口增减情况,都需要重新获取其属性。形成属性name值的集合。

其中,ci(i=1,2,…m)为文本分类系统中的类别,p(ci)是指每个类别的出现概率。

其中

(2)

其次是属性权值计算,目前比较常用的特征属性权重计算函数有布尔函数、TF-IDF、 WIFD函数、以及TF-IWF 等,在文本文档分类中使用最普遍的是TF-IDF 权值计算公式,TF-IDF基本思想是:如果一个词在特定文档中出现的次数越多,说明它在该文档中的重要性越大,说明它区分文档内容属性的能力越强,如果一个词在所有的文档中都出现,说明它区分文档内容属性的能力越低[12]。如果查询接口增多,其对应的属性文本集也增大,需要对特征属性的分类能力进行判断,采用TF-IDF算法赋予接口属性不同的权值,是为了跟据属性特征贡献大小实现查询接口文本的向量化。

3基于 XML Schema的Deep Web查询接口分类实现

3.1分类过程

本文提出的查询接口分类是通过对查询接口文本的XML表示,建立XML Schema,按照此XMLschema的结构,实现对不同查询接口信息提取。主要是通过数据源名称的语言学相似性能够直接判断哪些属于同一个数据源的查询接口。然后再对于不能够直接判断的查询接口采用KNN分类算法进行分类,以确定其所属类别。

设用户查询接口t和的查询接口样本集T(c1,c2,…,cm),其包含m个类别。对t进行分类,将其归类到某个类别ci(i=1,2,…m)的过程如下:

1)对t和所有查询接口ti(ti∈T),建立其对应的XML格式文档(从网页页面中获得)和XML schema树。

2)对所有查询接口ti,获得所有查询接口XML schema树中的元素,建立所对应的数据源名称集V(T)和查询接口属性名称集A(T)。

3)对于V(T),采用基于wordnet的语义分析,利用公式(1)计算t中的数据源名v(t)与V(T)中所有数据源名v(ti)∈V(T)的语言学相似度ingSim(v(t),v(ti))。

4)对于指定语言学相似度阈值σ,若存在一个或者多个lingSim(v(t),v(ti))>σ,则按照所属接口所在的类别进行分类。如果对于所有的样本V(T),其lingSim(v(t),v(ti))<σ,则需要对属性名称集A(T)根据IG方法计算公式(2)进行分类特征选择,通过TF-IDF权值方法计算特征属性权值,建立特征-接口矩阵和向量空间模型(VSM),将所有查询接口ti向量化为特征空间向量di(x1,x2,…,xn)。

5)将t表示为和ti一致的特征向量d0(x1,x2,…,xn)。

6) 根据距离函数计算d0和di的相似度,可以使用两向量之间欧氏距离计算,选择与d0相似度最大(距离最小)的k个文本作为d0的k个最近邻。利用欧氏距离计算公式为:

(3)

其中xil和x0l分别指di和d0的第l个属性。

(7) 根据d0的k个最近邻,计算文本类别相应的权重, 计算公式为:

(4)

其中S(di,d0)表示文本向量di与文本向量d0之间的相似度; 类别属性函数为:

(8) 比较各类的权重,将待分类文本t0归入权重最大的类别。

3.2案列分析

我们选择了UCUI提供的TEL-8数据集,从其中的4个类c1:Arefares、类c2:Automobiles、类c3:Books和类c4:Jobs分别选取5个查询接口作为样本集,再选择测试查询接口。由于在这些领域中的许多查询接口是来来自同一个数据源,因此我们分两种情况进行测试:一是选择来自相同数据源的查询接口;二是选择非相同数据源的查询接口。

在对新的查询接口分类前需要获得样本集中的所有接口节点属性值,获得其数据源名称集V(T)和查询接口属性名称集A(T)。则对于我们选择的20个查询接口:

表1 v(t)和V(T)中各数据源语言学相似度

(1)在选择了Arefares领域中来自同一数据源Orbitz Flight中的两个查询接口t和t1,如图4(a)、4 (b)所示,t1在样本接口集中,t作为测试数据进行测试。

其接口v(t)和V(T)中各数据源语言学相似度如表1所示。

我们选取相似度阈值σ=0.9,则判断查询接口t∈c1(t5所属的领域)。

(a) Orbitz Flight中的查询接口t

(b)Orbitz Flight中的查询接口t1

(2)随机选择一个Books领域的查询接口t,计算其和所有V(T)中的数据源名称都不相似,因此采用KNN分类算法进行分,取k=3。我们通过IG方法选择了10个分类特征属性:

然后再构建特征向量空间模型VSM,对查询接口进行向量化为di(i=1,2,…,20)。对于待分类接口t,也采用个同样的方法进行向量化为d0。

d0={0,0,0,0,0,0.5,0,0.5,0.377964473,0}

则d0与di的相似度如表2所示。

表2 dj与di的相似度

根据表2的相似度可获得d0的3个近邻为{d13,d14,d15};再根据类别权重的计算公式(4)计算类别权重,查询接口t归为c3。

5结束语

Deep Web数据查询接口是实现Deep Web数据检索的有效手段,担由于Deep Web在线数据数量巨大,查询接口也是纷繁多样,为了实现数据的快速检索,需要对多样的查询接口进行分类,使其能够实现某个领域数据的快速定位和检索,本文提出实现方案能够结合数据源属性的语义判断,通过KNN算法有效地解决这一问题,提高 Deep Web在线数据库的检索效率。

参考文献:

[1]BERGMAN M K. The Deep Web: surfacing hidden value[EB/OL].[2014-6-18].http://www.brightplanet.com/2012/06/the-deep-web-surfacing-hidden-value/.

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

[3]Liu Tantan,Wang Fan,Agrawal G.Instance discovery and schema matching with applications to biological Deep Web data integration[C].Washington,IEEE International Conference on Bioinformatics & Bioengineering,2010.

[4]曹庆皇, 鞠时光, 杨晓琴. 基于关联挖掘和语义聚类的Deep Web复杂匹配方法[J].计算机应用研究,2009,26(12):4613-4616.

[5]Research on Deep Web Query InterfaceClustering Based on Hadoop[J].Journal of Software,2014, 9(12):3057-3062.

[6]WangYing; LiHuilai; ZuoWanli;et al.Ontology-Based Approach to Integrate Deep Web Query Interfaces[J]. Advanced Science Letters,2012(4):220-223.

[7]Zhang H,Berg AC, Maire M. Discriminative nearest neighbor classification for visual category recognition[C].Los Alamitos,CA,IEEE Computer Society Conference on Computer Vision and Pattern Recognition(CVPR′06),2006.

[8]George M, Christiane F. WordNet: An Electronic Lexical Database[M].Massachusetts:MIT Press,1998.

[9]Peter Harrington著,李锐,李鹏,曲亚东,等,译.机器学习实战[M].北京:人民邮电出版社,2013.

[10]范明,孟小峰,等,数据挖掘概念与技术[M].北京:机械工业出版社,2001.

[11]周由,戴牡红.语义分析与TF-IDF方法相结合的新闻推荐技术[J].计算机科学,2013,40(11A):267-300.

责任编辑:程艳艳

Research on Query Interface Classification of Deep Web Based on XML Schema

GOU Heping, JING Yongxia, WU Duozhi

(Department of Information Technology, Qiongtai Normal University, Haikou 571100, China)

Abstract:Deep Web online database contains a lot of information, but their utilization is not high because of the difficult information retrieval. A query interface classification method based on XML Schema is proposed. XML Schema document of the data query interface is established, which realizes the first classification through the linguistic similarity of data source name; According to the label attribute of query interface, a vector space model is established to realize the vectorization of query interface, then KNN algorithm is used for secondary classification, which reduces the computing cost brought by KNN classification algorithm, improving the efficiency of Deep Web data retrieval.

Keywords:Deep Web; XML Schema; query interface; classification

中图分类号:TP391

文献标志码:A

文章编号:1009-3907(2016)04-0013-06

作者简介:苟和平(1978-),男,甘肃庆阳人,副教授,硕士,主要从事分布式计算、数据挖掘方面研究。

基金项目:海南省自然科学基金项目(20156241);海南省高等学校科学研究项目(Hnky2015-72);琼台师范高等专科学校科研项目(qtky201404)

收稿日期:2015-10-28

猜你喜欢
分类
分类算一算
垃圾分类的困惑你有吗
分类讨论求坐标
数据分析中的分类讨论
教你一招:数的分类
给塑料分分类吧