一、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模型训练“句子”,得到每个节点的嵌入向量。
通过生成节点的嵌入向量,我们可以将图中节点的低维信息捕捉到。在得到节点的嵌入向量后,可以使用这些向量进行节点分类、社区检测等任务。