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

趙 震，任永昌

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

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

趙 震1,2，任永昌1

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

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

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

0 引 言

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

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

文中在節(jié)點相似性的基礎上提出了XML文檔樹的相似性比較算法，從而計算得到XML文檔的相似性，并進行了實驗驗證。

1 XML文檔及樹形表示

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

GeorgeFrankprofessor26John@yahoo．com

圖1 XML文檔實例

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

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

對于XML文檔樹，樹節(jié)點是最基本的數(shù)據(jù)項。一個節(jié)點可以是XML文檔中的元素或?qū)傩浴Ｓ肧imNode(N1,N2)表示來自不同文檔樹節(jié)點N1和N2的相似度。

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

圖2 XML文檔樹實例

(1)標簽相似性度量。

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

(1)

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

(2)深度相似性度量。

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

(2)

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

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

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

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

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

3 超限學習機

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

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

(3)

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

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

(4)

上面的等式可表示為：

Hβ=T

(5)

其中

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

β=H?T

(6)

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

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

ot=βh(xt)

(7)

ELM算法描述如下：

算法1：ELM。

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

輸出：β。

Begin

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

步驟2：計算H;

步驟3：計算β=H?T。

Returnβ

End

4 文檔樹的相似性計算

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

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

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

圖3 基于ELM的相似性擬合

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

算法2：SimNode。

輸入:Node1,Node2；

輸出:SimNode。

Begin

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

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

ReturnSimNode

End

4.2 文檔樹的相似性

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

算法3：SimDocument。

輸入:D1,D2；

輸出:SimDocument。

Begin

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

步驟2：計算每個節(jié)點對的相似度SimNode(nodei,nodej)；

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

ReturnSimDocument

End

5 實 驗

下面通過實驗進一步評估文中提出的XML文檔相似性計算方法的性能。評估相似性比較的性能主要考慮兩方面：有效性和效率。

評估有效性主要有兩個指標：精確度和召回率。下面簡單介紹它們的定義。

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

(8)

(9)

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

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

(10)

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

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

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

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

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

圖5 DBLP和SigmodRecord數(shù)據(jù)集響應時間對比

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

6 結(jié)束語

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

[1] 趙慧勤,趙慧玲.電子政務數(shù)據(jù)交換標準—XML語言[J].山西大同大學學報:社會科學版,2003,17(3):76-78.

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

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

[4] 李冬睿.基于XML與Web Service的電子政務數(shù)據(jù)交換模型的設計與實現(xiàn)[D].桂林:廣西師范大學,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

時間：2017-01-04

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

趙 震(1977-)，男，博士研究生，講師，CCF會員，研究方向為人工智能與語義Web；任永昌，博士，教授，研究方向為云計算與軟件項目管理。

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