디시인사이드 갤러리

갤러리 이슈박스, 최근방문 갤러리

갤러리 본문 영역

구글 검색 알고리즘의 원리 끗

...(141.223) 2007.04.24 15:08:40
조회 561 추천 0 댓글 8


예를 들어 4개의 웹 페이지 A, B, C, D가 있고, 그 중에 B와 D가 A를 link하고 있을 때
A의 page rank는
Q(A) = Q(B)/N(B) + Q(D)/N(D)
이렇게 구해. 이때 N은 해당 페이지가 걸고 있는 link의 개수를 의미하고,
이 계산을 Q(A), Q(B), Q(C), Q(D)가 모두 수렴할 때까지 계속 반복해주면 돼.

이제 이게 앞의 알고리즘과 어떻게 연결되는지 보자.

우선, PageRank 알고리즘에서 웹페이지는 따로 벡터화를 하지 않아.
그렇다면 P(A->B) 같은, random walk을 위한 확률은 대체 어떻게 구하는가?

구글은 random walk 대신 random click 이라는 아이디어를 적용했어.
예를 들어, 현재 웹페이지가 하나 떠 있는데, 여기에 link가 N개 있다고 하자.
random click이란, 그 중에 하나를 무작위로 click한다는 거야.
따라서 다음 턴에 각각의 link된 사이트들로 이동할 확률은, 1/N이 되겠지.

즉, P(A->B)는, A에서 B로 가는 link가 있는 경우 1/N이고, link가 없는 경우 0이 되는 거지.
(즉, 위의 예에서 Q(A)의 실제 식은 Q(B)*(1/N(B)) + Q(C)*0 + Q(D)*(1/N(D)) 가 돼)
벡터화니 직선거리 계산이니 하는 복잡한 과정 없이 굉장히 간단하지.
웹이 가지는 특성을 정말 잘 이용한 것 같아.

그외에 나머지는 이전 글에서 설명한 알고리즘과 똑같아. 웹에 적용함으로써 달라진 건 저것 뿐이지...
계산 식이 이전 글의 알고리즘이랑 다르긴 한데, 결국 나오는 값은 똑같고 방법만 다른 거야.
(간단한 계산을 수렴할 때까지 반복하느냐, 아니면 역행렬을 구하는 다소 복잡한 계산이지만
 한 방에 결과가 나오는 방법이냐 하는... 그런데 역행렬 계산은 complexity가 O(n^3)이라;;;;
 규모가 큰 데이터에 대해서는 간단한 계산을 적당한 수준까지 반복하는 방법을 쓰지...)

그런데, PageRank 알고리즘에 대한 잘 알려진 직관적인 설명들이 있잖아.
정말 실제 알고리즘과 직관적인 설명이 잘 대응이 될까 생각해 보자.

우선,
악의적으로 링크를 많이 걸어놓은 사이트들로 인해 검색 엔진의 성능이 떨어지는 것을 막기 위해
링크를 많이 걸은 사이트의 영향력을 줄인다는 이야기.
이건 위에 1/N, 그거야. 링크를 많이 걸 수록 N이 커져서,
결국 이 사이트를 거치는 path들의 확률은 무진장 작아지게 되지.
이는 다시 말하면 이 사이트의 영향력이 약해진다는 얘기가 되고...
설명대로의 효과를 잘 나타내.

다음으로, 링크가 많이 걸려 있는 사이트는 더 높은 rank를 준다는 이야기.
어떤 사이트로 들어오는 link가 많다는 얘기는, 결국
임의의 사이트에서 이 사이트로 올 수 있는 경우의 수가 그만큼 늘어난다는 얘기고,
따라서 다른 모든 사이트들에 대해 이 사이트의 랭킹이 높아지는 효과가 일어나지.
역시 설명대로의 효과를 잘 나타내지...

하지만 실제 구체적인 알고리즘이 어떻게 되는지 알고 나면
걔들이 발표한 직관적인 설명 및 장점들은, 실제 PageRank 알고리즘의 진가에 비하면
그저 빙산의 일각일 뿐이라는 것을 알 수 있지...

추천 비추천

0

고정닉 0

0

원본 첨부파일 1

댓글 영역

전체 리플 0
등록순정렬 기준선택

하단 갤러리 리스트 영역

왼쪽 컨텐츠 영역

갤러리 리스트 영역

갤러리 리스트
번호 제목 글쓴이 작성일 조회 추천
설문 거지분장이 찰떡인 스타는? 운영자 20/12/02 - -
AD [댓글 이벤트] 삼성디프 12월 고객감사전! 운영자 20/12/02 - -
공지 프로그래밍 관련 내용이 있어야 합니다. [17] 운영자 20.09.28 1792 34
1547427 텐서플로우는 오픈ai가아니다 인공무현갤로그로 이동합니다. 05:31 5 0
1547426 여기 프로그램중 알맞는게 어떤걸까 ??? [3] ㅇㅇ(1.238) 05:20 23 0
1547424 인공무현 패키지 싱글 게임 하냐? 레식이런거 말고 [1] 어계세키위갤로그로 이동합니다. 05:05 13 0
1547423 php문법 대강 아는데 바로 라라벨 ㅇㅇ(115.86) 05:04 9 0
1547422 4년제 대학 졸업하고 바로 취업못하는 사람들 비율 몇%나 되냐? [2] 동반꿀갤로그로 이동합니다. 05:04 20 1
1547421 주식해보니까 창업을 보는관점이 확달라지노 [1] 인공무현갤로그로 이동합니다. 04:59 35 0
1547420 스타트업이라는게 결국 주식쇼구나 인공무현갤로그로 이동합니다. 04:57 24 0
1547419 리액트 네이티브 강좌듣고 앱 만들면서 실습 중인데 [3] ㅇㅇ(115.126) 04:51 27 0
1547418 2.프라미스 abort 많이들 함? [59] 딱국갤로그로 이동합니다. 04:48 88 0
1547417 그냥 빨리 잘걸 [1] 아무거나1234갤로그로 이동합니다. 04:36 19 0
1547416 열심히 공부하는 프갤러들을 위한 선물 [3] ㅇㅇ(115.86) 04:35 36 0
1547415 1. class vs return [1] 딱국갤로그로 이동합니다. 04:34 39 0
1547414 백단에서 데이터 관리 질문. [13] capcha_test갤로그로 이동합니다. 04:33 43 0
1547413 s3에 파일 업로드하고 나서 로그에 키 두번뜨는거 거슬리네 [3] 리삐삐갤로그로 이동합니다. 04:26 32 0
1547412 비트캠프나 삼성멀티캠이나 쌍용 이세개중한곳가면 ㅇㅇ(106.101) 04:25 18 0
1547411 업무효율을 위한 전담 뻑뻑피는 중.. 리삐삐갤로그로 이동합니다. 04:25 17 0
1547410 졸려서 미칠거같음 리삐삐갤로그로 이동합니다. 04:24 15 0
1547409 아 스트링파이해서 올리는게 맞네 리삐삐갤로그로 이동합니다. 04:22 14 0
1547407 etl 글루에서 할 예정이었는데 리삐삐갤로그로 이동합니다. 04:15 10 0
1547406 그래도 너무 이론만 하면 지칠거같음 sfdsa갤로그로 이동합니다. 04:15 19 0
1547405 헤으응 고3 대학 어쩌농 [2] ㅇㅇ(219.254) 04:14 49 0
1547404 구찮으니까 일단은 파싱해둔 s3만 쓰자 ㅇ.ㅇ.. 리삐삐갤로그로 이동합니다. 04:12 13 0
1547403 요건 추가 되도 다 받아들일 수 있게 좀 카탈로그 넓게 잡을까 리삐삐갤로그로 이동합니다. 04:09 13 0
1547402 앞으로 할 예정 [2] 리삐삐갤로그로 이동합니다. 04:06 38 0
1547401 철학과도 나쁘진 않을거같아 sfdsa갤로그로 이동합니다. 04:05 23 0
1547400 아 내가 string으로 저장하고 있었네 [3] 리삐삐갤로그로 이동합니다. 04:05 31 0
1547399 본인 지잡대 소프트웨어학과 학생인데 [4] ㅇㅇ(211.171) 04:03 44 0
1547398 AVL 트리 O(logN)에 동작하도록 개선했다 [7] ㄱㄹ갤로그로 이동합니다. 03:58 58 0
1547396 수학과도 재밌어보이는거 많음 sfdsa갤로그로 이동합니다. 03:56 25 0
1547395 웹은 아직 개발진행형인 거 같음 redux도 다음 세대에 교체될 듯 [12] 나트륨찡갤로그로 이동합니다. 03:38 72 0
1547393 밑글 사진 안올라가는데 비밀번호 까먹어서 사진첨부 ㅁㄹㅇㅁ(119.203) 03:35 42 0
1547392 야 리액트판에 퍼블리셔 생존하냐?? ㅇㅇ(118.235) 03:34 27 0
1547390 이거 오류 왜뜨는거냐? [1] ㅁㄹㅇㅁ(119.203) 03:32 21 0
1547389 국비중인데 강사 ㅈ같다 (국비 50일째) [6] ㅇㅇ(218.157) 03:31 58 1
1547387 오늘 한 일, 할일 ㅇㅇ(39.119) 03:30 16 0
1547386 redshift 처음으로 만들예정.. 리삐삐갤로그로 이동합니다. 03:28 20 0
1547385 저 포인터 관련 질문이요 ㅇㅇ(39.7) 03:27 21 0
1547384 아니 aws glue 이넘 도통 모르것메 [3] 리삐삐갤로그로 이동합니다. 03:26 31 0
1547383 디자이너랑 연애하고싶다 [2] 야근맨(220.117) 03:24 29 0
1547382 아이디어만으로 개발자 구하는애들 있더라 [5] 헬마스터갤로그로 이동합니다. 03:16 100 0
1547381 딸깜 던지고 간다 [1] ㅇㅇ(223.62) 03:16 85 0
1547380 useSelector [6] 야근맨(220.117) 03:13 52 0
1547379 인프런 파이썬 세일하는데 [1] ㅇㅇ(211.238) 03:12 175 0
1547378 react에서 redux쓰면 [6] aZe(106.250) 03:11 65 0
1547377 빌드는 esbuild 야근맨(220.117) 03:10 22 0
1547376 나도 리덕스싫어 빨리 새로운거 쓰고싶다 [12] 야근맨(220.117) 03:09 53 0
1547375 암호학 마스터 아무도 못 푸는 암호 만듦 ㅇㅅㅇ [6] 나트륨찡갤로그로 이동합니다. 03:08 61 0
1547374 난일단 일은 리액투로하고 피에로가르뎅갤로그로 이동합니다. 03:06 24 0
1547373 useState쓸때 주의해야할점. [8] capcha_test갤로그로 이동합니다. 03:03 64 0
갤러리 내부 검색
제목+내용게시물 정렬 옵션

오른쪽 컨텐츠 영역

이슈줌NEW

1/6

힛(HIT)NEW

그때 그 힛

1/3