이 장에서는 입력 받은 단어로 문서들을 찾아주고, 단어들에 가장 연관도가 높은 순으로 결과를 정렬하는 전문 검색엔진을 다룬다. 전문 검색에 사용하는 알고리즘들은 집단 지성 알고리즘 중에서 제일 중요한 것들에 해당되고, 이 분에에서 새로운 아이디어로 많은 갑부들이 탄생했다고 한다... 많은 사람들은 구글이 연구 프로젝트에서 세장에서 제일 인기 있는 검색엔진으로 초고속 성장한 이유가 페이지랭크 알고리즘에 있다고 믿는다.
1. 검색엔진이란?
: 검색엔진을 만드는 첫번째 단계는 문서 수집 방법을 개발하는 것이다. 크롤링이나 기업 인트라넷과 같이 고정된 문서 컬렉션으로 시작하는 경우가 있다. 문서들은 모은 후 색인을 하는데 이 때 여러 다른 단어들의 위치와 문서들을 담는 큰 테이블을 만드는 과정이 포함된다. 어떤 응용 분야에서는 문서가 데이터베이스 안에 저장되지 않는 경우도 있다. 색인에는 파일시스템 경로나 URL과 같이 문서 위치에 대한 참조(reference)만 저장한다.
이 장을 통해서 크롤링과 데이터베이스 생성용 클래스와 데이터베이스에 질의하는 전문 검색용 클래스를 만든다. 파이썬2로 인한 진행과 오래되어 사라진 페이지와 소스들로 인해서 사실상 이 책을 기반으로 전에 3장에서 군집발견처럼 다른 예를 가져와서 공부하려한다.
랭킹 알고리즘은 검색 결과의 순위를 결정하는 알고리즘이로써 검색결과의 순위는 다수의 알고리즘을 조합해 계산되고 있으며 또한 개별 알고리즘과 그 배분은 자주 조정되기 때문에 알고리즘의 전체상을 알 수는 없다. 그러나 중요하다고 판단되는 부분들은 대략 정해져 잇는데 그러한 요소들은 아래와 같고 이 장에서는 페이지랭크 알고리즘에 대한 개념을 학습해보도록 한다.
페이지의 중요도를 측정하는 지표
- 링크 인기도
- 사이트 테마
- HITS 알고리즘
- 클릭 인기도
키워드와 페이지 와의 관련성을 측정하는 지표 : 검색 키워드와 일치하는 문자열이 HTML파일에 포함되어 있는지.
페이지랭크 알고리즘을 논문에서는 이렇게 말한다. " 특정 페이지를 인용하는 다른 페이지가 얼마나 많이 있느냐를 세는 방식으로 학술지 인용 방식이 웹에 적용되어 왔다. 이렇게 하면 얼마나 특정 페이지가 중요한지 알 수 있다. pagerank는 이 아이디어의 연장으로써 다른ㄹ 페이지에서 오는 링크를 같은 비중으로 세는 대신에, 그 페이지에 걸린 링크 숫자를 '정규화(normalize)'하는 방식을 사용한다.
수식은 다음과 같다. $PR(A) = (1-d) + d(PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))$
$PR$은 pagerank의 줄임말이고, $PR(A)$는 $A$라는 웹페이지의 페이지 랭크를 의미한다.
$T1, T2, ... Tn$은 그 페이지를 가리키는 다른 페이지들을 의미한다.
$d$는 'Damping Factor' 이다.
$C(T1)은 T1이라는 페이지가 가지고 있는 링크의 총 갯수를 의미한다.
요약하면 $d$가 1이라 가정하면 나머지 부분들은 각 사이트별로 페이지랭크 값을 정규화시킨 것들의 합이라고 할 수 있다. 페이지 $A$의 페이지 랭크는 다른 페이지들의 페이지랭크 값이 높을수록 더 높아지게 된다.
정규화를 시킨합의 의미는 $C(T)$의 값이 높아지면 높아질수록 그 페이지가 기여하는 비중이 낮아진다는 것을 의미한다.
재귀적(recursive)인 모습을 볼 수 있다. 왜냐하면 $T1$ ~ $T5$ 전부 또 각각의 페이지랭크를 구하는 알고리즘을 거쳤기 때문이다.
위에서 설명을 제대로 하지 않은 $d$에 대해 알아보자
$d$값은 0과 1사이로 정해지는데 $d$값이 커져서 1이되면 앞의 $(1-d)$는 0이 되고, 뒤 수식의 합이 그대로 $A$의 페이지 랭크가 된다. 반대로 $d$가 작아져서 0이 되버리면 뒤 수식의 합은 0이 되어 암우 의미가 없어진다. 논문에서는 보통 0.85로 설정했다고 한다.
damping factor란 어떤 웹서핑하는 사람이 그 페이지에 만족을 못하고 다른 페이지로 가는 링크를 클릭할 확률이다. 즉 damping factor가 1이면 무한히 다른 링크를 클릭한다는 뜻이고, 0이면 처음 방문한 페이지에서 멈춘다는 것이다.
모든 웹페이지의 페이지랭크 값을 합산한 값은 1이 된다고 한다. .
위키피디아에서 그래서 이렇게 올바른 수식을 다시 작성하였다.
$PR(A) = (1-d)/N + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn))$
위 그림처럼 알파벳은 각 페이지 이름이 되겠고, 확률 값은 각 페이지가 지닌 페이지 랭크이다. 이 알고리즘을 통해서 모든 페이지들에 대해 페이지랭크를 구하고 정렬을 해놓는다면, 검색어가 포함된 페이지들을 이제 랭크 별로 노출시켜주면 그게 다이다. 이것은 아주 기초적인 알고리즘일 경우의 예이고 검색엔진 사이트들의 검색 랭킹 알고리즘은 실제로 훨씬 더 복잡하다고 한다. 어찌보면 추천과도 많은 연관이 있다는 생각이 든다. 내가 원하는 정보를 입력하고 이에 대해 그에 맞는 정보들을 추천해준다고도 생각해 줄 수 있는데, 실제로 사용자의 요구를 검색을 통해 얻어내고 그 짧은 검색어로 원하는 정보를 추천해준다는 것 자체가 실로 대단한 추천시스템이라고도 생각을 해본다.
출처:https://sungmooncho.com/2012/08/26/pagerank/
댓글