标签传播算法解读

  • A+
所属分类:安全闲碎

点击上方“AI公园”,关注公众号,选择加“星标“或“置顶”


作者: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.0001100, [0,1])

未标记节点的标签:

L.argmax(1)

最后的想法

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

标签传播算法解读
END

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

标签传播算法解读

请长按或扫描二维码关注本公众号

喜欢的话,请给我个好看吧标签传播算法解读

本文来源于互联网:标签传播算法解读

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: