一種基于實時CTR的移動應用商店內容推薦改進算法

馮欣，夏旸

（長春理工大學 計算機科學技術學院，長春 130022）

一種基于實時CTR的移動應用商店內容推薦改進算法

馮欣，夏旸

（長春理工大學 計算機科學技術學院，長春 130022）

針對內容信息過載，冷啟動等導致移動應用市場用戶消費受限、廣告收入受阻的問題，文章提供一種能夠提高移動應用市場人均分發能力的內容推薦算法。首先，收集一段時間內產生的內容推薦數據，作為待處理的推薦內容集合。然后，通過一種改進的實時CTR推薦算法，對已有內容進行基于展示、點擊、下載的重新排列，并將重新排列的數據展示在移動應用市場內部。與傳統的CTR推薦算法相比較，改進后的實時CTR推薦算法在評價維度上更加合理。通過對比，改進后的實時CTR推薦算法可以提高移動應用市場的分發能力，適用于信息過載下的移動應用市場。

移動應用市場；內容推薦；CTR

智能手機、高速網絡以及各種各樣的移動應用為人們創造了豐富多彩的生活［1-3］。從聊天交友，分享生活精彩到辦公軟件，再到影音娛樂和電子商務，人們越來越離不開這些應用，需要這些應用來進行娛樂和管理自己的生活［4，5］。2015年是移動應用爆發增長的一年，GooglePlay全球應用年度下載量與2014年相比實現了將近100%的增長，IOS應用商店全球應用年度收入同比顯著增長，可見，作為移動應用分發主要來源的移動應用市場，在這一年中扮演了至關重要的角色［6］。

由于政策等原因，Google Play無法為我國大陸地區的安卓用戶提供相關服務，經過幾年發展，國內的主流移動應用市場包括應用寶、360手機助手、PP助手、豌豆莢、以及其他手機品牌自有的獨立應用商店均占有很大一部分用戶，根據艾媒咨詢發布的2015～2016中國手機應用商店年度報告顯示，截止至2015Q4，第三方手機應用商店的活躍用戶規模已達4.40億，然而2014年相對2015環比增長僅為0.92%［7］。

圖1 國內第三方安卓應用商店活躍用戶規模圖示

隨著活躍用戶抵達天花板，如何在接近穩定的用戶群中，進一步提高移動應用市場應用分發的能力和廣告的收入，成為了各大移動應用市場需要思考的問題［8］。

1 內容推薦算法綜述

1.1 協同過濾推薦算法

協同過濾的概念是由Goldberg Nicols Oki及Terry在1992年首次提出的，作為協同過濾推薦的雛形，該算法展示了一種新的推薦思想，其后，出現了基于評分的協同推薦系統，比如用于新聞和電影網站的GroupLens［9-12］.

目前，主要分為兩類協同過濾推薦算法：基于用戶的協同過濾推薦算法［13］和基于物品的協同過濾推薦算法［14］。其中，前者基于這樣的一個假設，即若目標用戶的最近鄰居（最相似的若干用戶）用戶群對某項目的評分比較相似，算法便根據這些評分來逼近目標用戶對該項目的評分?；谖锲返膮f同過濾算法認為，用戶對不同物品的評分存在一定的相似性，當需要對某用戶對一個物品的評分時，可根據用戶在歷史上對該物品的若干相似物品的評分來評估評分。

1.1.1 基于用戶的協同過濾推薦算法

采用該算法為目標用戶Ui（i=1，2，…，n）確定給定物品Ij（j=1，2，…，n）的評分Pij，通常分為以下步驟：

（1）計算目標用戶Ui和其他為Ij評分過的用戶之間的相似度，其中為Ij評分過的用戶集合記為U*

（2）根據所有Uk∈U*對項目Ij的評分來估算Ui對Ij的評分。

若把用戶評分作為n維向量空間上的向量，則用戶相似性可通過向量間余弦表示：

然而向量的余弦相似度并沒有考慮用戶評分的極端問題，修正的余弦相似度方法通過減去用戶對項目的平均評分來改善評分落差巨大的問題，用戶i和用戶j之間的相似性表示為：

其中，Ri,c表示用戶i對物品c的評分，Rj,c表示用戶 j對物品c的評分，Rˉi與Rˉj表示用戶i、用戶 j對自己已評分項目的平均值。

根據上步得出的用戶相似性，進而計算用戶Ui對物品Ij的評分：

1.1.2 基于物品的協同過濾推薦算法

就目前移動應用市場的情況來說，雖然每天有大量的新應用上架，然而同質化趨勢卻日趨嚴重，因此可以認為，需要被推薦的項目數量保持了相對穩定，由此計算出的物品相似度矩陣更新頻率比較低，可以在比較長的一段時間內應用。這一特點恰好為采用基于物品（item-based）的推薦算法帶來了可能。該算法概括起來一般包括以下三個步驟：

（1）內容抽象（Item Representation）

在現實生活中，一個item通常都會有一些可以用來描述其自身的屬性，而這些屬性通常又分為結構化屬性和非結構化屬性。對于結構化的屬性，它們是一些很容易定義的，意義明確的屬性；而對于非結構化的屬性，往往要把它轉化為結構化的屬性后才能使用。其中應用內容推薦就是一個使用場景。

（2）用戶特征的學習（Profile Learning）

利用一個用戶過去喜歡的item的屬性數據，通過機器學習得出該用戶的喜好特征（profile）；加入一個用戶user1對一些item做出了喜好的判斷。那么，這一步就是根據用戶user1的喜好數據來建立一個模型，并以此來推斷user1是否會喜歡上一個特定應用item。所以接下來需要解決的就是一個采用某分類算法的機器學習過程，常用的學習算法包括：最近鄰居方法、決策樹算法，線性分類算法，樸素貝葉斯算法等。

（3）推薦內容的生成（RecommendationGenera?tion）

這一步基本就是根據學習得到的用戶特征與item特征進行相似度的判斷，然后為用戶推薦一組與其相關性最大的item。

上述3個步驟的大體流程圖如圖2所示。

圖2 以app為例的推薦流程圖

2 存在問題

2.1 冷啟動問題

無論是基于用戶還是基于物品的協同過濾推薦，冷啟動［15-17，19］都是一直以來讓使用者頭疼的問題。

隨著移動應用市場收錄的條目增長以及用戶規模的進一步擴大，用戶數量和應用數量快速增長，導致用戶-物品評分表經常需要反復計算用戶或物品之間的相似性，進而導致算法的耗時不斷升高，另一方面，當一個新用戶或者新應用進入移動應用市場時，相關的評分都是空白，所形成的相關性推薦并不準確，這也導致推薦結果的可靠性在不斷下降。

考慮兩種情況：

1.1.1的推薦中，如果被推薦者是一個新用戶，那么就不會有任何的消費記錄和喜好傾向，故而無法找到和該用戶相似的用戶，也就無法進行推薦。

1.1.2的推薦中，針對物品進行條件抽取已經十分困難并必然伴隨著抽取不完全的情況，無法很好的將該物品分類，也就無法進行推薦。

2.2 推薦速度問題

隨著用戶數和應用數的增多，協同過濾算法的計算量也在迅猛增長。當內容推薦所面臨的用戶規模達到數百萬甚至更高級別時，推薦算法面臨的可擴展問題將會十分嚴峻。對于在線服務，推薦的實時性顯得至關重要，然而對于時間復雜度為O(n2m)的協同過濾算法來講，計算開銷非常大，雖然可以通過降維、聚類、分類等方法能夠在一定程度上縮短計算開銷，然而這些措施本身也占用了大量的時間。

2.3 物品本身特征提取問題

雖然對文本信息的特征提取技術已比較成熟，但是對于一個本身具有多媒體屬性的app來說，其特征提取技術依舊進展緩慢，目前的移動應用市場主要采用開發者對app進行標簽分類的方式標注一個app的特征信息，這一方法在推薦的靈活性上較差。

2.4 其他問題

除了上述問題之外，移動應用市場還面臨著app刷榜刷量［18］、隱私問題、非注冊用戶行為收集困難等問題。對于這些問題，現有的大多數推薦算法都無法令人滿意，只有通過一些人工的運營方式來進行干預。

3 CTR推薦算法

CTR（Click-Through-Rate）是一個互聯網廣告常用語，即網絡廣告（圖片、文字、關鍵詞、排名、視頻等廣告形式）的到達率，也成點擊率，其計算公式如下。

基于CTR進行的推薦算法主要分為兩大部分，即CTR的實時計算和對CTR進行預估，其中對CTR進行的實時計算一方面可以用來進行內容推薦，另一方面，也為內容的CTR預估提供了歷史數據。

一個CTR實時計算系統的架構圖通常如圖3所示。

圖3 一種實時計算系統的架構示意圖

客戶端將內容的CTR原始數據上傳至服務器，服務器端通過CTR實時計算系統生成該內容的實時CTR數據，并將該數據存儲于CTR數據庫中，該數據庫需要滿足高并發性［20］。當服務器開始計算預估CTR時，CTR預估系統調用已有的實時CTR數值，來進行計算，并將計算結果上傳至內容推薦系統，內容系統根據CTR隊列，將內容抽取出來并排序，推送給客戶端，最后呈現在用戶面前。

3.1 單純CTR排序算法

該算法關注特定內容組合的最優排序，以期實現一定時間段內所展示頁面的平均CTR最高。

假設某特定內容 j在不同的位置i上的CTRi,j恒定，每個位置的曝光占比Impri恒定且遞減。

排序方法：在某一時間段內，CTR越高的內容所獲得的曝光量越大，進而使整體內容的平均CTR最高。即通過歷史CTR數據進行內容的CTR預測，通過調整內容的位置i來控制曝光量，從而給出最優排序，公式表述如下：

然而上述算法中，同一內容在不同位置上的CTR很有可能不恒定，當波動大于某一閾值時，假設的前提將不存在。

3.2 實時CTR預測排序算法

在單純CTR排序的基礎上，縮短計算CTR和生成新推薦序列的時間，每個小時計算一次下個小時某內容的CTR預測值，使每個小時的預測值都盡可能接近真實值，并據此調整推薦內容序列，使全天的平均CTR更高。

誤差檢測

針對部分內容和整體內容，采取下邊兩個公式進行預測CTR值的誤差檢測：

4 實時CTR排序算法改進

4.1 一種結合分發效率調權的實時CTR排序算法改進

在移動應用市場領域，除直接下載帶來的分發行為外，非直接下載的點擊行為也有一定概率轉化為下載行為，可以通過離線計算的方式來統計這部分非直接下載點擊行為轉化到下載行為的轉化率，記為c，當前內容的分發效率記為Ri( ) consumption，從而得出每一個內容的排序值：

其中，CTRi為實際計算得出的真實值，如果是首次推薦的內容，其CTR值和分發效率需要一段時間計算得出，并且在這段時間內要保證其有充足曝光，因此會為初次推薦的內容指定一個初始的R值，有

其中，Ravg和Rmax為當前頁面排序值的均值與最大值，m為一個隨機數，目的是為了調整Rj上限。通過這樣的一個公式，可以保證首次推薦的內容有足夠的曝光量，也利于后續計算CTR值與分發效率。

4.2 實驗結果

將改進前后的推薦算法分別運用到同一組內容上去，通過觀察一段時間內的數據反饋情況，得到如下結論。由實驗結果可以看出，執行了分發調權改進算法的實驗組在人均分發和消費滲透率這兩個數據指標上均優于未采用改進算法的對照組，所以可以說，針對實時CTR推薦算法的改進是有正向作用的。

圖4 算法改進前后人均分發情況對比

圖5 算法改進前后分發滲透率情況對比

5 結論

國內移動應用市場發展至今，其大部分的流量已經被百度、騰訊、360等幾家互聯網巨頭牢牢占據，為了能夠在競爭如此激烈的市場中保持健康而持續的狀態，其他獨立和第三方移動應用市場唯有在已有的流量渠道之下，進一步提升各項分發指標，找到適合自己生存的商業模式，輔以恰當的內容推薦技術，將自己的分發能力不斷提高。筆者通過對協同過濾推薦算法進行綜述，指出了其過于依賴計算資源，反饋不夠及時，受信息矩陣稀疏性影響大導致推薦結果失準等問題，也通過提出一種基于實時CTR推算算法的改進，該改進的算法在內容池確定的情況下，能夠使移動應用市場的分發能力進一步提升，然而，一個完整的移動應用市場生態并不是任何單一技術能夠支撐起來的，而是多種技術協作而成。因此，越來越多的應用分發廠商選擇走向了混合推薦的路線：將固定展示的內容根據展示下載等影響因素進行排序推薦，將即時更新的內容或個性化內容通過協同過濾、內容匹配推薦等其他算法進行推薦，以幾種算法結合而成的混合推薦系統來不斷提高自身的分發能力。

同時，缺少了谷歌的國內安卓市場，如何保證App的渠道來源正規，如何區分山寨應用，也是各大應用市場急需解決的事情，混亂的現狀需要規范的引導的同時，也存在著很大的機遇，希望國內的安卓應用市場可以為用戶提供優質可靠的服務。

［1]北京大學媒介研究中心.移動分發市場研究報告［EB/ OL］.http：//www.looec.cn/detail-6188727.html，2014.

［2]蔡可.基于用戶采納的手機商店研究［D］.武漢：華中科技大學，2010.

［3]閔棟，劉東明.移動應用商店跟蹤研究［J］.電信網技術，2010（2）：13-18.

［4]翁昱.移動應用盈利模式研究與分析［J］.商業文化（下半月），2012（10）：5.

［5]李曉賓.中國移動應用商店商業模式評價研究［D］.北京：北京郵電大學，2012：8-15.

［6]App Annie.全球移動應用市場2015年回顧［R］.App Annie，2016

［7]艾媒咨詢.2015-2016中國手機應用商店年度報告［R］.艾媒咨詢，2016

［8]陳婉玲，范久紅.我國移動應用分發平臺發展仍受制約，突破瓶頸須探索模式創新［J］.世界電信，2014（11）：43-48.

［9]Arwar B，Karypis G，Konstan J，et al.Analysis of rec?ommendationalgorithms for E-commerce［C］.In：Pro?cessing of 2nd ACM Conferenceon Electronic Com?merce，2000：158-167.

［10]Wang Zhi-mei，Yang Fan.P2P recommendation algo?rithmbased on hebbian consistency learning［J］.Com?puterEngineering and Applications，2006，42（36）：110-113.

［11]You Wen，Ye Shui-sheng.A survey of collaborative filteringalgorithm applied in E-commerce recommend?er system［J］.Computer Technology and Development，2006，16（9）：70-72.

［12]Wu Yan，Shen Jie，Gu Tian-zhu，et al.Algorithm for sparseproblem in collaborative filtering［J］.Application Research ofComputers，2007，24（6）：94-97.

［13]Wang Wei-ping，Liu Ying.Recommendation algo?rithm based oncustomer behavior locus［J］.Computer Systems&Applications，2006，15（9）：35-38.

［14]Deng Ai-lin，Zhu Yang-yong，Shi Bai-le.A collabor?ativefiltering recommendation algorithm based on item ratingprediction［J］.Journal of Software，2003，14（9）：1621-1628.

［15]于洪，李俊華.一種解決新項目冷啟動問題的推薦算法［J］.軟件學報，2015（6）：1395-1408.

［16]孫冬婷，何濤，張福海.推薦系統中的冷啟動問題研究綜述［J］.計算機與現代化，2012（5）：59-63.

［17]孫小華.協同過濾系統的稀疏性與冷啟動問題研究［D］.杭州：浙江大學，2005.

［18]孫飛飛，張淇人.APP刷榜黑幕調查［J］.IT時代周刊，2012（5）：29-34.

［19]Bobadilla J S，Ortega F，Hernando A，et al.A collabor?ativefilteringapproachtomitigatethenewuser cold start problem［J］.Knowledge-Based Systems，2012，26：225-238.

［20]王歡，趙建平，姜曉明，等.高并發性Web應用平臺研究與實現［J］.長春理工大學學報：自然科學版，2015，38（3）：144-147.

An Improvement of Content-Recommend Algorithm Based on Real-time CTR in Mobile Market

FENG Xin，XIA Yang
（School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022）

For the content and information overload，cold start and others as results of the limitation of mobile application market users’consumption and the obstruction of advertise revenue，in this paper，a content-recommend algorithm to improve the con?sumption ability of the mobile application market for each consumer is provided.First，the recommended content datum generated within the period are collected as the pending set.Then，through an improved real-time CTR recommendation algorithm，the existing contents based on their impressions are rearranged，clicked and downloaded，then the result in mobile application market is displayed.Compared with the traditional CTR recommendation algorithm，the improved real-time CTR recommendation algo?rithm is more reasonable in the evaluation dimensions.By contrast，the improved real-time recommendation algorithm can im?prove the distribution capabilities of the mobile application market，especially for those with the problem of information overload.

mobile application market；content-recommend；CTR

TP391

A

1672-9870（2017）02-0122-05

2016-08-25

馮欣（1973-），男，博士，副教授，E-mail：1203511908@qq.com