Tag Archives: datamining

[프로그래머를 위한 데이터마이닝] #5. 유사도를 기반으로 추천 시스템 만들기

DVD 대여 가게에서 고객이 DVD를 다 본 후 반납할 때, 평점을 매기면 다음 번에 대여할 때는 10% 할인하는 정책을 써서 아래와 같은 정보를 획득했다고 해 보자.

cf_input_data

이제 DVD 대여 가게 사장은 이 정보를 활용하여 고객이 들를 때 마다 고객이 아직 보지 않은, 좋아할 만한 DVD를 추천할 수 있는 시스템을 만들어서 매출을 올리려고 한다. 예를 들어 고객 1에게 어떤 DVD를 추천해야 고객 1이 만족할까?

사용자 유사도 기반 알고리즘

상식적인 접근법은 고객 1과 가장 유사한 선호도를 가진 다른 사용자 B를 찾고, 사용자 B가 보았지만 사용자 1은 보지 않은 DVD 중에서 가장 선호도가 높았던 DVD를 추천하는 방법이다.

추천 알고리즘

  • 사용자 1과 가장 유사한 사용자 A를 찾는다.
  • 사용자 A가 본 DVD 중에서 사용자 1이 보지 않은 DVD 목록을 D = {d_1, d_2, …, d_n}이라고 하자.
  • for d in D
    선호도가 가장 높은 d_m을 찾는다.

이 알고리즘을 적용하려면 사용자 1과 가장 유사한 사용자를 찾아야 하므로, 사용자 사이의 유사도를 먼저 계산해야 한다. 따라서 위의 추천 알고리즘은 아래와 같이 바꿀 수 있다.

추천 알고리즘

  • 사용자 사이의 유사도를 계산한다.
  • 사용자 1과 가장 유사한 사용자 A를 찾는다.
  • 사용자 A가 본 DVD 중에서 사용자 1이 보지 않은 DVD 목록을 D = {d_1, d_2, …, d_n}이라고 하자.
  • for d in D
    선호도가 가장 높은 d_m을 찾는다.

사용자 사이의 유사도 계산

그럼 추천 알고리즘을 차례 차례 계산해보자.

사용자 사이의 유사도를 계산하기 위해서는 사용자-아이템(DVD) 간의 정보를 행렬로 변환한다.

cf_user_item_matrix위의 행렬에서 사용자는 변수로 볼 수 있으며, 각 아이템에 대한 선호도는 해당 변수의 속성값으로 볼 수 있다. 즉, 변수 1은 101속성은 5.0, 102 속성은 3.0, 103 속성은 2.5 값을 각각 가진다. 그리고 각 변수는 7차원 평면에 존재하는 점으로 볼 수 있다.

이제 코사인 유사도를 사용해서 사용자간의 유사도를 계산해보자.

cosine_distance

vector_dot_prodcut

먼저 각 변수의 크기를 1로 정규화하기 위해 ||x||를 계산한 후, 속성 값을 ||x||로 나눈다. 즉 사용자 1 변수의 101 속성의 값은 아래와 같이 정규화할 수 있다.

cf_normalized_vector

따라서 위의 행렬의 속성값을 정규화한 행렬은 다음과 같다.

cf_user_item_matrix_normalized

이제 위 행렬을 사용하여 사용자간의 코사인 유사도를 계산해볼 수 있다. 예를 들어 사용자 1과 사용자 2사이의 코사인 유사도는 아래와 같이 계산한다.

cos(사용자1, 사용자2) = 0.788×0.319 + 0.473×0.399 + 0.394×0.798

따라서 사용자간의 유사도 행렬은 아래와 같이 계산하여 구할 수 있다. 이때 행렬은 대각선을 중심으로 대칭행렬이므로, 하단의 값은 계산하지 않아도 된다.

cf_user_user_matrix

아이템 추천하기

위의 사용자간의 유사도 행렬에서 사용자1과 가장 유사한 사용자는 유사도 0.755를 가지는 사용자 2다. 사용자2는 사용자1이 대여하지 않은 104 아이템에 대해 2.0 선호도를 가진다. 하지만 사용자 1에게 추천하기에는 선호도가 낮아보일 수도 있다.

그러면 사용자1과 다음으로 유사한 사용자 4를 살펴보자. 사용자 4 역시 사용자 1이 대여하지 않은 104 아이템에 대해 가장 높은 선호도 4.5를 주었다. 따라서 사용자 1에게 104 아이템을 추천하는게 가장 타당해 보인다.

여기에서는 계산을 단순화하였다. 하지만 실제 응용에서는 사용자 1에 유사한 사용자 그룹을 구한 후, 유사한 순서에 따라 우선순위를 부여하는 등의 작업을 해주어야만 더욱 정확한 추천을 할 수 있게 된다.

 

[프로그래머를 위한 데이터마이닝] #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)

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

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

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

참고자료

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