769
工作職位推薦係統的算法與架構
Indeed.com 每個月有兩億不同的訪客，有每天處理數億次請求的推薦引擎。在這篇文章裏，我們將描述我們的推薦引擎是如何演化的，如何從最初的基於Apache Mahout建立的最簡化可用行產品，到一個在線離線混合的成熟產品管道。我們將探索這些變化對產品性能指標的影響，以及我們是如何通過使用算法、架構和模型格式的增量修改來解決這些挑戰的。進一步，我們將回顧在係統設計中的一些相關經驗，相信可以適用於任何高流量的機器學習應用中。
從搜索引擎到推薦
▼
Indeed的產品運行在世界各地的許多數據中心上。來自每個數據中心的點擊流數據以及其他應用事件被複製到我們在奧斯丁數據中心的一個中心化的HDFS數據倉庫中。我們在這個數據倉庫上進行計算分析並且構建我們的機器學習模型。
我們的職位搜索引擎是簡單而直觀的，隻有兩個輸入：關鍵字和地點。搜索結果頁麵展示了一個匹配的職位列表，並基於相關性進行了排序。搜索引擎是我們的用戶發現職位的主要方式。
我們決定在搜索引擎之上加入職位推薦作為一個新的交互模式是基於以下幾個關鍵原因：
-
Indeed上所有搜索的25%隻指定了一個區域，並沒有搜索關鍵字。有許多的求職者並不確定在他們的搜索中應該用什麼關鍵字
-
當我們發送有針對性的推薦時，求職者的體驗是個性化的
-
推薦可以幫助甚至最複雜的用戶來發現額外的未被搜索所涵蓋的職位
-
推薦為亞馬遜帶來了額外35%的銷量為Netflix75%的內容閱覽。很顯然，推薦能提供額外的價值
推薦職位與推薦產品或者是電影有很顯著的區別。這裏列舉了一些我們在構建推薦引擎時仔細考慮過的因素：
-
（職位）庫存快速增長：我們每天要聚合計算幾百萬新的職位。可以推薦的職位的集合在不斷變化
-
新用戶：每天有幾百萬新的求職者訪問我們的網站並開始他們的職位搜索。我們想要能夠根據有限的用戶數據生成推薦。
-
流動性：在indeed上一個職位的平均生命周期是30天左右。內容的更新十分重要，因為老的職位的需要非常可能已經被滿足了
-
有限的供給關係：一個發布的職位通常隻招一個的應聘者。這和書籍或者電影很不一樣，並不是隻要有庫存就可以同時推薦給很多用戶。如果我們過度推薦一個職位，我們可能會讓雇主收到到上千個應聘申請的轟炸。
如何理解推薦算法
▼
推薦是一個匹配問題。給定一個用戶集合和一個物品集合，我們想要將用戶匹配到他們喜歡的物品上。有兩種高層次的方法可以達成這類匹配：基於內容的和基於行為的。它們各有優缺點，此外也有將兩者結合起來從而發揮各自優勢的方法。
基於內容的方法使用比如用戶偏好設置、被推薦物品的特性之類的數據來決定最佳匹配。對於職位推薦來說，通過職位的描述中的關鍵字來匹配用戶上傳的簡曆中的關鍵字是一種基於內容的推薦方法。通過一個職位的關鍵字來找到其他看上去相似的職位是另外一種基於內容的推薦的實現方法。
基於行為的方法利用了用戶的行為來生成推薦。這類方法是領域無關的，這意味著同樣的算法如果對於音樂或者電影有效的話，也可以被應用在求職領域。基於行為的方法會遇到所謂的冷啟動問題。如果你隻有很少的用戶活動數據，就很難去生成高質量的推薦。
Mahout協同過濾
▼
我們從建立一個基於行為的推薦引擎開始，因為我們想要利用我們已有的求職用戶和他們的點擊數據，我們的首次個性化推薦嚐試是基於Apache Mahout提供的基於用戶間的協同過濾算法的實現。我們將點擊流數據喂給一個運行在Hadoop集群上的Mahout構建器並產生一個用戶到推薦職位的映射。我們建立一個新的服務使得可以運行時訪問這個模型，且多個客戶端應用可以同時訪問這個服務來獲取推薦的職位。
產品原型的結果和障礙
▼
作為一個產品原型，基於行為的推薦引擎向我們展示了一步步迭代前進的重要性。通過快速建立起這個係統並將其展示給用戶，我們發現這種推薦對於求職者來說是有用的。然而，我們很快就遇到了一些在我們的數據流上使用Mahout的問題：
-
模型構建器需要花大約18個小時的時間來處理Indeed網站2013年的點擊流數據，這個數據量要比今日的數據小了三倍。
-
我們隻能一天執行一個模型構造器，這意味著每天新加入的用戶直到第二天為止看不到任何推薦。
-
幾百萬新匯總的職位在模型構造器再次運行之前是不能作為可見的推薦的。
-
我們產生的模型是一個很大的映射，大約占了50吉字節的空間，需要花費數個小時將其通過廣域網從其生成的數據中心拷貝到全球各地的數據中心。
-
Mahout的實現的提供露了一些可配置參數，比如相似度閾值。我們可以調節算法的參數，但是我們想要測試整個不同的算法這樣的靈活性。
為推薦實現最小哈希
▼
我們先解決最重要的問題：構建器太慢了。我們發現在Mahout中的用戶間相似度是通過在n^2複雜度下的用戶間兩兩比較的來實現的。僅對於美國的網站用戶來說（五千萬的訪問量），這個比較的數量將達到15 * 10^15次，這是難以接受的。而且這一計算本身也是批量處理的，新加一個用戶或者一個新的點擊事件就要求重新計算所有的相似度。
我們意識到推薦是一個非精確匹配問題。我們是在尋求方法來發現給定用戶最相近的用戶們，但是我們並不需要100%準確。我們找了一些估算相似度的方法，不需要準確的計算。
主要貢獻者戴夫格裏菲思從一篇穀歌新聞學術論文上看到了最小哈希方法。最小哈希（或者最小獨立序列）允許近似計算傑卡德相似度。將這一方法應用到兩個用戶都點擊過的職位上，我們發現兩個用戶有更多共同的職位點擊，那麼他們的傑卡徳相似度就越高。為所有的用戶對計算傑卡徳相似度的複雜度是O(n^2)，而有了最小哈希後，我們可以將複雜度降到O(n)。
給定一個哈希函數h1, 一個項目集合的最小哈希被定義為將集合中所有項用該哈希函數分別哈希，然後取其中最小的值。由於方差太大，單個哈希函數不足以計算近似傑卡徳相似度。我們必須使用一個哈希函數族來合理地計算近似的傑卡徳距離。通過使用一個哈希函數族，最小哈希可被用來實現可調節傑卡徳相似度閾值的個性化推薦。
“挖掘海量數據集”，一個最近的由斯坦福大學教授萊斯科維克、拉賈羅曼和厄爾曼講解的Coursera課程，非常詳細的解釋了最小哈希。他們書的第三章——“挖掘海量數據集”，解釋了最小哈希背後的數學證明原理。
我們針對推薦的最小哈希的實現涉及到以下三個階段：
1. 簽名計算和集群分配
每一個求職者被映射到一個h個集群的集合，對應了一個哈希函數族H（下麵的偽代碼展示了這一過程）：
H = {H1, H2, ..H20}
for user in Users
for hash in H
minhash[hash] = min{x∈Itemsi| hash(x)}
這裏H是一個包含h個哈希函數的族。這一步的最後，每一個用戶被一個簽名集合所代表，也即一個由h個值組成的集群。
2. 集群擴展
共享相同簽名的用戶被認為是相似的，他們的職位將為被互相推薦。因此我們從每一個在集群中的用戶開始，用其所有的職位來擴展每個集群。
3.生成推薦
為了給一個用戶生成推薦，我們將h個用戶所在的集群中的職位並起來。然後我們除去任何用戶已經訪問過的職位，從而得到最後的職位推薦。
為新用戶推薦職位
▼
最小哈希的數學屬性使得我們可以解決為新用戶推薦職位的問題，並且可以向所有的用戶推薦新的職位。當新的點擊數據到來的時候，我們增量地更新最小哈希簽名。我們也在內存中維護新職位和他們的最小哈希族的映射。通過在內存中保留這兩部分數據，我們就可以在新用戶點擊了一些職位後為他們推薦職位。隻要任何新發布的職位被點擊訪問過，它就可以被推薦給用戶。
在轉移到最小哈希方法後，我們有了一個混合的推薦模型，由一個在Hadoop上的構建的離線每日被更新的組件和一個由當日的點擊數據組成、在內存緩存中實現的在線組件。這兩個模型被整合起來用以計算每一個用戶的最終推薦集合。在我們做了這些改變之後，每一個用戶的推薦變得更加得動態，因為它們將隨著用戶點擊感興趣的職位的同時發生變化。
這些改變中我們認識到，我們可以在性能和準確度上做出權衡，用小的誤差增加來換大的性能提升。我們也認識到可以將較慢的離線模型通過在線的模型進行補充，從而得到更新的推薦結果。
工程基礎設施的影響
▼
包含每一個用戶到他們的推薦的映射的推薦模型是一個相當龐大的文件。由於職位對於每個國家來說都是本地的，我們首先嚐試將我們的數據基於大約的地理邊界進行分片。我們在每一塊區域運行模型構造器，而不是在整個世界運行一個。每一個地區都有多個國家組成。舉個例子，東亞地區包括為中國、日本、韓國、香港、台灣以及印度的推薦。
但是在分片之後，一些區域產生的數據仍然十分龐大，需要花好幾個小時才能通過廣域網從歐洲數據中心拷貝到奧斯丁的Hadoop集群。為了解決這個問題，我們決定增量的傳輸推薦數據，而不是一天一次。我們重用了連續先寫日誌(sequential write ahead logs)的方法，通過日誌結構合並樹來實現。這一方法已經在Indeed的其他大型產品應用中得到驗證，比如我們的文檔服務。
我們修改了我們的模型構建器，將推薦數據存儲成小的分段，而不是產生一個單獨龐大的模型文件。每一個段文件使用順序輸入輸出，並且為快速複製做了優化。這些分段在遠程數據中心運行推薦服務時將被重新組裝成一個日誌結構合並樹。
這一基礎架構的改變使得用戶可以比之前快數個小時在遠程的數據中心上看到他們新的推薦。從我們的A/B測試的結果來看，由用戶更快的得到新職位推薦帶來了30%的點擊量提升。
這一改進展示了工程基礎設施的改進與算法的改進帶來的影響不相上下。
改進A/B測試的速度
▼
建立起計算和更新推薦的管道隻是一個開始。為了改進覆蓋率和推薦質量，我們需要加快我們的A/B測試的速度。我們為了調整最後的推薦集合做了很多決策。這些決策包括，相似度閾值，每一個用戶的推薦包含的職位數量，以及各種不同的用來過濾掉低質量推薦的方法。我們想要調節和優化計算推薦的各個方麵，但是這需要逐個對算法的每個改進都構建新的模型。測試多個改進想法意味著處理用戶請求的服務器上多倍的磁盤以內存占用。
我們開始通過傳輸計算推薦的單獨組件而不是最終的結果來改進我們的A/B測試。我們改變了推薦服務來執行最後的計算，即通過將碎片整合起來，而不是簡單的讀取模型返回結果。重要的推薦子組件是每個用戶的集群分配，從每一個集群到這個集群中的職位的映射以及一個對於每個用戶來說包含不應該推薦給他們的職位的黑名單。我們修改了我們的構建器，來產生這些組件，並且修改了我們的服務，將他們在收到請求時組合起來從而返回最終的推薦列表。
通過實現這種架構上的改變，我們隻傳輸那些在每一個A/B測試中改變的子組件。比如說，如果測試隻調節了什麼樣的職位會從一個用戶的推薦中除去，那麼我們隻需要傳輸這個測試組的黑名單。
這一改變改進了A/B測試的速度的數量級。我們能夠在很短的時間內測試並驗證多個可以改進推薦質量和覆蓋率的想法。之前，由於設置環境的開銷較大，我們平均每個季度隻能測試一個模型中的改進，
我們的經驗表明A/B測試的速度應該在設計大型機器學習係統時就被考慮進去。你能越快地將你的想法放在用戶麵前，那麼你就能越快地在上麵迭代。
這篇文章總結了我們在構建我們的推薦引擎時做出的一係列算法和架構上的改變。我們迭代地構建軟件，我們從一個最簡單原型開始，從中獲取經驗，並不斷改進。這些改變帶來的成果是職位推薦的點擊增加從2014年初最簡原型時的3%增長到了14%。
我們將繼續精煉我們的推薦引擎。我們正在使用Apache Spark建立一個原型模型，建立一個模型集成組合，並精煉我們的優化參數來應對流行偏見問題。
原文發布時間為：2016-12-21
本文來自雲棲社區合作夥伴“大數據文摘”，了解相關信息可以關注“BigDataDigest”微信公眾號
最後更新：2017-05-27 10:32:57