Google에서 웹페이지 순위를 매기는 데 사용하는 PageRank 알고리즘을 이해하고 웹페이지의 호출기에 영향을 미치는 요소를 이해합니다.

1. 웹 페이지 순위와 Google 알고리즘의 탄생

Google이 탄생하기 전의 인기 있는 웹 페이지 순위 알고리즘은 모두 매우 유사했습니다. 아이디어: 웹페이지가 중요할수록 트래픽도 더 커집니다. 많은 대기업에서는 웹페이지 트래픽을 계산하여 웹페이지 순위를 매깁니다. 그러나 이 순위 알고리즘에는 두 가지 중요한 문제가 있습니다.

1. 샘플링만 가능하기 때문에 통계 데이터가 정확하지 않을 수 있으며, 정확한 통계를 얻으려면 방문 횟수의 변동이 크게 발생합니다. , 많은 시간과 인력이 필요하며 단기간 동안에만 효과를 볼 수 있습니다.

2. 방문 횟수가 반드시 웹페이지의 '중요도'를 반영하는 것은 아닙니다. 아마도 일찍이 인터넷을 접한 일부 네티즌들은 당시 많은 사람들이 특별히 웹페이지를 위해 서비스를 시작했다는 것을 기억하고 있을 것입니다. "방문 횟수를 늘리세요".

방문수를 계산하지 않고 웹페이지의 중요성 순위를 매기는 더 좋은 방법이 있습니까?

구글의 창업자이자 미국 스탠퍼드대 대학원생인 페이지와 브린이 1996년 초부터 웹페이지 순위 문제를 연구하기 시작한 것도 이런 상황에서였다.

1999년 페이지를 제1저자로 한 논문이 발표됐다. 이 논문은 페이지랭크(PageRank)라는 알고리즘을 소개했다. 이 알고리즘의 주요 아이디어는 웹페이지가 "중요"할수록 페이지 링크의 품질이 높아지고 다른 "중요" 웹페이지에 연결되기가 더 쉬워진다는 것입니다.

결과적으로 알고리즘은 웹페이지 간의 관계를 완전히 활용하여 웹페이지의 중요도를 계산하고, 웹페이지 정렬을 완전히 수학적 문제로 바꾸어 최종적으로 방문 통계의 틀을 없앱니다.

2. PageRank 알고리즘의 실행 프로세스 시뮬레이션

이 알고리즘을 자세히 설명하기 전에 독자가 이해할 수 있도록 게임을 사용하여 PageRank 알고리즘의 실행 프로세스를 간략하게 시뮬레이션하겠습니다. 그것에 대해 자세히 알아보세요.

세 형제는 처음에는 완두콩을 30개씩 나누어서 매번 마음에 드는 사람에게 완두콩을 모두 나눠주었습니다. 아래 사진은 각각의 초기 완두콩 수입니다. , 그리고 상호 좋아하는 관계(화살표의 방향은 좋아함을 나타냅니다. 예를 들어 둘째 아이는 상사를 좋아하고 상사는 둘째 아이와 셋째 아이를 좋아합니다).

첫 번째 할당 후에는 다음과 같은 결과를 얻게 됩니다.

그렇습니다. 손에 있는 완두콩의 수가 더 이상 변하지 않을 때까지 게임을 계속하세요.

그럼 이 게임은 끝날 수 있을까요? 그렇다면 최종 결과는 어떻게 될까요?

여기서 우리는 이 과정을 컴퓨터를 사용하여 시뮬레이션했고 결과는 다음과 같습니다. 사장과 두 번째 아이는 각각 접시에 완두콩 12개씩, 세 번째 아이는 이때 접시에 완두콩 6개를 놓았습니다. , 게임이 어떻게 진행되더라도 접시에 담긴 완두콩의 수는 변하지 않습니다.

이를 보면 독자들은 다음과 같이 질문할 수 있습니다. 이 게임이 웹페이지 정렬과 무슨 관련이 있나요?

사실 PageRank는 각 웹 페이지에 값을 부여합니다. 값이 높을수록 웹 페이지가 더 "중요"합니다.

방금 게임에서 완두콩의 개수를 이 값(정수일 필요는 없음)으로 간주하고 자식을 웹 페이지로 간주하면 게임 프로세스가 PageRank입니다. 알고리즘이며, 게임 종료 시 완두콩의 개수는 분포가 웹페이지의 PageRank 값입니다.

3. PageRank 알고리즘의 수학적 모델

이전 방문 통계와 달리 PageRank는 다음과 같은 문제를 해결합니다. 사람이 인터넷에서 웹 페이지를 탐색할 때 각 페이지를 본 후 무작위로 새 웹페이지에 액세스하려면 웹페이지의 링크를 클릭하세요.

이 사람이 현재 탐색하고 있는 웹 페이지 x가 결정되면 웹 페이지 x의 각 링크가 클릭될 확률도 결정되며 이는 벡터 Nx로 표시될 수 있습니다.

이러한 조건에서 이 사람이 무한한 수의 링크를 클릭한 후에도 각 웹페이지에 머무를 확률은 얼마나 됩니까?

이 모델에서는 벡터 Ri를 사용하여 i개의 링크를 클릭한 후 각 웹 페이지에 머무를 확률(각 웹 페이지를 처음부터 열 확률)을 나타냅니다. 나중에 증거의 내용은 최종 결과에 영향을 미치지 않습니다.)

분명히 Ri의 L1 정규 형식은 1이며 이는 PageRank 알고리즘 자체의 요구 사항이기도 합니다.

위 게임을 예로 들면, 전체 검색 프로세스 시작 시 다음이 표시됩니다.

그 중 A는 각 클릭 확률의 행렬을 나타냅니다. 링크, 그리고 A의 i번째 열 j번째 줄의 의미는 현재 방문한 웹 페이지가 웹 페이지 i라면 다음 번에 해당 링크를 클릭하여 웹 페이지 j로 이동할 확률은 입니다.

이런 방식으로 행렬 A를 설계할 때의 장점은 행렬 A와 벡터를 곱하면 링크를 클릭한 후 각 웹페이지의 가능한 체류 확률 벡터를 얻을 수 있다는 것입니다. 예를 들어 링크를 클릭한 후 각 웹페이지에 머무를 확률을 얻을 수 있습니다.

그런 다음 다음과 같이 계속 반복합니다.

위 예의 경우 반복 결과는

위 그림에서 볼 수 있듯이 각 웹페이지에 머무를 확률은 변동 이후 안정적인 경향을 보입니다.

이 안정된 상태에서는 아무리 반복해도 존재한다는 것을 알 수 있으므로 방정식을 얻습니다.

그리고 전체 반복 과정은 방정식을 구하는 것입니다. R=AR이 아무리 많아도 무한 반복을 하면 R=AR이 참이 되는 R값을 얻게 된다. 지상을 걷는 것과 동일하므로 "랜덤 워크 모델"이라고 합니다.

Random Walk 모델의 주목할만한 특징은 각 반복의 결과가 이전 결과와만 관련이 있고 이전 결과와는 아무런 관련이 없다는 것입니다. 이 프로세스를 Markov 프로세스라고도 합니다. 마르코프 체인(마르코프 체인).

마르코프 프로세스의 수학적 정의는 다음과 같습니다. 확률 변수 시퀀스의 경우, 여기서 이 프로세스는 마르코프 프로세스가 됩니다. 이를 "1단계 전이확률"이라고 부르는데, 1단계 전이확률을 적분하여 2단계 전이확률과 3단계 전이확률을 구할 수 있다.

상태 공간이 제한된 경우 전이 확률은 전이 행렬이라고 불리는 행렬 A로 나타낼 수 있으며, 이때 전이 확률의 적분은 행렬의 거듭제곱이고, k는 다음과 같습니다. -단계 전환 확률은 다음과 같이 표현할 수 있습니다. 해당 값은 최종 결과에 영향을 미치지 않습니다.

4. "웹 페이지 정지"로 인한 부작용 수정

그런데 여기에 문제가 있습니다. 의 값이 최종 결과에 영향을 미치지 않더라도 가능합니까? 웹페이지 정렬의 기반으로 R을 사용하는 것이 정말 합리적인가요?

Ma Haixiang의 관점에서 이것은 실제로 불합리합니다. 왜냐하면 웹페이지에 인바운드 링크만 있고 아웃바운드 링크가 없는 경우 웹페이지는 동일한 연결된 하위 그래프를 연결하는 "블랙홀"과 같기 때문입니다. 그 페이지로 유입되는 다른 웹 페이지는 천천히 "삼켜집니다"(알고리즘의 가상 사용자가 해당 웹 페이지에 들어가면 외부 링크가 없기 때문에 해당 웹 페이지는 영원히 거기에 머물기 때문입니다). 이러한 종류의 웹 페이지를 "행잉 웹"이라고 합니다. 페이지"(Dangling Link).

이러한 '블랙홀' 효과는 연결성이 좋은 인터넷에서는 하나의 '행잉 웹페이지'만으로도 전체 인터넷에서 웹페이지의 순위가 무효화될 만큼 심각하다고 설명할 수 있습니다. "한 개의 웹페이지". 쥐똥 한 알이 죽 한 그릇을 망친다.

이 문제를 해결하기 위해 페이지와 브린은 사용자가 '행잉 웹 페이지'를 방문할 때 이 페이지에 머물 수 없고 머물러서는 안 되며 다른 웹 페이지를 방문하게 된다는 점을 깨달았습니다. 당신 자신의.

각 사용자가 방문하는 웹페이지는 자신의 관심사와 관련되어 있지만, 페이지와 브린은 평균적으로 사용자가 전체 인터넷 웹페이지에서 웹페이지를 무작위로 선택한다고 가정합니다. 입장.

그래서 그들은 PageRank 알고리즘에 새로운 벡터 E를 추가했습니다. 그 기능은 거기에 설명된 비율에 따라 매달린 웹페이지에 의해 "삼켜진" PageRank를 모든 웹페이지에 할당하는 것입니다.

이런 방식은 매달린 웹 페이지에 대해 네트워크의 모든 웹 페이지에 대한 링크를 추가하는 것과 동일하며, 매달린 링크의 모양을 피합니다.

위 내용은 구글이 숨기고 있는 페이지랭크(PageRank) 알고리즘의 가장 중요한 비밀이다. 기존의 키워드 출현 횟수를 기준으로 한 순위와 달리 모든 웹페이지의 상호 링크를 통해 결정되는 이 순위는 그리 쉽지 않다. 예, 웹사이트가 아무리 가짜이더라도 진정으로 매력적인 콘텐츠가 없고 다른 사람들이 해당 웹사이트에 링크하지 않으면 모든 것이 여전히 헛되기 때문입니다.

그리고 "페이지 정렬"에도 중요한 기능이 있습니다. 즉, 인터넷의 구조에만 관련될 뿐 사용자가 구체적으로 검색하는 것과는 아무런 관련이 없다는 의미입니다. 정렬 계산은 별도의 작업 없이 독립적으로 수행할 수 있습니다. Google 검색의 속도는 사용자가 검색 명령을 입력한 후 일시적으로 수행한다는 사실에 크게 기인합니다.

Ma Haixiang의 블로그 댓글:

마지막으로 PageRank가 Google 검색 결과 순위를 매기는 중요한 기반이고 이를 통해 부를 얻었지만 이것이 전체 기반은 아니라는 점을 강조하고 싶습니다. 실제로 Google은 오늘날까지 수백 가지의 다양한 알고리즘을 동시에 사용하여 사용자에게 궁극적으로 표시되는 검색 결과의 순서를 결정했습니다.