|
0.25369412463315366
</td>
</tr>
</tbody>
</table>
</div>
可以發現，基于威爾遜區間法的排序，目前針對該問題取得了最好的推薦結果。其中，基于training set驗證是為了方便與隨機模型結果對比。
說明：
(1)本項目來自2011年舉辦的"第一屆數據挖掘邀請賽"，筆者周巍然親身參與了比賽的整個過程，本文1.0版為筆者周巍然在賽后根據自己的體會及他人經驗整理而成。
(2) 在周巍然的引導下，筆者嚴程開始涉足互聯網推薦系統這一新興而又實用的領域，將這次比賽的項目作為入門訓練。在周巍然的一些改進思路下繼續研究，同時也嘗試引入Learning to rank方法、以及時下非常流行的各種排序算法（如Reddit評論排序算法），希望能夠進一步提升推薦算法的性能，于是就有了2.0和3.0版。特別地，在3.0版中將前3種方法根據數學含義更名，筆者認為新的命名更為貼切。
(3) 本文是本人有關互聯網推薦系統設計的一次踐行結果，本文適合作為初學者對推薦系統的入門實踐練習。本文全部代碼及測試數據可免費下載，有任何問題歡迎直接聯系任一筆者。
其中，1.0版實現了"投票加權"的排序與推薦
2.0版補充實現了"投票加權平均"和"基于SVM-Rank進行Learning"的排序與推薦
3.0版補充實現了"基于威爾遜區間"和"基于貝葉斯平均"的排序與推薦，該方法思想來自于阮一峰老師的博客，特此感謝！
前言
背景：Amazon的數百萬圖書，Netflix的10萬部電影，淘寶的8億件在線商品，以及數以億萬計用戶的資料和行為記錄……互 聯網公司最近十年的迅猛發展伴隨著海量數據的積累。然而，在線用戶常常面對過多的選擇而顯得無所適從。心理學研究證實這類情境下的用戶有時做出放棄交易的 決定，從而造成大量潛在的用戶流失。統計技術的發展能夠為在線服務商提供更有效的推薦算法，在幫助用戶走出信息過載困境、改善用戶體驗的同時，還能夠挖掘 商品長尾、提升企業價值。在今天，用戶不再局限于通過搜索引擎來尋找感興趣的信息，推薦系統無所不在地為我們發現自己的潛在需求。
本文主題：推薦在社交網絡中的應用同樣受到業界重視【1,2】。目標是為世紀佳緣網站提供會員推薦的智能算法，改善會員推薦的精度，增加網站黏度。
本文目標：通過算法設計提供一個推薦系統，該系統有潛力為世紀佳緣網站的新注冊會員推薦潛在的老會員，使得這些老會員盡可能受到新會員的親睞。
本文內容：算法設計思路、算法具體設計及代碼、算法優劣的評測指標、算法推薦結果。
問題定義
世紀佳緣網站在會員訪問其網站時，會按照一定規則在頁面的特定位置，給會員A推薦（rec）他/她可能感興趣的會員B，此時A僅僅能看到B的頭像（真人照片）。如果A進入B的主頁進行查看，則發生了點擊（click），此時A能瀏覽B的詳細資料。在瀏覽B的資料后，如果A覺得有進一步的興趣，則會通過站內信件（msg）與B聯絡。會員A對同一會員B的click、msg行為有可能多次發生。同一會員B也可能被系統多次推薦給會員A。另外，會員A本身也可能被系統推薦給其他會員。
通過構造有效的統計評分算法模型，評估給定的候選會員集合中哪些會員更容易獲得特定會員 A 的青睞。例如，如果需要給會員 A 推薦（rec）某 10 名指定的候選會員，則構造的模型應該能夠將 1-10 號候選會員按照一定的優先級排序，排在前面的會員被認為更容易獲得 A 的喜愛，從而引起 click（點擊查看會員資料） 或 msg（給該會員發站內信） 的行為。根據推薦效果為事件進行排序： msg > click > rec，對應到評分算法模型中時，其權重依次減小。
評測指標
性能良好的評分模型，應該能夠給予那些引起msg或click的候選會員更高的評分（排序靠前），從而推薦給指定會員。本次競賽的主要排名標準為Learning to Rank 問題領域廣為使用的Normalized Discounted Cumulative Gain（NDCG）【3】。
與經常用來比較兩個序之間的相關程度的肯德爾和諧系數相比，NDCG指標的不同之處在于，它更強調和關注兩個序中排名靠前的部分的相關程度。這與本次競賽項目的實際需求正好相符，因為我們更希望將與會員 A 有可能發生 msg 行為的候選會員排名靠前。
NDCG數學定義如下：
這里  。  表示模型給出的排序中，排名為 的候選會員的實際 ACTION 值（msg=2，click=1，rec=0）。 對每一位獲得推薦建議的會員 A，都需要計算一個相應的 NDCG。所有獲得推薦建議的會員對應的 NDCG 的平均值，作為排名的主要依據。
 表示計算 NDCG 時僅采用排序前 10 的候選會員的 ACTION 進行計算，因此將盡可能多的 msg 或 click 排在前面至關重要。指數變換 是為了增大ACTION 間的差異以凸顯msg和click 的重要性。折扣因子 用 來強調越能將 msg 會員排名靠前的算法越好。例如，兩種不同的推薦算法給出的排序對應的真實 ACTION 如下表所示，由于 RANK 1 算出的 NDCG 為 0.8045，而 RANK 2算出的 NDCG 僅有 0.7579，我們認為 RANK 1 對應的算法更好。
這里給出一個計算 NDCG 的例子。假設某統計評分模型對 5 位會員進行了評分，以確定哪位會員更可能獲得會員 A 的青睞（評分越高表示興趣越大）：
因此對于會員A，
如果能夠獲得的評分足夠理想，從而能夠完美地預測出會員A關于5位會員的興趣排序，則此時相應的DCG稱為Ideal DCG：
從而對會員A，
NDCG的詳細使用說明見"NDCG的示例程序.txt"。
數據說明
本文提供了世紀佳緣網站中某城市會員在最近三個月內完整的交互行為數據 以及相關會員資料。共包含 4 個數據集：train.txt，profile_f.txt，profile_m.txt 和 test.txt。
train.txt 包含約 860 萬條交互記錄，每條記錄包括 4 個屬性，涉及近 6 萬名會 員。格式如下：
在上例中，該網站在第1輪推薦中為會員100033推薦了會員375879，但會員100033并沒有點擊會員375879的資料進行查看（rec），系統也沒有將會員375879再次推薦給會員100033。同樣在第1輪中，會員381720被推薦給會員100033，雖然沒有被點擊，系統仍然在第18輪推薦在再次重復了這一推薦。在第18輪推薦中，會員100033在獲得推薦后，僅僅查看了會員417848的資料（click），但沒有進一步的行為。在第19輪推薦時，會員100033在查看了會員327685的資料后，發出了站內信件（msg）。對同一會員的不同推薦批次間存在時間順序，即：第2批推薦發生的時間要晚于第1批推薦發生的時間。兩批推薦之間的時間間隔由很多因素決定，通常取決于會員登錄網站的頻率，以及瀏覽不同頁面的數量等。這些因素還會影響會員獲得的推薦批次總數。
一般而言，同一位會員B會被推薦給多位不同的會員，也可能在不同批次中，多次被推薦給同一位會員A。另外，A沒有點擊B的資料進行查看（rec），通常是由于多種原因造成的。有可能A對B的第一印象（推薦列表中顯示的頭像）不佳，或者A對在即將下線時獲得的推薦不予理睬，又或者是A已經找到合適的交往對象而對其余推薦置之不理，甚至是會員當時的心情，都有可能造成rec（即不發生click）。總之，婚戀網站的用戶瀏覽行為具有較大的隨意性，多次推薦同一會員有時會增加點擊的概率。對rec類樣本的深入分析或許有助于提升推薦系統性能。
在實際情況中，兩位會員間較少發生多次msg的行為，這可能是經過線上交流后的兩位會員常常會轉為線下交流的原因造成的（如在站內信件中互留聯系電話等）。參賽隊可以自行通過數據證實或分析這一點。對線上多次發生msg交流的樣本進行分析能否提升模型性能，尚不明確。
男女會員資料（包括部分擇偶要求）分別記錄在profile_m.txt和profile_f.txt中。每位會員包含34個特征變量（feature），我們提供了字段列表來說明不同特征變量的含義。
test.txt 文件中包含了用來在線驗證推薦算法效果的會員配對（interaction），及每對會員在三個月內的推薦次數。比賽過程中，為防止過度擬合現象的發生，競賽排名系統僅僅從test.txt中隨機選擇約40%的USER_ID_A及相應樣本進行NDCG的計算，據此進行排名。在競賽結束后，系統會基于所有會員配對重新計算各參賽隊模型的NDCG，并給出最終排名。由于比賽結束后無法再進行在線算法測評，因此本文算法改進主要基于train.txt進行交叉驗證來進行測評。
注意：本數據集由上海花千樹信息科技有限公司提供，僅能用于本次競賽的分析、建模用途。不得用于任何其他商業用途。以學術研究和論文發表為目的的，請與上海花千樹信息科技有限公司聯系并獲取授權。競賽委員會不具有授權權力。
解決方案
數據準備
為選取合適的數據進行模型訓練與測試，需要將train.txt中的數據，基于5倍交叉驗證思想，按照4:1隨機分配，4份用于模型訓練（命名為train_train.txt），1份用于模型測試（命名為train_test.txt）。
該步驟使用到了附件代碼中的splitdata.py，通過給定不同的k值，實現5種不同的數據4:1分配方式。
評分模型測評方案
本文使用了2種方式來對比測評本文提出的模型效果。
第一，按照一般性的數據挖掘模型驗證方法，為防止過擬合【4】，需要使用5倍交叉驗證中的1份數據來測試模型，給出相應測評分值。為方便介紹，本文僅以k=2這一種條件得到交叉驗證所需數據，進行后續的模型訓練與測評（由于處理過程的隨機性，k取其它值的結果相差不大）。
第二，為與競賽官方提供的隨機推薦模型給出的測評分值進行對比，以體現本文設計的模型效果，需要使用整個train.txt數據集測試模型，并給出相應測評分值。
評分模型測評示例
這里以第二種測評方式來說明，根據某種具體的評分模型，得到用戶推薦順序后，如何評測模型性能。
基于附件代碼中的label_train.py和train.txt，得到結果文件label_train.txt，該文件中包含針對每個新用戶userA的推薦用戶的action列表userB_Action_List。文件中每行按照userA升序排列，針對userA推薦的每個userB，可能存在多個action值，僅給出權重最高的action值（msg=2，click=1，rec=0）。
假定基于某種模型，得到train.txt中每個新用戶userA的推薦用戶列表排序文件model_ranks.txt，該文件中每行同樣按照userA升序排列，與label_train.txt中相對應。
于是，基于附件代碼中的evaluate.py、label_train.txt和model_ranks.txt就可以計算分別得到 NDCG@10和NDCG@20分值。例如根據附件NDCG_Example中的示例文件和程序，得到隨機模型的NDCG@10和NDCG@20分值分別為：
(0.08659561709415893, 0.11637114804038115)
評分模型設計
本文所涉及的問題是一個典型的信息排序問題，通過排序先后給出推薦結果順序。
由于數據存在稀疏性及冷啟動問題，也就是對新注冊的用戶進行推薦，這是本問題最大的難點。 針對稀疏數據和冷啟動的數據特性，經典的算法諸如，最近鄰的協同過濾算法、PageRank 排序算法、E-Greedy 排序算法、關聯規則挖掘等并不太奏效，因為對于新注冊的用戶沒有用戶行為可分析。
而最直接的想法是，根據分別記錄在 profile_m.txt 和 profile_f.txt 中男女會員資料（包括部分擇偶要求），其中每位會員包含 34 個特征變量（feature）。在考慮到特征之間的擇偶要求是否匹配，建立一個回歸模型，根據會員 A 和會員 B 的交互行為進行評分，如 msg 給出2分，click 給出1分，rec給出 0分，然而這樣做收效甚微。事實上，因為人的行為太隨機了，而且人往往重相貌高于其他， 不會僅僅因為你年齡、身高符合要求就和你 msg。profile可能并不奏效，用戶行為才是真正值得我們挖掘的信息。
大眾受歡迎度 + 少量的 profile 信息也許是解決冷啟動問題的最佳方式【5】。但本文同樣嘗試了另外兩類流行的方法。一類是，結合基于投票加權平均的大眾歡迎度和少量Profile特征作為特征向量，利用SVM-Rank進行排序的方法，以便了解利用用戶Profile信息之間的配對是否能夠進一步提高推薦效果。另一類是，借鑒時下非常流行的2個著名網站的評論排序算法（Reddit評論排序算法、IMDB電影熱門度排序算法）來嘗試提高推薦效果。
以下分別介紹5種模型方法的設計思路。
(1) 基于投票加權的大眾歡迎度（代碼見：version1(weighted votes)）
Train.txt中第二列為被推薦用戶，這些用戶大多為老用戶。根據這些用戶被推薦的歷史記錄，按照一定的模型，可以得到每個老用戶受大眾歡迎的程度。該模型定義如下：
Popularity = msg_weight * msg_times + click_weight * click_times + rec_weight * rec_times
上式中各參數含義非常明確，分別表示3種行為（msg|click|rec）的權重與次數的加權和。很容易理解，某個老用戶被rec，click，甚至msg的次數越多，某種程度上就說明該用戶更加受到公眾的喜愛，三種行為的權重順序為msg > click > rec，依次取值100，10，1。
基于上述模型和train_train.txt，就可以得到多數老用戶的大眾歡迎程度。由于采用隨機分配原則，train_train.txt中的大部分老用戶，同樣會出現在train_test.txt中。有了這些老用戶的大眾歡迎度排名，針對train_test.txt中的大部分被推薦用戶，就可以根據相應的大眾歡迎度進行排名，如果某個用戶沒有出現在train_train.txt中，則采用設置popularity為0的簡單處理辦法。最終可以得到針對train_test.txt中userA的推薦用戶順序列表文件myranks_train_test.txt。然后根據上述評分模型評測方法，可以計算得到本模型針對train_test.txt的NDCG@10和NDCG@20分值：
(0.5760898362334391, 0.6026498518875004)
同理基于該模型可得到針對train.txt中userA的推薦用戶順序列表文件myranks_train.txt。然后根據上述評分模型評測方法，可以計算得到本模型針對train.txt的NDCG@10和NDCG@20分值：
(0.15788352658143304, 0.19271909879690152)
(2) 基于投票加權平均的大眾歡迎度（代碼見：version2-1(average weighted votes)）
基于投票加權的大眾歡迎度模型，僅考慮了每個老用戶被推薦的總次數以及相應行為權重的加權和信息，但忽略了一個重要信息。例如，某2個老用戶A和B的加權和相同，均為100，但用戶A被推薦了20次，而用戶B僅被推薦了10次，即用戶B在更少的推薦次數內得到了同樣的訪問量。因此，我們可以認為用戶B相對來講擁有更高的大眾歡迎度。
基于這種思路，我們改進了上述模型，得到新的投票加權平均模型：
Popularity = ( msg_weight * msg_times + click_weight * click_times + rec_weight * rec_times) / (msg_times + click_times + rec_times)
類似地，這里三種行為權重msg > click > rec，依次取值100，10，1。
按照類似的處理步驟，基于該模型，針對train_test.txt中userA的推薦用戶順序列表文件myranks_train_test.txt。然后根據上述評分模型評測方法，可以計算得到本模型針對train_test.txt的NDCG@10和NDCG@20分值：
(0.6251315909409053, 0.6531515387910409)
同理基于該模型可得到針對train.txt中userA的推薦用戶順序列表文件myranks_train.txt。然后根據上述評分模型評測方法，可以計算得到本模型針對train.txt的NDCG@10和NDCG@20分值：
(0.22950347745869737, 0.2728895216170754)
在此基礎上，當我們嘗試針對三種行為使用不同的權重時，結果會有微妙的變化。最終，我們經驗性地發現，當三種行為權重msg > click > rec，依次取值2，1.5，1時，能得到相對最好的結果，分別為：
(0.6345833528026847, 0.6619046966636642)
(0.2571459631326702, 0.30000037338792146)
這里的0.25XXXX相比隨機模型的0.08XXXX已經有了很大提升，足以說明本模型已極大地提升了推薦效果。
(3) 基于SVM-Rank（投票加權平均 + Profile構成特征） （代碼見： version2-2(average weighted votes + SVM-Rank)）
雖然上述基于大眾歡迎度的評分模型已經極大地提升了推薦系統的效果，但至今我們沒有使用過用戶的任何Profile信息，而這些信息很有可能成為我們忽視的重要信息。
從附件"數據庫表.xlsx"中我們可以方便地提取一些重要特征字段，這些字段很可能會直接影響到用戶userA是否會在查看某個userB的資料（click）后進而給他發送站內信息（msg）。這里我們提取了如下4個主要特征字段：
Last_login：用戶是否活躍（active），如果最近3個月都未登陸過，新用戶可能不太會想跟TA聯系；
Status：用戶是否處于征友狀態（demand），如果已經在跟他人聯系，將不易被推薦；
Login_count：登陸次數（count），如果某個用戶登陸次數太少，新用戶可能會覺得跟他聯系希望不大；
Avatar：是否有頭像（picture），雖然某些新用戶不要求對方有頭像，但如果有頭像，肯定會起到加分的作用。
再結合上述大眾歡迎度（popularity），這里共計有5個特征，構成特征向量：
Feature_vector = （popularity，active，demand，count，picture）
要想充分利用這些特征向量信息來訓練一個有效的評分模型，最直接的想法就是利用一種用于排序問題的SVM方法：SVM-Rank。
SVM-Rank這一方法是經典的Learning to rank問題中的一種重要方法【6】，傳統的SVM方法是一種用于解決分類問題的機器學習方法，這里SVM-Rank通過將排序問題轉化為分類問題，來間接實現某種信息的排序。
要使用SVM-Rank，可以通過其官網【7】進行了解學習。該程序具備特定的輸入與輸出格式，以及某些重要的參數設置。其輸入格式遵從Learning to rank問題領域的標準測試用數據集LETOR【8】的格式要求，如下所示：
其中，第二列qid:n為某次查詢的編號，這里共包含3次查詢，每次返回4個結果。第一列為每次查詢結果中對應4個結果的相對排序。后面依次給出了5個特征序號及對應的特征值。#后為注釋信息，會被程序自動忽略。
回到我們的問題，我們已經提取了5個特征，基于train.txt、profile_m.txt和profile_f.txt我們可以輕松獲取每個老用戶的特征向量。那么要利用SVM-Rank，就必須將這些特征向量按照給定的格式生成SVM-Rank訓練和預測所需的文件。
以5倍交叉驗證的模型測評方式為例：
首先，我們基于train_train.txt，利用上述投票加權平均的大眾歡迎度模型計算多數用戶的歡迎度排名user_popularity.txt。
其次，基于user_popularity.txt，profile_m.txt和profile_f.txt計算大多數老用戶的特征向量文件user_feature_vector.txt以及后面將被SVM-rank使用的預測數據集user_feature_vector_for_predict.txt。
然后，按照給定的格式生成SVM-Rank訓練模型所需的輸入文件user_svm_train_file.txt，并使用SVM-Rank訓練模型參數。需要注意的是，訓練集中需要包含為每個用戶userA推薦的用戶列表的真實排序。為某個用戶userA推薦一個包含N個用戶的列表，就相當于一次查詢，返回N個結果。作為訓練集，這N個結果的排序必須是已知的。遺憾的是，競賽中未能提供這樣一種數據來反應所有老用戶的實際排序，為此，我們只能采用上述大眾歡迎度user_popularity.txt的結果來為這N個用戶排序，以便構成訓練集。
最后，利用SVM-Rank和user_feature_vector_for_predict.txt預測大多數用戶的分值，對所有用戶的分值進行排序，就可以針對train_test.txt或train.txt得到所有被推薦用戶的排序，進而得到模型的測評分值。
基于該評分模型，針對train_test.txt中userA的推薦用戶順序列表文件myranks_train_test.txt。然后根據上述評分模型評測方法，可以計算得到本模型針對train_test.txt的NDCG@10和NDCG@20分值：
(0.6344312058678667, 0.661812638898174)
同理基于該模型可得到針對train.txt中userA的推薦用戶順序列表文件myranks_train.txt。然后根據上述評分模型評測方法，可以計算得到本模型針對train.txt的NDCG@10和NDCG@20分值：
(0.2570729864787669, 0.300026754320666)
與上述模型結果進行比較，發現將大眾歡迎度與用戶profile信息進行結合，采用Learning to rank的方法并不能對結果有明顯提升。
(4) 基于威爾遜區間的大眾歡迎度（代碼見：version3(Wilson Interval)）
上述基于投票加權平均的排序方法，是比較常規的依據經驗設計的排序模型，而本小節將要介紹的基于威爾遜區間的排序算法是來源于具備強大理論基礎的統計學知識。
最初接觸到基于威爾遜區間排序是來自于阮一峰老師的博客【9】，其博客上先后連載了6篇不同的排序算法。其中，Delicious和Hacker News、Reddit、Stack Overflow及牛頓冷卻定律等算法主要永固解決一定時間內的熱門話題排序問題，排序受時間影響很大；而威爾遜區間及貝葉斯平均更為靈活，可以解決與時間無關的排序問題。
本小節關注基于威爾遜區間的排序問題。大概原理根據阮一峰老師的介紹，再經過自己的整理介紹如下。
首先將用戶對某一話題或評論的投票問題進行如下假設：
- 每個用戶的投票都是獨立事件
- 用戶只有兩個選擇，要么投贊成票，要么投反對票
- 如果投票總人數為n，其中贊成票為k，那么贊成票的比例p就等于k/n
</ul>
那么針對某個評論的大量用戶投票事件就可以轉化為一個統計學上的二項分布問題。在樣本足夠多，即投票數量n越大時，概率p可信度越大，如果p越高，就說明該話題越受歡迎，這沒有問題。但問題出在對于某些話題投票數n相對太少，這時的概率p的可信度會大大降低，即使p很高，也不敢妄下結論說該話題非常受歡迎。
根據以上假設，我們知道p是"二項分布"中某個事件（投贊成票）的發生概率，因此我們可以計算出p的置信區間。所謂"置信區間"，是指以某個概率而言，p會落在的那個區間。比如，某個話題的贊成率是80%，但是這個值不一定可信。根據統計學，我們只能說，有95%的把握可以斷定，贊成率在75%到85%之間，即置信區間是[75%, 85%]。這樣我們就可以得到一個根據置信概率確定排名的算法框架，分為以下三步：
- 計算每個話題的"贊成率"（即贊成票的比例）
- 計算每個"贊成率"的置信區間（以95%的概率）
- 第三步，根據置信區間的下限值，進行排名。這個值越大，排名就越高
</ul>
置信區間的實質，就是進行可信度的修正，彌補樣本量過小的影響。如果樣本多，就說明比較可信，不需要很大的修正，所以置信區間會比較窄，下限值會比較大；如果樣本少，就說明不一定可信，必須進行較大的修正，所以置信區間會比較寬，下限值會比較小。
現在話題的排名問題轉化為計算二項分布的置信區間問題，統計學上廣泛使用的"正態區間"方法只適用于樣本足夠多的情形。為了解決小樣本的置信區間計算準確性問題，1927年，美國數學家 Edwin Bidwell Wilson提出了一個修正公式，被稱為"威爾遜區間"，很好的解決了這個問題。基于威爾遜區間的置信區間計算公式如下：
上述公式中， 表示某一話題的"贊成票比例"，n表示樣本大小， 表示對應某個置信水平的z統計量，這是一個常量，可以通過查表得到。一般情況下，在85%和95%的置信水平下z統計值分別為1.0和1.6。
威爾遜置信區間的下限值為：
可以看到，當n的值足夠大時，這個下限值會趨向。如果n非常小（投票人很少），這個下限值會大大小于。實際上，起到了降低"贊成票比例"的作用，使得該項目的得分變小、排名下降。
這就是目前Reddit評論使用的主要排名算法。
現在回到我們這里所要面對的問題，即如何應用威爾遜區間法給出世紀佳緣會員的排名。威爾遜區間法將實際排序問題抽象為二項分布的統計問題，這里將世紀佳緣每個老會員看作一個話題，在過去有很多其他會員對他們進行了rec，click甚至msg三種操作，可以看作3種投票，所以無法直接應用威爾遜區間法進行排序。
但是，根據經驗，某個老會員被其它會員進行click或msg，都說明其它會員對這個老會員有一定好感，2種情形都可認為是"投贊成票"，而如果老會員僅僅是被系統推薦rec，說明其它會員不感興趣，則可以認為是"投反對票"，由此，可以將問題轉化為一個"二項分布"的統計問題。
這里，我們給定三種事件rec，click和msg以不同的權重（分別為1，1.5，2），則對于某個老會員，
贊成票數為：
Ups = msg_weight * msg_times + click_weight * click_times
反對票數為：
Downs = rec_weight * rec_times
那么投票的贊成率p = ups / (ups + downs)，于是就可以使用威爾遜區間法給出排序。
具體在排序算法中的核心函數，即計算針對每個老會員的投票贊成率的置信區間時，參考率Reddit評論排序的開源代碼【10】。
基于該評分模型，針對train_test.txt中userA的推薦用戶順序列表文件myranks_train_test.txt。然后根據上述評分模型評測方法，可以計算得到本模型針對train_test.txt的NDCG@10和NDCG@20分值：
(0.6373419863408559, 0.6640676330359446)
同理基于該模型可得到針對train.txt中userA的推薦用戶順序列表文件myranks_train.txt。然后根據上述評分模型評測方法，可以計算得到本模型針對train.txt的NDCG@10和NDCG@20分值：
(0.26356889450029836, 0.30645765290261523)
與基于投票加權平均的排序模型結果進行比較，發現該模型仍有進一步提高。
(5) 基于貝葉斯平均的大眾歡迎度（代碼見：version4(Bayes Average)）
除了威爾遜區間法之外，貝葉斯平均法【11】也非常適合于解決與時間無關的排序問題。威爾遜區間法很好地解決了投票人數過少、導致結果不可信的問題，但同時也存在一個致命問題，即馬太效應：排行榜前列總是那些票數最多的項目，新項目或者冷門項目，很難有出頭機會，排名可能會長期靠后。
舉例來說，一部好萊塢大片有10000個觀眾投票，一部小成本的文藝片只有100個觀眾投票。這兩者的投票結果，怎么比較？如果使用"威爾遜區間"，后者的得分將被大幅拉低，這樣處理是否公平，能不能反映它們真正的質量？一個合理的思路是，如果要比較兩部電影的好壞，至少應該請同樣多的觀眾觀看和評分。既然文藝片的觀眾人數偏少，那么應該設法為它增加一些觀眾。
基于這個思路，IMDB數據庫在其網站的電影推薦功能中提出了貝葉斯平均法進行排序。具體計算公式如下：
其中，
- WR， 加權得分（weighted rating）
- R，該電影的用戶投票的平均得分（Rating）
- v，該電影的投票人數（votes）
- m，排名前250名的電影的最低投票數（現在為3000）
- C， 所有電影的平均得分（現在為6.9）
仔細研究這個公式，我們會發現，IMDB為每部電影增加了3000張選票，并且這些選票的評分都為6.9。這樣做的原因是，假設所有電影都至少有3000張選票，那么就都具備了進入前250名的評選條件；然后假設這3000張選票的評分是所有電影的平均得分（即假設這部電影具有平均水準）；最后，用現有的觀眾投票進行修正，長期來看，v/(v+m)這部分的權重將越來越大，得分將慢慢接近真實情況。
這樣做拉近了不同電影之間投票人數的差異，使得投票人數較少的電影也有可能排名前列。
把這個公式寫成更一般的形式：
其中，
- C，投票人數擴展的規模，是一個自行設定的常數，與整個網站的總體用戶人數有關，可以等于每個項目的平均投票數
- n，該項目的現有投票人數
- x，該項目的每張選票的值
- m，總體平均分，即整個網站所有選票的算術平均值
這種算法被稱為"貝葉斯平均"（Bayesian average）。因為某種程度上，它借鑒了"貝葉斯推斷"（Bayesian inference）的思想：既然不知道投票結果，那就先估計一個值，然后不斷用新的信息修正，使得它越來越接近正確的值。
現在回到我們這里要解決的問題，每個老會員可以被看作一個項目，所有新注冊用戶對某個老會員進行rec，click，msg可以看作不同評分（分別為1，1.5，2）的投票，每一次事件相當于一次投票。這樣進行抽象后，就很容易利用貝葉斯平均法來解決我們這里的會員推薦問題。
假定總的老會員數量為num，那么對于某個老會員i：
投票人數ni = msg_times + click_times + rec_times
投票得分scorei = msg_weight * msg_times + click_weight * click_times + rec_weight * rec_times
每個老會員的平均投票數
每次投票的平均得分
基于該評分模型，針對train_test.txt中userA的推薦用戶順序列表文件myranks_train_test.txt。然后根據上述評分模型評測方法，可以計算得到本模型針對train_test.txt的NDCG@10和NDCG@20分值：
(0.6359828316337668, 0.6632682632885964)
同理基于該模型可得到針對train.txt中userA的推薦用戶順序列表文件myranks_train.txt。然后根據上述評分模型評測方法，可以計算得到本模型針對train.txt的NDCG@10和NDCG@20分值：
(0.25369412463315366, 0.2963307946419093)
與基于投票加權平均的排序模型結果進行比較，發現該模型推薦效果有一定提高，但略遜于基于威爾遜區間法的推薦效果。
后記：在阮一峰老師的博客上，分析貝葉斯平均法的缺陷時，提到該方法是假設針對每個項目，用戶的投票符合正態分布，如果實際的投票不符合這一假設，則推薦結果可能并不符合實際。對此，他推薦閱讀William Morgan的"How to rank products based on user input"一文【12】，結合多項分布和貝葉斯平均法，通過估計每一分布期望的途徑，有可能得到更符合實際情況的排序。通過仔細閱讀該文，發現當使用簡單的線性打分函數時，基于多項分布和貝葉斯平均法，與本文使用的第二種方法完全一樣，也就是說，我們從統計學理論上為第二種方法找到了依據！
總結與討論
本文涉及互聯網推薦系統領域廣泛存在的冷啟動問題，基于一些經典的推薦算法，如協同過濾、PageRank等并不奏效，于是采用基于大眾歡迎度的投票算法來達到一定的推薦效果。最后在試圖采用Learning to rank方法，充分利用用戶的注冊信息時，發現并沒有給問題帶來更好的解決效果。
基于各種模型的測評分值如下表所示。
具體每種模型算法的使用步驟見附件代碼中的"run.txt"。
目前，互聯網領域最為廣泛的推薦模式是聯系用戶與商品，即為某個注冊用戶推薦他可能感興趣的某件商品，以便通過個性化推薦留住客戶，提高流量的轉化率、訂單成交率。而本文的問題略有不同，是解決如何為用戶推薦其他用戶的問題。
本 文涉及到為新注冊用戶推薦他可能感興趣的老用戶，是典型的數據挖掘領域冷啟動問題。在實際互聯網應用中，用戶的行為太過于隨機，新用戶是否對推薦的某個老 用戶感興趣，可能完全憑借第一感覺，并不會嚴格根據某些資料配對（如身高、學歷）來決定是否去了解一個老用戶。因此，基于老用戶在注冊后積累的大眾歡迎度 或人氣，來解決這里的冷啟動問題，也許是相對最好的方式。
參考資料
- TOBY SEGARAN，《集體智慧編程》， 2009
- 項亮，《推薦系統實踐》， 2012
- http://en.wikipedia.org/wiki/Discounted_Cumulative_Gain
- http://en.wikipedia.org/wiki/Overfitting
- http://www.jiangfeng.me/blog/149
- http://www.jiangfeng.me/blog/123
- http://www.cs.cornell.edu/people/tj/svm_light/svm_rank.html
- http://research.microsoft.com/en-us/um/beijing/projects/letor//
- http://www.ruanyifeng.com/blog/2012/03/ranking_algorithm_wilson_score_interval.html
- https://github.com/reddit/reddit/blob/master/r2/r2/lib/db/_sorts.pyx
- http://www.ruanyifeng.com/blog/2012/03/ranking_algorithm_bayesian_average.html
- http://masanjin.net/blog/how-to-rank-products-based-on-user-input
</ol>
轉自：http://www.cnblogs.com/supersteven/archive/2012/09/01/2666565.html
本文由用戶 openkk 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。 轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！
|