推荐系统中的恶意用户过滤浅析

这篇文章大约很早前就想写了,不过随着自己屡次复发的拖延症一起被淹没了,直到最近有人在网络上咨询我才重新拿起来写篇博文。

这个题目其实来自于一道基于Hadoop MapReduce的编程类比赛题目,原题大约如下:基于公开数据集MovieLens数据集上的用户评价数据,计算用户对其未看过,并且可能会看的电影的评分。同时请各参赛队伍考虑数据稀疏性问题和恶意用户问题,使推荐系统在上述极端情况下具有较好的性能,其中的恶意用户被定义为在推荐系统中,存在一系列的恶意用户,其行为主要体现在随机打分或为多部电影打相同的分。为了检验推荐算法是否可以减少或避免恶意用户的影响,将通过随机加入恶意用户的方法,比率为5%,10%,并分别执行推荐算法,计算RMSE和MAE。,可以理解成那些在豆瓣上,电影放映期间的水军。

与Spark自己构建了一个MLlib的思路不同,Hadoop将主要精力focus在存储的HDFS和任务分配执行的YARN(包含可以执行MapReduce的任务部分)上面,所以如果熟悉Hadoop MapReduce的人都知道基于这个平台做分布式机器学习一个很好的轮子就是借助于Mahout。当然Mahout确实不怎么好用,依稀记得2013年Reynold来我校进行Spark的“地推”时,有个年轻老师就问了这个问题,Reynold就强烈吐槽了Mahout的难用。时过境迁,Mahout在2015年宣布了不再接受新的MapReduce算法(see 0.10.0 release notes),其执行引擎从Hadoop MapReduce全面转型为Scala + Spark和H2O,真是让人感叹技术圈的技术更新迭代。

回到题目本身,很容易想到的就是前端接一个过滤算法,后端再接一个推荐算法,推荐算法的选择就用工业界已经证明相当成熟的ALS-WR即可,Mahout很早就在Hadoop中实现了该部分,所以把轮子拿来用即可(稍微出乎我意料的是,这个比赛中貌似有些队伍自己实现了基于类似简单协同过滤等方法的推荐系统,效果还很一般,不知为何放着现成的好轮子不用)。数据稀疏性问题不大,毕竟ALS在过拟合以及稀疏数据上的效果都不错,但是如何应对恶意用户,因为自己不是纯做机器学习出身,所以就去搜了一下这方面的论文。恶意用户攻击一般在英文中被表述成shilling attack(托攻击),关于这方面内容的研究似乎不是非常多,在08、09年左右Mehta等人关于robust collaborative filtering的研究取得了不错的进展,过滤恶意用户的方法也就是著名的PCA。原理就是恶意用户的生成往往是遵从一些既有的设定模式,所以这些恶意用户间的协方差比较小,恶意用户与正常用户间的协方差比较大。PCA的核心思想就是压缩原始矩阵的特征维度,在这里就是压缩用户维度,保留包含信息量更大的用户下来(认为是真实用户),论文中用皮尔逊相关系数图表征了这一关系: 50个正常用户与20个攻击用户的皮尔逊积图 PCA部分的算法阐述如下:
PCA select 方法 需要注意的是这里的算法阐述是用求原始输入矩阵的协方差矩阵之后再求特征向量计算来计算SVD,实际分布式环境下一般用SVD得到矩阵Usigma来求PCA,论文中也提及了一般3~5个主成分的精度就可以了。该算法原理清晰,论文有数据支撑,但是本以为很快就搞定的东西居然遇到了困难,首先是Hadoop处理数据(movielens ml-10M)太慢,跑一轮程序需要13、14min左右,跑完还得看结果是否符合预期,验证时候没想到论文中在10% atack size下动辄90%+的精确度,在我这里居然只有很可怜的2、30%。由于当时我还在微软实习,白天得忙着公司的工作,晚上还得折腾这个比赛,由于Hadoop实现的验证太慢,所以我在Spark上又实现了一个PCA,结果发现Spark的实现也没快到哪去。由于整个流程比较长,所以我从向数据中插入恶意用户的代码开始,到数据预处理,中间数据处理(如何存储序列化矩阵)到最后的结果验证,一步步review了代码,在确信各个步骤的实现正确后,我一时没有头绪……此时我突然想到,既然论文中所用的数据movielens-100k规模不大,何不实现一个单机版本的算法用于我的理论验证,所以我很快用breeze(一个用scala写的线性代数库)实现了一个,并且在其上得到了与分布式版本一样糟糕的精确度= =

还好,这说明了我之前的实现是没有问题的。所以我回头看核心的算法表述,并且在网上找到了一个slides,原来根本问题是z-score时的trick,z-score也就是归一化输入矩阵在论文中被一句带过了,该trick就是将输入矩阵的缺失值当作0处理,根据被填上0的每个user的instance来计算均值和标准差,再对该instance进行归一化,而我原来的做法则是将缺失值忽略掉进行计算。在此基础上我果然重现了论文中的精确度。当然这个算法虽然精确度很高,但是有着一个比较致命的弱点,就是恶意攻击用户的比例是需要人为设置的,还好,这是一个比赛,所以题目中已经提及了恶意用户比例,使用这个算法再合适不过了。但是因为输入数据不同,但是我们无法判断输入数据是哪一种类型(正常的,稀疏的还是掺有虚假数据的),所以其他两种case时,仍然会对正常数据进行过滤,去除掉正常的数据会对最后的推荐带来负面影响,所以我离线测试了一下三种case在不同过滤比例下的RMSE,最终选择了过滤4%的数据,(做题嘛,毕竟要应试导向)。我还采用了另外一种方法来避免正常数据的过滤,由于插入虚假数据用户往往会对大量电影进行评分,从而提高其在推荐系统中的影响,所以对于嫌疑用户还加了一个限制,也就是如果该嫌疑用户的评分电影数目大于全局用户平均评分数的2倍以上(做实验的经验值),就认为其是恶意用户。 过滤不同比例恶意用户对应的RMSE

后来比赛的结果是我们在这道题上拿了第一(时间和RMSE的结果综合评价),实事求是的讲,我觉得我在这道题无论思路还是做法都挺直白简单的,只能说大牛没来参加吧(XD)。回头看整个项目的核心insight就是先在小数据集上进行单机debug,再在分布式上验证,这也应该是合理的开发模式。

我在github上放了其中PCA检测的部分代码,包含基于Mahout、Spark和Breeze的实现。