精华内容
下载资源
问答
  • 标签传播算法

    2019-10-09 03:07:47
    标签传播算法(Label Propagation Algorithm,LPA)是由Zhu等人于2002年提出,它是一种基于图的半监督学习方法,其基本思路是用已标记节点的标签信息去预测未标记节点的标签信息。 LPA算法思路简单清晰,其基本...

    1.LPA算法简介   

          标签传播算法(Label Propagation Algorithm,LPA)是由Zhu等人于2002年提出,它是一种基于图的半监督学习方法,其基本思路是用已标记节点的标签信息去预测未标记节点的标签信息。

           LPA算法思路简单清晰,其基本过程如下:

    (1)为每个节点随机的指定一个自己特有的标签;

    (2)逐轮刷新所有节点的标签,直到所有节点的标签不再发生变化为止。对于每一轮刷新,节点标签的刷新规则如下:

           对于某一个节点,考察其所有邻居节点的标签,并进行统计,将出现个数最多的那个标签赋值给当前节点。当个数最多的标签不唯一时,随机选择一个标签赋值给当前节点。

          在标签传播算法中,节点的标签更新通常有同步更新和异步更新两种方法。同步更新是指,节点x在t时刻的更新是基于邻接节点在t-1时刻的标签。异步更新是指,节点x在t时刻更新时,其部分邻接节点是t时刻更新的标签,还有部分的邻接节点是t-1时刻更新的标签。LPA算法在标签传播过程中采用的是同步更新,研究者们发现同步更新应用在二分结构网络中,容易出现标签震荡的现象。因此,之后的研究者大多采用异步更新策略来避免这种现象的出现。

    2.LPA算法

    2.1相似矩阵构建

           令( x1,y1) …( xl,yl) 是已标注数据,YL={ y1…yl} ∈{ 1…C} 是类别标签,类别数 C 已知,且均存在于标签数据中。令( xl + 1,yl + 1) …( xl + u,yl + u) 为未标注数据,YU={ yl + 1…yl + u} 不可观测,l << u,n=l+u。令数据集 X = { x1…xl + u} ∈R。问题转换为: 从数据集 X 中,利用YL的学习,为未标注数据集YU的每个数据找到对应的标签。将所有数据作为节点( 包括已标注和未标注数据) ,创建一个图,这个图的构建方法有很多,这里我们假设这个图是全连接的,节点i和节点j的边权重为:
    这里,α是超参。还有个非常常用的图构建方法是knn图,也就是只保留每个节点的k近邻权重,其他的为0,也就是不存在边,因此是稀疏的相似矩阵。

     2.2LPA算法

           标签传播算法非常简单:通过节点之间的边传播label。边的权重越大,表示两个节点越相似,那么label越容易传播过去。我们定义一个NxN的概率转移矩阵P:

           Pij表示从节点i转移到节点j的概率。我们将YL和YU合并,我们得到一个NxC的soft label矩阵F=[YL;YU]。soft label的意思是,我们保留样本i属于每个类别的概率,而不是互斥性的,这个样本以概率1只属于一个类。当然了,最后确定这个样本i的类别的时候,是取max也就是概率最大的那个类作为它的类别的。那F里面有个YU,它一开始是不知道的,那最开始的值是多少?无所谓,随便设置一个值就可以了。

           简单的LP算法如下:

    (1)执行传播:F=PF;

    (2)重置F中labeled样本的标签:FL=YL;

    (3)重复步骤(1)和(2)直到F收敛。

           步骤(1)就是将矩阵P和矩阵F相乘,这一步,每个节点都将自己的label以P确定的概率传播给其他节点。如果两个节点越相似(在欧式空间中距离越近),那么对方的label就越容易被自己的label赋予。步骤(2)非常关键,因为labeled数据的label是事先确定的,它不能被带跑,所以每次传播完,它都得回归它本来的label。

    2.3变身的LPA算法

           我们知道,我们每次迭代都是计算一个soft label矩阵F=[YL;YU],但是YL是已知的,计算它没有什么用,在步骤(2)的时候,还得把它弄回来。我们关心的只是YU,那我们能不能只计算YU呢?我们将矩阵P做以下划分:

    令   

    这时候,我们的算法就一个运算:

     

            迭代上面这个步骤直到收敛就ok了。可以看到fU不但取决于labeled数据的标签及其转移概率,还取决了unlabeled数据的当前label和转移概率。因此LP算法能额外运用unlabeled数据的分布特点。

    2.4收敛性证明

          当n趋近于无穷大是,有

     

    其中是fU的初始值,因此我们需要证明  因为P是行标准化的,并且PUU是P的子矩阵,所以

     

     

    因此

    当n趋近于无穷大时,rn=0,(PUU)n收敛于0,也意味着因此的初始值是无关紧要的,同时第n次迭代时fU收敛。

     

     

     

     

     

     

     

     

     

     

     

     
     

    转载于:https://www.cnblogs.com/Albertahuan/p/11449179.html

    展开全文
  • 什么是标签传播算法?为什么要使用标签传播算法?如何使用?.pdf
  • 标签传播算法解读.pdf

    2021-09-14 14:58:12
    标签传播算法解读.pdf
  • 最小代价路径标签传播算法
  • 标签传播算法LPA

    2019-01-15 21:03:05
    标签传播算法,能快速准确的识别网络社团,效率高,接近线性,但是对于二分图会产生震荡现象
  • 标签传播算法解读

    2020-07-10 13:04:29
    2020-07-08 11:00:08 作者:Vijini Mallawaarachchi 编译:ronghuaiyang 导读 ...基于图的标签传播算法的简单介绍。...社交媒体网络已经遍布全球,并且每天都在增长...标签传播算法(LPA)是一种迭代算法,通过在数据集中

    2020-07-08 11:00:08

    作者:Vijini Mallawaarachchi

    编译:ronghuaiyang

    导读

    基于图的标签传播算法的简单介绍。

    社交媒体网络已经遍布全球,并且每天都在增长。对于一个社交网络,你知道一些人的兴趣,你想预测其他人的兴趣,这样我们就可以有针对性地进行营销活动。为此,我们可以使用叫标签传播的基于图的半监督机器学习技术。在本文中,我将通过一些示例和示例代码解释标签传播过程。

    什么是标签传播?

    标签传播算法(LPA)是一种迭代算法,通过在数据集中传播标签,将标签分配给未标记的点。该算法由Xiaojin ZhuZoubin Ghahramani2002年首次提出。LPA属于转换学习,因为我们要预测已经给出的未标记数据点的标签。

    假设我们有一个如下所示的网络,其中有两个标签类“interested in cricket”(对板球感兴趣)和“not interested in cricket”(对板球不感兴趣)。所以问题是,我们能预测剩下的人是否对板球感兴趣吗?

    标签传播算法解读

     

    为了让LPA在这种情况下起作用,我们需要做一个假设,通过边连接的两个节点的边具有相似性。也就是说,如果两个人是连在一起的,这意味着这两个人很有可能拥有相同的兴趣。我们可以做出这样的假设,因为人们倾向于与有相似兴趣的人交往。

    在图中随机游走

    考虑图1中给出的示例图,其中我们有2个标签类(红色和绿色)和4个着色的节点(每个类2个)。我们想预测节点4的标签。

    标签传播算法解读

    图1,示例图

    我们可以在图中随机行走,从节点4开始,直到遇到任何标记节点。当我们到达一个标记节点时,我们停止游走。因此,这些标记的节点被称为吸收状态。让我们考虑所有可能的从节点4出发的路径。在所有可能的路径中,以下路径将以绿色节点结束。

    1. 4 → 9 → 15 → 16
    2. 4 → 9 → 13 → 14
    3. 4 → 9 → 13 → 15 → 16
    4. 4 → 9 → 15 → 13 → 14

    下面的路径以红色的节点结束。

    1. 4 → 7 → 8
    2. 4 → 7 → 6 → 5 → 1
    3. 4 → 5 → 1
    4. 4 → 5 → 6 → 7 → 8
    5. 4 → 2 → 1

    基于从节点4开始的所有可能的随机游走,我们可以看到大多数的游走都以红色节点结束。我们可以把结点4涂成红色。这是LPA背后的基本直觉。

    数学公式

    Xₗ是所有节点的标签的集合,Yₗ是已标记数据的one-hot标签。假设有{1,…,C}类标签,Xᵤ 是未标记的顶点,我们不知道Yᵤ是什么,因此Yᵤ是全0的。

    我们通过下面的公式来表示随机游走。

    标签传播算法解读

     

    在矩阵形式下,等式是下面这样的:

    标签传播算法解读

    图3,随机游走的矩阵形式

    如果我们可以计算概率转移矩阵T,我们可以计算所有未标记节点的标签概率。

    如何计算概率转移矩阵?

    标签传播算法解读

    图4,实例图2

    考虑具有吸收状态的示例图,如图4所示。对于每个节点,我们需要计算跳转到其他节点的概率。当我们到达吸收状态时,当我们被困在吸收状态(在图中表示为一个自循环)时,游走结束。这是一个无向图,所以我们可以向任何方向移动。

    假设从一个节点转移到它的邻居的概率是等可能的,我们可以把T写为:

    标签传播算法解读

    图5. 示例图2的矩阵

    从节点1到节点1的概率是1,因为节点1是吸收状态。从节点1,我们不能到达任何其他节点。因此从节点1到达其他节点的概率为0。同样的方法也适用于节点2。

    从节点4,可以转到节点1、3和5。因此,从节点4移动到节点1、3和5的概率相等,每个节点的概率为0.33。类似地,从节点5,我们可以以每个节点0.5的概率移动到节点4和6。

    注意,我们可以使用图的度矩阵(D)和邻接矩阵(A)计算T,使用下面的公式。

    T = D⁻¹A

    现在注意,我们可以分解矩阵T,如图6所示。

    标签传播算法解读

    图6,T可以分解成4个blocks

    • Tₗₗ — 从已标记节点到已标记节点的概率
    • Tₗᵤ — 从已标记节点到未标记节点的概率
    • Tᵤₗ — 从未标记节点到已标记节点的概率
    • Tᵤᵤ — 从未标记节点到未标记节点的概率

    注意:Tₗₗ是一个单位矩阵,Tₗᵤ是零矩阵,因为我们不能从已标记的节点离开,因为它们是吸收状态。

    如果我们将矩阵T和自己相乘t次,然后t趋于∞会发生什么?你可以在MATLAB中输入这个矩阵然后得到 T¹⁰⁰。你会得到这样的结果。

    标签传播算法解读

    图7. T乘以自己100次

    当你把T的次方的数量提高,概率将停止变化(饱和),并得到稳定的转移概率。现在可以看到,只有前两列包含非零值,其余的都是零。

    我们可以用数学的方法来描述它。

    标签传播算法解读

    图7. T自己乘方无穷次的公式

    得到最后的答案

    最后,带标签的矩阵是这样的,我们可以得到带标签节点的标签向量和未带标签节点的标签向量。

    标签传播算法解读

    图8. 标记的节点和未标记的节点的one-hot标签的公式

    现在让我们考虑图4中的示例图2,我们希望预测未标记节点的标签。利用MATLAB的结果,我们可以得到如下的标签。

    标签传播算法解读

    图9. 得到未标记节点的标签

    对于每个未标记节点,我们分配概率最大的类标签。但是,可以看到节点5出现红色和绿色的概率是相等的。因此,我们最终的标记图将如图10所示。

    标签传播算法解读

    图10. 示例图2的最后的标记结果

    示例代码

    创建图:

    from igraph import *
    
    node_count = 7
    
    # Create graph
    g = Graph()
    
    # Add vertices
    g.add_vertices(node_count)
    
    for i in range(len(g.vs)):
        g.vs[i]["id"]= i
        g.vs[i]["label"]= str(i+1)
    
    edges = [(0,3), (2,3), (3,4), (4,5), (5,6), (5,1)]
    
    g.add_edges(edges)
    
    g.simplify(multiple=True, loops=False, combine_edges=None)
    
    out_fig_name = "graph_plot.png"
    
    visual_style = {}
    
    # Define colors for nodes
    node_colours = ["red", "green", "grey", "grey", "grey", "grey", "grey"]
    g.vs["color"] = node_colours
    
    # Set bbox and margin
    visual_style["bbox"] = (500,500)
    visual_style["margin"] = 17
    
    # # Scale vertices based on degree
    # outdegree = g.outdegree()
    visual_style["vertex_size"] = 25
    
    # Set vertex lable size
    visual_style["vertex_label_size"] = 8
    
    # Don't curve the edges
    visual_style["edge_curved"] = False
    
    # Set the layout
    layout_1 = g.layout_fruchterman_reingold()
    visual_style["layout"] = layout_1
    
    # Plot the graph
    plot(g, out_fig_name, **visual_style)

    得到度矩阵和逆

    import numpy as np
    from numpy.linalg import inv
    
    D = np.matrix(np.array([[1,0,0,0,0,0,0], [0,1,0,0,0,0,0], [0,0,1,0,0,0,0], [0,0,0,3,0,0,0], [0,0,0,0,2,0,0], [0,0,0,0,0,3,0], [0,0,0,0,0,0,1]]))
    Dinv = inv(D)

    得到邻接矩阵

    A = np.matrix(np.array([[1,0,0,0,0,0,0], [0,1,0,0,0,0,0], [0,0,0,1,0,0,0], [1,0,1,0,1,0,0], [0,0,0,1,0,1,0], [0,1,0,0,1,0,1], [0,0,0,0,0,1,0]]))

    D的逆和A相乘

    S = Dinv*A

    标签传播算法

    import sys
    
    def LabelPropagation(T, Y, diff, max_iter, labelled):
        
        # Initialize
        Y_init = Y
        Y1 = Y
        
        # Initialize convergence parameters
        n=0
        current_diff = sys.maxsize
        
        # Iterate till difference reduces below diff or till the maximum number of iterations is reached
        while current_diff > diff or n < max_iter:
            
            current_diff = 0.0
            # Set Y(t)
            Y0 = Y1
            
            # Calculate Y(t+1)
            Y1 = T*Y0
            
            # Clamp labelled data
            for i in range(Y_init.shape[0]):
                if i in labelled:
                    for j in range(Y_init.shape[1]):
                        if i!=j:
                            Y1.A[i][j] = Y_init.A[i][j]
            
            # Get difference between values of Y(t+1) and Y(t)
            for i in range(Y1.shape[0]):
                for j in range(Y1.shape[1]):
                    current_diff += abs(Y1.A[i][j] - Y0.A[i][j])
            
            n += 1
            
        return Y1

    运行标签传播算法:

    %%time
    Y = np.matrix(np.array([[1,0], [0,1], [0,0], [0,0], [0,0], [0,0], [0,0]]))
    L = LabelPropagation(S, Y, 0.0001, 100, [0,1])

    未标记节点的标签:

    L.argmax(1)

    最后的想法

    LPA使用已标记节点的标签作为基础,并尝试预测未标记节点的标签。然而,如果最初的标签是错误的,这可能会影响标签的传播过程,错误的标签可能会被传播。为了解决这个问题,我们引入了标签扩展,在学习无标签节点的标签的同时也学习有标签节点的标签。这也是一种标签校正的应用。你可以从Dengyong Zhou等人的文章Learning with Local and Global Consistency中了解更多关于标签传播的信息。

    英文原文:https://towardsdatascience.com/label-propagation-demystified-cd5390f27472

    展开全文
  • 半监督+标签传播算法.pdf
  • 介绍了标签传播算法理论, 分析了标签传播算法的特点, 总结了其在多媒体信息检索、分类、标注、处理和社区发现等方面的应用研究, 最后探讨了标签传播算法未来的研究方向。
  • 重叠社区检测的加权标签传播算法
  • 基于数据重构的多级标签传播算法
  • 基于加权聚类集成的标签传播算法.pdf
  • 浅谈标签传播算法LPA

    2020-10-27 20:42:59
       研究生第一次对相关内容做了一个关于标签传播算法的汇报,查找了大量文献,发现很多的对于新手来说都看不懂,这里采用最简单的方法来浅谈一下,如有错误,欢迎指正。   标签传播算法是一种基于图的半监督...

       研究生期间第一次对相关内容做了一个汇报,查找了大量文献,发现很多的介绍对于新手来说都看不懂,这里采用最简单的方法来浅谈一下,如有错误,欢迎指正。


      标签传播算法是一种基于图的半监督学习方法,其基本思路是用已标记节点的标签信息去预测未标记节点的标签信息。利用样本间的关系建立关系完全图模型,在完全图中,节点包括已标注和未标注数据,其边表示两个节点的相似度,节点的标签按相似度传递给其他节点。标签数据就像是一个源头,可以对无标签数据进行标注,节点的相似度越大,标签越容易传播。该算法简单易实现,算法执行时间短,复杂度低且分类效果好。

    接下来直接放PPT


    1、首先来看LPA算法,其它的标签传播算法都是基于这个算法之上
    在这里插入图片描述
    下面直接举一个例子
    在这里插入图片描述



    2、LPAm没有找到很好的介绍
    在这里插入图片描述

    3、LPAm算法虽然克服了 LPA 算法稳定性弱的缺点,但是比较容易陷入局部最 优的境况。通过举例说明 LPAm算法陷入局部最优值的情况。如图 2-2 所示。 从图 2-2 a)中的网络可以看出,该网络很明显地应该被划分为两个社区。但是, LPAm算法将网络划分了如图 2-2 b)中所示的四个社区,这是因为 LPAm算法陷入了 局部最优的境况,且获得的模块度值为 0.399。但是,如果将图 2-2 b)中带有标签 a 的社区和带有标签 b的社区进行合并,那么模块度的值就会增加 0.008,这样可以避 免之前的局部最优值 0.399。继续执行 LPAm 算法,此时得到如图 2-2 d)所示的划分 结果,即将网络划分成了两个社区,两个社区之间通过一条边进行连接,并且模块 度值也会从之前的 0.407 增加到 0.413。这样,不仅获得了理想的社区,而且使得模块度值增加。因此,X.lin 等人在 LPAm 算法中增加了如图 2-2 所示的合并操作,克
    服了 LPAm算法中局部最优的缺点。

    在这里插入图片描述

    展开全文
  • 基于改进的标签传播算法的网络聚类方法
  • 基于改进的标签传播算法的网络聚类方法.pdf
  • 标签传播算法(Label Propagation Algorithm)

    万次阅读 多人点赞 2018-09-03 19:55:33
    半监督学习(Semi-supervised Learning SSL) 半监督学习是一种有监督学习和无...标签传播算法是基于图的半监督学习方法,基本思路是从已标记的节点的标签信息来预测未标记的节点的标签信息,利用样本间的关系,建...

    目录:
    1. 半监督学习(Semi-supervised Learning SSL)
    2. 完全图
    3. 标签传播算法的基本思路
    4. 标签传播算法
    5. 算法描述
    6. 标签传播算法的基本特点
    7. 代码实现

    1. 半监督学习(Semi-supervised Learning SSL)

    半监督学习是一种有监督学习和无监督学习想结合的一种方法,其主要思想是基于数据分布上的模型假设,利用少量的已标注数据进行指导并预测未标记数据的标记,并合并到标记数据集中去。

    2. 完全图

    在图论的数学领域,完全图是一个简单的无向图,其中每对不同的顶点之间都恰连有一条边相连。完整的有向图又是一个有向图,其中每对不同的顶点通过一对唯一的边缘(每个方向一个)连接。n个端点的完全图有n个端点以及n(n − 1) / 2条边,以Kn表示。它是(k − 1)-正则图。所有完全图都是它本身的团(clique)
    这里写图片描述

    3. 标签传播算法的基本思路

    标签传播算法是基于图的半监督学习方法,基本思路是从已标记的节点的标签信息来预测未标记的节点的标签信息,利用样本间的关系,建立完全图模型。
    每个节点标签按相似度传播给相邻节点,在节点传播的每一步,每个节点根据相邻节点的标签来更新自己的标签,与该节点相似度越大,其相邻节点对其标注的影响权值越大,相似节点的标签越趋于一致,其标签就越容易传播。在标签传播过程中,保持已标记的数据的标签不变,使其将标签传给未标注的数据。最终当迭代结束时,相似节点的概率分布趋于相似,可以划分到一类中。

    4.标签传播算法

    1. ( x 1 , y 1 ) . . . ( x l , y l ) 是 已 标 注 的 数 据 , Y L = { y 1 , . . . y L } ∈ { 1 , . . . , C } (x_1, y_1)...(x_l, y_l)是已标注的数据,Y_L=\lbrace y_1, ... y_L \rbrace\in \lbrace1, ..., C\rbrace (x1,y1)...(xl,yl)YL={y1,...yL}{1,...,C},类别数C已知,且均存在于标签数据中。令 ( x l + 1 , y l + 1 ) . . . ( x l + u , y l + u ) 为 未 标 注 数 据 , 则 Y U = { y l + 1 , . . . , y l + u } 是 没 有 标 签 的 , 通 常 l &lt; &lt; u , 也 就 是 说 有 标 签 的 数 据 的 数 量 远 远 小 于 没 有 标 签 的 数 据 的 数 量 , 让 X = { x 1 , . . , x l + u } ∈ R D , 则 问 题 转 换 为 从 X 和 Y L 中 去 预 测 Y U (x_{l+1},y_{l+1})...(x_{l+u}, y_{l+u})为未标注数据,则Y_U=\lbrace y_{l+1}, ..., y_{l+u} \rbrace 是没有标签的, 通常l&lt;&lt;u,也就是说有标签的数据的数量远远小于没有标签的数据的数量,让X= \lbrace{x_1, .., x_{l+u}} \rbrace\in R^D,则问题转换为从X和Y_L中去预测Y_U (xl+1,yl+1)...(xl+u,yl+u)YU={yl+1,...,yl+u}l<<uX={x1,..,xl+u}RD,XYLYU
    2. 我们想要相邻的数据点具有相同的标签,我们建立一个全连接图,让每一个样本点(有标签的和无标签的)都作为一个节点。用一下权重计算方式来设定两点i,j之间边的权重,所以两点间的距离 d i j d_{ij} dij越小,权重 w i j w_{ij} wij越大。
      w i j = e x p ( − d i j σ 2 ) = e x p ( − ∑ d = 1 D ( x i d − x j d ) σ 2 ) w_{ij} = exp(-{\frac{d_{ij}}{\sigma^2}}) = exp(-{\frac{\sum^D_{d=1}(x_i^d - x_j^d)}{\sigma^2}}) wij=exp(σ2dij)=exp(σ2d=1D(xidxjd))
      然后让每一个带有标签的节点通过边传播到所有的节点,权重大的边的节点更容易影响到相邻的节点。
    3. 我们定义一个(l+u)*(l+u)的概率传播矩阵T,让 T i j T_{ij} Tij为标签j传播到标签i的概率。
      T i j = P ( j → i ) = w i j ∑ k = 1 l + u w k j T_{ij} = P(j\rightarrow i) = \frac{w_{ij}}{\sum_{k=1}^{l+u}w_{kj}} Tij=P(ji)=k=1l+uwkjwij
      同时定义一个(l+u)*C的标签矩阵Y, Y i , C = δ ( y i , C ) Y_{i,C}=\delta(y_i, C) Yi,C=δ(yi,C),它的第i行表示节点 y i y_i yi的标注概率,第C列代表类别。 Y i , C = 1 Y_{i,C}=1 Yi,C=1, 则说明节点 y i y_i yi的标签为C。通过概率传递,使其概率分布集中于给定类别,然后通过边的权重值来传递节点标签。

    5. 算法描述

    input:u个未标记数据和l个标记的数据及其标签
    output:u个未标记数据的标签
    第一步:初始化,利用权重公式来计算每条边的权重 w i j w_{ij} wij,得到数据间的相似度
    第二步:根据得到的权重 w i j w_{ij} wij, 计算节点j到i的传播概率 T i j T_{ij} Tij
    第三步:定义一个(l+u)*C的矩阵
    第四步:每个节点按传播概率把它周围节点传播的标注值按权重相加,并更新到自己的概率分布
    第五步:限定已标注的数据,把已标注的数据的概率分布重新赋值为初始值,然后重复步骤四,直至收敛。

    6. 标签传播算法的基本特点

    (1) LPA是一种半监督学习方法,具有半监督学习算法的两个假设前提:1. 临近样本点具有相同的标签。根据该假设,分类时边界两侧尽可能避免选择较为密集的样本数据点,而是尽量选择稀疏数据,便于算法利用少了已标注数据指导大量的未标注数据。2. 相同流结构上的点能够拥有相同的标签。根据该假设,未标记的样本数据能够让数据空间变得更加密集,便于充分分析局部区域特征。
    (2) LPA只需要利用少量的训练标签指导,利用未标注数据的内在结构,分布规律和临近数据的标记,即可预测和传播未标记数据的标签,然后合并到标记的数据集中。该算法操作简单,运算量小,适合大规模数据信息的挖掘和处理。
    (3) LPA 可以通过相近节点之间的标签的传递来学习分类,所以它不受数据分布形状的局限。所以只要同一类的数据在空间分布上是相似的,那么不管数据分布是什么形状的,都能通过标签传播,把他们分到同一个类里。因此可以处理包括音频、视频、图像及文本的标注,检索及分类。

    7. 代码实现

    import time
    import math
    import numpy as np
    
    
    # return k neighbors index
    def navie_knn(dataSet, query, k):
        numSamples = dataSet.shape[0]
    
        ## step 1: calculate Euclidean distance
        diff = np.tile(query, (numSamples, 1)) - dataSet
        squaredDiff = diff ** 2
        squaredDist = np.sum(squaredDiff, axis=1)  # sum is performed by row
    
        ## step 2: sort the distance
        sortedDistIndices = np.argsort(squaredDist)
        if k > len(sortedDistIndices):
            k = len(sortedDistIndices)
    
        return sortedDistIndices[0:k]
    
    
    # build a big graph (normalized weight matrix)
    def buildGraph(MatX, kernel_type, rbf_sigma=None, knn_num_neighbors=None):
        num_samples = MatX.shape[0]
        affinity_matrix = np.zeros((num_samples, num_samples), np.float32)
        if kernel_type == 'rbf':
            if rbf_sigma == None:
                raise ValueError('You should input a sigma of rbf kernel!')
            for i in range(num_samples):
                row_sum = 0.0
                for j in range(num_samples):
                    diff = MatX[i, :] - MatX[j, :]
                    affinity_matrix[i][j] = np.exp(sum(diff ** 2) / (-2.0 * rbf_sigma ** 2))
                    row_sum += affinity_matrix[i][j]
                affinity_matrix[i][:] /= row_sum
        elif kernel_type == 'knn':
            if knn_num_neighbors == None:
                raise ValueError('You should input a k of knn kernel!')
            for i in range(num_samples):
                k_neighbors = navie_knn(MatX, MatX[i, :], knn_num_neighbors)
                affinity_matrix[i][k_neighbors] = 1.0 / knn_num_neighbors
        else:
            raise NameError('Not support kernel type! You can use knn or rbf!')
    
        return affinity_matrix
    
    
    # label propagation
    def labelPropagation(Mat_Label, Mat_Unlabel, labels, kernel_type='rbf', rbf_sigma=1.5,
                         knn_num_neighbors=10, max_iter=500, tol=1e-3):
        # initialize
        num_label_samples = Mat_Label.shape[0]
        num_unlabel_samples = Mat_Unlabel.shape[0]
        num_samples = num_label_samples + num_unlabel_samples
        labels_list = np.unique(labels)
        num_classes = len(labels_list)
    
        MatX = np.vstack((Mat_Label, Mat_Unlabel))
        clamp_data_label = np.zeros((num_label_samples, num_classes), np.float32)
        for i in range(num_label_samples):
            clamp_data_label[i][labels[i]] = 1.0
    
        label_function = np.zeros((num_samples, num_classes), np.float32)
        label_function[0: num_label_samples] = clamp_data_label
        label_function[num_label_samples: num_samples] = -1
    
        # graph construction
        affinity_matrix = buildGraph(MatX, kernel_type, rbf_sigma, knn_num_neighbors)
    
        # start to propagation
        iter = 0;
        pre_label_function = np.zeros((num_samples, num_classes), np.float32)
        changed = np.abs(pre_label_function - label_function).sum()
        while iter < max_iter and changed > tol:
            if iter % 1 == 0:
                print("---> Iteration %d/%d, changed: %f" % (iter, max_iter, changed))
            pre_label_function = label_function
            iter += 1
    
            # propagation
            label_function = np.dot(affinity_matrix, label_function)
    
            # clamp
            label_function[0: num_label_samples] = clamp_data_label
    
            # check converge
            changed = np.abs(pre_label_function - label_function).sum()
    
        # get terminate label of unlabeled data
        unlabel_data_labels = np.zeros(num_unlabel_samples)
        for i in range(num_unlabel_samples):
            unlabel_data_labels[i] = np.argmax(label_function[i + num_label_samples])
    
        return unlabel_data_labels
    
    
    # 测试代码
    # show
    def show(Mat_Label, labels, Mat_Unlabel, unlabel_data_labels):
        import matplotlib.pyplot as plt
    
        for i in range(Mat_Label.shape[0]):
            if int(labels[i]) == 0:
                plt.plot(Mat_Label[i, 0], Mat_Label[i, 1], 'Dr')
            elif int(labels[i]) == 1:
                plt.plot(Mat_Label[i, 0], Mat_Label[i, 1], 'Db')
            else:
                plt.plot(Mat_Label[i, 0], Mat_Label[i, 1], 'Dy')
    
        for i in range(Mat_Unlabel.shape[0]):
            if int(unlabel_data_labels[i]) == 0:
                plt.plot(Mat_Unlabel[i, 0], Mat_Unlabel[i, 1], 'or')
            elif int(unlabel_data_labels[i]) == 1:
                plt.plot(Mat_Unlabel[i, 0], Mat_Unlabel[i, 1], 'ob')
            else:
                plt.plot(Mat_Unlabel[i, 0], Mat_Unlabel[i, 1], 'oy')
    
        plt.xlabel('X1');
        plt.ylabel('X2')
        plt.xlim(0.0, 12.)
        plt.ylim(0.0, 12.)
        plt.show()
    
    
    def loadCircleData(num_data):
        center = np.array([5.0, 5.0])
        radiu_inner = 2
        radiu_outer = 4
        num_inner = num_data // 3
        num_outer = num_data - num_inner
    
        data = []
        theta = 0.0
        for i in range(num_inner):
            pho = (theta % 360) * math.pi / 180
            tmp = np.zeros(2, np.float32)
            tmp[0] = radiu_inner * math.cos(pho) + np.random.rand(1) + center[0]
            tmp[1] = radiu_inner * math.sin(pho) + np.random.rand(1) + center[1]
            data.append(tmp)
            theta += 2
    
        theta = 0.0
        for i in range(num_outer):
            pho = (theta % 360) * math.pi / 180
            tmp = np.zeros(2, np.float32)
            tmp[0] = radiu_outer * math.cos(pho) + np.random.rand(1) + center[0]
            tmp[1] = radiu_outer * math.sin(pho) + np.random.rand(1) + center[1]
            data.append(tmp)
            theta += 1
    
        Mat_Label = np.zeros((2, 2), np.float32)
        Mat_Label[0] = center + np.array([-radiu_inner + 0.5, 0])
        Mat_Label[1] = center + np.array([-radiu_outer + 0.5, 0])
        labels = [0, 1]
        Mat_Unlabel = np.vstack(data)
        return Mat_Label, labels, Mat_Unlabel
    
    
    def loadBandData(num_unlabel_samples):
        # Mat_Label = np.array([[5.0, 2.], [5.0, 8.0]])
        # labels = [0, 1]
        # Mat_Unlabel = np.array([[5.1, 2.], [5.0, 8.1]])
    
        Mat_Label = np.array([[5.0, 2.], [5.0, 8.0]])
        labels = [0, 1]
        num_dim = Mat_Label.shape[1]
        Mat_Unlabel = np.zeros((num_unlabel_samples, num_dim), np.float32)
        Mat_Unlabel[:num_unlabel_samples / 2, :] = (np.random.rand(num_unlabel_samples / 2, num_dim) - 0.5) * np.array(
            [3, 1]) + Mat_Label[0]
        Mat_Unlabel[num_unlabel_samples / 2: num_unlabel_samples, :] = (np.random.rand(num_unlabel_samples / 2,
                                                                                       num_dim) - 0.5) * np.array([3, 1]) + \
                                                                       Mat_Label[1]
        return Mat_Label, labels, Mat_Unlabel
    
    
    # main function
    if __name__ == "__main__":
        num_unlabel_samples = 800
        # Mat_Label, labels, Mat_Unlabel = loadBandData(num_unlabel_samples)
        Mat_Label, labels, Mat_Unlabel = loadCircleData(num_unlabel_samples)
    
        ## Notice: when use 'rbf' as our kernel, the choice of hyper parameter 'sigma' is very import! It should be
        ## chose according to your dataset, specific the distance of two data points. I think it should ensure that
        ## each point has about 10 knn or w_i,j is large enough. It also influence the speed of converge. So, may be
        ## 'knn' kernel is better!
        # unlabel_data_labels = labelPropagation(Mat_Label, Mat_Unlabel, labels, kernel_type = 'rbf', rbf_sigma = 0.2)
        unlabel_data_labels = labelPropagation(Mat_Label, Mat_Unlabel, labels, kernel_type='knn', knn_num_neighbors=10,
                                               max_iter=1)
        show(Mat_Label, labels, Mat_Unlabel, unlabel_data_labels)
    

    当max_iter=1时
    这里写图片描述
    当max_iter=100时
    这里写图片描述
    当max_iter=200时
    这里写图片描述
    当max_iter=300时
    这里写图片描述
    可以看出,随着迭代次数的增加逐步收敛。

    展开全文
  • 复杂网络中平均节点能量的改进标签传播算法
  • 首先,针对基于模块度最大化的标签传播算法中存在的时间复杂度高的问题,引入传播距离参数,依据“先传播,后合并”的原则,降低了社区合并导致整个网络需要更新带来的较高时间复杂度;其次,结合社区结构的概念提出...
  • Matlab实现的标签传播算法,希望对大家有帮助
  • 用于立体视频中人物识别的无参数标签传播算法
  • 基于标签传播算法的社区发现

    千次阅读 2019-10-28 17:32:27
    社区发现 社区发现是一种广义上的聚类,区别于传统聚类的核心是类别与类别之间可以有重叠部分。在传统的聚类算法,如K-Means,一个元素在结果中...本文介绍一种实现社区发现的算法,标签传播算法标签传播算法 ...
  • 标签传播算法应用于非重叠社区 LPA应用于非重叠社区,也是最基础的标签传播算法。本文只考虑非重叠社区。 SLPA算法 通过Speaker-listener互动的动态过程揭示社交网络中的重叠社区。 我们提出了一个有效的算法使用...
  • 基于标签传播算法(LPA)的社区检测由于其高效性而引起了广泛的关注。 但是,由于算法中标签的传播是随机的,因此难以保证社区检测的准确性。 针对这一问题,本文提出了一种改进的基于随机游走的LPA。 首先,通过...
  • 社区发现算法——标签传播算法LPA

    千次阅读 2016-09-26 14:47:15
    转自:http://blog.csdn.net/cleverlzc/article/details/39494957 标签传播算法(LPA)
  • 识别新的药物靶点作用关系是当前药物研究的关键,在网络标签传播算法的基础上,提出了一种融合异构网络信息的药物靶点预测策略。首先计算药物相似性和靶点相似性,并结合已知的药物靶点作用关系构建异构网络。然后...
  • 基于局部度中心节点的标签传播算法,周勇,夏士雄,社区发现是近年来社会网络中的研究热点。在众多社区发现算法中,标签传播(Label Propagation)算法思想简单且时间复杂度很低,但是该�

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 33,751
精华内容 13,500
关键字:

标签传播算法