구글이 개인화된 뉴스를 추천하는 방법

구글의 뉴스 추천 기능과 그 방법은 이미 많이 알려진 내용입니다.
2년쯤 전에 제 블로그에서도 구글의 뉴스 추천 서비스에 대해 간단하나마 설명을 드리기도 했고요. (요기 클릭!)

제 블로그를 통해서, 제게 개인적으로, 또는 저희 회사(넷스루)를 통해 개인화 추천에 관심을 가지고 문의하시는 분들의 대부분은 아마존의 개인화 추천 서비스에 가장 먼저 관심을 가집니다.
그리고, 간혹 구글의 추천 뉴스에 관심을 가지는 분들이 계시지요.

구글에서 사용하는 방법이라고 해서 기존 연구를 통해 고안된 방법과 크게 차이가 있는 것도 아닙니다.
다만... 구글이라고 하는 초대형 서비스는 그들의 인프라와 그들의 방법으로, 그들 서비스에 최적화된 형태로
잘 구현해 냈다는 것이 차이점일 뿐입니다. 그리고, 사실은 그것이 기술의 차이이기도 하겠지요.

그럼, 구글에서 개인화된 뉴스를 추천하는 방법에 대해서 개념적이긴 하지만 간단히 설명드립니다.
(자세한 내용은 2007년 5월, WWW 2007에서 발표된 "Google News Personalization: Scalable Online
Collaborative Filtering" 논문을 참고하세요.)

[주의] 어디까지나 개념적인 설명입니다. 구글의 개인화 추천 서비스의 방법을 제 나름대로, 좀 더 이해하기 쉽게 예를 통해서 만들어 보았습니다. 실제 논문의 내용은 다릅니다.^^ (헐~ 어려워요... 쩝!)

구글 추천 뉴스의 특징
구글은 사용자 수도 많고 Feeding되는 뉴스(Item)의 수도 많고, 사용량은 더 말할 필요도 없지요.
그리고, 뉴스 컨텐츠는 아마존의 상품들과 달리 Life-time이 짧습니다.
매일 매일 새로운 것으로 채워지는 컨텐츠이고, 어제의 컨텐츠는 추천할 가치가 현저히 떨어지지요.
그렇기 때문에 구글에서는 '현재 새롭게 서비스 되고 있는 뉴스' 중에서 추천할만한 것을 골라내야 합니다.

그 방법을 간단히 요약하면다음과 같습니다.
1. 며칠간의 사용자 Click-stream을 분석하여 '취향이 비슷한 사용자들의 묶음(Cluster)'을 찾아냅니다.
2. 각 Cluster별로 어떤 뉴스를 많이 보는지를 Scoring합니다.
3. 특정 사용자가 로그인 하면, 그 사용자가 속한 Cluster에서 가장 많이 본 뉴스를 추천합니다.

개인화 추천 서비스에 관심을 가진 분들은 Collaborative Filtering이란 말을 들어보셨을텐데
위에 설명한 내용이 바로 Collaborative Filtering 방법입니다.

그리고, 그 핵심은...
어떻게  '취향이 비슷한 사용자들의 묶음(Cluster)'을 찾아내는가?

취향이 비슷한 사용자 찾아내기 (Clustering)
이것은 전통적인 데이터 마이닝 분야의 문제입니다. 그리고, K-means와 같이 이미 널리 알려진 방법들도 있습니다.
구글에서 사용하는 Clustering 방법은 MinHash라는 방법에 기초합니다.

예를 들어, 설명하겠습니다.

다음과 같이, 어떤 사용자가 어떤 뉴스를 보았는가를 나타내는 Matrix가 있습니다.
뉴스를 보았을 때는 '1'로 표시하고, 보지 않은 뉴스는 '0'으로 표시합니다.
예를 들어, 몽룡이는 1번 뉴스와 2번 뉴스를 보았고 3번과 4번 뉴스는 보지 않았습니다.

이렇게 만든 사용자와 뉴스 사이의 클릭 관계 Matrix에서, 뉴스 목록(행, Rows)을 랜덤하게 섞어줍니다.
예를 들어, 위에서 1-2-3-4 순으로 되어 있던 뉴스 행들이 아래와 같이 3-1-4-2로 뒤죽박죽 뒤섞이게됩니다. (Random Permutation)
당연히... 각 뉴스에 표시된 사용자별 클릭 여부를 나타내는 '0', '1' 값도 따라 움직이겠죠.
 

이렇게 섞어 놓은 후에, 각 사용자별로 따라 내려가면서 맨 처음 '1'이 나오는 뉴스를 찾습니다.
예를 들어, 몽룡이의 경우 두번째 행에 나오는 "[인터뷰] 주한남아공대가가 되어 돌아온 브로닌"이라는 기사가 걸리게됩니다.
이와 같이 각 사용자별로 아래로 훑어가면서 맨 처음 '1'이 나오는, 즉 자기가 클릭한 뉴스 중에서 맨 처음 나타나는 것을 찾아냅니다. 바로, 위의 그림에서 빨간색으로 나타낸 것들이지요. 당연히, 한 사용자에게서 빨간색 숫자 '1'은 한번씩만 나타나게 됩니다.

그리고, 같은 뉴스 기사에 대해서 빨간색 '1'이 나타나는 사용자들끼리 묶어줍니다.
즉, "여권에 뽀샵사진 붙였다가 낭패본 K씨"라는 뉴스를 기준으로 향단이와 월매가 한 묶음으로 묶이게 됩니다.
이렇게 찾아낸 사용자 묶음(Cluster)는 다음과 같습니다.

Cluster 1 : 향단이, 월매
Cluster 2 : 몽룡이, 방자
Cluster 3 : 춘향이

쉽죠? ㅋㅋ
이렇게 사용자들의 묶음이 만들어 졌습니다.

예를 들어, 향단이와 월매는 같은 취향의 그룹으로 묶였으니까
이제 향단이가 많이 클릭한 뉴스를 월매에게 추천해 주면 되겠네요. ^^

이렇게 간단하게 처리했는데, 과연 향단이와 월매가 같은 취향이라고 볼 수 있을까요?
네... 같은 취향이라고 볼 수 있습니다.
전통적인 방법으로는 향단이와 월매가 클릭한 뉴스 중에서 서로 교집합인것과 차집합인 것을 비교해서 향단이와 월매가 어느정도 뉴스 클릭이 일치하는가를 계산한 후, 그 유사도가 높은 사람들끼리 묶음을 만듭니다.
하지만, 위에 소개한 방법처럼 사용자들이 클릭한 Item(뉴스) 목록을 랜덤하게 섞은 후에 맨 처음 나타나는 것들을 가지고 사용자 묶음을 만들어도 동일한 그룹핑 효과를 볼 수 있답니다.
(연구자들에 의해 증명된, MinHash라는 방법입니다.)
 
Covisitation - 함께 클릭되는 뉴스들
이러한 Clustering 작업은 많은 계산을 필요로하기 때문에, 즉시 얻어낼 수가 없습니다.
그래서, 하루 또는 며칠에 한번씩만 사용자 묶음을 만듭니다.
그렇게 때문에... 새로 들어온 사용자는 어느 그룹에도 속하지 않는 경우가 있겠지요.
예를 들어, 변학도라는 사용자가 새롭게 등장했을 때, 변학도는 위의 Cluster 1, 2, 3 어디에도 속하지 않습니다.

그럼, 변학도에게는 어떤 뉴스를 추천해 줄까?

구글에서 뉴스를 추천하는 또 다른 중요한 방법은 각 뉴스에 대해서 함께 클릭된 다른 뉴스들을 추천하는 것입니다.
아마존에서 "A를 산 사람은 B도 삽니다"라고 추천하는 것과 같은 원리이지요.
데이터 마이닝의 전통적인 기법 중 하나인 연관규칙(Association Rule) 탐사 방법도 이와 같습니다.

단, 아마존에서는 위와 같은 A-B 관계를 어젯밤에 미리 분석해 놓은 것으로 추천해도 되지만
뉴스는 하루가 지나버리면 그 생명력을 다하기 때문에 미리 분석해 놓을 수가 없습니다.
그래서, 구글에서는 실시간으로 각 사용자들의 뉴스 클릭을 분석하여, 각 뉴스마다 함께 클릭되는(Covisited) 다른 뉴스들을 관리합니다. (말이 분석이지... 사실은 Count한다고 보면 됩니다.)

그리하야... 변학도 같이 새로 들어온 사용자라 하더라도...
변학도가 어떤 뉴스를 클릭하면, 그 뉴스와 함께 많이 열람되는 다른 뉴스를 추천하게 됩니다.

....

사실 구글이라고 해서 아주 특별한 방법을 사용하지는 않습니다.
많은 연구를 통해서 그 이론과 개념은 대부분 알려진 것들이지요.

그러나... 저는 위에서 단순하게 예를 들어 설명했지만...
그것을 실제 대용량 환경에서 서비스로 제공할 수 있는 수준으로 만드는 작업은 그리 간단하지가 않습니다.
데이터량과 계산량, 처리속도에서 문제가 생기는 것은 기본이고
생명주기가 짧은 뉴스 컨텐츠이기 때문에 시간이 흐름에 따라 Click Score나 Covisitation Score를 감소시켜주는 방법도 필요할 것이며, Cluster를 만들 때에도 그 크기가 너무 크거나 너무 작은 것은 의미가 없으니까 그런 것들을 보정해 주는 방법도 필요할겁니다.
뉴스 사이의 Covisitation 관계에서도, 그 시기에 모든 사람이 관심을 가지는 빅 뉴스는 거의 모든 뉴스와 Covisitation 관계가 있을테니 이런것들도 적절히 보정해 주어야 할꺼구요.

개인화 추천 서비스, 특히 구글 뉴스처럼 생명주기가 짧은 컨텐츠나 상품을 추천하는 방법을 찾는 분들께 도움이 되었으면 좋겠네요...