探尋微博背后的大數(shù)據(jù)原理：微博推薦算法簡述

“We are leaving the age of information and entering the age of recommendation” — Chris Anderson in The Long Tail。

我們正在遠離信息，而進入推薦時代?！死锼埂ぐ驳律?/span>

在介紹微博推薦算法之前，我們先聊一聊推薦系統(tǒng)和推薦算法。有這樣一些問題：推薦系統(tǒng)適用哪些場景？用來解決什么問題、具有怎樣的價值？效果如何衡量？

推薦系統(tǒng)誕生很早，但真正被大家所重視，緣起于以”facebook”為代表的社會化網(wǎng)絡的興起和以“淘寶“為代表的電商的繁榮，”選擇“的時代已經來臨，信息和物品的極大豐富，讓用戶如浩瀚宇宙中的小點，無所適從。推薦系統(tǒng)迎來爆發(fā)的機會，變得離用戶更近：

• 快速更新的信息，使用戶需要借助群體的智慧，了解當前熱點。
• 信息極度膨脹，帶來了高昂的個性化信息獲取成本，過濾獲取有用信息的效率低下。
• 很多情況下，用戶的個性化需求很難明確表達，比如“今天晚上需要在附近找一個性價比高、又符合我口味的餐館“。

推薦系統(tǒng)的適用場景還有很多，不再一一列舉；其主要解決的問題是為用戶找到合適的item（連接和排序），并找到一個合理的理由來解釋推薦結果。而問題的解決，就是系統(tǒng)的價值，即建立關聯(lián)、促進流動和傳播、加速優(yōu)勝劣汰。

推薦算法是實現(xiàn)推薦系統(tǒng)目標的方法和手段。算法與產品相結合，搭載在高效穩(wěn)定的架構上，才能發(fā)揮它的最大功效。

接下來我們說一下微博推薦，微博本身的產品設計，使得即使沒有推薦系統(tǒng)，仍然會形成一個大的用戶關系網(wǎng)絡，實現(xiàn)信息快速傳播；而衡量一個事物的價值，一個簡單的方法是對比看看保留它和去掉它時的差別。微博需要健康的用戶關系網(wǎng)絡，保障用戶feed流的質量，且需要優(yōu)質信息快速流動，通過傳播淘汰低質信息。微博推薦的作用在于加速這一過程，并在特定的情況下控制信息的流向，所以微博推薦的角色是一個加速器和控制器。

最后回到微博推薦算法中來，上面扯了那么多，只是為了讓大家能對微博推薦算法有更好的理解。我們的工作，是將微博推薦的目標和需要解決的問題，抽樣為一系列的數(shù)學問題，然后運用多種數(shù)據(jù)工具進行求解。

接下來首先用一個圖梳理下我們用到的方法和技術，然后再逐一介紹。

基礎及關聯(lián)算法

這一層算法的主要作用是為微博推薦挖掘必要的基礎資源、解決推薦時的通用技術問題、完成必要的數(shù)據(jù)分析為推薦業(yè)務提供指導。

這一部分中常用的算法和技術如下：

分詞技術與核心詞提取

是微博內容推薦的基礎，用于將微博內容轉化為結構化向量，包括詞語切分、詞語信息標注、內容核心詞/實體詞提取、語義依存分析等。

分類與anti-spam

用于微博內容推薦候選的分析，包含微博內容分類和營銷廣告/色情類微博識別；

內容分類采用決策樹分類模型實現(xiàn)，共3級分類體系，148個類別；營銷廣告/色情類微博的識別，采用貝葉斯與最大熵的混合模型。

聚類技術

主要用于熱點話題挖掘，以及為內容相關推薦提供關聯(lián)資源。屬于微博自主研發(fā)的聚類技術WVT算法（word vector topic），依據(jù)微博內容特點和傳播規(guī)律設計。

傳播模型與用戶影響力分析

開展微博傳播模型研究和用戶網(wǎng)絡影響力分析（包含深度影響力、廣度影響力和領域內影響力）。

主要推薦算法

1. Graph-based 推薦算法

微博具有這樣的特點：用戶貢獻內容，社會化途徑傳播，帶來信息的爆炸式傳播。之所以稱作graph-based 推薦算法，而不是業(yè)界通用的memory-based 算法，主要原因在于：

• 我們的推薦算法設計是建立在社交網(wǎng)絡之上，核心點在于從社交網(wǎng)絡出發(fā)，融入信息傳播模型，綜合利用各類數(shù)據(jù)，為用戶提供最佳的推薦結果；比如很多時候，我們只是信息傳播的關鍵環(huán)節(jié)，加入必要的推薦調控，改變信息傳播通路，后續(xù)的傳播沿著原來的網(wǎng)絡自然的傳播。
• Feed流推薦（我們稱作趨勢），是我們最重要的產品，而結果必須包含用戶關系。

從graph的宏觀角度看，我們的目標是建立一個具有更高價值的用戶關系網(wǎng)絡，促進優(yōu)質信息的快速傳播，提升feed流質量；其中的重要工作是關鍵節(jié)點挖掘、面向關鍵節(jié)點的內容推薦、用戶推薦。

對這部分的算法做相應的梳理，如下面的表格：

這里的困難點在于graph的“邊”怎樣量化與取舍，依據(jù)多個“邊”與“節(jié)點”的綜合評分計算，以及與網(wǎng)絡挖掘分析結果的融合。

這部分的算法研發(fā)中，產出了如下的數(shù)據(jù)附產品：

2. Content-based 推薦算法

Content-based 是微博推薦中最常用也是最基礎的推薦算法，它的主要技術環(huán)節(jié)在于候選集的內容結構化分析和相關性運算。

正文頁相關推薦是content-based 應用最廣的地方，以它為例，簡要的說一下

內容分析的很多點已在前面描述過了，這里重點說2個地方：

• 內容質量分析，主要采用微博曝光收益+內容信息量/可讀性的方法來綜合計算。微博曝光收益是借助用戶群體行為，衡量內容優(yōu)劣；內容信息量計算比較簡單，即是微博關鍵詞的idf信息迭代；對于內容可讀性的衡量，我們做了一個小的分類模型，分別以可讀性較好的新聞語料和可讀性較差的口語化語料為訓練樣本，通過提取里面的各類詞搭配信息，計算新微博具有良好可讀性的概率。
• 詞擴展，content-based的效果取決于內容分析的深度。微博的內容比較短，可提取的關鍵信息比較少，做相關運算時容易因為數(shù)據(jù)稀疏而導致推薦召回率和準確率的難以權衡；我們引入word2vec技術，優(yōu)化了詞擴展效果，后面又以此為基礎開展詞聚類的工作，實現(xiàn)了推薦召回率和準確率的同步提升。

相關計算的技術點在于向量的量化和距離度量，我們通常使用“tf*idf權重量化 + 余弦距離”或者“topic 概率 + KLD距離“的兩種方法。

3. Model-based 推薦算法

微博作為中國最大的社會化媒體產品，具有海量的用戶和信息資源；這就給推薦帶來了2個挑戰(zhàn)：

來源融合與排序

候選的極大豐富，意味著我們有更多的選擇，于是我們推薦結果的產生包含兩層：多種推薦算法的初選與來源融合排序的精選，為了得到更客觀準確的排序結果，我們需要引入機器學習模型，來學習隱藏在用戶群體行為背后的規(guī)律。

內容動態(tài)分類和語義相關

微博UGC的內容生產模式，以及信息快速傳播和更新的特點，意味著之前人工標注樣本，訓練靜態(tài)分類模型的方法已經過時了，我們需要很好的聚類模型把近期的全量信息聚合成類，然后建立語義相關，完成推薦。

Model-based 算法就是為了解決上述的問題，下面是我們兩塊最重要的機器學習工作：

3.1 CTR/RPM（每千次推薦關系達成率）預估模型，采用的基本算法為Logistic regression，下面是我們CTR預估模型整體的架構圖：

這部分工作包含樣本選擇、數(shù)據(jù)清洗、特征提取與選擇、模型訓練、在線預估和排序。值得一提的是，模型訓練前的數(shù)據(jù)清洗和噪音剔除非常重要，數(shù)據(jù)質量是算法效果的上界，我們之前就在這個地方吃過虧。

Logisitic regression是一個2分類概率模型

優(yōu)化的目標在于最大化“樣本正確分類概率的連乘值“；我們借助yahoo 研發(fā)的vowpal_wabbit機器學習平臺來完成模型特征值求解的最優(yōu)化過程。

3.2 LFM（Latent Factor Model）：LDA、矩陣分解（SVD++、SVD Feature）

LDA是2014年初重點開展的項目，現(xiàn)在已經有了較好的產出，也在推薦線上產品中得到了應用；LDA本身是一個非常漂亮和嚴謹?shù)臄?shù)學模型，下面是我們一個LDA topic的例子，僅供參考。

至于矩陣分解，2013年的時候做過相應的嘗試，效果不是特別理想，沒有繼續(xù)投入。

隱語義模型是推薦精度最高的單一模型，其困難在于數(shù)據(jù)規(guī)模大時，計算效率會成為瓶頸；我們在這個地方開展了一些工作，后續(xù)會有同學專門介紹這一塊。

混合技術

三個臭皮匠頂個諸葛亮，每一種方法都有其局限性，將不同的算法取長補短，各自發(fā)揮價值，是極為有效的方式。微博推薦算法主要采用了下面的混合技術：

時序混合：

即在推薦過程的不同時間段，采用不同的推薦算法；以正文頁相關推薦為例，在正文頁曝光的前期階段，采用content-based + ctr預估的方法生成推薦結果，待產生的足量可信的用戶點擊行為后，再采用user-based 協(xié)同過濾的方法得到推薦結果，如下圖所示：

這樣利用content-based很好的解決了冷啟動的問題，又充分發(fā)揮了user-based CF的作用，實現(xiàn)1+1>2的效果。

分層模型混合：

很多情況下，一個模型無法很好的得到想要的效果，而分層組合往往會取得比較好的效果，分層模型混合即“將上一層模型的輸出作為下層模型的特征值，來綜合訓練模型，完成推薦任務“。比如我們在做微博首頁右側的ctr預估排序時，采用分層邏輯回歸模型，解決了不同產品間特征天然缺失與樣本量差異、曝光位置帶來的效果偏差等問題。

瀑布型混合：

這類混合技術思路非常簡單，即在推薦候選非常豐富的情況下，采用逐層過濾的方法的得到推薦結果，通常將運算快、區(qū)分度低的算法放在前面，完成大量候選集的篩選；將運算慢、區(qū)分度高的算法放在后面，精細計算剩下的小規(guī)模集合。這類混合在微博推薦中大量使用，我們采用各種輕量算法完成候選集粗選，然后采用ctr預估做精細化排序。

交叉混合：

各類推薦算法中子技術，可以在另外的推薦算法中綜合使用，比如content-based在相關性計算中積累的距離計算方法，可以很好的應用在協(xié)同過濾的量化計算中。實際的例子，我們將研究LDA時積累的向量計算方法成功的應用到用戶推薦中。

Online 與 offline

微博數(shù)據(jù)的特點（海量、多樣、靜態(tài)與動態(tài)數(shù)據(jù)混在一起），決定了大部分推薦產品的結果需要同時借助online和offline的計算來完成。從系統(tǒng)和算法設計的角度，這是一個“重”與“輕”的問題，計算分解和組合是關鍵，我們需要將對時間不敏感的重型計算放在offline端，而將時間敏感性強的輕型快速計算放在online端。幾種我們常用的方式如下圖：

Online需要簡單可靠的算法，快速得到結果；簡要說明下上面的圖，如下

半成品有以下的3中形式

1）計算過程拆解的離線部分，如user-based CF中的用戶相似度，online通過數(shù)據(jù)庫讀取后在線計算完成user-based 推薦。

2）離線挖掘的優(yōu)質候選集，如正文頁相關推薦的內容候選集，online通過索引獲取到數(shù)據(jù)后，再通過相關性和ctr預估排序生成推薦結果。

3）具有較高相似度的推薦結果集，如offline計算好粉絲相似高的用戶，在線對用戶行為做出實時反饋，實時補充推薦與其剛關注用戶相似的用戶。

• 靜態(tài)推薦結果，是指那些與時間關聯(lián)小的推薦item，如我們的用戶推薦95%的結果來自離線計算。
• 機器學習模型，這是一個計算過程時序性上的拆解；offline完成模型的訓練，在線調用model完成item排序，當然也可以通過online-learning或實時特征值完成模型的實時更新。同時，model在線計算時，需要注意缺失特征值的補全，保證offline與online環(huán)境的一致性。

此外，我們也有直接online計算完成的推薦結果，如首頁右側話題推薦，由于用戶對話題需求的差異非常小，它基本上是一個排行榜的需求，但熱門微博也可以有精巧的設計，我們采用了一個曝光動態(tài)收益模型，通過上一段時段的（點擊收益-曝光成本）來控制下一時段的item曝光幾率，取得了非常好的效果，ctr和導流量有3倍以上的提升。

不同類型的推薦結果，要輔以不同的推薦理由，這一點需要前端的多種展示嘗試和offline的日志分析。

效果評測

算法效果的度量方式決定了大家努力的方向，而對于不同類型的推薦，最好根據(jù)產品的定位和目標，采用不同的標準體系去衡量工作結果。實際效果的評測分為3個層次：用戶滿意度、產品層指標（如ctr）、算法層指標，我們的效果評測也會分為人工評測、線上A/B測試、離線算法效果評測3種。

產品指標的制定，應該從產品期望達成的目標出發(fā)，體現(xiàn)用戶滿意度。

對算法離線評測而言，關鍵的是找到一套合理的算法評測指標去擬合產品層指標，因為算法離線評測總是在上線前進行，這個對應做的越好，算法的優(yōu)化成果才能更好的轉化為線上的產品指標。

下圖為我們的算法離線效果評測的架構圖

常用的離線評測指標有：RMSE、召回率、AUC、用戶內多樣性、用戶間多樣性、新穎性等。對于不同的產品有不同的組合指標去衡量，比如用戶推薦中“用戶間多樣性”非常重要，而熱點話題卻可以允許用戶間有較大的結果重合度。