netflix prize라는 해당 사용자가 보지 않은 영화의 점수를 예측하는 시스템을 만드는 대회이다.
상금이 무려 100만달러에 육박한다…@.@

이것을 접하게된 계기는 hadoop mapreduce를 이용한 canopy clustering에 대한 자료를 찾다가 이 숙제 데이터셋을 보고 알게 되었다.

netflix prize사이트에 가면 많은 설명이 되어 있고, 이 블로그에 가면 쉽게 정리된 자료를 볼 수 있다.

아무래도 서비스를 위한 빠른 알고리즘을 원하기 보다 정확도가 중요한 측정 방법인데, 그래도 데이터를 입력하면 빠르게 결과를 보여주는 방향이 바람직하기 때문에 Item based filtering 방법으로 만들어 보고자 한다. 그러기 위해서는 영화데이터에 대한 클러스터링이 필수적일 것이다.

먼저 등록을 하고 받은 10억건이 넘는 데이터… 압축하지 않은 총 학습 데이터셋이 2G에 육박하는데 이 데이터셋을 주말을 이용해 야후 사내에서 직원들에게 공개한 리서치용 hadoop 클러스터에 넣어두었다.

먼저 영화에 대한 레코드로 배열이 되어 있으니 map reduce를 이용해서 user id를 키로하는 데이터로 만들었다. 이것들은 추후 영화 데이터를 canopy clustering하기 위한 canopy를 만드는데 빠른 룩업을 위한 역파일(?)로 사용된다.

hadoop을 사용해서 k-means 클러스터링을 수행할 것이기 때문에 주말에 여러 고민을 해봤다.

k-means 클러스터링은 한점에 대해서 이것이 어느 centroid에 속하는건지 k개에 대해서 룩업을 해봐야 하기 때문에, O(k* n * iteration)만큼의 복잡도를 가지고 있는 굉장히 실용적이기 않은 대표적인 클러스터링 알고리즘이다. 그런데 이걸 map reduce를 사용해 분산처리 한다면 상당히 시간을 아낄 수 있는데, n / No. of cluster 의 복잡도로 줄어들게 된다.
게다가 canopy 클러스터링 방법을 사용하면 비싼 distent measure를 값싼 distant measure로 바꿔서 정확도 저하를 방지하면서 빠르게 클러스터링을 해주기 때문에 k-means방법을 쓰기 이전에 실행하면 많은 컴퓨팅 리소스 낭비를 방지할 수 있다.

k-means를 mapreduce로 한번 생각해 보자면…

1. k개의 codewords를 별도의 파일로 준비하고, 모든 영화 데이터가 있는 영화id를 키로 하는 데이터파일을 하나로 준비한다.

2. map 작업을 하기 전에 초기 codewords 파일을 로딩하고 이것을 기반으로 각 영화 데이터에 대해 가장 가까운 codewords를 계산해서 clusterid, 영화 vector의 key, value 쌍으로 결과를 만든다.

3. combine작업에서는 각 노드의 map 작업 결과를 가지고 그 노드 전체의 같은 clusterid를 가지는 데이터에 대해서 clusterid, [all N,  sum of all vector] 를 구해서 새로운 cluster의 중심점인 codeword 점의 업데이트를 준비한다.

4. reduce 작업에서는 이전의 clusterid와 새로 업데이트될 new clusterid를 쌍으로 한 결과를 도출해서 파일로 쓴다.

5. 위 쌍의 데이터를 이용해 codewords 점의 업데이트가 어느 정도 이하로 움직인다던가, 아니면 어느정도 iteration의 임계치에 다다럿다고 생각하면 클러스터링을 종료하고 새로운 codeword를 가지고 2번 작업을 하고 reduce는 그대로의 결과를 도출해 파일로 쓰면 클러스터는 완성된다. 물론 임계치에 도달하지 않았다면 새로운 codewords를 로딩해서 2번부터 5번까지의 작업을 반복하면 될 것이다.

일단 위의 영화id를 기반으로 클러스터링을 어느정도 완료하면 item based filter를 하기위한 준비는 완료된다.
각 영화에 대한 클러스터를 했기 때문에 비슷한 영화셋들끼리 묶는 작업은 완료가 되었고, 문제가 되는 영화에 대한 내가 본 영화들간의 유사도를 기반으로 보지 않은 영화에 대한 점수를 예측할 수 있을 것이다.

물론 영화를 어느종류로 분류하는게 그러니까 k를 몇으로 잡아야 하는게 좋을지도 확인해 봐야 할 부분이고, 클러스터링을 할때 사용하는 distant measure를 어떤 식을 이용해서 하는것이 좋을지 식을 결정하는 문제같은것도 정확도를 높이기 위해 반드시 넘어야될 부분인거 같다.

일단 원하는 수준의 정확도는 나오지 않겠지만….실험을 많이 해보고 다시 리서치를 하는 과정을 거치면서 정확도는 높아질거라 생각한다.

클러스터링이나 collaboration filtering에 관심이 많은 연구원들이 군침을 흘릴만 한 문제인거 같다.
게다가 트레이닝 셋과 테스트 셋까지 공개했으니… 알고리즘 고민만 하면 된다는게 참 편리하다.

netflix prize에 도전하고 있습니다. by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.