基于多開發(fā)者社區(qū)的用戶推薦算法?

時宇岑,印 瑩,趙宇海,張 斌,王國仁

1(東北大學 計算機科學與工程學院,遼寧 沈陽 110169)

2(北京理工大學 計算機學院,北京 100081)

互聯(lián)網(wǎng)技術的迅猛發(fā)展,深刻變革了許多領域的傳統(tǒng)認知方式.例如在軟件工程領域,基于開發(fā)者社區(qū)的提問-回答經(jīng)驗交流方式已被眾多IT工作者廣泛接受,成為解決軟件開發(fā)、維護過程中所遇問題的重要手段之一.如何為開發(fā)者社區(qū)中的提問者推薦能及時、準確解決問題的回復者,是一個具有實際需求的重要問題.本文通過對Stack Overflow和Github兩個具有代表性的主流開發(fā)者社區(qū)大量相關數(shù)據(jù)的收集和分析,觀察到影響上述推薦問題準確性和反饋及時性的3個現(xiàn)象.

(1) 用戶標簽自定現(xiàn)象

通過對Stack Overflow和Github用戶注冊過程中標簽選擇及其后續(xù)變化情況的分析調(diào)研發(fā)現(xiàn),開發(fā)者社區(qū)中用戶標簽信息是由用戶主觀自定的.因此,存在著兩種情況:① 用戶未選定某標簽,但參與了該標簽對應的問答活動;② 用戶選定了某標簽,但實際并未參與該標簽的問答活動.這兩種情況都會影響推薦的準確性和反饋的及時性,其根源就在于用戶標簽的主觀自定.

(2) 不對稱活躍現(xiàn)象

通過對 Stack Overflow和 Github相關數(shù)據(jù)的搜集和分析,發(fā)現(xiàn)存在著部分用戶在一個社區(qū)(如 Stack Overflow)中十分活躍,參與大量問題回答;而在另一個社區(qū)(如Github)中極少參與問題回答.例如,圖1中給出了用戶“Parvin Gasimzade”在兩個不同社區(qū)中的表現(xiàn).由圖1(a)可見,該用戶在Github中的Repositories值為3,代表其在Github中僅參與了3次問答活動;而在Stack Overflow中用戶的POSTS值為143,代表該用戶僅在mongdb標簽下就參與了143次問答活動,其對應的SCORE值為846,代表該用戶具有846分的正向評分.很明顯,該用戶在Github中參與問答活動的活躍度明顯低于其參與Stack Overflow社區(qū)問答活動的活躍度.調(diào)研發(fā)現(xiàn),與用戶“Parvin Gasimzade”情況類似的其他用戶并不在少數(shù).

Fig.1 Performance of user “Parvin Gasimzade” in two communities圖1 用戶“Parvin Gasimzade”在兩個社區(qū)中的表現(xiàn)

(3) 關鍵詞集封閉現(xiàn)象

軟件開發(fā)人員在調(diào)試遇到的問題時,經(jīng)常會將問題的報錯信息直接復制粘貼到開發(fā)者網(wǎng)站中的搜索框內(nèi)進行查詢.Stack Overflow和 Github中的推薦算法通過提取用戶提交文本中的關鍵詞,利用關鍵詞匹配進行推薦.推薦結果僅根據(jù)用戶提交文本中獲取的關鍵詞給出,忽略了其他語義相關關鍵詞對推薦結果的有效擴充.封閉的關鍵詞集可能導致有效推薦結果被忽略,影響推薦準確性和反饋及時性.

開發(fā)者社區(qū)作為當前軟件開發(fā)人員面臨問題時尋找解決方案的主要參考平臺,在軟件開發(fā)領域有著舉足輕重的地位[1].因此,針對開發(fā)中存在的各種問題,對于推薦算法進行改良,可以有效提高開發(fā)者社區(qū)中的推薦效率.針對現(xiàn)象(1),通過一種基于重啟隨機游走的算法對開發(fā)者網(wǎng)絡中的用戶標簽進行更新,有效降低了用戶標簽的主觀性;針對現(xiàn)象(2),提出一種多開發(fā)者社區(qū)的網(wǎng)絡構建方法,將不同社區(qū)中的開發(fā)者進行鏈接,建立跨開發(fā)者網(wǎng)絡,以提高問題的推薦效率;針對現(xiàn)象(3),使用Taxonomy對問題的標簽范圍進行拓展,進一步聯(lián)合構建的開發(fā)者網(wǎng)絡進行最后的用戶推薦排名.大量實驗評估表明,本文所建立的開發(fā)者網(wǎng)絡有較好的準確性,且可以有效增強所獲的用戶與標簽間關系的客觀性;通過使用Taxonomy,也可以有效提高問題推薦的準確度以及反饋的及時性.

本文第1節(jié)對問題以及相關定義進行描述.第2節(jié)具體闡述本方法的設計思想與具體實現(xiàn).第3節(jié)描述整個實驗的設計和實施,給出實驗結果并進行分析.第4節(jié)概述本文的相關工作.最后,第5節(jié)對全文進行工作總結與展望.

1 問題定義及研究思路

1.1 相關定義

本文的相關定義是關于第 2節(jié)中識別用戶應該用到的文本相似度計算,以及計算用戶與用戶關系所應用到的線性歸一化定義.

定義1(文本相似度).文本相似度主要是針對兩個標簽間的相似度進行衡量,因此,本文對于標簽a與標簽b進行文本相似度計算sim(a,b)由公式(1)定義如下:

定義2(線性歸一化).對于一個集合A內(nèi)的所有元素ai(i≤N)進行線性歸一化處理后的每個元素數(shù)值是通過其原本數(shù)值與集合內(nèi)所有元素數(shù)值之和相除所得,集合A中的元素ai′的線性歸一化計算如公式(2)所示:

1.2 問題描述

本文跨社區(qū)網(wǎng)絡構建主要是將用戶與用戶、用戶與標簽兩部分信息構建成兩個矩陣,其中,用戶-用戶矩陣為n×n階矩陣,用戶-標簽矩陣為n×m階矩陣.利用用戶與用戶和用戶與標簽的關系,在重啟隨機行走中,通過矩陣間的運算得到更為準確的可以代表用戶與標簽關系的n×m階用戶-標簽矩陣.

受文獻[2]中提出的Taxonomy啟發(fā),在得到更新的用戶與標簽關系后,建立如圖2所示的具有上下義關系的標簽樹,用于開發(fā)者社區(qū)中的問題推薦范圍拓展.最后,協(xié)同更新后的用戶與標簽關系進行問題推薦及用戶權重計算,得出最終用戶推薦排名.

Fig.2 An example of a Taxonomy tree rooted at performance圖2 一個以performance為根的Taxonomy樹的例子

1.3 研究思路

本文設計并實現(xiàn)了基于重啟隨機游走的用戶標簽更新算法與基于Taxonomy的用戶推薦算法,主要目的是提高用戶標簽的準確度和問題推薦時的準確度.基于重啟隨機游走算法,通過利用用戶與用戶之間的關系對用戶與標簽之間的關系進行更新,獲得相比用戶自我標記更加準確的用戶偏好.基于 Taxonomy的用戶推薦算法,在擴大問題推薦時,可以匹配到的標簽范圍.方法整體框架如圖3所示.

Fig.3 Algorithm framework圖3 算法框架

本文首先處理開發(fā)者社區(qū)中的用戶數(shù)據(jù),進行跨社區(qū)用戶識別,將相同用戶合并后,建立跨社區(qū)開發(fā)者網(wǎng)絡.通過本文設計的重啟隨機游走算法更新用戶與標簽關系,獲得更加準確的用戶標簽信息.同時,將開發(fā)者社區(qū)中的問題提取關鍵詞并進行基于 Taxonomy的問題內(nèi)容拓展,進一步聯(lián)合獲得的用戶標簽信息進行權重計算,最后根據(jù)權重排名進行用戶推薦.

2 基于多開發(fā)者社區(qū)的用戶推薦算法

本文算法分為 3部分進行工作:(1) 數(shù)據(jù)預處理,包括網(wǎng)絡數(shù)據(jù)的收集處理以及跨社區(qū)相同用戶的識別;(2) 用戶標簽更新,本文受到重啟隨機游走算法的啟發(fā),設計了一種基于重啟隨機游走的用戶標簽更新算法;(3)用戶推薦,本文首先使用工具 Taxonomy對開發(fā)者社區(qū)中的標簽建立語義樹,通過語義樹對開發(fā)者社區(qū)中的問題標簽進行拓展,最后協(xié)同獲得的用戶標簽關系進行用戶推薦排名.

2.1 跨社區(qū)相同用戶識別

通過統(tǒng)計不同社區(qū)中用戶參與問題回答行為,本文得到用戶在回答問題種類上的偏好,并以用戶與標簽的關系表示.本文通過分析兩個社區(qū)中名字相似的用戶在不同問題上的偏好來識別不同社區(qū)中的相同用戶.對于計算兩個社區(qū)中用戶的相似度sim(a,b),本文主要通過計算用戶名稱相似度simn(a,b)與用戶標簽相同數(shù)量ω來獲得,由定義1可得公式(3).

其中,LCS()為計算用戶a與用戶b名字最長公共子串的長度,通過與二者中較長子串長度進行相除,得到用戶名稱相似度.這里,在衡量用戶名稱相似度時,與計算文本間相似度不同的是,本文未使用計算不用戶名稱之間的最長公共子序列而使用二者間最長公共子串.因為通過分析網(wǎng)絡中用戶在設定用戶名稱時,在首要期望的名稱已被其他用戶占用或者無法使用自己期望的特定字符的情況下,很大的可能會以用戶名稱加上一定的后綴或者插入一定的字符作為用戶名進行設定.如果僅對于二者的公共子序列進行比較,在某些情況下可以尋找到相比尋找公共子串更相近的用戶名稱.但是該方法忽略了用戶名本身字符的連接,很可能在相似度高的情況下仍然識別兩個完全不相關的用戶.并且在識別表現(xiàn)相近的情況下,計算公共子序列的開銷要遠大于計算公共子串.

在獲取用戶名稱之間相似度之后,通過與用戶間相同標簽數(shù)量以一定比例進行相加,可以得到最終用戶與用戶之間的相似度sim(a,b).通過計算sim()并設立一定的閾值,本文獲得不同開發(fā)者社區(qū)中可能為同一用戶的個人并進行分析.本文在識別用戶時發(fā)現(xiàn),忽略空格以及字符大小寫的情況下,兩個社區(qū)中包含大量名稱完全相同的用戶.但是通過訪問用戶個人主頁本文發(fā)現(xiàn),雖然在名字完全相同且用戶信息完整的情況下二者是同一用戶的可能性很高,但仍然存在著兩個社區(qū)的兩位用戶有著完全不同的興趣偏好.本文認為,不具有相同偏好的用戶不可能成為不同社區(qū)中的相同用戶.因此,在名稱相似度作為識別不用社區(qū)中相同用戶的條件下,本文引入了通過對比兩個用戶的標簽進一步作為識別用戶的參考條件.如公式(4)所示,在識別用戶時,如果兩位用戶不具有相同的標簽,二者的相似度直接設置為 0;在二者具有相同的標簽的情況下,對二者名稱相似度以及相同標簽數(shù)量的權重以一定的形式相加獲得最終二位用戶的相似度.本文結合用戶自己標記與本文統(tǒng)計的用戶標簽作為該用戶的代表偏好,在保證對比相似度不大于 1的情況下,在對權重計算時對其進行取對數(shù)計算以減小相同標簽數(shù)目過多對相似度判斷造成的影響,則有:

其中,α代表在計算用戶間相似度時保證名稱相似度時,為了保證識別相同用戶準確度而設定的用戶相同標簽數(shù)量系數(shù),通過之后實驗設定不同α最終取識別用戶效果最好的α值;ω代表識別用戶該參考用戶在兩個社區(qū)間相同的標簽數(shù)量.由于包含相同子串的用戶數(shù)量可能不止一位,因此,本文首先通過獲得具有大于一定數(shù)值的用戶相似度的用戶進行識別,在之后保證識別準確度的前提下,調(diào)整獲取相同用戶間計算sim()的閾值來識別更多的用戶.

2.2 基于重啟隨機游走的用戶更新算法

在進行重啟隨機游走更新前,本文首先建立兩個代表用戶與用戶關系和用戶與標簽關系的矩陣.用戶與用戶關系矩陣中每個元素代表每兩位用戶在開發(fā)者社區(qū)中的關系,因此用戶與用戶矩陣中元素rij可以通過進行用戶之間關系權重疊加進行計算,公式(5)所示:

權重計算中,n1代表用戶i作為發(fā)問者發(fā)表主題且用戶j參與該主題的主題數(shù)量,n2代表二者同時作為參與者在一個主題的主題數(shù)量即二者均不為發(fā)問者,I為所有主題總數(shù),α代表問題發(fā)問者對于其他用戶的影響力.在之后的實驗中,α取值為 0.66,即發(fā)布主題者對于參與主題的人權重加成是二者同時參與一個問題的權重加成的二倍.并且在實驗中本文也發(fā)現(xiàn)這種設定所獲得結果要優(yōu)于兩種權重直接相加.

但是在后續(xù)實驗中本文發(fā)現(xiàn),在利用用戶與用戶之間的關系對用戶與標簽之間的關系進行更新時,存在部分關系系數(shù)較大的用戶在更新時使一些用戶的標簽權重數(shù)值過大,在推薦時造成極大的影響.因此在統(tǒng)計用戶關系權重之后,本文對于用戶與用戶之間的關系rij進行歸一化處理,由定義2可得公式(6),以防止上述情況的發(fā)生.至此,可以獲得用戶與用戶關系矩陣如下.

與此相似,構建用戶與標簽矩陣需要對用戶在開發(fā)者社區(qū)中問題的回答數(shù)據(jù)進行采集.用戶對于標簽的權重計算公式如公式(7)所示.

其中,s1,s2分別代表用戶在Github與在Stack Overflow中對于標簽j的偏好次數(shù),T代表兩個開發(fā)者社區(qū)中所有的標簽數(shù)目,β代表Stack Overflow中用戶對于標簽喜好的權重.由于用戶與標簽之間的關系直接作為推薦時的參考信息,不需要進行歸一化處理.至此,獲得用戶與標簽關系矩陣.

受到重啟隨機游走算法的啟發(fā),本文設計了一個利用用戶與用戶之間的關系對用戶與標簽之間的關系進行更新的算法.重啟隨機游走本質(zhì)是從圖中的某一個節(jié)點出發(fā),每一步面臨兩個選擇,隨機選擇相鄰節(jié)點,或者返回開始節(jié)點.重啟隨機游走算法設定參數(shù)a為重啟概率,1-a代表移動到相鄰節(jié)點的概率,經(jīng)過一定次數(shù)的迭代到達平穩(wěn),平穩(wěn)后得到的概率分布可被視作受開始節(jié)點影響的分布,而利用重啟隨機游走更新所獲結果可以視作受到用戶與用戶之間關系影響得到的用戶與標簽之間的關系.本文將矩陣MT視為最原始的用戶-標簽關系矩陣,在一系列迭代過程中,不斷對MT進行更新,最后獲得的作為最終獲得的用戶-標簽矩陣.在每次迭代中,本文將第n次迭代下用戶與標簽之間的關系dij與矩陣用來表示,rik與dkj代表迭代時矩陣內(nèi)的元素.因此,本文可以用如下的公式(8)進行計算.

其中,p(uk)為一個返回用戶uk所指向的所有的用戶的函數(shù).為了保證迭代過程的收斂,本文引用了一個隨機重啟變量c與重啟條件下的矩陣MP,則整個重啟隨機游走過程可以用公式(9)進行表達.

其中,重啟矩陣MP是由初始矩陣得出.

當整個隨機游走過程收斂到一個平穩(wěn)狀態(tài)時,可以獲得一個穩(wěn)定的用戶-標簽關系分布矩陣,其中的用戶與標簽之間的關系即為本文所需求最終目標,即一個概率分布矩陣.本文認為,當所有元素滿足公式(10)條件時,整個過程即為收斂:

通過控制收斂率可以控制重啟隨機游走進行的次數(shù).通過設置不同的重啟率,可以獲得多種情況下使用重啟游走更新后的用戶-標簽關系.

2.3 基于Taxonomy的用戶推薦算法

在搜索內(nèi)容擴充處理部分,本文使用了分類工具 Taxonomy.Taxonomy是一種簡化的知識庫,它在表示標簽之間的上下義關系時省略了許多節(jié)點之間的復雜的語義關系.Taxonomy在結構上是一個多根樹,在本文中,每一個節(jié)點代表一個標簽,而每個標簽之下也會有 1個或多個子節(jié)點作為其子標簽.例如,標簽“Scrapy”在Taxonomy即為標簽“Python”的一個子節(jié)點.通過 Taxonomy的擴展,可以有效地擴大問題標簽的命中范圍與權值的準確度.

通過獲得的Taxonomy樹,本文設計了如算法1所示的搜索內(nèi)容擴充算法.搜索內(nèi)容擴充算法是對于本文提取出的所有單詞T,保存所有在本文所提取的標簽中出現(xiàn)的部分.如果問題文本中提出單詞{this,is,java,spl},T作為輸入取開發(fā)者社區(qū)中存在標簽即為{java,sql}.對于所有T中的節(jié)點,都會進行如下處理:在確定原有單詞標簽的權重前提下,對于有父輩節(jié)點的單詞,將其父輩節(jié)點以及一個關系系數(shù)c1加入輸出Tq中;同理,之后對于有兄弟節(jié)點的單詞,本文將其兄弟節(jié)點以及一個關系系數(shù)c2加入輸出Tq中.通常情況下,c1與c2可以取相同的系數(shù)以簡化算法.其中,Add(ti,a)函數(shù)是將權重a加進標簽ti在結果集的權重,GetParent(ti)以及GetBrother(ti)分別獲得當前節(jié)點ti的父親節(jié)點和兄弟節(jié)點,權重的計算方法本文沿用了文獻[2]中的設置.最后,算法輸出的Tq中,tn代表原標簽以及根據(jù)Taxonomy新加入的標簽,每個tn后的wn代表該標簽經(jīng)過算法1處理后所占權重.

算法1.搜索內(nèi)容擴充算法.

用戶排名算法如算法2所示,其中,Tq代表本文提取并引入后每個關鍵詞/標簽的權重,T代表更新前用戶對于單個問題所打的標簽,Ut為本文更新后用戶與標簽之間的關系向量,wn代表每個用戶對于各個標簽的偏好的向量.為了保證兩部分權重的平衡,此處在權重計算中,ω1和ω2取值均為 0.5.當然,后續(xù)可以根據(jù)不同的情況對ω的數(shù)值進行調(diào)整.在用戶推薦過程中,首先對用戶排名數(shù)組初始化,在初始情況下,每個用戶所具有的推薦權重為0.而推薦部分本文對兩部分內(nèi)容進行了參考,即使用Taxonomy更新后的關鍵詞參考推薦,與使用未更新的用戶直接標簽的內(nèi)容進行推薦.將兩部分內(nèi)容以一定權重求和,作為推薦權重.對于使用 Taxonomy更新后的關鍵詞權重更新,本文通過計算關鍵詞在文檔中的權重與用戶與標簽間權重二者的乘積,獲得每個用戶對于文檔的偏好權重.對于未更新的用戶對于文檔直接打標簽部分,本文默認文檔用戶中所有手動標記標簽權重均相等,在進行歸一化處理后,同用戶與標簽之間權重進行乘運算,獲得未使用 Taxonomy的用戶標簽推薦.二者在一定權重下(ω1,ω2)相加獲得最終每個用戶對于文檔的偏好程度,再由高到低進行排名后,通過網(wǎng)站進行推薦.其中,Scores()為通過計算用戶標簽向量與問題中標簽權重向量進行乘積來獲得的用戶推薦積分的函數(shù).

算法2.用戶排名算法.

3 實驗與分析

3.1 實驗數(shù)據(jù)集

由于本文算法所需數(shù)據(jù)基于開發(fā)者社區(qū)中的用戶行為,需要利用用戶與用戶之間的關系信息以及用戶與標簽之間的偏好信息進行實驗,因此通過抓取開發(fā)者社區(qū)中的所有有效問題,以獲得有意義的用戶在開發(fā)者社區(qū)中的行為信息.本文使用Python中的工具Scrapy進行開發(fā)者網(wǎng)站中的數(shù)據(jù)抓取工作.首先收集開發(fā)者社區(qū)中的標簽信息,通過標簽進行初步篩選,爬取在本文標簽分類下每類標簽包括的問題信息;進一步,爬取每個問題下所有用戶的參與行為,統(tǒng)計用戶與用戶和用戶與標簽的信息;最后,在獲得用戶有效信息之后,通過數(shù)個預處理方法對所獲數(shù)據(jù)進行標簽語義處理,包括根據(jù)問題評分進行有價值的主題篩選與有效用戶分類等,得到用于實驗的有效數(shù)據(jù)集.本文數(shù)據(jù)集見表1,本文收集的數(shù)據(jù)包含截止到2017年10月的Stack Overflow以及Github兩個社區(qū)中的共計117個標簽下約140萬有效主題貼.對所有主題貼統(tǒng)計參與其中的用戶,并排除無法作為推薦參考的游客賬號以及類似google的大型公共賬號,累計獲得兩個開發(fā)者社區(qū)中的約40萬有效注冊用戶的id及其在有效問題下的活動信息.

Table 1 Data set of our paper表1 本文數(shù)據(jù)集

3.2 用戶識別實驗

如圖4所示為本文統(tǒng)計高度相似用戶名稱并進行用戶識別的實驗.前2w名作為活躍部分的用戶中,本文統(tǒng)計出確定為不同社區(qū)間用戶是否相同的占比率與2w名之后用戶無太大區(qū)別,即所有用戶活躍區(qū)間中,可以完全直接確定二者為相同用戶的所占比例相同,并且在確定條件下二者具有至少 1個標簽相似且大部分情況為至少擁有 2個相似標簽.但由于非?；钴S的用戶本身所具有的標簽數(shù)量很高,會造成在跨社區(qū)比較時確定二者為相同用戶的概率增加,而具有相同標簽數(shù)量較多但無法確定為相同用戶的情況會減少.排除活躍用戶普通用戶與不活躍用戶都在發(fā)現(xiàn)名稱相近且具有相同標簽但無法確認占有較高的比率.由于 Github可以賦予用戶的標簽數(shù)量稀少,這可以通過圖中無法確定的用戶部分即深藍色部分可以發(fā)現(xiàn),大部分非活躍且無法確定的用戶中具有一個相同標簽的比重占很大部分.而對不同社區(qū)中可以確定的相同用戶,僅有一個標簽相同的情況則相對較少.因此,本文在對用戶識別時,將相似度閾值設為至少大于 1,即如果兩位用戶在不同社區(qū)具有相同的名稱但標簽數(shù)相同數(shù)目不大于1,則不將他們識別為同一開發(fā)者,這樣可能會損失大約2%現(xiàn)實可以確定為同一用戶的跨社區(qū)人員.

Fig.4 Overall ratio of three users under sampling conditions圖4 抽樣條件下的3種用戶所占總體比率

識別用戶的實驗中,不同標簽選擇表現(xiàn)基本相同.例如在標簽 sql下,識別用戶幾種情況所占比率為 14%,21%和25%.在閾值設定為1的情況下,除了統(tǒng)計存在相似用戶名稱的用戶占比,本文將標簽熱度進行分類,即標簽具有主題大于20w、大于10w以及大于1w,并對α分別取值2～7進行實驗,獲得識別用戶數(shù)量的占比率結果如圖5所示.可見,對于兩個社區(qū),在α取值大于3后,識別用戶數(shù)量占比趨于平穩(wěn),為本文算法可以識別出的相同用戶數(shù)量占所有用戶比例.

Fig.5 Differentαvalues and number of identified users in the label area圖5 不同α取值與標簽區(qū)域下的識別用戶數(shù)量

已有的跨社區(qū)用戶識別算法多數(shù)是基于用戶名稱與主頁之間的關系進行識別,與本文基于用戶標簽偏好的識別條件不同.部分算法通過實驗可以識別出的跨社區(qū)用戶數(shù)量約占實驗用戶數(shù)量的 20%.相對該算法,本文可以確定識別的用戶數(shù)量已達到15%,并且還有10%以上高概率相似的用戶可以作為相同用戶參考,因此,本文算法在保證識別準確度的前提下,在識別用戶的數(shù)量上也有著較好的表現(xiàn).但相對本文變量的取值適用于Stack Overflow以及Github兩個社區(qū),如果應用到其他社區(qū),需要對數(shù)據(jù)進行重新統(tǒng)計及變量的重新計算.

3.3 用戶標簽更新實驗

重啟隨機游走的重啟率通常情況下設置為 0.75,重啟率代表更新后的用戶矩陣受原用戶矩陣數(shù)值的影響,本文希望可以通過控調(diào)整重啟率(restart)以獲得更加準確的用戶對于標簽數(shù)量的偏好以及更加準確的用戶對于標簽偏好的權重.對于標簽更新實驗,將標簽按照當前開發(fā)者社區(qū)具有主題數(shù)量劃分為3個區(qū)域,對3個不同活躍度標簽分別進行F-measure的計算并取平均值作為該區(qū)域中的標簽更新顯著程度,其中3個區(qū)域分別為主題帖數(shù)量大于10w的熱門標簽約50個、主題帖數(shù)目大于5w的非熱門標簽約100個和剩下的所有主題帖數(shù)目大于1w的冷門標簽,實驗結果如圖6所示.

Fig.6 Different label areaF-measure values under different restart rates圖6 不同重啟率下的不同標簽區(qū)域F-measure值

更新標簽時,熱門標簽中,尤其是具有 100w 以上主題帖的標簽在用戶標簽更新后無論重啟值的多少,在迭代達到收斂條件后一定會被引入到每個用戶的偏好下,根據(jù)重啟值的增加,新加入的標簽權重也隨之增加.雖然對用戶標簽更新會造成所有用戶都具有熱門標簽偏好的情況,并且更新后原對標簽具有較高權重的用戶偏好值也會下降.對熱門標簽問題下的用戶推薦進行分析,如果問題中含有熱門標簽且熱門標簽在問題中的權重較高,則熱門標簽偏好值較低的用戶幾乎不會出現(xiàn)在推薦用戶中.因為本文是根據(jù)用戶適合問題的權重來進行用戶推薦,而新加入標簽與更新用戶標簽權重的主要功能分別是為冷門問題提供更多的用戶以及推薦用戶時平衡用戶排名權重大小.對在某個領域具有較高地位的用戶進行權重更新,則對于該用戶的領域地位不會造成太大影響.

3.4 用戶推薦實驗

3.4.1 NDCG

NDCG(歸一化折損累積增益)允許以實數(shù)形式對排名進行相關性打分.本文中,NDCG是由通過排名結果計算DCG值得出的,二者的計算公式如公式(11)與公式(12)所示.

兩個公式中,K代表推薦的列表長度,即推薦用戶數(shù)量.公式(11)中,DCG為通過本文算法得到的用戶排名后推薦用戶的相關性.公式(12)中,iDCG為理想狀態(tài)下DCG的值.iDCG的計算是本文對實驗選擇的問題使用原始用戶標簽權重衡量用戶與問題的相關性并添加標記,即DCG計算中,r(l)代表該用戶在推薦時的相關等級.由于推薦用戶時可以被本文尋找的用戶通常情況下都為活躍用戶,因此根據(jù)用戶數(shù)據(jù),在本文中,r(l)的取值分別為2:非常適合,1:適合與0:不適合.這里不包括令r(l)的取值為-1即推薦結果是錯誤的情況,因為可以推薦出的用戶一定會對問題中的一個或多個標簽進行過問題回答,因此只能判斷這位用戶適不適合于回答這個問題.并且在之后的實驗中,對于log2(i+1)中i的取值,本文分為兩種情況,即首先計算所有用戶的價值均相等的情況,來分析本文抽取一定數(shù)量下用戶的準確度;以及根據(jù)用戶排名,用戶價值遞減的分析推薦用戶的排名的準確度.

3.4.2 實驗結果

用戶的推薦方面,本文選取Stack Overflow中不同熱門程度下的標簽作為當前問題的最重要標簽進行推薦實驗.本文在實驗中將標簽以熱度劃分為3類,并且每類標簽之間的表現(xiàn)在實驗中基本相同.

如圖7所示,實驗中本文分別選取熱門標簽下編程領域中的幾個常用標簽:java,sql與scala以及冷門標簽下的android json.在其他冷門標簽領域中,本文選取了“編程表現(xiàn)”下的兩個標簽:optimization與inheritance和問題以概念為主的mvc標簽.實驗中,選擇將這些標簽作為主要標簽的問題,即問題在提取標簽權重后該標簽的權重數(shù)值最高,代表問題與主要標簽的相關度最高,每個問題也包含除主要標簽的其他標簽.實驗包含了兩個社區(qū)中的熱門和冷門以及 3個不同領域下的標簽,可以代表本文算法在兩個社區(qū)中的不同的熱度領域以及推薦方向領域推薦的表現(xiàn).

Fig.7 Consider user’s recommended performance under different master tags under the ranking weights圖7 考慮排名權重下不同主標簽下用戶推薦表現(xiàn)

實驗結果如圖7所示:在熱門標簽下,使用Taxonomy對于推薦準確度的提升有限以至不同抽樣下推薦的準確度在部分標簽下提升不明顯.因為提出問題時,對于熱門標簽選擇偏好的人員遠多于冷門標簽,活躍人員對于標簽的偏好權重也很高.本文在推薦用戶時發(fā)現(xiàn),在進行java等熱門標簽推薦時,使用3種推薦方法所獲得的用戶排名大致相同,僅推薦用戶時,根據(jù)用戶的權重排名有微小的變化.在本文算法下,由于用戶對于標簽的權重經(jīng)過計算后,過熱門標簽下的偏好的數(shù)值通常會減少,因此使用本文方法推薦用戶之間權重相差值較小,相對于參考未使用本文策略算法更新的用戶偏好矩陣進行推薦的用戶之間差值不明顯.但結果上,二者推薦的用戶排名結果大致相同.因此,本文也進行了不考慮用戶之間推薦權重的實驗,假定選中的前 20名用戶所代表的推薦權重一樣,即在NDCG的計算之中,log2(i+1)中i恒定為1,結果如圖8所示.

Fig.8 Do not consider the NDCG value under the user’s ranking weight圖8 不考慮用戶排名權重下的NDCG值

可以看出,在不考慮用戶權重的情況下,本文算法進行用戶推薦的準確值有一定程度的增加.說明在問題屬于熱門標簽領域的情況下,本文算法和普通推薦結果之間差距較小,但也存在至少 3%的提升率,部分熱門標簽下可以達到 10%.并且本文算法對于推薦一定數(shù)量用戶進行回答的表現(xiàn)要相對使用普通條件推薦表現(xiàn)更加準確.即在于冷門標簽的推薦情況,通過搜索內(nèi)容擴充,可以將問題的描述標簽數(shù)量增加,并且也擴展了用戶的標簽數(shù)量,相對于未使用 Taxonomy的條件進行推薦,明顯可以推薦更多數(shù)量且更加適合回答問題的用戶.非熱門標簽領域下,提升可以達到 10%以上,部分冷門標簽的提升率可以達到 26%.對于未更新的問題用戶標簽種類,單個用戶活躍的標簽數(shù)量較少,造成了冷門標簽對應的用戶數(shù)量稀少.加入對于用戶標簽關系的更新,可以擴大單個用戶在推薦時命中相應領域的范圍,進而擴大推薦時可以參考的用戶數(shù)量.雖然當前研究環(huán)境下熱門標簽推薦已經(jīng)達到一定的準確度,但是本文算法在熱門標簽領域上的推薦準確度仍然有一定的提升;并且根據(jù)本文統(tǒng)計,熱門標簽數(shù)量僅占所有實驗標簽的8%.而本文的算法可以在其余非熱門標簽領域下進行更為高效的問題推薦.

4 相關工作

本節(jié)將對與本文工作相關的用戶識別、重啟隨機游走以及Taxonomy分如下3節(jié)進行介紹.

4.1 用戶識別

為了識別不同開發(fā)者社區(qū)中的同一用戶,當前已有如下相關研究.

· Goeminne等人[3]將社區(qū)中的每個用戶表示為一對二維向量(用戶名,電子郵件).他們提出:如果兩對向量共享至少1個元素或者至少1個共享元素對具有大于某個閾值minLen長度的相同子串,則他們是同一個人.

· 之后,Bird等人[4]提出了更先進的算法.他們沒有僅僅定義一些簡單的匹配規(guī)則,而是首先測量文本間的Levenshtein距離,Levenshtein是一個用來衡量兩個用戶名之間的相似性的參數(shù);

· 然而,Goeminne和Bird在研究中都沒有考慮名字和電子郵件中的語義信息.針對該問題,Erik等人[5]提出了一種基于語義的方法,通過應用潛在語義分析(LSA)來識別同一用戶.

社交網(wǎng)絡中的身份鏈接問題也是Facebook和Twitter等社交網(wǎng)絡公司的熱門研究課題.Iofciu等人[6]將每個用戶配置文件被表示為一個向量,通過計算兩個向量之間的相似度來鏈接用戶.另一方法將用戶生成的內(nèi)容(如推文)以及用戶行為(如書寫風格)也考慮在內(nèi).Liu等人[7]提出了一個鏈接社會身份的框架 HYDRA,該方法考慮用戶的異構行為,建立一致性矩陣來模擬不同社交網(wǎng)絡中的結構一致性.但是實際上,開發(fā)者社區(qū)中的用戶識別與社交網(wǎng)絡不同,人們在開發(fā)者社區(qū)中所能產(chǎn)生的內(nèi)容的質(zhì)量和類型遠不及社交網(wǎng)絡中的內(nèi)容.例如,開發(fā)者社區(qū)的用戶不允許共享他們的位置.另外,一些開發(fā)者社區(qū)在用戶之間缺乏拓撲結構,如 Stack Overflow中的用戶間無法跟隨.

4.2 重啟隨機游走

隨機游走(random walk)算法是從一個或一系列頂點開始遍歷一張圖.在任意一個頂點,遍歷者將以概率1-a游走到這個頂點的鄰居頂點,以概率a隨機跳躍到圖中的任何一個頂點,稱a為跳轉(zhuǎn)發(fā)生概率.每次游走后得出一個概率分布,該概率分布刻畫了圖中每一個頂點被訪問到的概率.用這個概率分布作為下一次游走的輸入,并反復迭代這一過程.當滿足一定前提條件時,這個概率分布會趨于收斂.收斂后,即可以得到一個平穩(wěn)的概率分布.重啟隨機游走算法是在隨機游走算法的基礎的改進.從圖中的某一個節(jié)點出發(fā),每一步面臨兩個選擇,隨機選擇相鄰節(jié)點,或者返回開始節(jié)點.算法包含一個參數(shù)a為重啟概率,1-a表示移動到相鄰節(jié)點的概率,經(jīng)過迭代到達平穩(wěn),平穩(wěn)后得到的概率分布可被看作是受開始節(jié)點影響的分布.重啟隨機游走可以捕捉兩個節(jié)點之間多方面的關系,捕捉圖的整體結構信息.當前研究下,重啟隨機游走的工作主要集中于查詢、檢索及算法的優(yōu)化方面.Chao等人[8]在查詢方面提出了兩種算法——Squeeze和Ripple,其中,Ripple通過估計落在節(jié)點附近的重啟隨機游走分數(shù)采取相應策略,而不需要評估附近節(jié)點,在醫(yī)療查詢、廣告等方面有不錯的表現(xiàn).檢索方面,Masaki等人[9]提出一種基于共引網(wǎng)絡的文件推薦算法,通過解析引用文獻的全文為共引網(wǎng)絡中文件間的邊設立權重,并使用重啟隨機游走應于該加權圖中進行文檔推薦.Yu等人[10]提出一種動態(tài)調(diào)度算法,可以有效優(yōu)化動態(tài)更新時,使用重啟隨機游走算法計算相似程度的開銷.

4.3 Taxonomy

本文受到文獻[2]中Zhu等人針對開發(fā)者社區(qū)Stack Overflow所提出的Taxonomy算法的啟發(fā),建立標簽語法樹協(xié)助用戶推薦.Zhu等人提取標簽在開發(fā)者社區(qū)以及百科中的文本描述,通過這些文本分析標簽之間的語義關系,建立多棵以某一標簽為根節(jié)點且標簽間具有父子關系的標簽語義樹,可以準確體現(xiàn)出開發(fā)者社區(qū)中標簽間的關系.有關分類學(Taxonomy)的其他研究情況如下.

· 基于百科的方法主要關注從百科中提取概念層次結構.Wiki Taxonomy[1]從維基百科分類系統(tǒng)構建分類,它包含105 000個包容關系,準確率為88%.Wu等人[11]通過本體生成器(KOG),使用馬爾可夫邏輯網(wǎng)絡(MLN)來預測維基百科信息框類之間的包含關系.Yago2[12]將Wikipedia類別鏈接到WordNet同義詞集,Yago的實驗中有超過20萬個類別和40萬個包容關系,準確度估計為96%.

· 但是,開發(fā)者網(wǎng)站中的標簽之間沒有結構信息,難以應用基于百科的方法.基于網(wǎng)絡的方法是在使用自由文本或社會標簽的背景下提出的,Hearst模式是最被廣泛使用于基于自由文本的方法.Probase[13]構建了最大的分類標準,其中包含17億個網(wǎng)頁中的270多萬個類別.

· 對于基于社會標簽的方法,Mianwei Zhou等人[14]引入了一個無監(jiān)督模型來自動從社會注釋中派生出層次語義.Jie Tang等人[15]提出一種學習方法來捕捉標簽的層次語義結構.Xiance Si等人[16]提出3種方法來估計標簽之間的條件概率,并使用貪婪算法消除冗余關系.Huai等人[17]描述了一種從標簽中提取本體結構的綜合方法,該方法利用了低支持關聯(lián)規(guī)則挖掘的功能,并輔以上層本體.WordNet.Zhishi.schema[18]是第1個從流行的中文網(wǎng)站的標簽和類別發(fā)布一般分類標準的工作.

這些傳統(tǒng)基于標簽的通用域方法僅使用注釋文檔來幫助包含檢測.由于百科描述開發(fā)者社區(qū)還包含其他信息,因此開發(fā)者社區(qū)更具有域特定性.傳統(tǒng)的基于標簽的方法可能不是最好的,因為開發(fā)者社區(qū)中的附加信息可能會增加分類結構的性能.

5 總結與展望

5.1 工作總結

前面詳細介紹了本文的主要工作,包括數(shù)據(jù)集制作、跨社區(qū)網(wǎng)絡建立以及用戶標簽更新與問題內(nèi)容擴展等,下面對全文工作加以總結.

(1) 數(shù)據(jù)集制作

由于本文實驗所需數(shù)據(jù)要求按標簽將主題分類后處理用戶信息,且需要獲得主題的評分以判斷主題是否具有實驗價值,當前文獻中提供的開源數(shù)據(jù)集無法滿足本文對于實驗數(shù)據(jù)的需求.因此,本文通過對開發(fā)者社區(qū)進行數(shù)據(jù)抓取,制作新的開發(fā)者社區(qū)用戶信息數(shù)據(jù)集用于實驗.全部數(shù)據(jù)集制作歷經(jīng) 3個月的網(wǎng)站數(shù)據(jù)抓取及后處理工作,包括根據(jù)問題權重判斷問題是否有效、過濾游客或者無效用戶等.最后獲得了包含 117個標簽下170萬有效主題貼,累計40萬以上用戶的大規(guī)模真實實驗數(shù)據(jù)集.

(2) 跨社區(qū)網(wǎng)絡建立

開發(fā)者社區(qū)中的問答推薦通常采取等待社區(qū)內(nèi)會員回答或者推薦給內(nèi)部用戶進行回答的方式,因為存在用戶標簽自定、不對稱活躍、關鍵詞集封閉等現(xiàn)象,并采取回復等待的方式,這種方法可能會導致問題推薦后反饋不及時,局限性較大.針對該問題,本文提出一種跨社區(qū)的問答推薦算法,通過建立跨社區(qū)的用戶網(wǎng)絡,將多個開發(fā)者社區(qū)中的用戶連接起來,構建多個開發(fā)者社區(qū)中用戶共存的網(wǎng)絡進行問答推薦.在提高問題命中回復者的準確率的同時,通過關鍵詞集擴充,增大了推薦時有效用戶的范圍,使問題得到及時、準確回復的可能性大大增加.

(3) 用戶標簽更新與問題內(nèi)容擴展

本文設計的基于重啟隨機游走的用戶標簽更新算法與基于 Taxonomy的用戶推薦算法都是為了提高問題推薦的準確度以及擴大問題推薦的有效用戶命中范圍.基于重啟隨機游走的用戶更新算法屬于推薦系統(tǒng)中協(xié)同過濾算法的一種,通過使用用戶與用戶之間的關系,對用戶與標簽之間的權重進行一定程度的更新.由于用戶對于自我的定位較為主觀,而本文提出的算法可以分析用戶在開發(fā)者社區(qū)中的表現(xiàn),通過統(tǒng)計用戶在各個領域下的問題回答參與情況和與其他用戶的互動行為得出用戶個人數(shù)據(jù).之后,通過本文算法得到更為符合用戶定位的用戶標簽偏好.對于開發(fā)者社區(qū)中的問題回復者推薦,僅依據(jù)文本中提取得到的關鍵詞進行推薦可能會丟失有效的推薦用戶.本文通過 Taxonomy的語義樹,對提取的關鍵詞集進行拓展,利用拓展后的問題標簽及其權重協(xié)同更新后的用戶標簽矩陣進行推薦.實驗表明,本文的方法對于推薦用戶的數(shù)量提升明顯,并且準確度也有較高的提升.

5.2 未來展望

本文是針對開發(fā)者社區(qū)中的幾點現(xiàn)象,提出解決策略來提高開發(fā)者社區(qū)進行用戶推薦效率以及準確度.在用戶識別方面,本文對用戶名稱以及標簽相似度提出一定的閾值,根據(jù)閾值來確定識別用戶的范圍.本文提出這種方法對于特定的兩個社區(qū)適用性較強,但是仍有一定的局限性,將來可以在此算法基礎上,從更為復雜的用戶之間的關系入手來識別不同開發(fā)者社區(qū)中的相同用戶.而用戶推薦方面還有推薦系統(tǒng)共同面臨的冷啟動、降噪等問題待解決,解決這些問題可以在本文基礎上更多地提升推薦問題獲得反饋的效率以及準確率.本文已經(jīng)通過實驗證明,算法在開發(fā)者社區(qū)Stack Overflow以及Github中具有可實施性,下一步可以將該算法改良并推廣到多個開發(fā)者社區(qū)中進行測試.