程序员的数学基础课
黄申
LinkedIn资深数据科学家
立即订阅
23478 人已学习
课程目录
已完结 57 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 作为程序员,为什么你应该学好数学?
免费
导读 (1讲)
导读:程序员应该怎么学数学?
基础思想篇 (18讲)
01 | 二进制:不了解计算机的源头,你学什么编程
02 | 余数:原来取余操作本身就是个哈希函数
03 | 迭代法:不用编程语言的自带函数,你会如何计算平方根?
04 | 数学归纳法:如何用数学归纳提升代码的运行效率?
05 | 递归(上):泛化数学归纳,如何将复杂问题简单化?
06 | 递归(下):分而治之,从归并排序到MapReduce
07 | 排列:如何让计算机学会“田忌赛马”?
08 | 组合:如何让计算机安排世界杯的赛程?
09 | 动态规划(上):如何实现基于编辑距离的查询推荐?
10 | 动态规划(下):如何求得状态转移方程并进行编程实现?
11 | 树的深度优先搜索(上):如何才能高效率地查字典?
12 | 树的深度优先搜索(下):如何才能高效率地查字典?
13 | 树的广度优先搜索(上):人际关系的六度理论是真的吗?
14 | 树的广度优先搜索(下):为什么双向广度优先搜索的效率更高?
15 | 从树到图:如何让计算机学会看地图?
16 | 时间和空间复杂度(上):优化性能是否只是“纸上谈兵”?
17 | 时间和空间复杂度(下):如何使用六个法则进行复杂度分析?
18 | 总结课:数据结构、编程语句和基础算法体现了哪些数学思想?
概率统计篇 (14讲)
19 | 概率和统计:编程为什么需要概率和统计?
20 | 概率基础(上):一篇文章帮你理解随机变量、概率分布和期望值
21 | 概率基础(下):联合概率、条件概率和贝叶斯法则,这些概率公式究竟能做什么?
22 | 朴素贝叶斯:如何让计算机学会自动分类?
23 | 文本分类:如何区分特定类型的新闻?
24 | 语言模型:如何使用链式法则和马尔科夫假设简化概率模型?
25 | 马尔科夫模型:从PageRank到语音识别,背后是什么模型在支撑?
26 | 信息熵:如何通过几个问题,测出你对应的武侠人物?
27 | 决策树:信息增益、增益比率和基尼指数的运用
28 | 熵、信息增益和卡方:如何寻找关键特征?
29 | 归一化和标准化:各种特征如何综合才是最合理的?
30 | 统计意义(上):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
31 | 统计意义(下):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
32 | 概率统计篇答疑和总结:为什么会有欠拟合和过拟合?
线性代数篇 (13讲)
33 | 线性代数:线性代数到底都讲了些什么?
34 | 向量空间模型:如何让计算机理解现实事物之间的关系?
35 | 文本检索:如何让计算机处理自然语言?
36 | 文本聚类:如何过滤冗余的新闻?
37 | 矩阵(上):如何使用矩阵操作进行PageRank计算?
38 | 矩阵(下):如何使用矩阵操作进行协同过滤推荐?
39 | 线性回归(上):如何使用高斯消元求解线性方程组?
40 | 线性回归(中):如何使用最小二乘法进行直线拟合?
41 | 线性回归(下):如何使用最小二乘法进行效果验证?
42 | PCA主成分分析(上):如何利用协方差矩阵来降维?
43 | PCA主成分分析(下):为什么要计算协方差矩阵的特征值和特征向量?
44 | 奇异值分解:如何挖掘潜在的语义关系?
45 | 线性代数篇答疑和总结:矩阵乘法的几何意义是什么?
综合应用篇 (6讲)
46 | 缓存系统:如何通过哈希表和队列实现高效访问?
47 | 搜索引擎(上):如何通过倒排索引和向量空间模型,打造一个简单的搜索引擎?
48 | 搜索引擎(下):如何通过查询的分类,让电商平台的搜索结果更相关?
49 | 推荐系统(上):如何实现基于相似度的协同过滤?
50 | 推荐系统(下):如何通过SVD分析用户和物品的矩阵?
51 | 综合应用篇答疑和总结:如何进行个性化用户画像的设计?
加餐 (3讲)
数学专栏课外加餐(一) | 我们为什么需要反码和补码?
数学专栏课外加餐(二) | 位操作的三个应用实例
数学专栏课外加餐(三):程序员需要读哪些数学书?
结束语 (1讲)
结束语 | 从数学到编程,本身就是一个很长的链条
程序员的数学基础课
登录|注册

37 | 矩阵(上):如何使用矩阵操作进行PageRank计算?

黄申 2019-03-11
你好,我是黄申。今天我来说说矩阵。
前面我说过,矩阵由多个长度相等的向量组成,其中的每列或者每行就是一个向量。从数据结构的角度来看,我们可以把向量看作一维数组,把矩阵看作二维数组。
具有了二维数组的特性,矩阵就可以表达二元关系了,例如图中结点的邻接关系,或者是用户对物品的评分关系。而通过矩阵上的各种运算操作,我们就可以挖掘这些二元关系,在不同的应用场景下达到不同的目的。今天我就从图的邻接矩阵出发,展示如何使用矩阵计算来实现 PageRank 算法。

回顾 PageRank 链接分析算法

在讲马尔科夫模型的时候,我已经介绍了 PageRank 链接分析算法。所以,在展示这个算法和矩阵操作的关系之前,我们快速回顾一下它的核心思想。
PageRank 是基于马尔科夫链的。它假设了一个“随机冲浪者”模型,冲浪者从某张网页出发,根据 Web 图中的链接关系随机访问。在每个步骤中,冲浪者都会从当前网页的链出网页中,随机选取一张作为下一步访问的目标。此外,PageRank 还引入了随机的跳转操作,这意味着冲浪者不是按 Web 图的拓扑结构走下去,只是随机挑选了一张网页进行跳转。
基于之前的假设,PageRank 的公式定义如下:
其中, 表示第 张网页, 的入链接集合, 集合中的第 张网页。 表示网页 的 PageRank 得分, 表示网页 的出链接数量, 就表示从网页 跳转到 的概率。 是用户不进行随机跳转的概率, 表示所有网页的数量。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(4)

  • 拉欧
    一直想搞明白pagerank的计算流程,这节课真值
    2019-03-11
    2
  • qinggeouye
    思考题
    https://github.com/qinggeouye/GeekTime/blob/master/MathematicProgrammer/37_Matrix2PageRank/lesson37_1.py

            # 计算前后两次的 PageRank 数值的误差,判断是否需要结束迭代
            delta = list(map(abs, (pr/pr_tmp))) # pr_tmp 是前一次的值
            delta = abs(np.max(delta) - 1) # 最大误差的百分比
            if delta <= delta_threshold:
                return pr
            else:
                continue

    经计算,示例最大循环 6 次,迭代结束。
    round 6 [[0.46010028 0.03905229 0.46010028 0.02037357 0.02037357]]

    作者回复: 代码实现的很简洁,赞一个

    2019-03-23
    1
  • 晨曦后浪
    使用networkx中的pagerank函数,计算出来的数值和直接基于矩阵计算出来的数值有一点点差别,但相对大小还是一样的

    import networkx as nx
    import matplotlib.pyplot as plt

    # 创建有向图
    G = nx.DiGraph()
    # 添加带权重有向边
    G.add_weighted_edges_from([(1, 3, 1), (2, 1, 1), (2, 3, 1), (3, 1, 1), (5, 2, 1)])
    # 添加孤立节点
    G.add_node(4)
    # 计算pagerank值
    pagerank_list = nx.pagerank(G, alpha=0.85)
    print("pagerank 值是:", pagerank_list)

    nx.draw(G, with_labels=True, font_weight='bold')
    plt.show()


    pagerank 值是: {1: 0.43042160902192195, 3: 0.43042160902192195, 2: 0.06686758646711714, 5: 0.03614459774451953, 4: 0.03614459774451953}

    作者回复: 赞一下实践精神,确实我也发现了这点,估计是具体实现上有所区别。

    2019-03-11
    1
  • Paul Shan
    邻接矩阵的行表示每个节点出边,列表示每个节点的入边。行做归一化是为了出边平均分配权重,矩阵的乘法恰好按照入边累加pr值。
    随机跳转还是线性关系,依然可以用矩阵处理,这里用到矩阵分块思想。
    2019-09-27
收起评论
4
返回
顶部