複数の場所から収集する場合、あるいは一つの場所から複数回収集する場合、重複がついて回る。同じ商品が三つのマーケットプレイスにわずかに異なる三つの名前で掲載されている。同じ会社があるレジストリでは「Acme Widgets Ltd」、別のレジストリでは「ACME WIDGETS LIMITED」と表記されている。クロール中にページネーションがずれたため、あるいは一方のリンクにトラッキングパラメータが付いていて他方には付いていなかったために、同じ掲載が二重に現れる。
放置すれば、重複は件数を水増しし、履歴をレコード間に分断させ、その上に構築されるあらゆる指標を静かに損なう。本ガイドでは、識別子の正規化、強いキーによる優先マッチング、大規模な状況下での安全なファジーマッチング、クラスタリング、そしてどのバージョンのレコードを残すかの決定という観点から、重複の解消方法を扱う。
要点
- ほとんどの重複は、ファジーマッチングを行う前に識別子を正規化することで捕捉できる。正規化されたURL、検証済みの商品コード、クレンジングされた会社名がそれにあたる。
- まず強い識別子でマッチングする。有効なバーコードやレジストリ番号は、どれだけ名前が似ていてもそれに勝る。
- すべてのレコードを他のすべてのレコードと比較してはならない。100万件のレコードは約5000億組のペアを生む。ブロッキングによってそれを扱いやすい規模に減らせる。
- どちらの誤りがより痛手かを決める。あるタスクでは誤ったマージが見逃した重複より悪く、別のタスクではその逆になる。
- 由来(provenance)を保持する。マージされたレコードは、それが由来するすべてのソースを把握し続けるべきである。
三種類の重複
| 種類 | 例 | 捕捉方法 |
|---|---|---|
| 収集の重複 | 同じURLが二回取得された、あるいは結果ページが重なっていた | 正規化されたURLまたはソース識別子 |
| 同一エンティティ、異なるソース | 一つの商品が三つのマーケットプレイスに掲載されている | 共有された識別子、その後ファジーマッチング |
| 準重複コンテンツ | 同じ記事がわずかな編集を加えて配信されている | 大規模な変更検知で扱われるコンテンツ類似度 |
本ガイドは前二者に焦点を当てる。目標は、実世界の商品、会社、掲載につきレコードを一つにすることである。
ステップ1: 識別子を正規化する
正規化は低コストであり、どんな巧妙なマッチングよりも多くの重複を捕捉する。
URL。 同じページが多くのURLで届く。ホストを小文字化し、www.を除去し、utm_*やgclid、fbclidといったトラッキングパラメータを削除し、残ったクエリパラメータをソートし、末尾のスラッシュを取り除く。http://www.Shop.com/p/123/?utm_source=x&b=2&a=1とhttps://shop.com/p/123?a=1&b=2は同じキーになる。
商品コード。 Global Trade Item Number(UPCやEANバーコードの背後にある番号)にはチェックデジットが含まれており、これによって信頼する前に誤入力やスクレイピングミスのコードを弾くことができる。GS1の方式では、チェックデジットに隣接する桁から始めて3、1、3、1というように重みを付け、合計し、次の10の倍数に切り上げるために必要な数を求める。GS1自身の計算例では、11桁の本体61414121022のチェックデジットは0になる。有効なコードは14桁にパディングし、同じコードの13桁版と14桁版が同じものとして比較されるようにする。
会社名。 大文字小文字とアクセント記号を統一し、句読点を除去し、Ltd、Limited、Inc、GmbH、SAといった法人格の接尾辞を比較前に取り除く。「Acme Widgets Ltd.」も「ACME WIDGETS LIMITED」もどちらもacme widgetsになる。会社にレジストリ番号やLegal Entity Identifierがある場合は、名前の代わりにそれを使う。会社を識別子に解決する方法についてはサプライヤーの公開情報を監視するで扱っている。
ステップ2: まず強いキーでマッチングする
識別子が正規化されれば、それらの完全一致は高速かつ信頼性が高い。同じ有効なバーコードを持つ二つのレコードは同じ商品である。同じ正規化URLを持つ二つのレコードは同じページである。同じレジストリ番号を持つ二つの会社は、名称が何であれ同じ会社である。
構造化データもここで役立つ。多くの商品ページはバーコードやSKUをJSON-LDで公開しており、これは表示ページからスクレイピングするよりもはるかに信頼できる。詳しくはHTMLの解析をやめるを参照。
ステップ3: ファジーマッチングは、ただしブロック内でのみ
共有識別子を持たないレコードは、名前、住所、説明文でのファジーマッチングが必要になる。ここでの落とし穴は規模である。すべてのレコードを他のすべてのレコードと比較すると、データセットの規模の二乗で計算量が増える。100万件のレコードはおよそ5000億組のペアを生む。
ブロッキングがこれを解決する。真のマッチがほぼ必ず共有する安価なキー、例えば国と正規化された名前の最初の単語、あるいはブランドと商品カテゴリでレコードをグループ化し、各グループ内でのみ比較する。良いブロッキングキーは、真のマッチをほとんど失うことなく比較回数を桁違いに削減する。時折ブロックをまたいでペアをサンプリングし、何を失っているか確認する。
ブロック内では、文字列類似度スコアと閾値がマッチを決定する。厳しめの0.9前後から始め、緩めた設定が何をマージすることになるかを確認してからのみ緩める。
ステップ4: クラスタリングは慎重に
マッチはペア単位だが、エンティティは群である。union-find構造はペアを効率的にクラスタへと変換する。しかしこれはリスクも伴う。推移性である。AがBとマッチし、BがCとマッチすれば、AとCが何も共有していなくても一緒にまとめられてしまう。弱いマッチの長い連鎖こそが、二つの異なる会社がマージされる原因になる。異常に大きなクラスタに注意し、受け入れる前にレビューすること。
パイプライン全体は小さなモジュールに収まる。
import re
import unicodedata
from collections import defaultdict
from difflib import SequenceMatcher
from urllib.parse import urlsplit, urlunsplit, parse_qsl, urlencode
LEGAL_SUFFIXES = {"ltd", "limited", "inc", "incorporated", "llc", "gmbh", "ag", "sa", "sas",
"srl", "bv", "nv", "plc", "co", "corp", "corporation", "company", "oy", "ab"}
TRACKING = re.compile(r"^(utm_|gclid$|fbclid$|mc_|ref$|ref_)")
def gtin_valid(code):
"""GS1 check digit: weights 3,1,3,... from the digit next to the check digit."""
digits = re.sub(r"\D", "", str(code or ""))
if len(digits) not in (8, 12, 13, 14):
return False
body, check = digits[:-1], int(digits[-1])
total = sum(int(d) * (3 if i % 2 == 0 else 1) for i, d in enumerate(reversed(body)))
return (10 - total % 10) % 10 == check
def norm_name(name):
text = unicodedata.normalize("NFKD", name or "").encode("ascii", "ignore").decode().lower()
tokens = [t for t in re.findall(r"[a-z0-9]+", text) if t not in LEGAL_SUFFIXES]
return " ".join(tokens)
def norm_url(url):
parts = urlsplit((url or "").strip())
query = urlencode(sorted((k, v) for k, v in parse_qsl(parts.query) if not TRACKING.match(k.lower())))
host = parts.netloc.lower().removeprefix("www.")
return urlunsplit(("https", host, parts.path.rstrip("/") or "/", query, ""))
def similar(a, b):
return SequenceMatcher(None, a, b).ratio()
def cluster(records, threshold=0.9):
"""Group records that refer to the same entity. Returns lists of record indexes."""
parent = list(range(len(records)))
def find(i):
while parent[i] != i:
parent[i] = parent[parent[i]]
i = parent[i]
return i
def union(i, j):
parent[find(i)] = find(j)
# 1. Exact matches on strong identifiers.
by_key = defaultdict(list)
for i, r in enumerate(records):
if gtin_valid(r.get("gtin")):
by_key["gtin:" + re.sub(r"\D", "", r["gtin"]).zfill(14)].append(i)
if r.get("url"):
by_key["url:" + norm_url(r["url"])].append(i)
for ids in by_key.values():
for j in ids[1:]:
union(ids[0], j)
# 2. Fuzzy name match, only within a cheap blocking key.
blocks = defaultdict(list)
for i, r in enumerate(records):
name = norm_name(r.get("name"))
if name:
blocks[(r.get("country") or "", name.split()[0])].append((i, name))
for members in blocks.values():
for a in range(len(members)):
for b in range(a + 1, len(members)):
if similar(members[a][1], members[b][1]) >= threshold:
union(members[a][0], members[b][0])
groups = defaultdict(list)
for i in range(len(records)):
groups[find(i)].append(i)
return list(groups.values())小さなテストセットでは、これは「Acme Widgets Ltd」と「ACME WIDGETS LIMITED」、そして会社の正規化URLを共有する第三のレコードをマージし、バーコードが先頭の0のみ異なる二つの靴の掲載をマージし、そして意図的に、アメリカ合衆国の「Acme Widget Co」を別のエンティティとして残す。ブロッキングキーに国が含まれているためである。この最後の判断が正しいかどうかは、あなたのデータ次第であり、それこそが次のステップの要点である。
ステップ5: どのレコードを残すか決める
クラスタは一つのエンティティの複数のバージョンであり、それを一つにする必要がある。よく使われる生存ルールは以下の通りである。
- 最も完全なものが勝つ、フィールドごとに。一つのレコード全体をそのまま選ぶのではなく、各フィールドについて最良のソースを持つ非空の値を採用する。
- 最新のものが勝つ、価格や在庫状況のように変化する値については。
- 最も信頼できるソースが勝つ、正式名称や住所のような値については。例えばディレクトリよりもレジストリを優先する。
どの方法を選ぶにせよ、マージされたレコードにはすべてのソース識別子とURLを、それぞれが観測された時刻とともに保持する。マージが誤りだと判明したとき、由来こそが再分割を可能にするものである。
適合率と再現率を測定する
エンティティ解決には二種類の誤りがあり、どちらが重要かはタスクによって異なる。
| 誤り | 何が起きるか | 最も悪影響を受けるもの |
|---|---|---|
| 誤ったマージ | 二つの実在するエンティティが一つになる | 会社データや人物に関連するデータ、コンプライアンス、法的な事柄全般 |
| 見逃した重複 | 一つのエンティティが複数のレコードのまま残る | 件数、市場規模の算定、価格比較 |
数百組の候補ペアを手作業でラベル付けし、両方の誤り率を測定し、自分が重視する誤りに対して閾値とブロッキングキーを調整する。B2Bリードデータベースの構築にあるようなB2Bリードデータベースは、通常、見逃した重複を二つの会社が誤って融合されるよりもはるかに許容できる。リアルタイムの競合価格フィードのような価格比較フィードは逆で、見逃した重複は一つの商品が二つの価格で二重に表示されることを意味する。
早期に、ソースでデータクレンジングする
重複は精度を損なう前にコストを発生させる。同じ正規化URLを繰り返し取得するたびに、無駄に帯域幅やクレジットが消費される。だからこそURLの正規化は、ウェアハウスだけでなくクローラーのフロンティアに組み込まれるべきである。単位コストへの影響についてはクリーンなレコード1件あたりのコストで扱っている。
結論
重複排除はほとんどが正規化である。正規化されたURL、検証済みの商品コード、クレンジングされた会社名が、どんなファジーマッチングを実行するよりも先に大半の重複を捕捉する。その後、強いキーでマッチングし、ブロック内でのみファジーマッチングを行い、長い連鎖に注意しながらクラスタリングし、マージされたすべてのレコードに由来を保持し、自分のユースケースにとって重要な誤りを測定する。
うまくやれば、実世界の一つのものが一つのレコードになり、その完全な履歴が付随する。うまくやらなければ、データセットは大きく見えると同時に、信頼性が低くなる。
出典と参考文献
- GS1 US, チェックデジットを手動で計算する方法.
- GLEIF, Open LEIデータ.