Map Reduce 분산 추천 시스템: 클러스터링 기반 협업 필터링 알고리즘을 사용한 분산 추천 시스템

대규모 추천 시스템에서 분산 시스템을 통한 효율적인 추천을 필요하다

Min Hash 기반의 분산 추천 시스템은 Map Reduce 구조를 통해서 사용자가 선호하는 아이템을 기반으로 그룹 아이디를 생성하고, 같은 그룹 아이디의 클러스터로 묶인 사용자에 대해서만 코사인 유사도를 계산한다.

모든 사용자를 Pairwise로 비교하지 않으므로 효율적이지만 정확성과 확장성에 대해서는 의문이 든다.

추천 시스템에서 분산 시스템 적용

협업 필터링(특히 사용자 기반의 협업 필터링)은 취향이 비슷한 사용자들을 찾고, 해당 사용자들이 선호하는 아이템을 기반으로 추천하는 방법이다. 하지만 모든 사용자에 대해서 사용자 간 유사도를 구하는 과정을 대규모의 데이터 환경에서 비효율적이다. 따라서 분산 시스템을 도입하여서 효과적으로 빅 데이터 환경에 대응하는 것이 필요하다.

 

분산 시스템은 다수의 노드(컴퓨터)가 일정 크기로 나누어진 작업을 담당하여 처리하고 이를 종합하는 구조이다. 논문은 Map Reduce 기반의 분산 추천 시스템을 제안했다. Map 작업에서는 사용자가 선호하는 아이템을 기반으로 그룹 아이디를 생성한다. 그룹 아이디를 생성하는 방법은 Min-Hash 알고리즘이다. Map 작업에서는 <그룹 아이디, 아이템-평점 정보>가 출력되고 Reduce 작업에서는 동일한 그룹 아이디가 클러스터를 형성한다. 이렇게 형성된 클러스터 내에서 코사인 유사도를 계산하면, 모든 사용자 간의 코사인 유사도를 계산하는 이전의 시스템보다 효율적으로 협업 필터링의 개념을 구현할 수 있다. 

Min Hash 알고리즘

Min Hash 알고리즘은 어떠한 사용자가 유사한 사용자인지 판별한다. Min Hash를 위해서는 하이퍼 파라미터 p와 q를 정의해야 한다. q는 해시 함수 그룹의 개수이고, p는 개별 해시 함수 그룹에서 해시 함수의 개수이다.

Min Hash Clustering: 논문 Figure

하나의 해시 함수 그룹에서는 사용자에 대응하는 하나의 그룹 아이디를 생성한다. 하나의 해시 함수 그룹에는 p 개의 해시 함수가 있다. p 개의 해시 함수는 사용자가 선호하는 아이템에 대해서 Min Hash를 출력한다. Min Hash란 사용자가 선호하는 아이템에 해시 함수를 적용했을 때 출력되는 가장 작은 값이다. 예를 들어 사용자가 선호하는 아이템이 [3, 15, 20, 32] 이었고 해시 함수를 적용한 결과 [20, 13, 15, 18]이라면 최솟값 13이 적용된 해시 함수를 통해 얻은 Min Hash이다. 그룹 아이디는 p 개의 해시 함수를 통해 얻은 Min Hash를 조합한 결과이다. 결과적으로 한 개의 해시 함수 그룹에서 하나의 그룹 아이디가 생성되므로, 하나의 사용자는 q 개의 그룹 아이디를 할당받는다.

 

Map Reduce 구조에서 Map에서 Reduce로 넘어갈 때 Map의 출력인 <Key, Value> 쌍에서 Key 값을 기준으로 정렬한다. 따라서 이러한 과정을 통해 동일한 그룹 아이디의 사용자는 Reduce 작업의 입력으로 같이 들어가서 클러스터를 형성한다.

Min Hash 알고리즘 기반의 분산 추천 시스템이 문제는 없을까?

논문에서는 Min Hash 알고리즘 기반의 분산 추천 시스템이 사용자가 늘어감에 따라서 추천 시스템 수행 시간이 선형으로 증가하지 않는다는 것에 집중하였다. 하지만 구현된 분산 추천 시스템에 대해서 성능과 확장성에 의문이 든다.

 

Min Hash를 구하는 과정에서 사용자가 선호하는 아이템을 모두 고려하지 않는다. 사용자 A가 선호하는 아이템이 [1, 3, 4, 5]이고 사용자 B가 선호하는 아이템이 [1, 3, 4, 7]이라고 가정해보자. 하나의 해시 함수 그룹에는 p=3개의 해시 함수가 있다. 만약 p 개의 해시 함수가 A가 선호하는 5번 아이템과 B가 선호하는 7번에서 최솟값을 출력한다면 두 사용자는 대부분의 아이템을 공유하고 있음에도 불구하고 다른 그룹으로 할당될 것이다. 이러한 점에서 Min Hash는 계산상의 효율성은 있지만 얼마나 정확하게 동작할지 하이퍼 파라미터 p와 q를 잘 설정해야 한다.

 

또한 새로운 사용자 데이터가 등장했을 때 유연하게 대처하지 못할 수 있다. 새로운 사용자의 선호하는 아이템을 기반으로 그룹 아이디를 생성하였는데, 그룹 아이디에 다른 사용자가 없다면 추천이 이루어지지 않을 것이다.

 

대규모의 추천 시스템 서비스에서 효율성을 위해 분산 시스템을 적용하는 것은 필수적이다. 하지만 분산 시스템을 적용하는 과정에서 Approximation이 들어가게 되고, 이는 정확성이 떨어질 수 있는 여지가 있다. 최근에 딥 러닝 기반의 추천 시스템에서는 어떠한 방식으로 추천 시스템이 적용되는지 확인해볼 필요가 있다.

 

References

조현제, & 이필규. (2014). 클러스터링 기반 협업 필터링 알고리즘을 사용한 분산 추천 시스템. 한국인터넷방송통신학회 논문지, 14(1), 101-107.