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))
모든 지표들의 표준 가중치는 없음.
주요 검색 사이트들도 검색 결과 랭킹방법은 수시로 바꿈
: 사용할 지표와 제공할 가중치는 구축하려는 응용에 따라 크게 달라짐
