基于皮尔逊相关度算法的推荐引擎的研究

这是推荐引擎算法的核心技术,皮尔逊相关度算法在推荐系统中是一个判别同类人员的好方法

基于皮尔逊相关度算法的推荐引擎的研究

作者:sharpstill 邮箱:sharpstill@http://

本人专门从事搜索技术以及推荐引擎技术，最近看到一本书《集体智慧编程》,这本书使用python写的代码，非常不错，本调研是以《集体智慧编程》一书中的算法作为调研的依据。将集体智慧编程中的python程序翻译成中文和数学公式叙述。以通俗易懂的方式将数学公式及文字叙述展现出来。

欢迎与我联系探讨技术，我的邮箱是sharpstill@http://

相似值:皮尔逊相关度算法

算法背景:该算法可以视为对欧几里得距离算法的一种改进，因为此算法在对于某些对所有物品都很严苛评分的情况下仍然成立。类似几何中的相似三角形的原理。

该算法的原始数据材料需要三个：（俗话说无材料者：巧妇难为无米之炊） 三样数据为:人员id (uid) -> 电影 -> 评价值

第一步: 得到两个人的皮尔逊相关系数的核心函数

此算法的原理即为求的忽略打分忽高忽低的情况的欧几里得距离，即为欧几里得距离算法的改进算法，有些用户的打分比较严苛，如果打分较低，则对应到二维坐标中的“最佳拟合直线”的距离差为一个恒定值。（详见《集体智慧编程》）

def sim_pearson(prefs,p1,p2): '''

prefs是个嵌套字典,一维表示人,二维表示物品,三维表示评分 '''

si = {}

for item in prefs[p1]:

#将prefs中对应pi人的物品item(第二维中的物品放入si字典,key为item,value为1)

if item in prefs[p2]: si[item] = 1

n = len(si) #没有共同之处

if n==0 : return 1 #对所有偏好求和

#it表示交集列表里的物品,prefs[p1][it]表示 该人 对 该物品 的评分,最后求和 sum1 = sum([prefs[p1][it] for it in si.keys()]); sum2 = sum([prefs[p2][it] for it in si.keys()]);

#求评分的平方和

这是推荐引擎算法的核心技术,皮尔逊相关度算法在推荐系统中是一个判别同类人员的好方法

sum1Sq = sum([pow(prefs[p1][it],2) for it in si.keys()]) sum2Sq = sum([pow(prefs[p2][it],2) for it in si.keys()])

#求乘积之和

pSum = sum([prefs[p1][it]*prefs[p2][it] for it in si.keys()])

#计算皮尔逊评价值

#num=乘积和-(p1直接和*p2直接和/评价物品交集个数) num = pSum - (sum1*sum2/n)

den = sqrt((sum1Sq - pow(sum1,2)/n)) if den == 0:return 0 r = num/den return r

将此函数翻译为数学公式,相似度公式为

n

n

n

num

(p1对物品

i 1

n

i的评分*p2对物品i的评分) ( p1对物品i的评分* p2对物品i的评分

i 1

n

2

n

2

i 1

n

2

n)

den

( (p1对物品i的评分

i 1

) ( p1对物品i的评分)

i 1

n)*( (p2对物品i的评分

i 1

) ( p2对物品i的评分)

i 1

2

n)

p1 和 p2表示两个用户，物品i在本次表示电影i

先对p1和p2求交集,这个交集表示p1和p2都评价过的电影，在这些电影上求

相似度。评价电影的评价值用观看电影时间的百分比表示

最终结果为:similar(相似度) = num/den 相似度即为similar=

n

n

n

(p1对物品

i 1

n

i的评分*p2对物品i的评分) ( p1对物品i的评分* p2对物品i的评分

i 1

n

2

n

2

i 1

n

2

n)

2

( (p1对物品i的评分

i 1

) ( p1对物品i的评分)

i 1

n)*( (p2对物品i的评分

i 1

) ( p2对物品i的评分)

i 1

n)

求相似度的函数与解释

解释：此公式中的物品即为电影，相似度是介于 -1 至 1的数值。为1时表示两者用户评价完全相等

第二步 推荐电影

此步骤即为求得与自己相似度较近的用户们中看过的那些电影中带权平均值较近的那些电影。

这是推荐引擎算法的核心技术,皮尔逊相关度算法在推荐系统中是一个判别同类人员的好方法

（1）拿到一个人的时候计算除自己以外其他人对这个电影的评价值*其他人的相似度，并求和。计算出该电影所有用户的即:

n

该用户没看过的电影

Xj的带权总计值

(Pi对该电影的评价值

i 1

*Pi与本用户的相似度)

此步骤中的 “pi与本用户的相似度即为 步骤一提出的公式计算求得”

(2)计算所有对该电影有过评论的相似度之和

n

电影Xj的相似度之和

(对该电影有过评论

i 1

Pi用户的相似度

)

(3)针对所有的用户求得以下电影的带权平均值列表:

中国有句老话：“兼听则明偏信则暗”，如果只是以跟本用户相关度最大的（关系最好的）用户所看的电影作为推荐，则必然出现“偏信则暗”的情况，实际情况是:有用户关系与他第二好的用户所看的电影列表中，出现的推荐电影很可能评价较高，更受此用户欢迎，因此在这个地方使用“用户相似度”作为权，此“用户相似度”求的加权平均值(加权平均值的分母为权之和)。

n

给用户Pm推荐的电影=列表[

(Pi对该电影的评价值

i 1

n

*Pi与本用户的相似度Pi用户的相似度

)

)

]

(对该电影有过评论

i 1

中的前几项。

算法复杂度问题：

比较次数问题，由于每两个用户如果做相似度比较，因此用户量较大时，比较次数一定会成为算法时间复杂度的最重要因素，3个用户之间两两比较计算相似度需要对比次数为 即ABC三个用户,AB、AC、BC即为3次。利用次数=Cn2计算出n个用户比较次数为

n*(n 1)

2

次。即为n个用户，比较次数增长

n 12

倍。

假设有一亿活跃用户，比较相似度的计算将发生4999999950000000次。这是个天文数字，如何降低比较次数，成为我们推荐系统中计算相似度的一个关键。 但是此为数学理论值，实际中不可能每两个用户之间都存在观看电影交集，所以比较数字是远远小于

n*(n 1)

2

的。

为了解决这个问题，聚类成为一个关键技术，可显著降低程序的计算量，加快速度。 在下一篇文章中，我将会详细阐述分类聚类在程序员生活中的应用。