在美團點評的聯盟廣告投放系統（DSP）中，廣告從召回到曝光的過程需要經曆粗排、精排和競價及反作弊等階段。其中精排是使用CTR預估模型進行排序，由于召回的候選集合較多，出于工程性能上的考慮，不能一次性在精排過程中完成候選集的全排序，是以在精排之前，需要對候選廣告進行粗排，來過濾、篩選出相關性較高的廣告集合，供精排使用。
本文首先會對美團點評的廣告粗排機制進行概要介紹，之後會詳細闡述基于使用者、天氣、關鍵詞等場景特征的廣告粗排政策。
廣告粗排架構對引擎端召回的若幹廣告進行排序，并将排序的結果進行截斷，截斷後的候選集會被傳遞給廣告精排子產品處理。
粗排是為了盡可能在候選廣告集合裡找到與流量相關性較高的廣告，一般以有效轉化（通常包括點選後發生後續行為、電話、預約、購買等）為目标。流量因素通常包含媒體、使用者（使用者包含使用者畫像、曆史搜尋、曆史點選等各類使用者行為）因素。此外，還可包含流量外因素，如LBS、目前實時天氣特征等。
考慮到不同流量所覆寫的特征不盡相同：如有的流量包含大量豐富的使用者畫像，而有的流量無使用者畫像，但有辨別性較為明顯的媒體特征，如P2P、母嬰類媒體等，是以對于不同流量，會使用不同的粗排政策，以更好地應用流量特征。
下面将根據不同場景詳細介紹各類粗排機制的離線模型，以及線上應用方案。
使用者興趣對于廣告轉化有着顯著影響。在使用者畫像基礎上，向不同興趣的使用者推薦不同類型的廣告，對廣告的點選和轉化皆能帶來較大提升。下面先對使用者畫像進行簡要介紹，之後闡述我們是如何應用使用者畫像完成廣告定向的。
使用者畫像
使用者畫像也稱使用者标簽。美團點評的使用者畫像與使用者的站内行為息息相關。使用者的原始行為多為使用者對店鋪的浏覽、點選、購買、點評、收藏等，使用者畫像主要是基于這些使用者行為産出的統計型畫像。除了原始行為，我們還整合了其他團隊的資料，包含通過頻繁集挖掘出的使用者預估标簽，以及一些産品上自定義标簽等。此外，聯盟廣告獨有的ADX資料源也被使用進來，ADX日均約數十億次請求，涵蓋了文學、金融、教育、母嬰等各類媒體，我們将媒體帶來的部分使用者資訊進行清洗，并整合到使用者畫像，進而提升使用者畫像的覆寫率和豐富性。融合以上所有資料源資訊，我們産出了針對聯盟廣告的使用者畫像。
在政策應用的同時，考慮到産品投放，使用者标簽體系的設計采用了樹狀結構，以便于投放選擇。
标簽體系分為五大類：
- 與目前美團點評的商戶分類體系強相關（因為廣告主都來自于這些産品分類）的興趣體系，如“美食/火鍋”興趣人群，“親子/樂園”興趣人群等。
- 自然屬性，如使用者的年齡、性别、常駐城市等。
- 社會屬性，如職業、婚戀狀态、受教育程度等。
- 心理認知，消費水準、時尚偏好等。
- 根據某些需求衍生的自定義标簽，标簽可以根據後續需求不斷新增。
在工程方面，使用者畫像工程每日例行化運作一次，離線處理各資料源，并進行合并，産出裝置ID粒度（IMEI或IDFA）的标準化使用者标簽。使用者标簽結果會從Hive表導入Redis緩存，以供線上加載使用。
離線模組化
使用者定向包含了兩層含義：
- 政策應用，針對使用者的不同興趣，對召回的廣告進行權重調整，以篩選出最适合使用者的廣告。
- 産品投放，廣告精準定向，即某些廣告隻投放具有某些興趣的人群，如幼兒教育的廣告，隻投放給家裡有小孩的人群，以擷取更好的投放效果。
本文所述的使用者定向，僅指政策應用。
在使用者定向上，我們使用了頻繁集挖掘方案，因為使用者标簽與商戶分類較為相似，直覺上講，規則的收益可能好于模型。使用頻繁集方案，一方面可以挖掘出規則考慮不到的關聯關系；另一方面，它的可解釋性較強，且後期可以友善地進行人工幹預。
我們抽取一段時間的使用者點選曆史資料，來挖掘使用者興趣與廣告商戶分類的關聯關系。同時，考慮到轉化（包含電話、預約、購買等種種行為）是一種強行為，我們将其等同于多次點選行為，進行升采樣（如一次電話等于兩次點選，等等）。之後使用Spark的ML庫來進行頻繁集挖掘。資料處理上，每條點選紀錄會将廣告商戶的一級、二級、三級分類分别與使用者标簽關聯，即一條記錄會拆分成多份，分别使用不同級别的分類與使用者标簽關聯，這樣保證在計算頻繁集的時候，各個層級分類都不會被遺漏。通過Spark的ML庫找出大量頻繁集後，剔除掉僅包含廣告分類或僅包含使用者标簽的，僅保留兩者共存集合。同時我們限制了使用者标簽在頻繁項中的數量，使其不超過兩個，以保證規則可以覆寫較多線上使用者。接着，我們對标簽與廣告分類的關系進行打分，廣告分類A與興趣标簽B的打分為：\(\frac{\sum(A \bigcap B)}{A}\)。
舉例見下表：
“美食/火鍋”更為大衆化，是以通路量遠大于“親子/兒童樂園”，上列通路量雖為虛構，但與實際認知相符。上清單格想要說明的是，像“美食/火鍋”這樣的廣告分類，可能與很多使用者标簽的共生次數都很高，但由于它本身是大衆化的分類，是以分母取值也很大，則實際關聯打分就會很小（除非是強相關興趣）。用這種方式打分，可以篩選出指定标簽下關聯度較高的廣告二級分類。
得到全部的頻繁集及相應打分後，可線下進行人工篩選，剔除掉明顯不符合認知的頻繁項集。最終結果作為離線模型産出，寫入MySQL。
檢索端加載
檢索端每天定時加載一次離線結果到記憶體中。對于實時廣告請求，先從Redis讀取目前使用者裝置的使用者畫像，然後根據使用者實時位置等條件召回幾百條廣告後，對于目前流量中有使用者畫像的，根據離線訓練結果，對廣告進行打分及排序，排序後會根據線上的設定進行截斷。使用者定向的整體應用架構如下：
在業務引擎端，我們會進行A/B分流實驗，随機劃分一定百分比的流量作為實驗流量，用于進行使用者定向實驗。之後，分析一段時間的累積實驗結果，與base分流作對比，以檢測使用者定向政策帶來的轉化率提升，同時回報給上遊頻繁集模型，用于幹預調整離線産出模型。
實時天氣情況對使用者有一定影響。直覺上來說，炎熱的天氣下，使用者會更傾向于點選遊泳館的廣告；而寒冷的天氣下，飄着熱氣的星巴克廣告會更受歡迎。有些廣告行業則跟天氣的關系不大，如非實時消費的結婚、攝影、親子類廣告。下面将介紹我們基于天氣場景的離線模型及線上打分方案。
資料準備
天氣基礎資料包括溫度、雨量、雪量、天氣現象（大雨、霧霾等）、風力等級等。我們需要的天氣資料，并不需要實時更新，原因如下：
① 從應用角度講，由于天氣情況在短時間内比較穩定，并不需要每時每刻都抓取天氣資料； ② 第三方媒體對DSP（Demand-Side Platform）的響應時間有嚴格限制，如果每次廣告請求都去請求天氣資料，對廣告引擎的性能将造成較大影響。是以我們以小時粒度來儲存天氣資料，即在确定的某個城市、某個小時内，天氣情況是固定的。
天氣資料包含兩種： ① 線下模型使用的曆史天氣資料； ② 線上檢索使用的目前天氣資料。
兩者在相同特征上的資料取值涵義要保證一緻，即特征的一緻性。美團配送團隊對基礎天氣資料進行清洗和加工，每日提供未來72小時内的天氣預報資料，同時儲存了穩定的曆史資料，與我們的需求完全吻合，因為我們使用了該資料。
離線模組化
天氣特征的離線模型選用了AdaBoost模型，該模型可使用若幹簡單的弱分類器訓練出一個強大的分類器，且較少出現過拟合現象。考慮到要線上上檢索端加載弱分類器進行計算，基礎的弱分類器不能太過複雜（以免影響線上性能），基于以上考慮我們選用了AdaBoost常用的樹樁模型（即深度為1的決策樹）。
標明模型後，首先需要對原始資料進行處理，将其處理成适合決策樹分類的特征。我們標明溫度、濕度、降水量、降雪量、天氣情況等特征。以溫度舉例，将其作為連續變量處理，對于特征為溫度的決策樹，訓練合适的分割點，将溫度歸類到合适的葉子節點上；而對于天氣情況icon-code，由于其僅有幾個取值（正常、一般惡劣、非常惡劣等），是以當做離散值對待，進行one-hot編碼，散列到有限的幾個數值上（如1、2、3）。在樹樁模型中，左右葉子節點分别對離散值進行排列組合（如左子樹取1、3，右子樹取2等），直到左右子樹的均方誤內插補點之和為最小。當然，對于離散值較多的情況，出于性能上考慮，多以連續值對待，并訓練合适的分割點分離左右子樹。
對特征進行處理後，可以應用模型對特征進行疊代處理。我們以轉化為目标，搜集一段時間的曆史點選資料，對資料進行特征化處理，最終訓練出合适的離線模型。直覺上來講，天氣對不同行業的轉化影響有顯著差異。某些行業對天氣更為敏感，如餐飲、運動等，而有些行業則對天氣不敏感，如親子、結婚（因為轉化一般不發生在當下）等，是以我們對不同的廣告分類分别做訓練，每個行業訓練一個模型。考慮到在檢索端需要對廣告和天氣的特征關系進行打分，是以分類模型不能完全滿足我們的需求。最終我們選取了AdaBoost的改進版Gentle AdaBoost，有關該模型的論述網上有很多（根據文獻1，在采用樹樁模型時，該模型效果好于傳統的離散AdaBoost），本文不再對其進行數學說明。算法大緻流程如下圖所示：
另外說明一下我們對該模型的一些工程處理，我們去掉了最後的感覺器模型，直接使用回歸函數的和作為打分。在每次疊代過程中，我們會保留目前錯誤率，當疊代達到一定次數，而錯誤率仍大于給定門檻值時，則直接舍棄對該行業的訓練，即在天氣場景定向中，不對該行業的廣告打分。
工程上，我們使用Spark進行特征處理和模型訓練，并将最終結果寫入線上緩存Tair中。其中key為一級及二級行業，value即為AdaBoost模型的多輪疊代結果，同時保留了最後一輪疊代的錯誤率。保留錯誤率的原因是線上上檢索端加載模型時，可以動态配置錯誤率門檻值，根據模型的錯誤率超過門檻值與否來決定是否對廣告打分。另外，考慮到線上加載疊代模型會犧牲性能，我們将疊代輪次控制在100次以内。
天氣場景的離線資料和線上資料模型如下圖所示：
經過Gentle AdaBoost訓練出的多棵樹模型，以JSON格式寫入Tair中；線上在擷取ADX請求後，根據Tair中已經寫好的天氣預報資訊，加載目前小時目前城市的天氣情況，檢索端根據目前天氣和模型，對廣告進行打分和排序。
線上優化
廣告檢索端需要從Tair讀取離線模型，來完成廣告打分。由于第三方媒體對DSP響應時間要求較高，線上上做疊代模型的加載，是一個較為耗時的操作，是以需要做一些優化處理。我們一共做了三層優化處理：
- 模型緩存：對于檢索端召回的幾百條廣告，對廣告一級/二級分類進行緩存處理，對某條廣告打分後，其對應的二級分類及相應模型加入緩存，而後續遇到來自同樣二級行業的廣告，将直接使用緩存模型。
- 打分緩存：由于我們使用了小時級的天氣資料，是以對于指定的城市，在指定的小時内，天氣狀況完全一緻，當廣告一級/二級行業确定後，模型對于該廣告的打分是确定的。是以我們對廣告行業+城市的打分進行緩存處理，且每個整點清空一次緩存。對于已經打分過的城市+廣告行業，可以直接從緩存中讀取并使用打分結果。
- 性能與打分的折中：使用了前面兩種緩存方案後，性能仍無法得到足夠保證，此時我們需要考慮一個折中方案，犧牲一部分廣告打分，以換取性能的提升。即我們使用動态配置的門檻值來控制每次檢索請求中模型疊代的輪次。舉個例子，門檻值設為200次，在整點時刻，前五個召回的廣告的行業各不相同，且使用的模型分别疊代80、90、60、60、30次結束，則本次請求中我們隻對前三個廣告打分（80+90+60<200），并将廣告打分進行緩存。後續召回廣告，其二級分類若能命中緩存，則打分，否則不打分。在第二次廣告請求過來時，同樣沿用這個政策，對已經緩存的廣告打分直接加載，否則疊代模型進行打分，直到達到疊代門檻值200為止。通過打分緩存機制，可以保證前面犧牲掉的廣告行業被逐漸打分。使用該優化政策，可以完全確定上線後的性能，通過調整疊代輪次的門檻值，控制打分與性能的折中關系。
通過以上三層優化處理機制，保證了AdaBoost這樣的疊代模型可以線上上被加載使用。另外，我們還會考察離線模型中的錯誤率，通過線上動态調整門檻值，舍棄一些錯誤率較高的模型，以達到效果的最優化。模型上線後，我們進行A/B testing，以檢測使用天氣場景模型帶來的轉化率提升。
使用者在美團點評站内搜尋的關鍵詞，強烈地表達了使用者的短期偏好。基于關鍵詞定向（Query Targeting）是許多廣告精準定向的利器。尤其對于閉環條件下的應用，如百度鳳巢，淘寶的直通車，當使用者在站内進行搜尋，可以直接根據搜尋詞展示相關廣告，引導使用者在站内轉化。一般來說，關鍵詞定向的效果都非常出色。聯盟的關鍵詞定向，是通過對使用者近期搜尋詞的分析，識别出使用者感興趣的店鋪及店鋪分類，進而在站外App為使用者投放相關廣告。下面将介紹聯盟廣告基于關鍵詞特征的廣告排序機制。
離線模型
離線模型需要根據使用者搜尋詞分析出使用者的偏好，對于大多數搜尋引擎來說，需要使用NLP的相關技術和複雜的基礎特征建設工作。對于美團點評的關鍵詞搜尋場景，由于大部分搜尋詞與美團點評店鋪及店鋪分類強相關（大部分搜尋詞甚至直接是店鋪名稱），且新詞搜尋量增長幅度不大，同時考慮到開發成本，我們的關鍵詞定向舍棄了基礎特征建構的方案，而是直接采用一套合理的離線分析模型，來建構搜尋詞和店鋪分類的關系。
我們選用了TF/IDF模型，來建構關鍵詞和使用者偏好的關系。用這個方案原因是文章-詞模型與詞-店鋪模型非常相似。該方案主要用于計算店鋪分類（或商圈）與關鍵詞的相關程度，也是對其打分的依據。該模型相關資料很多，不再做原理性闡述，此處僅舉一例如下：
使用者搜尋詞為“潮汕火鍋”，計算“美食/火鍋”的商家分類與該關鍵詞的相似程度。
假設： c1 = 搜尋“潮汕火鍋”後的全部點選數， c2 = 搜尋“潮汕火鍋”後點選“美食/火鍋”類目店鋪的全部點選數， c3 = 搜尋詞總數， c4 = 搜尋點選“美食/火鍋”類目的詞總數。則 $$tfidf = (c2 / c1) × log(c3 / (c4 + 1))$$由此計算出店鋪分類與關鍵詞的關系，取topN（根據存儲大小及不同店鋪對同一詞的TF-IDF差距拟定）個店鋪分類。
單店及商圈計算方法與此類似，它們的計算值會同時與店鋪分類的TF-IDF進行比較，不作區分。（此處有一點需注意：如果使用者搜尋“中山公園 火鍋”，可以預見店鋪分類與商圈會同等重要，則最終産出兩條獨立打分規則，分别挂在店鋪分類和商圈下面）。
我們使用Spark來建構離線模型，提取使用者的搜尋詞和搜尋後點選的店鋪及店鋪分類，運用上述方案來計算每個搜尋詞的關聯店鋪及店鋪分類，設定門檻值，保留分數較大的分類結果。
為了提升線上命中率，我們使用了點評分詞系統，對長度較長的搜尋詞進行分詞，同時儲存原始詞和切分後基礎詞的TF-IDF結果。為了友善線上快速檢索，結果同樣儲存在Tair中。以檢索詞為key，關聯店鋪分類和店鋪的TF-IDF打分作為value進行儲存。
實時流計算
對于關鍵詞定向，與使用者定向的一個差別在于前者時效性要求很高，是以需要使用實時計算系統來處理使用者行為，并将最後的結果儲存在Tair叢集。首先通過Kafka訂閱使用者行為實時流，以五分鐘為時間片處理使用者行為，查找使用者ID和搜尋詞，如果搜尋詞過長，則進行分詞，接着從Tair中查找出與該搜尋詞相關的店鋪及店鋪分類和打分（離線模型給出）。接下來會Tair中查找該使用者ID是否有曆史結果，若有，則讀出，對之前的打分進行衰減（衰減方案見下文），并與目前新的打分進行合并；否則，将新的資料及時間戳寫入Tair。該方案的流程圖如下：
比較重要的部分是合并新來的資料與Tair裡的老資料，合并時，如果新資料包含老資料中某些店鋪（店鋪分類），就直接使用新資料中的店鋪（店鋪分類）權重；否則，對老資料中的店鋪（店鋪分類）權重進行衰減，若衰減後權重小于給定的門檻值，則直接将這個店鋪（店鋪分類）從合并資料中剔除。
衰減方案根據時間進行衰減。預設半衰期（即衰減權重從1衰減到0.5的時間長度）為72小時（不同的店鋪分類給予不同的半衰期），使用牛頓冷卻定律，參數計算公式為： 0.5 = 1 × e-α*時間間隔 ，解出α，并帶入下面公式得到實際權重為：$$ w’ = w × e ^{-\alpha × 時間間隔} $$ 其中，w為老權重，w’為新權重。
檢索端排序
檢索端接收到廣告請求，根據目前擷取的使用者ID，從Tair中讀取使用者偏好的店鋪分類，與召回的廣告進行比對，當廣告分類與召回廣告比對成功，則可将Tair讀出的分數進行時間衰減後，作為該廣告的最終打分。檢索端采用與實時流同樣的時間衰減方案，以保證一緻性。舉例如下：
使用者A在早上8:30有火鍋類搜尋行為，Spark Streaming處理後進入Redis，假設此時最新時間戳為8:30，而該使用者在11：00搜尋親子類商鋪，Spark Streaming處理該條記錄後，之前的火鍋權重需要衰減，同時時間戳更新為11:00，假設此時立即有廣告檢索請求命中該使用者，則此時使用者火鍋類偏好權重為11:00時權重；假設下午16:00有ADX請求命中該使用者，則使用者火鍋類權重需要根據16:00到11:00的時間間隔繼續衰減。
除了上述三種定向政策，還有其他基于上下文的定向，重定向等，它們方案各異，但大緻思路與前述方案類似，本文不再詳述。
在經過上述各類定向場景分别打分之後，需要對每個場景打分進行綜合，因為不同的廣告行業在不同場景下的重要性是不同的。如餐飲行業更注重距離和天氣，而麗人、親子等行業較注重媒體和使用者畫像。是以，不同行業下，各個定向打分的權重是不同的。我們使用模型的方式對各個場景打分進行權重的訓練和預測。
綜合打分我們采用了LR模型，分不同廣告行業，以點選為樣本，轉化為模型，以各個場景下的前期打分為特征，進行混合打分權重的離線模組化。 公式如下：$$h_\theta=g(\theta^{T})=\frac{1}{1+e^{-\theta^{T}x}}$$
其中θ是向量，θ0x0 + θ1x1 + …, + θnxn = \(\sum_{i=0}^n \theta _ix _i={\theta}^Tx\)，其中，\(x _1\),…，\(x _n\)是各個場景定向下的具體打分，打分分布在[0,1]之間。
冷啟動時，對每個場景打分給予一個預設權重，積累一定量資料後，使用離線模型訓練出各個廣告行業下的θ向量，并在引擎端加載使用。引擎端加載各個場景的廣告打分，并根據廣告行業加載打分權重，最終完成每個廣告與目前的流量綜合打分。
場景化定向綜合考慮了目前流量的種種場景因素（使用者、天氣、媒體等），分别根據業務需求設計了不同的模型來建構廣告打分機制，并對單個場景的廣告打分進行綜合。通過這種場景化的廣告粗排機制，對召回的廣告進行排序和篩選，可以保留相關性較強的廣告，以用于後續的CTR排序和處理。從實際的A/B testing來看，使用了場景化排序機制的流量，其點選率和轉化率的提升效果都較為顯著。
展望未來，如何豐富各類場景特征（如天氣、媒體的更多特征），引入更多的場景因素（如所處環境周邊店鋪、目前時間使用者行為等），嘗試不同的模型方案，都是下一步的可探索方向。
- Friedman J, Hastie T, Tibshirani R.(2000), Additive Logistic Regression: A Statistical View of Boosting, Annals of Statistics, 28, 337-307.
美團點評廣告聯盟團隊招聘各類資料挖掘、算法，以及Java背景開發的技術人才，有興趣的同學可以發送履歷到suxin03#meituan.com。
馬瑩，美團點評進階算法工程師，2012年畢業于浙江大學，同年加入百度聯盟研發部。2016年加入美團點評聯盟廣告部門，長期從事廣告行業政策算法研究開發工作。專注于計算廣告、使用者畫像、資料挖掘等方向。
一凡，美團點評進階算法工程師，現負責美團點評廣告平台聯盟廣告網盟方向。2011年畢業于華中科技大學，畢業後先後就職于百度、騰訊，2014年加入點評平台，2016年加入美團點評聯盟廣告部，長期緻力于計算廣告算法優化、推薦算法、大資料挖掘等方向。