AncomWiki

음식점명 군집화를 위한 문자열 유사도 계산 (Cosine Similarity)

Properties1
description동일한 전화번호를 가진 음식점명 데이터에서 중복 또는 유사한 명칭을 자동으로 군집(Clustering)하기 위한 방법을 다룬다. 단순 키워드 포함 여부나 해밍 거리(Hamming Distance)는 오타나 부분 일치로 인한 오판이 발생하므로, 문서 간 유사도 계산에 널리 쓰이는 코사인 유사도(Cosine Similarity)를 적용한다. 음식점명을 띄어쓰기나 구분자를 기준으로 토큰화하여 이진 벡터로 변환한 후, 코사인 유사도…

6 min read

음식점명 군집화를 위한 문자열 유사도 계산 (Cosine Similarity)

Source

  • Evernote/Technote scraps/구시렁 구시렁 유사도 계산.md

Summary

동일한 전화번호를 가진 음식점명 데이터에서 중복 또는 유사한 명칭을 자동으로 군집(Clustering)하기 위한 방법을 다룬다. 단순 키워드 포함 여부나 해밍 거리(Hamming Distance)는 오타나 부분 일치로 인한 오판이 발생하므로, 문서 간 유사도 계산에 널리 쓰이는 코사인 유사도(Cosine Similarity)를 적용한다. 음식점명을 띄어쓰기나 구분자를 기준으로 토큰화하여 이진 벡터로 변환한 후, 코사인 유사도 공식을 간략화한 식(n11, n10, n01 기반)을 사용하여 유사도를 산출한다. 유사도가 0 이상인 문서들을 연결하여 트리를 구성함으로써 동일한 실체를 지칭하는 명칭들을 효과적으로 그룹화할 수 있음을 예시(메이필드호텔 봉래정 등)를 통해 입증한다. 전처리 단계에서 형태소 분석이나 구분자 기반 토큰화가 중요함을 강조한다.

Key Points

  • 문제 정의: 동일 전화번호에 매핑된 다양한 음식점명(예: ‘메이필드호텔 봉래정’ vs ‘봉래정(메이필드호텔)‘)을 기계적으로 동일 실체로 판단하여 군집화하는 것이 목표.
  • 기존 방법의 한계: 단순 키워드 포함 검사는 부분 일치(예: ‘가네’ vs ‘신가네김밥’)로 인한 오탐(False Positive)이 발생함. 해밍 거리는 벡터 차원이나 존재 여부의 가중치를 고려하지 않아 부적합함.
  • 해결책: 정보 검색(IR)에서 사용하는 코사인 유사도(Cosine Similarity) 적용.
  • 알고리즘 구현:
    1. 토큰화: 음식점명을 띄어쓰기, 괄호, 하이픈 등 구분자를 기준으로 단어(키워드)로 분할.
    1. 벡터화: 추출된 키워드 집합을 기준으로 각 문서를 이진 벡터(0 또는 1)로 표현.
    1. 유사도 계산: 코사인 유사도 공식을 이진 벡터에 적용하여 간략화. n11(공유 키워드 수), n10(A만 있는 수), n01(B만 있는 수)를 사용하여 유사도 점수 산출.
    1. 군집화: 계산된 유사도가 0보다 큰 문서 쌍을 연결하여 그래프/트리를 구성하고, 이를 통해 독립적인 군집(Cluster)을 형성.
  • 전제 조건: 정확한 군집화를 위해서는 토큰화 단계의 정확도(형태소 분석 또는 구분자 규칙)가 핵심임.
  • 기대 효과: 검색 엔진 색인 데이터 정제(Data Mining)를 통해 맛집 검색 시 그룹핑 정확도 향상.

그래프 뷰

백링크