구글 PageRank

Contents

이 문서는 일반적인 검색 알고리즘과 구글의 page rank에 대한 내용을 담고 있다. 이해하기 어려운 내용이 될 수도 있겠으나, 쉽게 이해할 수 있도록 설명하기 위해서 노력을 했다. 검색알고리즘 특히 PageRank와 관련된 구글의 아이디어는 블로그검색 에서의 검색품질을 높이기 위한 방법으로도 사용될 수 있을 것이다. 이 글의 말미에서는 이에 대한 아이디어를 제시한다.

흔히 검색은 망망대해에서 투망을 던지는 작업에 비유되곤 한다. 문서의 양은 이미 100억건이 넘는데, 검색어로 주어지는 문서를 찾는 다는 자체가 대단한 도전과제이기 때문이다. 게다가 건져지는 양도 문제다. 검색하라고 단어를 던졌더니 한 10만건이 무작위로 검색되어서 올라온다고 생각해보라. 이 중에서 원하는 문서를 어떻게 찾아낼 수 있을 것인가.

초기의 디렉토리 기반의 검색엔진이 저러했었다. 지금은 기억에서 사라진 알타비스타라든지 디렉토리 기반의 고전 야후 검색엔진이 저러했었다. 그냥 검색어 던지면 걸리는데로 무작위로 화면에 뿌려주니, 정보의 더미속에서 원하는 문서를 찾아야만 했다. 그나마 그 당시는 문서의 양이 적었으니, 그러한 불편함을 감수 할 수 있었을 것이다.

그래서 문서에 score를 주어서 score순으로 정렬해서 보여주어야 겠다는 생각을 하게 된다. 지금의 대부분의 검색엔진들이 score 알고리즘을 이용해서 문서의 우선순위를 메긴다. 문서의 스코어를 내기 위해서 다음과 같은 원칙들이 사용된다.

1. 하나의 문서에 단어가 여러번 출현 하면, 문서의 스코어는 높아진다.
2. 단어가 여러 문서에 출현하면, 문서의 스코어가 낮아진다.

1번은 명료하다. Linux라는 단어를 포함한 문서를 찾는다고 하면, 여러번 Linux가 출현한 문서가 아무래도 찾고자 하는 문서일 확률이 높기 때문이다. 2번은 약간 알쏭달쏭할 수 있는데, 역시 상식적인 원칙이다. The Linux를 검색어로 입력했다고 가정해 보자. The같은 경우는 일반적으로 사용되는 단어이기 때문에, 거의 모든 문서에서 발견이 될 것이다. 그러나 Linux 와 같은 단어는 전문적인 단어이기 때문에, 몇개의 문서에서만 발견될 것이다. 그러므로 The와 Linux가 포함된 2개의 문서가 있다면, Linux가 포함된 문서에 더 높은 점수를 줘야 할 것이다. 대략 다음과 같은 순서로 문서에 대한 점수 순위가 메겨질 것이다.

1. The와 Linux를 모두 포함한 문서
2. Linux만 포함한 문서
3. The만 포함한 문서

하나의 문서에 몇개의 단어가 출몰 했는지를 나타내는 것을 tf (Term frequency)라고 하고, 하나의 단어가 몇개의 문서에서 발생했는지를 나타내는 것을 idf (Invert Document frequency) 라고 한다. 그러므로 문서에 대한 스코어는 tf * idf로 정의할 수 있게 된다. 물론 실제 score는 이렇게 단순하지 않지만 tf*idf의 기본원칙을 가진다.

어떻게 문서의 score가 메겨지는지 자세한 정보를 찾기를 원한다면 검색 알고리즘 문서를 참고하기 바란다. 아마 분명히 재미없는 문서일 것이다.

tf*idf 에 기반한 알고리즘을 적용하는 것만으로도 꽤 괜찮은 수준에서 검색결과를 얻어올 수 있으나, 검색의 품질을 떨어트리는 결정적인 문제가 있다. 그것은 바로 tf를 조작함으로써 인위적으로 문서의 스코어를 높일 수 있다는 점이다.

사람들이 자주 입력할만한 단어를 반복해서 입력해서 페이지를 상위에 노출시키는 소위 말하는 낚시 사이트를 만들 수 있다는 것이다. 아무런 내용도 없이 자극적인 단어들로 도배되어 있는 사이트를 아마도 본적이 있을 것이다.

이것은 검색의 품질을 극도로 떨어트리게 된다.

그래서 만들어낸게 PageRank 알고리즘이다. 가능한 사람이 개입할 여지를 제거해서, 페이지 순위 조작을 원천 봉쇄하자는 취지에서 만들어진 알고리즘이다. 개념은 간단하다. 모든 문서의 외부 링크를 검사해서, 링크가 많은 문서에 더 많은 점수를 부여해 주겠다는 아이디어다. 좋은 문서는 다른 많은 문서로 부터 참조될 것이다라는 가정에서 시작된다. 인위적으로 링크를 조작하기 힘들다는 장점도 가진다. 실제 PageRank를 도입한 구글은 상당히 좋은 검색품질을 보여준다.

아래는 PageRank가 어떻게 만들어지는 지를 보여주고 있다.

https://lh5.googleusercontent.com/-QE7gpfpurvY/UAeczFWVxCI/AAAAAAAACP8/iUc-44zic4c/s800/p2.jpg

만약 A,B,C,D 문서가 있고, B와 D문서가 A로 향하는 링크를 포함하고 있다면, 다음과 같은 PageRank 공식을 만들어낼 수 있을 것이다.

이 알고리즘은 약간 수정되어야 할 필요가 있다. 왜냐하면 하나의 문서는 목적지 URL이 다른 여러개의 링크를 포함할 수 있는데, 그렇다면 각 문서에 도달할 확률을 구할 필요가 있기 때문이다. PageRank는 random click를 이용해서 이 문제를 풀어낸다. 즉 1/N 해주는 거다. 이제 위의 알고리즘은 다음과 같이 수정될 수 있을 것이다.

PageRank는 tf*idf와 독립적으로 움직일 수 있으므로, PageRank를 도입한 구글의 문서 스코어 공식은 다음과 같이 나타낼 수 있다. (tf * idf) * PageRank

tf * idf 와 PageRank는 독자적으로 계산될 수 있다는 점은 , 문서에 이를 적용시키는 것도 매우 수월하게 만들어준다. 주기적으로 페이지의 모든 링크를 조사해서 계수하는 프로그램을 돌려서 PageRank 테이블을 만들어 놓기만 하면 되기 때문이다. 그 후 tf*idf 결과로 나온 문서에 대해서 해당되는 PageRank를 곱한 결과를 가지고 정렬해주면 된다.

개념이 간단하다고 해서 구현이 간단한건 물론 아니다. 처리해야 하는 페이지의 갯수가 100억건이기 때문이다. 이 정도의 데이터를 처리하려면, 가상화된 공간위에서 작동되는 분산처리시스템이 구비되어 있어야 한다. 이를 위해서 Google는 MapReduce(:12) 프로그래밍 모델을 이용해서 가상화된 구글 글로벌 파일 시스템을 만들어 냈다. 또한 구글은 MapReduce를 통해서 대량의 데이터를 여러대의 컴퓨터에 분산해서 처리하는 엔진역시 가지고 있다.

국내의 블로그 검색엔진을 통해 검색을 하다보면, 일반적인 검색엔진이 아예존재하지 않거나 검색결과 자체가 형편없는 경우를 발견할 수 있다. 가장 큰 문제는 낚시 블로그가 상위에 노출된다는 점이다. 음? 글쎄 네이버나 다음이나 검색을 해보면 대부분 낚시 사이트는 걸리지 않던데 ? 라고 반문할 수 있을 거 같다. 현재 국내 사이트는 수작업을 통해서 낚시 사이트를 걸러낸다. 낚시가 많을거 같은단어들 예를 들자면 티켓,옥션,경매... 등등등에 대해서는 미리 조사를 해서 낚시 사이트로 판명되는 것의 순위를 인위적으로 걸러버리는 것이다.

이러한 방법은 당연하지만 그만큼 많은 인력과 비용이 소비되며, 누락되는 단어들도 많을 수 밖에 없다. 테스트를 해보면 알겠지만, 그다지 잘 찾지 않을거 같은 단어들에 대해서는 낚시 사이트가 상위에 올라오는 것을 심심찮게 볼 수 있을 것이다. 포탈에서 제시하는 인기어들에 길들여지다 보니, 그게 체감이 되지 않을 뿐이다.

최악의 방식은 추천과 같은 인위적인 방식을 통해서 문서를 노출시키는 것이다. 올블로그를 비롯한 대부분의 국내 메타 블로그 사이트들이 취하고 있는 방식이다. 검색기술이 취약하니, 인위적인 방식을 통해서 양질의 문서를 노출시키는 전략으로 나가는 거라고 볼 수 있을 것이다. 추천이 최악의 방식인 이유는 다양한 양질의 문서가 노출되는 것을 원천적으로 막을 뿐더러, 충분히 조작될 수 있기 때문이다. 추천 받을려면 일단 첫페이지에 노출이 되어야 한다. 당연히 최근의 소위 말하는 뜨는 이슈를 쫓아서 자극적이고 선정적인 제목과 내용으로 포장된 글들이 첫페이지에 노출될 수 밖에 없다. 이는 장기적으로 메타블로그의 품질 자체를 떨어트리게 될 것이다. 추천이라는 기능을 유저의 참여라는 이상한 공식으로 포장해서 서비스 하는데, 이건 유저의 참여와는 전혀 관련 없는 것이다. 유저의 참여를 위한 요소인 링크와 트랙백은 이미 갖추어져 있다. 메타 블러그나 포탈에서는 이러한 요소를 잘 활용해서 유저에게 좋은 문서를 제공하는 시스템을 만들어주어야 한다. 기술이 없기 때문에 추천을 기술인것 처럼 포장하는 것이다.

검색품질을 높이기 위해서는 PageRank 와 같은 개념을 도입할 필요가 있다. 다음의 두가지 방법이 있을 것이다.

1. 블로그의 링크를 직접 계산한다.
2. 블로그의 로그를 계산한다.

네이버와 같이 자신의 영역에서 블로그 컨텐츠를 유지하고, 그 공간에서의 검색을 주로하려고 한다면 2번 방식이 더 좋을 것이다. 로그자체를 링크처럼 활용할 수 있을 것이기 때문이다. 반면 다음과 같이 인터넷 상에 블로그를 공개하는 방식이라면 1번의 방식을 선택해야 할 것이다.

UCC를 마케팅 영역으로 끌어올리면서, 특히 블로그 컨텐츠에 대한 중요성을 강조하고 있는데, 적어도 포탈이라고 하면 인기어를 제시해서 유저를 가두려고 하는 기존의 자세에서 벗어나서 다양한 컨텐츠에 대한 소비와 창조가 가능한 환경을 만들어줘야 하지 않을까 생각해본다.