Skip to Main Content
程序设计导论:Python语言实践
book

程序设计导论:Python语言实践

by 罗伯特 塞奇威克, 凯文 韦恩, 罗伯特 唐德罗
August 2021
Intermediate to advanced content levelIntermediate to advanced
350 pages
13h 15m
Chinese
Pearson
Content preview from 程序设计导论:Python语言实践

1.6.4 混合马尔可夫链

这里要提醒读者的是,页面排名是Web模型的属性,而不是计算的特定方法。也就是说,randomsurfer.py程序只是计算页面排名的一种方法。幸运的是,基于成熟数学领域的简单计算模型提供了一个远比模拟计算页面排名问题更有效的方法。该方法基于二维矩阵的基本数学运算(具体可参见1.4节)。

1. 马尔可夫链自乘(Squaring a Markov chain)

通过两次跳转,随机冲浪者从页面i跳转到页面j的概率是多少?第一次跳转到一个中间页面k,所以针对所有可能的页面k,先计算从页面i到k的概率,然后计算从页面k到j的概率,最后累计计算结果值。在本书的Web模型示例中,通过两次跳转从页面1跳转到页面2的概率计算方法为:从页面1到0再到2概率(0.02×0.02),加上从页面1到1再到2的概率(0.02×0.38),加上从页面1到2再到2的概率(0.38×0.02),加上从页面1到3再到2的概率(0.38×0.02),加上从页面1到4再到2的概率(0.20×0.47),合计结果为0.1172。这个计算过程适用于其他的页面对。

在矩阵乘法定义时曾涉及这种计算:结果矩阵的第i行第j列的元素为原始矩阵第i行和第j列的点积。换言之,矩阵p[][]与自身乘积的结果为一个矩阵,结果矩阵的第i行第j列元素的值是随机冲浪者通过两次跳转从页面i到页面j的概率。马尔可夫链自乘的示意图如图1-6-6所示。

图1-6-6 马尔可夫链自乘的示意图

研究两次跳转转换矩阵的元素,将有助于我们更好地理解随机冲浪者的移动行为。例如,方阵的最大元素位于2行0列,表明冲浪者位于页面2时,有1个到页面3的链接,页面3只有1个到页面0的链接。所以,从页面2开始,冲浪者经过两次跳转,结果到页面0的可能性最大。其他两次跳转路径包含多个选择,因而可能性比较小。值得注意的是,这是精确计算(仅受限于Python的浮点精度);与之对比,程序randomsurfer.py产生的结果为估值,所以需要多次迭代以获取更为准确的估值。 ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Go程序设计语言

Go程序设计语言

艾伦A. A.多诺万, 布莱恩W. 柯尼汉
C++语言导学(原书第2版)

C++语言导学(原书第2版)

本贾尼 斯特劳斯特鲁普
Go语言编程

Go语言编程

威廉·肯尼迪

Publisher Resources

ISBN: 9787111549246