[mathjax]
Record Linkage、Entity Recognitionなど、いわゆる「名寄せ」問題には、割とさまざまな解決策が
提案されている。その1つに確率論的な数学的背景を持つFellegi-Sunterモデルを実装したSplinkがある。
数学的背景について咀嚼して説明してくれているサイトはあまりなく、Splinkの公式ドキュメントが唯一
に近いソースだろうと思う。
今回は5万人の人物データを使って重複を除去するSplinkの主要な機能のサンプルを追ってみた。
数式を読んだところで実りは薄い、ということもあり、なるべく数式を読まずに読み進めたが、
モデルのパラメタ、予測結果を解釈する際にどうしても数式を読まないとわからない箇所があった。
特にベイズ統計について理解がかなり浅くて、正直なところ理解しきれてはいない。
Splinkの公式ドキュメントを読み進めていった際に気付いたメモを書いてみることにした。
[arst_toc tag=\"h4\"]
環境構築・準備
環境構築の実装部分は主な学習要素ではないのでClaude Codeでサクッと作ってみた。
まずはPlan modeで計画を立ててもらう。これぐらいだとほぼ言い値で使える。
DuckDB、Splinkを使う最小構成の環境を作ります。環境はDocker composeで構築します。計画を立ててください。
⏺ DuckDB、Splinkを使うDocker Compose環境の計画を完了しました。
計画概要
1. 設計文書: .tmp/design.mdで要件、アーキテクチャ、技術仕様を定義
2. タスク管理: .tmp/task.mdで詳細な実装手順を3フェーズに分けて整理
主要コンポーネント
- Jupyter Lab環境: DuckDB、Splink、必要なライブラリがプリインストール
- データボリューム: サンプルデータ、notebook、出力用のディレクトリ
- 最小構成: 開発・学習用途に特化した軽量環境
次のステップ
実装を開始する場合は、Phase 1から順番に進めます：
1. Docker設定ファイル作成
2. ディレクトリ構造構築
3. サンプル実装
4. テストと検証
計画の詳細は.tmp/design.mdと.tmp/task.mdをご確認ください。実装を開始しますか？
実際にファイルを作ってもらうと以下のような構成となる。
得られる中間成果物である docker-compose.yml、Dockerfile は本記事では省略する。
.
├── data
├── docker-compose.yml
├── Dockerfile
├── notebooks
├── output
└── requirements.txt
普通に http://localhost:8888 で JupyterLab が開く。
使用するサンプルデータ
5万人の人物データを使って名寄せを行うサンプル。おそらくSplinkの用途として最初に思いつくやつ。
Splinkにデータをロードする前に必要なデータクリーニング手順について説明がある。
公式によると、まずは行に一意のIDを割り当てる必要がある。
データセット内で一意となるIDであって、重複除去した後のエンティティを識別するIDのことではない。
[clink implicit=\"false\" url=\"https://moj-analytical-services.github.io/splink/demos/tutorials/01_Prerequisites.html\" imgurl=\"https://user-images.githubusercontent.com/7570107/85285114-3969ac00-b488-11ea-88ff-5fca1b34af1f.png\" title=\"Data Prerequisites\" excerpt=\"Splink では、リンクする前にデータをクリーンアップし、行に一意の ID を割り当てる必要があります。このセクションでは、Splink にデータをロードする前に必要な追加のデータクリーニング手順について説明します。\"]
使用するサンプルデータは以下の通り。
from splink import splink_datasets
df = splink_datasets.historical_50k
df.head()
データの分布を可視化
splink.exploratoryのprofile_columnsを使って分布を可視化してみる。
from splink import DuckDBAPI
from splink.exploratory import profile_columns
db_api = DuckDBAPI()
profile_columns(df, db_api, column_expressions=[\"first_name\", \"substr(surname,1,2)\"])
同じ姓・名の人が大量にいることがわかる。
ブロッキングとブロッキングルールの評価
テーブル内のレコードが他のレコードと「同一かどうか」を調べるためには、
基本的には、他のすべてのレコードとの何らかの比較操作を行うこととなる。
全てのレコードについて全てのカラム同士を比較したいのなら、
対象のテーブルをCROSS JOINした結果、各カラム同士を比較することとなる。
SELECT ...
FROM input_tables as l
CROSS JOIN input_tables as r
あるカラムが条件に合わなければ、もうその先は見ても意味がない、
というケースは多い。例えば、まず first_name 、surname が同じでなければ、
その先の比較を行わない、というのはあり得る。
SELECT ...
FROM input_tables as l
INNER JOIN input_tables as r
ON l.first_name = r.first_name AND l.surname = r.surname
このような考え方をブロッキング、ON句の条件をブロッキングルールと言う。
ただ、これだと性と名が完全一致していないレコードが残らない。
そこで、ブロッキングルールを複数定義し、いずれかが真であれば残すことができる。
ここでポイントなのが、ブロッキングルールを複数定義したとき、
それぞれのブロッキングルールで重複して選ばれるレコードが発生した場合、
Splinkが自動的に排除してくれる。
このため、ブロッキングルールを重ねがけすると、最終的に残るレコード数は一致する。
ただ、順番により、同じルールで残るレコード数は変化する。
逆に言うと、ブロッキングルールを足すことで、重複除去後のOR条件が増えていく。
積算グラフにして、ブロッキングルールとその順番の効果を見ることができる。
from splink import DuckDBAPI, block_on
from splink.blocking_analysis import (
cumulative_comparisons_to_be_scored_from_blocking_rules_chart,
)
blocking_rules = [
block_on(\"substr(first_name,1,3)\", \"substr(surname,1,4)\"),
block_on(\"surname\", \"dob\"),
block_on(\"first_name\", \"dob\"),
block_on(\"postcode_fake\", \"first_name\"),
block_on(\"postcode_fake\", \"surname\"),
block_on(\"dob\", \"birth_place\"),
block_on(\"substr(postcode_fake,1,3)\", \"dob\"),
block_on(\"substr(postcode_fake,1,3)\", \"first_name\"),
block_on(\"substr(postcode_fake,1,3)\", \"surname\"),
block_on(\"substr(first_name,1,2)\", \"substr(surname,1,2)\", \"substr(dob,1,4)\"),
]
db_api = DuckDBAPI()
cumulative_comparisons_to_be_scored_from_blocking_rules_chart(
table_or_tables=df,
blocking_rules=blocking_rules,
db_api=db_api,
link_type=\"dedupe_only\",
)
積算グラフは以下の通り。積み上がっている数値は「比較の数」。
要は、論理和で条件を足していって、次第に緩和されている様子がわかる。
DuckDBでは比較の数を2,000万件以内、Athena,Sparkでは1億件以内を目安にせよとのこと。
比較の定義
Splinkは Fellegi-Sunter model モデル (というかフレームワーク) に基づいている。
https://moj-analytical-services.github.io/splink/topic_guides/theory/fellegi_sunter.html
各カラムの同士をカラムの特性に応じた距離を使って比較し、重みを計算していく。
各カラムの比較に使うためのメソッドが予め用意されているので、特性に応じて選んでいく。
以下では、first_name, sur_name に ForenameSurnameComparison が使われている。
dobにDateOfBirthComparison、birth_place、ocupationにExactMatchが使われている。
import splink.comparison_library as cl
from splink import Linker, SettingsCreator
settings = SettingsCreator(
link_type=\"dedupe_only\",
blocking_rules_to_generate_predictions=blocking_rules,
comparisons=[
cl.ForenameSurnameComparison(
\"first_name\",
\"surname\",
forename_surname_concat_col_name=\"first_name_surname_concat\",
),
cl.DateOfBirthComparison(
\"dob\", input_is_string=True
),
cl.PostcodeComparison(\"postcode_fake\"),
cl.ExactMatch(\"birth_place\").configure(term_frequency_adjustments=True),
cl.ExactMatch(\"occupation\").configure(term_frequency_adjustments=True),
],
retain_intermediate_calculation_columns=True,
)
# Needed to apply term frequencies to first+surname comparison
df[\"first_name_surname_concat\"] = df[\"first_name\"] + \" \" + df[\"surname\"]
linker = Linker(df, settings, db_api=db_api)
ComparisonとComparison Level
ここでSplinkツール内の比較の概念の説明。以下の通り概念に名前がついている。
Data Linking Model
├─-- Comparison: Date of birth
│ ├─-- ComparisonLevel: Exact match
│ ├─-- ComparisonLevel: One character difference
│ ├─-- ComparisonLevel: All other
├─-- Comparison: First name
│ ├─-- ComparisonLevel: Exact match on first_name
│ ├─-- ComparisonLevel: first_names have JaroWinklerSimilarity > 0.95
│ ├─-- ComparisonLevel: first_names have JaroWinklerSimilarity > 0.8
│ ├─-- ComparisonLevel: All other
モデルのパラメタ推定
モデルの実行に必要なパラメタは以下の3つ。Splinkを用いてパラメタを得る。
ちなみに u は \"\'U\'nmatch\"、m は \"\'M\'atch\"。背後の数式の説明で現れる。
No
パラメタ
説明
1
無作為に選んだレコードが一致する確率
入力データからランダムに取得した2つのレコードが一致する確率 (通常は非常に小さい数値)
2
u値(u確率)
実際には一致しないレコードの中で各 ComparisonLevel に該当するレコードの割合。具体的には、レコード同士が同じエンティティを表すにも関わらず値が異なる確率。例えば、同じ人なのにレコードによって生年月日が違う確率。これは端的には「データ品質」を表す。名前であればタイプミス、別名、ニックネーム、ミドルネーム、結婚後の姓など。
3
m値(m確率)
実際に一致するレコードの中で各 ComparisonLevel に該当するレコードの割合。具体的には、レコード同士が異なるエンティティを表すにも関わらず値が同じである確率。例えば別人なのにレコードによって性・名が同じ確率 (同姓同名)。性別は男か女かしかないので別人でも50%の確率で一致してしまう。
無作為に選んだレコードが一致する確率
入力データからランダムに抽出した2つのレコードが一致する確率を求める。
値は0.000136。すべての可能なレコードのペア比較のうち7,362.31組に1組が一致すると予想される。
合計1,279,041,753組の比較が可能なため、一致するペアは合計で約173,728.33組になると予想される、
とのこと。
linker.training.estimate_probability_two_random_records_match(
[
block_on(\"first_name\", \"surname\", \"dob\"),
block_on(\"substr(first_name,1,2)\", \"surname\", \"substr(postcode_fake,1,2)\"),
block_on(\"dob\", \"postcode_fake\"),
],
recall=0.6,
)
> Probability two random records match is estimated to be 0.000136.
> This means that amongst all possible pairwise record comparisons,
> one in 7,362.31 are expected to match.
> With 1,279,041,753 total possible comparisons,
> we expect a total of around 173,728.33 matching pairs
u確率の推定
実際には一致しないレコードの中でComparisonの評価結果がPositiveである確率。
基本、無作為に抽出したレコードは一致しないため、「無作為に抽出したレコード」を
「実際には一致しないレコード」として扱える、という点がミソ。
probability_two_random_records_match によって得られた値を使ってu確率を求める。
estimate_u_using_random_sampling によって、ラベルなし、つまり教師なしでu確率を得られる。
レコードのペアをランダムでサンプルして上で定義したComparisonを評価する。
ランダムサンプルなので大量の不一致が発生するが、各Comparisonにおける不一致の分布を得ている。
これは、例えば性別について、50%が一致、50%が不一致である、という分布を得ている。
一方、例えば生年月日について、一致する確率は 1%、1 文字の違いがある確率は 3%、
その他はすべて 96% の確率で発生する、という分布を得ている。
linker.training.estimate_u_using_random_sampling(max_pairs=5e6)
> ----- Estimating u probabilities using random sampling -----
>
> Estimated u probabilities using random sampling
>
> Your model is not yet fully trained. Missing estimates for:
> - first_name_surname (no m values are trained).
> - dob (no m values are trained).
> - postcode_fake (no m values are trained).
> - birth_place (no m values are trained).
> - occupation (no m values are trained).
m確率の推定
「実際に一致するレコード」の中で、Comparisonの評価がNegativeになる確率。
そもそも、このモデルを使って名寄せ、つまり「一致するレコード」を見つけたいのだから、
モデルを作るために「実際に一致するレコード」を計算しなければならないのは矛盾では..となる。
無作為抽出結果から求められるu確率とは異なり、m確率を求めるのは難しい。
もしラベル付けされた「一致するレコード」、つまり教師データセットがあるのであれば、
そのデータセットを使ってm確率を求められる。
例えば、日本人全員にマイナンバーが振られて、全てのレコードにマイナンバーが振られている、
というアナザーワールドがあるのであれば、マイナンバーを使ってm確率を推定する。(どういう状況??)
ラベル付けされたデータがないのであれば、EMアルゴリズムでm確率を求めることになっている。
EMアルゴリズムは反復的な手法で、メモリや収束速度の点でペア数を減らす必要があり、
例ではブロッキングルールを設定している。
以下のケースでは、first_nameとsurnameをブロッキングルールとしている。
つまり、first_name, surnameが完全に一致するレコードについてペア比較を行う。
この仮定を設定したため、first_name, surname (first_name_surname) のパラメタを推定できない。
training_blocking_rule = block_on(\"first_name\", \"surname\")
training_session_names = (
linker.training.estimate_parameters_using_expectation_maximisation(
training_blocking_rule, estimate_without_term_frequencies=True
)
)
> ----- Starting EM training session -----
>
> Estimating the m probabilities of the model by blocking on:
> (l.\"first_name\" = r.\"first_name\") AND (l.\"surname\" = r.\"surname\")
>
> Parameter estimates will be made for the following comparison(s):
> - dob
> - postcode_fake
> - birth_place
> - occupation
>
> Parameter estimates cannot be made for the following comparison(s) since they are used in the blocking rules:
> - first_name_surname
>
> Iteration 1: Largest change in params was 0.248 in probability_two_random_records_match
> Iteration 2: Largest change in params was 0.0929 in probability_two_random_records_match
> Iteration 3: Largest change in params was -0.0237 in the m_probability of birth_place, level `Exact match on > birth_place`
> Iteration 4: Largest change in params was 0.00961 in the m_probability of birth_place, level `All other >comparisons`
> Iteration 5: Largest change in params was -0.00457 in the m_probability of birth_place, level `Exact match on birth_place`
> Iteration 6: Largest change in params was -0.00256 in the m_probability of birth_place, level `Exact match on birth_place`
> Iteration 7: Largest change in params was 0.00171 in the m_probability of dob, level `Abs date difference Iteration 8: Largest change in params was 0.00115 in the m_probability of dob, level `Abs date difference Iteration 9: Largest change in params was 0.000759 in the m_probability of dob, level `Abs date difference Iteration 10: Largest change in params was 0.000498 in the m_probability of dob, level `Abs date difference Iteration 11: Largest change in params was 0.000326 in the m_probability of dob, level `Abs date difference Iteration 12: Largest change in params was 0.000213 in the m_probability of dob, level `Abs date difference Iteration 13: Largest change in params was 0.000139 in the m_probability of dob, level `Abs date difference Iteration 14: Largest change in params was 9.04e-05 in the m_probability of dob, level `Abs date difference <= 10 year`
同様にdobをブロッキングルールに設定して実行すると、dob以外の列についてパラメタを推定できる。
training_blocking_rule = block_on(\"dob\")
training_session_dob = (
linker.training.estimate_parameters_using_expectation_maximisation(
training_blocking_rule, estimate_without_term_frequencies=True
)
)
> ----- Starting EM training session -----
>
> Estimating the m probabilities of the model by blocking on:
> l.\"dob\" = r.\"dob\"
>
> Parameter estimates will be made for the following comparison(s):
> - first_name_surname
> - postcode_fake
> - birth_place
> - occupation
>
> Parameter estimates cannot be made for the following comparison(s) since they are used in the blocking rules:
> - dob
>
> Iteration 1: Largest change in params was -0.474 in the m_probability of first_name_surname, level `Exact match on first_name_surname_concat`
> Iteration 2: Largest change in params was 0.052 in the m_probability of first_name_surname, level `All other comparisons`
> Iteration 3: Largest change in params was 0.0174 in the m_probability of first_name_surname, level `All other comparisons`
> Iteration 4: Largest change in params was 0.00532 in the m_probability of first_name_surname, level `All other comparisons`
> Iteration 5: Largest change in params was 0.00165 in the m_probability of first_name_surname, level `All other comparisons`
> Iteration 6: Largest change in params was 0.00052 in the m_probability of first_name_surname, level `All other comparisons`
> Iteration 7: Largest change in params was 0.000165 in the m_probability of first_name_surname, level `All other comparisons`
> Iteration 8: Largest change in params was 5.29e-05 in the m_probability of first_name_surname, level `All other comparisons`
>
> EM converged after 8 iterations
>
> Your model is not yet fully trained. Missing estimates for:
> - first_name_surname (some u values are not trained).
モデルパラメタの可視化
m確率、u確率の可視化。
マッチウェイトの可視化。マッチウェイトは (log_2 (m / u))で計算される。
linker.visualisations.match_weights_chart()
モデルの保存と読み込み
以下でモデルを保存できる。
settings = linker.misc.save_model_to_json(
\"./saved_model_from_demo.json\", overwrite=True
)
以下で保存したモデルを読み込める。
import json
settings = json.load(
open(\'./saved_model_from_demo.json\', \'r\')
)
リンクするのに十分な情報が含まれていないレコード
「John Smith」のみを含み、他のすべてのフィールドがnullであるレコードは、
他のレコードにリンクされている可能性もあるが、潜在的なリンクを明確にするには十分な情報がない。
以下により可視化できる。
linker.evaluation.unlinkables_chart()
横軸は「マッチウェイトの閾値」。縦軸は「リンクするのに十分な情報が含まれないレコード」の割合。
マッチウェイト閾値=6.11ぐらいのところを見ると、入力データセットのレコードの約1.3%が
リンクできないことが示唆される。
訓練済みモデルを使って未知データのマッチウェイトを予測
上で構築した推定モデルを使用し、どのペア比較が一致するかを予測する。
内部的には以下を行うとのこと。
blocking_rules_to_generate_predictionsの少なくとも1つと一致するペア比較を生成
Comparisonで指定されたルールを使用して、入力データの類似性を評価
推定された一致重みを使用し、要求に応じて用語頻度調整を適用して、最終的な一致重みと一致確率スコアを生成
df_predictions = linker.inference.predict(threshold_match_probability=0.2)
df_predictions.as_pandas_dataframe(limit=1)
> Blocking time: 0.88 seconds
> Predict time: 1.91 seconds
>
> -- WARNING --
> You have called predict(), but there are some parameter estimates which have neither been estimated or > specified in your settings dictionary. To produce predictions the following untrained trained parameters will > use default values.
> Comparison: \'first_name_surname\':
> u values not fully trained
records_to_plot = df_e.to_dict(orient=\"records\")
linker.visualisations.waterfall_chart(records_to_plot, filter_nulls=False)
predictしたマッチウェイトの可視化、数式との照合
predictしたマッチウェイトは、ウォーターフォール図で可視化できる。
マッチウェイトは、モデル内の各特徴量によって一致の証拠がどの程度提供されるかを示す中心的な指標。
(lambda)は無作為抽出した2つのレコードが一致する確率。(K=m/u)はベイズ因子。
begin{align}
M &= log_2 ( frac{lambda}{1-lambda} ) + log_2 K \\
&= log_2 ( frac{lambda}{1-lambda} ) + log_2 m - log_2 u
end{align}
異なる列の比較が互いに独立しているという仮定を置いていて、
2つのレコードのベイズ係数が各列比較のベイズ係数の積として扱う。
begin{eqnarray}
K_{feature} = K_{first_name_surname} + K_{dob} + K_{postcode_fake} + K_{birth_place} + K_{occupation} + cdots
end{eqnarray}
マッチウェイトは以下の和。
begin{eqnarray}
M_{observe} = M_{prior} + M_{feature}
end{eqnarray}
ここで
begin{align}
M_{prior} &= log_2 (frac{lambda}{1-lambda}) \\
M_{feature} &= M_{first_name_surname} + M_{dob} + M_{postcode_fake} + M_{birth_place} + M_{occupation} + cdots
end{align}
以下のように書き換える。
begin{align}
M_{observe} &= log_2 (frac{lambda}{1-lambda}) + sum_i^{feature} log_2 (frac{m_i}{u_i}) \\
&= log_2 (frac{lambda}{1-lambda}) + log_2 (prod_i^{feature} (frac{m_i}{u_i}) )
end{align}
ウォーターフォール図の一番左、赤いバーは(M_{prior} = log_2 (frac{lambda}{1-lambda}))。
特徴に関する追加の知識が考慮されていない場合のマッチウェイト。
横に並んでいる薄い緑のバーは (M_{first_name_surname} + M_{dob} + M_{postcode_fake} + M_{birth_place} + M_{occupation} + cdots)。
各特徴量のマッチウェイト。
一番右の濃い緑のバーは2つのレコードの合計マッチウェイト。
begin{align}
M_{feature} &= M_{first_name_surname} + M_{dob} + M_{postcode_fake} + M_{birth_place} + M_{occupation} + cdots \\
&= 8.50w
end{align}
まとめ
長くなったのでいったん終了。この記事では教師なし確率的名寄せパッケージSplinkを使用してモデルを作ってみた。
次の記事では、作ったモデルを使用して実際に名寄せをしてみる。
途中、DuckDBが楽しいことに気づいたので、DuckDBだけで何個か記事にしてみようと思う。
