使用协同过滤算法完成ACM线测评系统题目推荐

关于协同过滤的介绍,大家可以找本《集体智慧编程》去读,这本书第二章比较详细的介绍了协同过滤算法。

(TODO:什么是协同过滤算法)

功能简介

这里介绍的是一个协同过滤算法的简单应用:

使用协同过滤算法来完成ACM在线测评系统的题目推荐。

使用的数据来源于这个网站:http://acm.nyist.net

主要有两个功能:

../_images/rec.jpg

推荐系统功能展示图

  1. 相似题目推荐。在 推荐系统功能展示图 中,就是“做了此题的人也做了哪些题”。
  2. 根据个人做题记录个性化推荐一些适合他的题目。(登陆状态、且AC过至少一道题目时可见)

代码与数据都可以从 这个Google Code项目 下载到。

开发语言与底层库的选择:

在大数据时,业界比较常用mahout,因为它本身就是做机器学习用的,其中就包含了协同过滤的实现,并且能跑在hadoop上进行分布式计算。如果是实际工作上使用,这个是我所知道的系统中的首选。但是,由于我主要是为了练习这个算法,用这个价值就不大了。

然后,我就在考虑使用我刚学了几天的函数式语言haskell,不过在装了半天没把haskell的矩阵计算库装好之后,我放弃了。

C++吧,运行效率高,如果是工作使用应该是不错的,不过用C++写起来会比较慢,另外我也没找到一个好用的稀疏矩阵计算的库,所以没选用它。

最后,语言选用了python,并使用了numpy + scipy这两个库来完成矩阵计算库。(安装很方便,每个库都只用下一个msi安装包,直接双击一下,然后点“下一步”搞定)。

数据与代码的说明

数据

数据格式:以下文件如果被墙下载不下来,直接用svn试试吧。

先说用户字典文件:`user_dict <http://acmol.googlecode.com/svn/trunk/recommend/user_dict>`_

每行两列,第一列是用户编号,第二列是用户名

这些数据已经经过处理了,只含有提交过题目的用户

然后是用户提交题目的数据:`rev <http://acmol.googlecode.com/svn/trunk/recommend/data/rev>`_

每行三列,第一列是题目号,第二列是用户名,第三列是运行结果

注意其实这份数据是经过我处理了,处理成了倒序,并且只保留了Accepted的结果。

然后就是题目难度的数据:`score <http://acmol.googlecode.com/svn/trunk/recommend/data/score>`_

数据格式是第一列是题目号,第二列是难度

代码

先说load数据的几个函数,在pre.py中定义:

load_user_dict不怎么需要解释吧,直接把user_dict这个文件load进内存,生成了一个dict和一个list。load_last_n_correct函数需要传一个与上面的rev格式相同的文件(也就是说是与提交顺序相反),然后它会每个用户的最后的n个AC的题目数据读入内存。不过我现在其实一般都直接把n弄得很大,直接把所有数据读了进去。get_user_done_score这个函数严格来说应该不算pre模块的。功能后述。这个文件中大部分代码一看就明白,不用多说。

这个文件中有三个函数,get_cosine_sim、knn、get_recommend_matrix

get_cosine_sim

功能就是求相似度,传入一个矩阵,算出行维度的余弦相似度。

过程

求出每行的平方和,得到一个n*1的矩阵。

输入矩阵(n*m)乘以输入矩阵的转置(m*n),得到一个n*n的矩阵

用第二步中n*n的矩阵每行的每个元素除以第一步中n*1矩阵中每行的对应元素。

计算过程中使用了scipy提供的csc_matrix,它是一个稀疏矩阵计算库,计算起来效率还是蛮高的。

knn (K- nearest- neibour)

保留传入矩阵中每行的前k+1个大元素,其它元素全部置0。(为啥是k+1而不是k个,主要是我想着k个最近邻居加上自己嘛)

这里主要是为了将前一步计算出的矩阵变成一个稀疏矩阵,一是后面的计算比较快,二是去除一些相关度离得比较远的东东。

get_recommend_matrix

功能就是获取出推荐题目矩阵

传入一个用户完成题目情况的矩阵,一个相似度矩阵

以传入相似度矩阵是项目(题目)相似度矩阵(n*n)为例,传入的用户完成情况应该是题目数行,用户数列(n*m)的一个矩阵。(也可以只传入任意的列数,计算出的结果就是这些列的人每道题目的推荐程度)

计算过程:

将相似度矩阵n*n 乘以右面的用户完成情况矩阵n*m的矩阵,得到一个题目数行,用户数列(n*m)的矩阵。以NYOJ的这组数据为例,因为做题完成情况都是1或0,其实第a行,第b列的元素表示第b个人所做的所有题目与第a道题的相似度之和。

求出任意题目与其它所有题目的相似度之和。(一个n*1的矩阵)

让第一步的矩阵的每一列每个元素除以第二步矩阵中对应元素,得到推荐矩阵。

然后最后是main.py,这个文件是经过我调整了又调整之后的结果,反正刚开始直接去算结果不大好,后来经过几次调整才成了这样,现在得到的推荐结果似乎还不错:

直接看代码注释应该能很清楚整个流程,后面就不再多说了。

上面代码里还有一个东西没完善,那就是把隐藏的题目给过滤掉。。

本以为挺牛逼的一个东西,写一写发现这么简单-_-

效果也不错,我看了三个不同阶段的人,推荐出来的结果与其所处的阶段都比较合适。而且计算很快,整个流程跑下来,包括生成所有人的推荐矩阵,也只需要几秒钟时间。

然后另一点体会就是,搞数据挖掘时,有时候你弄出了个看起来不错的结果,你都不知道为啥这样结果不错,结果不好时你也搞不清为啥结果会这样,反正调着各种参数,整着整着就整得结果不错了>_<

后记:

欢迎试用NYOJ的题目推荐功能:

http://acm.nyist.net

折腾了几个小时,也没把scipy在服务器上装好。于是,想了个办法,在OJ上做了几个接口读取做题数据,然后直接在本机计算出相似度矩阵,求出KNN,然后把这些条目插入到OJ的数据库里- -

然后OJ推荐的页面写了个php程序,每次用户点击时计算出每个题对此人的推荐程度(和上面的方法略有不同的是,我是取最后50个正确的提交,计算最终推荐度时,我会让每次提交有不同的权重:倒数第n次正确提交的题目所占权重 = 1 / log( n + 1),这样就能保证越靠后的提交权重越大。

2013.07.26 今天把程序布置到学校提供的一个新服务器上了,不用我再在北京拉数据计算完再传回去了。


转载请指明出处:http://blog.acmol.com