一種面向移動應用開發的第三方庫混合推薦方法

任 其，李 兵，2，王 健，趙玉琦，熊燚銘

1(武漢大學 計算機學院，武漢 430072)2(武漢大學 復雜網絡研究中心，武漢 430072) E-mail：renqilvsx@163.com

1 引 言

移動應用正在日益改變著人們的日常，據統計，截至2018年11月初，App Store上擁有的移動應用數量已經超過250萬個，下載量超過100萬次的app數量多達32788(1)http：//www.appbrain.com/stats/ free-and-paid-android-applications,2018.日益增長的用戶群為移動應用的開發提出了更高的要求，快速敏捷的開發出高質量移動應用以適應日益增長的用戶需求變得尤為重要.

在移動應用推薦方面，當前大多數研究工作都是從用戶的角度出發，即為用戶推薦合適的移動應用.在面對日益增長的移動應用時，研究者們關注的是如何將這大量的移動應用推薦給用戶以滿足他們的個性化需求.隨之產生了大量基于海量移動應用數據的推薦算法.例如文獻[1]提出了一種將興趣-功能交互和用戶結合起來進行移動應用推薦的方法，該方法在推薦過程中考慮到了用戶的隱私偏好.文獻[4]則通過現代資產組合理論(MPT)將移動應用的流行度，個人偏好和移動設備約束結合起來用于移動應用推薦.然而，這些方法都是從移動應用使用者的角度出發，沒有考慮到開發者的需求.因此，難以實現輔助開發者進行應用開發的目標.

第三方庫在移動應用開發中扮演著越來越重要的角色.首先，第三方庫是用于移動應用開發的一種可重用資源，開發人員可以通過重用第三方庫來實現自己需要的功能，從而可以有效的幫助開發者減低開發時間與開發成本.其次，第三方庫可用來幫助完成特定的商業目標.例如，可以在應用中使用廣告庫完成廣告的推廣或者使用社交庫完成用戶社交的功能.根據在Google Play上的移動應用研究表明，使用最多的第三方庫是Google ads，也就是廣告庫，其中使用廣告庫的移動應用超過了60%[2，3].這就更加證明第三方庫在移動應用中的重要性.然而，可用的第三方庫數量繁多且功能各異，這為開發者選擇合適的第三方庫提出了新的挑戰.為此，我們構造了一個新的數據集，該數據集包含移動應用及其描述，第三方庫及其描述以及移動應用與第三方庫之間的調用關系.基于這些數據，我們可以完成移動應用第三方庫的推薦任務.用于推薦任務的方法有很多，包括傳統的基于歷史信息的協同過濾算法以及基于模型的矩陣分解，這些方法在很早就被研究者證明可以在Movielens、Netflix等電影推薦中有不錯的表現，研究者們進一步將不同的推薦方法進行混合以提高推薦的精度.基于構造的數據集，我們提出了一種將基于歷史調用數據的推薦結果與基于描述文本的推薦結果進行貝葉斯融合的推薦方法.該方法一方面基于歷史調用數據使用了基于用戶的協同過濾(UBCF)方法，另一方面基于文本信息使用了TF-IDF方法.從兩個不同的角度來為開發者推薦適合的第三方庫.

本文的貢獻包括以下兩點：

1.構造了一個全新的數據集，即移動應用(app)與第三方庫的數據集；

2.提出了一種混合推薦技術用于第三方庫的推薦，在構造的數據集上開展實驗進行驗證，表明了本文所提方法的有效性.

2 相關工作

在傳統的服務計算領域，軟件開發者通過重用服務，能夠創造出更多的服務組合來滿足更多更復雜的需求并實現商業價值[5].很多研究者提出了很先進的推薦方法對服務進行推薦來實現服務組合的目標.本文所研究的問題與此相似，在移動應用的開發過程中，第三方庫扮演著越來越重要的角色，第三方庫的重用可以滿足更多的需求.目前，已經開展了大量工作進行第三方庫的相關研究，例如Pearce P等人[6]研究了Android應用程序當中的廣告庫，發現了有49%的應用程序中至少包含一個廣告庫.Shekhar S等人[7]同樣研究的是Android第三方庫當中的廣告庫，其中說明了一些惡意應用會模擬廣告庫的行為.有研究人員[8，9]從代碼層面來識別第三方庫，做法是使用機器學習來提取特征，但同樣的只能識別出廣告庫.之后有研究人員[10]使用了基于語義的特征聚類方法，但是這樣的方法同樣不太準確.這些工作主要與發現和檢測第三方庫有關，就我們的調研所知，在第三方庫的推薦方面尚沒有相關研究.

在文獻[11]中，研究者提出了一種第三方庫自動檢測和分類的方法，可以快速精準的檢測出Android 移動應用當中的第三方庫.該方法基于多級聚類技術進行識別第三方庫，然后通過機器學習方法對第三方庫的功能進行分類.該方法用于第三方庫推薦時存在的一個局限是第三方庫在使用時可能會被開發者修改，這將導致聚類之后得到的第三方庫可能不全，并且檢測到的第三方庫不是完全準確，難以支撐我們進行第三方庫推薦的任務.

3 問題分析

針對第三方庫推薦中面臨的第三方庫的檢測與篩選問題，我們構造了相應的數據集.具體構造過程如下：首先，從Google Play上面提供的百萬移動應用中爬取10000多個移動應用安裝包，然后使用了工具ClassyShark(2)https: / /github． com/google /android-classyshark對它們進行分析.ClassyShark是Google提供的用于對apk進行反編譯的一個工具，可以方便我們快速且輕巧的輕量級瀏覽Android apk.通過使用該工具，我們能夠得到每個apk反編譯之后的一系列包名.然后我們設定了一個閾值，表示為包名出現在不同apk的次數.這是為了區分出第三方庫與開發者自己寫的代碼庫，我們認為大于這個閾值即為第三方庫.而對于出現的代碼混淆問題，通常開發者混淆的包名和函數名都是自己為了防止被惡意篡改而對自己代碼所做的一種保護措施，所以我們在篩選第三方庫的過程中會自動忽略掉混淆的包名.使用這種方法得到的第三方庫做實驗時，我們發現一個問題，那就是閾值的選擇問題，我們難以選擇出最適合的閾值來最準確的篩選出第三方庫.最終，我們選擇了工具AppBrain(3)https: / /www． appbrain． com/stats，該工具將第三方庫分為三大類：廣告類、社交網絡類和開發工具類，該工具上提供的app是基于Google Play，并且AppBrain上每個第三方庫都有其所對應的標簽及相關描述.

我們假設某一個移動應用開發者需要開發一個描述為“適用于Android手機的視頻app，該app提供最熱門的音樂視頻和游戲，娛樂，新聞等視頻，您可以訂閱您喜愛的頻道并與朋友分享”的移動app.對此，開發人員一開始分析功能需求確定要使用到AdMob庫，AdMob是全球最大的移動廣告網絡之一，為移動網絡上的發現，品牌推廣和貨幣化提供解決方案.之后我們的推薦系統會產生一個用于視頻移動應用開發的第三方庫的候選列表Android support_lib，firebase，gcm，google_gson，android_arch，facebook，retrofit，zxing，butterknife，jsoup，protobuf.并基于這些候選列表項開發人員推薦可能要使用的第三方庫以提高開發效率和質量.

針對以上的場景，我們可以將問題描述為：對于appi，i的描述文本與一些確定要使用的第三方庫是已知信息.我們首先將已經要使用的第三方庫作為對i的隱式反饋，基于這些隱式數據我們可以計算出與i相似的app并將這些app調用的第三方庫作為候選集Ru.此外，通過i的描述文本挖掘出與其他app的語義相似度并生成候選集Rc.最后，通過貝葉斯定理將候選集Ru和Rc融合得到最終的推薦列表.

更一般地，我們將不同的app擴展為一個很大的app集合M，將M中使用到的第三方庫擴展為三方庫集合L.這樣，我們就構建了一個M與L的隱式反饋矩陣并基于這個矩陣以及M集合中app的描述文本完成推薦目標.

4 TF-IDF與UBCF的混合推薦方法

4.1 方法概述

如圖1所示，本文提出了一種結合app和第三方庫交互信息和文本描述信息的方法.本方法主要是由兩部分組成，基于協同過濾推薦模塊和基于內容的推薦模塊.

圖1 App第三方庫的混合推薦方法框架Fig.1 Framework of hybrid recommendation method for App third-party libraries

協同過濾的模塊主要的作用是構建一個app和第三方庫的調用關系矩陣，從這個矩陣中我們可以挖掘出他們兩者的關系.基于內容的推薦模塊主要是利用app的需求描述和第三方庫的描述信息來完成，本文中我們使用了TF-IDF來計算文本相似度.首先將描述信息轉化為文本特征向量，然后得到他們之間的語義關系，基于語義關系計算出app之間的相似度，然后利用相似度生成第三方庫的推薦列表.最后將協同過濾的推薦結果和基于文本的推薦結果通過使用貝葉斯定理進行整合，整合之后得到最終的推薦結果.

4.2 UBCF部分

協同過濾算法是最早用于推薦系統中，也是最為經典和著名的推薦算法.該算法主要通過歷史使用數據來發現目標用戶的偏好，這些歷史使用數據可以是顯式的反饋數據，也可以是隱式反饋數據.在服務計算領域，QoS的預測是很多研究者所關心的問題，大多數基于QoS的方法是預測和排序服務質量(QoS)以推薦最佳服務[12-15]. 他們遵循經典推薦系統的思想，其中協同過濾(CF)被廣泛使用來進行QoS預測.鄭子彬等人在文獻[16]中就QoS預測問題提出了一種協同過濾方法并取得較好的結果.本文中使用的是隱式反饋數據，即數據是二值的，0表示沒有交互，1則表示有.同時，傳統的協同過濾算法分為基于用戶與基于物品這兩種.顧名思義，前一種表示挖掘用戶之間的相似性，基本思想是根據具有相似偏好的用戶來為用戶推薦可能喜好的物品；后一種表示尋找相似的物品，來直接為目標用戶做推薦.無論是基于用戶的推薦還是基于物品的推薦，都需要計算相似度，通?？梢允褂糜嘞蚁嗨贫然蛘咂栠d相關系數等相似度計算方法.本文中我們使用了余弦相似度來完成這個任務.本文中使用到的協同過濾圖模型如圖2所示.

圖2 協同過濾圖模型Fig.2 Collaborative filtering model

如圖2所示，在協同過濾中，每行表示一個app，每列表示一個三方庫，矩陣中的1表示該app調用了該三方庫，0表示沒有.而圖的右邊則是對于三方庫的推薦過程.從左邊到右邊是通過相似度的計算進行的，如下所示.

(1)

Sim(i，j)表示appi和appj之間的相似度值.得到app之間的相似度矩陣之后，我們可以計算appi對第三方庫lib的相似度：

(2)

其中，Si,j表示appi和appj之間的相似度，Ij,lib表示appj是否與第三方庫lib有交互，1表示是，0表示否，N則表示與appi相似的所有app集合.

4.3 TF-IDF部分

TF-IDF是一種統計方法，通常用于評估某一個詞對于某個文檔集合或者文檔集合中某一篇文檔的重要程度.TF-IDF分為TF和IDF兩部分.TF是詞頻的意思，是指某個給定單詞在指定文檔中的頻率，通常會將這個值歸一化；IDF表示逆向文件頻率，用來度量一個單詞的普遍重要性的程度.IDF的值越高，說明這個單詞在整個文檔集合中的重要性越低.由此，TF-IDF的思想可以表示為：當某一個單詞在給定的一篇文檔中的TF很高，IDF值也很高的時候，就認為這個單詞具有很好的區分能力，因此就保留下來這個單詞.

對于移動應用市場中的app，幾乎每個都有其對應的文本描述，同樣的，給定一個將要開發的app的文本描述，在本文中，我們基于這些文本描述使用TF-IDF和向量空間模型來計算app之間的相似度.首先我們計算出每個app描述文本當中每個單詞的TF-IDF值，在計算完單詞的TF-IDF值之后，我們進行關鍵詞的篩選，即保留重要的單詞，去掉非必要的單詞.然后我們使用向量空間模型將文本中的單詞向量化.具體的步驟如下：

1)通過使用TF-IDF算法，將兩個app各自的描述文本進行關鍵詞篩選，即去掉那些非重要性單詞

2)取出每個文本的若干個單詞組成單詞集合，然后計算每個app描述對該單詞集合中單詞的TF-IDF值

3)生成兩個app描述的單詞向量

4)通過計算出這兩個app單詞向量的余弦相似度

TF-IDF的方法描述如下：

(3)

(4)

其中，TF(tk，dj)是第k個詞在第j個文章中出現的次數，nk是包含第k個詞的文章數量.最后，第k個詞在第j個文章中權重如下：

(5)

這里做歸一化的目的是將不同文檔中的向量表示歸一到同一量級上.

得到每個描述文本中每個單詞的TF-IDF值之后，按照大小排序取前若干個單詞組成單詞向量.從而兩個app之間的文本相似度可以表示為：

(6)

其中，Des1和Des2分別app1和app2的描述，Wi1和Wi2分別表示第i個單詞在app1和app2中的權重，M表示app總數.

4.4 貝葉斯融合

通過歷史調用數據，我們計算出了app與第三方庫的余弦相似度，相似度的值落在0到1的范圍內.我們可以將其解釋為在一個app中使用到第三方庫的概率，即P(libu|app).另一方面，通過app的描述文檔，我們使用TF-IDF計算app之間的相似度并且利用app的相似度得到app使用第三方庫的概率，概率表示為P(libc|app).因此，我們假設條件獨立，就可以通過貝葉斯定理將這兩個概率進行整合.整合之后，對于給定的app及其描述，我們可以將其表示為：P(lib|app)=P(libu|app)*P(libc|app).我們將問題轉化為對于第三方庫來說，它被新的app調用的可能性是多少，這可由后驗概率P(app|lib)給出.通過使用貝葉斯定理，可以得到：

P(app|lib)∝P(libu，libc|app)*P(app)=
P(libu|app)*P(libc|app)

(7)

其中，P(app)是我們看到app的先驗概率，大小為1/M，M是app的總數.這樣，我們可以選出具有最大P(app|lib)的第三方庫.

5 實 驗

在本節中，我們將介紹為評估提出的第三方庫推薦方法性能所進行的實驗研究和不同方法之間的對比實驗，我們的實驗是基于之前所構造的現實世界的數據集.

5.1 實驗設置

我們所有的實驗部分都是在具有Intel(R) Xeon(R) CPU E5-1620 v3 @ 3.50GHz的處理器和64.0GB內存的Windows操作系統上進行的.

5.2 數據集

本次實驗的全部數據來自于AppBrain，這也是AppBrain上的數據首次被使用于該實驗目的.因此，我們選擇的一些現有方法都不曾用于該數據集，這些方法會產生什么樣的效果也讓我們有所期待.AppBrain上包含很多的app及其調用的第三方庫，由于考慮數據量的大小以及矩陣的稀疏程度，我們選擇了其中的5274個app，一共包括了470個第三方庫.同時我們也獲取了app以及第三方庫的相關描述.表1顯示了數據集中一個app的信息.表2顯示了該數據集的相關信息.

表1 App Gesture Call的信息Table 1 Information of App Gesture Call

數據預處理：對于文本數據，我們得到的原始文本數據包含了app的名字、類別、開發者以及描述等信息.第一步，我們選擇了描述信息.然后我們對描述信息進行了分詞，去掉停用詞和非法字符等.剩下的詞最能用來代表描述app的功能.對于歷史調用數據，正如前面所提到的，我們在這方面做了很多的工作，包括自己爬取數據并設計方法去篩選第三方庫.最終，我們選擇使用AppBrain上的數據并且就此構造數據集.之后，針對數據集我們構造了app與第三方庫的調用矩陣，該矩陣是一個0/1矩陣，其中行表示app，列表示第三方庫.

表2 數據集的狀態Table 2 Statistics of dataset

訓練集與測試集：為了評估推薦性能，我們基于自己的數據集為每個實驗構建了一個訓練集和一個測試集.首先，我們隨機選擇70%的app作為實驗的訓練集，剩下的部分則作為測試集.測試集當中的app所包含的一部分第三方庫用于預測，另外一部分則用于訓練.每個實驗進行10次實驗，并將它們的平均值作為最終的結果.

5.3 評價指標

在實驗中，我們采用了兩種評價指標用來評估對Android app進行第三方庫推薦時的性能.分別是MAP以及NDCG.

MAP是指平均均值精度，它是信息檢索領域當中常見的評價指標.當測試集中app的數量為Atest時，推薦K個第三方庫的MAP值定義如下：

(8)

其中，Atest表示測試集app的數量，la表示appa所調用的第三方庫的數量，Ki表示出現在推薦列表中的a的第三方庫的數量，I(i)表示推薦列表中位置i的第三方庫是否被a所調用.

當測試集中app的數量為時Atest，推薦K個第三方庫的NDCG值定義如下：

(9)

其中，IDCG表示IdealDCG，是指推薦列表中的最佳排列所對應的分數.

5.4 比較方法

我們選擇了幾種常見的比較先進的算法作為對比.其中包括基于文本的推薦和基于歷史調用數據的推薦等.

基于用戶的協同過濾(UBCF)：基于用戶的協同過濾算法是一種廣泛應用于推薦系統的經典算法.

基于物品的協同過濾(IBCF)：基于物品的協同過濾算法同樣是一種廣泛應用于推薦系統的經典算法，所不同的是計算物品之間的相似度.

基于主題模型LDA的推薦算法(LDA)：基于文本主題模型的推薦算法，通過使用LDA計算出每兩個app描述文本的主題相似度，基于這些相似度生成第三方庫的推薦列表.

基于用戶的協同過濾與主題模型LDA的混合推薦算法(LDA+UBCF)：同上，我們通過將主題模型LDA與UBCF進行整合得到混合推薦結果.

圖3 NDCG@KFig.3 NDCG@K圖4 MAP@KFig.4 MAP@K

圖3和圖4展示了我們所提出的混合推薦方法即TF-IDF+UBCF與其他的方法在NDCG@K，MAP@K這兩個指標上的對比.UBCF基本上在這兩項指標上都是差于其他的方法.同時，對比基于歷史調用方法和基于內容的方法，我們可以得出基于文本描述的方法即LDA要表現的比基于用戶的協同過濾更加優異，但卻要比IBCF在兩種指標上略差，其原因是我們在做第三方庫的推薦時，并沒有考慮到三方庫在移動應用中的優先級，所以使用UBCF時可能會忽略掉優先級較高的第三方庫.而IBCF則是直接通過第三方庫之間的相似度關系進行推薦，因此，使用IBCF的效果要優于UBCF.此外，無論是基于歷史調用數據的方法還是基于內容的方法在兩種指標上都比混合方法效果差.同時我們的貝葉斯混合推薦方法也在所有方法中脫穎而出.幾種指標的部分詳細數值如下表所示.

表3-表4顯示了各項指標的具體數值.表中加粗的數據是給定K的最好結果，?表示在0.01水平上與最佳結果的差異性具有統計顯著性.從以上表格中看出，我們的混合推薦方法基本在所有指標中都是最好的結果，并且在后兩個指標上與其他方法幾乎都具有統計顯著性的差異.更具體點，在NDCG這個指標上，當K為40時，TF-IDF+UBCF比UBCF高8.86%，比LDA+UBCF高2.76%；在MAP上，當K為40時，TF-IDF+UBCF比UBCF高7.35%，比LDA+UBCF高3.33%.

我們發現，在利用貝葉斯混合推薦方法進行基于內容的推薦時，挖掘到的相似移動應用的數量N對最終的推薦結果有著一定的影響，當設置的相似app數量較少時，會導致推薦結果不夠完整，而當我們將N設置較大時則會產生一些相關性不大的推薦結果.所以，設置適當的N的大小對我們的工作來說是有必要的.為了研究N的大小對推薦結果的影響，我們將N的范圍設置為20到120，步長為20.如圖5和圖6所示，當N從20增加到60 時，NDCG和MAP值都相應增加.

表3 5種方法的詳細NDCG值Table 3 Detailed NDCG values for the five methods

表4 5種方法的詳細MAP值Table 4 Detailed MAP values for the five methods

圖5 NDCG@KFig.5 NDCG@K

圖6 MAP@KFig.6 MAP@K

但是當N從60增加到120時，兩種度量指標都幾乎沒什么變化或者說在某個值附近浮動，這是因為排名越靠后的移動應用有著越小的影響因子，當這個排名值達到某個臨界點時，后面的推薦結果幾乎不影響整體的推薦性能.由此可以得出，在我們的貝葉斯混合推薦系統中，當推薦的移動應用數量N不大于60時，推薦性能會隨著N的增加而增強；然而當N繼續增加時，推薦系統基本趨于穩定.

6 結論與未來工作

本文針對為移動應用推薦三方庫這一應用場景，構建了相應的數據集.并在此基礎上提出了一種新的混合推薦方法，即使用貝葉斯理論集成了歷史調用和文本內容信息.所提模型中集成的文本內容可以在一定程度上緩解推薦系統中經典的冷啟動問題.在真實數據集上開展的實驗，表明了本文所提方法的有效性.

下一步，我們將在推薦模型中進一步利用數據集中的app以及第三方庫的標簽與類別等信息，并將這些信息與當前隱反饋數據加以整合，另外，將使用神經網絡進一步挖掘app與第三方庫的潛在關系.