当前课程知识点：计算思维导论 > 第九单元 > 9.23 网页排序方法（PageRank） > Video
搜索引擎必须从大量
被命中的网页里挑出
按匹配度大小排序的查询结果
那么
一个网页的“排名”究竟取决于什么
计算机科学家们使用“相关度”这个术语
来形容一个网页
和某个特定查询有多么相配或多么有用
为此
他们提出了很多好的方法
比如邻度技术
元词技术
关键词权值TF-IDF等
但更我们感兴趣的
是Google公司的PageRank
它圆满地解决了
以往网页搜索结果中排序不好的问题
一超链接技术
超链接技术是PageRank技术的基础
在互联网上
如果一个网页被很多其他网页所链接
说明它受到普遍的承认和信赖
那么它的排名就应该高
这就是PageRank的核心思想
这个道理其实很好理解
正常情况下
如果一个女孩子走在大街上
能吸引更多的眼球和目光
从颜值来说
她的排名肯定应该靠前
反之
她的排名应该靠后
假设你对学习如何制作炖鸡感兴趣
并且用网络搜索了这一主题
再假定检索结果只有两个网页
其中一个是“张三的炖鸡菜谱”
另一个是“李四的炖鸡菜谱”
并且有4个相关评论的网页
指向了这两个菜谱网页
这就是示意图
看起来这两份菜谱都不错
但人们对李四菜谱的反响
要更为热烈一些
因此
在没有给出其他信息的情况下
李四的菜谱应该更靠前
不幸的是
计算机并不擅长理解
网页文字信息的真实内涵
因此搜索引擎不太可能依据
网页评论信息
对每个菜谱推荐的强烈程度进行评估
一种简单的办法
就是只计算链向每份菜谱的网页数
根据链入链接数对菜谱进行排名
这样李四的网页比张三的网页排名在前
因为李四有三个链入链接
而张三只有一个
但这样的技术也存在问题
比如
相关网页的评价未必都是肯定的
例如“我试了下张三的菜谱很糟糕”
像这样的链接
的确会导致超链接技术
将网页的排名拔高
尽管如此
超链接技术仍然很有用
二权重技术
大家也许已经想到
为什么要对网页的所有链接一视同仁
来自专家的推荐肯定
要比“菜鸟”的推荐更有价值
这就是权重技术的基本思想
比如
张三的链接来自篮球巨星姚明
而李四的链接来自中国烹饪大师赵继宗
显然
著名主厨推荐的菜谱
要比选择由一名篮球界巨星
推荐的菜谱更好
计算机
如何才能自动判定烹饪大师赵继宗
在炖鸡方面比姚明更具有权威性呢
让我们把超链接技术
和权重技术结合起来
所有网页的初始权重值都设为1
但如果一个网页有链入链接
在计算该网页权重时就要加入
指向它的网页的权重
这样就可以计算出
张三菜谱网页的权重值为2
李四菜谱网页的权重值为100
所以李四的网页排名要比张三的靠前
大家看看这个示意图应该不难理解
我们不妨抽象一下
假设网页Y有4个链入的网页
x1 x2 x3 x4
如图所示
那么对于网页Y而言
它的pagerank很容易计算出来
它的值就是0.081
那么x1 x2 x3 x4的权重分别是多少
又如何计算呢
这是一个非常重要的问题
必须设法解决
三随机访问模型
就自动计算权重值来说
我们似乎拥有了一个真正奏效的策略
无须计算机真正地理解网页的内容
不幸的是
这种方法存在一个严重的问题
那就是超链接有可能会形成“循环”
就像这个图中A B和E三个网页一样
这样计算权重
就会产生“鸡生蛋，还是蛋生鸡”的问题
Google聪明的设计者
通过“随机访问模型”
很好地解决了这个问题
假设稍微复杂的万维网WWW有16个网页
被访问者访问的网页用深色表示
实线箭头代表访问者点击的超链接
虚线箭头代表随机重新开始访问
假定访问者
重新访问一个网页的概率是15%
你也可以认为访问者有15％的概率
对任何已访问过的网页厌倦
导致其选择其他网页
然后用计算机来模拟
实验表明
当访问次数达到一百万时
我们可以得到这样的模拟结果
从随机访问者模拟中计算得出的百分比
正好就是我们在衡量一个网页的权重时
所需要的
该模型天生能同时和超链接技术
及权重技术相配合
它的绝妙之处在于
不管超链接有没有形成循环
随机访问模型都能完美地面对
回到前面遇到的难题
通过随机访问模型进行模拟
就可以得到这样的结果
思路有了
怎么实现呢
Google的佩奇
和布林用迭代的方法解决了这个问题
他们先假定所有网页的排名是相同的
并且根据这个初始值
算出各个网页的第一次迭代排名
然后再根据第一次迭代排名
算出第二次的排名
依此类推
过程如下
我们先假定向量B为第1 第2
第n个网页的网页排名
矩阵A
为描述网页之间链接关系的稀疏矩阵
其中aij
表示第i个网页指向第j个网页的链接数
显然
矩阵A是已知的
B是未知待求解的
刚开始时
按如下的方式设置向量B的初始值
然后利用下面的迭代公式计算
向量B1 B2 B3 一直到Bi
理论上可以证明
当变量i不断增大时
Bi最终会收敛
也就是说Bi无限趋近于B
实际计算时
迭代十来次就够了
需要特别注意的是
每次迭代的计算量非常大
但佩奇和布林采用算法设计中的分治法
并利用稀疏矩阵计算的技巧
大大简化了计算量
最终实现了这个网页排名算法
好
这一节就讲到这里
谢谢大家
-1.1 计算思维及其教育
--Video
-2.1 计算是什么
--Video
-2.2 计算与自动计算
--Video
-2.3 计算机及其计算本质特征（I）
--Video
-2.4 计算机及计算的本质特征（II）
--Video
-3.1 数的表示与模拟计算
--Video
-3.2 数的表示与数字计算
--Video
-3.3 二进制加法运算的机器化
--Video
-3.4 “九九归一”的加法运算
--Video
-3.5 二进制之优越性及问题与代价
--Video
-4.1 从数学危机到图灵机
--Video
-4.2 图灵机的计算能力
--Video
-4.3 什么问题都能计算吗？
--Video
-4.4 冯•诺依曼机及其发展与演化
--Video
-4.5 从算盘到图灵机——机械计算的本质
--Video
-4.6 电子计算机——透过现象看本质
--Video
-5.1 思维可机械计算吗（I）
--Video
-5.2 思维可机械计算吗（II）
--Video
-6.1 量子理论
--Video
-6.2 量子计算机
--Video
-7.1 人类求解问题之过程
--Video
-7.2 基于计算（机）的问题求解过程
--Video
-7.3 面向过程的结构化设计方法学
--Video
-7.4 面向对象之方法学
--Video
-7.5 面向对象技术
--Video
-7.6 抽象
--Video
-7.7 计算学科中的抽象
--Video
-7.8 时间与空间及其相互转换
--Video
-7.9 技术层面的其他方法学
--Video
-7.10 认知层面的其他方法学
--Video
-8.1 算法与程序
--Video
-8.2 算法设计方法——枚举
--Video
-8.3 算法设计方法——递推
--Video
-8.4 算法设计方法——递归
--Video
-8.5 算法设计方法——分治
--Video
-8.6 算法设计方法——仿生
--Video
-9.1 机器间的通信方式
--Video
-9.2 数据转发方法
--Video
-9.3 网络分层体系结构
--Video
-9.4 有趣的对称加密技术
--Video
-9.5 难解的非对称加密技术
--Video
-9.6 数字签名及其应用
--Video
-9.7 从自然智能到人工智能
--Video
-9.8 符号主义的基本思想
--Video
-9.9 连接主义Ⅰ
--Video
-9.10 连接主义Ⅱ
--Video
-9.11 行为主义的基本思想
--Video
-9.12 机器翻译的愿景与困难
--Video
-9.13 峰回路转的自然语言处理
--Video
-9.14 信息传输中的问题与挑战
--Video
-9.15 重复传输与冗余编码
--Video
-9.16 校验与校验和
--Video
-9.18 自纠错技术及应用
--Video
-9.19 两种简单的数据压缩方法
--Video
-9.20 哈夫曼编码
--Video
-9.21 数据压缩极限与LZ压缩方法
--Video
-9.22 大海捞针的搜索引擎
--Video
-9.23 网页排序方法（PageRank）
--Video
-10.1 计算文化
--Video
-期末考试--作业
