Category Archives: Machine Learning

[프로그래머를 위한 데이터마이닝] #4. 유사도(Similarity)와 거리(Distance)

개체를 분류하거나 클러스터링을 하는 경우, 서로 유사한 개체를 동일한 분류 또는 클러스터로 그룹화해야 한다. 그러려면 개체가 서로 유사하다는 정도를 측정할 수 있는 기준이 필요하다.

유사도와 거리

유사도(similarity)란 두 개체가 닮은 정도에 대한 수치적인 척도다. 두 개체가 많이 닮을수록 유사도는 높아진다. 반대로 비유사도(dissimilarity)란 두 개체가 서로 다른 정도에 대한 수치적인 척도다. 따라서 두 개체사 서로 다를수록 비유사도는 높아진다. 비유사도는 흔히 거리(distance)라는 용어와 같은 의미를 갖는다.

비유사도가 d인 경우, 유사도 s는 아래와 같이 다양한 방식으로 계산할 수 있다.

  • 0 <= d <= 1인 경우, s = 1 – d
  • s = -d
  • s = 1 / (1 + d)

1차원 변수의 유사도

변수가 1개의 속성을 갖는 경우라면, 속성의 유형에 따라 아래와 같이 유사도(또는 비유사도)를 측정할 수 있다.

속성 유형 비유사도 유사도
명목형
(nominal)

if x = y, d = 0

if x != y, d = 1

if x = y, s = 1

if x != y, s = 0

서열형
(ordinal)

d = |x – y| / ( n – 1)

(속성의 값이 n개인 경우)

s = 1 – d
숫자형
(numeric)
d = |x – y|

 s = -d

s = 1 / (1 + d)

명목형 속성의 경우, 개체의 유일성에 대한 정보만을 포함하므로, 두 개체가 동일한 값을 가지는지 여부만 판별할 수 있다. 예를 들어 성별 속성이 {남자, 여자}의 속성값을 가지는 경우, 두 속성 x와 y가 동일한 값을 가진다면 유사도가 1이라고 볼 수 있다.

서열형의 경우 명목형 속성과는 달리 순서에 대해 고려를 해야 한다. 예를 들어 제품의 품질이 {poor, fair, ok, good, wonderful}의 속성값을 가지는 경우를 보자. 이 경우 각 속성값을 숫자형 {0, 1, 2, 3, 4}로 각각 매핑할 수 있다. 이때 제품 A가 poor이고 제품 B가 fair, 제품 C가 ok인 경우, 제품 A는 제품 C보다는 제품 B와 더 유사해야 한다. 따라서 비유사도 d를 |x – y|로 계산할 수 있다. (n – 1)로 나누는 이유는 속성값의 개수에 관계없이 동등한 구간을 유지하기 위함이다.

숫자형의 경우 산술연산이 가능하므로 비유사도를 단순히 |x – y|로 계산할 수 있다.

다차원 변수의 유사도

다차원 변수의 유사도는 일반적으로 아래와 같은 거리 측정 방식을 활용한다.

유클리드(Euclid) 거리

p차원의 공간 위에 있는 두 점 x와 y 사이의 유클리드 거리 d(x,y)는 다음과 같다.

distance_euclidean

p=2인 경우, 즉 2차원에서 유클리드 거리는 다음과 같다.

distance_euclidean_2

민코프스키(Minkowski) 거리

민코프스키 거리는 유클리드 거리를 일반화한 것으로 다음과 같다.

distance_minkowski

마할라노비스(Mahalanobis) 거리

distance_mahalanobis

유사도 계수(Similarity Coefficient)

유사도를 거리 관점이 아니라 계수 관점에서 측정하는 방식은 다음과 같다.

1. 단순 매칭 계수(SMC: Simple Matching Coefficient)

변수 x와 y가 이진 속성만을 가지는 경우 유사도를 측정하는 방식이다. 먼저 아래의 빈도를 측정한다.

  • f00
    x가 0일 때 y도 0인값을 가지는 속성의 수
  • f01
    x가 0일 때 y가 1인값을 가지는 속성의 수
  • f10
    x가 1일 때 y가 0인값을 가지는 속성의 수
  • f11
    x가 1일 때 y도 1인값을 가지는 속성의 수

이때 단순 매칭 계수는 다음과 같다.

smc즉 단순 매칭 계수는 전체 속성 개수 중에서 동일한 속성값을 가지는 속성의 비율이다.

2. 자카드 계수(Jaccard Coefficient)

단순 매칭 계수는 비대칭 이진 속성의 경우 문제가 된다. 비대칭 이진 속성(asymmetric binary attribute)이란 0이 아닌 속성만이 유효한 속성이다. 예를 들어 상점에서 판매중인 모든 상품에 대해 사람 x가 산 상품은 1로, 사지 않은 상품은 0을 가진다고 해보자. 이 경우 각 상품은 사람의 속성에 해당한다. 하지만 상점에서 파는 상품의 수는 굉장히 크고, 사람 x의 속성값의 대다수는 0일 것이다. 따라서 서로 다른 두 사람의 단순 매칭 계수를 비교하는 경우, f00 빈도가 굉장히 크기 때문에, 대다수의 사람은 유사하다고 측정된다. 따라서 단순 매칭 계수는 비대칭 이진 속성인 경우에는 올바른 방식이 아니다.

비대칭 이진 속성에 대한 유사도를 계산하는 한 방법이 자카드 계수는 아래와 같다.

jaccard

즉 자카드 계수에서는 f00 빈도를 제거하여 유사도를 계산한다

3. 코사인 유사도(Cosine Similarity)

문서간의 유사도를 측정할 때 자주 사용한다. 각 문서는 문서에 나오는 단어가 속성에 해당하며, 속성 값은 해당 단어의 빈도수다. 이 경우에도 마찬가지로 전체 단어의 개수는 방대하므로, 0이 아닌 속성 값만이 중요해진다. 하지만 자카드 계수는 이진 데이터에 대해서만 적용가능하다. 이처럼 0-0이 매칭되는 속성은 제외하고, 이진 데이터가 아닌 속성값에 대하 유사도를 측정하는 대표적인 방식이 코사인 유사도다.

n차원 평면에서 x = (x1, x2, …, xn), y = (y1, y2, …, yn)인 경우,

cosine_distance

vector_dot_prodcut

이때 cos(x,y)는 단위가 1인 벡터 x와 y 사이의 각도(코사인) 값에 해당한다. x와 y가 유사한 경우 각도가 작아지고(즉 코사인 값이 0에 가까워지고), 유사하지 않은 경우 각도가 커진다(즉 코사인 값이 1에 가까워진다).

cosine_angle

4. 확장 자카드 계수(EJ : Extended Jaccard)

확장 자카드 계수 또한 문서간의 유사도를 측정할 때 사용할 수 있으며, 타니모토 계수(Tanimoto Coefficient)라고도 부른다.

ex_jaccard

5. 피어슨 상관관계 계수(Pearson’s Correlation Coefficient)

피어슨 상관 계수는 다음과 같다.

pearson

이때 Sxy는 x와 y의 covariance(공분산), Sx는 x의 표준편차(standard deviation)이다.

피어슨 상관계수는 -1과 1 사이의 값을 가지며, 두 변수의 상관관계가 크면 1, 적으면 0의 값을 가진다. 만약 x 가 커질 때 y가 작아지는 서로 대립하는 연관성이 있는 경우 -1의 값에 가까워진다.

6. 스피어만 상관관계 계수(Spearman’s Correlation Coefficient)

스피어만 상관계수는 피어슨 상관계수의 변형으로, 원래의 속성값 대신, 속성값의 순위에 기반하여 상관관계를 계산한다. 속성값 대신 순위를 사용하는 이유는 두 변수 사이의 연관관계가 선형이든 비선형이든 관계없이 연관성을 보여줄 수 있기 때문이다.

일반적으로 스피어만 상관계수 측정은 계산 비용이 크기 때문에, 데이터셋이 적은 경우에 사용하는 편이다.

지금까지는 모든 속성을 동등하게 취급하였다. 하지만 일부 속성이 더 중요하다면 해당 속성에 가중치를 부여하여 유사도를 측정할 수도 있다.

참고자료

  • 데이터마이닝 / 인피니티북스 / 용환승 등 공역
  • 머하웃 완벽 가이드 / 한빛미디어 / 안태성 역

 

[프로그래머를 위한 데이터마이닝] #3. 클러스터링(Clustering)이란

개요

분류(Classification)에서는 데이터셋의 목표 변수(또는 클래스 변수)가 이미 알려져 있다. 예를 들어 정상/비정상, 충성고객/일반고객/이탈가능고객 등과 같은 형태로 목표 변수가 분류될 수 있다. 반면에 클러스터링은 목표변수가 없는 데이터셋에 대해 유사한 개체를 서로 그룹화하는 방법이다.

다시 말해 분류는 클래스가 알려져 있는 개체에 대해, 클래스가 이미 알려진 개체로부터 만들어진 모델을 사용하여 클래스를 예측하는 방법이다. 이 경우 분류는 교사 학습(supervised learning)이라고 부른다. 반면에 클러스터는 비교사 학습(unsupervised learning)에 포함된다.

클러스터링은 각 개체간의 유사도(similarity)를 기반으로 하며, 서로 유사한 개체를 동일한 그룹에 할당한다. 따라서 클러스터링을 하기 위해서는 유사도를 측정하기 위한 방법이 필수적이다.

거리(Distance)

클러스터링에서는 일반적으로 유사도보다는 비유사도(dissimilarity)를 기준으로 하며, 비유사도는 일반적으로 거리(distance)라고 부른다.

거리에 대한 수학적인 정의는 다음과 같다.

일반적으로 아래와 같은 거리 측정 방식을 활용한다.

유클리드(Euclid) 거리

p차원의 공간 위에 있는 두 점 x와 y 사이의 유클리드 거리 d(x,y)는 다음과 같다.

distance_euclidean

p=2인 경우, 즉 2차원에서 유클리드 거리는 다음과 같다.

distance_euclidean_2

민코프스키(Minkowski) 거리

민코프스키 거리는 유클리드 거리를 일반화한 것으로 다음과 같다.

distance_minkowski

마할라노비스(Mahalanobis) 거리

distance_mahalanobis