首页 > 技术杂记, 程序人生 > 动手构建一个推荐系统(Recommendation System)

动手构建一个推荐系统(Recommendation System)

写在前面:本文通过构建一个电影推荐系统,深入浅出的介绍推荐系统相关的概念、算法,让读者朋友能够在对推荐系统有比较全面的认识的基础之上,能够轻松地构建出自己的推荐系统。

1. 什么是推荐系统(Recommendation System)

推荐系统是指根据一个群体的偏好,来为群体中的成员提供推荐的系统。现实生活中这样的例子很多,比如豆瓣(Douban.com)读书中的“豆瓣猜”功能,它根据你看过的一些书和相关评价,与整个豆瓣社区其它会员看过的书与评价经过一系列的计算,就能给你推荐一些你没有读过的,但有可能感兴趣的书(如下图所示):
这是我读过的或者正在读的书:

这是豆瓣给我推荐的书:

通过上面的例子,相信大家对推荐系统都有了一个初步的认识。其实生活中还有许许多多的这样的例子,像在线购物中的商品推荐、在线视频播放网站的视频推荐等。

2. 推荐系统相关理论

(1)推荐系统通常可以分为两类:一类是基于人的推荐系统,它利用人与人之间的相似度来进行推荐;一类是基于物品的推荐,它利用物品之间的相似度来进行推荐。通俗地讲,基于人的推荐,是通过分析人与人喜欢的物品,计算出人与人之间的相似度,然后做推荐;而基于物品的推荐,是通过分析某人喜欢的物品与其它物品的相似度,然后来为其做推荐。
(2)推荐系统中比较关键的算法就是相似度的计算,有人与人之间的相似度计算,也有物品与物品之间的相似度计算。相似度计算函数要满足如下特点:拥有同样的函数签名,以一个浮点数做为返回值,其数值越大代表相似度越大。下面介绍几个算法:
a. 欧几里德距离(Euclidean Distance),我们知道两个人的喜好越相似,他们的欧几里德距离值越小,所以需要将欧几里德距离转化一下,这里介绍一个简单的转化:1/(1 + dist), 这样就能保证越相似取值越大,而且取值范围在(0, 1]
b. 皮求逊相关系数(Pearson Correlation Coefficient), 取值范围[-1, 1], 越相似值越大,满足条件
c. Tanimoto系统 (Tanimoto Coefficient),最值范围[0, 1], 越相似值越大,满足条件
(3)在推荐系统里,需要注意:
a. 没有对某物品进行评价的人不能对该物品的推荐打分产生影响
b. 不能因为某人的偏执喜好(打很高或者很低的分)对推荐打分产生明显的影响
为了避免上面的问题,通常采用加权平均的方法来计算某物品的推荐打分(详见第三部分算法实现)

3. 动手构建一个推荐系统

本部分通过构建一个真实的电影推荐系统,来介绍构建一个推荐的基本步骤与方法。

(1)数据集

本系统采用的数据是来自http://www.grouplens.org/node/73的数据,本次实验采用的是如下图所示的第三份数据,总共有6040个用户和3952部电影,以及1000209条相关评价。

(2)核心:推荐函数

typedef double (*ScoreFunc)(const double *, const double *, size_t);
 
void GetRecommendation(
	const double ** allCritics,    //[in]  所有人的打分表
	size_t personNum,              //[in]  所有人的个数
	size_t size,                   //[in]  打分表大小
	size_t myIndex,                //[in]  我在打分表中下标
	ScoreFunc scorer,              //[in]  打分函数
	size_t recNum,                 //[out] 被推荐项个数
	int * recItems,                //[out] 被推荐项列表
	double * recScores             //[out] 被推荐项得分
	)
 {
	double * allRels = new double[personNum];
	::memset(allRels, 0, sizeof(double)*personNum);
	///计算所有的相关度
	for (size_t idx = 0; idx < personNum; ++ idx)
	{
		if (idx == myIndex)
		{
			continue; //it's me, just continue
		}
		allRels[idx] = scorer(allCritics[myIndex], allCritics[idx], size);
	}
 
	double * rels = new double[personNum];
	double * critics = new double[personNum];
	std::multimap mapScores;
	for (size_t itemIdx = 0; itemIdx < size; ++ itemIdx)
	{
		::memset(rels, 0, sizeof(double)*personNum);
		::memset(critics, 0, sizeof(double)*personNum);
		///获取有效的相关度和对应的评分
		for (size_t personIdx = 0; personIdx < personNum; ++ personIdx)
		{
			if (allCritics[personIdx][itemIdx] <= 0)//invalid score
			{
				rels[personIdx] = 0;
				critics[personIdx] = 0;
			}
			else
			{
				rels[personIdx] = allRels[personIdx];
				critics[personIdx] = allCritics[personIdx][itemIdx];
			}
		}
 
		///计算加权打分
		double score = GetWeightedMead(critics, critics + personNum, rels, rels + personNum);
		mapScores.insert(std::make_pair(score, itemIdx));
	}
 
	///获取最终的推荐列表和对应的打分
	std::multimap::reverse_iterator oIt = mapScores.rbegin();
	for (size_t count = 0; count < recNum; ++ count) 	{ 		recItems[count] = oIt->second;
		recScores[count] = oIt->first;
		++ oIt;
	}
 
	delete [] critics;
	delete [] rels;
	delete [] allRels;
}

上面的函数,输入所有人的评分表,以及需要提供推荐的人的相关信息,输出提供的推荐列表,以及相应的打分。这里需要说明的一点是打分函数scorer, 它是一个ScoreFunc类型的函数指针,在实际调用的时候,可以通过传入不同的打分函数,获得在该打分函数下的推荐列表。需要注意打分函数的签名在这里必须与ScoreFunc的定义一致。下面是我定义的打分函数:

double GetEuclideanScore(double dist)
{
	return (1 / (1 + dist));
}
 
double GetPearsonScore(double coef)
{
	return coef;
}
 
double GetTanimotoScore(double coef)
{
	return coef;
}
 
double GetEuclideanScore(const double * myCritics, const double * hisCritics, size_t size)
{
	double dist = GetEuclideanDistance(myCritics, myCritics + size,
		hisCritics, hisCritics + size);
 
	return GetEuclideanScore(dist);
}
 
double GetPearsonScore(const double * myCritics, const double * hisCritics, size_t size)
{
	double coef = GetPearsonCorrelationCoefficient(myCritics, myCritics + size,
		hisCritics, hisCritics + size);
 
	return GetPearsonScore(coef);
}
 
double GetTanimotoScore(const double * myCritics, const double * hisCritics, size_t size)
{
	double coef = GetTanimotoCoefficient(myCritics, myCritics + size,
		hisCritics, hisCritics + size);
 
	return GetTanimotoScore(coef);
}

上面的六个函数,前面三个是对结果进行规范化的函数,使结果满足越相关越大。后面三个函数是真正的评价打分函数。在上面的实现中用到了GetEuclideanDistance, GetPearsonCorrelationCoefficient, GetTanimotoCoefficient, GetWeightedMead这四个函数,它们分别是计算欧几里德距离,Pearson相关系数,Tanimoto系数和加权平均值的函数,在这里我就不给出具体的实现了。

(3)实验结果

我们用三种不同的打分函数,为第1000个用户,推荐20部电影,来对比一下推荐的结果:
a. Euclidean结果:

b. Pearson结果:

c. Tanimoto结果:

从上面的结果中,可以得出如下结果:
a. 采用Euclidean打分推荐和采用Pearson打分推荐的结果中,有16个是相同的
b. 采用Pearson打分推荐和采用Tanimoto打分推荐的结果中,有15个是相同的
c. 采用Tanimoto打分推荐和采用Euclidean打分推荐的结果中,有16个是相同的
从上面的数据可以看出,虽说采用不同的打分函数进行推荐的结果存在一定的差异,但是整体上是一致的,不同的结果的相互覆盖率都超过了75%, 这说明我们的打分函数都还是比较有效的。

  1. 小凳子
    2010年7月12日14:44 | #1

    顶一个。。。

  2. 2010年7月12日16:59 | #2

    @小凳子 欢迎小凳子同学~~ 哈哈~~

  3. 小凳子
    2010年7月13日09:40 | #3

    我是你的忠实粉丝啊 哈哈哈 @小武哥

  4. 2010年7月13日10:36 | #4

    @小凳子 这个不敢。。你是领导,注意自己的身份,哈哈~

  5. 小凳子
    2010年7月13日11:46 | #5

    没有意思。。。@小武哥

  6. 2010年7月13日12:31 | #6
  7. 2010年7月14日23:05 | #7

    恩恩这个不错,估计以后会用到

  8. 2010年7月15日09:00 | #8

    你们在做什么推荐系统么?@cherubine

  9. willyang
    2010年7月16日10:08 | #9

    做的挺好的。
    很赞。
    另外可以考虑用夹角余弦试试,还有电影名以及电影类别的挖掘。

  10. wafht
    2010年11月3日22:00 | #11

    mark一下,很快就能用到了。

  11. huaqingsong
    2011年7月25日11:05 | #12

    谢谢楼主,正好需要这个方面做个论文呢,lzv5

  12. deydoris
    2012年3月5日10:05 | #13

    请问能把这个推荐系统的源码发给我邮箱么?刚入门这个,要慢慢学习呢~~谢谢谢谢啦!

  13. 2012年3月5日22:06 | #14

    代码在这里,你自己下载吧:http://code.google.com/p/xiao5geproject/source/browse/#svn%2Ftrunk%2FPCI@deydoris

  14. Bingo
    2013年6月11日20:28 | #15

    大神太给力了!膜拜~~

  15. Bingo
    2013年6月11日22:32 | #16

    楼主,你好!请问你用的具体是什么算法呢?能否给个出处,我好研究一下,万分感谢!

  16. 2013年6月12日21:44 | #17

    给你推荐一本书《集体智慧编程》@Bingo

  17. susan
    2013年12月14日15:45 | #18

    您好,为什么运行后会出现错误:c++ debug assertion failed: map/set iterator not dereferencable

  18. 淡奶油
    2014年4月6日12:45 | #19

    请问这个是在什么编译环境下运行的啊?我用VC++新建空项目怎么不行呢。。。

  1. 本文目前尚无任何 trackbacks 和 pingbacks.
您必须在 登录 后才能发布评论.