유사도(유사성) 측정은 데이터 마이닝의 여러 의사결정이 이루어지는 기반 틀을 제공합니다. 분류(classification)와 군집화(clustering) 같은 작업은 일반적으로 어떤 형태의 유사도 측정이 존재한다는 전제 위에서 수행되며, 반대로 유사도를 평가할 만한 기법이 부족한 분야에서는 정보 검색 자체가 번거롭고 어려운 작업이 되곤 합니다.
유사도 측정의 주요 적용 분야
정보 검색(Information Retrieval)
정보 검색(IR) 시스템의 목표는 사용자의 요구를 충족시키는 것입니다. 여기서 '요구'란 보통 온라인 검색 엔진의 입력창에 짧은 텍스트 질의(query) 형태로 표현됩니다. IR 시스템은 질의에 대한 답변을 직접 제시하기보다는, 특정 유사도 측정 기준으로 해당 질의와 관련성이 높다고 판단된 문서(record)들의 순위 목록을 보여주는 방식으로 동작합니다.
유사도 측정은 질의와 관련된 정보를 군집화하고 분류하는 역할을 하기 때문에, 사용자는 질의를 다시 구성할 때 자신의 정보 요구에 대한 새로운 해석을 발견하게 되며, 이것이 유용할 수도 있고 그렇지 않을 수도 있습니다.
질의가 초기 문서 집합에 속한 하나의 문서인 경우에는, 유사도 측정을 활용해 컬렉션 내부의 문서들을 군집화하거나 분류할 수 있습니다. 요컨대 유사도 측정은 이전까지 비정형(unstructured) 상태였던 집합에 기초적인 구조를 부여할 수 있는 도구입니다.
동기(Motivation)
IR 시스템에서 사용되는 유사도 측정은 데이터 전체 집합에 대한 사용자의 인식을 왜곡할 수 있습니다. 예를 들어, 사용자가 검색 엔진에 질의를 입력했는데 반환된 상위 10개 웹 페이지에서 만족스러운 답을 찾지 못하면, 보통 한두 번 정도 질의를 다시 표현(reformulate)하려고 시도합니다.
고전적 유사도 측정 방법
유사도 측정은 크기 k인 두 튜플 쌍을 스칼라 값으로 매핑(mapping)하는 함수로 정의됩니다. 관례상 모든 유사도 측정값은 [-1, 1] 또는 [0, 1] 범위로 매핑되어야 하며, 유사도 점수 1은 최대 유사함을 의미합니다. 또한 유사도 측정은 비교 대상인 두 항목 간에 공통 속성이 많아질수록 그 값이 증가하는 성질을 가져야 합니다.
다이스 계수(Dice Coefficient)
다이스 계수는 정밀도(precision)와 재현율(recall) 측정값의 조화평균(harmonic mean)을 일반화한 것입니다. 조화평균이 높은 시스템은 높은 재현율 수준에서도 높은 정밀도 값을 유지할 수 있으므로, 이론적으로 이상적인 검색 시스템에 가깝다고 볼 수 있습니다. 정밀도와 재현율의 조화평균은 다음과 같습니다.
$$E=\frac{2}{\frac{1}{P}+\frac{1}{R}}$$
다이스 계수는 아래와 같이 표현됩니다.
$$sim(d,d_{j})=D(A,B)=\frac{|A\cap B|}{\alpha|A|+(1-\alpha)|B|}\cong \frac{\propto \sum_{k=1}^{n}w_{kq}w_{kj}}{\propto \sum_{k=1}^{n}\mathrm{w}_{kq}^{2}+(1-\propto)\sum_{k=1}^{n}\mathrm{w}_{kj}^{2}}$$
여기서 α ∈ [0, 1]입니다. α = ½로 두면 다이스 계수가 가중 조화평균(weighted harmonic mean)임을 확인할 수 있습니다.
오버랩 계수(Overlap Coefficient)
오버랩 계수는 두 집합이 얼마나 겹치는지, 즉 중첩의 정도를 판단하려는 지표입니다. 오버랩 계수는 다음과 같이 정의됩니다.
$$sim(d,d_{j})=D(A,B)=\frac{|A\cap B|}{min(|A|,|B|)}\cong \frac{\propto \sum_{k=1}^{n}w_{kq}w_{kj}}{\propto \sum_{k=1}^{n}\mathrm{w}_{kq}^{2}+\sum_{k=1}^{n}\mathrm{w}_{kj}^{2}}$$
오버랩 계수는 min 연산자 자리에 max 연산자를 사용하여 계산하는 변형 방식도 존재합니다.