目的

仕事で名寄せをしたので、そこで得た知識やノウハウを少しでも共有できればいいなと思っています。あまり知られている分野ではないので、概要把握の時間を少しでも低減させれたら嬉しいです。

名寄せとは

まず、以下の記事が分かりやすいです（感謝）。

レコード間の名寄せ(Entity Recognition/Deduplication)を省力化・自動化できるかもしれない入門~

本記事でも一応説明しておきます。

Entity・・・現存する、もしくは現実のもの（人や組織、場所など）
Record Linkage(Entity Matching, Entity Resolution etc)・・・同一のEntityを指すデータを同定するタスク。ざっくり言うと、データ集合のID等の確実に判断できるものがない状況で、"いい感じ"に同じものを推定するのが名寄せです。名寄せは様々な呼び方がありますが、大別すると「2つのEntytyの集合が与えられてマッチングを行う」ケース（Entity Matching, Entity Resolution）と「1つのEntityの集合が与えられてマッチングを行う」ケース（Deduplication）があります。py_entitymatchingでは前者に対応することで、後者にも対応することができます。

手法

設定として、データ集合A,Bがあり、$e^A _ {i}$∈A, $e^B _ {i}$∈Bとします。任意の$e^A _ {i}$に対して、同一のEntityを指す$e^B _ {j}$が$argmax _{e^B _ {j}}f(e^A _ {i}, e^B _ {j})$となるような関数fを見つけることが目標となります。この関数fは教師あり・教師なしの両方の手段で設定されうるものです。

教師なし

学習なしで関数fを得る方法です。あるentityに類似しているentityを検索する手法が考えられます。単純に「特徴量をベクトル表現にして、ベクトルの類似度でソートする」というのはベンチマークとしてとても良いと思います。テキストがある場合、TF-IDF・BOW・分散表現などを用いてベクトル化することもあります。また、データとの特性をフルに活用したルールベースも考慮すべきでしょう。

教師あり

学習の結果、関数fを得ます。いわゆるランキング学習の問題になりますので、point-wise,pair-wise,list-wiseの3通りが考えれますが、pair-wiseな手法が多い印象は受けます。伝統的なSVMやrandom forestはもちろんですが、Neural Networkを用いた手法も提案されています。どのアルゴリズムを用いるのかはデータの性質によりそうです。Deep Learning for Entity Matching: A Design Space Explorationによるとデータセットの性質によって、向いているアルゴリズムが異なることが分かります（Problem Typeがデータセットの性質で、DLはDeep Learning baseのアルゴリズム、Magellanは非Deep Learningです）。テキストベースのデータの場合、Deep Learningベースの手法の方がパフォーマンスが良いみたいです。また、単語をEmbeddingしているのですが、その際に用いる分散表現を得るためのFast textを専門用語が多い場合はfrom scratchで学習させるかどうかも検討すべきでしょう。データが汚い場合（Dirty）、テキストベースのデータに変換することが可能です。

Blocking ~データ量の削減の工夫~

上記の教師なし・教師ありのどちらの手法もデータ量が多すぎると機能しない恐れがあります。例えば、教師なしでベクトルをコサイン類似度で類似度を測る場合、データ量が多すぎるとメモリに乗らないです（これは分割可能であれば、分割すれば良いとは思いますが）。他にも、計算時間が膨大になる可能性もあります。さらに、教師ありの場合、名寄せの性質上、データが非常に不均衡です。つまり、|A|=10000, |B| = 10000の時に、同一のEntityを指しているペアは1つしかありませんが、Brute-force的な組み合わせは10000×10000=100000000あります。これを学習データとする場合、マッチしているペアとマッチしてないペアは10000 : (100000000 - 1)となり、相当な不均衡データとなることが分かります。これではこのまま学習データとして活用できません。そこでblockingというデータ量を減らす工夫がなされます。blockingとは類似しているデータを同一のクラスターとしてクラスタリングし、そのクラスター内でのみpari-wiseな比較を行う手法です。小さなクラスターに分割していくことでトータルの比較の回数を小さくすることが可能になります。もちろん正解データがクラスターに含まれない＝リコールが下がる、ということもあり得ますが、極めてリコールの低下が小さければ、それは許される（むしろ奨励される）ケースが多いと思います。

Blockingについての包括的なサーベイ論文としてはComparative Analysis of Approximate Blocking Techniques for Entity Resolutionがよくまとまっていると思います。

上図は論文中に出てきたBlockingの手法のまとめを示しています。StBl, ACl, ESoNeなどが手法、Defaultはパラメータのデフォルト値、$D _ {cens}$, $D _ {rest}$などはデータセットで、各データセットに対応する最適なパラメータを示しています。これを見れば分かるようにBlockingの手法はたくさんのチューニングポイント（どの手法を使うのか、ハイパーパラメータの値）があります。手法はequality baseのものとsimilarity baseのものに大別できると思います。興味があればみて見てください。
時間があれば、全て試せばいいと思うのですが、要件によっては事前にどのBlockingの手法を採用するか絞り込むことが可能です。一般的にはリコールとどれだけ減らせたかの最適なバランスを取ることになると思います（論文中ではα(B, E)として定義される関数が、リコールと減少したペア数のバランスを考慮した指標となっています。興味があれば見てみてください。）。

これはどれだけ組み合わせを減らせたかの結果です。
グラフを理解するための知識について説明させてください。
上記の論文はBlockingの手法を下記のように分解して考えています。
Blocking = Block Building + Block Cleaning + Comparison Cleaning

	意味
Block Building	1つ、または2つのデータ集合をinputとして、複数のblockにクラスタ分類する
Block Cleaning	blockの集合をinputとして、不必要な比較を含むblockを削除を削除する
Comparison Cleaning	blockの集合をinputとして、不必要な比較を削除する

Block BuildingのみのアルゴリズムをLazy Blocking、「Block Building + Block Cleaning」 or 「Block Building + Block Cleaning + Comparison Cleaning」の機能を含むアルゴリズムをProactive Blockingと呼んでいます。
Lazy Blocking MethodとProactive Blocking Methodをフェアに比較するためにLazy BlockingにはBlock Cleaning やComparison Cleaningを行なっています。全てのケースで、Block CleaningやComparison Cleaningをすることでペア数が減っているのが見て取れます。これはペア数が減っているほど良いです。

これはリコールの結果です。Block CleaningやComparison Cleaningをすることでリコールが減っていることが分かります。これはリコールが減らない方が良い手法です。

一般的には上記の通りなのですが、具体的なケースを想定してみます。

データ量が極めて多い

データ量によってはスケールするのが難しいアルゴリズムもあります。例えば、データ量が数十万のオーダーになると、CaClやECaCl、MFIBなどはスケールしません。

効率性よりも高いリコールが必要

Lazy Blocking Methodsの方がリコールが高い傾向があります。

実装コスト

アルゴリズムによってはライブラリ等の実装がない（見つけられなかった）ので、実装するコストが必要です。

feature engineeringのコスト

Lazy Blocking Methodsの方がパラメータに対して頑強です。feature engineeringのコストをかけられないのであれば、Lazy Blocking Methodsの方がいいでしょう。

Blockingの実例を載せておきます。Non-comercialなので、参考程度だとは思います。

名寄せのシステム構成

データ集合A,Bが巨大だった場合、その状態で良いBlockerやMatcherを探すのは大変です。なので、Down Samplingをする必要があり、それがA', B'です。単純なランダムサンプリングは上手く行かない場合があるようです。なので、何らかの対策を講じる必要があるかもしれません（例えば、類似度ベースで絞り込むなどしてマッチしているサンプルが多く含まれるようにすれば良いとは思います）。これはBlockerのoutputに対するサンプリングでも話は同じです。
あとは、BlockerとMatcherを開発していきます。labelingがない場合、自分でlabelingを行う必要があり、非常にハードなプロセスを経る必要があります。

本番環境だとスケールを意識する必要があるかもしれません。上の構成はスケーラビリティやモニタリングなどあらゆる機能がフルフルであるので、要件次第では不要な部分もあると思います。また、クラウドソーシング等を利用することもあると思います。

開発プロセス

上記で名寄せの基本的なコンポーネントに対する基礎的な理解はできたと思います。具体的にどのように開発するのかについてまとめておきます。How-To Guide to Entity Matchingを簡潔にまとめたものです。

Down Sampling
先ほど触れたようにデータ量が100000を超えるようならDown Samplingを検討する必要があります。
データを見る
データを観察します。これはデータセットの性質を考察する（=Matcherにどのアルゴリズムを使うべきかの重要な示唆となる）ことになります。さらに、データによってはEntityをユニークに同定するための強力なkeyがあるかもしれません（国、メーカーなど）。
Matchするということについて考察する
データとデータがMatchする、ということについて深く考える必要があります。例えば、レストランのマッチングを考えた時に、チェーンのレストランで違う場所にあるレストランはMatchしてないのでしょうか？これは要件次第で、ビジネスオーナーと話し合うことが強く奨励されています。
Blocking
個々のアルゴリズムについては上述の通りですが、開発という視点で重要になってくる要素がいくつかあります。簡単なBlockerを積み重ねるほうがシンプルでデバッグしやすいです。まずはoverlap blocking(少なくともk個のtokenは共有している)、次にAttribute equalty(特定の一つのカラムの値が等しい)など簡単なアルゴリズムからやると良いです。
また、伝統的にはblockerをLとして生成されるblockの集合block(L, A', B')がメモリに乗るくらいで良いらしいのですが、実際にはA', B'はdown samplingの結果なので、実際にどのようにblockingを行うかを考慮する必要があります（もし一度に計算するなら、block(L, A, B)を考慮する必要がありますし、データが時間と共に増えていくならバッチになる=前回の差分から増加したデータ集合A'', B''について、block(L, A'', B'')を考慮する必要があります）。さらに、labelがつけられてない場合は、blockingの結果を適宜目で見て確認することで開発していく必要があります。将来的にはblockingとmatcherをend to endで最適化する手法がこの分野を支配していくと思います。
samplingとlabeling
Blockingでデータをblockに分割したあとは、そこから学習に使うデータをsamplingし、labelingする必要があります。効率的に学習データを生成するためにイテレーション的にlabelingすることが推奨されています。
まず、n個のlabelがつけられたペアが欲しいとします。blockingの結果から、k個（k << n）だけランダムに選びlabelingします。ここで、matchしているペアが極端に少ない場合は(n - k)個をさらにlabelingしたところで、matchしているペアが少ないので学習データには向きません。この場合は再びblockingのアルゴリズムを開発します。matchしているペアが十分ある場合は、(n-k)個をさらにlabelingして、これを学習データとします。
6.Matcherの開発
Matcherの開発はpy_entitymatchingが使うとSVMやナイーブベイズなどの基本的なアルゴリズムを簡単に使用することができます。より高度なアルゴリズムを検討しているとしても、ベンチマークとしてこれらと比較すれば良いと思います。
Matcherのデバッグ
予測を間違えているデータについて、なぜ間違っているのかを考えます。間違いは以下の四つに分類できます。

データが汚い
labelingが間違っている
特徴量に問題がある
Matcherのアルゴリズムに問題がある

そして、その間違いをfixさせることで性能を向上させることができます。Matcherのトレーニング -> デバッグ -> Matcherのトレーニングを繰り返すことで性能を向上させます。

参考

Comparative Analysis of Approximate Blocking Techniques for Entity Resolution
Deep Learning for Entity Matching: A Design Space Exploration
Deep Learning Based Approach for Entity Resolution in Databases
Magellan: Toward Building Entity Matching Management Systems
How-To Guide to Entity Matching