weidagang2046的專欄

算法大致思路：
??????? 把要匹配的模型轉換為帶標記的有向圖（directed labeled graphs。由節點和弧組成的圖，允許對象用自身的屬性及其和其他對象的關系來定義，類似于ER圖）。這些圖要用來做迭代的不動點計算，計算結果將告訴我們一張圖里的哪些節點和第二張圖的節點相似。
??????? 為了計算相似度，我們利用了這樣一個直覺：兩個不同的節點是相似的，當它們鄰接元素是相似的。換句話說，兩個元素相似性的一部分傳播給了它們各自的鄰居，這種傳播方式類似于IP廣播，這也是SF這個名字的由來。我們把算法的結果叫做一個?mapping，然后根據匹配目標，選擇特定的過濾器來過濾出一個原始結果的子集。我們希望能夠人工對結果進行修正，需要修正的成員數目就反映了算法的準確性。

概述：

??????? 假設有2個schema，S1和S2。我們要為S1里每一個元素在S2中找到匹配的元素。
??????過程如下：
??????1. G1 = SQL2Graph(S1); G2 = SQL2Graph(S2);? 把schema變成圖，圖采用了Open Information Model (OIM)規格，圖中node采用矩形和卵形，矩形是文字描述，卵形是標識符

??????2. initialMap = StringMatch(G1, G2);??????用字符串匹配做為初始匹配，主要是比較通常的前綴和后綴，這樣的結果通常是不準確的

??????3. product = SFJoin(G1, G2, initialMap);??????用SF算法生成結果。假設兩個不同的節點是相似的，則它們鄰接元素的相似度增加。經過一系列的迭代，這種相似度會傳遍整個圖

??????4. result = SelectThreshold(product);???結果篩選


SF算法

??????圖中的每條邊，用一個三元組表示（s，p，o），分別是 源點，邊名，目的點。


??????相似度傳播圖：首先定義pairwise connectivity graph(PCG) ： ((x; y); p; (x'; y')) 屬于 PCG(A;B)<==>(x; p; x')?€ A and (y; p; y')?€ B。 關鍵是p要相同，也就是邊的名字一樣。式子從右向左推導，就可以A、B從兩個模型建立起它們的PCG。圖中的每個節點，都是A和B中的元素構成的2元組，叫做map pairs。
??????induced propagation graph。從PCG推導而來，加上了反向的邊，邊上注明了[傳播系數]，值為 1/n，n為相應的邊的數目。
??????不動點計算：
????????????設ó(x; y)?> 0 代表了節點x € A?和 y € B 的相似度，是在整個?A?X B的范圍上定義的。我們把 ó 叫做 mapping。相似度的計算就是基于ó-values的迭代計算。設 óⁱ 代表了第 i 次迭代后的結果，ó⁰ 是初始相似度（可以用字符串相似度的辦法的得出，在我們的例子里，沒有 ó⁰ ，即讓 ó⁰ =1）。
????????????每次迭代中，ó-values 都會根據其鄰居paris的 ó-values? 乘以[傳播系數] 來增加。例如，在第一次迭代 ó¹(a1; b1) = ó⁰(a1; b1) + ó⁰(a; b)?*?0.5 = 1.5。類似的，ó¹(a, b) = ó⁰(a, b) + ó⁰(a1; b1) * 1.0 + ó⁰(a2, b1) *1.0 = 3.0。接下來，所有 ó 值進行正規化，比如除以當前迭代的 ó的最大值，保證所有 ó 都不大于1。所以在正規化以后，ó¹(a; b) = 1.0, ó¹(a1, b1) = 1.5/3.0 = 0.5。一般情況下，迭代如下進行：

??????上面的計算進行迭代，直到 óⁿ 和 ó^n-1之間的差別小于一個閾值，如果計算沒有聚合，我們就在迭代超過一定次數后停止。上圖3的第三副圖，就是5次迭代后的結果。表3時一些計算方法，后面的實驗表明，C比較好。A叫做 sparce，B叫做 excepted，C叫做verbose


過濾

??????迭代出的結果是一種[多匹配]，可能包含有用的匹配子集。
??????三個步驟：
????????????1。用程序定義的[限制條件]進行過濾。
????????????2。用雙向圖中的匹配上下文技術進行過濾
????????????3。比較各種技術的有效性（滿足用戶需求的能力）
??????限制：主要有兩種，一個是[類型]限制，比如只考慮[列]的匹配（匹配雙方都是列）。第二個是 cardinality 限制，即模式S1中的所有元素都要在S2中有一個映射。

stable marriage問題：n女和n男配對，不存在這樣的兩對 (x; y)和(x0; y0)，其中x喜歡 y0 勝過 y，而且 y0 喜歡 x 勝過 x0。具有stable marriage的匹配結果的total satisfaction可能會比不具有stable marriage的匹配結果還低！

匹配質量的評估

???基本的評估思想，就是? 用戶對匹配結果做的修改越少，匹配質量就越高（修改結果包括去掉錯誤的pair，加上正確的pair）
? n是找到的匹配數，m是理想的匹配數，c是用戶作出修正的數目。

from: http://www.cnblogs.com/anf/archive/2006/08/15/477700.html