(2)關(guān)于表單中的標(biāo)簽、文本框和列表框的描述方法有所不同，例如：對(duì)于Author項(xiàng)的XML描述：

(3)對(duì)于Format等具有固定選擇值的屬性描述：

對(duì)于上述關(guān)于allbookstores的查詢(xún)接口，其XML Schema表示如下：

(1)對(duì)于一個(gè)Deep Web數(shù)據(jù)源采用作為根節(jié)點(diǎn)，根節(jié)點(diǎn)中包含接口來(lái)源的屬性節(jié)點(diǎn)，名稱(chēng)和查詢(xún)表單節(jié)點(diǎn)。其結(jié)構(gòu)如圖2所示。

圖2　數(shù)據(jù)源節(jié)點(diǎn)的XML Schema結(jié)構(gòu)

(2)查詢(xún)接口表單節(jié)點(diǎn)是由若干個(gè)屬性組組成，其中每個(gè)屬性組又包含多個(gè)屬性元素。其結(jié)構(gòu)如圖3所示。

因此，按照上述的XML Schema結(jié)構(gòu)對(duì)不同的訪(fǎng)問(wèn)借口進(jìn)行轉(zhuǎn)換操作，建立XML Schema樹(shù)。

2基于 XML Schema的Deep Web查詢(xún)接口分類(lèi)

2.1關(guān)鍵實(shí)現(xiàn)方案

為了實(shí)現(xiàn)對(duì)Deep Web數(shù)據(jù)庫(kù)的快速查詢(xún)，需要事先將用戶(hù)的查詢(xún)接口進(jìn)行分類(lèi)，將其映射到某個(gè)領(lǐng)域，縮小查詢(xún)掃描范圍，以實(shí)現(xiàn)快速的查詢(xún)定位和數(shù)據(jù)檢索，提高查詢(xún)效率。

設(shè)用戶(hù)的查詢(xún)接口為t1，對(duì)于查詢(xún)接口樣本集T，對(duì)t1的分類(lèi)過(guò)程設(shè)計(jì)如下兩個(gè)方面：

(1)分別獲得t1和樣本t2(t2∈T)的XML Schema樹(shù)中的 屬性，對(duì)其采用屬性標(biāo)簽的語(yǔ)言學(xué)相似性來(lái)度量。如待分類(lèi)接口t1和t2(t2∈T)中 屬性值完全相似或者基本相似(即其相似度大于預(yù)先設(shè)定的相似度閾值)，則待分類(lèi)接口t1屬于接口t2所在的領(lǐng)域。

(2)如果待分類(lèi)接口t1和所有的t2(t2∈T)不相似(即其相似度小于預(yù)先設(shè)定的相似度閾值)，則對(duì)查詢(xún)接口樣本集T中的所有樣本，獲得其XML Schema中的節(jié)點(diǎn)的節(jié)點(diǎn)，將其節(jié)點(diǎn)屬性值作為待分類(lèi)特征屬性，對(duì)來(lái)自所有領(lǐng)域的接口進(jìn)行向量化，采用KNN算法進(jìn)行分類(lèi)。

圖3　查詢(xún)表單節(jié)點(diǎn)的XML Schema結(jié)構(gòu)

2.2節(jié)點(diǎn)語(yǔ)言學(xué)相似度計(jì)算

對(duì)于查詢(xún)接口XML schema，其屬性元素是代表其數(shù)據(jù)來(lái)源，表示結(jié)構(gòu)如下：

因此直接判斷此節(jié)點(diǎn)值，有助于提高查詢(xún)匹配的效率，本文采用對(duì)此節(jié)點(diǎn)屬性值的語(yǔ)言學(xué)相似度lingSim()來(lái)判斷相似性。對(duì)于查詢(xún)接口t1和樣本t2(t2∈T)，其獲取的屬性值為v(t1)和v(t2)

對(duì)v(t1)和v(t2)名稱(chēng)字符串進(jìn)行預(yù)處理，主要是實(shí)現(xiàn)字符串的拆分、去除一些虛詞和特殊連字符等，分解成獨(dú)立的單詞集(tokens)S1T1和S2T2，然后進(jìn)行語(yǔ)相似性分析，主要是采用基于wordnet來(lái)計(jì)算語(yǔ)義相似度。語(yǔ)言學(xué)相似度計(jì)算如公式(1)所示。

(1)

其中，

2.3查詢(xún)接口屬性選擇及權(quán)值計(jì)算

為了實(shí)現(xiàn)查詢(xún)接口快速分類(lèi)，需要在分類(lèi)前獲取所有的查詢(xún)接口對(duì)應(yīng)的接口屬性元素的name值，選擇策略是只要在查詢(xún)接口集中有接口增減情況，都需要重新獲取其屬性。形成屬性name值的集合。

其中，ci(i=1,2,…m)為文本分類(lèi)系統(tǒng)中的類(lèi)別，p(ci)是指每個(gè)類(lèi)別的出現(xiàn)概率。

其中

(2)

其次是屬性權(quán)值計(jì)算，目前比較常用的特征屬性權(quán)重計(jì)算函數(shù)有布爾函數(shù)、TF-IDF、 WIFD函數(shù)、以及TF-IWF 等，在文本文檔分類(lèi)中使用最普遍的是TF-IDF 權(quán)值計(jì)算公式，TF-IDF基本思想是：如果一個(gè)詞在特定文檔中出現(xiàn)的次數(shù)越多，說(shuō)明它在該文檔中的重要性越大，說(shuō)明它區(qū)分文檔內(nèi)容屬性的能力越強(qiáng)，如果一個(gè)詞在所有的文檔中都出現(xiàn)，說(shuō)明它區(qū)分文檔內(nèi)容屬性的能力越低[12]。如果查詢(xún)接口增多，其對(duì)應(yīng)的屬性文本集也增大，需要對(duì)特征屬性的分類(lèi)能力進(jìn)行判斷，采用TF-IDF算法賦予接口屬性不同的權(quán)值，是為了跟據(jù)屬性特征貢獻(xiàn)大小實(shí)現(xiàn)查詢(xún)接口文本的向量化。

3基于 XML Schema的Deep Web查詢(xún)接口分類(lèi)實(shí)現(xiàn)

3.1分類(lèi)過(guò)程

本文提出的查詢(xún)接口分類(lèi)是通過(guò)對(duì)查詢(xún)接口文本的XML表示，建立XML Schema，按照此XMLschema的結(jié)構(gòu)，實(shí)現(xiàn)對(duì)不同查詢(xún)接口信息提取。主要是通過(guò)數(shù)據(jù)源名稱(chēng)的語(yǔ)言學(xué)相似性能夠直接判斷哪些屬于同一個(gè)數(shù)據(jù)源的查詢(xún)接口。然后再對(duì)于不能夠直接判斷的查詢(xún)接口采用KNN分類(lèi)算法進(jìn)行分類(lèi)，以確定其所屬類(lèi)別。

設(shè)用戶(hù)查詢(xún)接口t和的查詢(xún)接口樣本集T(c1,c2,…,cm)，其包含m個(gè)類(lèi)別。對(duì)t進(jìn)行分類(lèi)，將其歸類(lèi)到某個(gè)類(lèi)別ci(i=1,2,…m)的過(guò)程如下：

1)對(duì)t和所有查詢(xún)接口ti(ti∈T)，建立其對(duì)應(yīng)的XML格式文檔(從網(wǎng)頁(yè)頁(yè)面中獲得)和XML schema樹(shù)。

2)對(duì)所有查詢(xún)接口ti，獲得所有查詢(xún)接口XML schema樹(shù)中的和元素，建立所對(duì)應(yīng)的數(shù)據(jù)源名稱(chēng)集V(T)和查詢(xún)接口屬性名稱(chēng)集A(T)。

3)對(duì)于V(T)，采用基于wordnet的語(yǔ)義分析，利用公式(1)計(jì)算t中的數(shù)據(jù)源名v(t)與V(T)中所有數(shù)據(jù)源名v(ti)∈V(T)的語(yǔ)言學(xué)相似度ingSim(v(t),v(ti))。

4)對(duì)于指定語(yǔ)言學(xué)相似度閾值σ，若存在一個(gè)或者多個(gè)lingSim(v(t),v(ti))>σ,則按照所屬接口所在的類(lèi)別進(jìn)行分類(lèi)。如果對(duì)于所有的樣本V(T)，其lingSim(v(t),v(ti))<σ，則需要對(duì)屬性名稱(chēng)集A(T)根據(jù)IG方法計(jì)算公式(2)進(jìn)行分類(lèi)特征選擇，通過(guò)TF-IDF權(quán)值方法計(jì)算特征屬性權(quán)值，建立特征-接口矩陣和向量空間模型(VSM)，將所有查詢(xún)接口ti向量化為特征空間向量di(x1,x2,…,xn)。

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

6) 根據(jù)距離函數(shù)計(jì)算d0和di的相似度,可以使用兩向量之間歐氏距離計(jì)算，選擇與d0相似度最大(距離最小)的k個(gè)文本作為d0的k個(gè)最近鄰。利用歐氏距離計(jì)算公式為：

(3)

其中xil和x0l分別指di和d0的第l個(gè)屬性。

(7) 根據(jù)d0的k個(gè)最近鄰，計(jì)算文本類(lèi)別相應(yīng)的權(quán)重, 計(jì)算公式為：

(4)

其中S(di,d0)表示文本向量di與文本向量d0之間的相似度; 類(lèi)別屬性函數(shù)為：

(8) 比較各類(lèi)的權(quán)重，將待分類(lèi)文本t0歸入權(quán)重最大的類(lèi)別。

3.2案列分析

我們選擇了UCUI提供的TEL-8數(shù)據(jù)集，從其中的4個(gè)類(lèi)c1:Arefares、類(lèi)c2:Automobiles、類(lèi)c3:Books和類(lèi)c4:Jobs分別選取5個(gè)查詢(xún)接口作為樣本集，再選擇測(cè)試查詢(xún)接口。由于在這些領(lǐng)域中的許多查詢(xún)接口是來(lái)來(lái)自同一個(gè)數(shù)據(jù)源，因此我們分兩種情況進(jìn)行測(cè)試：一是選擇來(lái)自相同數(shù)據(jù)源的查詢(xún)接口；二是選擇非相同數(shù)據(jù)源的查詢(xún)接口。

在對(duì)新的查詢(xún)接口分類(lèi)前需要獲得樣本集中的所有接口和 節(jié)點(diǎn)屬性值，獲得其數(shù)據(jù)源名稱(chēng)集V(T)和查詢(xún)接口屬性名稱(chēng)集A(T)。則對(duì)于我們選擇的20個(gè)查詢(xún)接口：

表1　v(t)和V(T)中各數(shù)據(jù)源語(yǔ)言學(xué)相似度

(1)在選擇了Arefares領(lǐng)域中來(lái)自同一數(shù)據(jù)源Orbitz Flight中的兩個(gè)查詢(xún)接口t和t1，如圖4(a)、4 (b)所示，t1在樣本接口集中，t作為測(cè)試數(shù)據(jù)進(jìn)行測(cè)試。

其接口v(t)和V(T)中各數(shù)據(jù)源語(yǔ)言學(xué)相似度如表1所示。

我們選取相似度閾值σ=0.9，則判斷查詢(xún)接口t∈c1(t5所屬的領(lǐng)域)。

(a) Orbitz Flight中的查詢(xún)接口t

(b)Orbitz Flight中的查詢(xún)接口t1

(2)隨機(jī)選擇一個(gè)Books領(lǐng)域的查詢(xún)接口t，計(jì)算其和所有V(T)中的數(shù)據(jù)源名稱(chēng)都不相似，因此采用KNN分類(lèi)算法進(jìn)行分，取k=3。我們通過(guò)IG方法選擇了10個(gè)分類(lèi)特征屬性：

然后再構(gòu)建特征向量空間模型VSM，對(duì)查詢(xún)接口進(jìn)行向量化為di(i=1,2,…,20)。對(duì)于待分類(lèi)接口t，也采用個(gè)同樣的方法進(jìn)行向量化為d0。

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

則d0與di的相似度如表2所示。

表2　dj與di的相似度

根據(jù)表2的相似度可獲得d0的3個(gè)近鄰為{d13,d14,d15}；再根據(jù)類(lèi)別權(quán)重的計(jì)算公式(4)計(jì)算類(lèi)別權(quán)重，查詢(xún)接口t歸為c3。

5結(jié)束語(yǔ)

Deep Web數(shù)據(jù)查詢(xún)接口是實(shí)現(xiàn)Deep Web數(shù)據(jù)檢索的有效手段，擔(dān)由于Deep Web在線(xiàn)數(shù)據(jù)數(shù)量巨大，查詢(xún)接口也是紛繁多樣，為了實(shí)現(xiàn)數(shù)據(jù)的快速檢索，需要對(duì)多樣的查詢(xún)接口進(jìn)行分類(lèi)，使其能夠?qū)崿F(xiàn)某個(gè)領(lǐng)域數(shù)據(jù)的快速定位和檢索，本文提出實(shí)現(xiàn)方案能夠結(jié)合數(shù)據(jù)源屬性的語(yǔ)義判斷，通過(guò)KNN算法有效地解決這一問(wèn)題，提高 Deep Web在線(xiàn)數(shù)據(jù)庫(kù)的檢索效率。

參考文獻(xiàn)：

[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]劉偉, 孟小峰, 孟衛(wèi)一. Deep Web 數(shù)據(jù)集成研究綜述[J].計(jì)算機(jī)學(xué)報(bào), 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]曹慶皇, 鞠時(shí)光, 楊曉琴. 基于關(guān)聯(lián)挖掘和語(yǔ)義聚類(lèi)的Deep Web復(fù)雜匹配方法[J].計(jì)算機(jī)應(yīng)用研究，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著,李銳,李鵬,曲亞?wèn)|,等，譯.機(jī)器學(xué)習(xí)實(shí)戰(zhàn)[M].北京：人民郵電出版社,2013.

[10]范明,孟小峰，等，數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社，2001.

[11]周由,戴牡紅.語(yǔ)義分析與TF-IDF方法相結(jié)合的新聞推薦技術(shù)[J].計(jì)算機(jī)科學(xué),2013,40(11A):267-300.

責(zé)任編輯：程艷艷

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

中圖分類(lèi)號(hào)：TP391

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1009-3907(2016)04-0013-06

作者簡(jiǎn)介：茍和平(1978-)，男，甘肅慶陽(yáng)人，副教授，碩士，主要從事分布式計(jì)算、數(shù)據(jù)挖掘方面研究。

基金項(xiàng)目：海南省自然科學(xué)基金項(xiàng)目(20156241)；海南省高等學(xué)校科學(xué)研究項(xiàng)目(Hnky2015-72);瓊臺(tái)師范高等專(zhuān)科學(xué)?？蒲许?xiàng)目(qtky201404)

收稿日期：2015-10-28