前段时间,从微薄上得到了一个开源电子书:
下载下来看了一下,发现该书讲的数据挖掘算法浅显易懂,受益匪浅,不敢独享,特将我的理解+精简翻译奉上:
1.1. 共同爱好——我喜欢你所喜欢的。
我们从学习推荐系统来开始数据挖掘之旅,推荐系统到处可见,国外的amazon,国内的京东、淘宝等系统。
如何理解推荐系统呢?我们看一个例子:
例如我们在京东浏览一本《数据挖掘概念与技术》:
从页面向下看:
滚动到页面的最下方,可以看到:
京东根据我们说浏览的图书,自动为我们推荐了一些相关的书籍。
推荐系统就是所谓的协同过滤(collaborative filtering),之所以叫协同,是因为得到推荐结果,是大家的力量——从众多用户那里搜集到信息,从中得到推荐信息。
基于用户的推荐——当系统发现你购买了一本《数据挖掘概念与技术》,而有其他用户同时购买了《数据挖掘概念与技术》和《mongobd权威指南》,那么系统猜想你同时喜欢《mongobd权威指南》的可能性也很大,就会把《mongobd权威指南》推荐给你。这种推荐是依据用户相似性,即两个用户有相同的爱好做出的推荐。
基于项目的推荐——将相同类型的东西推荐给用户,如上面的京东推荐的最佳组合就是基于项目的推荐。
首先来看看基于用户的推荐。
1.2. 如何发现两个人具有相似性?
还以图书为例,假设用户对amazon网站的图书进行了评价,从1星到5星,评价从差到好。评价结果如下表:
用户 书名
|
Snow Crash
|
Girl with the
Dragon Tattoo
|
Amy
|
5
|
5
|
Bill
|
2
|
5
|
Jim
|
1
|
4
|
将结果描述在二维图上:
从图上可以形象的看出:Bill和Jim距离较近。
现在有X先生,他给snow crash打了4星,给dragon tattoo 2星,我们为他推荐什么书籍呢?第一步就是要判断一下X和谁的爱好更相似。
1.2.1. Manhattan Distance——曼哈顿距离
最简单的距离计算方法就是曼哈顿距离,在二维图上,点Amy的坐标是(x1,y1),X的坐标是(x2,y2),那么amy和X之间的曼哈顿距离就是:
|x1-x2|+|y1-y2|。
则X到三个人的曼哈顿距离是:
|
到X的曼哈顿距离
|
Amy
|
4
|
Bill
|
5
|
Jim
|
6
|
Amy是最近的,从图上也可以看出。那么如果Amy喜欢《The windup girl》,那么我们就把这本书推荐给X先生。
曼哈顿距离的优点是计算速度快,单过于简单。
1.2.2. EuclideanDistance——欧几里得距离
欧几里得距离是根据毕达哥拉斯定律得到的,至于该定律,想必大家都学过的,就不再多说了。
重新计算三个点到X的欧几里得距离:
|
到X的欧几里得距离
|
Amy
|
3.16
|
Bill
|
3.61
|
Jim
|
3.61
|
1.2.3. N维扩展
实际情况中,用户可能不止给两本书打分,而是多个,这样就把距离的计算从二维空间推广到了N维空间,当然计算方法是不变的。
计算距离的时候,我们只计算共同项,即标有-标记的书不在计算项目中。
动手:
1. 计算一下Hailey和Veronica之间的欧氏距离。
2. 计算一下Hailey和Jordyn之间的欧氏距离。
答案:
缺陷:从上两题中看出,Hailey和Veronica只有两个共同项,但是他们之间的距离却是1.414,而Hailey和Jordyn之间有5项相同,之间的距离是4.387。很明显,Hailey和Jordyn之间更相似,但是欧氏距离却更大。这就说明该算法有缺陷。当计算的共同项较多时,计算的距离值可信度就更高。
1.2.4. 算法泛化
1.2.5. Minkowski距离算法
从曼哈顿距离和欧几里得距离的计算公式,可以推演出所谓的Minkowski距离算法:
当r=1时,就是曼哈顿距离;
当r=2时,就是欧几里得距离;
当r=∞时,就是无上界距离。
1.3. 算法代码实现
基于用户的推荐算法流程:
本文中,使用python来实现以上算法。
准备数据:
将表中的数据使用python的dict存储起来:
users = {"Angelica": {"Blues Traveler": 3.5, "Broken Bells": 2.0, "Norah Jones": 4.5, "Phoenix": 5.0, "Slightly Stoopid": 1.5, "The Strokes": 2.5, "Vampire Weekend": 2.0},
"Bill":{"Blues Traveler": 2.0, "Broken Bells": 3.5, "Deadmau5": 4.0, "Phoenix": 2.0, "Slightly Stoopid": 3.5, "Vampire Weekend": 3.0},
"Chan": {"Blues Traveler": 5.0, "Broken Bells": 1.0, "Deadmau5": 1.0, "Norah Jones": 3.0, "Phoenix": 5, "Slightly Stoopid": 1.0},
"Dan": {"Blues Traveler": 3.0, "Broken Bells": 4.0, "Deadmau5": 4.5, "Phoenix": 3.0, "Slightly Stoopid": 4.5, "The Strokes": 4.0, "Vampire Weekend": 2.0},
"Hailey": {"Broken Bells": 4.0, "Deadmau5": 1.0, "Norah Jones": 4.0, "The Strokes": 4.0, "Vampire Weekend": 1.0},
"Jordyn": {"Broken Bells": 4.5, "Deadmau5": 4.0, "Norah Jones": 5.0, "Phoenix": 5.0, "Slightly Stoopid": 4.5, "The Strokes": 4.0, "Vampire Weekend": 4.0},
"Sam": {"Blues Traveler": 5.0, "Broken Bells": 2.0, "Norah Jones": 3.0, "Phoenix": 5.0, "Slightly Stoopid": 4.0, "The Strokes": 5.0},
"Veronica": {"Blues Traveler": 3.0, "Norah Jones": 5.0, "Phoenix": 4.0, "Slightly Stoopid": 2.5, "The Strokes": 3.0}
}
测试一下
>>> users["Veronica"]
>>>{'The Strokes': 3.0, 'Slightly Stoopid': 2.5, 'Norah Jones': 5.0, 'Phoenix': 4.0,
'Blues Traveler': 3.0}
>>>
1.3.1. 曼哈顿距离算法:
def manhattan(rate1,rate2):
distance = 0
commonRating = False
for key in rate1:
if key in rate2:
distance+=abs(rate1[key]-rate2[key])
commonRating=True
if commonRating:
return distance
else:
return -1
测试算法:
>>> manhattan(users['Hailey'], users['Veronica'])
2.0
>>> manhattan(users['Hailey'], users['Jordyn'])
1.5
>>>
算法:找到距离最近的用户列表。
1.3.2. 返回最近距离用户
def computeNearestNeighbor(username,users):
distances = []
for key in users:
if key<>username:
distance = manhattan(users[username],users[key])
distances.append((distance,key))
distances.sort()
return distances
测试:
>>> computeNearestNeighbor('Hailey', users)
[(2.0, 'Veronica'), (4.0, 'Chan'),(4.0, 'Sam'), (4.5, 'Dan'), (5.0, 'Angelica'),
(5.5, 'Bill'), (7.5, 'Jordyn')]
>>>
#推荐
def recommend(username,users):
#获得最近用户的name
nearest = computeNearestNeighbor(username,users)[0][1]
recommendations =[]
#得到最近用户的推荐列表
neighborRatings = users[nearest]
for key in neighborRatings:
if not key in users[username]:
recommendations.append((key,neighborRatings[key]))
#排序
recommendations.sort(key=lambda rat:rat[1], reverse=True)
return recommendations
测试:
>>> recommend('Hailey', users)
[('Phoenix', 4.0), ('Blues Traveler', 3.0), ('Slightly Stoopid', 2.5)]
>>> recommend('Chan', users)
[('The Strokes', 4.0), ('Vampire Weekend', 1.0)]
>>> recommend('Sam', users)
[('Deadmau5', 1.0)]
Ok ,一个简单的推荐算法就完成了。
练习3:
实现一个Minkowski距离算法:
答案:
03 |
def minkowski(rate1,rate2,r):
|
13 |
distance + = pow ( abs (rate1[key] - rate2[key]),r)
|
19 |
return pow (distance, 1 / r)
|
练习4:
用Minkowski算法计算computeNearestNeighbor中的欧几里得距离。
答案:
def minkowski(rate1,rate2,r):
distance = 0
commonRating = False
for key in rate1:
if key in rate2:
distance+=pow(abs(rate1[key]-rate2[key]),r)
commonRating=True
if commonRating:
return pow(distance,1/r)
else:
return -1
1.3.4. 培生相关系数
用户具有偏见性,如Bill打分在2-4之间,而Hailey打分只有1和4.Jordyn打分只有4和5,那么bill打的4分和Jordyn的4分是一样的评价吗?显然不是,但是计算的时候,算法是无法判断的。因此需要降低这种主观带来的影响。所以就有了新的算法。
培生相关系数:Pearson Correlation Coefficient。
培生相关系数是测量两个变量之间的相关性的数值,其范围是从-1到1之间。1表示完全一致,-1表示不一致。与距离算法相反,培生相关稀疏越大越好。
算法:
由于该公式较难实现,有了以下近似算法:
上面的公式看似复杂,很吓人,不过可以一一分解:
例如我们计算Angelica 和 Bill之间的培生相关系数:
那么分子就是70-67.5=2.5
再来计算分母:
由此可以看到,两者的是完全相关的。
练习5:实现培生相关系数算法
以下是测试结果,用来测试你的算法正确性。
>>> pearson(users['Angelica'], users['Bill'])
-0.90405349906826993
>>> pearson(users['Angelica'], users['Hailey'])
0.42008402520840293
>>> pearson(users['Angelica'], users['Jordyn'])
0.76397486054754316
>>>
答案:
def pearson(rate1,rate2):
sum_xy = 0
sum_x=0
sum_y=0
sum_x2=0
sum_y2=0
n=0
for key in rate1:
if key in rate2:
n+=1
x=rate1[key]
y=rate2[key]
sum_xy += x*y
sum_x +=x
sum_y +=y
sum_x2 +=x*x
sum_y2 +=y*y
#计算距离
if n==0:
return 0
else:
sx=sqrt(sum_x2-(pow(sum_x,2)/n))
sy=sqrt(sum_y2-(pow(sum_y,2)/n))
if sx<>0 and sy<>0:
denominator=(sum_xy-sum_x*sum_y/n)/sx/sy
else:
denominator=0
return denominator
练习6:使用培生相关系数替代距离算法,实现简单推荐系统。
1.3.5. 余弦相似性
从上表中,我们可以凭感觉:Sally与Ann更相似。如何用算法实现上述描述呢?
余弦相似性算法:
余弦相似性的值范围从-1到1,值越大表示相似性越高。
练习7:实现余弦相似性算法,并改造我们的推荐算法。
1.4. 不同算法的适用情况
1. 如果数据比较稠密(即数据中的空项很少),那么适用距离算法如欧几里得距离等较合适。
2. 如果数据的差异较大(即不同用户的数据差别较大),Pearson算法较合适。
3. 数据稀疏,余弦相关性算法较合适。
1.5. 弱点
单纯的基于用户的推荐系统是有缺陷的,例如推荐系统计算得到王五和张三最相似,王五其实一点也不喜欢张学友,而张三是张学友家亲戚,当然,张三非常喜欢张学友咯。那么推荐系统会把张学友推荐给张三,实际情况适得其反。
仔细分析一下,主要原因是因为我们把希望全寄托在了这个最相似的用户身上。如果多考虑几个相似的用户的喜好,推荐的效果会更好。因此提出了k-nearest neighbor 算法。
k-nearest neighbor 算法中的k表示与目标用户最相似的k个用户。例如我们使用pearson算法,得到Ann最相似的三个用户及值:
根据pearson值,计算三个用户所占的权重:
Sally:0.8/(.08+0.7+0.5)=0.4
……
三个人对Grey Wardens的打分:
综合得到Ann对Grey Wardens的打分:
Projected rating = (4.5 x 0.25) + (5 x 0.35) + (3.5 x 0.4)= 4.275
练习8:将pearson算法改造为k-nearest neighbor
本文算法全部代码见附件
下一部分:基于项目的推荐算法,slope-one算法
相关推荐
基于python与协同过滤算法的电影推荐系统设计与实现
基于协同过滤算法的食堂菜品智能推荐程序——记华中科技大学学生创新创业项目实践.pdf
项目概述:基于用户协同过滤的商品推荐系统Java源码——探索与实践 技术栈:核心采用Java语言开发,辅以CSS、JavaScript技术支持。 项目组成:总计259个文件,具体分布如下: - Java源文件:63个,涵盖了推荐系统...
一个电影推荐系统——实现用户登录、评分、推荐,采用协同过滤算法
基于协同过滤算法的食堂菜品智能推荐程序——记华中科技大学学生创新创业项目实践
以基于物品的协同过滤推荐算法———slopeone 算法为核心实现 了协同过滤推荐并设计了整套实验流程,实验选择了一个具有代表性开放数据源作为处理对象,最后地实验结果给出了预测 的均方根误差以及实验的耗时和数据...
一个电影推荐系统——实现用户登录、评分、推荐,采用协同过滤算法 仅能用于学习使用。
针对协同过滤算法中项目(用户)之间的相似度计算出现的部分项目的相似度无法计算、对稀疏数据效果较差等问题,提出了一种计算项目之间相似度的新算法——Dice-Euclidean相似度算法。该算法综合考虑两个项目的共同...
1、资源内容:Spark实践:音乐个性化推荐——基于ALS矩阵分解的协同过滤算法+源代码+文档说明+数据库db+数据 2、代码特点:内含运行结果,不会运行可私信,参数化编程、参数可方便更改、代码编程思路清晰、注释明细...
基于用户和物品的协同过滤——通过统计学方法对数据进行分析的,因此也称 为基于内存的协同过滤或基于邻域的协同过滤; 隐语义模型——采用机器学习等算法,通过学习数据得出模型,然后根据模型 进行预测和推荐,是...
将社会标签的三维关系转化为二维关系,应用传统的推荐算法和模型,如基于内容的推荐方法、协同过滤、图模型等; 使用直接能处理三维关系的算法模型,如张量分解、超图模型。 基于标签的推荐最大的好处是可以利用标签...
本系统主要通过隐式地收集用户对歌曲的播放,下载以及收藏行为记录,进而使用基于最近邻用户的协同过滤推荐算法为当前激活用户推荐歌曲; 对于有歌词信息的歌曲(英文),通过基于异构文本网络的词嵌入来计算歌曲之间的...
人工智能——模拟人类智能的技术和理论,使其在计算机上展现出类似人类的思考、判断、决策、学习和交流能力。这不仅是一门技术,更是一种前沿的科学探索。 【实战项目与源码分享】 我们深入探讨了深度学习的基本...
提出了一种新的混合推荐方法——结合基于高斯概率潜在语义分析模型与改进的基于项目的协同过滤算法,通过建立用户群体混合模型和基于目标项目的邻居集进行预测推荐。实验证明该算法与其他协同过滤算法相比具有更高的...
基于物品相似度的协同过滤推荐的思想大致可分为两部分: 1.计算物与物之前的相似度 2.根据用户的行为历史,给出和历史列表中的物品相似度最高的推荐 通俗的来讲就是: 对于物品 A,根据所有用户的历史偏好,喜欢...
:two: 推荐系统模块:基于物品的协同过滤算法(ItemCF 算法) :three: GUI 模块:PyQt5 **开发环境:Python 3.7.7** ## :point_right: Instruction 运行 GUI 文件夹中的 `main.py` 文件即可。 【备注】 1、该...
提出了一个新的相似度概念——元相似度,并在此基础上对标准的协同过滤算法进行了改进。元相似度即相似度的相似度,与相似度相比元相似度是基于相似度矩阵而不是相关矩阵计算得出的。即使是在相关矩阵中未购买过任何...
基于item的协同过滤推荐 SVD矩阵分解的协同过滤 - ----- 小白不懂运行,下载完可以私聊问,可远程教学 该资源内项目源码是个人的课程设计,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到96分,放心...
利用这些分散的偏好信息,基于其背后可能存在的关联性,来为用户推荐物品的方法,便是协同过滤,或称协作型过滤(collaborative filtering)。 这种过滤算法的有效性基础在于: 用户的偏好具有相似性,即用户是可...