-
矩阵:如何使用矩阵操作进行 PageRank 计算?
2019-03-21 20:16:40具有了二维数组的特性,矩阵就可以表达二元关系了,例如图中结点的邻接关系,或者是用户对物品的评分关系。而通过矩阵上的各种运算操作,我们就可以挖掘这些二元关系,在不同的应用场景下达到不同的目的。今天我就从...内容选自《程序员的数学基础课》
你好,我是黄申。今天我来说说矩阵。
矩阵由多个长度相等的向量组成,其中的每列或者每行就是一个向量。从数据结构的角度来看,我们可以把向量看作一维数组,把矩阵看作二维数组。
具有了二维数组的特性,矩阵就可以表达二元关系了,例如图中结点的邻接关系,或者是用户对物品的评分关系。而通过矩阵上的各种运算操作,我们就可以挖掘这些二元关系,在不同的应用场景下达到不同的目的。今天我就从图的邻接矩阵出发,展示如何使用矩阵计算来实现PageRank算法。
回顾PageRank链接分析算法
在讲马尔科夫模型的时候,我已经介绍了PageRank链接分析算法。所以,在展示这个算法和矩阵操作的关系之前,我们快速回顾一下它的核心思想。
PageRank是基于马尔科夫链的。它假设了一个“随机冲浪者”模型,冲浪者从某张网页出发,根据Web图中的链接关系随机访问。在每个步骤中,冲浪者都会从当前网页的链出网页中,随机选取一张作为下一步访问的目标。此外,PageRank还引入了随机的跳转操作,这意味着冲浪者不是按Web图的拓扑结构走下去,只是随机挑选了一张网页进行跳转。
基于之前的假设,PageRank的公式定义如下:
其中,pi表示第i张网页,Mi是pi的入链接集合,pj是Mi集合中的第j张网页。PR(pj)表示网页pj的PageRank得分,L(pj)表示网页pj的出链接数量,1/L(pj)就表示从网页pj跳转到pi的概率。α是用户不进行随机跳转的概率,N表示所有网页的数量。
PageRank的计算是采样迭代法实现的:一开始所有网页结点的初始PageRank值都可以设置为某个相同的数,例如1,然后我们通过上面这个公式,得到每个结点新的PageRank值。每当一张网页的PageRank发生了改变,它也会影响它的出链接所指向的网页,因此我们可以再次使用这个公式,循环地修正每个网页结点的值。由于这是一个马尔科夫过程,所以我们能从理论上证明,所有网页的PageRank最终会达到一个稳定的数值。整个证明过程很复杂,这里我们只需要知道这个迭代计算的过程就行了。
简化PageRank公式
那么,这个计算公式和矩阵操作又有什么联系呢?为了把问题简化,我们暂时不考虑随机跳转的情况,而只考虑用户按照网页间链接进行随机冲浪。那么PageRank的公式就简化为:
这个公式只包含了原公式中的Σ(PR(pj)/L(pj))部分。我们再来对比看看矩阵点乘的计算公式。
以上两个公式在形式上是基本一致的。因此,我们可以把Σ(PR(pj)/L(pj))的计算,分解为两个矩阵的点乘。一个矩阵是当前每张网页的PageRank得分,另一个矩阵就是邻接矩阵。所谓邻接矩阵,其实就是表示图结点相邻关系的矩阵。
假设xi,j是矩阵中第i行、第j列的元素,那么我们就可以使用xi,j表示从结点i到结点j的连接,放到PageRank的应用场景,xi,j就表示网页pi到网页pj的链接。最原始的邻接矩阵所包含的元素是0或1,0表示没有链接,而1表示有链接。
考虑到PageRank里乘积是1/L(pj),我们可以对邻接矩阵的每一行进行归一化,用原始的值(0或1)除以L(pj),而L(pj)表示有某张网页pj的出链接,正好是矩阵中pj这一行的和。所以,我们可以对原始的邻接矩阵,进行基于行的归一化,这样就能得到每个元素为1/L(pj)的矩阵,其中j表示矩阵的第j行。注意,这里的归一化是指让所有元素加起来的和为1。
为了方便你理解,我用下面这个拓扑图作为例子给你详细解释。
基于上面这个图,原始矩阵为:
其中第i行、第j列的元素值表示从结点i到j是不是存在链接。如果是,那么这个值为1;否则就为0。
按照每一行的和,分别对每一行进行归一化之后的矩阵就变为:
有了上述这个邻接矩阵,我们就可以开始最简单的PageRank计算。PageRank的计算是采样迭代法实现的。这里我把初始值都设为1,并把第一次计算的结果列在这里。
好了,我们已经成功迈出了第一步,但是还需要考虑随机跳转的可能性。
考虑随机跳转
经过上面的步骤,我们已经求得Σ(PR(pj)/L(pj))部分。不过,PageRank引入了随机跳转的机制。这一部分其实也是可以通过矩阵的点乘来实现的。我们把Σ(PR(pj)/L(pj))部分用A表示,那么完整的PageRank公式就可以表示为:
于是,我们可以把上述公式分解为如下两个矩阵的点乘:
我们仍然使用前面的例子,来看看经过随机跳转之后,PageRank值变成了多少。这里α取0.9。
我们前面提到,PageRank算法需要迭代式计算。为了避免计算后的数值越来越大甚至溢出,我们可以进行归一化处理,保证所有结点的数值之和为1。经过这个处理之后,我们得到第一轮的PageRank数值,也就是下面这个行向量:
[0.37027027 0.24864865 0.37027027 0.00540541 0.00540541]接下来,我们只需要再重复之前的步骤,直到每个结点的值趋于稳定就可以了。
使用Python进行实现
说到这里,我已经把如何把整个PageRank的计算,转换成多个矩阵的点乘这个过程讲完了。这样一来,我们就可以利用Python等科学计算语言提供的库,来完成基于PageRank的链接分析。为了展示具体的代码,我以之前的拓扑图为例,给你详细讲述每一步。
首先,我们要进行一些初始化工作,包括设置结点数量、确定随机跳转概率的α、代表拓扑图的邻接矩阵以及存放所有结点PageRank值的数组。下面是一段示例代码,在代码中我提供了注释供你参考。
import numpy as np# 设置确定随机跳转概率的alpha、网页结点数alpha = 0.9N = 5# 初始化随机跳转概率的矩阵jump = np.full([2,1], [[alpha], [1-alpha]], dtype=float)# 邻接矩阵的构建adj = np.full([N,N], [[0,0,1,0,0],[1,0,1,0,0],[1,0,0,0,0],[0,0,0,0,0],[0,1,0,0,0]], dtype=float)# 对邻接矩阵进行归一化row_sums = adj.sum(axis=1) # 对每一行求和row_sums[row_sums == 0] = 0.1 # 防止由于分母出现0而导致的Nanadj = adj / row_sums[:, np.newaxis] # 除以每行之和的归一化# 初始的PageRank值,通常是设置所有值为1.0pr = np.full([1,N], 1, dtype=float)
之后,我们就能采用迭代法来计算PageRank值。一般我们通过比较每个结点最近两次计算的值是否足够接近,来确定数值是不是已经稳定,以及是不是需要结束迭代。这里为简便起见,我使用了固定次数的循环来实现。如果你的拓扑图比较复杂,需要更多次迭代,我把示例代码和注释列在这里。
# PageRank算法本身是采样迭代方式进行的,当最终的取值趋于稳定后结束。for i in range(0, 20): # 进行点乘,计算Σ(PR(pj)/L(pj)) pr = np.dot(pr, adj) # 转置保存Σ(PR(pj)/L(pj))结果的矩阵,并增加长度为N的列向量,其中每个元素的值为1/N,便于下一步的点乘。 pr_jump = np.full([N, 2], [[0, 1/N]]) pr_jump[:,:-1] = pr.transpose() # 进行点乘,计算α(Σ(PR(pj)/L(pj))) + (1-α)/N) pr = np.dot(pr_jump, jump) # 归一化PageRank得分 pr = pr.transpose() pr = pr / pr.sum() print(\u0026quot;round\u0026quot;, i + 1, pr)
如果成功运行了上述两段代码,你就能看到每个结点最终获得的PageRank分数是多少。
Python中还有一些很不错的库,提供了直接构建拓扑图和计算PageRank的功能,例如networkx。你可以尝试使用这种库,构建样例拓扑图并计算每个结点的PageRank得分,最后和上述代码所计算的PageRank得分进行比较,验证一下上述代码的结果是不是合理。
总结
我们可以把向量看作一维数组,把矩阵看作二维数组。矩阵的点乘,是由若干个向量的点乘组成的,所以我们可以通过矩阵的点乘操作,挖掘多组向量两两之间的关系。
今天我们讲了矩阵的点乘操作在PageRank算法中的应用。通过表示网页的邻接二元关系,我们可以使用矩阵来计算PageRank的得分。在这个应用场景下,矩阵点乘体现了多个马尔科夫过程中的状态转移。
矩阵点乘和其他运算操作,还可以运用在很多其他的领域。例如,我在上一节介绍K均值聚类算法时,就提到了需要计算某个数据点向量、其他数据点向量之间的距离或者相似度,以及使用多个数据点向量的平均值来获得质心点的向量,这些都可以通过矩阵操作来完成。
另外,在协同过滤的推荐中,我们可以使用矩阵点乘,来实现多个用户或者物品之间的相似程度,以及聚集后的相似程度所导致的最终推荐结果。下一节,我会使用矩阵来表示用户和物品的二元关系,并通过矩阵来计算协同过滤的结果。
-
增广矩阵的秩判断解的个数_系数矩阵与增广矩阵的秩如何判断
2020-12-31 09:23:07系数矩阵是矩阵中的众多类型之一,简单来说系数矩阵就是将方程组的系数组成矩阵来计算方程的解。系数矩阵常常用来表示一些项目的数学关系,比如通过此类关系系数矩阵来证明各项目的正反比关系...展开全部
方法:阶级矩阵,两行不为e68a8462616964757a686964616f313334313766390的“行”,所以秩为2。矩阵,行的秩等于列的秩。纯粹只为矩阵求秩的话,也可以通过列变换把右边两列变为0。
系数矩阵是矩阵中的众多类型之一,简单来说系数矩阵就是将方程组的系数组成矩阵来计算方程的解 。系数矩阵常常用来表示一些项目的数学关系,比如通过此类关系系数矩阵来证明各项目的正反比关系。
增广矩阵(又称扩增矩阵)就是在系数矩阵的右边添上一列,这一列是线性方程组的等号右边的值。对系数矩阵进行的一个增广矩阵,切勿以为增广矩阵只是右端添加一列,其实是在原矩阵的右端添加一个矩阵,而线性方程组的右端恰好是一个列数为1的矩阵。
扩展资料:
矩阵的概念最早在1922年见于中文。1922年,程廷熙在一篇介绍文章中将矩阵译为“纵横阵”。1925年,科学名词审查会算学名词审查组在《科学》第十卷第四期刊登的审定名词表中,矩阵被翻译为“矩阵式”。
方块矩阵翻译为“方阵式”,而各类矩阵如“正交矩阵”、“伴随矩阵”中的“矩阵”则被翻译为“方阵”。1935年,中国数学会审查后,中华民国教育部审定的《数学名词》(并“通令全国各院校一律遵用,以昭划一”)中,“矩阵”作为译名首次出现。
-
matlab 判断两个矩阵有元素相等_如何使用MATLAB对Excel中的多参数进行计算?
2020-12-31 09:03:48THE STARTMATLAB和Excel这两者之间有着什么样的关系呢?今天我把之前学习以及用到的关于用MATLAB读写Excel数据,并进行计算处理的经验分享给需要的小伙伴。参加过数学建模的这个应该就很简单了,不经常使用的来说...THE START
MATLAB和Excel这两者之间有着什么样的关系呢?今天我把之前学习以及用到的关于用MATLAB读写Excel数据,并进行计算处理的经验分享给需要的小伙伴。参加过数学建模的这个应该就很简单了,不经常使用的来说可能有点麻烦。
小编这几天学习使用MATLAB也走了一些弯路(matlab小白
),从会C语言的室友那里找到了解决办法,所以这些编程思路基本都是相通的。
MATLAB是matrix&laboratory两个词的组合,意思为矩阵实验室,所以一定要了解到矩阵在MATLAB中的重要性。一些数据的处理以及计算都是在此基础之上进行的,使用MATLAB对Excel数据进行处理也是用矩阵来处理,所以首先要了解MATLAB关于矩阵的基础。主要会用到读取Excel数据、寻访矩阵元素、计算结果创建矩阵、MATLAB绘图、结果写入Excel。
1.创建矩阵
1.矩阵元素在[ ]内。
2.矩阵列元素之间用空格或者逗号分开。
3.矩阵的行与行之间用分号;隔开。
如下:
A=[1 2 3 ;4 5 6]
运行结果
B=[1,2,4;6,8,9]
2.矩阵寻访
寻访矩阵一般有三种方法,下标寻访、单元素寻访和多元素寻访。
下标寻访又有单下标寻访和双下标寻访,单下标寻访和双下标寻访意思一样只是表示方法不同。
双下标分别表示行与列,对应矩阵的元素的第几行,第几列。无论单下标寻访还是双下标寻访都是单元素,本次小编用到的也是单元素寻访。
1.双下标寻访命令用(,)表示:小括号前边写明矩阵名称,逗号前边表示行,后边表示列。如
A=[123 ;456] C=A(1,1)
运行结果
多元素寻访
多元素寻访从字面意思理解就是寻访某个矩阵的多个元素,访问整行、整列或者全部。命令需要注意冒号和逗号的使用,要在英文输入状态下。
使用命令如下
1.A(1:2:10)表示取数组或者矩阵的A的第一个元素到第十个元素,步长为2。
2.A([1 2 3])表示取数组或矩阵A中的第1、2、3个元素。
3.A(:,L)表示取矩阵A的第L列全部元素。
4.A(L,:)表示取矩阵A的第L行的全部元素。
5.A(i:i+k,:)表示取矩阵A的第i-i+k行的全部元素。
6.A(:,i:i+k)表示 取矩阵A的第i列到底第i+k列的全部元素。
7.A(i:i+k,k:k+l)表示取矩阵A的第i-i+k行内,并在第k-k+l列中的所有元素。3.读取Excel
Excel数据可以命令读取也可以直接导入,命令读取也很简单,在MATLAB右上角搜索框输入 help Excel 即可获得命令帮助。
读取命令
今天小编主要用到以下三个命令,其他命令可以在help文档中学习使用,help 文档是一个很好的东西,遇到问题可以在上边进行搜索,还有案例教学。括号内为Excel信息,filename(文件名),sheet(表格位置),xlRange(读取范围)。
num = xlsread(filename) num = xlsread(filename,sheet) num = xlsread(filename,sheet,xlRange)
Excel数据
查看Excel数据,确定数据读取范围。我的数据较多,从A1-E603。
读取命令
A=xlsread('D:MATLAB和Excel计算yuzhuyi.xls','sheet1','A1:E603');
小编的参数是5列,603行,所以要将5列中的每行同时带入MATLAB中进行计算,并输出一个结果,一共是603个结果。
下边开始逐个读取Excel中的数据进行计算,也就是矩阵的单个元素寻访。循环读取以及矩阵元素寻访使用如下,一共是5列数据。
for j=1:603 lam=A(j,1); H=A(j,4); L=A(j,2); k1=A(j,5); k2=A(j,3); %加入自己的计算公式,输出结果 zeros(j,1)=R;%将每次循环计算的结果放到矩阵中 end
5.增加变量
在上一步的基础上增加变量,依然将变量都放在Excel中进行读取计算,放在F行,变量是5-50间隔为0.1。(如果是等差数列可以直接使用for循环,无需在Excel中读取,小编主要演示MATLAB处理Excel)
变量读取命令为
B=xlsread('D:MATLAB和Excel计算yuzhuyi.xls','sheet1','F2:F451');
小编将这一列数据作为两个变量使用,即d1、d2命令如下
for m=1:450 d1=B(m,1); d2=B(m,1); %写入自己的计算公式 end
6.最终计算
将两个循环计算放在一块 for j=1:603 lam=A(j,1); H=A(j,4); L=A(j,2); k1=A(j,5); k2=A(j,3); for m=1:450 d1=B(m,1); d2=B(m,1); %写入自己的计算公式 %加入自己的计算公式,输出结果 zeros(j,m)=R;%将每次循环计算的结果放到矩阵中 end end
小编需要将全部的计算结果输出,也就是450列、604行。zeros(j,m)=R这个命令就是将全部结果放入矩阵,结果如下
7.绘图
选中某列的计算结果,点击绘图-选择样式。如果Excel中的绘图无法满足要求可以使用此方法进行绘图,还可以进行拟合等操作。
小编随便选择的样式
8.导出结果
将计算的结果写入到Excel中去,方便后续的计算保存。命令格式和读取数据时是一样的。使用命令
xlswrite('yuzhu.xlsx',zeros);
注意数据太多的话需要使用xlsx格式。数据太多,计算以及结果导出时间有点久。
运行结束后MATLAB会在软件内自动打开数据表格。
使用Excel打开数据
总结
至此MATLAB导入Excel数据进行计算就算完成了,小编这个只是简单的计算,实际的肯定比这个要复杂,命令也多,但是只要明白基本原理操作起来就很简单了。水平有限难免有错误,还请批评指出。
-
correl函数相关系数大小意义_如何用Excel计算相关系数矩阵?
2020-12-31 08:35:09相关性,是指两个变量之间的关联程度。一般来讲,两个变量之间的关系是以下三种之一:正相关、负相关、无相关。...在以前的博文中,曾经介绍过如何计算两个变量之间的相关系数,方法是用Excel的correl函数,在Excel...相关性,是指两个变量之间的关联程度。一般来讲,两个变量之间的关系是以下三种之一:正相关、负相关、无相关。相关系数被用来衡量两个变量之间相关性的强弱程度,数值变动范围在+1和-1之间。但要注意,相关系数只反映两个变量之间的相互关系及其相关方向,但无法确切地表明两个变量之间相关的程度。
在以前的博文中,曾经介绍过如何计算两个变量之间的相关系数,方法是用Excel的correl函数,在Excel帮助中关于correl函数功能的介绍部分举了一个例子,有A、B两组数据,分别位于Excel的A3至A7和B3至B7单元格区域。
在Excel中的空白栏处输入=correl(),括号内为取值单元格范围A3:A7和B3:B7
结果说明A、B两组数据之间的相关系数为99.7054%。
可见用correl函数计算两个变量之间的相关系数是可行的,但是如果变量的数量不是两个而是很多怎么办?比如5个、10个甚至是100个。。。,显然再用correl函数一个一个分别计算各个变量之间的相关系数就会非常麻烦。
有没有相对省时省力的方法来计算多变量之间的相关系数呢?方法是有的,这就需要相关系数矩阵,相关系数矩阵是由一组变量相互之间的相关系数构成的一张表。
举个例子,一个外汇投资组合配置了5个币种,分别为欧元/美元、英镑/美元、美元/日元、美元/澳大利亚元、美元/加拿大元,投资经理需要知道这5个汇率之间的相关系数以进行投资管理。
下面按步骤进行计算:
1、数据的获得和整理。登录美国联邦储备银行圣路易斯分行的主页https://fred.stlouisfed.org/,点击Category按照数据类型进行查询
2、在Category大项中选择Exchange Rates
3、在Exchange Rates项中选择Monthly Rates,即月度收盘价数据
4、在Monthly Rates项中选择U.S. / Euro Foreign Exchange Rate,即欧元/美元的汇率
5、图中有选项可选择数据的取值期间,本例中用的是5年,右侧有下载功能键可下载选定期间的汇率数据
6、2014年1月至2018年12月的欧元/美元汇率下载后略作格式调整,结果如下:
7、同理,下载英镑/美元、美元/日元、美元/澳大利亚元、美元/加拿大元的月度收盘价数据
8、下面用Excel的LN函数计算这5个汇率的月度涨跌百分比
9、依次打开“工具”、“数据分析”、“相关系数”
10、在“相关系数”功能界面的“输入区域”点按光标选中这5个汇率的月度回报率数据所在栏G2:J61,“分组方式”系统默认为逐列,在表中空白处选择数据“输出区域”,然后按确定键
11、以下为相关系数矩阵,可见欧元/美元和英镑/美元是正相关,相关系数为0.52835;欧元/美元和美元/日元是负相关,相关系数为-0.40798。其中,英镑/美元和美元/日元的相关系数为-0.03755,相关性最低,说明英镑/美元和美元/日元走势之间基本上没有任何关系。
12、用Excel的“数据分析”功能可以非常高效地计算各货币对之间的相关系数,但这一结果与correl函数的计算结果是否相符呢?下面来验证一下。
用correl函数计算的欧元/美元和英镑/美元之间的相关系数为0.528350341,与英镑/美元和美元/加元之间的相关系数为0.369657257,与上表中的数值相符。
-
excel中如何对矩阵得对角线进行求和_如何使用MATLAB对Excel中的多参数进行计算?...
2020-11-28 12:02:10THE STARTMATLAB和Excel这两者之间有着什么样的关系呢?今天我把之前学习以及用到的关于用MATLAB读写Excel数据,并进行计算处理的经验分享给需要的小伙伴。参加过数学建模的这个应该就很简单了,不经常使用的来说... -
深入计算机组成原理(二十七)SIMD:如何加速矩阵乘法
2019-09-21 22:37:26在编译的过程,超长指令字技术可以搞定指令前后的依赖关系,使得一次可以取一个指令包。 不过,CPU里的各种神奇的优化我们还远远没有说完。这一讲里,我们讲一讲最后两个提升CPU性能的架构设计。它们分别是,超线程... -
如何用邻接矩阵最快速地存储图的结构
2018-05-22 16:31:18对于图的储存结构,最常用有两种方式:邻接矩阵的存储邻接链表的存储今天我们就来介绍一下关于图结构中,邻接矩阵到底是什么,到底该如何存储,示例代码又是怎样等问题。我们从最简单的说起,如果给你下面一张图,...
-
使用vue搭建微信H5公众号项目
-
基于Flink+Hudi构建企业亿级云上实时数据湖教程(PC、移动、小
-
QT编程思想【C++,基于QT 6】
-
精通编译Makefile,Nina, 从底层uboot到Android
-
2021-03-04
-
fancensus_demo-源码
-
2021-03-04
-
ibatis开发指南.pdf.zip
-
HTML5游戏_基于DOM平台跳跃小游戏开发_7.浮动的金币精灵
-
OnlineClass-源码
-
华为1+X——网络系统建设与运维(中级)
-
黑色磷半导体纳米带中电荷迁移率的第一性原理预测
-
模仿大学的教务管理系统
-
一桶食用油的数字化
-
基于微信的同城小程序、校园二手交易小程序 毕业设计毕设源码使用教程
-
游戏防封必须了解的6大知识点
-
MySQL DML 语言(插入、更新与删除数据)
-
马士兵JVM课程笔记
-
Unity RUST 逆向安全开发
-
Filecoin资讯:lotus v1.5.0版本已于今日更新