Deepwalk,deepwalk python

　　什么是网络嵌入？网络中的点用一个低维向量来表示，这些向量应该能够反映原网络的一些特征。

　　一种网络嵌入方法叫做DeepWalk。它的输入是图形或网络，输出是网络中顶点的矢量表示。DeepWalk通过截断随机游走(截断随机行走)学习一个网络的社会表示(社会表征)，即使在网络中顶点很少的情况下也能得到较好的结果。此外，该方法具有可扩展性，能够适应网络的变化。

　　学习社交表象适应性，网络表象一定要能适应网络的变化。网络是一个动态图，会不断增加新的节点和边。网络表示需要适应网络的正常演进。

　　属于同一个社区的节点有着类似的表示。在网络中，经常会出现一些具有相似特征的点的簇，这些节点用向量表示后一定是相似的。

　　低维。代表每个顶点的向量维数不能太高，会导致过拟合的风险，处理网络中缺失数据的能力较差。

　　连续性。低维向量应该是连续的。

　　网络嵌入：网络中的节点用向量表示。

　　网络表示中的节点序列是随机游走的。

　　嵌入图形嵌入图形是解决图形分析问题的有效方法。它将图形数据转换成低维空间，其中最大程度地保留了图形结构信息和图形属性。嵌入节点的目的是将节点编码成低维向量，并总结其图形位置及其局部图域的结构。这些低维嵌入可以被视为将节点编码或投影到潜在空间中，其中潜在空间中的几何关系对应于原始图中的交互(例如，边)。

　　空间中嵌入的节点之间的距离反映了原始图中节点的相似性，空间中嵌入的节点根据不同颜色编码的社区进行聚类。

　　图嵌入技术以低维稠密向量的形式表示图中的节点，要求原图中相似的节点(不同的方法对相似度的定义不同)在低维表达空间中也是接近的。获得的表达向量可用于下游任务，如节点分类、链接预测、原始图的可视化或重建等。

　　随机行走所谓随机游走（random walk ）是指在网络上反复随机选择一条行走路径，最终形成一条贯穿网络的路径。从特定的终点开始，遍历的每一步随机选择由当前节点连接的一条边，沿着选定的边移动到下一个固定点，并重复此过程。截断随机行走实际上是一种固定长度的随机行走。

　　随机漫步的好处：并行化，随机漫步是局部的。对于大型网络，可以在不同的顶点同时开始一定长度的随机行走，同时进行多次随机行走，可以减少采样时间。适应性，能适应网络的局部变化。网络的演化通常是局部点和边的变化，只会影响一些随机行走路径。因此，在网络的演化过程中，没有必要每次都重新计算整个网络的随机游走。$Pr(viv0，v1，…，vi-1)) $

　　也就是要优化的目标，也就是说：当(v0，v1，v1) (v0，v1，v1}) (v0，v1，v1)是已知的，那么要迁移的下一个节点是v1 _ v1。

　　因为顶点本身是无法计算的，所以需要引入一个映射函数，将顶点映射成向量，这样就可以计算了。

　　Alothm的整个DeepWalk算法由两部分组成，一部分是随机漫步的生成，另一部分是参数的更新。

　　第二步建立分层Softmax，第三步对每个节点做次随机游走，第四步打乱网络中的节点，第五步以每个节点为根节点生成长度为t的随机游走，第七步利用skip-gram模型根据生成的随机游走用梯度法更新参数。

　　Word2vec Word2vec由Tomas Mikolov于2013年提出，其核心思想是* *在其上下文中描述一个词。* *从这个想法出发，有两种不同的模式：

　　CBOW:给定中心词的上下文预测Skip-Gram:给定一个中心词来预测其上下文，一个语料库可以由多个文档组成。为简单起见，假设语料库可以表示为一个序列C={w 1，w 2，…，w N}，语料库的长度为N，单词的词汇量为v，w I v，Skip-gram模型利用中心词来预测其上下文单词。这里，上下文词被定义为以中心词为中心的窗口中的词，假设窗口大小为2m 1。给定中心词，要能正确预测上下文词，就是希望在给定中心词的情况下，输出词是上下文的概率最高。

　　以图4-5所示的一句话为例。选择m=2，考察中心词“网络”。它的语境是{图形、神经、你和非常}。我们可以构造这样一个词对[(图形，网络)，(神经，网络]。

　　为了根据中心词正确预测上下文词，可以最大化词对在样本中作为上下文出现的概率，最小化词对在负样本中作为上下文出现的概率，从而构造目标函数。具体来说，正负样本的标签定义如下：其中w c w_c wc代表头词。

　　这个问题转化为一个二元分类问题。给定任意两个词，判断它们是否是上下文。因此，可以使用逻辑回归对这个问题进行建模。介绍了r { d d}中的两个矩阵u r d d，v r d d u \和r { d d} u 中的v \U，V U，V U，V分别对应一个词，作为中心词和上下文词的不同表达。

　　对于一个单词W，定义U w U_w Uw表示其对应的单词向量，然后将公式(4.17)中的概率表示为公式(4.18)，其中(x)\(x)(x)表示sigmoid函数：

　　这个公式一方面是增大正样本的概率，另一方面是减小负样本的概率。我们注意到增加正样本的概率实际上在增加。

　　U c v w u _ {w _ c} v _ w uwc vw，即中心词和上下文词的内积，即两者的相似度。也就是说，最小化公式(4.19)实际上会使中心词与上下文词的距离变小，但中心词与非上下文词的距离变大。这样，它就作为一个监督信号来指导模型学习。收敛后，参数矩阵U和V就是我们需要的字向量。通常我们用U作为最终的词向量。

　　为了减少计算量，构造了哈弗曼树，将原来的复杂度从 v v v降低到 l o g V logV logV.

　　哈弗曼的树结构思想：将词典中的每个词按照词频大小构建出一棵Huffman树，保证词频较大的词处于相对比较浅的层，词频较低的词相应的处于Huffman树较深层的叶子节点，每一个词都处于这棵Huffman树上的某个叶子节点。

　　哈弗曼树构建是根据是否是为正负样本 左子树为正样本，右子树为负样本。即问题变成了二分类问题。

　　注：判断两个词是否相关，计算其关联的概率。将中心词输入到第0层，根据输入中心词的向量和上下文词的向量进行计算。首先根据原始训练集中的标签判断是否相关，如果是，则为正样本，取左子树。如果不是，就是阴性样本。取右边的子树。词频较高的词放在中间节点，词频越高越浅。因此。当输入的两个词没有上下文关系时，取负样本。此时，再次检查路径中的第一级节点是否与所需的上下文单词相关，以此类推。直到路径到达上下V w V_w Vw节点(最终目标节点)。将经过的节点带入概率公式(4.19)进行计算，求给定两个词的相关概率。

　　花了三天时间才最终搞清楚算法，文章中难免有一些问题和错误。如有疏漏，望各位批评指出。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。