지밍이 블로그

4. 검색과 랭킹

...

06. 유입 링크 사용하기

기존 - 페이지 내용에 기반한 점수 지표

검색품질향상 - 다른 사람들이 그 페이지에 등록한 정보를 적용,
                        의심스러운 값을 가진 페이지나 스패머들이 생성했을 법한 페이지 색인에 효과적

(이런 페이지들은 실제 내용을 가진 페이지에 비해 연결될 가능성이 적기때문)

# 단순계산

유입링크를 사용하는 가장 간단한 방법

> 각 페이지의 유입링크 개수를 세고,

> 링크 전체 개수를 페이지에 대한 지표로 사용

예, 학술눈문

: 인용논문수로 논문의 중요도가 평가

####코드

- 페이지들이 단순 리턴, 해당 페이지의 유입 링크 개수만을 의존하여 랭킹

예, "Programming language"페이지가 "Python"페이지보다 많은 유입링크를 갖지만

정말 찾는 것이 "Python"이라면 결과에서 제일 먼저 나타나야 함

유입 링크 기반지표와 다른 지표들 중 하나와 결합하여 검색능력과 랭킹에 적합도를 결합할 수 있다. (검색능력향상)

# 페이지랭크 알고리즘

"Google"을 만든 세르게이 브린과 래리 페이지가 대학원생 때 쓴 논문 "The Anatomy of a Large-Scale Hypertextual Web Search Engine"에서 발표

개요

- 검색엔진의 품질 향상을 목적

- 웹기반에서의 검색엔진은 인덱스만으론 부족

: 검색된 페이지수는 엄청난 성장으로 방대하나, 사람들의 수용능력은 느리게 성장

         -> 결국 필요한 페이지만 골라서 읽어야 할 필요가 있음

- 관련이 있는 페이지만을 도출하자

- 하이퍼텍스트 정보를 사용하여 웹 페이지간의 연결 관계를 판단, "링크구조 및 링크달린 텍스트"

알고리즘 소개

- 기존 : 특정 페이지를 인용하는 다른 페이지가 얼마나 많이 있느냐를 세는 방식

- PageRank : 다른 페이지에서 오는 링크를 같은 비중으로 세지 않고, 페이지에 걸린 링크 숫자를 "정규화(normalize)"하여 사용

-> 하이퍼링크를 가지는 문서에서 상대적 중요도에 따라 가중치를 부여하는 방법을 가진 알고리즘

PR(A) = (1-d) + d(PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

PR : PageRack

PR(A) : A페이지의 페이지랭크 값

T1, T2,... : 그 페이지를 가리키는 다른 페이지들

PR(T1) : T1 페이지의 페이지랭크 값

C(T1) ; T1 페이지가 가지고 있는 총 링크의 갯수

> d(Dampen Factor)는 아직 생각하지 않기(d=1로 가정)

> A페이지를 가리키는 다른 페이지들의 페이지랭크 값을 평균화하여 다 더한 값

> 즉 A페이지랭크 값은 그 페이지를 인용하고 있는 다른 페이지들의 페이지랭크 값을 "정규화" 시킨 값

> "정규화"라는 말의 의미... 페이지랭크 값은 단순 합산이 아님. 

예. T1의 페이지랭크가 높아도, T1페이지를 가리키는 링크가 많다면(C(T1)) 그 페이지가 기여하는 비중은 낮아짐

A : 페이지

T1, T2, T3, T4, T5 : A를 가리키는 페이지

- 재귀적 호출 알고리즘

T1, T2, T3, T4, T5 의 페이지랭크값을 정규화하여 합한 값으로 A의 페이지랭크 값을 계산

A의 페이지랭크값도 다른 페이지의 페이지랭크값을 구하는데 사용

제한조건이 필요

- Dampen Factor

: 어떤 마구잡이로 웹서핑을 하는 사람이 그 페이지에 만족을 못하고 다른 페이지로 가는 링크를 클릭할 확률 - 논문

PR(A) = (1-d) + d(PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

d=1, 수식 그대로가 A의 PageRank 값

d=0, 모든 페이지가 1이 되므로 의미가 없어짐

d는 0~1 사이값

보통.. d는 85%, 0.85 

논문에 따르면, "모든 웹페이지의 페이지랭크 값을 합산하면 1이된다."고 하는데..

수식에 모순이 있음

d=1일때, 하나의 페이지에 대한 페이지랭크가 최대 1이 될 수 있으므로, 전체 페이지에 대한 페이지랭크값은 N.

위키피디아에서 수식을 정정

PR(A) = (1-d)/N + d(PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))    // 전체 페이지수로 한번 나눔

출처 https://sungmoon.files.wordpress.com/2012/08/screen-shot-2012-08-25-at-4-46-19-am.png

책에서는,

dampen Factor를 85%로 계산(0.85)

PR(A) = 0.15 + 0.85 * ( PR(B) / link(B) + PR(C) / link(C) + PR(D) / link(D) )

PR(A) = 0.15 + 0.85 * ( 0.5 / 4 + 0.7 / 5 + 0.2 / 1 )        // 페이지랭크는 C가 젤 높은데, 링크는 A 한군데만 하기때문에 기여도가 젤 높음

PR(A) = 0.15 + 0.85 * ( 0.125 + 0.14 + 0.2 )

PR(A) = 0.15 + 0.85 * 0.465

PR(A) = 0.54425

함정,

페이지링크 값을 가지지않은 모든 페이지들의 페이지랭크 값들은??

> 모든 페이지랭크 값을 초기에 임의의 값으로 지정한 후 여러 번 반복 계산

> 반복을 할 때마다 각 페이지랭크값은 실제 페이지랭크값에 점점 가까워 지게됨

> 약 20회 정도

페이지랭크는 시간이 많이 걸림, 검색어와 상관없이 진행이 됨.

> 모든 URL에 대한 페이지 랭크를 사전에 계산

> 이 값을 테이블에 저장하는 함수 생성

calculatepagerank(x, y)

: 매번 수행될 때 모든 페이지랭크를 재계산

> 모든 페이지에 대한 페이지랭크값을 1로 초기화

> 모든 페이지URL에 대해 루프를 돌며 모든 유입링크에 대한 페이지랭크 값과 전체 링크 수를 얻는다.

>  예제 Database에서 어떤 페이지가 가장 높은 페이지랭크 값을 가지는지 확인하려면 데이터베이스에 직접 쿼리

>  "Main Page"가 젤 높은 페이지랭크를 가짐

> 정규화 함수 부분 추가

> weights 리스트를 수정하여 페이지랭크를 포함시키면 좀 더 향상된 결과를 얻을 수 있음

# 링크텍스트 활용

: 페이지의 링크들의 텍스트를 사용하여 페이지의 적합도를 판단

-> 링크를 가진 페이지 자체보다 페이지에 대한 링크에 대한 설명등을 참조(개발자들이 링크하려는 것들에 대한 간략한 설명을 링크에 넣기 떄문)

코드

> 검색 수행 시, 제공된 단어 ID들의 목록을 새로운 인자로 가짐

linktextscore(x,y,z)를 searccher안에 추가

> wordids 안에 있는 모든 단어들에 대해 루프를 돌면서 이 단어들의 링크를 찾기

> 링크의 목적지가 검색결과 안에 있다면, 링크소스의 페이지랭크 값을 목적지 페이지의 최종 점수에 더하기

검색 단어를 포함하고 있는 중요한 페이지로부터 링크를 많은 받은 페이지가 더 높은 점수를 가짐

검색 결과 내의 대부분의 페이지들의 경우 정확한 텍스트를 가진 링크가 없어 점수0을 가짐

> 링크 텍스트 랭킹을 반영하기 위해 weights 리스트에 코드를 추가

(1.0, selt.linktextscore(row, wordids))

모든 지표들의 표준 가중치는 없음. 

주요 검색 사이트들도 검색 결과 랭킹방법은 수시로 바꿈

: 사용할 지표와 제공할 가중치는 구축하려는 응용에 따라 크게 달라짐