Category Archives: Data Analysis

점진적으로 평균 구하기

다음과 같이 집합 V에 n개의 숫자가 있는 경우,

avg_set

평균은 아래와 같이 구한다.

avg_general
하지만 집합의 원소를 한번에 하나씩만 얻어야 하는 경우 위의 공식으로 평균을 구하려면 반복문을 2개를 사용해야 한다. 하나의 반복문을 써서, 평균을 점진적으로 구하고자 한다면 아래의 공식을 사용한다.

avg_inc

 

과거에 평균을 점진적으로 구해야 하는 상황이 있었던 적은 없었다. 다만 그냥 끄적여 본 글이었다. 하지만

2년 후…

어떤 글로벌 기업에 코딩 테스트를 치뤘던 적이 있다. 문제 난이도는 soso였는데, 마지막 문제가 사용자가 1억명이 있는데, 각 사용자별 아이템 소모의 평균 값을 구하는 문제였다. 그렇게 제출했더라면 코딩 테스트를 탈락했을거다.

다행히도 이 글이 생각이 나서 점진적으로 평균을 구하도록 알고리즘을 수정했다. 함정은 1억명 유저의 각 평균을 효율적으로(어느정도 정확하다면) 구하는 것이었다.

 

[프로그래머를 위한 데이터마이닝] #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에 유사한 사용자 그룹을 구한 후, 유사한 순서에 따라 우선순위를 부여하는 등의 작업을 해주어야만 더욱 정확한 추천을 할 수 있게 된다.