社区发现之标签传播算法

一、半监督学习（Semi-supervised Learning, SSL)

机器学习大体可分为三类：监督学习（Supervised Learning, SL）、非监督学习（Unsupervised Learning，USL）及半监督学习（Semi-supervised Learning， SSL）。

监督学习：利用已经标注好的数据样本，训练模型以学习数据的分布，从而对未来没有见到的样本做预测，监督学习的前提是有足够的训练数据。常见监督学习方法如支持向量机、Logistic回归、树模型、贝叶斯分类器等。
非监督学习：所有数据都没有标注，利用所有没有标注的样本来进行类别划分，这一类方法称之为聚类。
半监督学习：是一种有监督学习和无监督学习相结合的一种方法，同时使用标记数据和未标记数据的机器学习方法。其基本思想是基于数据分布上的模型假设，利用少量的已标注数据进行指导并预测未标记数据的标记，并合并到标记数据集中。半监督学习算法包括自训练算法（Self-training）、生成模型（Generative Models）如高斯混合模型（GMM）、半监督支持向量机（Semi-supervised SVMs， S3VM）如Transductive SVM 、图论方法（Graph-based Method）如标签传播算法、多视角算法（Multiview Learning）如协同训练（Co-training）等。

If intelligence was a cake, unsupervised learning would be the cake, supervised learning would be the icing on the cake, and reinforcement learning would be the cherry on the cake. We know how to make the icing and the cherry, but we don’t know how to make the cake.
-Yann LeCun

半监督学习的应用场景：少量的数据带有标记，而大量的数据没有标记。算法主要基于三大假设：

平滑假设（Smoothness）：相似的数据具有相同的Label （怎么定义相似？）；
聚类假设（Cluster）：同一个聚类下的数据具有相同的Label（与上条意思相同？）；
流行假设（Manifold）：同一流行结构下的数据具有相同的Label。

本文主要介绍最简单的半监督学习算法：标签传播算法（Label Propagation）。

二、社会网络的社区挖掘（Community Detection）

在各种基于图的网络中，节点之间存在一些潜在的社区结构，社区结构由一组相似的顶点互相连接而成，同一社区内部之间连接稠密，不同社区时间连接较为稀疏，如社交网络中喜好音乐的用户可以划分为一个社区。社区结构（Community Structure）是复杂网络中的一个普遍特征，网络由多个社区组成。社区挖掘（Community Detection )是一个负责而有意义的过程，其数据描述如下：
设图 $G=G(V,E)$ ，社区发现就是指在图G中确定nc ( $\geq 1$ )个社区：
$C=\{ C_1, C_2, \cdots, C_{nc}\}$
使得个社区的顶点集合构成V的一个覆盖。若任意两个社区的顶点集合交集为空，则称 $C$ 为非重叠社区（Disjoint Communities），否则为重叠社区（Overlapping Communities）

图1. 非重叠社区示例

图2. 重叠社区示例

社区发现算法很多，主要包括以下列表：

算法	年份	算法复杂度
CFinder	2005
LPA	2007	$O(m)$
LFM	2009	$O(n^2)$
EAGLE	2009	$O(n^2s)$
GIS	2009	$O(n^2)$
HANP	2009	$O(m)$
GCE	2010	$O(mh)$
COPRA	2010	$O(vm\log (vm/n))$
NMF	2010	$O(Kn^2)$
Link	2010	$O(nk_{max}^{2})$
SLPA	2011	$O(Tm)$
BMLPA	2012	$O(n\log n))$

三、标签传播算法（Label Propagation Algorithm）

1. 基本思想

标签传播算法（LPA）是基于图的半监督学习算法，基本思路是从已标记的节点标签信息来预测未标记的节点标签信息，利用样本间的关系，建立完全图模型，适用于无向图。
每个节点标签按相似度传播给相邻节点，在节点传播的每一步，每个节点根据相邻节点的标签来更新自己的标签，与该节点相似度越大，其相邻节点对其标注的影响权值越大，相似节点的标签越趋于一致，其标签就越容易传播。在标签传播过程中，保持已标记的数据的标签不变，使其将标签传给未标注的数据。最终当迭代结束时，相似节点的概率分布趋于相似，可以划分到一类中。

2. 算法描述

（1）算法符号介绍
$(x_1, y_1), \cdots, (x_l, y_l)$ ：已标注的数据；
$Y_L=\{y_1,\cdots, y_L\}\in \{1, \cdots, C \}$ ：已标注数据的类别， $C$ 已知，且存在于标签数据中。
$(x_{l+1}, y_{l+1}), \cdots, (x_{l+u}, y_{l+u})$ ：未标注数据；
$Y_U=\{ y_{l+1}, \cdots, y_{l+u}\}$ ：没有标签，满足 $L<<u$ ，即有标签的数据数量远小于没有标签的数据数量。
$X=\{x_1, \cdots, x_{l+u} \} \in R^D$
问题：从 $X$ 和 $Y_L$ 去预测 $Y_U$ 。
（2）全连接图建立：相邻的数据点具有相同的标签，建立一个全连接图，让每一个样本点(有标签的和无标签的)都作为一个节点。用以下权重计算方式来设定两点i, j之间边的权重，所以两点间的距离 $d_{ij}$ 越小，权重 $w_{ij}$ 越大。
$w_{ij}=\exp(-\frac{d_{ij}}{\sigma^2})=\exp(-\frac{\sum_{d=1}^{D}(x_i^d-x_j^d)}{\sigma^2})$
然后让每一个带有标签的节点通过边传播到所有的节点，权重大的边的节点更容易影响到相邻的节点。
（3）定义概率传播矩阵 $T\in (l+u)\times (l+u)$ , 元素 $T_{ij}$ 为标签j传播到标签i的概率。
$T_{ij}=P(j\rightarrow i)=\frac{w_{ij}}{\sum_{k=1}^{l+u}w_{kj}}$
（4) 定义标签矩阵（也称soft label矩阵） $Y\in (l+u)\times C$ ， $Y_{i, C}=\delta(y_i, C)$ ，第i行表示节点 $y_i$ 的标注概率。 $Y_{i, C}=1$ 说明节点 $y_i$ 的标签为C。通过概率传播，使其概率分布集中于给定类别，然后通过边的权重来传递节点标签。
算法流程：

输入： $l$ 个标记的数据及标签， $u$ 个未标记数据；
输出： $u$ 个未标记数据的标签
第1步：初始化，利用权重公式计算每条边的权重 $w_{ij}$ ，得到数据间相似度；
第2步：根据得到的权重 $w_{ij}$ ，计算节点 $j$ 到节点 $i$ 的传播概率 $T_{ij}$ ；
第3步：定义矩阵 $Y\in (l+u)\times C$ ;
第4步：执行传播，每个节点按传播概率将周围节点传播的标注值按权重相加，并更新到自己的概率分布， $Y^{t}=T \times Y^{t-1}$ 。
第5步：重置 $Y$ 中已标记样本的标签，限定已标注的数据，把已标注的数据的概率分布重新赋值为初始值；
第6步：重复步骤4和5，直至 $Y$ 收敛。

步骤5非常关键，因为已标记数据是事先确定的，不能被带跑，每次传播完都得回归本来的标签。

四、标签传播算法的变形

每次迭代都要计算标签矩阵 $Y$ ，但是 $Y_L$ 是已知的，计算用处不大。在步骤5中，还需重设初始值。可以将矩阵 $T$ 做以下划分：
$T=\left[ \begin{array}{cc} T_{LL} & T_{LU} \\ T_{UL} & T_{UU} \\ \end{array} \right]$
只需更新运算：
$Y_U \leftarrow T_{UU}Y_U+P_{UL}Y_L$
迭代至收敛。

五、LPA算法的R及Python实现

1. LPA算法的R实现

R中实现社区发现的包为igraph，算法函数有很多种：

cluster_edge_betweenness;
cluster_fast_greedy;
cluster_label_prop;
cluster_leading_eigen;
cluster_louvain;
cluster_optimal;
cluster_spinglass;
cluster_walktrap
其中cluster_label_prop执行标签传播算法。示例如下：

karate<-make_graph("Zachary")
wc<-cluster_label_prop(karate)
modularity(wc)
membership(wc)
plot(wc, karate)

结果展示如下：

图3. 基于R的社区发现示例

2. LAP算法的Python实现

实现方式：scikit-learn示例

import numpy as np
import matplotlib.pyplot as plt
from sklearn.semi_supervised import label_propagation
from sklearn.datasets import make_circles

# generate ring with inner box
n_samples = 200
X, y = make_circles(n_samples=n_samples, shuffle=False)
outer, inner = 0, 1
labels = np.full(n_samples, -1.)
labels[0] = outer
labels[-1] = inner
# Learn with LabelSpreading
label_spread = label_propagation.LabelSpreading(kernel='rbf', alpha=0.8)
label_spread.fit(X, labels)

# Plot output labels
output_labels = label_spread.transduction_
plt.figure(figsize=(8.5, 4))
plt.subplot(1, 2, 1)
plt.scatter(X[labels == outer, 0], X[labels == outer, 1], color='navy',
            marker='s', lw=0, label="outer labeled", s=10)
plt.scatter(X[labels == inner, 0], X[labels == inner, 1], color='c',
            marker='s', lw=0, label='inner labeled', s=10)
plt.scatter(X[labels == -1, 0], X[labels == -1, 1], color='darkorange',
            marker='.', label='unlabeled')
plt.legend(scatterpoints=1, shadow=False, loc='upper right')
plt.title("Raw data (2 classes=outer and inner)")

plt.subplot(1, 2, 2)
output_label_array = np.asarray(output_labels)
outer_numbers = np.where(output_label_array == outer)[0]
inner_numbers = np.where(output_label_array == inner)[0]
plt.scatter(X[outer_numbers, 0], X[outer_numbers, 1], color='navy',
            marker='s', lw=0, s=10, label="outer learned")
plt.scatter(X[inner_numbers, 0], X[inner_numbers, 1], color='c',
            marker='s', lw=0, s=10, label="inner learned")
plt.legend(scatterpoints=1, shadow=False, loc='upper right')
plt.title("Labels learned with Label Spreading (KNN)")

plt.subplots_adjust(left=0.07, bottom=0.07, right=0.93, top=0.92)
plt.show()

结果展示：

图4. 基于python的标签传播

参考资料

[1] 一起来读西瓜书：第十三章半监督学习: https://www.jianshu.com/p/7d4323c28716;
[2] 半监督学习的一些文章(Semi-supervised): https://www.jianshu.com/p/e0adfd789379;
[3] 社区发现(Community Detection)算法: https://blog.csdn.net/huangxia73/article/details/11801661;
[4] 标签传播算法(Label Propagation Algorithm): https://blog.csdn.net/Katherine_hsr/article/details/82343647;
[5] 标签传播算法（Label Propagation）及Python实现: https://blog.csdn.net/zouxy09/article/details/49105265;
[6] Using R to Detect Communities of Correlated Topics： https://wesslen.github.io/text%20mining/topic-networks/；
[7] igraph, R package: https://igraph.org/r/doc/communities.html;
[8] 1.14. Semi-Supervised: https://scikit-learn.org/stable/modules/label_propagation.html;
[9] Label Propagation learning a complex structure: https://scikit-learn.org/stable/auto_examples/semi_supervised/plot_label_propagation_structure.html#sphx-glr-auto-examples-semi-supervised-plot-label-propagation-structure-py;