0

次の 2 つのテーブルを用意します。

TableA
ID  Opt1    Opt2    Type
1   A       Z       10
2   B       Y       20
3   C       Z       30
4   C       K       40

と

TableB
ID  Opt1    Type
1   Z       57
2   Z       99
3   X       3000
4   Z       3000

これら 2 つのテーブル間の任意の関係を見つけるための良いアルゴリズムは何でしょうか? Op1 = Cこの例では、TableA と TableB に含まれるレコード間の明らかな関係を見つけたいと考えていますType = 3000。

アプリオリに考えることができますが、あまり実用的ではないようです。あなたたちは何を言いますか？

ありがとう。

4

2 に答える 2

1

リレーショナル データ マイニングの問題のように思えます。Ross Quinlan の FOIL を試すことをお勧めします: http://www.rulequest.com/Personal/

于 2011-11-04T12:50:21.633 に答える
1

疑似コードでは、素朴な実装は次のようになります。

  1. for each column c1 in table1
  2.    for each column c2 in table2
  3.      if approximately_isomorphic(c1, c2) then
  4.         emit (c1, c2)

  approximately_isomorphic(c1, c2)
  1. hmap = hash()
  2. for i = 1 to min(|c1|, |c2|) do
  3.    hmap[c1[i]] = c2[i]
  4. if |hmap| - unique_count(c1) < error_margin then return true
  5. else then return false

アイデアは次のとおりです。各列の要素を他の列とペアごとに比較します。列のペアごとに、2 つの列の対応する要素をリンクするハッシュ マップを作成します。ハッシュ マップに、最初の列の一意の要素と同じ数のリンクが含まれている場合、完全な同形性があります。さらにいくつかある場合は、ほぼ同形です。最初の列の要素の数まで、さらに多くの要素がある場合は、おそらく相関関係を表していないものがあります。

入力の例:

  ID & anything  : perfect isomorphism since all of ID are unique

  Opt1 & ID      : 4 mappings and 3 unique values; not a perfect
                  isomorphism, but not too far away.
  Opt1 & Opt1    : ditto above
  Opt1 & Type    : 3 mappings & 3 unique values, perfect isomorphism

  Opt2 & ID      : 4 mappings & 3 unique values, not a perfect
                  isomorphism, but not too far away
  Opt2 & Opt2    : ditto above
  Opt2 & Type    : ditto above

  Type & anything: perfect isomorphism since all of ID are unique

最良の結果を得るには、この手順を両方の方法 (つまり、table1 と table2 を比較してから table2 と table1 を比較する) を実行して、全単射マッピングを探すことができます。そうしないと、些細なケースで失敗する可能性があります...最初のすべての値が異なる (完全同型) または 2 番目のすべての値が同じ (完全同型)。この手法は、列がどの程度類似しているか、または類似していないかをランク付けまたは測定する方法を提供することにも注意してください。

これは正しい方向に進んでいますか？ちなみに、これは O(ijk) で、table1 には i 列、table 2 には j 列があり、各列には k 要素があります。理論的には、ペアごとの比較を行わずに相関関係を見つけることができる場合、メソッドに対して実行できる最善の方法は O(ik + jk) です。

于 2011-11-04T17:12:16.910 に答える