[發明專利]基于隱含分類信息的模式匹配方法

無效

• 申請號: 201010613046.2
• 申請日: 2010-12-29
• 公開（公告）號: CN102063489A
• 公開（公告）日: 2011-05-18
• 發明（設計）人: 王國仁;趙宇海;丁國輝
• 申請（專利權）人: 東北大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 沈陽東大專利代理有限公司 21109
• 代理人: 梁焱

技術領域

本發明屬于數據庫領域，具體涉及數據庫中關系模式之間的映射及匹配技術。特別涉及一種發現隱含分類信息提高模式匹配質量的方法。

背景技術

隨著計算機技術不斷深入各個領域，數據已呈現出分布、自制、異構等特點。數據集成、數據交換是解決多種數據源間共享問題的一個有效手段。數據集成、交換的應用領域及其廣泛，例如本體合并、數據空間、數據倉庫、電子商務、生命科學、Deep?Web等等。作為數據集成、交換的準備階段-模式匹配其主要任務是發現模式元素之間的語義相似性。如果兩個模式元素具有相似的語義則他們很可能表示相同的事物或者具有相似的意義。現有的模式匹配技術主要分為兩類。第一類技術負責發現元素間的語義相似性，主要包括Schema-Based方法和Instances-Based方法。第二類技術負責提高模式匹配質量，即通過約束等手段限定匹配的應用范圍來提高匹配的質量。Context-Based是這一類中的代表技術。

Schema-Based方法考慮模式本身的信息，即描述模式的元數據。可用的信息包括模式的名字、描述、結構、約束以及模式元素的數據類型等等。例如某個模式包含名字為“products-price”的屬性，而另一個模式包含名字為“p-price”屬性，則他們很可能具有相同的語義“產品價格”。Instances-Based方法主要利用依托于模式而存在的實例信息進行模式匹配。該類技術通過對實例的數據特性進行統計，利用統計結果作為不同模式元素間的對比依據。例如針對“student”信息表中的“age”屬性，統計該屬性的平均值作為該屬性與其他模式屬性對比的依據，如果另一個模式的某個屬性的算術平均值與“age”屬性的平均值之差在一個給定的范圍內，則有理由認為他們都表示人的年齡，即這兩個屬性的語義相似。此種技術可以利用數據的各方面數據特性進行匹配，例如均值、方差、分布等等。

Context-Based的技術對已經發現的模式匹配進行約束。該方法利用源數據實例中的顯示分類屬性(Context)約束屬性匹配。這些分類屬性使得匹配只對需要轉換的部分實例生效，而不影響不需要轉換的數據實例。該技術分為兩個階段。第一階段的主要任務是發現源模式中的分類屬性，其采用機器學習技術學習源數據實例和目標數據實例的特性，然后預測顯示分類屬性，例如“student”信息表中的“gender”屬性。第二階段的主要任務是根據發現的顯示分類屬性發現生成約束條件并將其與屬性匹配進行關聯。該方法的優點在于其有效地將顯示分類屬性與屬性匹配進行結合，并利用其作為屬性匹配的約束條件，從而使得不同模式之間的實例轉換具有選擇性，提高數據交換的質量。Context-Based技術雖然能夠利用數據實例本身的信息生成約束條件，但其同樣存在一些缺點，這些缺點表現在兩方面：

(1)在利用機器學習方法尋找顯示分類屬性時，如果源模式同時存在一些低勢(屬性的值域很小)屬性，則會降低顯示分類屬性查找的準確率。如果存在大量的低勢屬性，則很可能導致算法不能找到顯示分類屬性。低勢屬性與顯示分類屬性之間的混淆使得算法不能對其進行區分，導致查找準確率降低。

(2)第二，該技術第一步的返回結果往往是一些候選的顯示分類屬性，通過這些屬性構建候選約束條件，進一步形成候選屬性匹配，之后選擇具有最高置信度的屬性匹配，這使得目標模式具有的屬性匹配來自多個源模式，而這一現象往往不符合實際情況。同時候選空間往往很大，導致具有最高置信度的匹配搜索非常耗費時間和資源。同時該方法對顯示分類屬性的依賴性非常強，如果源模式中不具有顯示分類屬性，Context-Based技術則失效。

發明內容

為解決現有技術的不足之處，本發明提出一種基于隱含分類信息的模式匹配方法，限定了屬性匹配的應用范圍，提高數據交換的質量。相比于傳統的Context-Based技術，本方法從數據實例中尋找真正的分類信息，來進行約束條件的構建，而不依賴于顯示分類屬性。不論源模式中是否存在顯示分類屬性，本發明中的方法都能從實例數據中提取約束信息，限制屬性匹配，提高數據轉換質量。