정말 오래간만에 작성하는 글이다. 아랑고DB 관련 글을 진작 마무리했어야 했는데 그러지 못했다. 🤦🏻♂️
이번 글에서는 지난 글에 이어 그래프를 활용한 추천 시스템을 실습하려고 한다.
1. 들어가기에 앞서
일단 지난 시간에 아랑고DB에 넣어둔 데이터를 확인해보자. 보다 복잡한 분석을 위해서는 파이썬을 통해 아랑고DB에 AQL을 날려서 데이터를 주고받고 해야하지만 여기서는 최대한 간단한 형태의 추천 시스템을 실습할 것이기 때문에 오로지 AQL을 통해서만 결과를 낼 것이다.
아랑고DB 웹 UI로 들어가서 movie_ratings 데이터베이스를 선택한 후, 좌측의 QUERIES 메뉴를 클릭하자.
웹UI 관련 설정이 기억나지 않거나 이슈가 있으면 이 글에서 Web UI 세팅 부분을 다시 살펴보자.
2. 데이터 살펴보기
이제 실제로 데이터가 잘 들어갔는지 확인해보자.
우선 각 컬렉션의 데이터 개수를 확인한다. COLLECTIONS에서 각 컬렉션을 들어가서 좌측 하단의 데이터 개수를 확인해도 되는데, 여기서는 AQL을 통해 확인해보겠다.
// AQL은 하나의 리턴만 하기 때문에 아래를 각각 실행시켜줘야 함에 주의
RETURN length(rated) // 84942
RETURN length(User) // 1000
RETURN length(Movie) // 17763
유저는 천 명으로 제한했었기 때문에 딱 1000개의 레코드가 있고, 영화는 17763개, 그리고 평가는 84942개가 있다.
이번에는 유저별, 영화별, 년도별 평가의 개수를 확인해보자.
// AQL에서 통계값을 뽑는 관련 함수는 없는 것 같다. 각각을 개별 계산해준다.
LET rates = (
FOR e IN rated
COLLECT
user = Document(e._from).user
AGGREGATE
cnt = COUNT(1)
RETURN {
user,
cnt
}
)
RETURN {
min: min(rates[*].cnt),
max: max(rates[*].cnt),
avg: avg(rates[*].cnt)
}
위 쿼리는 일단 유저별로 평가의 개수를 모아준 뒤에(rates), 이 배열에서 cnt의 최소, 최대, 평균값만을 다시 계산한 결과이다.
유저들은 최소 20개에서 최대 2500개(!)의 평가를 내렸고, 평균적으로 84개의 평가를 내렸다. 아마 애초에 Netflix Prize에 사용되었던 데이터이기 때문에 양질의 평가를 한 사람들만을 추려놓은 것이라 생각된다.
// 영화별 rating 개수
FOR e IN rated
COLLECT
movie = Document(e._to).name
AGGREGATE
cnt = COUNT(1)
SORT cnt DESC
RETURN {
movie,
cnt
}
쿼리는 아까와 유사하다. 그룹을 해주는 기준만 영화 타이틀로 바뀌었을 뿐이다. 같은 통계를 내보면, 최소 1개의 평가가 있는 영화부터, 최대 640개의 평가가 있는 영화까지 다양하다. 평균적으로 22개의 평가가 있다.
오해하면 안 될 것이, 전체 Netflix의 평가가 아닌, 내가 임의로 선별한 아주 작은 데이터가 그렇다는 것이다.
// 이번에는 년도별로
FOR e IN rated
COLLECT
date = SUBSTRING(e.date, 0, 4)
AGGREGATE
cnt = COUNT(1)
SORT cnt DESC
RETURN {
date,
cnt
}
얘는 따로 통계를 볼 필요가 없다. 위 쿼리만 실행해도 2000년~2005년 사이 년도별 개수가 나오기 때문이다. 확실히 오래된 데이터라 2005년 데이터가 가장 많다.
3. 협업 필터링(Collaborative Filtering, CF)
이번 실습에서는 추천 시스템의 한 가지 방법인 협업 필터링을 사용한다. (간단히 CF라고 줄여서 부르겠다)
CF는 가장 널리 사용되는 기법 중 하나이고, 이름 그대로 주변 사람들의 정보를 이용하여 (협업, collaborate) 예측을 만들어내는 (filtering) 기법이다.
위키피디아의 예시를 가져와보면, CF의 기본 아이디어는 아래와 같다.
- 유저 A와 유저 B가 1번 주제에 대해 의견이 같다고 가정하자.
- 그럼 A는 임의의 유저보다, 또다른 2,3,4.. 주제에 대해서도 B와 의견이 같을 확률이 높을 것이다.
즉, 비슷한(similar) 유저일수록 취향이 비슷할 것이고, 그 점을 기반으로 추천 값을 만들어내는 것이다.
CF에도 여러가지 종류가 있는데, 크게는 메모리 기반(Memory-based or Neighborhood-based)과 모델 기반(Model-based)로 분류된다.
- Memory based CF : ‘메모리’ 기반에서는, 메모리에 주어진 ‘데이터’ 내에서 여러 계산을 거쳐 추천 값을 생성한다.
- Model based CF : ‘모델’ 기반에서는, 주어진 ‘데이터’를 통해 모델을 학습시켜서 이 모델이 추천 값을 생성하도록 한다.
추천 시스템에 관해 공부하고, 설명할 내용은 정말 많이 있다. CF도 자세하게 들어갈 수 있고, 이 외의 추천 방법론, 그리고 평가가 implicit 할 때의 방법 등.. 다룰 내용이 많다. 이건 기회가 되면 따로 시리즈로 작성해보도록 해야겠다. 😃
4. 메모리 기반 CF
여기서는 메모리 기반 CF를 쓸 건데, 메모리 기반도 크게 두 가지 종류로 나뉜다.
A 유저의 아이템 B에 대한 평가를 예측한다고 할 때, 각각은 아래처럼 해석할 수 있다.
- User-based : A 유저와 비슷한 성향을 가진 다른 유저들이 B에 대해 어떤 평가를 내렸는지 종합해본다.
- Item-based : B 아이템과 비슷한 성향을 가진 다른 아이템들에 대해 A가 어떤 평가를 내렸는지 종합해본다.
여기서는 user-based CF를 사용할 예정이다. 다양한 가정에 따라 다양한 수식을 적용할 수 있으니 함께 찬찬히 살펴보자.
1) CF with equal similarity
가장 일반적인 형태는 아래와 같다.
[r_{u,i} = \frac{1}{N}\sum_{u \prime \in U}r_{u \prime, I}]
위 수식의 좌변은 유저 $u$가 아이템 $i$에 대해 내릴 평가를 의미한다. 이는 예측값이다.
우변은 타겟 유저와 유사한 성향을 가진 집합 $U$에 속한 $u\prime$ 들이 상품 $i$에 대해 내린 평가를 다 더한 뒤, 집합의 크기인 N으로 나누어주고 있다. 즉, 타겟 유저의 아이템 $i$에 대한 평가를 예측하기 위해, 유사한 상위 N명의 $i$에 대한 평가를 평균낸 것이다. ($i$에 대해 평가한 사람들에 한해서 걸러내기 때문에 각 아이템마다 이 그룹은 달라진다)
일단 유사도라는 값은 이미 주어진 값이라고 생각하고, 아래에서 간단히 짚고 넘어가겠다.
2) CF with different similarity
여기서 의문을 가질 수 있는 부분이 있다. 유사한 상위 N명에 대해 그들의 점수를 평균내는 것은 이해하겠는데, 이들 중 누군가는 정말 비슷한 취향을 가졌을 것이고, 누군가는 그다지 취향이 맞지 않을 수도 있다.
따라서, 유사 그룹의 점수를 평균 내는 것이 아닌, 유사도에 따라 가중 평균을 해줄 수 있다.
[r_{u,i} = k \sum_{u \prime \in U}sim(u, u\prime)r_{u\prime, i}]
위 식에서 실제로 k값은 $ 1/ \sum_{u\prime \in U}|sim(u, u\prime)| $에 해당한다. 즉 가중 평균이기 때문에 가중치들의 합으로 나눠주는 것이다.
3) CF with different similarity, rating adjusted
더 나아가, 평가 점수 자체에 대한 의문을 제기할 수 있다. A 유저는 점수를 후하게 주는 사람이고, B는 그렇지 않은 사람일 때, A의 4점과 B의 2점은 비슷한 평가 수준일 수 있다. 그럼, 개인이 점수 주는 범위를 계산해서, 잘 스케일링 할 수 있지 않을까?
[r_{u,i} = \bar r_u + k \sum_{u \prime \in U}sim(u, u\prime)(r_{u\prime, i} - \bar r_{u\prime})]
2번 식과 달라진 부분은, 유사 사용자의 평가를 그대로 쓰는 대신, 평균 중심화(mean-centered) 된 값을 가중평균하고, 거기에 타겟 사용자의 평균 점수를 다시 더해준다는 점이다.
즉, 사람마다 평가 기준이 다르기 때문에 이를 나름대로의 표준화 과정을 거친 상태에서 가중 평균을 해주고, 거기에 다시 타겟 사용자의 평균값을 더해준다는 의미이다.
4) CF in graph
CF는 구현 방식이 정말 다양하기 때문에 그래프DB의 특성을 살려서 구현을 할 수도 있다. 예를 들어, ‘유사도’라는 개념을 ‘A 사용자 노드에서 k 스텝을 랜덤 워크 했을 때, 많이 겹치는 정도’라고 정의할 수도 있다. 즉, A 사용자에서 출발해서 임의의 그래프 횡단을 했을 때, 특정 사용자에게 많이 도달할수록 유사한 타겟이라는 의미가 된다.
Disclaimer
다만, 여기서는 1번 수식을 채택한다. 모두가 동일한 가중치를 가지고 있다고 가정하고, 가장 간단한 형태의 계산만을 할 것이다. 아랑고DB에 중점을 둔 글이기 때문에 이렇게 문법을 쓸 수 있다는 것에 집중하고, 추천 시스템의 정확한 프로세스와 검증 과정은 추천 시스템 관련 글에서 다루도록 하겠다!
5. 그래프를 통한 유사도 계산
이제 실전으로 넘어가보자!
유사도를 계산하는 방법은 피어슨 상관계수를 쓰거나, 코사인 유사도를 쓰는 방법 등이 있다. 여기서는 더 구현이 편한 코사인 유사도를 사용한다.
[cos(\vec x, \vec y) = \frac{\sum_{i\in I_{xy}}r_{x,i}r_{y,i}}{\sqrt {\sum_{i \in I_x}r_{x, i}^2} \sqrt {\sum_{i \in I_y}r_{y, i}^2}}]
위 수식들을 그래프DB로 되살려보자. 여기서는 전체 데이터셋에 대한 추천값을 계산하지 않고, 임의의 타겟 사용자 1명에 대해, Top-K 영화를 추천해 볼 것이다. 유사 그룹은 30명 사이즈라고 가정하겠다.
아래 AQL은 단순 구현을 위해 만들어졌기 때문에 효율적이지 않다. 데이터 재사용이 적고, 반복 계산이 많기 때문에 시간이 오래 걸린다. 여기서는 구현 자체만을 신경썼기에 실제로 구현을 할 예정이라면 글의 마지막을 참고하자.
LET target = Document('User/1158991')
LET sim = (
//1
LET movies_target = (
FOR movie, e, p IN OUTBOUND target rated
RETURN e
)
//2
LET movies_target_distinct = FLATTEN(UNIQUE(
RETURN movies_target[*]._to
))
//3
LET movies_target_ratings_square = (
RETURN SUM(movies_target[* RETURN POW(CURRENT.rating, 2)])
)
//4
LET users_with_same_movie = (
FOR movie IN OUTBOUND target rated
FOR other_user IN INBOUND movie rated
FILTER target != other_user
RETURN DISTINCT other_user
)
//5
FOR other_user IN users_with_same_movie
LET movies_other = (
FOR movie, e, p IN OUTBOUND other_user rated
RETURN e
)
LET movies_other_distinct = FLATTEN(UNIQUE(
RETURN movies_other[*]._to
))
LET movies_other_ratings_square = (
RETURN SUM(movies_other[* RETURN POW(CURRENT.rating, 2)])
)
LET dot_product = SUM(
FOR movie IN INTERSECTION(movies_target_distinct, movies_other_distinct)
LET score_target = movies_target[* FILTER CURRENT._to == movie].rating
LET score_other = movies_other[* FILTER CURRENT._to == movie].rating
RETURN score_target * score_other
)
LET cosine_sim = dot_product / (SQRT(movies_target_ratings_square) * SQRT(movies_other_ratings_square))
SORT cosine_sim DESC
RETURN {
other_user,
cosine_sim
}
)
위 쿼리는 일단 타겟 사용자(target)을 임의로 지정해준다. 그리고 이 타겟과 나머지 사용자에 대한 유사도를 계산해주고 있다.
- 1: 타겟 사용자가 평가한 영화와 그 엣지를 모은다
- 2: 타겟 사용자가 평가한 고유 영화를 모은다
- 3: 타겟 사용자가 평가한 점수의 제곱의 합에 루트를 씌운 값. 즉, 코사인 유사도에서 $ \lVert \vec x\rVert $ 에 해당하는 값
- 4: 2번에서 모은 영화를 함께 본 사용자의 목록. 어차피 함께 본 영화가 없다면 유사도가 없기 때문에 이들은 쿼리의 효율성을 위해 신경쓰지 않는다
- 5: 4번에서 대상 유사 그룹에 대해, 그들의 $ \lVert \vec y \rVert$ 값과, 타겟과 그들의 스칼라 곱($ \vec x \cdot \vec y $)을 구한다
그리고 이어서 다음 쿼리가 진행된다 (글에서는 분리했지만, 위 쿼리에 바로 이어서 실행된다)
FOR movie IN Movie
// 1
LET inflow = FIRST(
FOR v, e, p IN INBOUND movie rated
COLLECT WITH COUNT INTO length
RETURN length
)
FILTER inflow >= 30
// 2
LET candidates = (
FOR user IN INBOUND movie rated
FILTER user != target
RETURN DISTINCT user
)
// 3
LET predict_score = AVG(
FOR doc IN sim
FILTER doc.other_user IN candidates
LIMIT 30
FOR v, e, p IN OUTBOUND doc.other_user rated
FILTER v == movie
RETURN e.rating
)
SORT predict_score DESC
RETURN {
'name': movie.name,
predict_score
}
이제 타겟 사용자의 전체 영화에 대한 예측 평점을 구할 차례이다.
- 1: 전체 영화를 순회하되, 유의미한 선별을 위해 평가가 30개 이상인 영화만 남긴다 (평가가 없는 cold start 문제는 다른 방법으로 해소해 줘야 한다! 여기서는 무시함)
- 2: 해당 영화를 본 사람들의 목록을 만든다
- 3: 처음에 구한 (타겟, 다른 유저) 유사도를 순회하며, 함께 이 영화를 본(2번 목록에 있는) 사람들의 점수를 평균낸다. 유사 그룹은 30명으로 제한한다.
이렇게 결과값을 내면 아래 그림처럼 타겟이 좋아할만한 영화의 점수와 순위를 매길 수 있다!
이런 식으로 전체 유저에 대해 적용하면, 가장 단순한 형태의 CF를 구현해 볼 수 있다. 단, 그래프DB를 통해 더 깊이 들어갈 예정이라면 아래 6번은 꼭 읽어보자!
6. 그래프DB를 CF에 적용할 때의 어려움, 주의점
메모리 기반 CF에서 계산의 핵심은 유사도를 구하는 작업이다. 사용자와 사용자, 혹은 아이템과 아이템 사이의 유사도를 구해야하는데, 이는 $O(m^2)$의 복잡도를 갖는다. 따라서 대상의 수가 늘어날수록 급격하게 계산의 비용이 높아진다.
사실 그래도, 작은 규모의 데이터에서는 파이썬의 행렬 곱을 통해 유사도 행렬을 쉽게 구할 수가 있는데, 그래프DB에서는 그렇지가 않은 것 같다. 그래서 위 AQL도 반복적인 계산이 많고, 비효율적으로 구성된 것 같다. (분명 코드 개선의 여지는 있다! 근데 여기선 그게 중점이 아니어서 일단 넘어감 😂)
결론적으로, 일반적인 메모리 기반 CF를 구현하는 게 목적이라면, 그냥 파이썬을 사용하기를 추천드린다. 그래프DB를 활용하려면 유사도와 같이 계산 집약적인 작업은 파이썬으로 넘기고, 탐색 관련 작업을 그래프로 구현하는 것이다. 그렇게 하려면 그래프 초기 설계부터 잡고 들어가는 게 맞다. 즉, 사용자 A와 B 사이에 유사도 엣지를 추가하는 등의 방법을 쓰는 것!
7. 아랑고 시리즈를 마치며
이 글을 포함하여 무려 11편의 아랑고DB 시리즈가 끝이 났다. 아랑고DB를 접한 뒤, 꼭 그래프DB에 대한 가이드를 만들고 싶었기에 꾸준히 작성해왔는데, 돌아보니 시작하길 잘했다는 생각이 든다 :)
Neo4j가 주류인 상황에서 아랑고DB를 검색하는 한국 사용자가 얼마나 될까 싶지만, 그래프DB에 대한 간단한 개념을 익히기에는 아랑고DB만한 게 없다고 생각한다. 누군가에게는 가뭄의 단비처럼… 도움이 되길 바란다.
아랑고 시리즈를 읽어주셔서 감사하다는 말씀을 전하며, 저는 또 다른 글로 찾아 뵙도록 하겠습니다! 감사합니다.
- 아랑고DB란? 왜 쓰는가?
- 아랑고DB 세팅하기 on Ubuntu
- 아랑고DB 쉘로 붙어서 명령어 체험해보기, 실체 파악해보기
- AQL(Arango Query Lang) 배워보기 1
- AQL(Arango Query Lang) 배워보기 2 - RETURN / UPDATE
- AQL(Arango Query Lang) 배워보기 3 - REPLACE / UPSERT / REMOVE
- 그래프 개념잡기
- 그래프 횡단하기 Graph Traversal
- 데이터 모으기 COLLECT / AGGREGATE / MIN_BY, MAX_BY
- 프로젝트. 그래프를 통한 영화 추천시스템 만들어보기 1
- (지금 보고있는 글) 프로젝트. 그래프를 통한 영화 추천시스템 만들어보기 2 (최종편)
