Code Sprint 2015 Round 2 – 그리디 알고리즘으로 빠르게 클러스터링하기

안녕하세요. 2015 Code Sprint Round 2에서 1위로 입상한 전실라입니다.

문제 개요

라운드 2는 VOD 추천 (구매 예측) 알고리즘을 개발하는 것으로 2015년 3월에 고객들이 구매할 영화를 예측하는 것이 목표입니다. 제공 데이터로 대상 고객들의 지난 6개월 간의 구매 기록과 구매 VOD의 정보가 주어집니다. 문제 설명과 채점 설명(학습과 실행에 관한 설명)을 읽고 머신 러닝 문제로 판단하였습니다.

풀이

문제를 풀기 위해 간단한 방식으로 머신 러닝의 클러스터링을 구현했습니다. 다음은 코드와 함께 제출한 Readme 파일의 일부를 발췌하였습니다.

이 프로그램은 영화를 연관 집합으로 만들어 구매 영화를 예측한다. 어떤 고객이 여러 영화를 보았다면 그 영화들 각각의 쌍은 연관 점수를 1점 얻는다. 모든 고객에 의해 얻어진 연관 점수는 영화 X 영화의 행렬로 표현된다. 가장 높은 연관점수를 가진 영화 쌍부터 차례로 Greedy 방식으로 집합을 만든다. 방법은 다음과 같다.

A. 영화 쌍이 둘 모두 어떤 집합에도 포함되지 않았다면 둘을 묶어 하나의 집합으로 만든다.

B. 만약 영화 쌍의 한 쪽만이 집합에 포함되어 있다면 집합에 포함되지 않은 영화도 그 집합에 포함시킨다.

C. 만약 이미 두 영화가 서로 다른 집합에 포함되어 있다면 무시한다.

영화 집합 만들기가 끝나면 각 고객을 대상으로 추천 영화 목록을 만든다. 이 때는 고객이 기존에 구매했던 영화들이 어떤 집합에 속하는지를 확인한 후 가장 많은 영화를 본 집합부터 차례로 고객에게 적절한 수(후에 설명)의 영화를 인기도 순으로 추출하여 제공한다.

이는 Greedy, 탐욕 알고리즘으로 구현한 클러스터링이라고 할 수 있습니다. 클러스터링을 고객 위주로 하지 않고 영화 위주로 한 것은 그 수의 차이 때문이었습니다. 문제 출제 후기에서도 언급된 내용과 같이 고객은 9만여명, 영화는 8천여개이기 때문에 속도와 메모리의 차이도 있을 뿐만 아니라, VOD를 5개 미만의 적은 수만 구매한 고객이 매우 많았기에 고객 위주로는 제대로 된 클러스터링이 불가능할 것으로 보았습니다.

그리디로 구현된 특성 때문에 속도는 매우 빨랐습니다.  학습과 실행을 합하여 2분 내에 결과가 나왔습니다. 이런 빠른 속도는 프로그램 개선을 위해 다양한 시도를 할 수 있는 조건이 되었습니다.

개선

알고리즘을 개선할 수 없을까 고민하며 몇 가지 시도를 해보았습니다. 먼저 수정한 알고리즘으로 만든 결과물을 매번 제출해볼 수는 없기 때문에 (하루 최대 3번만 제출할 수 있습니다), 자체적으로 채점할 수 있는 기준이 필요했습니다. 그래서 Adaptive MAP(라운드 2의 채점 기준)을  직접 구현하였습니다. 이 프로그램이 잘 만들어졌는지 검증이 필요했는데 3월의 구매기록을 구할 수는 없으니 직접 대조해보는 것은 불가능했습니다. 그래서 14년 9월~15년 1월까지의 구매기록으로 학습시켜서 2월의 구매기록을 기준으로 채점을 해보았고, 이 때의 점수가 공식 채점 점수와 비슷하게 나오는 것을 확인하고 공식 채점 프로그램에 가깝게 구현된 것으로 생각하고 사용하였습니다.

다음은 시도해 보았지만 실제로 적용되지는 않은 개선안들입니다.

  • 첫 번째로 제 알고리즘에 문제점이 없는지 확인하였습니다. 위의 알고리즘 구현을 보시면 C번의 연관성 무시를 확인하실 수 있습니다. 이때 무시된 연관 점수가 앞서 연관 집합을 만들 때의 점수보다 현저히 낮다면 이 점수를 무시하는 것이 타당하지만, 별로 점수 차이가 나지 않는데 집합 구성 순서 때문에 무시되었다면 잘못된 클러스터링을 할 수 있습니다. 원래 하나로 묶여야 할 클러스터들이 순서 차이 때문에 나눠지는 것이죠. 이런 문제가 있는지 확인하기 위해 C번 룰에 의해 무시되는 연관 점수와 A번 룰에 의해 집합을 구성한 연관 점수의 차이를 살펴보았는데 이때 두 점수의 차이는 500점을 넘겼습니다. 이는 상대적으로 매우 큰 수치라서, 제공된 데이터에 대해서는 문제가 없는 알고리즘인 것을 확인하였습니다.
  • 두 번째로 다른 방식으로 연관점수를 만들어 클러스터링을 구현해보았습니다. 파이썬의 Numpy 모듈의 corrcoef 함수를 사용했는데, 이를 바탕으로 구매 예측을 해보았을 때의 점수가 위의 알고리즘을 사용하였을 때보다 낮아서 기존 알고리즘을 사용하기로 하였습니다.
  • 세 번째로 특정 고객의 VOD의 중복 구매를 이용한 시도였습니다. 구매기록을 분석하다 보니 어떤 고객들은 같은 VOD를 짧은 기간 내에 여러 번 구매한다는 것을 확인하였습니다. 그래서 2월 말 즈음에 구매한 VOD를 3월에 다시 추천해보는 것을 시도해보았습니다. 하지만 재구매가 흔치 않게 발생하는 만큼 예측에 도움이 되지 않는 것 같아서 최종 알고리즘에서 제외하였습니다.

다음은 실제로 적용된 개선안입니다.

  • 첫 번째로 영화 간의 연관성이 시기적으로 변화한다고 판단하였습니다. VOD 광고나 판매 플랫폼의 정책, 특정 배우/감독의 인기 상승 등이 원인이 될 수 있겠죠. 그래서 연관 점수를 얻기 위한 제공 데이터 분석을 처음에는 6개월의 모든 기간에 적용하다가 마지막에는 마지막 15일에 대해서만 적용하도록 수정하였습니다. 한편 고객이 관심을 가질만한 클러스터를 찾을 때는 고객의 구매 기록이 많이 필요했기 때문에 최근 3개월 간의 구매 기록을 참고하였습니다.
  • 두 번째로 고객에 따라 추천 영화 개수를 조정하였습니다. 처음에는 고객이 기존에 구매한 영화의 개수에 비례하게 영화를 추천하였습니다. 10개를 구매하였으면 3개를, 100개를 구매하였으면 30개를 추천하는 식이죠. 그런데 라운드2의 채점 방식에 따르면, 고객이 실제로 구매한 영화보다 적은 수의 영화를 추천하더라도 정확한 영화를 추천한다면 높은 점수를 받을 수 있습니다. 말하자면 10개 영화를 구매한 고객에게 10개 중 1개만 추천하고 이를 정확히 맞춘다면 그 고객에 대해서는 만점을 받을 수 있습니다. 이를 바탕으로 생각해보면 위와 반대의 방식으로 추천하는 게 점수를 높일 수 있다는 것을 알 수 있습니다. 고객이 영화를 30개 정도 볼 것으로 예상된다면, 해당 고객은 소속된 클러스터에서 가장 인기 있는 영화를 볼 가능성이 매우 높습니다. 그래서 그 영화 하나만을 추천하는 거죠. 반대로 영화를 적게 구매할 고객의 영화는 예측하기가 어렵습니다. 그래서 다수의 영화를 추천하여 그 중의 일부만이라도 맞게 하여 조금의 점수라도 얻어내는 게 유리하죠.

후기

사실 저는 라운드 2에 도전하며 머신 러닝을 처음 공부했습니다. 잘 할 수 있을지 자신도 없어서, 일단 첫 하루만 시간을 투자해서 결과가 어떻게 나오는지 보고 계속 할지 말지를 결정할 생각으로 시작했습니다. 그런데 조금씩 알고리즘을 개선해나가며 점수가 올라가는 것이 너무 재미있었고, 그러다 보니 원래 대회 기간 중에 예정되어있던 학회 엠티도 불참하고 밤낮 없이 도전하게 된 것입니다. 참 즐겁고 의미 있는 시간이었습니다. 한 번쯤 공부해보고 싶었던 머신 러닝 분야에 발을 들여놓는 계기도 된 것 같고요. 좋은 대회 준비해주신 관계자 여러분께 감사 드립니다.

전실라

성균관대학교에서 전자전기 공학과 컴퓨터 공학을 공부하고 있습니다. ACM ICPC 등의 알고리즘 프로그래밍 대회에 관심이 있습니다.

공유하기