精华内容
下载资源
问答
  • 记住咯: 最小点覆盖 = 二分图最大匹配 最小路径覆盖 = |P| - 二分图最大匹配 版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com 特别注意:本站所有转载文章言论不代表本站观点!...

    const int INF = 0x3f3f3f3f;

    const int MAXN=510;

    int uN,vN;//u,v数目

    int g[MAXN][MAXN];//构图

    int link[MAXN]; //link[v]=u表示右边对左边的匹配

    bool used[MAXN];//是否访问过

    bool dfs(int u)//从左边开始找增广路径

    {

    int v;

    for(v=0;v

    {

    if(g[u][v]&&!used[v]) //如果存在通路,且从u开始搜索时该点没访问过

    {

    used[v]=true;

    if(link[v]==-1 || dfs(link[v])) //找增广路

    {

    link[v]=u;

    return true;

    }

    }

    }

    return false;

    }

    int hungary()

    {

    int res=0;

    int i,u;

    memset(link,-1,sizeof(link));

    for(u=0;u

    {

    memset(used,0,sizeof(used));

    if(dfs(u))

    res++;

    }

    return res;

    }

    以上是匈牙利算法的关键代码

    其实实现就是一个找增广路径的过程

    增广路径 字面意思就是把路径越增越广

    实际意思也是一样的

    DFS从左边起始点开始搜索

    1.右边如果没匹配就匹配(link[v]==-1)

    2.如果右边匹配过了...就从右边点找左边的匹配点再搜索看是否能增广

    以上两种情况都能使匹配边+1

    这就是找二分图最大匹配的最简单算法了,代码很短,时间复杂度为O(n^3),网络流当然也能实现咯...

    记住咯:

    最小点覆盖 = 二分图最大匹配

    最小路径覆盖 = |P| - 二分图最大匹配

    版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com

    特别注意:本站所有转载文章言论不代表本站观点!

    本站所提供的图片等素材,版权归原作者所有,如需使用,请与原作者联系。

    展开全文
  • 文章目录一、理论基础1、WSN节点覆盖模型2、基本鲸鱼算法3、改进鲸鱼优化算法(1)量子位Bloch球面初始化(2)改进搜索猎物过程(3)莱维飞行扰动策略二、算法流程三、仿真实验与分析1、实验环境2、实验结果(1)与...

    一、理论基础

    1、WSN节点覆盖模型

    假设WSN监测区域是个二维平面,且数字化为 L × M L×M L×M的网格,每个网格大小设为1。在该区域部署 N N N个同构传感器,节点集合可以表示为 Z = { z 1 , z 2 , ⋯   , z N } Z=\{z_1,z_2,\cdots,z_N\} Z={z1,z2,,zN},都具有相同的感知半径 R s R_s Rs和通信半径 R c R_c Rc R s ≤ 2 R c R_s≤2R_c Rs2Rc。文采用布尔模型(0/1模型)作为节点感知模型,只要目标处于节点感知范围内,即可成功的被感知。假设在被监测区域的某个节点 z i z_i zi的坐标为 ( x i , y i ) (x_i,y_i) (xi,yi),目标点的位置 T j T_j Tj坐标为 ( x j , y j ) (x_j,y_j) (xj,yj),则节点与目标点的距离为: d ( z i , T j ) = ( x i − x j ) 2 + ( y i − y j ) 2 (1) d(z_i,T_j)=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}\tag{1} d(zi,Tj)=(xixj)2+(yiyj)2 (1) p ( z i , T j ) p(z_i,T_j) p(zi,Tj)表示节点 z i z_i zi T j T_j Tj的感知质量,当 T j T_j Tj的位置在节点 z i z_i zi的感知范围内时,则感知质量为1;否则节点 z i z_i zi T j T_j Tj的感知质量为0,数学表达式为: p ( z i , T j ) = { 1 i f   d ( z i , T j ) ≤ R s 0 o t h e r w i s e (2) p(z_i,T_j)=\begin{dcases}1\quad if\, d(z_i,T_j)≤R_s\\0\quad otherwise\end{dcases}\tag{2} p(zi,Tj)={1ifd(zi,Tj)Rs0otherwise(2)通常,传感器对目标的感知概率小于1,为了提高对目标的感知概率,需要多个传感器协同探测,则WSN对某一目标的感知概率为: p ( Z , T j ) = 1 − ∏ i = 1 N [ 1 − p ( z i , T j ) ] (3) p(Z,T_j)=1-\prod_{i=1}^N[1-p(z_i,T_j)]\tag{3} p(Z,Tj)=1i=1N[1p(zi,Tj)](3)该监测区的覆盖率是所有传感器节点覆盖的目标点数与该区域总的目标点数的比值,定义为: R c o v = ∑ j = 1 L × M p ( Z , T j ) L × M (4) R_{cov}=\frac{\displaystyle\sum_{j=1}^{L×M}p(Z,T_j)}{L×M}\tag{4} Rcov=L×Mj=1L×Mp(Z,Tj)(4)将式(4)作为目标函数,用改进的鲸鱼算法求得 R c o v R_{cov} Rcov的最优值以提高WSN的覆盖质量。

    2、基本鲸鱼算法

    请参考这里

    3、改进鲸鱼优化算法

    (1)量子位Bloch球面初始化

    将量子位的3个坐标看作3个并列的解,即每个鲸鱼个体包含对应优化问题的三个解,分别为 x x x解、 y y y解和 z z z解: { p i , x = ( c o s φ i 1 s i n θ i 1 , ⋯   , c o s φ i n s i n θ i n ) p i , y = ( s i n φ i 1 s i n θ i 1 , ⋯   , s i n φ i n s i n θ i n ) p i , z = ( c o s θ i 1 , ⋯   , c o s θ i n ) (5) \begin{dcases}p_{i,x}=(cos\varphi_{i1}sin\theta_{i1},\cdots,cos\varphi_{in}sin\theta_{in})\\p_{i,y}=(sin\varphi_{i1}sin\theta_{i1},\cdots,sin\varphi_{in}sin\theta_{in})\\p_{i,z}=(cos\theta_{i1},\cdots,cos\theta_{in})\end{dcases}\tag{5} pi,x=(cosφi1sinθi1,,cosφinsinθin)pi,y=(sinφi1sinθi1,,sinφinsinθin)pi,z=(cosθi1,,cosθin)(5)在IWOA中,1个量子位包含3个Bloch坐标,每个坐标对应一个优化解。由于Bloch坐标下每一维的范围是 [ − 1 , 1 ] [-1,1] [1,1],为解决连续优化问题,需要进行解空间变化,即将每个鲸鱼对应的三个Bloch坐标由单位空间映射到优化问题解空间。记鲸鱼 P i P_i Pi上第 j j j个量子位的Bloch坐标为 [ x i j , y i j , z i j ] T [x_{ij},y_{ij},z_{ij}]^T [xij,yij,zij]T,则对应解空间变量为: { X i x j = 0.5 [ b j ( 1 + x i j ) + a j ( 1 − x i j ) ] X i y j = 0.5 [ b j ( 1 + y i j ) + a j ( 1 − y i j ) ] X i z j = 0.5 [ b j ( 1 + z i j ) + a j ( 1 − z i j ) ] (6) \begin{dcases}X_{ix}^j=0.5[b_j(1+x_{ij})+a_j(1-x_{ij})]\\X_{iy}^j=0.5[b_j(1+y_{ij})+a_j(1-y_{ij})]\\X_{iz}^j=0.5[b_j(1+z_{ij})+a_j(1-z_{ij})]\end{dcases}\tag{6} Xixj=0.5[bj(1+xij)+aj(1xij)]Xiyj=0.5[bj(1+yij)+aj(1yij)]Xizj=0.5[bj(1+zij)+aj(1zij)](6)式中, i = 1 , 2 , ⋯   , m , j = 1 , 2 , ⋯   , n i=1,2,\cdots,m,j=1,2,\cdots,n i=1,2,,m,j=1,2,,n [ a j , b j ] [a_j,b_j] [aj,bj]为第 j j j个量子位的取值范围。
    每个鲸鱼对应Bloch坐标中的3个可行解,这种初始化方式能改善初始鲸鱼群的多样性,进而改善初始种群的质量,提高算法的全局优化能力。

    (2)改进搜索猎物过程

    本文引入了一个新的参数 U U U,它将自适应地改变步长,平衡全局搜索和局部搜索能力,将其应用于位置更新公式中, U U U的公式为: U = e 10 k (7) U=e^{10k}\tag{7} U=e10k(7) k = ( r a n d − 0.5 ) ( 1 − t / M a x i t e r ) (8) k=(rand-0.5)(1-t/Max_{iter})\tag{8} k=(rand0.5)(1t/Maxiter)(8)式中, r a n d rand rand [ 0 , 1 ] [0,1] [0,1]之间的随机数, t t t为当前迭代次数, M a x i t e r Max_{iter} Maxiter为最大迭代次数。新的位置更新公式为: D ′ = ∣ X r ( t ) − X ( t ) ∣ (9) D'=|\boldsymbol X_r(t)-\boldsymbol X(t)|\tag{9} D=Xr(t)X(t)(9) X ( t + 1 ) = X ( t ) − U s i g n ( a ) D ′ (10) \boldsymbol X(t+1)=\boldsymbol X(t)-Usign(a)D'\tag{10} X(t+1)=X(t)Usign(a)D(10)式中, s i g n ( ⋅ ) sign(\cdot) sign()为符号函数,取值为 − 1 , 0 , 1 -1,0,1 1,0,1
    随着迭代次数的增加, U U U整体呈减小趋势。但是与原始WOA中的 A A A相比较, U U U既有较大步长,又有小步长,可以帮助IWOA较好地协调其探索和开发能力并在整个搜索过程中保持多样性。

    (3)莱维飞行扰动策略

    本文引入莱维飞行机制,对寻优过程中位置更新方式进行扰动操作, 改善算法易陷入局部最优及出现早熟收敛现象。通过莱维飞行,新的位置更新公式如下: X l ( t ) = X ( t ) + α ⊕ L e v y ( λ ) (11) \boldsymbol X^l(t)=\boldsymbol X(t)+\alpha ⊕Levy(\lambda)\tag{11} Xl(t)=X(t)+αLevy(λ)(11)式中, X l ( t ) \boldsymbol X^l(t) Xl(t)为莱维飞行扰动后的位置, ⊕ ⊕ 为点乘, α \alpha α为步长控制因子, L e v y ( λ ) Levy(\lambda) Levy(λ)表示随机搜索路径。具体的莱维飞行公式请参考这里
    由于不能保证莱维飞行扰动后的位置优于原位置,所以本文采用贪婪选择决定是否更新鲸鱼位置,即新位置适应度值优于原位置的适应度值则保留,否则舍弃,公式为: X ( t + 1 ) = { X l ( t ) f [ X l ( t ) ] < f [ X ( t ) ] X ( t )   f [ X l ( t ) ] ≥ f [ X ( t ) ] (12) \boldsymbol X(t+1)=\begin{dcases}\boldsymbol X^l(t)\quad f[\boldsymbol X^l(t)]<f[\boldsymbol X(t)]\\\boldsymbol X(t)\quad\, f[\boldsymbol X^l(t)]≥f[\boldsymbol X(t)]\end{dcases}\tag{12} X(t+1)={Xl(t)f[Xl(t)]<f[X(t)]X(t)f[Xl(t)]f[X(t)](12)

    二、算法流程

    算法流程如图1所示。
    在这里插入图片描述

    图1 IWOA覆盖优化流程图

    三、仿真实验与分析

    1、实验环境

    为验证本文改进的鲸鱼算法应用于WSN覆盖优化性能,用MATLAB进行仿真,将原始WOA、改进后的IWOA 和其他文献的覆盖效果进行对比,其中实验的参数与其他文献的对应参数设置相同。参与对比的算法如表1所示。

    表1 对比算法

    在这里插入图片描述

    2、实验结果

    (1)与FA算法对比

    将实验参数设置与文献[2]相同, 设监测区域为 50 m × 50 m 50 m×50 m 50m×50m的二维平面, 传感器节点个数 N = 35 N=35 N=35,其感知半径是 R s = 5 m R_s = 5 m Rs=5m,通信半径 R c = 10 m R_c= 10 m Rc=10m,迭代1000次。初始部署、FA优化覆盖、IWOA优化覆盖如图2~4所示。
    在这里插入图片描述

    图2 初始部署

    在这里插入图片描述

    图3 FA优化覆盖

    在这里插入图片描述

    图4 IWOA优化覆盖

    二者的对比如图5所示。
    在这里插入图片描述

    图5 FAvsIWOA

    (2)与EABC算法对比

    将实验参数设置与文献[3]相同,即监测区域为 100 m × 100 m 100 m×100 m 100m×100m的二维正方形平面,部署同构传感器节点个数 N = 50 N=50 N=50,其感知半径是 R s = 10 m R_s=10 m Rs=10m,通信半径 R c = 20 m R_c=20 m Rc=20m,迭代次数为1000。图6为EABC初始部署,图7为EABC优化覆盖图,图8为IWOA优化覆盖图,图9为二者对比图。
    在这里插入图片描述

    图6 EABC初始部署

    在这里插入图片描述

    图7 EABC优化覆盖

    在这里插入图片描述

    图8 IWOA优化覆盖

    在这里插入图片描述

    图9 EABCvsIWOA

    四、参考文献

    [1] 宋婷婷, 张达敏, 王依柔,等. 基于改进鲸鱼优化算法的WSN覆盖优化[J]. 传感技术学报, 2020, 33(3):415-422.
    [2] Tuba E , Tuba M , Beko M . Mobile wireless sensor networks coverage maximization by firefly algorithm[C]// Radioelektronika. IEEE, 2017:1-5.
    [3] 于文杰,李迅波,羊行,黄波.外推人工蜂群算法在WSN部署优化中的应用研究[J].仪表技术与传感器,2017(06):158-160+164.
    [4] ~心升明月~. 基于鲸鱼优化算法的函数寻优算法. CSDN博客.
    [5] ~心升明月~. 基于嵌入莱维飞行的灰狼优化(LGWO)算法的函数寻优算法. CSDN博客.

    展开全文
  • 本文为大家分享了Python遗传算法解决最大流问题,供大家参考,具体内容如下Generate_matrixdef Generate_matrix(x,y):import numpy as npimport randomreturn np.ceil(np.array([random.random()*10 for i in range...

    本文为大家分享了Python遗传算法解决最大流问题,供大家参考,具体内容如下

    Generate_matrix

    def Generate_matrix(x,y):

    import numpy as np

    import random

    return np.ceil(np.array([random.random()*10 for i in range(x*y)]).reshape(x,y))

    Max_road

    def Max_road(A,degree,start):

    import random

    import numpy as np

    import copy

    def change(M,number,start): # number 控制变异程度 start 控制变异量

    x,y = M.shape

    for i in range(start,x):

    Line = zip(range(len(M[i])),M[i])

    index_0 = [t[0] for t in Line if t[1]==0] # 获取 0 所对应的下标

    index_1 = [t[0] for t in Line if t[1]==1] # 获取 1 所对应的下标

    M[i][random.sample(index_0,number)[0]]=1 # 随机改变序列中 number 个值 0->1

    M[i][random.sample(index_1,number)[0]]=0 # 随机改变序列中 number 个值 1->0

    return M

    x,y = A.shape

    n=x

    generation = y

    #初始化一个有 n 中情况的解决方案矩阵

    init_solve = np.zeros([n,x+y-2])

    init=[1]*(x-1)+[0]*(y-1)

    for i in range(n) :

    random.shuffle(init)

    init_solve[i,:] = init # 1 表示向下走 0 表示向右走

    solve = copy.copy(init_solve)

    for loop in range(generation):

    Sum = [A[0,0]]*n # 用于记录每一种方案的总流量

    for i in range(n):

    j=0;k=0;

    for m in solve[i,:]:

    if m==1:

    k=k+1

    else:

    j=j+1

    Sum[i] = Sum[i] + A[k,j]

    Sum_index = zip(range(len(Sum)),Sum)

    sort_sum_index = sorted(Sum_index,key = lambda d : d[1],reverse =True) # 将 方案 按照流量总和排序

    Max = sort_sum_index[0][1] # 最@R_497_403@

    #print Max

    solve_index_half = [a[0] for a in sort_sum_index[:n/2]] # 保留排序后方案的一半

    solve = np.concatenate([solve[solve_index_half],solve[solve_index_half]]) # 将保留的一半方案 进行复制 ,复制部分用于变异

    change(solve,int((x+y-2)*degree)+1,start) # 变异

    return solve[0],Max

    Draw_road

    def Draw_road(road,A):

    import pylab as plt

    import seaborn

    seaborn.set()

    x,y =A.shape

    # 将下移和右移映射到绘图坐标上

    Road = [(1,x)] # 初始坐标

    j=1;k=x;

    for m in road:

    if m==1:

    k=k-1

    else:

    j=j+1

    Road.append((j,k))

    # print Road

    for i in range(len(road)):

    plt.plot([Road[i][0],Road[i+1][0]],[Road[i][1],Road[i+1][1]])

    实际运行的例子

    In [119]: A = Generate_matrix(4,6)

    In [120]: A

    Out[120]:

    array([[ 10.,1.,7.,10.,8.,8.],[ 4.,4.,2.],[ 9.,3.,9.,[ 7.,2.,5.,8.]])

    In [121]: road,M=Max_road(A,0.1,2)

    In [122]: Draw_road(road,A)

    15182575431.jpg?2018029161344

    较大规模的情况

    In [105]: A = Generate_matrix(40,60)

    In [106]: road,4)

    In [107]: road

    Out[107]:

    array([ 0.,0.,1.])

    In [108]: Draw_road(road,A)

    15182575442.jpg?201802916144

    In [109]: A = generate_Matrix(100,200)

    In [110]: road,10)

    In [111]: draw_road(road,A)

    15182575443.jpg?2018029161424

    以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持编程小技巧。

    总结

    如果觉得编程之家网站内容还不错,欢迎将编程之家网站推荐给程序员好友。

    本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。

    如您喜欢交流学习经验,点击链接加入交流1群:1065694478(已满)交流2群:163560250

    展开全文
  • LINE是一种基于graph产生embedding的方法,它可以适用于任何类型的graph,如无向图、有向图、加权图等,同时作者基于边采样进行了目标函数的优化,使算法既能捕获到局部的网络结构,也能捕获到全局的网络结构。...

    1 概述

    LINE是2015年微软发表的一篇论文,其全称为: Large-scale Information Network Embedding。论文下载地址:https://arxiv.org/pdf/1503.03578.pdf

    LINE是一种基于graph产生embedding的方法,它可以适用于任何类型的graph,如无向图、有向图、加权图等,同时作者基于边采样进行了目标函数的优化,使算法既能捕获到局部的网络结构,也能捕获到全局的网络结构。

    2 算法原理

    2.1 新的相似度定义

    该算法同时优化了节点的相似度计算方法,提出了一二阶相似度。

    一二阶连接举例

    1、一阶相似度

    一阶相似度用来描述的是两个顶点之间有一条边直接相连的情况,如果两个 u 、 v u、v uv 之间存在直连变,则其一阶相似度可以用权重 w u v w_{uv} wuv来表示,如果不存在直连边,则一阶相似度为0。

    上图中,顶点6、7之间是直接相连的,且权重比较大(边比较粗),则认为顶点6、7是相似的,且一阶相似度较高,顶点5、6之间并没有直接相连,则两者的一阶相似度为0。

    2、二阶相似度

    二阶相似度描述的是两个顶点之间没有直接相连,但是他们拥有相同的邻居。比如顶点 u 、 v u、v uv 直接不存在直接相连,但是 顶点 u u u 存在其自己的一阶连接点, u u u 和 对应的一阶连接点 的一阶相似度可以形式化定义为: p ( u ) = ( w u , 1 , . . . , w u , ∣ V ∣ ) p(u) = (w_{u,1}, ..., w_{u, |V|}) p(u)=(wu,1,...,wu,V) ,同理可以得到顶点 v v v 和对应的一阶连接点的一阶相似度定义: p ( v ) = ( w v , 1 , . . . , w v , ∣ V ∣ ) p(v) = (w_{v,1}, ..., w_{v, |V|}) p(v)=(wv,1,...,wv,V) ,顶点 u 、 v u、v uv 之间的相似度即为 p ( u ) 、 p ( v ) p(u)、p(v) p(u)p(v) 之间的相似度。

    上图中,顶点 5、6之间并没有直接相连,但是他们各自的一阶连接点是相同的,说明他们也是相似的。二阶相似度就是用来描述这种关系的。

    2.2 优化目标

    1、一阶相似度

    对于每一条无向边 ( i , j ) (i,j) (i,j) ,定义顶点 v i , v j v_i, v_j vi,vj之间的联合概率为:
    p 1 ( v i , v j ) = 1 1 + e x p ( − u i ⃗ ⋅ u j ⃗ ) p_1(v_i,v_j) = \frac{1} {1+exp(- \vec{u_i} \cdot \vec{u_j})} p1(vi,vj)=1+exp(ui uj )1
    其中 u i ⃗ ∈ R d \vec{u_i} \in R^d ui Rd 为顶点 v i v_i vi 的低维向量表示(可以看作一个内积模型,计算两个item之间的匹配程度)。

    同时定义经验分为:
    p ^ 1 ( i , j ) = w i , j W \hat{p}_1(i,j) = \frac{w_{i,j}}{W} p^1(i,j)=Wwi,j
    其中 W = ∑ i , j ∈ E w i , j W = \sum_{i,j \in E} w_{i,j} W=i,jEwi,j

    为了计算一阶相似度,优化的目标函数为:
    O 1 = d ( p ^ 1 ( ⋅ , ⋅ ) , p 1 ( ⋅ , ⋅ ) ) O_1 = d(\hat{p}_1(\cdot , \cdot), p_1(\cdot , \cdot)) O1=d(p^1(,),p1(,))
    其中 d ( ⋅ , ⋅ ) d(\cdot , \cdot) d(,) 是两个分布的距离,常用的衡量两个概率分布差异的指标为 KL 散度,使用 KL 散度并忽略常用项后有:
    O 1 = − ∑ ( i , j ) ∈ E w i , j l o g   p 1 ( v i , v j ) O_1 = - \sum_{(i,j) \in E} w_{i,j} log \, p_1 (v_i, v_j) O1=(i,j)Ewi,jlogp1(vi,vj)
    一阶相似度只能用于无向图中。

    2、二阶相似度

    和一阶相似度不同的是,二阶相似度既可以用于无向图,也可以用于有向图。二阶相似度计算的假设前提是:两个顶点共享其各自的一阶连接顶点,在这种情况下,顶点被看作是一种特定的「上下文」信息,因此每一个顶点都扮演了两个角色,即拥有两个embedding向量,一个是顶点本身的表示向量,一个是该点作为其他顶点的上下文顶点时的表示向量。

    对于有向边 ( i , j ) (i,j) (i,j),定义给定顶点 v i v_i vi 的条件下,产生上下文(邻居)顶点 v j v_j vj 的概率为:
    p 2 ( v j ∣ v i ) = e x p ( u j ⃗ T ⋅ u i ⃗ ) ∑ k = 1 ∣ V ∣ e x p ( u k ⃗ T ⋅ u i ⃗ ) p_2(v_j|v_i) = \frac {exp(\vec{u_j}^T \cdot \vec{u_i})}{ \sum_{k=1}^{|V|} exp(\vec{u_k}^T \cdot \vec{u_i})} p2(vjvi)=k=1Vexp(uk Tui )exp(uj Tui )
    其中 ∣ V ∣ |V| V 为上下文顶点的个数。

    二阶相似度定义的优化的目标函数为:
    O 2 = ∑ i ∈ V λ i d ( p ^ 2 ( ⋅ ∣ v i ) , p 2 ( ⋅ ∣ v i ) ) O_2 = \sum_{i \in V} \lambda_i d(\hat{p}_2(\cdot|v_i), p_2(\cdot|v_i)) O2=iVλid(p^2(vi),p2(vi))
    其中 λ i \lambda_i λi 为控制节点重要性的因子,可以通过顶点的度数或者 PageRank等方法估计得到。

    同样定义经验分为:
    p 2 ^ ( v j ∣ v i ) = w i j d i \hat{p_2}(v_j | v_i) = \frac{w_{ij}}{d_i} p2^(vjvi)=diwij
    其中, w i j w_{ij} wij 是边 ( i , j ) (i,j) (i,j) 的边权, d i d_i di 是顶点 v i v_i vi 的出度,对于带权图, d i = ∑ k ∈ N ( I ) W i k d_i = \sum_{k \in N(I)} W_{ik} di=kN(I)Wik

    使用KL散度计算两个概率的差异,化简后有:
    O 2 = − ∑ ( i , j ) ∈ E w i , j   l o g   p 2 ( v j ∣ v i ) O_2 = -\sum_{(i,j) \in E} w_{i,j} \, log \, p_2(v_j | v_i) O2=(i,j)Ewi,jlogp2(vjvi)

    2.3 优化技巧

    1、Negative Sampling

    二阶相似度计算中,在计算条件概率 p 2 ( ⋅ ∣ v i ) p_2(\cdot|v_i) p2(vi) 时,需要遍历所有的顶点,效率非常低下,论文中采用了负采样的技术,优化后,目标函数为:
    l o g   σ ( u j ⃗ T ⋅ u i ⃗ ) + ∑ i = 1 K E v n ∼ P n ( v ) [ − l o g   σ ( u n ⃗ T ⋅ u i ⃗ ) ] log \, \sigma (\vec{u_j}^T \cdot \vec{u_i}) + \sum_{i=1}^{K} E_{v_n} \sim P_n(v)[-log \, \sigma(\vec{u_n}^T \cdot \vec{u_i}) ] logσ(uj Tui )+i=1KEvnPn(v)[logσ(un Tui )]
    其中 K K K 为负采样的个数。

    论文中定义 p n ( v ) p_n(v) pn(v) 正比于 d v 3 / 4 d_v ^{3/4} dv3/4 d v d_v dv 是顶点 v v v 的出度(采样的个数为:出度的 3/4 幂)。

    同时论文中使用 ASGD(Asynchronous Stochastic Gradient)算法进行优化。

    2、Edge Sampling

    在定义的一、二阶目标函数时,log之前还有一个权重系数 w i , j w_{i,j} wi,j ,在使用梯度下降方法优化参数时, w i , j w_{i,j} wi,j 会直接乘在梯度上。如果图中的边权方差很大,则很难选择一个合适的学习率。若使用较大的学习率那么对于较大的边权可能会引起梯度爆炸,较小的学习率对于较小的边权则会导致梯度过小。

    对于上述问题,如果所有边权相同,那么选择一个合适的学习率会变得容易。这里采用了将带权边拆分为等权边的一种方法,假如一个权重为 w w w 的边,则拆分后为 w w w 个权重为1的边。这样可以解决学习率选择的问题,但是由于边数的增长,存储的需求也会增加。

    另一种方法则是从原始的带权边中进行采样,每条边被采样的概率正比于原始图中边的权重,这样既解决了学习率的问题,又没有带来过多的存储开销。

    这里的采样算法使用的是Alias算法,Alias是一种 O ( 1 ) O(1) O(1) 时间复杂度的离散事件抽样算法。具体内容可以参考:时间复杂度O(1)的离散采样算法—— Alias method/别名采样方法

    2.4 其他讨论点

    1、低度顶点的嵌入表示

    由于低度顶点邻居数目极少,原网络中提供的信息有限,尤其在基于二阶相似度的LINE算法中是非常依赖于顶点的邻居数目的,那么如何确定低度顶点的向量表示呢?

    一种直观的方法:添加更高阶的邻居(如邻居的邻居)来作为该低度结点的直接邻居。 与新添邻居边的权重如下:
    w i j = ∑ k ∈ N ( i ) w i k w k j d k w_{ij} = \sum_{k \in N(i)} w_{ik} \frac{w_{kj}} {d_k} wij=kN(i)wikdkwkj
    d k d_k dk 是结点 k k k 的出边的权重总和(实际上,可以只添加与低度顶点 i i i 有边的,且边权最大的顶点 j j j 的邻居作为顶点i的二阶邻居)

    2、如何找到网络中新添加顶点的向量表示

    如果已知新添加的顶点i与现有顶点的联系(即存在边),则可得到其经验分布: p ^ 1 ( ⋅ , v i ) \hat{p}_1(\cdot, v_i) p^1(,vi) p ^ 2 ( ⋅ ∣ v i ) \hat{p}_2(\cdot | v_i) p^2(vi)

    之后通过最小化一、二阶相似度的目标函数可得到新加顶点i的向量表示:
    $$

    • \sum_{j \in N(i)} w_{ji} , log , p_1(v_j, v_i)
      或 者 : 或者:
    • \sum_{j \in N(i)} w_{ji} , log , p_1(v_j | v_i)
      $$
      如果未能观察到新添顶点与其他现有顶点的联系,我们只能求助其他信息,比如顶点的文本信息,留待以后研究。

    3 实验

    算法在以下的数据集上进行了测试

    数据集

    对比了算法:

    • Graph factorization (GF)
    • DeepWalk
    • LINE-SGD
    • LINE
    • LINE(1st+2nd)

    使用的评估指标为:

    • Micro-F1
    • Macro-F1

    在维基百科上的相关算法表现如下(更多看的是在语义、句法、覆盖率、运行时间上的对比分析):

    维基百科上的相关算法表现

    在维基百科上进行的分类对比实验结果如下,可以看出LINE(1st+2nd)是要比其他算法效果明显的

    维基百科上进行的分类对比实验结果

    在Flickr网络数据上进行的多目标分类LINE(1st+2nd)的效果也不错

    在这里插入图片描述

    将产出的embedding降维到2度,并进行可视化,可以看出,LINE的聚类效果更加明显。

    可视化

    4 代码实现

    论文中给出了C 代码实现的地址

    https://github.com/tangjianpku/LINE

    「浅梦」也实现了很多的graph embedding算法,链接为:https://github.com/shenweichen/GraphEmbedding。当然我也看到有人基于tf实现了LINE算法,算是扩展了眼界吧,其主要代码如下,完整链接为:https://github.com/snowkylin/line。

    import tensorflow as tf
    import numpy as np
    import argparse
    from model import LINEModel
    from utils import DBLPDataLoader
    import pickle
    import time
    
    
    def main():
        parser = argparse.ArgumentParser()
        parser.add_argument('--embedding_dim', default=128)
        parser.add_argument('--batch_size', default=128)
        parser.add_argument('--K', default=5)
        parser.add_argument('--proximity', default='second-order', help='first-order or second-order')
        parser.add_argument('--learning_rate', default=0.025)
        parser.add_argument('--mode', default='train')
        parser.add_argument('--num_batches', default=300000)
        parser.add_argument('--total_graph', default=True)
        parser.add_argument('--graph_file', default='data/co-authorship_graph.pkl')
        args = parser.parse_args()
        if args.mode == 'train':
            train(args)
        elif args.mode == 'test':
            test(args)
    
    
    def train(args):
        data_loader = DBLPDataLoader(graph_file=args.graph_file)
        suffix = args.proximity
        args.num_of_nodes = data_loader.num_of_nodes
        model = LINEModel(args)
        with tf.Session() as sess:
            print(args)
            print('batches\tloss\tsampling time\ttraining_time\tdatetime')
            tf.global_variables_initializer().run()
            initial_embedding = sess.run(model.embedding)
            learning_rate = args.learning_rate
            sampling_time, training_time = 0, 0
            for b in range(args.num_batches):
                t1 = time.time()
                u_i, u_j, label = data_loader.fetch_batch(batch_size=args.batch_size, K=args.K)
                feed_dict = {model.u_i: u_i, model.u_j: u_j, model.label: label, model.learning_rate: learning_rate}
                t2 = time.time()
                sampling_time += t2 - t1
                if b % 100 != 0:
                    sess.run(model.train_op, feed_dict=feed_dict)
                    training_time += time.time() - t2
                    if learning_rate > args.learning_rate * 0.0001:
                        learning_rate = args.learning_rate * (1 - b / args.num_batches)
                    else:
                        learning_rate = args.learning_rate * 0.0001
                else:
                    loss = sess.run(model.loss, feed_dict=feed_dict)
                    print('%d\t%f\t%0.2f\t%0.2f\t%s' % (b, loss, sampling_time, training_time,
                                                        time.strftime("%Y-%m-%d %H:%M:%S", time.localtime())))
                    sampling_time, training_time = 0, 0
                if b % 1000 == 0 or b == (args.num_batches - 1):
                    embedding = sess.run(model.embedding)
                    normalized_embedding = embedding / np.linalg.norm(embedding, axis=1, keepdims=True)
                    pickle.dump(data_loader.embedding_mapping(normalized_embedding),
                                open('data/embedding_%s.pkl' % suffix, 'wb'))
    
    
    def test(args):
        pass
    
    if __name__ == '__main__':
        main()
    

    5 应用

    LINE是与基于Graph构建的item embedding,在拿到item的embedding之后,我们可以进行的工作包括:

    • 作为特征在粗排模型、精排模型进行使用
    • 用来进行embedding的检索召回
    • 分类
    • 聚类

    有一点需要注意的是,LINE算法可以应用到有向图、无向图、带权图中,相比DeepWalk等graph算法更加的灵活,但还是要看自己的需求而定,选用合适的算法做合适的事。


    【技术服务】详情点击查看: https://mp.weixin.qq.com/s/PtX9ukKRBmazAWARprGIAg

    在这里插入图片描述
    扫一扫关注「搜索与推荐Wiki」!号主「专注于搜索和推荐系统,以系列分享为主,持续打造精品内容!

    展开全文
  • 二分图指的是这样一种图,其所有顶点可以分成两个集合X和Y,其中X或Y中任意两个在同一集合中的点都不相连,所有的边...二分图的最大匹配有两种求法,第一种是最大流;第二种就是我现在要讲的匈牙利算法。这个算法...
  • 贪心算法/贪婪算法

    2021-08-02 23:20:07
    贪心算法是所有算法中最简单、最易实现的一种算法,的吗? 世界上本没有贪,学算法的人多了,也便有了贪。你贪我也贪,贪心算法也变得越来越难贪了。 但是,万变不离其宗,打好基础得其根,我想怎么贪,就怎么贪...
  • 算法之贪心算法

    2021-05-31 17:42:19
    贪心算法 贪婪算法(贪心算法)是指在对问题进行求解时,在每一步选择中都采取最好或者最优(即最有利)的选择,从而希望能够导致结果是最好或者最优的算法 ...在经过一次贪心选择之后,问题将变成一个相似的,
  • 数据结构与算法必知基础知识

    千次阅读 多人点赞 2021-01-06 22:58:12
    文章已收录在 全网都在关注的数据结构与算法学习仓库 欢迎star 前言 数据结构与算法是程序员内功体现的重要标准之一,且数据结构也应用在各个方面,业界更有程序=数据结构+算法这个等式存在。各个中间件开发者,...
  • Android 音频倍速的原理与算法分析

    千次阅读 多人点赞 2021-10-31 00:58:15
    即便如此,在帧裁剪的过程中,仍然无法保证每一个帧都能覆盖完整周期并保证其相位对齐,这种失真也叫相位跳跃失真(phase jump artifacts),对于音频的听感仍然不佳: 如图,两个周期信号帧通过 OLA 合成后变得 ...
  • 找出数组中最大值所在下标位置3.找出数组中指定元素第一次出现的下标位置4.在数组中找出指定下标对应的元素5.找出指定元素在数组中最后一次出现位置6.找到元素在指定数组中的所有下标位置7.在指定位置插入指定元素8....
  • 《双指针》困难01 —— LeetCode 76. 最小覆盖子串
  • 算法

    2020-12-28 15:36:37
    1.图搜索算法 --邻接矩阵 邻接链表型数据 BFS 广度优先搜索 从根节点开始,沿着树的宽度遍历节点,遍历所有节点算法结束 从算法的观点,所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。 一般实现里...
  • 算法分析与设计 八大排序算法

    千次阅读 2021-11-21 21:11:27
    八大排序算法八大排序分类01 冒泡排序02 直接插入排序03 简单选择排序04 希尔排序05 快速排序06 堆排序07 归并排序08 桶排序/基数排序参考资料 八大排序分类 ​ 笔者是在LeetCode刷题过程中来复习排序算法的,虽然在...
  • 文章目录一、理论基础1、人工蜂群算法2、改进人工蜂群算法二、仿真与分析1、参数设置2、MATLAB程序实现三、算法对比四、参考文献 一、理论基础 1、人工蜂群算法 请参考这里。 ...计算WSN覆盖率函数
  • 算法分析与设计中的五大常用算法一、分治算法1. 基本概念2. 基本思想及策略3. 分治法适用的情况4. 分治法的基本步骤5. 分治法求解的一些经典问题二、 动态规划算法1. 基本概念2. 基本思想与策略3. 适用的情况4. 求解...
  • 代表了匹配搜苏从哪里开始,numberOfDisparities表示最大搜索视差数uniquenessRatio表示匹配功能函数,这三个参数比较重要,可以根据实验给予参数值。 该方法速度最快,一副320*240的灰度图匹配时间为31ms SBGM SGBM...
  • 例题:键盘输入一个正整数n,去掉其中任意s个数字后剩下的数字按左右次序将组成一个新的正整数。编程对给定的n和s,寻找一种方案使得剩下的数字组成新数最小。(n不超过240)问题分析:在位数固定的情况下,让高位的...
  • 如果没有合并就把区间加入到result数组。 C++代码如下: class Solution { public: // 按照区间左边界从小到大排序 static bool cmp (const vector& a, const vector& b) { return a[0] [0]; } vector> merge...
  • 在二分图中,包含边数最多的一组匹配被称为二分图的最大匹配。 匈牙利算法(增广路算法)时间复杂度 O(NM) 能用二分图匹配的模型一般包括两个要素 0要素 每个集合内部有0条边 1要素 每个节点只能和一条匹配...
  • 常用十大算法

    2021-09-25 16:51:24
    二分查找(非递归)算法:前面我们涉及的是递归实现二分查找算法。如今实现的是非递归的方式。同样,二分查找只适用于有序数列。二分查找的运行时间为对数时间O(log2n),即查找到需要的目标...
  • 指派问题算法

    千次阅读 2021-04-12 01:42:00
    M ′ w ( u , v ) \sum_{u,v\in M}w(u,v)\le\sum_{u,v\in M'}w(u,v) u,v∈M∑​w(u,v)≤u,v∈M′∑​w(u,v) 故该匹配 M ′ M' M′就是二分图的最大权完美匹配 算法(一般称之为匈牙利算法): 初始化 l ( u ) = ...
  • 文章目录区间问题区间选点原题链接:题目大意:思路:证明:代码:区间分组原题链接:题目大意:思路:证明:代码:区间覆盖原题链接:题目大意:思路:代码:huffman树合并果子原题链接题目大意:思路:代码: ...
  • 这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。 我们来对贪心算法和动态规划算法做一个对比。 在动态规划算法中,每步所做的选择往往依赖于相关子问题的解。因而只有在解出相关的子...
  • 匈牙利算法 0 引出 最近看DETR论文,发现其通过匈牙利算法来进行预测和ground truth匹配,从而实现set prediction。这个思路很有意思,并且该匹配算法能适用多种问题,因此,对其进行详细记录,便于后续回顾。 首先...
  • 当你有一天忘了这个算法的代码怎么写,仅仅凭借自己的理解就能复现出来原算法,那才是真正掌握。 我也曾经做过Leetcode上一些有意思的题目,也曾逛过评论区,很多题解都是一知半解,甚至并不正确。试想当这道题目换...
  • 2021年-算法期末试题汇总

    千次阅读 多人点赞 2020-12-18 20:52:02
    1.算法分析中,记号O表示(B),记号Ω标售(A),记号Θ表示(D) A 渐进下界 B 渐进上界 C 非紧上界 D 紧渐进界 E 非紧下界 2.以下关于渐进记号的性质是正确的有:(A) A f(n) =Θ(g(n)),g(n) =Θ(h(n)) ⇒f(n) =...
  • 算法设计与分析期末复习题(史上最详细)

    万次阅读 多人点赞 2021-06-07 13:25:06
    算法设计与分析期末复习题(一) 1、二分搜索算法是利用( A )实现的...3、最大效益优先是( A )的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是( B )。 A、
  • 贪心算法a

    2021-08-19 21:15:38
    贪心算法 ...第二步,我们尝试看下这个问题是否可以用贪心算法解决:每次选择当前情况下,对限制值同等贡献量的情况下,对期望值贡献最大的数据。 第三步,我们举几个例子看下贪心算法产生的结果是否是
  • BM算法详解

    2021-03-07 16:22:14
    来源在没有BM算法时,其原始算法是从后往前进行匹配,需要两层循环,判断以某个字符为结尾的子串是否和模式串相等,这种算法也称作暴搜;贴上代码:void BLS(string s, string p) {int s_len = s.size(), p_len = p....
  • 遗传算法的特性以及在具体算法应用中的应用 1 引言 ​ 近些年以来,随着人工智能领域的不断发展,数据处理和分析的量变得越来越大,随之而来的考验便是如何解决大量数据的处理和算法优化。而面对大规模的集成优化...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 64,188
精华内容 25,675
关键字:

最大覆盖原算法