[Data Science] Measuring Data Similarity and Dissimilarity

 

data similarity를 이용한 clustering (Disease influence graph)

 

Data Matrix

$n$개의 object와 $p$개의 attribute를 갖는 데이터가 있다고 하자. 우리는 이런 데이터를 $n \times p$ matrix로 표현할 수 있다.

 

\[ \begin{bmatrix} x_{11} & \cdots & x_{1f} & \cdots & x_{1p} \\ \cdots & \cdots & \cdots & \cdots & \cdots \\ x_{i1} & \cdots & x_{if} & \cdots & x_{ip} \\ \cdots & \cdots & \cdots & \cdots & \cdots \\ x_{n1} & \cdots & x_{nf} & \cdots & x_{np} \\ \end{bmatrix} \]

이 때 $1$번째 object의 데이터는 $x_1 = (x_{11}, x_{12}, \dots , x_{1p})$이고, $i$번째 object의 데이터는 $x_i = (x_{i1}, \dots, x_{ij}, \dots, x_{ip})$ 이다.

즉, $x_{ij}$는 $i$번째 object의 $j$번째 attribute의 값이다.

Dissimilarity Matrix

object별로 dissimilarity 를 계산하여 행렬로 표현한 것을 Dissimilarity Matrix라고 한다. 

$x_i, x_j$의 dissimilarity를 $d(i, j)$라 하면 아래와 같은 행렬로 표기할 수 있다. (당연히 $d(i, j) = d(j, i)$이다.)

\[ \begin{bmatrix} 0 & & & & & \\ d(2, 1) & 0 & & &\\ d(3, 1) & d(3, 2) & 0 & & \\ \vdots & \vdots & \vdots & &\\ d(n, 1) & d(n, 2) & \cdots & \cdots & 0 \end{bmatrix} \]

$d(i, j)$는 음이 아닌 실수이고, $0$에 가까울 수록 서로 비슷하다(near, high similar)고 한다. 

 

별도의 표기가 없으면, 두 object의 유사도는 $sim(i, j) = 1 - d(i, j)$로 한다.

 

object별로 dissimilarity를 계산하는 방법은 attribute의 type에 따라 다양한 방법이 제시된다.

Standardizing Numeric Data

데이터를 측정/저장할 때 결국 단위의 문제가 생긴다. 

예를 들어, 데이터가 [1lb, 2lb, 3lb]인 벡터와 [0.45kg, 0.90kg, 1.35kg]인 벡터는 사실 같은 의미를 갖지만 숫자로는 그렇지 못하다. 따라서 numeric data는 표준화(standardizing)이 필요하다. 

 

때때로, absolute value의 경우에는 표준화가 유용하지 않을 수 있다.

 

Z-score

\[ z = \cfrac{x - \mu}{\sigma} \]

$x$는 표준화 되지 않은 데이터, $\mu, \sigma$는 모집단의 평균과 표준편차.

 

그런데 (표본평균의 평균은 모평균이라 하지만) 모집단의 표준편차(모표준편차)는 사실상 모르는 것 아닌가? 

대안으로 $\sigma$ 대신에 mean absolute deviation(MeanAD, MAD, 평균 절대 편차)을 이용할 수 있다. 

$n$개의 표본과 

\[ m_f = \cfrac{1}{n}\sum_{i=1}^{n}x_{if} \]

\[ s_f = \cfrac{1}{n}\sum_{i=1}^{n} |x_{if} - m_f| \]

일 때

\[ z_{if} = \cfrac{x_{if}-m_f}{s_f} \]

 

MAD를 이용한 표준화는 outlier에 강하다. (outlier에 의한 데이터 왜곡을 줄일 수 있다.)

Dissimilarity between Nomial Attributes

$p$개의 attribute에 대하여, nomial attribute의 dissimilarity는 "ratio of mismatches"로 정의한다. 따라서

\[ d(i, j) = \cfrac{p-m}{p}, \quad sim(i, j) = \cfrac{m}{p} \]

$m$은 mismatch의 개수이다.

 

Example

아래 표의 데이터가 있을 때, Object Identifier와 test-1의 dissimilarity matrix를 구해보자.

Table 1.

test-1만 이용하기 때문에, nomial attribute의 개수 $p=1$이다. 따라서 $d(i, j)$의 값은 둘이 같으면 $0$이고 다르면 $1$이 된다. 

 

\[ \begin{bmatrix} 0 & & &   \\ 1 & 0 &  \\ 1 & 1 & 0   \\  0 & 1 &1 & 0 \end{bmatrix} \]

 

Dissimilarity between Binary Attributes

binary attribute의 경우, matching의 중요도에 따라 symmetric, asymmetric binary attribute로 분류한다.

Contigency Table for Binary Attribute

• $q$는 (1, 1)로 두 object 모두 1로 일치하는 경우
• $r$는 (1, 0)으로 $i$번째 objecet만 1인 경우
• $s$는 (0, 1)으로 $j$번째 objecet만 1인 경우
• $t$는 (0, 0)로 두 object 모두 0으로 일치하는 경우

 

Symmetric Binary Attribute

symmetric binary attribute는 각 state는 균일하게 중요하기 때문에(equally valuable) matching/unmatching의 개수의 비가 $d(i, j)$가 된다.

\[ d(i, j) = \cfrac{r+s}{q+r+s+t} \]

 

Asymmetric Binary Attribute

asymmetric binary attribute는 각 state의 중요도가 다르다. 

예를 들어, 질병 검사에서 양성반응(1, Positive, Yes)는 음성반응(0, Negative, No)보다 훨씬 중요하다. 그리고 둘 다 음성반응이어도(Negative, Negative) 이는 정보의 중요도가 (Positive, Positive)보다 매우 떨어진다. 따라서 $t$는 dissimilarity에 반영되지 않는다.

 

\[ d(i, j) = \cfrac{r+s}{q+r+s}, \quad sim(i, j) = \cfrac{q}{q+r+s} \]

 

Example

아래 표는 3명의 환자들의 증상을 나타낸 표이다. gender는 symmetric binary attribute이고 그 외 나머지는 asymmetric binary attribute이다. gender를 제외한 나머지 attribute에 대해 3명(Jack, Jim, Mary)의 dissimilarity를 구해보자.

Relational Table Where Patients Are Described by Binary Attributes

Jack과 Jim의 경우, q(1, 1), r(1, 0), s(0, 1)는 각각 $q=1, r=1, s=1$이므로

\[ d(Jack, Jim) = \cfrac{1+1}{1+1+1} = 0.67 \]

 

Jack과 Mary의 경우, $q=2$(fever, test-1이 (1, 1)로 일치), $r=1, s=1$이므로

\[ d(Jack, Mary) = \cfrac{0+1}{2+0+1} = 0.33 \]

 

Jim과 Mary의 경우는

\[ d(Jim, Mary) = \cfrac{1+2}{1+1+2} = 0.75 \]

Distance on Numeric Attributes

Minkowski Distance

$i = (x_{i1}, x_{i2}, \dots, x_{ip}), \ j = (x_{j1}, x_{j2}, \dots, x_{jp})$ 일 때, 민코프스키 거리(Minkowski distance)를 이용한 정의를 이용할 수 있다.

\[ d(i, j) = \sqrt[\leftroot{-2}\uproot{2}h]{|x_{i1}-x_{j1}|^h + |x_{i2}-x_{j2}|^h + \cdots + |x_{ip}-x_{jp}|^h} \]

위 식은 $L_h$ norm이라고 부른다.

 

• $h=1$인 경우 ($L_1$ norm) Manhattan distance
• $h=2$인 경우($L_2$ norm) Euclidian distance
• $h \to \infty$ 인 경우 ($L_{\text{max}}$ norm, $L_{\infty}$ norm, supreme distance) $\max{|x_{if}-x_{jf}|}$

 

Example

$x_1, x_2$의 $L_1, L_2, L_{\text{max}}$

 

 

Common Properties of a Distance

• Non-negativity: $d(i, j) \ge 0$
• Identity of indiscernibles: $d(i, i) = 0$
• Symmetry: $d(i, j) = d(j, i)$
• Tirangle inequality: $d(i, j) \le d(i, k) + d(k, j)$

위 성질을 다 만족하는 distance를 metric이라고 부른다.

 

Dissimilarity between Ordinal Attributes

데이터 $x_{if}$의 순위를 매긴다. $r_{if} = \{1, 2, \dots, M_f \}$

그 후 $[0, 1]$에 매핑되도록 $z$를 구한다.

\[ z_{if} = \cfrac{r_{if} - 1}{M_f - 1} \]

 

Example

옷의 사이즈에 대한 데이터가 [S, L, M]이 있다고 하자.

이들의 순위를 매기면 각각 [1, 3, 2]이고 $M_f=3$이므로 $z$를 구하면 [0, 1, 0.5]가 된다.

Cosine Similarity

document vector과 같은 두 벡터 $d_1, d_2$에 대하여 코사인 유사도를 구할 수 있다.

\[ sim(d_1, d_2) = \cos(d_1, d_2) = \cfrac{d_1 \cdot d_2}{\Vert d_1 \Vert \Vert d_2 \Vert} \]

이때 $\cdot$는 벡터의 dot product이고 $\Vert d \Vert$는 벡터 $d$의 길이(크기)이다.

 

Mixed types

data object가 여러가지 데이터 타입이 있다고 하자. (nomial, symmetric binary, ordinal등 이 모두 있어도 가능)

attribute는 $p$개일 때 dissimilarity는 

\[ d(i, j) = \cfrac{\sum_{f=1}^{p} \delta_{ij}^{(f)} d_{ij}^{(f)} }{\sum_{f=1}^{p}\delta_{ij}^{(f)} } \]

$\delta_{ij}^{(f)}$는 indicator로, 항목이 비어있거나(missing) $0$, asymmetric binary attribute이면서 (0, 0)인 경우에는 $0$을 할당하고, 그 외에는 $1$을 할당한다.

$d_{ij}^{(f)}$는 $f$의 attribute type에 따라 달라진다.

• numeric: $d_{ij}^{(f)} = \cfrac{|x_{if} - x_{jf}|}{\max_h x_{hf} - \min_h x_{hf}}$
• nomial/binary: $x_{if} = x_{jf}$이면 $d_{ij}^{(f)}=1$이고 그렇지 않으면 $d_{ij}^{(f)}=1$
• ordinal: $z_{if} = \cfrac{r_{if}-1}{M_f - 1}$

※ 경우에 따라 $\delta_{ij}^{(f)}$는 indicator가 아니라 $f$-th attribute의 weight/importance로 대신할 수 있다.