여러 곳에서 수집하거나, 한 곳에서 여러 번 수집하면 중복이 뒤따른다. 동일한 제품이 세 개의 마켓플레이스에 조금씩 다른 이름으로 등장한다. 동일한 회사가 한 레지스트리에서는 “Acme Widgets Ltd”로, 다른 레지스트리에서는 “ACME WIDGETS LIMITED”로 나타난다. 동일한 목록이 크롤링 중 페이지네이션이 바뀌었거나, 하나의 링크에는 추적 파라미터가 붙어 있고 다른 하나에는 붙어 있지 않아서 두 번 나타난다.
방치하면 중복은 카운트를 부풀리고, 히스토리를 여러 레코드로 분산시키며, 그 위에 구축된 모든 지표를 조용히 왜곡시킨다. 이 가이드는 식별자 정규화, 강한 키 우선 매칭, 대규모에서의 안전한 퍼지 매칭, 클러스터링, 그리고 어떤 버전의 레코드를 남길지 결정하는 방법을 다룬다.
핵심 요약
- 대부분의 중복은 퍼지 매칭을 실행하기 전에 식별자를 정규화하는 것으로 잡힌다: 표준화된 URL, 검증된 제품 코드, 정리된 회사명.
- 강한 식별자로 먼저 매칭한다. 유효한 바코드나 레지스트리 번호는 아무리 이름이 유사해도 그보다 우선한다.
- 모든 레코드를 다른 모든 레코드와 비교하지 않는다. 100만 개의 레코드는 약 5,000억 개의 페어를 만들며, 블로킹은 이를 다룰 수 있는 수준으로 줄여준다.
- 어느 오류가 더 치명적인지 결정한다. 어떤 작업에서는 잘못된 병합이 놓친 중복보다 더 나쁘고, 다른 작업에서는 반대다.
- 출처를 유지한다. 병합된 레코드는 여전히 자신이 어디에서 왔는지 모든 소스를 알고 있어야 한다.
세 종류의 중복
| 종류 | 예시 | 잡는 방법 |
|---|---|---|
| 반복 수집 | 동일한 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을 가진 두 레코드는 동일한 페이지다. 동일한 레지스트리 번호를 가진 두 회사는 이름이 무엇이든 동일한 회사다.
구조화된 데이터도 여기서 도움이 된다. 많은 제품 페이지가 JSON-LD로 바코드와 SKU를 게시하는데, 이는 보이는 페이지에서 스크래핑하는 것보다 훨씬 신뢰할 수 있다. HTML 파싱을 멈춰라를 참고하라.
3단계: 퍼지 매칭, 단 블록 내에서만
공유 식별자가 없는 레코드는 이름, 주소, 설명에 대한 퍼지 매칭이 필요하다. 함정은 규모다. 모든 레코드를 다른 모든 레코드와 비교하면 데이터셋 크기의 제곱으로 늘어난다: 100만 개의 레코드는 약 5,000억 개의 페어를 만든다.
블로킹이 이를 해결한다. 참 일치가 거의 항상 공유하는 저비용 키(예: 국가와 정규화된 이름의 첫 단어, 또는 브랜드와 제품 카테고리)로 레코드를 그룹화하고, 각 그룹 내에서만 비교한다. 좋은 블로킹 키는 참 일치를 거의 잃지 않으면서 비교 횟수를 몇 자릿수 줄인다. 가끔 블록 간 페어를 샘플링해서 무엇이 손실되는지 확인한다.
블록 내에서는 문자열 유사도 점수와 임계값이 매칭을 결정한다. 엄격하게 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 표준화가 웨어하우스뿐 아니라 크롤러의 프런티어에도 있어야 하는 이유다. 단가에 대한 영향은 클린 레코드당 비용에서 다룬다.
결론
중복 제거는 대체로 정규화의 문제다. 표준화된 URL, 검증된 제품 코드, 정리된 회사명이 어떤 퍼지 매칭이 실행되기 전에 대부분의 중복을 잡아낸다. 그 이후에는 강한 키로 매칭하고, 블록 내에서만 퍼지 매칭하고, 긴 체인을 주시하며 클러스터링하고, 병합된 모든 레코드에 출처를 유지하고, 각 용도에 중요한 오류를 측정한다.
잘 수행하면 실제 세계의 하나의 대상이 완전한 히스토리를 가진 하나의 레코드가 된다. 잘못 수행하면 데이터셋은 더 커 보이면서 동시에 신뢰도는 떨어진다.
출처 및 참고 자료
- GS1 US, 체크 디지트를 수동으로 계산하는 방법.
- GLEIF, Open LEI 데이터.