[2021-1 데이터마이닝및분석] Chapter 2: Data (3) Similarity

유사도 측정 Measures of Similarity

유사도(Similarity)는 두 데이터 객체가 얼마나 비슷한지에 대한 척도다. 두 객체가 더 비슷할수록 유사도는 높아진다. 비유사도(Dissimilarity)는 두 객체가 얼마나 다른지에 대한 척도다. 두 객체가 유사할수록 비유사도는 낮아진다.

데이터 객체간의 유사도와 비유사도는 Clustering, NN 등 많은 데이터 마이닝 기술에서 사용되므로, 유사도(또는 비유사도)에 대한 측정 방법에 대해서는 꼭 알아둬야 한다. 데이터 간 유사도를 측정하는 방법은 많으므로, 내가 뭘 판단하고 싶은 건지에 따라 선택하면 된다.

 

유사도-비유사도 변환 Transformations

$s(similarity) ∈ [0, 1], d(dissimilarity) ∈ [0, 1]$일 때, s를 d로 변환하는 방법은 다음과 같다:

• Substract: $d = 1 - s$
• Reciprocal: $d = 2 / (s + 1) - 1$
• Exponent: $d = 1/e^s$

 

민코스키 거리 Minkowski distance

$x = (x_1, x_2, ..., x_n), y = (y_1, y_2, ..., y_n)$ 의 데이터 객체 2개가 있을 때, 두 객체 사이의 거리를 나타낸다. 거리(Distance)는 dissimilarity의 일종이며, 특정 조건을 만족할 시 거리라고 칭한다.

유클리드 거리 Euclidean distance

두 점 간의 직선 거리다. $d(x, y) = \sqrt{\sum_{k=1}^n (x_k - y_k)^2}$ 식을 통해 구할 수 있다.

유클리드 거리의 일반화 Generalization of the Euclidean distance

아래의 식은 위의 Euclidean distance 공식을 일반화한 것이다. Euclidean distance의 일반화된 식에 r을 적절하게 넣으면 Manhattan distance와 Supremum distance도 구할 수 있다.

$$d(x, y) = (\sum_{k=1}^n |x_k - y_k|^r)^{1/r}$$

• r = 1: Manhattan distance($L_1$ norm)
• r = 2: Euclidean distance($L_2$ norm)
• r = $\infty$: Supremum distance($L_{\infty}$ norm). 가장 큰 값이 dominant해진다.

 

'거리'가 갖는 특징 The Properties of Distances

Dissimilarity 중 아래의 3가지 특징을 모두 가지면 Distance라고 칭할 수 있으며, Distance는 우리의 직관과 맞는 척도의 역할을 한다.

1. Positivity: 모든 x와 y에 대하여 $d(x, y) \geq 0$ 이어야 하며, $d(x, y) = 0$ 인 경우는 $x = y$ 일 때 뿐이다.
2. Symmetry: 모든 x와 y에 대하여 $d(x, y) = d(y, x)$이다.
3. Triangle inequality: 모든 x, y, z에 대하여 $d(x, z) \leq d(x, y) + d(y, z)$이다.

 

유사도 계수 Similarity Coefficients

0 또는 1의 값을 갖는 이진 특성에 대한 유사도 척도다. 이진 특성들은 앞서 설명한 민코스키 거리 계산이 힘들다(특히 이진 특성에서의 Supremum distance는 그냥 무의미하다). 보통 0부터 1 사이의 값을 가지며, 0은 전혀 유사하지 않음, 1은 완벽히 일치함을 뜻한다.

$x = (x_1, x_2, ..., x_n), y = (y_1, y_2, ..., y_n)$ 의 이진 데이터 객체 2개가 있을 때,

• $f_{00}$: x = 0이고 y = 0인 특성의 개수
• $f_{01}$: x = 0이고 y = 1인 특성의 개수
• $f_{10}$: x = 1이고 y = 0인 특성의 개수
• $f_{11}$: x = 1이고 y = 1인 특성의 개수

라고 하자. 우리가 이진 특성들의 유사도를 표현할 수 있는 방법은 다음 2가지가 있다.

• Simple Matching Coefficient:  짝이 맞는(00 or 11) 특성의 개수 / 전체 특성의 개수
  $ SMC = \cfrac{f_{11} + f_{00}}{f_{01} + f_{00} + f_{11} + f_{00}}$
• Jaccard Coefficient: 의미있는 데이터(11)의 개수 / 전체 특성의 개수데이터셋의 차원이 높을수록 $f_{00}$ 의 개수가 의미없이 많아진다. 예를 들어, 아마존에서 구매한 물건을 1로, 사지 않은 물건을 0으로 표시할 때 두 사람 x, y가 아마존에서 구매한 물건(1)보다 구매하지 않은 물건(0)이 압도적으로 많을 거다. 이때 $f_{00}$ 는 두 객체의 유사도에 영향을 준다고 보기 어려우므로, Jaccard coefficient 계산식의 분자에서 제외한다.
  $ J = \cfrac{f_{11}}{f_{01} + f_{00} + f_{11} + f_{00}}$

 

코사인 유사도 Cosine Similarity

두 벡터 x와 y 사이의 각도를 측정한다. 정치적 성향의 차이 측정, 문서 비교에 사용하면 유용하다.

$cos(x, y) = \cfrac{<x, y>}{||x|| ||y||}, <x, y>$는 x와 y의 내적이며 $||x||$는 벡터 x의 길이다. [-1, 1]의 범위를 가지며, Cosine distance는 (1 - cosine similarity)로 [0, 2]의 범위를 가진다.

특히 코사인 유사도는 문서간의 유사도를 측정할 때 유용하다. 문서는 문서의 각 단어가 나타나는 빈도수를 담고 있는 벡터로 표현되기도 하는데, 이 벡터간의 거리를 측정할 때 Euclidean distance를 사용하는 것보다 cosine sililarity를 사용하는 것이 훨씬 더 정확하다. Euclidean distance는 문서의 크기 차이를 고려하지 않아 문서의 내용이 유사하더라도 문서의 크기 차이가 크면 유사하지 않은 걸로 판단하는 반면, cosine은 벡터의 크기가 각도에 영향을 주지 않으므로 문서간의 유사도를 비교적 정확하게 측정할 수 있다.

 

상관계수 Correlation

2개의 measure가 주어졌을 때 값의 경향, 비례 혹은 반비례 등의 선형관계를 파악하는 것이다.

• $x = (1, 2, 3, 4, 5), y = (2, 4, 6, 8, 10)$ 이면 $corr = 1$로 완전 비례관계다.
• $x = (1, 2, 3, 4, 5), y = (5, 4, 3, 2, 1)$ 이면 $corr = -1$로 완전 반비례관계다(경향성 역전).

피어슨 상관계수 Pearson's correlation

통계학입문에서 배웠던 바로 그거다.

$$corr(x, y) = \cfrac{covariance(x, y)}{standard\_deviation(x) \times standard\_deviation(y)} = \cfrac{s_{xy}} {s_xs_y}$$