随机游走算法

㈠ 协同过滤算法

用户行为数据在网站上最简单的存在形式就是日志，比如用户在电子商务网站中的网页浏览、购买、点击、评分和评论等活动。 用户行为在个性化推荐系统中一般分两种——显性反馈行为(explicit feedback)和隐性反馈 行为(implicit feedback)。显性反馈行为包括用户明确表示对物品喜好的行为。网站中收集显性反馈的主要方式就是评分和喜欢/不喜欢。隐性反馈行为指的是那些不能明确反应用户喜好 的行为。最具代表性的隐性反馈行为就是页面浏览行为。 按照反馈的明确性分，用户行为数据可以分为显性反馈和隐性反馈，但按照反馈的方向分， 又可以分为正反馈和负反馈。正反馈指用户的行为倾向于指用户喜欢该物品，而负反馈指用户的 行为倾向于指用户不喜欢该物品。在显性反馈中，很容易区分一个用户行为是正反馈还是负反馈， 而在隐性反馈行为中，就相对比较难以确定。

在利用用户行为数据设计推荐算法之前，研究人员首先需要对用户行为数据进行分析，了解 数据中蕴含的一般规律，这样才能对算法的设计起到指导作用。

(1) 用户活跃度和物品流行度

(2) 用户活跃度和物品流行度的关系

一般认为，新用户倾向于浏览热门的物品，因为他 们对网站还不熟悉，只能点击首页的热门物品，而老用户会逐渐开始浏览冷门的物品。如果用横坐标表示用户活跃度，纵坐标表示具有某个活跃度的所有用户评过分的物品的平均流行度。图中曲线呈明显下 降的趋势，这表明用户越活跃，越倾向于浏览冷门的物品。

仅仅基于用户行为数据设计的推荐算法一般称为协同过滤算法。学术界对协同过滤算法进行了深入研究，提出了很多方法，比如基于邻域的方法(neighborhood-based)、隐语义模型 (latent factor model)、基于图的随机游走算法(random walk on graph)等。在这些方法中， 最着名的、在业界得到最广泛应用的算法是基于邻域的方法，而基于邻域的方法主要包含下面两种算法。

基于用户的协同过滤算法 ：这种算法给用户推荐和他兴趣相似的其他用户喜欢的物品

基于物品的协同过滤算法： 这种算法给用户推荐和他之前喜欢的物品相似的物品

基于邻域的算法是推荐系统中最基本的算法，该算法不仅在学术界得到了深入研究，而且在 业界得到了广泛应用。基于邻域的算法分为两大类，一类是基于用户的协同过滤算法，另一类是 基于物品的协同过滤算法。现在我们所说的协同过滤，基本上就就是指基于用户或者是基于物品的协同过滤算法，因此，我们可以说基于邻域的算法即是我们常说的协同过滤算法

(1) 基于用户的协同过滤算法（UserCF）

基于用户的协同过滤算法的基本思想是：在一个在线个性化推荐系统中，当一个用户A需要个性化推荐 时，可以先找到和他有相似兴趣的其他用户，然后把那些用户喜欢的、而用户A没有听说过的物品推荐给A。

Ø 从上面的描述中可以看到，基于用户的协同过滤算法主要包括两个步骤。 第一步：找到和目标用户兴趣相似的用户集合。 第二步： 找到这个集合中的用户喜欢的，且目标用户没有听说过的物品推荐给目标用户。

这里，步骤1的关键是计算两个用户的兴趣相似度，协同过滤算法主要利用行为的相似度计算兴趣的相似度。给定用户u和用户v，令N(u)表示用户u曾经有过正反馈的物品集合，令N(v) 为用户v曾经有过正反馈的物品集合。那么我们可以通过以下方法计算用户的相似度：

基于余弦相似度

(2) 基于物品的协同过滤算法（itemCF）
与UserCF同理
(3) UserCF和itemCF的比 较

首先我们提出一个问题，为什么新闻网站一般使用UserCF，而图书、电商网站一般使用ItemCF呢？ 首先回顾一下UserCF算法和ItemCF算法的推荐原理。UserCF给用户推荐那些和他有共同兴 趣爱好的用户喜欢的物品，而ItemCF给用户推荐那些和他之前喜欢的物品类似的物品。从这个算 法的原理可以看到，UserCF的推荐结果着重于反映和用户兴趣相似的小群体的热点，而ItemCF 的推荐结果着重于维系用户的历史兴趣。换句话说，UserCF的推荐更社会化，反映了用户所在的小型兴趣群体中物品的热门程度，而ItemCF的推荐更加个性化，反映了用户自己的兴趣传承。 在新闻网站中，用户的兴趣不是特别细化，绝大多数用户都喜欢看热门的新闻。个性化新闻推荐更加强调抓住 新闻热点，热门程度和时效性是个性化新闻推荐的重点，而个性化相对于这两点略显次要。因 此，UserCF可以给用户推荐和他有相似爱好的一群其他用户今天都在看的新闻，这样在抓住热 点和时效性的同时，保证了一定程度的个性化。同时，在新闻网站中，物品的更新速度远远快于新用户的加入速度，而且 对于新用户，完全可以给他推荐最热门的新闻，因此UserCF显然是利大于弊。

但是，在图书、电子商务和电影网站，比如亚马逊、豆瓣、Netflix中，ItemCF则能极大地发 挥优势。首先，在这些网站中，用户的兴趣是比较固定和持久的。一个技术人员可能都是在购买 技术方面的书，而且他们对书的热门程度并不是那么敏感，事实上越是资深的技术人员，他们看 的书就越可能不热门。此外，这些系统中的用户大都不太需要流行度来辅助他们判断一个物品的 好坏，而是可以通过自己熟悉领域的知识自己判断物品的质量。因此，这些网站中个性化推荐的 任务是帮助用户发现和他研究领域相关的物品。因此，ItemCF算法成为了这些网站的首选算法。 此外，这些网站的物品更新速度不会特别快，一天一次更新物品相似度矩阵对它们来说不会造成 太大的损失，是可以接受的。同时，从技术上考虑，UserCF需要维护一个用户相似度的矩阵，而ItemCF需要维护一个物品 相似度矩阵。从存储的角度说，如果用户很多，那么维护用户兴趣相似度矩阵需要很大的空间， 同理，如果物品很多，那么维护物品相似度矩阵代价较大

下表是对二者的一个全面的表较：

㈡ Graph Embedding之metapath2vec

  Metapath2vec是Yuxiao Dong等于2017年提出的一种用于异构信息网络（Heterogeneous Information Network, HIN）的顶点嵌入方法。 metapath2vec 使用基于meta-path的random walks来构建每个顶点的异构邻域，然后用 Skip-Gram 模型来完成顶点的嵌入。在 metapath2vec 的基础上，作者还提出了 metapath2vec++ 来同时实现异构网络中的结构和语义关联的建模。

  作者首先提到了基于神经网络的学习模型可以捕获不同类型数据的潜在信息和复杂关系，如图像，语音和语言等。同样地，基于神经网络的模型针对复杂网络的表示学习也有非常好的效果。作者提到了当前已经提出的采用了word2vec思想的网络表示算法，如 Deepwalk ， node2vec 以及 LINE 等。但是作者也明确指出了，上述这些算法虽然可以用于网络表示学习，但仅适合那些只包含一类顶点类型和边类型的同构网络（Homogeneous Networks），并不能很好地用于包含多种顶点类型和边类型的复杂关系网络。于是作者在基于meta-path的基础上，提出了能很好应对指定scheme结构的异构复杂关系网络的表示学习方法—— metapath2vec 和 metapath2vec++ 。 metapath2vec 的目标是最大化保留一个异构网络的结构和语义信息的似然，首先使用基于meta-path的随机游走获取异构网络中每种不同类型顶点的异构领域，然后使用扩展的Skip-Gram处理前面获取的顶点领域，最终学习每个不同类型顶点的网络嵌入表示。跟之前的网络嵌入成果相比，作者认为metapath2vec具有以下贡献：

  异构网络定义为： ，其中每个顶点和边对应的映射函数为： 和 ，其中 和 分布表示顶点和边的类型，另外还满足 。

  异构网络表征学习定义为：给定一个异构网络 ，学习一个 维的潜在表征 可以表征网络中顶点之间的结构信息和语义场景关系。异构网络表征学习的输出是一个低维的矩阵 ，其中 行是一个 维的向量，表示顶点 的表征。这里需要注意的是，虽然顶点的类型不同，但是不同类型的顶点的表征向量映射到同一个维度空间。由于网络异构性的存在，传统的基于同构网络的顶点嵌入表征方法很难有效地直接应用在异构网络上。

  在正式介绍metapath2vec方法之前，作者首先介绍了同构网络上的基于random walk的graph embedding算法的基本思想，如：Deepwalk和node2vec等。该类方法采用了类似word2vec的思想，即：使用skip-gram模型对每个顶点的局部领域顶点信息进行预测，进而学习到每个顶点的特征表示。通常，对于一个同构网络 ，目标是从每个顶点的局部领域上最大化网络似然：
其中 表示顶点 的领域，如1-hop以内的邻接顶点，2-hop以内的邻接顶点。 表示给定顶点 后，顶点 的条件概率。下面正式给出基于异构网络的metapath2vec嵌入算法。metapath2vec分为两个部分，分别是Meta-Path-Based Random Walks和Heterogeneous Skip-Gram。

  在metapath2vec中，作者使用Skip-Gram模型通过在顶点 的领域 上最大化条件概率来学习异构网络 上的顶点表征。
其中 表示顶点 的类型为 的领域顶点集合。 通常定义为一个softmax函数，即：
其中 是矩阵 的第 行矩阵，表示顶点 的嵌入向量。为了提升参数更新效率，metapath2vec采用了Negative Sampling进行参数迭代更新，给定一个Negative Sampling的大小 ，参数更新过程如下：
其中 ， 是一个negative node 在M次采样中的预定义分布。
metapath2vec通过不考虑顶点的类型进行节点抽取来确定当前顶点的频率。

  在同构网络中，DeepWalk和node2vec等算法通过随机游走的方式来构建Skip-Gram模型的上下文语料库，受此启发，作者提出了一种异构网络上的随机游走方式。在不考虑顶点类型和边类型的情况下， 表示从顶点 向其邻居顶点 的转移概率。然而Sun等已证明异构网络上的随机游走会偏向于某些高度可见的类型的顶点，这些顶点的路径在网络中具有一定的统治地位，而这些有一定比例的路径指向一小部分节点的集合。鉴于此，作者提出了一种基于meta-path的随机游走方式来生成Skip-Gram模型的邻域上下文。该随机游走方式可以同时捕获不同类型顶点之间语义关系和结构关系，促进了异构网络结构向metapath2vec的Skip-Gram模型的转换。
  一个meta-path的scheme可以定义成如下形式：
其中
表示顶点 和顶点 之间的路径组合。例如图（a）中，“APA”表示一种固定语义的meta-path，“APVPA”表示另外一种固定语义的meta-path。并且很多之前的研究成果都表明，meta-path在很多异构网络数据挖掘中很很大作用。因此，在本文中，作者给出了基于meta-path的随机游走方式。给定一个异构网络 和一个meta-path的scheme :
那么在第 步的转移概率定义如下：
其中 ， 表示顶点 的 类型的领域顶点集合。换言之， ，也就是说随机游走是在预定义的meta-path scheme 条件下的有偏游走。初次之外，meta-path通常是以一种对称的方式来使用，也就是说在上述路径组合中，顶点 的类型和 的类型相同。即：
基于meta-path的随机游走保证不同类型顶点之间的语义关系可以适当的融入Skip-Gram模型中。

  metapath2vec在为每个顶点构建领域时，通过meta-path来指导随机游走过程向指定类型的顶点进行有偏游走。但是在softmax环节中，并没有顶点的类型，而是将所有的顶点认为是同一种类型的顶点。换言之，metapath2vec在Negative Sampling环节采样的negative 样本并没有考虑顶点的类型，也就是说metapath2vec支持任意类型顶点的Negative Sampling。于是作者在metapath2vec的基础上又提出了改进方案metapath2vec++。

在metapath2vec++中，softmax函数根据不同类型的顶点的上下文 进行归一化。也就是说 根据固定类型的顶点进行调整。即：
其中 是网络中 类型顶点集合。在这种情况下，metapath2vec++为Skip-Gram模型的输出层中的每种类型的领域指定了一个多项式分布的集合。而在metapath2vec，DeepWalk和node2vec中，Skip-Gram输出多项式分布的维度等于整个网络中顶点的数目，然而对于metapath2vec++的Skip-Gram，其针对特定类型的输出多项式的维度取决于网络中当前类型顶点的数目。如图（c）所示。最终我们可以得到如下的目标函数：
可以得出其梯度如下：
其中 是一个指示函数，用来指示 在 时是否是顶点 的上下文。该算法使用随机梯度下降进行参数优化。整个metapath2vec++算法如下。

  以上就是metapath的全部内容，该算法沿用了之前同构网络上基于随机游走的Embedding算法的思想，作者通过在异构网络上，引入预置meta-paths来指导随机游走的过程，另外通过meta-path的领域来改进传统的Skip-Gram模型，使得该嵌入方法不仅能保留网络中的异构信息和语义关系信息，同时针对大规模网络，性能也有了本质上的提升。具体细节可以参考原论文，链接如下。

㈢ 随机游走图 稳定分布怎么 计算

对于同样的输入，每次执行同样的算法会有不同的输出”这句话对“随机算法”是不一定成立的，事实上它往往是不成立的。许多随机算法的随机性体现在：1、运行时间随机，但大多数情况下会低于某个值；2、计算结果大多数时候正确，但是有极低概率会给出不正确的结果。 对于random walker算法，它的前进路线是由势函数引导的，在图形边界，这个势函数会非常大，所以random walker穿过这个边界的概率很低。而且，random walker算法不是要真的执行“走”的这个过程，而是要直接算“从任一点出发，先到达哪个初始点的概率更高”。这种情况下，结果基本是确定的。就好像问“一个脚上绑着10kg重物的人，和一个没有带重物的人赛跑，谁获胜的概率高”？确实前者不是没有可能获胜，但是你比较概率大小的话，结果是显而易见的。

㈣ 随机游走算法是什么

这个……设置一个1到4的随机数（假定游走的空间是二维的），如果随机数结果为1，就向上走一个单位，如果为2，向左走一个单位，如果为3，向下走一个单位，如果为4，向右走一个单位，每走一个单位，重复一遍上面的过程。

㈤ 辫状河道的二维随机游走模型模拟

王家华

（西安石油学院计算机科学系，西安710065）

张团峰

（西安石油学院基础科学部，西安710065）

黄沧钿

（西安石油学院计算机科学系，西安710065）

摘要本文用随机游走模型模拟了频繁连接和分支的辫状河道的二维分布。作为渗透率、孔隙度和泥质含量三个参数的线性组合，二维网格数据PP（i,j）可用来区分网格节点的类型：河道、泥岩或介于河道与泥岩之间的砂岩。使用了分数维布朗运动来模拟油井中这三个参数的二维分布。首先定义河道中心线，然后再考虑河道边界。在文末，描述了辽河油田的有100口井的沈－84地区的一个研究实例。

关键词随机游走模拟实现辫状河道

1引言

研究区位于三角洲前扇和三角洲平原之间的子区域，沉积物来自于东北方向，由辫状河道和介于河道与泥岩之间的砂岩组成。由于三角洲扇沉积时弱的水动力条件，故位于河道和点砂坝之间的砂岩很少，且辫状河道是研究区域的主骨架。

在储层中，单独河道砂体有鞋带状和扁豆状两种形态。所有的辫状河道呈东北到西南方向展布。由于河道宽度小，在沉积过程中河道频繁地发生分支，所以这些辫状河道常常分路迂回、相互连接、相互交叉。

储层的油藏物理参数变化很大。例如，在相同的层，纵向和横向的渗透率可以相差10～100倍。

2储层油藏物理参数的条件模拟

由于储层强烈的非均质性，可以用分数维布朗运动来模拟地球物理参数的分布。即可用二维随机场｛Z（x）；x∈D）来建立地球物理参数模型，并假设随机场的增量满足从一种趋势移走的高斯过程。在研究中，使用了一次趋势面。期望值EZ（x）选择如下：

f^T（x）β＝β₁＋β₂x₁＋β₃x₂

式中：β^T＝（β₁，β₂，β₃）。

考虑滤掉这种趋势面的随机过程：

Y（x）=Z（x）-f^T（x）β

式中：Y（x）为EY（x）=0的平稳高斯过程。令D_L为研究区域中的一个大小为（2ⁿ+1）×（2ⁿ+1）的网格系统，N₀=（2ⁿ+1）×（2ⁿ+1）-1,D₀代表位置i从D_L移出之后D_L的剩余部分。于是，此条件概率的分布就是高斯型的：

数学地质和地质信息

式中：

；γ是模型的变异函数，γ_i是一个大小为1×（N₀+1）的向量，其第j个分量为－γ_｜i-j｜，当j∈D₀时，向量的第（N₀+1）个分量为1；

是一个大小为（N₀+1）×（N₀+1）的矩阵，其元素为－γ_｜k-l｜,k,l∈D₀，除了（N₀+1）×（N₀+1）位置处的元素为0外，最后一行和最后一列元素为1；Z^＊是一个大小为1×（N₀+1）的向量，其分量为Z_j；j∈D₀，最后分量值为0。

渗透率、孔隙度和泥质含量的实现可通过序贯窗口层次算法获得，并可用它来作模拟辫状河道的输入。实际过程如下。

3辫状河道的条件模拟

根据研究区域的储层特征，用前面的三个地球物理参数来确定辫状河道的位置。当深度增加时，由于地球物理参数会变小，于是，为了确定河道，就应用深度来校准这些值。

令Per、Por、Sh和H分别代表渗透率、孔隙度、泥质含量和层深。可以用一个区分值PP来确定一个二维点是否属于一个河道：

数学地质和地质信息

式中：α₁、α₂、a₃是由地质经验确定的非原始系数，且依赖于深度H。若PP≥Q，则此位置属于一个河道；若PP＜Q，则此位置属于介于河道和泥岩之间的砂岩；若Per=0，则此位置属于泥岩。在这里，值Q是一个由地质经验确定的值，且也依赖于深度H。

基于公式（1），可以利用Por,Per,Sh的网格数据得到网格数据｛PP（i,j）；j=1，…，N_y；i=1，…，N_x）。N_x是x方向的网格节点数，N_y是y方向的网格节点数。PP值可作为模拟河道位置的输入，当要确定河道宽度时会再一次考虑它。

下面讨论模拟辫状河道位置的过程。第一，模拟每一河道的中心线；第二，通过加宽河道中心线来得到河道的边界。此过程可保证被模拟的河道以1的概率穿过所观察的井中河道。河道的连接和分支遵循地质经验。

3.1辫状河道位置的模拟

核心技术是辫状河道位置的模拟。首先，在研究区域里搜索每一河道的出发点，然后用随机游走模型来找出河道中心线。其结果是一系列的网格节点，在这些节点中，开始点就是第一节点。

在这里要考虑的主要因素有：①井的位置；②由井中数据（河道、泥岩及介于河道与泥岩之间的砂岩）所表示的相分布；③PP值。以这些为基础，可以确定所有可能的河道，同时也考虑了辫状河道的连接与分支。

首先，把在每一井中的有关的相信息分配到距井位置最近的一个网格节点。一个整数KG（i,j）可能会有下面几个可能的值：

数学地质和地质信息

3.2河道开始位置

令D_L是一个在研究区域的网格系统（图1），Δx和Δy包含若干个网格间距（在这里是5个），是两个窄带的相应宽度。从（i,j）开始，在沿着东西方向的一个窄带中，i从1到N_x，j从Ⅳ_j到N_y搜索。假如在KG（i₁,j₁）等于3的网格节点发现了第一个位置（i₁,j₁），并且在KG（i₂,j₂）等于2或1的网格节点获得下一位置（i₂,j₂），那么就可以认为i₁是第一个河道开始点的x坐标。

同理，从（i,j）点开始，在沿着南北方向的另一个窄带中，i从N，到N_x,j从1到N_y搜索。假如在KG（i₃,j₃）等于3处找到了第一个位置（i₃,j₃），这样就能够把j₃-N_j标记为一个河道开始位置的y坐标。

图1寻找河道初始位置

图2网格节点的转移

在研究区域内，全部可能河道的开始点可以根据前面的过程依次找到。

可以用二维随机游走模型来确定一个网格节点是否向a、b和c中的一个方向转移（见图2）。

3.3第一个河道的流动和分叉位置的条件模拟

设当前位置为Q（i,j），下一点的确定就依赖于a、b、c三方向之一。

（1）方向a

沿着方向a从位置Q（i,j）出发找到最近的观察位置（i_a,j），在这里，i_a表示相应的最近的位置。令Λ表示“找到一个位置（i,j+1），它满足KG（i,j+1）=3”。假如P〔Q（i,j）→Q（i+1,j）代表转移概率，则有

数学地质和地质信息

式中：DA=｜i_a-i｜×d_x

；D_x＝（N_x-1）×d_x；d_x表示x方向上两个相邻网格节点间的距离；maxPP是网格系统中PP值的最大值；α₁、α₂、α₃、α₄是由地质经验来确定的非负值，且0＜α_i＜1,i=1,2,3,4。

假如沿着方向a找到了下一点，就令KG（i+1,j）＝3，否则就考虑方向b。

（2）方向b

方向b是向左下方的，迁移概率为P〔Q（i,j）→Q（i+1,j+1）〕：

数学地质和地质信息

式中：

；d_x表示在x方向上两个相邻网格节点间的距离。D_y-（N_y－1）×d_y；d_y表示在y方向上两个相邻网格节点间的距离。β₁，β₂，β₃，β₄是由地质经验来确定的非负值，且0＜β_i＜1,i=1,2,3,4。

假如一个河道的实现正向方向b转移，也就是Q（i,j）→Q（i+1,j+1），则令KG（i+1，j+1）=3，否则就考虑方向c。

（3）方向c

如果转移方向既不是a也不是b，那一定是c，其通路就是从Q（i,j）到Q（i,j+1），同时，令KG（i,j+1）=3。

重复执行前面的过程直至KG（i,j）＝一1，这样就模拟出了第一个河道的位置。

3.4所有其他可能河道的模拟

为了模拟其他河道的位置，KG（i,j）的值就要作如下改变：

数学地质和地质信息

在下面几部分将会考虑河道的连接和分支。

（1）方向a

令位置Q（i,j）向方向a转移，直到找到第一个河道的位置是（ia,j）为止，并且A＝“从位置（i,j+1）向方向a找到一个位置（i,j+1），它满足KG（i,j+1）=3，并且i″满足i＜i″＜i′，KG（i″,j+1）＝1或KG（i″,j+1）=2″。P〔Q（i,j）→Q（i+1,j）表示转移概率，这样就有

P〔Q（i,j）→Q（i+1,j）〕＝

数学地质和地质信息

式中：D_A=|i_a一i|×d_x,D_x与d_x和前面一样有相同含义；maxPP是网格系统中PP值的最大值；γ₁，γ₂，γ₃，γ₄，γ₅，γ。是由地质经验来确定的非负值，且

0＜γ_i＜1,i=1,2,3,4,5,6；

γ₁＋γ₂≤1，γ₃＋γ₄≤1，γ₅＋γ₆≤1；

γ₁≥γ₃≥γ₅，γ₂≥γ₄≥γ₆。

显然，假如最近的搜索位置属于一个河道，则最近搜索距离就越小，转移概率就越大。因此，河道将以更大的概率相互连接。条件γ₁≥γ₃≥γ₅及γ₂≥γ₄≥γ₆可以表示这样的特征：在河道间观测到泥岩，则河道的分支机会就会增加。

假如河道轨迹是从Q（i,j）到Q（i+1,j），当位置Q（i+1,j）不是河道位置时就令KG（i+1,j）等于4，否则就令KG（i+1,j）等于5。如果河道轨迹不是从Q（i,j）到Q（i+1,j），就要考虑方向b。

（2）方向b

令位置Q（i,j）向左下方向转移直到找到标记为（i_a,j_b）的第一个位置。如果KG（i+1,j）＝1或＝2，并且Q（i,j）没有转移到Q（i+1,j+1），这样从Q（i,j）到Q（i+1,j+1）的转移概率就是

数学地质和地质信息

式中：

；D_x,D_y,d_x及d_y的含义同前面；δ₁，δ₂，δ₃，δ₄，δ₅，δ₆是由地质经验确定的非负参数，且

0＜δ_i＜1,i=1,2,3,4,5,6；

δ₁＋δ₂≤1，δ₃＋δ₄≤1；δ₅＋δ₆≤1；

δ₁≥δ₃≥δ₅，δ₂≥δ₄≥δ₆。

因为河道轨迹是从东北到西南方向伸展的，参数δ_i及γ_i必须满足下面的关系：

δ_i＞γ_i,i=1,2,3,4,5,6

如果河道轨迹是向着方向b的，也就是Q（i,j）→Q（i+1,j+1），那么就令

数学地质和地质信息

否则，就要考虑方向c。

（3）方向c

假如河道轨迹既不沿方向a也不沿方向b，那一定是沿方向c，也就是Q（i,j）→Q（i,j+1）。同时，必须用（2）式来修改KG（i,j+1）的值。

为了找到更多的分支河道，就重复执行前面的过程直到KG（i,j）=-1，此过程的循环参数依赖于研究区域的实际地质特征。总体看来，搜索到的分支河道数越多，河道的连接与分支就越频繁。在研究中，每一河道仅搜索一个分支河道。

3.5其他河道及其分支河道的模拟

可以用同样的方法来找到其他河道及其分支河道。

4河道边界的确定

每一河道的宽度依赖于PP值。PP值越大，河道就越宽。

4.1参数

假如河道轨迹是M→N→L，就应移去位置N。显然这种处理可以简化加宽河道这一过程，但它不会改变每一河道的轨迹（图3）。

图3加宽河道前的预处理

4.2河道边界的确定

河道宽度公式如下：

宽度＝Δ₁+PP（i,j）×Δ₂/maxPP

式中：Δ₁是研究区域中河道宽度最小值；Δ₂是河道宽度最大值；PP（i,j）是与河道相邻位置的最近的网格节点的PP值（图4）。

5案例研究

本案例研究区域为中国辽河油田的沈－84。

图4加宽河道

在这一区域，使用了100口井的数据，包括如渗透率、孔隙度和泥质含量这样的油藏物理参数信息，以及如河道、泥岩和介于河道与泥岩之间的砂岩这样的相信息。通过分数维布朗运动模型得到了三个地球物理参数的实现。

以这些地球物理参数的模拟为基础，通过随机游走模型可以产生相的实现（图5）。

图5辫状河道模拟的一个实现

该模型的参数通过如下方法来选择：

N_x=N_y=65；D_x=50m,D_y=30m；

α₁=0.2，α₂=0.3，α₃=0.1，α₄=0.2；

β₁=0.3，β₂=0.4，β₃=0.2，β₄=0.3；

γ₁=0.2，γ₂=0.3，γ₃=0.1，γ₄=0.2，γ₅=0.1，γ₆=0.2；

δ₁=0.3，δ₂=0.5，δ₃=0.3，δ₄=0.4，δ₅=0.2，δ₆=0.3，Δ₁=70m，Δ₂=50m。

6结论

在三角洲沉积环境中，由辫状河道控制的储层具有极大的非均质性，这是因为河道的宽度较窄且有频繁的连接与分支。描述辫状河道的二维分布是十分重要的。

在本文中，随机游走作为一种二维随机模拟方法，可用来描述辫状河道的分布。这些实现产生了一些重要的辫状河道的特征：频繁发生的河道连接与分支。同时，在模型中也考虑了河道的宽度，并且保留了河道连续性和平滑性。

致谢特别感谢辽河石油管理局地质科学院的郑容植和李焕鹏两位高级工程师的技术支持。

参考文献

[1]H.H.Haldorsen.A new approach to shale management in field scale simulation models.SPE（10976）,1984,447～457.

[2]G.Matheron,H.Beucher,C.de Fouqqet,A.Galli,D.Guerillout and C.Ravenne.Conditional simulation of the geometry of fluriodeltaic reservoirs.SPE 62nd Annual Conference Dallas,Texas,1987,591～599.

[3]Olivier Dubrule.A review of stochastic models for petroleum reservoirs.GEOSTATISTICS,1989,2:493～506.

㈥ 随机游走算法怎么体现随机

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

㈦ 股票价格的随机游走的含义

“随机游走”（random walk）是指基于过去的表现，无法预测将来的发展步骤和方向。应用到股市上，则意味着股票价格的短期走势不可预知，意味着投资咨询服务、收益预测和复杂的图表模型全无用处。在华尔街上，“随机游走”这个名词是个讳语，是学术界杜撰的一个粗词，是对专业预言者的一种侮辱攻击。若将这一术语的逻辑内涵推向极致，便意味着一只戴上眼罩的猴子，随意向报纸的金融版面掷一些飞镖，选出的投资组合就可与投资专家精心挑选出的一样出色。

㈧ 基于社区发现算法和图分析Neo4j解读《权力的游戏》下篇

其中的分析和可视化是用Gephi做的，Gephi是非常流行的图分析工具。但作者觉得使用Neo4j来实现更有趣。

节点中心度
节点中心度给出网络中节点的重要性的相对度量。有许多不同的方式来度量中心度，每种方式都代表不同类型的“重要性”。

度中心性(Degree Centrality)
度中心性是最简单度量，即为某个节点在网络中的联结数。在《权力的游戏》的图中，某个角色的度中心性是指该角色接触的其他角色数。作者使用Cypher计算度中心性：
MATCH (c:Character)-[:INTERACTS]- RETURN c.name AS character, count(*) AS degree ORDER BY degree DESC

character
degree

Tyrion
36

Jon
26

Sansa
26

Robb
25

Jaime
24

Tywin
22

Cersei
20

Arya
19

Joffrey
18

Robert
18

从上面可以发现，在《权力的游戏》网络中提利昂·兰尼斯特（Tyrion）和最多的角色有接触。鉴于他的心计，我们觉得这是有道理的。

加权度中心性（Weighted Degree Centrality）
作者存储一对角色接触的次数作为 INTERACTS 关系的 weight 属性。对该角色的 INTERACTS 关系的所有 weight 相加得到加权度中心性。作者使用Cypher计算所有角色的这个度量：
MATCH (c:Character)-[r:INTERACTS]- RETURN c.name AS character, sum(r.weight) AS weightedDegree ORDER BY weightedDegree DESC

character
weightedDegree

Tyrion
551

Jon
442

Sansa
383

Jaime
372

Bran
344

Robb
342

Samwell
282

Arya
269

Joffrey
255

Daenerys
232

介数中心性（Betweenness Centrality）
介数中心性：在网络中，一个节点的介数中心性是指其它两个节点的所有最短路径都经过这个节点，则这些所有最短路径数即为此节点的介数中心性。介数中心性是一种重要的度量，因为它可以鉴别出网络中的“信息中间人”或者网络聚类后的联结点。

图6中红色节点是具有高的介数中心性，网络聚类的联结点。
为了计算介数中心性，作者使用Neo4j 3.x或者apoc库。安装apoc后能用Cypher调用其170+的程序：
MATCH (c:Character) WITH collect(c) AS charactersCALL apoc.algo.betweenness(['INTERACTS'], characters, 'BOTH') YIELD node, scoreSET node.betweenness = scoreRETURN node.name AS name, score ORDER BY score DESC

name
score

Jon
1279.7533534055322

Robert
1165.6025171231624

Tyrion
1101.3849724234349

Daenerys
874.8372110508583

Robb
706.5572832464792

Sansa
705.1985623519137

Stannis
571.5247305125714

Jaime
556.1852522889822

Arya
443.01358430043337

Tywin
364.7212195528086

紧度中心性（Closeness centrality）
紧度中心性是指到网络中所有其他角色的平均距离的倒数。在图中，具有高紧度中心性的节点在聚类社区之间被高度联结，但在社区之外不一定是高度联结的。

图7 ：网络中具有高紧度中心性的节点被其它节点高度联结
MATCH (c:Character) WITH collect(c) AS charactersCALL apoc.algo.closeness(['INTERACTS'], characters, 'BOTH') YIELD node, scoreRETURN node.name AS name, score ORDER BY score DESC

name
score

Tyrion
0.004830917874396135

Sansa
0.004807692307692308

Robert
0.0047169811320754715

Robb
0.004608294930875576

Arya
0.0045871559633027525

Jaime
0.004524886877828055

Stannis
0.004524886877828055

Jon
0.004524886877828055

Tywin
0.004424778761061947

Eddard
0.004347826086956522

使用python-igraph
Neo4j与其它工具（比如，R和Python数据科学工具）完美结合。我们继续使用apoc运行 PageRank和社区发现（community detection）算法。这里接着使用python-igraph计算分析。Python-igraph移植自R的igraph图形分析库。 使用 pip install python-igraph 安装它。

从Neo4j构建一个igraph实例
为了在《权力的游戏》的数据的图分析中使用igraph，首先需要从Neo4j拉取数据，用Python建立igraph实例。作者使用 Neo4j 的Python驱动库py2neo。我们能直接传入Py2neo查询结果对象到igraph的 TupleList 构造器，创建igraph实例：
from py2neo import Graphfrom igraph import Graph as IGraph graph = Graph query = ''' MATCH (c1:Character)-[r:INTERACTS]->(c2:Character) RETURN c1.name, c2.name, r.weight AS weight '''ig = IGraph.TupleList(graph.run(query), weights=True)

现在有了igraph对象，可以运行igraph实现的各种图算法来。

PageRank
作者使用igraph运行的第一个算法是PageRank。PageRank算法源自Google的网页排名。它是一种特征向量中心性(eigenvector centrality)算法。
在igraph实例中运行PageRank算法，然后把结果写回Neo4j，在角色节点创建一个pagerank属性存储igraph计算的值：
pg = ig.pagerank pgvs = for p in zip(ig.vs, pg): print(p) pgvs.append({"name": p[0]["name"], "pg": p[1]}) pgvs write_clusters_query = ''' UNWIND {nodes} AS n MATCH (c:Character) WHERE c.name = n.name SET c.pagerank = n.pg '''graph.run(write_clusters_query, nodes=pgvs)

现在可以在Neo4j的图中查询最高PageRank值的节点：
MATCH (n:Character) RETURN n.name AS name, n.pagerank AS pagerank ORDER BY pagerank DESC LIMIT 10

name
pagerank

Tyrion
0.042884981999963316

Jon
0.03582869669163558

Robb
0.03017114665594764

Sansa
0.030009716660108578

Daenerys
0.02881425425830273

Jaime
0.028727587587471206

Tywin
0.02570016262642541

Robert
0.022292016521362864

Cersei
0.022287327589773507

Arya
0.022050209663844467

社区发现（Community detection）

图8
社区发现算法用来找出图中的社区聚类。作者使用igraph实现的随机游走算法（ walktrap）来找到在社区中频繁有接触的角色社区，在社区之外角色不怎么接触。
在igraph中运行随机游走的社区发现算法，然后把社区发现的结果导入Neo4j，其中每个角色所属的社区用一个整数来表示：
clusters = IGraph.community_walktrap(ig, weights="weight").as_clustering nodes = [{"name": node["name"]} for node in ig.vs]for node in nodes: idx = ig.vs.find(name=node["name"]).index node["community"] = clusters.membership[idx] write_clusters_query = ''' UNWIND {nodes} AS n MATCH (c:Character) WHERE c.name = n.name SET c.community = toInt(n.community) '''graph.run(write_clusters_query, nodes=nodes)

我们能在Neo4j中查询有多少个社区以及每个社区的成员数：
MATCH (c:Character) WITH c.community AS cluster, collect(c.name) AS members RETURN cluster, members ORDER BY cluster ASC

cluster
members

0
[Aemon, Alliser, Craster, Eddison, Gilly, Janos, Jon, Mance, Rattleshirt, Samwell, Val, Ygritte, Grenn, Karl, Bowen, Dalla, Orell, Qhorin, Styr]

1
[Aerys, Amory, Balon, Brienne, Bronn, Cersei, Gregor, Jaime, Joffrey, Jon Arryn, Kevan, Loras, Lysa, Meryn, Myrcella, Oberyn, Podrick, Renly, Robert, Robert Arryn, Sansa, Shae, Tommen, Tyrion, Tywin, Varys, Walton, Petyr, Elia, Ilyn, Pycelle, Qyburn, Margaery, Olenna, Marillion, Ellaria, Mace, Chataya, Doran]

2
[Arya, Beric, Eddard, Gendry, Sandor, Anguy, Thoros]

3
[Brynden, Catelyn, Edmure, Hoster, Lothar, Rickard, Robb, Roose, Walder, Jeyne, Roslin, Ramsay]

4
[Bran, Hodor, Jojen, Luwin, Meera, Rickon, Nan, Theon]

5
[Belwas, Daario, Daenerys, Irri, Jorah, Missandei, Rhaegar, Viserys, Barristan, Illyrio, Drogo, Aegon, Kraznys, Rakharo, Worm]

6
[Davos, Melisandre, Shireen, Stannis, Cressen, Salladhor]

7
[Lancel]

角色“大合影”
《权力的游戏》的权力图。节点的大小正比于介数中心性，颜色表示社区（由随机游走算法获得），边的厚度正比于两节点接触的次数。现在已经计算好这些图的分析数据，让我们对其进行可视化，让数据看起来更有意义。
Neo4j自带浏览器可以对Cypher查询的结果进行很好的可视化，但如果我们想把可视化好的图嵌入到其它应用中，可以使用Javascript可视化库Vis.js。从Neo4j拉取数据，用Vis.js的neovis.js构建可视化图。Neovis.js提供简单的API配置，例如：
var config = { container_id: "viz", server_url: "localhost", labels: { "Character": "name" }, label_size: { "Character": "betweenness" }, relationships: { "INTERACTS": }, relationship_thickness: { "INTERACTS": "weight" }, cluster_labels: { "Character": "community" } }; var viz = new NeoVis(config); viz.render;

其中：
节点带有标签Character，属性name；

节点的大小正比于betweenness属性；

可视化中包括INTERACTS关系；

关系的厚度正比于weight属性；

节点的颜色是根据网络中社区community属性决定；

从本地服务器localhost拉取Neo4j的数据；

在一个id为viz的DOM元素中展示可视化。

㈨ 推荐算法简介

写在最前面：本文内容主要来自于书籍《推荐系统实践》和《推荐系统与深度学习》。

推荐系统是目前互联网世界最常见的智能产品形式。从电子商务、音乐视频网站，到作为互联网经济支柱的在线广告和新颖的在线应用推荐，到处都有推荐系统的身影。推荐算法是推荐系统的核心，其本质是通过一定的方式将用户和物品联系起来，而不同的推荐系统利用了不同的方式。

推荐系统的主要功能是以个性化的方式帮助用户从极大的搜索空间中快速找到感兴趣的对象。因此，目前所用的推荐系统多为个性化推荐系统。个性化推荐的成功应用需要两个条件：

在推荐系统的众多算法中，基于协同的推荐和基于内容的推荐在实践中得到了最广泛的应用。本文也将从这两种算法开始，结合时间、地点上下文环境以及社交环境，对常见的推荐算法做一个简单的介绍。

基于内容的算法的本质是对物品内容进行分析，从中提取特征，然后基于用户对何种特征感兴趣来推荐含有用户感兴趣特征的物品。因此，基于内容的推荐算法有两个最基本的要求：

下面我们以一个简单的电影推荐来介绍基于内容的推荐算法。

现在有两个用户A、B和他们看过的电影以及打分情况如下：

其中问好（?）表示用户未看过。用户A对《银河护卫队 》《变形金刚》《星际迷航》三部科幻电影都有评分，平均分为 4 .7 分 （ (5+4+5 ) / 3=4.7 ）；对《三生三世》《美人鱼》《北京遇上西雅图》三部爱情电影评分平均分为 2.3 分 （ ( 3十2+2 ) /3=2.3 ）。现在需要给A推荐电影，很明显A更倾向于科幻电影，因此推荐系统会给A推荐独立日。而对于用户B，通过简单的计算我们可以知道更喜欢爱情电影，因此给其推荐《三生三世》。当然，在实际推荐系统中，预测打分比这更加复杂些，但是其原理是一样的。

现在，我们可以将基于内容的推荐归纳为以下四个步骤：

通过上面四步就能快速构建一个简单的推荐系统。基于内容的推荐系统通常简单有效，可解释性好，没有物品冷启动问题。但他也有两个明显的缺点：

最后，顺便提一下特征提取方法：对于某些特征较为明确的物品，一般可以直接对其打标签，如电影类别。而对于文本类别的特征，则主要是其主题情感等，则些可以通过tf-idf或LDA等方法得到。

基于协同的算法在很多地方也叫基于邻域的算法，主要可分为两种：基于用户的协同算法和基于物品的协同算法。

啤酒和尿布的故事在数据挖掘领域十分有名，该故事讲述了美国沃尔玛超市统计发现啤酒和尿布一起被购买的次数非常多，因此将啤酒和尿布摆在了一起，最后啤酒和尿布的销量双双增加了。这便是一个典型的物品协同过滤的例子。

基于物品的协同过滤指基于物品的行为相似度（如啤酒尿布被同时购买）来进行物品推荐。该算法认为，物品A和物品B具有很大相似度是因为喜欢物品A的用户大都也喜欢物品B。

基于物品的协同过滤算法主要分为两步：

基于物品的协同过滤算法中计算物品相似度的方法有以下几种：
（1）基于共同喜欢物品的用户列表计算。

此外，John S. Breese再其论文中还提及了IUF（Inverse User Frequence，逆用户活跃度）的参数，其认为活跃用户对物品相似度的贡献应该小于不活跃的用户，应该增加IUF参数来修正物品相似度的公式：

上面的公式只是对活跃用户做了一种软性的惩罚， 但对于很多过于活跃的用户， 比如某位买了当当网80%图书的用户， 为了避免相似度矩阵过于稠密， 我们在实际计算中一般直接忽略他的兴趣列表， 而不将其纳入到相似度计算的数据集中。

（2）基于余弦相似度计算。

（3）热门物品的惩罚。
从上面（1）的相似度计算公式中，我们可以发现当物品 i 被更多人购买时，分子中的 N(i) ∩ N(j) 和分母中的 N(i) 都会增长。对于热门物品，分子 N(i) ∩ N(j) 的增长速度往往高于 N(i)，这就会使得物品 i 和很多其他的物品相似度都偏高，这就是 ItemCF 中的物品热门问题。推荐结果过于热门，会使得个性化感知下降。以歌曲相似度为例，大部分用户都会收藏《小苹果》这些热门歌曲，从而导致《小苹果》出现在很多的相似歌曲中。为了解决这个问题，我们对于物品 i 进行惩罚，例如下式， 当α∈(0, 0.5) 时，N(i) 越小，惩罚得越厉害，从而使热门物品相关性分数下降（ 博主注：这部分未充分理解 ）：

此外，Kary pis在研究中发现如果将ItemCF的相似度矩阵按最大值归一化， 可以提高推荐的准确率。 其研究表明， 如果已经得到了物品相似度矩阵w， 那么可以用如下公式得到归一化之后的相似度矩阵w'：

归一化的好处不仅仅在于增加推荐的准确度，它还可以提高推荐的覆盖率和多样性。一般来说，物品总是属于很多不同的类，每一类中的物品联系比较紧密。假设物品分为两类——A和B， A类物品之间的相似度为0.5， B类物品之间的相似度为0.6， 而A类物品和B类物品之间的相似度是0.2。 在这种情况下， 如果一个用户喜欢了5个A类物品和5个B类物品， 用ItemCF给他进行推荐， 推荐的就都是B类物品， 因为B类物品之间的相似度大。 但如果归一化之后， A类物品之间的相似度变成了1， B类物品之间的相似度也是1， 那么这种情况下， 用户如果喜欢5个A类物品和5个B类物品， 那么他的推荐列表中A类物品和B类物品的数目也应该是大致相等的。 从这个例子可以看出， 相似度的归一化可以提高推荐的多样性。

那么，对于两个不同的类，什么样的类其类内物品之间的相似度高，什么样的类其类内物品相似度低呢？一般来说，热门的类其类内物品相似度一般比较大。如果不进行归一化，就会推荐比较热门的类里面的物品，而这些物品也是比较热门的。因此，推荐的覆盖率就比较低。相反，如果进行相似度的归一化，则可以提高推荐系统的覆盖率。

最后，利用物品相似度矩阵和用户打过分的物品记录就可以对一个用户进行推荐评分：

基于用户的协同算法与基于物品的协同算法原理类似，只不过基于物品的协同是用户U购买了A物品，会计算经常有哪些物品与A一起购买（也即相似度），然后推荐给用户U这些与A相似的物品。而基于用户的协同则是先计算用户的相似性（通过计算这些用户购买过的相同的物品），然后将这些相似用户购买过的物品推荐给用户U。

基于用户的协同过滤算法主要包括两个步骤：

步骤（1）的关键是计算用户的兴趣相似度，主要是利用用户的行为相似度计算用户相似度。给定用户 u 和 v，N(u) 表示用户u曾经有过正反馈（譬如购买）的物品集合，N(v) 表示用户 v 曾经有过正反馈的物品集合。那么我们可以通过如下的 Jaccard 公式简单的计算 u 和 v 的相似度：

或通过余弦相似度：

得到用户之间的相似度之后，UserCF算法会给用户推荐和他兴趣最相似的K个用户喜欢的物品。如下的公式度量了UserCF算法中用户 u 对物品 i 的感兴趣程度：

首先回顾一下UserCF算法和ItemCF算法的推荐原理：UserCF给用户推荐那些和他有共同兴趣爱好的用户喜欢的物品， 而ItemCF给用户推荐那些和他之前喜欢的物品具有类似行为的物品。

（1）从推荐场景考虑
首先从场景来看，如果用户数量远远超过物品数量，如购物网站淘宝，那么可以考虑ItemCF，因为维护一个非常大的用户关系网是不容易的。其次，物品数据一般较为稳定，因此物品相似度矩阵不必频繁更新，维护代价较小。

UserCF的推荐结果着重于反应和用户兴趣相似的小群体的热点，而ItemCF的推荐结果着重于维系用户的历史兴趣。换句话说，UserCF的推荐更社会化，反应了用户所在小型兴趣群体中物品的热门程度，而ItemCF的推荐更加个性化，反应了用户自己的个性传承。因此UserCF更适合新闻、微博或微内容的推荐，而且新闻内容更新频率非常高，想要维护这样一个非常大而且更新频繁的表无疑是非常难的。

在新闻类网站中，用户的兴趣爱好往往比较粗粒度，很少会有用户说只看某个话题的新闻，而且往往某个话题也不是每天都会有新闻。 个性化新闻推荐更强调新闻热点，热门程度和时效性是个性化新闻推荐的重点，个性化是补充，所以 UserCF 给用户推荐和他有相同兴趣爱好的人关注的新闻，这样在保证了热点和时效性的同时，兼顾了个性化。

（2）从系统多样性（也称覆盖率，指一个推荐系统能否给用户提供多种选择）方面来看，ItemCF的多样性要远远好于UserCF，因为UserCF更倾向于推荐热门物品。而ItemCF具有较好的新颖性，能够发现长尾物品。所以大多数情况下，ItemCF在精度上较小于UserCF，但其在覆盖率和新颖性上面却比UserCF要好很多。

在介绍本节基于矩阵分解的隐语义模型之前，让我们先来回顾一下传统的矩阵分解方法SVD在推荐系统的应用吧。

基于SVD矩阵分解在推荐中的应用可分为如下几步：

SVD在计算前会先把评分矩阵 A 缺失值补全，补全之后稀疏矩阵 A 表示成稠密矩阵，然后将分解成 A' = U∑V T 。但是这种方法有两个缺点：（1）补成稠密矩阵后需要耗费巨大的储存空间，对这样巨大的稠密矩阵进行储存是不现实的；（2）SVD的计算复杂度很高，对这样大的稠密矩阵中进行计算式不现实的。因此，隐语义模型就被发明了出来。

更详细的SVD在推荐系统的应用可参考 奇异值分解SVD简介及其在推荐系统中的简单应用 。

隐语义模型（Latent Factor Model）最早在文本挖掘领域被提出，用于找到文本的隐含语义。相关的算法有LSI，pLSA，LDA和Topic Model。本节将对隐语义模型在Top-N推荐中的应用进行详细介绍，并通过实际的数据评测该模型。

隐语义模型的核心思想是通过隐含特征联系用户兴趣和物品。让我们通过一个例子来理解一下这个模型。

现有两个用户，用户A的兴趣涉及侦探小说、科普图书以及一些计算机技术书，而用户B的兴趣比较集中在数学和机器学习方面。那么如何给A和B推荐图书呢？

我们可以对书和物品的兴趣进行分类。对于某个用户，首先得到他的兴趣分类，然后从分类中挑选他可能喜欢的物品。简言之，这个基于兴趣分类的方法大概需要解决3个问题：

对于第一个问题的简单解决方案是找相关专业人员给物品分类。以图书为例，每本书出版时，编辑都会给出一个分类。但是，即使有很系统的分类体系，编辑给出的分类仍然具有以下缺点：（1）编辑的意见不能代表各种用户的意见；（2）编辑很难控制分类的细粒度；（3）编辑很难给一个物品多个分类；（4）编辑很难给一个物品多个分类；（5）编辑很难给出多个维度的分类；（6）编辑很难决定一个物品在某一个类别中的权重。

为了解决上述问题，研究员提出可以从数据出发，自动找到那些分类，然后进行个性化推荐。隐语义模型由于采用基于用户行为统计的自动聚类，较好地解决了上面提出的5个问题。

LFM将矩阵分解成2个而不是3个：

推荐系统中用户和物品的交互数据分为显性反馈和隐性反馈数据。隐式模型中多了一个置信参数，具体涉及到ALS（交替最小二乘法，Alternating Least Squares）中对于隐式反馈模型的处理方式——有的文章称为“加权的正则化矩阵分解”：

一个小细节：在隐性反馈数据集中，只有正样本（正反馈）没有负反馈（负样本），因此如何给用户生成负样本来进行训练是一个重要的问题。Rong Pan在其文章中对此进行了探讨，对比了如下几种方法：

用户行为很容易用二分图表示，因此很多图算法都可以应用到推荐系统中。基于图的模型（graph-based model）是推荐系统中的重要内容。很多研究人员把基于领域的模型也称为基于图的模型，因为可以把基于领域的模型看作基于图的模型的简单形式。

在研究基于图的模型之前，需要将用户行为数据表示成图的形式。本节的数据是由一系列用户物品二元组 (u, i) 组成的，其中 u 表示用户对物品 i 产生过行为。

令 G(V, E) 表示用户物品二分图，其中 V=V U UV I 由用户顶点 V U 和物品节点 V I 组成。对于数据集中每一个二元组 (u, i) ，图中都有一套对应的边 e(v u , v i )，其中 v u ∈V U 是用户对应的顶点，v i ∈V I 是物品i对应的顶点。如下图是一个简单的物品二分图，其中圆形节点代表用户，方形节点代表物品，用户物品的直接连线代表用户对物品产生过行为。比如下图中的用户A对物品a、b、d产生过行为。

度量图中两个顶点之间相关性的方法很多，但一般来说图中顶点的相关性主要取决于下面3个因素：

而相关性高的一对顶点一般具有如下特征：

举个例子，如下图，用户A和物品c、e没有边直连，但A可通过一条长度为3的路径到达c，而Ae之间有两条长度为3的路径。那么A和e的相关性要高于顶点A和c，因而物品e在用户A的推荐列表中应该排在物品c之前，因为Ae之间有两条路径。其中，（A,b,C,e）路径经过的顶点的出度为（3，2，2，2），而 (A,d,D,e) 路径经过了一个出度比较大的顶点D，所以 (A,d,D,e) 对顶点A与e之间相关性的贡献要小于（A,b,C,e）。

基于上面3个主要因素，研究人员设计了很多计算图中顶点相关性的方法，本节将介绍一种基于随机游走的PersonalRank算法。

假设要给用户u进行个性化推荐，可以从用户u对应的节点 v u 开始在用户物品二分图上进行随机游走。游走到任一节点时，首先按照概率α决定是继续游走还是停止这次游走并从 v u 节点重新开始游走。若决定继续游走，则从当前节点指向的节点中按照均匀分布随机选择一个节点作为游走下次经过的节点。这样，经过很多次随机游走后，每个物品被访问到的概率会收敛到一个数。最终的推荐列表中物品的权重就是物品节点的访问概率。

上述算法可以表示成下面的公式：

虽然通过随机游走可以很好地在理论上解释PersonalRank算法，但是该算法在时间复杂度上有明显的缺点。因为在为每个用户进行推荐时，都需要在整个用户物品二分图上进行迭代，知道所有顶点的PR值都收敛。这一过程的时间复杂度非常高，不仅无法在线进行实时推荐，离线计算也是非常耗时的。

有两种方法可以解决上面PersonalRank时间复杂度高的问题：
（1）减少迭代次数，在收敛之前停止迭代。但是这样会影响最终的精度。

（2）从矩阵论出发，重新涉及算法。另M为用户物品二分图的转移概率矩阵，即：

网络社交是当今社会非常重要甚至可以说是必不可少的社交方式，用户在互联网上的时间有相当大的一部分都用在了社交网络上。

当前国外最着名的社交网站是Facebook和Twitter，国内的代表则是微信/QQ和微博。这些社交网站可以分为两类：

需要指出的是，任何一个社交网站都不是单纯的社交图谱或兴趣图谱。如QQ上有些兴趣爱好群可以认识不同的陌生人，而微博中的好友也可以是现实中认识的。

社交网络定义了用户之间的联系，因此可以用图定义社交网络。我们用图 G(V,E,w) 定义一个社交网络，其中V是顶点集合，每个顶点代表一个用户，E是边集合，如果用户va和vb有社交网络关系，那么就有一条边 e(v a , v b ) 连接这两个用户，而 w(v a , v b )定义了边的权重。一般来说，有三种不同的社交网络数据：

和一般购物网站中的用户活跃度分布和物品流行度分布类似，社交网络中用户的入度（in degree，表示有多少人关注）和出度（out degree，表示关注多少人）的分布也是满足长尾分布的。即大部分人关注的人都很少，被关注很多的人也很少。

给定一个社交网络和一份用户行为数据集。其中社交网络定义了用户之间的好友关系，而用户行为数据集定义了不同用户的历史行为和兴趣数据。那么最简单的算法就是给用户推荐好友喜欢的物品集合。即用户u对物品i的兴趣 p ui 可以通过如下公式计算。

用户u和用户v的熟悉程度描述了用户u和用户在现实社会中的熟悉程度。一般来说，用户更加相信自己熟悉的好友的推荐，因此我们需要考虑用户之间的熟悉度。下面介绍3中衡量用户熟悉程度的方法。

（1）对于用户u和用户v，可以使用共同好友比例来计算他们的相似度：

上式中 out(u) 可以理解为用户u关注的用户合集，因此 out(u) ∩ out(v) 定义了用户u、v共同关注的用户集合。

（2）使用被关注的用户数量来计算用户之间的相似度，只要将公式中的 out(u) 修改为 in(u)：

in(u) 是指关注用户u的集合。在无向社交网络中，in(u)和out(u)是相同的，而在微博这种有向社交网络中，这两个集合的含义就不痛了。一般来说，本方法适合用来计算微博大V之间的相似度，因为大v往往被关注的人数比较多；而方法（1）适用于计算普通用户之间的相似度，因为普通用户往往关注行为比较丰富。

（3）除此之外，还可以定义第三种有向的相似度：这个相似度的含义是用户u关注的用户中，有多大比例也关注了用户v：

这个相似度有一个缺点，就是在该相似度下所有人都和大v有很大的相似度，这是因为公式中的分母并没有考虑 in(v) 的大小，所以可以把 in(v) 加入到上面公式的分母，来降低大v与其他用户的相似度：

上面介绍了3种计算用户之间相似度（或称熟悉度）的计算方法。除了熟悉程度，还需要考虑用户之间的兴趣相似度。我们和父母很熟悉，但很多时候我们和父母的兴趣确不相似，因此也不会喜欢他们喜欢的物品。因此，在度量用户相似度时，还需要考虑兴趣相似度，而兴趣相似度可以通过和UserCF类似的方法度量，即如果两个用户喜欢的物品集合重合度很高，两个用户的兴趣相似度很高。

最后，我们可以通过加权的形式将两种权重合并起来，便得到了各个好有用户的权重了。

有了权重，我们便可以针对用户u挑选k个最相似的用户，把他们购买过的物品中，u未购买过的物品推荐给用户u即可。打分公式如下：

其中 w' 是合并后的权重，score是用户v对物品的打分。

node2vec的整体思路分为两个步骤：第一个步骤是随机游走（random walk），即通过一定规则随机抽取一些点的序列；第二个步骤是将点的序列输入至word2vec模型从而得到每个点的embedding向量。

随机游走在前面基于图的模型中已经介绍过，其主要分为两步：（1）选择起始节点；（2）选择下一节点。起始节点选择有两种方法：按一定规则抽取一定量的节点或者以图中所有节点作为起始节点。一般来说会选择后一种方法以保证所有节点都会被选取到。

在选择下一节点方法上，最简单的是按边的权重来选择，但在实际应用中需要通过广度优先还是深度优先的方法来控制游走范围。一般来说，深度优先发现能力更强，广度优先更能使社区内（较相似）的节点出现在一个路径里。

斯坦福大学Jure Leskovec教授给出了一种可以控制广度优先或者深度优先的方法。

以上图为例，假设第一步是从t随机游走到v，这时候我们要确定下一步的邻接节点。本例中，作者定义了p和q两个参数变量来调节游走，首先计算其邻居节点与上一节点t的距离d，根据下面的公式得到α：

一般从每个节点开始游走5~10次，步长则根据点的数量N游走根号N步。如此便可通过random walk生成点的序列样本。

得到序列之后，便可以通过word2vec的方式训练得到各个用户的特征向量，通过余弦相似度便可以计算各个用户的相似度了。有了相似度，便可以使用基于用户的推荐算法了。

推荐系统需要根据用户的历史行为和兴趣预测用户未来的行为和兴趣，因此大量的用户行为数据就成为推荐系统的重要组成部分和先决条件。如何在没有大量用户数据的情况下设计个性化推荐系统并且让用户对推荐结果满意从而愿意使用推荐系统，就是冷启动问题。

冷启动问题主要分为三类：

针对用户冷启动，下面给出一些简要的方案：
（1）有效利用账户信息。利用用户注册时提供的年龄、性别等数据做粗粒度的个性化；
（2）利用用户的社交网络账号登录（需要用户授权），导入用户在社交网站上的好友信息，然后给用户推荐其好友喜欢的物品；
（3）要求用户在登录时对一些物品进行反馈，手机用户对这些物品的兴趣信息，然后给用推荐那些和这些物品相似的物品；
（4）提供非个性化推荐。非个性化推荐的最简单例子就是热门排行榜，我们可以给用户推荐热门排行榜，然后等到用户数据收集到一定的时候，在切换为个性化推荐。

对于物品冷启动，可以利用新加入物品的内容信息，将它们推荐给喜欢过和他们相似的物品的用户。

对于系统冷启动，可以引入专家知识，通过一定高效的方式快速建立起物品的相关度表。

在上面介绍了一些推荐系统的基础算法知识，这些算法大都是比较经典且现在还在使用的。但是需要注意的是，在实践中，任何一种推荐算法都不是单独使用的，而是将多种推荐算法结合起来，也就是混合推荐系统，但是在这里并不准备介绍，感兴趣的可以查阅《推荐系统》或《推荐系统与深度学习》等书籍。此外，在推荐中非常重要的点击率模型以及基于矩阵的一些排序算法在这里并没有提及，感兴趣的也可自行学习。

虽然现在用的很多算法都是基于深度学习的，但是这些经典算法能够让我们对推荐系统的发展有一个比较好的理解，同时，更重要的一点——“推陈出新”，只有掌握了这些经典的算法，才能提出或理解现在的一些更好地算法。

㈩ 优化算法笔记（二十五）飞蛾扑火算法

（以下描述，均不是学术用语，仅供大家快乐的阅读）
飞蛾扑火算法（Moth-Flame Optimization）是受飞蛾围绕火焰飞行启发而提出的算法。算法提出于2015年5月（投稿日期），虽可算作一个新算法，不过无数研究者就像飞蛾见了火一样，发表了如此之多的论文，惊了。
飞蛾扑火算法中有两种个体，飞蛾和火焰，飞蛾选择并围绕火焰以螺线方式飞行搜索，搜索完后，火焰将移动位置，以保持火焰是飞蛾和火焰群体中最优的位置。
算法的流程简单，螺线搜索在之前的鲸鱼算法中也出现过，这里会较为详细的记录记录螺线搜索的具体情况。

显然,飞蛾扑火算法中有两种角色,飞蛾与火焰。初始时飞蛾与火焰的数量均为N。为了方便查看，将飞蛾的位置表示为XM ，火焰的位置为 XF。
初始化时，会在解空间内初始化N个飞蛾与M(M=N)个火焰。在算法过程中，飞蛾将会围绕它所选择的火焰飞行，之后将这N个飞蛾与M个火焰按优劣排序，并将M个火焰移动到较优的前M个个体的位置。其中火焰的数量M会随着迭代次数的改变而不断变化，论文中阶梯递减至1。
算法的主要步骤如下：
1. 飞蛾选择火焰（将火焰分配给飞蛾）。
2. 飞蛾围绕火焰飞行。
3. 移动火焰到相应位置。
从步骤可以看出，算法中飞蛾的飞行是一种无贪心算法的操作，而火焰的移动则是一种变相的贪心操作。

初始化时，会有N个飞蛾和N个火焰（M=N）,故每只飞蛾都可以选择互不相同的火焰。随着迭代次数的递增，火焰的数量会递减。其数量根据以下公式计算得出：

其图像如下图所示：

其实就是将火焰数量M线性递减到1，由于火焰数量是正数，故图像呈阶梯状。
随着迭代次数增加，火焰数量递减，每只飞蛾无法选择互不相同的火焰，此时可以随机选择火焰或者飞蛾群体按顺序依次往后选取，类似于取模。两种方式的差别不大。

该步骤是算法的核心计算步骤。
对于飞蛾 ,它围绕火焰 飞行后到达的新位置XM_new根据以下公式计算得出：

其图像如下

而算法中的飞行轨迹应该是这样的：

取出一维看看

其中i为计算次数。

图像就是cos函数图像的变形。考虑到飞蛾与火焰之间的距离会越来越短，其飞行图像应该与上图相反，即振幅越来越小，局部搜索能力越来越强。

N只飞蛾围绕M个火焰飞行后，会到N个新位置，计算这N个新位置的适应度值，将这N个新位置与M个火焰这（N+M）个位置按优劣排序，并将其中较优的M个位置作为下一轮中火焰的位置。

其飞蛾扑火算法流程图如下：

由于飞蛾扑火算法可以说是对蚁狮算法和鲸鱼算法的结合，这里就看看算法的图像，不再做其他处理了。
适应度函数 。

实验一：

从结果看来，飞蛾扑火算法的性能稳定也优于蚁狮算法，从图像看算法收敛性不如蚁狮算法但局部搜索性能要强于蚁狮算法。
可见螺线的局部搜索能力还是强于随机游走的，不过其全局搜索要弱于随机游走。相比蚁狮算法，飞蛾扑火算法更容易陷入局部最优（其实与蚁狮差不多，只要火焰/蚁狮陷入局部最优基本完蛋，不过蚁狮数量恒定，火焰数量递减，所有火焰更容易局部最优）。

飞蛾扑火算法是根据飞蛾围绕火焰飞行的行为而提出的算法。算法的结构比较简单，与蚁狮算法类似，只是搜索步骤将随机游走替换成了螺线搜索（当然还有跟多细节上的不同，可以看看原文）。算法的局部搜索能力非常强，依靠螺线就提供了全局搜索和局部搜索能力，其全局搜索和局部搜索能力强弱由其极半径决定，算法中由b决定。不过算法缺少跳出局部最优的能力，在平滑函数中的效果非常好，在局部最优较多的函数中效果中规中矩。

参考文献
Mirjalili S . Moth-flame optimization algorithm: A novel nature-inspired heuristic paradigm[J]. Knowledge-Based Systems, 2015, 89(NOV.):228-249.. 提取码：koy9
以下指标纯属个人yy,仅供参考

目录
上一篇 优化算法笔记（二十四）帝王蝶算法
下一篇 优化算法笔记（二十六）和声搜索算法