2018の13日目です。カレンダーの折返し地点です!データアナリストにとっての悩みのひとつである、アドホックな分析における表結合。データソースの異なる複数システムからダンプされたデータや様々なオープンデータ、表計算ファイルなどに対して、キーとなるカラムの書式、型が異なる場合、その表を結合するためには、分析の事前処理として、その変換の作業を行わなければなりません。なかで、この変換処理を自動的に構築し、与えられた2つの表に対して等結合を行うAuto-Joinという仕組みを提案しました。Auto-Joinのアルゴリズムは、大規模なデータに対しても効率的に適用され、高い確率で正確な結合が可能であることを実験で評価しています。ここでは、同論文を解説しながら、PythonでAuto-Joinの実装を進めていきます。2017.Equi-Joinの限界¶Auto-Joinが解決したい問題は何なのか。データを見ると理解が早いですね。ように、表結合しようにも、フォーマットが異なることが多々あります。データウェアハウスなどは、こうした問題が起こらないように、事前にETLを通じてデータクレンジングや前処理を行うですが、アドホックなデータ分析では、こういった前処理に多大な時間がかかってしまいます。M.](yyyy-[yyyy])このフォーマットの違いを修正する構文的変換を自動的に見つけることがこの論文のテーマです。いう方法が挙げられており、これはトークン分割、距離関数、しきい値の組み合わせを元に、キーの組み合わせを探索するもののようです。この方法はあらゆるデータの型に合わせるにはあまりにも計算量が大きく、またその値を決めることはとても難しいと考えられます。Ronald(1911-2004)この組のJaccard距離(類似度)は$0.66$となるため、しきい値は少なくともこれ以上大きな値にならなければなりません。W.(1924-)この組の類似度は$0.4$となり、これは正しい結果になりません。v_t\right|}=1.0-\frac{\left|\{George,W,Bush\}\right|}{\left|\{George,W,Bush,H,(1924-)\}\right|}=1.0-\frac{3}{5}=0.4$$しきい値に基づいた決定境界では常に正しくキーの組合せを見つけることが難しいことがわかります。して問題をとくか¶では、この問題にどのように取り組むべきか。文字の変換を行う手順を具体的に考えてみます。例に、どのように変換を行うかを考えてみましょう。し、などの操作を加えることで、キーを変換する必要があります。この問題を定義すると次のようになります。$T_t$.$P(T_s)$の操作を行うことで、$T_t$のキー列と結合できるような列を作る$P$を発見することがこの問題の定義です。$\Omega$は次のような操作関数の集合です。$\Omega$は要件に応じて操作を追加し拡張することも可能です。(foreign-key:key)を扱うものとします。はじめは、どちらが、どちらであるかはわかりません。そのため、両方向から操作を行うことで、適切な方向を見つけます。Pairs.¶この問題を解く上で、$T_s$と$T_t$それぞれの値の組合せに対して計算量は二次的に増加してしまいます。そこで、まずは一意な$q$-gramを使って行同士の関係性を見つけるというやり方で、行の組合せをを推測し計算を効率化する手順を踏みます。前の手順で得られた行の組合せを基に、$T_s$を$T_t$のキー列の型へ変換する操作を学習します。ように、最も単純な変換操作を、異なる複数の行の組から繰り返しの学習を行います。不揃いで、汚いデータを扱う際に、そうした汚れを許容するための手順です。joinの自動調節をおこないます。AUTO-JOINのための2つのステップ¶Auto-Joinを実装するための、はじめの2ステップについて、まずは考えていきましょう。一致の分析をするにあたって、記法も整理しておきます。Ct$Q_q(C)$は与えられた文字列に対して、指定された$q$で分割された$q$-gramの部分列集合を返します。rowであることは直感的にわかります。1では、Barackという$q$-gramはこれに当たりますね)ここで次のように、$p_q(k)$という式を定義してみましょう。$k$が大きい、つまり、その$q$-gramの発生頻度が低い場合、その確率は低くなるので、感覚的に理解ができます。$q$この$P_q(k)$式をもとに、次の命題を立てましょう。$C_t$に一度だけ出現する確率は命題のように表すことができます。$N$数が増えるほど、この確率は指数関数的に小さくなります。matchのまとめとして、1-to-1マッチが起きる条件を、次のように定義することにします。$q$-gramによる組合せは95.6%の精度となったようです。実世界の問題では、$q$-gramの組合せが1-to-1になることは稀であるため、より現実的な場合を考えていきましょう。m$の最小化問題として考えることができます。最後に、この一致する$q$-gramの探索を効率よく計算する方法を考えていきましょう。一致する$q$-gramを探索する単純なアルゴリズムを考えると、次のようになります。matchとして表すことができますが、見るからに非効率なやり方に思えます。S)$とすることができます。indexの生成例を次に示します。arrayを使うことで、$q$-gramの探索においてバイナリ探索を用いることで効率化が可能です。$v$$v$の取りうるすべてのSuffixに対して、最も当てはまりのよい最強の$q$-gramを$g^*$として、この$g^*$を決めるという問題に置き換えます。$m=F(g,C_t)\gt0$は$C_s$と$C_t$それぞれに一致する数です。このとき、$q$について、次のような命題を立てましょう。Rows¶それでは、ここまでの議論を用いて、実際に探索のアルゴリズムを構築していきましょう。C_s$について$\operatorname{OptimalQGram}$を適用します。先の命題で定めたように、これは最適な$q$-gramを探索する問題の過程です。C_t)$$この問題は$\frac{1}{nm}$を最大化するgを見つけることが命題であり、$g^*$のときのペアとなる行とそのスコア$score=\frac{1}{nm}$である。Pythonで実装してみましょう。表のデータ構造として、pandas.DataFrameを使うことにする。Rating'])それでは参照論文の疑似コードと対比して見ていきましょう。rt))$FindJoinableRowPairs$を実装するまえに、$BinarySearchQ$について考えていきます。$g^*$となるような最高な$q^*$を返す関数です。a+(b-a)/2$とすることで、効率的なバイナリサーチができるようになります。1最適な$q$-gramを決めるために、セルの値$v$のすべてのSuffixに対して、$BinarySearchQ(v)$を計算し、それぞれの$q$とそのときの$\frac{1}{nm}$を求め、値が最大のものを返すような操作をします。resここまでで定義してきた関数を用いて、$FindJoinableRowPairs$を実装してみましょう。結果を見やすくするために、暫定的にアウトプットをpandas.DataFrameにしています。1のデータを渡して、結果を見てみましょう。$g_u^{q^*}$とあるように、$q^*$の探索では、$T_t$のみに探索を行います。ついても同様に理論を理解し、Pythonでの実装を進めますが、これについては、日を追って加筆を行います。