협업 필터링(Collaborative Filtering)과 같은 집단지성 발굴용 집계 알고리즘(collective algorithm)은 물품 또는 사용자 간의 유사도 계산(similarity function)으로 시작된다. 사용자, 물품이 소량인 경우라면 메모리에 올려 놓고 계산하면 된다. 하지만 현실은 만만치 않다. 사용자, 물품 수가 수십만 이상은 기본이고 수백만 단위가 되기 때문이다. 실무에서 협업 필터링 기법을 적용해 고객에 딱 맞는 물품을 추천하려면 교과서적인 메모리 기반 알고리즘으로는 불가능하다.
하둡(Hadoop)의 맵 리듀스 프레임워크(Map Reduce Framework)은 이런 대규모 계산 용도에 적합하다. 확장성이 뛰어 나지만 제한된 곳에서만 사용할 수 있다. 모든 메모리 기반 알고리즘을 맵 리듀스화 시킬 순 없다. 맵 또는 리듀스 작업 도중에 입력받은 이외의 데이터들이 필요하면 중앙 DB에 조회하여 데이터를 구해야 하기 때문이다. 이런 중앙 DB 연산이 많으면 하둡의 가치가 없어진다. 따라서, 대용량 상황에서 집단지성 발굴용 집계 알고리즘으로 교과서에 소개된 메모리 기반 알고리즘은 적합하지 않고, 대신에 맵 리듀스 전용 알고리즘을 찾아야 한다. 만일 중앙 DB가 꼭 필요한 경우라면 그 크기가 작아 빠른 조회가 되어야 한다.
페이지랭크 알고리즘이 메모리 기반 알고리즘과 맵 리듀스 기반 알고리즘의 기저사상이 다르듯 협업 필터링용 유사도 계산 알고리즘도 맵 리듀스 버전을 찾아야 한다. 다행히도 구글링을 통해 구글이 "대용량 뉴스 개인화 서비스"에서 사용한 기법인 LSA(Locality Sensitive Hashing)란 기법을 찾았다. 이 기법은 두 객체가 가까운 거리에 있을 수록 해쉬 값 충돌 확률이 높도록 해쉬 함수를 설계하는 방법이다. 한마디로 거리 관계를 충돌 확률 문제로 변환하여 해결하는 일종의 확률적 군집화 방법이다.
다양한 거리 계산 방법에 맞는 LSA용 해쉬 함수는 각각 다르다. 유사도 계산에 많이 사용하는 자카드 계수용 LSA 해쉬 함수로 MinHash란 것이 있다. MinHash 기법에 따르면 해쉬에 의해 차원이 축약된 개체들 간의 자카드 거리와 원 개체들의 자카드 거리는 확률적으로 근접하다라고 한다. 결국 어느 사용자들의 MinHash 값이 같으면 근접한 유사 사용자라고 판단할 수 있기 때문에 이 MinHash 값을 유사 군집 식별번호로 사용한다.
MinHash를 사용하면 맵 리듀스 프레임워크에서 다뤄야 할 데이터 량이 크게 준다. 맵 작업에서 "사용자 식별자 - 선호 물품 번호 목록" 입력을 받아 사용자별 물품의 MinHash값을 구한다. 사용자마다 p개 MinHash를 생성해 이 값들을 문자열 형태로 붙혀 군집 식별자를 생성한다. 맵의 출력 키로 군집 식별자를 그리고 맵 출력 값으로 사용자 식별자를 넣는다. 리듀스 작업을 통해 군집 식별자 - 사용자 식별자 목록(ClusterUserMap)을 최종 출력으로 구한다. 다음으로 새로운 맵-리듀스 작업을 통해 역전된 형태인 사용자 - 사용자가 속한 그룹 식별자 목록 데이터(UserClusterMap)를 생성한다. 이 두 출력 파일은 구글 BigTable 같은 중앙 DB에 넣어 키로써 값을 조회할 수도록 저장한다. MinHash로 인해 중앙 DB에 넣을 정도록 작아졌기 때문에 한곳에 저장 가능하다.
A 사용자의 유사 사용자 목록을 구하려면 2단계 거쳐야 한다. 먼저 UserClusterMap에서 A가 속한 군집 식별자 목록을 구한다. 이 군집들에 속한 유사 사용자를 ClusterUserMap에서 찾는다. 이렇게 얻은 <A 사용자 - 사용자 식별자> 간의 유사도 계산을 위해서는 A와 유사한 사용자들간의 군집 식별자를 구해 MinHash값을 분리낸 뒤 자카드 계수 계산법에 따라 계산하면 된다. 대용량의 로그 데이터에서 맵 리듀스 방식 알고리즘을 사용해 내 취향에 맞는 상품은 이렇게 구해질 수 있다.
@webJOY
MinHash 알고리즘을 이해하기 쉽게 설명한 파워포인트맵 리듀스 프레임워크를 이용한 확장성 있는 협업 필터링 기법 논문
minhash.pdf
