孫 凱, 劉宣彤, 張 莉, 劉華虓, 王 禹, 郜山權
(1. 吉林大學 計算機科學與技術學院, 長春 130012; 2. 外交學院 英語系, 北京 100037;3. 白城醫學高等??茖W校 信息化學院, 吉林 白城 137000)
目前, JavaScript編程語言已廣泛應用于Web瀏覽器和服務器上[1], 為幫助開發者分享和重用代碼, npm(node package manager)不僅是管理JavaScript第三方庫的管理工具, 同時也已成為分享代碼的開源平臺. 隨著npm包(第三方庫)的不斷發展, 越來越多的軟件系統依賴于npm包所提供的多樣且高效的功能.
當開發者需要一個合適的npm包滿足開發需求時, 其龐大的數量使開發者需耗費大量的時間用于搜索. 而標簽作為簡潔、 直觀的描述方式, 為開發者在搜索過程中提供了有效的幫助[2]. 開發者不僅可通過瀏覽標簽快捷地獲得包的描述信息, 而且可通過點擊標簽獲得與該標簽相關的所有包, 即通過使用標簽縮小搜索的范圍[3]. 包的創建者為創建的包打上恰當的標簽可提高其被索引到的概率, 從而被更多的開發者使用. 但有超過40%的npm包沒有標簽, 而且由于賦予標簽的方式和標簽的內容都具有極大的自由度, 使得一些包的標簽質量較低, 無法具有展示包功能的作用.
因此, 本文提出一種為npm包推薦標簽的自動化方法. 首先, 對npm平臺中現有的標簽進行分析, 根據標簽內容與彼此之間的相關程度解決標簽同義問題, 建立標簽庫; 其次, 利用包的Readme文檔進行詞向量的訓練, 借助詞向量挖掘出包的描述文本與標簽庫中標簽的聯系; 最后, 由計算得到的關聯程度進行排序生成標簽推薦列表, 完成標簽推薦工作.
本文首先分析npm社區中已存在的標簽, 用關聯關系挖掘算法構建標簽關聯關系網絡圖, 并利用社區檢測算法將標簽聚成社區, 在每個標簽社區中, 整合具有相同語義的標簽, 以解決標簽同義的問題并生成標簽庫; 然后利用word2vec技術將npm包的Readme文件作為訓練文本進行詞向量的訓練; 最后根據得到的標簽庫與生成的詞向量, 給定一個沒有標簽的npm包, 以計算其Readme中的單詞詞向量與標簽庫中標簽的相關度, 生成標簽推薦列表. 方法流程如圖1所示.
圖1 方法流程Fig.1 Flow chart of method
由于npm包的創建者可自由地為其包打上任意內容、 任意數量的標簽, 無任何約束, 從而導致npm社區的標簽數量龐大, 種類繁多, 卻沒有一致性[4]. 標簽作為展示包特點的窗口, 應具有簡潔、 直觀、 易懂的特點[5], 但打標簽是一個具有分布式特點且不協調的過程, 使得npm社區出現很多冗余的標簽. 為達到推薦恰當標簽的目的, 本文首先對現有標簽進行分析整合, 構建一個合理的標簽庫.
在現有標簽中, 一些標簽的出現率極低, 因為這些標簽具有定制化的特性, 只適合于所屬項目. 但主要還是因為這些標簽的內容很難使大多數開發者認同, 無法得到廣泛使用. 此外, 很多標簽是以不同的語法形式表達相同的語義, 如log,logs和logging都是指代日志功能. 同一單詞的不同語法形式導致標簽的冗余, 從而在通過標簽進行搜索的管理過程中造成不便. 對于以單詞作為內容呈現的標簽, 除上述語法問題外, 還存在單詞縮寫和單詞同義問題, 這些問題統稱為標簽同義詞問題[6].
定義1標簽句TagSentence可定義為對于存在標簽的npm包p, 所屬于p的所有經過詞干提取和詞形還原的標簽{t1,t2,…,tn}構成的標簽集.
定義2標簽關聯關系ti?tj可定義為對于兩個標簽ti和tj, 若存在由關聯關系挖掘算法[7]得到的Lift(ti?tj)大于閾值threshold, 則認定兩標簽構成關聯關系:
其中confidence(ti?tj)計算擁有這兩個標簽的標簽句占只含有標簽ti的標簽句比例, support(ti)計算標簽ti出現在所有標簽句中的次數, #tagSent表示tagSentence的數量.
定義3標簽關聯圖G〈V,E〉定義為對于標簽關聯關系ti?tj, 標簽ti,tj作為圖G〈V,E〉中以無向線段連接的兩個節點, 所有存在標簽關聯關系的標簽構成節點集V, 其關聯關系構成邊集E.
圖2為標簽關聯圖的樣例.本文利用關聯社區檢測方法[8], 使位于同一社區內的標簽具有相同顏色.通過人工觀察標簽關聯圖, 找出擁有相同語義的標簽歸為一類, 在每類中選擇出現頻率最高的標簽作為代表標簽構建成標簽庫TL={T1,T2,…,Tn}.
圖2 標簽關聯圖樣例Fig.2 Sample of a tag correlation graph
npm包的Readme文檔詳細地給出了包的功能、 使用方法、 安裝環境等信息, 所以可利用Readme文檔中描述功能的文本計算與標簽的關聯. 本文將Readme描述功能的文本作為訓練數據, 利用skip-gram模型[9]得到的詞向量完成后續的標簽關聯度計算過程.
標簽是對每個npm包的總結概述或描述其所擁有的特性, 而這些內容開發者也可通過閱讀包的Readme 文檔得到, 因此可通過挖掘Readme文檔中的相關信息實現推薦標簽. 由于包的Readme文檔所呈現的內容角度多(簡介、 使用方法、 參與者等)且形式多樣(文字、 圖片、 表格等), 而只有介紹包功能的描述文本才是挖掘的對象, 所以本文首先對Readme文檔進行處理, 抽取其中介紹包功能的描述文本并進行預處理. 研究表明, 大多數包Readme文檔的第一章文字都是介紹包的主要功能和特性[10], 這與標簽所展示的內容相符, 所以抽取這部分內容作為可利用的描述文本.
定義4Readme Token序列Lp定義為對包p原始Readme文檔描述文本Dp移除其中的圖片、 表格及超鏈接后, 再進行分詞、 詞干提取及詞形還原得到的單詞序列.
圖3 Skip-gram模型Fig.3 Skip-gram model
詞向量是對單詞的低維向量表示, 其建立在具有相似含義的單詞在相似上下文中呈現的假設上. 單詞的詞向量可捕捉到單詞在文中的語義信息, 即可以使用詞向量比較單詞之間的語義相似度[11]. skip-gram模型[12]是一種高效的學習詞向量方法, 該模型由一個簡單的3層神經網絡組成, 包括輸入層、 隱藏層和輸出層, 如圖3所示, 其中w(t)是中心詞, 也稱為給定輸入詞.首先, 隱藏層執行權重矩陣和輸入向量w(t)之間的點積運算; 其次, 隱藏層中的點積運算結果被傳遞到輸出層; 最后, 輸出層計算隱藏層輸出向量和輸出層權重矩陣之間的點積, 再用Softmax激活函數[13]計算在給定上下文位置中單詞出現在w(t)上下文中的概率.通過skip-gram算法, 每個單詞都會得到一個詞向量. 某個詞在句子中的位置與中心詞的位置越近, 則通過skip-gram 算法獲得該詞的詞向量與中心詞的詞向量在向量空間中越接近, 即詞向量間的關系反映了詞在句子中的密切程度[14].
定義5詞向量Vw定義為以Readme Token序列R形式為樣本的訓練集在skip-gram模型中訓練得到的關于單詞w的向量.
由于標簽是以單詞的形式對npm包進行概括性地描述, 使得同樣具有描述功能且更詳細的Readme文檔中的描述文本會覆蓋標簽的內容, 即標簽會出現在Readme文檔中. 因此, 詞向量Vw也可作為以單詞w為內容的標簽T的向量, 記為VT.
本文通過計算描述文本中的單詞與標簽庫中標簽的詞向量相似度建立兩者之間的聯系, 再對取得聯系的標簽進行排序, 最終挑選出合適的標簽進行推薦. 詞向量的語義相似度可捕捉到文本中單個單詞與標簽的關聯程度, 而描述文本由許多單詞組成, 對所有單詞進行相似度的計算即能捕獲整個描述文本與標簽的關聯程度. 但單詞在描述文本中出現的頻次在一定程度上影響了文本的主題, 因此本文考慮詞頻對標簽相關度的影響, 從而更準確地計算描述文本與標簽的關聯程度. 算法描述如下:
步驟1) 抽取Readme文檔中的描述文本Dp并進行預處理, 生成 Token序列Lp;
步驟2) 對Token序列Lp中每個單詞w的詞向量Vw與標簽庫中每個標簽T的詞向量VT進行語義相似度的計算, 結果為Sw,T;
步驟3) 由單詞w在Token序列Lp中的詞頻TF(w)與Sw,T的乘積得到關于詞頻的相關度Rw,T, 并將結果按對應的標簽進行累加, 最終生成每個標簽與描述文本Dp的關聯程度RT;
步驟4) 根據標簽與描述文本的相關程度RT進行排序, 得到標簽推薦列表;
步驟5) 推薦排名前k的標簽.
算法1RT.
輸入: ReadmeRpof npm packagep; Tag LibraryTL={T1,T2,…,Tn};
輸出: topktags;
1) Extract descriptionDpfromRp;
2) Generate token listLpby preprocessingDp;
3) forw∈Lpdo
4) forT∈TLdo
5)Sw,T=Similarity(Vw,VT);
6)Rw,T=Sw,T×TF(w);
7)RT=RT+Rw,T;
8) end for;
9) end for;
10) rank the tags according toRT;
11) return the topktags.
在構建標簽庫和訓練詞向量兩個步驟中, 都需要可靠的數據樣本作為數據集. 本文在選取實驗數據集時進行如下操作:
1) 考慮到現有標簽數量龐大, 且很多標簽利用率極低, 本文選擇最流行的8 000個包作為樣本;
2) 根據對npm包的質量、 流行度、 維護程度的官方評價指標, 本文選擇在樣本中綜合評分在60分以上的包作為數據集, 以保證實驗數據有高質量的Readme文檔和標簽;
3) 對標簽數大于10的包進行過濾, 這是因為過多的標簽對npm是冗余的, 也無法確定哪些標簽必要, 最終數據集包含6 753個npm包;
4) 從數據集中隨機抽取100個包作為最終的測試集.
由數據集構建的標簽庫包含126個代表標簽, 代表標簽與其同義標簽的部分示例列于表1.
表1 代表標簽與其同義標簽的部分示例
實驗與兩種最新的針對開源軟件倉庫進行主題推薦的方法進行對比: 文獻[2]提出在Github開源軟件倉庫中利用多種文本信息訓練多標簽分類器以達到最好的主題預測效果; 文獻[6]提出基于Multinomial Naive Bayes算法對Github開源軟件倉庫進行主題分類以生成推薦主題. 其中兩種對比方法使用的數據集與本文方法一致, 本文進行多次實驗, 取最好結果進行對比.
選擇Recall@k作為實驗指標[15]. 在推薦方法的評價指標中, Precision@k和Recall@k是最常用的兩個指標, 而Recall@k更符合本文問題的設定, 定義為
其中n是測試集的總數, Tagp是包p的實際擁有標簽, Recp是方法為包p推薦的top-k標簽.
圖4 實驗結果Fig.4 Experimental results
圖4為本文推薦標簽方法的性能. 實驗結果表明, 本文方法能完成為npm包推薦標簽的工作. 由圖4可見: 推薦得分最高的3個標簽時, Recall@3為49.1%; 推薦得分最高的5個標簽時, Recall@5為56.3%, 即超過50%的標簽都推薦正確; 而推薦得分最高的10個標簽時, 正確率提高了10%. 本文方法在3項指標上都高于文獻[6]方法, 在Recall@5和Recall@10指標上接近文獻[2]方法, 且在更精細的Recall@3指標上本文方法性能更好.
對推薦錯誤的標簽進行分析, 主要原因有: 某些包的Readme文檔描述文本過少, 不能從中抽取到足夠的信息, 也無法通過詞頻顯現出描述文本的主題, 從而導致本文方法無法準確地構建包與標簽之間的聯系, 最后導致分析結果錯誤. 由于文獻[2]方法不僅利用了Readme文檔而且利用了文件名、 wiki等文本進行數據挖掘訓練, 所以在推薦數量較多標簽時效果略優于本文方法, 但當推薦標簽數量較少時, 本文方法準確率更高.
綜上所述, 本文提出了一種為npm包推薦標簽的方法, 通過解決現有標簽同義詞的問題建立標簽庫, 并基于詞向量挖掘包的描述文本與標簽之間的語義關系實現標簽推薦. 實驗結果表明, 該方法能有效完成推薦標簽的工作.