面向智慧民生領域的增量交互式數據集成方法

夏 丁 王亞沙 趙梓棚 崔 達

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

面向智慧民生領域的增量交互式數據集成方法

夏 丁1,2王亞沙1,3趙梓棚1,2崔 達1,2

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

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

模式匹配;模式集成;數據集成;智慧城市;智慧民生

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

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

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

2) 模式數量眾多，傳統集成方式效率低.智慧民生領域中需要集成的數據源眾多.以二手房領域為例，對普通大中型城市而言，包含本城市二手房數據的信息系統超過20個.傳統的兩兩模式集成方式，要求每個已知源模式或者新加入的源模式都要與其他源模式進行1次集成，這種處理方式的復雜度與源模式數量的平方成正比例，且可擴展性不好，效率太低.另外，傳統的模式集成中，部分工作會引入人工參與以解決算法難以判定的元素匹配和沖突解決問題.在模式數量大幅增加的情況下，何時選擇人工參與的標準必須嚴格控制，否則將導致大量的人工任務，從而導致方法效率降低和成本的增加.

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

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

1 模式集成技術

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

1.1 模式匹配技術

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

基于模式信息的匹配技術關注數據模式的元信息，其從匹配粒度的角度，可分為基于元素(element level)與基于結構(structure level)的技術[7].基于元素的匹配算法忽略節點之間的層次結構關系，獨立地分析挖掘單個元素對的相似性，又可細分為3類：

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

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

3) 基于詞共現關聯的匹配器.這種模式匹配技術從源模式中節點標簽的關聯規律來挖掘節點的語義相似性[10-11]，能夠同時處理大量待匹配源模式，但通用性較差.

基于結構的匹配算法關注包含目標節點及鄰近元素的子結構間的相似性，一般將輸入的源模式轉換為有向圖的形式，具體算法包括：

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

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

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

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

1.2 中介模式生成技術

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

2 本文方法結構

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

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

預處理模塊接受源模式的輸入，負責調用元素級別匹配器，計算所有源模式元素中每2個元素之間的元素級別相似度，然后基于相似度結果對所有元素進行聚類，將標簽字符串上相似或者語義上相似的元素聚為同一類，聚類的目的是降低后續計算的復雜度.

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

模式匹配模塊中，模式匹配算法使用了利用模式信息的元素級別匹配器、祖先路徑匹配器和樹編輯距離匹配器，以及利用實例信息的基于統計匹配器、基于內容匹配器，其中的一些匹配器針對中文特點進行了修正或替代，且匹配器之間的結合方式都針對每種匹配器的性能特點進行了合理且高效的設計；基于相似度熵的人工干預決策選擇模塊針對候選元素的這些綜合相似度，通過相似度熵的計算可以判斷是否需要人工干預，若需要，系統就會向專家拋出問題.匹配結果仲裁子模塊綜合各候選元素的綜合相似度以及專家的反饋結果確定待匹配元素的最終匹配對象.

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

若有新的源模式加入，只需要重新進行1次元素聚類工作，并額外運行1次模式集成的迭代過程將新加入的源模式集成到中介模式即可，已有的結果不會發生逆轉，所有的更新和補充都是增量式的，系統增加的額外開銷非常小，可擴展性非常高.

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

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

3.1 預處理模塊

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

3.2 模式匹配算法

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

3.2.1 元素級別匹配器

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

算法1. 元素級別匹配器.

輸入: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 祖先路徑匹配器

祖先路徑匹配器屬于結構級別匹配器的一種，其思想是關注元素的祖先元素，認為2個元素若其祖先元素有相匹配的且距離它們越近，則它們之間的相似度越大.此算法特點是依照祖先元素的匹配關系嚴格控制子孫元素的匹配關系，能夠有效避免“置業經理”下方的“姓名”元素與“業主”下方的“姓名”元素被錯誤的匹配在一起的這種問題.算法流程算法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 樹編輯距離匹配器

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

3.2.4 基于統計匹配器

基于統計匹配器是利用實例數據的一種匹配器，其考察元素所附帶實例的統計參數.本文采用反向傳播(back propagation)神經網絡算法，對輸入的每個源模式，根據實例數據計算每個葉結點的特征向量，構造出訓練集并進行訓練以獲得分類模型；進行模式匹配時，將其他源模式B中某葉結點lb的特征向量輸入待匹配源模式A的分類模型，輸出的分類即代表lb應該匹配的A中的葉結點.

本文挑選了13個特征，對于數字類型的實例，特征值是對其數值的統計，對于實體類型(字符串)的實例，特征值是對其所占字節數的統計.特征包括整型、浮點型、統一資源標識符、日期、字符串和長文本這6個數據類型特征以及最大值、最小值、均值、標準差、均方差系數、字節數、精度這7個統計特征.

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

此算法利用了元素的實例數據，但對于實體類型(字符串)的實例，只考察了字符串的字節長度，沒有關注字符串的具體內容.此算法單獨使用時匹配結果的召回率高但準確率低，計算相似度時速度較快.

3.2.5 基于內容匹配器

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

(1)

此匹配器利用了元素的實例數據且關注字符串的具體內容，但由于實例子集合問題的影響，算法單獨使用時匹配結果的準確率高但召回率低，在算法效率上，由于需要對所有實例進行遍歷，故計算速度較慢.

3.2.6 綜合匹配器

本文所設計的5個匹配器具有各自的特點，需要針對它們的特點進行高效的結合，給每一對元素計算出一個綜合的相似度.

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

利用實例數據的2個匹配器其特點正好互補，可以先進行1次整合.基于統計匹配器召回率高，準確率低，計算出的相似度高時，實際上是不太可信的，而基于內容匹配器恰好相反，其召回率低，準確率高，計算出的相似度低時，實際上是不太可信的.又考慮到基于統計匹配器速度遠快于基于內容匹配器，故可以以基于統計匹配器為主，當其計算出來的相似度較高時再去考察基于內容匹配器的結果并作出調整，這樣的組合方式可以保證計算效率足夠高且準確率得到較大提高.計算為

(2)

其中，sta_sim是基于統計匹配器，con_sim是基于內容匹配器，d是0～1之間的一個經驗閾值.

按上述方法計算出來的基于統計匹配器和基于內容匹配器所結合的相似度ins_sim稱之為實例信息相似度，接下來將結合實例信息相似度以及樹編輯距離匹配器.由于前者只對葉結點有效，而后者主要對中間結點有效，故可以做互補形式的結合，當2個元素均為葉結點時，取實例信息相似度，否則取樹編輯距離匹配器所計算的相似度，此結合后的相似度稱之為實例及子樹相似度.

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

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

對于待匹配的元素，其候選集合中每個候選元素都有1個與之對應的綜合相似度，針對這些綜合相似度，人工干預的基本思路就是若這些相似度中有1個特別突出的高，則匹配對象就是綜合相似度高的那個候選元素，但若這些相似度比較接近，實際上就不能直接取綜合相似度最高的候選元素作為匹配對象.此時即可向專家拋出問題，讓專家從這些候選元素中選出與當前元素真正匹配的元素，然后算法繼續運行.

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

(3)

對于具有k個候選元素的情況，計算出來的相似度熵entropy(x)的值域為[0,lnk]，引入閾值T，當entropy(x)>T×lnk時，則向專家拋出問題請求協助，否則直接選擇綜合相似度最大的候選元素來匹配.

3.3 模式集成算法

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

3.3.1 元素集成子模塊

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

算法3. 元素集成流程.

步驟1. 默認所有源模式的根元素都直接匹配，因為輸入的同源異構模式都是同一子領域下的.以DFS順序，從根元素的第1個子元素開始遍歷.

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

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

步驟4. 對Y中的每個元素，調用模式匹配模塊計算其與x的綜合相似度.

步驟5. 對步驟4中得到的所有綜合相似度，計算相似度熵entropy(x)，若entropy(x)>T×ln|Y|，則向專家拋出問題請求協助，若專家認為候選集合中沒有x的真正匹配對象，跳至步驟7，否則，設專家給出x的真正候選元素為y；若entropy(x)≤T×ln|Y|，則選擇最大相似度所對應的元素為候選元素，同樣設為y.

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

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

步驟8. 若x不是葉結點，則取x的第1個子元素，否則取x的下一個兄弟元素，重復步驟2.

步驟9. 若x是DFS順序的最后一個元素，則算法結束.

3.3.2 沖突解決子模塊

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

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

Fig. 4 Nested path conflict type three圖4 嵌套路徑結構沖突3

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

③ 元素子結構沖突.本文的解決方式為：當葉結點與具有子結構的內部結點相匹配時，無論葉結點來自源模式還是中介模式，都直接保留內部結點的子結構.在算法3中此沖突將自然得到解決，不需要額外進行沖突調整.

④ 嵌套路徑結構沖突1.嵌套路徑結構沖突是最為復雜的沖突，其來源是2個模式中已經匹配的祖先元素和當前匹配的子孫元素之間路徑的不一致問題.這種問題可細分為3類，其中嵌套路徑結構沖突1產生于中介模式的路徑中有嵌套元素.如圖2所示，中介模式比源模式多1層“交通”元素，正確的解決方法是保留分級更多的結構，此沖突不需要額外進行沖突調整，按照算法3運行可以自然地解決，生成正確的新中介模式.

Fig. 2 Nested path conflict type one圖2 嵌套路徑結構沖突1

⑤ 嵌套路徑結構沖突2.此沖突產生于源模式的路徑中有嵌套元素.如圖3所示，源模式比中介模式多1層“交通”元素，正確的解決方法應該是保留分級更多的結構，但若按照算法3的算法運行，最終生成的中介模式將如圖3中新中介模式1，因為匹配“交通”元素時沒找到匹配對象，被當做生活配套最后一個子元素插入到中介模式中，導致錯誤，需要進行調整.但這種錯誤馬上可以檢測出來，接下來匹配源模式的“公交”元素時，發現其原本父元素“交通”成為其兄弟元素，解決方法是斬斷中介模式中“公交”元素與其父元素“生活配套”的連線，補充其與源模式中父元素所匹配的“交通”元素的連線，最終形成正確的新中介模式2，沖突消除，算法可以繼續運行.

Fig. 3 Nested path conflict type two圖3 嵌套路徑結構沖突2

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

4 實驗評估

4.1 實驗數據

本文實驗所使用的數據集是來自二手房領域的多源異構數據集，其中包含2015年1月的安居客①、我愛我家②、鏈家網③3個二手房交易網站上所發布的北京地區二手房源信息，三者的XML模式中分別包含51，50，46個元素.本文首先對這3個數據模式進行人工的數據融合，得到標準中介模式以及元素匹配映射表，用于進行實驗結果的對比.數據集的基本信息見如表1所示：

Table 1 Basic Information of Data Set

4.2 實驗方法

本文實驗方法是對4.1節數據運行本文整體算法，獲得最后記錄的元素匹配表，比較算法做出的匹配判斷與實際人工標注的匹配結果之間的差別，主要評價指標為準確率precision、召回率recall和F值，其計算為

(4)

(5)

(6)

其中，TP為實際匹配且算法也判斷為匹配的元素對數量，FP為算法判斷為匹配而實際不匹配的元素對數量，FN為實際匹配但算法未能判斷為匹配的元素對數量.

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

4.3 實驗結果

1) 人工干預效果實驗.

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

Fig. 5 Manual intervention experiment result圖5 人工干預效果實驗結果

2) 模式匹配效果實驗.

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

由實驗結果可以看出，無論通過哪個指標看都是有人工干預的本文方法好于無人工干預的本文方法，無人工干預的本文方法好于PORSCHE的解決方案.其中有人工干預的方法中，算法向專家拋出了52個問題，只占總搜索空間(7 196對元素對)的0.7%，占全人工拋出問題(420個)的12.4%，而F值高達97.7%.

Fig. 6 Schema matching experiment result圖6 模式匹配效果實驗結果

5 結 論

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

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

[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

國家“八六三”高技術研究發展計劃基金項目(2013AA01A605)；質檢公益性行業科研專項(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