'실시간 추천엔진 머신한대에 구겨넣기' 50줄로 구현하기

추천 시스템에 관심이 생겨 찾아봤다면 한 번쯤은 실시간 추천엔진 머신한대에 구겨넣기라는 슬라이드를 마주쳤을 거라고 생각한다. 워낙 유명한 발표라 당시 페이스북에서도 많이 공유 되었던 것 같다. 나 역시 씀 : 일상적 글쓰기를 개발하면서 사용자들에게 구독, 혹은 담아 갈 만한 글을 추천해주고 싶었고, 어떤 식으로 구현할 수 있을지 알아보다 이 슬라이드를 발견했다. 처음 1/3 정도까지는 고개를 끄덕이며 술술 읽어 나갔는데, MinHash, LSH 같은 단어가 보이면서 점점 잠이 오더니, 어떻게 다 읽기는 했다만 ‘그래서 어떻게 한다고?’라는 생각을 하며 브라우저를 닫아 버렸다.

그렇게 몇 달간 추천 시스템은 잊고 지내다가, 최근 Cake 앱 개편 작업을 준비하며 홈 화면 개인화(=추천)라는 주제가 회의에서 이야기되었고, 불현듯 한 번 읽고 넘겨버린 이 자료가 생각나 간단하게 구현해 보기로 했다. 본격적으로 개발을 시작하기 전에, 발표에서 나온 개념들을 하나씩 짚고 넘어가 보자.

Jaccard Similarity

발표 자료에 쉽게 설명이 되어 있다. A가 좋아한 상품이 [1, 2, 3], B가 좋아한 상품이 [1, 2, 4], C가 좋아한 상품이 [1, 4, 5] 일 때 각 사용자들이 좋아한 상품을 기반으로 서로 얼마나 비슷한지 알아보는 것이다. 두 사용자 A, B의 Jaccard similarity는 다음과 같이 측정할 수 있다.

$$J(A,B) = \frac{|A \cap B|}{|A \cup B|}$$

예를 들어, 앞서 말한 A와 B의 Jaccard similarity는 아래와 같이 구할 수 있다.

$$\frac{|A \cap B|}{|A \cup B|} = \frac{|{1, 2}|}{|{1, 2, 3, 4}|} = 0.5$$

Ruby로 간단하게 구할 수도 있다.

1
2

a = [1, 2, 3]; b = [1, 2, 4]
(a & b).length / (a | b).length

MinHash

LSH는 발표 자료에 잘 설명이 되어 있는데, MinHash에 관해서는 Jaccard similarity를 유지하는 타입의 LSH라는 것 말고는 별다른 내용이 없다. ‘그래서 MinHash가 구체적으로 뭐지?’ 하는 의문이 들 수 있는데 찾아보면 의외로 간단한 개념이다. n 개의 원소로 이루어진 집합 S에 대하여, 보통 MinHash를 구하기 위해 사용하는 해시 함수는 아래와 같다.

$$h(x) = (a x + b)\bmod p$$

여기서 a와 b는 n보다 작은 임의의 자연수이며, p는 n과 같거나 큰 가장 작은 소수이다.

이전에 설명한 예시를 다시 가져와 보면, 전체 상품이 1 ~ 10까지 있다고 가정하면 n이 10이고, a = 2, b = 8, p = 11로 했을 때, 우리의 첫 번째 해시 함수는 아래와 같을 것이다.

$$h(x) = (2x + 8) \bmod 11$$

이 해시 함수에 사용자의 아이템을 전부 집어넣어 나온 값 중 가장 작은 값이 바로 MinHash 값이다(정확히는 해당 사용자에 대한 이 해시 함수의 MinHash 값). 예시에서 사용자 A의 경우 이 해시 함수를 사용했을 때 MinHash 값이 1, 사용자 B의 경우에도 1, 사용자 C의 경우에는 5가 된다. 그러면 우리는 사용자 A와 B가 같고, C는 다르다고 생각할 수 있다.

Signiture

MinHash 값을 구하는 과정을 보면 알겠지만, 두 사용자가 서로 다른 아이템을 가지고 있을 때도 MinHash 값은 같을 수 있다. 그래서 실제로 사용할 때는 a, b를 다르게 설정한 해시 함수를 많이 만들어서, MinHash를 여러 개 구하고, 이를 이어 붙여서 사용자의 Signiture를 만든다. 발표 자료에서는 100개를 추천하고 있다. 이렇게 만들어진 Signiture는 사용자 간의 유사도를 구하는데 사용된다. 예를 들어, 사용자 A의 Signiture가 [1, 0, 1, 6, 0]이고, 사용자 B의 Signiture가 [1, 0, 0, 6, 0]이면 둘은 80% 일치한다고 보는 것이다.

Secondary Index

이렇게 구한 Signiture로 사용자 간의 유사도를 구한다는 것은 알겠는데, 추천할 때마다 모든 사용자와 비교해서 비슷한 사용자를 찾는다면 속도에 이점이 전혀 없다. 그래서 발표에서 제시한 것이 Secondary Index이다. 사용자의 각 Signiture와 그 Signiture의 인덱스를 합친 키에, 값을 해당 사용자로 하는 Key-Value 저장소를 만드는 것이다.

글로만 보면 이해하기 어려우니 예시를 통해 더 알아보자. 앞서 예로 든 사용자 A의 Signiture [1, 0, 1, 6, 0]를 각각의 Index와 함께 묶어 키로 만들고, 값에는 사용자 A를 넣어서 Secondary Index를 만든다.

1
2
3
4
5
6
7

{
  '1-0' => ['A'],
  '0-1' => ['A'],
  '1-2' => ['A'],
  '6-3' => ['A'],
  '0-4' => ['A'],
}

잘 보면, 키가 Signiture-Index로 구성되어 있다. 여기에 사용자 B의 Signiture [1, 0, 0, 6, 0]도 넣어 보자.

1
2
3
4
5
6
7
8

{
  '1-0' => ['A', 'B'],
  '0-1' => ['A', 'B'],
  '1-2' => ['A'],
  '6-3' => ['A', 'B'],
  '0-4' => ['A', 'B'],
  '0-2' => ['B'],
}

사용자 B의 3번째 Signiture인 0이 0-2로 마지막에 들어갔다. 이제 임의의 사용자와 비슷한 사용자를 찾으려면 해당 사용자의 Signiture를 map 함수를 사용하여 Signiture-Index 형태로 변형하고, Secondary Index에서 가져오면 되겠다.

사용자 A의 Signiture [1, 0, 1, 6, 0]를 Signiture-Index 형태로 변형하면 ['1-0', '0-1', '1-2', '6-3', '0-4']가 되고, 이 키들을 가지고 Secondary Index 저장소에서 값을 가져오면 ['A', 'B'], ['A', 'B'], ['A'], ['A', 'B'], ['A', 'B']가 나올 텐데, 여기서 A를 제외하면 비슷한 사용자 B를 빠르게 찾을 수 있는 것이다. 또, 둘의 유사도는 B의 등장 횟수 4를 Signiture의 길이 5로 나눈 80%가 된다.

비슷한 사용자, 비슷한 아이템

발표 자료와 이 글을 함께 보고 있으면 이상한 점을 하나 발견할 수 있다. 이쯤이면 발표 자료는 아이템의 Signiture에 관한 설명을 하고 있기 때문이다. (54페이지) 분명히 처음에는 사용자 기반 협업 필터링이었던 것 같은데?

생각해 보면 이 방법은 비슷한 사용자를 추천하는데도 사용할 수 있고, 비슷한 아이템을 추천하는데도 사용할 수 있다. 다만 한 사용자가 100개 이상의 아이템을 선호하는 경우가 많을지, 한 아이템을 100명 이상의 사용자가 선호하는 경우가 많을지 생각해보면 아이템 추천 시스템을 만드는 것이 좀 더 일리 있어 보이기는 하다.

1) 비슷한 사용자를 추천하는 경우에는 임의의 사용자에게 좋아할 만한 아이템을 추천해 줄 수 있고, 2) 비슷한 아이템을 추천하는 경우에는 사용자가 임의의 아이템을 선호한다는 표현을 했을 때, 그와 비슷한 다른 아이템들을 소개해 줄 수 있을 것이다.

원래 만들고자 한 기능이 홈 화면에서 볼 만한 영상을 추천해주는 것이기 때문에 이 글에서는 첫 번째 방법으로 임의의 사용자에게 좋아할 만한 다른 아이템을 추천해 주는 기능을 구현할 예정이지만, 원한다면 반대로 구현해도 좋다.

50줄로 구현하기

Redis를 사용하는 부분을 제외하고, 발표에서 이야기하는 실시간 추천 엔진이 어떻게 돌아가는 것인지 Ruby로 간단하게 구현해 보자. 마지막의 전체 코드를 제외한 이 글의 모든 코드는 irb를 사용해서 테스트할 수 있도록 작성했다. 맥 사용자라면 터미널에서 irb를 실행하고 복사-붙여넣기만 해도 작동한다. 테스트 데이터는 발표 자료에 나온 것을 그대로 사용하면 되겠다. (14페이지)

1
2
3
4
5
6

@likes_data = [
  [2, 3],
  [1, 4, 5], # 2번째 사용자 (나)
  [1, 2, 4, 5],
  [2, 5],
]

Signiture의 길이는 10으로 하고, p = 7로 잡아서 MinHash를 구하기 위한 해시 함수를 만들어 보자. Signiture의 길이만큼 해시 함수가 필요하다. a는 소수, b는 2의 배수로 정해서 해시 함수의 결과를 반환하는 함수를 보자. 소수를 쉽게 가져오기 위해 prime 젬을 사용했다.

1
2
3
4
5
6
7

require 'prime'

@coefficient = Prime.take(10) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

def min_hash(index, value)
  (@coefficient[index] * value.to_i + 2 * index) % 7
end

2번째 사용자의 첫 MinHash 값은

1
2
3
4
5

[
  min_hash(0, 1),
  min_hash(0, 4),
  min_hash(0, 5),
].min # = 1

이고, 그 다음 Minhash 값은

1
2
3
4
5

[
  min_hash(1, 1),
  min_hash(1, 4),
  min_hash(1, 5),
].min # = 0

이다. 이런 식으로 구한 2번째 사용자의 Signiture는 [1, 0, 1, 6, 0, 2, 1, 4, 3, 1] 이다. 전체 사용자의 Signiture를 구하는 코드는 다음과 같다.

1
2
3
4
5
6
7

@signitures = @likes_data.map do |likes|
  [*(0...10)].map do |i|
    likes.map do |like|
      min_hash(i, like)
    end.min
  end
end

각 사용자의 Signiture는 아래와 같다.

1
2
3
4
5
6

[
  [4, 1, 0, 6, 2, 0, 0, 1, 1, 0],
  [1, 0, 1, 6, 0, 2, 1, 4, 3, 1], # 2번째 사용자 (나)
  [1, 0, 0, 6, 0, 1, 1, 3, 3, 1],
  [3, 1, 0, 6, 0, 1, 4, 3, 5, 2],
]

잠깐 멈춰서 계산을 해보자. 2번째 사용자의 Signiture는 1번째 사용자와 10%, 3번째 사용자와 70%, 4번째 사용자와는 20% 일치한다. 그러므로 우리는 3번째 사용자가 좋아한 아이템 중, 2번째 사용자가 좋아하지 않은 것을 추천해 주면 되겠다. (likes_data[2] - likes_data[1])

발표 자료에도 나와 있듯, 모든 사용자를 하나하나 비교하는 것은 비효율적이다. Signiture의 위치와 값으로 Secondary Index를 만들어, Secondary Index lookup 만으로 유사도를 계산해 보자. 우선 Signiture를 Secondary Index key로 변환하는 함수를 만들자.

1
2
3
4
5

def signiture_to_key(signiture)
  signiture.map.with_index do |sig, index|
    "#{sig}-#{index}"
  end
end

2번째 사용자의 Signiture를 이 함수에 넣고 돌리면

1

["1-0", "0-1", "1-2", "6-3", "0-4", "2-5", "1-6", "4-7", "3-8", "1-9"]

이렇게 뒤에 Index가 붙게 되는 것을 확인할 수 있다. 다음으로 이렇게 만든 키에 사용자 목록을 값으로 가지는 Secondary Index를 만들어 보자.

1
2
3
4
5
6
7
8
9

@secondary_index = {}

@signitures.map.with_index do |signiture, user|
  keys = signiture_to_key(signiture)
  keys.each do |key|
    @secondary_index[key] ||= []
    @secondary_index[key] << user
  end
end

만들어진 Secondary Index 목록은 아래와 같다. 2번째 사용자의 Secondary Index key를 찾기 쉽도록 순서를 약간 바꿨다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

{
  "1-0"=>[1, 2],
  "0-1"=>[1, 2],
  "1-2"=>[1],
  "4-0"=>[0],
  "6-3"=>[0, 1, 2, 3],
  "0-4"=>[1, 2, 3],
  "2-5"=>[1],
  "1-6"=>[1, 2],
  "4-7"=>[1],
  "3-8"=>[1, 2],
  "1-9"=>[1, 2],
  "1-1"=>[0, 3],
  "0-2"=>[0, 2, 3],
  "2-4"=>[0],
  "0-5"=>[0],
  "0-6"=>[0],
  "1-7"=>[0],
  "1-8"=>[0],
  "0-9"=>[0],
  "1-5"=>[2, 3],
  "3-7"=>[2, 3],
  "3-0"=>[3],
  "4-6"=>[3],
  "5-8"=>[3],
  "2-9"=>[3],
}

이제 우리가 임의의 사용자를 집어넣으면, 그 사용자와 비슷한 다른 사용자를 반환해 주면 된다. 이미 Secondary Index까지 만들어 두었으니, 할 일은 그저 임의의 사용자의 Signiture를 Secondary Index key로 변환하고, Secondary Index에서 값을 읽어 와서 모두 합치는 것뿐이다. 두 번째 사용자와 비슷한 사용자를 찾는 코드는 다음과 같다.

1
2
3
4

signiture_to_key(@signitures[1]).reduce([]) do |users, key|
  users << @secondary_index[key]
end
# [[1, 2], [1, 2], [1], [0, 1, 2, 3], [1, 2, 3], [1], [1, 2], [1], [1, 2], [1, 2]]

각 Signiture 별로 일치하는 사용자 목록을 가져온 것이다. 이제 사용자 아이디의 등장 횟수를 세어 보자.

1
2
3
4
5
6
7
8
9
10
11
12
13

signiture_to_key(@signitures[1]).reduce([]) do |users, key|
  users << @secondary_index[key]
end.flatten.
  # [1, 2, 1, 2, 1, 0, 1, 2, 3, 1, 2, 3, 1, 1, 2, 1, 1, 2, 1, 2]
  group_by(&:itself).
  # {
  #   1=>[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  #   2=>[2, 2, 2, 2, 2, 2, 2],
  #   0=>[0],
  #   3=>[3, 3]
  # }
  transform_values(&:count)
  # {1=>10, 2=>7, 0=>1, 3=>2}

실행하면 아래와 같이 출력된다.

1

{1=>10, 2=>7, 0=>1, 3=>2}

자기 자신과는 100% 일치, 3번 사용자와 70% 일치, 1번 사용자와 10% 일치, 4번 사용자와 20% 일치한다. 앞서 우리가 계산한 결과와 같다. 조금 더 욕심을 부려 보자면, 가장 비슷한 한 명을 찾아볼 수 있겠다.

1
2
3
4
5
6
7
8
9

signiture_to_key(@signitures[1]).reduce([]) do |users, key|
  users << @secondary_index[key]
end.flatten.
  group_by(&:itself).
  transform_values(&:count).
  sort_by { |key, value| -value }.
  # [[1, 10], [2, 7], [3, 2], [0, 1]]
  slice(1)
  # [2, 7]

2번 유저가 70% 일치한다고 나올 것이다. 마지막으로 비슷한 사용자를 기반으로 아이템을 추천해 주는 함수까지 만들어 보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def recommended_for(user)
  neighbor = signiture_to_key(@signitures[user]).reduce([]) do |users, key|
    users << @secondary_index[key]
  end.flatten.
    group_by(&:itself).
    transform_values(&:count).
    sort_by { |key, value| -value }.
    slice(1).
    first

  @likes_data[neighbor] - @likes_data[user]
end

# puts recommended_for(1)

전체 코드는 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

require 'prime'

@coefficient = Prime.take(10) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

def min_hash(index, value)
  (@coefficient[index] * value.to_i + 2 * index) % 7
end

def signiture_to_key(signiture)
  signiture.map.with_index do |sig, index|
    "#{sig}-#{index}"
  end
end

def recommended_for(user)
  nearest_neighbor = signiture_to_key(@signitures[user]).reduce([]) do |users, key|
    users << @secondary_index[key]
  end.flatten
    .group_by(&:itself)
    .transform_values(&:count)
    .sort_by { |key, value| -value }
    .slice(1)
    .first

  @likes_data[nearest_neighbor] - @likes_data[user]
end

@likes_data = [
  [2, 3],
  [1, 4, 5], # 2번째 사용자 (나)
  [1, 2, 4, 5],
  [2, 5],
]

@signitures = @likes_data.map do |likes|
  [*(0...10)].map do |i|
    likes.map do |like|
      min_hash(i, like)
    end.min
  end
end

@secondary_index = {}

@signitures.map.with_index do |signiture, user|
  keys = signiture_to_key(signiture)
  keys.each do |key|
    @secondary_index[key] ||= []
    @secondary_index[key] << user
  end
end

puts recommended_for(1)

recommended_for 함수의 인자를 변경해 가며 각 사용자가 어떤 아이템을 추천받는지 확인해 볼 수 있다. 여기서 더 나아가면 비슷한 사용자 한 명이 아니라 여러 명을 가져와서 선호 데이터를 더 늘릴 수도 있고, @likes_data, @signitures, @secondary_index를 Redis를 통해 관리할 수도 있다. 여기까지 구현한 코드는 이곳에서 확인할 수 있다.

Comment and share