面向用戶話題相似性特征的鏈路預(yù)測方法

王菲菲,楊揚,蔣飛,許進

(1.北京大學(xué)光華管理學(xué)院,100871,北京;2.北京大學(xué)高可信軟件教育部重點實驗室,100871,北京)

?

面向用戶話題相似性特征的鏈路預(yù)測方法

王菲菲1,楊揚2,蔣飛2,許進2

(1.北京大學(xué)光華管理學(xué)院,100871,北京;2.北京大學(xué)高可信軟件教育部重點實驗室,100871,北京)

針對線上用戶間的鏈路預(yù)測對用戶文本內(nèi)容特征的挖掘不夠充分的現(xiàn)象,提出了面向用戶興趣話題相似性的二次特征抽取方法。該方法應(yīng)用主題模型得到任意用戶的主題分布,利用用戶在主題上相異的分布比例提取各自的興趣話題集合,基于興趣話題集合構(gòu)造了一組話題相似性特征用于鏈路預(yù)測。不同于傳統(tǒng)方法中對用戶主題分布的直接利用,該方法對用戶文本內(nèi)容的相似性特征進行了再次挖掘,使得文本特征具有等同于結(jié)構(gòu)特征的預(yù)測能力,并能夠作為結(jié)構(gòu)預(yù)測特征的有效補充。實驗結(jié)果表明,內(nèi)容特征的獨立預(yù)測效果普遍優(yōu)于結(jié)構(gòu)特征,并且在聯(lián)合預(yù)測中將結(jié)構(gòu)特征的預(yù)測效果提高了3%。

鏈路預(yù)測;用戶內(nèi)容;主題模型;相似性特征

社交服務(wù)提供商為了保持用戶黏性,需培養(yǎng)用戶從事在線社交活動的行為習(xí)慣,維持其較高的參與度和存在感,一個重要的方法就是通過鏈路預(yù)測來進行推薦，引導(dǎo)用戶關(guān)注具有共同愛好的線上朋友或發(fā)現(xiàn)尚未建立關(guān)注關(guān)系的線下好友。社交網(wǎng)絡(luò)中好友間可被觀測到的相互關(guān)注關(guān)系通常被簡稱為鏈路。鏈路預(yù)測問題可以概括為:對于目標(biāo)網(wǎng)絡(luò)中每一對未觀測到存在鏈路的節(jié)點對,預(yù)測它們之間是否真的存在鏈路,或者是否會在將來建立新的鏈路。

鏈路預(yù)測中一類重要方法是基于節(jié)點相似性假設(shè)進行預(yù)測,即相似性越強的節(jié)點對之間存在鏈路的概率越高。早期研究中對于節(jié)點相似性的刻畫,主要體現(xiàn)在提取有效的結(jié)構(gòu)特征來刻畫節(jié)點對的相似性,例如以社交行為為背景的共同好友數(shù)[1]、局部結(jié)構(gòu)相似性和社團貢獻度[2]等特征。這類研究普遍具有數(shù)據(jù)采集便捷、特征計算復(fù)雜度低、解釋性強和精度良好等優(yōu)勢,并常在后續(xù)工作中作為預(yù)測效果的評價基準(zhǔn)。在近期研究中,人們開始引入多元和異質(zhì)的信息來提高原有結(jié)構(gòu)信息的預(yù)測精度,即除了原有結(jié)構(gòu)信息外,還引入用戶在同一社交網(wǎng)絡(luò)中產(chǎn)生的文本內(nèi)容信息、地理位置信息或在其他平行社交網(wǎng)絡(luò)中產(chǎn)生的結(jié)構(gòu)、文本、地理位置信息等。

在社交網(wǎng)絡(luò)所包含的多元異質(zhì)信息中,文本信息占據(jù)著主導(dǎo)地位,其大量形成于網(wǎng)絡(luò)中的節(jié)點,并時刻借助網(wǎng)絡(luò)中的鏈路進行傳播。相比于結(jié)構(gòu)特征對用戶關(guān)注關(guān)系直接刻畫，文本特征從信息傳播角度間接體現(xiàn)了用戶間潛在的好友關(guān)系。對于文本信息的充分挖掘能夠有效改善結(jié)構(gòu)特征的預(yù)測效果,并體現(xiàn)在基于文本相似性假設(shè)的鏈路預(yù)測[3]等研究工作中。

基于文本相似性假設(shè)的鏈路預(yù)測是隨著文本建模研究的發(fā)展而出現(xiàn)的。文本模型經(jīng)歷了由TF-IDF(text frequency-inverse document frequency)模型到LDA (latent dirichlet allocation)模型[4]的重要發(fā)展階段,其中LDA模型是一類非常重要的概率主題模型。它在傳統(tǒng)的空間向量模型和語言模型的基礎(chǔ)上引入了主題空間,將每篇文檔看成是在主題空間上的概率分布,將每個主題看成是在整個詞典空間上的概率分布,從而構(gòu)建了“文檔-主題-詞典”的多層次概率模型。該模型具有較好的泛化能力和較強的可擴展性,因而被廣泛地應(yīng)用于包括社交網(wǎng)絡(luò)文本內(nèi)容建模在內(nèi)的研究工作中。

在社交網(wǎng)絡(luò)的鏈路預(yù)測中,對于用戶的文本內(nèi)容的利用主要通過以下兩種方式:

(1)對用戶的內(nèi)容進行文本建模,并將得到的內(nèi)容特征應(yīng)用于預(yù)測模型,或?qū)Τ醪降玫降膬?nèi)容特征進行進一步抽取,用新得到的用戶內(nèi)容特征進行預(yù)測;

(2)擴展原有的文本模型,對用戶內(nèi)容和網(wǎng)絡(luò)結(jié)構(gòu)進行聯(lián)合建模,并通過模型擬合后的相應(yīng)參數(shù)直接或間接推導(dǎo)出鏈路的存在概率。

在第一種方式中,Puniyani等在回歸模型中將每對文檔在每個主題上分布概率之差的平方值作為自變量,研究了每個特定主題與文檔間鏈路的存在性是否顯著相關(guān)[5]。相似地,Quercia等則證明了改進的監(jiān)督型主題模型Labeled-LDA能夠取得與LDA相近的用戶相似性評價效果[3]。

第二種方式中建立的聯(lián)合模型是對LDA主題模型的進一步擴展,能夠建模網(wǎng)絡(luò)中所有文本與結(jié)構(gòu)信息的生成過程。Erosheva等提出的Link-LDA模型假設(shè)一篇文檔中的每一個詞以及該文檔的引用連接服從同一個主題分布,并且由該引用連接的主題歸屬來分配被引文檔的編號[6],從而模擬了文檔間的引用與被引用的關(guān)系以及文檔內(nèi)容的生成過程,然而該模型并不服從文本相似性假設(shè)。Ramage等提出了Link-PLSA-LDA模型[7]。該模型對Link-LDA模型進行了擴展,將PLSA(probabilistic latent semantic analysis)模型和LDA模型統(tǒng)一在一個模型框架中,并顯式地刻畫了主引文檔和被引文檔之間的拓撲結(jié)構(gòu)關(guān)系,即文檔鏈路關(guān)系,進而經(jīng)過模型推導(dǎo),給出了主引文檔與被引文檔之間主題相關(guān)性的條件概率,并通過該條件概率取值來進行鏈路預(yù)測。Chang等提出了相關(guān)性主題模型,從而對文檔網(wǎng)絡(luò)的內(nèi)容和鏈路的生成過程進行建模[8]。該模型用一個二元指示變量表示一對文檔之間鏈路的存在性,并且假定該二元變量與其所對應(yīng)文檔的主題相關(guān)性系數(shù)具有邏輯回歸關(guān)系。

本文屬于第一種方式,研究了基于LDA主題模型提取的用戶內(nèi)容特征,在社交網(wǎng)絡(luò)中進行鏈路預(yù)測的效果。本文首先應(yīng)用LDA主題模型對用戶微博內(nèi)容進行主題建模,得到了每個用戶內(nèi)容的主題分布,進而創(chuàng)新性地提出了直接內(nèi)容特征和間接內(nèi)容特征兩類相似性指標(biāo)。其中在直接內(nèi)容特征中,提出將用戶主題熵之間的差異性與主題分布的相似性進行聯(lián)合,來評價不同用戶在話題愛好上的差異性;在間接內(nèi)容特征中,利用用戶內(nèi)容在主題分布上的差異性,設(shè)定不同閾值篩選出任意一個用戶的話題優(yōu)先性集合,進而基于不同用戶的話題集合,提出一組相似性指標(biāo)來評價他們的話題集合相似性。對于以上所有內(nèi)容特征,首先分別將其與常見結(jié)構(gòu)特征的獨立預(yù)測效果進行了對比,證實了直接內(nèi)容特征和間接內(nèi)容特征在鏈路預(yù)測中的有效性;接著,在不同監(jiān)督型算法中,對不同特征集合的預(yù)測效果進行了比較。實驗結(jié)果表明,內(nèi)容特征集合能夠獨立地取得較高的預(yù)測準(zhǔn)確率,并且能夠有效提高傳統(tǒng)的基于結(jié)構(gòu)特征的方法的預(yù)測效果。

本文的貢獻主要表現(xiàn)在:

(1)對LDA文本建模得到的用戶主題分布進行二次特征抽取,得到了直接內(nèi)容特征和間接內(nèi)容特征兩類內(nèi)容特征;

(2)通過充分的實驗,驗證了間接內(nèi)容特征在獨立預(yù)測中優(yōu)于結(jié)構(gòu)特征,并能在聯(lián)合預(yù)測中改善結(jié)構(gòu)特征的預(yù)測效果。

1 數(shù)據(jù)采集和預(yù)處理

1.1 數(shù)據(jù)采集

本文所用的原始數(shù)據(jù)采集自新浪微博,采集時間段為2014年8月31日8時至2014年8月31日18時,其中包含用戶54 119人,有向鏈接754 149條,以及所有用戶在近一周內(nèi)原創(chuàng)和轉(zhuǎn)發(fā)的微博文本內(nèi)容共1 114 693條。

1.2 數(shù)據(jù)預(yù)處理

由于本文關(guān)注的是無向網(wǎng)絡(luò)中的鏈路預(yù)測問題,因此需要把有向鏈路轉(zhuǎn)換成無向鏈路,并去除在此過程中產(chǎn)生的重邊。最終得到的網(wǎng)絡(luò)具有無向鏈路621 875條,其中用戶節(jié)點的最大度數(shù)為3 219,最小度數(shù)為4。

本文所用到的文本內(nèi)容數(shù)據(jù)包括用戶原創(chuàng)和轉(zhuǎn)發(fā)的微博,每條長度不超過140個中文漢字。在采集到的數(shù)據(jù)中,絕大多數(shù)用戶發(fā)表的微博數(shù)都在20到60條之間,占總?cè)藬?shù)的78.3%。為了取得更好的主題建模效果,將屬于同一個用戶的所有微博內(nèi)容進行拼接,以避免在主題建模的過程中由于文本稀疏性而引發(fā)的詞頻共現(xiàn)性較差等問題,因而最終得到了對應(yīng)于每個用戶的54 119條長度不同的文本內(nèi)容。

對于每條長文本,首先去掉微博內(nèi)容中的標(biāo)點符號、特殊字符以及外文字符,進而去除停用詞并進行中文分詞。本文所使用的分詞工具是北京理工大學(xué)發(fā)布的NLPIR中文文本分詞系統(tǒng)[9]。

2 預(yù)測特征

本節(jié)中分別給出本文在進行鏈路預(yù)測時用到的9個基準(zhǔn)結(jié)構(gòu)預(yù)測特征、2個由用戶主題分布直接計算得到的內(nèi)容相似性特征以及6個由對主題分布進行進一步挖掘得到的用戶內(nèi)容特征。

2.1 結(jié)構(gòu)預(yù)測特征

結(jié)構(gòu)預(yù)測特征是基于網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)計算得到的用于表示社交網(wǎng)絡(luò)中節(jié)點對的結(jié)構(gòu)相似性。本文用做基準(zhǔn)的結(jié)構(gòu)特征包括CN、LHN、Salton、Sonrensen、Jaccard、Adamic-Adar(AA)、PA、HPI和HDI指標(biāo)[10],分別設(shè)為S1、S2、S3、S4、S5、S6、S7、S8和S9。

2.2 直接內(nèi)容特征

文本內(nèi)容特征的提出是建立在相鄰用戶具有更高內(nèi)容相似性的假設(shè)之上的。對于數(shù)據(jù)預(yù)處理之后得到的中文文本分詞結(jié)果,應(yīng)用LDA主題模型進行文本建模,得到每一個用戶的主題分布,主題個數(shù)為100。

基于得到的用戶主題分布,本文給出2個直接計算得到的相似性度量指標(biāo):

(1)主題相關(guān)性系數(shù)Rxy。相關(guān)性系數(shù)能夠度量兩個變量之間線性相關(guān)關(guān)系的密切程度,因此本文通過計算不同用戶的微博文本內(nèi)容在主題分布上的相關(guān)性系數(shù),來度量用戶之間的主題相似程度。已知用戶x和用戶y的文本內(nèi)容在n個主題上的分布θx和θy,則相關(guān)性系數(shù)的計算方法為

(1)

(2)主題熵Hx。在本文中,熵被用于度量用戶主題分布的無序性,對于用戶x的內(nèi)容在n個主題上的分布,其主題熵的計算公式為

(2)

當(dāng)用戶內(nèi)容在主題上不是服從均勻分布,而是集中分布在一個或少數(shù)幾個主題上時,用戶的主題熵較小,這反映了用戶愛好比較集中的現(xiàn)象;相反,當(dāng)用戶的主題分布較為均勻,沒有明顯的傾向性時,用戶的主題熵較大,這說明了用戶的愛好比較廣泛。為了評價任意一對用戶x和y在興趣愛好的集中程度上的差異性,本文采用主題熵之差的絕對值作為度量指標(biāo),其計算公式為

(3)

如果該指標(biāo)的取值較小,則說明用戶x和y的興趣愛好的集中程度比較接近,反之則說明集中程度的差異性較大。

2.3 間接內(nèi)容特征

(1)共同興趣主題數(shù)設(shè)為F1。對于用戶x和y,該特征是他們主題集合Tx和Ty的交集,反映了兩人興趣主題集合的重疊數(shù)目。具有越多共同話題的用戶之間的共同興趣主題數(shù)越高。

(2)共同興趣主題占比設(shè)為F2。對于用戶x和y,該特征是他們興趣話題集合Tx和Ty的交集與并集之比,反映了共同興趣主題占兩人所有愛好主題的比例。若兩人具有較多的共同興趣主題數(shù)和較少的總愛好主題,則該特征取值較高。該特征刻畫了兩人興趣主題集合的重疊程度。

(3)以主題分布概率賦權(quán)的共同興趣主題數(shù)和共同興趣主題占比分別設(shè)為F3和F4。

3 實驗對象和算法

本文所采用的數(shù)據(jù)集為2014年8月31日當(dāng)天采集得到的靜態(tài)數(shù)據(jù),通過按相同比例隨機抽取該數(shù)據(jù)集中存在鏈接與不存在鏈接的節(jié)點對,構(gòu)造出無重復(fù)的訓(xùn)練數(shù)據(jù)與測試數(shù)據(jù)。

由于實驗是判斷給定的靜態(tài)網(wǎng)絡(luò)中任意兩點之間的鏈路是否存在,因此用1表示鏈路存在,用0表示鏈路不存在,可以將該問題轉(zhuǎn)化為二分類問題。在此基礎(chǔ)上,在監(jiān)督學(xué)習(xí)框架下對結(jié)構(gòu)特征、直接內(nèi)容特征和間接內(nèi)容特征的預(yù)測能力進行評價。首先通過每個特征的獨立預(yù)測效果對結(jié)構(gòu)特征和內(nèi)容特征的預(yù)測能力進行比較,進而在多個分類器中對這些特征的整體預(yù)測效果進行評價。

表1 內(nèi)容特征

4 實驗評價

本節(jié)在監(jiān)督學(xué)習(xí)框架下對提出的預(yù)測特征進行評價,以驗證本文所提內(nèi)容特征在鏈路預(yù)測應(yīng)用中的有效性。

4.1 獨立特征評價

分別應(yīng)用9個基準(zhǔn)結(jié)構(gòu)特征、2個直接內(nèi)容特征和6個間接內(nèi)容特征在新浪微博數(shù)據(jù)集上進行鏈路預(yù)測,并采用基于抽樣方法實現(xiàn)的近似AUC得分進行效果評價[11]。

對于每個特征,在新浪微博數(shù)據(jù)中進行30次隨機抽樣,每次抽取100 000組樣本,并計算其AUC得分,其中結(jié)構(gòu)特征和直接內(nèi)容特征如圖1所示,間接內(nèi)容特征分別在p值為0.2、0.4、0.6和0.8時進行計算,結(jié)果如圖2所示。

圖1 結(jié)構(gòu)特征和直接內(nèi)容特征的AUC得分

圖2 間接內(nèi)容特征的AUC得分

由圖1、圖2可以看出,在獨立特征預(yù)測中,PA指標(biāo)取得了結(jié)構(gòu)特征中的最高得分。這說明該數(shù)據(jù)集中的鏈路通常存在于兩個度數(shù)較高的節(jié)點之間,即新浪微博用戶表現(xiàn)出較強的擇優(yōu)連接特性。相應(yīng)地,其他與PA指數(shù)存在負相關(guān)的指標(biāo)預(yù)測效果相對較差。在直接內(nèi)容特征中,主題相關(guān)性系數(shù)Rxy取得了最好的預(yù)測效果,而間接內(nèi)容特征中的F5測度取得了更好的預(yù)測效果。

從整體上來看,內(nèi)容特征取得了與結(jié)構(gòu)特征相近的獨立預(yù)測效果,并且大多數(shù)內(nèi)容特征的單獨預(yù)測能力都優(yōu)于結(jié)構(gòu)特征。間接內(nèi)容特征在p值較小(p=0.2)時能夠取得最好的預(yù)測結(jié)果,而隨著p值增大,間接內(nèi)容特征的預(yù)測效果隨之下降。直接內(nèi)容特征中的主題熵差絕對值Dxy取得了最差的預(yù)測效果,幾乎與隨機預(yù)測器效果相同。

4.2 監(jiān)督預(yù)測評價

本節(jié)在監(jiān)督學(xué)習(xí)的框架下,給出了一個同時基于內(nèi)容特征和結(jié)構(gòu)特征的鏈路預(yù)測模型,以評價所提出特征的預(yù)測效果。首先利用邏輯回歸(LR)分類模型,對各個內(nèi)容特征與鏈接存在與否的相關(guān)關(guān)系進行了檢驗;然后通過支撐向量機(SVM)、隨機森林(RF)、決策樹(DT)和樸素貝葉斯(NB)4種常用分類器進一步驗證同時基于內(nèi)容特征和結(jié)構(gòu)特征的鏈路預(yù)測模型的有效性。

邏輯回歸分類器的優(yōu)勢在于不但能夠完成分類工作,還能夠在建模后檢驗自變量是否與因變量顯著相關(guān),并且自變量對應(yīng)的回歸系數(shù)可以顯示自變量與因變量的相關(guān)關(guān)系是正相關(guān)還是負相關(guān)。本文用邏輯回歸分類器判斷基于內(nèi)容特征的各項指標(biāo)是否具有較強的鏈路預(yù)測能力。

由于分類問題可看成是二分類問題,因此在邏輯回歸模型中,將節(jié)點對之間的鏈路是否存在作為因變量Y(取值為0或1);將結(jié)構(gòu)特征、直接內(nèi)容特征和間接內(nèi)容特征作為自變量,分別用X1,X2,…,X17表示。設(shè)在n個自變量作用下鏈路存在的條件概率為P=P(Y=1|X1,X2,…,Xn),則可將LR模型表示為

z1=a-1+a1Xi1+a2Xi2+…+a17Xi17+εi

Pi=1/(1+ezi)

式中:a-1和aj分別表示回歸常數(shù)和第j個自變量的回歸系數(shù);εi為隨機誤差項。本文對數(shù)據(jù)集中可觀測到的鏈路和未觀測到的鏈路進行了10組隨機抽樣,每組的抽樣規(guī)模為100 000,并保證正負樣本的比例相同。將其中的任意一組數(shù)據(jù)用于進行邏輯回歸分類器的訓(xùn)練,就能夠得到與每個自變量一一對應(yīng)的回歸系數(shù)及其顯著性指標(biāo),下面根據(jù)實驗數(shù)據(jù)進行詳細說明。

表2中列出了其中一組邏輯回歸分類器的訓(xùn)練結(jié)果。標(biāo)準(zhǔn)誤差可用于評價回歸系數(shù)是否顯著不為0;z值是由回歸系數(shù)與標(biāo)準(zhǔn)誤差之比得到的,與p一起用于檢驗回歸系數(shù)為0的零假設(shè)。一般來說,取顯著性水平α為0.05,當(dāng)p小于α?xí)r,說明回歸系數(shù)顯著不為0,即自變量與因變量顯著相關(guān)。由表2可以看出,只有Dxy的p大于顯著性水平α(α<0.166),因此除了直接預(yù)測特征中的主題熵之外,其他預(yù)測特征對鏈路存在與否均具有顯著影響。

表2 邏輯回歸結(jié)果

在所有10組實驗中,結(jié)構(gòu)相似性指標(biāo)一致地表現(xiàn)出顯著性特征,其中F5在少數(shù)幾次實驗中不具有顯著性;直接內(nèi)容特征中,主題相關(guān)性系數(shù)Rxy均表現(xiàn)出顯著性,而主題熵之差的絕對值Dxy均不具有顯著性;在間接內(nèi)容特征中,所有自變量均一致地表現(xiàn)出顯著性。實驗結(jié)果表明,在邏輯回歸分類器中,除主題熵特征外,其余文本內(nèi)容特征均能夠有效地影響鏈路預(yù)測結(jié)果。

接下來,在支撐向量機(SVM)、隨機森林(RF)、決策樹(DT)和樸素貝葉斯(NB)4個分類器中對模型的預(yù)測效果進行進一步測試。實驗中訓(xùn)練數(shù)據(jù)與測試數(shù)據(jù)的規(guī)模和抽樣方法與邏輯回歸分類器相同。在每個分類器中分別對結(jié)構(gòu)特征、內(nèi)容特征以及全部特征進行了測試,內(nèi)容特征包括直接內(nèi)容特征與間接內(nèi)容特征,其中間接內(nèi)容特征分別在p為0.2、0.4、0.6和0.8時進行抽取。所有的參數(shù)取值都是對10次重復(fù)實驗結(jié)果求得的平均值。模型的分類效果如圖3、圖4和表3所示。

圖3 全部特征的分類效果

圖4 內(nèi)容特征的分類效果

對比各個分類器的F-測度可以看出,SVM分類器在3組特征下都取得了最好的預(yù)測效果,其次分別為隨機森林分類器、決策樹分類器和樸素貝葉斯分類器。對比內(nèi)容特征和結(jié)構(gòu)特征各自的預(yù)測結(jié)果,可以看出內(nèi)容特征具有接近結(jié)構(gòu)特征的預(yù)測能力,其中對于SVM分類器、隨機森林分類器和決策樹分類器,內(nèi)容特征的預(yù)測效果稍差于內(nèi)容特征,而對于樸素貝葉斯分類器,應(yīng)用內(nèi)容特征分類的召回率和F-測度明顯高于結(jié)構(gòu)特征的相應(yīng)值。對比全部特征和結(jié)構(gòu)特征的預(yù)測效果,可以看出內(nèi)容特征分別將傳統(tǒng)的結(jié)構(gòu)特征預(yù)測效果(F-測度)提高了1.2%至3%,是對結(jié)構(gòu)預(yù)測特征的有效補充。

表3 結(jié)構(gòu)特征的分類效果

實驗中,內(nèi)容特征和全部特征的預(yù)測效果均隨著p的增大而保持穩(wěn)定或表現(xiàn)出不明顯的下降規(guī)律,但在p為0.2時均取得了最好的預(yù)測效果,這說明當(dāng)主題占比p較小時,通過用戶的興趣主題集合得到的內(nèi)容特征能夠更加有效地區(qū)分存在鏈路與不存在鏈路的用戶組合。

以上實驗結(jié)果表明,在監(jiān)督學(xué)習(xí)框架下,內(nèi)容特征取得了與傳統(tǒng)結(jié)構(gòu)特征相近的預(yù)測效果,并且將兩者結(jié)合在一起能夠取得更好的鏈路預(yù)測效果。

5 結(jié) 論

在鏈路預(yù)測研究中,本文基于在線社交網(wǎng)絡(luò)中的節(jié)點具有豐富的內(nèi)容信息這一特點,提出了利用文本內(nèi)容進行鏈路預(yù)測的研究思路。對于用戶的文本內(nèi)容,本文首先采用LDA主題模型進行文本建模,得到了所有用戶內(nèi)容在各個不同主題上的分布,進而提取出主題相關(guān)性系數(shù)和主題熵兩個直接內(nèi)容特征和其他間接內(nèi)容特征。接著,通過獨立特征預(yù)測,將兩類內(nèi)容特征與常用結(jié)構(gòu)特征的預(yù)測效果進行了對比,發(fā)現(xiàn)除結(jié)構(gòu)特征中的PA指標(biāo)外,內(nèi)容特征的獨立預(yù)測能力普遍高于結(jié)構(gòu)特征。最后,結(jié)合結(jié)構(gòu)特征、直接和間接內(nèi)容特征給出了一個監(jiān)督學(xué)習(xí)框架下的鏈路預(yù)測模型。實驗結(jié)果顯示,通過準(zhǔn)確率、召回率和測度值進行評價,內(nèi)容特征具有接近結(jié)構(gòu)特征的預(yù)測能力,并且將兩者進行結(jié)合能夠取得更好的預(yù)測效果。

在實際應(yīng)用中,常需要對用戶間鏈路的存在概率進行估計,而非簡單判斷鏈路是否存在,尤其是進行保守預(yù)測時。這時,可利用能夠給出概率估值的分類器或排序算法,例如本文所用的邏輯回歸分類器能夠給出樣本點的概率估值,Ranking SVM[13]算法能夠?qū)颖具M行排序。在得到概率估值或樣本排序后,概率值更大或序數(shù)更小的樣本(未觀測到存在鏈路的用戶組合)更可能被預(yù)測為存在鏈路。

本文的工作可以在模型參數(shù)優(yōu)化和內(nèi)容特征挖掘等方面進行改進。例如:通過優(yōu)化主題模型在短文本上的建模效果,可獲得更好的主題含義,進而得到解釋性更強的用戶內(nèi)容特征;挖掘用戶微博的時序性和頻次性等信息,從而可提取更為豐富且合理的內(nèi)容相似性特征等。

[1] 呂琳媛. 復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測 [J]. 電子科技大學(xué)學(xué)報, 2010, 39(5): 651-661. Lü Lin-yuan. Link prediction on complex networks [J]. Journal of University of Electronic Science and Technology of China, 2010, 39(5): 651-661.

[2] 伍杰華. 基于劃分社區(qū)和差分共鄰節(jié)點貢獻的鏈路預(yù)測 [J]. 計算機應(yīng)用研究, 2013, 30(10): 2954-2957. WU Jiehua. Link prediction based on partitioning community and differentiating role of common neighbors [J]. Application Research of Computers, 2013, 30(10): 2954-2957.

[3] QUERCIA D, ASKHAM H, CROWCROFT J. TweetLDA: supervised topic classification and link prediction in Twitter [C]∥Proceedings of the 4th Annual ACM Web Science Conference. New York, USA: ACM, 2012: 247-250.

[4] BLEI D M, NG A Y, JORDAN M I. Latent Dirichlet allocation [J]. Journal of Machine Learning Research, 2003, 3: 993-1022.

[5] PUNIYANI K, EISENSTEIN J, COHEN S, et al. Social links from latent topics in Microblogs [C]∥Proceedings of the NAACL HLT 2010 Workshop on Computational Linguistics in a World of Social Media. New York, USA: ACM, 2010: 19-20.

[6] EROSHEVA E, FIENBERG S, LAFFERTY J. Mixed-membership models of scientific publications [J]. Proceedings of the National Academy of Sciences, 2004, 101(S1): 5220-5227.

[7] RAMAGE D, HALL D, NALLAPATI R, et al. Labeled LDA: a supervised topic model for credit attribution in multi-labeled corpora [C]∥Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing. New York, USA: ACM, 2009: 248-256.

[8] CHANG J, BLEI D M. Relational topic models for document networks [J]. Journal of Machine Learning Research, 2009, 9: 81-88.

[9] ZHANG Huaping, YU Hongkui, XIONG Deyi, et al. HHMM-based Chinese lexical analyzer ICTCLAS [C]∥Proceedings of the Second SIGHAN Workshop on Chinese Language Processing. New York, USA: ACM, 2003: 184-187.

[10]DONG Yuxiao, KE Qing, WANG Bai, et al. Link prediction based on local information [C]∥Proceedings of the 2012 IEEE International Conference on Advances in Social Networks Analysis and Mining. Piscataway, NJ, USA: IEEE Computer Society, 2011: 382-386.

[11]呂琳媛, 周濤. 鏈路預(yù)測 [M]. 北京: 高等教育出版社, 2013: 82-87.

[12]KOSSINETS G. Effects of missing data in social networks [J]. Social Networks, 2006, 28(3): 247-268.

[13]JOACHIMS T. Optimizing search engines using click through data [C]∥Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2002: 133-142.

[本刊相關(guān)文獻鏈接]

劉兆麗,秦濤,管曉宏,等.采用用戶名相似度傳播模型的線上用戶身份屬性關(guān)聯(lián)方法.2016,50(4):1-6.[doi:10.7652/xjtuxb201604001]

孟憲佳,馬建峰,王一川,等.面向社交網(wǎng)絡(luò)中多背景的信任評估模型.2015,49(4):73-77.[doi:10.7652/xjtuxb201504 012]

葉娜,趙銀亮,邊根慶,等.模式無關(guān)的社交網(wǎng)絡(luò)用戶識別算法.2013,47(12):19-25.[doi:10.7652/xjtuxb201312004]

張賽,徐恪,李海濤,等.微博類社交網(wǎng)絡(luò)中信息傳播的測量與分析.2013,47(2):124-130.[doi:10.7652/xjtuxb201302 021]

孫艷,周學(xué)廣,付偉.無監(jiān)督的主題情感混合模型研究.2013,47(1):120-125.[doi:10.7652/xjtuxb201301023]

莫同,褚偉杰,李偉平,等.采用超圖的微博群落感知方法.2012,46(11):120-126.[doi:10.7652/xjtuxb201211022]

(編輯 武紅江)

A Link Prediction Method Based on Similarity of User’s Topics

WANG Feifei1,YANG Yang2,JIANG Fei2,XU Jin2

(1. Guanghua School of Management, Peking University, Beijing 100871, China; 2. Key Lab of High Confidence Software Technologies, Peking University, Beijing 100871, China)

A new topical feature extraction method based on similarities of user’s topics is proposed to solve the insufficiency of topical feature mining of link predictions in social networks. The topic distributions of social network users are firstly obtained using a topic model and then topic groups of interests for each user are extracted for further similarity-based feature extractions. The proposed topical features exhibit comparable performance of structural features and is efficiently combined with structural features to achieve better results in link predictions. Experimental results based on the dataset collected from Sina Microblog show that independent prediction of topical features is better than that of structural features and the F-measure of structural features is improved by up to 3% with joint predictions.

link prediction; user generated content; topic model; feature similarity

10.7652/xjtuxb201608017

2016-03-12。 作者簡介:王菲菲(1988—),女,博士生;許進(通信作者),男,教授,博士生導(dǎo)師。 基金項目:國家重點基礎(chǔ)研究發(fā)展計劃資助項目(2013cb329600);國家自然科學(xué)基金資助項目(61372191,61572492,61472433)。

時間:2016-06-27

http:∥www.cnki.net/kcms/detail/61.1069.T.20160627.1231.008.html

TP391.9

A

0253-987X(2016)08-0103-07