精华内容
参与话题
问答
  • 随机游走模型

    千次阅读 2018-07-01 10:37:57
    6.2.1 随机游走模型(Random Surfer Model) 《这就是搜索引擎:核心技术详解》第6章链接分析,本章主要介绍一些著名的链接分析方法。本节为大家介绍随机游走模型(Random Surfer Model)。 6.2 两个概念模型及算法...

    6.2.1 随机游走模型(Random Surfer Model)

    《这就是搜索引擎:核心技术详解》第6章链接分析,本章主要介绍一些著名的链接分析方法。本节为大家介绍随机游走模型(Random Surfer Model)。

    6.2 两个概念模型及算法之间的关系

    在介绍具体链接分析算法之前,首先介绍两个概念模型,并对各个链接分析算法之间的关系进行说明,这样有助于读者从宏观角度理解各个算法的基本思路与传承关系。

    6.2.1 随机游走模型(Random Surfer Model)

    互联网用户在上网时,往往有类似的网络行为:输入网址,浏览页面,然后顺着页面的链接不断打开新的网页。随机游走模型就是针对浏览网页的用户行为建立的抽象概念模型。之所以要建立这个抽象概念模型,是因为包括PageRank 算法在内的很多链接分析算法都是建立在随机游走模型基础上的。

    图1给出了随机游走模型的示意图。在最初阶段,用户打开浏览器浏览第1 个网页,假设我们有一个虚拟时钟用来计时,此时可以设定时间为1,用户在看完网页后,对网页内某个链接指向的页面感兴趣,于是点击该链接,进入第2 个页面,此时虚拟时钟再次计时,时钟走向字2,如果网页包含了k 个出链,则用户从当前页面跳转到任意一个链接所指向页面的概率是相等的。用户不断重复以上过程,在相互有链接指向的页面之间跳转。如果对于某个页面所包含的所有链接,用户都没有兴趣继续浏览,则可能会在浏览器中输入另外一个网址,直接到达该网页,这个行为称为远程跳转(Teleporting)。假设互联网中共有m 个页面,则用户远程跳转到任意一个页面的概率也是相等的,即为1/m。随机游走模型就是一个对直接跳转和远程跳转两种用户浏览行为进行抽象的概念模型。

     
    (点击查看大图)图1 随机游走模型示意图

    下面我们给出一个具体的随机游走模型的例子,为简单起见,该例子并未引入远程跳转行为。

    在如图2 所示的例子里,假设互联网由A、B、C 3 个网页构成,其相互链接关系如图中页面节点之间的有向边所示。根据链接关系,即可计算页面节点之间的转移概率,比如对于节点A 来说,只有唯一一个出链指向节点B,所以从节点A 跳转到节点B 的概率为1,对于节点C 来说,其对节点A 和B 都有链接指向,所以转向任意一个其他节点的概率为1/2。

     
    (点击查看大图)图2 随机游走模型示例

    假设在时刻1,用户浏览页面A,之后经由链接进入页面B,然后进入页面C,此时面临两种可能选择,跳转进入页面A 或者页面B 皆可,两者概率相同,都为1/2。

    假设例子中的互联网包含不止3 个页面,而是由10 个页面构成,此时用户既不想跳回页面A,也不想跳回页面B,则可以按照1/10 的概率跳入其他任意一个页面,即进行远程跳转。

    转载来自: 原文地址

    展开全文
  • 图——随机游走算法

    千次阅读 2019-09-26 17:26:00
    文章目录推荐基本概念PageRankPersonalRankTextRankSimRank 推荐基本概念 其中用户user=[A,B,C],物品item=[a,b,c,d],用户和物品有以下的关系 上述便是一个典型的二分图,我们用G(V,E)来表示,其中V为用户user和...

    推荐基本概念

    其中用户user=[A,B,C],物品item=[a,b,c,d],用户和物品有以下的关系
    在这里插入图片描述
    上述便是一个典型的二分图,我们用G(V,E)来表示,其中V为用户user和物品item组成的顶点集即[A,B,C,a,b,c,d],而E则代表每一个二元组(u,i)之间对应的边e(u,i),我们这里不考虑用户对物品的喜爱程度,即默认喜爱则e=1,不喜爱则e=0。

    那么我们如何使用上述的二分图模型进行物品的推荐呢?根据用户与物品的相关性,对于相关性高的顶点有如下的定义:

    (1)两个顶点之间有很多路径相连

    (2)连接两个顶点之间的路径长度都比较短

    (3)连接两个顶点之间的路径不会经过度比较大的顶点

    上面有一个概念需要理解,度,顶点的度是指和该顶点相关联的边数。

    基于上述的定义,我们这里使用基于随机游走的算法来计算

    PageRank

    它的基本思想是,假设网页之前通过超链接相互连接,互联网上的所有网页便构成了一张图。用户随机的打开一个网页,并通过超链接跳转到另一个网页。每当用户到达一个网页,他都有两种选择,停留在当前网页或者通过继续访问其他网页。如果用户继续访问网页的概率为d,那么用户停留在当前网页的概率便是1-d。如果用户继续访问其他网页,则会以均匀分布的方式随机访问当前网页指向的另一网页,这是一个随机游走的过程。当用户多次访问网页后,每一个网页被访问到的概率便会收敛到某个值,而计算出来的结果便可以用于网页排名,我们用以下的公式来表示:
    在这里插入图片描述
    其中PR(i)是网页i被访问到的概率,d代表用户继续访问网页的概率,N为所有网页的数量,in(i)代表所有指向网页i的网页集合,out(j)代表网页j指向的其他网页集合。

    接下来我们分析一下这个公式,网页i被访问到的概率由两部分组成:

    第一部分是网页i作为起点,第一个被用户点击后停留在当前页面的概率,即:
    在这里插入图片描述
    第二部分是用户点击其他网页后(无论网页i是不是起点),再次跳转回到网页i的概率:
    在这里插入图片描述
    这两部分的和便是网页i被点击到的概率

    PersonalRank

    在pageRank算法中,计算出来的是每一个顶点相对其他顶点的相关性,代入到我们的用户物品二分图中,这显然不是我们想要的,我们需要的是所有物品相对于特定某个用户的相关性,有公式如下:
    在这里插入图片描述
    在这里插入图片描述
    对比pageRank,不同点只在于r的值不同,u代表根节点,即我们的目标用户节点,意思便是我们每次都是从目标用户节点出发,进行随机游走,而不同于pageRank的起点是随机从所有网页中进行选择,personalRank算法得出的结果便是所有顶点相对于目标用户结点的相关性

    TextRank

    TextRank 算法是一种用于文本的基于图的排序算法,通过把文本分割成若干组成单元(句子),构建节点连接图,用句子之间的相似度作为边的权重,通过循环迭代计算句子的TextRank值,最后抽取排名高的句子组合成文本摘要

    • 抽取型摘要:这种方法依赖于从文本中提取几个部分,例如短语、句子,把它们堆叠起来创建摘要。因此,这种抽取型的方法最重要的是识别出适合总结文本的句子。
    • 抽象型摘要:这种方法应用先进的NLP技术生成一篇全新的总结。可能总结中的文本甚至没有在原文中出现

    现在我们已经掌握了PageRank,让我们理解TextRank算法。我列举了以下两种算法的相似之处:

    • 用句子代替网页
    • 任意两个句子的相似性等价于网页转换概率
    • 相似性得分存储在一个方形矩阵中,类似于PageRank的矩阵M
      在这里插入图片描述

    SimRank

    解决数据稀疏性的问题

    展开全文
  • Random Walk(随机游走

    万次阅读 2019-02-24 17:24:10
    金融和经济模型和概率统计学难以分离,对于这样的随机二级市场数据的理解和操作也是计算机科学的一个领域,十分有魅力的计算金融学。 普通数据挖掘方法大多都是确定性模型,对于输入的输出往往没有随机性,而一些能...

    在这里插入图片描述
    本篇文章主要整理随机游走的基本思想,如果是深度学习图方法中的DeepWalk随机游走,传送门整理了几种流行的图嵌入方法。


    金融和经济模型和概率统计学难以分离,对于这样的随机二级市场数据的理解和操作也是计算机科学的一个领域,十分有魅力的计算金融学。

    普通数据挖掘方法大多都是确定性模型,对于输入的输出往往没有随机性,而一些能给出概率的随机性模型似乎更加的适用,如蒙特卡洛模拟,即模拟输入一堆的随机数进行评估。

    几何布朗运动(Brownian motion)
    布朗运动是将看起来连成一片的液体,在高倍显微镜下看其实是由许许多多分子组成的。液体分子不停地做无规则的运动,不断地随机撞击悬浮微粒。当悬浮的微粒足够小的时候,由于受到的来自各个方向的液体分子的撞击作用是不平衡的。在某一瞬间,微粒在另一个方向受到的撞击作用超强的时候,致使微粒又向其它方向运动,这样,就引起了微粒的无规则的运动就是布朗运动。(布朗运动指的是分子迸出的微粒的随机运动,而不是分子的随机运动。)

    即布朗运动代表了一种随机涨落现象。普遍的观点仍认为,股票市场是随机波动的,随机波动是股票市场最根本的特性,是股票市场的常态。(随机现象的数学定义是:在个别试验中其结果呈现出不确定性;在大量重复试验中其结果又具有统计规律性的现象。)而布朗运动假设是现代资本市场理论的核心假设。

    随机游走
    其概念接近于布朗运动,是布朗运动的理想数学状态。任何分子所带的守恒量都各自对应着一个扩散运输定律。
    随机游走过程StS_t遵循几何布朗运动,满足微分方程:dSt=uStdt+σStdWtdS_t=uS_tdt+\sigma S_tdW_tdSt/St=udt+σdWtdS_t/S_t=udt+\sigma dW_t设定初试状态S0,根据伊藤积分,可以解出:St=S0exp((uσ2/2)t+σWt)S_t=S_0exp((u-\sigma^2/2)t+\sigma W_t)
    其中μ\mu (‘百分比drift’) 和σ\sigma (‘百分比volatility’)是常量。

    import matplotlib.pyplot as plt
    import numpy as np
    
    #rect=[0.1,5.0,0.1,0.1]
    fig=plt.figure()
    
     #time span
    T=2
    #drift factor飘移率
    mu=0.1 
    #volatility波动率
    sigma=0.04 
    #t=0初试价
    S0=20 
    #length of steps
    dt=0.01 
    N=round(T/dt)
    t=np.linspace(0,T,N)
    
    #布朗运动
    W=np.random.standard_normal(size=N)
    W=np.cumsum(W)*np.sqrt(dt)
    
    X=(mu-0.5*sigma**2)*t+sigma*W
    
    S=S0*np.exp(X)
    
    plt.plot(t,S,lw=2)
    plt.show()
    
    

    可以模拟出如下图:
    在这里插入图片描述
    一维的随机游走模拟:
    在这里插入图片描述
    在3D的模拟情形:
    在这里插入图片描述

    展开全文
  • 6.2.4 随机游走(Random Walk)

    万次阅读 2016-03-31 11:22:03
    随机游走这一名称由Karl Pearson在1905年提出[Pearson, K. (1905). The problem of the Random Walk. Nature. 72, 294.],本来是基于物理中"布朗运动"相关的微观粒子的运动形成的一个模型,后来这一模型作为数理金融...


    随机游走这一名称由Karl Pearson在1905年提出[Pearson, K. (1905). The problem of the Random Walk. Nature. 72, 294.],本来是基于物理中"布朗运动"相关的微观粒子的运动形成的一个模型,后来这一模型作为数理金融中的重要的假设,指的是证券价格的时间序列将呈现随机状态,不会表现出某种可观测或统计的确定趋势,即证券价格的变动是不可预测的。在计算机领域,随机游走则主要用来进行一种关系的传递分析,如图6-5所示。

     
    图6-5  随机游走

    以q表示查询,而d表示查询结果中的文档。则查询q1所对应的文档为d1和d2,并不包含d3。但不能简单断定q1和d3无关。因为查询q2所对应的文档包含了与查询q1相关的所有文档d1、d2,此外还包含了d3。文档d1、d2和d3通过共同的查询q2建立了关联,而查询q1和q2则通过共同的文档d1、d2建立了关联,关联性的传递意味着d3也许是和q1具有还未被表达的关联性。为表达这种关系的传递,可以视该图为一个随机场,依据结点间的连通性和转移概率进行随机游走,以传递结节的关联关系。

    可以用一个简单例子来说明这种方法的实际意义,如某用户用q1查询超市所售的糖,返回水果糖和奶糖两个结果;另一位用户则用q2查询超市中所售甜食,不仅返回了水果糖、奶糖,还返回了巧克力。而巧克力实际上和第一位用户的查询意图相关性还是相当高的。

    转自http://book.51cto.com/art/201107/276845.htm

    展开全文
  • 浅谈随机游走

    万次阅读 2014-01-11 14:21:26
    随机游走(random walk)矩阵可以看做是马尔科夫链的一种特例。对于一个图G的邻接矩阵A来说,A中的非零元素描述了图G中每一条边的权重(这里一般要求A的对角线为零)。这个权重描述了节点之间的相似性。关于Image ...
  • matlab练习程序(随机游走图像)

    千次阅读 2019-01-08 00:43:54
    随机游走类似布朗运动,就是随机的向各个方向走吧。 虽然代码没什么技术含量,不过产生的图像实在太漂亮了,所以还是贴上来吧。 产生的图像: matlab代码如下: clear all;close all;clc n=70000; %游走...
  • Python实现随机游走&详细解释

    千次阅读 2019-06-11 11:36:57
    Python实现随机游走 1、单一的500步随机游走的例子,从0开始,步长为1和-1,且以相等的概率出现。 注:需要python的内置函数random,不需安装,直接导入即可 import random -*- coding: utf-8 -*- import ...
  • 随机游走

    2019-01-27 14:54:46
    一、CF基本算法 1、基于近邻 包含:基于用户、基于项目、混合方法 以上三种都使用了皮尔森算法 缺点:数据稀疏 2、基于模型 训练数据集 基于以上两种,添加更加复杂的算法——内容信息、时间信息 ...
  • 随机游走与扩散 扩散定律是普适的 由扩散支配的亚细胞世界 摩擦与扩散是一对双胞胎——爱因斯坦关系 爱因斯坦关系溯源——涨落耗散定理 一杯咖啡是随机的吗? 生活中有许多例子是牛顿力学基本能完全描述的...
  • 随机游走 随机游走(Random Walk,缩写为 RW),是一种数学统计模型,它是一连串的轨迹所组成,其中每一次都是随机的。它能用来表示不规则的变动形式,如同一个人酒后乱步,所形成的随机过程记录。 1905年,由卡尔...
  • 随机游走

    2018-10-16 16:18:11
    #include<bits/stdc++.h> #define N 110000 #define inf 1e9+7 #define ll long long using namespace std; inline int read() { int x=0,flag=1; char ch=0;... ch=ge...
  • 随机游走算法

    千次阅读 2020-06-16 17:27:24
    随机游走(Random Walk,缩写为 RW),又称随机游动或随机漫步,是一种数学统计模型,它是一连串的轨迹所组成,其中每一次都是随机的。它能用来表示不规则的变动形式,如同一个人酒后乱步,所形成的随机过程记录。...
  • 随机游走

    千次阅读 2016-11-12 21:21:05
    今天,他遇到了这么一个概念:随机游走随机游走指每次从相邻的点中随机选一个走过去,重复这样的过程若干次。YJC很聪明,他很快就学会了怎么跑随机游走。为了检验自己是不是欧洲人,他决定选一棵树,每条边边权为...
  • 随机游走

    千次阅读 2016-11-14 21:06:51
    今天,他遇到了这么一个概念:随机游走随机游走指每次从相邻的点中随机选一个走过去,重复这样的过程若干次。YJC很聪明,他很快就学会了怎么跑随机游走。为了检验自己是不是欧洲人,他决定选一棵树,每条边边权为1...
  • 随机游走

    2018-03-20 07:48:00
    题目描述 给定一张有 nn个点 mm条边的图,生成 1∼n1\sim n的全排列,假设一个排列是 pp, SS是当前最大独立集;如果 S∪pi是独立集就令 S=S∪piS=S\cup {p_i} ;求这 n!n!个独立集有多少个为最大独立集,答案对 ...
  • 重启随机游走算法

    2019-03-23 13:46:16
    重启随机游走算法,带有小例子。
  • 一 基本概念 基于图的模型是推荐系统中相当重要的一种方法,以下内容的基本思想是将用户行为数据表示为一系列的二元组,每一个二元组(u,i)代表用户u对物品i产生过行为,这样便可以将这个数据集表示为一个二分图。...
  • 随机游走

    2019-10-04 18:57:14
    题目描述 给定一张有 nn个点 mm条边的图,生成 1∼n1\sim n的全排列,假设一个排列是 pp, SS是当前最大独立集;如果 S∪pi是独立集就令 S=S∪piS=S\cup {p_i} ;求这 n!n!个独立集有多少个为最大独立集,答案对 ...
  • <<MARKOV CHAINS AND RANDOM WALKS>> 非常不错的一本英文数据,内容是关于马尔科夫链和随机游走相关的,讲的比较清楚
  • Python RWR,可重启的随机游走源代码,可重启的随机游走源代码

空空如也

1 2 3 4 5 ... 20
收藏数 6,118
精华内容 2,447
关键字:

随机游走