Ctrl+K

Unification Algorithm の解説

Unification Algorithm の解説#

※ アルゴリズムは一般には Union-Find Algorithm と呼ばれるが、本書では Unification Algorithm で呼んでいくことにする。Unification Algorithm では key 同士の紐付きの関係を有向 graph として表現し、ループ処理によってシステムが同一人物とみなせる key 群を特定できる graph の形に変えていく。

初期状態の graph#

WF 内の+extract_and_merge タスクによって、graph_unify_loop_0 テーブルが生成される。 これは key 同士の “follower -> leader” の関係を表現する graph の初期状態を表現している。

_images/4-2-1.png

Fig. 7 graph_unify_loop_0 Table#

graph_unify_loop_0#

この初期状態の graph (graph_unify_loop_0 テーブル) を Graphviz によって可視化したものが以下になる。

_images/graph_unify_loop_0.png

Fig. 8 graph_unify_loop_0#

graph_unify_loop_0 テーブルの作成方法#

graph_unify_loop_0 テーブルで表現される graph がどのように生成されるのかを見ていこう。

canonical_ids:
  - name: unified_cookie_id
    merge_by_keys: [td_client_id, td_global_id]
    merge_iterations: 5

canonical_ids: の設定における merge_by_keys: では、縫い合わせに使う key を優先度順に列挙する。この key の優先度が graph の作り方に影響してくる。

_images/4-3-1.png

Fig. 9 graph_unify_loop_0 テーブルの作成方法1#

元のデータに対して、以下のステップで graph_unify_loop_0 テーブルを生成する。

_images/4-4-1.png

Fig. 10 graph_unify_loop_0 テーブルの作成方法2#

  1. 全ての key カラムの中で、優先度の最も高い key を leader とする。

  2. (leader含む) 全ての key カラムを follower として行に展開し、leader とのペアを作る。

  3. 全てのテーブルで同様にソーステーブルを展開。

  4. 全てのテーブルの follower、leader ペアを UNION ALL し、follower_id、follower_ns、leader_id、leader_ns の組み合わせでユニークになるように抽出したものが graph_unify_loop_0 テーブルとなる。

follower_ns、leader_ns はそれぞれの id がどの key なのかを特定する。 (今回の例では、1なら td_client_id、2なら td_global_id となる。) 今回の設定では、ns が [1,2] の順で優先度が高いことになる。

graph_unify_loop_1#

graph_unify_loop_0 の graph を基に、以下のルールに基づいて leader を更新していく。

_images/4-5-2.png

Fig. 11 graph_unify_loop_1 における leader 更新手順1#

  • (leader ごとに) 自身の値と、1つの follower を通じて繋がっている全ての別の leader の値とを比較する。

  • もし、自身の値より (文字列の意味で) 小さい値があれば、その値を持つ leader に入れ替わる。(自身は old_leader となり、new_leader と置き換わる。)

  • この時、”old_leader -> old_leader” の関係が必ず存在するのでこれも “old_leader -> new_leader” の関係に変わる。これは、入れ替えによって old_leader は new_leader の follower に変わることを意味している。

  • 全ての leader で new_leader への入れ替えを行った、新しい “follower -> leader” の関係を持った graph が graph_unify_loop_1 テーブルとなる。

全ての leader に対して、new_leader への置き換え (もちろん自身が最小であれば置き換えられない)を行い、全てをマージしたテーブルが graph_unify_loop_1 テーブルとなる。

_images/4-6-1.png

Fig. 12 graph_unify_loop_1 における leader 更新手順2#

このように、graph_unify_loop_1 で多くの leader が入れ替わり、また入れ替わった old leader は follower として new leader を指す形となる。以後のループでは、1つ前のループ graph に対して同じ処理を繰り返すことになる。

_images/graph_unify_loop_1.png

Fig. 13 graph_unify_loop_1#

graph_unify_loop_2#

_images/graph_unify_loop_2.png

Fig. 14 graph_unify_loop_2#

graph_unify_loop_3#

_images/graph_unify_loop_3.png

Fig. 15 graph_unify_loop_3#

graph_unify_loop_4#

_images/graph_unify_loop_4.png

Fig. 16 graph_unify_loop_4#

graph_unify_loop_5 (graph)#

_images/graph_unify_loop_4.png

Fig. 17 graph#

この例では、merge_iterations:を5に設定したため、graph_unify_loop_5 がこのアルゴリズムの最終状態となる。 graph_unify_loop_5 はこの名前でテーブル出力されず、graph という名前で出力されることに注意しよう。

収束状態の判断#

Unification Algorithm は必ず収束に向かうアルゴリズムであることが知られている。

graph_unify_loop_4 (4回目のループ)で、1つの leader だけが残り、他の全ての follower がそこに向かう形となっている。これは収束した状態と判断できる。この graph の意味での収束状態の定義は、

  1. 各個人ごとに leader が1つに集約される。

  2. そしてその他の全て key がその leader “だけ” を指している。(ある follower が複数の leader を指している状態はまだ収束していない、あるいはその場合 leader が1つに集約されていないとも言える。)

と定義できる。今回の例では1人しかいないので1つの島しか形成されていないが、本来は全ユーザーに対してこういった島ができあがることになる。

この状態で初めて、同一人物の全ての key に canonical_id を割り振ることが可能になる。今回の例では merge_iterations: 4 が必要最低限のループ回数となる。

ただし、実際には Graphviz を用いて graph を描いた上で収束を判定するのは面倒かつ graph が複雑で難しい。loop 回数が足りず、縫い合わせが完了していない にて、現実的な収束判定方法を2つ紹介する。

Note

merge_iterations: (ループ回数) を大きい値に設定しても、収束した時点で処理を打ち切ってくれるので回数を多く設定することには問題ないことを知っておこう。 ただ、graph_unify_loop_N table は、収束するところまでのテーブルのみが作られ、収束した以後のテーブルは作られないことに注意。

merge_by_keys: の順番を変えた場合はどうなるか？#

ところで、以下のように td_global_id を優先度が最も高くなるように設定した場合には、 graph はどのように変遷してのだろうか。

canonical_ids:
  - name: unified_cookie_id
#   merge_by_keys: [td_client_id, td_global_id]
    merge_by_keys: [td_global_id, td_client_id]
    merge_iterations: 5

この場合には、先ほどとは全く異なるループとなっていく。

graph_unify_loop_0#

_images/graph_unify_loop_01.png

Fig. 18 graph_unify_loop_0#

graph_unify_loop_1#

_images/graph_unify_loop_11.png

Fig. 19 graph_unify_loop_1#

graph_unify_loop_2#

_images/graph_unify_loop_21.png

Fig. 20 graph_unify_loop_2#

graph_unify_loop_3#

_images/graph_unify_loop_31.png

Fig. 21 graph_unify_loop_3#

graph_unify_loop_4#

_images/graph_unify_loop_41.png

Fig. 22 graph_unify_loop_4#

graph_unify_loop_12#

_images/graph_unify_loop_12.png

Fig. 23 graph_unify_loop_12#

この順番の場合の graph はなかなか収束せず、12回目のループでやっと収束することになる。このことから、merge_by_keys: の順番を変えると、必要なループ回数が異なることがわかる。

ループ回数が少なくて済む順番が良いのか？#

そこで、「良い merge_by_keys: の順番は、ループ回数が最小となるようなものである」と考えてしまうかもしれないが、これは間違いである。(そもそも、ループ回数が最小となる key の順番を見つけるのは、全ての順番の組み合わせで一度は実行してみないといけないので現実的ではない。)

重要なのはループ回数ではなく、次に説明する個人ごとに生成される canonical_id が (以後のWFの更新に対して)できるだけ不変であるように順番を設定することである。

Contents