社區(qū)發(fā)現(xiàn)之標簽傳播算法

一、半監(jiān)督學(xué)習(xí)（Semi-supervised Learning, SSL)

機器學(xué)習(xí)大體可分為三類：監(jiān)督學(xué)習(xí)（Supervised Learning, SL）、非監(jiān)督學(xué)習(xí)（Unsupervised Learning，USL）及半監(jiān)督學(xué)習(xí) （Semi-supervised Learning币绩， SSL）拉宗。

監(jiān)督學(xué)習(xí)：利用已經(jīng)標注好的數(shù)據(jù)樣本咖祭，訓(xùn)練模型以學(xué)習(xí)數(shù)據(jù)的分布，從而對未來沒有見到的樣本做預(yù)測砾赔，監(jiān)督學(xué)習(xí)的前提是有足夠的訓(xùn)練數(shù)據(jù)蝌箍。常見監(jiān)督學(xué)習(xí)方法如支持向量機、Logistic回歸暴心、樹模型妓盲、貝葉斯分類器等。
非監(jiān)督學(xué)習(xí)：所有數(shù)據(jù)都沒有標注专普，利用所有沒有標注的樣本來進行類別劃分悯衬，這一類方法稱之為聚類。
半監(jiān)督學(xué)習(xí)：是一種有監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)相結(jié)合的一種方法檀夹，同時使用標記數(shù)據(jù)和未標記數(shù)據(jù)的機器學(xué)習(xí)方法筋粗。其基本思想是基于數(shù)據(jù)分布上的模型假設(shè)，利用少量的已標注數(shù)據(jù)進行指導(dǎo)并預(yù)測未標記數(shù)據(jù)的標記炸渡，并合并到標記數(shù)據(jù)集中娜亿。半監(jiān)督學(xué)習(xí)算法包括自訓(xùn)練算法（Self-training）、生成模型（Generative Models）如高斯混合模型（GMM）蚌堵、半監(jiān)督支持向量機（Semi-supervised SVMs买决， S3VM）如Transductive SVM 、圖論方法（Graph-based Method）如標簽傳播算法吼畏、多視角算法（Multiview Learning）如協(xié)同訓(xùn)練（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

半監(jiān)督學(xué)習(xí)的應(yīng)用場景：少量的數(shù)據(jù)帶有標記，而大量的數(shù)據(jù)沒有標記宫仗。算法主要基于三大假設(shè)：

平滑假設(shè)（Smoothness）：相似的數(shù)據(jù)具有相同的Label （怎么定義相似够挂？）；
聚類假設(shè)（Cluster）：同一個聚類下的數(shù)據(jù)具有相同的Label（與上條意思相同藕夫？）孽糖；
流行假設(shè)（Manifold）：同一流行結(jié)構(gòu)下的數(shù)據(jù)具有相同的Label。

本文主要介紹最簡單的半監(jiān)督學(xué)習(xí)算法：標簽傳播算法（Label Propagation）毅贮。

二办悟、社會網(wǎng)絡(luò)的社區(qū)挖掘（Community Detection）

在各種基于圖的網(wǎng)絡(luò)中，節(jié)點之間存在一些潛在的社區(qū)結(jié)構(gòu)滩褥，社區(qū)結(jié)構(gòu)由一組相似的頂點互相連接而成病蛉，同一社區(qū)內(nèi)部之間連接稠密，不同社區(qū)時間連接較為稀疏，如社交網(wǎng)絡(luò)中喜好音樂的用戶可以劃分為一個社區(qū)铺然。社區(qū)結(jié)構(gòu)（Community Structure）是復(fù)雜網(wǎng)絡(luò)中的一個普遍特征俗孝，網(wǎng)絡(luò)由多個社區(qū)組成。社區(qū)挖掘（Community Detection )是一個負責(zé)而有意義的過程魄健，其數(shù)據(jù)描述如下：
設(shè)圖 $G=G(V,E)$ 赋铝，社區(qū)發(fā)現(xiàn)就是指在圖G中確定nc ( $\geq 1$ )個社區(qū)：
$C=\{ C_1, C_2, \cdots, C_{nc}\}$
使得個社區(qū)的頂點集合構(gòu)成V的一個覆蓋。若任意兩個社區(qū)的頂點集合交集為空沽瘦，則稱 $C$ 為非重疊社區(qū)（Disjoint Communities）革骨，否則為重疊社區(qū)（Overlapping Communities）

圖1. 非重疊社區(qū)示例

圖2. 重疊社區(qū)示例

社區(qū)發(fā)現(xiàn)算法很多，主要包括以下列表：

算法	年份	算法復(fù)雜度
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）是基于圖的半監(jiān)督學(xué)習(xí)算法良哲，基本思路是從已標記的節(jié)點標簽信息來預(yù)測未標記的節(jié)點標簽信息，利用樣本間的關(guān)系助隧，建立完全圖模型筑凫，適用于無向圖。
每個節(jié)點標簽按相似度傳播給相鄰節(jié)點喇颁，在節(jié)點傳播的每一步，每個節(jié)點根據(jù)相鄰節(jié)點的標簽來更新自己的標簽嚎货，與該節(jié)點相似度越大橘霎，其相鄰節(jié)點對其標注的影響權(quán)值越大，相似節(jié)點的標簽越趨于一致殖属，其標簽就越容易傳播姐叁。在標簽傳播過程中，保持已標記的數(shù)據(jù)的標簽不變洗显，使其將標簽傳給未標注的數(shù)據(jù)外潜。最終當?shù)Y(jié)束時，相似節(jié)點的概率分布趨于相似挠唆，可以劃分到一類中处窥。

2. 算法描述

（1）算法符號介紹
$(x_1, y_1), \cdots, (x_l, y_l)$ ：已標注的數(shù)據(jù)；
$Y_L=\{y_1,\cdots, y_L\}\in \{1, \cdots, C \}$ ：已標注數(shù)據(jù)的類別玄组， $C$ 已知滔驾，且存在于標簽數(shù)據(jù)中。
$(x_{l+1}, y_{l+1}), \cdots, (x_{l+u}, y_{l+u})$ ：未標注數(shù)據(jù)俄讹；
$Y_U=\{ y_{l+1}, \cdots, y_{l+u}\}$ ：沒有標簽哆致，滿足 $L<<u$ ，即有標簽的數(shù)據(jù)數(shù)量遠小于沒有標簽的數(shù)據(jù)數(shù)量患膛。
$X=\{x_1, \cdots, x_{l+u} \} \in R^D$
問題：從 $X$ 和 $Y_L$ 去預(yù)測 $Y_U$ 摊阀。
（2）全連接圖建立：相鄰的數(shù)據(jù)點具有相同的標簽，建立一個全連接圖，讓每一個樣本點(有標簽的和無標簽的)都作為一個節(jié)點胞此。用以下權(quán)重計算方式來設(shè)定兩點i, j之間邊的權(quán)重臣咖，所以兩點間的距離 $d_{ij}$ 越小，權(quán)重 $w_{ij}$ 越大豌鹤。
$w_{ij}=\exp(-\frac{d_{ij}}{\sigma^2})=\exp(-\frac{\sum_{d=1}^{D}(x_i^d-x_j^d)}{\sigma^2})$
然后讓每一個帶有標簽的節(jié)點通過邊傳播到所有的節(jié)點亡哄，權(quán)重大的邊的節(jié)點更容易影響到相鄰的節(jié)點。
（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行表示節(jié)點 $y_i$ 的標注概率灵临。 $Y_{i, C}=1$ 說明節(jié)點 $y_i$ 的標簽為C截型。通過概率傳播，使其概率分布集中于給定類別儒溉，然后通過邊的權(quán)重來傳遞節(jié)點標簽宦焦。
算法流程：

輸入： $l$ 個標記的數(shù)據(jù)及標簽， $u$ 個未標記數(shù)據(jù)顿涣；
輸出： $u$ 個未標記數(shù)據(jù)的標簽
第1步：初始化波闹，利用權(quán)重公式計算每條邊的權(quán)重 $w_{ij}$ ，得到數(shù)據(jù)間相似度涛碑；
第2步：根據(jù)得到的權(quán)重 $w_{ij}$ 精堕，計算節(jié)點 $j$ 到節(jié)點 $i$ 的傳播概率 $T_{ij}$ ；
第3步：定義矩陣 $Y\in (l+u)\times C$ ;
第4步：執(zhí)行傳播蒲障，每個節(jié)點按傳播概率將周圍節(jié)點傳播的標注值按權(quán)重相加歹篓，并更新到自己的概率分布， $Y^{t}=T \times Y^{t-1}$ 揉阎。
第5步：重置 $Y$ 中已標記樣本的標簽庄撮，限定已標注的數(shù)據(jù)，把已標注的數(shù)據(jù)的概率分布重新賦值為初始值毙籽；
第6步：重復(fù)步驟4和5洞斯，直至 $Y$ 收斂。

步驟5非常關(guān)鍵坑赡，因為已標記數(shù)據(jù)是事先確定的巡扇，不能被帶跑，每次傳播完都得回歸本來的標簽垮衷。

四厅翔、標簽傳播算法的變形

每次迭代都要計算標簽矩陣 $Y$ ，但是 $Y_L$ 是已知的搀突，計算用處不大刀闷。在步驟5中，還需重設(shè)初始值〉榛瑁可以將矩陣 $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實現(xiàn)

1. LPA算法的R實現(xiàn)

R中實現(xiàn)社區(qū)發(fā)現(xiàn)的包為igraph施蜜，算法函數(shù)有很多種：

cluster_edge_betweenness;
cluster_fast_greedy;
cluster_label_prop;
cluster_leading_eigen;
cluster_louvain;
cluster_optimal;
cluster_spinglass;
cluster_walktrap
其中cluster_label_prop執(zhí)行標簽傳播算法卒蘸。示例如下：

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

結(jié)果展示如下：

圖3. 基于R的社區(qū)發(fā)現(xiàn)示例

2. LAP算法的Python實現(xiàn)

實現(xiàn)方式：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()

結(jié)果展示：

圖4. 基于python的標簽傳播

參考資料

[1] 一起來讀西瓜書：第十三章半監(jiān)督學(xué)習(xí): http://www.reibang.com/p/7d4323c28716;
[2] 半監(jiān)督學(xué)習(xí)的一些文章(Semi-supervised): http://www.reibang.com/p/e0adfd789379;
[3] 社區(qū)發(fā)現(xiàn)(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實現(xiàn): 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;