TalkingData誕生于2011年，目前提供應用統計分析、游戲運營分析、移動廣告監測、移動數據DMP平臺、移動行業數據分析和洞察，以及企業級移動數據分析和挖掘的解決方案等產品和服務。隨著各項業務快速發展，需要機器學習支撐的需求也越多越多，數據規模也越來越大，帶來很大的挑戰。而且TalkingData作為一個新興企業，資源相對有限，沒有辦法通過大量增加硬件資源、增加計算能力來應對大數據問題，這給我們帶來了更大的挑戰。本文將簡要介紹我們應對這些挑戰的一些經驗。
計算平臺
TalkingData的數據處理集群目前僅有32臺機器，除了承擔機器學習任務外，更多的工作是數據處理，集群的負荷是非常繁重的。為了盡可能提高集群計算效率和程序開發效率，我們選擇了Spark。我們認為Spark最大的兩個優點。一是數據處理效率高(相對于Hadoop MapReduce而言)。二是開發效率高，Scala語言的特性和Spark的DAG機制使得復雜的數據處理流程和計算邏輯能夠很簡潔地編寫，雖然Scala語言的特性也非常多，但是Spark對Scala語言的掌握程度要求不高，對一般程序員而言，一周時間足夠掌握，而且程序開發效率相比Hadoop MapReduce能夠提高一倍以上。 而且Spark社區的發展也很快(活躍開發者人數已經超過Hadoop MapReduce)，能夠得到較好的社區支持和未來更多新功能。當然也有人質疑Spark在大規模集群上的穩定性，但對我們來說目前這還不是一個問題。
算法分析
大數據給機器學習帶來了很大的機遇，也給機器學習帶來了很多的挑戰。大量的訓練樣本和豐富的特征維度，使得學習算法更容易學到較好的模型。數據更新速度很快，我們也可以更快地更新模型。同時，由于數據規模的增大使得機器學習算法的效率問題越來越突出。首先，從算法復雜度來說，有些算法的復雜度與訓練樣本數(如SVM)或者特征數量(如決策樹)的關系是超線性關系。有一些模型學習中用到的優化方法，如牛頓法，需要計算訓練特征維度規模的海塞矩陣的逆矩陣及其乘法，其計算復雜度為 O(n^3))。隨著數據量和特征數量的增長，模型訓練的計算量急速增加，使得訓練時間變得越來越長而不可接受。而硬件數量的擴充，帶來的計算效率提升往往是低于線性的增長。因此，在進行大數據問題時，我們始終面臨著計算資源相對不足的問題。
為了解決計算復雜度的問題，也出現一些計算量較小的優化方法，如隨機梯度下降(Stochastic Gradient Decent)、小批量梯度下降(mini-Batch Gradient Decent)等方法。但是，機器學習算法大部分都是迭代算法，需要反復使用數據多次，而在處理大規模問題的時候，訓練數據集可能無法全部裝載到內存中，而需要一次一次的從分布式文件系統中讀取，帶來巨大的重復I/O開銷。即使Spark這樣具有In-Memory計算能力的分布式計算框架，同樣受制于集群資源和任務隊列資源的限制，很多情況下并不能夠把訓練數據全部裝載到內存中，還是需要多次從分布式文件系統中讀取數據文件。
數據迭代是機器學習算法處理大數據問題的“阿格硫斯之踵”。因此，盡可能降低算法迭代次數，是提高大規模機器學習任務的有效方法。在實踐中，我們盡可能使用那些只需掃描數據一遍的算法。 如用SimHash來進行聚類， 用關聯表算法來做推薦等。同時，我們也會優化算法實現，使其無需迭代即可訓練出較好的模型，如隨機決策樹算法(Random Decision Tree)、線性回歸(Linear Regression)和邏輯斯特回歸(Logsitic Regression)等。另外，雖然我們以Spark為計算平臺，但是并沒有太多的使用Spark內嵌的MLLib來完成機器學習任務。最主要的原因也是因為MLLib中的算法基本都是迭代算法，其效率達不到我們的要求。
實際應用
TalkingData的業務比較多，需要機器學習提供支持的地方也比較多。目前大致可分為四個方面：移動應用推薦，廣告投放優化，用戶畫像和游戲數據挖掘等四大塊。這里分別簡要介紹下這幾個方面的工作。
【移動應用推薦】
TalkingData為幾家移動應用市場提供過移動應用推薦解決方案如機鋒和同步推，使用用戶的下載和瀏覽行為數據，來進行移動應用的關聯推薦和個性化推薦。但是這種外包模式顯然無法充分利用我們的數據優勢，也不是一種便捷的服務提供模式。前幾年當推薦系統成為工業界和學術界都非常關心的技術時，國內外都出現了以提供推薦系統解決方案的公司。但目前這些公司都已經轉型，比如MyStrands.com, 目前已專注于提供金融客戶數據管理和分析工具，而不再把推薦系統解決方案作為重點。
實踐已經證明第三方提供技術解決方案(包括提供SaaS服務)的模式并不具備很大的市場。我們通過這些外包項目，發現這種模式最大的問題在于數據的收集處理。如果我們要求客戶按照我們提供的數據格式，為我們準備好數據，則會給客戶帶來很大的負擔。由于客戶對推薦系統了解不多，對于如何把已有的數據映射成我們的數據格式通常會感到比較困惑，而難以正確完成。而如果我們根據用戶提供的現有數據進行轉換，又使得我們的服務難以標準化而快速復制。另外就是一旦我們把推薦系統交付給客戶后，我們也很難給客戶提供持續及時的效果優化服務。
因為上述這些問題，我們的推薦系統服務，就從提供外包轉向了提供輕量級的移動應用推薦服務接口。這一服務也可以算是一種SaaS模式，但是與之前其他公司提供的推薦SaaS服務的重大區別是我們不需要客戶提供推薦模型訓練數據，客戶僅需要調用我們的接口獲得關聯推薦和個性化推薦的結果。這就樣也就沒有轉換客戶數據的問題，從而極大地降低推薦系統服務的使用門檻。而通過SaaS服務，我們也可以持續優化和升級推薦算法的效果。
我們能夠提供這樣的服務，主要是隨著TalkingData積累的數據量越來越大，我們逐漸積累了大量的移動應用使用情況數據，這些數據比下載和瀏覽行為數據能更準確地反映用戶的移動應用興趣偏好，我們完全具備了不使用客戶的數據而提供更好的推薦結果的能力。移動應用服務是作為TalkingData DMP里的一組接口向外提供服務的，我們將其作為TalkingData向外提供數據能力的一個出口。目前TalkingData推薦服務接口，每天要處理上億的移動應用使用行為Session來建立推薦模型，覆蓋30萬以上的移動應用。現在，已經有一些移動應用換量平臺使用我們的服務接口，也有一些移動應用市場準備嘗試使用我們的推薦接口來為用戶提供移動應用推薦。
近些年來，推薦算法是數據挖掘，機器學習學術會議上非常熱門的主題之一。可以說相關的文獻是汗牛充棟，各種新算法和算法改進層出不窮。Netflix懸賞100萬美元的推薦系統競賽更是推動了推薦算法研究的熱潮。然而眾多的推薦算法，在實際應用中并不是那么好用。首先對于最基礎的協同過濾算法，即通過計算用戶或者物品之間相似性的方法，由于其計算復雜度與用戶或者物品的數量是超線性的關系，而且需要計算矩陣乘法，難以并行化，用來處理大規模問題比較困難。而基于矩陣分解的方法，除了效率問題外，就是難以保證有較好的訓練數據。因為這些算法的假設是基于每個用戶和物品都有足夠多的評分，但是實際上這是不可能的。另外，矩陣分解算法的目標是預測評分值與實際評分值最小化， 而實際應用中我們真正關心的是用戶對不同物品感興趣程度的排序。最小化評分誤差，是否就能最小化排序誤差?當然，也有一些矩陣分解算法被提出來用以最小化排序誤差，但是其計算量的增長又是十分巨大的。
因此，我們基于現實的數據情況(都是隱式反饋，設備規模較大， 和應用較多)， 采用了在工程上比較好實現，計算效率較高，結果也較好解釋， 但是一點也不先進的算法，或者說算法框架—關聯表。關聯表算法原理比較簡單，可以看做是對關聯規則挖掘的一種簡化。該算法通過統計物品兩兩之間同時出現的頻次(如一個設備在一段時間內使用了哪些應用)，構建出物品到物品的關聯表。在進行關聯推薦時，通過在關聯表中查找目標物品的Top N關聯物品進行推薦。而在進行個性化推薦時，使用用戶最近有行為的那些物品分別查詢關聯表，然后再合并這些結果作為最后的推薦結果。
下面是一個關聯表構建和使用的例子：
基于以上的關聯表，做Top 2的關聯推薦時, 如果目標物品是a2, 推薦的結果是a5和a3(排除a2)。如果要做Top 2個性化推薦，有d11: a1, a2, 用a1查關聯表(a1, a2)得到a5(3), a3(2), a4(2)用a2查關聯表得到a5(5), a3(4), a4(3). 合并以后得到a5(8), a3(6), a4(5), 取前兩個為a5, a3。在此基礎上，根據實際情況的需要，我們還需要對關聯表的結果進行去流行，已避免推薦出來的全都是最流行的那些應用，在這里就不詳述了。
為了平衡長期興趣和短期興趣，我們采用不同時間內的數據建立關聯表，比如一個月，一周和一天的數據分別建立關聯表。也可以使用不同的數據源來建立關聯表，比如使用應用的數據和安裝應用的數據。然后再通過多個關聯表的加權結果來獲得最后的結果。實際上，除了用用戶行為數據來統計應用之間的關聯程度來建立關聯表外，還可以使用其他的數據和方法來構建物品兩兩之間的關系。比如為了解決應用的冷啟動問題，我們使用應用的介紹文本，采用文本處理的一些技術建立應用之間的關聯關系。因此，我們推薦系統的核心就是一系列這樣的關聯表。在做推薦時，通過一定的規則根據輸入參數查詢各個關聯表，然后融合也這些關聯表的結合，作為最終的推薦結果。關聯表方法，從算法的角度上看無疑是十分簡單的，但是是非常適合工程化的。從我們的實踐來看，在很多情況下，在精度上并不比先進算法有太大的差距。
【廣告投放優化】
TalkingData積累了大量移動數據，完全具備進行廣告精準投放的能力。但是作為第三方數據平臺，我們嚴守中立，不會從事任何具體的廣告投放業務，我們僅僅是為移動廣告生態系統提供數據能力，提高整個生態系統的效率。
我們的移動DMP可以提供移動設備的應用興趣等標簽，廣告主、網盟、DSP都可以通過我們的DMP平臺來獲得受眾數據來優化廣告投放。但是也有一些合作伙伴，希望我們能夠直接提供投放的目標設備或者媒體。為了提供較好的結果，我們使用超過1.5億移動設備使用行為作為訓練數據，特征空間超過180萬維，以使用過投放目標應用的設備為正樣本進行訓練。為了能夠對所有設備進行預測并輸出所有應用與目標應用的關系，我們選擇使用Logistic Regression算法進行訓練。Logistic Regress也是處理大規模分類問題的常用算法，模型和訓練過程相對簡單，模型的可解釋性也強。
但是這個規模的問題，如果采用一般的算法實現，如MLLib的實現，在我們的集群上最少也需要幾個小時的時間進行訓練， 這會長時間占據集群資源影響其他任務的完成。 而且這個學習問題，除了數據規模比較大以外，還有一個挑戰就是正樣本數量通常較少。因為需要投放廣告的應用，通常使用的用戶不會太多。我們遇到的情況，正樣本從幾百到幾百萬都有，但即使是幾百萬的正樣本，相對于1.5億的訓練樣本，正樣本比例也是極低的，不過千分之幾。在這種情況下，一般很難訓練得到較好的模型，我們使用過MLLib的LR算法進行訓練，即使有幾百萬的正樣本，模型的AUC指標也僅比0.5高一點，基本不具備區分正負樣本的能力。
這種情況下，一般可以對訓練數據采樣來增加正樣本的比例來改善的學習結果。采樣有兩種方式，一種是增加正樣本數量，另一種是減少負樣本數量。前者會增加訓練樣本的數量而增加計算量。而后者又因為用戶行為數據是稀疏數據且維度很高，如果丟棄大量的負樣本，就會丟棄大量的特征，使得在預測時對只有這些特征的設備無法進行預測。因此我們不希望通過調整樣本比例的方式來解決這個問題。為了解決訓練效率和樣本偏倚的問題，我們優化了Logistic Regression算法求解的過程，使得訓練過程只需要掃描數據一遍即可達到收斂，而且在樣本偏倚很嚴重的情況下也能達到較好的效果。在僅占用集群8%資源的情況下，Logistic Regression算法僅需5分鐘即可完成具有180萬維特征，1.5億樣本的訓練。從測試情況來看，在正樣本較多的情況下(幾十萬到幾百萬)，AUC基本都在0.7以上，很多時候超過0.8，甚至0.9。而在正樣本較少的情況下(幾百到幾千)，一般也能達到0.6以上的AUC。 從實際廣告投放情況來看，通常能提高50%以上的轉化率。
雖然Logistic Regression算法已經優化得很快了，但是在有多個優化任務的時候，還是可能會感到速度太慢。曾有過要跑500個任務的情況，一個任務跑5分鐘，就需要2500分鐘，接近42個小時。實際上500個任務，就需要掃描數據500次，這是最大的開銷。實際上，對于這500個任務，使用的都是同一份數據。其格式如下：
設備id, 應用1， 應用2， 應用3……
只是每個任務會指定一個應用為學習目標，其余的應用則為特征。把原始數據根據指定應用加工成訓練數據，這在Spark中是非常容易完成的。但是每個任務都這么干一次，就會多次的讀取這個數據。顯然，這是非常不經濟的。要提高效率，就需要消除這些冗余IO操作，只進行一次數據讀取。因為我們的算法是在每個數據分片上對數據逐條處理，因此對一條數據，進行多種不同的處理并沒有難度，只是在最后的Reduce階段，需要對不同分片上不同任務的模型結果進行整合，這在技術上不是什么難題。批量訓練程序的效率是非常高的，對于500個任務，批量訓練程序只需要50分鐘就可以完成訓練，訓練時間縮短到原來的2%。平均一個任務(有1.5億訓練樣本，180萬的特征空間)的訓練時間為6秒。批量訓練程序的限制在于內存，任務越多，對應的模型越多，占用的內存就越大。目前的數據情況能夠支撐大約1000個模型。
【用戶畫像】
TalkingData積累的數據以移動設備的行為數據為主，無法直接獲得設備的興趣標簽。而DMP向外提供數據時，又必須以標簽的形式向外提供數據，而且直接提供行為數據也對隱私保護不利。目前主要是利用移動應用的標簽(由我們的專業團隊人工標注)和設備使用應用的數據對設備進行標簽標注。除了為每個設備畫像，有時候我們需要對某個或者某類應用的使用者進行群體畫像。
我們曾通過直接統計用戶群使用過的其他應用比例作為用戶畫像的基礎，但是發現由于應用活躍程度的長尾效應，不管是什么人群，使用率最高的應用基本都是微信，QQ這些平臺級應用，也就沒有辦法總結出這個人群的特征了。而如果將這個人群的各個應用的使用率除以所有設備上的應用使用率，得到應用使用率的提升率，又會突出那些使用率很低的應用。通過調整公式和參數，可以在提升率和使用率之間做一些妥協，但很難達到理想的狀態。
為了解決這個問題，我們將這個問題作為分類問題，使用Logistic Regression模型來處理，以獲得模型中各個特征(即應用)的系數作為關聯程度的分值，取得了非常好的效果。這個學習問題與廣告投放優化中的問題是完全一樣的，都是以某個或者某些應用的使用設備為正樣本，其他設備為負樣本，而以其他的應用作為特征，訓練Logistic Regression模型，從而得到各個應用與目標人群的關聯程度。
從訓練得到的結果來看，流行度高的應用都得到了抑制，而關聯程度高的應用使用率也不會太低。得到了人群的關聯應用后，可以再利用這些應用的標簽為這個人群標注興趣標簽。用這個方法，我們為招商銀行掌上生活，和一些廣告的受眾人群做了畫像，都取得了比較好的效果。
【游戲數據挖掘】
TalkingData的游戲運營分析平臺，是國內手游運營分析工具的開創者。目前為超過3萬款游戲服務，其中包括消滅星星、植物大戰僵尸這些非常受歡迎的游戲。游戲運營分析平臺可以看作應用統計平臺的游戲專業版，在數據收集上增加了游戲相關的一些標準事件如升級，虛擬幣消費，付費等。
因為TalkingData的游戲運營分析平臺的定位，不僅僅是提供統計指標，還需要一定的預測能力，為游戲運營方預測哪些用戶可能流失，哪些用戶有可能付費。流失預測和付費預測，都是分類問題。因為我們需要考慮同時為3萬多款游戲提供這樣的預測，我們沒辦法逐個分析和抽取每款游戲收集的數據，特別是自定義事件來作為訓練的特征。因此從規模化的角度考慮，我們立足于使用十幾個標準化事件的數據作為特征。
而對于自定義事件，我們也將其作為標準化事件來使用，僅使用自定義事件的總次數，和出現的不同的自定義事件的種數作為特征。我們認為一個玩家產生的自定義事件的次數和種類，與玩家對這個游戲的興趣和投入程度應該是正相關的。這樣，既能利用一些自定義事件的信息，但是又不需要對每個游戲的自定義事件做深入分析。當然，這個方案是預測精度向工程可行性的妥協方案，必然是要損失一定的精度。但是從我們的測試結果來看，預測精度還是可以接受的。這個工作與前面提到的廣告投放優化問題，在規模上也有一些不同。對于每一個游戲而言，都不是一個大規模的機器學習問題，訓練樣本和最多也就百萬規模，而特征數量僅有十幾維。用我們優化過的Logistic Regression算法，這樣的規模單機訓練僅需要十幾秒的事件即可完成計算。但另一方面，因為需要支持所有游戲，每次需要訓練3萬多個模型。
這種情況下，運用Spark的并行能力來加速每個任務的訓練速度沒有什么意義，反而會因為多節點之間的同步問題，浪費掉不少計算能力。因此，我們在每個游戲的訓練數據和預測數據處理好以后，把每一個游戲的數據Shuffle到一起，然后在Reduce過程中進行單機的Logistic Regression算法模型訓練，然后進行預測。實際上，這里利用了Spark的并行能力來調度多個單機任務在集群上執行。
總結：機器學習能力服務化
前面介紹了我們在機器學習方面的一些工作。最后，總結一下我們的一點工作經驗。TalkingData作為一個數據公司，很多業務都需要機器學習能力的支持，而我們的機器學習團隊規模并不大，無法對每一個業務需求都做到及時響應。比如廣告投放優化的工作，每次業務部門接到客戶的需求，都需要來聯系我們，讓我們跑結果。這種方式讓我們經常要干一些重復勞動，每次修改一下腳本，然后向Spark集群提交任務，跑出結果，再篩選設備和媒體出來。而客戶的需求也得不到及時的響應。
為了解決這個問題，我們就把這個機器學習的能力進行了服務化，提供了Web界面給我們的業務部門使用。他們收到客戶需求后，就不需要再找我們了，而是直接使用Web工具，自動生成結果。這個工具幾乎不涉及機器學習的專業知識，使用者僅需要指定投放的目標應用是哪一個就行。這樣，我們免去了一些沒有太多意義的重復性勞動，又讓業務部門不再需要依賴我們來跑結果，提高了雙方工作效率。
移動應用推薦服務接口也是一個機器學習能力服務化的例子，我們把為客戶部署推薦系統，改為了提供推薦服務，而且進一步利用了我們的數據能力，降低用戶使用門檻。而我們也可以把精力集中在提供更高質量的標準化服務，而不是為客戶的需求變化而疲于奔命。
基于這些經驗，我們認為一個機器學習團隊，不僅要能提供好的機器學習能力(高效精準的算法)，還需要把這些能力盡可能的服務化，為其他部門或者是客戶提供簡單易用的機器學習服務。機器學習團隊的工作應該是不斷解決新的問題，把這些問題的解決方案固化成服務給公司內外的用戶來使用。當我們解決了一個問題時，就不要再讓這個問題成為我們的日常性工作，而牽扯我們解決新問題的精力。
作者簡介：張夏天，TalkingData首席數據科學家，負責TalkingData機器學習和數據挖掘工作，為TalkingData的數據產品和服務提供支持。曾在IBM中國研究院、騰訊數據平臺部和華為諾亞方舟實驗室任職。對大數據環境下的機器學習、數據挖掘有深入的研究和實踐經驗。
京公網安備 11010502049343號