エンティティ解決を用いたスクレイピングデータの重複排除方法

TL;DR:

• 四つのリストページが71件のレコードを返し、66のエンティティに解決され、5つの真の重複グループが存在しました — 同じ本が両方のカテゴリリストとページネートされたカタログに現れました。
• 比較の前に正規化することが、正確なキーを機能させる要因です：ケース折り畳み、Unicode正規化、句読点除去が、一つのタイトルの三つの表現を一つのキーに変換します。
• ブロッキングは測定可能であり、曖昧ではありません。66のエンティティは2,145の全ペア比較になります；4文字のブロックキーがそれを48ブロックで154に削減し、92.8%の削減を実現します。
• スコアリングはしきい値の前に決めます。同じペアのタイトルがratioで87.8、token_set_ratioで100.0のスコアを獲得しました。
• しきい値バンドはあなたのデータ上で測定できます：無関係なライブタイトルは63.4に達し、一つの本の三つの表現が93.5以上のスコアを付けました。
• 単一のクリーンカタログでは、正確なキーがすべての重複を捕らえ、あいまい一致は90を超えるものを見つけられませんでした — あいまいはソース全体でその地位を獲得しますが、一つの中ではそうではありません。
• この情報を調整するためのマルチソースレコードを収集してください。Scrapeless無料プラン。

一つのサイトをスクレイピングすると重複は稀です。同じカタログをカテゴリリストとページネートインデックスを通して、または二つの小売業者で同じ製品をスクレイピングすると、重複が構造的に発生します — クローラーは同じアイテムを二つのルートで訪れ、知る方法がありませんでした。

エンティティ解決は、これらのレコードを再び物に戻すステップです。抽出後、ストレージの前に実行され、ほとんどが安価な決定の連続です：同じ文字列と見なされるもの、同じレコードと見なされるもの、そしてどのバージョンが生き残るか。

以下のすべての数は、四つのライブリストページから取得した71件のレコードのコレクションに由来します。

Pipeline at a Glance

流れは正規化 → 正確なキー → ブロック → あいまい比較 → マージです。各ステージは次のものよりも安価なので、それぞれは次が行わなければならない作業を減らすために存在します。

Stage 1: 正規化前に比較する

同じ製品を説明する二つのレコードは、バイト同一の文字列を持つことは稀です。ケース、アクセント、句読点がすべて変化します。

import re
import unicodedata

def norm(text):
    text = unicodedata.normalize("NFKD", text or "").casefold()
    text = re.sub(r"[^a-z0-9 ]+", " ", text)
    return re.sub(r"\s+", " ", text).strip()

NFKDパスは見た目以上に重要です。Unicode正規化附録は複数の形式を定義しており、互換性分解は、あらかじめ構成されたéと組み合わさったeが等しく比較されるものです — この二つのスペルは視覚的には同一ですが、バイト上では異なる、これは出力中で誰も見えない重複を生み出すケースです。

小文字化ではなくケース折り畳みが一致の相対役であり、W3C文字モデルの正規化に関するノートは、非ASCIIテキストに対してなぜ二つが異なるのかの参照です。

収集されたレコード上では：

[1] collected 71 records from 4 listing pages
    raw distinct titles        66
    normalised distinct titles 66

ここでは同一です。なぜならこのカタログがクリーンだからです。それは仮定するのではなく知っておく価値があります — 比較を実行することで、正規化があなたのデータで何らかの作業を行っているかどうかを確認できます。

Stage 2: 正確なキーでグループ化する

正規化されたキーを使用して、最初のパスはグループ化であり、比較ではありません。それはO(n)であり、完全に一致するすべての重複をキャッチします。

from collections import defaultdict

by_key = defaultdict(list)
for record in records:
    by_key[norm(record["title"])].append(record)

dupe_groups = {k: v for k, v in by_key.items() if len(v) > 1}

[2] exact-key duplicates: 5 group(s), 10 records collapse to 5
    Sharp Objects                        x2  ['mystery', 'catalogue1']
    In a Dark, Dark Wood                 x2  ['mystery', 'catalogue2']
    In Her Wake                          x2  ['catalogue2', 'thriller']
    The Elephant Tree                    x2  ['catalogue2', 'thriller']
    Behind Closed Doors                  x2  ['catalogue2', 'thriller']

重複がどこから来ているかに注意してください：すべてのグループは二つの異なるリストページにまたがっています。単一のページには重複が含まれていません。それが一般的な形です — 重複はクローラーの特性であり、ページの特性ではないので、常に一つのリストを読んでいるスクレイパーは重複を見ず、四つを読むスクレイパーは見ることになります。

ページが安定した識別子を公開している場合は、常にそれをキーとして使用してください。製品ID、ISBN、またはカノニカルURLパスは、タイトルよりも優れています。なぜなら、タイトルはマーケティングコピーであり、製品が変わらなくても変わるからです。発行された識別子スキームは、独立した当事者がアイデンティティに合意できるように存在します — ISBN URN名前空間の仕様は書籍の世界の例であり、スクリプトされたページがそれを公開していれば、すでに一致問題を解決しています。

Stage 3: ペアを比較する前にブロックする

ファジー比較はペアワイズであり、ペアワイズは二次的です。66のエンティティの場合、比較は2,145件; 10,000の場合は約5000万件です。

ブロッキングは、すでに何かを共有するレコードのみを比較することによってフィールドをカットします:

blocks = defaultdict(list)
for entity in merged:
    blocks[norm(entity["title"])[:4]].append(entity)

blocked_pairs = sum(len(b) * (len(b) - 1) // 2 for b in blocks.values())

[4] 66 entities
    all-pairs comparisons  2145
    blocked on 4-char key  154 across 48 blocks
    reduction              92.8%

取引は明示的です: タイトルが異なるレコードは決して比較されないため、あまりにも攻撃的なブロックキーは実際のマッチを隠してしまいます。最初の4文字でブロックすると、記事が移動したため、The Elephant TreeとElephant Treeのペアを見逃します。一般的な回答は、ソートされたトークンのプレフィックス、数値識別子、または複数のキーで同時にブロックし、候補ペアの和集合を取得することです。

ステージ4: ファジーマッチングと必要ない場合

このカタログに対してファジーパスを実行した結果、正直に報告する価値のある結果が得られました:

[5] fuzzy near-duplicates above 90 (token_sort_ratio)
    brute force 2145 pairs in 2.5 ms -> 0 candidate(s)

何もありません。正規化と正確なグループ化の後、一つのクリーンなカタログには近似重複が残っていませんでした。ここでのファジーパスは、決して発火しないコードになるでしょう。

ファジーマッチングは、異なる形式のタイトルを持つソースからレコードが到着する時にその場所を得ます。1つの実際のタイトルを取り、それを3つの異なるリスティングが扱う方法で描写します:

from rapidfuzz import fuzz

VARIANTS = [
    "A Study in Scarlet (Sherlock Holmes #1)",
    "A Study In Scarlet - Sherlock Holmes Book 1",
    "A Study in Scarlet, Sherlock Holmes #1 [Paperback]",
]
keys = [norm(v) for v in VARIANTS]
print("distinct exact keys:", len(set(keys)))
for i in range(len(keys)):
    for j in range(i + 1, len(keys)):
        print(f"ratio {fuzz.ratio(keys[i], keys[j]):5.1f} | "
              f"token_sort {fuzz.token_sort_ratio(keys[i], keys[j]):5.1f} | "
              f"token_set {fuzz.token_set_ratio(keys[i], keys[j]):5.1f}")

distinct exact keys: 3
ratio  93.5 | token_sort  93.5 | token_set 100.0
ratio  87.8 | token_sort  87.8 | token_set 100.0
ratio  85.1 | token_sort  82.8 | token_set  93.5

1冊の本に対して3つのキー — エクザクトキーのステージではここでは助けになることはできません。そして、スコアラーは閾値よりも回答を変えることが多いです。ratioは文字列をシーケンスとして比較し、[Paperback]の接尾辞によって引きずり下ろされます; token_set_ratioはトークンのセットを比較するため、追加の単語は何のコストもかからず、最初の2つのバリエーションはクリーンな100をスコアします。

複数のソースからのレコードを調整しますか？ Scrapelessの無料プラン は、重複を表示する2番目のカタログを収集するのに十分なリクエストをカバーします。

自分のデータから閾値を選ぶ

閾値は、測定された分離に対してのみ防御可能です。ここで2つの数が境界を設定します:

これら2つの間は、このデータにおいてセットをクリーンに分けるものです。この方法は一般化可能です: 知られているマッチのサンプルと知られていないノンマッチのサンプルをスコアし、分布が重なり合うのを止める場所を見て、そのギャップに閾値を置きます。記事からコピーされた単一のグローバル数値は、他の人のデータについての推測です。

分布が重なり合う場合、正直な答えはレビューのバンドです — 上の上限を超えたものは自動マージし、下の下限を下回ったものは自動拒否し、それらの間に収まるものをキューに入れます。統計的レコードリンクは数十年にわたってこの問題に対処してきた方法であり、アメリカ国勢調査局のレコードリンク研究は確率的フレーミングに関する標準的なリファレンスです。

ステージ5: 生存者効果

2つのレコードが同じであると決定することは、マージされたレコードが何を示すかという問題を残します。負けた方を破棄することは、マッチが発生した証拠を静かに捨ててしまいます。

def survivor(group):
    best = sorted(group, key=lambda r: (r["href"] is None, len(r["href"] or "")))[0]
    return {**best,
            "seen_in": sorted({g["source"] for g in group}),
            "prices": sorted({g["price"] for g in group})}

[3] 71 records -> 66 entities
    merged example: 'Sharp Objects' seen_in=['catalogue1', 'mystery'] prices=['£47.82']

そのマージされたレコードには2つの特性が重要です。seen_inは出所を保持しているので、間違ったマージはその後追跡可能であり、目に見えなくなることはありません。そして、pricesは単一の値ではなく集合です: 2つのソースが異なる場合、その不一致が興味深い部分であり、それを最初にソートされたレコードに圧縮するとそれを破壊します。

フィールドレベルのルールは、全レコードの勝者に勝ります。最長の説明、最も最近のタイムスタンプ、最も完全なレコード、最も信頼のあるソース — レコードごとではなくフィールドごとに選ばれる — これはマージが1つのソースのギャップを引き継がないようにします。

これはパイプラインのどこに位置するか

重複排除は変換ステップに属し、抽出の後、書き込みの前です。これを早めに実行すると、まだ解析していない文字列を正規化することになります; 後で実行すると、重複がすでにテーブルに存在しており、修正がマイグレーションになります。
同じ製品を複数のソースから収集することが、そもそもそのステージを必要とする理由です — 競争力のある価格パイプラインはまさにその形をしており、ユニバーサルスクレイピングAPIは、どれか一つのソースがクライアントサイドでレンダリングされても、記録の形状を一貫して保つ役割を果たします。価格設定は、追加のソースのコストを示しています。

結論

エンティティ解決は、1つの高コストなステージの前に4つの低コストなステージがあるプロセスです。正規化は、同じ文字列とみなされるものを決定し、厳密なグループ化が同意するすべてをキャッチします — ここでは5つのグループと10のレコードです — ブロッキングは、比較が不要なペアの92.8%を削除し、残ったものだけがファジースコアラーに到達します。

2つの発見は、自分のデータに持ち帰る価値があります。スコアラーはしきい値よりも重要です：同じペアに対して87.8と100.0の違いがあります。そして、数を選ぶ前に分離を測定してください。ここで選択を明確にした63.4から93.5のギャップは、このカタログの特性であり、定数ではありません。

複数のソースからのレコードを照合する準備はできましたか？ Scrapelessの無料プランから始めましょう そして、重複を可視化する2番目のカタログを収集します。

FAQ

Q: スクレイピングしたデータから重複を削除するにはどうすればいいですか？

キー フィールドを正規化し、それに基づいてグループ化し、各グループをマージします。大文字小文字の折りたたみ、ユニコード NFKD 正規化、句読点の除去は、視覚的に同一の文字列を1つのキーに変換します。そして、グループ化はペアワイズではなくO(n)です。上記の71レコードでは、類似性スコアリングなしで10レコードを5エンティティにまとめました。通過したもののみに対してファジーマッチングを利用してください。

Q: エンティティ解決とは何ですか？

どのレコードが同じ現実の物事を指しているのかを決定し、それらを1つの標準レコードに統合することです。重複排除は、単一のソース内での同じ操作ですが、この用語は通常、共有識別子が存在せず、フィールドの類似性から決定を下さなければならない、より難しいクロスソースの場合に予約されます。

Q: ブロッキングとは何で、なぜ重要なのですか？

安価なキーを共有しているレコードのみを比較するため、ペアワイズのステージがすべてのものに対して実行されることはありません。66エンティティには2,145の可能なペアがあり、4文字プレフィックスキーによりそれを154まで削減し、92.8%の削減を達成しました。代償として、キーが異なるレコードは比較されないため、ブロックキーが厳しすぎるとマッチを静かに隠してしまいます。

Q: どのファジーマッチングスコアラーを使用すべきですか？

token_set_ratio は、異なるソースから追加の単語を拾うタイトルに対して有効です。これはトークンセットを比較し、余分な部分を無視するためです — 同じペアに対してratio が87.8を与えたのに対し、100.0をスコアしていました。位置や順序が意味を持つ場合、例えばコードや住所ではratio を使用してください。選択の前に、自分のデータから知られたマッチに対して両方をテストしてください。

Q: どの類似性しきい値を設定すべきですか？

コピーするのではなく、測定してください。既知のマッチと既知の非マッチのサンプルにスコアを付け、分布が重ならない場所にしきい値を設定します。ここでは異なる本の間の最高スコアが63.4で、1冊の本のレンダリングの中で最低スコアが93.5でしたので、その範囲内のものであれば機能しました。2つが重なる部分では、自動マージは上に、自動拒否は下にし、それ以外の部分はレビューのためにキューに入れます。

Q: どのレコードがマージを生き残るべきですか？

レコードごとではなく、フィールドごとに選択してください。最も長い説明、最も最近の価格、最も完全な住所を取得し、出所を保持します — 上のマージエンティティはseen_inと観察された価格の完全なセットを保持します。ソースリストを保持することで、不適切なマージを追跡可能にします。すべての観察された価格を保持することで、ソース間の対立が保存され、これはしばしば望んでいた信号となります。