基于XML Schema的Deep Web查詢接口分類研究*

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

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

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

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

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

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

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

2基于 XML Schema的Deep Web查詢接口分類

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

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

設(shè)用戶的查詢接口為t1，對于查詢接口樣本集T，對t1的分類過程設(shè)計(jì)如下兩個(gè)方面：

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

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

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

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

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

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

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

(1)

其中，

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

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

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

其中

(2)

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

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

3.1分類過程

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

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

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

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

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

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

(4)

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

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

3.2案列分析

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

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

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

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

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

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

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

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

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

然后再構(gòu)建特征向量空間模型VSM，對查詢接口進(jìn)行向量化為di(i=1,2,…,20)。對于待分類接口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ù)類別權(quán)重的計(jì)算公式(4)計(jì)算類別權(quán)重，查詢接口t歸為c3。

5結(jié)束語

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

參考文獻(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)挖掘和語義聚類的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著,李銳,李鵬,曲亞東,等，譯.機(jī)器學(xué)習(xí)實(shí)戰(zhàn)[M].北京：人民郵電出版社,2013.

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

[11]周由,戴牡紅.語義分析與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

中圖分類號：TP391

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

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

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

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

收稿日期：2015-10-28