劉宇廷，倪穎杰

(江南計(jì)算技術(shù)研究所，江蘇 無(wú)錫 214083)

0 引 言

傳統(tǒng)的社團(tuán)劃分方法是一種無(wú)監(jiān)督的劃分方法，僅僅根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息，即節(jié)點(diǎn)和節(jié)點(diǎn)間的連接關(guān)系來(lái)發(fā)現(xiàn)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)[1]。現(xiàn)實(shí)中，有些網(wǎng)絡(luò)可能是不精確的或者不完全的，而這些傳統(tǒng)方法劃分社團(tuán)的準(zhǔn)確度依賴于網(wǎng)絡(luò)的精確度，因此當(dāng)網(wǎng)絡(luò)中含有噪音時(shí)會(huì)迅速降低它們發(fā)現(xiàn)社團(tuán)的準(zhǔn)確度。在實(shí)際應(yīng)用中，往往能獲取結(jié)構(gòu)信息之外的數(shù)據(jù)，例如科學(xué)家合作網(wǎng)絡(luò)中已知某個(gè)科學(xué)家是屬于某個(gè)小團(tuán)體，蛋白質(zhì)與蛋白質(zhì)相互作用網(wǎng)絡(luò)中已知某個(gè)蛋白質(zhì)屬于某個(gè)功能模塊等等。這些信息可以直接或間接地獲取部分關(guān)于社團(tuán)結(jié)構(gòu)的先驗(yàn)信息，包括節(jié)點(diǎn)標(biāo)簽和節(jié)點(diǎn)對(duì)約束條件等。

傳統(tǒng)社團(tuán)檢測(cè)方法可以劃分為基于啟發(fā)式函數(shù)算法和基于統(tǒng)計(jì)模型的方法?；趩l(fā)式算法的核心是定義一個(gè)目標(biāo)函數(shù)如模塊度等，這些算法通常衡量網(wǎng)絡(luò)分割優(yōu)良程度，目標(biāo)函數(shù)的功能是最終找到一個(gè)最優(yōu)的分割方案?；谀Ｐ偷姆椒ㄓ蓸?gòu)建一個(gè)統(tǒng)計(jì)模型開始，生成用來(lái)研究的網(wǎng)絡(luò)，然后提出一個(gè)統(tǒng)計(jì)檢測(cè)工具來(lái)學(xué)習(xí)得到潛在的社團(tuán)。當(dāng)前比較流行的模型包括隨機(jī)塊模型、度數(shù)相關(guān)的隨機(jī)塊模型和混合成員的隨機(jī)塊模型。近年來(lái)，許多學(xué)者也在研究基于這些模型進(jìn)行社團(tuán)檢測(cè)的理論性能。例如，在隨機(jī)塊模型上使用基于相似度的方法[2]，使用譜聚類的方法等等。Newman提出一種基于隨機(jī)塊模型的統(tǒng)計(jì)檢測(cè)方法[1]，通過(guò)定義節(jié)點(diǎn)元數(shù)據(jù)歸屬不同社團(tuán)的邊緣概率分布，得到基于網(wǎng)絡(luò)拓?fù)渑c節(jié)點(diǎn)元數(shù)據(jù)的似然概率模型，通過(guò)EM算法求解方程得到最優(yōu)解。該方法能夠自動(dòng)判斷節(jié)點(diǎn)元數(shù)據(jù)是否有利于社團(tuán)劃分，但是也存在明顯的缺點(diǎn)。算法中使用的節(jié)點(diǎn)元數(shù)據(jù)為獨(dú)立屬性(如性別、種族、年級(jí))或組合屬性，這些屬性單一，對(duì)社交網(wǎng)絡(luò)這種復(fù)雜網(wǎng)絡(luò)的劃分其實(shí)作用并不明顯；EM算法在求解最優(yōu)解時(shí)容易產(chǎn)生局部最優(yōu)解。所以，Newman等在實(shí)際應(yīng)用中取多次運(yùn)行的最大值作為最優(yōu)解，這種方式并沒有完全解決如何得到全局最優(yōu)解的問(wèn)題。

在傳統(tǒng)的機(jī)器學(xué)習(xí)框架下，學(xué)習(xí)的任務(wù)就是在給定充分訓(xùn)練數(shù)據(jù)的基礎(chǔ)上學(xué)習(xí)一個(gè)分類或聚類模型，然后利用這個(gè)學(xué)習(xí)到的模型對(duì)測(cè)試網(wǎng)絡(luò)進(jìn)行分類或聚類與預(yù)測(cè)。然而，對(duì)于社交媒體中新出現(xiàn)的數(shù)據(jù)，訓(xùn)練樣本標(biāo)簽非常稀缺。隨著社交網(wǎng)絡(luò)的規(guī)模不斷擴(kuò)大，給訓(xùn)練數(shù)據(jù)打標(biāo)簽工作將會(huì)耗費(fèi)大量的人力與物力。而沒有大量的標(biāo)注數(shù)據(jù)，會(huì)使很多與學(xué)習(xí)相關(guān)的研究與應(yīng)用無(wú)法開展。其次，傳統(tǒng)的機(jī)器學(xué)習(xí)假設(shè)訓(xùn)練數(shù)據(jù)與測(cè)試數(shù)據(jù)服從相同的數(shù)據(jù)分布。然而，在許多情況下，這種同分布假設(shè)并不滿足。如線下的訓(xùn)練數(shù)據(jù)與線上預(yù)測(cè)數(shù)據(jù)存在差異，這往往需要去重新標(biāo)注大量的訓(xùn)練數(shù)據(jù)以滿足訓(xùn)練的需要。從另一個(gè)角度看，如果有大量的、在不同分布下的訓(xùn)練數(shù)據(jù)，完全丟棄這些數(shù)據(jù)也是非常浪費(fèi)的。所以，為了解決這些問(wèn)題，文中提出一種基于文本知識(shí)遷移的模型，能夠利用新聞數(shù)據(jù)訓(xùn)練的向量模型遷移到微博領(lǐng)域進(jìn)行社團(tuán)檢測(cè)，以減輕文本向量化模型訓(xùn)練帶來(lái)的資源消耗。

1 相關(guān)工作

1.1 社團(tuán)結(jié)構(gòu)檢測(cè)模型

近年來(lái)，越來(lái)越多的研究人員對(duì)不同類型模型在社團(tuán)檢測(cè)方面的理論性能進(jìn)行了研究。對(duì)于隨機(jī)塊模型，提出了許多基于似然概率的方法，包括最大似然函數(shù)[2]、子集似然函數(shù)[3]、偽似然函數(shù)[4]和變形推導(dǎo)[5]等。另有一些方法，如基于譜分析[6-8]，通過(guò)譜聚類進(jìn)行塊模型的社團(tuán)檢測(cè)，譜聚類和張量譜分析方法用來(lái)檢測(cè)混合成員模型中重疊社團(tuán)結(jié)構(gòu)。除此之外，一部分研究基于構(gòu)建凸函數(shù)用來(lái)保證社團(tuán)檢測(cè)的可靠性[9-11]，同時(shí)還有基于極大極小值框架的社團(tuán)檢測(cè)方法[12]。

針對(duì)傳統(tǒng)算法無(wú)法利用節(jié)點(diǎn)元數(shù)據(jù)的問(wèn)題，許多學(xué)者進(jìn)行了嘗試與探索。基于啟發(fā)函數(shù)的算法[13-15]，M.E.J.Newman提出一種基于節(jié)點(diǎn)元數(shù)據(jù)的社團(tuán)檢測(cè)算法，能夠自動(dòng)判斷元數(shù)據(jù)能否幫助網(wǎng)絡(luò)劃分，使得到的網(wǎng)絡(luò)劃分評(píng)價(jià)分?jǐn)?shù)更高[1]；Leto Peel等提出在使用元數(shù)據(jù)作為網(wǎng)絡(luò)分割指標(biāo)時(shí)應(yīng)該小心應(yīng)對(duì)，并以Karate俱樂(lè)部作為例子說(shuō)明元數(shù)據(jù)與社團(tuán)之間的關(guān)系[16]。

Newman在文獻(xiàn)[1]中提出了一種基于隨機(jī)塊模型的方法，建立了一個(gè)統(tǒng)計(jì)概率模型，能夠自動(dòng)判斷節(jié)點(diǎn)元數(shù)據(jù)是否有利于社團(tuán)劃分。其主要思想是：在隨機(jī)塊模型上生成的網(wǎng)絡(luò)中定義一個(gè)鄰接矩陣A，在給定參數(shù)與元數(shù)據(jù)的情況下，由模型生成的網(wǎng)絡(luò)的似然概率為：

(1)

其中，Θ為k*k矩陣，元素是θst，為算法中的混合參數(shù)；Γ為元數(shù)據(jù)分配到不同社團(tuán)的矩陣，元素是γsu。

通過(guò)對(duì)方程1應(yīng)用Jensen不等式，可以轉(zhuǎn)而計(jì)算社團(tuán)分配的完全分布q(s)。

P(s|A,Θ,Γ,x)

(2)

通常EM算法分為兩個(gè)部分，即E(期望)階段和M(極大值)階段。由于在這個(gè)算法中求完全分布q(s)與網(wǎng)絡(luò)大小有直接關(guān)系，所以Newman使用BP(置信傳播)算法進(jìn)行求解，目標(biāo)是得到最優(yōu)的參數(shù)Θ和Γ。

1.2 遷移學(xué)習(xí)模型

當(dāng)前，遷移學(xué)習(xí)算法以及相關(guān)理論研究受到了廣泛關(guān)注。遷移學(xué)習(xí)是運(yùn)用已有的知識(shí)對(duì)不同但相關(guān)領(lǐng)域問(wèn)題進(jìn)行求解的一種新的機(jī)器學(xué)習(xí)方法。它放寬了傳統(tǒng)機(jī)器學(xué)習(xí)中的兩個(gè)基本假設(shè)：用于學(xué)習(xí)的訓(xùn)練樣本與新的測(cè)試樣本滿足獨(dú)立同分布的條件；必須有足夠可利用的訓(xùn)練樣本才能學(xué)習(xí)得到一個(gè)好的分類模型。按照源領(lǐng)域和目標(biāo)領(lǐng)域中是否有標(biāo)簽樣本，遷移學(xué)習(xí)劃分為3類[17]：目標(biāo)領(lǐng)域中有少量標(biāo)注樣本的歸納遷移學(xué)習(xí)[18-20]、只有源領(lǐng)域中有標(biāo)注樣本的直推式遷移學(xué)習(xí)以及源領(lǐng)域和目標(biāo)領(lǐng)域都沒有標(biāo)注樣本的無(wú)監(jiān)督遷移學(xué)習(xí)。針對(duì)源領(lǐng)域中有大量已標(biāo)注樣本，而目標(biāo)領(lǐng)域中有少量已標(biāo)注樣本，典型的模型有文獻(xiàn)[21-23]。Harel和Mannor采用譜方法并且結(jié)合類信息將源數(shù)據(jù)和目標(biāo)數(shù)據(jù)建立對(duì)應(yīng)關(guān)系，對(duì)源領(lǐng)域的數(shù)據(jù)進(jìn)行重新表示，然后訓(xùn)練分類器，以便對(duì)目標(biāo)領(lǐng)域中的數(shù)據(jù)進(jìn)行分類。Wang等[24]結(jié)合類別信息和特征信息建立了兩個(gè)相似度矩陣和一個(gè)不相似度矩陣，然后利用譜分解的方法學(xué)到源領(lǐng)域和目標(biāo)領(lǐng)域到一個(gè)新的低維空間的映射關(guān)系。新的空間里面保持了數(shù)據(jù)點(diǎn)原有的類別和特征信息。所有數(shù)據(jù)點(diǎn)通過(guò)新的表示之后，可以進(jìn)行傳統(tǒng)機(jī)器學(xué)習(xí)的方法完成聚類任務(wù)。Duan等[25]借用支持向量機(jī)的思想，結(jié)合類信息學(xué)習(xí)，把源領(lǐng)域和目標(biāo)領(lǐng)域中的數(shù)據(jù)都映射到一個(gè)新的低維空間，然后，結(jié)合各自空間的特征組成新的特征表示。

微博數(shù)據(jù)高維、低質(zhì)體現(xiàn)在網(wǎng)絡(luò)中用戶發(fā)布的信息通常不規(guī)范，口語(yǔ)化，包含錯(cuò)別字和新生詞。這給特征詞的抽取帶來(lái)了很大的困難，所以對(duì)于這些文本信息分析的模型需要仔細(xì)研究與設(shè)計(jì)。當(dāng)前，研究的熱點(diǎn)方向是一些突發(fā)事件。比如，趙華等基于新浪微博數(shù)據(jù)研究H7N9傳染病話題模型[26]，Ting Hua等基于Twitter數(shù)據(jù)分析佛吉尼亞槍擊事件[27]。這些研究通過(guò)遷移學(xué)習(xí)理論學(xué)習(xí)用戶的標(biāo)簽，應(yīng)用分類或者聚類方法得到結(jié)果。Ting Hua在分析目標(biāo)主題(如疾病爆發(fā)、犯罪事件或者大眾情感)時(shí)，提出一種半監(jiān)督目標(biāo)興趣事件檢測(cè)STED方法，通過(guò)建立標(biāo)簽提取模型，將新聞標(biāo)簽遷移到Twitter，產(chǎn)生初始標(biāo)簽數(shù)據(jù)，標(biāo)簽傳播模型產(chǎn)生特征擴(kuò)展標(biāo)簽數(shù)據(jù)，圖分區(qū)模型將一個(gè)tweets分為多個(gè)子集，再使用SVM分類模型識(shí)別與目標(biāo)主題相關(guān)的tweets。

針對(duì)新浪微博用戶數(shù)據(jù)的特點(diǎn)，文中改進(jìn)了Newman提出的社團(tuán)結(jié)構(gòu)檢測(cè)模型，應(yīng)用知識(shí)遷移學(xué)習(xí)構(gòu)造用戶標(biāo)簽特征向量，提出一種融合知識(shí)遷移的社團(tuán)結(jié)構(gòu)檢測(cè)模型。該模型基于新浪微博用戶數(shù)據(jù)集，通過(guò)分詞模型和標(biāo)簽生成模型對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，提取用戶標(biāo)簽，使用新聞數(shù)據(jù)集上訓(xùn)練的模型作為源領(lǐng)域模型，通過(guò)應(yīng)用知識(shí)遷移學(xué)習(xí)模型，構(gòu)造微博用戶標(biāo)簽特征向量，最后使用社團(tuán)結(jié)構(gòu)檢測(cè)模型檢測(cè)社團(tuán)結(jié)構(gòu)。文中方法進(jìn)行的改進(jìn)如下：改進(jìn)Newman的社團(tuán)結(jié)構(gòu)檢測(cè)模型；構(gòu)建由源領(lǐng)域向量目標(biāo)領(lǐng)域遷移的學(xué)習(xí)模型；通過(guò)tf*idf模型擴(kuò)展用戶特征向量。

2 框架與方法

2.1 基于隨機(jī)塊模型的社團(tuán)結(jié)構(gòu)檢測(cè)模型構(gòu)建

隨機(jī)塊模型在給定參數(shù)與節(jié)點(diǎn)元數(shù)據(jù)的條件下，可定義為有無(wú)向網(wǎng)絡(luò)G(V,E,X)，其中V為節(jié)點(diǎn)集合，標(biāo)簽u∈n，E為節(jié)點(diǎn)間邊的集合，X為節(jié)點(diǎn)信息集合，xu∈X，由k個(gè)社區(qū)分割，節(jié)點(diǎn)u屬于某個(gè)社區(qū)表示為su∈k。基準(zhǔn)網(wǎng)絡(luò)中節(jié)點(diǎn)元數(shù)據(jù)來(lái)自不同的高斯模型，可以使用高斯混合模型求解元數(shù)據(jù)X的邊緣概率分布。針對(duì)復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)具有高維元數(shù)據(jù)的情況，可以定義：對(duì)于所有節(jié)點(diǎn)元數(shù)據(jù)X={x1,x2,…,xn}，假設(shè)每個(gè)節(jié)點(diǎn)u分配到社團(tuán)s的概率基于節(jié)點(diǎn)u的元數(shù)據(jù)xu，其中xu∈Ru,n≥1，定義概率為γsx，使用高斯混合模型對(duì)社團(tuán)歸屬建模，得到網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)社團(tuán)分配的先驗(yàn)概率模型為：

(3)

由隨機(jī)塊模型可知，基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的先驗(yàn)概率模型為：

(4)

基于這兩個(gè)模型生成網(wǎng)絡(luò)的似然概率為：

(5)

通?？梢允褂肊M算法進(jìn)行求解，得到：

logP(A|Θ,π,μ,σ,x)=

(6)

所以，EM算法的步驟如下：

循環(huán)重復(fù)直到收斂 {

(E步)對(duì)于每一個(gè)i，計(jì)算

(M步)更新Θ,π,μ,σ,x

}

2.2 知識(shí)遷移學(xué)習(xí)模型構(gòu)建

領(lǐng)域定義：領(lǐng)域D由特征空間χ和邊緣概率分布p(x)組成，其中X={x1,x2,…,xn}∈χ。χ是所有詞向量的空間，xi是第i個(gè)詞向量，對(duì)應(yīng)于一些文本，X是一個(gè)特定的學(xué)習(xí)樣本。一般地，如果兩個(gè)領(lǐng)域不同，則它們或許具有不同的特征空間或不同的邊緣概率分布。

對(duì)于給定的領(lǐng)域D，一個(gè)分類任務(wù)T由類別空間y和目標(biāo)預(yù)測(cè)函數(shù)f(x)組成。目標(biāo)預(yù)測(cè)函數(shù)無(wú)法通過(guò)觀察得到，需要通過(guò)學(xué)習(xí)訓(xùn)練數(shù)據(jù)獲得，訓(xùn)練數(shù)據(jù)由{xi,yi}組成，其中xi∈x，yi∈y。

遷移學(xué)習(xí)定義：給定源領(lǐng)域Ds和學(xué)習(xí)任務(wù)Ts，目標(biāo)領(lǐng)域DT和學(xué)習(xí)任務(wù)TT，遷移學(xué)習(xí)旨在使用Ds和Ts中的知識(shí)，幫助提高目標(biāo)領(lǐng)域DT中預(yù)測(cè)函數(shù)fT(x)的學(xué)習(xí)，其中DS≠DT，或者TS≠TT。

任務(wù)是通過(guò)微博文本特征向量判斷用戶的社團(tuán)信息?？紤]到當(dāng)前針對(duì)社團(tuán)信息的分類學(xué)習(xí)尚無(wú)多見，不妨將這個(gè)問(wèn)題轉(zhuǎn)化為如何由一個(gè)更全的知識(shí)庫(kù)來(lái)得到詞語(yǔ)向量，這個(gè)詞語(yǔ)向量能夠反映出詞語(yǔ)在不同句子、段落中的語(yǔ)義信息，所以源領(lǐng)域與目標(biāo)領(lǐng)域可以不需要標(biāo)注信息，從而可以將遷移學(xué)習(xí)任務(wù)定義為無(wú)監(jiān)督遷移學(xué)習(xí)。

選擇新聞文本數(shù)據(jù)集作為源領(lǐng)域Ds，新聞文本數(shù)據(jù)量要遠(yuǎn)大于微博文本數(shù)據(jù)量，通常句式比較規(guī)范，很少出現(xiàn)錯(cuò)用詞語(yǔ)的情況。通過(guò)學(xué)習(xí)任務(wù)Ts得到詞語(yǔ)向量，能夠較為真實(shí)地反映詞語(yǔ)之間的關(guān)系。學(xué)習(xí)任務(wù)Ts的實(shí)現(xiàn)方法可參考文獻(xiàn)[28]。

微博文本作為目標(biāo)領(lǐng)域DT，通過(guò)學(xué)習(xí)任務(wù)TT得到詞語(yǔ)向量，定義遷移模型為：

xTi=xSi1

(7)

(8)

其中，xSi∈X為源領(lǐng)域詞向量；xTi∈X為目標(biāo)領(lǐng)域詞向量；βi為權(quán)重調(diào)整系數(shù)；aTi為目標(biāo)領(lǐng)域用戶k的加權(quán)平均向量；N為微博用戶標(biāo)簽數(shù)量。

3 實(shí)驗(yàn)及結(jié)果分析

實(shí)驗(yàn)數(shù)據(jù)來(lái)自新浪微博，包含3 200個(gè)微博用戶共237 801條微博，319 565條邊。

通常對(duì)微博用戶數(shù)據(jù)進(jìn)行分詞后，一般需要進(jìn)行標(biāo)簽過(guò)濾，去掉標(biāo)點(diǎn)符號(hào)與停用詞，由于符號(hào)(@，#)與社交聯(lián)系相關(guān)，所以在分詞時(shí)進(jìn)行了預(yù)處理，沒有進(jìn)行切分，部分社交聯(lián)系詞如圖1所示。通過(guò)標(biāo)簽提取模型，共提取出61 372個(gè)標(biāo)簽。訓(xùn)練集中用戶社團(tuán)分布如圖2所示。

@上海@天津@浙江衛(wèi)視@東方衛(wèi)視@格瓦拉@騰訊@百度云@百思不得@北京@土豆網(wǎng)@搜狐新聞@愛奇藝

圖1 部分社交聯(lián)系詞

圖2 訓(xùn)練集用戶社團(tuán)分布

微博用戶網(wǎng)絡(luò)參數(shù)如表1所示。

表1 基準(zhǔn)網(wǎng)絡(luò)參數(shù)清單

應(yīng)用知識(shí)遷移模型可以得到微博用戶文本特征向量wi∈R300，應(yīng)用EM算法求解社團(tuán)檢測(cè)模型最優(yōu)參數(shù)得到社團(tuán)分布，準(zhǔn)確率為30%。通過(guò)標(biāo)簽提取模型進(jìn)一步擴(kuò)展用戶特征，得到微博用戶文本特征向量wi∈R61 672，準(zhǔn)確率達(dá)到41%。

由結(jié)果可知，預(yù)測(cè)結(jié)果性能較低，主要原因是微博用戶發(fā)布的文本內(nèi)容分散，有價(jià)值的信息不多，所以在特征工程上，仍然缺少對(duì)問(wèn)題有幫助的特征；文中使用的知識(shí)遷移模型仍然比較粗糙，需要進(jìn)一步改進(jìn)。

4 結(jié)束語(yǔ)

針對(duì)微博數(shù)據(jù)快速變化、人工標(biāo)注費(fèi)時(shí)費(fèi)力的特點(diǎn)，提出一種利用已有的新聞?lì)I(lǐng)域模型進(jìn)行知識(shí)遷移，得到微博用戶的特征向量，從而進(jìn)行社團(tuán)檢測(cè)的方法。通過(guò)改進(jìn)基于塊模型的社團(tuán)結(jié)構(gòu)檢測(cè)模型，能夠同時(shí)利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與節(jié)點(diǎn)信息進(jìn)行社團(tuán)結(jié)構(gòu)檢測(cè)，將網(wǎng)絡(luò)節(jié)點(diǎn)特征擴(kuò)展到多維，更符合現(xiàn)實(shí)世界網(wǎng)絡(luò)情況。

該方法在應(yīng)用過(guò)程中仍然存在一些問(wèn)題需要解決，比如微博用戶發(fā)微博通常比較口語(yǔ)化，經(jīng)常出現(xiàn)新詞和錯(cuò)字。對(duì)于這類問(wèn)題，文中沒有提出合理的解決方案。通常機(jī)器學(xué)習(xí)任務(wù)需要具體問(wèn)題具體分析，所以針對(duì)社團(tuán)檢測(cè)任務(wù)，仍然需要大量的時(shí)間分析數(shù)據(jù)標(biāo)簽與社團(tuán)的關(guān)系，文中沒有提出解決標(biāo)簽與任務(wù)相關(guān)度的方法。在應(yīng)用遷移學(xué)習(xí)理論中，非常容易出現(xiàn)“負(fù)遷移”的情況，文中進(jìn)行知識(shí)遷移的出發(fā)點(diǎn)是詞語(yǔ)在不同語(yǔ)句中表達(dá)含義相似，但是也存在一詞多義的情況，這種情況并沒有進(jìn)行測(cè)試與研究。這些都是下一步需要研究的方向。