結(jié)合屬性分布特征的模式匹配算法

1、結(jié)合屬性分布特征的模式匹配算法*本研究得到863高技術(shù)研究發(fā)展計(jì)劃的項(xiàng)目資助（項(xiàng)目編號(hào)：2007AA01Z438)。王宇1,2, 方濱興1, 吳博1,2,宋林海1,2,郭巖11中國(guó)科學(xué)院計(jì)算技術(shù)研究所智能信息與智能安全中心, 北京, 1001902中國(guó)科學(xué)院研究生院, 北京, 100190E-mail: HYPERLINK mailto:liaoxiangwen wangyu2005摘要：本文提出了一種結(jié)合屬性分布特征的Web模式匹配算法，屬性分布特征包括屬性對(duì)互斥特征和屬性對(duì)共現(xiàn)特征。屬性對(duì)互斥特征由屬性對(duì)的互斥性和出現(xiàn)次數(shù)計(jì)算得出，這個(gè)特征隱含了屬性對(duì)的語(yǔ)義相似程度。為了充分利用傳統(tǒng)的屬性

2、名、屬性值相似性特征，本文通過(guò)機(jī)器學(xué)習(xí)方法結(jié)合屬性對(duì)互斥特征與相似性特征進(jìn)行屬性匹配。并以潛在的匹配屬性對(duì)為基礎(chǔ)，引入有約束的屬性聚類(lèi)方法進(jìn)行Web模式匹配，聚類(lèi)方法的約束條件來(lái)自屬性對(duì)共現(xiàn)特征。實(shí)驗(yàn)結(jié)果表明，相對(duì)于僅使用相似性特征的方法，結(jié)合屬性分布特征的Web模式匹配算法取得了更好的結(jié)果，解決了單獨(dú)使用屬性名相似性能處理的屬性較少，而屬性值相似性需要針對(duì)特定領(lǐng)域優(yōu)化的問(wèn)題。關(guān)鍵詞：屬性對(duì)互斥，屬性對(duì)共現(xiàn)，Web模式匹配，約束聚類(lèi)Schema Matching Incorporating With Attribute Distribution FeaturesYu Wang1,2, Binx

3、ing Fang1, Bo Wu1,2,Linhai Song1,2 and Yan Guo11 Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190,2 Graduate School of Chinese Academy of Sciences, Beijing 100190E-mail: HYPERLINK mailto:liaoxiangwen wangyu2005Abstract: This paper presents a new Web schema matching algo

4、rithm which incorporate attribute distribution features. Attribute distribution features include the mutually exclusive feature and the co-occurring feature. By discovering mutually exclusive attribute pair and various statistics of the attribute pair, the mutually exclusive feature is calculated wh

5、ich implies the semantic similarity of the attribute pair. To utilize name similarity and value similarity based features, the attribute distribution features are combined with traditional similarity based features through machine learning techniques. After potential matched attribute pairs are disc

6、overed, this paper introduces the co-occurring feature as the constraint of clustering algorithms and solves the web schema matching problem by constrained attribute clustering algorithms. Experiments on a wide variety of domains demonstrate our method performs better than methods using only similar

7、ity based features: find more potential matched attribute pairs than using only name similarity, and does not over-optimized towards any predefined domain while value similarity based features does.Keywords: Mutually Exclusive Attributes, Co-occurring Attributes, Web Schema Matching, Constrained Clu

8、stering.引言在互聯(lián)網(wǎng)上存在很多半結(jié)構(gòu)化的信息，這些信息按照一定的結(jié)構(gòu)組織起來(lái)，形成針對(duì)某個(gè)物品或?qū)ο蟮拿枋觯Q(chēng)為Web對(duì)象 ADDIN EN.CITE Zaiqing200522247Zaiqing, NieYuanzhi, ZhangJi-Rong, WenWei-Ying, MaObject-level ranking: bringing order to Web objectsProceedings of the 14th international conference on World Wide Web2005Chiba, JapanACM/10.1145/1060745.1

9、0608281。許多領(lǐng)域的重要信息都以Web對(duì)象的形式呈現(xiàn)，例如在筆記本電腦領(lǐng)域中，一個(gè)Web對(duì)象就是一臺(tái)筆記本電腦的描述。收集和組織這些Web對(duì)象使得許多有價(jià)值的應(yīng)用成為可能，如語(yǔ)義網(wǎng)、垂直搜索等。但是，Web對(duì)象繼承了互聯(lián)網(wǎng)高度分布的特點(diǎn)，即便是屬于同一領(lǐng)域的Web對(duì)象也分布在許多不同的網(wǎng)站中，具有不同的模式，使用不同的名字來(lái)描述相同的概念。因此，為了管理來(lái)自不同網(wǎng)站的Web對(duì)象，這些對(duì)象的數(shù)據(jù)模式必須首先被整合起來(lái)?，F(xiàn)有的Web數(shù)據(jù)模式匹配算法已經(jīng)提出了各種不同的技術(shù)來(lái)融合所有可能的線索，例如，訓(xùn)練多個(gè)分類(lèi)器，然后用stacking方法結(jié)合所有分類(lèi)器 ADDIN EN.CITE AnHa

10、i200188817AnHai, DoanPedro, DomingosAlon, Y. HalevyReconciling schemas of disparate data sources: a machine-learning approachSIGMOD Rec.SIGMOD Rec.509-52030220010163-5808/10.1145/376284.3757312，或者用線性組合來(lái)融合多個(gè)分?jǐn)?shù) ADDIN EN.CITE He200466617He, HaiMeng, WeiyiYu, ClementWu, ZonghuanAutomatic integration of

11、Web search interfaces with WISE-IntegratorThe VLDB JournalThe VLDB Journal256-2731332004/10.1007/s00778-004-0126-43。盡管使用的技術(shù)有所不同，這些算法大都依賴(lài)屬性對(duì)的名字相似性和值相似性來(lái)尋找匹配的屬性對(duì)。之所以要同時(shí)使用這兩方面的相似度，是因?yàn)楸磉_(dá)同一個(gè)概念的屬性名具有極大的可變性，如“RAM”和“Memory”都表示“內(nèi)存”這個(gè)概念，但它們?cè)谧置嫔喜淮嬖谌魏蜗嗨菩?。因此僅僅使用屬性名會(huì)漏過(guò)許多本該匹配的屬性對(duì)。使用屬性值相似性可以彌補(bǔ)這一點(diǎn)。但是，屬性值的可變性比屬性名更大。數(shù)

12、據(jù)源不變，屬性值也會(huì)隨著Web對(duì)象的不同而變化。除非得到足夠多的數(shù)據(jù)，否則很難發(fā)現(xiàn)重疊的屬性值?？紤]到這個(gè)問(wèn)題，現(xiàn)有的算法都不僅僅依賴(lài)屬性值的字面特征，而對(duì)屬性值進(jìn)行了非常深入的語(yǔ)義分析，例如，如果屬性值中包含詞語(yǔ)“kilometers”或“miles”，則這個(gè)屬性值的類(lèi)型是“距離” ADDIN EN.CITE He200466617He, HaiMeng, WeiyiYu, ClementWu, ZonghuanAutomatic integration of Web search interfaces with WISE-IntegratorThe VLDB JournalThe VLDB

13、 Journal256-2731332004/10.1007/s00778-004-0126-43。在進(jìn)行這種語(yǔ)義分析后，兩個(gè)屬性可以在類(lèi)型這個(gè)層次進(jìn)行比較。這種分析顯然可以改善模式匹配的結(jié)果，但又帶來(lái)另一個(gè)問(wèn)題：語(yǔ)義分析過(guò)程針對(duì)特定領(lǐng)域進(jìn)行了過(guò)多的優(yōu)化，這使得依賴(lài)語(yǔ)義分析的Web數(shù)據(jù)模式匹配算法缺少推廣能力。為了解決以上問(wèn)題，本文提出了一種結(jié)合屬性分布特征的Web模式匹配算法，屬性分布特征包括屬性對(duì)互斥特征和屬性對(duì)共現(xiàn)特征。具體來(lái)說(shuō)，我們利用屬性對(duì)的互斥性和出現(xiàn)次數(shù)得出屬性對(duì)互斥特征，這個(gè)特征暗示了屬性對(duì)的語(yǔ)義相似程度，可以作為相似性特征的補(bǔ)充。我們通過(guò)機(jī)器學(xué)習(xí)方法將這些特征結(jié)合起來(lái)進(jìn)行屬性

14、匹配，發(fā)現(xiàn)潛在的匹配屬性對(duì)。在此基礎(chǔ)上，本文將Web模式匹配問(wèn)題建模成聚類(lèi)問(wèn)題。受到有約束聚類(lèi)算法的啟發(fā) ADDIN EN.CITE Kiri200111111147Kiri, WagstaffClaire, CardieSeth, RogersStefan, Schrdl,Constrained K-means Clustering with Background KnowledgeProceedings of the Eighteenth International Conference on Machine Learning2001Morgan Kaufmann Publishers I

15、nc.Davidson20051010105Davidson, IanRavi, S. S.Agglomerative Hierarchical Clustering with Constraints: Theoretical and Empirical ResultsKnowledge Discovery in Databases: PKDD 200559-702005/10.1007/11564126_114, 5，我們很自然的將屬性對(duì)共現(xiàn)特征作為聚類(lèi)算法的約束，通過(guò)有約束聚類(lèi)算法進(jìn)行屬性聚類(lèi)。通過(guò)以上改進(jìn)，我們的方法進(jìn)一步改善了模式匹配的效果，并證明了屬性分布特征與特定領(lǐng)域無(wú)關(guān)，具有良好

16、的推廣能力。相關(guān)工作互聯(lián)網(wǎng)上存在大量的Deep Web數(shù)據(jù)，這些數(shù)據(jù)存放在數(shù)據(jù)庫(kù)或其他結(jié)構(gòu)化數(shù)據(jù)源中，但用戶(hù)無(wú)法直接訪問(wèn)這些數(shù)據(jù)源，只能通過(guò)網(wǎng)站提供的界面提交查詢(xún)，得到以網(wǎng)頁(yè)形式返回的少量結(jié)果。一個(gè)領(lǐng)域的數(shù)據(jù)可能分布在許多Deep Web網(wǎng)站上，每個(gè)Deep Web網(wǎng)站的模式都有所不同，因此合并這些模式可以促進(jìn)數(shù)據(jù)的利用。每個(gè)Deep Web網(wǎng)站實(shí)際上擁有兩個(gè)模式：查詢(xún)界面的模式和返回結(jié)果的模式 ADDIN EN.CITE Jiying200433347Jiying, WangJi-Rong, WenFred, LochovskyWei-Ying, MaInstance-based schem

17、a matching for web databases by domain-specific query probingProceedings of the Thirtieth international conference on Very large data bases - Volume 302004Toronto, CanadaVLDB Endowment6。大部分現(xiàn)有研究都討論如何集成查詢(xún)模式，主要利用查詢(xún)界面提供的各種信息。與之相比，本文主要討論如何集成結(jié)果模式。 ADDIN EN.CITE AnHai200188817AnHai, DoanPedro, DomingosAlon

18、, Y. HalevyReconciling schemas of disparate data sources: a machine-learning approachSIGMOD Rec.SIGMOD Rec.509-52030220010163-5808/10.1145/376284.3757312通過(guò)名字和值相似度構(gòu)建多個(gè)分類(lèi)器，然后利用stacking技術(shù)設(shè)計(jì)一個(gè)元分類(lèi)器來(lái)綜合各個(gè)子分類(lèi)器。 ADDIN EN.CITE Wensheng200455547Wensheng, WuClement, YuAnHai, DoanWeiyi, MengAn interactive cluste

19、ring-based approach to integrating source query interfaces on the deep WebProceedings of the 2004 ACM SIGMOD international conference on Management of data2004Paris, FranceACM/10.1145/1007568.10075827通過(guò)對(duì)查詢(xún)界面的分析，提取出界面的結(jié)構(gòu)并將其表達(dá)成一棵有序樹(shù)。在此結(jié)構(gòu)基礎(chǔ)上，給定兩棵有序樹(shù)，一棵樹(shù)的葉結(jié)點(diǎn)可以與另一棵樹(shù)的多個(gè)相鄰葉結(jié)點(diǎn)或內(nèi)部節(jié)點(diǎn)匹配。反映到模式匹配上，就是允許1:m的匹配。 AD

20、DIN EN.CITE He200466617He, HaiMeng, WeiyiYu, ClementWu, ZonghuanAutomatic integration of Web search interfaces with WISE-IntegratorThe VLDB JournalThe VLDB Journal256-2731332004/10.1007/s00778-004-0126-43從查詢(xún)界面中提取出了更加細(xì)致的信息，除了像 ADDIN EN.CITE Wensheng200455547Wensheng, WuClement, YuAnHai, DoanWeiyi, Me

21、ngAn interactive clustering-based approach to integrating source query interfaces on the deep WebProceedings of the 2004 ACM SIGMOD international conference on Management of data2004Paris, FranceACM/10.1145/1007568.10075827一樣理解界面中各元素的嵌套關(guān)系，還進(jìn)一步識(shí)別出了各個(gè)屬性的領(lǐng)域類(lèi)型、值類(lèi)型、單位類(lèi)型、子屬性間的關(guān)系?？偟膩?lái)看，這些方法對(duì)查詢(xún)界面進(jìn)行了越來(lái)越深入地分析，

22、這些分析都提高了匹配的效果。但是，隨著分析的深入，它們也越來(lái)越多地依賴(lài)于對(duì)待匹配領(lǐng)域的了解。例如， ADDIN EN.CITE AnHai200188817AnHai, DoanPedro, DomingosAlon, Y. HalevyReconciling schemas of disparate data sources: a machine-learning approachSIGMOD Rec.SIGMOD Rec.509-52030220010163-5808/10.1145/376284.3757312主要處理房地產(chǎn)領(lǐng)域，因此它設(shè)計(jì)了一個(gè)地址識(shí)別器。 ADDIN EN.CITE

23、Wensheng200455547Wensheng, WuClement, YuAnHai, DoanWeiyi, MengAn interactive clustering-based approach to integrating source query interfaces on the deep WebProceedings of the 2004 ACM SIGMOD international conference on Management of data2004Paris, FranceACM/10.1145/1007568.10075827識(shí)別出的值類(lèi)型有time、mone

24、y、area、calendar month、int、real和string。在它的幾個(gè)應(yīng)用領(lǐng)域中，time、calendar month類(lèi)型只出現(xiàn)在Airfare領(lǐng)域，area只出現(xiàn)在Real Estate領(lǐng)域，money幾乎只出現(xiàn)在Real Estate領(lǐng)域。因此這幾種類(lèi)型都是針對(duì)少數(shù)領(lǐng)域的優(yōu)化。 ADDIN EN.CITE He200466617He, HaiMeng, WeiyiYu, ClementWu, ZonghuanAutomatic integration of Web search interfaces with WISE-IntegratorThe VLDB Journal

25、The VLDB Journal256-2731332004/10.1007/s00778-004-0126-43的值類(lèi)型和 ADDIN EN.CITE Wensheng200455547Wensheng, WuClement, YuAnHai, DoanWeiyi, MengAn interactive clustering-based approach to integrating source query interfaces on the deep WebProceedings of the 2004 ACM SIGMOD international conference on Man

26、agement of data2004Paris, FranceACM/10.1145/1007568.10075827類(lèi)似。此外， ADDIN EN.CITE He200466617He, HaiMeng, WeiyiYu, ClementWu, ZonghuanAutomatic integration of Web search interfaces with WISE-IntegratorThe VLDB JournalThe VLDB Journal256-2731332004/10.1007/s00778-004-0126-43的單位類(lèi)型識(shí)別也是與領(lǐng)域相關(guān)的，如果值中出現(xiàn)了“kil

27、ogram”，就認(rèn)為這是一個(gè)與重量相關(guān)的屬性。 ADDIN EN.CITE 姜芳艽200816161617姜芳艽孟小峰賈琳琳Deep Web集成服務(wù)的不確定模式匹配計(jì)算機(jī)學(xué)報(bào)計(jì)算機(jī)學(xué)報(bào)318Deep Web 集成服務(wù) 相似度 模式匹配 不確定性2008/Periodical_jsjxb200808011.aspx北京萬(wàn)方數(shù)據(jù)股份有限公司chi8指出現(xiàn)有的模式匹配算法都旨在尋找唯一的最優(yōu)匹配，而該文認(rèn)為選擇唯一的最優(yōu)匹配可能會(huì)降低結(jié)果的召回率。該文提出了不確定匹配方法，對(duì)多個(gè)候選匹配進(jìn)行打分并排序。但是，這種方法在計(jì)算匹配分值時(shí)同樣依賴(lài)于對(duì)屬性類(lèi)型和值域的正確識(shí)別。這些優(yōu)化導(dǎo)致許多模式匹配方法難

28、以推廣到其他領(lǐng)域。 ADDIN EN.CITE Jiying200433347Jiying, WangJi-Rong, WenFred, LochovskyWei-Ying, MaInstance-based schema matching for web databases by domain-specific query probingProceedings of the Thirtieth international conference on Very large data bases - Volume 302004Toronto, CanadaVLDB Endowment6提出了一種

29、探測(cè)式的利用大量數(shù)據(jù)進(jìn)行模式匹配的方法，這種方法通過(guò)向Deep Web網(wǎng)站提交查詢(xún)來(lái)獲得大量數(shù)據(jù)。這篇文章同時(shí)探討了查詢(xún)模式和結(jié)果模式的匹配。盡管存在許多優(yōu)點(diǎn)，這種方法的缺點(diǎn)是需要用戶(hù)提供全局模式，同時(shí)探測(cè)式的方法降低了匹配速度。與已有的方法相比，本文的方法引入了屬性分布特征用于模式匹配，這類(lèi)特征是與領(lǐng)域無(wú)關(guān)的。我們的文章受到 ADDIN EN.CITE Bin200399947Bin, HeKevin Chen-Chuan, ChangStatistical schema matching across web query interfacesProceedings of the 2003

30、ACM SIGMOD international conference on Management of data2003San Diego, CaliforniaACM/10.1145/872757.872784Bin200677717Bin, HeKevin Chen-Chuan, ChangAutomatic complex schema matching across Web query interfaces: A correlation mining approachACM Trans. Database Syst.ACM Trans. Database Syst.346-39531

31、120060362-5915/10.1145/1132863.11328729, 10的啟發(fā)，在這兩篇文章中，作者首次提出了屬性的分布對(duì)模式匹配的價(jià)值。盡管如此， ADDIN EN.CITE Bin200399947Bin, HeKevin Chen-Chuan, ChangStatistical schema matching across web query interfacesProceedings of the 2003 ACM SIGMOD international conference on Management of data2003San Diego, CaliforniaA

32、CM/10.1145/872757.8727849完全沒(méi)有考慮到如何將屬性分布特征與傳統(tǒng)的屬性名、值相似性特征結(jié)合， ADDIN EN.CITE Bin200677717Bin, HeKevin Chen-Chuan, ChangAutomatic complex schema matching across Web query interfaces: A correlation mining approachACM Trans. Database Syst.ACM Trans. Database Syst.346-39531120060362-5915/10.1145/1132863.113

33、287210也只利用規(guī)則進(jìn)行了有限的結(jié)合。因?yàn)楹雎粤藗鹘y(tǒng)的相似性特征，這兩篇文章提出的方法只能匹配頻繁出現(xiàn)的屬性。與它們相比，本文提出了一種新的屬性分布特征，這種特征適用于成對(duì)的匹配屬性，并提出了一種將該特征與傳統(tǒng)特征結(jié)合的框架。研究目標(biāo)與整體框架Deep Web模式匹配的目標(biāo)是將所有Web模式對(duì)應(yīng)到一個(gè)統(tǒng)一的全局模式，這個(gè)模式由多個(gè)抽象概念構(gòu)成。每個(gè)網(wǎng)站的結(jié)果都通過(guò)某個(gè)局部模式表達(dá)出來(lái)，這個(gè)局部模式包含全局模式中的部分概念，但是不同的局部模式使用不同的屬性來(lái)代表同一個(gè)概念。因此，模式匹配就是要將局部模式的屬性與它表達(dá)的全局模式中的概念對(duì)應(yīng)起來(lái)。在表達(dá)全局模式的某個(gè)概念時(shí)，網(wǎng)站可以選擇兩種不同

34、的方式：1）使用一個(gè)屬性代表這個(gè)概念；2)使用多個(gè)子屬性共同來(lái)表達(dá)這個(gè)概念，例如，如果全局模式中包含概念“姓名”，在局部模式中可能將這個(gè)概念分解成“姓”和“名”這兩個(gè)子屬性。如果網(wǎng)站只使用第一種方式表達(dá)概念，那么在模式匹配時(shí)屬性間只存在一對(duì)一的匹配，否則，就要求算法能發(fā)現(xiàn)一對(duì)多的匹配。 ADDIN EN.CITE Bin200677717Bin, HeKevin Chen-Chuan, ChangAutomatic complex schema matching across Web query interfaces: A correlation mining approachACM Tran

35、s. Database Syst.ACM Trans. Database Syst.346-39531120060362-5915/10.1145/1132863.1132872Wensheng200455547Wensheng, WuClement, YuAnHai, DoanWeiyi, MengAn interactive clustering-based approach to integrating source query interfaces on the deep WebProceedings of the 2004 ACM SIGMOD international confe

36、rence on Management of data2004Paris, FranceACM/10.1145/1007568.10075827, 10提出了發(fā)現(xiàn)并合并子屬性的方法，經(jīng)過(guò)預(yù)處理后將只存在一對(duì)一的匹配。因此本文不考慮如何發(fā)現(xiàn)一對(duì)多匹配，即有如下假設(shè)：假設(shè)1局部模式僅使用0或1個(gè)屬性來(lái)表達(dá)全局模式中的概念。這個(gè)假設(shè)將在討論屬性分布特征時(shí)用到。Web對(duì)象模式(2)屬性匹配（分類(lèi)）屬性對(duì)共現(xiàn)特征(3)模式匹配（有約束屬性聚類(lèi)）模式匹配結(jié)果潛在匹配屬性對(duì)(1)特征提取屬性名相似度屬性值相似度屬性對(duì)互斥特征圖 SEQ 圖 * ARABIC 1 結(jié)合分布特征的模式匹配算法整體流程結(jié)合屬性分布

37、特征的模式匹配算法的整體流程如 REF _Ref236673405 h 圖 1所示。整個(gè)算法的輸入是來(lái)自Web對(duì)象的模式：1）特征提取。模式可以定義為屬性的集合。給定任意一對(duì)屬性，特征提取模塊提取這對(duì)屬性的屬性名相似度、屬性值相似度、屬性對(duì)互斥特征和屬性對(duì)共現(xiàn)特征。2）屬性匹配。單獨(dú)使用屬性名相似度、屬性值相似度和屬性對(duì)互斥特征都不足以判斷兩個(gè)屬性是否應(yīng)該匹配。為了將它們結(jié)合起來(lái)，本文將屬性匹配問(wèn)題視為分類(lèi)問(wèn)題，利用分類(lèi)學(xué)習(xí)算法融合屬性對(duì)的各種特征，分類(lèi)算法的輸出是-1或+1。此外，分類(lèi)算法還會(huì)輸出一個(gè)分?jǐn)?shù)，表示這個(gè)屬性對(duì)匹配的程度。3）最后，算法利用有約束聚類(lèi)方法進(jìn)行模式匹配。Deep We

38、b集成的目標(biāo)是找到每個(gè)屬性所屬的概念。如果算法預(yù)先給定了全局模式和其中的每個(gè)概念，則模式匹配問(wèn)題將是一個(gè)分類(lèi)問(wèn)題。但是，通常的Deep Web集成不要求預(yù)先給定全局模式，在所有屬性中將相似的屬性歸為一類(lèi)，每個(gè)類(lèi)就代表了一個(gè)概念。因此，模式匹配問(wèn)題本質(zhì)上是一個(gè)聚類(lèi)問(wèn)題。我們將每個(gè)屬性作為節(jié)點(diǎn)，分類(lèi)算法輸出的分?jǐn)?shù)作為節(jié)點(diǎn)之間的距離。針對(duì)聚類(lèi)算法的研究 ADDIN EN.CITE Kiri200111111147Kiri, WagstaffClaire, CardieSeth, RogersStefan, Schrdl,Constrained K-means Clustering with Back

39、ground KnowledgeProceedings of the Eighteenth International Conference on Machine Learning2001Morgan Kaufmann Publishers Inc.Davidson20051010105Davidson, IanRavi, S. S.Agglomerative Hierarchical Clustering with Constraints: Theoretical and Empirical ResultsKnowledge Discovery in Databases: PKDD 2005

40、59-702005/10.1007/11564126_114, 5指出引入外部知識(shí)可以提高聚類(lèi)結(jié)果的質(zhì)量。外部知識(shí)包括禁止連接和必須連接，即哪些節(jié)點(diǎn)對(duì)禁止合并、哪些節(jié)點(diǎn)對(duì)必須合并。我們注意到屬性對(duì)共現(xiàn)特征可以直接判斷哪些屬性對(duì)不該匹配，因此它可以用于生成禁止連接。特征提取屬性分布與屬性匹配的關(guān)系根據(jù)假設(shè)1顯然可以導(dǎo)出如下兩個(gè)定理：定理1：出現(xiàn)在同一個(gè)局部模式中的兩個(gè)屬性不屬于同一個(gè)概念。定理2：屬于同一個(gè)概念的兩個(gè)屬性不出現(xiàn)在同一個(gè)局部模式中。以上兩個(gè)定理都包含兩個(gè)要素：兩個(gè)屬性是否出現(xiàn)在同一個(gè)局部模式中、兩個(gè)屬性是否屬于同一個(gè)概念。為了表述方便，我們引入兩個(gè)謂詞和。設(shè)、為任意兩個(gè)屬性，為真當(dāng)

41、且僅當(dāng)存在一個(gè)局部模式S，屬于S且屬于S。使為真的屬性對(duì)、稱(chēng)為共現(xiàn)屬性對(duì)，否則稱(chēng)為互斥屬性對(duì)。為真當(dāng)且僅當(dāng)存在一個(gè)概念C，屬于C且屬于C。使為真的屬性對(duì)、稱(chēng)為匹配屬性對(duì)。根據(jù)這些定義，定理1和定理2可以重寫(xiě)為：定理1：對(duì)于任意屬性對(duì)、，如果為真，則為假。定理2：對(duì)于任意屬性對(duì)、，如果為真，則為假。屬性對(duì)共現(xiàn)特征定理1說(shuō)明共現(xiàn)屬性對(duì)必然不匹配。因此，屬性對(duì)共現(xiàn)與否可以作為屬性匹配的一個(gè)特征，即屬性對(duì)共現(xiàn)特征。屬性對(duì)共現(xiàn)特征: 對(duì)于任意屬性對(duì)、，當(dāng)為真時(shí)，屬性對(duì)共現(xiàn)特征為1，否則，屬性對(duì)共現(xiàn)特征為0。屬性對(duì)互斥特征定理2說(shuō)明匹配屬性對(duì)一定是互斥屬性對(duì)，但反之并不成立。如果、形成互斥屬性對(duì)，這可以解

42、釋成、是匹配屬性對(duì)。但、之間也可能不存在任何語(yǔ)義關(guān)系，它們僅僅是因?yàn)榍珊隙纬苫コ鈱傩詫?duì)。我們使用隨機(jī)變量M的值來(lái)表達(dá)這兩種假設(shè)，當(dāng)和是匹配屬性對(duì)時(shí)，M為1，否則M為0。在給定數(shù)據(jù)的情況下，、形成匹配屬性對(duì)的概率是，我們將這個(gè)概率定義為屬性對(duì)互斥特征。屬性對(duì)互斥特征：對(duì)于任意屬性對(duì)、，當(dāng)為真時(shí)，屬性對(duì)互斥特征為0。否則，屬性對(duì)互斥特征為。根據(jù)定理2，。而當(dāng)M=0時(shí)，需要計(jì)算。設(shè)和屬性屬于兩個(gè)不同的概念，屬性出現(xiàn)在個(gè)模式中，屬性出現(xiàn)在個(gè)模式中，共有n個(gè)局部模式，那么， 等價(jià)于隨機(jī)將個(gè)和個(gè)分配到n個(gè)局部模式中，它們形成互斥屬性的概率，顯然，有如下公式： ( seq eq 1)為了計(jì)算，還需要知道假

43、設(shè)的先驗(yàn)概率，這個(gè)概率的值可以通過(guò)輸入數(shù)據(jù)來(lái)估算。設(shè)全局模式中有c個(gè)概念，所有n個(gè)局部模式中共有m個(gè)屬性。如果屬性平均分配在各個(gè)概念中，則每個(gè)概念有k=m/c個(gè)不同的屬性。這時(shí)，任選兩個(gè)屬性它們屬于同一個(gè)概念的概率是： ( seq eq 2)其中，m是屬性的總數(shù)量，可以直接從數(shù)據(jù)中算出來(lái)。c的值無(wú)法直接得到，但可以根據(jù)局部模式中包含的屬性數(shù)目來(lái)估算。假設(shè)在所有局部模式中最大模式包含的屬性數(shù)量為c，c可以作為c的一個(gè)近似估計(jì)。當(dāng)然，在實(shí)際的數(shù)據(jù)中屬性并不是平均分配的，有些概念較為常見(jiàn)，因此包含較多屬性，而其他概念只包含很少幾個(gè)屬性。例如在筆記本電腦領(lǐng)域中，幾乎每個(gè)局部模式都包含“CPU”這個(gè)概念

44、，但只有少數(shù)幾個(gè)模式包含“鍵盤(pán)”這個(gè)概念。因此，假設(shè)“屬性平均分配在各個(gè)概念上”是不合理的，通常。如下定理給出了的范圍。定理3：對(duì)于屬性的任意分布，有證明：當(dāng)所有屬性都屬于一個(gè)概念時(shí)，顯然，所以有。假設(shè)各個(gè)概念包含的屬性數(shù)量分別為、。則匹配屬性對(duì)的數(shù)量是： 約束是利用拉格朗日算子法可以證明，當(dāng)時(shí)，取得最小值。這時(shí)，。得證。由定理3可知，是的下界，而1是的上界。在實(shí)際數(shù)據(jù)中，相對(duì)于1而言，是的一個(gè)更好估計(jì)，因此我們用代替。最終，匯總整個(gè)計(jì)算過(guò)程，可以根據(jù)貝葉斯公式計(jì)算： ( seq eq 3)屬性對(duì)互斥特征分析屬性對(duì)互斥特征僅適合于匹配出現(xiàn)頻率較高的屬性對(duì)。在本節(jié)中，我們用圖表說(shuō)明了屬性對(duì)互斥特

45、征的這種性質(zhì)。首先，我們用圖形來(lái)表示屬性對(duì)互斥特征與屬性對(duì)的關(guān)系。除了屬性對(duì)的出現(xiàn)次數(shù)，屬性對(duì)互斥特征的值還與全局模式中概念的數(shù)目c、局部模式的數(shù)目n和總屬性個(gè)數(shù)m有關(guān)。我們根據(jù)真實(shí)數(shù)據(jù)集來(lái)設(shè)置這些參數(shù)，在視頻分享領(lǐng)域中，概念數(shù)目c=8，局部模式數(shù)目n=50，屬性總數(shù)m=182。數(shù)據(jù)的具體情況見(jiàn)節(jié) REF _Ref236749039 r h 6.1。 REF _Ref236762282 h 圖 2展示了屬性對(duì)互斥特征分別取0.5到0.9時(shí)的等高線。顯然，隨著屬性對(duì)出現(xiàn)次數(shù)的增加，屬性對(duì)互斥特征不斷增大。當(dāng)兩個(gè)屬性分別出現(xiàn)15和10次時(shí)，屬性對(duì)互斥特征的值約為0.9，即這兩個(gè)屬性匹配的概率約為0

46、.9。這符合我們的直觀感受，當(dāng)一對(duì)屬性頻繁出現(xiàn)時(shí)，它們很難僅僅因?yàn)榍珊隙纬苫コ鈱傩詫?duì)。因此，如果一個(gè)概念有多種流行的表達(dá)方式，這些表達(dá)方式的出現(xiàn)次數(shù)大體相當(dāng)，則屬性對(duì)互斥特征能夠成功的匹配它們。例如，“內(nèi)存”這個(gè)概念經(jīng)常使用“RAM”和“Memory”這兩個(gè)屬性來(lái)表達(dá)，屬性對(duì)互斥特征能夠發(fā)現(xiàn)它們之間的匹配關(guān)系，即使它們的名稱(chēng)沒(méi)有任何相似之處。這充分說(shuō)明了屬性對(duì)互斥特征的價(jià)值。圖 SEQ 圖 * ARABIC 2屬性對(duì)互斥特征與屬性出現(xiàn)次數(shù)的關(guān)系圖 SEQ 圖 * ARABIC 3固定一個(gè)屬性的出現(xiàn)次數(shù)，屬性對(duì)互斥特征與另一屬性出現(xiàn)次數(shù)的關(guān)系與此同時(shí)，我們也注意到，當(dāng)屬性出現(xiàn)次數(shù)降低時(shí)，屬性對(duì)

47、互斥特征的值可能隨之大幅降低。如 REF _Ref236762291 h 圖 3所示。我們固定一個(gè)屬性的出現(xiàn)次數(shù)，變換另一個(gè)屬性的出現(xiàn)次數(shù)，觀察屬性對(duì)互斥特征的變化情況。當(dāng)一個(gè)屬性的出現(xiàn)次數(shù)固定為10時(shí)，屬性對(duì)互斥特征隨著另一個(gè)屬性的出現(xiàn)次數(shù)的增長(zhǎng)而迅速增長(zhǎng)，而后逐漸穩(wěn)定。在增長(zhǎng)階段，當(dāng)另一個(gè)屬性出現(xiàn)15次時(shí)，屬性對(duì)互斥特征約為0.9，而當(dāng)另一個(gè)屬性出現(xiàn)10次時(shí)，屬性對(duì)互斥特征只有不足0.6。而在穩(wěn)定階段，屬性出現(xiàn)次數(shù)變化為20時(shí)，屬性對(duì)互斥特征僅從0.9變?yōu)闉?.97。由此可見(jiàn)，在增長(zhǎng)階段屬性次數(shù)的微小變動(dòng)會(huì)極大的影響屬性對(duì)互斥特征。因此，屬性對(duì)互斥特征僅對(duì)那些出現(xiàn)次數(shù)較多的屬性有價(jià)值。從另

48、一條曲線中也可以得出同樣的結(jié)論。當(dāng)一個(gè)屬性的出現(xiàn)次數(shù)固定為3時(shí)，另一個(gè)屬性的出現(xiàn)次數(shù)必須達(dá)到35，屬性對(duì)互斥特征才能達(dá)到0.9。相似性特征無(wú)論是傳統(tǒng)的模式匹配還是Deep Web模式集成都廣泛使用了屬性名和屬性值的相似性。這些特征背后的基本假設(shè)是：屬性名或?qū)傩灾迪嗨频膶傩詫?duì)可能屬于同一個(gè)概念。本文的實(shí)驗(yàn)部分也證明了屬性名與屬性值的相似性對(duì)于模式匹配是非常重要的。因此，本文也引入部分相似性特征。為了減少干擾，所有屬性的屬性名和屬性值都要首先經(jīng)過(guò)預(yù)處理。預(yù)處理過(guò)程包括大小寫(xiě)的正規(guī)化、去除不必要的標(biāo)點(diǎn)符號(hào)、基于空白字符分詞、去除停用詞等。和過(guò)去的工作一樣，我們也引入了字面和語(yǔ)義這兩類(lèi)相似度計(jì)算方法。

49、字面相似度計(jì)算方法包括編輯距離和cos距離。在計(jì)算語(yǔ)義相似度時(shí)，我們引入WordNet，使用標(biāo)準(zhǔn)的WordNet語(yǔ)義相似度計(jì)算方法，包括最短距離 ADDIN EN.CITE Rada198913131317Rada, R.Mili, H.Bicknell, E.Blettner, M.Development and application of a metric on semantic netsSystems, Man and Cybernetics, IEEE Transactions onSystems, Man and Cybernetics, IEEE Transactions on1

50、7-30191directed graphsgrammarsknowledge based systemsknowledge engineeringcause'average minimum path lengthconceptual distancehierarchical knowledge basehierarchical relationsmetricnodespairwise combinationspower setsemantic netsspreading activation19890018-947211和信息內(nèi)容 ADDIN EN.CITE Resnik19951

51、5151510Philip ResnikUsing Information Content to Evaluate Semantic Similarity in a TaxonomyProceedings of the 14th International Joint Conference on Artificial Intelligence448-453199512方法。除了直接根據(jù)屬性名和屬性值進(jìn)行相似度計(jì)算，過(guò)去的方法也經(jīng)常還原出屬性的類(lèi)型，從而計(jì)算屬性的類(lèi)型相似度。本文也引入幾種數(shù)據(jù)類(lèi)型，在進(jìn)行屬性匹配時(shí)，如果兩個(gè)屬性的類(lèi)型一致，則類(lèi)型相似度為1，否則為0。對(duì)屬性類(lèi)型進(jìn)行細(xì)致的分析能極

52、大地提高類(lèi)型相似度特征的價(jià)值，但是這些分析常常是與領(lǐng)域相關(guān)的。比如在筆記本電腦領(lǐng)域，根據(jù)詞語(yǔ)“GB”、“MB”、“KB”分析出屬性的類(lèi)型是“存儲(chǔ)空間”。為了避免針對(duì)領(lǐng)域的優(yōu)化，本文僅僅引入最常見(jiàn)的幾種類(lèi)型：日期、整數(shù)、實(shí)數(shù)和普通文本。有約束屬性聚類(lèi)同時(shí)匹配多個(gè)模式，這本質(zhì)上是屬性聚類(lèi)問(wèn)題。具體來(lái)說(shuō)，在模式匹配的過(guò)程中，需要聚類(lèi)的節(jié)點(diǎn)是局部模式中的屬性，節(jié)點(diǎn)間的距離是分類(lèi)算法輸出的分?jǐn)?shù)，這個(gè)分?jǐn)?shù)衡量?jī)蓚€(gè)屬性屬于同一個(gè)類(lèi)的可能性。常見(jiàn)的聚類(lèi)方法有層次式聚類(lèi)方法和以k-means為代表的平面聚類(lèi)方法。就我們所知，目前尚沒(méi)有相關(guān)的研究顯示何種聚類(lèi)方法最適用于模式匹配問(wèn)題， ADDIN EN.CITE

53、Wensheng200455547Wensheng, WuClement, YuAnHai, DoanWeiyi, MengAn interactive clustering-based approach to integrating source query interfaces on the deep WebProceedings of the 2004 ACM SIGMOD international conference on Management of data2004Paris, FranceACM/10.1145/1007568.10075827使用了層次式聚類(lèi)方法，并使用com

54、plete link度量來(lái)計(jì)算兩個(gè)類(lèi)的距離， ADDIN EN.CITE He200466617He, HaiMeng, WeiyiYu, ClementWu, ZonghuanAutomatic integration of Web search interfaces with WISE-IntegratorThe VLDB JournalThe VLDB Journal256-2731332004/10.1007/s00778-004-0126-43一文的方法類(lèi)似于single link層次式聚類(lèi)方法。為了避免特定算法的影響，我們同時(shí)試驗(yàn)了多種算法，包括使用single link、comp

55、lete link和average link度量的層次式聚類(lèi)方法和k-means算法的變種k-medoids算法。之所以選擇k medoids算法，是因?yàn)閗 means算法要求待聚類(lèi)的每個(gè)節(jié)點(diǎn)可以用向量表達(dá)且可以對(duì)這些節(jié)點(diǎn)求平均。針對(duì)聚類(lèi)算法的研究指出引入外部知識(shí)可以提高聚類(lèi)結(jié)果的質(zhì)量 ADDIN EN.CITE Kiri200111111147Kiri, WagstaffClaire, CardieSeth, RogersStefan, Schrdl,Constrained K-means Clustering with Background KnowledgeProceedings of

56、the Eighteenth International Conference on Machine Learning2001Morgan Kaufmann Publishers Inc.Davidson20051010105Davidson, IanRavi, S. S.Agglomerative Hierarchical Clustering with Constraints: Theoretical and Empirical ResultsKnowledge Discovery in Databases: PKDD 200559-702005/10.1007/11564126_114,

57、 5。外部知識(shí)包括禁止連接和必須連接，即哪些節(jié)點(diǎn)對(duì)禁止合并、哪些節(jié)點(diǎn)對(duì)必須合并。考慮到屬性對(duì)共現(xiàn)特征可以直接判斷一對(duì)屬性是否被禁止合并，因此它可以用于生成禁止連接。層次式聚類(lèi)算法和k medoids算法都可以被改造成有約束的聚類(lèi)算法。圖4給出了有約束的kmedoids算法。算法：有約束k medoids輸入：數(shù)據(jù)點(diǎn)、類(lèi)數(shù)量k、共現(xiàn)屬性對(duì)集合輸出：數(shù)據(jù)點(diǎn)集合D的一個(gè)k劃分方法：初始化所有k個(gè)類(lèi)對(duì)于D中的每個(gè)節(jié)點(diǎn)di，將它放入一個(gè)類(lèi)Cj，要求1) 對(duì)于Cj中的任意節(jié)點(diǎn)di，(di, di)不屬于P;2）在所有滿足條件1的類(lèi)中，Cj與di的距離最近。如果找不到滿足條件的Cj，返回空集。對(duì)于每個(gè)類(lèi)Cj

58、，重新尋找中心點(diǎn)。這個(gè)中心點(diǎn)到類(lèi)中所有其他點(diǎn)的距離之和最小。重復(fù)2、3兩步直到收斂。返回所有類(lèi)圖 SEQ 圖 * ARABIC 4 有約束k medoids實(shí)驗(yàn)數(shù)據(jù)集實(shí)驗(yàn)數(shù)據(jù)集包含來(lái)自150個(gè)網(wǎng)站的網(wǎng)頁(yè)，這些網(wǎng)站分屬于三個(gè)不同的領(lǐng)域，包括書(shū)籍、筆記本電腦和視頻分享領(lǐng)域。每個(gè)領(lǐng)域有50個(gè)網(wǎng)站。為了避免任何人為的傾向，在選擇網(wǎng)站時(shí)我們直接依賴(lài)現(xiàn)有的互聯(lián)網(wǎng)分類(lèi)目錄Yahoo Directory。三個(gè)領(lǐng)域的網(wǎng)站分別來(lái)自于Yahoo Directory的 “Books-Bookstores”、“Computer Retailers Notebooks”和“Internet Broadcasts Vide

59、o Sharing”分類(lèi)的前50個(gè)可訪問(wèn)的網(wǎng)站。在采集網(wǎng)頁(yè)后，我們手工從頁(yè)面中抽取出Web對(duì)象和相應(yīng)的屬性。為了評(píng)價(jià)模式匹配結(jié)果的好壞，我們預(yù)先對(duì)每個(gè)領(lǐng)域的所有模式進(jìn)行了人工匹配，人工匹配的結(jié)果將作為后期評(píng)價(jià)的標(biāo)準(zhǔn)。經(jīng)過(guò)人工匹配后，我們實(shí)際上得到了各個(gè)領(lǐng)域的全局模式。其中書(shū)籍領(lǐng)域的全局模式包含26個(gè)概念，筆記本電腦領(lǐng)域包含16個(gè)概念，視頻分享領(lǐng)域包含8個(gè)概念。實(shí)驗(yàn)與評(píng)價(jià)方法在結(jié)合分布特征的模式匹配算法中，分類(lèi)器所用的訓(xùn)練集、有約束屬性聚類(lèi)算法和測(cè)試集都會(huì)影響模式匹配的結(jié)果，因此，我們對(duì)于這三個(gè)要素的每一種組合都進(jìn)行了一次實(shí)驗(yàn)，即我們依次使用每個(gè)領(lǐng)域作為訓(xùn)練集和測(cè)試集，依次使用每一種有約束聚類(lèi)算

60、法，類(lèi)的個(gè)數(shù)設(shè)置為測(cè)試集所屬領(lǐng)域的概念數(shù)量，共進(jìn)行了36組實(shí)驗(yàn)。為了進(jìn)行算法的比較和評(píng)價(jià)，除了同時(shí)使用所有特征外，我們還設(shè)計(jì)了其他三組特征組合作為對(duì)比：僅僅使用相似性特征、僅僅使用屬性對(duì)互斥特征、同時(shí)使用相似性特征和屬性對(duì)互斥特征。使用這三種不同特征組合的模式匹配算法可以作為基準(zhǔn)算法與我們的算法進(jìn)行比較。同樣，基于每種特征組合我們也進(jìn)行了36組實(shí)驗(yàn)。模式匹配的結(jié)果是由聚類(lèi)算法生成，因此，結(jié)果的評(píng)價(jià)方式使用聚類(lèi)算法的標(biāo)準(zhǔn)評(píng)價(jià)方式，即成對(duì)準(zhǔn)確率(pairwise prec)、召回率(pairwise recall)和F值。算法的屬性匹配步驟使用的分類(lèi)器是SVM-perf ADDIN EN.CITE