大數(shù)據(jù)時(shí)代電子政務(wù)中XML文檔相似性

趙 震，任永昌

(1.渤海大學(xué) 信息科學(xué)與技術(shù)學(xué)院,遼寧 錦州 121013;2.東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,遼寧 沈陽 110819)

大數(shù)據(jù)時(shí)代電子政務(wù)中XML文檔相似性

趙 震1,2，任永昌1

(1.渤海大學(xué) 信息科學(xué)與技術(shù)學(xué)院,遼寧 錦州 121013;2.東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,遼寧 沈陽 110819)

XML作為電子政務(wù)應(yīng)用中的數(shù)據(jù)交換標(biāo)準(zhǔn)已經(jīng)被廣泛研究。隨著大數(shù)據(jù)時(shí)代的到來，對(duì)電子政務(wù)中XML數(shù)據(jù)的管理也顯得越來越重要。在XML數(shù)據(jù)的管理中，XML文檔的相似性是XML數(shù)據(jù)集成、XML數(shù)據(jù)分類的關(guān)鍵。為了研究XML文檔的相似性，針對(duì)XML文檔進(jìn)行了樹形變換，并提取樹節(jié)點(diǎn)的相應(yīng)特征，然后分別利用這些特征對(duì)節(jié)點(diǎn)進(jìn)行相應(yīng)的相似性計(jì)算，再將得到的相似性利用ELM(超限學(xué)習(xí)機(jī))算法進(jìn)行擬合得到最終的節(jié)點(diǎn)相似性。在節(jié)點(diǎn)相似性的基礎(chǔ)上提出了XML文檔樹的相似性比較算法，從而計(jì)算得到XML文檔的相似性。實(shí)驗(yàn)部分在給出具體的評(píng)估指標(biāo)的基礎(chǔ)上，在兩個(gè)不同的數(shù)據(jù)集上給出使用文中方法所得到的精確度、召回率、F-measure值以及相應(yīng)時(shí)間的對(duì)比情況，通過實(shí)驗(yàn)驗(yàn)證了所提方法的性能優(yōu)勢(shì)。

XML文檔；相似性；特征提取；擬合；數(shù)據(jù)集成

0 引 言

近年來，隨著電子政務(wù)的快速發(fā)展，XML作為電子政務(wù)應(yīng)用中的數(shù)據(jù)交換標(biāo)準(zhǔn)[1]越來越受到重視。眾多學(xué)者在此基礎(chǔ)上提出了許多基于XML的電子政務(wù)服務(wù)模型[2-4]。隨著大數(shù)據(jù)時(shí)代的到來，對(duì)電子政務(wù)中XML數(shù)據(jù)的管理也顯得越來越重要。XML數(shù)據(jù)的管理包括數(shù)據(jù)的存儲(chǔ)和集成、數(shù)據(jù)的交換等。在XML數(shù)據(jù)的管理中，XML數(shù)據(jù)的相似性是XML數(shù)據(jù)集成[5]、分類[6]的關(guān)鍵。由于各個(gè)部門XML的數(shù)據(jù)源是獨(dú)立構(gòu)建的，不同部門應(yīng)用中的XML數(shù)據(jù)結(jié)構(gòu)是有差異的，首先要對(duì)這些數(shù)據(jù)進(jìn)行識(shí)別，找出它們之間的相似性后再進(jìn)行數(shù)據(jù)集成或分類。文中工作有利于解決政府各部門各類應(yīng)用間的信息孤島問題，對(duì)實(shí)現(xiàn)部門間協(xié)同工作十分重要。

XML數(shù)據(jù)管理問題是以往各國(guó)學(xué)者研究的熱點(diǎn)[7-10]。提出了一些經(jīng)典方法，對(duì)于解決XML數(shù)據(jù)管理問題十分重要。在XML文檔的相似性研究中，XML文檔可以表示為樹，兩者的相似性問題可以轉(zhuǎn)化為兩棵樹的匹配問題，目前的解決方案主要有：將需要進(jìn)行匹配的XML文檔轉(zhuǎn)化為樹，利用基于樹編輯距離的算法計(jì)算文檔樹的相似性[7-8]；借助鄰接矩陣來計(jì)算對(duì)應(yīng)XML文檔的相似性[9-10]。

文中在節(jié)點(diǎn)相似性的基礎(chǔ)上提出了XML文檔樹的相似性比較算法，從而計(jì)算得到XML文檔的相似性，并進(jìn)行了實(shí)驗(yàn)驗(yàn)證。

1 XML文檔及樹形表示

XML作為可擴(kuò)展標(biāo)記語言，以半結(jié)構(gòu)化的方式描述各種類型的數(shù)據(jù)。XML文檔中允許使用自定義的標(biāo)簽來更準(zhǔn)確地描述數(shù)據(jù)。下面給出一個(gè)XML文檔片段，如圖1所示。

GeorgeFrankprofessor26John@yahoo．com

圖1 XML文檔實(shí)例

XML文檔可以用樹形結(jié)構(gòu)表示。按照文檔對(duì)象模型(DOM)，一個(gè)XML文檔也可以表示為一個(gè)單根的有序標(biāo)簽樹，其中的節(jié)點(diǎn)對(duì)應(yīng)文檔中的元素和屬性。文中只比較樹的結(jié)構(gòu)相似性，所以省略元素和屬性的值。圖1中文檔片段對(duì)應(yīng)的樹結(jié)構(gòu)如圖2所示。

2 樹節(jié)點(diǎn)的特征相似性

對(duì)于XML文檔樹，樹節(jié)點(diǎn)是最基本的數(shù)據(jù)項(xiàng)。一個(gè)節(jié)點(diǎn)可以是XML文檔中的元素或?qū)傩?。用SimNode(N1,N2)表示來自不同文檔樹節(jié)點(diǎn)N1和N2的相似度。

可以充分利用節(jié)點(diǎn)的特征來更精確地獲得節(jié)點(diǎn)的相似性。標(biāo)簽名、節(jié)點(diǎn)深度、數(shù)據(jù)類型是最常見的用于計(jì)算節(jié)點(diǎn)相似性的特征。也就是說，利用節(jié)點(diǎn)的這些特征值計(jì)算得到來自不同文檔樹節(jié)點(diǎn)的相似性。根據(jù)不同的特征，可以得到不同的相似度。

圖2 XML文檔樹實(shí)例

(1)標(biāo)簽相似性度量。

標(biāo)簽名(Label)是最重要的節(jié)點(diǎn)特征。利用字符串匹配來計(jì)算標(biāo)簽相似度。當(dāng)然字符串匹配的方法有很多，這里采用文獻(xiàn)[11]中的方法來計(jì)算字符串的相似性。那么，節(jié)點(diǎn)的相似性可由式(1)得到：

(1)

其中，editDistance(L1,L2)是字符串L1轉(zhuǎn)換為L(zhǎng)2所需要編輯字符的最小代價(jià)。

(2)深度相似性度量。

只用節(jié)點(diǎn)標(biāo)簽來度量節(jié)點(diǎn)相似性是完全不夠的，節(jié)點(diǎn)的深度是另外一個(gè)重要的考量節(jié)點(diǎn)相似性的特征。深度相似性需要考慮節(jié)點(diǎn)和它們最近共同祖先節(jié)點(diǎn)的深度。那么兩個(gè)節(jié)點(diǎn)的相似性可由式(2)得到：

(2)

其中，d1和d2分別是節(jié)點(diǎn)N1和N2在相應(yīng)文檔樹中的深度；d01和d02分別是N1和N2最近共同祖先N0在相應(yīng)文檔樹中的深度。

(3)數(shù)據(jù)類型相似性度量。

節(jié)點(diǎn)的數(shù)據(jù)類型是另一個(gè)用來確定節(jié)點(diǎn)相似性的特征。具有相同數(shù)據(jù)類型的節(jié)點(diǎn)具有更大的相似性(SimDataType)。表1說明了不同數(shù)據(jù)類型節(jié)點(diǎn)相似性度量值。

表1 數(shù)據(jù)類型相似性列表

還有很多用于度量節(jié)點(diǎn)相似性的特征，用這些特征計(jì)算得到節(jié)點(diǎn)特征相似性S1,S2,…,SN。但是每一個(gè)單一的特征得來的相似性都不足以表示節(jié)點(diǎn)的相似性，因此，有必要將這些相似性擬合在一起，從整體上來考慮這些特征，以得到更合理的節(jié)點(diǎn)相似性。一般采用權(quán)重的方法得到最終的相似性[12-13]，但是這種方法得到的結(jié)果誤差較大。于是利用基于超限學(xué)習(xí)機(jī)的方法得到擬合的節(jié)點(diǎn)相似性。

3 超限學(xué)習(xí)機(jī)

超限學(xué)習(xí)機(jī)[14-15]是由黃廣斌教授提出的單隱層前饋神經(jīng)網(wǎng)絡(luò)。超限學(xué)習(xí)機(jī)的最大優(yōu)點(diǎn)是提供了非?？斓膶W(xué)習(xí)速度，其隱藏層的權(quán)重和偏移值可以隨機(jī)指定，并且輸出權(quán)重可以通過矩陣計(jì)算而無需人工調(diào)節(jié)。

考慮N個(gè)任意樣本(xi,ti)∈Rn×m，那么ELM可表示為：

(3)

其中，L為隱藏層節(jié)點(diǎn)數(shù)目；g()為激活函數(shù)；Wi為輸入權(quán)重向量；βi為輸出權(quán)重向量；bi為第i個(gè)隱藏節(jié)點(diǎn)的偏移量。

則存在Wi，βi，bi，使得

(4)

上面的等式可表示為：

Hβ=T

(5)

其中

問題簡(jiǎn)化為求解線性系統(tǒng)的最小二乘解。則輸出權(quán)重β為：

β=H?T

(6)

其中，H?= (HTH)-1HT是H的偽逆矩陣。

計(jì)算得到輸出權(quán)重β后，利用它得到：

ot=βh(xt)

(7)

ELM算法描述如下：

算法1：ELM。

輸入：訓(xùn)練集D={(xt,yt)},t=1,2,…,T,激活函數(shù)g(x);隱藏節(jié)點(diǎn)數(shù)L;(whereL≤T);

輸出：β。

Begin

步驟1：隨機(jī)指定輸入權(quán)重Wi和偏移量bi;

步驟2：計(jì)算H;

步驟3：計(jì)算β=H?T。

Returnβ

End

4 文檔樹的相似性計(jì)算

4.1 樹節(jié)點(diǎn)的相似性

為了得到文檔樹的相似性，首先要獲得文檔樹中節(jié)點(diǎn)的相似度。前文介紹了依據(jù)節(jié)點(diǎn)特征得到的特征相似性，這一節(jié)介紹如何利用超限學(xué)習(xí)機(jī)得到擬合的節(jié)點(diǎn)相似性。

用超限學(xué)習(xí)機(jī)擬合節(jié)點(diǎn)的相似性如圖3所示。其中，S1,S2,…,Sn是根據(jù)節(jié)點(diǎn)特征得到的相互獨(dú)立的相似度量值；S是經(jīng)過ELM擬合得到的最終節(jié)點(diǎn)相似度。

圖3 基于ELM的相似性擬合

擬合過程分為訓(xùn)練階段和預(yù)測(cè)階段。這一擬合模型目的是利用訓(xùn)練樣本在輸入變量(S1,S2,…,Sn)和輸出變量(S)間建立一種映射關(guān)系。首先隨機(jī)選擇不同文檔樹中的節(jié)點(diǎn)作為訓(xùn)練樣本，然后分別計(jì)算節(jié)點(diǎn)對(duì)的特征相似值S1,S2,…,Sn，再通過專家確定這些樣本節(jié)點(diǎn)的最終相似性S，最后，通過超限學(xué)習(xí)機(jī)算法快速建立預(yù)測(cè)模型。算法描述如下：

算法2：SimNode。

輸入:Node1,Node2；

輸出:SimNode。

Begin

步驟1：分別計(jì)算特征相似度S1,S2,…,Sn;

步驟2：計(jì)算節(jié)點(diǎn)相似度SimNode=βH，β由算法1得到。

ReturnSimNode

End

4.2 文檔樹的相似性

給定文檔樹D1和D2，計(jì)算文檔樹的相似性。需要得到節(jié)點(diǎn)相似性大于給定閾值(θ)的節(jié)點(diǎn)數(shù)目。用這一數(shù)值與全部節(jié)點(diǎn)數(shù)目的比值來衡量文檔中相似節(jié)點(diǎn)所占的比重，據(jù)此得出文檔的相似性。算法3給出了計(jì)算文檔樹的相似性的具體算法。

算法3：SimDocument。

輸入:D1,D2；

輸出:SimDocument。

Begin

步驟1：遍歷D1,D2中每個(gè)節(jié)點(diǎn)，nodei∈D1,nodej∈D2；

步驟2：計(jì)算每個(gè)節(jié)點(diǎn)對(duì)的相似度SimNode(nodei,nodej)；

步驟3：如果SimNode(nodei,nodej)兩棵樹中相似節(jié)點(diǎn)對(duì)相似度大于閾值θ，則相似節(jié)點(diǎn)數(shù)目NumSimNode=NumSimNode+1;

ReturnSimDocument

End

5 實(shí) 驗(yàn)

下面通過實(shí)驗(yàn)進(jìn)一步評(píng)估文中提出的XML文檔相似性計(jì)算方法的性能。評(píng)估相似性比較的性能主要考慮兩方面：有效性和效率。

評(píng)估有效性主要有兩個(gè)指標(biāo)：精確度和召回率。下面簡(jiǎn)單介紹它們的定義。

精確度表示正確匹配的程度，召回率表示匹配的完整性，分別為：

(8)

(9)

其中，A為正確匹配的XML文檔數(shù)量；B為錯(cuò)誤匹配的XML文檔數(shù)量；C為沒有被識(shí)別出的正確匹配的XML文檔數(shù)量。

兩者的調(diào)和平均值可以用F-measure來表示。

(10)

為保證數(shù)據(jù)的真實(shí)性，選用的數(shù)據(jù)集為DBLP和SigmodRecord。同時(shí)，需要將數(shù)據(jù)集分割為0.1M到2M的數(shù)據(jù)，以便對(duì)比算法響應(yīng)時(shí)間。

圖4顯示了在DBLP和SigmodRecord數(shù)據(jù)集上使用文中方法所得到的精確度、召回率、F-measure值的對(duì)比情況。

圖4 DBLP和SigmodRecord數(shù)據(jù)集匹配有效性對(duì)比

從圖中可以看出，SigmodRecord數(shù)據(jù)集上的有效性要優(yōu)于DBLP數(shù)據(jù)集，這是因?yàn)镈BLP數(shù)據(jù)集的結(jié)構(gòu)比SigmodRecord復(fù)雜。

圖5顯示了在DBLP和SigmodRecord數(shù)據(jù)集上執(zhí)行文中算法所得到的響應(yīng)時(shí)間的對(duì)比情況。

圖5 DBLP和SigmodRecord數(shù)據(jù)集響應(yīng)時(shí)間對(duì)比

從圖中可以看出，SigmodRecord數(shù)據(jù)集上的響應(yīng)時(shí)間遠(yuǎn)小于DBLP數(shù)據(jù)集，由此可以看出DBLP數(shù)據(jù)集結(jié)構(gòu)比較復(fù)雜。

6 結(jié)束語

在大數(shù)據(jù)的背景下，研究了電子政務(wù)中XML數(shù)據(jù)的相似性。首先將XML文檔轉(zhuǎn)換為對(duì)應(yīng)的XML文檔樹，然后根據(jù)抽取的XML樹節(jié)點(diǎn)的特征，計(jì)算對(duì)應(yīng)的特征相似性，再使用基于ELM的算法得到XML節(jié)點(diǎn)的相似性，并給出了XML文檔樹的相似性比較算法，從而得到XML文檔的相似性。通過實(shí)驗(yàn)驗(yàn)證了所提方法的正確性和有效性。

[1] 趙慧勤,趙慧玲.電子政務(wù)數(shù)據(jù)交換標(biāo)準(zhǔn)—XML語言[J].山西大同大學(xué)學(xué)報(bào):社會(huì)科學(xué)版,2003,17(3):76-78.

[2] 鐘福金,辜麗川,張友華.基于語義Web服務(wù)的電子政務(wù)模型研究[J].微電子學(xué)與計(jì)算機(jī),2010,27(3):144-147.

[3] 陳 樺,麻風(fēng)梅,韓艷艷.基于XML的異構(gòu)數(shù)據(jù)集成模式的研究[J].微電子學(xué)與計(jì)算機(jī),2009,26(1):137-139.

[4] 李冬睿.基于XML與Web Service的電子政務(wù)數(shù)據(jù)交換模型的設(shè)計(jì)與實(shí)現(xiàn)[D].桂林:廣西師范大學(xué),2008.

[5] Thomo A,Venkatesh S.Rewriting of visibly pushdown languages for xml data integration[C]//Proceedings of the 17th ACM conference on information and knowledge management.Napa Valley,California,USA:ACM,2008:521-530.

[6] Algergawy A,Mesiti M,Nayak R,et al.XML data clustering:an overview[J].ACM Computing Surveys,2011,43(4):25-41.

[7] Nierman A,Jagadish H V.Evaluating structural similarity in XML documents[C]//Proceedings of the ACM SIGMOD international workshop on the web and databases.[s.l.]:ACM,2002:61-66.

[8] Tekli J,Chbeir R.A novel XML document structure comparison framework based-on sub-tree commonalities and label semantics[J].Journal of Web Semantics,2012,11(3):14-40.

[9] Zhang X,Yang T,Fan B Q,et al.A novel method for measuring structure and semantic similarity of XML documents based on extended adjacency matrix[C]//Proceedings of international conference on service science.[s.l.]:[s.n.],2012:1452-1461.

[10] Chowdhury I J,Nayak R.A novel method for finding similarities between unordered trees using matrix data model[M].Berlin:Springer,2013:421-430.

[11] Lin Dekang.An information-theoretic definition of similarity[C]//Proceedings of the international conference on machine learning.Madison,Wisconsin,USA:[s.n.],1998:296-304.

[12] Algergawy A,Nayak R,Saake G.Element similarity measures in XML schema matching[J].Information Sciences,2010,180(24):4975-4998.

[13] Tekli J,Chbeir R.Minimizing user effort in XML grammar matching[J].Information Sciences,2012,210(10):1-40.

[14] Huang Guangbin,Zhu Qinyu,Siew C K.Extreme learning machine:theory and applications[J].Neurocomputing,2006,70(1-3):489-501.

[15] Huang Guangbin.An insight into extreme learning machines:random neurons,random features and kernels[J].Cognitive Computation,2014,6(3):376-390.

Similarity of XML Documents in E-government in Era of Big Data

ZHAO Zhen1,2,REN Yong-chang1

(1.College of Information Science and Technology,Bohai University,Jinzhou 121013,China; 2.School of Computer Science and Engineering,Northeastern University,Shenyang 110819,China)

XML has been widely studied as the standard of data exchange in e-government applications.With the arrival of the era of big data,the management of XML data in e-government is also becoming more and more important.In the management of XML data,the similarity of XML documents is the key of XML data integration and XML data classification.In order to study the XML document similarity,the XML document are transformed into tree,extracting the corresponding characteristics of the nodes of the tree,and then using these characteristics to calculate the similarity of nodes,and then the final node similarity can be obtained by the ELM(Extreme Learning Machine) algorithm.Based on the similarity of nodes,the algorithm of similarity comparison of the XML document tree is given,which can obtain the similarity of XML documents.Based on the given specific evaluation indexes,the accuracy,recall,F-measurevaluesandthecorrespondingtimeareobtainedthroughexperimentsintwodifferentdatasetsusingthemethodproposed.Theperformanceadvantagesoftheproposedmethodareverifiedbyexperiments.

XML documents;similarity;feature extracting;synthesizing;data integration

2016-03-28

2016-07-05

時(shí)間：2017-01-04

教育部人文社會(huì)科學(xué)研究青年基金項(xiàng)目(15YJC870028);遼寧省自然科學(xué)基金(2015020009);遼寧省哲學(xué)社會(huì)科學(xué)規(guī)劃基金項(xiàng)目(L15BTQ002);遼寧省社科聯(lián)2015年度遼寧經(jīng)濟(jì)社會(huì)發(fā)展立項(xiàng)課題(2015lslktglx-01)

趙 震(1977-)，男，博士研究生，講師，CCF會(huì)員，研究方向?yàn)槿斯ぶ悄芘c語義Web；任永昌，博士，教授，研究方向?yàn)樵朴?jì)算與軟件項(xiàng)目管理。

http://www.cnki.net/kcms/detail/61.1450.TP.20170104.1039.076.html

TP

A

1673-629X(2017)01-0186-04

10.3969/j.issn.1673-629X.2017.01.042