本文以2011年举办的第一届数据挖掘邀请赛的"世纪佳缘会员推荐"赛题为例，尝试了5种排序方法来为新注册会员推荐容易受到亲睐的老会员。
先看5种排序方法的测试结果，以便朋友们有针对性地浏览本文。
基于5倍交叉验证
基于trainingset验证
随机模型
0.08659561709415893
基于投票加权的排序
0.5760898362334391
0.15788352658143304
基于投票加权平均的排序
0.6345833528026847
0.2571459631326702
SVM-Rank（投票加权平均+Profile特征）
0.6344312058678667
0.2570729864787669
基于威尔逊区间法的排序
0.6373419863408559
0.26356889450029836
基于贝叶斯平均的排序
0.6359828316337668
0.25369412463315366
可以发现，基于威尔逊区间法的排序，目前针对该问题取得了最好的推荐结果。其中，基于trainingset验证是为了方便与随机模型结果对比。
说明：
其中，1.0版实现了"投票加权"的排序与推荐
2.0版补充实现了"投票加权平均"和"基于SVM-Rank进行Learning"的排序与推荐
前言
背景：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的候选会员更高的评分（排序靠前），从而推荐给指定会员。本次竞赛的主要排名标准为LearningtoRank问题领域广为使用的NormalizedDiscountedCumulativeGain（NDCG）【3】。
NDCG数学定义如下：
这里给出一个计算NDCG的例子。假设某统计评分模型对5位会员进行了评分，以确定哪位会员更可能获得会员A的青睐（评分越高表示兴趣越大）：
因此对于会员A，
如果能够获得的评分足够理想，从而能够完美地预测出会员A关于5位会员的兴趣排序，则此时相应的DCG称为IdealDCG：
从而对会员A，
NDCG的详细使用说明见"NDCG的示例程序.txt"。
数据说明
train.txt包含约860万条交互记录，每条记录包括4个属性，涉及近6万名会员。格式如下：
一般而言，同一位会员B会被推荐给多位不同的会员，也可能在不同批次中，多次被推荐给同一位会员A。另外，A没有点击B的资料进行查看（rec），通常是由于多种原因造成的。有可能A对B的第一印象（推荐列表中显示的头像）不佳，或者A对在即将下线时获得的推荐不予理睬，又或者是A已经找到合适的交往对象而对其余推荐置之不理，甚至是会员当时的心情，都有可能造成rec（即不发生click）。总之，婚恋网站的用户浏览行为具有较大的随意性，多次推荐同一会员有时会增加点击的概率。对rec类样本的深入分析或许有助于提升推荐系统性能。
男女会员资料（包括部分择偶要求）分别记录在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可能并不奏效，用户行为才是真正值得我们挖掘的信息。
以下分别介绍5种模型方法的设计思路。
(1)基于投票加权的大众欢迎度（代码见：version1(weightedvotes)）
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。
(0.5760898362334391,0.6026498518875004)
(0.15788352658143304,0.19271909879690152)
(2)基于投票加权平均的大众欢迎度（代码见：version2-1(averageweightedvotes)）
基于投票加权的大众欢迎度模型，仅考虑了每个老用户被推荐的总次数以及相应行为权重的加权和信息，但忽略了一个重要信息。例如，某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。
(0.6251315909409053,0.6531515387910409)
(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(averageweightedvotes+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这一方法是经典的Learningtorank问题中的一种重要方法【6】，传统的SVM方法是一种用于解决分类问题的机器学习方法，这里SVM-Rank通过将排序问题转化为分类问题，来间接实现某种信息的排序。
要使用SVM-Rank，可以通过其官网【7】进行了解学习。该程序具备特定的输入与输出格式，以及某些重要的参数设置。其输入格式遵从Learningtorank问题领域的标准测试用数据集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得到所有被推荐用户的排序，进而得到模型的测评分值。
(0.6344312058678667,0.661812638898174)
(0.2570729864787669,0.300026754320666)
与上述模型结果进行比较，发现将大众欢迎度与用户profile信息进行结合，采用Learningtorank的方法并不能对结果有明显提升。
(4)基于威尔逊区间的大众欢迎度（代码见：version3(WilsonInterval)）
根据以上假设，我们知道p是"二项分布"中某个事件（投赞成票）的发生概率，因此我们可以计算出p的置信区间。所谓"置信区间"，是指以某个概率而言，p会落在的那个区间。比如，某个话题的赞成率是80%，但是这个值不一定可信。根据统计学，我们只能说，有95%的把握可以断定，赞成率在75%到85%之间，即置信区间是[75%,85%]。这样我们就可以得到一个根据置信概率确定排名的算法框架，分为以下三步：
置信区间的实质，就是进行可信度的修正，弥补样本量过小的影响。如果样本多，就说明比较可信，不需要很大的修正，所以置信区间会比较窄，下限值会比较大；如果样本少，就说明不一定可信，必须进行较大的修正，所以置信区间会比较宽，下限值会比较小。
现在话题的排名问题转化为计算二项分布的置信区间问题，统计学上广泛使用的"正态区间"方法只适用于样本足够多的情形。为了解决小样本的置信区间计算准确性问题，1927年，美国数学家EdwinBidwellWilson提出了一个修正公式，被称为"威尔逊区间"，很好的解决了这个问题。基于威尔逊区间的置信区间计算公式如下：
威尔逊置信区间的下限值为：
现在回到我们这里所要面对的问题，即如何应用威尔逊区间法给出世纪佳缘会员的排名。威尔逊区间法将实际排序问题抽象为二项分布的统计问题，这里将世纪佳缘每个老会员看作一个话题，在过去有很多其他会员对他们进行了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)，于是就可以使用威尔逊区间法给出排序。
(0.6373419863408559,0.6640676330359446)
(0.26356889450029836,0.30645765290261523)
与基于投票加权平均的排序模型结果进行比较，发现该模型仍有进一步提高。
(5)基于贝叶斯平均的大众欢迎度（代码见：version4(BayesAverage)）
举例来说，一部好莱坞大片有10000个观众投票，一部小成本的文艺片只有100个观众投票。这两者的投票结果，怎么比较？如果使用"威尔逊区间"，后者的得分将被大幅拉低，这样处理是否公平，能不能反映它们真正的质量？一个合理的思路是，如果要比较两部电影的好坏，至少应该请同样多的观众观看和评分。既然文艺片的观众人数偏少，那么应该设法为它增加一些观众。
基于这个思路，IMDB数据库在其网站的电影推荐功能中提出了贝叶斯平均法进行排序。具体计算公式如下：
其中，
-WR，加权得分（weightedrating）
-R，该电影的用户投票的平均得分（Rating）
-v，该电影的投票人数（votes）
-m，排名前250名的电影的最低投票数（现在为3000）
-C，所有电影的平均得分（现在为6.9）
仔细研究这个公式，我们会发现，IMDB为每部电影增加了3000张选票，并且这些选票的评分都为6.9。这样做的原因是，假设所有电影都至少有3000张选票，那么就都具备了进入前250名的评选条件；然后假设这3000张选票的评分是所有电影的平均得分（即假设这部电影具有平均水准）；最后，用现有的观众投票进行修正，长期来看，v/(v+m)这部分的权重将越来越大，得分将慢慢接近真实情况。
这样做拉近了不同电影之间投票人数的差异，使得投票人数较少的电影也有可能排名前列。
把这个公式写成更一般的形式：
-C，投票人数扩展的规模，是一个自行设定的常数，与整个网站的总体用户人数有关，可以等于每个项目的平均投票数
-n，该项目的现有投票人数
-x，该项目的每张选票的值
-m，总体平均分，即整个网站所有选票的算术平均值
这种算法被称为"贝叶斯平均"（Bayesianaverage）。因为某种程度上，它借鉴了"贝叶斯推断"（Bayesianinference）的思想：既然不知道投票结果，那就先估计一个值，然后不断用新的信息修正，使得它越来越接近正确的值。
现在回到我们这里要解决的问题，每个老会员可以被看作一个项目，所有新注册用户对某个老会员进行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
(0.6359828316337668,0.6632682632885964)
(0.25369412463315366,0.2963307946419093)
与基于投票加权平均的排序模型结果进行比较，发现该模型推荐效果有一定提高，但略逊于基于威尔逊区间法的推荐效果。
后记：在阮一峰老师的博客上，分析贝叶斯平均法的缺陷时，提到该方法是假设针对每个项目，用户的投票符合正态分布，如果实际的投票不符合这一假设，则推荐结果可能并不符合实际。对此，他推荐阅读WilliamMorgan的"Howtorankproductsbasedonuserinput"一文【12】，结合多项分布和贝叶斯平均法，通过估计每一分布期望的途径，有可能得到更符合实际情况的排序。通过仔细阅读该文，发现当使用简单的线性打分函数时，基于多项分布和贝叶斯平均法，与本文使用的第二种方法完全一样，也就是说，我们从统计学理论上为第二种方法找到了依据！
总结与讨论
本文涉及互联网推荐系统领域广泛存在的冷启动问题，基于一些经典的推荐算法，如协同过滤、PageRank等并不奏效，于是采用基于大众欢迎度的投票算法来达到一定的推荐效果。最后在试图采用Learningtorank方法，充分利用用户的注册信息时，发现并没有给问题带来更好的解决效果。
基于各种模型的测评分值如下表所示。
具体每种模型算法的使用步骤见附件代码中的"run.txt"。
目前，互联网领域最为广泛的推荐模式是联系用户与商品，即为某个注册用户推荐他可能感兴趣的某件商品，以便通过个性化推荐留住客户，提高流量的转化率、订单成交率。而本文的问题略有不同，是解决如何为用户推荐其他用户的问题。
本文涉及到为新注册用户推荐他可能感兴趣的老用户，是典型的数据挖掘领域冷启动问题。在实际互联网应用中，用户的行为太过于随机，新用户是否对推荐的某个老用户感兴趣，可能完全凭借第一感觉，并不会严格根据某些资料配对（如身高、学历）来决定是否去了解一个老用户。因此，基于老用户在注册后积累的大众欢迎度或人气，来解决这里的冷启动问题，也许是相对最好的方式。