去掉数据集中关联性不大和冗余的数据，确保不出现过度适应的前提下降低计算的成本，需要对特征进行无损规约，数学上叫降维。广泛用于模式识别、文本检索以及机器学习领域，主要分为两类，特征提取和特征筛选，前者是高维数据投影到低维空间，后者是特征子集代替锋做原始特征集，包括特征分级和特征筛选，分级是找到优化后的特征子集。
特征提取可以分成线性抽取和非线性抽取两种方法，前者是试图找到一个仿射空间能够最好的说明数据分布的变化，后者对高维非线性曲线平面分布的数据非常有效。
线性特征的抽取方法：
首先设定一些标准，然后挑选出满足标准的特征。
算法首先调用一个权重函数得到每个特征的权重值，权重评价指标是平均精确度下降 importance.type = 1 ，除了上面用的随机森林，还可以使用 chi.squared, information.gain 。
然后获取优化的特征子集，首先5折交叉验证评估特征子集的重要性，爬山搜索算法从原始特征集中选出优化的特征子集，也可以选择其他算法，比如 forward.search 。还可以使用caret包进行特征筛选，据说这个包是个宝呀，包罗万象。
主成分分析是一种应用非常广泛的线性降维方法，适合数据集包含非常多的特征，并且特征间彼此冗余（相关的情况）。通过将特征集缩减成一小部分能代表原始特征集最主要变化的主要特征分量，实现高维数据到低维数据空间的映射。
特征选择过程中会去掉一些彼此关联但有价值的特征，需要在特征制取过程中考虑将这些特征综合到单特征中，PCA采用正交变换将彼此有关行基丛联的特征转化为主成分，以便我们确定方差趋档樱势。
算法主要包括以下步骤：1）找到平均向量的数据点；2）计算
协方差矩阵；3）计算特征向量；4）对特征向量排序并选择前k个特征向量；5）构建特征向量矩阵；最后，将数据样本转换成新的子集。
拓展
princomp 是另一个高不成分分析函数，与上面的 prcomp 采用奇异值分解不同，采用相关矩阵或协方差矩阵的特征值计算方法，一般更习惯用后者。
以上两个函数均来自stats包，还可以使用psych包中的principal函数进行：
Kaiser方法、scree(碎石测试）和依据挑选规则使用解释变量比例都可以。碎石测试的主要目的是将主成分结果以碎石图方式表达，从图中找到引起曲线斜率变化最快的因素。
主成分为2时，斜率变化最快。也可以使用nfactors以并行分析非图形方式作Cattell碎石来测试。
biplot绘制数据与原始特征在前两个主成分上的投影图
biplot绘制数据及原始特征在前两个主成分上的投影，农业高，教育和检查低的省份在PC1上得分高；婴儿死亡率高，农业低的省份在主成分PC2上得分较高。
多维尺度分析通过图形方式展示多个对象之间的相似或相异程度距离），多维是指映射到一维、二维或多维空间表达CF全家人相对距离，一般使用一或二维空间。
分成计量和非计量两类，前者是主要考虑如何保证降维后各对象之间的距离尽可能接近它们在原始空间的距离，后者则假设两个空间中对象的距离排名已知，而且变换后排名不变。
可以通过将投影维度绘制在一个散点图中比较MDS和PCA的差异，如果MDS采用欧氏距离，投影维度将与PCA完全一致。
奇异值分解是矩阵分解的一种形式，可以将一个矩阵分解为两个正交矩阵和一个对角矩阵，原始矩阵可由这三个矩阵相乘得到。可以帮助去掉那些从线性代数角度观察存在线性相关冗余的矩阵，可以应用在特征筛选，图像处理和聚类等。
SVD是一类分解实数或复数矩阵的常见方法，PCA可以被看成SVD的一种特例：
两个矩阵基本相同。
[图片上传失败...(image-be0ae8-1639570485003)]
图像压缩领域应用最为广泛的标准测试图像，花花公子当年的模特图呀！
不知为啥，读什么图片都是负片呢？先继续：
ISOMAP属于流形学习方法，支持线性空间到非线性数据结构的转换，与MDS类似，它也能够以图形方式展现对象之间的相似性或相异性（距离），不过，由于数据采用非线性结构表示，以几何距离代替MDS中有欧氏距离。
ISOMAP是一种等距映射非线性降维方法，如果将计量MDS方法中数据点间成对的欧氏距离替换成邻接图间的测地距离，就可以将ISOMAP当做计量MDS方法的扩展。
算法分为4步：确定邻近点，构建邻接图，计算最短路径和MDS分析找到数据间的低维嵌入。
扩展
可以将RnavGraph包将图形作为数据浏览的基础方式来实现高维数据的可视化。
LLE算法是PCA算法的扩展，通过嵌入高维空间内的流形映射到低维空间来实现数据压缩。ISOMAP是全局性非线性降维，LLE主要是局部母性降维算法，假设每个数据点可以由k个邻近点的母性组合构成，映射后能保持原来的数据性质。
LLE是一种非线性降维算法，基于它我们可以得到高维数据在低维空间保持原有数据邻近嵌入关系的映射。算法主要分成三步：计算每个点的k个邻近，然后计算每个邻近点的权值，使得每个点都能最优地由其邻近点组合重构，即残差和最小。
扩展
还可以选择RDRTollbox包实现非线性降维，支持ISOMAP和LLE算法。
由于平台限制，公式无法显示，更好阅读体验，请访问( http://tianle.me/2017/06/30/SDNE/ )
论文阅读 Structural Deep Network Embedding
本文的PDF版 深层网络结构嵌入
这学期选了非线性电路与系统，最近又在做网络表示的相关研究，特将平时看过比较好的论文写一写，和大家分享一下。
信息网络在现实世界中普遍存在，例如航空公司网络，出版物网络，通信网络和万维网。这些信息网络的规模从几百个节点到数百万和闭兄数十亿个节点不等。大规模信息网络的分析在学术界和工业界引起越来越多的关注。本文研究的是将信息网络嵌入到低维空间的问题，其中每个顶点都表示为一个低维向量。这种低维嵌入在各种应用中非常有用，如可视化，节点分类，链路预测和选择推荐。
网络嵌入目前依旧面临许多挑战。（1） 高维且非线性 ，深层的网络结构特征通常是非线性且高维的。因此，如何去描述学习这种高维非线性的特征是非常具有挑战性的。（2） 结构保持 ，为了能够将结果应用到一些具体的网络分析任务中，网络嵌入方法需要能够将网络结构较好的保存下来，但是隐藏的网络结构是非常复杂并且难以发现的。节点的特性往往依赖于其局部和全局的网络结构。（3） 稀疏性 ，真实世界中的大部分网络都是稀疏的，只能够利用极少数已发现的关系连接，因此还远远不能依此得到满意的效果。
近些年来，许多网络嵌入的方法相继被提出，它们采用了一些浅显的模型，比如说：IsoMAP，Laplacian Eigenmap(LE)，Line。由于这些模型的局限性，它们很难获得网络高维的非线性特征。为了解决这个难题，本文提出了深层模型来学习网络中的节点表示。我们受深度学习的启发，因为其展现出了强大的表示学习能力，能够从复杂的网络中学习特征。它已经在图像、文本、语音等方面取得了卓越的成绩。特别的，我们提出的模型设计了多层的网络结构，这些结构是由许多非线性函数构成，能够将网络数据映射到隐藏的汪态铅非线性空间中，从而挖掘出网络的非线性结构。
为了处理网络结构保存以及稀疏性问题，我们把一阶相似度和二阶相似度相结合，并融于学习过程中。一阶相似度是两个顶点之间的局部点对的邻近度，但由于网络的稀疏性，许多真实存在的边可能缺失，因此，一阶相似度不足以表示网络结构。因此我们更进一步地提出了二阶相似度，一对顶点之间的接近程度表示在网络中其邻域网络结构之间的相似性。通过一阶相似度和二阶相似度，我们可以很好的捕获网络的局部特性与全局特性。为了保证网络的局部和全局特性在我们的模型中有较好的表示，我们提出了困好一种半监督的结构，其中，无监督部分重构了二阶相似度，以保持全局网络结构。而有监督的部分利用一阶相似度作为监督信息来保存网络的全局结构。因此，所学的表示能够很好的保存网络的局部和全局结构。此外，从图1可以看出，在许多网络中二阶相似度邻近点对的数目比一阶相似度多很多。由此可以得到，二阶相似度的引入能够在描述网络结构方面提供更多的信息。因此，我们的方法对稀疏网络是鲁棒的。
[图片上传失败...(image-a552b0-1510922608055)]
图1
算法主要步骤：
算法主要步骤：
在图上随机游走产生长度为$2w + 1$的路径，对每个点随机$\gamma $个随机游走序列。每一条随机游走路径便是相当于一个序列（相当于一句话），这样序列中的点就有上下文，定义一个时间窗口$w$，并进行马尔可夫假设，最后使用word2vec中的Skip-Gram训练每一个节点的向量。
Gram训练每一个节点的向量。
假设一个路径序列为{% raw %}$S = \left{ {{v_1},...,{v_{|S|}}} \right} ${% endraw %},对于${v_i} \in S$，其上下文为{% raw %}$C = \left{ {{v_{i - w}},{v_{i - w + 1}},...,{v_{i + w - 1}},{v_{i + w}}} \right}${% endraw %}, 那么DeepWalk的优化目标为:
{% raw %}$$f = \frac{1}{{\left| S \right|}}\sum\limits_{i = 1}^{\left| S \right|} {\sum\limits_{ - w \le j \le w,j \ne 0} {\log p({v_{i + j}}|{v_i})} } $${% endraw %}
其中：
{% raw %}$$p\left( {{v_j}|{v_i}} \right) = \frac{{exp\left( {c_{{v_j}}^T{r_{{v_i}}}} \right)}}{{\sum\nolimits_{v \in C} {exp\left( {c_{{v_j}}^T{r_{{v_i}}}} \right)} }}$${% endraw %}
{% raw %}${r_{{v_i}}}${% endraw %}是点${v_i}$的向量表征, {% raw %}${c_{{v_i}}}${% endraw %}是点{% raw %}${v_i}${% endraw %}上下文中点${v_j}$的向量表征。
DeepWalk使目标$f$最大化，使用Skip-Gram与Hierarchical Softmax进行训练得到每个点的vector，DeepWalk等价于MF(matrix factorization,矩阵分解)。
定义1（网络） ：给定一个网络{% raw %}$G = \left( {V,E} \right)${% endraw %}，其中{% raw %}$V = { {v_1}, \cdots ,{v_n}} ${% endraw %}表示为n个节点，{% raw %}$E = { {e_{i,j}}} {i,j = 1}^n${% endraw %}表示网络中所有边的集合。每一条边{% raw %}${e {i,j}}${% endraw %}与其网络中边的权重{% raw %}${s_{i,j}} \ge 0${% endraw %}相关联。如果{% raw %}${v_i}${% endraw %}和{% raw %}${v_j}${% endraw %}之间没有连接，那么{% raw %}${s_{i,j}} = 0${% endraw %}，否则，对于无权图{% raw %}${s_{i,j}} = 1${% endraw %}，有权图{% raw %}${s_{i,j}} >0${% endraw %}
网络嵌入的目的是将原始的高维网络数据映射到低维的表示空间中，网络中的每一个节点即可表示为一个低维向量，同时网络计算将会变得非常方便。正如我们之前提到的，网络的局部结构和全局结构都非常有必要在降维后保存下来，下面将详细定义一阶相似度和二阶相似度。
定义2（一阶相似度） ：网络中的一阶相似度是两个顶点之间的局部点对的邻近度。对于由边（u，v）链接的每对顶点，该边的权重${s_{u,v}}$表示u和v之间的一阶相似性，如果在u和v之间没有边，它们的一阶相似度为0。
一阶相似度通常意味着现实世界网络中两个节点的相似性。例如，在社交网络中成为朋友的人往往具有类似的兴趣；在万维网上互相链接的页面往往谈论类似的主题。由于一阶相似度的重要性，许多现有的图嵌入算法，如IsoMap，LLE，Laplacian Eigenmaps目的都是保持一阶相似度。
然而，在现实世界的信息网络中，能够观察到的链接只是小部分，许多隐藏的其他关系都没有被观察到。缺失链路上的一对节点，即使它们在本质上非常相似，然而他们的一阶相似度为0。 因此，只有一阶相似度对维持网络结构来说不是很有效。我们自然而然的想到，具有类似邻居的顶点往往是相似的。 例如，在社交网络中，分享相同内容的人往往具有相似的兴趣，从而成为朋友，在文本网络中，总是与同一组词汇共同出现的词往往具有相似的含义。 因此，我们定义二阶相似度，其补充了一阶相似性并能够保留网络结构。
定义3（二阶相似度） ：二阶相似度对应于网络中的点对（u，v）是其邻域网络结构之间的相似性。数学上，让{% raw %}${{\rm{\mathcal{N}}} u} = { {s {u,1}}, \cdots ,{s_{u,\left| V \right|}}} ${% endraw %}表示一阶附近 u 与所有其他的顶点，那么 u 和v之间的二阶相似性由{% raw %}${{\rm{\mathcal{N}}}_u}$和${{\rm{\mathcal{N}}}_v}${% endraw %}之间的相似性来决定。如果没有一个顶点同时和 u 与 v 链接，那么 u 和 v的二阶相似性是0。
定义4（网络嵌入） ：给定网络{% raw %}$G = \left( {V,E} \right)${% endraw %}，网络嵌入的问题是将每个顶点$v \in V$表示为低维空间{% raw %}${\mathbb{R}^d}${% endraw %}中的向量，学习函数$f:\left| V \right| \mapsto {\mathbb{R}^d}$，其中$d \ll \left| V \right|$。在空间{% raw %}${\mathbb{R}^d}${% endraw %}中，顶点之间的一阶相似度和二阶相似度都被保留。
在本篇文章中，我们提出了一个半监督的网络嵌入深度框架，整体框架如图2所示。具体来说，为了捕捉高维非线性的网络结构，我们提出了一个深层的体系结构，它由多个非线性映射函数组成，将输入数据映射到一个高维非线性的隐藏空间，以捕获网络结构。为了解决网络结构保持和稀疏性问题，我们提出了一个半监督模型来利用一阶和二阶相似度。对于每个顶点，我们都可以得到它的邻域。因此，我们设计了无监督的组件来保持二阶相似度，并重建每个顶点的邻域结构。同时，对节点的一部分，我们可以获得他们的一阶相似度。因此，我们设计了有监督的组件，利用一阶相似度作为监督信息来改进隐藏空间中的表示。通过联合优化所提出的半监督深度模型，SDNE可以保持高维的非线性网络结构，保证稀疏网络的健壮性。在接下来的部分中，我们将详细介绍如何实现半监督的深度模型。
[图片上传失败...(image-4ccde2-1510922608055)]
图2.网络整体结构
我们首先描述无监督组件如何利用二阶近似保持全局网络结构。
二阶相似性值指的是节点的邻居相似，因此模型的二阶相似性，需要每个节点邻居的性质。给定一个网络{% raw %}$G = \left( {V,E} \right)${% endraw %}，我们可以获得到它的邻接矩阵S，它包含了n个元素${s_1}, \cdots {s_n}$，对于每一个元素{% raw %}${s_i} = { {s_{i,j}}} {j = 1}^n${% endraw %}，如果${v_i}$与${v_j}$间有相连的边，那么{% raw %}${s {i,j}} >0${% endraw %}。因此，${s_i}$描述了节点${v_i}$的邻居结构，$S$提供了每一个节点的邻居结构信息。对于$S$来说，我们将传统的深度自编码器的进行延伸，用来保存网络的二阶相似性。
下面简单回顾一下深度自编码器的主要思想。它属于一种非监督模型，包含编码器与解码器。编码器由许多非线性函数构成，将输入数据映射到表示空间。对应的，解码器也由许多非线性函数构成，它将表示空间映射到输入数据的重构空间。给定输入数据${x_i}$，其中对于各个层的隐藏表示如下公式进行计算：
{% raw %}$$y_i^{(1)} = \sigma ({W^{(1)}}{x_i} + {b^{(1)}})$${% endraw %}
{% raw %}$$y_i^{(k)} = \sigma ({W {(k)}}y_i {(k - 1)} + {b^{(k)}}),k = 2, \cdots ,K$${% endraw %}
通过一系列编码器的计算，我们可以获得输出${\hat x_i}$。自动编码器的目标是尽量减少输入和输出的重构误差。损失函数可以表示为：
{% raw %}$${\rm{\mathcal{L}}} = \sum\limits_{i = 1}^n {\left| {{{\hat x} i} - {x_i}} \right| 2^2} $${% endraw %}
通过最小化损失函数能够较好的还原输入数据的原始表达，其表示空间能够提取出原始输入数据的特征。基于上述特性，我们将网络的邻接矩阵S作为自动编码器的输入，如： ${x_i} = {s_i}$，那么每一个元素${s_i}$表示节点${v_i}$邻居节点的特征。因此，通过重构可以让具有相似邻居结构的节点在隐藏的表示空间也具有相似的表达。
但是，仅仅通过这种方式还不能直接解决问题。因为在网络中，我们可以观察到一些连接，但是也有一些合法的连接是缺失的。此外，由于网络的稀疏性，在邻接矩阵$S$中，零元素远远大于非零元素。如果我们直接将S输入到传统的自编码器中，可能会导致大量的零元素出现在重构空间，这并不是我们想要的结果。为了解决这个问题，我们让其对非零元素的重构误差比零元素的惩罚更大。改进的目标函数如下所示：
{% raw %}$$\begin{array}{l}{{\rm{\mathcal{L}}} {2nd}} = \sum\limits{i = 1}^n {\left| {({{\hat x} i} - {x_i}) \odot {b_i}} \right| 2^2} \{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} = \left| {(\hat X - X) \odot B} \right| F^2\end{array}$${% endraw %}
其中$ \odot $表示Hadamard积，{% raw %}${b_i} = { {b {i,j}}} {j = 1}^n${% endraw %}，如果{% raw %}${s {i,j}} = 0${% endraw %}，那么{% raw %}${b{i,j}} = 1${% endraw %}，否则${b{i,j}} = \beta >1$。通过这种改进的损失函数，可以更好的让具有相似邻居的点在获得的表示空间也相似。换句话说，这个非监督部分能够很好的保存网络的二阶相似度。
不仅要维持全局网络结构，而且要捕获局部结构。我们使用一阶相似度表示网络局部结构。一阶相似度可以作为监督信息来约束一对顶点在隐藏表示空间的相似性。因此，我们设计了监督部分来利用一阶相似度。损失函数如下所示：
{% raw %}$$\begin{array}{l}{{\rm{\mathcal{L}}} {1nd}} = \sum\limits {i = 1}^n {{s_{i,j}}\left| {y_i^{(K)} - y_j^{(K)}} \right| 2^2} \{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} = \sum\limits {i = 1}^n {{s_{i,j}}\left| {{y_i} - {y_j}} \right| 2^2} \end{array}$${% endraw %}
其中{% raw %}${Y^{(k)}} = { y_i^{(k)}} {i = 1}^n${% endraw %}为编码器获得的隐藏表示空间。
该公式的灵感来源于拉普拉斯特征映射(Laplacian Eigenmaps)，在表示空间中，如果相似的节点相距较远，那么会受到一个较大的惩罚。通过这一 *** 作，我们的模型能够很好的保持网络的一阶相似度。
我们同时考虑网络的一阶相似度和二阶相似度，另外在加上L2正则项，共同构成了自动编码器的损失函数：
{% raw %}$$\begin{array}{l}{{\rm{\mathcal{L}}} {mix}} = {{\rm{\mathcal{L}}}{2nd}} + \alpha {{\rm{\mathcal{L}}} {1nd}} + \upsilon {{\rm{\mathcal{L}}} {reg}}\{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} = \left| {(\hat X - X) \odot B} \right| F^2 + \alpha \sum\limits {i = 1}^n {{s_{i,j}}\left| {{y_i} - {y_j}} \right| 2^2} + \upsilon {{\rm{\mathcal{L}}} {reg}}\end{array}$${% endraw %}
其中：
{% raw %}$$\begin{array}{l}{{\rm{\mathcal{L}}} {mix}} = {{\rm{\mathcal{L}}} {2nd}} + \alpha {{\rm{\mathcal{L}}} {1nd}} + \upsilon {{\rm{\mathcal{L}}} {reg}}\{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} = \left| {(\hat X - X) \odot B} \right| F^2 + \alpha \sum\limits {i = 1}^n {{s_{i,j}}\left| {{y_i} - {y_j}} \right| 2^2} + \upsilon {{\rm{\mathcal{L}}} {reg}}\end{array}$${% endraw %}
为了能够全面地评价算法得到的低维表示，我们使用了5个真实的网络数据，包括3个社交网络，1个引文网络，1个语言网络；实验了2类网络应用任务，包括多标签分类和可视化。考虑到各个网络数据的本身属性，对于每一类应用，我们使用了至少一个数据集进行试验。数据集的参数如下表所示：
表1. 网络数据集参数
我们实验与以下几个基准算法进行比较：DeepWalk、LINE、GraRep、Laplacian Eigenmaps、Common Neighbor。
对于多标签分类问题，我们采用micro-F1和macro-F1指标进行评价。对于标签A，我们将TP（A），FP（A）和FN（A）分别表示为属于A的样本被正确分类到A的数目，不属于A的样本被错误分类到A的数目和不属于A的样本被正确分类到了类别A的其他类的数目。假设 是整个标签集。Micro-F1和Macro-F1定义如下：
Macro-F1是一个每个类的权重的度量。 定义如下：
{% raw %}$$Macro - F1 = \frac{{\sum\nolimits_{A \in {\rm{\mathcal{C}}}} {F1(A)} }}{{\left| {\rm{\mathcal{C}}} \right|}}$${% endraw %}
其中F1(A)是标签A的F1度量。
Micro-F1是对每个实例权重的度量。定义如下：
{% raw %}$$\Pr = \frac{{\sum\nolimits_{A \in {\rm{\mathcal{C}}}} {TP(A)} }}{{\sum\nolimits_{A \in {\rm{\mathcal{C}}}} {(TP(A) + FP(A))} }}$${% endraw %}
{% raw %}$$R = \frac{{\sum\nolimits_{A \in {\rm{\mathcal{C}}}} {TP(A)} }}{{\sum\nolimits_{A \in {\rm{\mathcal{C}}}} {(TP(A) + FN(A))} }}$${% endraw %}
{% raw %}$$Micro - F1 = \frac{{2*\Pr *R}}{{\Pr + R}}$${% endraw %}
我们在本文中提出了一种多层的神经网络结构，层数随不同的数据集而做相应调整。每层的神经元数目如表2所示。其中BLOGCATALOG，ARXIV GR-QC和20-EWSGROUP使用了三层神经网络，FLICKR和YOUTUBE使用了四层。如果我们使用更深的模型，性能几乎保持不变，甚至变得更糟。
表2. 神经网络结构
对于我们的方法，通过在验证集上使用网格搜索(grid search)来调整 ， 和 三个超参数。对于LINE，随机梯度下降的mini-batch大小设置为1。学习速率的初始值为0.025。负采样数(number of negative samples)为5，总采样数(the total number of samples)设为100亿。对于DeepWalk，我们将窗口大小设置为10，步长为40，每次采样40个顶点。对于GraRep，我们将最大转移矩阵步长(maximum matrix transition step)设置为5。
我们通过本实验中的多标签分类任务来评估不同网络表示的有效性。顶点的表示是从网络嵌入方法生成的，并被用作将每个顶点分成一组标签的特征。具体来说，我们采用LIBLINEAR软件包来训练分类器。训练分类器时，我们随机抽取标签节点的一部分作为训练数据，其余作为测试。对于BLOGCATALOG，我们随机抽取10％至90％的顶点作为训练样本，并使用剩余顶点来测试性能。对于FLICKR和YOUTUBE，我们随机抽取1％至10％的顶点作为训练样本，并使用剩余顶点来测试性能。另外，我们删除没有在YOUTUBE中被任何类别标记的顶点。我们重复进行5次实验，取Micro-F1和Macro-F1指标的平均值进行度量。结果分别如图3到图5所示。
[图片上传失败...(image-8c4a6-1510922608055)]
图3 .Micro-F1和Macro-F1在BLOGCATALOG上的表现
[图片上传失败...(image-953fed-1510922608055)]
图4 .Micro-F1和Macro-F1在FLICKR上的表现
[图片上传失败...(image-bce93a-1510922608055)]
图5 .Micro-F1和Macro-F1在YOUTUBE上的表现
在图3到图5中，我们算法的曲线一直高于其他基准算法的曲线。它表明，在多标签分类任务中我们算法学习得到的网络表示比其他算法得到的效果更好。
在图3（BLOGCATALOG）中，当训练百分比从60％下降到10％时，我们的方法在基准线上的改善幅度更为明显。它表明当标签数据有限时，我们的方法可以比基准算法有更显着的改进。这样的优势对于现实世界的应用尤其重要，因为标记的数据通常很少。
在大多数情况下，DeepWalk的性能是网络嵌入方法中最差的。原因有两个方面。首先，DeepWalk没有明确的目标函数来捕获网络结构。其次，DeepWalk使用随机游走来获得顶点的邻居，由于随机性而引起了很多噪音，特别是对于度数高的顶点。
网络嵌入的另一个重要应用是在二维空间上生成网络的可视化。对此我们在20-NEWSGROUP网络进行可视化的实验。我们使用不同网络嵌入方法学习的低维网络表示作为可视化工具t-SNE的输入。因此，每个新闻组文档被映射为二维向量。然后我们可以将每个向量可视化为二维空间上的一个点。对于被标记为不同类别的文档，我们在对应的点上使用不同的颜色。因此，良好的可视化结果能让相同颜色的点彼此靠近。可视化结果如图6所示。
[图片上传失败...(image-b52fc7-1510922608055)]
图6. 20-NEWSGROUP的可视化
每个点表示一个文档。点的颜色表示文档的类别。蓝色表示rec.sport.baseball的主题，红色表示comp.graphics的主题，绿色表示talk.politics.guns的主题。
从图7可以看出，LE和DeepWalk的结果并不理想，属于不同类别的点相互混合。对于LINE，形成不同类别的群集。然而，在中心部分，不同类别的文件仍然相互混合。对于GraRep，结果看起来更好，因为相同颜色的点分割成分组，但是，每个群体的边界不是很清楚。显然，SDNE的可视化效果在群体分离和边界方面都表现最好。
在本文中，我们提出了一种深层网络结构嵌入，即SDNE来执行网络嵌入。具体来说，为了捕获高维非线性的网络结构，我们设计了一个具有多层非线性函数的半监督深度模型。为了进一步解决网络结构保持和稀疏问题，我们同时使用了一阶邻近度和二阶邻近度来表示网络的局部和全局特征。通过在半监督的深度模型中优化它们，所学习的表示能够体现出网络的局部和全局特征，并且对稀疏网络是鲁棒的。我们在真实的网络数据集上试验了多标签分类和可视化任务。结果表明，我们的算法与当前最好的算法(state-of-the-art)相比有本质性的提高。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）