面向智慧民生領(lǐng)域的增量交互式數(shù)據(jù)集成方法

夏 丁 王亞沙 趙梓棚 崔 達(dá)

1(高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室(北京大學(xué)) 北京 100871)2(北京大學(xué)信息科學(xué)技術(shù)學(xué)院 北京 100871)3 (軟件工程國家工程研究中心(北京大學(xué)) 北京 100871) (fabkxd@foxmail.com)

面向智慧民生領(lǐng)域的增量交互式數(shù)據(jù)集成方法

夏 丁1,2王亞沙1,3趙梓棚1,2崔 達(dá)1,2

1(高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室(北京大學(xué)) 北京 100871)2(北京大學(xué)信息科學(xué)技術(shù)學(xué)院 北京 100871)3(軟件工程國家工程研究中心(北京大學(xué)) 北京 100871) (fabkxd@foxmail.com)

智慧民生作為智慧城市的重點(diǎn)領(lǐng)域，包含眾多應(yīng)用系統(tǒng)，積累了大量層次結(jié)構(gòu)數(shù)據(jù).為了形成城市范圍完整數(shù)據(jù)集，需要集成并統(tǒng)一異構(gòu)的數(shù)據(jù)模式，向用戶提供統(tǒng)一的數(shù)據(jù)視圖.針對(duì)智慧民生領(lǐng)域的領(lǐng)域知識(shí)寬泛、缺乏中文語義匹配支持、模式數(shù)量眾多、元素標(biāo)簽缺失但實(shí)例數(shù)據(jù)豐富等幾方面特點(diǎn)，提出了一種增量交互式模式集成方法.該方法采用增量迭代的方式逐步完成多模式集成任務(wù)，大幅降低集成計(jì)算量；在模式匹配階段，綜合利用模式信息和實(shí)例數(shù)據(jù)構(gòu)造了多種適用于中文且能力互補(bǔ)的匹配器，并通過相似度熵來度量機(jī)器的決策置信度，適度引入人工干預(yù)；在中介模式生成階段，處理模式間可能出現(xiàn)的各種沖突，最終輸出全局統(tǒng)一的中介模式.利用從互聯(lián)網(wǎng)爬取的多源二手房數(shù)據(jù)設(shè)計(jì)并完成實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明:此方法在人工干預(yù)程度足夠小的前提下，具有較好的模式匹配準(zhǔn)確性.

模式匹配;模式集成;數(shù)據(jù)集成;智慧城市;智慧民生

智慧民生是智慧城市建設(shè)的重要領(lǐng)域，涉及服務(wù)于市民“衣、食、住、行”等生活服務(wù)的眾多應(yīng)用系統(tǒng).這些應(yīng)用在向市民提供服務(wù)的同時(shí)，積累了大量的數(shù)據(jù)，層次結(jié)構(gòu)數(shù)據(jù)占這些數(shù)據(jù)的主體部分.典型的層次結(jié)構(gòu)數(shù)據(jù)包括：在Web應(yīng)用中廣泛使用的XML文檔，以及在系統(tǒng)后臺(tái)普遍使用的關(guān)系型數(shù)據(jù)等.通常單一應(yīng)用系統(tǒng)中的數(shù)據(jù)并不完整，只有充分集成多個(gè)系統(tǒng)中的數(shù)據(jù)才能形成整個(gè)城市范圍內(nèi)較為全面的數(shù)據(jù)集，以滿足智慧城市中集成化、智能化的應(yīng)用的需求.以二手房交易領(lǐng)域?yàn)槔壳霸谥袊鞘兄袘?yīng)用較多的二手房交易信息交流平臺(tái)眾多，包括：專業(yè)二手房交易平臺(tái)(如鏈家、安居客、我愛我家、搜房網(wǎng)、愛屋吉屋、房通網(wǎng)等)、本地生活服務(wù)類網(wǎng)站(如趕集網(wǎng)、58同城、百姓網(wǎng)等)以及城市本地論壇(如新浪樂居、西祠胡同房產(chǎn)、大量以城市名稱命名的本地綜合論壇等).這些系統(tǒng)中都包含大量待售二手房的數(shù)據(jù)，然而單一系統(tǒng)中的數(shù)據(jù)都不完整.某個(gè)城市中，有購房需求的市民，往往需要逐一瀏覽多個(gè)系統(tǒng)，并人工實(shí)現(xiàn)數(shù)據(jù)的集成，才能對(duì)此城市中二手房的信息有較為全面的了解，效率很低.另外，城市管理規(guī)劃部門或市場(chǎng)調(diào)研機(jī)構(gòu)，若要對(duì)某城市二手房交易情況進(jìn)行調(diào)研分析，也必須從多個(gè)系統(tǒng)獲取數(shù)據(jù)并實(shí)現(xiàn)數(shù)據(jù)的集成.

源自不同系統(tǒng)的數(shù)據(jù)往往具有不同的數(shù)據(jù)模式(data schema)，要實(shí)現(xiàn)數(shù)據(jù)的集成，必須首先為來自不同系統(tǒng)的數(shù)據(jù)構(gòu)造一個(gè)全局、統(tǒng)一的數(shù)據(jù)模式，即實(shí)現(xiàn)數(shù)據(jù)模式的集成(schema integration).傳統(tǒng)的模式集成技術(shù)[1-5]的典型應(yīng)用場(chǎng)景包括：電子商務(wù)領(lǐng)域的產(chǎn)品目錄等數(shù)據(jù)模式的演化、公司并購過程中的數(shù)據(jù)系統(tǒng)集成等.這些場(chǎng)景中，待集成的源數(shù)據(jù)模式個(gè)數(shù)較少，結(jié)構(gòu)較為規(guī)范，預(yù)置的領(lǐng)域知識(shí)較為豐富，相較而言，智慧民生領(lǐng)域的數(shù)據(jù)存在3個(gè)特征：

1) 領(lǐng)域范圍寬泛，缺乏解決術(shù)語語義匹配的支持機(jī)制.智慧民生領(lǐng)域尚缺乏數(shù)據(jù)相關(guān)標(biāo)準(zhǔn)，模式元素標(biāo)簽所使用的術(shù)語差異巨大.例如二手房數(shù)據(jù)中，關(guān)于交易中介人就存在“代理”、“經(jīng)紀(jì)人”、“顧問”、“秘書”、“管家”等10余種同義詞.由于民生領(lǐng)域涉及市民生活的方方面面，范圍十分寬泛，如果試圖建立領(lǐng)域詞典或知識(shí)庫來解決元素標(biāo)簽的語義匹配問題，工作量巨大，且難以在短期內(nèi)完成.而現(xiàn)有的通用知識(shí)庫均以英文為主，對(duì)中文支持不足.已有的基于字符串的模式匹配算法，如公共前綴長度、公共后綴長度、編輯距離等，也無法適用于中文標(biāo)簽.

2) 模式數(shù)量眾多，傳統(tǒng)集成方式效率低.智慧民生領(lǐng)域中需要集成的數(shù)據(jù)源眾多.以二手房領(lǐng)域?yàn)槔瑢?duì)普通大中型城市而言，包含本城市二手房數(shù)據(jù)的信息系統(tǒng)超過20個(gè).傳統(tǒng)的兩兩模式集成方式，要求每個(gè)已知源模式或者新加入的源模式都要與其他源模式進(jìn)行1次集成，這種處理方式的復(fù)雜度與源模式數(shù)量的平方成正比例，且可擴(kuò)展性不好，效率太低.另外，傳統(tǒng)的模式集成中，部分工作會(huì)引入人工參與以解決算法難以判定的元素匹配和沖突解決問題.在模式數(shù)量大幅增加的情況下，何時(shí)選擇人工參與的標(biāo)準(zhǔn)必須嚴(yán)格控制，否則將導(dǎo)致大量的人工任務(wù)，從而導(dǎo)致方法效率降低和成本的增加.

3) 模式元素標(biāo)簽部分缺失，而實(shí)例數(shù)據(jù)較為豐富.智慧民生領(lǐng)域待集成的數(shù)據(jù)很多都是從互聯(lián)網(wǎng)抓取的Web表格，存在部分模式元素標(biāo)簽缺失的情況，這是傳統(tǒng)的元素級(jí)別匹配算法效果不佳的另一個(gè)重要原因.而另一方面，實(shí)例數(shù)據(jù)是比較豐富的，可以通過對(duì)實(shí)例數(shù)據(jù)的分析輔助模式匹配.然而，進(jìn)一步分析表明不同系統(tǒng)中數(shù)據(jù)源的實(shí)例數(shù)據(jù)并不是完全的重合，例如：某些在鏈家網(wǎng)上發(fā)布房源的房主并不會(huì)同時(shí)將房源發(fā)布在我愛我家網(wǎng)上.因此通過數(shù)據(jù)實(shí)例的重復(fù)度來判斷元素之間的相似性也是不夠準(zhǔn)確的.

本文針對(duì)以上問題，結(jié)合民生領(lǐng)域數(shù)據(jù)特征以及傳統(tǒng)的模式匹配技術(shù)和模式集成技術(shù)，提出并實(shí)現(xiàn)了一種“面向智慧民生領(lǐng)域?qū)哟谓Y(jié)構(gòu)數(shù)據(jù)的增量交互式模式集成方法”.該方法采用增量迭代的方式，每次集成2個(gè)模式，并將集成的結(jié)果表達(dá)為中介模式，后續(xù)集成基于前序集成的結(jié)果進(jìn)行，在源模式數(shù)量較多的情況下，大大減少了源模式間集成的次數(shù)；而在每一次集成迭代內(nèi)部，通過元素聚類等預(yù)處理工作，大大縮小元素匹配的搜索空間和比對(duì)次數(shù)，進(jìn)一步減少了工作量.在模式匹配階段，針對(duì)智慧民生領(lǐng)域數(shù)據(jù)的特點(diǎn)，綜合利用模式信息和實(shí)例數(shù)據(jù)，構(gòu)造了多種適應(yīng)于中文處理、且能力互補(bǔ)的匹配器進(jìn)行元素匹配，并通過計(jì)算相似度熵度量候選元素相似度的差異性，僅在差異性不夠明顯時(shí)才引入人工參與，較好地權(quán)衡了人工參與工作量和最終結(jié)果的準(zhǔn)確性.而中介模式生成過程則控制模式中元素遍歷的順序，并處理匹配完成之后源模式間可能出現(xiàn)的各種復(fù)雜沖突，綜合考慮了效率和中介模式的質(zhì)量.算法最終的輸出是全局統(tǒng)一的中介模式以及各源模式與中介模式元素之間的匹配映射關(guān)系.本文利用從互聯(lián)網(wǎng)爬取的二手房源信息數(shù)據(jù)設(shè)計(jì)并完成實(shí)驗(yàn)，對(duì)本文的數(shù)據(jù)集成方案的有效性和高效性進(jìn)行了驗(yàn)證.

1 模式集成技術(shù)

模式集成可分解成2部分內(nèi)容：模式匹配(schema matching)與中介模式生成(mediated schema generation).

1.1 模式匹配技術(shù)

模式匹配主要目標(biāo)是針對(duì)2個(gè)待匹配的數(shù)據(jù)模式(稱為源模式)中的元素集合S1，S2，構(gòu)造S1與S2之間的映射M以描述具有相同或相似語義的元素對(duì)應(yīng)關(guān)系.模式匹配問題中有多種匹配標(biāo)準(zhǔn)(matching criteria)，比如字符串相似性、詞匯語義相似性、結(jié)構(gòu)相似性等.能夠按照一個(gè)既定的匹配標(biāo)準(zhǔn)，獨(dú)立完成2個(gè)元素間相似度計(jì)算的算法稱為基本匹配器(elementary matcher)[6].基本的模式匹配技術(shù)按照所依賴信息的不同，可分為基于模式信息的匹配技術(shù)(schema level matching)和基于實(shí)例數(shù)據(jù)的匹配技術(shù)(instance data matching).

基于模式信息的匹配技術(shù)關(guān)注數(shù)據(jù)模式的元信息，其從匹配粒度的角度，可分為基于元素(element level)與基于結(jié)構(gòu)(structure level)的技術(shù)[7].基于元素的匹配算法忽略節(jié)點(diǎn)之間的層次結(jié)構(gòu)關(guān)系，獨(dú)立地分析挖掘單個(gè)元素對(duì)的相似性，又可細(xì)分為3類：

1) 基于字符串相似度.計(jì)算字符串相似度的算法包括相同前后綴長度[2，6]、編輯距離[1-2，6]和n-gram[1-2]等，這類算法對(duì)中文標(biāo)簽的處理效果欠佳；

2) 基于語言學(xué)資源的匹配器.這類技術(shù)很好地挖掘了字符串背后豐富的語言學(xué)涵義，但依賴外部可用的語義知識(shí)詞典資源[8]，如WordNet[9]；

3) 基于詞共現(xiàn)關(guān)聯(lián)的匹配器.這種模式匹配技術(shù)從源模式中節(jié)點(diǎn)標(biāo)簽的關(guān)聯(lián)規(guī)律來挖掘節(jié)點(diǎn)的語義相似性[10-11]，能夠同時(shí)處理大量待匹配源模式，但通用性較差.

基于結(jié)構(gòu)的匹配算法關(guān)注包含目標(biāo)節(jié)點(diǎn)及鄰近元素的子結(jié)構(gòu)間的相似性，一般將輸入的源模式轉(zhuǎn)換為有向圖的形式，具體算法包括：

1) 圖(樹)匹配算法[12-13]；

2) 路徑匹配算法[3，14]；

基于模式信息的匹配技術(shù)，算法運(yùn)行效率較高，但是該技術(shù)要求數(shù)據(jù)模式的元信息完整且僅適用于英文標(biāo)簽，而智慧民生領(lǐng)域的數(shù)據(jù)中，主要采用中文標(biāo)簽且標(biāo)簽術(shù)語使用隨意，甚至存在標(biāo)簽缺失的情況，因而導(dǎo)致該技術(shù)的匹配準(zhǔn)確性難以保障.

基于實(shí)例信息的匹配技術(shù)直接從數(shù)據(jù)實(shí)例中挖掘模式元素的相似性，可以使用于數(shù)據(jù)模式元信息不足、缺失或不可靠的應(yīng)用場(chǎng)景，但同時(shí)也會(huì)帶來較大的系統(tǒng)開銷.其從信息提取的角度，可分為基于統(tǒng)計(jì)數(shù)據(jù)和基于內(nèi)容的方法.基于統(tǒng)計(jì)數(shù)據(jù)的方法忽略實(shí)例數(shù)據(jù)的具體內(nèi)容，統(tǒng)計(jì)元素所有實(shí)例的統(tǒng)計(jì)特征形成元素的特征向量，然后利用機(jī)器學(xué)習(xí)相關(guān)技術(shù)來將匹配問題轉(zhuǎn)化為分類問題[16]，這種方法由于沒有考慮實(shí)例的具體內(nèi)容，準(zhǔn)確率較低，但召回率相對(duì)較高，且訓(xùn)練速度快，計(jì)算效率高；基于內(nèi)容的方法通過字符串匹配、TF-IDF文檔相似度等算法計(jì)算實(shí)例之間的相似度，然后加權(quán)平均得到元素之間的實(shí)例相似度[17-18]，這種方法的匹配準(zhǔn)確率較高，但由于存在實(shí)例子集合問題，即2個(gè)表達(dá)相同概念的元素，其實(shí)例都不全面且恰好互補(bǔ)，會(huì)導(dǎo)致計(jì)算出的相似度偏低，故召回率低，且計(jì)算復(fù)雜度高.智慧民生領(lǐng)域的多源數(shù)據(jù)實(shí)例豐富，但不同子領(lǐng)域中不同源數(shù)據(jù)的實(shí)例重合度差異明顯，因此應(yīng)該綜合基于統(tǒng)計(jì)和基于內(nèi)容2類方法，才能提供穩(wěn)定的匹配準(zhǔn)確性.

1.2 中介模式生成技術(shù)

中介模式生成技術(shù)一般先利用模式匹配技術(shù)確定元素之間的相似度或匹配關(guān)系，然后通過制定一系列算法和策略，發(fā)現(xiàn)并解決源模式中元素命名、元素定義、元素結(jié)構(gòu)關(guān)系不一致等沖突，整合所有源模式的元素，完成中介模式的生成，向數(shù)據(jù)用戶屏蔽模式的異構(gòu)性[4].中介模式的生成過程中需要解決同義詞、數(shù)據(jù)類型、結(jié)點(diǎn)子結(jié)構(gòu)、嵌套路徑4類沖突，并針對(duì)問題場(chǎng)景制定沖突解決策略[4-5，19-20].另外，除了沖突解決策略，輸入源模式的數(shù)量也對(duì)全局中介模式的構(gòu)造帶來影響.傳統(tǒng)的解決方案如XSIQ[4]，面向2個(gè)源模式，只需要進(jìn)行1次集成，但當(dāng)輸入的源模式有多個(gè)時(shí)，直接利用面向2個(gè)源模式的技術(shù)會(huì)導(dǎo)致計(jì)算復(fù)雜度過高，因此需要設(shè)計(jì)整體的集成方案.XINTOR[20]是一種基于統(tǒng)計(jì)的整體式模式集成技術(shù)，它面向多個(gè)XML源模式，以元素結(jié)構(gòu)的統(tǒng)計(jì)特征為依據(jù)，構(gòu)造中介模式，這種方案效率有所提高，但可擴(kuò)展性差，新加入的源模式仍然難以處理.另一種思路是以中介模式為媒介，讓所有源模式都與中介模式進(jìn)行集成，這樣不僅算法效率提高而且可擴(kuò)展性也較強(qiáng).在一些方法[21]中，專家會(huì)預(yù)先制定一個(gè)中介模式，但這種方法在民生領(lǐng)域存在大量不規(guī)范同源異構(gòu)模式的背景下，專家負(fù)擔(dān)太重.實(shí)際上若有某種算法可以自動(dòng)根據(jù)所有源模式生成中介模式，完全可以避免這部分人工工作，如PORSCHE[19]就是自動(dòng)完成中介模式的構(gòu)建，每次迭代集成1個(gè)源模式，同時(shí)增量地對(duì)中介模式進(jìn)行更新和擴(kuò)充，其缺陷體現(xiàn)在模式匹配技術(shù)只利用了模式上的信息，準(zhǔn)確率有限，而且沖突解決策略簡(jiǎn)單，部分沖突并沒有加以考慮，導(dǎo)致中介模式質(zhì)量不高.

2 本文方法結(jié)構(gòu)

本文所設(shè)計(jì)的解決方案框架如圖1所示.系統(tǒng)的主要輸入是n個(gè)源模式的模式信息和實(shí)例數(shù)據(jù)，同時(shí)還有專家的人工干預(yù)作為輔助輸入，主要輸出是中介模式.在算法運(yùn)行過程中，中介模式作為媒介，所有其他源模式依次與中介模式進(jìn)行匹配和集成，并增量式地更新和擴(kuò)充中介模式.系統(tǒng)中的核心組成部分是預(yù)處理模塊和增量式模式集成迭代模塊.

Fig. 1 Method framework圖1 本文方法框架

預(yù)處理模塊接受源模式的輸入，負(fù)責(zé)調(diào)用元素級(jí)別匹配器，計(jì)算所有源模式元素中每2個(gè)元素之間的元素級(jí)別相似度，然后基于相似度結(jié)果對(duì)所有元素進(jìn)行聚類，將標(biāo)簽字符串上相似或者語義上相似的元素聚為同一類，聚類的目的是降低后續(xù)計(jì)算的復(fù)雜度.

模式集成模塊在聚類結(jié)果以及專家的人工參與的支持下，以源模式、中介模式和數(shù)據(jù)實(shí)例為輸入，實(shí)施模式集成過程.首先需要從n個(gè)輸入源模式中選出1個(gè)作為初始中介模式，然后讓剩下的n-1個(gè)源模式依次與中介模式進(jìn)行融合，即共n-1輪迭代過程.每輪迭代都是一個(gè)完整模式集成過程，該過程由中介模式生成模塊和模式匹配模塊結(jié)合完成：在候選匹配模式元素選擇與集成子模塊(后簡(jiǎn)稱“元素集成子模塊”)的指導(dǎo)下，以深度優(yōu)先的順序從根元素開始遍歷當(dāng)前源模式，對(duì)當(dāng)前源模式上的每個(gè)元素，利用前面的聚類結(jié)果找出當(dāng)前中介模式上與之屬于同一聚類的所有元素作為候選元素，然后調(diào)用模式匹配模塊對(duì)這些候選元素進(jìn)行綜合相似度計(jì)算并選出最合適的一個(gè)，由此達(dá)到降低復(fù)雜度的效果.

模式匹配模塊中，模式匹配算法使用了利用模式信息的元素級(jí)別匹配器、祖先路徑匹配器和樹編輯距離匹配器，以及利用實(shí)例信息的基于統(tǒng)計(jì)匹配器、基于內(nèi)容匹配器，其中的一些匹配器針對(duì)中文特點(diǎn)進(jìn)行了修正或替代，且匹配器之間的結(jié)合方式都針對(duì)每種匹配器的性能特點(diǎn)進(jìn)行了合理且高效的設(shè)計(jì)；基于相似度熵的人工干預(yù)決策選擇模塊針對(duì)候選元素的這些綜合相似度，通過相似度熵的計(jì)算可以判斷是否需要人工干預(yù)，若需要，系統(tǒng)就會(huì)向?qū)＜覓伋鰡栴}.匹配結(jié)果仲裁子模塊綜合各候選元素的綜合相似度以及專家的反饋結(jié)果確定待匹配元素的最終匹配對(duì)象.

匹配對(duì)象確定之后，沖突解決子模塊將被調(diào)用以處理匹配完成之后模式之間可能出現(xiàn)的各種復(fù)雜沖突.每輪迭代完成，中介模式都會(huì)有所更新和擴(kuò)充，其中的元素映射表也會(huì)不斷擴(kuò)展，直到n-1輪迭代都完成，所得到的中介模式和元素映射表就是最終的模式集成的結(jié)果.

若有新的源模式加入，只需要重新進(jìn)行1次元素聚類工作，并額外運(yùn)行1次模式集成的迭代過程將新加入的源模式集成到中介模式即可，已有的結(jié)果不會(huì)發(fā)生逆轉(zhuǎn)，所有的更新和補(bǔ)充都是增量式的，系統(tǒng)增加的額外開銷非常小，可擴(kuò)展性非常高.

3 本文模式匹配與集成算法

本節(jié)將介紹本文方法中核心的預(yù)處理模塊、模式匹配模塊和中介模式生成模塊中所涉及到的具體算法.

3.1 預(yù)處理模塊

預(yù)處理模塊負(fù)責(zé)基于速度最快的元素級(jí)別匹配器的結(jié)果來完成所有元素的聚類工作.具體的聚類算法本文選擇使用計(jì)算最小生成樹的kruskal算法：1)計(jì)算所有元素對(duì)的相似度，并對(duì)這些相似度以從大到小的順序進(jìn)行排序;2)每次選取相似度最大的元素對(duì)，若二者本來不屬于同一個(gè)聚類，則將他們聚在一起，否則跳過它們檢查下一個(gè)相似度最大的元素對(duì)，運(yùn)行算法直到目前相似度最大的元素對(duì)的相似度低于某一閾值.此聚類算法能保證不同類之間的差別盡可能的大，可以有效避免2個(gè)表達(dá)同一概念的元素被分到不同的類別.

3.2 模式匹配算法

本文方法中一共使用了5種匹配器，利用了模式信息和實(shí)例數(shù)據(jù)，并根據(jù)不同匹配器的特點(diǎn)以一定的策略結(jié)合這5種匹配器來綜合計(jì)算元素對(duì)之間的相似度.最后本文方法中還設(shè)計(jì)了基于相似度熵的交互式人工干預(yù)方案，以提高算法準(zhǔn)確率.

3.2.1 元素級(jí)別匹配器

傳統(tǒng)的元素級(jí)別匹配器主要通過元素字符串上的相似性以及語義上的相似性來表達(dá)元素之間的相似度.字符串相似度的通用算法對(duì)于中文準(zhǔn)確率很低，而語義上的相似性則依賴外部近義詞詞典.針對(duì)這樣的現(xiàn)狀，本文所設(shè)計(jì)的元素級(jí)別匹配器將利用Word2Vec工具來計(jì)算相似度.Word2Vec可用于將詞映射到K維實(shí)數(shù)向量空間，于是可通過向量之間的余弦值來表達(dá)相似度，且這種相似度在經(jīng)過某一子領(lǐng)域下大量語料的訓(xùn)練后，既可以表達(dá)字符串上的相似性，又能涵蓋語義上的相似性.此算法特點(diǎn)是在準(zhǔn)備階段完成訓(xùn)練后，計(jì)算相似度的速度很快，多數(shù)情況也能單獨(dú)使用，但準(zhǔn)確度一般.算法流程見算法1.

算法1. 元素級(jí)別匹配器.

輸入:str1,str2;

輸出:element_similarity.

①token_list1←tokenize(str1);

②token_list2←tokenize(str2);

③element_similarity←0;

④ foreachtoken1intoken_list1do

⑤ foreachtoken2intoken_list2do

⑥element_similarity+=wtvSim(token1,token2);

⑦ end foreach

⑧ end foreach

⑨element_similarity=|token_list1|×|token_list2|.

3.2.2 祖先路徑匹配器

祖先路徑匹配器屬于結(jié)構(gòu)級(jí)別匹配器的一種，其思想是關(guān)注元素的祖先元素，認(rèn)為2個(gè)元素若其祖先元素有相匹配的且距離它們?cè)浇瑒t它們之間的相似度越大.此算法特點(diǎn)是依照祖先元素的匹配關(guān)系嚴(yán)格控制子孫元素的匹配關(guān)系，能夠有效避免“置業(yè)經(jīng)理”下方的“姓名”元素與“業(yè)主”下方的“姓名”元素被錯(cuò)誤的匹配在一起的這種問題.算法流程算法2.

算法2. 祖先路徑匹配器.

輸入:a,b;

輸出:ancestor_similarity.

①c←parentOf(a);

②element_similarity←0;

③ whilec≠null do

④d←matchingNodeOf(c);

⑤ ifisAncestorOf(d,b)=true

⑥ break;

⑦ else

⑧c←parentOf(c);

⑨ end if

⑩ end while

3.2.3 樹編輯距離匹配器

樹編輯距離匹配器也屬于結(jié)構(gòu)級(jí)別匹配器的一種，其思想是關(guān)注元素的子孫元素，認(rèn)為2個(gè)元素若其子樹具有越類似的結(jié)構(gòu)，則它們之間的相似度越大.子樹結(jié)構(gòu)的相似性則通過樹的編輯距離來衡量，樹的編輯距離定義為2棵異構(gòu)樹通過插入、重命名、刪除結(jié)點(diǎn)3種操作轉(zhuǎn)換為相同結(jié)構(gòu)樹的操作代價(jià)[12]，通過動(dòng)態(tài)規(guī)劃算法求解.此算法速度較慢，但能夠通過子結(jié)構(gòu)判斷2個(gè)元素的相似性，例如“購房經(jīng)紀(jì)人”和“置業(yè)經(jīng)理”可能通過其他方式難以判斷其表達(dá)同一概念，但由于二者都有“姓名”、“電話”、“公司”等子元素，故可以通過樹的編輯距離獲得較高的相似度，缺點(diǎn)是對(duì)于無子結(jié)構(gòu)的葉結(jié)點(diǎn)不適用.

3.2.4 基于統(tǒng)計(jì)匹配器

基于統(tǒng)計(jì)匹配器是利用實(shí)例數(shù)據(jù)的一種匹配器，其考察元素所附帶實(shí)例的統(tǒng)計(jì)參數(shù).本文采用反向傳播(back propagation)神經(jīng)網(wǎng)絡(luò)算法，對(duì)輸入的每個(gè)源模式，根據(jù)實(shí)例數(shù)據(jù)計(jì)算每個(gè)葉結(jié)點(diǎn)的特征向量，構(gòu)造出訓(xùn)練集并進(jìn)行訓(xùn)練以獲得分類模型；進(jìn)行模式匹配時(shí)，將其他源模式B中某葉結(jié)點(diǎn)lb的特征向量輸入待匹配源模式A的分類模型，輸出的分類即代表lb應(yīng)該匹配的A中的葉結(jié)點(diǎn).

本文挑選了13個(gè)特征，對(duì)于數(shù)字類型的實(shí)例，特征值是對(duì)其數(shù)值的統(tǒng)計(jì)，對(duì)于實(shí)體類型(字符串)的實(shí)例，特征值是對(duì)其所占字節(jié)數(shù)的統(tǒng)計(jì).特征包括整型、浮點(diǎn)型、統(tǒng)一資源標(biāo)識(shí)符、日期、字符串和長文本這6個(gè)數(shù)據(jù)類型特征以及最大值、最小值、均值、標(biāo)準(zhǔn)差、均方差系數(shù)、字節(jié)數(shù)、精度這7個(gè)統(tǒng)計(jì)特征.

計(jì)算2個(gè)輸入的葉子元素la，lb的相似度時(shí)，將la放入lb所在的模式B的分類模型中，獲取la與lb的相似度值，再將lb放入la所在的模式A的分類模型中，獲取lb與la的相似度值，二者取平均值作為la與lb的基于統(tǒng)計(jì)相似度.

此算法利用了元素的實(shí)例數(shù)據(jù)，但對(duì)于實(shí)體類型(字符串)的實(shí)例，只考察了字符串的字節(jié)長度，沒有關(guān)注字符串的具體內(nèi)容.此算法單獨(dú)使用時(shí)匹配結(jié)果的召回率高但準(zhǔn)確率低，計(jì)算相似度時(shí)速度較快.

3.2.5 基于內(nèi)容匹配器

基于內(nèi)容匹配器也是利用實(shí)例數(shù)據(jù)的一種匹配器，其考察元素所附帶的實(shí)例的具體內(nèi)容，對(duì)于2個(gè)葉結(jié)點(diǎn)，若二者的實(shí)例數(shù)據(jù)重疊程度比較大，則認(rèn)為二者有可能代表同一個(gè)概念.本文所設(shè)計(jì)的算法首先按照數(shù)據(jù)類型對(duì)葉結(jié)點(diǎn)進(jìn)行分類：1)長文本類型，即平均長度大于30的字符串；2)實(shí)體類型，即平均長度小于等于30的字符串；3)數(shù)值類型.計(jì)算2個(gè)葉結(jié)點(diǎn)la和lb的相似度的規(guī)則為：1)若la和lb的數(shù)據(jù)類型不同，則相似度為0；2)若la和lb都是長文本類型，則將實(shí)例合并為文檔并統(tǒng)計(jì)詞表和詞頻，采用空間向量模型VSM將文檔映射為向量，以向量余弦值作為其相似度；3)對(duì)于實(shí)體類型，采用貪心算法：對(duì)la的每個(gè)實(shí)例，在lb中尋找與其編輯距離最小的實(shí)例并累加編輯距離值，最后將累加值除以la的實(shí)例數(shù)量即可評(píng)估la和lb的相似度.編輯距離利用動(dòng)態(tài)規(guī)劃求解；4)對(duì)于數(shù)值類，分別統(tǒng)計(jì)2個(gè)實(shí)例集合的標(biāo)準(zhǔn)差std1與std2、平均值avg1與avg2，則相似度為

(1)

此匹配器利用了元素的實(shí)例數(shù)據(jù)且關(guān)注字符串的具體內(nèi)容，但由于實(shí)例子集合問題的影響，算法單獨(dú)使用時(shí)匹配結(jié)果的準(zhǔn)確率高但召回率低，在算法效率上，由于需要對(duì)所有實(shí)例進(jìn)行遍歷，故計(jì)算速度較慢.

3.2.6 綜合匹配器

本文所設(shè)計(jì)的5個(gè)匹配器具有各自的特點(diǎn)，需要針對(duì)它們的特點(diǎn)進(jìn)行高效的結(jié)合，給每一對(duì)元素計(jì)算出一個(gè)綜合的相似度.

首先由于元素級(jí)別匹配器計(jì)算效率最高，且大多數(shù)情況下準(zhǔn)確率可以接受，故本文在預(yù)處理模塊使用該匹配器計(jì)算所有元素之間的相似度，預(yù)先對(duì)所有元素做1次聚類，而其他匹配器計(jì)算效率稍低，就可以基于聚類的結(jié)果來減少計(jì)算量，不需要對(duì)所有元素對(duì)都實(shí)施計(jì)算，極大地增加了整體算法的效率.

利用實(shí)例數(shù)據(jù)的2個(gè)匹配器其特點(diǎn)正好互補(bǔ)，可以先進(jìn)行1次整合.基于統(tǒng)計(jì)匹配器召回率高，準(zhǔn)確率低，計(jì)算出的相似度高時(shí)，實(shí)際上是不太可信的，而基于內(nèi)容匹配器恰好相反，其召回率低，準(zhǔn)確率高，計(jì)算出的相似度低時(shí)，實(shí)際上是不太可信的.又考慮到基于統(tǒng)計(jì)匹配器速度遠(yuǎn)快于基于內(nèi)容匹配器，故可以以基于統(tǒng)計(jì)匹配器為主，當(dāng)其計(jì)算出來的相似度較高時(shí)再去考察基于內(nèi)容匹配器的結(jié)果并作出調(diào)整，這樣的組合方式可以保證計(jì)算效率足夠高且準(zhǔn)確率得到較大提高.計(jì)算為

(2)

其中，sta_sim是基于統(tǒng)計(jì)匹配器，con_sim是基于內(nèi)容匹配器，d是0～1之間的一個(gè)經(jīng)驗(yàn)閾值.

按上述方法計(jì)算出來的基于統(tǒng)計(jì)匹配器和基于內(nèi)容匹配器所結(jié)合的相似度ins_sim稱之為實(shí)例信息相似度，接下來將結(jié)合實(shí)例信息相似度以及樹編輯距離匹配器.由于前者只對(duì)葉結(jié)點(diǎn)有效，而后者主要對(duì)中間結(jié)點(diǎn)有效，故可以做互補(bǔ)形式的結(jié)合，當(dāng)2個(gè)元素均為葉結(jié)點(diǎn)時(shí)，取實(shí)例信息相似度，否則取樹編輯距離匹配器所計(jì)算的相似度，此結(jié)合后的相似度稱之為實(shí)例及子樹相似度.

最后，對(duì)實(shí)例及子樹相似度、元素級(jí)別匹配器計(jì)算的相似度和祖先路徑匹配器計(jì)算的相似度這3個(gè)相似度值取加權(quán)平均值，即得到任意2個(gè)元素之間的綜合相似度similarity.

即便是綜合考慮了各方面信息、高效的結(jié)合了各種匹配器所計(jì)算出的綜合相似度，有時(shí)候也不足以判斷某一元素的正確的匹配對(duì)象，此時(shí)可以引入人工干預(yù)，我們認(rèn)為專家的決策一定是正確的，但人工干預(yù)的程度必須受到控制，必須以機(jī)器的自動(dòng)化算法為主.

對(duì)于待匹配的元素，其候選集合中每個(gè)候選元素都有1個(gè)與之對(duì)應(yīng)的綜合相似度，針對(duì)這些綜合相似度，人工干預(yù)的基本思路就是若這些相似度中有1個(gè)特別突出的高，則匹配對(duì)象就是綜合相似度高的那個(gè)候選元素，但若這些相似度比較接近，實(shí)際上就不能直接取綜合相似度最高的候選元素作為匹配對(duì)象.此時(shí)即可向?qū)＜覓伋鰡栴}，讓專家從這些候選元素中選出與當(dāng)前元素真正匹配的元素，然后算法繼續(xù)運(yùn)行.

本文選擇利用相似度熵來衡量候選元素的綜合相似度之間的不確定性，計(jì)算公式為

(3)

對(duì)于具有k個(gè)候選元素的情況，計(jì)算出來的相似度熵entropy(x)的值域?yàn)閇0,lnk]，引入閾值T，當(dāng)entropy(x)>T×lnk時(shí)，則向?qū)＜覓伋鰡栴}請(qǐng)求協(xié)助，否則直接選擇綜合相似度最大的候選元素來匹配.

3.3 模式集成算法

此模塊負(fù)責(zé)每一輪模式集成迭代中的集成任務(wù)，分為元素集成子模塊和沖突解決子模塊.

3.3.1 元素集成子模塊

在一次迭代過程中，需要將當(dāng)前源模式集成到當(dāng)前的中介模式上，本文算法采用深度優(yōu)先的順序來遍歷當(dāng)前源模式的所有元素，保證在處理每個(gè)元素時(shí)，其祖先元素都已經(jīng)完成匹配.具體流程如下：

算法3. 元素集成流程.

步驟1. 默認(rèn)所有源模式的根元素都直接匹配，因?yàn)檩斎氲耐串悩?gòu)模式都是同一子領(lǐng)域下的.以DFS順序，從根元素的第1個(gè)子元素開始遍歷.

步驟2. 當(dāng)前遍歷到的元素為x，在聚類結(jié)果中取出x所在類別X，|X|=1，跳至步驟7.

步驟3. 從X中取出在當(dāng)前中介模式上存在的元素，獲得x的候選集合Y，若Y=?，跳至步驟7.

步驟4. 對(duì)Y中的每個(gè)元素，調(diào)用模式匹配模塊計(jì)算其與x的綜合相似度.

步驟5. 對(duì)步驟4中得到的所有綜合相似度，計(jì)算相似度熵entropy(x)，若entropy(x)>T×ln|Y|，則向?qū)＜覓伋鰡栴}請(qǐng)求協(xié)助，若專家認(rèn)為候選集合中沒有x的真正匹配對(duì)象，跳至步驟7，否則，設(shè)專家給出x的真正候選元素為y；若entropy(x)≤T×ln|Y|，則選擇最大相似度所對(duì)應(yīng)的元素為候選元素，同樣設(shè)為y.

步驟6. 將x與y匹配，調(diào)用沖突解決子模塊解決沖突，更新中介模式，記錄匹配關(guān)系，跳至步驟8；

步驟7. 若中介模式中沒有元素與x匹配，則考察x的父元素p，設(shè)中介模式中與p匹配的元素是q，則將x作為q最右邊一個(gè)子元素加入到中介模式中，擴(kuò)充中介模式.

步驟8. 若x不是葉結(jié)點(diǎn)，則取x的第1個(gè)子元素，否則取x的下一個(gè)兄弟元素，重復(fù)步驟2.

步驟9. 若x是DFS順序的最后一個(gè)元素，則算法結(jié)束.

3.3.2 沖突解決子模塊

當(dāng)確定了當(dāng)前源模式下某一元素的匹配對(duì)象后，需要按照沖突解決策略解決可能出現(xiàn)的策略，策略如下(轉(zhuǎn)行定格)：

① 同義詞沖突.本文的解決方式為先來后到，選擇舊的標(biāo)簽作為中介模式相應(yīng)元素的標(biāo)簽，但保留新匹配元素的標(biāo)簽，記錄在該元素標(biāo)簽可替換的同義詞集合中.

Fig. 4 Nested path conflict type three圖4 嵌套路徑結(jié)構(gòu)沖突3

② 數(shù)據(jù)類型沖突.本文的解決方式為保留精度更高的數(shù)據(jù)類型(如浮點(diǎn)型)或含義更寬泛的數(shù)據(jù)類型(如字符串類型).其中會(huì)涉及到實(shí)例數(shù)據(jù)的數(shù)據(jù)類型轉(zhuǎn)換問題.

③ 元素子結(jié)構(gòu)沖突.本文的解決方式為：當(dāng)葉結(jié)點(diǎn)與具有子結(jié)構(gòu)的內(nèi)部結(jié)點(diǎn)相匹配時(shí)，無論葉結(jié)點(diǎn)來自源模式還是中介模式，都直接保留內(nèi)部結(jié)點(diǎn)的子結(jié)構(gòu).在算法3中此沖突將自然得到解決，不需要額外進(jìn)行沖突調(diào)整.

④ 嵌套路徑結(jié)構(gòu)沖突1.嵌套路徑結(jié)構(gòu)沖突是最為復(fù)雜的沖突，其來源是2個(gè)模式中已經(jīng)匹配的祖先元素和當(dāng)前匹配的子孫元素之間路徑的不一致問題.這種問題可細(xì)分為3類，其中嵌套路徑結(jié)構(gòu)沖突1產(chǎn)生于中介模式的路徑中有嵌套元素.如圖2所示，中介模式比源模式多1層“交通”元素，正確的解決方法是保留分級(jí)更多的結(jié)構(gòu)，此沖突不需要額外進(jìn)行沖突調(diào)整，按照算法3運(yùn)行可以自然地解決，生成正確的新中介模式.

Fig. 2 Nested path conflict type one圖2 嵌套路徑結(jié)構(gòu)沖突1

⑤ 嵌套路徑結(jié)構(gòu)沖突2.此沖突產(chǎn)生于源模式的路徑中有嵌套元素.如圖3所示，源模式比中介模式多1層“交通”元素，正確的解決方法應(yīng)該是保留分級(jí)更多的結(jié)構(gòu)，但若按照算法3的算法運(yùn)行，最終生成的中介模式將如圖3中新中介模式1，因?yàn)槠ヅ洹敖煌ā痹貢r(shí)沒找到匹配對(duì)象，被當(dāng)做生活配套最后一個(gè)子元素插入到中介模式中，導(dǎo)致錯(cuò)誤，需要進(jìn)行調(diào)整.但這種錯(cuò)誤馬上可以檢測(cè)出來，接下來匹配源模式的“公交”元素時(shí)，發(fā)現(xiàn)其原本父元素“交通”成為其兄弟元素，解決方法是斬?cái)嘀薪槟Ｊ街小肮弧痹嘏c其父元素“生活配套”的連線，補(bǔ)充其與源模式中父元素所匹配的“交通”元素的連線，最終形成正確的新中介模式2，沖突消除，算法可以繼續(xù)運(yùn)行.

Fig. 3 Nested path conflict type two圖3 嵌套路徑結(jié)構(gòu)沖突2

⑥ 嵌套路徑結(jié)構(gòu)沖突3.此沖突產(chǎn)生于源模式和中介模式的路徑中都有嵌套元素，但兩邊的嵌套元素在實(shí)際匹配中錯(cuò)誤的匹配失敗.如圖4所示，實(shí)際算法運(yùn)行時(shí)，由于“購房經(jīng)紀(jì)人”和“置業(yè)經(jīng)理”的字符串不相似，使得二者的相似度較低，導(dǎo)致匹配“置業(yè)經(jīng)理”時(shí)未找到匹配對(duì)象而被當(dāng)做二手房的最后一個(gè)子元素插入到中介模式中，生成了錯(cuò)誤的新中介模式1，需要進(jìn)行調(diào)整.但這種錯(cuò)誤依然馬上可以檢測(cè)出來，接下來匹配源模式的“名字”元素時(shí)，發(fā)現(xiàn)其原本父元素“置業(yè)經(jīng)理”成為其父親的兄弟元素，解決方法是撤銷之前 “置業(yè)經(jīng)理”的匹配結(jié)果，依據(jù)子元素的匹配情況將“置業(yè)經(jīng)理”與 “購房經(jīng)紀(jì)人”匹配，最終形成正確的新中介模式2，沖突消除，算法可繼續(xù)運(yùn)行.

4 實(shí)驗(yàn)評(píng)估

4.1 實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)所使用的數(shù)據(jù)集是來自二手房領(lǐng)域的多源異構(gòu)數(shù)據(jù)集，其中包含2015年1月的安居客①、我愛我家②、鏈家網(wǎng)③3個(gè)二手房交易網(wǎng)站上所發(fā)布的北京地區(qū)二手房源信息，三者的XML模式中分別包含51，50，46個(gè)元素.本文首先對(duì)這3個(gè)數(shù)據(jù)模式進(jìn)行人工的數(shù)據(jù)融合，得到標(biāo)準(zhǔn)中介模式以及元素匹配映射表，用于進(jìn)行實(shí)驗(yàn)結(jié)果的對(duì)比.數(shù)據(jù)集的基本信息見如表1所示：

Table 1 Basic Information of Data Set

4.2 實(shí)驗(yàn)方法

本文實(shí)驗(yàn)方法是對(duì)4.1節(jié)數(shù)據(jù)運(yùn)行本文整體算法，獲得最后記錄的元素匹配表，比較算法做出的匹配判斷與實(shí)際人工標(biāo)注的匹配結(jié)果之間的差別，主要評(píng)價(jià)指標(biāo)為準(zhǔn)確率precision、召回率recall和F值，其計(jì)算為

(4)

(5)

(6)

其中，TP為實(shí)際匹配且算法也判斷為匹配的元素對(duì)數(shù)量，F(xiàn)P為算法判斷為匹配而實(shí)際不匹配的元素對(duì)數(shù)量，F(xiàn)N為實(shí)際匹配但算法未能判斷為匹配的元素對(duì)數(shù)量.

由于POSCHE的相關(guān)工作也是增量迭代式進(jìn)行數(shù)據(jù)融合，與本文最為相似，因此本文的對(duì)比對(duì)象選擇POSCHE的算法，同時(shí)本文方法將分為無人工干預(yù)和有人工干預(yù)2種，前者沒有任何人工干預(yù)，算法完全自主決策.另外本文還針對(duì)人工參與的程度與算法準(zhǔn)確率的關(guān)系進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)變量為相似度熵的閾值大小.

4.3 實(shí)驗(yàn)結(jié)果

1) 人工干預(yù)效果實(shí)驗(yàn).

本文將相似度熵的閾值T分別設(shè)置為0.0，0.5，0.6，0.7，0.8，1.0進(jìn)行了6次實(shí)驗(yàn)，比對(duì)每次實(shí)驗(yàn)的人工干預(yù)的次數(shù)(即算法拋出問題的次數(shù))以及算法最終的F值評(píng)估.其中T=0.0代表全部工作都由人工完成，T=1.0則代表沒有任何人工參與.實(shí)驗(yàn)結(jié)果如圖5所示.由實(shí)驗(yàn)結(jié)果可以看出，人工干預(yù)程度越高(相似度閾值越低)，算法匹配的效果就越好，綜合考慮效果提升的程度和人工干預(yù)的程度，本文選擇T=0.7的閾值，在此閾值下，人工干預(yù)次數(shù)的絕對(duì)數(shù)量和上升幅度都很低但算法匹配效果的提升足夠明顯.

Fig. 5 Manual intervention experiment result圖5 人工干預(yù)效果實(shí)驗(yàn)結(jié)果

2) 模式匹配效果實(shí)驗(yàn).

本文針對(duì)PORSCHE的解決方案、無人工干預(yù)的本文方法(T=1.0)以及有人工干預(yù)的本文方法(T=0.7)進(jìn)行了3次實(shí)驗(yàn)，比對(duì)了3種解決方案的準(zhǔn)確率、召回率和F值.實(shí)驗(yàn)結(jié)果如圖6所示.

由實(shí)驗(yàn)結(jié)果可以看出，無論通過哪個(gè)指標(biāo)看都是有人工干預(yù)的本文方法好于無人工干預(yù)的本文方法，無人工干預(yù)的本文方法好于PORSCHE的解決方案.其中有人工干預(yù)的方法中，算法向?qū)＜覓伋隽?2個(gè)問題，只占總搜索空間(7 196對(duì)元素對(duì))的0.7%，占全人工拋出問題(420個(gè))的12.4%，而F值高達(dá)97.7%.

Fig. 6 Schema matching experiment result圖6 模式匹配效果實(shí)驗(yàn)結(jié)果

5 結(jié) 論

文本針對(duì)智慧民生領(lǐng)域中數(shù)據(jù)模式的特點(diǎn)，結(jié)合傳統(tǒng)的模式匹配技術(shù)和模式集成技術(shù)，提出并實(shí)現(xiàn)了一種“面向智慧民生領(lǐng)域?qū)哟谓Y(jié)構(gòu)數(shù)據(jù)的增量交互式模式集成方法”.該方法采用增量迭代的方式，每次集成2個(gè)模式，并將集成的結(jié)果表達(dá)為中介模式，后續(xù)集成基于前序集成的結(jié)果進(jìn)行，在源模式數(shù)量較多的情況下，大大減少了源模式間集成的次數(shù)；而在每一次集成迭代內(nèi)部，通過元素聚類等預(yù)處理工作，大大縮小元素匹配的搜索空間和比對(duì)次數(shù)，進(jìn)一步減少了工作量.在模式匹配階段，針對(duì)智慧民生領(lǐng)域數(shù)據(jù)的特點(diǎn)，綜合利用模式信息和實(shí)例數(shù)據(jù)，構(gòu)造了多種適應(yīng)于中文處理，且能力互補(bǔ)的匹配器進(jìn)行元素匹配，并通過計(jì)算相似度熵度量候選元素相似度的差異性，僅在差異性不夠明顯時(shí)才引入人工參與，較好地權(quán)衡了人工參與工作量和最終結(jié)果的準(zhǔn)確性.而中介模式生成過程則控制模式中元素遍歷的順序，并處理匹配完成之后源模式間可能出現(xiàn)的各種復(fù)雜沖突，綜合考慮了效率和中介模式的質(zhì)量.算法最終的輸出是全局統(tǒng)一的中介模式以及各源模式與中介模式元素之間的匹配映射關(guān)系.本文利用從互聯(lián)網(wǎng)爬取的二手房源信息數(shù)據(jù)設(shè)計(jì)并完成實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，本文的數(shù)據(jù)集成方案效果優(yōu)秀.

本文解決方案的局限性體現(xiàn)在，雖然人工參與可以控制到很低的程度，但完全沒有人工參與的準(zhǔn)確率還有所欠缺.本文未來工作一方面將繼續(xù)研究自動(dòng)化的模式匹配算法，力圖改善沒有人工參與時(shí)的全自動(dòng)算法的有效性；另一方面將著手進(jìn)行實(shí)體匹配方面的研究工作(entity matching)，實(shí)體匹配的任務(wù)是在利用中介模式集成各個(gè)源模式的數(shù)據(jù)時(shí)必須對(duì)不同源模式中的數(shù)據(jù)進(jìn)行識(shí)別，判斷并刪除重復(fù)數(shù)據(jù).實(shí)際上模式集成是實(shí)體匹配的基礎(chǔ)，只有當(dāng)實(shí)體匹配也完成之后才能真正實(shí)現(xiàn)數(shù)據(jù)的集成，從而形成城市范圍的完整數(shù)據(jù)集.

[1]Madhavan J, Bernstein P A, Rahm E. Generic schema matching with cupid [C]Proc of the 27th Int Conf on Very Large Data Bases. San Francisco: Morgan Kaufmann, 2001: 49-58

[2]Aumueller D, Do H H, Massmann S, et al. Schema and ontology matching with COMA++ [C]Proc of the 11th ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2005: 906-908

[3]Noy N, Natalya F, Mark A M. Anchor-PROMPT: Using non-local context for semantic matching [C]Proc of the Workshop on Ontologies and Information Sharing at the Int Joint Conf on Artificial Intelligence (IJCAI). San Francisco: Morgan Kaufmann, 2001

[4]Madria S, Passi K, Bhowmick S. An XML schema integration and query mechanism system [J]. Data & Knowledge Engineering, 2008, 65(2): 266-303

[5]Pottinger R A, Bernstein P A. Merging models based on given correspondences [C]Proc of the 29th Int Conf on Very Large Data Bases. San Francisco: Morgan Kaufmann, 2003: 862-873

[6]Shvaiko P, Euzenat J. A survey of schema-based matching approaches [G]LNCS 3730: Journal on Data Semantics IV. Berlin: Springer, 2005: 146-171

[7]Bernstein P A, Madhavan J, Rahm E. Generic schema matching, ten years later [J]. Proc of the VLDB Endowment, 2011, 4(11): 695-701

[8]Giunchiglia F, Yatskevich M. Element level semantic matching [C]Proc of the 3rd Int Semantic Web Conf (ISWC2004) Workshop on Meaning Coordination and Negotiation. Berlin: Springer, 2004

[9]Bouquet P, Serafini L, Zanobini S. Semantic coordination: A new approach and an application [C]Proc of the 2nd Int Semantic Web Conf (ISWC2003). Berlin: Springer, 2003: 130-145

[10]He B, Chang C C, Han J. Discovering complex matchings across Web query interfaces: A correlation mining approach [C]Proc of the 10th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2010: 148-157

[11]Su W, Wang J, Lochovsky F. Holistic query interface matching using parallel schema matching [C]Proc of the 22nd Int Conf on Data Engineering. Los Alamitos, CA: IEEE Computer Society, 2006: 122-131

[12]Zhang Kaizhong, Dennis S. Simple fast algorithms for the editing distance between trees and related problems [J]. Journal on Computing, 1989, 18(6): 1245-1262

[13]Dennis S, Wang J T-L, Giugno Rosalba. Algorithmics and applications of tree and graph searching [C]Proc of the 21st ACM SIGMOD-SIGACT-SIGART Symp on Principles of Database Systems. New York: ACM, 2002

[14]Liu Chen, Wang Jianwu, Han Yanbo. Mashroom+: An interactive data mashup approach with uncertainty handling [J]. Journal of Grid Computing, 2014, 12(2): 221-244

[15]Do H H, Rahm E. COMA—A system for flexible combination of schema matching approaches [C]Proc of the 28th Int Conf on Very Large Data Bases. San Francisco: Morgan Kaufmann, 2002: 610-621

[16]Li W S, Clifton C, Liu S Y. Database integration ssing neural networks: Implementation and experiences [J]. Knowledge & Information Systems, 2000, 2(1): 73-96

[17]Massmann S, Rahm E. Evaluating instance-based matching of Web directories [C]Proc of Int Workshop on the Web and Databases. New York: ACM, 2008

[18]Fan J, Lu M, Ooi B C, et al. A hybrid machine-crowdsourcing system for matching Web tables [C]Proc of the 30th IEEE Int Conf on Data Engineering. Los Alamitos, CA: IEEE Computer Society, 2014: 976-987

[19]Saleem K, Bellahsene Z, Hunt E. PORSCHE: Performance oriented schema mediation [J]. Information Systems, 2008, 33(78): 637-657

[20]Nguyen H Q, Taniar D, Rahayu J W, et al. Double-layered schema integration of heterogeneous XML sources [J]. Journal of Systems & Software, 2011, 84(1): 63-76

[21]Aboulnaga A, El Gebaly K. μBE: User guided source selection and schema mediation for internet scale data integration [C]Proc of the 23rd IEEE Int Conf on Data Engineering. Los Alamitos, CA: IEEE Computer Society, 2007: 186-195

Xia Ding, born in 1992. Master candidate of the School of Electronics Engineering and Computer Science, Peking University. His main research interest is ubiquitous computing.

Wang Yasha, born in 1975. Received his PhD degree in Northeastern University, Shenyang, China, in 2003. Professor of National Engineering & Research Center of Software Engineering in Peking University, China. His main research interests include urban data analytics, ubiquitous computing, software reuse, and online software development environment.

Zhao Zipeng, born in 1988. Received his master degree from Peking University in 2015. His main research interests include ubiquitous computing and schema matching.

Cui Da, born in 1993. Master candidate of the School of Electronics Engineering and Computer Science, Peking University. His main research interest is ubiquitous computing.

Incremental and Interactive Data Integration Approach for Hierarchical Data in Domain of Intelligent Livelihood

Xia Ding1,2, Wang Yasha1,3, Zhao Zipeng1,2, and Cui Da1,2

1(KeyLaboratoryofHighConfidenceSoftwareTechnologies(PekingUniversity),MinistryofEducation,Beijing100871)2(SchoolofElectronicsEngineeringandComputerScience,PekingUniversity,Beijing100871)3(NationalEngineering&ResearchCenterofSoftwareEngineering(PekingUniversity),Beijing100871)

Intelligent livelihood is an important domain of the smart city. In this domain, there are many application systems that have accumulated a large number of multi-source hierarchical data. In order to form an overall and unified view of the multi-source data in the whole city, variant data schemas should be integrated. Considering the distinct characteristics of the data from intelligent livelihood domain, such as lacking support for semantic matching of Chinese labels, numerous quantities of schemas, missing element labels, the existing schema integration approaches are not suitable. Under such circumstances, we propose an incremental and iterative approach which can deduce the massive computation workload due to the big number of schemas. In each iteration, both meta information and instance data are used to create more precise results, and a similarity entropy based criteria is carefully introduced to control the human intervention. Experiments are also conducted based on real data of second-hand housing in Beijing fetched from multiple second-hand Web applications. The results show that our approach can get high matching accuracy with only little human interventions.

schema matching; schema integration; data integration; smart city; intelligent livelihood

2015-12-09；

2016-05-03

國家“八六三”高技術(shù)研究發(fā)展計(jì)劃基金項(xiàng)目(2013AA01A605)；質(zhì)檢公益性行業(yè)科研專項(xiàng)(201510209) This work was supported by the National High Technology Research and Development Program of China (863 Program) (2013AA01A605), and the National Public Benefit Research Foundation (201510209).

王亞沙(wangyasha@pku.edu.cn)

TP391