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

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

2、名、屬性值相似性特征，本文通過機器學(xué)習(xí)方法結(jié)合屬性對互斥特征與相似性特征進行屬性匹配。并以潛在的匹配屬性對為基礎(chǔ)，引入有約束的屬性聚類方法進行Web模式匹配，聚類方法的約束條件來自屬性對共現(xiàn)特征。實驗結(jié)果表明，相對于僅使用相似性特征的方法，結(jié)合屬性分布特征的Web模式匹配算法取得了更好的結(jié)果，解決了單獨使用屬性名相似性能處理的屬性較少，而屬性值相似性需要針對特定領(lǐng)域優(yōu)化的問題。關(guān)鍵詞：屬性對互斥，屬性對共現(xiàn)，Web模式匹配，約束聚類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)組織起來，形成針對某個物品或?qū)ο蟮拿枋?，稱為Web對象 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對象的形式呈現(xiàn)，例如在筆記本電腦領(lǐng)域中，一個Web對象就是一臺筆記本電腦的描述。收集和組織這些Web對象使得許多有價值的應(yīng)用成為可能，如語義網(wǎng)、垂直搜索等。但是，Web對象繼承了互聯(lián)網(wǎng)高度分布的特點，即便是屬于同一領(lǐng)域的Web對象也分布在許多不同的網(wǎng)站中，具有不同的模式，使用不同的名字來描述相同的概念。因此，為了管理來自不同網(wǎng)站的Web對象，這些對象的數(shù)據(jù)模式必須首先被整合起來?，F(xiàn)有的Web數(shù)據(jù)模式匹配算法已經(jīng)提出了各種不同的技術(shù)來融合所有可能的線索，例如，訓(xùn)練多個分類器，然后用stacking方法結(jié)合所有分類器 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，或者用線性組合來融合多個分?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ù)有所不同，這些算法大都依賴屬性對的名字相似性和值相似性來尋找匹配的屬性對。之所以要同時使用這兩方面的相似度，是因為表達同一個概念的屬性名具有極大的可變性，如“RAM”和“Memory”都表示“內(nèi)存”這個概念，但它們在字面上不存在任何相似性。因此僅僅使用屬性名會漏過許多本該匹配的屬性對。使用屬性值相似性可以彌補這一點。但是，屬性值的可變性比屬性名更大。數(shù)

12、據(jù)源不變，屬性值也會隨著Web對象的不同而變化。除非得到足夠多的數(shù)據(jù)，否則很難發(fā)現(xiàn)重疊的屬性值?？紤]到這個問題，現(xiàn)有的算法都不僅僅依賴屬性值的字面特征，而對屬性值進行了非常深入的語義分析，例如，如果屬性值中包含詞語“kilometers”或“miles”，則這個屬性值的類型是“距離” 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。在進行這種語義分析后，兩個屬性可以在類型這個層次進行比較。這種分析顯然可以改善模式匹配的結(jié)果，但又帶來另一個問題：語義分析過程針對特定領(lǐng)域進行了過多的優(yōu)化，這使得依賴語義分析的Web數(shù)據(jù)模式匹配算法缺少推廣能力。為了解決以上問題，本文提出了一種結(jié)合屬性分布特征的Web模式匹配算法，屬性分布特征包括屬性對互斥特征和屬性對共現(xiàn)特征。具體來說，我們利用屬性對的互斥性和出現(xiàn)次數(shù)得出屬性對互斥特征，這個特征暗示了屬性對的語義相似程度，可以作為相似性特征的補充。我們通過機器學(xué)習(xí)方法將這些特征結(jié)合起來進行屬性

14、匹配，發(fā)現(xiàn)潛在的匹配屬性對。在此基礎(chǔ)上，本文將Web模式匹配問題建模成聚類問題。受到有約束聚類算法的啟發(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，我們很自然的將屬性對共現(xiàn)特征作為聚類算法的約束，通過有約束聚類算法進行屬性聚類。通過以上改進，我們的方法進一步改善了模式匹配的效果，并證明了屬性分布特征與特定領(lǐng)域無關(guān)，具有良好

16、的推廣能力。相關(guān)工作互聯(lián)網(wǎng)上存在大量的Deep Web數(shù)據(jù)，這些數(shù)據(jù)存放在數(shù)據(jù)庫或其他結(jié)構(gòu)化數(shù)據(jù)源中，但用戶無法直接訪問這些數(shù)據(jù)源，只能通過網(wǎng)站提供的界面提交查詢，得到以網(wǎng)頁形式返回的少量結(jié)果。一個領(lǐng)域的數(shù)據(jù)可能分布在許多Deep Web網(wǎng)站上，每個Deep Web網(wǎng)站的模式都有所不同，因此合并這些模式可以促進數(shù)據(jù)的利用。每個Deep Web網(wǎng)站實際上擁有兩個模式：查詢界面的模式和返回結(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)有研究都討論如何集成查詢模式，主要利用查詢界面提供的各種信息。與之相比，本文主要討論如何集成結(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通過名字和值相似度構(gòu)建多個分類器，然后利用stacking技術(shù)設(shè)計一個元分類器來綜合各個子分類器。 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通過對查詢界面的分析，提取出界面的結(jié)構(gòu)并將其表達成一棵有序樹。在此結(jié)構(gòu)基礎(chǔ)上，給定兩棵有序樹，一棵樹的葉結(jié)點可以與另一棵樹的多個相鄰葉結(jié)點或內(nèi)部節(jié)點匹配。反映到模式匹配上，就是允許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從查詢界面中提取出了更加細致的信息，除了像 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)系，還進一步識別出了各個屬性的領(lǐng)域類型、值類型、單位類型、子屬性間的關(guān)系?？偟膩砜?，這些方法對查詢界面進行了越來越深入地分析，

22、這些分析都提高了匹配的效果。但是，隨著分析的深入，它們也越來越多地依賴于對待匹配領(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è)計了一個地址識別器。 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識別出的值類型有time、mone

24、y、area、calendar month、int、real和string。在它的幾個應(yīng)用領(lǐng)域中，time、calendar month類型只出現(xiàn)在Airfare領(lǐng)域，area只出現(xiàn)在Real Estate領(lǐng)域，money幾乎只出現(xiàn)在Real Estate領(lǐng)域。因此這幾種類型都是針對少數(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的值類型和 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類似。此外， 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ǐng)域相關(guān)的，如果值中出現(xiàn)了“kil

27、ogram”，就認為這是一個與重量相關(guān)的屬性。 ADDIN EN.CITE 姜芳艽200816161617姜芳艽孟小峰賈琳琳Deep Web集成服務(wù)的不確定模式匹配計算機學(xué)報計算機學(xué)報318Deep Web 集成服務(wù) 相似度 模式匹配 不確定性2008/Periodical_jsjxb200808011.aspx北京萬方數(shù)據(jù)股份有限公司chi8指出現(xiàn)有的模式匹配算法都旨在尋找唯一的最優(yōu)匹配，而該文認為選擇唯一的最優(yōu)匹配可能會降低結(jié)果的召回率。該文提出了不確定匹配方法，對多個候選匹配進行打分并排序。但是，這種方法在計算匹配分值時同樣依賴于對屬性類型和值域的正確識別。這些優(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、探測式的利用大量數(shù)據(jù)進行模式匹配的方法，這種方法通過向Deep Web網(wǎng)站提交查詢來獲得大量數(shù)據(jù)。這篇文章同時探討了查詢模式和結(jié)果模式的匹配。盡管存在許多優(yōu)點，這種方法的缺點是需要用戶提供全局模式，同時探測式的方法降低了匹配速度。與已有的方法相比，本文的方法引入了屬性分布特征用于模式匹配，這類特征是與領(lǐng)域無關(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ā)，在這兩篇文章中，作者首次提出了屬性的分布對模式匹配的價值。盡管如此， 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完全沒有考慮到如何將屬性分布特征與傳統(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ī)則進行了有限的結(jié)合。因為忽略了傳統(tǒng)的相似性特征，這兩篇文章提出的方法只能匹配頻繁出現(xiàn)的屬性。與它們相比，本文提出了一種新的屬性分布特征，這種特征適用于成對的匹配屬性，并提出了一種將該特征與傳統(tǒng)特征結(jié)合的框架。研究目標(biāo)與整體框架Deep Web模式匹配的目標(biāo)是將所有Web模式對應(yīng)到一個統(tǒng)一的全局模式，這個模式由多個抽象概念構(gòu)成。每個網(wǎng)站的結(jié)果都通過某個局部模式表達出來，這個局部模式包含全局模式中的部分概念，但是不同的局部模式使用不同的屬性來代表同一個概念。因此，模式匹配就是要將局部模式的屬性與它表達的全局模式中的概念對應(yīng)起來。在表達全局模式的某個概念時，網(wǎng)站可以選擇兩種不同

34、的方式：1）使用一個屬性代表這個概念；2)使用多個子屬性共同來表達這個概念，例如，如果全局模式中包含概念“姓名”，在局部模式中可能將這個概念分解成“姓”和“名”這兩個子屬性。如果網(wǎng)站只使用第一種方式表達概念，那么在模式匹配時屬性間只存在一對一的匹配，否則，就要求算法能發(fā)現(xiàn)一對多的匹配。 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)過預(yù)處理后將只存在一對一的匹配。因此本文不考慮如何發(fā)現(xiàn)一對多匹配，即有如下假設(shè)：假設(shè)1局部模式僅使用0或1個屬性來表達全局模式中的概念。這個假設(shè)將在討論屬性分布特征時用到。Web對象模式(2)屬性匹配（分類）屬性對共現(xiàn)特征(3)模式匹配（有約束屬性聚類）模式匹配結(jié)果潛在匹配屬性對(1)特征提取屬性名相似度屬性值相似度屬性對互斥特征圖 SEQ 圖 * ARABIC 1 結(jié)合分布特征的模式匹配算法整體流程結(jié)合屬性分布

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

38、b集成的目標(biāo)是找到每個屬性所屬的概念。如果算法預(yù)先給定了全局模式和其中的每個概念，則模式匹配問題將是一個分類問題。但是，通常的Deep Web集成不要求預(yù)先給定全局模式，在所有屬性中將相似的屬性歸為一類，每個類就代表了一個概念。因此，模式匹配問題本質(zhì)上是一個聚類問題。我們將每個屬性作為節(jié)點，分類算法輸出的分?jǐn)?shù)作為節(jié)點之間的距離。針對聚類算法的研究 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指出引入外部知識可以提高聚類結(jié)果的質(zhì)量。外部知識包括禁止連接和必須連接，即哪些節(jié)點對禁止合并、哪些節(jié)點對必須合并。我們注意到屬性對共現(xiàn)特征可以直接判斷哪些屬性對不該匹配，因此它可以用于生成禁止連接。特征提取屬性分布與屬性匹配的關(guān)系根據(jù)假設(shè)1顯然可以導(dǎo)出如下兩個定理：定理1：出現(xiàn)在同一個局部模式中的兩個屬性不屬于同一個概念。定理2：屬于同一個概念的兩個屬性不出現(xiàn)在同一個局部模式中。以上兩個定理都包含兩個要素：兩個屬性是否出現(xiàn)在同一個局部模式中、兩個屬性是否屬于同一個概念。為了表述方便，我們引入兩個謂詞和。設(shè)、為任意兩個屬性，為真當(dāng)

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

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

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

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

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

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

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

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

49、字面相似度計算方法包括編輯距離和cos距離。在計算語義相似度時，我們引入WordNet，使用標(biāo)準(zhǔn)的WordNet語義相似度計算方法，包括最短距離 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īng)常還原出屬性的類型，從而計算屬性的類型相似度。本文也引入幾種數(shù)據(jù)類型，在進行屬性匹配時，如果兩個屬性的類型一致，則類型相似度為1，否則為0。對屬性類型進行細致的分析能極

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

54、plete link度量來計算兩個類的距離， 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一文的方法類似于single link層次式聚類方法。為了避免特定算法的影響，我們同時試驗了多種算法，包括使用single link、comp

55、lete link和average link度量的層次式聚類方法和k-means算法的變種k-medoids算法。之所以選擇k medoids算法，是因為k means算法要求待聚類的每個節(jié)點可以用向量表達且可以對這些節(jié)點求平均。針對聚類算法的研究指出引入外部知識可以提高聚類結(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。外部知識包括禁止連接和必須連接，即哪些節(jié)點對禁止合并、哪些節(jié)點對必須合并?？紤]到屬性對共現(xiàn)特征可以直接判斷一對屬性是否被禁止合并，因此它可以用于生成禁止連接。層次式聚類算法和k medoids算法都可以被改造成有約束的聚類算法。圖4給出了有約束的kmedoids算法。算法：有約束k medoids輸入：數(shù)據(jù)點、類數(shù)量k、共現(xiàn)屬性對集合輸出：數(shù)據(jù)點集合D的一個k劃分方法：初始化所有k個類對于D中的每個節(jié)點di，將它放入一個類Cj，要求1) 對于Cj中的任意節(jié)點di，(di, di)不屬于P;2）在所有滿足條件1的類中，Cj與di的距離最近。如果找不到滿足條件的Cj，返回空集。對于每個類Cj

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

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

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