背景
どういう需要からか
(Zennとダブルポストです)
顧客企業や、営業アタックリストのための情報を、部署ごとだったり、サービスごとに保持していると、それらを統合して、自社全体の顧客企業や営業情報をより正確に把握したい、というケースがあります。
そういった場合に、企業情報のリスト同士をマッチングさせるシステムが必要になります。
具体例としては、複数のデータソースに、XXXという会社と思われるデータが、下記のような感じであるとします。
こういったものを、同一の会社として扱えるようにしたいということです。
| データソース | 名前 | 住所 | 電話番号 |
|---|---|---|---|
| 1 | 株式会社 XXX | □□県 yyy市1-2-3 | 03aaabbbccc |
| 2 | XXX | yyy市１丁目２番３ | 03aaabbbccc |
| 3 | XXX株式会社 | □□県yyy市１丁目 |
これは、Record linkageという分野と絡んできます。２つのレコードが、同一のものをさすかどうか、ということです。データセットは単一のときもあれば、複数のときもあります。いくつか論文でているくらいなので、真面目に取り組むと厄介な問題をはらんでいます。
既存製品やライブラリ
帝国データバンクやランドスケイプなど、企業情報のマスタデータを提供している企業では、提供しているマスタデータとマッチングをかけて、そのIDを付与することをなんらかの形で提供しているようです。
顧客情報を複数のDBなどでもっていて、あるひとつのマスタデータのIDをそれらに付与すれば、データを一元管理できるというわけです。
ライブラリで下記のようなものがあります。
dedupeは機械学習の技術の応用として、この問題に取り組んでいるようです。
一番手軽な方法
電話番号だけでやるのが一番簡単です。電話番号が一致したら、同じ企業ということにします。
電話番号が使い回されているものが大量にあるなど、データがよほど汚くなければ、大概はこれでも十分です。
実際によくある問題
現実はそう単純な手がとれないことも多いです。
- データソースごとに、会社名や住所の表記がばらばら
- データソースによっては、会社名しかないなど、項目の欠損がある
- 項目の欠損の仕方もデータソースごとにばらばら
- データの総件数が多い（100万件以上）
といったことがざらにあります。
特に件数がネックです。件数がすくなければ、２つのデータセットの組み合わせを総当りして、組み合わせごとに、文字列の距離などを使った類似度を出せばいいです。ですが、 組み合わせの数は、異なるデータセットならm * n、 ひとつのデータセットなら nC2 なので、２乗に比例するといえる状況です。100件程度なら、組み合わせの数は1万でおさまりますが、1万件をこえてからは、億単位になります。
現実問題、重複データが多かったとしても、同一とみなせる組み合わせは総当りの数から比べればかなり少ないはずです。なんらかの手法で、「同一と判定されそうな」組み合わせに絞り込むことが必要です。
それらに対してだけ類似度の計算をするというのが、基本的な方針です。
全文検索の利用
「同一と判定されそうな」組み合わせに絞り込むために、全文検索を使ってみようというアイディアです。
- 類似度の計算に使うカラムを（全て or 一部）をつなげたカラムを追加
- そのカラムに対して全文検索し、上位の一定件数（例えば5件）のみを使用
これによって、類似度を計算する対象が、高々、マッチングさせたい件数 * 定数 でおさえられます。
各項目が完全一致しているか、ほぼ一致しているようであれば、全文検索で上位にきます。これで同一とみなせそうなものがある程度拾えます。
これは以下のことを前提とした方針です。
- 比較的わかりやすい仕組みにする
- 多少の取りこぼしは許容する
- ある程度の速さは出したい
ということで、理論的に取りこぼしが一定以下とか、最速といったことは別に目指さないです。
Record linkageについて、学術的に取り組むのではなく、既存の技術でそれなりの結果を出すためのアイディアです。
100万件のデータをマッチングさせることを考えると、1回のクエリの実行時間はミリ秒単位が目標です。
マシンスペック
- MacBook Air (Retina, 13-inch, 2020)
- プロセッサ 1.1 GHz クアッドコアIntel Core i5
- メモリ 8 GB 3733 MHz LPDDR4X
サンプル実装
フリーで手軽に手に入る、法人番号のデータをもとに、テーブルを作成します。（法人番号自体は、このサイトで検索のAPIを提供しています。）
都道府県ごとにダウンロードできるので、今回は東京のみを使います。約110万件なので、それなりのサイズです。データとしてはこのようなものです。
1,1000011000005,01,1,2018-04-02,2015-10-05,"国立国会図書館",,101,"東京都","千代田区","永田町１丁目１０－１",,13,101,1000014,,,,,,,2015-10-05,1,"National Diet Library","Tokyo","1-10-1,Nagatacho, Chiyoda ku",,"コクリツコッカイトショカン",0
今回は名前と住所のみを取り出します。DBはpostgresqlと、高速な全文検索をするために、PGroongaという拡張機能をいれます。
ダウンロードしたファイルから、必要な項目の抜き出しと、名前と住所の結合をします。
import csv
def main():
print('start') # Press ⌘F8 to toggle the breakpoint.
with open('13_tokyo_all.csv', 'r', newline='') as f, open('master.csv', 'w', newline='\n', encoding='utf8') as f2:
reader = csv.reader(f, delimiter=',', quotechar='"')
writer = csv.DictWriter(f2, delimiter=',', quotechar='"', fieldnames=['corporate_number', 'name', 'address', 'search'])
for row in reader:
corporate_number = row[1]
name = row[6]
address1 = row[9]
address2 = row[10]
address3 = row[11]
address = address1 + address2 + address3
search = name + address
target_row = {'corporate_number': corporate_number, 'name': name, 'address': address, 'search': search}
writer.writerow(target_row)
if __name__ == '__main__':
main()
テーブルは次のようにします。比較として、pg_bigmという別の全文検索の拡張機能もいれるので、indexは２つセットします。
test=# \d company
Table "public.company"
Column | Type | Collation | Nullable | Default
------------------+------------------------+-----------+----------+---------
corporate_number | character varying(13) | | not null |
name | character varying(150) | | |
address | character varying(100) | | |
search | text | | |
Indexes:
"company_pkey" PRIMARY KEY, btree (corporate_number)
"bigm_idx" gin (search gin_bigm_ops)
"pgroonga_search_index" pgroonga (search)
pgroongaによる全文検索
公式サイトに早いと謳っているだけあって、かなりよいです。
何回かやると、5ミリ秒前後になってきました。
ただ、スコアが 「何個キーワードが含まれていたか」（TF、Term Frequency）です。 なので、やや扱いづらいところです。一部の単語が入ってるだけのものも、検索結果にでてきます。これだけでは足切りとしてはやや不十分な感があります。それもあって、bigm_similarityの類似度もあわせて出しています。
test=# select name, address, pgroonga_score(tableoid, ctid) as score, bigm_similarity(search, '国立国会図書館千代田区永田町１丁目１０−１') as bigm_similarity from company where search &@* '国立国会図書館千代田区永田町１丁目１０−１' order by pgroonga_score(tableoid, ctid) desc limit 5;
name | address | score | bigm_similarity
------------------------------------------------+------------------------------------------------------------+---------+-----------------
国立国会図書館 | 東京都千代田区永田町１丁目１０－１ | 1070423 | 0.76
一般社団法人スポーツ立国日本・選手生涯支援機構 | 東京都港区赤坂２丁目２０番５号 | 21846 | 0.051282052
特定非営利活動法人アミティ町田けやき | 東京都町田市原町田４丁目２８番１号町田市立国際版画美術館内 | 21846 | 0.045454547
日立国際電気グループ労働組合連合会 | 東京都小平市御幸町３２番地 | 21846 | 0.032258064
株式会社日立国際電気 | 東京都港区西新橋２丁目１５番１２号 | 21846 | 0.10714286
(5 rows)
Time: 3.627 ms
pg_bigmでの全文検索
pg_trgmという拡張機能もあるのですが、素のままでは日本語対応をしていないので、手軽にできるpg_bigmを採用。200ミリ秒なので、件数が大量でなければこれでも十分よいというところです。
test=# select name, address, bigm_similarity(search, '国立国会図書館千代田区永田町１丁目１０−１') from company where search =% '国立国会図書館千代田区永田町１丁目１０−１' order by bigm_similarity(search, '国立国会図書館千代田区永田町１丁目１０−１') desc limit 5;
name | address | bigm_similarity
----------------+------------------------------------+-----------------
国立国会図書館 | 東京都千代田区永田町１丁目１０－１ | 0.76
参議院 | 東京都千代田区永田町１丁目７－１ | 0.45454547
内閣官房 | 東京都千代田区永田町１丁目６－１ | 0.45454547
内閣府 | 東京都千代田区永田町１丁目６－１ | 0.45454547
衆議院 | 東京都千代田区永田町１丁目７－１ | 0.45454547
(5 rows)
Time: 202.458 ms
まとめ
候補が絞り込めたので、これに対して類似度の計算をします。これは、自力で文字列の距離関数などを組合わせてつくるか、機械学習の技術をつかってもいいかもしれません。データのばらつきがありすぎると、機械学習ではおもったようなスコアをつくるのが難しいかもしれません。