數(shù)據(jù)源敏感的多源XML 數(shù)據(jù)相似度量方法*

王繼奎 李少波，2?

(1.中國科學院 成都計算機應(yīng)用研究所，四川 成都 610041;2.貴州大學 現(xiàn)代制造技術(shù)教育部重點實驗室，貴州 貴陽 550003)

可擴展標記語言(XML)成為當前網(wǎng)絡(luò)應(yīng)用中事實的數(shù)據(jù)表達、數(shù)據(jù)交換的標準［1］.由于XML 數(shù)據(jù)的自描述、半結(jié)構(gòu)化性質(zhì)，很難準確地獲得XML數(shù)據(jù)的模式信息.所以，傳統(tǒng)的實體識別技術(shù)難以有效地應(yīng)用在XML 數(shù)據(jù)重復(fù)檢測上來.在多源異構(gòu)的情況下，XML 數(shù)據(jù)的結(jié)構(gòu)信息對相似度計算影響很小，所以不考慮XML 數(shù)據(jù)的結(jié)構(gòu)信息，可將預(yù)處理后的XML 數(shù)據(jù)當作文本信息進行處理.文本相似度在語言學、心理學和信息理論領(lǐng)域被廣泛研究.文本相似度量方法還廣泛地應(yīng)用于文本分類［2］、文本的重復(fù)檢測［3］等領(lǐng)域.傳統(tǒng)的方法利用詞頻信息將文檔建模成一個向量，并利用向量間的余弦相似度計算文檔間的相似度.基于語義的方法則是通過同義詞、蘊涵和冗余等語義關(guān)系進行計算［4］.文獻［5］基于信息論的原理定義了詞與詞的相似度.文獻［6］基于文本句子聚類的技術(shù)提出了判定句子相似性的方法.文獻［7］基于WordNet 提出了SSRM 模型來發(fā)現(xiàn)文本中的相似詞項.文獻［8］最早提出了利用編輯距離來度量兩棵樹的相似度.文獻［9］提出，兩個XML 文檔的距離可以通過計算它們的索引樹來測定.文獻［10］基于文檔的分類提出對詞項權(quán)重進行修正.文獻［11］在預(yù)處理的基礎(chǔ)上，通過建立屬性對象表，提出了Max-merge 算法對XML 重復(fù)對象進行檢測.文獻［12］用樹編輯距離的上下限優(yōu)化基于樹編輯距離的相似檢測算法，降低了相似檢測計算的復(fù)雜度，提高了運算效率.文獻［13］提出了一種遞歸相似度計算方法計算XML 數(shù)據(jù)的相似度.文獻［14］提出了一種對有序樹計算相似度的方法.這些工作從多方面對文本分類與XML 數(shù)據(jù)重復(fù)檢測進行研究.但是在已知數(shù)據(jù)源的情況下，詞項在數(shù)據(jù)源中的分布如何影響詞項的權(quán)重，進而影響XML 數(shù)據(jù)相似度量的研究則很少.與文本信息不同的是，預(yù)處理后的XML 數(shù)據(jù)不僅可以獲得詞項在數(shù)據(jù)中的分布情況，還可以獲得其在數(shù)據(jù)源中的分布情況.通過觀察，發(fā)現(xiàn)很多來源于同一數(shù)據(jù)源的數(shù)據(jù)有許多共同的詞項，其區(qū)分能力顯然低于有同樣逆向文檔頻率的IDF 值［15］且在各數(shù)據(jù)源分布比較均勻的詞項.因此，有必要根據(jù)詞項在數(shù)據(jù)源中的分布情況修正IDF.利用修正后的逆向文檔頻率IDF 將數(shù)據(jù)建模成向量，采用余弦相似度判斷兩個數(shù)據(jù)是否相似.這樣就排除了其他因素的干擾，得以單獨觀察已知數(shù)據(jù)源對XML 數(shù)據(jù)相似度量的影響.

文中利用含有詞項f 的數(shù)據(jù)xi、xj出現(xiàn)在不同數(shù)據(jù)源的概率定義詞項f 的數(shù)據(jù)源敏感度ρ 作為詞項f 權(quán)重的修正系數(shù)，并基于修正后的詞項權(quán)重向量定義了XML 數(shù)據(jù)xi、xj的相似度函數(shù).最后在模擬數(shù)據(jù)集與真實數(shù)據(jù)集上進行了實驗.

1 詞項的數(shù)據(jù)源敏感度

1.1 定義

定義1 待檢測數(shù)據(jù)集合D={x1，x2，…，xm}，xj表示標號為j 的XML 數(shù)據(jù).Q ( xj)表示xj的詞項集合，也用Qj表示，可看作是xj各屬性的義原詞集合的并集.

定義3 數(shù)據(jù)源集合S={s(xi):xiD}，si表示數(shù)據(jù)xi的數(shù)據(jù)源.

定義5 ID(f)表示詞項f 逆向文檔頻率，ID(f)=

定義6 詞項權(quán)重向量w(xi)=〈b1，b2，…，如果fkQ(xj)，ak=1;否則ak=0，bk=akID(fk).

定義7 Df={xiD:fQ(xi)};nf=eD(f).ns，f={xiD:fQ(xi)＆＆ si=s}.Df表示數(shù)據(jù)集D 中包含詞項f 的數(shù)據(jù)子集;nf表示數(shù)據(jù)集D 中包含詞項f的數(shù)據(jù)個數(shù);ns，f表示數(shù)據(jù)源s 提供的數(shù)據(jù)集中包含詞項f 的數(shù)據(jù)個數(shù).

1.2 數(shù)據(jù)源敏感度

度量詞項f 的數(shù)據(jù)源敏感度的測度ρ 需要滿足以下性質(zhì):

(2)ρf=0 時滿足?xi，xj，xiDf，xjDf且xi≠xj→s(xi)=s(xj)，即詞項f 僅來源于同一數(shù)據(jù)源.

(3)ρf=1 時，滿足?xi，xj，xiDf，xjDf且xi≠xj→s(xi)≠s(xj)，即每個數(shù)據(jù)源最多只存在一個詞項f.

(4)當ρf(0，1)時，滿足?xi，xj，xiDf，xjDf，xi≠xj且s(xi)≠s(xj).即至少有兩個數(shù)據(jù)源提供詞項f.

令pf為xiDf，xjDf，xi≠xj時s(xi)≠s(xj)的概率.則

xi～Df＆＆ xj～Df表示先從Df中取出一個元素xi，接著從Df再取出一個元素xj.p(f)表示詞項f 出現(xiàn)在XML 數(shù)據(jù)xi、xj中，而xi、xj不屬于同一數(shù)據(jù)源的概率.一般情況下nf≠1，nf=1 表示詞項在所有數(shù)據(jù)中僅出現(xiàn)一次，對XML 數(shù)據(jù)重復(fù)檢測的意義不大，在實現(xiàn)中不考慮.

顯然，pf滿足詞項f 的數(shù)據(jù)源敏感度測度ρf的4 個性質(zhì).定義

當pf=0 時表示詞項f 僅僅分布在一個數(shù)據(jù)源中;當pf=1 表示每個數(shù)據(jù)源最多僅有一個詞項f，分布最分散，因而增大詞項f 的權(quán)重.β{0，1}，作為修正標記，β=0 表示不修正，β=1 表示修正.

2 相似度函數(shù)

基于IDF 的相似度函數(shù)為

式中，wi=〈b1，b2，…，b|VD|〉.

XML 數(shù)據(jù)不同于一般的文本數(shù)據(jù)，詞項f 的權(quán)重可以使用ID(f)度量.因為處理后XML 數(shù)據(jù)中，詞項f 多次出現(xiàn)在同一XML 數(shù)據(jù)中的概率很低，就不再考慮詞頻的影響.

數(shù)據(jù)源敏感的相似度函數(shù)為

式(4)對式(3)中的詞項權(quán)重進行了修正，新的相似度函數(shù)考慮詞項f 的數(shù)據(jù)源敏感度.

XML 數(shù)據(jù)的相似度依然采用向量的余弦相似度度量.在具體實現(xiàn)相似度函數(shù)時，有多種實現(xiàn)公式.一般情況下，如果兩個XML 數(shù)據(jù)有相同的詞項，詞項的敏感度大說明其出現(xiàn)在不同數(shù)據(jù)源的概率就大，其對相似度計算結(jié)果的貢獻也應(yīng)該大.直觀地講，有相同詞項的兩個數(shù)據(jù)，其來源于不同數(shù)據(jù)源重復(fù)的概率要大于來源于同一數(shù)據(jù)源的概率.因為，同一數(shù)據(jù)源的數(shù)據(jù)有很多相同的詞項，而且同一數(shù)據(jù)源的數(shù)據(jù)在進行數(shù)據(jù)集成前一般是進行過數(shù)據(jù)清洗的，其重復(fù)的可能性本來就小.相反，來源于不同數(shù)據(jù)源的數(shù)據(jù)從整體上看各數(shù)據(jù)源可看作真實世界的視圖，有著巨大的交集.不同的數(shù)據(jù)源分別對客觀世界的實體做出了獨立的描述，極端的情況是每個數(shù)據(jù)源針對同一客觀實體各自獨立提供一個描述.所以，修正后的相似度函數(shù)增加了實體描述的各數(shù)據(jù)源共有的個性詞項的權(quán)重，從而降低了數(shù)據(jù)源特有詞項的權(quán)重.理論上，同樣相似度閾值的情況下，式(4)應(yīng)該比式(3)有更高的召回率，也應(yīng)該有更高的F 測度值.

3 實驗結(jié)果與分析

與普通的文本不同，XML 數(shù)據(jù)是半結(jié)構(gòu)化數(shù)據(jù)，在集成過程中通常文件比較小，且抽取時可完成數(shù)據(jù)源標識;由于其來源異構(gòu)的特性，發(fā)現(xiàn)其模式信息比較困難.所以針對這些特點，在實驗中將XML數(shù)據(jù)預(yù)處理后，將其看作有數(shù)據(jù)源及唯一標識的普通文本.實驗對異構(gòu)數(shù)據(jù)模式、內(nèi)容比較雜亂無章的XML 數(shù)據(jù)進行驗證，不考慮蘊涵、冗余等語義關(guān)系，也不考慮詞項的層次信息.實驗環(huán)境為Eclipse3.4、jdk1.6、Win7(64 位)，內(nèi)存為8 G.

3.1 XML 數(shù)據(jù)預(yù)處理

對于來源于不同數(shù)據(jù)源的XML 數(shù)據(jù)進行添加數(shù)據(jù)源標識.改造后的數(shù)據(jù)模式為

x'i=(oi，s，Qi).

式中，oi表示數(shù)據(jù)唯一標號，Qi表示XML 數(shù)據(jù)預(yù)先去除XML 標記、空值后的詞項集合.所以，在XML數(shù)據(jù)預(yù)處理后，實驗數(shù)據(jù)變成帶有數(shù)據(jù)源信息及唯一標識的文本信息.

3.2 數(shù)據(jù)相似度實驗

通過實驗觀察詞項權(quán)重修正系數(shù)ρ 對相似度計算的影響，數(shù)據(jù)集為模擬數(shù)據(jù)集.經(jīng)過處理后的XML 數(shù)據(jù)與表1 中的數(shù)據(jù)具有一樣的模式.部分數(shù)據(jù)相似度計算結(jié)果見表2.

數(shù)據(jù)〈5，9〉的兩種方法相似度計算結(jié)果均為1.000，通過查看表得知兩組數(shù)據(jù)完全相同，所以結(jié)果合理.數(shù)據(jù)〈1，5〉通過IDF 方法與ds.IDF 方法的計算結(jié)果差距較大.f1={guitar，hero，IIIX，gameboy，from，Toys-R-us}，f5={guitar，hero，IIIX，for，gameboy};在閾值為0.5 的情況下，Simds.IDF認為兩者是相似的，而SimIDF則認為兩者不相似.查看各詞項權(quán)重計算結(jié)果，發(fā)現(xiàn)詞項IIIX 的權(quán)重從IDF 計算的1.18 變成修正后的2.71，而Toys-R-us 的權(quán)重(1.87)沒有變化.這也意味者詞項IIIX 在相似度計算時，詞項IIIX 與詞項Toys-R-us 的權(quán)重對比發(fā)生了逆轉(zhuǎn).其原因是IIIX 在3 個數(shù)據(jù)源都有分布，且均勻;而Toys-R-us 僅存在于1 個數(shù)據(jù)源中.所以詞項IIIX 的區(qū)分能力強于詞項Toys-R-us，計算結(jié)果符合預(yù)期，也更合理.其他詞項可類似分析.這解釋了為什么對于數(shù)據(jù)〈1，5〉，Simds.IDF計算的結(jié)果大于SimIDF的結(jié)果.實際觀察也發(fā)現(xiàn)，從某種意義上來說標號1 和標號5標識了來源于不同數(shù)據(jù)源的同一實體，其現(xiàn)實世界的唯一標識很可能是guitar+hero +IIIX.顯然，是否為同一實體，與數(shù)據(jù)的解釋密切相關(guān).同樣的方法可以解釋為什么數(shù)據(jù)〈2，3〉的計算結(jié)果差別大.從以上分析可看到，數(shù)據(jù)源的確對數(shù)據(jù)相似度計算有影響.對表1 提供的數(shù)據(jù)進行重復(fù)檢測，結(jié)果顯示ds.IDF 方法在相似度閾值為0.6 時，重復(fù)數(shù)據(jù)檢測召回率比IDF方法提高了36.4%.

表1 測試數(shù)據(jù)Table 1 Test dataset

表2 部分數(shù)據(jù)相似度計算結(jié)果Table 2 Results of some similary experiments

3.3 真實數(shù)據(jù)集實驗

實驗數(shù)據(jù)來源于常用的Books-Authors 數(shù)據(jù)集，抽取了包括A1Books 在內(nèi)的84 個數(shù)據(jù)源的9 個不同ISBN 的書籍信息.處理后的數(shù)據(jù)格式為{o，s，z，q1，q2，…，qn}，如{1，A1Books，9780073516677，O'Leary，Timothy J.，O'Leary，Linda I.}.計算F 測度的依據(jù)為:如果IDF 方法或ds.IDF 方法計算的相似度大于閾值且其ISBN 相同，就認為檢測出一個重復(fù)數(shù)據(jù);否則認為做了一個錯誤檢測.最后統(tǒng)計正確檢測、錯誤檢測以及總數(shù)，并計算F 測度值.

實驗結(jié)果表明在相似度閾值 為0.8、0.5、0.2的情況下，IDF 方法的F 測度值分別為0.26、0.63和0.96，ds.IDF 方法的分別為0.29、0.68 和0.98.在相同相似度閾值的情況下，ds.IDF 方法重復(fù)檢測的F 測度值均略高于IDF 方法，真實數(shù)據(jù)上的實驗也驗證了修正后的詞項權(quán)重，提高了重復(fù)數(shù)據(jù)檢測的F 測度值.實驗結(jié)果與預(yù)期相符.可以得出結(jié)論:基于修正后IDF 的相似度函數(shù)在XML 重復(fù)數(shù)據(jù)檢測中提高了有效性.同時也看到在 較高的情況下，F(xiàn) 測度值很低，原因是不同數(shù)據(jù)源對于同一實體的描述差別很大，從相似度的角度很難判斷其為同一實體.計算結(jié)果也表明兩種方法的準確率幾乎都是100%，原因是Books-Authors 數(shù)據(jù)集中兩個不同的實體之間的相似度很小，基本在0.2 以下.

4 結(jié)論

文中在IDF 作為詞項權(quán)重度量的基礎(chǔ)上，進一步考慮了已知數(shù)據(jù)源對詞項權(quán)重的影響;將IDF 的思想推廣到詞項權(quán)重的數(shù)據(jù)源敏感性上，提出利用提供相同詞項的待檢測數(shù)據(jù)不在同一數(shù)據(jù)源中的概率度量詞項的數(shù)據(jù)源敏感度，并作為修正IDF 的依據(jù).模擬及真實數(shù)據(jù)集上的實驗表明，修正后的相似度函數(shù)有效性更好，其重復(fù)檢測的F 測度值也更高，結(jié)果符合預(yù)期.相似度函數(shù)的應(yīng)用十分廣泛，下一步擬將數(shù)據(jù)源敏感的數(shù)據(jù)相似度度量方法應(yīng)用在數(shù)據(jù)挖掘的分類、聚類領(lǐng)域.

［1］孔令波，唐世渭，楊冬青，等.XML 數(shù)據(jù)的查詢技術(shù)［J］.軟件學報，2007，18(6):1400-1418.Kong Ling-bo，Tang Shi-wei，Yang Dong-qing，et al.Querying techniques for XML data［J］.Journal of Software，2007，18(6):1400-1418.

［2］Ko Y，Park J，Seo J.Improving text categorization using the importance of sentences［J］.Information Processing ＆Management，2004，40(1):65-79.

［3］Theobald M，Siddharth J，Paepcke A.Spotsigs:robust and efficient near duplicate detection in large web collections［C］∥Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.Singapore:ACM，2008:563-570.

［4］黃承慧，印鑒，侯昉.一種結(jié)合詞項語義信息和TF-IDF方法的文本相似度量方法［J］.計算機學報，2011，34(5):856-864.Huang Cheng-hui，Yin Jian，Hou Fang.A text similarity measurement combining word semantic information with TF-IDF method［J］.Chinese Journal of Computers，2011，34(5):856-864.

［5］Lin D.An information-theoretic definition of similarity［C］∥Proceedings of the Fifteenth International Conference on Machine Learning.San Francisco:Morgan Kaufmann Publishers Inc，1998:296-304.

［6］Aliguliyev R M.A new sentence similarity measure and sentence based extractive technique for automatic text summarization［J］.Expert Systems with Applications，2009，36(4):7764-7772.

［7］Hliaoutakis A，Varelas G，Voutsakis E，et al.Information retrieval by semantic similarity［J］.International Journal on Semantic Web and Information Systems (IJSWIS)，2006，2(3):55-73.

［8］Tai K C.The tree-to-tree correction problem［J］.Journal of the ACM(JACM)，1979，26(3):422-433.

［9］鄭仕輝，周傲英，張龍.XML 文檔的相似測度和結(jié)構(gòu)索引研究［J］.計算機學報，2003，26(9):1116-1122.Zheng Shi-hui，Zhou Ao-ying，Zhang Long.Similarity measure and structural index of XML documents ［J］.Chinese Journal of Computers，2003，26(9):1116-1122.

［10］Zhang Yun-tao，Gong Ling，Wang Yong-cheng.An improved TF-IDF approach for text classification ［J］.Journal of Zhejiang University Science A，2005，6A (1):49-55.

［11］李亞坤，王宏志，高宏，等.基于實體描述屬性技術(shù)的XML 重復(fù)對象檢測方法［J］.計算機學報，2011，34(11):2131-2141.Li Ya-kun，Wang Hong-zhi，Gao Hong，et al.Efficient entity resolution on XML data based on entity-describeattribute［J］.Chinese Journal of Computers，2011，34(11):2131-2141.

［12］陳偉，丁秋林.一種XML 相似重復(fù)數(shù)據(jù)的清理方法研究［J］.北京航空航天大學學報，2004，30(9):835-838.Chen Wei，Ding Qiu-lin.Study on an XML approximately duplicated data cleaning method［J］.Journal of Bejing University of Aeronautics and Astronautics，2004，30(9):835-838.

［13］張丙奇，白碩，趙章界.XML 數(shù)據(jù)相似度研究［J］.計算機工程，2005，31(11):25-27.Zhang Bing-qi，Bai Shuo，Zhao Zhang-jie.A recursive method to compute similarity of XML documents ［J］.Computer Engineering，2005，31(11):25-27.

［14］Akutsu T，F(xiàn)ukagawa D，Takasu A.Approximating tree edit distance through string edit distance［J］.Algorithmica，2010，57(2):325-348.

［15］Jones K S.A statistical interpretation of term specificity and its application in retrieval［J］.Journal of Documentation，1972，28(1):11-21.