뉴스 근사 중복 제거: 3-gram 자카드와 IDF로 해결되지 않던 것

온디바이스 AI로 뉴스를 모았습니다. 상위 8건 중 4건이 같은 기사였습니다.

진천군의 스마트돌봄 사업 기사였습니다. v.daum.net, nbnnews, inews365, ccdailynews 네 곳에서 같은 사건을 보도했습니다.

제목이 조금씩 달랐습니다. 그래서 제목을 정규화해 정확히 비교하는 기존 중복 제거로는 잡히지 않았습니다.

단순 자카드와 IDF 가중 구현은 오탐을 임계값으로 가르지 못했습니다. 제목의 선두 어절을 비교하는 주제 게이트를 넣은 뒤 같은 사건을 묶었습니다.

한눈에 보기

문제	온디바이스 AI로 뉴스를 모았습니다.
결정	그래서 문자 3-gram을 썼습니다.
결과	전체 36건이 통과했습니다.
제약	**첫 두 시도의 중간 산출물을 남기지 않았습니다.

어절 대신 문자로 잘랐습니다

첫 결정은 무엇을 비교 단위로 삼을지였습니다.

공백으로 자른 어절이 자연스러운 선택입니다. 한국어에서는 위험합니다.

스마트 돌봄
스마트돌봄

같은 말인데 어절로 자르면 겹치는 토큰이 없습니다. 한국어는 띄어쓰기가 매체마다 다릅니다.

그래서 문자 3-gram을 썼습니다. 세 글자씩 겹쳐 자릅니다.

스마트돌봄 → 스마트 / 마트돌 / 트돌봄
스마트 돌봄 → 스마트 / 마트  / 트 돌 / " 돌봄"

완전히 같지는 않지만 스마트가 겹칩니다. 공백 변형에 견딥니다.

두 제목의 3-gram 집합으로 자카드 유사도를 계산했습니다. 교집합을 합집합으로 나눈 값입니다.

이 계산을 모든 기사에 돌리지는 않습니다. 앞에 값싼 단계가 하나 있습니다.

Dedupe는 두 번 훑습니다. 첫 번째는 정규화한 제목이 완전히 같은 것을 합칩니다. 통신사 기사를 그대로 받아 실은 매체들이 여기서 걸립니다. 문자열 비교와 맵 하나로 끝나니 비쌀 것이 없습니다.

남은 것이 두 번째로 갑니다. 매체가 문장을 고쳐 쓴 것들입니다.

진천군, 온디바이스 AI 기반 스마트 돌봄 구축 본격 착수
진천군 온디바이스 AI기반 스마트돌봄 본격화

정규화해도 같은 문자열이 되지 않습니다. 구축 본격 착수와 본격화가 다릅니다. 이 둘을 잡는 것이 근사 중복 단계입니다.

정확 일치를 먼저 거르면 두 번째 단계의 입력이 줄어듭니다. 그리고 두 단계의 실패 방식이 다릅니다. 첫 단계는 놓치기만 하고 잘못 합치지 않습니다. 잘못 합칠 가능성이 있는 것은 두 번째뿐입니다.

라이브 데이터 100건으로 분포를 봤습니다

온디바이스 AI 검색 결과 100건을 한국 로케일로 받아 실제 분포를 확인했습니다.

	유사도
같은 사건	0.29 ~ 0.62
다른 사건	0.02 ~ 0.19

대체로 갈렸습니다. 0.2와 0.29 사이에 선을 그으면 될 것 같았습니다.

상용구가 유사도를 부풀렸습니다

오탐 두 건을 발견했습니다.

0.64  "어드밴트, 온디바이스 AI 서비스 실증·확산 사업 참여"
      "엠젠솔루션, 온디바이스 AI 서비스 실증·확산 사업 참여"

같은 사업에 다른 회사가 참여한 것입니다. 서로 다른 뉴스입니다. 유사도는 0.64로 같은 사건 범위(0.29~0.62)보다 높았습니다.

0.46  "경북도, 온디바이스 AI 실증사업 공모 2년째 선정"
      "증평군 온디바이스 AI 실증사업 공모 선정"

다른 지자체입니다. 이것도 오탐입니다.

원인은 구조적이었습니다. 두 제목의 대부분이 같은 상용구입니다. 온디바이스 AI 실증사업 공모 선정이 공통이고, 다른 것은 앞의 주체 이름뿐입니다.

3-gram 집합에서 주체 이름이 차지하는 비중은 작습니다. 어드밴트는 3-gram 세 개이고 나머지 공통 문구는 스무 개가 넘습니다.

유사도는 전체 문자열의 비율을 봅니다. 뜻을 가르는 부분이 짧으면 그 차이가 묻힙니다.

IDF 가중은 절반만 해결했습니다

두 번째 시도는 흔한 3-gram의 가중치를 낮추는 것이었습니다.

배치 안에서 각 3-gram이 몇 개 문서에 나타나는지 세고, 흔한 것에 낮은 가중치를 줬습니다. 검색에서 쓰는 IDF와 같은 발상입니다.

가중치 = log(1 + 전체 문서 수 / (1 + 그 3-gram이 나온 문서 수))

실증사업은 배치의 여러 기사에 나오므로 가중치가 낮아집니다. 어드밴트는 한 기사에만 나오므로 높아집니다. 자카드의 교집합과 합집합을 개수 대신 이 가중치의 합으로 셉니다.

결과가 갈렸습니다.

쌍	단순 자카드	IDF 가중	판정
경북도 / 증평군	0.31	0.15	해소
어드밴트 / 엠젠솔루션	0.64	0.54	여전히 높음
진천군 (진짜 중복)	—	0.51	오탐보다 낮음

세 번째 줄이 결정적입니다.

진짜 중복인 진천군 쌍이 0.51이고, 오탐인 어드밴트 쌍이 0.54입니다. 오탐이 진짜보다 높습니다.

임계값을 어디에 그어도 둘 중 하나는 틀립니다. 0.52에 그으면 진짜 중복을 놓치고, 0.50에 그으면 오탐을 합칩니다.

가중만으로는 분리 불가능했습니다.

이 지점에서 유사도를 더 정교하게 만드는 방향을 포기했습니다. 문제가 유사도의 정확도가 아니라 다른 곳에 있었습니다.

제목의 구조를 이용했습니다

뉴스 제목에는 패턴이 있습니다.

어드밴트, 온디바이스 AI 서비스 실증·확산 사업 참여
경북도, 온디바이스 AI 실증사업 공모 2년째 선정
증평군 온디바이스 AI 실증사업 공모 선정

앞에 주체가 오고 뒤에 내용이 옵니다. 쉼표가 있기도 하고 없기도 합니다.

이 구조를 게이트로 만들었습니다. 선두 어절이 다르면 유사도가 얼마든 병합하지 않습니다.

쌍	선두 어절	병합
어드밴트 / 엠젠솔루션	다름	차단
경북도 / 증평군	다름	차단
진천군 4건	같음	허용

오탐 세 건이 전부 차단됐고 진짜 중복은 전부 유지됐습니다.

게이트가 정밀도를 담당하니 임계값을 낮출 수 있었습니다

이것이 이 설계의 실제 이득입니다.

게이트가 없으면 임계값이 정밀도와 재현율을 동시에 담당합니다. 높이면 놓치고 낮추면 잘못 합칩니다.

게이트가 정밀도를 담당하면 임계값은 재현율만 보면 됩니다. 공격적으로 낮출 수 있습니다.

임계값을 스윕했습니다. 100건이 몇 건으로 줄어드는지 봅니다.

임계값	결과 건수
0.45	84
0.40	83
0.35	81
0.30	77

0.30에서 생성된 병합 그룹을 전부 육안으로 검사했습니다. 진천군 스마트돌봄 3개 매체, 노타의 AMD 파트너십 5개, 화성시 화재감지 3개, 포항시 제조 실증 2개입니다. 네 그룹이 전부 진짜 중복이었습니다. 오탐 없음. 0.30을 채택했습니다.

그 근거를 상수 위에 주석으로 붙여 뒀습니다. 열세 줄입니다.

// core-feed/catalog/collect.go:232-245
// Calibrated on 100 live Google News results for "온디바이스 AI" …
// Sweeping downward collapsed 100 items to 84 / 83 / 81 / 77
// at 0.45 / 0.40 / 0.35 / 0.30.
//
// 0.30 is low only because the subject gate carries the precision.
const nearDuplicateThreshold = 0.30

숫자 하나를 고치려는 사람이 왜 0.30인지 읽을 수 있어야 합니다. 스윕 값과 육안 검사 결과가 없으면 0.35가 더 안전해 보입니다. 마지막 두 줄이 그 판단을 막습니다. 게이트가 정밀도를 담당하니까 낮은 것이고, 게이트를 걷어내면 이 값도 함께 올려야 합니다.

0.25 이하는 검증하지 않았습니다. 같은 주체가 낸 다른 사건을 합칠 위험이 있어 내려가지 않았습니다.

구현에서 두 가지를 더 신경 썼습니다

주체로 버킷팅해 N² 비교를 피했습니다

모든 쌍을 비교하면 문서 수의 제곱입니다. 100건이면 4,950번이고, 로케일 16개를 한 배치로 처리하면 훨씬 커집니다.

선두 어절이 다르면 어차피 병합하지 않습니다. 그래서 선두 어절로 버킷을 만들고 같은 버킷 안에서만 비교합니다.

// core-feed/catalog/collect.go:326-346
for i := range items {
  for _, r := range buckets[leads[i]] {          // 같은 선두 어절만 본다
    if weightedJaccard(grams[i], grams[r], idf) < nearDuplicateThreshold {
      continue
    }
    ...                                          // 대표를 더 나은 쪽으로 교체
  }
  buckets[leads[i]] = append(buckets[leads[i]], i)
}

버킷 키가 leadToken입니다. 제목 뒤의 매체 이름을 떼고, 공백과 쉼표와 ·와 콜론으로 자른 첫 조각에서 글자와 숫자만 남깁니다. 그래서 어드밴트,와 어드밴트가 같은 키가 됩니다.

키가 빈 문자열이 될 수도 있습니다. 쓸 만한 선두 어절이 없는 제목입니다. 그때는 게이트가 동작하지 않고, 빈 키끼리 한 버킷에 모여 유사도만으로 비교됩니다. 게이트는 있으면 막고 없으면 비켜섭니다.

게이트가 성능 최적화를 겸합니다. 정밀도를 위해 넣은 규칙이 비교 횟수를 준선형으로 만듭니다.

greedy clustering으로 연쇄 병합을 막았습니다

A와 B가 비슷하고 B와 C가 비슷하면 A와 C도 합쳐야 할까요.

유사도는 전이적이지 않습니다. A와 C는 전혀 다를 수 있습니다. 연쇄로 합치면 그룹이 무한히 커집니다.

그래서 각 그룹의 대표와만 비교합니다. A가 대표면 B는 A와 비교되고, C도 A와 비교됩니다. B와 C는 서로 비교되지 않습니다.

대가가 있습니다. 실제로 같은 사건인 두 그룹이 별도로 남았습니다.

"진천군 스마트돌봄" 그룹
"진천군 내년까지 어린이집 16곳" 그룹

둘은 같은 사업 보도였습니다. 대표끼리의 유사도가 임계값 아래라 합쳐지지 않았습니다.

과합병보다 과분할이 낫다고 판단했습니다. 잘못 합치면 사용자가 기사 하나를 잃습니다. 나누면 중복이 하나 보입니다.

어느 기사를 남길지는 기존 규칙을 그대로 씁니다

병합할 때 대표를 골라야 합니다. 정확 일치 중복 제거에서 쓰던 규칙을 그대로 적용했습니다.

순위	기준
1	신디케이터보다 원 매체 (v.daum.net, news.naver.com보다 원본)
2	불투명 링크보다 직접 링크
3	최신

두 번째가 Google News 때문입니다. Google News의 링크는 리다이렉트 주소이고 원문 도메인을 감춥니다.

테스트 네 개로 잠그고, 한계는 세 가지를 적었습니다

테스트 네 개를 새로 썼습니다.

테스트	무엇을 지키는가
리워딩된 같은 사건 병합	재현율
다른 주체(회사·지자체) 분리 유지	정밀도
근사 병합에서도 원 매체 우선	대표 선정
무관 기사 미병합	임계값

두 번째가 이 작업의 핵심을 지킵니다. 앞으로 임계값을 만지는 사람이 오탐을 되살리면 이 테스트가 잡습니다.

전체 36건이 통과했습니다. 라이브에서 다시 확인했습니다.

	전	후
온디바이스 AI 수집	102건	95건 고유
진천군 기사	4건	1건
상위 8건	4건이 같은 사건	전부 다른 사건

세 가지 한계를 적어 둡니다

임계값 0.30은 한국어 단일 토픽 100건으로 보정한 값입니다. 다른 언어나 다른 주제에서 같은 값이 맞는지 검증하지 않았습니다. 영어 뉴스의 제목 구조는 주체, 내용이 아닐 수 있고, 그러면 게이트 자체가 다르게 동작합니다.

IDF를 배치 안에서 계산합니다. 배치가 매우 작으면 문서 빈도가 불안정합니다. 세 건짜리 배치에서 어떤 3-gram이 두 건에 나오면 그것만으로 흔한 것이 됩니다. 상대 비교라 실용상 문제는 관측되지 않았지만 구조적 약점입니다.

첫 두 시도의 중간 산출물을 남기지 않았습니다. 단순 자카드와 IDF 가중 단독 구현을 폐기하면서 코드를 지웠습니다. 나중에 다른 언어에서 다시 시도할 때 처음부터 만들어야 합니다.