pysparksparkfuzzy-matchinglshentity-resolutiondata-engineering

PySpark 대규모 퍼지 매칭 — Cross Join 없이 수억 건 레코드 링크

이름·주소가 조금씩 다른 수억 건의 레코드를 어떻게 매칭하는가. O(n²) cross join 의 벽, 블로킹 전략, 그리고 MinHash LSH 로 유사 후보만 추려 근사 조인하는 실전 패턴을 PySpark 코드와 함께 정리합니다.

Data Dynamics2026年6月5日10 min read

This post is not yet translated. The original Korean version is shown below.

"같은 사람인데 이름이 조금씩 다른" 레코드를 합치는 일 — 고객 마스터 통합, 중복 거래처 정리, 부정거래 탐지 — 은 데이터 엔지니어링의 단골 난제입니다. 정확히 일치하면 조인하면 그만이지만, "김철수" 와 "김 철수", "Seoul" 과 "서울특별시" 처럼 유사하지만 다른 값을 매칭해야 합니다.

문제는 규모입니다. 100만 건끼리 모든 쌍을 비교하면 5천억 번의 비교가 필요합니다(O(n²)). 수억 건이면 cross join 으로는 우주가 끝나도 안 끝납니다. 이 글은 이 벽을 넘는 두 가지 핵심 기법 — 블로킹(Blocking) 과 LSH(Locality Sensitive Hashing) — 를 PySpark 로 구현하는 법을 정리합니다.

1. 문제의 본질 — O(n²) 의 벽

100만 × 100만 = 1조 쌍 → 각 쌍마다 유사도 계산 → 현실적으로 불가능

퍼지 매칭의 모든 기법은 결국 하나의 목표를 향합니다 — "비교할 필요 없는 쌍을 비교 후보에서 빼는 것". 전부 비교(cross join)하지 않고, 닮았을 가능성이 있는 쌍만 추려서 그 안에서만 정밀 비교합니다.

접근	비교 쌍 수	비고
Cross join (전수)	O(n²)	불가능
블로킹	블록 내부만	키 설계가 핵심
LSH	유사 버킷만	근사, 임계값 튜닝

2. 1단계 — 블로킹(Blocking)

가장 단순하고 강력한 기법. "같은 블록 키를 가진 것끼리만 비교" 합니다. 예를 들어 "성씨 + 생년" 이 같은 사람끼리만 비교하면, 비교 대상이 극적으로 줄어듭니다.

from pyspark.sql import functions as F
 
# 블로킹 키 생성: 성씨 첫 글자 + 생년 + 우편번호 앞 3자리
df = df.withColumn("block_key",
    F.concat_ws("|",
        F.substring("name", 1, 1),
        F.year("birth"),
        F.substring("zipcode", 1, 3)))
 
# 같은 블록 안에서만 self-join (cross join 회피)
a = df.alias("a")
b = df.alias("b")
candidates = (a.join(b, "block_key")
    .where("a.id < b.id"))      # 중복 쌍·자기자신 제거

장점	한계
단순, 빠름	블록 키가 다르면 진짜 매칭도 놓침(recall↓)
비교 쌍 급감	블록이 크면(스큐) 그 안은 다시 O(k²)

핵심 트레이드오프: 블록 키가 느슨하면 블록이 커져 비교가 많아지고, 빡빡하면 진짜 매칭을 놓칩니다. 보통 여러 블로킹 키를 만들어 union(multi-pass blocking)해서 recall 을 높입니다.

블록 스큐 주의

흔한 성씨(김)는 거대 블록을 만들어 그 안에서 다시 O(n²) 가 됩니다. 블록 크기를 모니터링하고, 큰 블록은 키를 더 세분화하세요. (스큐 일반론은 별도 글 "PySpark 데이터 스큐 완전 정복" 참고.)

3. 2단계 — MinHash LSH 로 유사 후보 추리기

블로킹은 "정확히 같은 키"가 전제입니다. 오타·표기 변형까지 잡으려면 LSH 가 필요합니다. LSH 의 아이디어: 유사한 항목이 높은 확률로 같은 해시 버킷에 떨어지게 하는 해시 함수를 써서, 같은 버킷 안에서만 비교합니다.

문자열 유사도(자카드)에는 MinHash LSH 를 씁니다. Spark MLlib 에 내장되어 있습니다.

단계 ① 텍스트 → 특징 벡터 (n-gram)

from pyspark.ml.feature import RegexTokenizer, NGram, HashingTF
 
# 문자 단위 정규화
df = df.withColumn("clean", F.lower(F.regexp_replace("name", "\\s+", "")))
 
# 문자 3-gram 생성 (예: "김철수" → ["김철수"] 등 — 한글은 자소/문자 단위 선택)
df = df.withColumn("chars", F.split("clean", ""))
ngram = NGram(n=3, inputCol="chars", outputCol="ngrams")
df = ngram.transform(df)
 
# n-gram → 희소 벡터
tf = HashingTF(inputCol="ngrams", outputCol="features", numFeatures=1 << 18)
df = tf.transform(df)

단계 ② MinHashLSH 학습·적용

from pyspark.ml.feature import MinHashLSH
 
mh = MinHashLSH(inputCol="features", outputCol="hashes", numHashTables=5)
model = mh.fit(df)
 
# 자기 자신 데이터셋 내 근사 유사 쌍 찾기 (자카드 거리 임계값 0.3 이하 = 유사도 0.7 이상)
pairs = model.approxSimilarityJoin(df, df, threshold=0.3, distCol="jaccard_dist")
 
candidates = (pairs
    .where("datasetA.id < datasetB.id")   # 중복·자기자신 제거
    .select(
        F.col("datasetA.id").alias("id_a"),
        F.col("datasetB.id").alias("id_b"),
        F.col("jaccard_dist")))

approxSimilarityJoin 은 cross join 없이, LSH 버킷이 겹치는 쌍만 후보로 내놓습니다. numHashTables 를 늘리면 recall(놓침 감소)이 올라가지만 비용도 늘어납니다.

파라미터	효과
`numHashTables`	↑ recall, ↑ 비용
`threshold` (거리)	↓ 일수록 엄격(정밀), 후보↓
`numFeatures`	해시 충돌↓, 메모리↑

4. 3단계 — 후보 정밀 비교(스코어링)

블로킹/LSH 로 추린 소수의 후보 쌍에 대해서만 비싼 정밀 유사도를 계산합니다. 이제 쌍이 적으므로 UDF/Pandas UDF 를 써도 됩니다.

# 여러 필드의 가중 유사도 (Levenshtein 등 내장 + 커스텀)
scored = candidates.join(df.alias("ra"), F.col("id_a") == F.col("ra.id")) \
                   .join(df.alias("rb"), F.col("id_b") == F.col("rb.id")) \
    .withColumn("name_sim",
        1 - F.levenshtein("ra.name", "rb.name") /
            F.greatest(F.length("ra.name"), F.length("rb.name")))
 
matches = scored.withColumn("score",
    0.6 * F.col("name_sim") + 0.4 * (1 - F.col("jaccard_dist"))
).where("score >= 0.85")

정밀 비교에 복잡한 로직이 필요하면 벡터화된 pandas_udf 가 적합합니다(별도 글 "PySpark UDF가 느린 이유와 Pandas UDF" 참고). 핵심은 이 단계에 들어오는 쌍이 이미 충분히 적다는 것입니다.

5. 전체 파이프라인

[원본 수억 건]
     │  ① 정규화 (소문자·공백·특수문자 제거)
     ▼
[블로킹 또는 LSH] ── cross join 회피, 유사 후보만 ──> [후보 쌍 (수백만)]
     │  ③ 정밀 스코어링 (Levenshtein·가중합)
     ▼
[매칭 쌍 (score ≥ 임계값)]
     │  ④ 군집화 (연결된 매칭을 한 엔티티로)
     ▼
[통합 엔티티]

마지막 ④단계 — "A=B, B=C 면 A=C" 로 매칭을 군집(연결 요소)으로 묶는 것 — 은 그래프 문제입니다. GraphFrames 의 Connected Components 로 푸는 법은 별도 글 "PySpark GraphFrames 엔티티 해소"에서 다룹니다.

6. 정밀도 vs 재현율 튜닝

퍼지 매칭은 놓침(recall) 과 오매칭(precision) 의 줄다리기입니다.

목표	조정
놓침 줄이기(recall↑)	블로킹 키 여러 개 union, `numHashTables`↑, threshold 완화
오매칭 줄이기(precision↑)	정밀 스코어 임계값↑, 다중 필드 가중
비용 줄이기	블록 크기 제한, threshold 엄격, 정규화 강화

실무 권장: 블로킹으로 1차 후보를 좁히고, LSH 로 변형까지 커버하고, 정밀 스코어로 마무리하는 3단 구성이 비용·품질 균형이 가장 좋습니다. 한 기법만으로 다 하려 하지 마세요.

7. 흔한 함정

함정	결과
정규화 생략	표기 차이로 다 다른 값 취급
cross join 으로 정밀 비교	O(n²) 폭발
단일 블로킹 키	recall 급락(키 다르면 놓침)
거대 블록 방치	블록 내 O(k²) 스큐
`numHashTables` 과대	후보·비용 폭증

8. 정리

단계	도구	목적
정규화	`lower`, `regexp_replace`	표기 통일
후보 축소	블로킹 / MinHash LSH	cross join 회피
정밀 비교	Levenshtein, Pandas UDF	후보 스코어링
군집화	GraphFrames CC	엔티티 통합

대규모 퍼지 매칭의 핵심은 단 하나 — "모든 쌍을 비교하지 않는 것" 입니다. 블로킹으로 명확한 후보를, LSH 로 변형까지 포함한 후보를 추린 뒤, 그 소수에만 비싼 정밀 비교를 적용합니다. O(n²) 를 정면 돌파하려 들면 어떤 클러스터로도 못 풀지만, 후보를 영리하게 줄이면 수억 건도 현실적인 시간에 매칭할 수 있습니다.

이 글은 Spark 3.5 + MLlib 기준으로 작성되었습니다. 대규모 고객 마스터 통합·레코드 링크·중복 정리 파이프라인이 필요하시면 언제든 문의해 주세요.

— Data Dynamics 엔지니어링 팀