您的位置:

DeepWalk算法详解

一、DeepWalk算法缺点

DeepWalk算法是一种用于图嵌入的无监督学习算法,它在学习图的低维表示方面表现出色。然而,它也有一些缺点:

1、DeepWalk算法基于随机游走,对于大图,这个方法可能会带来较高的计算复杂度。

2、DeepWalk算法依赖于节点的邻居关系,在节点之间存在高度长距离的图上时,DeepWalk效果可能不佳。

3、DeepWalk算法不能捕获节点的全局结构信息。

二、DeepWalk算法详解刘建平

DeepWalk算法是由加拿大蒙特利尔大学的Jian Tang等人在2015年提出的一种无监督学习算法。它通过把每个节点看做一个词,将图转换成一个句子,然后通过Word2Vec模型学习每个节点的低维表示。

DeepWalk算法之所以能够有效地学习节点的低维表示,是因为它利用了本质上与自然语言处理相同的思路:图是一种高维数据,很难直接处理,但是可以将其映射到低维空间中,这样可以更好地进行处理。

其中,DeepWalk算法的核心是随机游走过程。该过程从某个节点开始,依次按照一定的策略,选择这个节点的邻居节点进行移动,最终形成一个游走路径。重复执行该过程,就可以得到一系列游走路径,这些路径就是DeepWalk算法中的“句子”。Word2Vec对“句子”进行学习,得到每个节点的低维表示。

三、DeepWalk算法的用处

DeepWalk算法可以帮助应用程序中节点之间的相似性计算、节点分类、社区检测等领域。因为在图中,通常节点之间的相似性是由它们在图上的结构相似性决定的,而DeepWalk算法可以有效地捕捉这种结构信息。

可以利用DeepWalk算法帮助数据挖掘的应用:对于大规模的有标签和无标签网络数据集,DeepWalk通过将节点映射到低维向量空间,形成对节点的嵌入表示,弥补了浅层方法的局限性并成功将节点嵌入进向量空间。

可以利用嵌入向量在下游机器学习任务,例如节点分类、边预测、社区发现、数据可视化、相似性计算等等。

四、DeepWalk算法谱聚类

DeepWalk算法可以利用得到的节点嵌入向量进行谱聚类。谱聚类是一种标准的无监督分类技术,可以将相似的数据划分成同一组。

谱聚类之所以能够在各种分类问题中表现良好,是因为它能够有效地从数据的内在特征中提取信息。相似特征具有相似的嵌入向量,因此可以通过谱聚类将节点分组。

#deepwalk谱聚类代码示例
import networkx as nx
from gensim.models.word2vec import Word2Vec
from sklearn.cluster import KMeans
from sklearn.decomposition import PCA
from sklearn.mixture import GaussianMixture

graph=nx.read_edgelist("email-Eu-core.txt",nodetype=int)
walks=[]
for node in graph.nodes():
    for i in range(5):
        walk=nx.random_walk(graph, [node], length=20)
        walks.append([str(node) for node in walk])
model=Word2Vec(walks,size=128,window=10,min_count=0,sg=1,workers=8)
embeddings=model.wv
X=list(embeddings.values())
km=KMeans(n_clusters=42,n_init=20,tol=1e-12)
km.fit(X)

gmm=GaussianMixture(n_components=42, covariance_type='diag',tol=1e-8,min_covar=1e-8)
gmm.fit(X)

pca=PCA(n_components=2)
pca.fit(X)
reduced_X=pca.fit_transform(X)

五、DeepWalk算法以及实现

DeepWalk算法的核心是对图进行随机游走,得到游走序列,然后使用Skip-gram模型训练节点的嵌入向量。下面是DeepWalk算法的实现步骤:

1、构造图的邻接矩阵。

2、利用任意节点开始的随机游走算法,生成一系列游走路径,称为“句子”。

3、利用Word2Vec模型,对“句子”进行学习,得到每个节点的低维表示,即嵌入向量。

在Python中,可以使用Gensim库提供的Word2Vec函数实现DeepWalk算法。下面是DeepWalk算法的实现代码:

#DeepWalk算法代码示例
from gensim.models import Word2Vec
from gensim.models.word2vec import LineSentence
from sklearn.neighbors import NearestNeighbors
import networkx as nx

#加载图
G=nx.read_edgelist("email-Eu-core.txt", nodetype=int)

#生成游走路径
sentences=[]
num_walks=10 
walk_length=80 
for _ in range(num_walks):              
    for node in G.nodes():
        sentence=[node]
        for _ in range(walk_length-1):
            neighbors=list(G.neighbors(sentence[-1]))
            sentence.append(np.random.choice(neighbors))
        sentences.append([str(i) for i in sentence])
            
#训练Word2Vec模型
model=Word2Vec(sentences, size=128, window=5, min_count=0, sg=1, iter=1)

#保存节点的嵌入向量
embeddings={}
for node in G.nodes():
    embeddings[node]=model.wv[str(node)]

#寻找最近的节点
knn=NearestNeighbors(n_neighbors=10)
knn.fit(embeddings.values())
print(knn.kneighbors([embeddings[0]])[1])

六、DeepWalk算法基本原理

DeepWalk算法通过将图转化为文本序列,然后利用Word2Vec模型学习每个节点的嵌入向量。下面是DeepWalk算法的基本原理:

1、生成节点邻接矩阵A。

2、从一个初始节点开始,按照随机游走策略,不断移动到与它邻接的节点。

3、重复上面的步骤生成多个游走路径,这些路径就是DeepWalk算法中的“句子”。

4、利用Word2Vec模型训练“句子”,得到每个节点的嵌入向量。

通过生成节点的嵌入向量,我们可以将图中节点的低维信息捕捉到。在得到节点的嵌入向量后,可以使用这些向量进行节点分类、社区检测等任务。